k近邻算法matlab实现_k近邻算法

Dear 丶 2023-01-01 09:53 328阅读 0赞

k 近邻法 (k-NN) 是一种基于实例的学习方法，无法转化为对参数空间的搜索问题(参数最优化 问题)。它的特点是对特征空间进行搜索。除了k近邻法，本章还对以下几个问题进行较深入的讨 论:

  • 切比雪夫距离 的计算
  • “近似误差” 与“估计误差” 的含义
  • k-d树搜索算法图解

一、算法

输入：训练集 为实例特征向 为实例的类别,

输出：实例 所属的类

设在给定距离度量下，涵盖最近k个点的邻域为

其中示性函数 为真为假

寻找使得函数 取得最大值的变量 也就是说, 看看距离 最近的k个点里面哪一类别最多，以此作为输出。

二、模型

根据模型的分类, k-NN模型属于非概率模型。

观察 可发现它与感知机不同的之处, 作为决策函数, 它并不需要任何未知参数(感知机需要确定W和b)，直接从训练集的数据得到输出。

1. 距离度量

k-NN的基本思想是，特征空间中的距离反映了两个点的相似程度, 因此 “距离” 是作出分类判断 的基本依据。向量空间 的距离有多种度量方式：

(1) 不同距离度量

一般形式是闵可夫斯基距离( 范数)：

当p=1时, 称为曼哈顿距离( 范数)：

当p=2时，称为欧几里得距离( 范数)，也就是最常用的距离：:

  1. import math
  2. from itertools import combinations
  4. def L(x, y, p=2):
  5.     # x1 = [1, 1], x2 = [5,1]
  6.     if len(x) == len(y) and len(x) > 1:
  7.         sum = 0
  8.         for i in range(len(x)):
  9.             sum += math.pow(abs(x[i] - y[i]), p)
  10.         return math.pow(sum, 1 / p)
  11.     else:
  12.         return 0

下图表示平面上A、B两点之间不同的距离：a0b497bdbfb6a0425ad0100e87baf1a7.png

  • 只允许沿着坐标轴方向前进, 就像曼哈顿街区的出租车走过的距离
  • 两点之间直线最短, 通过勾股定理计算斜边的距离
  • 只剩下一个维度, 即最大的分量方向上的距离

可见p取值越大，两点之间的距离越短。

(2) 问题：为什么切比雪夫距离

其实这个问题等价于：为什么 即 空间中的向量 它的切比雪 夫长度等于它的最大分量方向上的长度。

证明: 设

不妨设 即

注意：最大分量的长度唯一, 但最大分量可能并不唯 一,设有x^{(1)}, x^{(2)}, \ldots x^{(k)}等个分量的长度都等于\left|x^{(1)}\right|$

当 即 为 时

当 即 为非最大长度分量时

计算 的切比雪夫长度:

由于已知 等于0或1，且有k个分量结果为1, 所以

因此

即 得证。

以上证明参考

(3) 平面上的圆

在平面上的图像:c086400f34a74934af558807d2aae6e6.png如果圆形的定义是 “到某一点距离相等的曲线围成的图形” ，那么在不同的距离度量下，圆形的形 状可以完全不同。为何 正则化在平面上的等高线为同心正方形, 不就很容易理解吗?

  1. k值选择

李航老师书中引入了“近似误差”和“估计误差”两个概念，但没有给出具体定义。

这里简单总结一下：

右侧两项分别是 “估计误差” 和 “近似误差”

  • 估计误差：训练集与无限数据集得到的模型的差距

  • 近似误差：限制假设空间与无限制假设空间得到的模型的差距

    • k值越小 单个样本影响越大 模型越复杂 假设空间越大 近似误差越小 (估计误差 越大)，容易过拟合;
    • k值越大 单个样本影响越小 模型越简单 假设空间越小 近似误差越大(估计误差 越小)，容易欠拟合。

一般通过交叉验证来确定最优的 k 值。

  1. 决策规则

k 近邻的决策规则就是 “多数表决” ，即少数服从多数, 用数学表达式表示为

等号左侧为误分类率，要是误分类率最小，就要使得 最大, 即选择集合 中最多的一类。

三、kd树

kd 树的结构

kd树是一个二叉树结构，它的每一个节点记载了 [特征坐标, 切分轴, 指向左枝的指针, 指向右枝的指针] 。其中, 特征坐标是线性空间 中的一个点

切分轴由一个整数 表示, 这里 是我们在 维空间中沿第 维进行一次分割。节点的左枝和右枝分别都是 kd 树, 并且满足：如果 是左枝的一个特征坐标, 那么 并且如果 是右 枝的一个特征坐标，那么

给定一个数据样本集 和切分轴 以下递归算法将构建一个基于该数据集的 kd 树, 每一次循环制作一 个节点:

  • 如果 记录 中唯一的一个点为当前节点的特征数据, 并且不设左枝和右枝。 指集合 中元素 . 的数量) 如果

  • 如果

    • 将 S 内所有点按照第 个坐标的大小进行排序;
    • 选出该排列后的中位元素 (如果一共有偶数个元素, 则选择中位左边或右边的元素, 左或右并无影响)，作为当前节点的特征坐标, 并且记录切分轴 将 设为在 中所有排列在中位元素之前的元素; 设为在 中所有排列在中位元素后的元素;
    • 当前节点的左枝设为以 为数据集并且 为切分轴制作出的 树; 当前节点的右枝设为以 为数据集并且 为切分轴制作出 的 kd 树。再设 这里, 我们想轮流沿着每一个维度进 行分割; 是因为一共有 个维度, 在 沿着最后一个维度进行分割之后再重新回到第一个维度。)

构造 kd 树的例子

上面抽象的定义和算法确实是很不好理解，举一个例子会清楚很多。首先随机在 中随机生成 13 个点作为我们的数据集。起始的切分轴 这里 对应 轴, 而 对应 轴。06a03dfef499dd149435a3a7481e8902.png首先先沿 x 坐标进行切分，我们选出 x 坐标的中位点，获取最根部节点的坐标64398c4983945f1c7554abcb17b57bca.png

并且按照该点的x坐标将空间进行切分，所有 x 坐标小于 6.27 的数据用于构建左枝，x坐标大于 6.27 的点用于构建右枝。cb7d2d1a15f1f2a458bcdf789512d382.png节点。得到下面的树，左边的x 是指这该层的节点都是沿 x 轴进行分割的。12b992946d6dad8d821657d81aac43e9.png空间的切分如下80cc2ba4f9c71002d411879faf550bd6.png下一步中 对应 轴, 所以下面再按照 除标进行排序和切分,有732f6f5c1de2e066859c3c0554348ac0.png9c99a458eaddf97a01b9cadc487a3c97.png最后每一部分都只剩一个点，将他们记在最底部的节点中。因为不再有未被记录的点，所以不再进行切分。f7ac1d37dfb6633e3e3b536ae26d9205.png87ab0b5180b5b4a176e70a271432fb9c.png就此完成了 kd 树的构造。

kd 树上的 kNN 算法

给定一个构建于一个样本生的 kd 树, 下面的算法可以寻找距离某个点 最近的 个样本。

  1. 设 为一个有 个空位的列表, 用于保存已搜寻到的最近点.
  2. 根据 的坐标值和每个节点的切分向下搜素(也就是选，如果树的节点是按照 进行切分，并且 的 坐标小于 则向左枝进行搜索: 反之则走右枝)。
  3. 当达到一个底部节点时，将其标记为访问过. 如果 里不足 个点. 则将当前节点的特征坐标加人 如 果 L不为空并且当前节点 的特征与 的距离小于 里最长的距离，则用当前特征音换掉 中离 最远的点

  4. 如果当前节点不是整棵树最顶而节点, 执行 下(1)：反之. 输出 算法完成. (1) . 向上爬一个节点。如果当前 (向上爬之后的) 节点未管被访问过, 将其标记为被访问过, 然后执行 1和2：如果当前节点被访 问过, 再次执行 (1)。

    1. 如果此时 里不足 个点, 则将节点特征加入 如果 中已满 个点, 且当前节点与 的距离小于 里最长的距离。则用节点特征豐换掉 中帝最远的点。
    2. 计算 和当前节点切分綫的距离。如果该距离大于等于 中距离 最远的距离井且 中已有 个点。则在切分线另一边不会有更近的点, 执行3: 如果该距离小于 中最远的距离或者 中不足 个点, 则切分綫另一边可能有更近的点, 因此在当前节点的另一个枝从 开始执行.

来看下面的例子：f11d5e01d5ce2a8ac22fce28c8cb6281.png首先执行1，我们按照切分找到最底部节点。首先，我们在顶部开始8d91e791bc0847fba17ddb8ba5ddffc9.png和这个节点的 x轴比较一下，5318f4aafe6910ff53ea251d8d007285.pngppp 的 x 轴更小。因此我们向左枝进行搜索：057fa3824dc7a2b0bc3f546e0b8b240a.png这次对比 y 轴，8a295ca9067758fae05e255e0c74d2ec.pngp 的 y 值更小，因此向左枝进行搜索：332b98fb03c2d1154733784d2134ec2b.png这个节点只有一个子枝，就不需要对比了。由此找到了最底部的节点 (−4.6,−10.55)。28717b2e1d10265c8b5f9fcf2342760e.png在二维图上是d09efa154746b760c368f00ade5bdf73.png此时我们执行2。将当前结点标记为访问过, 并记录下 访问过的节点就在二叉树 上显示为被划掉的好了。

然后执行 3，不是最顶端节点。执行 (1)，我爬。上面的是 (−6.88,−5.4)。ca3fc5282ba265224fe46ca7f440f6a3.png8c72193420262cf08e9499c7e72edce4.png

执行 1，因为我们记录下的点只有一个，小于k=3，所以也将当前节点记录下，有 L=[(−4.6,−10.55),(−6.88,−5.4)]。再执行 2，因为当前节点的左枝是空的，所以直接跳过，回到步骤3。3看了一眼，好，不是顶部，交给你了，(1)。于是乎 (1) 又往上爬了一节。2c3120ade29c90e38e20be68a7bc47a4.png6c5c7c1b135df4934867a3294ed2be41.png1 说，由于还是不够三个点，于是将当前点也记录下，有 L=[(−4.6,−10.55),(−6.88,−5.4),(1.24,−2.86)。当然，当前结点变为被访问过的。

2又发现，当前节点有其他的分枝，并且经计算得出 p 点和 L 中的三个点的距离分别是 6.62,5.89,3.10，但是 p 和当前节点的分割线的距离只有 2.14，小于与 L 的最大距离：42193065fc68d5a3b8958a34e14add66.png因此，在分割线的另一端可能有更近的点。于是我们在当前结点的另一个分枝从头执行 1。好，我们在红线这里：32eabf846b215bfe99509281d8566a10.png要用 p 和这个节点比较 x 坐标:d10a62dec73d3eec06d6f45e080d0f28.pngp 的x 坐标更大，因此探索右枝 (1.75,12.26)，并且发现右枝已经是最底部节点，因此启动 2。65f2ae4dade2a1e985a0950a41b9a20e.png经计算，(1.75,12.26)与 p 的距离是 7.48，要大于 p 与 L 的距离，因此我们不将其放入记录中。1c8cdb5ac5e94246c41379fc706ea419.png然后 3 判断出不是顶端节点，呼出 (1)，爬。5a7aea1ac85c3573b8d8c1d7100ab42e.png1出来一算，这个节点与 p 的距离是 4.91，要小于 p 与 L 的最大距离 6.62。d50a23922354bde4e9c1638ac3b7f22f.png因此，我们用这个新的节点替代 L 中离 p 最远的 (−4.6,−10.55)。06c76f100ba18817fde601d828bd3ca8.png然后 2又来了，我们比对 p 和当前节点的分割线的距离1ed8bfb515d276f97d3fecad88283315.png这个距离小于 L 与 p 的最小距离，因此我们要到当前节点的另一个枝执行 1。当然，那个枝只有一个点，直接到 2。9325d140947b0024c1d4c301bbce88a3.png计算距离发现这个点离 p 比 L 更远，因此不进行替代。5c093c495f19b3fdfae9d7cd9c78c7d0.png3发现不是顶点，所以呼出 (1)。我们向上爬，a3966725840bd179c696ab5ed7f67cc6.png这个是已经访问过的了，所以再来(1)，217a2150ff1e2a913746c9c7d801cf54.png好，(1)再爬，4d19160779cf0848921c266c4c3c7682.png啊！到顶点了。所以完了吗？当然不，还没轮到 3 呢。现在是 1的回合。

我们进行计算比对发现顶端节点与p的距离比L还要更远，因此不进行更新。724be2077a5ac878d43d4c4e5c7d99a9.png然后是 2，计算 p 和分割线的距离发现也是更远。2daaf58ebfa0bfe9e1ce0717a642779f.png因此也不需要检查另一个分枝。

然后执行 3，判断当前节点是顶点，因此计算完成！输出距离 p 最近的三个样本是 L=[(−6.88,−5.4),(1.24,−2.86),(−2.96,−2.5)].

C实现

  1. #include 
  2. #include 
  3. #include 
  4. #include 
  5. #include 
  7. #include "kdtree.h"
  9. static inline int is_leaf(struct kdnode *node){
  11.         return node->left == node->right;
  12. }
  14. static inline void swap(long *a, long *b){
  16.         long tmp = *a;
  17.         *a = *b;
  18.         *b = tmp;
  19. }
  21. static inline double square(double d){
  23.         return d * d;
  24. }
  26. static inline double distance(double *c1, double *c2, int dim){
  28.         double distance = 0;
  29.         while (dim-- > 0) {
  31.                 distance += square(*c1++ - *c2++);
  32.         }
  33.         return distance;
  34. }
  36. static inline double knn_max(struct kdtree *tree){
  38.         return tree->knn_list_head.prev->distance;
  39. }
  41. static inline double D(struct kdtree *tree, long index, int r){
  43.         return tree->coord_table[index][r];
  44. }
  46. static inline int kdnode_passed(struct kdtree *tree, struct kdnode *node){
  48.         return node != NULL ? tree->coord_passed[node->coord_index] : 1;
  49. }
  51. static inline int knn_search_on(struct kdtree *tree, int k, double value, double target){
  53.         return tree->knn_num }
  55. static inline void coord_index_reset(struct kdtree *tree){
  57.         long i;
  58.         for (i = 0; i capacity; i++) {
  60.                 tree->coord_indexes[i] = i;
  61.         }
  62. }
  64. static inline void coord_table_reset(struct kdtree *tree){
  66.         long i;
  67.         for (i = 0; i capacity; i++) {
  69.                 tree->coord_table[i] = tree->coords + i * tree->dim;
  70.         }
  71. }
  73. static inline void coord_deleted_reset(struct kdtree *tree){
  75.         memset(tree->coord_deleted, 0, tree->capacity);
  76. }
  78. static inline void coord_passed_reset(struct kdtree *tree){
  80.         memset(tree->coord_passed, 0, tree->capacity);
  81. }
  83. static void coord_dump_all(struct kdtree *tree){
  85.         long i, j;
  86.         for (i = 0; i count; i++) {
  88.                 long index = tree->coord_indexes[i];
  89.                 double *coord = tree->coord_table[index];
  90.                 printf("(");
  91.                 for (j = 0; j dim; j++) {
  93.                         if (j != tree->dim - 1) {
  95.                                 printf("%.2f,", coord[j]);
  96.                         } else {
  98.                                 printf("%.2f)\n", coord[j]);
  99.                         }
  100.                 }
  101.         }
  102. }
  104. static void coord_dump_by_indexes(struct kdtree *tree, long low, long high, int r){
  106.         long i;
  107.         printf("r=%d:", r);
  108.         for (i = 0; i <= high; i++) {
  110.                 if (i                         printf("%8s", " ");
  111.                 } else {
  113.                         long index = tree->coord_indexes[i];
  114.                         printf("%8.2f", tree->coord_table[index][r]);
  115.                 }
  116.         }
  117.         printf("\n");
  118. }
  120. static void bubble_sort(struct kdtree *tree, long low, long high, int r){
  122.         long i, flag = high + 1;
  123.         long *indexes = tree->coord_indexes;
  124.         while (flag > 0) {
  126.                 long len = flag;
  127.                 flag = 0;
  128.                 for (i = low + 1; i                         if (D(tree, indexes[i], r) 1], r)) {
  130.                                 swap(indexes + i - 1, indexes + i);
  131.                                 flag = i;
  132.                         }
  133.                 }
  134.         }
  135. }
  137. static void insert_sort(struct kdtree *tree, long low, long high, int r){
  139.         long i, j;
  140.         long *indexes = tree->coord_indexes;
  141.         for (i = low + 1; i <= high; i++) {
  143.                 long tmp_idx = indexes[i];
  144.                 double tmp_value = D(tree, indexes[i], r);
  145.                 j = i - 1;
  146.                 for (; j >= low && D(tree, indexes[j], r) > tmp_value; j--) {
  148.                         indexes[j + 1] = indexes[j];
  149.                 }
  150.                 indexes[j + 1] = tmp_idx;
  151.         }
  152. }
  154. static void quicksort(struct kdtree *tree, long low, long high, int r){
  156.         if (high - low <= 32) {
  158.                 insert_sort(tree, low, high, r);
  159.                 //bubble_sort(tree, low, high, r);
  160.                 return;
  161.         }
  163.         long *indexes = tree->coord_indexes;
  164.         /* median of 3 */
  165.         long mid = low + (high - low) / 2;
  166.         if (D(tree, indexes[low], r) > D(tree, indexes[mid], r)) {
  168.                 swap(indexes + low, indexes + mid);
  169.         }
  170.         if (D(tree, indexes[low], r) > D(tree, indexes[high], r)) {
  172.                 swap(indexes + low, indexes + high);
  173.         }
  174.         if (D(tree, indexes[high], r) > D(tree, indexes[mid], r)) {
  176.                 swap(indexes + high, indexes + mid);
  177.         }
  179.         /* D(indexes[low]) <= D(indexes[high]) <= D(indexes[mid]) */
  180.         double pivot = D(tree, indexes[high], r);
  182.         /* 3-way partition
  183.          * +---------+-----------+---------+-------------+---------+
  184.          * |  pivot  |  <=pivot  |   ?     |  >=pivot    |  pivot  |
  185.          * +---------+-----------+---------+-------------+---------+
  186.          * low     lt             i       j               gt    high
  187.          */
  188.         long i = low - 1;
  189.         long lt = i;
  190.         long j = high;
  191.         long gt = j;
  192.         for (; ;) {
  194.                 while (D(tree, indexes[++i], r)                 while (D(tree, indexes[--j], r) > pivot && j > low) {}
  195.                 if (i >= j) break;
  196.                 swap(indexes + i, indexes + j);
  197.                 if (D(tree, indexes[i], r) == pivot) swap(&indexes[++lt], &indexes[i]);
  198.                 if (D(tree, indexes[j], r) == pivot) swap(&indexes[--gt], &indexes[j]);
  199.         }
  200.         /* i == j or j + 1 == i */
  201.         swap(indexes + i, indexes + high);
  203.         /* Move equal elements to the middle of array */
  204.         long x, y;
  205.         for (x = low, j = i - 1; x <= lt && j > lt; x++, j--) swap(indexes + x, indexes + j);
  206.         for (y = high, i = i + 1; y >= gt && i 
  207.         quicksort(tree, low, j - lt + x - 1, r);
  208.         quicksort(tree, i + y - gt, high, r);
  209. }
  211. static struct kdnode *kdnode_alloc(double *coord, long index, int r){
  213.         struct kdnode *node = malloc(sizeof(*node));
  214.         if (node != NULL) {
  216.                 memset(node, 0, sizeof(*node));
  217.                 node->coord = coord;
  218.                 node->coord_index = index;
  219.                 node->r = r;
  220.         }
  221.         return node;
  222. }
  224. static void kdnode_free(struct kdnode *node){
  226.         free(node);
  227. }
  229. static int coord_cmp(double *c1, double *c2, int dim){
  231.         int i;
  232.         double ret;
  233.         for (i = 0; i                 ret = *c1++ - *c2++;
  234.                 if (fabs(ret) >= DBL_EPSILON) {
  236.                         return ret > 0 ? 1 : -1;
  237.                 }
  238.         }
  240.         if (fabs(ret)                 return 0;
  241.         } else {
  243.                 return ret > 0 ? 1 : -1;
  244.         }
  245. }
  247. static void knn_list_add(struct kdtree *tree, struct kdnode *node, double distance){
  249.         if (node == NULL) return;
  251.         struct knn_list *head = &tree->knn_list_head;
  252.         struct knn_list *p = head->prev;
  253.         if (tree->knn_num == 1) {
  255.                 if (p->distance > distance) {
  257.                         p = p->prev;
  258.                 }
  259.         } else {
  261.                 while (p != head && p->distance > distance) {
  263.                         p = p->prev;
  264.                 }
  265.         }
  267.         if (p == head || coord_cmp(p->node->coord, node->coord, tree->dim)) {
  269.                 struct knn_list *log = malloc(sizeof(*log));
  270.                 if (log != NULL) {
  272.                         log->node = node;
  273.                         log->distance = distance;
  274.                         log->prev = p;
  275.                         log->next = p->next;
  276.                         p->next->prev = log;
  277.                         p->next = log;
  278.                         tree->knn_num++;
  279.                 }
  280.         }
  281. }
  283. static void knn_list_adjust(struct kdtree *tree, struct kdnode *node, double distance){
  285.         if (node == NULL) return;
  287.         struct knn_list *head = &tree->knn_list_head;
  288.         struct knn_list *p = head->prev;
  289.         if (tree->knn_num == 1) {
  291.                 if (p->distance > distance) {
  293.                         p = p->prev;
  294.                 }
  295.         } else {
  297.                 while (p != head && p->distance > distance) {
  299.                         p = p->prev;
  300.                 }
  301.         }
  303.         if (p == head || coord_cmp(p->node->coord, node->coord, tree->dim)) {
  305.                 struct knn_list *log = head->prev;
  306.                 /* Replace the original max one */
  307.                 log->node = node;
  308.                 log->distance = distance;
  309.                 /* Remove from the max position */
  310.                 head->prev = log->prev;
  311.                 log->prev->next = head;
  312.                 /* insert as a new one */
  313.                 log->prev = p;
  314.                 log->next = p->next;
  315.                 p->next->prev = log;
  316.                 p->next = log;
  317.         }
  318. }
  320. static void knn_list_clear(struct kdtree *tree){
  322.         struct knn_list *head = &tree->knn_list_head;
  323.         struct knn_list *p = head->next;
  324.         while (p != head) {
  326.                 struct knn_list *prev = p;
  327.                 p = p->next;
  328.                 free(prev);
  329.         }
  330.         tree->knn_num = 0;
  331. }
  333. static void resize(struct kdtree *tree){
  335.         tree->capacity *= 2;
  336.         tree->coords = realloc(tree->coords, tree->dim * sizeof(double) * tree->capacity);
  337.         tree->coord_table = realloc(tree->coord_table, sizeof(double *) * tree->capacity);
  338.         tree->coord_indexes = realloc(tree->coord_indexes, sizeof(long) * tree->capacity);
  339.         tree->coord_deleted = realloc(tree->coord_deleted, sizeof(char) * tree->capacity);
  340.         tree->coord_passed = realloc(tree->coord_passed, sizeof(char) * tree->capacity);
  341.         coord_table_reset(tree);
  342.         coord_index_reset(tree);
  343.         coord_deleted_reset(tree);
  344.         coord_passed_reset(tree);
  345. }
  347. static void kdnode_dump(struct kdnode *node, int dim){
  349.         int i;
  350.         if (node->coord != NULL) {
  352.                 printf("(");
  353.                 for (i = 0; i                         if (i != dim - 1) {
  355.                                 printf("%.2f,", node->coord[i]);
  356.                         } else {
  358.                                 printf("%.2f)\n", node->coord[i]);
  359.                         }
  360.                 }
  361.         } else {
  363.                 printf("(none)\n");
  364.         }
  365. }
  367. void kdtree_insert(struct kdtree *tree, double *coord){
  369.         if (tree->count + 1 > tree->capacity) {
  371.                 resize(tree);
  372.         }
  373.         memcpy(tree->coord_table[tree->count++], coord, tree->dim * sizeof(double));
  374. }
  376. static void knn_pickup(struct kdtree *tree, struct kdnode *node, double *target, int k){
  378.         double dist = distance(node->coord, target, tree->dim);
  379.         if (tree->knn_num                 knn_list_add(tree, node, dist);
  380.         } else {
  382.                 if (dist                         knn_list_adjust(tree, node, dist);
  383.                 } else if (fabs(dist - knn_max(tree))                         knn_list_add(tree, node, dist);
  384.                 }
  385.         }
  386. }
  388. static void kdtree_search_recursive(struct kdtree *tree, struct kdnode *node, double *target, int k, int *pickup){
  390.         if (node == NULL || kdnode_passed(tree, node)) {
  392.                 return;
  393.         }
  395.         int r = node->r;
  396.         if (!knn_search_on(tree, k, node->coord[r], target[r])) {
  398.                 return;
  399.         }
  401.         if (*pickup) {
  403.                 tree->coord_passed[node->coord_index] = 1;
  404.                 knn_pickup(tree, node, target, k);
  405.                 kdtree_search_recursive(tree, node->left, target, k, pickup);
  406.                 kdtree_search_recursive(tree, node->right, target, k, pickup);
  407.         } else {
  409.                 if (is_leaf(node)) {
  411.                         *pickup = 1;
  412.                 } else {
  414.                         if (target[r] <= node->coord[r]) {
  416.                                 kdtree_search_recursive(tree, node->left, target, k, pickup);
  417.                                 kdtree_search_recursive(tree, node->right, target, k, pickup);
  418.                         } else {
  420.                                 kdtree_search_recursive(tree, node->right, target, k, pickup);
  421.                                 kdtree_search_recursive(tree, node->left, target, k, pickup);
  422.                         }
  423.                 }
  424.                 /* back track and pick up  */
  425.                 if (*pickup) {
  427.                         tree->coord_passed[node->coord_index] = 1;
  428.                         knn_pickup(tree, node, target, k);
  429.                 }
  430.         }
  431. }
  433. void kdtree_knn_search(struct kdtree *tree, double *target, int k){
  435.         if (k > 0) {
  437.                 int pickup = 0;
  438.                 kdtree_search_recursive(tree, tree->root, target, k, &pickup);
  439.         }
  440. }
  442. void kdtree_delete(struct kdtree *tree, double *coord){
  444.         int r = 0;
  445.         struct kdnode *node = tree->root;
  446.         struct kdnode *parent = node;
  448.         while (node != NULL) {
  450.                 if (node->coord == NULL) {
  452.                         if (parent->right->coord == NULL) {
  454.                                 break;
  455.                         } else {
  457.                                 node = parent->right;
  458.                                 continue;
  459.                         }
  460.                 }
  462.                 if (coord[r] coord[r]) {
  464.                         parent = node;
  465.                         node = node->left;
  466.                 } else if (coord[r] > node->coord[r]) {
  468.                         parent = node;
  469.                         node = node->right;
  470.                 } else {
  472.                         int ret = coord_cmp(coord, node->coord, tree->dim);
  473.                         if (ret 0) {
  475.                                 parent = node;
  476.                                 node = node->left;
  477.                         } else if (ret > 0) {
  479.                                 parent = node;
  480.                                 node = node->right;
  481.                         } else {
  483.                                 node->coord = NULL;
  484.                                 break;
  485.                         }
  486.                 }
  487.                 r = (r + 1) % tree->dim;
  488.         }
  489. }
  491. static void kdnode_build(struct kdtree *tree, struct kdnode **nptr, int r, long low, long high){
  493.         if (low == high) {
  495.                 long index = tree->coord_indexes[low];
  496.                 *nptr = kdnode_alloc(tree->coord_table[index], index, r);
  497.         } else if (low                 /* Sort and fetch the median to build a balanced BST */
  498.                 quicksort(tree, low, high, r);
  499.                 long median = low + (high - low) / 2;
  500.                 long median_index = tree->coord_indexes[median];
  501.                 struct kdnode *node = *nptr = kdnode_alloc(tree->coord_table[median_index], median_index, r);
  502.                 r = (r + 1) % tree->dim;
  503.                 kdnode_build(tree, &node->left, r, low, median - 1);
  504.                 kdnode_build(tree, &node->right, r, median + 1, high);
  505.         }
  506. }
  508. static void kdtree_build(struct kdtree *tree){
  510.         kdnode_build(tree, &tree->root, 0, 0, tree->count - 1);
  511. }
  513. void kdtree_rebuild(struct kdtree *tree){
  515.         long i, j;
  516.         size_t size_of_coord = tree->dim * sizeof(double);
  517.         for (i = 0, j = 0; j count; i++, j++) {
  519.                 while (j count && tree->coord_deleted[j]) {
  521.                         j++;
  522.                 }
  523.                 if (i != j && j count) {
  525.                         memcpy(tree->coord_table[i], tree->coord_table[j], size_of_coord);
  526.                         tree->coord_deleted[i] = 0;
  527.                 }
  528.         }
  529.         tree->count = i;
  530.         coord_index_reset(tree);
  531.         kdtree_build(tree);
  532. }
  534. struct kdtree *kdtree_init(int dim){
  536.         struct kdtree *tree = malloc(sizeof(*tree));
  537.         if (tree != NULL) {
  539.                 tree->root = NULL;
  540.                 tree->dim = dim;
  541.                 tree->count = 0;
  542.                 tree->capacity = 65536;
  543.                 tree->knn_list_head.next = &tree->knn_list_head;
  544.                 tree->knn_list_head.prev = &tree->knn_list_head;
  545.                 tree->knn_list_head.node = NULL;
  546.                 tree->knn_list_head.distance = 0;
  547.                 tree->knn_num = 0;
  548.                 tree->coords = malloc(dim * sizeof(double) * tree->capacity);
  549.                 tree->coord_table = malloc(sizeof(double *) * tree->capacity);
  550.                 tree->coord_indexes = malloc(sizeof(long) * tree->capacity);
  551.                 tree->coord_deleted = malloc(sizeof(char) * tree->capacity);
  552.                 tree->coord_passed = malloc(sizeof(char) * tree->capacity);
  553.                 coord_index_reset(tree);
  554.                 coord_table_reset(tree);
  555.                 coord_deleted_reset(tree);
  556.                 coord_passed_reset(tree);
  557.         }
  558.         return tree;
  559. }
  561. static void kdnode_destroy(struct kdnode *node){
  563.         if (node == NULL) return;
  564.         kdnode_destroy(node->left);
  565.         kdnode_destroy(node->right);
  566.         kdnode_free(node);
  567. }
  569. void kdtree_destroy(struct kdtree *tree){
  571.         kdnode_destroy(tree->root);
  572.         knn_list_clear(tree);
  573.         free(tree->coords);
  574.         free(tree->coord_table);
  575.         free(tree->coord_indexes);
  576.         free(tree->coord_deleted);
  577.         free(tree->coord_passed);
  578.         free(tree);
  579. }
  581. #define _KDTREE_DEBUG
  583. #ifdef _KDTREE_DEBUG
  584. struct kdnode_backlog {
  586.         struct kdnode *node;
  587.         int next_sub_idx;
  588. };
  590. void kdtree_dump(struct kdtree *tree){
  592.         int level = 0;
  593.         struct kdnode *node = tree->root;
  594.         struct kdnode_backlog nbl, *p_nbl = NULL;
  595.         struct kdnode_backlog nbl_stack[KDTREE_MAX_LEVEL];
  596.         struct kdnode_backlog *top = nbl_stack;
  598.         for (; ;) {
  600.                 if (node != NULL) {
  602.                         /* Fetch the pop-up backlogged node's sub-id.
  603.                          * If not backlogged, fetch the first sub-id. */
  604.                         int sub_idx = p_nbl != NULL ? p_nbl->next_sub_idx : KDTREE_RIGHT_INDEX;
  606.                         /* Backlog should be left in next loop */
  607.                         p_nbl = NULL;
  609.                         /* Backlog the node */
  610.                         if (is_leaf(node) || sub_idx == KDTREE_LEFT_INDEX) {
  612.                                 top->node = NULL;
  613.                                 top->next_sub_idx = KDTREE_RIGHT_INDEX;
  614.                         } else {
  616.                                 top->node = node;
  617.                                 top->next_sub_idx = KDTREE_LEFT_INDEX;
  618.                         }
  619.                         top++;
  620.                         level++;
  622.                         /* Draw lines as long as sub_idx is the first one */
  623.                         if (sub_idx == KDTREE_RIGHT_INDEX) {
  625.                                 int i;
  626.                                 for (i = 1; i                                         if (i == level - 1) {
  628.                                                 printf("%-8s", "+-------");
  629.                                         } else {
  631.                                                 if (nbl_stack[i - 1].node != NULL) {
  633.                                                         printf("%-8s", "|");
  634.                                                 } else {
  636.                                                         printf("%-8s", " ");
  637.                                                 }
  638.                                         }
  639.                                 }
  640.                                 kdnode_dump(node, tree->dim);
  641.                         }
  643.                         /* Move down according to sub_idx */
  644.                         node = sub_idx == KDTREE_LEFT_INDEX ? node->left : node->right;
  645.                 } else {
  647.                         p_nbl = top == nbl_stack ? NULL : --top;
  648.                         if (p_nbl == NULL) {
  650.                                 /* End of traversal */
  651.                                 break;
  652.                         }
  653.                         node = p_nbl->node;
  654.                         level--;
  655.                 }
  656.         }
  657. }
  658. #endif

python

  1. class kdtree(object):
  3.     # 创建 kdtree
  4.     # point_list 是一个 list 的 pair，pair[0] 是一 tuple 的特征，pair[1] 是类别
  5.     def __init__(self, point_list, depth=0, root=None):
  7.         if len(point_list)>0:
  9.             # 轮换按照树深度选择坐标轴
  10.             k = len(point_list[0][0])
  11.             axis = depth % k
  13.             # 选中位线，切
  14.             point_list.sort(key=lambda x:x[0][axis])
  15.             median = len(point_list) // 2
  17.             self.axis = axis
  18.             self.root = root
  19.             self.size = len(point_list)
  21.             # 造节点
  22.             self.node = point_list[median]
  23.             # 递归造左枝和右枝
  24.             if len(point_list[:median])>0:
  25.                 self.left = kdtree(point_list[:median], depth+1, self)
  26.             else:
  27.                 self.left = None
  28.             if len(point_list[median+1:])>0:
  29.                 self.right = kdtree(point_list[median+1:], depth+1, self)
  30.             else:
  31.                 self.right = None
  32.             # 记录是按哪个方向切的还有树根
  34.         else:
  35.             return None
  37.     # 在树上加一点
  38.     def insert(self, point):
  39.         self.size += 1
  41.         # 分析是左还是右，递归加在叶子上
  42.         if point[0][self.axis]0][self.axis]:if self.left!=None:
  43.                 self.left.insert(point)else:
  44.                 self.left = kdtree([point], self.axis+1, self)else:if self.right!=None:
  45.                 self.right.insert(point)else:
  46.                 self.right = kdtree([point], self.axis+1, self)# 输入一点# 按切分寻找叶子def find_leaf(self, point):if self.left==None and self.right==None:return selfelif self.left==None:return self.right.find_leaf(point)elif self.right==None:return self.left.find_leaf(point)elif point[self.axis]0][self.axis]:return self.left.find_leaf(point)else:return self.right.find_leaf(point)# 查找最近的 k 个点，复杂度 O(DlogN)，D是维度，N是树的大小# 输入一点、一距离函数、一k。距离函数默认是 L_2def knearest(self, point, k=1, dist=lambda x,y: sum(map(lambda u,v:(u-v)**2,x,y))):# 往下戳到最底叶
  47.         leaf = self.find_leaf(point)# 从叶子网上爬return leaf.k_down_up(point, k, dist, result=[], stop=self, visited=None)# 从下往上爬函数，stop是到哪里去，visited是从哪里来def k_down_up(self, point,k, dist, result=[],stop=None, visited=None):# 选最长距离if result==[]:
  48.             max_dist = 0else:
  49.             max_dist = max([x[1] for x in result])
  50.         other_result=[]# 如果离分界线的距离小于现有最大距离，或者数据点不够，就从另一边的树根开始刨if (self.left==visited and self.node[0][self.axis]-point[self.axis]and self.right!=None)\or (len(result)and self.left==visited and self.right!=None):
  51.             other_result=self.right.knearest(point,k, dist)if (self.right==visited and point[self.axis]-self.node[0][self.axis]and self.left!=None)\or (len(result)and self.right==visited and self.left!=None):
  52.             other_result=self.left.knearest(point, k, dist)# 刨出来的点放一起，选前 k 个
  53.         result.append((self.node, dist(point, self.node[0])))
  54.         result = sorted(result+other_result, key=lambda pair: pair[1])[:k]# 到停点就返回结果if self==stop:return result# 没有就带着现有结果接着往上爬else:return self.root.k_down_up(point,k,  dist, result, stop, self)# 输入 特征、类别、k、距离函数# 返回这个点属于该类别的概率def kNN_prob(self, point, label, k, dist=lambda x,y: sum(map(lambda u,v:(u-v)**2,x,y))):
  55.         nearests = self.knearest(point,  k, dist)return float(len([pair for pair in nearests if pair[0][1]==label]))/float(len(nearests))# 输入 特征、k、距离函数# 返回该点概率最大的类别以及相对应的概率def kNN(self, point, k, dist=lambda x,y: sum(map(lambda u,v:(u-v)**2,x,y))):
  56.         nearests = self.knearest(point, k , dist)
  57.         statistics = {}for data in nearests:
  58.             label = data[0][1]if label not in statistics: 
  59.                 statistics[label] = 1else:
  60.                 statistics[label] += 1
  61.         max_label = max(statistics.iteritems(), key=operator.itemgetter(1))[0]return max_label, float(statistics[max_label])/float(len(nearests))

发表评论

表情：
评论列表 （有 0 条评论，328人围观）

还没有评论，来说两句吧...

相关阅读

    相关 K近邻算法

    一、kNN算法的工作原理 官方解释：存在一个样本数据集，也称作训练样本集，并且样本中每个数据都存在标签，即我们知道样本集中每一数据与所属分类的对应关系，输入没有标签的新数据后

    水深无声水深无声/ 0 赞/ 152 阅读

    相关 k近邻算法matlab实现_k近邻算法

    k 近邻法 (k-NN) 是一种基于实例的学习方法，无法转化为对参数空间的搜索问题(参数最优化 问题)。它的特点是对特征空间进行搜索。除了k近邻法，本章还对以下几个问题进行较深

    Dear 丶Dear 丶/ 0 赞/ 329 阅读

    相关 k-近邻算法

    从今天开始，与大家分享我学习《Machine Learning In Action》这本书的笔记与心得。我会将源码加以详细的注释，这是我自己学习的一个过程，也是想通过这种方式帮

    淡淡的烟草味﹌淡淡的烟草味﹌/ 0 赞/ 281 阅读

    相关 K近邻分类算法

    K最近邻(k-Nearest Neighbor，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空间中的k个最相似

    亦凉亦凉/ 0 赞/ 336 阅读

    相关 K-近邻算法(KNN)

         拜读大神的系列教程，大神好像姓崔(猜测)，大神根据《机器学习实战》来讲解，讲的很清楚，读了大神的博客后，我也把我自己吸收的写下来，可能有很多错误之处，希望拍砖(拍轻点

    快来打我*快来打我*/ 0 赞/ 434 阅读

    相关 knn（k近邻算法）

    一、什么是knn算法 knn算法实际上是利用训练数据集对特征向量空间进行划分，并作为其分类的模型。其输入是实例的特征向量，输出为实例的类别。寻找最近的k个数据，推测新数据...

    灰太狼灰太狼/ 0 赞/ 761 阅读