K-означает кластеризацию:Что случилось?(PHP)
-
19-09-2019 - |
Вопрос
Я искал способ рассчитать динамическую рыночную стоимость в игре soccer manager. Я задал этот вопрос здесь и получил очень хороший ответ от Алчеу Коста.
Я попытался закодировать этот алгоритм (90 элементов, 5 кластеров), но он работает некорректно:
- На первой итерации высокий процент элементов изменяет свой кластер.
- Начиная со второй итерации, все элементы меняют свой кластер.
- Поскольку алгоритм обычно работает до конвергенции (ни один элемент не меняет свой кластер), в моем случае он не завершается.
- Поэтому я установил окончание 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);
?>
Решение
Это так смущает : D я думаю, что вся проблема вызвана только одной буквой:
В Назначьте playerstonearestcluster() вы можете найти arsort($abstaende);.После этого функция каждый() принимает первое значение.Но это поджог таким образом, первое значение должно быть самым высоким.Таким образом, он выбирает кластер, который имеет наибольшее значение расстояния.
Так и должно быть асорт, конечно.:) Чтобы доказать это, я протестировал его с асорт - и я получаю сходимость после 7 итераций.:)
Вы думаете, это было ошибкой?Если это было так, то моя проблема решена.В таком случае:Извините, что раздражаю вас этим глупым вопросом.;)
Другие советы
Редактировать:не обращайте внимания, я по-прежнему получаю тот же результат, что и вы, все попадают в кластер 4.Я пересмотрю свой код и попробую еще раз.
Я думаю, я понял, в чем проблема, однако кластеризация k-средних предназначена для разделения различий в наборе из-за способа вычисления средних значений и т.д.мы получаем ситуацию, когда в диапазонах нет больших разрывов.
Могу ли я предложить изменение и сосредоточиться только на одном значении (сила, по-моему, имеет наибольший смысл для меня) для определения кластеров или вообще отказаться от этого метода сортировки и принять что-то другое (не то, что вы хотите услышать, я знаю)?
Я нашел довольно приятный сайт с примером сортировки по k-среднему значению с использованием целых чисел, я собираюсь попробовать отредактировать это, я вернусь с результатами завтра.
http://code.blip.pt/2009/04/06/k-means-clustering-in-php/ <-- ссылка, о которой я упомянул и забыл.