数据挖掘技术综述

2008年第6期牡丹江教育学院学报N o．6，2008 (总第112期)J ouR N A L oF M uD A N J I A N G co L L E G EoF E D ucA T I oN s e“aI N o．112数据挖掘技术综述高翔侯小静(洛阳理工学院，河南洛阳471003)[摘要]在对数据仓库与数据挖掘的概念及数据挖掘的功用与分类进行介绍的基础上．阐述了串行关联规则算法和并行关联算法的目标与内容．详细分析了A pr i or i算法、神经网络、遗传算法等数据挖掘算法。

[关键词]数据挖掘f关联规则I apr i ori算法；神经网络l遗传算法[中图分类号]T P31[文献标识码]A[文章编号]1009—2323(2008)06一0109一02数据挖掘是信息技术自然进化的结果。

自上世纪六十年代以来，信息技术已经从原始的文件处理发展到复杂的、功能强大的数据库系统。

而数据仓库是近年来数据库研究领域中迅速发展起来的新技术。

利用数据仓库技术可以将现实中的海量数据存放在异构的数据库中。

为了从数据中有效地提取和发现知识．需要对数据仓库中存储的数据进行“挖掘”。

数据挖掘是从大量数据中抽取出未知的、有价值的模式或规律等知识的复杂过程。

数据挖掘技术由数据清理、数据集成、数据选择、数据交换、数据挖掘、模式评估六个步骤组成。

通过这六个步骤的提纯与处理向用户提供有价值的信息。

数据挖掘提供的数据模式有概念描述、关联规则、分类与预测、聚类分析、异类分析、演化分析等六类。

1．数据仓库与数据挖掘数据仓库系统在数据分析和决策方面为用户和“知识工人”提供服务。

这种系统与传统的联机事务处理(0L TP)系统不同．它可以用不同的格式组织和提供数据，以满足不同用户的形形色色需求．这种系统称为联机分析处理(oL A P)系统。

数据仓库和oL A P工具均基于多维数据模型．这种模型可以以星形模式、雪花模式或事实星座模式等形式存在。

星形模式是最常见的．其数据仓库包括一个大的、饱含大批数据、不含冗余的中心表(实事表)和一组附属表(维表)。

在星形模式中．每维只用一个表表示，每个表包含一组属性；雪花模式是星形模式的变种，其中某些维表是规范化的，故而把数据进一步分解到附加的表中。

雪花模式和星形模式的主要不同在于：雪花模式的维表可能是规范化形式．便于维护并节省存储空间，但是由于执行查询操作需要更多的连接操作，故而雪花结构可能降低浏览的性能导致系统性能也会受到一定影响。

事实星座模式可以看作是多个星形模式的集合．需要多个事实表共享维表。

从结构的角度看．数据仓库模型分为企业仓库、数据集市和虚拟仓库。

数据仓库和数据集市已在广泛的应用领域使用．从最初的应用于产生报告和回答预先定义的查询发展到现在已经用于知识发现，并使用数据挖掘工具进行决策。

在这种意义下．数据仓库工具可以分为存取与检索工具、数据库报表工具、数据分析工具和数据挖掘工具。

在此基础上信息处理与分析和数据挖掘的概念基本分离。

数据挖掘不限于分析数据仓库中的数据．也可以分析事务的、文本的、空间的和多媒体数据。

数据挖掘所能发现的知识有如下几种：广义型知识，即反映同类事务共同性质的知识；特征型知识．即反映事务各方面的特征的知识；差异型知识。

即反映不同事务之间属性差别的知识；关联型知识。

即反映事务之间依赖或关联的知识；预测型知识，它根据历史和当前的数据推测未来数据l 偏离型知识，用于揭示事务偏离常规的异常现象。

这些知识都可以在不同的概念层次上被发现，随着概念的提升．从微观到宏观．以满足不同用户、不同决策的需要。

至于数据挖掘的工具和方法常用的有分类、聚类、减维、模式识别、可视化、决策树、遗传算法、不确定性处理等。

从l EE E t r ans ac t i or L s o n kno w I edge and da t a engi neer．i ng以及A C M SI G M O D I nt l．C onf．M a na gem e nt of D a t a 近年来的文献中可以看出．除了不断地提出一些新的挖掘技术外。

大量的有关D M的文章集中讨论了如何提高D M 系统，尤其是关联规则挖掘的性能，这包括算法的有效性、可伸缩性和并行处理。

另外，复杂数据类型挖掘已经是一个发展迅速的热点研究领域。

复杂数据挖掘包括复杂数据对象的多维分析．空间数据挖掘，时序数据和其他与时间相关的数据挖掘、文本挖掘以及w eb挖掘等。

2．数据挖掘的关联规则算法研究2．1串行关联规则算法数据挖掘的一个重要任务是从事务数据库中发现关联规则。

其中每个事务都包括一个项目集．由于事务的数据库通常都饱含大量不同的项目，因此候选集的总数很大，所以当前的关联规则发现技术都是通过要求满足一个最小支持度以尽量减小搜索空间。

A pr i or．算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。

它将发现关联规则的过程分为两个步骤t 第一步．通过迭代检索出事务数据库中的所有频繁项集，即支持度不低于用户设定的阈值的候选集；第二步．利用频繁项集构造出满足用户最小信任度的规则t对于每个频度项目集L，产生它的所有非空子集S，对L的每个非空子集S，如果满足兰器茜乏渊≥mI-Lco挖，'贝Ⅱ输出相关规则s 一(L—S)。

图l给出了A pr i or i算法及其相关过程的伪代码。

由图所述，A pr i or Lgen完成两个动作：连接和剪枝。

在连接部分．L I一-与LI一，连接可能的候选．剪枝部分使用A pr i or i性质删除具有非频繁子集的候选集．非频繁子集的测试在过程has-i nf requer屯s ubs et中．1．Fl={f r equent l一i t em se t s}I2．F0r(k=2}R一1≠口Ik+十){3．C k=apri ot gen(Fk一1)[收稿日期]200—03一04[作者简介]高翔(198l一)。

女．河南洛阳人．洛阳理工学院助教．中国人民大学软件与理论专业在读硕士研究向为挖掘；侯小静(1975一)，女，河南洛阳人．洛阳理工学院讲师，硕士，研究向为计算机应用．1094．F or al l t讯n s act ions t∈T l‘5．Su bse t(Ck．t)6．For∞ch∞nd谴8t e c∈C k7．C count++I8．}9．F k={c∈Ckl ac ount≥m i ns up}10．'11．F=U Fkpf oce dur e apr i or L ge n()1．f or∞ch i t em s et f1∈R—I2．fo r each i t em s et f2∈Fk一13．i f(f1[1]；f2[1])^(f1[2]=fz[2])^K^(n[k一1]=f2[k 一1]){4．c2f1∞f2l5．i f(has_i nf f equen L3ubset(c．R—I))del e te c6．e l s e add ct o C k}7．f et ur n C kpr oce dur e has—i nf requent—s ub s et()1．fo r ea ch(k一1)一5ub8e t8of c2．i f s芒R—lr e t um T R U E I3．e ls e r e t ur n F A LS E I图l A pr i or．算法在算法的整个计算过程中，计算候选项目集的数目所花费的时间代价很高．在剪枝步骤中的每个元素都需要在交易数据库中进行验证来决定其是否加入，此过程是算法性能的一个瓶颈．可能产生大量的候选集以及可能需要重复扫描数据库．是A pr i or i算法的两大缺点。

为了提高效率．算法将所有大小为K的潜在频繁项集组织成一个哈希树，算法不需要事务驻留在主存中，但哈希树必须在主存中。

如果哈希树太大不能全部放在主存中．则哈希树需要被划分。

大量数据需要在各个事务数据库之间传递(对哈希树的每个分块)。

在A pr i o“算法之后又出现了许多其他算法，包括D H P(di r ec t has hi ng and pr uni ng)算法、投影树算法、Panit i on算法、基于抽样的算法、D I C(D ynam i c l t em—s et Count—i ng)算法以及基于FP—t r ee的算法。

所有这些算法都以某种方式利用了项目集支持度的单调性，即大小为k的项目集是频繁的，当且仅当其所有的大小为k一1的子集是频繁的。

本质上上述的所有算法都是遍历项目集，如何利用其单调的特性导致了遍历方式的不同，从而带来了效率的不同。

这些算法的另一不同之处在于其处理事务数据库的方式的不同．即对整个数据库遍历的次数以及在每次遍历的过程中如何减少处理后的数据规模．2．2并行关联规则算法无论上述何种串行关联规则算法都存在共同的缺陷：对数据库进行多次扫描．可能产生大量的候选集．占用大量的系统资源．针对这些不足，提出了很多关联规则的并行算法。

并行算法是一些可同时执行的进程的集合，这些进程相互作用可协调，以完成对一个问题的求解。

并行算法的目标是尽可能减少时间复杂性，为达到这个目的，要尽量使每个时刻可独立执行的计算任务增加，使整个算法的计算步数尽量减少。

或者说通过增加每个时刻步的算法复杂性来减少整体的时间复杂性，适当增加空间复杂性来减少时间复杂性．并行算法主要有以下几类：数值并行算法。

主要为数值计算而设计的算法I非数值并行算法，如神经网络算法、演化算法、遗传算法以及为符号计算而设计的并行算法；同步并行算法要求所有进程必须在一个给定时刻同步I异步并行算法是指诸进程执行相对独立，不需互相等待的一类并行算法1分布式算法是指由包括网络在内的通信链路连接的多节点或计算机群协同完成某个计算任务的算法。

神经网络是一种并行智能计算模型，由具有可调节权值的阀值逻辑单元组成，通过不断调节权值，直至动作计算表现令人满意来完成学习．神经网络具有较强的学习能力，可根据一定的学习算法自动地从训练实例中学习。

神经网络具有如下几个优点：可以充分逼近任意复杂的非线性关系l信息是分布储于网络内的神经元中，故具有较强鲁棒性和容错性l采用并行处理，计算速度较高；具有自学习和自适应能力，可以处理不确定或不知道的系统；具有很强的信息综合能力，能同时处理定量和定性的信息。

能很好地协调多种输人信息关系，适用于信息融合和多媒体技术。

遗传算法是模仿生物遗传与进化过程而得出的一种随机优化方法．在一般情况下，遗传学习首先创建一个由随机产生的规则组成的初始群体。

每个规则可以用一个二进制位串表示。

根据适者生存的原则．形成由当前群体中最适合的规则组成新的群体以及这些规则的子女。

规则的适合度用它对训练样本集的分类准确率评估．子女通过使用诸如交叉和变异等遗传操作来创建。