二维聚类算法

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