（信号与信息处理专业论文）关于web数据挖掘中hits算法的研究.pdf

摘要 i n t e m e t 是一个巨大、分布广泛、全球性的信息服务中心，它提供了各种各样的信息 服务。与此同时，如何从i n t e m e t 所提供的浩如烟海的信息中获取所需信息或是从中提 取出有用知识便相应的成为一个迫切需要解决的问题。 将传统的数据挖掘技术和w e b 结合起来，进行w e b 数据挖掘成为解决这一问题的 一条重要途径。本文首先论述了数据挖掘技术在w e b 中应用的各个方面，包括其分类、 技术、发展状况、前景和研究方向，以及w e b 数据挖掘技术在搜索引擎中的应用，并 讨论了x m l 为w e b 数据挖掘带来的新变化与转机。 w e b 结构挖掘是w e b 数据挖掘的一个重要方面，其重点在于信息检索，链接分析技 术在该领域中扮演着极为重要的角色，并已经被成功的用于分析w e b 超链接数据来确定 权威的信息源。在各种对网页进行链接分析并提取分组的算法中， 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 ) 算法是应用的最为广泛的。本文对h i t s 算法进行 了重点讨论，在实验的基础上对传统h i t s 算法易产生主题偏移问题这一缺点进行了分 析，并针对这一问题，使用根集向量投影法和基本集缩减法对h i t s 算法加以改进，接 着在根集向量投影法的基础上，又提出了根集向量加权投影法和基本集向量加权投影法 进行进步改进，以更好的实现权威网页搜索。 本文对改进后的h i t s 算法与传统h i t s 算法进行了实验比较，发现根集向量投影法 可以有效的避免主题偏移现象，基本集缩减法可以大大的缩减算法运算量，而根集向量 加权投影法和基本集向量加权投影法则可以在使权威网页的提取结果更为合理的基础 上，有效提高算法的灵活性。 关键词：w e b 数据挖掘；a u t h o ri ti e s ；h u b s ；t s 算法：根集向量投影法；基本集缩减 法；根集向量加权投影法；基本集向量加权投影法 a b s t r a c t i n t e m e ti sah u g e ，w i d e l yd i s 仃i b u t e da n dg i o b a li n f o r m a t i o ns e r v i c ec e n t e r , w h i c h p r o v i d e s v a r i o t l sk i n d so fi n f o r m a t i o ns e r v i c e s m e a n w h i l e ，h e wt oo b t a i n r e q u i r e d i n f o r m a t i o no ru s e f u lk n o w l e d g ef r o mt h eg r e a td e a lo fi n f o r m a t i o n p r o v i d e db yi n t e m e th a s t h e nb e c o m ea p r o b l e mr e q u i r e d t ob es o l v e da to n c e i ti sav e r yi m p o r t a n tm e t h o dt oi m p l e m e n tw e bd a t am i n i n gb yc o m b i n i n gt r a d i t i o n a l d a t a m i n i n gt e c h n o l o g y a n d w e b f i r s t ，a n o v e r v i e w o f d a t a m i n i n gt e c h n o l o g y u s e di nw e bi s g i v e ni nt h i st h e s i s ，i n c l u d i n gi t sc l a s s i f i c a t i o n ，t e c h n o l o g y , d e v e l o p m e n t ，f u t u r e ，r e s e a r c h d i r e c t i o na n di t s a p p l i c a t i o ni ns e a r c he n g i n e s ，a sw e l la st h ec h a n g e sa n dc h a n c e si nw e b m i n i n gb r o u g h tb y x m l i nw e bs t r u c t u r em i n i n g ，h y p e r l i n ka n a l y s i sh a sb e e ns u c c e s s f u l l yu s e di na n a l y z i n gt h e h y p e r l i n kd a t ao fw e bp a g e st o e x t r ta u t h o r i t a t i v ei n f o r m a t i o ns o u r c e s a m o n gv a r i o u s h y p e r l i n ka n a l y s i sm e t h o d 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 ) a l g o r i t h mi su s e dm o s t w i d e l y i nt h ef o l l o w i n gp a mo ft h i st h e s i s ，h i t sa l g o r i t h mi sd i s c u s s e da n db a s e do nt h e e x p e r i m e n t s ，t h et o p i c d r i f tp r o b l e mo fh i t sa l g o r i t h mi sa l s o a n a l y z e d t h e nr o o t s e t e i g e n v e c t o rp r o j e c t i o nm e t h o da n db a s e - s e td o w u s i z i n gm e t h o da r ei m p l e m e n t e dt oi m p r o v e t h eh i t sa l g o r i t h m b a s e do np r o j e c t i o nm e t h o d ，w e i g h e dr o o t - s a t e i g e n v e c t o rp r o j e c t i o n m e t h o da n d w e i g h e d b a s e - s e te i g e n v e c t o rp r o j e c t i o nm e t h o da r ea l s op m p o s e di nt h i st h e s i st o m a k ed e e p e r i m p r o v e m e n ts o t h a tt h es e a r c ho fa u t h o r i t a t i v ew e bp a g e sc a nb cm o r e e f f e c t i v e l y b yc o m p a r i n gt h ee x p e r i m e n t so f t h e s ei m p r o v e dh i t s a l g o r i t h m sa n d t r a d i t i o n a lh i t s a l g o r i t h m ，i tc a nb es e e nt h a tr o o t s e te i g e n v e c t o rp r o j e c t i o nm e t h o dc a ne f f e c t i v e l ya v o i d t o p i c d r i f tp r o b l e m s ；b a s e - s e td o w m i z i n gm e t h o dc a l lg r e a t l yd e c r e a s e dt h e c o m p u t a t i o n a l c o s ： w e i g h e dr o o t - s e te i g e n v e e t o rp r o j e c t i o nm e t h o da n dw e i g h e db a s e - s e te i g e n v e c t o rp r o j e c t i o n m e t h o dc a nn o to n l ym a k et h er e s u l t so fe x t r a c t i n ga u t h o r i t a t i v ep a g e sm o r er e a s o n a b l e ，b u t c a na l s oi m p r o v et h ea g i l i t yo f h i t s a l g o r i t h m k e y w e r d s ：w e bd a t a m i n i n g ：a u t h o r i t i e s ：h u b s ：h i t sa i g o r i t h m ：r o o t s e t e i g e n v e c t o rp r o j e c t i o nm e t h o d ：b a s e - s e td o w n s i z in gm e t h o d ；w e i g h e d r o o t s e t e i g e n v e c t o rp r o j e c t i 0 1 1 m e t h o d ：w e i g h e d b a s e s e t eig e n v e c t o rp r o j e c tio nm e t h o d 关于w e b 数据挖掘中h i t s 算法的研究 1 绪论 1 1 本文应用背景 万维网是i n t e m e t 信息的主要载体之一，我们每个人都能分享到其丰富的资源。这 几年来，我们身边的这个网络正在以惊人的速度成长起来，每天都有数以百万计的网页 加入到w w w 中。它已经成为了一个涉及教育、政府、电子商务、新闻、广告、消费信 息、金融管理和许多其它信息服务的、巨大的、分布广泛、全球性的信息服务中心。 i n t e m 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 数据挖掘就是从与w w w 相关的资源与行为中抽取感兴趣的、潜在的有用模式 和隐含信息。随着信息技术的发展，计算机、网络和通信三者的相互结合，已经产生了 数据挖掘的新方向。 w e b 结构挖掘是w e b 数据挖掘的个重要方面，其重点在于信息检索。虽然随着万 维网规模上的迅速增长，其复杂性也大大的增加，以致于我们已经无法继续掌握其全貌。 然而，在一些较小的、本地的领域里，w e b 表现的仍然是有序的、结构化的，因为网页 的超链接结构是建立在人们努力进行注释的基础上的。w e b 网页的作者往往会在其网页 中添加指向相关主题网页的链接。通过利用这些链接信息，就可以针对某一主题对网页 进行提取和分组。搜索引擎可以帮助人们尽快地找到所需要的信息，但是目前多数搜索 引擎是基于分类或关键词逻辑组配的检索方式，用户的一个查询请求往往会检索出庞大 的结果集，而用户所需要的信息却只是其中- - 4 , 部分，面对如此多的结果，用户仍然不 知所措，因此，如何提供一些有效的工具和方法，帮助人们高效地获取所需信息，搜索 所需领域的权威网页就成为了研究者们所面临的重大课题。 为了达到自动识别权威网页的目的，首先必须要能对网页价值进行合理的评估，而 计算网页价值的一种切实有效的途径就是利用万维网链接结构本身所包含的丰富信息。 关于w e b 数据挖掘中h i t s 算法的研究 链接分析技术在这一领域中扮演着重要的角色，已经被成功地用于分析w e b 超链接数据 来确定权威信息源，并已经成为当前主流i n t e m e t 搜索引擎的基础。 在所有对网页进行链接分析并提取分组的算法中，h i t s ( h y p e r l i n k - i n d u c e dt o p i c s e a r c h ) 算法是应用的最为广泛的。本文对h i t s 算法进行了深入细致的分析并提出了多 种改进方法，以期更好的实现权威网页搜索。 1 2 本文的工作 本文的主要研究对象是h i t s 算法及其改进，该算法属于w e b 数据挖掘中的结构挖 掘，本文具体的工作安排如下： ( 1 ) 第二章分别从w e b 内容挖掘，w e b 结构挖掘，w e b 使用挖掘，w e b 数据挖掘技 术在搜索引擎中的应用，x m l 为w e b 数据挖掘带来的新变化与转机，w e b 数据 挖掘的发展方向这6 个方面归纳总结了数据挖掘技术在w e b 中的应用。 ( 2 ) 第三章首先介绍了h i t s 算法的应用背景和发展历史，然后对m t s 算法进行了详 细的描述，接着将m t s 算法与另一个比较具有代表性的网页排序算法 p a g e r a n k 算法进行了比较，并在结合这两个算法的基础上，构建了信息检索的综 合模型，最后，针对w w ，信息动态性强、传统h i t s 算法对权威网页的提取结 果不稳定的特点，介绍了一种改进算法一子空间h i t s 算法。 ( 3 ) 第四章对h i t s 算法进行了实验验证，从中引出了传统h i t s 算法容易出现主题偏 移现象这一缺点，接下来便是针对这一缺点所进行的算法改进工作。首先，使用 了根集向量投影法对h i t s 算法进行改进，然后使用了能够大大减少算法运算量 的基本集缩减法，接着针对基本集缩减法较难设定合适系数的缺点，将根集向量 投影法与基本集缩减法结合起来，使结合后的新算法皆具两者共同的优点。再接 下来，又提出了根集向量加权投影法和基本集向量加权投影法。以使权威网页的 提取结果更为合理，并在避免主题偏移现象的同时，有效提高了算法的灵活性。 以上这些改进后算法，均通过实验与传统h i t s 算法进行了比较分析。 ( 4 ) 第五章对h i t s 算法和改进算法的结论及其应用进行了归纳总结。 2 关于w e b 数据挖掘中h i t s 算法的研究 2w e b 数据挖掘 2 1 引言 2 1 1 w e b 数据挖掘应用背景 i n t e r a c t 是一个巨大、分布广泛、全球性的信息服务中心，它涉及教育、政府、电子 商务、新闻、广告、消费信息、金融管理和许多其它信息服务，i n t e m e t 的普及和发展为 人们带来了巨大的社会效益，也为信息科学的研究带来了巨大的机遇和挑战。然而，虽 然网络可以迅速便捷的为人们带来大量信息，但在实际应用中，当需要从网络上获取信 息时，有用信息往往会被大量的无用信息所淹没，使用户处于无所适从的境地。与此同 时，还有许多其它问题伴随而来：诸如信息真假难以辨识：信息安全难以保证：信息形 式不一致，难以统一处理等等。因此，如何快速、准确地获取有价值的网络信息，如何 将已有的历史数据理解消化并用于预测未来的行为( 例如电子商务中的卖方通过记录下 来的消费者数据进行统计和预测，借以调整策略) ，如何从海量数据中发现知识，概括起 来也就是如何快速准确的获取所需信息、如何获得信息之间潜在的知识以及如何提供个 性化的服务，已经成为了亟需解决的问题。但是，w e b 所具有的海量数据、复杂性、极 强的动态性、用户的多样性和小相关性或有用性等特点给w e b 资源发掘造成了相当的难 度。 近年来兴起与发展的数据挖掘技术为以上这些问题的解决带来了一线曙光。数据挖 掘是融合了统计学、人工知识、模式识别、并行计算、机器学习、数据库等技术的一个 交叉性的研究领域，它是一个从存放在数据库、数据仓库或其它信息库中的大量数据中 挖掘有价值知识的过程。因此，将数据挖掘技术和w e b 结合起来，进行w e b 数据挖掘 就自然而然的成为了解决w e b 挖掘问题的重要途径。 本章首先对数据挖掘技术进行简要介绍，接下来从三个方面详细介绍w e b 数据挖掘 的内容、技术和发展状况，然后介绍w e b 数据挖掘技术在搜索引擎中的应用，并讨论了 x m l ( e x t e n s i v e m a r k u pl a n g u a g e ) 为w e b 数据挖掘带来的新交化与转机。最后对w e b 数据挖掘进行总结并对其未来的发展前景和研究方向做了个简单的介绍。 2 1 2 数据挖掘 数据挖掘是近年来随着数据库和人工智能技术的发展而出现的一种全新技术，也是 计算机科学与技术，尤其是计算机网络的发展和普遍使用所提出的，并迫切需要解决的 重要课题，从概念上讲，数据挖掘是一个从存放在数据库、数据仓库或其它信息库中的 大量数据中挖掘有用知识的过程，可以将人类经验与数据模式结合起来进行推理式知识 关于w e b 数据挖掘中b l t s 算法的研究 发现( 1l 。同时，数据挖掘又是一种决策支持过程，它主要基于人工智能、机器学习和统 计学等技术，它可以高度自动化的分析数据源原有数据，做出归纳性推理，从中挖掘出 潜在的模式，预测趋势，从而帮助使用者调整策略，做出正确决策。其技术包括特征、 分类、关联、聚类、偏差、时间序列、趋势分析等一“j 。 总的来说，数据挖掘是一个交叉学科领域，受多个学科影响，包括数据库系统、统 计学、机器学习、可视化和信息科学。此外，依赖于所用的数据挖掘方法，以及可以使 用的其它学科的技术，如神经网络、模糊和或粗糙集理论、知识表示、归纳逻辑程序设 计或高性能计算，依赖于所挖掘的数据类型或给定的数据挖掘应用，数据挖掘系统也可 能集成空间数据分析、信息检索、模式识别、图像分析、信号处理、计算机图形学、w e b 技术、经济、商业、生物信息学或心理学领域的技术【2 】。 数据挖掘工具是一种挖掘型的分析工具，其重点在于预测。它主要有两个任务i 5 】： ( i ) 机器的数据库理解，即将数据库变抉为可被计算机理解的简洁模型，然后利用此 模型求解新问题； ( 2 ) 数据库理解，即简化数据并将其翻译为自然形式( 如数学公式等) 。数据挖掘可 以从实例数据中直接导出规则，用于构造知识库，也可以验证已有规则，有利于 知识库的维护和更新。 数据挖掘的技术基础是人工智能，从功能上可以将其分析方法分为基于关联度的分 析、基于序列分析、分类分析和聚类分析四种，在一个实际的数据挖掘系统中经常综合 的利用这四种方法。现有的数据挖掘技术分为预测模型化、聚类、数据归约、依赖模型 化和发现变化偏差五类。随着信息技术的发展，计算机、网络和通信三者的相互结合， 已经产生了数据挖掘的新方向。 2 1 3w e b 数据挖掘 i n t e m e t 不仅可以为用户提供各种各样的信息服务，与此同时，它还包含了极其丰富 的、动态的超链接信息，以及用户对w e b 页面的访问信息，这些信息都为进行数据挖掘 提供了丰富的资源。简而言之，w e b 数据挖掘就是数据挖掘在w e b 上的应用，它是一项 综合技术，采用较为一般的定义：w e b 数据挖掘就是从与w w w 相关的资源与行为中抽 取感兴趣的、潜在的有用模式和隐含信息。概括地说，w e b 挖掘任务包括资源发现、信 息提取和概括三方面。 总的来看，w e b 数据挖掘包含w e b 内容挖掘、w e b 结构挖掘和w e b 使用挖掘三大类， 其分类图如图2 1 所示。 接下来将对这三个部分分别进行论述。 4 关于w e b 数据挖掘中h i t s 算法的研究 2 2w e b 内容挖掘 图2 1w e b 数据挖掘分类图 f i g u r e2 it h ec l a s s i f i c a t i o no f w e bd a t am i n i n g w e b 内容挖掘是指对w e b 页面内容进行挖掘，从w e b 文档的内容信息中抽取知识。 w e b 内容挖掘包括w e b 文本挖掘和w e b 多媒体挖掘，其重点在于页面分类和聚类6 1 。 2 2 1 w e b 文本挖掘 1 概述 w e b 文本挖掘的一般步骤见图2 2 。 图2 2w e b 文本挖掘的一般步骤 f i g u r e2 2t h e p r o c e s so f w e bt e x t m i n i n g 图2 2 所显示的只是在一个粗略的角度上，对w e b 文本挖掘过程的划分。如果详细 的来分析这个过程以及相应的技术，则首先应该指出，w e b 文本挖掘工作的基础是文本 的特征表示，目前常用的方法是向量空间模型。 文本知识挖掘所基于的模型称为文档特征向量空间模型( c v s m ：c h a r a c t e r i s t i c 关于w e b 数据挖掘中h i t s 算法的研究 v e c t o rs p a c em o d e l ) ，即用向量 f l ，d i ；f 2 ，d 2 ；以，或) 来表示文档。其中，n 是文档中所有 词的数目，t j 代表词，d i 指第i 词的权。文档模型建立的过程也就是文档结构化的过程， 其步骤如下： 预处理专概念映射和概念消歧专一般特征项提取和姓名目期数字特征提取专 特征集缩减，并将结果存入文档矢量库。 ( 1 ) 预处理。预处理过程一是要根据禁用词集去除文档中语义虚泛的禁用词，如“的、 尽管、t h e 、a s ”等；二是要利用特征词典集( 包括通用集和专业集) 进行分词， 例如“k n o w l e d g ed i s c o v e r y ”一般就只能作为一个词，而不能作2 个词，“计算 机操作系统”就应该分成3 个词：“计算机”、“操作系统”，“计算机操作系统”。 ( 2 ) 概念映射和概念消歧。有些词形式不同但概念相同，例如“计算机”和“电脑”， 这就要求根据概念集将它们映射为同一概念，如映射为“计算机”；对于一词具 有多概念标注的，如“软件”，可能就标注为“计算机软件”和“社会环境”等， 一般选择出现次数最多的概念标注为其标注。 ( 3 ) 经过以上这两步后，就可以进行一般特征项提取和姓名日期数字特征提取了，提 取的结果存入文档矢量库。 ( 4 ) 特征集缩减。通过以上方法得到的特征集数目巨大，无法有效的进行文本挖掘， 所以还必须进行缩减。其一般算法是构造一个评价函数，对每个特征向量进行评 估，然后根据评估值的大小选取一定数量的特征向量子集，这可以通过设置阈值 来实现。评估函数有多种，如信息增益、期望交叉熵、文本证据权、机率比、词 频等。特征集缩减的结果将存入文档矢量库。 在文档模型建立后，还应对结果进行模型评估，一般是将数据集分为训练集与测试 集。学习测试循环反复执行，最后用一个指标来衡量模型质量。模型评价具体指标 有：分类正确率、查准率、查全率、查准率和查全率的平均和信息估值等。 文档特征矢量中的d ，( 即第i 词的权) 的计算方法有很多种，常用的有t f ，t f i d f 和布尔方法。在t f + f 方法中： d f = t f ( t ，d o e ) 1 d f ( t ，) = t f ( t f ，d o e ) l o g d d f ( t 。) 其中，t f ( t ，d o c ) 为特征在文档d o c 中出现的频度，d 为总文档数，d f ( t ，) 为特征 f ，在其中至少出现一词的文档数，d j 越大，则文档越重要。d i 刻划了特征 区分文档内 容属性的能力，一个属性在文档记中出现的范围越广说明它的区分能力越低，另一方面， 它在某一文档中出现的频率越高，说明它在区分该文档内容属性方面的能力越强。 在布尔方法中，d 。只取0 ，1 两个值，若f f 在文档中出现则d j 取l ，反之取0 。 6 关于w e b 数据挖掘中h i t s 算法的研究 文档模型建立起来后，就可以进行知识发现了。首先进行文本摘要，这一般采用基 于统计的自动生成方式较多，其基本思想是将文中与主体密切相关的句子挑选出来，这 样的句子往往位于特殊的部分或含有较多的特征项，常常以权重函数为评价标准，句子 的权重可以这样设计：结论性的句子、标题、子标题应赋予较高权重，包含检索词的句 子以及段落的开头结尾一般都是结论性语句，权重应较高；接下来进行文本分类，这是 文本知识挖掘的主要目的，其基本思想是将训练矢量集与文档矢量集相互比较，方法主 要有朴素贝叶斯分类算法和k 最近邻参照分类算法。 知识发现完成之后，应该利用知识发现的结果进行模型评价，从而可以对模型作出 进一步修改和完善。 2 文本分类 w e b 文本挖掘研究的一个重要内容是根据文档中所包含的文本数据特征进行文本分 类，以方便查阅检索，其常用方法有相似度分类方法和朴素贝叶斯( n a i v eb a y e s ) 分类 算法。 ( 1 ) 相似度分类法： 相似度分类法是计算待分类文档与各类别的相似度，选取相似度大的类别作为待分 类文档的类别【”。 在计算相似度s i m ( d 。，q ) 时，最简单的方法是仅考虑两个特征矢量中所包含的词条的 重叠程度，即令 咖( 和f ) - 嬲 其中”n ( 以，c 1 ) 是文档特征矢量v ( a i ) 和类别特征矢量z ( c 。) 具有的相同词条数目， n u ( 矾，q ) 是矿( 以) 和以q ) 具有的所有词条数目。 另一种常用的计算相似度的方法是考虑两个特征矢量之间的夹角余弦，即 咖( = 蹦 ( 2 ) 朴素贝叶斯分类器： 朴素贝叶斯分类器是一个简单、有效而且在实际使用中很成功的分类器。它通过概 率计算，从待分类的实例的属性值口l ，一。求出最可能的分类目标值，即计算各类c e c 对 于这组属性的条件概率p ( c h ，) ，并输出条件概率最大的类标签作为目标值。条件 概率j p ( c ，h ，卅。) 的计算公式为： 7 关于w e b 数据挖掘中h i t s 算法的研究 e ( c 加。，) ：a p ( c n p ( n 小，) 其中a 是正规化常数，以后验概率作为分类指示，即输出具有最大后骏概率的类标 签c ，朴素贝叶斯分类器的定义为： c m 叫8 警p ( c 县酬c 声， 月 3 文本聚类 文本聚类与文本分类的过程恰恰相反，文本聚类指的是将文档集合中的文档分为更 小的簇，要求同一簇内的文档之间的相似性尽可能大，而簇与簇之间的关系尽可能小， 这些簇就相当于分类表中的类目。聚类分析是w e b 文本挖掘的主要手段之一，它的主要 作用是： ( 1 ) 通过对检索结果的聚类，将检索到的大量网页以一定的类别提供给用户，使用户 能够快速定位期望的目标； ( 2 ) 自动生成分类目录； ( 3 ) 通过相似网页的归并，便于分析这些网页的共性。 k 均值聚类是b b 较典型的聚类算法，另外，自组织映射( s o m ) 神经网络聚类和基于 概率分布的贝叶斯层次聚类( h b c ) 等新的聚类算法也正在不断地研制与应用。k i n g - i p l i n 和r a v i k u m a rk o n d a d a d i 提出了一种基于相似度的文档聚类算法( s i s c ： s i m i l a r i t y b a s e ds o f tc l u s t e r i n g a l g o r i t h m f o r d o c u m e n t s ) is 】。 基于相似度的文档聚类算法( s l s c ：s i m i l a r i t y - b a s e ds o f tc l u s t e r i n ga l g o r i t h mf o r d o c u m e n t s ) ： s i s c 算法将文档聚类工作分为4 步： ( 1 ) 预处理( p r e - p r o c c s s i n g ) 。在这一步中，将文档转换为向量结构表示，从而可以被 相似度函数厂( ) 使用。相似度函数，( ) 被定义为描述两篇文档x 和y 的相似程度， 且0 ，力1 ； ( 2 ) 产生初始簇( i n i t i a lc l u s t e rg e n e r a t i o n ) 。在这一步中主要是对输入进行分析，产生 初始簇并移除无关文档。在这一过程中，首先使用相应算法选取初始簇，然后设 立阈值并利用相似度函数判断剩余各篇文档的归属，最后根据结果筛除无关文 档； ( 3 ) 迭代步骤( i t e r a t i v es t e p ) 。在这一步中对簇进行进一步提炼，通过定义一个度量 函数m ( c ，x ) 来表示文档x 与簇c 的相似程度。在每次循环中都调整簇心并重新计 算新的m ( c ，x ) 值，从而实现簇的进一步改进； ( 4 ) 簇和关键字展示( d i s p l a y i n gc l u s t e r sa n dk e y w o r d s ) 。在s i s c 算法的最后，还需 要将最终结果显示出来从而达到对算法的评价。主要展示最终簇以及簇中文档， 8 关于w e b 数据挖掘中h i t s 算法的研究 簇中文档的展示根据聊( c ，x ) 的值( 反映了文档与簇的关联程度) 进行排序，另 外还对每一簇提取出关键字，进行概括表示。 s i s c 算法只需要对聚类过程进行相似度度量，并使用随机选取来提高聚类效率，与 传统的k 均值聚类算法相比，s i s c 算法的搜索过程更高效，结果也更为有效。为了降 低聚类中的运算量，f e i w u 和g e o r g e s g a r d a f i n 提出了逐步聚类算法( o r a d u a l c l u s t e r i n g a l g o r i t h m ) 【9 】迸行递增聚类，利用三角形两边之和大于第三边的原理来减少不必要的运 算。 由于无监督学习聚类算法对解空间的搜索带有一定的盲目性，因而聚类的结果在一 定程度上缺乏语义特征。同时，在高维情况下，选择合适的距离度量标准变得相当困难。 而网页分类是一种监督学习，它通过对一系列训练样本的分析来预测未知网页的类别归 属。目前已有很多有效的算法来实现网页的分类，如n a i v e b a y e s i a n ，s v m 等。但遗憾 的是，获得大量的、带有类别标注的样本的代价是相当昂贵的，而这些方法只有通过大 规模的训练才能获得较高精度的分类效果。此外，在实际应用中，分类体系常常是不一 致的，这为目录的日常维护带来了定的困难。为此，k a m a l n i g a m 等人提出了从带有 类别标注和不带有类别标注的混合文档中分类w e b 网页【l0 1 ，它只需要部分带有类别标 注的训练样本，结合未标注样本含有的知识来学习贝叶斯分类器，文献f i l 】中提出了一种 基于b a y e s 潜在语义模型的半监督w e b 挖掘算法。 基于b a y e s 潜在语义模型的半监督w e b 挖掘： 潜在语义分析( 1 a t e n ts e m a n t i ca n a l y s i s ，简称l s a ) 的基本观点是：把高维的向量空 间模型( v s m ) 表示中的文档映射到低维的潜在语义空间中。这个映射是通过对项文档 矩阵0 。的奇异值分解( s v d ) 来实现的。根据线性代数的知识可知，任意矩阵 0 。均可 以分解为以下形式： n ：u 2 v ( 2 1 ) 其中，u 、y 是正交阵( u u 7 = v v 7 = ，) ，三, = d i a g ( a i ，4 2 ，吼，口，) ( a 1 , 口2 ，吼，口， 为的奇异值) 是对角阵。潜在语义分析通过取七个最大的奇异值，而将剩余的值设为 零来近似式( 2 1 ) ，即 帮= 瞳y 7z u 三y 7 = n ( 2 2 ) 由于文档之间的相似性，可以通过7 * 旆7 = c 蘑2 u 来表示，因此文档在潜在语 义空间中的坐标可以通过磨来近似，于是便实现了商维空间中的文档表示到低维的潜 在语义空间中的投影。 通过奇异值分解，将文档在高维向量空间模型中的表示，投影到低维的潜在语义空 间中，有效的缩小了问题的规模。潜在语义分析在信息滤波、文本索引、视频检索等方 面都有较为成功的应用。 基于b a y e s 潜在语义模型的半监督w e b 挖掘算法的基本思想是：如果知道一批网页 0 关于w e b 数据挖掘中h i t s 算法的研究 d = d 1 , d 2 ，d 。) 是关于某些潜在类别主题变量z = z 1 , = 2 ，一。) 的描述，通过引入贝叶斯 潜在语义模型，首先将含有潜在类别主题变量的文档分配到相应的类主题中，接着利用 简单贝叶斯模型，在前一阶段类别标注的基础上，完成对未含类主题变量的文档作标注。 针对这两个阶段的特点，定义两种似然函数，并利用e m ( e x p e c t a t i o nm a x i m i z a t i o n ) 算 法获得最大似然估计的局部最优解。 这种处理方法一方面克服了非监督学习中对求解空间搜索的盲目性；另一方面，它 不需要对大量训练样本的类别进行标注，只需提供相应的类主题变量，从而把网站管理 人员从繁琐的训练样本的标注中解脱出来，提高了网页分类的自动性。 2 2 2w e b 多媒体挖掘 对于w e b 中多媒体文档( 包括i m a g e ，a u d i o ，v i d e o 等) 的挖掘称为w e b 多媒体挖 掘，主要是指通过对w e b 上的音频、视频数据和图像进行预处理，应用存储和搜索技术 与标准的数据挖掘方法的集成，对其中潜在的、有意义的信息和模式进行挖掘的过程。 其主要内容包括： ( 1 ) 多媒体数据的多维分析，这可以通过设计和构造多媒体数据立方体来实现； ( 2 ) 多媒体数据中的相似搜索，这又可以分为基于描述的检索系统和基于内容的检索 系统两种； ( 3 ) 分类和预测，主要通过使用决策树方法； ( 4 ) 多媒体数据的关联规则挖掘，包括图像与非图像内容之间的联系、与空间无关的 图像内容的关联和与空间有关的图像内容的关联【1 2 】。 限于篇幅，本文对w e b 多媒体挖掘将不再做更多的讨论。 2 3w e b 结构挖掘 w e b 结构挖掘是指针对w e b 页面之间的超链接结构、内部结构和u r l 中的目录路 径结构进行挖掘，从中抽取知识，它包括文档结构挖掘和站点结构挖掘。其主要目的在 于通过发现w 如页面的结构，在此基础上对页面进行分类和聚类，从而找到权威页面， 而权威页面的获得，可以为w e b 应用提供诸多益处，如对搜索引擎的改进等等。当前的 w e b 结构挖掘的研究分为两个方向1 3 】： ( 1 ) 一般的访问模式追踪，即通过分析使用记录来了解用户的访问模式和倾向，以改 进站点的组织结构； 1 0 关于w e b 数据挖掘中h i t s 算法的研究 ( 2 ) 个性化的使用记录追踪，即分析单个用户的偏好，根据不同用户的访问模式为每 个用户提供定制的站点。 s p e r m s 在p a r a s i t e 系统l 1 41 中提出了一种w 曲结构知识挖掘方法，其主要思想是： 超级链接从方向上可以分为向上链接、向下链接、交叉链接和向外链接，利用如下启发 式规则： ( 1 ) 在一个层次索引中，从一个页面开始，由向下或交叉链接得到的页面，其主题和 原始页面的主题相关； ( 2 ) 从一个索引开始，任何由本页面的向外链接得到的页面，其主题很可能是相同的： ( 3 ) 从一个索引p 开始，沿着向外链接指向索引q ，通过g 的向外链接得到的页面很 可能和p 的主题相关； ( 4 ) 如果p 是个人主页，而文件q 在下面的目录中，那么g 的作者很可能就是个人主 页p 所标识的人； ( 5 ) 如果页面p 是在g 的上层目录中，而且存在从q 到p 和p 到q 的超级链接，那么 p 就有可能是个人主页； ( 6 ) 如果u r lc 和沈在同一个页面中距离很近，那么它们就有可能具有类似的主题 或特征。 利用这些规则，就可以得到页面之间的结构关系，从而实现发现个人主页，搜索新 页面和自动索引的目的。 p a g e r a n k 方法 当我们在搜索某一给定主题的w e b 页面时，我们往往希望所检索到的页面具有较高 的质量和权威性。s t a n f o r d 大学研究的p a g e r a n k 算法【1 5 】是一种常用的权威页面识别算 法，它的基本思想是：如果一个页面被多次引用，则这个页面很可能是重要的；如果一 个页面被引用的次数不多，但它被另外一个重要页面引用，则它也可能是重要的；一个 页面的重要性被均分并被传递到它所引用的页面中。具体算法如下： 定义“是一个w e b 页面，凡是”引用的页面集合，风是引用”的页面集合，以= 阮l ， 则“的重要性为： r c u ) = ( r ( v ) a r ，) 雌口 对于一个查询g ，搜索引擎首先利用相似度函数找到七个页面，然后利用公式： r a n k i n g s c o r e ( q ，d ) 一一s i m ( q ，d ) + w 2 r ( d ) 计算每个页面的重要性，并进行排名，这里，w i , ”2e o ，1 】，w l + w 2 = 1 ，w 2 被称为衰减 因子，通常取0 8 5 ，s i m ( q ，d ) 是相似函数，s i m ( q ，d ) 和r ( d ) e o ，1 。 关于w e b 数据挖掘中h i t s 算法的研究 h u b a u t h o r i t y 算法 由于w e b 链接结构所具有的一些局限性，例如并不是每一个超链接都具有注解性， 有些链接是为了其它目的而创建，以及很少有w e b 页面会指向其竞争领域的其它权威页 面等等，一种称为h u b 的重要的w e b 页面被提出，h u b 是一个或多个w e b 页面，它提供 了指向权威页面的链接集合。通常，好的h u b 是指向许多好的权威页面的网页；好的 a u t h o r i t y 是由许多好的h u b s 所指向的页面。这种h u b 与a u t h o r i t y 之间的相互作用，可用 于权威页面的挖掘和高质量w e b 结构和资源的自动发现，这就是h u b a u t h o r i t y 算法的基 本思想。 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 ) 是利用h u b a u t h o r i t y 算法的搜索算法， 其内容如下： ( 1 ) 首先将查询q 提交给普通的基于相似度的搜索引擎，搜索引擎返回很多页面，从 中提取一个页面作为根集，用s 表示。 ( 2 ) 然后通过向s 中加入被s 引用的页面和引用s 的页面将s 扩展成一个更大的集合 r 。 ( 3 ) 再以r 中的h u b 页为顶点集巧，以a u t h o r i t y 页为顶点集乃，乃中的页面到巧中 的页面的超链接为边集e 形成一个二分有向图s g = ( 巧，圪，e ) 。对巧 中的任个顶点v ，用h ( v ) 表示页面v 的h u b 值，对巧中的顶点“用砷表示 页面“的a u t h o r i t y 值。开始时a = h ( v ) = 1 。对“执行i 操作修改它的a ( “) ， 对v 执行0 操作修改它的h ( v ) ： i 操作： 出) = j j l ( v ) ，( 2 f 3 ) 0 操作： ( v ) = ) ，( 2 4 ) ( 4 ) 每次迭代后对a ( 和h ( v ) 进行归一化处理： 嘶卜齑姆卜赫 式( 2 3 ) 反映了若一个页面由很多好的h u b s 所指，则其a u t h o r i t y 权重会相应增加 ( 即权重增加为所有指向它的页面的现有h u b s 权重之和) 。式( 2 4 ) 反映了若一个页面 指向许多好的权威页，则h u b 权重也会相应增加( 即权重增加为该页面链接的所有页面 的a u t h o r i t i e s 权重之和) 。 h i t s 算法输出一组具有较大h u b 权重的页面和具有较大a u t h o r i t y 权重的页面。实 验表明，该算法对于许多查询都具有非常好的效果。本文的主要内容就是h i t s 算法及 其改进，因此，关于这一方面的内容将在后面的章节里进行专门的详细论述。 关于w e b 数据挖掘中h i t s 算法的研究 2 4w