127fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk/* 227fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk * Copyright (C) 2012 The Android Open Source Project 327fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk * 427fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk * Licensed under the Apache License, Version 2.0 (the "License"); 527fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk * you may not use this file except in compliance with the License. 627fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk * You may obtain a copy of the License at 727fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk * 827fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk * http://www.apache.org/licenses/LICENSE-2.0 927fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk * 1027fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk * Unless required by applicable law or agreed to in writing, software 1127fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk * distributed under the License is distributed on an "AS IS" BASIS, 1227fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 1327fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk * See the License for the specific language governing permissions and 1427fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk * limitations under the License. 1527fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk */ 1627fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk 1727fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk#ifndef KMEANS_H 1827fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk#define KMEANS_H 1927fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk 2027fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk#include <cstdlib> 2127fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk#include <math.h> 2227fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk 2327fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk// Helper functions 2427fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk 2527fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunktemplate <typename T, typename N> 2627fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunkinline void sum(T values[], int len, int dimension, int stride, N dst[]) { 2727fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk int x, y; 2827fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk // zero out dst vector 2927fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk for (x = 0; x < dimension; x++) { 3027fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk dst[x] = 0; 3127fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk } 3227fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk for (x = 0; x < len; x+= stride) { 3327fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk for (y = 0; y < dimension; y++) { 3427fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk dst[y] += values[x + y]; 3527fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk } 3627fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk } 3727fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk} 3827fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk 3927fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunktemplate <typename T, typename N> 4027fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunkinline void set(T val1[], N val2[], int dimension) { 4127fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk int x; 4227fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk for (x = 0; x < dimension; x++) { 4327fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk val1[x] = val2[x]; 4427fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk } 4527fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk} 4627fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk 4727fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunktemplate <typename T, typename N> 4827fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunkinline void add(T val[], N dst[], int dimension) { 4927fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk int x; 5027fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk for (x = 0; x < dimension; x++) { 5127fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk dst[x] += val[x]; 5227fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk } 5327fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk} 5427fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk 5527fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunktemplate <typename T, typename N> 5627fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunkinline void divide(T dst[], N divisor, int dimension) { 5727fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk int x; 5827fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk if (divisor == 0) { 5927fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk return; 6027fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk } 6127fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk for (x = 0; x < dimension; x++) { 6227fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk dst[x] /= divisor; 6327fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk } 6427fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk} 6527fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk 6627fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk/** 6727fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk * Calculates euclidean distance. 6827fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk */ 6927fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk 7027fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunktemplate <typename T, typename N> 7127fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunkinline N euclideanDist(T val1[], T val2[], int dimension) { 7227fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk int x; 7327fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk N sum = 0; 7427fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk for (x = 0; x < dimension; x++) { 7527fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk N diff = (N) val1[x] - (N) val2[x]; 7627fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk sum += diff * diff; 7727fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk } 7827fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk return sqrt(sum); 7927fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk} 8027fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk 8127fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk// K-Means 8227fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk 8327fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk 8427fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk/** 8527fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk * Picks k random starting points from the data set. 8627fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk */ 8727fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunktemplate <typename T> 88f83b26c24ad2e3f6c9468afe18f43d1b53162fe3Ruben Brunkvoid initialPickHeuristicRandom(int k, T values[], int len, int dimension, int stride, T dst[], 89f83b26c24ad2e3f6c9468afe18f43d1b53162fe3Ruben Brunk unsigned int seed) { 9027fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk int x, z, num_vals, cntr; 9127fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk num_vals = len / stride; 9227fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk cntr = 0; 93f83b26c24ad2e3f6c9468afe18f43d1b53162fe3Ruben Brunk srand(seed); 9427fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk unsigned int r_vals[k]; 9527fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk unsigned int r; 9627fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk 9727fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk for (x = 0; x < k; x++) { 9827fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk 9927fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk // ensure randomly chosen value is unique 10027fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk int r_check = 0; 10127fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk while (r_check == 0) { 10227fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk r = (unsigned int) rand() % num_vals; 10327fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk r_check = 1; 10427fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk for (z = 0; z < x; z++) { 10527fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk if (r == r_vals[z]) { 10627fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk r_check = 0; 10727fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk } 10827fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk } 10927fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk } 11027fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk r_vals[x] = r; 11127fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk r *= stride; 11227fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk 11327fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk // set dst to be randomly chosen value 11427fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk set<T,T>(dst + cntr, values + r, dimension); 11527fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk cntr += stride; 11627fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk } 11727fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk} 11827fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk 11927fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk/** 12027fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk * Finds index of closet centroid to a value 12127fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk */ 12227fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunktemplate <typename T, typename N> 12327fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunkinline int findClosest(T values[], T oldCenters[], int dimension, int stride, int pop_size) { 12427fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk int best_ind = 0; 12527fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk N best_len = euclideanDist <T, N>(values, oldCenters, dimension); 12627fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk int y; 12727fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk for (y = stride; y < pop_size; y+=stride) { 12827fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk N l = euclideanDist <T, N>(values, oldCenters + y, dimension); 12927fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk if (l < best_len) { 13027fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk best_len = l; 13127fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk best_ind = y; 13227fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk } 13327fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk } 13427fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk return best_ind; 13527fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk} 13627fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk 13727fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk/** 13827fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk * Calculates new centroids by averaging value clusters for old centroids. 13927fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk */ 14027fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunktemplate <typename T, typename N> 14127fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunkint calculateNewCentroids(int k, T values[], int len, int dimension, int stride, T oldCenters[], 14227fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk T dst[]) { 14327fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk int x, pop_size; 14427fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk pop_size = k * stride; 14527fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk int popularities[k]; 14627fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk N tmp[pop_size]; 14727fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk 14827fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk //zero popularities 14927fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk memset(popularities, 0, sizeof(int) * k); 15027fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk // zero dst, and tmp 15127fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk for (x = 0; x < pop_size; x++) { 15227fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk tmp[x] = 0; 15327fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk } 15427fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk 15527fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk // put summation for each k in tmp 15627fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk for (x = 0; x < len; x+=stride) { 15727fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk int best = findClosest<T, N>(values + x, oldCenters, dimension, stride, pop_size); 15827fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk add<T, N>(values + x, tmp + best, dimension); 15927fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk popularities[best / stride]++; 16027fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk 16127fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk } 16227fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk 16327fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk int ret = 0; 16427fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk int y; 16527fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk // divide to get centroid and set dst to result 16627fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk for (x = 0; x < pop_size; x+=stride) { 16727fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk divide<N, int>(tmp + x, popularities[x / stride], dimension); 16827fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk for (y = 0; y < dimension; y++) { 16927fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk if ((dst + x)[y] != (T) ((tmp + x)[y])) { 17027fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk ret = 1; 17127fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk } 17227fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk } 17327fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk set(dst + x, tmp + x, dimension); 17427fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk } 17527fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk return ret; 17627fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk} 17727fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk 178f83b26c24ad2e3f6c9468afe18f43d1b53162fe3Ruben Brunktemplate <typename T, typename N> 179f83b26c24ad2e3f6c9468afe18f43d1b53162fe3Ruben Brunkvoid runKMeansWithPicks(int k, T finalCentroids[], T values[], int len, int dimension, int stride, 180f83b26c24ad2e3f6c9468afe18f43d1b53162fe3Ruben Brunk int iterations, T initialPicks[]){ 181f83b26c24ad2e3f6c9468afe18f43d1b53162fe3Ruben Brunk int k_len = k * stride; 182f83b26c24ad2e3f6c9468afe18f43d1b53162fe3Ruben Brunk int x; 183f83b26c24ad2e3f6c9468afe18f43d1b53162fe3Ruben Brunk 184f83b26c24ad2e3f6c9468afe18f43d1b53162fe3Ruben Brunk // zero newCenters 185f83b26c24ad2e3f6c9468afe18f43d1b53162fe3Ruben Brunk for (x = 0; x < k_len; x++) { 186f83b26c24ad2e3f6c9468afe18f43d1b53162fe3Ruben Brunk finalCentroids[x] = 0; 187f83b26c24ad2e3f6c9468afe18f43d1b53162fe3Ruben Brunk } 188f83b26c24ad2e3f6c9468afe18f43d1b53162fe3Ruben Brunk 189f83b26c24ad2e3f6c9468afe18f43d1b53162fe3Ruben Brunk T * c1 = initialPicks; 190f83b26c24ad2e3f6c9468afe18f43d1b53162fe3Ruben Brunk T * c2 = finalCentroids; 191f83b26c24ad2e3f6c9468afe18f43d1b53162fe3Ruben Brunk T * temp; 192f83b26c24ad2e3f6c9468afe18f43d1b53162fe3Ruben Brunk int ret = 1; 193f83b26c24ad2e3f6c9468afe18f43d1b53162fe3Ruben Brunk for (x = 0; x < iterations; x++) { 194f83b26c24ad2e3f6c9468afe18f43d1b53162fe3Ruben Brunk ret = calculateNewCentroids<T, N>(k, values, len, dimension, stride, c1, c2); 195f83b26c24ad2e3f6c9468afe18f43d1b53162fe3Ruben Brunk temp = c1; 196f83b26c24ad2e3f6c9468afe18f43d1b53162fe3Ruben Brunk c1 = c2; 197f83b26c24ad2e3f6c9468afe18f43d1b53162fe3Ruben Brunk c2 = temp; 198f83b26c24ad2e3f6c9468afe18f43d1b53162fe3Ruben Brunk if (ret == 0) { 199f83b26c24ad2e3f6c9468afe18f43d1b53162fe3Ruben Brunk x = iterations; 200f83b26c24ad2e3f6c9468afe18f43d1b53162fe3Ruben Brunk } 201f83b26c24ad2e3f6c9468afe18f43d1b53162fe3Ruben Brunk } 202f83b26c24ad2e3f6c9468afe18f43d1b53162fe3Ruben Brunk set<T, T>(finalCentroids, c1, dimension); 203f83b26c24ad2e3f6c9468afe18f43d1b53162fe3Ruben Brunk} 204f83b26c24ad2e3f6c9468afe18f43d1b53162fe3Ruben Brunk 20527fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk/** 20627fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk * Runs the k-means algorithm on dataset values with some initial centroids. 20727fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk */ 20827fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunktemplate <typename T, typename N> 20927fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunkvoid runKMeans(int k, T finalCentroids[], T values[], int len, int dimension, int stride, 210f83b26c24ad2e3f6c9468afe18f43d1b53162fe3Ruben Brunk int iterations, unsigned int seed){ 21127fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk int k_len = k * stride; 21227fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk T initialPicks [k_len]; 213f83b26c24ad2e3f6c9468afe18f43d1b53162fe3Ruben Brunk initialPickHeuristicRandom<T>(k, values, len, dimension, stride, initialPicks, seed); 21427fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk 215f83b26c24ad2e3f6c9468afe18f43d1b53162fe3Ruben Brunk runKMeansWithPicks<T, N>(k, finalCentroids, values, len, dimension, stride, 216f83b26c24ad2e3f6c9468afe18f43d1b53162fe3Ruben Brunk iterations, initialPicks); 21727fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk} 21827fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk 21927fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk/** 22027fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk * Sets each value in values to the closest centroid. 22127fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk */ 22227fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunktemplate <typename T, typename N> 22327fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunkvoid applyCentroids(int k, T centroids[], T values[], int len, int dimension, int stride) { 22427fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk int x, pop_size; 22527fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk pop_size = k * stride; 22627fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk for (x = 0; x < len; x+= stride) { 22727fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk int best = findClosest<T, N>(values + x, centroids, dimension, stride, pop_size); 22827fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk set<T, T>(values + x, centroids + best, dimension); 22927fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk } 23027fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk} 23127fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk 23227fb72ee1413871b4958ab2f24a229574de6ffa2Ruben Brunk#endif // KMEANS_H 233