javascript - 马尔可夫聚类算法

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;
};

Answer 1

您的实现是正确的。这个例子是错误的。

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

阐明算法的一些要点。

1. 扩张然后通货膨胀。
2. 精度是一个重要因素。这些方程永远不会导致数学上的收敛。是 cpus 上浮点运算的有限精度导致矩阵中的某些项变为零而不是无限小的数字。实际上官方实现是用一个cutoff值来剔除每列一定数量的item来加速收敛，提高算法的时间复杂度。在最初的论文中，作者分析了这一点的影响，并得出结论，在实践中，截止值与略微增加通货膨胀参数的结果相同。
3. 归一化是膨胀步骤不可或缺的一部分，请再次阅读该指南中的等式。

关于您的代码。

1. array.slice 创建一个浅拷贝，但这对您来说并不重要，因为您在 matrixExpand 中创建了一个新数组。
2. 您的 matrixExpand 实现忽略了 pow 变量，并且始终执行 2 的幂。

第一行全1的结果是预期的，这被解释为所有元素都在同一个簇中。