第5章数据分类-课件

数据仓库与数据挖掘数据仓库与数据挖掘第5章 数据分类7/14/20247/14/202415.1 引例引例一、分类的定义一、分类的定义 把把数数据据样样本本映映射射到到一一个个事事先先定定义义的的类类中中的的学学习习过过程程，即即给给定定一一组组输输入入的的属属性性向向量量及及其其对对应应的的类类，用用基基于于归归纳纳的的学学习习算算法法得得出出分分类。类。例如：例如：（1）正常信用卡与欺诈信用卡的分类正常信用卡与欺诈信用卡的分类 （2）正常细胞与癌变细胞的分类正常细胞与癌变细胞的分类 （3）正常邮件与垃圾邮件的分类）正常邮件与垃圾邮件的分类25.1 引例引例c1low33c2low18c1high43c2low21c2high25c1high30ClassSalaryAge描述属性描述属性类别属性类别属性二、分类问题使用的数据集二、分类问题使用的数据集35.1 引例引例二、分类问题使用的数据集（续）二、分类问题使用的数据集（续）描述属性：连续型属性或离散型属性描述属性：连续型属性或离散型属性类别属性：离散型属性类别属性：离散型属性 连连续续型型属属性性是是指指在在某某一一个个区区间间或或者者无无穷穷区区间内该属性的取值是连续的。间内该属性的取值是连续的。例如：属性例如：属性“Age”离散型属性是指该属性的取值是不连续的。离散型属性是指该属性的取值是不连续的。例如：属性例如：属性“Salary”和和“Class”45.1 引例引例二、分类问题使用的数据集（续）二、分类问题使用的数据集（续）l分类问题中使用的数据集分类问题中使用的数据集X=(xi,yi)|i=1,2,totallxi=(xi1,xi2,xid)，其其中中xi1,xi2,xid分分别别对对应应d个个描描述属性述属性A1,A2,Ad的具体取值的具体取值lyi表表示示数数据据样样本本xi的的类类标标号号，假假设设给给定定数数据据集集包包含含m个个类类别别，则则yic1,c2,cm，其其中中c1,c2,cm是是类类别属性别属性C的具体取值的具体取值l未未知知类类标标号号的的数数据据样样本本x用用d维维特特征征向向量量x=(x1,x2,xd)来表示来表示55.2 分类问题概述分类问题概述一、一、分类的过程分类的过程二、二、分类的评价准则分类的评价准则6一、一、分类的过程分类的过程获取数据获取数据预处理预处理分类器设计分类器设计分类决策分类决策7一、分类的过程（续）一、分类的过程（续）l获取数据获取数据输入数据、对数据进行量化输入数据、对数据进行量化l预处理预处理 去除噪声数据、对空缺值进行处理去除噪声数据、对空缺值进行处理 数据集成或者变换数据集成或者变换 l分类器设计分类器设计划分数据集、分类器构造、分类器测试划分数据集、分类器构造、分类器测试l分类决策分类决策对未知类标号的数据样本进行分类对未知类标号的数据样本进行分类8二、分类的评价准则二、分类的评价准则l给定测试集给定测试集Xtest=(xi,yi)|i=1,2,NlN表示测试集中的样本个数表示测试集中的样本个数lxi表示测试集中的数据样本表示测试集中的数据样本lyi表示数据样本表示数据样本xi的类标号的类标号-m个类别个类别l对于测试集的第对于测试集的第j个类别，假设个类别，假设l被正确分类的样本数量为被正确分类的样本数量为TPjl被错误分类的样本数量为被错误分类的样本数量为FNjl其他类别被错误分类为该类的样本数据量为其他类别被错误分类为该类的样本数据量为FPj9二、分类的评价准则二、分类的评价准则l精确度精确度 代代表表测测试试集集中中被被正正确确分分类类的的数数据据样样本所占的比例。本所占的比例。10二、分类的评价准则（续）二、分类的评价准则（续）l查全率查全率 表表示示在在本本类类样样本本中中被被正正确确分分类类的的样样本本所所占的比例。占的比例。l查准率查准率 表表示示被被分分类类为为该该类类的的样样本本中中，真真正正属属于于该类的样本所占的比例。该类的样本所占的比例。11二、分类的评价准则（续）二、分类的评价准则（续）lF-measure 查全率和查准率的组合表达式查全率和查准率的组合表达式 注：注：是可以调节的，通常取值为是可以调节的，通常取值为1。12二、分类的评价准则（续）二、分类的评价准则（续）l几何均值几何均值 各个类别的查全率的平方根。各个类别的查全率的平方根。135.3 决策树决策树 一、一、决策树的基本概念决策树的基本概念二、二、决策树算法决策树算法ID3三、三、ID3算法应用举例算法应用举例四、四、决策树算法决策树算法C4.5五、五、SQL Server 2005中的决策树应用中的决策树应用六、六、决策树剪枝决策树剪枝145.3 决策树决策树ID3决策树算法l只能处理离散型描述属性。l使用信息增益最大的方法选择属性。改进算法：C4.5 离散属性、连续属性 使用信息增益比（或信息增益率）决策树算法：1966年由Hunt等提出CLS，后Quinlan在1986年提出ID3，1993年提出C4.5。155.3 决策树决策树决策树的优点l进行分类器设计时，决策树分类方法所需时间相对较少。l决策树的分类模型是树状结构，简单直观，比较符合人类的理解方式。l可以将决策树中到达每个叶节点的路径转换为IFTHEN形式的分类规则，这种形式更有利于理解。16一、一、决策树的基本概念决策树的基本概念l采采用用自自顶顶向向下下的的递递归归方方式式产产生生一一个个类类似似于于流流程程图图的的树树结结构。构。l在在根根节节点点和和各各内内部部节节点点上上根根据据给给定定的的度度量量标标准准选选择择合合适适的描述属性，并且根据该属性的不同取值向下建立分枝。的描述属性，并且根据该属性的不同取值向下建立分枝。l对对未未知知类类标标号号的的数数据据样样本本分分类类时时，从从根根节节点点开开始始逐逐层层向向下判断，直至叶节点，从而获得该数据样本的类标号。下判断，直至叶节点，从而获得该数据样本的类标号。17一、一、决策树的基本概念（续）决策树的基本概念（续）公司公司职员年年龄收入收入信誉度信誉度买保保险否否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描述属性描述属性类别属性类别属性18一、决策树的基本概念（续）一、决策树的基本概念（续）年龄年龄公司职员公司职员信誉度信誉度c1c2c1c2c140415050是是否否良良优优19二、二、决策树算法决策树算法ID3基本思想：基本思想：ID3只只能能处处理理离离散散型型描描述述属属性性；在在选选择择根根节节点点和和各各个个内内部部节节点点上上的的分分枝枝属属性性时时，采采用用信信息息增增益益作作为为度度量量标标准准，选选择择具具有有最最高高信信息息增增益益的的描描述属性作为分枝属性。述属性作为分枝属性。假假设设nj是是数数据据集集X中中属属于于类类别别cj的的样样本本数数量量，则则 各各 类类 别别 的的 先先 验验 概概 率率 为为 P(cj)=nj/total，j=1,2,m。20二、二、决策树算法决策树算法ID3（续）（续）l对于数据集对于数据集X，计算期望信息（熵），计算期望信息（熵）l计算描述属性计算描述属性Af划分数据集划分数据集X所得的熵所得的熵l假假设设Af有有q个个不不同同取取值值，将将X划划分分为为q个个子子集集X1,X2,Xs,Xq。l假假设设ns表表示示Xs中中的的样样本本数数量量，njs表表示示Xs中中属属于于类别类别cj的样本数量。的样本数量。21二、二、决策树算法决策树算法ID3（续）（续）l由描述属性由描述属性Af划分数据集划分数据集X所得的熵为所得的熵为 其中：其中：l计算计算Af划分数据集时的信息增益划分数据集时的信息增益 Gain(Af)=I(n1,n2,nm)-E(Af)22三、三、ID3算法应用举例算法应用举例l参考书本的参考书本的p114116。23四、四、决策树算法决策树算法C4.5lC4.5算算法法使使用用信信息息增增益益比比来来选选择择分分枝枝属属性性，克克服服了了ID3算算法法使使用用信信息息增增益益时时偏偏向向于于取取值值较较多多的的属属性性的不足的不足l信息增益比的定义式为信息增益比的定义式为其中：其中：24四、四、决策树算法决策树算法C4.5（续）（续）lC4.5既既可可以以处处理理离离散散型型描描述述属属性性，也也可可以以处处理理连续型描述属性连续型描述属性 l对对于于连连续续值值描描述述属属性性，C4.5将将其其转转换换为为离离散散值值属性属性l在在A1c,A2c,Atotalc中中生生成成total-1个个分分割点割点l第第i个分割点的取值设置个分割点的取值设置vi=(Aic+A(i+1)c)/2 l每个分割点将数据集划分为两个子集每个分割点将数据集划分为两个子集l挑选最适合的分割点对连续属性离散化挑选最适合的分割点对连续属性离散化25五、五、SQL Server 2005中的决策树应用中的决策树应用 l创建创建 Analysis Services 项目项目 l创建数据源创建数据源 l创建数据源视图创建数据源视图 l创建决策树挖掘结构创建决策树挖掘结构 l设置决策树挖掘结构的相关参数设置决策树挖掘结构的相关参数 l建立决策树挖掘模型建立决策树挖掘模型 l查看挖掘结果查看挖掘结果 26六、六、决策树剪枝决策树剪枝l决决策策树树剪剪枝枝过过程程试试图图检检测测和和去去掉掉多多余余的的分分枝枝，以以提高对未知类标号的数据进行分类时的准确性提高对未知类标号的数据进行分类时的准确性l先先剪剪枝枝方方法法：在在生生成成决决策策树树的的过过程程中中对对树树进进行行剪枝剪枝 l后剪枝方法：在生成决策树之后对树进行剪枝后剪枝方法：在生成决策树之后对树进行剪枝 275.5 近邻分类方法近邻分类方法u最小距离分类器最小距离分类器 将将各各类类训训练练样样本本划划分分成成若若干干子子类类，并并在在每每个个子子类类中中确确定定代代表表点点。测测试试样样本本的的类类别别则则以以其其与与这这些些代代表表点点距距离离最最近近作决策。作决策。m1m2xg(x)=0m1m2xu缺点缺点 所所选选择择的的代代表表点点并并不不一一定定能能很很好好地地代代表表各各类类，其其后后果果将将使错误率增加。使错误率增加。285 5.5.15.1 最近邻法最近邻法u近邻法近邻法非参数法非参数法 由由Cover和和Hart于于1968年年提提出出的的，随随后后得得到到理理论论上上深深入的分析与研究。入的分析与研究。u最近邻分类器最近邻分类器(nearest neighborhood classifier,nnc):最最小小距距离离分分类类器器的的一一种种极极端端的的情情况况，以以全全部部训训练练样样本本作作为为代代表表点点，计计算算测测试试样样本本与与所所有有样样本本间间的的距距离离，并并以最近邻者的类别作为决策。以最近邻者的类别作为决策。29一、最近邻决策规则一、最近邻决策规则u判别函数 对一个C类别问题，每类有Ni个样本，i1，C，则第i类i的判别函数为：表示某种距离表示某种距离（相似性）度量，常用（相似性）度量，常用欧氏距离作为相似性度欧氏距离作为相似性度量。量。30u决策规则决策规则l最近邻法在原理上最直观，方法简单。l缺点：计算量大，存储量大。一、最近邻决策规则一、最近邻决策规则31二、最近邻法错误率分析u最近邻法的错误率高于贝叶斯错误率，可以证明以下关系式最近邻法的错误率高于贝叶斯错误率，可以证明以下关系式成立：成立：uP*为贝叶斯错误率，一般情况下P*很小，可粗略表示成：u粗略说最近邻法的渐近平均错误率在贝叶斯错误率的两倍之内。最近邻法的错最近邻法的错误率误率325.5.2 5.5.2 k-近邻法近邻法uk-近邻法最近邻法的推广近邻法最近邻法的推广 取取未未知知样样本本x的的k个个近近邻邻，看看这这k个个近近邻邻中中多多数数属属于于哪哪一类，就将一类，就将x归为哪一类。归为哪一类。u判别函数判别函数 假假设设所所有有N个个样样本本中中，来来自自i类的的样本本有有Ni个个，若若测测试试样样本本的的k个个最最近近邻邻所所属属各各类类别别样样本本个个数数分分别别为为ki,i1，c，则判别函数为：，则判别函数为：gi(x)=ki,i=1,2,c。k-近近邻邻一一般般采采用用k为为奇奇数数，跟跟投投票票表表决决一一样样，避避免免因因两两种种票数相等而难以决策。票数相等而难以决策。u决策规则决策规则33k-近邻法错误率分析u在在N的条件下，的条件下，k-近邻法的错误率要低近邻法的错误率要低于最近邻法。于最近邻法。u最近邻法和最近邻法和k-近邻法的错误率上下界都是在近邻法的错误率上下界都是在一倍到两倍贝叶斯决策方法的错误率范围内。一倍到两倍贝叶斯决策方法的错误率范围内。34近邻法应用举例3-近邻最近邻35