K-means 클러스터링 : 무엇이 잘못 되었나요? (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으로 테스트했습니다. 7 회 반복 한 후에 컨버전스를 얻습니다. :)

실수라고 생각합니까? 그렇다면 내 문제가 해결됩니다. 그 경우에 : 그 어리석은 질문으로 너를 성가 시게해서 미안해. ;)

Answer 2

편집 : 당신은 모든 사람이 내 코드를 다시 생각하고 다시 시도해야 클러스터 4에 바람이 같이 무시, 난 여전히 같은 결과를 얻을.

저는 k- 평균 클러스터링이 집합의 차이를 없애기 위해 설계되었지만 평균 등을 계산하는 방식으로 인해 문제가 무엇인지 깨달았을 것으로 생각합니다. 범위의 갭.

클러스터를 결정하기 위해 변경 사항을 제안하고 단일 값에만 집중할 수 있습니다 (강도가 나에게 가장 잘 들리는 것처럼 보임). 또는이 정렬 방법을 모두 포기하고 다른 것을 채택 할 수 있습니다. 알고있다)?

정수를 사용하는 k- 평균 정렬을 사용하는 좋은 사이트를 발견했습니다.이를 시도하고 편집하려고합니다. 내일은 결과가 돌아올 것입니다.

http://code.blip.pt/2009/04/06/k-means-clustering-in-php/ < - 링크 내가 언급하고 잊어 버렸습니다.