1.k-近邻算法概述

k-近邻算法采用测量不同特征值之间的距离方法进行分类，它的工作原理是：存在一个样本数据集合，也称作训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一数据与所属分类的对应关系。输人没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据(最近邻）的分类标签。一般来说，我们只选择样本数据集中前k个最相似的数据,这就是k-近邻算法中k的出处,通常k是不大于20的整数。最后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。

k-近邻算法步骤：

对未知类别属性的数据集中的每个点以此执行以下操作：

（1）计算已知类别数据集中的点与当前点之间的距离；

（2）按照距离递增次序排序；

（3）选取与当前点距离最小的k个点；

（4）确定前k个点所在类别的出现频率；

（5）返回前k个点出现频率最高的类别作为当前点的预测分类；

2.KNN的算法实现

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  #欧式距离计算

    sortedDistIndices=distances.argsort()
    classCount={}
    for i in range(k):
        voteIlabel=labels[sortedDistIndices[i]]
        classCount[voteIlabel]=classCount.get(voteIlabel,0)+1
    sortedClassCount=sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)  #按照出现标签的次数降序
    return sortedClassCount[0][0]

classify0()函数有4个输入参数:用于分类的输入向量是inX,输人的训练样本集为dataSet，
标签向量为labels,最后的参数k表示用于选择最近邻居的数目,其中标签向量的元素数目和矩
阵dataSet的行数相同。使用欧氏距离公式,计算两个向量点xA和xB之间的距离:

欧氏距离公式：

                                  d=\sqrt{\left ( xA_{0}-xB_{0} \right )^{2}+\left ( xA_{1}-xB_{1} \right )^{2}}

计算完所有点之问的距离后,可以对数据按照从小到大的次序排序.然后,确定前k个距离最小元素所在的主要分类,输入k总是正整效:最后,将classCount字典分解为元组列表,然后使用程序第二行导入运算符模块的itemgeter方法,按照第二个元素的次序对元组进行排序.此处的排序为逆序,即按照从最大到最小次序排序,最后返回发生频率最高的元素标签。

3.示例：使用k-近邻算法改进约会网站的配对效果

海伦一直使用在校约会网站寻找适合自己的约会对象。尽管约会网站会推荐不同的人选，但她并不是喜欢每一个人。经过一番总结，她发现曾交往过三种类型的人：1.不喜欢的人  2.魅力一般的人  3.极具魅力的人。海伦收集约会数据已经有一段时间，她把这些数据存放在文本文件datingTestSet.txt中，每个样本数据占据一行，总共1000行，海伦的样本主要包含以下3中特征：1.每年获得的飞行常客里程数  2.玩视频游戏所耗事件百分比  3.每周消费的冰淇淋公升数

3.1准备数据：从文本文件中解析数据

将datingTestSet.txt中的数据格式改变为分类器可以接受的格式，并输出训练矩阵和类标签向量。

def file2matrix(filename):
    fr=open(filename)
    arrayOLines=fr.readlines()  #读取文件的所有行
    numberOfLines=len(arrayOLines)  #读取行数
    returnMat=np.zeros((numberOfLines,3))  #创建数组
    classLabelVector=[]
    index=0
    for line in arrayOLines:
        line = line.strip()  #去除每一行的空格
        listFromLine = line.split('\t')  #将字符串根据'\t'分隔符进行切片。
        returnMat[index,:] = listFromLine[0:3]  #将数据前三列提取出来,存放到第returnMat的index行中
		#根据文本中标记的喜欢的程度进行分类,1代表不喜欢,2代表魅力一般,3代表极具魅力   
		# 对于datingTestSet.txt  最后的标签是已经经过处理的 标签已经改为了1, 2, 3
        if listFromLine[-1] == 'didntLike':   #判断行的最后一个元素
            classLabelVector.append(1)
        elif listFromLine[-1] == 'smallDoses':
            classLabelVector.append(2)
        elif listFromLine[-1] == 'largeDoses':
            classLabelVector.append(3)
        index += 1
    return returnMat,classLabelVector  #返回读出的原数据与各行的标签

分析：先打开文件，读取所有行与文件的行数，将文件的前三列数据存放在returnMat中，将文件中的标签‘didntLike’、'smallDoses'、'largeDoses'设为标签1、标签2、标签3，将标签的数据存放于classLabelVector。

3.2准备数据：归一化数据

计算点之间的距离时，我们很容易发现,数字差值最大的属性对计算结果的影响最大，也就是说，每年获取的飞行常客里程数对于计算结果的影响将远远其他两个特征一一玩视频游所耗时间百分比和每周消费冰淇淋公升数一的影响。而产生这种现象的唯一原因,仅仅是因为飞行常客里程数远大于其他特征值。但海伦认为这三种特征是同等重要的,因此作为三个等权重的特征之一,飞行常客里程数并不应该如此严重地影响到计算结果。在处理这种不同取值范围的特征值时，我们通常采用的方法是归一化，可将取值范围处理为0到1或者-1到1之间。下面的公式可以将任意取值范围的特征值转化为0到1区间内的值：

                             newValue=(oldValue-min)/(max-min)

def autoNorm(dataSet):
    minVals=dataSet.min(0)  #计算每一列的最小值m,minVals为长度为3的数组
    maxVals=dataSet.max(0)
    ranges=maxVals-minVals
    normDataSet =np.zeros(np.shape(dataSet))  #初始化一个与dataSet形状相同的全零数组，用于存储归一化后的数据
    m=dataSet.shape[0]  #获取行数
    normDataSet=dataSet-np.tile(minVals,(m,1))  #m为行数,一共m行的最小值
    normDataSet=normDataSet/np.tile(ranges,(m,1))
    return normDataSet,ranges,minVals

3.3测试算法：作为完整程序

我们已经将数据按照需求做了处理,本节我们将测试分类器的效果,如果分类器的正确率满足要求，海伦就可以使用这个软件来处理约会网站提供的约会名单了。机器学习算法一个很重要的工作就是评估算法的正确率,通常我们只提供已有数据的90%作为训练样本来训练分类器，而使用其余10%数据去测试分类器，检测分类器的正确率。需要注意的是,10%的测试数据应该是随机选择的,由于海伦提供的数据并没有按照特定目的来排序,所以我们可以随意选择10%数据而不影响其随机性。在训练分类器之后我们需要用到错误率来检测分类器的性能。

def datingClassTest():
    hoRatio=0.10  #90%的数据用于训练，10%的数据用于测试
    datingDataMat,datingLabels=file2matrix('datingTestSet.txt')
    normMat,ranges,minVals=autoNorm(datingDataMat)
    m=normMat.shape[0]
    numTestVecs=int(m*hoRatio)  #用于训练的行数
    errorCount=0.0
    for i in range(numTestVecs):
        classifierResult=classify0(normMat[i,:],normMat[numTestVecs:m,:],datingLabels[numTestVecs:m],3)
        print ("分类器预测结果:%d,正确结果是:%d" % (classifierResult, datingLabels[i]))
        if(classifierResult!=datingLabels[i]):errorCount+=1.0
    print("错误率%f" % (errorCount / float(numTestVecs)))

3.4使用算法：构建完整可用系统

我们将为海伦设计一小段程序，通过该程序海伦会在约会网站上找到某个人并输入他的信息。程序会给出她对对方喜爱程度的预测值。

def classifyPerson(flight, playing, iceCream):
    resultList = ['不喜欢的人', '魅力一般的人', '极具魅力的人']
    datingDataMat, datingLabels = file2matrix("datingTestSet.txt")
    normMat, ranges, minVals = autoNorm(datingDataMat)
    isArr = np.array([flight, playing, iceCream])
    isArr = (isArr - minVals) / ranges   # 将预测值归一化
    classifierResult = classify0(isArr, normMat, datingLabels, 3)
    print("结果:", resultList[classifierResult - 1])

3.5完整代码实现与结果

import numpy as np
import operator

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  #欧式距离计算

    sortedDistIndices=distances.argsort()
    classCount={}
    for i in range(k):
        voteIlabel=labels[sortedDistIndices[i]]
        classCount[voteIlabel]=classCount.get(voteIlabel,0)+1
    sortedClassCount=sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)  #按照出现标签的次数降序
    return sortedClassCount[0][0]

def file2matrix(filename):
    fr=open(filename)
    arrayOLines=fr.readlines()  #读取文件的所有行
    numberOfLines=len(arrayOLines)  #读取行数
    returnMat=np.zeros((numberOfLines,3))  #创建数组
    classLabelVector=[]
    index=0
    for line in arrayOLines:
        line = line.strip()  #去除每一行的空格
        listFromLine = line.split('\t')  #将字符串根据'\t'分隔符进行切片。
        returnMat[index,:] = listFromLine[0:3]  #将数据前三列提取出来,存放到第returnMat的index行中
		#根据文本中标记的喜欢的程度进行分类,1代表不喜欢,2代表魅力一般,3代表极具魅力   
		# 对于datingTestSet.txt  最后的标签是已经经过处理的 标签已经改为了1, 2, 3
        if listFromLine[-1] == 'didntLike':   #判断行的最后一个元素
            classLabelVector.append(1)
        elif listFromLine[-1] == 'smallDoses':
            classLabelVector.append(2)
        elif listFromLine[-1] == 'largeDoses':
            classLabelVector.append(3)
        index += 1
    return returnMat,classLabelVector  #返回读出的原数据与各行的标签

def autoNorm(dataSet):
    minVals=dataSet.min(0)  #计算每一列的最小值m,minVals为长度为3的数组
    maxVals=dataSet.max(0)
    ranges=maxVals-minVals
    normDataSet =np.zeros(np.shape(dataSet))  #初始化一个与dataSet形状相同的全零数组，用于存储归一化后的数据
    m=dataSet.shape[0]  #获取行数
    normDataSet=dataSet-np.tile(minVals,(m,1))  #m为行数,一共m行的最小值
    normDataSet=normDataSet/np.tile(ranges,(m,1))
    return normDataSet,ranges,minVals

def datingClassTest():
    hoRatio=0.10  #90%的数据用于训练，10%的数据用于测试
    datingDataMat,datingLabels=file2matrix('datingTestSet.txt')
    normMat,ranges,minVals=autoNorm(datingDataMat)
    m=normMat.shape[0]
    numTestVecs=int(m*hoRatio)  #用于训练的行数
    errorCount=0.0
    for i in range(numTestVecs):
        classifierResult=classify0(normMat[i,:],normMat[numTestVecs:m,:],datingLabels[numTestVecs:m],3)
        print ("分类器预测结果:%d,正确结果是:%d" % (classifierResult, datingLabels[i]))
        if(classifierResult!=datingLabels[i]):errorCount+=1.0
    print("错误率%f" % (errorCount / float(numTestVecs)))

def classifyPerson(flight, playing, iceCream):
    resultList = ['不喜欢的人', '魅力一般的人', '极具魅力的人']
    datingDataMat, datingLabels = file2matrix("datingTestSet.txt")
    normMat, ranges, minVals = autoNorm(datingDataMat)
    isArr = np.array([flight, playing, iceCream])
    isArr = (isArr - minVals) / ranges   # 将预测值归一化
    classifierResult = classify0(isArr, normMat, datingLabels, 3)
    print("结果:", resultList[classifierResult - 1])

if __name__ == '__main__':
    datingClassTest()
    classifyPerson(77354, 10, 0.2)

相关的问题：相关的代码书上已经基本给出，但需要注意有些函数名的调用来自于numpy库，在进行这些函数的调用时前面需加上numpy.的前缀。

结果展示：

分析：分类器将测试结果与对应的正确结果进行输出，并统计测试的错误率，此次实验将k值取为3，可以看到测试结果的错误率为0.05，错误率较低，说明该分类器的训练结果比较理想，预测的结果成功率较高。

3.6不同k值对实验结果的影响

对于k-近邻算法，k的取值尤为重要，k取不同的数值会对预测的结果有很大的影响

当k取值为1时，结果截图：

当k取值为5时

当k取值为10时

当k取值为50时

当k的取值为100时

当k取值为200时

当k取值为300时

当k取值为500时

当k取值900时

分析：由此可知k的取值并不是越大越好也不是越小越好，k值过小会使模型出现过拟合，即学习器把训练样本本身特点当作所有潜在样本都会具有的性质，k值过大会使模型出现欠拟合，即学习器对训练样本的一般性质尚未学好。在测试中当k的取值为1时，模型出现过拟合，错误率为0.08，当k的取值为900时，模型出现欠拟合，错误率为0.61，当k的取值适当时，测试的错误率才会相对较小，模型的训练较为成功。

4.实验总结

k-近邻算法采用测量不同特征值之间的距离方法进行分类，简单来说就是“物以类聚”，计算k个与预测对象距离最近的点，并将出现次数最多的标签最为预测结果。在模型的训练过程中，k值对训练的结果有巨大的影响，k的取值过大会出现欠拟合，k的取值过小会出现过拟合。并且通过此次实验，也能对机器学习有一个大致的概念，明白机器学习的目的与应用，帮助之后对更难的算法的理解。

# 机器学习 # 近邻算法 # 人工智能
Logo
2048 AI社区

有“AI”的1024 = 2048，欢迎大家加入2048 AI社区

更多推荐

cover

打造智能电商客服 Agent：基于 LLM 的工具调用与多轮推理实践

avatar 2048 AI社区

构建可观测Harness：Agent全链路追踪与监控

可观测Harness是一套统一的可观测性管控框架，向下对接所有的基础设施、业务服务，向上提供统一的可观测数据出口和管控能力，核心是统一Agent和控制平面，实现采集规则统一、数据标准统一、管控策略统一。全链路追踪是指对一个请求从发起到结束的整个生命周期进行跟踪，记录经过的所有服务、组件、节点的调用关系、延迟、错误状态等信息，用唯一的traceId作为整个链路的标识。

avatar 2048 AI社区
cover

破界而生：AI驱动的下一轮产业革命

avatar 2048 AI社区