第六章文本分类与聚类

1、文本分类与聚类这一部分将讲述这一部分将讲述n文本分类及聚类的概念文本分类及聚类的概念n文本特征的提取方法文本特征的提取方法n贝叶斯分类，贝叶斯分类，KNNKNN分类分类n层次聚类的方法层次聚类的方法文本分类概述文本分类概述概述概述n文本分类包括普通文本分类和网页文本分类文本分类包括普通文本分类和网页文本分类n中文网页分类技术已经成为中文信息处理领中文网页分类技术已经成为中文信息处理领域的一项基础性工作域的一项基础性工作n网页分类可以为搜索引擎用户提供目录导航网页分类可以为搜索引擎用户提供目录导航服务，进而提高系统查准率服务，进而提高系统查准率n网页分类可以为个性化搜索引擎奠定基础网页分类可以为

2、个性化搜索引擎奠定基础5引言引言n物以类聚、人以群分物以类聚、人以群分n相似的对象总聚集在一起相似的对象总聚集在一起n根据聚集情况可以对新的对象进行划分根据聚集情况可以对新的对象进行划分n分类分类/ /聚类的根本原因就是因为对象数目太多，处理困难聚类的根本原因就是因为对象数目太多，处理困难n一些信息处理部门，一个工作人员一天要看上千份信息一些信息处理部门，一个工作人员一天要看上千份信息n分门别类将会大大减少处理难度分门别类将会大大减少处理难度n分类是非常普遍的一种处理手段分类是非常普遍的一种处理手段n性别、籍贯、民族、学历、年龄等等，我们每个人身上贴满了性别、籍贯、民族、学历、年龄等等，我们每

3、个人身上贴满了“标签标签”n我们从孩提开始就具有分类能力：电影中的好人、坏人；好阿姨、坏我们从孩提开始就具有分类能力：电影中的好人、坏人；好阿姨、坏阿姨；亲人、非亲人等等。阿姨；亲人、非亲人等等。n分类无处不在，从现在开始，我们可以以分类的眼光看世界分类无处不在，从现在开始，我们可以以分类的眼光看世界 6分类和聚类的例子分类和聚类的例子n分类的例子：分类的例子：n在新街口马路上碰到一个人，判断他在新街口马路上碰到一个人，判断他/ /她是不是学生？她是不是学生？n根据某些特征给对象贴一个根据某些特征给对象贴一个“标签标签”。n聚类的例子：聚类的例子：n去综合楼一个大教室上自习，往往发现大家三三两

4、两扎去综合楼一个大教室上自习，往往发现大家三三两两扎推地坐，一打听，原来坐在一块的大都是一个班的。推地坐，一打听，原来坐在一块的大都是一个班的。n事先不知道事先不知道“标签标签”，根据对象之间的相似情况进行成，根据对象之间的相似情况进行成团分析。团分析。分类的概念分类的概念n给定给定: :n一个实例的描述一个实例的描述, , x x X X, X, X是实例空间是实例空间n一个固定的文本分类体系一个固定的文本分类体系: : C=C= c c1 1, , c c2 2, ,c cn n n由于类别是事先定义好的，因此分类是有指由于类别是事先定义好的，因此分类是有指导的（或者说是有监督的）导的（或

5、者说是有监督的）n确定确定: :n实例实例x x的类别的类别 c c( (x x) ) C C, , c c( (x x) ) 是一个分类函数，是一个分类函数，定义域是定义域是 X X ，值域是，值域是C C8文本分类的定义文本分类的定义n事先给定分类体系和训练样例事先给定分类体系和训练样例( (标注好类别标注好类别信息的文本信息的文本) )，将文本分到某个或者某几个，将文本分到某个或者某几个类别中。类别中。n计算机自动分类，就是根据已经标注好类别信计算机自动分类，就是根据已经标注好类别信息的训练集合进行学习，将学习到的规律用于息的训练集合进行学习，将学习到的规律用于新样本新样本( (也叫测试

6、样本也叫测试样本) )的类别判定。的类别判定。n分类是有监督分类是有监督/ /指导学习指导学习(Supervised Learning)(Supervised Learning)的的一种。一种。文本分类的模式文本分类的模式n从类别数目来分从类别数目来分n2 2类问题，属于或不属于类问题，属于或不属于(binary)(binary)n多类问题，多个类别多类问题，多个类别(multi-class)(multi-class)，可拆分成，可拆分成2 2类问题类问题n一个文本可以属于多类一个文本可以属于多类(multi-label)(multi-label)n从是否兼类看分从是否兼类看分n单标签单标签(

7、single label)(single label)问题：一个文本只属于一个类问题：一个文本只属于一个类n多标签多标签(multi-label)(multi-label)问题：一个文本可以属于多类，即出问题：一个文本可以属于多类，即出现兼类现象现兼类现象10关于分类体系关于分类体系n分类体系的构建标准可以是按照语义分类体系的构建标准可以是按照语义( (如：政治、如：政治、经济、军事经济、军事)，也可以是按照其他标准，也可以是按照其他标准( (如：垃圾如：垃圾vs. vs. 非垃圾；游戏网站非垃圾；游戏网站vs. vs. 非游戏网站非游戏网站) )，完全取决，完全取决于目标应用的需求。于目标应

8、用的需求。n分类体系一般由人工构造，可以是层次结构。分类体系一般由人工构造，可以是层次结构。n一些分类体系一些分类体系: Reuters: Reuters语料分类体系、中图分类、语料分类体系、中图分类、Yahoo Yahoo ！分类目录。！分类目录。11训练语料分类体系训练语料分类体系n中图分类体系中图分类体系n处理对象是图书，不适合网页分类处理对象是图书，不适合网页分类n学科分类与代码学科分类与代码n19921992年制定，时间过久，包括一些过时类别年制定，时间过久，包括一些过时类别n上述两个分类标准都不能直接用做中文上述两个分类标准都不能直接用做中文网页的分类网页的分类n中文网页的分类体系

9、中文网页的分类体系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类

10、电工技术 TN类 无线电电子学、电信技术 TP类 自动化技术、计算技术 TQ类 化学工业 TS类 轻工业、手工业 TU类 建筑科学 TV类 水利工程 中图分类法中图分类法13一种中文网页的分类体系 系统结构标注工具模型数据标注的样本类别预处理预处理训练数据文本新数据文本15文本分类的应用文本分类的应用n垃圾邮件的判定垃圾邮件的判定(spam or not spam)(spam or not spam)n类别类别spam, not-spamspam, not-spamn新闻出版按照栏目分类新闻出版按照栏目分类n类别类别 政治政治, ,体育体育, ,军事军事,n词性标注词性标注n类别类别 名词名词

11、, ,动词动词, ,形容词形容词,n词义排歧词义排歧n类别类别 词义词义1, 1,词义词义2,2,16文本分类的过程（文本分类的过程（1 1）n获取训练文档集合获取训练文档集合 n训练训练(training)(training)：即从训练样本中学习分类的规律。：即从训练样本中学习分类的规律。n测试测试(test(test或分类或分类classification)classification)：根据学习到的规律对新来：根据学习到的规律对新来的文本进行类别判定。的文本进行类别判定。n建立文档表示模型建立文档表示模型 n目前的文本分类系统，绝大多数都是以词语来表征文档目前的文本分类系统，绝大多数都是

12、以词语来表征文档的，用关键词、短语、主题词、概念的都有。的，用关键词、短语、主题词、概念的都有。17文本分类的过程（文本分类的过程（2 2）n特征选择特征选择n不管是训练还是测试，都要先分析出文本的某些特征不管是训练还是测试，都要先分析出文本的某些特征(feature(feature，也称为标引项，也称为标引项term)term)，然后把文本变成这些特，然后把文本变成这些特征的某种适宜处理的表示形式，通常都采用向量表示形征的某种适宜处理的表示形式，通常都采用向量表示形式或者直接使用某些统计量。式或者直接使用某些统计量。n选择或设计分类模型选择或设计分类模型n建立从文档特征（或属性）到文档类别的

13、映射关系，是建立从文档特征（或属性）到文档类别的映射关系，是文本分类的核心问题。现有的分类方法主要来自两个方文本分类的核心问题。现有的分类方法主要来自两个方面：统计和机器学习，比较著名的文档分类方法有面：统计和机器学习，比较著名的文档分类方法有kNNkNN、Nave Nave BayesBayes（NBNB）、）、SVMSVM等等。等等。 18文本分类的过程（文本分类的过程（3 3）n性能评测模型性能评测模型 n性能评测是分类处理流程中的重要一环。对改进和性能评测是分类处理流程中的重要一环。对改进和完善分类系统具有指导意义。完善分类系统具有指导意义。 19文本分类的方法文本分类的方法n人工方法

14、：人工总结规则人工方法：人工总结规则n优点：优点：n结果容易理解：如足球结果容易理解：如足球and and 联赛联赛体育类体育类n缺点：缺点：n费时费力费时费力n难以保证一致性和准确性难以保证一致性和准确性(40%(40%左右的准确率左右的准确率) )n专家有时候凭空想象，没有基于真实语料的分布专家有时候凭空想象，没有基于真实语料的分布n代表方法：人们曾经通过知识工程的方法建立专家系统代表方法：人们曾经通过知识工程的方法建立专家系统(80(80年代末期年代末期) )用于分类。用于分类。n自动的方法自动的方法( (学习学习) )：从训练语料中学习规则：从训练语料中学习规则n优点：优点：n快速快速

15、n准确率相对高准确率相对高( (准确率可达准确率可达60%60%或者更高或者更高) )n来源于真实文本，可信度高来源于真实文本，可信度高n缺点：缺点：n结果可能不易理解结果可能不易理解( (比如有时是一个复杂的数学表达式比如有时是一个复杂的数学表达式) )20规则方法和统计方法规则方法和统计方法n规则方法通过得到某些规则来指导分类，而这些规则往往是人规则方法通过得到某些规则来指导分类，而这些规则往往是人可以理解的。可以理解的。n统计方法通过计算得到一些数学表达式来指导分类。统计方法通过计算得到一些数学表达式来指导分类。n规则方法和统计方法没有本质的区别，它们都是想得到某种规规则方法和统计方法没

16、有本质的区别，它们都是想得到某种规律性的东西来指导分类，统计方法得到的数学表达式可以认为律性的东西来指导分类，统计方法得到的数学表达式可以认为是某种隐式规则。是某种隐式规则。n在目前的文本分类当中，统计方法占据了主流地位。在目前的文本分类当中，统计方法占据了主流地位。分类的评测分类的评测n偶然事件表（偶然事件表（Contingency TableContingency Table）n对一个分类器的度量对一个分类器的度量n准确率准确率(precision) = a / (a + b)(precision) = a / (a + b)n召回率召回率(recall) = a / (a + c)(re

17、call) = a / (a + c)nfallout = b / (b + d)fallout = b / (b + d)属于此类不属于此类判定属于此类AB判定不属于此类CDBEPBEP和和F F测度测度nBEPBEP（break-even pointbreak-even point）n当准确率和召回率相等时的值即为当准确率和召回率相等时的值即为BEPBEPnF F测度，取测度，取=1 =1 nBEPBEP和和F F测度的值越大，则表示分类器的性能越测度的值越大，则表示分类器的性能越好。好。nBEPBEP只是只是F1F1所有可能取值中的一个特定值（当所有可能取值中的一个特定值（当p p =

18、r= r时），因此时），因此BEPBEP小于或等于小于或等于F1F1的最大值。的最大值。rpprrpF221,rpprF21多类分类问题的评价多类分类问题的评价n宏平均（宏平均（macro-averagingmacro-averaging）n先对每个分类器计算上述量度，再对所有分先对每个分类器计算上述量度，再对所有分类器求平均类器求平均n是关于类别的均值是关于类别的均值n微平均（微平均（micro-averagingmicro-averaging）n先合并所有分类器的偶然事件表中的各元素，先合并所有分类器的偶然事件表中的各元素，得到一个总的偶然事件表，再由此表计算各得到一个总的偶然事件表，再由

19、此表计算各种量度。种量度。n是关于文本的均值是关于文本的均值收集训练数据收集训练数据nTRECTREC提供统一的训练集和测试集进行系提供统一的训练集和测试集进行系统评测统评测n国外：国外：CMU,BERKLEY,CORNELLCMU,BERKLEY,CORNELLn国内：中科院计算所，清华大学，复旦大学国内：中科院计算所，清华大学，复旦大学n后续增加了网页语料和中文文本后续增加了网页语料和中文文本n但是中文文本是新华社的新闻稿，与网页的但是中文文本是新华社的新闻稿，与网页的分类体系还有差别分类体系还有差别目前已有的评测语料目前已有的评测语料n有指导的机器学习方法是实现中文网页有指导的机器学习方

20、法是实现中文网页自动分类的基础，因此训练集是实现分自动分类的基础，因此训练集是实现分类的前提条件类的前提条件n已有训练语料已有训练语料n863863评测语料评测语料( (中图分类中图分类) )n搜狗语料搜狗语料n复旦语料复旦语料训练集的大小训练集的大小n通过不断增加实例的个数，考察每个类训练样通过不断增加实例的个数，考察每个类训练样本对分类器质量的影响本对分类器质量的影响 宏观F1 微观F1特征提取特征提取特征提取特征提取(Feature Selection)(Feature Selection)n在文本分类问题中遇到的一个主要困难就是高维在文本分类问题中遇到的一个主要困难就是高维的特征空间的

21、特征空间n通常一份普通的文本在经过文本表示后，如果以词为特通常一份普通的文本在经过文本表示后，如果以词为特征，它的特征空间维数将达到几千，甚至几万征，它的特征空间维数将达到几千，甚至几万n大多数学习算法都无法处理如此大的维数大多数学习算法都无法处理如此大的维数n在不牺牲分类质量的前提下尽可能降低特征空间在不牺牲分类质量的前提下尽可能降低特征空间的维数的维数n特征选取的任务将信息量小，不重要的词汇从特特征选取的任务将信息量小，不重要的词汇从特征空间中删除，减少特征项的个数征空间中删除，减少特征项的个数n在许多文本分类系统的实现中都引入了特征提取在许多文本分类系统的实现中都引入了特征提取方法方法特

22、征选择举例特征选择举例n对每类构造对每类构造k k 个最有区别能力的个最有区别能力的termtermn例如：例如：n计算机领域计算机领域：n主机、芯片、内存、编译主机、芯片、内存、编译 n汽车领域汽车领域: : n轮胎，方向盘，底盘，气缸，轮胎，方向盘，底盘，气缸，用文档频率选特征用文档频率选特征n文档频率文档频率nDF (Document Frequency)DF (Document Frequency)nDFiDFi：所有文档集合中出现特征：所有文档集合中出现特征i i的文档数目的文档数目n基本假设：稀少的词或者对于目录预测没有帮基本假设：稀少的词或者对于目录预测没有帮助，或者不会影响整体

23、性能。助，或者不会影响整体性能。n实现方法：先计算所有词的实现方法：先计算所有词的DFDF，然后删除所有，然后删除所有DFDF小于某个阈值的词，从而降低特征空间的维小于某个阈值的词，从而降低特征空间的维数。数。n优缺点：优缺点：n最简单的降低特征空间维数的方法最简单的降低特征空间维数的方法n稀少的词具有更多的信息，因此不宜用稀少的词具有更多的信息，因此不宜用DFDF大幅度地大幅度地删除词删除词词的熵词的熵ntermterm的熵的熵n该值越大，说明分布越均匀，越有可能出现在该值越大，说明分布越均匀，越有可能出现在较多的类别中；较多的类别中；n该值越小，说明分布越倾斜，词可能出现在较该值越小，说明

24、分布越倾斜，词可能出现在较少的类别中少的类别中iiitcPtcPtEntropy)|(log)|()(信息增益信息增益(Information Gain, IG)(Information Gain, IG)iiririrriiririrrcPtcPtcPtPcPtcPtcPtPtG)()|(log)|()()()|(log)|()()(t 出现的概率 t 不出现假定t 出现时取第i 个类别的概率 取第 i 个类别时的概率n该该termterm为整个分类所能提供的信息量为整个分类所能提供的信息量n不考虑任何特征的熵和考虑该特征后的熵的差值不考虑任何特征的熵和考虑该特征后的熵的差值n信息增益计算的

25、是已知一个词信息增益计算的是已知一个词t t是否出现在一份文本中对于是否出现在一份文本中对于类别预测有多少信息。类别预测有多少信息。n这里的定义是一个更一般的、针对多个类别的定义。这里的定义是一个更一般的、针对多个类别的定义。互信息（互信息（Mutual InformationMutual Information）n互信息互信息(Mutual Information)(Mutual Information)：MIMI越大越大t t和和c c共共现程度越大现程度越大n互信息的定义与交叉熵近似，只是互信息不互信息的定义与交叉熵近似，只是互信息不考虑考虑t t不出现的概率，它的定义为：不出现的概率，

26、它的定义为：1( )max( ,)mMAXiiItI t cmiiiAVGctIcPtI1),()()(iririrtPctPcPtI)()|(log)()( 2 2统计量（统计量（CHICHI）：）：n 2 2统计量的定义可以从一个词统计量的定义可以从一个词t t与一个类别与一个类别c c的的偶然事件表引出（假设文本的总数为偶然事件表引出（假设文本的总数为N N ）n度量两者度量两者(term(term和类别和类别) )独立性程度独立性程度n 2 2 越大，独立性越小，相关性越大越大，独立性越小，相关性越大n若若ADBC,ADBC,则类和词独立则类和词独立, N=A+B+C+D, N=A+B

27、+C+DABCDttcc)()()()(),(22DCBADBCACBADNct特征提取方法的性能比较特征提取方法的性能比较(Macro-F1)(Macro-F1)特征提取方法的性能比较特征提取方法的性能比较(Micro-F1)(Micro-F1)结论结论n可以看出可以看出CHICHI，IGIG，DFDF性能好于性能好于MIMInMIMI最差最差nCHICHI，IGIG，DFDF性能相当性能相当nDFDF具有算法简单，质量高的优点，可以具有算法简单，质量高的优点，可以替代替代CHICHI，IGIG分类器学习分类器学习n训练样本实例：训练样本实例：)n一个文本实例一个文本实例 x x X Xn带

28、有正确的类别标记带有正确的类别标记 c c( (x x) )n学习的过程是在给定训练样本集合学习的过程是在给定训练样本集合D D 的的前提下，寻找一个分类函数前提下，寻找一个分类函数h h( (x x), ), 使得使得: :)()(: )(,xcxhDxcx贝叶斯分类贝叶斯分类贝叶斯分类贝叶斯分类n基于概率理论的学习和分类方法基于概率理论的学习和分类方法n贝叶斯理论在概率学习及分类中充当重贝叶斯理论在概率学习及分类中充当重要角色要角色n仅使用每类的先验概率不能对仅使用每类的先验概率不能对待分的文待分的文本本提供信息提供信息n分类是根据给定样本描述的可能的类别分类是根据给定样本描述的可能的类别

29、基础上产生的后验概率分布基础上产生的后验概率分布41贝叶斯分类的基本思想贝叶斯分类的基本思想nNave Nave BayesBayes分类方法（以下简称分类方法（以下简称NBNB法）将概法）将概率模型应用于自动分类，是一种简单而又有效率模型应用于自动分类，是一种简单而又有效的分类方法。的分类方法。n它的分类思想是使用贝叶斯公式，通过先验概它的分类思想是使用贝叶斯公式，通过先验概率和类别的条件概率来估计文档率和类别的条件概率来估计文档d d对类别对类别ci ci的后的后验概率，以此实现对文档验概率，以此实现对文档d d的类别归属判断。的类别归属判断。42Bayes Rule贝叶斯分类贝叶斯分类n

30、设各个类别的集合为设各个类别的集合为 c c1 1, , c c2 2, ,c cn n n设设E E为实例的描述为实例的描述n确定确定E E的类别的类别nP(P(E E) ) 可以根据下式确定可以根据下式确定)()|()()|(EPcEPcPEcPiiiniiiniiEPcEPcPEcP111)()|()()|(niiicEPcPEP1)|()()(贝叶斯分类贝叶斯分类(cont.)(cont.)n需要知道需要知道: :n先验概率先验概率: : P(P(c ci i) ) n条件概率条件概率: P(: P(E E | | c ci i) )nP(P(c ci i) ) 容易从数据中获得容易从

31、数据中获得n如果文档集合如果文档集合D D中，属于中，属于c ci i的样例数为的样例数为 n ni in则有则有P(P(c ci i) = ) = n ni i / |/ |D D| |朴素的贝叶斯分类朴素的贝叶斯分类n如果假定样例的特征是独立的，可以写为：如果假定样例的特征是独立的，可以写为：n因此，只需要知道每个特征和类别的因此，只需要知道每个特征和类别的P(P(e ej j | | c ci i) ) n如果只计算单个特征的分布，大大地减少了如果只计算单个特征的分布，大大地减少了计算量计算量)|()|()|(121mjijimicePceeePcEP文本分类文本分类 NaNa ve v

32、e BayesBayes算法算法( (训练训练) )设设V V为文档集合为文档集合D D所有词词表所有词词表对每个类别对每个类别 c ci i C C D Di i 是文档是文档D D中类别中类别C Ci i的文档集合的文档集合 P(P(c ci i) = |) = |D Di i| / | / |D D| |设设 n ni i 为为D Di i中词的总数中词的总数 对每个词对每个词 wwj j V V 令令 n nij ij 为为D Di i中中wwij ij的数量的数量 P(P(wwi i | | c ci i) = () = (n nij ij+ 1) / (+ 1) / (n ni i

33、 + |+ |V V |)|)47文本分类文本分类 NaNa ve ve BayesBayes算法算法( (测试测试) )n给定测试文档给定测试文档 X Xn设设 n n 为为X X中词的个数中词的个数n返回的类别返回的类别: :nwwi i是是X X中第中第i i个位置的词个位置的词)|()(argmax1niiiiCiccwPcPNaNa ve ve BayesBayes分类举例分类举例nC = allergy, cold, wellne1 = sneeze; e2 = cough; e3 = fevern当前实例是：E = sneeze, cough, feverProbWellCold

34、AllergyP(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过敏打喷嚏NaNa ve ve BayesBayes 举例举例 (cont.)(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.6)/P(E)=0.

35、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 hothighfalsePrainmildhighfalsePraincoolnormalfalsePraincoolnormaltrueN

36、overcast coolnormaltruePsunnymildhighfalseNsunnycoolnormalfalsePrainmildnormalfalsePsunnymildnormaltruePovercast 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/5temper

37、atureP(hot|p) = 2/9P(hot|n) = 2/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

38、|p)P(false|p)P(p) = 3/92/93/96/99/14 = 0.010582nP(X|n)P(n) = P(rain|n)P(hot|n)P(high|n)P(false|n)P(n) = 2/52/54/52/55/14 = 0.018286n样本 X 被分到 n类，即“不适合打网球”讨论讨论n朴素的贝叶斯假定在一个位置上出现的词的概朴素的贝叶斯假定在一个位置上出现的词的概率独立于另外一个位置的单词，这个假定有时率独立于另外一个位置的单词，这个假定有时并不反映真实情况并不反映真实情况n虽然独立性假设很不精确，别无选择，否则计虽然独立性假设很不精确，别无选择，否则计算的概率项

39、将极为庞大算的概率项将极为庞大n幸运的是，在实践中朴素贝叶斯学习器在许多幸运的是，在实践中朴素贝叶斯学习器在许多文本分类中性能非常好，即使独立性假设不成文本分类中性能非常好，即使独立性假设不成立立K K近邻近邻 K K近邻（近邻（KNNKNN）n基本思想基本思想n给定一个经过分类的训练文档集合，在对新文档给定一个经过分类的训练文档集合，在对新文档（即测试文档或待分类文档）进行分类时，首先从（即测试文档或待分类文档）进行分类时，首先从训练文档集合中找出与测试文档最相关的训练文档集合中找出与测试文档最相关的k k篇文档，篇文档，然后按照这然后按照这k k篇文档所属的类别信息来对该测试文篇文档所属的

40、类别信息来对该测试文档进行分类处理。档进行分类处理。57文档间的距离文档间的距离n对于有对于有mm个特征属性的文档来说，个特征属性的文档来说，n n个文档可以视为个文档可以视为m-m-维维空间中的空间中的n n个点，自然地，可以设想用点间距离度量文档个点，自然地，可以设想用点间距离度量文档间的接近程度。常用间的接近程度。常用dijdij表示第表示第i i篇文档与第篇文档与第j j篇文档间的距篇文档间的距离。离。n n当当q q分别取分别取1 1，2 2和和时，明氏距离分别对应于绝对值距离时，明氏距离分别对应于绝对值距离、欧氏距离和切比雪夫距离。、欧氏距离和切比雪夫距离。qmkqjkikijww

41、qd11)()(KNNKNN算法算法n目标：基于训练集目标：基于训练集X X的对的对y y分类分类n在训练集中，寻找和在训练集中，寻找和y y最相似的训练样本最相似的训练样本x xn得到得到k k个最相似的集合个最相似的集合A,AA,A为为X X的一个子集的一个子集n设设n1,n2n1,n2分别为集合中属于分别为集合中属于c1,c2c1,c2的个数的个数n如果如果p(c1|y)p(c2|y),p(c1|y)p(c2|y),判为判为c1,c1,否则判为否则判为c2c2( )( , )MAXx NsimyMAXsim x ymax|( , )( )AxN sim x ysimy11(| )12np

42、 cynn22(| )12np cynnkNNkNN方法方法n一种基于实例的学习方法一种基于实例的学习方法新文本k=1, A类k=4，B类k=10，B类带权重计算，计算权重和最大的类。带权重计算，计算权重和最大的类。k k常取常取3 3或者或者5 5。KNNnkNNkNN分类法其分类法其优点优点不需要预先学习，分类精度不需要预先学习，分类精度较高，不存在漏识问题较高，不存在漏识问题n缺点缺点是分类速度与训练文档个数有关。对于每是分类速度与训练文档个数有关。对于每一个测试文档，都必须求解它与训练文档库中一个测试文档，都必须求解它与训练文档库中所有文档的相似度，其时间复杂度为所有文档的相似度，其时

43、间复杂度为OO（n1n1* *n2n2）。）。 相似度矩阵相似度矩阵n最近邻方法依赖于相似度矩阵最近邻方法依赖于相似度矩阵( (或距离或距离). ).n对连续对连续mm维空间最简单的方法采用欧氏距维空间最简单的方法采用欧氏距. .n对对mm维二值实例空间最简单的方法是海明维二值实例空间最简单的方法是海明距（绝对距离）距（绝对距离）. .n对于基于文本对于基于文本tf/idftf/idf权重向量的余弦相似度权重向量的余弦相似度是经常被采用的是经常被采用的. .影响影响KNNKNN的因素的因素nK K的取值的取值nK K一般取一般取1515n计算距离的方法计算距离的方法n欧式距离欧式距离n兰式距离

44、（余弦相似度），分类质量和分类效率较兰式距离（余弦相似度），分类质量和分类效率较高高n分类目录中类别的层次关系分类目录中类别的层次关系n基于层次模型的基于层次模型的KNNKNN分类比基本的分类比基本的KNNKNN效率高，效率高，但是效率也会有所下降但是效率也会有所下降KNNKNN和和NBNB比较比较n从表中看，从表中看，KNNKNN质量较高，质量较高，NBNB的效率较高的效率较高n从各个类别看，从各个类别看，KNNKNN比比NBNB稳定，稳定，NBNB对类别敏对类别敏感感文本聚类文本聚类Text Clustering聚类式搜索聚类式搜索聚类聚类n目的：目的：n发现与某文档相似的一批文档，发现相

45、关知识；发现与某文档相似的一批文档，发现相关知识； n导航，提供一种组织文档集合的方法导航，提供一种组织文档集合的方法 ；n生成用于文本自动分类的分类体系表生成用于文本自动分类的分类体系表 。n将无标记的样本划分到聚类的各个子集中将无标记的样本划分到聚类的各个子集中: :n类内样本非常相似类内样本非常相似n类间样本非常不同类间样本非常不同n无监督方法发现新类别无监督方法发现新类别.聚类样例聚类样例.层次聚类层次聚类n在无标注的样本集合中建立在无标注的样本集合中建立 树状层次分类结构树状层次分类结构n递归的标准层次聚类算法应用生成层次聚类递归的标准层次聚类算法应用生成层次聚类. .animalv

46、ertebratefish reptile amphib. mammal worm insect crustaceaninvertebrate会聚会聚vs. vs. 分裂聚类分裂聚类n会聚会聚( (bottom-upbottom-up) ) 以每个样本独自一类开以每个样本独自一类开始，迭代合并到越来越大的类中始，迭代合并到越来越大的类中n分裂分裂 ( (partitionalpartitional, top-down, top-down) ) 将所有样本将所有样本不断划分到类别中不断划分到类别中n不需要事先确定类别不需要事先确定类别n需要终止条件需要终止条件会聚层次聚类会聚层次聚类 (HAC)

47、(HAC)n设定相似度函数确定任意两个实例的相似度设定相似度函数确定任意两个实例的相似度n开始每个实例独自一类开始每个实例独自一类n然后重复合并最相似的类别，直到成为一类：然后重复合并最相似的类别，直到成为一类：n在当前的类别中，确定最近的两类在当前的类别中，确定最近的两类ci ci 和和cj cjn用单一的类别用单一的类别 ci ci cj cj取代取代 ci ci 和和 cj cjn合并的过程成为层次结构合并的过程成为层次结构系统树图系统树图: :d1d2d3d4d5d1,d2d4,d5d3d3,d4,d5 聚类相似度聚类相似度n设定一个相似度函数确定两个实例的相似程度设定一个相似度函数确

48、定两个实例的相似程度n文本向量的余弦相似度文本向量的余弦相似度n如何计算包含多个样例的两个类别的相似度？如何计算包含多个样例的两个类别的相似度？nSingle LinkSingle Link: : 两个类别中最近成员的相似度两个类别中最近成员的相似度nComplete LinkComplete Link: : 两个类别中最远成员的相似度两个类别中最远成员的相似度nGroup AverageGroup Average: : 成员间的平均相似度成员间的平均相似度计算类别间相似度计算类别间相似度n合并合并c ci i,c ,cj j后，计算该类和其他类的相似度后，计算该类和其他类的相似度可以如下计算

49、：可以如下计算：nSingle Link:Single Link:nComplete Link:Complete Link:),(),(max(),(kjkikjiccsimccsimcccsim),(),(min(),(kjkikjiccsimccsimcccsim单连通（单连通（Single LinkageSingle Linkage）全连通（全连通（Complete LinkageComplete Linkage）平均连通（平均连通（Average LinkageAverage Linkage） 计算复杂度计算复杂度n在第一次迭代中，在第一次迭代中，HACHAC方法需要计算所方法需要计算

50、所有样例的每一对的距离有样例的每一对的距离n在合并迭代中，需要计算新形成的类与在合并迭代中，需要计算新形成的类与其他类的距离其他类的距离n为了维持为了维持O(nO(n2 2) )的性能，计算类与类之间的性能，计算类与类之间的相似度需要的相似度需要常数时间常数时间平均连通凝聚聚类平均连通凝聚聚类n单连通容易导致狭长聚类，全连通的算单连通容易导致狭长聚类，全连通的算法复杂度为法复杂度为O(nO(n3 3) )n用合并后的类中所有对平均相似度度量用合并后的类中所有对平均相似度度量两个类的相似度两个类的相似度n是全连通和单连通的折中是全连通和单连通的折中. .)(: )(),() 1(1),(jiji

51、ccxxyccyjijijiyxsimccccccsim计算平均连通相似度计算平均连通相似度n设定余弦相似度及单位长度归一化向量设定余弦相似度及单位长度归一化向量. .n总是维持每个类别的向量和总是维持每个类别的向量和. .n计算类别相似度在常数时间内计算类别相似度在常数时间内: :jcxjxcs)( ( )() ( ( )()(|)( ,)(|)(| 1)ijijijijijijs cs cs cs cccsim c ccccc非层次聚类非层次聚类(动态聚类动态聚类)n需要确定期望的类别数需要确定期望的类别数k kn随机选择随机选择k k个种子个种子 n进行初始聚类进行初始聚类n迭代，将样例

52、重新划分迭代，将样例重新划分n直到样例所属的类别不再改变直到样例所属的类别不再改变82动态聚类的核心问题n初始聚类中心的选取初始聚类中心的选取n重心法重心法n密度法密度法n调用等级聚类算法调用等级聚类算法n参数参数K K的设置的设置聚类中心的选择聚类中心的选择n聚类结果与聚类中心的选择是相关的聚类结果与聚类中心的选择是相关的n随机选择的聚类中心可能会导致收敛很随机选择的聚类中心可能会导致收敛很慢或者收敛到局部最优慢或者收敛到局部最优n采用启发式方法或其他方法选择好的聚采用启发式方法或其他方法选择好的聚类中心类中心84重心法n首先计算出全部聚类样本的重心，把它作为第一凝聚点；首先计算出全部聚类样

53、本的重心，把它作为第一凝聚点；n再选定一个正数，作为建立新凝聚点的最小临界距离再选定一个正数，作为建立新凝聚点的最小临界距离d d；n依次逐个输入全部样本，如果输入样本与已有凝聚点的距依次逐个输入全部样本，如果输入样本与已有凝聚点的距离大于离大于d d，则将它作为新凝聚点，否则就不作为凝聚点；，则将它作为新凝聚点，否则就不作为凝聚点；n直到把所有样本处理完毕。直到把所有样本处理完毕。85密度法密度法n先选定两个正数先选定两个正数d1d1和和d2d2，然后，以样本空间的每个样本点为，然后，以样本空间的每个样本点为中心，以中心，以d1d1为半径做超维球，落在该球内的样本数（不包括为半径做超维球，落在该球内的样本数（不包括中心样本在内）就称为该