Markowa klastrowania Algorytm

Question

pracuję poprzez następujący przykład o szczegółach algorytm klastrowania Markowa:

http://www.cs.ucsb.edu/~xyan/classes/CS595D-2009winter/MCL_Presentation2.pdf

czuję jakbym dokładnie reprezentuje algorytm, ale nie otrzymuję takie same wyniki że ten poradnik przynajmniej dostał dla tego wejścia.

Aktualny kod jest pod adresem: http://jsfiddle.net/methodin/CtGJ9/

Nie jestem pewien, czy może mam po prostu brakowało mały fakt, czy wystarczy mały uszczypnąć gdzieś na tym, ale próbowałem kilka odmian, w tym:

1. Zamiana inflacja/Expansion
2. Sprawdzanie równości opiera się na precyzyjnym
3. Usuwanie normalizację (ponieważ oryginalny przewodnik nie wymagają, chociaż oficjalna MCL d Stany dokumentacji do normalizacji macierzy na każdym przejściu)

Wszystkie te elementy zwróciły ten sam wynik - węzeł wpływa tylko na siebie.

mam nawet znaleźć podobną realizację algorytmu w VB: http://mcl.codeplex.com/SourceControl/changeset/changes/17748#MCL%2fMCL%2fMatrix.vb

A mój kod wydaje się zgadzać z wyjątkiem ich numeracji (600 - odległość, na przykład).

Jest to funkcja ekspansja

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

I to jest funkcja inflacja

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

I wreszcie główną funkcją 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

Twoje wdrożenie jest poprawne. Przykład jest po prostu zły.

Trzy macierze wynikowe na "Powtórz kroki 5 i 6, aż do osiągnięcia stanu ustalonego (zbieżność)" są wynikiem TYLKO wykonywania inflacji.

Aby wyjaśnić niektóre punkty dotyczące algorytmu.

1. Expantion then inflation.
2. Precyzja jest ważnym czynnikiem. Równania nigdy nie prowadzą do matematycznej konwergencji. Jest to ograniczona precyzja operacji zmiennoprzecinkowych na cpus, które powodują, że niektóre elementy w macierzy stają się zerowe, a nie nieskończenie małe.W rzeczywistości oficjalne wdrożenie wykorzystuje wartość odcięcia, aby wyeliminować pewną liczbę pozycji na kolumnę, aby przyspieszyć konwergencję i poprawić złożoność czasu algorytmu. W oryginalnej tezie autor przeanalizował efekt tego i doszedł do wniosku, że odcięcie daje w praktyce taki sam wynik, jak nieznaczny wzrost parametru inflacji.
3. Normalizacja jest integralną częścią kroku inflacji, przeczytaj równanie w tym przewodniku ponownie.

Odnośnie Twojego kodu.

1. array.slice tworzy płytką kopię, ale to nie ma znaczenia w twoim przypadku, ponieważ tworzysz nową tablicę w matrixExpand.
2. Twój realizacja matrixExpand ignoruje zmienną pow i zawsze potęgą 2.

Wynik gdzie są wszystkie te, w pierwszym rzędzie jest oczekiwane, co interpretowane jest jako wszystkie elementy są w tym samym grupa.

Answer 2

Korzystanie currentMatrix.slice sklonować matrycę wygląda podejrzanie. To płytki klon, a ponieważ mutujesz, może to oznaczać kłopoty.

Korzystanie z rundy również wygląda trochę dziwnie, ponieważ nie ma wzmianki o zaokrągleniu jako części kroku normalizacji w tej prezentacji Powerpoint.