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

数据挖掘经典算法概述数据挖掘十大算法N关联分析PrefixSpan2004韩家炜聚类•为了更加方便直观的理解算法，每一个算法都不会只是空洞的讲述原理及步骤，都会有一个实例进行讲解展示，从而可以更直观的了解算法是如何应用的。算法一：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定义22log()log()pn22log()log()pnC4.5定义实例•假设有一个信息系统，关于的是几种天气的不同变化对是否进行比赛的影响．根据这些信息，给定一个决策表如右图：NO.OutlookTemperatureWindyHumidityPlay?1sunnyhotfalsehighNo2sunnyhottruehighNo3overcasthotfalsehighYes4rainMild（温暖）falsehighYes5raincoolfalsenormalYes6raincooltruenormalNo7overcastcooltruenormalYes8sunnymildfalsehighNo9sunnycoolfalsenormalYes10rainmildfalsenormalYes11sunnymildtruenormalYes12overcastmildtruehighYes13overcasthotfalsenormalYes14rainmildtruehighNo“Outlook”的信息增益最大，可知应该选择“Outlook”作为分裂点．接下来，继续上述过程．比如选择“Outlook=sunny”这个分支．现在要考虑计算剩下的三个属性对应的信息增益．NO.TemperatureWindyHumidityPlay?1hotfalsehighNo2hottruehighNo8mildfalsehighNo9coolfalsenormalYes11mildtruenormalYes上述只是完成了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个分割(kn)。它与处理混合正态分布的最大期望算法很相似，因为他们都试图找到数据中自然聚类的中心。它假设对象属性来自于空间向量，并且目标是使各个群组内部的均方误差总和最小。聚类•所谓聚类问题，就是给定一个元素集合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均值算法的优点1.如果变量很大，k均值的计算速度会很快（如果k很小）。2.k均值可以得到紧密的簇，尤其是对于球状簇。3.对大数据集，是可伸缩和高效率的。4.算法尝试找出使平方误差函数值最小的k个划分。当结果簇是密集的，而簇与簇之间区别明显的时候，效果较好。K均值算法的缺点•没有指明初始化均值的方法。常用的方法是随机的选取k个样本作为均值。•产生的结果依赖于均值的初始值，经常发生得到次优划分的情况。解决方法是多次尝试不同的初始值。•可能发生距离簇中心mi最近的样本集为空的情况，因此，