改进KNN算法描述及实现
前记

????随着文本信息量的快速增长, 文本分类己成为信息检索、知识挖掘和管理等领域的关键技术。文本分类的精确程度取决于特征提取的科学性和分类算法的科学性。现有的文本分类方法主要有支持向量机(SVM)、k 最近邻(KNN)、决策树、线性最小二乘法估计(LLSF)和贝叶斯分类算法(Bayes)等。KNN 算法是 VSM(向量空间模型)下最好的分类算法之一。

1. 何为KNN？

????以下是引用wiki的一个定义：

??? k-nearest neighbors algorithm (k-NN) is a method for classifying objects based on closest training examples in the feature space. k-NN is a type of instance-based learning, or lazy learning where the function is only approximated locally and all computation is deferred until classification. The k-nearest neighbor algorithm is amongst the simplest of all machine learning algorithms: an object is classified by a majority vote of its neighbors, with the object being assigned to the class most common amongst its k nearest neighbors (k is a positive integer, typically small). If k = 1, then the object is simply assigned to the class of its nearest neighbor.

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

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

2. KNN算法的决策过程

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

?

?3. 存在的不足

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

4. 改进的KNN算法

a. 快速KNN算法。FKNN：http://www.docin.com/p-9581757.html **（实际应用中结合lucene）**

b. 加权欧氏距离公式。在传统的欧氏距离中,各特征的权重相同,也就是认定各个特征对于分类的贡献是相同的,显然这是不符合实际情况的。同等的权重使得特征向量之间相似度计算不够准确, 进而影响分类精度。加权欧氏距离公式,特征权重通过灵敏度方法获得**。（根据业务需求调整，例如关键字加权、词性加权等）**

5. 算法的实现

以下实现语料库基于搜狗文本分类语料库：http://www.sogou.com/labs/dl/c.html

a. 传统knn实现。主要分为训练和计算两个步骤，以下是代码片段：
??? 1. 训练文本，构建语料库。

???? (1)训练指定文件夹中的语料 － 》? (2)读取单个文件，构建语料库 －》?(3)对文本进行分词（基于中科院分词器），构建 词组 向量模型? －》重复(2)(3)

Trainer.java

???public static List<StuffCell> cellList = new ArrayList<StuffCell>();
??
????public void start() {
????????logger.debug("训练ing...");
???????????
????????STUFF_SERIES_NUM = KnnConstants.KNN_STUFF_LIST.length;
????????StufSeriess = KnnConstants.KNN_STUFF_LIST;
???????????
????????/*
?????????* 构建单元语料队列
?????????*/
????????for(int i = 0; i < STUFF_SERIES_NUM; ++i) {
????????????buildStuffListByFile(StufSeriess[i].getId(), StufSeriess[i].getPath());
????????}
??
????????logger.debug("训练ed...");
????}
.....
????/**
?????* 方法说明：训练指定文件夹中的语料
?????*
?????* @param seriesid
?????* 语料类型ID
?????* @param filepath
?????* 语料路径
?????* @return
?????* boolean
?????* @author fisher
?????*/
????public static boolean buildStuffListByFile(String seriesid, String filepath) {
????????File file = new File(filepath);
????????if (file == null || !file.isDirectory()) {
????????????return false;
????????} else {
????????????/**
?????????????* 读取文件，构建语料库
?????????????*/
????????????String[] filelist = file.list();
????????????for (int i = 0; i < filelist.length; i++) {
????????????????File readfile = new File(filepath + KnnConstants.FileSeparator + filelist[i]);
????????????????if (!readfile.isDirectory()) {
????????????????????StuffCell stuffCell = new StuffCell();
????????????????????stuffCell.setCellid(i);
????????????????????stuffCell.setSeriesid(seriesid);
????????????????????String content = FileUtil.read(readfile.getPath(), "GBK");
????????????????????/*
?????????????????????* 对文本进行分词（基于中科院分词器），构建 词组 向量模型
?????????????????????*/
????????????????????TermVector[] termVectors = TermVector.buildTV(content);
????????????????????//stuffCell.setContent(content);

??
????????????????????stuffCell.setTermVectors(termVectors);
????????????????????cellList.add(stuffCell);
????????????????}
????????????}
????????}
????????return true;
????}


BwKNN.java

(1)获取 最近 N篇语料 －》(2)计算 得出 分类


????public String getClassification(String text) {
????????/*
?????????* 获取 最近 N篇语料
?????????*/
????????StuffCell[] nearest = getNearest(Trainer.cellList, text, KnnConstants.KNN_NEIGHBORS);
????????if(nearest == null)
????????????return null;
????????/*
?????????* 去重，重复的类目加1
?????????*/
????????Map<String, Integer> seriesMap = new HashMap<String, Integer>();
????????for(int i = 0; i < nearest.length; ++i) {
????????????if(seriesMap.containsKey(nearest[i].getSeriesid())) {
????????????????int num = seriesMap.get(nearest[i].getSeriesid());
????????????????seriesMap.put(nearest[i].getSeriesid(), num + 1);
????????????} else {
????????????????seriesMap.put(nearest[i].getSeriesid(), 1);
????????????}
????????}
????????/*
?????????* 类目数量倒排序，获取类目数量最多的数据
?????????*/
????????Map.Entry[] mes = StuffCell.getSortedHashtableByValue(seriesMap);
????????String seriesid = (String) mes[0].getKey();
????????return seriesid;
????}

b. 改进的KNN算法实现

1. 利用lucene对所有语料库建立索引

public void start() {
????????IndexFiles indexFiles = new IndexFiles();
????????indexFiles.indexDocs(new File("D:/Reduced/index"), new File("D:/Reduced/C000008"), "C000008");
????????indexFiles.indexDocs(new File("D:/Reduced/index"), new File("D:/Reduced/C000010"), "C000010");
????????indexFiles.indexDocs(new File("D:/Reduced/index"), new File("D:/Reduced/C000013"), "C000013");
????????indexFiles.indexDocs(new File("D:/Reduced/index"), new File("D:/Reduced/C000014"), "C000014");
????????indexFiles.indexDocs(new File("D:/Reduced/index"), new File("D:/Reduced/C000016"), "C000016");
????????indexFiles.indexDocs(new File("D:/Reduced/index"), new File("D:/Reduced/C000020"), "C000020");
????????indexFiles.indexDocs(new File("D:/Reduced/index"), new File("D:/Reduced/C000022"), "C000022");
????????indexFiles.indexDocs(new File("D:/Reduced/index"), new File("D:/Reduced/C000023"), "C000023");
????????indexFiles.indexDocs(new File("D:/Reduced/index"), new File("D:/Reduced/C000024"), "C000024");
????}

2. 改进lucene search score机制

??????? /*
?????????* 词性加权。存进payload
?????????*/
????????String payloadText = "";
????????if (needPOSTagged && !StringUtils.isEmpty(lexeme.getPartOfSpeech()))
????????????payloadText = lexeme.getPartOfSpeech();
??
????????/*
?????????* 关键字或者术语加权，存进payload
?????????*/
????????float keyweight = gmccKeyWordDeal.doDeal(lexeme.getText());
????????if(keyweight > 0)
????????????payloadText = payloadText + "_" + keyweight;


??????????? /*
?????????????* 利用lucene search score最大的前N篇语料
?????????????*/
????????????documents = searchManege.search(KnnConstants.INDEX, KnnConstants.FIELD,
????????????????????text, knn_neighbors, Occur.SHOULD, Occur.SHOULD);

????????/*
?????????* 类目数量倒排序，获取类目数量最多的数据
?????????*/
????????Map.Entry[] mes = StuffCell.getSortedHashtableByValue(seriesMap);

?6. 测试案例

待续

7. 后感

??? 文本分类的进一步改进不在算法方面，应该立足于影响文本分类最底层、最根本的因素：文本表示中的特征项，提高特征项的完整独立程度。关键短语是具有强文本表示功能的特征短语，在表示文本时，能将文本的内容特征（如主题类别）鲜明地表示出来。关键短语具有结构稳定、语义完整和强统计意义的特点，能克服向量空间模型和其他算法的缺点，更适合作为文本表示的特征，有利于提高文本分类的效果。