（计算机软件与理论专业论文）基于关联规则的数据挖掘技术在教学管理系统中的应用.pdf

华中科技大学硕士学位论文 摘要 通过对多维关联规则数据挖掘技术的研究，将基于多维频繁谓词的多维关联规 则数据挖掘技术运用到教学管理系统中，建立一个教学管理关联规则挖掘系统。 对群体特征与行为的数据挖掘是关联规则挖掘的一个重要的也是复杂的挖掘方 向。在教学管理系统中学生个体的自然信息与他们的选课行为之间的关联、商业领 域中的顾客基本信息与购买行为之间的关联都属于这类情况。许多通用的数据挖掘 工具，基于对更通用的挖掘需要的考虑，而没有能对上述的挖掘需求给予足够的满 足。 基于多维频繁项集的挖掘算法主要分为两个步骤。第一步是对学生特征进行维 间关联规则挖掘，找出频繁谓词，这一过程借助数据立方体工具实现；第二步是求 基于多维的频繁项集的算法及关联规则生成。这时需要以第一步生成的维问关联规 则为约束条件，对学生选修的课程进行挖掘。通过对基于多维频繁项集的算法进行 探索和优化，采用维搜索和散列的技术方法使系统的挖掘性能大大提高。兴趣度是 关联规则挖掘中经常要考虑的一个问题。有时关联规则仅用支持度和置信度来定义 是不够的，一件事情对另一件事情的促进作用实际上并没有规则兴趣度显现的那么 大，可以通过相关性判断哪些规则是有用的，哪些规则是无用的。 通过教学管理系统中的实践，得到许多有价值的信息，这些信息在帮助学校更 好地进行学生的培养、掌握学生表现情况、帮助教师备课以及安排课程等方面具有 重要的指导意义。 关键词：频繁谓词，频繁项集，散列，维搜索，关联规则，数据挖掘 华中科技大学顽士学位论文 a b s t r a c t t h em e a n si sr e s e a r c h e dt om i n em u l t i d i m e n s i o n a la s s o c i a t i o nr u l e sa n da f f e e t i v e m e a n sb a s e do nm u l t i d i m e n s i o n a lf r e q u e n ti t e m ss e tb yp r a c t i c ei nt e a c h i n gm a n a g e m e n t s y s t e mi sf o u n d m i l l i n gd a t ab e t w e e np e o p l ec h a r a c t e r sa n dt h e i ra c t i o n si sai m p o r t a n ta s p e c tf o r m u l t i d i m e n s i o n a la s s o e i 撕o nr u l e f o re x a m p l e a s s o e i a t i o nt r e n db e t w e e ns t u d e n t s s n a t u r ei n f o r m a t i o na n dt h e i rb e h a v i o r b mm a n yg e n e r a lm i n i n gt o o l sh a v en o tp a i dm u c h a t t e n t i o nt ot h e s ea s p e c t s t h ep a p e rp r o p o s ean e wm e a n st om i n em u l t i d i m e n s i o n a la s s o c i a t i o nr u l e sb a s e do n m u l t i d i m e n s i o n a lf r e q u e n ti t e m ss e tb yt w os t e p s f i r s t l yw eo b t a i ni n t e r - d i m e n s i o n a s s o c i a t i o nr o l e sb yc o m b i n i n gd a t ac u b et e c h n i q u ew i t ha p r o r im e t h o de f f i c i e n t l y s e c o n d l yw em i n em u l t i d i m e n s i o n a lf r e q u e n ti t e m ss e ta n dg e n e r a t ea s s o c i a t i o nr u l e n l i s s t e pm u s tb er e s t r i c t e db yt h em u l t i d i m e n s i o no u t c o m eg e n e r a t e di nt h ef i r s ts t e p t h e p a p e rp r o p o s eo p t i m i z i n gw a y s t oi m p r o v em i n i n ge f f i c i e n c yb yh a s h i n ga n dd i m e n s i o n s e a r c hm e t h o d i n t e r e s t i n gm e a s u r e m e n tp r o b l e mo f t e nb ec o n s i d e r e di nt h ep r o c e s st o m i n ea s s o c i a t i o nr u l e s o m e t i m e s ，i t sn o te n o u g ht od e f i n ei n t e r e s t i n gm e a s l l r e m e n to n l y b ys u p p o s e da n dc o n f i d e n c e i t sn o ts og r e a tt h a to n et l l i n ga c t u a l l ya c c e l e r a t ea n o t h e r m i n g i tc a nb e j u d g e db yc o r r e l a t i o nm e a s u r e m e n tw h i c ha s s o c i a t i o nr u l ei sv a l u a b l e b ya p p l y i n g t h em e t h o dt o t e a c h i n gm a n a g e m e n ts y s t e mw eo b t a i nm a n y v a l u a b l e k n o w l e d g ew h i c ha r eh e l p f u lf o rc o l l e g ee d u c a t i o n k a yw o r d s ：f r e q u e n tp r e d i c a t i o n ，f r e q u e n ti t e m s ，h a s i n g ，d i m e n s i o ns e a r c h ，a s s o c i a t i o n r u l e ，d a t am i n i n g i l 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他 个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：熄 日期：妒箩年f 口月了日 i 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有 权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据 库进行检索。可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在年解密后适用本授权书。 本论文属于 不保密田。 ( 请在以上方框内打“4 ”) 学位论文作者签名：瑚娉 日期：伽。y 年f ，月吁翻 指导教师签名：敞 日期；埘年一月节曰 华中科技大学硕士学位论文 1 1 课题背景 1绪论 随着数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积累的数据 越来越多。激增的数据背后隐藏着许多重要的信息，人们希望能够对其进行更高层 次的分析，以便更好地利用这些数据。目前的数据库系统可以高效地实现数据的录 入、查询、输出等功能但无法发现数据中存在的关系和规则，无法根据现有的数据 预测未来的发展趋势。缺乏挖掘数据背后隐藏的知识的手段，导致了“数据爆炸但 知识贫乏”的现象j 。 数据挖掘可以概括为从大量数据中提取或挖掘知识。可以说数据挖掘是建立在 知识与数据之间的一座桥梁。经过十多年的工作，数据挖掘技术的研究与应用己取 得了很大的成果。数据挖掘现在越来越为更多的人们所关注，被认为是未来最有发 展前景和广阔市场潜力的新兴学科之一m j 。 数据挖掘技术目前已经有不少成功的范例其实在日常生活中我们也可以看到许 多数据挖掘的应用例如，购物篮分析可以帮助经理设计不同的商店布局。一种策略 是：经常一块购买的商品可以放近些，以便进一步刺激商品的销售。顾客购买计算 机也倾向于同时购买财务管理软件，那么将硬件摆放离软件陈列近一点。更复杂的 应用见下面这个例子：美国f i r s t a r 银行使用m a r k s m a n 数据挖掘工具，根据客户的 消费模式预测何时为客户提供何种产品。f i r s t a r 银行市场调查和数据库营销部经理发 现：公共数据库中存储着关于每位消费者的大量信息，关键是要透彻分析消费者投入 到新产品中的原因，在数据库中找到一种模式，从而能够为每种新产品找到最合适 的消费者。m a r k s m a n 能读取8 0 0 到1 0 0 0 个变量并且给它们赋值，根据消费者是否 有家庭财产贷款、赊帐卡、存款证或其它储蓄、投资产品，将它们分成若干组，然 后使用数据挖掘工具预测。何时向每位消费者提供哪种产品。预测准客户的需要是 美国商业银行的竞争优势。 关联规则是数据挖掘的重要模式。学校中教学管理系统数据库有大量可供挖掘 的知识，例如挖掘出不同学生的能力，学生的就业倾向，学生的选课倾向，这些都 是学校希望掌握的信息，掌握这些信息对学生的培养工作有重要指导意义。上述知 识的发现都需要运用关联规则的知识方法，为此，本文对于学生特征和选课行为之 间数据的关联规则，尤其是基于多维频繁谓词的混合维关联规则挖掘方法进行了探 索。 华中科技大学硕士学位论文 皇昌= 墨墨= 罨暑皇皇= = = 鲁_ e ；昌盎= = 昌昌昌皇舞昌兰；= ： 1 2 国内外概况 1 2 1 数据挖掘工具现状简介 在数据挖掘技术日益发展的今天，许多数据挖掘的商业软件工具也逐渐问世。 数据挖掘工具主要有两类：特定领域的数据挖掘工具和通用的数据挖掘工具。 特定领域的数据挖掘工具针对某个特定领域的问题提供解决方案。在设计算法 的时候，充分考虑到数据、需求的特殊性，并作了优化。对任何领域，都可以丌发 特定的数据挖掘工具。例如，i b m 公司的a d v a n c e d s c o u t 系统针对n b a 的数据，帮 助教练优化战术组合；加州理工学院喷气推进实验室与天文科学家合作开发的 s k i c a t 系统，帮助天文学家发现遥远的类星体；芬兰赫尔辛基大学计算机科学系开 发的t a s a ，帮助预测网络通信中的警报p j 。特定领域的数据挖掘工具针对性比较强， 只能用于一种应用：也f 因为针对性强，往往采用特殊的算法，可以处理特殊的数 据，实现特殊的目的，发现的知识可靠度也比较高。 通用的数据挖掘工具不区分具体数据的含义，采用通用的挖掘算法，处理常见 的数据类型，一般提供六种模式。例如，i b m 公司a l m a d e n 研究中心开发的q u e s t 系统，s g i 公司开发的m i n e s e t 系统，加拿大s i m o n f r a s e r 大学开发的d b m i n e r 系统。 通用的数据挖掘工具可以做多种模式的挖掘，挖掘什么、用什么来挖掘都由用户根 据自己的应用来选折。 下面简单介绍几种数据挖掘工具： 1 q u e s t q u e s t 是m m 公司a l m a d e n 研究中心开发的一个多任务数据挖掘系统，目的 是为新一代决策支持系统的应用开发提供高效的数据开采基本构件。系统具有如下 特点： ( 1 1 提供了专门在大型数据库上进行各种开采的功能：关联规则发现、序列模式 发现、时间序列聚类、决策树分类、递增式主动开采等。 ( 2 ) 各种开采算法具有近似线性( 0 ( n ) ) 计算复杂度，可适用于任意大小的数据库。 ( 3 ) 算法具有找全性，即能将所有满足指定类型的模式全部寻找出来。 f 4 ) 为各种发现功能设计了相应的并行算法。 2 m 血e s c t m i n e s e t 是由s g i 公司和美国s t a n d f o r d 大学联合开发的多任务数据挖掘系统。 m i n e s e t 集成多种数据挖掘算法和可视化工具，帮助用户直观地、实时地发掘、理解 大量数据背后的知识。m i n e s e t 有如下特点： ( 1 ) m i n e s e t 以先进的可视化显示方法闻名于世。 华中科技大学硕士学位论文 ( 2 ) 提供多种数据挖掘模式。包括分类器、回归模式、关联规则、聚类、判断列 重要度。支持多种关系数据库。可以直接从o r a c l e 、工n f o r m i x ，s y b a s e 的表读取数 据，也可以通过s q l 命令执行查询。 ( 3 ) 多种数据转换功能。在进行挖掘前，m i n e s e t 可以去除不必要的数据项，统 计、集合、分组数据，转换数据类型，构造表达式由己有数据项生成新的数据项， 对数据采样等。 ( 4 ) 操作简单、支持国际字符、可以直接发布到w e b 。 3 d b m i n e r m i n e r 是加拿大s i m o n f r a s e r 大学开发的一个多任务数据挖掘系统，它的前身是 d b l e a r n j 。该系统设计的目的是把关系数据库和数据开采集成在一起，以面向属性 的多级概念为基础发现各种知识。d b m i n e r 系统具有如下特色： ( 1 ) 能完成多种知识的发现：泛化规则、特性规则、关联规则、分类规则、演化 知识、偏离知识等p j 。 ( 2 ) 综合了多种数据开采技术：面向属性的归纳、统计分析、逐级深化发现多级 规则、元规则引导发现等方法。 ( 3 ) 提出了一种交互式的类s q l 语言一数据开采查询语言d m q l 。 ( 4 ) 实现了基于客户服务器体系结构的u n i x 和p c ( w i n d o w s n t ) 版本的系统。 近年来数据挖掘也逐渐引起了我国许多学校和科研机构的关注，他们投入大量 精力进行数据挖掘语言和挖掘工具的开发研究并取得了可喜的成果，例如有西安交 大和上海复旦的数据挖掘组等。 1 2 2 关联规则研究状况 关联规则分为基于事务数据库的单维关联规则和基于关系数据库的多维关联规 则。其中多维关联规则又可分为维间多维关联规则和混合维关联规则。关联规则挖 掘性能的关键主要体现在频繁项集挖掘算法的性能上。由于关联规则是数据挖掘中 一种重要的模式，许多解决策略不断被提出。其中比较著名的是以连接和剪枝的方 法获取候选集进而得到频繁项集的a p r i o r i 算法，以及基于a p r i o r i 算法之上的一些 改进算法，如划分和事务压缩等方法，除此还有不需要获得候选集的挖掘算法。本 文中运用到的基于散列的优化技术也是基于a p r i o r i 算法的改进算法。 1 3 课题主要研究工作 课题研究主要是建立一个基于教学管理信息的关联规则挖掘系统。通过对学生 华中科技大学硕士学位论文 的招生信息、在校表现和就业信息的挖掘获得高校培养学生、了解学生的有用信息。 要建立的教学管理系统分为前台的数据库处理和后台的联机分析挖掘两部分。 研究的工作主要集中在后台的挖掘系统部分，最终实现友好界面并可以实现多种模 式挖掘的综合挖掘系统。 通过在教学管理系统中的具体实践和运用，对多维关联规则数据挖掘技术进行 探索，实现基于多维频繁谓词进行混合维关联规则数据挖掘的一种实用的方法。基 于多维的频繁项集的挖掘算法主要分为两个步骤： 第一步是对学生特征属性进行维间关联规则挖掘，找出频繁谓词，这一过程借 助数据立方体工具实现。 第二步是较复杂的基于多维的频繁项集的算法的实现及关联规则生成。这时需 要以第一步生成的多维规则结果为约束条件，对学生选课倾向进行挖掘。通过对基 于多维频繁项集的算法进行探索和优化，采用维搜索和散列的技术方法使系统的挖 掘性能大大提高。 兴趣度是关联规则挖掘中经常要考虑的一个问题，通过计算相关度判断出有用 的关联规则。 华中科技大学硕士学位论文 2 1 数据挖掘 2 数据挖掘背景知识介绍 数据挖掘是一个交叉学科领域，受多个学科影响，包括数据库系统、统计学、机 器学习、可视化和信息科学。数据挖掘确切地说是数据库中知识发现的一个步骤，但 却是最重要的一步，因为它发现隐藏的模式。典型的数据挖掘系统具有以下几个主 要成分，见图2 1 。 图2 1 数据挖掘系统 ( 1 ) 数据库、数据仓库或其它信息库：这是一个或一组数据库、数据仓库、电子 表格或其它类型的信息库。可以在数据上进行数据清理和集成。 ( 2 ) 数据库或数据仓库服务器：根据用户的数据挖掘请求，数据库或数据仓库服 务器负责提取相关数据。 ( 3 ) 知识库：这是领域知识，用于指导搜索，或评估结果模式的兴趣度。这种知 识可能包括概念分层，用于将属性或属性值组织成不同的抽象层。 ( 4 ) 数据挖掘引擎：这是数据挖掘系统基本的部分，由一组功能模块组成，用于 特征化、关联、分类、聚类分析以及演变和偏差分析。 ( 5 ) 模式评估模块：此模块使用兴趣度度量，并与数据挖掘模块交互，以便将收 华中科技大学硕士学位论文 集聚集在有趣的模式上。 ( 6 ) 图形用户界面：本模块在用户和数据挖掘系统之间通讯，允许用户与系统交 互，指定数据挖掘查询或任务，提供信息。 图2 2 给出的是实际中一种基于数据仓库的通用数据挖掘系统的结构框架【“。 图2 2 基于数据仓库的通用数据挖掘系统的结构框架 6 华中科技大学硕士学位论文 原则上讲，数据挖握可以在任何类型的信息存储上进行。这包括关系数据库、 数据仓库、事务数据库、高级数据库系统、展开文件和w w w 。 ( 1 ) 关系数据库 关系数据库管理系统( d b m s ) ，由一组内部相关的数据，和一组管理和存取数据 的软件程序组成。例如，在教学管理系统中有以下几张对我们很重要的关系数据库 表，如表2 1 、表2 2 、表2 3 。 表2 1 毕业生信息一个人信息表t _ g r a d u a t o r g r 学号姓名性别 院系名称专业名称 2 0 0 0 0 1 0 3 4 王倩 0 2 计算机科学技术系计算机多媒体 2 0 0 0 0 1 0 3 5 王瑞 0 1 计算机科学技术系计算机网络 表2 2 毕业生信息一综合能力表tg r a d u a t o rz h n l 学号办公应用高级操作等级平面设计等级网页设计等级网络管理等级 2 0 0 0 0 1 0 3 40 10 20 30 3 2 0 0 0 0 3 0 3 5 0 3 0 30 2 0 1 表2 3 毕业生信息就业表t _ g r a d u a t o r j y b 学号单位性质月收入 2 0 0 0 0 1 0 3 40 3 1 0 0 0 以上 2 0 0 0 0 3 0 3 50 3 2 0 0 0 以上 这三张表以学号字段相互关联。关系数据库是数据挖掘最丰富、最流行的数据 源，因此是数据挖掘研究的主要数据形式。 f 2 1 数据仓库 数据仓库是从多个数据源收集的信息存储，存放在一个一致的模式下，并通常 驻留在单个站点。数据仓库通过数据清理、数据变换、数据集成、数据装入和定期 数据刷新来构造。 通常，数据仓库用多维数据库结构建模。其中，每一维对应模式中的一个或一 组属性，每个单元存放某个聚集度量值，如c o u n t 。数据仓库的实际物理结构可以是 关系数据存储或多维数据立方体。微软公司的o l a fs e r v i c e s 要求数据仓库具有一个 非常特殊的表单，即以一个实际表格为特征的表单。为了便于o l a ps e r v i c e s 的使用， 实际表格必须包含能够展现所需的量度的最底层的细节的行。例如，在学生系统中 最后应通过对数据的预处理形成如表2 4 格式的表单。 7 华中科技大学硕士学位论文 表2 4 数据的预处理形成类似如下格式的表单 办公应用高级平面设网页设网络管月收入 学号性别操作员等级计等级计等级理等级等级计数 2 0 0 0 0 1 0 3 4 0 20 10 20 30 31 0 0 0 以上1 2 0 0 0 0 3 0 3 5 o l0 30 30 20 12 0 0 0 以上1 通过提供多维数据视图和汇总数据的预计算，数据仓库非常适合联机分析处理 ( o l a p ) 蚋。见图2 3 。 数据源3 图2 3 典型的数据仓库结构 ( 3 ) 事务数据库 事务数据库由一个文件组成，其中每个记录代表一个事务。通常，一个事务包 含一个唯一的事务标识号( t r a m i d ) ，和一个组成事务的项的列表( 如学生的选课信 息) ，在教学管理系统中，存在一张学生选课的事务信息表，见表2 ，5 。 表2 5 学生选课的事务信息表 学号 选修课代码 2 0 0 0 0 1 0 3 4 k l ，k 4 ，i 【5 2 0 0 0 0 3 0 3 5 k 2 ，k 3 ，k 5 2 0 0 0 0 1 0 3 4 k 1 ，k 4 ，k 6 ( 4 ) 高级数据库系统和高级数据库应用 随着数据库技术的发展，出现了新的应用需求。包括处理空间数据、工程设计数据、 日一曰一日 华中科技大学硕士学位论文 多媒体数据及唧等。为了响应这些需求，丌发了高级数据库系统和面向特殊应用 的数据库系统。例如，面向对象和对象一关系数据库系统、空间数据库系统和w w w 的全球信息系统。 2 2 数据挖掘的类型模式 数据挖掘任务一般可以分为两类p j ：描述型和预测型。描述型挖掘任务刻划数据 库中数据的一般特性。预测型挖掘任务在当前的数据上进行推断，以进行预测。 有时用户并不知道他们的数据中什么类型的模式是有趣的，因此可能想并行地 搜索多种模式。所以一个成熟的挖掘系统应能挖掘多种类型的模式，以适应不同的 用户需求或不同的应用h 。实用的数据挖掘系统应允许用户给出提示，指导或聚焦 有趣模式的搜索。 以下是几种主要的知识类型： 1 概念类描述：特征化和区分 数据可以与类和概念相关联。用汇总的、简洁的、精确的方式描述每个类和概 念是必要的。这种描述可以通过数据特征化和数据区分的方法来得到。数据特征化 是目标类数据的一般特征或特性的汇总。数据区分是将目标类对象的一般特征和多 个对比类对象的一般特征比较。 2 联分析 关联分析发现关联规则，这些规则展示属性值频繁地在给定数据集中一起出 现的条件。关联规则是本文要重点研究的模式，后面会详细介绍。 3 类和预测 分类是找出描述并区分数据类或概念的模型，以便能够使用模型预测类标记未 知的对象类。导出模型是基于对训练数据集( 即类标记已知的数据对象) 的分析。 4 类分析 与分类和预测不同，聚类分析数据对象，而不考虑己知的类标记。其它的模式 还有孤立点分析及演变分析等。 应当提出的是并不是所有的挖掘出的模式都是有趣的。实际上，对于给定的用 户，在可能产生的模式中，只有一小部分是他感兴趣的。存在一些模式兴趣度的客 观度量，如支持度和置信度。除此之外也有模式兴趣度的主观度量。对于关联规则 模式的兴趣度问题将在后面详细讨论。 9 华中科技大学顽士学位论文 2 3 数据挖掘中的挖掘性能问题 这包括数据挖掘算法的有效性、可伸缩性和并行处理。有效性和可伸缩性是指 对于大型数据库数据挖掘算法的运行时间必须是可预计和可接受的。解决挖掘算法 中的有效性和可伸缩性是系统实现的关键问题。此外，越来越复杂化和多样化的数 据库类型也使数据挖掘面临巨大的挑战。 2 4 数据仓库和数据挖掘的0 l a p 技术 数据仓库是伴随着决策支持系统的演化发展而逐渐发展起来的。数据仓库是一 个面向主题的、集成的、时变的、非易失的数据集合，支持管理部门的决策过程。 数据仓库的构建需要数据集成、数据清理和数据统一。数据仓库也是数据挖掘的重 要预处理步骤。此外，数据仓库提供联机分析处理( o l a p ) i 具，用于各种多维数据 分析。也有利于有效的数据挖掘。o l a p 是使得数据仓库数据能容易访问的工具。数 据仓库应该具有检索迅速、数据具有永久的一致性、拥有简单易用的浏览工具、数 据必须完整可靠等要素。 1 数据仓库的特征 ( 1 ) 面向主题：数据仓库围绕一些主题组织，如顾客、供应商、产品、招生、就 业等。数据仓库关注决策者的数据建模与分析，而不是集中于组织机构的日常操作 和事务处理。 ( 2 ) 集成的：通常，构造数据仓库是将多个异种数据源，如关系数据库、一般文 件和联机事务处理记录，集成在一起。使用数据清理和集成技术，确保命名约定编 码结构的一致性。 ( 3 ) 时变的：数据存储从历史的角度提供信息。数据仓库中的关键结构，隐式或 显式样地包含时间元素。 ( 4 ) 非易失性：数据仓库总是物理地分离存放数据：数据仓库不需要事务处理、恢 复和并发控制机制，它只需要数据的初始化装入和数据访问操作 之所以不直接从操作数据库上进行联机分析处理，而是另外花时间和资源建立 一个分离的数据仓库，主要是考虑到提高两个系统的性能。因为数据仓库的查询通 常是复杂的，涉及大量数据在汇总级的计算，可能需要特殊的数据组织、存取方法 和基于多维视图的实现方法。在操作数据库上处理o l a p 操作，可能会大大降低操 作任务的性能。 此外，操作数据库支持多事务的并行处理，需要加锁和日志等并行控制和恢复 机制，以确保一致性和事务的强壮性。而o l a p 查询只需要对数据记录进行只读访 1 0 华中科技大学硕士学位论文 问，以进行汇总和聚集。如果将并行控制和恢复机制用于这种o l a p 操作，就会危 害并行事务的运行，从而大大降低o l t p 系统的吞吐量。另外一点就是决策支持需 要历史数据，而操作数据库一般不维护历史数据。 2 多维数据模型和数据立方体 数据仓库和o l a p 工具基于多维数据模型【i “，该模型将数据看作是数据立方体 的形式。数据立方体允许以多维对数据进行建模和观察。它由维和事实定义。维是 一个组织想要记录的透视或实体。每一个维都与一个维表与之关联。多维数据模型 围绕中心主题组织。该主题用事实表示。事实是数值度量的。事实表包括事实的名 称或度量，以及每个相关维表的关键字。 现实世界中，立方体这个词指的是三维的物体。而在这里，立方体只是指具体 的报表中所包含数值的存储位置。同它的维无关。立方体可以少到只有一维或者多 到有6 4 维， 图2 4 是以三维角度观察学生数据的例子。三维分别是平面设计等级、网页设计 等级和学生就业收入等级。 月收入1 0 0 0 以下 月收入1 0 0 0 以上 月收入2 0 0 0 以上 平面设计不合格 平面设计合格 平面设计优秀 图2 4 毕业生就业收入的3 - o 立方体表 网页设计优秀 网页设计合格 网页设计不合格 多维数据模型可以以星型模式、雪花模式或事实星座模式存在。最常见的模式 是星型模式。多维数据模型有上卷、下铺、切片、转轴等操作。图2 5 是学生就业数 据仓库的星型模式。 3 三层数据仓库结构 ( 1 ) 底层是数据仓库服务器，一般是个关系数据库系统。由操作数据库和外部 数据源提取数据。使用网间连接程序来实现，允许客户程序产生s q l 代码【j “。 ( 2 ) 中间层是o l a p 服务器，其典型的实现或者是关系o l a p 模型，或者是多 华中科技大学硕士学位论文 维o l a p 模型。 ( 3 ) 顶层是客户，包括查询和报告工具、分析和数据挖掘工具。 4 o l a p 服务器类型 服务器类型有三种，o l a p 服务器为用户提供来自数据仓库的多维数据，用户不 必关心数据如何存放和存放在何处。 ( 1 ) 关系o l a p 服务器( r o l a p ) ：介于关系的后端服务器和客户的前端工具之 间。使用一个关系表的独立集来存储服务器用于计算立方体的汇总数据。 ( 2 ) o l a p 服务器( m o l a p ) ：它将所有的数据和所有的汇总值复制给服务器，用 一种优化的多维格式保存。 ( 3 ) 混合o l a p 服务器( h o l a p ) ：混合o l a p 服务器结合r o l a p 和m o l a p 技 术，同时具有r o l a p 的可伸缩性和m o l a p 的快速计算。 性别代码 性别代码 性别名称 厂、 办公应用高级操作代码 办公应用高级操作等级代码 平面设计 高新技术等级名称 等级代码平面设计等级代码 平面设计 厂、 等级名称 网页设计等级代码 网络管理等级代码 网络管理等级代码 网络管理等级名称 厂、 网页设计等 级代码 毕业生月收入等级代码 u 黧篡量 网页设计等 、 级名称 计数 2 。5 数据预处理 图2 5 学生就业信息数据仓库的星型模 在现实工作中，很容易发现你所要处理的大量数据并不是你所期望的完整的一 致的数据。而更可能是杂乱的充满了空缺的数据。如何让它们达到你的要求，使你 的挖掘工作变得更加有效，更加容易，这就要求你在挖掘之前进行数据的预处理。 华中科技大学硕士学位论文 数据的杂乱可能体现为它们是不完整的，比如有些你感兴趣的属性缺少属性值 或仪有聚集值。这可能是因为有线你感兴趣的数据并不可用，或者是因为输入时被 认为是不重要的，也许仅仅是因为设备故障；数据的杂乱也可能体现为包含噪声， 也就是有不正确的属性值，或者是由于来自于多个数据源而产生的编码上的数据不 一致：而且也很有可能包含大量对你的挖掘而言没什么价值的冗余数据。 数据清理有很多方法，如数据清理，数据集成，数据选择，数据变换和归约。下 面给予介绍。 2 6 1 数据清理 通过填写空缺的值，平滑噪声数据，删除孤立点，并解决不一致来清理数据。 尽管大多挖掘程序都有一些过程，处理不完整或噪声数据，但它们并非总是强壮的。 这样，使用专门的清理程序进行预处理是必要的。 1 空缺值的处理 如果学生就业信息库有个别的的学生记录不完整，如缺英文等级成绩f 正常输 入情况应有数据) ，这时怎样才能为该属性填充空缺的值呢? ( 1 ) 忽略记录：当类标号缺少时通常这样做。除非元组多个属性缺少值，否则该 方法不是很有效。 ( 2 ) 人工填写空缺值：通常该方法很费时。当数据集很大，缺少很多值时，该方 法可能行不通。 ( 3 ) 使用一个全局常量填充空缺值：将空缺的属性值用同一个常数替换。尽管该 方法简单，但不值得推荐。 ( 4 ) 使用属性的平均值填充空缺值：这无疑是一种值得推荐的方法。 ( 5 ) 使用与给定元组属同一类的所有样本的平均值。 ( 6 ) 使用最可能的值填充空缺值：这时需要使用判定树归纳等方法来预测属性的 空缺值。 其中方法( 6 ) 是最常用的，与其它方法相比，它使用现存数据的多数信息来推测 空缺值。教学管理系统库中含有大量的有空缺值记录，必需进行空缺值处理。 2 噪声数据的处理 噪声是一个测量中的随机错误或偏差。去掉噪声就是进行数据平滑的过程。 ( 1 ) 分箱：分箱方法通过考察周围的值来平滑存储数据的值。存储的数据被分配 到一些桶或箱中。 ( 2 ) 聚类：孤立点可以被聚类检测。聚类将类似的值组织成群。落在聚类集合之 外的值被视为孤立点。 华中科技大学硕士学位论文 = = = _ e 自= = = = = j _ = = = = 目_ - ；= = = = = = = = = = 一_ 此外，还有利用计算机和人工检查结合以及回归涵数来平滑数据的方法。 2 6 2 数据集成 数据分析任务大多涉及数据集成。数据集成将多个数据源中的数据结合起来存 放在一个一致的数据存储中，例如数据仓库。这些数据源可能包括多个数据库、数 据立方体或一般文件。 首先是实体识别的问题。现实中多个数据源中可能有些属性是相同的内容，但 却以不同的名称记录，这涉及实体识别的问题。通常数据库或数据仓库有元数据， 它可以帮助避免模式识别中的错误。 其次是冗余问题。如果一个属性可以由另一个表导出，则称为冗余。这些冗余 可以被相关分折检测到。 最后一个重要的问题是数据值冲突的检测与处理。对于现实中的同一实体，不 同数据源的属性可能不同。这可能是因为表示、比例和编码不同。数据这种语义上 的异种性，是数据集成的巨大挑战。 做好数据集成工作，能够减少或避免结果数据集中数据的冗余和不一致性。这 大大有助于提高挖掘的精度和效率。 此外还有数据变换和数据归约等预处理手段。 2 6 小结 本章介绍了数据挖掘中可挖掘的数据类型、可挖掘的模式、数据仓库和o l a p 技术这些和研究课题相关的背景知识，并介绍了相关知识在实现中的具体应用情况。 1 4 华中科技大学硕士学位论文 3 基于多维频繁谓词挖掘多维关联规则算法及理论基础 3 1关联规则相关知识 关联规则是数据挖掘中一个主要的挖掘模式。关联规则挖掘发现大量数据中项 集之间有趣的关联或相关关系。 关联规则的一个经典的例子是对顾客购物的分析。通过发现顾客放入其购物兹 中不同商品之间的关系，分析顾客的购买习惯。通过了解哪些商品频繁地被顾客同 时购买，可以帮助商家制定营销策略。例如，在同一次去超级市场，如果发现顾客 购买牛奶的同时，很可能也购买面包，这种信息可以引导销售。比如，可以将牛奶 和面包的货架尽可能放近一些。 3 1 1 关联规则基本概念 通过获得教学管理系统中有用的信息知识，可以帮助校方更有针对性地安排教 学培养计划。比如，如果发现女生的平面设计等级比男生普遍要高，那么学校可以 有意识地加强男生的平面设计培训。又比如，性别为男的学生倾向于网络管理的考 证培训，性别为女的学生倾向平面设计的考证培训，可以用以下关联规则表示： 性别】男= 【网络管理】优秀 s u p p o r t = l o ，c o n f i d e n c e = 3 0 】 规则的支持度和置信度是规则的两个兴趣度度量。分别反映发现的规则的有用 性和确定性。上式的支持度1 0 意味着所有学生中有1 0 的男生网络管理培训获得 优秀等级。置信度5 0 意味着3 0 的男生获得网络管理培训i 优秀等级。如果关联规 则满足最小支持度阀值和最小置信度阀值，则认为是有趣的。关联规则的挖掘问题 可形式化描述如下： 设i - - iz ，i 2 ，i 。 是由m 个不同的项目组成的集合。给定一个事务数据库d ， 其中每一个事务t 是i 中一组项目的集合，即t c i ，t 有一个唯一的标识符t i d 。若项 集a c i 且a c t ，则事务t 包含项集a 。一条相联规则就是形如a 母b 的蕴涵式，其 中a c i ，b c l ，a n b = 。相联规则a _ b 成立的条件是： 1 支持度s ，即事务数据库d 中至少有s 的事务包含a n b 。 s u p p o r t ( a = b ) = - p ( a r ib ) 2 置信度c 。即在事务数据库d 中包含a 的事务至少有c 同时也包含b 。 c o n f i d e n c e ( a = b ) = p ( b a ) 在本文中，用到一个学生选课的事务记录表，如表3 1 。 华中科技大学硕士学位论文 表3 。1 学生选课的信息表 学号 选课项 2 0 0 0 0 1 0 1 k l ，k 3 ，k 5 2 0 0 0 0 1 0 2 k 2 ，k 5 2 0 0 0 0 3 0 3 k 1 ，k 4 ，k 6 2 0 0 0 0 1 0 4k 1 k 6 2 0 0 0 0 1 0 5 k 2 ，k 5 ，k 6 2 0 0 0 0 1 0 6k 5 ，k 6 表中的学号起到事务号t i d 的作用，而k 0 1 ，k 0 2 ，k 0 3 ，k 0 4 ，k 0 5 组成项的 集合i ，对于这样一张事务记录表，可以稍作变形而转存到一个事务数据库d 中的表 里，见表3 2 。挖掘的过程就是扫描这个事务数据表而找出所有满足最小支持度阀值 和最小置信度阀值的频繁项集合和关联规则。 表3 2 学生选课的事务数据库表 学号选课项 2 0 0 0 0 1 0 1 k l 2 0 0 0 0 1 0 1 k 3 2 0 0 0 0 1 0 1 k 5 2 0 0 0 0 1 0 2 k 2 2 0 0 0 0 1 0 2 i ( 5 同时满足用户给定的最小支持度和最小置信度的关联规则称为强规则。项的集 合称为项集( i t e m s e t ) 。包含k 个项的项集称为k 一顼集。如选课集合 k 1 ，k 6 ) 是一个 二项集。挖掘关联规则可以分解为以下两步： 1 找出存在于事务数据库中的所有频繁项集。项集x 的支持度s u p p o r t ( x ) 不小 于用户给定的最小支持度m i n _ s u p ，则称x 为频繁项集。 2 用频繁项集生成关联规则。根据定义，这些规则必须满足最小支持度和最小 置信度。 除此外还可以使用附加的兴趣度度量。这两步中，后者比较简单，挖掘关联规 则的总体性能由第一步决定。 3 1 2 在事务数据库中挖掘单维布尔关联规则 3 1 2 1h p r i o r i 算法t 使用候选项集寻找频繁项集 这种单维、单层、布尔关联规则是关联规则的最简单形式。首先介绍一下a p r i o r i 1 6 华中科技大学硕士学位论文 算法。a p r i o r i 算法是由a g r a w a l 等人提出的，是一种最有影响的挖掘布尔关联规则 频繁项集的算法。进行改进后可以进行许多其它类型关联规则的挖掘。 a p r i o r i 算法使用一种称作逐层搜索的迭代方法。k 项集用于搜索( k + 1 ) 项集。首 先找出频繁l 一项集的集合。该集合记作l l ，l 1 用于找频繁2 - 项集的集合l 2 ，l 2 而 用于找l 3 ，如此下去，直到不能找到频繁k 一项集。找每个l k 需要一次数据库扫描。 频繁项集挖掘有一个重要的性质可以用于提高频繁项集产生的效率，那就是频 繁项集的所有非空子集也都必须也是频繁的。原因如下：假如一个非空子集i 不是频 繁的，那么任意项a 加到i ，则结果集i u a 不可能比i 更频繁出现，也就是说这样 会得到原来的频繁项集也不是频繁的错误结论。所以说频繁项集的所有非空子集也 都必须也是频繁的。 利用这一性质我们看看如何由l k - l 找l k 。这是分连接和剪枝两个步骤进行的。 1 连接步 为找l k ，通过l k - 1 与自己连接产生候选k - 项集的集合。该候选项集的集合记作 c k 。设1 1 和i z 是l k 1 中的项集，记号l l j 表示l i 的第j 项。为方便计，假定事务或 项集中的项按字典次序排列。执行连接l k 1 0 。l k _ i ，如果l i 和l 2 的前k - 2 个项相同， 则lk i 是可以连接的，条件l l k - 1 ：l 2 k - 1 保证不产生重复。连接i i 和1 2 产生的结 果项集是l i 1 l i 2 l 1 k 一1 l 2 k 一1 】。 2 剪枝步 c k 是l k 的超集，它的成员可以是也可以不是频繁的，但所有的频繁k 一项集都 包含在c k 中，扫描数据库，确定c k 中每个候选的计数，从而确定l k 。然而，c k 可 能很大，这样所涉及的计算量就很大。但我们知道，任何非频繁的( k 1 ) 一项集都不可 能是频繁k 项集的子集。因此，如果一个候选k 一项集的( k 一1 ) 一子集不在l k 1 中，则该 候选也不可能是频繁的，从而可以从c k 中删除。因而也减少了计算量。 下面是挖掘关联规则频繁项集的a p r i o r i 算法的伪代码： 输入：事务数据库d ；最小支持度r a i n s u p 输出：d 中的频繁项集l 方法： ( 1 ) l 1 = f i n df r e q u e n t _ l i t e m s e t s ( d ) ； ( 2 ) f o r ( k = 2 ；l k 1 空；k + + ) ( 3 ) c = a p r i o r i _ g e n ( l k 1 ，m i n _ s u p ) ； f 4 1f o re a c ht r a n s a c t i o nt c d s c a ndf o rc o u n t f 5 ) c t = s u b s e t ( c k ，0 ； 华中科技大学硕士学位论文 ( 6 ) f o re a c hc a n d i d a t ec c c t ( 7 ) c c o u n 什+ ； ( 8 ) ) ( 9 ) l k = e c c k l c c o u n t r a i n _ s u p ( 1 0 ) ) ( 11 ) r e t u r nl 2 u k l k ； a p r i o r i g e n ( l k 1 ：f r e q u e n t ( k - 1 ) ；m i n _ s u p ：m i n i m u ms u p p o r tt h r e s h o l d ) ( 1 ) f o re a c hi t e m s e tl l l k 1 ( 2