聚类算法（上）

前言

聚类算法很多，所以和讲回归算法一样，分成了上下，上中主要讲了传统的 K-Means 算法以及其相应的优化算法入 K-Means++，K-Means|| 和 Canopy 等。下中主要讲了另外两种的思路的聚类算法，即层次聚类和密度聚类。

什么是聚类

聚类算就是怼大量未知标注的数据集，按照数据内部存在的数据特征将数据集划分为多个不同的类别，使类别内的数据比较相似，类别之间的数据相似度比较小，属于无监督学习。

从定义就可以看出，聚类算法的关键在于计算样本之间的相似度，也称为样本间的距离。

相似度/距离计算公式

说到聚类算法，那肯定核心就是计算距离的公式了，目前常用的有以下几种。 闵可夫斯基距离（Minkowski）：公式2.1

当 p 为1的时候是曼哈顿距离（Manhattan）：公式2.2
当 p 为2的时候是欧式距离（Euclidean）：公式2.3
- 标准化欧式距离：这个距离的计算方式如同其字面意思，标准化欧式距离就是对欧式距离的标准化。标准化的正常定义为，$X^* = \frac{X - \overline X}{s}$，这个$s$指的就是方差，而方差的计算公式为$s = \sqrt{\frac{\sum_{i=1}^n(x_i - \overline X)^2}{n}}$，所以其标准化公式如下公式2.5。
当p为无穷大的以后是切比雪夫距离（Chebyshev）：公式2.4

\[dist(X,Y)= \sqrt[p]{\sum_{i=1}^{n} |x_i - y_i|^p}\ \ \ 公式2.1\] \[M_{dist}=\sum_{i=1}^n|x_i-y_i| \ \ \ 公式2.2\] \[E_{dist} = \sqrt{\sum_{i=1}^n|x_i-y_i|^2} \ \ \ 公式2.3\] \[C_{dist} = max_i(|x_i-y_i|)\ \ \ 公式2.4\] \[S\_E\_D = \sqrt{\sum_{i=1}^n(\frac{x_i-y_i}{s_i})^2}\ \ \ 公式2.5\]

夹角余弦相似度（Cosine）：

使用这个公式的时候，需要注意的是，这里的相似之的是同一个方向上的，而同一个方向上的两个点可能距离是非常远的。比如一个文章中分别出现单词A 10次，单词B 20次，另一个文章中出现单词A 100次，单词B 200次，这时候如果使用欧几里得距离的话，这两个文章是不相似的，然而显然这两个单词的比例相似很能说明这两个文章其实是有关系的，所以在文章的相似度的判别中使用夹角余弦相似度比较合适，如下公式2.6。

注：夹角余弦相似度是从距离以外的衡量相似度的另一个维度的指标

\[\cos(\theta) = \frac{\sum_{k=1}^n x_{1k}x_{2k}}{\sqrt{\sum_{k=1}^n x_{1k}^2} * \sqrt{\sum_{k=1}^n x_{2k}^2}} = \frac{a^T · b}{|a||b|}\ \ \ 公式2.6\]

KL距离（相对熵）：思考下条件熵的定义，简单的来说就是在放生一件事情的时候，发生另一件事的概率。公式如下公式 2.7.

注：这里说的概率不是实指概率，而是熵表达的含义。这个公式其实就是条件熵的公式。 $D(P|Q)=\sum_x P(x)\log(\frac{P(x)}{Q(x)})\ \ \ 公式2.7$

杰卡德相似系数(Jaccard)：

这个很好理解，它的核心就是使用两个集合的交集和并集的比率来代表两者的相似度，也就是说重合的越多越相似。公式如下，公式2.8.

\[J(A,B) = \frac{|A\bigcap B|}{|A \bigcup B|}\] \[dist(A,B) = 1-J(A,B) \ \ \ 公式2.8\]

Pearson相关系数：

这个就是考研数学中的相关系数，表达就是两者之间的相关性，所以直接拿来用就好了，公式如下公式 2.9。

\[\rho_{XY} = \frac{Cov(X,Y)}{\sqrt{D(X)} \sqrt{D(Y)}} = \frac{E[(X-E(X))(Y-E(Y))]}{\sqrt{D(X)}\sqrt{D(Y)}} = \frac{\sum_{i=1}^n(X_i - \mu_x)(Y_i - \mu_Y)}{\sqrt{\sum_{i=1}^n(X_i - \mu_X)^2}*\sqrt{\sum_{i=1}^n(Y_i - \mu_Y)^2}}\] \[dist(X,Y) = 1 - \rho_{XY}\ \ \ 公式2.9\]

聚类的思想

给定一个有 M 个对象的数据集，构建一个具有 k 个簇的模型，其中 k <= M。满足以下条件:

每个簇至少包含一个对象
每个对象属于且仅属于一个簇
将满足上述条件的k个簇成为一个合理的聚类划分

基本思想:

对于给定的类别数目k，首先给定初始划分，通过迭代改变样本和簇的隶属关系，使的每次处理后得到的划分方式比上一次的好，即总的数据集之间的距离和变小了

K-Means 系列

K-Means 算法

K-means的核心算法如下：

# 假设输入样本 T 为 x1,x2,x3,...,xm

初始化k个类别的中心点 a1,a2,a3,...,ak
while not EndCondition :
	1.根据每个样本和中心点的欧几里得距离，选择最近的中心点作为自己的类别
	2.更新每个类别的中心点 aj，为隶属该类别的所有的样本的均值

# EndCondition 有迭代次数，最小平方误差 MSE，簇中心点变化率。

在循环中的第二步，我们移动了中心点的位置，把中心点移到了隶属于该中心点类别的所有样本的中间，并使用样本的均值作为位置。这样子看似是拍脑袋想的移动策略，其实是可以推导出来的。正如聚类算法思想所指出的，我们要让所有的点到自己的分类的中心点的欧几里得距离最小，所以我们设置目标函数为公式 4.1，公式中的 1/2 是为了之后求导运算方便。我们为了让目标函数尽可能的小，所以使用了之前一直在使用的思考方式，对其使用梯度下降算法，求导后得到公式 4.2，之后令其等于 0，就得到了公式 4.3。

\[\mathop{\arg\min}_{S} \frac{1}{2}\sum_{i=1}^k\sum_{x\in S_i} ||x - a_i||^2\ \ \ 公式4.1\] \[\frac{\partial J}{\partial a_i} = \sum_{i=1}^{N_i}(x_i-a_i)\ \ \ 公式4.2\] \[a_j = \frac{1}{N_i}\sum_{i=1}^{N_i} x_i \ \ \ 公式4.3\]

注：其中 $S_i$ 为第 i 个簇的集合，对应的簇中元素的个数为 $N_i$

最后，这个看似不错的算法，其实有着不小的缺点，那就是初值敏感。我们来仔细想一想，如果两个不小心随机生成的初值落到了一个类别中，两者的距离还特别近，这中情况下就很难正确分类了。除此之外，由于移动策略中使用的是均值，也就是说如果集合中含有非常大的误差点的话，这样子会是中心点的设置偏离正确点很远，所以很多时候我们改用中值来更新中心点，这就是我们说的K-Mediods聚类，即K中值聚类。

K-means算法总结

优点：

理解容易，聚类效果不错
- 处理大数据集的时候，该算法可以保证较好的伸缩性和高效率
- 当簇近似高斯分布的时候，效果非常不错

缺点：

K值是用户给定的，在进行数据处理前，K值是未知的，不同的K值得到的结果也不一样
对初始簇中心点是敏感的
不适合发现非凸形状的簇或者大小差别较大的簇
特殊值(离群值)对模型的影响比较大

二分 K-Means 算法

和之前线性回归算法的进化一样，针对 K-Means 对初始中心点非常敏感这一缺点，就引入了二分 K-Means 算法，其尝试通过二分法弱化初始中心点。这种算法的具体步骤如下：

# 把所有样本数据作为一个簇放到队列中
while not EndCondition:
	1.从队列中选择一个簇，使用 K-means 划分为两个簇
	2.将划分好的两个簇放回队列
# EndCondition 为簇的数量，最小平方误差，迭代次数等
# 选择簇的手段有两种1.使用SSE 2.选择数据量最多的簇

我们在这个算法中提到了 SSE，这个可以是簇内所有样本点，到其中心点的距离的总和，代表着簇内的点是不是高度相关。计算公式如下公式4.4。

\[SSE = \sum_{i=1}^n (y_i - \hat y_i)^2\ \ \ 公式4.4\]

可以看出在这种算法下，很好的避开了，两个中心点都在一起的情况。

K-Means++ 和 K-Means||

K-Means++ 做的改善，是直接对初始点的生成位置的选择进行优化的，他的初始点生成策略如下：

从数据集中任选一个节点作为第一个聚类中心
对数据集中的每个点 x，计算 x 到所有已有聚类中心点的距离和 $D(x)$ ，基于 $D(x)$ 采用线性概率选择出下一个聚类中心点(距离较远的一个点成为新增的一个聚类中心点)
重复步骤2直到找到 k 个聚类中心点可以看出，K-Means++ 企图生成相聚距离较远的几个中心点。但是缺点也是显而易见的，由于聚类中心点选择过程中的内在有序性，在扩展方面存在着性能方面的问题，即第k个聚类中心点的选择依赖前k-1个聚类中心点的值。

而 K-Means|| 就是针对 K-Means++ 缺点作出了的优化，主要思路是改变每次遍历时候的取样规则，并非按照 K-Means++ 算法每次遍历只获取一个样本，而是每次获取 K 个样本，重复该取样操作 $O(\log{n})$ 次，然后再将这些抽样出来的样本聚类出 K 个点，最后使用这 K 个点作为 K-Means 算法的初始聚簇中心点。

注：一般 5 次重复采用就可以保证一个比较好的聚簇中心点。

Canopy算法

Canopy 属于一种“粗略地”聚类算法，简单的来说就是，不那么追求自动获得最优解，而是引入了一种人为规定的先验值进行聚类，具体步骤如下：

# 给定样本列表 L=x1,x,2...,xm 以及先验值r1和r2(r1 > r2)
for P in L:
	计算P到所有聚簇中心点的距离(如果不存在聚簇中心，那么此时点P形成一个新的聚簇)，并选择出最小距离D(P,aj)
	if D < r1:
		# 表示该节点属于该聚簇
		添加到该聚簇列表中
	if D < r2:
		# 表示该节点不仅仅属于该聚簇，还表示和当前聚簇中心点非常近，
		将该聚簇的中心点设置为P，并将P从列表L中删除
	if D > r1:
		节点P形成一个新的聚簇
	if EndCondition:
		# 结束条件为直到列表L中的元素数据不再有变化或者元素数量为0的时候
		break		

注：Canopy 算法得到的最终结果的值，聚簇之间是可能存在重叠的，但是不会存在某个对象不属于任何聚簇的情况

显然，这种算法虽然快，但是很难生成满足我们应用的模型，所以通常我们将它作为解决 K-Means 初值敏感的方案，他们合在一起就是 Canopy + K-Means 算法。顺序就是先使用 Canopy 算法获得 K 个聚类中心，然后用这K个聚类中心作为 K-Means 算法。这样子就很好的解决了 K-Means初值敏感的问题。

Mini Batch K-Means算法

Mini Batch K-Means 算法是 K-Means 算法的一种优化变种，采用小规模的数据子集，来减少计算时间。其中采用小规模的数据子集指的是每次训练使用的数据集是在训练算法的时候随机抽取的数据子集。Mini Batch K-Means 算法可以减少 K-Means 算法的收敛时间，而且产生的结果效果只是略差于标准 K-Means 算法。它的算法步骤如下：

# 首先抽取部分数据集，使用K-Means算法构建出K个聚簇点的模型
while not EndCondition:
	1.抽取训练数据集中的部分数据集样本数据，并将其添加到模型中，分配给距离最近的聚簇中心点
	2.更新聚簇的中心点值
# EndCondtion同K-Means一样，可以理解为不停的进行K-Means算法。

聚类算法衡量标准

聚类算法的衡量标准有很多，包括均一性、完整性、V-measure、调整兰德系数（ARI ，Adjusted Rnd Index）、调整互信息(AMI，Adjusted Mutual Information)以及轮廓系数等等。

均一性、完整性以及 V-measure

均一性：一个簇中只包含一个类别的样本，则满足均一性。其实也可以认为就是正确率，即每个聚簇中正确分类的样本数占该聚簇总样本数的比例和。其公式如下公式5.1。

\[p = \frac{1}{k}\sum_{i=1}^k \frac{N(C_i == K_i)}{N(K_i)}\ \ \ 公式5.1\]

完整性：同类别样本被归类到相同簇中，则满足完整性。每个聚簇中正确分类的样本数占该类型的总样本数比例的和，通俗的来说就是，我们已分类类别中，分类正确的个数。其公式如下，公式5.2：

\[r = \frac{1}{k}\sum_{i=1}^k \frac{N(C_i == K_i)}{N(C_i)}\ \ \ 公式5.2\]

在实际的情况中，均一性和完整性是往往不能兼得的，就好像抓特务时的矛盾一样，到底是保证每个抓的人都是特务，还是宁可错抓也不放过一个特务，之间的取舍很难把握。所以再一次贯彻，鱼和熊掌不可兼得，我们就加权，于是得到的就是V-measure，其公式如下公式5.3：

\[V_\beta = \frac{(1+\beta^2)·pr}{\beta^2·p + r}\ \ \ 公式5.3\]

调整蓝德系数ARI

兰德系数（RI，Rand index），我用中文看了不少讲兰德系数的博客，其中的文字说明几乎都是相同的，对个人的理解帮助不是特别大，于是用英文查的。最终理解了这个系数的参数的意思，想看英文说明的，个人觉得还挺好懂的参考这里。以下是我个人的讲解。

首先，将原数据集中的元素进行两两配对形成一个新的数据集，我们称之为S数据集。这时候，我们将原数据集，根据两种不同的策略分别划分成 r 份和 s 份，并对这两个数据集命名为 X 和 Y。在这里我们可以看出，X 和 Y 的元素是相同的，只是他们的划分方式不同。

接下来我们来思考，S 数据集中，每个元素中的两个样本，在 X 和 Y 中只有两种可能，就是两个样本都在一个子集中，或者不在一个子集中，那么对于 S 中的一个元素，只有四种可能性。

两个样本都在 X 的一个子集中，也同时在 Y 的一个子集中，这些元素的个数是a
两个样本横跨 X 的不同子集，也同时在 Y 中横跨Y的不同子集，这些元素的个数是b
两个样本都在 X 的一个子集中，但在 Y 中横跨 Y 的不同子集，同理数量为c
两个样本横跨 X 的不同子集，但在 Y 的一个子集中，同理数量为d 有了上述的理解，我们再看蓝得系数公式，公式5.4，我们就不难理解了。RI的取值在$[0,1]$之间，越靠近1代表越相似。

\[RI = \frac{a+b}{a+b+c+d} = \frac{a+b}{C_2^n} \ \ \ 公式5.4\]

接下来引入，调整兰德系数(ARI，Adjusted Rnd Index)，ARI取值范围$[-1,1]$，值越大，表示聚类结果和真实情况越吻合。从广义的角度来将，ARI是衡量两个数据分布的吻合程度的，公式5.5如下：

\[ARI = \frac{RI - E[RI]}{max(RI) - E[RI]}\ \ \ 公式5.5\]

调整互信息(AMI，Adjusted Mutual Information)

调整互信息，整体的流程很像ARI，AMI则是对MI进行调整。而MI是使用信息熵来描述的。那么互信息表示了什么呢，首先先看下维基百科的定义：

独立的(H(X),H(Y)), 联合的(H(X,Y)), 以及一对带有互信息 I(X; Y) 的相互关联的子系统 X,Y 的条件熵。在概率论和信息论中，两个随机变量的互信息（Mutual Information，简称MI）或转移信息（transinformation）是变量间相互依赖性的量度。不同于相关系数，互信息并不局限于实值随机变量，它更加一般且决定着联合分布p(X,Y) 和分解的边缘分布的乘积 p(X)p(Y) 的相似程度。互信息是点间互信息（PMI）的期望值。互信息最常用的单位是bit。简单的来说，这个公式代表着两个子系统 X 和 Y 的相似度，但是这里的相似度是从信息熵的角度出发的，它越大代表着两者的差异越大，其计算公式以及相关的公式如下公式5.6，公式5.7所示。

\[MI(X;Y) = \sum_{y \in Y}\sum_{x \in X}p(x,y)\log{\frac{p(x,y)}{p(x)p(y)}}\ \ \ 公式5.6\] \[\begin{split} MI(X;Y) &= H(X) - H(X|Y)\\ &=H(Y) - H(Y|X)\\ &=H(X) + H(Y) - H(X,Y)\\ &=H(X,Y) - H(X|Y) - H(Y|X) \ \ \ 公式5.7 \end{split}\]

轮廓系数

之前我们说到的衡量指标都是有标签的，这里的轮廓系数则是不包含标签的评价指标。

簇内不相似度： 计算样本i到同簇其它样本的平均距离为$a_i$ 。$a_i$越小，表示样本$i$越应该被聚类到该簇，而簇C中的所有样本的$a_i$的均值被称为簇C的簇不相似度。
簇间不相似度：

计算样本i到其它簇$C_j$ 的所有样本的平均距离bij， $b_i=min({b_{i1},b_{i2},…,b_{ik}}) ，$b_i$ 越大，表示该样本$i$越不属于其它簇。
轮廓系数：

$s_i$值越接近1表示样本i聚类越合理，越接近-1，表示样本i应该分类到另外的簇中，近似为0，表示样本i应该在边界上。所有样本的si的均值被成为聚类结果的轮廓系数。
\[s_i = \frac{b_i - a_i}{max\{a_i,b_i\}}\]