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