K 平均クラスタリング:どうしたの？(PHP)

StackOverflow https://stackoverflow.com/questions/1319232

質問

私はサッカーの監督ゲームにおける動的な市場価値を計算する方法を探していました。 ここでこの質問をしたところ、アルセウ・コスタから非常に良い答えが得られました。

このアルゴリズム (90 要素、5 クラスター) をコード化しようとしましたが、正しく動作しません。

  1. 最初の反復では、高い割合の要素がそのクラスターを変更します。
  2. 2 回目の反復以降、すべての要素のクラスターが変更されます。
  3. このアルゴリズムは通常、収束するまで機能するため (どの要素もそのクラスターを変更しない)、私の場合は終了しません。
  4. そこで、終了を手動で 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);
?>
役に立ちましたか？

解決

それはとても恥ずかしいです：D私は、問題全体が一つだけ文字によって引き起こされていると思います：

の、

のassignPlayersToNearestCluster（）のでは、のarsortを（$ abstaende）を見つけることができます。その後、関数のそれぞれは（）は最初の値をとります。しかし、それはそう最初の値が最高でなければなりません。のarsort のです。だから、最高の距離値を持つクラスタを選びます。

それはもちろん、のASORT のでなければなりませんので。 :)それを証明するために、私はのASORT のでそれをテストしてみた - と私は7回の反復後に収束を得ます。 ：）

あなたはそれが間違いだったと思いますか？それがあった場合は、その後、私の問題は解決されます。その場合：その愚かな質問で、あなたは迷惑なのために申し訳ありません。 ;）

他のヒント

EDIT：無視、私はまだあなたと同じ結果を得る、誰もが私は私のコードを再考し、もう一度試してならないクラスタ4に巻き取る。

。

私は道のあなたは何の大きなギャップが存在しない、我々は状況を取得している平均値などを計算するので、しかし、セットの違いを分割するように設計されてk平均クラスタリング、私は問題が何であるかを実現したと思います範囲でます。

私はあなたが私が知っている聞いて欲しいもの（クラスタを決定し、または完全にこのソート方法を放棄し、別の何かを採用する（強さは私にはほとんど意味をなすように見えます）ではない変更を提案し、単一の値のみに集中可能性があります）？

は、私はいくつかの時間の明日の結果で戻ってきます、並べ替え、私は試してみて、それを編集するつもりだ、整数を使用した例K-平均ではなく、素敵なサイトを見つけます。

ます。http：//code.blip。 PT / 2009/04/06 / k平均クラスタリング・イン・PHP / の< - 。私が述べたと忘れリンク

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top