title: K-means clustering: What's wrong? (PHP)
body: <p>I was looking for a way to calculate dynamic market values in a soccer manager game. <a href="https://stackoverflow.com/questions/1278128/manager-game-calculate-market-prices">I asked this question here and got a very good answer from Alceu Costa.</a></p>
  
  <p>I tried to code this algorithm (90 elements, 5 clustes) but it doesn't work correctly:</p>
  
  <ol>
  <li>In the first iteration, a high percentage of the elements changes its cluster.</li>
  <li>From the second iteration, all elements change their cluster.</li>
  <li>Since the algorithm normally works until convergence (no element changes its cluster), it doesn't finish in my case.</li>
  <li>So I set the end to the 15th iteration manually. You can see that it runs infinitely.</li>
  </ol>
  
  <p><a href="http://www.ballmanager.de/aa_marktwert_cluster.php" rel="nofollow noreferrer">You can see the output of my algorithm here.</a> What's wrong with it? Can you tell me why it doesn't work correctly?</p>
  
  <p>I hope you can help me. Thank you very much in advance!</p>
  
  <p>Here's the code:</p>
  
  <pre><code>&lt;?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=&gt;$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'=&gt;array_sum($strenthValues)/count($strenthValues), 'maxStrength'=&gt;array_sum($maxStrenthValues)/count($maxStrenthValues), 'motivation'=&gt;array_sum($motivationValues)/count($motivationValues), 'age'=&gt;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=&gt;$clusterValues) {
          // FOR EVERY SINGLE PLAYER START
          foreach ($clusterValues as $player) {
              // MEASURE DISTANCE TO ALL CENTROIDS START
              $abstaende = array();
              foreach ($clusterCentroids as $CentroidId=&gt;$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 &lt; $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'=&gt;$sql3['staerke'], 'maxStrength'=&gt;$sql3['talent'], 'motivation'=&gt;$sql3['trainingseifer'], 'age'=&gt;$sql3['wiealt'], 'id'=&gt;$sql3['ids']);
      if ($sql3['staerke'] &gt; $strengthMax) { $strengthMax = $sql3['staerke']; }
      if ($sql3['talent'] &gt; $maxStrengthMax) { $maxStrengthMax = $sql3['talent']; }
      if ($sql3['trainingseifer'] &gt; $motivationMax) { $motivationMax = $sql3['trainingseifer']; }
      if ($sql3['wiealt'] &gt; $ageMax) { $ageMax = $sql3['wiealt']; }
      $counter++;
  }
  // PUT PLAYERS IN RANDOM CLUSTERS END
  $m = 1;
  while ($m &lt; 16) {
      $clusterCentroids = calculateCentroids(); // calculate new centroids of the clusters
      $playersWhoChangedClusters = assignPlayersToNearestCluster(); // assign each player to the nearest cluster
      if ($playersWhoChangedClusters == 0) { $m = 1001; }
      echo '&lt;li&gt;Iteration '.$m.': '.$playersWhoChangedClusters.' players have changed place&lt;/li&gt;';
      $m++;
  }
  print_r($cluster);
  ?&gt;
  </code></pre>