Chapter 5: Cluster Analysis

Question 1

What is cluster analysis?

Answer 1

Cluster analysis groups data objects based on information found only in the data that describes the objects and their relationships.

The goal is that the objects from within a group be similar (or related) to one another and different from (or unrelated to) the objects in other groups.

The greater the similarity (or homogeneity) within a group and the greater the difference between groups, the better or more distinct the clustering.

Question 2

Hierarchical vs Partitional

Partitional Clustering

Answer 2

A division of the set of data objects into non-overlapping subsets (clusters) such that each data object is in exactly one subset.

Question 3

Hierarchical vs Partitional

Hierarchical Clustering

Answer 3

If we permit clusters to have subclusters, then we obtain a hierarchical clustering, which is a set of nested clusters that are organized as a tree.

Each node (cluster) in the tree (except for the leaf nodes) is the union of its children (subclusters), and the root of the tree is the cluster containing all the objects.

Often, but not always, the leaves of the tree are singleton clusters of individual data objects.

Question 4

Exclusive vs Overlapping vs Fuzzy

Exclusive Clustering

Answer 4

Exclusive clustering assigns each object to a single cluster.

Question 5

Exclusive vs Overlapping vs Fuzzy

Overlapping Clustering

aka Non-Exclusive Clustering

Answer 5

An object can simultaneously belong to more than one group (class).

Question 6

Exclusive vs Overlapping vs Fuzzy

Fuzzy Clustering

Answer 6

Every object belongs to every cluster with a membership weight that is between 0 (absolutely doesn’t belong) and 1 (absolutely belongs).

In other words, clusters are treated as fuzzy sets.

Question 7

Complete versus Partial Clustering

Answer 7

A complete clustering assigns every object to a cluster, whereas a partial cluster does not.

The motivation for a partial clustering is that some objects in a data set may not belong to well-defined groups.

Question 8

5 Different Types of Clusters

Answer 8

• Well-separated
• Prototype-based
• Graph-based
• Density-based
• Shared-Property (Conceptual Clusters)

Question 9

Different Types of Clusters

Well-Separated

Answer 9

A cluster is a set of objects in which each object is closer (or more similar) to every other object in the cluster than to any object not in the cluster.

Sometimes a threshold is used to specify that all the objects in a cluster must be sufficiently close (or similar) to one another.

Question 10

Different Types of Clusters

Prototype-Based

Answer 10

A cluster is a set of objects in which each object is closer (more similar) to the prototype that defines the cluster than to the prototype of any other cluster.

For data with continuous attributes, the prototype of cluster is often a centroid, i.e., the average of all the points in the cluster.

When a centroid is not meaningful, such as when the data has categorical attributes, the prototype is often a medoid, i.e. the most representative point of a cluster.

For many types of data, the prototype can be regarded as the most central point, and in instances, we commonly refer to prototype-based clusters as center-based clusters.

Question 11

Different Types of Clusters

Graph-based

Answer 11

If the data is represented as a graph, where the nodes are objects and the links represent connections among objects, then a cluster can be defined as a connected component; i.e. a group of objects that are connected to one another, but that have no connection to objects outside the group.

Question 12

Graph-based cluster

Contiguity-based cluster

Answer 12

Where two objects are connected only if they are within a specified distance of each other.

This implies that each object in a contiguity-based cluster is closer to some other object in the cluster than to any point in a different cluster.

This definition of a cluster is useful when clusters are irregular or intertwined.

Question 13

Graph-based cluster

Clique

Answer 13

A set of nodes in a graph that are completely connected to each other.

Specifically, if we add connections between objects in the order of their distance from one another, a cluster is formed when a set of objects forms a clique.

Question 14

Different Types of Clusters

Density-Based

Answer 14

A cluster is a dense region of objects that is surrounded by a region of low density.

Question 15

Different Types of Clusters

Shared-Property (Conceptual Clusters)

Answer 15

More generally, we can define a cluster as a set of objects that share some property.

This definition encompasses all the previous definition of a cluster; e.g., objects in a center-based cluster share the property that they are all closest to the same centroid or medoid.

Question 16

K-means

Answer 16

This is a prototype-based, partitional clustering technique that attempts to find a user-specified number of clusters (K), which are represented by their centroids.

Question 17

Agglomerative Hierarchical Clustering

Answer 17

This clustering approach refers to a collection of closely-related clustering techniques that produce a hierarchical clustering by starting with each point as a singleton cluster and then repeatedly merging the two closest clusters until a single, all-encompassing cluster remains.

Question 18

DBSCAN

Answer 18

This is a density-based clustering algorithm that produces a partitional clustering, in which the number of clusters is automatically determined by the algorithm.

Points in low-density regions are classified as noise and omitted; thus, DBSCAN does not produce a complete clustering.

Question 19

Algorithm 5.1

Basic K-means algorithm

Answer 19

1. Select K points as initial centroids.
2. repeat
3. . . Form K clusters by assigning each point to its closest centroid.
4. . . Recompute the centroid of each cluster.
5. until Centroids do not change.

Question 20

Algorithm 5.2

K-means++ initialization algorithm

Answer 20

1. For the first centroid, pick one of the points at random.
2. for i=1 to number of trials do
3. . . Compute the distance, d(x), of each point to its closest centroid.
4. . . Assign each point a probability proportional to each point’s d(x)².
5. . . Pick a new centroid from the remaining points using the weighted probabilities.
6. end for

Question 21

K Means

Time and Space Complexity

Answer 21

The space requirements for K-means are modest because only the data points and centroids are stored.

Specifically, the storage required is O((m + K) n), where m is the number of points and n is the number of attributes.

The time requirements for K-means are also modest - basically linear in the number of data points. In particular the time required is O(I x K x m x n), where I is the number of iterations required for convergence.

I is often small and can usually be safely bounded, as most changes typically occur in the first few iterations. Therefore, K-means is linear in m, the number of points, and is efficient as well as simple provided that K, the number of clusters, is significantly less than m.

Question 22

K-Means: Additional Issues

Handling Empty Clusters

Answer 22

One of the problems with the basic K-means algorithm is that empty clusters can be obtained if no points are allocated to a cluster during the assignment step.

If this happens, then a strategy is needed to choose a replacement centroid, since otherwise, the squared error will be larger than necessary.

One approach is to choose the point tha tis farthest away from any current centroid. If nothing else, this eliminates the point that currently contributes most to the total squared error.

Question 23

K-Means: Additional Issues

Outliers

Answer 23

When the squared error criterion is used, outliers can unduly influence the clusters that are found.

In particular, when outliers are present, the resulting cluster centroids (prototypes) are typically not as representative as they otherwise would be and thus, the SSE will be higher. Because of this, it is often useful to discover outliers and eliminate them beforehand.

It is important, however, to appreciate that there are certain clustering applications for which outliers should not be eliminated. When clustering is used for data compression, every point must be clustered, and in some cases, such as financial analysis, apparent outliers, e.g., unusually profitable customers, can be the most interesting points.

Question 24

K-Means: Reducing the SSE with Postprocessing

2 Ways to reduce SSE by increasing the number of clusters

Answer 24

1. Split a cluster: The cluster with the largest SSE is usually chosen, but we could also split the cluster with the largest standard deviation for one particular attribute.
2. Introduce a new cluster centroid: Often the point that is farthest from any cluster center is chosen. We can easily determine this if we keep track of the SSE contributed by each point. Another approach is to choose randomly from all points or from the points with the highest SSE with respect to their closest centroids.

Question 25

K-Means: Reducing the SSE with Postprocessing

2 Strategies to decrease the number of clusters

Answer 25

1. Disperse a cluster: This is accomplished by removing the centroid that corresponds to the cluster and reassigning the points to the other clusters. Ideally, the cluster that is dispersed should be the one that increases the total SSE the least.
2. Merge two clusters: The clusters with the closest centroids are typically chosen, although another, perhaps better, approch is to merge the two clusters that result in the smallest increase in total SSE. These two merging strategies are the same ones that are used in the hierarchical clustering techniques known as the centroid method and Ward’s method, respectively.

Question 26

Algorithm 5.3.

Bisecting K-means algorithm

Answer 26

1. Initialize the list of clusters to contain the cluster consisting of all points.
2. repeat
3. . . Remove a cluster from the list of clusters.
4. . . {Perform several “trial” bisections of the chosen cluster.}
5. . . for i=1 to number of trials do
6. . . . . Bisect the selected cluster using basic K-means.
7. . . end for
8. . . Select the two clusters from the bisection with the lowest total SSE.
9. . . Add these two clusters to the list of clusters.
10. until The list of clusters contains K cluster.

Question 27

K-Means Applicability

Answer 27

K-means and its variations have limitations with respect to finding different types of clusters.

In particular, K-means has difficulty detecting “natural” clusters, when clusters have
- non-sperical shapes
- or widely different sizes
- or widely different densities.

The difficulty in these situations is that the K-means objective function is a mismatch for the kinds of clusters we are trying to find because it is minimized by globular clusters of equal size and density or by clusters that are well-separated.

Question 28

Strengths of K-means

Answer 28

• K-means is simple
• It can be used for a wide variety of data types
• It is quite efficient, even though multiple runs are often performed.

Question 29

Weaknesses of K-means

Answer 29

• Not suitable for all types of data.
• It cannot handle non-globular clusters or clusters of different sizes and densities.
• It has trouble clustering data that contains outliers.
• K-means is restricted to data for which there is a notion of a center (centroid)

Question 30

2 Approaches for generating a hierarchical clustering

Answer 30

• Agglomerative
• Divisive

Question 31

Agglomerative Clustering

Answer 31

Start with the points as individual clusters and, at each step, merge the closest pair of clusters.

This requires defining a notion of cluster proximity.

Question 32

Divisive Clustering

Answer 32

Start with one, all-inclusive cluster and, at each step, split a cluster until only singleton clusters of individual points remain.

In this case, we need to decide which cluster to split at each step and how to do the splitting.

Question 33

Algorithm 5.4

Basic agglomerative hierarchical clustering algorithm

Answer 33

1. Compute the proximity matrix, if necessary.
2. repeat
3. . . Merge the closest two clusters
4. . . Update the proximity to reflect the proximity between the new cluster and the original clusters.
5. until Only one cluster remains.

Question 34

Agglomerative Hierarchical Clustering

Space Complexity

Answer 34

The basic agglomerative hierarchical clustering algorithm uses a proximity matrix.

This requires the storage of m²/2 proximities (assuming the proximity matrix is symmetric) where m is the number of data points.

The space needed to keep track of the clusters is proportional to the number of clusters, which is m-1.

Hence, the total space complexity is O(m²)

Question 35

Agglomerative Hierarchical Clustering

Computational Complexity

Answer 35

O(m²) time is required to compute the proximity matrix.

Question 36

Key Issues in Hierarchical Clustering

Lack of a Global Objective Function

Answer 36

Agglomerative hierarchical clustering cannot be viewed as globally optimizing an objective function.

Instead, agglomerative hierarchical clustering techniques use various criteria to decide locally, at each step, which clusters should be merged (or split for divisive approaches).

This approach yields clustering algorithms that avoid the difficulty of attempting to solve a hard combinatorial optimization problem.

Question 37

Key Issues in Hierarchical Clustering

Ability to Handle Different Cluster Sizes

Answer 37

2 Approaches to treating the relative sizes of the pairs of clusters that are merged:

• Weighted. All clusters are treated equally.
• Unweighted. This takes the number of points in each cluster into account.

(The terminology of weighted or unweighted refers to the data points, not the clusters. I.e. treating clusters of unequal size equally - the weighted approach - gives different weights to the points in different clusters, while taking the cluster size into account - the unweighted approach - gives points in different clusters the same weight.)

Question 38

Key Issues in Hierarchical Clustering

Merging Decisions are Final

Answer 38

Agglomerative hierarchical clustering algorithms tend to make good local decisions about combining two clusters because they can use the local information about the pairwise similarity of all points.

However, once a decision is made to merge two clusters, it cannot be undone at a later time.

This approach prevents a local optimization criterion from becoming a global optimisation criterion.

Question 39

Hierarchical Clustering

Outliers

Answer 39

Outliers pose the most serious problems for Ward’s method and centroid-based hierarchical clustering approaches because they increase SSE and distort centroids.

For single link, complete link and group average, outliers are potentially less problematic. As hierarchical clustering proceeds for these algorithms, outliers tend to form singleton / small clusters that do not merge with any other clusters until much later in the merging process.

By discarding singleton or small clusters that are not merging with other clusters, outliers can be removed.

Question 40

Density-based clustering

Answer 40

Density-based clustering locates regions of high density that are separated from one another by regions of low density.

Question 41

Classification of Points According to Center-Based Density

Answer 41

A center-based approach to density allows us to classify a point as being:
- A core point, in the interior of a dense region.
- A border point, on the edge of a dense region.
- A noise point, in a sparsely occupied region.

Question 42

Classification of Points According to Center-Based Density

Core points

Answer 42

These points are in the interior of a density-based cluster.

A point is a core point if there are at least MinPts wihin a distance of Eps, where MinPts and Eps are user-specified parameters.

Question 43

Classification of Points According to Center-Based Density

Border points

Answer 43

A border point is not a core point, but falls within a neighbourhood of a core point.

A border point can fall within the neighbourhoods of several core points.

Question 44

Classification of Points According to Center-Based Density

Noise points

Answer 44

A noise point is any point that is neither a core point nor a border point.

Question 45

Algorithm 5.5

DBSCAN Algorithm

Answer 45

1. Label all points as core, border, or noise points.
2. Eliminate noise points.
3. Put an edge between all core points within a distance Eps of each other.
4. Make each group of connected core points into a separate cluster.
5. Assign each border point to one of the clusters of its associated core points.

Question 46

DBScan Algorithm

Time & Space Complexity

Answer 46

The basic time complexity of the DBSCAN algorithm is O(m x time to find points in the Eps-neighbourhood), where m is the number of points.

In the worst case, this complexity is O(m²). However, in low-dimensional spaces, data structures such as kd-trees allow efficient retrieval of all points wihin a given distance of a specified point, and the time complexity can be as low as O(*m* log *m*) in the average case.

The space requirement of DBSCAN, even for high-dimensional data, is O(m) because it is necessary to keep only a small amount of data for each point, i.e. the cluster label and the identification of each point as a core, border, or noise point.

Question 47

Selection of DBScan Parameters

How to select Eps and MinPts

Answer 47

The basic approach is to look at the behaviour of the distance from a point to its kth nearest neighbour, which we will call the k-dist.

For points that belong to some cluster, the value of k-dist will be small if k is not larger than the cluster size.

If we compute the k-dist for all the data points for some k, sort them in increasing order, and then plot the sorted values, we expect to see a sharp change at the value of k-dist that corresponds to a suitable value of Eps.

If we select this distance as the Eps parameter, and take the value of k as the MinPts parameter, then points for which the k-dist is less than Eps will be labelled as core points, while other points will be labelled as noise or border points.

Question 48

Strengths of DBScan

Answer 48

Because DBSCAN uses a density-based definition of a cluster, it:
- is relatively resistant to noise and
- can handle clusters of arbitrary shapes and size.

Thus, it can find many clusters that could not be found using K-means.

Question 49

Weaknesses of DBSCAN

Answer 49

• DBSCAN has trouble when the clusters have widely varying densities.
• It also has trouble with high-dimensional data because density is more difficult to define for such data.
• DBSCAN can be expensive when the computation of nearest neighbours requires computing all pairwise proximities, as is usually the case for high-dimensional data.

Question 50

5 Important issues for cluster validation

Answer 50

1. Determining the clustering tendency of a set of data, i.e. distinguishing whether non-random structure actually exists in the data.
2. Determining the correct number of clusters.
3. Evaluating how well the results of a cluster analysis fit the data without reference to external information.
4. Comparing the results of a cluster analysis to externally known results, suh as externally provided class labels.
5. Comparing two sets of clusters to determine which is better.

Question 51

3 Types of cluster evaluation measures

Answer 51

• Unsupervised
• Supervised
• Relative

Question 52

3 Types of cluster evaluation measures

Unsupervised

Answer 52

Measures the goodness of a clustering structure without respect to external information.
An example of this is the SSE.

Unsupervised measures of cluster validity are often further divided into two classes:
- measures of cluster cohesion
- measures of cluster separation

Unsupervised measures are often called internal indices because they use only information present in the data set.

Question 53

Cluster cohesion

Answer 53

(tightness, compactness)

Cluster cohesion determines how closely related the objects in a cluster are.

Question 54

Cluster separation

Answer 54

(isolation)

Cluster separation determines how distinct or well-separated a cluster is from other clusters.

Question 55

3 Types of cluster evaluation measures

Supervised

Answer 55

Measures the extent to which the clustering structure discovered by a clustering algorithm matches some external structure.

E.g. entropy.

Supervised measures are often called external indices because they use information not present in the data set.

Question 56

Graph-based View of Cohesion

Answer 56

The sum of the weights of the links in the proximity graph that connect points within the cluster.

Question 57

Graph-based View of Cluster Separation

Answer 57

The separation between two clusters can be measured by the sum of the weights of the links from points in one cluster to points in the other cluster.

Question 58

Prototype-based View of Cluster Cohesion

Answer 58

The sum of the proximities with respect to the prototype (centroid or medoid) of the cluster.

Question 59

Prototype-based View of Cluster Separation

Answer 59

The separation between two clusters can be measured by the proximity of the two cluster prototypes.

Question 60

Between group sum of squares

(SSB)

Answer 60

When proximity is measured by Euclidean distance, the traditional measure of separation between clusters is the between group sum of squares (SSB), which is:

the sum of the squared distance of a cluster centroid cᵢ, to the overall mean, c, of all the data points.

Question 61

Silhouette Coefficient

Answer 61

Combines both cohesion and separation.

The value can vary between -1 and 1. A negative value is undesirable, as this corresponds to a case in which aᵢ, the average distance to points in the cluster, is greater than bᵢ, the minimum average distance to points in another cluster.

We want the silhouette coefficient to be positive (aᵢ < bᵢ), and for aᵢ to be as close to 0 as possible, since the coefficient assumes its maximum value of 1 when aᵢ = 0.

Question 62

3 Steps to Calculate the Silhouette Coefficient

Answer 62

For the ith object:

1. Calculate its average distance to all other objects in the cluster (aᵢ)
2. For any cluster not containing i, calculate i’s average distance to all objects in the cluster. Find the minimum w.r.t. all clusters. (bᵢ)
3. sᵢ = (bᵢ - aᵢ) / max(aᵢ, bᵢ)

Question 63

Cophenetic Distance

Answer 63

The proximity at which an agglomerative hierarchical clustering technique puts the objects in the same cluster for the first time.

E.g.
If at some point in the agglomerative hierarchical clustering process, the smallest distance between the two clusters that are merged is 0.1, then all the points in one cluster have a cophenetic distance of 0.1 with respect to the points in the other cluster.

Question 64

Cophenetic Distance Matrix

Answer 64

A matrix in which the entries are the cophenetic distances between each pair of objects.

The cophenetic distance is different for each hierarchical clustering of points.

Question 65

Cophenetic Correlation Coefficient

(CPCC)

Answer 65

The correlation between the entries of the Cophenetic Distance Matrix and the original dissimilarity matrix.

It is a standard measure of how well a hierarchical clustering fits the data.

One of the most common uses is to evaluate which type of hierarchical clustering is best for a particular type of data.