Grupowanie korelacji

Klastrowanie to problem dzielenia punktów danych na grupy na podstawie ich podobieństwa. Grupowanie korelacyjne zapewnia metodę grupowania zestawu obiektów w optymalną liczbę klastrów bez wcześniejszego określania tej liczby.

opis problemu

W uczeniu maszynowym grupowanie korelacji lub edytowanie klastrów działa w scenariuszu, w którym znane są relacje między obiektami zamiast rzeczywistych reprezentacji obiektów. Na przykład, biorąc pod uwagę $ważony,$ w którym waga krawędzi zadanie polega na znalezieniu grupowania, które albo maksymalizuje zgodność (suma dodatnich wag krawędzi w klastrze plus wartość bezwzględna sumy ujemnych wag krawędzi między klastrami), albo minimalizuje niezgodności (wartość bezwzględna sumy wag ujemnych krawędzi w klastrze plus suma dodatnich wag krawędzi w klastrach). W przeciwieństwie do innych algorytmów grupowania, nie wymaga to wcześniejszego wybierania liczby klastrów, $cel , jakim jest zminimalizowanie sumy wag ciętych krawędzi, jest niezależny od liczby klastrów.$

Może nie być możliwe znalezienie idealnego skupienia, w którym wszystkie podobne elementy znajdują się w klastrze, podczas gdy wszystkie niepodobne znajdują się w różnych klastrach. Jeśli graf rzeczywiście dopuszcza idealne skupienie, to po prostu usunięcie wszystkich ujemnych krawędzi i znalezienie połączonych elementów na pozostałym grafie zwróci wymagane skupienia.

Ale ogólnie graf może nie mieć idealnego grupowania. Na przykład, biorąc pod uwagę węzły a,b,c takie, że a,b i a,c są podobne, podczas gdy b,c są różne, idealne grupowanie nie jest możliwe. W takich przypadkach zadaniem jest znalezienie grupowania, które maksymalizuje liczbę zgodności (liczba + krawędzi wewnątrz klastrów plus liczba − krawędzi między klastrami) lub minimalizuje liczbę niezgodności (liczba − krawędzi wewnątrz klastrów plus liczba + krawędzi między klastrami). Ten problem maksymalizacji umów jest NP-zupełny (problem cięcia wielokierunkowego sprowadza się do maksymalizacji umów ważonych, a problem podziału na trójkąty można sprowadzić do wersji nieważonej).

Algorytmy

Bansala i in. omówić dowód NP-zupełności, a także przedstawić zarówno algorytm aproksymacji współczynników stałych, jak i schemat aproksymacji w czasie wielomianowym, aby znaleźć klastry w tym ustawieniu. Ailon i in. zaproponować losowy algorytm 3-aproksymacji dla tego samego problemu.

  CC-Pivot  (G = (V, E ⁺ , E ^- )) Wybierz losowy punkt obrotu ja ∈ V Ustaw do  $\ Displaystyle C = \ {i \}}$  , V'= Ø  Dla wszystkich  j ∈ V, j ≠ ja;  Jeśli  (i,j) ∈ E ⁺ następnie  Dodaj j do C  W przeciwnym razie  (Jeśli (i,j) ∈ E ⁻ ) Dodaj j do V' Niech G' będzie podgrafem indukowanym przez V'  Zwróć  skupienie C,CC-Pivot(G ')

Autorzy pokazują, że powyższy algorytm jest algorytmem 3-aproksymacyjnym dla grupowania korelacji. Najlepszy algorytm aproksymacji czasu wielomianowego znany obecnie dla tego problemu osiąga przybliżenie ~ 2,06 poprzez zaokrąglenie programu liniowego, jak wykazali Chawla , Makaryczew, Schramm i Jarosławcew .

Karpiński i Schudy udowodnili istnienie wielomianowego schematu aproksymacji czasu (PTAS) dla tego problemu na pełnych grafach i ustalonej liczbie klastrów.

Optymalna liczba klastrów

W 2011 roku Bagon i Galun wykazali, że optymalizacja funkcjonału grupowania korelacji jest ściśle związana z dobrze znanymi metodami optymalizacji dyskretnej . W swojej pracy zaproponowali analizę probabilistyczną podstawowego modelu niejawnego, który umożliwia korelacyjnemu funkcjonałowi klastrowania oszacowanie podstawowej liczby skupień. Ta analiza sugeruje, że funkcjonał zakłada jednolity a priori dla wszystkich możliwych partycji, niezależnie od ich liczby klastrów. W ten sposób powstaje niejednolita przeor nad liczbą klastrów.

W tej pracy zaproponowano kilka dyskretnych algorytmów optymalizacji, które skalują się z wdziękiem wraz z liczbą elementów (eksperymenty pokazują wyniki z ponad 100 000 zmiennych). Praca Bagona i Galuna oceniła również skuteczność odzyskiwania podstawowej liczby klastrów w kilku aplikacjach.

Grupowanie korelacji (eksploracja danych)

Grupowanie korelacji odnosi się również do innego zadania, w którym zakłada się, że korelacje między atrybutami wektorów cech w przestrzeni wielowymiarowej kierują procesem grupowania . Te korelacje mogą być różne w różnych klastrach, dlatego globalna dekorelacja nie może zredukować tego do tradycyjnego (nieskorelowanego) grupowania.

Korelacje pomiędzy podzbiorami atrybutów skutkują różnymi kształtami przestrzennymi skupień. Stąd podobieństwo między obiektami klastrów jest definiowane poprzez uwzględnienie lokalnych wzorców korelacji. Wraz z tym pojęciem termin ten został wprowadzony równocześnie z pojęciem omówionym powyżej. Różne metody klastrowania korelacji tego typu omówiono w, a związek z różnymi typami klastrowania jest omówiony w. Zobacz także Grupowanie danych wielowymiarowych .

Można wykazać, że grupowanie korelacyjne (zgodnie z tą definicją) jest ściśle związane z biclusteringiem . Podobnie jak w przypadku biclusteringu, celem jest zidentyfikowanie grup obiektów, które mają wspólną korelację w niektórych swoich atrybutach; gdzie korelacja jest zwykle typowa dla poszczególnych skupień.