Week 4: Clustering

Question 1

Clustering

Answer 1

Can overlapping or non-overlapping regions. Generally clusters are made by finding groupings of instances that have small intra-cluster distances and larger inter-cluster distances.

Question 2

Dendrogram

Answer 2

Represents a hierarchy of clusters.

Question 3

K-Means Clustering

Answer 3

Instances are assigned to the closest centroid, with centroid recomputed using the averages of all the members in its cluster.

Question 4

Density

Answer 4

The density of a data point x is the number of data points within a specified radius Eps, including x

Question 5

Categorisation of Data Points

Answer 5

Core Point: It must have a density above the threshold MinPts.
Border Point: It’s not a core point, but within the neighbourhood of a core point.
Noise Point: It’s neither a core point nor a border point.

Question 6

DBSCAN Algorithm

Answer 6

It’s a density-based clustering algorithm. Identifies high density regions separate by low density regions between them. It ignore noise points.

Finding the optimal Eps and MinPts is a key issue. Can use the elbow rule when plotting i-th nearest neighbour distance against points sorted by distance to i-th nearest neighbour.

Question 7

Graph-based Algorithm

Answer 7

Given a dataset, construct a proximity matrix and sparse graph (proximity matrix and sparse graph are built together iteratively), and partition the graph, with the partitions becoming clusters.

Question 8

Sparsification

Answer 8

After clustering the nodes, filter out the edges so that the structure is accentuated in the sparsified graph.

Question 9

Graph Partitioning

Answer 9

Graph cutting algorithms can be utilised, with the goal of finding a subset of edges whose deletion cuts a graph into k-connected components, with the weights of the connecting nodes minimised (minimum k-cut).

Question 10

Incremental Clustering

Answer 10

It approaches each cluster instance 1-by-1 in an online manner without needing simultaneous access to all instances.

Main points:
1. At each stage, the overall clustering forms a tree.
2. The root node represents the entire dataset.
3. Leaves correspond to instances
4. Nodes with the same parent form a cluster.

Steps:
1. Initialise a tree containing only the root node.
2. With the addition of a new instances, either a leaf for the new instance is added, or the tree is restructured by merging/splitting two nodes. Decisions are made based on the category utility metric, which measure the overall quality of a partition of instances into clusters.

Question 11

Fuzzy Cluster

Answer 11

Clusters whose elements have degrees of membership.

Question 12

Distance Metrics

Answer 12

3 Main Types:

1. Distance between the values of 2 different instances with respect to an individual attribute.
2. Distance between two difference instances which aggregates all attributes.
3. Distance between two different clusters which aggregates all instances.

Question 13

Cluster Centroid for Numerical Data

Answer 13

Calculate the arithmetic mean for each attribute using all cluster points.

Question 14

Cluster Medoid for Nominal Data

Answer 14

The most representative point for a cluster.

Question 15

Cluster Diameter

Answer 15

The largest distance between any two points in a cluster.

Question 16

Single-Link/Single Linkage

Answer 16

The minimum distance between any two points in the two different clusters.

Question 17

Complete-Link/Complete-Linkage

Answer 17

The maximum distance between any two points in the two different clusters.

Question 18

Average-Link/Average-Linkage/Group Average

Answer 18

The average distance among all pairs of instances in the two clusters.

Question 19

Centroid-Link/Centroid-Linkage

Answer 19

The distance of the two centroids of the two clusters.

Question 20

Within Cluster Score

Answer 20

The measure of cluster compactness, which is sum of square of the distance between a point and its cluster centroid.

Question 21

Between Cluster Score

Answer 21

Measure of cluster separation, which is sum of the square of the distances between each pair of centroids.

Question 22

Calinski-Harabaz Index

Answer 22

Based on the sum of squared distances of the points to their closest centroids. High for when the clusters are well separated and dense.

(\frac{BC}{WC}) \times (\frac{n-K}{K-1})

n = number of instances
K = number of clusters
BC = between cluster sum of squared distances
WC = within cluster sum of squared distances

Question 23

Silhouette Coefficient

Answer 23

s_i = \frac{b_i - a_i}{\max \left{a_i, b_i \right}}

s_i = 1, for dense and well-separated clusters
s_i = 0, for overlapping cluster
s_i = -1, for incorrect clustering

a_i = \frac{1}{m_k - 1} \sum_{i^{‘} C_k \ \left{i\right}} d(\boldsymbol{x}i, \boldsymbol{x}{i^{‘}})

a_i is the mean distance between \boldsymbol{x}_i and all other data points in the same cluster C_k

b_i = \frac{1}{m_{k^{‘}}} \sum_{i^{‘} \in c_{k^{‘}}} d(\boldsymbol{x}i, \boldsymbol{x}{i^{‘}})

B_i is the mean distance between an instance an all other points in the nearest cluster C_{k^{‘}}

Question 24

Minimum Description Length (MDL)

Answer 24

The best model is the simplest. The fewer bits it takes to encode the model, the better. We want to maximise the posterior probability Pr(h \mid D), i.e. the chance that the model h is correct given the set of examples D.

Question 25

Outlier/Anomaly Detection

Answer 25

In supervised learning, human experts can do this manually via classification.

In semi-supervised learning, collecting data with outliers is more difficult. But normal instances are more easily attainable.

In unsupervised learning, there needs to be assumptions for defining when a data point is far from other data.

Question 26

Model-Based Outlier

Answer 26

An observation that differs so much from other observations to arouse suspicion that it has been generated by a different mechanism.

Question 27

Proximity-Based Outlier

Answer 27

Object that have very high distance from its k-nearest neighbour: O = \left{\boldsymbol{x}_i : d_k(\boldsymbol{x}) \ge T, 1 \le I \le n \right}

Question 28

Density

Answer 28

The inverse of the average distance to the k-nearest neighbors.

\delta_k (\boldsymbol{x}) = \left( \frac{1}{\left\lvert N_k(\boldsymbol{x}) \right\vert} \sum_{\boldsymbol{x}^{‘} \in N_k(\boldsymbol{x})} d(\boldsymbol{x}, \boldsymbol{x}^{‘}) \right)^{-1}

Question 29

Relative Density

Answer 29

This helps find outliers even when density differs across different regions.

r_k(\boldsymbol{x}) = \frac{\delta_k(\boldsymbol{x})}{\frac{1}{\left\lvert N_k (\boldsymbol{x}) \right\rvert}\sum_{\boldsymbol{x}^{‘} \in N_k(\boldsymbol{x})} \delta_k(\boldsymbol{x}^{‘})}

Question 30

Cluster-Based Outlier

Answer 30

An object that doesn’t strongly belong to any cluster.

Question 31

Probabilistic Outlier

Answer 31

An object that has low probability with respect to a probabilistic model of the data.