關于層次聚類算法的python實現(xiàn)

from scipy.cluster import hierarchy

0.層次聚類的概念

層次聚類和k-means一樣都是很常用的聚類方法撞蚕。層次聚類是對群體的劃分盛霎，最終將樣本劃分為樹狀的結構铆农。他的基本思路是每個樣本先自成一類嫁怀，然后按照某種規(guī)則進行合并锅铅，直到只有一類或者某一類的樣本只有一個點刃唐。層次聚類又分為自底而上的聚合層次聚類和自頂而下的分裂層次聚類羞迷。

0.1 聚合層次聚類

每一個點初始為1類，得到N(樣本點個數(shù))類画饥，計算每一類之間的距離衔瓮，計算方法有很多，具體可以參考距離的計算方法抖甘。聚合層次聚類方法的終止條件是所有樣本點都處于同一類了热鞍，或者兩類之間的距離超過設置的某個閾值。大多數(shù)層次聚類都是聚合層次聚類衔彻。

0.2 分裂層次聚類

和聚合層次聚類是反著的薇宠，屬于自上而下的一種聚類方法。剛開始的時候所有的樣本點都位于同一類艰额，然后一步步劃分澄港，終止條件是所有的樣本點都位于單獨的一類，或者兩類之間的距離超過設置的某個閾值柄沮。
下面這個圖可以比較好的說明這個過程：

層次聚類的兩種方法

1.凝聚層次聚類算法步驟

1.1 算法過程

1）N個樣本單獨成類回梧，G1(0)、G2(0)祖搓、G3(0)狱意、……、GN(0)拯欧，0代表初始狀態(tài)详囤。
2）更新距離矩陣D(n)，找出D(n)中最小值镐作，把對應的兩類合并為1類藏姐。
3）更新距離矩陣D(n+1)蚓再，重復步驟2-3。

當兩類之間的最小距離小于給定的閾值或者所有樣本都單獨成類的時候包各，結束算法摘仅。

1.2算法案例

有個老師帶了五個學生，想給學生分組问畅，讓他們分組學習娃属，采用層次聚類來對學生進行聚類，基礎數(shù)據(jù)如下圖护姆。

學生基礎數(shù)據(jù)

先來算距離D(0)矾端，就采用歐式距離就好了。

初始距離矩陣

找到最小的那兩個合并為1類卵皂。

合并后的新數(shù)據(jù)

然后計算更新后的距離D(1)

合并的后新距離

以后的以此類推：

聚類的整體過程

我們看到其實124是一類秩铆，35是一類。
畫出圖來就是下面這個格式：

聚類結果

3.Python處理層次聚類的包

用的是在scipy.cluster里的hierarchy方法灯变，下面來看代碼殴玛，支持hierarchical clustering 和 agglomerative clustering。
首先來看一些基本函數(shù)的用法

linkage
scipy.cluster.hierarchy.linkage(data,method = 'single')
method 參數(shù)是類距離的計算公式
singele 兩個類之間最短的點的距離
complete 兩個類之間最長距離的點的距離
centroid 兩個類所有點的中點的距離
pdist計算樣本點之間的兩兩距離
scipy.cluster.hierarchy.distance.pdist(data, metric='euclidean')
metric參數(shù)是求距離的方法添祸，默認是歐氏距離滚粟，可選的還有：
‘braycurtis’, ‘canberra’, ‘chebyshev’, ‘cityblock’, ‘correlation’, ‘cosine’, ‘dice’, ‘euclidean’, ‘hamming’, ‘jaccard’, ‘jensenshannon’, ‘kulsinski’, ‘mahalanobis’, ‘matching’, ‘minkowski’, ‘rogerstanimoto’, ‘russellrao’, ‘seuclidean’, ‘sokalmichener’, ‘sokalsneath’, ‘sqeuclidean’, ‘yule’
關于求距離的函數(shù)我可能還會再更一篇文章，感興趣的朋友可以等一下刃泌。筆者之前算字符相似度自己還寫了一個杰爾卡德相似度凡壤，現(xiàn)在看看真實太費事了。
dendrogram(linkage)
scipy.cluster.hierarchy.dendrogram(linkage)耙替，這個函數(shù)是畫圖用的亚侠。

import numpy
import pandas
from sklearn import datasets
import scipy.cluster.hierarchy as hcluster
import scipy
#iris = datasets.load_iris()
#data = iris.data
#target = iris.target
points=scipy.randn(20,4)  
# Compute and plot first dendrogram.
linkage = hcluster.linkage(points, method='centroid')
hcluster.dendrogram(linkage,  leaf_font_size=10.)
p = hcluster.fcluster( linkage,  3, criterion='maxclust')

聚類結果如下圖所示：