NPR & Fluids World

Walk into Art with Heart
<2009年4月>
日一二三四五六
2930311234
567891011
12131415161718
19202122232425
262728293012
3456789

统计

  • 随笔 - 9
  • 文章 - 0
  • 评论 - 9
  • 引用 - 0

常用链接

留言簿(1)

随笔分类(10)

随笔档案(9)

others

搜索

  •  

最新评论

阅读排行榜

评论排行榜

K-Nearest Neighbor[KNN] Classifier Implementation
 1double squared_distance(double* source, double* target, int d)
 2{
 3    double res = 0;
 4    for (int i=0;i<d;i++)
 5    {
 6        res += pow(source[i]-target[i],2);
 7    }
 8    return sqrt(res);
 9}
10
11int knnLabel(double **p, int n, int d, int *c, double *x, int k, double t = 0)
12{
13   assert(k > 0 && k <= n && d > 0 && p && c && x);
14
15   if (t > 0) {
16      t *= t; // because we use squared distance
17   }
18
19   // a list of {index => distance} pairs
20   std::list<std::pair<int, double> > nabors;
21   std::list<std::pair<int, double> >::iterator i;
22   for (int j = 0; j < n; j++) {
23      double dist = squared_distance(p[j], x, d);
24      if (dist <= t) { // a neighbour within acceptable distance found
25         return c[j]; // done, immediately report this neighbour's category
26      }
27
28      //====
29      // check if p[j] is closer to the target than any recorded neighbours,
30      // and if positive then sort its index/distance profile into the list.
31
32      // searching the list for the first one with a longer distance
33      for (i = nabors.begin(); i != nabors.end() && dist >= i->second; i++);
34
35      if (i != nabors.end() || nabors.size() < k) { // p[j] qualified
36         nabors.insert(i, 1, std::pair<int, double>(j, dist));
37         if (nabors.size() > k) { // list overfilled (has k+1 profiles)
38            nabors.pop_back(); // bumping out the farthest neighbour
39         }
40      }
41   }
42   //====
43   // each of the k nearest neighbours cast a vote, and the majority wins
44   // use class average distance to the target to break any possible ties
45
46   // a {category => {count => distance}} map
47   std::map<int, std::pair<int, double> > votes;
48   int winner = c[0]; // randomly assign an initial category
49
50   for (i = nabors.begin(); i != nabors.end(); i++) {
51      int count = ++(votes[c[i->first]].first);
52      double dist = (votes[c[i->first]].second += i->second);
53      if (count > votes[winner].first || /* check for a possible tie */
54          count == votes[winner].first && dist < votes[winner].second) {
55         winner = c[i->first];
56      }
57   }
58
59   return winner;
60}
61

posted on 2008-05-22 15:20 Henry Ren 阅读(614) 评论(0)  编辑 收藏 引用 所属分类: 技术


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理