机器学习实战一(K-邻近算法(KNN))

一、概述

1. 原理:

  • 工作机制:给定测试样本,基于某种距离度量找出训练集中的与其最靠近的k个训练样本,然后基于这k个“邻居”的信息来进行预测.
  • 通常k是不大于20的整数

2. 优缺点

  • 优点:精度高、对异常值不敏感、无数据输入假定
  • 缺点:
    • 计算复杂度高、空间复杂度高,占用存储空间
    • 无法给出数据的内在含义
  • 适用数据范围:数值型和标称型

3. 懒惰算法:

  • 此类学习技术在训练阶段仅仅把样本保存起来
  • ==训练开支为零==,待收到测试样本后再进行处理

二、算法流程

  1. 收集数据
  2. 准备数据
  3. 分析数据
  4. 训练算法(不适合KNN算法,因为K是“懒惰算法”的著名代表)
  5. 测试算法
  6. 使用算法

三、算法框架

1. classify0()函数的4个输入参数:

  • inX:用于分类的输入向量
  • dataSet:用于输入的训练样本集
  • labels:标签向量
  • k:参数k用于选择最佳邻居的数目

2. 使用欧氏距离公式

  • 计算两个向量点xA和xB之间的距离
  • 计算存在4个特征值的数据集的距离

3. 在约会网站上使用算法

  • 海伦用三个属性来测试自己对于约会对象的喜爱程度
    每年的飞行里程数
    玩视频游戏所耗时间百分比
    每周消费的冰激凌公升数
    她积攒了一些数据,该数据保存在datingTestSet.txt中,共1000行。
  • 准备数据
def createDataSet():
    group = array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]])
    labels = ['A', 'A', 'B', 'B']
    return group, labels
  • 算法
def classify0(inX,dataSet,labels,k):
        #训练数据集的行数
        dataSetSize=dataSet.shape[0]
        #计算距离
        #这里要说一下tile()函数,以后我们还会多次用到它
        #tile(A,B)表示对A重复B次,B可以是int型也可以是数组形式
        #如果B是int,表示在行方向上重复A,B次,列方向默认为1
        #如果B是数组形式,tile(A,(B1,B2))表示在行方向上重复B1次,列方向重复B2次
        diffMat=tile(inX,(dataSetSize,1))-dataSet
        print(diffMat)
        sqDiffMat=diffMat**2
        print(sqDiffMat)
        sqDistances=sqDiffMat.sum(axis=1)
        distances=sqDistances**0.5
        #排序,这里argsort()返回的是数据从小到大的索引值,这里这就是第几行数据
        sortedDisIndicies =distances.argsort()
        print(sortedDisIndicies)
        classCount={}
        #选取距离最小的k个点,并统计每个类别出现的频率
        #这里用到了字典get(key,default=None)返回键值key对应的值;
        #如果key没有在字典里,则返回default参数的值,默认为None
        for i in range(k):
                voteIlabel=labels[sortedDisIndicies[i]]
                classCount[voteIlabel]=classCount.get(voteIlabel,0)+1;
        #逆序排序,找出出现频率最多的类别
        sortedClassCount=sorted(classCount.items(),
                                key=operator.itemgetter(1),reverse=True)
        print(sortedClassCount)
        return sortedClassCount[0][0]
  • py3.5中iteritems改为items(上倒数第4行)
#进入python界面: 
>>>import kNN 
>>>group,labels=kNN.createDataSet() 
>>>kNN.classify0([0,0],group,labels,3) 
  • 读取txt的数据
def file2matrix(filename):
        fr=open(filename)
        #读取文件
        arrayOLines=fr.readlines()
        #文件行数
        numberOfLines=len(arrayOLines)
        #创建全0矩阵
        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
# 重新加载kNN,得倒解析数据 
>>>reload(kNN) 
>>>datingDataMat,datingLabels=kNN.file2matrix('datingTestSet2.txt') 

  • 使用Matplotlib 创建散点图
# 命令行中输入
>>>import matplotlib 
>>>import matplotlib.pyplot as plt 
>>>from numpy import array 
>>>fig = plt.figure() 
>>>ax=fig.add_subplot(111) 
>>>ax.scatter(datingDataMat[:,1],datingDataMat[:,2],15.0*array(datingLabels),15.0*array(datingLabels))
>>>plt.show()
  • 利用github存储图片并以markdown的链接形式显示
    [图片上传失败...(image-2b31b0-1512123353929)]

4. 数据的归一化

  • 由于每个属性的取值数量级相差过大,会造成每个属性的权重不同,这显然是海伦不希望的。所以我们还要写一个函数实现数据归一化,公式如下:
  • newValue=(oldValue-min)/(max-min)
  • 这个公式可以将特征值转化为0~1之间的值。
#归一化特征值
def autoNorm(dataSet):
        #每列的最小值
        minVals=dataSet.min(0)
        #每列的最大值
        maxVals=dataSet.max(0)
        #最大值与最小值的差值
        ranges=maxVals-minVals
        normDataSet=zeros(shape(dataSet))
        m=dataSet.shape[0]
        #minVals是1*3的矩阵,使用tile函数复制成和dataSet同样大小的矩阵,方便计算
        normDataSet=dataSet-tile(minVals,(m,1))
        normDataSet=normDataSet/tile(ranges,(m,1))
        return normDataSet,ranges,minVals
>>>reload(kNN) 
>>>normMat,ranges,minVals=kNN.autoNorm(datingDataMat) 

5. 原始分类器

#原始测试分类器
def datingClassTest():
        hoRatio=0.10
        datingDataMat,datingLabels=file2matrix('datingTestSet2.txt')
        normMat,ranges,minVals=autoNorm(datingDataMat)
        m=normMat.shape(0)
        #10%的数据用于测试数据集
        numTestVecs=int(m*hoRatio)
        errorCount=0.0
        for i in range(numTestVecs):
                classifierResults=classify0(normMat[i,:],normMat[numTestVecs:m,:], datingLabels[numTestVecs:m],3)
                print("the classifier came back with: %d,the real answer id: %d"%(classifierResults,datingLabels[i]))
                if(classifierResults!=datingLabels[i]):errorCount +=1.0
        print("the total error rate is: %f" %(errorCount/float(numTestVecs)))

6. 接口

# 约会网站预测函数
def classifyPerson():
        resultList=['not at all','in small doses','in large doses']
        percentTats=float(input("在游戏上花费的时间占比( )?"))
        ffMiles=float(input("每年航空的里程数?"))
        iceCream=float(input("每年吃的冰淇淋(升)?"))
        datingDataMat,datingLabels=file2matrix('datingTestSet2.txt')
        normMat, ranges, minVals=autoNorm(datingDataMat)
        inArr=array([ffMiles,percentTats,iceCream])
        classifierResult=classify0((inArr-minVals)/ranges,normMat,datingLabels,3)
        print("你可能是属于以下这类人:",resultList[classifierResult - 1])

[图片上传失败...(image-77db49-1512123353929)]
[图片上传失败...(image-dd2d24-1512123353929)]

7. 识别手写数字

# 将图片格式处理为一个向量(把一个32*32的二进制图形矩阵转换为1*1024的向量),然后使用分类器处理图形信息
def img2vector(filename):
    # 创建一个1*1024的NumPy数组
    returnVect = zeros((1,1024))
    fr = open(filename)
    # 循环读出文件的前32行,并将每行的头32个字符值存储在NumPy数组中,最后返回数组
    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 = []
    # 将trainingDigits目录中的文件存储在列表中
    trainingFileList = listdir('trainingDigits')
    # 获得文件数赋值给m
    m = len(trainingFileList)
    # 创建一个m行1024列的训练矩阵,每行数据存储一个图像
    trainingMat = zeros((m,1024))
    for i in range(m):
        # 从文件名解析分类数字(eg:文件9_45.txt表示数字9的第45个实例)
        fileNameStr = trainingFileList[i]
        fileStr = fileNameStr.split('.')[0]     #take off .txt
        classNumStr = int(fileStr.split('_')[0])
        # 将类代码存储在 hwLabels向量中
        hwLabels.append(classNumStr)
        # 使用 img2vector函数载入图像
        trainingMat[i,:] = img2vector('trainingDigits/%s' % fileNameStr)

    # 将testDigits目录中的文件存储在列表中,步骤同上
    testFileList = listdir('testDigits')        #iterate through the test set
    errorCount = 0.0
    mTest = len(testFileList)
    for i in range(mTest):
        fileNameStr = testFileList[i]
        fileStr = fileNameStr.split('.')[0]     #take off .txt
        classNumStr = int(fileStr.split('_')[0])
        vectorUnderTest = img2vector('testDigits/%s' % fileNameStr)
        # 不同的是要使用 classify0函数测试目录下的每个文件(文件中的值介于0-1之间,无需用autoNorm()函数
        classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3)
        print("the classifier came back with: %d, the real answer is: %d" % (classifierResult, classNumStr))
        if (classifierResult != classNumStr): errorCount += 1.0
    print("\nthe total number of errors is: %d" % errorCount)
    print("\nthe total error rate is: %f" % (errorCount/float(mTest)))

github代码

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 214,922评论 6 497
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 91,591评论 3 389
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 160,546评论 0 350
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 57,467评论 1 288
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 66,553评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,580评论 1 293
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,588评论 3 414
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,334评论 0 270
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,780评论 1 307
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,092评论 2 330
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,270评论 1 344
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,925评论 5 338
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,573评论 3 322
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,194评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,437评论 1 268
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,154评论 2 366
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,127评论 2 352