标签:
杂谈 |
文本聚类—k-means
1
算法介绍
K-means是一个聚类算法,通过这个算法可以将给定的数据集切分为K个集合(K事先指定),同时保证任何一个元素到其所属类中心的的距离都小于这个元素到其他类中心的距离。用数学化的语言可以这样描述
算法过程可以描述如下:
1.
2.
3.
2
通俗理解
下面介绍一个通俗点的理解。
在平面上有9个点,标号从A-I。坐标见下图红点。
如果利用k-means算法来进行聚类,假设初始化的中心点选择了3个 E,B,H点。那么下一步可以计算所有点到这三个点的距离,然后将距离最小的中心作为点的新的中心,结果如下:
点 |
A |
B |
C |
D |
E |
F |
G |
H |
I |
J |
最近中心 |
H |
B |
B |
B |
E |
E |
E |
H |
H |
B |
根据第一步得到的结果可以中心计算出点的新的中心K(3,2),M(9.33,2),N(7.75,6)
将新的点画出来如下图黑点

重新计算各个点到新的中心的距离,记录下最小的中心如下
点 |
A |
B |
C |
D |
E |
F |
G |
H |
I |
J |
最近中心 |
H |
B |
B |
B |
E |
E |
E |
H |
H |
B |
发现,第二次迭代得到的中心和第一次并没有变化(这里只是一个巧合而已)。 这时算法停止。那么平面上所有的点的聚类就已经完成。 三个类别为(A,H,I),(E,F,G),(B,C,D,J)。
为了更加形象的理解,可以以各个聚类中心为圆心,最远的点到中心的距离为半径中心画圆,然后再进行观察

这样就能很好的理解一开始给出的数学定义了。
3
算法实现
实现代码:https://github.com/zengkui/machine-learning/blob/master/k-means/kmeans.py
本代码的测试数据是从搜狗实验室下载,选择了商务,数码产品,体育,娱乐4类文档。在代码实现的时候,对算法做了一些小的修改。
1.
2.
3.
4
算法评估
实验中用户聚类的文本总数为4037个。对于不同的距离算法结果如下:
距离函数 |
正确率 |
收敛所需迭代次数 |
欧式距离 |
84.4 |
6 |
余弦距离 |
90.6% |
14 |
5
算法复杂度
假设需要聚类的样本有N个,聚类结果有K个,特征个数为F,那么在每一轮中需要计算每个样本和每个中心的距离 需要消耗 K*N*F,所以总的复杂度应该还要乘以一个迭代次数M. 这个算法的复杂度还是偏高。
6
算法应用场景
聚类算法最典型的用就是用于web页面的聚类,如新闻聚类。一般的,在一个大型的门户网站在对新闻页面进行聚类的时候都会对这个算法进行一个改进。 考虑到新闻的时效性和准确性的要求可以将新闻聚类拆解为两个大的部分:在线算法和离线算法。