在不知道样本类别时，无监督聚类算法可以将具有相似属性或特征的样本归为相同的类别，常用语数据处理. 本文主要记录几种常见的聚类算法以及Python sklearn 包中的使用.

---

常用聚类算法的几种类别：

• 基于划分的聚类：需要指定初始的类别数，通过不断迭代将样本划分到各个类别中.主要以k-means 为代表
• 基于密度的聚类：由于层次聚类算法和划分式聚类算往往只能发现凸形的聚类簇。为了弥补这一缺陷，发现各种任意形状的聚类簇，开发出基于密度的聚类算法。这类算法认为，在整个样本空间点中，各目标类簇是由一群的稠密样本点组成的，而这些稠密样本点被低密度区域（噪声）分割，而算法的目的就是要过滤低密度区域，发现稠密样本点. 以DBSCAN 为代表.
• 基于层次的聚类：层次聚类主要有两种类型：合并的层次聚类和分裂的层次聚类。前者是一种自底向上的层次聚类算法，从最底层开始，每一次通过合并最相似的聚类来形成上一层次中的聚类，整个当全部数据点都合并到一个聚类的时候停止或者达到某个终止条件而结束，大部分层次聚类都是采用这种方法处理.后者是采用自顶向下的方法，从一个包含全部数据点的聚类开始，然后把根节点分裂为一些子聚类，每个子聚类再递归地继续往下分裂，直到出现只包含一个数据点的单节点聚类出现，即每个聚类中仅包含一个数据点.
• 基于模型的聚类

---

k-means 聚类

又称k均值算法，是最常用的聚类算法，目标检测YOLO系列用此算法进行anchor的生成. 算法流程如下：

• 确定要几个的聚类（cluster，也称簇），并为它们随机初始化一个各自的聚类质心点（cluster centroids。
• 计算每个数据点到质心的距离来进行分类，它跟哪个聚类的质心更近，它就被分类到该聚类。 需要注意的是，初始质心并不是真正的质心，质心应满足聚类里每个点到它的欧式距离平方和最小这个条件。因此根据这些被初步分类完毕的数据点，我们再重新计算每一聚类中所有向量的平均值，并确定出新的质心。
• 最后，重复上述步骤，进行一定次数的迭代，直到质心的位置不再发生太大变化。当然你也可以在第一步时多初始化几次，然后选取一个看起来更合理的点节约时间。

K-means 时间复杂度为O(n), 因为样本数量一般量级很大，类簇K，迭代数被看做常量. 缺点，需要事先指定类别数.

原始 k-measn 算法的初始聚类中心随机选择，k-means ++ 对此进行了改进，随机选择第一个聚类中心，之后选择的第 n + 1 个聚类中心聚类已有的 n 个聚类中心越远越好.

>>> from sklearn.cluster import KMeans
>>> import numpy as np
>>> X = np.array([[1, 2], [1, 4], [1, 0],
...               [10, 2], [10, 4], [10, 0]])
>>> kmeans = KMeans(n_clusters=2, random_state=0).fit(X)
>>> kmeans.labels_
array([1, 1, 1, 0, 0, 0], dtype=int32)
>>> kmeans.predict([[0, 0], [12, 3]])
array([1, 0], dtype=int32)
>>> kmeans.cluster_centers_
array([[10.,  2.],
        [ 1.,  2.]])

DBSCAN

算法流程如下:

• DBSCAN算法会以任何尚未访问过的任意起始数据点为核心点，并对该核心点进行扩充。这时我们给定一个半径/距离ε，任何和核心点的距离小于ε的点都是它的相邻点。
• 如果核心点附近有足够数量的点，则开始聚类，且选中的核心点会成为该聚类的第一个点。如果附近的点不够，那算法会把它标记为噪声（之后这个噪声可能会成为簇中的一部分）。在这两种情形下，选中的点都会被标记为“已访问”。
• 一旦聚类开始，核心点的相邻点，或者说以该点出发的所有密度相连的数据点（注意是密度相连）会被划分进同一聚类。然后我们再把这些新点作为核心点，向周围拓展ε，并把符合条件的点继续纳入这个聚类中
• 重复步骤2和3，直到附近没有可以扩充的数据点为止，即簇的ε邻域内所有点都已被标记为“已访问”。

• 一旦我们完成了这个集群，算法又会开始检索未访问过的点，并发现更多的聚类和噪声。一旦数据检索完毕，每个点都被标记为属于一个聚类或是噪声

  >>> from sklearn.cluster import DBSCAN
  >>> import numpy as np
  >>> X = np.array([[1, 2], [2, 2], [2, 3],
  ...               [8, 7], [8, 8], [25, 80]])
  >>> clustering = DBSCAN(eps=3, min_samples=2).fit(X)
  >>> clustering.labels_
  array([ 0,  0,  0,  1,  1, -1])
  >>> clustering
  DBSCAN(eps=3, min_samples=2)
  

与其他聚类算法相比，DBSCAN有一些很大的优势。首先，它不需要输入要划分的聚类个数。其次，不像mean-shift，即使数据点非常不同，它也会将它们纳入聚类中，DBSCAN能将异常值识别为噪声，这就意味着它可以在需要时输入过滤噪声的参数。第三，它对聚类的形状没有偏倚，可以找到任意大小和形状的簇。

DBSCAN的主要缺点是，当聚类的密度不同时，DBSCAN的性能会不如其他算法。这是因为当密度变化时，用于识别邻近点的距离阈值ε和核心点的设置会随着聚类发生变化。而这在高维数据中会特别明显，因为届时我们会很难估计ε

mean-shift

Mean shift算法，又称均值漂移算法，这是一种基于核密度估计的爬山算法，可用于聚类、图像分割、跟踪等。它的工作原理基于质心，这意味着它的目标是定位每个簇/类的质心，即先算出当前点的偏移均值，将该点移动到此偏移均值，然后以此为新的起始点，继续移动，直到满足最终的条件（找出最密集的区域

算法流程：

• 随机选择一个点作为中心，计算在设置的半径内球形空间内每个样本点到中心点的向量
• 计算整个球形空间内所有向量的平均值，得到一个偏移均值
• 将中心点center移动到偏移均值位置

• 重复上诉步骤直到样本点收敛

  >>> from sklearn.cluster import MeanShift
  >>> import numpy as np
  >>> X = np.array([[1, 1], [2, 1], [1, 0],
  ...               [4, 7], [3, 5], [3, 6]])
  >>> clustering = MeanShift(bandwidth=2).fit(X)
  >>> sklearn.cluster.estimate_bandwidth  估计带宽
  >>> clustering.labels_
  array([1, 1, 1, 0, 0, 0])
  >>> clustering.predict([[0, 0], [5, 5]])
  array([1, 0])
  >>> clustering
  MeanShift(bandwidth=2)
  

对于多类簇的聚类，mean-shift 通过 设置带宽来调节聚类的簇数.

该算法不需要设定聚类的簇数，可处理任意形状的簇类。但聚类结果取决于带宽的设置，带宽设置的太小，收敛太慢，簇类个数过多；带宽设置的太大，一些簇类可能会丢失

GMM

高斯混合模型是基于概率的聚类方法，它是多个高斯分布函数的线性组合，理论上可以拟合出任意类型的分布，通常用于解决同一集合下的数据包含多个不同的分布的情况。如果数据点符合某个高斯分布，那它就会被归类为那个聚类。

算法流程：

• 确定聚类的数量，并随机初始化每个聚类的高斯分布参数
• 根据每个聚类的高斯分布，计算数据点属于特定聚类的概率。如果数据点越接近高斯质心，那它属于该聚类的概率就越高。这很直观，因为对于高斯分布，我们一般假设大部分数据更靠近聚类质心。
• 在这些概率的基础上，为高斯分布计算一组新的参数，使聚类内数据点的概率最大化。我们用数据点位置的加权和来计算这些新参数，其中权重就是数据点属于聚类的概率，高斯分布标准差的变化调整着聚类的形状，以使它能更适合数据点的分布。

• 迭代步骤2和步骤3，直至收敛

  >>> import numpy as np
  >>> from sklearn.mixture import GaussianMixture
  >>> X = np.array([[1, 2], [1, 4], [1, 0], [10, 2], [10, 4], [10, 0]])
  >>> gm = GaussianMixture(n_components=2, random_state=0).fit(X)
  >>> gm.means_
  array([[10.,  2.],
     [ 1.,  2.]])
  >>> gm.predict([[0, 0], [12, 3]])
  array([1, 0])
  

层次聚类 Agglomerative

层次聚类实际上可以被分为两类：自上而下和自下而上。其中自下而上算法会将每个数据点视为单个聚类，然后连续合并（或聚合）成对的聚类，直到所有聚类合并成包含所有数据点的单个聚类， Agglomerative即为自下而上的层次聚类算法.

算法流程：

• 把每个数据点看作是一个聚类，即如果数据集中有X个数据点，它就有X个聚类。然后设置一个阈值作为衡量两个聚类间距离的指标：如果距离小于阈值，则合并；如果距离大于阈值，迭代终止。
• 在每轮迭代中，会把两个聚类合并成一个聚类。可以使用计算所有分属于两个目标聚类的数据点之间距离，然后求一个平均值。每次们会根据设定的阈值选取平均距离最小的两个聚类，然后把它们合并起来，可以认为它们是最相似的。

• 重复步骤2，直到到达树根，即最后只有一个包含所有数据点的聚类。通过这种方式，可以选择要几个聚类，以及什么时候停止聚类。

  >>> from sklearn.cluster import AgglomerativeClustering
  >>> import numpy as np
  >>> X = np.array([[1, 2], [1, 4], [1, 0],
  ...               [4, 2], [4, 4], [4, 0]])
  >>> clustering = AgglomerativeClustering().fit(X)
  >>> clustering
  AgglomerativeClustering()
  >>> clustering.labels_
  array([1, 1, 1, 0, 0, 0])
  

参考文献

• 知乎专栏