Unit 4 - Fundamentals of Clustering

Question 1

What is clustering?

Answer 1

Discover natural groupings in data

Clustering does not attempt to reveal relationships underlying the variables (as in the case of association analysis). Instead, clustering aims to group objects or records into different clusters to identify groups that exhibit a high degree of internal (within-cluster) similarity and external (between-cluster) dissimilarity.

Question 2

What are some clustering applications?

Answer 2

• Market Segmentation
  Divide customers into groups so that a mixture of selling strategies can be formulated to maximize company revenue
• Credit Scoring
  Bank or credit card company may apply clustering to Identify potential fraud cases
• Anomaly detection– things that are not in the normal clusters
  An underwriter attempts to single out the accident-prone clients who are likely to file claims after being insured
• Image Segmentation
  An image recognition system tries to recognize different parts of an image

Question 3

What are some examples of clustering?

Answer 3

• A capitalist endeavours to spot some potential hotels for takeover, based on their financial health, market shares, location and quality of service.
• An underwriter attempts to single out the accident-prone clients who are likely to file claims after being insured.
• A football club targets to shortlist a pool of potential players, according to their experience, age, transfer fees, market value, goal-scoring rate and fitness.
• A higher learning committee plans to categorise colleges in terms of student-faculty ratio, graduation rate, research ranking and alumni donation.
• An international agency sets out to segment countries by means of indicators like GDP per capita, literacy rate, population density, life expectancy and standards of living.

Question 4

What is a cluster?

Answer 4

a set in which its members are similar to one another but dissimilar to others not within the same cluster.

Question 5

Why is clustering different from association analysis?

Answer 5

clustering finds relationship

between records, association finds the relationship between field

Question 6

Why is clustering different from classification?

Answer 6

clustering does not train with a class
label, as in building classifiers in supervised learning

Question 7

Why is clustering different from factor analysis?

Answer 7

factor analysis groups variables; whereas clustering groups objects

Question 8

Steps in cluster analysis?

Answer 8

1) define a measure of similarity
2) choose an appropriate clustering algorithm
3) set the number of clusters
4) generate the clusters
5) Interpret the clusters, profile the clusters with the aim of illustrating their differences
6) validate the clusters

Question 9

What are the two types of clustering?

Answer 9

1) Hierarchical (agglomerative)

2) Partitional (divisive “top down”)

Question 10

Steps of hierarchical clustering?

Answer 10

1) compute the proximity among the data objects
repeatedly merge the closest data objects
2) Update the proximity between the new and the original clusters until all objects are grouped to form one final cluster

Question 11

Steps of partitioning clustering?

Answer 11

1) select k seed points as initial centroids
2) form k clusters by assigning each object to its closest centroid
3) update the centroid of each cluster until the stopping criterion is fulfilled
AKA K-means

Question 12

What is a dendrogram?

Answer 12

Illustrate how the objects and levels of distance are grouped and changed
It can show how the clusters are formed

Question 13

How reliant is clustering on an analyst? 7 poiints

Answer 13

• Exploratory in nature
• In hierarchical clustering, no grouping structure is assumed
• Clustering solution relies heavily on the analyst’s knowledge to label the clusters in a meaningful way
• Different solutions may be obtained with different stopping rules
• Usually, more than one competing solutions are evaluated before the clustering solution is determined
• The interpretation and labelling of a cluster is a subjective or even creative affair
• In some instances, there may be more than one interpretation for the identified clusters

Question 14

What are proximity measures?

Answer 14

closeness / distance measure / similarity

Question 15

What are the commonly used proximity measures?

Answer 15

• Euclidean distance
• Mahalanobis distance
• Minkowski distance.

Question 16

Difference between Mahalanobis distance and Euclidean distance?

Answer 16

A and B are equally distant from X BUT this is not true
if you look at the density distribution

• Mahalanobis takes dispersion into account
• Also useful for anomaly detection esp. for non-spherical-shaped distribution, such as the ellipsoidal shape in the right figure.

Question 17

Difference between Euclidean and Minkowski?

Answer 17

Euclidean distance is a special case of Minkowski distance with M=2

Question 18

What does clustering criteria Root-mean-square standard deviation do?

Answer 18

pools the variations of all the clustering variables that form the cluster at a certain stage of the clustering process

Question 19

The formula of Root-Mean-Square standard deviation?

Answer 19

Pooled sum of squares for all clustering variables divided by pooled degrees of freedom for all the clustering variables

small RMSSTD > small variations > homogenous cluster
large RMSSTD > large variations > heterogenous cluster

Question 20

Is 3-cluster solution or 4-cluster solution preferred?

Answer 20

3-cluster as it has a smaller RMSSTD

Question 21

What are other rules to determine the number of clusters?

Answer 21

Akaike’s information criterion
Bayesian Information criterion
Average silhouette

Question 22

What is Ward’s linkage metric?

Answer 22

used to minimise the total within-cluster sum of squares.

Question 23

Illustration of agglomerative methods of clustering?

Answer 23

1. Assign each object to one cluster (N objects, N clusters).
2. Calculate the distances (similarities) between all objects. This can be done using different methods of linkage (e.g. Single linkage, complete linkage, average linkage, centroid method, or Ward’s method).
3. Find the closest (most similar) pair of clusters and combine them into one single cluster; therefore, we get one cluster less.
4. Calculate the distances (similarities) between the new cluster and others.
5. Repeat steps 2, 3 and 4 until the moment when all objects are grouped together in one single cluster of size N (n-1 iterations).

Question 24

What is hierarchical clustering using single linkage?

Answer 24

min (10,20) = 10

the minimum distance of all possible combination of objects in the clusters

Question 25

What’s the final outcome of a single linkage?

Answer 25

one big cluster

Question 26

What is hierarchical clustering using complete linkage?

Answer 26

max (10,20) = 20

the maximum distance of all possible combination of objects in the clusters

Question 27

What is hierarchical clustering using centroid linkage?

Answer 27

d (Cluster m, Cluster k)

the distance between the centroids of clusters

Question 28

What is hierarchical clustering using average linkage?

Answer 28

average (10,20) =15

Aka group-average hierarchical clustering

Question 29

Effects of single linkage?

Answer 29

Good for detecting arbitrary-shaped clusters

cannot detect overlapping clusters

Question 30

Effects of complete-linkage?

Answer 30

good for detecting overlapping clusters

not for detecting arbitrary-shaped clusters

Question 31

effects of centroid and average linkage?

Answer 31

somewhere in between single linkage and complete linkage

Question 32

Practical issues of hierarchical clustering?

Answer 32

Works more efficiently with a pre-computed n by n proximity matrix
At least N^2 time and space complexity
> With 1000 records
- need 1 million time units to compute
- need 1 million memory units to store the proximity values