一起来《机器学习实战》 - k近邻

    jwolf 
2792  0  0   2018-4-26 12:16

  • 先从实际问题出发

假设小甜（美女妹子）填写了如下一份报告，关于是否愿意对方当男朋友的，你在想自己能否得到小甜的青睐呢？

颜值人品是否愿意
9899愿意
7660不愿意
6060不愿意
3097不愿意
6680愿意
6650不愿意
7080愿意

好了，我们来说重点-------> 大家来评评理，假设我的颜值和人品分别是69、90， 那么大家觉得小甜甜愿意当我女朋友吗？

我们把数据先以颜值为横坐标，人品为纵坐标，生成数个点，代码如下:

from numpy import *
import matplotlib.pyplot as plt
data = array([[98, 99], [76, 60], [60, 60], [30, 97], [66, 80], [66, 50], [70, 80], [69, 90])
label = ['r', 'b', 'b', 'b', 'r', 'b', 'r', 'g']
def draw (x, y, label):
    fig = plt.figure()
    ax = fig.add_subplot(111)
    ax.scatter(x, y, c=label, marker='o')
    plt.show()
draw(data[:,0], data[:,1], label)

效果如下：

image

来，大声地回答我， 小甜甜愿意当我女朋友吗？

好吧，回到主题，我知道大家都觉得她愿意（你看着这个图再说一次不愿意看看？？→_→），为什么呢，因为黑点给人的感觉是跟红点一伙的（很接近了）

正是因为从图中看出黑点跟这些红点比较近，所以这个黑点很有可能是跟红点一伙的；而 kNN(k-NearestNeighbor) 算法正是基于这么简单，直观的思路

算法执行的步骤如下：

  • 计算已知类别数据集中的点与当前点之间的距离；

  • 按照距离递增排序；

  • 选取与当前点距离最小的K个点；

  • 确定前K个点所在类别的出现频率；

  • 返回前k个点出现频率最高的类别作为当前点的预测分类；





  • 能解决什么问题？

刚刚只有两个维度（颜值，人品）于是我们在平面画点直观地看出点与点直接的远近，要是这个报告里面还有多一个或多个维度呢？比如银行卡存款，每周玩游戏频率等等，那么我们不能简单地在平面上画点直观地看出点与点直接的距离，但是我们知道，这个距离确凿的表示，应该是点与点直接的差异性，就是表示他们的差异程度

公式1：

d = \sqrt{(x1 - y1)^2 + (x2 - y2)^2 + ... +(xn-yn)^2}

下面我们利用这个实现简单的图形识别：

00000000000001100000000000000000
00000000000000111000000000000000
00000000000111111100000000000000
00000000000111111110000000000000
00000000011111111110000000000000
00000000001111100111100000000000
00000000011111000111100000000000
00000001111110000011100000000000
00000000111111000001110000000000
00000000111111000001111100000000
00000001111111000001111100000000
00000000111110000000011110000000
00000000111100000000011110000000
00000000111100000000011110000000
00000001111100000000001110000000
00000001111110000000000111000000
00000001111100000000000111000000
00000001111100000000000111000000
00000000111110000000000011100000
00000000111110000000000011100000
00000000111110000000000111100000
00000000111110000000001111100000
00000000011111100000001111110000
00000000011111100000001111100000
00000000011100000000111111000000
00000000001110000000111111000000
00000000011111000111111110000000
00000000001111111111111100000000
00000000000111111111111100000000
00000000000111111111110000000000
00000000000011111111000000000000
00000000000000100000000000000000

我们现在有多个这样的类似手写的数字的txt文件（已经知道每个文件对应什么数字，文末github源码中有这些数据文件），要是我再给一个新的格局一样的手写体文件，我们如何识别出这个文件对应哪个数字呢？

按照kNN的思路，文件中每一个0或者1都对应一个特征值，根据 公式1 我们能计算出两个文件之间的差异程度，无非就是把两个文件中对应位置的0或者1代入到公式。既然两个文件之间的差异程度能计算出来，那我们就把待测试的文件跟每个样本文件的差异程度都计算出来，排序取出差异程度最低的前K个，看看里面的这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.iteritems(), key=operator.itemgetter(1), reverse=True)    return sortedClassCount[0][0]

以上代码可能会有点不好理解，涉及到python的numpy库，大家用自己熟悉的语言实现一次，（笔者使用javascript实现了一次，源码见文末github, 效率简直不能比啊→_→）可以发现为什么python在机器学习的大潮中能火，python中成熟的科学函数库都实现了向量和矩阵的操作，这些库使用底层语言（C和Fortran）编写，提高了程序的计算性能，另一方面python是高级语言，学习成本也低，我们可以花费更多的时间在处理数据的内在含义，而无须花费太多精力解决计算机如何得出计算的结果。

下面附上一张效率对比图：

javascript:

image

python:

image

github: 点我加个star



标签