机器学习及数据挖掘常用技术4天版

1、第二章 机器学习及数据挖掘常用技术,王斌 中国科学院信息工程研究所,大数据核心技术之数据挖掘与机器学习技术探索及应用,目录,分类基本概念,课前思考题,中文文本分词如何看成分类问题？ 人脸识别如何看成分类问题？,什么是分类？,简单地说，分类(Categorization or Classification)就是按照某种标准给对象贴标签(label),男,女,为什么要分类？,人类社会的固有现象：物以类聚、人以群分 相似的对象往往聚集在一起 (相对而言)不相似的对象往往分开 方便处理！,分类非常普遍,性别、籍贯、民族、学历、年龄等等，我们每个人身上贴满了“标签” 我们从孩提开始就具有分类能力：爸爸、

2、妈妈；好阿姨、坏阿姨；电影中的好人、坏人等等。 分类无处不在，从现在开始，我们可以以分类的眼光看世界,文本分类,文本分类(Text classification或者 Text Categorization)：给定分类体系(还有训练语料)，将一篇文本分到其中一个或者多个类别中的过程。 分类体系：随应用不同而不同。比如：垃圾 vs. 非垃圾、体育/经济/军事 等等 文本分类的类型： 按类别数目： binary vs. multi-class：二类问题 vs. 多类问题 按每篇文档赋予的标签数目： sing label vs. multi label：单标签 vs. 多标签问题,一个文本分类任务：垃

3、圾邮件过滤,From: Subject: real estate is the only way. gem oalvgkay Anyone can buy real estate with no money down Stop paying rent TODAY ! There is no need to spend hundreds or even thousands for similar courses I am 22 years old and I have already purchased 6 properties using the methods outlined in thi

4、s truly INCREDIBLE ebook. Change your life NOW ! = Click Below to order: = 如何编程实现对上类信息的识别和过滤？,分类示意图,分类方法之一: 手工方法,Web发展的初期，Yahoo使用人工分类方法来组织Yahoo目录，类似工作还有： ODP、PubMed等 优点： 如果是专家来分类精度会非常高 如果问题规模和分类团队规模都很小的时候，能够保持分类结果的一致性 缺点： 代价昂贵 难以进行规模扩展 因此，需要自动分类方法,分类方法之二: (人工撰写)规则的方法,Google Alerts的例子是基于规则分类的 存在一些IDE

5、开发环境来高效撰写非常复杂的规则 (如 Verity) 通常情况下都是布尔表达式组合 (如Google Alerts) 优点： 如果规则经过专家长时间的精心调优，精度会非常高 可解释性好 缺点： 建立和维护基于规则的分类系统非常繁琐 开销大,一个Verity主题 (一条复杂的分类规则),分类方法之三: 统计/概率方法,文本分类被定义为一个有监督的学习问题，包括： (i) 训练(training)：通过有监督的学习，得到分类函数，然后将其 (ii) 测试/应用/分类(test)：应用于对新文档的分类 优点： 速度快，扩展性强，效果好 不需要专家 缺点： 需要手工构建训练集(但是普通人即可) 有些

6、方法解释性差,分类流程,课堂思考题,中文文本分词如何看成分类问题？ 人脸识别如何看成分类问题？,特征选择(Feature Selection),本讲义只介绍特征选择，分类中还可以进行特征变换(Feature Transformation),特征选择,文本分类中，通常要将文本表示在一个高维空间下，每一维对应一个词项 本讲义中，我们不特意区分不同的概念: 每个坐标轴 = 维 = 词语 = 词项 = 特征 许多维上对应的词(如某些罕见词)对分类作用不大，有时可能会误导分类器，这些特征称为噪音特征（noise feature） 去掉这些噪音特征会同时提高文本分类的效率和效果，该过程称为特征选择（fea

7、ture selection）,噪音特征的例子,比如我们将对文本是否属于China类进行判断 假定某个罕见词项，比如 ARACHNOCENTRIC，没有任何关于 China 类的信息 . . . 但是在训练集中，ARACHNOCENTRIC的所有出现正好都在 China这个类别中 这种情况下，我们就可能训练得到一个分类器，它认为 ARACHNOCENTRIC标志着类别 China的出现 这种从训练集中的偶然现象学习得到的一般化结果称为过学习(overfitting) 特征选择能减少过学习的可能性，提高分类器的精度,基本的特征选择算法,对类别c，选择得分靠前的k个特征,特征选择所考虑的因素,类内

8、代表性：该特征应该是类别当中的典型特征 偶尔出现1到2次的特征不是好特征 类间区别性：该特征在多个类别当中具有区分性 比如每个类中都频繁出现的特征不是好特征,不同的特征选择方法,特征选择方法主要基于其所使用特征效用(Utility)指标来定义，即定义特征对于分类的有用程度。 常用特征效用指标： 频率法 (DF) 选择高频词项 信息增益(IG-information gain) 卡方(Chi-square),频率法,基于DF的选择方法 (DF Thresholding) 去掉类别当中词项的DF小于某个阈值的特征去掉(太少，没有代表性) 实现十分简单，现有实验效果还不错,信息增益,信息增益(Inf

9、ormation Gain, IG)：该特征为整个分类所能提供的信息量(不考虑任何特征的熵和考虑该特征后的熵的差值),信息增益的计算例子,P(c1)=(49+141)/(49+141+27652+774106)=190/801948 P(c2)=1-P(c1)=801758/801948 P(t)=(49+27652)/801948=27701/801948 P( )=1-P(t)=774247/801948 P(c1|t)=49/(49+27652)=49/27701 P(c2|t)=1-P(c1|t)=27652/27701 P(c1| )=141/(141+774106)=141/774

10、247 P(c2| )=1-P(c1| )=774106/774247 于是，有： Entropy(S)=-P(c1)log2P(c1)-P(c2)log2P(c2) Expect Entropy(St)=P(t)-P(c1|t)log2P(c1|t)-P(c2|t)log2P(c2|t) +P( )-P(c1| )log2P(c1| )-P(c2| )log2P(c2| ) ,期望互信息(Expected Mutual Information),词项t 和类别 c的期望互信息(Expected Mutual Information, EMI)计算如下 MI给出的是词项所包含的有关类别的信息及

11、类别包含的有关词项的信息量 比如，如果词项的出现与否与类别独立(不同类别中包含和不包含词项的文档比例完全一样) 2类情况下 IG=MI,MI 特征选择的结果,卡方法,2 统计量(卡方统计量)：度量两者(词项和类别)独立性的缺乏程度， 2 越大，独立性越小，相关性越大(下面N=A+B+C+D),朴素贝叶斯: 特征选择的效果,(multinomial = 多项式朴素贝叶斯） binomial= 贝努利朴素贝叶斯),不同特征选择方法的比较,参考 Yiming Yang,Jan O. Pedersen: A Comparative Study on Feature Selection in Text

12、Categorization.ICML1997:412-420,特征选择 vs. 特征权重计算,特征选择：给定类别c、词汇表的情况下，通过给每个打分，选出得分靠前的特征，这里的分表示t与类别c的紧密程度 特征权重：给定文档集合，对每篇文档d中的特征t，给出的t在d中的权重。 两者不是一回事。有人在分类中，将两者结合为特征的权重。,关于特征选择,每个类别选前k个特征，k怎么定？ 交叉验证法(后面会讲) 通常画出随k变化分类效果变化的曲线 每个类别选的特征数目能不能不是固定的？ 可以采用阈值截断法 每个类别选出来的特征要不要合在一起形成全局特征空间？ 需要仔细分析。 一直困扰我很久，现在似乎好像大

13、概想明白了。,文本分类的评价,评价示意图,分类评价,评价必须基于测试数据进行，而且该测试数据是与训练数据完全隔离的 (通常两者样本之间无交集) 很容易通过训练可以在训练集上达到很高的性能 (比如记忆所有的样本集合) 指标：正确率、召回率、 F1值、分类精确率(classification accuracy)等等,正确率P 及召回率 R,正确率 Precision = TP / (TP + FP) 召回率 Recall = TP / (TP + FN) 精确率 Accuracy = (TP+TN)/(TP + FP + FN + TN),一个计算的例子,正确率Precision = 100 /

14、(100 + 50) 召回率Recall = 100 / (100 + 40) 精确率 Accuracy = (100+80)/(100 + 50 + 40 + 80),整个文档集合的划分,TP,TN,FP,FN,未返回的该类文档,返回的该类文档,返回的非该类文档,真正属于该类,真正不属于该类,未返回(即认为不是该类),系统返回(即判定为该类),整个文档集合,未返回的非该类文档,关于正确率和召回率的讨论(1),“宁可错杀一千，不可放过一人”偏重召回率，忽视正确率。冤杀太多。 判断是否有罪： 如果没有证据证明你无罪，那么判定你有罪。召回率高，有些人受冤枉 如果没有证据证明你有罪，那么判定你无罪。

15、召回率低，有些人逍遥法外,关于正确率和召回率的讨论(2),虽然Precision和Recall都很重要，但是不同的应用、不用的用户可能会对两者的要求不一样。因此，实际应用中应该考虑这点。 垃圾邮件过滤：宁愿漏掉一些垃圾邮件，但是尽量少将正常邮件判定成垃圾邮件。即尽量减少误判率，提高正确率。 特定疾病检测：宁愿误判一些健康人，也不漏掉一个病人。即尽量降低漏判率，提高召回率。,关于精确率(Accuracy),在类别不均衡的情况下，要慎重看待该指标,正确率Precision = 100 / (100 + 50) 召回率Recall = 100 / (100 + 40) 精确率 Accuracy =

16、(100+10000)/(100 + 50 + 40 + 10000) =99.1%,F值(F Measure),F1 允许在正确率和召回率之间达到某种均衡 也就是P和R的调和平均值 :,其他评价方法,混淆矩阵：将前面的2*2矩阵推广到N*N矩阵 ROC曲线,关于训练集和测试集,给定一个已标注好的数据集，将其中一部分划为训练集(training set)，另一部分划为测试集(test set)。在训练集上训练，训练得到的分类器用于测试集，计算测试集上的评价指标。 另一种做法：将上述整个数据集划分成k份，然后以其中k-1份为训练集训练出一个分类器，并用于另一份(测试集)，循环k次，将k次得到的评

17、价指标进行平均。这种做法称为k折交叉验证(k-cross validation)。如果k=数据集的大小，则称留一法(leave-one-out)。 有时，分类器的参数需要优化。此时，可以仍然将整个数据集划分成训练集和测试集，然后将训练集分成k份(其中k-1份作为训练，另一份称为验证集validation set，也叫开发集)，在训练集合上进行k折交叉验证，得到最优参数，然后将得到参数后的分类器应用于测试集。,关于训练集和测试集,训练集,测试集,训练+测试,训练集,开发集,测试集,k折交叉验证,参数确定,微平均 vs. 宏平均,上面对于一个类得到评价指标P、R、F1，但是我们希望得到分类器在所有

18、类别上的综合性能 宏平均(Macro-averaging)：以类别为单位 对类别集合C 中的每个类都计算一个P、R、F1值 对|C|个结果求算术平均 微平均(Micro-averaging)：以类别-文档对为单位 对类别集合C 中的每个类都计算TP、FP和FN 将C中的这些数字累加 基于累加的TP、FP、FN计算P、R和F1,朴素贝叶斯 vs. 其他方法,朴素贝叶斯(Nave Bayes),朴素贝叶斯分类器,朴素贝叶斯是一个概率分类器 文档 d 属于类别 c 的概率计算如下： nd 是文档的长度(词的个数) P(tk |c) 是词项tk 出现在类别c中文档的概率 P(tk |c) 度量的是类别

19、c中tk 的贡献 P(c) 是类别c的先验概率 如果文档的词项无法提供属于哪个类别的信息，那么我们直接选择P(c)最高的那个类别 独立性假设：P(d|c)=P(t1|c)P(t2|c)P(tnd|c),独立性假设,具有最大后验概率的类别,朴素贝叶斯分类的目标是寻找“最佳”的类别 最佳类别是指具有最大后验概率(maximum a posteriori -MAP)的类别 cmap:,对数计算,很多小概率的乘积会导致浮点数下溢出 由于 log(xy) = log(x) + log(y), 可以通过取对数将原来的乘积计算变成求和计算 由于log是单调函数，因此得分最高的类别不会发生改变 因此，实际中常

20、常使用的是：,朴素贝叶斯分类器,分类规则: 简单说明: 每个条件参数 是反映tk 对c的贡献高低的一个权重 先验概率 是反映类别c的相对频率的一个权重 因此，所有权重的求和反映的是文档属于类别的可能性 选择最具可能性的类别,参数估计 : 极大似然估计(MLE),如何从训练数据中估计 和 ？ 先验: 其中，Nc : 类c中的文档数目; N: 所有文档的总数 条件概率: 其中，Tct 是训练集中类别c中的词条t的个数 (多次出现要计算多次) 给定如下的 位置独立性假设(positional independence assumption):,MLE估计中的零概率问题,P(China|d) P(Ch

21、ina) P(BEIJING|China) P(AND|China) P(TAIPEI|China) P(JOIN|China) P(WTO|China),MLE估计中的零概率问题（续）,如果 WTO 在训练集中没有出现在类别 China中，那么就会有如下的零概率估计： 那么，对于任意包含WTO的文档d，P(China|d) = 0。 一旦发生零概率，将无法判断类别,避免零概率: 加一平滑,平滑前： 平滑后: 对每个量都加上1 其中，B 是不同的词语个数 (这种情况下词汇表大小 |V | = B),避免零概率: 加一平滑（续）,利用加1平滑从训练集中估计参数 对于新文档，对于每个类别，计算 (

22、i) 先验的对数值之和以及 (ii) 词项条件概率的对数之和 将文档归于得分最高的那个类,一个例子,估计朴素贝叶斯分类器的参数 对测试文档进行分类,例子: 参数估计,上述计算中的分母分别是 (8 + 6) 和 (3 + 6)，这是因为textc 和 (分别代表两类文档集的大小)的大小分别是8和3，而词汇表大小是6。,例子: 分类,因此, 分类器将测试文档分到c = China类，这是因为d5中起正向作用的CHINESE出现3次的权重高于起反向作用的 JAPAN和TOKYO的权重之和。,朴素贝叶斯独立性假设不成立的情况,自然语言文本中，上述独立性假设并不成立 条件独立性假设: 位置独立性假设:

23、问题： 给出条件独立性假设不成立的例子 给出位置独立性假设不成立的例子 在这些假设都不成立的情况下，为什么朴素贝叶斯方法有用？,朴素贝叶斯方法起作用的原因,即使在独立性假设严重不成立的情况下，朴素贝叶斯方法能够高效地工作 例子 概率P(c2|d)被过低估计(0.01) ，而概率P(c1|d)被过高估计 (0.99)。 分类的目标是预测正确的类别，并不是准确地估计概率 准确估计 精确预测 反之并不成立!,朴素贝叶斯的时间复杂度分析,Lave: 训练文档的平均长度, La: 测试文档的平均长度, Ma: 测试文档中不同的词项个数 训练文档，V : 词汇表， 类别集合 是计算所有统计数字的时间 是从

24、上述数字计算参数的时间 通常来说: 训练时间是线性的，而测试时间也是线性的 (相对于测试文档长度而言) 因此： 朴素贝叶斯 对于训练集的大小和测试文档的大小而言是线性的。这在某种意义上是最优的。,朴素贝叶斯并不朴素,朴素贝叶斯在多次竞赛中胜出 (比如 KDD-CUP 97) 相对于其他很多更复杂的学习方法，朴素贝叶斯对不相关特征更具鲁棒性 相对于其他很多更复杂的学习方法，朴素贝叶斯对概念漂移(concept drift)更鲁棒(概念漂移是指类别的定义随时间变化) 当有很多同等重要的特征时，该方法优于决策树类方法 一个很好的文本分类基准方法 (当然，不是最优的方法) 如果满足独立性假设，那么朴素

25、贝叶斯是最优的 (文本当中并不成立，但是对某些领域可能成立) (训练和测试)速度非常快 存储开销少,补充说明-朴素贝叶斯的两种实现方式,基于多项式模型的实现方法：多项式模型中各单词类条件概率计算考虑了词出现的次数，多项式模型是一种以词作为计算粒度的方法。 每个不规则骰子代表一个类 骰子的每个面代表一个词 面的个数等于文本中的单词个数 每个类的一篇文本是通过投掷上述对应骰子产生的 基于贝努利模型的实现方法：贝努利模型不考虑词在文档中出现的次数，只考虑出不出现，因此在这个意义上相当于假设词是等权重的。贝努利模型是一种以文档作为计算粒度的方法。 每个类对应一堆硬币 每个硬币代表一个词 硬币的个数等于

26、单词的个数 类中的一篇文本是通过投掷对应类的所有硬币产生的,参考,中心向量法(也称Rocchio法),向量空间表示回顾,每篇文档都表示一个向量，每一维对应一个词项 词项就是坐标轴 通常都高维: 100,000多维 通常要将向量归一化到单位长度 如何在该空间下进行分类？,向量空间分类,同前面一样，训练集包含一系列文档，每篇都标记着它的类别 在向量空间分类中，该集合对应着空间中一系列标记的点或向量。 假设 1: 同一类中的文档会构成一片连续区域（contiguous region） 假设2: 来自不同类别的文档没有交集 接下来我们定义直线、平面、超平面来将上述不同区域分开,向量空间中的类别,文档*

27、到底是属于UK、China还是Kenya类？首先找到上述类别之间的分类面，然后确定文档所属类别，很显然按照图中分类面，文档应该属于China类 如何找到分类面并将文档判定给正确类别是下面要讨论的重点。,中心向量法：基本思想,计算每个类的中心向量(所有文档向量的算术平均向量) 将每篇测试文档分到离它最近的那个中心向量,其中 Dc 是所有属于类别 c 的文档， 是文 档d的向量空间表示,中心向量法的算法,中心向量法的性质,简单地将每个类别表示成其中心向量 中心向量可以看成类别的原型或代表(prototype) 分类基于文档向量到原型的相似度或距离来进行 并不保证分类结果与训练集一致，即得到分类器后

28、，不能保证训练集中的文档能否正确分类,中心向量法的时间复杂度,训练时间是线性的，而测试时间也是线性的 (相对于测试文档长度而言) 训练和测试速度很快,中心向量法 vs. 朴素贝叶斯,很多情况下，中心向量法的效果不如朴素贝叶斯 一个原因是，中心向量法不能正确处理非凸、多模式类别问题,中心向量法不能正确处理多模式类别问题,课堂练习: 对于左图的A、B两类分类问题，为什么中心向量法难以有效处理? A 是所有a的中心向量， B是所有b的中心向量 点o 离A更近 但是o更适合于B类 A 是一个有两个原型多模式类别 但是，在中心向量法中，每个类别只有一个原型,X,X,a,b,b,B,a,a,a,b,a,b

29、,A,b,b,b,b,b,b,b,a,a,O,a,a,a,a,a,a,a,a,a,a,a,a,a,b,b,b,a,a,a,a,K近邻法(kNN),kNN(k Nearest Neighbor)分类器,kNN 是另外一种基于向量空间的分类方法 该方法非常简单，也容易实现 在大多数情况下，kNN的效果比朴素贝叶斯和中心向量法要好 如果你急切需要一种精度很高分类器并很快投入运行 . . . . . 如果你不是特别关注效率 . . . . . . 那么就使用kNN,kNN分类,kNN = k nearest neighbors，k近邻 k = 1 情况下的kNN (最近邻): 将每篇测试文档分给训练集

30、中离它最近的那篇文档所属的类别。 1NN 不很鲁棒一篇文档可能会分错类或者这篇文档本身就很反常 k 1 情况下的kNN: 将每篇测试文档分到训练集中离它最近的k篇文档所属类别中最多的那个类别 kNN的基本原理: 邻近性假设 我们期望一篇测试文档d与训练集中d周围邻域文档的类别标签一样。,概率型kNN,kNN的概率型版本: P(c|d) = d的最近的k个邻居中属于c类的比例 概率型kNN: 将d分到具有最高概率P(c|d)的类别c中,概率型kNN,对于 对应的文档，在1NN和 3NN下，分别应该属于哪个类？,kNN 算法,kNN的时间复杂度,kNN 测试时间复杂度与训练集的大小成正比! 训练集

31、越大，对测试文档分类的时间越长 在大训练集情况下，kNN效率较低,课堂练习,对于 对应的文档，在下列分类器下，分别应该属于哪个类: (i) 1-NN (ii) 3-NN (iii) 9-NN (iv) 15-NN (v) 中心向量法?,kNN: 讨论,优点： 不需要训练过程 但是，文档的线性预处理过程和朴素贝叶斯的训练开销相当 对于训练集来说我们一般都要进行预处理，因此现实当中kNN的训练时间是线性的。 当训练集非常大的时候，kNN分类的精度很高 缺点： 如果训练集很小， kNN可能效果很差。 需要确定参数k (可以采用多折交叉验证法) kNN倾向于大类，可以将相似度考虑在内。,kNN的快速实

32、现：KD-树,KD-树是K-dimension tree的缩写，是对数据点在k维空间（中划分的一种数据结构，主要应用于多维空间关键数据的搜索。本质上说，KD-树就是一种平衡二叉树。 例子： T1(2,3),T2(5,4),T3(9,6),T4(4,7),T5(8,1),T6(7,2)的KD-树,参考：李航，统计学习方法第3章,线性分类器(Linear Classifier),线性分类器(Linear Classifier),线性可分 vs. 非线性可分 线性分类器： 训练中确定所有的wi和参数 决策规则： 对于线性可分，必然存在线性分类面 =,N维空间下的二类线性分类器(N维超平面),一维,二

33、维,三维,中心向量分类器是一个线性分类器,中心向量分类器的线性分类面定义为： 其中 是向量 的法向量 请课后自己证明。,朴素贝叶斯也是线性分类器,多项式模型(本讲义所介绍的类型)下的二类朴素贝叶斯分类器也是线性分类器，其分类面定义为： 其中 , di = ti 在d中的出现次数， 1 i M, 注意：这里的ti指的是所有词汇表中的词项，而不是前面出现在文档d中的词项 请课后自己证明。,kNN不是线性分类器,kNN分类决策取决于k个邻居类中的多数类 类别之间的分类面是分段线性的 . . . 但是一般来说，很难表示成如下的 线性分类器,感知机(Perceptron),Threshold Logic

34、 Unit (TLU),. . .,w1,w2,wn,a=i=1n wi xi,1 if a q y= 0 if a q,y,输入,权重,activation,输出,q,Activation Functions,a,y,a,y,a,y,a,y,threshold,linear,piece-wise linear,sigmoid,Threshold as Weight,. . .,w1,w2,wn,wn+1,xn+1=-1,a= i=1n+1 wi xi,y,1 if a 0 y= 0 if a 0,q=wn+1,Perceptron Training Algorithm(错误驱动型),Repe

35、at for each training vector pair (x,t) evaluate the output y when x is the input if yt then form a new weight vector w according to w=w + a (t-y) x else do nothing end if end for Until y=t for all training vector pairs,a 为学习率,Perceptron Learning Rule,感知机的收敛性,在线性可分的情况下，可以证明感知机一定收敛(学习率要足够小) 取任意初值，感知机都

36、会收敛，但是不同初值，最后得到的超平面不一定相同 线性不可分的情况下，感知机不收敛，一般迭代到一定次数或者达到某个预定情形迭代结束，或者采用梯度下降策略。,多层感知机,input layer,hidden layer-可以有多层,output layer,支持向量机(Support Vector Machines),超平面的选择,线性可分的情况下分类面有无穷多个 那么不同的分类器选择方法不同,支持向量机,Support Vector,Optimal Separating Hyperplane,线性可分情况下，不仅要区分开，而且要使得间隔(Margin)最大。,Margin,H1:,H2:,小间

37、隔vs. 大间隔,如上图的训练样本,在线性可分的情况下,存在多个超平面(Hyperplane) (如 : H1,H2.)使得这两类被无误差的完全分开。超平面可以定义为：,其中W、都是向量，W是内积，b是标量。,超平面定义,最优超平面是指两类的分类间隔(Margin)最大，即每类距离超平面最近的样本到超平面的距离之和最大。距离这个最优超平面最近的样本被称为支持向量(Support Vector)。 优化问题：,最优超平面,Margin =,H1平面：,H2平面：,目标函数：,约束条件：,求解最优超平面就相当于，在下列约束条件下，求目标函数的最小值,目标函数:,约束条件:,最优超平面,可以通过求解

38、上述问题的对偶问题来得到最终的解。在对偶问题中，将原来需要求解的一系列wi转换成求解另一组变量i,求解原始问题,为求解原始问题，根据最优化理论，我们转化为对偶问题来求解,对偶问题,为原始问题中与每个约束条件对应的Lagrange乘子。这是 一个不等式约束条件下的二次函数寻优问题，存在唯一解,线性可分问题,计算 ，选择 的一个正分量 , 并据此计算,事实上， 的每一个分量 都与一个训练点相对应。而分划超平面仅仅依赖于 不为零的训练点 ，而与对应于 为零的那些训练点无关。,称 不为零的这些训练点的输入 为支持向量(SV),构造分划超平面 ,决策函数,根据最优解,求解结果,上述二次优化问题，采用La

39、grange方法求解 ，可得 相当于每个类别中选出若干支持向量组成“投票委员会”，根据这些“委员”的加权投票(内积)结果得到最终的类别归属,支持向量(Support Vector),非线性可分情况下的处理方法一,广义最优分类面方法：在线性不可分的情况下，就是某些训练样本不能满足上面的约束条件，因此可以在条件中增加一个松弛项(这种做法也称引入Soft Margin，软边界)，于是约束条件变成 :,此时的目标函数是求下式的最小值:,这个二次优化问题，同样可以应用Lagrange方法求解,正则项,经验风险,最优超平面求解,非线性可分情况下的处理方法二,变换到高维空间的支持向量机,采用如下的内积函数(

40、核函数)：,分类函数,支持向量机小结,SVM训练相对较慢，分类速度一般。但是分类效果较好。 在面对非线性可分情况时，可以引入松弛变量进行处理或者通过空间变换到另一个线性可分空间进行处理。 SVM有很多实现工具，SMO/SVM light/SVM torch/LibSVM等等。,一个SVM的例子几何法求解,最大间隔权重向量将和两类中距离最短的那条线段(直线)平行，即与连接点(1, 1)和(2, 3)的直线平行，这可以得到权重向量 (1,2). 最优的分类直线与上述线段垂直并相交与其中点(中垂线)，因此它经过点 (1.5, 2). 于是，可以求得SVM的决策直线方程为： y = x1 + 2x2

41、5.5,一个SVM的例子代数法求解,在约束条件 下，寻找最 小的 我们知道解的形式为： 于是有： a + 2a + b = 1, 2a + 6a + b = 1 解得， a = 2/5 及 b = 11/5 因此，最优超平面的参数为： b = 11/5. 此时间隔为：,其他分类方法,决策树(decision tree)方法,思想：将文本的特征进行优先度排序，并将每次的特征作为判定条件(子树的根节点)进行扩展，最后生成一颗树。 训练： 构造决策树：使用某个函数(如IG)来判断特征优先级 CART C4.5 (由ID3发展而来) CHAID 决策树的剪枝(pruning) 分类：按照决策树的条件进

42、行判定。,参考：李航，统计学习方法第5章,决策树的例子,决策树方法小结,决策树方法是一种规则方法，可以生成可以理解的规则(if then) 决策树方法会遇到过学习问题(Overfitting)：训练集合的样例都满足得较好，一推广则性能马上下降。 效果一般，但是有时很好。,回归方法,回归：用一条直线(线性回归)或者曲线去拟合已有的例子。 一种回归方法-LLSF(Linear Least Square Fit) 方法： |FA-B|, A是所有例子构成的矩阵，F是要求的权重矩阵，B是布尔矩阵，1表示属于该类，0表示不属于。 F求出以后，对新来的文本D，计算结果，哪个最大属于哪个类。,LLSF,举例

43、：2个类别c1,c2，4篇文档d1,d2,d3,d4分别属于c2,c1,c1,c2，3个特征t1,t2,t3，利用LLSF计算如下：,F,A,B,使|FA-B|最小，可以解得F矩阵。对一篇新文档d=a1,a2,a3T，Fd会得到一个2行一列的矩阵(实际是个向量)，哪个分量大则属于哪类。显然，LLSF可以直接处理多类问题，也能处理兼类问题。,LLSF小结,训练：计算类别权重矩阵F的过程，比较耗时。 分类：类别权重矩阵和文档向量相乘。 Yang Yiming通过实验证实LLSF的效果和kNN、SVM相当。,Yiming Yang and Xin Liu. A Re-examination of T

44、ext Categorization Methods. In Proceedings of the Twenty-Second International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR), pages 42-49, 1999.,基于投票的方法(集成方法),Bagging方法 训练R个分类器fi，分类器之间其他相同就是参数不同。其中fi是通过从训练集合中(N篇文档)随机取(取后放回)N次文档构成的训练集合训练得到的。 对于新文档d，用这R个分类器去分类，得到的最多的

45、那个类别作为d的最终类别 Boosting方法 类似Bagging方法，但是训练是串行进行的，第k个分类器训练时关注对前k-1分类器中错分的文档，即不是随机取，而是加大取这些文档的概率 AdaBoost AdaBoost MH,多类下的单标签和多标签问题,多类问题,前面介绍的都是二类问题 现实中大部分类别体系中类别的个数都不止2，这种情况的分类问题称为多类问题 如果有算法一次性考虑所有样本，通过求解一个多目标函数的优化问题，一次性得到多个分类面把空间划分为多个区域，每个区域对应一个类别。那么，事情就好办了。实际上这样的算法计算量太大无法实现。,通过二类分类器处理多类问题,1-V-R方式：4个类

46、别A、B、C、D，训练A vs BCD、B vs ACD、C vs ABD和D vs ABC四个二类分类器 分类器数目少，N个分类器 但是训练的样本数目大，还可能有非均衡问题 1-V-1方式：4个类别A、B、C、D，训练 A vs B, A vs C, A vs D, B vs C, B vs D, C vs D 六个二类分类器 分类器数目多，N(N-1)/2个分类器 但是每个分类器训练的样本数目小 LIBSVM采用了这种方式,各种处理方式的对比,余辉，赵晖，支持向量机多类分类算法新研究，计算机工程与应用，44(7):185-189, 212, 2008年7月,130,单标签问题（One-of

47、 problem）,单标签分类问题，也称single label problem 类别之间互斥 每篇文档属于且仅属于某一个类 例子：文档的语言类型 (假定：任何一篇文档都只包含一种语言),基于线性分类器的单标签分类(多类),对于单标签分类问题（比如A、B、C三类），可以将多个二类线性分类器(A vs BC、B vs AC、C vs AB)进行如下组合： 对于输入文档，独立运行每个分类器 将分类器排序 (比如按照每个分类器输出的在A、B、C上的得分) 选择具有最高得分的类别 也可以采用1-V-1方式，进行投票,多标签问题(Any-of problem),多标签分类问题，也称multi-label

48、 problem 一篇文档可以属于0、1或更多个类 针对某个类的决策并不影响其他类别上的决策 一种 “独立”类型，但是不是统计意义上的“独立” 例子：主题分类 通常：地区、主题领域、工业等类别之上的决策是互相独立的,基于线性分类器的多标签分类,对于多标签分类问题（比如A、B、C三类），可以将多个二类线性分类器(A vs BC、B vs AC、C vs AB)进行如下组合： 对测试文档独立地运行每个分类器 按照每个分类器自己的输出结果进行独立决策 采用1-V-1方式，也可以使用上述类似思路进行处理,文本分类的实际应用,文本分类,许多商业应用 “能够基于内容对文档进行自动分类的商业价值毋庸置疑，在

49、公司内网、政府机构及互联网出版等机构或领域中存在大量的潜在应用” 采用领域相关的文本特征在性能上会比采用新的机器学习方法获得更大的提升 “对数据的理解是分类成功的关键之一，然而这又是大部分分类工具供应商非常不擅长的领域。市场上很多所谓的通用分类工具并没有在不同类型的内容上进行广泛的测试。”,分类器的选择,当面对一个建立分类器的需求时，第一个要问的问题就是：训练数据有多少？ 一点都没有? 很少? 挺多? 量很大，而且每天都在增长?,如果没有任何训练数据,采用人工撰写规则的方法 实际中的规则要比这个例子长很多，并且可以采用更复杂的表示方式。经过精心调整（也就是说，人们可以在开发集上调整规则）之后，

50、利用这些规则分类的精度可以非常高。然而，要构造非常好的人工规则需要做大量的工作。一个基本合理的估计数字是每个类别需要两天的时间，由于类别中的文档内容会发生漂移，所以必须还要利用很多额外的时间去维护规则。,如果拥有较少的训练数据，又希望训练一个有监督的分类器,如何尽快地获得更多的标注数据 最佳方法：将自己也放入到标注的过程中去，在这个过程中人们自愿为你标注数据，并且这也是他们正常工作的一部分。,如果拥有训练数据,大规模高难度分类体系,如果文本分类问题仅包含少量具有区分度的类别，那么很多分类算法都可能取得很好的结果。但是实际的文本分类问题往往包含大量非常类似的类别。 对大量相近的类别进行精确分类是

51、一个固有的难题,分类研究趋势,更好的特征选择方法 非均衡分类问题 层次分类体系下的分类问题 大规模数据或分类体系下的高性能分类问题 面向领域的分类问题 情感分析 垃圾过滤 表示学习(Representation Learning),Sebastiani F., “Machine Learning in Automated Text Categorization”, ACM Computing Surveys, vol. 34 (1),2002, pp. 1-47.,苏金树,张博锋,徐昕.基于机器学习的文本分类技术研究进展.软件学报,2006,17(9):1848-1859,如何获得数据,数据分

52、成 未加工数据+加工(标注)后的数据 如何获得加工后的数据至关重要 人工标注：不可扩展，7万网页=￥200万，700万=？万 自动标注：精度问题 利用隐式标注：搜索中用户的点击、鼠标等行为，精度问题 众包法,众包技术,Jeff Howe对“众包”的定义是：“一个公司或机 构把过去由员工执行的工作任务，以自由自愿的形 式外包给非特定的（而且通常是大型的）大众网络的 做法众包的任务通常由个人来承担，但如果涉及到 需要多人协作完成的任务，也有可能以依靠开源的 个体生产的形式出现” 众包是一种公开面向互联网 大众的分布式的问题解决机制，它通过整合计算机 和互联网上未知的大众来完成计算机单独难以完成 的

53、任务。 众包能够利用大众力量、群体智慧，受到了学术界和工业界的广泛关注，可以用于分类标注等众多领域。,冯剑红，李国良，冯建华，众包技术研究综述，计算机学报，38(9):1713-1726, 2015年9月,众包的例子-Google图片标注,图片的标注是一个难题 2006年，CMU的Luis Von Ahn推出了一个著名的游戏，叫ESP Game，收集了5000万个标注结果。 该技术已经被Google所采用,日出,众包的例子-蛋白质组装,目录,聚类基本概念,课前思考题,网页内容自动抽取如何看成聚类问题？ 热点话题发现如何看成聚类问题？,聚类(Clustering)的定义,(文档)聚类是将一系列文

54、档按照相似性聚团成子集或者簇(cluster)的过程 簇内文档之间应该彼此相似 簇间文档之间相似度不大 聚类是一种最常见的无监督学习(unsupervised learning)方法 无监督意味着没有已标注好的数据集,一个具有清晰簇结构的数据集,提出一个算法来寻找该例中的簇结构,分类 vs. 聚类,分类: 有监督的学习 聚类：无监督的学习 分类：类别事先人工定义好，并且是学习算法的输入的一部分 聚类：簇在没有人工输入的情况下从数据中推理而得 但是，很多因素会影响聚类的输出结果：簇的个数、相似度计算方法、文档的表示方式，等等,聚类的例子：搜索结果的聚类,153,聚类的例子: Google New

55、s,课堂思考题,网页内容自动抽取如何看成聚类问题？ 热点话题发现如何看成聚类问题？,聚类的评价,怎样判断聚类结果的好坏?,内部准则(Internal criteria) 一个内部准则的例子： K-均值聚类算法的RSS值 但是内部准则往往不能评价聚类在应用中的实际效用 替代方法：外部准则(External criteria) 按照用户定义的分类结果来评价，即对一个分好类的数据集进行聚类，将聚类结果和事先的类别情况进行比照，得到最后的评价结果,外部准则,基于已有标注的标准数据集(如Reuters语料库)来进行聚类评价 目标：聚类结果和给定分类结果一致 (当然，聚类中我们并不知道最后每个簇的标签，而

56、只是关注如何将文档分到不同的组中) 一个评价指标：纯度(purity),外部准则: 纯度,= 1, 2, . . . , K 是簇的集合 C = c1, c2, . . . , cJ 是类别的集合 对每个簇 k : 找到一个类别cj ，该类别包含k中的元素最多，为nkj 个，也就是说k的元素最多分布在cj中 将所有 nkj 求和，然后除以所有的文档数目,纯度计算的例子,为计算纯度 maxj| 1 cj | = 5 (class x, cluster 1); maxj |2 cj | =4 (class o, cluster 2); maxj |3 cj | = 3 (class , clust

57、er 3) 纯度为 (1/17) (5 + 4 + 3) 0.71.,兰迪指数(Rand index),定义: 考虑所有两个文档之间(文档对)的关系，可以得到 2x2 的列联表： 总的文档对数目为TP+FN+FP+TN 对于N篇文档，总共有 个文档对 例子: = 136 每个文档对要么为positive或negative (聚类算法要么将这两个文档放在同一簇中，要么放在不同簇中) . . . . . . 聚类结果要么 “true” (correct) 要么 “false” (incorrect): 即聚类的结果要么正确要么不正确,兰迪指数：例子,回到上例，三个簇中分别包含6、6、5个点，因此处

58、于同一簇的文档对的个数为： 其中， 簇1中的x 对，簇2中的 o 对，簇3中的 对，以及簇3中的x 对，都是真正例： 于是, FP = 40 20 = 20。类似地，可以计算出FN和TN。,K-Means聚类算法,一个具有清晰簇结构的数据集,提出一个算法来寻找该例中的簇结构,聚类的要求,一般目标：将相关文档放到一个簇中，将不相关文档放到不同簇中 如何对上述目标进行形式化？ 簇的数目应该合适，以便与聚类的数据集相吻合 一开始，我们假设给定簇的数目为K。 后面会介绍确定K的半自动的方法 聚类的其它目标 避免非常小和非常大的簇 定义的簇对用户来说很容易理解 其它,扁平聚类 vs. 层次聚类,扁平算法 通过一开始将全部或部分文档随机划分为不同的组 通过迭代方式不断修正 代表算法：K-均值聚类算法 层次算法 构建具有层次结构的簇 自底向上(Bottom-up)的算法称为凝聚式(agglomerative)算法 自顶向下(Top-down)的算法称为分裂式(divisive)算法,扁平算法,扁平算法将N篇文档划分成K