Information-based clustering.
Ontology highlight
ABSTRACT:
SUBMITTER: Slonim N
PROVIDER: S-EPMC1317937 | biostudies-literature | 2005 Dec
REPOSITORIES: biostudies-literature
Publications
Information-based clustering.
Slonim Noam N Atwal Gurinder Singh GS Tkacik Gasper G Bialek William W
Proceedings of the National Academy of Sciences of the United States of America 20051213 51
In an age of increasingly large data sets, investigators in many different disciplines have turned to clustering as a tool for data analysis and exploration. Existing clustering methods, however, typically depend on several nontrivial assumptions about the structure of data. Here, we reformulate the clustering problem from an information theoretic perspective that avoids many of these assumptions. In particular, our formulation obviates the need for defining a cluster "prototype," does not requi ...[more]
Similar Datasets
Project description:Min-cut clustering, based on minimizing one of two heuristic cost functions proposed by Shi and Malik nearly a decade ago, has spawned tremendous research, both analytic and algorithmic, in the graph partitioning and image segmentation communities over the last decade. It is, however, unclear if these heuristics can be derived from a more general principle, facilitating generalization to new problem settings. Motivated by an existing graph partitioning framework, we derive relationships between optimizing relevance information, as defined in the Information Bottleneck method, and the regularized cut in a K-partitioned graph. For fast-mixing graphs, we show that the cost functions introduced by Shi and Malik can be well approximated as the rate of loss of predictive information about the location of random walkers on the graph. For graphs drawn from a generative model designed to describe community structure, the optimal information-theoretic partition and the optimal min-cut partition are shown to be the same with high probability.
| S-EPMC3603148 | biostudies-literature
Project description:Pancreatic cancer is one of the most adverse diseases and it is very difficult to treat because the cancer cells formed in the pancreas intertwine themselves with nearby blood vessels and connective tissue. Hence, the surgical procedure of treatment becomes complicated and it does not always lead to a cure. Histopathological diagnosis is the usual approach for cancer diagnosis. However, the pancreas remains so deep inside the body that experts sometimes struggle to detect cancer in it. Computer-aided diagnosis can come to the aid of pathologists in this scenario. It assists experts by supporting their diagnostic decisions. In this research, we carried out a deep learning-based approach to analyze histopathology images. We collected whole-slide images of KPC mice to implement this work. The pancreatic abnormalities observed in KPC mice develop similar histological features to human beings. We created random patches from whole-slide images. Then, a convolutional autoencoder framework was used to embed these patches into an integrated latent space. We applied 'information maximization', a deep learning clustering technique to cluster the identical patches in an unsupervised manner since our dataset does not have annotation. Moreover, Uniform manifold approximation and projection, a nonlinear dimension reduction technique was utilized to visualize the embedded patches in a 2-dimensional space. Finally, we calculated a few internal cluster validation metrics to determine the optimal cluster set. Our work concentrated on patch-based anomaly detection in the whole slide histopathology images of KPC mice.
| S-EPMC10707605 | biostudies-literature
Project description:MotivationMany real applications such as businesses and health generate large categorical datasets with uncertainty. A fundamental task is to efficiently discover hidden and non-trivial patterns from such large uncertain categorical datasets. Since the exact value of an attribute is often unknown in uncertain categorical datasets, conventional clustering analysis algorithms do not provide a suitable means for dealing with categorical data, uncertainty, and stability.Problem statementThe ability of decision making in the presence of vagueness and uncertainty in data can be handled using Rough Set Theory. Though, recent categorical clustering techniques based on Rough Set Theory help but they suffer from low accuracy, high computational complexity, and generalizability especially on data sets where they sometimes fail or hardly select their best clustering attribute.ObjectivesThe main objective of this research is to propose a new information theoretic based Rough Purity Approach (RPA). Another objective of this work is to handle the problems of traditional Rough Set Theory based categorical clustering techniques. Hence, the ultimate goal is to cluster uncertain categorical datasets efficiently in terms of the performance, generalizability and computational complexity.MethodsThe RPA takes into consideration information-theoretic attribute purity of the categorical-valued information systems. Several extensive experiments are conducted to evaluate the efficiency of RPA using a real Supplier Base Management (SBM) and six benchmark UCI datasets. The proposed RPA is also compared with several recent categorical data clustering techniques.ResultsThe experimental results show that RPA outperforms the baseline algorithms. The significant percentage improvement with respect to time (66.70%), iterations (83.13%), purity (10.53%), entropy (14%), and accuracy (12.15%) as well as Rough Accuracy of clusters show that RPA is suitable for practical usage.ConclusionWe conclude that as compared to other techniques, the attribute purity of categorical-valued information systems can better cluster the data. Hence, RPA technique can be recommended for large scale clustering in multiple domains and its performance can be enhanced for further research.
| S-EPMC9106167 | biostudies-literature
Project description:Identifying single nucleotide polymorphism (SNP) interactions is considered as a popular and crucial way for explaining the missing heritability of complex diseases in genome-wide association studies (GWAS). Many approaches have been proposed to detect SNP interactions. However, existing approaches generally suffer from the high computational complexity resulting from the explosion of candidate high-order interactions. In this paper, we propose a two-stage approach (called ClusterMI) to detect high-order genome-wide SNP interactions based on significant pairwise SNP combinations. In the screening stage, to alleviate the huge computational burden, ClusterMI firstly applies a clustering algorithm combined with mutual information to divide SNPs into different clusters. Then, ClusterMI utilizes conditional mutual information to screen significant pairwise SNP combinations in each cluster. In this way, there is a higher probability of identifying significant two-locus combinations in each group, and the computational load for the follow-up search can be greatly reduced. In the search stage, two different search strategies (exhaustive search and improved ant colony optimization search) are provided to detect high-order SNP interactions based on the cardinality of significant two-locus combinations. Extensive simulation experiments show that ClusterMI has better performance than other related and competitive approaches. Experiments on two real case-control datasets from Wellcome Trust Case Control Consortium (WTCCC) also demonstrate that ClusterMI is more capable of identifying high-order SNP interactions from genome-wide data.
| S-EPMC6121365 | biostudies-literature
Project description:The purposes are to evaluate the Distributed Clustering Algorithm (DCA) applicability in the power system's big data processing and find the information economic dispatch strategy suitable for new energy consumption in power systems. A two-layer DCA algorithm is proposed based on K-Means Clustering (KMC) and Affinity Propagation (AP) clustering algorithms. Then the incentive Demand Response (DR) is introduced, and the DR flexibility of the user side is analyzed. Finally, the day-ahead dispatch and real-time dispatch schemes are combined, and a multi-period information economic dispatch model is constructed. The algorithm performance is analyzed according to case analyses of new energy consumption. Results demonstrate that the two-layer DCA's calculation time is 5.23s only, the number of iterations is small, and the classification accuracy rate reaches 0.991. Case 2 corresponding to the proposed model can consume the new energy, and the income of the aggregator can be maximized. In short, the multi-period information economic dispatch model can consume the new energy and meet the DR of the user side.
| S-EPMC7951923 | biostudies-literature
Project description:Cluster analysis is one of the most popular data analysis tools in a wide range of applied disciplines. We propose and justify a computationally efficient and straightforward-to-implement way of imposing the available information from networks/graphs (a priori available in many application areas) on a broad family of clustering methods. The introduced approach is illustrated on the problem of a noninvasive unsupervised brain signal classification. This task is faced with several challenging difficulties such as nonstationary noisy signals and a small sample size, combined with a high-dimensional feature space and huge noise-to-signal ratios. Applying this approach results in an exact unsupervised classification of very short signals, opening new possibilities for clustering methods in the area of a noninvasive brain-computer interface.
| S-EPMC4643807 | biostudies-literature
Project description:BackgroundTime-course microarray experiments produce vector gene expression profiles across a series of time points. Clustering genes based on these profiles is important in discovering functional related and co-regulated genes. Early developed clustering algorithms do not take advantage of the ordering in a time-course study, explicit use of which should allow more sensitive detection of genes that display a consistent pattern over time. Peddada et al. 1 proposed a clustering algorithm that can incorporate the temporal ordering using order-restricted statistical inference. This algorithm is, however, very time-consuming and hence inapplicable to most microarray experiments that contain a large number of genes. Its computational burden also imposes difficulty to assess the clustering reliability, which is a very important measure when clustering noisy microarray data.ResultsWe propose a computationally efficient information criterion-based clustering algorithm, called ORICC, that also takes account of the ordering in time-course microarray experiments by embedding the order-restricted inference into a model selection framework. Genes are assigned to the profile which they best match determined by a newly proposed information criterion for order-restricted inference. In addition, we also developed a bootstrap procedure to assess ORICC's clustering reliability for every gene. Simulation studies show that the ORICC method is robust, always gives better clustering accuracy than Peddada's method and saves hundreds of times computational time. Under some scenarios, its accuracy is also better than some other existing clustering methods for short time-course microarray data, such as STEM 2 and Wang et al. 3. It is also computationally much faster than Wang et al. 3.ConclusionOur ORICC algorithm, which takes advantage of the temporal ordering in time-course microarray experiments, provides good clustering accuracy and is meanwhile much faster than Peddada's method. Moreover, the clustering reliability for each gene can also be assessed, which is unavailable in Peddada's method. In a real data example, the ORICC algorithm identifies new and interesting genes that previous analyses failed to reveal.
| S-EPMC2696449 | biostudies-literature
Project description:MotivationHeterogeneity in human diseases presents clinical challenges in accurate disease characterization and treatment. Recently available high throughput multi-omics data may offer a great opportunity to explore the underlying mechanisms of diseases and improve disease heterogeneity assessment throughout the treatment course. In addition, increasingly accumulated data from existing literature may be informative about disease subtyping. However, the existing clustering procedures, such as Sparse Convex Clustering (SCC), cannot directly utilize the prior information even though SCC produces stable clusters.ResultsWe develop a clustering procedure, information-incorporated Sparse Convex Clustering, to respond to the need for disease subtyping in precision medicine. Utilizing the text mining approach, the proposed method leverages the existing information from previously published studies through a group lasso penalty to improve disease subtyping and biomarker identification. The proposed method allows taking heterogeneous information, such as multi-omics data. We conduct simulation studies under several scenarios with various accuracy of the prior information to evaluate the performance of our method. The proposed method outperforms other clustering methods, such as SCC, K-means, Sparse K-means, iCluster+, and Bayesian Consensus Clustering. In addition, the proposed method generates more accurate disease subtypes and identifies important biomarkers for future studies in real data analysis of breast and lung cancer-related omics data. In conclusion, we present an information-incorporated clustering procedure that allows coherent pattern discovery and feature selection.Availability and implementationThe code is available upon request.
| S-EPMC10329496 | biostudies-literature
Project description:BackgroundA pharmacophore model consists of a group of chemical features arranged in three-dimensional space that can be used to represent the biological activities of the described molecules. Clustering of molecular interactions of ligands on the basis of their pharmacophore similarity provides an approach for investigating how diverse ligands can bind to a specific receptor site or different receptor sites with similar or dissimilar binding affinities. However, efficient clustering of pharmacophore models in three-dimensional space is currently a challenge.ResultsWe have developed a pharmacophore-assisted Iterative Closest Point (ICP) method that is able to group pharmacophores in a manner relevant to their biochemical properties, such as binding specificity etc. The implementation of the method takes pharmacophore files as input and produces distance matrices. The method integrates both alignment-dependent and alignment-independent concepts.ConclusionsWe apply our three-dimensional pharmacophore clustering method to two sets of experimental data, including 31 globulin-binding steroids and 4 groups of selected antibody-antigen complexes. Results are translated from distance matrices to Newick format and visualised using dendrograms. For the steroid dataset, the resulting classification of ligands shows good correspondence with existing classifications. For the antigen-antibody datasets, the classification of antigens reflects both antigen type and binding antibody. Overall the method runs quickly and accurately for classifying the data based on their binding affinities or antigens.
| S-EPMC4290656 | biostudies-literature
Project description:BACKGROUND: Genetic polymorphisms in the gene encoding the ?-adrenergic receptors (?-AR) have a pivotal role in the functions of the autonomic nervous system. Using heart rate variability (HRV) as an indicator of autonomic function, we present a bottom-up genotype-phenotype analysis to investigate the association between ?-AR gene polymorphisms and heart rate dynamics. METHODS: A total of 221 healthy Han Chinese adults (59 males and 162 females, aged 33.6 ± 10.8 years, range 19 to 63 years) were recruited and genotyped for three common ?-AR polymorphisms: ?(1)-AR Ser49Gly, ?(2)-AR Arg16Gly and ?(2)-AR Gln27Glu. Each subject underwent two hours of electrocardiogram monitoring at rest. We applied an information-based similarity (IBS) index to measure the pairwise dissimilarity of heart rate dynamics among study subjects. RESULTS: With the aid of agglomerative hierarchical cluster analysis, we categorized subjects into major clusters, which were found to have significantly different distributions of ?(2)-AR Arg16Gly genotype. Furthermore, the non-randomness index, a nonlinear HRV measure derived from the IBS method, was significantly lower in Arg16 homozygotes than in Gly16 carriers. The non-randomness index was negatively correlated with parasympathetic-related HRV variables and positively correlated with those HRV indices reflecting a sympathovagal shift toward sympathetic activity. CONCLUSIONS: We demonstrate a bottom-up categorization approach combining the IBS method and hierarchical cluster analysis to detect subgroups of subjects with HRV phenotypes associated with ?-AR polymorphisms. Our results provide evidence that ?(2)-AR polymorphisms are significantly associated with the acceleration/deceleration pattern of heart rate oscillation, reflecting the underlying mode of autonomic nervous system control.
| S-EPMC3087751 | biostudies-literature