《第5章数据分类专业教育》由会员分享，可在线阅读，更多相关《第5章数据分类专业教育（34页珍藏版）》请在金锄头文库上搜索。
1、第第5章章 数据分类数据分类1学习幻灯学习幻灯5.1 引例引例分类的定义分类的定义l分分类类是是指指把把数数据据样样本本映映射射到到一一个个事事先先定定义义的的类类中中的的学学习习过过程程，即即给给定定一一组组输输入入的的属属性性向向量量及及其其对对应应的的类类，用用基基于于归归纳纳的学习算法得出分类。的学习算法得出分类。2学习幻灯学习幻灯5.1 引例引例AgeSalaryClass30highc125highc221lowc243highc118lowc233lowc1描述属性描述属性类别属性类别属性分类问题使用的数据集格式：分类问题使用的数据集格式：3学习幻灯学习幻灯5.1 引例引例分类问
2、题使用的数据集格式分类问题使用的数据集格式l描描述述属属性性可可以以是是连连续续型型属属性性，也也可可以以是是离散型属性；离散型属性；l类别属性类别属性必须是离散型属性。必须是离散型属性。 l连连续续型型属属性性是是指指在在某某一一个个区区间间或或者者无无穷穷区区间间内内该该属属性的取值是连续的，例如属性性的取值是连续的，例如属性“AgeAge” l离离散散型型属属性性是是指指该该属属性性的的取取值值是是不不连连续续的的，例例如如属属性性“SalarySalary”和和“ClassClass” 4学习幻灯学习幻灯5.1 引例引例分类问题使用的数据集格式分类问题使用的数据集格式l分分类类问问题题
3、中中使使用用的的数数据据集集可可以以表表示示为为X=X=(x(xi i,y,yi i)|i=1,2,)|i=1,2,total,totallx xi i=(x=(xi1i1,x,xi2i2, ,x,xidid) ) ，其其中中x xi1i1,x,xi2i2, ,x,xidid分分别别对应对应d d个描述属性个描述属性A A1 1,A,A2 2, ,A,Ad d的具体取值的具体取值ly yi i表表示示数数据据样样本本x xi i的的类类标标号号，假假设设给给定定数数据据集集包包含含m m个个类类别别，则则y yi icc1 1,c,c2 2, ,c,cm m ，其其中中c c1 1,c,c2
4、2, ,c,cm m是类别属性是类别属性C C的具体取值的具体取值l未未知知类类标标号号的的数数据据样样本本x x用用d d维维特特征征向向量量x=x=(x(x1 1,x,x2 2, ,x,xd d) )来表示来表示5学习幻灯学习幻灯5.2 分类问题概述分类问题概述5.2.1 5.2.1 分类的过程分类的过程5.2.2 5.2.2 分类的评价准则分类的评价准则6学习幻灯学习幻灯5.2.1 分类的过程分类的过程获取数据获取数据预处理预处理分类器设计分类器设计分类决策分类决策7学习幻灯学习幻灯5.2.1 分类的过程分类的过程获取数据获取数据l输入数据、对数据进行量化输入数据、对数据进行量化预处理预
5、处理l去除噪声数据、对空缺值进行处理去除噪声数据、对空缺值进行处理l数据集成或者变换数据集成或者变换 分类器设计分类器设计l划分数据集、分类器构造、分类器测试划分数据集、分类器构造、分类器测试分类决策分类决策l对未知类标号的数据样本进行分类对未知类标号的数据样本进行分类8学习幻灯学习幻灯训练集与测试集训练集与测试集假如要做一个预测不同用户的购买产品的预测：假如要做一个预测不同用户的购买产品的预测：l首先：用户有他的属性如首先：用户有他的属性如 年龄、职业或者包括他的历史性息的保存。年龄、职业或者包括他的历史性息的保存。l其次：需要编写一个软件实现这种预测，而比编写软件要有真实数据其次：需要编写
6、一个软件实现这种预测，而比编写软件要有真实数据做依据，比如你得到了一个大商场的用户信息，有做依据，比如你得到了一个大商场的用户信息，有1000010000条记录。条记录。l此时可以从这此时可以从这1000010000条记录中选取条记录中选取70007000条记录，作为训练集。条记录，作为训练集。l比如说：让程序根据用户的基本信息预测出购买信息，再做出对比，比如说：让程序根据用户的基本信息预测出购买信息，再做出对比，直至效果达到满意程度为止。直至效果达到满意程度为止。l程序编完了后，因为你再编程过程中是利用训练集的数据为依据的，程序编完了后，因为你再编程过程中是利用训练集的数据为依据的，所以你的
7、程序很可能有局限性，值局限于训练集的数据上。所以你的程序很可能有局限性，值局限于训练集的数据上。l你就可以使用哪剩下的你就可以使用哪剩下的30003000条数据，即测试集，用它来测试你软件是条数据，即测试集，用它来测试你软件是否具有普遍性。否具有普遍性。9学习幻灯学习幻灯5.2.2 分类的评价准则分类的评价准则l给给定定测测试试集集X Xtesttest=(x=(xi i,y,yi i)|i=1,2,)|i=1,2,N,NlN N表示测试集中的样本个数表示测试集中的样本个数lx xi i表示测试集中的数据样本表示测试集中的数据样本ly yi i表示数据样本表示数据样本xixi的类标号的类标号l
8、对于测试集的第对于测试集的第j j个类别，假设个类别，假设l被正确分类的样本数量为被正确分类的样本数量为TPTPj jl被错误分类的样本数量为被错误分类的样本数量为FNFNj jl其其他他类类别别被被错错误误分分类类为为该该类类的的样样本本数数据据量量为为FPFPj j10学习幻灯学习幻灯5.2.2 分类的评价准则分类的评价准则l精精确确度度：代代表表测测试试集集中中被被正正确确分分类类的数据样本所占的比例的数据样本所占的比例 11学习幻灯学习幻灯5.2.2 分类的评价准则分类的评价准则l查查全全率率：表表示示在在本本类类样样本本中中被被正正确确分分类的样本所占的比例类的样本所占的比例 l查查
9、准准率率：表表示示被被分分类类为为该该类类的的样样本本中中，真正属于该类的样本所占的比例真正属于该类的样本所占的比例 12学习幻灯学习幻灯5.2.2 分类的评价准则分类的评价准则lF-measureF-measure：是是查查全全率率和和查查准准率率的的组组合表达式合表达式 l是可以调节的，通常取值为是可以调节的，通常取值为1 1 13学习幻灯学习幻灯5.2.2 分类的评价准则分类的评价准则l几几何何均均值值 ：是是各各个个类类别别的的查查全全率率的的平方根平方根 14学习幻灯学习幻灯5.3 决策树决策树 l5.3.1 5.3.1 决策树的基本概念决策树的基本概念l5.3.2 5.3.2 决策
10、树算法决策树算法ID3ID3l5.3.3 ID35.3.3 ID3算法应用举例算法应用举例l5.3.4 5.3.4 决策树算法决策树算法C4.5C4.5l5.3.5 SQL Server 20055.3.5 SQL Server 2005中的决策树应用中的决策树应用l5.3.6 5.3.6 决策树剪枝决策树剪枝15学习幻灯学习幻灯5.3 决策树决策树决策树的优点：决策树的优点：l进进行行分分类类器器设设计计时时，决决策策树树分分类类方方法法所所需需时时间间相相对对较少；较少；l决决策策树树的的分分类类模模型型是是树树状状结结构构，简简单单直直观观，比比较较符符合人类的理解方式；合人类的理解方式
11、；l可可以以将将决决策策树树中中到到达达每每个个叶叶节节点点的的路路径径转转换换为为IFIFTHENTHEN形式的分类规则，这种形式更有利于理解；形式的分类规则，这种形式更有利于理解；l适用于离散值属性、连续值属性；适用于离散值属性、连续值属性；l采采用用自自顶顶向向下下的的递递归归方方式式产产生生一一个个类类似似于于流流程程图图的的树结构；树结构；l在在根根节节点点和和各各内内部部节节点点上上选选择择合合适适的的描描述述属属性性，并并且根据该属性的不同取值向下建立分枝。且根据该属性的不同取值向下建立分枝。16学习幻灯学习幻灯5.3.1 决策树的基本概念决策树的基本概念公司职员公司职员年龄年龄
12、收入收入信誉度信誉度买保险买保险否否40高高良良c2否否40高高优优c2否否4150高高良良c1否否50中中良良c1是是50低低良良c1是是50低低优优c2是是4150低低优优c1否否40中中良良c2是是40低低良良c1是是50中中良良c1是是40中中优优c1否否4150中中优优c1是是4150高高良良c1否否50中中优优c2描述属性描述属性类别属性类别属性17学习幻灯学习幻灯5.3.1 决策树的基本概念决策树的基本概念年龄年龄公司职员公司职员信誉度信誉度c1c2c1c2c140415050是是否否良良优优18学习幻灯学习幻灯5.3.2 决策树算法决策树算法ID3lID3ID3只只能能处处理理
13、离离散散型型描描述述属属性性；在在选选择择根根节节点点和和各各个个内内部部节节点点上上的的分分枝枝属属性性时时，采采用用信信息息增增益益作作为为度度量量标标准准，选选择择具具有有最最高高信信息息增增益益的的描描述述属属性性作作为为分枝属性。分枝属性。19学习幻灯学习幻灯5.3.2 决策树算法决策树算法ID3lX=(xi,yi)|i=1,2,total；lxi=(xi1, xi2, xid)对应对应d个描述属性个描述属性A1,A2,Ad的的具体取值；具体取值；lyi(i=1,2,total)表示样本表示样本xi的类标号，假设要研的类标号，假设要研究的分类问题含有究的分类问题含有m个类别，则个类别
14、，则yi c1,c2,cm。l假假设设n nj j是是数数据据集集X X中中属属于于类类别别c cj j的的样样本本数数量量，则则各各类类别别的的先先验概率验概率为为P(cP(cj j)=n)=nj j/total/total，j=1,2,j=1,2,m,m。20学习幻灯学习幻灯5.3.2 决策树算法决策树算法ID3l对于数据集对于数据集X X，计算，计算期望信息期望信息l计算描述属性计算描述属性A Af f划分数据集划分数据集X X所得的熵所得的熵l假假设设A Af f有有q q个个不不同同取取值值，将将X X划划分分为为q q个个子子集集XX1 1,X,X2 2, ,X,Xs s, ,X
15、Xq q l假假设设n ns s表表示示X Xs s中中的的样样本本数数量量，n njsjs表表示示X Xs s中中属于类别属于类别c cj j的样本数量的样本数量 21学习幻灯学习幻灯5.3.2 决策树算法决策树算法ID3l由描述属性由描述属性A Af f划分数据集划分数据集X X所得的所得的熵熵为为l其中其中l计算计算A Af f划分数据集时的划分数据集时的信息增益信息增益Gain(AGain(Af f)=I(n)=I(n1 1,n,n2 2, ,n,nm m)-E(A)-E(Af f) ) 22学习幻灯学习幻灯5.3.2 决策树算法决策树算法ID3输入：输入：给定训练集Xtrain，其中
16、每一个训练样本都是由一组描述属性的具体取值表示的特征向量，并且每个训练样本都有类标号；给定描述属性组成的集合，作为决策树中根结点和各内部结点上的分枝属性的候选集。输出：输出：决策树。（1）如果训练集Xtrain中的样本都属于同一个类别，则将根结点标记为叶结点，否则进行第（2）步。（2）如果描述属性集为空集，则将根结点标记为叶结点，类标号为Xtrain中包含样本数量最多的类标号，否则进行第（3）步。（3）根据信息增益评价标准，从给定的描述属性集中选择一个信息增益的值最大的描述属性作为根结点的分枝属性，之后进行第（4）步。（4）按照根结点中分枝属性的具体取值从根结点进行分枝，假设测试属性有l种取值
17、，则Xtrain被划分为l个样本子集，每个具体的样本子集对应一个分枝，而且其中的样本具有相同的属性值，之后进行第（5）步。（5）对于根结点下面的各个内部结点，采用递归调用的方法重复步骤（1）（4），继续选择最佳的分枝作为内部结点，直到所有的样本都被归类于某个叶节点为止。说明：对于每个内部结点，在进行上述操作时使用的数据不再是说明：对于每个内部结点，在进行上述操作时使用的数据不再是X Xtraintrain ，而是该，而是该结点上所包含的样本子集。此外，选择下层结点的分枝属性时，上层节点中结点上所包含的样本子集。此外，选择下层结点的分枝属性时，上层节点中用到的描述属性不再作为候选属性。用到的描述
18、属性不再作为候选属性。23学习幻灯学习幻灯5.3.3 ID3算法应用举例算法应用举例l参考书本的参考书本的p114116p114116。ID3ID3算法缺点：算法缺点：l信息增益的缺点是倾向于选择取值较多的信息增益的缺点是倾向于选择取值较多的属性，在有些情况下这类属性可能不会提属性，在有些情况下这类属性可能不会提供太多有价值的信息。供太多有价值的信息。l只能对描述属性为离散型属性的数据集构只能对描述属性为离散型属性的数据集构造决策树。造决策树。24学习幻灯学习幻灯5.3.4 决策树算法决策树算法C4.5lC4.5C4.5算算法法使使用用信信息息增增益益比比来来选选择择分分枝枝属属性性，克克服服
19、了了ID3ID3算算法法使使用用信信息息增增益益时时偏向于取值较多的属性的不足偏向于取值较多的属性的不足l信息增益比信息增益比的定义式为的定义式为l其中其中25学习幻灯学习幻灯5.3.4 决策树算法决策树算法C4.5lC4.5C4.5既既可可以以处处理理离离散散型型描描述述属属性性，也也可以处理连续型描述属性可以处理连续型描述属性 l对对于于连连续续值值描描述述属属性性，C4.5C4.5将将其其转转换换为离散值属性为离散值属性l在在AA1c1c,A,A2c2c, ,A,Atotalctotalc 中中生生成成total-1total-1个个分分割点割点l第第i i个分割点的取值设置个分割点的取
20、值设置v vi i=(A=(Aicic+A+A(i+1)c(i+1)c)/2)/2 l每个分割点将数据集划分为两个子集每个分割点将数据集划分为两个子集l挑选挑选最适合的分割点最适合的分割点对连续属性离散化对连续属性离散化信息增益比最大信息增益比最大26学习幻灯学习幻灯5.3.5 SQL Server 2005中的决策树应用中的决策树应用 l创建创建 Analysis Services Analysis Services 项目项目 l创建数据源创建数据源 l创建数据源视图创建数据源视图 l创建决策树挖掘结构创建决策树挖掘结构 l设置决策树挖掘结构的相关参数设置决策树挖掘结构的相关参数 l建立决策
21、树挖掘模型建立决策树挖掘模型 l查看挖掘结果查看挖掘结果 27学习幻灯学习幻灯5.3.6 决策树剪枝决策树剪枝l决决策策树树剪剪枝枝过过程程试试图图检检测测和和去去掉掉多多余余的的分分枝枝，以以提提高高对对未未知知类类标标号号的的数数据据进进行行分分类类时的准确性时的准确性l先先剪剪枝枝方方法法：在在生生成成决决策策树树的的过过程程中中对对树树进进行行剪枝。剪枝。 l后剪枝方法：在生成决策树之后对树进行剪枝。后剪枝方法：在生成决策树之后对树进行剪枝。l组合式方法：交叉使用先剪枝和后剪枝方法。组合式方法：交叉使用先剪枝和后剪枝方法。后剪枝所需的计算比先剪枝多，但通常产生更可靠的树。后剪枝所需的计
22、算比先剪枝多，但通常产生更可靠的树。28学习幻灯学习幻灯5.4 支持向量机支持向量机l支持向量机的分类示意图为支持向量机的分类示意图为MarginH2H1Hw29学习幻灯学习幻灯5.4 支持向量机支持向量机l两类样本之间的分类间隔两类样本之间的分类间隔(Margin)(Margin)为为l支支持持向向量量机机的的目目的的是是使使r r最最大大，等等价价于于使使 或者或者 最小最小30学习幻灯学习幻灯5.4 支持向量机支持向量机l支持向量机使分类间隔最大可以转化支持向量机使分类间隔最大可以转化为如下的约束优化问题为如下的约束优化问题lMaxMaxlSubject toSubject to31学习
23、幻灯学习幻灯5.4 支持向量机支持向量机l求解约束优化问题，可以得到支持向求解约束优化问题，可以得到支持向量机的最优分类函数量机的最优分类函数l对于未知类标号的数据样本，可以使对于未知类标号的数据样本，可以使用最优分类函数对其进行分类用最优分类函数对其进行分类核函数核函数32学习幻灯学习幻灯5.5 近邻分类方法近邻分类方法l近邻分类方法是基于实例的分类方法近邻分类方法是基于实例的分类方法l不需要事先进行分类器的设计不需要事先进行分类器的设计l直接使用训练集对未知类标号的数据直接使用训练集对未知类标号的数据样本进行分类样本进行分类 l最近邻分类、最近邻分类、k-k-近邻分类近邻分类33学习幻灯学习幻灯5.5 近邻分类方法近邻分类方法k=1时为最近邻分类时为最近邻分类k1时为时为k k近邻分类近邻分类34学习幻灯学习幻灯
