文本聚類演算法kmeans

A. python sklearn里有kmeans演算法嗎

K-Means是常用的聚類演算法，與其他聚類演算法相比，其時間復雜度低，聚類的效果也還不錯，這里簡單介紹一下k-means演算法，下圖是一個手寫體數據集聚類的結果。
基本思想
k-means演算法需要事先指定簇的個數k，演算法開始隨機選擇k個記錄點作為中心點，然後遍歷整個數據集的各條記錄，將每條記錄歸到離它最近的中心點所在的簇中，之後以各個簇的記錄的均值中心點取代之前的中心點，然後不斷迭代，直到收斂，演算法描述如下：
上面說的收斂，可以看出兩方面，一是每條記錄所歸屬的簇不再變化，二是優化目標變化不大。演算法的時間復雜度是O(K*N*T)，k是中心點個數，N數據集的大小，T是迭代次數。
優化目標
k-means的損失函數是平方誤差：
RSSk=∑x∈ωk|x?u(ωk)|2
RSS=∑k=1KRSSk
其中$\omega _k$表示第k個簇，$u(\omega _k)$表示第k個簇的中心點，$RSS_k$是第k個簇的損失函數，$RSS$表示整體的損失函數。優化目標就是選擇恰當的記錄歸屬方案，使得整體的損失函數最小。
中心點的選擇
k-meams演算法的能夠保證收斂，但不能保證收斂於全局最優點，當初始中心點選取不好時，只能達到局部最優點，整個聚類的效果也會比較差。可以採用以下方法：k-means中心點
1、選擇彼此距離盡可能遠的那些點作為中心點；
2、先採用層次進行初步聚類輸出k個簇，以簇的中心點的作為k-means的中心點的輸入。
3、多次隨機選擇中心點訓練k-means，選擇效果最好的聚類結果
k值的選取
k-means的誤差函數有一個很大缺陷，就是隨著簇的個數增加，誤差函數趨近於0，最極端的情況是每個記錄各為一個單獨的簇，此時數據記錄的誤差為0，但是這樣聚類結果並不是我們想要的，可以引入結構風險對模型的復雜度進行懲罰：
K=mink[RSSmin(k)+λk]
$\lambda$是平衡訓練誤差與簇的個數的參數，但是現在的問題又變成了如何選取$\lambda$了，有研究[參考文獻1]指出，在數據集滿足高斯分布時，$\lambda=2m$，其中m是向量的維度。
另一種方法是按遞增的順序嘗試不同的k值，同時畫出其對應的誤差值，通過尋求拐點來找到一個較好的k值，詳情見下面的文本聚類的例子。
k-means文本聚類
我爬取了36KR的部分文章，共1456篇，分詞後使用sklearn進行k-means聚類。分詞後數據記錄如下：
使用TF-IDF進行特徵詞的選取，下圖是中心點的個數從3到80對應的誤差值的曲線：
從上圖中在k=10處出現一個較明顯的拐點，因此選擇k=10作為中心點的個數，下面是10個簇的數據集的個數。
{0: 152, 1: 239, 2: 142, 3: 61, 4: 119, 5: 44, 6: 71, 7: 394, 8: 141, 9: 93}
簇標簽生成
聚類完成後，我們需要一些標簽來描述簇，聚類完後，相當於每個類都用一個類標，這時候可以用TFIDF、互信息、卡方等方法來選取特徵詞作為標簽。關於卡方和互信息特徵提取可以看我之前的文章文本特徵選擇，下面是10個類的tfidf標簽結果。
Cluster 0: 商家 商品 物流 品牌 支付 導購 網站 購物 平台 訂單
Cluster 1: 投資 融資 美元 公司 資本 市場 獲得 國內 中國 去年
Cluster 2: 手機 智能 硬體 設備 電視 運動 數據 功能 健康 使用
Cluster 3: 數據 平台 市場 學生 app 移動 信息 公司 醫生 教育
Cluster 4: 企業 招聘 人才 平台 公司 it 移動 網站 安全 信息
Cluster 5: 社交 好友 交友 寵物 功能 活動 朋友 基於 分享 游戲
Cluster 6: 記賬 理財 貸款 銀行 金融 p2p 投資 互聯網 基金 公司
Cluster 7: 任務 協作 企業 銷售 溝通 工作 項目 管理 工具 成員
Cluster 8: 旅行 旅遊 酒店 預訂 信息 城市 投資 開放 app 需求
Cluster 9: 視頻 內容 游戲 音樂 圖片 照片 廣告 閱讀 分享 功能
實現代碼
#!--encoding=utf-8
from __future__ import print_function
from sklearn.feature_extraction.text import TfidfVectorizer
from sklearn.feature_extraction.text import HashingVectorizer
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans, MiniBatchKMeans
def loadDataset():
'''導入文本數據集'''
f = open('36krout.txt','r')
dataset = []
lastPage = None
for line in f.readlines():
if '< title >' in line and '< / title >' in line:
if lastPage:
dataset.append(lastPage)
lastPage = line
else:
lastPage += line
if lastPage:
dataset.append(lastPage)
f.close()
return dataset
def transform(dataset,n_features=1000):
vectorizer = TfidfVectorizer(max_df=0.5, max_features=n_features, min_df=2,use_idf=True)
X = vectorizer.fit_transform(dataset)
return X,vectorizer
def train(X,vectorizer,true_k=10,minibatch = False,showLable = False):
#使用采樣數據還是原始數據訓練k-means，
if minibatch:
km = MiniBatchKMeans(n_clusters=true_k, init='k-means++', n_init=1,
init_size=1000, batch_size=1000, verbose=False)
else:
km = KMeans(n_clusters=true_k, init='k-means++', max_iter=300, n_init=1,
verbose=False)
km.fit(X)
if showLable:
print("Top terms per cluster:")
order_centroids = km.cluster_centers_.argsort()[:, ::-1]
terms = vectorizer.get_feature_names()
print (vectorizer.get_stop_words())
for i in range(true_k):
print("Cluster %d:" % i, end='')
for ind in order_centroids[i, :10]:
print(' %s' % terms[ind], end='')
print()
result = list(km.predict(X))
print ('Cluster distribution:')
print (dict([(i, result.count(i)) for i in result]))
return -km.score(X)
def test():
'''測試選擇最優參數'''
dataset = loadDataset()
print("%d documents" % len(dataset))
X,vectorizer = transform(dataset,n_features=500)
true_ks = []
scores = []
for i in xrange(3,80,1):
score = train(X,vectorizer,true_k=i)/len(dataset)
print (i,score)
true_ks.append(i)
scores.append(score)
plt.figure(figsize=(8,4))
plt.plot(true_ks,scores,label="error",color="red",linewidth=1)
plt.xlabel("n_features")
plt.ylabel("error")
plt.legend()
plt.show()
def out():
'''在最優參數下輸出聚類結果'''
dataset = loadDataset()
X,vectorizer = transform(dataset,n_features=500)
score = train(X,vectorizer,true_k=10,showLable=True)/len(dataset)
print (score)
#test()
out()

B. 已計算出個文本間的餘弦相似度值，怎麼用kmeans聚類

K-MEANS演算法: k-means 演算法接受輸入量 k ；然後將n個數據對象劃分為 k個聚類以便使得所獲得的聚類滿足：同一聚類中的對象相似度較高；而不同聚類中的對象相似度較校聚類相似度是利用各聚類中對象的均值所獲得一個「中心對象

C. k-means聚類演算法的java代碼實現文本聚類

K-MEANS演算法:
k-means 演算法接受輸入量 k ；然後將n個數據對象劃分為 k個聚類以便使得所獲得的聚類滿足：同一聚類中的對象相似度較高；而不同聚類中的對象相似度較小。聚類相似度是利用各聚類中對象的均值所獲得一個「中心對象」（引力中心）來進行計算的。

k-means 演算法的工作過程說明如下：首先從n個數據對象任意選擇 k 個對象作為初始聚類中心；而對於所剩下其它對象，則根據它們與這些聚類中心的相似度（距離），分別將它們分配給與其最相似的（聚類中心所代表的）聚類；然後再計算每個所獲新聚類的聚類中心（該聚類中所有對象的均值）；不斷重復這一過程直到標准測度函數開始收斂為止。一般都採用均方差作為標准測度函數. k個聚類具有以下特點：各聚類本身盡可能的緊湊，而各聚類之間盡可能的分開。

具體如下：
輸入：k, data[n];
（1） 選擇k個初始中心點，例如c[0]=data[0],…c[k-1]=data[k-1];
（2） 對於data[0]….data[n], 分別與c[0]…c[n-1]比較，假定與c[i]差值最少，就標記為i;
（3） 對於所有標記為i點，重新計算c[i]=/標記為i的個數；
（4） 重復(2)(3),直到所有c[i]值的變化小於給定閾值。

演算法實現起來應該很容易，就不幫你編寫代碼了。

D. kmeans聚類演算法是什麼

kmeans聚類演算法是將樣本聚類成k個簇（cluster）。

K-Means演算法的思想很簡單，對於給定的樣本集，按照樣本之間的距離大小，將樣本集劃分為K個簇。讓簇內的點盡量緊密的連在一起，而讓簇間的距離盡量的大。在實際K-Mean演算法中，我們一般會多次運行圖c和圖d，才能達到最終的比較優的類別。

用數據表達式表示

假設簇劃分為$(C_1,C_2,...C_k)$，則我們的目標是最小化平方誤差E：$$ E = sumlimits_{i=1}^ksumlimits_{x in C_i} ||x-mu_i||_2^2$$。

其中$mu_i$是簇$C_i$的均值向量，有時也稱為質心，表達式為：$$mu_i = frac{1}{|C_i|}sumlimits_{x in C_i}x$$。

E. k-means 聚類演算法處理什麼類型數據

這個問題其實是無解的，數據不同，演算法的分類效果、實際運行時間也是不同。若單從運算速度而言，k-means比層次更快。原因是K-means是找中心，然後計算距離；層次是逐個樣本逐層合並，層次的演算法復雜度更高。更重要的是，在大數量下，K-means演算法和層次聚類演算法的分類效果真的只能用見仁見智來形容了。

F. 對比傳統K-Means等聚類演算法，LDA主題模型在文本聚類上有何優缺點

K-means 演算法屬於聚類分析方法中一種基本的且應用最廣泛的劃分演算法，它是一種已知聚類類別數的聚類演算法。指定類別數為K，對樣本集合進行聚類，聚類的結果由K 個聚類中心來表達，基於給定的聚類目標函數（或者說是聚類效果判別准則），演算法採用迭代更新的方法，每一次迭代過程都是向目標函數值減小的方向進行，最終的聚類結果使目標函數值取得極小值，達到較優的聚類效果。使用平均誤差准則函數E作為聚類結果好壞的衡量標准之一，保證了演算法運行結果的可靠性和有效性。
-

G. kmeans聚類演算法是什麼

K-means演算法是最為經典的基於劃分的聚類方法，是十大經典數據挖掘演算法之一。K-means演算法的基本思想是：以空間中k個點為中心進行聚類，對最靠近他們的對象歸類。通過迭代的方法，逐次更新各聚類中心的值，直至得到最好的聚類結果。

聚類屬於無監督學習，以往的回歸、樸素貝葉斯、SVM等都是有類別標簽y的，也就是說樣例中已經給出了樣例的分類。而聚類的樣本中卻沒有給定y，只有特徵x，比如假設宇宙中的星星可以表示成三維空間中的點集。

(7)文本聚類演算法kmeans擴展閱讀：

k個聚類以便使得所獲得的聚類滿足：同一聚類中的對象相似度較高；而不同聚類中的對象相似度較小。聚類相似度是利用各聚類中對象的均值所獲得一個「中心對象」（引力中心）來進行計算的。

（1）適當選擇c個類的初始中心；

（2）在第k次迭代中，對任意一個樣本，求其到c個中心的距離，將該樣本歸到距離最短的中心所在的類；

（3）利用均值等方法更新該類的中心值；

（4）對於所有的c個聚類中心，如果利用（2）（3）的迭代法更新後，值保持不變，則迭代結束，否則繼續迭代。

H. k-means演算法是聚類演算法還是分類演算法

一,k-means聚類演算法原理
k-means
演算法接受參數
k
；然後將事先輸入的n個數據對象劃分為
k個聚類以便使得所獲得的聚類滿足：同一聚類中的對象相似度較高；而不同聚類中的對象相似度較小.聚類相似度是利用各聚類中對象的均值所獲得一個「中心對
象」（引力中心）來進行計算的.
k-means演算法是最為經典的基於劃分的聚類方法,是十大經典數據挖掘演算法之一.k-means演算法的基本思想是：以空間中k個點為中心進行聚類,對最靠近他們的對象歸類.通過迭代的方法,逐次更新各聚類中心的值,直至得到最好的聚類結果.
假設要把樣本集分為c個類別,演算法描述如下：
（1）適當選擇c個類的初始中心；
（2）在第k次迭代中,對任意一個樣本,求其到c個中心的距離,將該樣本歸到距離最短的中心所在的類；
（3）利用均值等方法更新該類的中心值；
（4）對於所有的c個聚類中心,如果利用（2）（3）的迭代法更新後,值保持不變,則迭代結束,否則繼續迭代.
該演算法的最大優勢在於簡潔和快速.演算法的關鍵在於初始中心的選擇和距離公式.

I. 文本聚類 一個文本的中心怎麼表示

最簡單的來說文本聚類就是從很多文檔中把一些 內容相似的文檔聚為一類。文本聚類主要是依據著名的聚類假設：同類的文本相似度較大，而不同類的文本相似度較小。作
為一種無監督的機器學習方法，聚
類由於不需要訓練過程，以及不需要預先對文本手工標注類別，因此具有一定的靈活性和較高的自動化處理能力，已經成為對文本信息進行有效地組織、摘要和導航

的重要手段，為越來越多的研究人員所關注。一個文本表現為一個由文字和標點符號組成的字元串,由字或字元組成詞,由片語成短語,進而形成句、段、節、章、

篇的結構。要使計算機能夠高效地處理真是文本，就必須找到一種理想的形式化表示方法，這種表示一方面要能夠真實地反應文檔的內容(主題、領域或結構等)，
另一方面，要有對不同文檔的區分能力。目前文本表示通常採用向量空間模型(vector space model,VSM)。
VSM法即向量空間模型
(Vector Space
Model)法，由Salton等人於60年代末提出。這是最早也是最出名的信息檢索方面的數學模型。其基本思想是將文檔表示為加權的特徵向
量：D=D(T1，W1；T2，W2；…；Tn，Wn)，然後通過計算文本相似度的方法來確定待分樣本的類別。當文本被表示為空間向量模型的時候，文本的
相似度就可以藉助特徵向量之間的內積來表示。最簡單來說一個文檔可以看成是由若干個單片語成的，每個單詞轉化成權值以後,
每個權值可以看成向量中的一個分量，那麼一個文檔可以看成是n維空間中的一個向量，這就是向量空間模型的由來。單詞對應的權值可以通過TF-IDF加權技 術計算出來。

TF-IDF（term frequency–inverse document frequency）是一種用於資訊檢索與文本挖掘的常用加權技術。TF-IDF是一種統計方法，用以評估一字詞對於一個文件集或一個語料庫中的
其中一份文件的重要程
度。字詞的重要性隨著它在文件中出現的次數成正比增加，但同時會隨著它在語料庫中出現的頻率成反比下降。TF-IDF加權的各種形式
常被搜索引擎應用，作為文件與用戶查詢之間相關程度
的度量或評級。除了TF-IDF以外，互聯網上的搜尋引擎還會使用基於連結分析的評級方法，以確定文件在搜尋結果中出現的順序。

原理:

以上式子中 ni,j 是該詞在文件dj中的出現次 數，而分母則是在文件dj中所 有字詞的出現次數之和。

逆向文件頻率（inverse document frequency，IDF）是一個詞語普遍重要性的度量。某一特定詞語的IDF，可以由總文件數目除以包含該詞語之文件的數目，再將得到的商取對數得到：

其中

|D|：語料庫中的文件總數
： 包含詞語ti的文件數目（即的
文件數目）

然後

某一特定文件內的高詞語頻率，以及該詞語在整個文件集合中的低文件頻率，可以產生出高權重的TF-IDF。因此，TF-IDF傾向於過濾掉常見的詞 語，保留重要的詞語。

例子

有很多不同的數學公式可以用來計
算TF-IDF。這邊的例子以上述的數學公式來計算。詞頻
(TF)
是一詞語出現的次數除以該文件的總詞語數。假如一篇文件的總詞語數是100個，而詞語「母牛」出現了3次，那麼「母牛」一詞在該文件中的詞頻就是
0.03 (3/100)。一個計算文件頻率 (DF)
的方法是測定有多少份文件出現過「母牛」一詞，然後除以文件集里包含的文件總數。所以，如果「母牛」一詞在1,000份文件出現過，而文件總數是
10,000,000份的話，其逆向文件頻率就是
9.21 ( ln(10,000,000 / 1,000) )。最後的TF-IDF的分數為0.28( 0.03 * 9.21)。

TF-IDF權重計算方法經常會和余
弦相似度（cosine similarity）一同使用於向 量空間模型中，用以判斷兩份文件之間的相
似性。學過向量代數的人都知道，向量實際上是多維空間中有方向的線段。如果兩個向量的方向一致，即夾角接近零，那麼這兩個向量就相近。而要確定兩 個向量方向是否一致，這就要用到餘弦定理計算向量的夾角了。
餘弦定理對我們每個人都不陌生，它描述了三角形中任何一個夾角和三個邊的關系，換句話說，給定三角形的三條邊，我們可以用餘弦定理求出三角形各個角的角 度。假定三角形的三條邊為 a, b 和 c，對應的三個角為 A, B 和 C，那麼角 A 的餘弦 --

如果我們將三角形的兩邊 b 和 c 看成是兩個向量，那麼上述公式等價於

其中分母表示兩個向量 b 和 c 的長度，分子表示兩個向量的內積。舉一個具體的例子，假如文本 X 和文本 Y 對應向量分別是
x1,x2,...,x64000 和
y1,y2,...,y64000,
那麼它們夾角的餘弦等於，

當兩條文本向量夾角的餘弦等於一時，這兩個文本完全重復（用這個辦法可以刪除重復的網頁）；當夾角的餘弦接近於一時，兩個文本相似，從而可以歸成一類；夾 角的餘弦越小，兩個文本越不相關。

我們在中學學習餘弦定理時，恐怕很難想像它可以用來對文本進行分類。

最後我們在對文本進行聚類時要用到數據挖掘中的Kmeans演算法，聚類演算法有很多種，這篇文章主要介紹Kmeans演算法。K-MEANS演算法:

k-means 演算法接受輸入量 k ；然後將n個數據對象劃分為 k個聚類以便使得所獲得的聚類滿足：同一聚類中的對象相似度較高；而不同聚類中的對象相似度較小。聚類相似度是利用各聚類中對象的均值所獲得一個「中心對 象」（引力中心）來進行計算的。
k-means 演算法的工作過程說明如下：
首先從n個 數據對象任意選擇 k
個對象作為初始聚類中心；而對於所剩下其它對象，則根據它們與這些聚類中心的相似度（距離），分別將它們分配給與其最相似的（聚類中心所代表的）聚類；然
後再計算每個所獲新聚類的聚類中心（該聚類中所有對象的均值）；不斷重復這一過程直到標准測度函數開始收斂為止。一般都採用均方差作為標准測度函數.
k個聚類具有以下特點：各聚類本身盡可能的緊湊，而各聚類之間盡可能的分開。

處理流程：

（ 1 ） 從 c 個 數據對象任意選擇 k 個
對象作為初始聚類中心；
（ 2 ） 循 環（ 3 ） 到（ 4 ）
直到每個聚類不再發生變化為止；
（ 3 ） 根 據每個聚類對象的均值（中心對象），計算每個對象與這些中心對象的距離；並根據最小距離重新對相應對象進行劃分；
（ 4 ） 重 新計算每個（有變化）聚類的均值（中心對象)

到這里這個文本聚類的小程序的核心思想就講完了，總的來說大致步驟如 下：

(1)對各個文本分詞,去除停用詞

(2)通過TF-IDF方法獲得文本向量的權值(每個文本向量的維數是 相同的,是所有文本單詞的數目,這些單詞如果有重復那隻算一次,所以如果文本越多，向量的維數將會越大)

(3)通過K-means演算法對文本進行分類

本人的文本小程序的結 果還算令人滿意，對下面的實驗用例的聚類結果還算是理想，但是每次執行的結果都不一樣。其實聚類的結果受好多種因素制約，提取特徵的演算法，隨機初始化函 數，kmeans演算法的實現等，都有優化的地方，不信你把輸入的數據的順序改改，聚類結果就不一樣了，或者把隨機數的種子變一下，結果也不一樣，k-
means演算法加入一些變異系數的調整，結果也不一樣，提取特徵的地方不用TF/IDF權重演算法用別的，結果肯定也不一樣。

實驗用例：

奧運拳擊入場券基本分罄鄒市明奪冠對手浮出水面
股民要清楚自己的目的
印花稅之股民四季
杭州股民放鞭炮慶祝印花稅下調
殘疾女青年入圍奧運游泳比賽創奧運歷史兩項第一
介紹一個ASP.netMVC系列教程
在asp.net中實現觀察者模式,或有更好的方法(續)
輸大錢的股民給我們啟迪
Asp.Net頁面執行流程分析
運動員行李將"後上先下"奧運相關人員行李實名制
asp.net控制項開發顯示控制項內容
奧運票務網上成功訂票後應及時到銀行代售網點付款
某心理健康站開張後首個咨詢者是位新股民
ASP.NET自定義控制項復雜屬性聲明持久性淺析

以下是我在網上參考的資料：

http://www.cnblogs.com/onlytiancai/archive/2008/05/10/1191557.html

http://hi..com/zhumzhu/blog/item/fc49ef3d19b0a4c09f3d62a3.html