（计算机应用技术专业论文）免疫遗传算法在web使用挖掘中的应用研究.pdf

免蠢t t 毫h b 健用托l 中曲j t 用研完 免疫遗传算法在w e b 使用挖掘中的应用研究 摘要 w e b 的信息资源和信息服务的数量和复杂度都以惊人的速度增长着， 一个站点能否吸引访问者，能否成功地引导访问者获得有用的、恰到好处 的信息，成为这个站点是否能够成功的关键。这使得w e b 个性化成为w e b 组织者和终端用户所必需的工具。 w e b 使用挖掘技术是解决这一问题的有效手段，通过对用户浏览网站的 使用数据收集、分析和处理，建立起用户行为和兴趣模型，这些模型可以 帮助理解用户行为，改进站点结构以及为用户提供良好的个性化推荐。在 众多的挖掘技术中，关联规则的挖掘是w e b 使用挖掘领域的一个重要内容， 有着广泛的应用。 本文首先简要介绍了w e b 个性化服务的必要性。接着比较系统、完整 地分析和论述7w e b 挖掘中的各项技术，并总结了现有的w e b 挖掘中的关 联规则挖掘技术的研究成果以及目前关联规则挖掘算法的缺陷。然后通过 对遗传算法的研究，文章着重讨论了将遗传算法应用于w e b 关联规则挖掘 中的思想，提出基于遗传算法的w e b 关联规则挖掘模型；在深入研究的基 础上，通过分析免疫算法和遗传算法的可行性和优缺点，引入免疫算子， 针对遗传算法的不足，进一步提出改进型算法，以及基于免疫遗传算法的 w e b 关联规则挖掘的应用。最后，一系列仿真实验结果表明：与传统遗传算 法相比较，基于免疫遗传算法的关联规则发现在w e b 使用挖掘中具有一定 1 i 乞t | 瘫- e b u 一舅：l 中_ i 鼍f ，巴 的优势。 关键词：w e b 个性化w e b 挖掘w e b 使用挖掘关联规则免疫算法遗 传算法 ，1 ，| l 哇h k 宣奠“t 鼍l 问 隹w e b u 剞l 中的l 习院 t h e p p l i c a t l 0 n0 fw e bu s a g em i n i n gb a s e0 nl m m u n ea n d g e n e t i ca l g o r l t h m t h e t r e m e n d o u sg r o w t hi nt h en u m b e r a n dt h ec o m p l e x i t yo fi n f o r m a t i o n r e s o u r c e sa n ds e r v i c e so nt h e w e bh a sm a d ew e bp e r s o n a l i z a t i o n 锄i n d i s p e n s a b l e t o o lf o rb o t h 霄e b b a s e do r g a n i z a t i o n sa n df o rt h ee n du s e r s w e bm i n i n g t e c h n o l o g yi so n eo fc o r et e c h n i q u e su s e di nw e bp e r s o n a l i z a t i o n i nr e c e n ty e a r st h e r eh a sb e e na ni n c r e a s i n gi n t e r e s ta n dag r o w i n gb o d y o fw o r ki nw e bu s a g em i n i n ga sa nu n d e r l y i n ga p p r o a c ht oc a p t u r i n ga n dm o d e l i n g w e bu s e rb e h a v i o r a lp a t t e r n sa n df o rd e r i v i n ge b u s i n e s si n t e l l i g e n c e s e v e r a l m e t h o d sh a v eb e e nd e v e l o p e dt oe x t r a c tk n o w l e d g ef r o mt h es e s s i o n st od e s c r i b e t h en a v i g a t i o n a lb e h a v i o r so ft h eu s e r so naw e bs i t e s u c hp a t t e r n sc 8 1 1b e u s e dt ob e t t e ru n d e r s t a n db e h a v i o r a lc h a r a c t e r i s t i c so fv i s i t o r so ru s e r s e g m e n t s ，i m p r o v et h eo r g a n i z a t i o na n ds t r u c t u r eo ft h es i t e ，a n dc r e a t ea p e r s o n a l i z e de x p e r i e n c ef o r v i s i t o r sb yp r o v i d i n gd y n a m i cr e c o m e n d a t i o n s o n e o fi t sp o p u l a ra p p l i c a t i o n si st of i n d8 1 1a s s o c i a t i o nr u l ef r o md a t a b a s e t r a n s a c t i o n s a tf i r s t t h i sp a p e ri n t r o d u c e st h ei m p o r t a n c eo f - e bp e r s o n a l i z a t i o ni n e - c o m m e r c eb r i e f l y t h e n ，t h ew e bm i n i n gt e c h n i q u e sw e r ea n a l y z e da 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 ep r o g r e s so fa s s o c i a t i o nr u l e s d i s c o v e r yi nw e bm i n i n gw a ss u m m a r i z e d a n dt h e nt h r o u g hs t u d y i n gt h eg e n e t i c a l g o r i t h mt h e o r i e s ，t h i sw o r kp r o p o s e sam o d e lo fw e ba s s o c i a t i o nr u l e sm i n i n g b a s e do ng e n e t i ca l g o r i t l m b yr e s e a r c h i n gt h o r o u g h l y ，t h r o u g ha n a l y z i n gt h e f e a s i b i l i t yo ft h eg e n e t i ca l g o r i t h ma n d a r t i f i c i a li m m u n es y s t e m , t h ea d v a n t a g e a n ds h o r t c o m i n go fe x i s t i n gi nt h o s e , i ta l s og i v e sa ni m p r o v i n ga l g o r i t h mw i t h i m m u n ea n dg e n e t i ct e c h a i q u e f i n a l l y ，t h er e s u l t o fas e r i e so fe m u l a t e e x p e r i m e n tp r o v e st 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 ew e ba s s o c i a t i o n r u l e sm i n i n gb a s e do ni m m u n ea n dg e n e t i ca l g o r i t h mh 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 k e yw o r d s ：w e bp e r s o n a l i z a t i o nw e bm i n i n gw e bu s a g em i n i n g a s s o c i a t i o nr u l e si m m u n ea l g o r i t h mg e n e t i ca l g o r i t h m ，u t 传日皇w e b t j 抽+ 曲j l j _ t 第一章引言 随着互联网的普及和电子商务的发展，个性化技术逐渐成为电子商务i t 技术的一 个重要研究内容，得到了越来越多研究者的关注。w e b 信息资源和信息服务的数量和复 杂度都在以惊人的速度增长着，一个站点能否吸引访问者，能否成功地引导访问者获得 有用的恰到好处的信息，成为这个站点是否能够成功的关键。a c m 从1 9 9 9 年开始每年 召开一次电子商务的研讨会，其中关于电子商务个性化技术和推荐系统【l 】的研究文章占 据了很大比重。 1 1w e b 个性化服务 所谓个性化服务，就是在用户浏览w e b 站点时，尽可能地迎合每个用户的浏览兴 趣并且不断调整自己来适应用户浏览兴趣的变化，使得每个用户都有是该w e b 站点唯 一用户的感觉。 个性化服务包含两层涵义，首先针对不同的用户需求提供不同的服务，而更重要在 于发现用户的潜在需求进行主动的信息服务。这使得w e b 个性化成为w e b 组织者和终 端用户必需的工具。首先，不同的w e b 用户通过各种途径访问w e b 资源；其次，系统 学习用户的特性，创建用户访问模型；最后，系统根据得到的知识调整服务，以适应不 同用户的个性化需求。因此，创建w e b 个性化服务系统的一般步骤为： 一、收集用户的各种信息，如注册信息、访问历史等； 二、分析用户数据，创建符合用户特性的访问模式； 三、结合用户特性，向用户提供符合特殊需求的个性化服务。 用户对系统提供的服务做出反馈信息，系统再根据反馈信息调整信息服务。通过用户与 系统之间循环往复的交互，系统最终能够为用户提供个性化服务。从这个分析可以看出， 通过分析用户的各种信息建立用户的访问模式是建立个性化系统的关键，因为只有首先 客观地描述了用户的需求，然后才能根据这些特性向用户提供个性化服务。 建立个性化推荐系统的众多技术中，比较成功和广泛使用的是协同过滤技术( c f ) 【2 】。它们利用用户之间的相似性来过滤信息。基于协同过滤技术的优点是能为用户发现 新的感兴趣的信息，缺点是存在两个很难解决的问题【3 】，一个是稀疏性，亦即在系统使用初 期。由于系统资源还未获得足够多的评价，系统很难利用这些评价来发现相似的用户。另 一个是可扩展性，亦即随着系统用户和资源的增多，系统的性能会越来越低。针对上述的 问题，近几年来越来越多的工作注重于w 曲使用挖掘的研究 4 1 ，使其成为用来获取和建 模w e b 用户浏览行为模式的基本方法，从而为电子商务产生有效的推荐。 早期的工作，例如文献【5 6 ，7 】已经考虑过基于用户事务和页面聚类的自动的个性化。 竞蠢 传# ，l - 曲使用蛇一中曲j u 一研竞 然而，这通常以降低推荐准确度为代价。一个提高准确度的解决办法就是文献【9 1 中所描 述的使用预处理技术例如标准化。另一种方法是考虑个性化中的订购信息。与无序模式 ( 例如聚类和关联规则) 相比，有序模式包含更多关于用户浏览行为的准确信息。使用 浏览序列模式来预测用户模型已经被广泛研究 9 , i o , n 1 。所有这些研究的焦点都放在w e b 页面的预取( 例如，预测用户的下一个访问页面) 以提高服务器的运行效率或减少网络 的延迟。然而狭隘的关注浏览序列通常导致较低的推荐覆盖率，使得这个技术在推荐系 统中效率较低。 一些最近的研究考虑到了在推荐系统中关联规则挖掘的使用 1 2 , 1 3 , 1 4 , 1 5 】。这些研究的 大部分是基于发现所有的关联规则优先于产生推荐( 这样在推荐阶段需要在所有规则中 搜索) 或者在当前用户邻居事务集的子集中实时产生关联规则。还有小部分研究是基于 要素的冲突，例如支持度闭值或用户历史记录的规模对推荐有效性的影响。 1 2w e b 挖掘中的关联规则挖掘 i n t e m e t 提供了一个海量的信息源泉，它涉及新闻、广告、消费信息、金融管理、 教育、政府、电子商务和许多其它信息服务。w e b 还包含了丰富和动态的超链按信息， 以及w e b 页面的访问和使用信息，这为数据挖掘提供了丰富的资源。人们希望有一个 工具能够自动从i n t e m e t 上提取知识。传统的数据挖掘基于关系数据库或数据仓库，所 处理数据具有完整的结构。但是i n t e r n e t 上的数据却是无序的、非结构的，并且存在着 大量的冗余与噪声。 对有效的数据仓库和数据挖掘而言，w e b 似乎太大了。w e b 的数据量目前以几百兆 字节计算，而且仍然在迅速地增长。关联规则挖掘是w e b 使用挖掘的一个重要研究课题， 它的目的在于找出网站资源访问记录中隐含的相互关系。运用关联规则挖掘技术能够从 服务器以及浏览器端的日志记录中自动发现隐藏在数据中的模式信息，了解系统的访问 模式以及用户的行为模式，从而做出预测性分析。最早的系统是w e bw a t c h e r ，用来向 用户推荐他感兴趣的未来访问连接。w 3 i q 是另一个基于合作信息检索概念的推荐和个性 化系统。j o s eb o r g e s 和m a r kl e v e n e 使用超文本概率语法建模用户浏览记录，他们假 设高频率的点击流对应于用户的喜好，并用g r a m m a r 的熵值评估挖掘到的模式，但它不 能发现不同页面集之间的关联关系。c o o l e y 使用不同的关联规则算法去发现访问序列和 用户会话之间的关联模式。q i a n gy a n g 在传统关联规则算法的基础上建立n - g r a m 序列 模式。c o d yw o n g 采用模糊规则进行访问路径推荐。 还有文献 1 6 , 1 7 , 1 8 】把关联规则挖掘的结果用于推荐系统或个性化系统。文献1 1 9 1 提出的 t o p n 推荐系统首先从定购信息中挖掘出关联规则，然后把消费者的历史定购信息和规 则的左半部分相匹配，找出这个消费者支持的所有规则，把这些规则的右半部分( 物品) 根据可信度从高到低排列，最后向消费者推荐前n 件物品。基于关联规则挖掘的推荐系 统面临的问题之一是，如果数据是稀疏的，将无法生成推荐。文献1 1 6 提出两种解决方案。 2 克触佛，崔w e b h l 舅湘中曲啊| 竞 文献【2 0 】提出一个基于关联规则挖掘的推荐系统的可扩展框架。推荐算法使用有效的数据 结构存储频繁集，从而能够实时地生成推荐集。文献i i g i 描述了w u m ( w e bu s a g em i n i n g ) 的框架，并且结出一个关于w e b 访问信息挖掘的系统w e b m i n e r ，该框架尤其适合于y e b 个 性化的应用。文献【2 1 0 2 1 利用遗传算法建立用户的p r o f i l e ，用于个性化系统中。l iy i n g j i 提出关联规则挖掘结合w e b 内容挖掘和网络拓扑结构来改善算法的效率和性能。鲍玉斌 利用关联规则和聚类结合进行个性化推荐。陈振提出一种基于关联分类方法的w e b 用户 兴趣预测。 传统关联规则算法在w e b n 志挖掘中出现的问题： ( 1 ) 目前的w e b 日志关联规则挖掘算法，如f p ，a p f i o f i ，t v p 等，都忽略了用户对 规则是否感兴趣这一重要问题。 ( 2 ) 庞大的w e b 日志数据将给传统的关联规则挖掘算法带来巨大的挑战，极大的搜索 空间将导致算法效率低下。 针对传统的基于w e b 使用挖掘的个性化技术的缺陷，本文旨在引入免疫遗传概念， 将免疫遗传的优点相结合，提出一种免疫遗传的关联规则挖掘算法应用于w e b 日志挖 掘中。 1 3 人工免疫系统 1 9 7 4 年，美国诺贝尔奖获得者，生物学家、医学家、免疫学家j e r n e 提出的免疫网 络理论引起各方关注。继该文之后，f a r m e r 、p e r e l s o n ，b e m i n i 、v a r e l a 等理论免疫学 者分别在1 9 8 6 和1 9 8 9 年、1 9 9 0 年发表了有关论文，在免疫系统启发实际工程应用方面 奠定了基础，其中f a r m e r 关于免疫系统与机器学习的研究是具有创造性和开拓性的工 作。他们的研究工作为建立有效的基于免疫原理的计算系统和智能系统的发展开创了道 路。v a r e l a 在1 9 8 9 年讨论了免疫网络以某种方式收敛的思想以及免疫系统能够通过产 生不同的抗体和变异适应新环境的思想，为使免疫系统成为有效的解决工程和科学问题 的灵感源泉做出巨大贡献。日本学者i s h i d a 在1 9 9 0 年首先利用免疫系统解决故障诊断 问题，作者将几个简单的免疫方法应用于传感器网络故障诊断领域。同年，美国学者 b e m i s i 提出利用免疫系统方法解决自适应问题，随后，美国学者f o r r e s t 在1 9 9 4 年首 先将免疫系统方法用于解决计算机安全和病毒检测问题。越来越多的人注意到 p e r e l s o n 、b e m i n i 和v a r e l a 等理论免疫学家在1 9 8 9 年、1 9 9 0 年所做的早期研究工作 的重要性，他们尝试建立免疫系统的模型以期为生物计算提供新方法，人工免疫系统的 应用领域由此不断得到扩大。关予人工免疫系统的新方法、新技术不断出现，在世界信 息科学技术领域又诞生了一个崭新的研究领域：人工免疫系统( a r t i f i c i a li m m u n e s y s t e m ，a i s ) 。美国i e e e 组织已经从1 9 9 7 年开始分别在c o n f e r e n c eo ns y s t e m s ，m a n a n dc y b e r n e t i c s 和杂志上征集、发表人工免疫系统研究成果，i y c c l l 9 9 8 年起开设人工 免疫系统专题会议，目前己连续几年召开该会议，国际人工免疫系统会议近两年连续在 竞蠢哺算，l | e b t 用棚十l 一| 峨 英国召开两次，促进了人工免疫系统的发展。人工免疫系统已经用于解决许多不同的工 程和科学问题。 国外对人工免疫的研究成果较多：如文献田l 中提出了一种基于信息熵概念的免疫算 法。文献幽j 将遗传算法与人工免疫系统相结合，提出了免疫遗传算法，用于模式识别。 还有免疫a g e n t 算法【2 5 】等。文献1 2 6 】用免疫系统3 维模式识别来解决2 维动态物体的识别和 检测。文献t 2 n 弓l a 免疫系统3 种模式( b 、1 、d ) 用于故障诊断。d a s g u p t a 将人工免疫网络 的分布性、鲁棒性、动态性、多样性和自适应性应用到计算机网络的安全领域，采用否 定选择算法进行计算机网络入侵检测。人工免疫系统工程应用还有模式识别1 2 8 刎、数据 分析1 3 0 j 、机器人1 3 l j 、负荷预测p 2 l 等。 受生物免疫系统启发而产生的人工免疫系统，作为计算智能研究的新领域，提供了 一种强大的信息处理和问题求解范式p ”。学者们展开了对基于a i s 的数据挖掘技术的研 究，并取得了些成果：h u n t 和c o o k e 将其研究的基于a i s 模型的无监督学习算法用于d n a 序列的分类任掣3 4 j ；t i m i s 构造了一种与领域无关的无监督机器学习方法用于实验数据 的聚类分析，并进一步给出了用于数据分析的有限资源a i s 模型r l m s 郾1 ；d ec a s t r o 提出 了基于免疫网络模型a i n e t 的高维原始数据的聚类分析方法【3 6 1 。 国内目前人工免疫系统的应用主要还是集中在网络安全、控制器设计、故障诊断等 方面，将人工免疫系统应用于网络安全方面的研究较多，文献1 3 1 中引入免疫算子，提出 一种新的免疫规划算法；文献【3 8 1 设计人工免疫网络入侵检测模型i d s ；谈英姿p 9 1 根据自 然免疫系统调节原理设计了免疫控制器。 然而a i s 在数据挖掘领域的研究和应用还处于起步阶段，采用a i s 模型的数据挖掘 任务也主要集中在数据聚类分析、数据浓缩、分类任务等方面，华南理工大学的李春华 等提出一种新型的自适应人工免疫网络算法用于离散数据的聚类分析。广西大学的梁美 莲等提出基于人工免疫系统的关联规则挖掘算法应用于数据库的记录挖掘中。如何将 a i s 在数据挖掘中的应用扩展到其他方面将是极富挑战和意义的课题。 从文献可以看出，人工免疫系统在w e bm i n i n g 方面的应用还很少，相对于其他领 域而言，总体上，技术还不够成熟，远没有达到传统w e bm i n i n g 技术的成熟的工商业 应用阶段。因此，可做的研究工作还有很多。关联规则挖掘也是数据挖掘的重要任务之 一，通常，挖掘关联规则需要找出所有满足支持度要求的频繁模式，这将面临极大的搜 索空间。a i s 基于生物免疫系统抗体多样性的遗传机理，提供了一种多点、随机的智能 搜索技术，并引人了免疫记忆机制，具有卓越的搜索性能。另一方面，抗体和抗原由氨 基酸的不同排列组成，而记录或模式也由不同的属性值排列组合而成，因此很容易在关 联规则挖掘与a i s 之间建立对应关系。通常将人工免疫算法与其他进化算法( 如遗传算 法) 相结合是提高算法执行效率的一种非常有效的手段。 4 t 传算lw e bu j y 1 中曲堋研，巴 1 4 遗传算法 遗传算法( g e n e t i ca l g o r i t h m - - g a ) ，是模拟达尔文的遗传选择和自然淘汰的生物 进化过程的计算模型，它是美国m i c h i g a n 大学的h o l l a n dj 教授于1 9 7 5 年首先提出 的【帅l 。遗传算法中包含了5 个基本要素：1 ) 参数编码；2 ) 初始群体的设定；3 ) 适应度函 数的设计；4 ) 遗传操作设计；5 ) 控制参数设定。 遗传算法是一种仿生全局优化方法。它模拟生命进化机制，将较劣的初始解通过一 组遗传算子，在求解空间按一定的随机规则迭代搜索，直到求得同题的最优解。遗传算 法具有许多不同于传统方法的优点，以至它在复杂的问题优化、模式识别、工程设计、 控制系统优化及社会科学等许多领域得到广泛的应用，并取得了较好的效果。遗传算法 具有的隐含并行性、易于和其它模型结合等性质，使得它涉足于数据挖掘领域。近年来， 它在数据挖掘中的应用也引起了人们的关注。遗传算法具有十分顽强的鲁棒性，其在解 决大空间、多峰值、非线性、全局优化等复杂度高的问题时具有独特的优势。其可以单 独用于数据仓库中关联规则的挖掘，还可以和其他的数据挖掘技术相结合。例如，用于 进化神经网络结构以得到结构简单、性能优良的神经网络结构1 4 i j ；用于特征子集选择1 4 2 ； 应用于决策树、分类器和模糊规则的获取等等。 在利用遗传算法进行数据挖掘研究方面已经有了一些有意义的工作。f l o c k h a ri a n w 等提出了一个基于遗传算法的数据挖掘系统g a 射i n e r ，该系统利用并行遗传算法从 数据库中发掘多种模式，可以支持用户不同层次的监督。c a t t r ar o b e r t 等提出了一个 利用遗传算法实现规则获取的数据挖掘系统，该系统利用遗传算法高效搜索大空间的能 力，实现以有监督和某些无监督的方式从大的、可能存在噪声的数据库中提取知识。 s z p i r og e o r g eg 提出了利用遗传算法搜索数据集之间函数关系的数据挖掘算法，该算 法将一些基本的函数形式和运算作为积木块，利用遗传算法对这些积木块进行组合，以 发现最近似实际系统行为的积木块组合形式，也就是可对系统行为进行全局近似的数学 模型。 遗传算法用于分类器始于8 0 年代初。9 0 年代后，遗传算法用于分类系统的理论得 到广泛的研究和应用。目前研究的重点是一些基本设计方法，如编码方式、信任分配函 数的设计，等具体问题以及遗传算法的改进上。陈文伟等人研制了一种遗传分类器系统 g c l s 。这种系统采用了训练和测试同时进行的策略，系统训练后能继续学习。适应不断 变化的环境采掘对脑出血和脑血栓两类疾病的分类规则，系统表现出满意的测试正确 率。张雪江等收集多种故障的大量实例，用遗传退火算法解决了区分各种故障的最优规 则。2 0 0 2 年北京工业大学的杨新武等提出一种基于遗传算法的一阶规则挖掘算法。安徽 大学的贾兆红等提出遗传改进算法在农业气象数据库中进行关联规则发现。2 0 0 3 年河北 科技大学的朱金钧等提出一种基于遗传的分类规则数据挖掘算法。2 0 0 4 年同济大学的高 正光等提出一个基于神经网络与遗传算法的数据挖掘体系结构，应用于分类问题。2 0 0 5 年广西大学的覃华等提出使用前馈型神经网络构做一个c r m 客户分类模型的思想，并用 竞生t 传算 lw e b 健一，乞十曲l 研竞 免疫遗传算法对其进行优化。 实验结果表明遗传算法具有较强的鲁棒性和搜索较好解的能力，但同时也存在一些 缺陷，如收敛速度慢、易出现早熟现象等。遗传算法的出现引起了许多学者的关注，针 对算法的不足，近2 0 年来，致力于推动遗传算法发展的学者们，对遗传算法的编码方 式、控制参数的选定、选择方式和交换机理等进行了深入的探究，引入了动态策略和自 适应策略以改善遗传算法的性能，提出了各种变形的遗传算法，其中主要的手段包括： 采用非标准的遗传操作算子，如：记忆算子 4 3 1 、顶端增强算子酬等；采用混合遗传算法， 如把模拟退火算法【4 5 】、爬山法【4 6 1 、梯度法等与遗传算法相结合的混合算法；采用并行遗 传算法【4 7 , 4 8 1 ；采用动态自适应技术1 4 9 】。 1 5 本文研究意义及内容安排 1 5 1 本文的研究意义 由于w e b 访问信息存在于每一台w e b 服务器上，因此其具有普遍性，并且遵循共 同的标准，那么开展这项研究具有广泛的普遍意义。 w e b 网站记录下来的这些数据等并不是信息，其中所蕴涵的大量有益信息至今却未 能得到充分的挖掘和利用。要想使数据真正成为一个公司的资源，只有充分利用它为公 司业务决策和战略发展服务才行，否则大量的数据可能成为包袱，甚至成为垃圾。w e b 数据挖掘技术提供了一种有效的解决方法。利用该技术建立电子商务推荐系统，公司通 过分析大量的交易记录，可以预测用户未来的购买需要，向用户推荐他可能感兴趣的商 品。从用户角度来看，通过对收集到的用户的访问行为、访问频度、访问内容等浏览信 息进行挖掘，提取用户的特征，获取用户访问w e b 的模式，为用户实现主动推荐，提 供个性化服务。而从企业角度来看，企业希望能够获取用户的访问规律、进一步优化网 站的组织结构和服务方式。以提高网站的效率。目前，w 曲挖掘已经是电子商务信息 技术的一个重要研究内容，得到越了来越多研究者的关注。 遗传算法的随机性、鲁棒性和隐含并行性，能快速、有效地进行全局优化搜索，是 处理大规模数据项目集的有效方法。所以本文旨在将免疫遗传的优点相结合，提出一种 有免疫功能的遗传算法。在遗传算法中加入了免疫算子，与遗传算法相比，不降低遗传 算法的鲁棒性，而且兼顾了搜索速度、全局和局部搜索能力。利用免疫遗传技术，改善 传统的w e b 使用挖掘中所采用的关联规则技术所得出的挖掘结果。首先进行数据的预处 理，得出模式分析阶段所需的数据后，采用基于免疫遗传算法的关联规则技术，发现有 用的关联规则，进而能够在w e b 使用挖掘的最后一个阶段在线推荐阶段，形成更好 的个性化推荐。 6 | t 柏鼻，崔l r e b 瑚u 靠娜中i l o l i 1 , q r 1 5 2 本文的内容安捧 论文系统、完整地分析和论述了w e b 挖掘中的各项技术。在此理论基础上，引入 了免疫遗传算法的思想，根据网站的1 5 t 志对w e b 页面进行了w e b 页面关联规则挖掘的 研究论文的整体组织如下： 第一章引言 介绍了本课题的研究背景，主要内容和论文的组织结构 第二章w 曲挖掘 综合分析研究了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 6 本人主要工作 在本论文中，本人所作的主要工作如下： l 、分析了w e b 挖掘技术的三种分类：w e b 内容挖掘、结构挖掘和使用挖掘的各自 技术特点，总结了其研究成果。并对现有的基于w e b 挖掘的关联规则技术做了深入地 分析。仔细研究了人工免疫系统和遗传算法的理论基础及其在数据挖掘中的应用，对现 有的免疫和遗传算法的优缺点进行了分析。 2 、把遗传算法应用到w e b 关联规则挖掘中，并分析了实验结果。 3 、提出基于免疫遗传算法的w e b 关联规则挖掘模型，并把实验得出的关联规则结 果同传统遗传算法进行了比较。 7 e 。f t 囊峥在l e b 口u 靠舅中曲l j f j t 1 7 本章小结 本章首先给出了论文的研究背景：数据挖掘己成为计算机科学研究中的一个十分活 跃的前沿领域，i n t e r a c t 的飞速发展，作为一个提供海量信息的源泉，进行w e b 挖掘工 作就变的非常有意义。 然后，我们简单介绍了人工免疫系统( a r t i f i c i a li m m u n es y s t e m ，a i s ) 和遗传算法 ( g e n e t i ca l g o r i t h m s ，g a ) 及该算法的各种应用研究。最后，给出了本论文的总体内 容架构和本人的主要工作。 8 竞基鱼传尊，毫i r e b 使用把l 中曲u _ | 哥兜 2 1w e b 挖掘概述 第二章w e b 挖掘 随着以数据库、数据仓库等数据仓储技术为基础的信息系统在各行各业的应用，使 海量数据不断产生。随之而来的问题是如此多的数据让人难以消化，无法从表面上看出 他们所蕴涵的有用信息，更不用说有效地指导进一步的工作。如何从大量的数据中找到 真正有用的信息成为人们关注的焦点，数据挖掘技术也正是伴随着这种需求从研究走向 应用。 在互联网技术的强力推动下，w e b 己成了信息制造、发布、加工和处理的主要平台， 上面承载的数据量正在迅速膨胀。为了帮助用户在浩如烟海的w e b 中迅速找到相关的信 息，自动从w e b 文档和服务中发现和抽取信息的w e b 挖掘( w e bm i n i n g ) 技术己成为一 个数据挖掘研究的热点。 w e b 挖掘指使用数据挖掘技术在w w w 数据中发现潜在的、有用的模式或信息。w e b 挖掘研究覆盖了多个研究领域，包括数据库技术、信息获取技术、统计学、人工智能中 的机器学习和神经网络等。 w e b 文档和服务包含的数据，常总称为“w e b 数据”。按文献 5 0 , 5 h 的分类方法，w e b 数据主要分为三类： ( 1 ) 内容数据( ( c o n t e n td a t a ) ：它是提供信息的主体，包括文本，声音，图像和元数据。 内容数据主要以各种文档形式存在，譬如h t m l 文件和其他各种非文本的媒体文件。 内容数据的其他约定成俗的概念还有“w e b 文档”或者“w e b 页面”( w e bp a g e ) 。 ( 2 ) 结构数据( ( s t r u c t u r ed a t a ) ：它是对内容数据组织而派生的数据。内容数据大部 分用h t m l 描述，超链接被广泛用于组织w e b 文档和w e b 文档内部的数据实体。由此 w e b 上就存在着由各种超链接形成的结构( 也包含超链接的描述) 。此结构又分为站点 结构和站间结构两部分。 ( 3 ) 使用数据( u s a g eo a t a ) ：它是用户使用w e b 而衍生的数据。w e b 是一个不受时空限制 的交互式媒介，可在多个层面上记录和收集因用户访问而产生的数据。典型的方法是 在w e b 服务器端收集w e b 日志，它包含了大量h t t p 协议层面的数据。 2 2 w e b 挖掘分类 根据对w e b 数据的感兴趣程度不同，w e b 挖掘一般可以分为三类 4 1 ：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 挖掘的分类图。 9 囊l 鼍传# ，毫曲l 用挖中曲l 用研鼻 图2 - iw e b 挖掘的分类图 f i g u r e 2 一lt h ec l a s s i f i c a t i o no f w e bm i n i n g ( 1 ) w e b 内容挖掘 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 ed i s c o v e r yi nt e s t s ) ，但是，文本只是w e b 数 据的一种形式，因此，i ( d t 也是w e b 内容挖掘的一个特例。 ( 2 ) w e b 结构挖掘 w e b 结构挖掘是从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 w w 中的每 个服务器都保留了访问日志( w e ba c c e s sl o g ) ，记录了关于用户访问和交互的信息。分 析这些数据可以帮助理解用户的行为，从而改进站点的结构，或为用户提供个性化的服 务。这方面的研究主要有两个方向：一般的访闯模式追踪和个性化的使用记录追踪。一 般的访问模式追踪通过分析使用记录来了解用户的访问模式和倾向，以改进站点的组织 l o 结构。而个性化的使用记录追踪则倾向于分析单个用户的偏好，其目的是根据不同用户 的访问模式，为每个用户提供个性化的定制站点。 2 3w e b 使用挖掘 w e b 使用挖掘在新兴的电子商务领域有重要意义，它通过挖掘相关的w e b 日志记 录，来发现用户访问w e b 页面的模式，通过分析日志记录中的规律，可以识别用户的忠 实度、喜好、满意度，可以发现潜在用户，增强站点的服务竞争力。w e b 使用记录数据 除了服务器的日志记录外还包括代理服务器日志、浏览器端日志、注册信息、用户会话 信息、交易信息、c o o k i e 中的信息、用户查询、鼠标点击流等一切用户与站点之间可能 的交互记录。可见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 服务( 数据库、网络等) 的性能和其他服务质量是衡量用户满意度的 关键指标，w e b 使用挖掘可以通过用户的拥塞记录发现站点的性能瓶颈，以提示站 点管理者改进w e b 缓存策略、网络传输策略、流量负载平衡机制和数据的分布策略。 此外，可以通过分析网络的非法入侵数据找到系统弱点，提高站点安全性，这在电 子商务环境下尤为重要。 ( 3 ) 站点修改：站点的结构和内容是吸引用户的关键。w e b 使用挖掘通过挖掘用户的行为 记录和反馈情况为站点设计者提供改进的依，比如页面连接情况应如何组织、那些 页面应能够直接访问等。 ( 4 ) 智能商务：用户怎样使用w e b 站点的信息无疑是电子商务销售商关心的重点，用户 一次访问的周期可分为被吸引、驻留、购买和离开四个步骤，w e b 用法挖掘可以通 过分析用户点击流等w e b 日志信息挖掘用户行为的动机，以帮助销售商合理安排销 售策略。 毫t t ，毫n e bm 抽中曲l 用i 拜毫 ( 5 ) w e b 特征描述：这类研究跟关注这样通过用户对站点的访问情况统计各个用户在页 面上的交互情况，对用户访问情况进行特征描述。 w e b 使用挖掘一般有4 个过程：数据预处理( d a t ap r e p r o c e s s i n g ) 、模式发t 现( p a t t e r n d i s c o v e r y ) 、模式分析( p a t t e r na n a l y s i s ) 及模式应用( p a t t e r na p p l i c a t i o n s ) 。 如图2 - 2 所示。 源数据一 用皇烹要毒 规则、模式。 w e b 事务文件一 有实际意义的 规则、模式一 数据预处理一模式发现一模式分析一应用一 2 3 1 数据预处理 图2 - 2w e b 使用挖掘四个过程 f i g u r e2 - 2t h ef o u rp a r to f w e bu s a g em i n i n g w e b 使用挖掘首先要对挖掘数据进行预处理，其目标是将包含在多种数据源中的信 息转化为适合数据挖掘和模式发现所必需的数据抽象概念，然后在事务数据库上实施挖 掘算法，以期最终获得有价值的规律。预处理主要对用户访问同志进行数据清洗( d a t a c l e a n i n g ) 、用户唯一性识另l j ( u s e r i d e n t i f i c a t i o n ) 、用户会话识别( i d e n t i f y u s e r s e s s i o n ) 、 路径补充( p a t hc o m p l e t i o n ) 和事务g 嬲u ( t r a n s a c t i o ni d e n t i f i c a t i o n ) 等处理： 2 3 1 1 源数据收集 w e b 用户访问数据可以从3 方面收集：服务器端( s e w e r ) 、客户端( c l i e n t ) 和代理端