預(yù)習(xí)課件上課前會有部分?jǐn)?shù)據(jù)挖掘聚類算法

1、數(shù)據(jù)挖掘 聚類算法八斗學(xué)院數(shù)據(jù)挖掘聚類算法O u t L i n e八聚類基本知識斗層次聚類法Kmeans聚類【實(shí)踐】基于MLlib的Kmeans聚類 八斗大數(shù)據(jù) 數(shù)據(jù)挖掘聚類算法基 礎(chǔ) 知 識八將數(shù)據(jù)劃分到不同的類里，使相似斗的數(shù)據(jù)在同一類里，不相似的數(shù)據(jù)在不同類里 無監(jiān)督學(xué)習(xí) 應(yīng)用：文本聚類、圖像聚類和商品聚類 便于發(fā)現(xiàn)規(guī)律，以解決數(shù)據(jù)稀疏問題 八斗大數(shù)據(jù) 數(shù)據(jù)挖掘聚類算法基 礎(chǔ) 知 識 層次聚類 vs. 非層次聚類 不同類之間有無包含關(guān)系 八斗大數(shù)據(jù) 數(shù)據(jù)挖掘聚類算法基 礎(chǔ) 知 識八硬聚類 vs. 軟聚類斗 硬聚類：每個(gè)對象只屬于一個(gè)類 A：class1 B：class2 C：class

2、3 軟聚類：每個(gè)對象以某個(gè)概率屬于每個(gè)類 A：class1:0.5, class2:0.2, class3:0.3 B：class1:0.3, class2:0.3, class3:0.5 C：class1:0.4, class2:0.5, class3:0.1 八斗大數(shù)據(jù) 數(shù)據(jù)挖掘聚類算法基 礎(chǔ) 知 識八向量表示 每個(gè)對象用一個(gè)向量表示，可以視為高的一個(gè)點(diǎn) 例如：根據(jù)身高體重來 男(1.67, 62) 男(1.75, 65) 男(1.8, 75) 女(1.62, 48) 女(1.68, 52) 女(1.76, 60) 八斗大數(shù)據(jù) 數(shù)據(jù)挖掘聚類算法基 礎(chǔ) 知 識八向量表示斗 每個(gè)對象用一個(gè)向量

3、表示，可以視為高的一個(gè)點(diǎn) 所有對象形成數(shù)據(jù)空間 相似度計(jì)算： Cosine、點(diǎn)積 計(jì)算質(zhì)心 八斗大數(shù)據(jù) 數(shù)據(jù)挖掘聚類算法基 礎(chǔ) 知 識八距離矩陣、相似度矩陣斗 給出聚類對象之間的距離（或相似性度量） 八斗大數(shù)據(jù) 數(shù)據(jù)挖掘聚類算法基 礎(chǔ) 知 識八評價(jià)方法：斗 內(nèi)部評價(jià)法（Internal Evalution）： 沒有外部標(biāo)準(zhǔn)，非監(jiān)督式 同類是否相似，跨類是否相異 外部評價(jià)法（External Evalution）： 外部標(biāo)準(zhǔn)，監(jiān)督式 跟外部標(biāo)準(zhǔn)的一致性如何 八斗大數(shù)據(jù) 數(shù)據(jù)挖掘聚類算法基 礎(chǔ) 知 識八Davies-Bouldin index斗 八斗大數(shù)據(jù) 數(shù)據(jù)挖掘聚類算法基 礎(chǔ) 知 識八分類指標(biāo)

4、：斗 準(zhǔn)確度（accuracy） 精度（Precision） （Recall） F值（F-measure） 八斗大數(shù)據(jù) 數(shù)據(jù)挖掘聚類算法基 礎(chǔ) 知 識八矩陣斗 準(zhǔn)確度（accuracy）: (C11+C22) / (C11 + C12 + C21 + C22) 精度（Precision）: C11 / (C11 + C21 )（Recall）: C11 / (C11 + C12 ) 八斗大數(shù)據(jù) 數(shù)據(jù)挖掘聚類算法基 礎(chǔ) 知 識八矩陣斗 準(zhǔn)確度（accuracy）: (50+35) / (35+5+10+50) = 85% 精度（Precision）: 50 / (50+5) = 90.9%（Re

5、call）: 50 / (50 + 10) = 83.3% 八斗大數(shù)據(jù) 數(shù)據(jù)挖掘聚類算法O u t L i n e八聚類基本知識斗層次聚類法Kmeans聚類【實(shí)踐】基于MLlib的Kmeans聚類 八斗大數(shù)據(jù) 數(shù)據(jù)挖掘聚類算法層 次 聚 類 算 法八自底向上 凝聚層次聚類 自頂向下層次聚類 八斗大數(shù)據(jù) 數(shù)據(jù)挖掘聚類算法凝 聚 層 次 聚 類 算 法八算法描述：斗 1、將每一個(gè)對象一類，共得到N類，每類僅包含一個(gè)對象 2、找到最接近的兩個(gè)類合并成一個(gè)類 3、重新計(jì)算新的類與所有舊類之間的距離 4、重復(fù)2/3，直到最后合并為一個(gè)類為止（此類包含N個(gè)對象） 八斗大數(shù)據(jù) 數(shù)據(jù)挖掘聚類算法凝 聚 層 次

6、 聚 類 過 程八斗 八斗大數(shù)據(jù) 數(shù)據(jù)挖掘聚類算法凝 聚 層 次 聚 類 樹 狀 圖 描 述 八斗大數(shù)據(jù) 數(shù)據(jù)挖掘聚類算法凝 聚 層 次 聚 類 算 法八每次迭代需要重新計(jì)算新的類斗與舊類之間的距離 計(jì)算方式： 單鏈（Single linkage）：最近距離 （complete linkage）：最遠(yuǎn)距離 組合鏈（average linkage）：平均距離 八斗大數(shù)據(jù) 數(shù)據(jù)挖掘聚類算法凝 聚 層 次 聚 類 算 法八類間距離計(jì)算：斗 Min Max Group average 八斗大數(shù)據(jù) 數(shù)據(jù)挖掘聚類算法層 次 聚 類 算 法 總 結(jié)八算法簡單斗 層次用于概念聚類（生成概念、文檔層次樹） 聚類

7、對象的兩種表示法都適用 處理大小不同的簇 簇選取步驟在樹狀圖生成之后 八斗大數(shù)據(jù) 數(shù)據(jù)挖掘聚類算法O u t L i n e八聚類基本知識斗層次聚類法Kmeans聚類【實(shí)踐】基于MLlib的Kmeans聚類 八斗大數(shù)據(jù) 數(shù)據(jù)挖掘聚類算法K 平 均 （ K - m e a n s ） 聚 類八算法描述：斗 任意選擇K個(gè)點(diǎn)作為初始聚類中心 根據(jù)每個(gè)聚類的中算每個(gè)對象與這些中心的距離，并根據(jù)最小距離重新對相應(yīng)對象進(jìn)行劃分 重新計(jì)算每個(gè)聚類的中心 當(dāng)滿足一定條件，如類別劃分不再發(fā)生變化時(shí)，算法終止，否則繼續(xù)步驟2和3 八斗大數(shù)據(jù) 數(shù)據(jù)挖掘聚類算法K 平 均 （ K - m e a n s ） 聚 類八

8、斗 八斗大數(shù)據(jù) 數(shù)據(jù)挖掘聚類算法K 平 均 （ K - m e a n s ） 聚 類八 八斗大數(shù)據(jù) 數(shù)據(jù)挖掘聚類算法K 平 均 （ K - m e a n s ） 聚 類八計(jì)算每個(gè)對象與這些中心的距離斗： 歐式距離 重新計(jì)算每個(gè)聚類的中心對象： 中心對象：均值 當(dāng)滿足一定條件，則算法終止： 損失函數(shù)：WCSS 步驟3：最小化簇內(nèi)對象到質(zhì)心的距離 步驟4：重新計(jì)算質(zhì)心，從而最小化WCSS 八斗大數(shù)據(jù) 數(shù)據(jù)挖掘聚類算法K 平 均 （ K - m e a n s ） 聚 類八斗 八斗大數(shù)據(jù) 數(shù)據(jù)挖掘聚類算法K 平 均 （ K - m e a n s ） 聚 類八斗 八斗大數(shù)據(jù) 數(shù)據(jù)挖掘聚類算法K 平 均 （ K - m e a n s ） 聚 類 八斗大數(shù)據(jù) 數(shù)據(jù)挖掘聚類算法K 平 均 （ K - m e a n s ） 聚 類 小 結(jié)八K的選擇斗 中心點(diǎn)的選擇 隨機(jī) 多輪隨機(jī)：選擇最小的WCSS 優(yōu)點(diǎn) 算法簡單、有效 時(shí)間復(fù)雜度：O(nkt) N個(gè)聚類對象，K個(gè)類，T個(gè)迭代次數(shù) 八斗大數(shù)據(jù) 數(shù)據(jù)挖掘聚類算法K 平 均 （ K - m e a n s ） 聚 類 小 結(jié)八處理非球面（凸型）聚類斗 密度，大小不同的聚類（受K的限制，難于發(fā)現(xiàn)自然的聚類） 部分解決方法：增加聚類個(gè)數(shù) 八斗大數(shù)據(jù) 數(shù)據(jù)挖掘聚類算法K - m e a n s