Home > programming > openCV中kmeans++的实现

openCV中kmeans++的实现

上次看了一下OpenCV中kmeans算法的实现,现在来看看剩下部分的kmeans++的东西。kmeans++其实是在初始化cluster中心点的时候用到的算法。按照wiki上的说法这样做的好处解决了kmeans的一个问题: the approximation found can be arbitrarily bad with respect to the objective function compared to the optimal clustering.

下面是源代码

centers[0] = (unsigned)rng % N;//随机选择一个数据作为第一个center的中心点
for( i = 0; i < N; i++ )
{
    dist[i] = distance(data + step*i, data + step*centers[0], dims);//计算每一个数据点到第一个center的中心的距离
    sum0 += dist[i];//sum of the these distance
}
for( k = 1; k < K; k++ )//计算剩下的centers的中心点
{
    double bestSum = DBL_MAX;
    int bestCenter = 1;
    for( j = 0; j < trials; j++ )//在这里trials通常是3,原因我不清楚
    {
        double p = (double)rng*sum0, s = 0;//
        for( i = 0; i < N1; i++ )
            if( (p = dist[i]) <= 0 )
                break;//随机选择一个数据点,这个数据点貌似有什么特性,不过我没有看出来,为啥要这样做我还是不清楚
        int ci = i;//我们暂时找到了一个新的中心点
        for( i = 0; i < N; i++ )
        {
            tdist2[i] = std::min(distance(data + step*i, data + step*ci, dims), dist[i]);
            s += tdist2[i];//计算每个点到新的这个中心点的距离
        }
        
        if( s < bestSum )
        {//如果这个新的中心点比刚才找到的要好的话,就用这个了
            bestSum = s;
            bestCenter = ci;
            std::swap(tdist, tdist2);
        }
    }
    centers[k] = bestCenter;//这样查找3次以后我们得到了一个新的center的中心点
    sum0 = bestSum;
    std::swap(dist, tdist);
}
for( k = 0; k < K; k++ )
{//输出
    const float* src = data + step*centers[k];
    float* dst = _out_centers.ptr<float>(k);
    for( j = 0; j < dims; j++ )
        dst[j] = src[j];
}

虽然上面的代码很简单,但是因为没有理解算法所以不能完全搞懂。还需要一边看看算法一边在琢磨一下每一步在做什么和为什么要这么做。

Categories: programming Tags: , ,
  1. No comments yet.
  1. No trackbacks yet.