二維聚類算法

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