More Like this

1. Path-Based Spectral Clustering: Guarantees, Robustness to Outliers, and Fast Algorithms

   Little, Anna; Maggioni, Mauro; Murphy, James M (January 2020, Journal of machine learning research)

   null (Ed.)

   We consider the problem of clustering with the longest-leg path distance (LLPD) metric, which is informative for elongated and irregularly shaped clusters. We prove finite-sample guarantees on the performance of clustering with respect to this metric when random samples are drawn from multiple intrinsically low-dimensional clusters in high-dimensional space, in the presence of a large number of highdimensional outliers. By combining these results with spectral clustering with respect to LLPD, we provide conditions under which the Laplacian eigengap statistic correctly determines the number of clusters for a large class of data sets, and prove guarantees on the labeling accuracy of the proposed algorithm. Our methods are quite general and provide performance guarantees for spectral clustering with any ultrametric. We also introduce an efficient, easy to implement approximation algorithm for the LLPD based on a multiscale analysis of adjacency graphs, which allows for the runtime of LLPD spectral clustering to be quasilinear in the number of data points. 

   more » « less
2. Path-Based Spectral Clustering: Guarantees, Robustness to Outliers, and Fast Algorithms

   Little, Anna; Maggioni, Mauro; Murphy, James M. (January 2020, Journal of machine learning research)

   null (Ed.)

   We consider the problem of clustering with the longest-leg path distance (LLPD) metric, which is informative for elongated and irregularly shaped clusters. We prove finite-sample guarantees on the performance of clustering with respect to this metric when random samples are drawn from multiple intrinsically low-dimensional clusters in high-dimensional space, in the presence of a large number of high-dimensional outliers. By combining these results with spectral clustering with respect to LLPD, we provide conditions under which the Laplacian eigengap statistic correctly determines the number of clusters for a large class of data sets, and prove guarantees on the labeling accuracy of the proposed algorithm. Our methods are quite general and provide performance guarantees for spectral clustering with any ultrametric. We also introduce an efficient, easy to implement approximation algorithm for the LLPD based on a multiscale analysis of adjacency graphs, which allows for the runtime of LLPD spectral clustering to be quasilinear in the number of data points. 

   more » « less
3. Path-Based Spectral Clustering: Guarantees, Robustness to Outliers, and Fast Algorithms

   Little, Anna V; Maggioni, Mauro; Murphy, James M (January 2020, Journal of machine learning research)

   We consider the problem of clustering with the longest-leg path distance (LLPD) metric, which is informative for elongated and irregularly shaped clusters. We prove finite-sample guarantees on the performance of clustering with respect to this metric when random samples are drawn from multiple intrinsically low-dimensional clusters in high-dimensional space, in the presence of a large number of high-dimensional outliers. By combining these results with spectral clustering with respect to LLPD, we provide conditions under which the Laplacian eigengap statistic correctly determines the number of clusters for a large class of data sets, and prove guarantees on the labeling accuracy of the proposed algorithm. Our methods are quite general and provide performance guarantees for spectral clustering with any ultrametric. We also introduce an efficient, easy to implement approximation algorithm for the LLPD based on a multiscale analysis of adjacency graphs, which allows for the runtime of LLPD spectral clustering to be quasilinear in the number of data points. 

   more » « less
4. Bipartite Tight Spectral Clustering (BiTSC) Algorithm for Identifying Conserved Gene Co-clusters in Two Species

   https://doi.org/10.1093/bioinformatics/btaa741  

   Sun, Yidan Eden; Zhou, Heather J; Li, Jingyi Jessica (August 2020, Bioinformatics)

   Birol, Inanc (Ed.)

   Abstract Motivation Gene clustering is a widely-used technique that has enabled computational prediction of unknown gene functions within a species. However, it remains a challenge to refine gene function prediction by leveraging evolutionarily conserved genes in another species. This challenge calls for a new computational algorithm to identify gene co-clusters in two species, so that genes in each co-cluster exhibit similar expression levels in each species and strong conservation between the species. Results Here we develop the bipartite tight spectral clustering (BiTSC) algorithm, which identifies gene co-clusters in two species based on gene orthology information and gene expression data. BiTSC novelly implements a formulation that encodes gene orthology as a bipartite network and gene expression data as node covariates. This formulation allows BiTSC to adopt and combine the advantages of multiple unsupervised learning techniques: kernel enhancement, bipartite spectral clustering, consensus clustering, tight clustering, and hierarchical clustering. As a result, BiTSC is a flexible and robust algorithm capable of identifying informative gene co-clusters without forcing all genes into co-clusters. Another advantage of BiTSC is that it does not rely on any distributional assumptions. Beyond cross-species gene co-clustering, BiTSC also has wide applications as a general algorithm for identifying tight node co-clusters in any bipartite network with node covariates. We demonstrate the accuracy and robustness of BiTSC through comprehensive simulation studies. In a real data example, we use BiTSC to identify conserved gene co-clusters of D. melanogaster and C. elegans, and we perform a series of downstream analysis to both validate BiTSC and verify the biological significance of the identified co-clusters. Availability and implementation The Python package BiTSC is open-access and available at https://github.com/edensunyidan/BiTSC. 

   more » « less
5. Enhancing Streamflow Prediction in Ungauged Basins Using a Nonlinear Knowledge‐Based Framework and Deep Learning

   https://doi.org/10.1029/2024WR037152  

   Ghaneei, Parnian; Foroumandi, Ehsan; Moradkhani, Hamid (October 2024, Water Resources Research)

   Abstract In hydrology, a fundamental task involves enhancing the predictive power of a model in ungagged basins by transferring information on physical attributes and hydroclimate dynamics from gauged basins. Introducing an integrated nonlinear clustering framework, this study aims to develop a comprehensive framework that augments predictive performance in basins where direct measurements are sparse or absent. In this framework, uniform manifold approximation and projection (UMAP) is used as a nonlinear method to extract the essential features embedded in hydro‐climatological attributes and physical properties. Then, the Growing Neural Gas (GNG) clustering model is used to find the basins that potentially share similar hydro‐climatological behaviors. Besides UMAP‐GNG, the integration of Principal Component Analysis (PCA) as a linear method to reduce dimensionality with common clustering methods are also assessed to serve as benchmarks. The results reveal that the combination of clustering algorithms with the PCA method may lead to loss of information while the nonlinear method (UMAP) can extract more informative features. The efficacy of the proposed framework is assessed across the Contiguous United States (CONUS) by training a single Base Model using long short‐term memory (LSTM) for the centroids of all clusters and then, fine‐tuning the model on the centroids of each cluster separately to create a regional model. The results indicate that using the information extracted by the UMAP‐GNG method to guide a Base Model can significantly improve the accuracy in most of the clusters and enhance the median prediction accuracy within different clusters from 0.04 to 0.37 of KGE in ungauged basins. 

   more » « less