Random Edge deletion clustering
Gert Sluiter · 2019
Data Mining beschaftigt sich mit dem Gewinn von Wissen und der Suche nach Mustern in Daten. In der explorativen Datenanalyse konnen Clustering Algorithmen verwendet werden um Grup- pen ahnlicher Objekte in Daten zu finden. Solche Clustering Algorithmen basieren in der Regel auf einer Annahme fur die Verteilung innerhalb der Daten und folgen einem festen Schema, wie ahnliche Objekte in Gruppen aufgeteilt werden. Was passiert, wenn Zufallseffekte in Kombi- nation mit der paarweisen Ahnlichkeit, als Wahrscheinlichkeit einer Verbindung der Objekte in dem clustering Prozess genutzt werden? Diese Arbeit beschaftigt sich mit der Entwicklung und Analyse eines hierarchischen Clustering Algorithmus. Dieser beruht auf einem Zufallsansatz und der paarweisen Ahnlichkeiten oder Entfernungen der Datenpunkte. Probleme und Schwierigkeiten auf dem Weg von der Idee zur endgultigen parameterfreien Imple- mentierung werden diskutiert und deren Losung verglichen. Der aus der Idee entwickelte Clus- tering Algorithmus, wird auf mehreren synthetischen und echten Datensatze, die verschiedene Aspekte wie die Dimensionalitat, Clusterformen und Clustergrosen abdecken, getestet. Zum Vergleich tretet der implementierte Algorithmus gegen die klassischen Clustering-Algorithmen wie k-Means, DBSCAN, Spectral Clustering und einige verwandte Graphbasierte clustering Algorithmen an. Die vielversprechenden Ergebnisse zeigen, dass der vorgestellte clustering Algorithmus in der Lage ist, relevante Cluster in verschiedenen Datensatzen zu finden. Von den Ergebnissen her ubertrifft er Graphbasierte und etablierte klassische Clustering-Algorithmen. Allerdings sind weitere Entwicklungen sind notwendig, um die Laufzeit des Algorithmus zu reduzieren und zu optimieren. Diese Arbeit zeigt, dass das Prinzip des Algorithmus funktion- iert und in der Lage ist, den SingleLink Effekt und die lokale Abhangigkeit von verschiedenen Distanzbasierten Algorithmen zu uberwinden.