贝叶斯算法文本分类..

××××××××××文本分类问题的提出◆假想图书馆的图书资料不加以分类,结果如何?◆随着互联网技术的飞速发展，各种电子文本数据的数量急剧增加◆信息数据量的爆炸性增长使得传统的手工处理方法变得不切合实际××××××××××文本表示文本分类的基本概念第一部分特征选择第三部分分类器设计第四部分目录分类器评价第五部分第二部分有意义串对分类的改进第六部分××××××××××文本分类的基本概念文本分类(TextCategorization或TextClassification，TC)是根据给定文本的内容，将其判别为事先确定的若干个文本类别中的某一类或某几类的过程。这里所指的文本可以是媒体新闻、科技、报告、电子邮件、技术专利、网页、书籍或其中的一部分。由于类别是事先定义好的，因此分类是有指导的（或者说是有监督的）××××××××××文本分类的基本概念–分类体系一般人工构造•政治、体育、军事。。。•中美关系、恐怖事件。。。–分类系统可以是层次结构，如yahoo!–分类模式•2类问题，属于或不属于(binary)•多类问题，多个类别(multi-class)，可拆分成2类问题•一个文本可以属于多类(multi-label)–这里讲的分类主要基于内容–很多分类体系:Reuters分类体系、中图分类××××××××××文本分类的基本概念•冗余过滤在数字图书馆和搜索引擎的建设中•组织管理图书馆利用图书分类法来管理所收藏的图书资料•智能检索搜索引擎的构建过程中•信息过滤“人找信息”成为“信息找人”•其它应用元数据提取、构建索引、文本过滤应用领域××××××××××文本分类的基本概念文本分类的一般过程文本表示训练过程分类过程训练文本统计统计量特征表示学习分类器新文本特征表示类别××××××××××文本分类的基本概念文本表示第一部分特征选择第三部分分类器设计第四部分目录分类器评价第五部分第二部分有意义串对分类的改进第六部分××××××××××文本表示-中文分词中文的预处理要比英文的预处理要复杂的多，因为汉语的基元是字而不是词，句子中的词语间没有固定的分隔符（如空格），因此必需对中文文本进行词条切分处理。◆基于词典和规则的方法，应用词典匹配、汉语词法、约束矩阵等知识进行分词◆基于统计的方法:将汉语基于字与词的统计信息，如相邻字间互信息、词频及相应贡献信息等应用于分词◆混和方法××××××××××文本表示-向量空间模型•向量空间模型(VectorSpaceModel,简称VSM)•文档（Document）：—泛指一般的文献或文献中的片断（段落、句子组或句子），一般指一篇文章。•项（Term）：当文档的内容被简单地看成是它含有的基本语言单位（字、词、词组或短语等）所组成的集合时，这些基本的语言单位统称为项，即文档可以用项集（TermList）表示为其中是项,),...,,(21nTTTDkTnk1××××××××××文本表示-向量空间模型项的权重（TermWeight）：—对于含有n个项的文档，项常常被赋予一定的权重,表示它们在文档中的重要程度，即Ｄ＝),...,,(21nTTTD),;...;,;,(2211nnWTWTWTD为了简化分析，可以暂不考虑在文档中的先后顺序并要求无异（即没有重复）–这时可以把看成一个n维的坐标系，而为相应的坐标值，因而被看成是n维空间中的一个向量kTkTnTTT,...,,21n),...,,(21n××××××××××文本表示-向量空间模型•相似度（Similarity）：当文档被表示为VSM，常用向量之间的内积来计算：或用夹角余弦值来表示：,*),(12121nkkkWWDDSim,))((*cos),(12212112121nkknkknkkk××××××××××文本分类的基本概念特征选择第一部分文本表示第三部分分类器设计第四部分目录分类器评价第五部分第二部分有意义串对分类的改进第六部分××××××××××特征选择•目的:–为了提高程序的效率，提高运行速度–为了提高分类精度•一些通用的、各个类别都普遍存在的词汇对分类的贡献小•在某特定类中出现比重大而在其他类中出现比重小的词汇对文本分类的贡献大•对于每一类，我们应去除那些表现力不强的词汇，筛选出针对该类的特征项集合××××××××××特征选择•文档频率DF•信息增益IG•互信息MI•统计量（CHI-2）2常用方法××××××××××特征选择常用方法-文档频率DF–Documentfrequency，文档频率，简称DF–指在训练语料中出现某词条的文档数–Term的DF小于某个阈值去掉(太少，没有代表性)–Term的DF大于某个阈值也去掉(太多，没有区分度)××××××××××特征选择常用方法-信息增益IG•对于特征词条t和文档类别c，IG考察c中出现和不出现t的文档频数来衡量t对于c的信息增益，定义如下：××××××××××特征选择常用方法-信息增益IG•信息增益的优点在于，它考虑了词条未发生的情况，即虽然某个单词不出现也可能对判断文本类别有贡献。•但在类分布和特征值分布是高度不平衡的情况下其效果就会大大降低了。××××××××××特征选择常用方法-互信息MI•互信息(MutualInformation)在统计语言模型中被广泛使用。•它是通过计算特征词条t和类别c之间的相关性来完成提取的。其定义如下:()(,)lg()()PtcMItcPtPc××××××××××特征选择常用方法-互信息MI•如果用A表示包含特征词条t且属于类别c的文档频数，B为包含t但是不属于c的文档频数，C表示属于c但不包含t的文档频数，N表示语料中文档的总数，t和c的互信息可由下式计算：(,)lg()()ANMItcACAB××××××××××特征选择常用方法-统计量（CHI-2）2•它度量特征词条t和文档类别c之间的相关程度，并假设t和c之间符合具有一阶自由度的分布。•特征词条对于某类的统计值越高，它与该类之间的相关性越大，携带的类别信息也越多。•反之，统计量也是反映属性t和类别c之间的独立程度。当值为0时，属性t与类别c完全独立。××××××××××特征选择常用方法-统计量（CHI-2）2•令N表示训练语料中的文档总数，c为某一特定类别，t表示特定的词条•A表示属于c类且包含t的文档频数，B表示不属于c但是包含t的文档频数•C表示属于c类但是不包含t的文档频数，D是既不属于c也不包含t的文档频数.其定义为：))()()(()(),(22DCBADBCACBADNctABCDt~tc~c××××××××××特征选择特征选择方法性能比较××××××××××特征选择特征选择方法性能比较注：以上实验结果来自于Yang,Y.,PedersenJ.P.AComparativeStudyonFeatureSelectioninTextCategorizationProceedingsoftheFourteenthInternationalConferenceonMachineLearning(ICML'97),1997,pp412-420.××××××××××特征选择文本分类的基本概念分类器设计第一部分文本表示第三部分第四部分目录分类器评价第五部分第二部分有意义串对分类的改进第六部分××××××××××分类器设计•文本分类的方法大部分来自于模式分类，基本上可以分为三大类:–一种是基于统计的方法，如NaïveBayes,KNN、类中心向量、回归模型、支持向量机、最大熵模型等方法–另一种是基于连接的方法，即人工神经网络–还有一种是基于规则的方法，如决策树、关联规则等，这些方法的主要区别在于规则获取方法××××××××××K近邻算法-KNN支持向量机算法-SVM决策树算法-DecisionTree神经网络算法-NeuralNetworks朴素贝叶斯算法-NaïveBayes分类器设计××××××××××分类器设计K近邻算法-KNN•基本思想是：–在给定新文本后，考虑在训练文本集中与该新文本距离最近(最相似)的K篇文本–根据这K篇文本所属的类别判定新文本所属的类别新文本k=1,A类k=4，B类k=10，c类××××××××××分类器设计K近邻算法-KNN•具体的算法步骤:–根据特征项集合重新描述训练文本向量–在新文本到达后，根据特征词，确定新文本的向量表示–在训练文本集中选出与新文本最相似的K个文本，计算公式为：其中，K值的确定目前没有很好的方法，一般先定一个初始值，然后根据试验测试的结果调整K值，一般初始值定在几百到几千之间12211(,)()()MikjkkijMMikjkkkwwsimddww××××××××××分类器设计K近邻算法-KNN•在新文本的k个邻居中，依次计算每类的权重，计算公式如下：其中，为新文本的特征向量，为相似度计算公式，与上一步骤的计算公式相同,而为类别属性函数，即如果属于类，那么函数值为1，否则为0；•比较每类的权重，将文本分到权重最大的那个类别中(,)(,)(,)ijiijdKNNpxcsimxdydcx(,)isimxd(,)ijydcidjc××××××××××分类器设计决策树算法-DecisionTree•决策树方法的起源是概念学习系统CLS，然后发展到ID3方法而为高潮，最后又演化为能处理连续属性的C4.5。有名的决策树方法还有CART和Assistant××××××××××分类器设计决策树的表示法•决策树通过把实例从根节点排列到某个叶子节点来分类实例，叶子节点即为实例所属的分类。•树上的每一个节点说明了对实例的某个属性的测试，并且该节点的每一个后继分支对应于该属性的一个可能值××××××××××分类器设计ID3决策树算法简介基本思路是不断选取产生信息增益最大的属性来划分样例集和，构造决策树。信息增益定义为结点与其子结点的信息熵之差。Pi为子集合中不同性(而二元分类即正样例和负样例)的样例的比例。××××××××××分类器设计ID3决策树算法简介这样信息收益可以定义为样本按照某属性划分时造成熵减少的期望，可以区分训练样本中正负样本的能力，其计算公式是××××××××××分类器设计ID3算法实例OutlookTemperatureHumidityWindyClasssunnyhothighfalseNsunnyhothightrueNovercasthothighfalsePrainmildhighfalsePraincoolnormalfalsePraincoolnormaltrueNovercastcoolnormaltruePsunnymildhighfalseNsunnycoolnormalfalsePrainmildnormalfalsePsunnymildnormaltruePovercastmildhightruePovercasthotnormalfalsePrainmildhightrueN××××××××××分类器设计计算信息增益(),ValuesWindWeakStrong[9,5]S[6,2]WeakS[3,3]StrongS{,}(,)()vvWeakStrongSGainSWindEntroySEntropyS()(8/14)()(6/14)()WeakStrongEntropySEntropySEntropyS0.949(8/14)0.811(6/14)1.000.048××××××××××分类器设计不同属性的信息增益计算各属性的熵值Gain(S,Outlook)=0.246Gain(S,Humidity)=0.151Gain(S,Wind)=0.048Gain(S,Temperature)=0.029可以看到，Outlook得信息增益最大××××××××××分类器设计D1,D2,…D149+,5-OutlookSunnyD1,D2,D8,D9,D