CODEWITHSUNDEEP
phparraysalgorithmcluster-analysis
jantimon
jantimon

Reputation: 38160

2D Cluster algorithm

I am analyzing images and need a fast clustering algorithm which searches for the center of the biggest center.

A sample data set might look like this:

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

As you see there are 3 clusters in the array.

The result I am looking for is the array position of the center of the cluster with the highest sum. In the example above this would be 1 as $x[1] is the center of the biggest cluster 6+9+7(=22).

Graph

Any ideas?

Upvotes: 0

Views: 335

Answers (1)

Aleks G
Aleks G

Reputation: 57326

Whichever way you go, you'll have to walk through the array at least once. The following algorithm does this in one pass without any additional sorting/searching - although I admit that it still may not be the most efficient one. Note that if the biggest cluster has an even number of elements, then it'll return the "lower" mid-point (e.g. for a cluster with indices 0, 1, 2, 3 it will return 1) - this can be easily adjusted in the last line of computation ($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";
}

Upvotes: 1

Related Questions