机器学习实战（一）k-邻近算法

前言

最近开始看机器学习实战这本书，所以专门定期写一点自己的学习笔记以及分析上来

机器学习的应用：

“现今，机器学习已经用于多个领域，远超出大多数人的想象，下面就是假想的一日，其中很多场景都会碰到机器学习：假设你想起今天是某位朋友的生日，打算通过邮局给她寄一张生日贺卡。你打开浏览器搜索趣味卡片，搜索引擎将记录这次点击，并从中学习以优化下次搜索结果。然后，你检查电子邮件系统，此时垃圾邮件过滤器已经在后台自动过滤垃圾广告邮件，并将其放在垃圾箱内。接着你去购买这张生日卡片，并给你朋友的孩子挑选了一些尿布。结账时，收银员给了你一张1美元的优惠券，可以用于购买6罐装啤酒。之所以你会得到这张优惠券，是因为款台收费软件基于之前的统计知识，认为买尿布的人往往也会买啤酒。然后你去邮局邮递这张贺卡，手写识别软件识别出邮寄地址，并将贺卡发送给正确的邮车。当天你还去了贷款申请机构，查看自己是否能够申请贷款，办事员并不是直接给出结果，而是将你最近的金融活动信息输入计算机，有软件来判断你是否合格。最后，你还去赌场找些乐子，当你不如前门时，尾随你进来的一个家伙被突然出现的保安给拦了下来。“对不起，索普先生，我们不得不请你离开。我们不欢迎老千”。“

k-邻近算法

k-邻近算法概述

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

缺点：计算复杂度高、空间复杂度高

适用数据范围：数值型和标称型

工作原理：存在一个样本数据集合，也称作训练样本集，并且样本集中每个数据存在标签，即我们知道样本集中每一数据对应的特征与所属分类的对应关系。输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据的分类标签，一般来说我们只选择样本集中前k个最相似的数据，这就是k-邻近算法中k的出处，通常k是不大于20的整数。最后选择k个最相似数据中出现次数最多的分类，作为新数据的分类。

k-邻近算法一般流程

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

knn分类，传入待分类向量、训练集、标签、k值作为参数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def classify0(inX,dataSet,labels,k):
    dataSetSize=dataSet.shape[0]
    diffMat=tile(inX,(dataSetSize,1))-dataSet #tile函数生成一个列为dataSetSize行为1的矩阵并且减去dataSet，用于计算距离
    print diffMat
    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#获取字典中下标第0个值并将该值加1
    sortedClassCount=sorted(classCount.iteritems(),
                            key=operator.itemgetter(1),reverse=True)
    return sortedClassCount[0][0]
1
diffMat=tile(inX,(dataSetSize,1))-dataSet

tile函数位于python模块 numpy.lib.shape_base中，他的功能是重复某个数组。比如tile(A,n)，功能是将数组A重复n次，构成一个新的数组

函数格式tile(A,reps)

A和reps都是array_like

A的类型众多，几乎所有类型都可以：array, list, tuple, dict, matrix以及基本数据类型int, string, float以及bool类型。

reps的类型也很多，可以是tuple，list, dict, array, int, bool.但不可以是float, string, matrix类型。

1
2
3
4
>>> a=[[1,2,3],[5,4]]
>>> tile(a,[2,3])
array([[[1, 2, 3], [5, 4], [1, 2, 3], [5, 4], [1, 2, 3], [5, 4]],
       [[1, 2, 3], [5, 4], [1, 2, 3], [5, 4], [1, 2, 3], [5, 4]]])
1
sqDistances=sqDiffMat.sum(axis=1)

看起来挺简单的样子，但是在给sum函数中加入参数。sum（a，axis=0）或者是.sum(axis=1) 就有点不解了

在我实验以后发现 我们平时用的sum应该是默认的axis=0 就是普通的相加

而当加入axis=1以后就是将一个矩阵的每一行向量相加

例如：

import numpy as np

np.sum([[0,1,2],[2,1,3],axis=1)

结果就是：array（[3,6]）

1
sortedDistIndicies=distances.argsort()

argsort函数

argsort函数返回的是数组值从小到大的索引值

Examples：

-——-

One dimensional array:一维数组

>>> x = np.array([3, 1, 2])

>>> np.argsort(x)

array([1, 2, 0])

准备数据：从文本中解析数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def file2matrix(filename):
    fr=open(filename)
    arrayOLines=fr.readlines()
    numberOfLines=len(arrayOLines)
    returnMat=zeros((numberOfLines,3))#初始化一个三维数组用于存储特征
    classLabelVector=[]
    index=0
    for line in arrayOLines:
        line=line.strip()
        listFromLine=line.split('\t')
        returnMat[index,:]=listFromLine[0:3]#读取每一行的前三个特征
        classLabelVector.append(int(listFromLine[-1]))#读取最后一行为该数据的类型
        index+=1
    return  returnMat,classLabelVector

准备数据：归一化

1
2
3
4
5
6
7
8
9
def autoNorm(dataSet):
    minVals=dataSet.min(0)#min(0)为读取每一列的最小值（否则会读取每一行的最小值，minVals为一个一维数组，每个值为该列的最小值
    maxVals=dataSet.max(0)#同上
    ranges=maxVals-minVals
    normDataSet=zeros(shape(dataSet))#shape将会返回该矩阵行数和列数
    m=dataSet.shape[0]#shape[0]返回列数
    normDataSet=dataSet-tile(minVals,(m,1))
    normDataSet=normDataSet/tile(ranges,(m,1))
    return normDataSet,ranges,minVals

测试和使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def datingClassTest():
    hoRatio=0.10
    datingDataMat,datingLabels=file2matrix('datingTestSet2.txt')
    normMat,ranges,minVals=autoNorm(datingDataMat)#返回正规的矩阵，表示特征范围的矩阵，每个特征最小值的矩阵
    m=normMat.shape[0]
    print m
    numTestVecs=10
    errorCount=0.0
    for i in range(numTestVecs):
        classifierResult=classify0(normMat[i,:],normMat[numTestVecs:m,:],\
                                   datingLabels[numTestVecs:m],3)
        print "the classifier came back with:%d the real answer is %d"\
        %(classifierResult,datingLabels[i])
        if(classifierResult!=datingLabels[i]):errorCount+=1.0
    print "the total error rate is :%f"%(errorCount/float(numTestVecs))

Comments

⬆︎TOP