【机器学习】KNN（k-Nearest Neighbor）算法

落日映苍穹つ 2022-07-12 15:22 139阅读 0赞

K近邻（k-Nearest Neighbor， 简称KNN）算法是一种非常简单的机器学习监督算法。它的主要思想是：给定一个测试数据，如果离它最近的K个训练数据大多都属于某一个类别，则认为该测试数据也属于这个类别。以下图为例，图中的绿色点表示测试数据，现在我们需要判断这个点应该是红色三角形还是蓝色正方形。按照上述思想，如果K取3，则离绿色点最近的点中有两个是红色三角形，一个是蓝色正方形，因此KNN判断绿色点为红色三角形。  
![KNN例子][KNN]

可见，KNN的思想确实十分简单，实现也很容易。但是我们思考一下为什么可以判断两个数据之间的“远近”？回到现实中的例子，当你判断是一张桌子理离你近，还是椅子离你近时，我们的衡量标准其实就是看桌子和椅子和我们的距离。回想一下：计算一条直线上两点的距离，我们可以直接将两点的坐标值相减后取绝对值得到；计算一个平面内两个点的距离，我们可以将点的各个坐标值带入欧式距离计算公式得到距离；同样地，计算三维空间中点的距离，也是将点的各个坐标值带入欧式距离计算公式得到。那么推广到d维空间中的点，我们也可以点的各个坐标值带入欧式距离计算公式得到。但是，各个点的坐标是如何确定的呢？其实就是我们引入了一个空间坐标系，d维空间中的一个点其实就是一个向量，这个向量的各个数值就对应了其在各个维度坐标轴上的取值。其实我们也可以将机器学习中的每个样本看作是d维空间中的一个点，这样我们就可以采用空间中的距离计算方法来衡量样本之间的距离，因此才会有所谓的“远近”。也就是说，KNN将每一个数据都看作是d维空间中的一个点，在这个空间中采用了坐标系来描述这个点的位置，再通过某种距离计算公式来表示这两个点之间的距离。

## KNN分类 ##

给定一个d维的测试数据 x∈Rd，KNN对于x的分类过程如下：

*  计算x与每一个训练数据之间的距离
 *  对计算得到的距离按照从小到大的顺序排序
 *  找到距离最小的k个训练数据，采用多数投票的方式得到k个训练数据中出现次数最多的类标签，将x判定为这个类标签。
    
    使用pyhton实现KNN如下：
    
        def knn_cla(train_dat, train_label, test_dat, k = 1):
        '''
          k-neighbour nearest
        '''
        ntrain = train_dat.shape[0]
        pred_label = list()
        for i, test_item in enumerate(test_dat):
            dis = []
            for train_item in train_dat:
                dis.append(distance.euclidean(test_item, train_item))
            nearest_ind = range(ntrain)
            sorted(nearest_ind, key=lambda x:dis[x])
            nearest_label = [train_label[nearest_ind[x]] for x in range(k)]
            pred_label.append(Counter(nearest_label).most_common()[0][0])
        
        return np.array(pred_label)

## KNN 回归 ##

在分类任务中，KNN采取多数投票的方法判定测试数据的类别。在回归任务中可以采取多种方法判定。“平均法”将找出的K个最近测试样本的实值输出的平均值作为预测结果；“加权平均”将权重的倒数作为K个样本的权重值，从而计算加权平均，距离越近的样本其权重越大。

def knn_reg(train_dat, train_prob, test_dat, k = 1):
        '''
          k-neighbour nearest
        '''
        ntrain = train_dat.shape[0]
        ntest = test_dat.shape[0]
        pred_prob = np.zeros((ntest, 6)) 
        for i, test_item in enumerate(test_dat):
            dis = []
            for train_item in train_dat:
                dis.append(distance.euclidean(test_item, train_item))
            nearest_ind = list(range(ntrain))
            nearest_ind = sorted(nearest_ind, key=lambda x:dis[x])
            weight = np.array(list(map(lambda x: 1/(x+0.001), [dis[x] for x in range(k)]))) # avoid divide by 0 error
            weight = weight / weight.sum(keepdims=True) # noralize weight
            for x in range(k):
                pred_prob[i] += (train_prob[nearest_ind[x]] * weight[x])
    
        return (pred_prob / pred_prob.sum(axis=1, keepdims=True))

## 距离计算方法 ##

衡量两个样本之间距离除了可以使用欧式距离以外，还可以采用闵可夫斯基距离， 曼哈顿距离，切比雪夫距离，余弦距离等等。

## K的取值 ##

k值的不同预测结果也会很不一样，因此选取一个合适的k值是很有必要的。最简单的就是k=1，即只看与测试数据最近的那个训练数据。但是很有可能比这个训练数居远一点点的那些数据，大多数是另外一个分类标签，这样就会导致预测错误。最复杂的就是k=N，即k等于训练样本的总个数。这虽然考虑了所有的文本，大大提高了预测结果的可靠性，但是会带来大量的计算，降低算法的速度。而且，训练数据只是无穷数据中的一部分，训练数据集中样本的标签不能代表所有的数据类别标签分布。还可以将k取不同的值，选定训练错误率最低的k值。但是这种方法同样会花费大量的时间。 一个比较合理的取值是k=(√N)，这样不仅可以提高预测准确率，还可以将时间控制在一个比较合理的范围。

[KNN]: /images/20220709/39f609cea2e44bb0a813737f715595c7.png