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

数据挖掘经典算法概述,数据挖掘十大算法,聚类,为了更加方便直观的理解算法，每一个算法都不会只是空洞的讲述原理及步骤，都会有一个实例进行讲解展示，从而可以更直观的了解算法是如何应用的。,算法一：C4.5,挖掘主题：分类挖掘C4.5，是机器学习算法中的一个分类决策树算法，它是决策树(决策树也就是做决策的节点间的组织方式像一棵树，其实是一个倒树)核心算法ID3的改进算法，所以基本上了解了一半决策树构造方法就能构造它。决策树构造方法其实就是每次选择一个好的特征以及分裂点作为当前节点的分类条件。,什么是分类？,分类是用于识别什么样的事务属于哪一类的方法,什么是信息熵,信息熵：信息的基本作用就是消除人们对事物的不确定性。所谓信息熵，是一个数学上颇为抽象的概念，在这里不妨把信息熵理解成某种特定信息的出现概率。香农指出，它的准确信息量应该是-(p1*log(2,p1)+p2*log(2,p2)+p32*log(2,p32)，,熵的概念源自热物理学.假定有两种气体a、b，当两种气体完全混合时，可以达到热物理学中的稳定状态，此时熵最高。如果要实现反向过程，即将a、b完全分离，在封闭的系统中是没有可能的。只有外部干预（信息），也即系统外部加入某种有序化的东西（能量），使得a、b分离。这时，系统进入另一种稳定状态，此时，信息熵最低。热物理学证明，在一个封闭的系统中，熵总是增大，直至最大。若使系统的熵减少（使系统更加有序化），必须有外部能量的干预。,也就是说，熵是描述系统混乱的量，熵越大说明系统越混乱，携带的信息就越少，熵越小说明系统越有序，携带的信息越多。,C4.5具体算法步骤,1、创建节点N2、如果训练集为空，在返回节点N标记为Failure3、如果训练集中的所有记录都属于同一个类别，则以该类别标记节点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,C，s）返回的点,C4.5定义,C4.5定义,实例,假设有一个信息系统，关于的是几种天气的不同变化对是否进行比赛的影响根据这些信息，给定一个决策表如右图：,“Outlook”的信息增益最大，可知应该选择“Outlook”作为分裂点,接下来，继续上述过程比如选择“Outlook=sunny”这个分支现在要考虑计算剩下的三个属性对应的信息增益,上述只是完成了ID3,以上是ID3计算信息增益的方法，C4.5算法对此进行了改进。C4.5算法采用信息增益率作为选择分支属性的标准，克服了ID3算法中信息增益选择属性时偏向选择取值多的属性的不足。,树的终止,树的建立实际上是一个递归过程，那么这个递归什么时候到达终止条件退出递归呢？有两种方式，第一种方式是如果某一节点的分支所覆盖的样本都属于同一类的时候，那么递归就可以终止，该分支就会产生一个叶子节点。还有一种方式就是，如果某一分支覆盖的样本的个数如果小于一个阈值，那么也可产生叶子节点，从而终止建立树。我们只考虑二叉分割的情况，因为这样生成的树的准确度更高。,树的修剪,树一旦生成后，便进入第二阶段修剪阶段。决策树为什么要剪枝？原因就是避免决策树“过拟合”样本。前面的算法生成的决策树非常的详细而庞大，每个属性都被详细地加以考虑，决策树的树叶节点所覆盖的训练样本都是“纯”的。因此用这个决策树来对训练样本进行分类的话，你会发现对于训练样本而言，这个树表现堪称完美，它可以100%完美正确得对训练样本集中的样本进行分类（因为决策树本身就是100%完美拟合训练样本的产物）。但是，这会带来一个问题，如果训练样本中包含了一些错误，按照前面的算法，这些错误也会100%一点不留得被决策树学习了，这就是“过拟合”。C4.5的缔造者昆兰教授很早就发现了这个问题，他做过一个试验，在某一个数据集中，过拟合的决策树的错误率比一个经过简化了的决策树的错误率要高。目前决策树的修剪的策略有三种：基于代价复杂度的修剪（Cost-ComplexityPruning）、悲观修剪（PessimisticPruning）和MDL（MinimumDescriptionLength）修剪。对于树的修剪，相对树的生成要简单一些，时间关系，具体就不讲了，有兴趣下来讨论。,C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进：1)用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足；2)在树构造过程中进行剪枝；3)能够完成对连续属性的离散化处理；4)能够对不完整数据进行处理。C4.5算法有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。此外，C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。,C4.5总结,算法二：K-Means,挖掘主题：聚类k-means算法是一个聚类算法，把n个对象根据他们的属性分为k个分割(k=m)，则序列关于子序列的后缀为，其中em”=(em-em)。例如，对于序列s=，就被认识为是关于前缀的后缀，就被认为是关于前缀的后缀，就被被认为是关于前缀的后缀。,投影数据库定义,令是在序列数据库S中的一个序列模式，这个-投影数据库表示为：S|。简单来说，它是在S中关于前缀的序列的后缀的集合,PrefixSpan算法是一种深度优先搜索算法，其基本思想是使用频繁前缀划分搜索空间和投影序列数据库，并搜索相关的序列。首先检查前缀子序列，只将其相应的后缀子序列投影到数据库中。该算法同时采用分治(divideandconquer)的策略，不断产生序列数据库的多个更小的投影数据库，然后在各个投影数据库上进行序列模式挖掘。,算法描述,输入：序列数据库S和最小支持阈值min_support输出：完整的一组序列模式方法：调用PrefixSpan(,0,S)子程序：PrefixSpan(,l,S|)参数：是一个序列模式；l：的长度；S|：如果,S|是的投影数据库，否则他就是序列数据库S。,算法步骤,1）对投影数据库S|进行一次扫描，找到一组连续的项b，其中b可以集合成为的最后一个元素或者可以被追加到上，形成一个序列模式。2）对于每一个连续的项b，把他添加到上形成一个序列，并且输出。3）对于每一个，创建一个-投影数据库S|,并调用PrefixSpan(,l+1,S|).,实例,表中的序列数据库，最小支持数为2，PrefixSpan算法过程如下：,步骤1：对交易数据库扫描一次得到全部频繁项目，它们同时也是频繁1-序列。它们分别是：4：2：3：4,步骤2：基于以上发现的四个频繁项目，序列模式的完整的集合可被分为四个具有不同前缀的序列模式的子集：(1)为前缀的；(4)以为前缀