（计算机软件与理论专业论文）数据挖掘技术在图书管理系统中的应用研究.pdf

大连理工大学硕士学位论文 摘要 图书馆自动化为传统的图书馆服务带来了新的契机，不仅改变了图书馆传统的服务 方式，而且为图书馆积累了大量的宝贵数据。图书馆面向读者的信息需求与形式越来越 多样化，读者除了对本专业的理论和新技术知识的需求外，还需要提高自身的文化素养 和品味。对文献资料的类型需求也越来越来广泛，因此个性化的信息服务成为图书馆发 展的新趋势。 随着数据挖掘技术的发展，其研究重点逐渐由发现方法转向实际应用。数据挖掘技 术在商业领域取得了巨大的应用价值，在社会的其他领域应用也越来越广泛。将数据挖 掘技术应用于图书馆管理系统中，充分分析和处理图书馆的日常业务数据，如：读者的 借阅记录、图书的被借阅信息等，为图书馆合理分布馆藏、准确把握读者的个性需求， 提供个性化服务提供决策支持。使图书馆为读者提供个性化信息服务。 本文重点研究了聚类分析及关联规则发现技术，在分析吉林化工学院现有图书馆管 理系统的基础上，提出了数据挖掘在图书馆的应用模式。本文所做的工作主要体现在以 下几点：给出了数据挖掘技术在图书馆系统中的应用模式，将数据挖掘技术与图书馆服 务结合在一起；研究了聚类分析技术及其在图书馆中的应用，利用k - m e a n s 算法实现了 对读者和图书的聚类分析；采用a p r i o r i 算法，减少了对事务集的扫描，提高了频繁集 的生成效率。在图书馆系统中应用关联规则技术实现了对图书借阅历史记录数据从分类 角度挖掘，应用关联规则结果为图书馆合理分布馆藏、准确把握读者的个性需求。 关键词：聚类分析；关联规则；图书馆；个性化推荐服务 大连理工大学硕士学位论文 r e s e a r c ha n da p p l i c a t i o no fd a t am i n i n gi nl i b r a r ym a n a g e m e n ts y s t e m a b s t r a c t t h ea u t o m a t i s mp r o v i d e sn e wo p p o r t u n i t i e sf o r t h el i b r a r ym a n a g e m e n t ，w h i c hn o to n l y h a sc h a n g e dt h ew a yo ft h et r a d i t i o n a ls e r v i c eb u ta l s oh a sa c c u m u l a t e dal o to fi m p o r t a n td a t a t h ei n f o r m a t i o nt h er e a d e r sr e c e i v ef r o mt h el i b r a r yi sm o r ea n dm o r ed i v e r s i f i e d ，s ot h e r e a d e r sn e e dh a v eag o o dc o m m a n do fp r o f e s s i o n a lt h e o r ya n dt e c h n i q u e b e s i d e s ，t h er e a d e r s h a v et op r o m o t et h e i rc u l t u r es c h o l a r s h i pa n dt a s t e t h ed e m a n d sf o rt h ed o c u m e n t a r yi s b e c o m i n gm o r ev a r i a b l e ，w h i c hr e s u l t si nt h en e wt r e n do ft h ed e v e l o p m e n to ft h ei n d i v i d u a l i n f o r m a t i o ns e r v i c ei nt h el i b r a r y w i t ht h ed e v e l o p m e n to ft h ed a t am i n i n g ，t h er e s e a r c hf o c u s e so na p p l i c a t i o n 舶m d i s c o v e r ym e t h o d d a t am i n i n gh a sa c h i e v e de n o r m o u s l ya p p l i c a b l ev a l u ei nb u s i n e s s i tw i l l b ew i d e l ya p p l i e di ns o m eo t h e rs o c i a la r e a i tc a nt h o r o u g h l ya n a l y z ea n dd e a l 、i t l lt h ed a i l y b u s i n e s sd a t ai fi ti sa p p l i e di nl i b r a r ym a n a g i n gs y s t e m f o ri n s t a n c e ，t h er e a d e r s ，h i s t o r i c a l b o r r o w i n gr e c o r d ，t h el e n d i n gi n f o r m a t i o no ft h eb o o k s ，e t c i tc a nh e l pt h el i b r a r yt ol a yo u ta c o l l e c t i o no fb o o k sp r o p e r l y ，g r a s pt h er e a d e r si n d i v i d u a ld e m a n d sa c c u r a t e l ya n dp r o v i d e d e c i s i v es u p p o r t t h i st h e s i si sg o i n gt of o c u so nh o wt of i n do u tt h et e c h n i q u eo fc l u s t e ra n a l y s i sa n d a s s o c i a t i o nr u l e i tp u t sf o r w a r dt h ea p p l i c a t i o nm o d e lo ft h ed a t am i n i n gi nl i b r a r yw h i c h b a s e do nt h ea n a l y s i so ft h ep r e s e n tl i b r a r i a n m a n a g e m e n ts y s t e m t h et h e s i sm a i n l yc l a r i f i e s t h ef o l l o w i n gp o i n t s ：i tp o i n t so u tt h ea p p l i c a t i o nm o d e lo ft h ed a t am i n i n gw i t hl i b r a r y s e r v i c e i tm a k e sar e s e a r c ha b o u tt h ea p p l i c a t i o no fc l u s t e ra n a l y s i si nt h el i b r a r y i tm a k e su s e o fk - m e a n sa l g o r i t h mt oa c h i e v et h ec l u s t e ra n a l y s i so ft h er e a d e r sc u td o w nt h es c a no f i t e m s e ta n dr a i s et h eg e n e r a t i v er a t i oo ff r e q u e n ti t e m s e t t h eh i s t o r i c a lr e c o r d so ft h eb o o k s c a i lb em i n e d 、i n lt h ea p p l i c a t i o no fa s s o c i a t i o nr u l ei nt h el i b r a r ym a n a g e m e n ts y s t e ma n d t h ei n d i v i d u a lr e c o m m e n ds e r v i c ef o rt h er e a d e r sc a nb ea c h i e v e dt h r o u g hc l a s s i f i c a t i o n m i n i n ga n da p p l i c a t i o no fa s s o c i a t i o nr u l er e s u l t k e yw o r d s ：c l u s t e ra n a l y s i s ；a s s o c i a t i o nr u l e ；l i b r a r y ；i n d i v i d u a lr e c o m m e n ds e r v i c e i i i 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名：纭避日期：逝仝：( 1 垒 人连理f ：人学硕+ 研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论 文版权使用规定”，同意大连理工大学保留并向国家有关部门或机构送交学 位论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连理工大 学可以将本学位论文的全部或部分内容编入有关数据库进行检索，也可采 用影印、缩印或扫描等复制手段保存和汇编学位论文。 作者签名2i 肇建硅 导师签名= 塞垂 勤立辟上月1 日 大连理工大学硕士学位论文 1绪论 1 1 研究背景及意义 信息技术的迅速发展，改变了我们的工作和生活。各行各业都建立了相关的信息系 统，在信息化进程中，积累了大量的数据。这些数据间存在大量的有价值的信息，能够 为企业和部门的决策者提供决策支持。如何充分利用这些数据，分析和处理使之成为决 策的辅助信息，是当前急需解决的问题。 数据挖掘技术为挖掘数据资源提供了技术支持。自从1 9 8 9 年第1 1 届国际联合人工 智能学术会议上首次提出k d d 这一概念以来【l 】，信息挖掘技术日益受到人们的关注， 并己经成为当前计算机领域的一大热点，其研究的重点也逐渐从发现方法转移到系统应 用，并且注意多种发现策略和技术的集成以及多学科之间的相互渗透。现今，数据挖掘 的应用领域越来越广泛，从早期的商业应用，发展到科学研究、电子商务、产品控制、 金融行业、教育教学等多个领域，并且有了许多成功的应用。在科学实验中，f a y y a d 和他的同事们在加利福尼亚p a s a d e n a 的j e tp r o p u l s i o n 实验室【2 】，应用决策树和基于规则 的方法发现了一批新的类星体；在零售行业，货篮分析帮助商店确定货架布局以促进销 售；在金融领域，孤立点的发现用以预测和预防可疑信用卡交易、恶意透支等；在销售 行业，通过在c r m 中应用，提高销售的成功率；在制造业，用来控制产品生产，降低 次品率。 图书馆自动化为传统的图书服务带来了新的契机，不仅改变了传统的服务方式，而 且积累了大量的宝贵数据。图书馆面向用户的信息需求与形式越来越多样化，用户除了 对本专业的理论和新技术知识的需求外，还需要提高自身的文化素养和品味。对文献资 料的类型需求也越来越来广泛。因此个性化的信息服务成为了新的发展趋势【3 1 。个性化 服务需要用户的兴趣、图书间的关联等信息的支持，而这些信息能够通过对图书馆的日 常业务数据分析和挖掘获得，如：用户的借阅记录、图书的被借阅信息等。除此之外， 对业务数据的挖掘还可以为图书馆合理分布馆藏、为准确把握用户的个性和需求，提供 个性化服务提供决策支持。 因此，研究数据挖掘在图书馆系统中的应用具有非常重要的实际意义。 1 2 图书馆信息化建设 从七十年代中期，计算机应用技术进入我国图书馆领域，少数图书馆研究机构开展 了计算机图书馆应用研究，以1 9 7 6 年中国科学院图书馆设立计算机组，与计算所合作 试编中文文献的机读数据，进行批处理的定题检索服务、编制馆藏目录和新书通报的试 数据挖掘技术在图书管理系统中的应用研究 验为标志，我国图书馆计算机应用己走过了2 4 个年头。2 4 年来，我国图书馆计算机应 用恰好与国家五年计划合拍，大至可分为四个阶段： 第一阶段( 1 9 7 6 - - 1 9 8 0 ) ，摸索、起步阶段。这阶段主要是学习、借鉴国外的经验， 探索中文文献机读数据的编制。1 9 7 4 年，国家批准了“汉字信息处理工程研制工作， 这项工程包括汉字通讯、汉字激光照排、汉字情报检索的计算机应用软件、汉语主题词 语表及机器翻译等。中国图书馆界的自动化研究、试验工作正是从此起步【4 1 。1 9 7 6 年中 国科学院图书馆第一个成立计算机组，与中科院计算机所合作试编了中文文献的机读数 据，输入文献3 0 0 余篇，图书3 0 0 余册。当时由于计算机功能的限制，上述试验还不能 使用汉字信息，只能使用汉语拼音对中文文献加以描述和处理。 第二阶段( 1 9 8 1 - - 1 9 8 5 ) ，实验总结阶段。图书馆界通过5 年多的探索学习，一些有 条件的图书馆相继建立了相应的组织，并配备人员，进行培训，积极参加m a r c 协作 组，推进对l c m a r c 的研究开发，结合各单位的需要，进行一些探索性地研究或研制。 第三阶段( 1 9 8 6 - - 1 9 9 0 ) ，实用开发阶段。在积累了一定的实践经验和队伍建设的基 础上，以及性能较高和较大容量的微型计算机问世，为图书馆自动化提供了物质条件， 在图书馆的流通、采访、编目、期刊管理、书目或文献检索以及内部管理等各个工作领 域都开展了研究和应用。 第四阶段( 1 9 9 1 一今) 提高、并轨阶段。这一阶段是计算机技术的飞速发展阶段。从 硬件上，p c 机经历了2 8 6 ，3 8 6 ，4 8 6 ，5 8 6 ，奔腾和p i i - i 各时代，现己进入p i i i 时代。与 计算机的硬件的发展相应：操作系统经过了字符界面的d o s 各版本后，进而进入了图形 界面的w i n d o w s 时代，同时数据库系统也经历了d b a s e 系列，f o xb a s e 和f o x p r o 时代， 而进入了关系型数据库管理系统时代。在这一飞速发展时期，由于图书馆各级领导的重 视与图书馆各部门的努力，我国图书馆自动化建设一直紧跟着时代发展的步伐。到目前 为至，各种图书馆的集成管理系统像雨后春笋般发展起来。在这批系统中比较有代表性 的有：北京丹诚软件有限责任公司的丹诚图书馆集成管理系统，深圳图书馆的i l a s 等一 批优秀的图书馆集成管理系统。这批集成管理系统都己基本上实现了图书馆各部门的自 动化，并都采用了比较标准的关系型数据库系统【6 】。 以上这些基于联机事务处理( o l t p ) 的图书馆管理系统的建立，己经使我国的图书馆 基本上完成了信息化建设的基础建设阶段和系统优化阶段，下一步，就应该进入利用联 机事务处理系统所积累的数据挖掘知识的实现价值阶段。 1 3 本文主要工作 本文主要研究聚类和关联规则在图书馆系统中的应用。主要研究工作如下： 一2 一 大连理工大学硕士学位论文 ( 1 ) 分析图书馆系统中的历史数据，对数据进行预处理。 以现有图书馆管理系统为研究对象，了解系统的组成，分析系统的业务数据，抽取 用于数据挖掘的数据集，并对数据集进行预处理。主要工作包括填充空值记录、建立表 间联系、生成统计表等。 ( 2 ) 聚类技术研究，实现k m e a n s 算法在读者聚类中的挖掘应用。 查阅资料，研究数据挖掘中的聚类技术，了解当前常用的聚类分析算法。选择 k - m e a l l s 算法作为主要研究对象，在j a v a 环境下实现该算法。采用国际通用标准数据集 进行算法实验，检查算法的正确性和算法执行效率。在图书馆系统中，选择相关数据做 应用研究，并对产生的挖掘结果进行分析。 ( 3 ) 关联规则挖掘研究，实现改进的a p r i o r i 算法在图书关联性中的挖掘应用。 对关联规则挖掘的理论进行研究，选择a p f i o r i t l 】算法作为主要研究对象【7 1 。在研究 的基础上，提出了改进的a p r i o r i 算法，提高了产生频繁集的效率。在i a v a 环境下实现 了两个算法。利用图书管理系统中的图书借阅数据，进行了关联规则的挖掘实验，分析 了两个算法的优劣。验证了算法的正确性。并对关联规则产生的结果进行了解释。 ( 4 ) 数据挖掘技术在图书馆系统中的应用模型的设计与实现。 提出了在图书馆环境下的数据挖掘应用模型。系统采用基于j 2 e e 的w e b 开发环境， 结合h t m l 、j s p 、j a v a b e a n s 、s e r v l e t 、j a v a s c r i p t 以及数据库技术等，完成了主要功能。 包括数据处理、数据挖掘以及挖掘结果应用。其中数据挖掘模块中实现了聚类挖掘、关 联规则挖掘，并实现了挖掘结果的可视化表示。 一3 一 数据挖掘技术在图书管理系统中的应用研究 2 相关理论及技术基础 2 1数据挖掘的介绍 ( 1 ) 数据挖掘的定义 随着数据库技术的不断发展及数据库管理系统的广泛应用，数据库中存储的数据量 急剧增大，在大量的数据背后隐藏着许多重要的信息，如果能把这些信息从数据库中抽 取出来，将为管理部门创造很多潜在的利润，而这种从海量数据库中挖掘信息的技术， 就称之为数据挖掘。 数据挖掘( d a t am i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的、随机的数据 中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程【8 】。 还有很多和这一术语相近似的术语，如从数据库中发现知识( k d d ) 、数据分析、数据融 合( d a t af u s i o n ) 以及决策支持等。人们把原始数据看作是形成知识的源泉，就像从矿石 中采矿一样。原始数据可以是结构化的，如关系数据库中的数据，也可以是半结构化的， 如文本、图形、图像数据，甚至是分布在网络上的异构型数据。发现知识的方法可以是 数学的，也可以是非数学的：可以是演绎的，也可以是归纳的。发现了的知识可以被用于 信息管理、查询优化、决策支持、过程控制等，还可以用于数据自身的维护。因此，数 据挖掘是一门广义的交叉学科，它汇聚了不同领域的研究者，尤其是数据库、人工智能、 数理统计、可视化、并行计算等方面的学者和工程技术人员【9 】。 特别要指出的是，数据挖掘技术从一开始就是面向应用的。它不仅是面向特定数据 库的简单检索查询调用，而且要对这些数据进行微观、中观乃至宏观的统计、分析、综 合和推理，以指导实际问题的求解，企图发现事件间的相互关联，甚至利用已有的数据 对未来的活动进行预测。例如加拿大b c 省电话公司要求加拿大s i m o nf r a s e r 大学k d d 研究组，根据其拥有十多年的客户数据，总结、分析并提出新的电话收费和管理办法， 制定既有利于公司又有利于客户的优惠政策【l o 】。这样一来，就把人们对数据的应用，从 低层次的末端查询操作，提高到为各级经营决策者提供决策支持。这种需求驱动力，比 数据库查询更为强大。同时需要指出的是，这里所说的知识发现，不是要求发现放之四 海而皆准的真理，也不是要去发现崭新的自然科学定理和纯数学公式，更不是什么机器 定理证明。所有发现的知识都是相对的，是有特定前提和约束条件、面向特定领域的， 同时还要能够易于被用户理解，最好能用自然语言表达发现结果。因此d m k d 的研究 成果是很讲求实际的。 从数据库中发现知识( k d d ) - - 词首次出现在1 9 8 9 年举行的第十一届国际联合人工 一4 一 大连理工大学硕士学位论文 智能学术会议上。到目前为止，由美国人工智能协会主办的k d d 国际研讨会已经召开 了8 次，规模由原来的专题讨论会发展到国际学术大会，研究重点也逐渐从发现方法转 向系统应用，注重多种发现策略和技术的集成，以及多种学科之间的相互渗透。1 9 9 9 年，亚太地区在北京召开的第三届p a k d d 会议收到1 5 8 篇论文，空前热烈。i e e e 的 k n o w l e d g ea n dd a t ae n g i n e e r i n g 会刊率先在1 9 9 3 年出版了k d d 技术专刊。并行计算、 计算机网络和信息工程等其他领域的国际学会、学刊也把数据挖掘和知识发现列为专题 和专刊讨论，甚至到了脍炙人口的程度【l l 】。 ( 2 ) 国内外研究概况 与国外相比，国内对d m k d 的研究稍晚，没有形成整体力量。1 9 9 3 年国家自然科 学基金首次支持我们对该领域的研究项目。目前，国内的许多科研单位和高等院校竟相 开展知识发现的基础理论及其应用研究，这些单位包括清华大学、中科院计算技术研究 所、空军第三研究所、海军装备论证中心等【1 2 】。其中，北京系统工程研究所对模糊方法 在知识发现中的应用进行了较深入的研究，北京大学也在开展对数据立方体代数的研 究，华中理工大学、复旦大学、浙江大学、中国科技大学、中科院数学研究所、吉林大 学等单位开展了对关联规则开采算法的优化和改造：南京大学、四川联合大学和上海交通 大学等单位探讨、研究了非结构化数据的知识发现以及w e b 数据挖掘。 当前，d m k d 研究正方兴未艾，预计在2 1 世纪还会形成更大的高潮，研究焦点可 能会集中到几个方面：研究专门用于知识发现的数据挖掘语言，也许会像s q l 语言一样 走向形式化和标准化：寻求数据挖掘过程中的可视化方法，使得知识发现的过程能够被用 户理解，也便于在知识发现过程中的人机交互：研究在网络环境下的数据挖掘技术，特别 是在i n t e m e t 上建立d m k d 服务器，与数据库服务器配合，实现数据挖掘：加强对各种 非结构化数据的挖掘，如文本数据、图形图像数据、多媒体数据。但是，无论怎样，需 求牵引，市场驱动是永恒的，d m k d 将首先满足信息时代用户的急需，基于d m k d 的 决策支持软件工具产品将会问世【1 3 】。 2 2 数据挖掘研究内容和本质 随着d m k d 研究逐步走向深入，数据挖掘和知识发现的研究已经形成了三根强大 的技术支柱：数据库、人工智能和数理统计。因此，k d d 大会程序委员会曾经由这三个 学科的权威人物同时来任主席。目前d m k d 的主要研究内容包括基础理论、发现算法、 数据仓库、可视化技术、定性定量互换模型、知识表示方法、发现知识的维护和再利用、 半结构化和非结构化数据中的知识发现以及网上数据挖掘等。数据挖掘所发现的知识最 常见的有以下五类： 一5 一 数据挖掘技术在图书管理系统中的应用研究 ( 1 ) 广义知识 广义知识指类别特征的概括性描述知识 1 4 】。根据数据的微观特性发现其表征的、带 有普遍性的、较高层次概念的、中观和宏观的知识，反映同类事物共同性质，是对数据 的概括、精炼和抽象。广义知识的发现方法和实现技术有很多，如数据立方体、面向属 性的归约等。数据立方体还有其他一些别名，如“多维数据库 、“实现视图 、“o l a p 等。该方法的基本思想是实现某些常用的代价较高的聚集函数的计算，诸如计数、求和、 平均、最大值等，并将这些实现视图储存在多维数据库中。既然很多聚集函数需经常重 复计算，那么在多维数据立方体中存放预先计算好的结果将能保证快速响应，并可灵活 地提供不同角度和不同抽象层次上的数据视图。另一种广义知识发现方法是加拿大 s i m o n f r a s e r 大学提出的面向属性的归约方法。这种方法以类s q l 语言表示数据挖掘查 询，收集数据库中的相关数据集，然后在相关数据集上应用一系列数据推广技术进行数 据推广，包括属性删除、概念树提升、属性阈值控制、计数及其他聚集函数传播等。 ( 2 ) 关联知识 它反映一个事件和其他事件之间依赖或关联的知识。如果两项或多项属性之间存在 关联，那么其中一项的属性值就可以依据其他属性值进行预测。最为著名的关联规则发 现方法是r a g r a w a l 提出的a p r i o r i 算法【1 5 】。关联规则的发现可分为两步。第一步是迭 代识别所有的频繁项目集，要求频繁项目集的支持率不低于用户设定的最低值：第二步是 从频繁项目集中构造可信度不低于用户设定的最低值的规则。识别或发现所有频繁项目 集是关联规则发现算法的核心，也是计算量最大的部分。 ( 3 ) 分类知识 它反映同类事物共同性质的特征型知识和不同事物之间的差异型特征知识。最为典 型的分类方法是基于决策树的分类方法。它是从实例集中构造决策树，是一种有指导的 学习方法。该方法先根据训练子集( 又称为窗口) 形成决策树【l6 1 。如果该树不能对所有对 象给出正确的分类，那么选择一些例外加入到窗口中，重复该过程一直到形成正确的决 策集。最终结果是一棵树，其叶结点是类名，中间结点是带有分枝的属性，该分枝对应 该属性的某一可能值。最为典型的决策树学习系统是i d 3 ，它采用自顶向下不回溯策略， 能保证找到一个简单的树。算法c 4 5 和c 5 o 都是i d 3 的扩展，它们将分类领域从类别 属性扩展到数值型属性。 数据分类还有统计、粗糙集( r o u g h s e t ) 等方法。线性回归和线性辨别分析是典型的 统计模型。为降低决策树生成代价，人们还提出了一种区间分类器。 ( 4 ) 预测型知识 一6 一 大连理工大学硕士学位论文 它根据时间序列型数据，由历史的和当前的数据去推测未来的数据，也可以认为是 以时间为关键属性的关联知识。目前，时间序列预测方法有经典的统计方法、神经网络 和机器学习等。1 9 6 8 年b o x 和j e n k i n s 提出了一套比较完善的时间序列建模理论和分析 方法【1 7 】，这些经典的数学方法通过建立随机模型，如自回归模型、自回归滑动平均模型、 求和自回归滑动平均模型和季节调整模型等，进行时间序列的预测。由于大量的时间序 列是非平稳的，其特征参数和数据分布随着时间的推移而发生变化。因此，仅仅通过对 某段历史数据的训练，建立单一的神经网络预测模型，还无法完成准确的预测任务。为 此，人们提出了基于统计学和基于精确性的再训练方法，当发现现存预测模型不再适用 于当前数据时，对模型重新训练，获得新的权重参数，建立新的模型。也有许多系统借 助并行算法的计算优势进行时间序列预测。 ( 5 ) 偏差型知识 此外，还可以发现其他类型的知识，如偏差型知识( d e v i a t i o n ) ，它是对差异和极端 特例的描述，揭示事物偏离常规的异常现象，如标准类外的特例，数据聚类外的离群值 等。所有这些知识都可以在不同的概念层次上被发现，并随着概念层次的提升，从微观 到中观、到宏观，以满足不同用户不同层次决策的需要。 2 3 数据挖掘的功能 数据挖掘通过预测未来趋势及行为，做出前摄的、基于知识的决策。数据挖掘的目 标是从数据库中发现隐含的、有意义的知识，主要有以下五类功能。 ( 1 ) 自动预测趋势和行为 数据挖掘自动在大型数据库中寻找预测性信息，以往需要进行大量手工分析的问题 如今可以迅速直接由数据本身得出结论【l6 1 。一个典型的例子是市场预测问题，数据挖掘 使用过去有关促销的数据来寻找未来投资中回报最大的用户，其它可预测的问题包括预 报破产以及认定对指定事件最可能做出反应的群体。 ( 2 ) 关联分析 数据关联是数据库中存在的一类重要的可被发现的知识。若两个或多个变量的取值 之间存在某种规律性，就称为关联。关联可分为简单关联、时序关联、因果关联。关联 分析的目的是找出数据库中隐藏的关联网。有时并不知道数据库中数据的关联函数，即 使知道也是不确定的，因此关联分析生成的规则带有可信度。 ( 3 ) 聚类 数据库中的记录可被化分为一系列有意义的子集，即聚类。聚类增强了人们对客观 一7 一 数据挖掘技术在图书管理系统中的应用研究 现实的认识，是概念描述和偏差分析的先决条件。聚类技术主要包括传统的模式识别方 法和数学分类学。8 0 年代初，m c h a l s k i 提出了概念聚类技术及其要点是，在划分对象时 不仅考虑对象之间的距离，还要求划分出的类具有某种内涵描述，从而避免了传统技术 的某些片面性【17 1 。 ( 4 ) 概念描述 概念描述就是对某类对象的内涵进行描述，并概括这类对象的有关特征。概念描述 分为特征性描述和区别性描述，前者描述某类对象的共同特征，后者描述不同类对象之 间的区别。生成一个类的特征性描述只涉及该类对象中所有对象的共性。生成区别性描 述的方法很多，如决策树方法、遗传算法等。 ( 5 ) 偏差检测 数据库中的数据常有一些异常记录，从数据库中检测这些偏差很有意义。偏差包括 很多潜在的知识，如分类中的反常实例、不满足规则的特例、观测结果与模型预测值的 偏差、量值随时间的变化等。偏差检测的基本方法是，寻找观测结果与参照值之间有意 义的差别。 2 4 聚类的介绍 ( 1 ) 聚类的定义 聚类分析( c l u s t e ra n a l y s i s ) 是数据挖掘领域最常用的技术之一【1 8 】。所谓聚类就是 将物理或抽象对象的集合组成为由类似的对象组成的多个类或簇的过程。由聚类生成的 簇是一组数据对象的集合，同一簇中的对象尽可能相似。而不同簇中的对象尽可能相异。 通过聚类，人们可以发现数据分布的一些特征。 聚类分析己被广泛应用于许多研究领域，包括数据挖掘、图像分割、模式识别等研 究领域。如在商务上，聚类能帮助市场分析人员从客户基本信息中发现不同的客户群， 并且用购买模式来刻画不同的客户群特征。在生物学上，聚类能推导植物和动物的分类， 对基因分类。聚类分析还可以应用在其他挖掘算法的预处理步骤，如先对数据进行聚类， 再在得到的聚类结果上进行其他的研究和处理。 ( 2 ) 聚类分析的主要方法 聚类分析已经成为数据挖掘领域非常活跃的研究课题。研究人员已经提出了许多聚 类算法：比较著名的有k m e a n s 、p a m 、c l a r a n s 、b i r c h 、c u r e 、d b s c a n 、o p t i c s 、 c l i q u ec a b o s f v 等算法。 算法的选择取决于数据的类型和聚类的目的。总体而言，聚类算法可以归纳为以下 几种： 一8 一 大连理工大学硕士学位论文 分割聚类方法( p a r t i t i o n i n gc l u s t e r i n gm e t h o d ) 分割聚类算法是基于原型的聚类方法，是从数据集中随机选择几个对象作为原始的 划分，然后将其他对象分别按照最相似特性划分到不同的簇中去。分割聚类算法需要通 过反复的迭代对产生的类进行调整，以达到最优。 主要包括两大类计算方法： ( a ) k m e a n s 算法。其主要特点是在完成每一次的对象划分后，以每个类的所有对 象的平均值作为该簇新的中心。直到所有的簇不再发生变化为止。 k - m e d o i d 算法。在这个算法中，每个簇的中心以最接近聚类中心的一个对象来 表示。比较著名的k - m e d o i d 算法有p a m 、c l a r a n s 等。 在聚类形状为球形、大小和密度相似的情况下，分割聚类算法能够形成较好的聚类 效果。 层次聚类方法( h i e r a r c h i c a lc l u s t e r i n gm e t h o d ) 层次聚类方法对给定数据对象集合进行层次的分解。根据层次的分解的形成方式， 又可以分为凝聚的或分裂的层次方法。凝聚方法也称为自底向上的方法，一开始将每个 对象作为单独的一个组，然后相继地合并相近的对象或组，直到所有的组合并为一个， 或者达到一个终止条件。分裂方法也称为自顶向下的方法，一开始将所有对象置于一个 簇中。在迭代的每一步中，一个簇被分裂为更小的簇直到最终每个对象在单独的一个簇 中，或者达到一个终止条件。 层次聚类方法与分割聚类方法不同之处在于：分割聚类方法需要采用迭代控制策 略，使聚类结果达到最优。而层次聚类方法使按照一定的相似性判断标准合并最相似的 部分，或分割最不相似的部分。比较常用的算法有b i r c h 、c u r e 、r o c k 等方法。 基于密度的聚类方法( d e n s i t y - b a s e dc l u s t e r i n gm e t h o d ) 基于密度的聚类方法是以局部数据特征作为聚类的判断标准，根据区域内数据对象 的密集和稀疏程度进行聚类。基于密度的聚类算法适用于任意形状的聚类。如d b s c a n 、 o p t i c s 等算法。 基于网格的聚类方法( g r i d b a s e dc l u s t e r i n gm e t h o d ) 基于网格的方法把对象空间量化为有限数目的单元，形成一个网格结构，所有的聚 类操作都在网格结构( 即量化空间) 上进行。这种方法的主要优点是它的处理速度很快， 其处理时间独立于数据对象的数目，只与量化空间中每一维的单元数目有关。s t i n g 算 法是基于网格方法的一个典型例子。c l i q u e 算法既是基于网格的，又是基于密度的。 这种算法适用于处理高维数据和大数据集。 基于模型的聚类方法( m o d e l b a s e dc l u s t e r i n gm e t h o d ) 一9 一 数据挖掘技术在图书管理系统中的应用研究 基于模型的方法为每个簇假定了一个模型，寻找数据对此模型的最佳拟合。一个基 于模型的算法可能通过构建反映数据点空间分布的密度函数来定位聚类，它也可能基于 标准的统计数字自动决定聚类的数目，考虑“噪声”数据和孤立点，从而产生健壮的聚 类方法。 ( 3 ) k m e a n s 算法基本思想 k - m e a n s 算法是以平均值作为类中心的一种分割聚类方法【1 9 】。假设对n 个对象进行 聚类，其结果要求产生k 个类，算法的基本过程描述如下： 首先随机地选择k 个对象，每个对象作为一个类的中心，分别代表将分成的k 个类； 根据“距离中心最近的原则，寻找与各个对象最为相似的类，将其他对象划 分到各个相应的类中； 在完成对象的分配之后，针对每一个类，计算机其所有对象的平均值，作为该 类的新的中心j 根据“距离中心最近“的原则，重新进行所有对象的划分； 返回步骤3 ，直至所有产生的类没有变化为止。 1坍 假设给定肛 芒胁t 胁o 柚，类中心计算定义为：舻二罗t ， m 石 假设给定需要进行聚类的元组：f 2 ，4 ，1 0 ，1 2 ，3 ，2 0 ，3 0 ，1 1 ，2 5 ；假设k = - 2 ， 利用前两个元组作为初始类中心，即m i _ 2 ，m z = 4 。利用欧几里德距离计算与类中心的距离。 按照上述算法过程，可得到如表2 1 所示。 表2 1 聚类结果 t a b 2 1 c l u s t e r i n gr e s u l t s 该算法的时间复杂度是o ( t k n ) ，其中t 是迭代的次数，k 为聚类个数，n 为数据对象 个数。该算法容易受到异常值的影响。 2 5 关联规则的介绍 ( 1 ) 关联规则的基本概念 一1 0 大连理工大学硕士学位论文 关联规则挖掘是发现大量数据中项集之间有趣的关联或相关联系。随着大量数据的 收集和存储，人们希望从大量的数据中发现感兴趣的数据关联关系，从而帮助管理者进 行决策的制订。关联规则发现的最初形式是零售商的货篮分析，即通过发现顾客放入其 货篮的不同商品间的联系，分析顾客的购买习惯。在数据挖掘的研究中，关联规则研究 开展得最广泛，应用也较早。 关联规则的定义：设仁 厶厶，口是所有项的集合，其中i 。( k = l ，2 ，m ) 称为项， 项的集合称为项集，包含k 个项的项集称为k 项集。一个事务r 是一个项集它是，的一 个子集，每个事务均与一个惟一标识符t i d 相联系。不同的事务构成了事务集d ，它构 成了关联规则发现的事务数据库。如果项集x t ，则称事务丁支持( s u p p o r t ) 项集疋 也称事务r 包含项集兄关联规则是这样一种形式的蕴涵：x y ，其中彳c 1 ，y c l 且 x ny = 1 2 j 。 一般用4 个参数来描述关联规则的属性。它们是支持度( s u p p o r t ) 、可信度 ( c o n f i d e n c e ) 、期望可信度( e x p e c t e dc o n f i d e n c e ) 和作用度( l i f t ) 。其中支持度和 可信度能够比较直观地描述关联规则的性质。 支持度 设事务集d 中有s 的事务同时支持项集x 和y ，s 称为关联规则xjy 的支持度。 支持度描述了x 和】，两个项集的并集x uy 在所有事务中出现的频率。例如1 0 0 0 顾客 中，有1 0 0 个顾客同时购买了果酱和面包，则果酱j 面包的支持度为1 0 。 s u p ( x ) = 幽铲 s u p ( x 耻删x 旧= 幽塑产 ( 2 1 ) ( 2 2 ) 可信度( c o n f i d e n c e ) 设事务集d 中支持项集j 的事务中，有c 的事务同时也支持项集y ，c 称为关联 x jy 的可信度。即在出现了项集x 的事务r 中，项集】，也同时出现的概率。如果酱? 面包的可信度为6 0 ，表示购买果酱的人，有7 0 也同时会购买面包。 conf(x=】，、l：ittdand(xt)y)c_ti：sup(xw y ) ( 2 3 ) f rt d a n d x 丁) is u p ( x ) 数据挖掘技术在图书管理系统中的应用研究 关联规则的选择主要基于这两个参数的值，从关联规则定义中可以看出，支持度度 量关联规则在事务数据库中出现的概率，可信度度量关联规则的强度。有些关联规则的 可信度虽然很高，但是支持度很低，说明该规则实用的价值非常小，因此也不重要。在 事务数据库中，任意的两个项集之间都存在关联规则，若不考虑支持度和可信度，那么 在事务数据库中就存在无穷多的关联规则。而实际应用中，人们只会对满足一定支持度 和可信度的关联规则感兴趣，因此在进行关联规则发现时，需要确定两个阈值：最小支 持度( m i ns u p ) 和最小可信度( m i nc o n f ) 。同时满足最小支持度和最小可信度的规则 称作强规则。 ( 2 ) 关联规则的发现过程 货篮分析是关联规则的一种挖掘形式，实际的关联规则根据不同的标准也存在不同 的类别。如单维关联规则和多维关联规则，比如前面例子果酱? 面包只涉及一个属性， 就是单维关联规则；性别= “女j 职业= “秘书”就是属于多维规则。根据层次关 系又可分为单层的关联规则和多层关联规则。不论是属于哪类关联规则，关联规则的发 现过程一般要经过以下步骤： 数据准备 确定最小支持度和最小可信度 关联规则发现 关联规则的解释 最小支持度和最小可信度的选择会直接影响到关联规则的挖掘，过大可能会漏掉有 价值的规则，过小又可能会造成大量的无用规则产生、影响挖掘的效率。对关联规则的 合理解释也是充分利用关联规则价值的关键所在。在关联规则的研究中，最著名的算法 是a g r a w a l 提出的a p r i o r i 算法，除此以外还有f p - g r o w t h 方法、针对加权关联规则发现 的m i n w a l 和d w a r 算法等【2 0 】。 ( 3 ) a p r i o r i 算法的基本思想 a p r i o r i 是由r a k e s ha g r a w a l 和r n a m a k r i s h n a ns r i k a n t 在19 9 4 年提出的关联规则的 经典算法【3 】，它是所有关联规则挖掘算法的核心。a p r i o r i 算法将关联规则挖掘分解为两 个子问题： 求出事务数据库d 中满足最小支持度m i n s u p 的所有频繁集； 利用频繁集生成满足最小可信度m i n c o n f 的所有关联规则； 寻找频繁集是关联规则发现的核心问题。包含k 个项的项集称为k 项集。若项集满 足最小支持度，则称该项集为频繁项集( f r e q e n ti t e m s e t ) ，简称频繁集。频繁k 项集通 常记作l i 。 一1 2 大连理工大学硕士学位论文 具体做法是：第一步从候选1 项集c l 中找出频繁1 项集l l ，然后利用l k - l 连接产 生候选c k ，并根据a p r i o r i 的性质删除那些具有非频繁子集的候选项集。扫描事务数据 库，统计候选项集的支持计数，与最小支持计数相比，形成频繁项集l k 。直至找到所有 频繁项集。 从a p r i o r i 算法的步骤中可以发现，在产生候选项集时，可能会产生大量的候选集， 当长度为l 的频繁集有1 0 0 0 0 个时，长度为2 的候选集数将会超过1 0 0 0 万。同时由于 需要计算项集的支持度，会反复扫描事务数据库d ，增加了系统的i o 开销。因此出现 了许多改进的方法，如基于散列的优化方法d h p 算法、基于减少事务个数的方法 a p r i o r i t i d 方法、基于数据库分割的方法等。 2 6j 2 e e 简介 j 2 e e 是基于组件的，具有与平台无