HCS-klusterointialgoritmi - HCS clustering algorithm

HCS-klusterointialgoritmi
luokka Klusterianalyysi (samankaltaisuuskaaviossa)
Tietorakenne kaavio
Huonoin tapaus O (2N xf (n, m))
Pahimman tapauksen tilan monimutkaisuus {{{Tilaa}}}

HCS (Highly Connected Subgraphs) klusterointialgoritmi (tunnetaan myös HCS algoritmi , ja muilla nimillä, kuten erittäin Yhdistetty klusterit / Komponentit / ytimet ) on algoritmi, joka perustuu kuvaajan liitettävyys Ryhmittelyanalyysi , ensin edustaa samankaltaisuus datan samankaltaisuus kuvaaja , ja sen jälkeen löytää kaikki tiiviisti kytketyt aligraafit klusteriksi. Algoritmi ei tee aiempia oletuksia klustereiden lukumäärästä. Tämän algoritmin julkaisivat Erez Hartuv ja Ron Shamir vuonna 1998.

HCS-algoritmi antaa klusterointiratkaisun, jolla on luonnostaan ​​merkitystä sovellusalueella, koska jokaisella ratkaisuklusterilla on oltava halkaisija 2, kun taas kahden ratkaisuklusterin yhdistyksellä on halkaisija 3.

Samankaltaisuuden mallintaminen ja esikäsittely

Klusterianalyysin tavoitteena on ryhmitellä elementit erillisiin osajoukkoihin tai klustereihin elementtien välisen samankaltaisuuden perusteella siten, että saman klusterin elementit ovat hyvin samankaltaisia ​​toistensa kanssa (homogeenisuus), kun taas eri klusterien elementit ovat vähän samankaltaisia ​​keskenään (erottaminen). Samankaltaisuuskaavio on yksi malleista, joka edustaa elementtien välistä samankaltaisuutta ja puolestaan ​​helpottaa klustereiden muodostamista. Samankaltaisuuskaavion muodostamiseksi samankaltaisuustiedoista edustaa elementtejä kärkinä ja saa aikaan reunat kärkien välillä, kun niiden välinen samankaltaisuusarvo on jonkin kynnyksen yläpuolella.

algoritmi

Samankaltaisuuskaaviossa, mitä enemmän reunoja on tietyllä lukumäärällä huippuja, sitä samankaltaisempi tällainen piikkien joukko on keskenään. Toisin sanoen, jos yritämme irrottaa samankaltaisuusgraafin poistamalla reunat, sitä enemmän reunoja meidän on poistettava ennen kuvaajan irtoamista, sitä samankaltaisempia tämän kuvaajan pisteet ovat. Pienin leikkaus on vähimmäisreunajoukko, jota ilman kaavio irtoaa.

Katso myös: Yhteydet (kuvaaja_teoria)

HCS-klusterointialgoritmi löytää kaikki aligrafiikat, joissa on n kärkeä siten, että kyseisten aligraafien vähimmäisleikkaus sisältää enemmän kuin n / 2 reunaa, ja tunnistaa ne klusteriksi. Tällaista alakerrosta kutsutaan voimakkaasti kytketyksi alakerroksi (HCS). Yksittäisiä kärkipisteitä ei pidetä klustereina ja ne ryhmitellään singletonijoukkoon S.

Katso myös: Pienin leikkaus

Koska samankaltaisuuskäyrä G (V, E), HCS-klusterointialgoritmi tarkistaa onko se jo tiiviisti kytketty, jos kyllä, palauttaa G, käyttää muuten G: n vähimmäisleikkausta osioon G kahteen alagraafiikkaan H ja H ', ja suorittaa rekursiivisesti. HCS-klusterointialgoritmi H: llä ja H ': llä.

esimerkki

Seuraava animaatio osoittaa, kuinka HCS-klusterointialgoritmi jakaa samankaltaisuuskaavion kolmeen klusteriin.

HCS Algorithm.gif

pseudokoodi

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

Vaihe, jossa löydetään pienin leikkaus kuvaajaan G, on aliohjelma, joka voidaan toteuttaa käyttämällä erilaisia ​​algoritmeja tähän ongelmaan. Katso alla esimerkki algoritmista minimileikkauksen löytämiseksi satunnaistamista käyttämällä.

Monimutkaisuus

HCS-klusterointialgoritmin ajoaika rajoitetaan N xf (n, m). f (n, m) on graafisen minimileikkauksen laskennan aikakompleksi, jossa on n kärkeä ja m reunaa, ja N on löydettyjen klusterien lukumäärä. Monissa sovelluksissa N << n.

Nopeita algoritmeja varten, kun haluat löytää minimileikkauksen painottamattomasta kuvaajasta:

Katso myös: Kargerin algoritmi

Todistus oikeellisuudesta

HCS-klusterointialgoritmin tuottamilla klustereilla on useita ominaisuuksia, jotka voivat osoittaa ratkaisun homogeenisuuden ja erottumisen.

Lause 1 Jokaisen erittäin kytkettävän kuvaajan halkaisija on korkeintaan kaksi.

Todiste: Tiedämme, että minimileikkauksen reunojen on oltava suurempia tai yhtä suuria kuin kuvaajan vähimmäisaste. Jos kuvaaja G on tiukasti kytketty, silloin minimileikkauksen reunojen on oltava suurempia kuin kärkien lukumäärä jaettuna kahdella 2. Joten tiiviisti kytketyssä kuvaajassa G olevien kärkipisteiden on oltava suurempia kuin puolet kärkipisteistä. Siksi jokaisessa graafin G kahdessa huipussa on oltava ainakin yksi yhteinen naapuri, koska niiden välinen etäisyys on kaksi.

Katso myös: Etäisyys (kuvaajateoria)

Lause 2 (a) Tiiviisti kytketyssä alakerrossa olevien reunojen lukumäärä on neliö. (b) Jokaisella HCS-algoritmin iteraatiolla poistettujen reunojen lukumäärä on korkeintaan lineaarinen.

Todiste: (Kohdan a kohdalla) Laajasta 1 tiedämme, että jokaisessa kärkipisteessä on oltava yli puolet kokonaispisteistä naapureina. Siksi erittäin kytkettävän aligraafin reunojen kokonaismäärän on oltava vähintään (n / 2) xnx 1/2, jossa summataan kunkin kärkipisteen kaikki asteet ja jaetaan kahdella.

(B) Jokainen iteraatio-HCS-algoritmi erottaa n kärkipisteen sisältävän kuvaajan kahteen aligrafiikkaan, joten näiden kahden komponentin välisten reunojen lukumäärä on enintään n / 2.

Lause 1 ja 2a antavat vahvan osoituksen homogeenisyydestä, koska halkaisijan kannalta ainoa parempi mahdollisuus on, että rypäleen jokainen kaksi kärkeä on kytketty reunalla, mikä on molemmat liian tiukka ja myös NP-kova ongelma .

Lause 2b osoittaa myös erottelun, koska HCS-algoritmin jokaisella iteraatiolla poistettujen reunojen lukumäärä on korkeintaan lineaarinen alla olevan alakerran koosta, toisin kuin lopullisten rypäleiden neliömäinen reunojen lukumäärä.

Muunnelmat

Singletonien omaksuminen : Alkuperäisen klusterointiprosessin yksinkertaisina jättämät elementit voidaan "hyväksyä" klusterien samankaltaisuuden perusteella klusteriin. Jos tietyn klusterin naapureiden enimmäismäärä on riittävän suuri, se voidaan lisätä kyseiseen klusteriin.

Matala- asteisten pisteiden poistaminen : Kun syöttökaaviossa on matalilla asteilla olevia huipuja, algoritmin suorittaminen ei ole syytä, koska se on laskennallisesti kallis eikä informatiivinen. Vaihtoehtoisesti algoritmin tarkennus voi ensin poistaa kaikki kärkipisteet, joiden aste on tiettyä kynnysarvoa alempi.

Esimerkkejä HCS: n käytöstä

  • Geeniekspressioanalyysi Synteettisten oligonukleotidien hybridisoituminen järjestetyiksi cDNA: ksi antaa sormenjäljen jokaiselle cDNA-kloonille. Suorita HCS-algoritmi näillä sormenjäljillä voi tunnistaa saman geenin vastaavat kloonit.

Viitteet