数据挖掘算法报告(五条算法).ppt

《数据挖掘算法报告(五条算法).ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、数据挖掘经典算法概述数据挖掘十大算法N关联分析PrefixSpan2004韩家炜聚类为了更加方便直观的理解算法，每一个算法都不会只是空洞的讲述原理及步骤，都会有一个实例进行讲解展示，从而可以更直观的了解算法是如何应用的。算法一：C4.5挖掘主题：分类挖掘C4.5，是机器学习算法中的一个分类决策树算法，它是决策树(决策树也就是做决策的节点间的组织方式像一棵树，其实是一个倒树)核心算法ID3的改进算法，所以基本上了解了一半决策树构造方法就能构造它。决策树构造方法其实就是每次选择一个好的特征以及分裂点作为当前

2、节点的分类条件。什么是分类？分类是用于识别什么样的事务属于哪一类的方法什么是信息熵信息熵：信息的基本作用就是消除人们对事物的不确定性。所谓信息熵，是一个数学上颇为抽象的概念，在这里不妨把信息熵理解成某种特定信息的出现概率。香农指出，它的准确信息量应该是-(p1*log(2,p1)+p2*log(2,p2)+　．．．　+p32*log(2,p32))，熵的概念源自热物理学.假定有两种气体a、b，当两种气体完全混合时，可以达到热物理学中的稳定状态，此时熵最高。如果要实现反向过程，即将a、b完全分离，在封闭的

3、系统中是没有可能的。只有外部干预（信息），也即系统外部加入某种有序化的东西（能量），使得a、b分离。这时，系统进入另一种稳定状态，此时，信息熵最低。热物理学证明，在一个封闭的系统中，熵总是增大，直至最大。若使系统的熵减少（使系统更加有序化），必须有外部能量的干预。也就是说，熵是描述系统混乱的量，熵越大说明系统越混乱，携带的信息就越少，熵越小说明系统越有序，携带的信息越多。C4.5具体算法步骤1、创建节点N2、如果训练集为空，在返回节点N标记为Failure3、如果训练集中的所有记录都属于同一个类别，则以

4、该类别标记节点N4、如果候选属性为空，则返回N作为叶节点，标记为训练集中最普通的类；5、foreach候选属性attribute_list6、if候选属性是连续的then7、对该属性进行离散化8、选择候选属性attribute_list中具有最高信息增益的属性D9、标记节点N为属性D10、foreach属性D的一致值d11、由节点N长出一个条件为D=d的分支12、设s是训练集中D=d的训练样本的集合13、ifs为空14、加上一个树叶，标记为训练集中最普通的类15、else加上一个有C4.5（R-{D},

5、C，s）返回的点C4.5定义C4.5定义实例假设有一个信息系统，关于的是几种天气的不同变化对是否进行比赛的影响．根据这些信息，给定一个决策表如右图：NO.OutlookTemperatureWindyHumidityPlay?1sunnyhotfalsehighNo2sunnyhottruehighNo3overcasthotfalsehighYes4rainMild（温暖）falsehighYes5raincoolfalsenormalYes6raincooltruenormalNo7overcast

6、cooltruenormalYes8sunnymildfalsehighNo9sunnycoolfalsenormalYes10rainmildfalsenormalYes11sunnymildtruenormalYes12overcastmildtruehighYes13overcasthotfalsenormalYes14rainmildtruehighNo“Outlook”的信息增益最大，可知应该选择“Outlook”作为分裂点．接下来，继续上述过程．比如选择“Outlook=sunny”这个分支

7、．现在要考虑计算剩下的三个属性对应的信息增益．NO.TemperatureWindyHumidityPlay?1hotfalsehighNo2hottruehighNo8mildfalsehighNo9coolfalsenormalYes11mildtruenormalYes上述只是完成了ID3以上是ID3计算信息增益的方法，C4.5算法对此进行了改进。C4.5算法采用信息增益率作为选择分支属性的标准，克服了ID3算法中信息增益选择属性时偏向选择取值多的属性的不足。树的终止树的建立实际上是一个递归过程，

8、那么这个递归什么时候到达终止条件退出递归呢？有两种方式，第一种方式是如果某一节点的分支所覆盖的样本都属于同一类的时候，那么递归就可以终止，该分支就会产生一个叶子节点。还有一种方式就是，如果某一分支覆盖的样本的个数如果小于一个阈值，那么也可产生叶子节点，从而终止建立树。我们只考虑二叉分割的情况，因为这样生成的树的准确度更高。树的修剪树一旦生成后，便进入第二阶段——修剪阶段。决策树为什么要剪枝？原因就是避免决策树“过拟合”样本。前面的算法生成的