비계층 클러스터 분석의 k-means법을 PHP로 만들어 보았다

비계층 클러스터 분석에서 대표적인 기법인 k-means법은 파이썬 라이브러리에 존재하거나 통계 소프트웨어에 표준 기능으로 탑재되어 있는 경우가 많고 익숙한 기법인 것 같지만 실제 알고리즘 확인하기 위해 (익숙한) PHP로 만들어 보았습니다.

k-means법의 알고리즘의 이해는, 여기 를 알기 쉽습니다.

소스는 다음과 같습니다.

점을 2차원 평면에 점재하여 해당 클러스터로 나눕니다.
완전히 무작위로 배치하면 클러스터링의 초기 값 의존성이 높아지기 때문에 굳이 여러 장소에 집중하여 배치하도록 했습니다.

<?php

$max = 500; //領域の大きさ
$margin = 50; //ランダムの配置するときの中心からの範囲
$dot_num_per_center = 30; //１中心点に配置するときの点の数
$center_num = 4; //中心点の数
$action_num = 5; //k-means実行回数

//点の配置
print "①この下の表が配置した点です。";
$dots = array();
print "<table>";
for ($i = 1; $i <= $center_num; $i++) {
    //中心点の位置をランダムに決める
    $center_x = rand($margin, $max - $margin);
    $center_y = rand($margin, $max - $margin);
    for ($j = 1; $j <= $dot_num_per_center; $j++) {
        //中心点を中心にmarginの範囲で点を決める
        $x = rand($center_x - $margin, $center_x + $margin);
        $y = rand($center_y - $margin, $center_y + $margin);
        $dots[] = ["x" => $x, "y" => $y];
        print "<tr><td>{$x}</td><td>{$y}</td></tr>";
    }
}
print "</table>";

//初期の重心を適当に決める（適当すぎて重心候補から外れてエラーになることがある）
$gravity = [];
for ($i = 1; $i <= $center_num; $i++) {
    $gravity[$i]["x"] = rand($margin, $max - $margin);
    $gravity[$i]["y"] = rand($margin, $max - $margin);
}

//k-means実行
for($num = 1; $num <= $action_num; $num++)
{
    //各点の一番近い重心を決める
    foreach ($dots as $dot_key => $dot) {
        $min_length = 0;
        for ($i = 1; $i <= $center_num; $i++) {
            $length = calc_length($gravity[$i]["x"], $gravity[$i]["y"], $dot["x"], $dot["y"]);
            if($min_length === 0 || $min_length > $length) {
                $min_length = $length;
                $dots[$dot_key]["gravity_number"] = (int)$i;
            }
        }
    }

    //各重心の点の重心を再計算する
    $gravity = [];
    $count = [];
    foreach ($dots as $dot_key => $dot) {
        if(!isset($gravity[$dot["gravity_number"]]["x"])) $gravity[$dot["gravity_number"]]["x"] = 0;
        $gravity[$dot["gravity_number"]]["x"] += $dot["x"];
        if(!isset($gravity[$dot["gravity_number"]]["y"])) $gravity[$dot["gravity_number"]]["y"] = 0;
        $gravity[$dot["gravity_number"]]["y"] += $dot["y"];

        //核にある点の数
        if(!isset($count[$dot["gravity_number"]]))$count[$dot["gravity_number"]] = 0;
        $count[$dot["gravity_number"]]++;
    }

    for ($i = 1; $i <= $center_num; $i++) {
        if(isset($gravity[$i]["x"]))$gravity[$i]["x"] /= $count[$i];
        if(isset($gravity[$i]["y"]))$gravity[$i]["y"] /= $count[$i];
    }
}

print "<br /><br /><br />②以下がクラスターに分けたデータです";

//それぞれの重心の点を表示する
print "<table>";
foreach ($dots as $dot_key => $dot) {
    print"<tr><td>{$dot["x"]}".(str_repeat("</td><td>", (int)$dot["gravity_number"])).$dot["y"]."</td></tr>";
}
print "</table>";

//長さを求める
function calc_length($x1, $y1, $x2, $y2)
{
    return sqrt(pow($x1 - $x2, 2) + pow($y1 - $y2, 2));
}

데이터 보기

위의 PHP를 실행하면 위와 아래에 두 개의 테이블이 출력됩니다. (①②라고 표시하고 있습니다)

데이터의 점재 확인

①은 데이터의 점재를 확인합니다. 엑셀에 붙여, 「산포도」에서 확인할 수 있습니다.

클러스터 확인

②는 클러스터로 나뉘어진 상태를 확인할 수 있습니다. 마찬가지로 엑셀에 붙여 "산포도"에서 확인할 수 있습니다.

도전

만약 결정한 무게 중심이 완전 랜덤이므로, 데이터의 점재로부터 너무 멀어져 에러가 되는 일이 있습니다. . .
그 때는, 다시 실행해 주세요.
실제 k-means법에서는, 가결정의 중심은 데이터의 점재 상황에 따라 어느 정도 영역을 한정하는 것으로 밝혀졌습니다.