k-近邻算法

云计算 waitig 607℃ 百度已收录 0评论

这篇文章算是机器学习算法文章的开头篇,k-近邻算法个人觉得比较有效而且简单,这一系列的学习我感觉将会很有趣,因为这些算法能直接被用来解决一些实际的问题,把一些枯燥的数学算法用来解决问题,我也认为这是最好的学习方法。本系列文章结合机器学习实战学习做的一些学习笔记。
k-近邻算法简单说就是采用测量不同特征值之间的距离方法进行分类,这是机器学习实战所写的,我觉得不够完整,首先特征值必须是数值类型,否则欧氏距离无法计算,目标值也必须是类别分类。后面我会结合书上两个例子改进约会网站来进一步分析。

1.算法描述

输入:训练数据集
T={(x1,y1),(x2,y2),…,(xN,yN))}
其中,xi∈X⊆Rn 为实例的特征向量,yi∈Y={c1,c2,…,cK} 为实例的类别,i=1,2,…,N ;新输入的实例表示为x;
输出:实例x所属的类y
分类步骤:

根据给定的距离度量,在训练集T中找出与x最邻近的k个点,涵盖这k个点的x的领域记作Nk(x)
在Nk(x)中根据分类决策规则(如多数表决)决定x的类别y:
这里写图片描述
上式中,I为指示函数,即当 yi=cj 时I为1,否则I为0。
借鉴机器学习算法系列——k近邻分类法这篇博客

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

  • 准备数据:从文本文件中解析数据
    这里有一个约会数据共1000行datingTestSet.txt样本,主要包含以下三个特征:

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

以及目标值:

 - 不喜欢的人
   魅力一般的
   极具魅力的人
  • 代码分析实现
    k-近邻算法
def classify0(inX, dataSet, labels, k):
    dataSetSize = dataSet.shape[0]
    diffMat = tile(inX, (dataSetSize, 1)) - dataSet
    sqDiffMat = diffMat**2
    sqDistances = sqDiffMat.sum(axis=1)
    distances = sqDistances**0.5
    sortedDistIndicies = distances.argsort()
    classCount = {}
    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]

这里inX对应输入向量,dataSet对应输入训练样本集,labels对应标签向量,k也就是算法名k对应选取前k个最领近的数据,另外就是欧式距离实现。将函数加入kNN模块

def file2matrix(filename):
    fr = open(filename)
    arrayOLines = fr.readlines()#注意这里读入的是readlines而不是readline
    numberOfLines = len(arrayOLines)
    returnMat = zeros((numberOfLines, 3))#这里创建的是1000行3列的0矩阵
    classLabelVector = []
    index = 0
    for line in arrayOLines:
        line = line.strip()
        listFromLine = line.split('\t')
        returnMat[index,:] = listFromLine[0:3]
        if listFromLine[-1] == 'largeDoses':
            listFromLine[-1] = 3
        elif listFromLine[-1] == 'smallDoses':
            listFromLine[-1] = 2
        else:
            listFromLine[-1] = 1
        classLabelVector.append(listFromLine[-1])
        index += 1
    return returnMat,classLabelVector

首先我们创建python文件kNN.py,然后将上面函数加入,这个函数主要就是将文本文件中的第四列分类用数字1,2,3代替分类,并将文本1,2,3列的数据读入矩阵和数组中。

>>>import kNN
>>>datingDataMat,datingLabels = kNN.file2matrix('datingTestSet.txt')

这样我们就把文本第四行变成数值分类了。


  • 使用Matplotlib创建散点图

这里写图片描述
附上代码:

import kNN
import matplotlib
import matplotlib.pyplot as plt
from numpy import *
matplotlib.rcParams['font.family'] = 'SimHei'

datingDataMat, datingLabels = kNN.file2matrix('datingTestSet.txt')
n=1000
xcord1 = []; ycord1 = []
xcord2 = []; ycord2 = []
xcord3 = []; ycord3 = []
for i in range(n):
    if(datingLabels[i] == 1):
        xcord1.append(datingDataMat[i][0]);ycord1.append(datingDataMat[i][1])
    elif(datingLabels[i] == 2):
        xcord2.append(datingDataMat[i][0]);ycord2.append(datingDataMat[i][1])
    else:
        xcord3.append(datingDataMat[i][0]);ycord3.append(datingDataMat[i][1])
fig = plt.figure()
ax = fig.add_subplot(111)
type1 = ax.scatter(xcord1, ycord1, s=20, c='red')
type2 = ax.scatter(xcord2, ycord2, s=30, c='green')
type3 = ax.scatter(xcord3, ycord3, s=50, c='blue')
ax.legend([type1,type2,type3],["不喜欢","魅力一般","极具魅力"],loc=2)
ax.axis([-5000,100000,-2,25])
plt.xlabel("每年获取的飞行常客里程数")
plt.ylabel("玩视频游戏所耗的时间百分比")
plt.show()

这里可以看看matplotlib怎么画三点图,通过上图我们看到大致三类分的还是比较明显,玩游戏少,飞行里程多的人果然还是最有魅力的啊~0.0~

  • 归一化数值
    这里写图片描述
    观察数据我们很容易发现特征值的范围是不一样的,对我们的计算结果影响不一样,这里我们需要数值归一化:
    newValue = (oldValue – min)/ (max – min)
def autoNorm(dataSet):
    minVals = dataSet.min(0)
    maxVals = dataSet.max(0)
    ranges = maxVals - minVals
    normDataSet = zeros(shape(dataSet))
    m = dataSet.shape[0]
    normDataSet = dataSet - tile(minVals, (m,1))
    normDataSet = normDataSet/tile(ranges,(m,1))
    return normDataSet, ranges , minVals

继续把上面函数加入kNN代码块里面

>>>normMat, ranges, minVals = kNN.autoNorm(datingDataMat)

结果如下:
这里写图片描述
可以看到范围都在0-1内。

  • 利用测试集测试代码
def datingClassTest():
    hoRatio = 0.10
    datingDataMat, datingLabels = file2matrix('datingTestSet.txt')
    normMat, ranges, minVals = autoNorm(datingDataMat)
    m = normMat.shape[0]
    numTestVecs = int(m*hoRatio)
    print(numTestVecs)
    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)))

这里我们选取样本数据集的10%作为测试集,90%作为训练集,由于数据集本来就是随机的,所以随便选取10%,如果还需要随机可以用Random库来随机选取,这里我就选前10%。

>>>kNN.datingClassTest()

运行结果如下:
这里写图片描述
可以看到这个算法对这个约会数据吻合的还不错,错误率只有5%,接下来我们要对随便一个人输入他的三个特征,程序会给出对他的喜欢程度(~0.0~)

def classifyPerson():
    resultList = ['一点不喜欢','有点喜欢','很喜欢']
    percentTats = float(input("玩视频游戏的时间百分比?"))
    ffMile = float(input("每年飞行里程数:"))
    iceCream = float(input("每年吃冰淇淋量(公升)"))
    datingDataMat, datingLabels = file2matrix('datingTestSet.txt')
    normMat, ranges, minVals = autoNorm(datingDataMat)
    inArr = array([ffMile,percentTats,iceCream])
    classifierResult = classify0((inArr-minVals)/ranges,normMat,datingLabels,3)
    print("你可能对这个人:",resultList[classifierResult - 1])

将上述函数依旧加入kNN模块,通过输入三个特征值就可以得到实际结果了!!!

<<<kNN.classifyPerson()

运行结果如下:
这里写图片描述
~0.0~对我似不似很喜欢,哈哈哈,由于数据特征值过少,而且这是国外的数据,我实在搞不懂吃冰淇淋跟这有什么关系。。。所以可能结果不是很准确,不过没关系,通过这个例子对k-近邻算法理解是不是更深刻了一些。


本文由【waitig】发表在等英博客
本文固定链接:k-近邻算法
欢迎关注本站官方公众号,每日都有干货分享!
等英博客官方公众号
点赞 (0)分享 (0)