数据挖掘文本分类器.ppt

文本分类器 主要内容 Newsgroup文本预处理 朴素贝叶斯 KNN 算法对比评价 5 2 3 4 分类器实现概述 1 分类器实现概述 对newsgroup文档集进行预处理 提取出30095个特征词计算每篇文档中的特征词的TF IDF值 实现文档向量化 在KNN算法中使用用JAVA实现了KNN算法及朴素贝叶斯算法的newsgroup文本分类器作为学习拓展 用C 实现了决策树ID3算法 采用了课件上的训练数据 Newsgroup文档预处理 文档预处理类DataPreProcess javaSTEPONE 英文词法分析 去除数字 连字符 标点符号 特殊字符 所有大写字母转换成小写 可以用正则表达式Stringres line split a zA Z STEPTWO 去停用词 过滤对分类无价值的词STEPTHRE 词根还原stemming 基于Porter算法 Newsgroup文档预处理 特征词的提取首先统计在所有文档中出现不重复的单词一共有87554个 对这些词进行统计发现 出现次数大于等于1次的词有87554个出现次数大于等于2次的词有49352个出现次数大于等于3次的词有36456个出现次数大于等于4次的词有30095个策略一 保留所有词作为特征词共计87554个策略二 选取出现次数大于等于4次的词作为特征词共计30095个 特征词的选取策略 采用策略一 后面将对两种特征词选取策略的计算时间和平均准确率做对比 朴素贝叶斯算法描述 伯努利模型 Bernoullimodel 以文件为粒度类条件概率P tk c 类c下包含单词tk的文件数 1 类c下单词总数 2 先验概率P c 类c下文件总数 整个训练样本的文件总数本分类器选用多项式模型计算根据 IntroductiontoInformationRetrieval 多项式模型计算准确率更高 朴素贝叶斯分类器有两种模型 多项式模型 multinomialmodel 以单词为粒度类条件概率P tk c 类c下单词tk在各个文档中出现过的次数之和 1 类c下单词总数 训练样本中不重复特征词总数 先验概率P c 类c下的单词总数 整个训练样本的单词总数 朴素贝叶斯算法实现 贝叶斯算法类NaiveBayesianClassifier java测试集与训练集创建类CreateTrainAndTestSample java计算概率用到了BigDecimal类实现任意精度计算用交叉验证法做十次分类实验 对准确率取平均值根据正确类目文件和分类结果文计算混淆矩阵并且输出MapcateWordsProbkey为 类目 单词 value为该类目下该单词的出现次数 避免重复计算 朴素贝叶斯算法分类结果 为方便计算混淆矩阵 将类目编号0alt atheism1comp graphics2comp os ms windows misc3comp sys ibm pc hdwar4comp sys mac hardwar5comp windows x6misc forsale7rec autos8rec motorcycles9rec sport baseball 10rec sport hockey11sci crypt12sci electronics13sci med14sci space15soc religion christian16talk politics guns17talk politics mideast18talk politics misc19talk religion misc 朴素贝叶斯算法分类结果 贝叶斯算法分类结果 混淆矩阵表示 朴素贝叶斯算法分类结果 贝叶斯算法分类结果硬件环境 IntelCore2DuoCPUT57502GHZ 2G内存实验结果取所有词共87554个作为特征词 10次交叉验证实验平均准确率78 19 用时23min 准确率范围75 65 80 47 第6次实验准确率超过80 取出现次数大于等于4次的词共计30095个作为特征词 10次交叉验证实验平均准确率77 91 用时22min 准确率范围75 51 80 26 第6次实验准确率超过80 朴素贝叶斯算法分类结果 结论 朴素贝叶斯算法不必去除出现次数很低的词 因为出现次数很低的词的IDF比较大 去除后分类准确率下降 而计算时间并没有显著减少 朴素贝叶斯 实验编号 准确率 KNN算法描述 KNN算法描述如下 STEPONE 文本向量化表示 由特征词的TF IDF值计算STEPTWO 在新文本到达后 根据特征词确定新文本的向量STEPTHREE 在训练文本集中选出与新文本最相似的K个文本 相似度用向量夹角余弦度量 计算公式为 其中 K值的确定目前没有很好的方法 一般采用先定一个初始值 然后根据实验测试的结果调整K值本项目中K取20 KNN算法描述 KNN算法描述如下 STEPFOUR 在新文本的K个邻居中 依次计算每类的权重 每类的权重等于K个邻居中属于该类的训练样本与测试样本的相似度之和 STEPFIVE 比较类的权重 将文本分到权重最大的那个类别中 KNN算法 文档向量计算 实现KNN算法首先要实现文档的向量化表示计算特征词的TF IDF 每个文档的向量由包含所有特征词的TF IDF值组成 每一维对应一个特征词 TF及IDF分别为特征词的特征项频率和逆文档频率 KNN算法 文档向量计算 文档向量计算类ComputeWordsVector java 计算IDF非常耗时 3万多个词的属性词典初步估计需要25个小时可以先尝试所有词的IDF都设成1的情况 KNN算法实现 用TreeMap 保存测试集和训练集注意要以 类目 文件名 作为每个文件的key 才能避免同名不同内容的文件出现注意设置JM参数 否则会出现JAVAheap溢出错误本程序用向量夹角余弦计算相似度 KNN算法实现类KNNClassifier java KNN算法分类结果 KNN算法分类结果 混淆矩阵表示 KNN算法分类结果 KNN算法分类结果硬件环境 IntelCore2DuoCPUT57502GHZ 2G内存相同硬件环境计算和贝叶斯算法做对比 实验结果取出现次数大于等于4次的词共计30095个作为特征词 10次交叉验证实验平均准确率78 19 用时1h55min 10词实验准确率范围73 62 82 10 其中有3次实验准确率超过80 KNN算法分类结果 准确率 实验编号 KNN 算法对比与评价 朴素贝叶斯与KNN分类准确率对比取出现次数大于等于4次的词共计30095个作为特征词 做10次交叉验证实验 朴素贝叶斯和KNN算法对Newsgroup文档分类结果对比 朴素贝叶斯 KNN 实验编号 准确率 算法对比与评价 结论分类准确率上 KNN算法更优分类速度上 朴素贝叶斯算法更优 决策树算法ID3的C 实现 作为学习拓展 还用C 实现了决策树ID3算法采用的训练数据是第2讲上的数据 记录了在不同气候条件下是否