X-Means: Ein Algorithmus zur Clusterbildung unter selbstständiger Abschätzung der optimalen Clusteranzahl

Studienarbeit aus dem Jahr 2006 im Fachbereich Informatik - Wirtschaftsinformatik, Note: 1,7, Friedrich-Schiller-Universität Jena (Wirtschaftswissenschaftliche Fakultät), Veranstaltung: Datenanalyse 2, Sprache: Deutsch, Abstract: X-Means: Extending K-means with Efficient Estimation of the Number of Cluster

Aufbauend auf k-means greift der x-means Algorithmus die drei hauptsächlichen Probleme von k-means auf und versucht diese zu umgehen bzw. zu beheben. Dabei wird vom Benutzer im Gegensatz zu k-means nicht die Angabe einer Klassenanzahl k gefordert, sondern lediglich ein Bereich in welchem die optimale Klassenanzahl wahrscheinlich liegen wird.

Nun werden ausgehend von der unteren Grenze des angegebenen Bereiches kontinuierlich neue Centroide hinzugefügt. Dies geschieht indem die alten ¿Vatercentroide¿ aufgespalten

werden. Aus jedem Vater werden auf diese Weise zwei ¿Söhnecentroide¿ erstellt. Ob Vater- oder Söhnecentroide beibehalten werden wird auf Grundlage einer Punktbewertung mittels BIC ermittelt. Je nachdem wessen Punktzahl höher ausfällt, werden entweder die Söhne oder

der Vater als Klassenmittelpunkte verworfen. Danach wird grundsätzlich jenes Gesamtmodell ausgegeben welches nach einem ewertungskriterium die höchste Punktzahl erreicht hat.

Der x-means Algorithmus besteht grundsätzlich aus zwei Schritten:

1. Improve Params

2. Improve Structure

Der erste Schritt entspricht einem herkömmlichen k-means Durchlauf. Der zweite Schritt ermittelt, welche Centroide gesplittet werden müssen um das Ergebnis zu verbessern. Auf dieser Basis und unter Einbeziehung eines kd-tree, welcher die Durchläufe der k-means

Iterationen erheblich beschleunigt, werden sowohl die optimale Anzahl der Cluster wie auch die Cluster als solche ausgegeben. Dadurch wird es möglich viel größere Datenmengen in viel kürzerer Zeit zu analysieren.