北邮郭军web搜索第六章

Web搜索郭军北京邮电大学第6章信息推荐关联规则挖掘的基本算法可信关联规则及其挖掘算法基于FPT的超团模式快速挖掘算法协同过滤推荐的基本算法基于局部偏好的协同过滤推荐算法基于个性化主动学习的协同过滤面向排序的协同过滤引言应用举例在电子商务系统中，新商品会不断推出，向一个用户主动提供哪些商品信息便是一个典型的信息推荐问题InformationRetrieval•被检索的文档相对稳定•用户查询需求不同InformationFilter•信息资源动态变化•用户需求相对固定InformationRecommendation•信息资源动态变化•用户的需求不确切，只能通过历史数据和相关数据进行挖掘(预测)信息推荐技术的种类基于内容(contentbased)对用户和商品的描述信息分别建模通过比较两类模型之间关联度(相似度)进行推荐基于关联(associationbased)通过历史上的交易或评价数据挖掘用户之间、商品之间、用户-商品之间的关联性基于上述关联性预测用户对商品的态度不需要关于用户和商品的描述信息通常也不需要领域知识关联规则挖掘(AssociationRulesMining)和协同过滤(CollaborativeFiltering)是两种主要算法关联规则挖掘数据挖掘的一个重要研究方向1993年，IBM的R.Agrawal等人提出在大型商品交易数据库中挖掘商品项(Item)之间的关联规则的问题，并提出Apriori算法后提出多种改进算法，以减小计算量或内存的占用量最初主要应用在大型超市的商品关系的挖掘等方面目前已在信息推荐中得到重要应用协同过滤算法来自信息推荐系统方法：通过他人对某一商品已知的需求来预测一个用户对该商品未知的需求基本假设：历史上的需求类似，则当前的需求也类似算法的核心：通过历史数据找出与被预测用户有类似需求的用户(组)基于用户(Userbased)的算法基于项目(Itembased)的算法关联规则挖掘的基本算法基本定义I={i1,i2,…,im}为m个不同项目的集合事务数据库D={T1,T2,…,Tn}，其中每个交易Ti是I中一组项目的集合关联规则就是一个形如X→Y的蕴涵式，其中X⊂I，Y⊂I，而且X∩Y=支持度和置信度是传统关联规则的主要客观度量如果D中S%的事务同时包含X和Y，则关联规则X→Y的支持度为S%，记support(X→Y)=S%若D中包含X的事务中有C%也包含Y，则关联规则X→Y的置信度为C%，记confidence(X→Y)=P(Y|X)=C%同时满足最小支持度阈值和最小置信度阈值的规则称为强规则挖掘关联规则问题就是产生强规则的问题Apriori算法关联规则挖掘可以分解为两个步骤找出D中满足minSup的k项集，由这些项集生成关联规则找出置信度不小于minConf的规则频繁项集的向下封闭性频繁项集的所有非空子集一定是频繁项集Apriori算法把由频繁k-1项集的集合Fk-1生成频繁k项集的集合Fk的过程分为连接和剪枝两步连接和剪枝连接：连接Fk-1中的项集产生k项集的集合Ck假设f1和f2是Fk-1中的项集，记fi[j]为fi的第j项，并令fi[j-1]≤fi[j]如果f1和f2满足：(f1[1]=f2[1])∧…∧(f1[k-2]=f2[k-2])∧(f1[k-1]f2[k-1])那么称f1和f2是可连接的，进行连接操作，结果为一个k项集f1[1]f1[2]…f1[k-1]f2[k-1]剪枝：将生成的Ck中的非频繁项集删除Ck中的某个候选频繁k项集不被删除的条件是：它的所有k-1项子集都在Fk-1中Ck中保留下来的k项集构成Fk递推挖掘方法首先产生频繁1项集F1，然后是频繁2项集F2，直到某个r值使得Fr为空，算法停止在第k次循环中，先产生k项集的集合Ck频繁项集Fk是Ck的一个子集:Ck中的每个元素需在交易数据库中进行验证来决定其是否加入FkApriori算法的两大缺点可能产生大量的候选集需要重复扫描数据库Apriori算法例数据库中的项目列表TIDListofItemID001002003004005006007008ABCDEFGABCDGHIEFGHJCDEGIABCDGIFIJEGHIDIminsup=40%minconf=80%AJIHGFEDCB3345436362JABDFH4243244424CDG:CD→G(4/4)CG→D(4/4)DG→C(4/4)DI:D→I(4/5)I→D(4/6)EG:E→G(4/4)G→E(4/6)GI:G→I(4/6)I→G(4/6)CD→G(50%100%)CG→D(50%100%)DG→C(50%100%)D→I(50%80%)E→G(50%100%)43CECGCIEGEIGICDDEDGDICECGCIEGEIGICDDEDGDICDGDGIDGIApriori算法描述输入:事务数据库D，最小支持度minsup输出:频繁项目集合F符号:X—项目集合；Fi—频繁i-项集集合步骤:(1)F1={X|XD,support(X)minsup};(2)for(k=2;Fk-1!=;k=k+1){(3)Ck=apriori_gen(Fk-1,minsup);(4)foralltransactionstD{(5)support(C)=support(C)+1,CCk}(6)Fk={C|CCk,support(C)minsup};}(7)F=Fk;Apriori算法的优化剪枝技术原理项集是频繁的当且仅当它的所有子集都是频繁的如果Ck中某个候选项集有任意一个(k-1)子集不属于Fk-1，则这个项集就应被剪掉散列用于生成频繁2项集F2划分把数据库从逻辑上分成几个互不相交的块采样利用数据子集进行挖掘，然后在整个数据集中验证基于FPT的算法韩家炜[Han00]提出利用频繁模式树FPT进行频繁模式挖掘的FP-growth算法1）采用FPT存放数据库的主要信息，算法只需扫描数据库两次2）不需要产生候选项集，从而减少了产生和测试候选项集所耗费的大量时间3）采用分而治之的方式对数据库进行挖掘，在挖掘过程中，大大减少了搜索空间FPT的树结构构成标记为“null”的根节点(root)项前缀子树(itemprefixsubtrees)的集合频繁项头表(frequent-itemheadertable)项前缀子树中的每个节点包含5个域item-namecountnode-linkchildren-linkparent-link频繁项头表中的每行至少存储两个域item-namenode-linkFPT例c:6f:5b:4h:4e:3a:7a:7nullh:1b:1f:1c:5f:1c:1e:1b:1e:1d:4d:1d:1f:3h:1b:1d:1e:1b:1d:1frequent-itemheadertableitemandit'ssupportcountheadofnode-linksh:2CreateFPtree()算法Step1扫描DB中的每个事务ti，收集由所有项构成的集合F及其支持度Step2根据最小支持度，获得F中的频繁项，并按照支持度降序的顺序将它们放入FPT的项头表Step3建立FPT的根节点T，并将其标记为“null”Step4对DB中的每个事务ti，根据项头表选择ti中的频繁项并对它们进行排序以构成ri；如果ri不为空，调用insert_tree(ri,T)Step5输出以T为根节点的FPTinsert_tree()算法输入：项集{p1,P}，节点N输出：无符号：n代表树中节点N的子节点Step1若有N的子节点n，使得n.item-name=p1.item-name，则n.count=n.count+1，否则转Step2Step2建立N的子节点n，执行n.item-name=p1.item-name;n.parent-link=N;n.count=1;将节点n加入到项p1.item-name的节点链接node-link中Step3如果P不为空，则继续调用insert_tree(P,n)111FP-Growth例NullGECD6I133minsup=40%minconf=80%GIDC6654I4CD2利用条件FP树得到频繁项集：GEGDCIDGI数据库中的项目列表TIDListofItemID001002003004005006007008ABCDEFG:GDCEABCDGHI:GIDCEFGHJ:GECDEGI:GlDCEABCDGI:GIDCFIJ:IEGHI:GIEDI:IDE4E1EE1D1111NullGECD6I133GIDC6654I4CD2E4E1EE1D1111NullGECD4111I2CDE1EE111NullGCD411I2CD{E}{E}NullG4{EG}cond.fp-treeofE可信关联规则及其挖掘算法在数据分布严重倾斜的情况下，会遇到最小支持度难以设定的问题支持度稍一偏高，就会漏掉很多重要的置信度较高的关联规则支持度稍一偏低，就会产生大量的虚假规则抑制虚假规则的产生[Omie03]提出了all-confidence兴趣度测度[Xiong03]提出h-confidence兴趣度测度可信关联规则相关定义设I={i1,i2,…,im}是m个不同项目的集合给定事务数据库D={T1,T2,…,Tn}若存在k个项目x1,…,xk,对于i,j∈{1,…,k}(i≠j)有(xixj)∧(﹁xi﹁xj)则称由这k个项目构成k项可信关联规则(CredibleAssociationRule,CAR)，记为R(x1,…,xk)(xixj)(xixj)xixj。其物理含义为:若xi出现，则xj出现;若xi不出现，则xj不出现，即xi与xj是同现的规则中的各个项目具有很强的亲密度/共现度，任意一个项目的出现很强地暗示规则中其他项目也会出现可信度度量k-项可信关联规则的可信度定义为规则中任意项目出现时，所有项目同时出现的概率：111iikki=x...xki=xxC=150.0172090015ABABCABAB重要性质：k-项集的可信度不大于其任意子集的可信度例：事务数据库中的交易有1000项，其中包含项A的交易有20，包含项B的交易有900项，同时包含项AB的交易有15项性质12xxC121221()()1(,)()()1xx2xxsupxsupxCanysupxsupxC命题1：设可信关联规则x1x2的置信度为D中x1的支持度为sup(x1),x2的支持度为sup(x2)，则有12121111xxCCC命题2：设传统关联规则x1x2的置信度为C1,x2x1的置信度为C2，则有用邻接矩阵求2项可信集2项集邻接矩阵A={aij}(i,j=1,…n)被定义为：(1)如果T中有且仅有k个事务包含项目集{vi,vj}(i≠j)则矩阵中的元素aij=k(2)如果T中有且仅有k个事务包含项目vi，则矩阵中的元素aii=k2项集邻接矩阵记为D2可信关联规则vivj的置信度ijvvCijiijjijaa+a-a=2项可信集邻接矩阵若2项集邻接矩阵D2中非对角线元素aij所对应的可信关联规则的置信度小于minconf，则令aij=0，由此形成2项可信集邻接矩阵，记为Dc2对Dc2中的每一个非零元素aij(i≠j)，若项目vi和vj的支持度均大于1项集的最小支持度阈值minsup，则称aij对应的项目集{vi,vj}为2项可信集计算邻接矩阵数据库中的项目列表TIDListofItemID001002003004005006007008ABCDEFGIABCGHICEFGHIJCDEGIABCEGIFIJCEGHIDI2-项集邻接矩