一、原型聚類和層次聚類

原型聚類也稱基於原型的聚類(prototype-based clustering)，這類算法假設聚類結構能夠通過一組原型刻畫，先對原型進行初始化，然後對原型進行迭代更新求解。採用不同的原型表示、不同的求解方式，產生不同的算法。常用的原型聚類算法有k-means算法。

層次聚類(hierarchical clustering)是一種基於原型的聚類算法，試圖在不同層次對數據集進行劃分，從而形成樹形的聚類結構。數據集的劃分可採用"自底向上"的聚合策略，也可以採用"自頂向下"的分拆策略。層次聚類算法的優勢在於，可以通過繪製樹狀圖(dendrogram)，幫助我們使用可視化的方式來解釋聚類結果。層次聚類的另一個優點就是，它不需要事先指定簇的數量。

二、凝聚層次聚類

層次聚類可以分為凝聚(agglomerative)層次聚類和分裂(divsive)層次聚類。分裂層次聚類採用的就是"自頂而下"的思想，先將所有的樣本都看作是同一個簇，然後通過迭代將簇劃分為更小的簇，直到每個簇中只有一個樣本為止。凝聚層次聚類採用的是"自底向上"的思想，先將每一個樣本都看成是一個不同的簇，通過重複將最近的一對簇進行合併，直到最後所有的樣本都屬於同一個簇為止。

在凝聚層次聚類中，判定簇間距離的兩個標準方法就是單連接(single linkage)和全連接(complete linkage)。單連接，是計算每一對簇中最相似兩個樣本的距離，併合並距離最近的兩個樣本所屬簇。全連接，通過比較找到分佈於兩個簇中最不相似的樣本(距離最遠)，從而來完成簇的合併。

凝聚層次聚類除了通過單連接和全連接來判斷兩個簇之間的距離之外，還可以通過平均連接(average linkage)和ward連接。使用平均連接時，合併兩個簇所有成員間平均距離最小的兩個簇。使用ward連接，合併的是使得SSE增量最小的兩個簇。

三、全連接的凝聚層次聚類

基於全連接的凝聚層次聚類主要包括下面幾個步驟：

1、獲取所有樣本的距離矩陣

2、將每個數據點作為一個單獨的簇

3、基於最不相似(距離最遠)樣本的距離，合併兩個最接近的簇

4、更新樣本的距離矩陣

5、重複2到4，直到所有樣本都屬於同一個簇為止。

下面通過代表來實現基於全連接的凝聚層次聚類

1、獲取樣本

隨機產生5個樣本，每個樣本包含3個特徵(x、y、z)

2、獲取所有樣本的距離矩陣

通過SciPy來計算距離矩陣，計算每個樣本間兩兩的歐式距離，將矩陣矩陣用一個DataFrame進行保存，方便查看

3、獲取全連接矩陣的關聯矩陣

通過scipy的linkage函數，獲取一個以全連接作為距離判定標準的關聯矩陣(linkage matrix)。

第一列表的是簇的編號，第二列和第三列表示的是簇中最不相似(距離最遠)的編號，第四列表示的是樣本的歐式距離，最後一列表示的是簇中樣本的數量。

4、通過關聯矩陣繪製樹狀圖

使用scipy的dendrogram來繪製樹狀圖

通過上面的樹狀圖，可以直觀的發現。首先是s1和s5合併，s2和s3合併，然後s2、s3、s4合併，最後再和s1、s5合併。

5、結合樹狀圖和熱度圖

在實際應用中，可以將樹狀圖和熱力圖結合使用，通過不同的顏色來代表樣本矩陣中的獨立值。

通過熱力圖與樹狀圖結合，能夠更加直觀的發現特徵對於簇劃分的影響，不同顏色代表歐式距離的大小。

6、使用sklearn實現凝聚聚類

使用sklearn的AgglomerativeClustering可以很容易的實現凝聚聚類，需要設置返回簇的數量。