三支概念格中的關(guān)聯(lián)規(guī)則提取算法

劉美玉,祁建軍,劉偉

(西安電子科技大學計算機科學與技術(shù)學院,710071,西安)

自Agrawal等首次從大型數(shù)據(jù)庫中提取出關(guān)聯(lián)規(guī)則[1]以來,關(guān)聯(lián)規(guī)則的提取已成為數(shù)據(jù)挖掘領(lǐng)域中的重要內(nèi)容。關(guān)聯(lián)規(guī)則可以在大量的數(shù)據(jù)中揭示特征與特征之間的隱含關(guān)系,從而達到數(shù)據(jù)挖掘的目的。

關(guān)聯(lián)規(guī)則表示屬性集之間的相關(guān)性。在形式概念分析(FCA)[2]中,概念表示對象集和屬性集之間的統(tǒng)一,概念格節(jié)點之間的關(guān)系表示概念的泛化和例化。因此,概念格是非常適合關(guān)聯(lián)規(guī)則提取的工具之一。目前,已有一些利用概念格進行關(guān)聯(lián)規(guī)則發(fā)現(xiàn)的方法。Zaki等提出CHARM算法,利用概念格閉項集的特性和對概念格的深度優(yōu)先搜索提取了非冗余的關(guān)聯(lián)規(guī)則[3];Stumme等提出TITANIC算法,通過對概念格進行改造,提高了關(guān)聯(lián)規(guī)則挖掘的效率[4];Kim等設計了一個完整的關(guān)聯(lián)規(guī)則挖掘系統(tǒng)FARM,該系統(tǒng)將關(guān)聯(lián)規(guī)則與植物的生長模型聯(lián)系起來,依據(jù)布爾表達式生成只與用戶興趣相關(guān)的關(guān)聯(lián)規(guī)則,與CHARM算法和TITANIC算法相比,FARM有更優(yōu)的效果[5]。在國內(nèi):謝志鵬等首先發(fā)現(xiàn)了概念格在關(guān)聯(lián)規(guī)則提取上的優(yōu)勢,提出了概念格節(jié)點內(nèi)涵縮減概念,給出了相應的漸進式生成算法和基于概念格的關(guān)聯(lián)規(guī)則提取算法[6-8];Wang等利用領(lǐng)域知識來指導概念格上的關(guān)聯(lián)規(guī)則挖掘[9];王志海等基于概念格的閉項集特性,提出了一種更有利于規(guī)則提取的格結(jié)構(gòu),并給出了閉標記格中的規(guī)則提取算法[10]。從前人的工作中可以總結(jié)出,利用FCA提取規(guī)則的優(yōu)點是只提取最大規(guī)模的頻繁項集,從而縮小了搜索空間,減少不必要的挖掘,從整體上提高了效率。另外,使用閉項集還可以減少規(guī)則的冗余。然而,這些方法主要研究了屬性子集之間的“具有”關(guān)系,即正相關(guān),忽略了屬性子集之間的“不具有”關(guān)系,即負相關(guān)。

Brin等首次提出了負關(guān)聯(lián)的概念,負關(guān)聯(lián)規(guī)則描述了兩個項集之間的反作用,即某個項集的發(fā)生會降低另外某個項集發(fā)生的概率[11]。此后,基于FCA進行負規(guī)則提取的研究也有了進一步發(fā)展。Rodriguez-Jimenez等在建格算法NextClosure的基礎(chǔ)上提取了混合屬性蘊含[12];Missaoui等根據(jù)原形式背景和補背景,提出了一種混合蘊含的提取方法[13]。這些研究僅關(guān)注了項集之間的蘊含,并未提取出完整的負規(guī)則。

為了更完整地表達形式背景中的信息,Qi等結(jié)合三支決策[14]和形式概念分析提出了三支概念分析(3WCA)[15]。三支概念分析是一種進行知識表示與知識發(fā)現(xiàn)的理論,可以同時表達“共同具有”和“共同不具有”兩種語義,相較于形式概念分析,三支概念分析蘊含了更加豐富的信息。目前,基于三支概念分析理論的研究有了豐富的成果[16-24]。為了獲取規(guī)則方面的知識,許多學者進行了深入的研究:文獻[20]給出了決策形式背景上基于屬性導出三支協(xié)調(diào)性和對象導出三支協(xié)調(diào)性的規(guī)則提取,并與強協(xié)調(diào)決策形式背景的規(guī)則進行了比較;文獻[23-24]給出了決策形式背景在屬性導出三支概念格下的規(guī)則提取方法,在三支概念框架下提出了負規(guī)則。這些研究都是基于決策形式背景進行的。

本文以形式背景作為原始數(shù)據(jù)信息,基于三支概念分析理論對關(guān)聯(lián)規(guī)則的提取進行研究,提出基于三支概念分析的關(guān)聯(lián)規(guī)則提取算法(3ARM)。該算法從對象導出概念格中概念之間的父子關(guān)系和兄弟關(guān)系出發(fā),同時提取正關(guān)聯(lián)規(guī)則與負關(guān)聯(lián)規(guī)則,獲得更豐富的知識。

1 三支概念分析

三支概念格是三支概念分析的主要內(nèi)容,三支概念格包括對象導出(OE)概念格和屬性導出(AE)概念格。本文主要在OE概念格上進行研究,因此只介紹OE概念格的相關(guān)理論。

定義1[2]形式背景是一個三元組(G,M,I),其中:G={x1,x2,…,xn},每一個xi(i≤n)被稱為一個對象;M={a1,a2,…,am},每一個aj(j≤m)被稱為一個屬性。對于x∈G與a∈M,如果對象x擁有屬性a,記為xIa,即(x,a)∈I。

定義2[2]設(G,M,I)為一個形式背景,對于任意的對象子集X?G和屬性子集A?M,一對算子被定義為

*:P(G)→P(M),X*={a∈M|?x∈X,
(x,a)∈I}

*:P(M)→P(G),A*={x∈G|?a∈A,
(x,a)∈I}

式中P(·)表示冪集。該算子定義為正算子。

定義3[2]設(G,M,I)為一個形式背景,X?G,A?M。若二元組(X,A)滿足X*=A且A*=X,則稱(X,A)為(G,M,I)一個形式概念,簡稱概念。X稱為(X,A)的外延,A稱為(X,A)的內(nèi)涵。

定義4[15]設(G,M,I)為一個形式背景,對于任意的對象子集X?G和屬性子集A?M,一對負算子被定義為

式中Ic=(G×M)-I,×為笛卡爾積。

文獻[15]中同時考慮正算子和負算子,從對象子集與屬性子集之間“共同具有”和“共同不具有”兩個角度出發(fā),給出如下三支算子的定義。

定義5[15]設(G,M,I)為一個形式背景,對于任意的對象子集X,Y?G和屬性子集A,B?M,一對對象導出三支算子定義為

式中DP(·)=P(·)×P(·)。該算子簡稱為OE算子。

定義6[15]設(G,M,I)為一個形式背景,如果X<·=(A,B)與(A,B)·>=X同時成立,則稱(X,(A,B))為(G,M,I)的一個對象導出三支概念,簡稱OE概念,X稱為(X,(A,B))的外延,(A,B)稱為(X,(A,B))的內(nèi)涵。

對于(X,(A,B))和(Y,(C,D)),定義偏序關(guān)系為(X,(A,B))≤(Y,(C,D))?X?Y?(A,B)?(C,D)。

用OEL(G,M,I)表示由形式背景(G,M,I)生成的所有OE概念的集合,則OEL(G,M,I)在定義6的偏序關(guān)系“≤”下是一個完備格,稱為(G,M,I)的對象導出三支概念格,簡記為OE概念格。其中,上確界和下確界分別為(X,(A,B))∨(Y,(C,D))=((X∪Y)·><·,(A,B)∩(C,D))和(X,(A,B))∧(Y,(C,D))=(X∩Y,((A,B)∪(C,D))·><·)。

用(X,(A,B))<(Y,(C,D))表示(X,(A,B))≤(Y(C,D))且(X,(A,B))≠(Y,(C,D))。如果(X,(A,B))<(Y,(C,D))成立,且不存在使得(X,(A,B))<(Z,(E,F))<(Y,(C,D))成立的(Z,(E,F)),則稱(X,(A,B))是(Y,(C,D))的子概念,(Y,(C,D))是(X,(A,B))的父概念,記為(X,(A,B))(Y,(C,D))。

例1 表1表示形式背景(G,M,I),表中G={1,2,3,4},M={a,b,c,d,e},○表示對象具有屬性,空表示對象不具有屬性。圖1為(G,M,I)對應的OE概念格OEL(G,M,I),圖中概念外延和內(nèi)涵都以羅列的元素序列來表示相應集合,如123表示{1,2,3}。

表1 形式背景(G,M,I)

圖1 OEL(G,M,I)Fig.1 OEL(G,M,I)

在OEL(G,M,I)中,凡是有邊直接相連的兩個概念就是一對父子概念。同一個父概念的兩個子概念是一對兄弟概念。

2 三支概念格中的關(guān)聯(lián)規(guī)則提取

關(guān)聯(lián)規(guī)則是形如A?B的規(guī)則,其中A和B為項的集合。任意項集X的支持度是包含X的事務在事務集D中所占百分比,記為supp(X)=|X(t)|/|D|,其中X(t)={D中事務t|t包含X}。支持度大于給定的最小支持度的項集稱為頻繁項集。關(guān)聯(lián)規(guī)則A?B的支持度supp(A?B)=supp(A∪B),即包含A∪B的事務在事務集中所占百分比。關(guān)聯(lián)規(guī)則的置信度conf(A?B)=supp(A∪B)/supp(A),即事務集中包含A的事務同時包含B的百分比。

挖掘關(guān)聯(lián)規(guī)則的目標是生成所有支持度大于給定的最小支持度s且置信度大于最小置信度c的關(guān)聯(lián)規(guī)則。一般包括計算所有的頻繁項集、從頻繁項集中生成置信度大于最小置信度的關(guān)聯(lián)規(guī)則兩步。本文依據(jù)這一思想,對三支概念格進行剪枝,選出候選概念,再根據(jù)候選概念間的父子關(guān)系和兄弟關(guān)系提取出符合條件的關(guān)聯(lián)規(guī)則。

在形式概念分析中,形式背景(G,M,I)可以理解成事務數(shù)據(jù)庫,其中G為數(shù)據(jù)庫中事務的集合,M為數(shù)據(jù)庫中所有可能項的集合。對于x∈G與a∈M,xIa則表示a屬于事務x的項集,那么項集之間的關(guān)系在概念格中就得到了充分的體現(xiàn),每個概念就是一個最大頻繁項集。概念(X,A)中,X是全體事務集的子集,A是這些事務共同具有的閉項集。一條關(guān)聯(lián)規(guī)則A?B成立,對應于內(nèi)涵包含A的概念同樣包含B。

定義7設(G,M,I)為一個形式背景,A,B,C,D?M,正規(guī)則A?B的支持度定義為具有A∪B的對象在G中所占的比例,記為

定義8設(G,M,I)為一個形式背景,A,B,C,D?M,正規(guī)則A?B的置信度定義為具有A∪B的對象在具有A的對象中占的比例,記為

(2)如果有(X,(A,B))(Y,(C,D)),則可以得到正規(guī)則C?A-C和負規(guī)則D?(B-D);

(3)如果同時滿足(X,(A,B))(Z,(E,F))且(Y,(C,D))(Z,(E,F)),則可以得到正規(guī)則A?C-A∩C和負規(guī)則B?(B-B∩D)。

根據(jù)這3步,給出基于三支概念分析的正負關(guān)聯(lián)規(guī)則提取算法,即3ARM算法,具體如下。

3ARM算法:從OEL(G,M,I)中提取正負關(guān)聯(lián)規(guī)則

輸入:OEL(G,M,I),s,c

輸出:正規(guī)則集合R+、正規(guī)則對應的支持度集合S+和置信度集合C+,負規(guī)則集合R-、負規(guī)則對應的支持度集合S-和置信度集合C-

1 for (X1,(A1,B1)) in OEL(G,M,I):

2 if |X1|

3 continue

9 for (X2,(A2,B2)) in (X1,(A1,B1)).Parent-concepts:

10 if supp(A2?A1-A2)>sand conf(A2?A1-A2)>cthen

11 putA2?A1-A2intoR+

12 put supp(A2?A1-A2) intoS+

13 put conf(A2?A1-A2) intoC+

18 for (X3,(A3,B3)) in (X2,(A2,B2)).Child-concepts:

19 if (X3,(A3,B3))≠(X1,(A1,B1)) then

20 if supp(A1?A3-A1∩A3)>sand

conf(A1?A3-A1∩A3)>cthen

21 putA1?A3-A1∩A3intoR+

22 put supp(A1?A3-A1∩A3) intoS+

23 put conf(A1?A3-A1∩A3) intoC+

intoS-

intoC-

28 returnR+,S+,C+,R-,S-,C-

步驟1～3:設置循環(huán)體,選擇候選概念(X1,(A1,B1))。

步驟4～8:從概念(X1,(A1,B1))的內(nèi)涵中提取負關(guān)聯(lián)規(guī)則。

步驟9～13:提取(X1,(A1,B1))和父概念之間的正關(guān)聯(lián)規(guī)則,并根據(jù)定義7和8計算正規(guī)則的置信度和支持度。

步驟14～17:提取(X1,(A1,B1))和父概念之間的負關(guān)聯(lián)規(guī)則,并計算負規(guī)則的置信度和支持度。

步驟18～23:設置循環(huán)體,此時(X2,(A2,B2))是(X3,(A3,B3))和(X1,(A1,B1))的公共父概念,提取(X1,(A1,B1))和兄弟概念(X3,(A3,B3))之間的正關(guān)聯(lián)規(guī)則,計算兩個正規(guī)則的置信度和支持度。

步驟24～27:提取(X1,(A1,B1))和兄弟概念(X3,(A3,B3))之間的負關(guān)聯(lián)規(guī)則,并計算兩個負規(guī)則的置信度和支持度。

在第二層循環(huán)結(jié)束時,關(guān)于概念(X1,(A1,B1))生成的規(guī)則提取完畢。另外,從算法中可以分析得出,隨著最小支持度和最小置信度的增大,候選概念的數(shù)量減少,規(guī)則的數(shù)量隨之減少,程序運行的時間也隨之減少,然而對非候選概念的判斷相對增多,使得整體效率略微降低。

例2 根據(jù)3ARM算法,s=c=0.4時,例1中OEL(G,M,I)得到關(guān)聯(lián)規(guī)則如表2所示。

表2 關(guān)聯(lián)規(guī)則及其支持度和置信度

規(guī)則1～5由概念間的父子關(guān)系得到,負規(guī)則6～9由單個概念生成。特別的,前件為空集的規(guī)則,如規(guī)則1、2、4、5,可以根據(jù)實際應用選擇保留或者刪除。例如,在推薦系統(tǒng)中,這些規(guī)則可以用作為新用戶提供推薦的依據(jù),而后件為空集的規(guī)則一般被忽略。

3 實驗及分析

實驗數(shù)據(jù)采用推薦系統(tǒng)中廣泛使用的MovieLens數(shù)據(jù)集。數(shù)據(jù)集組成為:User(userID,age,gender,occupation),Movie(movieID,title,genres,tag),Rating(userID,movieID,rating,timestamp)。其中,Rating含有610個用戶對9 742部電影的100 836個評分。

3.1 正規(guī)則分析

首先,把評分信息轉(zhuǎn)化成形式背景,建立OE概念格和經(jīng)典概念格。OE概念格分析得到的概念數(shù)和父子概念對數(shù)分別為13 583、137 229,經(jīng)典概念格的分別為10 787、87 984?？梢钥闯?在相同的形式背景下,OE概念格中的概念數(shù)和父子概念對數(shù)均大于經(jīng)典概念格中的。

然后,對3ARM算法提取到的關(guān)聯(lián)規(guī)則與其他算法取得的規(guī)則進行數(shù)量上和分布上的分析。3ARM算法得到的關(guān)聯(lián)規(guī)則中正負規(guī)則的分布情況如圖2所示?？梢钥闯?得到的正規(guī)則數(shù)量占全部規(guī)則數(shù)量的25%～42%,負規(guī)則數(shù)量占全部規(guī)則數(shù)量的58%～75%,是正規(guī)則的1.06倍～1.26倍。

圖2 3ARM算法得到的正負規(guī)則分布情況Fig.2 Positive and negative rules distribution from 3ARM

3ARM算法與FARM算法提取出的正規(guī)則數(shù)對比如圖3所示?？梢钥闯?兩種算法得到的正規(guī)則都主要分布在支持度小于30%的范圍內(nèi),且在同一最小支持度閾值下,3ARM算法得出的正規(guī)則數(shù)量比FARM算法得出的規(guī)則數(shù)量多出0.9～1.5倍。綜合分析可知,概念間父子關(guān)系數(shù)的增多是使得3ARM算法得到更多正規(guī)則的主要原因。

圖3 3ARM算法與FARM算法得到的正規(guī)則數(shù)對比Fig.3 Comparision of positive rules between 3ARM and FARM

3.2 負規(guī)則分析

為評估提取到的負規(guī)則的可靠性,對3ARM算法與FISM算法進行對比。FISM算法是Balakrishna等提出的一種基于頻繁項集的負關(guān)聯(lián)規(guī)則提取算法,利用改進的FP-tree生成頻繁項集,再從頻繁項集中生成負規(guī)則[26]。3ARM算法與FISM算法得到的負規(guī)則數(shù)對比如圖4所示?？梢钥闯?支持度為22%～30%時,3ARM算法與FISM算法提取到的負規(guī)則數(shù)量相當;隨支持度減小,3ARM算法提取到的負規(guī)則數(shù)量逐漸少于FISM算法的,且差距逐漸拉大。將兩種算法提取到的規(guī)則進行對比,可以發(fā)現(xiàn)FISM算法提取到的規(guī)則中存在類似于的冗余規(guī)則,而3ARM算法利用三支概念的優(yōu)勢,從最大頻繁閉項集的泛化與例化關(guān)系中提取負規(guī)則,大量減少了冗余規(guī)則的生成。

圖4 3ARM算法與FISM算法得到的負規(guī)則數(shù)對比Fig.4 Comparision of negative rules between 3ARM and FISM

3.3 運行時間分析

對3ARM算法、FARM算法和FISM算法的運行時間進行對比,實驗結(jié)果如圖5所示。需要說明的是,這里的運行時間指的是在概念格上提取關(guān)聯(lián)規(guī)則的時間,不包括構(gòu)建經(jīng)典格和OE概念格的時間,3ARM算法的運行時間是同時提取正規(guī)則和負規(guī)則所需時間。為保證公平性,FISM算法的運行時間也不包含生成FP-tree所需的時間,而實際上,3ARM算法對數(shù)據(jù)庫進行一次掃描就可以建立OE概念格,構(gòu)建FP-tree則需要兩次掃描數(shù)據(jù)庫。

圖5 3ARM、FARM及FISM算法的運行時間對比Fig.5 Comparison of running time of 3ARM,FARM and FISM

從圖5可以看出,3ARM算法的運行時間明顯小于FARM算法和FISM算法的。在同一支持度閾值下,3ARM算法的運行時間比FISM算法減少了44%～63%,比FARM算法減少了27%～62%。與FARM算法相比,3ARM算法省去了布爾表達式的邏輯運算;與FISM算法相比,3ARM算法省去了將頻繁項集兩兩結(jié)合生成負規(guī)則的時間。3ARM算法利用OE概念格的偏序關(guān)系及OE概念閉項集的特性,有規(guī)律地提取關(guān)聯(lián)規(guī)則,提高了算法的效率。

從第3節(jié)實驗可以得出,與FARM算法相比,3ARM算法不僅可以延續(xù)經(jīng)典概念格提取非冗余正規(guī)則的優(yōu)點,還可以提取出有價值的負規(guī)則。與FISM算法對比,3ARM算法可以減少負規(guī)則的冗余。從運行時間上看,3ARM算法減去了復雜的操作,縮短了算法的運行時間。

4 結(jié) 論

在關(guān)聯(lián)規(guī)則的提取方面,現(xiàn)有許多基于概念格進行正規(guī)則提取的研究,取得了較好的效果,并在文本分類[18]、推薦系統(tǒng)[27-28]等領(lǐng)域有充分的應用。為更完整地提取關(guān)聯(lián)規(guī)則,本文提出基于三支概念分析的關(guān)聯(lián)規(guī)則提取算法3ARM,利用三支概念的閉項集特性,從父子關(guān)系和兄弟關(guān)系中提取了具有置信度和支持度的正關(guān)聯(lián)規(guī)則和負關(guān)聯(lián)規(guī)則。經(jīng)過實驗對比和分析,得出結(jié)論如下。

(1)在同一形式背景上,建立的三支概念格比經(jīng)典概念格包含更多的概念和父子關(guān)系,因此3ARM算法能比FARM算法提取到更多的正規(guī)則。

(2)利用三支概念的閉項集特性,能快速得到最大規(guī)模的頻繁項集,減少了冗余規(guī)則的產(chǎn)生;利用3WCA中“共同具有”和“共同不具有”的語義,3ARM算法可以同時提取到正規(guī)則和負規(guī)則。

(3)根據(jù)三支概念間的父子關(guān)系和兄弟關(guān)系,有規(guī)律地進行規(guī)則的提取,減少了不必要的操作,使得3ARM算法的運行時間少于FARM算法和FISM算法的。

未來將研究本文算法應用于推薦系統(tǒng)。