❶ excel怎么用k近邻算法
K近邻算法的原理非常简单：对于一个新的数据而言，K近邻算法的目的就是在已有数据中寻找与它最相似的K个数据，或者说“离它最近”的K个数据，如果这K个点大多数属于某一个类别，则该样本也属于这个类别。
❷ 八：聚类算法K-means（20191223-29)
学习内容：无监督聚类算法K-Means
k-means：模型原理、收敛过程、超参数的选择
聚类分析是在数据中发现数据对象之间的关系，将数据进行分组，组内的相似性越大，组间的差别越大，则聚类效果越好。
不同的簇类型： 聚类旨在发现有用的对象簇，在现实中我们用到很多的簇的类型，使用不同的簇类型划分数据的结果是不同的。
基于原型的： 簇是对象的集合，其中每个对象到定义该簇的 原型 的距离比其他簇的原型距离更近，如(b)所示的原型即为中心点，在一个簇中的数据到其中心点比到另一个簇的中心点更近。这是一种常见的 基于中心的簇 ，最常用的K-Means就是这样的一种簇类型。 这样的簇趋向于球形。
基于密度的 ：簇是对象的密度区域，(d)所示的是基于密度的簇，当簇不规则或相互盘绕，并且有早上和离群点事，常常使用基于密度的簇定义。
关于更多的簇介绍参考《数据挖掘导论》。
基本的聚类分析算法
1. K均值： 基于原型的、划分的距离技术，它试图发现用户指定个数(K)的簇。
2. 凝聚的层次距离： 思想是开始时，每个点都作为一个单点簇，然后，重复的合并两个最靠近的簇，直到尝试单个、包含所有点的簇。
3. DBSCAN: 一种基于密度的划分距离的算法，簇的个数有算法自动的确定，低密度中的点被视为噪声而忽略，因此其不产生完全聚类。
不同的距离量度会对距离的结果产生影响，常见的距离量度如下所示：
优点：易于实现
缺点：可能收敛于局部最小值，在大规模数据收敛慢
算法思想：
选择K个点作为初始质心
repeat
将每个点指派到最近的质心，形成K个簇
重新计算每个簇的质心
until 簇不发生变化或达到最大迭代次数
这里的“重新计算每个簇的质心”，是根据目标函数来计算的，因此在开始时要考虑 距离度量和目标函数。
考虑欧几里得距离的数据，使用 误差平方和（Sum of the Squared Error,SSE） 作为聚类的目标函数，两次运行K均值产生的两个不同的簇集，使用SSE最小的那个。
k表示k个聚类中心，ci表示第几个中心，dist表示的是欧几里得距离。
这里有一个问题就是为什么，我们更新质心是让所有的点的平均值，这里就是SSE所决定的。
k均值算法非常简单且使用广泛，但是其有主要的两个缺陷：
1. K值需要预先给定 ，属于预先知识，很多情况下K值的估计是非常困难的，对于像计算全部微信用户的交往圈这样的场景就完全的没办法用K-Means进行。对于可以确定K值不会太大但不明确精确的K值的场景，可以进行迭代运算，然后找出Cost Function最小时所对应的K值，这个值往往能较好的描述有多少个簇类。
2. K-Means算法对初始选取的聚类中心点是敏感的 ，不同的随机种子点得到的聚类结果完全不同
3. K均值算法并不是很所有的数据类型。 它不能处理非球形簇、不同尺寸和不同密度的簇，银冠指定足够大的簇的个数是他通常可以发现纯子簇。
4. 对离群点的数据进行聚类时，K均值也有问题 ，这种情况下，离群点检测和删除有很大的帮助。
下面对初始质心的选择进行讨论：
当初始质心是随机的进行初始化的时候，K均值的每次运行将会产生不同的SSE,而且随机的选择初始质心结果可能很糟糕，可能只能得到局部的最优解，而无法得到全局的最优解。
多次运行，每次使用一组不同的随机初始质心，然后选择一个具有最小的SSE的簇集。该策略非常的简单，但是效果可能不是很好，这取决于数据集合寻找的簇的个数。
关于更多，参考《数据挖掘导论》
为了克服K-Means算法收敛于局部最小值的问题，提出了一种 二分K-均值(bisecting K-means)
将所有的点看成是一个簇
当簇小于数目k时
对于每一个簇
计算总误差
在给定的簇上进行K-均值聚类,k值为2 计算将该簇划分成两个簇后总误差
选择是的误差最小的那个簇进行划分
在原始的K-means算法中，每一次的划分所有的样本都要参与运算，如果数据量非常大的话，这个时间是非常高的，因此有了一种分批处理的改进算法。
使用Mini Batch（分批处理）的方法对数据点之间的距离进行计算。
Mini Batch的好处：不必使用所有的数据样本，而是从不同类别的样本中抽取一部分样本来代表各自类型进行计算。n 由于计算样本量少，所以会相应的减少运行时间n 但另一方面抽样也必然会带来准确度的下降。
聚类试图将数据集中的样本划分为若干个通常是不相交的子集，每个子集成为一个“簇”。通过这样的划分，每个簇可能对应于一些潜在的概念（也就是类别）；需说明的是，这些概念对聚类算法而言事先是未知的，聚类过程仅能自动形成簇结构，簇对应的概念语义由使用者来把握和命名。
聚类是无监督的学习算法，分类是有监督的学习算法。所谓有监督就是有已知标签的训练集（也就是说提前知道训练集里的数据属于哪个类别），机器学习算法在训练集上学习到相应的参数，构建模型，然后应用到测试集上。而聚类算法是没有标签的，聚类的时候，需要实现的目标只是把相似的东西聚到一起。
聚类的目的是把相似的样本聚到一起，而将不相似的样本分开，类似于“物以类聚”，很直观的想法是同一个簇中的相似度要尽可能高，而簇与簇之间的相似度要尽可能的低。
性能度量大概可分为两类： 一是外部指标， 二是内部指标 。
外部指标：将聚类结果和某个“参考模型”进行比较。
内部指标：不利用任何参考模型，直接考察聚类结果。
对于给定的样本集，按照样本之间的距离大小，将样本集划分为K个簇。让簇内的点尽量紧密的连在一起，而让簇间的距离尽量的大
初学者会很容易就把K-Means和KNN搞混，其实两者的差别还是很大的。
K-Means是无监督学习的聚类算法，没有样本输出；而KNN是监督学习的分类算法，有对应的类别输出。KNN基本不需要训练，对测试集里面的点，只需要找到在训练集中最近的k个点，用这最近的k个点的类别来决定测试点的类别。而K-Means则有明显的训练过程，找到k个类别的最佳质心，从而决定样本的簇类别。
当然，两者也有一些相似点，两个算法都包含一个过程，即找出和某一个点最近的点。两者都利用了最近邻(nearest neighbors)的思想。
优点：
简单， 易于理解和实现 ；收敛快，一般仅需5-10次迭代即可，高效
缺点：
1，对K值得选取把握不同对结果有很大的不同
2，对于初始点的选取敏感，不同的随机初始点得到的聚类结果可能完全不同
3，对于不是凸的数据集比较难收敛
4，对噪点过于敏感，因为算法是根据基于均值的
5，结果不一定是全局最优，只能保证局部最优
6，对球形簇的分组效果较好，对非球型簇、不同尺寸、不同密度的簇分组效果不好。
K-means算法简单理解，易于实现（局部最优），却会有对初始点、噪声点敏感等问题；还容易和监督学习的分类算法KNN混淆。
参考阅读：
1.《 深入理解K-Means聚类算法 》
2.《 K-Means 》
❸ 实验二 K-近邻算法及应用
（1）简单，易于理解，易于实现，无需估计参数。
（2）训练时间为零。它没有显示的训练，不像其它有监督的算法会用训练集train一个模型（也就是拟合一个函数），然后验证集或测试集用该模型分类。KNN只是把样本保存起来，收到测试数据时再处理，所以KNN训练时间为零。
（3）KNN可以处理分类问题，同时天然可以处理多分类问题，适合对稀有事件进行分类。
（4）特别适合于多分类问题(multi-modal,对象具有多个类别标签)， KNN比SVM的表现要好。
（5）KNN还可以处理回归问题，也就是预测。
（6）和朴素贝叶斯之类的算法比，对数据没有假设，准确度高，对异常点不敏感。
（1）计算量太大，尤其是特征数非常多的时候。每一个待分类文本都要计算它到全体已知样本的距离，才能得到它的第K个最近邻点。
（2）可理解性差，无法给出像决策树那样的规则。
（3）是慵懒散学习方法，基本上不学习，导致预测时速度比起逻辑回归之类的算法慢。
（4）样本不平衡的时候，对稀有类别的预测准确率低。当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。
（5）对训练数据依赖度特别大，对训练数据的容错性太差。如果训练数据集中，有一两个数据是错误的，刚刚好又在需要分类的数值的旁边，这样就会直接导致预测的数据的不准确。
需要一个特别容易解释的模型的时候。
比如需要向用户解释原因的推荐算法。
通过此次实验我了解了K近邻算法及其思路，该方法的思路是：如果一个样本在特征空间中的k个最相似的样本中的大多数属于某一个类别，则该样本也属于这个类别。
所谓k近邻算法，即是给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的k个实例。
❹ 12 - SVM, KNN，LR, RF简要介绍
这里接 第11篇 的介绍。
支持向量机是可对类别进行分类的有监督的学习算法。其在样本的特征空间中找出间隔最大的超平面对样本进行分类。SVM根据其学习算法不同可划分为线性可分SVM、线性近似可分SVM与非线性SVM。实现上述三种SVM主要依靠核函数—线性核函数、高斯核函数、多项式核函数与Sigmoid核函数，后三种核函数为非线性，一般建议使用高斯核函数。
如上图，对于二分类，SVM需要确定一条最优直线使两类样本分开，在图1-4中A可以看到有多条直线可将两组分开，但最优的是图1-4中B的w*x+b=0直线。对于最优直线的确定，需要使最优直线到最近点的距离最大，最近点被称为支持向量（如图1-4中B的红点/圈），这里的距离是求出点到直线的距离最大，这是在二维空间，当在三维及其以上的空间时，直线变为超平面，距离则需要求点到超平面的几何距离（Westreich et al 2010）。
SVM的优点：（1）适用各种形式的数据，如文本、图像等；（2）泛化能力较好，即其过拟合的风险小；（3）相对较好地处理高维度数据；（4）核函数的应用使其能很好的适应各种情况。其缺点：（1）对大规模数据难以处理；（2）只依靠少数支持向量决定最终结果，如有异常值，则结果容易出现较大偏差；（3）对缺失值敏感（Westreich et al 2010）。
K最近邻算法是通过计算样本特征之间的距离，根据距离k进行分类，属于无参数分类和回归方法（Altman 1992）。距离k的度量可以使用闵可夫斯基距离、欧氏距离与曼哈顿距离等距离公式进行计算，一般其取20以内的正整数，较大的k取值会降低噪音对分析的影响，且一般对于二分类问题，取k为奇数将有利于判别。
闵可夫斯基距离公式为：
上述公式中，当p=2时，变为欧氏距离，当p=1时，变为曼哈顿距离（Hechenbichler and Schliep 2004）。
KNN属于“懒惰学习”，即只是将训练集数据储存起来，再来新样本时进行距离计算，根据投票结果判别新样本属于哪一类。例如图1-6，蓝色方框与红色三角为已知的训练集，当有绿色圆圈新样本进行判别时，假设k为1，则有两个红色三角与一个为蓝色方框参与判别，这样投票结果为2:1，故绿色圆圈属于红色三角形一类；假如k为2，则有两个红色三角与三个为蓝色方框参与判别，这样投票结果为2:3，故绿色圆圈属于蓝色方框。所以k值需要选择，一般是根据经验进行设置，并且每个样本（如红三角）对判别决策所占的比重也可以进行设定即为权重KNN（Hechenbichler and Schliep 2004）。
逻辑回归是一种有监督的学习方法，其函数基本的公式：
上述公式为Sigmoid函数，图为1-7，其输出值在[0, 1]之间，需要选择一个阈值，通常是0.5，当p(x) > 0.5时，x为A类，如果p(x) < 0.5时，x为B类。阈值可以调整，其代表对于这个事情的把握度，如上述的阈值为0.5，如计算的p(x1)=0.3，则有50%的把握认为x1属于B类（Press 2013）。
LR的运算基本过程：（1）假设p(x)=1，构造sigmoid函数，即利用最大似然取对数作为误差函数，用梯度下降求最小的误差函数值，求出a与b；（2）根据训练数据集多组数据，重复循环（1）n次，计算数据集梯度，更新sigmoid参数，确定最终的sigmoid函数；（3）输入预测集数据；（4）运用最终sigmoid函数求解分类（Dreiseitl and Ohno-Machado 2002）。
LR的优点：（1）容易接收新数据，对模型更新；（2）能够容易解决变量间的共线性问题；（3）运算速度快，适合二分类问题。其缺点：（1）适用的数据和具体场景较少；（2）不适用于样本具有很大的特征值（即变量过多）；（3）容易欠拟合，分类准确性较低；（4）使用前提是应变量和自变量有线性关系，只是广义线性模型，不能处理非线性问题。
随机森林是将多个决策树集合在一起的一种算法，基本单元为决策树，并且可以用于回归和分类（Breiman 2001, Liaw and Wiener 2002）。其名字由“随机”与“森林”组成，“随机”有两个含义，一指在训练集中随机且有放回的抽取n个样本进行建模，二指每个节点在特征值M中随机抽取k（k<M）个进行建模，且每个节点处的k应相同，这两个随机使该算法不容易过拟合（Ho 1998）。“森林”即为多个决策树组成，其要求基本同上述的决策树，但这里的决策树没有剪枝的过程，让其尽量生长（Cutler et al 2012）。其将多个决策树组合在一起是采用集成学习方法，该算法的中心思想是让每个决策树产生一个结果，再对这些结果进行统计，哪种结果数量最多，即为最终结果。
RF实现的过程（1）随机有放回的从样本N中选出n个子样本；（2）每个节点在特征值M中随机选出k个特征值；（3）重复第一与第二步s次，创建s个决策树；（4）对s个决策树结果分析，哪一类决策树最多，则最终判别为哪一类。
RF算法主要有两个参数，第一个为抽取每个样本的特征值k，第二个为决策树的数量。特征值k一般建议为全部特征值的开方（Geurts et al 2006）。在确定较优的k后，一般取决策树数为500进行尝试，查看随着决策树的数量增多，袋外错误率是否会稳定在一个定值，取能达到这个定值的最小决策树数的数量。
随机森林算法优点：（1）能够有效处理大数据；（2）能处理高维度变量的样本，不需要降维；（3）能较好处理缺失值问题。其缺点：（1）不能直观进行解释（2）过度拟合某些具有噪声分类。
上述的八种算法，一般多用于二分类问题，如“有或无”与“好或坏”等，但在实际应用中也有较多的多分类问题，如彩虹可以划分7种颜色，当判别一个新的颜色属于这7种颜色的哪一种时，这就需要解决一个七分类问题。多分类是二分类的一个拓展，解决办法有两种，第一种是一对多，即先从K类中选出一种，剩余K-1类归为一种，这样需要建立K个判别模型，当有新数据进行判别时，新样本需在K个判别模型中，同时进行判别，看被判别为哪一类的可能性最大，就判别为哪类；
❺ 02 KNN算法 - KD Tree
KD Tree 是KNN算法中用于计算最近邻的快速简便的构建方式。
当样本量少的时候，用 brute 直接搜索最近邻的方式是可行的。即计算到所有样本的距离。但当样本量庞大时，直接计算所有样本距离的工作量很大，这种情况使用 KD Tree 可以节约大量时间成本。
KD树采用从m个样本的n维特征中，分别计算n个特征取值的方差，用 方差最大 的第k维特征n k 作为 根节点 。对于这个特征，选择取值中的 中位数 n kv 作为样本的划分点，对于小于该值的样本划分到 左子树 ，对于大于等于该值的样本划分到 右子树 ，对左右子树采用同样的方式找 方差最大的特征 作为 根节点 ，递归产生KD Tree。
为什么要选择方差最大的进行划分？
构建树的目的是加快我的搜索过程。
既然我想加快我的搜索过程，要就意味着我最终的数据落在某个叶子节点上。我希望只需搜索整个二叉树的某一些列即可，那么最好的划分方式，就是让我的每个分支上数据的差异性最大化。
那么衡量数据差异性的最基础的数学指标是什么？
是方差。方差越大，意味着数据的离散程度就越大，我将离散程度由大到小的数据一分为二，方差小意味着数据更集中到了一起。
现在有一个二维样本: {(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)}
1、计算x1和x2每一列对应的方差
a、通过pandas计算出的是 样本方差:
/ (n-1)
0| 6.966667
1| 5.366667
dtype: float64
b、通过numpy计算出的是 总体方差:
/ n
[[2 3]
[5 4]
[9 6]
[4 7]
[8 1]
[7 2]]
[ 5.80555556 4.47222222]
[ 5.80555556 4.47222222]
第一个树的划分：基于x 1 进行划分
[2,4,5,7,8,9]的中位数是5和7的平均值6。
虽然严格意义上说中位数是6，但是在计算机中我们人为得定义x 1 的中位数是7。
左侧：（2,3）（5,4）（4,7） （7,2）
右侧: （9,6）（8,1）
第二个树的划分：根据右侧（9,6）（8,1）的x 2 进行划分
下侧：x 2 ≤ 6；上侧x 2 ＞6
第二个树的划分：根据左侧（2,3）（5,4）（4,7） （7,2）的x 2 进行划分
寻找2、3、4、7的中位数 4 进行划分
....
注意：每次生成的划分都是一个矩形。当叶子节点无法被继续划分的时候，KD树的构建完成，递归结束。
我们生成了KD Tree后，现在就可以去预测测试集里面的样本目标点了。
1、对于一个目标点，先在KD树里找到包含目标点的叶子节点。
2、以目标点为圆心，以 目标点 到 叶子节点样本实例 的距离为半径，得到一个超球体，最近邻的点一定在这个超球体内部。
3、然后返回叶子节点的父节点，检查另一个子节点包含的超矩形体是否和超球体相交。
4、如果相交就倒这个子节点寻找着是否有更加近的近邻，有的话就更新最近邻。
5、如果不相交，直接返回父节点中的父节点，在另一个子树继续搜索最近邻。当回溯到根节点时，算法结束。
6、此时保存的最近邻节点就是最终的最近邻。
如果现在想找(2,4.5)这点的最近邻，该如何操作？
1、画出二叉树：
2、寻找(2,4.5)这点：
一个比较好的理解方式：首先找到第一个最近邻，然后画出一个圆。然后逐渐收缩圆的半径，查看每次缩小后的圆是否能够和矩形相交于一个更小的最近邻点，如果有则更新。直到回到根节点。
❻ R语言-KNN算法
1、K最近邻(k-NearestNeighbor，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。
2、KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。 KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。
3、KNN算法不仅可以用于分类，还可以用于回归。通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight)，如权值与距离成正比。
简言之，就是将未标记的案例归类为与它们最近相似的、带有标记的案例所在的类 。
原理及举例
工作原理：我们知道样本集中每一个数据与所属分类的对应关系，输入没有标签的新数据后，将新数据与训练集的数据对应特征进行比较，找出“距离”最近的k（通常k<20）数据，选择这k个数据中出现最多的分类作为新数据的分类。
算法描述
1、计算已知数据集中的点与当前点的距离
2、按距离递增次序排序
3、选取与当前数据点距离最近的K个点
4、确定前K个点所在类别出现的频率
5、返回频率最高的类别作为当前类别的预测
距离计算方法有"euclidean"（欧氏距离）,”minkowski”（明科夫斯基距离）, "maximum"（切比雪夫距离）, "manhattan"（绝对值距离）,"canberra"（兰式距离）, 或 "minkowski"（马氏距离）等
Usage
knn(train, test, cl, k = 1, l = 0, prob =FALSE, use.all = TRUE)
Arguments
train
matrix or data frame of training set cases.
test
matrix or data frame of test set cases. A vector will be interpreted as a row vector for a single case.
cl
factor of true classifications of training set
k
number of neighbours considered.
l
minimum vote for definite decision, otherwisedoubt. (More precisely, less thank-ldissenting votes are allowed, even
ifkis increased by ties.)
prob
If this is true, the proportion of the votes for the
winning class are returned as attributeprob.
use.all
controls handling of ties. If true, all distances equal
to thekth largest are
included. If false, a random selection of distances equal to thekth is chosen to use exactlykneighbours.
kknn(formula = formula(train), train, test, na.action = na.omit(), k = 7, distance = 2, kernel = "optimal", ykernel = NULL, scale=TRUE, contrasts = c('unordered' = "contr.mmy", ordered = "contr.ordinal"))
参数：
formula A formula object.
train Matrix or data frame of training set cases.
test Matrix or data frame of test set cases.
na.action A function which indicates what should happen when the data contain ’NA’s.
k Number of neighbors considered.
distance Parameter of Minkowski distance.
kernel Kernel to use. Possible choices are "rectangular" (which is standard unweighted knn), "triangular", "epanechnikov" (or beta(2,2)), "biweight" (or beta(3,3)), "triweight" (or beta(4,4)), "cos", "inv", "gaussian", "rank" and "optimal".
ykernel Window width of an y-kernel, especially for prediction of ordinal classes.
scale Logical, scale variable to have equal sd.
contrasts A vector containing the ’unordered’ and ’ordered’ contrasts to use
kknn的返回值如下：
fitted.values Vector of predictions.
CL Matrix of classes of the k nearest neighbors.
W Matrix of weights of the k nearest neighbors.
D Matrix of distances of the k nearest neighbors.
C Matrix of indices of the k nearest neighbors.
prob Matrix of predicted class probabilities.
response Type of response variable, one of continuous, nominal or ordinal.
distance Parameter of Minkowski distance.
call The matched call.
terms The ’terms’ object used.
iris%>%ggvis(~Length,~Sepal.Width,fill=~Species)
library（kknn）
data（iris）
dim(iris)
m<-(dim(iris))[1]
val<-sample(1:m,size=round(m/3）,replace=FALSE,prob=rep(1/m,m))
建立训练数据集
data.train<-iris[-val,]
建立测试数据集
data.test<-iris[val,]
调用kknn 之前首先定义公式
formula ： Species ~ Sepal.Length + Sepal.Width + Petal.Length + Petal.Width
iris.kknn<-kknn(Species~.,iris.train,iris.test,distance=1,kernel="triangular")
summary(iris.kknn)
# 获取fitted.values
fit <- fitted(iris.kknn)
# 建立表格检验判类准确性
table(iris.valid$Species, fit)
# 绘画散点图，k-nearest neighbor用红色高亮显示
pcol <- as.character(as.numeric(iris.valid$Species))
pairs(iris.valid[1:4], pch = pcol, col = c("green3", "red")[(iris.valid$Species != fit)+1]
二、R语言knn算法
install.packages("class")
library(class)
对于新的测试样例基于距离相似度的法则，确定其K个最近的邻居，在K个邻居中少数服从多数
确定新测试样例的类别
1、获得数据
2、理解数据
对数据进行探索性分析，散点图
如上例
3、确定问题类型，分类数据分析
4、机器学习算法knn
5、数据处理，归一化数据处理
normalize <- function(x){
num <- x - min(x)
denom <- max(x) - min(x)
return(num/denom)
}
iris_norm <-as.data.frame(lapply(iris[,1:4], normalize))
summary(iris_norm)
6、训练集与测试集选取
一般按照3:1的比例选取
方法一、set.seed(1234)
ind <- sample(2,nrow(iris), replace=TRUE, prob=c(0.67, 0.33))
iris_train <-iris[ind==1, 1:4]
iris_test <-iris[ind==2, 1:4]
train_label <-iris[ind==1, 5]
test_label <-iris[ind==2, 5]
方法二、
ind<-sample(1:150,50)
iris_train<-iris[-ind,]
iris_test<-iris[ind,1:4]
iris_train<-iris[-ind,1:4]
train_label<-iris[-ind,5]
test_label<-iris[ind,5]
7、构建KNN模型
iris_pred<-knn(train=iris_train,test=iris_test,cl=train_label,k=3)
8、模型评价
交叉列联表法
table（test_label,iris_pred)
实例二
数据集
http://archive.ics.uci.e/ml/machine-learning-databases/breast-cancer-wisconsin/wdbc.data
导入数据
dir <-'http://archive.ics.uci.e/ml/machine-learning-databases/breast-cancer-wisconsin/wdbc.data'wdbc.data <-read.csv(dir,header = F)
names(wdbc.data) <- c('ID','Diagnosis','radius_mean','texture_mean','perimeter_mean','area_mean','smoothness_mean','compactness_mean','concavity_mean','concave points_mean','symmetry_mean','fractal dimension_mean','radius_sd','texture_sd','perimeter_sd','area_sd','smoothness_sd','compactness_sd','concavity_sd','concave points_sd','symmetry_sd','fractal dimension_sd','radius_max_mean','texture_max_mean','perimeter_max_mean','area_max_mean','smoothness_max_mean','compactness_max_mean','concavity_max_mean','concave points_max_mean','symmetry_max_mean','fractal dimension_max_mean')
table(wdbc.data$Diagnosis)## M = malignant, B = benign
wdbc.data$Diagnosis <- factor(wdbc.data$Diagnosis,levels =c('B','M'),labels = c(B ='benign',M ='malignant'))
❼ K-近邻算法简介
1.K-近邻(KNearestNeighbor,KNN)算法简介 ：对于一个未知的样本，我们可以根据离它最近的k个样本的类别来判断它的类别。
以下图为例，对于一个未知样本绿色小圆，我们可以选取离它最近的3的样本，其中包含了2个红色三角形，1个蓝色正方形，那么我们可以判断绿色小圆属于红色三角形这一类。
我们也可以选取离它最近的5个样本，其中包含了3个蓝色正方形，2个红色三角形，那么我们可以判断绿色小圆属于蓝色正方形这一类。
3.API文档
下面我们来对KNN算法中的参数项做一个解释说明：
'n_neighbors'：选取的参考对象的个数（邻居个数），默认值为5，也可以自己指定数值，但不是n_neighbors的值越大分类效果越好，最佳值需要我们做一个验证。
'weights': 距离的权重参数，默认uniform。
'uniform': 均匀的权重，所有的点在每一个类别中的权重是一样的。简单的说，就是每个点的重要性都是一样的。
'distance'：权重与距离的倒数成正比，距离近的点重要性更高，对于结果的影响也更大。
'algorithm':运算方法，默认auto。
'auto'：根绝模型fit的数据自动选择最合适的运算方法。
'ball_tree'：树模型算法BallTree
'kd_tree'：树模型算法KDTree
'brute'：暴力算法
'leaf_size'：叶子的尺寸，默认30。只有当algorithm = 'ball_tree' or 'kd_tree'，这个参数需要设定。
'p'：闵可斯基距离，当p = 1时，选择曼哈顿距离；当p = 2时，选择欧式距离。
n_jobs：使用计算机处理器数目，默认为1。当n=-1时，使用所有的处理器进行运算。
4.应用案例演示
下面以Sklearn库中自带的数据集--手写数字识别数据集为例，来测试下kNN算法。上一章，我们简单的介绍了机器学习的一般步骤：加载数据集 - 训练模型 - 结果预测 - 保存模型。这一章我们还是按照这个步骤来执行。
[手写数字识别数据集] https://scikit-learn.org/stable/moles/generated/sklearn.datasets.load_digits.html#sklearn.datasets.load_digits
5.模型的方法
每一种模型都有一些它独有的属性方法（模型的技能，能做些什么事），下面我们来了解下knn算法常用的的属性方法。
6.knn算法的优缺点
优点：
简单，效果还不错，适合多分类问题
缺点：
效率低（因为要计算预测样本距离每个样本点的距离，然后排序），效率会随着样本量的增加而降低。
❽ 核密度估计与k近邻估计的区别
核密度估计实际上是表现一组数据的分布情况，转录组中用来展示所有样本基因的表达量丰度分布。kNN是一种基本分类与回归方法。
k-NN的输入为实例的特征向量，对应于特征空间中的点，输出为实例的类别，可以取多类。k近邻实际上利用训练数据集对特征向量空间进行划分，并作为其分类的“模型”。k值的选择、距离度量及分类决策规则是k近邻的三个基本要素。核密度估计（kerneldensityestimation）是在概率论中用来估计未知的密度函数，属于非参数检验方法之一，Ruppert和Cline基于数据集密度函数聚类算法提出修订的核密度估计方法。
K最近邻(k-NearestNeighbor，KNN)，是一种常用于分类的算法，是有成熟理论支撑的、较为简单的经典机器学习算法之一。
❾ 简单数字识别(knn算法)
knn算法，即k-NearestNeighbor，后面的nn意思是最近邻的意思，前面的k是前k个的意思，就是找到前k个离得最近的元素
离得最近这个词具体实现有很多种，我使用的是欧式几何中的距离公式
二维中两点x(x1,y1),y(x2,y2)间距离公式为sqrt( (x1-x2)^2+(y1-y2)^2 )
推广到n维就是
x(x1,x2, … ,xn),y(y1,y2, … ,yn)
sqrt [ ∑( x[i] - y[i] )^2 ] (i=1,2, … ,n)
knn算法是要计算距离的，也就是数字之间的运算，而图像是png，jpg这种格式，并不是数字也不能直接参与运算，所以我们需要进行一下转换
如图所示一个数字8，首先要确定的是这一步我做的是一个最简单的转换，因为我假定背景和图之间是没有杂物的，而且整个图只有一个数字（0-9）如果遇到其他情况，比如背景色不纯或者有其他干扰图像需要重新设计转换函数
接下来就是最简单的转换，将图片白色部分（背景）变0，有图像的部分变1。转换后的大小要合适，太小会影响识别准确度，太大会增加计算量。所以我用的是书上的32*32，转换后结果如图所示
这样一来，图片就变成了能进行计算的数字了。
接下来我们需要创建一个库，这个库里面存着0-9这些数字的各种类似上图的实例。因为我们待识别的图像要进行对比，选出前k个最近的，比较的对象就是我们的库。假定库中有0-9十个数字，每个数字各有100个这种由0和1表示的实例，那么我们就有了一共1000个实例。
最后一步就是进行对比，利用开头说的欧式几何距离计算公式，首先这个32*32的方阵要转换成一个1*1024的1024维坐标表示，然后拿这个待识别的图像和库中的1000个实例进行距离计算，选出前k个距离最近的。比如50个，这50个里面出现次数最多的数字除以50就是结果数字的概率。比如50个里面数字8出现40次，那么待识别数字是8的可能性就是40/50 = 80%
个人理解：
只能识别单个数字，背景不能有干扰。如果想多数字识别或者背景有干扰需要针对具体情况考虑具体的图像转01的方法。
数字识别非常依赖库中的图像，库中的图像的样子严重影响图像的识别（因为我们是和库中的一一对比找出距离最近的前k个），所以数字的粗细，高低，胖瘦等待都是决定性因素，建库时一定全面考虑数字的可能样子
计算量比较大，待识别图像要和库中所有实例一一计算，如果使用32*32，就已经是1024维了。如果库中有1000个，那就是1024维向量之间的1000次计算，图像更清晰，库更丰富只会使计算量更大
对于其他可以直接计算距离的数值型问题，可以用欧式距离，也可以用其他能代表距离的计算公式，对于非数值型的问题需要进行合适的转换，转换方式很重要，我觉得首先信息不能丢失，其次要精确不能模糊，要实现图片转换前后是一对一的关系
参考资料：机器学习实战 [美] Peter Harrington 人民邮电出版社
python源码
import numpy
import os
from PIL import Image
import heapq
from collections import Counter
def pictureconvert(filename1,filename2,size=(32,32)):
#filename1待识别图像，filename2 待识别图像转换为01txt文件输出，size图像大小，默认32*32
image_file = Image.open(filename1)
image_file = image_file.resize(size)
width,height = image_file.size
f1 = open(filename1,'r')
f2 = open(filename2,'w')
for i in range(height):
for j in range(width):
pixel = image_file.getpixel((j,i))
pixel = pixel[0] + pixel[1] + pixel[2]
if(pixel == 0):
pixel = 0
elif(pixel != 765 and pixel != 0):
pixel = 1
# 0代表黑色（无图像），255代表白色（有图像）
# 0/255 = 0,255/255 = 1
f2.write(str(pixel))
if(j == width-1):
f2.write('\n')
f1.close()
f2.close()
def imgvector(filename):
#filename将待识别图像的01txt文件转换为向量
vector = numpy.zeros((1,1024),numpy.int)
with open(filename) as f:
for i in range(0,32):
linestr = f.readline()
for j in range(0,32):
vector[0,32*i+j] = int(linestr[j])
return vector
def compare(filename1,filename2):
#compare直接读取资源库识别
#filename1资源库目录，filename2 待识别图像01txt文档路径
trainingfilelist = os.listdir(filename1)
m = len(trainingfilelist)
labelvector = []
trainingmatrix = numpy.zeros((m, 1024), numpy.int8)
for i in range(0,m):
filenamestr = trainingfilelist[i]
filestr = filenamestr.split('.')[0]
classnumber = int(filestr.split('_')[0])
labelvector.append(classnumber)
trainingmatrix[i,:] = imgvector(filename1 + '/' + filenamestr)
textvector = imgvector(filename2)
resultdistance = numpy.zeros((1,m))
result = []
for i in range(0,m):
resultdistance[0,i] = numpy.vdot(textvector[0],trainingmatrix[i])
resultindices = heapq.nlargest(50,range(0,len(resultdistance[0])),resultdistance[0].take)
for i in resultindices:
result.append(labelvector[i])
number = Counter(result).most_common(1)
print('此数字是',number[0][0],'的可能性是','%.2f%%' % ((number[0][1]/len(result))*100))
def distinguish(filename1,filename2,filename3,size=(32,32)):
# filename1 png，jpg等格式原始图像路径，filename2 原始图像转换成01txt文件路径，filename3 资源库路径
pictureconvert(filename1,filename2,size)
compare(filename3,filename2)
url1 = "/Users/wang/Desktop/number.png"
url2 = "/Users/wang/Desktop/number.txt"
traininglibrary = "/Users/wang/Documents/trainingDigits"
distinguish(url1,url2,traininglibrary)
❿ 技术 | 文本聚类与分类
按照处理的对象和处理的方法不同，可将常见文本分类/聚类任务分为以下几种：
① 文档聚类： 把一组未知类别的文档划分为若干类别，例如将介绍奥运会的新闻都归到某一类；
② 文档分类： 给定一个文档，将其划分到预定义好的某一个类别中，例如将所有介绍奥运会的新闻都标记为“体育”；
③ 词汇聚类： 把一组未知类别的词汇划分为若干类别，例如将各种运动的项目名称（词汇）都归为一类；
④ 词汇分类： 给定一个词汇，将其划分到预定义好的某一个类别中，例如将篮球、足球等都比较为球类，将打猎、射箭等都标记为射击。
要实现上述目的，通常有以下几个核心问题要解决：
1. 特征选择
1.1 用什么作为特征项
用于表示文本的基本单位通常称为文本的特征或特征项。特征项必须满足：能够标识文本内容、能够将目标文本与其他文本相区分、个数不能太多、特征项分离要比较容易实现。在中文文本中可以采用字、词或短语作为表示文本的特征项。
相比较而言，词比字具有更强的表达能力，而词和短语相比，词的切分难度比短语的切分难度小得多。因此，目前大多数中文文本分类系统都采用词作为特征项，称作特征词。这些特征词作为文档的中间表示形式，用来实现文档与文档、文档与用户目标之间的相似度计算 。
1.2 选取哪些作为特征项
如果把所有的词都作为特征项，那么特征向量的维数将过于巨大，从而导致计算量太大，在这样的情况下，要完成文本分类几乎是不可能的。特征提取的主要功能是在不损伤文本核心信息的情况下尽量减少要处理的单词数，以此来降低向量空间维数，从而简化计算，提高文本处理的速度和效率。
特征选取的方式有2种：用映射或变换的方法把原始特征变换为较少的新特征（将原始特征用新特征表示）；从原始特征中挑选出一些最具代表性的特征（只保留部分原始特征，不产生新特征），即根据某个特征评估函数计算各个特征的评分值，然后按评分值对这些特征进行排序，选取若干个评分值最高的作为特征词，常见的特征评估函数包括TF-IDF、信息增益、互信息等。
2. 文本表示
2.1 如何表示文档
为了让计算机能够“计算”文本，就需要我们将文本数据转换成计算机可以处理的结构化数据。常见的文本表示模型有布尔模型、向量空间模型、统计主题模型等。其中，向量空间模型概念简单，把对文本内容的处理简化为向量空间中的向量运算，并且它以空间上的相似度表达语义的相似度，直观易懂，目前应用最广。
2.2 如何确立权重
一篇文档有很多词，有些词表达的语义很重要，有些相对次要，那么如何确定哪些重要？哪些次要呢？因此，需要进一步对每个词的重要性进行度量。常见的确立词汇权重的算法有TF-IDF、词频法等。
3. 相似性计算
要实现文本的分类和聚类，需要设计一种算法计算出文档与文档、词汇与词汇之间的相似性。
3.1 文档相似性
设定我们要比较X和Y间的差异，它们都包含了N个维的特征，即X=（x1, x2, x3, … xn），Y=（y1, y2, y3, … yn）。下面来看看主要可以用哪些方法来衡量两者的差异，主要分为距离度量和相似度度量。
a. 距离度量
距离度量（Distance）用于衡量个体在空间上存在的距离，距离越远说明个体间的差异越大。常见的距离有欧几里得距离(Euclidean Distance)、明可夫斯基距离(Minkowski Distance)、曼哈顿距离(Manhattan Distance)、切比雪夫距离(Chebyshev Distance)、马哈拉诺比斯距离(Mahalanobis Distance)。
b. 相似性度量
相似度度量（Similarity），即计算个体间的相似程度，与距离度量相反，相似度度量的值越小，说明个体间相似度越小，差异越大。常见的相似性度量有向量空间余弦相似度(Cosine Similarity)、皮尔森相关系数(Pearson Correlation Coefficient)、Jaccard相似系数(Jaccard Coefficient)、调整余弦相似度(Adjusted Cosine Similarity)。
欧氏距离是最常见的距离度量，而余弦相似度则是最常见的相似度度量，很多的距离度量和相似度度量都是基于这两者的变形和衍生，所以下面重点比较下两者在衡量个体差异时实现方式和应用环境上的区别。下面借助三维坐标系来看下欧氏距离和余弦相似度的区别：
从图上可以看出距离度量衡量的是空间各点间的绝对距离，跟各个点所在的位置坐标（即个体特征维度的数值）直接相关；而余弦相似度衡量的是空间向量的夹角，更加的是体现在方向上的差异，而不是位置。如果保持A点的位置不变，B点朝原方向远离坐标轴原点，那么这个时候余弦相似度cosθ是保持不变的，因为夹角不变，而A、B两点的距离显然在发生改变，这就是欧氏距离和余弦相似度的不同之处。
根据欧氏距离和余弦相似度各自的计算方式和衡量特征，分别适用于不同的数据分析模型：欧氏距离能够体现个体数值特征的绝对差异，所以更多的用于需要从维度的数值大小中体现差异的分析，如使用用户行为指标分析用户价值的相似度或差异；而余弦相似度更多的是从方向上区分差异，而对绝对的数值不敏感，更多的用于使用用户对内容评分来区分用户兴趣的相似度和差异，同时修正了用户间可能存在的度量标准不统一的问题（因为余弦相似度对绝对数值不敏感）。
3.2 词汇相似性
目前我接触的常见词汇相似性的方法有：
a. 传统图情领域：基于共现频次这一基本统计量衍生出来的，如association strength、inclusion index、Jaccard’s coefficient、Salton’s cosine（Ochiia系数）等；
b. 计算机领域：一是基于语义词典的方法，即依据词典分类体系挖掘所包含的词义知识，常用的词典包括Wordnet、Hownet等；二是基于语料库的方法，这里的语料库较为多元，例如网络预料、唐诗宋词预料等；；三是进行词向量化，如Word2vec。
4. 文本分类/聚类算法
有了文本表示方法，又有了计算相似性的公式，下一步就可以在此基础上讨论文本分类/聚类的算法了。
4.1 文本分类
医生对病人进行诊断就是一个典型的分类过程，任何一个医生都无法直接看到病人的病情，只能观察病人表现出的症状和各种化验检测数据来推断病情，这时医生就好比一个分类器，而这个医生诊断的准确率，与他当初受到的教育方式（构造方法）、病人的症状是否突出（待分类数据的特性）以及医生的经验多少（训练样本数量）都有密切关系。
分类器是对样本进行分类的方法的统称，包含决策树、逻辑回归、朴素贝叶斯、神经网络等算法。举个例子：假如你想区分小明是好学生还是坏学生，那么区分“好学生”和“坏学生”就是一个分类任务。
4.1.1 K最邻近
“别和其他坏学生在一起，否则你也会和他们一样。” —— 家长
主要思想是通过离待预测样本最近的K个样本的类别来判断当前样本的类别。从K最近邻算法的角度来看，就是让目标样本与其他正样本距离更近、与其他负样本距离更远，从而使得其近邻中的正样本比例更高，更大概率被判断成正样本。
4.1.2 朴素贝叶斯
“根据以往抓获的情况来看，十个坏学生有九个爱打架。” —— 教导主任
“十个坏学生有九个爱打架”就意味着“坏学生”打架的概率P(打架|坏学生)=0.9，假设根据训导处历史记录坏学生占学生总数P(坏学生)=0.1、打架发生的概率是P(打架)=0.09，那么这时如果发生打架事件，就可以通过贝叶斯公式判断出当事学生是“坏学生”的概率P(坏学生|打架)=P(打架|坏学生)×P(坏学生)÷P(打架)=1.0，即该学生100%是“坏学生”。
4.1.3 决策树
“先看抽不抽烟，再看染不染头发，最后看讲不讲脏话。” ——社区大妈
假设“抽烟”、“染发”和“讲脏话”是社区大妈认为的区分“好坏”学生的三项关键特征，那么这样一个有先后次序的判断逻辑就构成一个决策树模型。在决策树中，最能区分类别的特征将作为最先判断的条件，然后依次向下判断各个次优特征。决策树的核心就在于如何选取每个节点的最优判断条件，也即特征选择的过程。
而在每一个判断节点，决策树都会遵循一套IF-THEN的规则：
IF “抽烟” THEN -> “坏学生” ELSE IF “染发” THEN -> “坏学生” ELSE IF “讲脏话” THEN -> “坏学生” ELSE -> “好学生”
4.1.4 逻辑回归
“上课讲话扣1分，不交作业扣2分，比赛得奖加5分。” ——纪律委员
我们称逻辑回归为一种线性分类器，其特征就在于自变量x和因变量y之间存在类似y=ax+b的一阶的、线性的关系。假设“上课讲话”、“不交作业”和“比赛得奖”的次数分别表示为x1、x2、和x3，且每个学生的基础分为0，那么最终得分y=-1 x1-2 x2+5*x3+0。其中-1、-2和5分别就对应于每种行为在“表现好”这一类别下的权重。
对于最终得分y，逻辑回归还通过Sigmoid函数将其变换到0-1之间，其含义可以认为是当前样本属于正样本的概率，即得分y越高，属于“表现好”的概率就越大。也就是说，假如纪律委员记录了某位同学分别“上课讲话”、“不交作业”和“比赛得奖”各一次，那么最终得分y=-2-1+5=2，而对2进行Sigmoid变换后约等于0.88，即可知该同学有88%的概率为“好学生”。
4.1.5 支持向量机
“我想个办法把表现差的学生都调到最后一排。” ——班主任
支持向量机致力于在正负样本的边界上找到一条分割界线（超平面），使得它能完全区分两类样本的同时，保证划分出的间隔尽量的大。如果一条分割界线无法完全区分（线性不可分），要么加上松弛变量进行适当的容忍，要么通过核函数对样本进行空间上的映射后再进行划分。对于班主任来讲，调换学生们的座位就相当于使用了核函数，让原本散落在教室里的“好”、“坏”学生从线性不可分变得线性可分了。
4.2 文本聚类
4.2.1 基于分层的聚类
hierarchical methods： 对数据集进行逐层分解，直到满足某种条件为止。可分为“自底向上”和“自顶向下”两种。例如“自底向上”指初始时每个数据点组成一个单独的组，在接下来的迭代中，按一定的距离度量将相互邻近的组合并成一个组，直至所有的记录组成一个分组或者满足某个条件为止。代表算法有：BIRCH，CURE，CHAMELEON等。自底向上的凝聚层次聚类如下图所示。
4.2.2 基于划分的聚类
partitioning methods： 给定包含N个点的数据集，划分法将构造K个分组，每个分组代表一个聚类，这里每个分组至少包含一个数据点，每个数据点属于且仅属于一个分组。对于给定的K值，算法先给出一个初始的分组方法，然后通过反复迭代的方法改变分组，使得每一次改进之后的分组方案较前一次好，这里好的标准在于同一组中的点越近越好，不同组中的点越远越好。代表算法有：K-means，K-medoids，CLARANS。K-means聚类过程图解如下：
4.2.3 基于密度的聚类
density-based methods： 基于密度的方法的特点是不依赖于距离，而是依赖于密度，从而克服基于距离的算法只能发现“球形”聚簇的缺点。其核心思想在于只要一个区域中点的密度大于某个阈值，就把它加到与之相近的聚类中去。代表算法有：DBSCAN，OPTICS，DENCLUE，WaveCluster。DBSCAN的聚簇生成过程的简单理解如下图。
4.2.3 基于网格的聚类
gird-based methods： 这种方法通常将数据空间划分成有限个单元的网格结构，所有的处理都是以单个的单元为对象。这样做起来处理速度很快，因为这与数据点的个数无关，而只与单元个数有关。代表算法有：STING，CLIQUE，WaveCluster。基于Clique的聚类过程可直观如下图进行理解。
4.2.4 基于模型的聚类
model-based methods： 基于模型的方法给每一个聚类假定一个模型，然后去寻找能很好的拟合模型的数据集。模型可能是数据点在空间中的密度分布函数或者其它。这样的方法通常包含的潜在假设是：数据集是由一系列的潜在概率分布生成的。通常有两种尝试思路：统计学方法和神经网络方法。其中，统计学方法有COBWEB算法、GMM(Gaussian Mixture Model)，神经网络算法有SOM(Self Organized Maps)算法。下图是GMM过程的一个简单直观地理解。
4.2.5 基于图论的聚类
图论聚类方法解决的第一步是建立与问题相适应的图，图的节点对应于被分析数据的最小单元，图的边（或弧）对应于最小处理单元数据之间的相似性度量。因此，每一个最小处理单元数据之间都会有一个度量表达，这就确保了数据的局部特性比较易于处理。图论聚类法是以样本数据的局域连接特征作为聚类的主要信息源，因而其主要优点是易于处理局部数据的特性。典型算法有谱聚类。
聚类问题的研究不仅仅局限于上述的硬聚类，即每一个数据只能被归为一类，模糊聚类也是聚类分析中研究较为广泛的一个分支。模糊聚类通过隶属函数来确定每个数据隶属于各个簇的程度，而不是将一个数据对象硬性地归类到某一簇中。目前已有很多关于模糊聚类的算法被提出，如着名的FCM算法等。