k-Nearest Neighbors

 

简介

 

    KNN 法即K最近邻法，最初由Cover和Hart于1968年提出的，是一个理论上比较成熟的方法。该方法的思路非常简单直观：如果一个样本在特征空间中的k 个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决 定待分样本所属的类别。

    KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。因此，采用这种方法可以较好地避免样本的不平衡问题。另外，由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说， KNN方法较其他方法更为适合。

    该方法的不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。另外还有一种Reverse KNN法，能降低KNN算法的计算复杂度，提高分类的效率。

    该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。

    k近邻分类器具有良好的文本分类效果，对仿真实验结果的统计分析表明:作为文本分类器，k近邻仅次于支持向量机，明显优于线性最小二乘拟合、朴素贝叶斯和神经网络。

 

关于分类算法，可以参考soso团队博文：

http://blog.csdn.net/soso_blog/archive/2010/06/22/5685774.aspx

 

1余弦定理和新闻的分类

 

余弦定理和新闻的分类似乎是两件八杆子打不着的事，但是它们确有紧密的联系。具体说，新闻的分类很大程度上依靠余弦定理。

Google 的新闻是自动分类和整理的。所谓新闻的分类无非是要把相似的新闻放到一类中。计算机其实读不懂新闻，它只能快速计算。这就要求我们设计一个算法来算出任意 两篇新闻的相似性。为了做到这一点，我们需要想办法用一组数字来描述一篇新闻。

我们来看看怎样找一组数字，或者说一个向量来描述一篇新 闻。回忆一下我们在“如何度量网页相关性 ” 一文中介绍的TF/IDF 的概念。对于一篇新闻中的所有实词，我们可以计算出它们的单文本词汇频率/逆文本频率值（TF/IDF)。不难想象，和新闻主题有关的那些实词频率 高，TF/IDF 值很大。我们按照这些实词在词汇表的位置对它们的 TF/IDF 值排序。比如，词汇表有六万四千个词，分别为

单词编 号 汉字词
------------------
1 阿
2 啊
3 阿斗
4 阿姨
...
789 服装
....
64000 做作

在一篇新闻中，这 64,000 个词的 TF/IDF 值分别为

单词编号 TF/IDF 值
==============
1 0
2 0.0034
3 0
4 0.00052
5 0
...
789 0.034
...
64000 0.075


如果单词表中的某个次在新闻中没有出现，对应的值为零，那么这 64,000 个数，组成一个64,000维的向量。我们就用这个向量来代表这篇新闻，并成为新闻的特征向量。如果两篇新闻的特征向量相近，则对应的新闻内容相似，它们 应当归在一类，反之亦然。

学过向量代数的人都知道，向量实际上是多维空间中有方向的线段。如果两个向量的方向一致，即夹角接近零，那么这 两个向量就相近。而要确定两个向量方向是否一致，这就要用到余弦定理计算向量的夹角了。

余弦定理对我们每个人都不陌生，它描述了三角形中 任何一个夹角和三个边的关系，换句话说，给定三角形的三条边，我们可以用余弦定理求出三角形各个角的角度。假定三角形的三条边为 a, b 和 c，对应的三个角为 A, B 和 C，那么角 A 的余弦 --



如果我们将三角形的两边 b 和 c 看成是两个向量，那么上述公式等价于



其中分母表示两个向量 b 和 c 的长度，分子表示两个向量的内积。举一个具体的例子，假如新闻 X 和新闻 Y 对应向量分别是
x1,x2,...,x64000 和
y1,y2,...,y64000,
那 么它们夹角的余弦等于，



当两条新闻向量夹角的余弦等于一时，这两条新闻完全重复（用这个办法可以删除重复的网页）；当夹 角的余弦接近于一时，两条新闻相似，从而可以归成一类；夹角的余弦越小，两条新闻越不相关。

 

2.KNN算法描述

 

比如说这里有两篇文章，这两篇文章中都有hibernate和spring这两个单词，在第一篇文章中hibernate出现了10次，spring出现 了20次，第二篇文章中hibernate出现15次，spring出现10次，那么对第一篇文章来说有两个项向量，分别是 hibernate:10,spring:20，第二篇文章类似，hibernate:15,spring:10。然后我们就可以在二维空间的x，y组上 表示出来。这样看来我们其实是要得到两者之间的夹角，计算两个向量之间夹角的公式为A*B/||A||*||B||。按照这个原理我们就可以得到新文章和样 本文章之间的距离

 

根据kNN的原理，我们记录下待分类数据和样本数据的距离，对每一个待分类数据都找出k个距离最小的样本，最后判断这些样本所在的分类， 这些样本所在的分类就是该新数据应该所在的分类。

那么根据以上的描述，我把结合使用反余弦匹配和kNN结合的过程分成以下几个步骤：
1， 计算出样本数据和待分类数据的距离
2， 为待分类数据选择k个与其距离最小的样本
3， 统计出k个样本中大多数样本所属的分类
4， 这个分类就是待分类数据所属的分类

 

public double caculateVectorSpace(Map<String, Integer> articleVectorMap,
			Map<String, Integer> classVectorMap) {
		if (articleVectorMap == null || classVectorMap == null) {
			if (logger.isDebugEnabled()) {
				logger.debug("itemVectorMap or classVectorMap is null");
			}

			return 20;
		}

		int dotItem = 0;
		double denominatorOne = 0;
		double denominatorTwo = 0;

		for (Entry<String, Integer> entry : articleVectorMap.entrySet()) {
			String word = entry.getKey();
			double categoryWordFreq = 0;
			double articleWordFreq = 0;

			if (classVectorMap.containsKey(word)) {
				categoryWordFreq = classVectorMap.get(word).intValue()
						/ classVectorMap.size();
				articleWordFreq = entry.getValue().intValue()
						/ articleVectorMap.size();
			}

			dotItem += categoryWordFreq * articleWordFreq;
			denominatorOne += categoryWordFreq * categoryWordFreq;
			denominatorTwo += articleWordFreq * articleWordFreq;
		}

		double denominator = Math.sqrt(denominatorOne)
				* Math.sqrt(denominatorTwo);

		double ratio = dotItem / denominator;

		return Math.acos(ratio);
	}

 

 

参考文章：

1.分类算法小结

http://blog.csdn.net/discxuwei/archive/2010/02/08/5297240.aspx

2.Google数学之美系列-余弦定理和新闻的分类

http://www.google.com.hk/ggblog/googlechinablog/2006/07/12_4010.html

3.数据挖掘之分类（kNN算法的描述及使用）

http://www.iteye.com/topic/164435