马尔科夫聚类算法

Question

我一直在研究马尔可夫聚类算法的细节，参考了以下示例：http://www.cs.ucsb.edu/~xyan/classes/CS595D-2009winter/MCL_Presentation2.pdf。我觉得我已经准确地表示了该算法，但是我并没有得到与该指南相同的结果。我目前的代码链接在这里：http://jsfiddle.net/methodin/CtGJ9/。

我不确定我是否错过了某些小问题或者只需要对某些内容进行微调，因为我尝试了几个变化包括：

1. 交换膨胀/扩张 2. 根据精度检查相等性 3. 删除归一化(因为原始指南不需要它，尽管官方MCL文档声明要在每次通过时正常化矩阵)

所有这些都返回了相同的结果——节点仅影响自身。

我甚至找到了一个类似的VB算法实现，链接在这里：http://mcl.codeplex.com/SourceControl/changeset/changes/17748#MCL%2fMCL%2fMatrix.vb，我的代码似乎与其匹配，除了它们的编号(例如600-距离)。

这是扩张函数。

// Take the (power)th power of the matrix effectively multiplying it with
// itself pow times
this.matrixExpand = function(matrix, pow) {
    var resultMatrix = [];
    for(var row=0;row<matrix.length;row++) {
        resultMatrix[row] = [];
        for(var col=0;col<matrix.length;col++) {
            var result = 0;
            for(var c=0;c<matrix.length;c++)
                result += matrix[row][c] * matrix[c][col];
            resultMatrix[row][col] = result;
        }
    }
    return resultMatrix;
}; 

这是通胀函数

// Applies a power of X to each item in the matrix
this.matrixInflate = function(matrix, pow) {
    for(var row=0;row<matrix.length;row++) 
        for(var col=0;col<matrix.length;col++)
            matrix[row][col] = Math.pow(matrix[row][col], pow);
};

最后是主要的传递函数

// Girvan–Newman algorithm
this.getMarkovCluster = function(power, inflation) {
    var lastMatrix = [];

    var currentMatrix = this.getAssociatedMatrix();
    this.print(currentMatrix);        
    this.normalize(currentMatrix);  

    currentMatrix = this.matrixExpand(currentMatrix, power);    
    this.matrixInflate(currentMatrix, inflation);                               
    this.normalize(currentMatrix);

    while(!this.equals(currentMatrix,lastMatrix)) {
        lastMatrix = currentMatrix.slice(0);

        currentMatrix = this.matrixExpand(currentMatrix, power);                
        this.matrixInflate(currentMatrix, inflation);         
        this.normalize(currentMatrix);            
    }
    return currentMatrix;
};

- methodin

---

这段程序相关的内容需要翻译成中文。请仅返回翻译后的文本：jsfiddle链接好像失效了，你的实现还能在其他地方找到吗？谢谢！ - skyork

奇怪，我不知道它去哪了？这里有一个代码要点：https://gist.github.com/methodin/1573728 - methodin

这里有一个CodePen链接：http://codepen.io/Xeoncross/pen/NqWqWe?editors=101 - Xeoncross

Answer 1

您的实现是正确的，示例是错误的。

“重复步骤5和6直到达到稳定状态（收敛）”幻灯片上的三个结果矩阵仅执行膨胀的结果。

为了澄清算法的一些要点：

1.先扩展再膨胀。

2.精度是一个重要因素。数学上方程永远不会导致收敛。它是CPU上浮点运算的有限精度使得矩阵中的某些项变为零而不是无限小的数字。事实上，正式实现使用截止值来消除每列的某个数量的项，以加速收敛并提高算法的时间复杂度。在原始论文中，作者分析了这种影响，并得出结论：截止值在实践中给出与膨胀参数略微增加相同的结果。

3.规范化是膨胀步骤的一个组成部分，请再次阅读指南中的等式。

关于您的代码：

1.array.slice创建一个浅拷贝，但在matrixExpand中创建一个新数组时，这并不重要。

2.您对matrixExpand的实现忽略了pow变量，并且总是进行2的幂次方。

预计第一行中全部为1的结果，这意味着所有元素都在同一个集群中。

- Michał Modzelewski

---

感谢您的澄清 - 我原以为这个例子可能展示了其他内容，但无法确定它是什么。 - methodin

Answer 2

使用 currentMatrix.slice 克隆矩阵看起来有些可疑。这是一个浅克隆，由于您正在进行变异，可能会带来麻烦。

使用 round 也看起来有些奇怪，因为在那个 PowerPoint 演示文稿中没有提到舍入作为归一化步骤的一部分。

- dyoo

---

添加了一个复制方法来运行完整的复制，但它仍然返回相同的结果。去掉 round 后会得到不同的结果，但只是 0.99999999877 而不是 1，以及 0.00004 而不是 0，因此实际上是相同的结果。我觉得奇怪的是，在第一次迭代（while 循环之前）后，矩阵与 PowerPoint 相同，但经过一次迭代后，它们完全不同。 - methodin

我能想到的另一件事，而不是更仔细地查看算法并手动操作它，就是你编写的equal()方法看起来不太对。它没有使用Math.abs进行比较，这让我感到意外。 - dyoo

尝试对每个部分和整体结果进行绝对值运算，但两者都没有影响结果。真的非常奇怪！我在想，也许我所参考的示例在不同的部分使用了不同的数据。 - methodin

我自己实现了大部分代码，没有参考你的代码。http://jsfiddle.net/qTZnw/ 看起来有一个类似的问题。一开始，数值看起来会收敛到给定的数字，但很快就会全部集中在第一行。你也是这种情况吗？ - kybernetikos