- Mitglied seit
- 06.12.2000
- Beiträge
- 5.486
- Reaktionen
- 0
Folgendes Problem...
Ich habe diese Tabelle:
In den Spalten stehen verschiedene Cluster-Algorithmen, in den Zeilen unterschiedliche Beobachtungen, die mit den Algorithmen geclustert wurden. Die Zellen zeigen, in welches Cluster der jeweilige Algorithmus die Beobachtung gesteckt hat.
Als Kriterium soll die Summe der quadrierten Anzahl der Abweichungen vom häufigsten Wert minimiert werden. Mathematisch dieser Term:
sum{i=1}{n} (N-M_i)²
mit n = Anzahl der Beobachtungen, N = Anzahl der Algorithmen, M_i = Anzahl wie oft der häufigste (Cluster-)Wert für diese Beobachtung vorkommt
Beispiel:
Ich habe Cluster 1 bei allen 3 Algorithmen => Abweichungen = 0, Kriterium = 0
Ich habe (wie bei Beobachtung 1) 2 mal Cluster 1, einmal Cluster 2 => Abweichungen = 1, Kriterium = 1
Das Problem ist, dass der Clustername eigentlich keine Bedeutung hat. Cluster 2 im Algorithmus 3 kann also auch das gleiche Cluster sein wie Cluster 1 im Algorithmus 1. Innerhalb eines Algorithmus lassen sich also die Clusternamen (hier im Beispiel 1, 2 und 3 bzw. rot, blau und grün) beliebig rotieren, um das Kriterium zu minimieren.
In der Tabelle könnte das zum Beispiel so aussehen:
Hier wurden bei Algorithmus 2 Cluster 2 und 3 gedreht und im Algorithmus 3 wurde 2 zu 1, 3 zu 2 und 1 zu 3. Damit hat sich das Kriterium (unten rechts) von 7 auf 3 verringert.
Allerdings habe ich dieses sehr einfache und konstruierte Beispiel einfach „per Hand“ bearbeitet/minimiert. Für meine Analysen habe ich aber evtl bis zu 10 Algorithmen und evtl 10-12 Cluster – und natürlich deutlich mehr Beobachtungen (bis zu 100 evtl). Anfangs hab ich ja noch gedacht, ich könnte einfach die Clusternamen durchpermutieren (sukzessive für alle Algorithmen), jeweils das Kriterium berechnen und dann die Lösung mit dem geringsten Kriteriumsmaß nehmen. Quasi der brute force Ansatz. Leider wären dass dann bei 12 Clustern und 10 Algorithmen sehr sehr viele Berechnungen. Irgendwas in die Richtung 12!^9 oder so (Kombinatorik war noch nie meine Stärke). Damit wären wir bei 10^78 Berechnungen, was logischerweise recht schlecht durchführbar ist.
Was ich also brauche, ist ein besserer Algorithmus als „alles durchprobieren“. Da dieses Problem mir nicht allzu außergewöhnlich erscheint, kann ich mir gut vorstellen, dass es irgendwelche Algorithmen in diese Richtung schon gibt. Leider habe ich super wenig Ahnung in dem Feld. Falls hier jemand ein paar gute Ideen hat oder mir ein paar Stichworte für entsprechende Algorithmen liefern kann, damit ich da mal nachlesen kann, ob das für mich passt und umsetzbar ist, wäre das top! Selbst, wenn es erstmal nur die Anzahl der Abweichungen (nicht die der quadrierten Abweichungen) minimiert, könnte ich vorerst gut damit leben.
Thx schonmal
BBW
Ich habe diese Tabelle:
In den Spalten stehen verschiedene Cluster-Algorithmen, in den Zeilen unterschiedliche Beobachtungen, die mit den Algorithmen geclustert wurden. Die Zellen zeigen, in welches Cluster der jeweilige Algorithmus die Beobachtung gesteckt hat.
Als Kriterium soll die Summe der quadrierten Anzahl der Abweichungen vom häufigsten Wert minimiert werden. Mathematisch dieser Term:
sum{i=1}{n} (N-M_i)²
mit n = Anzahl der Beobachtungen, N = Anzahl der Algorithmen, M_i = Anzahl wie oft der häufigste (Cluster-)Wert für diese Beobachtung vorkommt
Beispiel:
Ich habe Cluster 1 bei allen 3 Algorithmen => Abweichungen = 0, Kriterium = 0
Ich habe (wie bei Beobachtung 1) 2 mal Cluster 1, einmal Cluster 2 => Abweichungen = 1, Kriterium = 1
Das Problem ist, dass der Clustername eigentlich keine Bedeutung hat. Cluster 2 im Algorithmus 3 kann also auch das gleiche Cluster sein wie Cluster 1 im Algorithmus 1. Innerhalb eines Algorithmus lassen sich also die Clusternamen (hier im Beispiel 1, 2 und 3 bzw. rot, blau und grün) beliebig rotieren, um das Kriterium zu minimieren.
In der Tabelle könnte das zum Beispiel so aussehen:
Hier wurden bei Algorithmus 2 Cluster 2 und 3 gedreht und im Algorithmus 3 wurde 2 zu 1, 3 zu 2 und 1 zu 3. Damit hat sich das Kriterium (unten rechts) von 7 auf 3 verringert.
Allerdings habe ich dieses sehr einfache und konstruierte Beispiel einfach „per Hand“ bearbeitet/minimiert. Für meine Analysen habe ich aber evtl bis zu 10 Algorithmen und evtl 10-12 Cluster – und natürlich deutlich mehr Beobachtungen (bis zu 100 evtl). Anfangs hab ich ja noch gedacht, ich könnte einfach die Clusternamen durchpermutieren (sukzessive für alle Algorithmen), jeweils das Kriterium berechnen und dann die Lösung mit dem geringsten Kriteriumsmaß nehmen. Quasi der brute force Ansatz. Leider wären dass dann bei 12 Clustern und 10 Algorithmen sehr sehr viele Berechnungen. Irgendwas in die Richtung 12!^9 oder so (Kombinatorik war noch nie meine Stärke). Damit wären wir bei 10^78 Berechnungen, was logischerweise recht schlecht durchführbar ist.
Was ich also brauche, ist ein besserer Algorithmus als „alles durchprobieren“. Da dieses Problem mir nicht allzu außergewöhnlich erscheint, kann ich mir gut vorstellen, dass es irgendwelche Algorithmen in diese Richtung schon gibt. Leider habe ich super wenig Ahnung in dem Feld. Falls hier jemand ein paar gute Ideen hat oder mir ein paar Stichworte für entsprechende Algorithmen liefern kann, damit ich da mal nachlesen kann, ob das für mich passt und umsetzbar ist, wäre das top! Selbst, wenn es erstmal nur die Anzahl der Abweichungen (nicht die der quadrierten Abweichungen) minimiert, könnte ich vorerst gut damit leben.
Thx schonmal
BBW
