（计算机应用技术专业论文）潜在语义分析在互联网数据挖掘中的应用研究.pdf

潜在语义分析在互联网数据挖掘中的应用研究 摘要 互联网搜索现已成为人们学习和生活中必不可少的一部分，互联网知识的合 理组织、互联网知识的快速有效地获取、对互联网链接结构的挖掘以及信息系统 的个性化推荐都会在很大程度上影响互联网用户的使用体验。同时，信息爆炸式 的增长已经使大量互联网用户迷失在知识的海洋。因此，对互联网数据进行挖掘 对于改善人们的学习和生活具有重大的现实意义。 本文介绍了互联网数据挖掘的研究现状，重点论述了互联网链接结构挖掘和 使用挖掘，同时在深入剖析了潜在语义分析技术的数学模型和实现原理的基础上， 提出了两个算法：基于潜在语义分析的h i t s 改进算法以及基于潜在语义分析的 个性化推荐算法。文章给出了改进h i t s 算法的具体描述，深入分析了算法的参 数设置、实现、时间空间复杂度以及实验结果；对新提出的个性化推荐算法也从 算法描述、算法系统框架、算法评价指标、算法实验等多方面作了深入的分析。 接着利用对比实验验证了改进h i t s 算法在性能上的提高以及新提出的个性化推 荐算法性能。本文最后给出了原型系统的设计。系统设计不仅考虑了系统功能的 实现细节，同时也考虑了系统的可扩展性、可维护性以及对已有代码的重用。 实验结果表明，改进的基于潜在语义分析的h i t s 算法与原算法相比，有更 高的查全率和时间效率，且算法返还的搜索结果总体上更加权威、更有参考价值： 基于潜在语义分析的个性化推荐算法通过提供合理的推荐策略，在低维用户语义 空间和低维资源空间中挖掘用户与用户、资源与资源之间的相似度，实现的个性 化推荐系统在实验样本不太大的情况下，表现出较理想的推荐性能。 综上，本文提出的改进h i t s 算法与个性化推荐算法在潜在语义分析技术的 支持下，不但提高了时间效率，而且由于加入了基于数学统计的“语义”支持， 算法可以在低维的语义空间上进行信息处理，既提高了算法的空间效率，又提高 了算法信息处理的准确度。 关键词：互联网搜索；潜在语义分析；奇异值分解；t s 算法；个性化推荐 硕l j 学位论文 a bs t r a c t i n t e r n e ts e a r c hh a sn o wb e c o m ea ni n d i s p e n s a b l ep a r ti np e o p l e ss t u d ya n dl i f e r e a s o n a b l eo r g a n i z a t i o na n df a s ta n de f f i c i e n ta c c e s st ot h ei n t e r n e tk n o w l e d g e ， m i n i n go ft h ei n t e r n e t l i n ks t r u c t u r e ，a n dp e r s o n a l i z e dr e c o m m e n d a t i o no ft h e i n f o r m a t i o ns y s t e ma l la f f e c t ，t oal a r g ee x t e n t ，t h ei n t e r n e t u s e r s s e a r c h i n g e x p e r i e n c e m e a n w h i l et h ee x p l o s i v eg r o w i n go fi n f o r m a t i o nt o d a yh a sm a d eal a r g e n u m b e ro fi n t e r n e tu s e r sl o s ti nt h eo c e a no fk n o w l e d g e t h e r e f o r e ，i n t e r n e td a t a m i n i n gi so fg r e a tp r a c t i c a ls i g n i f i c a n c ei ni m p r o v i n gp e o p l e ss t u d ya n dl i f e t h ep r e s e n ts t u d yi n t r o d u c e dt h er e s e a r c ho ni n t e r n e td a t am i n i n g ，e s p e c i a l l yt h e l i n ks t r u c t u r em i n i n ga n du s em i n i n g w ea l s oa n a l y z e di nd e p t ht h em a t h e m a t i c a l m o d e la n dt h er e a l i z a t i o np r i n c i p l eo ft h el a t e n ts e m a n t i ca n a l y s i s ( l s a ) t e c h n o l o g y b a s e do nt h er e s e a r c ho fi n t e r n e td a t am i n i n g ，t h ep r e s e n ts t u d yp r e s e n t e dt w o a l g o r i t h m s ：t h ei m p r o v e dl s a - b a s e dh i t sa l g o r i t h ma n dt h el s a - b a s e dp e r s o n a l i z e d r e c o m m e n d a t i o na l g o r i t h m w em a d ed e e p a n a l y s e so ft h ed e s c r i p t i o no ft h e i m p r o v e dh i t sa l g o r i t h m ，i t sp a r a m e t e rs e t t i n ga n dr e a l i z a t i o n ，t h et i m ea n ds p a c e c o m p l e x i t y ，t h er e s u l t so ft h ee x p e r i m e n ta n ds oo n w ea l s od e e p l ya n a l y z e dt h e n e w l yp r o p o s e dp e r s o n a l i z e dr e c o m m e n d a t i o na l g o r i t h mi ns e v e r a la s p e c t ss u c ha st h e d e s c r i p t i o n ，t h es y s t e ma r c h i t e c t u r e ，t h ei n d e x e so ft h ea l g o r i t h mp e r f o r m a n c e ，a n d t h ee x p e r i m e n to ft h ea l g o r i t h m a n dt h e n w i t ht h e h e l p o fs e v e r a lc o n t r a s t e x p e r i m e n t s ，t h ep e r f o r m a n c eo ft h et w oa l g o r i t h m sh a sb e e ne v a l u a t e d f i n a l l y ，w e p r e s e n t e dt h es y s t e md e s i g no fo u rw o r k t h ed e s i g np r e s e n t e dt o o ki n t oa c c o u n tn o t o n l yt h er e a l i z a t i o nd e t a i l so ft h es y s t e mf u n c t i o n s ，b u ta l s ot h es c a l a b i l i t ya n d m a i n t a i n a b i l i t yo ft h es y s t e m ，a n dt h er e u s eo ft h ee x i s t i n gc o d e t h ee x p e r i m e n t a lr e s u l t ss h o w e dt h a tc o m p a r e dw i t ht h eo r i g i n a la l g o r i t h m ，t h e i m p r o v e dl s a - b a s e dh i t sa l g o r i t h mh a dab e t t e rr e c a l lr a t i oa n dm o r ef e a s i b l et i m e e f f i c i e n c y ，a n dt h er e s u l t sr e t u r n e db yt h ei m p r o v e dh i t sa l g o r i t h mw e r eg e n e r a l l y m o r ea u t h o r i t a t i v ew i t hm o r er e f e r e n c ev a l u e w ea l s o e m p l o y e dt h el s a b a s e d p e r s o n a l i z e dr e c o m m e n d a t i o na l g o r i t h mt om i n et h es i m i l a r i t yb e t w e e nu s e r sa n d u s e r s ，a n db e t w e e nr e s o u r c e sa n dr e s o u r c e si nl o w - d i m e n s i o n a ls e m a n t i cs p a c ea n d l o w d i m e n s i o n a lr e s o u r c es p a c e t h r o u g hr e a s o n a b l er e c o m m e n d a t i o ns t r a t e g i e s ，w e f o u n dt h a tt h ep e r s o n a l i z e dr e c o m m e n d a t i o ns y s t e mr e a l i z e dt h r o u g ht h el s a b a s e d p e r s o n a l i z e d r e c o m m e n d a t i o n a l g o r i t h ms h o w e df a i r l y i d e a lr e c o m m e n d a t i o n i i i 潜在语义分析在互联网数据挖掘中的应用研究 p e r f o r m a n c e ，w h e no u re x p e r i m e n ts a m p l e sa r en o tv e r yl a r g e i ns h o r t ，w i t ht h es u p p o r to fl s a ，t h et i m ee f f i c i e n c yo ft h ei m p r o v e dl s a b a s e d h i t sa l g o r i t h ma n dt h el s a b a s e dp e r s o n a l i z e dr e c o m m e n d a t i o na l g o r i t h mh a sb e e n i m p r o v e d ，a n db e c a u s eo ft h es t a t i s t i c s b a s e ds e m a n t i cs u p p o r t ，t h e yc a nd e a lw i t h i n f o r m a t i o np r o c e s s i n gi nl o w - d i m e n s i o n a ls e m a n t i cs p a c e ，n o to n l yh a v i n gi m p r o v e d t h es p a c ee f f i c i e n c yo ft h ea l g o r i t h mb u ta l s ot h ea c c u r a c yo fi n f o r m a t i o np r o c e s s i n g k e yw o r d s ：i n t e r n e ts e a r c h ；l a t e n ts e m a n t i ca n a l y s i s ；s i n g u l a r v a l u ed e c o m p o s i t i o n ；h i t sa l g o r i t h m ；p e r s o n a l i z e dr e c o m m e n d a t i o n 硕l ：学位论文 图2 1 图2 2 图2 3 图2 4 图2 5 图2 6 图3 1 图3 2 图3 3 图3 4 图3 5 图4 1 图4 2 图4 3 图4 4 图5 1 图5 2 图5 3 图5 4 图 图 图 图 插图索引 搜索引擎原理图4 矩阵奇异值分解1 5 “词汇文档矩阵a 的奇异值分解图1 5 文本集合的语义空间1 8 二维文本语义子空间1 8 加入一个文本重新计算后的语义子空间1 9 “词汇文档 矩阵2 l 大型链接邻接矩阵的奇异值分解一2 2 改进h i t s 算法系统框架2 4 改进h i t s 算法与g o o g l e 搜索结果统计对比一2 7 原h i t s 算法与g o o g l e 搜索结果统计对比一2 8 个性化推荐系统框架图3 4 “用户资源”矩阵分解后的u 矩阵3 6 “用户资源 矩阵分解后的s 矩阵3 8 “用户资源 矩阵分解后的v 矩阵3 8 搜索引擎子系统的系统框架图4 3 个性化推荐子系统系统框架图一4 4 h i t s 算法类图框架4 4 s v dh i t s 委托h i t s 子类实现g e t r o o t 函数4 5 s v dh i t s 排序引入了潜在语义分析4 5 c o n t r u c t m a t r i x 的类图4 5 个性化推荐模块的系统类图框架4 6 改进h i t s 算法与原h i t s 算法时间效率对比4 8 v i i 潜在语义分析在互联网数据挖掘中的应用研究 附表索引 表2 1用户资源矩阵1 l 表2 2 小规模的“词汇文本 矩阵1 7 表2 3十二个文本对应的“词汇文本 矩阵1 8 表2 4 四个语义相似度高的文本一1 9 表2 5m a t l a b 提供的三个用于矩阵的奇异值分解的函数2 0 表3 1改进h i t s 算法查找“s v d 排前2 0 的资源列表。3 9 表4 1“用户资源”矩阵3 7 表4 2 资源矩阵的语义子空间3 9 表4 3用户矩阵v 的语义子空间4 0 表4 4 新的推荐算法推荐给用户7 的资源以及推荐指数4 0 表4 5其它用户与被推荐用户的相似度表4 0 表4 6 资源2 1 的相似资源列表4 0 表5 1利用g o o g l e 查找“s v d 排前2 0 的资源列表4 9 表5 2利用原h i t s 算法查找“s v d 排前2 0 的资源列表5 0 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献 的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法 律后果由本人承担。 作者签名：矗细勰 日期1 年6 月各日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被 查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编 本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“”) 作者签名：废名j 挥 刷磁孙劫、氓 日期：小q 年6 月3 日 日期：即年石月8 日 硕士学位论文 第1 章绪论 1 1 研究背景与意义 互联网搜索是一个蓬勃发展的行业，同时它还存在很多的问题。我们正处于 信息爆炸的时代，信息使得人们可以更好地去了解身边的世界。与此同时，人们 真正可以有效利用的信息似乎已经相对减少，并且很多时候，互联网用户不得不 花大量的时间去从海量的数据中找出那些可能对自己有用的信息，这使得人们迷 失在知识的海洋。 互联网搜索旨在为用户快速提供用户所需要的有效信息，而用户只需向信息 系统输入其所需信息对应的主题。这要求该信息系统具备“理解 用户意图的能 力，同时它还应该“知道”互联网文档的内在含义，并能自动地为与用户所需主 题相关的大量信息进行排序，只有这样，系统才能使用户在知识的海洋中游刃有 余。 本文深入研究了潜在语义分析技术的原理以及实现，并将这种技术融入到互 联网链接结构挖掘当中。潜在语义分析技术的引入使得现有的信息系统可以在一 定程度上“理解 网页内容，同时自动获取词语间的语义关系，并将词语和文档 以某种可计算性和可操作性高、在某种程度上代表其语义的形式表示和存储。这 样就可以为互联网用户高效地提供其最需要的信息，而不仅仅是“表面 上的相 似。这种改进可以在很大程度上提高用户的搜索体验，因而具有实际的意义。 此外，电子商务迅猛发展的今天，对潜在用户挖掘的质量是电子商务盈利的 一个很关键的因素。因而互联网搜索中使用的挖掘成为了当前研究的热点，且将 在很大程度上推动互联网经济继续向前发展。 1 2 本文研究工作及章节安排 现在的主流搜索引擎采用的搜索技术都是基于词汇上的表层匹配，这样的技 术存在一些弊端。它们所利用的“关键字”仅仅是出现在网页中的符号，这些“关 键字对应的语义并没有被使用；同时，互联网链接结构分析所依据的存在于页 面之间的链接结构，也不能表示这些页面本身内在的含义。这就决定了当代搜索 引擎还不能较好地处理页面的语义信息，因此，目前搜索引擎出现了一系列的技 术难题。例如如果用户提交的关键词不能很好地反映用户的意图，信息系统不能 与用户进行良性的交互等。 互联网搜索中使用挖掘的研究也还没有成熟，虽然其理论模型多种多样，且 涝确j 语义分析存互联网数据挖掘中的应用研究 各有优点，但它们对用户日志的分析效果都还不尽如人意，从而不能得到广泛的 应用。本文将从语义层面来分析互联网搜索中使用的挖掘的理论模型和实现，意 在实现一个可行的互联网搜索个性化推荐算法。 本文把潜在语义分析的技术创造性地融合到互联网数据挖掘算法中，并且提 出了对应的算法，同时给出了它们的实现，最后通过实验的方法来验证算法的有 效性。 本文工作主要体现在以下几个方面： 1 深入研究潜在语义分析技术的理论模型、技术特征以及其适用的领域。分 析潜在语义分析在优化互联网数据挖掘中应用的可行性，给后面的研究以理论上 的支持。 2 深入研究基于互联网链接结构分析的搜索排序算法，重点剖析h i t s 算法。 在此基础上，引入潜在语义分析技术，提出一种改进的基于潜在语义分析的h i t s 算法。 3 对获取的用户搜索日志进行建模，同时结合潜在语义分析技术，对用户日 志进行智能分析，得出用户搜索的内在规律，“推断”并推荐其可能感兴趣的主 题，从而为互联网搜索用户提供个性化的服务。 4 给出了原型系统相关模块的设计。设计不仅会考虑到系统的功能实现，同 时也对系统的可扩展性和可维护性作了充分的考虑。 本文的组织结构如下： 第一章潜在语义分析在互联网数据挖掘中的应用的研究背景、意义和待研究 的问题，给出了论文的主要研究内容以及文章的组织结构。 第二章首先对互联网搜索的发展进行了一定的总结，然后论述了互联网数据 挖掘的研究现状，接着介绍了潜在语义分析技术的数学模型和具体实现，为后文 的研究工作提供了理论支持。本章最后给出了m a t l a b 在矩阵奇异值分解中的 应用。 第三章主要是结合潜在语义分析技术改进h i t s 算法，并且用实验验证改进 算法在性能上的提高。 第四章对搜索引擎用户使用日志进行了建模，并结合潜在语义分析技术，对 用户日志进行智能分析。通过计算用户与用户、资源与资源之间的相似度，结合 适宜的推荐策略，实现了一种全新的基于潜在语义分析的个性化协同推荐算法。 第五章给出了本文原型系统的设计。 最后是对本文的总结及对今后工作的展望。 硕l ：学位论文 2 1 引言 第2 章互联网数据挖掘相关技术概述 我们处于信息迅猛发展的年代，信息的有效表达和快速获取在很大程度上影 响着当代人的学习与生活。在搜索引擎出现之前，互联网用户使用h t m l 语言 把信息分布在w w w 上，而其它用户在互联网上查找信息时，通常只能沿着一个 进入点一个用u r l 标识的网页一一出发去访问其他的网页。在互联网规模较 小时，这种随机漫步的浏览方式可以较为有效地满足用户的要求。随着互联网规 模快速变大，这种查询方法使浏览者如同置身于页面内容的海洋中。这种手工查 找的方式在时间效率上和所获取互联网内容的用户满意度来说都不尽人意。为便 于获取信息，部分信息提供者将手工搜集到的多个网页链接编制成到单个h t m l 文件，其它用户便可以按照某种顺序一如主题、地域、时间等一进行浏览。随着 互联网规模爆炸式增大，在信息的海洋中单纯依靠人力搜集与组织信息，效率非 常低而且难免出现差错。同时，随着用户的使用要求慢慢地提高，更快捷地找到 所需的网页信息成为w w w 用户的迫切需要。一种全新的信息服务系统应运而生， 这种信息服务系统能够在较短时间内在w w w 上获取与用户所需主题相关的网页 集合，并且对该集合进行一定规则下的排序。当用户查询时，它可以较为快速、 准确而又全面的得到用户所需要的信息。这种信息服务系统就是现今广泛使用的 互联网搜索引擎。 为了更好地为用户提供更优质的服务，对互联网搜索进行挖掘也很有必要。 比如对搜索结果进行分类、聚类处理，从而便于用户找到更多类似的搜索结果； 对互联网链接结构进行分析，从而找出网格中的特殊点：它或者很权威或者指向 了很多权威的节点：对用户的搜索日志进行分析以便发现用户潜在的兴趣或为用 户推荐一些其可能感兴趣的网页、服务。所有的这些都可能为网络经济的快速发 展注入新的推动力。 2 2 国内外文献综述 2 2 1 互联网搜索引擎 2 2 1 1 互联网搜索引擎的原理 搜索引擎的原理图如图2 1 所示。 潜在语义分析稚：互联网数据挖掘中的戍用研究 图2 1 搜索引擎原理图 现在流行的搜索引擎几乎都是由搜索软件、索引软件和检索软件三部分组成。 它的基本原理是：首先从互联网上抓取网页，然后对其建立本地索引，再根据不 同的查询排序算法对用户提供的“输入”按一定的顺序给出一系列的w e b 信息 的集合。 搜索软件用来从互联网上抓取网页，它利用能够从互联网上自动收集网页的 系统程序，如r o b o t ( 机器人) 、s p i d e r ( 蜘蛛) 等，自动访问互联网，并沿着任何网 页中的所有u r l 爬到其它网页，重复这过程，并把获取的所有网页收集回来。这 个过程通常有两种策略：第一种是每次爬取一个站点；另一种是按一定的搜索算 法一如广度优先搜索与深度优先搜索一遍历整个互联网上的网页。这些网页信息 主要由正文、题名、摘要、关键词和u r l 组成。 索引软件则是用来为从互联网中获取的网页信息建立本地的索引数据库。搜 索引擎的“网络机器人”或“网络蜘蛛 是一种网络软件，它可以遍历w e b 空间， 扫描一定i p 地址范围内的网站，并沿着网络上的链接从一个网页到另一个网页， 从一个网站到另一个网站采集网页资料。它可以保证采集的资料是最新的，也会 回访已抓取过的网页。网络机器人或网络蜘蛛采集的网页，还要有其它程序进行 分析，根据一定的相关度算法进行大量的计算建立网页索引，才能添加到索引数 据库中。有的信息系统对互联网内容进行全文索引，即对页面中出现的每个单词 进行标引，如a l t a v i s t a ：有的根据网页的标题、人名、地名及网页前2 5 到1 0 0 个词进行标引，如l y c o s e 。 检索软件则是用来当用户输入提问式后，从索引数据库中搜索与提问式主题 相关度最高的互联网内容，并对它们的相关度进行一定的排序。真正意义上的搜 索引擎，通常指的是收集了因特网上几千万到几十亿个网页并对网页中的每一个 4 硕 ：学位论文 关键词进行索引，建立索引数据库的全文搜索引擎。当用户查找某个关键词时， 所有在页面内容中包含了该关键词的网页都将作为搜索结果被检索出来。在经过 复杂的算法进行排序后，这些结果将按照与搜索关键词的相关度高低，依次排列。 当然，为了提高用户的搜索体验，现有的大多数的搜索引擎都会对用户的使 用情况进行一定的挖掘，从而从侧面获知用户的偏好，以便可以为用户以后的使 用提供更多的优质服务。 2 2 1 2 互联网搜索引擎的性能评价标准 通常说来，搜索引擎的性能评价标准主要包括：查全率查准率、收录范围、 检索功能、结果组织显示、时间效率、人机界面几个方面【l ，2 】： 1 查全率、查准率 查全率是指检索系统检出的与查询主题相关的文献量和系统文献库中与查询 主题相关的文献总量的比率，即：查全率= 检出相关文献量文献库内相关文献总 量；查准率是指所检出的与查询主题相关的文献占所有检出文献的比率。查全率 和查准率是衡量检索系统检索性能的两个最重要的指标，它们可以反映一个检索 系统的基本检索效果。 2 收录范围 搜索引擎按领域可以分成综合型搜索引擎与面向特定领域的搜索引擎。不同 类型的搜索引擎有其特定的收录对象，比如说面向教育领域的搜索引擎收录的对 象主要是与教育相关的文献。选择搜索系统必须先对该搜索引擎简单了解，知道 它是面向特定领域的搜索引擎还是综合型搜索引擎。若是面向特定领域的搜索引 擎，则要了解它面向的是哪个领域；而综合型的搜索引擎则通常覆盖了很多的领 域，通用但是领域化程序不高。 3 检索功能 每种搜索引擎所提供的检索功能虽略有不同，但大致包含布尔逻辑、词组查 询、相近检索、限制字段等功能，或进一步提供相似性反馈信息、关键词检索、 自然语句输入等较先进的功能。 4 检索结果的组织、显示 检索结果的组织也会在很大程序上影响用户的检索体验。对检索的结果按一 定的逻辑进行分类通常可以减少用户对信息的筛选过程。通常信息不是太少，而 是过多。现有的大多数的商用搜索引擎都是根据资源与查询的相关性来排序，最 相关的资料就会排在前面，有些系统允许用户自定义资料显示的数量，可节省查 询和浏览的时间；另外显示资料的详细程度也会影响资料的参考价值。 5 时间效率 搜索引擎的反应时间对于商用互联网搜索引擎来说是至关重要的，这项指标 潜在语义分析在互联嘲数据挖掘中的心用研究 直接影响到用户的搜索体验。在信息高速发展的现在，人们无法忍受输入提问式 后在显示器前“漫长的等待：相反，如果用户在输入提问式后信息可以“立即 给出反馈，用户体验会相对好些，即使在很多时候系统给出的答案并非用户真正 所需要。 6 人机界面 软件的易用性对于软件的生命力来说相当重要，其中很重要的一点就是人机 交互界面的设计，它也是评价搜索引擎性能的一个很重要的指标。没有易用的人 机交互界面，即使查询系统功能再多再强，也可能无法吸引大众使用。界面要简 单大方，并提供辅助说明或系统特性介绍。 2 2 1 3 互联网搜索引擎的发展趋势 搜索引擎发展到现在其功能已经非常强大，它从文字搜索发展到对文字、图 片、视频等信息整合的功能。随着互联网信息的爆炸式增长，未来的信息检索系 统要处理的不是当用户输入提问式后得到很多的看似相关的结果，而是少量的对 用户真正有参考价值的网页集。 g o o g l e 公司是现在公认的世界上最成功的互联网搜索引擎公司，现任谷歌 全球副总裁李开复在博鳌亚洲论坛年会时表示，互联网搜索引擎未来发展有三大 趋势，分别为：移动化、个性化、智能化【3 1 。 移动搜索引擎：目前手机的普及率和伎用率都要比个人电脑高，移动搜索将 迅速发展。实际上不仅是手机，未来电视、汽车等所有能上网的产品都将具有搜 索功能。只有如此才能从海量信息中得到少数真正需要的信息。 个性化搜索引擎：它能够让人依照不同的个性化需求调整搜索的结果，例如 可以选择时间排序、重要性排序或者地域性排序等排序方式，找到令人满意的搜 索结果；同时还可以通过对用户的搜索日志进行挖掘，为用户推荐其感兴趣的商 品和服务。 智能化搜索引擎：智能特性是未来互联网搜索引擎发展的一个方向标。有了 智能特性，互联网用户的搜索体验会大大的提高。比如某一天对搜索引擎说“送 母亲一束花 ，它就能善解人意地把花买了并送到目的地，用户无需向服务提供 商提供详细的用户个人信息以及了解交易、寄送的过程。李开复表示，现在“谷 歌生活搜索已经有了一部分这种功能，在不久的将来这种搜索引擎将会投入商 用。 总之，搜索引擎发展的动力在于为互联网搜索用户提供最好的搜索体验，随 着用户的生活水平、搜索服务要求不断提高，搜索引擎必然会朝着更人性化的方 向发展。 6 硕l j 学位论文 2 2 2 互联网链接结构挖掘 随着社会的信息化推进，公司、政府及个人越来越多地在互联网上发布和获 取信息。w e b 已经成为信息制造、发布、加工和处理的主要平台。传统的互联网 应用技术大多是基于文档内容的，与经典的信息检索技术和数据库技术有着密切 的联系。但是，互联网中特有的许多问题，诸如超大规模的非结构化文档数量、 良莠不齐的网页质量、包含在文档中的大量多媒体信息，甚至相当含糊或不规范 的用户查询表示等，都使得经典的信息检索技术和数据库技术在互联网环境中很 难有效地应用。 同时，互联网的超链接拓扑结构体现了网络资源间的相互认可。链接的指向 反映了网页创建者的一种判断：如果网页a 存在一条超链接指向网页b ，那么网 页a 的作者是认为网页b 包含了有价值的信息，并且很多时候，这两个网页具有 相似的主题。因此，充分利用互联网的链接结构信息对互联网应用技术的研究将 具有极为重要的意义。 第三代搜索引擎引入了链接分析的概念，对互联网链接结构作了深入的分析， 从而使搜索排序实现了自动化。p a g e r a n k t 4 1 和h i t s 算法【5 1 是其中的两个最著名的 搜索排序算法。它们的原始模型都存在缺陷，基于这两种算法原形产生了很多的 改进算法。 2 2 2 1h i t s 算法 h i t s 算法是一种基于主题的互联网链接分析技术，它的广泛应用在于它对网 络结构的合理描述。在h i t s 算法【5 1 模型中，k l e i n b e r g 提出了权威性网页( a u t h o r i t y ) 和中心性网页( h u b ) 的概念。互联网上一个广义的主题包含有大量显著的权威性网 页，这些权威网页从链接结构的角度来看应该是被大量的超链接所指向的，也可 以说是被大量的网页作者所认可；而中心性网页则指向多个主题相关的权威网页。 k l e i n b e r g 认为搜索开始于用户的检索提问，每个页面的重要性也依赖于用户的检 索提问。应该注意的是，每个页面也有两个权值，即h u b s ( 中心值) 和a u t h o r i t i e s ( 权 威值) ，其中a u t h o r i t y 值表示与给定查询主题的相关的网页的权威性，而h u b 值 则是表示它包含有很多与给定查询主题的相关的权威网页的链接。a u t h o r i t i e s 依 赖于所有指向它的页面，而h u b s 依赖于所有它所指向的页面。h i t s 算法的目标 就是通过一定的迭代计算得到针对某个检索提问的最具价值的网页，即排名最高 的网页。 k l e i n b e r g 用图来表示链接关系，可以认为页面的集合v 为一个有向图g = ( v ， e ) ，图中的每一个节点对应一个网页。有向边( p ，q ) e 表示网页p 链接指向网 页q ，节点p 的出度( o u t - - d e g r e e ) 指节点p 链出的网页数量，而节点p 的入度 ( i n - - d e g r e e ) 贝, l j 指的是链接指向节点p 的网页数量。 7 潜拍! 语义分析在互联网数据挖掘中的应用研究 h i t s 算法可以归纳为以下几个步骤【6 1 ： ( 1 ) 用户给定查询关键词，以此得到r 个相似度最高的网页集作为根集r ； ( 2 ) 通过将从根集链出指向的网页集与指向根集的网页集包含进来，可以将根 集r 的规模进行扩展，形成扩展集s ； ( 3 ) 通过扩展集推导出一个网络邻接子图g ( s ) 。 ( 4 ) 将根集s 构造为n 1 1 的邻接矩阵a 及其转置矩阵a t ，计算a t a 的最大特 征值入l ，并将入1 所对应最大特征值的主特征向量e l 进行归一化； ( 5 ) 将经过归一化后的特征向量e 1 中具有较大绝对值的元素作为a u t h o r i t i e s 返 回； ( 6 ) 计算a a l 的最大特征值入l ，并将入l 所对应最大特征值的主特征向量e 1 进 行归一化： ( 7 ) 将经过归一化后的特征向量e 1 中具有较大绝对值的元素作为h u b s 返回。 多数情况下，h i t s 算法的主题查询能够较为准确地得出与主题相关的网页集 合，但在某些场合中算法会发生严重的“主题漂移的现象【7 1 ，即有些网页对于特 定的检索，虽然其主题与查询主题无关，但却具有较高的a u t h o r i t y 值。这是h i t s 算法固有的缺陷，很多研究给出了改进的算法。其中大多数的改进是基于网页内 容和链接文本【7 1 0 】；也有的是改变算法的粒度，而不是以单个网页之间的链接来 衡量网页的权威性，从而提高链接结构分析的有效性，进而提高权威页面搜索的 效率【1 1 13 1 。 d e n gc a i 与x i a o f e ih e 1 4 】等人对上述的主题漂移作了更深入的分析，指出： 单个网页其实包含了多个语义块，即多个主题区域。从语义的角度对互联网链接 结构重新审视，可以发现一个网页的相同语义块中的链接通常会指向相同主题的 网页。自然可以想到，在互联网链接分析中，选择语义块作为最小粒度会更为合 理。 d e n gc a i 与x i a o f e ih e 等人对h i t s 算法作出了改进，但同时也引入了大量 额外的计算量，如对页面的分块。更坏的情况是网页d o m 树形结构下同一个结 点下的链接并非都具有相同的主题。 b w u 与b d d a v i s o n t l 5 1 对h i t s 算法中的产生的s p a m 网页的去除作了相 关的研究，提出了相关的算法并验证了其有效性。 2 2 2 2p a g e r a n k 算法 p a g e r a n k 算法是最早并且最成功地将链接分析技术应用到商业搜索引擎中 的算法。 l p a g e 等给出p a g e r a n k 的简单定义：令u 为一个网页，n ( u ) 表示从网页v 向外的链接数目，b ( u ) 表示链接到网页u 的网页集合，r ( u ) 表示网页u 的 8 硕j ：学位论文 p a g e r a n k 值，c 为规范化因子，作用是保证所有网页的p a g e r a n k 总和为常量。 例如为保证总的p a g e r a n k 值为l ，可以通过网页p a g e r a n k 总和的倒数求得。如 公式( 2 1 ) 所示。 r 0 ) = c 尺( v ) ( v ) ( 2 1 ) v e 曰扣j 为了更加容易地理解p a g e r a n k 的定义，可以用非常直观的模拟冲浪模型来 进行解释【1 6 】。假设一个网络冲浪者通过随机的点击超链接在网上冲浪，在前面的 假设前提下，每个网页都是可能达到的，只不过是达到的可能性的大小不同。很 显然，链接到哪个网页的超链接多，那么到达哪个网页的可能性大。这个网页就 相对重要，p a g e r a n k 值也就高。而重要的网页链接到的网页，冲浪者到达的可能 性当然也就大，其p a g e r a n k 值也就相对高。同时也可见重要性权值( p a g e r a n k ) 是整个网页的一个重要性概率分布结果。所以所有网页p a g e r a n k 的总和应该是l 。 如果存在一类网页，这类网页中不包含任何指向其他网页的链接，那么这种 网页将成为沉积( s i n k ) 网页，永远终止。解决这个问题的方法很简单，假如一个随 机冲浪者遇到了这种沉积网页，那么他可以随机地挑选另一个网页并继续他的浏 览。为了对那些不是沉积的网页也一视同仁，这种类型的随机迁跃应该能以相同 的概率在任何一个网页上发生。公式2 2 是整个网络的链接跳变矩阵公式【1 7 】。 ， 厂1 m = 1 1 一a ) m + 口l 二i 幸n ( 2 2 ) 、 l j 其中m 是一般情况下的跳变矩阵，在这种情况下，所有的页面都至少有一个 链出，而公式2 2 的后面一部分则是对无链出页面的一种修正，即用户以一特定 的概率随机地挑选另一个网页并继续他的浏览，a 为随机选择概率的大小。 2 2 2 3h i t s 算法与p a g e r a n k 算法的区别 显而易见，两者均是基于链接分析的搜索引擎排序算法，学者对这两种算法 相结合的可能性作了理论上的探讨，并且在算法中二者均利用了特征向量作为理 论基础和收敛性依据。但两种算法的不同点也非常明显，以下是它们主要的不同 占 ，、 a 虽然均同为链接分析算法，但二者之间还是有一定的区别。h i t s 的原理 如前所述，其a u t h o r i t y 值只是相对于某个检索主题的权重。而p a g e r a n k 算法独 立于检索主题。p a g e r a n k 把引文分析思想借鉴到网络文档重要性的计算中利用网 络自身的超链接结构给所有的网页确定一个重要性的等级数【1 8 】。 b h i t s 是首先通过基于文本的搜索引擎柬获得最初的处理数据，网页重要 性的传播是通过h u b 页向a u t h o r i t y 页传递，而且k l e i n b e r g 认为，h u b 与a u t h o r i t y 之间是相互增强的关系；两p a g e r a n k 是基于随机浪模型，可以认为它将网页的 9 潜在语义分析布互联m 数据挖掘中的麻用研究 重要性从一个a u t h o r i t y 页传递给另一个a u t h o r i t y 页。 c p a g e r a n k 算法实质上是一种通过离线对整个互联网结构图进行幂迭代的 方法。p a g e r a n k 所计算出的价值度的值实际上就是互联网结构图经过修改后的相 邻矩阵的特征值。它是离线进行的，因此不会为在线的查询过程付出额外的代价。 但是，它计算出来的价值度不是针对查询的，而h i t s 算法所作用的查询子图的 获取是在线实现的，所以要付出较大的时间代价。 还有一点必须要提到的是，在对很多广义主题进行查询时，h i t s 算法会错误 地将许多与主题无关的网页赋予很高的价值度。通常这些页面之间有大量的互链 接，从而错误地诱导了h i t s 算法。这种现象通常被称为主题漂移( t o p i cd r i f t ) 。 2 2 3 互联网搜索中使用的挖掘 对于互联网搜索而言，互联网搜索中使用的挖掘是其中很重要的一部分，同 时它也已经成为互联网发展的一股新动力。在电子商务迅猛发展的当代，它主要 表现在互联网搜索的个性化推荐。 个性化推荐就是对于不同的互联网用户，输入不同的查询词信息系统会因为 不同用户的兴趣不同而得到不同的网页或服务，以满足用户不同的需求。个性化 推荐通过收集和分析用户信息来获取用户的兴趣和行为，从而实现主动