K-Means算法

• K-Means聚类算法是非监督学习方法。对于样本数据，按样本之间的距离大小，将样本划分为K个簇。让簇内的点之间距离尽可能的小，同时让簇之间的距离尽可能的大。

• 簇划分为$（C_1,C_2,C_3,\dots ,C_k）$

目标函数，最小化平方误差
$$E=\sum _{i=1}^k\sum _{x\in C_i}||x-{\mu }_i|{|}_2^2$$

(11.1)式中，$ \mu_i $是簇$ C_i $的均值向量，即为质心。

$${\mu }_i=\frac{1}{|C_i|}\sum _{x\in C_i}x$$

K-Means算法流程

• input：样本D, 簇个数k, 最大迭代次数T

$$D=x_1,x_2,x_3,\dots ,x_n$$

• output：簇划分

、$$C=（C_1,C_2,C_3,\dots ,C_k）$$

1.从样本$D$中随机选择$k$个样本作为初始的k个质心向量：${\mu }_1，{\mu }_2,{\mu }_3,\dots ,{\mu }_k$,将每个簇初始化为$\varnothing$

2.对于$t=1,2,3,\dots ,T$

（1）对于$i=1,2,3,\dots ,N$，计算样本$x_i$和各个执行向量${\mu }_j,j=1,2,3,\dots ,k$的欧氏距离，将$x_i$划分到最近的簇中，更新Cj=Cj⋃{xi}C_j = C_j \bigcup \{x_i\}Cj​=Cj​⋃{xi​}

（2）对于$j=1,2,3,\dots ,k$，$C_j$中所有的样本点重新计算新的质心

（3）如果所有的$k$个质心向量都没有发生变化，那么跳转到步骤（3）

3.最终输出簇划分

$$C=（C_1,C_2,C_3,\dots ,C_k）$$

评估方法-肘部法则公式

$$SSE=\sum _{i=1}^k\sum _{x\in C_i}||x-{\mu }_i|{|}^2$$

上式中，$C_i$是第$i$簇，$x$是$C_i$中的样本点，${\mu }_i$是$C_i$的质心，即$C_i$所有样本的均值，$SSE$是所有样本的聚类误差。

agglomerative算法

• agglomerative算法有两种实现方式：一种是“自底向上”的Hierarchical；另一种是“自顶向下”的Divisive。

** Hierarchical算法 **

• Hierarchical算法：“自底向上”。首先每个样本点各自为一个类别，然后每一次迭代去距离最近的两个类别将他们合并，最后只有一个类别时，迭代结束。

** 计算距离公式 **

• 最小距离公式（single-linkage）：

$$d_{min}(C_i,C_j)=mindist(p,q)$$

• 上式中，$C_i,C_j$为聚类簇，$p\in C_i,q\in C_j$

• 最大距离公式(complete-linkage)

$$d_{max}(C_i,C_j)=maxdist(p,q)$$

*上式中，$C_i,C_j$为聚类簇，$p\in C_i,q\in C_j$

• 平均距离公式(average-linkage)

$$d_{avg}(C_i,C_j)=\frac{1}{|C_i||C_j|}\sum _{p\in C_i}\sum _{q\in C_j}dist(p,q)$$

• 上式中，$C_i,C_j$为聚类簇，$p\in C_i,q\in C_j$

Hierarchical算法流程

1.将每个样本作为一个簇。

2.计算任意两侧簇之间的距离，选取距离最近的两个簇。

3.将步骤2中的两个簇合并成一个新的簇，删除合并前的那两个簇。

4.重复步骤2、步骤3，直到所有簇仅剩一个簇，迭代结束。

欢迎大家交流学习，任何问题都可以留言