К-означает, что центры кластеров одинаковы при каждом запуске, хотя инициализируются случайным образом - PullRequest
Новая
       118

К-означает, что центры кластеров одинаковы при каждом запуске, хотя инициализируются случайным образом

0 голосов
/ 06 августа 2020

У меня есть приложение, в котором мне нужно самому реализовать K-means. Я пробовал свою реализацию в небольшой программе, чтобы посмотреть, как идут дела; однако меня действительно сбивает с толку то, что каждый раз при запуске программы я получаю одни и те же центры кластеров. Я удивлен, потому что мои центры кластеров инициализируются случайным образом, и я использую FLANN для обновления кластеров (оба должны сделать вывод недетерминированным c, верно?). Я, наверное, что-то упускаю и буду признателен за помощь. 

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

Ответы [ 2 ]

2 голосов
/ 06 августа 2020

Вам нужна эта строка: 

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

в начале вашей программы, чтобы получать различные последовательности из функции rand каждый раз, когда вы запускаете программу.

Вы можете использовать некоторые другое начальное значение, если хотите, но вам все равно нужно вызвать srand с некоторым источником случайности в начале программы.

0 голосов
/ 09 августа 2020

OpenCV также предоставляет класс генератора случайных чисел: 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;
...