计算机软件及应用数据挖掘算法报告五条算法ppt课件

数据挖掘经典算法概述,数据挖掘十大算法,聚类,为了更加方便直观的理解算法，每一个算法都不会只是空洞的讲述原理及步骤，都会有一个实例进行讲解展示，从而可以更直观的了解算法是如何应用的。,算法一：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、创建节点N 2、如果训练集为空，在返回节点N标记为Failure 3、如果训练集中的所有记录都属于同一个类别，则以该类别标记节点N 4、如果候选属性为空，则返回N作为叶节点，标记为训练集中最普通的类； 5、for each 候选属性 attribute_list 6、if 候选属性是连续的then 7、对该属性进行离散化 8、选择候选属性attribute_list中具有最高信息增益的属性D 9、标记节点N为属性D 10、for each 属性D的一致值d 11、由节点N长出一个条件为D=d的分支 12、设s是训练集中D=d的训练样本的集合 13、if s为空 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-Complexity Pruning）、悲观修剪（Pessimistic Pruning）和MDL（Minimum Description Length）修剪。对于树的修剪，相对树的生成要简单一些 ，时间关系， 具体就不讲了，有兴趣下来讨论。,C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进： 1) 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足； 2) 在树构造过程中进行剪枝； 3) 能够完成对连续属性的离散化处理； 4) 能够对不完整数据进行处理。 C4.5算法有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。此外，C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。,C4.5总结,算法二：K-Means,挖掘主题：聚类 k-means算法是一个聚类算法，把n个对象根据他们的属性分为k个分割(k n)。它与处理混合正态分布的最大期望算法很相似，因为他们都试图找到数据中自然聚类的中心。它假设对象属性来自于空间向量，并且目标是使各个群组内部的均方误差总和最小。,聚类,所谓聚类问题，就是给定一个元素集合D，其中每个元素具有n个可观察属性，使用某种算法将D划分成k个子集，要求每个子集内部的元素之间相异度尽可能低，而不同子集的元素相异度尽可能高。其中每个子集叫做一个簇 。 与分类不同，分类是示例式学习，要求分类前明确各个类别，并断言每个元素映射到一个类别。而聚类是观察式学习，在聚类前可以不知道类别甚至不给定类别数量，是无监督学习的一种。,聚类图形化表示如图：,K次平均算法,K-means算法的基本思想是：给定一个包含n个数据对象的数据库，以及要生成簇的数目k，随机选取k个对象作为初始的k个聚类中心；然后计算剩余各个样本到每一个聚类中心的距离，把该样本归到离它最近的那个聚类中心所在的类，对调整后的新类使用平均值的方法计算新的聚类中心；如果相邻两次的聚类中心没有任何变化，说明样本调整结束且聚类平均误差准则函数已经收敛。本算法在每次迭代中都要考察每个样本的分类是否正确，若不正确，就要调整。在全部样本调整完成后修改聚类中心，进入下一次迭代。如果在一次迭代算法中，所有的样本被正确分类，则不会有调整，聚类中心不会有变化。在算法迭代中值在不断减小，最终收敛至一个固定的值。该准则也是衡量算法是否正确的依据之一。,K-Means步骤,假设要把样本集分为c个类别，算法描述如下： （1）适当选择c个类的初始中心； （2）在第k次迭代中，对任意一个样本，求其到c个中心的距离，将该样本归到距离最短的中心所在的类； （3）利用均值等方法更新该类的中心值； （4）对于所有的c个聚类中心，如果利用（2）（3）的迭代法更新后，值保持不变，则迭代结束，否则继续迭代。 该算法的最大优势在于简洁和快速。算法的关键在于初始中心的选择和距离公式。,实例：中国男足,下面，我们来看看k-means算法一个有趣的应用示例：中国男足近几年到底在亚洲处于几流水平？下页的图是亚洲15只球队在2005年-2010年间大型杯赛的战绩 其中包括两次世界杯和一次亚洲杯。我提前对数据做了如下预处理：对于世界杯，进入决赛圈则取其最终排名，没有进入决赛圈的，打入预选赛十强赛赋予40，预选赛小组未出线的赋予50。对于亚洲杯，前四名取其排名，八强赋予5，十六强赋予9，预选赛没出现的赋予17。这样做是为了使得所有数据变为标量，便于后续聚类。,下面先对数据进行0,1规格化，下表是规格化后的数据,接着用k-means算法进行聚类。设k=3，即将这15支球队分成三个集团。现抽取日本、巴林和泰国的值作为三个簇的种子，即初始化三个簇的中心为A：0.3, 0, 0.19，B：0.7, 0.76, 0.5和C：1, 1, 0.5 下面，计算所有球队分别对三个中心点的相异度，这里以欧氏距离度量。下面是用程序求取的结果：,从左到右依次表示各支球队到当前中心点的欧氏距离，将每支球队分到最近的簇，可对各支球队做如下聚类：中国C，日本A，韩国A，伊朗A，沙特A，伊拉克C，卡塔尔C，阿联酋C，乌兹别克斯坦B，泰国C，越南C，阿曼C，巴林B，朝鲜B，印尼C。 第一次聚类结果： A：日本，韩国，伊朗，沙特； B：乌兹别克斯坦，巴林，朝鲜； C：中国，伊拉克，卡塔尔，阿联酋，泰国，越南，阿曼，印尼。,下面根据第一次聚类结果，调整各个簇的中心点。 A簇的新中心点为：(0.3+0+0.24+0.3)/4=0.21, (0+0.15+0.76+0.76)/4=0.4175, (0.19+0.13+0.25+0.06)/4=0.1575 = 0.21, 0.4175, 0.1575（取簇中所有元素各自维度的算术平均数。） 用同样的方法计算得到B和C簇的新中心点分别为0.7, 0.7333, 0.4167，1, 0.94, 0.40625。,用调整后的中心点再次进行聚类，得到： 第二次迭代后的结果为： 中国C，日本A，韩国A，伊朗A，沙特A，伊拉克C，卡塔尔C，阿联酋C，乌兹别克斯坦B，泰国C，越南C，阿曼C，巴林B，朝鲜B，印尼C。,结果无变化，说明结果已收敛，于是给出最终聚类结果： 亚洲一流：日本，韩国，伊朗，沙特 亚洲二流：乌兹别克斯坦，巴林，朝鲜 亚洲三流：中国，伊拉克，卡塔尔，阿联酋，泰国，越南，阿曼，印尼 看来数据告诉我们，说国足近几年处在亚洲三流水平真的是没有冤枉他们，至少从国际杯赛战绩是这样的。 其实上面的分析数据不仅告诉了我们聚类信息，还提供了一些其它有趣的信息，例如从中可以定量分析出各个球队之间的差距，例如，在亚洲一流队伍中，日本与沙特水平最接近，而伊朗则相距他们较远，这也和近几年伊朗没落的实际相符。,k均值算法的优点,如果变量很大，k均值的计算速度会很快（如果k很小）。 k均值可以得到紧密的簇，尤其是对于球状簇。 对大数据集，是可伸缩和高效率的。 算法尝试找出使平方误差函数值最小的k个划分。当结果簇是密集的，而簇与簇之间区别明显的时候，效果较好。,K均值算法的缺点,没有指明初始化均值的方法。常用的方法是随机的选取k个样本作为均值。 产生的结果依赖于均值的初始值，经常发生得到次优划分的情况。解决方法是多次尝试不同的初始值。 可能发生距离簇中心mi最近的样本集为空的情况，因此， mi将得不到更新。这是一个必须处理的问题，但我们忽略该问题。 结果依赖于|x- mi|的度量单位。一个常用的解决方法是用标准差规范各个变量，虽然这并非总是可取的。结果还依赖于k值，所以难以比较聚类结果的优劣。 不适合发现非凸面形状的簇，并对噪声和离群点数据是较敏感的，因为少量的这类数据能够对均值产生极大的影响。,算法三： Apriori算法,挖掘主题：关联分析 Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。 其核心是基于两阶段频集思想的递推算法。,关联分析,关联分析是指如果两个或多个事物之间存在一定的关联,那么其中一个事物就能通过其他事物进行预测.它的目的是为了挖掘隐藏在数据间的相互关系 在数据挖掘的基本任务中关联(association)和顺序序贯模型(sequencing)关联分析是指搜索事务数据库(transactional databases)中的所有细节或事务,从中寻找重复出现概率很高的模式或规则。,Apriori算法的基本原理,如何生成频繁集(连接，剪枝) C1(1-项频繁集候选集):扫描数据库,对每个单独的项进行计数得到C1 L1(1-项频繁集):从C1中删除支持度小于sup的项得到L1 Ck+1(K+1项频繁集候选集)：CK+1由Lk与自身连接得到，即CK+1=Lk*Lk连接的条件是，参与连接的两个K项集合前k-1项相同，第k项不同 Lk+1(K+1项频繁集)：从CK+1重删除支持度小于sup的项，删除CK+1中K项子集不在LK中的项 Apriori 性质 任何K+1项频繁集的任意K项子集必须是频繁的,例如：,有L2产生C3的过程,实例,每一行表示一条交易，共有9行，既9笔交易，左边表示交易ID，右边表示商品名称。最小支持度是22%，那么每件商品至少要出现9*22%=2次才算频繁。第一次扫描数据库，使得在每条交易中，按商品名称递增排序。,第二次扫描数据，找频繁项集为1的元素如右图：,左边表示商品名称，右边表示出现的次数，都大于阈值2。在此基础上找频繁项集是2的元素，方法是两两任意组合，第三次扫描数据得到它们出现的次数如左图所示：,这里I1,I4,I3,I4,I3,I5,I4,I5出现的次数都小于2，过滤掉，实际频繁项集为2的元素如右图：,继续上述操作，直到选出最大频繁项集 。,整个过程如下：,Apriori算法的不足,(1 ) 产生大量的频繁集 (2 ) 重复扫描事务数据库,算法四：EM算法,挖掘主题：聚类 在统计计算中，最大期望 （EM，ExpectationMaximization）算法是在概率（probabilistic）模型中寻找参数最大似然估计的算法，其中概率模型依赖于无法观测的隐藏变量（Latent Variabl）。最大期望经常用在机器学习和计算机视觉的数据集聚（Data Clustering）领域。,步骤,EM是一个在已知部分相关变量的情况下，估计未知变量的迭代技术。EM的算法流程如下： 初始化分布参数 重复直到收敛： E步骤：估计未知参数的期望值，给出当前的参数估计。 M步骤：重新估计分布参数，以使得数据的似然性最大，给出未知变量的期望估计。,实例,(3) 假设上一步猜测的结果为 B,A,A,B,A，那么根据这个猜测，可以像完 整数据的参数估计一样重新计算 的值。,EM算法特点,EM算法比K-means算法计算复杂，收敛也较慢，不适于大规模数据集和高维数据，但比K-means算法计算结果稳定、准确。EM经常用在机器学习和计算机视觉的数据集聚（Data Clustering）领域。,算法五：prefixspan算法,挖掘主题：关联分析 采用分治的思想，不断产生序列数据库的多个更小的投影数据库，然后在各个投影数据库上进行序列模式挖掘。PrefixSpan算法就是基于序列投影的一种模式增长算法。,前缀定义,假设所有的项在一个元素中按照字母表的顺序排列出来。给定一个序列=(在这里每一个e都和在S中给定的连续的元素相一致)和一个序列=(mn).只有如果：1）ei=ei（im-1），2）emem ，3）所有在（emem）的连续项在em中都是按照字母表顺序排列的，那么我们就说是的一个前缀。 例如，,和都是序列s=的前缀,后缀定义,序列关于子序列 = 的投影为 = (n = m)，则序列关于子序列的后缀为， 其中em” = (em - em)。 例如，对于序列s=，就被认识为是关于前缀的后缀，就被认为是关于前缀的后缀， 就被被认为是关于前缀的后缀。,投影数据库定义,令是在序列数据库S中的一个序列模式，这个-投影数据库表示为：S|。 简单来说，它是在S中关于前缀的序列的后缀的集合,PrefixSpan算法是一种深度优先搜索算法，其基本思想是使用频繁前缀划分搜索空间和投影序列数据库，并搜索相关的序列。首先检查前缀子序列，只将其相应的后缀子序列投影到数据库中。该算法同时采用