（计算机应用技术专业论文）基于遗传算法的web关联规则挖掘的研究与设计.pdf

基于遗传算法的w e b 关联规则挖掘的研究与设计 摘要 摘要 本文提出一种基予遗传算法的w e b 用户聚类和关联分析方法， 研究如何从用户与w e b 服务器的交互中发现隐含的规律、知识。旨 在通过数据挖掘、遗传算法，得到描述用户行为特征的聚类划分和关 联规则，为用户的个性化服务提供知识依据。 本文所述系统以w e b 访问日志、站点拓扑结构作为数据挖掘数 据源。通过对w e b 的拓扑分析和基于遗传算法聚类技术，对用户群 体进行聚类，以每一类用户为分析对象，挖掘出每一类用户的关联规 则。运用遗传算法、增量挖掘技术对用户的访问行为进行跟踪，优化 已挖掘出的关联规则，并对描述用户行为特征的关联规则进行预测， 从总体上提高了关联挖掘的精确度和适应性。 在本文最后，给出了相应的实验数据分析，总结了遗传挖掘的特 点，并进一步讨论了未来的研究方向。 关键字：数据挖掘，w e b 行为挖掘，遗传算法，关联规则，用户聚类 作者：汤亚玲 指导教师：崔志明 a b s t r a c t t h i s p a p e rp r e s e n t s am e t h o do fc l u s t e r i n go nw e bu s e r sa n d a n a l y s i s o fa s s o c i a t i o nb a s e do ng e n e t i ca l g o r i t h m ，w h i c h d o e sr e s e a r c h o ni n t e r a c t i v ed a t ab e t w e e n aw e bs e r v e ra n di t su s e r st of i n do u ti m p l i c i t r u l e sa n dk n o w l e d g e t h r o u g hd a t am i n i n ga n dg e n e t i ca l g o r i t h r n ，i ta i m s t og e tc l u s t e rp a r t i t i o na n da s s o c i a t i o nr u l e st h a td e s c f i p e st h ew e b u s e r s b e h a v i o u ra n dc a n p r o i v d ek n o w l e d g e f o r p e r s o n a l s e r v i c e s t h e s y s t e m d i s c u s s e di nt h i sp a p e rg e t sd a t af r o mw e bl o g sa n dw e b s i t e t o p o l o g y b ya n a l y z i n g t h e t o p o l o g y o fw e bs i t ea n dc l u s t e r i n g t e c h n o l o g y w h i c hi sb a s e do ng e n e t i ca l g o r i t h m ，i ti m p l e m e n t sc l u s t e r i n g t h ew e bu s e r sa n dm i n i n g t h ea s s o c i a t i o nr u l e so fc l u s t e ru s e r s i ta p p l i e s g e n e t i ca l g o r i t h m ，i n c r e m e n t a lm i n i n gt e c h n o l o g yt o t r a c eu s e r sa c c e s s b e h a v i o u ra n do p t i m i z e sa s s o c i a t i o nr u l e st h a th a v eb e e nj u s tm i n e d ，a n d f o r e c a s t c a p a b l e a s s o c i a t i o nr u l e sw h i c hi m p r o v e s i t s p r e c i s i o n a n d a d a p t a b i l i t y f i n a l l y , t h i sp a p e rg i v e s o u tt h ed a t aa n a l y s i s o f s u m m a r i z e st h ec h a r a c t e r i s t i c so fg e n e t i cm i n i n g t h e n w ec a nd oi nt h ef u r t h e rr e s e r a r c hw o r k e x p r i m e n ta n d i t e x p e c t sw h a t k e y w o r d s ：d a t am i n i n g ，w e b b e h a v i o u rm i n i n g ，g e n e t i ca l g o r i t h m ， a s s o c i a t i o nr u l e ，u s e rc l u s t e r i n g i i w r i t t e n b y t a n g y a - l i n g s u p e r v i s e db y c u iz h i m i n g y 6 4 5 7 4 4 苏少i i 大学学位论文独创性声明及使用授权声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立 进行硼究工作所墩得的成果。除文中已经注明引用的内容外，本论文 彳i 含其他个人或集体已经发表或撰写过的研究成果，也不含为获得苏 州大学或其它教育机构的学位证书而使用过的材料。对本文的研究作 出重要贡献的个人和集体，均已在文中以明确方式标明。本人承担本 声明的法律责任。 研究生签名：逸壁选 曰 期：盘翌垦筐 学位论文使用授权声明 苏、i , i 大学、中国科学技术信息研究所、国家图书馆、清华大学论 文合作部、中国社科院文献信息情报中心有权保留本人所送交学位论 文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论 文。本人电子文档的内容和纸质论文的内容相一致。除在保密期内的 保密论文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的 全部或部分内容。论文的公布( 包括刊登) 授权苏州大学学位办办理。 研喜篇篓耄襄多骘翥f 兰 0 专扩j 薹 肇十遗传算法的w e b 关联规则挖掘的研究与设计 1 1 论文背景 第一章引言 二十一世纪是信息时代，迅速发展的i n t e r n e t 技术让世界变得 更加贴近每一个人，人们尽情享受着i n t e r n e t 所带来的各种便利与 高效，而基于i n t e r n e t 的w e b 技术的兴起与发展让人们生活得日益 丰富多彩，在i n t e r n e t 上更加流连忘返。有统计数据表明，世界上 每年w e b 服务器数量都以超过3 5 的比例增长，w e b 页面以7 0 的比 例增长，在我们每个用户面前汇成了一个信息的海洋。如何能够在最 短的时间内找到最适合自己的信息，已越来越成为用户和各运行商日 益关注的事情。如何提高w e b 服务质量，了解访问者在网站的活动情 况，如何从庞大的用户群的数据海洋中挖掘客户活动信息，让用户可 以得到个性化的服务，正在成为前沿研究课题之一。 本课题作为基于数据挖掘“。5 1 的智能w e b 服务系统的数据分析部 分，旨在通过遗传算法、数据挖掘技术，从用户与w e b 服务器的交互 数据中发现用户访问过程中隐含的的知识、规律，得到用户的访问模 式和用户的兴趣，实现用户聚类以及挖掘基于用户行为的关联规则， 为用户的个性化服务提供知识依据。 1 2 研究动态与发展趋势 遗传挖掘的研究现状： 国外：结合遗传算法的数据挖掘已成功应用在一些商务数据的挖 掘上，在w e b 数据挖掘挖掘上也建立了一些实验模型“，“。 如：o r o b u s tm u l t i r e s o l u t i o nw e bu s a g em i n i n gw i t hg e n e t i c n i c h ec l u s t e r r a g h uk r i s h n a p u r a m i b mi n d i ar e s e a r c hl a b ，e t c u s i n gg e n e t i ca l g o r i t h m sf o rd a t am i n i n go p t i m i z a t i o n i na ne d u c a t i o n a lw e b b a s e ds y s t e m t 基于遗传算法的w e b 关联规则挖掘的研究与设计 g e n e t i c a l g o r i t h m s a n d a p p l i c a t i o ng r o u pm i c h i g a n s t a t eu n i v e r s i t y 国内：主要集中在遗传算法理论与数据挖掘领域的探讨上，建立了 一些基本的数据挖掘问题计算模型，如在聚类过程中采用遗传计算技 术。 数据挖掘是一门新兴的数据处理技术，涉及数据库技术、人工智 能、机器学习、神经网络等学科。遗传算法作为一种模拟自然进化思 想的启发式全局寻优算法，是进化计算的杰出代表，也是机器学习的 重要方法。将遗传算法引入数据挖掘领域的越来越引起学术界的重 视，国外已经有不少成功的范例，如：将遗传算法与数据挖掘的聚类 算法进行整合，发挥遗传算法启发式全局寻优、和并行模式处理的计 算优势，寻求最优聚类；将遗传算法与关联规则挖掘算法相结合，挖 掘关联规则并且对关联规则进行优化、预测；将遗传算法应用于由产 生式规则构成的知识树的优化等。 随着数据挖掘应用领域的不断拓展，i b mi n d i ar e s e a r c hl a b 和 m i c h i g a ns t a t eu n i v e r s i t y 首度将遗传算法引入基于w e b 的数据挖 掘上，为w e b 数据挖掘提供了一个崭新的思考模式，虽然i b m 和 m i c h i g a n 并未给出具体的技术细节，但是仍然给人们对于处理复杂 的w e b 的数据挖掘问题时指出了一个新的研究方向。 1 3 研究目标 本课题是基于数据挖掘的智能w e b 服务系统的数据分析部分，处 理数据源主要是w e b 站点的拓扑结构和用户访问日志，是整个系统的 离线部分，从众多用户对w e b 页面的大量的点击中，分析w e b 用户的 行为特征，实现用户聚类，再分析每一类用户的个性行为特征，得到 描述用户行为方式的关联规则，为整个系统的个性化服务提供知识支 持。 堆十遗传算法的w e b 关联规则挖掘的研究与设计第2 章遗传算法简介 2 1 遗传算法概述 第二章遗传算法简介 遗传算法( g e n e t i ca l g o r i t h m ，下简称g a ) 是上一世纪7 0 年代 由美国密西根州( m i n c h i g a n ) 大学的h o l l a n d 教授提出的种计算 理论，主要模拟自然界的生物的遗传、变异的进化过程，通过选择、 交叉、变异等算子来体现g a 的思想。g a 是一种启发式全局寻优算法， 它的两大特点是隐的并行计算性“州和很强的全局寻优能力，是机器 学习的重要方法。 g a 主要体现了生物进化中“适者生存”的规律，其主要特征体 现为：进化发生在解的编码上。这些编码按生物学的术语称为染色 体。由于对解进行了编码，优化问题的一切性质都通过编码来研究。 编码和解码是g a 的一个基本问题。自然选择规律决定哪些染色体产 生超过后代的平均数。染色体上功能单位是基因。双亲染色体上的 遗传基因的复制使得子女保持父母的特征，基因的组合、随机的变 异会造成子代与父代的不同的性状。 2 2 标准g a 的基本操作 h o l l a n 提出的g a ，也称标准g a ，在实际的运用中往往对标准 g a 做一定的修改，但是操作的简单和功能的强大仍然是标准g 胪”的 重要特点。一般的g a 都包含三个基本的操作：选择( s e l e c t i o n ) 、 交叉( c r o s s o v e r ) 、变异( m u t a ti o n ) 。 1 、选择 又称选择算子，是从父代种群中选择适应值高的个体位串 ( 染色体) 产生新种群的过程，也是个体位串根据其自身的生存能 力复制自身的过程，体现了自然选择的“优胜劣汰，适者生存” 的规律。 2 、交叉 第2 章遗传算法简介 摹于遗传算法的w e b 关联规则挖掘的醐究与设计 又称交叉算子，交叉的操作分两步实现。在由选择算子得到的 位串构成的匹配池中，首先将新复制的产生的个体位串进行两两 配对；然后随机选择交叉点，将配对的个体位串进行交叉繁殖， 产生新的位串对。 3 、变异 变异算子的设计思想源于自然界中染色体上的基因突变，基因 突变使得物种可以出现祖先中未曾有的性状特征，再通过自然选择， 让富有生命力的新物种延续下去。在g a 中变异算子让位串中某些位 以较小的概率发生随机的改变，交叉算子和变异算子是生物进化的 主要原因。 图2 1 给出了g a 的运作流程： 图2 - 1g a 运作流程 g a 首先初始化个体种群，并对个体进行染色体适应值评估，然 后根据个体的适应值选择双亲个体放入交配池，对个体进行两两配 对；互相配对的个体进行染色体上的基因互换，并以一较小的概率 进行基因突变，从而形成下一代种群，此时判断种群是否收敛或者 能解决应用问题，满足g a 的结束条件，如满足则结束，否则对新一 代种群的个体进行适应度值评估，通过选择算子选择个体进入交配 池，开始新一轮进化。 基十遗传算法的w e b 关联规则挖掘的研究与设计 2 36 a 的模式理论 g a 模拟的是自然界生物优胜劣汰进化过程。但是，作为一种智 能搜索算法，它的本质内涵是什么? 更具体地讲，g a 的基因操作， 即选择、交叉和变异算子何以能使g a 体现出其它算法所没有的鲁棒 性、自适应性和全局优化等，g a 的内在的运行机理便是模式理论所 要阐述的问题。 2 3 1 模式的相关概念 定义l 模式( s c h e m a ) 是描述字符串集的模版，该字符串集中的 串的某些位置上具有相似性。 定义2 模式阶( s c h e m ao r d e r ) 亦称模式位数，模式h 中确定 位置的个数称为该模式的阶，记作0 ( h ) 。 如0 1 0 * * 0 1 * 0 模式的阶为6 。 定义3 模式定义长度亦称模式距，模式中的第一个确定位置和 最后一个确定位置之间的距离，记作6 ( h ) 。 如0 1 0 * * 0 1 * 0 模式的定义长度为l o i = 9 。 1 选择算子对模式的影响 设在第t 代，群体a ( t ) 有m 个特定的模式h ，记成 i l l = m ( h ，t ) 在选择过程中，a ( t ) 中任意一位串a 。以概率p i = f ；( f 。代 表a ，的适应度函数值，其它类同) 有放回被选中并进行复制，并且 假定种群的规模不变。 则在t + l 代，特定模式h 的数量为 m l ( h ，t + 1 ) = m ( h ，t ) n * f ( h ) ， ( 2 1 ) 或者记作 m ( h ，t + 1 ) = i l l ( h ，t ) f ( h ) 7其中7 表示平均适应值 基于遗传算法的w e b 关联规则挖掘的研究与设计 可见通过选择算子，子代种群中特定模式h 的数量正比于父代 种群中模式h 的适应值与父代种群适应值的平均值。当f ( h ) 7 时， h 的数量将增加，反之则减少。 设f ( h ) 一7= c 7( c o ) 则( 2 1 ) 式可转化为： m ( t t ，t + 1 ) = m ( h ，t ) ( 1 + c )( 2 - 2 ) 那么从第0 代种群进化到第t + l 代种群时，特定模式h 的个体数 量为： m ( h ，t + 1 ) = m ( h ，0 ) ( 1 + c ) 。( 2 - 3 ) 其中m ( h ，0 ) 表示初始种群种中符合特定模式h 的个体的数量。 2 交叉算子对模式的影响 位串( 染色体) 通过交叉来有组织的、随机性的交换各自的基因 信息，交叉算予对模式h 的影响和模式的定义长度6 ( h ) 有关，越 大，模式h 被破坏的可能性越大，一般情况下，假设交叉发生的概率 是l ，模式h 在交叉算子的作用下存活概率p 。为： p 。= 1 - 6 ( h ) ( l - 1 )( 2 _ 4 ) 其中l 代表泣串长度 如设发生交：赋阱口障为r ，贝咔漠式h 存活概率p 。为： p 。= l p c * 6f f l ) ( l - 1 )( 2 ) 在经过选择、交叉算子的作用后，模式h 的数量变比= 公式为： m ( h ，t + 1 ) = m ( h ，t ) p 。术f ( h ) 7 ( 2 - 6 ) 代入( 2 _ 4 ) 式，即 m ( h ，t + 1 ) = m ( h ，t ) f ( h ) 丰 1 6 ( ) ( c - 1 ) 7 ( 2 7 ) 3 变异算子对模式的影响 变异是对位串e 鲍挚个渤憧e 埔t 率p - 进伺嘲仉变换，变异算子i 捕勖嘲观 确雠麒式h ，由于单价啦置的存活的概率是l - p , ( p - 为变异的概率) ，且每一 毓十遗传算法的w e b 关联规则挖掘的研究与设计 第2 章遗传算法简介 个位置发生变异是统计独立的，因此，特定模式当目仅当它的0 ( h ) 个确定位 置都存活删才希话，即模式h 的存活率为 ( 1 一p _ ) o 仲( 2 - 8 ) 一般清况下，设定的变异概率很小，因此匕式的值近似可看作为 l 一0 ( h ) p m( 2 删 4 遗传算子对模式的影晌 如果我1 f 球菝解、交叉、变异算予硎书差模式h 的勃栏萧鲡生_ 起，特定 模式h 在下内耀为： m ( t + 1 ) = m ( h ，t ) f ( h ) 7 ：j c 1 6 ( ) ( l 一1 ) 术 1 - 0 ( h ) p 。( 2 - 1 1 ) 在p m 很小的情况下上式近似等于： m ( h ，t + 1 ) = m ( h t ) f ( h ) 7 1 6 ( ) ( l _ 1 ) - o ( h ) p ( 2 - 1 2 ) 因此t + l 代的特定模式h 与初始种群( 0 代) 中特定模式h 的数 量关系是： m ( h jt + 1 ) 硼啦0 ) 木 f ( h ) 7 * 卜6 ( m ( l _ 1 ) 一o ( h ) p ( 2 - 1 3 ) 这里为说明问题，假设每代遗传的f ( h ) 、7 、p 。等数值不变。 据上分析，可得出结论，通过遗传算子“0 1 ”3 的作用，定义长度短 的、低阶的、高适应值的模式的数量将越来越大，最终g a 将收敛于 高适应值的特定模式，逼近全局的最优点。 下面我们给出g a 重要定理。 模式定理( s c h e m at h e o r e m ) ：定义长度短的，确定位数少的， 平均适应值高的模式数量将随着进化代数的增加呈指数级增长。模 式定理是g a 的基本定理。 建筑块假设( b u il d i n gb i o c kh y p o t h e s is ) ：定义长度短的、 低阶的、适应值高的模式( 称为建筑块) ，在遗传算子的作用下被采 样、重组，从而形成高阶、长模式距、高于群体平均适应值的模式。 模式定理保证了性能较优的模式其样本数呈指数级增加，满足 了寻找最优解的必耍条件，即g a 有可能达到全局最优解：建筑块假 设则表明g a 具备全局寻优能力，即建筑块在遗传算子的作用下，能 基于遗传算法的w e b 关联规则挖掘的研究与设计 产生高平均适应值的模式，并最终形成最优解。 2 4 计算并行性 h o l i a n d 指出g a 的有效处理的模式个数为0 ( n 3 ) ，即尽管g a 实 际上只对n 个串个体进行运算，却隐含的处理了0 ( n ) 个模式。 h o l l a n d 称这一性质为隐并行性( i m p l i c i tp a r a l l e l i s m ) 。事实上可 以证明：g a 在每代的蝴，随然嬲了o ( n ) 个模式的个啦但 模式数艉疑影糍0 了o ( 雨。 2 5 模式欺骗( d e c e p t i v e ) l 司题 g a 适用于穴多数经鞫建臣0 的问题，但也存舀 些g a 难幽辆缺的问题，即 晟终的搜索往盛嘲惑垒尉嚣扰解，这类问题视翰柞g a 隧蝴。如果给定些带 欺骗性瘌掘卿哈条件“干扰、迷惑 c a ，使其偏离全局鼋损解，最大限度地违 背建筑块假设，使得低阶、短距、高于平均适应度的模式生成局部最优点，这 就尉副鹊耘始诣留撼骗问题。由 知戈理论，问题茸旨芒用g a 有效地求解，取决 于问题编码韪酮南园勃倒班i 设，在满足建筑姗设下g a 能以较高的效率查找 最由优解，否贝| 顺蜊氐，甚至毖4 淫蝌撼解。但是，在_ 段悻形下，尽管存 在些问题或荐冽磋涤件“迷惑”g a ，但这类明问题却由矾g a 困难的，即 通常不会偏离全局最伊日挥。 肇十遗传算法的w e b 关联规则挖掘的研究与设计第3 章w e b 行为挖掘与智能化服务偷述 第三章w e b 行为挖掘与个性化服务概述 3 1w e b 挖掘简介 为什么要提出w e b 挖掘? 纵观i n t e l m e t 的发展历史，i n t e r n e t 从最初的 部门专用网络发展到今天的开放性、全球性、公用性的分布式网络，包含着海 量级的信息，并正以极快的速度瞥长。但正由于它的信息曼十- 分巨大目缺乏统 一的规范和结构，导致了用户获取自己感兴趣的信副 常困难。尽管已经有一 些铰为有效的搜索引擎，如g o o g l e 、b a i d u 等，但它们提供的都是基于关睫词 自c 搞亩查询日e 努，虽夹鞴生弓电l 渡匕】镝映了信息劫眦问题，征五丕运发鳓邕满 足用户的个隆化鬣恩自动获取要求。另方面，随着电子商务的日益发展，商 业网站面临的乍严峻问题是：如何吸引客户以缟吉激益。事实上，电子商务业 务的竞争比倦鲡孙蟛孵狰更自激烈由于颓标的次点击，客户就有可能扶- 一 个网站转到其竞争对手那边，网站的内容的组织安排、用词、标题、服务等任 何付幻肆鳓踟沩吸引客户、同时断璐铡沩失去客户的因素；同时， 用户对网站访问过箍骣含了用户的兴趣、爱好，如伺分析、跟踪、获得用户的 个性譬特征，个危艺副潮劬弛躺拥数据挖撼匆艮因此，将数据挖掘技 术应用于w e b ，以发现用户的个性特征行为f ；设计出能满足不用客户群体 需要的智能化网站，方便甩户快速、准确地矾浩瀚的信皂资源中定位到所需信 息，就显黜重要和迫切。但是，由于w e b 数据的复杂性，数据的非结陶化， 不同于i 錾摆库中台勺数据，w e b 挖掘鸶艮多方面有另盯璀拗麴数f 嚣挖掘，涉及数 据离封曼沭、w e b 、数目旨挖掘、计算语言学、信自学、自然语言羽酶翠、人工智能等 多个学利领域。 笼统啦沆数据眩撼陂应用到w o r l dw i d ew e b 上，就 秀作w e b 挖捌“埘， w e b 挖掘可以广义匕的定义为“从w 孵匕茂晒f d = 制疳朗的信息”。这个定义包 含了谬j ：j 豁义：( 1 ) 自动篚庄臣戋售皂搜索，世掳宄是在聊哪资源e j 挂行珀瞧自芳毫呗， 称作w e b 内容挖掘。研究用户访问w e b 服务器自撼，也就剧巨掘用户浏览、 访问w w 自尊隗式，称作w e b 应用挖掘。 9 第3 章w e b 行为挖掘与智能化服务简述基于遗传算法的w e b 关联规则挖掘的研究与设计 3 1 1w e b 挖掘的分类 同传统的数锎匏酷瓣日比，w e b 数据具有其特殊性，其特点就是划踅羧有 严格的结构 ；弑、含有不同格式的数据( 文本、声音、图像等) 、面向显示的 h i 札文本无法区分数据类型，并目存在大量的冗余和噪声，同时w e b 是喇 态隆鹂虽的信皂源，所以面向w e b 蝴魄融赫翮究溉其挑战陛 b 内容挖牖：是指从w e b 文档内容茸淳凇中发荔隋月胤的过程。挖 掘的对象是w e b 文档内容。w e b 文本内容挖掘乎脚、基于概念索引或基于f 曰瞰 术的资源发现也可以归入这类。 w e b 结构挖掘：是指从w e b 的结构中发瑚溜渣拦蒯出帘矧泊q 过程。挖掘的 刘象是w e b 页面之间和页面内部的超链接。目前研究的多是对页面( u 甩) 间结 构的挖掘。 w e b 行为挖掘： b 称w e b 使用挖掘挚1 ，通过处理眼务器日志文件，结合站 点的拓扑结构信息，以发珊用户的浏览模式，如【j 宁歹嘴式、关联揪u 、用户聚 类和页面聚类等，理解用户的行为，进而实现： ( 1 ) 鄙瞢煲佣户的行为，进行个 信亩的定制和网页预测推荐，为用户提供 个性化服务。 ( 2 ) 改进和优化w e b 站点的拓扑结构，为电子商务提供技术支持。 3 1 2w e b 行为挖掘的主要技术、方法 w e b 行为挖掘的数据源是服务器端的日志文晰w 曲站点的结构信息，w e b 行为白勺j 渊目示是将w e be 大垂啪用户群魁分做富龟在以用户类为剃立- 分析 各类用户的俐“也特征。因蚴矽姥苎堀的主要技术乜融甏耻匕展开。首先要通 过用户访问日志识另恪自不同的用户，每用户赋予乍雌卜的用户标识，再 运用户聚类技沭将不同的用户划分成类，然后提取出每类用户的相关数据， 挖掘每类用户的行为方式，如关联规则、序列模式等。从后台的数据处理匕 来考虑，因为需要处理大量、频繁更新的数据，可以采用数据仓库找秽。 基十遗传算法的w e b 关联规则挖掘的研究与设计第3 章w e b 行为挖掘与智能化服务简述 3 2w e b 行为挖掘的一般过程 w e b 行为挖掘的过程不是本文蜘樾点，这里简要概述的它一咱殳过程。 ( 1 ) w e b 数据收集 用户访问日志、w e b 站点拓朴、页面信息等。般h ；形下，服务器的日志 是记录用户行为的重萼f 6 潍，在存在代理的隋形下，悃彤酣黼日志也矗溅 了用户的行为。而站点的拓扑则是w e b 站点本身的结构伉息，也是挖瓶阐户行 为特征的重要依据。 ( 2 ) 数据预处理 数捷葑争化：翮科融链麟中与剃尉勤环相关的冗余项。清除w e b 服 务器日志中与挖掘算法无关的数据，行为挖掘的目的是获得用户的 行为模式，并不关心那些用户没有显式请求的文件，要删除不相关的 数据类型主要有：g i f 、j p e g 、3 p g 、g i f 、j p e g 、j p g 和m a p 应将后 缀为这些的项从原始数据库中删除，后级名为c g i 的脚本文件也应 被删除。 用户识别：包括注册用户识别和非注册用户识别。如果是注册用户登 录，直接记下用户i d 即可；如果用户没有登录，则该用户可能是注 册用户，也可能是新用户，可以结合库中的访问历史和用户i p 以及 用户正在访问的页面等多个方面来进行判断。 会话识别：识别用户定时间内连封辩求的页面序歹啦 路径补充：补充由于本地缓存和f 淫导致的页面渚日之j 芋列的不完整。 事务识另u ：将用户会话划分为原子事务的集合。此部分的工作是将数撇 集阶段到的数据淹鼬据物豁翔数据挖掘算法的数据单盥。 ( 3 ) 用户模式挖掘 用户聚类：基于用户行为方式的群徽 1 分。 基于类用户的关联规则分析：挖掘类用户行为特征。 席离玢是w e b e 锖勰自嗡薨心，将用户翅盼颜同类的群体，并拄曲毽耋于 用户羹寝耐晓匕的关珏搬则。 ( 4 ) 模式分析 提取用户感凝倒抟模式，提* 个性化w e b 服氖实时嘟爵凋户白嘞t 可行为， 第3 章w 如行为挖掘与智能化服务简述基于遗传算法的w c b 关联规则挖掘的研究与设计 根据用户的当前的u r l 访问序歹0 ，推荐用户可奢甑努锄页面。 3 3w e b 行为挖掘构建个性化服务 从曾蚌上，我 f 蛤硅j 甚于w e b 衍蝴附眺眦服射蛹燃图，如图 3 - 1 所示。 图3 1 行为挖掘体系图 系统体系结构匕，般由在线部分和离线部分组成。 3 3 1 在线部分 ( 1 ) 用户识别 如果是宜期用户登纛可眺阼搠户名或者i d 来识舭如是匿名登陆， 可以限踣用户的工p 及浏览器类型和用户当前访问u r l 的引用u r l 来判断用户 的身份，即便叟呲，仍然难以准确识别匿名用户。 ( 2 ) 日志记录 船啪w e b 访问日志中可以记录下，用户的登陆的i p 挝i 址、用户名( 非 匿名登陆) 、请求u 甩、引用u 甩等信息、访问时间等信息，在我们的个f 生化 w e b 服努豸；统中，采用的是基于j 2 髓平台的f i l t e r 技术定制的日志，可以 记录下用户访问u r l 时的会话i d ( s e s s i o n i d ) ，以及用户注册的用户名等重要 信息，为后期的数据预处固孙侮鳓留瓯打下了基础。 基十遗传算法的w e b 关联规则挖掘的研究与设计 第3 章w e b 行为挖掘与智能化服务简述 ( 3 ) 个性化推荐 按照定的推荐算法，本系统内嵌至哪2 务槲主丰月蒯制孰黻见 个陛懈的功能。推荐崩夫三懿跑括当前s e s s i o n 集合、推 争陵型、推 荐引擎三个部分。其中，s e s s i o n 集合是当前已访问的页面集合，这个集合 作为整个个性化系统的输入；推荐漠型是指我f f 根据日志、页面、用户等 信息箜酎圣掘、统计得出聚类、关蝴0 、序歹峭拭等。 3 3 2 离线部分 主要包括日志管理、数据挖掘系统中自矬差要耕；缺、统计等功能。 ( 1 ) 日志管理 站点日志的日常管理，包括日志的添加，删除，读入，备份等。 ( 2 ) 网站拓朴结构分析 实现将w e b 站点的结构信息的获取，及各个u r l 之间的连接关系的获驭。 ( 3 ) 数据转换、清洗 将通过( 1 ) 、( 2 ) 得到的数据的瞻甜i 寻崖化，并对数函指亍清洗，去除与 数据挖掘无关的数据。 ( 4 ) 用户聚类分析 将大量的w e b 用户按照用户自身的个性喜好行为特征划分成不同的用户 的群体，即是聚类分析。 ( 5 ) 关联规贝蝴 通过晰醐户访问行为的事务库，发现甩户访问的u r l 之间的关联关系。 考虑用户用户的访问序列，挖掘的关珏椒则应更符合应用实际，更加切实有效。 基于遗传算法的w e b 关联规则挖掘的研究与设计 第四章遗传聚类的设计与实现 为什么要进行聚类? 在人们认识事物的过程中，总有这样一种潜 在意识：通过将事物归类来认识事物，如果某些事物可作为同类事 物来对待，那么一个事物所具有的特性可能同类的其它事物也具备， 这就为人们认识世间纷繁众多的事物提供了一条捷径。同样的， i n t e r n e t 用户的数量是巨大的，认识、学习如此众多的w e b 用户同样 需要以类为单位来进行，通过以类为单位处理w e b 用户，那么同类用 户可能具有相同或者相似的兴趣爱好，这样将大大提高工作效率和 处理能力。可以通过某种方式将数量众多的w e b 用户划分成以类为 单位的多个用户群体( 簇) ，这其中聚类就是一种较为可行且有效的 方法。 4 1 遗传聚类概述 4 1 1 聚类技术 聚类是把个体群按照相似性归成若干类别，目的是使得属于同 一类别的个体之间的差别尽可能的小，而不同类别上的个体间的差 别尽可能的大。聚类方法包括统计学方法、机器学习方法和神经网 络方法等。 在统计方法中，聚类也称聚类分析，它是多元数据分析的三大 方法之一( 其它两种是回归分析和判别分析) 。它主要研究基于几何距 离的聚类，如欧式距离、明考斯基距离等。传统的统计聚类分析方 法包括系统聚类法、分解法、加入法、动态聚类祛、有序样品聚类、 有重叠聚类和模糊聚类等。这类聚类方法是一种基于全局比较的聚 类，它需要考察所有的个体才能决定类的划分：因此它要求所有的 数据必须预先给定，而不能动态增加新的数据对象。聚类分析方法 不具有线性的计算复杂度，难以适用于数据库非常大的情况。 基十遗传算法的w e b 关联规则挖掘的研究与设计第4 章遗传聚类的设计与实现 在机器学习中聚类称作无监督或无导师归纳；因为和分类学习 相比，分类学习的例子或数据对象有类别依据，而无导师聚类的对 象没有类别依据，需要由聚类学习算法来自动确定。人工智能中， 聚类也称概念聚类；因为这里的距离不再是统计方法中的几何距离， 而是根据概念的描述来确定的，是待定的。当聚类对象可以动态增 加时，概念聚类则称是概念形成。 在神经网络中，有一类无监督学习方法：自组织神经网络方法； 如k o h o n e n 自组织特征映射网络、竞争学习网络等等。在数据挖掘 领域里，神经网络聚类方法主要是自组织特征映射方法，i b m 公司 在其发布的数据挖掘白皮书中就特别提到了使用此方法进行数据库 聚类分割。 聚类评估则是用数学手段研究和处理所给对象的分类以及各类 之间的亲疏程度，是对聚类质量的客观评定，不同类型聚类算法和 数据分布类型的聚类结果往往需要不同的评估方法，如对于采用划 分算法的聚类结果采用对类间差异、类内差异的线性度量，而对层 次聚类一般单链接标准来度量。 4 1 2 g a 与聚类 聚类的任务是将某些具有共同属性、的对象划分成为个群体， 按照事物间的相似性进行区分和分类的过程，即“物以类聚”，在这 一过程中没有导师指导，因此是一种无导师分类。遗传聚类是将g a 应用于聚类的种方法，其基本思想是通过遗传学习，将上一代的优 良特性保留下来，并通过个性之间的基因组合、变异从而产生更为优 良的下一代个体，这样经过数代的个体进化，最终达到找到满意的 个体。g a 是一种启发式的全局寻优算法，具有机器学习的功能【2 4 , 2 5 1 ， 在具体设计实现遗传聚类时，其要点是要将g a 计算得到的最优个 体信息应用于某一类聚类算法，从而得到基于g a 的最优聚类。任 何聚类结果都必须有一个评判标准，一般说来，较好的聚类结果应 该是：类内的个体之间相似性较大，不同类间之间的个体相似性 第4 章遗传聚类的设计与实现基于遗传算法的w e b 关联规则挖掘的研究与设计 较小；如果用个体之间距离来衡量个体之间的差异，那么一类内的 个体之间的聚类应尽量地小，而不同类间之间的个体距离应尽可能 的大。运用g a 进行聚类时，要寻找某种方法使得聚类的效果反映 到染色体的基因编码上，在此基础之上运用g a 的三大遗传算子( 选 择、交叉、变异) 通过数代的群体进化，得到最优的个体，此个体 同时对应了最优的聚类结果担”。最优化问题的求解过程是从众多的 解中选出最优的解。生物进化的适者生存规律使得最具有生存能力 的染色体以最大的可能生存，这样的共同点使得g a 可以在优化问 题中应用。 4 2w e b 遗传聚类的设计与实现 4 2 1 遗传聚类所要解决的问题 ( 1 ) 聚类对象的描述 w e b 用户聚类有其特殊性与复杂性。首先，要准确描述用户有 以下几点考虑：其一通过用户的注册信息，注册信息中有用户的一 些个性特征的描述，如年龄、文体爱好等，但注册信息的可信度有 待考证，并且注册的信息是否是过时也需要考虑，同时对匿名用户 要进行用户识别；其二通过文本挖掘【1 2 2 l l ，用户访问过的u r l 对应 的页面中的内容来分析用户兴趣、爱好，但这牵涉到自然语言理解 的问题：其三是行为挖掘，通过用户对网站的访问行为来挖掘他的 行为特征，因为一类用户总是访问他所感兴趣的某些类网页，可以 依据用户的访问行为进行用户聚类，是比较切实有效的方法。 从聚类的技术上来析，聚类的算法有很多种，如基于的划分的 k 均值聚类、k 中心点聚类，基于层次方法b i r c h 聚类、c h a m e l e o n 聚类，基于密度的d b s c a n 聚类等。从算法的适用性来说，划分法 适合球形形状的聚类的发现，层次聚类中b i r c h 聚类效果仍以球形 聚类为好，层次聚类算法中c h a m e l e o n 方法对任意形状的聚类有较 好的效果；另外基于密度的聚类算法将具有足够高密度的聚类对象 捧十遗传算法笪w c b 关联规则挖掘鲍研蜜。主塑计第4 章遗传聚类的设计与实现 划分成类，在发现任意形状的空间数据的聚类也有较好的表现。但 是，以上所述的聚类算法的基础般是聚类对象的空间分布，聚类 对象之间的欧氏距离，但w e b 的用户聚类的对象是一个个w e b 用户， 被聚类的用户的一个较为准确的描述是通过用户访问过的u r l 来实 现的，也就是说用户特征描述的根据是用户的行为，用户访问的u r l 来表示的，但一个w e b 站点往往有成百上千个u r l ，聚类算法应 用于w e b 用户的聚类通常的做法是建立一个多维向量，每个u r l 是向量的一维，用来记录用户的访问历史，描述用户的行为。这样 做的缺点是用户描述向量维数太大，更重要的是描述向量的每一维 处于同等位置，而事实上并非如此，因为页面的u r l 之间存在类属、 层次关系，在此基础之上的聚类有两个后果：向量维数太大导致计 算量巨大，用户行为描述向量的不精确致使聚类结果非常不准确。 如果我们考虑网站的拓朴结构，将所有的页面及其对应的u r l 进行 分层、归类，在此基础之上进行u r l 的编码，进而在这种编码的基 础之上对用户访问向量进行降维归约，那么用户的行为的描述将准 确得多、聚类的计算量也大大降低，也就很好地解决了上述的两个 问题。 ( 2 ) 遗传聚类算法的确定 正如前面所述，基于划分、层次、密度等聚类算法都有一个共 性是他们一般是建立在对聚类对象的空间描述上，也就聚类对象应 是一个不超过三维空间的点，如果聚类的对象不能用三维空间来描 述，那么算法聚类的效果也就很难进行评估，算法的基础、可行性 就很难保证。而w e b 用户描述向量一般是大于三维的，特别是大型 的网站，即使将w e b 用户描述向量归约到拓朴结构的较高层一般也 是远高于三维的，正是出于这样的考虑，如将机器学习的方法与聚 类算法结合起来，对聚类效果的评估通过机器学习的方式g “4 , 5 , 6 , 1 3 来实现，将聚类中的一些关键问题通过进化计算、机器学习的手段 来确定，能很好的解决了这个问题。遗传学习的目标也就在于把上 代种群的优良个性传递给下一代，在一代代的进化中，寻求全局 的最优化解。 第4 章遗传聚类的设计与实现基于遗传算法的w e b 关联规则挖掘的研究与设计 具体在将g a 与聚类算法相结合时，要解决个体染色体编码的问 题和个体适应值，以及如何g a 的三个算子的具体实施和相关聚聚 类评估等问题，下面将具体详细说明。 4 2 2w e b 遗传聚类的具体设计与实现 1 w e b 站点的拓朴分析和u r l 编码 从逻辑结构上来说，一个w e b 站点是一个特殊的有向图，这个 图有一个特殊的根节点，这就是主页，所有页面( u r l ) 包括主页 之间的每一个连接就是这个图的一个有向边，一个逻辑结构设计得 较好的w e b 站点，页面之间的类属和层次关系是比较明晰的，可能 存在一些u r l 之间的连接不符合这种类属、层次关系，我们可以在 对u r l 进行编码时做一些处理，如根据u r l 本身的字符序列并结 合对站点层次遍历来确定u r l 的应该的类属、层次，也可以通过对 用户描述向量进行特征学习来最大程度地减小这种影响：因此从总 体上来说，基于w e b 站点的拓朴分析的u r l 编码方案是科学的、 可行的，这也被后来的聚类结果所证实。 具体的做法是：按层次顺序构造站点的最小生成树，树的根就 是主页节点，主页中每一个u r l 链接是根节点的一个子树根节点， 递归进行这样的处理，在此基础之上建立每一个u r l 的层次编码， 从每一个u r l 的编码我们可以确定它所代表的页面所处的位置，和 所在逻辑层次，它的父u r l ，及它可能有那些子u r l ，能判断某一 u r l 是否是它的兄弟。图4 1 给出了一个简化的站点拓朴编码图： 图4 - 1 拓扑编码图 些垫堡基鎏盟里垄! 羞鐾塑型堡塑盟婴壅量堡生蔓兰垦望堡墨耋塑堂丛生壅些 从图4 - 1 得到的各u r l 编码为( 二进制) ： a ：0 0 0 0 ，0 0 0 0b ：0 0 0 l ，0 0 0 0c ：0 0 1 0 ，0 0 1 0 a i ：0 0 0 0 ，0 0 0 1a 2 ：0 0 0 0 ，0 0 1 0 b 2 ：0 0 0 1 ，0 0 1 0 c ：0 0 1 0 ，0 0 0 1c 2 ：0 0 1 0 ，0 0 1 0 r 是主页，a ，b ，c 是r 下的某一大类页面，而a l ，a 2 a 。 是a 页面下某一子类页面，b ，b 2 ，b 。是b 下的某一子类页面， 依此类推，一般设计较为的规范的网站都具有这样的逻辑结构。因 此，如果我们将针对与此建立网站u r l 的树型分层编码体系，每一 个i j i 也的编码体现自身在整个网站中所处类属以及与其它u r l 之 间的远近关系，根据用户访问的u r l 及访问的次数( 频度) ，建立 描述用户聚类向量，向量的每一元素是一个二维向量( 其中包括u r l 编码和权值，权值由由访问频度和时间决定) ，根据聚类的精度需要 对聚类向量归约到网站拓朴的某一层，如根下第二层，那么基于此 编码设计的u r l 之上的用户聚类实现应更为准确，更好地反映用户 的兴趣爱好和个性行为特征。在具体实现u r l 层次编码时，应结合 具体的网站规模加以分析，小型网站可以采用定长层次编码，而对 于大型网站，则可以考虑采用动态不定长层次编码以适应网站拓朴 体系的要求。 此种编码设计特点： 1