Марковский алгоритм кластеризации

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

И, наконец, основная функция passthru

// 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. Точность является важным фактором.Уравнения никогда не могут привести к математической сходимости.Это ограниченная точность операций с плавающей запятой на процессоре, которые приводят к тому, что некоторые элементы в матрице становятся нулевыми, а не бесконечно малыми числами.Фактически официальная реализация использует предельное значение, чтобы исключить определенное количество элементов в столбце, чтобы ускорить сходимость и улучшить временную сложность алгоритма.В оригинальном тезисе автор проанализировал эффект этого и пришел к выводу, что отсечение дает на практике тот же результат, что и незначительное увеличение параметра инфляции.
3. Нормализация является неотъемлемой частью шага инфляции, прочитайте уравнениев этом руководстве снова.

Относительно вашего кода.

1. array.slice создает поверхностную копию, но это не важно в вашем случае, так как вы создаете новый массив в matrixExpand.
2. Ваша реализация matrixExpand игнорирует переменную pow и всегда имеет степень 2.

Ожидается результат, когда в первой строке есть все единицы, который интерпретируется каквсе элементы находятся в одном кластере.

Answer 2

Использование currentMatrix.slice для клонирования матрицы выглядит подозрительно. Это мелкий клон, и, поскольку вы мутируете, это может вызвать проблемы.

Использование округления также выглядит немного странно, поскольку в представлении PowerPoint нет упоминания о округлении как части шага нормализации.