Clustering comparison

k-Means

The k-Means Algorithm is based on the method of least squares and optimizes \[ F = \sum_{i=1}^{k}\sum_{x_{j} \in S_{i}}\left \| x_{j} - \mu_{i} \right \|^{2} \] where \(x_i\) are data points, \(\mu_i\) are Centroids or Means and \(S_i\) are corresponding clusters.
The Algorithm has three steps.

1. Initialisation
Choose \(k\) Centroids (also called Means)
\( m_1^{(0)},\cdots,m_k^{(0)} \)

2. Assign Points
Each data Point is assigned to the "nearest" cluster (cluster variance is increased the least).
\( S_i^{\left( t \right)} = \left\{ x_j : \left\| x_j - m_{i}^{\left( t \right)} \right\|^2 \leq \left\| x_j - m_{i^*}^{\left( t \right)} \right\|^2 \text{ for all } i^*=1,\cdots,k \right\} \)

3. Update Centroids
Recalculate the new cluster means.
\( m_i^{\left( t+1 \right)} = \frac{1}{\left| S_{i}^{\left( t \right)} \right|} \sum_{x_j \in S_{i}^{\left( t \right)}} x_j \)

Repeat steps 2 and 3 until the centroids don't change anymore.

DBSCAN

In DBSCAN there are three different kinds of points:

• core points which are dense themselfs
• density-reachable points that are reachable from core points but are not dense themselfs
• outliers or noise points

The DBSCAN method has two parameters ε and minPts, where ε is the maximum neigborhood radius and minPts is the minimum number of neighbors to be a core point.

From one point another point is reachable if their distance is smaller than ε. A Point is dense (=core point) if it has at least minPts in its ε-reachable neighborhood.

Density-reachable points are reachable from core points but are not themselfs dense.

All reachable points around at least one core point form a cluster. Other points are outliers.

Algorithm

1. Start with arbitrary, not yet visited point
2. Get the point's ε-neighborhood
3. If the point is dense, start a cluster
4. If not, the point is labeled as noise (it can get part of a cluster later)
5. Get the ε-neighborhood of all unvisited points in the cluster and add them to the cluster
6. Again add the ε-neighborhood of the neighbors to the cluster if the neighbor is dense itself
7. Continue until the density-connected cluster is completely found
8. Start with a new unvisited point
9. Continue until all points are either part of a cluster or labeled as noise

Advantages of DBSCAN over k-Means

• DBSCAN does not require a priori knowled about the number of classes
• DBSCAN can separate arbitrarily shaped and non-linearly separable clusters
• DBSCAN is robust against noise

Disadvantages of DBSCAN

• One has to understand the data to choose meaningful parameters
• DBSCAN has difficulties at clustering datasets with large differences in densities
• DBSCAN is not entirely deterministic (Assignment of points reachable from more than one cluster is dependant on the processing order)