（管理科学与工程专业论文）基于支持向量机的web文本挖掘研究.pdf

基于支持向量机的w e b 文本挖掘研究 摘要 随着互联网等信息技术的发展和广泛应用，w e b 已经成为人们获取信息最重 要手段之一。互联网提供了到足够丰富的信息，而人们所需要的通常只是一部 分信息，如何从这海量的信息资源库中快速、准确地进行分类并提取出有用的 信息，显得异常迫切，当前广泛应用的搜索引擎技术，基于关键字搜索往往检 索的网页达数万条，其中很大一部分与主题无关，而有用的信息则淹没在这些 无关的信息中，这使得寻求通过数据挖掘技术在w e b 领域开辟新的途径。中文 文本分类是中文信息处理领域的重要组成部分，目前，广泛应用于w e b 中的搜 索引擎技术、信息过滤技术等都是文本分类技术的应用。 支持向量机技术是建立在统计学习理论的v c 维理论和结构风险最小原理基 础上的，根据有限的样本信息在模型的复杂性和学习能力之间寻求最佳折衷， 以期获得最好的推广能力。它是专门研究有限样本集的情况，算法最终转化为 一个二次型寻优阀题，通过非线性变换转到高维的特征空间，保证机器有较好 的推广能力，同时它巧妙地解决了维数灾难问题。 本文首先介绍了w e b 挖掘的研究内容，探讨了w e b 挖掘的内容挖掘、结构 挖掘和使用挖掘的常用技术及其存在的问题；随后对文本分类的研究进行了讨 论，总结了文本分类的一般处理过程，并就相关的算法步骤进行了深入的分析， 提出了一种基于语义引导的特征选择方法，对小样本集下的文本进行了分类实 验，结果表明，基于语义引导的特征选择方法有较高的查全率和查准率，具有 较好的分类性能。随后对支持向量机技术进行理论上的分析，探讨研究在有限 样本集下，支持向量机技术在文本分类中的优势。对多类文本分类的问题，进 行了分析，给出了集中解决方案，对多类文本分类问题，在变换成高维的特征 空间中核函数选取的问题进行了深入的讨论，分析核函数的选取对分类的精度 可能造成的影响。 最后，采用支持向量机技术，对有限样本集文本进行了分类实验。采用了 分类问题常用的评价算法查全率和查准率等进行了评估，比较研究了多项式核 函数参数的选取以及惩罚参数的变化对文本分类效果的影响。 关键词：w e b 挖掘，文本分类，语义引导，支持向量机 t h ew e bt e x tm i n i n gb a s e do n s u p p o r t v e c t o rm a c h i n e a b s t r a c t w i t ht h ei n t e r n e ta n do t h e ri n f o r m a t i o nt e c h n o l o g i e s sd e v e l o p m e n ta n dw i d e l y u s e d ，t h ew e bh a sb e c o m eo n eo ft h em o s ti m p o r t a n tm e a n st oo b t a i ni n f o r m a t i o n f o rp e o p l e i n t e r n e tp r o v i d e das u f f i c i e n ta b u n d a n c eo fi n f o r m a t i o n ，b u to n l yaf e w i su s e f u lf o r p e o p l e ，i t i sv e r yu r g e n tt of i n dh o wt os e a r c ha n dc l a s s i f yt h e d o c u m e n tq u i c k l ya n de x a c t l yf r o mt h eh u g ei n f o r m a t i o nd a t a b a s e t h i sm a k e s r e s e a r c h e rt of i n dt h em e t h o dt oi n t r o d u c et h ed a t am i n i n gt e c h n o l o g yi n t ot h ew e b a n di tw i l lb eo p e nu pn e wa r e a so ft h ew e bd a t am i n i n g s u p p o r tv e c t o rm a c h i n et e c h n o l o g yi sb a s e do ns t a t i s t i c a ll e a r n i n gt h e o r ya n d t h et h e o r yo fv c - d i m e n s i o n a la n ds t r u c t u r eo ft h es m a l l e s tr i s k ，b yt h el i m i t e d s a m p l eo ft h ei n f o r m a t i o ni nt h em o d e lt om a k eac o m p r o m i s eb e t w e e nt h e c o m p l e x i t ya n dl e a r n i n ga b i l i t y , w i t hav i e wt oo b t a i n i n gt h eb e s to u t r e a c hc a p a c i t y i tw a sd e v o t e dt ot h es t u d yo fal i m i t e ds a m p l es e t ，t h ea l g o r i t h mw i l le v e n t u a l l yb e t r a n s f o r m e di n t oa q u a d r a t i co p t i m i z a t i o np r o b l e m t h r o u g h n o n l i n e a r t r a n s f o r m a t i o nt oah i g h d i m e n s i o n a lf e a t u r es p a c e ，w h i c hg u a r a n t e et h em a c h i n e h a v eab e t t e rp r o m o t i o n ，i ta l s oc l e v e r l ys o l v e dt h ed i m e n s i o nd i s a s t e r t h i sp a p e rf i r s tr e s e a r c ht h ec o n t e n to ft h ew e b m i n i n g ，r e s e a r c ht h et e c h n o l o g y u s e da n dp r o b l e m se x i s t e d o ft h ew e bc o n t e n tm i n i n g ，w e bs t r u c t u r em i n i n ga n d u s a g em i n i n g s u b s e q u e n td i s c u s st h et e x tc l a s s i f i c a t i o n t h e n ，w eg i v eas a m - u po ft h ep r o c e s so ft h et e x tc l a s s i f i c a t i o n ，t h e na n a l y s i st h e a l g o r i t h mw h i c hu s e d i nt e x tc l a s s i f i c a t i o n d e e p l y , p r e s e n taf e a t u r es e l e c t i o n m e t h o db a s e d o ns e m a n t i c s ，u s et h eu s a l l ye v a l u a t e di nt e x tc l a s s i f i c a t i o ns u c ha s p r e c i s o n ，r e c a l le t ，s h o w st h et e x tf e a t u r es e l e c t i o nb a s e o ns e m a n t i c sh a v eag o o f f p e r f o r m a n c e a n a l y s es v mt e c h n o l o g yt h e o r e t i c a l ，d i s c u s s i o no ft h el i m i t e ds a m p l es e t ，t h e s v mt e c h n o l o g yi nt h et e x tc l a s s i f i c a t i o na d v a n t a g e f o rt h em a n ys o r t st e x t c l a s s i f i c a t i o n sp r o b l e m ，a n a l y s i st h e md e e p l ya n dg i v et h em e t h o d st or e s o l v e f i n a l l y , u s et h es u p p o r tv e c t o r m a c h i n e t e c h n o l o g y t o c o m p l e t e t e x t c l a s s i f i c a t i o nt e s t ，d i s c u s st h ep o l y n o m i a lk e r n e lp a r a m e t e r sc h a n g em a ye f f e c to n t h ew o r ko ft e x tc a t e g o r i z a t i o n k e y w o r d s ：w e bm i n i n g ，t e x tc a t e g o r i z a t i o n ，s u p p o r tv e c t o rm a c h i n e ，s e m a n t i c 图2 1 图3 1 图3 - 2 图4 - l 图睨 图4 。 插图清单 w e b 挖掘的分类9 语义描述图 语义层次结构图 样本学习模型 函数集子集：scs ：cs 3 0 最优分类超平面 v i 表3 - 1 表5 - 2 表5 - 3 基于语义引导的特征选择 表格清单 c 保持不变得情况下( 固定为c = o 5 ) d 保持不变得情况下( d 固定为1 ) l 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所 知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果 也不包含为获得金胆工些杰堂 或其他教育机构的学位或证书而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签字：j 京啭 飙呼；月日 学位论文版权使用授权书 本学位论文作者完全了解盒8 王些太堂有关保留、使用学位论文的规定，有权保留并向 国家有关鄂门或机构送交论文的复印件秘磁盘，允许论文被查阕或借阕。本人授权金b 壁王些盔 ! l 可以将学位论文的全部或部分论文内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文者签名：j 务峭 签字日期：守。滓1 5 月8 日 学位论文作者毕业后去向： 工作单位： 通讯地址： 黜名：锈舰4 y _ 签字日期：z 。呷年6 月哆日 电话： 邮编： 致谢 本文是在我的导师毛雪岷副教授的悉心指导下完成的。在三年的硕士研究 生期间，毛老师在学业上一直对我严格要求，生活上给予无微不至的关怀，我 所取得的每一点进步、每一点成绩都离不开毛老师的谆谆教诲，毛老师对我的 成长倾注了大量的心血。值此论文完成之际，我谨向导师毛老师表示诚挚的感 谢，并致以深深的敬意。毛老师渊博的学识、严谨的治学态度、敏锐的学术洞 察力、积极开拓和忘我的工作精神，对我产生很大的影响，将会使我受益终生。 在今后的学习、生活和工作中，我将以导师为榜样，为社会做出自己的贡献。 感谢实验室的张公让老师、朱方义老师、李应老师在平曰学习过程中的帮 助与指导，感谢师兄弟杨杰，张兄利、沈洋等在学习和工作上给予的帮助。 衷心感谢我的父母，几年来，他们在生活上给予我的关心，在学习上给我 不断地鼓励，使我能够最终完成我的学业。没有他们背后的支持，我将无法完 成我的学业，他们是我的精神支柱。 同时，我还要感谢审阅我的论文和参加我的论文答辩的各位老师，感谢他 们在百忙之中帮助我完成硕士论文的最后一个过程，这是我莫大的荣幸! 最后，感谢所有关心和帮助过我的师长、同学、朋友和亲人们! i l l 作者：丁友明 2 0 0 7 年5 月 第一章绪论 i i选题背景及意义 随着i n t e r n e t 的飞速发展，它在人们生活中发挥愈来愈重要的作用。 i n t e r n e t 上存储着大量的文件、图像、视频数据等各种信息资源，而且这些数 据分布在数以亿计的不同的网页中。据c n n i c 最新的统计，截至2 0 0 5 年1 2 月 3 1 日，我国已有1 亿的网络用户，近7 0 万个网站。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 文档 和w e b 结构中抽取感兴趣、潜在的、有用的信息进行w e b 挖掘。这就为数据挖 掘技术在w e b 领域发展开辟了新的空间。 数据挖掘( 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 yi n d a t a b a s e ，k d d ) 过程中进行模式抽取的阶段，指从大型数据库或数据仓库中提 取有效的、潜在的有应用价值的数据和知识的过程，它包括关联规则、聚类分 析、分类分析、模式序列、预测等。数据挖掘一般具有以下特点；1 、处理数据 的庞大性；2 、没有精确的查询要求，一般都是决策者提出的即时随机查询：3 、 数据挖掘发现的规则是动态的，它只能反映当前状态的数据库所呈现的特点， 随看新数据的不断加入，需要随时对其更新。4 、数据挖掘中发现的规则是基于 统计规律的，它是大多数的样本的所具备的特征，因此，发现的规则不必适用 于所有数据，只要达到某一阀值时，即为规律。 w e b 挖掘是在数据挖掘研究的一个新方向，是指使用数据挖掘技术从w e b 文档和w e b 活动中发现感兴趣的、有用的模式和隐含的信息。如果将w e b 文 件的集合看作g ，隐含的知识或模式看作m ，那么w e b 挖掘的过程就是一个从输 入g 到输出m 的一个映像e ，记作： ：g - ，n w e b 挖掘从数据挖掘发展而来，但是w e b 与传统的数据挖掘相比有以下特 点。 首先w e b 挖掘的对象是大量的、不同的、分布的w e b 文件，而对于w e b 服务器上的日志等进行的挖掘仍属于传统的数据挖掘范畴。其次，w e b 在逻辑 上是一个由文件节点和超链接结构构成的图形，挖掘得到的知识可以是关于 w e b 内容的，也可以是关于w e b 结构的。由于w e b 挖掘的对象是半结构化或无 结构化的，因此，基于传统的结构化数据库的数据挖掘技术并不都适合于w e b 挖掘，对此，可以对w e b 文档数据进行适当的预处理或者研究新的w e b 挖掘方 法。 1 2 w e b 挖掘研究现状 1 2 1 国外的研究现状 文本分类长期以来一直是自然语言处理的一个重要的研究领域。国外在 w e b 挖掘领域的研究技术相对来说比较深入。 从w e b 文本的自身特点来分，主要有从两个方向：一是从信息检索的角度 来进行研究，着重研究文本内容的结构化处理。由于w e b 上信息的非结构化或 半结构化的特点，数据多数以词、短语的形式展现，因此，通过对词组、短语 在文本中权重的计算度量和统计等方法，来对文档进行分类、聚类，从而抽取 出词组在文本中出现的规律。h a m m o n d 和b u r k e 等人开发的f a q f i n d e r 【2 ”，是 利用将文本信息源采取基于问题的自然语言来进行存取的，从而帮助用户在数 据库中获取其问题的相关答案。c r i s i s 研究了用短语、超链接和信息元素表 示文档内容，采用自动和非自动学习的分类算法，对文档进行聚类和分层分类。 f u m k r a n z 、j o a c h i m s 用词包和超级链接信息表示文档内容，采用规则学习算法 t f i d f ，对超级链接文档进行分类。m u s l e a ”等用词包、标识和词位信息表示文 档，采用规则学习算法，训练抽取规则。二是从数据库的角度进行研究。主要 是如何对w e b 数据库的半结构化的处理进行研究。其中，z a i a n e 和h a n 心副采用 关系数据库描述文本内容，引入面向对象的推理方法，试图建立起多层次数据 库模型，从而标准化文献标引。概括起来，无论是从i r 角度还是数据库角度研 究，都是为了解决文本的分析，规范化，从而使得可以用机器来处理文本分类 的问题，提高文本挖掘的效率。 九十年代以来，信息技术的空前发展，大量的各种信息内容在w e b 呈现几 何级数的增加，采用机器学习的方法来研究文本分类，成为文本分类的主流技 术。从机器学习技术的角度来研究文本挖掘，有两种方法。即基于内容的方法 和协同的方法。基于内容的方法从文本的整体内容着手，采用关键词匹配技术、 统计学习理论、租糙集技术、支持向量机技术，抽取文本内容的特征项。g o l d m a n 等人开发的m u s a g ”“，通过获取用户给出的关键词，在w e b 上搜索有关的文件， 系统产生出相关的同义词典，该词典用于文档获取时扩充给定的关键词集合， 实现词典库的动态增加。b a l a b a n o v i c 和s h o h a m 乜”开发的系统模拟一个用户学 习浏览i n t e r n e t ，在有限的时间里，选择最好的w e b 页，接受来自用户的请求。 2 同时，来自用户的反馈信息，作为更新检索方式以及选择相应的启发式方法。 l a n g 开发的用于电子新闻过滤n e w s w e e d e r ”5 1 系统利用文本学习，锝出用户的 兴趣模型，利用w e b 界面确保用户以通常的方式存取新闻，同时保证系统收集 用户的申请作为反馈。 l a m a c c h i a r 提出了i n t e r n e tf i s h “，是一类资源发现工具，用户从 i n t e r n e t 抽取有用的信息，系统包括一个具有一定约束的自然语言界面，只能 进行结构化的交互。系统也允许使用现有的搜索引擎帮助用户浏览。m a r k o g r o b e l n i k 等提出了基于y a h o o 利用贝叶斯分类器进行i n t e r n e t w e b 上的文本 分类的方法”。该方法仅用了少许的几个关键字作为特征向量，通过分析每个 字出现的概率，收集若干具有较高概率的特征字，以快速的分类文本。d u n j a m l a d e n i c 开发的p e r s o n a lw e b w a t c h e r 【2 ”系统可以看成是一个基于内容的个性 化处理助理。帮助用户来浏览w e b 。m i t c h e l l ”等人提出的c a l e n d e r a p p r e n t i e e ，可以帮助用户时序安排的喜好情况和有关出席会议的人员的个人 信息。利用这些规则可以对新的、还未进行时间安排的会议提供帮助信息。 1 2 2 国内的研究现状 相对于国外的研究情况，国内在文本分类的研究领域起步较晚。 由于中文文本的自身特点，中文的词与词之间没有像英文的单词之间用空 格来区分，因此，在进行中文文本分类之前，必须要对文本进行预处理即分词。 只有经过预处理后，将中文文本变成规范化的样本集合，通常表现形式为向量， 这样处理后的“文本”类型才能进行文本分类，随后的文本分类处理过程与英 文文本分类相同。因此，文本分类的一个热点就是研究如何利用中文文本自身 的一些特征来更好的表示文本，提高文本分类的效率和准确率。 由于国内的文本分类的研究起步晚，在很长的一段时间内都没有可供研究 的公开的中文文本分类的语料库，使得分类的结果难以进行比较。现在，关于 中文文本分类的语料库有很多，比如台湾师范大学的中文古文语料库，复旦大 学的中文文本语料库，北京大学建立的人民日报语料库和搜狐网发布的搜狗语 料库等等。 我国目前在文本挖掘系统的研究方面，取得了不小的进步，比较有影响力 的当属中国科学院计算所开发的汉语词法分析系统i c t c l a s ，现已公开发布供 中文文本分类的研究使用，清华大学研究的手写汉字识别( 动态匹配) 系统， 上海交通大学研制的语句语义、自然语言模型、构造语义解释模型等，哈尔滨 工业大学研制的自动分词和手写识别系统等等口1 。 1 3统计学习理论与支持向量机 统计学习理论( s t a r i s t i c a ll e a r n i n gt h e o r y ) 是一种研究有限样本下的 机器学习规律的理论。早在六、七十年代，v a p n i k 等人就开始致力于这方面的 3 研究，随着其理论的不断发展和成熟，到九十年代中期，统计学习理论开始受 到越来越广泛的重视。 v c 维概念( v cd i m e n s i o n ) 是统计学习理论的核心，它是描述函数集或学 习机器的复杂性或者说是学习能力的一个重要指标，在词概念基础上发展出了 一些关于统计学习的一致性、收敛性、推广性能等重要结论。 支持向量机方法是建立在统计学习理论的v c 维理论和结构风险最小原理 基础上的，根据有限的样本信息在模型的复杂性和学习能力之间寻求最佳折衷， 以期获得最好的推广能力。支持向量机方法的几个主要优点有： ( 1 ) 它是专门针对有限样本情况的，其目标是得到现有信息下的最有解而 不仅仅是样本数趋于无穷大时的最优值； ( 2 ) 算法时最终将转化为一个二次型寻优问题，从理论上说，得到是全局 最优解，解决了在神经网络方法中无法避免的局部极值问题； ( 3 ) 算法将实际问题通过非线性变换转到高维的特征空间，在高维的特征 空间中构造线性判别函数来实现原空间中的非线性判别函数，特征性能保证机 器有较好的推广能力，同时它巧妙地解决了维数问题，其算法复杂度与样本维 数无关。 目前，支持向量机算法在模式识别、回归估计、概率密度函数估计等方面 都有应用。在模式识别方面，对于手写体数字识别、人脸识别与人脸检测、以 及文本分类等各个领域。研究支持向量机在w e b 文本挖掘中的应用时本论文的 主要内容。 1 9 9 8 年，d o r t m u n d 大学的j o a c h i m s 报道了将s v m 用于文本分类的实验结 果，实验在r e u t e r s 和o h s u m e d 两个标准语准语料库上进行，在与贝叶斯、 r o c c h i o ，k 最近邻和决策树这四种分类方法的比较中，s v m 方法不仅取得了更 好的分类效果，还表现出了更强的鲁棒性和处理高维数据的优良特性。微软的 d u m a i s 和c a r n e g i em e l l o n 大学的y a n g 等很多学者也相继对此进行了研究， 并报道了相类似的结果。j o a c h i m s 对s v m 方法在文本分类中的应用进行了大量 深入细致的研究，取得了一系列的成果，并实现了一个简单有效的工具箱 s v m l i g h t 。该工具箱不仅被各国学者广泛使用，而且也非常适合解决文本分 类问题。 1 4 本文的研究思路及组织结构安排 本文认真研究分析了基于支持向量机的w e b 文本数据挖掘的基本原理和一 般方法，对支持向量机分类和w e b 数据挖掘的定义、相关技术以及国内外研究 现状进行了认真地归纳总结，并在此基础上对支持向量机分类算法进行了研究。 全文分为四章。 第一章是绪论，介绍了本课题的来源、目的和意义；基于w e b 的文本挖掘 4 技术的研究现状以及统计学习理论和支持向量机算法。 第二章介绍了w e b 数据挖掘的基本概念；探讨了基于w e b 的数据挖掘和传 统的数据挖掘的区别；并深入研究分析了w e b 挖掘的特点。 第三章阐述了w e b 文本挖掘的一些基本理论、w e b 文本挖掘的具体过程， 着重介绍了w e b 文本挖掘中的特征表示与特征提取技术，深入分析了它们的优 势与不足，并提出了一种新的类别区分词的特征选择方法，即基于语义引导的 特征选择方法。对文本分类的质量评估指标作了阐述。 第四章是机器学习、统计学习理论概述，介绍支持向量机的主要研究内容， 对两类线性可分和不可分的情况进行了深入的分析，采用了软化约束条件使得 线性不可分转化为线性可分。针对多类别的分类问题，总结了几种方法加以解 决。并就核函数的选取问题，及其在多类情况下应用产生的影响进行了讨论。 第五章运用支持向量机方法进行实验。对核函数的选取对文本分类的影响 进行了讨论，并详细讨论了在多项式核函数的参数的选取及其对分类效果的影 响进行分析和归纳。 第六章对本文进行了总结和展望。 5 2 1w e b 挖掘概述 第二章w e b 文本挖掘研究概述 2 1 1 数据挖掘简述 由于数据库技术的飞速发展所带来的各行各业的信息化程度的提高，产生 了大量的部门数据信息( 数据库) ，人们希望通过已有的数据可以分析得到有助 于决策的潜在的信息。建立在机器学习技术上的数据挖掘技术应运而生。数据 挖掘是建立在数据库、人工智能、统计学、可视化等多门学科的基础上。 数据挖掘( 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 yi n d a t a b a s e ，k d d ) 过程的一个环节，指从大型数据库或数据仓库中提取有效的、 潜在的、有应用价值的数据和知识的过程，它包括关联规则、聚类分析、分类 分析、模式序列、预测等。广义的数据挖掘是指在一些事实或观察数据的集合 中发现知识的决策支持过程。挖掘的对象不仅是数据库，也可以是文件系统， 或其它任何组织在一起的数据集合，如w w w 信息资源，甚至是数据仓库数据。 数据挖掘一般分为以下几个步骤： f 1 ) 数据收集 数据挖掘的处理对象是大量的已有的数据库中信息，寻找出已有的数据中 潜在的信息或是规律。因此，丰富的数据是数据挖掘的前提。因此，数据采集 是数据挖掘的前提，通常可以在数据库系统或是数据仓库中取出待分析的数据。 ( 2 ) 数据预处理 采集来的数据，往往是无规律的，一些数据或是数据的一些特征对挖掘的 过程来说是冗余的，而它们的存在会对挖掘结果的准确性产生较大的干扰，称 之为“噪声数据”。因此，必须要进行相关的处理，即数据清洗。将原始的数据 可能存在的“噪声”消除，比如数据可能存在自身的不一致性，或是缺失数据 等等，进而净化数据，为下一步的数据挖掘做好准备。 ( 3 ) 数据挖掘 通常有决策树( d e c i s i o nt r e e ) 、神经网络( n e u r a ln e t w o r k ) 、k n e a r e s t 近 邻、遗传算法、联机分析处理( o n l i n ea n a l y t i c a lp r o c e s s i n g ，o l a p ) 和关联规则 等方法。采用上述技术的某些专门的分析工具已经发展了大约十年的历史，不 过这些工具所面对的数据量通常较小。 f 4 ) 结果评估 针对不同的应用，会采取不同的挖掘技术，但是我们对数据挖掘的效果会 6 作出适当的分析，因为数据挖掘的结果有些是有实际意义的，而有些却是没有 多大实际的意义，甚至违背实际情况。这就需要进行结果评估。通常采用用户 的经验，也可以用实际数据来验证模型的正确性，进而调整数据挖掘模型，不 断重复进行数据挖掘。 ( 5 ) 决策分析 数据挖掘的目的是为人们提供数据中潜在的规律或是知识，因此，数据挖 掘出的知识将给人们的决策提供参考，是决策的依据之一。 2 1 2 什么是w e b 挖掘 1 w e b 挖掘的特点 w e b 已经成为信息发布、交互及获取的重要工具，它是一个巨大的、分布 广泛的、全球的信息服务中心。它涉及新闻、广告、消费信息、金融、管理、 教育、电子商务和其他许多信息服务。现代社会的竞争趋势要求对i n t e r n c t 上 大量产生和出现的信息进行实时、多角度、多层次的分析。虽然可以借助于强 大的搜索引擎，但是在分析和使用这些信息时面l 临许多的困难：首先查询信息 的查准率和查全率低，表现在返回很多不相关的结果和找不到相关的文档；其 次大多数搜索引擎仅仅用关键字查找，不具备机器学习和数据挖掘技术；最后， 不能了解用户的兴趣爱好，无法提供个性化的服务。由于w e b 是异质分布且不 断增长的信息系统，对其挖掘并不是上述技术的简单综合，它需要有新的模型、 体系结构和算法等。当今世界上研究的热门领域一一w e b 挖掘能直接或间接地 解决上述问题。w e b 挖掘是数据库、数据挖掘、人工智能、信息检索、自然语 言理解等技术的综合应用。 w e b 挖掘指使用数据挖掘技术在w w w 数据中发现潜在的、有用的模式或 信息。w e b 挖掘研究覆盖了多个研究领域，包括数据库技术、信息获取技术、 统计学、人工智能中的机器学习和神经网络等。 2 典型w e b 挖掘的处理流程如下【3 l ： ( 1 ) 资源发现：从w e b 中获取相关的信息，包括w e b 文件，电子邮件等多 种形式。 ( 2 ) 信息准备和预处理：对获取的信息进行必要的整理，剔除脏数据。 ( 3 ) 模式发现：自动进行模式发现，可以是同一个站点内部也可以在多个 站点之间进行。 ( 4 ) 模式分析：对挖掘的模式进行验证、解释。可以是机器进行，也可以 人一机交互进行。 3 w e b 挖掘面临的技术难点 和传统的数据库相比，w e b 上的信息具有动态、半结构化和相互的超链接 7 等特性。它能够以不同的形式表现并在全球范围内共享多个网页和平台。因此， 在w w w 上查询与从传统的数据库查询有明显的不同，比如，结构化的、静态 的关系数据库【4 1 。 ( 1 ) w e b 上的信息量十分庞大 2 0 世纪末，随着信息化程度的提高，i n t e r n e t 上的各种数据迅速激增，导 致了“信息爆炸，知识匮乏”。从广义的角度来说，w e b 上所包含了大量的各 种数据信息，是一个数据库。它是一个有大量的、相关的有用的信息结合，是 一个高度复杂性的数据库，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 b 这一庞大的数字数据库 中数据加以归类。由于w e b 中的信息并不像传统的数据库中按照一定的数据模 型建立起来的集合，因此，严格来说，w e b 不是一个数据库。由于w e b 的自身 的特点，各个信息页面之间结构关系复杂，存在着相互链接的结构关系，处理 w e b 的信息比起传统的文本文档复杂的多。主要有以下一些表现：w e b 的内容 组织没有同一的格式，没有任何规范的标题、摘要、内容以及文档的分类索引； w e b 的信息结构相互关联，可以通过一个页面链接到其他的页面中去，彼此在 结构上不是独立的，这和传统的满足范式的关系数据模型有着很大的差别。这 就是数据挖掘领域中所说的“半结构化数据”，它是介于结构数据化和完全无结 构的数据之间的数据形式，通常它们有以下一些特点：隐含的模式信息： 半结构化数据本身有着自己的组成结构，其中与数据混在一起。一个数据 集合可能由异构的元素组成；几乎没有严格的类型结构，缺乏对数据的严 格约束是其最明显的特点。 ( 3 ) w e b 的动态性极强 w e b 上的数据和信息处于不停地更新状态，比如新闻，股票，天气等都在 不断地更新着。链接信息和访问记录也在频繁地更新之中。由于w e b 信息源的 分布具有分散性，带来的每个信息源都在不停地增加、更新的信息，这就对挖 掘的要求具备自主学习或增量学习的能力，可以在一个开放的环境中学习。否 则，挖掘的效果会大打折扣，也没有太大的价值。 8 ( 4 ) w e b 用户群体的广泛性和兴趣的多样性 不同的用户有着不同背景、兴趣和使用目的。用户通常只对特定的一部分 信息感兴趣，而对其余的信息不关心，这就对挖掘的精确度提出了更高的要求， 否则，有用的信息淹没在大量的无用的信息中，将失去数据挖掘的意义。研究 得出，一个用户通常关注特定的信息内容，而且是相对稳定的。根据用户的习 惯，挖掘出相关的兴趣所在，将会有十分重要的意义。 ( 5 ) 对于w e b 上的信息有用性 w e b 上的信息，通常只有极少一部分是相关的或是有用的。据统计，有9 9 的w e b 信息相对9 9 的客户是无用的，如何从大量的无用的信息中准确地 找出所需的信息，具有很大的挑战。 2 2w e b 挖掘的分类 w e b 挖掘可以分为三类：w e b 内容挖掘( w e bc o n t e n tm 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 e a g em i n i n g ) 。 2 2 1w e b 内容挖掘 图2 - 1 w e b 挖掘的分类 w e b 内容挖掘是指从大量的w e b 页面描述数据中( 可以是文本、图像、音 频视频等) 发现信息并提取知识的过程。它包括从w e b 中发现资源，文档分类 和聚类，w e b 页面中的信息提取。文本挖掘是w e b 内容挖掘的核心。 1 w e b 页面内容挖掘 w e b 页面的内容可以有文本、图像等多种形式表现的数据信息，因此，按 照挖掘的内容来分，可以分为对t e x t 、h t m l 等文档的w e b 文本文档挖掘和对 i m a g e 、v i d e o 等多媒体信息的多媒体挖掘。对文本文档的挖掘，可以是对文本 文档的分类、聚类或是对文本文档内容的概括等，方法主要有基于a g e n t 的分 类器方法和建立数据库方法。对文本文档内容的挖掘，可以用于将文本分类， 9 这样归类的文本，可以提高信息检索的速度和效率。现有的搜索引擎技术就是 通过将w e b 中的信息进行整理分类，分为网页、文档、音频、视频等类别，最 新的搜索引擎也引入了w e b 2 0 技术，即加入了博客和论坛搜索。也可以是多 文本的内容分析，从而发现隐含在文本中的知识。多媒体挖掘关注于从单个多 媒体中提取具体的特征，其主要方法有关联规则、聚类分析等。 2 搜索结果挖掘 搜索结果一般以标题、内容摘要、链接、相似网页或网页快照等方式呈现 给用户，面对大量的搜索结果，其中有很多的信息并不是用户所需要的，搜索 的结果排序不是按照信息的重要性来排序的，往往出现用户所需要的结果并没 有呈现在搜索结果的排序比较靠前的位置，而呈现在搜索结果的排序靠前的并 不是用户所想要的结果。因此搜索的结果往往需要进行进一步的分析和处理。 一般地，对标题、内容摘要和链接信息等信息的研究是搜索结果挖掘关注的重 点，在h t m l 文件中，它们是以不同的标识来标记的，比如标题用“t i t l e ”，图片 用“i m a g e ”等表示，链接信息有“u r l ”来标识，因而可以通过字符串匹配的 方法查找这些标记，提取所需的标题、内容摘要和链接等信息，采用适当的统 计或是挖掘方法，来对结果进行挖掘。文献3 8 提出了一种加权的w e b 挖掘算 法，通过采用多种搜索引擎搜索的结果，为每一个搜索引擎设置一定的权值， 对结果作加权处理，从而搜索出相关性强的结果，过滤了相关性弱的搜索结果。 2 2 2w e b 结构挖掘 w e b 结构挖掘是从w w w 的组织结构和连接关系中推导知识f7 1 。和文本和 数据库不同，w e b 中有用的知识不仅仅局限于w e b 页面内容中，还包含在w e b 文档内部结构和w e b 页面间的链接结构中。因此，通过对这些文档结构和链接 结构的分析和挖掘，可以发现隐藏的未知的模式或知识。典型的w e b 结构挖掘 算法有p a g e r a n k 、h i t s 和h i t s 的改进算法，利用这些算法计算w e b 页面之 间的关联程度，可以提高搜索结果的准确性。 1 p a g e r a n k 算法【8 j 可以将w e b 看作一个有向图g = ( v ，e ) ，其中v 是页面的集合，e 是页 面之间的超链接结合。页面看作这个有向图中的顶点，页面之间的超链接抽象 化为图中的有向边。p a g e r a n k 算法的基本思想是，一个页面被多次引用，则这 个页面很可能是重要的；一个页面尽管没有被多次引用，但被一个重要页面引 用，则这个页面很可能是重要的；一个页面重要性被均分，被传达到它所引用 的页面。描述为：u 是一个w e b 页面，职m ) 是页面的等级值，链向页面u 的 集合为r o ) ，页面了 ( f ) 链出的链接数量设为c ( z ) ，则u 的重要性为： p r ) 一o - p ) + p ( p r ( r o c ( r o + + p r ( 瓦) c ( 瓦) ) 一( 1 一p ) + 芝：王。p r ( z ) c ) 其中，p 为阻尼系数，在0 到1 之间取值，即以概率p 随机取w e b 上的任一页 面；1 - p 则是页面本身所具有的网页等级值。著名的网络搜索引擎g o o g l e 应用 了该算法，其网页等级值是采用了一种近似迭代的方法，即先给每个网页赋予 个初值，然后利用上面的公式，循环进行有限次运算得到近似的网页等级值。 据b r i n 和p a g e 的研究表明，进行大约1 0 0 次的迭代才可以得出互联网上整个 网页的等级值。 2 h i t s 算法 h i t s ( h y p e r l i n k - - i n d u c e dt o p i cs e a r c h ) 算法是k l e i n b e r g 在1 9 9 8 年提出 的，是利用h u b a u t h o r i t y 的方法提出的。一个h u b 是指一个或多个w e b 页面， 它提供了指向权威页面的链接集合，它本身可能不突出，甚至没有几个链接指 向它。但是，由于好的h u b 指向许多好的权威的页面，h u b 与a u t h o r i t y 之间的 这种关系决定了它可以发现权威页面和高品质w e b 结构和资源。h i t s 算法如 下： ( 1 ) 将查询q ( q u e r y ) 提交给普通的面向相似度的搜索引擎，从搜索的结 果中提取前n 个页面作为根集，用s 表示。 ( 2 ) 通过向s 中加入被s 引用的页面和引用s 的页面，将s 扩展成一个更 大的集合t 。 ( 3 ) 对t 中的每个页面p 赋予一个非负的h u b 值和非负的a u t h o r i t y 值，分 别记为h ，a 。将a 和h 的初始值设为同一常数，比如令其都为1 ，则h u b 与 权威的权重可按如下公式进行迭代计算： 矿。满， 铲带。 该算法输出一组具有较大h u b 加权值的页面和具有较大a u t h o r i t y 加权值的 页面。但是，如果h u b 页面的内容包含为多个主题时，由于h i t s 忽略了文本 内容，对此常常显得无能为力。必须对算法作适当的改进，比如将h u b 页面分 成多个小的单元，对小的单元进行权重的分析，从而综合计算它们的h u b 值。 2 2 3w e b 使用挖掘 w e b 使用记录挖掘是指利用数据挖掘技术分析用户访问w e b 的日志记录， 挖掘用户访问w e b 模式，预测用户浏览行为。用法( u s a g e ) 分析f 9 】包括简单 统计，比如网页访问频率，也包括更复杂形式的分析，比如发现在网页中转换 的路径。但是w e b 挖掘中大多数的工作，集中在w e b 日志分析。w e b 日志分 析主要有用户和s e s s i o n 的识别，用户访问的系列网页。从而识别出网站的潜在 用户，为客户提