K-means clustering: qu'est-ce qui ne va pas? (PHP)

Question

Je cherchais un moyen de calculer des valeurs de marché dynamiques dans un jeu de gestion de football. I asked this question here and got a very good answer from Alceu Costa.

J'ai essayé de coder cet algorithme (90 éléments, 5 clustes), mais il ne fonctionne pas correctement:

1. Dans la première itération, un pourcentage élevé des éléments change de cluster. Depuis la deuxième itération, tous les éléments changent de cluster.
2. Puisque l'algorithme fonctionne normalement jusqu'à la convergence (aucun élément ne change son cluster), il ne se termine pas dans mon cas.
3. Donc, je mets fin à la 15ème itération manuellement. Vous pouvez voir qu'il fonctionne infiniment.

You can see the output of my algorithm here. Qu'est-ce qui ne va pas? Pouvez-vous me dire pourquoi cela ne fonctionne pas correctement?

J'espère que vous pouvez m'aider. Merci beaucoup d'avance!

Voici le 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

Il est tellement embarassant: D Je pense que le problème est causé par une seule lettre:

En assignPlayersToNearestCluster() vous pouvez trouver arsort ($ abstaende);. Après cela, la fonction chaque() prend la première valeur. Mais c'est arsort donc la première valeur doit être la plus élevée. Il choisit donc le cluster qui a la plus grande valeur de distance.

Il devrait donc être asort, bien sûr. :) Pour le prouver, je l'ai testé avec asort - et j'obtiens la convergence après 7 itérations. :)

Pensez-vous que c'était l'erreur? Si c'était le cas, alors mon problème est résolu. Dans ce cas: Désolé de t'avoir ennuyé avec cette question stupide. ;)

Answer 2

EDIT: mépris, je reçois toujours le même résultat que vous, tous vents en groupe 4. Je vais revoir mon code et essayer à nouveau.

Je pense que j'ai réalisé quel est le problème, mais le clustering k-means est conçu pour casser les différences d'un ensemble, cependant, à cause de la façon dont vous calculez les moyennes, etc. Nous obtenons une situation où il n'y a pas de grandes lacunes dans les gammes. Je pourrais suggérer un changement et ne me concentrer que sur une seule valeur (la force semble avoir plus de sens pour moi) pour déterminer les groupes, ou abandonner complètement cette méthode de tri, et adopter quelque chose de différent (pas ce que vous voulez entendre). connaître)?

J'ai trouvé un site plutôt sympa avec un exemple de tri k-mean utilisant des entiers, je vais essayer de l'éditer, je reviendrai avec les résultats demain.

http://code.blip.pt/2009/04/06/k-means-clustering-in-php/ < - lien J'ai mentionné et oublié.