關於大型稀疏矩陣上的親和力傳播聚類

Question

我正在嘗試R包apcluster上我想要羣集的對象，但我遇到性能/內存問題，並且我懷疑我做得不對。我想聽聽你的意見。

總之：我有一套約13000個對象。每個對象都與一組2到5個「特徵」相關聯。任何兩個對象i和j之間的相似性（最終我想要聚類）等於它們共有的特徵數量除以它們「跨越」的不同特徵的總數量。例如。如果i = {a，b，c}和j = {c，d}，那麼sim [i，j] = 1/4 = 0.25，因爲它們只有1個共同特徵（{c}），描述4個不同的特徵（{a，b，c，d}）。

計算我的NxN相似度矩陣不是問題理論上：如果每個對象的特徵都作爲列表存儲，則可以使用集合操作完成;或特徵可以旋轉到1和0的矩陣，其中每列是一個特徵，然後R的函數dist與method="binary"有訣竅。

然而，在實踐中然而，第一個問題是這種相似性計算非常慢。對於13 K的物體，計算的相似度大約爲84.5 M，但對於現代計算機來說，這聽起來不那麼糟糕。我不明白爲什麼需要幾個小時才能做到這一點。而據我所知，設置的操作版本應該更快，實際上比dist慢得多。 [另一個名爲fingerprint的軟件包應該可以更有效地處理這種情況，但到目前爲止，我還沒有能夠使其工作，但在嘗試製作他們稱之爲「featvec」對象時出現了很多錯誤）。

要考慮的另一件事是每個對象2-5個特徵不是很重複。可能有一組100個左右的對象，它們之間至少有一個共同的特徵，但是其他12.9個K對象沒有任何特徵與這100個對象有共同之處。結果是旋轉的特徵矩陣非常稀疏（如果我們認爲0是空的）。樞軸矩陣中有大約4000列，每行至多有5個1。我想知道這是否會對dist的性能產生負面影響，因爲它必須乘以很多0才能被忽略。

對於像你所描述的那個矩陣應用dist需要幾個小時的時間，對你來說這是否正常？你能否提出一種不同的方法來計算利用矩陣稀疏性的相似性？

無論如何，我設法從dist，然而有類「DIST」得到的輸出，並且是距離矩陣，而不是相似，所以我只好用1 - as.matrix(distance_matrix)才能夠使相似矩陣apcluster需要作爲輸入。

那是當我得到第一個'記憶'問題。 R表示，由於它的大小，矢量不能被分配。我嘗試了通常的技巧，但最終我無法獲得超過4 GB的性能，而且我的矩陣（顯然）更大。

我克服了這一點，每次將新的矩陣分配給舊的「自我」。

然後當我提交這個辛辛苦苦的相似度矩陣到apcluster時，再次出現矢量大小錯誤，就好像apcluster所做的第一件事是從我所餵食的東西中創建了一些其他大對象。

我看過as.Sparse...在apcluster，但它似乎沒有什麼幫助，考慮到你必須首先計算全矩陣。

最後，唯一有效的工作是apclusterL的「槓桿親和力傳播」，但這是近似值。

有沒有人知道我是否可以做得更好？例如。首先轉換數據是明智的，還是應該堅持列表並設置操作？或者，可以將初始矩陣稀疏的事實用於直接計算稀疏矩陣，而不是完全計算並將其減少到稍後稀疏？

任何意見將不勝感激。謝謝！

順便說一句，是的，我看到這個線程：Cluster Analysis in R on large sparse matrix;這似乎沒有得到有力的回答。

Answer 1

R解釋器真的很慢。所以你應該使用R主要是爲了「驅動」你的程序，但是在C或者FORTRAN中實現所有的計算重量。

你沒有顯示你正在使用的代碼，但我猜它涉及嵌套for循環？嘗試在R中沒有任何for循環來重寫它，或者用C重寫它。

但是無論如何，AP羣集總是會保持非常緩慢。它涉及O（n2）矩陣的很多遍歷，即它的縮放非常糟糕。