关 键 词：

数据 挖掘 基于 贝叶斯 算法 KNN

资源描述：

数据挖掘-基于贝叶斯算法及KNN算法的newsgroup18828文档分类器的JAVA实现（上）本分类器的完整工程可以到点击打开链接下载，详细说明的运行方法，用eclipse可以运行，学习数据挖掘的朋友可以跑一下，有问题可以联系我，欢迎交流：） 上文中描述了newsgroup18828文档集的预处理及贝叶斯算法的JAVA实现，下面我们来看看如何实现基于KNN算法的newsgroup文本分类器 1 KNN算法的描述 KNN算法描述如下： STEP ONE:文本向量化表示,由特征词的TF*IDF值计算 STEP TWO:在新文本到达后，根据特征词确定新文本的向量 STEP THREE:在训练文本集中选出与新文本最相似的 K 个文本，相似度用向量夹角余弦度量，计算公式为： 其中，K 值的确定目前没有很好的方法，一般采用先定一个初始值，然后根据实验测试的结果调整 K 值 本项目中K取20 STEP FOUR:在新文本的 K 个邻居中，依次计算每类的权重，每类的权重等于K个邻居中属于该类的训练样本与测试样本的相似度之和。 STEP FIVE:比较类的权重，将文本分到权重最大的那个类别中。 2 文档TF-IDF计算及向量化表示 实现KNN算法首先要实现文档的向量化表示 计算特征词的TF*IDF，每个文档的向量由包含所有特征词的TF*IDF值组成，每一维对应一个特征词 TF及IDF的计算公式如下，分别为特征词的特征项频率和逆文档频率 文档向量计算类 ComputeWordsVector.java如下 1. packagecom.pku.yangliu; 2. importjava.io.BufferedReader; 3. importjava.io.File; 4. importjava.io.FileReader; 5. importjava.io.FileWriter; 6. importjava.io.IOException; 7. importjava.util.SortedMap; 8. importjava.util.Map; 9. importjava.util.Set; 10. importjava.util.TreeMap; 11. importjava.util.Iterator; 12. 13. /**计算文档的属性向量，将所有文档向量化 14. *@authoryangliu 15. *@qq 16. *@mailyang.liu@ 17. * 18. */ 19. publicclassComputeWordsVector{ 20. 21. /**计算文档的TF属性向量,直接写成二维数组遍历形式即可，没必要递归 22. *@paramstrDir处理好的newsgroup文件目录的绝对路径 23. *@paramtrainSamplePercent训练样例集占每个类目的比例 24. *@paramindexOfSample测试样例集的起始的测试样例编号 25. *@paramwordMap属性词典map 26. *@throwsIOException 27. */ 28. publicvoidcomputeTFMultiIDF(StringstrDir,doubletrainSamplePercent,intindexOfSample,MapiDFPerWordMap,MapwordMap)throwsIOException{ 29. FilefileDir=newFile(strDir); 30. Stringword; 31. SortedMapTFPerDocMap=newTreeMap(); 32. //注意可以用两个写文件，一个专门写测试样例，一个专门写训练样例，用sampleType的值来表示 33. StringtrainFileDir="F:/DataMiningSample/docVector/wordTFIDFMapTrainSample"+indexOfSample; 34. StringtestFileDir="F:/DataMiningSample/docVector/wordTFIDFMapTestSample"+indexOfSample; 35. FileWritertsTrainWriter=newFileWriter(newFile(trainFileDir)); 36. FileWritertsTestWrtier=newFileWriter(newFile(testFileDir)); 37. FileWritertsWriter=tsTrainWriter; 38. File[]sampleDir=fileDir.listFiles(); 39. for(inti=0;i=testBeginIndex&&j<=testEndIndex){ 68. tsWriter=tsTestWrtier; 69. } 70. else{ 71. tsWriter=tsTrainWriter; 72. } 73. DoublewordWeight; 74. Set>tempTF=TFPerDocMap.entrySet(); 75. for(Iterator>mt=tempTF.iterator();mt.hasNext();){ 76. Map.Entryme=mt.next(); 77. //wordWeight=(me.getValue()/wordSumPerDoc)*IDFPerWordMap.get(me.getKey()); 78. //这里IDF暂时设为1，具体的计算IDF算法改进和实现见我的博客中关于kmeans聚类的博文 79. wordWeight=(me.getValue()/wordSumPerDoc)*1.0; 80. TFPerDocMap.put(me.getKey(),wordWeight); 81. } 82. tsWriter.append(cateShortName+""); 83. StringkeyWord=fileShortName.substring(0,5); 84. tsWriter.append(keyWord+""); 85. Set>tempTF2=TFPerDocMap.entrySet(); 86. for(Iterator>mt=tempTF2.iterator();mt.hasNext();){ 87. Map.Entryne=mt.next(); 88. tsWriter.append(ne.getKey()+""+ne.getValue()+""); 89. } 90. tsWriter.append("\n"); 91. tsWriter.flush(); 92. } 93. } 94. tsTrainWriter.close(); 95. tsTestWrtier.close(); 96. tsWriter.close(); 97. } 98. 99. /**统计每个词的总的出现次数，返回出现次数大于3次的词汇构成最终的属性词典 100. *@paramstrDir处理好的newsgroup文件目录的绝对路径 101. *@throwsIOException 102. */ 103. publicSortedMapcountWords(StringstrDir,MapwordMap)throwsIOException{ 104. FilesampleFile=newFile(strDir); 105. File[]sample=sampleFile.listFiles(); 106. Stringword; 107. for(inti=0;inewWordMap=newTreeMap(); 127. Set>allWords=wordMap.entrySet(); 128. for(Iterator>it=allWords.iterator();it.hasNext();){ 129. Map.Entryme=it.next(); 130. if(me.getValue()>=1){ 131. newWordMap.put(me.getKey(),me.getValue()); 132. } 133. } 134. returnnewWordMap; 135. } 136. 137. /**打印属性词典 138. *@paramSortedMap属性词典 139. *@throwsIOException 140. */ 141. voidprintWordMap(MapwordMap)throwsIOException{ 142. //TODOAuto-generatedmethodstub 143. System.out.println("printWordMap"); 144. intcountLine=0; 145. FileoutPutFile=newFile("F:/DataMiningSample/docVector/allDicWordCountMap.txt"); 146. FileWriteroutPutFileWriter=newFileWriter(outPutFile); 147. Set>allWords=wordMap.entrySet(); 148. for(Iterator>it=allWords.iterator();it.hasNext();){ 149. Map.Entryme=it.next(); 150. outPutFileWriter.write(me.getKey()+""+me.getValue()+"\n"); 151. countLine++; 152. } 153. System.out.println("WordMapsize"+countLine); 154. } 155. 156. /**计算IDF，即属性词典中每个词在多少个文档中出现过 157. *@paramSortedMap属性词典 158. *@return单词的IDFmap 159. *@throwsIOException 160. */ 161. SortedMapcomputeIDF(Stringstring,MapwordMap)throwsIOException{ 162. //TODOAuto-generatedmethodstub 163. FilefileDir=newFile(string); 164. Stringword; 165. SortedMapIDFPerWordMap=newTreeMap(); 166. Set>wordMapSet=wordMap.entrySet(); 167. for(Iterator>pt=wordMapSet.iterator();pt.hasNext();){ 168. Map.Entrype=pt.next(); 169. DoublecoutDoc=0.0; 170. StringdicWord=pe.getKey(); 171. File[]sampleDir=fileDir.listFiles(); 172. for(inti=0;i>保存测试集和训练集 (2)注意要以"类目_文件名"作为每个文件的key，才能避免同名不同内容的文件出现 (3)注意设置JM参数，否则会出现JAVA heap溢出错误 (4)本程序用向量夹角余弦计算相似度 KNN算法实现类 KNNClassifier.java如下 1. packagecom.pku.yangliu; 2. 3. importjava.io.BufferedReader; 4. importjava.io.File; 5. importjava.io.FileReader; 6. importjava.io.FileWriter; 7. importjava.io.IOException; 8. importjava.util.Comparator; 9. importjava.util.HashMap; 10. importjava.util.Iterator; 11. importjava.util.Map; 12. importjava.util.Set; 13. importjava.util.TreeMap; 14. 15. /**KNN算法的实现类，本程序用向量夹角余弦计算相似度 16. *@authoryangliu 17. *@qq 18. *@mailyang.liu@ 19. * 20. */ 21. 22. publicclassKNNClassifier{ 23. 24. /**用KNN算法对测试文档集分类,读取测试样例和训练样例集 25. *@paramtrainFiles训练样例的所有向量构成的文件 26. *@paramtestFiles测试样例的所有向量构成的文件 27. *@paramkNNResultFileKNN分类结果文件路径 28. *@returndouble分类准确率 29. *@throwsIOException 30. */ 31. privatedoubledoProcess(StringtrainFiles,StringtestFiles, 32. StringkNNResultFile)throwsIOException{ 33. //TODOAuto-generatedmethodstub 34. //首先读取训练样本和测试样本，用map>保存测试集和训练集，注意训练样本的类目信息也得保存， 35. //然后遍历测试样本，对于每一个测试样本去计算它与所有训练样本的相似度，相似度保存入map有 36. //序map中去，然后取前K个样本，针对这k个样本来给它们所属的类目计算权重得分，对属于同一个类目的权重求和进而得到 37. //最大得分的类目，就可以判断测试样例属于该类目下，K值可以反复测试，找到分类准确率最高的那个值 38. //！注意要以"类目_文件名"作为每个文件的key，才能避免同名不同内容的文件出现 39. //！注意设置JM参数，否则会出现JAVAheap溢出错误 40. //！本程序用向量夹角余弦计算相似度 41. FiletrainSamples=newFile(trainFiles); 42. BufferedReadertrainSamplesBR=newBufferedReader(newFileReader(trainSamples)); 43. Stringline; 44. String[]lineSplitBlock; 45. Map>trainFileNameWordTFMap=newTreeMap>(); 46. TreeMaptrainWordTFMap=newTreeMap(); 47. while((line=trainSamplesBR.readLine())!=null){ 48. lineSplitBlock=line.split(""); 49. trainWordTFMap.clear(); 50. for(inti=2;itempMap=newTreeMap(); 54. tempMap.putAll(trainWordTFMap); 55. trainFileNameWordTFMap.put(lineSplitBlock[0]+"_"+lineSplitBlock[1],tempMap); 56. } 57. trainSamplesBR.close(); 58. 59. FiletestSamples=newFile(testFiles); 60. BufferedReadertestSamplesBR=newBufferedReader(newFileReader(testSamples)); 61. Map>testFileNameWordTFMap=newTreeMap>(); 62. MaptestClassifyCateMap=newTreeMap();//分类形成的<文件名，类目>对 63. MaptestWordTFMap=newTreeMap(); 64. while((line=testSamplesBR.readLine())!=null){ 65. lineSplitBlock=line.split(""); 66. testWordTFMap.clear(); 67. for(inti=2;itempMap=newTreeMap(); 71. tempMap.putAll(testWordTFMap); 72. testFileNameWordTFMap.put(lineSplitBlock[0]+"_"+lineSplitBlock[1],tempMap); 73. } 74. testSamplesBR.close(); 75. //下面遍历每一个测试样例计算与所有训练样本的距离，做分类 76. StringclassifyResult; 77. FileWritertestYangliuWriter=newFileWriter(newFile("F:/DataMiningSample/docVector/yangliuTest")); 78. FileWriterKNNClassifyResWriter=newFileWriter(kNNResultFile); 79. Set>>testFileNameWordTFMapSet=testFileNameWordTFMap.entrySet(); 80. for(Iterator>>it=testFileNameWordTFMapSet.iterator();it.hasNext();){ 81. Map.Entry>me=it.next(); 82. classifyResult=KNNComputeCate(me.getKey(),me.getValue(),trainFileNameWordTFMap,testYangliuWriter); 83. KNNClassifyResWriter.append(me.getKey()+""+classifyResult+"\n"); 84. KNNClassifyResWriter.flush(); 85. testClassifyCateMap.put(me.getKey(),classifyResult); 86. } 87. KNNClassifyResWriter.close(); 88. //计算分类的准确率 89. doublerighteCount=0; 90. Set>testClassifyCateMapSet=testClassifyCateMap.entrySet(); 91. for(Iterator>it=testClassifyCateMapSet.iterator();it.hasNext();){ 92. Map.Entryme=it.next(); 93. StringrightCate=me.getKey().split("_")[0]; 94. if(me.getValue().equals(rightCate)){ 95. righteCount++; 96. } 97. } 98. testYangliuWriter.close(); 99. returnrighteCount/testClassifyCateMap.size(); 100. } 101. 102. /**对于每一个测试样本去计算它与所有训练样本的向量夹角余弦相似度 103. *相似度保存入map有序map中去，然后取前K个样本， 104. *针对这k个样本来给它们所属的类目计算权重得分，对属于同一个类 105. *目的权重求和进而得到最大得分的类目，就可以判断测试样例属于该 106. *类目下。K值可以反复测试，找到分类准确率最高的那个值 107. *@paramtestWordTFMap当前测试文件的<单词,词频>向量 108. *@paramtrainFileNameWordTFMap训练样本<类目_文件名,向量>Map 109. *@paramtestYangliuWriter 110. *@returnStringK个邻居权重得分最大的类目 111. *@throwsIOException 112. */ 113. privateStringKNNComputeCate( 114. StringtestFileName, 115. MaptestWordTFMap, 116. Map>trainFileNameWordTFMap,FileWritertestYangliuWriter)throwsIOException{ 117. //TODOAuto-generatedmethodstub 118. HashMapsimMap=newHashMap();//<类目_文件名,距离>后面需要将该HashMap按照value排序 119. doublesimilarity; 120. Set>>trainFileNameWordTFMapSet=trainFileNameWordTFMap.entrySet(); 121. for(Iterator>>it=trainFileNameWordTFMapSet.iterator();it.hasNext();){ 122. Map.Entry>me=it.next(); 123. similarity=computeSim(testWordTFMap,me.getValue()); 124. simMap.put(me.getKey(),similarity); 125. } 126. //下面对simMap按照value排序 127. ByValueComparatorbvc=newByValueComparator(simMap); 128. TreeMapsortedSimMap=newTreeMap(bvc); 129. sortedSimMap.putAll(simMap); 130. 131. //在disMap中取前K个最近的训练样本对其类别计算距离之和，K的值通过反复试验而得 132. MapcateSimMap=newTreeMap();//K个最近训练样本所属类目的距离之和 133. doubleK=20; 134. doublecount=0; 135. doubletempSim; 136. 137. Set>simMapSet=sortedSimMap.entrySet(); 138. for(Iterator>it=simMapSet.iterator();it.hasNext();){ 139. Map.Entryme=it.next(); 140. count++; 141. StringcategoryName=me.getKey().split("_")[0]; 142. if(cateSimMap.containsKey(categoryName)){ 143. tempSim=cateSimMap.get(categoryName); 144. cateSimMap.put(categoryName,tempSim+me.getValue()); 145. } 146. elsecateSimMap.put(categoryName,me.getValue()); 147. if(count>K)break; 148. } 149. //下面到cateSimMap里面把sim最大的那个类目名称找出来 150. //testYangliuWriter.flush(); 151. //testYangliuWriter.close(); 152. doublemaxSim=0; 153. StringbestCate=null; 154. Set>cateSimMapSet=cateSimMap.entrySet(); 155. for(Iterator>it=cateSimMapSet.iterator();it.hasNext();){ 156. Map.Entryme=it.next(); 157. if(me.getValue()>maxSim){ 158. bestCate=me.getKey(); 159. maxSim=me.getValue(); 160. } 161. } 162. returnbestCate; 163. } 164. 165. /**计算测试样本向量和训练样本向量的相似度 166. *@paramtestWordTFMap当前测试文件的<单词,词频>向量 167. *@paramtrainWordTFMap当前训练样本<单词,词频>向量 168. *@returnDouble向量之间的相似度以向量夹角余弦计算 169. *@throwsIOExcepti

内容简介：

-