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

《数据挖掘导论-第2章 基本数据挖掘技术.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、第2章基本数据挖掘技术2.1决策树2.2关联规则2.3聚类分析技术2.4数据挖掘技术的选择本章目标决策树了解决策树的概念；了解C4.5决策树建立过程、关键技术和决策树规则；了解其他决策树算法。关联规则了解关联规则；掌握Apriori关联分析过程。聚类分析掌握K-均值算法。了解数据挖掘技术的选择考虑。2.1决策树决策树（DecisionTree）：从数据产生决策树的机器学习技术。决策树是数据挖掘中最常用的一种分类和预测技术，可建立分类和预测模型。决策树模型是一个树状结构，树中每个节点表示分析对象的某个属性，每个分支表示这个属性的某个可能的取值，每个叶节点

2、表示经历从根节点到该叶节点这条路径上的对象的值。模型通过树中的各个分支对对象进行分类，叶节点表示的对象值表达了决策树分类的结果。C4.5算法决策树是一种常用的有指导学习模型，其中C4.5算法是常用算法之一。C4.5由罗斯.昆兰提出，其基本思想是：给定一个表示为“属性-值”格式的由多个实例构成的数据集，数据集具有多个输入属性和一个输出属性输入属性表达了数据集中每个实例的某个方面的特征或行为输出属性代表每个实例属于且仅属于的那个类罗斯.昆兰罗斯.昆兰以发明机器学习和数据挖掘程序而闻名。昆兰1965年获悉尼大学物理学硕士学位；1968年获惠灵顿大学计算机科学

3、博士学位。1979年，澳大利亚计算机科学家昆兰提出ID3的决策树算法，ID3的增强版C4.5。C4.5在工业数据挖掘实践中应用非常广泛，被誉为机器学习和数据挖掘研究中的基准算法。分类模型算法使用数据集中的部分或全部实例作为训练实例建模，即分类模型。分类模型可以用于分类或预测新的未知分类的实例。在模型应用之前，往往需要进行必要的剪枝和检验。剪枝是用来限制树的规模，提高模型的分类正确率。检验是评估决策树模型质量的重要环节，也可以对模型分类未知实例的能力进行检验。2.1.1决策树算法的一般过程C4.5算法的步骤（1）给定格式为“属性-值”的数据集T。（2）选

4、择一个最能区别T中实例的输入属性，C4.5使用增益率来选择该属性。（3）使用该属性创建一个树节点，同时创建该节点的分支，每个分支为该节点的所有可能取值。（4）使用这些分支，将数据集中的实例进行分类，成为细分的子类。C4.5算法的步骤（续）（5）将当前子类的实例集合，对数据集中的剩余属性重复（2）（3）步，直到满足以下两个条件之一时，该过程终止，创建叶节点，该节点为沿此分支所表达的分类类别，其值为输出属性的值。算法终止条件：该子类中的实例满足预定义的标准，如全部分到一个输出类中，分到一个输出类中的实例达到某个比例；没有剩余属性。【例2.1】假设打篮球数据

5、集T，建立决策树，用于预测某个学生是否决定去打篮球。序号WeatherTemperature/CCoursesPartnerPlay1Sunny20~304YesYes2Sunny20~304NoYes3Rain10~01YesYes4Sunny30~405YesYes5Rain20~308NoNo6Sunny-10~05YesYes7Sunny-10~07NoNo8Rain20~302YesYes9Rain20~306YesNo10Sunny10~206YesNo11Rain10~203NoNo12Rain10~201YesNo13Sunny10~

6、208YesNo14Sunny0~103YesYes15Rain0~102YesNo打篮球决策树使用15个实例进行有训练，输入属性有四个：Weather、Temperature、Courses和Partner输出属性Play2.1.2决策树算法的关键技术三项关键技术（1）选择最能区别数据集中实例属性的方法（2）剪枝方法：为控制决策树规模、优化决策树而采取的剪除部分分支的方法。（3）检验方法：评估决策树的分类正确程度的方法。分支节点的创建剪枝检验1、选择最能区别数据集中实例属性的方法C4.5使用了信息论，即使用增益率（GainRatio）的概念来选择属性

7、；目的是使树的层次和节点数最小，使数据的概化程度最大。C4.5选择的基本思想：选择具有最大增益率的属性作为分支节点来分类实例数据。1）信息熵1948年，克劳德·香农提出“信息熵”的概念。在信息论中，信息熵是信息的不确定程度的度量。熵越大，信息就越不容易搞清楚，需要的信息量就越大，能传输的信息就越多。香农（1916年4月30日—2001年2月24日）是美国数学家、信息论的创始人。香农提出了信息熵的概念，为信息论和数字通信奠定了基础。信息熵的计算公式H(x)表示随机事件x的熵p表示xi出现的概率xi表示某个随机事件x的所有可能的结果n为实例集合被分为可能的

8、类的个数信息熵的计算单位是比特bit举例例1：一次投硬币实验，理想情况下正反面出现的概率分别为