kNN算法基本原理与Python代码实践

2022-04-10 00:47:10

　kNN是一种常见的监督学习方法。工作机制简单：给定测试样本，基于某种距离度量找出训练集中与其最靠近的k各训练样本，然后基于这k个“邻居”的信息来进行预测，通常，在分类任务中可使用“投票法”，即选择这k个样本中出现最多的类别标记作为预测结果；在回归任务中可以使用“平均法”，即将这k个样本的实值输出标记的平均值作为预测结果；还可以基于距离远近进行加权平均或加权投票，距离越近的样本权重越大。[1] 　　

　　kNN的伪代码如下：[2] 　　　　

　　　　对未知类别属性的数据集中的每个点依次执行以下操作：　　　　

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

　　　　（2）按照距离递增次序排序；　　　　

　　　　（3）选取与当前点距离最小的k个点；　　　　

　　　　（4）确定前k个点所在类别的出现频率；　　　　　

　　　　（5）返回前k个点出现频率最高的类别作为当前点的预测分类。　　

　　以下通过图来进一步解释：

　　假定要对紫色的点进行分类，现有红绿蓝三个类别。此处以k为7举例，即找出到紫色距离最近的7个点。

分别找出到紫色距离最近的7个点后，我们将这七个点分别称为1、2、3、4、5、6、7号小球。其中红色的有1、3两个小球，绿色有2、4、5、6四个小球，蓝色有7这一个小球。

显然，绿色小球的个数最多，则紫色小球应当归为绿色小球一类。

　　以下给出利用kNN进行分类任务的最基本的代码。

KNN.py文件内定义了kNN算法的主体部分

from numpy import *

import operator

def createDataSet():

    group = array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0.0, 0.1]])

    labels = ['A', 'A', 'B', 'B']

    return group, labels

def kNN_Classify(inX, dataSet, labels, k):

    dataSetSize = dataSet.shape[0]

    diffMat = tile(inX, (dataSetSize, 1)) - dataSet

    #关于tile函数的用法

	#>>> b=[1,3,5]

	#>>> tile(b,[2,3])

	#array([[1, 3, 5, 1, 3, 5, 1, 3, 5],

	#       [1, 3, 5, 1, 3, 5, 1, 3, 5]])

    sqDiffMat = diffMat ** 2

    sqDistances = sum(sqDiffMat, axis = 1)

    distances = sqDistances ** 0.5#                           算距离

    sortedDistIndicies = argsort(distances)

    #关于argsort函数的用法

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

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

	#>>> np.argsort(x)

	#array([1, 2, 0])

    classCount = {} #                                         定义一个字典

#   选择k个最近邻

    for i in range(k):

        voteLabel = labels[sortedDistIndicies[i]]

        #                                                     计算k个最近邻中各类别出现的次数

        classCount[voteLabel] = classCount.get(voteLabel, 0) + 1

    #                                                         返回出现次数最多的类别标签

    maxCount = 0

    for key, value in classCount.items():

        if value > maxCount:

            maxCount = value

            maxIndex = key

    return maxIndex

KNN_TEST.py文件中有两个样例测试。

#!/usr/bin/python

# coding=utf-8

import KNN

from numpy import *

# 生成数据集和类别标签

dataSet, labels = KNN.createDataSet()

# 定义一个未知类别的数据

testX = array([1.2, 1.0])

k = 3

# 调用分类函数对未知数据分类

outputLabel = KNN.kNN_Classify(testX, dataSet, labels, 3)

print("Your input is:", testX, "and classified to class: ", outputLabel)

testX = array([0.1, 0.3])

outputLabel = KNN.kNN_Classify(testX, dataSet, labels, 3)

print("Your input is:", testX, "and classified to class: ", outputLabel)

代码输出：

画图解释一下输出结果：

参考文献：

[1]机器学习，周志华，清华大学出版社2016.

[2]机器学习实战，Peter Harrington,人民邮电出版社.

2019-03-06

01:52:08

码农公寓

相关文章