2023学年完整公开课版k近邻算法

K-近邻算法目录1概述2K-近邻算法的Python实现3Kd树4样本实验PARTONE01概述概述k-近邻算法(k-NearestNeighbouralgorithm)，又称为KNN算法，是数据挖掘技术中原理最简单的算法。KNN的工作原理:给定一个已知标签类别的训练数据集，输入没有标签的新数据后，在训练数据集中找到与新数据最邻近的k个实例，如果这k个实例的多数属于某个类别，那么新数据就属于这个类别。可以简单理解为:由那些离X最近的k个点来投票决定X归为哪一类。概述图中有红色三角和蓝色方块两种类别，我们现在需要判断绿色圆点属于哪种类别当k=3时，绿色圆点属于红色三角这种类别;当k=5时，绿色圆点属于蓝色方块这种类别。PARTONE02K-近邻算法的Python实现K-近邻算法的Python实现1构建已经分类好的原始数据集为了方便验证，这里使用python的字典dict构建数据集，然后再将其转化成DataFrame格式。importpandasaspdrowdata={'电影名称':['无问西东','后来的我们','前任3','红海行动','唐人街探案'，'战狼2']，'打斗镜头':[1,5,12,108,112,115]，'接吻镜头':[101,89,97,5,9,8]，'电影类型':['爱情片','爱情片'，'爱情片','动作片'，'动作片'，'动作片']}movie_data=pd.DataFrame(rowdata)movie_dataK-近邻算法的Python实现⒉计算已知类别数据集中的点与当前点之间的距离new_data=[24,67]dist=list((((movie_data.iloc[:6,1:3]-new_data)**2).sum(1))**0.5)dist3.将距离升序排列，然后选取距离最小的k个点dist_1=pd.DataFrame({'dist':dist，'labels':(movie_data.iloc[:6，3])3)dr=dist_1.sort_values(by='dist')[:4]drK-近邻算法的Python实现4.确定前k个点所在类别的出现频率re=dr.1oc[:,'1abels'].value_counts(）re5.选择频率最高的类别作为当前点的预测类别result=[]result.append(re.index[0])resultK-近邻算法的Python实现封装函数importpandasaspd"""函数功能:KNN分类器参数说明:new_data:需要预测分类的数据集dataset:已知分类标签的数据集（训练集)k:k-近邻算法参数，选择距离最小的k个点返回:result:分类结果....defc1assifyo(inx,dataset,k):result=[]dist=list((((dataset.iloc[:,1:3]-inX)**2).sum(1))**0.5)dist_l=pd.DataFrame({'dist':dist,'1abe1s':(dataset.iloc[:，3])3)dr=dist_1.sort_values(by='dist')[:k]re=dr.loc[:，'7abels'].value_counts(resu1t.append(re.index[0])returnresultK-近邻算法的Python实现测试函数运行结果这就是我们使用k-近邻算法构建的一个分类器，根据我们的"经验′可以看出，分类器给的答案还是比较符合我们的预期的。学习到这里，有人可能会问:"分类器何种情况下会出错?“或者"分类器给出的答案是否永远都正确?“答案一定是否定的，分类器并不会得到百分百正确的结果，我们可以使用很多种方法来验证分类器的准确率。此外，分类器的性能也会受到很多因素的影响，比如k的取值就在很大程度上影响了分类器的预测结果，还有分类器的设置、原始数据集等等。为了测试分类器的效果，我们可以把原始数据集分为两部分，一部分用来训练算法（称为训练集一部分用来测试算法的准确率（称为测试集)。同时，我们不难发现，k-近邻算法没有进行数据的训练，直接使用未知的数据与已知的数据进行比较，得到结果。因此，可以说，k-近邻算法不具有显式的学习过程。PARTONE03Kd树Kd树1.实现k近邻法时，主要考虑的问题是:如何对训练数据进行快速k近邻搜索。⒉.最简单的实现方法:线性扫描。此时要计算输入样本与每个训练样本的距离。当训练集很大时，计算非常耗时。解决办法是:使用kd树来提高k近邻搜索的效率。3.kd树是一种对k维空间中的样本点进行存储以便对其进行快速检索的树型数据结构。它是二叉树，表示对k维空间的一个划分。4.构造kd树的过程相当于不断的用垂直于坐标轴的超平面将k维空间切分的过程。kd树的每个结点对应于一个k维超矩形区域。简述Kd树Kd树算法构建Kd树Kd树搜索算法Kd树通常最近邻搜索只需要