java層次聚類（層次聚類 密度聚類）

本文目錄一覽：

• 1、三種聚類方法：層次、K均值、密度
• 2、層次聚類改進
• 3、層次聚類方法的聚類分類

三種聚類方法：層次、K均值、密度

一、層次聚類

1）距離和相似係數

r語言中使用dist(x, method = “euclidean”,diag = FALSE, upper = FALSE, p = 2) 來計算距離。其中x是樣本矩陣或者數據框。method表示計算哪種距離。method的取值有：

euclidean                歐幾里德距離，就是平方再開方。

maximum                切比雪夫距離

manhattan 絕對值距離

canberra Lance 距離

minkowski            明科夫斯基距離，使用時要指定p值

binary                    定性變量距離.

定性變量距離： 記m個項目裡面的 0:0配對數為m0 ,1:1配對數為m1，不能配對數為m2，距離=m1/(m1+m2);

diag 為TRUE的時候給出對角線上的距離。upper為TURE的時候給出上三角矩陣上的值。

r語言中使用scale(x, center = TRUE, scale = TRUE) 對數據矩陣做中心化和標準化變換。

如只中心化 scale(x,scale=F) ,

r語言中使用sweep(x, MARGIN, STATS, FUN=”-“, …) 對矩陣進行運算。MARGIN為1，表示行的方向上進行運算，為2表示列的方向上運算。STATS是運算的參數。FUN為運算函數，默認是減法。下面利用sweep對矩陣x進行極差標準化變換

?

1

2

3

center -sweep(x, 2, apply(x, 2, mean)) #在列的方向上減去均值。

R -apply(x, 2, max) -apply(x,2,min)   #算出極差，即列上的最大值-最小值

x_star -sweep(center, 2, R, “/”)        #把減去均值後的矩陣在列的方向上除以極差向量

?

1

2

3

center -sweep(x, 2, apply(x, 2, min)) #極差正規化變換

R -apply(x, 2, max) -apply(x,2,min)

x_star -sweep(center, 2, R, “/”)

有時候我們不是對樣本進行分類，而是對變量進行分類。這時候，我們不計算距離，而是計算變量間的相似係數。常用的有夾角和相關係數。

r語言計算兩向量的夾角餘弦：

?

1

2

y -scale(x, center =F, scale =T)/sqrt(nrow(x)-1)

C -t(y) %*%y

相關係數用cor函數

2）層次聚類法

層次聚類法。先計算樣本之間的距離。每次將距離最近的點合併到同一個類。然後，再計算類與類之間的距離，將距離最近的類合併為一個大類。不停的合併，直到合成了一個類。其中類與類的距離的計算方法有：最短距離法，最長距離法，中間距離法，類平均法等。比如最短距離法，將類與類的距離定義為類與類之間樣本的最段距離。。。

r語言中使用hclust(d, method = “complete”, members=NULL) 來進行層次聚類。

其中d為距離矩陣。

method表示類的合併方法，有：

single            最短距離法

complete        最長距離法

median        中間距離法

mcquitty        相似法

average        類平均法

centroid        重心法

ward            離差平方和法

?

1

2

3

4

5

6

7

8

 x -c(1,2,6,8,11)      #試用一下

 dim(x) -c(5,1)

 d -dist(x)

 hc1 -hclust(d,”single”)

 plot(hc1)

 plot(hc1,hang=-1,type=”tirangle”)             #hang小於0時，樹將從底部畫起。

#type = c(“rectangle”, “triangle”),默認樹形圖是方形的。另一個是三角形。

#horiz  TRUE 表示豎著放，FALSE表示橫着放。

?

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

 z -scan()

1: 1.0000.8460.8050.8590.4730.3980.3010.382

9: 0.8461.0000.8810.8260.3760.3260.2770.277

17: 0.8050.8811.0000.8010.3800.3190.2370.345

25: 0.8590.8260.8011.0000.4360.3290.3270.365

33: 0.4730.3760.3800.4361.0000.7620.7300.629

41: 0.3980.3260.3190.3290.7621.0000.5830.577

49: 0.3010.2770.2370.3270.7300.5831.0000.539

57: 0.3820.4150.3450.3650.6290.5770.5391.000

65: 

Read 64items

 names

[1] “shengao””shoubi””shangzhi””xiazhi””tizhong”

[6] “jingwei””xiongwei””xiongkuang”

 r -matrix(z,nrow=8,dimnames=list(names,names))

 d -as.dist(1-r)

 hc -hclust(d)

 plot(hc)

然後可以用rect.hclust(tree, k = NULL, which = NULL, x = NULL, h = NULL,border = 2, cluster = NULL)來確定類的個數。 tree就是求出來的對象。k為分類的個數，h為類間距離的閾值。border是畫出來的顏色，用來分類的。

?

1

2

3

 plot(hc)

 rect.hclust(hc,k=2)

 rect.hclust(hc,h=0.5)

result=cutree(model,k=3) 該函數可以用來提取每個樣本的所屬類別

二、動態聚類k-means

層次聚類，在類形成之後就不再改變。而且數據比較大的時候更占內存。

動態聚類，先抽幾個點，把周圍的點聚集起來。然後算每個類的重心或平均值什麼的，以算出來的結果為分類點，不斷的重複。直到分類的結果收斂為止。r語言中主要使用kmeans(x, centers, iter.max = 10, nstart = 1, algorithm  =c(“Hartigan-Wong”, “Lloyd”,”Forgy”, “MacQueen”))來進行聚類。centers是初始類的個數或者初始類的中心。iter.max是最大迭代次數。nstart是當centers是數字的時候，隨機集合的個數。algorithm是算法，默認是第一個。

?

使用knn包進行Kmean聚類分析

將數據集進行備份，將列newiris$Species置為空，將此數據集作為測試數據集

newiris – iris

newiris$Species – NULL

在數據集newiris上運行Kmean聚類分析， 將聚類結果保存在kc中。在kmean函數中，將需要生成聚類數設置為3

(kc – kmeans(newiris, 3)) 

K-means clustering with 3 clusters of sizes 38, 50, 62: K-means算法產生了3個聚類，大小分別為38,50,62. 

Cluster means: 每個聚類中各個列值生成的最終平均值

  Sepal.Length Sepal.Width Petal.Length Petal.Width

1     5.006000    3.428000     1.462000    0.246000

2     5.901613    2.748387     4.393548    1.433871

3     6.850000    3.073684     5.742105    2.071053

Clustering vector: 每行記錄所屬的聚類（2代表屬於第二個聚類，1代表屬於第一個聚類，3代表屬於第三個聚類）

  [1] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

[37] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

[73] 2 2 2 2 2 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 2 3 3 3 3 2 3

[109] 3 3 3 3 3 2 2 3 3 3 3 2 3 2 3 2 3 3 2 2 3 3 3 3 3 2 3 3 3 3 2 3 3 3 2 3

[145] 3 3 2 3 3 2

Within cluster sum of squares by cluster: 每個聚類內部的距離平方和   

[1] 15.15100 39.82097 23.87947

(between_SS / total_SS =  88.4 %) 組間的距離平方和佔了整體距離平方和的的88.4%，也就是說各個聚類間的距離做到了最大

Available components: 運行kmeans函數返回的對象所包含的各個組成部分

[1] “cluster”      “centers”      “totss”        “withinss”    

[5] “tot.withinss” “betweenss”    “size”  

(“cluster”是一個整數向量，用於表示記錄所屬的聚類  

“centers”是一個矩陣，表示每聚類中各個變量的中心點

“totss”表示所生成聚類的總體距離平方和

“withinss”表示各個聚類組內的距離平方和

“tot.withinss”表示聚類組內的距離平方和總量

“betweenss”表示聚類組間的聚類平方和總量

“size”表示每個聚類組中成員的數量)

創建一個連續表,在三個聚類中分別統計各種花出現的次數

table(iris$Species, kc$cluster)           

              1  2  3

  setosa      0 50  0

  versicolor  2  0 48

  virginica  36  0 14

根據最後的聚類結果畫出散點圖，數據為結果集中的列”Sepal.Length”和”Sepal.Width”，顏色為用1，2，3表示的缺省顏色

plot(newiris[c(“Sepal.Length”, “Sepal.Width”)], col = kc$cluster)

在圖上標出每個聚類的中心點

〉points(kc$centers[,c(“Sepal.Length”, “Sepal.Width”)], col = 1:3, pch = 8, cex=2)

三、DBSCAN

動態聚類往往聚出來的類有點圓形或者橢圓形。基於密度掃描的算法能夠解決這個問題。思路就是定一個距離半徑，定最少有多少個點，然後把可以到達的點都連起來，判定為同類。在r中的實現

dbscan(data, eps, MinPts, scale, method, seeds, showplot, countmode)

其中eps是距離的半徑，minpts是最少多少個點。 scale是否標準化（我猜) ,method 有三個值raw,dist,hybird,分別表示，數據是原始數據避免計算距離矩陣，數據就是距離矩陣，數據是原始數據但計算部分距離矩陣。showplot畫不畫圖，0不畫，1和2都畫。countmode，可以填個向量，用來顯示計算進度。用鳶尾花試一試

?

1

2

3

4

5

6

7

8

9

10

11

 install.packages(“fpc”, dependencies=T)

 library(fpc)

 newiris -iris[1:4]

 model -dbscan(newiris,1.5,5,scale=T,showplot=T,method=”raw”)# 畫出來明顯不對 把距離調小了一點

 model -dbscan(newiris,0.5,5,scale=T,showplot=T,method=”raw”)

 model #還是不太理想……

dbscan Pts=150MinPts=5eps=0.5

        012

border 34518

seed    04053

total  344571

層次聚類改進

一個層次的聚類方法將數據對象組成一棵聚類的樹。根據層次分解是自底向上的還是自頂向下形成的，層次的聚類方法可以進一步分為凝聚的（agglomerative）和分裂的（divisive）層次聚類。

（1）凝聚的層次聚類：這種自底向上的策略首先將每個對象作為單獨的一個簇，然後和並這些原子簇為越來越大的簇，直到所有的對像都在一個簇中，或者達到某個終止條件。

（2）分裂的層次聚類：這種自頂向下的策略與凝聚的層次聚類相反，它首先將所有的對象置於一個簇中。然後逐漸細分為越來越小的簇，直到每個對象在單獨的一個簇中，或者達到一個終止條件，例如打到了某個希望的簇數目後者兩個簇之間的距離超過了某個閥值。

例2 圖2－3描述了一個凝聚的層次聚類方法AGNES（Agglomerative NESting）和一個分裂的層次聚類方法DIANA（Divisive Analysis）在一個包含五個對象的數據集合{a,b,c,d,e}上的處理過程。最初,AGNES將每個對象作為一個簇，然後這些簇根據某些準則一步步合併。例如，如果簇C1中的一個對象和簇 C2中的一個對象之間的距離使所有屬於不同簇的對象間歐式距離最小的，C1和C2可能被合併。其每個簇可以被簇中所有對象代表，兩個簇間的相似度由兩個不同簇中距離最近的數據點對的相似度來確定。聚類的合併過程反覆進行直到所有對象最終合併為一個簇。

圖2-3 在對象集合(a,b,c,d)上的凝聚與分裂層次聚類

在DIANA方法處理過程中，所有的對象都放在一個簇中。根據一些原則（如簇中最鄰近的對象的最大歐氏距離），將該簇分裂。簇的分裂過程反覆進行，直到最終每個新的簇只包含一個對象。

層次聚類方法儘管簡單，但經常會遇到合併或分裂點選擇的困難。這樣的選擇是非常關鍵的，因為一旦一組對象（合併或分裂）完成，它就不能被撤銷，下一步的處理將在新完成的簇上進行。這個嚴格規定是有用的，由於不用擔心組合數目的不同選擇，計算代價會比較小。但是，已做的處理不能被撤消，聚類之間也不能交換對象。如果在某一步沒有很好的選擇合併或分裂的決定，可能會導致低質量的聚類結果。而且，這種聚類不具有很好的可伸縮性。因為合併或分裂的決定需要檢查和估算大量的對象或結果。

改進層次方法的聚類質量的一個有希望的方向是將層次聚類和其他聚類技術集成。有兩種方法可以改進層次聚類的結果：

（i） 在每層劃分中，仔細分析對象間的“聯接”，例如CURE和Chameleon中的做法。

（ii）綜合層次凝聚和迭代的重定位方法。首先用自底向上的層次算法，然後用迭代的重定位來改進結果。例如BIRCH中的方法。

層次聚類方法的聚類分類

根據聚類原理步驟3的不同, 可將層次式聚類 方法分為幾類: single-linkage, complete-linkage 以及average-linkage 聚類方法等. SL聚類，即single-linkage聚類法(也稱connectedness 或minimum 方法)：

類間距離等於兩類對象之間的最小距離，若用相似度衡量，則是各類中的任一對象與另一類中任一對象的最大相似度。 CL層次聚類，即complete-linkage聚類法(也稱diameter 或maximum 方法)：

組間距離等於兩組對象之間的最大距離。 AL層次聚類，即average-linkage聚類法組間距離等於兩組對象之間的平均距離。

average-link 聚類的一個變種是R. D’Andrade (1978) 的UCLUS方法, 它使用的是median距離, 在受異常數據對象的影響方面, 它要比平均距離表現更佳一些.

這種層次聚類稱為“凝聚法，由於它迭代合併所有分類。也有一種“劃分”層次聚類法，與“凝聚”相反，它先將所有對象放在同一類中，並不斷劃分成更小的類，劃分法一般很少使用。