【正文】 的大小 (即將圖劃分成兩個(gè)大致相等的部分的邊的加權(quán)和 )表示。 Chameleon聚類算法 利用動(dòng)態(tài)模型的層次聚類算法 Chameleon算法是一種基于圖的層次聚類算法，該算法利用基于 圖 的方法得到的初始數(shù)據(jù)劃分與一種新穎的 層次聚類 方案相結(jié)合，使用簇間的接近性和互連性概念以及簇的局部建模來(lái)高質(zhì)量地發(fā)現(xiàn)具有 不同形狀、大小和密度 的簇。 (3) 定義核心對(duì)象并構(gòu)建環(huán)繞它們的簇。可以利用為稀疏圖開(kāi)發(fā)的有效圖劃分算法來(lái)進(jìn)行稀疏化。 最終識(shí)別出三個(gè)簇， P9為噪聲點(diǎn)。類似地， S和 R從 O是“密度可達(dá)”的； O、 R和 S均是“密度相連”的。 密度相連： 如果存在對(duì)象 O∈ D，使對(duì)象 p和 q都是從 O關(guān)于 Eps和MinPts密度可達(dá)的，那么對(duì)象 p到 q是關(guān)于 Eps和 MinPts密度相連的 (densityconnected)。 邊界點(diǎn)： 邊界點(diǎn)不是核心點(diǎn)，但落在某個(gè)核心點(diǎn)的鄰域內(nèi)。 數(shù)據(jù)集中特定點(diǎn)的密度通過(guò)該點(diǎn)的 Eps半徑之內(nèi)包含的點(diǎn)數(shù) (包括點(diǎn)本身 )來(lái)估計(jì)?；诿芏鹊姆椒ǖ湫偷陌? DBSCAN (DensityBased Spatial Clustering of Applications with Noise) OPTICS(Ordering Points to Identify the Clustering Structure) 圖 基于密度的聚類算法可聚類的形狀 DBSCAN算法 1 DBSCAN是一種基于高密度連通區(qū)域的聚類方法，該算法將具有足夠高密度的區(qū)域劃分為簇，并在具有噪聲的空間數(shù)據(jù)庫(kù)中發(fā)現(xiàn)任意形狀的簇，它將簇定義為密度相連的點(diǎn)的最大的集合。然后在這個(gè)稀疏圖上執(zhí)行凝聚層次聚類。然而， C2中的事務(wù) {a， b， f}與 C1中事務(wù) {a， b， c}之間的鏈接數(shù)僅為 3(其共同的鄰居為 {a， b， d}， {a， b， e}和 {a， b，g})。很明顯，僅僅使用 Jaccard系數(shù)，無(wú)法得到所期望的簇。假設(shè)我們首先只考慮點(diǎn)間的相似度而忽略鄰域信息。 兩個(gè) “點(diǎn) ”即兩個(gè)事務(wù) 和 之間的相似度用 Jaccard系數(shù) 定義為： ||||),(jijiji TTTTTTs i m???例 44同時(shí)使用點(diǎn)間相似度和鄰域鏈接信息的影響分析示例 假定一個(gè)購(gòu)物籃數(shù)據(jù)庫(kù)包含關(guān)于商品 a,b,…,g 的事務(wù)記錄。這些點(diǎn)描述和捕捉到了簇的形狀。 算法描述如下： (1)從源數(shù)據(jù)對(duì)象中抽取一個(gè)隨機(jī)樣本 S； (2)將樣本 S劃分為一組分塊； (3)對(duì)每個(gè)劃分局部地聚類； (4)通過(guò)隨機(jī)取樣剔除孤立點(diǎn)。 ③ 不用單個(gè)質(zhì)心或?qū)ο髞?lái)代表一個(gè)簇，而是選擇了數(shù)據(jù)空間中固定數(shù)目的具有代表性的點(diǎn)。 (6) 判斷此時(shí)存儲(chǔ)潛在離群點(diǎn)的磁盤(pán)是否已滿，如果沒(méi)有滿則轉(zhuǎn) (2)繼續(xù)掃描下一個(gè)數(shù)據(jù)點(diǎn)。 (3) 判斷內(nèi)存是否溢出，如果沒(méi)有溢出轉(zhuǎn) (4)，如果溢出轉(zhuǎn) (5)。 BIRCH算法描述 ? BIRCH算法主要分為四個(gè)階段：第一個(gè)階段對(duì)整個(gè)數(shù)據(jù)集進(jìn)行掃描，根據(jù)給定的初始閾值 T建立一棵初始聚類特征樹(shù)；第二階段通過(guò)提升閾值T重建 CF樹(shù)，得到一棵壓縮的 CF樹(shù)。 (2) 比較計(jì)算出的距離是否小于閾值 T，如果小于則當(dāng)前條目吸收該數(shù)據(jù)點(diǎn)；如果距離大于等于閾值 T，則轉(zhuǎn) (3)。給定簇中 n個(gè) m維對(duì)象或點(diǎn) ，則該簇的 CF定義如下 假定在簇 中有三個(gè)點(diǎn) (2， 5)， (3， 2)和 (4， 3)。 自頂向下分解層次聚類方法 (或分裂層次聚類 )。 FALSE:4, TRUE:1}。 FALSE:3,TRUE:2 }；簇 C2 包含的記錄集合為 {4,5, 8,12, 14}，摘要信息為 C2:{overcast:1,rainy:1,sunny:2。 簇 C3:{ overcast:2,rainy:1,sunny:2。 FALSE:3,TRUE:2 }。 FALSE:1,TRUE:3}。 FALSE:5,TRUE:3} (3)重新劃分對(duì)象到最近的簇，第二次迭代結(jié)果： 記錄號(hào) 到簇 C1的距離 到簇 C2的距離 到簇 C3的距離 所屬簇標(biāo)號(hào) 1 3 2 3 3 3 4 1 5 1 6 2 7 2 8 1 9 2 10 3 11 2 12 1 13 3 14 1 ksummary算法示例 4 第二次劃分后三個(gè)簇的摘要信息更新為 簇 C1:{ overcast:1,rain:3,sunny:1 。 FALSE:2,TRUE:1}。有兩條記錄 p， q及兩個(gè)簇 C1， C2的信息如下，分別求出記錄和簇彼此之間的距離： p={男，廣州， 18} ， q={女，深圳， 20} C1={男： 25，女： 5；廣州： 20，深圳： 6，韶關(guān)： 4； 19} C2={男： 3，女： 12；汕頭： 12，深圳： 1，湛江： 2； 24} ? 按定義 43，取 x=1得到的各距離如下： d(p， q)=1+1+(2018)=4 d(p， C1)=(125/30)+(120/30)+(1918)= d(p， C2)=(13/15)+(10/15)+(2418)= d(q,C1)=(15/30)+(16/30)+(2019)=79/30 d(q,C2)=(112/15)+(11/15)+(2420)=77/15 d(C1,C2)=1(25*3+5*12)/(30*15)+16*1/(30*15)+(2419)=1003/150≈ kmeans聚類算法的拓展 — ksummary ksummary算法由幾個(gè)主要步驟完成 : (1)從數(shù)據(jù)集 D中任意選擇 k個(gè)對(duì)象，并創(chuàng)建 k個(gè)簇的摘要信息 CSI； (2) repeat (3) for 數(shù)據(jù)集 D中每個(gè)對(duì)象 P do (4) 計(jì)算對(duì)象 P到 k個(gè)簇中心的距離 (5) 將對(duì)象 P指派到與其最近 (距離最短 )的簇； (6) end for (7) 更新簇的摘要信息 CSI； (8) until k個(gè)簇的摘要信息不再發(fā)生變化 ksummary算法示例 1 例 43 對(duì)于表 42所示的數(shù)據(jù)集，請(qǐng)使用 ksummary算法將其劃分為 3個(gè)簇。 (4) 簇 C1與 C2間的距離 定義為兩個(gè)簇的摘要間的距離： 。 (1)對(duì)象 p， q在屬性 i上的差異程度 (或距離 ) 定義為： 對(duì)于分類屬性或二值屬性， 。 將這兩個(gè)簇添加到簇表中 Until 簇表中包含 k個(gè)簇 kmeans聚類算法的拓展 1 ? 對(duì)于聚類分析而言，聚類表示和數(shù)據(jù)對(duì)象之間相似度的定義是最基礎(chǔ)的問(wèn)題，直接影響數(shù)據(jù)聚類的效果。 (a) 大小不同的簇 (b) 形狀不同的簇 圖 基于質(zhì)心的劃分方法不能識(shí)別的數(shù)據(jù) 二分 kmeans算法 ? 二分 Kmeans算法是基本 kmeans算法的直接擴(kuò)充，基于如下想法：為了得到 k個(gè)簇，將所有點(diǎn)的集合分裂成兩個(gè)簇，從中選擇一個(gè)繼續(xù)分裂，如此重復(fù)直到產(chǎn)生 k個(gè)簇。 基本 kmeans聚類算法 kmeans聚類算法： (1)從數(shù)據(jù)集 D中任意選擇 k個(gè)對(duì)象作為初始簇中心； (2) repeat (3) for 數(shù)據(jù)集 D中每個(gè)對(duì)象 P do (4) 計(jì)算對(duì)象 P到 k個(gè)簇中心的距離 (5) 將對(duì)象 P指派到與其最近 (距離最短 )的簇； (6) end for (7) 計(jì)算每個(gè)簇中對(duì)象的均值，做為新的簇的中心； (8) until k個(gè)簇的簇中心不再發(fā)生變化 Kmeans算法采用 k,mean來(lái)表示一個(gè)簇 kmeans聚類算法示例 1 ? 例 對(duì) 表 41中二維數(shù)據(jù)，使用 kmeans算法將其劃分為 2個(gè)簇，假設(shè)初始簇中心選為 P7(4， 5)， P10(5， 5)。 特征選擇 /提取 模式相似性計(jì)算 劃分 模式表示 模式 聚類結(jié)果 反饋回路 數(shù)據(jù)挖掘?qū)垲愃惴ǖ囊? 聚類是一個(gè)富有挑戰(zhàn)性的研究領(lǐng)域，數(shù)據(jù)挖掘?qū)垲惖?典型要求如下 ： (1)可伸縮性 (Scalability) (2)處理不同類型屬性的能力 (3)發(fā)現(xiàn)任意形狀的聚類 (4)用于決定輸入?yún)?shù)的領(lǐng)域知識(shí)最小化 (5)對(duì)于輸入記錄順序不敏感 (6)高維性 (7)處理噪音和異常數(shù)據(jù)的能力 (8)基于約束的聚類 (9)可解釋性 典型聚類方法簡(jiǎn)介 ? 劃分方法 (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)絡(luò) ? 其他聚類方法 譜聚類算法 (spectral clustering)、蟻群聚類算法等 基于劃分的聚類 原始數(shù)據(jù)點(diǎn) 基于劃分的聚類結(jié)果 基于層次的聚類 p4p1p3p 2 p4 p1 p3 p 2 p4p1 p2 p3p4p1 p2 p3傳統(tǒng)的層次聚類 非傳統(tǒng)的基于層次的聚類 非傳統(tǒng)的樹(shù)圖 傳統(tǒng)的基于層次的樹(shù)圖 基于劃分的聚類算法 給定一個(gè) n 個(gè)對(duì)象或元組的數(shù)據(jù)庫(kù)，一個(gè)劃分方法構(gòu)建數(shù)據(jù)的 k個(gè)劃分，每個(gè)劃分表示一個(gè)聚類，并且 k=n。 類間相似度最小化(距離最大化 ) 類內(nèi)相似度最大化(距離最小化 ) 從 機(jī)器學(xué)習(xí) 的角度看，聚類是一種無(wú)監(jiān)督的機(jī)器學(xué)習(xí)方法，即事先對(duì)數(shù)據(jù)集的分布沒(méi)有任何的了解，它是將物理或抽象對(duì)象的集合組成為由類似的對(duì)象組成的多個(gè)類的過(guò)程。或者說(shuō)一個(gè)簇(cluster)就是由彼此相似的一組對(duì)象所構(gòu)成的集合，不同簇中的對(duì)象通常不相似或相似度很低。 聚類分析研究的主要內(nèi)容 ? (1) 模式表示 (包括特征提取和 /或選擇 )； ? (2) 適合于數(shù)據(jù)領(lǐng)域的模式相似性定義； ? (3) 聚類或劃分算法； ? (4) 數(shù)據(jù)摘要； ? (5) 輸出結(jié)果的評(píng)估。這類方法分為 基于質(zhì)心的(Centroidbased)劃分方法 和 基于中心的 (Medoidbased)劃分方法 。 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算法聚類過(guò)程示例 kmeans算法描述容易、實(shí)現(xiàn)簡(jiǎn)單、快速，但存在不足： (1)簇的個(gè)數(shù)難以確定； (2) 聚類結(jié)果對(duì)初始值的選擇較敏感； (3)這類算法采用爬山式技術(shù)尋找最優(yōu)解 ,容易陷入局部最優(yōu)值； (4)對(duì)噪音和異常數(shù)據(jù)敏感； (5)不能用于發(fā)現(xiàn)非凸形狀的簇，或具有各種不同大小的簇。 { 對(duì)選定的簇進(jìn)行多次二分“試驗(yàn)” } For i=1 to 試驗(yàn)次數(shù) do 使用基于基本 kmeans，二分選定的簇 End for 從二分試驗(yàn)中選擇具有最小總 SSE的兩個(gè)簇。 定義 41 給定簇 C， ， a 在 C中關(guān)于 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