k 近邻法 (或简称为 kNN) 是一种易于理解和实现的算法, 也是一种功能强大的工具
在本教程中, 您将学会使用 Python(2.7)从零开始实现 k 近邻 (k-Nearest Neighbors) 算法并将这一算法使用在具体的分类问题上, 并对鸢尾花分类问题进行论证
如果你是一名 Python 程序员, 或是一个能够快速学会 python 的程序员, 本教程适合你, 当然你还要对如何从头开始实现 k 近邻算法算法感兴趣
k-Nearest Neighbors 算法
图片来自维基百科, 保留所有权利
什么是 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 邻近算法的更多信息, 从算法的工作原理和工作原理以及在代码中实现它们的实际问题两方面进行了解
问题
维基百科上的鸢尾花数据集
UCI 机器学习知识库 Iris 数据集
代码
本节链接到流行的机器学习库中 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 吗? 你怎么实现的的? 你学会了什么?
来源: https://cloud.tencent.com/developer/article/1043112