第六章-K近邻

K近邻算法2017目录K近邻K-D树的构造和查询作业•背景•定义•距离度量•K的选择•手写识别例子•KNN总结背景•K-近邻算法（KNN算法）是一种用于分类和回归的非参数统计方法。•最近邻方法在1970年代初被用于统计估计和模式识别领域。•该方法仍然是十大数据挖掘算法之一。Youaretheaverageofthefivepeopleyouspendmosttimewith.—JimRohnScottDinsmore::Howtofindworkyoulove|TEDTalk•近朱者赤近墨者黑•把这种思想用于数据方面形式化描述Note:•kNN算法的核心思想是如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别，则该样本也属于这个类别，并具有这个类别上样本的特性。•“K”表示分类考虑的数据集项目的数量。•K-NN是一种基于实例的学习。•k-近邻算法是所有的机器学习算法中最简单的方法之一。形式化描述给定训练数据（或已标记数据）(𝑥1,𝑦1),...,(𝑥𝑁,𝑦𝑁)以及测试点𝑥𝑁对;𝑥𝑖是D维特征所组成的向量,𝑦𝑖-标记或类别预测准则：寻找训练数据中最近的K个样本目标:输出对未知标记或类别的样本𝑥的预测𝑦形式化描述输出形式:分类问题:离散值𝑦𝑖∈1,...,𝐶多数投票(majorityvoting)回归问题：连续的（实值）变量𝑦𝑖∈𝑅平均值averageresponse这个算法需要:参数K:寻找的近邻个数距离函数:计算样本之间的相似度常见的度量方式三维空间中的欧氏距离欧氏距离（Euclideandistance）最常使用在二维欧式平面中,两点p=(p1,p2)和q=(q1,q2)的距离为一般的，n维空间中的距离常见的度量方式一般的，n维空间中的两点的曼哈顿距离是曼哈顿距离（ManhattanDistance）常见的度量方式闵可夫斯基距离(MinkowskiDistance)闵氏距离不是一种距离，而是一组距离的定义，是对多个距离度量公式的概括性的表述。之间的闵式距离定义为：𝑝=(𝑝1，𝑝2，...，𝑝𝑛)𝑞=(𝑞1，𝑞2，...，𝑞𝑛)|𝑝𝑖−𝑞𝑖|𝑚𝑛𝑖=11𝑚和m取1或2时的闵氏距离是最为常用的，m=2即为欧氏距离，而m=1时则为曼哈顿距离。当m取无穷时的极限情况下，可以得到切比雪夫距离。两个n维变量常见的度量方式夹角余弦（Cosinesimilarity）几何中，夹角余弦可用来衡量两个向量方向的差异；机器学习中，借用这一概念来衡量样本向量之间的差异。两个n维样本点的夹角余弦为：夹角余弦取值范围为[-1,1]。余弦越大表示两个向量的夹角越小，余弦越小表示两向量的夹角越大。当两个向量的方向重合时余弦取最大值1，当两个向量的方向完全相反余弦取最小值-1。常见的度量方式Hammingdistance(汉明距离)两个等长字符串s1与s2的汉明距离为：将其中一个变为另外一个所需要作的最小字符替换次数。•1011101and1001001is2.•2173896and2233796is3.例如:左右字符串之间的汉明距离分别是：汉明距离在包括信息论、编码理论、密码学等领域都有应用。比如在信息编码过程中，为了增强容错性，应使得编码间的最小汉明距离尽可能大。K-NN:特征归一化Note:特征应该在同一尺度距离度量会被数值较大的维度主导，既然数据各维分量的分布不一样，那先将各个分量都“标准化”到均值、方差相等。例如:代替by(零均值,单位方差):第m维特征的均值:第m维特征的方差𝑝𝑖K-NN:特征权重根据维度的重要性来赋予不同的权重使用先验知识来决定哪些维度的特征比较重要可以使用交叉验证法学习权重Wk(本课没有涉及)那么样本之间的权重又如何呢？K的选择理论上,如果有无穷多的样本,k越大,分类效果越好.这是不可能实现的，实际中样本个数总是有限的k=1最近样本的类别k=N样本个数最多的类别两种极端情况：K的选择k=1最常用，效果也较好,但是却对“噪声”敏感任何浅蓝色区域内的样本都会被错分为蓝色类别。任何浅蓝色区域内的样本都会被正确分类为红色类别。1NN3NN噪声样本1NN可视化维诺图(VoronoiDiagram)可以用来可视化维诺图基于一组特定点将平面分割成不同区域，而每一区域又仅包含唯一的特定点，并且该区域内任意位置到该特定点的距离比到其它的特定点都要更近。决策边界K的选择小K对每个类别都创建了许多小的分类区域对“噪声敏感”非平滑的决策边界，(可能导致过拟合)大K创建了少数大范围的区域,通常产生更平滑的决策边界可以降低噪声样本的影响(注意过于平滑的决策边界可能导致欠拟合)留出法•方法：直接将数据集划分为两个互斥的集合，训练集合和测试集合，模型在验证集上的表现就是对模型泛化能力的一种估计。•例如：训练集(80%)验证集(20%)•注意：训练／测试集的划分要尽可能保持数据分布的一致性，避免因为数据划分过程引入额外的偏差而对最终结果产生影响。•缺点与改进：使用留出法得到的估计往往不够稳定可靠。K折交叉验证留一法总结：距离度量&K的选择如何选择距离度量方式?欧氏距离（Euclidean）最为常用具体问题具体分析例如：对于一个复杂的问题，不同维度上也可以使用不同的度量方式最好是奇数1-NN在实践中经常表现不错一个有趣的理论性质是ksqrt(n),n是样本个数可以通过交叉验证法（cross-validation）等K的选择KaggleKaggle是一个数据建模和数据分析竞赛平台。企业和研究者可在其上发布数据，统计学者和数据挖掘专家可在其上进行竞赛以产生最好的模型。数字识别的例子近邻方法还是相当有竞争力的！数字识别的应用场景门牌号识别银行支票识别车牌号识别邮件数字识别数据集32x32像素的二值图像:d=10241,934个训练样本946个测试样本…数字识别的例子维度的“诅咒”K-NN在高维空间中失效,因为此时“Neighborhood”的空间变得非常巨大，这时候找到近邻点的距离相当远，以至于无法用于预测分类。维度的诅咒是指在高维空间中出现的各种现象，不存在于日常经验的的低维空间中。维数灾难最早是由理查德·贝尔曼（RichardE.Bellman）在考虑优化问题时提出来的，它用来描述当(数学)空间维度增加时，分析和组织高维空间(通常有成百上千维)中的数据，因体积指数增加而遇到各种问题场景。•存储和计算复杂性•样本稀疏•组合爆炸•近邻搜索•距离度量•非参估计•…等密度取样所需样本量1维：52维：5*5=2510维：5^10=9765625维数灾难的几个表现://blog.csdn.net/zc02051126/article/details/49618633://blog.csdn.net/zc02051126/article/details/49618633近邻搜索•假设在单位超立方体中的5000个点服从均匀分布，我们要应用5-nn算法。(假设我们的查询点在原点)•在一维中，5000个点均匀分布在单位长度1的线段上，我们必须查询5/5000=0.001的长度，以捕获5个最近邻居•在二维中，同样是5000个点均匀分布在单位面积1的矩形上，数据已经变得稀疏了，我们必须查询面积0.001的区域来得到5个最近邻居，小矩形的边长为0.0010.001•在n维空间中，我们必须查询大小（0.001）1/d—1的区域由于空间的急剧扩张，样本变得非常稀疏，为了找到最近的5个样本，需要查询的空间越来越接近于1，此时的邻居已经不在查询点附近。邻居之间相似性很低，分类效果也就很差，所以无法用来分类。维数灾难的几个表现://blog.csdn.net/zc02051126/article/details/49618633://blog.csdn.net/zc02051126/article/details/49618633组合爆炸问题、距离度量失效、概率密度估计…KNN性质总结优点：简单直观，训练非常快，易于实现特别适合多分类问题训练数据无限和足够大的K，K-NN方法效果会相当好！缺点：对噪声敏感（小K）即使在测试时间时，也需要存储所有训练数据查询时间慢：每个查询O（nd）复杂度在高维度上，距离的概念是违反直觉的！高维空间表现不佳（维度诅咒）也叫：记忆/实例学习懒惰学习降低复杂度•提出了各种精确和近似的方法来降低复杂性•降低计算复杂性的方法：ANN、BBF算法、LSH(局部敏感哈希)、RandomizedK-dtreesk-d树、球树、M树、VP树、MVP树下面介绍最常用的最近邻搜索算法：k-d树K-d树•20世纪70年代由JonBentley发明，k维空间中划分的一种数据结构，主要应用于多维空间范围搜索和最近邻搜索•Kd-树是K-dimensiontree的缩写，名称原来是指“3-D树，4-d树等”，其中k是尺寸的数量•思想：树的每个节点划分仅使用1个维比较。•用于存储空间数据。•最邻居搜索。•范围查询。•快速查找！3DK-d树K-d树构造(1)yabcghedixfK-d树构造(2)yxabcghedis1s1xfK-d树构造(3)yxabcghedis1s2ys1s2xfK-d树构造(4)yxabcghedis1s2ys3xs1s2s3xfK-d树构造(5)yxabcghedis1s2ys3xs1s2s3axfK-d树构造(6)yxabcghedis1s2ys3xs1s2s3abxfK-d树构造(7)yxabcghedis1s2ys3xs4ys1s2s3s4abxfK-d树构造(8)yxabcghedis1s2ys3xs4ys5xs1s2s3s4s5abxfK-d树构造(9)yxabcghedis1s2ys3xs4ys5xs1s2s3s4s5abdxfK-d树构造(10)yxabcghedis1s2ys3xs4ys5xs1s2s3s4s5abdexfK-d树构造(11)yxabcghedis1s2ys3xs4ys5xs1s2s3s4s5abdegxfgihs6cfs4ds5es2as3bs1yxs1s2yys6s3xs4ys5xabdegxK-d树构造(12)gihs6fs4ds5es2as3bs1s7cyxs1s2yys6s3xs4ys7ys5xabdegxK-d树构造(13)gihs6fs4ds5es2as3bs1s7cyxs1s2yys6s3xs4ys7ys5xabdegcxK-d树构造(14)gihs6fs4ds5es2as3bs1s7cyxs1s2yys6s3xs4ys7ys5xabdegcfxK-d树构造(15)gis8hs6fs4ds5es2as3bs1s7cyxs1s2yys6s3xs4ys7ys8ys5xabdegcfxK-d树构造(16)gis8hs6fs4ds5es2as3bs1s7cyxs1s2yys6s3xs4ys7ys8ys5xabdegcfhxK-d树构造(17)gis8hs6fs4ds5es2as3bs1s7cys2yys6s3xs4ys7ys8ys5xabdegcfhixk-dtreecellxs1K-d树构造(18)Anodehas5fields