R 中的資料探勘演算法/聚類/混合層次聚類

待辦事項
本節仍在編寫中。但請隨時新增您的貢獻或以任何方式提供幫助

混合層次聚類是一種聚類技術，它試圖結合兩種層次技術（凝聚的和分裂的）的最佳特徵。

介紹

聚類可以被認為是一個重要的無監督學習問題，它試圖在一個未標記的資料集合中找到相似的結構（JAIN，MURTY，FLYNN，1999）^[1]。

這些相似的結構是資料組，更廣為人知的是聚類。每個聚類中的資料與其聚類內的元素相似（或接近），並且與屬於其他聚類的元素不同（或更遠）。聚類技術的目標是確定資料集中的內在分組（JAIN，MURTY，FLYNN，1999）^[1]。

聚類技術

有幾種聚類技術，但沒有一種可以被認為是絕對最好的方法。每種技術都有自己的優點和缺點，這通常會讓使用者決定哪種聚類方法最能滿足他的需求。

層次聚類

層次聚類函式基本上是將最接近的聚類連線起來，直到達到所需的聚類數量。這種層次聚類被稱為凝聚的，因為它迭代地連線聚類。還有一種分裂的層次聚類，它執行相反的過程，每個資料項都在同一個聚類中開始，然後它被分成更小的組（JAIN，MURTY，FLYNN，1999）^[1]。

聚類之間的距離測量可以透過多種方式完成，這就是單鏈接、平均連結和完全連結的層次聚類演算法的不同之處。

在單鏈接聚類中，也稱為最小方法，兩個聚類之間的距離被認為是所有資料項對之間的最小距離。在完全連結聚類中，也稱為最大方法，兩個聚類之間的距離被認為是所有資料項對之間的最大距離。完全連結演算法找到的聚類通常比單鏈接演算法找到的聚類更緊湊。然而，單鏈接演算法更通用（JAIN，MURTY，FLYNN，1999）^[1]。

在平均連結聚類中，兩個聚類之間的距離等於所有資料的平均距離。此方法的一個變體使用中位數距離，它對資料變化比平均距離更不敏感。

許多層次聚類演算法具有一個吸引人的屬性，即巢狀的聚類序列可以用一棵樹圖形地表示，稱為“樹狀圖”（CHIPMAN，TIBSHIRANI，2006）^[2]。圖 1 顯示了一個樹狀圖示例。

圖 1：使用單鏈接凝聚聚類演算法獲得的樹狀圖。來源：Jain，Murty，Flynn（1999）^[1]。

層次聚類的最大缺點是它的高複雜度順序 O(n^2 log n)（JAIN，MURTY，FLYNN，1999）^[1]。然而，層次方法具有處理不同密度的聚類的優點，這比其他聚類技術好得多。

混合層次聚類

凝聚演算法將資料分組為許多小的聚類和幾個大的聚類，這通常使它們擅長識別小的聚類而不是大的聚類。然而，分裂演算法具有相反的特徵；使它們普遍擅長識別大型聚類（CHIPMAN，TIBSHIRANI，2006）^[2]。

混合層次聚類技術試圖結合凝聚和分裂技術的最佳優勢（LAAN，POLLARD，2002；CHIPMAN，TIBSHIRANI，2006）^[2]^[3]。這種組合的實現方式取決於所選的演算法。

在本節中，將介紹一種混合層次演算法，該演算法使用“互斥聚類”的概念將分裂技術的程式與從初步凝聚聚類中獲得的資訊相結合。

互斥聚類

互斥聚類可以定義為一組資料，這些資料相互之間比對任何其他資料更接近，並且與所有其他資料相距甚遠。互斥聚類中包含的資料絕不應該分離（CHIPMAN，TIBSHIRANI，2006）^[2]。

基本上，這要求在互斥聚類中，S 中的資料元素之間的最大距離小於 S 中的元素到不在 S 中的任何資料的最小距離

$d(x,y)_{x\in S,y\notin S}>diameter(S)\equiv \max _{w\in S,z\in S}d(w,z)$

其中 S 是資料的子集，d 是兩個資料項之間的距離函式，x 是屬於 S 的元素，y 是不屬於 S 的元素。

互斥聚類有一個有趣的屬性，它表明互斥聚類不會被任何單鏈接、平均連結或完全連結方法的凝聚聚類破壞（CHIPMAN，TIBSHIRANI，2006）^[2]。有關單鏈接、平均連結或完全連結方法的更多資訊，請參閱層次聚類部分的凝聚技術。

此屬性對互斥聚類有幾個影響。最明顯的是支援這樣的想法，即互斥聚類包含強大的聚類資訊，無論使用哪種連結方法。此屬性還有助於解釋凝聚方法。此附加資訊可以幫助解釋互斥聚類，或幫助決定要分割哪些聚類。

此屬性的另一個影響是互斥聚類不能被凝聚方法破壞，這表明所有互斥聚類都可以透過檢查此方法中的巢狀聚類來識別。

演算法

使用互斥聚類的混合層次演算法可以分為三個步驟

使用凝聚技術計算互斥聚類。
執行約束的分裂技術，其中每個互斥聚類必須保持完整。這是透過暫時用它們的質心替換一組資料元素的互斥聚類來實現的。
一旦分裂聚類完成，透過在每個互斥聚類“內部”執行另一個分裂聚類來分割每個互斥聚類。

前面描述的互聚類屬性及其含義表明，如何在步驟 1 中使用凝聚技術輕鬆找到互聚類。對於步驟 2，可以使用任何自上而下的方法，它甚至不需要是分裂式層次演算法。在步驟 3 中，可以使用凝聚方法。由於互聚類通常很小，因此在步驟 3 中使用自上而下或自下而上的方法將產生類似的結果。在步驟 2 和 3 中同時使用自上而下似乎更簡單。

R 中的實現

包： hybridHclust
描述： 透過互聚類進行混合層次聚類
版本 1.0-3
依賴： cluster
釋出 2008-04-08
作者： Hugh Chipman、Rob Tibshirani，tsvq 程式碼最初來自 Trevor Hastie
維護者： Hugh Chipman <hugh.chipman@acadiau.ca>
許可證： GPL-2
網址： http://ace.acadiau.ca/math/chipmanh/hybridHclust
儲存庫： CRAN
在檢視中： 聚類、多元

要下載此包，請訪問 CRAN Mirrors 頁面，然後選擇離您所在區域最近的映象。到達那裡後，選擇“包”，然後搜尋“hybridHclust”。

詳情

hybridHclust 包使用互聚類概念來構建一個聚類，其中互聚類永遠不會被破壞。這是透過暫時將互聚類中的所有點“融合”在一起，使它們具有相同的座標來實現的。然後將生成的從上到下的聚類“拼接”在一起，形成一個單獨的從上到下的聚類（CHIPMAN，TIBSHIRANI，2006；2008）^[2]^[4]。

“只有最大的互聚類被限制為不能被破壞。因此，如果點 A、B、C、D 是一個互聚類，而點 A、B 也是一個互聚類，那麼只有這四個點將被禁止被破壞”（CHIPMAN，TIBSHIRANI，2008）^[4]。

此包使用 x 的行之間的平方歐幾里得距離作為距離度量。在某些情況下，理想的距離度量是 d(x1,x2)=1-cor(x1,x2)，如果 x1 和 x2 是矩陣 x 的兩行。這種基於相關性的距離在行被縮放為具有均值 0 和標準差 1 後等效於平方歐幾里得距離。這可以透過在呼叫混合聚類演算法之前預處理資料矩陣來實現（CHIPMAN，TIBSHIRANI，2008）^[4]。

執行混合聚類的主要方法稱為 hybridHclust。

用法
hybridHclust(x, themc=NULL, trace=FALSE)

引數
x - 要聚類的行是資料矩陣
themc - 代表 x 中的互聚類的物件，通常由 mutualCluster 函式生成。如果沒有提供，它將被計算。
trace – 指示在執行時是否列印內部步驟。

返回值
hclust 格式的樹狀圖

視覺化

hybridHClust 函式返回一個樹狀圖，代表演算法的聚類。可以使用“plot”函式檢視樹狀圖。

可以使用互聚類函式計算互聚類。該函式有一個“plot”引數，它會在圖表上自動繪製互聚類樹狀圖。要列印互聚類，需要使用“print.mutualCluster”函式。

請記住在嘗試任何示例程式碼之前載入 hybridHclust R 包。

示例

# Function to show multiple graphs plotting, in this case 3 graphs in one row 
par(mfrow=c(1,3))
# An Example Data 
x <- cbind(c(-1.4806,1.5772,-0.9567,-0.92,-1.9976,-0.2723,-0.3153),c( -0.6283,-0.1065,0.428,-0.7777,-1.2939,-0.7796,0.012))
# Plot the example data
plot(x, pch = as.character(1:nrow(x)), asp = 1)
# Calculate the mutual clusters
mc1 <- mutualCluster(x, plot=TRUE)
print.mutualCluster(mc1) # print the mutual clusters
dist(x) # distance between data so you can verify that mc's are correct
# Calculate the Hybrid Hierarchical Cluster
hyb1 <- hybridHclust(x)
# Plot the Hybrid Clustering Dendogram
plot(hyb1)

案例研究

為了更好地說明聚類技術，將展示一個簡單的案例研究。

當代心理學中的“五大”包含五個重要的性格因素。這五個因素被發現包含並涵蓋了所有已知的性格特徵，並代表了所有性格特徵背後的基本結構。

五大因素及其組成特徵可概括如下

開放性 - 對藝術、情感、冒險、非凡的想法、好奇心和各種體驗的欣賞。
盡責性 - 表現出自律、盡職盡責和追求成就的傾向；計劃性而非自發性行為。
外向性 - 活力、積極情緒、緊迫感，以及在與他人交往中尋求刺激的傾向。
宜人性 - 傾向於對他人表現出同情和合作，而不是懷疑和對抗。
神經質 - 容易體驗到令人不快的情緒，例如憤怒、焦慮、抑鬱或脆弱。

心理學家衡量某人性格中這些因素最常見的方式是應用帶有描述性句子的“測試”。這些特徵的測試分數通常以百分位數的形式呈現。

場景/情況/發展

假設五大分數被應用於人口。在這種情況下，測試還附帶一個社會經濟測試，用於研究目的。這些測試可以根據他們在每個因素和社會經濟變數中的百分位數得分進行分組，以便心理學家可以更好地分析結果及其對人口的可能影響。

輸入資料

輸入資料是六維數值資料，包含五個因素百分位數得分和個人家庭收入。輸入資料是使用每個維度上的正態分佈隨機生成的。隨機生成的資料節省了時間，並避免了使用個人可能的特權資訊（即使是匿名）的法律問題。

列 O、C、E、A、N 分別代表開放性、盡責性、外向性、宜人性和神經質因素。所有這些列的值都以五大測試的百分位數結果的形式呈現。每個因素的百分位數從最低 5 到最高 95，間隔為 5。

列 I 代表個人家庭收入，該值是家庭賺取的最低工資數。

包含輸入資料的 csv 檔案可以在這裡找到：HybridHClust 案例研究 CSV 輸入檔案

	O	C	E	A	N	I
1.	10	30	40	55	45	12
2.	50	85	25	30	40	6
3.	95	90	80	50	5	10
4.	20	65	20	15	50	5
5.	50	25	65	10	95	13
6.	40	85	25	10	65	10
7.	55	50	90	90	75	9
8.	35	80	5	40	35	10
9.	30	65	85	35	80	13
10.	20	45	30	50	25	13
11.	40	30	65	10	25	14
12.	50	75	85	50	10	6
13.	65	75	50	5	50	9
14.	90	30	50	35	95	10
15.	60	80	10	75	50	6
16.	25	85	25	50	20	4
17.	10	30	90	50	35	13
18.	75	10	85	55	5	10
19.	65	65	20	50	15	16
20.	60	70	60	60	25	9
21.	35	70	30	40	45	6
22.	55	5	90	70	70	13
23.	15	20	60	40	60	10
24.	20	40	75	70	15	9
25.	30	95	25	65	20	7
26.	90	75	30	20	70	2
27.	95	20	65	80	45	15
28.	45	50	85	70	65	4
29.	60	90	70	25	5	14
30.	70	45	65	50	40	9
31.	50	50	65	65	45	7
32.	50	95	15	35	60	5
33.	70	15	90	80	50	9
34.	85	30	20	30	80	2
35.	70	40	45	85	30	2
36.	75	55	80	85	25	4
37.	20	55	25	35	90	4
38.	85	10	5	55	80	15
39.	5	15	75	35	25	10
40.	75	50	45	60	40	16
41.	65	85	35	90	10	3
42.	25	50	20	15	65	12
43.	15	15	50	75	80	3
44.	30	95	30	45	75	14
45.	80	50	85	20	25	5
46.	35	35	60	25	35	8
47.	90	55	50	15	35	5
48.	35	65	95	35	20	7
49.	30	70	60	25	45	15
50.	30	55	50	30	65	9
51.	35	90	70	20	20	6
52.	60	35	95	10	15	9
53.	25	60	35	90	25	10
54.	10	5	10	45	20	6
55.	80	5	15	75	90	14
56.	20	40	80	35	15	5
57.	80	60	95	65	70	4
58.	65	30	75	30	65	15
59.	15	45	55	50	70	6
60.	20	5	55	55	35	1
61.	40	10	75	70	30	3
62.	20	90	65	80	75	10
63.	95	40	40	20	5	4
64.	45	45	75	25	45	11
65.	80	95	50	45	10	14
66.	60	25	50	70	80	6
67.	85	60	45	95	55	9
68.	95	10	70	60	20	12
69.	65	75	25	50	40	15
70.	10	50	35	10	50	10
71.	50	85	85	40	65	8
72.	45	55	10	10	70	1
73.	5	50	95	55	90	3
74.	35	15	35	15	50	15
75.	95	40	75	50	50	4
76.	50	40	95	65	5	4
77.	40	80	50	95	5	14
78.	55	50	70	50	15	9
79.	90	45	55	30	65	1
80.	20	60	95	95	50	15
81.	85	50	95	95	90	11
82.	5	55	55	25	95	10
83.	15	15	40	20	15	9
84.	80	50	50	50	35	2
85.	65	90	65	50	35	3
86.	75	70	85	20	30	7
87.	65	10	85	10	50	1
88.	75	10	85	15	5	10
89.	50	25	15	20	30	6
90.	15	30	60	10	75	7
91.	30	15	45	25	25	11
92.	75	95	5	95	30	10
93.	55	15	70	30	40	12
94.	10	15	50	30	65	5
95.	5	50	50	60	25	7
96.	75	5	75	65	90	15
97.	80	25	90	90	50	6
98.	60	15	10	75	80	9
99.	95	15	95	95	5	7
100.	55	30	70	85	90	5

執行

# Read the data file
x <- read.csv("hybridHclust_case_study_input.csv")
# calculate the mutual clusters
mc <- mutualCluster(x)
# Calculate the Hybrid Hierarchical Cluster
hyb <- hybridHclust(x, mc)
# Plot the Hybrid Clustering Dendogram
plot(hyb)

輸出

聚類函式顯示了聚類資料的樹狀圖，透過它可以決定要使用多少個聚類。下圖中的紅線演示了分析的這種選擇，在本例中，將考慮紅線以下的聚類。

圖 2：上述案例研究資料的混合聚類樹狀圖

分析

由於案例研究具有多維資料，因此很難直觀地瞭解聚類有哪些共同之處。但是，當選擇了一個合適的聚類數量時，就可以看到它們的相似性，並更好地分析結果。

看看由 50、59、23、94、43、82、90、5、4、42、70、72 和 37 形成的聚類。該聚類具有中等至高的神經質值 [50、95]，中等至低的開放性值 [5、50]，以及低至中等高的盡責性值 [15、65]。

	O	C	E	A	N	I
4.	20	65	20	15	50	5
5.	50	25	65	10	95	13
23.	15	20	60	40	60	10
37.	20	55	25	35	90	4
42.	25	50	20	15	65	12
43.	15	15	50	75	80	3
50.	30	55	50	30	65	9
59.	15	45	55	50	70	6
70.	10	50	35	10	50	10
72.	45	55	10	10	70	1
82.	5	55	55	25	95	10
90.	15	30	60	10	75	7
94.	10	15	50	30	65	5

另一個有趣的聚類是由 74、89、83、91、54、10、95 和 1 形成的。該聚類具有中等至低的開放性值 [5、50]，中等至低的盡責性值 [5、50]，中等至低的外向性值 [10、50]，以及中等至低的神經質值 [15、50]。

	O	C	E	A	N	I
1.	10	30	40	55	45	12
10.	20	45	30	50	25	13
54.	10	5	10	45	20	6
74.	35	15	35	15	50	15
83.	15	15	40	20	15	9
89.	50	25	15	20	30	6
91.	30	15	45	25	25	11
95.	5	50	50	60	25	7

如果聚類中的值範圍是風險行為或病理的指標，那麼心理學家就可以更關注該組中的任何人，例如。或者，如果更準確的社會經濟變數可以用來檢視五大因素與其他社會經濟因素之間的相關性。

參考文獻

↑ ^a ^b ^c ^d ^e ^f Jain, A. K., Murty, M. N., Flynn, P. J. (1999) “資料聚類：綜述”。ACM 計算機調查 (CSUR)，31(3)，第 264-323 頁，1999 年。
↑ ^a ^b ^c ^d ^e ^f Chipman, H., Tibshirani, R. (2006) “帶有微陣列資料應用的混合層次聚類”。生物統計學提前訪問，7(2)，第 286-301 頁，2006 年 4 月。
↑ Laan, M.，Pollard, K. (2002) "一種新的混合層次聚類演算法及其視覺化和自舉方法"。統計規劃與推斷雜誌，117 (2)，第 275-303 頁，2002 年 12 月。
↑ ^a ^b ^c Chipman, H.，Tibshirani, R. (2008) "hybridHClust 包"，2008 年 4 月。

[jain99-1] ↑ ^a ^b ^c ^d ^e ^f Jain, A. K., Murty, M. N., Flynn, P. J. (1999) “資料聚類：綜述”。ACM 計算機調查 (CSUR)，31(3)，第 264-323 頁，1999 年。

[chipman06-2] ↑ ^a ^b ^c ^d ^e ^f Chipman, H., Tibshirani, R. (2006) “帶有微陣列資料應用的混合層次聚類”。生物統計學提前訪問，7(2)，第 286-301 頁，2006 年 4 月。

[laan02-3] Laan, M.，Pollard, K. (2002) "一種新的混合層次聚類演算法及其視覺化和自舉方法"。統計規劃與推斷雜誌，117 (2)，第 275-303 頁，2002 年 12 月。

[chipman08-4] Chipman, H.，Tibshirani, R. (2008) "hybridHClust 包"，2008 年 4 月。

[1]

[2]

[3]

[4]