層次聚類簡(jiǎn)介

層次聚類主講：田鵬浩層次聚類層次聚類算法(HierarchicalClustering)將數(shù)據(jù)集劃分為一層一層的Clusters后面一層生成的Clusters基于前面一層的結(jié)果。層次聚類試圖在不同層次對(duì)數(shù)據(jù)集進(jìn)行劃分，從而形成樹形的聚類結(jié)構(gòu)。層次聚類層次聚類算法一般分為兩類：Divisive層次聚類：又稱自頂向下（top-down）的層次聚類，最開始所有的對(duì)象均屬于一個(gè)Cluster，每次按一定的準(zhǔn)則將某個(gè)Cluster

劃分為多個(gè)Cluster，如此往復(fù)，直至每個(gè)對(duì)象均是一個(gè)Cluster。Agglomerative層次聚類：又稱自底向上（bottom-up）的層次聚類，每一個(gè)對(duì)象最開始都是一個(gè)Cluster，每次按一定的準(zhǔn)則將最相近的兩個(gè)Cluster合并生成一個(gè)新的Cluster，如此往復(fù)，直至最終所有的對(duì)象都屬于一個(gè)Cluster。層次聚類左圖直觀的給出了層次聚類的思想以及以上兩種聚類策略的異同。層次聚類算法是一種貪心算法（GreedyAlgorithm），因其每一次合并或劃分都是基于某種局部最優(yōu)的選擇。層次聚類層次聚類優(yōu)點(diǎn)：距離和規(guī)則的相似度容易定義，限制少；不需要預(yù)先制定聚類數(shù)；可以發(fā)現(xiàn)類的層次關(guān)系；可以聚類成其它形狀。層次聚類缺點(diǎn)：計(jì)算復(fù)雜度太高；奇異值也能產(chǎn)生很大影響；算法很可能聚類成鏈狀。層次聚類HierarchicalK-means算法是“自頂向下”的層次聚類算法，用到了基于劃分的聚類算法K-means，算法思路如下：步驟1：首先，把原始數(shù)據(jù)集放到一個(gè)簇C，這個(gè)簇形成了層次結(jié)構(gòu)的最頂層。步驟2：使用K-means算法把簇C劃分成指定的K個(gè)子簇Ci，i=1,2,…,k，形成一個(gè)新的層。步驟3：對(duì)于步驟2所生成的K個(gè)簇，遞歸使用K-means算法劃分成更小的子簇，直到每個(gè)簇不能再劃分（只包含一個(gè)數(shù)據(jù)對(duì)象）或者滿足設(shè)定的終止條件。層次聚類如下圖，展示了一組數(shù)據(jù)進(jìn)行了二次K-means算法的過程：HierarchicalK-means算法一個(gè)很大的問題是，一旦兩個(gè)點(diǎn)在最開始被劃分到了不同的簇，即使這兩個(gè)點(diǎn)距離很近，在后面的過程中也不會(huì)被聚類到一起。層次聚類如左圖所示，紅色橢圓框中的對(duì)象聚類成一個(gè)簇可能是更優(yōu)的聚類結(jié)果，但是由于橙色對(duì)象和綠色對(duì)象在第一次K-means就被劃分到不同的簇，之后也不再可能被聚類到同一個(gè)簇。層次聚類層次聚類的合并算法通過計(jì)算兩類數(shù)據(jù)點(diǎn)間的相似性，對(duì)所有數(shù)據(jù)點(diǎn)中最為相似的兩個(gè)數(shù)據(jù)點(diǎn)進(jìn)行組合，并反復(fù)迭代這一過程。簡(jiǎn)單的說層次聚類的合并算法是通過計(jì)算每一個(gè)類別的數(shù)據(jù)點(diǎn)與所有數(shù)據(jù)點(diǎn)之間的距離來確定它們之間的相似性，距離越小，相似度越高。并將距離最近的兩個(gè)數(shù)據(jù)點(diǎn)或類別進(jìn)行組合，生成聚類樹。相比于HierarchicalK-means算法存在的問題，Agglomerativ