NAVIGATING TO TEXT CATEGORIZATION 文本分类初探文本分类初探作者：领头驴作者：领头驴ROADOFMAP特征词选择算法基础知识几种特征词选择算法效果验证文本分类以及预处理代码实现程序调用文本分类基础知识文本分类基础知识分类问题(CATEGORIZATION)的两种模式广义分类问题的两种定义监督学习（SupervisedLearning）非监督学习(UnsupervisedLeaning)区别：是否对于类别标签(classlabel)有先验知识监督学习（狭义上的分类）：事先知道类别标签非监督学习（狭义上的聚类）：事先不知道类别标签本次汇报专题集中于：狭义上的分类（后面统称为文本分类）返回文档模型（一）Bagofwordsorbowl(词袋模型或者碗模型)思想：词与词之间的概率分布条件独立条件独立（在给定类别后每个词的概率分布与其他词无关）单词生成的概率与它在文档中的位置无关每篇文档看作是一“袋子”的词应用举例：朴素贝叶斯模型文档模型（二）VectorSpaceModelVSM（文档向量模型）思想：利用向量空间模型进行文本分类的主要思路基于邻近假设邻近假设：同一类文档在N维向量空间中会构成一个邻近区域，而不同类的邻近区域之间是互不重叠的该模型将每个文档看成是一个N维向量应用：KNN，LR,SVM两种文档模型的对比相同点：从词的粒度上来讲，都没有考虑词语概率分布与其他词语概率分布之间的相关性（即：都做了独立性假设）生成文档模型的时候，都没有考虑到词在文档中出现的位置等因素不同点：可以理解为“权重”计算方式和表示方式不同词袋模型的“权重”用概率表示，最后求出由词生成文档的概率；VSM模型的“权重”，可以看做是tf,df的函数映射分类器的划分(一)Generativeclassifier(产生式模型or生成式模型)Generativeclassifierlearnamodelofjointprobabilityp(x,y),oftheinputsxandthelabely,andmaketheirpredictionsbyusingBayesrulestocalculatep(y|x),andthenpickingthemostlikelylabelyDiscriminativeclassifier（判别式模型）Discriminativeclassifiermodeltheposteriorp(y|x)directly,orlearnadirectmapfrominputsstotheclasslabels分类器的划分（二）仁者见仁，智者见智Vapnik:Oneshouldsolvetheclassificationproblemdirectly,andneversolveamoregeneralproblemasanintermediatestepsuchasmodelingp(x|y)NgAndrew$Jordan:discriminativeclassifier比generativeclassifier有更低的渐进错误率，但是generativeclassifier能更快地收敛到最低错误；随着样本数目的增多，discriminativeclassifer的performance会overtakegenerativeclassifier分类器的划分（三）几种常见的产生式模型GaussiandistributionGaussianmixturemodelMultinomialdistributionHiddenMarkovmodelNaiveBayesAODELatentDirichletallocation几种常见的判别式模型LineardiscriminantanalysisSupportvectormachinesBoostingConditionalrandomfieldsLogisticregressionNeuralNetworks分类器的划分与文档模型划分之间的关系（个人经验）VSM模型：一般用在判别式分类模型中，如LR（对数回归），SVM（支持向量机）词袋子模型：一般用在生成式分类模型中，如朴素贝叶斯词袋子模型也可以用在判别式模型中模型的参数估计：EM算法（missingdatalikelihood）特征词选择算法（一）回顾文本分类的两种模式有监督特征词选择算法：特点：依赖于类别信息具体方法有：信息增益（IG），卡方(Chisquare),互信息（pointwiseMI）,相对熵（KLDivergence）无监督特征词选择算法：特点：不依赖于类别信息具体方法有：文档频率法（DF），单词贡献度（TC）特征词选择算法（二）-无监督算法DF：它指在整个数据集中有多少个文本包含这个单词单词贡献度：它认为一个单纯的重要性取决于它对整个文本数据集相似性的贡献程度特征词选择算法（三）基于信息论的方法事件的互信息集合的平均互信息特征词选择算法（四）基于信息论的方法Point-wisemi基本思想：计算每个词t,与类别c之间的互信息运算公式：存在问题：倾向于选择稀疏词（先给出结论，稍后会有实验结果展示）特征词选择算法（五）基于信息论的方法InformationGain(IG,信息增益熵，平均互信息)基本思想：将单词和类别出现的情况看做是事件集合，然后求上述两个事件集合的平均互信息运算公式：存在问题：计算过程中考虑到了既不包含termt，也不属于类别c的文档的概率计算，可能会引进误差特征词选择算法（六）基于信息论的方法KLDivergence基本思想：交叉熵反映了文本类别的概率分布和在出现了某个特定词的条件下文本类别的概率分布之间的距离,特征词t的交叉熵越大,对文本类别分布的影响也越大。熵的特征选择效果都要优于信息增益（尚未验证）。运算公式：D（p/q）=sum(p(x)*log(p(x)/q(x)。其中p(x)和q(x)为两个概率分布约定0*log(0/q(x)=0;p(x)*log(p(x)/0)=infinity;存在问题：如果文本类别数目较少，每类文本的数目又非常大时，KL值的区分度可能会不明显（个人认为这种特征词选择方法效率同MI）特征词选择算法（七）基于统计学的方法Chi-squaredistribution基本思想卡方统计量常常用于检测两个事件的独立性，在特征词选择中，两个事件分别指词项的出现和类别的出现。运算公式存在问题同IG法几种特征词选择算法效果验证几种特征词选择算法效果验证训练语料库测试语料库情况说明共有文化、历史、读书、社会与法制、娱乐，军事等六个类别（其中文化，历史，读书，军事来自凤凰新闻，社会与法制来自腾讯和新浪，娱乐类新闻来自网易）。训练语料库中每个类别1000篇文章，共有6000篇文章，测试语料库中每个类别有100篇文章，共有600篇文章。DF、卡方、点对点互信息、信息增益法提取特征词对比（一）DF、卡方、点对点互信息、信息增益法提取特征词对比（三）一般结论：CHI,IG,和DF的性能明显优于MI;CHI、IG和DF的性能大体相当，都能够过滤掉80%以上的特征项；DF具有算法简单、质量高的优点，可以用来代替CHI和IG,但是同被广泛接受的信检索理论有些矛盾。我们这里得出的结论，同文献（Yangetal.1997）使用普通英文文本评测的结果基本一致。（摘自李晓明搜索引擎原理、技术、与系统）DF、卡方、点对点互信息、信息增益法提取特征词对比（四）DF、卡方、点对点互信息、信息增益法提取特征词对比（五）我的实验结论：评价一个特征词是否是好词，一个特征词集合是否选择的合理。主要看所选择的词是否具有类别标识性。所谓类别标识性有以下两点含有：1。Distinctiveforcategorization：也就是说，如果该词出现则可以以一个很大的概率将文章归为某类。2。该词在它所“标识”的类别中应该频繁出现。DF法选择的特征词满足第二个条件多一点；而点互信息法选择的特征词只满足第一个条件多一点；而IG法和卡方法在满足两个条件方面达到了均衡。所以IG和卡方法性能差不多，优于DF法，DF优于点互信息法。（注：这是我个人的一点见地，如有偏颇的地方欢迎指正）由此我们可以得出这样的结论：IG法，卡方法，虽然有抑制高频词噪声和低频词噪声的能力，但是归根结底，这两种方法是基于频率的经典经典统计推断，不能够有效抑制全部高频词噪声，如果要提高特征词集合抑制高频词噪声的能力，可能要求诸于贝叶斯贝叶斯统计推断。评估分类器的效果（EFFECTIVENESS）(一)效果(effectiveness):这个术语来统称那些分类结果质量的评价指标，包括正确率、召回率和F1值。性能（performance):这个术语主要指的是分类或者IR系统的计算计算效率。评估分类器的效果（EFFECTIVENESS）(二)经常把分类问题（多分类问题）看成是二类问题（是否属于某个特定类别）。但针对某一个具体类别来说，我们又可以这样考虑：即有多少篇文章属于该类？有多少篇文章不属于该类？如果将属于该类的文章定义为“正例”，不属于该类别的文章定义为负例，那么就有了查准率，查全率，F-score等性能评估标准。分类器的混合矩阵：可以这样考虑TP,FN,FP,TN的含义：TP（TrulyPositve）：是指那些分类为正例实际上也是正例的文章；FP（FalselyPostive）：是指那些分类为正例但是实际上为负例的文章；FN（FalselyNegtive）：是指那些分类为负例但是实际上为正例的文章；TN（TrulyNegtive）:是指那些分类为负例，实际上也为负例的文章。查准率（precision）p=TP/(TP+FP)。它的含义是：测试集中被正确分类的正例数量除以测试集中被分类为正例的数据数量。查全率(recall)r=TP/(TP+FN)。它的含义是：测试集中被正确分类的正例数量除以测试集中实际正例数量。F-score=2pr/(p+r)。它是查准率和查全率的调和平均值。F-score更接近于p,r两个数种较小的那个文本分类以及预处理代码实现文本分类以及预处理代码实现预处理算法处理框架图分类算法框架图KNN算法KNN文本分类算法又称为(knearestneighhor)。它是一种基于事例的学习方法，也称懒惰式学习方法。它的大概思路是：对于某个待分类的样本点，在训练集中找离它最近的k个样本点，并观察这k个样本点所属类别。看这k个样本点中，那个类别出现的次数多，则将这类别标签赋予该待分类的样本点。重要数据结构定义typedefmapstring,vectorpairDICTIONARY;/定义字典数据结构typedefmappair,pairCONTINGENCY;/定义关联表数据结构typedefmapint,vectorpairDOCMATRIX;/文档向量矩阵typedefvectorpairRESULTINFO;/最后的分类和聚类结果信息编程思路操纵数据库模块intConstructDictionary(DICTIONARY&mymap,FUNCSEGseg,stringtablename);/从数据库中读出文章，分词，过滤停用词建立词典intGetArticleIdinEachClass(vectorlabels,stringtablename,mapstring,vector&articleIdinEachClass);/ 获得训练集中每一类所包含的文章IDvectorGetClassification(stringarticleIds);/ 获得指定篇文章ID号集合分别对应的类别stringGetCategorizationInfoById(intarticleId,stringtablename);/ 获得指定ID号的文章ID信息intPreprocess:GetManyVSM(intbegin,intend,stringtablename,DICTIONARY&mymap,DOCMATRIX&testingsetVSM,char*keywordsaddress)/ 为测试样本集合建立VSM模型序列化模块voidSaveDictionary(DICTIONARY&mymap,char*address);/将词典序列化到硬盘voidLoadDictionary(DICTIONARY&mymap,char*address);/将词典反序列化到内存voidSaveContingencyTable(CONTINGENCY&contingencyTable,char*address);/ 将关联表序列化到硬盘voidLoadContingencyTable(CONTINGENCY&contingencyTable,char*address);/ 将关联表结构反序列化到内存voidSaveVSM(DOCMATRIX&VSMmatrix,char*dest);/保存VSM模型到硬盘voidLoadVSM(DOCMATRIX&VSMmatrix,char*dest);/将VSM分词模块：头文件中定义了一个指向指向类的成员函数的指针，分别指向两种不同的切分模式。其中一种切分模式调用计算所的ICTCLAS；另一种切分模式以空格作为分界符进行分割vectorgoodWordsinPieceArticle(stringrawtext,setstopwords);vectormySplit(strings,setstopwords);文档向量模型权重计算（一）文档向量模型权重计算（二）文档向量模型权重计算（三）程序调用程序调用语料库格式（测试语料训练语料放在不同的数据表中）程序调用（一）程序调用（二）程序调用（三）程序调用（四）程序调用（五）分类器效果（EFFECTIVENESS）评估mapstring,vectorevaluation;for(vector:iteratorit=labels.begin();it!=labels.end();it+)doubleprecision=p.getPrecision(*it,classifyResults,TestingCorpus);doublerecall=p.getRecall(*it,classifyResults,TestingCorpus);doubleF=p.getFscore(*it,classifyResults,TestingCorpus);vectortemp;temp.push_back(precision);temp.push_back(recall);temp.push_back(F);evaluation*it=temp;temp.clear();for(mapstring,vector:iteratorit=evaluation.begin();it!=evaluation.end();it+)coutfirstendl;coutprecisonsecond)0endl;coutrecallsecond)1endl;coutFscoresecond)2endl;cout*endl;doubleavaP=0.;/平均准确率doubleavaR=0.;/平均召回率doubleavaF=0.;/平均F值for(mapstring,vector:iteratorit=evaluation.begin();it!=evaluation.end();it+)avaP+=(it-second)0;avaR+=(it-second)1;avaF+=(it-second)2;coutevaluation.size();avaP/=evaluation.size();avaR/=evaluation.size();avaF/=evaluation.size();cout平均准确率为avaPendl;cout平均召回率avaRendl;cout平均F值avaFendl;附录：资源推荐Boost库安装vs2008安装boost手记获取语料库搜狗2008版语料库http:/www.sogou.com/labs/dl/cs.html处理程序参考书目C.D.ManingIntroductiontoinformationRetrieval（王斌译）搜索引擎-原理、技术与系统THANKSALOT!