K近邻法

文章目录

1.概述
2.模型介绍
3.模型改进
4.算法实现

概述

k-近邻算法，是一种容易理解的监督学习算法，其工作机制简单，给定测试样本，基于某种距离度量找出训练集中与其最接近的k个值，然后基于这k个邻居，在分类任务中，判别为某个类别的可以使用投票法，观察其邻居的类别，如果邻居属于a类多，属于b类的少，那么这个点就属于a类。
与一般的学习方法不同的是，knn是一种懒惰学习，它没有显式的训练过程，相对于的，大部分学习方法为急切学习，即一拿到数据，就把数据仍进去模型中训练，然后得到训练好的模型就把训练数据丢弃，用模型预测新的数据。而knn这种懒惰学习，学习过程滞后，有了测试数据再进行学习。
knn算法可以用来做分类，其
优点是精度高，对异常值不敏感，无数据输入假定
缺点是计算复杂度高，空间复杂度高。

knn分类示意图

模型介绍

当训练集，距离度量，k值，分类规则确定后，对于每一个输入需要预测的类，它所属于的类是确定的。
下面分别介绍距离度量，k值的选取，分类规则
距离度量
这里介绍一般的距离度量方法
设n维空间中有两点坐标x, y，p为常数 ,
闵可夫斯基距离：

当p = 2 时，为欧式距离：

当p = 1时，为曼哈顿距离：

当p ，为切比雪夫距离：

模型改进

实现KNN时，主要是考虑的问题时如何对训练数据进行快速K近邻搜索，如果特征空间的维数大或者训练数据容量大时，那么数据存储就是一个大问题。KNN最简单的实现方法是线性扫描，这时当数据集很大，计算就非常地耗时。为了提高这种搜索效率，使用特殊地结构进行存储训练数据——kd树（kd tree）。kd树是一种对k维空间中的点进行存储以便于对其进行快速搜索的树形数据结构。实质上，kd树是一种二叉树，表示对k维空间的一个划分。
具体学习后回来补充

算法实现

给定一个二维空间的数据集T={正实例：(5,4),(9,6),(4,7)；负实例：(2,3), (8,1),(7,2)}，基于欧氏距离，找到数据点S（5,3）的最近邻（k=1），并对S点进行分类预测。

用“线性扫描”算法自编程实现

image.png

import numpy as np

class KNN():
    def __init__(self ,dataSet, labels, k = 1):
        self.k = k
        self.dataSet = dataSet
        self.labels = labels
    
    def predict(self, x):
        # 欧式距离计算
        dataSize = self.dataSet.shape[0]
        diffMat = np.tile(x,(dataSize,1)) - self.dataSet
        sqDiffMat = diffMat ** 2
        sqDistances = sqDiffMat.sum(axis = 1)
        distances = sqDistances ** 0.5
        
        #按照值从小到大，索引排序
        sortedDistIndecies = distances.argsort()
        
        # 字典存储到哪个类的投票数
        classCount = {}
        for i in range(self.k):
            voteIlabel = self.labels[sortedDistIndecies[i]]
            classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
        return list(classCount.keys())[list(classCount.values()).index(max(classCount.values()))]

if __name__ == 'main' :
    group = np.array([(5,4),(9,6),(4,7),(2,3), (8,1),(7,2)])
    labels = [1,1,1,2,2,2]
    s = [5,3]
    knn = KNN(group,labels)
    result = knn.predict(s)
    print(result)