K-近邻算法

• 优点：精度高，对异常值不敏感，无数据输入假定
• 缺点：计算复杂度高，空间复杂度高
• 适用数据范围：数值型和标称型

K-近邻算法的一般流程

1. 收集数据：可以使用任何方法
2. 准备数据：距离计算所需要的数值，最好是结构化的数据格式
3. 分析数据：可以使用任何方法
4. 训练方法：此步骤不适用于K-近邻算法
5. 测试算法：计算错误率
6. 使用算法：首先需要输入样本数据和结构化的输出结果，然后运行K-近邻算法判定输入数据分别属于那个分类，最后应用对计算出的分类执行后续的处理
   tile（A,rep）:重复A的各个维度

from numpy import *
import operator
def createDataSet():
    group=array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
    labels=['A','B','C','D']
    return group,labels

def classify0(inX,dataSet,labels,k):
    dataSetSize=dataSet.shape[0]
    #距离计算
    diffMat=tile(inX,(dataSetSize,1))-dataSet
    sqDoffMat=diffMat**2
    sqDistances=sqDoffMat.sum(axis=1)
    distances=sqDistances**0.5
    sortedDistIndices=distances.argsort()
    classCount={}
    #选择激励最小的K个点
    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]   

group,labels=createDataSet()
classify0([0,0],group,labels,3)

'C'

函数详解

tile([1,2],2)

array([1, 2, 1, 2])

tile([1,2],(2,2))

array([[1, 2, 1, 2],
       [1, 2, 1, 2]])

x=array([[1,2,3],[2,3,4]])
print(x.shape)
print(x.shape[0])

(2, 3)
2

x=array([[1,2,3],[2,3,4]])
print(x**2)

[[ 1  4  9]
 [ 4  9 16]]

x = np.array([[0, 3], [2, 2]])
np.argsort(x, axis=0)
np.argsort(x, axis=1)

array([[0, 1],
       [1, 0]])
array([[0, 1],
       [0, 1]])

dict = {
   'Name': 'Zara', 'Age': 27}
print "Value : %s" %  dict.get('Age')
print "Value : %s" %  dict.get('Sex', "Never")

Value : 27
Value : Never

""
Python 字典(Dictionary) items() 函数以列表返回可遍历的(键, 值) 元组数组
""
dict = {
   'Google': 'www.google.com', 'Runoob': 'www.runoob.com', 'taobao': 'www.taobao.com'}

print "字典值 : %s" %  dict.items()

# 遍历字典列表
for key,values in  dict.items():
    print key,values

字典值 : [('Google', 'www.google.com'), ('taobao', 'www.taobao.com'), ('Runoob', 'www.runoob.com')]
Google www.google.com
taobao www.taobao.com
Runoob www.runoob.com

#operator库块提供了一系列的函数操作。比如，operator.add(x, y)等于x+y 
abs(...)
        abs(a) -- Same as abs(a).
and_(...)
        and_(a, b) -- Same as a & b.
contains(...)
        contains(a, b) -- Same as b in a (note reversed operands).
eq(...)
        eq(a, b) -- Same as a==b.

operator模块提供的itemgetter函数用于获取对象的哪些维的数据，参数为一些序号。operator.itemgetter函数获取的不是值，而是定义了一个函数，通过该函数作用到对象上才能获取值。

a = [1,2,3] 
>>> b=operator.itemgetter(1)      //定义函数b，获取对象的第1个域的值
>>> b(a) 

2

>>> b=operator.itemgetter(1,0)  //定义函数b，获取对象的第1个域和第0个的值
>>> b(a) 
(2, 1)

sorted函数用来排序，sorted(iterable[, cmp[, key[, reverse]]])

其中key的参数为一个函数或者lambda函数。所以itemgetter可以用来当key的参数

a = [(‘john’, ‘A’, 15), (‘jane’, ‘B’, 12), (‘dave’, ‘B’, 10)]

根据第二个域和第三个域进行排序

sorted(students, key=operator.itemgetter(1,2))
只要是可迭代对象都可以用sorted 。

sorted(itrearble, cmp=None, key=None, reverse=False)

=号后面是默认值 默认是升序排序的， 如果想让结果降序排列，用reverse=True

最后会将排序的结果放到一个新的列表中， 而不是对iterable本身进行修改。

1, 简单排序

sorted('123456')  字符串

['1', '2', '3', '4', '5', '6']

sorted([1,4,5,2,3,6])  列表
[1, 2, 3, 4, 5, 6]

sorted({
    1:'q',3:'c',2:'g'}) 字典， 默认对字典的键进行排序
[1, 2, 3]

 sorted({
    1:'q',3:'c',2:'g'}.keys())  对字典的键
[1, 2, 3]

sorted({
    1:'q',3:'c',2:'g'}.values())  对字典的值
['c', 'g', 'q']

sorted({
    1:'q',3:'c',2:'g'}.items())  对键值对组成的元组的列表
[(1, 'q'), (2, 'g'), (3, 'c')]

自定义比较函数

def comp(x, y):
if x < y:
return 1
elif x > y:
return -1
else:
return 0

nums = [3, 2, 8 ,0 , 1]
nums.sort(comp)
print nums # 降序排序[8, 3, 2, 1, 0]
nums.sort(cmp) # 调用内建函数cmp ，升序排序
print nums # 降序排序[0, 1, 2, 3, 8]

key在使用时必须提供一个排序过程总调用的函数

x = ['mmm', 'mm', 'mm', 'm' ]
x.sort(key = len)
print x # ['m', 'mm', 'mm', 'mmm']

在约会网站上使用K近邻算法

1. 收集算法：提供文本文件
2. 准备数据：使用Python解析文本文件
3. 分析数据：使用matplotlib画二维扩散图
4. 训练算法：不适用K近邻算法
5. 测试算法：使用海伦提供的部分数据作为测试样本。
   测试样本与非测试样本的区别在于：测试样本是已经完成分类的 数据，如果预测分类与实际类别不同，则标记为一个错误

6. 使用算法：产生简单的命令行程序，然后海伦可以输入一些特征数据以判断对方是否为自己喜欢的类型

   完整代码：

from numpy import *
import operator

def classify0(inX,dataSet,labels,k):
    dataSetSize=dataSet.shape[0]
    #距离计算
    diffMat=tile(inX,(dataSetSize,1))-dataSet
    sqDoffMat=diffMat**2
    sqDistances=sqDoffMat.sum(axis=1)
    distances=sqDistances**0.5
    sortedDistIndices=distances.argsort()
    classCount={}
    #选择激励最小的K个点
    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=zeros((numberOfLines,3))
    classLabelVector=[]
    index=0
    for line in arrayOLines:
        #跳过所有的空格字符，使用tab‘\t’分割数据
        line=line.strip()
        listFromLine=line.split('\t')
        returnMat[index,:]=listFromLine[0:3]
        classLabelVector.append(int(listFromLine[-1]))
        index+=1
    return returnMat,classLabelVector
data_path='E:/dataset/machinelearninginaction/Ch02/'
datMat,datLabel=file2matrix(data_path+'datingTestSet2.txt')
print(datMat)
print(datLabel[0:20])
#分析数据：使用matplotlib创建散点图
import matplotlib
import matplotlib.pyplot as plt
fig=plt.figure()
ax=fig.add_subplot(111)
ax.scatter(datMat[:,0],datMat[:,1],
           15.0*array(datLabel),15.0*array(datLabel))
plt.show()
#准备数据：归一化数据
def autoNorm(dataSet):
    minVals=dataSet.min(0)
    maxVals=dataSet.max(0)
    ranges=maxVals-minVals
    m=dataSet.shape[0]
    normData=dataSet-tile(minVals,(m,1))
    normData=normData/tile(ranges,(m,1))
    return normData,ranges,minVals
normData,ranges,minVals=autoNorm(datMat)
print(normData)
print(ranges)
#测试算法：作为完整程序验证分类器
def datingClassTest():
    hoRatio=0.10
    datingDataMat,datingDatalabel=file2matrix(data_path+\
                                              'datingTestSet2.txt')
    norm,range1,minVals=autoNorm(datingDataMat)
    m=norm.shape[0]
    numTest=int(m*hoRatio)
    errorCount=0
    for i in range(numTest):
        classResult=classify0(norm[i,:],norm[numTest:m,:],\
                              datLabel[numTest:m],3)
        print('分类器学习的结果，%d,真实值是%d'%(classResult,datingDatalabel[i]))
        if(classResult!=datingDatalabel[i]):errorCount+=1
    print("错误率是:%f"%(errorCount/numTest))
if __name__ == '__main__':
    datingClassTest()

实例：手写识别系统

1. 收集数据：提供文本文件
2. 准备数据：编写函数img2vector函数，将图像格式转换为分类器的向量形式
3. 分析数据：在Python命令提示符中检查数据，确保它符合要求
4. 训练算法：此步骤不适用KNN
5. 测试算法：编写函数使用提供的部分数据集作为测试样本，测试样本与非测试样本的区别在于测试样本是已经完成分类的数据，如果测试分类与实际类别不同，则标记为一个错误
6. 使用算法：本例没有完成此步骤，若你感兴趣可以构建完整的应用程序，从图像中提取数字，并完成数字识别，美国的邮件分拣系统就是一个实际运行的类似系统

准备数据：将图像转换为测试向量

from numpy import *
import operator
def img2vector(filename):
    file_path = "E:/dataset/machinelearninginaction/Ch02/digits/trainingDigits/"
    returnVec=zeros((1,1024))
    fr=open(file_path+filename)
    for i2 in range(32):
        lineStr=fr.readline()
        for j2 in range(32):
            returnVec[0,32*i2+j2]=int(lineStr[j2])
    return returnVec

def classify0(inX,dataSet,labels,k):
    dataSetSize=dataSet.shape[0]
    #距离计算
    diffMat=tile(inX,(dataSetSize,1))-dataSet
    sqDoffMat=diffMat**2
    sqDistances=sqDoffMat.sum(axis=1)
    distances=sqDistances**0.5
    sortedDistIndices=distances.argsort()
    classCount={}
    #选择激励最小的K个点
    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]

import os
def handWritingClassTest():
    hwLabels=[]
    trainingFileList=os.listdir('E:/dataset/machinelearninginaction/Ch02/digits/trainingDigits')
    m=len(trainingFileList)
    print(m)
    trainVec=zeros((m,1024))
    #traingLabel=zeros((m,1))
    traingLabel=[]
    i=0
    for filename in trainingFileList:
        img=img2vector(filename)
        trainVec[i,:]=img
        label=filename.split('_')[0]
        traingLabel.append(int(label))
        i+=1
    testFileList=os.listdir("E:/dataset/machinelearninginaction/Ch02/digits/testDigits")
    #n=len(testFileList)
    i=0
    for filename in testFileList:
        img=img2vector(filename)
        #testVect[i]=img
        resu=classify0(img,trainVec,traingLabel,3)
        label = filename.split('_')[0]
        print("predict:%d    the true value:%d"%(resu,int(label)))
        if(resu!=label):
            i+=1
    print("the precision is %f"%(i/len(testFileList)))

file_path="E:/dataset/machinelearninginaction/Ch02/digits/trainingDigits/"
#testVec=img2vector(file_path+"0_0.txt")
#print(testVec[0:32])
handWritingClassTest()

the precision is 1.000000