基于軟集上邏輯公式的極大關(guān)聯(lián)規(guī)則描述與挖掘方法

馮 鋒, 張瓏耀, 張 青

(西安郵電大學 理學院, 西安 710121)

近年來, 隨著物聯(lián)網(wǎng)、云計算、移動互聯(lián)網(wǎng)等技術(shù)的廣泛應(yīng)用, 人們正在不知不覺中構(gòu)建一個包羅萬象的數(shù)據(jù)自然界[1]. 與此同時, 各種紛繁復雜的大數(shù)據(jù)中所蘊含的巨大商業(yè)及社會價值受到前所未有的關(guān)注和重視, 使得數(shù)據(jù)挖掘和知識發(fā)現(xiàn)等領(lǐng)域內(nèi)的前沿研究變得炙手可熱[2]. Agrawal等[3]提出的Apriori算法被認為是數(shù)據(jù)挖掘方面最具代表性的成果之一. 該算法將提取關(guān)聯(lián)規(guī)則分為兩步: 首先, 識別所有的頻繁項集, 即支持不低于預先設(shè)定的最低支持項集; 其次, 從頻繁項集中構(gòu)造出置信度不低于預先設(shè)定最低置信度的有效關(guān)聯(lián)規(guī)則. 常規(guī)關(guān)聯(lián)規(guī)則的挖掘算法主要包括: 1) 經(jīng)典的Apriori算法; 2) 不產(chǎn)生候選集的FP-growth算法[4]; 3) 基于概念格的Eclat算法[5]; 4) CD (count distribution),DD (data distribution) 和CaD (candidate distribution) 為代表的并行算法[6]. 目前, 關(guān)于常規(guī)關(guān)聯(lián)規(guī)則的研究已取得了一些成果. Barati等[7]研究了在RDF數(shù)據(jù)中自動挖掘關(guān)聯(lián)規(guī)則的SWARM算法; Mai等[8]將格理論應(yīng)用于挖掘關(guān)聯(lián)規(guī)則; Song等[9]提出了一種判斷關(guān)聯(lián)規(guī)則置信度的新方法; Kim[10]引入了結(jié)構(gòu)化關(guān)聯(lián)映射圖的概念. 但常規(guī)關(guān)聯(lián)規(guī)則的定義中并未涉及項域的劃分, 且在計算支持時僅考慮了包含關(guān)系, 這在實際應(yīng)用中會影響數(shù)據(jù)挖掘的精準性, 并降低規(guī)則生成的效率. 為了解決上述問題, Amir等[11]引入了一種極大關(guān)聯(lián)規(guī)則. 極大關(guān)聯(lián)規(guī)則可用于搜尋通常關(guān)聯(lián)規(guī)則挖掘中常被忽略的一些特異性內(nèi)在關(guān)聯(lián), 且挖掘出的規(guī)則數(shù)量相對較少, 有利于提高數(shù)據(jù)挖掘過程的效率. 一個極大關(guān)聯(lián)規(guī)則表示: 若前件在交易中恰為其所屬范疇中獨自出現(xiàn)的項集, 則后件必將以一定的置信度出現(xiàn)在該交易中. 極大關(guān)聯(lián)規(guī)則既不是Agrawal經(jīng)典關(guān)聯(lián)規(guī)則的一種特化, 更不是為了擴展或取代常規(guī)關(guān)聯(lián)規(guī)則, 而是常規(guī)關(guān)聯(lián)規(guī)則不可或缺的有益補充.

軟集理論[12]是從參數(shù)化的角度處理不確定性的新構(gòu)架. 軟集定義中既涉及對象論域, 同時也引入了與論域有關(guān)的參數(shù)空間, 相對于模糊集或粗糙集等不確定計算理論, 軟集可進行更靈活多樣的信息描述和數(shù)學處理. 文獻[13]首次從軟集的角度探討了交易數(shù)據(jù)庫中關(guān)聯(lián)規(guī)則和極大關(guān)聯(lián)規(guī)則的挖掘問題; 馮鋒等[14]指出了文獻[13]中一些已有概念存在的缺陷, 并給出了修正方法, 提升了相關(guān)概念的準確性和適用性; 文獻[15]首次引入了軟集上的邏輯公式及其軟真度等概念, 用于研究基于軟集的近似推理理論; 在此基礎(chǔ)上, 文獻[16]基于軟集理論構(gòu)建了一種不確定計算和決策的邏輯框架, 并將其成功應(yīng)用于研究信息系統(tǒng)中的決策規(guī)則提取和屬性分析等問題; 文獻[17]利用軟真度給出了關(guān)聯(lián)規(guī)則的挖掘方法. 本文考慮如何借助軟集邏輯公式給出常規(guī)關(guān)聯(lián)規(guī)則和極大關(guān)聯(lián)規(guī)則的統(tǒng)一數(shù)學刻畫.

1 軟集與軟集邏輯公式

設(shè)U是論域,E是與U內(nèi)對象相關(guān)全體參數(shù)構(gòu)成的集合, 稱為參數(shù)空間. 記U的冪集為P(U), (U,E)稱為軟論域.

定義1[12]二元組P =(F,A)稱為U上的一個軟集, 其中A?E稱為P的參數(shù)集, 集值映射F:A→P(U)稱為P的近似函數(shù).

定義2[14]設(shè)(F,A)∈SA(U), 且T是參數(shù)集A的一個劃分, 則稱三元組P =(F,A,T)為U上的一個參數(shù)類化軟集.

定義3[15]設(shè)P =(F,A)∈SA(U), 構(gòu)造集合F(P )如下:

1)A?F(P );

2) 若φ∈F(P ), 則φ∈F(P );

3) 若φ,ψ∈F(P ), 則(φ∧ψ)∈F(P ), (φ∨ψ)∈F(P );

4) 當且僅當有限次應(yīng)用2)和3)所得的字符串是F(P )中的元素.

F(P )中元素稱為軟集P上的邏輯公式. 特別地, 稱A中的元素為原子公式.

定義4[15]設(shè)P =(F,A)∈SA(U)且X={a1,a2,…,as}?A, 則公式φX?a1∧a2∧…∧as稱為X在P中對應(yīng)的滿合取公式.

定義5[15]設(shè)P =(F,A)∈SA(U), 定義φ∈F(P )的基本軟真度為

2 關(guān)聯(lián)規(guī)則與極大關(guān)聯(lián)規(guī)則

假設(shè)I={i1,i2,…,i|I|}是給定交易數(shù)據(jù)中涉及的全體項目集, 稱為項域. 每條交易記錄t都是I的一個非空子集, 并被賦予唯一的交易標識符TID與之對應(yīng). 集合D={t1,t2,…,t|D|}包含所有給定的交易, 稱為交易數(shù)據(jù)集. 由I中若干項目構(gòu)成的非空集合X稱為項集, 包含k個項目的項集稱為k-項集. 如果X?t, 則稱交易t在D內(nèi)支持X.ΔD(X)={t∈D:X?t}稱為項集X在D內(nèi)的實現(xiàn)集, 其基數(shù)稱為X在D內(nèi)的支持, 記為SD(X).

定義6[3]給定兩個不相交的項集X,Y?I, 形式表達式X?Y稱為一個關(guān)聯(lián)規(guī)則. 項集X,Y分別稱為規(guī)則的前件和后件. 關(guān)聯(lián)規(guī)則X?Y在D內(nèi)的實現(xiàn)集ΔD(X?Y)定義為

ΔD(X?Y)=ΔD(X∪Y).

X?Y在D內(nèi)的支持SD(X?Y)定義為

SD(X?Y)=SD(X∪Y)=card(ΔD(X?Y)).

定義7[3]關(guān)聯(lián)規(guī)則X?Y在D內(nèi)的置信度CD(X?Y)定義為

此外, 若SD(X)=0, 則令CD(X?Y)=0.

為了在交易數(shù)據(jù)集中挖掘有用的關(guān)聯(lián)規(guī)則, 需預先設(shè)定最小支持(minsupp)和最小置信度(minconf). 如果SD(X)≥minsupp, 則稱X為頻繁項集. 此外, 當SD(X?Y)≥minsupp且CD(X?Y)≥minconf時, 則稱X?Y是一條強關(guān)聯(lián)規(guī)則. 在交易數(shù)據(jù)庫的數(shù)據(jù)挖掘和知識發(fā)現(xiàn)研究中, 如何在預先設(shè)定好最小支持和最小置信度的前提下, 從交易數(shù)據(jù)集中提取出頻繁項集和強關(guān)聯(lián)規(guī)則是一個熱點問題.

為了挖掘交易數(shù)據(jù)集中隱藏的極大關(guān)聯(lián)規(guī)則, 需考慮項域I={i1,i2,…,i|I|}的劃分T, 也稱為I的分類, 分類T中的子塊稱為范疇. 由定義知, 對任意的ik∈I,T中包含ik的范疇是唯一的, 記為C(ik). 當項集X取自范疇Ci(即X?Ci∈T)時, 可將Ci記為CX.

定義8[11]設(shè)t∈D是數(shù)據(jù)集中的一條交易記錄,X?CX是一個項集. 若t∩CX=X, 則稱X在t中是獨自的, 也稱t在D內(nèi)M-支持X.

(Y?t)}.

其中

D(X,Y)={t∈D: (t∩CX=X)∧(t∩CY≠?)}.

3 極大關(guān)聯(lián)規(guī)則的軟集邏輯公式描述

設(shè)D={t1,t2,…,t|D|}是項域I={i1,i2,…,i|I|}上的交易數(shù)據(jù)集. 取論域U=D, 參數(shù)集A=I, ?ik∈I, 令F(ik)=ΔD(ik)={t∈D:ik∈t}. 從而可得D上的軟集P =(F,I), 稱為由交易數(shù)據(jù)集D誘導的軟集. 此外, 如果T={C1,C2,…,C|T|}是I的分類, 則P =(F,I,T)是D上的參數(shù)類化軟集.

ΔD(X?Y)=‖φX∧φY‖P.

進而有

SD(X?Y)=|D|·βP(φX∧φY).

此外,

命題1設(shè)X?CX∈T且X≠?, 則

此外, 對任意的t∈D, 有

因此,

命題1表明, 項集X的M-實現(xiàn)集可通過φX∧在軟集P中的實現(xiàn)集計算. 類似地, 可證明如下結(jié)果.

命題2設(shè)X和Y是分別來自兩個不同范疇CX和CY的項集, 則

(Y?t)}=‖φX∧φY∧

命題3設(shè)X和Y是分別來自兩個不同范疇CX和CY的項集, 則

利用上述已證命題, 可得下列結(jié)果:

推論1設(shè)X?CX∈T且X≠?, 則

推論2設(shè)X?CX∈T且X≠?, 則

推論3設(shè)X和Y是分別來自兩個不同范疇CX和CY的項集, 則

推論4設(shè)X和Y是分別來自兩個不同范疇CX和CY的項集, 則

推論5設(shè)X和Y是分別來自兩個不同范疇CX和CY的項集, 則

上述結(jié)果表明, 利用滿合取及其對偶公式, 能方便地描述極大關(guān)聯(lián)規(guī)則挖掘中涉及的全部核心概念.

4 實例分析

設(shè)某醫(yī)院記錄的臨床診斷數(shù)據(jù)集D={t1,t2,…,t200}的項域I={A,B,x,y,z}, 其中:x,y,z表示3種“癥狀”;A,B表示兩種“疾病”. 共計200條數(shù)據(jù)記錄, 結(jié)果列于表1. 為了分析癥狀和疾病之間的內(nèi)在關(guān)聯(lián), 考慮項域I={A,B,x,y,z}的劃分T={C1,C2}, 其中范疇C1={A,B}和C2={x,y,z}分別表示“疾病”和“癥狀”. 由臨床診斷數(shù)據(jù)集D誘導的參數(shù)類化軟集P =(F,I,T)列于表2.

在此基礎(chǔ)上, 利用軟集邏輯公式等概念設(shè)計相關(guān)算法, 并在MATLAB8.5中編程挖掘數(shù)據(jù)集D中的極大關(guān)聯(lián)規(guī)則. 當設(shè)定最小M-支持α=20和最小M-置信度β=75%時, 同時在相同閾值下利用經(jīng)典的Apriori算法挖掘常規(guī)關(guān)聯(lián)規(guī)則進行對照, 部分結(jié)果列于表3.

表1 臨床診斷數(shù)據(jù)集D

表2 數(shù)據(jù)集D誘導的參數(shù)類化軟集

表3 常規(guī)與極大關(guān)聯(lián)規(guī)則的對比

考慮表3中的常規(guī)關(guān)聯(lián)規(guī)則{x,y,z}?A, 令X={x,y,z},Y={A}, 則X對應(yīng)的滿合取公式為φX?x∧y∧z. 進而知規(guī)則{x,y,z}?A對應(yīng)的軟集邏輯公式為

φX∧φY?x∧y∧z∧A.

該常規(guī)關(guān)聯(lián)規(guī)則在D內(nèi)的實現(xiàn)集可利用對應(yīng)公式在軟集P中的實現(xiàn)集‖x∧y∧z∧A‖P計算, 即

ΔD({x,y,z}?A)=‖x∧y∧z∧A‖P={t35,…,t139}.

此外,

進一步, 有

φX1∧φY∧?x∧y∧A∧z.

根據(jù)該公式在軟集P中的實現(xiàn)集‖x∧y∧A∧z‖P可計算出對應(yīng)極大關(guān)聯(lián)規(guī)則在D內(nèi)的實現(xiàn)集, 即

此外,

且

于是,

上述實例說明了如何利用軟集邏輯公式描述挖掘關(guān)聯(lián)規(guī)則時涉及的核心概念.

當設(shè)定最小支持α=20和最小置信度β=75%時, 利用Apriori算法挖掘出41條常規(guī)強關(guān)聯(lián)規(guī)則, 如z?x,x?A, {x,y}?A和{x,y,z}?A等. 分析表明, 雖然規(guī)則z?x的支持為120且置信度為87.6%, 遠高于所設(shè)的閾值, 但該強關(guān)聯(lián)規(guī)則的前件和后件均為癥狀, 在臨床診斷中無實際意義. 此外, 常規(guī)關(guān)聯(lián)規(guī)則x?A和{x,y}?A的支持分別為135和123, 置信度分別為83.3%和98.4%. 雖然這兩條強關(guān)聯(lián)規(guī)則都具有很高的支持和置信度, 但其是由更精準的規(guī)則{x,y,z}?A衍生出來的“副產(chǎn)品”. 實際上, 置信度為100%的規(guī)則{x,y,z}?A真正反映了臨床診斷中的客觀規(guī)律, 而其他“副產(chǎn)品”的大量輸出增加了常規(guī)挖掘的冗余性, 為識別真正有價值的規(guī)則帶來了困難.

綜上可見, 雖然常規(guī)挖掘中獲得的強規(guī)則通常數(shù)量驚人, 但卻包含了大量無意義及冗余規(guī)則, 并有可能忽略一些具有實際意義的重要規(guī)則. 因此, 基于軟集邏輯公式的極大關(guān)聯(lián)規(guī)則挖掘不僅對解決常規(guī)挖掘中的“規(guī)則爆炸”等問題有益, 更是對經(jīng)典關(guān)聯(lián)規(guī)則挖掘方法的補充.