Kmeans文本聚類

Kmeans演算法

　K-Means是常用的聚類演算法，與其他聚類演算法相比，其時間複雜度低，聚類的效果也還不錯，這裡簡單介紹一下k-means演算法。

基本思想

　k-means演算法需要事先指定簇的個數k，演算法開始隨機選擇k個記錄點作為中心點，然後遍歷整個數據集的各條記錄，將每條記錄歸到離它最近的中心點所在的簇中，之後以各個簇的記錄的均值中心點取代之前的中心點，然後不斷迭代，直到收斂。

上面說的收斂，可以看出兩方面，一是每條記錄所歸屬的簇不再變化，二是優化目標變化不大。演算法的時間複雜度是O(K*N*T)，k是中心點個數，N數據集的大小，T是迭代次數。

核心代碼

# 計算歐式距離ndef distEclud(vecA, vecB):n return sqrt(sum(power(vecA - vecB, 2))) #la.norm(vecA-vecB)nn# 為給定數據集構建一個包含k個隨機質心的集合ndef randCent(dataSet, k):n n = shape(dataSet)[1]n centroids = mat(zeros((k,n)))#create centroid matn for j in range(n):#create random cluster centers, within bounds of each dimensionn minJ = min(dataSet[:,j]) n rangeJ = float(max(dataSet[:,j]) - minJ)n centroids[:,j] = mat(minJ + rangeJ * random.rand(k,1))ndef kMeans(dataSet, k, distMeas=distEclud, createCent=randCent):n m = shape(dataSet)[0]n clusterAssment = mat(zeros((m,2)))#create mat to assign data points n #to a centroid, also holds SE of each pointn centroids = createCent(dataSet, k)n clusterChanged = Truen while clusterChanged:n clusterChanged = Falsen for i in range(m):#for each data point assign it to the closest centroidn minDist = inf; minIndex = -1n for j in range(k):n distJI = distMeas(centroids[j,:],dataSet[i,:])n if distJI < minDist:n minDist = distJI; minIndex = jn if clusterAssment[i,0] != minIndex: clusterChanged = Truen clusterAssment[i,:] = minIndex,minDist**2n print centroidsn for cent in range(k):#recalculate centroidsn ptsInClust = dataSet[nonzero(clusterAssment[:,0].A==cent)[0]]#get all the point in this clustern centroids[cent,:] = mean(ptsInClust, axis=0) #assign centroid to mean n return centroids, clusterAssmentn

優化目標

　　k-means的損失函數是平方誤差：

其中ωk表示第k個簇，u(ωk)表示第k個簇的中心點，RSSk是第k個簇的損失函數，RSS表示整體的損失函數。優化目標就是選擇恰當的記錄歸屬方案，使得整體的損失函數最小。

中心點的選擇

　　k-meams演算法的能夠保證收斂，但不能保證收斂於全局最優點，當初始中心點選取不好時，只能達到局部最優點，整個聚類的效果也會比較差。可以採用以下方法：k-means中心點

　　1、選擇彼此距離儘可能遠的那些點作為中心點，在sklearn中：

km= KMeans(init=k-means++)

　　2、先採用層次進行初步聚類輸出k個簇，以簇的中心點的作為k-means的中心點的輸入。

km= KMeans(init=random)

　　3、多次隨機選擇中心點訓練k-means，選擇效果最好的聚類結果

文本聚類完整的流程

1.將分詞後的文本矩陣化

讀入文本

def loadDataset():n 導入文本數據集n f = open(26kr.txt,r)n dataset = []n for line in f.readlines():n dataset.append(line)n f.close()n return datasetn

將文本轉化為矩陣，值為TF-IDF值

def transform(dataset,n_features=1000):n vectorizer = TfidfVectorizer(max_df=0.5, max_features=n_features, min_df=2,use_idf=True)n X = vectorizer.fit_transform(dataset)n return X,vectorizern

2.使用kmeans演算法進行聚類，並返回當前聚類結果的損失

def train(X,vectorizer,true_k=10,showLable = False):n km = KMeans(n_clusters=true_k, init=k-means++, max_iter=300, n_init=1,n verbose=False)n km.fit(X)n return km.inertia_ n #inertia_ : floatn #Sum of distances of samples to their closest cluster center.n

k值的選取

　　k-means的誤差函數有一個很大缺陷，就是隨著簇的個數增加，誤差函數趨近於0，最極端的情況是每個記錄各為一個單獨的簇，此時數據記錄的誤差為0，但是這樣聚類結果並不是我們想要的，可以引入結構風險對模型的複雜度進行懲罰：

λ是平衡訓練誤差與簇的個數的參數，但是現在的問題又變成了如何選取λ了，有研究[參考文獻1]指出，在數據集滿足高斯分布時，λ=2m，其中m是向量的維度。

def test():n 測試選擇最優參數n dataset = loadDataset() n print("%d documents" % len(dataset))n X,vectorizer = transform(dataset,n_features=500)n true_ks = []n scores = []n for i in xrange(3,80,1): n score = train(X,vectorizer,true_k=i)/len(dataset)n print (i,score)n true_ks.append(i)n scores.append(score)n plt.figure(figsize=(8,4))n plt.plot(true_ks,scores,label="error",color="red",linewidth=1)n plt.xlabel("n_features")n plt.ylabel("error")n plt.legend()n plt.show()n

得到圖像如下，橫坐標是k的數量，縱坐標是損失。

從上圖中在k=8處出現一個較明顯的拐點，因此選擇k=8作為中心點的個數。

result = list(km.predict(X))nprint (Cluster distribution:)nprint (dict([(i, result.count(i)) for i in result]))n

結果

Cluster distribution:n{0: 2, 1: 12, 2: 14, 3: 127, 4: 25, 5: 5, 6: 2, 7: 5, 8: 4, 9: 4}n

簇標籤生成

聚類完成後，我們需要一些標籤來描述簇，聚類完後，相當於每個類都用一個類標，這時候可以用TFIDF、互信息、卡方等方法來選取特徵詞作為標籤。

if showLable:n print("Top terms per cluster:")n order_centroids = km.cluster_centers_.argsort()[:, ::-1]n terms = vectorizer.get_feature_names()n print (vectorizer.get_stop_words())n for i in range(true_k):n print("Cluster %d:" % i, end=)n for ind in order_centroids[i, :10]:n print( %s % terms[ind], end=)n print()n

結果：

Cluster 0: 店鎮 村民 委員會 園林綠化 地區 培訓中心 大興 大隊 學會 學校nCluster 1: 俱樂部 有限公司 健身 管理 北京 學院 培訓中心 大興 大隊 委員會nCluster 2: 上海 有限公司 文化 傳播 培訓中心 大興 大隊 委員會 學會 學校nCluster 3: 小學 玉林市 秦皇島市 大興 黑龍江省 學會 國家稅務局 地區 培訓中心 大隊nCluster 4: 中心小學 衛生院 辦公室 委員會 人民政府 教育 管理站 協會 財政 有限公司nCluster 5: 村民 委員會 行政村 濉溪縣 巴林左旗 宜興市 安徽省 國家稅務局 地區 培訓中心nCluster 6: 經濟 管理 開發區 委員會 信息 黑龍江省 地區 培訓中心 大興 大隊nCluster 7: 有限公司 文化 傳播 深圳市 學校 河北 北京 黑龍江省 培訓中心 大興n

Kmeans的優點和缺點

Kmeans聚類是一種自下而上的聚類方法，它的優點是簡單、速度快；

缺點是聚類結果與初始中心的選擇有關係，且必須提供聚類的數目。

Kmeans的第二個缺點是致命的，因為在有些時候，我們不知道樣本集將要聚成多少個類別，這種時候kmeans是不適合的。

第一個缺點可以通過多次聚類取最佳結果來解決。

第二個缺點可以通過選取不同的k值，然後選擇損失最小的k值。

ps

將文檔轉化為詞頻矩陣的方法

# coding:utf-8 nfrom sklearn.feature_extraction.text import CountVectorizer n#語料 ncorpus = [ n This is the first document., n This is the second second document., n And the third one., n Is this the first document?, n] n#將文本中的詞語轉換為詞頻矩陣 nvectorizer = CountVectorizer() n#計算個詞語出現的次數 nX = vectorizer.fit_transform(corpus) n#獲取詞袋中所有文本關鍵詞 nword = vectorizer.get_feature_names() nprint word n#查看詞頻結果 nprint X.toarray() n

輸出如下：

[uand, udocument, ufirst, uis, uone, usecond, uthe, uthird, uthis] n[[0 1 1 1 0 0 1 0 1] n [0 1 0 1 0 2 1 0 1] n [1 0 0 0 1 0 1 1 0] n [0 1 1 1 0 0 1 0 1]] n

將文檔轉化為TFIDF矩陣的方法

# coding:utf-8 n#語料 ncorpus = [ n This is the first document., n This is the second second document., n And the third one., n Is this the first document?, n] nfrom sklearn.feature_extraction.text import TfidfTransformer n n#類調用 ntransformer = TfidfTransformer() nprint transformer n#將詞頻矩陣X統計成TF-IDF值 ntfidf = transformer.fit_transform(X) n#查看數據結構 tfidf[i][j]表示i類文本中的tf-idf權重 nprint tfidf.toarray() n

reference：

K-means演算法及文本聚類實踐 - CodeMeals - 博客園

[python] 基於k-means和tfidf的文本聚類代碼簡單實現

[python] 使用scikit-learn工具計算文本TF-IDF值