K-Means 算法简介
中文名字叫做K-均值算法，算法的目的是将n个向量分别归属到K个中心点里面去。算法首先会随机选择K个中心向量，然后通过迭代计算以及重新选择K个中心向量，使得n个向量各自被分配到距离最近的K中心点，并且所有向量距离各自中心点的和最小。
在这里借用Wikipedia上的K-Means条目的图来说明
步骤一：在输入数据集里面随机选择三个向量作为初始中心点，这里的K值为3, 也就是一开始从数据集里面选择了三个向量。
步骤二：将每个向量分配到离各自最近的中心点，从而将数据集分成了K个类。
步骤三：计算得到上步得到聚类中每一聚类观测值的图心，作为新的均值点。
步骤四：重复步骤三，直至结果收敛，这里的收敛是指所有点到各自中心点的距离的和收敛。
K-Means算法的原理比较简单，但是值得注意的是，有两个地方是需要算法使用者去自己选择的：第一个就是K的值，简而言之就是数据集应该被分成多少个类，在K-Means算法里面是要求先给出K值的; 第二个就是距离函数，即如何计算向量和向量或者向量和中心点之间的距离，这里也有很多选择，最常见的自然是欧式距离，也可以用余弦相似度来作为距离函数，还有其他的一些方法等等。以上两个需要注意的选择必然会对聚类结果产生影响，尤其是K值的选择，这里就需要算法使用者根据自身需要来做出仔细衡量。
scikit-learn
scikit-learn 是一个基于Python的Machine Learning模块，里面给出了很多Machine Learning相关的算法实现，其中就包括K-Means算法。安装的话建议参考scikit-learn的Github Repo， 从软件包管理里面装的似乎都版本比较低，会少一点功能。
在做K-Means聚类之前，我们首先需要对将文本转化成向量的形式，转换文本的第一步，自然是分词，这里可以直接使用jieba分词，分完词过后再将词转换成向量，或者说转换成Bag-of-words模型，这里可以采用TF-IDF算法，TF-IDF简单来说就是从两个方面对文本中的词进行加权：
- 词在当前文本中出现的次数。
- 总文本数包含词的数目。
前者越高越好，后者越低越好，比如说「你」，「我」这些词，在一个文本中出现的次数很多，总文本包含这些词的数目也会很多，那么这些词自然无法作为当前文本的代表性内容，如果一个文本中某个词大量出现，但是在总文本中出现的次数又不多，那么这个词对于文本来说很有可能是很重要的。比如在A文本中」乔布斯「这个词出现了很多次，然后「乔布斯」在其他文本里面又很少出现，那么A文本主题和「乔布斯」相关的可能性就比较大，我们必然得提高「乔布斯」这个词在A文本向量中的权重。
在scikit-learn里面，同样也实现了TF-IDF算法，我们可以直接调用。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
#!/usr/bin/env python # -*- coding: utf-8 -*- ''' Author: razrlele Email: razrlele@gmail.com ''' import jieba from sklearn.feature_extraction.text import TfidfVectorizer from sklearn.cluster import KMeans def jieba_tokenize(text): return jieba.lcut(text) tfidf_vectorizer = TfidfVectorizer(tokenizer=jieba_tokenize, \ lowercase=False) ''' tokenizer: 指定分词函数 lowercase: 在分词之前将所有的文本转换成小写，因为涉及到中文文本处理， 所以最好是False ''' text_list = ["今天天气真好啊啊啊啊", "小明上了清华大学", \ "我今天拿到了Google的Offer", "清华大学在自然语言处理方面真厉害"] #需要进行聚类的文本集 tfidf_matrix = tfidf_vectorizer.fit_transform(text_list) num_clusters = 3 km_cluster = KMeans(n_clusters=num_clusters, max_iter=300, n_init=40, \ init='k-means++',n_jobs=-1) ''' n_clusters: 指定K的值 max_iter: 对于单次初始值计算的最大迭代次数 n_init: 重新选择初始值的次数 init: 制定初始值选择的算法 n_jobs: 进程个数，为-1的时候是指默认跑满CPU 注意，这个对于单个初始值的计算始终只会使用单进程计算， 并行计算只是针对与不同初始值的计算。比如n_init=10，n_jobs=40, 服务器上面有20个CPU可以开40个进程，最终只会开10个进程 ''' #返回各自文本的所被分配到的类索引 result = km_cluster.fit_predict(tfidf_matrix) print "Predicting result: ", result |
程序运行结果：
|
1 2 3 4 5 6 |
python2 kmeans_demo.py Building prefix dict from the default dictionary ... Loading model from cache /tmp/jieba.cache Loading model cost 0.275 seconds. Prefix dict has been built succesfully. Predicting result: [2 0 1 0] |
对拟合结果的持久化
在进行大规模文本聚类的时候，并不是每一次都需要从头开始计算TF-IDF和K-Means的，有的时候我们只是需要根据之前的数据聚类结果预测新数据，所以我们可以考虑将计算中途的一些数据保存下来，这样就可以节省不少的时间，令人感到惊喜的是，我们同样可以通过scikit-learn的joblib模块来实现持久化这一过程。
如果有看过scikit-learn官方文档的话应该就可以发现，其实fit_transform和fit_predict只是将fit和transform，以及fit和predicti两个方法写在了一起，也就是说在上面代码中：
|
1 2 3 4 5 6 7 8 9 |
tfidf_matrix = tfidf_vectorizer.fit_transform(text_list) #上面一行代码等价于下面两行代码 tfidf_vectorizer.fit(text_list) tfidf_matrix = tfidf_vectorizer.transform(text_list) result = km_cluster.fit_predict(tfidf_matrix) #上面一行代码等价于下面两行代码 km_cluster.fit(tfidf_matrix) result = km_cluster.predict(tfidf_matrix) |
每一次fit都是对数据进行拟合操作，所以我们可以直接选择将拟合结果持久化，然后预测的时候直接加载，进而节省时间。
|
1 2 3 4 5 6 7 8 |
from sklearn.externals import joblib joblib.dump(tfidf_vectorizer, 'tfidf_fit_result.pkl') joblib.dump(km_cluster, 'km_cluster_fit_result.pkl') #程序下一次则可以直接load tfidf_vectorizer = joblib.load('tfidf_fit_result.pkl') km_cluster = joblib.load('km_cluster_fit_result.pkl') |
References
https://en.wikipedia.org/wiki/K-means_clustering
https://github.com/scikit-learn/scikit-learn
https://github.com/fxsjy/jieba
https://en.wikipedia.org/wiki/Bag-of-words_model
https://en.wikipedia.org/wiki/Tf%E2%80%93idf
http://scikit-learn.org/stable/modules/generated/sklearn.cluster.KMeans.html
http://scikit-learn.org/stable/auto_examples/text/document_clustering.html
http://scikit-learn.org/stable/modules/model_persistence.html
http://brandonrose.org/clustering