数据挖掘技术与关联规则挖掘算法研究(收藏)

数据挖掘技术与关联规则挖掘算法研究(收藏)内容摘要：

索和实践。  数据挖掘理论与算法研究。 经过十几年的研究，数据挖掘已经在继承和发展相关基础学科（如机器学习、统计学等）已有成果方面取得了可喜的进步，探索出了许多独具特色的理论体系。 但是，这决不意味着挖掘理论的探索已经结束，恰恰相反它留给了研究者丰富的理论课题。 一方面，在这些大的理论框架下有许多面向实际应用目标的挖掘理论等待探索和创新。 另一方面，随着数据挖掘技 术本身和相关技术的发展，新的挖掘理论的诞生是必然的，而且可能对特定的应用产生推动作用。 新理论的发展必然促进新的挖掘算法的产生，这些算法可能扩展挖掘的有效性，如针对数据挖掘的某些阶段、某些数据类型、大容量源数据集等更有效；可能提高挖掘的精度或效率；可能融合特定的应用目标，如 CR M、电子商务等。 因此，对数据挖掘理论和算法的探讨将是长期而艰巨的任务。 从上面的叙述，可以看出数据挖掘研究和探索的内容是及其丰富和具有挑战性的。 我们正是在这样的背景下，在以往的研究和各类基金的支持下，开展相关研究工作的。 第 1章 绪论 ４ 拟解决 的问题 作为博士论文，我们在收集和整理大量的相关资料，弄清相关的理论、方法、算法、体系结构（原型系统）等基础上，集中选取了下面几个问题开展相关工作：  数据挖掘过程和系统构架研究。 在分析现有的数据挖掘系统（原型系统）的体系结构基础上，系统化研究了数据挖掘系统的基本过程和功能部件。 这些研究包括从数据挖掘 的基本 过程来探 讨系统 应具备 的主要功能部件及其相互联系；不同的源数据类型对数据挖掘系统的功能部件要求；不同的应用目标对数据挖掘系统的功能部件要求；数据挖掘系统的主要功能部件的实现机制等。  数据挖掘理论探索。 如前所述 ，数据挖掘已经建立了许多独具特色 的挖掘 理论体系 ，但是 不论是 从应用范围、有效性以及适应性等方面仍需新的挖掘理论的探索。 因此，本文对关联规则（ Association Rule）挖掘理论和模型进行了研究，建立了项目序列集格空间和基于项目序列集操作的关联规则挖掘模型等。  关联规则挖掘算法 设计。 关联规则挖掘是数据挖掘中研究较早而且至今仍最活跃的研究分支之一。 影响关联规则的挖掘效率的因素主要有数据库扫描的 I/O 代价、内存的需求、 CPU 的时间花费等。 目前的关联规则挖掘算法仍然需要在这些方面加以创新或改进。 因此，我们选取了 关联规则挖掘算法进行了集中研究和实现，并通过系列的算法设计和实现来验证我们新的挖掘理论和积累研制数据挖掘系统的经验。 创新性工作 本文的创新性工作集中在数据挖掘理论和关联规则挖掘算法设计两个方面。 数据挖掘理论研究 大多数文献中使用的项目集（ Itemset）是普通的集合概念 [1， 2]。 我们使用术语“项目序列（ Ite msequence）”来替 代其第 1章 绪论 ５ 它文献中出现的“项目集”。 所谓项目序列是指项目集中的元素是按特定标准（如出现次数、字典排序）进行有序排列的。 因此，我们首次引入的项目序列集（ Set of Itemsequences）概念可以用来表示一类特定的项目序列集合（如频繁项目序列集）。 本文主要的理论研究和成果为： （ 1）基于项目序列集操作的挖掘模型 我们建立了项目序列集的代数空间描述，并探讨了在这个空间上的基本 操作算子。 在此基础上，讨论了基于项目序列集操作的数据挖掘模型（详见第 4 章）。 （ 2）约束条件下的数据挖掘理论 毫无疑问，引进约束条件可以加速数据挖掘的过程。 但是，约束条件的引入，必须解决诸如适合数据挖掘的约束条件的形式化表示以及约束条件在数据挖掘特定阶段的使用方式等。 本文针对时态约 束条件下的数据挖掘理论问题进行了探索。 在时态区间代数空间上定义了两个新的时态区间变量操作（时态交∩T 和时态并 UT）。 基于这样的时态约束条件下的数据挖掘理论框架，我们可以扩展数据挖掘工作到包括数据过滤（ Data filtrating）、时态区间合并等数据预处理在内的更广泛的范畴中去（详见第 5 章）。 （ 3）数据分割下的数据挖掘理论 随着数据库容量的增大，使得通过对源数据集的分割来处理大容量数据库的数据挖掘问题成为必要。 本文就数据分割下的数据 挖 掘 问 题 进 行 了 讨 论 ， 引 入 局 部 频 繁 项 目 序 列 集 (Local Frequent Set of Ite msequences) 和 全 局 项 目 序 列 集 (Global Frequent Set of Itemsequences)等概念，并解决了局部频繁项目序列集和全局频繁项目序列集转换等问题（详见第 6 章）。 关联规则挖掘算法设计与实现 把上面的数据挖掘理论应用到关联规则的发现中，我们完成了相应算法的设计，并且通过理论分析和实验模拟讨论了算法的性能。 第 4 章介绍了基于项目序列集操作的 ISSDM 算法。 它是一个一次数据库扫描并且不使用侯选集的高效算法。 为了增强对大容量数据库挖掘的适应性和可 用性，第 5 章设计了时第 1章 绪论 ６ 态约束下的 TISSDM 算法。 它是对 ISSDM 算法的改进，实验证明它具有较好的数据过滤和区间合并效率，因而能在同样的处理环境下挖掘更大容量的数据库（比 ISSDM）。 第 6 章提出了另一个 ISSDM 的改进算法 PISSDM。 它通过对数据库的分割，减少了对内存和 CPU 等系统资源的占用，而且可以在两次数据库扫描的情况下完成挖掘工作。 本章小节 本章介绍了数据挖掘研究的意义和技术背景、论文的选题依据、研究背景以及我们的主要研究内容等。 数据挖掘作为二十世纪信息处理的骨干技术之一，正以一种 全新的概念改变着我们利用数据的方式。 经过十几年的研究和实践，数据挖掘技术已经融合了许多学科的最新研究成果而形成独具特色的研究分支。 目前的数据挖掘研究正处于蓬勃发展时期，有许多具有挑战性的课题被提出。 数据挖掘的研究内容是极其丰富的。 作为博士论文，我们在充分了解基本概念和主要技术发展状况的前提下，有选择地进行了重点研究。 这些研究包括数据挖掘系统的体系结构、关联规则挖掘理论和算法等。 第 2 章 数据挖掘技术 7 第 2 章 数据挖掘技术 数 据 挖 掘 作 为 一 个 只 有 十 几 年 研 究 历 史 的 较 新 研 究 领域，许多 概念和技 术是逐 步发展 起来的。 因此， 本章将 系统地介绍相 关的概念 和技术 ，并力 求从不同 视点和 流派来 阐述数据挖掘的 重要概 念、发展 和应用 情况。 在 2 .1 节，我 们介绍了数据挖 掘技术 产生的商 业和技 术背景； 在 节， 我们从不 同视 点阐 述了 数据 挖掘 的概 念和 主要 理论 构架 ；在 节，我们 从多种 角度对数 据挖掘 系统的分 类问题 进行了概 括；在 节，我们 从知识 表示模式 角度出 发，归纳 了主要 的数据挖掘技术 及其研 究成果 ； 节对不 同源数据 组织形 式下的数 据挖 掘技 术的 特点 和策 略进 行了 剖析 ； 2. 6 节 分析 了数据挖掘技术的应用现状和发展趋势。 数据挖掘技术的 产生背景 数 据 挖 掘 技 术的 商业 需求分 析 数据挖 掘之 所以 吸引 专家 学者的 研究 兴趣 和引 起商 业厂家的广泛 关注，主 要在于 大型数 据系统的 广泛使 用和把 数据转换成有用 知识的 迫切需要。 60 年代，为了适应 信息的 电子化要求， 信息技术 一直从 简单的 文件处理 系统向 有效的 数据库系统变革。 70 年 代，数 据库系 统的三个 主要模 式――层 次、网 络 和 关 系 型 数据 库 的 研 究 和开 发 取 得 了重 要 进 展。 80 年代，关系 型数据库 及其相 关的数 据模型工 具、数 据索引 及数据组织技术 被广泛 采用，并且成 为了整个 数据库 市场的主 导。 80 年代中 期开始 ，关系 数据库技 术和新 型技术的 结合成 为数据库研究 和开 发的 重要标 志。 从 数据模型 上看， 诸如扩 展关系、面向 对象 、对象 关系（ Objec tRelatio n）以 及演绎 模型等被应用 到数据库 系统中。 从应 用的数据 类型上 看，包 括空间、时态、 多媒体 以及 WE B 等 新型数 据成为数 据库应 用的重要数据源。 同 时，事 务数据 库（ Tra nsactio n Da tabase）、主动数据库 （ Ac tive Database）、知 识库（ K now led ge Base）、办公信息库（ Infor ma tio n Base）等 技术也 得到蓬 勃发展。 从第 2 章 数据挖掘技术 8 数据的 分布 角度 看，分 布式 数据 库（ Distrib uted Data ba se）及其透明 性、并发 控制、 并行处 理等成为 必须面 对的课 题。 进入 90 年 代，分 布式数据 库理论 上趋于成 熟，分 布式数 据库技术得到 了广泛应 用。 目 前，由 于各种新 型技术 与数据 库技术的有机 结合，使 数据库 领域中 的新内容 、新应 用、新 技术层出不穷 ，形成了 庞大的 数据库 家族。 但 是，这 些数据 库的应用都是 以实时查 询处理 技术为 基础的。 从本质 上说， 查询是对数据 库的被动 使用。 由于简 单查询只 是数据 库内容 的选择性输出 ，因此它 和人们 期望的 分析预测 、决策 支持等 高级应用仍有很大距离。 新的需 求推 动新 的技 术的 诞生。 数据 挖掘 的灵 魂 是 深层次的数据 分析方法。 数 据 分析 是 科学研究 的基础 ，许多 科学研究都是 建立在 数 据收集 和分析 基础上的。 同时 在目前 的商业活动中 ， 数据分 析 总是 和一些 特殊的人 群的高 智商行 为联系起来， 因为并不 是每个 平常人 都能从过 去的销 售情况 预测将来发展 趋势或作 出正确 决策的。 但是， 随着一 个企业 或行业业务数 据的不断 积累， 特别是 由于数据 库的普 及，人 工去整理和理 解如此大 的数据 源已经 存在效率 、准确 性等问 题。 因此，探 讨自动化 的数据 分析技 术， 为 企业 提供 能带来 商业利润 的决策信息 而成为必然。 事实上， 数据 （ Data ） 、信息 （ Infor ma tio n ）和 知识（ K now led ge）可以 看作 是广义 数据 表现 的不同 形式 [ 3 ]。 毫不夸张地说 ，人们对 于数据 的拥有 欲是贪婪 的，特 别是计 算机存储技术 和网络技 术的发 展加速 了人们收 集数据 的范围 和容量。 这种贪婪 的结果导 致了“ 数据 丰富而 信息 贫乏 （ Data Ric h amp。 Infor ma tio n Poor）” 现象的产 生。 数 据库是目 前组织 和存储数据的 最有效方 法之一 ，但是 面对日益 膨胀的 数据， 数据库查询技 术已表现 出它的 局限性。 直观上 说，信 息或称 有效信息是指 对人们有 帮助的 数据。 例如，在 现实社 会中， 如果人均日阅读 时间在 30 分钟 的话，一个人 一天最快 只能浏 览一份 20 版左 右的报纸。 如果 你订阅 了 100 份 报纸，其实你 每天也不过只 阅读了一 份而已。 面对 计算机中 的海量 的数据 ，人们也处于 同样的尴 尬境地 ，缺乏 获取有效 信息的 手段。 知识是一种 概 念、规则 、模式 和规律 等。 它不 会象数 据或信 息那么具体， 但是它却 是人们 一直不 懈追求的 目标。 事实上。 在我们的生 活中， 人们 只是 把数据 看作是形 成知识 的源泉。 我第 2 章 数据挖掘技术 9 们是通过 正面的或 反面的 数据或 信息来形 成和验 证知识 的，同时又不 断地利用 知识来 获得新 的信息。 因此， 随着数 据的膨胀和技 术环境的 进步， 人们对 联机决策 和分析 等高级 信息处理的要 求越来越 迫切。 在强大 的商业需 求的驱 动下， 商家们开始注 意到有效 地解决 大容量 数据的利 用问题 具有巨 大的商机；学 者们开始 思考如 何从大 容量数据 集中获 取有用 信息和知识的 方法。 因 此，在 二十世 纪八十年 代后期 ，产生 了数据仓库和数据挖掘等信息处理思想。 数 据 挖 掘 产 生的 技术 背景分 析 任何技 术的 产生 总是 有它 的技术 背景 的。 数据 挖掘 技术的提出和 普遍接受 是由于 计算机 及其相关 技术的 发展为 其提供了研究和应用的技术基础。 归纳数 据挖 掘产 生的 技术 背景， 下面 一些 相关 技术 的发展起到了决定性的作用：  数据库、数据仓库和 Inter ne t 等 信息技 术的发展 ；  计算机性能的提高和先进的体系结构的发 展；  统计学和人工智能等方法在数据分析中的研究和应用。 数据库技术 从二十 世纪 80 年代开始 ，已经得 到广泛 的普及和应用。 在关系 型数据 库的研 究和产品 提升过 程中， 人们一直在探 索组织大 型数据 和快速 访问的相 关技术。 高性 能关系数据库 引擎以及 相关的 分布式 查询、并 发控制 等技术 的使用，已经 提升了数 据库的 应用能 力。 在数 据的快 速访问 、集成与抽取 等问题的 解决上 积累了 经验。