K-means clustering: ¿Qué pasa? (PHP)

Question

Yo estaba buscando una manera de calcular los valores de mercado dinámicas en un juego de manager de fútbol. hice esta pregunta aquí y conseguimos una muy buena respuesta por parte de Alceu Costa.

He intentado codificar este algoritmo (90 elementos, 5 clustes) pero no funciona correctamente:

1. En la primera iteración, un alto porcentaje de los elementos cambia su clúster.
2. En la segunda iteración, todos los elementos cambian su clúster.
3. Dado que el algoritmo funciona normalmente hasta la convergencia (sin elemento cambia de clúster), no termina en mi caso.
4. Así que me puse al final de la iteración 15a manualmente. Se puede ver que se ejecuta infinitamente.

Se puede ver la salida de mi algoritmo de aquí. ¿Qué pasa con ella? ¿Me puede decir por qué no funciona correctamente?

Espero que me puedan ayudar. Muchas gracias por adelantado!

Aquí está el código:

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

Es tan embarazoso: D Creo que todo el problema es causado por una sola letra:

assignPlayersToNearestCluster () que se puede encontrar arsort ($ abstaende); . Después de eso, la función cada () toma el primer valor. Pero es arsort lo que el primer valor debe ser el más alto. Por lo que recoge el racimo que tiene el valor más alto de la distancia.

Por lo tanto, debe ser asort , por supuesto. :) Para probar esto, he probado con asort - y consigo la convergencia después de 7 iteraciones. :)

¿Cree que fue el error? Si lo era, entonces mi problema está resuelto. En ese caso: Lo siento por usted molesto con esa pregunta estúpida. ;)

Answer 2

EDIT:. Indiferencia, sigo teniendo el mismo resultado que usted, todo el mundo termina en el grupo 4. Voy a reconsiderar mi código y vuelve a intentarlo

Creo que me he dado cuenta cuál es el problema, k-means clustering está diseñado para romper las diferencias en un conjunto, sin embargo, debido a la forma de calcular los promedios etc. que estamos obteniendo una situación donde no hay grandes lagunas en los rangos.

¿Puedo sugerir un cambio y sólo concentrarse en un único valor (fuerza parece tener más sentido para mí) para determinar los racimos, o abandonar este método de clasificación por completo, y adoptar algo diferente (no lo que quiere oír lo sé )?

He encontrado un sitio bastante agradable con un ejemplo k-media clase usando números enteros, voy a tratar de corregir eso, voy a volver con los resultados de algún tiempo mañana.

http: //code.blip. pt / 2009/04/06 / k-medias-agrupamiento-en-php / <-. enlace que he mencionado y se olvidó de