商务智能原理与方法（第3版）-课件 Lecture4-Classification

数据挖掘——分类内容安排分类问题简介决策树分类贝叶斯分类关联规则分类其他分类方法分类方法介绍分类性能度量分类问题一组人体特征的统计资料性别身高(英尺)体重(磅)脚掌(英寸)男618012男5.9219011男5.9817012男5.9216510女51006女5.51508女5.421307女5.751509已知某人身高6英尺，体重130磅，脚掌8英寸，请问该人是男是女？分类问题SNS社区不真实账号、使用虚假身份或用户的小号检测出不真实账号在运营分析报告中避免这些账号的干扰加强对SNS社区的了解与监管SNS社区的运营商据某社区网站的统计，该站10000个账号中有89%为真实账号C0，11%为虚假账号C1F1:日志数量/注册天数

F2:好友数量/注册天数

F3:是否使用真实头像（真实头像为1，非真实头像为0）F1=0.1，F2=0.2，F3=0，真实账号还是虚假账号？分类应用分类广泛应用于决策分析的各个领域，基于数据构建趋势描述模型对未来做出预测银行的信用评级文献的整理归档客户细分特征的认定疾病的严重程度划分产品/服务评论的有用性估计分类vs聚类分类与聚类的区别有监督学习提供了每个训练元组的类标号填空题无监督学习每个训练元组的类标号是未知的要学习的类的个数或集合也可能事先不知道问答题分类简介分类所要解决的问题是将一个事件或对象划分到给定的类别上银行可以基于收入水平、工作情况等对给定客户进行信用风险分析，确定客户的风险等级假设有一组历史数据，反映了动物类别的信息，可根据这些数据进行分类来描述动物属性与类别之间的对应关系分类简介序

号食

肉产

奶有

鳍有

毒类

别11010鱼类21100哺乳动物30010鱼类40101哺乳动物51011鱼类61001爬行动物71010鱼类81001爬行动物91100哺乳动物100001爬行动物110001爬行动物如果“有鳍”则为“鱼类”；如果“无鳍”且“产奶”则为“哺乳动物”；如果“无鳍”且“不产奶”则为“爬行动物”分类过程分类过程主要包含两个步骤：第一步，分析已知数据情况，建立一个分类模型以描述已知数据属性与给定类别之间的对应关系，该分类模型也被称做分类器训练集分类过程的第二步是利用所获得的分类模型（分类器）对新数据的类别进行预测。测试集生成分类器生成分类器的目的就是通过分析训练集的数据来概括训练集数据的属性向量与类别之间的关系形如：X

C，表明“若记录t满足条件X，则t为类别C”分类器通常可以表示为分类规则、决策树、数学公式等形式分类预测要使用测试集对分类器的分类准确率进行估计测试集的结构与训练集的结构相同由于生成分类器的过程倾向于过分逼近训练数据，可能造成对分类准确率的估计过于乐观过拟合(Overfit)如果一个分类器的准确率经测试被认为是可以接受的，那么就可以使用此分类器对未来数据对象进行分类。决策树分类决策树（DT，DecisionTree）是一个类似流程图的树形结构以树的形式采用自上而下的方式给出分类规则多种决策树方法，如ID3,C4.5,CART,SLIQ等C4.5方法是决策树分类方法中的代表决策树分类决策树方法可以划分为两阶段决策树构建决策树可以转换为分类规则形式根据训练集得到一个粗略的、基础的树形结构在每个内部节点上确定分裂属性和对应的测试内容决策树剪枝有许多由数据集中的噪声或异常数据所产生的分枝决策树剪枝就是识别并消除这类分枝，以帮助改善对未知对象分类的准确性决策树构建递归地从所有可选的属性中选择“最优”的分裂属性，直至满足某个结束条件为止“最优”意为根据该属性上的不同值能够把训练集分为彼此之间“差异”最大的几部分决策树构建初始构建决策树时，作为一个单个节点（根节点）代表了所有的训练样本集数据对于任意一个节点，如果对应的样本均为同一类别，则该节点就成为叶子节点并标记为该类别分裂属性的每一个值均对应一个将要被创建的分枝这个分枝或连接一个叶子节点（类别），或连接一个内部节点（对应一个分裂属性）否则，将选择合适的分裂属性递归上述过程，可为每个分枝赋予一个节点决策树构建训练集中每一个属性都包含了一定的信息，这些信息的作用是减少整个数据集的不确定性信息增益方法选择具有最高信息增益（即信息熵减少的程度最大）的属性作为当前节点的分裂属性使划分获得的训练样本子集进行分类所需要的信息最少所产生的各样本子集中的“不同类别混合程度”降为最低决策树构建假设从一个数据集T中随意抽出一个样本并说明它属于某个类别Ck，这个消息出现的概率是，它所表达的信息量是。T中某个记录的类别所需的平均信息量|T|表示数据集T中的记录总数，表示数据集T中属于类别Ck的记录数。决策树构建假设属性A有n个不同的取值，可将训练数据集T分为n个子集T1，T2，…，Tn。属性A对数据集T进行划分之后的信息增益根据属性A的n个不同取值将数据集T分成n个子集之后，期望的平均信息量为决策树构建——示例样本数据集T。该数据集包含三个类别：鱼类C1、爬行动物C2和哺乳动物C3；四个属性：食肉P、产奶M、有鳍F和有毒Vg=3，|T|=11，每个属性均为布尔值，因此所有n均为2。freq(C1,T)=4，freq(C2,T)=4，freq(C3,T)=3决策树构建——示例首先计算所有样本分类需要的期望信息量info(T)=–4/11×log2(4/11)–4/11×log2(4/11)–3/11×log2(3/11)=1.5726序

号食

肉产

奶有

鳍有

毒类

别11010鱼类21100哺乳动物30010鱼类40101哺乳动物51011鱼类61001爬行动物71010鱼类81001爬行动物91100哺乳动物100001爬行动物110001爬行动物决策树构建——示例计算每一个属性的期望信息量。首先计算属性P（食肉）的期望信息量T1=7（P=1），T2=4（P=0）。其中freq(C1,T1)=3，freq(C2,T1)=2，freq(C3,T1)=2因此有：info(T1)=–3/7×log2(3/7)–2/7×log2(2/7)–2/7×log2(2/7)=1.5567。freq(C1,T2)=1，freq(C2,T2)=2，freq(C3,T2)=1因此有info(T2)=–1/4×log2(1/4)–2/4×log2(2/4)–1/4×log2(1/4)=1.5000属性P的期望信息量为：infoP(T)=7/11×1.5567+4/11×1.5000=1.5361infoM(T)=0.7273，infoF(T)=0.6270，infoV(T)=1.1240决策树构建——示例因此，根据各属性对数据集T进行划分之后所得的信息增益分别为gain(P)=info(T)–infoP(T)=0.0366gain(M)=info(T)–infoM(T)=0.8454gain(F)=info(T)–infoF(T)=0.9457gain(V)=info(T)–infoV(T)=0.4486决策树构建——示例最优分裂属性为数据集T中所有属性中信息增益最大的属性因为该属性可以最大程度地对数据进行类别划分，本数据集的最优分裂属性为“有鳍（F）”决策树构建——示例针对“F=0”的数据组成的节点进一步选择分裂属性此时需要重新计算数据集的熵与上述过程类似，可以计算得出该节点的分裂属性为“产奶（M）”，并对M的每个属性值引出一个分枝M=1或M=0时，相应的样本均属于同一属性决策树剪枝树的很多分枝属于噪声或会对分类准确率造成负面影响模型“过适应于”数据对决策树进行剪枝来提高决策树的分类能力剪枝的优点提高决策树分类的速度决策树独立于测试数据正确分类的能力也会有所提高决策树剪枝先剪枝策略在决策树构建的过程中就进行剪枝和控制后剪枝策略在决策树构建结束之后按照一定的标准进行剪枝先剪枝策略在先剪枝策略中，通过提前停止生成分枝对决策树进行剪枝。某分枝对应的样本虽然不完全属于同一类别，但仍为该分枝构建一个叶子节点可以利用信息增益等测度来对分枝生成情况（优劣）进行评估用户事先制定一个阈值难度在于如何确定一个合理的阈值阈值过大会导致决策树过于简单，分类精度降低阈值过小又会导致剪枝不够彻底。后剪枝策略首先完全地构建一个决策树，然后删除不必要的节点和对应的分枝，从而对该树进行剪枝后剪枝方法的一个典型例子是基于代价复杂性方法对于树中每个非叶子节点，计算出该节点（分枝）被剪枝后得到的新树所对应的分类错误率根据每个分枝的分类错误率及每个分枝的权重（样本分布），计算该节点不被剪枝时的分类错误率如剪枝导致分类错误率变大，则放弃剪枝，保留节点的各个分枝，否则就将相应节点分枝剪枝删去贝叶斯定理贝叶斯定理：ThomasBayes英国律师X用n个属性集的测量值描述X是一位35岁的顾客，收入为4万美元两个类别C1=购买IphoneX，C2=购买Mate10H为某种假设数据元组X属于类C1X顾客购买IphoneX贝叶斯定理P(H)先验概率任意给定顾客将购买IphoneX的概率P(H|X)后验概率知道顾客年龄和收入后，购买IphoneX的概率P(X)先验概率顾客集合中年龄为35岁，收入4万美元的概率P(X|H)后验概率已经购买IphoneX，他35岁且收入4万美元概率简单贝叶斯分类D是训练元组的类标号集合每个元组X用一个n维属性向量X={x1,x2,…,xn}表示，描述n个属性A1,A2,…,An对X的测量假设有m个类C1,C2,…,Cm，给定元组X，预测X属于类Ci的概率最大化只需要最大即可简单贝叶斯分类估计P(Ci)是D中Ci类的训练元组数估计P(X|Ci)假定属性值相互独立属性Ak是离散属性属性Ak是连续值属性，假定属性服从正态分布简单贝叶斯分类AllElectronics顾客数据库记录RIDageincomestudentcredit-ratingClass:buys_computer1YouthHighNoFairNo2YouthHighNoExcellentNo3MiddleHighNoFairYes4SeniorMediumNoFairYes5SeniorLowYesFairYes6SeniorLowYesExcellentNo7MiddlelowYesExcellentYes8YouthMediumNoFairNo9YouthLowYesFairYes10SeniorMediumYesFairYes11YouthMediumYesExcellentYes12MiddleMediumNoExcellentYes13MiddleHighYesFairYes14SeniorMediumNoExcellentNo简单贝叶斯分类希望分类的元组X=(age=youth,income=medium,student=yes,credit_rating=fair)最大化,i=1,2C1对应类buys_computer=yesC2对应类buys_computer=no计算先验概率P(Ci)P(buys_computer=yes)=9/14=0.643P(buys_computer=no)=5/14=0.357简单贝叶斯分类为计算P(X|Ci)，计算下面的条件概率P(age=youth|buys_computer=yes)=2/9=0.222P(age=youth|buys_computer=no)=3/5=0.600P(income=medium|buys_computer=yes)=4/9=0.444P(income=medium|buys_computer=no)=2/5=0.400P(student=yes|buys_computer=yes)=6/9=0.667P(student=yes|buys_computer=no)=1/5=0.200P(credit_rating=fair|buys_computer=yes)=6/9=0.667P(credit_rating=fair|buys_computer=no)=2/5=0.400简单贝叶斯分类使用上面的概率，得到P(X|buys_computer=yes)=0.222*0.444*0.667*0.667=0.044P(X|buys_computer=no)=0.600*0.400*0.200*0.400=0.019P(X|buys_computer=yes)P(buys_computer=yes)=0.044*0.643=0.028P(X|buys_computer=no)P(buys_computer=no)=0.019*0.357=0.007对于X元组，应该划分到buys_computer=yes类简单贝叶斯分类的优缺点理论上：与其他所有分类方法相比，贝叶斯分类法具有最小的错误率实践上：类条件独立性未必成立缺乏可用的概率数据拉普拉斯估计(Laplace)如果遇到零概率值怎么办？计算零概率

——拉普拉斯估计假定训练集D足够大，每个计数加1造成的概率估计的变化可以忽略不计如果对q个计数都加上1，则计算概率的对应分母上加q类buys_computer=yes包含1000个元组有0个元组income=low990个元组income=medium10个元组income=high假设D中这些事件的概率是0,0.990,0.010假定每个收入增加一个元组，重计算概率关联规则分类关联规则分类分类关联规则利用关联规则进行分类CBA,CMAR,CPAR其中X为属性集合，C为类别。CAR，ClassAssociationRules表示为形如X

C的规则，如果将C看做一种特殊属性，那么分类规则其实是关联规则的一种特例关联规则分类生成分类关联规则的两种思路首先挖掘所有关联规则，然后从中挑选出后项为类别属性的规则思路简单浪费时间，没有必要生成所有的规则直接挖掘后项为单个类别属性的分类关联规则CBA方法CBA方法D每个记录由n个条件属性和一个类别属性组成。一个候选频繁集可以描述为：X∪Ci及对应的两个指标lcount和wcount。X是n个条件属性中任意m（m<=n）个属性取值组合lcount是D中包含X的记录个数wcount是同时包含X和类别值Ci的记录的个数CBA方法给定候选频繁集Lk，根据lcount和wcount计算该候选频繁集的支持度可得到满足最小支持度的候选集Lk然后生成新的候选集Ck+1这是一个典型的Apriori过程。进而计算候选规则的置信度，最终可得到满足最小支持度和最小置信度的分类规则集。CBA方法样本数据集鱼类(C1)，爬行动物(C2)，和哺乳动物(C3)数据集包含三个类别序

号食

肉P产

奶M有

鳍F有

毒V类

别11010鱼类21100哺乳动物30010鱼类40101哺乳动物51011鱼类61001爬行动物71010鱼类81001爬行动物91100哺乳动物100001爬行动物110001爬行动物食肉(P)，产奶(M)，有鳍(F)，有毒(V)四个属性最小支持度2/11，最小置信度75%CBA方法计算1-项集的lcount和wcount值wcount(C1)=4,wcount(C2)=4,wcount(C3)=3如果某一类别的支持度小于最小支持度，那么将不再生成后项为该类的分类规则lcount(P)=7,lcount(M)=3,lcount(F)=4,lcount(V)=6P、M、F、V的lcount均不小于2，计算对应的wcountwcount(P∪C1)=3,wcount(P∪C2)=2,wcount(P∪C3)=2wcount(M∪C1)=0,wcount(M∪C2)=0,wcount(M∪C3)=3wcount(F∪C1)=4,wcount(F∪C2)=0,wcount(F∪C3)=0wcount(V∪C1)=1,wcount(V∪C2)=4,wcount(V∪C3)=1CBA方法计算2-项集的lcount和wcount值lcount(P∪M)=2,lcount(P∪F)=3,lcount(P∪V)=3,lcount(M∪F)=0,lcount(M∪V)=1,lcount(F∪V)=1选择其中满足阈值限制的项集计算wcountwcount(P∪M∪C1)=0,

wcount(P∪M∪C3)=2无需计算P∪M∪C2的wcount，因为wcount(M∪C2)=0，故P∪M∪C2不可能为频繁集。wcount(P∪F∪C1)=3无需计算P∪F∪C2的wcount，因为wcount(F∪C2)=0，故P∪F∪C2不可能为频繁集，同理P∪F∪C3也不可能为频繁集。wcount(P∪V∪C2)=2无需计算P∪V∪C1的wcount，因为wcount(V∪C1)=1，故P∪V∪C1不可能为频繁集，同理P∪V∪C1也不可能为频繁集。CBA方法计算3-项集的lcount和wcount值lcount(P∪M∪F)=0,lcount(P∪F∪V)=1不存在3项频繁集，结束。计算置信度从一项频繁集中得到：Dconf(P

C1)=3/7<75%Dconf(P

C2)=2/7<75%Dconf(P

C3)=2/7<75%对于一系列频繁集P∪Ci，我们仅需考虑wcount(P∪Ci)值最大的频繁集P∪Ci所对应的分类关联规则Dconf(M

C3)=3/3>75%Dconf(F

C1)=4/4>75%Dconf(V

C2)=4/6<75%CBA方法从2项频繁集中得到Dconf(MP

C3)=2/2>75%Dconf(PF

C1)=3/3>75%Dconf(PV

C2)=2/3<75%最终得到如下分类关联规则：M

C3withDsupp=3/11,Dconf=100%F

C1withDsupp=4/11,Dconf=100%MP

C3withDsupp=2/11,Dconf=100%PF

C1withDsupp=3/11,Dconf=100%其他分类方法神经元网络分类NeuralNetwork支持向量机分类SupportVectorMachine1.间隔与支持向量

直观上看，应该去找位于两类训练样本“正中间”的划分超平面，即图1中红色的那条，因为该划分超平面度自训练样本局部扰动的“容忍”性最好。这个划分平面所产生的分类结果是最鲁棒的，对未见示例的分化能力最强。图1存在多个划分超平面将两类样本分开1.间隔与支持向量

1.间隔与支持向量

图2支持向量与间隔它被称为间隔。1.间隔与支持向量

这就是支持向量机（SupportVectorMachine，简称SVM）的基本模型，模型中范数为w的L2范数。为什么要转成L2范数？要将目标函数转成凸二次规划问题，以满足后面对偶问题需要的KKT条件系数为1/2为了求导的时候约去系数，计算方便2.对偶问题

2.对偶问题

（10）

（11）2.对偶问题

这显示出支持向量机的一个重要性质：训练完成后，大部分的训练样本都不需保留，最终模型仅与支持向量有关。2.对偶问题式（10）是一个二次规划问题，可使用通用的规划算法来求解，然而，该问题的规模正比于训练样本数，这会在实际任务中造成很大的开销。为了避开这个障碍，可利用问题本身的特性，使用更为高效的算法，SMO(SequentialMinimalOptimization)是其中一个著名代表。

2.对偶问题

（13）

（14）2.对偶问题

（15）

（16）3.软间隔与正则化之前的讨论假设训练样本是线性可分的，即存在一个划分超平面能将训练样本正确分类，然而在现实任务中，往往很难保证训练样本在空间中线性可分，缓解该问题的一个办法是允许支持向量机在一些样本上出错。为此，要引入软间隔的概念，如图3所示。图3软间隔示意图，红色圈出了一些不满足约束的样本前面介绍的支持向量机形式是要求所有样本均满足约束（3），即所有样本都必须划分正确，这称为“硬间隔”，而软间隔则允许某些样本不满足约束

（17）3.软间隔与正则化在最大化间隔的同时，不满足约束的样本应尽可能少，于是优化目标可写为

（18）

（19）

3.软间隔与正则化

（20）（21）（22）图4三种常见的替代损失函数3.软间隔与正则化若采用hinge损失，则式（18）变成

（23）

（24）这就是常用的“软间隔支持向量机”式（24）中每个样本都有一个对应的松弛变量，用以表征该样本不满足约束（17）的程度，但是与式（6）相似，这仍是一个二次规划问题，可通过拉格朗日乘子法得到式（24）的拉格朗日函数(25)

（25）

3.软间隔与正则化

（26）

（27）

（28）将（26）-（28）代入式（25）即可得到式（24）对偶问题

（29）3.软间隔与正则化对软间隔支持向量机，KKT条件要求

（30）

由此可以看出，软间隔支持向量机的最终模型仅与支持向量有关，即通过采用hinge损失函数仍保持了稀疏性。其他分类方法前面介绍的各种分类方法具有一个共同点均通过给定的训练集构造一个分类器，利用该分类器对新记录分类，这类方法称为“急切型学习方法”（EagerLearner）与急切型学习方法对应的是“懒惰型学习方法”（LazyLearner）这类方法不构造分类器，仅仅将训练集保存起来或只对训练集做简单分析当需要对新记录进行分类时，在保存的记录中寻找与之最相似的样本，根据这个样本的类别来分类