R 中的資料探勘演算法/聚類/RockCluster
聚類是一種將資料點分組的有用技術，使得同一個組/聚類中的點具有相似的特徵（或彼此接近），而不同組中的點則不同。
我們描述了 ROCK（使用連結的穩健聚類）聚類演算法，它屬於凝聚層次聚類演算法類別。
下圖描述了使用 ROCK 進行聚類的步驟。從資料庫中抽取隨機樣本後，將採用連結的層次聚類演算法應用於取樣點。最後，僅包含取樣點的聚類用於將磁碟上的剩餘資料點分配到相應的聚類中。在以下小節中，我們首先詳細描述了 ROCK 執行的步驟。
ROCK 的層次聚類演算法在下圖中給出。它接受要聚類的 N 個取樣點集 S（從原始資料集隨機抽取）和所需的聚類數量 k 作為輸入。該過程從步驟 1 中計算點對之間的連結數開始。最初，每個點都是一個單獨的聚類。對於每個聚類 i，我們構建一個區域性堆 q[i]，並在演算法執行期間維護該堆。q[i] 包含每個聚類 j，使得 link[i,j] 不為零。q[i] 中的聚類 j 按相對於 i 的優度度量的降序排列，即 g(i,j)。
除了每個聚類 i 的區域性堆 q[i] 之外，該演算法還維護一個額外的全域性堆 Q，其中包含所有聚類。此外，Q 中的聚類按其最佳優度度量的降序排列。因此，g(j,max(q[j])) 用於對 Q 中的各種聚類 j 進行排序，其中 q[j] 中的最大元素 max(q[j]) 是與聚類 j 合併的最佳聚類。在每個步驟中，Q 中的最大聚類 j 和 q[j] 中的最大聚類是最佳合併聚類對。
對於每個點，在計算其鄰居列表後，該演算法考慮其所有鄰居對。對於每對鄰居，該點貢獻一個連結。如果對每個點重複該過程，並對每個鄰居對增加連結計數，那麼在結束時，所有點對的連結計數將被累加。如果 Mi 是點 i 的鄰居列表的大小，那麼對於點 i，我們必須在 M^2i 個條目中增加連結計數。因此，該演算法的複雜度是 M^2i 的總和，即 O(N * Mm * Ma)，其中 Ma 和 Mm 分別是點的平均鄰居數和最大鄰居數。在最壞情況下，Mm 的值為 n，在這種情況下，該演算法的複雜度變為 O(Ma * N^2)。在實踐中，我們期望 Mm 與 Ma 相當接近，因此，對於這些情況，該演算法的複雜度平均而言降低到 O(M^2a * n)。
為了在 R 中使用 ROCK 演算法，必須安裝“CBA”包。該包包含一個執行 RockCluster 過程的函式。
安裝 CBA 包
install.packages("cba")
匯入方法和演算法
library("cba")
用法
rockCluster(x, n, beta = 1-theta, theta = 0.5, fun = "dist", funArgs = list(method="binary"), debug = FALSE) rockLink(x, beta = 0.5)
引數
X: a data matrix; for rockLink an object of class dist. n: the number of desired clusters. beta: optional distance threshold. theta: neighborhood parameter in the range [0,1). fun: distance function to use. funArgs: a list of named parameter argu
如果一切順利，將返回一個 rockCluster 物件。該物件具有以下元件
x: the data matrix or a subset of it. cl: a factor of cluster labels. size: a vector of cluster sizes. beta: see above. theta: see above. rockLink: returns an object of class dist.
有一種方法可以顯示該演算法的結果。這種方法是列印 RockCluster 物件
print(RockObject)
例如，我們將使用“蘑菇”資料集與 CBA 包提供的演算法一起使用
data("Mushroom")
x <- as.dummy(Mushroom[-1])
rc <- rockCluster(x[sample(dim(x)[1],1000),], n=10, theta=0.8)
print(rc)
rp <- predict(rc, x)
table(Mushroom$class, rp$cl)
輸出 - 蘑菇
在本節中，我們說明了 RockCluster 的案例研究
從歷史上看，美國大選的特點是兩個主要的政黨。一個稱為**共和黨**，它通常反映了美國政治光譜中的保守主義，另一個稱為**民主黨**，被稱為更“自由”或“進步”。
我們的想法是使用 UCI 機器學習庫提供的美國國會投票資料庫，並執行 RockCluster 技術以將**民主黨**與**共和黨**分開。**
國會投票資料集是從 UCI 機器學習庫中獲取的。它是 1984 年的美國國會投票記錄。每個記錄對應於一位國會議員對 16 個議題的投票（例如，教育支出、犯罪）。所有屬性都是布林型的，具有“是”（即 1）和“否”（0）值，並且很少有屬性包含缺失值。每個資料記錄都提供了一個共和黨或民主黨的分類標籤。該資料集包含 168 名共和黨人和 267 名民主黨人的記錄。
R 程式碼:
data(Votes) x <- as.dummy(Votes[-17]) rc <- rockCluster(x, n=2, theta=0.73, debug=TRUE) print(rc) rf <- fitted(rc) table(Votes$Class, rf$cl)
下面展示了函式應用返回的類的元件列印結果。
如表所示，ROCK 和傳統演算法都識別出兩個叢集，一個包含大量共和黨人，另一個包含大多數民主黨人。然而，在傳統演算法發現的共和黨人叢集中，大約 25% 的成員是民主黨人，而對於 ROCK，只有 12% 是民主黨人。聚類質量的提升可歸因於 ROCK 使用連結。
- Meira Jr., W.; Zaki, M. 資料探勘演算法基礎。[1]
- CBA R 包。[2]
- UCI 機器學習庫 [3]
- Sudipto Guha; Rajeev Rastogi; Kyuseok Shim。ROCK：用於分類屬性的穩健聚類演算法