KNN算法又称为k最邻近算法（k-Nearest Neighbour），是一种出现较早且原理比较简单的机器学习算法。其基本思想就是根据距离待分类数据A最近的k个样本数据的分类来预测A可能属于的类别。基本的计算步骤如下：
计算待分类数据与样本集中每一个样本之间的距离（欧式距离、马氏距离等）；找出距离最近的k个样本；观测这k个样本的分类情况；将出现次数最多的类别作为待分类数据的类别。KNN算法的优点是原理简单，易于实现，在多分类问题中能取得较好的结果；缺点是计算量较大，需要计算待测数据与每一个样本数据的距离，而且容易受到样本分布的影响，当样本不平衡时很容易产生错误分类。
class包中提供了KNN的相关算法，包括knn，knn1（k取1时的knn），还有改进的算法knn.cv，kknn等函数，调用起来非常方便。本文主要介绍一下如何手工实现最基本的KNN算法。自己实现算法的过程能够加深对算法的理解，同时也能锻炼一下编写代码的能力，是快速提升个人能力的途径之一。下面是详细代码：
library(dplyr) knnDIY <- function(train,test,labels,k){ if(ncol(train)!=ncol(test)) stop("dims of 'test' and 'train' differ") if(nrow(train)!=length(labels)) stop("'train' and 'class' have different lengths") labels <- as.character(labels) classify0 <- function(vec){ diffMat <- matrix(vec,nrow(train),ncol(train),byrow = T) - train distances <- diffMat^2 %>% apply(.,1,sum) %>% sqrt sortedDistIndexes <- order(distances) kMaxDistLabels <- vector(length = k) for(i in 1:k){ kMaxDistLabels[i] <- labels[sortedDistIndexes[i]] } predictLabel <- table(kMaxDistLabels) %>% which.max %>% names return(predictLabel) } allPredict <- apply(test,1,classify0) return(allPredict) } 自定义了一个knnDIY函数，需要传入四个参数，train是训练集，即带分类标签的数据；test为待测试的数据；labels为train的分类标签，k为邻居个数。在函数中又定义了一个classify0的内部函数，该函数的作用是对每一条待分类数据做分类，最后通过apply函数对整个test数据集做分类。这样做的好处是能够简化逻辑思维，更专注于算法过程的实现，同时apply函数的效率也比for循环要高一些。因此主要的算法过程定义在了classify0中。 首先将传入到classify0中的单条数据vec扩充成与train训练集维度相同的矩阵，用byrow参数控制扩充的方向，再与train做减法，得到diffMat。diffMat中的每一行都相当于vec与train训练集中每一条数据做减法的结果（）。这样再对diffMat的每一个元素平方（），按行相加（），再做开方就求出了vec与每一个样本点之间的欧式距离（）。 然后对distances从小到大做排序并返回排序后元素在distances中的序号向量sortedDistIndexes（详见order函数），取sortedDistIndexes的前k个值去labels里查找相应的标签，就得到了k个最近邻居的分类标签。通过table函数对k个邻居的标签做频数统计，求出频数最大的数据，利用names得到分类标签。 将最终得到的标签作为vec数据的分类。利用apply函数对整个test执行classify0函数即可得到所有test的分类标签。
