Wybierz najlepszy partycji klastra opartego na funkcji kosztu

Question

Mam ciąg znaków, który chciałbym klastra:

s = 'AAABBCCCCC' 

nie wiem z góry, ile klastry dostanę. Wszystko, co mam, to funkcja kosztowa, która może zająć skupienie i dać mu wynik.

Istnieje również ograniczeniem wielkości klastra: muszą być w przedziale [a, b]

W moim exemple dla a=3 i b=4, wszystko jest możliwe grupowanie to:

[ 
    ['AAA', 'BBC', 'CCCC'], 
    ['AAA', 'BBCC', 'CCC'], 
    ['AAAB', 'BCC', 'CCC'], 
] 

Łączenie poszczególnych klastrów musi dać String s

funkcja kosztu jest coś takiego

cost(clustering) = alpha*l + beta*e + gamma*d 

gdzie:

• l = variance(cluster_lengths)
• e = mean(clusters_entropies)
• d = 1 - nb_characters_in_b_that_are_not_in_a)/size_of_b (na b rzędu klaster a)
• alpha, beta, gamma są ciężary

Ta funkcja kosztów daje niski koszt (0) dla najlepszego przypadku:

1. Gdzie wszystkie klastry mają ten sam rozmiar.
2. Zawartość wewnątrz każdego klastra jest taka sama.
3. Kolejne klastry nie mają tej samej treści.

Teoretycznie rozwiązaniem jest obliczenie kosztu wszystkich możliwych compositions dla tego ciągu i wybranie najniższego. ale zajmie to zbyt dużo czasu.

Czy istnieje algorytm klastrowania, który może znaleźć najlepsze skupienie zgodnie z tą funkcją kosztów w rozsądnym czasie?

Answer 1

Powinno tu działać podejście dynamicznego programowania.

Wyobraź sobie, po pierwsze, że cost(clustering) jest równa sumie cost(cluster) dla wszystkich wszystkich klastrów tworzących klaster.

Następnie prosta funkcja DP jest zdefiniowany następująco:

F[i] = minimal cost of clustering the substring s[0:i]

i oblicza się w następujący sposób:

for i = 0..length(s)-1: 
    for j = a..b: 
     last_cluster = s[i-j..i] 
     F[i] = min(F[i], F[i - j] + cost(last_cluster)) 

Oczywiście, najpierw trzeba zainicjować wartości F do niektóre nieskończone wartości lub wartości null, aby poprawnie zastosować funkcję min.

Aby rzeczywiście przywrócić odpowiedź, można zapisać dodatkowe wartości P[i], które będą zawierać długości ostatniego klastra z optymalnym grupowaniem ciągu s [0..i]. Po aktualizacji F [i] aktualizujesz także P[i].

Następnie, przywracając odpowiedź jest mały kłopot:

current_pos = length(s) - 1 
while (current_pos >= 0): 
    current_cluster_length = P[current_pos] 
    current_cluster = s[(current_pos - current_cluster_length + 1)..current_pos] 
    // grab current_cluster to the answer 
    current_pos -= current_cluster_length 

Należy zauważyć, że w tym podejściu dostaniesz clsuters w kolejności odwrotnej, czyli od ostatniego klastra całą drogę do pierwszego.

Zastosujmy teraz ten pomysł do początkowego problemu. Chcielibyśmy, aby koszt (grupowanie) był mniej więcej liniowy, abyśmy mogli obliczyć go za pomocą klastra zamiast go obliczać dla całego skupienia.

Pierwszy parametr funkcji naszego DP F będzie, jak dotychczas, i, liczba znaków w podciągu s[0:i] Znaleźliśmy optymalną odpowiedź. Znaczenie funkcji F to, jak zwykle, minimalny koszt, jaki możemy osiągnąć przy danych parametrach.

Parametr e = mean(clusters_entropies) funkcji kosztu jest już liniowy i można go obliczyć klastrze według klastra, więc nie stanowi to problemu.

Parametr l = variance(cluster_lengths) jest nieco bardziej złożony. Wariancja wartości n jest zdefiniowana jako Sum[(x[i] - mean)^2]/n. mean to wartość oczekiwana, a mianowicie mean = Sum[x[i]]/n. Należy również zauważyć, że Sum[x[i]] to suma długości wszystkich klastrów, w naszym przypadku jest zawsze stała i jest równa length(s). Dlatego mean = length(s)/n. Okej, mamy mniej lub więcej niż jedną część funkcji kosztu liniowego, z wyjątkiem parametru n. Dodamy ten parametr, a mianowicie liczbę klastrów w pożądanym skupieniu, jako parametr do naszej funkcji F. Będziemy również mieć parametr cur, który będzie oznaczać liczbę klastrów aktualnie złożonych w danym stanie.

Parametr d funkcji kosztu wymaga dodawania dodatkowego parametru dla funkcjonowania, a mianowicie DP Fj, sz, rozmiaru klastra w naszej ostatniej strefie.

Ogólnie rzecz biorąc, mają pochodzić z funkcji DP F[i][n][cur][sz] który daje nam minimalną funkcję kosztową partycjonowania ciąg s[0:i] do n klastrów których cur obecnie budowanych z wielkością ostatniego klastra równej sz. Naszym obowiązkiem jest oczywiście upewnić się, że a<=sz<=b. Odpowiedź pod względem funkcji minimalnego kosztu będzie minimalna spośród wszystkich możliwych wartości n i a<=sz<=b funkcji DP F[length(s)-1][n][n][sz]. Teraz zauważ, że tym razem nie potrzebujemy nawet funkcji towarzyszącej P do przechowywania długości ostatniego klastra, ponieważ już uwzględniliśmy tę informację jako ostatni parametr sz w naszej funkcji F. Będziemy jednak przechowywać w P[i][n][cur][sz] długość następnego do ostatniego klastra w optymalnym zgrupowaniu z określonymi parametrami. Wykorzystamy tę wartość do przywrócenia naszego rozwiązania. ten sposób będziemy w stanie przywrócić odpowiedzieć w następujący sposób, zakładając minimum F osiąga w parametrach n=n0 i sz=sz0:

current_pos = length(s) - 1 
current_n = n0 
current_cluster_size = sz0 
while (current_n > 0): 
    current_cluster = s[(current_pos - current_cluster_size + 1)..current_pos] 
    next_cluster_size = P[current_pos][n0][current_n][current_cluster_size] 
    current_n--; 
    current_pos -= current_cluster_size; 
    current_cluster_size = next_cluster_size 

Chodźmy teraz dostać się do obliczania F. Pomijam przypadki narożne i sprawdzanie zasięgu, ale wystarczy tylko zainicjować F z pewnymi nieskończonymi wartościami.

// initialize for the case of one cluster 
// d = 0, l = 0, only have to calculate entropy 
for i=0..length(s)-1: 
    for n=1..length(s): 
     F[i][n][1][i+1] = cluster_entropy(s[0..i]); 
     P[i][n][1][i+1] = -1; // initialize with fake value as in this case there is no previous cluster 

// general case computation 
for i=0..length(s)-1: 
    for n=1..length(s): 
     for cur=2..n: 
      for sz=a..b: 
       for prev_sz=a..b: 
        cur_cluster = s[i-sz+1..i] 
        prev_cluster = s[i-sz-prev_sz+1..i-sz] 
        F[i][n][cur][sz] = min(F[i][n][cur][sz], F[i-sz][n][cur - 1][prev_sz] + gamma*calc_d(prev_cluster, cur_cluster) + beta*cluster_entropy(cur_cluster)/n + alpha*(sz - s/n)^2)