（计算机应用技术专业论文）关联规则挖掘在盲文软件中的应用研究.pdf

论文题目： 专 业： 硕士生： 指导教师： 关联规则挖掘在盲文软件中的应用研究 计算机应用技术 李重周 杨君锐 摘要 ( 签名) ( 签名) 数据挖掘是致力于数据分析和理解、揭示数据内部蕴涵知识的技术，它是未来信息 技术应用的重要方法之一。关联规则挖掘是数据挖掘中一个很重要的研究领域。关联规 则挖掘算法是关联规则数据挖掘研究中的主要内容，迄今为止已提出了许多高效的关联 规则挖掘算法。 本文首先对数据挖掘的基本概念、数据挖掘的基本过程和数据挖掘的研究热点等方 面进行了探讨，并对关联规则数据挖掘的经典算法a p r i o r i 进行了较详细的分析和研究， 在此基础上，提出了一种新的不产生候选项集及少量扫描数据库来挖掘频繁项集的超集 树算法s it r e e 。该算法通过搜索数据库，一次性的找出当前项的所有超集从而获得频 繁项集，经实验验证，产生了较好的效果。 然后，通过对盲文软件系统的研究，针对传统盲文软件系统中存在的问题，并在充 分考虑关联规则挖掘算法特性的基础上，再采取不断扫描挖掘对象，组成一个w e b 信 息元数据库，找出其中相互关联的部分，并对其进行分类等方法和手段，将超集树关联 规则挖掘方法应用到盲文软件系统中，从而使盲文软件在网站访问时，达到快速访问相 关内容的目的。 最后，针对关联规则挖掘中可能产生许多无效规则的问题，在对兴趣度度量方法进 行研究的基础上，提出了一种旨在反映项目集之间紧密性、稀有性和简洁性的新的度量 方法一紧密度( 性) ，并利用该度量方法给出了一个基于紧密性的兴趣度挖掘算法，同 时将这种挖掘方法应用到盲文软件的网站访问中。经实验验证，在盲文软件的网站访问 中应用基于紧密性的兴趣规则挖掘方法的访问效率要优于基于超集树的关联规则挖掘 方法。 关键词：数据挖掘；关联规则；兴趣度；紧密度；盲文软件 研究类型：应用研究 s u b j e c t ：r e s e a r c ho na s s o c i a t i o nr u l e sm i n i n ga p p l i e di n t o b r a i l l e s o f t w a r e s p e c i a l t y ：c o m p u t e ra p p l i c a t i o nt e c h n o l o g y n a m e：l ic h o n g z h o u i n s t r u c t o r ：y a n gj u n r u i ( s i g n a t u r e )垒鱼生! 坠旦兰塑望丝 ( s i g n a t ur e ) a b s t r a c t d a t am i n i n gi sat e c h n i q u et h a ta i m st oa n a l y z ea n du n d e r s t a n dl a r g es o u r c ed a t aa n d r e v e a lk n o w l e d g eh i d d e ni nt h ed a t a i th a sb e e nv i e w e da so n eo fi m p o r t a n tw a y si n i n f o r m a t i o np r o c e s s i n g a s s o c i a t i o nr u l em i n i n gi sav e r yi m p o r t a n tr e s e a r c hf i e l di nd a t a m i n i n g t h er e s e a r c ho nt h ea l g o r i t h m so f a s s o c i a t i o nr u l em i n i n gi sak e yt a s ki nd a t am i n i n g o fa s s o c i a t i o nr u l e m a n yh i g h l ye f f i c i e n ta l g o r i t h m si nt h ef i e l dh a v eb e e np u tf o r w a r df o r m i n i n ga s s o c i a t i o nr u l e ss of a r a tf i r s t ，t h ep r o b l e m so nt h ef u n d a m e n t a lc o n c e p t so fd a t am i n i n g ，t h em a i np r o c e s so f d a t am i n i n g ，t h ek e yr e s e a r c ho fd a t am i n i n ga n ds oo nw e r ei n q u i r e di nt h et h e s i s t h e c l a s s i c a la l g o r i t h ma p r i o r ii nd a t am i n i n go fa s s o c i a t i o nr u l ew a sa n a l y s e da n ds t u d i e dm o r e t h o r o u g h t h e nan e ws u p e r - i t e m st r e e ( s i _ t r e e ) a l g o r i t h mw i t h o u tc a n d i d d t ei t e m sa n di n m i n i n gf r e q u e n ti t e m s e t sb a s e do nd a t a b a s es c a n e df e ww a sp u tf o r w a r d i tm i n e sf r e q u e n t i t e m s e t st h r o u g ha l ls u p e ri t e m so ft h ec u r r e n ti t e m sf o u n do n l yo n eb ys c a n i n gd a t a b a s e t h e e x p e r i m e n t a lr e s u l t ss h o wt h a t t h ea l g o r i t h mh a sb e t t e rp e r f o r m a n c e t h e n ，t h ep r o b l e m si nt h et r a d i t i o n a lb r a i l l es o f t w a r es y s t e mw e r es l o v e dt h a tb a s e df u l l y o nt h ec h a r a c t e r i s t i co fa s s o c i a t i o nr u l em i n i n ga l g o r i t h ma f t e rb r a i l l es o f t w a r ew a ss t u d i e d t h o s ew e r et h a ts e a r c h e sa l lo ft h eo b j e c t si nt h ew e b s i t ec o n s t a n t l y , m a k e su paw e bd a t a b a s e ， f i n d st h ei t e m sw h i c ha s s o c i a t ee a c ho t h e rf r o mt h ew e bd a t a b a s e ，c l a s s e st h e ma n ds oo n t h ea l g o r i t h mo fs u p e ri t e mt r e ef o ra s s o c i a t i o nr u l em i n i n gw a sa p p l i e dt ob r a i l l es o f t w a r e s ot h a tt h es p e e dt oa c c e s st ot h ew e bc o n t e n t si nb r a i l l es o f t w a r ew a si m p r o v e d f i n a l l y , an e ww a ya b o u tt h eq u e s t i o nt h a ta s s o c i a t i o nr u l em i n i n gc a l lb r i n gm a n y u n a v a i l a b l ea s s o c i a t i o nr u l e sw a sp r e s e n t e da f t e rt h ei n t e r e s t i n g n e s si na s s o c i a t i o nr u l e s m i n i n gw a sr e s e a r c h e d t h i sw a yw a sc a l l e d t h ei m p a c t i o nw h i c ha i m e dt h er e p o r to f c l o s e n e s s 、s i n g u l a r i t ya n dc o n c i s i o na m o n gt h ei t e m s a na l g o r i t h mo fi n t e r e s t i n gm i n i n g b a s e do nt h ei m p a c t i o nw a sp r e s e n t e db yt h ew a y a l s ot h ea l g o r i t h mw a sa p p l i e dt oa c c e s st o t h ew e bc o n t e n t si nb r a i l l es o f t w a r e t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h ew a yh a sm o r e e f f i c i e n tt h a ns u p e ri t e mt r e ew a yw h e nt h ec o n t e n t so fw e bw e r ea c c e s s e di n b r a i l l e s o f t w a r e k e y w 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 b r a i l l es o f t w a r ei n t e r e s t n e s s i m p a c t i o n t h e s i s ：a p p l i c a t i o nr e s e a r c h 姿料技夫学 学位论文独创性说明 本人郑重声明：所呈交的学位论文是我个人在导师指导下进行的研究工作 及其取得研究成果。尽我所知，除了文中加以标注和致谢的地方外，论文中不 包含其他人或集体已经公开发表或撰写过的研究成果，也不包含为获得西安科 技大学或其他教育机构的学位或证书所使用过的材料。与我一同工作的同志对 本研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意。 学位论文作者签名杏重j 习日期：d 为郎日j7 目 学位论文知识产权声明书 本人完全了解学校有关保护知识产权的规定，即：研究生在校攻读学位期 间论文工作的知识产权单位属于西安科技大学。学校有权保留并向国家有关部 门或机构送交论文的复印件和电子版。本人允许论文被查阅和借阅。学校可以 将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩 印或扫描等复制手段保存和汇编本学位论文。同时本人保证，毕业后结合学位 论文研究课题再撰写的文章一律注明作者单位为西安科技大学。 保密论文待解密后适用本声明。 学位论文作者签名：夺重周 删臌：锄果铭 踏年月1 7 日 1 绪论 1 绪论 数据收集和存储变得越来越容易，数据规模的爆炸性增长也远超出了人们的处理和 理解能力，对于这些庞大的数据，如何寻找和发现其内在的规律，从而产生了数据挖掘技 术。数据挖掘就是从大量的数据中发现和提取有用知识的过程【l j 。数据挖掘正日益得到 各界的重视并广泛应用于各个领域。本章将简要介绍数据挖掘技术及其相关背景和内 容，最后介绍本文的主要研究内容。 1 1 选题背景与研究意义 1 1 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 ， k d d ) 、数据挖掘( d a t am i n i n g ，d m ) 等等更深层次利用数据的阶段。 数据挖掘就是从大量的、不完全的、有噪声的、模糊的和随机的实际应用数据中， 提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。数据挖 掘技术的应用领域十分广阔，它可以从关系数据库、数据仓库、文本和多媒体数据库、 事务数据库和互联网等各种数据源上设法获取诸如分类模型、聚类模型、回归模型、关 联模型和时间序列模型等多种知识模型。可以说，有数据积累的地方，就有数据挖掘技 术的用武之地。目前，数据挖掘技术在货篮数据分析、金融风险预测、产品质量分析、 电信、分子生物学、基因工程研究、站点访问模式发现以及信息搜索等领域得到了广泛 的应用，数据挖掘技术被认为是数据库和人工智能领域中研究、开发和应用最活跃的分 支之一，汇聚了不同领域的研究者，尤其是数据库技术、人工智能技术、数理统计、可 视化技术、并行计算等方面的学者和工程技术人员，投身到数据挖掘这一新兴的研究领 西安科技大学硕士学位论文 域，形成了新的研究热点。 k d d 一词是在1 9 8 9 年8 月于美国底特律市召开的第一届k d d 国际学术会议上正 式形成的【l 】，国际k d d 学术会议起初每两年召开一次，1 9 9 3 年后才每年召开一次。在 几次国际k d d 学术会议上讨论的问题有：定性知识和定量知识的发现；数据汇总； 知识发现方法；数据依赖关系的发现和分析；发现过程中知识的应用；继承的 交互式的知识发现系统；知识发现的应用。 数据挖掘的主要目的是从大量的数据源中采用和发展有关的理论、方法和工具来提 取有用的和使人感兴趣的知识和模式。数据挖掘是从实际的海量数据源中发现知识。由 于数据的完整性、一致性和正确性难以保证，因此数据挖掘算法的效率、有效性和扩充 性就显得非常关键。数据挖掘与传统的数据库查询是不同的，它们的区别主要表现在： 前者是主动的、不生成严格的结果集和不同层次的挖掘，而后者则是被动的、只对字段 进行严格的查询【2 】。归纳起来，数据挖掘有如下特点【l 】： ( 1 ) 处理的数据规模十分庞大。 ( 2 ) 由于用户不能形成精确的查询要求，因此需要靠数据挖掘技术来寻找其可能感 兴趣的东西。 ( 3 ) 数据挖掘对数据的迅速变化作出快速响应，以提供决策支持信息。 ( 4 ) 数据挖掘既要发现潜在规则，还要管理和维护规则，随着新数据的不断加入， 规则需要随着新数据更新。 ( 5 ) 数据挖掘中规则的发现基于统计规律，发现的规则不必适合于所有数据，而且 当达到某一阈值时，便认为有此规则。 1 1 2 研究意义 关联规贝j j ( a s s o c i a t i o nr u l e s ) 挖掘是由r a k e s ha g r a w a l 等人于1 9 9 3 年首次提出的一个 重要的数据挖掘研究课题【3 】。自关联规则诞生以来，国内外业界人士对其进行了大量研 究，并广泛地应用于多个领域，如商业营销、仓储规划、网络故障分析、商品广告邮寄 分析、目录设计、股票交易分析、电子通信、医疗预测等领域。 目前，全世界拥有的巨大数据资源，需要将这些数据资源转换为信息和知识资源。 数据挖掘的出现迎合这种需求。数据挖掘经过二十几年的迅速发展，目前已经存在多种 挖掘技术，其中关联规则的提取是数据挖掘技术研究的一个重要课题。由于其比较符合 人类认知世界的思维模式，所以关联规则挖掘被广泛应用于各行各业。但由于数据挖掘 不是面向任务( 或问题) 的，所以导致其不易被掌握，且容易偏离数据挖掘的目标。目前 的数据挖掘系统或工具很少能真正让用户参与到挖掘过程中，将相关领域的知识融入数 据挖掘系统。随着这些问题的不断解决，将使数据挖掘技术的研究更加深入。 今天，数据挖掘的研究正方兴未艾，焦点将集中在研究专门用于知识发现的数据挖 2 1 绪论 掘任务和数据挖掘方法上，而数据挖掘任务和数据挖掘方法的多样性，给数据挖掘提出 了许多挑战性的课题。数据挖掘语言的设计、高效而有效的数据挖掘方法和系统的开发、 交互和集成的数据挖掘环境的建立以及应用数据挖掘技术解决大型或实际应用问题，都 是目前数据挖掘研究人员、系统和应用开发人员所面临的主要问题。所以对数据挖掘理 论及其应用的研究将具有重要的意义。 1 2 数据挖掘概述 1 2 1 数据挖掘的概念 数据挖掘是人们多年来对数据库技术进行大量研究和开发的成果，在2 0 世纪8 0 年 代末有了很大的发展。数据挖掘是指从数据库或数据仓库的大量数据中揭示出隐含的、 先前未知的、潜在有用的信息的非平凡过程，这个定义是由w j f r a w l e y 、 c t p i a t e t s k y s h a p i o r 【4 】等人提出的。它作为知识发现过程中一个特定的步骤，是一系列技 术及其应用，或者说是对大容量数据及数据间关系进行考察和建模的方法集。它的目标 是将大容量数据转化为有用的知识和信息。 简单的说，数据挖掘就是从( 大型) 数据库或数据仓库中储存的大量的、不完整的、 有噪声的数据中发现潜在的、有价值的、有趣知识的过程。提取的知识一般可以表示为 概念、规则、规律、模式等形式。数据挖掘所研究的知识发现，不是要求发现放之四海 而皆准的真理，也不是要去发现全新的科学定律。实际上，它所发现的知识都是相对的， 都是有特定前提和约束条件的，它是面向特定的应用领域，同时发现的知识还要易于被 用户所理解。 从宏观研究方面数据挖掘的含义可以理解为： ( 1 ) 公认的是w j f r a w l e y 等给出的定义 4 1 ：数据挖掘，就是从大型数据库的数据中 提取人们感兴趣的知识，这些知识是隐含的、事先未知的、潜在有用的信息，提取的知 识可表示为概念( c o n c e p t s ) 、规贝, l j ( r u l e s ) 、规律( r e g u l a r i t i e s ) 、模式( p a t t e r n s ) 等形式。此 定义把数据挖掘的对象仅定义为数据库。 ( 2 ) 也有人认为，数据挖掘是在一些事实或观察的集合中寻找模式的决策支持过程。 也就是说，数据挖掘的对象不仅是数据库，也可以是文件系统，或其他任何数据集合。 数据挖掘d m 与数据库知识发现k d d 的区别与联系：长期以来，d m 和k d d 这两 个术语的范畴和使用界限一直不很清晰，直到k d d 9 6 国际会议上，f a y y a d 、p i a t e t s k y s h a p i r o 和s m y t h 就这两个术语的关系作了如下阐述：k d d 是指从数据库中发现知识的 全部过程，d m 则是全部过程中的一个特定步骤。 3 西安科技大学硕士学位论文 1 2 2 数据挖掘的演变 随着数据库技术和信息技术的迅速发展，大型数据库系统的广泛应用，企业积累的 数据量急剧地增加。从信息处理的角度，希望计算机帮助人们分析与理解数据，帮助我 们做人力所不能及的事情，因此数据的丰富就带来了对强有力的数据分析工具的需求。 传统的数据分析方法，只能获得这些数据的表层信息，很难对这些数据进行更深层次的 处理，不能发现这些数据内部隐含的规则和规律，而这些规则和规律很有可能对人们的 行为具有重要的指导作用。快速增长的海量数据收集、储存在大型和大量数据库中，没 有强有力的工具，要理解它们已经远远超出了人的能力。决策者缺乏从海量数据库中提 取有价值知识的工具。其结果是，大型数据库变成了“数据冗余库”。人们亟需一种能从 海量数据中发现潜在知识的工具，以解决“数据丰富与知识贫乏”的矛盾。 1 9 8 9 年在美国底特律召开的第1 1 届国际人工智能会议上，首先提出数据库中的知 识发现概念。其目的是在数据库中发现先前不被人们所知道的、潜在的知识和有用的信 息。随后，它引起了国际人工智能和数据库等领域的专家的广泛关注。1 9 9 5 年，在加拿 大蒙特利尔召开的首届知识发现和数据挖掘国际学术会议上，数据挖掘这一术语被学术 界正式提出，数据挖掘技术的出现为海量知识发现带来了新的曙光。 数据挖掘技术在数十年的发展中其实是一个逐渐演变的过程。在电子化数据处理的 初期，人们就试图通过某些方法来实现自动决策支持，当时机器学习成为人们关心的焦 点。之后，随着神经网络技术的形成和发展，人们的注意力转向了知识工程。知识工程 不同于机器学习，它不是为计算机输入范例由其生成出规则，而是直接为计算机输入已 被代码化的规则，计算机通过使用这些规则来解决某些问题，专家系统就是这种方法所 得到的成果。2 0 世纪8 0 年代人们又在新的神经网络理论的指导下，重新回到机器学习 的方法上，并将其成果应用于处理大型商业数据库，从而产生了一个新的术语一数据 库中的知识发现。 k d d 泛指所有从源数据中发现模式或联系的方法，常用来描述整个数据挖掘的过 程，包括最开始的制定业务目标到最终的结果分析。近几年，数据挖掘中有许多工作逐 渐开始使用统计方法来完成，并将统计方法与数据挖掘有机的结合起来。 目前数据挖掘的研究重点也逐渐从发现方法转向系统应用，注重多种发现策略和技 术的集成，以及多种学科之间的相互渗透。这些学科包括数据库技术、人工智能p j 、机 器学习【6 1 、神经网络【7 1 、统计学引、模式识另j t 9 1 、知识库系统、知识获取、信息检索、高 性能计算和数据可视化等。数据挖掘这门交叉学科，把人们对数据的应用从低层次的简 单查询，提升到从数据中挖掘出有用的信息用于决策支持。经过十几年的努力，数据挖 掘技术的研究已经取得了丰硕的成果，不少软件公司已经研发出数据挖掘软件产品，例 如，i b m 公司开发的q u e s t 和i n t e l l i g e n t m i n e ra n g o s ss o f t w a r e 开发的基于规则和决 4 1 绪论 策树【6 】的k n o w l e d g es e e k e r ；a d v a n c e ds o f t w a r ea p p l i c a t i o n 开发的基于人工神经网络的 d bp r o f i l e ：加拿大s i m o nf r a s e r 大学开发的d b m i n e r ；s g i 公司开发的m i n e s e t 等。在 我国，数据挖掘技术的研究也引起了学术界的高度重视，并逐步成为科学界的热点研究 课题。与国外相比，国内对数据挖掘和知识发现的研究稍晚，没有形成整体力量。1 9 9 3 年国家自然科学基金首次支持了对该领域的研究项目。目前，国内的许多科研单位和高 等院校也在竞相开展知识发现的基础理论及其应用研究。 1 2 3 数据挖掘的过程 数据挖掘过程一般由确定挖掘对象、数据准备、模型建立、数据挖掘、结构分析表 述和挖掘应用这几个主要的阶段组成。数据挖掘可以描述为这几个阶段的反复过程【l j 。 ( 1 ) 数据准备 数据准备阶段又可细分为4 个过程：数据集成、数据选择、数据预处理和数据转换。 数据集成。数据集成是将多个文件或多数据库运行环境中的数据进行合并处理， 解决语义模糊性，处理数据中的遗漏和清洗数据等。 数据选择。数据选择是指为数据挖掘目标而搜索和选择有关的数据，这包括不 同格式数据的转换以及不同部门数据的统一和汇总。 数据预处理。数据预处理是对数据进行清理和充实。数据库中重要的数据是准 确的，不重要的数据可能存在污染，预处理就是用于解决数据的局限性问题。 数据转换。数据转换的一个重要工作是对数据进行编码。数据库中字段( 属性) 的不同取值转换成数码形式将有利于搜索。 ( 2 ) 数据挖掘 这个阶段进行实际的挖掘操作，即利用机器学习、统计分析等方法，从数据库中发 现有用的模式或知识( 这里，模式是浓缩数据的信息形式，如精炼数据库、表格、产生 式规则、决策树、神经网络的权值等) 。 选择数据挖掘方法。如统计分析、机器学习、模式识别和人工神经元方法等。 选择数据挖掘算法。选择用来查找模式或符合数据模型的算法，确定合适的模 型和参数。另外，数据挖掘方法必须和目标相匹配。 数据挖掘。查找感兴趣的模式。模式一般表示为一种特殊的形式或一套表达方 式，如关联规则、分类规则或分类树、回归结构和聚类集等。除了选择合适的挖掘算法 以外，其余的一切工作都可自动完成。 ( 3 ) 结果分析表述和挖掘应用 结果表达。尽量直观的表达挖掘结果，便于用户理解和使用，可使用可视化方 法表示为图表等形式。 结果评价。筛选和评价挖掘结果中的有用部分，查找可接受的结果。可定义兴 5 西安科技大学硕士学位论文 趣指标，考虑结果的正确度、新颖度、有用性和简单性，把信息从输出中过滤出来。利 用可视化方法帮助用户解决所提出知识的有效性或对基本的数据或现象做出结论。 知识巩固。把挖掘出的信息结合到执行系统中，了解这些信息的作用或证明这 些信息。用预选知道且可信的信息来检查和验证所挖掘出的信息，解决可能存在的矛盾。 当然，在有些情况下，也可以只是简单地记录所挖掘出的信息并把它报告给用户， 由用户进一步分析。根据最终用户的决策目的对提取的信息进行分析和评价把最有价值 的信息区分出来，并且通过决策支持工具提交给决策者。因此，这一步的任务不仅是把 结果表达出来( 例如采用信息可视化方法) ，还要对发掘出的数据模式进行评价过滤处 理。上述处理阶段可以根据用户的目的重新进行某些处理过程，同时在处理的任意阶段 都可以返回以前的阶段进行再处理。 1 2 4 数据挖掘的应用 数据挖掘技术旨在发现大量数据中所隐藏的知识，以用来解决“数据丰富而知识贫 乏”的问题。随着数据库和网络技术的广泛应用，加上使用先进的自动数据生成和采集 工具，人们所拥有的数据量急剧增加，使数据挖掘技术在科学研究、金融投资、市场营 销、保险、医疗卫生、产品制造业、通信网络管理等行业已得到广泛应用，而数据挖掘 技术从一开始就是面向应用的。 ( 1 ) 科学研究 在信息量极为庞大的天文、气象、生物技术等领域中，由于所获得的大量实验和观 测数据靠传统的数据分析工具己难于对付，因此对功能强大的智能化自动分析工具要求 迫切，这种需求推动了k d d 技术在科学研究领域的应用发展，并且已获得一些重要的 应用成果。 ( 2 ) 金融投资 在银行和金融机构中产生的金融数据通常相对比较完整、可靠，而且数据质量较高， 因此，数据挖掘在这一领域中的应用相对比较成熟，也取得较好的社会效益和经济效益。 由于金融投资的风险很大，在进行投资决策时，需要对各种投资方向的有关数据进行分 析，以选择最佳的投资方向，而数据挖掘则是通过对己有数据进行处理，并利用学习得 到的模式进行市场预测，以选择最佳的投资方向，可使金融投资的风险降低。通过分析 市场波动的因素，建立预测模型，进行投资分析和预测，改进预测市场波动的能力，为 投资决策提供科学的依据。 ( 3 ) 保险业 随着社会保障体系的日益健全，保险业取得了蓬勃的发展，发挥着越来越重要的作 用。保险是一项风险业务，保险公司的一个重要工作就是进行风险评估。通过研究证明， 可以利用数据挖掘技术来进行风险分析，在保险公司建立的保单及索赔信息数据库的基 6 1 绪论 础上，寻找保单中风险较大的领域，从而得出一些实用的控制风险的规则，以指导保险 公司的工作。数据挖掘技术在保险业中的应用，有利于保险公司开展业绩评价、财务预 算、市场分析、风险评估和风险预测等，大大提高企业防范和抵抗经营风险的能力和水 平，也为管理人员提供科学的决策依据。 ( 4 ) 零售业 零售业是数据挖掘应用较为活跃的一个领域。了解客户的购买习性和趋向，对于零 售商制定销售策略是至关重要的。销售分析人员运用关联规则挖掘技术对大量的销售数 据进行分析，可以发现顾客购买模式和趋势，改进服务质量，取得更好的顾客保持力和 满意程度，提高货品销售比率，设计更好的货品运输与分销策略，减少商业成本。购物 篮分析是数据挖掘技术应用在零售业中的一种有效方式，可用于销售搭配、产品目录设 计、产品定价和促销等。 ( 5 ) 制造业 随着现代技术越来越多地应用于制造业，产品生产已不是人们想象中的手工劳动， 而是集成了多种先进科技的流水作业。在产品的生产制造过程中常伴随着大量的数据， 如产品的各种加工条件或控制参数，这些数据反映了每个生产环节的状态，不仅为生产 的顺利进行提供了保证，而且通过对这些数据的分析，得到产品的质量与这些参数之间 的关系。这样通过数据挖掘对这些数据的分析，可以对改进产品质量提出针对性很强的 建议，而且有可能提出新的更高效节约的控制模式，从而为制造厂家带来极大的回报。 ( 6 ) 电信业 电信业已经从单纯的提供市话和长话服务演变成提供综合电信服务，如语音、传真、 寻呼、移动电话、图像、电子邮件、计算机和w e b 数据传输，以及其他数据通信服务。 而且随着许多国家对电信业的开放和新兴计算与通信技术的发展，电信市场正在迅速扩 张并越发竞争激烈。因此，利用数据挖掘技术来帮助理解商业行为、确定电信模式、捕 捉盗用行为、更好地利用资源和提高服务质量是非常有必要的。 ( 7 ) 医疗保健 医疗保健行业有大量的数据需要处理。但这个行业的数据一般是由不同的信息系统 所管理，数据以不同的格式保存。从总体上看数据是无组织的。在这个行业中，数据挖 掘最关键的任务是进行数据清理，预测医疗保健的费用。 1 2 5 数据挖掘的发展趋势 以下简要介绍数据挖掘的发展趋势。 ( 1 ) 应用的探索 数据挖掘最早应用于零售业和金融业的数据分析。它是一种功能强大的应用技术， 主要为企业和管理人员进行销售和决策提供依据。目前在保险业、制造业、电信和医学 7 西安科技大学硕士学位论文 等领域也得到了广泛的应用，并取得了显著的效果。信息产业的发展为数据挖掘提供了 广阔的空间，数据挖掘技术的应用范围将不断得到拓宽，特别是在生物工程、商业智能、 网络服务等领域的应用将成为新的研究热点。 ( 2 ) 可伸缩的数据挖掘方法 数据挖掘必须尽可能交互式地、有效地处理大量数据。由于数据量在不断地激增， 因此针对单独和集成的数据挖掘功能的可伸缩算法显得十分重要。一个重要的方向是所 谓基于约束的挖掘( c o n s t r a i n t b a s e dm i n i n g ) 1 0 , 1 1 】。它致力于在增加用户交互的同时， 如何改进挖掘处理的总体效率。它提供了额外的控制方法，允许用户说明和使用约束， 引导数据挖掘系统对感兴趣模式的搜索。 ( 3 ) 数据挖掘与数据库系统、数据仓库系统和w 曲数据库系统的集成【1 2 1 3 j 数据库系统、数据仓库系统和w w w 己经成为信息处理系统的主流，而数据挖掘 系统的理想体系结构是与数据库和数据仓库的紧耦合方式。事务管理、查询处理、联机 分析处理和联机分析挖掘应集成在一个统一框架中。这将保证数据的可获得性，数据挖 掘的可移植性、可伸缩性、高性能以及对多维数据分析和探查的集成信息处理。 ( 4 ) 数据挖掘语言的研究1 1 4 - 1 6 在进行数据挖掘时，让挖掘系统自动挖掘整个大型数据库或数据仓库中隐藏的所有 有价值的知识往往是不切实际的，总是需要在用户的指导下进行有目的的挖掘。这就需 要为用户提供一组与数据挖掘系统通信的语言，可以把这组语言称为数据挖掘语言。这 组语言用于说明用户感兴趣的数据集、要挖掘的知识类型、用于指导挖掘过程的背景知 识、模式评估兴趣度量以及如何显示所发现的知识等等。这组语言使得用户可以在数据 挖掘的过程中与数据挖掘系统进行交互，从不同的角度和深度检查发现结果。研究专门 用于知识发现的数据挖掘语言，也许会像s q l 语言一样走向形式化和标准化。 ( 5 ) 可视化数据挖掘 可视化数据挖掘是从大量数据中发现知识的有效途径，系统研究和开发可视化数据 挖掘技术将有助于推进数据挖掘作为数据分析的基本工具。目前数据挖掘的可视化仅体 现在结果的简单描述，并没有达到真正意义上的可视化。数据可视化、挖掘过程可视化 和结果可视化，将揭开数据挖掘复杂和神秘的面纱，使其变得更为生动、形象和具体， 用户可以随时了解整个过程的进展情况，减少了行为过程的盲目性。数据和结果的图形 展示可以放大、缩小、平移、旋转和变换角度，使分析人员和用户更加容易理解，这将 大大推动数据挖掘工具在发现知识和数据分析中的应用。因此，加强数据可视化和知识 发现过程的可视化具有重要的理论意义和应用价值。 ( 6 ) 复杂数据类型挖掘的新方法 复杂数据类型挖掘是数据挖掘中一项重要的前沿研究课题。虽然在地理空间挖掘、 多媒体挖掘、时序挖掘、序列挖掘以及文本挖掘方面取得一些进展，但它们与实际应用 8 1 绪论 的需要仍存在很大的距离。对此需要进一步的研究，尤其是把针对上述数据类型的现存 数据分析技术与数据挖掘方法集成起来的研究。 ( 7 ) w 曲挖掘 由于w e b 上存在大量信息，并且w e b 在当今社会扮演越来越重要的角色，有关w e b 内容挖掘、w e b 日志挖掘和因特网上的数据挖掘服务，将成为数据挖掘中一个最为重要 和繁荣的子领域。 ( 8 ) 数据挖掘中的隐私保护与信息安全 随着数据挖掘工具和电信与计算机网络的日益普及，数据挖掘要面对的一个重要问 题是隐私保护和信息安全。需要进一步开发有关方法，以便在适当的信息访问和数据挖 掘过程中确保隐私保护与信息安全。 1 3 论文的主要工作 本文的主要工作是在对关联规则挖掘技术进行较深入分析和研究的基础上，将其应 用到盲文软件系统中。具体内容包括以下几个方面： ( 1 ) 对数据挖掘的演变、数据挖掘的过程、数据挖掘的应用及其数据挖掘的发展 趋势等相关概念进行了概括性的综述，并对选题背景与研究意义进行了介绍。 ( 2 ) 对关联规则的定义、关联规则的挖掘过程、关联规则的种类与关联规则常用 挖掘方法等问题进行了介绍。然后对关联规则经典挖掘算法a p r i o r i 进行了较系统和全 面的分析与研究。 ( 3 ) 对盲文软件系统的开发背景、研究现状、设计思想及组织结构等有关盲文软 件系统的基本情况进行了简介，并指出了其存在的缺陷和不足。 ( 4 ) 针对a p r i o r i 算法的不足，提出了一种新的不产生候选项集及少量扫描数据库 来挖掘频繁项集的超集树挖掘算法s it r e e ( s u p e r - i t e m st r e e ) 。并将该算法应用到盲文 软件系统中，从而使盲文软件在网站访问时，达到快速访问相关内容的目的。 ( 5 ) 针对传统关联规则挖掘下的支持度置信度评价标准的问题，在对兴趣度度量 标准进行研究的基础上，提出了旨在反映项目集之间紧密性、稀有性和简洁性的新的度 量方法一紧密度( 性) ，并利用该度量方法给出了一个基于紧密性的兴趣度挖掘算法， 同时将这种挖掘方法应用到盲文软件的网站访问中。 1 4 本章小结 本章首先对本文的选题背景与研究意义进行了分析与探讨，然后对数据挖掘的发展 里程、数据挖掘的主要过程、数据挖掘的应用及数据挖掘的发展趋势等有关数据挖掘的 基本情况进行了介绍，最后对论文的主要工作进行了描述。 9 西安科技大学硕士学位论文 2 关联规则挖掘理论和算法 关联规则( a s s o c i a t i o nr u l e s ) 挖掘是数据挖掘领域中一个非常重要的研究课题，它 是由a g r a w a l 等1 人在1 9 9 3 年首先提出的，是k d d 研究的重要内容。关联规则挖掘就 是从大量的数据中挖掘出有价值的描述数据项之间相互联系的有关知识。最初提出它的 动机是针对购物篮分析问题的，其目的是为了发现事务数据库中不同商品之间的联系规 则。这些规则刻画了顾客购买行为模式，可以用来指导商家科学地安排进货、库存以及 货架设计等。例如，经典的“啤酒和尿布”就是一个关联规则的例子，啤酒和尿布分别 是一个数据项集，通过关联分析，发现这两个数据项集之间潜在的关系，以指导销售实 践。通过关联规则的挖掘可以发现数据库项目间一定的内在联系，能有效的提高应用系 统的决策支持能力。在客户关系管理、零售业等方面，关联规则挖掘能找出产品销售模 式、客户的购买习惯、客户特性等，从而制定相应的商业决策，如促销方案的制定、客 户服务决策的分析等。 本章在提出关联规则基本概念的基础上，概述了关联规则分类、关联规则的挖掘过 程、经典算法a p f i o f i 、以及一些优化算法。 2 1 关联规则挖掘的基本概念 2 1 1 关联规则描述1 1 7 l 关联规则是描述数据库中数据项之间存在的潜在关系的规则，形式为 “a l a a 2 a a m = b l 八b 2 b m ”，其中a i ( i = 1 , 2 ，m ) ，b i ( j = 1 , 2 ，1 1 ) 是 数据库中的数据项。数据项之间的关联规则表现为根据一个事务中某些项的出现，可推 出另一些项在同一事务中也出现。 关联规则问题描述如下： 设仁 f j ，易，如) 是m 个不同项目的集合。d 是所有事务的集合( 即事务数据库) ， 每个事务丁是一些项目的集合，丁包含在，中，即t c i ，并且每个事务可以用唯一的标 识符t i d 来标识。 【定义2 1 】设x 为i 中某些项目的集合，简称为项集( i t e m s e t ) ，如果x c t ，则称事 务t 包含x 。 关联规则表示为：x j y 的蕴涵式，这里x c - i ，y c i ，并且x n y 巾。d 中的规 则x j y 是由支持度( s u p p o r t ，简称s u p p 或s ) 和置信度( c o n f i d e n c e ，简称c o n f 或c ) 来约束的。支持度表示规则出现的频度，置信度表示规则的强度。具体描述是： s u p p o r t ( x j y ) = p ( x u y ) 1 0 2 关联规则的概论及经典算法 c o n f i d e n c e ( x j y ) = p ( y x ) 【定义2 2 】在进行关联规则挖掘时，要求用户预先设定支持度和置信度阈值，即在挖 掘过程中只产生满足这两个阈值要求的关联规则，对于这样的支持度和置信度通常分别 称为最小支持度( m i n i m u ms u p p o r t ) 和最小置信度( m i n i m u mc o n f i d e n c e ) 。对于满足最 小支持度和最小置信度要求的关联规则称为强规则。 文中，为方便起见把支持度和置信度分别简记为s 和c ，最小支持度和最小置信度 分别简记为m i n s u p 和m i n c o n f , 它们的取值在0 到l 之间。另外d 中包含的事务数表示 为i d | x 中包含的项目数表示为i x i 。 【定义2 3 】项集x 在d 中出现的频率，即d 中包含x 的事务t 的个数，称为x 在d 中的支持数( s u p p o r tc o u n t ) ，简记为c o u n t 。 根据以上支持度和支持数的定义，可以得出某项集x 的支持数与支持度的关系是 c o u n t = s xi d i ，另外与最小支持度相对应，把支持数阈值定义为最小支持数( m i n i m u m s u p p o r tc o u n t ，简记为m i n c o u n t ) ，它和最小支持度的关系是m i n c o u n t = m i n s u p i d l 。 【定义2 4 】对于项集x ，如果x 中包含有k 个项目，则x 称为k 项集。例如项集x = a ， b 就是一个2 项集。 【定义2 5 】若项集x 的支持度不小于最小支持度，则称x 为频繁项目集，即x 满足 最小支持度要求，否则，称x 为非频繁项目集。若某一项目m 满足最小支持度要求， 则称m 为频繁项目，所有频繁项目的集合称为频繁1 项集，记为l l ；满足最小支持度 要求的k 项集称为频繁k - 项集，所有频繁k - 项集的集合记为l k 。在有些文献中把频繁 项目集又称为频繁模式，本文采用频繁项目集或频繁项集来表示。 2 1 2 关联规则的分类 传统的关联规则挖掘形式是购物篮分析，但关联规则绝不仅此一种。可以根据以下 标准对这些关联规则进行分类： ( 1 ) 根据关联规则所处理的具体值来进行分类 若一个规则仅描述数据项是否出现在这种情况间的联系，那么这种关联规则就是一 个布尔关联规则。例如规则( 2 1 ) 描述的就是有关市场购物分析所获得的一条布尔关联 规则。 购买电脑j 购买电子词典【s u p p