K-означает кластеризацию: что случилось? (PHP)

Question

Я искал способ рассчитать динамические рыночные ценности в игре футбольного менеджера. I asked this question here and got a very good answer from Alceu Costa.

Я пытался кодировать этот алгоритм (90 элементов, 5 clustes), но он не работает правильно:

1. В первой итерации, высокий процент элементов изменяет свой кластер.
2. Со второй итерации все элементы меняют свой кластер.
3. Поскольку алгоритм обычно работает до конвергенции (ни один элемент не меняет свой кластер), он не заканчивается в моем случае.
4. Итак, я установил конец для 15-й итерации вручную. Вы можете видеть, что он работает бесконечно.

You can see the output of my algorithm here. Что в этом плохого? Можете ли вы сказать мне, почему это работает неправильно?

Надеюсь, вы можете мне помочь. Заранее большое спасибо!

Вот код:

<?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

Это так смущают: D Я думаю, что вся проблема вызвана лишь одной буквой:

В assignPlayersToNearestCluster() вы можете найти arsort ($ abstaende);. После этого функция each() принимает первое значение. Но это arsort, поэтому первое значение должно быть самым высоким. Поэтому он выбирает кластер с наивысшим значением расстояния.

Таким образом, это должно быть asort, конечно. :) Чтобы доказать это, я проверил его с asort - и я получаю конвергенцию после 7 итераций. :)

Считаете ли вы, что это была ошибка? Если бы это было так, то моя проблема решена. В таком случае: Извините за раздражение вас этим глупым вопросом. ;)

Answer 2

EDIT: невнимание, я до сих пор получить тот же результат, как вы, все ветры в группе 4. Я должен пересмотреть свой код и повторите попытку.

Я думаю, что я понял, в чем проблема, k-означает, что кластеризация предназначена для разбиения разностей в наборе, однако, из-за того, как вы вычисляете средние значения и т. Д., Мы получаем ситуацию, когда нет больших пробелы в диапазонах.

Могу ли я предложить изменение и сосредоточиться только на одном значении (сила, по-видимому, имеет для меня смысл), чтобы определить кластеры или вообще отказаться от этого метода сортировки и принять что-то другое (не то, что вы хотите услышать? знаю)?

Я нашел довольно хороший сайт с примером k-mean sort, используя целые числа, я попытаюсь отредактировать это, я вернусь с результатами некоторое время завтра.

http://code.blip.pt/2009/04/06/k-means-clustering-in-php/ < - ссылка Я упомянул и забыл о.