文本挖掘技术04-分类

1文本自动分类技术杨建武Email:[e-mail]第四章：北京大学计算机科学技术研究所文本挖掘技术2知识的组织¾知识的结构和知识是孪生的兄弟™结构本身也是知识¾分类体系™杜威十进制系统（图书分类），™国会图书馆的目录，™AMS（美国数学会）的数学知识体系，™美国专利内容的类别体系¾Webcatalogs™Yahoo以前的主页™OpenDirectory（）•志愿者共同维护与建设的最大的全球目录社区3OpenDirectory（）4分类的概念¾分类：对于给定一个对象，从一个事先定好的分类体系中挑出一个（或者多个）最适合该对象的类别。™对象：可以是任何东西™事先定好的分类体系：可能有结构™最适合：判断标准¾便于今后查找是其最直接、最普遍的应用5分类体系¾分类体系一般人工构造™政治、体育、军事¾分类系统可以是层次结构非学术性学术性人文与艺术新闻与媒体商业与经济社会与文化娱乐与休闲政府与政治教育自然科学社会科学医疗与健康¾分类模式™2类问题，属于或不属于(binary)™多类问题，多个类别(multi-class)，可拆分成2类问题™一个对象可以属于多类(multi-label)6人工方法和自动方法¾人工方法™知识工程的方法建立专家系统(80年代末期)™结果容易理解•足球and联赛Æ体育类™费时费力•MEDLINE(NationalLibraryofMedicine)$2million/yearformanualindexingofjournalarticles™难以保证一致性和准确性(40%左右的准确率)™专家有时候凭空想象¾自动的方法(学习)™结果可能不易理解™快速™准确率相对高(准确率可达85%或者更高)™来源于真实文本，可信度高7文本自动分类的定义¾TextCategorization(TC)¾在给定的分类体系下，根据文本的内容自动地确定文本关联的类别。¾从数学角度来看，文本分类是一个映射的过程，它将未标明类别的文本映射到已有的类别中，该映射可以是一一映射或一对多的映射。¾用数学公式表示如下：合为分类体系中的类别集为待分类的文本集合，其中，:BABAf→8应用领域¾门户网站（网页）¾图书馆（电子资料）¾情报/信息部门（情报处理）¾政府、企业等（电子邮件）9自动分类的优点¾减小人工分类的繁杂工作¾提高信息处理的效率¾减小人工分类的主观性10文本自动分类¾基本步骤™定义分类体系™将预先分类过的文档作为训练集™从训练集中得出分类模型（需要测试过程，不断细化）™用训练获得出的分类模型对其它文档加以分类11文本分类基本步骤¾1.用户定义分类树¾2.用户为分类节点提供训练文档¾3.特征选择¾4.训练¾5.自动分类12文本分类基本步骤13文本分类的过程文本表示训练过程分类过程训练文本训练文本统计统计统计量特征表示特征表示学习学习分类器分类器新文本新文本特征表示特征表示类别14自动分类技术的发展15专家系统(late1980s)人工定义规则16专家系统¾专家系统（人工定义规则）™太花时间™太难（最初看起来容易）™一致性问题(规则集很大)17专家系统¾美国人口调查局（1990）™十年人口统计资料的分析（2200万项资料）™232个产业类别和504个行业类别™$15millioniffullydonebyhand¾人工定义规则™ExpertSystemAIOCS™Developmenttime:192person-months(2people,8years)™Accuracy=47%¾基于机器学习的方法™最近邻分类方法(Creecy’92:1-NN)™Developmenttime:4person-months™Accuracy=60%18统计学习取代知识工程19自动分类技术发展文本分类实例21新闻自动分类¾Given:Collectionofexamplenewsstoriesalreadylabeledwithacategory(topic).¾Task:Predictcategoryfornewsstoriesnotyetlabeled.¾Forourexample,we’llonlygettoseetheheadline（标题）ofthenewsstory.¾We’llrepresentcategoriesusingcolors.(Allexampleswiththesamecolorbelongtothesamecategory.)22AmatilProposesTwo-for-FiveBonusShareIssueJardineMathesonSaidItSetsTwo-for-FiveBonusIssueReplacing“B”SharesBowaterIndustriesProfitExceedExpectationsCitibankNorwayUnitLosesSixMlnCrownsin1986VieilleMontagneSays1986ConditionsUnfavourableIsuzuPlansNoInterimDividendAnheuser-BuschJoinsBidforSanMiguelItaly’sLaFondiariatoReportHigher1986ProfitsJapanMinistrySaysOpenFarmTradeWouldHitU.S.SenatorDefendsU.S.MandatoryFarmControlBill人工标注的样例企业个人事务政府事务23能给一个新闻赋予什么颜色？?AmatilProposesTwo-for-FiveBonusShareIssueJardineMathesonSaidItSetsTwo-for-FiveBonusIssueReplacing“B”SharesBowaterIndustriesProfitExceedExpectationsCitibankNorwayUnitLosesSixMlnCrownsin1986VieilleMontagneSays1986ConditionsUnfavourableIsuzuPlansNoInterimDividendAnheuser-BuschJoinsBidforSanMiguelItaly’sLaFondiariatoReportHigher1986ProfitsJapanMinistrySaysOpenFarmTradeWouldHitU.S.SenatorDefendsU.S.MandatoryFarmControlBill分类预测：取多数？什么没看到之前24SenatePanelStudiesLoanRate,SetAsidePlansAmatilProposesTwo-for-FiveBonusShareIssueJardineMathesonSaidItSetsTwo-for-FiveBonusIssueReplacing“B”SharesBowaterIndustriesProfitExceedExpectationsCitibankNorwayUnitLosesSixMlnCrownsin1986VieilleMontagneSays1986ConditionsUnfavourableIsuzuPlansNoInterimDividendAnheuser-BuschJoinsBidforSanMiguelItaly’sLaFondiariatoReportHigher1986ProfitsJapanMinistrySaysOpenFarmTradeWouldHitU.S.SenatorDefendsU.S.MandatoryFarmControlBill看见标题25SenatePanelStudiesLoanRate,SetAsidePlansAmatilProposesTwo-for-FiveBonusShareIssueJardineMathesonSaidItSetsTwo-for-FiveBonusIssueReplacing“B”SharesBowaterIndustriesProfitExceedExpectationsCitibankNorwayUnitLosesSixMlnCrownsin1986VieilleMontagneSays1986ConditionsUnfavourableIsuzuPlansNoInterimDividendAnheuser-BuschJoinsBidforSanMiguelItaly’sLaFondiariatoReportHigher1986ProfitsJapanMinistrySaysOpenFarmTradeWouldHitU.S.SenatorDefendsU.S.MandatoryFarmControlBill得到分类：政府事务26评价指标27评价指标¾「准确率」（P,precision）¾「召回率」（R,recall）¾F－Measure()RPF1111αα−+=RPPRF+=2128评价指标¾每个类™Precision=a/(a+b)™Recall=a/(a+c),™missrate=1-recall™accuracy=(a+d)/(a+b+c+d),error=(b+c)/(a+b+c+d)=1-accuracy™fallout=b/(b+d)=falsealarmrate,™F=(β2+1)p.r/(β2p+r)™BreakEvenPoint,BEP,p=r的点™interpolated11pointaverageprecision(p-r曲线)29评价指标¾所有类的总体评价iiiiiRPRPF+=21¾宏平均Macro¾微平均Micro∑∑==⋅=−miimiiinFnFMicro11)(∑==−miiFmFMacro11()iiiRPF1111αα−+=30特征抽取31文档模型¾布尔模型¾向量空间模型¾概率模型32特征抽取(featureextraction)¾预处理™去掉html一些tag标记™停用词(stopwords)去除、词根还原(stemming)™(中文)分词、词性标注、短语识别、…™词频统计(TFDF)™数据清洗：去掉噪声文档或文档内垃圾数据¾文本表示™向量空间模型¾降维技术™特征选择(FeatureSelection)™特征重构(Re-parameterisation，如LSI)33向量空间模型¾向量空间模型(VectorSpaceModel)™M个无序标引项ti(特征)，词根/词/短语/其他™每个文档dj可以用标引项向量来表示•(a1j,a2j,…,aMj)™权重计算，N个训练文档•AM*N=(aij)™相似度比较•Cosine计算•内积计算T3T1T2D1=2T1+3T2+5T3D2=3T1+7T2+T3Q=0T1+0T2+2T3732534Term的粒度¾Character，字：中¾Word，词：中国¾Phrase，短语：中国人民银行¾Concept，概念™同义词：开心高兴兴奋™相关词cluster，wordcluster：葛非/顾俊¾N-gram，N元组：中国国人人民民银银行¾某种规律性模式：比如某个window中出现的固定模式¾DavidLewis等一致地认为：(英文分类中)使用优化合并后的Words比较合适35权重计算方法¾布尔权重(booleanweighting)™aij=1(TFij0)or0(TFij=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(36特征选择37特