X-Means

Studienarbeit aus dem Jahr 2006 im Fachbereich Informatik - Wirtschaftsinformatik Note: 17 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 ClusterAufbauend 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 aufgespaltenwerden. 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 oderder 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 Params2. Improve StructureDer 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-meansIterationen 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.