KNN邻近算法

发表于

从年初开始，笔者开始对机器学习做出初步的了解与学习，初衷是为了解决游戏开发中AI的算法问题，但是由于其数学门槛和我工作方面的原因，进度一直都是断断续续。这里开始重新对机器学习方面的知识做出一些学习后的理解总结，以方便日后的学习。

目前笔者看的书是《机器学习实战》。这是一本用python实现的，以案例为主，比较基础的学习书。代码的思路也主要是来自该书。有兴趣的同学可以去了解下。

什么是KNN邻近算法

邻近算法，或者说K最近邻(kNN，k-NearestNeighbor)分类算法是数据挖掘分类技术中最简单的方法之一。所谓K最近邻，就是k个最近的邻居的意思，说的是每个样本都可以用它最接近的k个邻居来代表。－百度百科

这里我们可以大概看得比较明白了。这个算法得功能无非就是用来作分类。既然是用来分类，那么我们的数据首先要可以根据其特征来进行分类。比如，我们要判定一个动物是鸭子，他会嘎嘎叫，有羽毛，并且会像鸭子那样走路，而且有着鸭子的喙，那么我们就可以认定这是一只鸭子而不是一个人。

我们进行分类的方法很简单，根据该动物的特征，羽毛，喙，嘎嘎叫这些特点，都是鸭子所具备的，人虽然可以嘎嘎叫，但是并不具备喙和羽毛的特征，所以根据特征的偏移，我们可以将其与人的特征作出对比之后，然后做出认定，这是一只鸭子。

上述可以看做是一个KNN算法的简单实例。

在机器学习的分类问题中，这个算法也被使用得相当之多。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

# coding:utf-8
from numpy import *
import operator

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]  # shape函数是numpy.core.fromnumeric中的函数，它的功能是读取矩阵的长度，比如shape[0]就是读取矩阵第一维度的长度。它的输入参数可以使一个整数表示维度，也可以是一个矩阵。
    # tile函数位于python模块 numpy.lib.shape_base中，他的功能是重复某个数组。比如tile(A,n)，功能是将数组A重复n次，构成一个新的数组

    # 差异矩阵
    diffMat = tile(inx, (dataSetSize, 1)) - dataSet  
    # 求方差
    sqDiffMat = diffMat ** 2 

    # 我们平时用的sum应该是默认的axis=0 就是普通的相加 而当加入axis=1以后就是将一个矩阵的每一行向量相加
    sqDistances = sqDiffMat.sum(axis=1)

    distance = sqDistances ** 0.5
    sortedDistIndicies = distance.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]


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

这段python代码可能有一点难懂，里面引用了很多numpy库中对矩阵操作的方法，我们可以把矩阵当作一个直角坐标系中的二维数组来做处理，其主要的逻辑我都注释了出来。其实就是通过比较已有数据中几个距离最近的点，来对未知的数据作出分类。

我们在运行的时候，将最后一段的注释去掉，就能看到其对这个新的数据类型作出的判断。这里的k就是指的元素距离k个数据最近时候的分类结果。

以上就是KNN临近算法最简单的原理，其应用我们后续再聊。

  • 代码来自《机器学习实战》