K-Means聚类算法
概要
聚类算法是一种非监督的算法，简单说“人以类聚，物以群分”，就是将类似的事物归为一类，这里的类似特指距离，也就是距离越近，相似度越大。
相似性或距离的度量
对于样本空间 S，其中任意两个样本X, Y
X = {x_1, x_2, \cdots, x_p} \\
Y = {y_1, y_2, \cdots, y_p}
Y = {y_1, y_2, \cdots, y_p}
- 欧几里得距离
样本之间的距离一本采用欧几里得空间距离，也就是我们常用的距离
d(X, Y) = \sqrt{(x_1 – y_1)^2 + (x_2 – y_2)^2 + \cdots + (x_p – y_p)}
- 曼哈顿距离
主要用于城市两点的距离度量
d(X, Y) = |x_1 – y_1| + |x_2 – y_2| + \cdots + |x_p – y_p|
- 闵可夫斯基距离
d(X, Y) = \sqrt[q]{|x_1 – y_1|^q + |x_2 – y_2|^q + \cdots + |x_p – y_p|^q}
- 余弦距离
用于度量两个文档之间的距离，将文档抽象为两个向量，向量的夹角余弦值作为两个文档的相似度
d(X, Y) = \cos <X, Y> = \frac{X \cdot Y}{||X|| \cdot ||Y|| }
计算流程
- 从N个样本数据中随机选取K个对象作为初始的聚类中心；
- 分别计算每个样本到各个中心的距离，将对象归为距离最近的中心；
- 所有对象计算完毕之后，得到总的距离平方和；
- 重新计算K个聚类中心，得到的总的距离平方和与上一次比较，如果大于上一次的，则转为步骤5，否则转为步骤2
- 当聚类中心不发生改变时，输出聚类结果
误差的计算
选择距离的平方和作为误差函数SSE，选择当SSE最小情况下的聚类
SSE = \sum _{i=1} ^ {K} \sum_{x \in E_i} d(e_i, x) ^ 2
其中簇E_i的聚类中心e_i为:
e_i = \frac{1}{n} \sum _{x \in E_i} x
| 符号 | 含义 |
|---|---|
| K | 聚类簇的个数 |
| e_i | 簇E_i的中心 |
| E_i | 第i个簇 |
| x | 样本 |
| n_i | 第i个簇样本的个数 |