K-Means是常用的聚类算法，与其他聚类算法相比，其时间复杂度低，聚类的效果也还不错，这里简单介绍一下k-means算法，下图是一个手写体数据集聚类的结果。 基本思想 k-means算法需要事先指定簇的个数k，算法开始随机选择k个记录点作为中心点，然后遍历整个数据集的各条记录，将每条记录归到离它最近的中心点所在的簇中，之后以各个簇的记录的均值中心点取代之前的中心点，然后不断迭代，直到收敛，算法描述如下： 上面说的收敛，可以看出两方面，一是每条记录所归属的簇不再变化，二是优化目标变化不大。算法的时间复杂度是O(K*N*T)，k是中心点个数，N数据集的大小，T是迭代次数。 优化目标 k-means的损失函数是平方误差： 其中ωkωk表示第k个簇，u(ωk)u(ωk)表示第k个簇的中心点，RSSkRSSk是第k个簇的损失函数，RSSRSS表示整体的损失函数。优化目标就是选择恰当的记录归属方案，使得整体的损失函数最小。 中心点的选择 k-meams算法的能够保证收敛，但不能保证收敛于全局最优点，当初始中心点选取不好时，只能达到局部最优点，整个聚类的效果也会比较差。可以采用以下方法：k-means中心点
k值的选取 k-means的误差函数有一个很大缺陷，就是随着簇的个数增加，误差函数趋近于0，最极端的情况是每个记录各为一个单独的簇，此时数据记录的误差为0，但是这样聚类结果并不是我们想要的，可以引入结构风险对模型的复杂度进行惩罚： λλ是平衡训练误差与簇的个数的参数，但是现在的问题又变成了如何选取λλ了，有研究[参考文献1]指出，在数据集满足高斯分布时，λ=2mλ=2m，其中m是向量的维度。 另一种方法是按递增的顺序尝试不同的k值，同时画出其对应的误差值，通过寻求拐点来找到一个较好的k值，详情见下面的文本聚类的例子。 k-means文本聚类 我爬取了36KR的部分文章，共1456篇，分词后使用sklearn进行k-means聚类。分词后数据记录如下： 使用TF-IDF进行特征词的选取，下图是中心点的个数从3到80对应的误差值的曲线： 从上图中在k=10处出现一个较明显的拐点，因此选择k=10作为中心点的个数，下面是10个簇的数据集的个数。 簇标签生成 聚类完成后，我们需要一些标签来描述簇，聚类完后，相当于每个类都用一个类标，这时候可以用TFIDF、互信息、卡方等方法来选取特征词作为标签。关于卡方和互信息特征提取可以看我之前的文章文本特征选择，下面是10个类的tfidf标签结果。
实现代码 #!--encoding=utf-8from __future__ import print_functionfrom sklearn.feature_extraction.text import TfidfVectorizerfrom sklearn.feature_extraction.text import HashingVectorizerimport matplotlib.pyplot as pltfrom sklearn.cluster import KMeans, MiniBatchKMeansdef loadDataset(): '''导入文本数据集''' f = open('36krout.txt','r') dataset = [] lastPage = None for line in f.readlines(): if ' |
|
声明：文章版权归原作者所有 部分文章转自互联网 如有侵权请联系
[邮箱地址] 删除
|
注册
登录
