Footnote:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Description:
Die Clusteranalyse ist ein mächtiges Werkzeug um Gruppen von Datenpunkten mit ähnlichen Eigenschaften zu identifizieren. Verschiedene Algorithmen finden diese Gruppen indem sie das k-means Optimierungsproblem lösen. Da die Lösung dieses Problems NP-schwer ist, wurden Heuristiken entwickelt um die Optimierung zu beschleunigen. Eine dieser Heuristiken wurde von Lloyd vorgestellt und hat sich zum Standard k-means Algorithmus entwickelt. Über den Zeitraum von mehreren Dekaden wurden in Forschungsarbeiten zahlreiche Lloyd Varianten vorgestellt mit dem Ziel den originalen Algorithmus zu beschleunigen. Fast alle dieser Arbeiten hatten gemeinsam, dass eine Beschleunigung auf nahezu allen getesteten Datensätzen erreicht werden sollte. Es wird ein Rahmenwerk präsentiert um k-means Varianten zu erzeugen welche lediglich auf Datensätzen mit einer spezifischen Datenrepräsentation effektiv sind. Mit detailliertem Wissen über die Struktur eines Datensatzes ist es somit möglich die schnellste Variante passend zu dem Datensatz auszuwählen. Um die Varianten zu erzeugen werden Lower Bound Feature Maps vorgestellt welche verschiedene Datenrepräsentationen ausnutzen können um Distanzen zu approximieren. Die Approximationen benötigen zur Berechnung nur einen Bruchteil der Zeit einer vollständigen Distanzberechnung and eignen sich daher zur Beschleunigung des k-means Algorithmus. Anhand einer sehr diversen Auswahl von Datensätzen unterschiedlicher Datentypen (Video, Text, ausführbare Dateien) und Spärlichkeit wird gezeigt, dass Varianten mit aktivierter Feature Map Optimierung signifikant schneller sind als nicht optimierte Varianten. Weitergehende Untersuchungen haben gezeigt, dass die Lower-Bounds effektiver werden je höher k gewählt wird. Dies führte zu der Entwicklung von hoch optimieren sehr schnellen Varianten, welche für große k einen Speicherverbrauch ähnlich zu Lloyd’s Algorithmus aufweisen. ; Cluster analysis is a powerful tool to identify groups of data points with similar properties. Various algorithms find these groups by ...