Web搜索

郭軍

北京郵電大學(xué)

第6章信息推薦關(guān)聯(lián)規(guī)則挖掘的基本算法可信關(guān)聯(lián)規(guī)則及其挖掘算法基于FPT的超團模式快速挖掘算法協(xié)同過濾推薦的基本算法基于局部偏好的協(xié)同過濾推薦算法基于個性化主動學(xué)習(xí)的協(xié)同過濾面向排序的協(xié)同過濾引言應(yīng)用舉例在電子商務(wù)系統(tǒng)中，新商品會不斷推出，向一個用戶主動提供哪些商品信息便是一個典型的信息推薦問題InformationRetrieval被檢索的文檔相對穩(wěn)定用戶查詢需求不同InformationFilter信息資源動態(tài)變化用戶需求相對固定InformationRecommendation信息資源動態(tài)變化用戶的需求不確切，只能通過歷史數(shù)據(jù)和相關(guān)數(shù)據(jù)進行挖掘(預(yù)測)信息推薦技術(shù)的種類基于內(nèi)容(contentbased)對用戶和商品的描述信息分別建模通過比較兩類模型之間關(guān)聯(lián)度(相似度)進行推薦基于關(guān)聯(lián)(associationbased)通過歷史上的交易或評價數(shù)據(jù)挖掘用戶之間、商品之間、用戶-商品之間的關(guān)聯(lián)性基于上述關(guān)聯(lián)性預(yù)測用戶對商品的態(tài)度不需要關(guān)于用戶和商品的描述信息通常也不需要領(lǐng)域知識關(guān)聯(lián)規(guī)則挖掘(AssociationRulesMining)和協(xié)同過濾(CollaborativeFiltering)是兩種主要算法關(guān)聯(lián)規(guī)則挖掘數(shù)據(jù)挖掘的一個重要研究方向1993年，IBM的R.Agrawal等人提出在大型商品交易數(shù)據(jù)庫中挖掘商品項(Item)之間的關(guān)聯(lián)規(guī)則的問題，并提出Apriori算法后提出多種改進算法，以減小計算量或內(nèi)存的占用量最初主要應(yīng)用在大型超市的商品關(guān)系的挖掘等方面目前已在信息推薦中得到重要應(yīng)用協(xié)同過濾算法來自信息推薦系統(tǒng)方法：通過他人對某一商品已知的需求來預(yù)測一個用戶對該商品未知的需求基本假設(shè)：歷史上的需求類似，則當(dāng)前的需求也類似算法的核心：通過歷史數(shù)據(jù)找出與被預(yù)測用戶有類似需求的用戶(組)基于用戶(Userbased)的算法基于項目(Itembased)的算法關(guān)聯(lián)規(guī)則挖掘的基本算法基本定義I={i1,i2,…,im}為m個不同項目的集合事務(wù)數(shù)據(jù)庫D={T1,T2,…,Tn}，其中每個交易Ti是I中一組項目的集合關(guān)聯(lián)規(guī)則就是一個形如X→Y的蘊涵式，其中X?I，Y?I，而且X∩Y=支持度和置信度是傳統(tǒng)關(guān)聯(lián)規(guī)則的主要客觀度量如果D中S%的事務(wù)同時包含X和Y，則關(guān)聯(lián)規(guī)則X→Y的支持度為S%，記support(X→Y)=S%若D中包含X的事務(wù)中有C%也包含Y，則關(guān)聯(lián)規(guī)則X→Y的置信度為C%，記confidence(X→Y)=P(Y|X)=C%同時滿足最小支持度閾值和最小置信度閾值的規(guī)則稱為強規(guī)則挖掘關(guān)聯(lián)規(guī)則問題就是產(chǎn)生強規(guī)則的問題Apriori算法關(guān)聯(lián)規(guī)則挖掘可以分解為兩個步驟找出D中滿足minSup的k項集，由這些項集生成關(guān)聯(lián)規(guī)則找出置信度不小于minConf的規(guī)則頻繁項集的向下封閉性頻繁項集的所有非空子集一定是頻繁項集Apriori算法把由頻繁k-1項集的集合Fk-1生成頻繁k項集的集合Fk的過程分為連接和剪枝兩步連接和剪枝連接：將Fk-1中的項集進行連接,產(chǎn)生k項集的集合Ck假設(shè)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是可連接的，進行連接操作，結(jié)果為一個k項集f1[1]f1[2]…f1[k-1]f2[k-1]剪枝：將生成的Ck中的非頻繁項集刪除Ck中的某個候選頻繁k項集不被刪除的條件是：它的所有k-1項子集都在Fk-1中Ck中保留下來的k項集構(gòu)成Fk遞推挖掘方法首先產(chǎn)生頻繁1項集F1，然后是頻繁2項集F2，直到某個r值使得Fr為空，算法停止在第k次循環(huán)中，先產(chǎn)生k項集的集合Ck頻繁項集Fk是Ck的一個子集:Ck中的每個元素需在交易數(shù)據(jù)庫中進行驗證來決定其是否加入FkApriori算法的兩大缺點可能產(chǎn)生大量的候選集需要重復(fù)掃描數(shù)據(jù)庫Apriori算法例

數(shù)據(jù)庫中的項目列表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算法描述輸入:事務(wù)數(shù)據(jù)庫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算法的優(yōu)化剪枝技術(shù)原理項集是頻繁的當(dāng)且僅當(dāng)它的所有子集都是頻繁的如果Ck中某個候選項集有任意一個(k-1)子集不屬于Fk-1，則這個項集就應(yīng)被剪掉散列用于生成頻繁2項集F2劃分把數(shù)據(jù)庫從邏輯上分成幾個互不相交的塊采樣利用數(shù)據(jù)子集進行挖掘，然后在整個數(shù)據(jù)集中驗證基于FPT的算法

韓家煒[Han00]提出利用頻繁模式樹FPT進行頻繁模式挖掘的FP-growth算法1）采用FPT存放數(shù)據(jù)庫的主要信息，算法只需掃描數(shù)據(jù)庫兩次2）不需要產(chǎn)生候選項集，從而減少了產(chǎn)生和測試候選項集所耗費的大量時間3）采用分而治之的方式對數(shù)據(jù)庫進行挖掘，在挖掘過程中，大大減少了搜索空間FPT的樹結(jié)構(gòu)構(gòu)成標(biāo)記為“null”的根節(jié)點(root)項前綴子樹(itemprefixsubtrees)的集合頻繁項頭表(frequent-itemheadertable)項前綴子樹中的每個節(jié)點包含5個域item-namecountnode-linkchildren-linkparent-link頻繁項頭表中的每行至少存儲兩個域item-namenode-linkFPT例

CreateFPtree()算法Step1掃描DB中的每個事務(wù)ti，收集由所有項構(gòu)成的集合F及其支持度Step2根據(jù)最小支持度，獲得F中的頻繁項，并按照支持度降序的順序?qū)⑺鼈兎湃隖PT的項頭表Step3建立FPT的根節(jié)點T，并將其標(biāo)記為“null”Step4對DB中的每個事務(wù)ti，根據(jù)項頭表選擇ti中的頻繁項并對它們進行排序以構(gòu)成ri；如果ri不為空，調(diào)用insert_tree(ri,T)Step5輸出以T為根節(jié)點的FPTinsert_tree()算法輸入：項集{p1,P}，節(jié)點N輸出：無符號：n代表樹中節(jié)點N的子節(jié)點Step1若有N的子節(jié)點n，使得n.item-name=p1.item-name，則n.count=n.count+1，否則轉(zhuǎn)Step2Step2建立N的子節(jié)點n，執(zhí)行n.item-name=p1.item-name;n.parent-link=N;n.count=1;將節(jié)點n加入到項p1.item-name的節(jié)點鏈接node-link中Step3如果P不為空，則繼續(xù)調(diào)用insert_tree(P,n)111FP-Growth例NullGECD6I133minsup=40%minconf=80%GIDC6654I4CD2利用條件FP樹得到頻繁項集：GEGDCIDGI

數(shù)據(jù)庫中的項目列表TIDListofItemID001

002

003

004

005

006

007

008ABCDEFG:GDCEABCDGHI:GIDCEFGHJ:GECDEGI:GlDCEABCDGI:GIDCFIJ:IEGHI:GIEDI:IDE4E1EE1D1111NullGECD6I133GIDC6654I4CD2E4E1EE1D1111NullGECD4111I2CDE1EE111NullGCD411I2CD{E}{E}NullG4{EG}cond.fp-treeofE可信關(guān)聯(lián)規(guī)則及其挖掘算法在數(shù)據(jù)分布嚴(yán)重傾斜的情況下，會遇到最小支持度難以設(shè)定的問題支持度稍一偏高，就會漏掉很多重要的置信度較高的關(guān)聯(lián)規(guī)則支持度稍一偏低，就會產(chǎn)生大量的虛假規(guī)則抑制虛假規(guī)則的產(chǎn)生[Omie03]提出了all-confidence興趣度測度[Xiong03]提出h-confidence興趣度測度可信關(guān)聯(lián)規(guī)則相關(guān)定義設(shè)I={i1,i2,…,im}是m個不同項目的集合

給定事務(wù)數(shù)據(jù)庫D={T1,T2,…,Tn}若存在k個項目x1,…,xk,對于i,j∈{1,…,k}(i≠j)有(xixj)∧(﹁xi﹁xj)則稱由這k個項目構(gòu)成k項可信關(guān)聯(lián)規(guī)則

(CredibleAssociationRule,CAR)，記為R(x1,…,xk)(xixj)(xixj)xixj。其物理含義為:若xi出現(xiàn)，則xj出現(xiàn);若xi不出現(xiàn)，則xj不出現(xiàn)，即xi與xj是同現(xiàn)的規(guī)則中的各個項目具有很強的親密度/共現(xiàn)度，任意一個項目的出現(xiàn)很強地暗示規(guī)則中其他項目也會出現(xiàn)可信度度量k-項可信關(guān)聯(lián)規(guī)則的可信度定義為規(guī)則中任意項目出現(xiàn)時，所有項目同時出現(xiàn)的概率：

重要性質(zhì)：k-項集的可信度不大于其任意子集的可信度例：事務(wù)數(shù)據(jù)庫中的交易有1000項，其中包含項A的交易有20，包含項B的交易有900項，同時包含項AB的交易有15項性質(zhì)命題1：設(shè)可信關(guān)聯(lián)規(guī)則x1x2的置信度為D中x1的支持度為sup(x1),x2的支持度為sup(x2)，則有命題2：設(shè)傳統(tǒng)關(guān)聯(lián)規(guī)則x1x2的置信度為C1,

x2x1的置信度為C2，則有用鄰接矩陣求2項可信集2項集鄰接矩陣A={aij}(i,j=1,…n)被定義為：(1)如果T中有且僅有k個事務(wù)包含項目集{vi,vj}(i≠j)則矩陣中的元素aij=k(2)如果T中有且僅有k個事務(wù)包含項目vi，則矩陣中的元素aii=k2項集鄰接矩陣記為D2可信關(guān)聯(lián)規(guī)則vi

vj的置信度=2項可信集鄰接矩陣若2項集鄰接矩陣D2中非對角線元素aij所對應(yīng)的可信關(guān)聯(lián)規(guī)則的置信度小于minconf，則令aij=0，由此形成2項可信集鄰接矩陣，記為Dc2對Dc2中的每一個非零元素aij(i≠j)，若項目vi和vj的支持度均大于1項集的最小支持度閾值minsup，則稱aij對應(yīng)的項目集{vi,vj}為2項可信集計算鄰接矩陣

數(shù)據(jù)庫中的項目列表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定理設(shè)x1，x2，x3為項目集I中的3個項目，并且任意兩項構(gòu)成的規(guī)則的可信度分別為Cx1x2，Cx2x3，Cx1x3，設(shè)C2min=min{Cx1x2，Cx2x3，Cx1x3}，則由x1，x2，x3構(gòu)成的可信關(guān)聯(lián)規(guī)則的可信度Cx1x2x3滿足：(1)Cx1x2x3C2min(2)Cx1x2x3max{0，1.5C2min-0.5}推論設(shè)x1，x2，…，xk，xk+1為項目集I中的k+1個項目，任意k項構(gòu)成的規(guī)則的可信度分別為Cx1x2…xk，…，Cx2x3…xk+1，設(shè)其中最小的可信度為Ckmin，則這k+1個項目構(gòu)成的規(guī)則的可信度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}基于極大團挖掘可信關(guān)聯(lián)規(guī)則算法特點可以忽略最小支持度的限制采用鄰接矩陣產(chǎn)生2-項可信集，進而利用極大團思想產(chǎn)生所有的可信集實驗結(jié)果表明，相對于相關(guān)統(tǒng)計算法及超團挖掘算法等常見算法具有更高的效率和準(zhǔn)確性。各種度量都適用于該方法步驟k-項集≠TF結(jié)束計算所有1項集，2項集的支持度，存放到鄰接矩陣中用鄰接矩陣求可信2-項集k=2極大團方法由可信k項集求所有(k+1)-項集,k++基于FPT的超團模式快速挖掘算法h-置信度：設(shè)項集P={i1,i2,…,im}(m≥2)，定義其h置信度為min{conf(i1i2,…,im),…,conf(imi1,…,im-1)}，記為hconf(P)其中conf為傳統(tǒng)關(guān)聯(lián)規(guī)則的置信度超團模式:滿足sup(P)≥且hconf(P)≥的含有m(m≥2)個項目的項集P

m被稱為超團模式P的長度是最小支持度閾值是最小h置信度閾值當(dāng)為0時，超團模式變?yōu)轭l繁模式極大超團模式：一個含有m個項目的超團模式HP，若其任意超集都不再是超團模式，則被稱為極大超團模式h-置信度設(shè)項集P={a1,a2,…,am}(m2)，定義其h-置信度對于含有m(m2)個項目的項集P，若sup(P)且hconf(P)，則稱P是超團模式(hypercliquepattern)極大超團模式超團模式是可信關(guān)聯(lián)規(guī)則的一種特定形式

基于FPT的超團模式和極大超團模式挖掘算法特點統(tǒng)一了超團模式和極大超團模式的挖掘遞歸處理，無需存儲大量候選項集多種剪枝策略最小支持度剪枝策略、最大支持度剪枝策略、項目自剪枝策略、剩余項目剪枝策略比原有的超團模式和極大超團模式挖掘算法效率高挖掘思路首先將數(shù)據(jù)庫構(gòu)造為FPT按支持度依次處理每個項目，得到包含該項目的超團模式或極大超團模式構(gòu)造FP-tree數(shù)據(jù)庫中的項目列表TIDItemListSorted001

002

003

004

005abcdeabcdcefcdeabceceabdcabdcecedceabh-置信度閾值=0.65

最小支持度計數(shù)=2

項目支持度計數(shù)排序ceabdf543331最小支持度剪枝策略基于FPT挖掘超團模式(含項目d)d的條件模式基：

(b:1，a:1，e:1)(e:1)(b:1，a:1)新的支持度計數(shù)

(a:2，b:2，e:2)可與d構(gòu)成超團模式的項目：

(a:2,b:2)最小支持度剪枝策略項目自剪枝策略d的搜索路徑:baeb的搜索路徑:aea的搜索路徑:ee的搜索路徑:c最大支持度剪枝策略CHCP-treeof“d”:遞歸挖掘，得到超團模式abd:2CHCP-treeof“bd”:基于FPT挖掘極大超團模式局部極大超團模式挖掘超團模式時，每次新產(chǎn)生的超團模式都會包含遞歸前的超團模式只有當(dāng)遞歸終止時，產(chǎn)生的超團模式P才有可能是極大超團模式，定義P為局部極大超團模式例：上例中超團模式：abd:2協(xié)同過濾推薦的基本算法協(xié)同過濾推薦系統(tǒng):預(yù)測用戶A是否喜歡項目x基于用戶的推薦(用戶間協(xié)同)基于項目的推薦系統(tǒng)(項目間協(xié)同)推薦系統(tǒng)的基本數(shù)據(jù)是用戶對項目的評分表:假設(shè)有m個用戶，n個項目，則評分表R就是一個m×n

的矩陣推薦系統(tǒng)的任務(wù)就是預(yù)測這個稀疏矩陣中的空缺項的值如何計算用戶之間或項目之間的相似度是推薦系統(tǒng)的核心問題相似度測度余弦相似度(cosine)相關(guān)度(correlation)

修正的余弦相似度(adjustedcosine)：預(yù)測獲得k個對x打了分的A的最相近者后，A對x的打分可以通過這k個相近者對x的打分的加權(quán)平均進行預(yù)測，所加的權(quán)重就是A與各相近者的相似度計算方法有多種，如面臨的挑戰(zhàn)精度問題R矩陣具有天然的稀疏性為了保證精度，推薦系統(tǒng)需要盡量利用所有可以利用的信息——存儲整個R矩陣可伸縮性問題當(dāng)R矩陣非常大時，基于存儲的方法無法被采用基于模型的(modelbased)方法例如，將用戶通過聚類等方法分成若干組，然后對各個組(類)建立描述模型——只利用用戶所在組的數(shù)據(jù)進行計算算法的評價評價協(xié)同過濾推薦算法的常用測度是平均絕對誤差MAE(MeanAbsoluteError)設(shè){p1,p2,…pN}為用戶對項目的實際評分，{q1,q2,…,qN}為通過某推薦算法預(yù)測得到的對這些項目的評分，則基于局部偏好的協(xié)同過濾推薦算法選出k個類代表對整個用戶數(shù)據(jù)空間中的聚類狀況以k個中心點進行描述根據(jù)每個用戶與各個類代表之間的相似度來確定用戶與類之間的所屬關(guān)系(程度)預(yù)測用戶A對項目x的評分在A所屬的所有類中選擇類代表在x上極化分值最大的類利用該類中的用戶對x的評分來預(yù)測A對x的評分兩個特殊的操作評分值的極化利用用戶對所有項目評分的平均值將其評分轉(zhuǎn)化為+1、0和-1評分行向量的合并操作將兩個以上的極化用戶評分向量(R矩陣中的兩個及以上行)合并為一個向量可定量地獲得被合并的用戶對于指定項目偏好的一致程度算法的三個主要環(huán)節(jié)類代表的選取與計算通過聚類的方法獲得類代表向量用戶歸屬類計算一個用戶可歸屬于多個相似度大于閾值的類評分預(yù)測在用戶A所屬的各個類中，選擇類代表在給定的項目x上有最高的絕對極化分值的類的前k個近鄰預(yù)測。k近鄰按下式求得:

基于個性化主動學(xué)習(xí)的協(xié)同過濾基本思想：系統(tǒng)對新加入的用戶主動提示一些對訓(xùn)練用戶模型最有幫助的項目讓其進行評價，以便盡快獲得其偏好特點應(yīng)用于以下基于模型的協(xié)同過濾系統(tǒng):對給定用戶和項目條件下的各種打分的概率建模，即P(r|u,i)方面模型AM(AspectModel)柔性混合模型FMM(FlexibleMixtureModel)方面模型AM是概率潛語義模型，將用戶看作由多方面潛在興趣構(gòu)成的“混合體”設(shè)用戶集合為U，潛在興趣集合為Z，則任意用戶u∈U對任意興趣組z∈Z都有一個歸屬的概率同一興趣組中的用戶對項目具有相同的打分模式，即給定潛在類變量z，用戶u與項目i是相互獨立的，因此有用戶的所有個性項構(gòu)成用戶模型FMMAM的一種改造，將模型中的潛在變量分成兩個代表具有類似興趣的用戶組的潛在變量zu代表具有類似訂購用戶的項目組的潛在變量zi最小化熵主動學(xué)習(xí)一種流行的主動學(xué)習(xí)方法是請用戶對能夠最大限度降低用戶模型的熵的項目進行打分Bayes選擇法最小化熵的方法會導(dǎo)致每個用戶趨于只具有一個興趣方面為了對此進行改進，提出了Bayes選擇法以加速當(dāng)前模型向“真實”模型逼近為目標(biāo)