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

摘要 随着w e b 站点自身信息越来越丰富和拓扑结构越来越复杂，目前信息服务 中普遍存在着“信息过载”和“资源迷向 的状况。面对今天浩如烟海的信息， 人们关心的是如何有效地收集和选择感兴趣的信息，更重要的是，人们关心如何 在日益增多的信息中自动发现新的概念，并自动分析它们之间的关系，能够真正 地做到信息处理的自动化。 准确及时地掌握用户对系统的访问情况是确保系统高效地实现自适应性的 重要依据。本文主要研究了数据挖掘技术的现状和发展，改进k - m e a n s 算法，优 化k m e a n s 算法的初始类中心，并改进每次类中心的计算方式，对上一次类中心 和本次迭代的所有簇对象的平均值再求均值作为类中心，减少了噪声的影响，加 快了迭代函数的收敛，提高了算法的效率，并应用于信息管理系统。系统根据r 志记录的数据获得各个模块用户的支持度的信息来关闭或者打开模块的 w e b p a r t ，实现站点的智能化，使其提供模块自动推荐，改变用户视图和优化系 统结构，提高站点信息服务质量，促进智能信息处理领域的发展，在理论和实践 上都有重要的研究意义。 关键字：数据挖掘，关联规则，聚类规则，w e b p a r t a b s t r a c t a st h ei n f o r m a t i o no fw e b s i t ei sm o r ea n dm o r ea b u n d a n ta sw e l la st h et o p o l o g y m o r ea n dm o r ec o m p l e x ，t h e r ee x i s t st h es i t u a t i o no f “i n f o r m a t i o no v e r l o a d i n g a n d “r e s o u r c em a z e ”i ni n f o r m a t i o ns e r v i c e t o d a yt h ef a c e o fab r o a da r r a yo f i n f o r m a t i o n p e o p l ea r ec o n c e r n e da b o u ti sh o wt oe f f e c t i v e l yc o l l e c ta n ds e l e c t i n f o r m a t i o no fi n t e r e s t ，a n d ，m o r ei m p o r t a n t l y , p e o p l ea r ec o n c e r n e da b o u th o wt h e g r o w i n gn u m b e ro fi n f o r m a t i o na u t o m a t i c a l l yd i s c o v e rn e wc o n c e p t s a n da u t o m a t i c a n a l y s i so ft h er e l a t i o n s h i pb e t w e e nt h e m ，c a nt r u l ys u c c e e di nt h ea u t o m a t i o no f i n f o r m a t i o np r o c e s s i n g a c c u r a t ea n dt i m e l yg r a s po fu s e r so nt h es y s t e m sv i s i ti st oe n s u r et h a te f f i c i e n t s y s t e mt oa c h i e v ea ni m p o r t a n tb a s i sf o ra d a p t a b i l i t y t h i sp a p e rm a i n l yo nt h es t a t u s o fd a t am i n i n gt e c h n o l o g ya n dd e v e l o p m e n t ，i m p r o v i n gt h ek m e a n s a l g o r i t h m ， k m e a n sa l g o r i t h mo p t i m i z a t i o no ft h ei n i t i a lc a t e g o r yc e n t e r s e a c ho ft h ec e n t r ea n d t oi m p r o v et h em e t h o do fc a l c u l a t i n gt h el a s tt i m et h i sc a t e g o r yc e n t e r sa n dt h e i t e r a t i v et h ea v e r a g eo fa l lc l u s t e rt a r g e t sa sam e a n so fs e e k i n gr e c e n t r e r e d u c i n gt h e i m p a c to fn o i s e ，s p e e du pt h ec o n v e r g e n c eo ft h ei t e r a t i v ef u n c t i o nt oe n h a n c et h e e f f i c i e n c yo ft h ea l g o r i t h m ，a n da p p l i e di n f o r m a t i o nm a n a g e m e n ts y s t e m a c c o r d i n g t ot h es y s t e ml o gd a t au s e r sa c c e s st ot h ev a r i o u sm o d u l e so ft h ed e g r e eo fs u p p o r tt o c l o s e do ro p e ni n f o r m a t i o nm o d u l ew e b p a r tt oa c h i e v es i t e i n t e l l i g e n t a u t o m a t i c s y s t e mm o d u l et op r o v i d er e c o m m e n d e dc h a n g e su s e r sv i e wa n do p t i m i z e ds y s t e m s t r u c t u r e ，i m p r o v et h eq u a l i t yo fs e r v i c e i n t e l l i g e n ti n f o r m a t i o np r o c e s s i n gf i e l d a n di np r a c t i c e i n f o r m a t i o ns i t e ，p r o m o t et h ed e v e l o p m e n to f i ti si m p o r t a n tr e s e a r c hs i g n i f i c a n c ei nt h e o r y 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 s ，c l u s t e r i n gr u l e s ，w e b p a r t 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得丞洼王些太堂或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示了谢意。 学位敝作者虢髟l 司莨 签字日期：殍7 月2 护 学位论文版权使用授权书 本学位论文作者完全了解丞洼王些太堂有关保留、使用学位论文的规定。 特授权丞洼王些太堂可以将学位论文的全部或部分内容编入有关数据库进行 检索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学 校向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名 刍l r 筏 导师签名： 签字日期：2 一肛f 月百 签字日期： 嘭年月白 学位论文的主要创新点 一、优化k m e a n s 算法的初始类中心，并改进每次类中心的计算方式， 对上一次类中心和本次迭代的所有簇对象的平均值再求均值作为类中心，减 少了噪声的影响，加快了迭代函数的收敛，提高了算法的效率。 二、将改进算法应用于信息管理系统，提出一种新的基于数据挖掘的信 息系统模型，通过对日志系统信息进行挖掘，实现信息系统模块自推荐，提 高信息系统站点智能化。 第一章绪论 第一章绪论 1 1 论文选题背景和研究意义 a s 系统下的数据挖掘作为数据挖掘技术和i n t e r n e t 应用研究相结合的研 究领域，是自适应网站技术的重要工具。数据挖掘是从大量的、不完全的、有噪 声的、模糊的、随机的数据集中识别有效的、新颖的、潜在有用的，以及最终可 理解的模式的非平凡过程。而由于互联网自身数据海量，动态更新以及w e b 页 面组成复杂等特点，w e b 数据挖掘需要克服一些复杂的技术难点。因此，w e b 数 据挖掘是一门涉及面很广的交叉学科，还包括机器学习、数理统计、数据库、神 经网络、模式识别、粗糙集、模糊数学等人工智能相关技术，目前已经发展成为 一个受到社会各界关注的研究热点。 模块自推荐系统是把从日志数据中提取的知识转换成站点的智能，使其为用 户提供更高效的服务。这也将进一步推动w e b 数据挖掘和人工智能的发展，促 使网络技术和智能信息处理领域中一些有价值的新技术诞生他1 。综上所述，模块 自推荐系统无论在实践上还是在理论上都有很重要的研究意义。 1 2 基于w e b 数据挖掘信息管理系统研究现状 从数据库中发现知识( k d d ，k n o w l e d g ed i s c o v e r yi nd a t am i n i n g ) 一词首 次出现在1 9 8 9 年举行的第十一届国际联合人工智能学术会议上。之后，研究重 点逐渐从发现方法转向系统应用，注重多种发现策略和技术的集成，以及多种学 科之间的相互渗透。在美国国家科学基金会( n s f ，n a t i o n a ls c i e n c ef o u n d a t i o n ) 的数据库研究项目中，k d d 被列为9 0 年代最有价值的研究项目口1 。人工智能研 究领域的科学家也普遍认为，下一个人工智能应用的重要课题之一，将是以机器 学习算法为主要工具的大规模的数据库知识发现。尽管数据挖掘还是一个很新的 研究课题，但它所固有的为企业创造巨大经济效益的潜力，已使其很快有了许多 成功的应用，具有代表性的应用领域有市场预测、投资、制造业、银行、通讯等 【4 】 o 美国钢铁公司和神户钢铁公司利用基于数据挖掘技术的i s p a 系统，研究分 析产品性能规律和进行质量控制，取得了显著效果。通用电器公n ( g e ，g e n e r a l e l e c t r i cc o m p a n y ) 与法国飞机发动机制造公司，利用数据挖掘技术研制了工质量 控制系统，被三家欧洲航空公司用于诊断和预测渡音的故障，带来了可观的经济 效益。该系统于1 9 9 6 年获欧洲一等创造性应用奖晦3 。 第一章绪论 享有盛誉的市场研究公司，如美国的a c n i e l s o n 和i n f o r m a t i o nr e s o u r c e s ， 欧洲的g f k 和i n f r a t e s tb u r k 等纷纷开始使用数据挖掘工具来应付迅速增长的销 售和市场信息数据。商家的激烈竞争导致了市场快速饱和，产品的迅速更新，增 加了经营者对市场信息的需求。市场研究公司利用数据挖掘技术所形成的市场预 测能力和服务，取得了巨大收益哺3 。 英国广播公司( b b c ) 也应用数据挖掘技术来预测电视收视率，以便合理安排 电视节目时刻表。信用卡公司a l l l e l i c a l lk x t r e s s 自采用数据挖掘技术后，信用卡 使用率增加了1 0 一1 5 n 1 。a t & t 公司凭借数据挖掘技术侦探国际电话欺诈行 为，可以尽快发现国际电话使用中的不正常现象。 与国外相比，国内对d m k d 的研究稍晚，没有形成整体力量。1 9 9 3 年国家 自然科学基金首次支持该领域的研究项目。目前，国内的许多科研单位和高等院 校竞相开展知识发现的基础理论及其应用研究，这些单位包括清华大学、中科院 计算技术研究所、空军第三研究所、海军装备论证中心等。中国的公安部门正在 研究利用k d d 技术总结各类案件的共性和发生规律，从而在宏观上制定最有效 的社会治安综合治理的方案和措施，在微观上指出犯罪人的特点，划定罪犯的范 围，为侦破工作提供方向。 最近，g a r t n e rg r o u p 的一次高级技术调查将数据挖掘和人工智能列为“未来 三到五年内将对工业产生深远影响的五大关键技术 之首，并且还将并行处理体 系和数据挖掘列为未来五年内投资焦点的十大新兴技术前两位。根据最近的研究 表明，“随着数据捕获、传输和存储技术的快速发展，大型系统用户将更多地需 要采用新技术来挖掘市场以外的价值，采用更为广阔的并行处理系统来创建新的 商业增长点。8 1 就目前来看，将来的几个热点包括网站的数据挖掘( w e bs i t ed a t a m i n i n g ) 、生物信息或基因( b i o i n f o r m a t i c sg e n o m i c s ) 的数据挖掘及其文本的数据 挖掘( t e x t u a ld a t am i n i n g ) 。 目前还有许多开发者在开发通用可靠的工具集，可以预见，新的应用工具将 随着新的挖掘技术的出现而不断地产生。 w e b 数据挖掘系统阻1 指使用数据挖掘技术在w w w 数据中发现潜在的、有用的 模式或信息。挖掘研究覆盖了多个研究领域，包括数据库技术、信息获取技术、 统计学、人工智能中的机器学习和神经网络等。作为一个完整的技术体系，在进 行w e b 挖掘之前的信息获得和信息抽取相当重要。信息获得目的在于找到相关 w e b 文档，而信息抽取目的在于从文档中找到需要的数据项目，它对文档的结构 和表达的含义感兴趣，其重要任务就是对数据进行组织整理并适当建立模型。信 息获得和信息抽取技术的研究已经有很长时间，随着w e b 技术的发展，由于w e b 数据量非常大而且增长快，用原来手工方式进行信息收集早已经力不从心，目前 2 第一章绪论 的研究方向是用自动化、半自动化的方法在w e b 上进行信息获得和信息抽取。根 据对w e b 数据感兴趣的不同角度，w e b 挖掘一般分为w e b 内容挖掘( w e bc o n t e n t m i n i n g ) ，w e b 结构挖掘( w e bs t r u c t u r em i n i n g ) ，w e b 使用记录挖掘( w e bu s a g e m i n i n g ) 。在搜索引擎的研究方面，结构挖掘的研究已经相对成熟，基于文本的 内容挖掘也已经有许多研究。使用记录挖掘与用户的行为分析密切相关，是实现 模块自推荐系统的重要工具，目前的研究集中于关联规则，序列模式，聚类和分 类模式们。 模块自推荐技术从1 9 9 6 年开始就已经成为人工智能领域的研究热点n 1 1 ，近 年来伴随着w e b 数据挖掘技术的不断成熟，已经取得了一些重要的理论和实践成 果。 目前关于模块自推荐系统的重点集中于信息系统的模块根据用户的关注程 度自动显示或者隐藏，其主流技术是自推荐技术。即根据网页的浏览量分析，找 出用户最感兴趣的模块。根据实现的途径不同，个性化推荐技术可以分为基于规 则的推荐、基于内容的推荐、合作推荐和混合推荐。 1 2 1 基于规则的推荐 基于规则的推荐是指根据已经生成的规则向用户推荐网页的方式n 刭。该方式 较多地应用于电子商务网站，根据用户浏览和购买的日志生成规则，向用户推荐 感兴趣的商品。允许系统管理员根据用户的静态特征和动态属性来制定规则。一 个规则本质上是一个i f - t h e n 语句，规则决定了在不同的情况下如何提供不同 的服务。此类系统的优点是简单直接，精确度高，缺点是规则的质量很难保证而 且不能动态更新，系统负荷也将随着规则数量的增多而不断加重。 1 2 2 基于内容的推荐 基于内容的推荐是指通过比较资源与用户模型的相似程度向用户推荐网页 的方式n 引。这种方式是目前个性化推荐的主流，较多地应用于可计算的文本领域， 如浏览页面的推荐、新闻组中的新闻推荐等。利用资源和用户兴趣的相似性来过 滤信息。这种方法的优点是简单有效，缺点是不能发现用户的新兴趣信息，只能 推荐与已发现用户兴趣相似的页面。 1 2 3 合作推荐 合作推荐是指通过相同或相近兴趣的用户对资源的评价向用户推荐网页的 方式n 们。该方法是通过比较用户之间的相似性来推荐信息，即先对用户进行分类。 3 第一章绪论 这种方法既适用于可计算的文本领域，又可应用于其它领域，如音乐、电影和书 籍。该方法的优点是可以预测用户可能感兴趣的新信息，缺点是存在两个难点： 一是稀疏性，即在系统使用初期，由于系统资源还未获得足够多的评价，系统很 难利用这些评价来发现相似的用户；另一个是扩展性，即随着系统用户和资源的 增多，系统的性能会越来越低。 1 2 4 混合推荐 混合推荐是指既通过比较资源与各个用户模型的相似度进行基于内容的推 荐，又通过相似兴趣的用户群进行合作推荐的一种方式n 射。这种方法具有较好的 推荐性能。混合推荐同时采用了基于内容的推荐和合作推荐，可以克服这两种技 术各自的一些缺点。为了克服合作推荐的稀疏性问题，可以利用用户浏览过的资 源内容预期用户对其它资源的评价。这样可以增加资源评价的密度，利用这些评 价再进行基于内容的推荐，从而提高合作推荐的性能。近年来，很多电子商务网 站也注意到了个性化服务的巨大商机，如新浪网也推出了个性化服务功能n 引。经 历了近十年的发展，个性化服务虽然还不甚成熟，但已经真真切切地走进了我们 的生活，为广大用户和网络公司带来益处。系统结构的修改可以在线进行也可以 离线进行，但是关于系统如何自适应改善拓扑结构目前仍处于摸索阶段。此外， 如何用评价测度评价自适应技术是否提高了信息服务质量，使管理员先验知识和 智能更好的配合人工智能来确保系统的改善也是一个需要关注的问题。 1 3 论文结构 第一章是绪论。首先介绍了论文选题背景和研究意义，然后介绍了数据挖掘 技术和目前的研究现状，说明了本文的研究内容及其意义。 第二章是数据挖掘技术研究。首先概述了数据挖掘的定义，功能和流程。然 后介绍常用技术和方法，最后介绍数据挖掘技术的应用范围和应用前景。 第三章设计并实现上海科技馆信息管理系统。首先阐述了系统的总体目标和 项目需求，接着提出了系统的拓扑结构，讨论了系统的软件设计技术，最后根据 上海科技馆信息管理系统的实际情况提出系统功能架构。 第四章研究了k - m e a n s 算法，并优化k - m e a n s 算法的初始类中心，并改进每 次类中心的计算方式，对上一次类中心和本次迭代的所有簇对象的平均值再求均 值作为类中心，减少了噪声的影响，加快了迭代函数的收敛。 第五章研究数据挖掘在管理信息系统中的应用。首先介绍了数据准备和预处 理，然后给出算法定义和描述，最后给出数据挖掘应用系统模型。 第六章是全文总结和展望。总结本文所完成的工作，并提出我们以后需进一 4 第一章绪论 步研究的方向和问题。 5 第二章数据挖掘研究 第二章数据挖掘研究 随着数据库技术的发展和应用，人类积累的数据量正在以指数速度迅速增 长。进入2 0 世纪9 0 年代，i n t e r n e t 的出现和发展，将整个世界联成一个小小的 地球村。人们可以跨越时空地在网上交换数据信息和协同工作。因此展现在人们 面前的己不再是局限于本部门、本单位和本行业的庞大数据库，而是浩瀚无垠的 信息海洋，数据洪水正向人们滚滚涌来。当数据量急速增长时，如果没有有效的方 法，利用计算机及信息技术来提取有用信息，人们也会感到面对信息海洋像大海 捞针一样束手无策。据估计，一个大型企业数据库中的数据，只有约百分之七能得 到很好应用。这样，在“数据过剩”和“信息爆炸 的同时，人们又感到“信息贫 乏和“数据关在牢笼中，人类正被信息淹没，却饥渴于有用信息的提取。面临 浩瀚无际的数据海洋，人们迫切需要能找到一种去粗取精、去伪存真的技术。从 数据库中发现有用的知识及其核心技术数据挖掘技术便应运而生了。n 司 数据挖掘技术根据其任务的不同，可以分成关联规则挖掘、分类规则挖掘、 聚类规则挖掘以及预测、趋势和偏差分析等。它是一门涉及面很广的交叉学科， 包括机器学习、数理统计、神经网络、数据库、模式识别、粗糙集、模糊数学等 相关技术n7 1 。本章将就论文后面各章所涉及的一些规则，在相关概念和技术方面 进行讨论。 2 1 数据挖掘综述 2 1 1 数据挖掘 数据挖掘的历史虽然较短，但从2 0 世纪9 0 年代以来，它的发展速度很快， 在当今世界的海量数据中隐藏着人们所需要的具有决策意义的信息。数据挖掘技 术的产生和发展使得人们可以利用这些数据中挖掘出有用的、隐藏的商业和科学 信息。由于数据挖掘是多学科综合的产物，它从多个学科汲取营养，包括数据库 技术、人工智能、机器学习、神经网络、统计学、模式识别、知识库系统、信息 检索和数据库可视化等，因此目前还没有一个完整的定义。通常普遍认同的一个 十分广泛的数据挖掘定义是：从数据库中抽取隐含的、以前未知的、具有潜在应 用价值的模型或规则等有用知识的复杂过程，是一类深层次的数据分析方法。 ( 1 ) 数据挖掘系统的体系结构 第二章数据挖掘研究 图2 1 数据挖掘系统体系结构图 ( 2 ) 数据挖掘的主要方法n 明 在数据挖掘的处理过程中，数据挖掘方法是最为关键的，而目前数据挖掘的 方法主要有以下几类： 关联规则方法：挖掘关联规则就是发现存在于大量数据集中的关联性或 相关性，例如关联规则“9 0 客户在购买面包的同时也会购买牛奶”，其直观意义 为顾客在购买某些商品的时候有多大倾向会购买另外一些商品。 分类和聚类方法：分类就是假定数据库中的每个对象( 在关系数据库中对 象是元组) 属于一个预先给定的类，从而将数据库中的数据分配到给定的类中。 而聚类是将实体对象集合依照某种相似性度量原则划分为若干个类似实体对象 组成的多个类或簇的过程。分类和聚类都是对目标进行划分，划分的标准是类内 差别最小而类问差别最大。分类和聚类的区别在于分类事先知道类别数和各类的 典型特征，而聚类则事先不知道。 数据统计方法：使用这些方法一般首先建立一个数据模型或统计模型， 然后根据这种模型提取有关的知识。例如，可由训练数据建立一个b a y e s i a n 网， 然后，根据该网的一些参数及联系权重提取出相关的知识。 机器学习方法：大多数机器学习方法使用人类的认识模型模仿人类的学 习方法从数据中提取知识，由于机器学习经过多年的研究，已取得了一些较满意 的成果，因此，在数据挖掘中可以利用目前比较成熟的机器学习方法。 多层次数据汇总归纳：数据库中的数据和对象经常包含原始概念层上的 详细信息，将一个数据集和归纳成更高概念层次信息的数据挖掘技术被称为数据 汇总。概念汇总将数据库中的相关数据由低概念层抽象到高概念层，主要有数据 立方体和面向对象的归纳两种方法。 神经网络方法：神经网络由于本身良好的鲁棒性、自组织自适应性、并 行处理、分布存储和高度容错等特性非常适合解决数据挖掘的问题，因此近年来 7 图一图一圉 第二章数据挖掘研究 越来越受到人们的关注。典型的神经网络模型主要分3 大类：以感知机、b p 反 向传播模型、函数型网络为代表的，用于分类、预测和模式识别的前馈式神经网 络模型；以t t o p f i e l d 的离散模型和连续模型为代表的，分别用于联想记忆和优 化计算的反馈式神经网络模型；以a r t 模型、k o h o l o n 模型为代表的，用于聚 类的自组织映射方法。 决策树方法：利用信息论中的互信息( 信息增益) 寻找数据库中具有最 大信息量的字段，建立决策树的一个结点，再根据字段的不同取值建立树的分支； 在每个分枝子集中，重复建立树的下层结点和分支的过程，即可建立决策树。国 际上最有影响和最早的决策树方法是j r q u i n l a n 提出的i d 3 方法，它对越大 的数据库效果越好，在i d 3 基础上后人又发展成各种决策树方法。 序列模式分析方法：主要用于发现一定时间间隔内接连发生的事件。这 些事件构成一个序列，发现的序列应该具有普遍意义，其依据除了统计上的概率 之外，还要加上时间的约束。 可视化技术：数据与结果被转化和表达成可视化形式，如图形、图像等， 使用户对数据的剖析更清楚。 ( 3 ) 数据挖掘的发展趋势n 们 当前，数据挖掘知识发现的研究方兴未艾，数据挖掘研究人员、系统合应用 开发人员所面临的主要问题是高效而有效的数据挖掘方法和系统的开发，交互和 集成的数据挖掘环境的建立，以及如何应用挖掘技术解决大型应用问题。研究的 焦点可能会聚集在以下几方面： 数据挖掘语言的形式化描述：即研究专门用于知识发现的数据挖掘语言， 也许会像s q l 语言一样走向形式化和标准化。 可视化数据挖掘：是从大量数据中发现知识的有效途径，它使数据挖掘 的过程能够被用户理解，也便于在数据挖掘过程中进行人机交互，该技术将有助 于推进数据挖掘作为数据分析的基本工具。 多媒体数据挖掘：是指从大量的文本数据、图形数据、视频图像数据、 音频数据乃至综合多媒体数据的开采中，通过分析语义和视听特征，发现其中隐 含的、有价值的模式。它和传统的数据挖掘方法中处理的数据不同，传统的数据 挖掘处理的数据是数据库中表格形式中的记录和条目，属于结构型数据，而多媒 体数据挖掘处理的是非结构化的数据。 w e b 数据挖掘：主要是利用数据挖掘技术从w e b 文档及w e b 服务器中自 动发现并提取有用信息的过程。w e b 上有海量数据，这些数据最大特点是半结构 化。那么开发新的w e b 挖掘技术以及对w e b 文档进行预测处理以得到关于文档的 特征表示，就成为w e b 挖掘的重点。 8 第二章数据挖掘研究 数据挖掘中的隐私与信息安全：随着数据挖掘工具和电信与计算机网络 的日益普及，数据挖掘要面对的一个重要问题就是隐私保护和信息安全。需要进 一步开发有关方法，以便在适当的信息访问和挖掘中确保隐私保护与安全。 2 1 2w e b 数据挖掘 w e b 数据挖掘是数据挖掘技术和i n t e r n e t 应用研究相结合的研究领域。网 络中蕴藏着很多信息，例如，一个对于网络的分析可以揭示出人类语言群落的个 数。因为任何以某种语言写成的页面总是链接与它相同语言的页面，而几乎没有 与其他语言群落的联系。 目前互联网上的数据挖掘技术根据挖掘的方向一般分为三类：w e b 内容挖掘， w e b 结构挖掘和w e b 使用记录的挖掘。而结构本来就蕴藏在内容中，是内容的骨， 因此有些分类方法又分为w e b 内容挖掘和w e b 使用记录挖掘。本文按照后一种分 类方法来分析目前的相关技术和应用。 ( 1 ) w e b 内容挖掘 w e b 内容挖掘是指从w e b 文档内容中获取有用知识的过程，同时也可以对w e b 组织结构和链接关系进行挖掘，从人为的链接结构中获取有用的知识。由于文档 之间的互相关联，因此能够提供一些文档内容之外的信息，利用这些信息对页面 进行排序，进而发现重要的页面。目前w e b 内容挖掘多数是基于文本信息的挖掘， 它和通常的平面文本挖掘的功能和方法比较类似，但由于互联网上的数据基本上 都是h t m l 格式的文件数据格式流，因此可以利用文档中的h t m l 标记来提高w e b 文本挖掘的性能。目前主要使用的技术有两种类型：一种类型是建立在统计模型 的基础上，采用的技术有决策树、分类、聚类、关联规则等，主要技术包括：文 本总结，指从文档中抽取信息，用简洁的形式对文档内容进行摘要或者解释；文 本分类，指在已有数据的基础上学会一个分类函数或构造出一个分类模型，即通 常说的分类器；文本聚类：把一组文档按照相似性归纳成若干个类别，大致可以 分为层次凝聚法和平面划分法两种方法。另一种类型是建立一个以机器学习为主 的人工智能模型，采用的方法包括神经网络、自然法则计算方法等。 目前w e b 内容挖掘主要用于权威页面的发现以及分析相关的页面链接结构， 并且通过分析这类信息来获取到更多需要的信息。例如，现在许多w e b 搜索引擎 就利用w e b 内容挖掘中的w e b 超链分析算法来提高搜索的效率和准确性。传统的 w e b 搜索引擎大多数是基于关键字匹配的，返回的结果包含查询项的文档，也有 基于目录分类的搜索引擎，这些搜索引擎的结果并不十分令人满意。有些站点会 看准这些算法的弊端，有意提高关键字出现的频率来提高本身在搜索引擎中的重 要性，破坏搜索引擎结果的客观性和准确性。现在比较有名的搜索引擎g o o g l e 9 第二章数据挖掘研究 就是用了w e b 超链分析算法的一种p a g e r a n k 算法，它可以比较准确地将相 关的权威网页排在搜索结果的前面，是目前比较受欢迎的w e b 搜索引擎啪1 。总的 来说，理想的链接分析算法可以提高w w w 上重要社区的声望和权威性，w e b 内容 挖掘技术能够帮助用户在w w w 海量的信息里面准确找出需要的信息。 ( 2 ) w e b 使用记录挖掘比 w e b 使用记录挖掘是w e b 数据挖掘中最重要的应用，其数据源通常是服务器 的日志信息。w e b 服务器的日志( w e bl o g ) 记载了用户访问站点的信息，这些信 息包括：访问者的i p 地址、访问时间、访问方式( g e t p o s t ) 、浏览器，访问的 页两、协议、错误代码以及传输的字节数等信息。每当网页被请求一次，w e bl o g 就在日志数据库内追加相应的记录。站点的规模和复杂程度与日俱增，利用普通 的概率方法来统计、分析和安排站点结构已经不能满足要求。通过挖掘服务器的 日志文件，分析用户访问站点的规律，来改进网站的组织结构及其性能，增加个 性化服务，实现网站自适应，发现潜在的用户群体。 2 1 3f f e b 数据挖掘面临的问题 将数据挖掘技术应用到互联网数据上，理论上可行，但是由于互联网自身的 一螳特点，也使它面临一些需要克服的技术难点恤1 ： ( 1 ) 互联网上的数据动态性很强，页面本身的内容和相关的链接经常更新。 而互联网面对的客户也各不相同，这些都增加了用户行为模式分析的困难度。而 且，互联网上的数据是海量增长的。 ( 2 ) w e b 页面支持多种媒体的表达，比一般文本文件结构复杂很多。人们希 望通过w e b 来实现世界各种信息的互通，所以这个平台需要表达现实应用中所 有的任何信息。因此也造成了互联网数据的复杂性这个特点，互联网上的文档一 般是分布的，异构的，无结构或者半结构的。目前由于x m l 技术的出现，为解 决这个难题提供了一条可行的方法。 ( 3 ) 用户访问站点的情况复杂多样。如何从日志文件中构造网站访问模型， 挖掘出准确的用户访问模式从而发现网站被访问的规律，是一个复杂问题。 2 2 关联规则 在数据挖掘技术中，关联规则是比较重要的一种，也是最活跃的一个分支。 关联规则挖掘：从事务数据库，关系数据库和其他信息存储中的大量数据的项集 之间发现有趣的、频繁出现的模式、关联和相关性。即关联规则是表示数据库中 一组对象之间某种关联关系的规则。例如，采用关联模型比较典型的案例是“尿 布与啤酒”的故事。胁1 在美国，一些年轻的父亲下班后经常要到超市去买婴儿尿 1 0 第二章数据挖掘研究 布，超市也因此发现了一个规律，在购买婴儿尿布的年轻父亲们中，有3 0 - 4 0 的人同时要买一些啤酒。超市随后调整了货架的摆放，把尿布和啤酒放在一起， 明显增加了销售额。关联规则可以表示为“购买了项目a 和b 的顾客中有9 5 的 人又买了c 和d 。从这些规则可找出顾客购买行为模式，可以应用于商品货架设 计、生产安排、针对性的市场营销以及产品的组合销售等。再如，如果问题的全 域是商店中所有商品的集合，则对每种商品都可以用一个布尔量来表示该商品是 否被顾客购买，则每个购物篮都可以用一个布尔向量表示( 0 0 0 1 0 0 1 1 0 0 ) ；而通过 分析布尔向量则可以得到商品被频繁关联或被同时购买的模式，这些模式就可以 用关联规则表示，关联规则问题由r a g r a w a l 等在1 9 9 3 年首先提出，随即引起 了广泛的关注。许多研究者( 包括r a g r a w a l 本人) 对关联规则挖掘问题进行了深 入的研究，对最初的关联规则挖掘算法进行了改进和扩展。同时，关联规则的挖 掘被应用到许多其它领域的数据库，取得了良好的挖掘效果。 a g r a w a l 等于1 9 9 3 年首先提出了挖掘顾客交易数据库中项集间的关联规则 问题，以后诸多的研究人员对关联规则的挖掘问题进行了大量的研究。口钔他们的 工作包括对原有的算法进行优化，如引入随机采样、并行的思想等，以提高算法 挖掘规则的效率对关联规则的应用进行推广。 最近也有独立于a g r a w a l 的频集方法的工作，以避免频集方法的一些缺陷， 探索挖掘关联规则的新方法。也有一些工作注重于对挖掘到的模式的价值进行评 估，他们提出的模型建议了一些值得考虑的研究方向乜引。 2 2 i 关联规则描述 分析某一信息系统在一个时期内用户访问情况的事务数据库，将每个用户的 一次访问作为一个事务中的一条记录，每一个事务是所有可供访问的模块的一个 项目集合。挖掘关联规则就是查找所有描述一个项目集合与其他项目集合相关性 原则陉帕。例如，关联规则 b r o w n ( x ，“d o w n l o a d ) 一b r o w n ( x ，“n e w s c e n t e r ) s u p p o r t = 2 ， c o n f id e n c e = 8 0 表示的意义“进入新闻中心模块和进入下载中心下载的用户占所有用户的 2 ，而去下载中心的用户中有6 0 9 6 会去新闻中心 。设，= ，乞，毛。m 是m 个不 同项的集合，d 是针对i 的事务的集合，其中每一事务t 个包含若干 ，f ：，岛c j ，t c i ，有一个标识符t i d 。关联规则表示x y ，其中x ，y c i ，并 且x n y = ，x 称为规则的前提或前件，y 是结果或后件。 项集( i t e m s e t ) ：一些项的集合，在项集中的项数称为项集的长度，包含k 个项的项集称为k 一项集。 第二章数据挖掘研究 支持度( s u p p o r t ) ：表示一次事务中包含 x ，y ) 的可能性。 s u p p o r t ( x y ) = p ( xuy ) 置信度( c o n f i d e n c e ) ：表示包含x 的事务中也包含y 的条件概率。 c o n f i d e n c e ( x y ) = p ( yj x ) 阈值：最小支持度m i n s u p ，最小置信度m i n c o n f 。 如果个规则满足预先设定的最小支持度阈值和最小置信度阈值，则认为该规则 是有趣的。 关联规则的问题就是找出这样一些原则：它们的s u p p o r t 和c o n f i d e n c e 分别大| 二等于指定的m i n s u p 和m i n c o n f ，这一过程可以分解为两个子问题： ( 1 ) 挖掘所有s u p p o r t 满足m i n s u p 的项集，即产生频繁项集。 ( 2 ) 对于每个频繁项集，在任意频繁项集l 和任何scl 上产生所有满 足i i n c o n f 的规则。 该问题的主要难点在于( 1 ) ，因为数据集中的数据量巨大，如何以“对数据 集较少的扫描次数、对每个事务较少的项集比较次数 来完成这一过程，既如何 川最伙的速度获得频繁项集，是各种算法所研究的关键问题。 2 2 2 关联规则模型 关联规则挖掘他7 3 的任务就是要挖掘出数据集( 设为d ) 中的所有强规则。可以 将关联规则的挖掘划分为两个子问题：1 根据最小支持度计数找出数据集中的所 有频繁项目集：2 根据频繁项目集和最小置信度产生关联规则。 关联规则挖掘的基本模型如图2 2 所示。 图2 - 2 关联规则挖掘的基本模型 关联规则的挖掘可以分成两个步骤： 1 2 第二章数据挖掘研究 根据最小的支持度，在大量事务寻找高频率出现的频繁项集( i t e m s e t ) 。 根据最小的置信度，找到的频繁项集产生关联规则。 其中第二个步骤比较容易，一般经过第一步的筛选后的频繁项集都不会很 多，通过子集产生法就可以产生关联规则。第一个步骤是需要在大量的事务数据 集中寻找高频率出现的项集i t e m s e t ，所以就需要一个比较高效的搜索查找方法。 r a k e s ha g r a w a l 等在1 9 9 3 年提出了第一步搜索频繁项集的经典a p r i o r i 算 法汇。通过遍历一大堆事务数据中，从一个一个的单个项开始记数，每次遍历完 所有的事务后，裁减掉支持度记数少于用户给定的支持度的项，然后逐步扩展到 多项事务。最后保留下来的频繁项集，通过子集产生法来产生关联规则，然后去 掉其中置信度低于用户指定的最低置信度的关联规则，最后剩下的就是满足用户 需要的关联规则。 a p r i o r i 算法的特点就是在于从单项开始，每次剪裁一点，利用a p r i o r i 性 质，有效避免了对很多不可能的项的搜索过程。 2 2 3 典型算法分析 a g r a w a l 等于1 9 9 4 年提出了a p r i o r i 算法瞳8 1 ，这是迄今为止一种最有影响 的挖掘布尔型关联规则的算法。 ( 1 ) a p r i o r i 算法 a g r a w a l 等于1 9 9 4 年提出了a p r i o r i 算法，这是迄今为止一种最有影响的 挖掘布尔型关联规则的算法。该算法基于这样一个事实：频繁项集的子集一定都 是频繁项集，非频繁项集的超集一定都是非频繁项集。a p r i o r i 算法正是应用这 一性质连接和剪枝的，从频繁k 一项集生成侯选频繁( k + 1 ) 一项集。 a p r i o r i 算法采用逐层搜索迭代方法，首先找出频繁卜项集的集合厶，将 厶中各项集两两组合，采用侯选项集生成算法生成侯选频繁2 一项集的集合c 2 ， 再应用剪枝算法对其剪枝，之后扫描数据集c 2 生成频繁2 一项集的集合t ，以 此类推，不断调用连接算法由k 一，生成侯选频繁k 一项集的集合q ，调用剪枝算 法对c 剪枝，扫描数据集生成厶。对连接和剪枝算法描述如下。 连接：用频繁k 一项集的集合k 一，自连接得到候选k 一项集的集合g 。 剪枝：一个k 一项集，如果他的一个k 一1 项集( 他的子集) 不是频繁的，则 其本身也不可能是频繁的，应删除。 许多学者从不同角度提出了改进方法以提高a p r i o r i 算法的效率，概括如 下： 第二章数据挖掘研究 基于h a s h 的项集计数。因为如果一个k 一项集在h a s h - t r e e 的路径上的一 个计数值低于阈值，那他本身也不可能是频繁的。 减少事务记录。因为不包含任何频繁k 一项集的事务也不可能包含任何大于 k 的频繁项集分割。因为一个项集要想在整个数据库中是频繁的，那么他至少在 数据库的一个分割上是频繁的。 上述算法减少了数据集扫描复杂度、提高了数据挖掘的效率。 ( 2 ) t o pd o w nf p - g r o w t h 算法啪1 为j 了克服a p r i o r i 系列算法的缺点，根据关联规则挖掘的特点，1 9 9 9 年加 拿大的j i a w e ih a n 等人提出一种频繁模式增长( f r e q u e n tp a t t e r ng r o w t h ) 方法 1 8 ，或叫f p g r o w t h 方法，它采用分治策略：将提供频繁项集的数据库压缩到 一棵频繁模式树( f p t r e e ) 上，但是仍保留项集间的关联信息；然后将这种压缩 后的数据库分成一组条件数据库( 一种特殊类型的投影数据库) ，每个关联一个频 繁项，并分别挖掘每个条件数据库。 f p g r o w t h 算法是一种按照自底向上的从较短频繁项生成较长频繁项的挖掘 过程，在从短的频繁项生成较长频繁项的时候，该算法需要为每一短频繁项生成 一个条件模式库，并在条件模式库基础上递归构建子f p - t r e e ，而这一过程将耗 费大量的时间和空间。后来提出了一个称之为自项向下的规则挖掘算法 t d - f p - g r o w t h ( t o p d o w nf p g r o w t h ) ，该算法按照从顶向下的顺序生成频繁项， 不需要生成条件模式库和构建子f p - t r e e s ，这样节省了大量时间和空间。 t d f p g r o w t h 构建f p t r e e 的过程同f p - g r o w t h 一样，也需要扫描数据库 两次，但是在第二次扫描将事务中频繁项插入f p - t r e e 中的时候，将那些事务头 部含有相同频繁项的事务认为是共享相同的路径。f p t r e e 中每一个含有项目 ( i t e m ) i 的节点都用一个i - n o d e 结构来表示，这些含有项目i 的节点都通过一 个边连接( s i d e - l i