《网络信息检索》课件第11章.ppt

1、第11章 信息分类与聚类第11章 信息分类与聚类 11.1 基本知识 11.2 特征描述及提取 11.3 聚类方法 11.4 分类方法 11.5 方法评测 11.6 小结 思考题第11章 信息分类与聚类11.1 基本知识基本知识信息分类是指将对象分到类别集合中去的过程。如果类别集合是事先给定，对训练集中的对象给出类别标识，则称为有监督的分类(通常所说的分类)。如果类别不是事先给定，而是在操作过程中生成，则称为无监督的分类(通常称为聚类)。无论是聚类还是分类，都涉及“类”的概念。如何认识和定义“类”的概念，如何对类的特征进行描述，是信息自动处理的首要问题。第11章 信息分类与聚类11.1.1 类

2、的概念类的概念在信息聚类和分类中，类是一个核心概念。如何认识类，定义类，描述类等是聚类和分类的基础。只有认识了什么是类，了解了如何抽取描述类的特征，才能熟悉信息聚类与分类的本质所在。直观而言，类是相似物体的集合。我们通常谈及“车”，其实可以看成是谈及“车”这样一个类。“车”类可能包括汽车、自行车、摩托车和火车等元素。“车”类中的这些元素都有一些共同的特征，都有轮子，都可以移动等。除了相似性之外，“车”类的各元素之间也有不同的地方，比如轮子数目的不同，动力源的差异等。信息聚类和分类的目的就是根据各个元素的一个特征信息，应用机器学习的方法1，将这些元素划分到不同的类中。第11章 信息分类与聚类11

3、.1.2 对象特征描述对象特征描述对象的形式化表示是一个基本的，而又非常重要的问题。首先要将对象从无结构的原始形式转化为计算机能够理解的结构化形式，然后才能进行分析与处理。常见的对象表示模型有向量空间模型、概率模型和语言模型等。其中最常用的是向量空间模型(VSM)。向量空间模型以特征项作为对象表示的基本单位，特征项可以由字、词、短语、颜色、纹理等组成。每一个对象Oi被看成是由特征项组成的n维特征空间的一个向量Wi，Wi=(t1，wi1;t2，wi2;tj，wij)，其中wij为第j个特征项tj在对象Oi中的权重。类通常具有质量、直径等性质，设类S有n个对象，这n个对象的特征抽象成n个向量W1，

4、W2，Wn，则：第11章 信息分类与聚类1 类的质心类的质心类的质心为该类所有对象的平均向量，即(11-1)nWCniis12 类的直径类的直径通常可以用类中对象间的最大距离，或者类中各元素到类的质心距离的欧氏距离平方和作为类的直径。即(11-2),(max(jisOODD 或者(11-3)nCWDCWDWDsisiniisT1),(),(第11章 信息分类与聚类式(11-3)将类直径定义为各元素的离差平方和的总和，简称离差平方和。第11章 信息分类与聚类11.1.3 文档相似性文档相似性许多分类方法基于对象之间的二元关系来分类。对象之间的二元关系，通常有“相似性”、“相关系数”、“差异性”和

5、“距离”等多种表达方式。确定文档的相似性是对文档进行分类的基础。对于有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章 信息分类与聚类(3)对称性。对于任何i、j，恒有s(Oi，Oj)=s(Oj，Oi)。在检索技术的研究过程中，研究者们提出了众多的相似性度量方式，其中最常用的有以下5种，如表11-1所示。设Wi，W

6、j为两个向量，wi，k与wjk分别为其第k个分量。第11章 信息分类与聚类第11章 信息分类与聚类通常使用距离来衡量两个对象之间的相异度。两个文档之间的差异性系数越接近1，则表明这两个文档之间的距离越大。设d(Oi，Oj)为对象Oi与Oj之间的距离。常用的距离度量方法有以下几种。明考斯基距离(Minkowski distance)：(11-4)(),(1NqwwOOdqmkqjkikji当q分别取1、2和时，明考斯基距离分别对应于曼哈坦距离(Manhattan distance)、欧几里德距离(Euclidean distance)和切比雪夫距离(Chebyishev distance)。曼哈

7、坦距离，也叫做绝对值距离：(11-5)mkjkikjiwwOOd1),(第11章 信息分类与聚类欧几里德距离，也叫做欧氏距离：(11-6)mkkjkijiwwOOd12,),(切比雪夫距离：(11-7)max(),(,kjkijiwwOOd其他的距离函数包括兰氏距离(Lance distance)、马氏距离(Mahalanobis distance)和斜交距离(Oblique distance)等。一般地，这些距离函数都有如下特性：非负性：d(Oi，Oj)0 自相似性：d(Oi，Oi)=0 对称性：d(Oi，Oj)=d(Oj，Oi)第11章 信息分类与聚类三角不等式：d(Oi，Oj)d(Oi，

8、Ok)+d(Ok，Oj)三角不等式的物理意义表现在：对于欧几里德空间(Euclidean Space)，一个三角形的任意两边长度之和总是大于第三条边的长度。在文本自动分类和处理的过程中，最基本的就是要得到文档之间相似系数或者距离。设共有N个文档，则任意两文档之间的二元关系可以构成一个NN的关系矩阵MNN。此关系矩阵全面地反映了文档之间的相似程度及其差异性，这是对文档进行分类和聚类的基础。由于相似系数和距离都满足对称性，故此关系矩阵是一个对称矩阵，即MNN=MTNN。第11章 信息分类与聚类【例例11-1】设有两对象所对应的总体特征分别是O1=1，3，5，O2=2，3，1。查询q的总体特征为q=

9、1，1，0。求q与O1，O2之间的夹角余弦相似性以及欧几里德距离。根据这些度量，q与O1，O2中的哪个对象更相似？解：解：计算查询与两对象之间的余弦夹角相似性：0478170453123111),(221Oqs9449.072513223121),(222Oqs第11章 信息分类与聚类计算查询与两对象之间的欧几里德距离：449.2121),(385.552),(22221OqdOqd由于s(q，O1)d(q，O2)，从而可知q与O2更为相似。第11章 信息分类与聚类11.1.4 类间距离类间距离在文档分类和聚类的过程中，通常用类间距离来衡量不同类之间的相似性和差异性。与文档距离一样，类间距离同

10、样有多种度量方式。设Si、Sj为两个类，常用的类间距离度量方式有最小距离法(Single-linkage)、最大距离法(Complete-linkage)、类平均距离法(Average linkage)、质心法(Centroid hierarchical)和离差平方和法(Wards method)。1 最小距离法最小距离法(11-8),(min),(,jiSOSOjiOOdSSdjjii因为在实际中很少出现极小异常值，使用最小距离法可以避免极大值的影响。第11章 信息分类与聚类2 最大距离法最大距离法(11-9),(max),(,jiSOSOjiOOdSSdjjii利用不同类的元素之间的最长距

11、离作为类间距离。在一些应用中，为避免异常的极大值扭曲分类和聚类结果，需要删除这些异常值之后再进行处理。3 类平均距离法类平均距离法(11-10)iijjSOSOjijijiOOdSSSSd),(|1),(利用类间所有样本点的平均距离作为类间距离。该法利用了所有样本的信息，是一种较为常用的类间距离度量方式。第11章 信息分类与聚类4 质心法质心法设两个类Si，Sj的质心分别为，利用类的质心之间的距离作为类间距离：(11-11)这种度量方式对异常值不敏感，结果比较稳定。iSCjSC),(),(jiSSjiCCdSSd第11章 信息分类与聚类5 离差平方和法离差平方和法用式(11-3)的类直径的定义

12、得到两个类Si,Sj分别为 ,，合并后新类为Si+j的直径为，则可以定义类间距离的平方为iSDjSDjiSD(11-12)jijiSSSjiDDDSSd),(2类间距离即为总类Si+j的离差平方和减去各子类的离差平方和。这种度量方式对异常值很敏感；对较大的类倾向产生较大的距离，从而不易合并，较符合实际需要。第11章 信息分类与聚类11.2 特征描述及提取特征描述及提取在前面描述文档的相似性时提到，对于有m个特征属性的文档而言，其总体特征可以看成一个m维向量，也可以看成是m维空间中的一个点。在本节中，将描述如何从待分类的元素中提取总体特征，以及如何选择合适的特征，进行信息的分类和聚类。第11章

13、信息分类与聚类11.2.1 特征提取特征提取基于VSM模型的文本表示常用TF-IDF算法计算特征项的权重。这里回顾一下TF-IDF算法：TF：词频(Term Frequency)，向量空间模型中特征项termi在文档dj中出现的次数，记作tfi，j。tfi，j越高，意味着ti对文档dj越重要。比如，在一篇描写计算机应用的文档中，“计算机”、“电脑”出现的频率比较大，TF值比较高。TF还可以通过文档中的最大词频进行规范化。第11章 信息分类与聚类DF：文档频率(Document Frequency)，文档集中含有特征项ti的文档个数，记作dfi。dfi越高，意味着termi在衡量文档之间差异性方

14、面的作用越低。比如，在汉语中，“的”、“我”这种词的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)。第11章 信息分类与聚类11.2.2 特征选择特征选择实

15、现文本自动分类的基本困难之一是特征项空间的维数过高。所谓“特征项”，在中文文本中主要指分词处理后得到的词汇，而特征项的维数则对应不同词汇的个数。数量过大的特征项一方面导致分类算法的代价过高，另一方面导致无法准确地提取文档的类别信息，造成分类效果不佳。因此，需要在不牺牲分类质量的前提下尽可能地降低特征项空间的维数。“特征选取”的任务就是要将信息量小、“不重要”的词汇从特征项空间中删除，从而减少特征项的个数，它是文本自动分类系统中的一个关键步骤。常用的特征选择算法有文档频率、信息增益(Information Gain，IG)、互信息量(Mutual Information，MI)以及卡方检验(2

16、test，CHI)，以下对这4种方法作简单的介绍。第11章 信息分类与聚类1 文档频率文档频率DF表示在训练集中包含某个特征项t的文档数。这种衡量特征项重要程度的方法基于这样一个假设：DF较小的特征项对分类结果的影响较小。这种方法优先取DF较大的特征项，而DF较小的特征项将被剔除。DF是最简单的特征项选取方法，而且该方法的计算复杂度低，能够胜任大规模的分类任务。但这种策略不符合被广泛接受的信息检索理论：高频词没有低频词对文档特征贡献大。第11章 信息分类与聚类2 信息增益信息增益IG通过统计某个特征项在一篇文档中出现或不出现的次数来预测文档的类别。IG的计算公式如下所示。(11-13)|(lo

17、g)|()()|(log)|()()(log)()(111tcPtcPtPtcPtcPtPcPcPtGirirmiririrmiririrmi式中：Pr(ci)表示一篇文档属于类别的概率；Pr(t)表示特征项t在一篇文档内出现的概率；Pr()表示特征项t不在一篇文档内出现的概率；Pr(ci|t)表示特征项t在属于类别的文档内出现的概率；Pr(ci|)表示特征项t不在属于类别的文档内出现的概率；m是文档类别数。G(t)值大则被选取的可能性大，即特征项按照G值排序。tt第11章 信息分类与聚类3 互信息互信息MI使用公式(11-14)计算某个特征项和类别之间的相关性2。(11-14)()(log)

18、,(BACANActI式中：A为t和c同时出现的次数；B为t出现而c没有出现的次数；C为c出现而t没有出现的次数；N为所有文档数。如果t和c不相关，则I(t，c)值为0。如果有m个类，于是对于每个t会有m个值，取它们的平均，就可得到特征选取所需的一个线性序。大的I平均值的特征被选取的可能性大。第11章 信息分类与聚类4 2检验检验使用MI衡量特征项的重要程度时，只考虑到了正相关对特征项重要程度的影响。如果特征项t和类别反相关，就说明含有特征项t的文档不属于的概率要大一些，这对于判断一篇文档是否不属于类别c也是很有指导意义的。为克服这个缺陷，2使用公式计算特征项t和类别c的相关性：(11-15)

19、()()()()(),(22DCBADBCACBADNct第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)。第11章 信息分类与聚类第11章 信息分类与聚类解解：总共有80个文档。计算特征值“财务”在类别C1和

20、非C1(记为)中的分布：1C则有：2(财务，C1)=280(33 75240)20.3(3340)(275)(332)(4075)第11章 信息分类与聚类11.3 聚类方法聚类方法所谓聚类，就是完全根据元素之间的相关性，将所有元素聚集成若干个类，使得属于同一类的元素之间尽可能相似，属于不同类的元素之间差别显著。由于事先没有关于这些元素信息的分类知识和类别信息，所以文本聚类可以看成是一种“无监督学习”(unsupervision learning)，文本聚类的特点是“先有元素后有类”，完全根据元素的信息来进行分类。事实上，信息聚类的方法起源于数据分析和数据挖掘3的研究。聚类分析的目的是把一个给定

21、的数据对象集合分成不同的簇(cluster)。簇是相似数据对象的集合，在同一个类中，对象之间具有相似性；不同类的对象之间是相异的。第11章 信息分类与聚类11.3.1 划分聚类法划分聚类法较流行的划分聚类方法(partitional algorithms)有动态聚类法(也称逐步聚类法)，如k-均值(k-means)算法、k-中心点算法。其基本思想为：随机选择k个对象，每个对象初始地代表一个类的平均值或中心，对剩余每个对象，根据其到类中心的距离，被划分到最近的类；然后重新计算每个类的平均值。不断重复这个过程，直到所有的样本都不能再分配为止。k-均值聚类法是一种常用的划分聚类法，它利用类的质心之间

22、的距离作为类间距离。下面以一个实际例子，来说明k-均值聚类法的过程。【例例11-3】在(X，Y)平面有表11-3给出的点，试对它们进行聚类。第11章 信息分类与聚类第11章 信息分类与聚类解：解：在此例中，每个对象都有2个特征，分别表示在X轴和Y轴上。第一步：k=3，随机选取3个类的中心，分别用k1、k2、k3表示，如图11-1所示。为了将点指派到最近的中心，通常可以用欧几里得距离表示欧氏空间中的点，用余弦值表示文档间距离，用公式(11-1)计算类中心。第二步：对于所有对象，根据其到k1、k2、k3之间的距离，划分到相应的类中。然后重新计算每个类的质心。此时的k1、k2、k3与第一步中的值已经

23、不同了，如图11-2所示。第11章 信息分类与聚类图11-1 各类的中心点第11章 信息分类与聚类图11-2 各类的质心第11章 信息分类与聚类第三步：此为第一次聚类后的情况，如图11-3所示。图11-3 第一次聚类结果第11章 信息分类与聚类第四步：对于所有对象，根据其到k1、k2、k3之间的距离，继续划分到相应的类中。然后重新计算每个类的质心，如图11-4所示。第五步：重复“分类”“计算新的质心”“分类”“计算新的质心”这样的过程，直到分类情况不再变化为止。以下为最终的聚类情况，如图11-5所示。第11章 信息分类与聚类图11-4 重新计算各类的质心第11章 信息分类与聚类图11-5 最终

24、聚类结果第11章 信息分类与聚类总之，划分聚类法的特点为：k需要事先定好；创建一个初始划分，再采用迭代的重定位技术；不必确定距离矩阵；时间复杂度为O(n)，比层次聚类法运算量要小，适用于处理庞大的样本数据；适用于发现球状类。划分聚类法的缺陷是：不同的初始值，结果可能不同；有些k-均值算法的结果与数据输入顺序有关，如在线k-均值算法；用爬山法(hill-climbing)来寻找最优解，容易陷入局部极小值。第11章 信息分类与聚类11.3.2 层次聚类法层次聚类法层次聚类法(hierarchical method)也称为系统聚类法，它对给定的数据进行层次的分解。层次聚类法又可分为凝聚的(agglo

25、merative，bottom-up)的方法与分裂的(divisive，top-down)方法。凝聚的方法一开始将每个对象单独地看做一类，然后根据同类相近，异类相异的原则，合并类，直到所有的类并成一个，或达到一个终止条件为止。分裂的方法一开始将所有的对象置于一类，在迭代的每一步中，一个类不断地分为更小的类，直到每个对象在单独的一个类中，或达到一个终止条件。第11章 信息分类与聚类设共有N个元素需要聚类，计算所有元素两两间的距离，共有C2N个，MNN为元素之间的距离矩阵。显然，MNN为一个对称矩阵，且MNN的所有对角元素均为0。层次聚类法的基本流程如下：(1)把每个元素当成一个类，则初始时，系统

26、一共存在N个类，每个类中只含有一个元素，这些类的类间距离等于其包含的元素之间的距离。(2)找到最接近(距离最小)的两个类，将这两个类合并为一个类，现在系统中类的总数目将减少1。(3)计算合并成的新类与其他旧类之间的距离。(4)重复步骤(2)与(3)，直到所有的元素都合并成为了一个类。第11章 信息分类与聚类由此过程可见，每次合并都将使得系统中类的数目减少1，经过N-1次合并，则原来的N个元素就聚合成为一类了，聚类过程也就结束了。在聚类的过程中，将会产生一个层次结构的树状图，这也是层次聚类法这个名字的由来。步骤(3)中的类间距离有多种计算方式，如最小距离、最大距离、重心距离、类平均距离等，关于类

27、间距离的详细介绍请参见11.1.4节。层次聚类法的特点为：(1)类的个数不需事先定好；(2)聚类的效果较好；(3)需确定距离矩阵；(4)时间复杂度至少是O(N2)，运算量较大，扩展性不佳，适用于处理小样本数据。第11章 信息分类与聚类11.3.3 其他聚类方法其他聚类方法除了划分聚类法和层次聚类法之外，还有一些其他的聚类方法。这些聚类方法有其自身的特点，可以根据需要独立运用于信息聚类中，也可以用来补充划分聚类法和层次聚类法的不足。比如，基于距离的方法比较适合发现聚集球状类，基于密度的方法(density-based method)可以用来识别任意形状的类。第11章 信息分类与聚类在基于密度的方

28、法中，只要临近区域的密度超过一定的阈值，就继续聚类，所以这种方法可以过滤噪声和孤立点(outlier)，发现任意形状的类。基于网格的方法(grid-based method)把样本空间量化为有限数目的单元，形成一个网络结构，聚类操作都在这个网格结构(即量化空间)上进行。基于模型的方法(model-based method)为每个类假定一个模型，寻找数据对给定模型的最佳拟合。在此不详述这些聚类方法，有兴趣者可以参阅相关书籍。第11章 信息分类与聚类11.4 分类方法分类方法与聚类不同的是，分类之前，已经有分类知识和类别信息。在很多分类的应用中，已经知道了目标数据需要分成哪些类。文本分类是指在给定

29、分类体系下，根据文本内容自动确定文本类别的过程。文本分类的过程一般包括特征提取、特征选择、分类判决的过程，如图11-6所示。第11章 信息分类与聚类图11-6 自动分类的一般过程第11章 信息分类与聚类在整个文本分类过程中，分类算法是文本分类的核心。目前文本分类的算法有很多种，包括朴素贝叶斯算法(Nave Bayes)、k近邻法(kNN)、决策树算法、决策规则算法、回归模型、Rocchio算法、神经网络算法(NN)、支撑矢量机(SVM)、线性最小二乘方估计(LLSF)和分类器集成方法等，总体来说，分类算法大致可归结为两大类：参数类型和非参数类型。参数类型的分类方法使用训练数据集估计各参数，然后

30、利用估计的参数值进行分类判断。朴素贝叶斯算法是典型的参数类型分类法。第11章 信息分类与聚类非参数类型的分类法还可以分为两类：基于示例和基于样本。基于示例的方法是从每个类别的训练集中抽取或建立一个示例作为该类别的代表，示例用加权特征词组成的特征向量来表示。若共有N个类别，则建立N个特征矢量作为各个类别的示例，未知类别的文档通过与各个类别示例相比较来进行分类，Rocchio方法属于该类方法。而基于样本的方法将未知类别的文档看做是对于训练集的一个查询，它从训练集合中得到多个已知类别样本，这些样本的类别作为未知文本的候选样本。k近邻法就是一种基于样本的方法。下面介绍几种常用的分类方法。第11章 信息

31、分类与聚类11.4.1 Nave Bayes算法算法朴素贝叶斯(NaIve Bayes，NB)算法是机器学习领域中最常见的一种基于概率的算法。它建立在类条件独立的朴素假设之上，即假设文本中的各个特征项属于特定类别的概率相互独立。该算法计算待分类实例属于各个类别的后验概率，取后验概率最大的类别作为所属类别。假设存在一些类别：C1，C2，Cn，E是一个实例的特征描述，现在要判断该实例属于哪个类别，即求P(Ci|E)。根据贝叶斯定理，有(11-16)()|()()|(EPCEPCPECPiii第11章 信息分类与聚类假设各类是独立的，则有1)|(1ECPnii(11-17)niiiCEPCPEP1)

32、|()()(需要知道先验概率P(Ci)和条件概率P(E|Ci)，才能计算后验概率P(Ci|E)。P(Ci)可以从数据中估计得来，假设在样本空间D中，类别Ci中有ni个样本，总的样本数是|D|，则可以估计P(Ci)为(11-18)|)(DnCPii第11章 信息分类与聚类再假设实例是由一系列独立的特征来表述的，关于给定类别的条件概率也是独立的：(此处最好准确重述一下，这个条件独立性假设即朴素贝叶斯假设。其最大作用在于NB假设下计算联合分布时简单可行。)(11-19)|()|()|(121mjijimicePceeePcEP【例例11-4】根据统计，天气情况和几种特征有如表11-4所示的关系。假定

33、当前天气特征为有乌云，刮大风，没有闪电，试估计当前的天气情况。第11章 信息分类与聚类第11章 信息分类与聚类解：解：当前特征：E=乌云，大风，闪电)(0089.0)(99.01.01.09.0)|(EPEPEP晴天)(01.0)(3.08.09.005.0)|(EPEPEP晴天)(019.0)(6.07.09.005.0)|(EPEPEP晴天P(E)=0.0089+0.01+0.019=0.0379因此，P(晴天|E)=0.23，P(雨天|E)=0.26，P(阴天|E)=0.50。按朴素贝叶斯方法判断，当前最可能的天气情况为阴天。将朴素贝叶斯应用于文本分类。需要假设文本中的各个特征项属于特定

34、类别的概率相互独立。该算法计算文本属于各个类别的后验概率，取后验概率最大的类别作为文本类别。第11章 信息分类与聚类假设文本d属于类别Cj的后验概率为P(Cj|d)，可以由公式(11-20)计算。(11-20)()()|()|(dPCPCdPdCPjjj由于P(d)代表文档d的先验概率，对所有类别为常数，则有)()|(maxarg)|(maxargjjCjCCPCdPdCPjjjkkjCdtdtNjkjCCtPCP),()|()(maxarg式中：P(Cj)代表训练集中类别Cj的先验概率；P(d|Cj)代表假设为类别Cj时观察到d的概率；P(tk|Cj)代表类别Cj中特征tk出现的频率；N(t

35、k，d)代表在文档d中特征tk出现的次数。各概率计算公式如下：(11-21)第11章 信息分类与聚类(11-22)|)(DDCPjj|1|1|1),(|),(1)|(VsDiisDiikjkjjdtNVdtNCtP(11-23)式中：|Dj|代表类别Cj中的训练文档数;|D|代表所有的训练文档数;N(tk，di)代表在训练文档di中特征tk出现的次数;|V|代表所有的特征数目。式(11-23)中，分子表示类别Cj中特征tk出现的次数，分母表示类别Cj中所有特征出现的总次数，并对分子和分母进行了平滑处理，避免出现零概率。第11章 信息分类与聚类在训练时，先对训练数据根据公式(11-22)和(11

36、-23)计算各个类别的P(Cj)和P(tk|Cj)。当待分类文本d到达时，再根据公式(11-21)计算出该文本的类别。理论上讲，贝叶斯分类具有最小的出错率。然而，实践中并非总是如此，这是由于对其应用的假定(如类条件独立性和特征独立性)的不准确性所造成的。朴素贝叶斯算法描述如下：第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|)测试：

37、已知一个测试集XN是X中词汇出现的次数，得到分类为第11章 信息分类与聚类其中，j是测试集X中第j个位置出现的词。【例例11-5】有如表11-5所示的训练集和测试集，请问测试集中的文档D5应该归属于哪一类？njijiCiCCPCP1)|()(maxarg第11章 信息分类与聚类第11章 信息分类与聚类解：解：用朴素贝叶斯算法，先计算“Yes”和“No”两个类的先验概率：41(No),43(Yes)PP测试集包含的词汇V=Chinese，Japan，Tokyo，对这几个词项计算关于两个类别的条件概率：926311no)|P(Japanno)|P(Tokyo926311no)|P(Chinese1

38、416810yes)|P(Japanyes)|P(Tokyo736815yes)|P(Chinese第11章 信息分类与聚类对文档D5，计算关于每个类别的后验概率：0.0001)92()92()92(41)D|P(no0.0003)141()141()73(43)D|P(yes3535因此文档D5属于类别Yes。第11章 信息分类与聚类11.4.2 kNN算法算法kNN法是基于样本(Instance-Based)的算法，该算法首先对训练集文本进行向量化，得到各文本的特征向量。当待分类文本到达后，进行向量化，得到特征向量，然后计算该向量与每个训练文本向量的距离，找到与该文本相似度最近的k个文本。

39、在这k个文本中，哪个类别的文本数最多，待分类文本就属于哪个类别。相似度的计算公式如下：(11-24)|12,|12,|1,)(),sim(VkkjVkkiVkkjkijiwwwwdd kNN算法可由图11-7形象地表示。第11章 信息分类与聚类图11-7 kNN分类第11章 信息分类与聚类假设有两个类别，k值取5，当一个未知文档d1到达时，计算该文档与每个训练文档的相似度，得到最近的5个训练文档，4个属于类别A，1个属于类别B，则文档d1判为类别A。同理，文档d2判为类别B。如果考虑相似度的量化值，可以改进kNN算法的判别方法。计算文档关于类别的权重：(11-25),(),sim()|scor

40、e(jiikxdCdIdxxCi个邻居的这里，x是一个新的点，Cj是已知类别，di是x的k个最近的邻居点，sim(x，di)是x和di的相似度。而I(di，Cj)为类别属性函数，即如果di属于类Cj，那么函数值为 1，否则为 0。第11章 信息分类与聚类比较类的权重，将文本分到权重最大的那个类别中。kNN法的缺点就是k值不好确定，传统上要进行一系列实验来比较不同k值所产生的结果，从而得到最优的k值。并且大量的计算在分类时进行，当训练文本集很大时，会导致分类耗时较多。(11-26)否则属于类别当且仅当 0 1),(jijiCdCdI第11章 信息分类与聚类kNN的算法描述如下：1 根据特征项集合

41、重新描述训练文本向量。2 在新文本到达后，根据特征词分词新文本，确定新文本的向量表示。3 在训练文本集中选出与新文本最相似的k个文本，计算公式为(11-24)。其中，k值的确定目前没有很好的方法，一般采用先定一个初始值，然后根据实验测试的结果调整k值，一般初始值定为几百到几千之间(并非定论，可以不提此句)。第11章 信息分类与聚类4 在新文本的k个邻居中，依次计算每类的权重，计算公式为(11-25)。5 比较类的权重，将文本分到权重最大的那个类别中。【例例11-6】假定通过计算某文档与训练集文档的相似度，得出表11-6(k=10)。第11章 信息分类与聚类第11章 信息分类与聚类11.4.3

42、Rocchio算法算法Rocchio算法是一种典型的基于示例的算法。它首先为每个类别建立一个代表矢量，当一个待分类文档到达后，计算该文档矢量和类别代表矢量的距离，取距离最小的类别作为文档所属类别4。Rocchio分类器是基于向量空间模型和最小距离的方法。此方法起初应用于信息检索系统中，后来最早由Hull在1994年应用于分类5,此后，Rocchio方法就在分类中广泛应用起来。Rocchio计算公式为(11-27)CCdijCCdijicnnwnwwjj第11章 信息分类与聚类式中：wic为类C中心向量的权重；为训练样本中正例的控制参数；为训练样本中反例的控制参数；nC为训练样本中类别C的正例数

43、目；n为训练样本的文档数；和是两个控制参数，可以通过提高，降低来削弱反例的影响。当1，0时，wic为正例的质心。文档di与类别C的距离度量公式为(11-28)2,2,)()CSV(jijcjijcicidwdwdwd假定有n个文档类别记为C1，C2，Cn，训练过程的算法描述如下：第11章 信息分类与聚类循环：i从1到 n，令pi=(初始化原型向量)对每一个训练样本D 令d是文档x的归一化TF-IDF权重矢量 i=j(Cj=C(x)(某类文档向量之和形成原型向量pi)pi=pi+d第11章 信息分类与聚类给定测试文档 x，分类过程的算法描述如下：令d是文档x的归一化TF-IDF权重矢量m=2(初

44、始化最大的余弦相似度)循环：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)属于哪类文档？第11章 信息分类与聚类第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类。第11章 信息分类与聚类11.4.4 SVM算法算法支撑向量机

45、(Support Vector Machines，SVM)是Vapnik为了解决两层模式识别问题于1995年提出来的6。SVM基于结构风险最小化(Structural Risk Minimization)原理，这个方法定义在一个矢量平面上，问题就是找到一个决定平面可以最优地把数据点分割成两类。为了定义“最优”分割，需要引入“间隔”(Margin)的概念。图11-8解释了这个想法。为了简便，图中只显示了在二维空间上线性分割数据点，但是这种思想可以推广到多维空间，并且对数据点可以不是线性分割。在一个线性分割空间中的分割平面是一个超平面，每组平行线间的距离叫做“间隔”。SVM的难点就是在训练集中找到

46、分割平面i，并且最大化间隔。第11章 信息分类与聚类图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的范数平方为最小。第11章 信息分类与聚类对线性可分数据集

47、而言，SVM的一个有趣的特性是分割平面仅由来自决定平面的等于距离1/w的数据点(图11-8中带框的点)决定。这些点叫做支撑向量(Supporting Vector)，是训练集中唯一有效的元素。如果除掉所有的其他点，算法具有同样的分类功能。这个特性使得SVM在理论上是独特的，和其他方法都不同，如kNN、LLSF、NN和NB都是使用训练集中的所有数据点来优化分类功能。【例例11-8】图11-9所示三个训练点坐标分别为(1，1)、(2，0)和(2，3)，分属两个类别，求两个类别的决定平面及最大间隔。第11章 信息分类与聚类图11-9 训练点分布图第11章 信息分类与聚类解：解：具有最大边缘的权重向量

48、平行于两个类的最短连接线，即(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)，所以有16212baabaa解得：54,52,511,52wba第11章 信息分类与聚类最大间隔为5251625422wSVM的求解实际上是一个优化问题，因此可以引入拉格朗日乘子(Lagrange multiplier)i来求解。分类函数表示为(1

49、1-32)sign()(bxxyxHiTiii当指定数值表达式的值为正或负时，sign函数分别返回 1或1，+1表示属于一个类别，1表示属于另一个类别。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)li1maxlj 1第11章 信息分类与聚类对于线性不可分的情况，可以把样本X 映射到一个高维特征空间H，并在此空间中运用原空间的函数来实现内积运算，这样将非线性问题转换成另一空间的线性问题。(最

50、好明确一下核函数定义和作用)常用的内积核函数有下面三种。(1)多项式函数：(11-33)pjijixxxxK)1(),(这样得到的是p阶多项式分类器。(2)径向基函数(Radial Basis Function，RBF)，也称高斯核函数：(11-34)2exp(),(22jijixxxxK第11章 信息分类与聚类(3)Sigmoid函数：(11-35)tanh(),(jijixkxxxK这里，k是增益，是阈值。【例例11-9】使用SVM解决XOR分类问题，XOR值域及其分布如图11-10所示。解：解：使用多项式核函数K(x1，x2)=(1+x1x2)2进行变换，也就是可以表示为 表11-8给出