Question about kNN Algorithm

2024-05-14 05:58
文章标签 knn algorithm question

本文主要是介绍Question about kNN Algorithm,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

kNN算法中K表示最接近自己的K个数据样本

例如下图绿色的圆形是我们待分类的数据。根据kNN算法:

  • 如果K=3,那么离绿色点最近的有2个红色三角形和1个蓝色的正方形,这3个点投票,于是绿色的这个待分类点属于红色的三角形。
  • 如果K=5,那么离绿色点最近的有2个红色三角形和3个蓝色的正方形,这5个点投票,于是绿色的这个待分类点属于蓝色的正方形。

 

 

当遇到下列这种情况:

  • 如果K=3,那么离绿色点最近的有2个红色三角形和1个蓝色的正方形,这3个点投票,于是绿色的这个待分类点属于红色的三角形。
  • 如果K=4,那么离绿色点最近的有2个红色三角形和2个蓝色的正方形,这4个点投票,那么绿色的这个待分类点应该属于哪一个类型呢?

 

 

Python代码试验:构造四个四个点A(1,1.1)、B(1,1)、C(0,0)、D(0,0.1)

def createDataSet():

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

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

return group, labels

 

kNN待分类数据点(0.5,0.5),与各邻近数据点的欧氏距离的平方分别为:

Distan(A)=0.25+0.36=0.61

Distan(B)=0.5

Distan(C)=0.5

Distan(D)=0.25+0.16=0.41

当k=1,最邻一点只有D,预计推荐结果为D

 

当k=2,待测点与B、C点距离相等,实际kNN推荐结果为B

 

当k=3,相邻3点有B、C、D,最近为D,实际kNN推荐结果为C

 

当k=4,相邻4点有A、B、C、D,最近为D,最远为A,实际kNN推荐结果为A

 

 问题总结:

在kNN算法中,当k取值为类别组数的偶数时,如何得出推荐结果?

kNN分类算法:

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

    dataSetSize = dataSet.shape[0]

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

    sqDiffMat = diffMat**2

    sqDistances = sqDiffMat.sum(axis=1)

    distances = sqDistances**0.5

    sortedDistIndicies = distances.argsort()    

    classCount={}         

    for i in range(k):

        voteIlabel = labels[sortedDistIndicies[i]]

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

    sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)

    return sortedClassCount[0][0]

 

kNN算法本身简单有效,它是一种lazy-learning算法,分类器不需要使用训练集进行训练,训练时间复杂度为0。kNN分类的计算复杂度和训练集中的文档数目成正比,也就是说,如果训练集中文档总数为n,那么kNN的分类时间复杂度为O(n)。

这篇关于Question about kNN Algorithm的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/987932

相关文章

机器学习--KNN算法

knn算法针对有监督学习,分为2种:聚类和回归 第1种:聚类 #导包(聚类)from sklearn.neighbors import KNeighborsClassifier#构建数据x = [[3],[6],[8]]y=[3,7,6]#实例化模型knn=KNeighborsClassifier(n_neighbors=1)#训练knn.fit(x,y)#预测print(

【tensorflow 使用错误】tensorflow2.0 过程中出现 Error : Failed to get convolution algorithm

如果在使用 tensorflow 过程中出现 Error : Failed to get convolution algorithm ,这是因为显卡内存被耗尽了。 解决办法: 在代码的开头加入如下两句,动态分配显存 physical_device = tf.config.experimental.list_physical_devices("GPU")tf.config.experiment

KNN-机器学习实战系列(一)

开门见山,本文单说KNN: 作为机器学习实战书籍介绍的第一个算法,有一些值得说道的地方: 1:什么是KNN? 机器学习的一些基本知识和概念不加叙述了,直接给出KNN的白话定义:给定M个样本,每个样本均有N个数字衡量的属性,而每个样本均带有自身的标签: 这里,为什么需要数字化定义属性呢?这方便了我们衡量指标的计算,我们可以使用距离这一可用数学表达式实现的概念,来阐述何谓近邻。 而KNN,英

【HDU】5021 Revenge of kNN II 树状数组

传送门:【HDU】5021 Revenge of kNN II 题目分析:【HDU】4995 Revenge of kNN的升级版,这次取消的K<=10的限制。 但是依旧可以做! 首先我们将点按照横坐标从小到大排序,然后对于每次查询,我们先二分距离mid,然后再二分查找在X-mid,X+mid里面有多少数,如果小于K则抬升下界,如果大于K+1则降低上界,如果等于K则直接更新,还有就是正

机器学习项目——基于机器学习(决策树 随机森林 朴素贝叶斯 SVM KNN XGBoost)的帕金森脑电特征识别研究(代码/报告材料)

完整的论文代码见文章末尾 以下为核心内容和部分结果 问题背景 帕金森病(Parkinson’s Disease, PD)是一种常见的神经退行性疾病,其主要特征是中枢神经系统的多巴胺能神经元逐渐丧失,导致患者出现运动障碍、震颤、僵硬等症状。然而,除运动症状外,帕金森病患者还常常伴有一系列非运动症状,其中睡眠障碍是最为显著的非运动症状之一。 脑电图(Electroencephalogram, E

k近邻(kNN)算法的Python实现(基于欧氏距离)

k近邻算法是机器学习中原理最简单的算法之一,其思想为:给定测试样本,计算出距离其最近的k个训练样本,将这k个样本中出现类别最多的标记作为该测试样本的预测标记。 k近邻算法虽然原理简单,但是其泛华错误率却不超过贝叶斯最有分类器错误率的两倍。所以实际应用中,k近邻算法是一个“性价比”很高的分类工具。 基于欧式距离,用Python3.5实现kNN算法: 主程序: from numpy impor

Leetcode Question 高频 和 分类

Leetcode Question Difficulty and Frequency 题目分类: Dynamic Programming Edit DistanceMaximum SubarrayMinimum Path SumUnique PathsUnique Paths IILongest Palindromic SubstringInterleaving StringT

纪念一下自己的Coursera Princeton Algorithm的课程第一个assignment

今天终于完成了第一个Union-Find的assignment,之前觉得特别的难,可是最后自己也搞定了。而且是100%满分。 自己后来plot了一下自己的分数,也许这就是学习曲线吧。刚开始不会,到后来中期显著提高,但是要到100%,那就要经历更多的波折,甚至是下降都有可能。最后才能达到100%满分。 我觉得最有用的还是下面这段源代码: /*************************

[Algorithm][综合训练][栈和排序][加减]详细讲解

目录 1.栈和排序1.题目链接2.算法原理详解 && 代码实现 2.加减1.题目链接2.算法原理详解 && 代码实现 1.栈和排序 1.题目链接 栈和排序 2.算法原理详解 && 代码实现 解法:栈 + 贪心 -> 每次尽可能先让当前需要的最大值弹出去vector<int> solve(vector<int>& a) {int n = a.size();vect

[Algorithm][综合训练][四个选项][接雨水]详细讲解

目录 1.四个选项1.题目链接2.算法原理详解 && 代码实现 2.接雨水1.题目链接2.算法原理详解 && 代码实现 1.四个选项 1.题目链接 四个选项 2.算法原理详解 && 代码实现 解法:DFS(暴搜) + 剪枝 + Hash 剪枝: 填某个数的时候,要看看还有没有剩余次数填某个数的时候,符不符合若干题的选项必须相同 #include <iostr