R 中的資料探勘演算法/聚類/CLARA
對大型資料集進行聚類的一個顯而易見的方法是嘗試擴充套件現有方法，使其能夠處理更多物件。重點在於對大量物件而不是高維空間中的少量物件進行聚類。Kaufman 和 Rousseeuw (1990) 提出了 CLARA (用於大型應用程式的聚類) 演算法來處理大型應用程式。CLARA 擴充套件了他們的 k-medoids 方法，適用於大量物件。它透過對資料集中的樣本進行聚類，然後將資料集中的所有物件分配到這些聚類中。
- 將要討論的技術
這項工作重點介紹 CLARA，這是一種用於對大型資料集進行聚類的方法。
| 符號 | 定義 |
|---|---|
| D | 要聚類的資料集 |
| n | D 中的物件數量 |
| O_i | D 中的物件 i |
| k | 聚類數量 |
| S | D 的樣本 |
| s | S 的大小 |
表 1: 符號和定義的摘要
CLARA (Clustering LARge Applications) 依賴於取樣方法來處理大型資料集。CLARA 並沒有為整個資料集尋找 medoids，而是從資料集中抽取一個小的樣本，並應用 PAM 演算法為樣本生成一個最佳的 medoids 集。結果 medoids 的質量透過整個資料集 D 中每個物件與其聚類 medoid 之間的平均差異來衡量，定義為以下成本函式
其中 M 是選定的 medoids 集，dissimilarity(Oi, Oj) 是物件 Oi 和 Oj 之間的差異，rep(M, Oi) 返回 M 中最接近 Oi 的 medoid。
為了減輕取樣偏差，CLARA 重複取樣和聚類過程預先定義的次數，然後選擇成本最小的 medoids 集作為最終的聚類結果。假設 q 是取樣次數。CLARA 演算法在圖 1 中詳細說明。
檔案:Algorithm CLARA.png
圖 1: CLARA 演算法
由於 CLARA 採用了取樣方法，因此其聚類結果的質量在很大程度上取決於樣本的大小。當樣本量較小時，CLARA 在對大型資料集進行聚類方面的效率是以聚類質量為代價的。
為了在 R 中使用 CLARA 演算法，必須安裝 cluster 包。此包包含一個執行 CLARA 過程的函式。
安裝 cluster 包
install.packages("cluster")
匯入內容
library("cluster")
cluster 包提供的 CLARA 函式可以按如下方式使用
clara(x, k, metric = "euclidean", stand = FALSE, samples = 5, sampsize = min(n, 40 + 2 * k), trace = 0, medoids.x = TRUE, keep.data = medoids.x, rngR = FALSE)
其中引數為
- x: 資料矩陣或資料框，每行對應一個觀測值，每列對應一個變數。所有變數都必須是數值型的。允許出現缺失值 (NA)。
- k: 整數，聚類數量。要求 0 < k < n，其中 n 是觀測值數量（即 n = nrow(x)）。
- metric: 字串，指定用於計算觀測值之間差異的度量。目前可用的選項為 "euclidean" 和 "manhattan"。歐幾里得距離是差異的平方根和，曼哈頓距離是絕對差異的總和。
- stand: 邏輯值，指示在計算差異之前是否對 x 中的測量值進行標準化。測量值對於每個變數（列）進行標準化，方法是減去變數的平均值併除以變數的平均絕對偏差。
- samples: 整數，從資料集中抽取的樣本數量。
- sampsize: 整數，每個樣本中的觀測值數量。sampsize 應該大於聚類數量 (k)，最多等於觀測值數量 (n = nrow(x))。
- trace: 整數，指示演算法過程中診斷輸出的跟蹤級別。
- medoids.x: 邏輯值，指示是否應返回 medoids，與輸入資料 x 的某些行相同。如果為 FALSE，則 keep.data 也必須為 false，並且將仍然返回 medoid 索引（即 medoids 的行號，即 i.med 元件），演算法透過少複製 x 來節省空間。
- keep.data: 邏輯值，指示是否應將 (如果 stand 為 true 則為縮放的) 資料儲存在結果中。將其設定為 FALSE 可以節省記憶體（從而節省時間），但會停用 clusplot()ing 結果。使用 medoids.x = FALSE 可以節省更多記憶體。
- rngR: 邏輯值，指示是否應使用 R 的隨機數生成器而不是 clara()-內建的隨機數生成器。如果為 true，這也意味著對 clara() 的每次呼叫都會返回不同的結果 - 儘管在良好的情況下只有細微的差異。
實際上有兩種方法可以檢視 CLARA 使用的結果。它們都使用函式應用程式返回的 class 為 clara 的物件。
第一種方法是繪製該物件，建立一個表示資料的圖表。因此，如果有 N 個物件被分成 K 個聚類，圖表必須包含 N 個點來表示這些物件，並且這些點必須用 K 種不同的顏色著色，每種顏色代表一個聚類集。例如，給定物件 clarax，它是函式 clara 應用程式的結果，要繪製該物件，只需
plot(clarax)
檢視 CLARA 應用程式結果的第二種方法是簡單地列印 class 為 clara 的物件的元件。例如，給定與上一個示例相同的物件 clarax，可以使用以下方法列印其元件
print(clarax)
示例
假設我們有 500 個物件，每個物件有兩個屬性（或特徵）。我們的目標是根據它們的兩個特徵將這些物件分成 K=2 個組。CLARA 函式可用於定義這些組，如下所示
## generate 500 objects, divided into 2 clusters. x <- rbind(cbind(rnorm(200,0,8), rnorm(200,0,8)), cbind(rnorm(300,50,8), rnorm(300,50,8))) ## run clara clarax <- clara(x, 2) clarax clarax$clusinfo ## print components of clarax print(clarax) ## plot clusters plot(x, col = clarax$cluster) ## plot centers points(clarax$centers, col = 1:2, pch = 8)
列印 clarax 元件的結果
Call: clara(x = x, k = 2)
Medoids:
[,1] [,2]
[1,] 1.091033 -0.5367556
[2,] 51.044099 51.0638017
Objective function: 9.946085
Clustering vector: int [1:500] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
Cluster sizes: 200 300
Best sample:
[1] 6 45 51 56 67 75 85 90 94 97 110 111 160 170 176 181 201 219 249
[20] 260 264 275 296 304 317 319 337 340 361 362 369 370 374 379 397 398 411 420
[39] 422 424 436 448 465 489
Available components:
[1] "sample" "medoids" "i.med" "clustering" "objective"
[6] "clusinfo" "diss" "call" "silinfo" "data"
繪製 "clarax" 的結果
圖 2: 繪製 clarax 的結果
在本節中，我們將說明使用 CLARA 的案例研究。
此資料集包含 1973 年美國 50 個州的攻擊、謀殺和強姦每 10 萬居民的逮捕統計資料。還給出了城市人口的百分比。
具有 50 個觀測值和 4 個變數的資料框。
- [,1] 謀殺 數值型 謀殺逮捕（每 10 萬人）
- [,2] 攻擊 數值型 攻擊逮捕（每 10 萬人）
- [,3] 城市人口 數值型 城市人口百分比
- [,4] 強姦 數值型 強姦逮捕（每 10 萬人）
| 州 | 謀殺 | 攻擊 | 城市人口 | 強姦 |
|---|---|---|---|---|
| 阿拉巴馬州 | 13.2 | 236 | 58 | 21.2 |
| 阿拉斯加州 | 10.0 | 263 | 48 | 44.5 |
| 亞利桑那州 | 8.1 | 294 | 80 | 31.0 |
| 阿肯色州 | 8.8 | 190 | 50 | 19.5 |
| 加利福尼亞州 | 9.0 | 276 | 91 | 40.6 |
| 科羅拉多州 | 7.9 | 204 | 78 | 38.7 |
| 康涅狄格州 | 3.3 | 110 | 77 | 11.1 |
| 特拉華州 | 5.9 | 238 | 72 | 15.8 |
| 佛羅里達州 | 15.4 | 335 | 80 | 31.9 |
| 佐治亞州 | 17.4 | 211 | 60 | 25.8 |
| 夏威夷州 | 5.3 | 46 | 83 | 20.2 |
| 愛達荷州 | 2.6 | 120 | 54 | 14.2 |
| 伊利諾伊州 | 10.4 | 249 | 83 | 24.0 |
| 印第安納州 | 7.2 | 113 | 65 | 21.0 |
| 愛荷華州 | 2.2 | 56 | 57 | 11.3 |
| 堪薩斯州 | 6.0 | 115 | 66 | 18.0 |
| 肯塔基州 | 9.7 | 109 | 52 | 16.3 |
| 路易斯安那州 | 15.4 | 249 | 66 | 22.2 |
| 緬因州 | 2.1 | 83 | 51 | 7.8 |
| 馬里蘭州 | 11.3 | 300 | 67 | 27.8 |
| 馬薩諸塞州 | 4.4 | 149 | 85 | 16.3 |
| 密歇根州 | 12.1 | 255 | 74 | 35.1 |
| 明尼蘇達州 | 2.7 | 72 | 66 | 14.9 |
| 密西西比州 | 16.1 | 259 | 44 | 17.1 |
| 密蘇里州 | 9.0 | 178 | 70 | 28.2 |
| 蒙大拿州 | 6.0 | 109 | 53 | 16.4 |
| 內布拉斯加州 | 4.3 | 102 | 62 | 16.5 |
| 內華達州 | 12.2 | 252 | 81 | 46.0 |
| 新罕布什爾州 | 2.1 | 57 | 56 | 9.5 |
| 新澤西州 | 7.4 | 159 | 89 | 18.8 |
| 新墨西哥州 | 11.4 | 285 | 70 | 32.1 |
| 紐約州 | 11.1 | 254 | 86 | 26.1 |
| 北卡羅來納州 | 13.0 | 337 | 45 | 16.1 |
| 北達科他州 | 0.8 | 45 | 44 | 7.3 |
| 俄亥俄州 | 7.3 | 120 | 75 | 21.4 |
| 俄克拉荷馬州 | 6.6 | 151 | 68 | 20.0 |
| 俄勒岡州 | 4.9 | 159 | 67 | 29.3 |
| 賓夕法尼亞州 | 6.3 | 106 | 72 | 14.9 |
| 羅德島州 | 3.4 | 174 | 87 | 8.3 |
| 南卡羅來納州 | 14.4 | 279 | 48 | 22.5 |
| 南達科他州 | 3.8 | 86 | 45 | 12.8 |
| 田納西州 | 13.2 | 188 | 59 | 26.9 |
| 德克薩斯州 | 12.7 | 201 | 80 | 25.5 |
| 猶他州 | 3.2 | 120 | 80 | 22.9 |
| 佛蒙特州 | 2.2 | 48 | 32 | 11.2 |
| 弗吉尼亞州 | 8.5 | 156 | 63 | 20.7 |
| 華盛頓州 | 4.0 | 145 | 73 | 26.2 |
| 西弗吉尼亞州 | 5.7 | 81 | 39 | 9.3 |
| 威斯康星州 | 2.6 | 53 | 66 | 10.8 |
| 懷俄明州 | 6.8 | 161 | 60 | 15.6 |
表 2: USArrests 資料庫
"clara" 函式的使用方式如下
## import data x <- USArrests ## run CLARA clarax <- clara(x[1:4], 3) ## print components of clarax print(clarax) ## plot clusters plot(x, col = clarax$cluster) ## plot centers points(clarax$centers, col = 1:2, pch = 8)
- plot(Assault, Murder)
(USArrests) points(254,11.1, pch=16) text(254,11.11, labels ='紐約') lines(Assault, (.63168 + (.04191 * Assault)))
下面顯示了列印函式應用返回的類元件的結果。
Call: clara(x = x[1:4], k = 3)
Medoids:
Murder Assault UrbanPop Rape
Michigan 12.1 255 74 35.1
Missouri 9.0 178 70 28.2
Nebraska 4.3 102 62 16.5
Objective function: 29.31019
Clustering vector: Named int [1:50] 1 1 1 2 1 2 3 1 1 2 3 3 1 3 3 3 3 1 ...
- attr(*, "names")= chr [1:50] "Alabama" "Alaska" "Arizona" "Arkansas" "California" "Colorado" "Connecticut" ...
Cluster sizes: 16 14 20
Best sample:
[1] Alabama Alaska Arizona Arkansas California
[6] Colorado Delaware Florida Georgia Idaho
[11] Illinois Indiana Iowa Kansas Kentucky
[16] Louisiana Maine Maryland Massachusetts Michigan
[21] Minnesota Mississippi Missouri Montana Nebraska
[26] Nevada New Hampshire New York North Carolina North Dakota
[31] Ohio Oklahoma Oregon Pennsylvania Rhode Island
[36] South Carolina South Dakota Tennessee Texas Utah
[41] Vermont Virginia Washington West Virginia Wisconsin
[46] Wyoming
Available components:
[1] "sample" "medoids" "i.med" "clustering" "objective"
[6] "clusinfo" "diss" "call" "silinfo" "data"
下面顯示了繪製函式應用返回的類的結果。
圖 3：示例結果
CLARA 的實現生成了三個相對同質的叢集，分別包含 16 個、14 個和 20 個國家。分析叢集均值，我們可以將每個組與三種州類別中的每一種相關聯。
- 由阿拉巴馬州、阿拉斯加州、亞利桑那州、加利福尼亞州、特拉華州、佛羅里達州、伊利諾伊州、路易斯安那州、馬里蘭州、密歇根州、密西西比州、內華達州、新墨西哥州、紐約州、北卡羅來納州、南卡羅來納州組成的叢集的謀殺、襲擊和強姦逮捕率最高（每 100,000 人），而且人口最多。
- 由阿肯色州、科羅拉多州、佐治亞州、馬薩諸塞州、密蘇里州、新澤西州、俄克拉荷馬州、俄勒岡州、羅德島州、田納西州、德克薩斯州、弗吉尼亞州、華盛頓州、懷俄明州組成的叢集的謀殺、襲擊和強姦逮捕率中等（每 100,000 人），而且人口最多。
- 由康涅狄格州、夏威夷州、愛達荷州、印第安納州、愛荷華州、堪薩斯州、肯塔基州、緬因州、明尼蘇達州、蒙大拿州、內布拉斯加州、新罕布什爾州、北達科他州、俄亥俄州、賓夕法尼亞州、南達科他州、猶他州、佛蒙特州、西弗吉尼亞州、威斯康星州組成的叢集的謀殺、襲擊和強姦逮捕率最低（每 100,000 人），而且人口最多。
根據 [3] 分析這兩個極端叢集（1、3）中的州，可以驗證每個國家位於這些組中的原因。加利福尼亞州雖然擁有良好的人類發展指數和個人收入中位數，但其失業率在美國排名第三，密歇根州排名第二，內華達州排名第一，這兩個州也位於叢集 1 中。康涅狄格州擁有最高的人類發展指數，位於叢集 3 中。懷俄明州擁有最高的高中畢業率，位於叢集 2 中。其他原因可以透過結合 [3] 對這項工作進行檢查來驗證。