HCS-Clustering-Algorithmus - HCS clustering algorithm
| Klasse | Clusteranalyse (in einem Ähnlichkeitsdiagramm) |
|---|---|
| Datenstruktur | Graph |
| Worst-Case- Leistung | O (2N xf (n, m)) |
| Worst-Case -Raumkomplexität | {{{Raum}}} |
Der HCS-Clustering-Algorithmus (Highly Connected Subgraphs) (auch als HCS-Algorithmus bekannt , und andere Namen wie Highly Connected Clusters / Components / Kernels ) ist ein Algorithmus, der auf der Konnektivität von Graphen für die Clusteranalyse basiert . Es funktioniert, indem die Ähnlichkeitsdaten in einem Ähnlichkeitsgraphen dargestellt werden und dann alle stark verbundenen Untergraphen gefunden werden. Es werden keine vorherigen Annahmen über die Anzahl der Cluster getroffen. Dieser Algorithmus wurde im Jahr 2000 von Erez Hartuv und Ron Shamir veröffentlicht.
Der HCS-Algorithmus liefert eine Clustering-Lösung, die in der Anwendungsdomäne von Natur aus von Bedeutung ist, da jeder Lösungscluster den Durchmesser 2 haben muss, während eine Vereinigung zweier Lösungscluster den Durchmesser 3 hat.
Ähnlichkeitsmodellierung und Vorverarbeitung
Das Ziel der Clusteranalyse besteht darin, Elemente basierend auf der Ähnlichkeit zwischen Elementen in disjunkte Teilmengen oder Cluster zu gruppieren, sodass Elemente im selben Cluster einander sehr ähnlich sind (Homogenität), während Elemente aus verschiedenen Clustern eine geringe Ähnlichkeit zueinander aufweisen (Trennung). Der Ähnlichkeitsgraph ist eines der Modelle, um die Ähnlichkeit zwischen Elementen darzustellen und die Erzeugung von Clustern zu erleichtern. Um ein Ähnlichkeitsdiagramm aus Ähnlichkeitsdaten zu erstellen, stellen Sie Elemente als Scheitelpunkte dar und lösen Sie Kanten zwischen Scheitelpunkten aus, wenn der Ähnlichkeitswert zwischen ihnen über einem bestimmten Schwellenwert liegt.
Algorithmus
Je mehr Kanten im Ähnlichkeitsdiagramm für eine bestimmte Anzahl von Scheitelpunkten vorhanden sind, desto ähnlicher ist ein solcher Satz von Scheitelpunkten untereinander. Mit anderen Worten, wenn wir versuchen, ein Ähnlichkeitsdiagramm durch Entfernen von Kanten zu trennen, sind die Scheitelpunkte in diesem Diagramm umso ähnlicher, je mehr Kanten entfernt werden müssen, bevor das Diagramm getrennt wird. Der minimale Schnitt ist ein minimaler Satz von Kanten, ohne den das Diagramm getrennt wird.
Der HCS-Clustering-Algorithmus findet alle Untergraphen mit n Eckpunkten so, dass der minimale Schnitt dieser Untergraphen mehr als n / 2 Kanten enthält, und identifiziert sie als Cluster. Ein solcher Untergraph wird als Highly Connected Subgraph (HCS) bezeichnet. Einzelne Eckpunkte werden nicht als Cluster betrachtet und in einer Singletons-Menge S gruppiert.
Bei einem Ähnlichkeitsgraphen G (V, E) prüft der HCS-Clustering-Algorithmus, ob er bereits stark verbunden ist. Wenn ja, wird G zurückgegeben. Andernfalls wird der minimale Schnitt von G verwendet, um G in zwei Teilgraphen H und H 'zu unterteilen und rekursiv auszuführen HCS-Clustering-Algorithmus für H und H '.
Beispiel
Die folgende Animation zeigt, wie der HCS-Clustering-Algorithmus einen Ähnlichkeitsgraphen in drei Cluster unterteilt.
Pseudocode
function HCS(G(V, E)) is
if G is highly connected then
return (G)
else
(H1, H2, C) ← MINIMUMCUT(G)
HCS(H1)
HCS(H2)
end if
end function
Der Schritt zum Finden des minimalen Schnitts in Graph G ist eine Unterroutine, die unter Verwendung verschiedener Algorithmen für dieses Problem implementiert werden kann. Im Folgenden finden Sie einen Beispielalgorithmus zum Ermitteln des minimalen Schnitts mithilfe der Randomisierung.
Komplexität
Die Laufzeit des HCS-Clustering-Algorithmus ist durch N × f (n, m) begrenzt. f (n, m) ist die zeitliche Komplexität der Berechnung eines minimalen Schnitts in einem Graphen mit n Eckpunkten und m Kanten, und N ist die Anzahl der gefundenen Cluster. In vielen Anwendungen ist N << n.
Für schnelle Algorithmen zum Finden eines minimalen Schnitts in einem ungewichteten Diagramm:
Eigentumsnachweise
Die durch den HCS-Clustering-Algorithmus erzeugten Cluster besitzen mehrere Eigenschaften, die die Homogenität und Trennung der Lösung demonstrieren können.
Satz 1 Der Durchmesser jedes stark verbundenen Graphen beträgt höchstens zwei.
Beweis: Sei n = | G |. Wenn G einen Scheitelpunkt x mit dem Grad <= n / 2 hat, hat G einen minimalen Schnitt (der x isoliert) mit Kanten <= n / 2, so dass G nicht stark verbunden ist. Wenn also G stark verbunden ist, hat jeder Scheitelpunkt den Grad> = n / 2. In der Graphentheorie gibt es einen berühmten Satz, der besagt, dass, wenn jeder Scheitelpunkt einen Grad> = n / 2 hat, der Durchmesser von G (der längste Weg zwischen zwei beliebigen Knoten) <= 2 ist.
Satz 2 (a) Die Anzahl der Kanten in einem stark verbundenen Graphen ist quadratisch. (b) Die Anzahl der Kanten, die durch jede Iteration des HCS-Algorithmus entfernt werden, ist höchstens linear.
Beweis: (a) Aus Satz 1 wissen wir, dass jeder Scheitelpunkt einen Grad> = n / 2 hat. Daher muss die Anzahl der Kanten in einem stark verbundenen Graphen mindestens (n × n / 2) / 2 betragen, wobei wir die Grade jedes Scheitelpunkts summieren und durch 2 dividieren.
(b) Per Definition entfernt jede Iteration einen minimalen Schnitt mit <= n / 2 Kanten.
Die Sätze 1 und 2a liefern einen starken Hinweis auf die Homogenität eines endgültigen Clusters. Besseres Vorgehen ist der Fall, in dem alle Eckpunkte eines Clusters verbunden sind, was sowohl zu streng als auch NP-hart ist .
Satz 2b gibt die Trennung an, da zwei beliebige Endcluster C1 und C2 nicht getrennt worden wären, wenn nicht höchstens O (C1 + C2) Kanten zwischen ihnen gewesen wären (Kontrast zu den quadratischen Kanten innerhalb der Cluster).
Variationen
Übernahme von Singletons : Elemente, die beim ersten Clustering-Prozess als Singletons verbleiben, können von Clustern basierend auf der Ähnlichkeit mit dem Cluster "übernommen" werden. Wenn die maximale Anzahl von Nachbarn zu einem bestimmten Cluster groß genug ist, kann sie diesem Cluster hinzugefügt werden.
Entfernen von Scheitelpunkten mit niedrigem Grad: Wenn das Eingabediagramm Scheitelpunkte mit niedrigem Grad aufweist, ist es nicht sinnvoll, den Algorithmus auszuführen, da er rechenintensiv und nicht informativ ist. Alternativ kann eine Verfeinerung des Algorithmus zuerst alle Scheitelpunkte entfernen, deren Grad unter einem bestimmten Schwellenwert liegt.
Beispiele für die Verwendung von HCS
- Genexpressionsanalyse Die Hybridisierung von synthetischen Oligonukleotiden mit angeordneten cDNAs ergibt einen Fingerabdruck für jeden cDNA-Klon. Durch Ausführen des HCS-Algorithmus für diese Fingerabdrücke können Klone identifiziert werden, die demselben Gen entsprechen.
- Erkennung der PPI-Netzwerkstruktur Verwenden von HCS-Clustering zur Erkennung dichter Subnetze in PPI, die möglicherweise biologische Bedeutung haben und biologische Prozesse darstellen.
- "Übersicht über Clustering-Algorithmen." Neuronale Netze, IEEE-Transaktionen
- Der CLICK-Clustering-Algorithmus ist eine Anpassung des HCS-Algorithmus an gewichtete Ähnlichkeitsgraphen, bei denen das Gewicht mit einem Wahrscheinlichkeitsgeschmack versehen wird.
- https://www.researchgate.net/publication/259350461_Partitioning_Biological_Networks_into_Highly_Connected_Clusters_with_Maximum_Edge_Coverage Partitionierung biologischer Netzwerke in stark verbundene Cluster mit maximaler Kantenabdeckung]