06文本分类与聚类课件.ppt

1、文本分类与聚类哈工大信息检索研究室2007这一部分将讲述n文本分类及聚类的概念n文本特征的提取方法n贝叶斯分类，KNN分类及决策树分类nK均值及层次聚类的方法文本分类概述概述n文本分类包括普通文本分类和网页文本分类n中文网页分类技术已经成为中文信息处理领域的一项基础性工作n网页分类可以为搜索引擎用户提供目录导航服务，进而提高系统查准率n网页分类可以为个性化搜索引擎奠定基础分类的概念n给定:n一个实例的描述,xX,X是实例空间n一个固定的文本分类体系:C=c1,c2,cnn由于类别是事先定义好的，因此分类是有指导的（或者说是有监督的）n确定:n实例x的类别 c(x)C,c(x)是一个分类函数，定

2、义域是 X，值域是C说明n分类模式n2类问题，属于或不属于(binary)n多类问题，多个类别(multi-class)，可拆分成2类问题n一个文本可以属于多类(multi-label)n分类体系一般人工构造n政治、体育、军事n中美关系、恐怖事件n很多分类体系:Reuters分类体系、中图分类A类 马列主义、毛泽东思想 B类 哲学 C类 社会科学总论 D类 政治、法律 E类 军事 F类 经济 G类 文化、科学、教育、体育 H类 语言、文字 I类 文学 J类 艺术 K类 历史、地理 N类 自然科学总论 O类 数理科学和化学 P类 天文学、地球科学 Q类 生物科学 R类 医药、卫生 S类 农业科学

3、 U类 交通运输 V类 航空、航天 X类 环境科学、劳动保护科学（安全科学）TB类 一般工业技术 TD类 矿业工程 TE类 石油、天然气工业 TF类 冶金工业 TG类 金属学、金属工艺 TH类 机械、仪表工艺 TJ类 武器工业 TK类 动力工业 TL类 原子能技术 TM类 电工技术 TN类 无线电电子学、电信技术 TP类 自动化技术、计算技术 TQ类 化学工业 TS类 轻工业、手工业 TU类 建筑科学 TV类 水利工程 中图分类法中图分类法 系统结构标注工具模型数据标注的样本类别预处理预处理训练数据文本新数据文本MultimediaGUIGarb.Coll.SemanticsMLPlannin

4、gplanningtemporalreasoningplanlanguage.programmingsemanticslanguageproof.learningintelligencealgorithmreinforcementnetwork.garbagecollectionmemoryoptimizationregion.“planning language proof intelligence”训练数据训练数据测试数据测试数据类别类别(AI)文本分类示例(Programming)(HCI).分类的一般过程n收集训练集和测试集，对文本进行预处理n对文本进行特征提取n分类器训练（学习）n测

5、试与评价n精确率、召回率、F1n宏平均，微平均分类的评测n偶然事件表（Contingency Table）n对一个分类器的度量n准确率(precision)=a/(a+b)n召回率(recall)=a/(a+c)nfallout=b/(b+d)属于此类不属于此类判定属于此类AB判定不属于此类CDBEP和F测度nBEP（break-even point）n当准确率和召回率相等时的值即为BEPnF测度，取=1 nBEP和F测度的值越大，则表示分类器的性能越好。nBEP只是F1所有可能取值中的一个特定值（当p=r时），因此BEP小于或等于F1的最大值。rpprrpF221,rpprF21多类分类问题

6、的评价n宏平均（macro-averaging）n先对每个分类器计算上述量度，再对所有分类器求平均n是关于类别的均值n微平均（micro-averaging）n先合并所有分类器的偶然事件表中的各元素，得到一个总的偶然事件表，再由此表计算各种量度。n是关于文本的均值收集训练数据nTREC提供统一的训练集和测试集进行系统评测n国外：CMU,BERKLEY,CORNELLn国内：中科院计算所，清华大学，复旦大学n后续增加了网页语料和中文文本n但是中文文本是新华社的新闻稿，与网页的分类体系还有差别目前已有的评测语料n有指导的机器学习方法是实现中文网页自动分类的基础，因此训练集是实现分类的前提条件n已有

7、训练语料n863评测语料(中图分类)n搜狗语料n复旦语料训练语料分类体系n中图分类体系n处理对象是图书，不适合网页分类n学科分类与代码n1992年制定，时间过久，包括一些过时类别n上述两个分类标准都不能直接用做中文网页的分类n中文网页的分类体系一种中文网页的分类体系训练集的大小n通过不断增加实例的个数，考察每个类训练样本对分类器质量的影响 宏观F1 微观F1网页预处理n去掉网页中的导航信息n去掉HTML网页中的tag标记n(中文)分词、词性标注、短语识别、n去除停用词和词根还原(stemming)n数据清洗：去掉不合适的噪声文档或文档内垃圾数据n特征提取特征提取(Feature Selecti

8、on)n在文本分类问题中遇到的一个主要困难就是高维的特征空间n通常一份普通的文本在经过文本表示后，如果以词为特征，它的特征空间维数将达到几千，甚至几万n大多数学习算法都无法处理如此大的维数n为了能够在保证分类性能的前提下，自动降低特征空间的维数，在许多文本分类系统的实现中都引入了特征提取方法举例n对每类构造k 个最有区别能力的termn例如：n计算机领域计算机领域：n主机、芯片、内存、编译主机、芯片、内存、编译 n汽车领域汽车领域:n轮胎，方向盘，底盘，气缸，轮胎，方向盘，底盘，气缸，用文档频率选特征n文档频率nDF(Document Frequency)nDFi：所有文档集合中出现特征i的文

9、档数目n基本假设：稀少的词或者对于目录预测没有帮助，或者不会影响整体性能。n实现方法：先计算所有词的DF，然后删除所有DF小于某个阈值的词，从而降低特征空间的维数。n优缺点：n最简单的降低特征空间维数的方法n稀少的词具有更多的信息，因此不宜用DF大幅度地删除词词的熵nterm的熵n该值越大，说明分布越均匀，越有可能出现在较多的类别中；n该值越小，说明分布越倾斜，词可能出现在较少的类别中iiitcPtcPtEntropy)|(log)|()(信息增益(Information Gain,IG)iiririrriiririrrcPtcPtcPtPcPtcPtcPtPtG)()|(log)|()()(

10、)|(log)|()()(t 出现的概率 t 不出现假定t 出现时取第i 个类别的概率 取第 i 个类别时的概率n该term为整个分类所能提供的信息量n不考虑任何特征的熵和考虑该特征后的熵的差值n信息增益计算的是已知一个词t是否出现在一份文本中对于类别预测有多少信息。n这里的定义是一个更一般的、针对多个类别的定义。互信息（Mutual Information）n互信息(Mutual Information)：MI越大t和c共现程度越大n互信息的定义与交叉熵近似，只是互信息不考虑t不出现的概率，它的定义为：1()max(,)mMAXiiItI t cmiiiAVGctIcPtI1),()()(i

11、ririrtPctPcPtI)()|(log)()(2统计量（CHI）：n2统计量的定义可以从一个词t与一个类别c的偶然事件表引出（假设文本的总数为N）n度量两者(term和类别)独立性程度n2 越大，独立性越小，相关性越大n若ADBC,则类和词独立,N=A+B+C+DABCDttcc)()()()(),(22DCBADBCACBADNct特征提取方法的性能比较(Macro-F1)特征提取方法的性能比较(Micro-F1)结论n可以看出CHI，IG，DF性能好于MInMI最差nCHI，IG，DF性能相当nDF具有算法简单，质量高的优点，可以替代CHI，IG分类器学习n训练样本实例：n一个文本实

12、例 xXn带有正确的类别标记 c(x)n学习的过程是在给定训练样本集合D 的前提下，寻找一个分类函数h(x),使得:)()(:)(,xcxhDxcx贝叶斯分类贝叶斯分类n基于概率理论的学习和分类方法n贝叶斯理论在概率学习及分类中充当重要角色n仅使用每类的先验概率不能对待分的文本提供信息n分类是根据给定样本描述的可能的类别基础上产生的后验概率分布贝叶斯理论)()()|()|(EPHPHEPEHP)()()|(EPEHPEHP)()()|(HPEHPHEP)()|()(HPHEPEHP得到：由条件概率的定义：贝叶斯分类n设各个类别的集合为 c1,c2,cnn设E为实例的描述n确定E的类别nP(E)

13、可以根据下式确定)()|()()|(EPcEPcPEcPiiiniiiniiEPcEPcPEcP111)()|()()|(niiicEPcPEP1)|()()(贝叶斯分类(cont.)n需要知道:n先验概率:P(ci)n条件概率:P(E|ci)nP(ci)容易从数据中获得n如果文档集合D中，属于ci的样例数为 nin则有P(ci)=ni/|D|n假设样例的特征是关联的:n指数级的估计所有的 P(E|ci)meeeE21朴素的贝叶斯分类n如果假定样例的特征是独立的，可以写为：n因此，只需要知道每个特征和类别的P(ej|ci)n如果只计算单个特征的分布，大大地减少了计算量)|()|()|(121m

14、jijimicePceeePcEP文本分类 Nave Bayes算法(训练)设V为文档集合D所有词词表对每个类别 ci C Di 是文档D中类别Ci的文档集合 P(ci)=|Di|/|D|设 ni 为Di中词的总数 对每个词 wj V 令 nij 为Di中wij的数量 P(wi|ci)=(nij+1)/(ni+|V|)文本分类 Nave Bayes算法(测试)n给定测试文档 Xn设 n 为X中词的个数n返回的类别:nwi是X中第i个位置的词)|()(argmax1niiiiCiccwPcPNave Bayes分类举例nC=allergy,cold,wellne1=sneeze;e2=cough

15、;e3=fevern当前实例是：E=sneeze,cough,feverProbWellColdAllergyP(ci)0.9 0.05 0.05P(sneeze|ci)0.1 0.9 0.9P(cough|ci)0.1 0.8 0.7P(fever|ci)0.01 0.7 0.4过敏打喷嚏Nave Bayes 举例(cont.)n参数计算：nP(well|E)=(0.9)(0.1)(0.1)(0.99)/P(E)=0.0089/P(E)nP(cold|E)=(0.05)(0.9)(0.8)(0.3)/P(E)=0.01/P(E)nP(allergy|E)=(0.05)(0.9)(0.7)(0

16、.6)/P(E)=0.019/P(E)n最大概率类:allergynP(E)=0.089+0.01+0.019=0.0379nP(well|E)=0.23nP(cold|E)=0.26nP(allergy|E)=0.50Play-tennis 例子:估算 P(xi|C)Outlook Temperature Humidity Windy ClasssunnyhothighfalseNsunnyhothightrueNovercast hothighfalsePrainmildhighfalsePraincoolnormalfalsePraincoolnormaltrueNovercast co

17、olnormaltruePsunnymildhighfalseNsunnycoolnormalfalsePrainmildnormalfalsePsunnymildnormaltruePovercast mildhightruePovercast hotnormalfalsePrainmildhightrueNP(p)=9/14P(n)=5/14outlookP(sunny|p)=2/9P(sunny|n)=3/5P(overcast|p)=4/9P(overcast|n)=0P(rain|p)=3/9P(rain|n)=2/5temperatureP(hot|p)=2/9P(hot|n)=2

18、/5P(mild|p)=4/9P(mild|n)=2/5P(cool|p)=3/9P(cool|n)=1/5humidityP(high|p)=3/9P(high|n)=4/5P(normal|p)=6/9P(normal|n)=2/5windyP(true|p)=3/9P(true|n)=3/5P(false|p)=6/9P(false|n)=2/5正例反例Play-tennis例子:分类 Xn例子 X=nP(X|p)P(p)=P(rain|p)P(hot|p)P(high|p)P(false|p)P(p)=3/92/93/96/99/14=0.010582nP(X|n)P(n)=P(rai

19、n|n)P(hot|n)P(high|n)P(false|n)P(n)=2/52/54/52/55/14=0.018286n样本 X 被分到 n类，即“不适合打网球”举例n在Joachims(1996)的一个实验中，被应用于分类新闻组文章n20个电子新闻组，每个新闻组1000篇文章，形成2万个文档的数据集n2/3作训练集，1/3作测试集衡量性能n20 个新闻组，随机猜测的分类精确度5%，由程序获得的精确度89%讨论n朴素的贝叶斯假定在一个位置上出现的词的概率独立于另外一个位置的单词，这个假定有时并不反映真实情况n虽然独立性假设很不精确，别无选择，否则计算的概率项将极为庞大n幸运的是，在实践中朴

20、素贝叶斯学习器在许多文本分类中性能非常好，即使独立性假设不成立K近邻 K近邻（KNN）n最近邻分类规则n 对于测试样本点x，在集合中距离它最近的的x1。最近邻分类就是把x分为x1 所属的类别n最近邻规则的推广-KNNn没有好的相似度矩阵不能用 KNNKNN算法n目标：基于训练集X的对y分类n在训练集中，寻找和y最相似的训练样本xn得到k个最相似的集合A,A为X的一个子集n设n1,n2分别为集合中属于c1,c2的个数n如果p(c1|y)p(c2|y),判为c1,否则判为c2()(,)MAXx NsimyMAXsim x ymax|(,)()AxN sim x ysimy11(|)12np cyn

21、n22(|)12np cynnkNN方法n一种基于实例的学习方法新文本k=1,A类k=4，B类k=10，B类带权重计算，计算权重和最大的类。k常取3或者5。KNN在文本分类中的应用KNNn分类错误是由于：n单个的非典型样例 n单个训练样本的噪音.n更鲁棒的方法是发现k个最相似的样本，返回k个样本最主要的类别相似度矩阵n最近邻方法依赖于相似度矩阵(或距离).n对连续m维空间最简单的方法采用欧氏距.n对m维二值实例空间最简单的方法是海明距.n对于基于文本tf/idf权重向量的余弦相似度是经常被采用的.影响KNN的因素nK的取值nK一般取15n计算距离的方法n欧式距离n兰式距离（余弦相似度）KNN和

22、NB比较n从表中看，KNN质量较高，NB的效率较高n从各个类别看，KNN比NB稳定，NB对类别敏感决策树简介n决策树方法的起源是概念学习系统CLS，然后发展到ID3方法而为高潮，最后又演化为能处理连续属性的C4.5。有名的决策树方法还有CART和Assistantn应用最广的归纳推理算法之一n一种逼近离散值目标函数的方法决策树的表示法n决策树通过把实例从根节点排列到某个叶子节点来分类实例，叶子节点即为实例所属的分类。n树上的每一个节点说明了对实例的某个属性的测试，并且该节点的每一个后继分支对应于该属性的一个可能值决策树表示举例表达式()OutlookSunnyHumidityNormal()O

23、utlookOvercast()OutlookRainWindWeak决策树学习的适用问题n实例是由属性-值对表示的n目标函数具有离散的输出值n可能需要析取的描述n训练数据可以包含错误n训练数据可以包含缺少属性值的实例属性选择n构造好的决策树的关键在于如何选择好的逻辑判断或属性。n对于同样一组例子，可以有很多决策树能符合这组例子。n一般情况下或具有较大概率地说，树越小则树的预测能力越强。n要构造尽可能小的决策树，关键在于选择恰当的逻辑判断或属性。n由于构造最小的树是NP-难问题，因此只能采取用启发式策略选择好的逻辑判断或属性 用熵度量样例的均一性（纯度）n熵的定义n举例关于某布尔分类的熵函数用

24、信息增益度量期望熵最低n一个属性的信息增益就是由于使用这个属性分割样例而导致的期望熵的降低()(,)()()vvv Value ASGain S AEntropy SEntropy SS举例Outlook Temperature Humidity Windy ClasssunnyhothighfalseNsunnyhothightrueNovercast hothighfalsePrainmildhighfalsePraincoolnormalfalsePraincoolnormaltrueNovercast coolnormaltruePsunnymildhighfalseNsunnycoo

25、lnormalfalsePrainmildnormalfalsePsunnymildnormaltruePovercast mildhightruePovercast hotnormalfalsePrainmildhightrueN计算信息增益(),Values WindWeak Strong9,5 S 6,2 WeakS3,3 StrongS,(,)()vvWeak StrongSGain S WindEntroy SEntropyS()(8/14)()(6/14)()WeakStrongEntropy SEntropy SEntropy S0.949(8/14)0.811(6/14)1.0

26、00.048确定最佳分类的属性哪一个属性是最好的分类？S:9+,5-E=0.940Humidity3+，4-E=0.9856+,1-E=0.592Gain(S,Humidity)=0.940-(7/14)0.985-(7/14)0.592S:9+,5-E=0.940Wind6+，2-E=0.8113+，3-E=1.000Gain(S,Wind)=0.940-(8/14)0.811-(6/14)0.100highnormalstrongweak不同属性的信息增益n计算各属性的熵值nGain(S,Outlook)=0.246nGain(S,Humidity)=0.151nGain(S,Wind)=

27、0.048nGain(S,Temperature)=0.029n可以看到，Outlook得信息增益最大D1,D2,D149+,5-OutlookSunnyD1,D2,D8,D9,D112+,3-RainD4,D5,D6,D10,D143+,2-D3,D7,D12,D134+,0-Overcast?哪一个属性在这里被测试？Ssunny=D1,D2,D8,D9,D11Gain（Ssunny,Humidity）=0.970-(3/5)0.0-(2/5)0.0=0.970Gain(Ssunny,Temperature)=0.970-(2/5)0.0-(2/5)1.0-(1/5)0.0=0.570Gai

28、n(Ssunny,Wind)=0.970-(2/5)1.0-(3/5)0.918=0.019?YesID3算法创建树的Root结点开始AAttributes中分类能力最好的属性Root的决策属性A对于每个可能值vi 在Root下加一个新的分支对应测试A=vi 令Examplesvi为Examples中满足A属性值为vi的子集 如果Examplesvi为空在这个新分支下加一个叶子结点，节点的lable=Examples中最普遍的目标属性值(target-attribute)否则在这个新分支下加一个子树ID3(examplevi,target-attribute,attributes-A)返回 R

29、ootC4.5nC4.5是对ID3的改进算法n对连续值的处理n对未知特征值的处理n对决策树进行剪枝n规则的派生决策树学习的常见问题n过度拟合数据n基本的决策树构造算法没有考虑噪声，生成的决策树完全与训练例子拟合n有噪声情况下，完全拟合将导致过分拟合（overfitting），即对训练数据的完全拟合反而不具有很好的预测性能 解决方法n剪枝是一种克服噪声的技术，同时它也能使树得到简化而变得更容易理解。n向前剪枝（forward pruning）n向后剪枝（backward pruning）n理论上讲，向后剪枝好于向前剪枝，但计算复杂度大。n剪枝过程中一般要涉及一些统计参数或阈值，如停机阈值n有人提

30、出了一种和统计参数无关的基于最小描述长度（MDL）的有效剪枝法 决策树的优点n可以生成可以理解的规则n计算量相对来说不是很大n可以处理连续和离散字段n决策树可以清晰的显示哪些字段比较重要n过程可见不足之处n对连续性的字段比较难预测n当类别太多时，错误可能会增加的比较快n一般的算法分类的时候，只是根据一个属性来分类。n不是全局最优文本分类的应用n新闻出版按照栏目分类n类别 政治,体育,军事,n网页分类n类似于Yahoo的分类n个性化新闻n智能推荐n垃圾邮件过滤n类别 spam,not-spam文本聚类Text Clustering聚类式搜索聚类式搜索聚类n将无标记的样本划分到聚类的各个子集中:n

31、类内样本非常相似n类间样本非常不同n无监督方法发现新类别.聚类样例.层次聚类n在无标注的样本集合中建立 树状层次分类结构n递归的标准层次聚类算法应用生成层次聚类.animalvertebratefish reptile amphib.mammal worm insect crustaceaninvertebrate会聚vs.分裂聚类n会聚(bottom-up)以每个样本独自一类开始，迭代合并到越来越大的类中n分裂(partitional,top-down)将所有样本不断划分到类别中会聚层次聚类(HAC)n设定相似度函数确定任意两个实例的相似度n开始每个实例独自一类n然后重复合并最相似的类别，直

32、到成为一类：n在当前的类别中，确定最近的两类ci 和cjn用单一的类别 ci cj取代 ci 和 cjn合并的过程成为层次结构聚类相似度n设定一个相似度函数确定两个实例的相似程度n文本向量的余弦相似度n如何计算包含多个样例的两个类别的相似度？nSingle Link:两个类别中最近成员的相似度nComplete Link:两个类别中最远成员的相似度nGroup Average:成员间的平均相似度计算复杂度n在第一次迭代中，HAC方法需要计算所有样例的每一对的距离n在合并迭代中，需要计算新形成的类与其他类的距离n为了维持O(n2)的性能，计算类与类之间的相似度需要常数时间计算类别间相似度n合并c

33、i,cj后，计算该类和其他类的相似度可以如下计算：nSingle Link:nComplete Link:),(),(max(),(kjkikjiccsimccsimcccsim),(),(min(),(kjkikjiccsimccsimcccsim平均连通凝聚聚类n单连通容易导致狭长聚类，全连通的算法复杂度为O(n3)n用合并后的类中所有对平均相似度度量两个类的相似度n是全连通和单连通的折中.)(:)(),()1(1),(jijiccxxyccyjijijiyxsimccccccsim计算平均连通相似度n设定余弦相似度及单位长度归一化向量.n总是维持每个类别的向量和.n计算类别相似度在常数时

34、间内:jcxjxcs)()()()()(|)(,)(|)(|1)ijijijijijijs cs cs cs cccsim c ccccc非层次聚类n需要确定期望的类别数kn随机选择k个种子 n进行初始聚类n迭代，将样例重新划分n直到样例所属的类别不再改变K-Meansn设定样例是一个实值向量n基于质心或类c中样本的均值聚类n根据样例与当前类别质心的相似度重新划分类别cxxc|1(c)距离矩阵n欧式距(L2 norm):nL1 norm:n余弦相似度(转换成距离):212)(),(imiiyxyxLmiiiyxyxL11),(yxyx1K-Means 算法令 d为两个实例的距离度量.选择 k

35、个随机样例s1,s2,sk 作为种子.直到聚类收敛或满足停止策略:对每个样例 xi:将 xi 分配到 cj，d(xi,sj)是最小的.(Update the seeds to the centroid of each cluster)对每个类 cj sj=(cj)K Means 举例(K=2)Pick seedsReassign clustersCompute centroidsxxReasssign clustersxxxxCompute centroidsReassign clustersConverged!种子的选择n聚类结果与随机种子的选择是相关的n随机选择的种子可能会导致收敛很慢或者

36、收敛到局部最优n采用启发式方法或其他方法选择好的种子Buckshot 算法n层次聚类和 K-均值n首先随机选择n1/2 大小的语料n在这些样例上运行HAC n利用HAC的结果做为K-均值的种子n该方法避免了不良种子的选取文本聚类nHAC 和 K-Means可以直接应用于文本中.n典型的使用归一化、基于TF/IDF权重的向量以及余弦相似度.n应用:n在检索阶段，加入同一类别的其他文本作为初始检索结果，提高召回率.n检索结果进行聚类，可以提供给用户更好的组织形式n自动生成的层次聚类结果为用户提供方便，根据聚类结果生成文摘等半监督学习n对于有监督的分类，生成标注的训练语料代价很大.nIdea:用无标

37、记的数据帮助有监督分类.n通过用标注和未标注的语料训练EM，在半监督模式中应用.n用已标注的数据子集训练初始的模型.n用户已标注的数据在迭代过程中不再改变.n无指导的数据标注在迭代过程中被重新标注.半监督学习举例n假设“quantum”出现在标为物理的文档中，但是“Heisenberg”（海森堡）没有出现在标注的数据中.n从标注的数据中学到“quantum”是物理文档的标示.n标注无监督数据时，将出现“quantum”和“Heisenberg”的文档标为物理类.n在进行训练时，可以学到“Heisenberg”也是物理类文档的标示.n最后学到的模型可以正确地将仅包含“Heisenberg”的文档划为物理类.本章小结n介绍了文本分类和聚类的概念n介绍了几种特征提取的方法n介绍了贝叶斯，KNN及决策树分类方法n介绍了层次聚类和非层次聚类的方法