基于極大頻繁項集的粒關(guān)聯(lián)規(guī)則方法

李山山, 張正炳，付青青

(長江大學(xué)電子信息學(xué)院，湖北 荊州 434023)

數(shù)據(jù)挖掘廣泛應(yīng)用于零售、網(wǎng)絡(luò)日志、生物、化工、醫(yī)藥等領(lǐng)域，在日常生活中扮演著越來越重要的角色。粒關(guān)聯(lián)規(guī)則(GR)[1,2]是一種結(jié)合粒計算[3]和粗糙集[4]的相關(guān)知識，通過源覆蓋、目標覆蓋、源置信度和目標置信度來尋找多元關(guān)系數(shù)據(jù)表中隱藏模式的新方法。在恰當設(shè)置4個指標的閾值后，就可以得到一些語義比關(guān)聯(lián)規(guī)則挖掘更加豐富的規(guī)則。粒關(guān)聯(lián)規(guī)則適用于推薦系統(tǒng)[5,6]的冷啟動問題[7],但粒關(guān)聯(lián)規(guī)則挖掘結(jié)果存在冗余等問題。為解決這一問題，筆者利用極大頻繁項集可以緊湊地表示頻繁項集的特點，提出了基于極大頻繁項集的粒關(guān)聯(lián)規(guī)則方法(MGR算法)。

1 基本概念

針對粒關(guān)聯(lián)規(guī)則挖掘所得規(guī)則存在冗余的問題，類比頻繁項集[8]和極大頻繁項集[8]的定義，筆者給出源頻繁粒、目標頻繁粒、源極大頻繁粒和目標極大頻繁粒的定義(見定義1和定義2)，并證明根據(jù)極大頻繁粒集的源覆蓋和目標覆蓋可以表示其子集的源覆蓋和目標覆蓋的范圍(見性質(zhì)1)，為基于極大頻繁項集的粒關(guān)聯(lián)規(guī)則方法(MGR算法)解決上述問題奠定基礎(chǔ)。

引理1[2]假定S=(U,A)為一個信息系統(tǒng)，其中，U=(x1,x2…,xn)表示所有對象集合，A={a1,a2,…,am}表示所有屬性集合，若A′?A，則(A′,x)決定信息系統(tǒng)的一個粒。

引理3[2]若(U,A)和(V,B)為2個信息系統(tǒng)，R?U×V是從U到V的二元關(guān)系，則ES=(U,A,V,B,R)表示一個多對多實體關(guān)系系統(tǒng)。

定義1對于A′?A，B′?B，A′和B′構(gòu)成粒關(guān)聯(lián)規(guī)則GR，給定源覆蓋和目標覆蓋分別為ms，mt，若scov(GR)≥ms,則稱(A′,x)決定的粒為源頻繁粒；同理，若tcov(GR)≥mt，則稱(B′,y)決定的粒為目標頻繁粒。

根據(jù)文獻[1]和定義2，筆者給出MGR的基本形式：

(1)

MGR中源覆蓋、目標覆蓋、源置信度和目標置信度的定義如下：

(2)

(3)

因為源置信度和目標置信度之間存在相互制約的關(guān)系，計算任意一個需要確定另外一個的值[1]。在給定目標置信度tc的條件下，源置信度的定義式為：

(4)

2 MGR算法

筆者將以定義1、定義2、性質(zhì)1和式(1)為基礎(chǔ)，介紹MGR算法。算法包含2個部分，即MaxApriori算法(算法1)和MSandwich算法(算法2)，其中算法1用于挖掘出所有的極大頻繁粒集，該結(jié)果作為算法2的輸入，算法2用于生成規(guī)則。

2.1 算法1

輸入為多對多實體關(guān)系系統(tǒng)[1,2]、源覆蓋和目標覆蓋閾值，輸出為源極大頻繁粒集MSG和目標極大頻繁粒集MTG。算法第1步利用式(2)、式(3)分別獲得的1-頻繁粒集，該步需要掃描數(shù)據(jù)庫一次；第2步利用粒的定義[3]求得1-頻繁粒集的外延，該過程需要掃描數(shù)據(jù)庫一次；第3步針對每個1-頻繁粒集利用Apriori性質(zhì)求得k-頻繁粒集和其對應(yīng)的粒的外延；第4步利用定義2和粒的外延求得k-1-極大頻繁粒集;第5步將k-頻繁粒集添加到極大頻繁粒集。

算法1求出所有的極大頻繁粒集的過程只需要2次掃描數(shù)據(jù)庫。

2.2 算法2

算法2的輸入為算法1輸出結(jié)果MSG和MTG，輸出為一組規(guī)則集。算法2首先分別取出MSG和MTG中對應(yīng)的源極大頻繁粒g和目標極大頻繁粒g′，然后利用二元關(guān)系R得到候補規(guī)則集，最后輸出滿足tconf(MGR)≥tc，sconf(MGR)≥sc的規(guī)則集。

2.3 算法時間復(fù)雜度問題

MGR算法時間復(fù)雜度與GR算法時間復(fù)雜度[2]相似，都可以用公式表述為：

O(|MSG(ms)|×|MTG(mt)|×|U|×|V|)

(5)

3 試驗

試驗數(shù)據(jù)來自MovieLens數(shù)據(jù)集，目前已被廣泛的應(yīng)用于推薦系統(tǒng)。采用的數(shù)據(jù)表為一個含有943個用戶的用戶信息表、一個含有1682部電影的電影信息表和一個用戶對電影的100000條評分記錄表。為避免無用數(shù)據(jù)，這100000條評分記錄中每個用戶至少評價了20部電影?？紤]到挖掘過程中用戶和電影之間的二元關(guān)系，忽略評分記錄表中的5個等級評分對試驗結(jié)果產(chǎn)生的影響，采用“1”和“0”區(qū)分評分和未評分重構(gòu)評分記錄表。由于原始用戶信息表中用戶年齡范圍介于7～73歲，電影信息表中電影上映年份介于1922～1998，為了更好地挖掘規(guī)則，對這2個數(shù)據(jù)表中的數(shù)據(jù)采用離散預(yù)處理。將用戶年齡劃分為6個區(qū)間：[7，22)，[22，27)，[27，31)，[31，39)，[39，48)和[48，73)，并用0～5表示這6個區(qū)間；將電影上映時間劃分為7個區(qū)間[1922，1980)，[1980，1993)，[1993，1994)，[1994，1995)，[1996，1996)，[1996，1997)和[1997，1998)，并用0～6表示這7個區(qū)間。針對電影類型的多值屬性問題，利用多值屬性方法進行處理。

圖1 規(guī)則數(shù)量

圖2 運行時間

3.1 不同閾值下算法的規(guī)則數(shù)量和運行時間

設(shè)置sc=tc=0.2，ms=mt，隨著ms(mt)變化時可以得到不同閾值條件下MGR算法和GR算法的規(guī)則數(shù)量和運行時間，分別對應(yīng)圖1和圖2。

3.2 MGR算法獲得的規(guī)則是否存在損失

造成規(guī)則損失是因為MGR算法是建立在2個論域上的規(guī)則，通過多對多實體關(guān)系系統(tǒng)來實現(xiàn)。在多對多實體關(guān)系系統(tǒng)中，利用MGR算法中的算法1得到的極大頻繁粒集的子集包含了粒關(guān)聯(lián)規(guī)則算法中的全部頻繁粒集，這說明算法1得到極大頻繁粒集的過程是無信息損失的，在算法2建立規(guī)則過程中，存在少量的極大頻繁粒的真子集滿足二元關(guān)系R而生成對應(yīng)的規(guī)則，這個過程在MGR算法中未能體現(xiàn)出來，從而造成少量的規(guī)則損失。

3.3 不同閾值條件下算法的準確率

圖3 不同閾值條件下訓(xùn)練集和測試集的準確率

由于利用MGR算法在得到規(guī)則時存在規(guī)則損失，為評價這個損失對推薦系統(tǒng)造成的影響，下面就冷啟動問題利用MGR算法和GR算法進行推薦，推薦的效果用準確率[1]來衡量。在試驗過程中，對冷啟動問題采用60%的訓(xùn)練集和40%的測試集的劃分比率，為使試驗得到的結(jié)果更加準確，每個閾值下的試驗都進行30次，求得30次試驗的平均值。設(shè)置sc=tc=0.4，ms=mt，隨著ms(mt)變化得到不同閾值下的結(jié)果，如圖3所示。

由圖3可以看出，2種算法在訓(xùn)練集的推薦準確率比測試集推薦準確率高，且在訓(xùn)練集和測試集上MGR算法的推薦準確率比GR算法的準確率高。由此可以看出在利用MGR算法的過程中雖然會造成少量的規(guī)則損失，但在推薦準確率方面卻有所提升。這說明利用MGR算法可以在降低挖掘規(guī)則冗余度的同時提高推薦的準確率。

3.4 不同劃分比例訓(xùn)練集和測試集

圖4 不同劃分比例訓(xùn)練集和測試集的準確率

考慮到訓(xùn)練集和測試集的劃分比例可能對冷啟動問題的推薦準確率造成影響，設(shè)置sc=tc=0.4,ms=mt=0.005，將訓(xùn)練集和測試集的劃分比例從0.3增加到0.8，得到訓(xùn)練集和測試集的推薦準確率如圖4所示。

由圖4可知，隨著訓(xùn)練集劃分比例逐漸增大，訓(xùn)練集和測試集在推薦準確率上基本呈現(xiàn)遞增趨勢，這說明隨著訓(xùn)練集劃分比例增大，有更多已有用戶和電影的評分記錄，從而可以挖掘出更適于用戶的規(guī)則。此外，MGR算法的推薦準確率比GR算法推薦準確率略高，說明MGR算法具有較強的穩(wěn)定性，在不同的劃分比例下推薦準確率依然比GR算法高。

4 結(jié)語