Получить ближайший центроид, используя библиотеку Thrust? (К-средства)

Question

Получить ближайший центроид, используя библиотеку Thrust? (К-средства)

Я уже закончил вычисление расстояний и сохранил в векторе тяги, например, у меня есть 2 центроида и 5 точек данных, и способ вычисления расстояний заключался в том, что для каждого центроида я сначала вычислял расстояния с 5 точками данных и сохранял их в массиве и позже с другим центроидом в одномерном массиве на расстояниях, вот так:

for (int i = 0; i < centroids.size(); ++i)
{
computeDistance(Data, distances, centroids[i], nDataPoints, nDimensions);
}

В результате получается вектор 1d, например:

DistancesValues = {10, 15, 20, 12, 10, 5, 17, 22, 8, 7}

DatapointsIndex = {1, 2,  3,   4,  5,  1,  2,  3, 4, 5}

Где первые 5 значений представляют центроид 1, а другие 5 значений центроид 2.

Что я хотел бы знать, если есть функция тяги, в которой я могу хранить счет в другом массиве минимальных значений для каждого центроида?

Сравнивая значения каждого индекса, Результатом должно быть:

Counts = {2, 3}

где:

CountOfCentroid 1 = 2
CountOfCentroid 2 = 3

0

c++cuda k-means thrust

Решение

Другие решения

Источник

Accepted Answer

Вот один из возможных подходов:

Создайте дополнительный вектор индекса центроида:

DistancesValues = {10, 15, 20, 12, 10, 5, 17, 22,  8, 7}
DatapointsIndex = {1,   2,  3,  4,  5, 1,  2,  3,  4, 5}
CentroidIndex   = {1,   1,  1,  1,  1, 2,  2,  2,  2, 2}

Теперь сделайте sort_by_key, используя DatapointsIndex в качестве ключей, а два других вектора упакованы в виде значений. Это приводит к перестановке всех 3 векторов так, чтобы DatapointsIndex имеет схожие индексы:
```
DatapointsIndex = {1, 1, 2, 2, 3, 3, 4, 4, 5, 5}
```
(и другие 2 вектора соответственно переставлены).
Теперь сделайте limit_by_key. Если мы выберем thrust::minimum Оператор, мы получаем сокращение, которое эффективно выбирает минимальное значение в группе (а не суммирует значения в группе). Reduce_by_key означает, что сокращение этого типа выполняется для каждой последовательной группы одинаковых ключей. Таким образом, мы будем снова использовать DatapointsIndex как наш ключевой вектор, а два других вектора заархивированы как наш вектор значений. Большую часть выходных данных метода limit_by_key нам все равно, за исключением вектора результатов, который исходит из CentroidIndex вектор. Посчитав индексы центроидов в этом векторе результатов, мы можем получить желаемый результат.

Вот полностью проработанный пример:

$ cat t428.cu
#include <thrust/host_vector.h>
#include <thrust/device_vector.h>
#include <thrust/sort.h>
#include <thrust/reduce.h>
#include <thrust/copy.h>
#include <thrust/iterator/zip_iterator.h>
#include <thrust/iterator/discard_iterator.h>
#include <stdio.h>
#define NUM_POINTS 5
#define NUM_CENTROID 2
#define DSIZE (NUM_POINTS*NUM_CENTROID)

int main(){

int DistancesValues[DSIZE] = {10, 15, 20, 12, 10, 5, 17, 22, 8, 7};
int DatapointsIndex[DSIZE] = {1, 2,  3,   4,  5,  1,  2,  3, 4, 5};
int CentroidIndex[DSIZE]   = {1, 1, 1, 1, 1, 2, 2, 2, 2, 2};

thrust::device_vector<int> DV(DistancesValues, DistancesValues + DSIZE);
thrust::device_vector<int> DI(DatapointsIndex, DatapointsIndex + DSIZE);
thrust::device_vector<int> CI(CentroidIndex, CentroidIndex + DSIZE);
thrust::device_vector<int> Ra(NUM_POINTS);
thrust::device_vector<int> Rb(NUM_POINTS);

thrust::sort_by_key(DI.begin(), DI.end(), thrust::make_zip_iterator(thrust::make_tuple(DV.begin(), CI.begin())));
thrust::reduce_by_key(DI.begin(), DI.end(), thrust::make_zip_iterator(thrust::make_tuple(DV.begin(), CI.begin())), thrust::make_discard_iterator(), thrust::make_zip_iterator(thrust::make_tuple(Ra.begin(), Rb.begin())), thrust::equal_to<int>(), thrust::minimum<thrust::tuple<int, int> >());
printf("CountOfCentroid 1 = %d\n", thrust::count(Rb.begin(), Rb.end(), 1));
printf("CountOfCentroid 2 = %d\n", thrust::count(Rb.begin(), Rb.end(), 2));

return 0;
}

$ nvcc -arch=sm_20 -o t428 t428.cu
$ ./t428
CountOfCentroid 1 = 2
CountOfCentroid 2 = 3
$

Как указывает Эрик в своем ответе Вот (ваш вопрос почти дублирует этот вопрос), sort_by_key вероятно, не нужно. Переупорядочение этих данных следует регулярному шаблону, поэтому нам не нужно использовать сложность сортировки, и поэтому мы можем переупорядочивать данные с умным использованием итераторов. При таких обстоятельствах можно выполнить всю операцию (приблизительно) одним вызовом reduce_by_key,

2