K最近邻方法

1.简述k最近邻算法的原理、算法流程以及优缺点一、什么是K近邻算法k近邻算法又称knn算法、最近邻算法，是一种用于分类和回归的非参数统计方法。

在这两种情况下，输入包含特征空间中的k个最接近的训练样本，这个k可以由你自己进行设置。

在knn分类中，输出是一个分类族群。

一个对象的分类是由其邻居的“多数表决”确定的，k个最近邻居（k为正整数，通常较小），所谓的多数表决指的是，在k个最近邻中，取与输入的类别相同最多的类别，作为输入的输出类别。

简而言之，k近邻算法采用测量不同特征值之间的距离方法进行分类。

knn算法还可以运用在回归预测中，这里的运用主要是指分类。

二、k近邻算法的优缺点和运用范围优点：精度高、对异常值不敏感、无数据输入假定。

缺点：计算复杂度高、空间复杂度高。

适用范围：数值型和标称型、如手写数字的分类等。

三、k近邻算法的工作原理假定存在一个样本数据集合，并且样本集中的数据每个都存在标签，也就是说，我们知道每一个样本数据和标签的对应关系。

输入一个需要分类的标签，判断输入的数据属于那个标签，我们提取出输入数据的特征与样本集的特征进行比较，然后通过算法计算出与输入数据最相似的k个样本，取k个样本中，出现次数最多的标签，作为输入数据的标签。

四、k近邻算法的一般流程（1）收集数据：可以使用任何方法，可以去一些数据集的网站进行下载数据。

（2）准备数据：距离计算所需要的数值，最好是结构化的数据格式（3）分析数据：可以使用任何方法（4）训练算法：此步骤不适用于k近邻算法（5）测试算法：计算错误率（6）使用算法：首先需要输入样本数据和结构化的输出结构（统一数据格式），然后运行k近邻算法判定输入数据属于哪一种类别。

五、k近邻算法的实现前言：在使用python实现k近邻算法的时候，需要使用到Numpy科学计算包。

如果想要在python中使用它，可以按照anaconda，这里包含了需要python需要经常使用到的科学计算库，如何安装。

k近邻算法的发展
k近邻算法的发展如下：
k近邻算法最初是由Cover和Hart在1967年提出的，也称为k-最近邻法（k-NN）。

它的基本原理是：对于样本数据集合中每个数据都存在标签，输入没有标签的新数据后，将新的数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本最相似数据（最近邻）的分类标签。

k近邻算法在Cover和Hart提出后，并没有受到太多关注。

直到1984年，Devroy和Lloyd重新独立地发现了k近邻算法，并将其应用到英国的邮政编码分类问题上，取得了良好的效果。

之后，k近邻算法得到了广泛的应用和发展。

如今，k近邻算法已经成为了机器学习中最常用的算法之一，被广泛应用于分类和回归问题中。

同时，k近邻算法也在数据挖掘、自然语言处理、图像处理等领域得到了广泛的应用。

k-近邻算法一、 实验题目1. kNN 代码实现-AB 分类采用测量不同特征值之间的距离方法进行分类，用所给的函数创建具有两个特征与一个标签类型的数据作 为训练集，编写 classify0 函数对所给的数据进行 AB 分类。

2. k-近邻算法改进约会网站的配对效果k-近邻算法改进约会网站的配对效果通过收集的一些约会网站的数据信息，对匹配对象的归类：不喜欢的人、魅力一般的人、极具魅力的人。

数据中包含了 3 种特征：每年获得的飞行常客里程数、玩视频游戏所耗时间百分比、每周消费的冰淇淋公升数二、 实验代码1. kNN 代码实现-AB 分类kNN from http.client import ImproperConnectionStatefrom numpy import ∗ from collections importCounter import operator def createDataSet():group = array([[1.0, 1.1], [1.0, 1.0], [0, 0], [0, 0.1]])labels = [’A ’, ’A ’, ’B’, ’B’] return group, labelsdef classify0(inX, group, labels, k = 3):res1 = (inX − group)∗∗2 dist =res1[:,0] + res1[:,1] dic = argsort(dist) dic = dic[0:k:1] newdic = [] for i in range (k): newdic.append(labels[dic[i]]) c = Counter(newdic).most_common(1) return c[0][0] tests import kNN group, lables = kNN.createDataSet() print (’分类结果’) print (’[0,0] %c’ %(kNN.classify0([0, 0], group, lables, k = 3))) print (’[0.8,0.7] %c’ %(kNN.classify0([0.8, 0.7], group, lables, k = 3)))2.k-近邻算法改进约会网站的配对效果1 2 3 4 5 67 8 910111213141516171819 1 2 3 4 5import pandas as pdimport kNNfrom sklearn.model_selection import train_test_splitdf = pd.read_table(’datingTestSet2.txt’,sep=’\s+’, names = [’A ’, ’B’, ’C’, ’Y’])# 对特征进行归一化处理df2 = df.iloc[:, :3] df2 =(df2−df2.mean())/df2.std() lable=df.iloc[:,3:4] df2.loc[:, ’Y’] =lable# 对数据集进行测试集和训练集划分，90%作为训练集，10%作为测试集X_train, X_test, Y_train, Y_test = train_test_split(df2.iloc[:, :3], df2.Y, train_size=.90)# 将DataFrame 格式转化为numpy 格式处理 group = X_train.values label =Y_train.values length =len (X_test) X_test.iloc[0:1,:]# res 以储存测试结果res = []# 设置错误正确数count 以计算正确率Tnum = 0 Fnum = 0 for iin range (length):inX = X_test.iloc[i:i+1 , :].values res.append(kNN.classify0(inX,group, label, k = 3)) if (kNN.classify0(inX, group, label, k = 3) ==Y_test.values[i]):Tnum += 1 else :Fnum += 1res1 = pd.DataFrame(data = res, columns=[’TestResult’])Y_test.reset_index(inplace=True,drop=True)res1.loc[:, ’OriginTest’] = Y_testprint (’前20个数据测试结果和原数据比较’) print (’−−−−−−−−−−−−−−−−−−−−−——−−−−’) print (res1.head(20))print (’−−−−−−−−−−−−−−−−−−−−−——−−−−’) print (’正确率%.2f%%’ %(100∗Tnum/(Tnum+Fnum))) 三、 实验结果及分析1. kNN 代码实现-AB 分类分类结果[0, 0] B[0.8, 0.7] A2. k-近邻算法改进约会网站的配对效果1 2 3 45 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 2526 27 28 29 3031 32 33 3435363738 1 2 3前20个数据测试结果和原数据比较−−−−−−−−−−−−−−−−−−−−−——−−−TestResult OriginTest0 2 2 1 3 3 2 1 3 3 2 2 4 2 2 5 3 3 6 3 3 7 2 2 8 1 1 9 1 1 10 1 1 11 3 3 12 2 2 13 2 2 14 1 1 15 2 2 16 1 1 17 2 2 18 1 1 19 3 3−−−−−−−−−−−−−−−−−−−−−——−−− 正确率97.00%从实验结果可以看出，通过 k-近邻算法改进后的约会网站的配对效果比较显著，多次随机划分测试集和训练集后发现正确率基本可以达到 90% 以上。

机器学习--K近邻（KNN）算法的原理及优缺点⼀、KNN算法原理 K近邻法(k-nearst neighbors,KNN)是⼀种很基本的机器学习⽅法。

它的基本思想是：在训练集中数据和标签已知的情况下，输⼊测试数据，将测试数据的特征与训练集中对应的特征进⾏相互⽐较，找到训练集中与之最为相似的前K个数据，则该测试数据对应的类别就是K个数据中出现次数最多的那个分类。

由于KNN⽅法主要靠周围有限的邻近的样本，⽽不是靠判别类域的⽅法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN⽅法较其他⽅法更为适合。

KNN算法不仅可以⽤于分类，还可以⽤于回归。

通过找出⼀个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。

更有⽤的⽅法是将不同距离的邻居对该样本产⽣的影响给予不同的权值(weight)，如权值与距离成反⽐。

KNN算法的描述： （1）计算测试数据与各个训练数据之间的距离； （2）按照距离的递增关系进⾏排序； （3）选取距离最⼩的K个点； （4）确定前K个点所在类别的出现频率 (5）返回前K个点中出现频率最⾼的类别作为测试数据的预测分类。

算法流程： （1）准备数据，对数据进⾏预处理。

（2）选⽤合适的数据结构存储训练数据和测试元组。

（3）设定参数，如k。

（4）维护⼀个⼤⼩为k的的按距离由⼤到⼩的优先级队列，⽤于存储最近邻训练元组。

随机从训练元组中选取k个元组作为初始的最近邻元组，分别计算测试元组到这k个元组的距离，将训练元组标号和距离存⼊优先级队列。

（5）遍历训练元组集，计算当前训练元组与测试。

元组的距离，将所得距离L 与优先级队列中的最⼤距离Lmax。

（6）进⾏⽐较。

若L>=Lmax，则舍弃该元组，遍历下⼀个元组。

若L < Lmax，删除优先级队列中最⼤距离的元组，将当前训练元组存⼊优先级队列。

（7）遍历完毕，计算优先级队列中k 个元组的多数类，并将其作为测试元组的类别。

监督分类的方法监督分类的方法监督分类是一种数据分析技术，是一种机器学习算法，它很大程度上是在两类或者多类数据之间划分线性分类模型。

它是将已经标记的训练数据集映射成一个函数，从而预测没有标记的数据集属于哪一类。

监督分类通常有四种方法：一、K最近邻(K-Nearest Neighbors)法K最近邻(KNN)法是最常用的监督分类法之一。

它是一种基于实例的方法，其假设一个新实例的类别可以由它最近的训练实例的类别来决定(即K个最相似的实例)，而不是统计分布。

KNN是一种基于投票的方法，即多数表决算法。

KNN的工作机制如下：对于一个未知类别的实例，依次取它距离最近的K个已知类别的实例，确定它的类别。

二、朴素贝叶斯(Naive Bayes)朴素贝叶斯(NB)是一种统计学方法，它假设每个特征属性之间相互独立，这个假设被称为贝叶斯假设或者朴素假设。

它被广泛地用于文档分类，数据挖掘，垃圾邮件过滤，和其他数据相关的应用场景中。

三、决策树(Decision Tree)决策树是一种监督学习的方法，它利用一系列问题来决定某一特定的类别分类的结果。

使用决策树可以将未确定的分类结果拆分成各个层次的问题，每个问题都可以用有限数量的语句来表示，称为决策节点，从而对分类结果进行准确的判断，并且决策树可以根据每个决策节点建立模型，将训练数据集映射成决策树模型，从而得出预测结果。

四、支持向量机(Support Vector Machine)支持向量机(SVM)是一种监督式学习的技术，它可以用来在样本空间中建立一个最佳的超平面，从而将类别完全分开。

它有两个基本概念：核函数和决策函数，其工作原理是：它从原始数据中提取出最佳分类的超平面，再根据支持向量的距离来判断类别，从而使得分类效果尽可能获得最高的精度。

K-近邻法是一种常用的机器学习算法，它在分类和回归问题中有着广泛的应用。

而互信息是一种用于衡量两个随机变量之间关联性的指标，它在特征选择、信息检索等领域具有重要的作用。

本文将以k-近邻法为基础，探讨如何利用k-近邻法来求解互信息的计算过程。

1. 什么是K-近邻法K-近邻法（K-nearest neighbors, KNN）是一种基本的分类与回归方法。

在K-近邻法中，对于一个未知样本，通过计算它与训练集中所有样本的距离，然后选择与它距离最近的k个样本，最后根据这k个样本的类别来对该未知样本进行分类或回归预测。

2. 什么是互信息互信息（Mutual Information, MI）是信息论中的一个重要概念，用于衡量两个随机变量之间的相关性。

互信息的定义如下：对于离散型随机变量X和Y，其联合概率分布为P(X, Y)，边缘概率分布分别为P(X)和P(Y)，则X和Y的互信息I(X; Y)定义为：I(X; Y) = ΣΣP(X, Y)log(P(X, Y) / (P(X)P(Y)))对于连续型随机变量X和Y，互信息的定义稍有不同，这里不做详细展开。

3. K-近邻法与互信息的关联K-近邻法的关键在于样本之间的距离度量，通常使用的距离度量有欧氏距离、曼哈顿距离、闵可夫斯基距离等。

而互信息则可以用于衡量两个随机变量之间的关联程度。

我们可以利用K-近邻法来近似计算互信息。

4. K-近邻法求解互信息的计算过程我们假设有两个随机变量X和Y，它们分别有n个样本。

现在，我们希望利用K-近邻法来计算它们之间的互信息。

步骤一：计算X和Y的联合概率分布在K-近邻法中，我们需要计算样本之间的距离。

对于X和Y的每一个样本Xi和Yi，我们可以根据它们的特征值计算它们之间的距离，得到一个距离矩阵。

假设我们选择欧氏距离作为距离度量，那么对于Xi和Yi，它们之间的距离可以表示为：d(Xi, Yi) = sqrt(Σ(Xij - Yij)^2)其中，Xij和Yij分别表示Xi和Yi的第j个特征值。

k近邻算法水果案例k近邻算法是一种常用的分类算法，其基本思想是通过计算待分类样本与训练样本之间的距离，选取距离最近的k个样本作为邻居，根据邻居的标签来确定待分类样本的类别。

在这里，我们以水果分类为例，介绍k近邻算法的应用。

1. 数据收集：首先，我们需要收集一些水果的特征数据，包括颜色、形状、重量等特征。

同时，还需要为每个水果标注其对应的类别，如苹果、橙子、香蕉等。

2. 数据预处理：在进行分类之前，我们需要对数据进行预处理，包括数据清洗、缺失值处理、特征选择等。

例如，如果有些样本的特征值缺失，我们可以使用均值或中值进行填充；如果某个特征对分类结果影响较小，我们可以将其剔除。

3. 特征工程：为了提高分类的准确性，我们可以进行一些特征工程的处理。

例如，我们可以将颜色特征转化为颜色的HSV值，以增加颜色特征的区分度；还可以将形状特征转化为轮廓的特征向量，以增加形状特征的准确性。

4. 训练集和测试集划分：为了评估分类算法的准确性，我们需要将数据集划分为训练集和测试集。

通常，将数据集的70%作为训练集，30%作为测试集。

5. 特征标准化：由于不同特征的取值范围可能不同，为了保证各个特征对分类的贡献相同，我们需要对特征进行标准化处理。

常用的方法有Z-score标准化和Min-Max标准化。

6. 计算距离：在k近邻算法中，我们需要计算待分类样本与训练样本之间的距离。

常用的距离计算方法有欧氏距离、曼哈顿距离和余弦相似度等。

7. 选择k值：k值的选择对于分类结果的准确性有着重要的影响。

一般来说，较小的k值容易受到噪声的影响，较大的k值容易忽略样本之间的细节。

通常，我们可以通过交叉验证的方法来选择合适的k值。

8. 进行分类：选取距离最近的k个样本作为邻居后，我们可以根据邻居的标签来确定待分类样本的类别。

通常采用多数表决的方式，即将邻居中出现最多次数的类别作为待分类样本的类别。

9. 评估分类准确性：为了评估分类算法的准确性，我们可以计算分类的准确率、精确率、召回率和F1值等指标。

k-最近邻算法
1.k-最近邻算法是一种基于实例（Instance-based）的学习方法，也称为惰性学习（Lazy learning）方法或者近似实例学习方法。

它是一种分类方法，它不学习实例及其
之间的关系，而是直接存储数据，当需要进行分类预测时，寻找距离最近的K个点，然后
根据这些点的类别进行预测。

2.k-最近邻算法原理：通过比较未知实例与训练数据库中的实例，测量它们之间的距离，来预测该未知实例的类别。

与距离它最近的K个实例的类别最多的作为该未知实例的
类别。

3.k-近邻算法的优缺点：
优点：
1.简单易行：最近邻算法是计算机最简单的分类算法，直观有效，操作简单易行。

2.可预测性良好：最近邻分类算法可以获得较好的解决方法，并达到较高的预测性能。

3.大规模数据集可以很快地进行分类：kNN算法仅依赖训练数据中出现的模型，而不
用于存储数据，因此它可以在庞大的数据集上进行分类并实现极快的计算性能。

1.计算复杂度高：KNN算法比较复杂，需要调参数，计算复杂度较高且及时性较差。

2.存在样本不平衡问题：由于KNN算法没有考虑数据的内在分布特征，对于样本不平
衡的问题容易出现误分的情况。

3.维数灾难：KNN算法容易陷入维数灾难，即随着维数增加，距离也会不断增加，准
确率越来越低。