【文章內(nèi)容簡(jiǎn)介】 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 45 k中心點(diǎn)聚類方法 (續(xù) ) ? 找聚類中的代表對(duì)象 (中心點(diǎn) ) ? PAM (Partitioning Around Medoids, 1987) ? 首先為每個(gè)簇隨意選擇選擇一個(gè)代表對(duì)象 , 剩余的對(duì)象根據(jù)其與代表對(duì)象的距離分配給最近的一個(gè)簇 。 然后反復(fù)地用非代表對(duì)象來替代代表對(duì)象，以改進(jìn)聚類的質(zhì)量 ? PAM 對(duì)于較小的數(shù)據(jù)集非常有效 , 但不能很好地?cái)U(kuò)展到大型數(shù)據(jù)集 ? CLARA (Kaufmann amp。 Rousseeuw, 1990)抽樣 ? CLARANS (Ng amp。 Han, 1994): 隨機(jī)選樣 46 k中心點(diǎn)聚類方法 (續(xù) ) ? 基本思想： ? 首先為每個(gè)簇隨意選擇選擇一個(gè)代表對(duì)象 。 剩余的對(duì)象根據(jù)其與代表對(duì)象的距離分配給最近的一個(gè)簇 ? 然后反復(fù)地用非代表對(duì)象來替代代表對(duì)象 , 以改進(jìn)聚類的質(zhì)量 ? 聚類結(jié)果的質(zhì)量用一個(gè)代價(jià)函數(shù)來估算 , 該函數(shù)評(píng)估了對(duì)象與其參照對(duì)象之間的平均相異度 47 k中心點(diǎn)聚類方法 (續(xù) ) ? 為了判定一個(gè)非代表對(duì)象 Orandom 是否是當(dāng)前一個(gè)代表對(duì)象 Oj的好的替代 , 對(duì)于每一個(gè)非代表對(duì)象 p,考慮下面的四種情況： ? 第一種情況： p當(dāng)前隸屬于代表對(duì)象 Oj. 如果 Oj被 Orandom所代替 , 且 p離 Oi最近 , i≠j, 那么 p被重新分配給 Oi ? 第二種情況： p當(dāng)前隸屬于代表對(duì)象 Oj. 如果 Oj 被 Orandom代替 , 且 p離Orandom最近 , 那么 p被重新分配給 Orandom ? 第三種情況： p當(dāng)前隸屬于 Oi， i≠j。 如果 Oj被 Orandom代替，而 p仍然離 Oi最近，那么對(duì)象的隸屬不發(fā)生變化 ? 第四種情況： p當(dāng)前隸屬于 Oi， i≠j。 如果 Oj被 Orandom代替，且 p離Orandom最近，那么 p被重新分配給 Orandom 48 k中心點(diǎn)聚類方法 (續(xù) ) 重新分配給 Oi 2. 重新分配給 Orandom 3. 不發(fā)生變化 Orandom ● 數(shù)據(jù)對(duì)象 + 簇中心 替代前 替代后 圖 83 k中心點(diǎn)聚類代價(jià)函數(shù)的四種情況 + + + ● Orandom Oi Oj p + + + ● Orandom Oi Oj p + + + ● Orandom Oi Oj p + + + ● Orandom Oi Oj p 49 k中心點(diǎn)聚類方法 (續(xù) ) ? 算法 : k中心點(diǎn) (1) 隨機(jī)選擇 k個(gè)對(duì)象作為初始的代表對(duì)象； (2) repeat (3) 指派每個(gè)剩余的對(duì)象給離它最近的代表對(duì)象所代表的簇； (4) 隨意地選擇一個(gè)非代表對(duì)象 Orandom； (5) 計(jì)算用 Orandom代替 Oj的總代價(jià) S； (6) 如果 S0， 則用 Orandom替換 Oj， 形成新的 k個(gè)代表對(duì)象的集合； (7) until 不發(fā)生變化 50 PAM ? PAM (Partitioning Around Medoids) (Kaufman and Rousseeuw, 1987) ? 是最早提出的 k中心點(diǎn)聚類算法 ? 基本思想 : ? 隨機(jī)選擇 k個(gè)代表對(duì)象 ? 反復(fù)地試圖找出更好的代表對(duì)象 : 分析所有可能的對(duì)象對(duì)，每個(gè)對(duì)中的一個(gè)對(duì)象被看作是代表對(duì)象 , 而另一個(gè)不是 . 對(duì)可能的各種組合 , 估算聚類結(jié)果的質(zhì)量 51 PAM(續(xù) ) 0123456789100 1 2 3 4 5 6 7 8 9 10Total Cost = 20 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 K=2 Arbitrary choose k object as initial medoids 0123456789100 1 2 3 4 5 6 7 8 9 10Assign each remaining object to nearest medoids Randomly select a nonmedoid object,Oramdom Compute total cost of swapping 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 Total Cost = 26 Swapping O and Oramdom If quality is improved. Do loop Until no change 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 52 PAM(續(xù) ) ? 當(dāng)存在噪音和孤立點(diǎn)時(shí) , PAM 比 k平均方法更健壯 . 這是因?yàn)橹行狞c(diǎn)不象平均值那么容易被極端數(shù)據(jù)影響 ? PAM對(duì)于小數(shù)據(jù)集工作得很好 , 但不能很好地用于大數(shù)據(jù)集 ? 每次迭代 O(k(nk)2 ) 其中 n 是數(shù)據(jù)對(duì)象數(shù)目 , k 是聚類數(shù) ?基于抽樣的方法 , CLARA(Clustering LARge Applications) 53 CLARA (Clustering Large Applications) (1990) ? CLARA (Kaufmann and Rousseeuw in 1990) ? 不考慮整個(gè)數(shù)據(jù)集 , 而是選擇數(shù)據(jù)的一小部分作為樣本 ? 它從數(shù)據(jù)集中抽取多個(gè)樣本集 , 對(duì)每個(gè)樣本集使用 PAM, 并以最好的聚類作為輸出 ? 優(yōu)點(diǎn) : 可以處理的數(shù)據(jù)集比 PAM大 ? 缺點(diǎn) : ? 有效性依賴于樣本集的大小 ? 基于樣本的好的聚類并不一定是 整個(gè)數(shù)據(jù)集的好的聚類 , 樣本可能發(fā)生傾斜 ? 例如 , Oi是最佳的 k個(gè)中心點(diǎn)之一 , 但它不包含在樣本中 , CLARA將找不到最佳聚類 54 CLARANS (―Randomized‖ CLARA) (1994) ? CLARANS (A Clustering Algorithm based on Randomized Search) (Ng and Han’94) ? CLARANS將采樣技術(shù)和 PAM結(jié)合起來 ? CLARA在搜索的每個(gè)階段有一個(gè)固定的樣本 ? CLARANS任何時(shí)候都不局限于固定樣本 , 而是在搜索的每一步帶一定隨機(jī)性地抽取一個(gè)樣本 ? 聚類過程可以被描述為對(duì)一個(gè)圖的搜索 , 圖中的每個(gè)節(jié)點(diǎn)是一個(gè)潛在的解 , 也就是說 k medoids ? 相鄰節(jié)點(diǎn)：代表的集合只有一個(gè)對(duì)象不同 ? 在替換了一個(gè)代表對(duì)象后得到的聚類結(jié)果被稱為當(dāng)前聚類結(jié)果的鄰居 55 CLARANS(續(xù) ) ? 如果一個(gè)更好的鄰居被發(fā)現(xiàn) , CLARANS移到該鄰居節(jié)點(diǎn) , 處理過程重新開始 , 否則當(dāng)前的聚類達(dá)到了一個(gè)局部最優(yōu) ? 如果找到了一個(gè)局部最優(yōu) , CLARANS從隨機(jī)選擇的節(jié)點(diǎn)開始尋找新的局部最優(yōu) ? 實(shí)驗(yàn)顯示 CLARANS比 PAM和 CLARA更有效 ? CLARANS能夠探測(cè)孤立點(diǎn) ? 聚焦技術(shù)和空間存取結(jié)構(gòu)可以進(jìn)一步改進(jìn)它的性能 (Ester et al.’95) 56 第 7章 . 聚類分析 ? 什么是聚類（ Clustering） 分析 ? ? 聚類分析中的數(shù)據(jù)類型 ? 主要聚類方法分類 ? 劃分方法（ Partitioning Methods） ? 層次方法（ Hierarchical Methods） ? 基于密度的方法（ DensityBased Methods） ? 基于網(wǎng)格的方法（ GridBased Methods） ? 基于模型的聚類方法 （ ModelBased Clustering Methods） ? 孤立點(diǎn)分析（ Outlier Analysis） ? 小結(jié) 57 層次方法 ? 層次的聚類方法將數(shù)據(jù)對(duì)象組成一棵聚類的樹 ? 根據(jù)層次分解是自底向上 , 還是自頂向下形成 , 層次的聚類方法可以進(jìn)一步分為 凝聚的 (agglomerative)和 分裂的 (divisive)層次聚類 ? 純粹的層次聚類方法的聚類質(zhì)量受限于如下特點(diǎn)：一旦一個(gè)合并或分裂被執(zhí)行，就不能修正 ? 最近的研究集中于凝聚層次聚類和迭代重定位方法的集成 ? 使用距離矩陣作為聚類標(biāo)準(zhǔn) . 該方法不需要輸入聚類數(shù)目 k, 但需要終止條件 58 層次方法 (續(xù) ) ? 凝聚的 (agglomerative)和分裂的 (divisive)層次聚類圖示 Step 0 Step 1 Step 2 Step 3 Step 4 b d c e a a b d e c d e a b c d e Step 4 Step 3 Step 2 Step 1 Step 0 agglomerative (AGNES) divisive (DIANA) 59 AGNES (Agglomerative Nesting) ? 由 Kaufmann和 Rousseeuw提出 (1990) ? 已在一些統(tǒng)計(jì)分析軟件包中實(shí)現(xiàn) . 如 Splus ? 使用單鏈接 (SingleLink)方法和相異度矩陣 ? 合并具有最小相異度的節(jié)點(diǎn) ? 以非遞減的方式繼續(xù) ? 最終所有的節(jié)點(diǎn)屬于同一個(gè)簇 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 1060 DIANA (Divisive Analysis) ? 由 Kaufmann和 Rousseeuw提出 (1990) ? 已在一些統(tǒng)計(jì)分析軟件包中實(shí)現(xiàn) . 如 Splus ? 是 AGNES的逆 ? 最終每個(gè)節(jié)點(diǎn)自己形成一個(gè)簇 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 1061 層次方法 (續(xù) ) ? 四個(gè)廣泛采用的簇間距離度量方法 ? 最小距離： dmin(Ci,Cj) = min p∈ Ci, p’∈ Cj |pp’| ? 最大距離： dmax(Ci,Cj) = max p∈ Ci, p’∈ Cj |pp’| ? 平均值的距離： dmean(Ci,Cj) = | mi mj | ? 平均距離： davg(Ci,Cj) =∑ p∈ Ci ∑p’∈ Cj |pp’| /ninj 其中 , |pp’|是兩個(gè)對(duì)象 p和 p’之間的距離 mi是簇 Ci 的平均值， ni是簇 Ci中對(duì)象的數(shù)目 62 層次方法 (續(xù) ) ? 層次聚類的主要缺點(diǎn) ? 不具有很好的可伸縮性 : 時(shí)間復(fù)雜性至少是 O(n2), 其中 n 對(duì)象總數(shù) ? 合并或分裂的決定需要檢查和估算大量的對(duì)象或簇 ? 不能撤消已做的處理 , 聚類之間不能交換對(duì)象 . 如果某一步?jīng)]有很好地選擇合并或分裂的決定 , 可能會(huì)導(dǎo)致低質(zhì)量的聚類結(jié)果 63 層次方法 (續(xù) ) ? 改進(jìn)層次方法的聚類質(zhì)量的方法 : 將層次聚類和其他的聚類技術(shù)進(jìn)行集成 , 形成多階段聚類 ? BIRCH (1996): 使用 CFtree對(duì)對(duì)象進(jìn)行層次劃分 , 然后采用其他的聚類算法對(duì)聚類結(jié)果進(jìn)行求精 ? ROCK1999：基于簇間的互聯(lián)性進(jìn)行合并 ? CHAMELEON (1999): 使用動(dòng)態(tài)模型進(jìn)行層次聚類 ? CURE (1998):采用固定數(shù)目的代表對(duì)象來表示每個(gè)簇，然后依據(jù)一個(gè)指定的收縮因子向著聚類中心對(duì)它們進(jìn)行收縮 64 BIRCH (1996) ? Birch (Balanced Iterative Reducing and Clustering using Hierarchies): 利用層次方法的平衡迭代歸約和聚類由 Zhang, Ramakrishnan和 Livny 提出(SIGMOD’96) ? 兩個(gè)重要概念 ? 聚類特征 (Clustering Feature, CF) ? 聚類特征樹 (Clustering