php - 二维聚类算法

Question

我正在分析图像，需要一种快速聚类算法来搜索最大中心的中心。

示例数据集可能如下所示：

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

如您所见，阵列中有 3 个集群。

我正在寻找的结果是总和最高的集群中心的数组位置。在上面的示例中，这将是 1，因为$x[1]最大集群 6+9+7(=22) 的中心也是如此。

有任何想法吗？

Answer 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";
}