K-means 聚类中心每个运行都相同，尽管它是随机初始化的

Question

我有一个应用程序需要自己实现 K-means。我正在尝试在一个小程序中实现我的实现，看看事情进展如何；但是，我发现每次运行程序时得到完全相同的聚类中心真的很令人困惑。我很惊讶，因为我的集群中心是随机初始化的，而且我正在使用 FLANN 更新集群（两者都应该使输出不确定，对吧？）。我可能遗漏了一些东西，希望得到一些帮助。

cv::Mat kMeans(cv::Mat data, int k, int max_itr){
    cv::Mat centroids = cv::Mat(cv::Size(data.cols, k), data.type());
    std::vector<int> cluster_ids(data.rows, 0);

    //randomly initialize centroids
    for(int i = 0; i < k; i++)
    {
        int idx = rand() % data.rows;
        data.row(idx).copyTo(centroids.row(i));
    }

    int itr = 0;
    cv::flann::Index kdtree(centroids, cv::flann::KDTreeIndexParams(4));
    cv::Mat indices, dists;
    
    //TODO: add tolerance stopping condition
    while (itr < max_itr)
    {
        //assign data points to centroids
        for(int i = 0; i < data.rows; i++)
        {
            kdtree.knnSearch(data.row(i), indices, dists, 1, cv::flann::SearchParams(32));
            cluster_ids[i] = indices.data[0];
        } 
        //update centroids
        for(int i = 0; i < centroids.rows; i++)
        {
            cv::Mat sum = cv::Mat::zeros(cv::Size(data.cols, 1), data.type()); 
            int count = 0;
            for(int j = 0; j < data.rows; j++)
            {
                if(cluster_ids[j] != i) {continue;}
                sum += data.row(j);
                count++;
            }
            centroids.row(i) = sum / float(count);
        }
       itr += 1;
    }
return centroids;
}

int main()
{
    cv::Mat_<float> data;
    cv::Mat_<float> centroids;
    cv::Mat dst;
    //initialize with dummy data
    for(int i = 0; i < 1000; i++) 
    { 
        cv::Mat row = (cv::Mat_<float>(1, 3) << float(i), float(i), float(i));
        data.push_back(row);
    }
    centroids = kMeans(data, 20, 20);
    std::cout << centroids << std::endl;
 
    return 0;
}

Answer 1

您需要这一行：

std::srand(std::time(nullptr)); // use current time as seed for random generator

在程序开始时每次运行程序时从 rand 函数获取不同的序列。

如果需要，您可以使用其他一些种子，但您仍然需要在程序开始时使用一些随机源调用 srand。

Answer 2

OpenCV 还提供了一个随机数生成器class：cv::RNG。你可以这样使用它：

//Create the RNG object:
cv::RNG& rng = cv::theRNG();
//Seed it:
rng.state = cv::getTickCount();

//Print it:
std::cout<<"Random Number: "<<(int)rng<<std::endl;

K-means 聚类中心每个运行都相同，尽管它是随机初始化的

K-means Cluster Centers Are the Same Every Run Although It Is Randomly Initialized

c++

opencv

k-means

flann

K-means 聚类中心每个 运行 都相同，尽管它是随机初始化的

K-means Cluster Centers Are the Same Every Run Although It Is Randomly Initialized

c++

opencv

k-means

flann

K-means 聚类中心每个运行都相同，尽管它是随机初始化的