北邮郭军web搜索chapter6

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中的每个元素需在交易数据库中进行验证来决定其是否加入FkApriori算法的两大缺点可能产生大量的候选集需要重复扫描数据库Apriori算法例

数据库中的项目列表TID

ListofItemID001

002

003

004

005

006

007

008ABCDEFGABCDGHIEFGHJCDEGIABCDGIFIJEGHIDIminsup=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|XD,support(X)minsup};(2)for(k=2;Fk-1!=;k=k+1){(3) Ck=apriori_gen(Fk-1,minsup);(4) foralltransactionstD{(5) support(C)=support(C)+1,CCk}(6) Fk={C|CCk,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-namecountnode-linkchildren-linkparent-link频繁项头表中的每行至少存储两个域item-namenode-linkFPT例

CreateFPtree()算法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，否则转Step2Step2建立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

数据库中的项目列表TIDListofItemID001

002

003

004

005

006

007

008ABCDEFG: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)(xixj)(xixj)xixj。其物理含义为:若xi出现，则xj出现;若xi不出现，则xj不出现，即xi与xj是同现的规则中的各个项目具有很强的亲密度/共现度，任意一个项目的出现很强地暗示规则中其他项目也会出现可信度度量k-项可信关联规则的可信度定义为规则中任意项目出现时，所有项目同时出现的概率：

重要性质：k-项集的可信度不大于其任意子集的可信度例：事务数据库中的交易有1000项，其中包含项A的交易有20，包含项B的交易有900项，同时包含项AB的交易有15项性质命题1：设可信关联规则x1x2的置信度为D中x1的支持度为sup(x1),x2的支持度为sup(x2)，则有命题2：设传统关联规则x1x2的置信度为C1,

x2x1的置信度为C2，则有用邻接矩阵求2项可信集2项集邻接矩阵A={aij}(i,j=1,…n)被定义为：(1)如果T中有且仅有k个事务包含项目集{vi,vj}(i≠j)则矩阵中的元素aij=k(2)如果T中有且仅有k个事务包含项目vi，则矩阵中的元素aii=k2项集邻接矩阵记为D2可信关联规则vi

vj的置信度=2项可信集邻接矩阵若2项集邻接矩阵D2中非对角线元素aij所对应的可信关联规则的置信度小于minconf，则令aij=0，由此形成2项可信集邻接矩阵，记为Dc2对Dc2中的每一个非零元素aij(i≠j)，若项目vi和vj的支持度均大于1项集的最小支持度阈值minsup，则称aij对应的项目集{vi,vj}为2项可信集计算邻接矩阵

数据库中的项目列表TIDListofItemID001

002

003

004

005

006

007

008ABCDEFGIABCGHICEFGHIJCDEGIABCEGIFIJCEGHIDI2-项集邻接矩阵itemABCDEFGHIJA3331213130B3331213130C3362526361D1123212030E2252525251F1121232132G3362526361H1130213331I3363536382J0010121122通过邻接矩阵求可信2-项集

可信2-项集邻接矩阵

minconf=0.5minsup=0itemABCDEFGHIJA3330003000B3330003000C3360506360D0003000000E0050505050F0000030002G3360506360H0030003300I0060506080J0000020002EBCDIFAGHJ由k项可信集生成(k+1)项可信集EBCDIFAGHJABC

ABG

ACG

BCG

CEG

CEI

CGH

CGI

EGIABCG

CEGIAB

AC

AG

BC

BG

CE

CG

CH

CI

EG

EI

FJ

GH

GIABC

ABG

ACG

BCG

CEG

CEI

CGH

CGI

EGIABCG

CEGICGH

FJEBCDIFAGHJEBCDIFAGHJEBCDIFAGHJEBCDIFAGHJFJABCG

CEGICGH

FJ定理设x1，x2，x3为项目集I中的3个项目，并且任意两项构成的规则的可信度分别为Cx1x2，Cx2x3，Cx1x3，设C2min=min{Cx1x2，Cx2x3，Cx1x3}，则由x1，x2，x3构成的可信关联规则的可信度Cx1x2x3满足：(1)Cx1x2x3C2min(2)Cx1x2x3max{0，1.5C2min-0.5}推论设x1，x2，…，xk，xk+1为项目集I中的k+1个项目，任意k项构成的规则的可信度分别为Cx1x2…xk，…，Cx2x3…xk+1，设其中最小的可信度为Ckmin，则这k+1个项目构成的规则的可信度Cx1x2…xkxk+1满足：(1)Cx1x2…xkxk+1

Ckmin(2)Cx1x2…xkxk+1

max{0,((k+1)Ckmin-1)/k}(3)Cx1x2…xkxk+1

max{0,1-(k+1)(1-C2min)/2}基于极大团挖掘可信关联规则算法特点可以忽略最小支持度的限制采用邻接矩阵产生2-项可信集，进而利用极大团思想产生所有的可信集实验结果表明，相对于相关统计算法及超团挖掘算法等常见算法具有更高的效率和准确性。各种度量都适用于该方法步骤k-项集≠TF结束计算所有1项集，2项集的支持度，存放到邻接矩阵中用邻接矩阵求可信2-项集k=2极大团方法由可信k项集求所有(k+1)-项集,k++基于FPT的超团模式快速挖掘算法h-置信度：设项集P={i1,i2,…,im}(m≥2)，定义其h置信度为min{conf(i1i2,…,im),…,conf(imi1,…,im-1)}，记为hconf(P)其中conf为传统关联规则的置信度超团模式:满足sup(P)≥且hconf(P)≥的含有m(m≥2)个项目的项集P

m被称为超团模式P的长度是最小支持度阈值是最小h置信度阈值当为0时，超团模式变为频繁模式极大超团模式：一个含有m个项目的超团模式HP，若其任意超集都不再是超团模式，则被称为极大超团模式h-置信度设项集P={a1,a2,…,am}(m2)，定义其h-置信度对于含有m(m2)个项目的项集P，若sup(P)且hconf(P)，则称P是超团模式(hypercliquepattern)极大超团模式超团模式是可信关联规则的一种特定形式

基于FPT的超团模式和极大超团模式挖掘算法特点统一了超团模式和极大超团模式的挖掘递归处理，无需存储大量候选项集多种剪枝策略最小支持度剪枝策略、最大支持度剪枝策略、项目自剪枝策略、剩余项目剪枝策略比原有的超团模式和极大超团模式挖掘算法效率高挖掘思路首先将数据库构造为FPT按支持度依次处理每个项目，得到包含该项目的超团模式或极大超团模式构造FP-tree数据库中的项目列表TIDItemListSorted001

002

003

004

005abcdeabcdcefcdeabceceabdcabdcecedceabh-置信度阈值=0.65

最小支持度计数=2

项目支持度计数排序ceabdf543331最小支持度剪枝策略基于FPT挖掘超团模式(含项目d)d的条件模式基：

(b:1，a:1，e:1)(e:1)(b:1，a:1)新的支持度计数

(a:2，b:2，e:2)可与d构成超团模式的项目：

(a:2,b:2)最小支持度剪枝策略项目自剪枝策略d的搜索路径:baeb的搜索路径:aea的搜索路径:ee的搜索路径:c最大支持度剪枝策略CHCP-treeof“d”:递归挖掘，得到超团模式abd:2CHCP-treeof“bd”:基于FPT挖掘极大超团模式局部极大超团模式挖掘超团模式时，每次新产生的超团模式都会包含递归前的超团模式只有当递归终止时，产生的超团模式P才有可能是极大超团模式，定义P为局部极大超团模式例：上例中超团模式：abd:2协同过滤推荐的基本算法协同过滤推荐系统:预测用户A是否喜欢项目x基于用户的推荐(用户间协同)基于项目的推荐系统(项目间协同)推荐系统的基本数据是用户对项目的评分表:假设有m个用户，n个项目，则评分表R就是一个m×n

的矩阵推荐系统的任务就是预测这个稀疏矩阵中的空缺项的值如何计算用户之间或项目之间的相似度是推荐系统的核心问题相似度测度余弦相似度(cosine)相关度(correlation)

修正的余弦相似度(adjustedcosine)：预测获得k个对x打了分的A的最相近者后，A对x的打分可以通过这k个相近者对x的打分的加权平均进行预测，所加的权重就是A与各相近者的相似度计算方法有多种，如面临的挑战精度问题R矩阵具有天然的稀疏性为了保证精度，推荐系统需要尽量利用所有可以利用的信息——存储整个R矩阵可伸缩性问题当R矩阵非常大时，基于存储的方法无法被采用基于模型的(modelbased)方法例如，将用户通过聚类等方法分成若干组，然后对各个组(类)建立描述模型——只利用用户所在组的数据进行计算算法的评价评价协同过滤推荐算法的常用测度是平均绝对误差MAE(MeanAbsoluteError)设{p1,p2,…pN}为用户对项目的实际评分，{q1,q2,…,qN}为通过某推荐算法预测得到的对这些项目的评分，则基于局部偏好的协同过滤推荐算法选出k个类代表对整个用户数据空间中的聚类状况以k个中心点进行描述根据每个用户与各个类代表之间的相似度来确定用户与类之间的所属关系(程度)预测用户A对项目x的评分在A所属的所有类中选择类代表在x上极化分值最大的类利用该类中的用户对x的评分来预测A对x的评分两个特殊的操作评分值的极化利用用户对所有项目评分的平均值将其评分转化为+1、0和-1评分行向量的合并操作将两个以上的极化用户评分向量(R矩阵中的两个及以上行)合并为一个向量可定量地获得被合并的用户对于指定项目偏好的一致程度算法的三个主要环节类代表的选取与计算通过聚类的方法获得类代表向量用户归属类计算一个用户可归属于多个相似度大于阈值的类评分预测在用户A所属的各个类中，选择类代表在给定的项目x上有最高的绝对极化分值的类的前k个近邻预测。k近邻按下式求得:

基于个性化主动学习的协同过滤基本思想：系统对新加入的用户主动提示一些对训练用户模型最有帮助的项目让其进行评价，以便尽快获得其偏好特点应用于以下基于模型的协同过滤系统:对给定用户和项目条件下的各种打分的概率建模，即P(r|u,i)方面模型AM(AspectModel)柔性混合模型FMM(FlexibleMixtureModel)方面模型AM是概率潜语义模型，将用户看作由多方面潜在兴趣构成的“混合体”设用户集合为U，潜在兴趣集合为Z，则任意用户u∈U对任意兴趣组z∈Z都有一个归属的概率同一兴趣组中的用户对项目具有相同的打分模式，即给定潜在类变量z，用户u与项目i是相互独立的，因此有用户的所有个性项构成用户模型FMMAM的一种改造，将模型中的潜在变量分成两个代表具有类似兴趣的用户组的潜在变量zu代表具有类似订购用户的项目组的潜在变量zi最小化熵主动学习一种流行的主动学习方法是请用户对能够最大限度降低用户模型的熵的项目进行打分Bayes选择法最小化熵的方法会导致每个用户趋于只具有一个兴趣方面为了对此进行改进，提出了Bayes选择法以加速当前模型向“真实”模型逼近为目标