R 中的資料探勘演算法/聚類/Proximus
隨著用於高保真設計和模擬的大規模計算平臺的可用性，以及用於收集科學和商業資料的儀器的可用性，人們越來越重視用於分析大型和極高維資料集的有效技術。這些資料集可能包含離散屬性，例如來自商業流程、資訊檢索和生物資訊學的屬性，以及來自科學模擬、天體物理測量和工程設計的連續屬性。
高維資料的分析通常採用提取資料項之間的相關性、發現數據中的有意義資訊、對資料項進行聚類以及找到聚類資料的有效表示、分類和事件關聯的形式。由於資料的體積（和維數）通常很大，因此新演算法的重點必須是效率和可擴充套件性，以適應大型資料集。
在本節中，我們將重點介紹 Proximus。預期的應用領域是將高維二進位制資料壓縮成代表性模式。例如，購買發生率（市場籃子資料）或術語-文件矩陣可以透過 Proximus 進行預處理，以便進行後續的關聯規則挖掘。在下一節中，我們將簡要說明該演算法的工作原理。
Proximus 演算法對邏輯矩陣的行進行聚類。演算法的壓縮率會受到最大聚類半徑和最小聚類大小選擇的影響。
該演算法屬於遞迴劃分型別。具體來說，在每一步，使用當前子矩陣（行集）的區域性秩一近似來嘗試進行二進位制劃分。這是一種將主成分專門用於二進位制資料的方法，它將矩陣表示為兩個二進位制向量的外部積。當子矩陣是純的時，節點擴充套件停止，即列（存在集）向量指示所有行，並且行（主要屬性集）模式向量之間的漢明距離或行集的大小小於或等於指定的閾值。如果秩一近似沒有導致劃分，但半徑約束被違反，則使用隨機行劃分矩陣並使用半徑約束。
該圖顯示了 proximus 的遞迴結構，其中 A 表示原始資料矩陣。每個矩形內部節點都是秩一近似，而這些節點的兩個圓形子節點是根據此近似從父矩陣的劃分得到的矩陣。遞迴樹的葉子對應於最終分解。總體分解為 ，其中 和 .
![{\displaystyle X=[x_{1},x_{01},x_{00}]^{T}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/91f13fc69bd10164bc3c260a0728e0b81f327aa7)
![{\displaystyle Y=[y_{1},y_{01},y_{00}]^{T}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f7c16038f74d7c1333b3640c36503f19939dff2a)
Proximus 是 cba 包的一部分。在本節中，您將找到有關如何在 R 環境中安裝和使用它的更多資訊。
在 R 控制檯中輸入以下命令以安裝 cba 包
install.packages("cba")
在 R 控制檯中輸入以下命令以載入該包
library("cba")
cba 包提供的 Proximus 函式可能按如下方式使用
proximus(x, max.radius = 2, min.size = 1, min.retry = 10, max.iter = 16, debug = FALSE)
其中引數是
x: a logical matrix. max.radius: the maximum number of bits a member in a row set may deviate from its dominant pattern. min.size: the minimum split size of a row set. min.retry: number of retries to split a pure rank-one approximation (translates into a resampling rate). max.iter: the maximum number of iterations for finding a local rank-one approximation. debug: optional debugging output.
具有以下元件的 proximus 類物件
nr: the number of rows of the data matrix. nc: the number of columns of the data matrix. a: a list containing the approximations (patterns). a$x: a vector of row (presence set) indexes. a$y: a vector of column (dominant attribute set) indexes. a$n: the number of ones in the approximated submatrix. a$c: the absolute error reduction by the approximation. max.radius: see arguments. min.size: see arguments. rownames: rownames of the data matrix. colnames: colnames of the data matrix.
有一種方法可以顯示此演算法的結果。該方法是輸入
summary(ProximusObject)
這裡我們有一個 proximus 演算法處理的示例。該示例非常簡單，並提供了一個關於它如何工作的想法。基本上，會生成一個統一的邏輯矩陣。然後，proximus 對原始邏輯矩陣進行秩 4 近似。
x <- rlbmat() pr <- proximus(x, max.radius=8, debug=TRUE) op <- par(mfrow=c(1,2), pty="s") lmplot(x, main="Data") box() lmplot(fitted(pr)$x, main="Approximation") box() par(op)
輸出
在本節中，我們將說明一個使用 Proximus 的案例研究。
在本節中，我們將使用 PROXIMUS 對假設資料庫中的術語進行聚類，以提取語義資訊。這意味著我們想要知道文件的主要主題是什麼。
假設有一個包含一些文件的庫，我們想要將這些文件分成幾類。我們可以將每個文件描述為該文件中出現的單詞集。
我們透過將術語對映到行，將列對映到文件，將資料表示為二進位制術語-文件矩陣，這樣，矩陣中的 TRUE 項就表示該詞在相應文件中存在。
下表顯示了 14 個術語和 10 個文件。顯然，有兩個片語：與計算機相關的詞和與作者相關的詞。詞語 love 是孤立的。
R 程式碼:
x <- matrix(scan("matriz.txt",what=logical(0),n = 14*10), 14, 10, byrow = TRUE)
pr <- proximus(x, max.radius=8, debug = TRUE)
summary(pr)
對術語和文件矩陣進行聚類得到的結果如下所示
如輸出所示，表格中顯示了聚類結果。很明顯，存在三個詞語組（每行一個組）。第一組與計算機相關。第二組與作者相關。第三組代表單個詞語“love”。名為“size”的列表示屬於同一個組的詞語數量。Proximus演算法將詞語聚類如下：組 1（計算機） = {intel, computer, software, linux, windows, Firefox, explorer, programming} 組 2（作者） = {kuth, shakespeare, grisham, asimov, book} 組 3（噪聲） = {love}
- Meira Jr., W.; Zaki, M. 資料探勘演算法基礎。 [1]
- CBA R 包。 [2]
- Koyuturk; Mehmet 和 Grama; Ananth。PROXIMUS：一個分析超高維離散屬性資料集的框架。
第九屆 ACM SIGKDD 國際知識發現與資料探勘大會 (KDD) 論文集，第 147-156 頁，2003 年。