More Like this

1. Deep Descriptive Clustering

   Zhang, H; Davidson, I (August 2021, IJCAI)

   null (Ed.)

   Recent work on explainable clustering allows describing clusters when the features are interpretable. However, much modern machine learning focuses on complex data such as images, text, and graphs where deep learning is used but the raw features of data are not interpretable. This paper explores a novel setting for performing clustering on complex data while simultaneously generating explanations using interpretable tags. We propose deep descriptive clustering that performs sub-symbolic representation learning on complex data while generating explanations based on symbolic data. We form good clusters by maximizing the mutual information between empirical distribution on the inputs and the induced clustering labels for clustering objectives. We generate explanations by solving an integer linear programming that generates concise and orthogonal descriptions for each cluster. Finally, we allow the explanation to inform better clustering by proposing a novel pairwise loss with self-generated constraints to maximize the clustering and explanation module's consistency. Experimental results on public data demonstrate that our model outperforms competitive baselines in clustering performance while offering high-quality cluster-level explanations. 

   more » « less
2. Summarizing the solution space in tumor phylogeny inference by multiple consensus trees

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

   Aguse, Nuraini; Qi, Yuanyuan; El-Kebir, Mohammed (July 2019, Bioinformatics)

   Abstract MotivationCancer phylogenies are key to studying tumorigenesis and have clinical implications. Due to the heterogeneous nature of cancer and limitations in current sequencing technology, current cancer phylogeny inference methods identify a large solution space of plausible phylogenies. To facilitate further downstream analyses, methods that accurately summarize such a set T of cancer phylogenies are imperative. However, current summary methods are limited to a single consensus tree or graph and may miss important topological features that are present in different subsets of candidate trees. ResultsWe introduce the Multiple Consensus Tree (MCT) problem to simultaneously cluster T and infer a consensus tree for each cluster. We show that MCT is NP-hard, and present an exact algorithm based on mixed integer linear programming (MILP). In addition, we introduce a heuristic algorithm that efficiently identifies high-quality consensus trees, recovering all optimal solutions identified by the MILP in simulated data at a fraction of the time. We demonstrate the applicability of our methods on both simulated and real data, showing that our approach selects the number of clusters depending on the complexity of the solution space T. Availability and implementationhttps://github.com/elkebir-group/MCT. Supplementary informationSupplementary data are available at Bioinformatics online. 

   more » « less
3. Scalable Optimal Power Management for Large-Scale Battery Energy Storage Systems

   https://doi.org/10.1109/TTE.2023.3331243  

   Farakhor, Amir; Wu, Di; Wang, Yebin; Fang, Huazhen (September 2024, IEEE Transactions on Transportation Electrification)

   Large-scale battery energy storage systems (BESS) play a pivotal role in advancing sustainability through their widespread applications in electrified transportation, power grids, and renewable energy systems. However, achieving optimal power management for these systems poses significant computational challenges. To address this, we propose a scalable approach that partitions the cells of a large-scale BESS into clusters based on state-of-charge (SoC), temperature, and internal resistance. Each cluster is represented by a model that approximates its collective SoC and temperature dynamics and overall power losses during charging and discharging. Using these clusters, we formulate a receding-horizon optimal power control problem to minimize power losses while promoting SoC and temperature balancing. The optimization determines a power quota for each cluster, which is then distributed among its constituent cells. This clustering approach drastically reduces computational costs by working with a smaller number of clusters instead of individual cells, enabling scalability for large-scale BESS. Simulations show a computational overhead reduction of over 60% for small-scale and 98% for large-scale BESS compared to conventional cell-level optimization. Experimental validation using a 20-cell prototype further underscores the approach's effectiveness and practical utility. 

   more » « less
4. SemCluster: Clustering of Imperative Programming Assignments based on Quantitative Semantic Features

   https://doi.org/10.1145/3314221.3314629  

   Perry, David M.; Kim, Dohyeong; Samanta, Roopsha; Zhang, Xiangyu (June 2019, Programming Language Design and Implementation)

   A fundamental challenge in automated reasoning about programming assignments at scale is clustering student submissions based on their underlying algorithms. State-of-the-art clustering techniques are sensitive to control structure variations, cannot cluster buggy solutions with similar correct solutions, and either require expensive pair-wise program analyses or training efforts. We propose a novel technique that can cluster small imperative programs based on their algorithmic essence: (A) how the input space is partitioned into equivalence classes and (B) how the problem is uniquely addressed within individual equivalence classes. We capture these algorithmic aspects as two quantitative semantic program features that are merged into a program's vector representation. Programs are then clustered using their vector representations. The computation of our first semantic feature leverages model counting to identify the number of inputs belonging to an input equivalence class. The computation of our second semantic feature abstracts the program's data flow by tracking the number of occurrences of a unique pair of consecutive values of a variable during its lifetime. The comprehensive evaluation of our tool SemCluster on benchmarks drawn from solutions to small programming assignments shows that SemCluster (1) generates far fewer clusters than other clustering techniques, (2) precisely identifies distinct solution strategies, and (3) boosts the performance of clustering-based program repair, all within a reasonable amount of time. 

   more » « less
5. Multi-view clustering by CPS-merge analysis with application to multimodal single-cell data

   https://doi.org/10.1371/journal.pcbi.1011044  

   Zhang, Lixiang; Lin, Lin; Li, Jia (April 2023, PLOS Computational Biology)

   Alber, Mark (Ed.)

   Multi-view data can be generated from diverse sources, by different technologies, and in multiple modalities. In various fields, integrating information from multi-view data has pushed the frontier of discovery. In this paper, we develop a new approach for multi-view clustering, which overcomes the limitations of existing methods such as the need of pooling data across views, restrictions on the clustering algorithms allowed within each view, and the disregard for complementary information between views. Our new method, called CPS-merge analysis , merges clusters formed by the Cartesian product of single-view cluster labels, guided by the principle of maximizing clustering stability as evaluated by CPS analysis. In addition, we introduce measures to quantify the contribution of each view to the formation of any cluster. CPS-merge analysis can be easily incorporated into an existing clustering pipeline because it only requires single-view cluster labels instead of the original data. We can thus readily apply advanced single-view clustering algorithms. Importantly, our approach accounts for both consensus and complementary effects between different views, whereas existing ensemble methods focus on finding a consensus for multiple clustering results, implying that results from different views are variations of one clustering structure. Through experiments on single-cell datasets, we demonstrate that our approach frequently outperforms other state-of-the-art methods. 

   more » « less