（计算机应用技术专业论文）基于遗传算法的web用户聚类模型的研究.pdf

摘要 w e b 日志挖掘作为w e b 挖掘的一个重要组成部分，包含了大量的用户访问信息，对 之进行分析，从中挖掘出用户的行为模式，有着重要的理论和实践意义。w e b 日志挖掘 的方法主要有三种：聚类分析、关联分析、序列分析，其中，聚类分析方法适合挖掘具 有噪音和不完整数据的大量数据集，因此它在用户行为模式分析中起着重要的作用。 在聚类分析中，k 均值算法是应用较为广泛的一种算法，但是它的缺点是对初始值 非常敏感而且容易陷入局部极小值，因此本文引入遗传算法，将遗传算法与k 均值算法 进行整合，充分发挥遗传算法启发式全局寻优的计算优势，寻求最优聚类。 本文所述系统首先根据网站的拓扑结构对页面进行编码，在编码中存储了页面的层 次关系及其类属关系，有助于提高了w e b 用户的聚类质量。然后以编码为基础根据w e b 日志得到一组用户行为访问向量，并改进了一个基于遗传算法的w e b 用户聚类模型 w u g c ( w e bu s e rg e n e t i cc l u s t e r i n g ) ，以实现对w e b 用户的聚类分析。w u g c 以遗传算 法为基础，在聚类过程中利用个体间的选择、交叉、变异操作，保留适应度高的个体并 使之进化，直至得到最优的聚类结果。这种算法对初始聚类中心和样本输入次序可以不 做要求，从而避免了k 均值算法的对初始值敏感而且容易陷入局部极小值的问题。 最后，系统设计了一个实验平台，分别采用k 均值算法和w u g c 模型对w e b 用户进 行聚类分析，并对实验结果进行比较。结果表明：新方法在聚类问题中得到的结果要优 于传统k 均值聚类方法，但是由于用到了遗传操作，聚类速度相对k 均值方法要慢一些。 关键词：聚类k 均值算法w e b 用户聚类遗传算法 a b s t r a c t w e bl o gm i n i n gi sa l li m p o r t a n tc o m p o n e n to fw e bm i n i n g ，i n c l u d i n gal a r g en u m b e ro f u s e r s a c c e s s i n gi n f o r m a t i o n ，a n dw ec a nf i n dt h eu s e rb e h a v i o u rp a t t e r n sb ya n a l y z i n gi t s o r e s e a r c ho ni ti so fg r e a ts i g n i f i c a n c ei nt h e o r ya n dp r a c t i c e t h e r ea r et h r e em a j o rw a y sf o r w e bl o gm i n i n g ：c l u s t e r i n ga n a l y s i s ，a s s o c i a t i o na n a l y s i s ，a n ds e q u e n c ea n a l y s i s h e r e c l u s t e r i n ga n a l y s i si ss u i t a b l ef o rm i n i n gn o i s ea n di n c o m p l e t ed a t as e t s ，f o rt h i sr e a s o ni t p l a y sc r i t i c a lr o l ei na n a l y s i so fu s e rb e h a v i o rm o d e l k - m e a n sa l g o r i t h mi st h em o s tw i d e s p r e a dm e t h o di nc l u s t e r i n ga n a l y s i s h o w e v e ri t s v i t a ls h o r t c o m i n gi st h es e n s i b i l i t yt oi n i t i a lv a l u ea n di ti se a s yt or u ni n t oal o c a lo p t i m u m t h e r e f o rb yi n t r o d u c i n gg e n e t i ca l g o r i t h m ，i n t e g r a t i o no fk - m e a n sa l g o r i t h ma n dg e n e t i c a l g o r i t h mc a l lb r i n gt h ec o m p u t i n ga d v a n t a g e so fg e n e t i ca l g o r i t h m sh e u r i s t i cg l o b a l o p t i m i z a t i o ni n t of u l lp l a yt og e to p t i m a lc l u s t e r i n g f i r s t l y , t h es y s t e md i s c u s s e di n t h i sp a p e r u s e sa ne n c o d e dm o d ef o rw e bp a g e sw h i c h e s t a b l i s h e db yt h ew e bs i t e st o p o l o g i c a ls t r u c t u r e w i t ht h i sc o d e ，p a g eh i e r a r c h ya n d d e p e n d e n c yr e l a t i o n s h i pa r es t o r e d t h em e t h o dc a nh e l pp r o m o t eq u a l i t yo fw e bu s e r s c l u s t e r i n g t h e nag r o u po f u s e rb e h a v i o u ra c c e s s i n gv e c t o rb a s e do nt h ec o d ei sb u i l tf r o m w e b l o g s ，a n dw e bu s e rc l u s t e r i n gm o d e lb a s e do ng e n e t i ca l g o r i t h m ( w u g c ) i sp r o p o s e d t oi m p r o v et h ew e bu s e rc l u s t e r i n g m a k i n gu s eo ft h ei n d i v i d u a l s s e l e c t i o n ，c r o s s o v e ra n dm u t a t i o no p e r a t o ro fg e n e t i c a l g o r i t h m ，i nc l u s t e r i n gp r o c e s s ，t h ei n d i v i d u a lt h a th a st h eh i g h e rf i t n e s sa r er e t a i n e da n d e v o l v e dt i l lt h eo p t i m a lr e s u l ti sf o u n d t h i sm o d e lh a sn od e m a n do ft h es e l e c t i o no fi n i t i a l c l u s t e r i n gc e n t e ra sw e l la st h eo r d e ro ft h es a m p l e si n p u t t h u sd i s a d v a n t a g e so ft h ek - m e a n s a l g o r i t h m ，s e n s i t i v et oi n i t i a lv a l u e sa n de a s yt or u ni n t ol o c a lm i n i m a ，a r ea v o i d e d f i n a l l ya ne x p e r i m e n t a lp l a t f o r mi sd e s i g n e d ，w h i c hr e a l i z e sb o t hk - m e a n sa l g o r i t h ma n d w u g ct oc l a s s i f yt h es a m ew e bu s e rd a t a f u r t h e rm o r e ，t h ee x p e r i m e n t a lr e s u l t sa r e c o m p a r e da n da n a l y z e d c o n s e q u e n t l yr e s u l ts h o w st h a tw u g ci sm o r ee f f e c t i v et h a n t r a d i t i o n a lk - m e a n sa l g o r i t h mi nc l u s t e r i n gq u a l i t y ，w h i l et h es p e e di ss l o w e rt h a nk - m e a n s a l g o r i t h mb e c a u s eo ft h eu s eo fg e n e t i co p e r a t i o n k e yw o r d s ：c l u s t e r i n g ，k m e a n sa l g o r i t h m ，w e bu s e rc l u s t e r i n g ，g e n e t i ca l g o r i t h m 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取 得的研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得 墨盗墨墨太堂 或 其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研 究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 学位论文作者签名：参7 渤咻 签字日期：力年月日 学位论文版权使用授权书 本学位论文作者完全了解墨盗墨兰盘堂有关保留、使用学位论文 的规定。特授权墨盗墨兰盘堂 可以将学位论文的全部或部分内容编入 有关数据库进行检索，并采用影印、缩印或扫描等复制手段保存、汇编， 以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复本和电子 文件。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：别垮砟卜 导翌签名： 穹似 j 签字日期：州年j 月f 日签字日期：加驴年1 月i ，日 第一章引言 1 1 研究背景、目的和意义 第一章引言 随着计算机技术和信息技术的发展，信息的增长速度呈现指数上升，最近几十年产 生了很多超大型数据库，遍及超级市场销售、银行存款、行政办公、科学研究。信息量 的增长，使传统分析方法远远不能满足现实的需求。面对海量数据，如何从中发现有价 值的信息或知识，成为一项非常艰巨的任务。人们急切的需要一种去粗存精、去伪存真 的技术，能够从海量的数据中提取知识和信息的数据挖掘技术应运而出。 二十一世纪是信息时代，迅速发展的i n t e m 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 m e t 上更加流连忘返。有统计数据表明，世 界上每年w e b 服务器数量都以超过3 5 的比例增长，w e b 页面以7 0 的比例增长，在 我们每个用户面前汇成了一个信息的海洋。如何能够在最短的时间内找到最适合自己的 信息，已越来越成为用户和各运营商日益关注的事情。如何提高w e b 服务质量，了解 访问者在网站的活动情况，如何从庞大的用户群的数据海洋中挖掘客户活动信息，让用 户可以得到个性化的服务，正在成为前沿研究课题之一。 w e b 日志挖掘作为w e b 挖掘的一个重要组成部分，包含了大量的用户访问信息， 对之进行分析，从中挖掘出用户的行为模式，有着重要的理论和实践意义。行为模式表 明了用户的个性特征，兴趣爱好，据此把大量的w e b 用户划分为不同的类，为每一类 用户提供量身定制的个性化w e b 服务，对网站的管理者和用户本身都有重要的意义。 本课题作为基于数据挖掘l l j 【2 】【3 】的智能w e b 服务系统的数据分析部分，旨在通过遗 传算法、聚类分析技术，从用户与w e b 服务器的交互数据中发现用户访问过程中的隐 含的知识、规律，得到用户的访问模式和用户的兴趣，实现用户聚类，为用户的个性化 服务提供事实依据。 1 2 研究动态与发展趋势 数据挖掘是一门新兴的数据处理技术，涉及数据库技术、人工智能、机器学习、神 经网络等学科”j 。遗传算法作为一种模拟自然进化思想的启发式全局寻优算法，是进化 计算的杰出代表，也足机器学习的重要方法1 4 j 。将遗传算法引入数据挖掘领域的越来越 引起学术界的重视，嗣外己经有不少成功的范例，如：将遗传算法与数据挖掘的聚类算 法进行整合，发拘；遗传算法启发式全局寻优和并行模式处理的计算优势，j - 求最优聚类 1 5 j ；将遗传算法父联舰则挖掘算法相结合，挖掘关联规则并且对关联姚则进行优化、 第一章引言 预测【6 l ；将遗传算法应用于由产生式规则构成的知识树的优化i 4 l 等。 在统计方法中，聚类被称为聚类分析i z j ，它是多元数据分析的三大方法之一，其它 两种是回归分析和判别分析。它主要研究基于几何距离的聚类，如欧氏距离、明考斯基 距离等。传统的统计聚类分析包括系统聚类法、分解法、加入法、动态聚类法、有序样 品聚类、重叠聚类和模糊聚类等。这种聚类方法是一种基于全局比较的聚类，它需要考 察所有的个体才能决定类的划分，因此它要求所有的数据必须预先给定，不能动态地增 加新的数据对象。聚类分析方法不具有线性的计算复杂度，难以适用于数据库非常大的 情况问。 聚类与数据挖掘中的分类不刚剐。在分类问题中，我们知道训练例的分类属性值， 在那里我们要做的就是将每一条记录分别属于哪一类标记出来；与此相似但又不同的 是，聚类分析的输入数据集是一组未标记的对象，也就是说此时输入的对象还没有被进 行任何分类，聚类的目的是根据一定的规则，合理地进行分组或聚类，并用显式或隐式 的方法描述不同的类别。由于分类可以采用不同的算法，所以对于相同的数据集合可能 有不同的划分。在机器学习中，聚类是无指导学习的一个例子，分类是有指导学习的一 个例子，两者所采用的方法相差甚远，并且聚类的时间复杂度要比分类大得多。 聚类的用途是很广泛的。在商业上，聚类可以帮助市场分析人员从他们的消费者数 据库中区分出不同的消费群体，并概括出每一类消费者的消费模式，可以从保险公司的 数据库中发现汽车保险中具有较高索赔概率的群体；在生物学中，它可以被用来辅助研 究动、植物的分类，可以对具有相似功能的基因进行分类，还可以用来发现人群中的一 些潜在的结构等等；聚类还可以用来从地理数据库中识别出具有相似土地用途的区域。 在国外，结合遗传算法的数据已成功应用在一些商务数据的挖掘上，在w e b 数据 挖掘上也建立了一些实验模型。如：c ) 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 h g e n e t i cn i c h ec l u s t e rr a g h uk r i s h n a p u r a mi b mi n d i ar e s e a r c hl a b ，e t c 9 1 ( 窑) u s i n gg e n e t i c a 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 ni na ne d u c a t i o n a lw e b - b a s e ds y s t e mg e n e t i c a l g o r i t h m sa n da p p l i c a t i o ng r o u pm i c h i g a ns t a t eu n i v e r s i t y 1 1 0 l 而国内的研究主要集中在遗传算法理论与数据挖掘领域的探讨上，建立了一些基本 的数据挖掘问题计算模型，如在聚类过程中采用遗传计算技术1 1 1 】。 随着数据挖掘应用领域的不断拓展，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 e u n i v e r s i t y 首度将遗传算法引入基于w 曲的数据挖掘上，为w e b 数据挖掘提供了一个崭 新的思考模式，虽然i b m 和m i c h i g a n 并未给出具体的技术细节，但是仍然给人们对于 处理复杂的w e b 的数据挖掘问题时指出了一个新的研究方向。 聚类就是按照一定的要求和规律对事物进行区分的过程，在这一过程中或在此过程 之前，没有任何关于数据集类分的先验知识，仅靠事物问的相似性作为类属划分的准则， 因此属于无监督学习的范畴。聚类分析通常也当作是知识发现的预处理工作。聚类的质 量对整个知识发现过程来说是非常重要的，在进行数据挖掘过程中，聚类除了精确之外 还要求高效。所以，好的聚类算法应该满足：预先知识的独立性、尽可能少的参数、准 确、快速、可测性。 传统的基于聚类准则的聚类算法本质 ：是一一种局部搜索算法，它们采用了一种迭代 第一章引言 的爬山技术来寻找最优值。因此，存在两个问题：一是处理大数据量费时，二是容易陷 入局部极小值。 遗传算法是一种通过模拟自然进化过程搜索最优解的方法，其显著特点是隐含并行 性和对全局信息的有效利用能力，只需少量结果就可以反映探索空间较大的区域，便于 实时处理，而且具有较强的稳健性。国内外许多学者已经将遗传算法应用到各自研究的 领域中，如车辆调度问题、通信网的设计等方面。在数据挖掘领域，包括聚类分析领域 中也有一些学者使用遗传算法来解决相关问题。利用遗传算法可以降低传统聚类算法对 初始化的要求。 例如傅景广等人在基于遗传算法的聚类分析【2 j 一文中，提出了一种基于遗传算 法的聚类分析方法，该算法采用二进制编码方式对聚类的中心进行编码，用特征量与相 应聚类中心的欧氏距离之和来判断聚类划分的质量；张伟等在一种基于遗传算法的聚 类新方法【1 1 j 一文中，也提出了一种改进的遗传算法，并用来解决聚类问题；还有k r i s h n a k 等人于1 9 9 9 年在i e e e 上发表的文章( ( g e n e t i ck - m e a n sa l g o r i t h m ) ) 1 3 j ，也是一种 遗传k 均值聚类算法。 不断有人提出基于遗传算法的聚类方法，并做着各种改进，来提高算法的效率。刘 健庄f 5 j 等于1 9 9 2 年提出了基于遗传算法的k 均值算法和模糊k 均值聚类算法。f a l k 于1 9 9 3 年提出了所谓的分组遗传算法( g r o u p i n gg e n e t i c a l g o r i t h m ，g g a ) 1 2 l ，致力于设 计适当的染色体表达来获取问题的编码，并应用于各种分组、分割以及聚类问题。1 9 9 4 年a l - s u l t a n 1 3 】提出用t a b u 搜索算法求解k 均值聚类问题，它通过对划分矩阵u 的 随机搜索以获得全局最优解。1 9 9 7 年唐立新【1 4 】以及1 9 9 9 年戴晓晖等提出了基于g a 的动态聚类方法1 1 引，2 0 0 4 年傅景广等提出基于遗传算法的聚类分析，可以说这些算法 都是基于g a 的改善聚类效果的一个思路。高坚的用基于免疫机制的单亲遗传算法 求解数据聚类优化问题 1 6 j 一文中，将免疫机制引入遗传算法，按免疫系统维持免疫平 衡的原理对群体中的个体按浓度进行自适应抑制和促进，然后借助该免疫遗传算法来解 决聚类分析问题。 综上所述，将遗传算法应用到各自的研究领域是一个发展趋势，并且遗传算法擅长 于数据聚类。常规聚类方法因不能有效地处理局部极值问题，因此当初始聚类中心在整 个样本空间不平衡时，它很难将这种不平衡纠正过来，从而导致聚类结果对初始聚类中 心的选取有着很大的敏感性。本文的研究是将遗传算法与k 均值聚类算法相结合的形 式，改进了一个用于w e b 用户聚类的模型，即用于对w e b 用户的聚类分析方法。该算 法比常规聚类更能有效的处理局部极值，并对初始聚类中心的选取以及样本的输入次序 没有任何要求，另一方面，从它们各自的收敛速度上来看，虽然w u g c 的收敛速度较 慢，但是比通过不同初始聚类中心进行聚类来获取全局最优解的常规方法要有效。 1 3 本文的主要研究工作和创新之处 课题的研究内容是：基于遗传算法的w e b 用户聚类模型( w u g c ) 的研究，旨在 第一章引言 通过遗传算法、聚类分析技术，从用户与w e b 服务器的交互数据中发现用户访问过程 中的隐含的知识、规律，得到用户的访问模式和用户的兴趣，实现用户聚类，为用户的 个性化服务提供事实依据。 在课题中，主要完成了如下工作： ( 1 ) 研究了网站的特点和拓扑结构，引用了一种用于w e b 用户聚类分析的网页编码 方式，在编码中存储了页面的层次关系及其类属关系，它不仅有助于提高了w e b 用户 的聚类质量，同时在聚类后还能更好地反映用户的个性行为特征。 ( 2 ) 以编码为基础根据w e b 日志得到一组用户行为访问向量，并改进了一个基于遗 传算法的w e b 用户聚类模型w u g c ( w e bu s e rg e n e t i cc l u s t e r i n g ) ，以实现对w e b 用户 的聚类分析。 ( 3 ) 设计了一个实验平台，分别采用k 均值算法和w u g c 模型对w e b 用户进行聚 类分析，并对实验结果进行比较。结果表明：新方法在聚类问题中得到的结果要优于传 统k 均值聚类方法，但是由于用到了遗传操作，聚类速度相对k 均值方法要慢一些。 本文的创新之处在于： ( 1 ) 通过研究网站的特点和拓扑结构，引用了一种用于w e b 用户聚类分析的网页编 码方式，在编码中存储了页面的层次关系及其类属关系，不仅有助于提高了w e b 用户 的聚类质量，同时在聚类后还能更好地反映用户的兴趣爱好和个性行为特征。 ( 2 ) 通过研究聚类算法和遗传算法，改进了一个w u g c 模型，w u g c 以遗传算法 为基础，在聚类过程中利用个体间的选择、交叉、变异操作，保留适应度高个体并使之 进化，直至得到最优的聚类结果。这种算法对初始聚类中心和样本输入次序可以不做要 求，从而避免了k 均值算法的对初始值敏感而且容易陷入局部极小值的问题。 1 4 论文内容的组织和结构 本文共分五章： 第一章主要阐述了课题的研究背景、目的和意义。 第二章介绍了w e b 行为挖掘及其行为挖掘的一般过程，在分别介绍了遗传算法和 聚类分析的工作原理后，归纳出w u g c 的工作原理及其在w e b 用户聚类中的应用。 第三章讲述了w u g c 模型的研究与实现。首先阐述了w e b 用户聚类中存在的问题， 然后确定了w u g c 的体系结构，并在体系结构中设计了七个模块，最后详细给出了 w u g c 的设计思想、算法描述和具体的实现过程。 第四章主要介绍了系统的实验平台，它实现了k 均值聚类算法和w u g c 模型，分 别针对现有的物流信息网站和校园网网站系统中的w e b 用户进行了聚类分析。 最后，在第五章中，对本文进行了总结，并提出了进一步的工作思路。 第：章w e b 行为挖掘和i k i g c 模犁相关理论综述 第二章w e b 行为挖掘和w u g c 模型相关理论综述 2 1w e b 行为挖掘和个性化服务描述 2 1 1w e b 挖掘简介 近年来，随着i n t e r n e t 技术的快速普及和迅猛发展，使各种信息可以以非常低的成 本在网络上获得。i n t e r n e t 从最初的部门专用网络发展到今天的开放性、全球性、公用 性的分布式网络，包含着海量级的信息，并正以极快的速度增长。但正由于它的信息量 十分巨大且缺乏统一的规范和结构，导致用户获取自己感兴趣的信息非常困难。尽管已 经有一些较为有效的搜索引擎，但它们提供的都是基于关键词的信息查询服务，虽然在 一定程度上解决了信息源定位问题，但还远远不能满足用户的个性化信息自动获取要 求。另一方面，随着电子商务的日益发展，商业网站面临的一个严峻问题是：如何吸引 客户以提高效益。事实上，电子商务业务的竞争比传统的业务更加激烈。由于鼠标的一 次点击，客户就有可能从一个网站转到其竞争对手那边，网站的内容的组织安排、用词、 标题、服务等任何一个地方都有可能成为吸引客户、同时也可能成为失去客户的因素； 同时，用户对网站访问过程隐含了用户的兴趣、爱好，如何分析、跟踪、获得用户的个 性特征，一个行之有效的方法就是运用数据挖掘技术。因此，将数据挖掘技术应用于 w e b ，发现用户的个性特征行为模式，设计出能满足客户群体需要的智能化网站，方便 用户快速准确地从浩瀚的信息资源中定位到所需信息，显得尤为重要和迫切。但是由于 w e b 数据的复杂性，数据的非结构化，不同于数据库中的数据，w e b 挖掘在很多方面有 别于传统的数据挖掘，涉及数据库技术、w e b 、数据挖掘、自然语言理解、人工智能等 多个学科领域。 w e b 挖掘指使用数据挖掘技术在w w w 数据中发现潜在的、有用的模式或信息。 w e b 挖掘可以广义的定义为“从w w w 上发现和分析有用的信息 。这个定义包含了两 层含义：( 1 ) 自动的在线信息搜索，也就是在w w w 资源上进行的信息发现，称作w e b 内容挖掘。( 2 ) 研究用户访问w e b 服务器的模式，也就是挖掘用户浏览、访问w w w 的 模式，称作w e b 应用挖掘。 1 、w e b 挖掘的分类 w e b 挖掘l l7 j 是数据挖掘在w e b 上的应用。w 曲数据具有其特殊性，其特点就是数 据没有严格的结构模式、含有不同格式的数据、面向显示的h t m l 文本无法区分数据类 型，并且存在大量的冗余和噪声，同时w e b 是一个动态性极强的信息源，所以面向w e b 的数据挖掘研究极具挑战性。 w e b 内容挖掘：是指从w e b 文档内容或其描述中发现有用信息的过程。挖掘的对 象包括文本、图像、音频、视频、多媒体和其他各种类型的数据。其中针对无结构化文 本进行的w e b 挖掘被归类到基j ：文本的知识发现领域，也称文本数据挖掘或文本挖掘， 第二：章w e b 行为挖掘和w u g c 模型相关理论综述 是w e b 挖掘中比较重要的技术领域，也引起了许多研究者的关注。最近在w e b 多媒体 数据挖掘方面的研究成为另一个热点。 w e b 结构挖掘：是指从w e b 的结构中发现潜在的链接模式的过程。挖掘的对象是 w e b 页面之间和页面内部的超链接。目前研究的多是对页面间结构的挖掘。 w e b 行为挖掘：也称w e b 使用挖掘，通过处理服务器日志文件，结合站点的拓扑 结构信息，以发现用户的浏览模式，如序列模式、关联规则、用户聚类和页面聚类等， 理解用户的行为，进而实现： ( 1 ) 预测用户的行为，进行个人信息的定制和网页预测推荐，为用户提供个性化服 务。 ( 2 ) 改进和优化w e b 站点的拓扑结构，为电子商务提供技术支持。 2 、w e b 行为挖掘的主要技术 w e b 行为挖掘的数据源是服务器端的日志文件和w e b 站点的结构信息，w e b 行为 的挖掘的目标是将w e b 上大量的用户群划分成类，在以用户类为单位分析各类用户的 个性化特征。因此行为挖掘的主要技术也是围绕此展开。首先要通过用户访问日志识别 各自不同的用户，每一用户赋予一个唯一的用户标识，再运用聚类技术将不同的用户 划分成类，然后提取出每一类用户的相关数据，挖掘每一类用户的行为方式。 2 1 2w e b 行为挖掘的一般过程 w e b 行为挖掘的一般过程如下1 1 8 j ： ( 1 ) w e b 数据收集 用户访问日志、w e b 站点拓扑、页面信息等。一般情形下，服务器的日志是记录用 户行为的重要依据，在存在代理的情形下，代理服务器的日志也记载了用户的行为。而 站点的拓扑则是w e b 站点本身的结构信息，也是挖掘用户行为特征的重要依据。 ( 2 ) 数据预处理 数据净化：删除原始数据库中与数据挖掘不相关的冗余项。清除w e b 服务器日志 中与挖掘算法无关的数据，行为挖掘的目的是获得用户的行为模式，并不关心那些用户 有没有显式请求的文件，要删除不相关的数据类型主要有：g i f 、j p e g 、j p g 和m a p 应 将后缀为这些的项从原始数据库中删除，后缀名为c 西的脚本文件也应该删除。 用户识别：包括注册用户识别和非注册用户识别。如果是注册用户登录，直接记下 用户i d 即可；如果用户没有登录，则该用户可能是注册用户，也可能是新用户，可以 结合库中的访问历史和用户i p 以及用户正在访问的页面等多个方面来进行判断。 会话识别：识别用户一定时间内连续请求的页面序列。 路径补充：补充由于本地缓存和代理导致的页面淆求序列的不完整。 事务谚 别：将用户会话划分为原子事务的集合。此部分的工作是将数据收集阶段得 到的数挺转换成能直接运用数据挖掘算法的数据誓位。 ( 3 ) 片j ，、模式挖掘 用户聚类：基于用户行为方式的群体划分。 第二章w e b 行为挖掘和w u g c 模型相关理论综述 本部分是w e b 行为挖掘的核心，将用户划分成不同类的群体，并挖掘基于用户类 基础之上的关联规则。 ( 4 ) 模式分析 提取用户感兴趣的模式，提供个性化w e b 服务。实时跟踪用户的访问行为，根据 用户的当前的u r l 访问序列，推荐用户可能感兴趣的页面。 2 1 3w e b 行为挖掘个性化服务 w e b 行为挖掘的个性化服务的系统体系结构由下面三部分组成。 ( 1 ) 日志记录 从网站服务器上可以得到用户的访问日志，即可以得到用户登录的i p 地址、用户 名、请求u r l 、引用u r l 、访问时间等信息，在这里记录下用户访问u r l 时的会话l d ， 以及用户注册的用户名等重要信息，为后期的数据预处理的准确高效打下了基础。 ( 2 ) 用户行为访问向量 网站的拓扑结构分析是实现w e b 站点的结构信息的获取，各个u r l 之间的连接关 系的获取。并根据w e b 的日志记录而得到用户行为访问向量，从而为聚类分析打下数 据基础。 ( 3 ) 聚类分析 将大量的w e b 用户按照用户自身的个性喜好、行为特征划分成不同的用户的群体， 即是聚类分析。 2 2w u g c 模型相关理论综述 2 2 1 遗传算法的工作原理 遗传算法1 4 l ( g e n e t i ea l g o r i t h m g a ) 是一类借鉴生物界自然选择和自然遗传机制的随 机化搜索算法，是模拟达尔文的遗传选择和自然淘汰的生物进化过程模型，它是由美国 密歇根大学h o l l a n d 等人在七十年代首次提出并建立了它的数学框架。该方法一经提出 便受到了关注，到8 0 年代中期其研究开始进入高潮。g o l d b e r g 和m i c h a l e w i c z 进行了大 量的研究工作，并成功地将它应用到各种领域的优化问题。 遗传算法中处理的是染色体，或者叫基因型个体。一定数量的个体组成了群体。群 体中个体的数目称为群体规模，而各个体对环境的适应程度叫做适应度。此外，执行遗 传算法时，通常需要两个必要的数据转换操作，一个是表现型到基因型的转换，另一个 是基因型到表现型的转换。前者是把搜索空间中的参数或解转换成遗传窄i 日j 中的染色体 或个体，此过程又叫编码操作；后者是前者的一个相反操作，叫做译码操作。 遗传算法，从数学角度看，是+ 一种概率性搜索算法；从工程学角度看，它是种自 适应的迭代：产优过程。它从某随机产生的或是特定的初始群体出发( 作为父本) ，按 第二章w e b 行为挖掘和w u g c 模型相关理论综述 照一定的操作规则，如选择、交叉、变异等，不断地迭代计算，并根据每一个个体的适 应度值，保留优良品种，淘汰次品，引导搜索过程向最优解逼近。 1 、遗传算法的特点 遗传算法与传统的优化方法相比有不同的特点1 4 j ： ( 1 ) 遗传算法是进行群体的搜索 传统的优化方法是从一个点开始搜索。如 f l - i ( c l i m b i n g ) 法是从当前点邻近的点中选 出新点，如果新点的目标函数值更好，那么该新点就变成当前点，否则就选择和测试其 他邻近点。如果目标函数值没有更进一步的改进，则算法终止。很显然，爬山法只能提 供局部最优解，它依赖于初始点的选择。 遗传算法是对多个个体进行群体的搜索，即在问题空间中不同区域进行搜索，构成 一个不断进化的群体序列。对于复杂问题的多峰情况，遗传算法也能以很大的概率找到 全局最优解。 ( 2 ) 遗传算法是一种随机搜索方法 遗传算法使用三个遗传算子。选择算子通过选择概率复制个体；交叉算子通过交叉 概率在交配池中决定配对的个体是否需要进行交叉操作；变异算子通过变异概率确定某 些基因位的值进行变异。可见，三个遗传算子都是随机操作，利用概率转移规则产生好 的后代，引导其搜索过程朝着更优解的空间移动。可见遗传算法虽然是一个随机搜索方 法，但是它是高效有方向的搜索，而不是一般随机搜索方法的那种无方向的搜索。 ( 3 ) 遗传算法处理的对象是个体，而不是参变量自身 遗传算法要求将优化问题的参变量编码成长度有限的位串个体，通过遗传算子操作 位串个体，并从中找出高适应值的位串个体。遗传算法不是对参数变量进行直接操作。 编码操作可直接对结构对象进行操作。结构对象泛指集合、序列、矩阵、树、图、 链和表等一维或二维结构形式的对象。这一特点使得遗传算法具有广泛的应用领域。 ( 4 ) 遗传算法不需要导数或其它辅助信息 一般传统的搜索算法需要一些辅助信息，如梯度算法需要求导数，当这些信息不存 在时( 如函数不连续时) ，这些算法就失效。而遗传算法只需要适应值信息，用它来评估 个体，引导搜索过程朝着搜索空间的更优化解的区域移动。 进化算法在搜索过程中使用的是基于目标函数值的评价信息，而不是传统方法主要 采用的目标函数的导数信息或待求解问题领域内知识。进化算法的这一特点使其成为具 有良好普适性和可规模化的优化方法。 ( 5 ) 隐含并行性 遗传算法实质上是模式的运算。对于一个长度为k 的串，其中隐含着残个模式。 若群体规模为刀，则其中隐含的模式个数介于放和n * 2 k 之间。遗传算法实际上是对n 个位串个体进行运算，但却隐含地处理了大量的模式，这一性质称为隐含并行性。隐含 并行性是遗传算法优于传统的搜索方法的关键所在。 ( 6 ) 形式简单明了 进化算法在形式上简单明了，f ：仅便于与其他方法相结合，而且非常适合于人规模 并行计算机运算，因此可以有效地川j ：解决复杂的适应性系统模拟和优化问题。 第二章w e b 行为挖掘和w u g c 模型相关理论综述 ( 7 ) 具有很强的鲁棒性 进化算法具有很强的鲁棒性，即在存在噪声的情况下，对同一问题的进化算法的多 次求解中得到的结果是相似的。进化算法的鲁棒性在大量的应用实例中得到了充分的验 证。 2 、遗传算法的构成要素 构成基本遗传算法的要素主要有：染色体编码，个体适应度评价，遗传操作数( 选 择操作数，交叉操作数，变异操作数) 以及遗传参数的设置等。 ( 1 ) 染色体编码方式 在实现对一个问题用遗传算法进行求解之前，必须先对问题的解空间进行编码，用 的编码方式为二进制编码，其等位基因是由二值符号集 o ，1 组成。对于解空间中的变 量是离散变量的情况下，对每个变量直接用相应位数的二进制串进行编码即可。对于那 些连续变量，需要先对连续变量进行离散化，再进行编码。初始群体中各个个体的基因 值可用均匀分布的随机数来生成。遗传算法的进化过程是建立在编码机制基础上的，编 码对于算法的性能如搜索能力和种群多样性等影响很大。 ( 2 ) 适应度函数 在遗传算法中，以个体的适应度的大小来确定该个体被遗传到下一代群体中的概 率。个体的适应度越大，该个体被遗传到下一代的概率也越大；反之，个体的适应度越 小，该个体被遗传到下一代的概率也越小。 ( 3 ) 遗传算子 基本遗传算法使用三种遗传算子，分别为： 选择算子：按照某种策略从父代中挑选个体进入中间群体； 交叉算子：随机从中间群体中抽取两个个体，并按照某种交叉策略使两个个体互相 交换部分染色体码串，从而形成新的个体。 变异算子：通常按照一定的概率，改变染色体中某些基因的值。 ( 4 ) 运行参数 基本遗传算法有下述四个运行参数需要提前设定： ：群体规模，即群体中所含个体的数量； 兀遗传算法的终止进化代数； p c ：交叉概率，一般取值为0 4 0 9 ； 砌：变异概率，一般取值为0 0 0 1 0 1 。 这四个运行参数对遗传算法的求解结果和求解效率都有一定的影响，但目前尚无合 理设霄它们的理论依据。在遗传算法的实际应用中，往往需要经过多次运算后才能确定 出这些参数合理的取值大小和取值范围。 3 、遗传算法的处理流程 遗传算法中包含两个必须的数据转换操作，一个是把搜索空间中的参数或解转换成 遗传空问中的染色体或个体，此过程又叫做编码操作；另一个是相反操作，又叫做译码 操作。 遗传算法是一种群体性操作，该操作以群体中的所有个体为对象。选择、交叉和变 第二章w e b 行为挖掘和w u g c 模型相关理论综述 异是遗传算法的三个主要操作算子，它们构成了遗传操作，使遗传算法具有了其他传统 方法所没有的特性。 遗传算法首先将问题的每个可能的解按照某种形式进行编码，编码后的解称作染色 体。随机选取个染色体构成初始种群p 0 ，再根据预定的评价函数对每个染色体计算 适应值，使得性能较好的染色体具有较高的适应值。选择适应值高的染色体进行复制， 通过遗传算子：选择、交叉、变异，来产生一群新的更适应环境的染色体，形成新的种 群。这样一代一代不断繁殖、进化，最后收敛到一个最适应环境的个体上，求得问题的 最优解。 一个串行运算的遗传算法( s e q u e n t i a lg e n e t i c a l g o r i t h m ，s g a ) 按如下过程进行： ( 1 ) 对待解决问题进行编码； ( 2 ) 随机初始化群体； ( 3 ) 对当前群体中每个个体计算其适应度，适应度表示了该个体的性能好坏； ( 4 ) 应用选择算子产生中间代： ( 5 ) 应用其它的算子产生新一代群体，这些算子的目的在于扩展有限个体的覆盖 面，体现全局搜索的思想； ( 6 ) f = 件1 ；如果不满足终止条件继续( 3 ) 。 图2 1 遗传算法i ：作流稃劁 第二章w e b 行为挖掘和w u g c 模型相关理论综述 遗传算法中最常用的算子：选择算子，交叉算子和变异算子，它们的实现是多种多 样的，而且许多新的算子正在不断地提出，以改进遗传算法的某些性能。系统参数( 个 体数n ，基因链长度k ，交叉概率p c ，变异概率p m 等) 对算法的收敛速度及结果有很大 的影响，应视具体问题选取不同的值。 由于遗传算法是一个概率过程，所以每次迭代的情况是不一样的，而且，系统参数 不同，迭代情况也不同。在实验中参数一般选取如下：个体数n = 5 0 2 0 0 ，变异概率 砌= o 0 3 ，交叉概率p c - - o 6 。变异概率太大，会导致不稳定。 4 、遗传算法的缺陷 遗传算法本身仍然存在一些缺陷，阻碍了它在实际问题中的应用，对算法本身运行 机理的研究和这些缺陷的解决将有力地推动遗传算法的发展。遗传算法的数学基础并不 完善，缺乏广泛而完整的有关遗传算法的收敛性理论，虽然e i b e n ，r u d o l p h ，q i 和 p a l m i e r 等在一些特殊情形下说明了遗传算法的收敛性，但缺乏广泛性；另一方面对于 遗传算法随机搜索机理的研究，虽然有h o l l a n d 等人的s c h e m a 理论，但该理论并不 能用以解释实践中所观察到的遗传算法过早收敛的现象。遗传算法最主要的缺陷就是局 部搜索能力差，并且容易形成早熟收敛，采用遗传算法求解优化问题一般只能得到准最 优解，而不容易得到最优解。 遗传算法的主要缺陷是早熟收敛问题，产生的原因是因为传统的复制机制和比例选 择会使得高于群体平均适应度值的模式在下一代中获得较多的取样，随着迭代的进行， 某些模式在种群中占据了优势，传统的遗传算法就会强化这种优势，使搜索范围迅速变 窄，迅速收敛的种群达到的未必是全局最优解，从而产生过早收敛。 2 2 2 聚类分析算法的工作原理 聚类分析1 1 9 】是将物理或抽象的对象组成的集合分组成为由类似的对象组成的多个 簇，使得处于相同簇中的对象具有最大的相似性，而处于不同簇中的对象具有最大的差 异性的方法及过程。在许多应用中，可以将一个簇中的数据对象作为一个整体来对待， 从而可以辅助人们从整体上对于有多个事物所构成的群体取得认识。通过聚类，能够找 出数据属性之间潜在的相互关系。 聚类分析的过程可由图2 2 表示： 样本 川馈循环 劁2 - 2 聚类步骤 簇 第二二章w e b 行为挖掘和w u g c 模型相关理论综述 1 、聚类分析的方法 在数据挖掘中，需要根据应用所涉及的数据类型、聚类的目的以及具体应用要求来 选择合适的聚类算法，一些应用也需要将多个方法结合