|
|
楼主
楼主 |
发表于 2009-12-23 14:00:23
|
只看该作者
如何用SAS/Base Stat写KNN(K近邻)的实现方法
KNN的算法本身很简单，但是计算复杂度很高，如果没有优化算法，100万条记录的多维表，计算复杂度是100万*100万，好几个小时也出不来，我知道可以用K-D Tree或者Hash的方法建索引降低搜索复杂度，但是不会写，不知道有没有高人写过啊。谢谢。
KNN算法的大概描述：
数据表:var1-varn是用于计算距离的指标，Target是每一个ID的目标值
id,var1,var2,var3,var4...varn,target
1,23,34,56,7,88,...
2,...
3,...
4,...
KNN算法的目标就是：针对每一个ID，搜索跟它距离（如欧式距离）最近的K（K需要指定）个邻居，把K个邻居的Target值进行某些处理（例如求平均值）之后作为该ID的Target预测值。
如果数据表有100万条记录，复杂度是100万*100万。 |
|
