Algoritmul de clustering HCS - HCS clustering algorithm

The HCS (Foarte Connected subgrafurilor) clustering algoritm ( de asemenea , cunoscut sub numele de algoritmul HCS , și alte nume , cum ar fi Clustere foarte Connected / Componente / Miezuri ) este un algoritm bazat pe conectivitate grafic pentru analiza cluster , mai întâi prin reprezentarea datelor similaritate într - o similitudine grafic și, ulterior, găsirea tuturor subgrafelor foarte conectate ca cluster. Algoritmul nu face presupuneri anterioare cu privire la numărul de clustere. Acest algoritm a fost publicat de Erez Hartuv și Ron Shamir în 1998.

Algoritmul HCS oferă o soluție de clustering, care este inerent semnificativă în domeniul aplicației, deoarece fiecare grup de soluții trebuie să aibă diametrul 2, în timp ce o uniune a două grupuri de soluții va avea diametrul 3.

Modelare similară și preprocesare

Scopul analizei clusterului este gruparea elementelor în subseturi disjuncte sau clustere, bazate pe asemănarea dintre elemente, astfel încât elementele din același cluster să fie extrem de asemănătoare între ele (omogenitate), în timp ce elementele din clustere diferite au o similaritate scăzută între ele. (separare). Graficul de asemănare este unul dintre modelele care reprezintă similitudinea dintre elemente și, la rândul său, facilitează generarea de clustere. Pentru a construi un grafic de asemănare din date de similitudine, reprezintă elemente ca vertexuri și scoateți muchii între vârfuri atunci când valoarea de similaritate între ele este peste un prag.

Algoritmul

În graficul de asemănare, cu cât există mai multe muchii pentru un număr dat de vârfuri, cu atât este mai asemănător un astfel de set de vertexuri între ele. Cu alte cuvinte, dacă încercăm să deconectăm un grafic de asemănare eliminând marginile, cu cât trebuie să eliminăm mai multe muchii înainte de a deconecta graficul, cu atât sunt mai similare vârfurile din acest grafic. Tăierea minimă este un set minim de margini fără de care graficul nu va fi deconectat.

Algoritmul de clustering HCS găsește toate subgrafele cu n vârfuri astfel încât tăierea minimă a acelor subgrafe conțin mai mult de n / 2 muchii și le identifică ca grupuri. O astfel de subgrafă se numește Subgrafă cu conectare înaltă (HCS). Vârfurile unice nu sunt considerate clustere și sunt grupate într-un set S singleton.

Având în vedere un grafic de asemănare G (V, E), algoritmul de clustering HCS va verifica dacă acesta este deja foarte conectat, dacă da, returnează G, altfel folosește tăierea minimă a lui G pentru a partiționa G în două subgrafe H și H 'și a rula recursiv. Algoritmul de clustering HCS pe H și H '.

Exemplu

Următoarea animație arată cum algoritmul de clustering HCS repartizează un grafic de similaritate în trei clustere.

Pseudo cod

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

Etapa de a găsi reducerea minimă a graficului G este o subrutină care poate fi implementată folosind algoritmi diferiți pentru această problemă. Vedeți mai jos un exemplu de algoritm pentru a găsi o reducere minimă folosind randomizarea.

Complexitate

Durata de rulare a algoritmului de clustering HCS este delimitată de N xf (n, m). f (n, m) este complexitatea în timp a calculării unei tăieri minime într-un grafic cu n vârfuri și m muchii, iar N este numărul de clustere găsite. În multe aplicații N << n.

Pentru algoritmi rapide pentru găsirea unei tăieri minime într-un grafic neponderat:

Dovada corectitudinii

Clusterele produse de algoritmul de clustering HCS posedă mai multe proprietăți, care pot demonstra omogenitatea și separarea soluției.

Teorema 1 Diametrul fiecărui grafic extrem de conectat este cel mult două.

Dovadă: Știm că marginile tăierii minime trebuie să fie mai mari sau egale decât gradul minim al graficului. Dacă graficul G este extrem de conectat, atunci marginile tăierii minime trebuie să fie mai mari decât numărul de vârfuri împărțite la 2. Deci, gradul de vârfuri din graficul G foarte conectat trebuie să fie mai mare decât jumătate din vârfuri. Prin urmare, pentru oricare două vârfuri din acest grafic G, trebuie să existe cel puțin un vecin comun, deoarece distanța dintre ele este de două.

Teorema 2 (a) Numărul de muchii dintr-o subgrafă extrem de conectată este pătrat. (b) Numărul de muchii eliminate de fiecare iterație a algoritmului HCS este cel mult liniar.

Dovadă: (Pentru a) Din teorema 1 știm că fiecare vertex trebuie să aibă mai mult de jumătate din vârfurile totale ca vecini. Prin urmare, numărul total de muchii dintr-o subgrafă extrem de conectată trebuie să fie cel puțin (n / 2) xnx 1/2, unde adunăm toate gradele fiecărui vertex și împărțim cu 2.

(Pentru b) Fiecare algoritm de iterație HCS va separa un grafic care conține n vârfuri în două subgrafe, deci numărul de muchii între cele două componente este cel mult n / 2.

Teorema 1 și 2a oferă o indicație puternică a omogenității, deoarece singura posibilitate mai bună în ceea ce privește diametrul este că fiecare două vârfuri ale unui cluster sunt conectate de o margine, care este atât de strictă, cât și de o problemă dură NP .

Teorema 2b indică, de asemenea, separarea, deoarece numărul de muchii eliminate prin fiecare iterație a algoritmului HCS este cel mult liniar în mărimea subgrafiei subiacente, în contrast cu numărul patratic de muchii din clustere finale.

Variații

Adoptarea Singletons : Elementele lăsate ca singletoni de procesul inițial de clustering pot fi „adoptate” de clustere pe baza asemănării cu clusterul. Dacă numărul maxim de vecini de un anumit cluster este suficient de mare, atunci acesta poate fi adăugat la acel grup.

Înlăturarea vertexurilor de grad scăzut : Când graficul de intrare are vârfuri cu grade scăzute, nu este demn să rulați algoritmul, deoarece este calculativ costisitor și nu informativ. Alternativ, un rafinament al algoritmului poate elimina mai întâi toate vârfurile cu un grad mai mic decât un anumit prag.

Exemple de utilizare HCS

• Analiza expresiei genice Hibridizarea oligonucleotidelor sintetice la ADNc-urile arătate produce o amprentă pentru fiecare clonă de ADNc. Execută algoritmul HCS pe aceste amprente poate identifica clone corespunzătoare aceleiași gene.

• Descoperirea structurii rețelei PPI Folosind gruparea HCS pentru a detecta subrețelele dense în PPI care pot avea semnificație biologică și care reprezintă procese biologice.
• „Sondaj de algoritmi de clustering”. Rețele neuronale, tranzacții IEEE
• Algoritmul de clustering CLICK este o adaptare a algoritmului HCS pe grafice de asemănare ponderate, unde greutatea este atribuită cu o aromă de probabilitate.
• https://www.researchgate.net/publication/259350461_Partitioning_Biological_Networks_into_Highly_Connected_Clusters_with_Maximum_Edge_Coverage Partition Biworks Networks in Clusters High Connected cu acoperire maximă de margine]

• Documentația R

Referințe