第11章--信息分类与聚类ppt课件

第11章 信息分类与聚类第11章 信息分类与聚类 11.1 基本知识 第11章.ppt特征描述及提取 11.3 聚类方法 11.4 分类方法 11.5 方法评测 11.6 小结 思考题第11章 信息分类与聚类 11.1 基本知识第11章 信息分类与聚类11.1 基本知识基本知识信息分类是指将对象分到类别集合中去的过程。如果类别集合是事先给定，对训练集中的对象给出类别标识，则称为有监督的分类(通常所说的分类)。如果类别不是事先给定，而是在操作过程中生成，则称为无监督的分类(通常称为聚类)。无论是聚类还是分类，都涉及“类”的概念。如何认识和定义“类”的概念，如何对类的特征进行描述，是信息自动处理的首要问题。11.1 基本知识信息分类是指将对象分到第11章 信息分类与聚类11.1.1 类的概念类的概念在信息聚类和分类中，类是一个核心概念。如何认识类，定义类，描述类等是聚类和分类的基础。只有认识了什么是类，了解了如何抽取描述类的特征，才能熟悉信息聚类与分类的本质所在。直观而言，类是相似物体的集合。我们通常谈及“车”，其实可以看成是谈及“车”这样一个类。“车”类可能包括汽车、自行车、摩托车和火车等元素。“车”类中的这些元素都有一些共同的特征，都有轮子，都可以移动等。除了相似性之外，“车”类的各元素之间也有不同的地方，比如轮子数目的不同，动力源的差异等。信息聚类和分类的目的就是根据各个元素的一个特征信息，应用机器学习的方法1，将这些元素划分到不同的类中。11.1.1 类的概念在信息聚类和分类中，类是一个核第11章 信息分类与聚类11.1.2 对象特征描述对象特征描述对象的形式化表示是一个基本的，而又非常重要的问题。首先要将对象从无结构的原始形式转化为计算机能够理解的结构化形式，然后才能进行分析与处理。常见的对象表示模型有向量空间模型、概率模型和语言模型等。其中最常用的是向量空间模型(VSM)。向量空间模型以特征项作为对象表示的基本单位，特征项可以由字、词、短语、颜色、纹理等组成。每一个对象Oi被看成是由特征项组成的n维特征空间的一个向量Wi，Wi=(t1，wi1;t2，wi2;tj，wij)，其中wij为第j个特征项tj在对象Oi中的权重。类通常具有质量、直径等性质，设类S有n个对象，这n个对象的特征抽象成n个向量W1，W2，Wn，则：11.1.2 对象特征描述对象的形式化表示是一个基本第11章 信息分类与聚类1 类的质心类的质心类的质心为该类所有对象的平均向量，即(11-1)2 类的直径类的直径通常可以用类中对象间的最大距离，或者类中各元素到类的质心距离的欧氏距离平方和作为类的直径。即(11-2)或者(11-3)1 类的质心类的质心为该类所有对象的平均向量，即第11章 信息分类与聚类式(11-3)将类直径定义为各元素的离差平方和的总和，简称离差平方和。式(11-3)将类直径定义为各元素的离差平方和的总和，简第11章 信息分类与聚类11.1.3 文档相似性文档相似性许多分类方法基于对象之间的二元关系来分类。对象之间的二元关系，通常有“相似性”、“相关系数”、“差异性”和“距离”等多种表达方式。确定文档的相似性是对文档进行分类的基础。对于有m个特征属性的对象而言，其总体特征可以看成一个m维向量，也可以看成是m维空间中的一个点，向量的第i个分量大小对应着第i个属性的权重。设Oi与Oj为两个对象，s(Oi，Oj)为Oi与Oj之间的相似性，s(Oi，Oj)应该满足：(1)非负性。对于任何i、j，恒有s(Oi，Oj)0。(2)对于任何i、j，恒有s(Oi，Oj)1。11.1.3 文档相似性许多分类方法基于对象之间的二第11章 信息分类与聚类(3)对称性。对于任何i、j，恒有s(Oi，Oj)=s(Oj，Oi)。在检索技术的研究过程中，研究者们提出了众多的相似性度量方式，其中最常用的有以下5种，如表11-1所示。设Wi，Wj为两个向量，wi，k与wjk分别为其第k个分量。(3)对称性。对于任何i、j，恒有s(Oi，Oj)=s第11章 信息分类与聚类第11章-信息分类与聚类ppt课件第11章 信息分类与聚类通常使用距离来衡量两个对象之间的相异度。两个文档之间的差异性系数越接近1，则表明这两个文档之间的距离越大。设d(Oi，Oj)为对象Oi与Oj之间的距离。常用的距离度量方法有以下几种。明考斯基距离(Minkowski distance)：(11-4)当q分别取1、2和时，明考斯基距离分别对应于曼哈坦距离(Manhattan distance)、欧几里德距离(Euclidean distance)和切比雪夫距离(Chebyishev distance)。曼哈坦距离，也叫做绝对值距离：(11-5)通常使用距离来衡量两个对象之间的相异度。两个文档之间的第11章 信息分类与聚类欧几里德距离，也叫做欧氏距离：(11-6)切比雪夫距离：(11-7)其他的距离函数包括兰氏距离(Lance distance)、马氏距离(Mahalanobis distance)和斜交距离(Oblique distance)等。一般地，这些距离函数都有如下特性：非负性：d(Oi，Oj)0 自相似性：d(Oi，Oi)=0 对称性：d(Oi，Oj)=d(Oj，Oi)欧几里德距离，也叫做欧氏距离：(11-6)切比雪夫距离第11章 信息分类与聚类三角不等式：d(Oi，Oj)d(Oi，Ok)+d(Ok，Oj)三角不等式的物理意义表现在：对于欧几里德空间(Euclidean Space)，一个三角形的任意两边长度之和总是大于第三条边的长度。在文本自动分类和处理的过程中，最基本的就是要得到文档之间相似系数或者距离。设共有N个文档，则任意两文档之间的二元关系可以构成一个NN的关系矩阵MNN。此关系矩阵全面地反映了文档之间的相似程度及其差异性，这是对文档进行分类和聚类的基础。由于相似系数和距离都满足对称性，故此关系矩阵是一个对称矩阵，即MNN=MTNN。三角不等式：d(Oi，Oj)d(Oi，Ok)+d(第11章 信息分类与聚类【例【例11-1】设有两对象所对应的总体特征分别是O1=1，3，5，O2=2，3，1。查询q的总体特征为q=1，1，0。求q与O1，O2之间的夹角余弦相似性以及欧几里德距离。根据这些度量，q与O1，O2中的哪个对象更相似？解：解：计算查询与两对象之间的余弦夹角相似性：【例11-1】设有两对象所对应的总体特征分别是O1=第11章 信息分类与聚类计算查询与两对象之间的欧几里德距离：由于s(q，O1)d(q，O2)，从而可知q与O2更为相似。计算查询与两对象之间的欧几里德距离：由于s(q，O1第11章 信息分类与聚类11.1.4 类间距离类间距离在文档分类和聚类的过程中，通常用类间距离来衡量不同类之间的相似性和差异性。与文档距离一样，类间距离同样有多种度量方式。设Si、Sj为两个类，常用的类间距离度量方式有最小距离法(Single-linkage)、最大距离法(Complete-linkage)、类平均距离法(Average linkage)、质心法(Centroid hierarchical)和离差平方和法(Wards method)。1 最小距离法最小距离法(11-8)因为在实际中很少出现极小异常值，使用最小距离法可以避免极大值的影响。11.1.4 类间距离在文档分类和聚类的过程中，通常第11章 信息分类与聚类2 最大距离法最大距离法(11-9)利用不同类的元素之间的最长距离作为类间距离。在一些应用中，为避免异常的极大值扭曲分类和聚类结果，需要删除这些异常值之后再进行处理。3 类平均距离法类平均距离法(11-10)利用类间所有样本点的平均距离作为类间距离。该法利用了所有样本的信息，是一种较为常用的类间距离度量方式。2 最大距离法(11-9)利用不同类的元素之间的最第11章 信息分类与聚类4 质心法质心法设两个类Si，Sj的质心分别为，利用类的质心之间的距离作为类间距离：(11-11)这种度量方式对异常值不敏感，结果比较稳定。4 质心法设两个类Si，Sj的质心分别为，第11章 信息分类与聚类5 离差平方和法离差平方和法用式(11-3)的类直径的定义得到两个类Si,Sj分别为 ,，合并后新类为Si+j的直径为，则可以定义类间距离的平方为(11-12)类间距离即为总类Si+j的离差平方和减去各子类的离差平方和。这种度量方式对异常值很敏感；对较大的类倾向产生较大的距离，从而不易合并，较符合实际需要。5 离差平方和法用式(11-3)的类直径的定义得第11章 信息分类与聚类11.2 特征描述及提取特征描述及提取在前面描述文档的相似性时提到，对于有m个特征属性的文档而言，其总体特征可以看成一个m维向量，也可以看成是m维空间中的一个点。在本节中，将描述如何从待分类的元素中提取总体特征，以及如何选择合适的特征，进行信息的分类和聚类。11.2 特征描述及提取在前面描述文档的相第11章 信息分类与聚类11.2.1 特征提取特征提取基于VSM模型的文本表示常用TF-IDF算法计算特征项的权重。这里回顾一下TF-IDF算法：TF：词频(Term Frequency)，向量空间模型中特征项termi在文档dj中出现的次数，记作tfi，j。tfi，j越高，意味着ti对文档dj越重要。比如，在一篇描写计算机应用的文档中，“计算机”、“电脑”出现的频率比较大，TF值比较高。TF还可以通过文档中的最大词频进行规范化。11.2.1 特征提取基于VSM模型的文本表示常用T第11章 信息分类与聚类DF：文档频率(Document Frequency)，文档集中含有特征项ti的文档个数，记作dfi。dfi越高，意味着termi在衡量文档之间差异性方面的作用越低。比如，在汉语中，“的”、“我”这种词的DF值一定比较高；在英语中，“if”、“is”等词的DF值也很高，这些词对于区分文档的意义不大。DF可以通过文档总数进行规范化。IDF：逆文档频率(Inverse Document Frequency)，与dfi形成反比关系。常用的IDF形式有idfi=1/dfi、idfi=lg(D/dfi)等。idfi越高，意味着ti在衡量文档之间差异性方面的作用越大。TF-IDF：同时考虑标引项在所在文本中的分布情况以及在全部文本集合中的分布情况。TF-IDF值的计算公式可参见第2章公式(2-4)。DF：文档频率(Document Frequency)，第11章 信息分类与聚类11.2.2 特征选择特征选择实现文本自动分类的基本困难之一是特征项空间的维数过高。所谓“特征项”，在中文文本中主要指分词处理后得到的词汇，而特征项的维数则对应不同词汇的个数。数量过大的特征项一方面导致分类算法的代价过高，另一方面导致无法准确地提取文档的类别信息，造成分类效果不佳。因此，需要在不牺牲分类质量的前提下尽可能地降低特征项空间的维数。“特征选取”的任务就是要将信息量小、“不重要”的词汇从特征项空间中删除，从而减少特征项的个数，它是文本自动分类系统中的一个关键步骤。常用的特征选择算法有文档频率、信息增益(Information Gain，IG)、互信息量(Mutual Information，MI)以及卡方检验(2 test，CHI)，以下对这4种方法作简单的介绍。11.2.2 特征选择实现文本自动分类的基本困难之一第11章 信息分类与聚类1 文档频率文档频率DF表示在训练集中包含某个特征项t的文档数。这种衡量特征项重要程度的方法基于这样一个假设：DF较小的特征项对分类结果的影响较小。这种方法优先取DF较大的特征项，而DF较小的特征项将被剔除。DF是最简单的特征项选取方法，而且该方法的计算复杂度低，能够胜任大规模的分类任务。但这种策略不符合被广泛接受的信息检索理论：高频词没有低频词对文档特征贡献大。1 文档频率DF表示在训练集中包含某个特征项t的第11章 信息分类与聚类2 信息增益信息增益IG通过统计某个特征项在一篇文档中出现或不出现的次数来预测文档的类别。IG的计算公式如下所示。(11-13)式中：Pr(ci)表示一篇文档属于类别的概率；Pr(t)表示特征项t在一篇文档内出现的概率；Pr()表示特征项t不在一篇文档内出现的概率；Pr(ci|t)表示特征项t在属于类别的文档内出现的概率；Pr(ci|)表示特征项t不在属于类别的文档内出现的概率；m是文档类别数。G(t)值大则被选取的可能性大，即特征项按照G值排序。2 信息增益IG通过统计某个特征项在一篇文档中出第11章 信息分类与聚类3 互信息互信息MI使用公式(11-14)计算某个特征项和类别之间的相关性2。(11-14)式中：A为t和c同时出现的次数；B为t出现而c没有出现的次数；C为c出现而t没有出现的次数；N为所有文档数。如果t和c不相关，则I(t，c)值为0。如果有m个类，于是对于每个t会有m个值，取它们的平均，就可得到特征选取所需的一个线性序。大的I平均值的特征被选取的可能性大。3 互信息MI使用公式(11-14)计算某个特征第11章 信息分类与聚类4 2检验检验使用MI衡量特征项的重要程度时，只考虑到了正相关对特征项重要程度的影响。如果特征项t和类别反相关，就说明含有特征项t的文档不属于的概率要大一些，这对于判断一篇文档是否不属于类别c也是很有指导意义的。为克服这个缺陷，2使用公式计算特征项t和类别c的相关性：(11-15)4 2检验使用MI衡量特征项的重要程度时，只第11章 信息分类与聚类式中：A为t和c同时出现的次数；B为t出现而c没有出现的次数；C为c出现而t没有出现的次数；D为t和c同时没有出现的次数；N为训练集中的文档数。与MI类似，如果t和c不相关，则2(t，c)值为0。与MI相同，如果有m个类，每个t就会有m个值，取它们的平均，就可得到特征选取所需的一个线性序。大的2平均值的特征被选取的可能性大。【例【例11-2】表11-2显示了几个特征词在不同文档类出现的次数，试计算2(财务，C1)。式中：A为t和c同时出现的次数；B为t出现而c没有出现的次数第11章 信息分类与聚类第11章-信息分类与聚类ppt课件第11章 信息分类与聚类解解：总共有80个文档。计算特征值“财务”在类别C1和非C1(记为)中的分布：则有：2(财务，C1)=解：总共有80个文档。计算特征值“财务”在类别C1和非第11章 信息分类与聚类11.3 聚类方法聚类方法所谓聚类，就是完全根据元素之间的相关性，将所有元素聚集成若干个类，使得属于同一类的元素之间尽可能相似，属于不同类的元素之间差别显著。由于事先没有关于这些元素信息的分类知识和类别信息，所以文本聚类可以看成是一种“无监督学习”(unsupervision learning)，文本聚类的特点是“先有元素后有类”，完全根据元素的信息来进行分类。事实上，信息聚类的方法起源于数据分析和数据挖掘3的研究。聚类分析的目的是把一个给定的数据对象集合分成不同的簇(cluster)。簇是相似数据对象的集合，在同一个类中，对象之间具有相似性；不同类的对象之间是相异的。11.3 聚类方法所谓聚类，就是完全根第11章 信息分类与聚类11.3.1 划分聚类法划分聚类法较流行的划分聚类方法(partitional algorithms)有动态聚类法(也称逐步聚类法)，如k-均值(k-means)算法、k-中心点算法。其基本思想为：随机选择k个对象，每个对象初始地代表一个类的平均值或中心，对剩余每个对象，根据其到类中心的距离，被划分到最近的类；然后重新计算每个类的平均值。不断重复这个过程，直到所有的样本都不能再分配为止。k-均值聚类法是一种常用的划分聚类法，它利用类的质心之间的距离作为类间距离。下面以一个实际例子，来说明k-均值聚类法的过程。【例【例11-3】在(X，Y)平面有表11-3给出的点，试对它们进行聚类。11.3.1 划分聚类法较流行的划分聚类方法(par第11章 信息分类与聚类第11章-信息分类与聚类ppt课件第11章 信息分类与聚类解：解：在此例中，每个对象都有2个特征，分别表示在X轴和Y轴上。第一步：k=3，随机选取3个类的中心，分别用k1、k2、k3表示，如图11-1所示。为了将点指派到最近的中心，通常可以用欧几里得距离表示欧氏空间中的点，用余弦值表示文档间距离，用公式(11-1)计算类中心。第二步：对于所有对象，根据其到k1、k2、k3之间的距离，划分到相应的类中。然后重新计算每个类的质心。此时的k1、k2、k3与第一步中的值已经不同了，如图11-2所示。解：在此例中，每个对象都有2个特征，分别表示在X轴和Y第11章 信息分类与聚类图11-1 各类的中心点图11-1 各类的中心点第11章 信息分类与聚类图11-2 各类的质心图11-2 各类的质心第11章 信息分类与聚类第三步：此为第一次聚类后的情况，如图11-3所示。图11-3 第一次聚类结果第三步：此为第一次聚类后的情况，如图11-3所示。图1第11章 信息分类与聚类第四步：对于所有对象，根据其到k1、k2、k3之间的距离，继续划分到相应的类中。然后重新计算每个类的质心，如图11-4所示。第五步：重复“分类”“计算新的质心”“分类”“计算新的质心”这样的过程，直到分类情况不再变化为止。以下为最终的聚类情况，如图11-5所示。第四步：对于所有对象，根据其到k1、k2、k3之间的距离第11章 信息分类与聚类图11-4 重新计算各类的质心图11-4 重新计算各类的质心第11章 信息分类与聚类图11-5 最终聚类结果图11-5 最终聚类结果第11章 信息分类与聚类总之，划分聚类法的特点为：k需要事先定好；创建一个初始划分，再采用迭代的重定位技术；不必确定距离矩阵；时间复杂度为O(n)，比层次聚类法运算量要小，适用于处理庞大的样本数据；适用于发现球状类。划分聚类法的缺陷是：不同的初始值，结果可能不同；有些k-均值算法的结果与数据输入顺序有关，如在线k-均值算法；用爬山法(hill-climbing)来寻找最优解，容易陷入局部极小值。总之，划分聚类法的特点为：k需要事先定好；创建一个初始划第11章 信息分类与聚类11.3.2 层次聚类法层次聚类法层次聚类法(hierarchical method)也称为系统聚类法，它对给定的数据进行层次的分解。层次聚类法又可分为凝聚的(agglomerative，bottom-up)的方法与分裂的(divisive，top-down)方法。凝聚的方法一开始将每个对象单独地看做一类，然后根据同类相近，异类相异的原则，合并类，直到所有的类并成一个，或达到一个终止条件为止。分裂的方法一开始将所有的对象置于一类，在迭代的每一步中，一个类不断地分为更小的类，直到每个对象在单独的一个类中，或达到一个终止条件。11.3.2 层次聚类法层次聚类法(hierarch第11章 信息分类与聚类设共有N个元素需要聚类，计算所有元素两两间的距离，共有C2N个，MNN为元素之间的距离矩阵。显然，MNN为一个对称矩阵，且MNN的所有对角元素均为0。层次聚类法的基本流程如下：(1)把每个元素当成一个类，则初始时，系统一共存在N个类，每个类中只含有一个元素，这些类的类间距离等于其包含的元素之间的距离。(2)找到最接近(距离最小)的两个类，将这两个类合并为一个类，现在系统中类的总数目将减少1。(3)计算合并成的新类与其他旧类之间的距离。(4)重复步骤(2)与(3)，直到所有的元素都合并成为了一个类。设共有N个元素需要聚类，计算所有元素两两间的距离，共有C第11章 信息分类与聚类由此过程可见，每次合并都将使得系统中类的数目减少1，经过N-1次合并，则原来的N个元素就聚合成为一类了，聚类过程也就结束了。在聚类的过程中，将会产生一个层次结构的树状图，这也是层次聚类法这个名字的由来。步骤(3)中的类间距离有多种计算方式，如最小距离、最大距离、重心距离、类平均距离等，关于类间距离的详细介绍请参见11.1.4节。层次聚类法的特点为：(1)类的个数不需事先定好；(2)聚类的效果较好；(3)需确定距离矩阵；(4)时间复杂度至少是O(N2)，运算量较大，扩展性不佳，适用于处理小样本数据。由此过程可见，每次合并都将使得系统中类的数目减少1，经过第11章 信息分类与聚类11.3.3 其他聚类方法其他聚类方法除了划分聚类法和层次聚类法之外，还有一些其他的聚类方法。这些聚类方法有其自身的特点，可以根据需要独立运用于信息聚类中，也可以用来补充划分聚类法和层次聚类法的不足。比如，基于距离的方法比较适合发现聚集球状类，基于密度的方法(density-based method)可以用来识别任意形状的类。11.3.3 其他聚类方法除了划分聚类法和层次聚类法第11章 信息分类与聚类在基于密度的方法中，只要临近区域的密度超过一定的阈值，就继续聚类，所以这种方法可以过滤噪声和孤立点(outlier)，发现任意形状的类。基于网格的方法(grid-based method)把样本空间量化为有限数目的单元，形成一个网络结构，聚类操作都在这个网格结构(即量化空间)上进行。基于模型的方法(model-based method)为每个类假定一个模型，寻找数据对给定模型的最佳拟合。在此不详述这些聚类方法，有兴趣者可以参阅相关书籍。在基于密度的方法中，只要临近区域的密度超过一定的阈值，就第11章 信息分类与聚类11.4 分类方法分类方法与聚类不同的是，分类之前，已经有分类知识和类别信息。在很多分类的应用中，已经知道了目标数据需要分成哪些类。文本分类是指在给定分类体系下，根据文本内容自动确定文本类别的过程。文本分类的过程一般包括特征提取、特征选择、分类判决的过程，如图11-6所示。11.4 分类方法与聚类不同的是，分类第11章 信息分类与聚类图11-6 自动分类的一般过程图11-6 自动分类的一般过程第11章 信息分类与聚类在整个文本分类过程中，分类算法是文本分类的核心。目前文本分类的算法有很多种，包括朴素贝叶斯算法(Nave Bayes)、k近邻法(kNN)、决策树算法、决策规则算法、回归模型、Rocchio算法、神经网络算法(NN)、支撑矢量机(SVM)、线性最小二乘方估计(LLSF)和分类器集成方法等，总体来说，分类算法大致可归结为两大类：参数类型和非参数类型。参数类型的分类方法使用训练数据集估计各参数，然后利用估计的参数值进行分类判断。朴素贝叶斯算法是典型的参数类型分类法。在整个文本分类过程中，分类算法是文本分类的核心。目前文第11章 信息分类与聚类非参数类型的分类法还可以分为两类：基于示例和基于样本。基于示例的方法是从每个类别的训练集中抽取或建立一个示例作为该类别的代表，示例用加权特征词组成的特征向量来表示。若共有N个类别，则建立N个特征矢量作为各个类别的示例，未知类别的文档通过与各个类别示例相比较来进行分类，Rocchio方法属于该类方法。而基于样本的方法将未知类别的文档看做是对于训练集的一个查询，它从训练集合中得到多个已知类别样本，这些样本的类别作为未知文本的候选样本。k近邻法就是一种基于样本的方法。下面介绍几种常用的分类方法。非参数类型的分类法还可以分为两类：基于示例和基于样本。第11章 信息分类与聚类11.4.1 Nave Bayes算法算法朴素贝叶斯(NaIve Bayes，NB)算法是机器学习领域中最常见的一种基于概率的算法。它建立在类条件独立的朴素假设之上，即假设文本中的各个特征项属于特定类别的概率相互独立。该算法计算待分类实例属于各个类别的后验概率，取后验概率最大的类别作为所属类别。假设存在一些类别：C1，C2，Cn，E是一个实例的特征描述，现在要判断该实例属于哪个类别，即求P(Ci|E)。根据贝叶斯定理，有(11-16)11.4.1 Nave Bayes算法朴素贝叶斯(第11章 信息分类与聚类假设各类是独立的，则有(11-17)需要知道先验概率P(Ci)和条件概率P(E|Ci)，才能计算后验概率P(Ci|E)。P(Ci)可以从数据中估计得来，假设在样本空间D中，类别Ci中有ni个样本，总的样本数是|D|，则可以估计P(Ci)为(11-18)假设各类是独立的，则有(11-17)需要知第11章 信息分类与聚类再假设实例是由一系列独立的特征来表述的，关于给定类别的条件概率也是独立的：(此处最好准确重述一下，这个条件独立性假设即朴素贝叶斯假设。其最大作用在于NB假设下计算联合分布时简单可行。)(11-19)【例【例11-4】根据统计，天气情况和几种特征有如表11-4所示的关系。假定当前天气特征为有乌云，刮大风，没有闪电，试估计当前的天气情况。再假设实例是由一系列独立的特征来表述的，关于给定类别的条第11章 信息分类与聚类第11章-信息分类与聚类ppt课件第11章 信息分类与聚类解：解：当前特征：E=乌云，大风，闪电P(E)=0.0089+0.01+0.019=0.0379因此，P(晴天|E)=0.23，P(雨天|E)=0.26，P(阴天|E)=0.50。按朴素贝叶斯方法判断，当前最可能的天气情况为阴天。将朴素贝叶斯应用于文本分类。需要假设文本中的各个特征项属于特定类别的概率相互独立。该算法计算文本属于各个类别的后验概率，取后验概率最大的类别作为文本类别。解：当前特征：E=乌云，大风，闪电P(E)=0.第11章 信息分类与聚类假设文本d属于类别Cj的后验概率为P(Cj|d)，可以由公式(11-20)计算。(11-20)由于P(d)代表文档d的先验概率，对所有类别为常数，则有式中：P(Cj)代表训练集中类别Cj的先验概率；P(d|Cj)代表假设为类别Cj时观察到d的概率；P(tk|Cj)代表类别Cj中特征tk出现的频率；N(tk，d)代表在文档d中特征tk出现的次数。各概率计算公式如下：(11-21)假设文本d属于类别Cj的后验概率为P(Cj|d)，可以由第11章 信息分类与聚类(11-22)(11-23)式中：|Dj|代表类别Cj中的训练文档数;|D|代表所有的训练文档数;N(tk，di)代表在训练文档di中特征tk出现的次数;|V|代表所有的特征数目。式(11-23)中，分子表示类别Cj中特征tk出现的次数，分母表示类别Cj中所有特征出现的总次数，并对分子和分母进行了平滑处理，避免出现零概率。(11-22)(11-23)式中：|Dj|代表类别Cj中的第11章 信息分类与聚类在训练时，先对训练数据根据公式(11-22)和(11-23)计算各个类别的P(Cj)和P(tk|Cj)。当待分类文本d到达时，再根据公式(11-21)计算出该文本的类别。理论上讲，贝叶斯分类具有最小的出错率。然而，实践中并非总是如此，这是由于对其应用的假定(如类条件独立性和特征独立性)的不准确性所造成的。朴素贝叶斯算法描述如下：在训练时，先对训练数据根据公式(11-22)和(11-2第11章 信息分类与聚类训练：V是文档D里面的所有词汇，对于每一个分类CjC假设Di是文档D的一个子集，属于类Cj P(Ci)=|Di|/|D|Ti是所有文档Di串接而成的总文档，ni是Ti中词汇出现的总数对于每一词wjV，nij是词wj在Ti中的出现的次数 P(wj|Ci)=(nij+1|Ci)/(ni+|V|)测试：已知一个测试集XN是X中词汇出现的次数，得到分类为训练：V是文档D里面的所有词汇，对于每一个分类CjC假第11章 信息分类与聚类其中，j是测试集X中第j个位置出现的词。【例【例11-5】有如表11-5所示的训练集和测试集，请问测试集中的文档D5应该归属于哪一类？其中，j是测试集X中第j个位置出现的词。【第11章 信息分类与聚类第11章-信息分类与聚类ppt课件第11章 信息分类与聚类解：解：用朴素贝叶斯算法，先计算“Yes”和“No”两个类的先验概率：测试集包含的词汇V=Chinese，Japan，Tokyo，对这几个词项计算关于两个类别的条件概率：解：用朴素贝叶斯算法，先计算“Yes”和“No”两个类的第11章 信息分类与聚类对文档D5，计算关于每个类别的后验概率：因此文档D5属于类别Yes。对文档D5，计算关于每个类别的后验概率：因此文档D5属于第11章 信息分类与聚类11.4.2 kNN算法算法kNN法是基于样本(Instance-Based)的算法，该算法首先对训练集文本进行向量化，得到各文本的特征向量。当待分类文本到达后，进行向量化，得到特征向量，然后计算该向量与每个训练文本向量的距离，找到与该文本相似度最近的k个文本。在这k个文本中，哪个类别的文本数最多，待分类文本就属于哪个类别。相似度的计算公式如下：(11-24)kNN算法可由图11-7形象地表示。11.4.2 kNN算法kNN法是基于样本(Inst第11章 信息分类与聚类图11-7 kNN分类图11-7 kNN分类第11章 信息分类与聚类假设有两个类别，k值取5，当一个未知文档d1到达时，计算该文档与每个训练文档的相似度，得到最近的5个训练文档，4个属于类别A，1个属于类别B，则文档d1判为类别A。同理，文档d2判为类别B。如果考虑相似度的量化值，可以改进kNN算法的判别方法。计算文档关于类别的权重：(11-25)这里，x是一个新的点，Cj是已知类别，di是x的k个最近的邻居点，sim(x，di)是x和di的相似度。而I(di，Cj)为类别属性函数，即如果di属于类Cj，那么函数值为 1，否则为 0。假设有两个类别，k值取5，当一个未知文档d1到达时，计算第11章 信息分类与聚类比较类的权重，将文本分到权重最大的那个类别中。kNN法的缺点就是k值不好确定，传统上要进行一系列实验来比较不同k值所产生的结果，从而得到最优的k值。并且大量的计算在分类时进行，当训练文本集很大时，会导致分类耗时较多。(11-26)比较类的权重，将文本分到权重最大的那个类别中。第11章 信息分类与聚类kNN的算法描述如下：1 根据特征项集合重新描述训练文本向量。2 在新文本到达后，根据特征词分词新文本，确定新文本的向量表示。3 在训练文本集中选出与新文本最相似的k个文本，计算公式为(11-24)。其中，k值的确定目前没有很好的方法，一般采用先定一个初始值，然后根据实验测试的结果调整k值，一般初始值定为几百到几千之间(并非定论，可以不提此句)。kNN的算法描述如下：1 根据特征项集合重新描述第11章 信息分类与聚类4 在新文本的k个邻居中，依次计算每类的权重，计算公式为(11-25)。5 比较类的权重，将文本分到权重最大的那个类别中。【例【例11-6】假定通过计算某文档与训练集文档的相似度，得出表11-6(k=10)。4 在新文本的k个邻居中，依次计算每类的权重，计算公式第11章 信息分类与聚类第11章-信息分类与聚类ppt课件第11章 信息分类与聚类11.4.3 Rocchio算法算法Rocchio算法是一种典型的基于示例的算法。它首先为每个类别建立一个代表矢量，当一个待分类文档到达后，计算该文档矢量和类别代表矢量的距离，取距离最小的类别作为文档所属类别4。Rocchio分类器是基于向量空间模型和最小距离的方法。此方法起初应用于信息检索系统中，后来最早由Hull在1994年应用于分类5,此后，Rocchio方法就在分类中广泛应用起来。Rocchio计算公式为(11-27)11.4.3 Rocchio算法Rocchio算法是第11章 信息分类与聚类式中：wic为类C中心向量的权重；为训练样本中正例的控制参数；为训练样本中反例的控制参数；nC为训练样本中类别C的正例数目；n为训练样本的文档数；和是两个控制参数，可以通过提高，降低来削弱反例的影响。当1，0时，wic为正例的质心。文档di与类别C的距离度量公式为(11-28)假定有n个文档类别记为C1，C2，Cn，训练过程的算法描述如下：式中：wic为类C中心向量的权重；为训练样本中正例的控第11章 信息分类与聚类循环：i从1到 n，令pi=(初始化原型向量)对每一个训练样本D 令d是文档x的归一化TF-IDF权重矢量 i=j(Cj=C(x)(某类文档向量之和形成原型向量pi)pi=pi+d循环：i从1到 n，令pi=(初始化原型第11章 信息分类与聚类给定测试文档 x，分类过程的算法描述如下：令d是文档x的归一化TF-IDF权重矢量m=2(初始化最大的余弦相似度)循环：i从1到n，(计算与原型向量的相似度)s=cos(sim(d，pi)如果sm，令：m=s r=Ci(更新最相似的类原型向量)返回类别 r【例11-7】已知训练集的文档向量如表11-7所示。请区分测试集dnew(0，0.005，0.15，0.1)属于哪类文档？给定测试文档 x，分类过程的算法描述如下：令d是文档x第11章 信息分类与聚类第11章-信息分类与聚类ppt课件第11章 信息分类与聚类解：解：经计算，C1的原型向量p1=(0.06，0.2，0，0.2)C2的原型向量p2=(0.001，0.001，0.38，0.5)相似度：s1=0.4027，s2=0.9448故文档dnew属于C2类。解：经计算，C1的原型向量p1=(0.第11章 信息分类与聚类11.4.4 SVM算法算法支撑向量机(Support Vector Machines，SVM)是Vapnik为了解决两层模式识别问题于1995年提出来的6。SVM基于结构风险最小化(Structural Risk Minimization)原理，这个方法定义在一个矢量平面上，问题就是找到一个决定平面可以最优地把数据点分割成两类。为了定义“最优”分割，需要引入“间隔”(Margin)的概念。图11-8解释了这个想法。为了简便，图中只显示了在二维空间上线性分割数据点，但是这种思想可以推广到多维空间，并且对数据点可以不是线性分割。在一个线性分割空间中的分割平面是一个超平面，每组平行线间的距离叫做“间隔”。SVM的难点就是在训练集中找到分割平面i，并且最大化间隔。11.4.4 SVM算法支撑向量机(Support 第11章 信息分类与聚类图11-8 SVM分类图11-8 SVM分类第11章 信息分类与聚类由SVM决定的线性分割空间的决定平面是一个超平面(Hyper-plane)，这个超平面可以表示如下：wxb=0 (11-29)x是训练集中一个任意的数据点，矢量w和常数b是需要从训练集中学习的数据。用Tr=(xi，yi)表示训练集，yi1是对xi的分类(对于给定类别，1代表正例，1代表负例)，SVM的任务就是找到满足以下约束条件的w和b：wxib+1 for yi=+1 (11-30)wxib1 for yi=1 (11-31)并且矢量使w的范数平方为最小。由SVM决定的线性分割空间的决定平面是一个超平面(Hyp第11章 信息分类与聚类对线性可分数据集而言，SVM的一个有趣的特性是分割平面仅由来自决定平面的等于距离1/w的数据点(图11-8中带框的点)决定。这些点叫做支撑向量(Supporting Vector)，是训练集中唯一有效的元素。如果除掉所有的其他点，算法具有同样的分类功能。这个特性使得SVM在理论上是独特的，和其他方法都不同，如kNN、LLSF、NN和NB都是使用训练集中的所有数据点来优化分类功能。【例【例11-8】图11-9所示三个训练点坐标分别为(1，1)、(2，0)和(2，3)，分属两个类别，求两个类别的决定平面及最大间隔。对线性可分数据集而言，SVM的一个有趣的特性是分割平面仅第11章 信息分类与聚类图11-9 训练点分布图图11-9 训练点分布图第11章 信息分类与聚类解：解：具有最大边缘的权重向量平行于两个类的最短连接线，即(1，1)和(2，3)的连线，决定平面必定垂直于这条线，并与之相交于(1.5，2)，所以，SVM的决定平面是y=x1+2x25.5用代数方法求解，标准的约束是式子(11-28)和(11-29)，并且矢量w范数平方为最小，这仅当两个支撑向量满足约束时才可能。矢量w平行于(1，1)和(2，3)的连线，可以设为w=(a，2a)，所以有解得：解：具有最大边缘的权重向量平行于两个类的最短连接线，即(第11章 信息分类与聚类最大间隔为SVM的求解实际上是一个优化问题，因此可以引入拉格朗日乘子(Lagrange multiplier)i来求解。分类函数表示为(11-32)当指定数值表达式的值为正或负时，sign函数分别返回 1或1，+1表示属于一个类别，1表示属于另一个类别。SVM算法的计算过程如下：最大间隔为SVM的求解实际上是一个优化问题，因此可以引入第11章 信息分类与聚类给定训练样本S=(x1，x2，xl)初始化，0，b0，R xi重复以下循环直至没有任何误差 循环：i从1到l 如果yi(jyjxjxi+b)0，则 i=i+1 b=b+yiR2返回(，b)，得到H(x)给定训练样本S=(x1，x2，xl)初始化，0，b第11章 信息分类与聚类对于线性不可分的情况，可以把样本X 映射到一个高维特征空间H，并在此空间中运用原空间的函数来实现内积运算，这样将非线性问题转换成另一空间的线性问题。(最好明确一下核函数定义和作用)常用的内积核函数有下面三种。(1)多项式函数：(11-33)这样得到的是p阶多项式分类器。(2)径向基函数(Radial Basis Function，RBF)，也称高斯核函数：(11-34)对于线性不可分的情况，可以把样本X 映射到一个高维特征空第11章 信息分类与聚类(3)Sigmoid函数：(11-35)这里，k是增益，是阈值。【例【例11-9】使用SVM解决XOR分类问题，XOR值域及其分布如图11-10所示。解：解：使用多项式核函数K(x1，x2)=(1+x1x2)2进行变换，也就是可以表示为 表11-8给出了变换后的输入输出关系，变换后的函数图像如图11-11所示。(3)Sigmoid函数：(11-35)这里，k是增益第11章 信息分类与聚类图11-10 XOR值域及其分布图11-10 XOR值域及其分布第11章 信息分类与聚类第11章-信息分类与聚类ppt课件第11章 信息分类与聚类图11-11 变换后的函数图像图11-11 变换后的函数图像第11章 信息分类与聚类变换后在高维空间的XOR值域分布如图11-12所示，很显然这是线性可分的。图11-12 高维空间中的XOR值域分布变换后在高维空间的XOR值域分布如图11-12所示，很显第11章 信息分类与聚类11.5 方法评测方法评测11.5.1 聚类方法评测聚类方法评测一个好的聚类方法要能产生高质量的聚类结果簇，这些簇要具备以下两个特点：(1)高的簇内相似性。(2)低的簇间相似性。聚类结果的好坏取决于该聚类方法采用的相似性评估方法以及该方法的具体实现；聚类方法的好坏还取决于该方法是能发现某些还是所有的隐含模式。11.5 方法评测11.5.1 聚类方第11章 信息分类与聚类 一个聚类方法应该满足以下特点：(1)时间和空间上的可扩展性；(2)能够处理不同类型的属性；(3)能发现任意形状的簇；(4)在决定输入参数的时候，尽量不需要特定的领域知识；(5)能够处理噪声和异常；(6)对输入数据对象的顺序不敏感；(7)能处理高维数据；(8)能产生一个好的、能满足用户指定约束的聚类结果；(9)结果是可解释的、可理解的和可用的。一个聚类方法应该满足以下特点：(1)时间和空间第11章 信息分类与聚类由于聚类是一种无监督的学习方法，事先没有训练集，也不能事先确定聚成的类会是什么样的，所以评测聚类的效果是比较困难的。聚类本身就是一个较为主观的过程，很多时候多种聚类结果都同样合理。目前有的做法采用分类测试集来测试聚类的效果，即把已经分好类的测试集打乱，再利用聚类方法进行聚类，把聚类出来的结果与分好类的测试集进行比较，用来衡量聚类的效果。下面介绍两个用于评估的指标。由于聚类是一种无监督的学习方法，事先没有训练集，也不能事第11章 信息分类与聚类1.纯度纯度(purity)聚类评估即评测其发现隐含模式或潜在类别的能力。假设有J个已经标注好的类C=c1,c2，cJ，聚类算法产生K个簇=1，2，K，则聚类纯度指标定义为(11-36)这里N是要聚类的文档数。1.纯度(purity)聚类评估即评测其发现隐第11章 信息分类与聚类2.Rand指标指标(Rand Index)把聚类看成是做一系列决定的过程，即对集合中N(N-1)/2 对文档做决定的过程，可能的决定种类有：TP(true positive):将两个相似的文档放到同一个簇的决定;TN(true negative):将两个不相似的文档放到不同簇的决定;FP(false positive):将两个不相似的文档放到同一簇的决定;FN(false negative):将两个相似的文档放到不同簇的决定。定义Rand指标值为(11-37)【例【例11-10】对三个类别的数据，用某聚类方法得到的聚类结果如图11-13所示。2.Rand指标(Rand Index)把聚类第11章 信息分类与聚类图11-13 聚类结果图11-13 聚类结果第11章 信息分类与聚类解：解：该聚类方法的纯度指标值为该聚类方法的RI指标值为解：该聚类方法的纯度指标值为该聚类方法的RI指标值为第11章 信息分类与聚类11.5.2 分类方法评测分类方法评测在信息检索领域，通常采用查准率(Precision)和查全率(Recall)作为评价测度。在分类研究领域，人们通常也借鉴这些标准来评价分类系统的优劣。在信息检索系统中，查准率表示在所有被检索出的文档结果集中，真正符合检索意图的文档所占的比率，它体现了系统检索结果的准确程度。查全率表示被检索出的文档集结果中真正符合检索意图的文档数在所有符合检索意图的文档集中所占的比率，它体现了系统检索所有相关文档的完备性。在分类系统中，查准率是指被分类的正确文档数与所有被分类的文档数的比率，反映了分类的准确程度，也称准确率，查全率是指被分类的正确文档数与实际类别包含的文档数的比率，反映了分类结果与实际类别的吻合程度。11.5.2 分类方法评测在信息检索领域，通常采用查第11章 信息分类与聚类查准率和查全率这两个标准是互补的，单纯提高查准率就会导致查全率的降低，反之亦然。因此，尽管一个好的分类器应该同时具有较高的查准率和较高的查全率，但是实际的检索分类器需要在两者之间做出一些折中，而避免其中一个指标过低。为了反映查准率和查全率的综合效果，可用F测度：(11-38)比较常用的是F1(=1)值。对多个类别的分类器，为了评价分类器的整体效果，需要对每个分类器的结果进行平均。采用的平均方法有两种：查准率和查全率这两个标准是互补的，单纯提高查准率就会导致第11章 信息分类与聚类宏平均(Macroaveraging)：对每个类分别求评测值，然后平均。这种平均方法将大类小类同等看待。微平均(Microaveraging)：将所有文档一块儿计算，求评测值。这种平均方法使得评测结果易受大类的影响。对测度F1根据不同的平均方法可以得到微平均F1和宏平均F1。【例【例11-11】一个分类方法对两个类的分类结果分别如表11-9和表11-10所示，求该分类方法的宏平均和微平均查准率。宏平均(Macroaveraging)：对每个类分别求评第11章 信息分类与聚类第11章-信息分类与聚类ppt课件第11章 信息分类与聚类第11章-信息分类与聚类ppt课件第11章 信息分类与聚类解：解：宏平均查准率：微平均查准率：分类评测时要注意训练集合和测试集合是不同的集合，即用训练集合训练，用测试集合测试。常用的测试方法称为N重交叉检验(N fold cross-validation)，即将已标注好的标准数据集分成N份，用其中N1训练分类器，预留一份用于测试，对测试N次的结果求平均。解：宏平均查准率：微平均查准率：分类评测时要注意训第11章 信息分类与聚类分类评测中用到的标准数据集也称分类评测语料库(corpus)，目前国际常用的测试语料库是Reuters-21578数据集，该测试集经路透社人工收集和分类而成，包含路透社1987年的21 578篇新闻稿；其中9603个训练文档，3299个测试文档，118个类别。其他常用的语料库还包括包含从270余种医学杂志上搜集的23万篇文档的摘要的Ohsumed数据集，包含平均分布在20个类中的2万篇新闻文章的Newsgroup数据集，以及包含分布在20个类别中的9833个测试文档及9804个训练文档的复旦大学中文文本分类语料库。分类评测中用到的标准数据集也称分类评测语料库(corpu第11章 信息分类与聚类11.5.3 显著性检验显著性检验虽然分类方法已有很多的研究，但是由于发表的结果之间很难直接对比，所以这些方法的比较很难有清晰明确的结论。例如很难说神经网络方法(NNet)比SVM方法性能好还是坏。这是因为测试中使用了不同的语料集，并且没有进行不同数据集对分类结果影响方面的分析。朴素贝叶斯方法在某些研究中性能表现得相对比较差，但是其他一些研究中却被宣称为表现得出乎意料地好。这是因为在实验中要么使用了不一样的性能指标，要么只使用了基准(Benchmark)语料的一些子集。而且上述说法也非常含糊，“出乎意料地好”其实有很多的理解，例如可以理解成这个方法在统计意义显著地比其他方法好，或者说和最好的那些方法相比实际上在统计上并没有什么不同，或者说比那些最好的方法差一些但是比作者预料的要好。如果上述某种理解成立的话，又有什么实验证据可以证明。这些都是我们需要解决的问题。11.5.3 显著性检验虽然分类方法已有很多的研究，第11章 信息分类与聚类因此有必要引入显著性检验(Significance Tests)，来比较两个系统的不同性能指标是否有显著的差别。考虑比较两个系统A和B。假设系统A在测试集合上的正确率是pa，系统B的正确率是pb，两个测试集合分别包含na和nb个实验样本(trial)。注意到实验样本的定义在不同情形下是不同的：(1)对于微平均的查全率(Micro-avg Recall)，NA+C。(2)对于微平均的查准率(Micro-avg Precision)，NA+B。(3)对于微平均的准确率(Micro-avg Accuracy)或错误率(Error)，N=A=B+C+D。原假设(null hypothesis)H0=papb=0。因此有必要引入显著性检验(Significance Te第11章 信息分类与聚类备择假设(alternative hypothesis)HA：0，则认为系统A的性能比系统B性能好。在H0下的统计量(test statistic)满足N(，2)的正态分布：(11-39)这里：(11-40)计算检验统计量：(11-41)备择假设(alternative hypothesis)第11章 信息分类与聚类如果只有一个测试集合，即有n=na=nb，则以上计算简化为当n足够大时，可用正态分布方法计算P-value：(11-42)(11-43)如果只有一个测试集合，即有n=na=nb，则以上计算简化第11章 信息分类与聚类显著性检验计算步骤如下：1 给出原假设H0；2 给出备择假设HA；3 对H0和HA计算检验统计量Z；4 计算P-value；5 接受或拒绝H0，并陈述结论。【例【例11-12】采用NB和SVM方法对文本进行分类，其中NB方法对600份文档操作，358份分类正确；SVM方法对550份文档分类，405份分类正确。请问在0.01的显著性水平(significance level)上这两种分类方法的正确率有没有不同？解：解：采样规模：n1=550，n2=600显著性检验计算步骤如下：1 给出原假设H0；第11章 信息分类与聚类(1)原假设：H0：1=2(2)备择假设：H1：12(3)规定显著性水平=0.01(4)计算检验统计量：(1)原假设：H第11章 信息分类与聚类(5)计算 P-value：(6)接受或拒绝H0，并陈述结论。P-value=(0.004)(=0.01)因此，拒绝H0。也就是说可以得出结论：在0.01水平下，NB和SVM的分类方法的正确率显著不同。显著性检验是