bigdata數(shù)據(jù)挖掘培訓(xùn)3-文庫(kù)吧資料
2025-01-25 02:56本頁(yè)面
【正文】 3 4 5 6 1 2 3 4 5 層次聚類的困難 ?合并或分裂點(diǎn)的選擇非常關(guān)鍵 ?一旦選定，下一步的處理將針對(duì)新的簇進(jìn)行，已做過(guò)的處理不能撤銷，簇間也不能交換對(duì)象。 ? PAM 適合于小數(shù)據(jù)集，但是在大數(shù)據(jù)集上效果不佳 ? CLARA (Kaufmann Rousseeuw, 1990) ? CLARANS (Ng Han, 1994):隨即抽樣 對(duì)比 k中心與 k均值 ?當(dāng)存在噪聲和離群點(diǎn)時(shí)， k中心法更魯棒 ? k中心法的執(zhí)行代價(jià)高于 k均值法 小結(jié)與回顧 ?聚類分析 ?同一數(shù)據(jù)，不同聚類方法可導(dǎo)致不同結(jié)果 ?距離的度量 ?基于劃分的聚類 ? k均值法 K均值方法 ?給定 k : ? k個(gè)點(diǎn)作為初始的質(zhì)心 ? ? 3. 將每個(gè)點(diǎn)指派到最近（相似）的簇集 ? 4. 重新計(jì)算每個(gè)簇的均值，即更新質(zhì)心 ? 不再發(fā)生變化 . K均值方法 ?例 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 10k均值的優(yōu)點(diǎn) ?簡(jiǎn)單、有效 ?可用于各種數(shù)據(jù)類型 ?（但并非適合所有數(shù)據(jù)類型） k均值的局限（缺點(diǎn)） ? 不能處理： ? 不同尺寸的簇 ? 不同密度的簇 ? 非球形的簇 ? 對(duì)含離群點(diǎn)的數(shù)據(jù)聚類時(shí)也有問(wèn)題 聚類分析 ? 什么是聚類分析 ? ? 聚類分析中的數(shù)據(jù)類型 ? 主要的聚類方法分類 ? 劃分方法 ? 層次方法 層次聚類 Hierarchical Clustering: Nested Clusters Dendrogram 樹狀圖 1 2 3 4 5 6 1 2 3 4 5 3 6 2 5 4 100 . 0 50 . 10 . 1 50 . 2層次方法 ?將嵌套定義的簇集組成一棵層次形式的樹 ?按照分裂方式可分為： ?凝聚的 ? 把每個(gè)點(diǎn)都作為一個(gè)簇，開(kāi)始聚類 ? 每一步合并兩個(gè)最近的簇，直到只剩下一個(gè)簇 ?分裂的 ? 所有的點(diǎn)看做一個(gè)簇 ? 每一步，分裂一個(gè)簇， 直到每個(gè)點(diǎn)都是一個(gè)簇 層次聚類方法 ? 利用相似度或距離矩陣作為聚類標(biāo)準(zhǔn) . 這種方法不需要提供k值，但是必須提供中止條件 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 凝聚的 (AGNES) 分裂的 (DIANA) AGNES (凝聚的層次聚類 ) ? Kaufmann and Rousseeuw (1990) ? 將具有最少相異性的點(diǎn)合并 ? 將這些簇合并成越來(lái)越大的簇 ? 直到所有終結(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 10DIANA (分裂的層次聚類 ) ? Kaufmann and Rousseeuw (1990) ?與 AGNES剛好相反 ?直到每個(gè)對(duì)象自成一簇 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 10基本層次凝聚聚類 ? 基本算法簡(jiǎn)單直接： 1. 計(jì)算相似度矩陣（或鄰近矩陣） 2. 以每個(gè)點(diǎn)為一個(gè)簇 3. Repeat 4. 合并最近的兩個(gè)簇 5. 更新相似度矩陣 6. Until 僅剩下一個(gè)簇 ? 關(guān)鍵操作 : 計(jì)算兩個(gè)簇間的相似度 ? 有多種方法度量距離或者相似度 簡(jiǎn)單直接的凝聚聚類 ? 初始，每個(gè)點(diǎn)都為一個(gè)簇集，計(jì)算鄰近矩陣 p1 p3 p5 p4 p2 p1 p2 p3 p4 p5 . . . . . . Proximity Matrix 中間過(guò)程 ? 經(jīng)若干次合并后 C1 C4 C2 C5 C3 C2 C1 C1 C3 C5 C4 C2 C3 C4 C5 Proximity Matrix 中間過(guò)程 ? 合并 C2與 C5，更新矩陣 C1 C4 C2 C5 C3 C2 C1 C1 C3 C5 C4 C2 C3 C4 C5 Proximity Matrix 合并后 ? 問(wèn)題： “如何更新矩陣 ?” C1 C4 C2 U C5 C3 ? ? ? ? ? ? ? C2 U C5 C1 C1 C3 C4 C2 U C5 C3 C4 Proximity Matrix 如何度量簇間距離（相似性） p1 p3 p5 p4 p2 p1 p2 p3 p4 p5 . . . . . . Similarity? ? 最小距離 ? 最大距離 ? 均值距離 ? 中心點(diǎn)間距離 ? 其他 Proximity Matrix How to Define InterCluster Similarity p1 p3 p5 p4 p2 p1 p2 p3 p4 p5 . . . . . . Proximity Matrix ? 最小距離 ? 最大距離 ? 均值距離 ? 中心點(diǎn)間距離 ? 其他 How to Define InterCluster Similarity p1 p3 p5 p4 p2 p1 p2 p3 p4 p5 . . . . . . Proximity Matrix ? 最小距離 ? 最大距離 ? 均值距離 ? 中心點(diǎn)間距離 ? 其他 How to Define InterCluster Similarity p1 p3 p5 p4 p2 p1 p2 p3 p4 p5 . . . . . . Proximity Matrix ? 最小距離 ? 最大距離 ? 均值距離 ? 中心點(diǎn)間距離 ? 其他 兩個(gè)極端 折中 How to Define InterCluster Similarity p1 p3 p5 p4 p2 p1 p2 p3 p4 p5 . . . . . . Proximity Matrix ? 最小距離 ? 最大距離 ? 均值距離 ? 中心點(diǎn)間距離 ? 其他 ? ? 最近鄰聚類與單連接算法 ? 最近鄰：以最小距離度量簇間距離 ? 單連接：最近的簇間距離超過(guò)某個(gè)閾值聚類就會(huì)終止 I1 I2 I3 I4 I5I1 1 . 0 0 0 . 9 0 0 . 1 0 0 . 6 5 0 . 2 0I2 0 . 9 0 1 . 0 0 0 . 7 0 0 . 6 0 0 . 5 0I3 0 . 1 0 0 . 7 0 1 . 0 0 0
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號(hào)-1