教程从头开始在Python中实现k最近邻居

花落花飞去

发布于 2018-02-23 16:10:29

2.6K0

文章被收录于专栏：人工智能人工智能

k近邻法（或简称为kNN）是一种易于理解和实现的算法，也是一种功能强大的工具。

在本教程中，您将学会使用Python（2.7）从零开始实现k近邻（k-Nearest Neighbors）算法。并将这一算法使用在具体的分类问题上，并对鸢尾花分类问题进行论证。

如果你是一名Python程序员，或是一个能够快速学会python的程序员，本教程适合你，当然你还要对如何从头开始实现k近邻算法算法感兴趣。

什么是k近邻算法

kNN的模型是整个训练数据集。当一个不可见的数据实例需要预测时，kNN算法将通过训练数据集搜索k个最相似的实例，并汇总最相似实例的预测属性，将其作为不可见数据实例的预测返回。

相似性的度量取决于数据的类型。对于实值数据，可以使用欧氏距离。其他类型的数据，如分类或二进制数据，可以使用汉明距离。

在回归问题的情况下，可以返回预测属性的平均值。在分类的情况下，会返回最可能的类别。

k近邻算法如何工作

kNN算法属于基于数据实例的竞争学习和即时学习算法。

基于实例的算法是那些使用数据实例（或单条数据）对问题进行建模以便做出预测性决策的算法。kNN算法是基于实例的算法的一种极端形式，因为所有的训练观察值都保留为模型的一部分。

这是一种竞争学习算法，因为它在内部使用模型元素（数据实例）之间的竞争来作出预测性决策。数据实例之间的客观相似性度量使得每个数据实例与“胜利”竞争或者与给定的不可见数据实例最相似并对预测进行贡献。

即时学习指的是这个算法直到需要预测的时候才建立一个模型。这是“懒惰”，因为它只在最后一秒工作。这样做的好处是只包括与不可见的待预测数据相关的数据，称为本地化模型。缺点是在较大的训练数据集上重复相同或类似的搜索可能使计算量难以承受。

最后，kNN是强大的，因为它不会假设任何关于数据的内容，除了可以在任何两个实例之间一致地计算距离度量。因此，它被称为非参数或非线性的，因为它不具有函数形式。

使用测量数据分类鸢尾花

我们将在本教程中使用鸢尾花分类问题作为测试。

问题是由三种不同种类的鸢尾花的150个观察结果组成。给定的花有4种测量值：萼片长度，萼片宽度，花瓣长度和花瓣宽度，全部以厘米为单位。预测属性是种类，看看数据实例属于setosa，versicolor或者virginica三种花的哪一种。

这是一个标准的数据集，其中的物种数据已知所有情况。因此，我们可以将数据分成训练和测试数据集，并使用预测结果来对我们的算法实现进行评估。正确的对这个问题的分类准确度要求在90％以，通常是96％或更好。

您可以从iris.data免费下载数据集，也可参阅资源部分了解更多详情。

如何在Python中实现k近邻算法

本教程分为以下几个步骤：

数据处理：从CSV文件导入数据集并分割成测试/训练数据集。
相似度：计算两个数据实例之间的距离。
近邻：找到k个最相似的数据实例。
响应：从一组数据实例生成响应。
准确性：总结预测的准确性。
集成：把算法各部分集成在一起。

1.处理数据

我们需要做的第一件事是加载我们的数据文件。数据为CSV格式，没有标题行或任何引号。我们可以使用open函数打开文件，并使用csv库中的reader函数逐行读取数据。

 import csv
with open('iris.data', 'rb') as csvfile:
    lines = csv.reader(csvfile)
    for row in lines:
        print ', '.join(row)

接下来，我们需要将数据拆分成可被kNN用于预测的训练数据集，以及可用于评估模型准确性的测试数据集。

我们首先需要将作为字符串类型加载的花朵测量值转换为我们可以使用的数字类型。接下来，我们需要将数据集随机分成训练和测试数据集。训练/测试的比例为67/33，是使用的标准比率。

综合起来，我们可以定义一个名为loadDataset的函数，它使用提供的文件名加载一个CSV文件，并使用提供的分割比例随机地将其分割为火车和测试数据集。

import csv
import random

def loadDataset(filename, split, trainingSet=[] , testSet=[]):
with open(filename, 'rb') as csvfile:
    lines = csv.reader(csvfile)
    dataset = list(lines)
    for x in range(len(dataset)-1):
        for y in range(4):
            dataset[x][y] = float(dataset[x][y])
            if random.random() < split:
                trainingSet.append(dataset[x])
            else:
                testSet.append(dataset[x])

将鸢尾花数据集CSV文件下载到本地目录。我们可以用我们的该数据集来测试这个函数，如下所示：

 trainingSet=[]
testSet=[]
loadDataset('iris.data', 0.66, trainingSet, testSet)
print 'Train: ' + repr(len(trainingSet))
print 'Test: ' + repr(len(testSet))

2.相似性

为了做出预测，我们需要计算任意两个给定数据实例之间的相似度。这是必要的，以便我们可以在训练数据集中为测试数据集的给定成员定位k个最相似的数据实例，从而进行预测。

考虑到花朵的四种测量属性都是数字类型的，并且具有相同的单位，我们可以直接使用欧几里得距离度量。这被定义为两个数字数组之间的平方差的总和的平方根（再读几次，真正理解它）。

此外，我们要控制哪些字段包含在距离计算中。具体来说，我们只想包含前4个属性。一种方法是将欧氏距离限制在一个固定的长度，忽略超出的内容。

把所有这些放在一起，我们可以定义euclideanDistance函数如下：

import math
def euclideanDistance(instance1, instance2, length):
    distance = 0
    for x in range(length):
        distance += pow((instance1[x] - instance2[x]), 2)
    return math.sqrt(distance)

我们可以用一些示例数据来测试这个函数，如下所示：

data1 = [2, 2, 2, 'a']
data2 = [4, 4, 4, 'b']
distance = euclideanDistance(data1, data2, 3)
print 'Distance: ' + repr(distance)

3.近邻

现在我们有了一个相似性度量，我们可以用它为一个给定的不可见的实例收集k个最相似的实例。

这是计算所有实例的距离和选择具有最小距离值的子集的直接过程。

下面是getNeighbors函数，该函数从给定测试实例的训练集中返回k个最相似的邻居（使用已定义的euclideanDistance函数）

import operator
def getNeighbors(trainingSet, testInstance, k):
    distances = []
    length = len(testInstance)-1
    for x in range(len(trainingSet)):
        dist = euclideanDistance(testInstance, trainingSet[x], length)
        distances.append((trainingSet[x], dist))
    distances.sort(key=operator.itemgetter(1))
    neighbors = []
    for x in range(k):
        neighbors.append(distances[x][0])
    return neighbors

我们可以测试这个函数，如下：

trainSet = [[2, 2, 2, 'a'], [4, 4, 4, 'b']]
testInstance = [5, 5, 5]
k = 1
neighbors = getNeighbors(trainSet, testInstance, 1)
print(neighbors)

4.响应

一旦找到测试实例最相似的邻居，下一个任务是根据这些邻居设计一个预测的响应。

我们可以通过允许每个邻居为他们的类属性进行投票来做到这一点，并以多数票作为预测。

以下提供了获得多个邻居的多数投票答复的功能。它假定所分种类是每个邻居的最后一个属性。

import operator
def getResponse(neighbors):
    classVotes = {}
    for x in range(len(neighbors)):
        response = neighbors[x][-1]
        if response in classVotes:
            classVotes[response] += 1
        else:
            classVotes[response] = 1
    sortedVotes = sorted(classVotes.iteritems(), key=operator.itemgetter(1), reverse=True)
    return sortedVotes[0][0]

我们可以用一些测试邻居来测试这个函数，如下所示：

neighbors = [[1,1,1,'a'], [2,2,2,'a'], [3,3,3,'b']]
response = getResponse(neighbors)
print(response)

这种方法在特定的情况下返回一个响应，但是您可以以特定方式处理这些情况，例如不返回响应或选择无偏差的随机响应。

5.准确性

我们已经实现了全部的kNN算法。剩下的一个重要问题是如何评估预测的准确性。

评估模型准确性的简单方法是计算所有预测中所有正确预测的比例，称为分类准确率。

下面是getAccuracy函数，将总体正确预测相加，并以正确分类的百分比形式返回准确性：

def getAccuracy(testSet, predictions): 
    correct = 0
    for x in range(len(testSet)):
        if testSet[x][-1] is predictions[x]:
            correct += 1
    return (correct/float(len(testSet))) * 100.0

我们可以用一个测试数据集和预测来测试这个函数，如下所示：

testSet = [[1,1,1,'a'], [2,2,2,'a'], [3,3,3,'b']]
predictions = ['a', 'a', 'a']
accuracy = getAccuracy(testSet, predictions)
print(accuracy)

6.集成

我们现在拥有算法的所有元素，我们可以将它们与主函数结合在一起。

下面是在Python中从头开始实现kNN算法的完整示例。

# Example of kNN implemented from Scratch in Python

import csv
import random
import math
import operator

def loadDataset(filename, split, trainingSet=[] , testSet=[]):
	with open(filename, 'rb') as csvfile:
	    lines = csv.reader(csvfile)
	    dataset = list(lines)
	    for x in range(len(dataset)-1):
	        for y in range(4):
	            dataset[x][y] = float(dataset[x][y])
	        if random.random() < split:
	            trainingSet.append(dataset[x])
	        else:
	            testSet.append(dataset[x])


def euclideanDistance(instance1, instance2, length):
	distance = 0
	for x in range(length):
		distance += pow((instance1[x] - instance2[x]), 2)
	return math.sqrt(distance)

def getNeighbors(trainingSet, testInstance, k):
	distances = []
	length = len(testInstance)-1
	for x in range(len(trainingSet)):
		dist = euclideanDistance(testInstance, trainingSet[x], length)
		distances.append((trainingSet[x], dist))
	distances.sort(key=operator.itemgetter(1))
	neighbors = []
	for x in range(k):
		neighbors.append(distances[x][0])
	return neighbors

def getResponse(neighbors):
	classVotes = {}
	for x in range(len(neighbors)):
		response = neighbors[x][-1]
		if response in classVotes:
			classVotes[response] += 1
		else:
			classVotes[response] = 1
	sortedVotes = sorted(classVotes.iteritems(), key=operator.itemgetter(1), reverse=True)
	return sortedVotes[0][0]

def getAccuracy(testSet, predictions):
	correct = 0
	for x in range(len(testSet)):
		if testSet[x][-1] == predictions[x]:
			correct += 1
	return (correct/float(len(testSet))) * 100.0
	
def main():
	# prepare data
	trainingSet=[]
	testSet=[]
	split = 0.67
	loadDataset('iris.data', split, trainingSet, testSet)
	print 'Train set: ' + repr(len(trainingSet))
	print 'Test set: ' + repr(len(testSet))
	# generate predictions
	predictions=[]
	k = 3
	for x in range(len(testSet)):
		neighbors = getNeighbors(trainingSet, testSet[x], k)
		result = getResponse(neighbors)
		predictions.append(result)
		print('> predicted=' + repr(result) + ', actual=' + repr(testSet[x][-1]))
	accuracy = getAccuracy(testSet, predictions)
	print('Accuracy: ' + repr(accuracy) + '%')
	
main()

运行该示例，您将看到每个预测的结果与测试集中的实际类别值相比较。在运行结束时，您将看到模型的准确性。在这种情况下，略高于98％。

 ...
> predicted='Iris-virginica', actual='Iris-virginica'
> predicted='Iris-virginica', actual='Iris-virginica'
> predicted='Iris-virginica', actual='Iris-virginica'
> predicted='Iris-virginica', actual='Iris-virginica'
> predicted='Iris-virginica', actual='Iris-virginica'
Accuracy: 98.0392156862745%

一些扩展问题

本节为您提供继续扩展的一些思路，您可以使用您在本教程中实现的Python代码进行尝试。

回归：可以使实现适应回归问题（预测实值属性）。总结最接近的实例可能涉及到预测属性的平均值或中值。
规范化：当度量单位在属性之间不同时，某种属性可能在对距离度量的贡献中占主导地位。对于这些类型的问题，在计算相似性之前，您需要将所有数据属性重新缩放到0-1范围内（称为归一化）。更新模型以支持数据规范化。
可选的距离度量：有很多距离度量可用，你甚至可以开发自己的域特定的距离度量，如果你喜欢。实施一个可选的距离测量，如曼哈顿距离或矢量点乘。

关于这个算法还有更多的扩展，也许你会想要探索一下。另外两个思路包括支持与预测的k个最相似实例的距离加权和用于搜索相似实例的更高级的基于数据树的结构。

了解更多

本节将提供一些资源，您可以使用这些资源来了解有关k邻近算法的更多信息，从算法的工作原理和工作原理以及在代码中实现它们的实际问题两方面进行了解。

问题

代码

本节链接到流行的机器学习库中kNN的开源实现。如果您正在考虑实施您自己的操作使用方法，请查看这些内容。

在scikit-learn中实现kNN
在Weka中实施kNN（非官方）

书

你可能有一本或多本关于应用机器学习的书籍。本部分重点介绍机器学习常用的应用书中关于k近邻法的章节。

Applied Predictive Modeling, pages 159 and 350.
Data Mining: Practical Machine Learning Tools and Techniques, Third Edition (The Morgan Kaufmann Series in Data Management Systems), pages 76, 128 and 235.
Machine Learning for Hackers, Chapter 10.
Machine Learning in Action, Chapter 2.
Programming Collective Intelligence: Building Smart Web 2.0 Applications, Chapters 2 and 8 and page 293.

教程摘要

在本教程中，您了解了k-Nearest Neighbor算法，它是如何工作的以及可用于思考算法并将其与其他算法关联的一些比喻。建议您从头开始在Python中实现kNN算法，这样您就可以了解每一行代码，并且可以调整算法实现并探索扩展以满足自己的项目需求。

以下是本教程的5个关键知识：

k-最近邻：一个简单的算法来理解和实现，以及一个强大的非参数方法。
基于实例的方法：使用数据实例（观察）对问题进行建模。
竞争学习：学习和预测决策是通过模型元素之间的内部竞争来实现的。
即时学习：一个模型直到需要时才被构建出来，以便进行预测。
相似度量：计算数据实例之间的目标距离度量是该算法的一个关键特征。

最后，回顾一下，你使用这个教程实现了kNN吗？你怎么实现的的？你学会了什么？

python

机器学习

python

机器学习

登录后参与评论

0 条评论

热度