（计算机软件与理论专业论文）基于数据仓库的知识发现模式的研究.pdf

台肥下业人学硕l 论义摘要 摘要 刚间序列模式、分类规则和关联规则挖掘是当前数据挖掘研究中一个热点。 本文对时间序列模式、分类规则和关联规则挖掘的方法进行了深入的研究。挖掘 规则及其它知识是个多阶段的处理过程，本文认为这个过程应以用户为中心。 这个处理过程的各个阶段都是重要的，都应加以详细研究。在这个思想指导下开 展工作，主要内容如下： 本文对数据准备的方法进行了深入的研究，提出了一种基于数据仓库的数据 挖掘模型，该模型结合了o l a p 技术和数据仓库的策略，利用概念层次作为背景 知识，将数据库中的原始数据泛化成用户感兴趣的概念层次上的、聚合的、具有 统计意义的元数据。 将相关性分析引入数据预处理过程，从而去除与挖掘任务不相关的属性，减 少了数据集，提高了挖掘规则精度。 针对泛化后的数据，本文改进并实现时间序列模式发现算法； 修改了传统的决策树算法，提出了一种适合于泛化数据的决策树构造算法： 阈值控制法，阈值控制法通过闽值和概念层次的控制，可以建立简洁明了、具有 统计意义的分类树； 在概念格理论基础上提出了基于不确定系数法挖掘关联规则的算法。 设计并初步实现了一个数据挖掘原型系统，该工具以用户为中心，在用户的 干预下能够有效的对现实数据库、数掘仓库进行时间序列模式、分类规则和关联 规则的挖掘。 关键字：数据挖掘、数据仓库、联机分析、时间序列模式、分类规则、概念格、 关联规则。 合肥t 业人学硕i ：i q 文摘要 a b s t r a c t i ti sah o t s p o tt h a tt h ed a t am i n i n go ft i m es e r i a lm o d e l c l a s s i f yr u l e a s s o c i a t i o n r u l ei nt h ed a t am i n i n gs t u d yc u r r e n t l y i nt h i st h e s i s ，t h et h o r o u g hs t u d yo ft i m e s e r i a lm o d e l c l a s s i f i c a t i o nn i l ea n da s s o c i a t i o nr u l ei sm a d e i ti st h o u g h tt l l a tt h e d a t am i n i n gi st h em u l t i s t a g ep r o c e s so fr i s e r sc e n t e ri nt h i st h e s i s i ti si m p o r t a n t t h a tt h ed a t am i n i n go f m u l t i s t a g ep r o c e s ss h o u l db es t u d yi nt h ee a c hp h a s e i nt h i s t h o u g h t t h em a i nw o r ki nt h i st h e s i sa sf o l i o w i n g ： t h ew a yo ft h ed a t am i n i n gi sd e e p l ys t u d i e da n dam o d e lo fd a t am i n i n gb a s e d o nd a t aw a r e h o u s ei si n t r o d u c e d t h em o d e li sc o m b i n e dw i t ht h es t r a t e 州o fd a t a w a r e h o u s ea n do l a pt e c h n o l o g y , m a d eu s eo fc o n c e p th i e r a r c h ya sb a c k g r o u n d k n o w l e d g e a n de x t e n d e dd a t ai nt h ed a t a b a s ea su s e r si n t e r e s t i n gm e t a d a t ao ft h e c o n c e p th i e r a r c h y , a g g r e g a t t o n b e s i d e s r e l a t i v i t ya n a l y s e si si n t r o d u c e di nt h ep r o c e s so fd a t ap r e t r e a t m e n ti n t h i st h e s i s t h e r e b yc a n c e l e dt h ed i s r e l a t e da t t r i b u t eo fd a t am i n i n ga s s i g n m e n t ， r e d u c e di o t so fd a t as e t sa n di m p r o v e st h ea c c u r a c ya n de f f i c i e n c yo fr u l e sm i n e d t bb ed e a l e da g a i s te x t e n d e dd a t a 。t h i st h e s i sh a si m p r o v e do na n dc o m et r u e a r i t h m e t i co ft i m es e q u e n c em o d e l ，a n da m e n d e dc o n v e n t i o n a ld e c i s i o nt r e e a r i t h m e t i c ，i n t r o d u c e dt h ed e c i s i o nt r e ea r i t h m e t i cf o re x t e n d e dd a t a ，n a m e l y t h r e s h o l dv a l u ec o n t r o la p p r o a c h a c c o r d i n gt ot h r e s h o l dv a l u ea n dc o n c e p t h i e r a r c h y , t h r e s h o l dv a l u ec o n t r o la p p r o a c hc ans e tu pt h ec o n c i s ea n ds t a t i s t i c c l a s s i f i c a t i o nt r e e a tt h es a m et i m e ，b a s e do nt h et h e o r yo ft h ec o n c e p tl a t t i c e ，t h i st h e s i s i n t t o d u c e st h ea r i t h m e t i co fm i n i n ga s s o c i a t i o nr u l e sb a s e do nq u a n t i f i e dc o n c e p t l a a i c er e d u c e db yu n c e r t a i n t yc o e m c i e n t t h i st h e s i sd e s i g n sa n da c c i d e n c i l yc a r r i e so u tt h ep r o t o t y p es y s t e mo fd a t a m i n i n g t 1 1 i st 0 0 1i sc e n t e r e do nt h eu s e r , u n d e rt h eu s e r sc o n t r 0 1 a n dt ob e c a p a b l et oe r i e c t i v e l ym i n et h er u l eo ft i m es e q u e n c em o d e la n dt h ec l a s s i f i c a t i o n r o l ea n dt h ea s s o c i a t i o nr u l ei nt h ed a t a b a s eo rd a t aw a r e h o u s e k e y w o r d s ：d a t am i n i n g ，d a t aw a r e h o u s e ，o l a p , t i m es e q u e n c em o d e l ，c l a s sr u l e ， c o n c e p tl a t t i c e ，a s s o c i a t i o nr u l e 1 1 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究 成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表或撰写过的研究成果，也不包含为获得 盒蟹王些太堂 或其他教育机 构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示谢意。 学位论文作者签名 、 b b 签字日期：0 彬年一r 月弓日 学位论文版权使用授权书 本学位论文作者完全了解金蟹王些盔堂有关保留、使用学位论文的规定 有权保留菏向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和 借阅。本人授权盒蟹王些友堂可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：够 、 多鲁、 签字目期：朋年r 月弓】日 学位论文作者毕业后去向 工作单位： 通讯地址： 导师签名 签字日期：年月日 电话 邮编 多 合肥t 业人学砸i 论文 笫一秆绪论 第一章绪论 随着信息技术的高速发展，数据库应用的规模、范围和深度不断扩大。近年 来，商业条码的推广、企业和政府事务的管理以及数据采集工具的发展，都提供 了大规模的数据，在商业管理、政府部门、科学和工业数据处理等领域都应用了 数以百万计的数据库。随之数据和数据库的急剧增长，仅仅依靠数据库管理系统 的查询检索机制和统计学分析方法已经远远不能满足现实需要了，它迫切要求自 动和智能地将待处理的数据转化成有用的信息和知识。于是，数据库中知识发现 ( k n o w l e d g ed i s c o v e ri nd a t a b a s e ，简称k d d ) 便应运而生，成为近年来人工智 能、数据库应用等领域的研究热点。目前，k d d 的研究涵盖了多个领域的多种知 识发现方法，已经能够发现时间序列规则、关联规则、分类规则、聚类规则等多 种知识类型。此外，随之联机分析处理( o n _ l i n ea n a l y t i c a lp r o c e s s i n g ，o l a p ) 和数据仓库( d a t aw a r e h o u s e ，d w ) 研究技术【2 n 列的发展，将d w 与k d d 两者结合 用于数据分析和知识发现是一个新的研究方向【4 j 。本章将首先概括的介绍一下 d w 、o l a p 、k d d 的方法及现状，最后提出本文的研究内容和本文的内容安排。 1 1 数据仓库与联机分析处理 数据仓库的经典概念由w i - t i n m o n 于1 9 9 2 年最早提出：“数据仓库是2 0l u ： 纪9 0 年代信息技术构架的新焦点，它提供集成化和历史化的数据，集成种类不同 的应用系统，数据仓库从事物发展和历史的角度来组织和存储数据，以供信息化 和分析处理之用。”数据仓库是面向主题的、集成的、不易失的、时变的数据库。 数据仓库应用是一个典型的c s 结构。其客户端的工作包括客户交互、格式化查 询及报表生成等。服务器端完成各种辅助决策的s q l 查询、复杂的计算和各类综 合功能等。现在采用三层结构的形式，即在客户与服务器之间增加一个应用服务 器，它能加强和规范决策支持的服务工作，集中和简化客户端和d w 服务器的部 分工作，降低系统数据传输量，因此工作效率更高。 随之数据仓库技术的发展，人们越来越需要强有力的工具来对数据进行有效 的分析，以提高决策能力。在众多的分析工具中，由e e c o d d 于1 9 9 3 年提出的 联机分析处理( o nl i n ea n a l y t i c a lp r o c e s s i n g ，称为o l a p ) 在业界引起了很大的 反响1 5 】，不仅是数据库领域的研究热点，也引起了a i 工作者的极大兴趣。联机分 析处理是针对特定问题的联机数据访问和分析。o l a p 系统必须提供数据的多维 概念视图，通过对信息的很多种可能的观察形式如切片、切块、旋转，进行快速、 稳定一致和交互性的提取，允许管理决策人员对数据进行深入观察分析。o l a p 一般分为三个步骤i z 】：( 1 ) 根据用户的查询模式，从数据仓库中选择相关数据；( 2 ) 台肥t 业人学顺l 二论史 第一章绪论 建造多维立方体( c u b e ) ，以提供给用户数据的多维试图；( 3 ) 以多维立方体为 依据进行多维分析。在这三步中，多维立方体的建立是一个基础，它能够以多维 视图组织存储统计过的数据，使用户能够从多个不同的角度处理分析数据，图1 1 便是一个典型的多维立方体。目前一般采用两种技术建立立方体：基于多维数据 库和基于关系数据库。 图1 1 数据立方体示意图 多维分析是o l a p 中最有特点的技术。基本的分析动作有切片、切块、旋转 等；通过多维分析对信息的多个角度、多个侧面进行快速、一致和交互的存取， 从而使分析人员能够对数据进行深入地分析和观察。o l a p 对数据存储和分析特 点，引起了k d d 研究者的极大兴趣，j i a w e ih a r t 等人便提出将o l a p 与k d d 相 结合的研究方法，并进行了一系列的深入研究，取得了较好的效果。本文提出在 多种数据库的基础上构造数据仓库，然后在多种数据源和数据仓库上进行联机分 析和各种知识、规则的挖掘算法的研究，可以有效地对异型数据库进行联机地、 多层次地挖掘知识和规则。 1 2 数据库中知识发现( k d d ) 1 2 1 数据库中知识发现的定义与目标 数据库中知识发现是面向应用的，不同的应用需要发现的知识形式不同，采 取的发现策略和方法也不同。因此，在进行知识发现前要充分了解应用的主题。 目前，k d d 发现的知识形式主要包括以下几类【6 j ： 特征( c h a r a c t e r i z a t i o n ) ：是指将与任务相关的数据集概括或抽象为某个 关系，称为推广关系( g e n e r a l i z e dr e l a t i o n ) 。该推广关系可用于提取特征 规贝l j ( c h a r a c t e r i s t i er u l e s ) 。特征规则可以在多层概念级上表示称之为目标 类( t a r g e tc l a s s ) 的数据集特征。 区分( d i s c r i m i n a t i o n ) ：是指发现分辨目标类( t a r g e tc l a s s ) 与对照类 ( c o n t r a s t i n gr u l e s ) 的特征与性质。从这些分辨目标类与对照类的特性中， 我们可以发现一系列的区分规则( d i s c r i m i n a n tr u l e s ) 。 第一章绪论 分类( c l a s s i f i c a t i o n ) ：是指将数据归于一系列已知类( k n o w nc l a s s e s ) 中 的某一个的标记或分类过程。给定一训练数据集( 即已知其类别标记的 客体集) ，以及基于训练集中数据的特性建立的分类模型，目标是从该分 类模型中生成一系列的分类规则，这些分类规则可用于对其它未来的数 据进行分类，从而可以更好地理解数据库中的每一类。 聚类( c l u s t e r i n g ) ：是根据客体属性对一系列未分类客体进行类n 0 ( c l u s t e r ) 的识别。客体的聚类应使用类内( i n t r a c l a s s ) 相似性最大，而类间 ( i n t e r c l a s s ) 相似性最小。一旦聚类得以确定，各个客体就作相应的聚类 标记，并概括同一聚类中的各个客体的共同特征，从而形成类别描述。 关联规则发现( a s s o c i a t i o nr u l e s m i n i n g ) ：是指发现客体之间的相互关系。 关联规则，形如“a 1 a a i ：b i a b ”，意昧着在目标数据中客体br - b 倾向于同客体a l a i 一起出现。 序列模式发现( s e q u e n t i a lp a t t e r n sm i n i n g ) ：是指在多个数据序列中发现 共同的行为模式。序列模式的发现方法与关联规则的发现方法大致相同。 但两者的序列包含判断是不一样的，而且，关联规则仅仅发现事务内部 ( i n t r a t r a n s a c t i o n ) 的模式( 项目集i t e m s e t s ) ，而序列模式则是发现事务 之间( i n t e r t r a n s a c t i o n ) 的模式。 预测( p r e d i c t i o n ) ：是指对某客体集中缺损值( m i s s i n gv a l u e ) 或某属性 值分布的估计。这涉及到寻找与兴趣属性相关的属性集和根据与选中客 体相似的数据集预测值分布。 本文所讨论的知识发现主要是时问序列模式、分类规则、关联规则。 1 2 2k d d 的过程与方法 正如定义所说，k d d 实际上是一个从数据库中发现知识的过程。1 9 9 6 年， f a y y a d 、p i a t e t s k y s h a p i r o r 和s m y t h 给出了k d d 过程的描述【7 】，如图1 2 所示： 图1 2k d d 的过程 从图1 2 中可以看出，数据采掘过程一般由3 个主要的阶段组成：数据准备、采 合肥1 ：业人学硕i j 论文第一章绪论 掘操作、结果表达和解释。知识的发现可以描述为这3 个阶段的反复过程。下面 具体说明一下这三个阶段： 数据准备：这个阶段又可进一步分成3 个子步骤：数据集成、数据选择、数据 预处理。数据集成将多文件或多数据库运行环境中的数据进行合并处理，解 决语义模糊性、处理数据中的遗漏和清洗脏数据等；数据选择的目的是辨别 出需要分析的数据集合，缩小处理范围，提高数据采掘的质量；预处理主要 是对数据选择产生的数据进行再加工，检查数据的完整性及数据的一致性， 对其中的噪音数据进行处理，对丢失的数据可以利用统计方法进行填补，本 文在数据准备阶段中，将着重研究在异种数据库上构建数据仓库时要解决的 实际问题。 数据挖掘：这个阶段进行实际的采掘操作包括的要点有：( 1 ) 要先决定如何 产生假设，是让数据采掘系统为用户产生假设，还是用户自己对于数据库中 可能包含的知识提出假设。前一种称为发现型( d i s c o v e r y d r i v e n ) 的数据采 掘；后一种称为验证型( v e t i f i c a t i o n d r i y e n ) 的数据采掘；( 2 ) 选择合适 的工具；( 3 ) 发掘知识的操作；( 4 ) 证实发现的知识。 结果表述和解释：根据最终用户的决策目的对提取的信息进行分析，把最有价 值的信息区分出来，并且通过决策支持工具提交给决策者。因此，这一步骤 的任务不仅是把结果表达出来( 例如采用信息可视化方法) ，还要对信息进 行过滤处理。如果不能令决策者满意，需要重复以上数据采掘的过程。 在这个过程中，数据采掘是其中最重要的部分，根据挖掘的任务不同，数据挖掘 的方法也不同，常用的挖掘方法和技术可归为以下几类1 8 】： 概念格方法：概念格( 也称为g a l o i s 格) 是r w i l l e 在1 9 8 2 年【9 首先提 出的，已知上下文( c o n t e x t ) 为三元组c - ( 0 ，d ，r ) ，其中0 是对象集 合，d 是属性集合，r 是0 和d 之间的一个二元关系，则存在唯一的偏序 关系与之对应，并且这个偏序关系产生一个格结构，它能揭示数据中所蕴 含的各种关系。 决策树方法：利用信息论中的互信息( 信息增益) 寻找数据库中具有最大信 息量的字段，建立决策树的一个结点，再根据字段的不同取值建立树的分 支；在每个分支子集中重复建树的下层结点和分支的过程，即可建立决策 树。国际上最有影响和最早的决策树方法是o u i u l a n 研制的i d 3 方法，它 对越大的数据库效果越好。在i d 3 方法的基础上，后人又发展了各种决策 树方法；如c 4 5 方法。 神经网络方法：它模拟人脑神经元结构，以m p 模型和h e b b 学习规则为基 础，建立了三大类多种神经网络模型。( 1 ) 前馈式网络。它以感知机、反向 第一章绪论 传播模型、函数型网络为代表，可用于预测、模式识别等方面。( 2 ) 反馈 式网络。它以i f o p f i e l d 的离散模型和连续模型为代表，分别用于联想记 忆和优化计算。( 3 ) 自组织网络。它以a r t 模型、k o h o l o n 模型为代表，用 于聚类。神经网络的知识体现在网络连接的权值一i - ，是一个分布式矩阵结 构；神经网络的学习体现在神经网络权值的逐步计算上( 包括反复迭代或 累加计算) 。 粗集( r o u g hs e t ) 方法：在数据库中，将行元素看成对象，列元素看成属性 ( 分为条件属性和决策属性) 。等价关系r 定义为不同对象在某个( 或几个) 属性上取值相同，这些满足等价关系的对象组成的集合称为该等价关系r 的等价类。条件属性上的等价类e 与决策属性上的等价类y 之间有三种情 况：下近似：y 包含e ；上近似：y 和e 的交非空；无关：y 和e 的 交为空。对下近似建立确定性规则，对上近似建立不确定性规则( 含可信 度) ，对无关情况不存在规则。 遗传算法：这是模拟生物进化过程的算法，由三个基本算子组成：( 1 ) 繁殖 ( 选择) 是从一个旧种群( 父代) 选出生命力强的个体，产生新种群( 后代) 的过程。( 2 ) 交叉( 重组) 选择丽个不同个体( 染色体) 的部分( 基因) 进行交 换，形成新个体。( 3 ) 变异( 突变) 对某些个体的某些基因进行变异( 1 变0 、 0 变1 ) 。这种遗传算法可起到产生优良后代的作用。这些后代需满足适应 值，经过若干代的遗传，将得到满足要求的后代( 问题的解) 。遗传算法已在 优化计算和分类机器学习方面发挥了显著作用。 统计分析方法：在数据库字段项之间存在两种关系：函数关系( 能用函数 公式表示的确定性关系) ；相关关系( 不能用函数公式表示、但仍是相关 确定关系) 。对它们的分析采用如下方法：回归分析、相关分析、主成分 分析。 可视化技术：可视化数据分析技术拓宽了传统的图表功能，使用户对数据 的剖析更清楚。例如，把数据库中的多维数据变成多种图形，这对揭示数 据的状况、内在本质及规律性起了很大作用。 1 3 数据挖掘的研究现状和方法 1 3 1 时间序列的研究现状与挑战 数据库中的知识发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e s ，简称k d d ) 是数据 库和人工智能领域研究的热点课题，其目的是在数据库中提取隐含的，先前未知 的，潜在有用的知识。在很多实际应用中，如保险业、银行业、商业事务处理系 台肥工业大学硕：f ：论文 第一章绪论 统、地理信息系统等，数据库中时问的改变是有价值的信息源，它能进一步指导 企业的运作。在时问序列模式发现中我们关注数据库中与时间有关的历史数据， 从这些数据中抽取关于周期行为的有用的知识。发现的知识能为用户提供进一步 的指导。知识发现和数据仓库在有效地协助和分析大规模数据库中越来越来重要。 在知识发现和数据仓库中，我们充分利用联机分析( o l a p ) 技术。把这个技术应 用于时间相关数据以解决周期模式发现问题。周期模式发现问题分为二类：一类是 给定周期发现时序周期模式；另一类是在任意周期长度上发现时序周期模式。我 们可以看出，在许多现实数据库中，对象的属性值可能会随时问而变化，数据变 动很可能随时问呈现出某种发展趋势或周期性。因此，为了进行预测，我们必须 从分析时间序列数据的变化特征着手，首先建立适当的预测模型，再根据惯性原 则，假定预测对象以往的变化趋势会延续到将来，从而做出预测。所以，如何从 时序数据中挖掘出时序模式，就变成十分重要。我对国内外的一些典型算法作了 分析，并结合现实数据库，发现在分析时间序列数据时，对于一个复杂的模式， 往往不可能预先确定其形式，并且在一个时序序列数据库中包含了多种类型的模 式。时序序列模式并不是一个形如y = f ( t ) 的函数表达式。判断二个模式是否相似 时，常常要允许某种程度的形变，我们可以发现看似不同的模式其实是相似的， 如何定义模式的相似性程度，成为关键问题。针对这些问题，提出一种新的时序 序列模式的逻辑表示法，进而设计出一种新的时序序列建模算法。 1 3 。2 分类规则的研究现状与挑战 在数据库知识发现领域中，分类规则挖掘是一种重要的发现任务，分类规则 的挖掘问题在统计学、机器学习、神经网络和专家系统中得到了较早的研究，但 只是在近些年来，人们才将其与数据库技术结合起来解决实际问题。分类的目的 是学会一个分类函数或分类模型( 也常常称作分类器) ，该模型能把数据库中的数 据项映射到给定类别中的某一个。根据这个分类器可以提取出t f t h e n 型的分 类规则。 分类规则挖掘的首要任务是要构造分类器，这需要有一个训练样本数据集作 为输入。训练集由一组数据库中的记录、元组构成，每个元组是一个由有关字段 ( 又称属性或特征) 值组成的特征向量，除了这些外，训练样本还有一个类别标 记。一个具体样本的形式可为：( v l ，v 2 ，v n ；c ) ；其中v i 表示字段值，c 表示类 别。 目前常用的分类器构造方法有统计方法 1 0 】【l 、机器学习方法1 2 1 1 13 1 、神经网络 方法1 4 等等。统计方法包括贝叶斯法和非参数法( 近邻学习或基于事例的学习： i n s t a n c e b a s e dl e a r n i n g ，i b l ) ，对应的知识表示则为判别函数和原型事例。机器学 习方法包括决策树和规则归纳法，前者对应的表示为决策树或判别树，后者则有 台* m _ 丁业大学硕i 二论文第一章绪论 两种：决策表和产生式规则。神经网络方法主要是b p 算法，它的模型表示是前 向反馈神经网络模型( 由代表神经元的节点和代表联接权值的边组成的一种体系 结构) ，b p 算法本质上是一种非线性判别函数。另外，最近又兴起了一种新的方 法：粗糙集( r o k l g hs e t ) ，其表示是产生式规则。 不同的分类器有不同的特点。有三种分类器评价或比较尺度：预测准确度； 计算复杂度；模型描述的简洁度。预测准确度是用的最多的一种比较尺度。 计算复杂度依赖于具体的实现细节和硬件环境，在k d d 中，由于操作对象是巨 量的数据库，因此空间和时间的复杂度问题将是非常重要的一环节。对于描述型 的分类任务，模型描述越简洁越受欢迎；例如，采用规则表示的分类器构造法就 更有用，而神经网络方法产生的结果就难以理解。另外要注意的是，分类的效果 一般和数据的特点有关，有的数据噪声大，有的有空值，有的分布稀疏，有的字 段或属性间相关性强，有的属性是离散的而有的是连续的或混合式的。目前普遍 认为不存在某种方法能适合于各种特点的数据。 近年来，在数据库中进行分类规则挖掘己成为分类研究领域中的一个重要研 究方向，目前常用的方法是先将与分类任务有关的数据库中的各属性的值抽取出 来，并将其存入二维文件中，然后将这些二维文件装入内存，再把算法施加于该 二维文件，构造分类器并挖掘出分类规则。随着数据库、数据仓库技术的发展与 应用，数据量急剧增大，人们对分类规则的挖掘提出了新的要求。有这样一个例 子：一个人发现了一种新蘑菇，他希望能根据该蘑菇的颜色、形状、大小和气味 来判断是否有毒。这人从互联网上找到了一个蘑菇数据库，该数据库记载了许多 种蘑菇的洋细特征，其中就包括了颜色、形状、大小、气味以及是否有毒。于是 这个人就希望有一种方法能帮助他根据颜色、形状、大小、气味等属性对是否有 毒这一属性进行联机分类，以发现规律。这种分类任务被许多研究者称为在线分 类规则挖掘( 简称在线分类) ，具有以下特点： 直接面对大数据量、现实世界的数据库或数据仓库： 用户要求明确的元模式，即根据数据库中哪几个属性对某个属性进行分 类。有时用户还会在挖掘的过程中修改元模式。因此用户需分析浏览原始 数据； 分类是联机在线进行的，用户期望在较短时间内得到结果； 用户期望得到较高层次的，具有统计意义的分类规则，这是跟传统分类最 大的不同点。基于以上四个特点，使用二维文件式的方法很难完成该类任 务，需要研究新的方法。 1 3 3 关联规则的研究现状与挑战 关联规则是r a k e s ha g r a w a l 等人提出的数据挖掘领域中的一个重要课题，它 介删t 业人学坝j 论义第一章绪论 揭示数据问的相互关系，关联规则的挖掘就是从一组给定的数据项以及交易集合 ( 每一条交易是一个数据项的集合) 中，分析出数据项集在交易集合中出现的频 度关系。 挖掘关联规则的算法已经有很多，比较重要的有r a k e s ha g r a w a l 等人提出的 a p r i o r i 算法和s e r g e yb r i n 等人提出的d i c 算法【1 6 】。另外，最近一些研究人员 关注从概念格中挖掘各种规则。把所感知的事物的共同本质特点抽象出来，并加 以概括，成为概念，概念都具有内涵和外延。r ，w i l l e 在1 9 8 2 年首先提出根据二 元关系系统来构造相应概念格( 或g a l o i s 格) 的思想【9 】，也称为形式概念分析， 就是以格巾的每个节点表示一个形式概念，其中概念的外延代表相应的一组对象， 内涵则为这组对象所具有的公共特征( 属性) ：而概念格所相应的h a s s e 图则形象 地揭示了概念间的泛化和例化关系，反映出一种概念层次结构( c o n c e p t h i e r a r c h y ) ，实现了对数据的可视化，非常适用于从数据库中进行知识发现的描述 b 7 1 ，从而成为数据分析和规则提取的一种有效工具。 1 4 本文的研究内容与章节安排 本文对数据挖掘的方法进行了广泛和深入的研究，结合了数据仓库和联机分 析处理技术，提出了有效的时间序列预测，分类方法，关联规则的挖掘；并设计 实现了一个数据挖掘工具的原型。各章的内容安排如下： 第一章绪论。概括的介绍了k d d 、d w 、o l a p 及数据挖掘的理论与方法； 第二章数据挖掘中的数据仓库及数据泛化研究。提出了如何构造数据仓库和一 种基于数据立方体的数据泛化算法。在本文的研究中，数据泛化作为数据准备阶 段采用的策略，在数据挖掘中起着重要作用。 第三章时间序列模式发现分析研究。在这个过程中，我们将发现一些属性会随 着时间数据的变化而改变，其改变有时具有一定的规律性，本章就是发现一些会 随着时间变化而发生的模式。 第四章基于泛化的在线分类算法。详尽描述了本文研究中采用的在线分类算法。 第五章研究关联规则挖掘算法，并提出基于概念格发现关联规则的思想和构造 算法。 第六章数据挖掘工具的设计与实现。本章详细描述了作者设计并实现的一个数 据挖掘工具的构造、实现与应用。 第七章结论与展望 8 合粑t 业 = 学顺i j 论文第二章数据仓库构造的 i j | _ 究 第二章数据仓库构造的研究 构造数据仓库涉及数据清理和数据集成，可以看作数据挖掘的预处理部分。 此外，数据仓库提供联机分析处理( o l a p ) 工具，用于各种粒度的多维数据分析， 有利于有效的数据挖掘。许多其他数据挖掘功能，如分类、预测、关联和聚类等， 都可以与o l a p 操作集成，以加强多个抽象层上的交互知识挖掘。因此，数据仓 库已经成为数据分析和联机分析处理日趋重要的平台，并为数据挖掘提供有效的 平台。 本章将首先介绍数据仓库与数据仓库的构造，然后引入概念分层、多维立方 体的构造以及泛化算法，最后提出了相关性分析。 2 1 数据仓库 2 1 1 数据仓库的概念 数掂仓库的概念定义是：数据仓库是一个面向主题的、集成的、时变的、非 易失的数据集合，支持管理部门的决策过程。这个简短而又全面的定义指出了数 据仓库的主要特征。四个关键词，面向主题的、集成的、时变的、非易失的，将 数据仓库与其他数据存储系统( 如关系数据库系统、事务处理系统和文件系统) 相区别。让我们看看这些关键特征： 面向主题的( s u b j e c t o r i e n t e d ) ：数据仓库围绕一些主题，如顾客、供应 量、产品和销售组织。数据仓库关注决策者的数据建模和分析，而不是集 中于组织机构的日常操作和事务处理。因此，数据仓库排除对于决策无用 的数据，提供特定主题的简明视图。 集成的( i n t e g r a t e d ) ：构造数据仓库是将多个异种数据源，如关系数据库、 一般文件和联机事务处理记录，集成在一起。使用数据清理和数据集成技 术，确保命名约定、编码结构、属性度量等的一致性。 时变的( t i m e - v a r i a n t ) ：数据存储从历史的角度( 例如过去5 1 0 年) 提 供信息。数据仓库的关键结构，隐式或显示地包含时间元素。 非易失的( n o n v o l a t i l e ) ：数据仓库总是物理地分离存放数据：这些数据 源于操作环境下的应用数据。由于这种分离，数据仓库不需要事务处理、 恢复和并发控制机制。通常，它只需要二种数据访问：数据的初始化装入 和数据访问。 总而言之，数据仓库是一种语义上一致的数据存储，它充当决策支持数据模 型的物理实现，并存放企业战略决策所需信息。数据仓库也常常被看作一种体系 9 肥 。业大学硕上论文第二章数据仓库构造的研究 结构，通常把异种数据源中的数据集成在一起而构造，支持结构化的和专门的查 询、分析和决策制定。建立数据仓库可看作构造和使用数据仓库的过程。数据仓 库的构造需要数据集成、数据清理和数据统一。对异种数据库来说，数据仓库是 十分有用的。许多组织收集了不同的数据，并将多个异种的、自治的、分布的信 息源维护大型数据库。集成这些数据，并提供简明、有效的访问。下面给出有关 数据仓库的一些基本概念： 元数据：是关于数据的数据。元数据是定义仓库对象的数据。对于给定数据仓库 的数据名和定义，创建元数据。其他元数据包括对提取数据添加的时间标签、提 取数据的源、被数据清理或集成处理添加的字段等。 元数据的存储应包括： 数据仓库结构的描述，包括仓库模式、视图、维、层次结构和导出数据的 定义，以及数据集市的位置和内容。 操作元数据，包括数据血统( 移植数据的历史和用于它的转换序列) ，数 据流通( 主动的、档案的或净化的) ，以及监视信息( 仓库使用统计、错误 报告、审计跟踪) 。 汇总用的算法，包括度量和维定义算法，数据所处粒度、分割、主题领域、 聚集、汇总、预定义的查询与报告。 由操作环境到数据仓库的映射，包括源数据库和他们的内容、网阳j 连接程 序描述、数据分割、数据提取、清理、转换规则和缺省、数据刷新和剪裁 规则、安全( 用户授权和存取控制) 。 关于系统性能的数据，除刷新、更新和复制周期的定时和调度的规则外， 还包括改善数据存取和检索性能的索引和配置。 商务元数据，包括商务术语和定义、数据拥有者信息和收费策略。 与数据仓库中的其他数据相比，元数据扮演很不相同的角色，并且由于各种 原因，也是重要的角色。例如，元数据用作目录，帮助决策支持系统分析者对数 掘仓库的内容定位；当数据由操作环境到仓库环境转换时，作为数据映射指南； 对于用在当前细节数据与稍加综合的数据之间以及稍加综合的数据与高度综合的 数据之间的汇总算法，也作为指南。元数据应该持久的存放和管理。 2 1 2 数据仓库的设计和结构 数据仓库的设计可以使用自顶向下方法，自底向上方法或二者结合的混合方 法设计。自顶向下方法由总体设计和规划开始。当技术成熟并已经掌握，对必须 解决的商业问题清楚并已很好理解时，这种方法是有用的。自底 1 - 法以试验和 原型开始。在商务建模和技术开发的早期阶段，这种方法是有用的。这样可以以 相当低的代价进行。在混合方法下，一个组织即可以利用自顶向下方法的有计划 o 合肥t 业人学硕i 论文 第二奇数据仓库构造的研究 的战略性的特点，又能保持像自底向上方法一样快速实现和立即应用。 从软件工程的观点，数据仓库的设计和构造包含以下步骤：规划、需求研究、 问题分析、仓库设计、数据集成和测试，最后，部署数据仓库。大的软件系统可 以用二种方法开发：瀑布式方法和螺旋式方法。瀑布式方法在进行下一步之前， 每一步都进行结构化和系统的分析，就像瀑布一样，从一级落到下一级。螺旋式 方法涉及功能渐增的系统的快速产生，相续版本之间的间隔很短。对于数据仓库， 特别是对于数据集市的开发，这是一个好的选择，因为其周转时间短，能够快速 修改，并且新的设计和技术可以快速接受。 一般地，数据仓库的设计过程包含如下步骤： 选取待建模的商务处理，例如，订单、发票、出货、库存、记帐管理、销 售和一般分类帐。如果一个商务过程是整个组织的，并涉及多个复杂的对 象，应当选用数据仓库模型。然而，如果处理是部门的，并关注某一类商 务处理，则应当选择数据集市。 选取商务处理的粒度。对于处理，该粒度是基本的，在事实表中是数据的 原子级，例如，单个事务、一天的快照等。 选取用于每个事实表记录的维。典型的维是时间、商品、顾客、供应商、 仓库、事务类型和状态。 选取用于每个事实表中的度量。典型度量是可加的数值量，如d o l l a r sj d l d 和u n i t ss o l d 。 一旦设计和构造好数据仓库的构造，数据仓库的最初使用包含初始化装入、 首次展示规划、培训和定位。数据仓库的管理包括数据刷新、数据源同步、规划 故障恢复、管理存取控制和安全、管理数据增长、管理数据库性能以及数据仓库 的增强和扩展，数据仓库的体系结构如图2 1 。 图2 1 数据仓库体系结构 仓淝丁业人学坝i ：论文 第一：章数据仓库构造的研究 从结构的角度看，有三种数据仓库模型：企业仓库、数据集市和虚拟仓库。 企业仓库( e n t e r p r i s ew a r e h o u s e ) ：企业仓库搜集了关于主题的所有信 息，跨越整个组织。它提供企业范围内的数据集成，通常来自一个或多个 操作的系统，或外部信息提供者，并且是跨功能的。通常，它包含详细数 据和汇总数据，其大小出数千兆字节到数百千兆字节，数兆兆字节或更多。 企业数据仓库可以在传统的大型机上实现，如u n i x 超级服务器或并行结 构平台。它需要广泛的商务建模，可能需要多年设计和建造。 数据集市( d a t am a r t ) ：数据集市包含企业范围数据的一个子集，对于特 定的用户是有用的。其范围限于选定的主题。例如，一个商场的数据集市 可能限定其主题为顾客、商品和销售。包括在数据集市中数据通常是汇总 的。通常，数据集市可以在低价格的部门服务器上实现，基于u n i x 或 w i n d o w s n t 。实现数据集市的周期一般是数以周计，而不是数以月计或数 以年计。然而，如果它们的规划不是企业范围的，从长远讲，可能涉及很 复杂的集成。根据数据的来源的不同，数据集市分为独立的和依赖的二类。 在独立的数据集市中，数据来自一个或多个操作的系统或外部信息提供 者，或者来自在一个特定的部门或地域局部产生的数据。依赖的数据集市 中的数据直接来自企业数据仓库。 虚拟仓库( v i r t u a lw a r e h o u s e ) ；虚拟仓库是操作数据库上视图的集合。 为了有效地处理查询，只有一些可能的汇总视图被物化。虚拟仓库易于建 立，但需耍操作数据库服务器具有剩余能力。 数据仓库包含了海量数据。要求o l a p 服务器在若干秒内回答决策支持查询。 因此，数据仓库系统要支持高效的数据立方体计算技术、存取方法和查询处理技 术。下一节我们将研究数据立方体以实现数据仓库。 2 2 数据立方体 2 2 1 数据立方体的定义 从逻辑上讲，数据仓库是一个多维数据库。数据仓库和o l a p 基于多维数据 模型。该模型将数据看作数据立方体( d a t ac u b e ) 形式。o l a p 是以多维分析为基 础，刻画了在管理和决策过程中对数据进行多层面、多角度的分析处理的要求踟。 数据仓库的多维数据模式和联机分析处理中，要求在逻辑上采用多维的方式来组 织和处理数据。根据数据分析的需求，要确定多维模式中的一些属性作为对数据 对象性质的观察角度，称为维( d i m e n s i o n ) ，维往往决定着数据对象的属性。同时， 台肥丁业大学颤 论文第一二章数据仓库构造的研究 反映数据对象特性的属性称为指标( m e a s u r e ) 或度量( m e a s u r e ) 。这样的结构称作 数据立方体( d a t ac u b e ) 1 9 。实际上，并没有什么一般的根据来区分维和指标，所 有划分都是根据分析的当前需要而进行的，是相对的和暂时的。维还可以有层次 结构，例如，日期可以按