k近邻算法实例总结 第1篇

每个邻近样本的权重是不一样的,一般情况下采用权重和距离成反比的方式来计算,也就是说最终预测结果是出现权重最大的那个类别;

如图,红色圆到待预测样本的距离为3,蓝色方块到待预测样本的距离为2,权重与距离成反比,所以蓝色的权重比较大,待预测样本被预测为蓝色方块。

(2)回归预测规则:一般采用平均值法或者加权平均值法

假设上图中的2和3表示邻近样本的目标属性值(标签值),此时没有类别,只有属性值

k近邻算法实例总结 第2篇

红酒数据集是Scikit-learn库中自带的数据集,我们只需要直接调用它,然后打乱它的顺序来进行我们自己的分类预测。首先我们导入Scikit-learn库,如果大家使用的是anaconda的话,这个库中的数据集都是提前安装好了的,我们只需要调用它即可。

Scikit-learn数据集获取方法:

(1)用于获取小规模数据集,数据集已在系统中安装好了的

数据名()

(2)远程获取大规模数据集安装到本地,data_home默认是位置是/scikit_learn_data/

数据名(data_home = 数据集下载目录)

这两种方法返回的数据是 .Bunch类型,它有如下属性:

data:特征数据二维数组;相当于x变量 target:标签数组;相当于y变量 DESCR:数据描述 feature_names:特征名。新闻数据、手写数据、回归数据没有 target_name:标签名。回归数据没有

首先导入sklearn的本地数据集库,变量wine获取红酒数据,由于wine接收的返回值是**.Bunch类型的数据,因此我用win_data接收所有特征值数据**,它是178行13列的数组,每一列代表一种特征win_target用来接收所有的目标值,本数据集中的目标值为0、1、2三类红酒。如果大家想更仔细的观察这个数据集,可以通过来看这个数据集的具体描述

然后把我们需要的数据转换成DataFrame类型的数据。为了使预测更具有一般性,我们把这个数据集打乱。操作如下:

我们取出最后10行数据用作后续的验证预测结果是否正确,这10组数据分出特征值(相当于x)和目标值(相当于y)。剩下的数据也分出特征值features和目标值targets,用于模型训练。剩下的数据中还要划分出训练集和测试集,下面再详述。到此,数据处理这块完成。

k近邻算法实例总结 第3篇

一般采用75%的数据用于训练,25%用于测试,因此在数据进行预测之前,先要对数据划分。

划分方式:

使用 模块进行数据分割。

x_train,x_test,y_train,y_test = train_test_split(x, y, test_size=数据占比)

train_test_split() 括号内的参数: x:数据集特征值(features) y:数据集目标值(targets) test_size: 测试数据占比,用小数表示,如表示,75%训练train,25%测试test。

train_test_split() 的返回值: x_train:训练部分特征值 x_test: 测试部分特征值 y_train:训练部分目标值 y_test: 测试部分目标值

由于不同数据的单位不同,数据间的跨度较大,对结果影响较大,因此需要进行数据缩放,例如归一化和标准化。考虑到归一化的缺点:如果异常值较多,最大值和最小值间的差值较大,会造成很大影响。我采用数据标准化的方法,采用方差标准差,使标准化后的数据均值为0,标准差为1,使数据满足标准正态分布。

使用sklearn实现k近邻算法

from import KNeighborsClassifier

KNeighborsClassifier(n_neighbors = 邻居数,algorithm = ‘计算最近邻居算法’)

.fit(x_train,y_train)

KNeighborsClassifier() 括号内的参数:

n_neighbors:int类型,默认是5,可以自己更改。(找出离自身最近的k个点)

algorithm:用于计算最近邻居的算法。有:‘ball_tree’、‘kd_tree’、‘auto’。默认是’auto’,根据传递给**fit()**方法的值来决定最合适的算法,自动选择前两个方法中的一个。

将训练所需的特征值和目标值传入.fit()方法之后,即可开始预测。首先利用**.score()评分法输入用于测试的特征值和目标值,来看一下这个模型的准确率是多少,是否是满足要求,再使用.predict()方法预测**所需要的目标值。

评分法:根据x_test预测结果,把结果和真实的y_test比较,计算准确率

预测方法:

accuracy存放准确率,result存放预测结果,最终准确率为, 最终的分类结果和wine_predict_target存放的实际分类结果有微小偏差。

完整代码及数据已放置后台,按关键字回复即可,想加入技术交流,添加时最好的备注方式为:来源+兴趣方向,方便找到志同道合的朋友

k近邻算法实例总结 第4篇

我们使用knn算法及其变种,对Pina印第安人的糖尿病进行预测。数据集可从下面下载。 链接: 提取码:orfr

从输出可以看到,总共有768个样本、8个特征,其中Outcome为标签,0表示没有糖尿病,1表示有糖尿病。这8个特征分别为:

进一步观察数据集里阳性和阴性样本的个数:

其中阴性样本500例,阳性样本268例。接着,我们要把数据集分词训练集和测试集。

使用普通的knn算法、带权重的knn以及指定半径的knn算法分别对数据集进行拟合并计算评分。

权重算法,我们选择了距离越近,权重越高。RadiusNeighborsClassifier模型的半径选择了500.从输出可以看出,普通的knn算法还是最好。 问题来了,这个判断准确吗? 答案是:不准确。因为我们的训练集和测试集是随机分配的,不同的训练样本和测试样本组合可能导致计算出来的算法准确性有差异。 那么该如何解决呢? 我们可以多次随机分配训练集和交叉验证集,然后求模型评分的平均值。scikit-learn提供了KFold和cross_val_score()函数来处理这种问题。

上述代码,我们通过KFold把数据集分成10份,其中1份会作为交叉验证集来计算模型准确性,剩余9份作为训练集。cross_val_score()函数总共计算出10次不同训练集和交叉验证集组合得到的模型评分,最后求平均值。 看起来,还是普通的knn算法性能更优一些。

根据上面模型比较得到的结论,我们接下来使用普通的knn算法模型对数据集进行训练,并查看对训练样本的拟合情况以及对测试样本的预测准确性情况:

从这里可以看到两个问题。

从图中可以看出训练样本评分较低,且测试样本与训练样本距离较大,这是欠拟合现象。不过,knn算法没有更好的措施解决欠拟合问题,也许可以换用其它类型的算法。

k近邻算法实例总结 第5篇

  ​

        机器学习算法一个很重要的工作就是评估算法的正确率,通常我们只提供已有数据的90%作为训练样本来训练分类器,而使用其余的10%数据去测试分类器,检测分类器的正确率。10%数据应该是随机选择的。

k近邻算法实例总结 第6篇

原理:如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别,那么该样本也属于这个类别。简单来说就是,求两点之间的距离,看距离谁是最近的,以此来区分我们要预测的这个数据是属于哪个分类。

我们看图来理解一下。蓝色点是属于a类型的样本点,粉色点是属于b类型的样本点。此时新来了一个点(黄色点),怎么判断是属于它是a类型还是b类型呢。

方法是:新点找距离自身最近的k个点(k可变)。分别计算新点到其他各个点的距离,按距离从小到大排序,找出距离自身最近的k个点。统计在这k个点中,有多少点属于a类,有多少点属于b类。**在这k个点中,如果属于b类的点更多,那么这个新点也属于b分类。**距离计算公式也是我们熟悉的勾股定理。

算法优点:简单易理解、无需估计参数、无需训练。适用于几千-几万的数据量。

算法缺点: 对测试样本计算时的计算量大,内存开销大,k值要不断地调整来达到最优效果。k值取太小容易受到异常点的影响,k值取太多产生过拟合,影响准确性。

k近邻算法实例总结 第7篇

knn算法的核心思想是未标记样本的类别,由距离其最近的k个邻居投票来决定。 具体的,假设我们有一个已标记好的数据集。此时有一个未标记的数据样本,我们的任务是预测出这个数据样本所属的类别。knn的原理是,计算待标记样本和数据集中每个样本的距离,取距离最近的k个样本。待标记的样本所属类别就由这k个距离最近的样本投票产生。 假设X_test为待标记的样本,X_train为已标记的数据集,算法原理的伪代码如下:

其算法参数是k,参数选择需要根据数据来决定。

knn算法有一些变种,其中之一是可以增加邻居的权重。默认情况下,在计算距离时,都是使用相同权重。实际上,可以针对不同的邻居指定不同的距离权重,如距离越近权重越高。这个可以通过指定算法的weights参数来实现。 另一个变种是,使用一定半径内的点取代距离最近的k个点。当数据采样不均匀时,可以有更好的性能。在scikit-learn里, R a d i u s N e i g h b o r s C l a s s i f i e r {RadiusNeighborsClassifier} RadiusNeighborsClassifier类实现了这个算法变种。

k近邻算法实例总结 第8篇

图中,双箭头线上的数表示到待预测样本的距离

每个邻近样本的权重是不一样的,一般情况下采用权重和距离成反比的方式来计算,也就是说在计算均值的时候进行加权操作;

如图,权重分别为(各自距离反比占距离反比总和的比例):

属性值为3的权重:

属性值为2的权重:

待预测样本的加权平均值为:

三、手写 k 近邻算法

实现kNN分类算法的伪代码:

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

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

(2)按照距离递增次序排序

(3)选取与当前点距离最小的k个点

(4)确定前k个点所在类别的出现频数

(5)返回当前k个点出现频数最高的类别作为当前点的预测分类

欧氏距离公式:

例如求点(1,0,0,1) (1,0,0,1)(1,0,0,1)和(7,6,9,4) (7,6,9,4)(7,6,9,4)之间的距离:

检测分类器效果:

可以使用已知类别的数据(当然不告诉分类器),检验分类器给出的结果是否与已知类别相同,通过大量的测试数据,我们可以计算出分类器的错误率。

以上算法的实现是用于分类的,决策规则使用了多数表决法;此算法通过改变决策规则,同样可以用于回归。

源代码可见:_Learning/tree/master/03_KNN;01_k近邻算法.py

四、使用手写k kk 近邻算法的案例

1、案例1:约会网站的配对效果

样本包括3种特征:

每年获得的飞行常客里程数

玩视频游戏所耗时间百分比

每周消费的冰淇淋公升数

样本包括3种标签:

不喜欢的人

魅力一般的人

极具魅力的人

部分数据格式为:

代码可见:02_约会网站的配对效果.py

2、案例2:手写数字识别系统

数据集包括训练集和测试集

数据是32*32的二进制文本文件

需要将文本数据转换为Numpy数组

如下是0的一种表示:

预测错误的总数为:10

手写数字识别系统的错误率为:

代码可见:03_手写数字识别系统.py

五、KD树

KNN算法的重点在于找出K个最邻近的点,主要方法如下:

1、蛮力实现(brute)

计算出待预测样本到所有训练样本的训练数据,然后选择最小的K个距离即可得到K个最邻近点;

当特征数比较多,样本数比较多的时候,算法的执行效率比较低。

2、KD树(KD_Tree)

KD_Tree算法中,首先是对训练数据进行建模,构建KD树,然后再根据构建好的模型来获取邻近样本数据

KD_Tree是KNN算法中用于计算最近邻的快速、便捷构建方式

除此之外,还有一些从KD_Tree修改后的求解最邻近点的算法,比如:Ball Tree、BBF Tree、MVP Tree等

当样本数据量少的时候,我们可以使用brute这种暴力的方式进行求解最近邻,即计算到所有样本的距离。

当样本量比较大的时候,直接计算所有样本的距离,工作量有点大,所以在这种情况下,我们可以使用kd tree来快速的计算。

(1)KD数的构建

KD树采用从m个样本的n维特征中,分别计算n个特征取值的方差,用方差最大的第 k 维特征作为根节点。对于这个特征,选择取值的中位数作为样本的划分点,对于小于该值的样本划分到左子树,对于大于等于该值的样本划分到右子树,对左右子树采用同样的方式找方差最大的特征作为根节点,递归即可产生KD树。

假设二维样本为:{(2, 3), (5, 4), (9, 6), (4, 7), (8, 1), (7, 2)},下面我们来构建KD树:

k近邻算法实例总结 第9篇

X[:,0] 取所有行的第0个数据,即第二维下标位0的所有数据,第0列(数组从0开始)

X[:,1] 取所有行的第1个数据,即第二维下标位1的所有数据,第1列(数组从0开始)

X[:,1:]第一维全部取,即所有行,列上从第一列开始往后取,不取第0列

X[1,:] 是取第1维中下标为1的元素的所有数据,第1行列全部取

X[:2,1:]第一维取下标2之前的元素,即第2行之前,下标为0和1的两行,列从第一列开始取

        Matplotlib 是 Python 的绘图库,类似 MATLAB 的绘图工具。它可与 NumPy 一起使用,提供了一种有效的 MatLab 开源替代方案, 它也可以和图形工具包一起使用。

k近邻算法实例总结 第10篇

         上面的实例二实验中,可以知道当K = 3时,使用K-近邻算法识别手写数据集的错误率大约为百分之一。但是从运行效果看,实际使用这个算法的时候,算法的执行效率并不高。我们需要进行2000次距离计算,每个距离计算包括了1024个维度的浮点数,总计执行900次,此外,我们还要为测试向量准备很大的存储空间。

        我觉得中手写数字识别的系统可以做的更好一点,比如做出一个程序界面,给窗口在画板上手写数字,然后程序能够识别出手写数字,后期继续吧自己的想法实现!

k近邻算法实例总结 第11篇

分类问题的预测值是离散的,我们也可以用knn算法在连续区间内对数值进行预测,回归拟合。我们使用 s k l e a r n . n e i g h b o r s . K N e i g h b o r s R e g r e s s o r {} sklearn.neighbors.KNeighborsRegressor类。

我们怎么进行回归拟合呢? 一个方法是,在X轴上的指定区间内生成足够多的点,针对这些足够密集的点,使用训练出来的模型去预测,得到预测值y_pred,然后在坐标轴上把所有的预测点连接起来,这样就画出了拟合曲线。如下:

k近邻算法实例总结 第12篇

d(a,b)=\max(|x_a-x_b|,|y_a-y_b|) \\

n维空间

d(a,b)=\max_i(|x_{ai}-x_{bi}|) \\

余弦相似度用向量空间中两个向量夹角的余弦值作为衡量两个样本差异的大小。余弦值越接近1, 说明两个向量夹角越接近0度,表明两个向量越相似。几何中,夹角余弦可用来衡量两个向量方向的差异;机器学习中,借用这一概念来衡量样本向量之间的差异。

cos(\theta)=\frac{\sum_{i=1}^nx_{ia}x_{ib}}{\sqrt{\sum_{i=1}^nx_{ia}^2}\sqrt{\sum_{i=1}^nx_{ib}^2}} \\

k 值的选择会对KNN 算法的结果产生重大影响。

在应用中,k 值一般选取一个较小的数值,通常采用交叉验证来选取最优的k 值。

根据 _少数服从多数,一 点算一票_ 的原则进行判断,数量最多标签类别就是x的标签类别。其中涉及到的原理是_越相近越相似_,这也是KNN 的基本假设。

KNN算法作为一种较简单的算法,存在不足之处:

由于上述的不足,为了提高KNN搜索的速度,可以利用特殊的数据存储形式来减少计算距离的次数。kd树就是一种以二叉树的形式存储数据的方法。

kd树就是对k维空间的一个划分。构造kd树相当于不断用垂直于坐标轴的超平面将k维空间切分,构成一系列k维超矩阵区域。kd树的每一个节点对应一个超矩阵区域。(想要深入了解的同学可以参看李航老师的《统计机器学习》P41页)

输出结果:

这里的最近邻k, 选取的是5,结果为。需要思考两个问题:

1、前面提到 k 值的大小将会影响模型效果,如何选择合适的k 值?

2、模型得分是否可以进一步其他,受哪些因素影响?

我们所用数据是 数据集,均是 '完美' 数据,并不需要常规数据预处理(包括缺失值、异常值、重复值等),但 KNN是距离类模型,数据的量纲不统一将会严重影响其效果。在模型中,欧式距离的计算公式中存在着特征上的平方和:

d(A,B) = \sqrt{(x_{1a}-x_{1b})^2+(x_{2a}-x_{2b})^2+\cdots+(x_{3a}-x_{3b})^2} =\sqrt{\sum_{i=1}^n(x_{ia}-x_{ib})^2} \\

若某个特征取值非常大而导致其掩盖了特征之间的距离对总距离d(a,b)的影响,这样距离模型便不能很好地将不同类别的特征区分开。因此在使用KNN分类器,则需要先对数据集进行去量纲处理。即是将所有的数据压缩到同一个范围内。数据的归一化或者标准化,主要目的是消除量纲对距离类模型的影响,并加速梯度下降等算法的迭代速度,使其更快找到最优解。

带入模型训练后得分: 相比于未归一化前的模型得分提高不少。

输出结果:

输出结果:

KNN分类模型的另一个基本假设:就算是最近邻的K个点,每个点和分类目标点的距离仍然有远近之别,而近的点往往和目标分类点有更大的可能性属于同一类别。

基本的最近邻分类使用统一的权重:分配给查询点的值是从最近邻的简单多数投票中计算出来的。 在某些环境下,最好对邻居进行加权,使得更近邻更有利于拟合。

关于惩罚因子的选取有很多种方法,最常用的就是根据每个最近邻距离的不同对其作用加权,加权方法为设置的权重,该权重计算公式为:距离的倒数

w_i=\frac{1}{d(x^\prime,x_i)} \\

注意,关于模型的优化方法只是在理论上优化会提升模型判别效力,但实际应用过程中最终能否发挥作用,本质上取决于优化方法和实际数据情况的契合程度,如果数据本身存在大量异常值点,则采用距离远近作为惩罚因子则会有较好的效果,反之则不然。

输出结果:

如果文中图片加载出错,可到原文链接查看。

原文链接

k近邻算法实例总结 第13篇

本节讲解在Python中如何对一张图片进行简单处理,使其变成计算机能识别的内容。

Pillow库是一款功能强大、简单好用的第三方图像处理库。

结果如下图所示。

原始图片是一个彩色的数字4,我们需要对其进行灰度处理,将其转换为黑白的数字4,以便之后将其转换为数字0和1,代码如下。

获得黑白的数字4后,就要进行关键的图像二值化处理了,代码如下。

point()函数可以操控每一个像素点,point()函数中传入的内容为之前讲pandas库时讲过的lambda匿名函数,其含义为将色彩数值大于128的像素点赋值为0,反之赋值为1。

图像在进行灰度处理后,每一个像素点由一个取值范围为0~255的数字表示,其中0代表黑色,255代表白色,所以这里以128为阈值进行划分,即原来偏白色的区域赋值为0,原来偏黑色的区域赋值为1。这样便完成了将颜色转换成数字0和1的工作。

array()函数将已经转换成数字0和1的32×32像素的图片转换为32×32的二维数组,并赋给变量arr。

打印所有行,一共32行。

上面获得的32×32的二维数组不能用于数据建模,因此还需要用reshape(1,-1)函数将其转换成一行(若写成reshape(-1,1)则转换成一列),即1×1024的一维数组,代码如下。

把处理好的一维数组arr_new传入前面训练好的knn模型中,代码如下。

因为获取到的res是一个一维数组(类似列表),所以通过res[0]提取其中的元素,又因为提取出的元素是数字,不能直接进行字符串拼接,所以用str()函数转换后再进行字符串拼接,运行结果如下,可以看到,预测结果是正确的。

k近邻算法实例总结 第14篇

(2)KD tree查找最近邻

当我们生成KD树以后,就可以取预测测试集里面的样本目标点了。

对于一个目标点,我们首先在KD树里面寻找包含目标点的叶子节点;

以目标点为圆心,以目标点到叶子节点样本实例的距离为半径,得到一个超球体,最近邻的点一定在这个超球体内部;

然后返回叶子节点的父节点,检查另一个子节点包含的超矩形体是否和超球体相交,如果相交就到这个子节点寻找是否有更加近的近邻,有点话就更新最近邻;如果不相交那就直接返回父节点的父节点,在另一个子树继续搜索最近邻;

当回溯到根节点时,算法就结束了,保存最近邻节点就是最终的最近邻。

假设要寻找点(2,) (2,)(2,)的最近邻点:

六、KNN案例

1、鸢尾花数据分类

使用Logistic算法和KNN算法对鸢尾花数据进行分类,比较结果;

具体内容在代码的注释中有介绍;

画出下面两张图,需要将代码整合起来,才能画出来。

代码可见:_Learning;02_Logistic回归下05_鸢尾花数据分类.py,以及03_KNN目录下04_鸢尾花数据分类.py。

2、信贷审批

具体内容将在代码中介绍

代码可见:_Learning;02_Logistic回归下03_信贷审批.py,以及03_KNN目录下05_信贷审批.py。

七、总结

本篇主要通过简单的暴力求解的方式实现KNN算法,有助于理解KNN算法

后面又介绍了KD树找K个最近邻,此算法是最快捷的

最后通过sklearn库下的KNeighborsClassifier实现了两个案例,来属性KNN模型的构建

原文链接:

注:本文部分文字与图片资源来自于网络,转载此文是出于传递更多信息之目的,若有来源标注错误或侵犯了您的合法权益,请立即后台留言通知我们,情况属实,我们会第一时间予以删除,并同时向您表示歉意

发表评论

评论列表(7人评论 , 39人围观)