【正文】 第 4章 聚類分析 概述 基于劃分的聚類算法 層次聚類算法 基于密度的聚類算法 基于圖的聚類算法 一趟聚類算法 基于原型的聚類算法 聚類算法評價 概述 簡單地描述， 聚類 (Clustering)是將數(shù)據(jù)集劃分為若干相似對象組成的多個組 (group)或簇 (cluster)的過程，使得 同一組中對象間的相似度最大化，不同組中對象間的相似度最小化 ?；蛘哒f一個簇(cluster)就是由彼此相似的一組對象所構(gòu)成的集合，不同簇中的對象通常不相似或相似度很低。 類間相似度最小化(距離最大化 ) 類內(nèi)相似度最大化(距離最小化 ) 從 機器學習 的角度看，聚類是一種無監(jiān)督的機器學習方法，即事先對數(shù)據(jù)集的分布沒有任何的了解，它是將物理或抽象對象的集合組成為由類似的對象組成的多個類的過程。聚類方法的 目的 是尋找數(shù)據(jù)中：潛在的自然分組結(jié)構(gòu)和感興趣的關系。 聚類分析中“簇”的 特征 ： ? 聚類所說的簇不是事先給定的，而是根據(jù)數(shù)據(jù)的相似性和距離來劃分 ? 聚的數(shù)目和結(jié)構(gòu)都沒有事先假定 注意：聚類也可以是不明確的 有多少聚類？ 四個類 2個類 六個類 聚類分析正在蓬勃發(fā)展，廣泛應用于一些探索性領域 ,如 統(tǒng)計學與模式分析，金融分析，市場營銷，決策支持，信息檢索， WEB挖掘，網(wǎng)絡安全，圖象處理，地質(zhì)勘探、城市規(guī)劃，土地使用、空間數(shù)據(jù)分析，生物學，天文學，心理學，考古學 等。 聚類分析研究的主要內(nèi)容 ? (1) 模式表示 (包括特征提取和 /或選擇 )； ? (2) 適合于數(shù)據(jù)領域的模式相似性定義； ? (3) 聚類或劃分算法； ? (4) 數(shù)據(jù)摘要； ? (5) 輸出結(jié)果的評估。 特征選擇 /提取 模式相似性計算 劃分 模式表示 模式 聚類結(jié)果 反饋回路 數(shù)據(jù)挖掘?qū)垲愃惴ǖ囊? 聚類是一個富有挑戰(zhàn)性的研究領域，數(shù)據(jù)挖掘?qū)垲惖?典型要求如下 ： (1)可伸縮性 (Scalability) (2)處理不同類型屬性的能力 (3)發(fā)現(xiàn)任意形狀的聚類 (4)用于決定輸入?yún)?shù)的領域知識最小化 (5)對于輸入記錄順序不敏感 (6)高維性 (7)處理噪音和異常數(shù)據(jù)的能力 (8)基于約束的聚類 (9)可解釋性 典型聚類方法簡介 ? 劃分方法 (partitioning methods)基于質(zhì)心 (Kmeans)、中心的劃分方法 ? 層次的方法 (hierarchical methods)BIRCH 、 ROCK 、 CURE ? 基于密度的方法 DBSCAN、 OPTICS ? 基于圖的方法 Chameleon、 SNN ? 基于網(wǎng)格的方法 (gridbased methods) STING 、 WaveCluster 、 CLIQUE ? 基于模型的方法 (modelbased methods)EM、 COBWEB、神經(jīng)網(wǎng)絡 ? 其他聚類方法 譜聚類算法 (spectral clustering)、蟻群聚類算法等 基于劃分的聚類 原始數(shù)據(jù)點 基于劃分的聚類結(jié)果 基于層次的聚類 p4p1p3p 2 p4 p1 p3 p 2 p4p1 p2 p3p4p1 p2 p3傳統(tǒng)的層次聚類 非傳統(tǒng)的基于層次的聚類 非傳統(tǒng)的樹圖 傳統(tǒng)的基于層次的樹圖 基于劃分的聚類算法 給定一個 n 個對象或元組的數(shù)據(jù)庫，一個劃分方法構(gòu)建數(shù)據(jù)的 k個劃分，每個劃分表示一個聚類，并且 k=n。也就是說，它將數(shù)據(jù)劃分為 k個組，同時滿足如下的要求： (1)每個組至少包含一個對象； (2)每個對象必須屬于且只屬于一個組。 劃分式聚類算法需要預先指定簇數(shù)目或簇中心，通過反復迭代運算，逐步降低目標函數(shù)的誤差值，當目標函數(shù)值收斂時，得到最終聚類結(jié)果。這類方法分為 基于質(zhì)心的(Centroidbased)劃分方法 和 基于中心的 (Medoidbased)劃分方法 。 基本 kmeans聚類算法 kmeans聚類算法： (1)從數(shù)據(jù)集 D中任意選擇 k個對象作為初始簇中心； (2) repeat (3) for 數(shù)據(jù)集 D中每個對象 P do (4) 計算對象 P到 k個簇中心的距離 (5) 將對象 P指派到與其最近 (距離最短 )的簇； (6) end for (7) 計算每個簇中對象的均值，做為新的簇的中心； (8) until k個簇的簇中心不再發(fā)生變化 Kmeans算法采用 k,mean來表示一個簇 kmeans聚類算法示例 1 ? 例 對 表 41中二維數(shù)據(jù)，使用 kmeans算法將其劃分為 2個簇，假設初始簇中心選為 P7(4， 5)， P10(5， 5)。 表 41 kmeans聚類過程示例數(shù)據(jù)集 1 ? 解：圖 42 顯示了對于給定的數(shù)據(jù)集 kmeans聚類算法的執(zhí)行過程。 (1)根據(jù)題目，假設劃分的兩個簇分別為 C1和 C2，中心分別為 (4， 5)和(5， 5)，下面計算 10個樣本到這 2個簇中心的距離，并將 10個樣本指派到與其最近的簇： (2)第一輪迭代結(jié)果如下： 屬于簇 C1的樣本有： {P7， P1， P2， P4， P5， P8} 屬于簇 C2的樣本有： {P10， P3， P6， P9} 重新計算新的簇的中心，有： C1的中心為 (， )， C2的中心為 (， ) P1 P2 P3 P4 P5 P6 P7 P8 P9 P10 x 3 3 7 4 3 8 4 4 7 5 y 4 6 3 7 8 5 5 1 4 5 kmeans聚類算法示例 2 (3)繼續(xù)計算 10個樣本到新的簇的中心的距離，重新分配到新的簇中，第二輪迭代結(jié)果如下： 屬于簇 C1的樣本有： { P1， P2， P4， P5， P7， P10} 屬于簇 C2的樣本有： { P3， P6， P8， P9} 重新計算新的簇的中心，有： C1的中心為 (， )， C2的中心為 (， ) (4)繼續(xù)計算 10個樣本到新的簇的中心的距離，重新分配到新的簇中，發(fā)現(xiàn)簇中心不再發(fā)生變化，算法終止。 0123456789100 1 2 3 4 5 6 7 8 9 100123456789100 1 2 3 4 5 6 7 8 9 100123456789100 1 2 3 4 5 6 7 8 9 100123456789100 1 2 3 4 5 6 7 8 9 10圖 42 kmeans算法聚類過程示例 kmeans算法描述容易、實現(xiàn)簡單、快速，但存在不足： (1)簇的個數(shù)難以確定； (2) 聚類結(jié)果對初始值的選擇較敏感； (3)這類算法采用爬山式技術尋找最優(yōu)解 ,容易陷入局部最優(yōu)值； (4)對噪音和異常數(shù)據(jù)敏感； (5)不能用于發(fā)現(xiàn)非凸形狀的簇，或具有各種不同大小的簇。 (a) 大小不同的簇 (b) 形狀不同的簇 圖 基于質(zhì)心的劃分方法不能識別的數(shù)據(jù) 二分 kmeans算法 ? 二分 Kmeans算法是基本 kmeans算法的直接擴充，基于如下想法：為了得到 k個簇，將所有點的集合分裂成兩個簇，從中選擇一個繼續(xù)分裂，如此重復直到產(chǎn)生 k個簇。算法詳細描述如下： 初始化簇表，使之包含由所有的點組成的簇。 Repeat 從簇表中選取一個簇。 { 對選定的簇進行多次二分“試驗” } For i=1 to 試驗次數(shù) do 使用基于基本 kmeans，二分選定的簇 End for 從二分試驗中選擇具有最小總 SSE的兩個簇。 將這兩個簇添加到簇表中 Until 簇表中包含 k個簇 kmeans聚類算法的拓展 1 ? 對于聚類分析而言，聚類表示和數(shù)據(jù)對象之間相似度的定義是最基礎的問題，直接影響數(shù)據(jù)聚類的效果。 ? 這里介紹一種簡單的聚類表示方法，并對 Minkowski距離進行推廣以使聚類算法可以有效處理含分類屬性的數(shù)據(jù)。 ? 假設數(shù)據(jù)集 D有 m個屬性，其中有 mC個分類屬性和 mN個數(shù)值屬性， m=mC+mN ，用 Di表示第 i個屬性取值的集合。 定義 41 給定簇 C， ， a 在 C中關于 Di 的頻度定義為 C在 Di上的投影中包含 a 的次數(shù)： 定義 42 給定簇 C， C的摘要信息 CSI(Cluster Summary Information)定義為： ，其中 為 C的大小 , 由分類屬性中不同取值的頻度信息和數(shù)值型屬性的質(zhì)心兩部分構(gòu)成，即： }.,{)(| aDo b je c tCo b je c to b je c taF r e q iDC i ???},{ S u m m a r ynC S I ? || Cn?)},(,1},))(,{(,{21|NCCCimmmmCiDCiicccC e nmiDaaF r e qaS t a tC e nS t a tS u mma r y???????????? kmeans聚類算法的拓展 2 iDa?定義 43 給定 D的簇 C、 和 ,對象 與 ， x0。 (1)對象 p， q在屬性 i上的差異程度 (或距離 ) 定義為： 對于分類屬性或二值屬性， 。 對于連續(xù)數(shù)值屬性或順序?qū)傩裕? ； (2)兩個對象 p， q間的差異程度 (或距離 ) 定義為： 。 kmeans聚類算法的拓展 3 1C 2C ],[ 21 mpppp ??],[ 21 mqqqq ??),( ii qpd if?????????????iiiiiiiiii qpqpqpqpqpd i f10101),(iiii qpqpd i f ??),(),( qpdxmixii qpd i fqpd/11),(),( ????????? ??(3)對象 p與簇 C間的距離 定義為 p與簇 C的摘要之間的距 離： 。 這里 為 p與 C在屬性 上的距離，對于分類屬性 其值定義為 p與 C中每個對象在屬性 上的距離的算術平均值，即 ；對于數(shù)值屬性 其值定義為 。 (4) 簇 C1與 C2間的距離 定義為兩個簇的摘要間的距離： 。 kmeans聚類算法的拓展 4 ),( Cpdxmixii Cpd i fCpd/11),(),( ????????? ??),( ii Cpd if iD iDiDCpFr eqCpdi f iDCii i)(1),( |?? iDiiii cpCpd i f ??),(),( 21 CCdxmixii CCd i fCCd/11)2()1(