数学建模的数据挖掘方法幻灯片.ppt

《数学建模的数据挖掘方法幻灯片.ppt》由会员分享，可在线阅读，更多相关《数学建模的数据挖掘方法幻灯片.ppt（65页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数学建模的数据挖掘方法第1页，共65页，编辑于2022年，星期六分类（Classification)就是通过学习得到一个目标函数（称为模型函数）f，然后把新的对象x通过f映射到一个预先定义的类别号y。1.分类的定义：一、相关概念第2页，共65页，编辑于2022年，星期六2.数据挖掘中分类任务的一般模型数据集构造模型函数f模型是否合理不合理新对象合理模型确定输出类别训练样本集检验样本集输入模型检验第3页，共65页，编辑于2022年，星期六2.分类性能的度量考虑二分类问题即类标号只有2个，可设为1和0.定义：f11：实际为第一类，按模型也判别为第一类；f00：实际为第二类，按模型也判别为第二类；f

2、10：实际为第一类，按模型也判别为第二类；f01：实际为第二类，按模型也判别为第一类；则分类性能可以用准确率或错误率来度量准确率=（f11+f00)/(f11+f00+f10+f01)准确率=1-准确率第4页，共65页，编辑于2022年，星期六3.常见的分类方法常见的分类有：决策树、神经网络、支持向量机、遗传算法、粗糙集、贝叶斯等。三、基于决策树的分类方法例1.下表是用于构造分类模型的数据集，包括14个样本和5个属性:Outlook、Temperature、Humidity、Windy和Play，其中前4个属性是天气，最后一个属性是根据前4个属性的情况说明这样的天气状况是否适合比赛。各属性取值

3、如下：Outlook：sunny(s),overcast(o),rain(r);Temperature:hot(h),mild(m),cool(c);Humidity:high(h),normal(n);Windy:false,truePlay:Yes(y),no(n)第5页，共65页，编辑于2022年，星期六训练样本集如下OutlookTempHumiWindy PlaySHHFNSHHTNOHHFYRMHFYRCNFYRCNTNOCNTYSMHFNSCNFYRMNFYOMNTYOMHTYOHNFYRMHTN第6页，共65页，编辑于2022年，星期六决策树是类似如下的一棵树Outlooksu

4、nnyrainovercastPlay=noPlay=yeswindyfalsePlay=yesTruePlay=no给定一个新的天气象:“rain,hot,high,true”，则判别其类别第7页，共65页，编辑于2022年，星期六决策树的构造：分裂属性的选择四、基于信息增益的特征选择策略1.相关概念设信息源X的取值为A=(a1,a2,an)，ai出现的概率为pi，称I(ai)=log(1/pi)=-logpi为ai的信息量；称为X的信息熵。第8页，共65页，编辑于2022年，星期六决策树分类方法利用信息量增加（信息增益）作为特征选择的一种指标。信息增益衡量每个属性对分裂后的数据子集的信息量

5、的贡献。假设训练集T包含n个样本，这些样本分别属于m个类，其中第i个类在T中出现的比例为pi，称为集合T的信息熵。如果m=1，即T的样本都属于一个类，则I（T）=0，达到最小值，何时（）达到最大？第9页，共65页，编辑于2022年，星期六假设属性把集合划分为个子集T1,T2,.,Tv,其中Ti所包含的样本数为ni，那么划分后的熵就是：分裂后的信息增益定义为基于信息理论的特征选择方法就是逐一计算每种分裂的信息增益，选择信息增益最大的属性作为分裂属性。下面以前面给出的数据集为例，利用信息增益方法构造决策树。第10页，共65页，编辑于2022年，星期六第一步：计算训练样本集的信息量。分类属性Play

6、有两个类，其样本数统计如下：因此T的信息量为：第二步：计算每个属性的信息增益，对于Outlook属性，它有3个属性值，把样本集T分成3个子集，每个子集的类别统计如下：样本集TPlay=yesPlay=no样本数95第11页，共65页，编辑于2022年，星期六Outlook的信息熵为：OutlookPlay=yesPlay=nototalSunny(T1)134Overcast(T2)505Rain(T3)32514第12页，共65页，编辑于2022年，星期六Outlook的信息增益为：同理对于Temperature属性，它也有3个属性值，把样本集T分成3个子集，每个子集的类别统计如下：Temp

7、eraturePlay=yesPlay=nototalhot(T1)224mild(T2)426cool(T3)31414第13页，共65页，编辑于2022年，星期六Temperature的信息熵为：Temperature的信息增益为：第14页，共65页，编辑于2022年，星期六对于Humidity属性和Windy属性，统计如下：HumidityPlay=yesPlay=nototalNormal(T1)347high(T2)61714WindyPlay=yesPlay=nototalTrue(T1)336False(T2)62814计算其信息增益值分别为0.1653和0.0481.第15页，

8、共65页，编辑于2022年，星期六第三步：比较四个属性的信息增益，按大小顺序排列为Gain(Outlook)Gain(Humidity)Gain(Windy)Gain(Temperature)因此应该选Outlook作为首分裂结点，即决策树的形状为：OutlookSunnyRainOvercast第16页，共65页，编辑于2022年，星期六第二层结点的选择与首结点类似，具体选择过程如下：对于“Sunny”的分支，从原数据集T中统计出Outlook属性值为sunny的样本作为新的数据集T。OutlookTempHumiWindy PlaySHHFNSHHTNSMHFNSCNFY作为新样本集第17

9、页，共65页，编辑于2022年，星期六计算T的信息量为：对于Temperature属性，简单统计如下：TemperaturePlay=yesPlay=nototalhot(T1)022mild(T2)011cool(T3)101显然第18页，共65页，编辑于2022年，星期六对于Humidity属性，简单统计如下：显然HumidityPlay=yesPlay=nototalNormal(T1)101high(T2)033WindyPlay=yesPlay=nototalF(T1)123T(T2)011第19页，共65页，编辑于2022年，星期六因此Sunny分支下的分裂属性可选Temperat

10、ure或Humidity，若取Humidity，则其属性H和N下的记录都为相同的类，该分支算法结束。OutlookTempHumiWindy PlaySHHFNSHHTNSMHFNSCNFY其分支结构如下：HumiditySunnyHighNormalPlay=NoPlay=Yes第20页，共65页，编辑于2022年，星期六若取Temperature，则重新确定记录集如下：OutlookTempHumiWindy PlaySHHFNSHHTNSMHFNSCNFYTempSunnyHighMPlay=NoPlay=No可以看出其三个分支H，C和M下的所有记录也属于相同的类，此分支算法结束。其分支

11、结构如右：CPlay=Yes第21页，共65页，编辑于2022年，星期六同理，对于Rain分支，统计数据如下：WindyRainFalseTruePlay=YesPlay=NoOutlook=RTempHumiWindyPlayMHFYCNFYCNTNMNFYMHTN因此选Windy其分支结构如右：第22页，共65页，编辑于2022年，星期六同理，对于Overcast分支，统计数据如下：Play=Yes该分支下所有记录均为同一类，因此该分支算法结束，其结构如下右。Outlook=Overcast TempHumiWindy PlayHHFYCNTYMNTYMHTYHNFYOvercast第23

12、页，共65页，编辑于2022年，星期六综合以上结果，最后得到决策树如下：OutlookTempSunnyHighMPlay=NoPlay=NoCPlay=YesWindyFalsePlay=YesPlay=NoTrueRainPlay=YesOvercast第24页，共65页，编辑于2022年，星期六决策树构造好后，给出新的对象便可判别其类别，例如，新的天气对象为：1)“Overcast,cool,high,False”2)“Rain,Mild,Normal,True”，其类别分别为：第25页，共65页，编辑于2022年，星期六五、基于数据分布的特征选择策略除了基于信息增益的特征选择策略外，还

13、可以根据结点的数据类别的分布来选择最优分裂结点，称之为Gini Index方法。定义：假设训练集T包含n个样本，这些样本分别属于m个类，其中第i个类在T中出现的比例为pi，则T的Gini Index定义为：假设属性把集合划分为个子集T1,T2,.,Tv,其中Ti所包含的样本数为ni，那么这个划分的Gini Index为：第26页，共65页，编辑于2022年，星期六Gini Index的特征选择方法就是逐一计算按每个属性分裂后的Gini Index值，选择gini Index值最小的属性作为分裂属性。下面以前面给出的数据集为例，利用Gini Index选择策略构造决策树的过程。对总样本进行统计如

14、下：样本集TPlay=yesPlay=no样本数95样本集T的gini Index值为第27页，共65页，编辑于2022年，星期六对于Outlook属性，它有3个属性值，把样本集T分成3个子集，每个子集的类别统计如下：OutlookPlay=yesPlay=nototalSunny(T1)134Overcast(T2)505Rain(T3)325每个子集的Gini Index值如下：因此属性Outlook的Gini Index值为：第28页，共65页，编辑于2022年，星期六同理对于Temperature属性，它也有3个属性值，把样本集T分成3个子集，每个子集的类别统计如下：Temperatu

15、rePlay=yesPlay=nototalhot(T1)224mild(T2)426cool(T3)314因此属性Temperature的Gini Index值为：第29页，共65页，编辑于2022年，星期六对于Humidity属性和Windy属性，统计如下：HumidityPlay=yesPlay=nototalNormal(T1)347high(T2)61714WindyPlay=yesPlay=nototalTrue(T1)336False(T2)62814计算其Gini Index值分别为0.3674和0.4357.第30页，共65页，编辑于2022年，星期六第三步：比较四个属性的G

16、ini Index值如下：因此应该选Outlook作为首分裂结点，即决策树的形状为：OutlookSunnyRainOvercast属性OutLTempHumiWindyGini Index值 0.27850.3750.3674 0.4357第31页，共65页，编辑于2022年，星期六第二层结点的选择与首结点类似，具体选择过程如下：对于“Sunny”的分支，从原数据集T中统计出Outlook属性值为sunny的样本作为新的数据集T。Outlook=STempHumi Windy PlayTHHFNHHTNMHFNCNFY第32页，共65页，编辑于2022年，星期六对于Temperature属性

17、，简单统计如下：TemperaturePlay=yesPlay=nototalhot(T1)022mild(T2)011cool(T3)101第33页，共65页，编辑于2022年，星期六对于Humidity属性，简单统计如下：显然HumidityPlay=yesPlay=nototalNormal(T1)101high(T2)033WindyPlay=yesPlay=nototalF(T1)123T(T2)011第34页，共65页，编辑于2022年，星期六因此Sunny分支下的分裂属性可选Temperature或Humidity，若取Humidity，则其属性H和N下的记录都为相同的类，该分支

18、算法结束。OutlookTempHumiWindy PlaySHHFNSHHTNSMHFNSCNFY其分支结构如下：HumiditySunnyHighNormalPlay=NoPlay=Yes第35页，共65页，编辑于2022年，星期六剩下的计算类似，最后得到决策树如下：OutlookTempSunnyHighMPlay=NoPlay=NoCPlay=YesWindyFalsePlay=YesPlay=NoTrueRainPlay=YesOvercast第36页，共65页，编辑于2022年，星期六六、信息增益和Gini Index值的另一个应用考虑如下问题：预测贷款申请者是否会按时归还贷款，历

19、史数据如下：顾客Id有房婚姻状况年收入拖欠贷款1是单身125K否2否已婚100K否3否单身70K否4是已婚120K否5否离异95K是6否已婚60K否7是离异220K否8否单身85K是9否已婚75K否10否单身90K是第37页，共65页，编辑于2022年，星期六对于“年收入”属性，它是连续型变量，按前面决策树的构造方法，应该每个属性都是离散型属性。为此，应该把连续型属性划分成若干个区间，这样把该属性化为离散型属性。简单的，若划分为两个区间，如何划分？可以用信息增益或Gini Index值方法。步骤如下：把连续型属性值由小到大排列，取每两个值的中间值作为候选划分点：类NNNYYYNNNN值6070

20、75 859095100120125220候选划分点65 72 8087 9297110 122 172第38页，共65页，编辑于2022年，星期六然后计算按各个候选划分点划分的信息增益或GiniIndex值，例如，用Gini Index值方法如下：类NNNYYYNNNN值607075 859095100120125220候选划分点65 72 8087 9297110 122 172对于候选点65，划分后类别统计如下类=N类=Y=65(T2)63第39页，共65页，编辑于2022年，星期六类NNNYYYNNNN值607075 859095100120125220候选划分点65 72 8087

21、9297110 122 172对于候选点72，划分后类别统计如下类=N类=Y=70(T2)53第40页，共65页，编辑于2022年，星期六类NNNYYYNNNN值607075 859095100120125220候选划分点65 72 8087 9297110 122 172对于候选点80，对于候选点87，对于候选点92，对于候选点97，对于候选点110，对于候选点122，对于候选点172，最佳候选点第41页，共65页，编辑于2022年，星期六根据上面的分析，可把“年收入”属性划分成两个区间（0,97）和97,10000)分别设为属性A1和A2，则原数据集变为：顾客Id有房婚姻状况年收入拖欠贷款

22、1是单身125K（A2）否2否已婚100K（A2）否3否单身70K（A1）否4是已婚120K（A2）否5否离异95K（A1）是6否已婚60K（A1）否7是离异220K（A2）否8否单身85K（A1）是9否已婚75K（A1）否10否单身90K（A1）是第42页，共65页，编辑于2022年，星期六再按前面的方法构造决策树，便可对类似的顾客：“否，单身，100K”进行分类判别。第43页，共65页，编辑于2022年，星期六七、朴素贝叶斯分类法1.朴素贝叶斯分类方法描述 设样本集T有n个属性：A1，A2，An，可能的类别有m个：C1，C2，Cm，待分类的样本为x=X1,X2，Xn，分别计算条件概率：则条

23、件概率P(Ci|X）最大所对应的类Ci即为X所在的类。在公式（1）中，计算等式左边的每个条件概率时，右边的分母相同，因此只需要计算分子，然后比较大小即可。第44页，共65页，编辑于2022年，星期六各概率的计算如下：另外，用朴素贝叶斯分类时还需假设各属性之间相互独立，此时有：2.条件概率 P(xj|Ci）的估计第45页，共65页，编辑于2022年，星期六条件概率 P(xj|Ci）的估计值分两种情况情形1.第j个属性Aj为离散型 的情况此时，条件概率 P(xj|Ci）可按如下公式计算：第46页，共65页，编辑于2022年，星期六例1：给定训练样本集如下，请用贝叶斯方法判别对象：“rain，hot

24、，high，true”的类别。OutlookTempHumiWindy PlaySHHFNSHHTNOHHFYRMHFYRCNFYRCNTNOCNTYSMHFNSCNFYRMNFYOMNTYOMHTYOHNFYRMHTN第47页，共65页，编辑于2022年，星期六解：分类属性Play有两个类，Play=yes（C1）和其Play=no（C2），样本数统计如下：于是P（C1）=9/14，P（C2）=5/14对于Outlook属性，数据汇总如下表：样本集TPlay=yes（C1）Play=no（C2）样本数95第48页，共65页，编辑于2022年，星期六于是各条件概率为：OutlookC1（Y）C

25、2（N）Sunny13Overcast50Rain32Total95，第49页，共65页，编辑于2022年，星期六同理对于Temperature属性，它也有3个属性值，把样本集T分成3个子集，每个子集的类别统计如下：TemperaturePlay=yesPlay=nohot22mild42cool31total95于是各条件概率为：，第50页，共65页，编辑于2022年，星期六对于Humidity属性和Windy属性，统计如下：HumidityPlay=yesPlay=noNormal34high61total95WindyPlay=yesPlay=noTrue33False62total95

26、试计算其“条件概率”。第51页，共65页，编辑于2022年，星期六对于待分类样本:分别计算以下两个概率：=0.333*0.22*0.33*0.3*0.643=0.0053=0.4*0.4*0.8*0.6*0.357=0.0274，因此 为第二类，即不适合比赛。第52页，共65页，编辑于2022年，星期六情形2.第j个属性Aj为连续型 的情况tid有房婚姻状况年收入拖欠贷款1是单身125否2否已婚100否3否但是70否4是已婚120否5否离婚95是6否已婚60否7是离婚220否8否单身85是9否已婚75否10否单身90是考虑如下的训练样本集，如何判别样本的类别？第53页，共65页，编辑于2022

27、年，星期六属性“年收入”为连续型数据类型，此时如果再用公式 来估计条件概率已不合适，例如，若新样本的“年收入”为110K，则类似的新样本将无法判别。有两种策略可以用了估计连续型属性的条件概率：1.把连续属性离散化；2.用概率分布来估计条件概率第54页，共65页，编辑于2022年，星期六1.把连续属性离散化如前面构造决策树的Gini Index或信息增益方法，把连续属性划分成几个区间，即连续属性离散化。按前面所述，如果把“年收入”划分成两个区间，则最佳的候选划分点为97K，对应区间为（0,97）和97,10000）。通过计算类 Ci中属性“年收入”落入对应区间的比例来估计条件概率 即把训练数据集

28、修改为下表第55页，共65页，编辑于2022年，星期六 tid 有房 婚姻状况 年收入97K拖欠贷款1是单身否否2否已婚否否3否但是是否4是已婚否否5否离婚是是6否已婚是否7是离婚否否8否单身是是9否已婚是否10否单身是是用Bayes方法估计每个条件概率后，对新给出的任何样本都可以判别。第56页，共65页，编辑于2022年，星期六2.用概率分布来估计条件概率假设连续型属性服从某种概率分布（通常假设服从正态分布），然后用训练数据估计出分布的参数，进而计算相应的条件概率。如上例中，假设“年收入”属性为随机变量 对于每个类 Ci，属性值xj属于类Ci的概率为 和分别为类Ci 中随机变量xj的期望和方

29、差可分别用 Ci中xj的观察值的样本均值和标准差估计。第57页，共65页，编辑于2022年，星期六如上表数据中“年收入”数据，分别属于两类，设类别C1=“否”，C2=“是”，对应的观察值如下：类别 C1=“否”的两个参数估计如下：年收入125100701209560220857590拖欠贷款否否否否是否否是否是类别 C1=“否”的两个参数估计为：第58页，共65页，编辑于2022年，星期六 同理，类别 C2=“是”的两个参数估计为：对于新样本 可以估计“年收入”属性相应的条件概率为：第59页，共65页，编辑于2022年，星期六 下面用上述方法来判别新样本 数据汇总如下：样本集所属的类别。类别C

30、1（No）C2（Yes）total73属性“有房”C1（No）C2（Yes）是30否43Total73第60页，共65页，编辑于2022年，星期六 属性“婚姻状况”C1（No）C2（Yes）离异11单身22已婚40Total73对于属性“年输入”，已估计相应的条件概率为：第61页，共65页，编辑于2022年，星期六 由以上概率计算样本 相应的条件概率为：因此新样本属于第二类，即“是”拖欠贷款。问题1：有一个属性的类条件概率为0，则整个类的后验概率就等于0，如果样本 的类条件概率X应该如何判别？第62页，共65页，编辑于2022年，星期六 问题2：对于连续型属性Xj，估计条件概率时把它视为连续型

31、随机变量，估计的条件概率为那么，这样估计是否合理？内的类条件概率为问题2的解释：但我们知道，对于连续型随机变量，有假设Xj落在区间对于连续型属性Xj的每个取值xj，都使用同一个小正数在比较时，果，因此公式（5）仍可以用了估计相应的条件概率。成为一个常数乘法因此，不影响比较结第63页，共65页，编辑于2022年，星期六 对于问题1，通常使用m值法来估计条件概率以解决这种情况。m值估计法：条件概率的估计值用下式进行估计其中，n为训练样本中类Ci的总实例数，nc为Ci类中取值为xj的实例数，m和p是用户事先给定的参数。一般m为正整数，p是位于0与1之间的小数。例.设m=10，p=1/4，试对前面所给的数据重新估计离散型属性的各条件概率。第64页，共65页，编辑于2022年，星期六 tid 有房 婚姻状况 年收入97K拖欠贷款1是单身否否2否已婚否否3否但是是否4是已婚否否5否离婚是是6否已婚是否7是离婚否否8否单身是是9否已婚是否10否单身是是第65页，共65页，编辑于2022年，星期六