算法01：聚类算法

算法
algorithm

聚类算法，是把一组样本中，把类似的样本聚在一起，不同的样本分开，最终形成几个簇。主要是基于已有数据进行分析，得出结论的过程。常见业务场景包括：基于用户位置信息的商业选址、中文地址标准化处理、用户画像、非人恶意流量识别、广告精准投放、图像分割等众多领域。

距离：在多维空间里，假设两个样本为a(x1, x2, x3 ,x4, … xn)，b(y1, y2, y3, y4, … yn)。那么他们之间的欧式距离（Euclidean distance）的计算公式是

$$d=\sqrt{\sum_{k=1}^n (x_k-y_k)^2}$$

除了欧式距离、还有Mahattan disatnce、Mahalanobis distance等。

K-Means

K-Means是最常用的经典聚类算法。

过程

  1. 在样本中随机选择K个点CM={M0, M1, … Mk}，作为每个类别的初始中心点。K由用户自定义，表示拥护想将样本分为K个簇；
  2. 分别计算所有样本离这K个初始中心点的距离，并分别进行比较，样本离哪个中心点最近，就将其归入那个中心点簇中，从而将所有样本分为K个簇；
  3. 在划分好的K个簇中，分别计算出新的中心点CN={N0, N1, … Nk}，使中心点到该簇中所有样本的距离之和最小；
  4. 判断新获得的中心点CN是否与旧中心点CM一致，如不一致，则将CN赋值给CM，然后回到第2步，重新计算CN并再次比较；如一致则结束，即收敛。

案例

设置K=3，并随机选择3个点，进行第一次聚类

第二次聚类

收敛时

K的选择

K的选择通常有4种方法

  • 按需选择

    根据需求或经验进行选择，例如把客户分为高级VIP、普通VIP、普通用户三类。

  • 观察法

    将样本在坐标系中绘制，并用眼睛观察大致分为几类，这种方式有时会很模糊，而且只能用于低维度数据（1、2、3维），对于高维度数据，需要利用PCA算法降维，然后进行观察。

  • 手肘法

    手肘法是一种间接的观察法，当K-Means算法完成后，我们将得到K个聚类的中心点。计算样本点到它所在的簇的中心点的距离，并求和作为模型的度量，记为D。

    $$D_k=\sum_{i=1}^K\sum_{X\in C_i}||X-M_i||$$

    对于不同的K，最后我们会得到不同的中心点和聚类，所有会有不同的度量。

    我们把上面的例子用不同的K去计算，会得到不同的结果。把K作为横坐标，D作为纵坐标，我们可以得到下面的折线。

    很显然K越大，距离和越小。但是我们注意到K=3是一个拐点，就像是我们的肘部一样，K=1到3下降很快，K=3之后趋于平稳。手肘法认为这个拐点就是最佳的K。

  • Gap Statistics方法

    计算Gap Statisitc，Gap statistic取得最大值所对应的K就是最佳的K，详细内容可以Google。

优点：

  • 逻辑简单，便于实现。

缺点：

  • 较为低效，因为要计算所有的样本到中心的距离；
  • K由用户定义，所以需要对数据由比较深刻的了解；
  • “距离”的选择影响结果。欧式距离计算中，所有属性的权重是相同的，而实际应用时，各属性的权重实际上是有差别的，而不同的权重系数，会导致聚类结果出现较大差异。

应用：

由于K-Means简单易实现，所以经常被用来做pre-clustering，在使用更高级的算法前，先进行初步聚类。

层次聚类

层次聚类算法（Hierarchical clustering）通过分层来实现样本的聚类，包括Agglomerative和Divisive两种策略。Agglomerative初始假设每个样本属于独立的簇，自下而上，通过合并每层中相邻的簇进行汇聚，最终达到所有簇的最高层。Divisive初始假设所有样本属于一个簇，从上到下，通过分离每个簇中比较不相似的样本，直到每个样本都属于不同的簇。

Cluster dissimilarity：为了决定簇的合并（Agglomerative）或分解（Divisive）方式，需要一个指标来衡量两个簇所包含的样本的差异程度。一般来说，这个指标有两个组成部分，一个是Metric，用于衡量两个样本之间的距离，另一个是Linkage，用于衡量两个簇间的差异程度。Metric跟Linkage的选取直接影响最终结果。Metric包括Euclidean distance、Squared Euclidean distance、Mahattan distance、Mahalanobis distance等，Linkage包括Single linkage、Complate linkage、Average linkage等。

过程

  1. Agglomerative是每次将Linkage最小的两个簇合并，直到只剩一个最大的簇为止；
  2. Divisive是每次把一个簇分成两个，使这两个簇的Linkage最大，直到每个簇只剩一个样本为止；
  3. 由于用户需要的结果不会是Agglomerative或Divisive的最终结果，所以用户在过程中何时停下，决定了最终的结果。

案例

如下图是Agglomerative算法的示意图，每次对差异度最小的簇进行合并，直到最终成为一个大簇，用户在Y轴上取一个值，作为终止计算的位置，则此时簇的数量为4。

Divisive算法示意图与Agglomerative类似。

优点

  • 不像K-Means需要用户定义簇的数量。

缺点

  • 没有目标函数，会一直计算直到极端情况出现；
  • 最终的结果取决于用户的主观想法，即何时停止；
  • Cluster dissimilarity中的Metric和Linkage的选择没有统一标准。

应用

查询结果聚类、信息检索

DBSCAN

当样本分布不均匀，形状不规则时，K-Means和层次聚类算法都有可能失效，此时可以采用基于密度的聚类算法DBSCAN。例如下图样本：

过程

  1. 设定扫描半径 Eps, 并规定扫描半径内的密度值。若当前点的半径范围内密度大于等于设定密度值，则设置当前点为核心点；若某点刚好在某核心点的半径边缘上，则设定此点为边界点；若某点既不是核心点又不是边界点，则此点为噪声点。
  2. 删除噪声点。
  3. 将距离在扫描半径内的所有核心点赋予边进行连通。
  4. 每组连通的核心点标记为一个簇。
  5. 将所有边界点指定到与之对应的核心点的簇总

案例

假设扫描半径 Eps 为 1.5，密度阈值 threshold 为 3，可得下图：

通过计算各个点之间的欧式距离及其所在扫描半径内的密度值来判断这些点属于核心点，边界点或是噪声点。因为我们设定了扫描半径为 1.5，密度阈值为 3，所以：

  • P0 点为边界点，因为在以其为中心的扫描半径内只有两个点 P0 和 P1；
  • P1 点为核心点，因为在以其为中心的扫描半径内有四个点 P0, P1, P2, P4 ；
  • P8 为噪声点，因为其既非核心点，也非边界点；
  • 其他点依次类推。

优点

  • 可以对任意形状的稠密数据集进行聚类；（K-Means之类的聚类算法一般只适用于凸数据集）
  • 可以在聚类的同时发现异常点，对数据集中的异常点不敏感;
  • 聚类结果没有偏倚。（K-Means之类的聚类算法初始值对聚类结果有很大影响）

缺点

  • 全局参数难以设定；
  • 难以识别空间簇相互邻接（颈问题）情况下的空间聚类操作。

其他

除了以上三种聚类算法，还有BIRTH、CURE、SOM、FCM等多种聚类算法。

分享到