HCS klaszterezési algoritmus - HCS clustering algorithm

A HCS (erősen összekapcsolt algráfok) klaszterezési algoritmus (más néven HCS algoritmus , és más nevek, például erősen összekapcsolt klaszterek / összetevők / kernelek ) egy grafikus kapcsolaton alapuló algoritmus a klaszteranalízishez , először a hasonlósági adatokat mutatva egy hasonlóságban grafikonra , majd utána megkeresi az összes szorosan összekapcsolt algráfot klaszterekként. Az algoritmus nem tesz semmiféle előzetes feltételezést a klaszterek számáról. Ezt az algoritmust Erez Hartuv és Ron Shamir 1998-ban tette közzé .

A HCS algoritmus olyan klaszterezési megoldást ad, amely lényegében jelentőséggel bír az alkalmazási tartományban, mivel minden megoldáscsoportnak átmérőjével kell rendelkeznie, 2, míg két oldatcsoport együttesének átmérője 3 lesz.

A hasonlóság modellezése és előfeldolgozása

A klaszteranalízis célja az elemek csoportosítása alcsoportokba vagy klaszterekbe, az elemek közötti hasonlóság alapján, úgy, hogy ugyanazon klaszter elemei nagyon hasonlóak legyenek egymáshoz (homogenitás), míg a különböző klaszterek elemei kis hasonlóságúak egymással (elválasztás). A hasonlósági grafikon az egyik modell, amely az elemek közötti hasonlóságot ábrázolja, és ezáltal megkönnyíti a klaszterek létrehozását. A hasonlósági adatokból való hasonlósági gráf elkészítéséhez ábrázolja az elemeket csúcsokként, és éleket vált ki a csúcsok között, ha a hasonlósági érték közöttük valamilyen küszöbérték meghaladja.

Algoritmus

A hasonlósági gráfban minél több éle létezik egy adott csúcs számához, annál hasonlóbb az ilyen csúcskészlet egymás között. Más szavakkal: ha megpróbálunk szétválasztani a hasonlósági gráfot élek eltávolításával, minél több élt kell eltávolítanunk, mielőtt a gráf leválasztódna, annál hasonlóbbak lesznek a csúcsok ebben a grafikonban. A minimális vágás az élek minimális halmaza, amely nélkül a grafikon leválasztódik.

A HCS klaszterezési algoritmus megtalálja az összes olyan n-csúcsú algráfot, amelyben az alsó rész minimális vágása több mint n / 2 élt tartalmaz, és klaszterekként azonosítja azokat. Egy ilyen algráfot erősen összekapcsolt algráfnak (HCS) hívnak . Az egyes csúcsok nem minősülnek klasztereknek, és szingulett halmazba vannak csoportosítva.

A G (V, E) hasonlósági gráfot figyelembe véve a HCS klaszterezési algoritmus megvizsgálja, hogy már szorosan kapcsolódik-e, ha igen, visszatér G-t, egyébként a G minimális vágását használja a G partícióba két H és H 'algráfra, és rekurzív módon fut. HCS klaszterezési algoritmus H-on és H '-en.

Példa

A következő animáció azt mutatja be, hogy a HCS klaszterezési algoritmus hogyan osztja meg a hasonlósági gráfot három klaszterre.

pszeudókód

1  function HCS(G(V,E))   
2    if G is highly connected
3      then return (G)
4    else
5     (H1,H2,C) ← MINIMUMCUT(G)
6      HCS(H1)
7      HCS(H2)
8    end if
9  end

A G gráf minimális vágásának megkeresése egy olyan szubrutin, amely különféle algoritmusok segítségével valósítható meg erre a problémára. Az alábbiakban található egy példa algoritmus a minimális vágás megtalálására randomizálás segítségével.

Bonyolultság

A HCS klaszterezési algoritmus futási idejét Nxf (n, m) határolja. f (n, m) a minimális vágás kiszámításának időbeli bonyolultsága n csúcs és m él mellett, N pedig a talált klaszterek száma. Sok alkalmazásban N << n.

Gyors algoritmusokhoz a minimális vágás meg nem súlyozott grafikonon történő megtalálásához:

A helyesség igazolása

A HCS klaszterezési algoritmus által előállított klaszterek számos tulajdonsággal rendelkeznek, amelyek igazolják az oldat homogenitását és szétválasztását.

1. tétel Minden erősen összekapcsoló gráf átmérője legfeljebb kettő.

Bizonyítás: Tudjuk, hogy a minimális vágás széleinek nagyobbnak vagy egyenlőnek kell lenniük a grafikon minimális fokával. Ha a G gráf szorosan kapcsolódik, akkor a minimális vágás széleinek nagyobbnak kell lennie, mint a csúcsok száma osztva 2-vel. Tehát a csúcsok fokának a nagymértékben összekapcsolt G gráfban nagyobbnak kell lennie, mint a csúcsok felének. Ezért a G grafikon bármelyik két csúcsának legalább egy közös szomszédnak kell lennie, mivel a távolság kettő.

2. tétel (a) Egy erősen összekapcsolt algráfban az élek száma négyzetes. b) A HCS algoritmus minden egyes ismétlésekor eltávolított élek száma legfeljebb lineáris.

Bizonyítás: (Az a) Az 1. tétel alapján tudjuk, hogy minden csúcsnak a teljes csúcsok több mint felének szomszédnak kell lennie. Ezért a nagyon összekapcsolt algráfban az élek teljes számának legalább (n / 2) xnx 1/2-nek kell lennie, ahol összeadjuk az egyes csúcsok összes fokát, és elosztjuk 2-del.

(B) Minden iterációs HCS algoritmus elkülöníti az n csúcsot tartalmazó gráfot két részgráfra, tehát a két elem közötti élek száma legfeljebb n / 2.

Az 1 és a 2a tétel határozottan jelzi a homogenitást, mivel az átmérő szempontjából az egyetlen jobb lehetőség, hogy a klaszter minden két csúcsa egy éllel van összekötve, ami egyaránt túl szigorú és NP-nehéz probléma .

A 2b. Tétel azt is jelzi az elválasztást, mivel a HCS algoritmus minden egyes iterációjával eltávolított élek száma legfeljebb lineáris a mögöttes algráf méretében, ellentétben az élek kvadratikus számával a végső klaszterekben.

Variációk

Szinguletták elfogadása : A kezdeti klaszterezési folyamat során szingulettként meghagyott elemeket a klaszterek a klaszterhez való hasonlóság alapján "elfogadhatják". Ha egy adott fürthez tartozó szomszédok maximális száma elég nagy, akkor hozzáadható az adott fürthez.

Alacsony fokú csúcsok eltávolítása : Ha a bemeneti gráfban alacsony fokú csúcsok vannak, nem érdemes az algoritmust futtatni, mivel számítási szempontból drága és nem informatív. Alternatív megoldásként az algoritmus finomítása először eltávolíthat minden csúcsot, amelynek bizonyos küszöbértéknél alacsonyabb fok van.

Példák a HCS használatára

• Gén expressziós elemzés A szintetikus oligonukleotidok hibridizációja elrendezett cDNS-ekké az egyes cDNS-klónok ujjlenyomatát eredményezi. A HCS algoritmus futtatása ezeken az ujjlenyomatokon azonos géneket azonosító klónokat képes azonosítani.

• PPI-hálózati struktúra felfedezése A HCS-fürtözés segítségével olyan sűrű alhálózatokat detektálunk a PPI-ben, amelyek biológiai jelentéssel bírhatnak és biológiai folyamatokat reprezentálhatnak.
• "A klaszterezési algoritmusok felmérése." Neurális hálózatok, IEEE tranzakciók
• A CLICK klaszterezési algoritmus a HCS algoritmus adaptációja súlyozott hasonlósági grafikonokon, ahol a súlyt valószínűségi aránnyal kell hozzárendelni.
• https://www.researchgate.net/publication/259350461_Partitioning_Biological_Networks_into_Highly_Connected_Clusters_with_Maximum_Edge_Coverage A biológiai hálózatok felosztása nagymértékben összekapcsolt klaszterekbe a maximális szélességgel]

• R dokumentáció

Irodalom