方案中列表的最近邻和多数

Question

我正在尝试定义一个过程knn，该过程采用正整数k、房屋的坐标、距离函数和训练数据，并返回训练数据中给定房屋的(至多)k个最近邻居的列表。返回的列表应该按照与给定房屋的距离按非降序排列。

训练数据由以下方式提供：

(define training-data
   '((d (1 8)) (d (2 9)) (d (8 10)) (d (4 2)) (r (1 3)) (r (2 1)) (r (4 8)) (r (6 4))
      (d (7 3)) (r (1 5)) (d (1 9)) (d (6 2)) (r (10 9)) (d (7 7))
      (d (5 11)) (r (1 1)) (r (0 9)) (r (12 12)) (r (20 30))))

我使用的距离函数是taxicab-distance，它接受两个点，并返回它们坐标的绝对差值之和。它由以下内容提供：

(define (taxicab-distance ls1 ls2)
   (+ (abs (- (car ls1) (cadr ls1))) (abs(- (car ls2) (cadr ls2)))))

我想要做的一个例子是：

~(knn 3 '(3 8)出租车-距离训练-数据)

-> ((r (4 8)) (d (1 8)) (d (2 9)

因此，我知道它将开始如下：

(define (knn k point distance data)

我知道我必须计算每个点的距离，所以我需要计算训练数据的caadr，然后重复列表的cdr来获得每个值，但是如何将其与原始值进行比较，然后返回整个嵌套列表，这就是我迷路的地方。

最后，我还想定义一个名为多数的函数，该函数接受一个非空的标签数据列表和一个非空的标签列表，并返回出现频率最高的标签。如果有多个这样的标签，那么你的程序返回哪一个都无关紧要。

对于多数，它将需要两个参数，一个数据集，以及它正在查找的内容的列表。我知道对于训练数据，它必须查看数据的caar，并对cdr执行相同的操作，然后计算每个d和r。

Answer 1

(import (rnrs)
        (rnrs sorting)
        (only (srfi :1) take))

(define (knn k point distance data)
  ;; Is p1 is closer to point than p2?
  (define (data-distance-point< p1 p2)
    (< (distance point (cadr p1))
       (distance point (cadr p2))))

  ;; take k elements of the coordinates 
  ;; with the shortest path to point   
  (take (list-sort data-distance-point< data) k))

(knn 3 '(3 8) point-distance training-data) ; ==> ((r (4 8)) (d (2 9)) (d (1 8)))

我没有使用你的距离函数，因为(0,0)->(0,10)比(0,5)->(0,10)的距离短，这没有任何意义。我的结果是，如果你使用毕达哥拉斯来计算距离，你会得到什么。

point与data的元素具有不同的结构，这一事实很奇怪。我不希望在data-distance-point<中有cadr。