北大nlp聚類(lèi)《互聯(lián)網(wǎng)數(shù)據(jù)挖掘》本

1、互聯(lián)網(wǎng)數(shù)據(jù)挖掘本科生課程數(shù)據(jù)挖掘基礎(chǔ)（三）： 聚類(lèi)萬(wàn)小軍語(yǔ)言計(jì)算與互聯(lián)網(wǎng)挖掘組2016年11月1日概念 聚類(lèi)：將數(shù)據(jù)自動(dòng)聚集到不同類(lèi)簇n 同一類(lèi)簇內(nèi)數(shù)據(jù)相似，不同類(lèi)簇間數(shù)據(jù)不相似n 無(wú)監(jiān)督學(xué)習(xí) 沒(méi)有標(biāo)注數(shù)據(jù) 類(lèi)簇未知類(lèi)簇1類(lèi)簇2.類(lèi)簇n數(shù)據(jù)/ 文本聚類(lèi)器2應(yīng)用 聚類(lèi)應(yīng)用聚類(lèi)與話題檢測(cè)nn 檢索結(jié)果組織n 網(wǎng)絡(luò)社區(qū)發(fā)現(xiàn)n 3文本聚類(lèi)技術(shù) 聚類(lèi)質(zhì)量n 類(lèi)簇之間的文檔距離 最大化n 類(lèi)簇內(nèi)部的文檔距離 最小化 聚類(lèi)算法n K-Means聚類(lèi)n 層次式聚類(lèi)(Hierarchical clustering)n 增量式單遍聚類(lèi)n 基于圖分割的聚類(lèi)n 基于密度峰值的聚類(lèi) 距離(或相似度)測(cè)度4文本聚類(lèi)技術(shù)

2、距離測(cè)度n 歐式距離(Euclidian distance (L2 norm)mr rL2 (x, y) =(xi - yi )2i=1n L1范式(L1 norm)mrrL (x, y) =x - y1iii=1n 基于余弦測(cè)度的距離xrry1 -ryrx5層次式聚類(lèi) 自底向上的凝聚式聚類(lèi)(Agglomerative clustering):n 初始每個(gè)文檔自成一個(gè)類(lèi)簇n 每次合并最相似/距離最近的兩個(gè)類(lèi)簇，形成一個(gè)新類(lèi)簇，循環(huán)執(zhí)行，直到滿足終止條件 終止條件為類(lèi)簇?cái)?shù)量或者相似度閾值6層次式聚類(lèi) 凝聚式聚類(lèi)-示例7層次式聚類(lèi) 凝聚式聚類(lèi)-結(jié)果為樹(shù)形圖8層次式聚類(lèi) 凝聚式聚類(lèi)-不同的計(jì)算類(lèi)簇間

3、距離/相似性的cosminpglleet-el-inliknk (最大小距離)Group-average (平均距離)9層次式聚類(lèi) 自頂向下的劃分式聚類(lèi)(Divisive clustering):n 初始只有一個(gè)類(lèi)簇，所有文檔n 每次從當(dāng)前類(lèi)簇中選擇最大（或最不合理）的一個(gè)類(lèi)簇，將其分割成兩個(gè)（或多個(gè)）新的類(lèi)簇，循環(huán)執(zhí)行，直到滿足終止條件 類(lèi)簇分割為采用其他聚類(lèi)算法，比如K均值算法等10層次式聚類(lèi) Agglomerative vs. Divisive clusteringStep 1Step 2Step 3Step 4Step 0agglomerativea b c dea ba b c d

4、ec d ed edivisiveStep 3Step 2Step 1Step 0Step 411K均值(K-means)聚類(lèi) 一種基于劃分的聚類(lèi)算法 算法將文檔集劃分到k個(gè)類(lèi)簇中n 每個(gè)類(lèi)簇有一個(gè)類(lèi)簇中心, 稱為centroid. 可基于該類(lèi)簇文檔向量的平均向量計(jì)算n k 由用戶指定12K均值(K-means)聚類(lèi) 算法執(zhí)行以下幾步:1) 隨機(jī)選擇k個(gè)心；點(diǎn)作為初始中心點(diǎn)/類(lèi)簇中2) 將每個(gè)文檔指派到與其最相似的中心點(diǎn)所在的類(lèi)簇；3) 根據(jù)當(dāng)前類(lèi)簇文檔重新計(jì)算類(lèi)簇中心點(diǎn)；4) 如果不收斂或不滿足終止條件, 繼續(xù)執(zhí)行步驟2）；13K均值聚類(lèi)例子(k=2)Pick seeds Reassign

5、clusters Compute centroidsReasssign clustersCompute centroidsReassign clustersConverged!x14K-means算法復(fù)雜度 時(shí)間復(fù)雜度為 O(tkn)n n 為數(shù)據(jù)點(diǎn)個(gè)數(shù)n k 為聚類(lèi)數(shù)目n t為迭代次數(shù)n 通常 k, t n.15點(diǎn)(seed)的選擇Iteration 1Iteration 2Iteration 33332.52.52.52221.51.51.51110.50.50.5000-2-1.5-1-0.50x0.511.52-2-1.5-1-0.50x0.511.52-2-1.5-1-0.50x0.

6、511.52Iteration 4Iteration 5Iteration 63332.52.52.52221.51.51.51110.50.50.500016-2-1.5-1-0.50x0.511.52-2-1.5-1-0.50x0.511.52-2-1.5-1-0.50x0.511.52yyyyyy點(diǎn)(seed)的選擇32.5Original Points21.510.50-2-1.5-1-0.50x0.511.52332.52.5221.51.5110.50.500-2-1.5-1-0.50x0.511.52-2-1.5-1-0.50x0.511.5217Optimal Clusteri

7、ngSub-optimal Clusteringyyy結(jié)合K-means與凝聚式聚類(lèi) Buckshot算法n 從原始n個(gè)數(shù)據(jù)點(diǎn)中隨機(jī)取n 個(gè)數(shù)據(jù)點(diǎn)這些樣本數(shù)據(jù)點(diǎn)上運(yùn)行凝聚式聚類(lèi)nn 使用凝聚式聚類(lèi)結(jié)果作為初始點(diǎn)n 在原數(shù)據(jù)上基于初始點(diǎn)運(yùn)行K-means18增量式單遍聚類(lèi) 單遍聚類(lèi)(Single-Pass)n 增量式聚類(lèi)，適合于高效處理動(dòng)態(tài)文本數(shù)據(jù)流n 將新文檔與已有類(lèi)簇逐一比對(duì)，如果與某個(gè)類(lèi)簇的相似度值大于設(shè)定的閾值，那么將該文檔歸并到相應(yīng)類(lèi)簇中，否則基于該文檔形成一個(gè)新的類(lèi)簇 數(shù)據(jù)流中第一個(gè)文檔形成第一個(gè)類(lèi)簇19增量式單遍聚類(lèi)20基于圖分割的聚類(lèi) 計(jì)算文檔對(duì)之間的相似度值，構(gòu)建相似度圖G=(

8、V, E)n 每個(gè)文檔為圖的一個(gè)節(jié)點(diǎn)n 文檔之間有邊連接，邊的權(quán)重W為文檔相似度值 文檔聚類(lèi)問(wèn)題轉(zhuǎn)換成在圖上進(jìn)行頂點(diǎn)分割的問(wèn)題21基于圖分割的聚類(lèi)2個(gè)類(lèi)簇22基于圖分割的聚類(lèi)圖分割目標(biāo)為最小化cut值23基于圖分割的聚類(lèi)切割準(zhǔn)則問(wèn)題：只考慮了類(lèi)簇之間的連接情況，沒(méi)有考慮類(lèi)簇內(nèi)部的密度24基于圖分割的聚類(lèi)改進(jìn)辦法： Normalized CutVol(A): A中節(jié)點(diǎn)到圖中所有節(jié)點(diǎn)的邊的權(quán)重之和.Cut(A,B)/vol(A)1 Cut(A,B)/vol(B)1一種基于圖分割準(zhǔn)則的優(yōu)化求解為譜聚類(lèi)(spectralclustering)，具體細(xì)節(jié)參考(Shi&Malik2000)通過(guò)規(guī)范化能夠取

9、得更加均衡25的圖分割。基于密度峰值的聚類(lèi)(Science) 簡(jiǎn)單優(yōu)美，可自動(dòng)確定聚類(lèi)數(shù)目，檢測(cè)孤立點(diǎn)，可識(shí)別不同形狀的聚類(lèi) 假設(shè)：類(lèi)簇中心被一些局部密度較低的點(diǎn)，并且這些點(diǎn)距離其它有高局部密度的點(diǎn)的距離都比較大26基于密度峰值的聚類(lèi)(Science) 定義n 為每個(gè)數(shù)據(jù)點(diǎn)i計(jì)算兩個(gè)值 局部密度 與更高局部密度點(diǎn)的最小距離27基于密度峰值的聚類(lèi)(Science) 聚類(lèi)過(guò)程n 計(jì)算出所有數(shù)據(jù)點(diǎn)的局部密度值和到高局部密度點(diǎn)的距離后，可以得到一張決策圖n 在決策圖上挑選具有較大類(lèi)簇中心以及較大的樣本點(diǎn)作為n 將其它樣本點(diǎn)按照局部密度從高到底依次確定所屬類(lèi)簇，其類(lèi)簇為鄰域內(nèi)最近的高于該點(diǎn)局部密度的樣本

10、點(diǎn)所屬的類(lèi)簇28基于密度峰值的聚類(lèi)(Science) 示例聚類(lèi)中心點(diǎn)：1, 10孤立點(diǎn)(outlier)：26, 27, 2829聚類(lèi)結(jié)果評(píng)估 基于人工標(biāo)注的類(lèi)簇進(jìn)行評(píng)價(jià) 評(píng)價(jià)準(zhǔn)則息(NMI) F值計(jì)算：F值、純度(Purity)、規(guī)范化互信n 對(duì)每個(gè)人工標(biāo)注的類(lèi)簇i與每個(gè)系統(tǒng)生成的類(lèi)簇j, 計(jì)算相應(yīng)的F值F(i,j)n 總體F值為30聚類(lèi)算法的選擇 聚類(lèi)算法的選擇具有性n 每種算法都有各自的優(yōu)勢(shì)與不足，聚類(lèi)效果通常依賴于聚類(lèi)算法、距離函數(shù)、具體的數(shù)據(jù)與應(yīng)用 實(shí)際做法n 運(yùn)行使用不同距離函數(shù)的多個(gè)聚類(lèi)算法，分析和比較聚類(lèi)結(jié)果 對(duì)聚類(lèi)結(jié)果的解釋要基于原始數(shù)據(jù)的意義以及聚 類(lèi)算法的特性31半監(jiān)督聚

11、類(lèi) 除了待聚類(lèi)的數(shù)據(jù)，還提供了少量先驗(yàn)知識(shí)n 部分標(biāo)注 例如為若干數(shù)據(jù)點(diǎn)標(biāo)注了類(lèi)簇n 約束 例如要求某兩個(gè)數(shù)據(jù)點(diǎn)必須在同一類(lèi)簇，或某兩個(gè)數(shù)據(jù)點(diǎn)不能在同一類(lèi)簇 處理：改造現(xiàn)有聚類(lèi)算法n 以K-means算法為例32半監(jiān)督聚類(lèi)提供了部分Seeded points提供了約束Must-linkCannot-link33半監(jiān)督聚類(lèi) Seeded K-meansn 用戶提供了Seeded pointsn 利用提供的標(biāo)注(seeded points)尋找初始類(lèi)簇中心，然后運(yùn)行K-meansn Seeded points的可能會(huì)改變34半監(jiān)督聚類(lèi) Seeded K-means35半監(jiān)督聚類(lèi) Seeded K-

12、meansInitialize Means Using Labeled Dataxx36半監(jiān)督聚類(lèi) Seeded K-meansAssign Points to Clustersxx37半監(jiān)督聚類(lèi) Seeded K-meansRe-estimate Meansxx38半監(jiān)督聚類(lèi) Seeded K-meansAssign points to clusters and Convergexthe label is changedx39半監(jiān)督聚類(lèi) Constrained K-meansn 用戶提供了Seeded pointsn 利用提供的標(biāo)注(seeded points)尋找初始類(lèi)簇中心，然后運(yùn)行K-

13、meansn Seeded points的不被改變40半監(jiān)督聚類(lèi) COP K-meansn 用戶提供了must-link與cannot-link約束n 初始化：類(lèi)簇中心隨機(jī)選擇，但必須保證滿足must-link約束， 也就是must-link的兩個(gè)數(shù)據(jù)點(diǎn)不能選做為不同類(lèi)簇的中心n 算法：一個(gè)數(shù)據(jù)點(diǎn)必須在不任何約束的情況下歸屬到鄰近的類(lèi)簇41半監(jiān)督聚類(lèi) COP K-meansDetermineits labelMust-linkxxAssign to the red class42半監(jiān)督聚類(lèi) COP K-meansDetermine its labelxxCannot-linkAssign to

14、 the red class43半監(jiān)督聚類(lèi) COP K-meansDetermine its labelMust-linkxxCannot-linkThe clustering algorithm fails44檢索結(jié)果聚類(lèi) 應(yīng)對(duì)n “有歧義、檢索結(jié)果過(guò)多的問(wèn)題” 水果？公司？ 對(duì)某的檢索頁(yè)面結(jié)果進(jìn)行組織，將相似/相關(guān)的結(jié)果聚集到同一類(lèi)簇，形成多個(gè)類(lèi)簇，方便用 戶瀏覽檢索結(jié)果n 每個(gè)類(lèi)簇需要有方便用戶理解的n 主要基于頁(yè)面的標(biāo)題與短摘要(snippet)，而非整個(gè)頁(yè)面45檢索結(jié)果聚類(lèi)-Clusty46檢索結(jié)果聚類(lèi)-Kartoo47檢索結(jié)果聚類(lèi)-Grokker“Open Source”48檢索結(jié)果聚類(lèi)-笨笨貓49檢索結(jié)果聚類(lèi) 兩類(lèi)n 先對(duì)snippet進(jìn)行聚類(lèi)，然后為每個(gè)類(lèi)簇選擇n 先分析獲取有意義的類(lèi)簇到不同，然后將檢索結(jié)果劃分50基于回歸學(xué)習(xí)的檢索結(jié)果聚類(lèi) 先獲得重要的短語(yǔ)代表類(lèi)簇，然后再將檢索結(jié)果跟類(lèi)簇關(guān)聯(lián) 同樣一文檔隸屬多個(gè)類(lèi)簇基于學(xué)習(xí)的短語(yǔ)排序從文檔中抽取候選短語(yǔ)H. Zeng et al. Learning to cluster web search results文檔與類(lèi)簇關(guān)聯(lián)51基于回歸學(xué)習(xí)的檢索結(jié)果聚類(lèi)