聚类算法

Based on partition(基于划分/距离/原型的分类)

这类聚类想要的效果就是类内的点都足够近, 类间的点都足够远.

另外, 这种聚类方法都要指定簇的数量. 然后挑选几个点作为初始中心点, 再然后依据预先定好的启发式算法(heuristic algorithms)对数据点做迭代重置, 最后到达上面的效果.

这里的启发式算法, 主要包括:

• k-means及其变体

  • 变体例如k-medoids, k-modes, K-Medoids, kernel k-means等算法

  • 降低对初始值的敏感度: k-means++, intelligent k-means, genetic k-means

  • 降低对噪声和离群点的敏感度: k-medoids, k-medians

  • 适用于categorical类型数据: k-modes

  • 解决非凸(non-convex)数据/非球形数据: kernel k-means

Partition-based methods聚类多适用于中等体量的数据集, 换句话说, 数据集越大, 越有可能陷入局部最小.

其他的算法包括:

• CLARA

• CLARANS

• AP

• PAM

其中CLARA和PAM都是K-Medoids算法的一种实现, 是降低K-Medoids算法很高的算法复杂度的一种改进.

Based on Hierarchical(基于层次的聚类)

层次聚类有两种方法:

• agglomerative, 自下而上法(bottom-up). 一开始每个个体都是一个类, 然后根据linkage寻找同类, 最后形成一个类

• divisive, 自上而下法(top-down). 一开始所有个体都属于一个类, 然后根据linkage排除异己, 最后每个个体都成为一个类

这两种路径本质上没有孰优孰劣之分, 只是在实际应用的时候要根据数据特点以及想要的类的数量, 来考虑是自上而下更快还是自下而上更快.

根据Linkage判断类的分类/合并方法就是最短距离法, 最长距离法, 中间距离法, 类平均法等(其中类平均法往往被认为是最常用也最好用的方法, 一方面因为其良好的单调性, 另一方面因为其空间扩张/浓缩的程度适中)

层次聚类相关的算法有:

• BIRCH

  • 用于数据体量很大的时候

• ROCK

  • 主要用在categorical的数据类型上

• Chameleon:

  • 用到的linkage是kNN算法, 并以此构建一个graph

  • Chameleon的聚类效果被认为非常强大, 但运算复杂的发很高, $O(n^2)$, 可以处理非常复杂的形状

• CURE

Based on density(基于密度的聚类)

主要是用来解决不规则形状的聚类, 同时也对噪声数据的处理比较好. 一般不需要设置类别的数量, 但一般对参数比较敏感.

密度相关的聚类算法有:

• DBSCAN(Density-Based Spatial Clustering of Applications with Noise)

• OPTICS(Ordering Points To Identify Clustering Structure)

• DENCLUE

• Mean-shift

Based on gird(基于网格的聚类)

原理就是将数据空间划分为网格单元, 将数据对象集映射到网格单元中, 并计算每个单元的密度. 根据预设的阈值判断每个网格单元是否为高密度单元, 由邻近的稠密单元组形成类.

该类方法的优点就是执行效率高, 因为其速度与数据对象的个数无关, 而只依赖于数据空间中每个维上单元的个数, 但缺点也很明显, 比如对参数敏感, 无法处理不规则分布的数据, 维数灾难等.

网格相关的聚类算法有:

• STING(STatistical INformation Grid)

• CLIQUE(CLustering In QUEst)

• Wavecluster

Based on model(基于模型的聚类)

这一类方法主要是指基于概率模型的方法和基于神经网络模型的方法, 尤其以基于概率模型的方法居多, 这里的概率模型主要指概率生成模型.

同一类的数据属于同一种概率分布, 这中方法的优点就是对类的划分不那么HARD, 而是以概率形式表现, 每一类的特征也可以用参数来表达. 但缺点就是执行效率不高, 特别是分布数量很多并且数据量很少的时候.

模型相关的聚类算法有:

• GMM(Gaussian Mixture Models): 高斯混合模型, 最典型, 最常用的方法

• SOM(Self Organized Maps): 一种经典的非监督学习的神经网络

• COBWEB