K近邻法(KNN)

介绍

1． $k$ 近邻法是基本且简单的分类与回归方法。 $k$ 近邻法的基本做法是：对给定的训练实例点和输入实例点，首先确定输入实例点的 $k$ 个最近邻训练实例点，然后利用这 $k$ 个训练实例点的类的多数来预测输入实例点的类。

2． $k$ 近邻模型对应于基于训练数据集对特征空间的一个划分。 $k$ 近邻法中，当训练集、距离度量、 $k$ 值及分类决策规则确定后，其结果唯一确定。

3． $k$ 近邻法三要素：距离度量、 $k$ 值的选择和分类决策规则。常用的距离度量是欧氏距离及更一般的pL距离。 $k$ 值小时， $k$ 近邻模型更复杂； $k$ 值大时， $k$ 近邻模型更简单。 $k$ 值的选择反映了对近似误差与估计误差之间的权衡，通常由交叉验证选择最优的 $k$ 。

常用的分类决策规则是多数表决，对应于经验风险最小化。

4． $k$ 近邻法的实现需要考虑如何快速搜索k个最近邻点。kd树是一种便于对k维空间中的数据进行快速检索的数据结构。kd树是二叉树，表示对 $k$ 维空间的一个划分，其每个结点对应于 $k$ 维空间划分中的一个超矩形区域。利用kd树可以省去对大部分数据点的搜索，从而减少搜索的计算量。

距离度量

设特征空间 $x$ 是 $n$ 维实数向量空间， $x_{i}, x_{j} \in \mathcal{X}$ , $x_{i}=\left(x_{i}^{(1)}, x_{i}^{(2)}, \cdots, x_{i}^{(n)}\right)^{\mathrm{T}}$ , $x_{j}=\left(x_{j}^{(1)}, x_{j}^{(2)}, \cdots, x_{j}^{(n)}\right)^{\mathrm{T}}$ ，则： $x_i$ , $x_j$ 的 $L_p$ 距离定义为:

$L_{p}\left(x_{i}, x_{j}\right)=\left(\sum_{i=1}^{n}\left|x_{i}^{(i)}-x_{j}^{(l)}\right|^{p}\right)^{\frac{1}{p}}$

$p = 1$ 曼哈顿距离
$p = 2$ 欧氏距离
$\infty$ 切比雪夫距离

原生代码实现KNN算法:

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from collections import Counter

#导入iris数据并进行数据预处理
iris = load_iris()
df = pd.DataFrame(iris.data,columns=iris.feature_names)
df['label'] = iris.target
df.columns = ['sepal length', 'sepal width', 'petal length', 'petal width', 'label']

""" 数据可视化展示
plt.scatter(df[:50]['sepal length'], df[:50]['sepal width'], label='0')
plt.scatter(df[50:100]['sepal length'], df[50:100]['sepal width'], label='1')
plt.xlabel('sepal length')
plt.ylabel('sepal width')
plt.legend() """

#分离特征数据和标签数据
data = np.array(df.iloc[:100, [0, 1, -1]])
X, y = data[:,:-1], data[:,-1]
#随机划分训练集和测试集(测试集占比0.2)
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)


"""KNN算法实现"""
class KNN:
    def __init__(self,X_train,y_train,n_neighbors=3,p=2):
        """
        X_train: 训练集的特征数据
        y_train: 训练集的标签数据
        n_neighbors: 对应K的取值,即选取的临近点的数目
        p: 对应距离度量的选择  p=2(欧式距离)
    """
        self.n = n_neighbors
        self.p = p
        self.X_train = X_train
        self.y_train = y_train

    #预测输入实例的类别的函数,X是输入实例点
    def predict(self,X):
        #存储n个 训练实例点的(Lp距离,类别)元组的 列表
        knn_list = []
        #计算 前三个训练实例点 与 输入实例的 Lp距离
        for i in range(self.n):
            """
                np.linalg.norm(x, ord=None, axis=None, keepdims=False)函数说明:
                ---------------------------------------------------------------
                x: 表示矩阵(也可以是一维)
                ord: 计算的范数类型
            """
            #计算p范数,即Lp距离(列表-np.array,结果是np.array)(相减 对应列的元素相减)
            dist = np.linalg.norm(X - self.X_train[i], ord=self.p)
            #空列表增添元组形式 (Lp距离,训练实例点对应的标签数据)
            knn_list.append((dist, self.y_train[i]))

        #从前三个训练实例点之后的实例点开始 到 最后一个训练实例点 继续计算与X输入实例点的Lp距离
        for i in range(self.n, len(self.X_train)):
            #index() 函数用于从列表中找出某个值第一个匹配项的索引位置。
            #寻找knn_list中distance最大的元组的下标
            max_index = knn_list.index(max(knn_list, key=lambda x: x[0]))
            #继续计算Lp距离(列表-np.array,结果是np.array)(相减 对应列的元素相减)
            dist = np.linalg.norm(X - self.X_train[i], ord=self.p)
            #如果已知的最大的元组的distance 大于 上面计算出来的dist,就替换元组
            if knn_list[max_index][0] > dist:
                #替换成distance更小的元组
                knn_list[max_index] = (dist, self.y_train[i])
        #统计,存储类别的列表(其列表长度一直是3,即3个元组)
        knn = [k[-1] for k in knn_list]
        #Counter对象的主要功能为快速计算相同元素的个数
        count_pairs = Counter(knn)  #返回:Counter({1.0: 3})
        #sorted()对所有可迭代的对象进行排序操作(以相同元素的个数进行按升序排序)
        #选取排序后投票最多的类别 (即输入实例点所属的类别)
        max_count = sorted(count_pairs.items(), key=lambda x: x[1])[-1][0]
        #返回输入实例 所属的类别
        return max_count

    #传入测试集,测试模型表现情况(即分类正确的点数的占比)
    def score(self, X_test,y_test):
        #初始化正确分类的点的个数
        right_count = 0
        """
            zip() 函数用于将可迭代的对象作为参数，
            将对象中对应的元素打包成一个个元组，
            然后返回由这些元组组成的列表。
            列表中元组的个数与最短的列表长度一致
            如输入:[1,2] 和 [3,4] 输出:[(1,3),(2,4)]
        """
        #预测 测试集中每个测试输入点的 类别
        for X, y in zip(X_test, y_test):
            label = self.predict(X)
            #如果点正确分类,正确分类的点的个数+1
            if label == y:
                right_count += 1
        #返回被正确分类的点的个数 在测试集所有点中的占比
        return right_count / len(X_test)

#实例化KNN模型算法类对象
clf = KNN(X_train, y_train)
#测试 测试集的表现情况
print(clf.score(X_test, y_test))

#一个测试的 输入实例点
test_point = [6.0, 3.0]
#输入实例点进行预测
print('Test Point: {}'.format(clf.predict(test_point)))

"""数据可视化"""
#绘制iris的散点图
plt.scatter(df[:50]['sepal length'], df[:50]['sepal width'], label='0')
plt.scatter(df[50:100]['sepal length'], df[50:100]['sepal width'], label='1')
#绘制 输入实例点
plt.plot(test_point[0], test_point[1], 'bo', label='test_point')
#x轴,y轴的名称设置
plt.xlabel('sepal length')
plt.ylabel('sepal width')
#显式图例
plt.legend()
#展现图像
plt.show()

效果:
在这里插入图片描述

sklearn框架实现KNN:

from sklearn.neighbors import KNeighborsClassifier
from sklearn.datasets import load_iris
import numpy as np
import pandas as pd
from sklearn.model_selection import train_test_split


#data
iris = load_iris()
df = pd.DataFrame(iris.data,columns=iris.feature_names)
df['label'] = iris.target
df.columns = ['sepal length', 'sepal width', 'petal length', 'petal width', 'label']

#分离特征数据和标签数据
data = np.array(df.iloc[:100, [0, 1, -1]])
X, y = data[:,:-1], data[:,-1]
#随机划分训练集和测试集(测试集占比0.2)
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)

"""
    sklearn.neighbors.KNeighborsClassifier()函数参数说明: 
    ------------------------------------------------------
    n_neighbors: 临近点个数
    p: 距离度量
    algorithm: 近邻算法，可选{'auto', 'ball_tree', 'kd_tree', 'brute'}
    weights: 确定近邻的权重
"""
##实例化knn对象
clf_sk = KNeighborsClassifier()
#传入训练数据,训练模型
clf_sk.fit(X_train, y_train)
#传入测试数据,测试模型的表现
print(clf_sk.score(X_test, y_test))

KD树

kd树是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形数据结构。

kd树是二叉树，表示对 $k$ 维空间的一个划分（partition）。构造kd树相当于不断地用垂直于坐标轴的超平面将 $k$ 维空间切分，构成一系列的k维超矩形区域。kd树的每个结点对应于一个 $k$ 维超矩形区域。

构造平衡kd树算法

输入： $k$ 维空间数据集 $T＝\{x_1，x_2,…,x_N\}$ ，

其中 $x_{i}=\left(x_{i}^{(1)}, x_{i}^{(2)}, \cdots, x_{i}^{(k)}\right)^{\mathrm{T}}$ ， $i ＝ 1, 2, \dots, N$ ；

输出：kd树。

（1）开始：构造根结点，根结点对应于包含 $T$ 的 $k$ 维空间的超矩形区域。

选择 $x^{(1)}$ 为坐标轴，以T中所有实例的 $x^{(1)}$ 坐标的中位数为切分点，将根结点对应的超矩形区域切分为两个子区域。切分由通过切分点并与坐标轴 $x^{(1)}$ 垂直的超平面实现。

由根结点生成深度为1的左、右子结点：左子结点对应坐标 $x^{(1)}$ 小于切分点的子区域，右子结点对应于坐标 $x^{(1)}$ 大于切分点的子区域。

将落在切分超平面上的实例点保存在根结点。

（2）重复：对深度为 $j$ 的结点，选择 $x^{(1)}$ 为切分的坐标轴， $l ＝ j (m o d k) + 1$ ，以该结点的区域中所有实例的 $x^{(1)}$ 坐标的中位数为切分点，将该结点对应的超矩形区域切分为两个子区域。切分由通过切分点并与坐标轴 $x^{(1)}$ 垂直的超平面实现。