复旦大学毕业论文高速数据链的挖掘算法(编辑修改稿)

复旦大学毕业论文高速数据链的挖掘算法(编辑修改稿)内容摘要：

储器的存取速度住存储器和磁盘存储器慢，所以，查询优化处理程序所选择的查询优化策略必须避免数据在存储介质之间的频繁传递。 此外，数据库管理系统还必须优 高速数据链的挖掘算法 8 化数据记录在第三级存储器上的分布，降低第三级存储器上数据的选择和存取时间。 在包括第三级存储器的数据库系统中，磁盘通常作为第三级存储器的读写缓冲器。 第二章． Hoeffding 树 介绍： 知识发现系统受三个 主要的有限资源限制：时间、内存和抽样的大小。 在机器学习和统计的传统应用中，抽样的大小往往是最大的限制。 计算资源对于大样本上的搜索是足够的，但在小样本上开展这样的搜索常常会导致超出尺寸或数据丢失后重新捞取。 因此避免超出尺寸成了当务之急。 然而如今的许多数据挖掘的应用中，瓶颈已不再是样本，而是时间和内存。 样本的数量是非常充足的，现行的 KDD 系统基本上无法用上所有的样本。 因此，很多的样本都被浪费了。 充足的数据完全可以用来模拟一些复杂的现象，但是因为我们无法充分利用这些数据，而只能建立一些简单模型。 因此我们必须考虑去 发展一些高效的算法。 目前，最有效的挖掘数据库的算法需要连续扫描硬盘。 然而，即使是这些算法，也只能测试几百万个样本，在实际应用中这甚至还不到一天的数据量。 例如，每天零售链要增加几百万个购买记录。 电信公司要连接几百万个电话。 大银行要操作几百万个 ATM 和信用卡使用申请。 网站日志要记录几百万次点击。 互联网的发展更使随时随地的计算成为现实。 我们可以想象，这样大的数据量将不再是偶然。 现行的数据挖掘系统已经无法应付这一切。 新样本高速到来的同时，未能得到及时利用的数据也无限地增长。 即使仅仅简单地将这些样本保存在第三级存储器 中留待将来使用也成了问题，因为这样做不可靠，极易丢失数据。 况且这些数据上下文相关，当等到资源允许，可以利用它们时，它们也没用了。 若这些样本资源成为了一个可随时扩充的高速数据链，则挖掘样本尺寸各异的数据库的想法本身就已成了一个难题。 我们曾经梦想利用 KDD 系统高效地、连续地组织一一到来的样本而不丢失任何将来可能有用的信息。 现在这种想法通过增量式学习的方法得到实现。 当然，这种有效的算法同 KDD 相比仍有许多不足之处。 有些情况虽然处理得很高效， 高速数据链的挖掘算法 9 但却不能保证得到的模型与分批处理模式得到的一样。 它也无法恢复过去选取的不 满意的样本集。 虽然有些情况下得到与批处理模式一样的模型，但相比之下却显得效率较低，速度较慢。 本文推荐了 Hoeffding 树 一种决策树学习方法。 在一开始，样本数量较少，与批处理模式几乎相同的模式下， Hoeffding 树可以用不变的时间来学习每个样本。 但随着样本数目的增多， Hoeffding 树对于每个结点选择不同测试的可能性将呈指数下降趋势。 我们也描述和评价了 VFDT一种基于 Hoeffding 树的决策树学习方法。 VFDT 受 I/O 限制，因此感觉上，它挖掘样本集的速度比把它们从硬盘输入内存还要快。 它不 在内存中存储样本集，而只需要一些存储 Hoeffding树的空间。 它学习每个样本时都只见到一次，因此也就没有必要将在线数据链中的样本集全部存起来。 VFDT 是一个实时算法，因此，在学习了最初的一些样本之后，它就提供了一个随时可用的模型，并且此模型的质量将随着时间的增加而越来越高。 树 分类问题是如下定义的：一个有 N 个样本的训练集如形式 (x,y)给出 ,y 是一个离散的类说明，而 x 是一个有 d 个属性的向量。 每个属性可以是符号表示的，也可以是数值表示的。 目标是要建造一个模型： y=f(x)，从而根据将来的 x 来高精确度地预测 y。 例如， x 可以是一个客户的购买记录，而 y 表示是否给此客户一本商品目录。 或者 x 是一个蜂窝电话记录，而 y 表示它是否具有欺诈性。 最有效也用的最多的分类方法就是决策树学习方法。 学习者通过决策树归纳出模型，其中的每个结点都包含对一个属性的测试，每条树都通向这棵树的一个可能的输出结果，每个叶子都包含了一个预测类。 Y=DT(x)的获得方法是将待测样本自根结点一直下行至叶子结点，在每个结点用其特定的属性进行测试，根据测试结果进入相应树枝。 一棵决策树是自根结点开始，通过递归地测试结点，更 换叶子得到的。 对于每个结点的测试属性的选择，我们运用某些启发式规则来比较该结点的所有可用属性，从中选出最合适的一个。 分类决策学习者例如 ID 和CART 都假定所有的训练集可以同时存在主存里，因此它们能够学习的样本数受到了严格的限制。 基于硬盘的决策树学习者象 SLIQ 和 SPRINT 假定所有的样本都存在硬盘上，通过反复的读取来学习它们。 当训练集的尺寸骤增时，学习这样 高速数据链的挖掘算法 10 复杂的树的代价是很高的，若数据集大到了硬盘无法容纳的程度时，这些方法将彻底失败。 我们的目标是要为海量数据集设计一个决策树学习者。 它要求以极短 的、不变的时间一次性地学习每个样本，这样将可以直接挖掘在线数据资源并以可接受的计算代价去建造具有潜力的复杂的树。 我们要在保证考虑所有训练样本的一个小的子集就足够的前提下，为每个结点选取一个测试属性。 这样，对于一个给定的数据链，最初的一些样本用来对根结点进行测试，余下的用来生成叶子，并为叶子选择测试属性，如此递归进行。 我们运用 Hoeffding 约束来解决究竟应选取多少样本来得到测试属性这个难题。 若一个真值随机变量 r 的取值 范围是 R，假定我们对 r 有 n 个独立的观察值，并计算了它们的平均值 r ， Hoeffding 约束即是：对于可信度 1δ ，变量 r 的真实值至少是 r ε ，其中 ε = nR 2 )/1ln(2  树算法 输入 : S 样本集 X 离散属性集 G(•) 所用启发式规则 δ 给定的可信度 输出 : HT 一棵决策树 Procedure Hoeffding(S,X,G,δ ) 令 HT 是一棵只有一个 l1叶子 (根 )的树 令 X1=XU{ X216。 } 令 G 1(X216。 )是预测了 S 中的最多见的类后得到的 G 对每个 yk 对每个 xij 值 (属性 xi∈ X的值 ) 令 nijk (l1)=0 对每个样本 (x,yk) ∈ S Sort(x,y)作为一个叶子 l 对每个 xij(xij 是 xi∈ Xl 的值 )。