基于極大頻繁項集的粒關聯規則方法

李山山, 張正炳，付青青

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

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

1 基本概念

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

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

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

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

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

(1)

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

(2)

(3)

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

(4)

2 MGR算法

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

2.1 算法1

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

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

2.2 算法2

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

2.3 算法時間復雜度問題

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

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

(5)

3 試驗

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

圖1 規則數量

圖2 運行時間

3.1 不同閾值下算法的規則數量和運行時間

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

3.2 MGR算法獲得的規則是否存在損失

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

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

圖3 不同閾值條件下訓練集和測試集的準確率

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

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

3.4 不同劃分比例訓練集和測試集

圖4 不同劃分比例訓練集和測試集的準確率

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

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

4 結語