# 聚类算法选择速查表

其中涉及到算法复杂度的计算时, $$n$$表示样本数量, $$m$$表示特征维度, $$k$$表示设定的簇的数量, $$t$$表示迭代次数.

| 模型名称                | 数据类型 | 算法效率                 | 聚类形状 | 适用于高维 | 适用于大数据 | 噪声敏感 | 能否识别异常点 | 能否自动得到类别数 | 应用场景                                  | Python API                                                                                                                                                                                                                                                                                |
| ------------------- | ---- | -------------------- | ---- | ----- | ------ | ---- | ------- | --------- | ------------------------------------- | ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
| **Partition based** |      |                      |      |       |        |      |         |           |                                       |                                                                                                                                                                                                                                                                                           |
| K-Means             | 数值型  | 高效,$$O(kmnt)$$       | 球形   | 是     | 是      | 敏感   | 否       | 否         | 大数据量, 球形, 噪声小, 没有异常点                  | [sklearn.cluster.KMeans](https://scikit-learn.org/stable/modules/generated/sklearn.cluster.KMeans.html#sklearn.cluster.KMeans), [sklearn.cluster.MiniBatchKMeans](https://scikit-learn.org/stable/modules/generated/sklearn.cluster.MiniBatchKMeans.html#sklearn.cluster.MiniBatchKMeans) |
| K-Medoids           | 数值型  | 低效,$$O(k(n-k)^2)$$   | 球形   | 否     | 否      | 不敏感  | 否       | 否         | 小数据集, 特别适合有噪声和极端值的情况                  | [pyclust](https://pypi.org/project/pyclust/0.1.3/)                                                                                                                                                                                                                                        |
| PAM                 | 数值型  | 低效                   | 球形   | 否     | 否      | 不敏感  | 否       | 否         | K-Medoids算法的变种                        | [pyclust](https://pypi.org/project/pyclust/0.1.3/)                                                                                                                                                                                                                                        |
| CLARA               | 数值型  | 中                    | 球形   | 否     | 是      | 不敏感  | 否       | 否         | K-Medoids算法的变种                        | [pyclust](https://pypi.org/project/pyclust/0.1.3/)                                                                                                                                                                                                                                        |
| AP                  | 数值型  | 低效,$$O(n^2\log{n})$$ | 球形   | 否     | 否      | 不敏感  | 否       | 是         | 小数据集, 球形数据                            | [sklearn.cluster.AffinityPropagation](https://scikit-learn.org/stable/modules/generated/sklearn.cluster.AffinityPropagation.html#sklearn.cluster.AffinityPropagation)                                                                                                                     |
| **Hierarchy based** |      |                      |      |       |        |      |         |           |                                       |                                                                                                                                                                                                                                                                                           |
| agglomerative       | 数值型  | 低效                   | 任意形状 | 否     | 否      | 是    | 否       | 否         | 小数据集, 精准聚类; 不同的linkage方法使算法的表现有根本性的变化 | [AgglomerativeClustering](https://scikit-learn.org/stable/modules/generated/), [scipy.cluster.hierarchy.fclusterdata](https://docs.scipy.org/doc/scipy/reference/generated/scipy.cluster.hierarchy.fclusterdata.html#scipy.cluster.hierarchy.fclusterdata)                                |
| BIRCH               | 数值型  | 高效,$$O(n)$$          | 球形   | 否     | 是      | 否    | 是       | 否         | 大数据量, 低位; 有多种应用情景, 查阅Birch文档          | [sklearn.cluster.Birch](https://scikit-learn.org/stable/modules/generated/sklearn.cluster.Birch.html#sklearn.cluster.Birch)                                                                                                                                                               |
| CURE                | 数值型  | 高效,$$O(s^2\log{s})$$ | 任意形状 | 是     | 是      | 否    | 否       | 否         | 大数据量, 任意形状                            | [pyclustering.cluster.cure.cure](https://codedocs.xyz/annoviko/pyclustering/classpyclustering_1_1cluster_1_1cure_1_1cure.html)                                                                                                                                                            |