数据挖掘技术概述讲义PPT(共182页)

1数据挖掘技术赵卫东博士复旦大学软件学院[e-mail]2分类和预测3分类对离散数据的分类称为分类，对数值数据的分类称为预测。分类要解决的问题是为一个事件或对象归类，即确定一个特定的对象属于哪一类。分类函数或分类模型(分类器)分类模型是通过那些已知历史数据训练出来的。这里用于建立模型的数据称为训练集，通常是已经掌握的历史数据。在训练集中每个对象都赋予一个类别的标记，不同的类别具有不同的标记。分类就是通过分析训练集中的数据，为每个类别做出准确的描述或建立分析模型或挖掘出分类规则，然后用这个分类规则对其它数据对象进行分类。4分类规则实例低风险收入￥40,000工作时间5年高负债高风险高风险低风险否否否是是是If收入￥40,000而且工作时间5年then低风险5分类数据ThedatausedtobuildaclassificationmodelconsistsofAsetofrecords.Eachrecordhasthesamenumberoffields.Onefieldintheserecordcontainsindicatorsofclasseswhichrecordsbelongto.Thisfieldiscalledtargetfield.Otherfieldsarecalledindependentfieldswhichdescribetheindividualobjectsrepresentedbytherecords.6决策表实例AgeSexBPCholesterolNaKDrug25FHIGHHIGH0.6759960.074834drugA17FHIGHHIGH0.5397560.030081drugY23MLOWNORMAL0.5564530.03618drugY24MNORMALNORMAL0.8452360.055498drugY74FLOWHIGH0.8496240.076902drugC40FNORMALHIGH0.676830.049634drugX32FHIGHHIGH0.5816640.024803drugY70MLOWHIGH0.7163590.036936drugY64MHIGHNORMAL0.6407890.078302drugB45MHIGHHIGH0.6641050.047819drugA33FLOWNORMAL0.8218050.027674drugY74FLOWNORMAL0.7722250.04794drugY73MHIGHNORMAL0.7921310.062171drugB38FLOWHIGH0.7943180.051825drugY72FHIGHNORMAL0.5335580.021289drugY27FHIGHNORMAL0.5550640.04665drugA62MHIGHNORMAL0.510150.071463drugB72MHIGHNORMAL0.8194830.073802drugB19MHIGHNORMAL0.5527010.032598drugY28MHIGHHIGH0.5840390.068375drugA54MNORMALNORMAL0.6056290.076527drugX7决策树arewidelyusedindatamining.weredevelopedinmachinelearningandstatistics.areusedtobuildclassificationandpredictionmodels.arewidelyavailable.判定树分类算法output训练集决策树input新数据分类8使用决策树进行分类决策树一个树形的结构内部节点上选用一个属性进行分割每个分叉都是分割的一个部分叶子节点表示一个分类决策树生成算法分成两个步骤树的生成开始，数据都在根节点递归的进行数据分片树的修剪：去掉一些可能是噪音或者异常的数据决策树使用:对未知数据进行分割按照决策树上采用的分割属性逐层往下，直到叶子节点9决策树算法基本算法（贪心算法）自上而下分而治之的方法开始时所有的实例都在根节点属性都是分类型(如果是连续的，将其离散化)所有记录用所选属性递归的进行分割属性的选择是基于一个启发式规则或者一个统计的度量(如信息增益)停止分割的条件一个节点上的实例都属于同一个类别；没有属性可以再用于对数据进行分割10属性选择的统计度量信息增益—Informationgain(ID3/C4.5)所有属性假设都是分类型字段经过修改之后可以适用于数值型字段基尼指数—Giniindex(IBMIntelligentMiner)能够适用于分类和数值字段其他11信息增益度度量(ID3/C4.5)任意样本分类的期望信息：I(s1,s2,……,sm)=－∑Pilog2(pi)(i=1..m)其中，数据集为S，m为S的分类数目，PiCi为某分类标号，Pi为任意样本属于Ci的概率，si为分类Ci上的样本数由A划分为子集的熵：E(A)=∑j(|s1j|+……+|smj|)/|s|*I(s1j，……，smj)A为属性，具有V个不同的取值信息增益：Gain(A)=I(s1,s2,……,sm)－E(A)||||SSi12训练集ageincomestudentcredit_ratingbuys_computer=30highnofairno=30highnoexcellentno30…40highnofairyes40mediumnofairyes40lowyesfairyes40lowyesexcellentno31…40lowyesexcellentyes=30mediumnofairno=30lowyesfairyes40mediumyesfairyes=30mediumyesexcellentyes31…40mediumnoexcellentyes31…40highyesfairyes40mediumnoexcellentno13使用信息增益进行属性选择ClassP:buys_computer=“yes”ClassN:buys_computer=“no”I(p,n)=I(9,5)=0.940Computetheentropyforage:HenceSimilarlyagepiniI(pi,ni)=30230.97130…4040040320.971971.0)2,3(145)0,4(144)3,2(145)(IIIageE048.0)_(151.0)(029.0)(ratingcreditGainstudentGainincomeGain)(),()(ageEnpIageGain0.69414分枝15决策树age?overcaststudent?creditrating?noyesfairexcellent=3040nonoyesyesyes30..4016决策树在犯罪分析中的应用有无固定职业家庭经济状况年龄文化程度有无特长社会关系犯罪记录违法记录家庭和睦状况犯罪记录次数是否经常赌博犯罪程度无差30-40初中否有差有4是严重有中20-30中专否无差无0是较轻有差20高中否无中无1否较轻无差30-40初中有无中有1是严重无差40初中有有差无2是严重有差20-30高中有有中有6是严重有差20-30中专否无中有1否较轻有差30-40大专有有差无3是严重无中20初中有无好有5是严重无差20-30初中否有差无0否严重有好20高中否无差有1否较轻无差30-40初中有无中有0是严重无中30-40初中否无差有1是较轻有差40小学否有中无2否严重无差40初中否无差无0否严重无差30-40高中否无好无4否较轻无好20-30中专有无差有2否较轻17犯罪潜在风险决策树1819典型的银行卡顾客分类树20基尼指数（GiniIndex）集合T包含n个类别的记录，那么其Gini指数就是pj类别j出现的频率如果集合T分成两部分N1andN2。那么这个分割的Gini就是提供最小Ginisplit就被选择作为分割的标准.njpjTgini121)()()()(2211TginiNNTginiNNTginisplit21过拟合问题训练数据测试数据此处剪枝决策树深度剪枝避免过拟合决策树泛化22PruningTree目的：消除决策树的过拟合(OverFitting)问题实质：消除训练集中的异常和噪声两种方法：先剪枝法(Public算法)后剪枝法(Sprint算法)23误分类率C1C2C3C10r12r13C2r210r23C3r31r320实际类别分类类别Cost(orloss)matrix24决策树算法的可伸缩性ID3、C4.5等算法对规模较小，可以一次放入内存的训练样本集很有效，但实际上数以百万计样本的超大型训练集是常见的，大多数情况下无法把训练样本集全部放入内存，导致这些算法的有效性降低。因此需要增加可伸缩的方法以节省空间。IBM的研究人员运用一些特殊数据结构，例如属性表和类表，在1996年提出了一种快速的、可伸缩的SLIQ算法，可以处理离散属性和连续属性。SLIQ算法首先把训练样本集划分成若干子集，使每一个子样本集都能放入内存，然后对每个子样本集分别构造一棵决策树，再把这些决策树综合，得到最终决策树。SLIQ算法可以处理大规模的训练样本集，具有较好的伸缩性。与传统决策树算法相比，减少了运行时间。SLIQ算法在执行过程中需要随时修改类表，类表常驻内存，而类表的大小会随着训练样本集的增大而增大，因此SLIQ算法对内存容量有一定的要求。25常用的决策树算法ID3,C4.5,C5.0CARTCHAID26CART算法CART算法采用一种二分递归分割的方法，每次都把当前样本集分割为两个子样本集，使生成的决策树的非叶结点都有两个分枝，因此CART算法生成的决策树是结构简单的二叉树。这种算法选择分枝属性A的判别函数如下：式中pL和pR分别是属性A的左右分枝的样本数占总体的比例，p(iL)和p(iR)分别表示属性A的左右分枝中样本子集属于类别i的比例，m为分类类别数。使Ф（A）最大的属性A作为分枝的属性，因为这需要满足下面的条件：左右分枝样本的数量差不多。左右分枝的样本集尽量不要属于同一类。此外，CART算法也使用后剪枝。在决策树生成过程中，考虑到多展开一层就会有更多信息被发现，CART算法运行到不能再长出分枝为止，从而得到一棵最大的决策树。然后CART对生成的决策树进行剪枝。剪枝算法使用独立于训练样本集的测试样本集对子树的分类错误进行计算，找出分类错误最小的子树作为最终的分类模型。1()2|()()|mLRLRiApppipi27评估分类算法的准确性K次交叉校验（k-foldcrossvalidation:把数据集分为k子集，用k-1个子集为训练集，1个子集作为测试集，然后k次交叉验证。如何提高分类算法的准确率？28Bagging基本思想是用一个不稳定（数据集小的变化可能使分类结果有显著的变化）、弱学习算法（准确率不高），对一个训练集用该算法使用多次，得到多个分类模型。对于新样本的分类，可以用这些分类模型进行投票（得票最多的类别作为结果），结果会提高决策树的分类准确率。29Boosting基本思想是每个样本都赋予权重，每次迭代对分类错误的样本增加权重，以便下次的样本关注这些样本。这种方法也能提高不稳定分类算法的准确率。Boosting和Bagging的区别是Bagging的训练集是随机选择，相互独立的，分类模型可以并行生成；而Boosting的训练集不是独立的，与前一轮的学习有关，分类模型只能顺序生成。30神经网络31神经网络的组成神经网络是由许多人工神经元通过一定的互联方式组成。这些神经元的结构比较简单，但它们复杂的连接（拓扑结构）会形成功能很强的网