Kmeans聚類

1 聚類與分類的區(qū)別
2 k-means 聚類基本概念
3 算法優(yōu)缺點(diǎn)
4 算法思路
5 代碼實現(xiàn)

1 聚類與分類的區(qū)別

簡單來說

  • 分類：類別是已知的，通過對已知分類的數(shù)據(jù)進(jìn)行訓(xùn)練和學(xué)習(xí)，找到這些不同類的特征，再對未分類的數(shù)據(jù)進(jìn)行分類。屬于監(jiān)督學(xué)習(xí)。
  • 聚類：事先不知道數(shù)據(jù)會分為幾類，通過聚類分析將數(shù)據(jù)聚合成幾個群體。聚類不需要對數(shù)據(jù)進(jìn)行訓(xùn)練和學(xué)習(xí)。屬于無監(jiān)督學(xué)習(xí)。

分類作為一種監(jiān)督學(xué)習(xí)方法，要求必須事先明確知道各個類別的信息，并且斷言所有待分類項都有一個類別與之對應(yīng)。但是很多時候上述條件得不到滿足，尤其是在處理海量數(shù)據(jù)的時候，如果通過預(yù)處理使得數(shù)據(jù)滿足分類算法的要求，則代價非常大，這時候可以考慮使用聚類算法。

2 k-means聚類基本概念

K-Means 聚類算法屬于無監(jiān)督學(xué)習(xí)方法。K表示類別數(shù)，Means表示均值，K一般由人工來指定，或通過層次聚類(Hierarchical Clustering)的方法獲得數(shù)據(jù)的類別數(shù)量作為選擇K值的參考。選擇較大的K可以降低數(shù)據(jù)的誤差，但會增加過擬合的風(fēng)險。

2.1幾個概念：

  • 聚類（Clustering）：K-Means 是一種聚類分析（Cluster Analysis）方法。聚類就是將數(shù)據(jù)對象分組成為多個類或者簇 (Cluster)，使得在同一個簇中的對象之間具有較高的相似度，而不同簇中的對象差別較大。
  • 劃分（Partitioning）：聚類可以基于劃分，也可以基于分層。劃分即將對象劃分成不同的簇，而分層是將對象分等級。
  • 排他（Exclusive）：對于一個數(shù)據(jù)對象，只能被劃分到一個簇中。如果一個數(shù)據(jù)對象可以被劃分到多個簇中，則稱為可重疊的（Overlapping）。
  • 距離（Distance）：基于距離的聚類是將距離近的相似的對象聚在一起。基于概率分布模型的聚類是在一組對象中，找到能符合特定分布模型的對象的集合，他們不一定是距離最近的或者最相似的，而是能完美的呈現(xiàn)出概率分布模型所描述的模型。

2.2 K-Means 問題描述：

給定一個 n 個對象的數(shù)據(jù)集，它可以構(gòu)建數(shù)據(jù)的 k 個劃分，每個劃分就是一個簇，并且 k ≤ n。同時還需滿足：

  • 每個組至少包含一個對象。
  • 每個對象必須屬于且僅屬于一個簇。

3 算法優(yōu)缺點(diǎn)

3.1 優(yōu)點(diǎn)：

  • 是解決聚類問題的一種經(jīng)典算法，簡單、快速。
  • 對處理大數(shù)據(jù)集，該算法保持可伸縮性和高效率。
  • 當(dāng)結(jié)果簇是密集的，它的效果較好。

3.2 缺點(diǎn)：

  • 在簇的平均值可被定義的情況下才能使用，可能不適用于某些應(yīng)用。
  • 必須事先給出k（要生成的簇的數(shù)目），而且對初值敏感，對于不同的初始值，可能會導(dǎo)致不同結(jié)果。
  • 不適合于發(fā)現(xiàn)非凸形狀的簇或者大小差別很大的簇。
  • 對躁聲和孤立點(diǎn)數(shù)據(jù)敏感。

4 算法思路

4.1 K-Means 聚類算法的大致意思就是“物以類聚，人以群分”。

算法思路如下：

  1. 首先輸入 k 的值，即我們指定希望通過聚類得到 k 個分組；
  2. 從數(shù)據(jù)集中隨機(jī)選取 k 個數(shù)據(jù)點(diǎn)作為初始質(zhì)心；
  3. 對集合中每一個樣本點(diǎn)，計算與每一個初始質(zhì)心的距離，離哪個初始質(zhì)心距離近，就屬于那個類。
  4. 按距離對所有樣本分完組之后，計算每個組的均值（最簡單的方法就是求樣本每個維度的平均值），作為新的質(zhì)心。
  5. 重復(fù)（2）（3）（4）直到新的質(zhì)心和原質(zhì)心相等，算法結(jié)束。

4.2 相似度/距離計算:

  • 1 歐氏距離相似度


    image.png

  • 2 Jaccard相似度


    image.png

  • 3 余弦相似度


    image.png

  • 4 Pearson相似度


    image.png

  • 5 相對熵(K-L距離)


    image.png

4.3 實例解釋算法（采取余弦相似性對166個文本聚為13類）

image.png

以新聞的聚類為例子。對多篇新聞進(jìn)行聚類，步驟如下：

（1） 文本預(yù)處理：分詞、統(tǒng)計TF-IDF

1 分詞
由于文本過多，故選取一篇文章說明，例如對下文分詞：
中石油海南銷售公司掛牌10%股權(quán)|2016-11-24|每日經(jīng)濟(jì)新聞|在終端銷售板塊宣布進(jìn)入混改超過2年后，作為
試點(diǎn)的新疆銷售公司還未見實質(zhì)動作，中國石油已經(jīng)在海南啟動股權(quán)轉(zhuǎn)讓，但這場掛牌“叫賣”卻頗顯蹊蹺，是
混改正在加速？又或者是地方提前鎖定的交易仍存懸念。 11月23日，上海聯(lián)合產(chǎn)權(quán)交易所披露，中國石油以
1.57億元掛牌出售中石油海南銷售有限公司（以下簡稱海南銷售公司）10％股權(quán)的公告。 但巧合的是，《每
日經(jīng)濟(jì)新聞》記者查詢公開信息發(fā)現(xiàn)，今年1月，海南省國資委就已經(jīng)公布，由海南國資控股的海南省發(fā)展控
股公司（以下簡稱海南發(fā)控）參股海南銷售公司10%，并啟動辦理程序。今年8月?lián)逗Ｄ先請蟆穲蟮?，海?發(fā)控宣布與中國石油就合資經(jīng)營海南銷售公司簽署框架協(xié)議。 目前尚不清楚掛牌的10%與海南發(fā)控的10%是
否為同一份股權(quán)。對此，國資專家李錦認(rèn)為，如此次公開掛牌轉(zhuǎn)讓最后受讓方就是海南發(fā)控，雖然不算是違
規(guī)，但這就不一定能完全達(dá)到混改目的，“海南發(fā)控也是國資。只能算作產(chǎn)權(quán)轉(zhuǎn)讓而不是混合所有制改革?！?
對于上述情況，記者致電中國石油集團(tuán)（以下簡稱中石油），但截稿前并未得到答復(fù)。 交易所稱接受各類資
本 據(jù)掛牌信息，海南銷售凈資產(chǎn)7.26億元，10%股權(quán)掛牌價為1.57億元，

排序后:================
海南             的次數(shù)為27
銷售             的次數(shù)為23
中石油             的次數(shù)為14
掛牌             的次數(shù)為11
國資             的次數(shù)為10
公司             的次數(shù)為10
10             的次數(shù)為9
中國石油             的次數(shù)為8
轉(zhuǎn)讓             的次數(shù)為8
記者             的次數(shù)為7
板塊             的次數(shù)為7
股權(quán)             的次數(shù)為7
新疆             的次數(shù)為6
億元             的次數(shù)為6
表示             的次數(shù)為6
受讓方             的次數(shù)為6

2 計算詞頻（某詞在一篇文章中出現(xiàn)的次數(shù)/文章總詞數(shù)）
排序前:================
程序             的tf為0.004739336492890996
交易             的tf為0.00631911532385466
子公司             的tf為0.004739336492890996
目前             的tf為0.00631911532385466
中國             的tf為0.004739336492890996
中石油             的tf為0.022116903633491312
新聞             的tf為0.007898894154818325
記者             的tf為0.011058451816745656
交易所             的tf為0.007898894154818325
今年             的tf為0.007898894154818325
參股             的tf為0.004739336492890996

結(jié)果以（文章標(biāo)題，詞語，頻數(shù)）形式存儲在Map數(shù)據(jù)結(jié)構(gòu)中：
{中石油海南銷售公司掛牌10%股權(quán)={程序=0.004739336492890996, 交易=0.00631911532385466, 子公司
=0.004739336492890996, 目前=0.00631911532385466, 中國=0.004739336492890996, 中石油
=0.022116903633491312, 新聞=0.007898894154818325, 記者=0.011058451816745656, 交易所
=0.007898894154818325, 今年=0.007898894154818325, 參股=0.004739336492890996, 這一
=0.004739336492890996, 項目=0.004739336492890996, 國資=0.01579778830963665, 報道
=0.004739336492890996, 簡稱=0.004739336492890996, 可能=0.004739336492890996, 啟動
=0.00631911532385466, 改革=0.007898894154818325, 經(jīng)濟(jì)=0.007898894154818325, 板塊
=0.011058451816745656, 有限公司=0.004739336492890996, 新疆=0.009478672985781991, 中國石油
=0.01263823064770932, 公司=0.01579778830963665, 試點(diǎn)=0.004739336492890996, 所有制
=0.004739336492890996, 意向=0.004739336492890996, 海南省=0.004739336492890996, 8月
=0.004739336492890996, 信息=0.004739336492890996, 以下=0.004739336492890996, 銷售
=0.036334913112164295, 目的=0.004739336492890996, 企業(yè)=0.00631911532385466, 億元
=0.009478672985781991, 掛牌=0.017377567140600316, 產(chǎn)權(quán)=0.004739336492890996, 1月
=0.004739336492890996, 表示=0.009478672985781991, 加速=0.004739336492890996, 要求
=0.004739336492890996, 股權(quán)=0.011058451816745656, 海南=0.04265402843601896, 發(fā)現(xiàn)
=0.004739336492890996, 受讓方=0.009478672985781991, 10=0.014218009478672985, 每日
=0.007898894154818325, 出售=0.004739336492890996, 轉(zhuǎn)讓=0.01263823064770932, 協(xié)議
=0.00631911532385466, 公開=0.004739336492890996, 宣布=0.004739336492890996, 此次
=0.004739336492890996}}

3計算idf。
IDF的主要思想是：如果包含詞條t的文檔越少，也就是n越小，IDF越大，則說明詞條t具有很好的類別區(qū)分能
力。如果某一類文檔C中包含詞條t的文檔數(shù)為m，而其它類包含t的文檔總數(shù)為k，顯然所有包含t的文檔數(shù)
n=m+k，當(dāng)m大的時候，n也大，按照IDF公式得到的IDF的值會小，就說明該詞條t類別區(qū)分能力不強(qiáng)。
IDF＝log(|D| /(1+|Dt|))，其中|D|表示文檔總數(shù)，|Dt|表示包含關(guān)鍵詞t的文檔數(shù)量。
如上所述IDF原理，所以需要用到文檔總數(shù)，下面以40篇文檔為例子。
計算出的idf（下方有文本的tf，可幫助查看包含的文檔，注意此處關(guān)鍵詞還未包含標(biāo)題內(nèi)的詞語。）
例如，在此例子中“重點(diǎn)”出現(xiàn)了1次，“冬季”和“合資”出現(xiàn)2次，“建設(shè)”和“減產(chǎn)”出現(xiàn)4次。
{重點(diǎn)(1次)=3.713572066704308, 天山=3.713572066704308, 支持=3.713572066704308, 停止
=3.713572066704308, 聯(lián)盟=3.713572066704308, 明確=3.713572066704308, 建設(shè)(4
次)=2.327277705584417, 備用=3.713572066704308, 網(wǎng)絡(luò)=3.713572066704308, 具有

（2）計算每個詞的權(quán)重(tf-idf)

4 計算每個詞的權(quán)重(tf-idf)
由于文本長短不一，權(quán)重也不同和向量維度也不同，會影響后面計算文本距離。故為了降維，此處每篇文章只選取了權(quán)重排名前15的詞，若文章詞數(shù)不夠，
則在后面添加none，并將其權(quán)重置為0.0（none=0.0）。
Eg
{西安啟動天然氣供氣應(yīng)急預(yù)案={中心=0.04184306554033023, 供氣=0.13613182585439382, 停止
=0.04184306554033023, 啟動=0.034032956463598454, 天氣=0.051049434695397675, 天然氣
=0.08120334918913744, 應(yīng)急=0.08368613108066046, 搶險=0.05230383192541279, 每天
=0.04184306554033023, 氣量=0.042541195579498065, 用戶=0.05955767381129729, 西安
=0.05230383192541279, 采暖=0.04184306554033023, 鍋爐=0.04184306554033023, 預(yù)案
=0.05230383192541279},

（3）尋找k個初始文本做為初始聚類中心

5 尋找k個初始文本做為初始聚類中心。
由于若文檔過多在調(diào)試時，無法顯示所有的值，故選取20篇文本作為試驗。
例如，此處將20篇文檔聚為4類，K=4，即隨機(jī)選取4個文檔作為初始聚類中心；
{0={atlantis=0.036978005316478824, none12=0.0, none13=0.0, none14=0.0, none15=0.0, 公司
=0.01743017642051809, 發(fā)電站=0.036978005316478824, 安裝=0.036978005316478824, 最大
=0.036978005316478824, 海峽=0.036978005316478824, 渦輪機(jī)=0.1479120212659153, 潮汐
=0.13558601949375568, 系統(tǒng)=0.01743017642051809, 蘇格蘭=0.036978005316478824, 項目
=0.01743017642051809},

（4）計算每個文檔與K個初始文檔之間的距離。（余弦相似性）

6 計算每個文檔與K個初始文檔之間的距離。（余弦相似性）
結(jié)果：
[[0.5341768283489521, 0.22550087649869377, 0.2486281038946042, 0.3159328699405629], 
[0.42238218857464127, 0.41725395486903627, 0.5710840557617309, 0.29669879516442077], 
[0.29046239030058363, 0.21421111152521566, 0.3573621468604463, 0.2735781861114148], 
[0.3150300121740689, 0.11204100926947691, 0.13070547127558185, 0.33172344660962116], 
[0.4797761652659057, 0.11949185554315389, 0.1190211581617493, 0.3756470592440674], 
[0.5044412632415061, 0.1485076373690446, 0.11095477841747425, 0.4654333547886619], 
[0.3407495589566709, 0.19413640256543818, 0.31617687351478385, 0.2193834077767255], 
[0.44727521067474907, 0.1541152390227356, 0.18167884692213088, 0.42173415611538445], 
[-2.220446049250313E-16, 0.3921325379658961, 0.5195159081779397, 0.2950273294005489], 
[0.5085455872006137, 0.26155864577038823, 0.3609306237010538, 0.44333775672496933], 
[0.2950273294005489, 0.2855060565280657, 0.4805358516787299, 0.0],

解釋上面的結(jié)果。
將上面的（0,1,2,3）個初始文檔分別與（1,2,3,4,5，……20）篇文檔（總文檔）計算余弦相似性；
那么，拿上面第一行來說，[[0.5341768283489521, 0.22550087649869377, 0.2486281038946042, 0.3159328699405629]四個數(shù)分別代表，0（初始文檔）0（總文檔），01,02，03的相似性。
但是，上面在初始化時，因為隨機(jī)取了K個文檔，故（0,1,2,3）只是控制文檔個數(shù)所需，只是個代號，此處的（0,1,2,3）分別代表20篇文檔中的第9,11,12,20篇文檔。（初始文檔與總文檔中這些文檔的計算結(jié)果已在上方標(biāo)黃）
從該結(jié)果可以看出，在所有的文檔中，初始的9,12,11,20篇文檔與總文檔中的9,12,11,20篇距離最近，最相似，驗證了其本身就是一篇文檔。

（5）通過比較文檔之間的距離，獲得最相似的文檔。

結(jié)果：

[1, 3, 1, 1, 2, 2, 1, 1, 0, 1, 3, 1, 1, 1, 3, 1, 1, 1, 1, 2]

解釋：
將上面通過余弦定理計算出來的文檔結(jié)果看作一個矩陣，找出每一行中最小值，即該行中與K個聚類中心最相似的文檔，并將這些文檔歸為一類，顯示如上所示結(jié)果。

（6）判斷當(dāng)前所有點(diǎn)屬于的聚類序號是否已經(jīng)全部是其離得最近的聚類，如果是或者達(dá)到最大的迭代次數(shù)，那么結(jié)束算法。

判斷代碼：

for(int i = 0; i <tsLength; i++){  
    if(nearestMeans[i] == assignMeans[i]) 
}
if(okCount == tsLength || iterNum >= 100) break;

參數(shù)解釋：
tsLength：文檔總數(shù)
iterNum：迭代次數(shù)
nearestMeans[i]: 本次迭代的最近文檔數(shù)
[1, 3, 1, 1, 2, 2, 1, 1, 0, 1, 3, 1, 1, 1, 3, 1, 1, 1, 1, 2]
assignMeans[i]: 用于記錄上次迭代的最近文檔數(shù)，初始為0
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

代碼解釋：
比較本次迭代的文檔和上次迭代的文檔，如果相同，則表明當(dāng)前所有文檔已經(jīng)達(dá)到最近聚類，結(jié)束循環(huán)；同時，設(shè)置最大迭代次數(shù)，當(dāng)?shù)竭_(dá)最大迭代次數(shù)時也結(jié)束循環(huán)。

（7）如果未能滿足上述條件，則那么需要重新聚類再進(jìn)行一次迭代，需要修改每個聚類的成員和每個點(diǎn)屬于的聚類信息。

結(jié)果：

{0=[8], 1=[0, 2, 3, 6, 7, 9, 11, 12, 13, 15, 16, 17, 18], 2=[4, 5, 19], 3=[1, 10, 14]}

結(jié)果解釋：
將上面分類結(jié)果[1, 3, 1, 1, 2, 2, 1, 1, 0, 1, 3, 1, 1, 1, 3, 1, 1, 1, 1, 2]歸類，每個文檔賦值給該文檔所屬于的類。

（8）同時，重新計算聚類中心（此處采用向量中心），重復(fù)4~6步驟。

結(jié)果：
{0={5號=0.01679896591155781, dcs=0.044797242430820824, none12=0.0, none13=0.0, none14=0.0, 
none15=0.0, vr=0.01622879764244895, 中廣=0.010720149428603602, 互聯(lián)網(wǎng)=0.04264956001121174, 產(chǎn)
業(yè)=0.0053606511097096955, 發(fā)展=0.00714753481294626, 和睦=0.01955879602559945, 威盛
=0.027588955992163215, 安全=0.01679896591155781, 展區(qū)=0.008114398821224476, 展示
=0.008114398821224476, 工業(yè)=0.011360158349714265, 工程=0.008387543745928074, 應(yīng)用
=0.00973727858546937, 快遞=0.00649151905697958, 我國=0.023750221822483743, 技術(shù)
=0.011804741125103237, 推動=0.00984220615643348, 推進(jìn)=0.013122941541911307, 數(shù)據(jù)
=0.010027186597712057, 智能=0.017851677406693845, 機(jī)組

結(jié)果解釋：
{0=[2, 5, 9, 18], 1=[8, 10], 2=[1, 3, 6, 7, 11, 12, 13, 14, 15, 16, 17, 19], 3=[0, 4]}
將上述聚類出的文檔，計算質(zhì)心（向量中心）。
將每一類中文檔的所有詞/文檔總數(shù)，得到向量中心。

（9） 聚類結(jié)果分析

（a）結(jié)果分析（余弦相似性）：

從結(jié)果中可以看出，聚類的結(jié)果并不是很好，而且無法控制聚出的類，在反復(fù)思考調(diào)試之后發(fā)現(xiàn)：使用余弦相似性需要每個文本的詞數(shù)相同，這個條件在第一次可以達(dá)到（由于我將排名前15的詞提取出來，計算文本相似性），但是隨著迭代次數(shù)的增加，當(dāng)再次計算聚類質(zhì)心時，文檔的詞數(shù)就無法保證（因為每個類中所含的文檔數(shù)不同），所以用余弦相似性計算就行不通了。
優(yōu)化方法：
1 可以考慮采用新的方法計算文檔的質(zhì)心。
2 采用逐一比較法計算文檔相似性。

故決定換用直接逐一比較每個詞，計算文本相似性。
原理：將初始的K個文檔和總文檔中所有文檔進(jìn)行比較，如果總文檔中含有K個初始文檔的某個關(guān)鍵詞，則將二者的權(quán)重相乘。此方法主要是通過計算文本中的相同詞來計算文檔的相似性。

（b）結(jié)果分析（向量內(nèi)積）：

結(jié)果分析：從結(jié)果來看，使用逐一比較法計算文本相似性要比用余弦相似性聚類結(jié)果要更合理。原因是，使用此方法沒有了特征詞的限制，通過逐一比較文檔，可以更加全面的計算文檔的相似性。

但是，結(jié)果依舊存在一些問題。例如有些地方還是存留著一些某個主題卻未聚到一類中，有些聚出的類難以辨認(rèn)屬于哪類，也說明算法還需要優(yōu)化。

進(jìn)一步優(yōu)化的具體方法

首先，Kmeans算法本身就有兩個巨大的缺陷：

（1）K是事先給定的，這個K值的選定是非常難以估計的。很多時候，事先并不知道給定的數(shù)據(jù)集應(yīng)該分成多少個類別才最合適。

（2）K-Means算法需要用初始隨機(jī)種子點(diǎn)來確定，這個隨機(jī)種子點(diǎn)太重要，不同的隨機(jī)種子點(diǎn)會有得到完全不同的結(jié)果。

上述問題優(yōu)化的方法:

(1) ISODATA算法通過類的自動合并和分裂，得到較為合理的類型數(shù)目K。

(2) K-Means++算法可以用來解決這個問題，其可以有效地選擇初始點(diǎn)。

其次，現(xiàn)在的聚類是將文本中的所有內(nèi)容作為相同的處理，而且并未處理文章的標(biāo)題，但事實上文章的每一段中詞的權(quán)重是不同的，所以可以考慮通過給不同的部分的詞語加上不同的權(quán)重來重新計算詞權(quán)重。

最后，還需要通過與其他優(yōu)秀的算法的聚類結(jié)果進(jìn)行比較，并學(xué)習(xí)其在選取K值和計算質(zhì)心時的方式。

5 代碼實現(xiàn)

主函數(shù)

public void KmeansClusterMain(String testSampleDir) throws IOException {  
        //首先計算文檔TF-IDF向量，保存為Map<String,Map<String,Double>> 即為Map<文件名，Map<特征詞，TF-IDF值>>
        Configuration rc = new Configuration("daoconfig.properties");
        String RootURL_exSegTxt = rc.getValue("RootURL_exSegTxt");
        int[] K = {10};  
        Map<String,Map<String,Double>> allTestSampleMap = TfIdf.tfidf(testSampleDir);  
        for(int i = 0; i < K.length; i++){  
            System.out.println("開始聚類，聚成" + K[i] + "類");  
            String KmeansClusterResultFile = RootURL_exSegTxt;  
            Map<String,Integer> KmeansClusterResult = new TreeMap<String, Integer>();  
            KmeansClusterResult = doProcess(allTestSampleMap, K[i]);  
            KmeansClusterResultFile = KmeansClusterResultFile + "\\" + K[i];  
            printClusterResult(KmeansClusterResult,KmeansClusterResultFile);  
            //System.out.println("The Entropy for this Cluster is " + computeV.evaluateClusterRes(KmeansClusterResultFile, K[i]));  
        }  
    }

處理tf-idf的函數(shù)

    /**
     * 計算TF-IDF = TF*IDF
     * @param dir
     * @return singelFile(詞語，TF-IDF)
     * @throws IOException
     */
    public static Map<String, Map<String, Double>> tfidf(String dir) throws IOException {       
        TfIdf.NormalTFOfAll(dir);
        Map<String, Map<String, Double>> tf = TfIdf.tfOfAll(dir);
        //TfIdf.idf(dir); 
        int n=15;
        //Map<String, Double> idf = selectTokenWords(TfIdf.idf(dir), n);
        Map<String, Double> idf = TfIdf.idf(dir);
        Map<String, Map<String, Double>> tfidf = new HashMap<String, Map<String, Double>>();
        sortDouResult(idf,"idf");//排序顯示idf
        for (String title : tf.keySet()) {  
            Map<String, Double> singelFile = tf.get(title);  
            for (String word : singelFile.keySet()) {  
                singelFile.put(word, (idf.get(word)) * singelFile.get(word));  
            }  
            sortDouResult(singelFile,"tf-idf");//排序顯示tf-idf
            tfidf.put(title, selectTokenWords(singelFile, n));
        }
        
        return tfidf;  
    }

聚類過程主函數(shù)

 /**Kmeans算法主過程 
     * @param Map<String, Map<String, Double>> allTestSampleMap 聚類算法測試樣本map 
     * @param int K 聚類的數(shù)量 
     * @return Map<String,Integer> 聚類的結(jié)果  即<文件名，聚類完成后所屬的類別標(biāo)號> 
     * @throws IOException  
     */  
    private Map<String, Integer> doProcess(  
            Map<String, Map<String, Double>> allTestSampleMap, int K) {  
        //0、首先獲取allTestSampleMap所有標(biāo)題順序組成的數(shù)組  
        String[] testSampleNames = new String[allTestSampleMap.size()];  
        int count = 0, tsLength = allTestSampleMap.size();  
        Set<Map.Entry<String, Map<String, Double>>> allTestSampeleMapSet = allTestSampleMap.entrySet();  
        for(Iterator<Map.Entry<String, Map<String, Double>>> it = allTestSampeleMapSet.iterator(); it.hasNext(); ){  
            Map.Entry<String, Map<String, Double>> me = it.next();  
            testSampleNames[count++] = me.getKey();  
        }  
        //1、初始點(diǎn)的選擇算法是隨機(jī)選擇
        Map<Integer, Map<String, Double>> meansMap = getInitPoint(allTestSampleMap, K);//保存K個中心點(diǎn)  <標(biāo)題<詞,權(quán)重>>
        double [][] distance = new double[tsLength][K];//distance[i][j]記錄點(diǎn)i到聚類中心j的距離  
        //2、初始化K個聚類  
        int [] assignMeans = new int[tsLength];//記錄所有點(diǎn)屬于的聚類序號，初始化全部為0  
        Map<Integer, Vector<Integer>> clusterMember = new TreeMap<Integer,Vector<Integer>>();//記錄每個聚類的成員點(diǎn)序號  
        Vector<Integer> mem = new Vector<Integer>();  
        int iterNum = 0;//迭代次數(shù)  
        while(true){  
            System.out.println("迭代次數(shù)" + (iterNum++) + "----------------------");  
            //3、計算每個點(diǎn)和每個聚類中心的距離  
            for(int i = 0; i < tsLength; i++){  
                for(int j = 0; j < K; j++){
                    //計算每個類和k個初始類之間的距離
                    distance[i][j] = getDistance(allTestSampleMap.get(testSampleNames[i]),meansMap.get(j));
                }  
                //wordsDis.put(testSampleNames[i], value);
            }  
            //4、找出最相似的文檔  
            int[] nearestMeans = new int[tsLength];  
            for(int i = 0; i < tsLength; i++){  
                nearestMeans[i] = findNearestMeans(distance, i);    
            }  
            //5、判斷當(dāng)前所有點(diǎn)屬于的聚類序號是否已經(jīng)全部是其離得最近的聚類，如果是或者達(dá)到最大的迭代次數(shù)，那么結(jié)束算法  
            int okCount = 0;  
            for(int i = 0; i <tsLength; i++){  
                if(nearestMeans[i] == assignMeans[i]) okCount++;  
            }  
            System.out.println("okCount = " + okCount);  
            if(okCount == tsLength || iterNum >= 100) break;  
            //6、如果前面條件不滿足，那么需要重新聚類再進(jìn)行一次迭代，需要修改每個聚類的成員和每個點(diǎn)屬于的聚類信息  
            clusterMember.clear();  
            for(int i = 0; i < tsLength; i++){  
                assignMeans[i] = nearestMeans[i];  
                if(clusterMember.containsKey(nearestMeans[i])){  
                    clusterMember.get(nearestMeans[i]).add(i);    
                }  
                else {  
                    mem.clear();  
                    mem.add(i);  
                    Vector<Integer> tempMem = new Vector<Integer>();  
                    tempMem.addAll(mem);  
                    clusterMember.put(nearestMeans[i], tempMem);  
                }  
            }  
            //7、重新計算每個聚類的中心點(diǎn)!  
            for(int i = 0; i < K; i++){  
                if(!clusterMember.containsKey(i)){//注意kmeans可能產(chǎn)生空聚類  
                    continue;  
                }  
                Map<String, Double> newMean = computeNewMean(clusterMember.get(i), allTestSampleMap, testSampleNames);  
                Map<String, Double> tempMean = new TreeMap<String, Double>();  
                tempMean.putAll(newMean);  
                meansMap.put(i, tempMean);  
            }  
        }  
        //8、形成聚類結(jié)果并且返回  
        Map<String, Integer> resMap = new TreeMap<String, Integer>();  
        for(int i = 0; i < tsLength; i++){  
            resMap.put(testSampleNames[i], assignMeans[i]);  
        }  
        return resMap;  
    }
    /**計算當(dāng)前聚類新的中心，采用向量平均 
     * @param clusterM 該點(diǎn)到所有聚類中心的距離 
     * @param allTestSampleMap 所有測試樣例的<文件名，向量>構(gòu)成的map 
     * @param testSampleNames 所有標(biāo)題構(gòu)成的數(shù)組 
     * @return Map<String, Double> 新的聚類中心的向量 
     * @throws IOException  
     */  
    private Map<String, Double> computeNewMean(Vector<Integer> clusterM,  
            Map<String, Map<String, Double>> allTestSampleMap,  
            String[] testSampleNames) {  
        // TODO Auto-generated method stub  
        double memberNum = (double)clusterM.size();  
        Map<String, Double> newMeanMap = new TreeMap<String,Double>();  
        Map<String, Double> currentMemMap = new TreeMap<String,Double>();  
        for(Iterator<Integer> it = clusterM.iterator(); it.hasNext();){  
            int me = it.next();  
            currentMemMap = allTestSampleMap.get(testSampleNames[me]);  
            Set<Map.Entry<String, Double>> currentMemMapSet = currentMemMap.entrySet();  
            for(Iterator<Map.Entry<String, Double>> jt = currentMemMapSet.iterator(); jt.hasNext();){  
                Map.Entry<String, Double> ne = jt.next();
                
                if(newMeanMap.containsKey(ne.getKey())){  
                    newMeanMap.put(ne.getKey(), newMeanMap.get(ne.getKey()) + ne.getValue());//將出現(xiàn)過的詞頻的權(quán)重相加  
                }   
                else {  
                    newMeanMap.put(ne.getKey(), ne.getValue());  
                }  
            }  
        }  
        //計算新的向量中心 
        Set<Map.Entry<String, Double>> newMeanMapSet = newMeanMap.entrySet();  
            for(Iterator<Map.Entry<String, Double>> jt = newMeanMapSet.iterator(); jt.hasNext();){  
                Map.Entry<String, Double> ne = jt.next();  
                newMeanMap.put(ne.getKey(), newMeanMap.get(ne.getKey()) / memberNum);     
        }  
        return newMeanMap;  
    }  
  
    /**找出距離當(dāng)前點(diǎn)最近的聚類中心 
     * @param double[][] 點(diǎn)到所有聚類中心的距離 
     * @return i 最近的聚類中心的序 號 
     * @throws IOException  
     */  
    private int findNearestMeans(double[][] distance,int m) {  
        // TODO Auto-generated method stub  
        double minDist = 10;  
        int j = 0;  
        for(int i = 0; i < distance[m].length; i++){  
            if(distance[m][i] < minDist){  
                minDist = distance[m][i];  
                j = i;  
            }  
        }  
        return j;  
    } 
    
    /**計算兩個點(diǎn)的距離 
     * @param map1 點(diǎn)1的向量map 
     * @param map2 點(diǎn)2的向量map 
     * @return double 兩個點(diǎn)的歐式距離 
     */  
    private double getDistance(Map<String, Double> map1, Map<String, Double> map2) {  
        // TODO Auto-generated method stub  
        return 1 - computeSim(map1,map2);  
    }

END

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容