数据挖掘文本分类器.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,文本分类器,主要内容,Newsgroup,文本预处理,朴素贝叶斯,KNN,算法对比评价,5,2,3,4,分类器实现概述,1,分类器实现概述,对,newsgroup,文档集进行预处理，提取出,30095,个特征词,计算每篇文档中的特征词的,TF*IDF,值，实现文档向量化，在,KNN,算法中使用,用,JAVA,实现了,KNN,算法及朴素贝叶斯算法的,newsgroup,文本分类器,作为学习拓展，用,C+,实现了决策树,ID3,算法，采用了课件上的训练数据,Newsgroup,文档预处理,文档预处理类,DataPreProcess.java,STEP ONE:,英文词法分析，去除数字、连字符、标点符号、特殊,字符，所有大写字母转换成小写，可以用正则表达式,String res=line.split(a-zA-Z);,STEP TWO:,去停用词，过滤对分类无价值的词,STEP THRE:,词根还原,stemming,基于,Porter,算法,Newsgroup,文档预处理,特征词的提取,首先统计在所有文档中出现不重复的单词一共有,87554,个，对这些词进行统计发现：,出现次数大于等于,1,次的词有,87554,个,出现次数大于等于,2,次的词有,49352,个,出现次数大于等于,3,次的词有,36456,个,出现次数大于等于,4,次的词有,30095,个,策略一：保留所有词作为特征词 共计,87554,个,策略二：选取出现次数大于等于,4,次的词作为特征词共计,30095,个,特征词的选取策略：,采用策略一,后面将对两种特征词选取策略的计算时间和平均准确率做对比,朴素贝叶斯算法描述,伯努利模型（,Bernoulli model,）,以文件为粒度,类条件概率,P(t,k,|c)=,（类,c,下包含单词,t,k,的文件数,+1,）,/(,类,c,下单词总数,+2),先验概率,P(c)=,类,c,下文件总数,/,整个训练样本的文件总数,本分类器选用多项式模型计算,根据,Introduction to Information Retrieval,，多项式模型计算准确率更高,朴素贝叶斯分类器有两种模型,多项式模型,(multinomial model),以单词为粒度,类条件概率,P(t,k,|c)=(,类,c,下单词,t,k,在各个文档中出现过的次数之和,+1)/,（类,c,下单词总数,+,训练样本中不重复特征词总数）,先验概率,P(c)=,类,c,下的单词总数,/,整个训练样本的单词总数,朴素贝叶斯算法实现,贝叶斯算法类,NaiveBayesianClassifier.java,测试集与训练集创建类,CreateTrainAndTestSample.java,计算概率用到了,BigDecimal,类实现任意精度计算,用交叉验证法做十次分类实验，对准确率取平均值,根据正确类目文件和分类结果文计算混淆矩阵并且输出,Map cateWordsProb key,为,“,类目,_,单词,”,value,为该类目下该单词的出现次数，避免重复计算,朴素贝叶斯算法分类结果,为方便计算混淆矩阵，将类目编号,0 alt.atheism,1 comp.graphics,2 comp.os.ms-windows.misc,3comp.sys.ibm.pc.hdwar,4comp.sys.mac.hardwar,5 comp.windows.x,6 misc.forsale,7 rec.autos,8 rec.motorcycles,9 rec.sport.baseball,10 rec.sport.hockey,11 sci.crypt,12 sci.electronics,13 sci.med,14 sci.space,15 soc.religion.christian,16 talk.politics.guns,17 talk.politics.mideast,18 talk.politics.misc,19 talk.religion.misc,朴素贝叶斯算法分类结果,贝叶斯算法分类结果,-,混淆矩阵表示,朴素贝叶斯算法分类结果,贝叶斯算法分类结果,硬件环境：,Intel Core 2 Duo CPU T5750 2GHZ,2G,内存,实验结果,取所有词共,87554,个作为特征词：,10,次交叉验证实验平均准确率,78.19%,，用时,23min,准确率范围,75.65%-80.47%,，第,6,次实验准确率超过,80%,取出现次数大于等于,4,次的词共计,30095,个作为特征词：,10,次交叉验证实验平均准确率,77.91%,，用时,22min,，准确率范围,75.51%-80.26%,，第,6,次实验准确率超过,80%,朴素贝叶斯算法分类结果,实验编号,0,1,2,3,4,5,6,7,8,9,平均,准确率（,%,）,75.51,75.93,79.48,79.30,75.51,77.57,80.26,79.54,78.75,77.25,77.91,结论：,朴素贝叶斯算法不必去除出现次数很低的词，因为出现次数很低的词的,IDF,比较 大，去除后分类准确率下降，而计算时间并没有显著减少,朴素贝叶斯,实验编号,准确率（,%,）,KNN,算法描述,KNN,算法描述如下：,STEP ONE:,文本向量化表示,由特征词的,TF*IDF,值计算,STEP TWO:,在新文本到达后，根据特征词确定新文本的向量,STEP THREE:,在训练文本集中选出与新文本最相似的,K,个文本，相似度用向量夹角余弦度量，计算公式为：,其中，,K,值的确定目前没有很好的方法，一般采用先定一个初始值，然后根据实验测试的结果调整,K,值,本项目中,K,取,20,KNN,算法描述,KNN,算法描述如下：,STEP FOUR:,在新文本的,K,个邻居中，依次计算每类的权重，每类的权重等于,K,个邻居中属于该类的训练样本与测试样本的相似度之和。,STEP FIVE:,比较类的权重，将文本分到权重最大的那个类别中。,KNN,算法,-,文档向量计算,实现,KNN,算法首先要实现文档的向量化表示,计算特征词的,TF*IDF,，每个文档的向量由包含所有特征词的,TF*IDF,值组成，每一维对应一个特征词,TF,及,IDF,分别为特征词的特征项频率和逆文档频率,KNN,算法,-,文档向量计算,文档向量计算类,ComputeWordsVector.java,计算,IDF,非常耗时，,3,万多个词的属性词典初步估计需要,25,个小时,可以先尝试所有词的,IDF,都设成,1,的情况,KNN,算法实现,用,TreeMap,保存测试集和训练集,注意要以,类目,_,文件名,作为每个文件的,key,，才能避免同名不同内容的文件出现,注意设置,JM,参数，否则会出现,JAVA heap,溢出错误,本程序用向量夹角余弦计算相似度,KNN,算法实现类,KNNClassifier,.java,KNN,算法分类结果,KNN,算法分类结果,-,混淆矩阵表示,KNN,算法分类结果,KNN,算法分类结果,硬件环境：,Intel Core 2 Duo CPU T5750 2GHZ,2G,内存,相同硬件环境计算和贝叶斯算法做对比,实验编号,0,1,2,3,4,5,6,7,8,9,平均,准确率（,%,）,73.62,78.67,79.97,78.93,79.43,79.61,82.10,80.79,80.16,75.81,78.19,实验结果,取出现次数大于等于,4,次的词共计,30095,个作为特征词：,10,次交叉验证实验平均准确率,78.19%,，用时,1h55min,，,10,词实验准确率范围,73.62%-82.10%,，其中有,3,次实验准确率超过,80%,KNN,算法分类结果,准确率（,%,）,实验编号,KNN,算法对比与评价,朴素贝叶斯与,KNN,分类准确率对比,取出现次数大于等于,4,次的词共计,30095,个作为特征词，做,10,次交叉验证实验，朴素贝叶斯和,KNN,算法对,Newsgroup,文档分类结果对比,：,朴素贝叶斯,KNN,实验编号,准确率（,%,）,算法对比与评价,实验编号,0,1,2,3,4,5,6,7,8,9,平均,NB,（,%,）,75.51,75.93,79.48,79.30,75.51,77.57,80.26,79.54,78.75,77.25,77.91,KNN,（,%,）,73.62,78.67,79.97,78.93,79.43,79.61,82.10,80.79,80.16,75.81,78.19,结论,分类准确率上，,KNN,算法更优,分类速度上，朴素贝叶斯算法更优,决策树算法,ID3,的,C+,实现,作为学习拓展，还用,C+,实现了决策树,ID3,算法,采用的训练数据是第,2,讲上的数据，记录了在不同气候条件下是否去打球的情况，程序根据该表输出决策树,输入数据如下,决策树算法,ID3,的,C+,实现,生成决策树按照树形输出如下图所示多叉树的实现有很多方法，本算法采用每个结点的所有孩子用,vector,保存比较合适。注意维护剩余样例和剩余属性信息，建树时横向遍历靠循环属性的值，纵向遍历靠递归调用，总体是,DFS,QA&Thanks,