（计算机应用技术专业论文）蚁群算法在web挖掘中的应用研究.pdf

蚁群算法在w e b 挖掘中的应用研究 蚁群算法在w e b 挖掘中的应用研究 摘要 本文比较系统、完整地分析和论述了w e b 挖掘中的各项 技术，总结了现有的w e b 挖掘中的聚类技术和分类的研究成果。 结合蚁群优化算法，将一种基于蚂蚁“相容理论( c o l o n i a lc l o s u r e ) ” 原理的聚类算法应用于w e b 使用挖掘的页面聚类中；并引入一 种基于“蚂蚁觅食”原理的分类算法应用于w e b 内容挖掘的页 面分类中。实验结果表明：与传统算法相比较，基于蚂蚁的聚类 和分类算法在w e b 挖掘中具有一定的优势。 论文首先对w e b 使用挖掘的四个过程：数据预处理、模式 发现、模式分析和模式应用进行了详细地论述、并对在w e b 挖 掘中进行聚类和分类的现有技术的优缺点做了综述性的评价。介 绍了蚁群算法的起源、蚁群算法的原型以及为了借鉴蚂蚁行为而 建立的人工蚂蚁概念与真实蚂蚁的异同，且给出了蚁群聚类算法 的基本思想。在给出了必要的背景知识之后，本文将一种基于蚂 蚁“相容理论”原理的聚类算法应用于w e b 使用挖掘的页面聚类 中，对w e b 日志进行了根据目的而需的预处理工作。实验结果 表明：较传统算法，该聚类算法对w e b 页面进行聚类时，无需 先验知识的支撑，并能够聚出各种大小的簇、且聚类结果能够很 好地被解释。 然后，论文提出一种蚂蚁分类算法a n t应用到 蚁群算法在w e b 挖掘中的应用研究 内容挖掘中页面分类的方法，并进行了非结构化数据集的处理。 经过对w e b 页面进行消歧和抽取词干的预处理之后，数据属性 的维度大大下降。根据论文实验结果就得出的分类规则的准确率 和简洁性同传统的分类算法c 5 0 进行了对比：a n t m i n e r 3 算法 能够发现更准确的分类规则，以及得出更简单的规则。 关键字：w e b 挖掘；蚁群算法；w e b 使用挖掘； w e b 内容挖掘；聚类；分类 广西大学硕士学位论文蚁群算法存w e b 挖掘中的应用研究 t h er e s e a r c ho fu s i n ga n t c o l o n ya l g o r i t h m i nw e bm i n i n g a b s t r a c t t h ew e b m i n i n gt e c h n i q u e s w e r e a n a l y z e d a n dd i s c u s s e d s y s t e m a t i c a l l y , i n t e g r a l l yi nt h i sp a p e r , a n dt h e nt h ep r o g r e s so fc l u s t e r i n g a n dc l a s s i f i c a t i o ni nw e bm i i l i i l gw a ss u m m a r i z e d c o m b i n e dw i t ht h e a c oa l g o r i t h m , ac l u s t e r i n ga l g o r i t h mb a s e do na n t c o l o n i a lc l o s u r e w a sa p p l i e dt ow e bp a g ec l u s t e r i n go fw e bu s a g em i n i n g ，m o r e o v e r , a c l a s s i f i c a t i o na l g o r i t h mb a s e do n a n ts e a r c hf o rf o o d w a su s e di nt h e p r o c e s s i n go fw e bp a g ec l a s s i f i c a t i o ni nw e bc o n t e n tm i n i n g t h er e s u l t s h o wt h a t ，c o n t r a s tt ot r a d i t i o n a lm e t h o d ，t h ec l u s t e r i n g a n d c l a s s i f i c a t i o na l g o r i t h mb a s e do na n th a b i th a v ec e r t a i nc o m p a r a t i v e a d v a n t a g e si nw e bm i n i n g f o u rs t a g ed e s i g n a t e da sd a t ap r o c e s s i n g ，p a r e md i s c o v e r y , p a t t e r n a n a l y s i sa n dt h ea p p l i c a t i o no fp a r e r nw e r ef i r s ta d d r e s s e di nd e t a i l ，t h e n t h ea d v a n t a g ea n ds h o r t c o m i n go fe x i s t i n gc l u s t e r i n ga n dc l a s s i f i c a t i o n t e c h n i q u e si nw e bm i n i n gw e r ee s t i m a t e d t h eo r i g i na n dp r o t o t y p i n go f a o ca l g o r i t h mw e r ei n t r o d u c e da n dt h e nt h ed i f f e r e n c eb e t w e e na r t i f i c i a l a n td e r i v e df r o ma n tb e h a v i o ra n dr e a la n tw e r ep r e s e n t e d ，t h eb a s i c p r i n c i p l eo fa o ca l g o r i t h mw a sa l s od i s p l a y e d a f t e rt h ei n t r o d u c t i o no f 4 广西大学硕士学位论文蚁群算法在w e b 挖掘中的应用研究 n e c e s s a r yb a c k g r o u n dk n o w l e d g e ，t h ec l u s t e r i n ga l g o r i t h mb a s e do na n t “c o l o n i a lc l o s u r e w a sa p p l i e dt ow e bp a g ec l u s t e r i n go fw e bb s b g c m i n i n ga n dt h ew e bl o gw a sp r o c e s s e dp r i m a r i l yf r o mt h ep u r p o s eo fo u r r e s e a r c ha i m w h e na p p l y i n gt ow e bc l u s t e r i n g ，t h i sc l u s t e r i n ga l g o r i t h m w a sb 啊i o rt ot h et r a d i t i o n a la l g o r i t h mw i t h o u tp r i o rk n o w l e d g e ，t h e d a t a r e v e a ld i v e r s i f i e dc l u s t e r sc a nb eo b t a i n e da n dt h er e s u l ti s r e a s o n a b l e an o v e lc l a s s i f i c a t i o na l g o r i t h mn a m e da n l i n e r 3b a s e do na n t b e h a v i o rt os o l v et h ec l a s s i f i c a t i o np r o b l e md u r i n gi nd a t em i n i n gt a s k w a se x p l o i t e dt ow e bp a g ec l a s s i f i c a t i o no fw e bc o n t e n tm i n i n ga n dt h e p r o c e s s o fn o n - s t r u c t u r ed a t a s e tw a sc a r r i e do u t a f t e rt h ep r i m a r y s t e m m i n ga n de x t r a c t i o no fk e y w o r d si nt h ew e bd o c u m e n t ( w e bp a g e o n l y ) ，t h e d i m e n s i o n so fd a t ac h a r a c t e r i z a t i o nd e c r e a s e s h a r p l y c o m p a r e d w i t ht h et r a d i t i o n a lc l a s s i f i c a t i o n a l g o r i t h mc 5 0 ，t h e a l g o r i t h ma n t _ m i n e r 3c a nd i s c o v e rm o r ep r e c i s ea n db r i e f r u l e s k e yw o r d s ：w e bm i n i n g ；a n tc o l o n ya l g o r i t h m ：w e bu s a g em i n i n g ； w e bc o n t e n tm i n i n g ；c l u s t e r i n g ；c l a s s i f i c a t i o n 广西大学硕士学位论文 蚁群算法存w e b 挖掘中的应用研究 第一章引言 近年来，随着大规模的工业生产过程的自动化、商务贸易电子化及企业和政 府事务电子化的迅速普及以及科学计算的日益增长，产生了大规模的数据源。计 算机网络技术的长足进步也为数据的传输和远程交互提供了技术手段，特别是互 联网的迅速发展更是将全球的信息源纳入了一个共同的数据环境中【1 】。日益成熟 的数据库系统和数据库管理系统都为这些海量数据的存储和管理提供了技术保 证，为步入信息时代奠定了基础，这雌庞大的数据库及其中的海晕数据是极其丰 富的信息源。 在这些信息源中隐含了许多有潜在价值的知识，如何发现这些有用的知识是 人工智能、数据库等领域的研究焦点。但是仅仅依靠传统的数据检索机制和统计 分析方法已经远远不能满足需要了。因此，近年来出现了一门新兴的知识提取技 术一数据挖掘数据挖掘旨在从数据库中提取正确的、非平凡的、未知的、有 潜在应用价值的并最终为用户理解的模式。它的出现为自动和智能地把海量的数 据转化成有用的信息和知识提供了手段1 1 1 。数据挖掘涉及到诸如机器学习、模式 识别、统计学、数据库和人工智能等众多学科，是数据库理论和机器学习的交叉 学科 1 1 数据挖掘 数据挖掘和知识发现k d d ( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ) 有密切的联 系。知识发现( r d g d ) 口1 是指从数据库中发现有用知识的整个过程，数据挖掘是这 一过程中的一个特定步骤，知识发现包括数据选择、预处理、数据转换、数据挖 掘、模式解释和知识评价等多个步骤，是应用特定数据挖掘算法和评价解释模式 的一个循环反复过程，并要对发现的知识不断求精深化，使其易于理解：数据挖 掘是知识发现过程中的一个关键步骤。数据挖掘( d a t am i n i n g ) 是从大量的、不完 全的、有噪声的、模糊的、随机的数据中提取潜在的、不为人知的有用信息、模 式和趋势。数据挖掘的目的是提高市场决策能力、检测异常模式、在过去的绎验 基础上预言未束趋势等【3 】。这些知识和规则是隐含的、先前未知的、对决策自潜 在价值的有用信息。通过数据挖掘，有价值的知识、规则或高层次的信息就能从 数据库的相关数据集合中抽取出来，为决策提供依据，从而使数据库作为一个丰 富可靠的资源，为知识归纳服务。 与传统的数据库查询系统相比较，数据挖掘技术有以下不同【4 】 ( 1 ) 传统的数据库查询一般都具有严格的查询表达式，可以用s q l 语句描述， 广西大学硕士学位论文 蚁群算法存w e b 挖掘中的应用研究 而数据挖掘则不一定具有严格的要求，常常表现出即时、随机的特点，查询要求 也不确定。 ( 2 ) 整个挖掘过程也无法仅用s o l 语言就能完整表达，实际上，数据挖掘常 常用一种类似s q l 语言柬描述。 ( 3 ) 传统的数据库查询一般生成严格的结果集，但数据挖掘可能并不生成严 格的结果集。挖掘过程往往基于统计规律，产生的规则并不要求对所有的数据项 总是成立，而是只要达到一定的事先给定的闽值就可以了。 ( 4 ) i 砬常情况下，数据库查询只对数据库的原始字段进行，而数据挖掘则可 能在数据库的不同层次上发掘知识规则。 从广义上讲，数据挖掘分为三种类型：全自动、半自动和全交互式。对于全 自动技术，一旦系统被创建，无需任何人的干预，它能在后台自动进行操作；对 于半自动技术，系统或者在后台操作，或者采用全交互方式：对于全交互式技术， 是一种简单的数据挖掘，它由用户设置每次操作的参数，然后等待相应结果。 数据挖掘在解决实际问题时，经常要同时使用多种模式。一个数据挖掘系统 或仅仅一个数据挖掘查询就可能生成成千上万的模式，但是并非所有的模式都是 令人感兴趣。这里有一个重要的概念，兴趣度( i n t e r e s t i n g n e s s ) ，通常是用来衡量 模式的总体价值，它包括正确性( v a l i d i t y ) 、新奇性( n o v e l t y ) - - 用性( u s e f u l n e s s ) 和 简洁性( s i m p l i c i t y ) 。数据挖掘工具还要求具有开放性，它的开放性体现在两个方 面： 能与各种数据源集成和分析的结果是通用的或易于转化的。数据挖掘工具 相互差别很大，这不仅体现在关键技术上，还体现在运行平台、数据存取和价格 等方面。从运行平台来看，简单的工具可运行在p c 的d o s 或w i n d o w s 上，复 杂的工具要求运行在u n i x 工作站或并行处理平台上。从数据存取来看，简单工 具处理的数据以文件形式输入，复杂工具要求大型的数据库环境。 目前，数据挖掘己成为计算机科学研究中的一个十分活跃的前沿领域，并在 市场分析、金融投资、欺诈甄别、医疗卫生、环境保护、产品制造和科学研究等 许多领域获得了广泛的应用，取得了十分可观的社会效益和经济效益。同时，知 识发现和数据挖掘的研究和应用，对于人工智能这门前沿学科的发展注入了新的 活力，有力地促进了计算机科学朝着纵深方向顺利发展。 1 2w e b 挖掘中的聚类与分类 i n t e m e t 提供了一个海量的信息源泉，它涉及新闻、广告、消费信息、金融 管理、教育、政府、电子商务和许多其它信息服务。w e b 还包含了丰富和动态的 超链接信息，以及w 曲页面的访问和使用信息，这为数据挖掘提供了丰富的资 源。人们希望有一个工具能够自动从i n t e r n e t 上提取知识。传统的数据挖掘基于 关系数据库或数据仓库，所处理数据具有完整的结构。但是i n t e m e t 上的数据却 2 广西大学硕士学位论文 蚁群算法在w e b 挖掘中的应用研究 是无序的、非结构的，并且存在着大量的冗余与噪声。 对有效的数据仓库和数据挖掘而言，w e b 似乎太大了。w e b 的数据量目前 以几百兆字节计算，而且仍然在迅速地增长。 “物以类聚，人以群分”，聚类分析足w e b 挖掘的关键技术之一。在w e b 使 用挖掘中，可以进行两种聚类：用户聚类( 包括用户访问会话聚类和用户访问事 务聚类) 和页面聚类。个性化服务中的用户聚类主要是指通过分析w w 服务器的 日志文件获取w e b 用户行为模式，并将其量化，然后利用一定的算法进行用户聚 类的过程。也就要建立具有相似浏览模式的用户c l u s t e r 。这样的规则对于电子 商务中的市场决策和向用户提供个性化的服务是非常有帮助的。页面聚类是要挖 掘具自相关内容的页面c l u s t e r ，这对于i n t e r n e t 搜索引擎和w e b 提供商都是非常 有用的。 p a g e g r t h e r 算法【3 7 】 3 8 】基于页面在用户访问会话中的共现对w e b 站点的页面 作聚类。对聚类结果中的每一个c l u s t e r ，系统自动生成一个包含该c l u s t e r 中所 以页面链接的w e b 页面，称为索引页。每一个索引页反映一组用户可能具有的 共同兴趣。利用索引页面，可以提供用户的浏览效率。由于索引页面是自动生成 的，因此p a g e g a t h e r 算法可以使w e b 站点具有自适应性。文【3 9 】【4 0 】提出了基于 密度的的递归聚类算法r d b c ( r e c u r s i v ed e n s i t yb a s e dc l u s t e r i n ga l g o r i t h m ) ，该 算法基于d b s c a n 的一种改进，能智能地、动态地修改其密度参数。文【4 1 】【4 2 】 对w e b 服务器日志作用户会话聚类，得到p r o f i l e 。文 4 3 】对用户的评价记录作聚 类，作为协同过滤的先前步骤，试图弥补k - n e a r e s t - n e i g h b o r 算法的规模问题。 文 4 4 】提出k - - p a t h s 路径聚类方法。他们认为，用户对w e b 站点的访问代表了 用户对w e b 站点上页面的访问兴趣，这种兴趣可以通过用户对w e b 站点上页面 的测览顺序表现出米，k - - p a t h s 路径聚类方法根据群体用户对w e b 站点的访问 顺序进行聚类。文【4 5 】提出了基于w e b 使用挖掘进行个性化服务的框架，其中把 用户访问事务聚类和页面聚类作为框架中的一个组成部分。 由于目前网络信息杂乱的现象非常普遍，为了方便用户准确地定位所需的信 息和分流信息，因此，w e b 页面的自动分类已成为一项具有较大实用价值的关键 技术，是组织和管理网络信息的有效手段。 分类足将一个对象分到事先定义好的类中。在w e b 挖掘中，分类可以用于为 一组特定用户建立简档( p r o f i l e ) ，这需要抽取并选择最能描述这组特定用户的特 征。分类可以使用监督学习算法，如决策树【7 、n a t v eb a y e s i a n 分类器、k n e a r e s t n e l g h b o r 分类器和支持向量机、机器学习法( 包括规则归纳泫及利用b o o s t i n g 方 法解决兼类问题的技术，如b o o s t i n g 中的a d a b o o s t 。m h 和a d a b o o s t ) 。m r 算 法可用于解决多类多标签问题等。例如对服务器日志作分类，可能会发现类似这 样有趣的规则：在p r o d u c t m u s i e s u n y a n z i 在线定购的用户中3 0 年龄在1 8 2 5 岁之间，并家住在海淀区。 广西大学顾士学位论文 蚁群算 去在w e b 挖掘中的戍用研究 1 3 蚁群优化算法 社会昆虫的群体能够表现出许多令人惊讶的复杂行为。对蚁群行为的研究产 生了一个完全崭新的研究领域，现在被称为蚁群优化( a c o ，a n tc o l o n y o p t i m i z a t i o n ) 1 5 1 。 a c o 技术是最近出现的新的启发式算法，属于起源于自然的解决问题的战 略。其它的算法包括神经网络、模拟退火算法和进化算法。m a r c od o f i g o 在1 9 9 2 年他的论文【5 】中首次提出了蚂蚁系统( a s ) ，这是对a c o 方法最早的研究。蚂蚁 系统算法被首先应用到旅行商f f j 题( t s p ) “。a s 优化算法基本上是个多a g e n t 系 统，系统中单个a g e n t ( 即人工蚂蚁) 之间低层次的交互可以导致蚁群整体上的复杂 行为。 a c o 算法是受到真实蚂蚁觅食行为的启发，特别是蚂蚁如何能够找到从蚁 巢到食物源的最短路径。大家都知道个体蚂蚁之间关于路径的信息通讯的媒介是 信息素痕迹。蚂蚁开始是以一种任意的方式搜索蚁巢周围的区域，当一个独立的 蚂蚁在任意的游荡中找到食物源时，它会在地上释放出一定量的信息素。位于邻 近区域的其它任意移动的蚂蚁会察觉到这些信息素痕迹，接着它们会以很高的概 率沿着这条痕迹搜索，同时在行进的过程中释放自己的信息素，从而增强了痕迹 的浓度。越来越多的蚂蚁沿着信息素浓度高的路径行进，这条路径上信息素浓度 的进一步升高又使得其它蚂蚁沿这条路径行进的概率又进一步提高。正是这种具 有正反馈机制的自动催化过程帮助蚂蚁快速找到了最短的路线。 实验结果表明蚂蚁系统具有较强的鲁棒性和搜索较女了解的能力，但同时也存 在一些缺陷，如收敛速度慢、易出现停滞现象等。蚂蚁系统的出现引起了许多学 者的关注，针对算法的不足，提出了许多新的蚂蚁算法如蚁群系统( a n tc o l o n y s y s t e m ，a c s ) 、最大一最小蚂蚁系统( m a x m i na n ts y n e m , m m a s ) p 】和基 于排序的蚂蚁系统( r a n k - - b a s e dv e r s i o no f a n ts y s t e m ，a s r a n k ) i s 等。这些算法在 性能上有了很大的提高，很大程度上消除了搜索中的停滞现象，更适合求解高维 的n p h a r d 问题；除此之外，许多学者利用蚂蚁算法求解其它组合优化问题， 如指派问题( q u a d r a t i ca s s i g n m e n tp r o b l e m ) 9 1 ，j o b + s h o p 调度问题( j o b - - s h o p s c h e d u l i n gp r o b l e m ) “o j 、车辆由问题( v e h i c l er o u t i n gp r o b l e m ) e 1j l , 图着色问题 ( g r a p hc o l o r m gp r o b l e m ) t 1 2 j 和网络路南( n e t w o r kr o u t i n gp r o b l e m ) ”等。近年来， 一些学者提出了蚁群优化( a n tc o l o n yo p t i m i z a t i o na c o ) 这一新概念，给蚂蚁算 法提供了一个统一的框架，为蚂蚁系统的理论研究打下了坚实的基础。 4 广西大学硕士学位论文蚁群算法在w e b 挖掘中的应用研究 1 4 本文研究意义及内容安排 1 本文的研究意义 由于w e b 访问信息存在于每一台w e b 服务器上，因此其具有普遍陛，并且 遵循共同的标准。那么开展这项研究具有广泛的普遍意义。 w e b 网站记录下来的这些数据等并不是信息，其中所蕴涵的大量有益信息至 今却未能得到充分的挖掘和利用。要想使数据真正成为一个公司的资源，只有充 分利用它为公司业务决策和战略发展服务才行，否则大量的数据可能成为包袱， 甚至成为垃圾。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 挖掘中的应用研究 本章主要介绍了蚁群算法的起源、蚁群算法的原型以及为了借鉴蚂蚁行为而 建立的人工蚂蚁概念与真实蚂蚁的异同，最后，给出了蚁群聚类算法的基本思想。 第四章基于蚂蚁聚类算法的w e b 使用挖掘模型 在引出了人工蚂蚁聚类算法的w e b 页面聚类模型后，我们给出了算法实现 的各个主要部分。接着对实验数据( w e bl o g ) 的预处理进行了详细的论述。最 后是采用该方法进行w e b 页面聚类后的结果分析。 第五章基于蚂蚁算法的w e b 页面分类模型 在介绍前人基于蚁群算法的分类规则挖掘算法a n tm i n e r 3 之上，我们将该 算法首次引入到w e b 内容挖掘中。在实验设置部分，由于w e b 页面是非结构化 数据，我们采用了文本预处理的方法( w o r d n e t 和t e x t m l n e r ) 对页面进行预处 理。最后，根据实验结果，和传统的分类算法c 5 0 进行了比较。 第六章总结与展望 文章的最后总结了本文的工作，并且对w e b 挖掘这个热门研究领域的未来 发展趋势做了进一步的探讨。 1 5 本人主要工作 在本论文中，本人所作的主要工作如下； 1 分析了w e b 挖掘技术的三种分类：w e b 内容挖掘、结构挖掘和使用挖掘 的各自技术特点，总结了其研究成果。并对现有的基于w e b 挖掘的聚类和分类 技术做了深入地分析。仔细研究了蚁群优化算法的原型及为了应用于解决问题所 提出的人工蚂蚁的概念和真实蚂蚁的异同，对现有的蚁群聚类算法的优缺点进行 了分析。 2 把a n tc l a s s 蚂蚁聚类算法应用到w e b 使用挖掘的页面聚类中，并对w e b 日志进行了数据预处理工作，并分析了实验结果。 3 把a n t m i n e r 3 算法应用到w e b 内容挖掘的页面分类中，并用文本预处理 工具进行了页面预处理，并把实验得出的分类结果同传统分类算法进行了比较。 1 6 本章小结 本章先给出了沦文的研究背景：数据挖掘己成为计算机科学研究中的一个十 分活跃的前沿领域，i n t e m e t 的飞速发展，作为一个提供海量信息的源泉，进行 w e b 挖掘工作就变的非常有意义。 然后，我们简单介绍了蚁群优化算法( a n tc o l o n yo p t i m i z a t i o n ，a c o ) 及 该算法的各种应用研究。受到自然界中真实蚁群集体行为的启发，意大利学者 m d o t g o 于1 9 9 1 年在他的博士论文中首次系统地提出一种基于蚂蚁种群的新型 优化算法一一蚁群算法，并用该方法解决了一系列组合优化问题。 最后，给出了本论文的总体内容架构和本人的主要工作。 6 广西大学硕士学位论文 蚁群算法在w e b 挖掘中的应用研究 2 1w e b 挖掘概述 第二章w e b 挖掘 随着以数据库、数据仓库等数据仓储技术为基础的信息系统在各行各业的应 用，使海量数据不断产生。随之而来的问题是如此多的数据让人难以消化，无法 从表面上看出他们所蕴涵的有用信息，更不用说有效地指导进一步的工作。如何 从大量的数据中找到真正有用的信息成为人们关注的焦点。数据挖掘技术也正是 伴随着这种需求从研究走向应用。 在互联网技术的强力推动f ，w e b 己成了信息制造、发布、加工和处理的主 要平台，上面承载的数据量正在迅速膨胀。为了帮助用户在浩如烟海的w e b 中迅 速找到相关的信息，自动从w e b 文档和服务中发现和抽取信息的w e b 挖掘( w e b m i n i n g ) 技术“”己成为一个数据挖掘研究的热点。 w e b 挖掘指使用数据挖掘技术在w 啊数据中发现潜在的、有用的模式或信息。 w e b 挖掘研究覆盖了多个研究领域，包括数据库技术、信息获取技术、统计学、 人工智能中的机器学习和神经网络等。 w e b 文档和服务包含的数据，常总称为“w e b 数据”。按文献 1 5 的分类方法， w e b 数据主要分为三类： 内容数据( ( c o n t e n td a t a ) ：它是提供信息的主体，包括文本，声音，图像和 元数据。内容数据主要以各种文档形式存在，譬如t t t m l 文件和其他各种非文 本的媒体文件。内容数据的其他约定成俗的概念还有“w e b 文档”或者“w e b 页面”( w e bp a g e ) 。 结构数据( ( s t r u c t u r ed a t a ) ：它是对内容数据组织f u 派生的数据。内容数据 大部分用t t t m l 描述，超链接被广泛用于组织w e b 文档和w e b 文档内部的数据 实体。由此w e b 上就存在着由各种超链接形成的结构( 也包含超链接的描述) 。 此结构又分为站点结构和站间结构两部分。 使用数据( u s a g ed a t a ) ：它是用户使用w e b 而衍生的数据。w e b 是一个不受时 空限制的交互式媒介，可在多个层面上记录和收集因用户访问而产生的数据。 典型的方法是在w e b 服务器端收集w e b 日志，它包含了大量h t t p 协议层面的 数据。 2 2w e b 挖掘分类 根据对w 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 a g em i n i n g ) 图2 - 1 给出了w e b 挖掘的分类图。 7 广西大学硕士学位论文 蚁群算法在w e b 挖掘中的应用研究 ( 1 ) w e b 内容挖掘 图2 - lw e b 挖掘的分类图 f i 9 2 1t h ec l a s s i f i c a t i o no fw e bm i n i n g w e b 内容数据挖掘是从w e b 数据中抽取知识，以实现w e b 资源的自动检索， 提高w e b 数据的利用效率。w e b 数据分布范围很广，有f t p 上、g o p h e r 中的、数 字图书馆中的，还有企业自己w e b 网站上的，也有隐形的私人数据和动态查询的 结果数据的形式也是多样化，除了文本外还有图形、声音等。因此，多媒体数 据挖掘也是w e b 内容数据挖掘之一。这些都是非结构化的数据，人们把数据挖掘 技术用于从半结构化或非结构化文档发现有价值的信息称作k d t ( k n o w l e d g e d i s c o v e r yi nt e s t s ) ，但是，文本只是w e b 数据的一种形式，因此，k d t 也是 w e b 内容挖掘的一个特例。 ( 2 ) w e b 结构挖掘 w e b 结构挖掘是从w 啊的组织结构和链接关系中推导知识。由于文件之间的 相连，w w w 能够提供除了文件内容以外的有用信息。目前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 使用挖掘的主要目标则是从w e b 的访问记录中抽取感兴趣的模式。w w 中的每个服务器都保留了访问日志( w e ba c c e s sl o g ) ，记录了关于用户访问和交 互的信息。分析这些数据可以帮助理解用户的行为，从而改进站点的结构，或为 用户提供个性化的服务。这方面的研究主要有两个方向：一般的访问模式追踪和 个性化的使用记录追踪。一般的访问模式追踪通过分析使用记录来了解用户的访 问模式和倾向，以改进站点的组织结构。而个性化的使用记录追踪则倾向于分析 单个用户的偏好，其目的是根据不同用户的访问模式，为每个用户提供个性化的 定制站点。 2 3w e b 内容挖掘 w e b 内容挖掘是一种基于网页内容的w e b 挖掘，是从大量的w e b 数据中发 现信息、抽取有用知识的过程。这些数据对象既有文本和超文本数据，也有图形， 图像、语音等多媒体数据：既有来自于数据库的结构化数据，也有用h t m l 标 记的半结构化数据和无结构的自由文本。 w 曲内容挖掘针对的对象是w e b 文档信息和多媒体信息，就其挖掘内容而言， 又可将其分为对w e b 文本文档( 包括t e x t h t m l 等格式) 和多媒体文档( 包括 i m a g e ，a u d i o ，v i d e o 。等媒体类型) 的挖掘。对无结构的自由文本的挖掘称之为文 本的知识发现【l q 文本挖掘的结果可以是对某个文本内容的总结概括，也可以 是对整个文本集合的分类或聚类结果。基于文本的w e b 挖掘方法有数据库方法、 建立w e b 数据库仓库方法和新近的基于软件a g e n t 的分类器方法、基于概念的 文本信息挖掘方法。对多媒体文档的挖掘称之为多媒体数据挖掘【1 ”。w e b 多媒 体信息挖掘通常采用的力一法有关联规则法和特征提取法。 就其方法而言，w e b 内容挖掘可以分为两大类【l 即：信息查询( i n f o r m a t i o n r e t r i e v e ，m ) 方法和数据库方法。 m 方法主要应用取技术，评估和改进搜索信息的质量，也可以处理无结构 化数据和h t m l 标记的半结构化数据，主要应用于文本分类、聚类和模式发现 等。 数据库方法和数据仓库方法都是采用数据抽取和转换的方法将非结构化的 w e b 信息转换或映射为结构化的数据，再采用数掘挖掘技术进彳一信息挖掘。数据 库方法主要集中在对w e b 上异质的、半结构化的数据进行整合与组织，使之成 为结构化较好的、高丢的资源集合，以便进行更好的信息管理和查询。在数据库 力一法中，半结构化数据的表示一般用o e m ( o b j e c te x c h a n g em o d e l ) 模型，也可 用o i m ( o b j e e ti n t e g r a t i o nm o d e l ) 模型，用m f r o ( m i n i m a lf u l lr e p r e s e n t a t i o n o b j e c t s ) 方法实现其模式抽取o i m 是o e m 的一种变形数据模型。数据库方法 的应用集中在模式发现、多层数据库的建立或数据向导( d a t ag u i d e s ) 的建立以 及w e b 查询系统。 9 广西大学硕士学位论文 蚁群算法在w e b 挖掘中的应用研究 就其挖掘策略的不同，w e b 内容挖掘又可分为w e b 概要( 即直接挖掘w e b 文 档的内容) 和搜索引擎结果概要( 即对搜索引擎的查询结果作进一步处理，得到更 精确和有用的信息，以增强搜索引擎的内容查询功能) 。 2 4w 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 的结构和页面的结构及其蕴含在这些结构中的有用模 式；对页面及其链接进行分类和聚类，找出权威页面。这方面研究工作的代表有 p a g e - r a n k 和c l e v e r ，它们正是利用了文档间的链接信息查找相关的w e b 页。 有关这方面研究的算法有：p a g e r a n k 。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 u b a u t h o r i t y 。 2 4 1p a g e r a n k 方法 p a g e r a n k 算法是w e b 超链接结构分析中最成功的代表之一，是评价网页权 威性的一种重要工具。搜索引擎g o o g l e 就是利用该算法和a n c h o rt e x t 标记、词 频统计等因素相结合的方法对检索出的大量结果进行相关度排序，将最权威的网 页尽量排在前面。 p a g e r a n k 的基本思想是：一个页面被多次引用，则这个页面很可能是重要 的：一个页面尽管没有被多次引用，但被一个重要页面引用，则这个页面很可能 是重要的：一个页面的重要性被均分并被传递到它所引用的页面。因此，网页之 间的超链接( 引用) 在一定程度上能表明w e b 文档的重要性。网页的被点击率也是 与超链接有关的一项重要评价指标。侗具有一定欺骗性，因为一个i _ 0 9 页虽然被点 击，可能只是通往目标网贞的超链路径 二的一环，用户并非真正想浏览它。 p a g e r a n k 的理论基础是：忽略掉w e b 页面上的文本和其它内容，只考虑页 面问的超链接，把w e b 看成是一个巨大的自向图g = ( 矿，e ) ，结点v v 代表一 个w e b 页面，有向边( p ，q ) e e 代表从结点p 指向结点g 的超链接，结点p 的出 度是指从页面p 出发的超链接( o u tl i i l i 【) 的总数，而入度是指所有指向结点p 的超 链接( hi m k ) 的总数。 广西大学硕士学位论文蚁群算法在w e b 挖掘中的应用研究 p a g e - r a n k 的具体定义如下： 将w e b 对应成有向图，设w 为该有向图结 点的集合，n = 1 w l ，f 是页面指向的所有页面i 的集合，e 是指向页面i 的所有 页面的集合。对每个出度为0 的结点s ，设f = 有向图中仝部n 个节点 ，则所 有其他结点的毋= 修u s ) ，这样可以将结点s 所具有的p a g e r a n k 值均匀地传 递给其他所有页面。p a g e r a n k 的具体迭代公式( e q2 1 ) 为： 艘= ( 1 一d ) n + d 丽p r ( o ( e q 2 j ) 难毋f 。i l 其中，参数d 是取值0 到l 之间的衰减因子，因为任何一个网页的作者都认 为其它的网页不如自己的重要。d 通常被置为0 8 5a 。 p a g e r a n k 的实现过程为：将网页的u r l 对应成唯一的整数，把每一个超链 接用其整数m 存放到索引数据库中，经过预处理( 如去除数据库中的悬摆指针) 之后，设每个网页的初始p r 值为l ，通过以上的递归算法计算每一个网页的 p a g e r a n k 值，反复进行迭代，直至结果收敛。 2 4 2h u b a u t h o r i t y 方法 现实中当我们搜索某个给定话题的w e b 页面时，不仅希望得到相关的w e b 页面，而且希望检索到的w e b 页面是权威w e b 页面。也就是说，检索到的页面 具有高质量，或对该主题具有权威性。由于w e b 链接结构对于实现这些需求存 在很人的局限性，人们提出了另外一种重要的w e b 页面，称为h u b 页面。h u b 页面是指一个或多个w