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

馮 鋒, 張瓏耀, 張 青

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

近年來(lái), 隨著物聯(lián)網(wǎng)、云計(jì)算、移動(dòng)互聯(lián)網(wǎng)等技術(shù)的廣泛應(yīng)用, 人們正在不知不覺(jué)中構(gòu)建一個(gè)包羅萬(wàn)象的數(shù)據(jù)自然界[1]. 與此同時(shí), 各種紛繁復(fù)雜的大數(shù)據(jù)中所蘊(yùn)含的巨大商業(yè)及社會(huì)價(jià)值受到前所未有的關(guān)注和重視, 使得數(shù)據(jù)挖掘和知識(shí)發(fā)現(xiàn)等領(lǐng)域內(nèi)的前沿研究變得炙手可熱[2]. Agrawal等[3]提出的Apriori算法被認(rèn)為是數(shù)據(jù)挖掘方面最具代表性的成果之一. 該算法將提取關(guān)聯(lián)規(guī)則分為兩步: 首先, 識(shí)別所有的頻繁項(xiàng)集, 即支持不低于預(yù)先設(shè)定的最低支持項(xiàng)集; 其次, 從頻繁項(xiàng)集中構(gòu)造出置信度不低于預(yù)先設(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ù)中自動(dòng)挖掘關(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ī)則的定義中并未涉及項(xiàng)域的劃分, 且在計(jì)算支持時(shí)僅考慮了包含關(guān)系, 這在實(shí)際應(yīng)用中會(huì)影響數(shù)據(jù)挖掘的精準(zhǔn)性, 并降低規(guī)則生成的效率. 為了解決上述問(wèn)題, 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ù)量相對(duì)較少, 有利于提高數(shù)據(jù)挖掘過(guò)程的效率. 一個(gè)極大關(guān)聯(lián)規(guī)則表示: 若前件在交易中恰為其所屬范疇中獨(dú)自出現(xiàn)的項(xiàng)集, 則后件必將以一定的置信度出現(xiàn)在該交易中. 極大關(guān)聯(lián)規(guī)則既不是Agrawal經(jīng)典關(guān)聯(lián)規(guī)則的一種特化, 更不是為了擴(kuò)展或取代常規(guī)關(guān)聯(lián)規(guī)則, 而是常規(guī)關(guān)聯(lián)規(guī)則不可或缺的有益補(bǔ)充.

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

1 軟集與軟集邏輯公式

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

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

定義2[14]設(shè)(F,A)∈SA(U), 且T是參數(shù)集A的一個(gè)劃分, 則稱三元組P =(F,A,T)為U上的一個(gè)參數(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) 當(dāng)且僅當(dāng)有限次應(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中對(duì)應(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ù)中涉及的全體項(xiàng)目集, 稱為項(xiàng)域. 每條交易記錄t都是I的一個(gè)非空子集, 并被賦予唯一的交易標(biāo)識(shí)符TID與之對(duì)應(yīng). 集合D={t1,t2,…,t|D|}包含所有給定的交易, 稱為交易數(shù)據(jù)集. 由I中若干項(xiàng)目構(gòu)成的非空集合X稱為項(xiàng)集, 包含k個(gè)項(xiàng)目的項(xiàng)集稱為k-項(xiàng)集. 如果X?t, 則稱交易t在D內(nèi)支持X.ΔD(X)={t∈D:X?t}稱為項(xiàng)集X在D內(nèi)的實(shí)現(xiàn)集, 其基數(shù)稱為X在D內(nèi)的支持, 記為SD(X).

定義6[3]給定兩個(gè)不相交的項(xiàng)集X,Y?I, 形式表達(dá)式X?Y稱為一個(gè)關(guān)聯(lián)規(guī)則. 項(xiàng)集X,Y分別稱為規(guī)則的前件和后件. 關(guān)聯(lián)規(guī)則X?Y在D內(nèi)的實(shí)現(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ī)則, 需預(yù)先設(shè)定最小支持(minsupp)和最小置信度(minconf). 如果SD(X)≥minsupp, 則稱X為頻繁項(xiàng)集. 此外, 當(dāng)SD(X?Y)≥minsupp且CD(X?Y)≥minconf時(shí), 則稱X?Y是一條強(qiáng)關(guān)聯(lián)規(guī)則. 在交易數(shù)據(jù)庫(kù)的數(shù)據(jù)挖掘和知識(shí)發(fā)現(xiàn)研究中, 如何在預(yù)先設(shè)定好最小支持和最小置信度的前提下, 從交易數(shù)據(jù)集中提取出頻繁項(xiàng)集和強(qiáng)關(guān)聯(lián)規(guī)則是一個(gè)熱點(diǎn)問(wèn)題.

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

定義8[11]設(shè)t∈D是數(shù)據(jù)集中的一條交易記錄,X?CX是一個(gè)項(xiàng)集. 若t∩CX=X, 則稱X在t中是獨(dú)自的, 也稱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|}是項(xiàng)域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誘導(dǎo)的軟集. 此外, 如果T={C1,C2,…,C|T|}是I的分類, 則P =(F,I,T)是D上的參數(shù)類化軟集.

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

進(jìn)而有

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

此外,

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

此外, 對(duì)任意的t∈D, 有

因此,

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

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

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

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

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

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

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

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

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

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

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

4 實(shí)例分析

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

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

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

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

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

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

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

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

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

此外,

進(jìn)一步, 有

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

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

此外,

且

于是,

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

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

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