k Nearest Neighbor Algorithm
k Nearest Neighbor(kNN) algorithm算法和k-Means算法一样,都是简单理解,但是实际效果出人意料的算法之一。正式由于其算法思想简单,很多人可能会认为在工程中用途有限,实际上kNN和k-Means两种算法正是凭借其算法思想入选 Top Ten Data Mining Algorithm(http://www.cs.umd.edu/~samir/498/10Algorithms-08.pdf),成为值得深入学习和思考的算法。
kNN算法是最简单的机器学习算法之一,采用空间向量模型分类;在概念空间上为相同或者相似类别的数据,彼此的相似度比较高;而借由计算已知类别数据和未知数据的相似程度,来计算位置数据的分类,是典型的监督算法(Supervised Algorithm)。
kNN在分类数据时,使用到了相似度的概念,而kNN正式按照相似度对位置数据分类;那么衡量数据相似度的度量就是一种很重要的标准,如欧式空间可以使用Euclidean Distance(L2)、City-Block Distance(L1)等,文本数据使用TF-IDF等。关于距离或者相似度的概念,这里有篇比较全的文章, http://isilic.iteye.com/blog/1816986,大家可以参考下距离的特征,以及使用距离的场景。
算法思路:
如果一个样本在特征空间中的K个最相似的样本中大多数都属于某类别,则该样本页数于该类别。在该算法中,所选择的邻居是已经正确分类的对象,在决定测试数据的分类时,依赖邻近的一个或者多个样本来决定测试数据的类别。从原理上来看,kNN算法依赖于极限定理;但是在具体决策上,至于少数相邻的样本数据有关。
如果样本数据集空间分布有交叉或者重叠,kNN方法较其它方法更为合适;因为kNN是Instance-Based算法,而不是靠判别(discriminative)来确定数据类别。
从上面的算法描述可以看出来,kNN算法具有下列特性:
1:Lazy Learning Algorithm:接到测试样例才会进行kNN算法计算,并且会搜索所有的样本数据,最终给出直接分类,没有其它的信息可用。
2:Non-parameter:直接计算,基于实例(Instance Based),
3:Majority Vote:邻近节点的属于某类别的多数决定。
和Eager Learning算法相比,需要保存样例在内存中,存储数据量比较大,内存要求高;在训练阶段计算比较少,测试样例计算量都集中在测试阶段,计算要求高。
简单提下Lazy Learning Algorithm,这类算法在训练阶段有优势,但是在测试阶段计算量比较大;常用的其它的Lazy Algorithm的称呼还有Memory-Based、Exemplar-Based、Case-Based、Experience-Based等,含义都比较简单形象。
参数选择
k参数对于算法的性能影响巨大:较大的k值能够避免噪声数据的影响,但是也会使分类之间变得难以区分。一般的比较好的k值都是通过启发式技术得到,最为特殊的例子就是当k=1时称为是最邻近算法(Nearest Neighbor Algorithm)。另外kNN算法的精确度受到样本数据无关属性、噪声数据的英标比较大,尤其是特征属性和数据重要性分类无关时。所以kNN算法的大部分精力都放在特征选取(Feature Selecting or Scaling)上,当然这个就是另外比较高深的问题了;两种比较常用的做法是通过evolutionary algorithms优化特征缩放和利用训练数据的Mutual Information来缩放特征。
kNN用于回归:
kNN算法用于回归时,可以找出K个邻近的数据点,将这些数据的属性平均的赋给该样本,就可以得到该样本的属性;更为通用的方法是将距离不同的样本赋予不同的权重值(Weithted)。
kNN用于分类
分类思想如上,当k=1时相当于Nearest Neighbor Search。当然对于分类也可以使用权重(Weighted)算法。
下面我们看下对于带权重的kNN(Weighted kNN)几种算法思路,都用到了Gradient Descent算法:
Instance-Weighted kNN:基于实例的权重kNN
该算法有两个假设:首先所有的属性石都是数字后者是可以衡量的;其次样本属性值离散。
将数据分组,使用交叉验证(cross validation)的思路:
使用全部数据(whole dataset)时:
Attribute-Weighted kNN:基于实例样本属性的权重kNN
使用cross validation,将权重添加到样本数据属性上,注意Attribute和Instance的区别
当使用全部数据集合(whole set)时:
Backward Elimination
反向消除是通过估计反复对数据集合操作,如果删除某个样本属性后,精确度降低,就将该属性再添加进距离度量,直到获得最为合适的属性;在后来的计算过程中就是用这些属性,降低计算复杂度,但是训练过程倒是复杂了不少。
Curse of Dimensionality
1:距离和样本的维度有关,通常是和样本的所有维度有关,样本的维度对于距离的影响是一样的
2:相似性并不考虑样本属性对于最终分类结果的影响;并且在很大程度上分类错误是因为很多无关属性的计算,属性计算越多,维度灾难发生的可能性越大。
3:和距离、相似性相关的算法都会有维度灾难问题(Curse of Dimensionality)
数据搜索:
1:Brute-Force,遍历暴力搜索,这个最为简单,但是性能最差,数据稍微有点数量级别提升,就无法进行。
2:Index-Tree,索引树结构,包括以前提到的 kd-tree ,还有其它结构的索引结构,R tree、B Tree等。通过索引结构能够大大提升搜索的效率,对于kNN的实用是个很重要的一环。
综上,kNN的实用有几个关键点:
1:数据清理,包括Scaling、Outliar检测等。
2:数据特征选择
3:搜索数据结构优化
如果预处理好这些问题,kNN算法的优势还是比较明显的,不会比其它分类算法差;既有kNN算法的优点,又不失数据准确性。
相关推荐
coding for k nearest neighbor algorithm
java实现KNN(k-Nearest Neighbor algorithm)算法,可以设置改变k值。
该文献的主要思想是:输入文件的哈希值(我用的是文件名)例如一个64位的哈希值,多次随机抽取若干位(例如4位)的值组成一个字串,按照字串值的不同将文件放入不同的哈希桶中。这样一个64位哈希值将被放入64/4=16个...
False Nearest Neighbor Searching algorithm.在国内非常罕见的算法。为了解决科学研究的需求用来4周编译处理的。这个软件包市作经济分析的必备工具,当然,非线性系统中更是不可缺少的东西了。 由于该软件包的技术...
algorithm for nearest neighbor search from MIT
K nearest neighbor algorithm for indoor localization
code for approximate nearest neighbor algorithm,最经典的近似搜索算法
邻近算法,或者说K最近邻(kNN,k-NearestNeighbor)分类算法是数据挖掘分类技术中最简单的方法之一。所谓K最近邻,就是k个最近的邻居的意思,说的是每个样本都可以用它最接近的k个邻居来代表。 kNN算法的核心思想是...
所提出的算法基于 k 最近邻方法,其中 k 的值是唯一的算法参数,用于控制最终解决方案的“平滑度”。 该算法的思想属于: 莫雷拉、阿德里亚诺和桑托斯、马里贝尔。 (2007)。 Concave hull:用于计算由一组点占据...
FKNN Fuzzy k-nearest neighbor classification algorithm.
An improved K-nearest-neighbor algorithm for text categorization
In this paper, we describe a system that answers the question, “What is the fastest approximate nearest-neighbor algorithm for my data? ” Our system will take any given dataset and desired degree ...
是K最邻近结点算法(k-Nearest Neighbor algorithm)的缩写形式,是电子信息分类器算法的一种。KNN方法对包容型数据的特征变量筛选尤其有效。
针对传统的基于WiFi的最近邻(K-nearest neighbor algorithm, WiFi-KNN)室内定位算法精确度不能达到精准定位的需求的问题,本文提出了一种基于位置范围限定的K近邻(K-nearest neighbor based on the location range ...
global nearest neighbor algorithm
knn(k-Nearest Neighbor algorithm)最邻近算法程序
FKNN Fuzzy k-nearest neighbor classification rule;参考文献:A Fuzzy K-Nearest Neighbor Algorithm", IEEE Transactions on Systems, Man, and Cybernetics, Vol. 15, No. 4, pp. 580-585.
KNN也称作K最邻近结点算法(k-Nearest Neighbor algorithm)的缩写形式,是分类预测的经典算法之一。在煤炭勘探过程中,往往希望将新勘探出来的煤炭产品分类预测,并采取对应类别的煤炭处理和保存措施。文中,将采用基于...
Nearest Neighbour algorithm for a TSP with 7 cities. The solution changes as the starting point is changed The nearest neighbour (NN) algorithm (a greedy algorithm) lets the salesperson choose the ...