KNN算法描述

dewlily

数据挖掘之web文本归类算法的设计与实现

 

1 引言

自动分类器利用机器学习原理对网页进行分类。分类器的工作步骤如下：
（1）利用搜狐分类目录的分类样本集进行训练，获得每个分类在特征空间上的聚类中心。

（2）采用用户选择的分类器对接收的文本进行自动分类，并输出结果。
分类器被应用在网页搜索的分类提示功能中。分类提示功能不是简单的关键字叠加。

下面对分类流程作个简要描述：

训练：训练集——>特征选取——>训练——>分类器

分类：新样本——>特征选取——>分类——>判决

分类器自动判断出文本所属的分类，然后按分类下结果多少给出提示，帮助用户有效缩小结果集，更精准地找到所需的信息。

训练语料:搜狗实验室提供的分类语料精简版,另自己爬了些数据
训练词典:搜狗实验室提供的词典,包含IDF,词性等值

包含大类:房产，汽车，财经，IT，医疗，教育，旅游，体育，招聘，政治，军事

实现算法:

训练,解压搜狗分类语料,对各个类别分别训练,利用我自己变通的KNN算法,得到每种语料的学习结果
分类,给定一篇文本,分词,得到每一个词的权重,然后根学习结果比较,最相近的一类就是它所属的大类.

缺点:训练语料都是新闻类,所以测试最好用新闻语料.另IT类训练语料问题,IT类误差较大.

2 KNN文本分类算法描述

KNN算法的决策过程

　　k-Nearest Neighbor algorithm

　　图中，绿色圆要被决定赋予哪个类，是红色三角形还是蓝色四方形？如果K=3，由于红色三角形所占比例为2/3，绿色圆将被赋予红色三角形那个类，如果K=5，由于蓝色四方形比例为3/5，因此绿色圆被赋予蓝色四方形类。 

　　K最近邻(k-Nearest Neighbor，KNN)分类算法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。 KNN方法虽然从原理上也依赖于极限定理，但在类别决策时，只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本，而不是靠判别类域的方法来确定所属类别的，因此对于类域的交叉或重叠较多的待分样本集来说，KNN方法较其他方法更为适合。

　　KNN算法不仅可以用于分类，还可以用于回归。通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight)，如权值与距离成正比。

　　该算法在分类时有个主要的不足是，当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。因此可以采用权值的方法（和该样本距离小的邻居权值大）来改进。该方法的另一个不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。该算法比较适用于样本容量比较大的类域的自动分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。

 

相关资料：

1. k-nearest neighbor algorithm:  http://en.wikipedia.org/wiki/K-nearest_neighbor_algorithm

 

2. k-nearest neighbor algorithm in Visual Basic and Java http://paul.luminos.nl/documents/show_document.php?d=197

http://paul.luminos.nl/update/408