（计算机软件与理论专业论文）用户兴趣模型建模方法研究.pdf

辽宁师范大学硕士学位论文 摘要 数据挖掘( d a t am i n i n g ) 是从存放在数据库，数据仓库或其他信息库中的大量的数 据中获取有效的、新颖的、潜在有用的、最终可理解模式的非平凡过程。其应用于网络 环境中则称为w e b 数据挖掘( w e bd a t am i n i n g ) 。w e b 数据挖掘是从w e b 中相关资源和 用户浏览行为中抽取感兴趣的、有用的模式和隐含的信息。w e b 使用挖掘是w e b 数据 挖掘的一种，挖掘的对象是用户在w e b 服务器上的信息，通过用户兴趣建模算法建立 用户兴趣模型，挖掘用户兴趣，为用户提供更好的浏览体验。在众多的建模方法中关联 规则和马尔可夫模型是两种非常重要的建模方法。 本文对关联规则以及马尔可夫模型的相关算法进行系统的分析和总结，然后再此基 础之上提出了新的建模方法： 首先，提出了基于最大频繁项目集的事务间关联规则的挖掘算法，由改进的m a f i a 算法，得到最大频繁项目集的同时得到对应的共有用户集，对事务内到事务间最大频繁 项目集的转换，分析不同用户之间的关系及用户对网站上不同网页的访问情况，直接发 现不同用户之间的关联关系来预测用户的兴趣。该方法经实验证明能够更加全面的预测 用户感兴趣的网页，更好的为用户提供个性化服务。 其次，在基于最大频繁项目集的挖掘事务间关联规则的算法的基础之上，结合两种 建立用户数据库的方法，提出基于二阶马尔可夫模型与事务间关联规则的用户兴趣预测 模型。 另外，本文以用户指向思想为核心，通过分析用户之间的关系从而映射到有相同 兴趣用户所对应的数据上，使找到的结果相对之前数据指向的结果更加符合用户的需 求。改进的m a f i a 算法，使得这种最大频繁项目集的算法能够记录找到的最大频繁项目 集中的项目在原数据中事务号的交集，从而方便使这种算法作用于事务间关联规则成为 可能。加入马尔可夫模型，将事务间关联规则与2 阶马尔可夫模型的结合起来，使事务 间关联规则的挖掘结果准确性大幅度提高。 在实际问题中，不同数据之间存在着一定的联系，关联规则就是用来找到这些联系 的方法。但是随着数据量的增多，数据冗余和结果准确度之间的矛盾凸显，所以采用事 务间关联规则来完善结果的准确性，同时加入马尔可夫模型的方法来解决数据冗余的问 题，通过实验证这种结果是有效的。 关键词：w e b 数据挖掘；用户兴趣模型；事务间关联规则；最大频繁项目集；马尔可夫 模型 用户兴趣建模方法研究 r e s e a r c ho f b u i l d i n gu s e ri n t e r e s t i n gm o d e l a b s t r a c t d a t am i n i n gi sat e c h n o l o g yt h a to b t a i n sv a l i d ，n o v e l ，p o t e n t i a l l yu s e f u la n du l t i m a t e l y u n d e r s t a n d a b l ep a t t e r n so fn o n - t r i v i a lp r o c e s sf r o md a t a b a s e s ，d a t aw a r e h o u s e so ro t h e r r e p o s i t o r i e so fl a r g ea m o u n t so fd a t a i ti so n eo ft h em o s td y n a m i ca r e a sw h i c hi na r t i f i c i a l i n t e l l i g e n c ea n dd a t a b a s e s w h e nt h ed a t am i n i n gt e c h n o l o g ya p p l i e d i nt h en e t w o r k e n v i r o n m e n t ，i ti sc a l l e dw e bd a t am i n i n g w e bd a t am i n i n gi sf r o mw e b u s e r st ob r o w s e t h er e l e v a n tr e s o u r c e sa n de x t r a c tb e h a v i o ra n di n t e r e s t ，u s e f u lp a a e m sa n di m p l i c i t i n f o r m a t i o n n ev a r i o u sf o r m so fd o c u m e n t a t i o n sa n du s e ra c c e s st oi n f o r m a t i o nc o n s t i t u t e s aw e bd a t am i n i n go b j e c t s t h ev a r i o u sw e bc o n t e n td e t e r m i n e st h ed i v e r s i t yo fw e bm i n i n g t a s k s a c c o r d i n gt ot h ed i f f e r e n td a t am i n i n go b j e c t s ，w e bd a t am i n i n gc a nb ed i v i d e di n t o w e bc o n t e n tm i n i n g ，w e bs t r u c t u r em i n i n ga n dw e bu s a g em i n i n g o n ei sw e b u s a g em i n i n g ， a l s ok n o w na sw e bl o gm i n i n g ，o rw e bu s e ra c c e s sp a t t e mm i n i n g ，m i n i n go b je c ti s i n f o r m a t i o nw h i c hu s e r sl e a v ei nw e bs e r 、，e r e s t a b l i s hu s e ri n t e r e s tm o d e lt h r o u g hu s e r i n t e r e s tm o d e l i n ga l g o r i t h m ，m i n i n gu s e r s 、i n t e r e s t sf r o mt h ei n f o r m a t i o n ，i no r d e rt op r o v i d e u s e r sab e t t e rb r o w s i n ge x p e r i e n c e a m o n gt h em a n ym e t h o d so fm o d e l i n g ，a s s o c i a t i o nr u l e s a n dm a r k o vm o d e l sa r et w oi m p o r t a n tm o d e l i n gm e t h o d s i np r a c t i c a lp r o b l e m s t h es a m ep r o je c tb e t w e e nd i f f e r e n td a t ao rt h ed i f f e r e n ti t e m s b e t w e e nd i f f e r e n td a t aw i l le x i s ts o m el i n k s a s s o c i a t i o nr u l ei st h em e t h o du s e dt of i n dt h e s e l i n k s b u ta st h ea m o u n to fd a t ai n c r e a s e s ，t h ec o n t r a d i c t i o nb e t w e e nt h ea c c u r a c yo fd a t a r e d u n d a n c ya n dt h ea c c u r a c yi n c r e a s e d s om i xt h em e t h o d so fi n t e r t r a n s a c t i o na s s o c i a t i o n r u l e sa n dm a r k o vm o d e lt os o l v et h e s ep r o b l e m s i nt h i sp a p e r ，f i r s t l yp r o p o s et h ei n t r a - t r a n s a c t i o na s s o c i a t i o nr u l e sa n dt h ei n t e r t r a n s a c t i o n a s s o c i a t i o nr u l e s ，a sw e l la st h er e l a t e dm a r k o vm o d e la l g o r i t h mf o rs y s t e m a t i ca n a l y s i sa n d s u m m a r y ，a n dt h e nb a s e do nt h i s ，p r o p o s ea n e w m i n i n ga l g o r i t h mt os o l v et h ec o r r e s p o n d i n g p r o b l e m ： f i r s t l y ，p r o p o s et h ei n t e r t r a n s a c t i o na s s o c i a t i o nr u l e sm i n i n ga l g o r i t h mb a s e do nm a x i m u m f r e q u e n ti t e ms e t s ，b yi m p r o v e dm a f i aa l g o r i t h m ，g e tt h em a x i m u mf r e q u e n ti t e m s e t sw i t h t h ec o r r e s p o n d i n gs e to ft o t a lu s e r s ，n a m e dc o m m o nu s e ri n t e r s e c t i o n ( c u i ) ，t h r o u g h c o n v e r s i n gt h em a x i m a lf r e q u e n ti t e r ns e to fi n t r a t r a n s a c t i o nt oi n t e r - t r a n s a c t i o n ，a n a l y z et h e r e l a t i o n s h i pb e t w e e nt h ed i f f e r e n tu s e r s ，a n a l y z i n gu s e ra c c e s st od i f f e r e n tp a g e so nt h ew e b s i t e ，d i r e c t l yf o u n dt h a tt h ea s s o c i a t i o nr u l e sb e t w e e nt h ed i f f e r e n tu s e r st op r e d i c tt h eu s e r s i i 一 a罗 辽宁师范大学硕士学位论文 i n t e r e s t s t h ee x p e r i m e n tp r o v e dt h a tt h em e t h o dc a np r e d i c tau s e ri n t e r e s t e di nam o r e c o m p r e h e n s i v ep a g e ，b e t t e rt op r o v i d ep a g e su s e r sm a yc o n s i d e r e da b o u t s e c o n d l y ，b a s eo nm i n i n gi n t e r t r a n s a c t i o na s s o c i a t i o nr u l e sw i t hm a x i m u mf r e q u e n ti t e m s e t s ，c o m b i n i n gw i t ht w ok i n d so fm e t h o d st o e s t a b l i s hu s e r s d a t a b a s e ，p r o p o s e dam o d e l b a s e do n2 n dm a r k o vm o d e la n da s s o c i a t i o nr u l e sn a m e dd u i m i na d d i t i o n ，t h i sp a p e rp r e s e n t ss o m en e wm e t h o d sa n di m p r o v e m e n t so fu s i n ga s s o c i a t i o n r u l e sa n dm a r k o vm o d e lt oe s t a b l i s hu s e ri n t e r e s t i n gm o d e l p r o p o s et h ec o n c e p to ft h eu s e r p o i n tb ya n a l y z i n gt h er e l a t i o n s h i pb e t w e e nu s e r sw i t hs i m i l a ri n t e r e s t sa n dt h u sm a p p e dt o t h ec o r r e s p o n d i n gu s e rd a t a ，s ot h a tt h er e s u l t sc a l lb e t t e rt os a t i s f yt h eu s e r s n e e d p r o p o s ea n i m p r o v e dm a f i aa l g o r i t h m m a k e st h i sm a x i m u mf r e q u e n ti t e ms e t sa l g o r i t h mc a nf i n dt h e m a x i m u mf r e q u e n tw i t hc u l ( a sa b o v e ) ，t h u sm a k ep o s s i b l et om a k et h i sa l g o r i t h mo nt h e t r a n s a c t i o nb e t w e e nt h ea s s o c i a t i o nr u l e s c o m b i n gm a r k o vm o d e lw i t ht h em e t h o dp r o p o s e d a b o v e i n t e r - t r a n s a c t i o na s s o c i a t i o nr u l e sa n d2 n dm a r k o vm o d e lr u nt o g e t h e rt oi n c r e a s ei n t h ea c c u r a c yo fm i n i n gr e s u l t s k e yw o r d s ：w e bd a t am i n i n g ；u s e ri n t e r e s t i n gm o d e l ；i n t e r t r a n s a c t i o na s s o c i a t i o nr u l e ； m a x i m u mf r e q u e n ti t e ms e t ；m a r k o vm o d e l i i i 月a11 用户兴趣建模方法研究 目录 摘要i a b s t r a c t i i l 绪论1 1 1 研究背景与意义1 1 2 国内外研究现状l 1 3 现有算法存在的问题_ 2 1 4 主要工作及论文组织：2 2 关联规则及马尔可夫模型的相关知识4 2 1 关联规则的基本概念：4 2 1 1 关联规则综述4 2 1 2 传统关联规则4 2 1 3 事务间关联规则4 2 2 关联规则的算法5 2 2 1 传统关联规则算法一5 - 2 2 2 事务间关联规则算法6 2 3 马尔可夫模型的基本概念7 2 3 1 马尔可夫模型综述7 2 4 马尔可夫模型的算法7 2 5 本章小结8 3一种基于最大频繁项目集的事务间关联规则挖掘方法9 3 1 相关知识一9 3 2 基本思想1 1 3 3 基于最大频繁项目集的挖掘事务间关联规则方法【2 5 1 1 1 3 3 1 算法基本步骤1 l 3 3 2 算法描述1 2 3 3 3 算法应用15 3 4 实验与分析1 6 3 5 本章小结17 4 双策略用户兴趣模型。l8 4 1 相关知识18 4 2 基本思想l9 辽宁师范大学硕士学位论文 4 3 用户兴趣模型d u i m ( d u a lu s e ri n t e r e s tm o d e l ) 2 1 4 3 1 建立双重策略用户数据库2 1 4 3 2 预测策略一：2 阶马尔可夫模型2 2 4 3 - 3 预测策略二：事务间关联规则2 3 4 3 4 算法应用2 4 4 4 实验与分析2 8 4 5 本章小结3 0 结论3l 参考文献：，3 3 攻读硕士期间撰写和发表的学术论文3 6 攻读硕士学位期间参与的科研项目3 6 致谢3 7 一v 一 用户兴趣建模方法研究 1绪论 1 1 研究背景与意义 随着i n t e m e t 的进一步发展和完善，各种基于i n t e m e t 的应用业务也如雨后春笋般的 发展起来，例如网上购物、网上银行、远程教育、远程医疗等。我们应该看到i n t e m e t 在给我们带来机遇的同时也带来了挑战。随着应用越来越复杂，数据量越来越大，w w w 上的一些主要工作，例如w e b 站点设计、电子商务等变得更为复杂和繁重。+ 这就需要 从用户的访问兴趣、访问频度、访问时间等方面动态的调整页面结构，改进服务，开展 有针对性的电子商务以更好的满足访问者的需求【l l 【2 】。解决这种需求的一个有利的工具 就是w e b 数据挖掘。 数据挖掘历史较短，从上世纪9 0 年代以来得到了蓬勃的发展。用于发现数据之间 的潜在关系，还可以被用于决策支持、信息管理、过程控制、查询优化等。数据挖掘是 一门交叉学科，它具有分类、聚类、关联规则和序列模式的发现、预测、偏差的检测等 多种功能，各项功能互相联系，共同发挥作用。当数据挖掘技术应用于网络环境下的 w e b 中，就称为w e b 数据挖掘。根据数据挖掘对象的不同，可以将w e b 数据挖掘分为 w e b 内容挖掘、w e b 结构挖掘和w e b 使用挖掘三类【3 儿4 。 其中，w e b 使用挖掘【5 1 【6 1 1 7 】【8 】【9 1 能够从服务器、浏览器端的同志记录和用户的个人信 息中自动发现隐藏在数据中的模式信息，以获得有价值的、描述用户行为的模型，做出 预测性分析，从而改进w e b 站点的结构和性能，提高查找信息的效率和质量。随着 w e b 应用和规模的快速增长，研究w e b 使用挖掘技术的需求将日益增加。 w e b 使用挖掘一般通过如下几步来完成用户兴趣的预测数据预处理、模式挖掘 和模式分析。同样是由这几部分组成用户兴趣预测模型，数据预处理去除数据中的噪声 ( 如图像、声音、视频、无用的网页日志等) ，模式挖掘使用相关算法来发现经过预处 理的数据中潜在的关系，并在模式分析中分析这些结果，最后将用户感兴趣的内容推荐 给用户。 1 2 国内外研究现状 7 已有的建模方法多种多样，不仅仅有使用分类、聚类、关联规则这样的传统方法， 近几年有将聚类、马尔可夫模型和关联规则整合的模型，也有关联规则和马尔可夫模型 整合的模型。这些模型都是在提高预测结果准确度和提高算法效率上做着努力。大部分 辽宁师范人学硕士学位论文 模型都是抱着归类的思想来对可能具有相同兴趣的用户进行分类，在从这些用户中发现 相关数据的关系，当有新用户加入，可以通过模型来判断此用户应属的类，将同类的内 容进行推荐。 数据挖掘在国内本身起步较晚，1 9 9 3 年国家自然科学基金首次支持对该领域的研究 项目，目前w e b 个性化服务的发展，使出现了大量的用户兴趣模型的研究。其中，清 华大学、大连理工大学、中科院等科研机构对此相关领域进行了一定的研究。 1 3 现有算法存在的问题 用户兴趣模型的建立的方法有很多，本文提出通过基于最大频繁项目集的事务间关 联规则和整合事务间关联规则与2 阶马尔可夫模型【1 1 1 的两种方法。 在数据预处理、模式挖掘和模式分析三步中，事务间关联规则的方法由于要跨事务， 在多维间对数据进行处理，所以提高数据处理效率是非常重要的。而在事务间关联规则 与2 阶马尔可夫模型中的2 阶马尔可夫算法，在算法效率、用户兴趣预测结果的准确性、 对数据库的处理方面存在如下的问题： 1 、将网页作为中心进行建模。网页为事务，对此网页的每次访问为项目，这样找 到的结果是网页间的联系，并不能作用于用户。 2 、采用最大频繁项目集算法m a f i a 坛】，在找到的最大频繁项目集要想作用于事务间 关联规则【1 3 1 1 1 4 】【1 5 】【1 6 】【1 7 】【1 8 】，要做很多复杂的工作。 3 、2 阶马尔可夫模型预测效率高，结果准确，但是对数据的覆盖度低l l9 1 。使用了 最大频繁项目集的事务间关联规则虽能够生成很多规则，但是准确度有限。 对于上述问题，论文中提出了相应的优化方法来改善现有算法中存在的不足。 1 4 主要工作及论文组织 本论文的主要工作及创新点： l 、网络是为用户服务的，所以提出用户指向的概念，将数据库建立为用户的一次 访问行为为事务，其中每次点击的网页为项目。而不是将网页作为事务，对此网页的每 次访问为项目。 2 、对最大频繁项目集算法m a f i a 进行改进，使之能够存储在找最大频繁项目集后 每个项目从原数据库共同出现过的事务号的交集。 3 、2 阶马尔可夫模型预测效率高，结果准确，但是对数据的覆盖度低，有可能遗漏 可能为用户兴趣的数据，将事务间关联规则与之结合，既能对通过事务间关联规则找到 的结果进行二次筛选，使结果更加准确，又能增加2 阶马尔可夫模型的数据覆盖度，能 够预测到更多更准确的用户兴趣。 一2 一 用户兴趣建模方法研究 论文共分五章，第一章绪论，介绍了论文的研究背景、目前国内外的研究现状和现 有算法存在的问题；第二章介绍了用户兴趣模型的相关知识；第三章基于最大频繁项目 集的事务间关联规则建模方法，介绍了一种新的用户兴趣模型建模方法，给出了新模型 的构建步骤：第四章基于二阶马尔可夫模型与事务间关联规则的用户兴趣预测模型，在 上一种模型建立方法的基础上提出一种新模型，提出双策略用户兴趣库和双策略建模方 法；第五章给出了研究的总结和展望。 ，零： f 辽宁师范大学硕士学位论文 2 关联规则及马尔可夫模型的相关知识 2 1 关联规则的基本概念 2 1 1 关联规则综述 数据关联是数据库中存在的一类重要的可被发现的知识。若两个或多个变量的取值 之间存在某种规律性，就称为关联。关联可分为简单关联、时序关联、因果关联。关联 分析的目的是找出数据库中隐藏的关联网。有时并不知道数据库中数据的关联函数，即 使知道也是不确定的，因此关联分析生成的规则带有可信度。关联规则挖掘发现大量数 据中项集之间有趣的关联或相关联系。a g r a w a l 等于1 9 9 3 年首先提出了挖掘顾客交易数 据库中项集间的关联规则问题，以后诸多的研究人员对关联规则的挖掘问题进行了大量 的研究。他们的工作包括对原有的算法进行优化，如引入随机采样、并行的思想等，以 提高算法挖掘规则的效率，对关联规则的应用进行推广。1 9 9 8 年又提出了事务间关联规 则。关联规则挖掘在数据挖掘中是一个重要的课题，最近几年已被业界所广泛研究。 2 1 2 传统关联规则 传统关联规则即为事务内关联规则( i n t r a - t r a n s a c t i o na s s o c i a t i o nr u l e s ) 其定义为： 假设i ( i t e m s e t s ) 是项的集合。给定一个事务数据库d ( d a t a b a s e ) ，其中每个事务 ( t r a n s a c t i o n ) t 是i 的非空子集，即每一个事务都与一个唯一的标识符t i d ( t r a n s a c t i o ni d ) 对应。关联规则在事务数据库d 中的支持度( s u p p o r t ) 是d 中包含项目x 的百分比，x ， 则有s u p p d ( x ) = 扎s u ，即为概率值；置信度( c o n f i d e n c e ) 是包含项目x 的事务中同 时包含项目y 的百分比，为矽如r i c e ( x ) - - s u p p 7 【爿u 】二缸p 。力似) ，y 1 ，即为条 件概率。则有关联规则为xjy 的蕴涵式，并且xny ，其中x 称为规则的前项( 又 成为关联规则先导l e f t h a n d s i d e ，l h s ) ，y 称为规则的后项( 又成为关联规则的后继 f i g h t h a n d s i d e ，r h s ) 。同时关联规则x y 在事务数据库d 中成立时，具有支持度s 和置信度c ，分别为s u p p o r t ( xjr ) - - p ( xu 】，) 和c o n f i d e n c e ( xj 】，) = e ( x r ) 。如果满 足最小支持度阈值( m i n s u p ) 和最小置信度阈值( m i n c o n f ) ，这样的关联规则是可信的。 这些阈值由用户或者专家设定。 2 1 3 事务间关联规则 在数据挖掘的关联规则里，大部分都是在找寻单个事务里面项目( i t e m ) 之间的笑联 规则，而没有所谓的跨界性。例如：我们发现买面包的人，同时也会买牛奶，但是面包 一4 一 用户兴趣建模方法研究 和牛奶都同属于一笔交易记录。如果我们加上了跨界性的性质，那么我们将会得到以下 例子：买面包的人隔了两天之后还会再来买牛奶，此时的面包和牛奶则分别属于不同的 交易纪录。换句话说，跨界性可以帮我们找到多笔记录中，项目与项目之间的关联规则。 换句话说，我们将这些交易纪录加上了以时间为维度的话，那么这些纪录发生在不 同时间，彼此就有了一个先后的关系。因此，假设项目y 是在项目x 发生的两天之后 跟着发生，那我们将得到的关联规则x ( 0 ) jr ( 2 ) a 有了预测的能力。根据此关联规则， 当下次又有x 发生，则可以推论y 将会有很大的机会，会在两天之后随之发生。这样 的跨越通过事务之间的项目来挖掘关联规则的方法，就成为事务间关联规则。 2 2 关联规则的算法 2 2 1 传统关联规则算法 1 、a p r i o r i 算法 a p r i o r i 是由r a g r a w a l 于1 9 9 3 年提出一种关联规则算法。此算法使用一种逐层搜“，。一， 索的迭代方法，k 项集用于搜索k + l 项集。首先找出频繁l 项集l i ，然后连接l t 产生频 繁2 项集的候选项集c 2 ，扫描数据库验证候选项集频繁性，剪枝，产生频繁项集，如 此循环下去，直至无频繁项集产生。故每找l k 都需扫描数据库一次。所以a p r i o r i 算法茁 主要是通过两个过程组成，即由连接和剪枝组成。a p r i o r i 是一种非常重要算法，对之后 关联规则的研究有着深远的影响，并由此衍生出许多算法。 。，。，一 i ! 2 、d h p 算法 、 d h p 算法利用散列技术有效地改进了候选频繁项集的产生过程，能够生成比前述算 法更小的候选频繁项集，同时减少数据库的大小，缩短了数据库数据通讯的时问，其效 率比a p r i o r i 算法有明显的提高。此算法的缺点是：在第k 次扫描数据库时需要建立关 于( k + 1 ) 项集的散列表，需要额外的时间和空间，实现起来比较困难。 3 、c d 算法1 2 0 1 c d 算法是a p r i o r i 算法在并行环境下的一种应用，它要求计算机p i ( i = l ，2 ，n ) 对数据库进行多次扫描。在第k 次扫描时，若k l ，计算机p i ( i _ l ，2 ，n ) 首先利用第 k 1 次扫描所得到的频繁项集l k i 和a p r i o r i g e n 函数生成候选频繁项集c k ，当k = l 时， 计算机p i 先扫描d b i ( 并行环境下，存储于某台计算机上的数据库) 得出其中的频繁1 项集l l ，再与其它计算机得到的频繁l 项集群进行数据的交换及合并，从而生成候选频 繁1 项集c l ：然后扫描d b i ，计算c k 中的元素在d b i 中的支持数，计算机p i 广播c k 辽宁师范大学硕士学位论文 中元素的支持数，并接收从其它计算机p i ( j i ) 传来的c k 中元素的支持数，并对这些支 持数进行累加，得出c k 中元素的全局支持数。最后计算出频繁k 项集l k ，若l k 中元素 个数为1 ，则算法结束。c d 算法速度较快、易于实现，对各计算机同步次数要求较少， 但是它所需的数据交换较大，而且候选频繁项集较大。 4 、c a p 算法 c a p 算法是一个基于约束的高效的关联规则挖掘算法，它利用约束中两个对发现关 联规则生成算法中剪枝步骤非常重要的属性：反单调性( a n t i m o n o t o n i c i t y ) $ i 简洁性 ( s u c c i n c t n e s s ) ，通过对这两个属性的分析而获得正确的关联规则。 2 2 2 事务间关联规则算法 l 、e h a p f i o f i 算法 每个滑动窗口里面有一个元事务，发现事务间频繁项集的一个方法是通过对a p r i o r i 算法的扩展去挖掘元事务数据库。a p f i o f i 算法假设在扩展项中存在字典序，元事务里的 扩展项将按一定顺序使用。 用a p f i o f i 算法去发现事务间频繁项目集。为更有效地提高算法的效率，使用一个 哈希技术。当事务间侯选l 项集的支持度通过浏览数据库被计算出，关于事务问候选2 项集的信息则被进一步收集到这里，所有可能的2 项集被生成一个哈希表。组成哈希表 的每个桶的数目代表在这个桶里有多少项集。哈希表被用于减少事务候选2 项集的数目， 如果在哈希表里对应的桶值小于m i n s u p ，就撤去一个候选2 项集。我们称这个算法为 e x t e n d e dh a s ha p f i o f i 或e h a p r i o r i 。 2 、f i t i 算法 e h a p n o d 是由a p r i o r i 算法改进的，而f i t i 是为发现频繁事务间项集而专门设计 的一个算法。f i t i 利用下面的性质来提高在发现频繁事务间项集的效率。 性质：令f 是频繁事务问项集，令a ，= e ，il - ，甜，p ，( f ) f ，0 i ( w - 1 ) ，对所有i ， 0 f ( w 1 ) 和a i 必须是一个频繁事务内项集。详见见第三章。f i t i 由3 个步骤组成： 步骤1 ：挖掘和储存频繁事务内项目集。 步骤2 ：转换数据库。 步骤3 ：挖掘频繁事务间项目集。 一6 用户兴趣建模方法研究 2 3 马尔可夫模型的基本概念 2 3 1 马尔可夫模型综述 马尔可夫模型( m a r k o v m o d e l ，m m ) 一种随机过程，在已知它目前的状态( 现在) 的条件下，它未来的演变( 将来) 不依赖于它以往的演变( 过去) 。也就是说，将来的 演变由现在而来。正是因为这样的特性近几年被广泛应用于模式识别和数据挖掘中。 2 4 马尔可夫模型的算法 !一。 、 l 、隐马尔可夫模型( h m m ) 隐马尔可夫模型( h i d d e nm a r k o vm o d e l ，h m m ) 是统计模型，它用来描述一个含 有隐含未知参数的马尔可夫过程。其难点是从可观察的参数中确定该过程的隐含参数。 然后利用这些参数来作进一步的分析。 在正常的马尔可夫模型中，状态对于观察者来说是直接可见的。这样状态的转换概 率便是全部的参数。而在隐马尔可夫模型中，状态并不是直接可见的，但受到状态影响 的某些变量是可见的。每一状态在可能的输出上都有一概率分布。因此状态序列的信息 便能从输出内容的序列中得到。 。臻， 2 、k 阶马尔可夫模型( k t hm a r k o vm o d e l ) 擎； 马尔可夫模型有公式如下： p h = p ( p h + i i w ) = p ( p h + i = pp h ，p h 1 ，p ，p 1 ) 一( 2 1 ) 当w 越大h 越长时，概率v ( v i l w ) 的准确性就越高。但w 和h 的增大，就意味着数 据量的增大，运算效率的降低。为了解决这个问题。引入参数k 来进行数据量的控制， 即只要使用k 个网页来进行预测就能得到合适的结果。加入了参数k 之后，上述公式变 为： p h + l2p ( p h + l = p ip h ，p h 1 ，p h ( h k ) ) ( 2 2 ) k 控制着样本网页的数量，k 同样代表了马尔可夫模型的阶数。在引入了k 之后， 马尔可夫模型成为k 阶马尔可夫模型。 3 、频度过滤马尔可夫模型( f r e q u e n c yp r u n e dm a r k o vm o d e l ) 一7 一 辽宁师范大学硕士学位论文 在k 值大于1 的马尔可夫模型中，数据库中每个项目出现的频率如果小于最小置信 度，则项目对预测结果的准确性没有影响。为了减少运算量，降低数据冗余，将该项目 从数据库中过滤。采用此方法处理数据的马尔可夫模型为频度过滤马尔可夫模型。 2 5 本章小结 本章对用户兴趣模型建模中的主要技术进行了概述，论述了关联规则和马尔可夫模 型的相关算法。本章研究和论述的内容是本论文研究的基础和铺垫。 下面的第三章和第四章，提出两种新的建模方法，并针对现存使用关联规则及马尔可夫 模型的建模方法进行改进。 用户兴趣建模方法研究 3一种基于最大频繁项目集的事务间关联规则挖掘方法 通过发现网页之间的关联关系来预测用户的兴趣是w e b 事务间关联规则挖掘的主 要内容。关联规则概念是由a g r a w a l 等人在1 9 9 3 年率先提出的，并随后提出a p f i o r i 算 法以及相关的改进算法。1 9 9 8 年提出多维跨事务的事务间关联规则，经典算法有源自 a p r i o r i 的e a p f i o r i 和h e a p d o d ，在2 0 0 4 年a n t h o n yk h 提出全新的f i t i 算法。但因 为要在事务间跨维度来分析数据，所以对数据的处理量就非常大，效率有限。 本章系统的提出一种新的事务间关联规则挖掘方法，通过对最大频繁项目集算法 m a f i a 算法改进，得到最大频繁项目集的同时得到对应的共有用户集( c u i ) ，通过对 事务内到事务间最大频繁项目集的转换，分析不同用户之间的关系，分析用户对网站上 不同网页的访问情况，直接发现不同用户之间的关联关系来预测用户的兴趣。该方法经 实验证明能够更加全面的预测用户感兴趣的网页，更好的为用户提供个性化服务。 3 1 相关知识 定义3 1 ( w e b 中事务的描述) 假设某个网站上包含着若干网页的集合为p = p l ，p 2 ， p 3 ，p m ，访问此网站的用户的集合为u = u l ，u 2 ，u 3 ，u n ，每一个p i p 都有一个为了识 别方便而设置的编号，记为t i d ( t r a n s a c t i o ni d ) ，其中网页p i 便可称为一个事务，浏 览此网页的用户为项目，w ( u n ) 是一个权值，当w ( u n ) = l 时，用户u n 访问过网页p i ，而当 w ( u n ) = o 时，用户u n 没有访问p i 时，则有： p i = ( 3 1 ) 定义3 2 ( 滑动窗口) 2 1 1 2 2 】【2 3 】【2 4 】：将所有事务展开，寻找事务间关联规则，对数 据的处理量无疑是巨大且低效的。所以引入了滑动窗口技术来控制每次处理的数据量。 滑动窗口w 在一个事务数据库中是一段连续的区间，区间数为w ( 即子窗口的个数) 。 如图1 ，w 为4 。 本章中所使用的滑动窗口技术是固定窗口大小的滑动窗口，滑动窗口的大小由使用 者根据数据集自行规定。 一9 一 辽宁师范人学硕士学位论文 五d s e ti t e m l b ，e ，g ，j 2 3 4 e ，j 5 6 乞d ，h ， 8 9 a c ，e ，h 1 0 l l 1 2 瓢； 一丁1 i _ _ j 图3 1 滑动窗口定义 f i g 3 1 t h ed e f i n i t i o no fs l i d i n gw i n d o w 定义3 3 ( 共有用户集) ：共有用户集( c u i ) 是一个交集，其内容是某个最大频繁 项目集中各个项目在原数据库中共同出现过的事务的t i d 的集合。 定义3 4 ( 最大频繁项目集) x 是数据库中n 个项目的集合，当x 的支持度不小于 用户给定的m i n s u p ，则称x 为数据库中的频繁项目集。当x 没有其它频繁项目集为超 集时，x 则是一个最大频繁项目集。 性质1 ：频繁项目集的任何真子集都不是最大频繁项目集。 定义3 5 ( 关联规则的支持度) ：关联规则x j y 的支持度定义为项集x uy 的支 持度( s u p p o r t ) ，s u p p o r t ( x ： y ) 表示。s u pp o r t ( x y ) 计算如下： s u p p o r t ( 耻箐 ( 3 2 ) 其中，d 表示数据库。s u p p o r t ( x ) 且p 为x 数量在d 中占的比例。关联规则x y 的 支持度计算方法如下： s u p p o r t ( xjy ) = s u p p o r t ( xwy ) ( 3 3 ) 用户兴趣建模