K近邻算法

发布于：2024-10-10 ⋅ 阅读:(111) ⋅ 点赞:(0)

一、K近邻算法基础介绍

K近邻算法也是常说的KNN算法，是一种常见的分类和回归算法，当然我们常将其用于分类。是一种监督算法，该算法的内容其实和名字很像，根据邻居来进行判断。有点近朱者赤近墨者黑的意味。

比如我们常说：某个人的工资一般是与其玩的最好的5个朋友(或者说是N个)工资的平均值。

在K近邻算法中也是如此，某个样本的类别是与其最近的K个样本类别的众数，某个样本的值(回归问题中)是与其最近的K个样本的平均值。

上句话中我将三个地方标黑了，这也是K近邻算法中最重要的三个地方，也是KNN算法的三要素：

(1)：k值的选择

(2)：距离的度量(即何为最近)

(3)：决策规则(为什么分类用众数，回归用平均值)

算法介绍：

以使用KNN算法分类为例，给定一个数据集：

T=\{(x_1,y_1),(x_2,y_2),...(x_n,y_n)\}

其中 x_i 是一个k维向量， y_i\in \{c_1,c_2,c_3,...c_k\} 为数据 x_i 所属的类别。一般𝑘<<𝑛

预测：

给定一个𝑥输出其所属的类别。

该算法采用的方法是：在给定的距离度量基础上，在训练集𝑇中找出与𝑥最接近的k个点，将其记录为 N_k(x) 。然后在 N_k(x) 中根据分类决策规则决定𝑥的类别𝑦

用公式表示就是:

y=argmax_{c_j}\sum_{x_i \in N_k(x)}I(y_i==c_i)

𝐼是指示函数，当 y_i==c_j 时为1，否则为0。

当𝑘==1时，可以称之为最近邻算法，此时𝑥的预测值为直接距离𝑥最近的训练集中的样本 x_j 对应得  y_j

根据上面的介绍，我们可以发现KNN算法好像并不需要对样本𝑇进行训练，当预测样本来的时候我们直接查找与预测样本最近，然后做一些判断就ok了。事实也是如此，该算法没有显示学习的过程，并且是是一个无参算法。

无参算法对应的就是有参数算法，故名思义，无参就是没有参数！我们不需要去优化某个参数，然后生成由参数和结构组成的模型。有参算法就是需要训练生成参数，然后根据生成的参数和模型对预测样本进行预测。

二、K近邻算法三要素和源码

上文说到k近邻算法的三要素。下面我们来详细介绍一下：

1：k值

k值就是选取邻居的数量。到达到达根据几个朋友的工资来估算某个人的工资呢？如果k的取值太小的话，相应的误差就会比较大。反之如果k的取值太大，可能会选取大不那么近的邻居，导致误差也偏大。极端情况下，当k等于样本总和N时，无论预测样本是什么都会选取训练集中最多的类别(分类问题)作为预测结构。

k值的选取我们可以根据交叉检验的方法来选取。比如：我们将训练集拆成2份，一部分作为训练集，一部分作为验证集。选取几个k值的候选值，然后预测验证集在该k值情况下的分类误差。然后可以选取分类误差最小的一个k值。当然也可以采用五折验证的方法。

2：距离度量

距离度量就是衡量两个样本距离的方法，常见的度量方法有：欧式距离，曼哈顿距离，或者是更为一般的 L_p 距离。

假设特征空间是n维的向量空间 R^n 。x_i=(x_i^{(1)},x_i^{(2)},...x_i^{(n)})，x_j=(x_j^{(1)},x_j^{(2)},...x_j^{(n)})  。x_i,x_j  的 L_p 距离为：

L_p(x_i,x_j)=(\sum_{l=1}^n|x_i^{(l)}-x_j^{(l)}|^p)^{\frac{1}{p}}

其中𝑞>=1，可以发现，当𝑝=2时，称之为欧式距离：

L_2(x_i,x_j)=(\sum_{l=1}^n|x_i^{(l)}-x_j^{(l)}|^2)^{\frac{1}{2}}

当𝑝=1时，称之为曼哈顿距离，即：

L_2(x_i,x_j)=\sum_{l=1}^n|x_i^{(l)}-x_j^{(l)}|

3：决策规则

就是决策方法，假设一个分类问题，我们现在已经获取了预测样本最近的K个训练样本的类别，怎样去进行预测？一般情况下我们可以使用直接表决的方法，也就是取众数，在回归问题中我们采用平均数。当然有时候我们也要考虑到距离因素，给距离越近的样本加点权重。

下面我们用代码来表示从五折检验选取最优的k值，然后通过k值来进行预测。

import numpy as np
from sklearn import datasets
from sklearn.model_selection import train_test_split
from sklearn.model_selection import StratifiedKFold

X = datasets.load_iris()['data']
Y = datasets.load_iris()['target']
X_train, X_test, y_train, y_test = train_test_split(X, Y, test_size=0.4, stratify=Y,random_state=100)


class KNN:
    def __init__(self, train_x, train_y, test_x, test_y):
        """
        KNN初始话
        :param train_x:训练集X
        :param train_y: 训练集Y
        :param test_x: 预测集X
        :param test_y: 预测集Y
        """
        self.train_x = train_x
        self.train_y = train_y
        self.test_x = test_x
        self.test_y = test_y
        self.k = None

    def euclidean_dis(self, x1, x2):
        """
        返回x1与x2的距离(x1,x2均为二维矩阵).x1.shape=(N1*M),x2.shape=(N2*M2),返回结果为(N1*N2)
        :param x1:
        :param x2:
        :return:
        """
        n1, m1 = x1.shape
        n2, m2 = x2.shape
        if m1 != m2:
            raise ("两个向量维度不相等")
        x1x2 = np.dot(x1, x2.T)  # (n1,n2)
        y1 = np.repeat(np.reshape(np.sum(np.multiply(x1, x1), axis=1), (n1, 1)), repeats=n2, axis=1)
        y2 = np.repeat(np.reshape(np.sum(np.multiply(x2, x2), axis=1), (n2, 1)), repeats=n1, axis=1).T
        dis = y1 + y2 - 2 * x1x2
        return dis

    def predict(self, train_x, y, test, k):
        """
        返回根据KNN预测的结果
        :param train_x: 训练集x
        :param y: 训练集y
        :param test: 预测集
        :return: 返回test预测的结果
        """
        dis = self.euclidean_dis(test, train_x)
        k_neighbor = np.argsort(dis, axis=1)[:, :k]
        k_neighbor_value = y[k_neighbor]
        n = test.shape[0]  # 预测结果的个数
        pred = np.zeros(n)
        for i in range(n):
            pred[i] = np.argmax(np.bincount(k_neighbor_value[i]))
        return pred

    def KFlod(self, k):
        folds = StratifiedKFold(n_splits=5, shuffle=True, random_state=1996)
        oof = np.zeros(self.train_x.shape[0])
        for fold_, (train_index, test_index) in enumerate(folds.split(self.train_x, self.train_y)):
            train_x, test_x, train_y, test_y = self.train_x[train_index], self.train_x[test_index], \
                                               self.train_y[
                                                   train_index], self.train_y[test_index]
            pred = self.predict(train_x, train_y, test_x, k)
            oof[test_index] = pred
        return np.sum(oof == self.train_y)

    def selectK(self):
        ks = [2,3, 4, 5, 6,7,8,9,10,11,12,13,14,15]
        value = 0
        for k in ks:
            value_tem = self.KFlod(k)
            print("当前K的值为：", k, "预测得分为：", value_tem)
            if value_tem > value:
                self.k = k
                value = value_tem

    def trainAndPredic(self):
        self.selectK()
        print("选择的k为：", self.k)
        preds = self.predict(self.train_x, self.train_y, self.test_x, self.k)
        print("预测结果的正确个数为:", np.sum(preds == self.test_y))
        print("预测结果的错误个数为:", np.sum(preds != self.test_y))


model = KNN(X_train, y_train, X_test, y_test)
model.trainAndPredic()

'''
当前K的值为： 2 预测得分为： 89
当前K的值为： 3 预测得分为： 89
当前K的值为： 4 预测得分为： 89
当前K的值为： 5 预测得分为： 89
当前K的值为： 6 预测得分为： 88
当前K的值为： 7 预测得分为： 89
当前K的值为： 8 预测得分为： 89
当前K的值为： 9 预测得分为： 89
当前K的值为： 10 预测得分为： 89
当前K的值为： 11 预测得分为： 89
当前K的值为： 12 预测得分为： 89
当前K的值为： 13 预测得分为： 90
当前K的值为： 14 预测得分为： 88
当前K的值为： 15 预测得分为： 89
选择的k为： 13
预测结果的正确个数为: 56
预测结果的错误个数为: 4
'''

三、K近邻算法的优化

假设我的样本空间是𝑁𝑋𝑀,那么我每次预测一个样本花费的时间是𝑂(𝑁𝑀)+𝑂(𝐾𝑁)。(前者为计算距离的时间，后者为选出K个最近邻居的时间)。在很多大型的场景中𝑁的值会非常的大，采用该算法进行预测花费的时间会非常的长。比较常见的优化方法有：KD树。在实际的应用中我们会比较常用Annoy等信息检索中常用的方法。

KD树在很多关于K近邻算法的介绍中都有所提及，并且相比与Annoy相比，Annoy算法其实更加常用。

Annoy也是采用二叉树的方法，在各种工业系统中使用的比较多，算法基础我们不说了，直接看下面的例子：

import numpy as np
from sklearn import datasets
from sklearn.model_selection import train_test_split
X=datasets.load_iris()['data']
Y=datasets.load_iris()['target']
Y[Y>1]=1
X_train,X_test,y_train,y_test=train_test_split(X,Y,test_size=0.4,stratify=Y)
from annoy import AnnoyIndex
# pip install annoy 安装Annoy

f指的是向量的维度，metric 表示度量公式。在这里，Annoy 支持的度量公式包括："angular", "euclidean", "manhattan", "hamming", "dot"
 

metric="euclidean" 
f=4
a = AnnoyIndex(f, metric)


'''
a.add_item(i, v)：i 是一个非负数，表示 v 是第 i 个向量
'''

for i in range(90):
    a.add_item(i, X_train[i])


'''
trees表示树的数量
'''


# 树的数量
trees=10
a.build(trees) # 10 trees
# True


'''
储存索引成文件
'''


a.save("train.ann")
# True


'''
读取存储好的索引文件
'''


u = AnnoyIndex(f, 'euclidean')
u.load("train.ann")
# True


'''
查找距离某个向量最近的n个样本。include_distances=False时仅输出索引，True输出索引和距离值。
'''


a.get_nns_by_vector(X_test[0], n=10, search_k=-1, include_distances=True)

'''
([13, 5, 42, 89, 33, 45, 55, 71, 63, 47],
 [0.20000028610229492,
  0.331662654876709,
  0.34640997648239136,
  0.38729819655418396,
  0.4358895421028137,
  0.4582575857639313,
  0.47958314418792725,
  0.49999988079071045,
  0.5099020004272461,
  0.5567763447761536])
'''

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布