book

Data Clustering

Name: Data Clustering
ISBN: 9781466558229

by Charu C. Aggarwal, Chandan K. Reddy

August 2013

Intermediate to advanced

652 pages

26h 7m

English

Chapman and Hall/CRC

Read now

Unlock full access

Cover
Preliminaries
Preface
Editor Biographies
Contributors
Chapter 1 An Introduction to Cluster Analysis
1.1 Introduction1.2 Common Techniques Used in Cluster Analysis1.2.1 Feature Selection Methods1.2.2 Probabilistic and Generative Models1.2.3 Distance-Based Algorithms1.2.4 Density- and Grid-Based Methods1.2.5 Leveraging Dimensionality Reduction Methods1.2.5.1 Generative Models for Dimensionality Reduction1.2.5.2 Matrix Factorization and Co-Clustering1.2.5.3 Spectral Methods1.2.6 The High Dimensional Scenario1.2.7 Scalable Techniques for Cluster Analysis1.2.7.1 I/O Issues in Database Management1.2.7.2 Streaming Algorithms1.2.7.3 The Big Data Framework1.3 Data Types Studied in Cluster Analysis1.3.1 Clustering Categorical Data1.3.2 Clustering Text Data1.3.3 Clustering Multimedia Data1.3.4 Clustering Time-Series Data1.3.5 Clustering Discrete Sequences1.3.6 Clustering Network Data1.3.7 Clustering Uncertain Data1.4 Insights Gained from Different Variations of Cluster Analysis1.4.1 Visual Insights1.4.2 Supervised Insights1.4.3 Multiview and Ensemble-Based Insights1.4.4 Validation-Based Insights1.5 Discussion and ConclusionsBibliography
Chapter 2 Feature Selection for Clustering: A Review
2.1 Introduction2.1.1 Data Clustering2.1.2 Feature Selection2.1.3 Feature Selection for Clustering2.1.3.1 Filter Model2.1.3.2 Wrapper Model2.1.3.3 Hybrid Model2.2 Feature Selection for Clustering2.2.1 Algorithms for Generic Data2.2.1.1 Spectral Feature Selection (SPEC)2.2.1.2 Laplacian Score (LS)2.2.1.3 Feature Selection for Sparse Clustering2.2.1.4 Localized Feature Selection Based on Scatter Separability (LFSBSS)2.2.1.5 Multicluster Feature Selection (MCFS)2.2.1.6 Feature Weighting k-Means2.2.2 Algorithms for Text Data2.2.2.1 Term Frequency (TF)2.2.2.2 Inverse Document Frequency (IDF)2.2.2.3 Term Frequency-Inverse Document Frequency (TF-IDF)2.2.2.4 Chi Square Statistic2.2.2.5 Frequent Term-Based Text Clustering2.2.2.6 Frequent Term Sequence2.2.3 Algorithms for Streaming Data2.2.3.1 Text Stream Clustering Based on Adaptive Feature Selection (TSC-AFS)2.2.3.2 High-Dimensional Projected Stream Clustering (HPStream)2.2.4 Algorithms for Linked Data2.2.4.1 Challenges and Opportunities2.2.4.2 LUFS: An Unsupervised Feature Selection Framework for Linked Data2.2.4.3 Conclusion and Future Work for Linked Data2.3 Discussions and Challenges2.3.1 The Chicken or the Egg Dilemma2.3.2 Model Selection: K and l2.3.3 Scalability2.3.4 StabilityBibliographyFigure 2.1Figure 2.2Figure 2.3Figure 2.4Table 2.1
Chapter 3 Probabilistic Models for Clustering
3.1 Introduction3.2 Mixture Models3.2.1 Overview3.2.2 Gaussian Mixture Model3.2.3 Bernoulli Mixture Model3.2.4 Model Selection Criteria3.3 EM Algorithm and Its Variations3.3.1 The General EM Algorithm3.3.2 Mixture Models Revisited3.3.3 Limitations of the EM Algorithm3.3.4 Applications of the EM Algorithm3.4 Probabilistic Topic Models3.4.1 Probabilistic Latent Semantic Analysis3.4.2 Latent Dirichlet Allocation3.4.3 Variations and Extensions3.5 Conclusions and SummaryBibliographyFigure 3.1Figure 3.2Figure 3.3Figure 3.4Figure 3.5Figure 3.6Figure 3.7
Chapter 4 A Survey of Partitional and Hierarchical Clustering Algorithms
4.1 Introduction4.2 Partitional Clustering Algorithms4.2.1 K-Means Clustering4.2.2 Minimization of Sum of Squared Errors4.2.3 Factors Affecting K-Means4.2.3.1 Popular Initialization Methods4.2.3.2 Estimating the Number of Clusters4.2.4 Variations of K-Means4.2.4.1 K-Medoids Clustering4.2.4.2 K-Medians Clustering4.2.4.3 K-Modes Clustering4.2.4.4 Fuzzy K-Means Clustering4.2.4.5 X-Means Clustering4.2.4.6 Intelligent K-Means Clustering4.2.4.7 Bisecting K-Means Clustering4.2.4.8 Kernel K-Means Clustering4.2.4.9 Mean Shift Clustering4.2.4.10 Weighted K-Means Clustering4.2.4.11 Genetic K-Means Clustering4.2.5 Making K-Means Faster4.3 Hierarchical Clustering Algorithms4.3.1 Agglomerative Clustering4.3.1.1 Single and Complete Link4.3.1.2 Group Averaged and Centroid Agglomerative Clustering4.3.1.3 Ward’s Criterion4.3.1.4 Agglomerative Hierarchical Clustering Algorithm4.3.1.5 Lance–Williams Dissimilarity Update Formula4.3.2 Divisive Clustering4.3.2.1 Issues in Divisive Clustering4.3.2.2 Divisive Hierarchical Clustering Algorithm4.3.2.3 Minimum Spanning Tree-Based Clustering4.3.3 Other Hierarchical Clustering Algorithms4.4 Discussion and SummaryBibliographyFigure 4.1Figure 4.2Table 4.1
Chapter 5 Density-Based Clustering
5.1 Introduction5.2 DBSCAN5.3 DENCLUE5.4 OPTICS5.5 Other Algorithms5.6 Subspace Clustering5.7 Clustering Networks5.8 Other Directions5.9 ConclusionBibliographyFigure 5.1Figure 5.2Figure 5.3Figure 5.4Figure 5.5Figure 5.6

Chapter 6 Grid-Based Clustering
6.1 Introduction6.2 The Classical Algorithms6.2.1 Earliest Approaches: GRIDCLUS and BANG6.2.2 STING and STING+: The Statistical Information Grid Approach6.2.3 WaveCluster: Wavelets in Grid-Based Clustering6.3 Adaptive Grid-Based Algorithms6.3.1 AMR: Adaptive Mesh Refinement Clustering6.4 Axis-Shifting Grid-Based Algorithms6.4.1 NSGC: New Shifting Grid Clustering Algorithm6.4.2 ADCC: Adaptable Deflect and Conquer Clustering6.4.3 ASGC: Axis-Shifted Grid-Clustering6.4.4 GDILC: Grid-Based Density-IsoLine Clustering Algorithm6.5 High-Dimensional Algorithms6.5.1 CLIQUE: The Classical High-Dimensional Algorithm6.5.2 Variants of CLIQUE6.5.2.1 ENCLUS: Entropy-Based Approach6.5.2.2 MAFIA: Adaptive Grids in High Dimensions6.5.3 OptiGrid: Density-Based Optimal Grid Partitioning6.5.4 Variants of the OptiGrid Approach6.5.4.1 O-Cluster: A Scalable Approach6.5.4.2 CBF: Cell-Based Filtering6.6 Conclusions and SummaryBibliographyFigure 6.1Figure 6.2Figure 6.3Table 6.1Table 6.2Table 6.3Table 6.4
Chapter 7 Nonnegative Matrix Factorizations for Clustering: A Survey
7.1 Introduction7.1.1 Background7.1.2 NMF Formulations7.2 NMF for Clustering: Theoretical Foundations7.2.1 NMF and K-Means Clustering7.2.2 NMF and Probabilistic Latent Semantic Indexing7.2.3 NMF and Kernel K-Means and Spectral Clustering7.2.4 NMF Boundedness Theorem7.3 NMF Clustering Capabilities7.3.1 Examples7.3.2 Analysis7.4 NMF Algorithms7.4.1 Introduction7.4.2 Algorithm Development7.4.3 Practical Issues in NMF Algorithms7.4.3.1 Initialization7.4.3.2 Stopping Criteria7.4.3.3 Objective Function vs. Clustering Performance7.4.3.4 Scalability7.5 NMF Related Factorizations7.6 NMF for Clustering: Extensions7.6.1 Co-Clustering7.6.2 Semisupervised Clustering7.6.3 Semisupervised Co-Clustering7.6.4 Consensus Clustering7.6.5 Graph Clustering7.6.6 Other Clustering Extensions7.7 ConclusionsAcknowledgmentBibliographyFigure 7.1Figure 7.2Figure 7.3
Chapter 8 Spectral Clustering
8.1 Introduction8.2 Similarity Graph8.3 Unnormalized Spectral Clustering8.3.1 Notation8.3.2 Unnormalized Graph Laplacian8.3.3 Spectrum Analysis8.3.4 Unnormalized Spectral Clustering Algorithm8.4 Normalized Spectral Clustering8.4.1 Normalized Graph Laplacian8.4.2 Spectrum Analysis8.4.3 Normalized Spectral Clustering Algorithm8.5 Graph Cut View8.5.1 Ratio Cut Relaxation8.5.2 Normalized Cut Relaxation8.6 Random Walks View8.7 Connection to Laplacian Eigenmap8.8 Connection to Kernel k-Means and Nonnegative Matrix Factorization8.9 Large Scale Spectral Clustering8.10 Further ReadingBibliographyFigure 8.1Figure 8.2Figure 8.3
Chapter 9 Clustering High-Dimensional Data
9.1 Introduction9.2 The “Curse of Dimensionality”9.2.1 Different Aspects of the “Curse”9.2.2 Consequences9.3 Clustering Tasks in Subspaces of High-Dimensional Data9.3.1 Categories of Subspaces9.3.1.1 Axis-Parallel Subspaces9.3.1.2 Arbitrarily Oriented Subspaces9.3.1.3 Special Cases9.3.2 Search Spaces for the Clustering Problem9.4 Fundamental Algorithmic Ideas9.4.1 Clustering in Axis-Parallel Subspaces9.4.1.1 Cluster Model9.4.1.2 Basic Techniques9.4.1.3 Clustering Algorithms9.4.2 Clustering in Arbitrarily Oriented Subspaces9.4.2.1 Cluster Model9.4.2.2 Basic Techniques and Example Algorithms9.5 Open Questions and Current Research Directions9.6 ConclusionBibliography
Chapter 10 A Survey of Stream Clustering Algorithms
10.1 Introduction10.2 Methods Based on Partitioning Representatives10.2.1 The STREAM Algorithm10.2.2 CluStream: The Microclustering Framework10.2.2.1 Microcluster Definition10.2.2.2 Pyramidal Time Frame10.2.2.3 Online Clustering with CluStream10.3 Density-Based Stream Clustering10.3.1 DenStream: Density-Based Microclustering10.3.2 Grid-Based Streaming Algorithms10.3.2.1 D-Stream Algorithm10.3.2.2 Other Grid-Based Algorithms10.4 Probabilistic Streaming Algorithms10.5 Clustering High-Dimensional Streams10.5.1 The HPSTREAM Method10.5.2 Other High-Dimensional Streaming Algorithms10.6 Clustering Discrete and Categorical Streams10.6.1 Clustering Binary Data Streams with k-Means10.6.2 The StreamCluCD Algorithm10.6.3 Massive-Domain Clustering10.7 Text Stream Clustering10.8 Other Scenarios for Stream Clustering10.8.1 Clustering Uncertain Data Streams10.8.2 Clustering Graph Streams10.8.3 Distributed Clustering of Data Streams10.9 Discussion and ConclusionsBibliographyFigure 10.1Table 10.1
Chapter 11 Big Data Clustering
11.1 Introduction11.2 One-Pass Clustering Algorithms11.2.1 CLARANS: Fighting with Exponential Search Space11.2.2 BIRCH: Fighting with Limited Memory11.2.3 CURE: Fighting with the Irregular Clusters11.3 Randomized Techniques for Clustering Algorithms11.3.1 Locality-Preserving Projection11.3.2 Global Projection11.4 Parallel and Distributed Clustering Algorithms11.4.1 General Framework11.4.2 DBDC: Density-Based Clustering11.4.3 ParMETIS: Graph Partitioning11.4.4 PKMeans: K-Means with MapReduce11.4.5 DisCo: Co-Clustering with MapReduce11.4.6 BoW: Subspace Clustering with MapReduce11.5 ConclusionBibliographyFigure 11.1Figure 11.2Figure 11.3Figure 11.4Figure 11.5Figure 11.6Figure 11.7Figure 11.8Figure 11.9Figure 11.10
Chapter 12 Clustering Categorical Data
12.1 Introduction12.2 Goals of Categorical Clustering12.2.1 Clustering Road Map12.3 Similarity Measures for Categorical Data12.3.1 The Hamming Distance in Categorical and Binary Data12.3.2 Probabilistic Measures12.3.3 Information-Theoretic Measures12.3.4 Context-Based Similarity Measures12.4 Descriptions of Algorithms12.4.1 Partition-Based Clustering12.4.1.1 k-Modes12.4.1.2 k-Prototypes (Mixed Categorical and Numerical)12.4.1.3 Fuzzy k-Modes12.4.1.4 Squeezer12.4.1.5 COOLCAT12.4.2 Hierarchical Clustering12.4.2.1 ROCK12.4.2.2 COBWEB12.4.2.3 LIMBO12.4.3 Density-Based Clustering12.4.3.1 Projected (Subspace) Clustering12.4.3.2 CACTUS12.4.3.3 CLICKS12.4.3.4 STIRR12.4.3.5 CLOPE12.4.3.6 HIERDENC: Hierarchical Density-Based Clustering12.4.3.7 MULIC: Multiple Layer Incremental Clustering12.4.4 Model-Based Clustering12.4.4.1 BILCOM Empirical Bayesian (Mixed Categorical and Numerical)12.4.4.2 AutoClass (Mixed Categorical and Numerical)12.4.4.3 SVM Clustering (Mixed Categorical and Numerical)12.5 ConclusionBibliographyFigure 12.1Figure 12.2Figure 12.3Figure 12.4Figure 12.5Figure 12.6Figure 12.7Figure 12.8Figure 12.9Table 12.1Table 12.2
Chapter 13 Document Clustering: The Next Frontier
13.1 Introduction13.2 Modeling a Document13.2.1 Preliminaries13.2.2 The Vector Space Model13.2.3 Alternate Document Models13.2.4 Dimensionality Reduction for Text13.2.5 Characterizing Extremes13.3 General Purpose Document Clustering13.3.1 Similarity/Dissimilarity-Based Algorithms13.3.2 Density-Based Algorithms13.3.3 Adjacency-Based Algorithms13.3.4 Generative Algorithms13.4 Clustering Long Documents13.4.1 Document Segmentation13.4.2 Clustering Segmented Documents13.4.3 Simultaneous Segment Identification and Clustering13.5 Clustering Short Documents13.5.1 General Methods for Short Document Clustering13.5.2 Clustering with Knowledge Infusion13.5.3 Clustering Web Snippets13.5.4 Clustering Microblogs13.6 ConclusionBibliographyFigure 13.1Figure 13.2Figure 13.3Figure 13.4Figure 13.5Figure 13.6Figure 13.7Table 13.1Table 13.2
Chapter 14 Clustering Multimedia Data
14.1 Introduction14.2 Clustering with Image Data14.2.1 Visual Words Learning14.2.2 Face Clustering and Annotation14.2.3 Photo Album Event Recognition14.2.4 Image Segmentation14.2.5 Large-Scale Image Classification14.3 Clustering with Video and Audio Data14.3.1 Video Summarization14.3.2 Video Event Detection14.3.3 Video Story Clustering14.3.4 Music Summarization14.4 Clustering with Multimodal Data14.5 Summary and Future DirectionsBibliography
Chapter 15 Time-Series Data Clustering
15.1 Introduction15.2 The Diverse Formulations for Time-Series Clustering15.3 Online Correlation-Based Clustering15.3.1 Selective Muscles and Related Methods15.3.2 Sensor Selection Algorithms for Correlation Clustering15.4 Similarity and Distance Measures15.4.1 Univariate Distance Measures15.4.1.1 Lp Distance15.4.1.2 Dynamic Time Warping Distance15.4.1.3 EDIT Distance15.4.1.4 Longest Common Subsequence15.4.2 Multivariate Distance Measures15.4.2.1 Multidimensional Lp Distance15.4.2.2 Multidimensional DTW15.4.2.3 Multidimensional LCSS15.4.2.4 Multidimensional Edit Distance15.4.2.5 Multidimensional Subsequence Matching15.5 Shape-Based Time-Series Clustering Techniques15.5.1 k-Means Clustering15.5.2 Hierarchical Clustering15.5.3 Density-Based Clustering15.5.4 Trajectory Clustering15.6 Time-Series Clustering Applications15.7 ConclusionsBibliographyFigure 15.1Figure 15.2Figure 15.3Figure 15.4Figure 15.5
Chapter 16 Clustering Biological Data
16.1 Introduction16.2 Clustering Microarray Data16.2.1 Proximity Measures16.2.2 Categorization of Algorithms16.2.3 Standard Clustering Algorithms16.2.3.1 Hierarchical Clustering16.2.3.2 Probabilistic Clustering16.2.3.3 Graph-Theoretic Clustering16.2.3.4 Self-Organizing Maps16.2.3.5 Other Clustering Methods16.2.4 Biclustering16.2.4.1 Types and Structures of Biclusters16.2.4.2 Biclustering Algorithms16.2.4.3 Recent Developments16.2.5 Triclustering16.2.6 Time-Series Gene Expression Data Clustering16.2.7 Cluster Validation16.3 Clustering Biological Networks16.3.1 Characteristics of PPI Network Data16.3.2 Network Clustering Algorithms16.3.2.1 Molecular Complex Detection16.3.2.2 Markov Clustering16.3.2.3 Neighborhood Search Methods16.3.2.4 Clique Percolation Method16.3.2.5 Ensemble Clustering16.3.2.6 Other Clustering Methods16.3.3 Cluster Validation and Challenges16.4 Biological Sequence Clustering16.4.1 Sequence Similarity Metrics16.4.1.1 Alignment-Based Similarity16.4.1.2 Keyword-Based Similarity16.4.1.3 Kernel-Based Similarity16.4.1.4 Model-Based Similarity16.4.2 Sequence Clustering Algorithms16.4.2.1 Subsequence-Based Clustering16.4.2.2 Graph-Based Clustering16.4.2.3 Probabilistic Models16.4.2.4 Suffix Tree and Suffix Array-Based Method16.5 Software Packages16.6 Discussion and SummaryBibliographyFigure 16.1Figure 16.2Figure 16.3Figure 16.4
Chapter 17 Network Clustering
17.1 Introduction17.2 Background and Nomenclature17.3 Problem Definition17.4 Common Evaluation Criteria17.5 Partitioning with Geometric Information17.5.1 Coordinate Bisection17.5.2 Inertial Bisection17.5.3 Geometric Partitioning17.6 Graph Growing and Greedy Algorithms17.6.1 Kernighan-Lin Algorithm17.7 Agglomerative and Divisive Clustering17.8 Spectral Clustering17.8.1 Similarity Graphs17.8.2 Types of Similarity Graphs17.8.3 Graph Laplacians17.8.3.1 Unnormalized Graph Laplacian17.8.3.2 Normalized Graph Laplacians17.8.4 Spectral Clustering Algorithms17.9 Markov Clustering17.9.1 Regularized MCL (RMCL): Improvement over MCL17.10 Multilevel Partitioning17.11 Local Partitioning Algorithms17.12 Hypergraph Partitioning17.13 Emerging Methods for Partitioning Special Graphs17.13.1 Bipartite Graphs17.13.2 Dynamic Graphs17.13.3 Heterogeneous Networks17.13.4 Directed Networks17.13.5 Combining Content and Relationship Information17.13.6 Networks with Overlapping Communities17.13.7 Probabilistic Methods17.14 ConclusionAcknowledgmentsBibliographyFigure 17.1Table 17.1
Chapter 18 A Survey of Uncertain Data Clustering Algorithms
18.1 Introduction18.2 Mixture Model Clustering of Uncertain Data18.3 Density-Based Clustering Algorithms18.3.1 FDBSCAN Algorithm18.3.2 FOPTICS Algorithm18.4 Partitional Clustering Algorithms18.4.1 The UK-Means Algorithm18.4.2 The CK-Means Algorithm18.4.3 Clustering Uncertain Data with Voronoi Diagrams18.4.4 Approximation Algorithms for Clustering Uncertain Data18.4.5 Speeding Up Distance Computations18.5 Clustering Uncertain Data Streams18.5.1 The UMicro Algorithm18.5.2 The LuMicro Algorithm18.5.3 Enhancements to Stream Clustering18.6 Clustering Uncertain Data in High Dimensionality18.6.1 Subspace Clustering of Uncertain Data18.6.2 UPStream: Projected Clustering of Uncertain Data Streams18.7 Clustering with the Possible Worlds Model18.8 Clustering Uncertain Graphs18.9 Conclusions and SummaryBibliographyFigure 18.1Figure 18.2Figure 18.3Figure 18.4
Chapter 19 Concepts of Visual and Interactive Clustering
19.1 Introduction19.2 Direct Visual and Interactive Clustering19.2.1 Scatterplots19.2.2 Parallel Coordinates19.2.3 Discussion19.3 Visual Interactive Steering of Clustering19.3.1 Visual Assessment of Convergence of Clustering Algorithm19.3.2 Interactive Hierarchical Clustering19.3.3 Visual Clustering with SOMs19.3.4 Discussion19.4 Interactive Comparison and Combination of Clusterings19.4.1 Space of Clusterings19.4.2 Visualization19.4.3 Discussion19.5 Visualization of Clusters for Sense-Making19.6 SummaryBibliographyFigure 19.1Figure 19.2Figure 19.3Figure 19.4Figure 19.5Figure 19.6Figure 19.7Figure 19.8
Chapter 20 Semisupervised Clustering
20.1 Introduction20.2 Clustering with Pointwise and Pairwise Semisupervision20.2.1 Semisupervised Clustering Based on Seeding20.2.2 Semisupervised Clustering Based on Pairwise Constraints20.2.3 Active Learning for Semisupervised Clustering20.2.4 Semisupervised Clustering Based on User Feedback20.2.5 Semisupervised Clustering Based on Nonnegative Matrix Factorization20.3 Semisupervised Graph Cuts20.3.1 Semisupervised Unnormalized Cut20.3.2 Semisupervised Ratio Cut20.3.3 Semisupervised Normalized Cut20.4 A Unified View of Label Propagation20.4.1 Generalized Label Propagation20.4.2 Gaussian Fields20.4.3 Tikhonov Regularization (TIKREG)20.4.4 Local and Global Consistency20.4.5 Related Methods20.4.5.1 Cluster Kernels20.4.5.2 Gaussian Random Walks EM (GWEM)20.4.5.3 Linear Neighborhood Propagation20.4.6 Label Propagation and Green’s Function20.4.7 Label Propagation and Semisupervised Graph Cuts20.5 Semisupervised Embedding20.5.1 Nonlinear Manifold Embedding20.5.2 Semisupervised Embedding20.5.2.1 Unconstrained Semisupervised Embedding20.5.2.2 Constrained Semisupervised Embedding20.6 Comparative Experimental Analysis20.6.1 Experimental Results20.6.2 Semisupervised Embedding Methods20.7 ConclusionsBibliographyFigure 20.1Figure 20.2Figure 20.3Figure 20.4Figure 20.5Table 20.1Table 20.2Table 20.3
Chapter 21 Alternative Clustering Analysis: A Review
21.1 Introduction21.2 Technical Preliminaries21.3 Multiple Clustering Analysis Using Alternative Clusterings21.3.1 Alternative Clustering Algorithms: A Taxonomy21.3.2 Unguided Generation21.3.2.1 Naive21.3.2.2 Meta Clustering21.3.2.3 Eigenvectors of the Laplacian Matrix21.3.2.4 Decorrelated k-Means and Convolutional EM21.3.2.5 CAMI21.3.3 Guided Generation with Constraints21.3.3.1 COALA21.3.3.2 Constrained Optimization Approach21.3.3.3 MAXIMUS21.3.4 Orthogonal Transformation Approaches21.3.4.1 Orthogonal Views21.3.4.2 ADFT21.3.5 Information Theoretic21.3.5.1 Conditional Information Bottleneck (CIB)21.3.5.2 Conditional Ensemble Clustering21.3.5.3 NACI21.3.5.4 mSC21.4 Connections to Multiview Clustering and Subspace Clustering21.5 Future Research Issues21.6 SummaryBibliography
Chapter 22 Cluster Ensembles: Theory and Applications
22.1 Introduction22.2 The Cluster Ensemble Problem22.3 Measuring Similarity Between Clustering Solutions22.4 Cluster Ensemble Algorithms22.4.1 Probabilistic Approaches to Cluster Ensembles22.4.1.1 A Mixture Model for Cluster Ensembles (MMCE)22.4.1.2 Bayesian Cluster Ensembles (BCE)22.4.1.3 Nonparametric Bayesian Cluster Ensembles (NPBCE)22.4.2 Pairwise Similarity-Based Approaches22.4.2.1 Methods Based on Ensemble Co-Association Matrix22.4.2.2 Relating Consensus Clustering to Other Optimization Formulations22.4.3 Direct Approaches Using Cluster Labels22.4.3.1 Graph Partitioning22.4.3.2 Cumulative Voting22.5 Applications of Consensus Clustering22.5.1 Gene Expression Data Analysis22.5.2 Image Segmentation22.6 Concluding RemarksBibliographyFigure 22.1Figure 22.2Figure 22.3Figure 22.4Figure 22.5Table 22.1
Chapter 23 Clustering Validation Measures
23.1 Introduction23.2 External Clustering Validation Measures23.2.1 An Overview of External Clustering Validation Measures23.2.2 Defective Validation Measures23.2.2.1 K-Means: The Uniform Effect23.2.2.2 A Necessary Selection Criterion23.2.2.3 The Cluster Validation Results23.2.2.4 The Issues with the Defective Measures23.2.2.5 Improving the Defective Measures23.2.3 Measure Normalization23.2.3.1 Normalizing the Measures23.2.3.2 The DCV Criterion23.2.3.3 The Effect of Normalization23.2.4 Measure Properties23.2.4.1 The Consistency Between Measures23.2.4.2 Properties of Measures23.2.4.3 Discussions23.3 Internal Clustering Validation Measures23.3.1 An Overview of Internal Clustering Validation Measures23.3.2 Understanding of Internal Clustering Validation Measures23.3.2.1 The Impact of Monotonicity23.3.2.2 The Impact of Noise23.3.2.3 The Impact of Density23.3.2.4 The Impact of Subclusters23.3.2.5 The Impact of Skewed Distributions23.3.2.6 The Impact of Arbitrary Shapes23.3.3 Properties of Measures23.4 SummaryBibliographyFigure 23.1Figure 23.2Figure 23.3Figure 23.4Figure 23.5Figure 23.6Figure 23.7Figure 23.8Figure 23.9Figure 23.10Figure 23.11Figure 23.12Figure 23.13Figure 23.14Figure 23.15Figure 23.16Table 23.1Table 23.2Table 23.3Table 23.4Table 23.5Table 23.6Table 23.7Table 23.8Table 23.9Table 23.10Table 23.11Table 23.12Table 23.13Table 23.14Table 23.15Table 23.16Table 23.17Table 23.18Table 23.19Table 23.20
Chapter 24 Educational and Software Resources for Data Clustering
24.1 Introduction24.2 Educational Resources24.2.1 Books on Data Clustering24.2.2 Popular Survey Papers on Data Clustering24.3 Software for Data Clustering24.3.1 Free and Open-Source Software24.3.1.1 General Clustering Software24.3.1.2 Specialized Clustering Software24.3.2 Commercial Packages24.3.3 Data Benchmarks for Software and Research24.4 SummaryBibliography

Overview

Research on the problem of clustering tends to be fragmented across the pattern recognition, database, data mining, and machine learning communities. Addressing this problem in a unified way, Data Clustering: Algorithms and Applications provides complete coverage of the entire area of clustering, from basic methods to more refined and complex data clustering approaches. It pays special attention to recent issues in graphs, social networks, and other domains.

The book focuses on three primary aspects of data clustering:

Methods, describing key techniques commonly used for clustering, such as feature selection, agglomerative clustering, partitional clustering, density-based clustering, probabilistic clustering, grid-based clustering, spectral clustering, and nonnegative matrix factorization
Domains, covering methods used for different domains of data, such as categorical data, text data, multimedia data, graph data, biological data, stream data, uncertain data, time series clustering, high-dimensional clustering, and big data
Variations and Insights, discussing important variations of the clustering process, such as semisupervised clustering, interactive clustering, multiview clustering, cluster ensembles, and cluster validation

In this book, top researchers from around the world explore the characteristics of clustering problems in a variety of application areas. They also explain how to glean detailed insight from the clustering process—including how to verify the quality of the underlying clusters—through supervision, human intervention, or the automated generation of alternative clusters.

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Read now

Unlock full access

More than 5,000 organizations count on O’Reilly

O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.

Julian F.

Head of Cybersecurity

I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.

Addison B.

Field Engineer

I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.

Amir M.

Data Platform Tech Lead

I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.

Mark W.

Embedded Software Engineer

Publisher Resources

ISBN: 9781466558229

Cloud Computing

Data Engineering

Data Science

AI & ML

Programming Languages

Software Architecture

IT/Ops

Security

Design

Business

Soft Skills