（计算机应用技术专业论文）基于本体的多层关联规则算法与知识管理模型研究.pdf

大连交通大学丁学硕士学位论文 摘要 随着国际互联网i n t e r n e t 的发展和普及，需要面对海量的信息资源，信息内容和层 次上的多元性和复杂性，特别是从海量的信息中筛选出少量自己需要的有用的信息资源 时，人们有时会感到束手无策。因此，对数据挖掘技术的研究及知识管理是全球信息化 发展的客观要求。 本文主要基于本体并利用本体的概念层次结构，提出了基于本体的多层关联规则算 法m la r 。关联规则中的最关键因素是最小支持度，它是用来缩减搜索空间和限制生 成规则的数目，如果仅用单个最小支持度，就会隐含地假设数据库中的子项有相同的性 质或相似的出现频率，为了解决上述问题，提出了一个根据概念层次的上层支持度计算 下层支持度的公式。通过该公式所得的支持度是递减的，并且当父层是非频繁项的项， 子层有可能是频繁的项，此时还可以把符合这样条件的项回收。如果计算的支持度大于 父项支持度，说明上层支持度选取过小，不符合实际数据，则应重新对初始支持度进行 调整，从这方面讲，该算法对初始支持度的选择有了一定的评价。另外，针对以上挖掘 出来的数据，知识管理系统在检索时存在大量不相关的知识等问题，本文还提出了一个 新的知识管理模型框架。本框架利用本体的概念规范、语义丰富、层次关系等特点，并 结合本体的知识库和一阶谓语推理引擎对用户的查询请求进行处理，使用户最终检索到 与请求内容匹配较高的信息。实验结果表明算法在时间复杂度和空间复杂度是高效的， 而且具有较好的性能。 关键词：数据挖掘；关联规则；频繁项集；本体；管理模型 l l 摘要 a b s t r a c t w i t ht h ed e v e l o p m e n ta n dp o p u l a r i z a t i o no fi n t e r n e t ，p e o p l en e e dt of a c eaf l o o do f i n f o r m a t i o nr e s o u r c e s ，i n f o r m a t i o nc o n t e n ta n dt h el e v e lo fd i v e r s i t ya n dc o m p l e x i t y , e s p e c i a l l yw h e np e o p l ew a n tt og a i nas m a l la m o u n to fn e e d e da n du s e f u li n f o r m a t i o nf r o m m u c hi n f o r m a t i o n ，t h e ys o m e t i m e sf e e lh e l p l e s sw h e nf a c es u c hq u e s t i o n s od a t am i n i n g t e c h n o l o g y r e s e a r c ha n dk n o w l e d g em a n a g e m e n ti st h eo b j e c t i v e r e q u i r e m e n t so ft h e d e v e l o p m e n to fg l o b a li n f o r m a t i o n i nt h i sp a p e r , m a i n l yb a s i n go no n t o l o g ya n dm a k i n gu s eo fo n t o l o g y sh i e r a r c h y ，a n d a na l g o r i t h mm l _ - a rw h i c ho n t o l o g y b a s e dm u l t i l e v e la s s o c i a t i o nr u l e si sp r o p o s e d t h e s m a l l e s td e g r e eo fs u p p o r tw h i c hi st h em o s tc r i t i c a lf a c t o ri na s s o c i a t er u l e s ，w h i c hi su s e dt o r e d u c et h es e a r c hs p a c ea n dl i m i tt h en u m b e ro fg e n e r a t e dr u l e s ，i fo n l yas i n g l em i n i m u m s u p p o r t ，i tw i l li m p l i c i t l ya s s u m et h a tt h es u b - i t e m si nt h ed a t a b a s eh a v et h es a m eas i m i l a r n a t u r eo rf r e q u e n c yo fo c c u r r e n c e ，i no r d e rt oa d d r e s st h ea b o v ei s s u e s ，a n daf o r m u l ai sg i v e n w h i c ha c c o r d st ot h eu p p e rs u p p o r tt oc a l c u l a t et h el o w e rl e v e ls u p p o r t b e c a u s eo ft h e s u p p o r ti sd e c r e a s i n gw h i c hm a yc a u s et h ep a r e n tl a y e ro fn o n - f r e q u e n ti t e me n t r ya n d s u b - l a y e rm a yb ef r e q u e n t ，s oc a nr e g a i nt h ei t e m st h a nm e e tt h e s ec o n d i t i o n s i ft h es u p p o r t o fc a l c u l a t e di sg r e a t e rt h a nt h eo fs u p p o r tp a r e n t ，a n dt h ei n d i c a t i n gs u p p o r tf o rs e l e c t i n g a b o u tt h et o pi st o os m a l lw h i c hd o e sn o tm e e tt h ea c t u a ld a t a , a n di ts h o u l dr e a d j u s tt h e s u p p o r tf r o mt h ei n i t i a lp o i n to fv i e w t h i sa l g o r i t h mh a sa l s oc e r t a i ne v a l u a t i o no ft h ec h o i c e o ft h ei n i t i a ld e g r e eo fs u p p o r t a n o t h e r ，a sf o r t h ep r o b l e mo f g i a n to f u n r e l a t e di n f o r m a t i o n t h a te m e r g e sw h e ns e a r c h i n gk n o w l e d g eo nt h ek n o w l e d g em a n a g e m e n ts y s t e m ，t h ep a p e r p r o p o s e san e wk n o w l e d g em a n a g e m e n ts y s t e mf r a m e w o r k t h ef r a m e w o r km a k e su s eo ft h e c h a r a c t e r i s t i c so fc o n c e p to fn o r m s ，r i c hs e m a n t i ca n dl e v e lr e l a t i o n so ft h eo n t o l o g ya n d c o m b i n e st h ek n o w l e d g ew a r e h o u s eo fo n t o l o g ya n dt h ef i r s to r d e rp r e d i c a t er e a s o n i n ge n g i n e o nt h eu s e r sq u e r yt o p r o c e s st h er e s u l ta n dm a k eu s e r sg e tu l t i m a t e l yi n f o r m a t i o nt h a t m a t c h e sw i t hs e a r c hr e q u e s t si nah i g h e rs t a t e e x p e r i m e n t a lr e s u l t ss h o wt h a tt h ea l g o r i t h mi s e f f i c i e n to nt h et i m ec o m p l e x i t ya n dt h es p a c e c o m p l e x i t y ，b u ta l s oh a sg o o dp e r f o r m a n c e k e yw o r d s ：d a t am i n i n g ；a s s o c i a t i o nr u l e s ；f r e q u e n ti t e m s e t ；o n t o l o g y ；m a n a g e m o d d i i i 大连交通大学学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。尽我所知，除了文中特别加以标注和致谢及参考 文献的地方外，论文中不包含他人或集体已经发表或撰写过的研究成 果，也不包含为获得太蔓塞通太堂或其他教育机构的学位或证书而 使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在 论文中作了明确的说明并表示谢意。 本人完全意识到本声明的法律效力，申请学位论文与资料若有不 实之处，由本人承担一切相关责任。 学位论文作者签名：当，矛、诗 日期： 矽罗年r ，月，吖日 大连交通大学学位论文版权使用授权书 本学位论文作者完全了解太羹塞通太堂有关保护知识产权及保 留、使用学位论文的规定，即：研究生在校攻读学位期间论文工作的 知识产权单位属太羹銮通太堂，本人保证毕业离校后，发表或使用 论文工作成果时署名单位仍然为太董塞通太堂。学校有权保留并向 国家有关部门或机构送交论文的复印件及其电子文档，允许论文被查 阅和借阅。 。 本人授权太蓬交通太堂可以将学位论文的全部或部分内容编入 中国科学技术信息研究所中国学位论文全文数据库等相关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 、 又： ( 保密的学位论文在解密后应遵守此规定) 学位论文作者签名：是示老导师签名：睇 日期： 训，7 年17 - 月，中日 日期： 夕7 年p 月，丫日 学位论文作者毕业后去向：河南省平顶山市 工作单位：河南省平顶山市中平能化集团电话：1 3 5 9 1 7 6 5 6 8 2 通讯地址：河南省平顶山市中平能化集团计算机与通信分公司软件部 邮编：4 6 7 0 0 0 电子信箱：z h a o j i n g t a o w e l l 1 6 3 t o m 绪论 绪论 1 课题背景及实际意义 我们现在已经生活在一个网络化的时代，通信、计算机和网络技术正改变着整个人 类和社会。在这些技术及随着数据库技术的迅速发展以及数据库管理系统的广泛应用， 人们积累的数据越来越多。激增的数据背后隐藏着许多重要的信息，人们希望能够对其 进行更高层次的分析，以便更好地利用这些数据。目前的数据库系统可以高效地实现数 据的录入、查询、统计等功能，但无法发现数据中存在的关系和规则，无法根据现有的 数据预测未来的发展趋势。缺乏挖掘数据背后隐藏的知识的手段，导致了“数据爆炸但 知识贫乏 的现象。让我们来看一些身边俯拾即是的现象：纽约时报由6 0 年代的 1 0 - 2 0 版扩张至现在的1 0 0 - - 2 0 0 版，最高曾达1 5 7 2 版；北京青年报也已是1 6 - 4 0 版；市场营销报已达1 0 0 版。然而在现实社会中，人均日阅读时间通常为3 0 , - - 4 5 分 钟，只能浏览一份2 4 版的报纸。大量信息在给人们带来方便的同时也带来了一大堆问 题：第一是信息过量，难以消化；第二是信息真假难以辨识；第三是信息安全难以保证； 第四是信息形式不一致，难以统一处理。人们开始提出一个新的口号：“要学会抛弃信 息。人们开始考虑：“如何才能不被信息淹没，而是从中及时发现有用的知识、提高 信息利用率? 面对这一挑战，数据开采和知识发现( d m k d ) 技术应运而生，并显示出 强大的生命力。 数据挖掘技术是人们长期对数据库技术进行研究和开发的结果。起初各种商业数据 是存储在计算机的数据库中的，然后发展到可对数据库进行查询和访问，进而发展到对 数据库的即时遍历。数据挖掘使数据库技术进入了一个更高级的阶段，它不仅能对过去 的数据进行查询和遍历，并且能够找出过去数据之间的潜在联系，从而促进信息的传递。 现在数据挖掘技术在商业应用中已经可以马上投入使用，因为对这种技术进行支持的三 种基础技术已经发展成熟，他们是： 海量数据搜集 强大的多处理器计算机 数据挖掘算法 f r i e d m a n 1 9 9 7 y u 举了四个主要的技术理由激发了数据挖掘的开发、应用和研究的兴趣： 超大规模数据库的出现，例如商业数据仓库和计算机自动收集的数据记录； 先进的计算机技术，例如更快和更大的计算能力和并行体系结构； 大连交通大学工学硕士学位论文 对巨大量数据的快速访问； 对这些数据应用精深的统计方法计算的能力。 数据挖掘的主要任务是发现隐藏在数据中的模式，包括：分类模式、聚类模式、回 归模式、关联模式、序列模式和偏差模式等。数据挖掘的常用方法有：模糊方法、粗糙 集理论、云理论、证据理论、人工神经网络、遗传算法和归纳学习等。 数据挖掘技术的应用就业领域，当前数据挖掘应用主要集中在电信( 客户分析) ，零 售( 销售预测) ，农业( 行业数据预测) ，网络日志( 网页定制) ，银行( 客户欺诈) ，电力( 客 户呼叫) ，生物( 基因) ，天体( 星体分类) ，化工，医药等方面。当前它能解决的问题典 型在于：数据库营销( d a t a b a s em a r k e t i n g ) 、客户群体划分( c u s t o m e rs e g m e n t a t i o n & c l a s s i f i c a t i o n ) 、背景分析( p r o f i l ea n a l y s i s ) 、交叉销售( c r o s s s e l l i n g ) 等市场分析行为，以 及客户流失性分析( c h u ma n a l y s i s ) 、客户信用记分( c r e d i ts c o r i n g ) 、欺诈发现( f r a u d d e t e c t i o n ) 等等，在许多领域得到了成功的应用。如果你访问著名的亚马逊网上书店 ( w w w a m a z o n c o m ) ，会发现当你选中一本书后，会出现相关的推荐数目“c u s t o m e r sw h o b o u g h tt h i sb o o ka l s ob o u g h t ”，这背后就是数据挖掘技术在发挥作用l l j 。 根据i d c ( i n t e m a t i o n a ld a t ac o r p o r a t i o n ) 预测说2 0 0 4 年估计b i 行业市场在1 4 0 亿美 元。现在，随着我国加入w t o ，我国在许多领域，如金融、保险等领域将逐步对外开 放，这就意味着许多企业将面临来自国际大型跨国公司的巨大竞争压力。国外发达国家 各种企业采用商务智能的水平已经远远超过了我国。美国p a l oa l t o 管理集团公司1 9 9 9 年对欧洲、北美和日本3 7 5 家大中型企业的商务智能技术的采用情况进行了调查。结果 显示，在金融领域，商务智能技术的应用水平已经达到或接近7 0 ，在营销领域也达到 5 0 ，并且在未来的3 年中，各个应用领域对该技术的采纳水平都将提高约5 0 。现在， 许多企业都把数据看成宝贵的财富，纷纷利用商务智能发现其中隐藏的信息，借此获得 巨额的回报。国内暂时还没有官方关于数据挖掘行业本身的市场统计分析报告，但是国 内数据挖掘在各个行业都有一定的研究。据国外专家预测，在今后的5 - 1 0 年内，随着 数据量的日益积累以及计算机的广泛应用，数据挖掘将在中国形成一个产业。 当前，d m k d 研究方兴未艾，其研究与开发的总体水平相当于数据库技术在7 0 年 代所处的地位，迫切需要类似于关系模式、d b m s 系统和s q l 查询语言等理论和方法 的指导，才能使d m k d 的应用得以普遍推广。预计在本世纪，d m k d 的研究还会形成 更大的高潮，研究焦点可能会集中到以下几个方面： ( 1 ) 发现语言的形式化描述，即研究专门用于知识发现的数据挖掘语言，也许会像 s q l 语言一样走向形式化和标准化； ( 2 ) 寻求数据挖掘过程中的可视化方法，使知识发现的过程能够被用户理解，也便 2 绪论 于在知识发现的过程中进行人机交互； ( 3 ) 研究在网络环境下的数据挖掘技术( w e bm i n i n g ) ，特别是在因特网上建立 d m k d 服务器，并且与数据库服务器配合，实现w e bm i n i n g ； ( 4 ) 加强对各种非结构化数据的开采( d a t am i n i n gf o ra u d i o & v i d e o ) ，如对文本数 据、图形数据、视频图像数据、声音数据乃至综合多媒体数据的开采；处理的数据将会 涉及到更多的数据类型，这些数据类型或者比较复杂，或者是结构比较独特。为了处理 这些复杂的数据，就需要一些新的和更好的分析和建立模型的方法，同时还会涉及到为 处理这些复杂或独特数据所做的费时和复杂数据准备的一些工具和软件。 ( 5 ) 交互式发现； ( 6 ) 知识的维护更新。 但是，不管怎样，需求牵引与市场推动是永恒的，d m k d 将首先满足信息时代用 户的急需，大量的基于d m k d 的决策支持软件产品将会问世。 只有从数据中有效地提取信息，从信息中及时地发现知识，才能为人类的思维决策 和战略发展服务。也只有到那时，数据才能够真正成为与物质、能源相媲美的资源，信 息时代才会真正到来。 就目前来看，将来的几个热点包括网站的数据挖掘( w e bs i t ed a t am i n i n g ) 、生物信息 或基 ( b i o i n f o r m a t i c s g e n o m i c s ) 的数据挖掘及其文本的数据挖掘( t e x t u a lm i n i n g ) r 】。下 面就这几个方面加以简单介绍。 然而，目前的数据挖掘技术的研究还很不成熟，其应用还有较大的局限性，正是这 些局限性，促进数据挖掘研究进一步向前发展。下面列出了数据挖掘研究和应用所面临 的主要挑战：( 1 ) 数据挖掘的性能问题。( 2 ) 多种形式的输入数据。( 3 ) 用户参与和领 域知识。 ( 4 ) 知识的维护和更新。( 5 ) 知识的表达和解释机制。( 6 ) 隐私保护问题。 另外，数据挖掘系统和其他决策支持系统的有机集成也是一个挑战，特别是与一些用户 已经熟悉的系统相结合，这对于挖掘系统充分发挥作用是非常重要的。 2 本体分析 本体的概念起源于哲学领域。1 7 世纪，德意志哲学家郭克兰纽( r 1 g o c l e n i u s ) 首次提 出“o n t o l o g y 一词。哲学领域的“o n t o l o g y 在苏格拉底提出“始基 问题中萌芽， 由柏拉图和亚里士多德奠定了它的雏形，中世纪经院哲学使之最终成熟起来。古希腊哲 学家亚里士多德将本体定义为研究“存在 的科学，又把它分为两个方面：一方面研究 存在的本质，另一方面研究客体对象的理论定义，即整个现实世界( 本体) 的基本特征。 人工智能【3 l ( a r t i f i c i a li n t e l l i g e n c e ) 领域将本体概念引入，用于知识表示和知识组织，其概 3 大连交通大学工学硕士学位论文 念的内涵也发生了改变。 斯坦福大学的g r u b e r ( 1 9 9 3 ) 最早提出本体的定义，其后b o r s tp i m 博士等( 1 9 9 7 ) 在 g r u b e r 定义的基础上做了一些修正。两个定义合并以后，表达如下： “i ti sa ne x p l i c i t f o r m a ls p e c i f i c a t i o no fas h a r e dc o n c e p t u a l i z a t i o n l ”译为中文，即本体是一套得到大多数 人认同的、关于概念体系的明确的、形式化的规范说吲4 】。 德国卡尔斯鲁厄大学的s t u d e r 等学者认为本体有四大特征： ( 1 ) 明确( e x p l i c i t ) 是指“被引用的概念所属的上位类与在使用此概念时的限制条件 应预先得到明确的定义和说明 。 ( 2 ) 形式化( f o r m a l ) 。是指“本体应该具有机器可读性 。 ( 3 ) 共享( s h a r e d ) 。是指在一个本体中，知识所表达的观念、观点应该“抓住知识的 共性，也就是说，它不只是为某一小部分人所接受的，而是为整个群体所接受的，体 现的是共同认可的知识，反映的是相关领域中公认的概念集。 ( 4 ) 概念化，又称概念模型( c o n c e p t u a l i z a t i o n ) 。是指“客观世界中某些现象的一个 抽象模式，该模式是通过定义了这些现象的相关概念形成的 。 本体的开发过程通常是迭代的，即先给出初步的本体框架，然后再对本体进行不断 修改和精炼的过程中补充细节。 对于本体的作用，可以归纳为以下6 剧5 j ： ( 1 ) 人与组织之间的信息交流。本体的核心概念是知识共享，通过减少概念和术语 上的歧义，保持语义上的一致性。 ( 2 ) 系统之间的互操作。应用程序使用本体论实现异构系统之间的互操作，即不同 系统或工具之间的实现通信交流。 ( 3 ) 需求分析和系统设计的基础。在需求分析中，本体论通过对问题和任务的理解 描述，提高明确性，减少分析代价。 ( 4 ) 支持知识重用。本体是领域内重要实体、属性、过程及其相互关系形式化描述 的基础。这种形式化描述可成为软件系统中可重用和共享的组件。 ( 5 ) 显式地定义对领域的认识。 ( 6 ) 将领域知识同使用领域知识的操作性知识分离开来。 近一二十年，本体已被计算机领域所采用，可以有效地进行知识表达，只是查询或 不同领域知识的语义消解。本体还可以支持更丰富的服务发现，匹配，提高自动化程度， 本体知识管理可以实现语义级知识服务，提高知识利用的深度。本体知识管理还可以支 持隐性知识进行推理，方便异构知识服务之间实现互操作，方便融入领域专家知识及经 验知识结构等【6 j 。本体的应用研究： 4 绪论 ( 1 ) 本体的教育应用研究：本体是对领域知识概念的抽象和描述，目的是为了软件 共享、重用。可以用本体来描述远程用户的生存、活动的环境。在分布式系统中，把本 体充当中介的作用，负责沟通a g e n t 和环境之间的信息交流。针对教学系统进行设计的常 用词汇表和框架，在恰当的抽象层次上给智能教育的任务加以形式化。使学习者访问教 学系统发现自己的问题和不足，系统不断调整适合学习场所、学习方法，即学习者和系 统的角色以及只能教学过程的任务能根据实际而变化。设计本体，充分利用现有的教学 资源使远程教育得到应有的发展。 ( 2 ) 在知识检索方面的应用研究：本体使得传统的基于关键词的检索上升到语义检 索的高度。其基本思想是：先建立相关领域的本体，根据本体收集到的信息进行标注， 用户的检索请求按照本体转换成规定的格式，在本体的帮助下匹配出符合条件的资料集 合返回给用户。目前本体应用在信息检索中的著名项目包括( o n t o ) a g e n t ，o n t o b r o k e r 等。 ( o n t o ) a g e n t 的目的是为了帮助用户检索到所需要的w w w 上的已有的本体，o n t o b r o k e r 面向的是w w w 上的网页资源，目的是为用户检索到所需要的网页。 ( 3 ) 信息集成方面的应用研究：分布式信息集成的问题是结构、设施的异构和缺乏 统一的语义集借助本体可以在一定程度上解决语义异构的问题。集成方式有两种：自底 向上，自顶向下。后者的基本思想是先建立相关领域的本体，然后有该本体来统一底层 信息源的语义。前者是先提取底层各信息源的局部资料模式，再在局部资料模式上抽取 局部概念模式，最后在局部感念模式上构造上构造全局概念模式。信息集成的著名项目 k a c t u s 是欧洲的e s p r i t 项目。在k a c t u s 中，主要的知识表示形式c m l ( c o n c e p t u a l m o d e l i n gl a n g u a g e ) ，k a c t u s 支持面向应用和理论的工作包，提供了一个既能对理论 问题做实验，又能进行实际工作的环境。 ( 4 ) 在知识获取方面的应用研究：借助本体能够更加有效地获取知识；在资料挖掘 中，基于本体的资料挖掘可在高层次进行，产生高层次或多层次的规则，甚至在具有语 义意义上的规则上产生挖掘结果；在软件工程方面，本体能帮助更加准确地获取需要信 息。例如o n t k n o w l e d g e 主要目的是提供对弱结构化的在线信息资源进行访问、获取和维 护。o n t k n o w l e d g e 的本体用三层结构对信息进行访问：在最底层( 信息层) ，抽取机器可 处理的元信息；中问层( 表示层) 使用这些元信息对信息资源进行自动访问、创建和维护； 最高层( 访问层) 使用基于a g e n t l 拘技术、人工查询技术和可视化技术等来指导用户去访 问这些信息。 本体的功能主要是实现知识共享和重用，它使得计算机对信息和对语言的理解上升 到语义层次。所以，本体在一些涉及到信息的互操作、知识理解等方面的领域具有很大 的应用前景1 7 1 。 大连交通大学r 学硕十学位论文 3 课题来源 关联规则挖掘是数据挖掘技术中非常重要和应用前景广阔的一种技术。由于关联规 则发现潜在的商业价值和学术价值，所以近年来它一直是数据挖掘研究和应用领域活跃 的前沿。虽然关联规则挖掘问题的提出不过只是十几年的时间，但在算法的研究上已经 积累的大量的成果。同时应当看到，数据库的规模仍然在不断膨胀，对进一步提高挖掘 算法效率的要求仍然十分紧迫。再者就是多层关联数据挖掘的研究，不仅包括同层次关 联规则挖掘的问题，有时也涉及跨层次关联规则的挖掘。另外一点是关联规则中的最关 键因素最小支持度，它是用来缩减搜索空间和限制生成规则的数目，如果仅用单个最小 支持度，就会隐含地假设数据库中的子项有相同的性质或相似的出现频率。而在现实情 况却并非如此，在实际应用中有些子项可能出现很频繁，另外一些子项却很少出现。特 别是在发现频繁集这一步上，由于它是整个流程最耗时间和空间的环节，是关联规则挖 掘的瓶颈。本体的普遍应用及其良好的概念层次结构，利用它可以将进行语义标注，这 样可以产生很好的层次含义，解释性较好【s j 。 本课题就是在这样的背景下产生，着眼于现有算法的不足和缺陷进行改进，利用本 体的概念层次结构旨在可以在高层次进行数据挖掘，提高关联规则的挖掘的效率，是挖 掘出来的规则便于理解。 4 研究内容及组织结构 本文的研究工作源于上述背景，目的是对数据挖掘技术进行深入研究，主要探讨数 据挖掘中的多层关联规则挖掘和多层关联知识管理模型研究问题，具体如下： ( 1 ) 为了挖掘事务数据库中局部关联性比较强的频繁项集，提出基于本体的多层关 联规则的算法挖掘同层次间及不同层次间的最大频繁项集。首先对知识库进行本体的建 立，本体的信息是组织框架，在原始信息的收集、资源对象元数据的提取和信息检索中 都要以领域本体为基础依据。利用p r o t 6 9 6 对主题词添加逆反属性、属性和属性之间的映 射关系，表达主题词表中无法描述的关系。当完成构建工作后，利用p r o t 6 9 6 自动导出 o w l 描述的领域本体，以文件方式保存，为共享本体提供规范化的文件。然后利用本体 的概念层次结构分析最小支持度阀值逐层独立递减和通过提出的公式逐层递减两种策 略来挖掘最大频繁项集，最后进行比较两种策略的效率。最后，将数据挖掘算法m l _ a r 应用于零售业进行多层关联规则挖掘，并对其进行了评价。 ( 2 ) 针对当前知识管理系统存在检索时存在大量无关的知识等问题，本文还提出了 一个新的知识管理模型框架。本框架利用本体的概念规范、语义丰富、层次关系等特点， 6 绪论 并结合本体的知识库和一阶谓语推理引擎对用户的查询请求进行处理，使用户最终检索 到与请求内容匹配较高的信息。 本文组织结构安排如下： 绪论，主要介绍本文的研究背景及实际意义、本体分析、课题来源、本文的研究内 容和组织结构。 第一章，讲述了关联规则的基本概念，论述了与本文相关的研究工作，并详细分析 了多种经典关联规则算法。 第二章，是本文重点，提出基于本体的多层关联规则挖掘算法，分析了三种策略来 挖掘最大频繁项集，根据不同的最小支持度和不同的事务数比较三种策略的挖掘效率。 第三章，针对当前知识管理系统存在检索时存在大量无关的知识等问题，本文还提 出了一个新的知识管理模型框架。并应用于数据挖掘领域，最后作了做了评价。 第四章，将数据挖掘算法应用于超市数据集进行数据挖掘，分析评价挖掘结果。 总结全文。 大连交通大学- t 学硕士学位论文 第一章关联规则概述 关联规贝j j ( a s s o c i a t i o nr u l e s ) 是数据挖掘的一个重要研究方向。关联规则挖掘最初的 形式是零售商的货篮分析，货篮分析是通过发现顾客放入货篮中的不同商品、即不同项 之间的联系，分析顾客的购买习惯。通过了解哪些商品频繁地被顾客同时购买，分析商 品之间的关联，这种关联的发现可以帮助零售商制定营销策略。 r a g r a w a l 9 】等人于1 9 9 3 年首先提出了挖掘顾客交易数据库中项集间的关联规则问 题，其核心方法是基于频集理论的递推方法。此后人们对关联规则的挖掘问题进行了大 量研究，出现了如a p r i o r i t i d t l o l ，a i s ，s e t m ，a p f i o r ih y b r i d ，f p t r e e bj 等挖掘方法。 这些方法主要是从挖掘技术上不断进行改进，包括对a p r i o r i 算法优化、多层次关联规 则算法、多值属性关联规则算法和其他关联规则算法等，以提高算法挖掘规则的效率。 但挖掘的重点仍局限于在某个单一的概念层上进行频繁模式的挖掘。因此引用本体并利 用本体的概念层次结构可以在较高的概念层次上及不同的概念层次上进行数据挖掘，发 现新颖的、有价值的强关联规则。因此，多层关联数据挖掘的研究，不仅包括同层次关 联规则挖掘的问题，有时也涉及跨层次关联规则的挖掘。另外一点是关联规则中的最关 键因素最小支持度，它是用来缩减搜索空间和限制生成规则的数目，如果仅用单个最小 支持度，就会隐含地假设数据库中的子项有相同的性质或相似的出现频率。而在现实情 况却并非如此，在实际应用中有些子项可能出现很频繁，另外一些子项却很少出现。若 子项的出现频率差别很大，却只用一个最小支持度，会碰到如下问题：( 1 ) 若最小支持 度过高就不能找出那些只涉及数据库中稀有子项( r a r ei t e m 即出现频率低的子项) 的规 则；( 2 ) 若为了找出那些只涉及数据库中稀有子项的规则，而把最小支持度设得过低， 则有可能产生组合爆炸，产生过多的规则。因为那些频繁出现的子项会以任何可能的方 式与别的子项相关联而它们中许多是无意义的。 例：在一超市的销售数据中，为了找出那些涉及很少出现的子项的规则( 如平底锅 p a n 和餐刀k n i f e ，它们虽然卖得较少，但利润较高) ，我们需要把最小支持度设得很低， 如0 5 。我们可能会找出一条有用的规则，如p a l l 一l ( 1 1 i f e 【s u p = o 5 ，c o n f = 6 0 】。但0 5 的支持度可能产生下面的无意义规贝, l j b r e a d ，c h e e s e ，m i l k - - b e e r s u p = o 5 ，c o n f = 6 0 】。 因为b r e a d 、c h e e s e 、m i l k 、b e e r 在超市销售中是频繁出现的，涉及这些子项的规则只有 0 5 的支持度是不够的。 关联规则挖掘的任务是在事务数据库d 中找出满足用户给定的最小支持度m i n s u p 阀值和最小置信度m i n c o n f 阀值以及用户感兴趣的、有用的关联规则。因此挖掘关联规 则时主要解决下面两个问趔忆j ： 8 第一章关联规则概述 首先是算法的复杂性，目前大多数关联规则挖掘算法都是为解决这个问题而提出来 的。通常，算法从两个方面来考虑如何提高算法的效率：( 1 ) 减少i o 操作。关联规则 挖掘的数据库的规模有时可达g b 甚至t b 数量级，频繁的i o 操作势必会影响关联规 则的挖掘效率。减少扫描数据库d 的次数可以减少i o 操作，提高效率；( 2 ) 降低需要 计算支持度的候选项集的数量，使其与频繁项集的数量相接近，候选项集数量的减少可 以节省处理候选项所需要的计算时间和存储空间。 其次是必须从产生的规则集中选择用户感兴趣的和有用的规则。最小支持度和最小 置信度并不能确保挖掘出来的关联规则都是用户感兴趣的，其中可能包含许多冗余的、 无意义的规则，而且支持度和置信度高的关联规则又可能是常识性的知识，并不能称之 为信息。因此，制定好关联规则兴趣度衡量标准可以使挖掘出来的关联规则更能满足用 户的需求。 通过对关联规则的研究可以发现，在事务或关系数据库中，一些项或属性所隐含的 概念是有层次的。在许多实际应用中，由于多维数据空间的稀疏性，在低层或原始层的 数据层次上很难找出强关联规则。概念分层的引入使得人们能够在较高的概念层次上进 行数据挖掘，发现新颖的、有价值的强关联规则。在某些情况下，有些项在同层次之间 不存在关联关系，但与不同层次的项之间存在着关联关系。因此，多层关联规则挖掘的 研究，不仅包括同层次关联规则挖掘的问题，有时也涉及跨层次关联规则的挖掘【1 3 1 。这 样有效地提高了应用系统的决策支持能力，对市场策略、商业经营、目标设计、仓储规 划等有很大的现实意义。 1 1 关联规则的基本概念和问题描述 设i = i l , i ：i m ) 是所有项的集合，其中ik ( k = l ，2 ，m ) 称为项。项的集合称为项集， 包含k 个项的项集称为k 一项集。一个事务t ( t r a n s a c t i o n ) 是一个项集，它是i 的一个子 集，每个事务t 有一个唯一标识符t i d 。不同的事务组成事务集d ，它构成了发现关联 规则的事务数据库。如果项集x t ，则称事务t 支持项集x ，也称事务t 包含项集x 。 关联规则是如下形式的一种蕴含形式：xjy ，其中xci ，yci ，且x ny = g 。 支持度( s u p p o r t ) ：设事务集d 中有s 的事务同时支持项集x 和y ，s 称为关联规 则x j y 的支持度。支持度描述了x 和y 这两个项集的并集x w y 在所有事务中出现 的概率。用数学公式来描述，项集x 在d 中的支持度定义为： s u p p o i r t ( x ) ：竖坚罢粤堕型 ( 1 1 ) i d i 、。 关联规则的支持度定义为： 9 大连交通大学t 学硕士学位论文 s u p p o n ( x 叫= 型坐产 ( 1 2 ) = s u p p o r t ( x uy ) 置信度( c o n f i d e n c e ) - 设事务集d 中支持项集x 的事务中，有c 的事务同时也支持 项集y ，c 称为关联规则xjy 的置信度。换句话说，置信度就是指在出现项集x 的 事务t 中，项集y 也同时出现的概率有多大。关联规则x j y 的置信度定义为： c o n f i d e n c e ( xj = ylt da n d ( x w y ) c _ t i i t | t d a n d x t f ) | s u p p o r t ( x v ) y ) s u p p o r t ( x ) ( 1 3 ) 给定一个事务集d ，关联规则挖掘问题就是产生支持度和置信度分别大于用户定义 的最小支持度( m i n s u p ) 和最小置信度( m i n c o n f ) 的关联规则。这种满足最小支持度和最小 置信度的关联规则，我们称之为强关联规则1 1 引。 1 2 关联规则的分类 我们将关联规则按不同的标准进行分类i i5 j ： ( 1 ) 基于规则中处理变量的类型，关联规则可以分为布尔型和数值型。 布尔型关联规则处理的值都是离散的、种类化的，它显示了这些变量之间的关系； 而数值型关联规则处理的是量化值，可以和多维关联规则或多层关联规则结合起来，对 数值型字段进行处理，将其进行动态的分割，或者直接对原始的数据进行处理，当然数 值型关联规则中也可以包含种类变量。 例如：性别= “女 j 职业= “护士 ，是布尔型关联规则：性别= “女 j a v g ( 收 入) = 2 5 0 0 ，涉及的收入是数值类型，所以是一个数值型关联规则。 ( 2 ) 基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。 在单层的关联规则中，所有的变量都没有考虑到现实的数据是具有多个不同的层次 的；而在多层的关联规则中，对数据的多层性已经进行了充分的考虑。 例如：联想台式机h p 打印机，是一个细节数据上的单层关联规则；台式机= h p 打印机，是一个较高层次和细节层次之间的多层关联规则。 ( 3 ) 基于规则中涉及到的数据的维数，关联规则可以分为单维的和多维的。 在单维的关联规则中，我们只涉及到数据的一个维，如用户购买的各种商品；而在 多维的关联规则中，要处理的数据将会涉及多个维。换话说，单维关联规则是处理单个 属性中的一些关系；多维关联规则是处理各个属性之间的某些关系。 例如：啤酒尿布，这条规则只涉及到用户的购买的物品；性别= “女 职业= “护士 ，这条规则就涉及到两个属性信息，是在两个维上的一条关联规则。 1 0 第一章关联规则概述 给出了关联规则的分类之后，在关联规则实际应用中，我们就可以考虑某个具体的 方法适用于哪一类规则的挖掘，某类规则又可以用哪些不同的方法进行处理。 1 3 关联规则挖掘算法 1 3 1 经典频繁集方法 r a g r a w a l 1 6 1 等人于1 9 9 3 年首次提出挖掘顾客交易数据库中项集间的关联规则问 题，其核心方法是基于频繁集理论的递推方法。以后又有很多研究人员对关联规则的挖 掘问题进行了大量的研究。他们的工作包括对原有算法进行优化，如引入随即采样、分 割、并行的思想、分布的思想等等，以提高算法的挖掘效率；提出各种变体，如泛化的 关联规则、周期关联规则等。 r a g r a w a l 等人在19 9 3 年设计了一个基本算法a p f i o d ，提出了挖掘关联规则的一 个重要方法。该方法是一个基于两阶段频繁集的方法，将关联规则挖掘算法分为两个子 问题： ( 1 ) 找出数据库中满足最小支持度m i n s u p 的所有频繁集； ( 2 ) 利用频繁集挖掘出满足最小置信度m i n c o n f 的所有关联规则。 其中第一个问题是算法的核心，a p d o d 算法基于频繁集理论的递推方法来解决这一 问题。其算法描述如下： 输入：事务数据库j d ；最小支持度m i n s u p 输出：d 中的频繁项集l ( 1 ) l ，= 频繁卜项集，； ( 2 ) f o r ( k = 2 ；l g ；k 抖) d ob e g i n ( 3 ) c t = a p r i o r i _ g e n ( l ) ； 候选k 一项集 ( 4 ) f o ra l lt r a n s a c t i o n st dd ob e g i n ( 5 ) c r = s u b s e t ( c l ，t ) ； ( 6 ) f o ra l lc a n d i d a t e sc c 7 ( 7 ) c c o u n t + + ； ( 8 ) e n d ( 9 ) l 2 c e c tl c c o u n t m i n s u p ；频繁k 一项集 ( 1 0 ) e n d ( 1 1 ) 三= u 。厶 大连交通大学工学硕士学位论文 首先产生频繁卜项集l l ，然后是频繁2 一项集l 2 ，直到有某个r 值使得l r 为空，这 个算法停止。这里在第k 次循环中，过程先产生候选k 一项集的集合c k ，c k 是对l k 1 的 频繁集连