数据挖掘之分类（kNN算法的描述及使用）
/**
*作者：张荣华
*日期：2008-2-23
**/
数据挖掘之分类系列文章
之前说到分类的基本概念以及一个文本分类的实例，原文地址见：http://www.iteye.com/topic/163285 现在我们就来改造之前的分类算法，本文主要介绍KNN算法在文本分类器中的使用。
kNN算法简介：
kNN(k Nearest Neighbors)算法又叫k最临近方法， 总体来说kNN算法是相对比较容易理解的算法之一，假设每一个类包含多个样本数据，而且每个数据都有一个唯一的类标记表示这些样本是属于哪一个分类， kNN就是计算每个样本数据到待分类数据的距离，取和待分类数据最近的k各样本数据，那么这个k个样本数据中哪个类别的样本数据占多数，则待分类数据就属于该类别。
基于kNN算法的思想，我们必须找出使用该算法的突破点，本文的目的是使用kNN算法对文本进行分类，那么和之前的文章一样，关键还是项向量的比较问题，之前的文章中的分类代码仅使用的反余弦来匹配项向量，找到关键的“距离”，那么我们可以试想反余弦之后使用kNN的结果如何。
补充上一篇文章中没有详细讲解的反余弦匹配问题：
Lucene中有一个term vectors这个东东，它表示该词汇单元在文档中出现的次数，比如说这里有两篇文章，这两篇文章中都有hibernate和spring这两个单词，在第一篇文章中hibernate出现了10次，spring出现了20次，第二篇文章中hibernate出现15次，spring出现10次，那么对第一篇文章来说有两个项向量，分别是hibernate:10,spring:20，第二篇文章类似，hibernate:15,spring:10。然后我们就可以在二维空间的x，y组上表示出来，如图：
这样看来我们其实是要得到两者之间的夹角，计算两个向量之间夹角的公式为A*B/||A||*||B||。按照这个原理我们就可以得到新文章和样本文章之间的距离，代码如下，这个份代码在第一篇文章提供的代码下载中。
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);}protected Map<String, List<MatchCondition>> analyse(Map<String, Map<String, Integer>> articleVectorMap, Map<String, Map<String, Integer>> categoryVectorMap) {Map<String, List<MatchCondition>> result = new HashMap<String, List<MatchCondition>>();for (Entry<String, Map<String, Integer>> categoryEntry : categoryVectorMap.entrySet()) {for (Entry<String, Map<String, Integer>> itemEntry : articleVectorMap.entrySet()) {double acos = caculateVector(itemEntry.getValue(), filterVectorMap(categoryEntry.getValue()));if (acos < vectorGene) {if (result.get(itemEntry.getKey()) != null) {List<MatchCondition> list = result.get(itemEntry.getKey());if (list.size() < kNum) {list.add(new MatchCondition(itemEntry.getKey(), categoryEntry.getKey(), acos));} else {if (list.size() == kNum) {Collections.sort(list, new MatchConditionComparator());}int n = 0;for (MatchCondition condition : list) {if (acos < condition.getAcos()) {list.set(n, new MatchCondition(itemEntry.getKey(), categoryEntry.getKey(), acos));}n++;}}} else {List<MatchCondition> list = new LinkedList<MatchCondition>();list.add(new MatchCondition(itemEntry.getKey(), categoryEntry.getKey(), acos));result.put(itemEntry.getKey(), list);}}}}return result;}