（计算机应用技术专业论文）多维关联规则数据挖掘研究及其在学生信息系统中的应用.pdf

沈阳工业大学硕士学位论文 摘要 本文通过在学生信息管理系统中的具体实践和运用，对多维关联规则数据挖掘技术 进行了探索，实现了基于多维频繁项集进行多维关联规则数据挖掘的一种实用高效的方 法，并建立了一个高效的学生信息关联规则挖掘系统。 对于群体的特征与行为的数据挖掘是关联规则挖掘的一种重要的也是复杂的挖掘方 向。例如在学生系统中的学生个体自然信息与他们的选课行为倾向之间的关联倾向，商 业领域中的顾客基本信息与购买倾向也属于这类情况。许多通用的数据挖掘工具，基于 对更通用的挖掘需要的考虑，而没有能对上述的挖掘需求给予足够的满足。 本文中基于多维的频繁项集的挖掘算法主要分为两个步骤。第一步是对群体特征进 行维间关联规则挖掘，本文中借助数据立方体工具实现这一过程。第二步是求基于多维 的频繁项集的算法的实现及关联规则生成。这时需要以第一步生成的多维规则结果为约 束条件，对群体行为的关联倾向进行挖掘。本文中对基于多维的频繁项集的算法进行了 探索和算法优化，尤其是通过采用了维搜索和散列的技术方法而使得系统的挖掘性能大 大提高。 同时通过在学生信息系统中的具体挖掘实践，也得n t 许多有价值的信息，这些知 识在帮助校方更好地进行学生的培养、对学生表现情况的掌握以及课程的安排等方面无 疑具有重要的指导意义。 兴趣度是关联规则挖掘中经常要考虑的一个问题。本文通过相关度的概念对含有负 属性项的关联规则生成方法进行了探索，并给出了相应算法。 关键词：数据挖掘，多维频繁项集，关联规则 鲨堕三些奎兰堡主堂焦鲨茎 m 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 ss t u d y i n g a n d a p p l y i n g i n s t u d e n t si n f o r m a t i o ns y s t e m i nt h ep a p e r t h em e a i l si sr e s e a r c h e d t 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 d a e f f e c t i v em e a r l sb a s e do u tm 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 s s e tb y p r a c t i c ei ns t u d e n t s i n f o r m a t i o n s y s t e m i sf o u n d m i n i n g d a t ab e t w e e n p e o p l ec h a r a c t e r s a 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 c i a t i o nr u l e s f o re x a m p l e ，a s s o c i a t i o nt r e n d b e t w e e ns t u d e n t s sn a t u r e i n f o r m a t i o na n dt h e i r b e h a v i o r b u tm a n yg e n e r a lm i n i n g t o o l sh a v en o tp a i dm u c ha t t e n t i o n t ot h e s e a s p e c t s t h e p a p e rp r o p o s e an 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 e o b t a i ni n t e r - d i m e n s i o na s s o c i a t i o n r u l e sb y c o m b i n i n g d a t ac u b e t e c h n i q u e w i t h a p r i 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 y w em i n e 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 ta n dg e n e r a t ea s s o c i a t i o n r u l e s t h i ss t e pm u s tb er e s t r i c t e d b y t h em u l t i d i m e n s i o no u t c o m e g e n e r a t e d i 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 e m i n i n ge f f i c i e n c y b ya p p l y i n g t h em e t h o dt os t u d e n t si n f o r m a t i o n s y s t e mw e o b t a i nm a n yv a l u a b l e k n o w l c d g e s w h i c ha r ch e l p f u lf o r c o l l e g e e d u c a t i o r l i n t e r e s t i n g m e a s u r e m e n t p r o b l e mo 髓n b ec o n s i d e r e di nt h ep r o c e s st om i n ea s s o c i a t i o n r u l e s t h ep a p e r p r o p o s e m e a l l st om i n ea s s o c i a t i o nr u l e sw h i c hc o n t a i n n e g a t i v e c h a r a c t e ri t e m b yc o r r e l a t i o nm e a s u r e m e n t 1 辙w o r d s ：脚辆m i n i n g ，m u l t i d i m e n s i o n a l f r e q u e n ti t e m ss e t ，a s s o c i a t i o nr u l e s 2 独。创性说明 本人郑重声明：所呈交的论文是我个人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得 沈阳工业大学或其他教育机构的学位或证书所使用过的材料。与我一同 工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表 示了谢意。 、 、 签名：仁扯日期：1 签立盟 关于论文使用授权的说明 本人完全了解沈阳工业大学有关保留、使用学位论文的规定，即： 学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公 布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论 文。 ( 保密的论文在解密后应遵循此规定) 魏阜弛导燧名：经纽嗽坦u ：型 沈阳工业大学硕士学位论文 引言 随着数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积累的数据越来 越多。激增的数据背后隐藏着许多重要的信息，人们希望能够对其进行更高层次的分 析，以便更好地利用这些数据。目前的数据库系统可以高效地实现数据的录入、查询、 统计等功能，但无法发现数据中存在的关系和规则，无法根据现有的数据预测未来的发 展趋势。缺乏挖掘数据背后隐藏的知识的手段，导致了“数据爆炸但知识贫乏”的现 象。 计算机技术的另一领域人工智能自1 9 5 6 年诞生之后取得了重大进展。经历了 博弈时期、自然语言理解、知识工程等阶段，目前的研究热点是机器学习【4 i 。机器学习 是用计算机模拟人类学习的- - f q 乖b 学，比较成熟的算法有神经网络、遗传算法等。 用数据库管理系统来存储数据，用机器学习的方法来分析数据，挖掘大量数据背后 的知识，这两者的结合促成了数据库中的知识发现( ) d ：k n o w l e d g e d i s c o v e r y i n d a t a b a s e s ) 的产生。实际上，数据库中的知识发现是- - i 1 交叉性学科，涉及至g 机器学 习、模式识别、统计学、智能数据库、知识获取、数据可视化、高性能计算、专家系统 等多个领域【l o j 。从数据库中发现出来的知识可以用在信息管理、过程控制、科学研究、 决策支持等许多方面。 1 9 8 9 年8 月在美国底特律召开的第1 1 届国际人工智能联合会议的专题讨论会上首 次出现k d d 这个术语。随后在1 9 9 1 年、1 9 9 3 年和1 9 9 4 年都举行k d d 专题讨论会， 汇集来自各个领域的研究人员和应用开发者，集中讨论数据统计、海量数据分析算法、 知识表示、知识运用等问题。随着参与人员的不断增多，k d d 国际会议发展成为年 会。1 9 9 8 年在美国纽约举行的第四届知识发现与数据挖掘国际学术会议不仅进行了学 术讨论，并且有3 0 多家软件公司展示了他们的数据挖掘软件产品，不少软件已在北 美、欧洲等国得到应用。 数据挖掘是k d d 最核一i i , 的部分，是采用机器学习、统计等方法进行知识学习 沈阳工业大学硕士学位论文 的阶段。数据挖掘算法的好坏将直接影响到所发现知识的好坏。目前大多数的研究都集 中在数据挖掘算法和应用上。人们往往不严格区分数据挖掘和数据库中的知识发现，把 两者混淆使用。一般在科研领域中称为k j ) d ，而在工程领域则称为数据挖掘。 数据挖掘可以概括为从大量数据中提取或挖掘知识。可以说数据挖掘是建立在知识 与数据之间的一座桥梁。经过十多年的工作，数据挖掘技术的研究与应用已取得了很大 的成果。数据挖掘现在越来越为更多的人们所关注，被认为是未来最有发展前景和广阔 市场潜力的新兴学科之一。 数据挖掘技术目前已经有不少成功的范例其实在日常生活中我们也可以看到许多 数据挖掘的应用例如，如果你在一家比较著名的电子商务网站购买了一张周星驰的经典 搞笑片”大话西游”该网站会提醒你， 【购买该商品的用户还买了这些商品】 行运一条龙 9 7 家有喜事 武状元苏乞儿 月光宝盒 秀兰邓波儿( 12 套装) 这些就是用数据挖掘技术从购买这部片子的人群中统计出来的当然这只是一种比 较简单的应用更复杂的应用见下面这个例子： 美国f i r s t a r 银行使用m a r k s m a n 数据挖掘工具，根据客户的消费模式预测何时为 客户提供何种产品。f i r s t a x 银行市场调查和数据库营销部经理发现：公共数据库中存 储着关于每位消费者的大量信息，关键是要透彻分析消费者投入到新产品中的原因，在 数据库中找到一种模式，从而能够为每种新产品找到最合适的消费者。m a r k s m a n 能读 取8 0 0 到1 0 0 0 个变量并且给它们赋值，根据消费者是否有家庭财产贷款、赊帐卡、存 款证或其它储蓄、投资产品，将它们分成若干组，然后使用数据挖掘工具预测何时向每 位消费者提供哪种产品。预测准客户的需要是美国商业银行的竞争优势。 2 沈阳工业大学硕士学位论文 关联规则是数据挖掘的重要模式。学校中学生信息数据库有大量可供挖掘的知 识，例如什么样在校表现的学生有什么样的就业倾向，什么样类型的学生有什么样 的选课倾向这些都是校方希望掌握的信息，对学生的培养工作无疑有重要指导意 义。上述知识的发现都需要运用关联规则的知识方法，为此，本文对于学生特征和 选谋行为之间数据的关联规则尤其是基于多维频繁项集的混合维关联规则挖掘方法 进行了大胆探索。 本文中基于多维的频繁项集的挖掘算法主要分为两个步骤。第一步是对群体特征进 行维间关联规则挖掘，本文中借助数据立方体工具实现这一过程。第二步是求基于多维 的频繁项集的算法的实现及关联规则生成。这时需要以第一步生成的多维规则结果为约 束条件，对群体行为的关联倾向进行挖掘。本文中对基于多维的频繁项集的算法进行了 探索和算法优化尤其是通过采用了维搜索和散列的技术方法而使得系统的挖掘性能大 大提高。兴趣度是关联规则挖掘中经常要考虑的一个问题。本文通过相关度的概念对含 有负属性项的关联规则生成方法进行了探索，并给出了相应算法。 本文中首先介绍了数据挖掘相关的背景知识，之后在第三部分具体介绍了实现基于 多维频繁项集挖掘多维关联规则的算法和理论基础，第四部分给出了系统实现的过程。 3 沈阳工业大学硕士学位论文 1 绪论 1 1 国内外研究发展概况简介 1 1 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 ，帮助预测网络通 信中的警报。“。 特定领域的数据挖掘工具针对性比较强，只能用于一种应用；也正因为针对性强， 往往采用特殊的算法，可以处理特殊的数据，实现特殊的目的发现的知识可靠度也比 较高。 通用的数据挖掘工具不区分具体数据的含义，采用通用的挖掘算法。处理常见的数 据类型，一般提供六种模式。例如，i b m 公司h 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 是i b m 公司a 1 m a d e n 研究中心开发的一个多任务数据挖掘系统，目的是为新一 代决策支持系统的应用开发提供高效的数据开采基本构件。系统具有如下特点： 提供了专门在大型数据库上进行各种开采的功能：关联规则发现、序列模式发现、 时间序列聚类、决策树分类、递增式主动开采等。 各种开采算法具有近似线性( 0 ( n ) ) 计算复杂度，可适用于任意大小的数据库。 4 沈阳工业大学硕士学位论文 算法具有找全性，即能将所有满足指定类型的模式全部寻找出来。 为各种发现功能设计了相应的并行算法。 ( 2 ) m i n e s e 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 有如下特点： m i n e s e t 以先进的可视化显示方法闻名于世。 提供多种数据挖掘模式。包括分类器、回归模式、关联规则、聚类、判断列重要 度。 支持多种关系数据库。可以直接从o r a c l e 、i n f o r m i x 、s y b a s e 的表读取数据，也可 以通过s q l 命令执行查询。 多种数据转换功能。在进行挖掘前，m i n e s e t 可以去除不必要的数据项，统计、集 合、分组数据，转换数据类型，构造表达式由已有数据项生成新的数据项，对数据采样 等。 操作简单、支持国际字符、可以直接发布到w e b 。 ( 3 ) d b m i n e r 1 d b m i n e r 是加拿大s i m o n f r a s e r 大学开发的一个多任务数据挖掘系统，它的前身是 d b l e a r n 。该系统设计的目的是把关系数据库和数据开采集成在一起，以面向属性的多 级概念为基础发现各种知识。d b m i n e r 系统具有如下特色： 能完成多种知识的发现：泛化规则、特性规则、关联规则、分类规则、演化知识、 偏离知识等4 1 。 综合了多种数据开采技术：面向属性的归纳、统计分析、逐级深化发现多级规则、 元规则引导发现等方法。 提出了一种交互式的类s q l 语言数据开采查询语言d m q l 。 实现了基于客户服务器体系结构的u n i x 和p c ( w i n d o w s n t ) 版本的系统。 5 沈阳工业大学硕士学位论文 近年来数据挖掘也逐渐引起了我国许多学校和科研机构的关注，他们投入大量精 力进行数据挖掘语言和挖掘工具的开发研究并取得了可喜的成果，例如有西安交大和上 海复旦的数据挖掘组等。 11 2 关联规则研究状况 关联规则分为基于事务数据库的单维关联规则和基于关系数据库的多维关联规则。 其中多维关联规则又可分为维间多维关联规则和混合维关联规则。关联规则挖掘性能的 关键主要体现在频繁项集的挖掘算法的性能上。由于关联规则是数据挖掘中一种重要的 模式，许多解决策略不断被提出。其中比较著名的是以连接和剪枝的方法获取候选集进 而获得频繁项集的a p r i o r i 算法，以及基于a p r i o r i 算法之上的一些改进算法，如划分 和事务压缩等方法。本文中运用到的基于散列的优化技术也是基于a p r i o r i 算法的改进 算法。此外还有不需要获得候选集的挖掘算法等。 1 2 研究设想和意义 本文中要建立一个基于学生信息的关联规则挖掘系统。通过对学生的招生信息、在 校表现和就业信息的挖掘获得对校方培养学生，了解学生的有用信息。把数据挖掘这样 - - i - j 新兴技术应用到学生管理工作中，这在大力提倡科教兴国的今天无疑具有前瞻性的 重要意义。 要建立的学生信息管理系统分为前台的数据库处理和后台的联机分析挖掘两部分。 本文中的工作主要集中在后台的挖掘系统部分。最终应实现界面友好并可以实现多种模 式挖掘的综合挖掘系统。由于时间关系，硕士论文课题的设计阶段只能完成关联规则挖 掘部分的工作。 本文通过在学生信息管理系统中的具体实践和运用，对多维关联规则数据挖掘技术 进行了探索，实现了基于多维频繁项集进行混合维关联规则数据挖掘的一种实用高效的 方法。本文中基于多维的频繁项集的挖掘算法主要分为两个步骤。第一步是对群体特征 属性进行维间关联规则挖掘，本文中借助数据立方体工具实现这一过程。第二步是较复 杂的基于多维的频繁项集的算法的实现及关联规则生成。这时需要以第一步生成的多维 规则结果为约束条件，对群体行为事务的关联倾向进行挖掘。兴趣度是关联规则挖掘中 6 沈阳工业大学硕士学位论文 经常要考虑的一个问题。本文通过相关度的概念对含有负属性项的关联规则生成方法进 行了探索，并给出了相应算法。 7 沈阳工业大学硕士学位论文 2 背景知识介绍 本部分介绍课题研究所要用到的相关知识，并在相应处介绍课题挖掘系统对知识的 具体应用的情况。 2 1 数据挖掘“1 数据挖掘是一个交叉学科领域，受多个学科影响，包括数据库系统、统计学、机器 学习、可视化和信息科学。 数据挖掘确切地说是数据库中知识发现的一个步骤“3 ，知识发现过程由以下步骤组 成： 数据清理( 消除噪声或不一致数据) 数据集成( 多种数据源集合在一起) 数据选择( 从数据库中检索和分析任务相关的数据) 数据变换( 数据变换或统一成适合挖掘的形式，如通过汇总或聚集操作) 数据挖掘 模式评估( 根据某种兴趣度度量，识别表示知识的真正有趣的模式) 知识表示( 使用可视化和知识表示技术，向用户提供挖掘的知识) 数据挖掘只是知识发现过程中的一步，但却是最重要的一步，因为它发现隐藏的模 式。典型的数据挖掘系统具有以下几个主要成分：( 参图2 1 ) 1 ) 数据库、数据仓库或其它信息库：这是一个或一组数据库、数据仓库、电子表 格或其它类型的信息库。可以在数据上进行数据清理和集成。 2 ) 数据库或数据仓库服务器：根据用户的数据挖掘请求，数据库或数据仓库服务 器负责提取相关数据。 3 ) 知识库：这是领域知识，用于指导搜索，或评估结果模式的兴趣度。这种知识 可能包括概念分层，用于将属性或属性值组织成不同的抽象层。 4 ) 数据挖掘引擎：这是数据挖掘系统基本的部分，由一组功能模块组成，用于特 征化、关联、分类、聚类分析以及演变和偏差分析。 8 沈阳工业大学硕士学位论文 图2 1 典型的数据挖掘系统结构 5 ) 模式评估模块：此模式使用兴趣度度量，并与数据挖掘模块交互，以便将收集 聚集在有趣的模式上。模式评估模块也可以与挖掘模块集成在一起，这依赖于所用的数 据挖掘方法的实现。 6 ) 图形用户界面：本模块在用户和数据挖掘系统之间通讯，允许用户与系统交 互，指定数据挖掘查询或任务，提供信息，帮助搜索聚焦，根据数据挖掘的中间结果进 行探索式数据挖掘。此外，此成分还允许用户浏览数据库、数据仓库模式和数据结构， 评估挖掘的模式，以不同的形式对模式可视化。 从数据仓库的观点看，数据挖掘可以看作联机分析处理( o l a p ) 的高级阶段。通过 结合更高级的数据理解技术，数据挖掘比汇总型分析处理走得更远。 9 沈阳工业大学硕士学位论文 图2 2 给出的是实际中一种基于数据仓库的通用数据挖掘系统的结构框架! 。 在图2 2 中，查询协同机的作用是协同数据仓库管理系统、模型库管理系统、知识 库管理系统，共同对查询接口提交的查询请求进行处理。接到查询请求后，首先系统进 行分类和解释工作，接着查询协同机将分类和解释后形成的查询语句同时提交数据仓库 管理系统和知识库管理系统，二者并行查询。当其中的一个找到符合的结论或相反的结 论时，可通知查询协同机终止另外一个的查询任务。 用户查询上 查询分类 + l查询解释 l 图2 2 基于数据仓库的通用数据挖掘系统的结构框架 1 0 沈阳工业大学硕士学位论文 2 2 需要挖掘的数据类型 原则上讲，数据挖掘可以在任何类型的信息存储上进行。这包括关系数据库、数据 仓库、事务数据库、高级数据库系统、展开文件和、 ，、 n a ( 1 ) 关系数据库 关系数据库管理系统( d b m s ) ，由一组内部相关的数据，和一组管理和存取数据的 软件程序组成。 例如，在学生信息管理系统中有以下几张对我们很重要的关系数据库表： 表2 1 毕业生信息一自然信息表t _ g r a d u a t o r z r 就业号学号姓名性别专业名称院系名称生潭地 2 0 0 2 0 5 1 0 6 49 8 0 0 0 l 于力 o l 计算机计算机 铁岭 2 0 0 2 0 5 1 0 6 59 8 d 0 0 2 马强 0 2 计算机计算机大连 表2 2 毕业生信息一综合能力表t _ g r a d u a t o r _ z h n l 学号主修外语语种主修外语等级计算机水平相关能力证书 9 8 0 0 0 10 1o l0 2 9 8 0 0 0 20 l0 l0 3 其中，主修外语等级、计算机水平等内容依照代码通过相关字典查询。 表2 3 毕业生信息一派遣表t _ g r a d u a t o r j a q b 学号就业号单位名称单位所有制性质单位性质毕业去 向 9 8 0 0 0 l2 0 0 2 0 5 1 0 6 4 中国建筑第 0 93 10 l 三工程局 其中，单位性质、毕业去向等内容依照代码通过相关字典裔询。 这三张表以学号字段相互关联。关系数据库是数据挖掘最丰富、最流行的数据源， 因此是数据挖掘研究的主要数据形式。 沈阳工业大学硕士学位论文 ( 2 ) 数据仓库 数据仓库是从多个数据源收集的信息存储，存放在一个一致的模式下，并通常驻留 在单个站点。数据仓库通过数据清理、数据变换，数据集成、数据装入和定期数据刷新 来构造。 通常，数据仓库用多维数据库结构建模。其中，每一维对应模式中的一个或一组 属性，每个单元存放某个聚集度量值，如c o u n t 。数据仓库的实际物理结构可以是关系 数据存储或多维数据立方体。微软公司的0 l a ps e r v i c e s 要求数据仓库具有一个非常特 殊的表单，即以一个实际表格为特征的表单。为了便于o l a ps e r v i c e s 的使用，实际 表格必须包含能够展现所需的量度的最底层的细节的行。例如，在学生系统中最后应通 过对数据的预处理形成类似如下格式的表单( 表2 4 ) ： 表2 4 予处理后的学生库表结构 学号性别代码生源地类别代码外语水平代码计算机水平代码单位性质类别代码记数 9 8 0 0 0 l0 ll0 10 20 i 1 9 8 0 0 0 20 220 10 30 3 l 通过提供多维数据视图和汇总数据的预计算，数据仓库非常适合联机分析处理 ( o l a p ) 1 1 9 1 。参见图2 3 ( 3 ) 事务数据库 事务数据库由一个文件组成，其中每个记录代表一个事务。通常，一个事务包含一 个唯一的事务标识号( t r a n s _ i d ) ，和一个组成事务的项的列表( 如学生的选课信 息) ，在学生信息系统中，存在一张学生选课的事务信息表( 表2 5 ) ： 表2 5 学生选课的事务信息表 学号选惨果代码 9 8 0 0 0 1k l _ k 3 9 8 0 0 0 2 k l ，1 ( 2 ，1 ( 5 9 8 0 0 0 3k 4 k 5 1 2 沈阳工业大学硕士学位论文 数据源3 图2 3 典型的数据仓库结构 ( 4 ) 高级数据库系统和高级数据库应用 随着数据库技术的发展，出现了耨的应用需求。包括处理空间数据、工程设计数 据，多媒体数据及w 删等。为了响应这些需求，开发了高级数据库系统和面向特殊应用 的数据库系统。例如，面向对象和对象关系数据库系统，空间数据库系统和w w w 的全 球信息系统。 2 3 可挖掘的知识类型 数据挖掘任务一般可以分为两类“”：描述型和预测型。描述型挖掘任务刻划数据 库中数据的一般特性。预测型挖掘任务在当前的数据上进行推断，以进行预测。 有时用户并不知道他们的数据中什么类型的模式是有趣的，因此可能想并行地搜索 多种模式。所以一个成熟的挖掘系统应能挖掘多种类型的模式，以适应不同的用户需求 或不同的应用1 。实用的数据挖掘系统应允许用户给出提示，指导或聚焦有趣模式的搜 索。 以下是几种主要的知识类型： 概念璞描述：特征化和区分 1 3 旬一旬一旬 沈阳工业大学硕上学位沦文 数据可以与类和概念相关联。用汇总的，简洁的、精确的方式描述每个类和概：客是 必要的。这种描述可以通过数据特征化和数据区分的方法来得到。数据特征化是目标类 数据的一般特征或特性的汇总。数据区分是将目标类对象的一般特征或多个对比类对象 的一般特征比较。 关联分析 关联分析发现关联规则，这些规则展示属性值频繁地在给定数据集中一起出 现的条件。关联规则是本文要重点研究的模式，后面会详细介绍。 分类和预测 分类是找出描述并区分数据类或概念的模型，以便能够使用模型预测类标记未知的 对象类。到出模型是基于对训练数据集( 即类标记已知的数据对象) 的分析。 聚类分析 与分类和预测不同，聚类分析数据对象，而不考虑已知的类标记。其它的模式还有 孤立点分析及演变分析等。 应当提出的是并不是所有的挖掘出的模式都是有趣的。实际上，对于给定的用户， 在可能产生的模式中，只有一小部分是他感兴趣的。存在一些模式兴趣度的客观度量， 如支持度和置信度。除此之外也有模式兴趣度的主观度量。对于关联规则模式的兴趣度 问题将在后面详细讨论。 2 4 数据挖掘中的挖掘性能问题 这包括数据挖掘算法的有效性、可伸缩性和并行处理。 有效性和可伸缩性是指对于大型数据库数据挖掘算法的运行时间必须是可预计和可 接受的。解决挖掘算法中的有效性和可伸缩性是系统实现的关键问题。此外，越来越复 杂化和多样化的数据库类型也使数据挖掘面临巨大的挑战。 2 5 数据仓库及数据立方体介绍 数据仓库是伴随着决策支持系统的演化发展而逐渐发展起来的。数据仓库是一个 面向主题的，集成的、时变的、非易失的数据集合1 5 1 ，支持管理部门的决策过程。数据 仓库的构建需要数据集成、数据清理和数据统一。数据仓库也是数据挖掘的重要预处理 步骤。此外，数据仓库提供联机分析处理( o 乙蟑) 工具，用于各种多维数据分析。也 1 4 沈阳工业大学硕士学位论文 有利于有效的数据挖掘。o l a p 是使得数据仓库数据能容易访问的工具。数据仓库应该 具有检索迅速、数据具有永久的一致性、拥有简单易用的浏览工具、数据必须完整可靠 等要素。 ( 1 ) 数据仓库的特征1 5 j ： 面向主题：数据仓库围绕一些主题组织，如顾客、供应商、产品、招生、就 业等。数据仓库关注决策者的数据建模与分析，而不是集中于组织机构的日常操作 和事务处理。 集成的：通常，构造数据仓库是将多个异种数据源，如关系数据库、一般文 件和联机事务处理记录，集成在一起。使用数据清理和集成技术，确保命名约定、 编码结构的一致性。 时变的：数据存储从历史的角度提供信息。数据仓库中的关键结构，隐式或 显式样地包含时间元素。 非易失性：数据仓库总是物理地分离存放数据：数据仓库不需要事务处理、 恢复和并发控制机制，它只需要数据的初始化装入和数据访问操作 之所以不直接从操作数据库上进行联机分析处理，而是另外花时间和资源建立一个 分离的数据仓库主要是考虑到提高两个系统的性能。因为数据仓库的查询通常是复杂 的，涉及大量数据在汇总级的计算，可能需要特殊的数据组织，存取方法和基于多维视 图的实现方法。在操作数据库上处理0 l a p 操作，可能会大大降低操作任务的性能。 此外，操作数据库支持多事务的并行处理，需要加锁和日志等并行控制和恢复机 制，以确保一致性和事务的强壮性。而0 u 心查询只需要对数据记录进行只读访问，以 进行汇总和聚集。如果将并行控制和恢复机制用于这种o l a p 操作，就会危害并行事务 的运行，从而大大降低o l t p 系统的吞吐量。另外一点就是决策支持需要历史数据，而 操作数据库一般不维护历史数据。 ( 2 ) 多维数据模型和数据立方体 数据仓库和0 l a p 工具基于多维数据模型“，该模型将数据看作是数据立方体的形 式。数据立方体允许以多维对数据进行建模和观察。它由维和事实定义。维是一个组织 想要记录的透视或实体。每一个维都与一个维表与之关联。多维数据模型围绕唧i ) 主题 1 5 沈阳工业大学硕士学位论文 组织。该主题用事实表示。事实是数值度量的。事实表包括事实的名称或度量，以及每 个相关维表的关键字。 现实世界中，立方体这个词指的是三维的物体。而在这里，立方体只是指具体的报 表中所包含数值的存储位置。同它的维无关。立方体可以少到只有一维或者多到有6 4 维。 图2 4 是以三维角度观察学生数据的例子。三维分别是计算机水平等级、主修外语 水平等级和毕业分配单位性质。 多维数据模型可以以星型模式、雪花模式或事实星座模式存在a 最常见的模式是星 型模式。图2 5 是学生就业数据仓库的星型模式。 多维数据模型有上卷、下钻，切片和转轴等操作。 三资企 英语五级 计算机一级 计算机二级 计算机三级 图2 4学生分配信息数据的3 _ d 立方体表示 ( 3 ) 三层数据仓库结构【1 底层是数据仓库服务器，一般是一个关系数据库系统。由操作数据库和外部数据 源提取数据。使用网间连接程序来实现，允许客户程序产生s q l 代码。 中间层是o l a p 服务器，其典型的实现或者是关系o i a p 模型，或者是多维o l a p 模型。 顶层是客户，包括查询和报告工具、分析和数据挖掘工具。 1 6 沈阳工业大学硕士学位论文 性别代码 性别名称 维表 f 计算机水平代码1 l i 计算机水平名称 图2 5 学生就业数据仓库的星型模式 ( 4 ) o i a p 服务器类型 服务器类型有三种，o l a p 服务器为用户提供来自数据仓库的多维数据，用户不必 关心数据如何存放和存放在何处。 - 关系o l a p 服务器( r o u 岬) ：介于关系的后端服务器和客户的前端工具 之间。使用一个关系表的独立集来存储服务器用于计算立方体的汇总数据。r o l a p 对 偶尔的大量数据集合来说是最好的方法，因为它把前台的处理时间和存储需求最小化 了。 多维o l a p 服务器( m o u 心) ：它将所有的数据和所有的汇总值复制给 0 l a p 服务器用一种优化的多维格式保存。由于查询时一切都准备好了，因此 m o l a p 有三种类型中最好的查询性能。另一方面它也占用最大的空间和最长时间去准 备。而如果数据是稀疏的，存储利用率可能很低，这时应使用稀疏矩阵的压缩技术。 混合0 l 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 的快速计算。 1 7 。1 沈阳工业大学硕士学位论文 除此外，数据仓库包含了海量数据，如何使o l a p 服务器支持快速的决策查询，要 求数据仓库系统提供高效的数据立方体计算和存储。 2 6 数据预处理 在现实工作中，很容易发现你所要处理的大量数据并不是你所期望的完整的一致的 数据。而更可能是杂乱的充满了空缺的数据。如何让它们达到你的要求，使你的挖掘工 作变得更加有效，更加容易，这就要求你在挖掘之前进行数据的预处理。 数据的杂乱可能体现为它们是不完整的，比如有些你感兴趣的属性缺少属性值或仅 有聚集值。这可能是因为有些你感兴趣的数据并不可用，或者是因为输入时被认为是不 重要的，也许仅仅是因为设备故障：数据的杂乱也可能体现为包含噪声，也就是有不正 确的属性值，或者是由于来自于多个数据源而产生的编码上的数据不一致：而且也很有 可能包含大量对你的挖掘而言没什么价值的冗余数据。 数据清理有很多方法，如数据清理，数据集成，数据选择，数据变换和归约。下面 给予介绍。 2 6 1 数据清理 通过填写空缺的值，平滑噪声数据，删除孤立点，并解决不一致来清理数据。尽管 大多挖掘程序都有一些过程，处理不完整或噪声数据，但它们并非总是强壮的。这样， 使用专门的清理程序进行预处理是必要的。 ( 1 ) 空缺值的处理 如果学生就业信息库有个别的的学生记录不完整，如缺英文等级成绩( 正常输 入情况应有数据) ，这时怎样才能为该属性填充空缺的值昵? 忽略记录：当类标号缺少时通常这样做。除非元组多个属性缺少值，否则该方法 不是很有效。 人工填写空缺值：通常该方法很费时。当数据集很大，缺少很多值时，该方法可 能行不通。 使用一个全局常量填充空缺值：将空缺的属性值用同一个常数替换。尽管该方法 简单，但不值得推荐。 使用属性的平均值填充空缺值：这无疑是一种值得推荐的方法。 1 8 沈阳工业大学硕士学位论文 使用与给定元组属同一类的所有样本的平均值。 使用最可能的值填充空缺值：这时需要使用判定树归纳等方法来预测属性的空缺 值。 其中方法6 ) 是最常用的，与其它方法相比，它使用现存数据的多数信息来推测空缺 值。学生信息库中含有大量的有空缺值记录，必需进行空缺值处理。 ( 2 ) 噪声数据的处理 噪声是一个测量中的随机错误或偏差。去掉噪声就是进行数据平滑的过程。 分箱：分箱方法通过考察周围的值来平滑存储数据的值。存储的数据被分配到一 些桶或箱中。 聚类：孤立点可以被聚类检测。聚类将类似的值组织成群。落在聚类集合之外的 值被视为孤立点。 此外，还有利用计算机和人工检查结合以及回归涵数来平滑数据的方法 2 62 数据集成 数据分析任务大多涉及数据集成。数据集成将多个数据源中的数据结合起来存放在 一个一致的数据存储中，例如数据仓库。这些数据源可能包括多个数据库、数据立方体 或一般文件。 首先是实体识别的问题。现实中多个数据源中可能有些属性是相同的内容，但却以 不同的名称记录，这涉及实体识别的问题。通常数据库或数据仓库有元数据，它可以帮 助避免模式识别中的错误。 其次是冗余问题。如果一个属性可以由另一个表导出，则称为冗余。这些冗余可以 被相关分析检测到。 最后一个重要的问题是数据值冲突的检测与处理。对于现实中的同一实体，不同数 据源的属性可能不同。这可能是因为表示、比例和编码不同。数据这种语义上的异种 性，是数据集成的巨大挑战。 做好数据集成工作，能够减少或避免结果数据集中数据的冗余和不一致性。这大大 有助于提高挖掘的精度和效率。 此外还有数据变换和数据归约等预处理手段。 1 9 沈阳工业大学硕士学位论文 3 基于多维频繁项集挖掘多维关联规则算法及理论基础 3 1 关联规则相关知识 关联规则是数据挖掘中一个主要的挖掘模式。关联规则挖掘发现大量数据中项集之 间有趣的关联或相关关系。 关联规则的一个经典的例子是对顾客购物的分析。通过发现顾客放入其购物篮中不 同商品之间的关系，分析顾客的购买习惯。通过了解哪些商品频繁地被顾客同时购买， 可以帮助商家制定营销策略。例如，在同一次去超级市场，如果发现顾客购买牛奶的同 时，很可能也购买面包，这种信息可以引导销售。比如，可以将牛奶和面包的货架尽可 能放近一些。 31l 基本概念 通过获得学生信息系统中有用的信息知识，可以帮助校方更有针对性地安排教学培 养计划。比如，如果发现女同学的英语水平好于男生，那么学校可以有意识地加强男生 的英语培养。例如，性别为女的学生倾向于外语水平为优秀可以用以下关联规则表示： 性别 女= ) 外语水平 优秀 s u p p o r t = l o ，c o n f i d e n c e = 6 0 规则的支持度和置信度是规则的两个兴趣度度量。分别反映发现的规则的有用性和确定 性。上式的支持度l o 意味着所有学生中有1 0 的学生是女生而且外语水平优秀。置信 度6 0 意味着6 0 的女生外语水平优秀。如果关联规则满足最小支持度阈值和最小置信 度闽值，则认为是有趣的。关联规则的挖掘问题可形式化描述如下： 设i = i l ，i 2 ，i ) 是由m 个不同的项目组成的集合。给定一个事务数据库d ， 其中每一个事务t 是i 中一组项目的集合，即t ：i ，t 有一个唯一的标识符t i d 。若项 集a c _ t 且a 量t ，则事务t 包含项集a 。一条相联规则就是形如a = b 的蕴涵式，其中 a c l ，b 互i ，a n b = 中。相联规则a = b 成立的条件是： 1 ) 支持度s ，即事务数据库d 中至少有s 的事务包含a f 3 b 。 s u p p o r t ( a = b ) = p ( a n b ) 2 ) 置信度c 。即在事务数据库d 中包含a 的事务至少有c 9 6 同时也包含b 。 c o n f i d e n c e ( a - - b ) = p ( alb ) 2 0 沈阳工业大学硕士学位论文 在本文中，用到一个学生选课的事务记录表，表3 1 ： 表3 1 学生选课的信息表 学号选课项 9 8 0 0 0 1k 1 k 2 k 5 。 9 8 0 0 0 2k 2 ，k 4 9 8 0 0 0 3k 2 ，k 3 9 8 0 0 0 4k l ，l ( 2 k 4 9 8 0 0 0 5k 1 k 3 9 8 0 0 0 6k 2 k 3 9 8 0 0 0 7k 1 k 3 9 8 0 0 0 8k i 1 ( 2 ，k 3 k 5 9 8 0 0 0 9k 1 。l ( 2 + k 3 表中的学号起到事务号t i d 的作用，而k 0 1 ，k 0 2 ，k 0 3 ，k 0 4 ，k 0 5 组成项的 集合i ，对于这样一张事务记录表，可以稍作变形而转存到一个事务数据库d 中的表里 ( 表3 2 ) 。挖掘的过程就是扫描这个事务数据表而找出所有满足最小支持度闽值和最小 置信度阈值的频繁项集合和关联规则。 表3 2 学生选课的事务数据库表 l学号选课项 9 8 0 0 0 lk 1 9 8 0 0 0 l k 2 9 8 0 0 0 lk s 9 8 0 0 0 2k 2 9 8 0 0 0 2k 4 同时满足用户给定的最小支持度和最小置信度的关联规则称为强规则。项的集合称 为项集( i t e m s e t ) 。包含k 个项的项集称为k 一项集。如选课集合【k o i 。k 0 3 是一个二 项集。挖掘关联规则可以分解为以下两步； 2 1 沈阳工业大学硕士学位论文 ( 1 ) 找出存在于事务数据库中的所有频繁项集。项集x 的支持度s u p p o r t ( x ) 不小于用户给定的最小支持度m i n s u p ，则称x 为频繁项集。 ( 2 ) 用频繁项集生成关联规则。根据定义，这些规则必须满足最小支持度和最小置 信度。 除此外还可以使用附加的兴趣度度量。这两步中，后者比较简单，挖掘关联规则的 总体性能由第一步决定。 3 1 2由事务数据库挖掘单维布尔关联规则 3 121a p r i o r i 算法：使用候选项集寻找频繁项集 这种单维单层，布尔关联规则是关联规则的最简单形式。首先介绍一下a p r i o r