Chapter 9�Cluster Analysis: Advanced Methods

Outline

• Probabilistic model-based clustering
• Clustering high-dimensional data
• Biclustering
• Dimensionality reduction for clustering
• Clustering graph and network data
• Semisupervised clustering

2

Outline

• Probabilistic model-based clustering
• Fuzzy clusters
• Probabilistic model-based clusters
• Expectation-maximization (EM) algorithm
• Clustering high-dimensional data
• Biclustering
• Dimensionality reduction for clustering
• Clustering graph and network data
• Semisupervised clustering

3

Fuzzy Set and Fuzzy Cluster

4

4

Fuzzy (Soft) Clustering

5

5

Probabilistic Model-Based Clustering

• Cluster analysis is to find hidden categories
• A hidden category (i.e., probabilistic cluster) is a distribution over the data space, which can be mathematically represented using a probability density function (or distribution function)
• Example: two categories for digital cameras sold
• Consumer line vs. professional line
• Density functions f₁, f₂ for C₁, C₂
• Obtained by probabilistic clustering

​

6

6

Probabilistic Model-Based Clustering

• A mixture model assumes that a set of observed objects is a mixture of instances from multiple probabilistic clusters, and conceptually each observed object is generated independently
• Our task: infer a set of k probabilistic clusters that is mostly likely to generate D using the above data generation process

​

7

7

Model-Based Clustering

8

8

Model-Based Clustering

9

9

Univariate Gaussian Mixture Model

10

10

Univariate Gaussian Mixture Model

11

11

The EM (Expectation Maximization) Algorithm

• The k-means algorithm has two steps at each iteration
• Expectation Step (E-step): Given the current cluster centers, each object is assigned to the cluster whose center is closest to the object: An object is expected to belong to the closest cluster
• Maximization Step (M-step): Given the cluster assignment, for each cluster, the algorithm adjusts the center so that the sum of distance from the objects assigned to this cluster and the new center is minimized
• The (EM) algorithm: A framework to approach maximum likelihood or maximum a posteriori estimates of parameters in statistical models
• E-step assigns objects to clusters according to the current fuzzy clustering or parameters of probabilistic clusters
• M-step finds the new clustering or parameters that minimize the sum of squared error (SSE) or the expected likelihood

12

12

Fuzzy Clustering Using the EM Algorithm: Example

13

Fuzzy Clustering Using the EM Algorithm: Example

14

Computing Mixture Models with EM

15

Computing Mixture Models with EM

16

Advantages and Disadvantages of Mixture Models

• Strength
• Mixture models are more general than partitioning and fuzzy clustering
• Clusters can be characterized by a small number of parameters
• The results may satisfy the statistical assumptions of the generative models
• Weakness
• Converge to local optimal (overcome: run multi-times with random initialization)
• Computationally expensive if the number of distributions is large, or the data set contains very few observed data points
• Need large data sets
• Hard to estimate the number of clusters

17

17

Outline

• Probabilistic model-based clustering
• Clustering high-dimensional data
• Why is clustering high-dimensional data challenging?
• Axis-parallel subspace approaches
• Arbitrarily oriented subspace approaches
• Biclustering
• Dimensionality reduction for clustering
• Clustering graph and network data
• Semisupervised clustering

18

Motivation Example

19

Curse of Dimensionality

• Many irrelevant or correlated attributes
• Data sparsity
• Distance concentration effect of similarity measures
• Difficulty in optimization

​

20

High-dimensional Clustering Models

• Clusters hidden in high-dimensional data are often significantly smaller and are manifested by a dramatically smaller subset of attributes
• An essential principle in clustering high-dimensional data is to find clusters in subspaces
• Finding clusters in axis-parallel versus arbitrarily oriented subspaces

21

Categorization of High-dimensional Clustering Methods

• The clustering approaches: identify clusters in subspaces
• The subspace clustering methods: find all clusters in all subspaces of the entire data space
• The projected clustering methods: partition a given data set into non-overlapping subsets
• The bi-clustering methods: cluster attributes and objects simultaneously
• The dimensionality-reduction methods

22

Subspace Clustering: Subspace Search Methods

• Search various subspaces to find clusters
• Bottom-up approaches
• Start from low-D subspaces and search higher-D subspaces only when there may be clusters in such subspaces
• Various pruning techniques to reduce the number of higher-D subspaces to be searched
• Ex. CLIQUE (Agrawal et al. 1998)
• Top-down approaches
• Start from full space and search smaller subspaces recursively
• Effective only if the locality assumption holds: Restricts that the subspace of a cluster can be determined by the local neighborhood
• Ex. PROCLUS (Aggarwal et al. 1999): A k-medoid-like method

23

Example of CLIQUE: Density and Grid-Based Subspace Clustering

• Start at 1-D space and discretize numerical intervals in each axis into grid
• Find dense regions in each subspace and generate their minimal descriptions (clusters)
• Use the dense regions to find promising candidates in 2-D space (using Apriori principle)
• CLIQUE automatically identifies subspaces of a high dimensional data space and terminates when no more clusters or cluster candidates can be found

24

CLIQUE Illustration

25

PROCLUS: A Projected Clustering Method

• A k-medoid-like method
• Three phases
• The initialization phase: generate k potential cluster centers using a greedy sample of the data set
• The iterative phase: progressively improve the quality of the medoids
• Find the attributes for each medoid
• Form clusters
• The refinement phase: adjust the subspaces of the clusters using only the data objects assigned to a cluster

26

Arbitrarily Oriented Subspace Approaches

27

Outline

• Probabilistic model-based clustering
• Clustering high-dimensional data
• Biclustering
• Why and where is biclustering useful?
• Types of biclusters
• Biclustering methods
• Enumerating all biclusters using MaPle
• Dimensionality reduction for clustering
• Clustering graph and network data
• Semisupervised clustering

28

Bi-Clustering Methods

• Bi-clustering: Cluster both objects and attributes simultaneously (treat objects and attributes in a symmetric way)
• Four requirements:
• Only a small set of objects participate in a cluster
• A cluster only involves a small number of attributes
• An object may participate in multiple clusters, or does not participate in any cluster at all
• An attribute may be involved in multiple clusters, or is not involved in any cluster at all

29

Bi-Clustering Methods

• Example 1: Gene expression or microarray data: a gene sample/condition matrix.
• Each element in the matrix, a real number, records the expression level of a gene under a specific condition
• Example 2: Clustering customers and products
• Another bi-clustering problem

​

30

Types of Bi-clusters

31

31

Bi-Clustering Methods

• Real-world data is noisy: Try to find approximate bi-clusters
• Methods: Optimization-based methods vs. enumeration methods
• Optimization-based methods
• Try to find a submatrix at a time that achieves the best significance as a bi-cluster
• Due to the cost in computation, greedy search is employed to find local optimal bi-clusters
• Ex. δ-Cluster Algorithm (Cheng and Church, ISMB’2000)
• Enumeration methods
• Use a tolerance threshold to specify the degree of noise allowed in the bi-clusters to be mined
• Then try to enumerate all submatrices as bi-clusters that satisfy the requirements
• Ex. δ-pCluster Algorithm (H. Wang et al.’ SIGMOD’2002, MaPle: Pei et al., ICDM’2003)

32

32

Bi-Clustering for Micro-Array Data Analysis

• Left figure: Micro-array “raw” data shows 3 genes and their values in a multi-D space: Difficult to find their patterns
• Right two: Some subsets of dimensions form nice shift and scaling patterns
• No globally defined similarity/distance measure
• Clusters may not be exclusive
• An object can appear in multiple clusters

33

33

δ-Bi-Cluster

34

34

δ-Bi-Cluster

• A submatrix I x J is δ-bi-cluster if H(I x J) ≤ δ where δ ≥ 0 is a threshold. When δ = 0, I x J is a perfect bi-cluster with coherent values. By setting δ > 0, a user can specify the tolerance of average noise per element against a perfect bi-cluster
• residue(e_ij) = e_ij − e_iJ − e_Ij + e_IJ

35

The δ-Cluster Algorithm

36

36

The δ-Cluster Algorithm

• Addition phase:
• Expand iteratively the δ-bi-cluster I x J obtained in the deletion phase as long as the δ-bi-cluster requirement is maintained
• Consider all the rows/columns not involved in the current bi-cluster I x J by calculating their mean squared residues
• A row/column of the smallest mean squared residue is added into the current δ-bi-cluster
• It finds only one δ-bi-cluster, thus needs to run multiple times: replacing the elements in the output bi-cluster by random numbers

​

37

δ-pCluster

38

38

δ-pCluster

• A submatrix I x J is a δ-pCluster (pattern-based cluster) if the p-score of every 2 x 2 submatrix of I x J is at most δ, where δ ≥ 0 is a threshold specifying a user's tolerance of noise against a perfect bi-cluster
• The p-score controls the noise on every element in a bi-cluster, while the mean squared residue captures the average noise
• Monotonicity: If I x J is a δ-pClusters, every x x y (x,y ≥ 2) submatrix of I x J is also a δ-pClusters.
• A δ-pCluster is maximal if no more row or column can be added into the cluster and retain δ-pCluster: We only need to compute all maximal δ-pClusters.

39

39

MaPle: Efficient Enumeration of δ-pClusters

• Pei et al., MaPle: Efficient enumerating all maximal δ-pClusters. ICDM'03
• Framework: Same as pattern-growth in frequent pattern mining (based on the downward closure property)
• For each condition combination J, find the maximal subsets of genes I such that I x J is a δ-pClusters
• If I x J is not a submatrix of another δ-pClusters
• then I x J is a maximal δ-pCluster

40

40

Outline

• Probabilistic model-based clustering
• Clustering high-dimensional data
• Biclustering
• Dimensionality reduction for clustering
• Linear dimensionality reduction methods for clustering
• Nonnegative matrix factorization (NMF)
• Spectral clustering
• Clustering graph and network data
• Semisupervised clustering

41

Dimensionality-Reduction Methods

• Dimensionality reduction: In some situations, it is more effective to construct a new space instead of using some subspaces of the original data
• Example: to cluster the points in the figure, any subspace of the original one, X and Y, cannot help, since all the three clusters will be projected into the overlapping areas in X and Y axes
• Construct a new dimension as the dashed one, the three clusters become apparent when the points projected into the new dimension

42

42

Dimensionality Reduction Methods

• Feature selection and extraction: But may not focus on clustering structure finding
• Non-negative matrix factorization (NMF): One high-D sparse nonnegative matrix factorizes approximately into two low-rank matrices
• Spectral clustering: Uses the spectrum of the similarity matrix of the data to perform dimensionality reduction for clustering in fewer dimensions

​

43

High-Dimensional Clustering by Nonnegative Matrix Factorization (NMF)

• Nonnegative matrix factorization (NMF)
• A nonnegative matrix A_n×d (e.g., word frequencies in docs) can be approximately factorized into two non-negative low rank matrices U_n×k and V_k×d : A_n×d ≈ U_n×k V_k×d (or, A ≈ U V)
• Residue matrix R represents the noise in the underlying data: R = A − U V
• Constrained optimization: Determine U and V so that the sum of the square of the residuals in R is minimized
• U and V simultaneously provide the clusters on the rows (docs) and columns (words). Thus it is another kind of co-clustering
• U_n×k represents the components of each of n objects mapped into each of k newly created dimensions
• V_k×d represents each of k newly created dimensions in terms of the original d dimensions (words)
• Advantage: Intepretability of NMF—A data point can be expressed as a non-negative linear combination of the concepts in the underlying data

44

Spectral Clustering Methods

• Spectral clustering methods use the spectrum of the similarity matrix of the data to perform dimensionality reduction for clustering in fewer dimensions
• It combines feature extraction and clustering
• Classical methods
• Normalized Cuts (Shi and Malik, CVPR’97 or PAMI’2000)
• The Ng-Jordan-Weiss algorithm (NIPS’01)

45

45

Spectral Clustering: �The Ng-Jordan-Weiss (NJW) Algorithm

46

46

Spectral Clustering: Illustration and Comments

• Spectral clustering: Effective in tasks like image processing
• Scalability challenge: Computing eigenvectors on a large matrix is costly
• Can be combined with other clustering methods, such as bi-clustering

47

47

Spectral Clustering: Illustration and Comments

48

48

Outline

• Probabilistic model-based clustering
• Clustering high-dimensional data
• Biclustering
• Dimensionality reduction for clustering
• Clustering graph and network data
• Applications and challenges
• Similarity measures
• Graph clustering methods
• Semisupervised clustering

49

Clustering Graphs and Network Data

• Applications
• Bi-partite graphs, e.g., customers and products, authors and conferences
• Web search engines, e.g., click through graphs and Web graphs
• Social networks, friendship/coauthor graphs
• Similarity measures
• Geodesic distances
• Distance based on random walk (SimRank)
• Graph clustering methods
• Minimum cuts: FastModularity (Clauset, Newman & Moore, 2004)
• Density-based clustering: SCAN (Xu et al., KDD’2007)

50

50

Similarity Measure (I): Geodesic Distance

• Geodesic distance (A, B): length (i.e., # of edges) of the shortest path between A and B (if not connected, defined as infinite)
• Eccentricity of v, eccen(v): The largest geodesic distance between v and any other vertex u ∈ V − {v}.
• E.g., eccen(a) = eccen(b) = 2; eccen(c) = eccen(d) = eccen(e) = 3
• Radius of graph G: The minimum eccentricity of all vertices, i.e., the distance between the “most central point” and the “farthest border”
• r = min v∈V eccen(v)
• E.g., radius (g) = 2
• Diameter of graph G: The maximum eccentricity of all vertices, i.e., the largest distance between any pair of vertices in G
• d = max v∈V eccen(v)
• E.g., diameter (g) = 3
• A peripheral vertex is a vertex that achieves the diameter.
• E.g., Vertices c, d, and e are peripheral vertices

51

51

SimRank: Similarity Based on Random Walk and Structural Context

52

52

Similarity Based on Random Walk in a Strongly Connected Component

53

53

Graph Clustering: Sparsest Cut

54

54

Graph Clustering: Sparsest Cut

55

55

Graph Clustering: Challenges of Finding Good Cuts

• High computational cost
• Many graph cut problems are computationally expensive
• The sparsest cut problem is NP-hard
• Need to tradeoff between efficiency/scalability and quality
• Sophisticated graphs
• May involve weights and/or cycles.
• High dimensionality
• A graph can have many vertices. In a similarity matrix, a vertex is represented as a vector (a row in the matrix) whose dimensionality is the number of vertices in the graph
• Sparsity
• A large graph is often sparse, meaning each vertex on average connects to only a small number of other vertices
• A similarity matrix from a large sparse graph can also be sparse

56

56

Two Approaches for Graph Clustering

• Two approaches for clustering graph data
• Use generic clustering methods for high-dimensional data
• Designed specifically for clustering graphs
• Using clustering methods for high-dimensional data
• Extract a similarity matrix from a graph using a similarity measure
• A generic clustering method can then be applied on the similarity matrix to discover clusters
• Ex. Spectral clustering: approximate optimal graph cut solutions
• Methods specific to graphs
• Search the graph to find well-connected components as clusters
• Ex. SCAN (Structural Clustering Algorithm for Networks)
• X. Xu, N. Yuruk, Z. Feng, and T. A. J. Schweiger, “SCAN: A Structural Clustering Algorithm for Networks”, KDD'07

57

57

SCAN: Density-Based Clustering of Networks

• Application: Given simply information of who associates with whom, could one identify clusters of individuals with common interests or special relationships (families, cliques, terrorist cells)?
• How many clusters?
• What size should they be?
• What is the best partitioning?
• Should some points be segregated?

​

58

An Example Network

A Social Network Model

• Cliques, hubs and outliers
• Individuals in a tight social group, or clique, know many of the same people, regardless of the size of the group
• Individuals who are hubs know many people in different groups but belong to no single group. Politicians, for example bridge multiple groups
• Individuals who are outliers reside at the margins of society. Hermits, for example, know few people and belong to no group
• The Neighborhood of a Vertex
• Define Γ(ν) as the immediate neighborhood of a vertex (i.e. the set of people that an individual knows)

​

​

​

59

59

Structure Similarity

60

60

Outline

• Probabilistic model-based clustering
• Clustering high-dimensional data
• Biclustering
• Dimensionality reduction for clustering
• Clustering graph and network data
• Semisupervised clustering
• Semisupervised clustering on partially labeled data
• Semisupervised clustering on pairwise constraints
• Other types of background knowledge for semisupervised clustering

61

Clustering with Partially Labeled Data

• Example: building a malware detector
• Data
• A large number of images of host systems
• A small number of labeled images into two categories: malware and benign
• Using only the labeled data to build a classifier may not be reliable and does not take the full advantage of all data
• Semisupervised clustering approaches assume some domain knowledge is available

62

Semisupervised Clustering on Partially Labeled Data

63

Pairwise Constraints

• Must-link constraints: two objects x and y should be grouped into one cluster in the output
• Cannot-link constraints: two objects x and y should belong to different clusters in the output

64

The COP-k-Means Algorithm

65

Other Types of Background Knowledge for Semisupervised Clustering

• Semisupervised hierarchical clustering
• Clusters associated with outcome variables
• Active and interactive learning for semisupervised clustering

66