人工智能-AI-5文本分类89

文本分类胡佳妮提纲„文本分类概述„特征提取„主要分类算法„Rocchio法„贝叶斯„K近邻„决策树文本分类概述分类的概念„给定:„一个实例的描述,x∈X,X是实例空间„一个固定的文本分类体系:C={c1,c2,…cn}„由于类别是事先定义好的，因此分类是有指导的（或者说是有监督的）„确定:„实例x的类别c(x)∈C,c(x)是一个分类函数，定义域是X，值域是C说明„分类模式„2类问题，属于或不属于(binary)„多类问题，多个类别(multi-class)，可拆分成2类问题„一个文本可以属于多类(multi-label)„分类体系一般人工构造„政治、体育、军事„中美关系、恐怖事件„很多分类体系:Reuters分类体系、中图分类中图分类法A类马列主义、毛泽东思想B类哲学C类社会科学总论D类政治、法律E类军事F类经济G类文化、科学、教育、体育H类语言、文字I类文学J类艺术K类历史、地理N类自然科学总论O类数理科学和化学P类天文学、地球科学Q类生物科学R类医药、卫生S类农业科学U类交通运输V类航空、航天X类环境科学、劳动保护科学（安全科学）TB类一般工业技术TD类矿业工程TE类石油、天然气工业TF类冶金工业TG类金属学、金属工艺TH类机械、仪表工艺TJ类武器工业TK类动力工业TL类原子能技术TM类电工技术TN类无线电电子学、电信技术TP类自动化技术、计算技术TQ类化学工业TS类轻工业、手工业TU类建筑科学TV类水利工程系统结构标注工具机器学习工具机器学习工具模型数据标注的样本分类工具分类工具类别预处理预处理训练数据文本新数据文本分类的一般过程„收集训练集和测试集，对文本进行预处理„对文本类别进行人工标注„对文本进行特征提取„训练（学习）„评价„精确率、召回率、F1„宏平均，微平均文本分类示例“planninglanguageproofintelligence”MultimediaGUIGarb.Coll.SemanticsML测试数据(Programming)(AI)(HCI)Planning类别garbagecollectionmemoryoptimizationregion...programmingsemanticslanguageproof...planningtemporalreasoningplanlanguage...learningintelligencealgorithmreinforcementnetwork.........训练数据预处理„去掉网页中的导航信息„去掉HTML网页中的tag标记„(中文)分词、词性标注、短语识别、…„去除停用词和词根还原(stemming)„数据清洗：去掉不合适的噪声文档或文档内垃圾数据„⋅⋅⋅⋅⋅⋅特征提取(FeatureSelection)„特征提取„在文本分类问题中遇到的一个主要困难就是高维的特征空间。„通常一份普通的文本在经过文本表示后，如果以词为特征，它的特征空间维数将达到几千，甚至几万。„大多数学习算法都无法处理如此大的维数。„为了能够在保证分类性能的前提下，自动降低特征空间的维数，在许多文本分类系统的实现中都引入了特征提取方法。学习„训练样本实例：x,c(x)„一个文本实例x∈X„带有正确的类别标记c(x)„学习的过程是在给定训练样本集合D的前提下，寻找一个分类函数h(x),使得:)()(:)(,xcxhDxcx=∈∀分类的评测„偶然事件表（ContingencyTable）„对一个分类器的度量„准确率(precision)=a/(a+b)„召回率(recall)=a/(a+c)„fallout=b/(b+d)属于此类不属于此类判定属于此类AB判定不属于此类CDDABCPrecisionBEPRecallBEP和F测度„BEP（break-evenpoint）„当准确率和召回率相等时的值即为BEP„F测度，取β=1„BEP和F测度的值越大，则表示分类器的性能越好。„BEP只是F1所有可能取值中的一个特定值（当p=r时），因此BEP小于或等于F1的最大值。()()rpprrpFβ++=221,ββrpprF+=21多类分类问题的评价„宏平均（macro-averaging）„先对每个分类器计算上述量度，再对所有分类器求平均„是关于类别的均值„微平均（micro-averaging）„先合并所有分类器的偶然事件表中的各元素，得到一个总的偶然事件表，再由此表计算各种量度。„是关于文本的均值文本分类的应用„新闻出版按照栏目分类„类别{政治,体育,军事,…}„网页分类„类似于Yahoo的分类„个性化新闻„智能推荐„垃圾邮件过滤„类别{spam,not-spam}特征提取举例„对每类构造k个最有区别能力的term„例如：„计算机领域：„主机、芯片、内存、编译…„汽车领域:„轮胎，方向盘，底盘，气缸，…文本表示„向量空间模型(VectorSpaceModel)„M个无序标引项ti(特征)„词根/词/短语/其他„每个文档dj可以用标引项向量来表示„(a1j,a2j,…,amj)„权重计算，N个训练文档„AM*N=(aij)„相似度比较„Cosine计算„内积计算Term的粒度„字(Character)：中„词(Word)：中国„短语(Phrase)：中国人民银行„概念(Concept)：„同义词：开心/高兴/兴奋„相关词词簇(wordcluster)：葛非/顾俊„N-gram(N元组)：„中国/国人/人民/民银/银行„某种规律性模式：比如某个window中出现的固定模式„DavidLewis等一致地认为：(英文分类中)使用优化合并后的Words比较合适用文档频率选特征„词频„TF(TermFrequency)„TFi,j：特征i在文档j中出现次数„文档频率„DF(DocumentFrequency)„DFi：所有文档集合中出现特征i的文档数目„基本假设：稀少的词或者对于目录预测没有帮助，或者不会影响整体性能。„实现方法：先计算所有词的DF，然后删除所有DF小于某个阈值的词，从而降低特征空间的维数。„优缺点：„最简单的降低特征空间维数的方法„稀少的词具有更多的信息，因此不宜用DF大幅度地删除词权重计算方法„布尔权重(booleanweighting)„aij=1(TFij0)or(TFij=0)0„TFIDF型权重„TF:aij=TFij„TF*IDF:aij=TFij*log(N/DFi)„TFC:对上面进行归一化„LTC:降低TF的作用∑=kkkjiijijDFNTFDFNTFa2)]/log(*[)/log(*∑++=kkkjiijijDFNTFDFNTFa2)]/log(*)0.1[log()/log(*)0.1log(信息增益„term的熵„该值越大，说明分布越均匀，越有可能出现在较多的类别中；„该值越小，说明分布越倾斜，词可能出现在较少的类别中„信息增益(InformationGain,IG)：„该term为整个分类所能提供的信息量„不考虑任何特征的熵和考虑该特征后的熵的差值„信息增益计算的是已知一个词t是否出现在一份文本中对于目录预测有多少信息。„这里的定义是一个更一般的、针对多个目录的定义。∑−=iiitcPtcPtEntropy)|(log)|()(信息增益)}]|(log)|(){()}|(log)|(){([)}(log)({)Entropy(Expected)(EntropyGain(t)111tcPtcPtPtcPtcPtPcPcPSSiMiiiMiiiMiit∑∑∑===−+−−−=−=∑∑+=iiririrriiririrrcPtcPtcPtPcPtcPtcPtPtG)()|(log)|()()()|(log)|()()(t出现的概率t不出现假定t出现时取第i个目录的概率取第i个目录时的概率交叉熵（CrossEntropy）„相对熵：也称为KL距离(Kullback-Leiblerdivergence)，反映了文本类别的概率分布和在出现了某个特定词汇条件下的文本类别的概率分布之间的距离，该值越大，词对文本类别分布的影响也大。„交叉熵的定义与信息增益近似，不同之处在于交叉熵只考虑一个词t出现时的影响。它的定义为：∑=iiririrrcPtcPtcPtPtC)()|(log)|()()(∑=iiiicPtcPtcPtCE)()|(log)|()(互信息（MutualInformation）„互信息(MutualInformation)：MI越大t和c共现程度越大„互信息的定义与交叉熵近似，只是互信息不考虑t出现的概率，它的定义为：))((log)()|(log)()()(log),(BACANAtPctPcPtPctPctI++×==∧=∑==miiiAVGctIcPtI1),()()(),()(max)(1iimiMAXctIcPtI==χ2统计量(念CHI)：„χ2统计量的定义可以从一个词t与一个目录c的偶然事件表引出（假设文本的总数为N）„度量两者(term和类别)独立性的缺乏程度„χ2越大，独立性越小，相关性越大„若ADBC,则类和词独立,N=A+B+C+DABCDt~tc~c))()()(()(),(22DCBADBCACBADNct++++−=χ),()()(212imiiAVGctcPtχχ∑==)},({max)(212imiMAXcttχχ==几率比（OddsRatio）„几率比是一种在信息检索中广泛使用的方法，它的定义是：„Pr(t|pos)为已知目录值为正“positive”时t出现的条件概率„Pr(t|neg)为已知目录值为负“negative”时t出现的条件概率。)|Pr())|Pr(1())|Pr(1)(|Pr(log)(negtpostnegtposttOddsRatio−−=特征提取方法的性能比较(1)特征提取方法的性能比较(2)特征提取方法的性能比较(3)YangYi-ming,CMU,USARocchio法Rocchio方法„可以认为类中心向量法是它的特例„Rocchio公式„分类CCiijCCiijjcjcnnxnxww−−+=∑∑∉∈γβα'类C中心向量的权重训练样本中正例个数文档向量的权重∑∑∑⋅=⋅=22cxw)(ijcjijcjiicxwxwdCSVRocchio文本分类算法(训练)„假设类别集合为{c1,c2,…cn}„Forifrom1tonletpi=0,0,…,0(init.prototypevectors)„Foreachtrainingexamplex,c(x)∈D„LetdbethefrequencynormalizedTF/IDFtermvectorfordocx„Leti=j:(cj=c(x))„(sumallthedocumentvectorsincitogetpi)„Letpi=pi+dRocchio文本分类算法(测试)„Giventestdocumentx„LetdbetheTF/IDFweightedtermvectorforx„Letm=–2(init.maximumcosSim)„Forifrom1ton:„(computesimilaritytoprototypevector)„Lets=cosSim(d,pi)„ifsm„letm=s„letr=ci(updatemostsimilarclassprototype)„ReturnclassrRocchio事件复杂度„Note:将两个稀疏的向量相加的时间是和两个向量中的非零项的个数成正比的„训练时间:O(|D|(Ld+|Vd|))=O(|D|Ld)„D：文档集合„Ld：D中文档的平均长度„Vd：D中文档的平均词表大小„测试时间:O(Lt+|C||Vt|)„Lt：测试文档的平均长度„|Vt|：测试文档的平均词表长度„假设pi向量的长度在训练的过程中被计算和存储,cosSim(d,pi)的计算在时间上和d中的非零项的数量成比例贝叶斯分类贝叶斯分类„给定训练集D,h的后验概率P(h|D)遵循下面的B