（计算机软件与理论专业论文）基于用户行为和遗传算法的用户建模研究.pdf

重庆大学硕士学位论文 中文摘要 摘要 随着i n t e r n e t 的迅速发展，各种信息呈指数级的速度增长，信息类型也越来 越多。如何有效地解决信息过载和信息迷失带来的种种问题，如何满足各种用户 不同的个性化需求等，是研究人员面临的新课题，个性化服务已经成为当前信息 服务领域的研究热点之一。用户兴趣建模技术作为个性化服务的核心问题，主要 是研究如何有效地组织用户的兴趣源、用户兴趣的表示、更新以及存储等。本文 针对向量空间模型下不同的应用需求提出了两种基于用户行为的用户建模方法， 实验验证这两种建模方法均能提供较为精确有效的用户兴趣描述。本文的研究内 容及成果如下： 首先，分析了传统的浏览时间转化为用户兴趣的方法之后，提出了一种将用 户浏览时间表示为用户兴趣度的非线性转换方法。该方法以不同用户的平均浏览 时间为标准，将用户浏览时间转化为o n i 之间的兴趣表示。这不仅满足本文用户 建模的要求，也同样适合其它对浏览时间有类似变换要求的场合。 其次，在对于传统的基于遗传算法用户建模分析的基础上，结合浏览时间的 非线性变换，提出了一种基于浏览时间和遗传算法的用户建模算法。该算法是一 种简单、实用的方法，具有较高的效率和准确性。 然后，在基于对其它用户行为分析的基础上，结合用户行为的线性回归模型， 提出了一种基于综合行为和遗传算法的用户建模算法。该方法虽然效率略低，但 能获得比基于浏览时间和遗传算法的用户建模方法更高的准确性。 最后，采用知名网站的标准分类页面作为测试集，针对本文提出的用户兴趣 建模方法，做了较为充分的验证实验。一方面将文中的方法和传统的方法做了比 较；另一方面将文中的两种方法做了对比。结果表明：文中的方法都能较好地描 述用户兴趣。 上述取得的研究成果，在个性化服务领域中具有很好的学术参考价值和较好 的应用价值。 关键词：浏览时间，非线性，遗传算法，适应度函数，用户兴趣，用户模型 重庆大学硕士学位论文 英文摘要 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to ft h ei n t e r n e t ，t h ei n f o r m a t i o no ni ti n c r e a s e sa st h e i n d e xi l u m b e r , a n dt h ec a t e g o r i e so fi n f o r m a t i o nb e c o m em o r ea n dm o l e r e s e a r c h e r s h a v et of a c et h ei l e wt a s k s ，s u c ha sh o wt od e a lw i t ht h ep r o b l e m so fi n f o r m a t i o n o v e r l o a d i n ga n di n f o r m a t i o nm a z i n g pp e r s o n a l i z e ds e r v i c eh a si i o wb oo m e dt ob ea f o c u sr e s e a r c hi nt h ed o m a i no f i n f o r m a t i o ns e r v i c e a st h ec o r eo f p e r s o n a l i z e ds e r v i c e ， t h et e c h n o l o g yo fc o n s t r u c t i n g1 l s e rp r o f i l ef o c u s e so nh o wt os t r u c t u r et h eu s e r s i n t e r e s ts o u r c e ，u s e rp r o f i l ep r e s e n t a t i o n , u s e rp r o f i l eu p d a t i n g , u s e rp r o f i l es t o r a g e ，a n d s oo n i nt h i sp a p e r , t w oi l e wm e t h o d so fc o n s t r u c t i n gu s e rp r o f i l e ，w h i c ha r eb a s e do n u s e rb e h a v i o ra n dg aa r ep r o p o s e di nv e c t o rs p a c em o d e l t h ef i n a le x p e r i m e n t v a l i d a t e st h a tt h et w on e wm e t h o d sc a np r o v i d eu s e rp r o f i l ea c c u r a t e l ya n de f f e c t i v e l y t h em a i nr e s e a r c ho f m i sp a p e ri n c l u d e ss u c ha s p e c t s 髂b e l o w ： f i r s t ，b a s e do na n a l y z i n gt h et r a d i t i o n a lm e t h o d so ft r a n s f e r i n gv i e w i n g - t i m ei n t o u s e ri n t e r e s tl e v e l ，an e wm e t h o dt h a tt r a n s f e rv i e w i n g - t i m ei n t ou s e ri n t e r e s tl e v e l w h i c hi sb e t w e e n0a n d1n o n l i n e a r l yb a s e do na v e r a g et i m ei sp r o p o s e d i tf u l f i lt h e d e m a n do ft h em e t h o do fc o n s t r u c i n gu s e rp r o f i l ei nt h i sp a p e r , a n di ti sa l s of i tf o rt h e c i r c u m s t a n c e st h a tn e e dt r a n s f e rv i e w i n g - t i m ei n t ou s e ri n t e r e s tl e v d s e c o n d a f t e ra n a l y z i n gt h et r a d i t i o n a lm e t h o d st h a tc o n s t r u c tu s e rp r o f i l e 诵t hg a ， c o m b i n i n gt h em e t h o do f t r a n s f e r i n gv i e w i n g t i m ei n t ou s e ri n t e r e s tl e v e ln o n l i n e a r l y , a l l e wm e t h o dt h a tc o u s t r u c i n gu s e rp r o f i l eb a s e do nv i e w i n g - t i m ea n dg ai sp r o p o s e d i t i sn o to n l ys i m p l ea n du t i l i t y , b u ta l s om o r ee f f i c i e n ta n da c c u r a t e t h i r d ，a n a l y z i n go t h e ru s e rb e h a v i o r sa n dc o m b i n i n gl i n e a rr e g r e s s i o nm o d e l b a s e do nu s e rb e h a v i o r , an e wm e t h o dt h a tc o n s t r u c t su s e rp r o f i l eb a s e do nu s e r b e h a v i o r sa n dg ai sp r o p o s e d t h o u g hi t se f f i c i e n c ei sal i t t l el o w e r , b u ti ti sm o r e a c c u r a t et h a nt h em e t h o db a s e do i lv i e w i n g - t i m ea n dg a f i n a l l y , t h es t a n d a r dc l a s s i f i e dw e bp a g e sf r o mt h ew e l l - k n o w ni n t e r n a t i o n a lw e b s i t ea r ec o l l e c t e da st h et e s t i n gi n s t a n c e sa n dt h ep e r f o r m a n c eo ft h en e wm e t h o d so f c o n s t r u c t i n gu s e rp r o f i l et h a ta r ep r o p o s e di nt h i sp a p e r i sc o m p a r e dw i t he a c ho t h e ra n d at r a d i t i o n a lm e t h o d t h ec o m p u t a t i o n a lr e s u l t ss h o wt h a tt h en e wm e t h o d sp r o p o s e di n t h i sp a p e rc a nc o n s t r u c tt h eu s e rp r o f i l ea c c u r a t e l ya n de f f i c i e n t l y i i 重庆大学硕士学位论文 英文摘要 t h er e s e a r c ha b o v eh a sg o o da c a d e m i cr e f e r e n c ev a l u ea n dg o o da p p l i e dv a l u ei n t h ed o m a i no f p e r s o n a l i z e ds e r v i c e k e y w o r d s ：v i e w i n g - t i m e , n o n - l i n e a r , g e n e t i ca l g o r i t h m s ，f i t n e s sf u n c t i o n , u s e r p r o f i l e i l l 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重麽太堂 或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本 研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：何彤盈) 签字日期：卿年珀日 学位论文版权使用授权书 本学位论文作者完全了解重麽盍堂有关保留、使用学位论文的 规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许 论文被查阅和借阅。本人授权重庆盘堂可以将学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存、汇编学位论文。 保密() ，在年解密后适用本授权书。 本学位论文属于 不保密( ) 。 ( 请只在上述一个括号内打“”) 学位论文作者签名：9 孑彩彩导师签名：学位论文作者签名：y 勺夕、吃)导师签名： 签字日期：佣年多月fe l签字日期：棚年6 月f 日 f 3 重庆大学硕士学位论文1 绪论 1 绪论 1 1 选题背景 随着i n t e r n e t 的普及发展，人们已经进入了一个信息化社会，信息对日常的 生活起到了越来越重要的作用，人们可以方便地接触到大量的信息，信息资源不 足的问题再也不存在。但是人们也感觉到，目前最大的问题不是信息的缺乏或不 足，而是信息量的严重膨胀，信息查询的困扰，人们突然发现他所面对的信息远 远超出其处理能力。现代社会已经进入了一个“数据爆炸”和“信息丰富，但有 用信息获取困难的社会”【1 川。人们不得不借助一些信息查询工具进行查询，其中 利用最多的就是搜索引擎( s e a r c he n g i n e ) 【”】。使用搜索引擎主要存在以下问题 f 8 1 l 】 搜索的精度不高。有时返回太多的信息，其中包含大量的不相关的信息， 需要用户自己判断哪些有用，哪些没用。 排列无序问题。一个查询返回的结果可能有数千条，与用户需求最相关的 信息可能排在最后。 没有针对不同用户的个性化的信息搜索服务。即不问用户，针对同一个关 键词所提出的搜索请求，返回的结果是相同的。 其中第3 个问题是解决其它问题的关键。只有实现信息服务的个性化，才能做 到提高搜索精度，节约用户获得信息的时间。 个性化信息服务的主要目的就是要为用户提供个性化的信息。个性化信息服 务应该是能够满足用户的个体信息需求的一种服务，即根据用户提出的明确要求 提供信息服务，或通过对用户个性、使用习惯的分析而主动地向用户提供可能需 要的信息服务。个性化信息服务是网络信息环境发展的产物，是信息服务发展的 必然趋势。个性化服务的第一个层次是提供一个个性化接口供用户进行个性化定 制，系统根据用户提出的明确要求，向每一个用户提供符合要求的信息；第二个 层次是通过对用户个性、使用习惯的分析和跟踪，系统不断学习、挖掘用户潜在 的兴趣特征，主动向用户推荐其可能感兴趣的信息，提供智能的信息服务。 个性化服务的实质是要针对不同的用户采取不同的服务内容，就是为特定的 用户指定特定的w 曲内容和应用，m p w e b 内容开发人员基于某些条件为特定的个人 或用户组剪裁信息或一个应用，尽可能使得每个用户在浏览该站点时感觉到他是 站点的主人，站点能为他提供特殊的服务，尽可能地迎合每个用户的浏览兴趣并 且不断地根据用户的浏览兴趣的变化来调整站点的内容和结构。个性化服务在当 前学术界和商业界应用中都是很热门的研究领域。 重庆大学硕士学位论文 i 绪论 个性化服务技术的关键是如何高效、准确地获取用户兴趣。用户兴趣获取的 准确与否直接关系到个性化服务的质量。而遗传算法的全局搜索能力和鲁棒性等 特征，使其在个性化服务领域有着广泛的应用前途。因此根据个性化服务的具体 要求，将遗传算法等智能计算方法应用到个性化服务中具有重要的意义。尤其对 于个性化服务领域的用户兴趣建模等某些关键问题的解决具有重要作用。 1 2 国内外研究现状 1 2 1 个性化服务的应用现状 目前，一些信息供应商提出了个性化的信息服务的概念。如y a h o o 、p h y s i c i i n f o r m a t i o nc u s t o m i z e r 和f i s h w r a ps y s t e m ，提出了个性化( p e r s o n a l i z e ) 信息 搜索。例如y a h o o ，用户首次登陆时，网站会提供一系列个人兴趣选择项，用户填 写并提交之后，在今后登陆时，网站会自动地把相关信息首先推送给用户，可以 说这具有一定的个性化。有代表性的个性化信息服务系统及方法如下： s a v v y s e a r c h ”1 。中介搜索系统，采用基于经验学习优化选择搜索引擎的方法， 具有智能选择多个远程搜索引擎以及与其交互的能力。其思想是根据用户提供的 术语以及以往搜索成功与失败的经验，建立一种中介索引。当用户提交一项查询 时，系统利用中介索引，分析影响性能的时间因素( 或称为最佳查询时间) 和经验 因素( 即某一个搜索引擎搜索某一类信息最佳) ，选择效益好的搜索引擎进行信息 检索，从而充分地利用了信息资源。 w e b w a t c h e r 1 3 1 。著名的导航器，它帮助用户在网上导航，同时研究其浏览习 惯，通过对用户选择“链路”或站点的跟踪学习，改善导航质量。其学习算法属 于一种强化学习算法。 y u r i q u i n t a n a 提出了一种利用用户个性信息的智能的信息过滤系统【1 4 1 。这个 系统中用户的个性信息包括用户访问过的网页、用来索引这些网页的标题及用户 关于各个网页的评价反馈( 不相关，有一些相关，非常相关) 。另外用户可以明确 地表达他感兴趣的一个或几个主题。因而此系统记录了用户明确表达的兴趣信息， 及用户对系统提供网页的相关性评价等个性特征信息，由这些特征系统自动生成 实时变化的用户兴趣集合。按照这个集合，系统可以给用户提供一种特殊定制的 个性化网页。 p e i - m i n c h e n 等人提出了一种根据“关键词表”来学习用户特性信息，并使用 这些特性信息进行信息查询的系绀”1 。这个系统除了完成用户输入信息的查询工 作外，还可以根据用户的反馈自动地更新关键词表，跟踪用户兴趣的变化，并把 这些信息存储起来，作为以后查询的依据。 这些系统在一定意义上完成了用户个性信息的获得和应用。但是用户个性是 2 重庆大学硕士学位论文1 绪论 个多维的、变化的范畴。对于浩如烟海的信息资源和变化不定的用户信息需求， 我们需要全面地研究用户信息需求的特征，并且把研究结果应用到个性信息的搜 寻，个性化信息服务系统的设计中去，来完成真正意义上的个性化信息服务。总 的来说，虽然个性化信息服务越来越引起人们的重视，但是现在没有非常好的用 户个性特征信息表示方法，没有好的个性信息匹配算法，也没有好的个性信息获 取系统。 通过分析个性化服务的各种技术环节，不难看出用户个性特征模型、用户描 述文件的表达与更新、个性化的特征提取显得尤其重要 1 6 - 1 7 】。而用户的行为归根 结底是由其认知过程决定的。但是，由于用户认知过程的机理比较复杂，其中的 不确定性因素太多，目前还不能用一个精确的模型来描述。鉴于这方面的复杂性， 近年来已将一些人工智能的方法应用到个性化服务中。尤其遗传算法以其全局寻 优、简单通用、鲁棒性强、适用于并行处理等特点在个性化服务领域被广泛应用1 1 8 1 。 1 2 2 用户建模现状分析 在个性化服务中，用户兴趣描述是极其重要的内容，一直是个性化服务的研 究重点。用户建模按用户兴趣的获取方式的不同可以分为显式反馈的用户建模方 式和隐式反馈用户建模方式。 显式反馈方式通过用户提供对每一个项目评价的范围得到用户兴趣的相关 反馈信息。可以用户通过回答特定问题、提交关键词、设定主题或参与训练等方 式给出评价，主动地完成自己信息需求的设定。这种方式需要用户事先总结自己 的信息需求，并能准确地表达，或是在浏览网页的同时给出自己对于特定网页的 评价。 但是由于语言表达和分类的模糊性与多样性，用户很难利用这种方法将信息 需求的方向表达清楚。另外，因为这种方式需要用户主动填写，系统的灵活性较 差，如果用户未将自己己经变化了的兴趣提交给系统，系统便无法获知用户新的 兴趣和需求，也就无法根据用户的新兴趣及时提供给用户所需的信息。 此外，c a r r o l l 和r o s s o n 的心理学研究表明：即使用户知道他的工作在不久 后会给他带来好处，用户仍然不愿意参与这个训练过程【1 9 】。事实上，要求用户在 浏览过程中对页面进行标注会干扰用户的正常浏览，降低系统的可用性：而且， 随着浏览时间的延长，用户的兴趣主题和评价标准并不稳定。 隐式反馈的方式下，系统通过对用户日志的挖掘可以发现用户的浏览行为、 阅读习惯、访问模式等个人信息，从而提取出用户的兴趣构建用户模型。这种方 法能够适应用户兴趣的变化，不会干扰用户的工作，有利于提高个性化信息服务 系统的易用性。 总的说来，作为个性化服务的基础与核心技术，用户兴趣获取技术还不成熟， 3 重庆大学硕士学位论文i 绪论 没有形成完整的技术体系，还有一些关键技术尚待解决。隐式反馈方式的用户建 模由于其独特的优点在个性化服务领域成为了研究的热点。 1 2 3 基于浏览行为的用户建模现状 基于浏览行为的用户建模是属于隐式反馈方式的用户兴趣建模。按用户兴趣 获取时考虑的用户行为种数的不同，可以分为基于单种行为和基于综合行为的用 户建模。所谓的综合行为是指两种或两种以上的行为。 基于单种行为的用户建模 对于用户访问页面的次数而言，访问的次数越多，表明用户对页面越感兴趣。 基于用户访问页面的次数文献 2 0 提出了一种基于用户访问次数估计用户兴趣的 方法。该方法认为对于用户在时间段t i m e s p a n 内浏览的页面，访问次数f r e q ( w ) 越大，用户兴趣i n t e r e s t ( w ) 就越大，也即：i n t e r e s t ( w ) = f r e q ( w ) 。 由于兴趣度在0 和1 之间取值，将上式归一化后的用户兴趣度表示为： i n t e r e s t ( w 1 ：! 型型 m u x ( f r e q ( u ) ) 其中，u 为时间段t i m e s p a n 内用户访问的所有页面的集合。 在基于单种行为的用户建模方法中，更多的是基于浏览时间的建模。文献 认为用户在页面上驻留的时间越长，表明用户对页面越感兴趣。于是提出了一种 基于用户访问页面的驻留时间计算用户兴趣度的方法： i n t 嗽s t ( w 1 ：坐堕坐! ! ) _ 、。m a u x ( d u r a t i o n ( v ) ) 其中u 是用户访问的页面集。w 是用户浏览的页面，d u r a t i o n ( w ) 是用户浏览页面 的驻留的时间，i n t e r e s t ( w ) 是用户兴趣度。 基于综合行为的用户建模 文献。”就介绍了根据用户是否保存页面和在页面上的驻留的时间来判断用户 对页面是否感兴趣，如果用户保存了某个页面，则认为用户对该页面感兴趣，如 果用户在某个页面上驻留的时间很短，则认为用户对该页面不感兴趣。 文献乜2 3 提出一种用户建模方法：通过对用户浏览的w e b 页面进行聚类分析， 并与采用线性回归分析用户浏览行为相结合，得到了采用加权关键字矢量表示的 用户兴趣模型。其关键字矢量的权等于子类兴趣度按下式计算得到： i n t c r c s t d e g r e e ( i , ) - - ， s - i 其中，l i 为兴趣子类中任一页面i 的兴趣度( 由行为分析计算得到) ，1 1 1 为兴趣 子类中的页面数目。 4 重庆大学硕士学位论文 1 绪论 基于浏览行为的用户建模，目前存在的主要问题是： 1 ) 基于浏览行为的用户兴趣表示不够准确 用户行为的确能够体现用户感兴趣的程度。但如何用用户的行为来量化用户 的兴趣，目前虽然有一些方法，但都比较粗略。缺乏比较准确的表示方法。 2 ) 用户模型的效果不理想 用户模型的准确与否，直接关系到个性化推荐和个性化服务的质量。在流行 的向量空间模型中，待推荐的文档都表示成向量的形式，一些模型将用户兴趣表 示成非向量的形式，不利于将文档和用户兴趣做相似度比较。严重影响了个性化 推荐的质量。 1 3 课题提出的意义 实现个性化服务的关键，就是对w 曲用户浏览信息进行正确的分析，准确地 描述用户的兴趣。只有准确地把握用户的浏览兴趣，才能将用户感兴趣的资源推 荐给用户，也才能在用户群之间进行准确地协作推荐。 准确地描述用户的兴趣主要包括三个方面：准确地捕捉用户的浏览信息； 从用户浏览过程中准确地挖掘出体现用户兴趣的行为等信息；采用准确的方 法处理用户行为以便于表示用户兴趣；采用准确的表示方法来表示用户兴趣。 在个性化服务系统研究中，本课题属于其中的一个关键部分。对提高个性化 服务的质量具有重要的意义。 1 4 本文研究的内容 针对当前个性化服务面临的种种问题，本文提出基于用户行为和遗传算法的 用户兴趣建模方法，该方法能够结合用户的浏览内容和浏览行为建立用户兴趣描 述向量，为用户提供更为精确有效的个性化服务。 首先，分析了用户的浏览时间的特性之后，提出了一种将用户浏览时间表示 为用户兴趣度的非线性的转换方法，然后在该方法的基础上提出了一种基于浏览 时间和遗传算法相结合的用户兴趣获取算法。 其次，在前面对于浏览时间分析的基础上，进一步分析了用户的其他行为。 认为用户的浏览时间和翻页拉动滚动条行为与其他行为相比不仅具有典型性， 而且它们的组合能更好地表达用户的兴趣。利用回归模型，提出了基于浏览行为和 遗传算法相结合的用户兴趣获取方法。 最后，采用知名网站的标准分类页面作为测试集通，针对本文提出的用户兴 趣建模方法，做了较为充分的验证实验。一方面将文中的方法和传统的方法做了 比较；另一方面将文中的两中方法做了对比。结果表明：文中的方法都能较好地 5 重庆大学硕士学位论文1 绪论 描述用户兴趣。实验结果表明，本文所采用的基于用户行为和遗传算法的用户兴 趣建模方法能够更为准确的描述用户兴趣，提高推荐质量，整个研究工作在用户 兴趣建模和个性化服务领域中具有很好的学术参考价值和应用价值。 1 5 本文组织结构 本文的组织结构如下： 第一章绪论：主要介绍和分析了个性化服务的应用、用户兴趣的获取方法和 遗传算法在个性化服务领域的应用的国内外研究现状和面l 临的问题，本课题的意 义，以及本文的主要研究工作。 第二章基于浏览时间的用户建模：分析了用户的浏览时间的特性之后，详细 介绍了本文提出的将用户浏览时间表示为用户兴趣度的非线性的转换方法，然后 讲述了在该方法的基础上提出的基于浏览时间和遗传算法相结合的用户兴趣建模 算法。 第三章基于综合行为的用户建模：在对于浏览时间分析的基础上，进一步分 析了用户的其它行为。重点分析了用户的浏览时间和翻页拉动滚动条行为并指 出这两种行为对于其它用户行为而言具有较好的代表性，它们的组合能更好地表 达用户的兴趣。然后借助流行的线性回归模型方法，给出了基于浏览行为和遗传 算法相结合的用户兴趣获取算法的具体设计。 第四章实验与结果分析：主要介绍了实验系统设计和数据预处理，并对实验 结果数据进行了分析说明。 第五章总结与展望：总结了本文的研究工作与存在的不足，并提出了进一步 研究的方向 6 重庆大学硕士学位论文 2 基于浏览时问的用户建模 2 基于浏览时间的用户建模 用户浏览网页的时间作为一种特殊的用户浏览行为，由于其易于获取、处理， 并且对用户兴趣准确的表现力，一直以来成为基于隐式反馈方法用户建模研究的 重点。本章主要讨论是在向量空间模型中，基于浏览时间的用户兴趣度量以及用 户兴趣建模方法。 2 1 传统的基于遗传算法的用户建模 2 1 1 遗传算法简介 遗传算法的基本原理和方法 遗传算法( g e n e t i c a l g o r i t h m ，简称g a ) 是上一世纪7 0 年代由美国密西根州 ( m i c h i g a n ) 大学的h o l l a n d 教授提出的一种计算理论，主要模拟自然界的生物遗传、 变异的进化过程，通过选择、交叉、变异等算子来体现g a 的思想。g a 是一种启发 式全局寻优算法，它的两大特点是并行性处理和很强的全局寻优能力，是机器学 习的重要方法田】。 1 ) 基因链码：生物的性状是由生物的遗传基因的链码所决定的。使用遗传算 法时，需要把问题的每一个解编码成为一个基因链码。一个基因链码就代表问题 的一个解，在遗传算法中有时也把基因链码称作染色体。 2 ) 群体：个体组成了群体，一个群体是若干个个体的集合。由于每个个体代 表了问题的一个解，所以一个群体就是问题的一些解的集合。因此，还必须为遗 传操作准备由若干初始解组成的初始群体，初始群体也称作为进化的初始代。 3 ) 交叉：许多生物体的繁衍是通过染色体的交叉完成的。在遗传算法中使用 了这一概念，并把交义作为一个操作算子，实现过程如图3 1 所示，选择群体中的两 个个体x l 、x 2 ，以这两个个体为双亲做基因链码的交叉，从而产生两个新个体x l 、 x 2 作为它们的后代。简单的交叉方法是：随机地选取一个截断点，将x i 、x 2 的基因 链码在截断点切开，并交换其后半部分，从而组合成两个新的个体x i 、x 2 。在很 多的应用中，交叉算子是以一定概率发生的，这一概率称之为交叉概率。 双亲 x l 1 0 1 01 0 0 1 1 1 1 0 x 2 1 0 0 01 1 0 0 0 1 1 0 后代 x i 1 0 1 0 1 1 0 0 0 1 1 0 x 2 1 0 0 0 1 0 0 1 1 1 1 0 图2 1 遗传算法中的交叉算子 f i 9 2 1 t h eg r o s s o v e ro p e r a t o ri ng e n e t i ca l g o r i t h m 7 重庆大学硕士学位论文 2 基于浏览时间的用户建模 4 ) 变异：在生物体的繁衍过程中变异是一个重要的步骤。通过在染色体上的 某些基因位置产生突变使得新产生的个体与其他个体有所不同。该算子的实现方 法如下：对于群体中的某个个体，即基因链码，随机选取某一位，即某基因，将 该基因翻转( o 变为1 ，1 变为o ) 。 5 ) 适应度：生物体对环境的适应程度的不同而表现出不同的生命力。遗传算 法在搜索进化过程中一般不需要其它外部信息，仅用评估函数来评估个体或解的 优劣，并作为遗传操作的依据，评估函数值又称作适应度( f i m c s s ) 。 6 ) 选择：选择的目的是为了从当前群体中选出优良的个体，使它们有机会作 为父代产生后代个体。判断个体优良与否的准则就是各自的适应度值。这一操作 是借用了这样一种进化原则：个体适应度越高，其被选择的机会就越多。选择操 作在遗传算法中有多种实现方式，其中最简单的一种方法就是采用和适应度值成 比例的概率方法来进行选择。具体地说，就是首先计算群体中所有个体适应度 的总和z ，再计算每个个体的适应度所占的比例晦，并以此作为相应的选 择概率。这样，遗传算法就可以寻找具有最大适应度的个体。 遗传算法的适应度函数 遗传算法在进化搜索中基本上不用外部信息，仅用目标函数即适应度函数为 依据。遗传算法的目标函数不受连续可微的约束且定义域可以为任意集合。对目 标函数的唯一要求是，针对输入可计算出能加以比较的非负结果。这一特点使得 遗传算法应用范围很广。 在许多问题求解中，其目标是求取费用函数( 代价函数) g ( x ) 的最小值，而不 是求效能或利润函数l l ( x ) 的最大值。即使某一问题可自然地表示成求最大值形式， 也不能保证对于所有的x ，u ( x ) 都取非负值。由于遗传算法中，适应度函数要比较 排序并在此基础上计算选择概率，所以适应度函数的值要取正值。 在通常搜索方法下，为了把一个最小化问题转化为最大化问题，只需要简单 的把费用函数乘以1 即可，但对遗传算法而言，这种方法还不足以保证在各种情 况下的非负值。对此，可采用以下的方法进行转换： rc 。r 烈x )当颤x ) q c 。 t l x ) = l 0 其它情况 存在多种方式来选择系数c 。c 可以是一个合适的输入值，也可采用迄今为 止进化过程中甙x ) 的最大值或当前种群中g ( x ) 的最大值。当然c 一也可以是当前k 代中g ( x ) 的最大值。c 。最好与群体无关。 当求解问题的目标函数采用利润函数形式时，为了保证其非负性，可用如下 8 重庆大学硕士学位论文2 基于浏览时问的用户建模 u ( x ) + c m 缸当u ( x ) + c m i n o 0其它情况 式中系数c m i n 可以是合适的输入值，或是当前一代或前k 代中的颤x ) 的最小 值，也可以是群体方差的函数。 遗传算法的收敛性 遗传算法虽然可以实现均衡的搜索，并且在许多复杂问题的求解中往往能得 到满意的结果，但是该算法的全局优化收敛性的理论分析尚待解决。目前普遍认 为，标准遗传算法不保证全局最优收敛。 在遗传算法处理过程的每个环节都可能导致产生未成熟收敛的因素，具体表 现如下：1 ) 进化初始阶段，生成了具有很高适应度的个体x ；2 ) 在基于适应度比 例的选择下，其它个体被淘汰，大部分个体与x 一致；3 ) 相同的两个个体进行交 叉，从而未能生成新个体；4 ) 通过变异或逆转所生成的个体适应度高但数量少， 所以被淘汰的概率很大；5 ) 群体中的大部分个体都处于与x 一致的状态。 针对上述情况，需要在编码、适应度函数和遗传操作等设计中考虑抑制未成 熟收敛的对策。 2 1 2 遗传算法在用户建模中的应用 在向量空间模型中，文档表示成关键字及其权重组成的向量形式，我们将其 称作文挡向量。为便于做相似度比较，用户兴趣也表示威向量的形式，我们将其 称作用户兴趣向量。用户兴趣向量的获取比较困难，这就不得不采用一些人工智 能技术。 遗传算法代是一种十分重要的人工智能搜索技术，它能够模拟自然界的生物 的遗传、变异的进化过程，遗传算法正被越来越多的应用于个性化服务中3 2 啦】。 由于个性化服务中的文本信息通常采用向量空间模型( v s m ) 表示方法，而且这 样的模型通常属于高维空间，因此，遗传算法非常适合个性化服务在这方面的应 用，利用遗传算法应用于个性化服务的方法研究很多。随着对遗传算法研究的不 断深入完善，它已被应用于越来越广泛的领域。与此同时，应用于个性化服务的 方法也朝着多元化的方向发展，除了广泛采用的遗传算法之外，更多的方法也被 应用于个性化服务当中，包括数据挖掘4 3 1 、机器学习、人工智能4 6 1 、统计理 论 4 7 1 、粗糙集理论梆】和神经网络1 4 9 等，这些新方法的应用，给个性化服务带来了 新的生机。 人们将遗传算法灵活地应用于用户兴趣建模技术中。文本信息用特征向量空 9 、-，l 走 咿 换变 重庆大学硕士学位论文2 基于浏览时间的用户建模 间模型表示，用于g a 的种群称为染色体，每个染色体代表了用户兴趣模型的一 种可能的方案。染色体的初始化构成可以由系统随机的产生，如果系统在运行之 前已经有关于解决问题的部分信息，也可以由这些信息来初始化染色体。这些种 群中的个体通过选择、交叉和变异来模拟生物的遗传、变异的进化过程。当种群 不再改变，或者系统设定的一个遗传代数次数的最大值已经达到，系统将终止遗 传操作。最后经过g a 处理后得到的优化个体或者这些优化个体的结合就是最终 的用户兴趣模型。利用这些优化个体或者这些优化个体的结合得到的用户兴趣模 型，作为向用户推荐信息的过滤条件，向用户提供个性化推荐服务。在这一过程 中，适应度函数起着至关重要的作用，因为适应度函数值代表了个体的优劣程度， 如果适应度函数选择正确，它将能够引导种群朝着解决问题的最优方案进化。因 此，大多数将遗传算法都在适应度函数的选择和确定上做了深入的研究。 j o m g - t z o n gh o m g & c h i n g - c h a n gy e h 于2 0 0 2 年提出了一种全新的遗传算法， 该方法【3 5 】主要是对种群中染色体基因权重的重新调整，使之能够成为最优或是接 近最优的染色体。在该方法中，适应度函数的设计非常巧妙，不仅考虑到相关反 馈文档，而且将反馈得到的不相关文档也考虑在内，依靠相关文档和不相关文档 在推荐文档中出现的顺序来确定适应度函数值，而传统方法只将相关文档考虑在 内，而不考虑不相关文档，并且未考虑相关文档在推荐文档中出现的顺序。因此， 该方法不需要如传统方法那样设置阈值来确定一篇文档是否应该被作为相关文档 进行推荐( 设置阈值的方法很有可能影响推荐效果，比如阈值设置太低，将会向 用户推荐大量的文档，增加用户的选择负担，如果阈值设置太高，向用户推荐的 文档将会太少，而且很有可能大量用户感兴趣的文档没有被推荐出来) 。 适应度函数的计算过程：首先利用内积公式计算染色体和所有相关反馈文档的相 似度，将所有相关反馈文档按相似度值大小降序排列，最后由公式3 1 计算染色体 的适应度值： 1 侧厂俐、 f _ 占y i ，；猡三j j d i 智l 篙_ ，j 如果文档d i 是相关文档，则r ( d i 户l ，否则“d i ) = 0 ，1 i i d l ，其中d 为查询的反馈文 档，包括相关文档和不相关文档。例如，假设由染色体计算与所有文档的内积值 按降序排列，组成的集合d 为d l ，d 2 ，d 3 ，d 4 ，d 5 五篇文档，即染色体与文档d 的内 积值最高，与文档d 2 的内积值次之，与文档d 5 的内积值最小。其中文档d l ，d 2 ，d 4 是相关文档，文档d 3 ，d 5 是不相关文档，则 f = l 5 ( ( 1 1 + 1 2 + 1 3 + l 4 + 1 5 “l 2 + 1 3 + 1 4 + l 5 ) “1 4 + 1 5 ) ) = 0 8 3 3 3 3 3 该f 值即代表了该染色体的适应度值。 l 6 p e z 。p u j a l t e 于2 0 0 2 年提出了一种方法【3 3 】，该方法与j o m g - t z o n gh o m g 和 1 0 重庆大学硕士学位论文2 基于浏览时间的用户建模 c h i n g - c h a n g y e l l 提出的方法有类似之处，也考虑到了相关文档和不相关文档在反 馈文档中出现的顺序。适应度函数的计算过程是：首先利用余弦夹角公式计算染 色体和所有相关反馈文档的相似度，将所有相关反馈文档按相似度值大小降序排 列，最后由公式3 2 计算染色体的适应度值，再将该适应度值乘以染色体的召回率 来更新染色体适应度值。 忙p 艺o s ；l 去睁) ”1 】 、n 几， n u m 表示相关反馈文档个数，p o s 表示按照余弦夹角值降序排列后，文档d i 在相 关反馈文档中出现的位置，a 为待定参数，根据文献【3 3 】实验确定参数a 为2 。如果 文档d i 是相关文档，贝, l j r ( d i 户1 ，否则r 户1 。 l 6 p e z p u j a l t e 于2 0 0 2 年提出了另一种方法【剐，同样考虑到了相关文档和不相关 文档在相关反馈文档中出现的顺序。适应度函数的计算过程是：首先利用余弦夹 角公式计算染色体和所有相关反馈文档的相似度，将所有相关反馈文档按相似度 值大小降序排列，然后计算召回率从0 1 到0 9 时的不同精确率的平均值，即将此平 均值作为染色体的适应度值。 在文献啪1 中提出了一种基于用户评价的用户兴趣建模方法。该方法在建立用 户模型的时候也是通过遗传算法，但首先要求用户给出表示自己兴趣的0 到1 的 评价。具体算法描述如下： 从用户浏览的w e b 网页中提取n 篇 d ，d ：，d 3 ，甜，作为文档资源。 由用户分别给每篇文档d 。评分r ；，以表示用户偏好。 分别提取文档d i 的特征空间，表示为： d l = ( t 。f ：。) ，( t 。f ；。) ，( t 。，f j ，) 其中t 。，表示d 。中出现频率最高的前m 个单词，f l j 表示t j 的出现频率 初始化群体p = p r o f i l e 。p r o f i l e ：，p r o f i l e 2 ，p r o f i l e 。 t ，为随机从文档的特征空间中选取的单词，霄；j 为一个一1 到1 之间的一个随机的 数值，表示权重，并由这些权组成一个向量p = ( 眠，) 当演化代数小于m a x g e n 时，执行下列过程： 1 ) 随机选择一个个体p r o f i l e ；进行变异演化产生一个后代； 2 ) 随机选择两个个体p r o f il e 。和p r o f il e ，进行杂交演化产生两个后代； 3 ) 通过适应值函数f i t n e s s0 ，计算它们的适应值，取值最大的前n 个个体作为 下一带种群组成。 f i t * s s ( p r o f i l e , ) = n - g a p 万( p i 一, d j ) g a p ( 尸，协，j ) = 旧- s ，埘i 重庆大学硕士学位论文2 基于浏览时间的用户建模 当s i i i i ( p , d j l 0 当s i l i ，( p j 算 印 ( 2 1 ) 返回适应值最好的个体作为结果，算法结束。 虽然以上几种方法对适应度函数的设计做了很大改进，但是以上方法只考虑 了用户反馈，而用户在浏览网页时的行为等相关信息对用户建模的准确性有着非 常关键的作用，用户的浏览行为能从某种程度反应用户的浏览兴趣与偏好。因此， 本文提出一种新的结合用户的浏览内容和浏览行为建立用户兴趣描述方法。 2 2 基于浏览时间的用户兴趣表示 2 2 1 传统的基于浏览时间的用户兴趣表示方法 浏览时间以其易于获取、处理简单、能够准确表现用户浏览兴趣等特性，成 为用户兴趣学习领域研究的热点。以下简单介绍一些传统的基于浏览时间的用户 兴趣表示方法。 文献认为用户在页面上驻留的时间越长，表明用户对页面越感兴趣。也就 是说，对于页面w ，用户浏览页面的驻留的时间d u r a t i o n ( w ) 越大，用户兴趣度 i n t e r e s t ( w ) 就越大，也即： i n t e r e s t ( 霄) d u r a t i o n ( w ) 基于这种思想文献 2 0 提出了一种基于用户访问页面的驻留时间计算用户兴 趣的方法： i n t e r e s t ( w 1 ：堕型! ! 堡盟 。m a x ( d u r a t i o n ( v ) ) 其中u 是用户访问的页面集。 上式的实质是将线性归一化的驻留