（管理科学与工程专业论文）关联型数据挖掘技术和移动代理在数字图书馆中的应用.pdf

关联型数据挖掘技术和移动代理在数字剧书馆中的应用 关联型数据挖掘技术和移动代理在数字图书馆中的应用 摘要 随着数字化技术和网络化技术的发展，信息资源正以每年1 0 倍的 速度增长着，这就向数字图书馆提出了巨大的挑战。如何能实时地分 析不断增长的海量数据，如何能更好地为读者提供个性化服务，已成 为数字图书馆界所要解决的追在眉睫的问题。针对数字图书馆中信息 的分布性和海量性的特点，本文将数据挖掘技术和移动代理相结合， 重点运用了关联型数据挖掘技术，对数字图书馆中的海量信息进行挖 掘，经试验证明，本系统能有效应对数字图书馆所面临的挑战。 本文首先分析了网络环境下数字图书馆的建设要求，并对现有数 字图书馆的基本框架进行研究，进而指出了在数字图书馆中引入数据 挖掘和移动代理的迫切性和可行性。再以面向对象的分析设计方法为 基础，针对数字图书馆的特点，创建了嵌入式功能模块，结合相关的 系统框架，提出了一个新的数字图书馆系统框架，并针对相关数据的 特点，实现了一种改进的关联型数据挖掘算法。经试验证明，该系统 不仅可以对本地数字图书馆资源进行有效的挖掘，还可以利用移动代 理，对异地数字图书馆中的海量数据进行挖掘分析，从而更好地为读 者提供个性化的服务。本文为建立新型的数字图书馆系统提供了新的 思路。 关键词：关联规则、数据挖掘、移动代理、数字图书馆 顺f ”学位论文关联型数据挖掘技术和移动代理存数宇图书馆中的应川 t h ea p p l i c a t i o no fa s s o c i a t i o nd a t am i n i n ga n dm o b i l e a g e n t i nd i g i t a ll i b r a r y a b s t r a c t w i t ht h e d e v e l o p m e n t o f d i g i t a lt e c h n o l o g y a n d i n t e r n e t ，t h e i n f o r m a t i o ni s g r o w i n gv e r yf a s t ，a n di t b e c o m e sag r e a t c h a l l e n g et o d i g i t a ll i b r a r y h o wc a r ld i g i t a ll i b r a r yd e a lw i t hs om u c hi n f o r m a t i o n ， h o wc a ni to f f e rb e t t e rs e r v i c e st ot h er e a d e r s ? d u et om o b i l ea g e n t s i n t e l l i g e n c e ，s e l f - d e t e r m i n a t i o n ，a n dt h ee x c e l l e n c e so f d a t am i n i n g ，t h e y a r eg o o d t e c h n i q u e st os u p p o r t t h ei n f o r m a t i o ns e r v i c e so f d i g i t a ll i b r a r y t h i st h e s i sp o i n t so u tt h er e a s o n sf o ra p p l y i n gm o b i l e a g e n t a n dd a t a m i n i n gt h r o u g ha n a l y z i n gt h e d e m a n d so fb u i l d i n g d i g i t a ll i b r a r y i n n e t w o r ke n v i r o n m e n t ，a n di m p r o v e sa na l g o r i t h mo fa s s o c i a t i o nr u l e s d i r e c t e db yt h et h e o r yo f o b j e c t o r i e n t e da n a l y s i sm e t h o d ，an e wm o d e l o fm o b i l ea g e n ta n dd a t am i n i n gs y s t e mi s d e v e l o p e d t h i sn e w m o d e l c a n h e l pd i g i t a ll i b r a r y t om i n ei n f o r m a t i o na n d p r o v i d e b e t t e r i n f o r m a t i o ns e r v i c e st ot h er e a d e r s i no r d e rt of u r t h e rd i s c u s sh o wt o a p p l y t h em o b i l ea g e n ta n dd a t am i n i n gi nd i g i t a ll i b r a r y , t h i st h e s i sa l s o t h e o r e t i c a l l yd i s c u s s e sh o w t oc a r r yo u tt h i sm o d e l k e y w o r d s ：a s s o c i a t i o n r u l e s ，d a t am i n i n g ，m o b i l ea g e n t ， d i g i t a ll i b r a r y 硕l 。学位论文关联型数据挖掘技术和移动代理在数宁图鹳馆中的脚用 第1 章绪论 1 1论文的研究主题和意义 图书馆是人类社会重要的信息机构，它的发展深深的刻上了信息技术的烙 印。随着2 0 世纪9 0 年代数字化技术和网络化技术应用的深入，为了更好的适应 人们对信息的需求，数字图书馆应运而生并得到了空前的发展。当前，信息资源 以每年1 0 倍的数量级增长，形成了动态变化的海量数据。数字图书馆所要处理 和提供的信息变得更多、更新、更广、更复杂，然而，人们管理和处理这些数据 的能力却非常有限，造成了对组织决策有重要价值的信息与知识的匮乏。如何有 效地进行海量数据管理，是数字图书馆j 卜在面临的一个严峻挑战。 数据挖掘技术是互联网之后出现的又一项信息技术新热点，为人们战胜这一 挑战带来了新的机遇。它运用机器学习方法从大量不完全、有噪声、模糊、随机 数据中，发现隐含其中、不为人知、具有潜在价值的信息和知识。它不同于从数 据中查找相关事实的简单数据处理技术，而是从数据中发现有用的趋势和模式。 由于数字图书馆中数据多源性、分布性、动态性、海量性等特点，决定了数据挖 掘管理平台必定是一个网络协同计算平台，而移动代理技术则是数据管理平台的 核心。 现有数据挖掘算法主要是利用传统网络的计算模式，由于计算任务由客户端 来执行，客户端和服务器之间的网络流量非常大，计算效率非常低。同时，这种 计算模式要求客户端和服务器始终保持连接，降低了系统的灵活性与健壮性。为 此本文提出利用移动代理技术来构建松散型协同数据挖掘模块。移动代理作为一 个独立运行的计算机程序，具有自主性、移动性、协作性、安全性、智能性等特 性。移动代理计算模式能有效地降低分布计算中的网络负载，提高通信效率，支 持异步及自主交互，支持非连接互操作，可动态自适应，具有一定的健壮性和容 错能力。 通过对数据挖掘以及移动代理的研究，本文在具体分析现有数字图书馆的框 架的基础上，针对数字图书馆的特点，将基于移动代理的数据挖掘模块嵌入数字 图书馆的框架中，并实现了其主要的功能，并重点研究了关联型数据挖掘技术， 第1 页 关联型数据挖掘技术和移动代理在数字图书馆中的府用 提出了相应的改进算法。希望本文的研究可以为数字图书馆的建设带来新的思 路，为数字图书馆的信息管理，为读者提供个性化服务提供一定的帮助。 1 2 国内外研究现状 数字图书馆主要是为了解决信息资源的有效利用而产生的。其关键的技术 是解决如何从大量的、分布的信息仓储中查找所需要的相关信息并向用户提供最 优的显示。其核心是形成数字图书馆的基础体系结构，有效的操作大规模、分布 的数字化信息。 在当前国内外的数字图书馆的研究中，主要有i n t e r s p a c e 、i n f o b u s 、u m d l 、 n c s t r l 等四种最具代表性的数字图书馆的框架。这些框架主要是运用了静态代 理技术，还没有到达利用于数据挖掘技术和移动代理相结合对数字图书馆进行数 据挖掘的阶段。在国内外的公开技术文献中也没有报道。 1 3 创新点、研究方法和论文结构 本文的主要创新点如下： 1 ) 通过研究国内外数字图书馆的发展现状，分析总结了当前数字图书馆界具 有代表性的基本框架的优缺点，指出其所存在的问题，提出了相应改进的 方案。 2 ) 在分析了数字图书馆的现存主要框架的基础上，将数据挖掘技术和移动代 理紧密结合，提出了在数字图书馆框架中，嵌入基于移动代理的数据挖掘 模块，提出自己的数字图书馆的框架，并编程实现了嵌入模块的主要功能。 3 ) 针对数字图书馆中海量数据存储运算的特点，提出了一种新的改进的关联 规则数据挖掘算法，并将其运用于数字图书馆中的文本和目录挖掘中。通 过数据试验分析表明，在保证准确性的同时，改进算法比原有的算法的效 率大幅度提高。 本文采用的研究方法主要是理沦研究与试验研究相结合。在文献阅读的基础 第2 页 关联型数据挖掘技术和移动代理和数字图书馆中的心用 l ，研究数字图书馆的模型结构，提出有关的嵌入模块，并对功能模块进行程序 编写，最后结合真实的数据进行试验分析。 其中，本文牛要框架的设计，主要是参考浙江省自然科学基金项日：基_ 丁 协同知识发现技术的数据流管理和基于移动代理的网络海量数据挖捌技术 中笔者所参与设计的部分。 本文的论文结构共分六章。 第一章是绪论部分。第二章主要介绍数字图书馆和数据挖掘的相关基本知 识，探讨了数据挖掘在数字图书馆中的应用。第三章对移动代理的基本理论进行 介绍，说明在数字图书馆中引入移动代理的必要性，在原有数字图书馆框架的基 础i 二，创建了一个嵌入式的功能模块，提出了j 个新的数字图书馆模型。第四章 介绍了基于移动代理的数据挖掘嵌入式模块m o b i l ed m 的设计与实现，对移动 模块进行了详细的说明，并利用真实的数据对系统进行了检测。第五章详细介 绍了埽中针对海量数据而设计的改进关联规则算法，并将其应用于文本挖掘中。 第六章是总结和展望。 第3 页 坝1 学似埝文关联型数据挖掘技术和移动代理杠数字网书馆中的应用 第2 章数字图书馆与数据挖掘 2 1 数字图书馆概述 2 1 1 数字图书馆的定义 数字图书馆( d i g i t a ll i b r a r y ，简称d l ) 是随着2 0 世纪9 0 年代数字化技术 和网络化技术的高速发展由“电子图书馆”的概念不断演变过来的。其研究内容 包括环境规划和地理信息系统、海量的空f 1 j 和地理信息的集成和检索、科技文献 的联邦化仓储、各类信息服务的互操作机制、智能代理框架等 l i 0 4 。 中国国家图书馆对d l 的定义是【中数h ：“数字图书馆是采用现代高新技术 所支持的数字信息资源系统，是下一代因特网上信息资源的管理模式，它将从根 本上改变目前因特网上信息分散不便使用的现状。数字图书馆是没有时空限制 的、便于使用的、超大规模的知谚 中心。” 该定义指出了数字图书馆的核心和本质是充分的利用现代信息技术，以计算 机网络为基础平台，构建一一个有利于产生新知识( 知识创新) 的资源、工具及合 作环境，这种作为环境的数字图书馆不仅仅局限于网络数字信息资源的开发利 用，更是一个促进信息获取、传递、交流的知识网络。 2 1 2 数字图书馆的基本特征 数字图书馆是一个开放式的硬件和软件的集成平台，通过对技术和产品的集 成，把当前大量的各种文献载体数字化，将它们组织起来在网上服务。从理论上 讲，数字图书馆是一种引入管理和应用数字化技术的方法。其基本的结构如图 2 1 所示。美国研究图书馆协会( a r l ) 概括了数字图书馆的基本特征 a r l h l ： ( 1 )数字图书馆不是一个单独的实体，不能独立的存在，是一个无限的 信息空间，互联空间。 信息存储数字化，将印刷型文献转换成数字信号，这是数字图书馆 的基本特征。 第4 页 顺1 学位论文关联型数据挖掘技术和移动代理柞- 数字国书馆叶1 的府用 ( 3 )刚络化的信息组织形式，用户可以检索道信息资源而不必知道所检 索的信息存储在何处。 ( 4 )以检索为目标，从提供信息入口转向选择最相关的信息，从以信息 为中心转向以知识为中心。 ( 5 )以用，1 为中心的服务模式。 ( 6 )图书馆馆员角色由图书管理员向知识导航员转变，馆员应成为用户 与知识之问的桥梁。 图2 1 数字图书馆的基本结构图 2 1 3 数字图书馆的国内外研究现状 数字图书馆的构想最早可以追溯到1 9 4 5 年。经过多年的探索，美国在1 9 9 2 年制定“高性能计算与通信( h p c c ) ”国家攻关项目中，率先将发展数字图书馆 列入“国家级挑战”。1 9 9 4 年9 月，美国国家科学基金会( n s f ) 、国家宇航局 ( n a s a ) 和国防部研究署( a r p a ) 开始实施的“数字图书馆创始计划”( d i 百t a l l i b r a r yi n i t i a t i v e ) 。1 9 9 5 年秋，美国国会图书馆正式启动国家数字图书馆项目 ( n a t i o n a l d i g i t a l l i b r a r y p r o g r a m ) 。美国当前主要的数字图书馆项目有g 7 全球信 息社会项同，d l f 数字图书馆联盟、i b m 数字图书馆等项目。 第5 页 倾 学位论文 关联型数据挖掘技术和移动代理在数字图书馆中的应用 在欧洲，1 9 9 3 年英国不列颠图书馆宣布了通过数字化技术使用户最大限度 地利用其收藏文献的“2 0 0 0 年政策目标”；法国国家图书馆在致力于将收藏的 1 0 0 万册图b 数字化的同时，还参加了欧洲多国合作的项目“欧洲电子图书馆图 像服务”计划；1 9 9 6 年8 月，德图联邦内阁会议正式通过了德国1 9 9 6 2 0 0 0 信 息技术发展计划，中一1 1 , 内容是建立全球性数字图书馆和开展电子h 版业服务，其 目的是应用先进信息技术为全球数字图书馆服务。 在亚洲，1 9 9 5 年1 1 月，日本4 0 家主要掰闻机构和出版社发起成立“数字 图书馆研究会，只本通产省信息技术促进会与日本国立国会图书馆合作，下展 了国会图书馆关西馆工程，目标之一就是研制一套信息资源数字化处理系统，成 为日本最大的数字图书馆及亚洲地区的文献中心。 我国的数字图书馆理论研究于9 0 年代初开始，其中以文献资源的开发利用 为重点所建设的“金图”工程巾国图书馆信息网络( c h i n a l i b r a r y i n f o r m a t i o n n e t w o r k ) ，为我国数字图书馆的建设与发展奠定了基础 张0 2 。 1 9 9 6 年5 月国家图书馆提出了“中国试验型数字图书馆”项目，将1 0 0 万 页中文全文数据放在其网站上，到2 0 0 4 年4 月，已建有8 0 0 0 万页中文全文影像 数据资料及1 6 0 万条书目数据。1 9 9 8 年7 月2 0 日，国家图书馆向文化部提出申 请建议在国家立项实施：“中国数字图书馆工程”。由文化部倡议，国家图书馆牵 头，联合上海图书馆、南京图书馆、深圳图书馆等国内主要公共图书馆实旋建设 的试验示范项目“中国国家试验型数字图书馆计划”，于2 0 0 1 年5 月通过国家鉴 定 李0 3 。 2 0 0 0 年4 月我国成立了由文化部为召集单位、2 1 个部委参加的“中国数字 化图书馆工程建设联席会”，标志着中国数字图书馆工程正式启动。其目标为： 构建一个国家数字图书馆，集中国家图书馆和地方图书馆中有一定特色或典型示 范性的馆藏资源，通过遍布全国的数字通信网，向全国乃至全球提供示范性的数 字化服务。 第6 页 i i ；! i 。学位论文关联型数据挖掘技术和移动代理在数字幽书馆中的脚用 2 2 数据挖掘概述 2 2 1 数据挖掘的产生 随着计算机硬件和软件的飞速发展，尤其是数据库技术与应用的日益普及， 人们而临着快速扩张的数据海洋，如何有效利用这一丰富数据海洋的宝藏为人类 服务，业已成为广大信息技术二i ：作者的所重点关注的焦点之一。与只趋成熟的数 据管理技术与软件工具相比，人们所依赖的数据分析工具功能，却无法有效地为 决策者提供其决策支持所需要的相关知识，从而形成了一种独特的现象“十富的 数掘，贫乏的知识”。为有效解决这一问题，自- 十世纪8 0 年代开始，数据挖掘 技术逐步发展起来，数据挖掘技术的迅速发展，得益于目前全世界所拥有的巨大 数据资源以及对将这些数据资源转换为信息和知识资源的臣大需求，对信息和知 识的需求来自各行各业，从商业管理、生产控制、市场分析到工程设计、科学探 索等。数据挖掘可以视为是数据管理与分析技术的自然进化产物。下图2 2 展示 了数掘挖掘的一个演化过程。 数据收集与数据库创建 ( 6 0 年代或更早) 基础文件处理 数据库管理系统 ( 7 0 年代) 网络和关系数据库系统 数据建棋工具 索引和数据组织技术 查询语言和查询处理 用户界面与优化方法 在线事务处理 先进数据库系统 ( 8 0 年代中期至今) 先进数据模型( 扩展关系、 面向对象、对象关系) 面向应用( 空间、时间、多 媒体、知识库) 数据仓库和数据挖掘 ( 8 0 年代后期至今) 先进数据模型( 扩展关系、 面向对象、对象关系) 面向应用( 空间、时问、多 媒体、知识库) 新一代信息系统 ( 2 0 0 0 年以后) 图2 2 数据挖掘的演化过程 第7 页 硕 学位论文关联型数据挖掘技术和移动代理在数7 留书馆中的应用 2 2 2 数据挖掘的定义 数据挖掘( d a t am i n i n g ，简称d m ) ，简单地讲就是从大量数据巾挖掘或抽 取出知识，数据挖掘概念的定义描述有若干版本，以下给出个被普遍采用的定 义描述：数据挖掘，又称为数据库中知识发现( k n o w l e d g ed i s c o v e r yf r o m d a t a b a s e ，简称k d d ) ，它是一个从大量数据中抽取挖掘出未知的、有价值的模 式或规律等知识的复杂过程 c e 0 1 。 个典型的数据挖掘系统如图2 3 所示： 图2 3 一个典型数据挖摒系统 其中，数据库、数据仓库或者是其他的一些信息存储媒介为数据挖掘的工作 对象；服务器主要是响应数据挖掘引擎的请求，提取相应的数据；领域知识库主 要用来指导挖掘的过程，以及用来评价挖掘出来的候选模式；数据挖掘引擎是这 个系统的核心部分，一般由以下的模块组成：分类模块、关联规则模块、聚类分 析模块、时序模块和异常分析模块等；模式评价模块主要是根据一定的度量标准 来与数据挖掘模块交互，以使得数据挖掘向着用户感兴趣的方向进行；图形用户 界面主要是为了方便用户与数据挖掘系统的交互：由用户提出挖掘任务、指定重 第8 页 砸i 学位论文 关联型数据挖掘技术和移动代理在数宁刳书馆中的应用 要的挖掘参数以及山当前返回的结果指导进行更进一步的挖掘工作。 2 2 3 数据挖掘的挖掘过程 数据挖掘是极据对数据的分析，建立对数据特性以及数据之间关系描述模式 的过程。在这里数据是指一系列事实的集合( 例如数据库中的实例) ，而模式是 使用某秽浯言对数据集合的一个子集的描述。过程是在数据挖掘中包括的步骤， 如数扼的飘处理、模式搜索、知识表示以及知识评价等。比较具有代表性的数据 挖掘的令过程如卜图2 4 【j m 0 1 ： 图2 4 数据挖掘的挖掘过程 如图2 4 所示，整个知识发现( k d d ) 过程是由若干挖掘步骤组成，而数据挖 掘仅是其中的一个主要步骤。整个知识挖掘的主要步骤有： 数据清洗( d a t a c l e a n i n g ) ，其作用就是清除数据噪声和与挖掘主题明显 无关的数据； ，其作用就是将来自多数据源中的相关数 数掘转换( d a t a t r a n s f o r m a t i o n ) ，其作用就是将数据转换为易于进行数 据挖掘的数据存储形式； 第9 页 )n。砒 旷 瞻l 如起 ( 一 成到集合据组数据 硕l 学位论义关联型数据挖掘技术和移动代理n 擞字图书馆中的应用 数据挖掘( d a t am i n i n g ) ，它是知识挖掘的一个基本步骤，其作用就是利 用智能方法挖掘数据模式或规律知识； 模式评估( p a t t e r ne v a u a t o r ) ，其作用就是根据一定评估标准 ( i n t e r e s t i n gm e a s u r e s ) 从挖掘结果筛选出有意义的模式知识； 知识表示( k n o w l e d g ep r e s e n t a t i o n ) ，其作用就是利用可视化和知识表 达技术，向用户展示所挖掘出的相关知识。 2 2 4 关联型数据挖掘技术 数据挖掘有很多方法，包括关联、分类、聚类、决策树等方法。下面对关 联型数据挖掘算法进行详细介绍，并简单介绍其他的常用的4 种方法。 2 2 4 i 关联型算法的基本思想 关联规i j f l 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 年提出的 a i s 9 3 ，目的是希望在事务数 据库中发现各项目之间的关系。关联规则挖掘能发现大量数据中项集之间有趣的 关联或相关关系。从大量商务事务记录中发现有趣的关联关系，可以帮助许多决 策的指定，如分类设计、交叉购物和贱卖分析等。 关联规则挖掘的一个典型的例子是购物篮分析。该过程通过发现顾客放入其 购物篮中不同商品之间的联系，来分析顾客的购买习惯。通过了解哪些商品频繁 的被顾客同时购买，这种关联的发现可以帮助零售商制定营销的策略。例如，有 这样一条关联规则：购买了面包的顾客中有4 0 同时也购买牛奶。又如，购买汽 车轮胎和配件的顾客中9 8 都会要求相关的服务，等等。其直观的意义就是顾客 在购买一些商品的同时有多大的可能购买其他的商品。通过帮助零售商有选择的 经销和安排货物，这种信息可以引导消费。例如，将牛奶和面包尽可能的放近一 些，可以进一步刺激这些商品被一次性购买。 规则一般以条件逻辑进行表示，即“如果那么”的形式，另外也可 以用相似逻辑的形式表示。关联规则的本质含义就是从大量的历史数据中通过高 第1 0 页 顺l 学位论文 关联型数据挖掘技术和移动代理辅数宁图h 馆中的废 效的分析和抽墩算法发现记录属性值之间的统计规律性。 关联规则的应用主要包括顾客购物篮分析、目录没计、市场营销行为预测、 银行信誉分析、图书馆资料整理、工业机器故障预测等。 关联规则的挖掘问题可形式化描述如下： 定义2 1 设i = i i ，i 2 ，i 。j 是由m 个不同的项目组成的集合，给定 个事务数据库d ，其中的每个事务t 是t 中一组项目的集合，即t a i ，t 有唯 的标识符t i d 。一条关联规则就是形如x y 的蕴涵式，其中x e i ，y i ，x 厂、y = 巾。关联规则x y 成立的条件是：( 1 ) 具有支持度s ，即事务数据库d 中至少 有s 的事务包含x u y ；( 2 ) 具有置信度c ，即在事务数据库d 包含x 的事务中 至少有c 的事务同时也包含y 。关联规则的挖掘问题就是在事务数据库d 中找 出具有用户给定的最小支持度m i n s u p p p o r t 和最小置信度m i n c o n f i d e n c e 的关联 规则。 定义2 2 频繁项目集是指支持度不小于用户给定的最小支持度的项目的集 合。 挖掘关联规则可以分解为以下两个子问题： 1 ) 找出存在于事务数据库中的所有频繁项目集。 2 ) 利用频繁项目集生成关联规则。对于每个频繁项目集a ，若a a a ， a 巾，上ls u p p o r t ( a ) s u p p o r t ( a ) m i n c o n f i d e n c e ，贝ua = ，aa 。 第一个子问题的任务是迅速高效的找出d 中全部频繁项目集，是关联规则挖 掘的中心问题，是衡量关联挖掘算法的标准；第二个子问题相对比较容易，其生 成算法参见 r r 9 4 】。关联规则挖掘的基本模型如图2 5 ： 图2 5 关联规则挖掘的基本模型 第1 1 页 坝l 学位论支关联型数据挖掘技术和移动代理在数。，图书馆中的应用 其中d a t a 为数据集，a l g o r i t h m 1 为频繁项目集的搜索算法，a l g o r i t h m 2 为 关联规则的产生算法，r 为挖掘出的关联规则集合。用，1 通过指定m i n s u p p o r t 、 m i n c o n f i d e n c e 分别与算法a l g o r i t h m 一1 和a l g o r i t h m 一2 交互，并通过与r 的交盯 埘挖掘结果进行解释和评价。 自r a g r a w a l 提出关联规则挖掘问题并给出解决此问题最原始算法a i s 之 后，该问题得到了国际人工智能和数据库等领域学者的密切关注，提出了多种算 法。无论挖掘算法采用何种数据结构，其复杂程度、效率如何，都可以分为以f 几个步骤： 1 )预处理与挖掘任务有关的数据。根据具体问题的要求对数据库进行相 应的操作，从而构成规格化的数据库。 2 )针对产生的数据库，求h 所有满足最小支持度的项日集，即大项目集。 此步骤为算法的核心。 3 )生成满足最小置信度的规则，形成规则集。 4 ) 解释并输出规则集。 父联规则挖掘算法的原型如下： 输入：事务数据库d ； 最小支持度阈值m i n s u p p o m 最小置信度阈值m i n c o n f i d e n c e ； 输出：d 中所有关联规则 程序： 1 ) f o r a l l 大k 一项目集1 k ，k 2 i n l d o 2 ) b e g i n 3 ) h i = l k 中一个项目作为规则后项目的项目集合1 ； 4 ) a p g e n _ r u l e s ( 1 k ，h 1 ) ； 5 ) e n d 6 ) 7 ) a p g e n - r u l e s ( 1 k ，h m ) ； 8 ) i f k m + lt h e n 9 ) b e g i n 第1 2 页 坝l 学位论文 关联型数据挖掘挫术和移动代理往数字图书馆巾的府用 1 0 ) h m l = a p r i o f ig e n ( n 。) ；大项甘集生成算法； 1 1 )f o r a l lh m + 1 h 。n 十ld o 1 2 ) b e g i n 1 3 ) c o n f = s u p p o r t ( 1 k ) s u p p o r t ( 1 k h m l ) ； 1 4 )i f c o n f m i n c o n f i d e n c et h e n 1 5 ) 添加( 1 k h 。+ 1 ) jh m + 1 到规则集 1 6 )e l s e 1 7 )从h m + 1 删除h m + 1 ； 1 8 )e n d 1 9 ) a p g e nr u l e s ( 1 k ，h m 十1 ) ； 2 0 )e n d 就算法而言。利用了以下原则： 1 ) 如果规则a j ( l a ) 不满足最小置信度，则对于a 所有的非空子集b ，规 则b j ( l b ) 也不满足最小置信度，因为a 的最小支持度b 最小支持度。 如果( l a ) j a 满足最小置信度，则对于a 的非空子集b 所有的形如 f l - b ) j b 的规则也一定满足最小置信度。 2 2 4 2 其他几种挖掘算法 1 、分类方法( c l a s s i f i c a t i o n ) 分类法是最普通的数据挖掘方法之一。它试图按照事先定义的标准对数据进 行归类。分类法大至上可分为如下几种类型 1 )决策树归纳法( d e c i s i o nt r e ei n d u c t i o n ) ，根据数据的值把数据分层 组织成树型结构。在决策树中每一个分支代表一个子类，树的每层代 表、一个概念。国际上最有影响和最早的决策树方法是由q u i u l a n 研制的 i d 3 方法 q u 8 6 3 ，后人又发展了各种决策树方法，如b r o d l e yc e 等人 使用顺序反向删除和顺序前向选择2 种策略，选择若干属性的线性组合 作为分枝属。i 牛 b u 9 5 。 2 )神经网络法( n e u r a ln e t w o r k s ) ，要是通过训练神经网络使其识别不 关联型数据挖掘技术和移动代理在数宁幽 s 馆中的心用 同的类，再利用神经网络对数据进行归类。 2 、聚类方法( c l u s t e r i n g ) 聚类是把一组个体按照相似性归成若1 j 类别。它的目的是使得属于同类 别的个体之间的距离尽可能的小，而不同类别上的个体问的距离尽可能的人。聚 类方法包括统计方法、机器学习方法、神经网络方法和面向数据库的方法。 传统的统计聚类分析方法包括系统聚类法、分解法、加入法、动态聚类法、 有序样品聚类、有重叠聚类和模糊聚类等。聚类分析方法矸i 具有线性的计算复杂 度，难以适用于数据库非常大的情况。 3 、粗糙集方法( r o u g hs e t ) 粗糙集理论是近年来才兴起的用于研究不精确、不确定性知识的学习、表达、 归纳的方法。它通过引入不可分辨关系、等价类、上近似、下近似等概念考察知 识表达中不同属性的重要性，来确定哪些属性是冗余的，哪些属性是必不可少的。 删除冗余属性进而简化知识表达空间，最终能从数据中挖掘出规则。它的理论核 心是：知识源于对对象的分类这，通过分类找出属性间的关联规则 韩张9 9 。 4 、遗传算法( g e n e t i c a l g o r i t h m s ) 遗传算法是基于达尔文的进化论中基因重组、突变和自然选择等概念。这些 算法作用于对某一特定问题的一组可能的解法。它们试图通过组合或“繁殖”现 存的最好的解法来产生更好的解法。利用“适者生存”的概念使较差的解法被抛 弃，从而导致解法的集合，即繁殖的结果得到改善。 2 3 数据挖掘在数字图书馆中应用的必要性和可行性 2 3 1数据挖掘在数字图书馆中的必要性 虽然现在数字图书馆得到了极大的发展，但是随着网络化的发展，数字图书 馆作为社会信息中心的职能日益上升，自动化建设也有了新的要求。 首先，图书馆要处理和提供的信息更多、更新、更广、更复杂。为了避免陷 碱_ 学位论文关联犁数据挖掘技术和移动代理在数宁图书馆中的心用 入“数据丰富、信息贫乏”的局面，图书馆有必要加强对信息的处理能力以及对 信息资源的组织能力，尤其是对海量信息的深层次的开发，提取表面上庞杂无序 的信息的内在联系供读者使用。 其次，随着读者信息水平和信息要求的不断提高，向读者提供更主动的和个 性化的信息服务被摆到图书馆面前。图书馆要谋求自身的发展，固步于传统的业 务是不可取得，必须在原有工作基础上不断扩展、不断满足读者新的更复杂的要 求。 再次，在图书馆现有的自动化系统中每年、每月、每天产生着大量的统计数 据和表单，对图书馆的采购、馆藏、咨询等业务有着很强的指导作用。但快速增 长数据收集往往会变成“数据坟墓”，失去其指导价值。 这些要求都呼唤一个强有力的数据采集和处理工具介入图书馆中，为图书馆 工作提供技术支持和决策管理支持。而数据挖掘就是这样的一种技术。 2 3 2 数据挖掘在数字图书馆中的可行性 数据挖掘技术是在“数据的丰富带来了对强有力的数据分析工具的需求” 的条件下发展起来的。从，卜世纪8 0 年代后期到现在，已经取得了丰硕的成果。 伴随着数字图书馆自动化系统建设而建立和发展的大量数据库，在运行过程中产 牛的大量数据，以及图书馆长期以来形成的有序的、有组织的大量书目信息，都 是数据挖掘技术施展其能力的基础。在数字图书馆中普遍使用的是关系数据库， 而关系数据库正是数据挖掘研究的主要数据形式。再者，在网络化和电子图书馆 的环境下，文本数据库和w e b 上的大量信息成为数字图书馆的重要信息源，而这 两种信息源的数据挖掘文本挖掘和w e b 挖掘则是当前数据挖掘重要的研究 课题。总之，数据挖掘应用于数字图书馆在技术上是完全可行的。 2 4 数据挖掘在数字图书馆中的应用 在数字图书馆中采用各种数据挖掘技术与方法，完全可以评判信息资源的利 用率、有效率、拒借率等指标，有助于数字图书馆的自动化建设，提升服务质量， 第1 5 页 关联型数据挖掘技术和移动代理在数宁图书馆中的城用 其作用如图2 6 所示。 信息资源建没 图2 6 数据挖掘在数字图书馆中的应用 2 4 1 信息资源优化建设 数据挖 掘 w eb 数 据挖拥 文本数 据挖批 传统图书馆信息采集多由专fj 采访人员独自确定或与少数专家商讨决定，不 可避免的带有极大的主观性以及个人喜好。利用基于移动代理的数据挖掘，至少 可以从以下三方面搜集，1 泛的信息需求，聚集用户智慧，达到信息资源的优化并 提高针对性。 第一，可以对流通记录、检索请求进行分析，按类统计文献拒借集和频繁借 阅集，有针对性的补充和丰富信息资源；并可以籍此分析出文献的利用率，及时 剔除过时的文献信息，或减少部分文献信息的采访搜集量。另一方面，对用户每 次借阅的文献进行关联分析，发现各类文献间的关联规则或比例关系，优化信息 建设或馆藏布局。 第二，搜集整理重构数字图书馆系统在线调查、留言簿、荐书条等中的数据， 使之转化为标准的结构化数据库，利用数据挖掘方法发现用户兴趣模式。甚至可 以预先发现用户群体兴趣的变迁，调整馆藏方向，提前做好文献信息的搜集订购。 第三，利用w e b 访问信息的挖掘，分析服务器l o g 中用户请求失败的数据， 结合聚集算法发现信息资源的缺漏。另外，利用路径分析模式采掘捕捉确定用户 频繁浏览访问的路径，改进数字图书馆站点结构设计，并可在适当处加， 二广告或 第1 6 硬 顿i j 学位论文关联犁数掂挖掘技术和移动代理在数图书馆中的应用 荐书条。 c h 9 6 1 给出了具体的路径模式采掘步骤。 2 4 2 信息自动化处理 从数字图书馆发展趋势来看，其资源将涌盖纸质文献、电子图书、电子期刊、 光盘数据库、多媒体数据以及w e b 数据等，并且其中每一一种数据都在迅猛增长， 对各种类型信息处理的自动化要求愈显迫切。针对数字图书馆中文本数据占据绝 人多数的特点，本文着重探讨数据挖掘在文本数据自动化处理中的应用。其可以 分为文档的表示和标引；文本自动摘要；文档自动分类等。 2 4 3 信息服务质量和服务形式的扩展 数字图书馆借助现代信息技术，其意义不仅在于服务媒体和时空的转变，更 重要的是能够借助数据挖掘技术完善服务结构和提升服务水平： 第一，提高信息获取速度。为保证用户在尽可能短的响应时间内获取所需信 息，首先可以搜集用户每次阅读的专题集合( 浏览模式) 作为一个事务，记录所有 用户每一次浏览过程构成事务库，再对事务库进行如下操作：( 1 ) 利用关联规则 采掘算法找到访问频率超过给定闽值的专题( 项目) 集，进而用分类算法把客户的 浏览模式与频繁项目集进行相似匹配，将具相似浏览模式的客户组织到个服务 器l ，从而减少服务器缓存和传输页面的数量；( 2 ) 找到事务库中频率访问的专 题集，利用关联分析得到专题之间的关联规则，存入服务器的知识库，当用户浏 览某页时，网络代理根据规则预先连接其关联页，从而提高响应速度；( 3 ) 也可 利用w e b 挖掘得到用户访问序列模式，根据预测预先传输用户可能阅读的页面。 第二，提供个性化服务。个性化服务表现为两个层次。第一层次为按用户要 求进行信息订制。第二层次则是数字图书馆挖掘用户兴趣模式，主动提供服务， 使数字图书馆成为一个智能型、主动性的信息提供商。具体的过程可以包括：( 1 ) ， 根据本地和异地数字图书馆对用户兴趣的调查建模。( 2 ) ，将数字图书馆中的资 源与用户兴趣相比较，把与用户兴趣相符合的信息主动推荐给用户。( 3 ) ，根据 用户兴趣对检索结果进行排列、分类。 第三，提升服务质量，拓展服务形式。如同网络向智能化方向发展一样，信 第1 7 页 硕l 学位论文关联型数据挖掘技术和移动代理在数字图书馆中的应l 息服务也应“智能化”，即由被动服务转向主动服务，由单纯的信息早现转阳信 息生成。信息检索服务。传统的检索： 具缺乏结果的友好性、可理解性和交互性， 往往将一大堆查询结果线性呈现，令用户不知所入；智能化的信息检索不仅支持 概念检索、模糊检索、联想检索及多语言检索等，而且能迅速利用聚类算法将查 询结果分析聚类，使之条理化呈现，方便用户筛选。同时在此基础上确定进一步 的检索定位。 2 4 4 关联型数据挖掘技术在数字图书馆中的应用 对于关联型数据挖掘技术而言，在数字图书馆中，主要可以有以下的应用： 第一，文档自动标引。数字图书馆中文本的对象一般缺乏结构化数据库中数 据的组织规整性，针对以上问题，关联型数据挖掘技术可以将这些文档转化为一 种类似结构化数据库中i 己录的较规整且能反映文档内容特征的表示，也就是文档 特征向量、文档自动标引。 第二，文本自动摘要。关联算法可以将原文中与主题密切相关的句子挑出来， 自动生成文本的摘要信息，这对于数字图书馆系统中电子图书、电子期刊等文献 信息具有巨大的应用价值。 第三，可以对用户每次借阅的文献，以及有关访问的日志进行关联分析，从 而发现各类文献间的关联规则或比例关系，优化信息建设或馆藏布局。 此外，关联型数据挖掘技术还可以与其他数据挖掘技术一起，评判数字图书 馆信息资源的利用率、有效率、拒借率等指标，引导数字图书馆的建设。 由此可见，关联型数据挖掘技术在数字图书馆资源建设中的应用前景广阔， 对教学、科研、生活、学术研究具有巨大的应用价值。 第1 8 页 烦j ：学化论文父联型数据挖掘技术和移动代理在数字幽书馆中的廊月j 第3 章基于移动代理的数字图书馆 数字图书馆主要是为了解决信息资源的有效利用而产，t 的。其哭键的技术是 解决如何从大量的、分布的信息仓储中查找所需要的相关信息并向用户提供最优 的显示。核心是研究数字化信息的有效组织结构，解决各特性不同的信息空问 仓储的匀操作性，形成数字图书馆的基础体系结构，有效的操作大规模、分布的 数字化信息。本章研究了当前数字图书馆中的框架，介绍了移动代理的基本原理， 在此基础上，提出了一个基于移动代理的数据挖掘模块，并将其嵌入数字图书馆 的框架中。 3 1数字图书馆现有系统框架及其优缺点的介绍 本节将介绍当前四种最具代表性的数字图书馆的框架，并对其优缺点进行分 析，从而揭示在数字图书馆中引入移动代理的必要性。 ( 1 ) 集成式一i n t e r s p a c e i n t e r s p a c e 是d l i ( 美国数字图书馆启动项目) 一期工程中的研究项目，由 l l l i n o i s 大学的科学家s c h a t z 主持研究 b s 9 7 k b 9 8 】。 i n t e r s p a c e 体系结构将互异的、分布的信息资源统一在一个一致的模型里。 它是一个互连的信息空间的集合，每个成员信息空间是一个互连对象的集合，其 中包含了某社区或某主题域的知识。网络上的每一份电子文献，在信息空间中都 表示为一个对象。该模型的基本抽象是一个特殊的对象：信息单元( i u ) ，既系 统中的基础组织单元。其关键的功能包括数据类型封装、语义索引与检索、全文 搜索、词语转换等。底层是一个分布式的数据存储层，负责常驻数据的管理。通 过i u 的拼合和协作，支持复杂的互操作应用。标准的服务包括：对象间互联、远 程执行、对象缓存、支持复杂对象等。 i n t e r s p a c e 系统由三层组成：应用层提供与用户的接口；应用编程环境( a p e ) 层包括编写各类高层应用所需的通用服务，a p e 为编写程序提供了一组简单的通 用对象( 如文献和数据库) 和一组通用高级服务( 如出版控制和收藏分析) ；系统 编程层( s p e ) 包括信息空间和i u s 基本功能，这是i n t e r s p a c e 的核心。其结构如图 3 1 所示。 第1 9 页 关联型数据挖掘技术和移动代理存数字国书馆中的应 用户謦 i n t e r s p a c e 分析环境 应用层 系统编程环境 ( s p e ) 磊磊币菰 。矗“姆 锱黔m m 一 显示交互l 查找索引i 结黧嘉型l 永粪器象i 通信 操作系统 图3 1 i n t e r s p a c e 结构图 i n t e r s p a c e 是建立于统一对象模型i l j 之上的一个系统，i u s 用于定义系统中 的所有功能。再加上应用环境及其查找、索引、链接、访问控制、包装等功能， 为强大的互操作的应用开发提供了一个坚实的基础。 但其也有不足之处： 1 1 i n t e r s p a c e 要求过于庞杂，要求必须有统一的模型，相同的标准和规范， 这给资源提供者带来了较大不便。 2 ) 是一个高集成性的系统，各个模块没有自主性，不能主动发现用户的兴 趣。 3 1 i n t e r s p a c e q 6 所有权和访问权是通过访问器抽象的捆绑在一起的，当用户 访问某个方法i u 时，访问器分配权限，使得用户独占这个i