層次聚類（1）

層次聚類算法不同于其它算法，主要體現(xiàn)在它不是只生成一個(gè)分類結(jié)果，而是產(chǎn)生一系列原模式集合的分類結(jié)果，每個(gè)分類結(jié)果滿足一些限制。

1、概念

X = {x_i, i = 1,...,N}; 是N個(gè)l維特征向量組成的集合，我們就是要對(duì)這個(gè)集合中的特征向量分類。

Clustering ： R = {C_j, j = 1,...,m}。是某個(gè)聚類結(jié)果，就叫他類簇吧，我想這樣叫，也許別人已經(jīng)定義了類簇，但是我還是想這樣叫他。

如果類簇（clustering）R_1 包含 k個(gè)類（cluster），類簇R_2 包含r個(gè)類，且r < k, 如果R_1中的每一個(gè)類都是R_2中的某個(gè)類的子集，那么我就說類簇R_1 嵌入到了 R_2中。?

注意，R_1中至少有兩個(gè)類是R_2的中某個(gè)類的真子集，我沒有深入思考這一點(diǎn)，但是這好像是顯然的。

比如 R_1 = {{x_1, x_3}, {x_4}, {x_2,x_5}}， R_2 = {{x_1, x_3,x_4}, {x_2.x_5}} ，那么R_1嵌入了R_2中。

層次聚類的目標(biāo)就是將X分成多個(gè)嵌套的類簇（a hierarchy of nested clusterings），這類算法大約包含N步，每一步都是利用上一步產(chǎn)生的類簇結(jié)果，生成一個(gè)新的類簇，這兩個(gè)類簇存在一個(gè)嵌套關(guān)系。根據(jù)這種嵌套關(guān)系，一般層次聚類有兩個(gè)方向， 一種方法是從每個(gè)特征向量為一類，N個(gè)類，聚成一個(gè)類，另一種是從一個(gè)類，一步步處理到N個(gè)類。

前者叫 agglomerative層次算法，后者叫 divisive層次算法。

2、 Agglomerative算法

設(shè)g(C_i, C_j)為 C_i 和 C_j兩個(gè)類之間的近鄰測度（proximity measurement）， t 表示 當(dāng)前層次的序號(hào)。 下面敘述的是 GAS（Generalized Agglomerative scheme）

下面的算法， g 表示的不相似度測度。

Initialization:
??Choose?R_0?=?{C_i?=?{x_i},?i?=?1,...,N}?as?the?initial?clustering.?
??t?=?0.
Repeat?:
??t?=?t?+?1;
??Among?all?possible?pairs?of?clusters?(C_r,?C_s)?in?R_{t-1}?find?the?one?(C_i,C_j),?such?that????g(C_i,?C_j)?=?min?g(C_r,C_s);
??define?C_q?=?C_i?U?C_j?and?produce?a?new?clustering?R_t?=?(R_{t-1}?-?{C_i,?C_j})?U?{C_q}
Until?all?vectors?lie?in?a?single?cluster.

3、matlab中的agglomerative 算法

給定 模式的特征向量集

Object 1: 1, 2
Object 2: 2.5, 4.5
Object 3: 2, 2
Object 4: 4, 1.5
Object 5: 4, 2.5

即?

X?=?[1,?2;?2.5,?4.5;?2,?2;?4,?1.5;?4,?2.5];

下面的三個(gè)命令可以看到層次圖：

Y?=?pdist(X);?
Z?=?linkage(Y);
dendrogram(Z)

結(jié)果如下：