K-Means Clustering: Was ist los? (PHP)

Question

Ich war auf der Suche nach einer Möglichkeit, dynamische Marktwerte in einem Fußball-Manager Spiel zu berechnen. ich diese Frage hier gefragt und bekam eine sehr gute Antwort von Alceu Costa.

ich Code versucht, diesen Algorithmus (90 Elemente, 5 clustes), aber es funktioniert nicht richtig:

1. In der ersten Iteration ein hoher Prozentsatz des Elements ändert seinen Cluster.
2. Von der zweiten Iteration werden alle Elemente ändern ihre Cluster.
3. Da normalerweise der Algorithmus bis zur Konvergenz funktioniert (kein Element ändert seine Cluster), ist es nicht in meinem Fall nicht beenden.
4. gesetzt Also ich das Ende der 15. Iteration manuell. Sie können sehen, dass es läuft unendlich.

Sie können die Ausgabe meines Algorithmus hier sehen. Was ist falsch daran? Können Sie mir sagen, warum es nicht richtig funktioniert?

Ich hoffe, dass Sie mir helfen können. Vielen Dank im Voraus!

Hier ist der Code:

<?php
include 'zzserver.php';
function distance($player1, $player2) {
    global $strengthMax, $maxStrengthMax, $motivationMax, $ageMax;
    // $playerX = array(strength, maxStrength, motivation, age, id);
    $distance = 0;
    $distance += abs($player1['strength']-$player2['strength'])/$strengthMax;
    $distance += abs($player1['maxStrength']-$player2['maxStrength'])/$maxStrengthMax;
    $distance += abs($player1['motivation']-$player2['motivation'])/$motivationMax;
    $distance += abs($player1['age']-$player2['age'])/$ageMax;
    return $distance;
}
function calculateCentroids() {
    global $cluster;
    $clusterCentroids = array();
    foreach ($cluster as $key=>$value) {
        $strenthValues = array();
        $maxStrenthValues = array();
        $motivationValues = array();
        $ageValues = array();
        foreach ($value as $clusterEntries) {
            $strenthValues[] = $clusterEntries['strength'];
            $maxStrenthValues[] = $clusterEntries['maxStrength'];
            $motivationValues[] = $clusterEntries['motivation'];
            $ageValues[] = $clusterEntries['age'];
        }
        if (count($strenthValues) == 0) { $strenthValues[] = 0; }
        if (count($maxStrenthValues) == 0) { $maxStrenthValues[] = 0; }
        if (count($motivationValues) == 0) { $motivationValues[] = 0; }
        if (count($ageValues) == 0) { $ageValues[] = 0; }
        $clusterCentroids[$key] = array('strength'=>array_sum($strenthValues)/count($strenthValues), 'maxStrength'=>array_sum($maxStrenthValues)/count($maxStrenthValues), 'motivation'=>array_sum($motivationValues)/count($motivationValues), 'age'=>array_sum($ageValues)/count($ageValues));
    }
    return $clusterCentroids;
}
function assignPlayersToNearestCluster() {
    global $cluster, $clusterCentroids;
    $playersWhoChangedClusters = 0;
    // BUILD NEW CLUSTER ARRAY WHICH ALL PLAYERS GO IN THEN START
    $alte_cluster = array_keys($cluster);
    $neuesClusterArray = array();
    foreach ($alte_cluster as $alte_cluster_entry) {
        $neuesClusterArray[$alte_cluster_entry] = array();
    }
    // BUILD NEW CLUSTER ARRAY WHICH ALL PLAYERS GO IN THEN END
    foreach ($cluster as $oldCluster=>$clusterValues) {
        // FOR EVERY SINGLE PLAYER START
        foreach ($clusterValues as $player) {
            // MEASURE DISTANCE TO ALL CENTROIDS START
            $abstaende = array();
            foreach ($clusterCentroids as $CentroidId=>$centroidValues) {
                $distancePlayerCluster = distance($player, $centroidValues);
                $abstaende[$CentroidId] = $distancePlayerCluster;
            }
            arsort($abstaende);
            if ($neuesCluster = each($abstaende)) {
                $neuesClusterArray[$neuesCluster['key']][] = $player; // add to new array
                // player $player['id'] goes to cluster $neuesCluster['key'] since it is the nearest one
                if ($neuesCluster['key'] != $oldCluster) {
                    $playersWhoChangedClusters++;
                }
            }
            // MEASURE DISTANCE TO ALL CENTROIDS END
        }
        // FOR EVERY SINGLE PLAYER END
    }
    $cluster = $neuesClusterArray;
    return $playersWhoChangedClusters;
}
// CREATE k CLUSTERS START
$k = 5; // Anzahl Cluster
$cluster = array();
for ($i = 0; $i < $k; $i++) {
    $cluster[$i] = array();
}
// CREATE k CLUSTERS END
// PUT PLAYERS IN RANDOM CLUSTERS START
$sql1 = "SELECT ids, staerke, talent, trainingseifer, wiealt FROM ".$prefix."spieler LIMIT 0, 90";
$sql2 = mysql_abfrage($sql1);
$anzahlSpieler = mysql_num_rows($sql2);
$anzahlSpielerProCluster = $anzahlSpieler/$k;
$strengthMax = 0;
$maxStrengthMax = 0;
$motivationMax = 0;
$ageMax = 0;
$counter = 0; // for $anzahlSpielerProCluster so that all clusters get the same number of players
while ($sql3 = mysql_fetch_assoc($sql2)) {
    $assignedCluster = floor($counter/$anzahlSpielerProCluster);
    $cluster[$assignedCluster][] = array('strength'=>$sql3['staerke'], 'maxStrength'=>$sql3['talent'], 'motivation'=>$sql3['trainingseifer'], 'age'=>$sql3['wiealt'], 'id'=>$sql3['ids']);
    if ($sql3['staerke'] > $strengthMax) { $strengthMax = $sql3['staerke']; }
    if ($sql3['talent'] > $maxStrengthMax) { $maxStrengthMax = $sql3['talent']; }
    if ($sql3['trainingseifer'] > $motivationMax) { $motivationMax = $sql3['trainingseifer']; }
    if ($sql3['wiealt'] > $ageMax) { $ageMax = $sql3['wiealt']; }
    $counter++;
}
// PUT PLAYERS IN RANDOM CLUSTERS END
$m = 1;
while ($m < 16) {
    $clusterCentroids = calculateCentroids(); // calculate new centroids of the clusters
    $playersWhoChangedClusters = assignPlayersToNearestCluster(); // assign each player to the nearest cluster
    if ($playersWhoChangedClusters == 0) { $m = 1001; }
    echo '<li>Iteration '.$m.': '.$playersWhoChangedClusters.' players have changed place</li>';
    $m++;
}
print_r($cluster);
?>

Answer 1

Es ist so peinlich: D Ich denke, das ganze Problem nur durch einen Brief verursacht wird:

In assignPlayersToNearestCluster () finden Sie arsort ($ abstaende); . Danach wird die Funktion each () nimmt den ersten Wert. Aber es ist arsort , so der erste Wert am höchsten sein muß. So nimmt es den Cluster, die den höchsten Entfernungswert hat.

So sollte es sein asort , natürlich. :) Um das zu beweisen, ich habe es getestet mit asort - und ich Konvergenz nach 7 Wiederholungen. :)

Denken Sie, dass der Fehler war? Wenn ja, dann ist mein Problem gelöst. In diesem Fall: Es tut sie ärgerlich Sie mit dieser dummen Frage. ;)

Answer 2

EDIT:. Mißachtung, habe ich noch das gleiche Ergebnis wie Sie bekommen, jeder windet sich in Cluster 4. Ich werde meinen Code überdenken und versuchen Sie es erneut

Ich glaube, ich realisiert habe, was das Problem ist, k-means Clustering ausgelegt ist, Unterschiede in einem Satz zu brechen, aber wegen der Art und Weise Sie mittelt berechnen usw. wir eine Situation bekommen, wo es keine großen Lücken in den Bereichen.

Might ich eine Veränderung und nur konzentrieren sich auf einen einzigen Wert vorschlagen (Stärke erscheint am meisten Sinn für mich zu machen), um die Cluster zu bestimmen, oder verlassen Sie diese Sortiermethode zusammen, und etwas anderes annehmen (nicht das, was Sie hören wollen, ich weiß, )?

fand ich eine ziemlich schöne Seite mit ein Beispiel k-mean Art ganze Zahlen mit, ich werde versuchen, und zu bearbeiten, dass ich mit den Ergebnissen einiger Zeit morgen zurück.

http: //code.blip. pt / 2009/04/06 / k-Mittel-Clustering-in-php / . <- Link, den ich erwähnt und vergessen