TextMining04-分类

1文本自动分类技术杨建武Email:[e-mail]第四章：北京大学计算机科学技术研究所文本挖掘技术(2012春)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自动分类的优点减小人工分类的繁杂工作提高信息处理的效率减小人工分类的主观性8文本自动分类的定义TextCategorization(TC)在给定的分类体系下，根据文本的内容自动地确定文本关联的类别。从数学角度来看，文本分类是一个映射的过程，将未标明类别的文本映射到已有的类别中该映射可以是一一映射或一对多的映射。用数学公式表示如下：合为分类体系中的类别集为待分类的文本集合，其中，:BABAf9自动分类技术的发展10专家系统(late1980s)人工定义规则11专家系统专家系统（人工定义规则）太花时间太难（最初看起来容易）一致性问题(规则集很大)12专家系统美国人口调查局（1990）十年人口统计资料的分析（2200万项资料）232个产业类别和504个行业类别$15millioniffullydonebyhand人工定义规则ExpertSystemAIOCSDevelopmenttime:192person-months(2people,8years)Accuracy=47%基于机器学习的方法最近邻分类方法(Creecy’92:1-NN)Developmenttime:4person-months;Accuracy=60%13统计学习取代知识工程14基于统计学习文本自动分类基本步骤定义分类体系将预先分类过的文档作为训练集从训练集中得出分类模型（需要测试过程，不断细化）用训练获得出的分类模型对其它文档加以分类“文本分类”通常指“基于统计学习文本自动分类”15文本分类基本步骤1.用户定义分类树2.用户为分类节点提供训练文档3.特征选择4.训练5.自动分类16文本分类过程待分类文本特征表示预处理训练集实例训练分类算法校验集校验策略每个类的阈值测试结果类别表阈值策略候选类列表分类模型训练过程分类过程17自动分类技术发展18应用领域门户网站（网页）图书馆（电子资料）情报/信息部门（情报处理）政府、企业等（电子邮件）文本分类实例20新闻自动分类Given:Collectionofexamplenewsstoriesalreadylabeledwithacategory(topic).Task:Predictcategoryfornewsstoriesnotyetlabeled.Forourexample,we’llonlygettoseetheheadline（标题）ofthenewsstory.We’llrepresentcategoriesusingcolors.(Allexampleswiththesamecolorbelongtothesamecategory.)21AmatilProposesTwo-for-FiveBonusShareIssueJardineMathesonSaidItSetsTwo-for-FiveBonusIssueReplacing“B”SharesBowaterIndustriesProfitExceedExpectationsCitibankNorwayUnitLosesSixMlnCrownsin1986VieilleMontagneSays1986ConditionsUnfavourableIsuzuPlansNoInterimDividendAnheuser-BuschJoinsBidforSanMiguelItaly’sLaFondiariatoReportHigher1986ProfitsJapanMinistrySaysOpenFarmTradeWouldHitU.S.SenatorDefendsU.S.MandatoryFarmControlBill新闻自动分类企业个人事务政府事务人工标注的样例22能给一个新闻赋予什么颜色？?AmatilProposesTwo-for-FiveBonusShareIssueJardineMathesonSaidItSetsTwo-for-FiveBonusIssueReplacing“B”SharesBowaterIndustriesProfitExceedExpectationsCitibankNorwayUnitLosesSixMlnCrownsin1986VieilleMontagneSays1986ConditionsUnfavourableIsuzuPlansNoInterimDividendAnheuser-BuschJoinsBidforSanMiguelItaly’sLaFondiariatoReportHigher1986ProfitsJapanMinistrySaysOpenFarmTradeWouldHitU.S.SenatorDefendsU.S.MandatoryFarmControlBill什么没看到之前，分类预测：取多数？新闻自动分类23SenatePanelStudiesLoanRate,SetAsidePlansAmatilProposesTwo-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得到分类：政府事务25评价指标26评价指标「准确率」（P,precision）「召回率」（R,recall）F－MeasureRPF1111RPPRF21142527评价指标每个类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曲线)28评价指标所有类的总体评价iiiiiRPRPF21宏平均Macro微平均MicromiimiiinFnFMicro11)(miiFmFMacro11iiiRPF111129特征抽取30文档模型布尔模型向量空间模型概率模型31特征抽取(featureextraction)预处理去掉html一些tag标记停用词(stopwords)去除、词根还原(stemming)(中文)分词、词性标注、短语识别、…词频统计(TF,DF)数据清洗：去掉噪声文档或文档内垃圾数据文本表示向量空间模型降维技术特征选择(FeatureSelection)特征重构(Re-parameterisation，如LSA)32向量空间模型向量空间模型(VectorSpaceModel)M个无序标引项ti(特征)，词根/词/短语/其他每个文档dj可以用标引项向量来表示•(a1j,a2j,…,aMj)权重计算，N个训练文档•AM*N=(aij)相似度比较•Cosine计算•内积计算T3T1T2D1=2T1+3T2+5T3D2=3T1+7T2+T3Q=0T1+0T2+2T3732533Term的粒度Character，字：中Word，词：中国Phrase，短语：中国人民银行Concept，概念同义词：开心高兴兴奋相关词cluster，wordcluster：葛非/顾俊N-gram，N元组：中国国人人民民银银行某种规律性模式：比如某个window中出现的固定模式DavidLewis等认为：(英文分类中)使用优化合并后的Words比较合适34权重计算方法布尔权重(booleanweighting)aij=1(TFij0)or0(TFij=0)TFIDF型权重TF:aij=TFijTF*IDF:aij=TFij*log(N/DFi)TFC:对上面进行归一化LTC:降低TF的作用kkkjiijijDFNTFDFNTFa2)]/log(*[)/log(*kkkjiijijDFNTFD