K- 평균 클러스터링 : 무엇이 잘못 되었습니까? (PHP)

https://stackoverflow.com/questions/1319232

19-09-2019
|

문제

축구 관리자 게임에서 동적 시장 가치를 계산할 수있는 방법을 찾고있었습니다. 나는 여기서이 질문을했고 Alceu Costa로부터 아주 좋은 답변을 얻었습니다.

이 알고리즘 (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);
?>

해결책

너무 당황 스럽습니다. DI 전체 문제는 단 하나의 글자로 인해 발생한다고 생각합니다.

~ 안에 AssidplayerstonearestCluster () 당신은 찾을 수 있습니다 Arsort ($ Abstaende);. 그 후, 기능 각() 첫 번째 값을 취합니다. 그러나 그것은입니다 아르 소트 따라서 첫 번째 값은 가장 높아야합니다. 따라서 거리 값이 가장 높은 클러스터를 선택합니다.

그래서해야합니다 Asort, 물론이야. :) 그것을 증명하기 위해, 나는 그것을 테스트했다 Asort - 7 번의 반복 후에 수렴됩니다. :)

그것이 실수라고 생각하십니까? 만약 그렇다면, 내 문제가 해결됩니다. 이 경우 : 그 멍청한 질문으로 당신을 괴롭히서 죄송합니다. ;)

다른 팁

편집 : 무시, 나는 여전히 당신과 같은 결과를 얻습니다. 모두가 클러스터 4에 감습니다. 나는 내 코드를 재고하고 다시 시도해야합니다.

나는 문제가 무엇인지 깨달았다 고 생각합니다. K- 평균 클러스터링은 평균을 계산하는 방식으로 인해 세트의 차이를 분해하도록 설계되었다고 생각합니다. 우리는 범위에 큰 차이가없는 상황을 얻고 있습니다. .

클러스터를 결정하거나 이런 분류 방법을 완전히 포기하고 다른 것을 채택하기 위해 단일 값 (강도가 가장 의미가있는 것으로 보입니다)에만 변화를 제안하고 (강도가 가장 의미가있는 것처럼 보일 수 있습니까?

나는 정수를 사용하여 K-Mean 정렬의 예제가있는 다소 멋진 사이트를 찾았습니다. 나는 내일에 언젠가 결과를 다시 얻을 것입니다.

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

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 StackOverflow