第二章机器学习及数据挖掘常用技术剖析

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 oalvgkayAnyone can buy real estate with no money downStop paying rent TODAY !There is no need to spend hundreds or even thousands for similar coursesI am 22 years old and I have already purchased 6 properties using themethods outlined in this truly INC

4、REDIBLE ebook.Change your life NOW !=Click Below to order:http:/ 手工方法 Web发展的初期，Yahoo使用人工分类方法来组织Yahoo目录，类似工作还有： ODP、PubMed等 优点： 如果是专家来分类精度会非常高 如果问题规模和分类团队规模都很小的时候，能够保持分类结果的一致性 缺点： 代价昂贵 难以进行规模扩展 因此，需要自动分类方法分类方法之二: (人工撰写)规则的方法 Google Alerts的例子是基于规则分类的 存在一些IDE开发环境来高效撰写非常复杂的规则 (如 Verity) 通常情况下都是布尔表达式组合 (

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

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

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

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

9、现十分简单，现有实验效果还不错信息增益 信息增益(Information Gain, IG)：该特征为整个分类所能提供的信息量(不考虑任何特征的熵和考虑该特征后的熵的差值)111( )Entropy( )Expected Entropy()( )log( ) ( )(| )log( | )( )(| )log( | )MtiiiMMiiiiiiIG tSSP cP cP tP c tP c tP tP ctP ct 信息增益的计算例子c1c2t4927652141774106tP(c1)=(49+141)/(49+141+27652+774106)=190/801948P(c2)=1-P(c1

10、)=801758/801948P(t)=(49+27652)/801948=27701/801948P( )=1-P(t)=774247/801948P(c1|t)=49/(49+27652)=49/27701P(c2|t)=1-P(c1|t)=27652/27701P(c1| )=141/(141+774106)=141/774247P(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)log2

11、P(c2|t)+P( )-P(c1| )log2P(c1| )-P(c2| )log2P(c2| ) ttttttttt期望互信息(Expected Mutual Information) 词项t 和类别 c的期望互信息(Expected Mutual Information, EMI)计算如下 MI给出的是词项所包含的有关类别的信息及类别包含的有关词项的信息量 比如，如果词项的出现与否与类别独立(不同类别中包含和不包含词项的文档比例完全一样) 2类情况下 IG=MIMI 特征选择的结果卡方法 2 统计量(卡方统计量)：度量两者(词项和类别)独立性的缺乏程度， 2 越大，独立性越小，相关性越大

12、(下面N=A+B+C+D)ABCDttcc)()()()(),(22DCBADBCACBADNct朴素贝叶斯: 特征选择的效果(multinomial = 多项式朴素贝叶斯） binomial= 贝努利朴素贝叶斯)不同特征选择方法的比较 参考 Yiming Yang, Jan O. Pedersen: A Comparative Study on Feature Selection in Text Categorization. ICML 1997: 412-420特征选择 vs. 特征权重计算 特征选择：给定类别c、词汇表的情况下，通过给每个打分，选出得分靠前的特征，这里的分表示t与类别c的

13、紧密程度 特征权重：给定文档集合，对每篇文档d中的特征t，给出的t在d中的权重。 两者不是一回事。有人在分类中，将两者结合为特征的权重。关于特征选择 每个类别选前k个特征，k怎么定？ 交叉验证法(后面会讲) 通常画出随k变化分类效果变化的曲线 每个类别选的特征数目能不能不是固定的？ 可以采用阈值截断法 每个类别选出来的特征要不要合在一起形成全局特征空间？ 需要仔细分析。 一直困扰我很久，现在似乎好像大概想明白了。文本分类的评价评价示意图 分类评价 评价必须基于测试数据进行，而且该测试数据是与训练数据完全隔离的 (通常两者样本之间无交集) 很容易通过训练可以在训练集上达到很高的性能 (比如记忆所

14、有的样本集合) 指标：正确率、召回率、 F1值、分类精确率(classification accuracy)等等 正确率P 及召回率 R正确率 Precision = TP / (TP + FP)召回率 Recall = TP / (TP + FN)精确率 Accuracy = (TP+TN)/(TP + FP + FN + TN)一个计算的例子In the class(实际属于该类实际属于该类)Not in the class(实际不属于该类实际不属于该类)Predicted to be in the class(判定为该类)10050Predicted to not be in the c

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

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

17、edicted to be in the class(判定为该类)10050Predicted to not be in the class(判定不属于该类)4010000正确率Precision = 100 / (100 + 50)召回率Recall = 100 / (100 + 40)精确率 Accuracy = (100+10000)/(100 + 50 + 40 + 10000) =99.1% F值(F Measure) F1 允许在正确率和召回率之间达到某种均衡 也就是P和R的调和平均值 :其他评价方法 混淆矩阵：将前面的2*2矩阵推广到N*N矩阵 ROC曲线http:/ 给定一个已

18、标注好的数据集，将其中一部分划为训练集(training set)，另一部分划为测试集(test set)。在训练集上训练，训练得到的分类器用于测试集，计算测试集上的评价指标。 另一种做法：将上述整个数据集划分成k份，然后以其中k-1份为训练集训练出一个分类器，并用于另一份(测试集)，循环k次，将k次得到的评价指标进行平均。这种做法称为k折交叉验证(k-cross validation)。如果k=数据集的大小，则称留一法(leave-one-out)。 有时，分类器的参数需要优化。此时，可以仍然将整个数据集划分成训练集和测试集，然后将训练集分成k份(其中k-1份作为训练，另一份称为验证集val

19、idation set，也叫开发集)，在训练集合上进行k折交叉验证，得到最优参数，然后将得到参数后的分类器应用于测试集。关于训练集和测试集训练集测试集训练+测试训练集开发集测试集k折交叉验证参数确定 微平均 vs. 宏平均 上面对于一个类得到评价指标P、R、F1，但是我们希望得到分类器在所有类别上的综合性能 宏平均(Macro-averaging)：以类别为单位 对类别集合C 中的每个类都计算一个P、R、F1值 对|C|个结果求算术平均 微平均(Micro-averaging)：以类别-文档对为单位 对类别集合C 中的每个类都计算TP、FP和FN 将C中的这些数字累加 基于累加的TP、FP、F

20、N计算P、R和F1 朴素贝叶斯 vs. 其他方法朴素贝叶斯(Nave Bayes)朴素贝叶斯分类器 朴素贝叶斯是一个概率分类器 文档 d 属于类别 c 的概率计算如下： nd 是文档的长度(词的个数) P(tk |c) 是词项tk 出现在类别c中文档的概率 P(tk |c) 度量的是类别c中tk 的贡献 P(c) 是类别c的先验概率 如果文档的词项无法提供属于哪个类别的信息，那么我们直接选择P(c)最高的那个类别 独立性假设：P(d|c)=P(t1|c)P(t2|c)P(tnd|c)1( |)( | ) ( )/( )( | ) ( )( )(| )dkk nP c dP d c P cP d

21、P d c P cP cP tc 独立性独立性假设假设具有最大后验概率的类别 朴素贝叶斯分类的目标是寻找“最佳”的类别 最佳类别是指具有最大后验概率(maximum a posteriori -MAP)的类别 cmap:对数计算 很多小概率的乘积会导致浮点数下溢出 由于 log(xy) = log(x) + log(y), 可以通过取对数将原来的乘积计算变成求和计算 由于log是单调函数，因此得分最高的类别不会发生改变 因此，实际中常常使用的是：朴素贝叶斯分类器 分类规则: 简单说明: 每个条件参数 是反映tk 对c的贡献高低的一个权重 先验概率 是反映类别c的相对频率的一个权重 因此，所有权

22、重的求和反映的是文档属于类别的可能性 选择最具可能性的类别 参数估计 : 极大似然估计(MLE) 如何从训练数据中估计 和 ？ 先验: 其中，Nc : 类c中的文档数目; N: 所有文档的总数 条件概率: 其中，Tct 是训练集中类别c中的词条t的个数 (多次出现要计算多次) 给定如下的 位置独立性假设(positional independence assumption): MLE估计中的零概率问题P(China|d) P(China) P(BEIJING|China) P(AND|China) P(TAIPEI|China) P(JOIN|China) P(WTO|China)MLE估计中

23、的零概率问题（续） 如果 WTO 在训练集中没有出现在类别 China中，那么就会有如下的零概率估计： 那么，对于任意包含WTO的文档d，P(China|d) = 0。 一旦发生零概率，将无法判断类别 避免零概率: 加一平滑 平滑前： 平滑后: 对每个量都加上1 其中，B 是不同的词语个数 (这种情况下词汇表大小 |V | = B)避免零概率: 加一平滑（续） 利用加1平滑从训练集中估计参数 对于新文档，对于每个类别，计算 (i) 先验的对数值之和以及 (ii) 词项条件概率的对数之和 将文档归于得分最高的那个类一个例子 估计朴素贝叶斯分类器的参数 对测试文档进行分类例子: 参数估计上述计算中

24、的分母分别是 (8 + 6) 和 (3 + 6)，这是因为textc 和 (分别代表两类文档集的大小)的大小分别是8和3，而词汇表大小是6。例子: 分类因此, 分类器将测试文档分到c = China类，这是因为d5中起正向作用的CHINESE出现3次的权重高于起反向作用的 JAPAN和TOKYO的权重之和。朴素贝叶斯独立性假设不成立的情况 自然语言文本中，上述独立性假设并不成立 条件独立性假设: 位置独立性假设: 问题： 给出条件独立性假设不成立的例子 给出位置独立性假设不成立的例子 在这些假设都不成立的情况下，为什么朴素贝叶斯方法有用？朴素贝叶斯方法起作用的原因 即使在独立性假设严重不成立的

25、情况下，朴素贝叶斯方法能够高效地工作 例子 概率P(c2|d)被过低估计(0.01) ，而概率P(c1|d)被过高估计 (0.99)。 分类的目标是预测正确的类别，并不是准确地估计概率 准确估计 精确预测 反之并不成立!朴素贝叶斯的时间复杂度分析 Lave: 训练文档的平均长度, La: 测试文档的平均长度, Ma: 测试文档中不同的词项个数 训练文档，V : 词汇表， 类别集合 是计算所有统计数字的时间 是从上述数字计算参数的时间 通常来说: 训练时间是线性的，而测试时间也是线性的 (相对于测试文档长度而言) 因此： 朴素贝叶斯 对于训练集的大小和测试文档的大小而言是线性的。这在某种意义上是

26、最优的。朴素贝叶斯并不朴素 朴素贝叶斯在多次竞赛中胜出 (比如 KDD-CUP 97) 相对于其他很多更复杂的学习方法，朴素贝叶斯对不相关特征更具鲁棒性 相对于其他很多更复杂的学习方法，朴素贝叶斯对概念漂移(concept drift)更鲁棒(概念漂移是指类别的定义随时间变化) 当有很多同等重要的特征时，该方法优于决策树类方法 一个很好的文本分类基准方法 (当然，不是最优的方法) 如果满足独立性假设，那么朴素贝叶斯是最优的 (文本当中并不成立，但是对某些领域可能成立) (训练和测试)速度非常快 存储开销少补充说明-朴素贝叶斯的两种实现方式 基于多项式模型的实现方法：多项式模型中各单词类条件概率

27、计算考虑了词出现的次数，多项式模型是一种以词作为计算粒度的方法。 每个不规则骰子代表一个类 骰子的每个面代表一个词 面的个数等于文本中的单词个数 每个类的一篇文本是通过投掷上述对应骰子产生的 基于贝努利模型的实现方法：贝努利模型不考虑词在文档中出现的次数，只考虑出不出现，因此在这个意义上相当于假设词是等权重的。贝努利模型是一种以文档作为计算粒度的方法。 每个类对应一堆硬币 每个硬币代表一个词 硬币的个数等于单词的个数 类中的一篇文本是通过投掷对应类的所有硬币产生的参考http:/ 每篇文档都表示一个向量，每一维对应一个词项 词项就是坐标轴 通常都高维: 100,000多维 通常要将向量归一化到

28、单位长度 如何在该空间下进行分类？向量空间分类 同前面一样，训练集包含一系列文档，每篇都标记着它的类别 在向量空间分类中，该集合对应着空间中一系列标记的点或向量。 假设假设 1: 同一类中的文档会构成一片连续区域（contiguous region） 假设假设2: 来自不同类别的文档没有交集 接下来我们定义直线、平面、超平面来将上述不同区域分开向量空间中的类别 文档*到底是属于UK、China还是Kenya类？首先找到上述类别之间的分类面，然后确定文档所属类别，很显然按照图中分类面，文档应该属于China类 如何找到分类面并将文档判定给正确类别是下面要讨论的重点。 中心向量法：基本思想 计算每

29、个类的中心向量(所有文档向量的算术平均向量) 将每篇测试文档分到离它最近的那个中心向量其中 Dc 是所有属于类别 c 的文档， 是文档d的向量空间表示 中心向量法的算法中心向量法的性质 简单地将每个类别表示成其中心向量 中心向量可以看成类别的原型或代表(prototype) 分类基于文档向量到原型的相似度或距离来进行 并不保证分类结果与训练集一致，即得到分类器后，不能保证训练集中的文档能否正确分类中心向量法的时间复杂度 训练时间是线性的，而测试时间也是线性的 (相对于测试文档长度而言) 训练和测试速度很快中心向量法 vs. 朴素贝叶斯 很多情况下，中心向量法的效果不如朴素贝叶斯 一个原因是，中

30、心向量法不能正确处理非凸、多模式类别问题中心向量法不能正确处理多模式类别问题课堂练习: 对于左图的A、B两类分类问题，为什么中心向量法难以有效处理? A 是所有a的中心向量， B是所有b的中心向量 点o 离A更近 但是o更适合于B类 A 是一个有两个原型多模式类别 但是，在中心向量法中，每个类别只有一个原型X X a b b B a a a b a b 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 是另外一种基于向量空间的分类方法 该方

31、法非常简单，也容易实现 在大多数情况下，kNN的效果比朴素贝叶斯和中心向量法要好 如果你急切需要一种精度很高分类器并很快投入运行 . . . . . 如果你不是特别关注效率 . . . . . . 那么就使用kNN kNN分类 kNN = k nearest neighbors，k近邻 k = 1 情况下的kNN (最近邻): 将每篇测试文档分给训练集中离它最近的那篇文档所属的类别。 1NN 不很鲁棒一篇文档可能会分错类或者这篇文档本身就很反常 k 1 情况下的kNN: 将每篇测试文档分到训练集中离它最近的k篇文档所属类别中最多的那个类别 kNN的基本原理: 邻近性假设 我们期望一篇测试文档d

32、与训练集中d周围邻域文档的类别标签一样。 概率型kNN kNN的概率型版本: P(c|d) = d的最近的k个邻居中属于c类的比例 概率型kNN: 将d分到具有最高概率P(c|d)的类别c中 概率型kNN对于 对应的文档，在1NN和 3NN下，分别应该属于哪个类？ kNN 算法kNN的时间复杂度 kNN 测试时间复杂度与训练集的大小成正比! 训练集越大，对测试文档分类的时间越长 在大训练集情况下，kNN效率较低课堂练习对于 对应的文档，在下列分类器下，分别应该属于哪个类:(i) 1-NN (ii) 3-NN (iii) 9-NN (iv) 15-NN (v) 中心向量法?kNN: 讨论 优点：

33、 不需要训练过程 但是，文档的线性预处理过程和朴素贝叶斯的训练开销相当 对于训练集来说我们一般都要进行预处理，因此现实当中kNN的训练时间是线性的。 当训练集非常大的时候，kNN分类的精度很高 缺点： 如果训练集很小， kNN可能效果很差。 需要确定参数k (可以采用多折交叉验证法) kNN倾向于大类，可以将相似度考虑在内。kNN的快速实现：KD-树 KD-树是K-dimension tree的缩写，是对数据点在k维空间（中划分的一种数据结构，主要应用于多维空间关键数据的搜索。本质上说，KD-树就是一种平衡二叉树。 例子： T1(2,3),T2(5,4),T3(9,6),T4(4,7),T5(

34、8,1),T6(7,2)的KD-树参考：李航，统计学习方法第3章线性分类器(Linear Classifier)线性分类器(Linear Classifier) 线性可分 vs. 非线性可分 线性分类器： 训练中确定所有的wi和参数 决策规则： 对于线性可分，必然存在线性分类面 = N维空间下的二类线性分类器(N维超平面)一维二维三维中心向量分类器是一个线性分类器 中心向量分类器的线性分类面定义为： 其中 是向量 的法向量 请课后自己证明。 朴素贝叶斯也是线性分类器 多项式模型(本讲义所介绍的类型)下的二类朴素贝叶斯分类器也是线性分类器，其分类面定义为： 其中 , di = ti 在d中的出现

35、次数， 1 i M, 注意：这里的ti指的是所有词汇表中的词项，而不是前面出现在文档d中的词项 请课后自己证明。kNN不是线性分类器 kNN分类决策取决于k个邻居类中的多数类 类别之间的分类面是分段线性的 . . . 但是一般来说，很难表示成如下的 线性分类器感知机(Perceptron)Threshold Logic Unit (TLU)x1x2xn.w1w2wna=i=1n wi xi 1 if a qy= 0 if a qy输入权重activation输出qActivation Functionsayayayaythresholdlinearpiece-wise linearsigmoi

36、dThreshold as Weightx1x2xn.w1w2wnwn+1xn+1=-1a= i=1n+1 wi xiy 1 if a 0y= 0 if a 0q=wn+1Perceptron Training Algorithm(错误驱动型)Repeatfor each training vector pair (x,t)evaluate the output y when x is the inputif yt thenform a new weight vector w accordingto w=w + a (t-y) xelse do nothing end if end forUn

37、til y=t for all training vector pairsa 为学习率Perceptron Learning Rulet=1t=-1w=0.25 0.1 0.5x2 = 0.2 x1 0.5o=1o=-1(x,t)=(-1,-1,1)o=sgn(0.25+0.1-0.5) =-1w=0.2 0.2 0.2(x,t)=(2,1,-1)o=sgn(0.45-0.6+0.3) =1w=-0.2 0.4 0.2(x,t)=(1,1,1)o=sgn(0.25-0.7+0.1) =-1w=0.2 0.2 0.2感知机的收敛性 在线性可分的情况下，可以证明感知机一定收敛(学习率要足够小) 取

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

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

40、约束条件下，求目标函数的最小值 目标函数: WWWW2121)(2() 10iiyWXb 约束条件: 最优超平面 可以通过求解上述问题的对偶问题对偶问题来得到最终的解。在对偶问题中，将原来需要求解的一系列wi转换成求解另一组变量i求解原始问题 为求解原始问题，根据最优化理论，我们转化为对偶问题来求解11111minX X2. .0,0,1llli jijijjijjliiiiyystyilaa aaaa对偶问题对偶问题 为原始问题中与每个约束条件对应的Lagrange乘子。这是一个不等式约束条件下的二次函数寻优问题，存在唯一解ia*a线性可分问题计算 ，选择 的一个正分量 , 并据此计算*1(

41、,)Tlaaa*1WXliiiiya*a*ja*1XXljiijiibyya事实上， 的每一个分量 都与一个训练点相对应。而分划超平面仅仅依赖于 不为零的训练点 ，而与对应于 为零的那些训练点无关。*a*ia*iaX,iiy*ia称 不为零的这些训练点的输入 为支持向量支持向量(SV)*iaXi构造分划超平面 ,决策函数*WX0b *Xsgn(WX)fb根据最优解求解结果 上述二次优化问题，采用Lagrange方法求解 ，可得 相当于每个类别中选出若干支持向量组成“投票委员会”，根据这些“委员”的加权投票(内积)结果得到最终的类别归属*1()sgniniiif Xy XXba支持向量(Supp

42、ort Vector)非线性可分情况下的处理方法一 广义最优分类面方法：在线性不可分的情况下，就是某些训练样本不能满足上面的约束条件，因此可以在条件中增加一个松弛项(这种做法也称引入Soft Margin，软边界)，于是约束条件变成 :01)(iiibXWy 此时的目标函数是求下式的最小值: niiiCWWW121),( 这个二次优化问题，同样可以应用Lagrange方法求解 正则项经验风险最优超平面求解非线性可分情况下的处理方法二变换到高维空间的支持向量机 采用如下的内积函数(核函数)：qiiXXXXK 1)(),(22exp),(XiXXiXK)(tanh(),(cXXXXKii*1*),

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

44、= x1 + 2x2 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) 分类：按照

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

46、11213141112131121222324222122233132333401 101001a a a awwwcca aa accwwwa a a a 举例：2个类别c1,c2，4篇文档d1,d2,d3,d4分别属于c2,c1,c1,c2，3个特征t1,t2,t3，利用LLSF计算如下：FAB 使|FA-B|最小，可以解得F矩阵。对一篇新文档d=a1,a2,a3T，Fd会得到一个2行一列的矩阵(实际是个向量)，哪个分量大则属于哪类。显然，LLSF可以直接处理多类问题，也能处理兼类问题。LLSF小结 训练：计算类别权重矩阵F的过程，比较耗时。 分类：类别权重矩阵和文档向量相乘。 Yang

47、Yiming通过实验证实LLSF的效果和kNN、SVM相当。Yiming Yang and Xin Liu. A Re-examination of Text 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，分类器之间其他相同就

48、是参数不同。其中fi是通过从训练集合中(N篇文档)随机取(取后放回)N次文档构成的训练集合训练得到的。 对于新文档d，用这R个分类器去分类，得到的最多的那个类别作为d的最终类别 Boosting方法 类似Bagging方法，但是训练是串行进行的，第k个分类器训练时关注对前k-1分类器中错分的文档，即不是随机取，而是加大取这些文档的概率 AdaBoost AdaBoost MH多类下的单标签和多标签问题多类问题 前面介绍的都是二类问题 现实中大部分类别体系中类别的个数都不止2，这种情况的分类问题称为多类问题 如果有算法一次性考虑所有样本，通过求解一个多目标函数的优化问题，一次性得到多个分类面把空

49、间划分为多个区域，每个区域对应一个类别。那么，事情就好办了。实际上这样的算法计算量太大无法实现。通过二类分类器处理多类问题 1-V-R方式：4个类别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采用了这种方式各种处理方式的对比余辉，

50、赵晖，支持向量机多类分类算法新研究，计算机工程与应用，44(7):185-189, 212, 2008年7月 130单标签问题（One-of problem） 单标签分类问题，也称single label problem 类别之间互斥 每篇文档属于且仅属于某一个类 例子：文档的语言类型 (假定：任何一篇文档都只包含一种语言) 基于线性分类器的单标签分类(多类) 对于单标签分类问题（比如A、B、C三类），可以将多个二类线性分类器(A vs BC、B vs AC、C vs AB)进行如下组合： 对于输入文档，独立运行每个分类器 将分类器排序 (比如按照每个分类器输出的在A、B、C上的得分) 选择具

51、有最高得分的类别 也可以采用1-V-1方式，进行投票 多标签问题(Any-of problem) 多标签分类问题，也称multi-label problem 一篇文档可以属于0、1或更多个类 针对某个类的决策并不影响其他类别上的决策 一种 “独立”类型，但是不是统计意义上的“独立” 例子：主题分类 通常：地区、主题领域、工业等类别之上的决策是互相独立的 基于线性分类器的多标签分类 对于多标签分类问题（比如A、B、C三类），可以将多个二类线性分类器(A vs BC、B vs AC、C vs AB)进行如下组合： 对测试文档独立地运行每个分类器 按照每个分类器自己的输出结果进行独立决策 采用1-V

52、-1方式，也可以使用上述类似思路进行处理文本分类的实际应用文本分类 许多商业应用 “能够基于内容对文档进行自动分类的商业价值毋庸置疑，在公司内网、政府机构及互联网出版等机构或领域中存在大量的潜在应用” 采用领域相关的文本特征在性能上会比采用新的机器学习方法获得更大的提升 “对数据的理解是分类成功的关键之一，然而这又是大部分分类工具供应商非常不擅长的领域。市场上很多所谓的通用分类工具并没有在不同类型的内容上进行广泛的测试。”分类器的选择 当面对一个建立分类器的需求时，第一个要问的问题就是：训练数据有多少？ 一点都没有? 很少? 挺多? 量很大，而且每天都在增长?实际中的挑战: 建立或获取足够的训

53、练语料为了获得高性能的分类器，每个类都需要成百上千的训练文档，而且现实当中的类别体系也非常庞大如果没有任何训练数据 采用人工撰写规则的方法 实际中的规则要比这个例子长很多，并且可以采用更复杂的表示方式。经过精心调整（也就是说，人们可以在开发集上调整规则）之后，利用这些规则分类的精度可以非常高。然而，要构造非常好的人工规则需要做大量的工作。一个基本合理的估计数字是每个类别需要两天的时间，由于类别中的文档内容会发生漂移，所以必须还要利用很多额外的时间去维护规则。例子IF (wheat OR grain) AND NOT (whole OR bread) THENc = grain如果拥有较少的训练

54、数据，又希望训练一个有监督的分类器 如何尽快地获得更多的标注数据 最佳方法：将自己也放入到标注的过程中去，在这个过程中人们自愿为你标注数据，并且这也是他们正常工作的一部分。例子很多情况下，人们会根据需要整理或者过滤邮件数据，这些动作能够提供类别相关的信息主动学习(Active Learning)建立一个系统来确定应该标注的那些文档。通常情况下，这些文档主要指那些分类器不确定能否正确分类的文档。如果拥有训练数据拥有极大规模的标注数据分类器的选择也许对最后的结果没有什么影响，目前我们还不清楚是否有最佳的选择方法。也许最好的方法是基于训练的规模扩展性或运行效率来选择。为达到这个目的，需要极大规模的数

55、据。一个通用的经验法则是，训练数据规模每增加一倍，那么分类器的效果将得到线性的提高。但是对于极大规模的数据来说，效果提高的幅度会降低成亚线性。拥有适量的标注数据能够使用我们在前面所介绍的任何文本分类技术通常优先考虑混合方法大规模高难度分类体系 如果文本分类问题仅包含少量具有区分度的类别，那么很多分类算法都可能取得很好的结果。但是实际的文本分类问题往往包含大量非常类似的类别。 对大量相近的类别进行精确分类是一个固有的难题例子Web目录（如Yahoo!目录或ODP（Open Directory Project）目录）、图书馆分类机制（杜威十进制分类法或美国国会图书馆分类法），或者用于法律和医学领域

56、的分类机制。分类研究趋势 更好的特征选择方法 非均衡分类问题 层次分类体系下的分类问题 大规模数据或分类体系下的高性能分类问题 面向领域的分类问题 情感分析 垃圾过滤 表示学习(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如何获得数据 数据分成 未加工

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

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

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

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