一个面向大规模数据库的数据挖掘系统钱卫宁Word文件下载.docx
《一个面向大规模数据库的数据挖掘系统钱卫宁Word文件下载.docx》由会员分享，可在线阅读，更多相关《一个面向大规模数据库的数据挖掘系统钱卫宁Word文件下载.docx（16页珍藏版）》请在冰点文库上搜索。
挖掘、增量挖掘.
（5）作为一个支持决策分析的系统,其使用者不是计
算机工作者,而是决策者,系统应该提供友好的界面.
1.2功能模块
1.2.1挖掘操作模块
不同的挖掘操作模块负责不同的数据挖掘操作.它们彼此之间相对独立,共同之处是都受到挖掘库管理模
块的管理,通过存储控制模块获得数据,并把结果写入挖掘库.在下一节里我们将详细介绍各个操作模块.
1.2.2数据预处理模块
数据预处理模块的主要功能是定义数据源、格式化数据源以及过滤数据源.该模块对整个系统的可用性非
常重要,它可以分为以下几个子模块:
•数据映射.将源表中的数据映射成ID形式,并生成对照表（ID和原始值的对照）.此功能的目的是把不同形
式的数据映射成统一的、可供挖掘模块操作的形式.
•类型映射.对源表中所列数据类型进行强制类型转换.之所以需要这个功能,是因为在数据库中不同的数
据类型很多,数据挖掘算法只支持其中最基本的几种.
•列映射.该子模块从源表中提取所需要的列,以减少数据量,提高系统的效率.
1.2.3存储控制模块
系统假设数据源存放在数据库中,由存储控制模块对数据库统一进行操作.对于存放在外部文件中的数据,
需要使用数据库管理系统提供的导入工具把数据导入数据库以后再进行挖掘操作.当前,系统的数据源存放在
DB2UDB5.2中,从可移植性的角度考虑,我们使用ODBC作为底层的接口.我们对存储控制的封装高于ODBC
对存储控制的封装,这是因为数据挖掘应用不同于一般的数据库应用程序,它对数据库的访问频繁,而每次对数
据库的访问都会耗费一定的时间和资源.对于数据挖掘操作来说,对大数据量的处理能力和处理效率是一个根
①界面,②挖掘操作模块,③挖掘库管理模块,④数据
预处理模块,⑤挖掘库,⑥存储控制模块,⑦数据库,
⑧外部文件.
Fig.1Systemarchitecture
图1系统框架
ControlflowDataflow
Data
④
preprocessing
Interface
①
Miningbase
③
management
⑤
Storagemanagement
⑥
Miningoperations
②
Database
⑦
Flatfiles
⑧
一个面向大规模数据库的数据挖掘系统1543
2系统功能
2.1数据准备
2.1.1泛化
泛化就是将相关数据或概念泛化到更高级的层次上.本系统集成的泛化算法是GDBR
[1]
.该算法的特点是:
对比其他算法（如LCHR,AOG等）,它有最好的时间复杂度O（n）以及很好的空间复杂度O（c）.
2.1.2数据清洗
数据清洗的主要工作就是准确、高效地检测出数据库中的相似重复记录.系统使用一种基于N-Gram
[2]
的
检测相似重复记录的综合方法,能处理常见的拼写错误,如插入、删除、交换、替换和单词的交换等.为了消除
基本算法在检测精度上的一些不足,系统采用了经过改进的算法
[3]
在实现中运用了统计学原理较好地去除了
噪声,并综合应用了正向和逆向重复矩阵,提高了插入/删除错误的检测率.
2.2数据挖掘操作
2.2.1关联规则
关联规则发现可以分两步来完成:
找出所有的频繁项集;
由发现的频繁项集生成关联规则.在找出所有的频
繁项集时,系统实现了Agrawal等人提出的Apriori算法
[4]
.由频繁项集产生关联规则的基本思想是:
对于每一个
频繁项集l,找出l的所有非空子集a,如果support（l）/support（a）>
minconf,则输出规则a⇒（l−a）.系统对这种方法略
作改进:
如果频繁项集l的子集a不能产生出规则,则没有必要用a的子集来产生关联规则.
2.2.2例外规则
广义的关联规则可分为3类:
强规则、例外规则和随机规则.强规则（大部分数据服从的规则）可以帮助我们
预料将来的情况.然而在一些特定的场合,我们需要的不仅仅是预测,而是我们还不知道的知识.这时,我们更感
兴趣的是发现例外规则（小部分数据服从的高可信度规则）
[5]
.
设I为数据集D中的所有记录,Y为属性集.对于分类关联规则（CAR）X⇒y（X⊂I,y∈Y）,它在两种情况下会成
为虚假的规则（SCAR）:
一是若y的支持度大于X⇒y的支持度;
二是若X′⊆X且（X′⇒y）的支持度大于（X⇒y）的支
持度.若X⇒y为CAR,例外分类关联规则（ECAR）有如下的形式:
X,Z⇒
~
y,其中X,Z∈I,X∩Z=∅,
y,y∈Y,
y≠y.例外分
类关联规则的可信度满足最小可信度的设置,但支持度低于最小支持度的设置.
我们的例外规则挖掘模块包含3个子模块:
生成CAR、删除SCAR、生成ECAR.算法的细节请参见文献[5].
2.2.3时序模式
同关联规则一样,挖掘时序模式的问题也源于由销售记录组成的事务数据库D,但时序模式主要是对物品
（项）在时间上的关联性加以考虑.Golden-Eye系统集成的时序模式挖掘算法是Agrawal等人提出的AprioriAll
算法
[6]
关于算法的说明在此不作赘述.
2.2.4分类
分类的基本思想是:
根据一些已定义好类别的数据的信息,产生一个可以描述数据类别或对未知类别的数
据进行分类的分类器.本系统集成的分类算法最终生成的分类器被称为区间分类器（intervalclassifier）
[7]
.该算法
的特点在于与采用二叉树的决策树分类器相比,它的准确度较高,决策树的深度也不至于过深.
2.2.5考虑综合因素的聚类方法
系统集成的考虑综合因素的聚类方法
[8]
吸收了一些现有聚类算法的优点,使用层次聚类方法的框架,综合
考虑簇之间的距离和簇中对象的密度来决定两个簇是否应该合并.它吸收了CURE算法中采用多个代表点来
表示簇的方法,因而能够有效地识别特殊形状的簇.为了增强处理大数据量的能力,在使用层次聚类法之前,算
法将对象所分布的数据空间划分成数据单元,计算统计信息后得到初始的簇.最后,算法利用索引对数据库中的
所有对象进行标记.该算法的主要步骤如下:
（1）取样;
（2）划分数据单元;
（3）消除噪声;
（4）利用距离和密度判
断、合并簇;
（5）识别outlier;
（6）标记数据.
1542JournalofSoftware软件学报2002,13（8）
本的问题,所以,由系统来进行缓冲和内存索引就非常重要.存储控制模块的功能主要体现在3个方面:
•对连接数据库、管理外部文件以及交换外部文件和内存的内容等较为底层的操作进行封装.
•负责缓冲管理.具体地说,该模块为数据源、数据挖掘中间结果以及挖掘结果分别申请缓冲区,并保证其
驻留在内存中.
•提供简单的数据格式转换.不同于数据预处理模块提供的数据格式转换,该功能主要弥补关系数据库不
能存储不规则格式数据的问题:
在向缓冲区中存放数据以前对事务记录进行重新拼接.
正是由于存储控制模块的存在,系统才获得了良好的可扩展性,各个算法的检测数据集规模都达到了
100000条以上,其中部分算法的检测数据集规模达到了1000000条.具体的实验数据参见相关论文.
1.2.4挖掘库及挖掘库管理模块
挖掘库和挖掘库管理是整个系统的核心部分.挖掘库是一个逻辑概念.一个挖掘库存放用户所指定的一系
列挖掘操作的所有信息.在系统中,所有的挖掘库都统一存放在数据库中,由系统统一管理.
挖掘库所保存的挖掘操作是指包括数据准备和数据挖掘在内的所有操作.在挖掘库中存放的这些操作信
息是有顺序的（用户进行这些操作的顺序）.这是因为一个数据挖掘操作在整个知识发现过程中往往不是孤立
的,它所使用的数据源常常是另一个数据挖掘操作的结果,而它的挖掘结果又有可能是其他操作的数据源.所
以,保留挖掘顺序实际上就是保留了挖掘操作之间的这种关系,这无论对用户理解挖掘结果还是以后重新进行
挖掘都是有帮助的.除了操作的名称和顺序以外,挖掘库还保存数据源信息、挖掘操作的参数设置以及挖掘的
结果.因此,我们的系统能够很方便地实现把一个挖掘操作的结果作为另一个挖掘操作的输入.
我们提供了一套管理挖掘库的操作,这些操作被封装成挖掘库管理模块.图形界面通过调用挖掘库管理模
块来完成对挖掘库的管理.同时,挖掘库管理模块通过调用各个挖掘操作模块来实现挖掘操作.管理挖掘库的所
有操作可以被分成以下4类.
•对挖掘库的操作.这组操作主要提供对挖掘库整体的管理.包括连接挖掘库、断开挖掘库、打开挖掘库、
增加挖掘库、存储挖掘库、删除挖掘库和查询挖掘库.任何对挖掘库的操作必须在打开了一个挖掘库以后才能
进行,而系统的任意运行时刻最多只能打开一个挖掘库.
•对数据源的操作.这组操作主要用于定义数据源.包括查询数据库信息、增加数据源、查询数据源信
息等.
•对挖掘操作的设置操作.包括增加挖掘操作、查询挖掘操作、设置挖掘操作参数、查询挖掘操作参数等.
•对挖掘结果的操作.系统实现了对挖掘结果的查询操作.
1.2.5界面
Golden-Eye提供API作为访问界面,并在此基
础上开发了图形界面.
系统的主图形界面采取类Explorer的风格.我
们使用不同形式的图形技术来表示不同形式的挖掘
结果.如图2所示为分类操作树型结果的图形界面.
目前,Golden-Eye所使用的图形界面及其针对的挖
掘操作如下:
•表格.泛化和数据清洗的结果显示.
•树型结构.决策树的显示.
•2维点/3维点.聚类结果的图形显示.
•文本.关联规则、例外规则以及时序模式的
显示.
Fig.2Thegraphicalinterfaceofthedecisiontree
andthebackground:
theGUIofthesystem
图2分类操作树型结果的图形界面以及类
Explorer风格的主图形界
1000-9825/2002/13（08）1540-06©
2002JournalofSoftware软件学报Vol.13,No.8
á
摘要:
数据挖掘融合了数据库技术、人工智能和统计学,是目前的研究热点.为了能够集成当前数据挖掘的主要
技术并使它们协同工作,在进行数据挖掘基本算法研究的基础上研制开发了一个数据挖掘系统——
Golden-Eye.系统实现了在数据挖掘研究中的一些最新成果,集成了泛化、数据清洗这两个数据准备操作以及关
联规则发现、例外规则发现、时序模式发现、分类器构造、聚类分析等基本数据挖掘操作,并实现了对挖掘操
作的基本管理和结果的图形化显示.整个框架设计充分体现了系统的完整性、协调性和高效性:
自底向上将存储
控制模块、数据预处理模块、挖掘操作模块、挖掘库管理模块有机地结合在一起,在底层实现了对包括中间结
果在内的数据的统一管理,在上层为用户提供了可视化的界面.实验结果表明,该系统能够在大规模数据库上成
功地完成用户所指定的数据挖掘操作.
关键词:
数据挖掘;
系统;
数据预处理;
存储控制;
挖掘库
中图法分类号:
TP311文献标识码:
A
数据挖掘（datamining）又被称作数据库中的知识发现（knowledgediscoveryindatabases）,是指从数据库或
数据仓库中提取隐含的、未知的和潜在的有用信息的非平凡过程.数据挖掘技术主要包括关联规则（association
rule）发现、分类（classification）、聚类（clustering）分析、泛化（generalization）和预测（prediction）等.当前,数据挖掘
的研究热点在于提高挖掘所得的知识的准确度和可理解性、提高数据挖掘操作的可伸缩性、集成数据挖掘操
作和现有的数据存储和分析工具等.此外,作为数据挖掘准备工作的数据离散化、数据变换、数据清洗（data
cleaning）和数据挖掘结果的可视化显示以及挖掘结果的评估等技术也属于数据挖掘研究的范畴.
虽然数据挖掘包含诸多方面的工作,但在实际运用中,这些方面的技术往往需要相互协作,共同完成某项挖
掘任务.这就需要数据挖掘工具能够集成各方面的技术,使它们能够协同工作,并统一管理各个挖掘步骤以及结
果.Golden-Eye系统就是为此目的而开发的.本系统具有如下特点:
•集成了泛化、数据清洗、关联规则发现、时序模式（sequentialpattern）发现、分类、聚类等多种基本数
据挖掘操作.
•集成了一些新的操作和新的算法,比如改进的DBSCAN聚类算法以及例外规则发现、数据清洗、类别
属性（categoricalattribute）聚类这些数据挖掘领域里较新的操作.
•能处理大规模的数据集,测试的最大记录数目达到了1000000条.
•在系统框架的设计上充分考虑到了系统的完整性、协调性和高效性.
收稿日期:
2001-04-05;
修改日期:
2002-01-24
基金项目:
国家自然科学基金资助项目（60003016）;
国家重点基础研究发展规划973资助项目（G1998030414）
作者简介:
钱卫宁（1976－）,男,浙江上虞人,博士生,主要研究领域为数据挖掘,聚类,Web数据管理;
魏藜（1978－）,女,江西南昌
人,硕士生,主要研究领域为数据挖掘技术;
王焱（1977－）,女,江苏镇江人,硕士,主要研究领域为数据挖掘,Web数据管理;
钱海蕾
（1977－）,女,上海人,硕士,主要研究领域为数据挖掘,聚类,Web数据管理;
周傲英（1965－）,男,安徽宣城人,博士,教授,博士生导师,主要
研究领域为Web数据管理,数据挖掘,Web搜索.
1544JournalofSoftware软件学报2002,13（8）
2.2.6改进的基于密度的聚类方法
本系统还包含了另一种聚类算法,即对DBSCAN算法
[9]
加以改进后得到的一种高效算法
[10]
.我们通过以下
3个方面对DBSCAN进行有效的改进:
首先使用快速算法.在选取下一步扩展的种子点时我们只选取具有代表性的一部分邻居对象,这样就提高
了算法的速度.
其次,用数据分区改进.根据数据空间的分布特性,将整个数据空间划分为多个较小的分区,然后分别对这
几个分区进行聚类,最后将各局部聚类进行合并.
最后,通过数据取样改进算法.对数据进行取样,并通过对取样数据的聚类计算来达到对整个数据库数据的
聚类.
3相关工作
国际上的一些数据挖掘研究者已经开发了一些集成的数据挖掘系统,例如DBMiner
[11]
QUEST
[12]
等,这些
系统大都是研究成果向产品的过渡.与这些系统不同,Golden-Eye致力于提供一个数据挖掘技术研究的试验平
台.一方面可以在集成的环境下对人工数据�l,�m;
�业+尝����������$���验平
一个面向大规模数据库的数据挖掘系统1545
[6]Agrawal,R.,Srikant,R.Miningsequentialpatterns.In:
ProceedingsoftheICDE.1995.3~14.
[7]Agrawal,R.,Ghosh,S.,Imielinski,T.,etal.Anintervalclassifierfordatabaseminingapplications.In:
ProceedingsoftheVLDB.
1992.560~573.
[8]Zhou,Ao-ying,Qian,Wei-ning,Qian,Hai-lei,etal.Ahybridapproachtoclusteringinverylargedatabases.In:
Proceedingsofthe
5thPAKDD.2001.519~524.
[9]Ester,M.,Kriegel,H.P.,Sander,J.,etal.Adensity-basedalgorithmfordiscoveringclustersinlargespatialdatabaseswithnoise.
In:
ProceedingsoftheKDD.1996.226~231.
[10]Zhou,Ao-ying,Zhou,Shui-geng,Cao,Jing,etal.ApproachesforscalingDBSCANalgorithmtolargespatialdatabases.Journalof
ComputerScienceandTechnology,2000,15（6）:
509~527.
[11]Han,J.,Fu,Y.,Wang,W.,etal.DBMiner:
asystemforminingknowledgeinlargerelationaldatabases.In:
KDD.1996.250~255.
[12]Agrawal,R.,Mehta,M.,Shafer,J.C.,etal.Thequestdataminingsystem.In:
ProceedingsoftheKDD.1996.244~249.
[13]Liu,Li-jun,Huang,Ya-lou,Xue,Bin,etal.Thedesignandimplementationofthedataminingprototypesystem:
RoboMiner.
ComputerSciences,2000,27（10）:
57~60（inChinese）.
[14]Shao,Hua,Wan,Jia-hua,Wang,Jian-hu,etal.Auser-centereddataminingtool:
openminer.ComputerSciences,
2000,27（10）:
68~72（inChinese）.
附中文参考文献:
[13]刘丽君,黄亚楼,薛彬,等.数据挖掘原型系统RoboMiner的设计和初步实现.计算机科学,2000,27（10）:
57~60.
[14]邵华,万家华,王剑虎,等.一个以用户为中心的数据挖掘工具:
OpenMiner.计算机科学,2000,27（10）:
68~72.
ADataMiningSystemforVeryLargeDatabases
QIANWei-ning,WEILi,WANGYan,QIANHai-lei,ZHOUAo-ying
（DepartmentofComputerScienceandEngineering,FudanUniversity,Shanghai200433,China）;
（LaboratoryforIntelligentInformationProcessing,FudanUniversity,Shanghai200433,China）
Abstract:
Dataminingisahotspotthatcombinesthetechniquesindatabases,artificialintelligenceand
statisticsareas.Onthebasisoftheresearchonsomedataminingalgorithmsandtheirimplementation,adata
miningsystem,Golden-Eye,isdevelopedtoincorporateprimarydataminingtechniquesandcoordinatetheir
operations.Astheintegrationofseveralexistingtechniquesincludingsomeimprovedalgorithmsaswellassome
newlyproposedoperationsindataminingarea,thesystemimplementsawidespectrumofdataminingfunctions
升级会员 