机器学习（2）k近邻算法

2019-02-05

一、k-近邻

k近邻法(k-nearest neighbor,k-NN)是1967年由Cover T和Hart P提出的一种基本分类与回归方法。它的算法的描述为：

计算测试数据与各个训练数据之间的距离（欧式距离或曼哈顿距离）；
按照距离的递增关系进行排序；
选取距离最小的K个点；
确定前K个点所在类别的出现频率；
返回前K个点中出现频率最高的类别作为测试数据的预测分类。

优点：

精度高
对异常值不敏感
无数据输入假定

缺点：

计算复杂度高
空间复杂度高

二、分类示例1-电影分类

问题背景

根据电影的打斗镜头和接吻镜头，来判定电影类型

电影	打斗镜头	接吻镜头	电影类型
电影1	3	104	爱情片
电影2	2	100	爱情片
电影3	1	81	爱情片
电影4	101	10	动作片
电影5	99	5	动作片
电影6	98	2	动作片
？	18	90	？

采用欧式距离（可理解为直线距离）计算未知电影和已知的距离，当前示例有2个特征，为2维空间，通过计算可得：

电影	与未知电影的距离
电影1	20.5
电影2	18.7
电影3	19.2
电影4	115.3
电影5	117.4
电影6	118.9

假定k=3，则3个靠近的电影依次是电影2、电影3和电影1，这三部电影都是爱情片，则我们判定未知电影是爱情片。

python实现

主要算法实现：kNN.py

'''
kNN: k Nearest Neighbors

Input:      inX: 用于分类的数据 (1xN，测试集)
            dataSet: 用于训练的数据 (MxN，训练集)
            labels: 已知数据集的分类标签 (1xM)
            k: 选择距离最小的k个点
            
Output:     结果-分类标签
'''
from numpy import *

def classify0(inX, dataSet, labels, k):
    #dataSet的行数
    dataSetSize = dataSet.shape[0]
    #tile在列向量方向复制dataSetSize，重复dataSetSize次
    diffMat = tile(inX, (dataSetSize,1)) - dataSet
    #二维相减后分别平方
    sqDiffMat = diffMat**2
    #sum(1)为行相加
    sqDistances = sqDiffMat.sum(axis=1)
    #开方得到欧式距离
    distances = sqDistances**0.5
    #返回distances中元素从小到大排序后的索引值
    sortedDistIndicies = distances.argsort()     
    classCount={}
    #排序后取k个距离最近的数据
    for i in range(k):
        voteIlabel = labels[sortedDistIndicies[i]]
        classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1
    #降序排列字典
    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
    #返回最可能的数据集分类
    return sortedClassCount[0][0]

测试数据集分类

import kNN
import numpy as np

def createDataSet():
    groups = np.array([[3,104],[2,100],[1,81],[101,10],[99,5],[98,2]])
    labels = ['爱情片','爱情片','爱情片','动作片','动作片','动作片']
    return groups, labels

groups,labels=createDataSet()
result =kNN.classify0([18,90],groups,labels,3)
print(result)

三、分类示例2-男士魅力分类

收集数据

海伦女士一直使用在线约会网站寻找适合自己的约会对象。尽管约会网站会推荐不同的任选，但她并不是喜欢每一个人。经过一番总结，她发现自己交往过的人可以进行如下分类：

没有魅力的人
魅力一般的人
极具魅力的人

海伦收集约会数据已经有了一段时间，她把这些数据存放在文本文件datingDataSet.txt中，每个样本数据占据一行，总共有1000行。

海伦收集的样本数据主要包含以下3种特征：

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

准备数据

'''
file2matrix: 文件转矩阵

Input:      filename: 文件路径

Output:     returnMat： 数据集
            classLabelVector： 标签向量
'''

def file2matrix(filename):
    fr = open(filename)
    numberOfLines = len(fr.readlines())         #get the number of lines in the file
    returnMat = zeros((numberOfLines,3))        #prepare matrix to return
    classLabelVector = []                       #prepare labels return   
    fr = open(filename)
    index = 0
    for line in fr.readlines():
        line = line.strip()
        listFromLine = line.split('\t')
        returnMat[index,:] = listFromLine[0:3]
        classLabelVector.append(int(listFromLine[-1]))
        index += 1
    return returnMat,classLabelVector

调用方法将文件转成矩阵

1	datingDataMat,datingLabels = kNN.file2matrix('datingDataSet.txt')

分析数据

使用matplotlib进行数据可视化，将3个特征两两进行分析：

import kNN

from matplotlib.font_manager import FontProperties
import matplotlib.lines as mlines
import matplotlib.pyplot as plt

def showdatas(datingDataMat, datingLabels):
    # 设置汉字字体，避免乱码
    font = FontProperties(fname=r"/Library/Fonts/Songti.ttc", size=14)
    # 将fig画布分隔成1行3列,被分为3个区域,axs[0]表示第一个区域。（也可分成2行2列成为4个区域，axs[0][0]表示第一个区域）
    fig, axs = plt.subplots(nrows=1, ncols=3, sharex=False, sharey=False, figsize=(18, 6))

    LabelsColors = []
    # 标签分类中：1代表没有魅力,2代表魅力一般,3代表极具魅力
    for i in datingLabels:
        if i == 1:
            LabelsColors.append('black')
        if i == 2:
            LabelsColors.append('orange')
        if i == 3:
            LabelsColors.append('red')
    # 散点图1,以datingDataMat矩阵的第1、2列
    axs[0].scatter(x=datingDataMat[:, 0], y=datingDataMat[:, 1], color=LabelsColors, s=15, alpha=.5)
    # 设置标题,x轴label,y轴label
    axs0_xlabel_text = axs[0].set_xlabel(u'每年获得的飞行常客里程数', FontProperties=font)
    axs0_ylabel_text = axs[0].set_ylabel(u'玩视频游戏所消耗时间占', FontProperties=font)
    plt.setp(axs0_xlabel_text, size=10, weight='bold', color='black')
    plt.setp(axs0_ylabel_text, size=10, weight='bold', color='black')

    # 散点图2,以datingDataMat矩阵1、3列
    axs[1].scatter(x=datingDataMat[:, 0], y=datingDataMat[:, 2], color=LabelsColors, s=15, alpha=.5)
    axs1_xlabel_text = axs[1].set_xlabel(u'每年获得的飞行常客里程数', FontProperties=font)
    axs1_ylabel_text = axs[1].set_ylabel(u'每周消费的冰激淋公升数', FontProperties=font)
    plt.setp(axs1_xlabel_text, size=10, weight='bold', color='black')
    plt.setp(axs1_ylabel_text, size=10, weight='bold', color='black')

    # 散点图3,以datingDataMat矩阵的第2、3列
    axs[2].scatter(x=datingDataMat[:, 1], y=datingDataMat[:, 2], color=LabelsColors, s=15, alpha=.5)
    axs2_xlabel_text = axs[2].set_xlabel(u'玩视频游戏所消耗时间占比', FontProperties=font)
    axs2_ylabel_text = axs[2].set_ylabel(u'每周消费的冰激淋公升数', FontProperties=font)
    plt.setp(axs2_xlabel_text, size=10, weight='bold', color='black')
    plt.setp(axs2_ylabel_text, size=10, weight='bold', color='black')

    # 设置图例
    didntLike = mlines.Line2D([], [], color='black', marker='.',
                              markersize=6, label='didntLike')
    smallDoses = mlines.Line2D([], [], color='orange', marker='.',
                               markersize=6, label='smallDoses')
    largeDoses = mlines.Line2D([], [], color='red', marker='.',
                               markersize=6, label='largeDoses')
    axs[0].legend(handles=[didntLike, smallDoses, largeDoses])
    axs[1].legend(handles=[didntLike, smallDoses, largeDoses])
    axs[2].legend(handles=[didntLike, smallDoses, largeDoses])
    # 显示图片
    plt.show()

datingDataMat,datingLabels = kNN.file2matrix('datingDataSet.txt')
showdatas(datingDataMat, datingLabels)

通过数据可以很直观的发现规律，比如海伦喜欢的人的特征包括：飞行常客中等（不能太闲和太忙），要玩视频游戏多的。至于是否吃冰淇淋看起来不重要。

准备数据：数据归一化

当计算本例的距离时，会发现飞行常客里程数值过大，如果三个特征同样重要，则需要归一化，保证权重相同。下面的公式可以将任意取值范围的特征值转化为0到1区间内的值：

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

其中min和max分别是数据集中的最小特征值和最大特征值。

"""
函数说明:对数据进行归一化

Parameters:
    dataSet - 特征矩阵
Returns:
    normDataSet - 归一化后的特征矩阵
    ranges - 数据范围
    minVals - 数据最小值
"""

def autoNorm(dataSet):
    #获取某个特征纬度的最大和最小值
    minVals = dataSet.min(0)
    maxVals = dataSet.max(0)
    #根据最大值和最小值确定范围
    ranges = maxVals - minVals
    #返回dataSet的矩阵行列数
    normDataSet = zeros(shape(dataSet))
    m = dataSet.shape[0]
    #根据公式，newValue = (oldValue - min) / (max - min)。先原始值减去最小值
    normDataSet = dataSet - tile(minVals, (m,1))
    #再除以最大和最小值的差,得到归一化数据
    normDataSet = normDataSet/tile(ranges, (m,1))
    #返回归一化数据结果,数据范围,最小值
    return normDataSet, ranges, minVals

测试算法：验证分类器

def datingClassTest():
    #取10%比例数据进行测试
    hoRatio = 0.10
    datingDataMat,datingLabels = kNN.file2matrix('datingDataSet.txt')
    normMat, ranges, minVals = kNN.autoNorm(datingDataMat)
    m = normMat.shape[0]
    numTestVecs = int(m*hoRatio)
    errorCount = 0.0
    for i in range(numTestVecs):
        classifierResult = kNN.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)))
    print ("错误数: %d" % errorCount)

if __name__ == '__main__':
    #分类器测试
	datingClassTest()

得到的错误率为5%，可调整k值和测试数据比例，得到不同的错误率。

1 2	错误率: 0.050000 错误数: 5

使用算法

def classifyMan(man):
    #输出结果
    resultList = ['没有魅力','魅力一般','极具魅力']
    #打开的文件名
    filename = "datingDataSet.txt"
    #打开并处理数据
    datingDataMat, datingLabels = kNN.file2matrix("datingDataSet.txt")
    #训练集归一化
    normMat, ranges, minVals = kNN.autoNorm(datingDataMat)
    #测试集归一化
    norminArr = (man - minVals) / ranges
    #返回分类结果
    classifierResult = kNN.classify0(norminArr, normMat, datingLabels, 3)
    #打印结果
    return resultList[classifierResult-1]

使用算法进行分类：

#使用kNN算法分类
man1=np.array([ 4000,4, 1.1])
man2=np.array([ 20000,15, 1.1])
print("man1 is : %s" % classifyMan(man1))
print("man2 is : %s" % classifyMan(man2))

结果如下：

1 2	man1 is :魅力一般 man2 is :极具魅力

四、分类示例3-手写数字识别

trainingDigits文件夹为训练集，testDigits文件夹为测试集。

import kNN

import numpy as np
from os import listdir

def img2vector(filename):
    returnVect = np.zeros((1,1024))
    fr = open(filename)
    for i in range(32):
        lineStr = fr.readline()
        for j in range(32):
            returnVect[0,32*i+j] = int(lineStr[j])
    return returnVect

def handwritingClassTest():
    hwLabels = []
    trainingFileList = listdir('trainingDigits')
    m = len(trainingFileList)
    trainingMat = np.zeros((m,1024))
    for i in range(m):
        fileNameStr = trainingFileList[i]
        fileStr = fileNameStr.split('.')[0]
        classNumStr = int(fileStr.split('_')[0])
        hwLabels.append(classNumStr)
        trainingMat[i,:] = img2vector('trainingDigits/%s' % fileNameStr)
    testFileList = listdir('testDigits')
    errorCount = 0.0
    mTest = len(testFileList)
    for i in range(mTest):
        fileNameStr = testFileList[i]
        fileStr = fileNameStr.split('.')[0]
        classNumStr = int(fileStr.split('_')[0])
        vectorUnderTest = img2vector('testDigits/%s' % fileNameStr)
        classifierResult = kNN.classify0(vectorUnderTest, trainingMat, hwLabels, 3)
        print( "分类器计算结果: %d, 答案: %d" % (classifierResult, classNumStr))
        if (classifierResult != classNumStr): errorCount += 1.0
    print ("\n错误率: %f" % (errorCount/float(mTest)))
    print ("错误数: %d" % errorCount)

if __name__ == '__main__':
    handwritingClassTest()

学习结果如下：

...
分类器计算结果: 9, 真正答案: 9
分类器计算结果: 9, 真正答案: 9

错误率: 0.010571

错误数: 10

五、相关代码

『代码传送门』