作者：張張張張
github地址：https://github.com/zhanghekai
【转载请注明出处，谢谢！】

【机器学习系列】之k近邻（kNN）
【机器学习系列之】纯python及sklearn实现kNN

一、纯python实现kNN Brute-Force法

kNN项目案例：优化约会网站的配对效果

项目概述
拉克丝使用约会网站寻找约会对象，经过一段时间之后，她发现曾交往过三种类型的人：

• 不喜欢的人
• 魅力一般的人
• 极具魅力的人

她希望：

1. 工作日与魅力一般的人约会
2. 周末与极具魅力的人约会
3. 不喜欢的人则直接排除掉

现在她收集到了一些约会网站未曾记录的数据信息，这更有助于匹配对象的归类。拉克丝约会的对象主要包含以下3种特征：

• 每年获得的飞行常客里程数
• 玩视频游戏所耗时间百分比
• 每周消费的冰淇淋公升数

文本文件数据格式如下，完整数据集可在我的github中找到。
$$\begin{gathered} 409208.3269760.9539523 \\ 144887.1534691.6739042 \\ 260521.4418710.8051241 \\ 7513613.1473940.4289641 \\ 383441.6697880.1342961 \end{gathered}$$

导入需要用到的包

import numpy as np
import matplotlib.pyplot as plt
import operator
from os import listdir
from collections import Counter

数据处理：将文本记录转换为 NumPy 的解析程序
\quad 输入： 数据文件路径

\quad 输出： 数据矩阵 returnMat 和对应的类别 classLabelVector

def file2matrix(filename):
    fr = open(filename)
    # 获得文件中的数据行的行数
    numberOfLines = len(fr.readlines())
    # 生成对应的空矩阵
    # 例如：zeros(2，3)就是生成一个 2*3的矩阵，各个位置上全是 0 
    returnMat = np.zeros((numberOfLines, 3))  
    classLabelVector = []  
    
    fr = open(filename)
    index = 0
    for line in fr.readlines():
        line = line.strip()
        # 以 '\t' 切割字符串
        listFromLine = line.split('\t')
        # 每列的属性数据
        returnMat[index, :] = listFromLine[0:3]
        # 每列的类别数据，就是 label 标签数据
        classLabelVector.append(int(listFromLine[-1]))
        index += 1
    # 返回数据矩阵returnMat和对应的类别classLabelVector
    return returnMat, classLabelVector

将数据归一化
归一化是一个让权重变为统一的过程，归一化特征值，消除特征之间量级不同导致的影响。

归一化定义： 我们是这样认为的，归一化就是要把你需要处理的数据经过处理后（通过某种算法）限制在你需要的一定范围内。首先归一化是为了后面数据处理的方便，其次是保正程序运行时收敛加快。

归一化的几种方法
1.线性函数转换：
$$y=\frac{x-MinValue}{MaxValue-MinValue}$$
**说明：**x、y分别为转换前、后的值，MaxValue、MinValue分别为样本的最大值和最小值。

2.对数函数转换：
$$y=lo{g}_{10}x$$
**说明：**以10为底的对数函数转换。

3.反余切函数转换:
$$y=\frac{2\times arctan(x)}{\pi }$$

在统计学中，归一化的具体作用是归纳统一样本的统计分布性。归一化在0-1之间是统计的概率分布，归一化在-1~+1之间是统计的坐标分布。

归一化特征值，消除特征之间量级不同导致的影响
\quad 输入： 数据集

\quad 输出： 归一化后的数据集normDataSet

\quad 使用的归一化公式： $Y=\frac{X-Xmin}{Xmax-Xmin}$
\quad 其中：min和max分别是数据集中的最小特征值和最大特征值。该函数可以自动将数字特征转化为0到1的区间。

def autoNorm(dataSet):
    # 计算每种属性的最大值、最小值、范围
    minVals = dataSet.min(0) # min(0)返回该矩阵中每一列的最小值
    maxVals = dataSet.max(0) # max(0)返回该矩阵中每一列的最大值
    ranges = maxVals - minVals # 计算归一化公式的分母
    
    # 生成normDataSet矩阵，normDataSet用于记录归一化后的数据集
    normDataSet = np.zeros(np.shape(dataSet))
    # m记录的是数据集的行数
    m = dataSet.shape[0]
    
    '''tile（A,reps） 
          A: 输入的array 
          reps: A沿各个维度重复的次数'''
    # 计算归一化公式的分子，生成数据集与最小值之间的差值组成的矩阵
    normDataSet = dataSet - np.tile(minVals, (m, 1))
    # 使用归一化公式，使用上述计算出来的分子和分母做除法
    normDataSet = normDataSet / np.tile(ranges, (m, 1))
    
    return normDataSet, ranges, minVals

kNN算法伪代码
对于每一个在数据集中的数据点：
\qquad 计算目标的数据点（需要分类的数据点）与该数据点的距离
\qquad 将距离排序：从小到大
\qquad 选取前K个最短距离
\qquad 选取这K个中最多的分类类别
\qquad 返回该类别来作为目标数据点的预测值

上述伪代码的算法构建
\qquad 输入：
\qquad\qquad inX：目标点的数据
\qquad\qquad dataSet：所有已知样本的数据
\qquad\qquad labels：每个样本的类别标签
\qquad\qquad k：int型数值，用来选取前k个最短距离

\qquad 输出：
\qquad\qquad sortedClassCount[0][0]：返回这k个中最多的分类类别作为预测值

距离公式：$d=\sqrt[2]{(x_1-x_2{)}^2+(y_1-y_2{)}^2}$

def classify0(inX, dataSet, labels, k):
    # 记录一共有多少个样本点
    dataSetSize = dataSet.shape[0]
    
    # 距离度量 ：实现上述距离公式
    diffMat = np.tile(inX, (dataSetSize, 1)) - dataSet
    sqDiffMat = diffMat ** 2
    sqDistances = sqDiffMat.sum(axis=1)
    distances = sqDistances ** 0.5
    
    '''argsort函数返回的是数组值从小到大的索引值'''
    # 距离排序：从小到大
    sortedDistIndicies = np.argsort(distances)
    
    # 选取前k个最短距离， 选取这k个中最多的分类类别
    classCount={}
    for i in range(k):
        # 记录当前样本点的分类类别
        voteIlabel = labels[sortedDistIndicies[i]]
        '''Python 字典(Dictionary) get() 函数返回指定键的值，如果值不在字典中返回默认值。'''
        # 将每个类别及其出现的次数保存在字典中
        classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1
    
    '''Python 字典 items() 方法以列表返回可遍历的(键, 值) 元组数组。'''
    '''operator模块提供的itemgetter函数用于获取对象的哪些维的数据，参数为一些序号（即需要获取的数据在对象中的序号）'''
    # 将字典中类别出现的次数从大到小排序,以元组方式保存键值对，并以列表形式返回
    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
    
    # 返回出现次数最多的类别
    return sortedClassCount[0][0]

约会网站预测函数
使用拉克丝提供的部分数据作为测试样本。如果预测分类与实际类别不同，则标记为一个错误。

\qquad 输出：
\qquad\qquad errorCount：判断错误的样本的数量。

def classifyPerson():
    
    # 设置测试数据的一个比例（训练数据集比例 = 1 - hoRatio）
    hoRatio = 0.1
    # 从文件中加载数据
    datingDataMat, datingLabels = file2matrix('G:\\desktop\\dataknn.txt')
    # 归一化数据
    normMat, _, _ = autoNorm(datingDataMat)
    # m表示数据的行数，即矩阵的第一维
    m = normMat.shape[0]
    # 设置测试的样本数量
    numTestVecs = int(m * hoRatio)
    print('测试集数量为：', numTestVecs)
    
    # errorCount:记录测试集中样本分类错误的数量
    errorCount = 0
    
    for i in range(numTestVecs):
        # 对数据进行测试，classifierResult为该样本的预测类别，datingLabels[i]为该样本的实际类别
        # classify0为 kNN 预测函数，将数据集中前numTestVecs个样本作为测试集，其余样本作为训练集
        # k 取3 ，即找例目标点最近的3个点来判别该点的类别。
        classifierResult = classify0(normMat[i, :], normMat[numTestVecs:m, :], datingLabels[numTestVecs:m], 3)
        print('该样本的预测类别为：%d, 该样本的实际类别为：%d' %(classifierResult, datingLabels[i]))
        # 如果预测的类别不等于实际的类别，则分类错误的数量加一
        if(classifierResult != datingLabels[i]): 
            errorCount += 1

    print('测试集中分类错误的样本数量为：', errorCount)
    print('测试集上分类错误率为：%.2f' % (errorCount/numTestVecs*100), '%')

classifyPerson()

测试集数量为： 100
该样本的预测类别为：3, 该样本的实际类别为：3
该样本的预测类别为：2, 该样本的实际类别为：2
该样本的预测类别为：1, 该样本的实际类别为：1
				  .
				  .
				  .
									
该样本的预测类别为：2, 该样本的实际类别为：2
该样本的预测类别为：1, 该样本的实际类别为：1
该样本的预测类别为：3, 该样本的实际类别为：1
测试集中分类错误的样本数量为： 5
测试集上分类错误率为：5.00 %

约会网站预测函数
产生简单的命令行程序，然后拉克丝可以输入一些特征数据以判断对方是否为自己喜欢的类型。

def classifyPerson():
    # 预测类别文字化
    resultList = ['不喜欢的人', '魅力一般的人', '极具魅力的人']
    
    ffMiles = float(input('每年获得的飞行常客里程数：'))
    percentTats = float(input('玩视频游戏所耗时间百分比：'))
    iceCream = float(input('每周消费的冰淇淋公升数：'))
    
    datingDataMat, datingLabels = file2matrix('G:\\desktop\\dataknn.txt')
    normMat, ranges, minVals = autoNorm(datingDataMat)
    # inArr记录目标点的数据
    inArr = np.array([ffMiles,percentTats,iceCream])
    # 由于训练集中的数据都是归一化后的， 所以也需要将目标点进行归一化，也就是第一个参数所做的工作
    classifierResult = classify0((inArr - minVals)/ranges, normMat, datingLabels, 3)
    
    print('你对此人的评价为：', resultList[classifierResult - 1])

实际运行效果如下

classifyPerson()

每年获得的飞行常客里程数：10000
玩视频游戏所耗时间百分比：10
每周消费的冰淇淋公升数：0.5
你对此人的评价为： 魅力一般的人

二、sklearn实现kNN：KDTree和BallTree

sklearn实现拉克丝约会案例。

KDTree和BallTree具有相同的接口，在这里只展示使用KDTree的例子。
若想要使用BallTree，则直接导入：from sklearn.neighbors import BallTree

from sklearn.neighbors import KDTree
import numpy as np
import operator

数据处理：将文本记录转换为 NumPy 的解析程序
\quad 输入： 数据文件路径

\quad 输出： 数据矩阵 returnMat 和对应的类别 classLabelVector

def file2matrix(filename):
    fr = open(filename)
    # 获得文件中的数据行的行数
    numberOfLines = len(fr.readlines())
    # 生成对应的空矩阵
    # 例如：zeros(2，3)就是生成一个 2*3的矩阵，各个位置上全是 0 
    returnMat = np.zeros((numberOfLines, 3))  
    classLabelVector = []  
    
    fr = open(filename)
    index = 0
    for line in fr.readlines():
        line = line.strip()
        # 以 '\t' 切割字符串
        listFromLine = line.split('\t')
        # 每列的属性数据
        returnMat[index, :] = listFromLine[0:3]
        # 每列的类别数据，就是 label 标签数据
        classLabelVector.append(int(listFromLine[-1]))
        index += 1
    # 返回数据矩阵returnMat和对应的类别classLabelVector
    return returnMat, classLabelVector

datingDataMat, datingLabels = file2matrix('G:\\desktop\\dataknn.txt')

构建KDTree

KDTree(X, leaf_size=40, metric=‘minkowski’, **kwargs)

\qquad X：样本点数据。
\qquad leaf_size：切换到暴力求取的点数，更改leaf_size不会影响查询结果，但会显著影响查询的速度和存储构造树所需的内存。
\qquad metric：用于树的距离度量。默认=‘minkowski’，即欧式度量标准。

tree = KDTree(datingDataMat) 

方式1. 查询k个最近邻

# 输入一个目标点
target = np.array([[43757, 7.882601, 1.332446]])

# 43757	7.882601	1.332446	3

# 输入目标点
dist, ind = tree.query(target, k=3)

# 三个最近邻的索引
print(ind)

[[461 575  15]]

# 这三个最近邻距目标点的距离
print(dist)

[[ 6.49498394 78.07623758 84.22125611]]

方式2. 查询给定半径内的邻居
限定半径后就不能再限定k

ind_r = tree.query_radius(target, r=100) 

# 半径为r范围内的所有样本点
print(ind_r)

[array([ 15, 575, 461], dtype=int64)]

以"查询k个最近邻为例"，判定目标点为哪个类别

返回最近邻样本中最多的类别

def classify(ind, labels):
    classCount={}
    for i in range(len(ind)):
        # 记录当前样本点的分类类别
        voteIlabel = labels[ind[0][i]]
        # 将每个类别及其出现的次数保存在字典中
        classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1
        
    # 将字典中类别出现的次数从大到小排序,以元组方式保存键值对，并以列表形式返回
    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
    
    return sortedClassCount[0][0]

def predict():
    # 预测类别文字化
    resultList = ['不喜欢的人', '魅力一般的人', '极具魅力的人']
    
    # 找出最近邻的k个样本中最多的类别
    classifierResult = classify(ind, datingLabels)
    print('你对此人的评价为：', resultList[classifierResult - 1])

predict()

你对此人的评价为： 极具魅力的人

---

【参考文献】

• apache github主页：https://github.com/apachecn/AiLearning
• sklearn kNN部分官网：https://scikit-learn.org/stable/modules/neighbors.html#classification