正負關聯規則數據挖掘算法研究

楊井榮，侯向寧

(成都理工大學 工程技術學院，四川 樂山 614007)

0 引 言

在線事務處理(OLTP)[1]是傳統的數據庫應用程序。進行在線交易是它的主要任務，對數據進行查詢處理是它的另一個主要任務。在ONLINE交易中，商業數據庫需要極速增長的數據，以提供決策信息的支持。采礦技術(即在線分析處理(OLAP)的快速發展是從數據庫中獲取信息并使用信息。

目前，國內對數據挖掘的研究主要集中在算法的優化和改進上。該文在總結以往數據的基礎上，從另一個角度研究了關聯規則——負關聯規則，使它們與傳統規則有所差別。正相關的關聯規則加上負相關的關聯規則一起形成正負相關的關聯規則，以達到提高關聯規則數據挖掘效率的目的，也使數據挖掘理論中的關聯規則得以完善。

1 關聯規則的核心技術

關聯規則的核心技術就是通過數據挖掘技術，尋找關聯度、興趣度非常高的一個重要的規則模型，以達到在大量數據中發現項目集之間的有效關聯[2]的目的。在以往的研究中，關聯規則使用頻率最高的數據挖掘經常用于發現在交易數據庫中不同種類、不同項目之間的聯系。

設T={t1,t2,…,tm}是項(term)的m元集合。在這個等式里，設置事務有相關性的數據Data是DataBase事務集的集合元素，在此集合中的每個交易T是一個項的集合，用集合表示為Ti?T。公式里為每一個事務選擇一個候選碼，即一個關鍵字，稱作T_KEY。若X是集合T中項的集合，被命名為項集(termset)，即項集X包含于事務T的充要條件是X?T。

據此，關聯規則的形式可以用離散數學中的蘊涵式表示，P決定Q，其中P?T，Q?T，這里P與Q的交集為空集。

若規則P?Q在事務D中成立，并且存在支持度s(supportort)，充分且必要條件是D中事務包含P∪Q的百分比是s，即:

s=support(P?Q)=P(X∪Y)=|{T|P∪Q?∧T∈D}|/|D|

規則P?Q在事務D中成立，并且具有置信度c(confidence)，則充分且必要條件是D中包含P的事務同時也包含Q的百分比是c，即:

C=confidence(P?Q)=p(P/Q)={T|P∪Q?T∧T∈D}|/|{T|X?T∧T∈D}|

項的集合稱為項集。包含K個項目的項目集稱為K個項目集。例如，{printer，computer}是兩項。物料集的發生頻率是指包括該物料集在內的事務個數，被稱為該物料集的發生頻率，稱為支持計數或計數。當且僅當sup乘以D中的事務總數，項目集的頻率不小于最小支持時，就稱項目集滿足最小支持度。在文獻[3]中，將達到或超過最小支持的項目集，簡稱為頻繁項目集。集合的基數為K的頻繁項目集全稱為K-頻繁項目集，簡記為LK。在文獻[4]中，將同時達到或超過最小支持度(min_SUP)、最小置信度(min_CONF)的關聯規則稱為強規則。

2 關聯規則研究現狀及分類

二十世紀末的關聯規則挖掘形式主要是購物籃分析。二十一世紀擴展了關聯規則研究類型。在文獻[5]中，按照不同的標準，不同的維度，可以把關聯規則分為不同的研究模型。

2.1 按值的類型分類

在文獻[6]中，根據所處理值的數據類型進行分類，把關聯規則分成布爾(Boolean)關聯規則、數量化關聯規則。

2.1.1 布爾關聯規則

布爾關聯規則(Boolean關聯規則)處理的是連續的分類數據，該分類數據關注的是相關項目之間存在的關系。例如:SEX(M，“男性”)->professional(M，“快遞員”)，其中M是代表某人員的變量。

2.1.2 數量化關聯規則

數量化關聯規則處理的是數字類型的數據。在處理之前，首先將數字類型的數據劃分為不同的區間。另外，數量化關聯規則也可以包含類別型變量。例如:SEX(M，“男性”)->Profession(M，“快遞員”)->Age(M，“18～45”),其中M是代表某人員的變量，則數量化的屬性Age是不連續的，即離散數據。

2.2 按照抽象層分類

在文獻[7]中，按照能把數據抽象成的層數分類，把關聯規則分成單層關聯規則、多層關聯規則。

2.2.1 單層關聯規則

單層關聯規則(single-level association rules)，只關心現實生活中數據的一個層次，不關心數據實際上有多個不同的層次，也不討論不同抽象層的元組或字段。例如：購買(M，“毛筆”)決定也采購(A，“墨汁”)，其中M是表示購買者的變量，而毛筆和墨汁在數據中屬于同一概念層。

2.2.2 多層關聯規則

多層關聯規則全面討論了現實生活中數據的多樣性、多層性。這個規則涉及不同抽象數據層的元組或字段。例如：

購買(A，“計算機”)->購買(A，“打印機”)

(1)

購買(A，“聯想計算機”)->購買(A，“Sony打

印機”)

(2)

購買(A，“IBM計算機”)->購買(A，“打印機”)

(3)

其中，計算機和打印機屬于同一抽象層，聯想計算機、Sony打印機同屬于同一抽象層，計算機與聯想計算機相比，處于更高的抽象層，Printer與Sony Printer相比，也處于更高的抽象層。規則(3)展現了一個細節，聯想計算機和較高層次打印機之間的多層關聯規則。在文獻[8]中，重命名這種關聯規則稱為交叉層關聯規則(cross-level association rule)。

2.3 按照所涉及的數據維分類

在文獻[9]中，按照所涉及的數據維度分類，把關聯規則分成關聯規則一維關聯規則、多維關聯規則。

2.3.1 一維關聯規則

一維關聯規則常常稱為維度內關聯規則。關聯規則內的元組或字段僅僅涉及數據的一個維度。此類關聯規則通常都可以通過事務數據庫挖掘出來。例如：

購買(M，“毛筆”)->購買(M，“墨汁”)

(4)

2.3.2 多維關聯規則

在文獻[10]中，多維關聯規則是指元組或字段涉及兩個或多個數據維度的關聯規則。這種關聯規則常常通過關系型數據庫或數據倉庫進行挖掘。多維關聯規則是按照數據維度重復與否進行區分的，按照這個標準，把關聯規則分為維度間關聯規則、混合維度間關聯規則。維度間關聯規則是指在相異數據維度重復出現的關聯規則，參照規則(5)；混合維度關聯規則是指在相同數據維度重復出現的關聯規則，參照規則(6)。

sex(M，“男”)∧profession(M，“互聯網”)?

buys(M，“品牌計算機” )

(5)

sex(M，“男”)∧buys(M，“品牌計算機”)?

buys(M，“品牌打印機”)

(6)

數據庫字段或列可以是分類的或量化的。分類字段(categorical field)也稱標稱字段(nominal field)，是指具有可數并有限的不同的、無序的值的字段。分類字段多維關聯規則挖掘利用先前的算法即可進行相應的處理。數量化字段(quantitative field)是指具有有序的數值類型值的字段。

關系型數據庫可以分類或量化。category字段也稱為nominal字段，是指具有有限數量的不同無序值的關系字段。前一種算法可以用來挖掘分類字段的多維關聯規則。數量字段是指具有有序數值的字段。

3 正負關聯規則數據挖掘算法

二十世紀末的關聯規則數據挖掘(association rule，AR)是P?Q的模式，主要用來挖掘消費者事務數據庫中元組集之間的關聯關系。關聯規則最初是以R.Agrawal為首提出的。二十世紀九十年代提出了一種快速算法，成為P?Q類關聯規則的一個重要補充規則。該文研究了三種形式的關聯規則：P?┑Q,┑P?Q,┑P?┑Q，這三種形式的關聯規則被稱為負AR，即NAR。該文提出了一種簡單有效的利用正關聯規則的相關信息計算負關聯規則支持度和置信度的方法，并給出了能夠同時挖掘正關聯規則、負關聯規則的算法。與現有算法相比，其不同之處在于，該算法不但可以挖掘頻繁項目集中的正、負關聯規則，同時還可以檢測并且刪除沖突規則。有一個非常有效，快速進行挖掘的算法。

(1)負關聯規則的支持度和置信度計算方法[11]。

事務數據庫D中規則P?Q的置信度[12](confidence，C)是指同時包含P和Q的事務數與包含P的事務數之比[13]，記錄為C(P?Q)。負關聯規則[14]包含不存在的項(non-existing-items，如┑P，┑Q)，很難直接計算它們的支持度和置信度[15]。因此，該文給出了以下定理和計算方法。

定理1：設P,Q?T，P∩Q=?，則有：

①S(P)=1-s(┑P);

②S(P∪┑Q)=S(P)-S(P∪Q);

③S(┑P∪Q)=S(Q)-S(P∪Q);

④(┑P∪┑Q)=1-S(P)-S(Q)+S(P∪Q)。

根據定理1，為了能夠用數學理論證明定理，該文利用離散數學的集合論的理論重新表示支持度和置信度，即將項目集的集合運算利用事務集的集合運算進行計算，這樣，定理的證明就可以通過數學理論得以支撐，利用集合論中某些定理和性質，有利于理解定理1。

設Ps表示包含于項集P的事務集[16]，其集合基數|Ps|表示Ps中的事務數；類似地，設Qs表示包含于項集Q的事務集，其集合基數|Qs|表示Qs中的事務數。對于關系型數據庫E，代表數據庫中全體事務的集合，即全集，它的基數|E|是事務的總個數。相應的轉換如下：

①s.count(P∪Q)=|Ps∩Qs|;

②s(P)=s.count(P)/|D|=|Ps|/|D|;

③s(P∪Q)=s.count(P∪Q)/|D|=|Ps∩Qs|/|D|;

④c(P?Q)=s(P∪Q)/s(P)=|Ps∩Qs|/

|Ps|。

推論1：設P,Q,T,P∩Q=?，則有：

①c(P?┑Q)=(s(P)s(P∪Q))/s(P)=

1-c(P?Q);

②c(┑P?Q)=(s(Q)-s(P∪Q))/

(1-s(P));

③c(┑P?┑Q)=(1-s(P)-s(Q)+s(P∪Q))/(1-s(P))=1-c(┑P?Q)。

按照定理1和置信度的定義，很容易證明推論1，這里省略了推論1。推理1用于計算負關聯規則的置信度[17]。

(2)正負關聯規則數據挖掘的算法。

算法中，假設頻繁項集已經求出并且已經保存在集合Collection中。

算法1：挖掘正關聯規則和負關聯規則。

Input:

Collection:頻繁項集;

min_conf:最小支持度;

Output:

正關聯規則和負關聯規則集合AR;

①AR=?;

②∥產生Collection中的正負關聯規則

For any itemsetTin Collection do{

For any itemsetP∪Q=TandP∩Q=? do

{

correlation=s(P∪Q)/(s(P)s(Q))

if correlation>1 then{

∥產生P?Q和┑P?┑Q型的規則

ifc(P?Q)≥min_conf then

AR=AR∪{P?Q};

ifc(┑P?┑Q)≥min_conf then

AR=AR∪{┑P?┑Q};

}

if correlation<1 then{

∥產生P?┑Q和┑P?Q型的規則

ifc(P?┑Q)≥min_conf then

AR=AR∪{P?┑Q};

ifc(┑P?Q)≥min_conf then

AR=AR∪{┑P?Q};

}

}

}

③ returnAR;

據此，為了驗證算法1的有效性，對合成數據進行了實驗。實驗在inteli7、4gram、win10、VS 2010集成開發環境下進行。有400個事務實驗數據，最大項集數為6。設置min_support為0.15，min_conf為0.45，表1列出了兩種算法的實驗結果。

表1 兩種算法關聯規則數對照

從表1可以看出，算法1得到的正相關的關聯規則數明顯少于經典的Apriori算法。這就說明算法1刪除了一些互相矛盾的關聯規則，挖掘出許多負相關的關聯規則，證明算法1是有效的。

4 P-S興趣度在正負關聯規則中的研究

文獻[4]提到的一條規則P?Q只有在符合條件support(P∪Q)-support(P)support(Q)≥mininterest>0下才是有興趣的。那么，對于負關聯規則，support(P∪Q)-support(P)support(Q)可能小于0，因此可以使用它的絕對值作為條件，即規則P?Q僅在滿足條件support(P∪Q)-support(P)support(Q)≥mininterest<0時才感興趣。那么，這四種關聯規則的最低利益之間的關系是什么？

定理2：如果|support(P∪Q)-support(P)support(Q)|≥mininterest,那么:

(1)|support(P∪┑Q)-support(P)support(┑Q)|≥mininterest;

(2)|support(┑P∪Q)-support(┑P)support(Q)|≥mininterest;

(3)|support(┑P∪┑Q)-support(┑P)support(┑Q)|≥mininterest。

從定理2可以看出，只要合理有效地進行最小興趣度的選取，就能夠有效地避免大部分不感興趣的規則。與此同時，也證明了四種關聯規則可以被同一個最小興趣P所約束。

當同時研究正負關聯規則[18-19]后有可能會出現conf(┑A?B)>conf(A?B)>min_conf的矛盾問題，而相關性的應用是解決這一矛盾問題的有效方法。該文對關聯規則的相關性進行了定義，提出兩個集合，集合A和集合B的相關性可以由support(A∪B)/support(A)support(B)表示，要求其中的s(A)≠Q,s(B)≠0。其實只要將P-S興趣度稍加改進就可用于關聯規則的相關性判斷，即當同時研究正、負關聯規則時，可能會出現conf(┑P?Q)>conf(P?Q)>min_conf的情況，應用關聯是解決conf問題的一種有效方法，定義了關聯規則的相關性。該文提出項集P和項集Q的相關性可以用P∪Q/support(P)support(Q)來計算，其中s(P)≠0,s(Q)≠0。實際應用中，可以通過提高P-S興趣度來判斷關聯規則的相關性，即通過correlation(P,Q)=support(P∪Q)-support(P)support(Q)來度量。

correlation(P,Q)可能出現三種情況:

(1)若correlation(P,Q)>0，則P和Q是正相關的，即事件P出現的次數越多，事件B出現的次數也越多;

(2)若correlation(P,Q)=0，則P和Q是相互獨立的，事件Q出現的次數與事件P出現的次數無關;

(3)若correlation(P,Q)<0，則P和Q負相關，事件P出現的次數越多，事件Q出現的次數越少。

定理3：如果correlation(P,Q)>0，那么:

(1)correlation(┑P,Q)<0;

(2)correlation(P, ┑Q)<0;

(3)correlation(┑P，┑Q)>0。

反之亦反之。

定理3說明規則P?Q(或┑P?┑Q)和P?┑Q(或┑P?Q)不會同時作為有效規則，從而有效防止自相矛盾的規則產生。

5 結束語

該文主要研究了負關聯規則理論，并與傳統的正關聯規則(positive association rules)相結合，形成了較為完整的關聯規則理論。對于負關聯規則，它比傳統的關聯規則更有意義。目前，涉及負關聯規則的領域很多，特別是在證券市場分析方面[20-25]。

在正、負關聯規則的應用中，由于條件的限制，該文沒有進行深入實踐，只做了少量的原型研究，而負關聯規則還需要進一步的研究和完善。目前，對關聯規則的研究主要是從算法的角度出發。如何提高算法的時空有效性，使得算法經過處理后可以應用到負關聯規則中，而關聯規則挖掘正是將研究與應用相結合，因此該應用系統的設計非常重要。