php - 2D クラスター アルゴリズム

Question

画像を分析しており、最大の中心の中心を検索する高速クラスタリング アルゴリズムが必要です。

サンプル データ セットは次のようになります。

$x = array(6,9,7,0,0,0,4,0,0,6,6,3);

ご覧のとおり、アレイには 3 つのクラスターがあります。

私が探している結果は、合計が最も高いクラスターの中心の配列位置です。上記の例$x[1]では、最大のクラスター 6+9+7(=22) の中心であるため、これは 1 になります。

何か案は？

Answer 1

どちらの方法でも、少なくとも 1 回は配列を通過する必要があります。次のアルゴリズムは、追加の並べ替え/検索を行わずに 1 回のパスでこれを実行しますが、それでも最も効率的なアルゴリズムではない可能性があることは認めます。最大のクラスターの要素数が偶数の場合、「より低い」中間点が返されることに注意してください (たとえば、インデックス 0、1、2、3 のクラスターの場合は 1 が返されます)。これは簡単に調整できます。計算の最後の行 ( $mid = ...)。

$input = array(6,9,7,0,0,0,4,0,0,6,6,3);

$clust = array(0, 0, 0);
$st = -1;
$sum = 0;
for($i=0; $i<count($input); $i++) {
    if($input[$i] == 0) {
        if($i == 0) {
            continue;
        }
        elseif($input[$i - 1] == 0) {
            continue;
        }
        else {
            if($clust[2] < $sum) {
                $clust = array($st, $i - 1, $sum);
            }
        }
    }
    else {
        if($i == 0 || $input[$i - 1] == 0) {
            $st = $i;
            $sum = 0;
        }
        $sum += $input[$i];
    }
}
if(end($input) != 0 && $clust[2] < $sum) {
    $clust = array($st, $i - 1, $sum);
}

if($clust[2] > 0) {
    $mid = (int)(($clust[1] - $clust[0]) / 2);
    echo $clust[0] ."->". $mid ."->" . $clust[1] ." = ". $clust[2];
}
else {
    echo "No clusters found";
}