【IT168 技术】
注：本文为IT168&NVIDIA联合举办的“如何并行化我的应用”方案征集活动参赛作品。本次方案征集活动详情见：http://cuda.itpub.net/thread-1299715-1-1.html。近期活动的大部分方案，将会逐步与大家分享，不可错过哦!
CUDA ZONE专区：http://cuda.it168.com/
CUDA技术论坛：http://cuda.itpub.net
前面看到有个人写了个k-均值算法，我今天就写个k近邻算法看看!
KNN 算法的基本思想是:将文本内容形式化为特征空间中的向量,每个文本就是一个向量，向量的每维数据代表不同的内容。对于一个测试文本, 计算它与已分类样本集中每个文本的相似度, 找出K 个最相似的文本, 根据这k个文本中属于那个类的文本最多，以此判断测试文本所属的类别。具体算法步骤如下:
( 1) 将待分类文本特征化为向量a
( 2) 计算该测试文本与训练集中每个文本的文本(特征化为向量b)相似度, 计算公式为: cos = ab/(|a||b|)
( 3) 按照文本相似度, 在训练文本集中选出与测试文本最相似的k 个文本。
( 4) 在测试文本的k 个近邻中, 依次计算每类的权重。本文权重定义为文本数
( 5) 比较类的权重, 将文本分到权重最大的那个类别中。
CUDA实现
unsigned int len;//text number
unsigned int dim;//text’s dimension
//every text have a row, column first
float *textData;
unsigned int pitch;//use to access textData
}text;
text结构中，len 表示所有文本的数量;dim 表示每个文本向量的维数;textData 表示所有的文本数据，每列代表一个文本的特征信息，pitch 是用cudaMallocPitch分配数据时返回的值除以4，也就是textData每行的长度。
下面的代码用于计算两个文本的相似度
__host__ __device__ float homo(text t, int first, int second){
float mul = 0.0f;
float o2 = 0.0f, tw2 = 0.0f, temp1, temp2;
for(int I = 0; I < t.dim; i++){
temp1 = t.textData[first + t.pitch*i];
temp2 = t.textData[second + t.pitch*i];
mul += temp1*temp2;
o2 +=temp1*temp1;
tw2 += temp2*temp2;
}
return mul/sqrtf(o2*tw2);
}
内核函数大致如下：其基本思想相当简单，就是每个线程处理自己的那一亩三分地。
Int id = blockDim.x*blockIdx.x + threadIdx.x;
float knn[K];
int index[K];
for(int I =0; I < k; i++){
index[i] = 0;
knn[i]= 0.0f;
｝
If( id >= t.len)
return;
float temp =home(…);
//遍历knn，将ｔｅｍｐ插入其中，丢弃最小的那个并记录其所属的类
…………………
}
由于流多处理器中的寄存器数量有限，所以K值不能太大，具体大小依据硬件每个 SM寄存器的数目以及每个线程块的线程数决定，由于 CUDA 目前还不支持动态数据，因此只能使用宏,这样保证了在实际使用的k值小于预定义的K时，依旧会被分配到寄存器中，但是一旦k大于K时，就要重新处理了。
