机器学习-KNN最近邻算法原理及实践_knn算法实验原理

一、KNN最近邻算法原理

1.KNN(k-nearest neighbor)最近邻算法是一种有监督学习（存在特征标签）能够解决分类与回归问题的方法，是一个理论上比较成熟的、也是最简单的机器学习算法之一。KNN算法中在给定的一个数据集中，其中数据集实例分类已经确定。对于已知某新的特征实例且未知分类时，根据其K个最近邻居训练样本实例进行统计分析类别，有多数表决进行决策新实例的分类。

 

图中K个最近邻居的值、相似度计量决定了圆域半径，在圆域中进行训练样本实例分类统计，有类别占比多数决定新实例的分类。 

二、KNN算法关键参数

2.KNN最近邻法三要素：距离度量（相似度计量）、K值的选择和分类决策规则。

距离度量（相似度计量） 

 分类之间相似度的计算采用距离度量，常见的距离度量：欧氏距离、曼哈顿距离、明科夫斯基距离。一般采用欧氏距离。

 K值的选择

k值的选项表示对分类甄别条件的宽松或严苛。当K值过小时，k近邻模型更复杂，新实例的分类容易受到局部少数训练实例的影响，容易发生欠拟合；当K值过大时，k近邻模型更简单，容易发生过拟合，导致泛化性能下降。因此k 值得选择会对分类结果产生重大影响。k 值的选择反映了对近似误差与估计误差之间的权衡，通常由交叉验证选择最优的k值 。

（交叉验证）

交叉验证的基本想法是重复地使用数据，把给定的数据进行切分，将切分的数据组合为训练集与测试集，在此基础上反复进行训练测试以及模型的选择。在实现过程中将采用sklearn.model_selection.cross_val_score()实现交叉验证选取k kk值。

分类决策规则

分类决策规则往往是多数表决，即由输入实例的k kk个邻近输入实例中的多数类决定输入实例的类

如果K=3，那么离绿色点最近的有2个红色三角形和1个蓝色的正方形，这3个点投票，于是绿色的这个待分类点属于红色的三角形。

如果K=5，那么离绿色点最近的有2个红色三角形和3个蓝色的正方形，这5个点投票，于是绿色的这个待分类点属于蓝色的正方形。

三、KNN算法实践（KNN实现鸢尾花分类）

步骤：

算距离：给定待分类样本，计算它与已分类样本中的每个样本的距离；

找邻居：圈定与待分类样本距离最近的K个已分类样本，作为待分类样本的近邻；

做分类：根据这K个近邻中的大部分样本所属的类别来决定待分类样本该属于哪个分类；

数据集：鸢尾花数据集

KNN算法文件：KnnAlgorithm.py

# -*- coding: utf-8 -*-
"""
Created on Tue Jul 19 10:10:40 2022
@author: 文浩
"""
 
import numpy as np
 
def knn(inX,DataSet,Label,K):
    #欧几里得距离计算样本之间的相似度
    dist = (((DataSet-inX)**2).sum(1))**0.5
    
    #返回后排序的索引值 
    sortedDist = dist.argsort()
    
    #统计训练样本分类次数
    classCount = {}
    for i in range(K):
        voteLabel = Label[sortedDist[i]]
        classCount[voteLabel] = classCount.get(voteLabel,0)+1
    
    #找出训练样本中类别频次最高
    maxtype = 0
    maxcount = -1
    for key,value in classCount.items():
        if value > maxcount:
            maxtype = key
            maxcount = value
    return maxtype
'
运行
运行

主体代码

# -*- coding: utf-8 -*-
"""
Created on Mon Jul 25 10:08:07 2022
@author: 文浩
"""
import numpy as np
import KnnAlgorithm as K
 
#特征矩阵函数实现
#将数据集中的数据提炼出特征矩阵，标签向量
def filematrix(filename):
    fr = open(filename)
    numberfileLines = len(fr.readlines())
    returnMatrix = np.zeros((numberfileLines,4))
    classLabelVector = []
    fr = open(filename)
    index = 0
    for line in fr.readlines():
        line = line.strip() 
        listFromLine = line.split(",")
        returnMatrix[index,:] = listFromLine[0:4]
        if listFromLine[-1] == 'Iris-setosa':
            classLabelVector.append(1)
        elif listFromLine[-1] == 'Iris-versicolor':
            classLabelVector.append(2)
        elif listFromLine[-1] == 'Iris-virginica':
            classLabelVector.append(3)
        index += 1
    return returnMatrix,classLabelVector
 
#归一化（当测试集中某个特征向量对测试样本模型计算结果远远大于其他特征时需要进行）
#数据归一化的目的就是为了把不同来源的数据统一到同一数量级
#0-1标准化
#线性归一化，也称min-max标准化、离差标准化；
#是对原始数据的线性变换，使得结果值映射到[0,1]之间。转换函数如下
def autoNorm(dataSet):
    #min(0) 参数0 代表是按照列 进行运算   1 代表按照行 进行运算
    minVals = dataSet.min(0)  
    maxVals = dataSet.max(0)
    #初始化 zero 0 矩阵
    normDataSet = np.zeros(dataSet.shape)  
    normDataSet = (dataSet - minVals)/(maxVals - minVals)
    return normDataSet
 
datingDataMatrix,datingLabels = filematrix('iris.txt')
print("特征矩阵:\n",datingDataMatrix)
print("标签向量：",datingLabels)
 
#归一化后的特征矩阵
#dataSet=autoNorm(datingDataMat)
#print(dataSet)
 
#划分测试集和训练集  分占比例
m = 0.9
dataSize = datingDataMatrix.shape[0]
print("样本总的行数：",dataSize)
trainSize=int(m*dataSize)
testSize=int((1-m)*dataSize)
print("训练样本数：%d，测试样本%d"%(trainSize,testSize))
k=5
error=0
for i in range(testSize):
    #调用knn 最近邻算法
    result=K.knn(datingDataMatrix[trainSize+i,:],datingDataMatrix[0:trainSize,:],datingLabels[0:trainSize],k)
    if result!=datingLabels[trainSize+i-1]:
        error=error+1
print("error:",error/testSize)
 
 
 
 
 
 
 
 
 
 
 
 
 
 

运行结果：（当训练样本与测试样本为9:1时，KNN算法分类效果最好，错误率几乎可以达到0）

四、KNN算法总结

KNN算法优点：

操作简单易用，相比其他算法，KNN算是比较简洁明了的算法。
模型训练时间快，
对于分类预测效果好。
对异常值不敏感

KNN算法缺点：

对内存要求较高，因为该算法存储了所有训练数据
预测阶段可能很慢
对不相关的功能和数据规模敏感