K-means clustering di: Cosa c'è che non va? (PHP)

Question

Ero alla ricerca di un modo per calcolare i valori di mercato dinamici in un gioco manageriale di calcio. Ho fatto questa domanda qui e ho ottenuto una risposta molto buona da Alceu Costa.

Ho cercato di codificare questo algoritmo (90 elementi, 5 clustes), ma non funziona correttamente:

1. Nella prima iterazione, un'alta percentuale degli elementi cambia cluster.
2. Dalla seconda iterazione, tutti elementi che modificano il loro cluster.
3. Poiché l'algoritmo funziona normalmente fino a quando la convergenza (nessun elemento cambia il suo gruppo), non finisce nel mio caso.
4. Quindi ho impostato manualmente la fine al 15 iterazione. Si può vedere che corre all'infinito.

Si può vedere l'uscita del mio algoritmo qui. Cosa c'è che non va? Puoi dirmi il motivo per cui non funziona correttamente?

Spero che mi può aiutare. Grazie mille in anticipo!

Ecco il codice:

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

E 'così imbarazzante: D Penso che tutto il problema è causato da una sola lettera:

assignPlayersToNearestCluster () è possibile trovare arsort ($ abstaende); . Dopo di che, la funzione ogni () assume il primo valore. Ma è arsort in modo che il primo valore deve essere il più alto. Così prende il cluster, che ha il più alto valore di distanza.

Quindi dovrebbe essere asort , naturalmente. :) Per dimostrare che, ho provato con asort - e ottengo la convergenza dopo 7 iterazioni. :)

Pensi che è stato l'errore? Se fosse, allora il mio problema è risolto. In tal caso: Ci scusiamo per fastidioso con quella stupida domanda. ;)

Answer 2

EDIT:. Disprezzo, ho ancora ottenere lo stesso risultato di voi, tutti finisce in gruppo 4. I riesamina il mio codice e riprova

Credo di aver capito qual è il problema, k-means è stato progettato per rompere le differenze in un set, però, a causa del modo di calcolare le medie, ecc stiamo ottenendo una situazione in cui non ci sono grandi lacune nelle gamme.

Posso suggerire un cambiamento e concentrarsi solo su un singolo valore (forza sembra rendere più senso per me) per determinare i cluster, o abbandonare questo metodo di ordinamento del tutto, e adottare qualcosa di diverso (non quello che si desidera ascoltare lo so )?

Ho trovato un bel sito, piuttosto con un esempio k-mean ordinamento mediante numeri interi, ho intenzione di provare a modificare questo, mi metterò di nuovo con i risultati un po 'di tempo domani.

http: //code.blip. pt / 2009/04/06 / k-means clustering-in-php / <-. link che ho già detto e dimenticato