Ref:
A Youtube Video
Clustering
一般我们的cluster分为Centroid based cluster 和 Density Based Cluster。但John更推荐是将cluster分为 Flat Cluster和Hierarchical Cluster。
| Flat | Hierarchical | |
| Centroid / Parametric | K-manes GMM | Ward Complete-linkage |
| Density / Non-Parametric | DBSCAN Mean Shift | HDBSCAN |
Hierarchical Density Based Clustering
一般有三个问题我们需要解决：
- 如何去估计pdf
- 如何去切一个海平面(how to determine the level set)
- Computational complexity
首先是如何去估计pdf
Locally approxiate the density. 就如同DBSCAN做的一样。我们一般寻找的是同时囊括min_pts个点的最小的半径，来作为一个local density的快速估计。
其次是如何切一个海平面
首先我们来看一张图，如果我们是pure euclidean distance的情况时，我们在一维数据上只需要像hierarchical cluster一样画出以下的这张图就好了，然后纵切一刀就能够确定我们要分的cluster数量。低于某个密度的点都将视为噪声。
但是，我们往往还需要其他的条件，例如我们要一个cluster还要足够的dense。因此，提出了一个新的距离计算方法(Mutual Reachability Distance)：
$$d_{\text{mreach}}(X_i, X_j) = \left\lbrace\begin{align}\max\{\kappa(X_i), \kappa(X_j), d(X_i, X_j)\}\quad &X_i\not=X_j\\0 \quad&X_i = X_j\end{align}\right.$$
其中，$\kappa(X_i)$ 是对于$X_i$这个点最近的$k$个点的距离。这样定义的距离，有利于将原本就很稀疏的point赋予比较大的距离，让他不容易被纳入到一个cluster中间。
Computational cost
时间复杂度是$O(n^2)$。实际上，最花时间的部分是Single linkage computation, which can be reduced to minimal spanning tree computation。直觉上，我们可以考虑类似于prim’s algorithm去计算最小生成树，但我们实际上有$n^2$条边，是个完整的图，对于prim’s algorithm来说，并不是一个有效且快速的情况。因此，我们可以采用Boruvka’s algorithm来计算。
最终的选择：Dual Tree Boruvka for Euclidean Minimum Spanning Trees. Reduced to $n\log(n)$.
而且Mutual Reachability Distance同样适用于这样的计算，因为唯一requirement for this algorithm to work只是triangle inequality holding，他们通过一些技巧和修改，最终设计出了改进版的计算方法。
关于与其他cluster method的对比
