从零开始用Python实现k近邻算法(附代码、数据集)

简介:

进入数据分析领域的四年来,我构建的模型的80%多都是分类模型,而回归模型仅占15-20%。这个数字会有浮动,但是整个行业的普遍经验值。分类模型占主流的原因是大多数分析问题都涉及到做出决定。例如一个客户是否会流失,我们是否应该针对一个客户进行数字营销,以及客户是否有很大的潜力等等。这些分析有很强的洞察力,并且直接关系到实现路径。在本文中,我们将讨论另一种被广泛使用的分类技术,称为k近邻(KNN)。本文的重点主要集中在算法的工作原理以及输入参数如何影响输出/预测。

目录

d47e62d2b349aca45e42305ed6714efbe5ed61d9 什么情况下使用KNN算法?
d47e62d2b349aca45e42305ed6714efbe5ed61d9 KNN算法如何工作?
d47e62d2b349aca45e42305ed6714efbe5ed61d9 如何选择因子K?
d47e62d2b349aca45e42305ed6714efbe5ed61d9 分解--KNN的伪代码
d47e62d2b349aca45e42305ed6714efbe5ed61d9 从零开始的Python实现
d47e62d2b349aca45e42305ed6714efbe5ed61d9 和Scikit-learn比较

什么情况使用KNN算法?

KNN算法既可以用于分类也可以用于回归预测。然而,业内主要用于分类问题。在评估一个算法时,我们通常从以下三个角度出发:

d47e62d2b349aca45e42305ed6714efbe5ed61d9 模型解释性
d47e62d2b349aca45e42305ed6714efbe5ed61d9 运算时间
d47e62d2b349aca45e42305ed6714efbe5ed61d9 预测能力

让我们通过几个例子来评估KNN:

58ac53d11f4af0ec7763f9a3cec720c114ebcdf1

KNN算法在这几项上的表现都比较均衡。由于便于解释和计算时间较短,这种算法使用很普遍。

KNN算法的原理是什么?

让我们通过一个简单的案例来理解这个算法。下图是红圆圈和绿方块的分布图:

0385f03567c9d820c4638cfe51b0e65aa1fa84ca

现在我们要预测蓝星星属于哪个类别。蓝星星可能属于红圆圈,或属于绿方块,也可能不属于任何类别。KNN中的“K”是我们要找到的最近邻的数量。假设K = 3。因此,我们现在以蓝星星为圆心来作一个圆,使其恰巧只能包含平面内的3个数据点。参阅下图:

dfe5bc23bbc4850243d7c842b7a7f9f3bff7c705

离蓝星星最近的三个点都是红圆圈。因此,我们可以以较高的置信水平判定蓝星星应属于红圆圈这个类别。在KNN算法中,参数K的选择是非常关键的。接下来,我们将探索哪些因素可以得到K的最佳值。

如何选择因子K?

首先要了解K在算法中到底有什么影响。在前文的案例中,假定总共只有6个训练数据,给定K值,我们可以划分两个类的边界。现在让我们看看不同K值下两个类别的边界的差异。

3fe4ba827d59b99922eb5773ecb4cfb42207b6e8

仔细观察,我们会发现随着K值的增加,边界变得更平滑。当K值趋于无穷大时,分类区域最终会全部变成蓝色或红色,这取决于占主导地位的是蓝点还是红点。我们需要基于不同K值获取训练错误率和验证错误率这两个参数。以下为训练错误率随K值变化的曲线:

e75a07ce392b1bf6f96c97d98d5f6fa01d816ad3

如图所示,对于训练样本而言,K=1时的错误率总是为零。这是因为对任何训练数据点来说,最接近它的点就是其本身。因此,K=1时的预测总是准确的。如果验证错误曲线也是这样的形状,我们只要设定K为1就可以了。以下是随K值变化的验证错误曲线:

fbe65745dfee6b76e2855b576eb5fe1c158d4c4f

显然,在K=1的时候,我们过度拟合了边界。因此,错误率最初是下降的,达到最小值后又随着K的增加而增加。为了得到K的最优值,我们将初始数据集分割为训练集和验证集,然后通过绘制验证错误曲线得到K的最优值,应用于所有预测。

分解--KNN的伪代码

我们可以通过以下步骤实现KNN模型:

d47e62d2b349aca45e42305ed6714efbe5ed61d9 加载数据。
d47e62d2b349aca45e42305ed6714efbe5ed61d9 预设K值。
d47e62d2b349aca45e42305ed6714efbe5ed61d9 对训练集中数据点进行迭代,进行预测。

STEPS:

d47e62d2b349aca45e42305ed6714efbe5ed61d9 计算测试数据与每一个训练数据的距离。我们选用最常用的欧式距离作为度量。其他度量标准还有切比雪夫距离、余弦相似度等
d47e62d2b349aca45e42305ed6714efbe5ed61d9 根据计算得到的距离值,按升序排序
d47e62d2b349aca45e42305ed6714efbe5ed61d9 从已排序的数组中获取靠前的k个点
d47e62d2b349aca45e42305ed6714efbe5ed61d9 获取这些点中的出现最频繁的类别
d47e62d2b349aca45e42305ed6714efbe5ed61d9 得到预测类别

从零开始的Python实现

我们将使用流行的Iris数据集来构建KNN模型。你可以从这里下载(数据集链接:https://gist.githubusercontent.com/gurchetan1000/ec90a0a8004927e57c24b20a6f8c8d35/raw/fcd83b35021a4c1d7f1f1d5dc83c07c8ffc0d3e2/iris.csv)

# Importing libraries

import pandas as pd

import numpy as np

import math

import operator


#### Start of STEP 1

# Importing data

data = pd.read_csv("iris.csv")

#### End of STEP 1


data.head()
8310abfc3054784a89a43d7abfdf0178336644ab

# Defining a function which calculates euclidean distance between two data points

def euclideanDistance(data1, data2, length):

distance = 0

for x in range(length):

distance += np.square(data1[x] - data2[x])

return np.sqrt(distance)


# Defining our KNN model

def knn(trainingSet, testInstance, k):


distances = {}

sort = {}

length = testInstance.shape[1]

#### Start of STEP 3

# Calculating euclidean distance between each row of training data and test data

for x in range(len(trainingSet)):

#### Start of STEP 3.1

dist = euclideanDistance(testInstance, trainingSet.iloc[x], length)


distances[x] = dist[0]

#### End of STEP 3.1


#### Start of STEP 3.2

# Sorting them on the basis of distance

sorted_d = sorted(distances.items(), key=operator.itemgetter(1))

#### End of STEP 3.2


neighbors = []

#### Start of STEP 3.3

# Extracting top k neighbors

for x in range(k):

neighbors.append(sorted_d[x][0])

#### End of STEP 3.3

classVotes = {}

#### Start of STEP 3.4

# Calculating the most freq class in the neighbors

for x in range(len(neighbors)):

response = trainingSet.iloc[neighbors[x]][-1]


if response in classVotes:

classVotes[response] += 1

else:

classVotes[response] = 1

#### End of STEP 3.4


#### Start of STEP 3.5

sortedVotes = sorted(classVotes.items(), key=operator.itemgetter(1), reverse=True)

return(sortedVotes[0][0], neighbors)

#### End of STEP 3.5


# Creating a dummy testset

testSet = [[7.2, 3.6, 5.1, 2.5]]

test = pd.DataFrame(testSet)


#### Start of STEP 2

# Setting number of neighbors = 1

k = 1

#### End of STEP 2

# Running KNN model

result,neigh = knn(data, test, k)


# Predicted class

print(result)

-> Iris-virginica


# Nearest neighbor

print(neigh)

-> [141]

现在我们改变k的值并观察预测结果的变化:

# Setting number of neighbors = 3

k = 3

# Running KNN model

result,neigh = knn(data, test, k)

# Predicted class

print(result) -> Iris-virginica

# 3 nearest neighbors

print(neigh)

-> [141, 139, 120]


# Setting number of neighbors = 5

k = 5

# Running KNN model

result,neigh = knn(data, test, k)

# Predicted class

print(result) -> Iris-virginica

# 5 nearest neighbors

print(neigh)

-> [141, 139, 120, 145, 144]

和scikit-learn比较

可以看到,两个模型都预测了同样的类别(“irisi –virginica”)和同样的最近邻([141 139 120])。因此我们可以得出结论:模型是按照预期运行的。

尾注

KNN算法是最简单的分类算法之一。即使如此简单,它也能得到很理想的结果。KNN算法也可用于回归问题,这时它使用最近点的均值而不是最近邻的类别。R中KNN可以通过单行代码实现,但我还没有探索如何在SAS中使用KNN算法。

您觉得这篇文章有用吗?您最近使用过其他机器学习工具吗?您是否打算在一些业务问题中使用KNN?如果是的话,请与我们分享你打算如何去做。


原文发布时间为:2018-04-17

本文作者:TavishSrivastava

本文来自云栖社区合作伙伴“数据派THU”,了解相关信息可以关注“数据派THU”。

相关文章
|
2天前
|
机器学习/深度学习 自然语言处理 算法
Python遗传算法GA对长短期记忆LSTM深度学习模型超参数调优分析司机数据|附数据代码
Python遗传算法GA对长短期记忆LSTM深度学习模型超参数调优分析司机数据|附数据代码
|
2天前
|
算法 机器人 Python
Python实现教程:平面最短路径算法
Python实现教程:平面最短路径算法
10 1
|
2天前
|
数据采集 机器学习/深度学习 Python
python怎么对数据集进行归一化处理
python怎么对数据集进行归一化处理
11 1
|
8天前
|
机器学习/深度学习 运维 算法
【Python机器学习专栏】异常检测算法在Python中的实践
【4月更文挑战第30天】本文介绍了异常检测的重要性和在不同领域的应用,如欺诈检测和网络安全。文章概述了四种常见异常检测算法:基于统计、距离、密度和模型的方法。在Python实践中,使用scikit-learn库展示了如何实现这些算法,包括正态分布拟合、K-means聚类、局部异常因子(LOF)和孤立森林(Isolation Forest)。通过计算概率密度、距离、LOF值和数据点的平均路径长度来识别异常值。
|
8天前
|
机器学习/深度学习 数据可视化 算法
【Python机器学习专栏】t-SNE算法在数据可视化中的应用
【4月更文挑战第30天】t-SNE算法是用于高维数据可视化的非线性降维技术,通过最小化Kullback-Leibler散度在低维空间保持数据点间关系。其特点包括:高维到二维/三维映射、保留局部结构、无需预定义簇数量,但计算成本高。Python中可使用`scikit-learn`的`TSNE`类实现,结合`matplotlib`进行可视化。尽管计算昂贵,t-SNE在揭示复杂数据集结构上极具价值。
|
8天前
|
机器学习/深度学习 算法 数据挖掘
【Python机器学习专栏】关联规则学习:Apriori算法详解
【4月更文挑战第30天】Apriori算法是一种用于关联规则学习的经典算法,尤其适用于购物篮分析,以发现商品间的购买关联。该算法基于支持度和置信度指标,通过迭代生成频繁项集并提取满足阈值的规则。Python中可借助mlxtend库实现Apriori,例如处理购物篮数据,设置支持度和置信度阈值,找出相关规则。
|
8天前
|
机器学习/深度学习 算法 数据挖掘
【Python机器学习专栏】层次聚类算法的原理与应用
【4月更文挑战第30天】层次聚类是数据挖掘中的聚类技术,无需预设簇数量,能生成数据的层次结构。分为凝聚(自下而上)和分裂(自上而下)两类,常用凝聚层次聚类有最短/最长距离、群集平均和Ward方法。优点是自动确定簇数、提供层次结构,适合小到中型数据集;缺点是计算成本高、过程不可逆且对异常值敏感。在Python中可使用`scipy.cluster.hierarchy`进行实现。尽管有局限,层次聚类仍是各领域强大的分析工具。
|
8天前
|
机器学习/深度学习 算法 数据挖掘
【Python 机器学习专栏】K-means 聚类算法在 Python 中的实现
【4月更文挑战第30天】K-means 是一种常见的聚类算法,用于将数据集划分为 K 个簇。其基本流程包括初始化簇中心、分配数据点、更新簇中心并重复此过程直到收敛。在 Python 中实现 K-means 包括数据准备、定义距离函数、初始化、迭代和输出结果。虽然算法简单高效,但它需要预先设定 K 值,且对初始点选择敏感,可能陷入局部最优。广泛应用在市场分析、图像分割等场景。理解原理与实现对应用聚类分析至关重要。
|
8天前
|
机器学习/深度学习 算法 前端开发
【Python机器学习专栏】集成学习算法的原理与应用
【4月更文挑战第30天】集成学习通过组合多个基学习器提升预测准确性,广泛应用于分类、回归等问题。主要步骤包括生成基学习器、训练和结合预测结果。算法类型有Bagging(如随机森林)、Boosting(如AdaBoost)和Stacking。Python中可使用scikit-learn实现,如示例代码展示的随机森林分类。集成学习能降低模型方差,缓解过拟合,提高预测性能。
|
8天前
|
机器学习/深度学习 算法 Python
【Python 机器学习专栏】随机森林算法的性能与调优
【4月更文挑战第30天】随机森林是一种集成学习方法,通过构建多棵决策树并投票或平均预测结果,具有高准确性、抗过拟合、处理高维数据的能力。关键性能因素包括树的数量、深度、特征选择和样本大小。调优方法包括调整树的数量、深度,选择关键特征和参数优化。Python 示例展示了使用 GridSearchCV 进行调优。随机森林广泛应用于分类、回归和特征选择问题,是机器学习中的重要工具。