（测试计量技术及仪器专业论文）数据挖掘技术及应用研究.pdf

摘要 数据挖掘是一项较新的数据库技术，它基于由日常积累的大量数据所构成的 数据库，从中发现潜在的、有价值的信息称为知识，用于支持决策。数据挖 掘是一项数据库应用技术，存在广泛的实际应用需隶，因此，无论数挖掘的理论 研究，还是数据挖掘的应用实践，都是有意义的。关联规则挖掘是数据挖掘的重 要分支，已有一些较成功的算法。本文主要探讨数据挖掘的基本过程，并着重研 究关联规则的基本理论和算法以及编程实现。 本文首先对数据挖掘技术作一个全面的概述，然后介绍数据仓库的概念、结 构和架构的基本步骤，数据预处理的必要性和几种基本功能，之后探讨了关联规 则挖掘的基本算法和一个改进算法，并加以比较研究。然后是在d e l p h i 平台上 对关联规则的算法进行完全实现。对于每一主要步骤所用函数都给出算法和主要 代码。最后是一个关联规则挖掘在电厂中的应用实例，描述了该数据挖掘实现的 过程，最后给出试验数据结果。 关键字：数据挖掘，数据仓库，数据预处理关联规则 a b s t r a c t d a t am i n i n gi san e wt e c h n i q u ew h i c ha i m sa t d i s c o v e r i n gp o t e n t i a l a n dv a i u a b l ep a t t e r nt h a ti sc a l l e da s k n o w l e d g ef r o md a t a b a s e t h e k n o w l e d g ed i s c o v e r r e dc a nb eu s e df o rd e c i s i o n m a k i n g t o d a yd a t am i n i n g i sw i d e l yn e e n e di np r a t i c a lf i e l d ，t h e r e f o r ，e i t h e rt h et h e o r i c a lr e s e a r c h o rt h ep r a c t i c eo fd a t am i n i n gi s s i g n i f i c a t i v e ，m i n i n gf o ra s s o c i a t i o n r u l e si sai m p o r t a n tb r a n c ho fd a t am i n i n g s o m es u c c e s s f u la l g o r i t h mh a v e b e e nd i s c o r e di nt h i sf i e l d i nt h i sp a p e rt h eb a s i cp r o c e d u r eo fd a t a m i n i n g i sd is c u s s e d ，a n d m a i n l y t h eb a s i c t h e o r ya n d a r i t h m e t i co f a s s o c i a t i o nr u l e sa n dp r o g r a m m i n gw h i c hi m p l e m e n ta s s o c i a t i o nr u l e s i nt h i s p a p e r ，f i r s tg i v e aa l 卜a r r o u n d d e p i c t i o n a b o u tb a s i c p r o c e d u r eo fd a t am i n i n g ，t h e ni n t r o d u c eb a s i cc o n c e p ta n ds t r u c t u r ea n d b a s i cp r o c e d u r eo fc o n f o r m a t i o no fd a t aw a r e h o u s e ，n e c e s s a r i t ya n ds o m e b a s i cf u n c t i o no fd a t ap r e p r o c e s s i n g t h e ns t u d yb a s i ca r i t h m e t i ca n da n e wa r i t h m e t i co fa s s o c i a t i o na n dc o m p a r et h e m t h e ni m p l e m e n ta s s o c i a t i o n r u l e sw i t hp r o g r a n _ l 】n i n go nt h ed e l p h ip l a t f o r m ，a n dp r e s e n tt h ea r i t h m e t i c a n dm a i nc o d eo ff u n c t i o no fe v e r yi m p o r t a n tp r o c e d u r e i nt h el a s t ，a n a p p l i c a t i o ni n s t a n c eo fa s s o c i a t i o nr u l e s i np o w e rp l a n ti sp r e s e n t e d d e p i c t i n gt h ep r o c e d u r ef o ri m p l e m e n t i n gd a t am i n i n ga n dl i s tr e s u l td a t a o ft e s t k e y w o r d s ：d a t am i n i n g ，d a t a w a r e h o u s e ，d a t ap r e p r o c e s s i n g ，a s s o c i a t i o n r t i e s 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 研究生签名： 鲫z 讶日 l l 期：2 0 0 4 3 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位 论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人 电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论 文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包 括刊登) 授权东南大学研究生院办理。 研究生签名 翱签私期一悼s 东南大学硕士学位论文 第一章绪论 1 1 课题研究背景、研究现状、内容 1 1 1 、数据挖掘的产生 近十几年来，随着数据库系统的广泛流行以及计算机技术的快速发展，人们 利用信息技术生产和搜集数据的能力大幅度提高。千万个数据库被用于商业管 理、政府办公、科学研究和工程开发等，特别是网络系统的流行，使得信息爆炸 性增长。这一趋势仍将持续发展下去。大量信息在给人们带来方便的同时也带来 了一大堆问题：第一是信息过量，难以消化：第二是信息真假难以辨识；第三是 信息安全难以保证；第四是信息形式不一致，难以统一处理。面对这种状况，一 个新的挑战被提了出来：如何才能不被信息的汪洋大海所淹没，从中及时发现有 用的知识，提高信息利用率呢? 要想使数据真正成为个企业的资源，只有充分利 用它为企业自身的业务决策和战略发展服务，使决策建立在或者参考历史数据 基础上，而不是完全由领导者的直觉决定的，否则大量的数据可能成为包袱， 甚至成为垃圾。因此，面对“人们被数据淹没，人们却饥饿于知识”的挑战，新的 数据处理技术数据挖掘( d a t am i n i n g ) 技术便应运而生了。 面对海量的存储数据，如何从中发现有价值的信息或知识，成为一项非常艰 巨的任务。数据挖掘就是为迎合这种要求而产生并迅速发展起来的。数据挖掘是 指从大型数据库或数据仓库中提取出隐含的、先前未知的、对决策有潜在价值的 知识和规则。数据挖掘是数据库发展与人工智能技术相结合的产物，是目前国际 上数据库和信息决策领域的最前沿的研究方向之一，引起了学术界和工业界的广 泛关注。 l ，1 2 、数据挖掘的研究现状及应用 由美国人工智能协会主办的k d d ( 数据库中的知识发现，k n o w l e d g ed i s c o v e r 9 。 i nd a t a b a s e ，简称k d d ) 国际研讨会已经召开了1 2 次，规模不断壮大，研究重点 也逐渐从发现方法转向系统应用，并且注重多种发现策略和技术的集成，以及多 种学科之间的相互渗透。其他内容的专题会议也把数据挖掘和知识发现列为议题 之一，成为当前计算机科学界的一大热点。与国外相比，国内对d m k d 的研究稍晚， 没有形成整体力量。1 9 9 3 年国家自然科学基金首次支持我们对该领域的研究项 目。目前，国内的许多科研单位和高等院校竞相开展知识发现的基础理论及其应 用研究。 第一章绪论 随着数据挖掘理论的研究的发展其应用也越来越普及。数据挖掘可以应用在 各个不同的领域。电讯公司和信用卡公司是用数据挖掘检测欺诈行为的先行者。 保险公司和证券公司也开始采用数据挖掘来减少欺诈。医疗应用是另一个前景广 阔的产业：数据挖掘可以用来预测外科手术、医疗试验和药物治疗的效果。零销 商更多的使用数据挖掘来决定每种商品在不同地点的库存，通过数据挖掘更灵活 的使用促销和优惠卷手段。制药公司通过挖掘巨大的化学物质和基因对疾病的影 响的数据库来判断哪些物质可能对治疗某种疾病产生效果。发电厂使用数据挖掘 来进行电价、负荷预测及故障诊断等。 1 1 3 、课题内容 数掘挖掘的基本理论产生发展已有十几年的历时了，现阶段对数据挖掘的研 究重点如上所述也逐渐从发现方法转向系统应用。本文主要从中小型企事业单位 对数据挖掘应用的实现角度出发，首先对数据挖掘的基本概念、过程的阐述，然 后论述关联规则挖掘的理论方法，之后给出在d e l p h i 平台下的编程实现，并且 给出关联规则挖掘在电厂中的一个应用实例。 1 ，2 1 定义 1 2 数据挖掘概述 数据挖掘( d a t am i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的、 随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有 用的信息和知识的过程。简单的说就是从大量数据中提取或“挖掘”知识。这种 定义是把数据挖掘和数据库中知识发现( k n o w l e d g ed i s c o v e r y i nd a t a b a s e ) 看作类似的概念，是一种比较公认的定义，是一种广义的数据挖掘概念。本文中 的数据挖掘在不发生混淆的情况下一律取这种定义。 1 2 2 数据挖掘研究内容和本质 随着数据开采和知识发现( d m k d ) 技术研究逐步走向深入，数据挖掘和知识 发现的研究已经形成了三根强大的技术支柱：数据库、人工智能和数理统计。因 此，k d d 大会程序委员会曾经由这三个学科的权威人物同时来任主席。目前3 m k b 的主要研究内容包括基础理论、发现算法、数据仓库、可视化技术、定性定量互 换模型、知识表示方法、发现知识的维护和再利用、半结构化和非结构化数据中 的知识发现以及网上数据挖掘等。 2 东南久学预上学位论文 1 2 3 数据挖掘与传统分析方法的区别 数据挖掘与传统数据分析( 如查询、报表、联机应用分析) 的本质区别是数 据挖掘是在没有明确假设的前提下去挖掘信息、发现知识。数据挖掘所得到的信 息应具有先前未知、有效和实用三个特征。 先前未知的信息是指该信息是预先未曾预料到的，即数据挖掘是要发现那些 不能靠直觉发现的信息或知识，甚至是违背直觉的信息或知识，挖掘出的信息越 是出乎预料，就可能越有价值。在商业应用中最典型的例子就是一家连锁店通过 数据挖掘发现了小孩尿布和啤酒之间竟然有着惊人的联系。 1 2 4 数据挖掘组威部分 典型的数据挖掘系统具有以下主要成分( 如下图1 1 所示) ： 图1 1 典型的数据挖掘系统 l 数据库、数据仓库或其他信息库：这是一个或一组数据库、数据仓库、电 子表格或其他类型的信息库。可以在数据上进行数据清理和集成。 2 数据库或数据仓库服务器：根据用户的数据挖掘请求，数据库或数据仓库 服务器负责提取相关数据。 3 知识库：这是领域知识，用于指导搜索，或评估结果模式的兴趣度。这种 知识可能包括概念分层，用于将属性或属性值组成不同的抽象层。用户确信方面 的知识也可以包括在内。可以使用这种知识，根据非期望性评估模式的兴趣度。 领域知识的其他例子有兴趣度限制或阀值和元数据( 例如，描述来自爹个异种数 i 笙二皇箜笙 据源的数据) 。 4 数据挖掘引擎：这是数据挖掘系统的基本部分，由一组功能模块组成，用 于特征化、关联、分类、聚类分析以及演变和偏差分析。 5 模式评估模块：通常，此成分使用兴趣度度量，并与数据挖掘模块交互， 以便将搜索聚焦在有趣的模式上。它可能使用兴趣度阀值过滤发现的模式。模式 评估模块也可以与数据挖掘模块集成在一起，这依赖于所用的数据挖掘方法的实 现。 6 图形用户界面：本模块在用户和数据挖掘系统之间通信，允许用户与系统 交互，指定数据查询或任务，提供信息、帮助搜索聚焦，根据数据挖掘的中间结 果进行探索式数据挖掘。此外，次成分还允许用户流浪数据库和数据仓库模式和 数据结构，评估挖掘的模式，以不同的形式对模式可视化。 1 2 5 数据挖掘处理过程模型 从工程角度讲，数据挖掘是一个需要经过反复的多次处理过程。如同软件工 程在软件开发种的作用，数据挖掘处理过程模型为数据挖掘提供了宏观知道和工 程方法。合理的数掘挖掘处理过程模型能将各个处理阶段有机地结合在一起，知 道人们更好地开发和使用数据挖掘系统。 从数据挖掘进入工程应用领域起，就有人对数据挖掘地过程进行归纳和总 结，提出了不同地数据挖掘处理过程模型。其中u s a m am f a y y a d 、g r e g o r y p i a t e t s k y s h a p i r o 等人给出的多处理阶段模型是一种通用模型，也是最被广为 接受的一种模型，图1 2 所示的模型示意图在数据挖掘领域内被多次引用。 ： ： li 。二一。二。彗f_ _ h _ 一- _ * _ o - i - - j 图i2u s a m amf a y y a d 的数据挖掘多阶段处理过程模颦 在上述模型提出后也有人提出不同的数据挖掘过程模型，但是都有一个共同 点就是都要经过准备、预处理、算法设计、数据挖掘、后处理阶段。其中准备阶 4 争 价卤剥罐；：黼、辅 撰 - i i |氓目 帮。一 预辩姗 睫眄一 东南大学硕士学位论文 段包括问题定义、对象理解、数据收集等准备工作；预处理包括数据清理、压缩、 变换等；后处理包括结果解释、输出、评价、分析、使用等。 上述模型侧重于模型的通用性，它的特点是通用性强，每一阶段相对对立， 每个处理阶段有处理工具完成相应的工作。 1 2 6 数据挖掘一般方法概述 数据挖掘是多学科和多种技术交叉结合的新领域，它综合了机器学习、数据 库、专家系统、模式识别、统计、管理信息系统、基于知识的系统、可视化等领 域的有关技术、因而数据挖掘的方法是极其丰富的，下面列举若干较为典型的数 据挖掘方法_ 。具体使用时，可依据数据的特点及挖掘任务的不同采用不同的 方法。 l 概念描述( c o n c e p td e s o r i p t i o n ) 从数据分析的角度，数据挖掘可以分为两类：描述式数据挖掘和预测式数据 挖掘。描述式数据挖掘以简介概要的方式描述数据，并提供数据的有趣的一般性 质。预测式数据挖掘分析数据，建立一个和一组模型，并试图预测新数据集的行 为。 数据库通常存放大量的细节数据。然而，用户通常希望以简洁的描述形式观 察汇总的数据集。这种数据描述可以提供一类数据的概貌，或将它与对比类相区 别。此外，用户希望方便、灵活地以不同地粒度和从不同的角度描述数据集。这 种描述性数据挖掘称为概念描述。 2 关联分析( a s s o c i a t i o na n a l y s i s ) 关联规则挖掘发现大量数据中项集之间有趣的关联或相互联系。随着大量数 据不停的收集和存储，许多业界人士对于从他们的数据库中挖掘关联规则越来越 感兴趣。 3 聚类方法( c l u s t e r i n ga p p r o a c h ) 该方法是按一定的距离或相似尺寸将数据分成一系列相互区别的组，它不需 要背景知识而直接发现有意义的结构或模式。 4 决策树方法( d e c i s i o nt r e ea p p r o a c h ) 该方法是首先利用信息论中的信息增益寻找数据库中具有最大信息量的字 段，建立决策树的一个节点，再根据字段的不同取值建立树的各个分枝，然后在 每个分枝子集上分别递归上述过程，即可建立决策树。国际上最早和最有影响的 决策树方法是由q u i u l a n 研制的i d 3 方法。采用决策树，可以将数据规则可视化， 其输出结果也容易理解，决策树方法精确度比较高，同时系统也不需要长时间的 构造过程。 5 神经网络方法( n e u r a ln e t w o r ka p p r o a c h ) !簦二茎望笙 模拟人脑神经元方法，以m p 模型和h e b b 学习规则为基础，建立了三大类多种 神经网络模型：前馈式网络、反馈式网络、自组织网络。 6 粗糙集方法( r o u g hs e t sa p p r o a c h ) 在数据库中将行元素看成对象，将列元素看成属性( 分为条件属性和决策属 性) 。等价关系r 定义为不同对象在某个或几个属性上取值相同，满足等价关系的 对象组成的集合被称为等价关系r 的等价类。条件属性上的等价类e 与决策属性 上的等价类y 之间的关系分三种情况： ( 1 ) 下近似：y 包含e 。对下近似建立确定性规则。 ( 2 ) 上近似：y 和e 的交集非空。对上近似建立不确定性规则( 含可信度) 。 ( 3 ) 无关：y 和e 的交为空。无关情况不存在规则。 7遗传算法( g e n e t i ca i g o r i t h m s ) 模拟生物进化过程的算法，由繁殖( 选择) 、交叉( 重组) 、变异( 突变) 三个基 本算子组成。遗传算法已在优化计算、分类、机器学习等方面发挥了显著作用。 8 、模糊集方法( f u z z ys e t sa p p r o a c h ) 利用模糊集合理论，对实际问题进行模糊判断、模糊决策、模糊模式识别、 模糊簇聚分析。系统的复杂性越高，精确能力就越低，模糊性就越强。这是z a d a h 总结出的互克性原理， 9 、可视化方法( v i s u a l i z a t i o na p p r o a c h ) 拓宽了传统的图表功能，使用户对数据的剖析更清楚。例如，把数据库中的 多维数据变成多种图形，这对充分揭示数据的内涵、内在本质及规律起了很大的 作用。 6 东南大学硕士学位论文 第二章数据仓库及数据预处理 2 1 1 什么是数据仓库 2 1 数据仓库 数据仓库概念始于本世纪8 0 年代中期，首次出现是“数据仓库之 父”w i l l i a m h i n m o n 提出的，即“数据仓库是在企业管理和决策中面向主题的、 集成的、与时间相关的、不可修改的数据集合”。 由上面的定义，可以看出数据仓库有四个特点： ( 1 ) 面向主题的( s u b j e e t o r i e n t e d ) ：数据仓库是围绕应用而组织的，也就 是说它是面向一些主题的，如顾客，供应商、销售、产品等。数据仓库的关键是 决策者的建模与分析，以排除对决策无用的数据，提供针对特定主题的数据信息。 ( 2 ) 集成的( i n t e g r a t e d ) ：这是数据仓库最重要的特点。构造数据仓库的数 据来自不同的数据源，由于业务的原因这些数据可能来自不同结构的数据库中， 或者来自不同厂商的数据库，即异质的数据库。在这些异质数据库和异构数据库 中的数据输入到数据仓库中之前，必须先清洗数据，再进行数据集成以确保命 名约定、编码结构、属性度量等的一致性。 ( 3 ) 与时间相关的( t i m e v a r i a n t ) ：数据仓库以维的形式组织数据，时间维 是数据仓库中一个很重要的维。数据仓库中的数据周期要远远长于操作型系统中 的数据周期，操作型数据库中的时间周期一般为6 0 9 0 天。两数据仓库中数据的 时间周期通常是5 1 0 年。 ( 4 ) 不可修改的( n o n v o l a t i l e ) ：数据仓库物理地分离存放数据，这些数据源 于操作型数据库中的数据。与操作型数据库不同的是，对于面向应用的操作型数 据库需要对数据作频繁的插入、更新，而数据仓库中的数据操作仅限于作数据的 初始化装入和数据访问。 简而言之，数据仓库是一种语义上一致的数据存储，它实现决策支持的数据 模型，并且存放企业战略决策所需要的信息。数据仓库通常也被看作一种体系结 构，通过将异质和异构数据库中的数据集成在一起而构成。支持结构化的和专门 的查询、分析报告和决策制定。 技术上人们习惯于从工作过程等方面来分析，并按其关键技术部份分为数据 的抽取、存储与管理以及数据的表现等三个基本方面。 ( 1 ) 数据的抽取：数据的抽取是数据进入仓库的入口。由于数据仓库是一个 第二章数据仓库及数据预处理 独立的数据环境，它需要通过抽取过程将数据从联机事务处理系统、外部数据源、 脱机的数据存储介质中导入到数据仓库。数据抽取在技术上主要涉及互连、复制、 增量、转换、调度和监控等方面。数据仓库中的数掘并不要求与联机事务处理系 统保持实时同步，因此数据抽取可以定时进行，但多个抽取操作执行的时间、相 互的顺序、成败对数据仓库中信息的有效性则至关重要。 ( 2 ) 存储和管理：数掘仓库的真正关键是数据的存储和管理。数据仓库的组 织管理方式决定了它有别于传统数据库，同时也决定了其对外部数据的表现形 式。要决定采用什么产品和技术来建立数据仓库的核心，则需要从数据仓库的技 术特点着手分析。 ( 3 ) 数据的表现：数据表现实际上相当于数据仓库的门面，其性能主要集中 在多维分析、数理统计和数据挖掘方面。而多维分析又是数据仓库的重要表现形 式，近几年来由于互联网的发展，使得多维分析领域的工具和产品更加注重提供 基于w e b 前端联机分析界面，而不仅仅是在网上发布数据。 2 1 2 数据仓库中的几个概念 1 多维数据集 多维数据集是联机分析处理中的主要对象，是一项可对数据仓库中的数据进 行快速访问的技术。多维数据集是一个数据集合，通常由数据仓库的子集构造， 并组织和汇总成一个由一组维度和度量值定义的多维结构。 2 维度 维度是分类的有组织的层次结构，它描述数据仓库中事实数据表的数据。 3 数据集市 数据集市是指包含企业数据的一个子集，对特定用户有用，其范围限于选定 的主题例如一个移动通信企业的数据集市可能限定的主题是客户、服务、话费。 包括在数据集市中的数据通常是汇总的。实现数据集市的周期比较短，一般是数 以周计，而不是数以月计和数以年计。根据数据的来源不同，数据集市分为独立 的和从属的两类。在独立的数据集市中，数据来自一个或者多个操作系统和外部 信息提供者，或者来自在一个特定的部门或者地域局部产生数据。从属的数据集 市中的数据直接来自企业数据仓库。 在数据仓库的实施过程中，对于某些主题的业务分析问题，可能会按照主题 采用数掘集市的方式对数据进行迸一步的组织。所以在中央数据仓库的基础之上 根据分析需求创建相应的从属的数据集市。 从属数据集市的数据直接来自于中央数据仓库。采用这种方式，可以保持整 体数据的一致性。为一些访问数据仓库十分频繁的关键业务部门建立从属数据集 东南夫学硕士学位论文 市，可以较好的提高查询的反映速度。 数据集市的设计原则是首先建立中央的企业级数据仓库，存储详细数据，业 务用户可以根据自己的需要，从不同的角度对这些详细信息进行大量的分析，以 发现其中蕴涵的大量的商业价值。同时可以根据不同部门的业务需求，建立相应 的部门级的从属数据集市。 4 元数据 元数据是数据仓库中的一个重要方面。元数据是关于数据的数据，对数据的 结构、内容、键码、索引等等的描述。典型的元数据记录有：数据仓库表的结构， 数据仓库表的属性，数据仓库中的源数据，数据加入数据仓库时的转换记录、数 据模型、数据模型和数据仓库的关系，抽取数据的历史记录。 元数据类型按照元数据的使用情况和面向对象的不同，可以将元数据分为业 务元数据、技术元数据、操作元数据。 ( 1 ) 业务元数据 业务元数据用业务名称、定义、描述和别名来表示数据仓库和业务系统中各种 属性，直接供最终用户使用。业务元数据使最终用户能够更好理解、使用数据仓 库，成为最终用户在数据仓库中的业务地图。 ( 2 ) 技术元数据 技术元数据描述了源系统、数据转换、抽取过程、工作流、加载策略以及目标 数据库的定义等。技术元数据可供信息系统人员和一部分最终用户使用，用来进 行影响分析、变化管理、数据库优化、任务调度和安全管理等。 2 1 3 黼仓库的结构 数据仓库是存储数据的一种组织形式，它从传统数据库中获得原始数据，先 按辅助决策的主题要求形成当前基本数据层，再按综合决策的要求形成综合数据 层( 又可分为轻度综合层和高度综合层) ，随着时间的推移，由时间控制机制将当 前基本数据层转为历史数据层。数据仓库中数据的物理存储形式有多维数据库组 织形式( 空间超立方体形式) 和基于关系数据库组织形式( 由关系型事实表和维表 组成) 。 数据仓库系统( d w s ) 由数据仓库、仓库管理和分析工具三部分组成。数据仓 库的数据来源于多个数据源，包括企业内部数据、市场调查报告及各种文档之类 的外部数据。 数据仓库：包括对数据的安全、归档、备份、维护，恢复等工作，这些工作 需耍利用数据库管理系统d b m s ) 的功能。 仓库管理：在确定数据仓库信息需求后，首先进行数据建模，然后确定从源 9 一一一 一 查堕查兰堡兰兰垡堡茎 ( 联机分析处理o n l i n ea n a l y t i c a lp r o c e s s i n g ) 。 从数据仓库的构架和实施过程出发，数据仓库的构建可以分为以下几个步 骤： ( 1 ) 启动工程建立开发数据仓库工程的目标及制定工程计划。汁划包括数据 范围、提供者、技术没备、资源、技能、组员培训、责任、方式方法、工程跟踪 及详细工程调度等。 ( 2 ) 建立技术环境。选择实现数据仓库的软硬件资源，包括开发平台、d b m s 、 网络通信、开发工具、终端访问工具及其建立服务水平目标等。 ( 3 ) 确定主题进行数据建模。根据决策需求确定主题，选择数据源，对数据 仓库的数据组织进行逻辑结构设计。 ( 4 ) 设计数据仓库中的数据库基于用户的需求，着重于某个主题，r 丌发数据 仓库中的数据物理存储结构，即设计多维数据结构的事实表和维表。 ( 5 ) 实现数据转换程序。从源系统中抽取数据、清洗数据、一致性格式化数 据、综合数据、装载数据等过程的设计和编码。 ( 6 ) 管理元数据和定义元数据。即表示、定义数据的意义及系统各组成部件 之间的关系。元数据包括关键字、属性、数据描述、物理数据结构、源数据、映 射及转换规则、综合算法、代码、缺省值、安全要求、变化及数据时限等。 ( 7 ) 开发用户决策的数据分析工具。建立结构化的决策支持查询，实现和使 用数据仓库的数据分析工具，包括优化查询工具、统计分析工具、c s 工具、 o l a p 工具及其数据挖掘工具等，通过分析工具实现决策支持需求。 ( 8 ) 管理数据仓库环境。数据仓库必须像其它系统一样进行管理，包括质量 检测、管理决策支持工具及应用程序，并定期进行数据更新，使数据仓库正常运 行。 2 2 数据预处理 目前关于数据挖掘的研究工作很多，但大多着眼数据挖掘算法的探讨，而忽 略了对数据预处理的研究。由于数据挖捉算法对其处理的数据集合一般老s 有一定 的要求，如数据完整性好、数据冗余度小、数据属性之间的相关性小等。然而， 际系统中的数据一般都不具备上述要求。另外，海量的实际数据中无意义的成分 很多，严重影响了数据挖掘算法的执行效率：而且，由于其中的噪声干扰还会造 成挖掘结果的偏差。因此，如何对原始数据进行有效的预处理，已经成为数据挖 掘系统实现过程中的关键问题。 数据挖掘过程可粗略地理解为四部分：数据采集、数据预处理、数据挖掘、 以及结果的解释评估。数据预处理是其中的重要一环，是必不可少的。数据颈 第二章数据仓库及数据预处理 处理以领域知识作为指导，来组织原来的业务数据，放弃一些与挖掘目标不相 关的属性，提供高质量的数据，从而减少了数据挖掘的数据处理量，提高了挖 掘算法的效率，提升了数据挖掘的起点和知识的准确度。 2 2 i 数据的相关概念 数据逻辑上可以用一个二维表来表示，横向为元组( 记录、观察等) ，纵向为 属性( 变量、字段等) 。 数据属性般分为两种类型，离散型和连续型。离散型( d i s c r e t e ) 属性也被 称为符号的( s y m b o l i c ) 、名称的( n o m i h a l ) 、类别的( c a t e g o r i c a l ) 、定性的 ( q u a l i t a t i v e ) 、分类的( c l a s s ) ：连续型( o o n t i n u o u s ) 属性也被称为实数的 ( r e a l ) 、有序的( o r d e r e d ) 、数值的( n u m e r i c a l ) 、定量的( q u a n t i t a t i v e ) 、区间 的( i n t e r v a l ) 。许多数据挖掘算法对属性类型有明确的要求，这就要求在这两种 类型间进行转换。 元组中含有预测结果的属性或变量，称为依赖变量( d e p e n d e n t v a r i e s ) 、目 标变量( t a r g e tv a r i e s ) 。元组中用来生成预涩4 模型的属性或变量，称为独立变 量( i n d e p e n d e n t v a r i e s ) 、输入变量( 1n p u t v a r i e s ) 。 2 2 2 实际数据存在的问题 要使数据挖掘算法有效地挖掘出知识，就必须为它提供干净、准确、简洁 的数据。然而，从实际应用系统中收集到的原始数据通常存在以下几方弼的阚 题： 杂乱性。原始数据是从各个实际应用系统中获取的( 多种数据库、多种文件 系统) ，由于各个实际应用系统的数据缺乏统一标准和定义，数据结构也有较大 的差异，因此各系统间的数据存在较大的不一致性，往往不能直接拿来使用。重 复性。是指对于同一个客观事物在数据库中存在两个或两个以上完全相同的描 述。由于应用系统实际使用中存在的一些问题，几乎所有应用系统中都存在数据 的重复和信息的冗余现象。 不完整性。由于实际系统设计时存在的缺陷，以及一些使用过程中人为因素 所造成的影响，可能出现有些数据属性的值丢失或不确定的情况，还可能缺少必 需的数据而造成数据不完整。实际使用的系统中，存在大量的模糊信息，有些数 据甚至还具有定的随机性质。 东南大学硕士学位论文 2 2 3 数据预处理的基本功能 数据挖掘中的数据预处理，主要是接受并理解用户的挖掘要求，确定挖掘任 务，抽取与挖掘任务相关的数据源，根据领域知识中的约束规则对数据进行合法 性检查，通过清理和规约等操作，生成挖掘算法所需要的目标数据，即原始数据 经过处理后得到的二维表，横向为观察( 记录、元组) ，纵向为变量( 属性、字段) 。 它汇集了原始数据中与数据挖掘任务相关的所有数据的总体特征，是最原始的知 识模板。数据预处理应该包括以下几个方面的功能。 2 2 3 1 数据集成( d a t ai n t e g r a t i o n ) 数据集成主要是将多文件或多数据库运行环境中的异构数据进行合并处理， 解决语义的模糊性。该部分主要涉及数据的选择、数据的冲突问题、不一致数据 的处理以及冗余等问题。 由于数据可能来自多个实际系统，所以存在异构数据的转换问题。另外，多 个数据源的数据之间，还存在许多不一致的地方，如命名、结构、单位、含义等。 因此，数据集成并非是简单的数据合并，而是把数据进行统一化和规范化处理的 复杂过程。它需要统一原始数据中的所有矛盾之处，如字段的同名异义、异名圊 义、单位不统一、字长不一致等，从而把原始数据在最低层次上加以转换、提炼 和聚集，形成最初始的挖掘数据。在数据集成中还应考虑数据类型的选择问题， 应尽量选择占用物理空间较小的数据类型。如在值域范围内使用t i n y i n t 代替 i n t ，这对大规模数据集来说将大大减少系统开销。 冗余是一个重要问题。一个属性是冗余的，如果它能由另外的属性“导出”。 属性或维的不一致也可能导致数据集中的冗余。有些冗余可以被相关分析检测 到。例如，给定两个属性，根据可用的数据，可以分析度量一个属性能在多大程 度上蕴含另一个。属性a 和b 之间的相关性可由下式( 式2 1 ) 度量： ，。：圣丝二丝2 堡二墨2 ( 2 1 ) j f n 一、) o a 8 b 其中，n 是元组个数，爿和b 分别是a 和b 的平均值，6 一和6e 分别是a 和 b 的标准差。该值越大，一个属性蕴含另一个属性的可能性越大。因此，一个很 大的值表明a ( 或b ) 可以作为冗余而被去掉。盍口果结果等于0 ，则a 和b 是独 立的，他们之间不相关。 2 2 3 2 数据清洗( d a t ac l e a n i n g ) 数掘清洗是要去除源数据集中的噪声数据和无关数据，处理遗漏数据和清洗 第二章数据仓库及数据预娃理 脏数据，去除空白数据域和知识背景上的白噪声，考虑时间顺序和数据变化等。 主要包括噪声数据处理和缺值数据处理，并完成一些数据类型的转换。 处理空缺值可以有以下几种方法：1 忽略元组；2 人工填写空缺值：只适用 数据量不大的情况，否则该办法行不通；3 使用个全局常量填充空缺值：浚方 法尽管简单，但是一般不被推荐使用：4 使用属性的平均值填充：使用与给定元 组属同一类的所有样本的平均值；6 。使用最可能的值填充空缺值：可以用回归、 基于推导的使用贝叶斯形式化方法的工具和判定树归纳确定。 噪声是一个测量变量中的随机错误或偏差。数据含噪声( 具有不正确的属性 值) 可能有多种原因，例如设备故障、人或计算机错误输入、数据传输错误等。 平滑数据，去处噪声主要有以下几种方法：分箱、聚类( 后面详细讨论) 、回归 等。 数据清洗可以分为有监督和无监督两类。有监督过程是在领域专家的指导 下，分析收集的数据，去除明显错误的噪声数据和重复记录，填补缺值数据：无 监督过程是用样本数据训练算法，使其获得一定的经验，并在以后的处理过程中 自动采用这些经验，完成数据清洗工作。 2 2 3 。3 数据变换( d a t at r a n s f o r m a t i o n ) 数据变换主要是找到数据的特征表示，用维变换或转换方法减少有效变量的 数目或找到数据的不变式，包括规格化、归约、切换、旋转和投影等操作。 规格化指将元组集按规格化条件进行合并，也就是属性值量纲的归一化处 理。规格化条件定义了属性的多个取值到给定虚拟值的对应关系。数据规范化的 方法有许多种，例如：最小一最大规范化、z - s c o r e ( 或零一均值规范化) 、小数 定标规范化等。最大一最小规范化是对原始数据进行线性变换。假定m i n 。和m a 溉 分别为属性a 的最小值和最大值。该规范化通过计算 v ，= ! 二竺! 呈g f 挖删m m i n m a xah e wa 1 + h 驯m i n ( 2 2 一) v = 生一( 挖g w 一 ) + h g wm l n ( ) m a x 一m i n 、 一一 一 将a 的值v 映射到区间 n e wm i n n e w _ m g x 。 中的v 7 。z - s c o r e 规范化中，属性a 的值基于a 的平均值和标准差规范化。a 的值v 被规范化为1 ，由式2 3 计算， 其中，4 和西分别为属性a 的平均值和标准差。当属性a 的最大值和最小值未 v ，：! 丝( 2 3 o 囊 知，或孤立点左右了最大一最小规范化时，该方法是有用的。小数定标规范化通 过移动属性a 的小数点位置进行规范化。小数点的移动位数依赖于a 的最大绝对 东南未学硕士学位论文 值。a 的值v 被规范化为v ，由下式计算： v 4 = ( 2 4 ) 。v 1 0 。 其中，j 是使得m a x ( jv ) y 的支持度则记作s u p ( x u y ) 。 可信度( c o n f i d e n c e ) ；对形如x = y 的关联规则，其中x 和y 都是项目集， 定义规则的可信度为交易集合d 中既包含x 也包含y 的交易个数与d 中仅包含x 而不包含y 的交易个数之比，或者说是项目集x u y 的支持度与x 的支持度之比， 即s u p ( x u y ) s u p ( x ) ，把规则x = y 的可信度记作c o n f ( x uy ) 。一个规贼的可 信度的范围在0 到1 之间。事实上可信度即指在出现了项目集x 的交易中，项目 集y 也同时出现的概率有多大。 最小支持度( m i n i m u m s u p p o r t ) ：由用户定义的衡量支持度的一个闽值，表示 项目集在统计意义上的最低重要性，记作m i n s u p 。 最小可信度( m i n i m u mc o n f i d e n c e ) ：由用户定义的衡量可信度的一个阚值， 表示舰则的最低可靠性。记作m i n c o n f 。 频繁项目集( f r e q u e n ti t e m s e t ) ：对个项目集x ，如果x 的支持度不小子 用户定义的最小支持度阈值，即s u p ( x ) m i n s u p ，称x 为非频繁项目集或大集 ( l a r g ei t e m s e t ) 。 非频繁项目集( n o t r e q u e n t l t e m s e t ) ：对一个项目集x 持度小于用户定义的 第三章关联规则 最小支持度阈值，即s u p ( x ) c l 八c 2 八 c t 其中舡( 1 i s ) ，c j ( 1 j t ) 为集合i 中的个元素( 或个项目) 。 可信度是对关联规则的准确度的度量，或者说表示规则的强度；支持度是对关 联规则的重要性的度量，表示规则的频度。支持度说明了这条规则在所有事务中 有多大的代表性，显然，支持度越大，关联规则越重要。有些关联规则可信度虽 然很高，但支持度却很低，说明该关联规则实用的机会很小。反之，如果支持度 很高，可信度很低，则说明该规则不可靠。 如果不考虑关联规则的支持度和可信度，那么在数据库中存在非常多的关联 规则。事实上，人们一般只对那些满足一定的支持度和可信度的关联规则感兴趣。 因此，为了发现有意义的关联规则，需要由用户给定两个基本阈值：最小支持度 和最小可信度。 关联规则的挖掘问题被归纳成两个子问题或两个基本步骤：找到所有满足用 户给定的最小支持度的频繁项目集。在频繁项目集的基础上生成所有满足用户 给定的最小可信度的关联规则。 查塑查兰堕圭兰堡堡苎t 第一个子问题由于产生的数据量巨大，具有很大的挑战性，其中算法的关键 是效率问题，故大多数算法多集中在第一个问题上。 第二个子问题相对容易和直观。从频繁项目集生成所有满足用户给定的最小 可信度的关联规则，即对任何一个频繁项目集z 和z 的所有非空真子集w ，w c z 如果s u p ( z ) s u p ( z - w ) 一 m i n c o n f ，则( z - w ) = w 就是条有效的关联规则。 上述方法发现所有类似的规则。一旦知道了频繁项目集的支持度，对所有频繁项 集x ，假定规则x y y ( y c x ) 匹配上了一个期望的最小可信度形如x y = ，y 的规则就生成了。虽然第二步很简单，但仍然有很重要的研究内容，例如从大量 规则中找到有意义的规则。 3 4 1 概述 3 3 基于最大频繁项目集的关联规则发现 关联规则挖掘工作的一个关键问题就是从交易集合中发现所有满足用户给 定的最小支持度的频繁项目集，这一步骤集中了所有的计算量。关联规则由 r a k e s h a g r a w a l 等人提出，他们提出了关联规则挖掘中最著名的a p r i o r i 算法以 及它的变种a p r i o r i t i d 和a p r i o r i h y b r i d 算法来发现频繁项目集。其后，许多 学者都提出了关联规则频繁项目集的发现算法，但大多数算法都是a p r i o r i 算法 的变种或者是其改进。由于a p r i o r i 算法是个多趟搜索算法，对海量数据集合， 每搜索一次，都要读取外存一次，i 0 开销很大。因此大多改进算法，都在如 何减少搜索次数上做文章。 以a p r i o r i 算法为基础的经典关联规则频繁项目集发现算法，如果在交易数 据集合中包含的不同的项目的数量为n 个，则传统的发现算法将要计算2 的a 次 方项目集。当n 比较大时，将会产生组合爆炸。虽然s a m p l i n g 算法、p a r t i t i o n 算法、d i c 算法等都试图减少对交易数据集合的搜索次数，但仍有很多缺点。 s a m p l i n g 算法从原数据集合中随机抽样出一部分样本，利用样本宋挖掘关联规 则以减少算法的搜索次数，但是由于数据集合中经常存在数据分布不均匀的隋 况，所以随机抽样根本就无法保证能够抽取到有代表性的样