维普资讯 http://www.cqvip.com 本栏目责任编辑：阉翔军 ｅ ・・数据库及信息管理・ 数据挖掘综述 方元康１２ （１．合肥工业大学计算机与信息学院，安徽合肥２３０００９；２．池州学院计算机中心，安徽池州２４７０００） 摘要：综述了关联规则、分类与预测、聚类分析等数据挖掘的三个主要功能，最后描述了数据挖掘的发展前景。 关键词：数据挖掘；关联规则；分类和预测；聚类分析；发展前景 中图分类号：ＴＰ３１１．１３８ 文献标识码：Ａ 文章编号：１００９—３０４４（２００７）１７—３１１８９一Ｏ２ Ａｎ Ｏｖｅｒｖｉｅｗ ｏｆ Ｄａｔａ Ｍｉｎｉｎｇ ＦＡＮＧ Ｙｕａｎ—ｋａｎｇ 。 （１．Ｃｏｍｐｕｔｅｒ＆Ｉｎｆｏｒｍａｔｉｏｎ Ｃｏｎｅｇｅ，ＨｅＦｅｉ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ，Ｈｅｆｅｉ ２３０００９，Ｃｈｉｎａ；２．Ｃｏｍｐｕｔｅｒ Ｃｅｎｔｅｒ，ＣｈｉＺｈｏｕ Ｃｏｎｅｇｅ，Ｃｈｉｚｈｏｕ ， ２４７０００，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｉｔ ｉｓ ａ Ｓｕｎｍａａｒｙ ｆｏｒ ｄａｔａ ｍｉｍｎｇ ｔｈａｔ ｒｅｖｉｅｗ ｉｔｓ ｔｈｒｅｅ ｍａｉｎ ｆｕｎｃｔｉｏｎｓ ｓｕｃｈ ａｓ ａｓｓｏｃｉａｔｉｏｎ ｒｕｌｅｓ，ｃｌａｓｓｉｉｆｃａｔｉｏｎ ａｎｄ ｐｒｅｄｉｃｔｉｎｇ ａｎｄ ｃｌｕｓ— ｔｅｒｉｎｇ．Ａｔ ｌａｓｔ，ｉｔ ｄｅｓｃｒｉｂｅｓ ｔｈｅ ｆｏｒｅｇｒｏｕｎｄ ｏｆ Ｄａｔａ Ｍｉｎｉｎｇ． Ｋｅｙ ｗｏｒｄｓ：Ｄａｔａ Ｍｉｎｉｎｇ；ａｓｓｏｃｉａｔｉｏｎ ｒｕｌｅｓ；ｃｌａｓｓｉｉｆｃａｔｉｏｎ ａｎｄ ｐｒｅｄｉｃｔｉｎｇ；ｃｌｕｓｔｅｒｉｎｇ；ｆｏｒｅｇｒｏｕｎｄ １引言 度大于或等于最小支持度闯值．并且它的直接真超集都不具有和 用数据库管理系统来存储数据．用机器学习的方法来分析数 它相同的支持度计数 ） 据．挖掘大量数据背后的知识．这两者的结合促成了数据库中的 ２．２ Ａｐｒｉｏｒｉ算法 知识发现（ＫＤＤ：ＫｎｏＷｌｅｄｇｅ Ｄｉｓｃｏｖｃｒｙ ｉｎ Ｄａｔａｂａｓｅｓ）的产生。实际 Ａｐｒｉｏｒｉ算法利用频繁项集性质的先验知识（ｐｒｉｏｒ ｋｎｏｗｌ— 上．ＫＤＤ是一门交叉性学科．不但涉及到机器学习．而且涉及到模 ｅｄｇｅ），通过逐层搜索的迭代方法．即将ｋ一项集用于探察ｆｋ＋１）一项 式识别、统计学、数据可视化、高性能计算、专家系统等多个领域。 集，来穷尽数据集中的所有频繁项集。先找到频繁ｌ一项集集合Ｌ１． 从数据库中发现出来的知识可以用在科学研究、信息管理、过程 然后用Ｌ１找到频繁２一项集集合Ｌ２，接着用Ｌ２找Ｌ３．直到找不 控制、决策支持等各个方面 数据挖掘是ＫＤＤ最核心的部分，是 到频繁ｋ一项集，找每个Ｌｋ需要一次数据库扫描。 采用机器学习、统计等方法进行知识学习的阶段、数据挖掘算法 ２．２．１ Ａｐｒｉｏｒｉ性质 的好坏将直接影响到所发现知识的好坏 目前大多数的研究都集 频繁项集的所有非空子集也必须是频繁的 （ＡＵＢ模式不可 中在数据挖掘算法和应用上 能比Ａ更频繁的出现）Ａｐｒｉｏｒｉ算法是反单调的，即一个集合如果 ２关联规则挖掘 不能通过测试，则该集合的所有超集也不能通过相同的测试 ２．１关联规则的定义 ２．２．２ Ａｐｒｉｏｒｉ算法步骤 关联规则挖掘就是从事务数据库．关系数据库和其他信息存 Ａｐｒｉｏｒｉ算法由连接和剪枝两个步骤组成 储中的大量数据的项集之间发现有趣的、频繁出现的模式、关联 连接 和相关性。应用于购物篮分析、分类设计、捆绑销售和亏本销售 为了找Ｌｋ，通过Ｌ 与自己连接产生候选ｋ一项集的集合，该 分析等。关联分析是发现ｘ＝＞Ｙ关联规则的分析，分析这些规则展 候选ｋ项集记为Ｃ 。 示属性一值频繁地在给定数据集中一起出现的条件 更形式化的． Ｌ¨中的两个元素Ｌ 和 可以执行连接操作ｌ 。ｌ，的条件是 关联规则Ｘ＝＞Ｙ是形如Ａｌ＾…＾Ａ ＝＞Ｂ Ａ…＾Ｂ 的规则。其中 （‘【ｌ】＝／Ａｌ１）＾（／ｄ２】＝／２１２１）Ｉ＇，．．Ａ（‘【七一２】＝ 【 －－２１）Ａ（‘【七一１】＜１２【七一ｌ】） Ａ，。Ｅ是属性一值对。 关联规则有多种分类 剪枝 根据规则中所处理的值类型来分有： Ｃ 是 的超集，即它的成员可能不是频繁的，但是所有频繁 布尔关联规则 的ｋ一项集都在Ｃ 中。因此可以通过扫描数据库，通过计算每个 量化关联规则 ｋ一项集的支持度来得到 。为了减少计算量，可以使用Ａｐｒｉｏｒｉ性 （ ．’３０…３９”）＾ｉｎｃｏｍｄ（ 、”４２ｋ…４８ｋ”）＝ ｂ￣ｏ＇ｓ（－、’，”ｃｏｌｎｐｔｔｔｅｔ‘’’） 质，即如果一个ｋ一项集的（ｋ一１）一子集不在 一 中，则该候选不可能 根据规则中设计的数据维来分有： 是频繁的，可以直接从Ｃ 删除 单维关联规则 ２．３ Ａｐｒｉｏｒｉ算法的变形 ｂ￣ｏ＇ｓ（＾ ，”ｃｏｍｐｕｔｅＪ ） ｂｔ９’Ｓ（』 ”ｓｏ）％＇ａｒｅ”） 为了提高Ａｐｒｉｏｒｉ算法的有效性．目前已经提出了许多Ａｐｒｉｏｒｉ 关联规则 算法的变形．旨在提高原算法的效率 根据规则集所涉及的抽象层来分有： ｆｌ１基于划分的的方法 单层关联规则 Ｓａｖａｓｅｒｅ设计了一个基于划分的改进算法 多层关联规则 ｆ２１基于散列的技术 一个高效地产生频集的基于散列的算法由Ｄａｒｋ等提出来。 ａｇｅ（ ，”３０…３９”） ｂｔｏ＇ｓ（ ”ｌａｐｔｏｐｃｏＷｌｐｔｌｌＧ＇ ’） ａｇｅ（ ．’３Ｏ…３９＂）ｊ ｂｌｏ＇ｓ（．Ｙ，”ｃｏｍｐｔｔ￣ｌ ’ ） ｆ３、基于选样的方法 、 根据关联挖掘的各种扩充来分有： Ｍａｎｎｉｌａ、Ｔｏｉｖｏｎｅｎ、Ｌｉｎ和ｄｕｎｈａｍ等等提出各种选样方法 事务压缩的方法 ‘挖掘最大的频繁模式（该模式的任何真超模式都是非频繁 减少用于未来扫描的事务集的大小 一个基本的原理就是当 的） 一挖掘频繁闭项集（一个项集ｃ是频繁闭项集．如果它的支持 个事务不包含长度为Ｋ的大项集．则必然不包含长度为Ｋ＋Ｉ 的大项集。从而我们就可以将这些事务移去，这样在下一遍的扫 收稿！ｌｆ期 ２００７—０８—０３ 作者简介：方元康（１９６８一），男，讲师，合肥工业大学在读硕士研究生，研究方向：数据挖掘。 １１８９ 维普资讯 http://www.cqvip.com ＼ 数据库及信息管理。 描中就可减少要进行扫描的事务集的个数 这个就是Ａｐｒｉｏｒｉｔｉｄ的 基本思想 ． 本栏目责任编辑：闻翔军 聚类分析的的类型和代表算法主要有： Ｋ均值是一种基于划分的聚类算法．它需要指定聚类个数Ｋ 和Ｋ个初始点，通过平方差指标找出Ｋ个聚类．但有时为了减少 平方差会将一个大的聚类为几个小的聚类 即使进行了优化．但是Ａｐｒｉｏｒｉ算法一些固有的缺陷还是无法 克服。第一，可能产生大量的候选集 当长度为ｌ的频集有１００００ 个的时候，长度为２的候选集个数将会超过１０Ｍ 还有就是如果 要生成一个很长的规则的时候，要产生的中间元素也是巨大量 的。第二，可能需要重复扫描数据库．通过模式匹配检查一个很大 的候选集。第三．无法对稀有信息进行分析 为了解决这些问题 采用了一种ＦＰ－Ｇｒｏｗｔｈ的方法 它采取了分治策略 这种方法对 于挖掘长的和短的频繁模式．它都是有效和可以伸缩的．并比 Ｃｕｒｅ是一种自底向上的层次聚类算法．它用一定数量的记录 来代表一个类，然后将它们缩为类的中心。在每一步。那些有最大 相似度的聚类被合并，直到聚类的个数为ｋ Ｃｕｒｅ算法能够挖掘 任意形状的聚类 Ｄｂｓｃａｎ是一种基于密度的聚类算法。其基本思想是对于一个 聚类中的每一个对象。在其给定半径的领域中包含的对象不能少 Ａｐｒｉｏｒｉ算法快了一个数量级 ３分类和预测 分类就是预测分类标号（或离散值）。根据训练数据集和类标 号属性，构建模型来分类现有数据，并用来分类新数据。预测就是 建立连续函数值模型，比如预测空缺值。数据分类有两步过程，第 一步，建立～个模型。捕述预定数据类集和概念集。第二步。使用 模型，对将来的或未知的对象进行分类．首先评估模型的预测准 确率．对每个测试样本，将已知的类标号和该样本的学习模型类 预测比较．模型在给定测试集上的准确率是正确被模型分类的测 试样本的百分比．测试集要于训练样本集．否则会出现“过分 适应数据”的情况 ３．１判定树归纳分类 用判定树归纳分类。类似于流程图的树结构．每个内部节点 表示在一个属性上的测试。每个分枝代表一个测试输出．每个树 叶节点代表类或类分布 判定树的生成由两个阶段组成．首先要 构建判定树．开始时，所有的训练样本都在根节点递归的通过选 定的属性，来划分样本（必须是离散值）；其次，要进行树剪枝，许 多分枝反映的是训练数据中的噪声和孤立点．树剪枝试图检测和 剪去这种分枝。通过将样本的属性值与判定树相比较．对未知样 本进行分类 ３．２贝叶斯分类 贝叶斯分类利用统计学中的贝叶斯定理．来预测类成员的概 率，即给定一个样本．计算该样本属于一个特定的类的概率。朴素 贝叶斯分类是假设每个属性之间都是相互的．并且每个属性 对非类问题产生的影响都是一样的 ３．３后向传播分类 后向传播是一种神经网络学习算法：神经网络是一组连接的 输入／输出单元．每个连接都与一个权相连 在学习阶段．通过调整 神经网络的权．使得能够预测输入样本的正确标号来学习 它的 优点是预测精度总的来说较高．健壮性好．训练样本中包含错误 时也可正常＿丁作．输出可能是离散值、连续值或者是离散或量化 属性的向量值．对目标进行分类较快。缺点是训练（学习）时间长． 蕴涵在学习的权中的符号含义很难理解．很难跟专业领域知识相 整合 ３．４预测和分类的异同点 预测是构造和使用模型评估无样本类．或评估给定样本可能 具有的属性或值空间。相同点是两者都需要构建模型．都用模型 来估计未知值．预测当中主要的估计方法是回归分析．有线性回 归和多元回归及非线性回归 不同点是分类法主要是用来预测类 标号（分类属性值）．预测法主要是用来估计连续值（量化属性 值）。‘ ４聚类分析， 聚类（簇）是数据对象的集合，在同一个聚类（簇）中的对象彼 此相似．不同簇中的对象则相异．聚类分析就是将物理或抽象对 象的集合分组成为由类似的对象组成的多个类的过程 聚类是一 种无指导的学习．没有预定义的类编号 聚类分析的数据挖掘可 以作为一个的工具来获得数据分布的情况．也可以作为其他 算法（如：特征和分类）的预处理步骤。 １ １９０ 电脑知识与技术 于某一给定的最小数目．然后对具有密度连接特性的对象进行聚 类。一个聚类能够被其中的任意一个核心对象所确定 Ｄｂｓｃａｎ算 法可以挖掘任意形状的聚类，对数据输入顺序不敏感．并且具有 处理异常数据（噪声）的能力 Ｃｌｉｑｕｅ是一种基于网格和密度的聚类算法．由于把数据空问 划分为网格，所以算法效率高，可以处理高维数据。但在划分网格 时没有或者很少考虑数据的分布，而且用一个网格内的统计信息 来代替该网格内的所有点．从而降低了聚类质量 评判聚集算法好坏的标准有：能够适用于大数据量和不同的 数据类型，能够发现不同形状和类型的聚集：对领域知识的要求 尽量少；对噪声或数据不同的顺序不敏感：模型可解释。 ５数据挖掘的发展前景 近几年对于数据挖掘的研究发展很快．预计在未来若干年． 研究还会形成更大的高潮。研究的总体发展方向可能会集中到以 下几个方面。 ５．１专业开发语言出现 研究专门用于知识发现的数据挖掘语言。并使其走向形式化 和标准化。 ５．２寻求数据挖掘过程中更优秀的可视化方法 实现在知识发现的过程中进行人机交互．图文数并茂．便于 知识发现的过程能够很容易的被用户理解 ５．３研究基于网络环境下的数据挖掘技术 特别是在因特网上建立ＤＭＫＤ服务器．并且与数据库服务器 配合，实现网络（远程）数据挖掘。 ５．４加强对各种非结构化数据的开采 如对图形数据、视频图像数据、声音数据乃至综合多媒体数 据的开采．这些数据类型或者比较复杂．或者是结构比较独特 为 了处理这些复杂的数据．就需要一些新的和更好的分析和建模方 法．同时还会涉及到为处理这些复杂或独特数据所做的费时和复 杂数据准备的一些工具和软件 ５．５挖掘软件的适用性更加灵活 如果一次挖掘不能实现相应的目标，可以进行交互式、动态 性、分层挖掘等．即交互挖掘技术的发展 ５．６出现功能较强大的专用数据挖掘软件 就目前来看．将来的几个热点发展方向包括网站的数据挖 掘、生物信息或基因的数据挖掘及其文本的数据挖掘等．这些领 域具有独特的数据性质．需要由独特的专用软件来支持 ５．７空间数据挖掘（Ｓｐａｔｉａｌ Ｄａｔａ Ｍｉｎｉｎｇ）将有所突破 在ＳＤＭ的理论和方法方面。重要的研究方向有：背景知识概 念树的自动生成、不确定性情况下的数据挖掘、递增式数据挖掘、 栅格矢量一体化数据挖掘、多分辨率及多层数据挖掘、并行数据 挖掘、新算法和高效算法的研究、空问数据挖掘查询语言、规则的 可视化表达等等。在ＳＤＭ系统的实现方面．要研究多算法的集 成、ＳＤＭ系统中的人机交互技术和可视化技术、ＳＤＭ系统与地理 信息系统、遥感解译专家系统、空间决策支持系统的集成等。研究 更有效的方法使挖掘过程中的数据更安全 总之．数据挖掘是一个很好的数据处理工具．但由于挖掘效 ． （下转第１１９９页） 维普资讯 http://www.cqvip.com 本栏目责任编辑：闻翔军 系统中定义字符集类型．方法如下： ￥ＮＬＳＬＡＮＧ＝“ｓｉｍｐｌｉｉｆｅｄ ｃｈｉｎｅｓｅ＂ｃｈｉｎａ．ｚｈｓｌ６ｇｂｋ ＿＿・・ ・・・数据库及信息管理・ ＵＳ７ＡＳＣＩＩ是截然不同的两种字符集。在字符集ＺＨＳ１６ＧＢＫ的数 据库中．可以查询到英文，但在ＵＳ７ＡＳＣＩＩ字符集的数据库中的中 文会出现乱码 Ｏｒａｃｌｅ８ｉ、Ｏｒａｃｌｅ９ｉ支持Ｕｎｉｃｏｄｅ ３．０标准，支持Ｕｎｉｃｏｄｅ编码 ￥ｅｘｐｏ￣ＮＬＳ＿ＬＡＮＧ 在ＷｉｎｄＯＷｓ中．决定客户端字符集的参数ＮＬＳ ＬＡＮＧ被定 义在Ｗｉｎｄｏｗｓ系统的注册表里 如果要重新定义，可以直接修改 注册表。 如果要将界面修改为英文，ＮＬＳＬＡＮＧ的取值为： —的数据库字符集类型有ＵＴＦ８、ＡＬ３２ＵＴＦ８、以及ＵＴＦＥ，优先使用 ＵＴＦ８。这样．在同一台服务器中可以存储不同类型语种的语言，读 取不同的语言使用不同字符集的客户端即可．这种应用系统特别 适用于国际多语种的环境 ＡｍｅｒｉｃａｎＡｍｅｒｉｃａ．ＵＳ７ＡＳＣＩＩ ＿Ｂ、字符集转换实例 在Ｏｒａｃｌｅ中．一些不同的字符集是允许进行转换的．同时存 在多语种字符集的问题．允许在同一数据库中使用不同字符集的 语种。下面分别说明几种使用不同字符集数据库的案例。 案例一、单一字符集数据库系统： 这种应用系统的结构如图１所示．服务器与客户端的字符集 相同，这种字符集的使用是典型的数据库应用类型。当然．这里也 允许使用ＮＬＳ１６ＣＧＢ２３１２８０字符集．这两种字符集维持兼容。 ■ Ｕｎｉｘ （ＺＨＳ１６ＧＢＫ－） 图１单一字符集数据库 Ｕｎｉｘ Ｕｎｉｘ （ＺＨＳ１６ＧＢＫ）（ｕｓ７ＡＳＣＩＩ） 图３不同字符集不可相互转换 ３修改数据库核心字符集 在实际中．如果数据库核心字符集在安装时选择错误．则必 须修改．否则将来汉字的显示会出现乱码。要改变数据库核心字 需要说明的是．数据库核心字符集与服务器操作系统的语 种是没有关系的．也就是说，在英文的操作系统中可以存储中文． 在中文操作系统的数据库中也可以存储日文．只要将字符集参数 设置正确就可以了 符集，一种方法是重新安装数据库．另外一种方法则是修改字符 集 重新安装数据库自然可以．这里不必赘述．下面说明如何修改 核心字符集 ‘ 在Ｏｒａｃｌｅ８ｉ、Ｏｒａｃｌｅ９ｉ中．可以通过修改系统数据字典ｐｒｏｐｓ￥直 接修改数据库核心字符集．将参数ＮＬＳ ＣＨＡＲＡＣＴＥＲＳＥＴ的列值 改为所需要的字符集类型，修改后重新启动数据库即可。例如： 案例二、单一字符集三层数据库系统结构： 图２是基于Ｏｒａｃｌｅ数据库的三数据库应用层结构 在数据库 服务器、以及应用服务器中使用了相同的字符集ＺＨＳ１６ＧＢＫ．这 是最为理想的状况．服务器之间不存在字符集转换问题 ＳＱＬ＞ｕｐｄａｔｅ ｐｒｏｐｓ￥ ２＞ｓｅｔ ｖａＩｕｅ￥＝ ＨＳｌ６ＧＢＫ ３＞ｗｈｅｒｅ ｎａｍｅ＝ ＮＬＳＣＨＡＲＡＣＴＥＲＳＥＴ ： ＿在Ｏｒａｃｌｅ数据库中．客户端字符集必须与数据库核心字符集 类型一致，否则汉字将出现乱码：如果要将早期数据库中的数据 。 移入到Ｏｒａｃｌｅ８ｉ、Ｏｒａｃｌｅ９ｉ中，由于原始数据字符集问题，新的数据 库核心必须使用早期数据库核心字符集类型．客户端也要保持与 早期核心字符集一致。这种使用方式不存在字符集转换问题。 Ａｐｐｌｉｃａｔｉｏｎ ， 浏览器 Ｓｅｒｖｅｒ 参考文献： 【１】滕永昌．Ｏｒａｃｌｅ数据库系统管理（上、下册）【Ｍ】．北京：清华大 学出版社．２００３． （ＺＨＳＩ６ＧＢＫ） 图２单一字符集三层结构 案例三、不同字符集不可以相互转换： 对于图３的情况，字符集是不能相互转换的，ＺＨＳ１６ＧＢＫ与 『２］Ｋｅｖｉｎ Ｌｏｎｅｙ．Ｏｒａｃｌｅ９ｉ ＤＢＡ手册『Ｍ１．北京：机械工业出版社， ２Ｏ０３． （上接第１１９０页） 【２】朱玉全，杨鹤标，孙蕾，著．数据挖掘技术【Ｍ】．东南大学出版 社２００６．１１． 果不能预期，受到许多诸如数据、工具、技术人员水平等因素影 响。所以数据挖掘的成功要求对期望解决问题的领域有深刻的了 解，理解数据，了解其过程，才能对数据挖掘的结果找出合理的解 释。数据挖掘虽然是近年来计算机领域的研究热点，但客户的行 为是与社会环境相关联的．数据挖掘本身也受社会背景的影响 【３］Ｐａｎｇ—Ｎｉｎｇ Ｔａｎ Ｍｉｃｈａｅｌ Ｓｔｅｉｎｂａｃｈ Ｖｉｐｉｎ Ｋｕｍａｒ著范明范 宏建等译数据挖掘导论『Ｍ１．人民邮电出版社。２００６．５． 【４】陈安，陈宁，等著．数据挖掘技术及应用【Ｍ】．科学出版社， ２００６＿３． 所以挖掘的结果没有人们想象那样的神秘．它不可能是完全正确 的。比如说，在美国对银行信用卡客户信用评级的模型运行得非 常成功，但是，它可能 不适合中国。要得到一个较好的数据挖掘结 果需要结合各方面的专业知识和不同领域的专家合作．这也是目 前研究正在探讨的问题 『５］Ｒｉｃｈａｒｄ Ｊ．Ｒｏｉｇｅｒ Ｍｉｃｈａｅｌ Ｗ．Ｇｅａｔｚ著数据挖掘基础教程 『Ｍ１．清华大学出版社，２００３．１２． 【６】石纯一，黄昌宁，等著．人工智能原理【Ｍ】．清华大学出版社 ２００３．５． 『７］Ｉａｎ Ｈ．Ｗｉｔｔｅｎ Ｅｉｂｅ ＦｒａＪ１ｋ．著，董琳，邱泉，王晓峰，吴韶群，孙立 骏，译．数据挖掘实用机器学习技术『Ｍ１．机械工业出版社２００６．２ 『８１郑新奇．数据挖掘软件现状特点与发展趋势ｈｔｔｐ：／／ｗｗｗ．ｐａ． ｐｅｒ．ｅｄｕ．ｃｎ ２００５．６．１ ３ 参考文献： 『ｌ￣ａｎｗｅｉ Ｈａｎ ａｎｄ Ｍｉｃｈｅｌｉｎｅ Ｋａｍｂｅｒ，著，范明，孟小峰，等译．数 据挖掘概念与技术『Ｍ１．机械工业出版社２００７＿３． １１９９
