正負關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘算法研究

楊井榮，侯向?qū)?/p>

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

0 引 言

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

目前，國內(nèi)對數(shù)據(jù)挖掘的研究主要集中在算法的優(yōu)化和改進上。該文在總結(jié)以往數(shù)據(jù)的基礎(chǔ)上，從另一個角度研究了關(guān)聯(lián)規(guī)則——負關(guān)聯(lián)規(guī)則，使它們與傳統(tǒng)規(guī)則有所差別。正相關(guān)的關(guān)聯(lián)規(guī)則加上負相關(guān)的關(guān)聯(lián)規(guī)則一起形成正負相關(guān)的關(guān)聯(lián)規(guī)則，以達到提高關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘效率的目的，也使數(shù)據(jù)挖掘理論中的關(guān)聯(lián)規(guī)則得以完善。

1 關(guān)聯(lián)規(guī)則的核心技術(shù)

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

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

據(jù)此，關(guān)聯(lián)規(guī)則的形式可以用離散數(shù)學(xué)中的蘊涵式表示，P決定Q，其中P?T，Q?T，這里P與Q的交集為空集。

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

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

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

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

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

2 關(guān)聯(lián)規(guī)則研究現(xiàn)狀及分類

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

2.1 按值的類型分類

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

2.1.1 布爾關(guān)聯(lián)規(guī)則

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

2.1.2 數(shù)量化關(guān)聯(lián)規(guī)則

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

2.2 按照抽象層分類

在文獻[7]中，按照能把數(shù)據(jù)抽象成的層數(shù)分類，把關(guān)聯(lián)規(guī)則分成單層關(guān)聯(lián)規(guī)則、多層關(guān)聯(lián)規(guī)則。

2.2.1 單層關(guān)聯(lián)規(guī)則

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

2.2.2 多層關(guān)聯(lián)規(guī)則

多層關(guān)聯(lián)規(guī)則全面討論了現(xiàn)實生活中數(shù)據(jù)的多樣性、多層性。這個規(guī)則涉及不同抽象數(shù)據(jù)層的元組或字段。例如：

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

(1)

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

印機”)

(2)

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

(3)

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

2.3 按照所涉及的數(shù)據(jù)維分類

在文獻[9]中，按照所涉及的數(shù)據(jù)維度分類，把關(guān)聯(lián)規(guī)則分成關(guān)聯(lián)規(guī)則一維關(guān)聯(lián)規(guī)則、多維關(guān)聯(lián)規(guī)則。

2.3.1 一維關(guān)聯(lián)規(guī)則

一維關(guān)聯(lián)規(guī)則常常稱為維度內(nèi)關(guān)聯(lián)規(guī)則。關(guān)聯(lián)規(guī)則內(nèi)的元組或字段僅僅涉及數(shù)據(jù)的一個維度。此類關(guān)聯(lián)規(guī)則通常都可以通過事務(wù)數(shù)據(jù)庫挖掘出來。例如：

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

(4)

2.3.2 多維關(guān)聯(lián)規(guī)則

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

sex(M，“男”)∧profession(M，“互聯(lián)網(wǎng)”)?

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

(5)

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

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

(6)

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

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

3 正負關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘算法

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

(1)負關(guān)聯(lián)規(guī)則的支持度和置信度計算方法[11]。

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

定理1：設(shè)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)。

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

設(shè)Ps表示包含于項集P的事務(wù)集[16]，其集合基數(shù)|Ps|表示Ps中的事務(wù)數(shù)；類似地，設(shè)Qs表示包含于項集Q的事務(wù)集，其集合基數(shù)|Qs|表示Qs中的事務(wù)數(shù)。對于關(guān)系型數(shù)據(jù)庫E，代表數(shù)據(jù)庫中全體事務(wù)的集合，即全集，它的基數(shù)|E|是事務(wù)的總個數(shù)。相應(yīng)的轉(zhuǎn)換如下：

①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：設(shè)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用于計算負關(guān)聯(lián)規(guī)則的置信度[17]。

(2)正負關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘的算法。

算法中，假設(shè)頻繁項集已經(jīng)求出并且已經(jīng)保存在集合Collection中。

算法1：挖掘正關(guān)聯(lián)規(guī)則和負關(guān)聯(lián)規(guī)則。

Input:

Collection:頻繁項集;

min_conf:最小支持度;

Output:

正關(guān)聯(lián)規(guī)則和負關(guān)聯(lián)規(guī)則集合AR;

①AR=?;

②∥產(chǎn)生Collection中的正負關(guān)聯(lián)規(guī)則

For any itemsetTin Collection do{

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

{

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

if correlation>1 then{

∥產(chǎn)生P?Q和┑P?┑Q型的規(guī)則

ifc(P?Q)≥min_conf then

AR=AR∪{P?Q};

ifc(┑P?┑Q)≥min_conf then

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

}

if correlation<1 then{

∥產(chǎn)生P?┑Q和┑P?Q型的規(guī)則

ifc(P?┑Q)≥min_conf then

AR=AR∪{P?┑Q};

ifc(┑P?Q)≥min_conf then

AR=AR∪{┑P?Q};

}

}

}

③ returnAR;

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

表1 兩種算法關(guān)聯(lián)規(guī)則數(shù)對照

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

4 P-S興趣度在正負關(guān)聯(lián)規(guī)則中的研究

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

定理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可以看出，只要合理有效地進行最小興趣度的選取，就能夠有效地避免大部分不感興趣的規(guī)則。與此同時，也證明了四種關(guān)聯(lián)規(guī)則可以被同一個最小興趣P所約束。

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

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

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

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

(3)若correlation(P,Q)<0，則P和Q負相關(guān)，事件P出現(xiàn)的次數(shù)越多，事件Q出現(xiàn)的次數(shù)越少。

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

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

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

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

反之亦反之。

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

5 結(jié)束語

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

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