I'll try anything once

人生苦短,何妨一试

k-means聚类算法

使用k-means算法时需要指定分类的数量,这也是k的由来。其是由k-means是Lloyd博士在1957年提出的,kmeans是一种无监督的算法,需要自行去划分

聚类过程

《k-means聚类算法》

  1. 将图中的数据分为3类(k=3)
  2. 首先随机选取三个点进行划分(分类的中心点),并用红绿紫进行标记
  3. 剩余的点根据其到三个中心的距离进行划分,这样便可以分为三类了。
  4. 计算分类好的簇的中心点,便重新选取了三个中心点,之后重复第二步,直到中心点不再变动,或者迭代到设置的阈值。

例子

(Column1) (Column2)
1 2
1 4
2 2
2 3
4 2
4 4
5 1
5 3

随机选取中心点
选取(1,4) (4,2)为两个分类点
计算距离(曼哈顿距离)

与(1,4)的距离 与(4,2)的距离
(1,2) 2 3
(1,4) 0 5
(2,2) 3 2
(2,3) 2 3
(4,2) 5 0
(4,4) 3 2
(5,1) 7 2
(5,3) 5 2

聚类结果为
簇一
(1,2)
(1,4)
(2,3)
簇二
(2,2)
(4,2)
(4,4)
(5,1)
(5,3)
根据平均值再次计算两个簇的当前中心点为(1.33,3), (4,2.4)
继续计算距离

与(1.33,3)的距离 与(4,2.4)的距离
(1,2) 1.33 3.4
(1,4) 1.33 4.6
(2,2) 1.67 2.4
(2,3) 0.67 2.6
(4,2) 3.67 0.4
(4,4) 3.67 1.6
(5,1) 5.67 2.4
(5,3) 3.67 1.6

新的簇为
簇一
(1,2)
(1,4)
(2,2)
(2,3)
簇二
(4,2)
(4,4)
(5,1)
(5,3)
新的中心点为(1.5, 2.75), (4.5, 2.5)
继续计算距离

与(1.5,2.75)的距离 与(4.5,2.5)的距离
(1,2) 1.25 4
(1,4) 1.75 5
(2,2) 1.25 3
(2,3) 0.75 3
(4,2) 3.25 1
(4,4) 3.75 2
(5,1) 5.25 2
(5,3) 3.75 1

新的簇为
簇一
(1,2)
(1,4)
(2.2)
(2,3)
簇二
(4,2)
(4,4)
(5,1)
(5,5)
计算出的中心点与上一次的相同,所以不需要再次重复了,当然在现实的数据中,不可能做到完全没有发生转移,所以可以将其弱化为少于1%的点发生转移,即可停止迭代

局限性

对于k-means算法,其与爬山算法是类似,依赖于初始定下的几个点,其只能最大程度的得到局部的最优解,不能保证是全局最优解。

判断聚类结果的好坏

我们可以使用误差平方和(离散程度)评判聚类结果的好坏,其计算的是每个点到中心点的距离平方和
《k-means聚类算法》

  • 第一个求和是遍历所有的簇,直到第k个簇,如i=1时遍历簇1,i=2时遍历簇2,直到遍历到第k簇。
  • 第二个求和是遍历每个分类里面的所有的点,dist是距离计算公式(曼哈顿、欧拉等)计算对应分类的点与其所对应的簇的中心点的距离平方和。

误差平方和越小效果越好

实现

同样的道理,其对数据也是需要进行标准化的,因为其也是根据特征计算距离的

以下为初始化所需要完成的工作

计算每个点与当前划分的中心点的距离(欧式距离)

根据以上的距离判断所属的簇

将对应的点划分到对应的簇

划分好之后重新计算中心点

kmeans核心

reference

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

3 × 1 =