最新数据挖掘的常用算法教学讲义ppt课件.ppt

《最新数据挖掘的常用算法教学讲义ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据挖掘的常用算法目录1.概念和术语2.决策树归纳算法3.Apriori算法4.聚类算法5.其他一些算法CompanyLogo1概念和术语数据挖掘和知识发现数据挖掘是从存放在数据集中的大量数据挖掘出有趣知识的过程。数据挖掘，又称为数据库中知识发现（KnowledgeDiscoveryinDatabases）或知识发现，它是一个从大量数据中抽取挖掘出未知的、有价值的模式或规律等知识的非平凡过程，它与数据仓库有着密切的联系。广义的数据挖掘是指知识发现的全过程；狭义的数据挖掘是指统计分析、机器学习等发

2、现数据模式的智能方法，即偏重于模型和算法。数据库查询系统和专家系统不是数据挖掘！在小规模数据上的统计分析和机器学习过程也不应算作数据挖掘。CompanyLogo1概念和术语按训练方式，机器学习可分为：（1）有监督的学习；有训练样本，学习机通过学习获有监督的学习；并用其作为判断测试样本的类别的依据。、（2）无监督的学习：无训练样本，仅根据测试样本的在特征空间分布情况判断其类别。（3）半监督的学习：有少量训练样本，学习机以从训练样本获得的知识为基础，结合测试样本的分布情况逐步修正已有知识，并判断测试

3、样本的类别。（4）强化学习：没有训练样本，但有对学习机每一步是否更接近目标的奖惩措施。CompanyLogo目录1.概念和术语2.决策树归纳算法3.Apriori算法4.聚类算法5.其他一些算法CompanyLogo2决策树归纳算法在20世纪70年代后期和80年代出去，机器学习研究者J.RossQuinlan开发了决策树算法，称作ID3（IterativeDichotomiser，迭代的二分器）Quinlan后来提出了C4.5（ID3的后继），成为新的监督学习算法的性能比较基准，核心算法是ID3

4、。1984年几位统计学家（L.Breiman，J.Friedman，R.Olshen和C.Stone）出版了分类与回归树（CART），介绍了二叉决策树的产生。ID3，C4.5和CART都采用贪心（即非回溯的）方法，其中决策树以自顶向下递归的分治方法构造。CompanyLogo2决策树归纳算法从数据产生决策树的机器学习技术叫做决策树学习,通俗说就是决策树。决策树是一种类似于流程图的树结构；其中，每个内部节点（非树叶节点）表示在一个属性上的测试，每个分支代表一个测试输出，而每个树叶节点（或终结点）存

5、放一个类标号。决策树归纳是从类标记的训练元组学习决策树。CompanyLogo2决策树归纳算法一棵典型的决策树如图表5-1所示。某公司应用决策树方法预测客户是否购买电脑的方法，内部节点用矩形表示，而叶节点用椭圆表示。每个内部（非树叶）节点表示一个属性的测试。每个树叶节点代表一个类（buys_computer=yes，或buys_computer=no）CompanyLogo2决策树归纳算法算法思想：设S为训练集，训练集中有U1、U2两类，训练集含有n个属性（A1、A2…An），Ak处有m个取值（

6、V1、V2…Vm）计算该集合所包含的全部属性的互信息，选择最大的Ak，作为节点。把Ak处取值相同的，归为一个子集。若子集中同时含有U1、U2类的样本，返回1，递归调用。若子集仅含有U1或U2，对该分支标上类别，该分支结束运算。当算法遇到以下两种情况，也应停止递归运算。某节点对应的训练数据子集为空。此时该节点作为叶节点，并用父节点中占多数的类别标记。某节点没有剩余的属性。此时，该节点作为叶节点，并用该节点占多数的类别标记。CompanyLogo2决策树归纳算法使用的策略：分而治之过程：递归的对训练

7、数据进行分隔的过程，自顶向下的构造决策树每个后续的递归都选择最佳分类属性作为分隔当前数据实例集的属性。最佳分类属性的选择是通过一个混杂度函数来实现的。CompanyLogo2决策树归纳算法何为混杂度函数？1.混杂度函数反映了用该属性进行数据分隔以后的数据集的混杂度。2.目前用于决策树学习的混杂度函数是信息增益和信息增益率。3.这里的信息增益是涉及了信息论中信息熵的概念。信息熵是表示一个事件的不确定性的大小，不确定性越大那么该事件包含的信息熵就越大，如果一个事件完全确定了，那么它所包含的信息熵就是

8、0CompanyLogo2决策树归纳算法信息增益的主要思想1.给定一数据集D，用公式(1)entropy(D)=－计算D的混杂度，表示为entropy(D)2.然后，把所有的属性都计算一遍，找出用哪个属性来划分D可将D的混杂度减少最多，设属性Ai可取V个值，则用Ai来划分D，可将D划分为不相交的V个子集D1，D2，D3，...,Dm划分后D的熵为entropy(Di)=此处的entropy(Dj)用第一步的公式求解。属性Ai的信息增益计算如下Gain(D,Ai)=entropy(D)-entro