（管理科学与工程专业论文）关联挖掘在科研管理系统中的应用研究.pdf

中文摘要 摘要 随着数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积累的数 据越来越多。数据挖掘技术的应运而生使得这些数据背后隐藏着的重要信息得以 利用，也为更高层次的分析提供了科学依据。经过多年的发展，。数据挖掘的算法 已日趋成熟、稳定，且易于理解和操作，于是数据挖掘的研究重点也逐渐转向了 如何应用方面。目前，数据挖掘技术在商业、金融等领域的应用已积累了很多成 功经验。但在教育层面上的应用却还很少。近年来随着高校的不断扩招，学生人 数大幅度增加，给高校的教学、科研管理工作带来了严峻的考验，我们发现利用 高校逐年积累下来的海量的教学、科研信息，通过数据挖掘获得科学的依据、启 示，来引导高校寻求合理的教学模式，指导师生进行有效的科研工作，完全可以 使高校朝着好的方向健康、稳步的发展、前进。 本文就是将数据挖掘的技术引入到高校的科研工作中的一个应用尝试。本文 以某高校的科研管理系统为背景，运用关联挖掘的技术对其积累的科研信息进行 挖掘，来试图发现影响科研成果的关键要素，以及各科研要素间和科研成果间的 关联关系，从而为领导组织、协调师生科研工作、做出科研决策提供科学依据。 本文首先综述了数据挖掘的研究背景、意义以及数据挖掘技术在高校科研管 理中的应用现状和意义，然后在对数据挖掘相关理论、关联规则思想及主要算法 进行讨论，分析经典a 嘶o r i 算法及其存在的问题、基本解决方案后，提出了适合 本文挖掘的多维a p r i 硎算法的设计方案，并应用于本文挖掘中；接着论文介绍了 科研数据的关联挖掘系统的结构，确定了面向主题的挖掘任务，包括：科研项目 信息的挖掘、论文信息的挖掘、学术专著信息的挖掘等；设计了关联规则的实施 过程，并通过程序编码得以实现，获得了多条有启发性的关联规则，并对其进行 了解释与分析。最后本文阐述了课题研究中的一些心得及对后续科研活动的展望。 关键词：关联规则；高校科研管理；多维 p r i o r i 算法；关联挖掘系统 英文摘要 t h er e s e a r c ho nm e a p p l i c a t i o no f a s s o c i a t i o nm i n i n gi ns c i e n t i f i c r e s e a r c hm a n a g e m e n ts y s t e m a b s l t a c t w i t l lt h em p i dd e v e l o p i i l e n lo f 出曲b a s et e c b n o l o g y 锄dt l l ee x l e 璐i v ea p p l i c a 土i o 璐 o fd a l a b a m 锄a g 锄e ms y s 蛔f n ，m o r ea n dm o 他d a l ai sa c c 岫u l a t e d i n l p 0 删 m e s 鞠g ec 锄b ef 曲n db yd a t am “n gt h n o l o g y ，州c h 啪p r o v i d i e n t i 丘cb 罄i sf o r b i g h 盯l e 、r d 加a l y s i s a f t c ry e 躺o fd e v e i 叩m 锄t ，d a t a l i j l i n ga i g o r i t i l i i lh 娼b e c 砌e j n c r e 勰i n 9 1 ym a t 眦，s t ；出l e ，a n d s yt om d 髓s t a n d 锄d 唧础，血e nt h ed a t an l i n i n g m 辩a r c hh 船粤a d i l a l l ys i l i f t e di t sf b c 璐0 nh o wt oa p p l i c a t e o 叫r e n 廿y ，d a 瞳am i n i n g t e c h i l o l o g yh 覃喀龇砚皿i l l 曲e dal o to f 如c c e 嚣f i l le x p e 一c c si i it h ec o m m e r c i a l ，a n d 血锄c i a lf i e l d s b u ta p p l i c 鲥。璐f o rc d a t i a 地s t i v e r yf e w mr e c e n ty e a 曙，、i l h t h ec 0 惦t a n te ) 【p 柚s i o no fu n i v e 硌i t i e s ，t h en d b e ro f 蛐_ l d 即t ss u b s t 柚t i a l l yi n c 陀雠s ， w l l i c hh a sb f o u g h ts “e mt e s tt ot b ct 韶c h i n g i 衄t i f 沁r e a r c hm a n a g 锄e n to f l l i l i v e 巧i t i e s w ef o 岫dt l l 越m a l 【i n gu 辩o fm a 黯i v et e a c h i n g ，i e n t i f i cr e a m h i n f o 皿a l i o nw h i c hh 勰b 啪a c c u m l l l a t c df o ry e 趾_ s ，t od i o v 盯s c i e n t i f i cb 勰i sf o r c i l l i g l i t e ：衄n e n tm r o u g hd a l am i n i n g ，w i l i c h 咖n o to n l yg i l i d eu i i i v e r s 硒e s 蛳k 嘲n a b l em o d co f 栅t i o i l ，b l i ta i g i l i d a i l c c 僦l c h e 巧衄ds t i l d t sf o re 任b c t i v e 佗s e a r c hw o r k ，t l l 璐c o l l e g e sa n dl l n i v e 巧i 6 e sc a nm a k eag o o dd i r c c t i o nh e a i t l l i l ya n d 鼬e a d i l y 1 1 l i sp a p c ri n 臼o d u c c st 1 1 cd a l am i n i i l gi 咖t b c 眦n a g e m e n to f i e n 6 丘c s e a r c l l i n g b 笛e d 叻a1 1 1 1 i v e r s i t ) ，ss c i e n t i f i c 化a r c hm 觚a 静n e n ts y s t e m ，t h i sp a p c r u 辩s 丛s o c i a t i o nm i n i i l gt e c h n i c a lt o 血1 dt h ek e ye l e m 锄i t si ns c i e n t i f i cr ；e s e a r c l l i i 唱，觚d t h e 邪s o c i a t i o na b o l i tr e 辩a r c he l 咖e l l t s 锄dr e s e a r c hf h l i t t h ei n i l l i n go f 伯忙 i 叫0 m a t i w i l lp r o m o t ct t l e 越t i l a l 幽go f s c i e n t i 丘cm s e a r c h i n gp o h c i e s t l l i sp a p 盯驯衄皿a r i 搬t b eb k g r o l l i l d 蚰da d v 锄瞳a g eo f 加m i i l i i l g ，髂w e n 鹤 t h cs i g i l i f i c a n c eo fd a 重am i n i n gi nt h c i e 嘶丘c 佗s e a r c h 蚴a g 锄e mo fc o l l e g e sa 耐 l l i l i v e 陪m 鹤伍吼l y ，锄d ( h e nd i u s s 韶t h et h e o r yo fd 砒am i n i n g ，s o c i 缸i o nn l l e sa n d t h ei d e 越o fm a i l la l g o r i t h m a n a l y z 鼯t h ec l 勰s i ca p r i 耐a l g o r i t h ma n di t s 谢s 哑 p m b l e m s 勰w e u 觚t l l eb i cs o l l i t i o n s 触e rt h a t ，t h i sp a p 啊p r o p o s 船 英文摘要 m u l 矗d i i n e i l s i o 捌a p 一谢a 1 9 0 删髓删c hi sd 吲印c ds l ，e c 础y 断缸n l i n i n go f t l l i s p a p e r ；1 1 1 饥d e s c r i b e sl h es t r u c t i 聆o f i 训f i c 崩嘲r c hd a t ai n i n i n gs y s c e m ，d e f i n 锚 s u b j c c t - o r i c n t c dm 弛gt 勰l 【s ，i i l c l u d i n g ：m i n m gt h ed a 土aa b o u tr e a r c hp r o j c c t s ， m i i l m gt h ed a l 丑a b o l i tp a p e 巧，m m i n gt h ed a 扭a b o l i ta c a d e m i cw r i 吐i l g s t h ea s s o c i a t i m i i l j i l gp i d c e s si si n l p l 锄e n t c db yp r o 舯l l l i l l g ，an 岫b e ro fs t i m l i l a t i n g 鹤s o c i a t i o n m l 鹤a 把f o 咖吐曲【e r p t e da n da i l a l y z e 也f i l l a l l yt h i sp a p 盯a l p f e s e l l t s m e f o l l o w u d 佗s e a r c hw o r l 【i n 矗l n 睇 k e yw o r d s ：a s s o c j 曩h o r u i e s c i e n 俩ci t 姻k hm a 的g 咖e 斫o fu n i v e 件i t y ； m u m - d i m e 砸j o 的ia p r i o r ia 1 9 0 一t h m ；a 姻o c i a t i o m i i gs y s t e m 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果， 撰写成硕士学位论文：羞隧控堡垄型研笪堡丕蕴生的廑旦巫宜：。除论文中已 经注明引用的内容外，对论文的研究做出重要贡献的个人和集体，均已在文中以 明确方式标明。本论文中不包含任何未加明确注明的其他个人或集体已经公开发 表或未公开发表的成果。 本声明的法律责任由本人承担。 论文作者签名：古咔2 。1 年1 1 月) 护 学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连海事大学研究生学位论文提交、 版权使用管理办法”，同意大连海事大学保留并向国家有关部门或机构送交学位 论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将 本学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或 扫描等复制手段保存和汇编学位论文。 保密口，在 年解密后适用本授权书。 本学位论文属于：保密口 不保密9 磊在以上方框内打“一) 论文储躲s 叶翩躲瓤予 日期：1 。1 年1 1 月2 沪 关联挖掘在科研管理系统中的应用研究 第1 章绪论 1 1 数据挖掘技术研究背景与研究意义 近年来，人们利用信息技术生产和搜集数据的能力大幅度提高，无数个数据 库被用于商业管理、政府办公、科学研究和工程开发等，这一势头仍将持续发展 下去【。于是，一个新的挑战被提了出来：在这信息爆炸的时代，信息过量几乎成 为人人需要面对的问题，大量信息在给人们带来方便的同时也带来了许多问题1 2 j ： 第一是信息过量，难以消化；第二是信息真假难以辨识；第三是信息安全难以保 证；第四是信息形式不一致，难以统一处理。人们开始提出一个新的口号：“要 学会抛弃信息”【3 】。如何才能不被信息的汪洋大海所淹没，从中及时发现有用的知 识，提高信息利用率昵? 数据挖掘和知识发现( d m k d ) 技术应运而生，并得以蓬勃 发展，越来越显示出其强大的生命力f “。 数据挖掘( d m ) 就是从大量的，不完全的、有噪声的、模糊的、随机的实际应 用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知 识的过程【5 】。数据挖掘技术的应用领域十分广阔，它可以从关系数据库、数据仓库、 文本和多媒体数据库、事务数据库和互联网等各种数据源上设法获取诸如分类模 型、聚类模型、回归模型、关联模型和时间序列模型等多种知识模型1 6 】。可以说， 有数据积累的地方，就有数据挖掘技术的用武之地。目前，数据挖掘技术在货篮 数据分析、金融风险预测、产品质量分析、电信、分子生物学、基因工程研究、i c c r n c t 站点访问模式发现以及信息搜索等领域得到了广泛的应用同。数据挖掘技术被认为 是数据库和人工智能领域中研究、开发和应用最活跃的分支之一，汇聚了不同领 域的研究者，尤其是数据库技术、人工智能技术、数理统计、可视化技术、并行 计算等方面的学者和工程技术人员，投身到数据挖掘这一新兴的研究领域，形成 了新的技术热点唧。 第l 章绪论 1 2 数据挖掘技术在高校科研管理中应用的研究现状及意义 目前，从总体上来看，国外在数据挖掘领域中研究的内容十分广泛。从挖掘 的知识种类看，已经取得明显的成果，研究重点从发现方法逐步转向系统应用， 并且已经开发出了多种关于数据挖掘的软件1 9 】。数据挖掘研究具有广泛的应用前 景，并且在医药、金融、商业和工业制造等行业中已经积累了很多的成功经验i lo j 。 目前，基于数据挖掘技术在教育层面上的应用也已经开始，例如，浙江大学 使用关联规则发现技术对高校的人事信息库进行挖掘，试图找到影响学科发展的 因素】，另外，曲阜师范大学体育系与上海体委就体育人才的选拔也探讨了数据 挖掘的可行性1 1 2 1 。近年来，全国的高校都在不断的发展扩大，教学、科研条件都 得到了极大的改善，在校学生的创新精神和实践能力有了更高的发展，高校的学科水 平、社会服务水平和科研水平亦有长足进步【j 扪。很多高校都已经实现了办公的自动 化、网络化，很多部门也都有了自己的办公系统1 1 4 1 ，这些年也逐年积累了很多的 教学、科研、人事等信息，只是这些以台帐管理为主的o l t p 系统缺乏综合分析， 辅助决策的能力，不能为学校的高层领导在做出教学、科研的决策时提供全方位 的科学依据，所以把数据挖掘技术引入高校的教学、科研管理中变得十分紧急重 要，这关系到学校高层能否制定出长远的、稳健的、卓有成效的发展战略，关系 到学科水平、社会服务水平和科研水平等无形资产的改进与提高，关系到学生能否真 正学到知识、思考能力、意志力量，从而为步入社会实现梦想与人生价值打下坚实的 基础。本文是对数据挖掘在高校科研管理工作中应用的一个有益尝试，以大连某高 校的科研管理系统为背景，运用关联挖掘的技术对其积累的科研信息进行挖掘， 来试图发现影响科研成果的关键要素，以及各科研要素问和科研成果问的关联关 系，从而为领导组织、协调师生科研工作、做出科研决策提供科学依据，以便于 教师在教学和科研方面能够平衡发展。长远来看，此举有着非常重要的意义，因 为实践证明，开展科研活动能够更新和提高教师的业务知识水平，并能及时地应 用于课堂教学及实验教学中，从而促进教学质量的提高，对学生、教师个人及对 学校整体的发展都将起着积极的推动作用【1 5 1 。 关联挖掘在科研管理系统中的应用研究 1 3 本文的研究内容及论文的结构 高等学校多年来的教学和科研工作积累了大量的数据，目前这些数据还未能 得到有效利用，只是一个待开发的。宝藏”。鉴于社会对高等学校发展的需求和 目前高校数据管理现状，利用这些数据理性的分析学校各方面工作的成效以及师 生科研工作的合理性与有效程度变得十分重要。本文主要研究如何利用丰富的科 研信息，采用关联规则的数据挖掘技术，获得辅助开展科研工作的知识，指导科 研的进行，从而提高科研水平、改善科研能力。本文的研究内容主要包括两个方 面：一是在收集、阅读大量的数据挖掘特别是关联挖掘的有关理论、算法后设计 出符合本次挖掘任务要求的挖掘算法、系统结构、挖掘流程等等；二是分主题的 对科研数据进行关联挖掘，得到有用的规则，通过分析解释给出开展科研工作的 合理性建议。 论文的主要结构如下： 第1 章介绍了数据挖掘技术的研究背景与研究意义，以及数据挖掘技术在高 校科研管理中的应用情况以及应用的意义。 第2 章首先介绍了数据挖掘的基本过程、分类及任务，以及几种目前较为成 熟的数据挖掘技术方法与技术；然后介绍了关联规则的相关基本理论，描述了关 联规则的经典算法a p r i o f i ；探讨了频繁项集算法a 面谢算法的弊端。 第3 章设计了科研数据关联挖掘系统，分析系统流程，设计挖掘系统结构以 及适用本文挖掘要求的多维a 砸o r i 算法，明确了本文挖掘过程中不同阶段的要求。 第4 章论述科研项目、论文信息、学术专著等挖掘主题的详细关联挖掘过程， 包括数据预处理、发现最大频繁项集、产生关联规则、以及挖掘结果的解释与分 析等阶段，得到对本校教师科研情况的深入了解，获得合理安排师资的启示，充 分调动教师科研的积极性，辅助管理决策的目的。 第5 章对全文进行总结。提出后续研究工作的展望。 第2 章数据挖掘及关联规则 第2 章数据挖掘及关联规则 本章首先介绍数据挖掘的相关知识，包括数据挖掘的过程、数据挖掘的分类、 数据挖掘的常用技术和方法等，然后介绍关联规则的相关基本理论，描述了最常 用算法a 叫o d 算法的基本模型并探讨了其不足之处。 2 1 数据挖掘理论 2 1 1 数据挖掘的概念 数据挖掘( d 1 扎i t am “n g ) 就是从大量的、不完全的、有噪声的、模糊的、 随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在的有用信息 和知识的过程f 。与这一概念相近的术语有【1 7 】：从数据库中发现知识( 1 ( d d ) 、数 据分析、知识抽取、模式分析、数据考古、数据采集、信息收割、商业智能、数 据融合以及决策支持等。国内的学者也把d 啦m i l l i n g 翻译为数据采掘或数据开采。 人们把原始数据看作是形成知识的源泉，就像从矿石中采矿一样。原始数据 可以是结构化的，如关系数据库中的数据，也可以是半结构化的，如文本、图形、 图像数据，甚至是分布在网络上的异构型数据。发现知识的方法可以是数学的， 也可以是非数学的，可以是演绎的，也可以是归纳的。发现的知识可以被用于信 息管理、查询优化、决策支持、过程控制等，还可以用于数据自身的维护。因此， 数据挖掘是一门广义的交叉学科。 2 1 2 数据挖掘过程 数据挖掘一般有以下几个主要步剩1 幻： ( 1 ) 问题定义( t a s kd e 觚t i o n ) 数据挖掘是为了在大量数据中发现有用的令人感兴趣的信息，因此发现何种 知识就成为整个过程中第一个也是最重要的一个阶段。在问题定义过程中，数据 挖掘人员必须和领域专家以及最终用户紧密协作，一方面明确实际工作对数据挖 掘的要求，另一方面通过对各种学习算法的对比而确定可用的学习算法。后续的 学习算法选择和数据集准备都是在此基础上进行的。 4 关联挖掘在科研管理系统中的应用研究 ( 2 ) 数据收集和预处理( d a t a 舯删o n 龃dp r e l 珊c e 鲻i i l g ) 数据准备又可分为三个子步骤：数据选取( d a t as e l e c t i o n ) 、数据预处理( d a 扭 p r 印r o c e s s i t l g ) 和数据变换( d a t a 缸a i 岱f o m m t i o n ) 。数据选取的目的是确定发现任务的 操作对象，即目标数据( t a 唱e t d a t a ) ，是根据用户的需要从原始数据库中抽取的一组 数据。数据预处理一般包括消除噪声、推导计算缺值数据、消除重复记录、完成 数据类型转换等。当数据挖掘的对象是数据仓库时，一般来说，数据预处理己经 在生成数据仓库时完成。数据变换的主要目的是消减数据维数或降维( d i m c 璐i r c d u c t i o n ) ，即从初始特征中找出真正有用的特征，以减少数据挖掘时要考虑的特 征或变量个数。 ( 3 ) 数据挖掘( d a l im i i l i n g ) 算法执行 数据挖掘算法执行阶段首先根据对问题的定义明确挖掘的任务或目的，如分 类、聚类、关联规则发现或序列模式发现等。确定了挖掘任务后，就要决定使用 什么样的算法。选择实现算法有两个考虑因素：一是不同的数据有不同的特点， 因此需要用与之相关的算法来挖掘；二是用户或实际运行系统的要求，有的用户 希望获取描述型的( d c s c r i p t i v e ) 容易理解的知识，而有的用户只是获取预测准确度 尽可能高的预测型( p f e d i c t i v e ) 的知识。 ( 4 ) 结果解释和评估( i n t e i p r e t 矧o na n d “a l u 鲥) 数据挖掘阶段发现出来的模式，经过评估可能存在冗余或无关的模式，这时 需要将其剔除。也有可能模式不满足用户要求，这时则需要整个发现过程回退到 前一阶段。重新选取数据、采用新的数据变换方法、设定新的参数值，甚至换一 种算法。另外，数据挖掘是面向最终用户的，因此需要对发现的模式进行可视化， 或者需要将结果转换为用户易懂的表示。数据挖掘算法执行，仅仅是整个过程的 一个步骤。数据挖掘质量的好坏有两个影响要素：一是所采用的数据挖掘技术的 有效性；二是用于挖掘的数据的质量和数量。整个挖掘过程是一个不断反馈的过 程。 第2 章数据挖掘及关联规则 2 1 3 数据挖掘的分类 数据挖掘可按数据库类型、挖掘对象、挖掘任务、挖掘方法与技术等几个方 面进行分类嘲。 ( 1 ) 按数据库类型分类 数据挖掘主要是在关系数据库中挖掘知识。随着数据库类型的不断增加，逐 步出现了不同数据库的数据挖掘。现在，除关系数据库挖掘外，还有模糊数据挖 掘、历史数据挖掘、空间数据挖掘等多种不同数据库的数据挖掘类型。 ( 2 ) 按数据挖掘对象分类 数据挖掘除了对数据库这个主要对象进行挖掘外，还有文本数据挖掘、多媒 体数据挖掘、w e b 数据挖掘等。由于对象不同，挖掘方法的差异很大。 ( 3 ) 按数据挖掘任务分类 数据挖掘的任务有：关联分析、时序模式、聚类、分类、偏差监测、预测等。 按任务分类可将数据挖掘分为：关联规则挖掘、序列模式挖掘、聚类数据挖掘、 分类数据挖掘、偏差分析挖掘和预测挖掘等类型【冽。 关联分析( a s s o c i 撕o na i i a l y s i s ) 两个或两个以上数据项的取值之间存在某种规律性，就称为关联，可以建立 起这些数据项的关联规则口”。数据关联是数据库中存在的一类重要的、可被发现 的知识，它反映一个事件和其他事件之间依赖或关联。如果两项或多项属性之间 存在关联，那么其中一项的属性值就可以依据其他属性值进行预测。例如，买面 包的顾客中9 0 还买牛奶，这就是一条关联规则。在商场中将这两样物品摆放在 一起销售，将会提高销售量。在大型数据库中，这样的关联规则可以产生很多， 这就需要进行筛选。一般用“支持度”和“可信度”两个阈值来淘汰那些无用的 关联规则。 聚类分析( c l 惦c c r i l l g ) 聚类是把数据按照它们的相似性归纳成若干类别同一类别中的数据距离较 小、彼此相似，不同类别中的数据距离偏大、彼此相异圆。聚类分析可以建立宏 关联挖掘在科研管理系统中的应用研究 观的概念，发现数据的分布模式，以及可能的数据属性之间的相互关系。 分类( c l 舾s i f i c a d o n ) 分类就是找出一个类别的概念描述，并用这种描述来构造模型( 一般用规则或 决策树模式表示) 。类别的概念描述代表着这类数据的整体信息，也就是该类的内 涵描述。 ( 4 ) 按数据挖掘的方法和技术分类 数据挖掘的技术和方法较多。包括归纳学习类、聚类方法类、统计分析类、 仿生物技术类、模糊数学类、可视化技术类等【2 3 1 。 本文中数据挖掘的主要任务是对科研信息进行挖掘，试图找出科研要素之间、 科研成果之间以及科研要素与科研成果之间的关联关系，因此由上述的按数据挖 掘的任务分类可以看出关联规则的数据挖掘方法是最适合本文要求的数据挖掘方 法，所以本文采用了关联规则的数据挖掘方法来对科研信息进行挖掘。 2 2 关联规则理论 关联规则是数据挖掘技术所能发现的非常重要的一类规则，它首先由舢删， i m i e l i s k i 和s 坝呲i u 于1 9 9 3 年提出洲，用于发现交易数据库中不同商品( 项) 之间的 联系，这些规则找出顾客购买行为模式，如购买了某一商品对购买其他商品的影 响。发现这样的规则可以应用于商品货架设计、货存安排以及根据购买模式对用 户进行分类。以后诸多的研究人员对关联规则的挖掘问题进行了大量的研究。他 们的工作包括对原有的算法进行优化，如引入随机采样、并行的思想等，以提高 算法挖掘规则的效率瞄】。最近也出现了独立于a l 驴w a l 的频集方法的研究嗍，为 弥补频集方法的一些缺陷而探索挖掘关联规则的新方法；也有一些研究注重于 对挖掘到的模式的价值进行评估，他们提出的模型建议了一些值得考虑的研究方 向。 2 2 1 关联规则的基本概念 关联规则是表示数据库中一组对象之间某种关联关系的规则【2 刀。 第2 章致据挖掘及关联规则 设i = ( i l ，i 2 ， 是项目的集合，其中的元素称为项目( i t c m ) 。记d 为交易 ( 昀n s a c 廿o n ) t 的集合，这里交易t 是i 上的子集，并且t c i 。对应每一个交易有 难一的标识记作1 1 d 。设x 是一个i 中项的集合。如果x t ，那么称交易t 包 含x 。 一个关联规则是形如x 号y 的蕴涵式，其中x c i ，y c i ，x n y = 0 。x 称为规 则的条件，y 为规则的结果，规则x j y 在交易数据库d 中的支持度( s u p p o r t ) 是交 易集中包含x 和y 的交易数与所有交易数之比，记为s u p p o 删寺y ) ，即 s u p p o r “ x j y ) = i t ：x u y ct ，t d ) i i d i 规则x 号y 在交易集中的可信度( c 0 而d 印c c ) 是指包含x 和y 的交易数与包含 x 的交易数之比，记为c 0 曲d 如c e ( ) ( j y ) ，即 、 c o i l f i d e n c e ( x = 争y 产i t ：x u y e t ，t d ) j i 仃：x t ，t d 训 给定一个交易集d ，挖掘关联规则问题就是产生支持度和可信度分别大于用 户给定的最小支持度( m 妞s u p p ) 和最小可信度( m j nc o n d 的关联规则。我们称这类 规则为强规则，否则称为弱规则。 2 2 2 挖掘关联规则的基本步骤 挖掘关联规则的步骤大体可以由一个两步的过程来描述闭： ( 1 ) 找出所有的频繁项集。即找出所有那些支持度大于事先给定的支持度阈值 的项集。 ( 2 ) 在找出的频繁项集的基础上产生强关联规则。即产生那些支持度和可信度 分别大于或等于事先给定的支持度阈值和可信度阈值的关联规则。 在上述两个步骤中，第二个步骤相对要容易一些，因为它只需要在已经找出 的频繁项集的基础上列出所有可能的关联规则，然后用可信度阈值来衡量这些关 联规则。而第一个步骤是挖掘关联规则的关键步骤，需要大量的i ，o 操作，挖掘关 联规则的总体性能由第一个步骤决定，因此目前所有关联规则挖掘算法都是着重 于研究第一个步骤，即频繁项集挖掘算法。 此外，还可利用有趣度性度量标准来帮助挖掘有价值的关联规则知识。 善 关联挖掘在科研管理系统中的应用研究 关联规则挖掘的基本模型捌如图2 1 所示： 图2 1 关联规则挖掘的基本模型图 f 培2 11 k b a s i cm o d e lo f a s s j a t i 彻r i i l 韩m 雠n g 图2 1 中d 为数据集，算法l 为频繁项集的搜索算法，算法2 为关联规则的 产生算法，r 为挖出的关联规则集合。用户通过指定最小支持度和最小可信度分别 与算法1 和算法2 交互，并通过与r 的交互对挖掘结果进行解释与评估。 2 2 3 关联规则的种类 我们将关联规则按不同的情况进行分类3 0 】： ( 1 ) 布尔型规则和数值型规则 基于规则中处理的变量的类别，关联规则可以分为布尔型和数值型。布尔型 关联规则( b o o l e 趾a s s o c i a t i r u l e ) 处理的值都是离散的、种类化的，它显示了这 些变量之间的关系；而数值型关联规则( 删t 砒i v e 舡s o c i a l i 刚e ) 可以和多维关 联或多层关联规则结合起来，对数值型字段进行处理，将其进行动态的分割，或 者直接对原始的数据进行处理，当然数值型关联规则中也可以包含种类变量。 例如：性别= “女”号职业= “秘书”，是布尔型关联规则；性别= 。女”j a v g ( 收 入p 2 3 0 0 ，涉及的收入是数值类型，所以是一个数值型关联规则。 ( 2 ) 单层规则和多层规则 基于规则中的数据的抽象层次，可以分为单层关联规则和多层关联规则。在 单层的关联规则( s 埘“e v e la s s o c i 鲥r “e ) 中，所有的变量都没有考虑到现实 的数据是具有多个不同的层次的；而在多层的关联规则( m l l l n l e v e l 触i a l i r 山e ) 中，对数据的多层性已经进行了充分的考虑。 第2 章数据挖掘及关联规则 例如：b u y ( x ，c o m p 眦r ) 号b u “x ，p r i m 哪，是一个单层关联规则；a g x ，”3 0 ，3 9 ”) j b u y ( x ，c o n l p u ，是一个多层关联规则。 ( 3 ) 单维规则和多维规则 基于规则中涉及到的数据的维数，关联规则可以分为单维的和多维的。在单 维的关联规则( s i i i g l e d i m e 船i o n a la s s o c i a l i o nr u l e ) 中，我们只涉及到数据的一个 维，如用户所购买的物品：而在多维的关联规则( m u m - d i i i i e n s i o n a la s s o c i a t i r i l l e ) 中，要处理的数据将会涉及多个维。换成另一句话，单维关联规则是处理单个属 性中的一些关系；多维关联规则是处理各个属性之间的某些关系。 例如：啤酒昔尿布，这条规则只涉及到用户的购买的物品；性别= “女”穹职 业= 。秘书”，这条规则就涉及到两个字段的信息，是两个维上的一条关联规则。 2 2 4 关联规则价值衡量的方法 当我们用数据挖掘的算法得出了一些结果之后，数据挖掘系统如何知道哪些 规则对于用户来说是有用的、有价值的? 因为并不是所有的规则对用户都有用。 衡量关联规则挖掘结果的有效性应该从多种综合角度来考虑。 准确性：挖掘出的规则必须反映数据的实际情况。尽管规则不可能是1 0 0 适 用的，但是必须要在一定的可信度内。 实用性：挖掘出的规则必须是简洁可用的，而且是针对挖掘目标的，不能说 有2 0 0 条规则，其中l o o 条与目标无关，5 0 条用户无法理解。 新颖性：挖掘出的关联规则可以为用户提供新的有价值信息。如果它们是用 户事先就知道的，那么这样的规则即使再正确也是毫无价值的。 改善关联规则挖掘质量是一件很困难的工作。必须采用事先预防、过程控制 及事后评估等多种方法，其中使用合适的机制( 如约束) ，让用户主动参与挖掘工作 是解决问题的关键【3 1 1 。粗略地说，可以在系统客观和用户主观两个层面上考虑关 联规则挖掘的质量问题1 3 2 】。 ( 1 ) 系统客观层面 很多的算法都使用“支持度一可信度”的框架。这样的结构有时会产生一些 关联挖掘在科研管理系统中的应用研究 错误的结果。看如下的一个例子： 假设我们对分析涉及购买计算机游戏和录象的商业事务感兴趣。设事件g a m e 表示包含计算机游戏的事务，而“d e o 表示包含录象的事务。在所分析的l o o o o 个 事务中，数据显示6 0 0 0 个顾客事务包含计算机游戏，7 5 0 0 个事务包含录象，而 4 0 0 0 个事务同时包含计算机游戏和录象。假定发现关联规则的数据挖掘程序在该 数据上运行，使用最小支持度3 0 ，最小可信度6 0 。将发现下面的关联规则： b u y s ( ) ( ，伽m p u t e rg a m 嚣) 辛b u y s ( ) 【， v i d o 两l p p o 州0 ，c o 嘶d 蛐c e 6 吲 该规则是强关联规则，因而向用户报告，因为其支持度为( 4 0 0 0 l o o o o 户4 0 ， 可信度为( 4 0 0 0 ，6 0 0 0 户6 6 ，分别满足最小支持度和最小可信度的阈值。然而，该 规则是误导，因为购买录象的可能性是7 5 ，比6 6 还大。事实上，计算机游戏 和录象是负相关的，买其中的一种实际上减少了买另一种的可能性。如果我们把 支持度和可信度设得足够低，那么我们将得到两条矛盾的规则，另一方面，如果 我们把那些参数设得足够高，我们只能得到不精确的规则。总之，没有一对支持 度和可信度的组合可以产生完全正确的关联。 于是人们引入了兴趣度，用来修剪无趣的规则，即避免生成。错觉”的关联 规则。一般一条规则的兴趣度是在基于统计独立性假设下真正的强度与期望的强 度之比，然而在许多应用中已发现，只要人们仍把支持度作为最初的项集产生的 主要决定因素，那么要么把支持度设得足够低以使得不丢失任何有意义的规则， 要么冒丢失一些重要规则的风险；对前一种情形计算效率是个问题而后一种情 形则有可能丢失从用户观点来看是有意义的规则的问题。 ( 2 ) 用户主观层面 上面的讨论只是基于系统方面的考虑，但是一个规则的有用与否最终取决于 用户的感觉，只有用户可以决定规则的有效性、可行性。所以我们应该将用户的 需求和系统更加紧密的结合起来。 可以采用一种基于约束( c o n s t r a i n t - b 舔c d ) 的挖掘【3 3 1 。具体约束的内容有： 第2 章数据挖掘及关联规则 数据约束：用户可以指定对哪些数据进行挖掘，而不一定是全部的数据。对 数据的约束可以起到减少数据挖掘算法所用的数据量、提高数据质量等作用。通 过指定约束把粗糙的、混杂的庞大源数据集逐步压缩到与任务相关的数据集上。 在不同的阶段，可以通过数据挖掘语言实施数据约束。例如，目前研究的数据挖 掘操纵语言大都支持数据约束的设定。 指定挖掘的维和层次：用户可以指定对数据哪些维以及这些维上的哪些层次 进行挖掘。对于一个基于数据仓库或多维数据库的数据挖掘工作来说，不同的维 为用户提供了不同粒度的数据和对数据的不同视点。但是，它也给数据挖掘工作 带来新的问题。例如，从不同粒度挖掘出来的知识可能存在冗余问题；由于维数 不加限制可能引起挖掘效率低下等问题。因此，可以限制聚焦的维数和粒度层次， 也可以针对不同的维设置约束条件。利用约束灵活地进行多维挖掘是目前比较集 中讨论的问题【蚓。 规则约束：可以指定哪些类型的规则是我们所需要的。引入一个模板 m p l a t e ) 的概念，用户使用它来确定哪些规则是令人感兴趣的而哪些是不感兴趣的。如果 一个规则匹配一个包含的模板( i i l c l u s i v et e m p l a t e ) ，则该规则是令人感兴趣的，相 反，如果一个规则匹配一个限制的模板( 】陀鲥c t i v e t 哪p l a i c ) 则被视为是缺乏兴趣的。 其中有些条件可以和算法紧密地结合，从而既提高了效率，又使挖掘的目的 更加明确化。 2 3 关联规则相关算法及分析 2 3 1 p r i o r i 算法 基本模型【3 5 j ： 设i - i l ，i 2 ，i l - i ) 为所有项目的集合，d 为事务数据库，事务t 是一个项目子 集( t i ) 。每一个事务具有唯一的事务标识t i d 。设a 是一个由项目构成的集合， 称为项集。事务t 包含项集a ，当且仅当a e t 。如果项集a 中包含k 个项目，则 称其为k 项集。项集a 在事务数据库d 中出现的次数占d 中总事务的百分比叫做 项集的支持度。如果项集的支持度超过用户给定的最小支持度阈值，就称该项集 关联挖掘在科研管理系统中的应用研究 是频繁项集( 或大项集) 。 关联规则是形如x j y 的逻辑蕴涵式，其中x c i ，y c i ，且x n y 三0 。如果事 务数据库d 中有s 的事务包含x u y ，则称关联规则x 哥y 的支持度为s ，实际 上，支持度是一个概率值。若项集x 的支持度记为吼l p p o r “p ( ) ，规则的可信度为 s u p p o r t ( ) 【j y ) 蛐p p o r t ( 均。这是一个条件概率p ( y l x ) 。也就是： s u p p o r t o ( 号驴p 岱uy ) c o n 饲锄c e ( ) ( j y ) p ( y i 为 关联规则就是支持度和可信度分别满足用户给定阈值的规则。发现关联规则 需要经历如下两个步骤： 找出所有频繁项集： 由频繁项集生成满足最小可信度阈值的规则。 a 面嘶算法在发现关联规则领域具有很大影响力。算法命名源于算法使用了 频繁项集性质的先验( p r i 何) 知识。在具体实现时，a 硼耐算法将发现关联规则 的过程分为两个步骤：第一步通过迭代，检索出事务数据库中的所有频繁项集， 即支持度不低于用户设定的阈值的项集；第二步利用频繁项集构造出满足用户最 小可信度的规则。其中，挖掘或识别出所有频繁项集是该算法的核心，占整个计 算量的大部分。 由m 个项目形成的不同项集的数目可以达到2 m - 1 个，尤其在海量数据库d 中， 这是一个n p 难度的问题。为了避免计算所有项集的支持度( 实际上频繁项集只占 很少一部分) ，a l m o f i 算法引入候选项集的概念。若候选k 项集的集合记为q ， 频繁k 项集的集合记为l k ，m 个项目构成的k 项集的集合记为c ：t 则三者之间满 足关系l k c c k c ：。构成候选项集所遵循的原则是。频繁项集的子集必为频繁项 集”。 性质l ：频繁项集的子集必为频繁项集。 性质2 ：非频繁项集的超集一定是非频繁的。 第2 章数据挖掘及关联规则 a 删嘶算法运用性质1 ，通过已知的频繁项集构成长度更大的项集，并将其 称为候选项集。候选k 项集的集合c k 是指由有可能成为频繁k 项集的项集组成的 集合。以后只需计算候选项集的支持度，而不必计算所有不同项集的支持度，因 此在一定程度上减少了计算量。具体的实现过程为： ( 1 ) 通过单趟扫描数据库d 计算出各个1 项集的支持度，从而得到频繁l 项集 构成的集合。 ( 2 ) 连接步：为了产生频繁k 项集构成的集合k ，预先生成一个候选k 项集的 集合c k 。候选项集的集合由j o 运算得到。若p ，q h - l ，p = ( p i 她，p m 舰1 ， q = q f ，q 2 ，qk 2 qk 1 ) 并且当1 i k - 2 时，p i = q i ，当i = k - 1 时，p b l q k 1 ，则p u q = p l ， p 2 ，雎l ，啦i ) 是候选k 项集的集合c k 中的元素。这里的候选k 项集的集合c k 是 指由有可能成为频繁k 项集的项集组成的集合。 ( 3 ) 剪枝步：由于c k 是h 的超集，可能有些元素不是频繁的。c k 很庞大时会 带来巨大的计算量，为减少c k 的规模，a 州o r i 遵从下列性质：任何非频繁的( k - 1 ) 项集必定不是频繁k 项集的子集。所以，当候选k 项集的某个( k - 1 ) 子集不是l k 1 中的成员时，则该候选项集不可能是频繁的，可以从c k 中移去。这就是a 埘耐 的剪枝思想。 ( 4 ) 通过单趟扫描数据库d ，计算c k 中各个项集的支持度。 ( 5 ) 将c k 中不满足最小支持度的项集剔除，形成由频繁k 项集构成的集合h 。 通过迭代循环，重复上述步骤2 巧，直到不能产生新的频繁项集的集合( 非空 集合) 时为止，a o r i 算法求出所有满足最小支持度的频繁项集。 a p r i o r i 算法如下： ( 1 ) l l = 频繁l 项集) ； ( 2 ) f - o r o c _ 2 ；k 1 a ；k + + ) d ob e g m ( 3 ) c 硎。咄e n ( l k 1 ) ； ，新的候选k 项集 ( 4 ) f 醅a l l 垭l s a c t i o 璐t dd ob e g i n，a 为d 中的一条事务 ( 5 ) c t - 鲫b s e t (