使用R实现具有不同距离度量的KNN

Question

我正在研究数据集，以便比较不同距离指标的影响。我正在使用KNN算法。

R中的KNN算法默认使用欧几里德距离。所以我写了自己的。我想找到最近邻居和目标之间正确的类别标签匹配的数量。

我首先准备了数据。然后我调用了数据（wdbc_n），我选择了K = 1。我用欧几里得距离作为测试。

library(philentropy)
knn <- function(xmat, k,method){
  n <- nrow(xmat)
  if (n <= k) stop("k can not be more than n-1")
  neigh <- matrix(0, nrow = n, ncol = k)
  for(i in 1:n) {
    ddist<- distance(xmat, method)  
    neigh[i, ] <- order(ddist)[2:(k + 1)]
  }
  return(neigh)
}
wdbc_nn <-knn(wdbc_n ,1,method="euclidean")

希望得到类似的结果（“关于高维空间中距离度量的惊人行为”）（https://bib.dbvis.de/uploadedFiles/155.pdf，第431页，表3）。

我的问题是

我对这些代码是对还是错？

任何指导我的建议或参考将受到高度赞赏。

编辑

我的数据（乳腺癌 - 威斯康星）（wdbc）维度是

569  32

规范化并删除id和目标列后，维度为

dim(wdbc_n)
569  30

列车和测试拆分由。给出

wdbc_train<-wdbc_n[1:469,]
wdbc_test<-wdbc_n[470:569,]

Answer 1

我对这些代码是对还是错？

你的代码错了。

在我最近的PC上每次调用距离函数大约需要3秒，所以我只对k = 3做了前30行，并注意到neigh矩阵的每一行都是相同的。这是为什么？看看这一行：

ddist<- distance(xmat, method)  

每个循环在距离函数处馈送整个xmat矩阵，然后仅使用结果矩阵中的第一行。这计算训练集行之间的距离，并且这样做n次，丢弃除第一行之外的每一行。这不是你想要做的。 knn算法应该为测试集中的每一行计算训练集中每行的距离。

我们来看看距离函数的文档：

distance（x，method =“euclidean”，p = NULL，test.na = TRUE，unit =“log”，est.prob = NULL）

x数字data.frame或矩阵（存储概率向量）或数字data.frame或矩阵存储计数（如果指定了est.prob）。

(...)

如果nrow（x）= 2：单个距离值。在nrow（x）> 2的情况下：距离矩阵存储所有成对概率向量比较的距离值。

在您的特定情况下（knn分类），您想要使用2行版本。

最后一件事：你使用了order，它将返回ddist向量中k个最大距离的位置。我想你想要的是距离本身，所以你需要使用排序而不是顺序。

根据您的代码和Lantz（2013）中您的代码似乎基于的示例，这是一个完整的工作解决方案。我冒昧地添加几行来制作一个独立的程序。

独立工作解决方案

library(philentropy)
normalize <- function(x) {
 return ((x - min(x)) / (max(x) - min(x)))
}

knn <- function(train, test, k, method){
  n.test <- nrow(test)
  n.train <- nrow(train)
  if (n.train + n.test <= k) stop("k can not be more than n-1")
  neigh <- matrix(0, nrow = n.test, ncol = k) 
  ddist <- NULL
  for(i in 1:n.test) {
    for(j in 1:n.train) {
      xmat <- rbind(test[i,], train[j,]) #we make a 2 row matrix combining the current test and train rows
      ddist[j] <- distance(as.data.frame(xmat), method, k)  #then we calculate the distance and append it to the ddist vector.
    }
    neigh[i, ] <- sort(ddist)[2:(k + 1)] 
  }
  return(neigh)
}

wbcd <- read.csv("https://resources.oreilly.com/examples/9781784393908/raw/ac9fe41596dd42fc3877cfa8ed410dd346c43548/Machine%20Learning%20with%20R,%20Second%20Edition_Code/Chapter%2003/wisc_bc_data.csv")
rownames(wbcd) <- wbcd$id
wbcd$id <- NULL
wbcd_n <- as.data.frame(lapply(wbcd[2:31], normalize))

wbcd_train<-wbcd_n[1:469,]
wbcd_test<-wbcd_n[470:549,]
wbcd_nn <-knn(wbcd_train, wbcd_test ,3, method="euclidean")

请注意，由于对距离函数的多次调用（100次469次），此解决方案可能会很慢。但是，由于我们一次仅向距离函数提供2行，因此可以使执行时间易于管理。

现在这样做吗？

使用自定义knn函数的两个第一个测试行：

          [,1]      [,2]      [,3]
[1,] 0.3887346 0.4051762 0.4397497
[2,] 0.2518766 0.2758161 0.2790369

让我们与FNN包中的等效函数进行比较：

library(FNN)
alt.class <- get.knnx(wbcd_train, wbcd_test, k=3, algorithm = "brute")
alt.class$nn.dist

          [,1]      [,2]      [,3]
[1,] 0.3815984 0.3887346 0.4051762
[2,] 0.2392102 0.2518766 0.2758161

结论：不要太破旧。