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

Question

Я искал способ рассчитать динамическую рыночную стоимость в игре soccer manager. Я задал этот вопрос здесь и получил очень хороший ответ от Алчеу Коста.

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

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

Вы можете увидеть результат моего алгоритма здесь. Что в этом плохого?Можете ли вы сказать мне, почему это работает некорректно?

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

Вот код:

<?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 я думаю, что вся проблема вызвана только одной буквой:

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

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

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

Answer 2

Редактировать:не обращайте внимания, я по-прежнему получаю тот же результат, что и вы, все попадают в кластер 4.Я пересмотрю свой код и попробую еще раз.

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

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

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

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