(计算机应用技术专业论文)基于蚁群算法的web挖掘技术的设计与实现.pdf_第1页
(计算机应用技术专业论文)基于蚁群算法的web挖掘技术的设计与实现.pdf_第2页
(计算机应用技术专业论文)基于蚁群算法的web挖掘技术的设计与实现.pdf_第3页
(计算机应用技术专业论文)基于蚁群算法的web挖掘技术的设计与实现.pdf_第4页
(计算机应用技术专业论文)基于蚁群算法的web挖掘技术的设计与实现.pdf_第5页
已阅读5页,还剩47页未读 继续免费阅读

(计算机应用技术专业论文)基于蚁群算法的web挖掘技术的设计与实现.pdf.pdf 免费下载

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

摘要 本文通过研究现有的w e b 挖掘中聚类和分类技术的基础上,将一种基于蚁群 优化的分类算法应用于w e b 内容挖掘的页面分类中:并引入一种基于改进的蚁 群算法应用于w e b 使用挖掘的用户事务聚类中。实验结果表明:与传统算法相 比较,基于蚂蚁的聚类和分类算法在w e b 挖掘中具有一定的优势。 本文首先在对w e b 挖掘过程进行分析的基础上,详细地分析了w e b 挖掘中 聚类和分类的现有技术的优缺点。深入讨论了几种改进的蚁群算法,在分析了现 有算法应用于w e b 挖掘技术上的不足之后,本文将一种基于蚁群优化的分类算 法a m m i n e r 3 应用到w e b 内容挖掘中的页面分类上,并进行了非结构化数据集 的处理。通过实验分析,得出了分类规则的准确率和简洁性同传统分类算法c 5 o 进行了对比:a 玳一m i n e r 3 算法的分类规则在准确率和简洁性方面更优。 最后,引入了一种改进的蚁群算法( i m p r o v e da n tc o l o n ya l g o r i t h m ,i a c a ) ,并 给出了基于i a c a 的聚类分析模型,继而对相应的算法进行实现,并应用到、e b 使用挖掘的聚类模型上。通过实验仿真,该聚类算法在聚类过程中,能够很好地 避免算法出现停滞,并且较好地解决了全局优化的问题,使聚类的整体性能达到 最优。 关键词:w e b 挖掘;蚁群算法;w e b 内容挖掘;w e b 使用挖掘;分类;聚类 a b s t r a c t t h ep f o g f e s so fc l u s t e r i n ga n dc l a s s i f i c a t i o ni nw e bm i n i n gw a sr e s e a r c h e di n t h ep a p e r ac 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 t c o l o n yo p t i m i z a t i o nw a sa p p l i e d i 藏t 纛ep r o e e s s i 藏go fw e bp a g ec l 鑫s s l 蠡c a t i 矬i 露w e b c o 最e 蠢t 街i 露j 数g ,m o 愆o v e f 。鑫+ c l u s t e r i n ga l g o r i t h mb a s e do na ni n l p r 0 v e da n tc o l o n ya l g o r i t h mw a su s e di nt h e f o c e s s i 纛go fw e b 毽s e fe l 毪s l e f i 建gi 建w e b 挂s a g el 臻i 纛i 矗g t 魏el 零s 轻l l s h o w 纛a ,i 珏 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 ga n dc l a s s i f i c a t i o n a l g o r i t h mb a s e do n a 毅h a b i h a v ec e r t a i ne o l 建p a f a t i v ea d v a n t a g e si nw e b m i n i n g f i r s lo fa l li nl h ep r o c e s so fw e bm i n i n gw a sa n a l y s e di nt h i sp a p e f ,ad e t a i l e d a n a l y s i s o fw e bm i n i n g c l u s t e r i n g a n dc l a s s i f i c a t i o np fh e a d v a 丑t a g e sa n d d i s a d v a 蕺t a g e so fe x i s t i n gt e c | l n o l o g y 。d i s c u s s i o no f 鑫n 醅l n b e ro fi m p f o y e da n t c o l o n ya l g o r i t h m ,a f t e rt h ea n a l y s i so ft h ee x i s t i n gw e bm i n i n ga l g o r i t h mw a sa p p l i e d l o 圭魏e | o e 魏鑫i e 鑫耋纛e 萎c i e 纛c i e s ,a 嚣o v e le l a s s i 鑫c a l i o 纛鑫l g o 蠢纛l 旌曩a l 鞋o da 磊ll 暖i 藏e f 3 b a s e do na n tb 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 am i n i n gt a s k w a se x p l o i 乏e dl ow e bp a g ec l 鑫s s i 蠡c a i o no fw e be q 瓤t e 薹l lm i 娃i n ga n dl h ep f o c e s so f n 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 c o i n p a r e dw 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 l nc 5 o ,t h ea l g o f i l 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 ff u l e s an e wc l u s t e r i n g a n a l y s i sl n e t h o d , w h c l lb a s e do nl l n p f o v e da n lc o l o n y a l g o r i t h m ,w a sp u tf o r w a r di nt h i sp a p e r ,w h i c hi sn a m e di a c af o rs h o r t t h e a 毽l 量l o ff e a l i z e st b e 薹l 曩p l 蛩v e da n c o l o 珏ya l g o f i l 魏l 鞋( 薹a c a ) 嚣纛dd e s i g 稳a ne l 纛毽l a l o f 。 w i t ht h ee m u l a t o r ,t h ei a c ai sc o m p a r e dw i t ho t h e rc l u s t e r i n ga n a l y s i sa l g o r i t h m s : c 鑫戮鑫v o i d 囊es 鑫g 蕤鑫i 0 嚣fl 囊ea l 鬈。砖l 蠢l 纛,a v i dl 基ep 鑫f s 糕p e f i o f 蠢跫da a i 纛h e o v e r a l le x c e l l e n to p t i m i z a t i o n s oi tc a nm a k et h ew h o l e c a p a b i l i t yo fi a c at oa t t a i n o p l i m i z a i o n 。 k e y 弼o r d s :w e bm i n i n g ;a n lc o l o n ya l g o r i t h m ;w e bc o n t e n tm i n i n g ;w e bu s a g e l 涯i n i n g ; c l u s l e r i n g ;c l a s s i f i c a t i o n 长沙理工大学 学位论文原创性声明 本人郑重声明:所受交的论文是本入在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外,本论文不包含 任何其他个人或集体已经发表或撰写的成果作品。对本文的研究徽描重 要贡献的个人和集体,均已在文中以明确方式标明。本人完全意识到本 声明的法律后果由本人承担。 作者签名:羡特翘嗍刁年僻日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定,同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版,允许论 文被查阅和借阅。本人授权长沙理工大学可以将本学位论文的全部或部 分内容编入有关数据库进行检索,可以采用影印、缩印或扫描等复制手 段保存和汇编本学位论文。 本学位论文属于 薹、保密口,在年解密蒿适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“) 作者签名: 导师签名: 暑期:爿年否月乒透 霉期: 矽年多胃尹墨 ? v i 第一章绪论 随着w e b 页面的急剧增长,以及在信息共享和电子商务方面的广泛应用, i n t e r n e t 已成为世界上最丰富的信息来源。为了让搜索引擎能更好地对这些大量、 无序的信息进行检索,让用户能更清楚地了解网站的作用,提升网络信息处理与 组织技术,w e b 挖掘( w e bm i n i n g ) 就是在这样的环境下产生的,它旨在从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 使用挖掘。它们分别挖掘网页站点文件内 容、结构和使用信息,并且已经在很多方面得到实现,如在搜索引擎和建立数据 仓库等方面都起着很重要的作用。 1 1 课题背景及研究意义 w o r l dw i d ew e b 的迅速发展,电子商务的发展为网络应用提供了强大的支 持。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 数据,并且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 研究现状及现状分析 ( 1 ) w e b 挖掘中的聚类和分类 聚类是w e b 挖掘的关键技术之一。它是从w e b 的访问数据中聚类出相似特征 的事务的过程。在w e b 使用挖掘中,可以进行两种类型聚类:使用聚类和页面聚 类。使用聚类就是将所有用户分为若干组,并将其量化,其中具有相似浏览模式 的用户c 1 u s t e r 就归为一组。这类规则对于电子商务和为用户提供个性化的服务是 非常重要的。页面聚类可以找出具有相关内容的页面组,这对于搜索引擎的发展 和用户上网帮助都是非常有用的。使用聚类和页面聚类就是通过对用户查询或访 问产生的历史信息所形成的h t m l ,来向用户提供超链接。 分类是w e b 挖掘的另一关键技术,它是对新添加的数据进行分类并将一个对 象分到事先定义好的类中,根据用户群的特征来挖掘出用户群的访问特征。在 w e b 挖掘中,分类可以通过访问用户信息而得到的一些用户特征,这需要抽取并 选择出最好地描述这组特定用户的特征,并根据这些特征对用户进行分类。常使 用监督归纳学习算法来进行分类,如决策树、k 邻近分类法和支持向量机、机 器学习法、贝叶斯分类方法等。 ( 2 ) 蚁群算法 社会昆虫的群体能够表现出许多令人惊讶的复杂行为。对蚁群行为的研究产 生了一个完全崭新的研究领域,现在被称为蚁群优化( a c o ,a n tc o l o n y o p t i m i z a t i o n ) 引。 a c o 技术是最近出现的新的基于群体智能的算法,并在很多领域都已取得了 成功的应用。其算法起源于自然解决问题的思想,m a r c od o r i g o 在1 9 9 2 年他的论 文h 3 中首次提出了蚂蚁系统( a s ) ,这是对a c o 方法最早的研究。并且在解决旅行 商问题( t s p ) 哺1 、q q p 、j o b s h o p 调度等问题取得了成功的效果。a s 优化算法 采用了分布式计算方法,具有多代理性和较强的鲁棒性,在于单个代理之间的交 互容易增加蚁群整体上的复杂性。 2 a c 0 算法是受到蚂蚁寻找食物的启发,蚂蚁如何能够找到最短路径。这得归 功于蚂蚁之间相互进行信息通讯的信息素,另外还要归功于环境。信息素多的地 方经过的蚂蚁就会多,假设蚂蚁开始是以一种相同的方式进行搜索路径,并且在 搜索过程中会在地上释放出一定量的信息素,当蚂蚁到达终点后返回,短的路径 蚂蚁来回一次时间比较短重复的频率快,所以它们会以很高的概率沿着这条痕迹 搜索,同时继续在搜索路径的过程中释放自己的信息素,因而在单位时间内走过 该路径的蚂蚁数目就多,释放的信息素也自然多,使得这条路径上信息素浓度的 进一步升高,越来越多的蚂蚁聚集到这条较短的路径上来,正是这种具有正反馈 性的过程使得最短的路径就近似被找到了。 蚂蚁系统具有较强的鲁棒性和并行性,结合了正反馈机制和分布式计算,使 其具有搜索较优解的能力,但同时也存在一些缺陷,比如容易陷入局部最优、且 易出现停滞现象等。蚂蚁系统的出现引起了许多中外学者的关注,并把蚁群算法 的研究推向了国际水平,针对该算法的不足,提出了许多新的改进蚁群算法并且 很大程度上消除了搜索中出现的停滞现象和局部最优问题,在当前很多国际学术 报告上,蚁群算法已经成为一个广受关注的研究热点话题。 1 3 本文的架构 论文中很系统地分析和论述了w e b 挖掘中的各项技术。在此理论基础上,引。 入了改进的蚁群算法,并将其成功应用于w e b 挖掘的聚类和分类上。论文的整体 构架如下: 第一章绪论 介绍了本课题的研究背景,主要内容和论文的组织结构 第二章基于蚁群算法的w e b 挖掘理论 介绍了w e b 挖掘理论,在论述了w e b 挖掘过程的基础上,详细地分析了w e b 挖掘中聚类和分类技术。然后分析了蚁群算法及几种改进的蚁群算法的思想。最 后,对现有算法应用于w c b 挖掘技术上存在的问题做了详细地论述。 第三章基于蚁群算法在w e b 挖掘技术上的模型设计 在分析了现有算法在w e b 挖掘技术上存在不足的基础上,本章提出了基于蚁 群算法在w e b 挖掘分类和聚类模型的设计,为后两章的应用实现打下基础。 第四章基于蚁群算法在w e b 内容挖掘分类模型的实现 在介绍基于蚁群算法的分类规则挖掘算法a m m i n e r 3 之上,我们将该算法首 次引入到w e b 内容挖掘中。在实验设置部分,由于w e b 页面是非结构化数据,我 们采用了文本预处理的方法( w o r d n e t 和t e x t m i n e r ) 对页面进行预处理,最后, 与传统的分类算法c 5 o 进行比较。 第五章基于改进的蚁群算法在w e b 使用挖掘聚类模型的实现 3 分析了w e b 挖掘的含义和相关技术的基础上,引入随机扰动和蚂蚁的感觉知 觉特征,结合k 一均值算法,从而提出了改进蚁群算法( i a c a ) ,根据改进蚁群算法 的聚类分析模型,将该模型用算法实现。并将该模型首次引入到w e b 使用挖掘的 用户聚类中。实验表明,以上的技术和方法无论在算法性能还是聚类效果上都比 其它算法有着更好的结果。 第六章总结与展望 总结了本文的研究工作,提出进一步研究的方向。 4 第二章基于蚁群算法的w e b 挖掘理论 2 1w e b 挖掘 w e b 挖掘是一项综合技术,涉及统计学、信息获取技术、机器语言学等多个 领域。从不同的领域出发,其对w e b 挖掘的理解也是不同的。w e b 挖掘实质上是 实现从w e b 资源中挖掘那些隐藏的、有潜在的有用模式和信息的过程。 w e b 数据挖掘的基本原理的处理过程如图2 1 所示。从w e b 网站的结构和内容 上提取出满足用户需求的目标数据集,w e b 挖掘主要是在这些数据集中进行数据 提取;通过将目标数据集中错误和冗余的数据进行清理( 预处理) ,经预处理的 数据通过模式发现,把数据转换成有效形式( 模式、规则、统计结果) ,最终得 到用户感兴趣的模型;模式分析是从一批数据中寻找普遍关系的过程,对现有的 模式进行解释,反复提取并返回前面处理过程中的一些步骤,最后向用户提供一 些易于接受和理解的知识。 图2 1w e b 数据挖掘原理图 2 1 1w e b 挖掘分类及架构模型 2 1 1 1 分类 根据挖掘的对象不同,我们将其分类三类:w e b 内容挖掘、w e b 结构挖掘和 w e b 使用挖掘。w e b 数据是非结构化的、动态的且没有统一的结构模式,即包含 不同格式( t e x t 、a u d i o 、v i d e o ) 等。要在动态而又存在大量冗余的数据中挖掘出 有用的、潜在的东西是一种挑战,所以当前基于w e b 的数据挖掘具有很重要的研 究前景。 ( 1 ) w e b 内容挖掘:是指对w e b 文档内容的总结概括以及对搜索过程中发现 的有用信息进行藐视。挖掘的对象是w e b 文档信息和多媒体信息,主要分为数据 库方法和信息查询方法两种; 5 ( 2 ) w e b 结构挖掘:是指对w e b 文档的结构进行挖掘并从中发现潜在的模式 的过程。w e b 结构挖掘最常用的算法有p a g e r a n k 算法和h i t s 算法,挖掘的对象是 w 曲页面本身之间的超链接: ( 3 ) w e b 使用挖掘:它是通过挖掘相关服务器的日志文件来发现用户访问页 面的模式,如统计分析、关联规则、序列模式、分类和聚类。将访问记录数据通 过预处理传给传统关系表中,并通过挖掘算法对关系表数据进行挖掘。我们将 w 曲使用挖掘分为五类:个性挖掘、系统改进、站点修改、智能商务、w e b 特征 描述,其改进的拓扑结构为电子商务的发展提供了强大的支持。 2 1 1 2w e b 挖掘架构模型 w 曲挖掘技术具有许多优点,如不需要用户提供主观的评价信息,可以处理 大规模的数据量,用户访问模式动态获取,不会过时等。但是与传统数据库和数 据仓库相比,w e b 是一个巨大、分布广泛、全球性的信息服务中心,涉及经济、 文化、教育、新闻、广告、消费、娱乐、金融、保险、销售、电子商务等信息, 内容极其丰富,数据最大特点就是半结构化;而传统的数据库中的数据结构性很 强,即其中的数据为完全结构化的数据。其基本架构如图2 2 所示: 6 输 预 处 理 站点文件 访问日志连接日志询问日志 b 程a g c 。日志 一。k 二、 页面分类拓扑结构 r 用户文件 7 l j刀个、 一 r 个 务识扒 譬 r 模上l譬 土1 【 l 序列模式 页面聚类 联规则 使用数据 化厂仑 有趣的规则、模式和统计数据 图2 2 - e b 挖掘的基本架构 2 1 2w e b 挖掘过程 2 1 2 1w e b 内容挖掘的基本过程 w c b 内容挖掘从用户的角度出发挖掘出w e b 文本信息和多媒体信息,提高信 息质量,对无结构的动态文本进行集成、建模来实现知识发现并对w e b 数据进 行复杂查询。将w e b 内容挖掘分为两大类1 引:资源查找( i n f o r m a t i o nr e t r i e v e ,i r ) 方法和数据库( d a t a b a s e ) 方法。 7 入l 妙 几”v知识发几v模式分析 i r 方法主要用来挖掘非结构化文档,处理非结构化数据( 小说、新闻等) 或半 结构化数据( h t m l 、超链接) ,其中还包含了文本分类、聚类以及各文档之间的 关系,提出了半结构化数据中的规则和模式。 数据库方法主要是为了解决w e b 服务器上数据的查询以及管理问题。数据库 方法主要是对w e b 上非结构化、半结构化的数据进行整合与处理的过程,使其 得到较好的资源集合。主要是基于半结构化数据进行研究的,半结构化数据用 o e m ( o b i e c te x c h a n g em o d e l ) 模型来实现并表示成标志图。由于数据的表达方式 特殊,所以需要数据向导和多层数据库的建立来实现。 2 1 2 2w e b 使用挖掘的基本过程 w e b 使用挖掘是从w e b 日志数据中获取有价值的信息或模式的过程,也即是 对用户访问w e b 站点时在服务器留下的访问记录进行挖掘的过程。其主要目的是 发现用户访问站点的浏览模式,关注的是如何从w e b 数据中挖掘出有意义的关联 规则、序列规则、聚类分析、依赖模型等知识类型。一般而言,w e b 日志数据挖 掘可以分为预处理阶段、挖掘算法实施阶段和模式分析阶段,如图2 。3 所示: o 1 日志文i ii u 图2 3w e b l 更用挖掘过程 ( 1 ) 数据预处理 w e b 使用挖掘首先要对挖掘数据进行预处理,其目标是将包含在多种数据源 中的信息转化为适合数据挖掘和模式发现所必需的数据抽象概念,然后在事务数 据库上实施挖掘算法,以期最终获得有价值的规律。预处理主要对用户访问日志 进行数据清洗( d a t ac l e a n i n g ) 、用户唯一性识别( u s e ri d e n t i f i c a t i o n ) 、用户 会话识别( i d e n t i f yu s e rs e s s i o n ) 、路径补充( p a t hc o m p l e t i o n ) 和事务识别 ( t r a n s a c t i o ni d e n t i f i c a t i o n ) 等处理1 。 ( 2 ) 模式识别 在对事务进行了划分后,就可以根据具体的分析需求选择访问模式发现的技 术。由于目标的不同,所采用的技术也有所不同。如路径分析、关联规则挖掘、 时序模式、聚类和分类技术。路径分析( p a t ha n a l y s i s ) 可以用来发现w e b 站点中 8 最经常被访问的路径,从而可以调整站点的结构。在w e b 日志挖掘的环境下,关 联规则挖掘的目标是发现用户对站点各页面的访问之间的关系,这对于电子商务 是非常有用的。时序模式的发现,各种聚类和分类技术的采用对于w e b 日志中的 模式发现都有其各自的作用。 1 ) 统计分析 统计方法是从w e b 中提取有用信息最常用的一种技术。通过对s e s s i o n 文件的 分析,可以对感兴趣的信息进行统计。一般的包括各种统计数据,如最频繁访问 的n 个页面、每页平均浏览时间、网址路径平均访问长度等,也可能涉及一些关 于限制的错误分析,如统计非法i p 、无效u r l 和未授权访问等。这些信息对于提 高系统性能,加强网站安全起到辅助决策作用。 2 ) 关联规则 在w e b 日志挖掘中,关联规则主要用于发现用户之间、页面之间以及用户浏 览页面和网上行为之间存在的潜在关系。 3 ) 序列模式 序列模式挖掘目的是发现含有时间戮的事务间的关联关系。在w e b 服务器事 务日志中记录的是一段时间内的用户访问行为,那么在数据预处理阶段,每个事 务都会附带一个时间片,称为时间戳。w e b 日志数据的序列挖掘,可以帮助研究 人员预测用户访问行为。 4 ) 分类 。 分类算法首先建立一个模型,通过对训练数据的分析,给出预定数据类集或 概念集的特征描述,然后抽取未知数据对象的自身特性,根据模型中的定义,将 其划分到相对应的类别中。 5 ) 聚类 聚类技术将数据对象按特征相近的原则划分为多个类或簇。在w e b 日志挖掘 领域有两种有趣的聚类:用户聚类和页面聚类。用户聚类就是将那些经常访问相 同页面的用户群划分出来,他们具有相同的使用习惯和网上行为,可以对他们开 展特定的广告策略或是个性化定制。页面聚类则发现内容相关的页面组,为搜索 引擎和w e b 服务商提供有用信息。 ( 3 ) 模式分析 如果没有合适的工具和机制来辅助分析人员的理解,采用各种技术挖掘出来 的模式,数目庞大,表达晦涩,从而得不到很好的利用。因此,模式分析技术和 工具也是近年来研究w e b 使用挖掘的一个新热点。这些技术主要包括以下几个方 面: 1 ) 可视化技术 可视化良好的系统用图形和图像表示抽象网络中错综复杂的关系,用文字描 9 述、解释和阐述模式之间相互的作用,帮助人们更好地理解w e b 中海量数据各部 分之间的关系,指导和加速查找的过程。 2 ) 联机分析工具 o l a p ( o n l i n ea n a l y t i c a lp r o c e s s i n g ) 在基于多维数据模型的数据仓库或数据 集市上使用,目标是满足决策支持或者满足在多维环境下特定的查询和报表需 求,它将传统数据以多维数据模型重新组织,然后通过上卷、下钻、切片和切块、 旋转等操作实现对多个抽象层上的知识发现。 3 ) 知识查询机制 知识查询机制首先分析查询目的,然后自动搜索相关的规则、模式以及其它 的知识,可以帮助分析用户目的,用智能的方式回答查询。 2 1 3w e b 挖掘技术 2 1 3 1 聚类 聚类技术是对符合某一访问规律特征的用户进行用户特征挖掘。聚类分析可 以从w e b 访问信息数据中聚类出具有相似特征的那些客户,可实现自动给一个特 定的顾客聚类发送销售邮件,为一个顾客聚类动态地改变一个特殊地站点等。在 w e b 使用挖掘中,存在两种类型的聚类:使用聚类( 用户聚类) 和网页聚类。用户 聚类主要是把所有用户划分为若干组,具有相似特性( 或浏览模式) 的用户分为一 组。这类知识对电子商务和为用户提供个性化的服务特别有用。网页聚类可以找 出具有相关内容的网页组。这对网上搜索引擎及提供上网帮助的应用特别有用。 上述两类应用都能根据用户的询问或过去所需信息的历史生成静态或动态 h t m l ,从而向用户推荐相关的超链接。 1 w e b 挖掘对聚类的要求 聚类是一个富有挑战性的研究领域,它的潜在应用提出了各自特殊的要求。 w e b 挖掘对聚类的典型要求如下: ( 1 ) 可伸缩性 许多聚类算法在小的数据对象集合上工作的很好:但是一个大规模服务器日 志库可能包括几百万条记录,在这样的大数据集合样本上进行聚类可能会导致有 偏差的结果。我们需要具有高度可伸缩性的聚类算法。 ( 2 ) 处理不同类型属性的能力 许多算法被设计用来聚类数值类型的数据。但是,应用可能要求聚类其他类 型的数据,如二元类型、分类标称类型、序数型数据,或者这些数据类型的混 合。 ( 3 ) 发现任意形状的聚类 1 0 许多聚类算法基于欧几里得距离或者曼哈坦距离度量来决定聚类。基于这样 的距离度量的算法趋向于发现其有相近尺度密度的球状簇。但是,一个簇可能是 任意形状的。提出能发现任意形状的算法是很重要的。 ( 4 ) 处理噪声数据的能力 绝大多数现实世界中的服务器日志库中都包含了孤立点、空缺、未知数据或 者错误的数据。一些聚类算法对于这样的数据敏感,可能导致低质量的聚类结果。 ( 5 ) 对于输入记录的顺序不敏感 同一个数据集合,当以不同的顺序提交给同一个算法时,可能生成差别很大 的聚类结果。开发对数据输入顺序不敏感的算法具有重要的意义。 ( 6 ) 高维性 一个数据库或者数据仓库可能包含若干维属性。许多聚类算法擅长处理低维 数据,可能只涉及两维或三维。人类最多在三维的情况下能够很好地判断聚类的 质量。在高维空间中聚类数据对象是非常有挑战的,特别是考虑到这样的数据可 能非常稀疏,而且高度偏斜。 ( 7 ) 可解释性和可用性 用户希望聚类结果是可解释的,可理解的,和可用的。 2 w e b 挖掘中的聚类技术 聚类是将具有相似特征的对象聚成一个c l u s t e r 。在同一个簇中的对象具有较 高的相似度,而不同簇中的对象差别较大。通过聚类,人们能够识别数据对象密 集的和稀疏的区域,因而发现全局的对象分布模式,以及数据属性之间的相互关 系。在商务上,聚类能帮助市场分析人员从客户信息库中发现不同的客户群,并 且用购买模式来刻画不同的客户群的特征。为了便于寻找目标用户的相似用户, 聚类模型首先将现有的用户按照一定的方法分成为多个类或簇,这样具有相似爱 好的客户分配到相同的簇中,根据目标用户所在簇的对某商品的评价得到目标用 户对该商品的评价,有些算法将目标用户分配到多个簇中,根据与所在簇的关系 强度进行综合考虑计算。由于对大型数据集产生最佳的聚类是不现实的,因此在 实际应用过程中使用贪婪聚类生成的方法,这些方法首先形成各个分类,每个分 类常常仅包含一个任意选择的用户,然后反复地将剩余用户分配到不同的簇中, 这期间可能产生新的簇,也可能将不同的簇进行合并等。由于聚类模型只是将目 标用户与一定数量的簇进行比较而不是整个用户集,因此在扩展性和实现性能上 比传统的协同过滤技术略显优势,而且聚类计算可以离线进行。 ( 1 ) 基于u r l u s e r i d 关联矩阵的用户聚类算法n 2 1 典型的w e b 日志文件包括用户的i p 地址、访问时间、请求方式、被访问页面 u r l 、数据传输协议、返回码、传输的字节数等。对w e b 日志预处理主要由两部 分构成:数据清洗( d a t ac l e a n i n g ) 和事务识别( t r a n s a c t i o ni d e n t i f i c a t i o n ) 。 通过对日志进行恰当的预处理,可得到用户i d ( u s e r i d ) 、用户i p 地址( u s e r i p ) 、 用户请求的u r l 以及用户浏览时间等。以客户访问u r l 为行,u s e r i d 为何可建立 u r l u s e r i d 关联矩阵u ,其元素值为用户访问次数。矩阵中的元素值触i ,是指 第j 个用户在一个用户会话中访问第i 个u r l 的次数,矩阵中的列向量表示所有用 户对某一u r l 访问情况,也反映用户访问模式的共性,而行向量则表示某一用户 对所有u r l 访问的情况,也反映了用户访问路径。基于u r l u s e r i d 关联矩阵, 对矩阵的列向量进行相似性比较,具有相似访问模式的用户即定义为一类。聚类 算法如下:对于v 阢; o ,可对其进行预处理,令阢;= 1 ,然后计算列向量间的 h a m m i n g 距离( h a m m i n g 距离可定义为v 订【o ,l 】“,n 1 ,有x ,y 间的h a m m i n g 距离日j ( x ,y ) = j 鼍一zi ,建立基于u r l u s e r i d 关联矩阵的列向量间的距离矩 阵u 肌 ,其元素值定

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论