关于大型稀疏矩阵上的亲和力传播聚类

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）矩阵的很多遍历，即它的缩放非常糟糕。