KNN算法应用

应用场景
(1)文本分类:文本分类主要应用于信息检索，机器翻译，自动文摘，信息过滤，邮件分类等任务。

文本分类在搜索引擎中也有着大量的使用，网页分类/分层技术是检索系统的一项关键技术，搜索引擎需要研究如何对网页进行分类、分层，对不同类别的网页采用差异化的存储和处理，以保证在有限的硬件资源下，提供给用户一个高效的检索系统，同时提供给用户相关、丰富的检索结果。

在搜索引擎中，文本分类主要有这些用途:相关性排序会根据不同的网页类型做相应的排序规则;根据网页是索引页面还是信息页面，下载调度时会做不同的调度策略;在做页面信息抽取时，会根据页面分类的结果做不同的抽取策略;在做检索意图识别的时候，会根据用户所点击的url所属的类别来推断检索串的类别。

(2)回归:通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。

更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值(weight)，如权值与距离成正比。

(3)可以使用knn算法做到比较通用的现有用户产品推荐，基于用户的最近邻(长得最像的用户)买了什么产品来推荐是种介于电子商务网站和sns网站之间的精确营销。

只需要定期(例如每月)维护更新最近邻表就可以，基于最近邻表做搜索推荐可以很实时。

文本分类
1.KNN 算法最初由Cover 和Hart 于1968 年提出，该算法的基本思想是：根据传统的向量空间模型，文本内容被形式化为特征空间中的加权特征向量，即 D = D (T1，W1;T2,W2;…;Tn,Wn)。

对于一个测试文本，计算它与训练样本集中每个文本的相似度，找出K 个最相似的文本，根据加权距离和判断测试文本所属的类别。

具体算法步骤如下:
(1) 对于一个测试文本，根据特征词形成测试文本向量。

(2) 计算该测试文本与训练集中每个文本的文本相似度，计算公式为:
式中: x 为测试文本的特征向量；Sim(x,di)为相似度计算公式；b 为阈值，有待于优化选择；而y(di,Cj)的取值为1 或0，如果di属于Cj，则函数值为1，否则为0 。

(5)比较类的权重，将文本分到权重最大的那个类别中。

2.传统KNN 分类系统
传统的KNN 分类过程如图5-1：
传统的KNN 分类系统主要分为预处理、训练、分类三个阶段，如果要在不同时间进
行分类，则每次都需要对训练样本进行训练，这是造成了KNN 分类时间较长的原因之一，其实，在训练过程的一些数据，如特征集，训练好的样本等，对下一次分类同样有用。

3.改进后的分类系统
系统各模块的操作如下：
一、训练模块：训练模块在同一流程实现了预处理和训练两种功能，因为这两个模块的数据处理具有继承性，所以安排到同一模块实现。

“选择词典”按键将所使用的停用词词典加载到哈希表中；“选择维数”文本框可以更改文本向量的维数(特征数)；“训练文本库”按钮加载训练文本的文件夹，然后进行去停用词、分词、特征选择、特征权重计算、文本向量表示等一系列操作。

二、分类模块：“训练”按钮选择要进行分类的测试文本文件夹，读取测试文本，然后依次进行：分词、去停用词、特征选择、权重计算、向量表示、距离计算、K 近邻选择、类别评定等操作。

K 文本框输入为K 近邻数，n1为PKNN 算法选择的小样本数。

三、评价模块：评价模块实现分类结果的统计与评测，所采用的评价指标是：宏召回率、宏准确率、F1 值，“重置分类”键可以将内存中的全局变量清空，为下一次分类作准备，这样不需要再训练就能直接从xml文件中读取所需数据再次存放在全局变量中。

邮件过滤
随着互联网的广泛普及，电子邮件已经成为人们日常生活中最便捷、最经济的通信手段。

但是电子邮件给用户带来便捷的同时，也带来了不可避免的副产品——垃圾邮件。

由于实现比较简单以及受到利益的驱使，一些企业和个人采用了这种最经济的方式进行商业广告，一些黑客也采用发送电子邮件进行违法行为：盗窃用户的机密资料，攻击用户的电脑等。

电子邮件用户几乎每天都要收到几十、几百封垃圾邮件，每天都需要花费一定的精力与时间来判断是否为垃圾邮件，并进行清除。

垃圾邮件不仅影响到了电子邮件用户，对网络运营提供商和网络管理员也带来了无尽的烦恼。

这些所谓的垃圾邮件会占用用户的带宽、时间和存储资源，如果泛滥严重甚至会对网络通信造成堵塞，使得正常邮件不能正常发送和接收，垃圾邮件严重阻碍了互联网的健康发展。

因此对垃圾邮件过滤技术的研究具有很大的实用价值，也是亟待解决的问题。

传统的KNN 算法只考虑到相似度之和，或者简单的利用相似度个数的多少来进行判断；将KNN 算法应用于垃圾邮件的过滤中，而没有考虑到垃圾邮件本身的偏依赖特性，即用户情愿多收到一封垃圾邮件，也不愿意让垃圾邮件过滤系统将自己的正常邮件误判为垃圾邮件过滤掉；传统的KNN 分类算法进行分类时，每次都需要将待测样本和训练样本集中的每个样本进行比较，计算相似度，计算量十分的大，不适合实时性要求比较高的垃圾邮件过滤系统。

本文针对上述KNN 算法的不足之处进行改进，提出并设计一种考虑了偏依赖特性的基于平均相似度和相似度个数的KNN 算法。

该算法首先通过计算平均相似度而不是相似度之和来表示类权重值，同时考虑到相似样本的个数对分类性能的影响；其次引入了两个表示垃圾邮件本身的偏依赖特性的参数；最后，为了解决KNN 算法的计算量大的缺点，本文利用类中心向量法的思想，通过将将原始样本转化为一个个小类，并计算每个小类的中心向量，以代表原始训练样本建立分类模型，这就相当于将大样本转化为小样本，减少了比较次数，大大降低了KNN 分类算法的计算量。

实验表明，与传统的KNN 算法进行对比，本文提出的APC-KNN 算法应用于垃圾邮件的过滤，具有高正确率，低误报率等优点；并且能够更好的实现垃圾邮件的过滤，起到了保护电子邮件用户以及节省宽带等效果。

改进的KNN算法过滤系统的构建
将以上这种提升垃圾邮件过滤系统效率的方法应用于前面改进的KNN分类算法中，可以减少其计算量，提高分类速度。

提升后的KNN算法过滤系统可以称为APC-KNN过滤系统。

APC-KNN过滤系统具体流程如下：
Input：电子邮件训练样本和待测电子邮件
Output：待测电子邮件的类别
Step1：对训练样本进行预处理，包括中文分词、选取特征，根据选取的特征项集合重新描述训练样本，对训练集合提取特征；将训练样本表示为向量形式。

Step2：对于垃圾邮件和正常邮件两类进行伪聚类得到m+M个小类，分别计算它们的类中心向量。

Step3：对待测电子邮件进行预处理，根据特征项确定待测电子邮件的向量表示。

Step4：利用公式3.1计算待测电子邮件与所有小类的相似度根据相似度的大小排序，找出与待测电子邮件最相似的K个样本。

其中K值的初始值是人为给定的，并根据实验结果进行调整。

Step5：对这K个样本根据如下公式计算正常邮件和垃圾邮件的类权重：
其中p1=0.8，p2=0.2，k1+k2=K。

如果，则将当前待测电子
邮件判定为正常邮件，否则为垃圾邮件。

过滤系统包括样本的预处理、训练模块和分类模块三个部分，工作流程图如图
基于改进的 k NN 算法的中文网页自动分类方法研究
1 k N N 分类算法
k NN ( k 最近邻) 算法是一种传统的分类算法 ,在文本分类方面得到了广泛的研究和应用. kNN算法实际上是矢量相似度法的一种改进.一般有两种方法计算相似度 :
( 1) 欧氏距离 ,两个标准化的文本向量 a 、 b 之间的欧氏距离为
( 2) 余弦距离 , 计算两个向量的余弦夹角 :
该分类算法的基本思路是 : 在给定新文本后 ,考虑在训练文本集中与该测试文本距离最近 ( 最相似) 的 k 篇文本 , 根据这 k 篇文本所属的类别判定测试文本所属的类别.由于使用 kN N 算法进行分类的过程中 , 要计算测试文本与每个训练文本的相似度 ,这样无疑大大增加了分类的计算量 , 分类的速度无法提高 , 因此 ,在训练文本较多的情况下 ,如何减小计算量 ,提高分类速度是个关键性问题
2.基于改进的 k N N 算法的中文网页自动分类实现
2 . 1 特征提取
在英文文本分类中 ,常用的特征提取的评估函数有文档频数、信息增益、期望交叉熵、互信息、 x2统计、文本证据权和几率比等. 但这些方法用于中文文本的特征提取 , 并没有很高的效率. 这主要有两个方面的原因 : 第一 ,特征提取的计算量太大 ,特征提取效率太低 ,而特征提取的效率直接影响到整个文本分类系统的效率 ; 第二 , 经过特征提取后生成的特征向量维数太高 ,而且不能直接计算出特征向量中各个特征词的权重. 因此 , 在中文文本分类中 ,如何提取特征词以及如何控制特征向量的维数 ,成为了一个亟待解决的难题.本文采取的是基于词性的特征提取方法[ 11 ].这种方法充分考虑了汉语言自身的特性 ,在中文文本中 ,往往是文章中的名词和动词包含了能标识该文本类别的信息. 因此 , 在基于词性的特征提取过程中 ,只提取中文文本中的名词和动词作为文本的一级特征词 ,再根据这些特征词的词频和文本频度计算其权重 , 取权重高的 V 个特征词作为文本的核心特征词. 这种方法不仅很大程度上提高了特征词提取的效率而且有效地降低了特征向量的维数.
2. 2 训练库生成
对于训练库中收集的网页进行以下处理 :
( 1) 定义类别集合 C = { C 1 , …, Ci , …, Cm } ;
( 2 ) 给出训练文档集合 S = { S1 , …, S i , …,S n } , 每个训练文档 S j 被标上所属的类别标识 Ci ;
( 3) 统计 S 中所有文档的特征矢量 V ( S j ) ;
( 4) 根据采取的不同分类算法 , 确定文档 Ci 的特征矢量.。