regroupement K-means: Qu'est-ce qui ne va pas? (PHP)

Question

Je cherchais un moyen de calculer les valeurs de marché dynamique dans un jeu de gestion de football. J'ai posé cette question ici et nous avons eu une très bonne réponse de Alceu Costa.

J'ai essayé de coder cet algorithme (90 éléments, 5 clustes), mais il ne fonctionne pas correctement:

1. Dans la première itération, un pourcentage élevé des éléments change de cluster.
2. A partir de la deuxième itération, tous les éléments changent cluster.
3. Puisque l'algorithme fonctionne normalement jusqu'à convergence (aucun élément change de cluster), il ne se termine pas dans mon cas.
4. Je me suis donc la fin de la 15e itération manuellement. Vous pouvez voir qu'il fonctionne à l'infini.

Vous pouvez voir la sortie de mon algorithme ici. Quel est le problème avec elle? Pouvez-vous me dire pourquoi il ne fonctionne pas correctement?

J'espère que vous pouvez me aider. Merci beaucoup à l'avance!

Voici le code:

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

Il est tellement embarassant: D Je pense que le problème est causé par une seule lettre:

assignPlayersToNearestCluster () vous pouvez trouver arsort ($ abstaende); . Après cela, la fonction each () prend la première valeur. Mais il est arsort pour la première valeur doit être le plus élevé. Donc, il choisit le groupe qui a la valeur la plus élevée à distance.

Il doit donc être asort , bien sûr. :) Pour prouver que, je l'ai testé avec asort - et je reçois la convergence après 7 itérations. :)

Pensez-vous que l'erreur était? Si c'était, mon problème est résolu. Dans ce cas: Désolé pour vous ennuyer avec cette question stupide. ;)

Answer 2

EDIT:. Mépris, je reçois toujours le même résultat que vous, tous les vents en groupe 4. Je vais revoir mon code et essayer à nouveau

Je pense que je me suis rendu compte que le problème est, k-means est conçu pour briser les différences dans un ensemble, cependant, en raison de la façon dont on calcule les moyennes, etc., nous obtenons une situation où il n'y a pas de grandes lacunes dans les fourchettes.

Puis-je suggérer un changement et se concentrer uniquement sur une seule valeur (la force semble faire le plus de sens pour moi) pour déterminer les groupes, ou abandonner cette méthode de tri tout à fait, et d'adopter quelque chose de différent (pas ce que vous voulez entendre, je sais )?

J'ai trouvé un site plutôt agréable avec un exemple k-moyenne trier par des entiers, je vais essayer de modifier, je vais revenir avec les résultats certains temps demain.

http: //code.blip. pt / 2009/04/06 / k-means-clusters en php / <-. lien et je l'ai mentionné oublié