机器学习|算法模型——K近邻法(KNN)

1、基本概念

K近邻法(K-nearest neighbors,KNN)既可以分类，也可以回归。

　　KNN做回归和分类的区别在于最后预测时的决策方式。

KNN做分类时，一般用多数表决法

KNN做回归时，一般用平均法。

　　基本概念如下：对待测实例，在训练数据集中找到与该实例最邻近的K个实例（也就是上面所说的K个邻居），这K个实例的多数属于某个类，就把该输入实例分类到这个类中

2. KNN算法三要素

　　KNN算法主要考虑：k值的选取，距离度量方式，分类决策规则。

1） k值的选取。在应用中，k值一般选择一个比较小的值，一般选用交叉验证来取最优的k值

当K值较小，训练误差减小，泛化误差增大，模型复杂容易过拟合；

当K值较大，泛化误差减小，训练误差增大，模型简单使预测发生错误（一个极端，K等于样本数m，则完全没有分类，此时无论测试集是什么，结果都属于训练集中最多的类）

　　2）距离度量。Lp距离：误差绝对值p次方求和再求p次根。欧式距离：p=2的Lp距离。曼哈顿距离：p=1的Lp距离。p为无穷大时，Lp距离为各个维度上距离的最大值
　　3）分类决策规则。也就是如何根据k个最近邻决定待测对象的分类。k最近邻的分类决策规则一般选用多数表决

3. KNN基本执行步骤

　　1）计算待测对象和训练集中每个样本点的欧式距离

　　2）对上面的所有距离值排序

　　3）选出k个最小距离的样本作为“选民”

　　4）根据“选民”预测待测样本的分类或值

4. KNN特点

　　1）原理简单

　　2）保存模型需要保存所有样本集

　　3）训练过程很快，预测速度很慢

· 优点：

　　精度高、对异常值不敏感

　　可用于数值型数据和离散型数据（既可以用来估值，又可以用来分类）

· 缺点：

　　时间复杂性高；空间复杂性高；需要大量的内存

　　样本不平衡问题（即有些类别的样本数量很多，而其它样本的数量很少）；

　　一般数值很大的时候不用这个，计算量太大。但是单个样本又不能太少，否则容易发生误分。

　　最大的缺点是无法给出数据的内在含义。

需要思考的问题：

样本属性如何选择？如何计算两个对象间距离？当样本各属性的类型和尺度不同时如何处理？各属性不同重要程度如何处理？模型的好坏如何评估？

5.代码实现

K近邻算法的一般流程：准备数据- 分析数据- 测试算法- 使用算法

5.1 sklearn包实现

关于sklearn的详细介绍，请见之前的博客 https://www.cnblogs.com/aitree/p/14331551.html

5.1.1

sklearn实现k-近邻算法简介官方文档

5.1.2 KNeighborsClassifier函数8个参数

　　- n_neighbors：k值，选取最近的k个点，默认为5;k值不同分类结果也会不同

　　- weights：默认是uniform，参数可以是uniform（均等权重）、distance（按距离分配权重），也可以是用户自己定义的函数。uniform是均等的权重，就说所有的邻近点的权重都是相等的。

　　- algorithm：快速k近邻搜索算法，默认参数为auto。除此之外，用户也可以自己指定搜索算法ball_tree、kd_tree、brute方法进行搜索。

　　- leaf_size：默认是30，这个是构造的kd树和ball树的大小。这个值的设置会影响树构建的速度和搜索速度，同样也影响着存储树所需的内存大小。需要根据问题的性质选择最优的大小。

　　- metric：用于距离度量，默认度量是minkowski，也就是p=2的欧氏距离(欧几里德度量)。

　　- p：距离度量公式。欧氏距离和曼哈顿距离。这个参数默认为2，也可以设置为1。

　　- metric_params：距离公式的其他关键参数，这个可以不管，使用默认的None即可。

　　- n_jobs：并行处理设置。默认为1，临近点搜索并行工作数。如果为-1，那么CPU的所有cores都用于并行工作。

注意：样本数据 - 特征数据 feature 必须是数字类型，要进行运算的！

5.1.3 实例

(1)对电影进行分类

import pandas as pd
import numpy as np
from sklearn.neighbors import KNeighborsClassifier
# 读取数据
df = pd.read_excel(../../myfile.excel)

#1、实例模型对象
knn = KNeighborsClassifier(n_neighbors=3)

#2、拿到样本数据和分类结果数据: 截取目标列，样本数据要二维
feature =  df[['Action Lean','Love Lean']]
target = feature['target']

#3、训练模型
knn.fit(feature,target)

#4、测试结果
movie = np.array([13,21])
res = knn.predict(movie) 

#5、评分：分数越高悦准确
knn.score(feature,target)

(2)预测年收入是否大于50K美元

# 读取adult.txt文件，最后一列是年收入，并使用KNN算法训练模型，然后使用模型预测一个人的年收入是否大于50
# 1.  读取数据
data = pd.read_csv('../data/adults.txt')
data.head()

# 2. 获取年龄、教育程度、职位、每周工作时间作为机器学习数据 获取薪水作为对应结果    
feature = data[['age','education_num','occupation'
                    ,'hours_per_week']]
target = data['salary']
    
# 3. knn中特征数据是需要参与运算的，所以要保证特征数据必须为数值型的数据 
     # 数据转换，将String类型数据转换为int
     #### map方法，进行数据转换
        
dic = {}
# unique()方法保证数据唯一
occ_arr = feature['occupation'].unique()
# 生成 字符对应数字的 关系表
for i in range(occ_arr.size):
   dic[occ_arr[i]] = i  

# 数值替换字符串        
feature['occupation'] = feature['occupation'].map(dic)    
    
# 4. 切片：训练数据和预测数据  
# 查看数据的形状 (训练的数据必须是二维数据)
feature.shape
    
#训练数据
x_train = feature[:32500]
y_train = target[:32500]

#测试数据
x_test = feature[32500:]
y_test = target[32500:]      

# 5. 生成算法
from sklearn.neighbors import KNeighborsClassifier
# 实例化一个 knn对象, 
# 参数:n_neighbors可调,调到最终预测的是最好的结果.
knn = KNeighborsClassifier(n_neighbors=10)
# fit() 训练函数, (训练数据,训练数据的结果)
knn.fit(x_train,y_train)
    
# 对训练的模型进行评分 (测试数据,测试数据的结果)
knn.score(x_test,y_test)    
    
# 6.预测数据
print('真实的分类结果：',np.array(y_test))
print('模型的分类结果：',knn.predict(x_test))

(3)实例：基于sklearn实现手写数字识别系统

pylot 读取图片：img_arr.shape 查看形状

import pandas as pd
import numpy as np
from sklearn.neighbors import KNeighborsClassifier
# 1、样本数据提取：每张图片对应的numpy数组：0,1,2,3,4,5,6,7,8,9
feature =[]
target =[]
for i in range(10):#0-9 文件夹名称
   for j in range(1,501): #1-500图片名称
      imgpath = './data/'+str(i)+'/'+str(i)+'_'+str(j)+'.bmp'  #图片路径
      img_arr = pld.imread(imgpath)
      feature.append(img_arr)
      target.append(i)   
# 2、把列表转成numpy数组;feature 必须为二维数组；
feature = np.array(feature) #这个feature 里有多个二维数组，
target = np.array(target)

feature.shape 
(5000,28,28) #里面有5000个28*28的二维数组

# 扩展：feature是三维数组；多个二维数组组成的数组是三维数组，多个一维数组组成的数组是二维数组！
# 3、feature变形为二维数组
feature.shape(5000,784)
#4、对样本数据和目标数据进行同步打乱
np.random.seed(10)
np.random.shuffle(feature)
np.random.seed(10)
np.random.shuffle(target)

# 5、对样本数据进行拆分：训练数据和测试数据
x_train = feature[:4950] 
y_train = target[:4950]
x_test = feature[4950:]
y_test = target[4950:]

# 6、对模型进行训练：参数:n_neighbors可调,调到最终预测的评分最好的结果.
from sklearn.neighbors import KNeighborsClassifier
knn = KNeighborsClassifier(n_neighbors=8)
knn.fit(x_train,y_train)  # (训练数据,训练数据的结果)
    
# 7、对训练的模型进行评分 (测试数据,测试数据的结果)
knn.score(x_test,y_test)
# 8、对模型进行测试
print('真实的结果',y_test)
print('模型分类的结果',knn.predict(x_test))

#9、保存训练号的模型
from sklearn.externals import joblib
joblib.dump(knn,'./knn.m')

#10、读取训练好的模型
knn = joblib.load('./knn.m')
#-------------------------------------------------------------------------------------------------
# 11、将外部图片带入模型进行测试
#   注意：外部图片的样本数据要转成和训练模型时候使用的样本图片一样的维度数组    
#       ！！！模型只可以测试类似于测试数据中的特征数据 ！！！  
img_arr = plt.imgread('./数字.jpg')
eight_arr = img_arr[170：260，80:70]  # 截取图片的部分
plt.imshow(eight_arr) #查看截取的数字图片

# 变形为测试数据中的特征数据：feature.shape(5000,784) 每一行是一个一维的784个元素的数组；像素要变为一样
# 12、将eight_arr 对应的图片降维(三维变为二维)：将(65,50,3)变为(28,28)
 eight_arr.mean(axis=2 )  # axis=2 表示去除第三个维度,保留(65,50)保证图片不能变！

# 13、将图片像素进行等比例压缩
import scipy.ndimage as ndimage
data_pre_test = ndimage.zoom(eight_arr,zoom=(28/65,28/50))
eight_arr.shape   #(28,28)

# 14、将压缩好的图片由二维(28,28)变为一维(1,784)
eight_arr = eight_arr(1,784)

# 15、识别外部进行压缩和降维的图片
knn.predict(eight_arr)
array([8])

# -*- coding: UTF-8 -*-
import numpy as np
import operator
from os import listdir
from sklearn.neighbors import KNeighborsClassifier as kNN

"""
函数说明:将32x32的二进制图像转换为1x1024向量。

Parameters:
    filename - 文件名
Returns:
    returnVect - 返回的二进制图像的1x1024向量

"""
def img2vector(filename):
    #创建1x1024零向量
    returnVect = np.zeros((1, 1024))
    #打开文件
    fr = open(filename)
    #按行读取
    for i in range(32):
        #读一行数据
        lineStr = fr.readline()
        #每一行的前32个元素依次添加到returnVect中
        for j in range(32):
            returnVect[0, 32*i+j] = int(lineStr[j])
    #返回转换后的1x1024向量
    return returnVect

"""
函数说明:手写数字分类测试

Parameters:
    无
Returns:
    无

"""
def handwritingClassTest():
    #测试集的Labels
    hwLabels = []
    #返回trainingDigits目录下的文件名
    trainingFileList = listdir('trainingDigits')
    #返回文件夹下文件的个数
    m = len(trainingFileList)
    #初始化训练的Mat矩阵,测试集
    trainingMat = np.zeros((m, 1024))
    #从文件名中解析出训练集的类别
    for i in range(m):
        #获得文件的名字
        fileNameStr = trainingFileList[i]
        #获得分类的数字
        classNumber = int(fileNameStr.split('_')[0])
        #将获得的类别添加到hwLabels中
        hwLabels.append(classNumber)
        #将每一个文件的1x1024数据存储到trainingMat矩阵中
        trainingMat[i,:] = img2vector('trainingDigits/%s' % (fileNameStr))
    #构建kNN分类器
    neigh = kNN(n_neighbors = 3, algorithm = 'auto')
    #拟合模型, trainingMat为训练矩阵,hwLabels为对应的标签
    neigh.fit(trainingMat, hwLabels)
    #返回testDigits目录下的文件列表
    testFileList = listdir('testDigits')
    #错误检测计数
    errorCount = 0.0
    #测试数据的数量
    mTest = len(testFileList)
    #从文件中解析出测试集的类别并进行分类测试
    for i in range(mTest):
        #获得文件的名字
        fileNameStr = testFileList[i]
        #获得分类的数字
        classNumber = int(fileNameStr.split('_')[0])
        #获得测试集的1x1024向量,用于训练
        vectorUnderTest = img2vector('testDigits/%s' % (fileNameStr))
        #获得预测结果
        # classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3)
        classifierResult = neigh.predict(vectorUnderTest)
        print("分类返回结果为%d\t真实结果为%d" % (classifierResult, classNumber))
        if(classifierResult != classNumber):
            errorCount += 1.0
    print("总共错了%d个数据\n错误率为%f%%" % (errorCount, errorCount/mTest * 100))


"""
函数说明:main函数

Parameters:
    无
Returns:
    无

"""
if __name__ == '__main__':
    handwritingClassTest()