数据挖掘导论-第2章 基本数据挖掘技术

第2章基本数据挖掘技术1第2章基本数据挖掘技术2.1决策树2.2关联规则2.3聚类分析技术2.4数据挖掘技术的选择第2章基本数据挖掘技术2本章目标决策树–了解决策树的概念；–了解C4.5决策树建立过程、关键技术和决策树规则；–了解其他决策树算法。关联规则–了解关联规则；–掌握Apriori关联分析过程。聚类分析–掌握K-均值算法。了解数据挖掘技术的选择考虑。第2章基本数据挖掘技术32.1决策树决策树（DecisionTree）：从数据产生决策树的机器学习技术。决策树是数据挖掘中最常用的一种分类和预测技术，可建立分类和预测模型。决策树模型是一个树状结构，树中每个节点表示分析对象的某个属性，每个分支表示这个属性的某个可能的取值，每个叶节点表示经历从根节点到该叶节点这条路径上的对象的值。模型通过树中的各个分支对对象进行分类，叶节点表示的对象值表达了决策树分类的结果。第2章基本数据挖掘技术4C4.5算法决策树是一种常用的有指导学习模型，其中C4.5算法是常用算法之一。C4.5由罗斯.昆兰提出，其基本思想是：•给定一个表示为“属性-值”格式的由多个实例构成的数据集，•数据集具有多个输入属性和一个输出属性•输入属性表达了数据集中每个实例的某个方面的特征或行为•输出属性代表每个实例属于且仅属于的那个类第2章基本数据挖掘技术5罗斯.昆兰罗斯.昆兰以发明机器学习和数据挖掘程序而闻名。昆兰1965年获悉尼大学物理学硕士学位；1968年获惠灵顿大学计算机科学博士学位。1979年，澳大利亚计算机科学家昆兰提出ID3的决策树算法，ID3的增强版C4.5。C4.5在工业数据挖掘实践中应用非常广泛，被誉为机器学习和数据挖掘研究中的基准算法。第2章基本数据挖掘技术6分类模型算法使用数据集中的部分或全部实例作为训练实例建模，即分类模型。分类模型可以用于分类或预测新的未知分类的实例。在模型应用之前，往往需要进行必要的剪枝和检验。剪枝是用来限制树的规模，提高模型的分类正确率。检验是评估决策树模型质量的重要环节，也可以对模型分类未知实例的能力进行检验。第2章基本数据挖掘技术72.1.1决策树算法的一般过程C4.5算法的步骤（1）给定格式为“属性-值”的数据集T。（2）选择一个最能区别T中实例的输入属性，C4.5使用增益率来选择该属性。（3）使用该属性创建一个树节点，同时创建该节点的分支，每个分支为该节点的所有可能取值。（4）使用这些分支，将数据集中的实例进行分类，成为细分的子类。第2章基本数据挖掘技术8C4.5算法的步骤（续）（5）将当前子类的实例集合，对数据集中的剩余属性重复（2）（3）步，直到满足以下两个条件之一时，该过程终止，创建叶节点，该节点为沿此分支所表达的分类类别，其值为输出属性的值。算法终止条件：该子类中的实例满足预定义的标准，如全部分到一个输出类中，分到一个输出类中的实例达到某个比例；没有剩余属性。第2章基本数据挖掘技术9【例2.1】假设打篮球数据集T，建立决策树，用于预测某个学生是否决定去打篮球。序号WeatherTemperature/CCoursesPartnerPlay1Sunny20~304YesYes2Sunny20~304NoYes3Rain10~01YesYes4Sunny30~405YesYes5Rain20~308NoNo6Sunny-10~05YesYes7Sunny-10~07NoNo8Rain20~302YesYes9Rain20~306YesNo10Sunny10~206YesNo11Rain10~203NoNo12Rain10~201YesNo13Sunny10~208YesNo14Sunny0~103YesYes15Rain0~102YesNo第2章基本数据挖掘技术10打篮球决策树使用15个实例进行有训练，输入属性有四个：Weather、Temperature、Courses和Partner输出属性PlayWeatherYesNoSunnyRainCoursesNo≤55第2章基本数据挖掘技术112.1.2决策树算法的关键技术三项关键技术（1）选择最能区别数据集中实例属性的方法（2）剪枝方法：为控制决策树规模、优化决策树而采取的剪除部分分支的方法。（3）检验方法：评估决策树的分类正确程度的方法。分支节点的创建剪枝检验第2章基本数据挖掘技术121、选择最能区别数据集中实例属性的方法C4.5使用了信息论，即使用增益率（GainRatio）的概念来选择属性；目的是使树的层次和节点数最小，使数据的概化程度最大。C4.5选择的基本思想：选择具有最大增益率的属性作为分支节点来分类实例数据。第2章基本数据挖掘技术131）信息熵1948年，克劳德·香农提出“信息熵”的概念。在信息论中，信息熵是信息的不确定程度的度量。熵越大，信息就越不容易搞清楚，需要的信息量就越大，能传输的信息就越多。香农（1916年4月30日—2001年2月24日）是美国数学家、信息论的创始人。香农提出了信息熵的概念，为信息论和数字通信奠定了基础。第2章基本数据挖掘技术14信息熵的计算公式H(x)表示随机事件x的熵p表示xi出现的概率xi表示某个随机事件x的所有可能的结果n为实例集合被分为可能的类的个数信息熵的计算单位是比特bitniiixpxpxH12)((log)()(第2章基本数据挖掘技术15举例例1：一次投硬币实验，理想情况下正反面出现的概率分别为1/2，计算投硬币事件的熵值。例2：一个随机事件x，有三种可能的取值x1、x2和x3，出现的概率分别为1/4、1/2和1/4，计算x的熵值。第2章基本数据挖掘技术162）信息增益（InformationGain）信息增益表示当x取属性xi值时，其对降低x的熵的贡献大小。信息增益值越大，越适于对x进行分类。C4.5使用信息量和信息增益的概念计算所有属性的增益，并计算所有属性的增益率，选择值最大的属性来划分数据实例。计算属性A的增益率的公式)(SplitsInfo)Gain()GainRatio(AAA第2章基本数据挖掘技术17计算Gain（A）Info(I)为当前数据集所有实例所表达的信息量niiiI12)(log)Info(所有实例总数类中的实例个数出现在所有实例总数类中的实例个数出现在Info(I,A)为根据属性A的k个可能取值分类I中实例之后所表达的信息量（k为属性A具有k个输出结果）Gain(A)=Info(I)-Info(I,A)𝐼𝑛𝑓𝑜𝐼,𝐴=出现在𝑗类中的实例个数所有实例总数𝑘𝑗=1Info(j类)第2章基本数据挖掘技术18计算SplitsInfo（A）SplitsInfo(A)是对A属性的增益值的标准化，目的是消除属性选择上的偏差。SplitsInfo(A)=-第2章基本数据挖掘技术19举例：下表是由银行的客户基本资料和信贷资料的一部分数据组成的训练样本集，使用C4.5算法生成决策树。序号年龄age收入income婚姻状况marriage信用等级credit_rate贷款与否loan130HighNoFairNo230HighNoExcellentNo330-40HighNoFairYes440MediumNoFairYes540LowYesFairYes640LowYesExcellentNo730-40LowYesExcellentYes830MediumNoFairNo930LowYesFairYes1040MediumYesFairYes1130MediumYesExcellentYes1230-40MediumNoExcellentYes1330-40HighYesFairYes1440MediumNoExcellentNo第2章基本数据挖掘技术20根据属性“年龄”对样本集进行划分的信息增益为：GainRatio(age)=0.246/1.577=0.156GainRatio(income)=0.029/1.557=0.018GainRatio(marriage)=0.151/1=0.151GainRatio(credit_rate)=0.048/0.985=0.049第2章基本数据挖掘技术21ageincomemarriagecredit_rateclassHighNoFairNoHighNoExcellentNoMediumNoFairNoLowYesFairYesMediumYesExcellentYesincomemarriagecredit_rateclassHighNoFairYesLowYesExcellentYesMediumNoExcellentYesHighYesFairYesincomemarriagecredit_rateclassMediumNoFairYesMediumYesFairYesLowYesExcellentNoLowYesFairYesMediumNoExcellentNo403030-40第2章基本数据挖掘技术22选出age30的分支节点剩余输入属性：income，marriage，credit_rateGrainRatio(income)=(0.971-1)/1.522=-0.019GrainRatio(marriage)=(0.971-0)/0.971=1GrainRatio(credit_rate)=(0.971-0.95)/0.971=0.022选择信息增益最大的属性marriage已婚的实例中2个全部是Yes类未婚的实例中3个全部是No类都分到一个输出类中，该分支终止。第2章基本数据挖掘技术23选出age40的分支节点剩余输入属性：income，credit_rateGrainRatio(income)=(0.971-0.95)/0.971=0.022GraniRatio(credit_rate)=(0.971-0)/0.971=1选择信息增益最大的属性credit_rateFair的实例中3个全部是Yes类Excellent的实例中2个全部是No类都分到一个输出类中，所以算法结束。第2章基本数据挖掘技术24agemarriageYesYesYesCredit_rateNoNo403030-40YesNoFairExcellent使用信息增益分裂属性图第2章基本数据挖掘技术25计算例2.1的增益率序号WeatherTemperature/CCoursesPartnerPlay1Sunny20~304YesYes2Sunny20~304NoYes3Rain-10~01YesYes4Sunny30~405YesYes5Rain20~308NoNo6Sunny-10~05YesYes7Sunny-10~07NoNo8Rain20~302YesYes9Rain20~306YesNo10Sunny10~206YesNo11Rain10~203NoNo12Rain10~201YesNo13Sunny10~208YesNo14Sunny0~103YesYes15Rain0~102YesNo第2章基本数据挖掘技术26计算GainRatio(Weather)（1）Info(I)=(7/15log2(7/15)-8/15log2(8/15))=0.9968（2）Info(I,Weather)=0.9118（3）SplitsInfo(Weather)=0.9968（4）Gain(Weather)=Info(I)Info(I,Weather)=0.99680.9118=-0.085（5）GainRatio(Weather)=-0.085/0.9968=-0.085第2章基本数据挖掘技术27计算GainRatio(Temperature)（1）Info(I)=0.9968（2）Info(I,Temperature)=0.6406（3）SplitsInfo(Temperature)=2.1493（4）Gain(Temperature)=0.3561（5）GainRat