数据挖掘导论第章_分类_其他技术ppt课件.ppt

数据挖掘导论 Pang ningTan MichaelStieinbach andVipinKumar著PearsonEducationLTD 范明等译人民邮电出版社 1 第5章分类 其他技术 基于规则的分类最近邻分类贝叶斯分类神经网络支持向量机组合方法不平衡类问题多类问题 2 5 1基于规则的分类器 3 基于规则的分类器 使用一组 if then 规则进行分类规则 Condition y其中Condition是属性测试的合取y是类标号左部 规则的前件或前提右部 规则的结论分类规则的例子 BloodType Warm LayEggs Yes Birds TaxableIncome 50K Refund Yes Evade No 4 基于规则的分类器 例 脊椎动物数据集 5 基于规则的分类器的使用 规则r覆盖实例x 如果该实例的属性满足规则r的条件r1 胎生 否 飞行动物 是 鸟类r2 胎生 否 水生动物 是 鱼类r3 胎生 是 体温 恒温 哺乳类r4 胎生 否 飞行动物 否 爬行类r5 水生动物 半 两栖类规则r1覆盖 鹰 鸟类规则r3覆盖 灰熊 哺乳类 6 规则的质量 用覆盖率和准确率度量规则的覆盖率 coverage 满足规则前件的记录所占的比例规则的准确率 accuracy 在满足规则前件的记录中 满足规则后件的记录所占的比例规则 Status Single NoCoverage 40 Accuracy 50 Tid Refund Marital Status Taxable Income Class 1 Yes Single 125K No 2 No Married 100K No 3 No Single 8 No Single 85K Yes 9 No Married 75K No 10 No Singl e 90K Yes 10 7 如何用规则分类 一组规则r1 胎生 否 飞行动物 是 鸟类r2 胎生 否 水生动物 是 鱼类r3 胎生 是 体温 恒温 哺乳类r4 胎生 否 飞行动物 否 爬行类r5 水生动物 半 两栖类待分类记录狐猴触发规则r3 它分到哺乳类海龟触发规则r4和r5 冲突狗鲨未触发任何规则 8 规则的分类器的特征 互斥规则集每个记录最多被一个规则覆盖如果规则都是相互独立的 分类器包含互斥规则如果规则集不是互斥的一个记录可能被多个规则触发如何处理 有序规则集基于规则的序vs基于类的序无序规则集 使用投票策略 9 规则的分类器的特征 续 穷举规则集每个记录至少被一个规则覆盖如果规则集涵盖了属性值的所有可能组合 则规则集具有穷举覆盖如果规则集不是穷举的一个记录可能不被任何规则触发如何处理 使用缺省类 10 有序规则集 根据规则优先权将规则排序定秩 rank 有序规则集又成决策表 decisionlist 对记录进行分类时由被触发的 具有最高秩的规则确定记录的类标号如果没有规则被触发 则指派到缺省类 11 规则定序方案 基于规则的序根据规则的质量排序基于类的序属于同一类的规则放在一起基于类信息 如类的分布 重要性 对每类规则排序 12 如何建立基于规则的分类器 直接方法 直接由数据提取规则例如 RIPPER CN2 Holte s1R间接方法 由其他分类模型提取规则 例如 从决策树 神经网络等 例如 C4 5rules 13 直接方法 顺序覆盖 基本思想依次对每个类建立一个或多个规则对第i类建立规则第i类记录为正例 其余为负例建立一个第i类的规则r 尽可能地覆盖正例 而不覆盖负例删除r覆盖的所有记录 在剩余数据集上学习下一个规则 直到所有第i类记录都被删除 14 直接方法 顺序覆盖 顺序覆盖 sequentialcovering 算法1 令E是训练记录 A是属性 值对的集合 Aj vj 2 令Yo是类的有序集 y1 y2 yk 3 令R 是初始规则列表4 for每个类y Yo yk do5 while终止条件不满足do6 r Learn One Rule E A y 7 从E中删除被r覆盖的训练记录8 追加r到规则列表尾部 R R r9 endwhile10 endfor11 把默认规则 yk插入到规则列表R尾部 15 顺序覆盖 例 a Originaldata b Step1 c Step2 c Step3 16 删除实例 为什么要删除实例 否则 下一个规则将与前面的规则相同为什么删除正实例 确保下一个规则不同为什么删除负实例 防止低估规则的准确率比较图中的规则R2和R3 17 Learn One Rule 规则增长实例删除规则评估停止准则规则剪枝 18 规则增长 两种策略一般到特殊从初始规则r y开始反复加入合取项 得到更特殊的规则 直到不能再加入特殊到一般随机地选择一个正例作为初始规则反复删除合取项 得到更一般的规则 直到不能再删除问题加入 删除合取项有多种选择 如何选择 何时停止加入 删除合取项 需要评估标准 19 规则增长 例 一般到特殊 特殊到一般 20 规则评估 常用的度量准确率似然比LaplaceM estimateFOIL信息增益 21 规则评估 续 准确率Accuracyn 被规则覆盖的实例数nc 被规则正确分类的实例数问题 准确率高的规则可能覆盖率太低似然比 越高越好 k是类的个数fi是被规则覆盖的类i的样本的观测频度ei是规则作随机猜测的期望频度 22 规则评估 例 例 60个正例和100个反例规则r1 覆盖50个正例和5个反例 acc 90 9 规则r2 覆盖2个正例和0个反例 acc 100 使用准确率 r2好使用似然比r1 正类的期望频度为e 55 60 160 20 625负类的期望频度为e 55 100 160 34 375r2 正类的期望频度为e 2 60 160 0 75负类的期望频度为e 2 100 160 1 25R r1 2 50 log2 50 20 625 5 log2 5 34 375 99 9R r2 2 2 log2 2 0 75 0 log2 0 1 25 5 66r1比r2好 23 规则评估 续 考虑规则覆盖率的评估度量n是规则覆盖的样例数 f 是规则覆盖的正例数 k是类的总数 p 是正类的先验概率当规则的覆盖率很高时 两个度量都渐近地趋向于规则的准确率f n继续前例r1的Laplace度量为51 57 89 47 很接近它的准确率r2的Laplace度量 75 比它的准确率小很多 24 规则评估 续 考虑规则的支持度计数的评估度量规则的支持度计数对应于它所覆盖的正例数FOIL信息增益 FirstOrderInductiveLeanerinformationgain 设规则r A 覆盖p0个正例和n0个反例 规则r A B 覆盖p1个正例和n1个反例 扩展后规则的FOIL信息增益定义为该度量与p1和p1 p1 n1 成正比 所以它更倾向于选择那些高支持度计数和高准确率的规则继续前例r1和r2的FOIL信息增益分别为43 12和2 因此规则r1比r2好 25 停止条件与规则剪枝 停止条件计算增益如果增益不显著 则丢弃新规则规则剪枝类似于决策树后剪枝降低错误剪枝 删除规则中的合取项比较剪枝前后的错误率如果降低了错误率 则剪掉该合取项 26 直接方法 RIPPER 对于2类问题 选定一个类为正类 另一个为负类从正类学习规则负类时缺省类多类问题按类的大小 属于特定类的实例所占的比例 对诸类排序从最小的类开始学习规则 其余类都看做负类对次小类学习规则 如此下去 27 直接方法 RIPPER 续 规则增长 由空规则开始只要能够提高FOIL信息增益就增加一个合取项当规则不再覆盖负实例时就停止剪枝剪枝度量 v p n p n p 验证集中被规则覆盖的正实例数n 验证集中被规则覆盖的负实例数剪枝方法 如果剪掉合取项可以提高v就剪 28 直接方法 RIPPER 续 建立规则集 使用顺序覆盖算找出覆盖当前正实例的最佳规则删除被规则覆盖的所有正实例和负实例当一个规则加入规则集时 计算新的描述长度当新的描述长度比已经得到的描述长度多d位时 就停止增加新规则 29 直接方法 RIPPER 续 优化规则集 对规则集R中的每个规则r考虑2个替换的规则 替换规则 r 重新增长新规则编辑的规则 r 把一个新的合取项增加到规则r比较替换前后的规则集选择最小化MDL的规则集对剩下的正实例 重复规则产生和优化 30 规则提取的间接方法 决策树从根结点到叶结点的每一条路径都可以表示为一个分类规则路径中的测试条件构成规则前件的合取项 叶结点的类标号赋给规则后件 31 间接方法 C4 5rules 续 从未剪枝的决策树提取规则规则产生对每个规则r A y 考虑替换规则r A y其中A 由删除A的一个合取项得到比较r与所有r 的悲观误差如果r 的悲观误差小 则剪枝重复该过程 直到不能改进 32 间接方法 C4 5rules 规则定序不是对规则定序 而是对规则的子集定序 classordering 每个规则子集是一组具有相同规则后件 class 的规则计算每个子集的描述长度描述长度 L error gL model g是参数 考虑规则集中冗余属性 缺省值g 0 5 33 C4 5vsC4 5rulesvsRIPPER 34 基于规则的分类器的特征 表达能力与决策树一样高容易解释容易产生能够快速对新实例分类性能可与决策树相媲美 35 5 2最近邻分类器 36 急切学习vs惰性学习 急切学习 EagerLearner 两步过程 1 归纳 2 演绎惰性学习 lazylearner 把训练数据建模过程推迟到需要对样本分类时例子Rote learner 死记硬背 记住所有的训练数据 仅当记录的属性值与一个训练记录完全匹配才对它分类最近邻 Nearestneighbor 使用 最近 的k个点 最近邻 进行分类 37 最近邻分类器 基本思想 Ifitwalkslikeaduck quackslikeaduck thenit sprobablyaduck 38 最近邻分类器 要求存放训练记录计算记录间距离的度量k值 最近邻数对未知记录分类 计算域各训练记录的距离找出k个最近邻使用最近邻的类标号决定未知记录的类标号 例如 多数表决 39 最近邻定义 记录x的k 最近邻是与x之间距离最小的k个训练数据点 40 1nearest neighbor VoronoiDiagram 41 k 最近邻分类算法 k 最近邻分类算法1 令k是最近邻数目 D是训练样例的集合2 for每个测试样例z x y do3 计算z和每个样例 x y D之间的距离d x x 4 选择离z最近的k个训练样例的集合Dz D5 6 endfor距离加权表决 42 k 最近邻 k值的选择 如果k太小 则对噪声点敏感如果k太大 邻域可能包含很多其他类的点定标问题 规范化 属性可能需要规范化 防止距离度量被具有很大值域的属性所左右 43 k NN的特点 k NN的特点是一种基于实例的学习需要一个邻近性度量来确定实例间的相似性或距离不需要建立模型 但分类一个测试样例开销很大需要计算域所有训练实例之间的距离基于局部信息进行预测 对噪声非常敏感最近邻分类器可以生成任意形状的决策边界决策树和基于规则的分类器通常是直线决策边界需要适当的邻近性度量和数据预处理防止邻近性度量被某个属性左右 44 5 3贝叶斯分类器 45 贝叶斯定理 每个记录用一个d维特征向量X x1 x2 xd 表示假定有k个类y1 y2 yk 给定X X属于yj类的后验概率P yj X 满足贝叶斯 Bayes 定理MAP maximumposteriorihypothesis 最大后验假设 将X指派到具有最大后验概率P yj X 的类yj 即将X指派到P X yj P yj 最大的类yj 46 朴素贝叶斯分类 朴素贝叶斯分类 Na veBayesClassifier 工作原理给定一个未知的数据样本X 分类法将预测X属于具有最高后验概率的类 即 未知的样本分配给类yj 当且仅当根据贝叶斯定理 我们有由于P X 对于所有类为常数 只需要最大化P X yj P yj 即可 47 朴素贝叶斯分类 续 估计P yj 类yj的先验概率可以用下式估计P yj nj n其中 nj是类yj中的训练样本数 而n是训练样本总数估计P X yj 为便于估计P X yj 假定类条件独立 给定样本的类标号 假定属性值条件地相互独立 于是 P X Y yj 可以用下式估计其中 P xi yj 可以由训练样本估值 48 朴素贝叶斯分类 续 估计P xi yj 设第i个属性Ai是分类属性 则P xi yj nij nj其中nij是在属性Ai上具有值xi的yj类的训练样本数 而nj是yj类的训练样本数设第i个属性Ai是连续值属性把Ai离散化假定Ai服从高斯分布其中 ij ij分别为给定yj类的训练样本在属性Ai上的均值和标准差 49 朴素贝叶斯分类 朴素贝叶斯分类器所需要的信息计算每个类的先验概率P yj P yj nj n其中 nj是yi类的训练样本数 而n是训练样本总数对于离散属性Ai 设的不同值为ai1 ai2 ail 对于每个类yj 计算后验概率P aik yj 1 k lP aik yj nikj nj其中nikj是在属性Ai上具有值aik的yj类的训练样本数 而nj是yj类的训练样本数对于连续属性Ai和每个类yj 计算yj类样本的均值 ij 标准差 ij 50 贝叶斯分类器 例 例 P Yes 3 10P No 7 10P 有房 是 No 3 7P 有房 否 No 4 7P 有房 是 Yes 0P 有房 否 Yes 1P 婚姻状况 单身 No 2 7P 婚姻状况 离婚 No 1 7P 婚姻状况 已婚 No 4 7P 婚姻状况 单身 Yes 2 3P 婚姻状况 离婚 Yes 1 3P 婚姻状况 已婚 Yes 0年收入 类 No 样本均值 110样本方差 2975类 Yes 样本均值 90样本方差 25 51 贝叶斯分类器 例 续 X 有房 否 婚姻状况 已婚 年收入 120K 计算P X No 和P X Yes P X No P 有房 否 No P 婚姻状况 已婚 No P 年收入 120K No 4 7 4 7 0 0072 0 0024P X Yes P 有房 否 Yes P 婚姻状况 已婚 Yes P 年收入 120K Yes 1 0 1 2 10 9 0计算P X No P No 和P X Yes P Yes P X No P No 0 0024 0 7 0 00168P X Yes P Yes 0 0 3 0因为P X No P No P X Yes P Yes 所以X分类为No 52 贝叶斯分类器 问题如果诸条件概率P Xi xi Y yj 中的一个为0 则它们的乘积 计算P X Y yj 的表达式 为0很可能每个P X Y yj 都为0解决方法使用Laplace估计 原估计 P Xi xi Y yj nij nj 53 贝叶斯分类器的特点 对孤立的噪声点的鲁棒性个别点对概率估计的影响很小容易处理缺失值在估计概率时忽略缺失值的训练实例对不相关属性的鲁棒性各类在不相关属性上具有类似分布类条件独立假设可能不成立使用其他技术 如贝叶斯信念网络 BayesianBeliefNetworks BBN 54 贝叶斯信念网络 贝叶斯信念网络 Bayesianbeliefnetwork 允许在变量的子集间定义类条件独立性因果关系图模型表示变量之间的依赖给出联合概率分布的说明图示节点 随机变量边 依赖X Y是Z的父节点 前驱 并且Y是P的父节点 前驱Z和P之间没有依赖关系图中没有环 55 贝叶斯信念网络 例 变量LungCance LC 值的条件概率表 CPT 给出其双亲结点FamilyHistory和Smoke的每个可能值的组合的条件概率 56 贝叶斯信念网络 例 续 给出了LungCancer的CPT 对于其双亲值的每个可能组合 表中给出了LungCancer的每个值的条件概率 例如 由左上角和右下角 我们分别看到P LungCancer yes FamilyHistory yes Smoker yes 0 8P LungCancer no FamilyHistory no Smoker no 0 9对应于属性或变量Z1 Zn的任意元组 z1 zn 的联合概率由下式计算其中 P zi parents zi 的值对应于Zi的CPT中的表目 57 训练贝叶斯信念网络 若干情况给定网络结构和所有可观测变量只需要学习CPT网络结构已知 而某些变量是隐藏的使用梯度下降法或类似于神经网络的方法训练信念网络网络结构未知 所有的变量可以观测搜索模型空间 构造网络拓扑结构网络结构未知 所有变量是隐藏的没有已知的好算法D Heckerman Bayesiannetworksfordatamining 58 训练贝叶斯信念网络 梯度下降法设S是s个训练样本X1 X2 Xs的集合 wijk是具有双亲Ui uik的变量Y yij的CPT项wijk可以看作权 类似于神经网络中隐藏单元的权 权的集合记作w这些权被初始化为随机概率值 梯度下降策略采用贪心爬山法 在每次迭代中 修改这些权 并最终收敛到一个局部最优解基于w的每个可能设置都等可能的假定 该方法搜索能最好地对数据建模wijk值 目标是最大化 59 训练贝叶斯信念网络 梯度下降法 给定网络结构和wijk的初值 该算法按以下步骤处理计算梯度 对每个i j k 计算沿梯度方向前进一小步 用下式更新权值l是表示步长的学习率 设置为一个小常数重新规格化权值 由于权值wijk是概率值 它们必须在0 0和1 0之间 并且对于所有的i k 必须有 60 BBN的特点 BBN提供了一种用图形模型来捕获特定领域的先验知识的方法 网络还可以用来对变量间的因果依赖关系进行编码构造网络可能既费时又费力 然而 一旦网络结构确定下来 添加新变量就十分容易贝叶斯网络很适合处理不完整的数据 对有属性遗漏的实例可以通过对该属性的所有可能取值的概率求和或求积分来加以处理因为数据和先验知识以概率的方式结合起来了 所以该方法对模型的过分拟合问题是非常鲁棒的 61 使用BBN进行推理举例 E 锻炼 D 饮食 HD 心脏病 Hb 胸口痛 BP 血压 CP 胸痛 62 情况一 没有先验信息 通过计算先验概率P HD Yes 和P HD No 来确定一个人是否可能患心脏病设 Yes No 表示锻炼的两个值 健康 不健康 表示饮食的两个值 由全概率公式P HD Yes 0 25 0 7 0 25 0 45 0 7 0 75 0 55 0 3 0 25 0 75 0 3 0 75 0 49因为P HD No 1 P HD Yes 0 51 所以 此人不得心脏病的机率略微大一点 63 情况二 高血压 如果一个人有高血压 可以通过比较后验概率P HD Yes BP 高 和P HD No BP 高 来诊断他是否患有心脏病先用全概率公式 计算P BP 高 P BP 高 0 85 0 49 0 2 0 51 0 5185其中 Yes No 用贝叶斯公式计算此人患心脏病的后验概率 64 情况三 情况三 高血压 饮食健康 经常锻炼身体患心脏病的后验概率 65 5 4人工神经网络 66 神经网络 神经网络最早是由心理学家和神经学家提出的 旨在寻求开发和测试神经的计算模拟神经网络是一组连接的输入 输出单元 其中每个连接都与一个权相关联在学习阶段 通过调整神经网络的权 使得能够预测输入样本的正确类标记神经网络的优点对噪音数据的高承受能力对未知样本的分类能力神经网络缺点需要很长的训练时间 因而对于有足够长训练时间的应用更合适很难解释蕴涵在学习权之中的符号含义它需要大量的参数 这些通常主要靠经验确定 如网络拓扑或 结构 67 多层前馈神经网络 后向传播是一种神经网络学习算法后向传播算法在多层前馈 multilayerfeed forward 神经网络上学习例 一个多层前馈神经网络训练样本X x1 x2 xi 馈入输入层 每层之间存在加权连接 其中 wij表示由某层的单元j到前一层的单元i的权 68 多层前馈神经网络 续 输入同时提供给称作输入层的单元层隐藏层的数量是任意的 实践中通常只用一层输出层发布给定样本的网络预测隐藏层和输出层的单元 有时称作neurodes 源于符号生物学 或输出单元包含n个隐藏层的网络称作n 1层神经网络网络是前馈的 如果其权都不回送到输入单元 或前一层的输出单元网络是全连接的 如果每个单元都向下一层的每个单元提供输入给定足够多的隐藏单元 线性阈值函数的多层前馈神经网络可以逼近任何函数 69 多层前馈神经网络 续 定义网络拓扑用户必须说明输入层的单元数 隐藏层数 每一隐藏层的单元数和输出层的单元数对于 最好的 隐藏层单元数没有明确的规则网络设计是一个实验过程 并可能影响结果训练网络的准确性 权的初值也可能影响结果的准确性一旦网络经过训练 并且其准确率不能被接受 则通常用不同的网络拓扑或使用不同的初始权值 重复训练过程对训练样本中每个属性的值进行规格化将有助于加快学习过程通常 对输入值规格化 使得它们落入0 0和1 0之间离散值属性可以重新编码 使得每个域值一个输入单元例如 如果属性A的定义域为 a0 a1 a2 则可以分配三个输入单元I0 I1 I2表示A 70 后向传播 基本思想迭代地处理一组训练样本 将每个样本的网络预测与实际知道的类标号比较 进行学习 对于每个训练样本 修改权值 使得网络预测和实际类之间的均方误差最小尽管不能保证 一般地 权将最终收敛 学习过程停止步骤解释初始化权 网络的权被初始化为很小的随机数 例如 由 1 0到1 0 或由 0 5到0 5 每个单元有一个偏置 也类似地初始化为小随机数每个样本X按以下步骤处理向前传播输入后向传播误差重复以上两步 直至终止条件满足 71 后向传播 续 向前传播输入计算隐藏层和输出层每个单元的净输入和输出对于输入层的单元j 它的输出等于它的输入 Oj Ij 给定隐藏层或输出层的单元j 到单元j的净输入Ij是其中 wij是由上一层的单元i到单元j的连接的权 Oi是上一层的单元i的输出 而 j是单元j的偏差 用来改变单元的活性 给定单元j的净输入Ij 则单元j的输出Oj用下式 logistic函数 计算该函数又称挤压函数 因为它将一个较大的输入值域映射到较小的区间0到1 72 一个神经元 Neuron 一个隐藏或输出单元j j的输入是来自前一层的输出 这些与对应的权相乘 以形成加权和 加权和加到与单元j相联的偏差上 一个非线性的活化函数用于净输入 73 神经网络的激活函数 线性函数 S型函数 双曲正切函数 符号函数 74 后向传播 续 后向传播误差通过更新权和反映网络预测误差的偏置 向后传播误差对于输出层单元j 误差Errj用下式计算其中 Oj是单元j的实际输出 而Tj是j基于给定训练样本的已知类标号的真正输出 Oj 1 Oj 是logistic函数的导数隐藏层单元j的误差是其中 wkj是由下一较高层中单元k到单元j的连接权 而Errk是单元k的误差 75 后向传播 续 后向传播误差 续 更新权和偏置 以反映传播的误差权由下式更新其中 wij是权wij的改变 变量l是学习率 通常取0和1之间的值 学习率帮助避免陷入判定空间的局部最小学习率调整规则 将学习率设置为1 t 其中t是已对训练样本集迭代的次数偏置由下式更新其中 j是偏置 j的改变 76 后向传播 续 实例更新VS 周期更新实例更新 caseupdate 每处理一个样本就更新权值和偏置周期更新 epochupdate 处理完训练集中的所有样本之后再更新权值和偏置终止条件前一周期所有的 wij都小于某个指定的阈值 或前一周期未正确分类的样本百分比小于某个阈值 或超过预先指定的周期数实践中 权值收敛可能需要数十万个周期 77 后向传播算法 输入D 由训练元组和它们的相关联的目标值组成的数据集l 学习率Network 多层前馈网络输出 训练后的神经网络方法 1 初始化network的权和偏置 2 while 终止条件不满足 3 for D中每个训练元组X 4 向前传播输入 5 for每个输入层单元j 6 Oj Ij 输入单元的输出是它的实际输入值 7 for 隐藏或输出层每个单元j 8 相对于前一层i 计算单元j的净输入 9 计算单元j的输出 78 后向传播算法 续 10 后向传播误差 11 for输出层每个单元j 12 Errj Oj 1 Oj Tj Oj 计算误差 13 for 由最后一个到第一个隐藏层 对于隐藏层每个单元j 14 计算下一个较高层k的误差 15 fornetwor中每个权wij 16 wij l ErrjOi 权值增量 17 wij wij wij 权值更新 18 fornetwor中每个偏差 j 19 j l Errj 偏置增量 20 j j j 偏置更新 21 79 后向传播 例 一个多层前馈神经网络第一个训练样本X 1 0 1 其类标号为1 80 后向传播 例 续 初始输入 权值和偏差值净输入和输出的计算计算每个结点的误差 81 后向传播 例 续 计算权和偏置的更新 82 神经网络的特点 至少含有一个隐藏层的多层神经网络是一种普适近似 universalapproximator 即可以用来近似任何目标函数ANN可以处理冗余特征权值在训练过程中自动学习 冗余特征的权值非常小神经网络对训练数据中的噪声非常敏感使用确认集来确定模型的泛化误差每次迭代把权值减少一个因子使用的梯度下降方法经常会收敛到局部最小值权值更新公式中加上一个动量项训练ANN是一个很耗时的过程 但分类非常快 83 5 5支持向量机 84 支持向量机 支持向量机 SupportVectorMachines SVM 源于Vapnik和Chervonenkis的统计学习理论的早期工作第一篇论文是Boser Guyon和Vapnik BGV92 的文章优点对复杂的非线性边界的建模能力与其它模型相比 它们不太容易过分拟合支持向量机还提供了学习模型的紧凑表示广泛的使用范围SVM可以用来预测和分类它们已经用在许多领域 包括手写数字识别 对象识别 演说人识别 以及基准时间序列预测检验 85 支持向量机 两个线性可分的类找到这样一个超平面 使得所有的方块位于这个超平面的一侧 而所有的圆圈位于它的另一侧可能存在无穷多个那样的超平面 86 决策边界的边缘 找这样的超平面 它最大化边缘B1比B2好 87 SVM的决策边界和边缘 一个线性分类器的决策边界可以写成如下形式 wx b 0其中 w和b是模型的参数 88 边缘 方块的类标号为 1 圆圈的类标号为 1z的类标号y调整决策边界的参数w和b 两个平行的超平面bi1和bi2可以表示如下bi1 w x b 1bi2 w x b 1可以证明 边缘d 89 边缘推导 w的方向垂直于决策边界如果xa和xb是任意两个位于决策边界上的点 则wxa b 0 wxb b 0于是w xb xa 0 由于xb xa是决策超平面中任意向量 于是w的方向必然垂直于决策边界令x1是bi1上的数据点 x2是bi2上的数据点 代入bi1和bi2相减得到w x1 x2 2由令u w v x1 x2 得到 w x1 x2 cos w x1 x2 2 90 边缘推导 续 但 x1 x2 cos w x1 x2 d于是 w d 2 即 91 SVM SVM的训练阶段从训练数据中估计决策边界的参数w和b最大化边缘d 并满足wxi b 1如果yi 1wxi b 1如果yi 1即yi wxi b 1最大化d等价于最小化这是一个凸二次优化问题 可以通过标准的拉格朗日乘子 Lagrangemultiplier 方法求解 92 SVM 续 拉格朗日算子其中 参数 i称为拉格朗日乘子对Lp关于w和b求偏导 并令它们等于零因为拉格朗日乘子 i是未知的 因此仍然不能得到w和b的解 5 38 5 39 5 40 93 SVM 续 使用Karuch Kuhn Tucher KKT 条件 i 0 i yi wxi b 1 0 5 42 除非训练实例满足方程yi wxi b 1 否则拉格朗日乘子 i必须为零 i 0的训练实例位于超平面bi1或bi2上 称为支持向量 5 39 和 5 40 代入到公式 5 38 中这是Lp的对偶问题 最大化问题 可以使用数值计算技术 如二次规划来求解 5 43 94 SVM 续 解出 i后 用 5 39 求w 再用 5 42 求b决策边界为z可以按以下的公式来分类如果f z 1 则检验实例z被分为到正类 否则分到负类 95 SVM 例 例 二维数据集包含8个训练实例使用二次规划方法 求解优化问题LD 得到 i w1 iyixi1 65 5261 1 0 3858 65 5261 1 0 4871 6 64w2 iyixi2 65 5261 1 0 4687 65 5261 1 0 611 9 32b 1 1 wx1 1 6 64 0 3858 9 32 0 4687 7 9300b 2 1 wx2 1 6 64 0 4871 9 32 0 611 7 9289b b 1 b 2 2 7 93 i 96 SVM 不可分情况 如果不是线性可分的 怎么办 软边缘 softmargin 允许一定训练误差引入松驰变量 i其中C和k是用户指定的参数 对误分训练实例加罚取k 1 C根据模型在确认集上的性能选择 97 SVM 不可分情况 续 拉格朗日算子其中 前面两项是需要最小化的目标函数 第三项表示与松弛变量相关的不等式约束 而最后一项是要求 i的值非负的结果KKT条件 i 0 i 0 i 0 i yi w xi b 1 i 0 i i 0 98 SVM 不可分情况 续 令L关于w b和 i的一阶导数为零 99 SVM 不可分情况 续 对偶拉格朗日问题其形式与可分情况相同 但是0 i C 100 非线性SVM 使用非线性变换 例 101 非线性SVM 续 非线性SVM的优化问题约束条件 yi w xi b 1 i 1 2 N对偶拉格朗日问题参数w和b 102 非线性SVM 续 实例z分类点积 xi xj 计算问题能否在原空间直接计算 例 103 核技术 Mercer定理 核函数K可以表示为K u v u v 当且仅当对于任意满足g x 2dx为有限值的函数g x 则K x y g x g y dxdy 0满足定理5 1的核函数称为正定 positivedefinite 核函数常用核函数 104 SVM的特点 SVM学习问题可以表示为凸优化问题 因此可以利用已知的有效算法发现目标函数的全局最小值SVM通过最大化决策边界的边缘来控制模型的能力需要提供其他参数 如使用的核函数类型 为了引入松弛变量所需的代价函数C等分类属性处理每个分类属性值引入一个哑变量 转化为二元变量可以推广到多类问题 105 多类问题 SVM是对二类问题设计的还有一些方法也是针对二类问题的如何处理多类问题 训练令Y y1 y2 yK 是类标号的集合1 r方法 分解成K个二类问题每一个类yi Y创建一个二类问题 其中所有属于yi的样本都被看作正类 而其他样本作为负类1 1方法 构建K K 1 2个二类分类器每一个分类器用来区分一对类 yi yj 为类 yi yj 构建二类分类器时 不属于yi或yj的样本被忽略掉 106 多类问题 续 分类投票表决票的计算1 r方法如果一个样本被分为正类 则正类得一票如果一个样本被分为负类 则除正类之外的所有类都得到一票1 1方法如果Cj把样本分到yi类 则yi类得一票冲突处理分到多数类 少数类 107 多类问题 例 例 Y y1 y2 y3 y4 1 r方法建立4个分类器设这4个分类器分别把检验实例x分类为 使用简单的多数表决 y1得到最高的票4 而其他类仅仅得到3票 因此检验实例被分类为y11 1方法建立6个分类器假设它们对x如下表y1和y4都得到2票 而y2和y3仅仅得到1票 108 5 6组合方法 109 一般思想 聚集多个分类器的预测来提高分类准确率称为组合 ensemble 或分类器组合 classifiercombination 方法 110 Whydoesitwork 假定有25基分类器每个基分类器的误差均为 0 35假定基分类器是独立的组合分类器错误预测的概率为 111 Bagging Bagging又称自助聚集 bootstrapaggregating 训练阶段使用自助抽样产生多个训练数据集有放回 等概率 等容量抽样在每个训练数据集上使用相同的分类算法建立基分类器分类 x是待分类实例每个基分类器独立地对x产生类预测 算作一票统计得票 并将x指派到得票最高的类 112 Boosting 基本思想训练赋予每个训练记录一个权值wi权值反映对元组分类的困难程度迭代地学习k个分类器 学习得到分类器Mi之后 更新权值 使得其后的分类器Mi 1 更关注 被Mi误分类的训练元组分类 x是待分类实例每个基分类器独立地对x产生类预测通过基分类器的加权投票产生x最终的类预测 其中每个分类器投票的权重是其准确率的函数 113 Adaboost 一种流行的boosting方法基本思想令 xj yj j 1 2 N 表示包含N个训练样本的集合训练1 每个训练样本一个抽样权重wj 初始 wj 1 N i 12 采用有放回 等容量 加权抽样 产生训练集 建立基分类器Ci3 计算Ci的分类误差 i 并调整每个记录的抽样权重wj4 如果 i 0 5 则令wj 1 N 转步骤25 计算Ci的重要性 i6 如果i k 则i i 1 转步骤2分类1 每个Ci产生x的类预测Ci x 2 组合分类器预测 114 Adaboost 续 Ci的分类误差 i基分类器Ci的重要性权值更新1 2 规范化诸wi 使得 5 68 和算法5 7的行7需要修改 115 RotationForest 旋转森林 RF 使用整个训练数据集 不抽样 建立多个基分类器通过不同特征变换 把数据变换到不同的新的特征空间这是真正意义下的从不同角度分析数据在不同的变换后的空间上 使用决策树建立不同的基分类器J J Rodriguez L I Kuncheva C J Alonso RotationForest anewclassifierensemblemethod IEEETrans PatternAnal Mach Intell 28 2006 1619 1630 116 RotationForest 续 训练建立第i个基分类器把特征集F随机地划分为K个不相交的子集 将训练数据集投影到每个特征子集上 使用PCA得到每个特征子集的主成分Tij表示到第j个特征子集的主成分的变换 这些Tij形成一个如下形式的矩阵按照特征集F中的特征次序调整Ti的诸列 得到一个特征变换矩阵 记作Ti XTi y 为训练数据 使用决策树算法建立基分类器Ci 117 5 7不平衡类问题 118 准确率的局限性 考虑一个两类问题0类的实例数 99901类的实例数 10如果模型预测每个实例为0类 则准确率为9990 10000 99 9 准确率是误导 因为模型不能正确预测任何1类实例 119 其它度量 混淆矩阵真正率 truepositiverate TPR 或灵敏度 sensitivity TPR TP TP FN 真负率 turenegativerate TNR 或特指度 specificity TNR TN TN FP 假正率 falsepositiverate FPR FPR FP TN FP 假负率 falsenegativerate FNR FNR FN TP FN 120 其它度量 续 两个广泛使用的度量召回率 recall 和精度 precision F1度量 121 ROC曲线 Developedin1950sforsignaldetectiontheorytoanalyzenoisysignalsCharacterizethetrade offbetweenpositivehitsandfalsealarmsROCcurveplotsTP onthey axis againstFP onthex axis PerformanceofeachclassifierrepresentedasapointontheROCcurvechangingthethresholdofalgorithm sampledistributionorcostmatrixchangesthelocationofthepoint 122 ROC曲线 续 TP FP 0 0 declareeverythingtobenegativeclass 1 1 declareeverythingtobepositiveclass 1 0 idealDiagonalline RandomguessingBelowdiagonalline predictionisoppositeofthetrueclass 123 UsingROCforModelComparison NomodelconsistentlyoutperformtheotherM1isbetterforsmallFPRM2isbetterforlargeFPRAreaUndertheROC