趙 龍,楊小兵,吳 強(qiáng),高 宇

(中國(guó)計(jì)量大學(xué) 信息工程學(xué)院,浙江 杭州 310018)

一種基于多值屬性的改進(jìn)Apriori算法

趙 龍,楊小兵,吳 強(qiáng),高 宇

(中國(guó)計(jì)量大學(xué) 信息工程學(xué)院,浙江 杭州 310018)

隨著大量需要被挖掘的數(shù)據(jù)變得越來(lái)越復(fù)雜,多維關(guān)聯(lián)規(guī)則已經(jīng)成為關(guān)聯(lián)規(guī)則挖掘中最實(shí)用的內(nèi)容之一.本文主要介紹了在多維關(guān)聯(lián)規(guī)則挖掘過(guò)程中,針對(duì)同一種屬性數(shù)據(jù)出現(xiàn)重復(fù)連接的情況,由此而提出的一種解決方案.通過(guò)對(duì)多值屬性信息進(jìn)行比較,去除重復(fù)連接的屬性信息,保留有效信息,減少對(duì)數(shù)據(jù)庫(kù)的掃描.由此對(duì)Apriori算法中連接步進(jìn)行改進(jìn),最后通過(guò)布爾型關(guān)聯(lián)規(guī)則挖掘數(shù)據(jù)信息并得到結(jié)果.相較于Apriori算法,改進(jìn)算法能更加快速準(zhǔn)確地發(fā)現(xiàn)知識(shí),縮短挖掘所用的時(shí)間.

多維關(guān)聯(lián)規(guī)則;多值屬性;Apriori算法;布爾型關(guān)聯(lián)規(guī)則

數(shù)據(jù)在當(dāng)今時(shí)代已經(jīng)成為一種重要的資源,面對(duì)龐大復(fù)雜的信息數(shù)據(jù),數(shù)據(jù)挖掘在這種背景下得到了較快的發(fā)展.關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘的重要手段之一.在關(guān)聯(lián)規(guī)則挖掘中,由于數(shù)據(jù)的維度不同,可以將關(guān)聯(lián)規(guī)則分為單維關(guān)聯(lián)規(guī)則和多維關(guān)聯(lián)規(guī)則;根據(jù)數(shù)據(jù)的抽象層次分為單層和多層關(guān)聯(lián)規(guī)則;根據(jù)屬性的類型可以分為布爾型和數(shù)值型關(guān)聯(lián)規(guī)則[1].它們?cè)诿鎸?duì)不同的事務(wù)類型時(shí)采取不同的挖掘方式,交易型數(shù)據(jù)庫(kù)和關(guān)系型數(shù)據(jù)庫(kù)是它們主要處理的事務(wù)數(shù)據(jù)類型.

SRIKANT R和AGRAWAL R[2]在1996年提出了多值屬性關(guān)聯(lián)規(guī)則,KAREl F[3]等人也提出了關(guān)于多值屬性的挖掘算法,這種思想的主要內(nèi)容是將多值屬性關(guān)聯(lián)規(guī)則轉(zhuǎn)化成布爾型關(guān)聯(lián)規(guī)則,然后再通過(guò)Apriori算法進(jìn)行挖掘計(jì)算.但是這種方法也存在著不足之處,會(huì)使事務(wù)數(shù)據(jù)庫(kù)的屬性值不斷增加,數(shù)據(jù)會(huì)變得復(fù)雜,給挖掘過(guò)程帶來(lái)了不少難處.近年來(lái),還有很多關(guān)于多值屬性算法的嘗試,國(guó)內(nèi)和國(guó)外一些研究者嘗試用矩陣的方法來(lái)處理多值屬性的數(shù)據(jù)[4-6],這在一定程度上解決了關(guān)聯(lián)規(guī)則轉(zhuǎn)化帶來(lái)的問(wèn)題;但同時(shí)矩陣在進(jìn)行數(shù)據(jù)存儲(chǔ)和處理也帶來(lái)了其他問(wèn)題,當(dāng)數(shù)據(jù)量很大時(shí),可能無(wú)法處理這些由矩陣存儲(chǔ)的數(shù)據(jù),這會(huì)使計(jì)算變得相當(dāng)復(fù)雜.還有很多使用關(guān)聯(lián)規(guī)則改進(jìn)算法進(jìn)行數(shù)據(jù)挖掘的嘗試[7-9],但是過(guò)程中都出現(xiàn)了不可避免的同種屬性值連接的情況,一方面數(shù)據(jù)復(fù)雜的屬性值影響了算法的效率,另一方面算法的使用中沒(méi)涉及到處理同種屬性值連接的情況,影響了算法的挖掘效率.

針對(duì)以上情況,提出的算法改進(jìn)之處是針對(duì)于多值屬性關(guān)聯(lián)規(guī)則,面對(duì)同屬性值連接時(shí),為了不讓同種屬性值產(chǎn)生重復(fù)連接,通過(guò)提前判斷是否有同種屬性值已經(jīng)出現(xiàn)在挖掘的信息數(shù)據(jù)中,這種做法可以避免由于重復(fù)連接而產(chǎn)生的數(shù)據(jù)信息雜亂問(wèn)題,而且在掃描數(shù)據(jù)庫(kù)時(shí)能夠節(jié)省時(shí)間,相對(duì)于Apriori算法,有更好的挖掘效率.

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

在關(guān)聯(lián)規(guī)則中,每個(gè)不同的謂詞稱為維,規(guī)則中只出現(xiàn)一種謂詞的稱之為單維關(guān)聯(lián)規(guī)則,涉及到兩個(gè)或者多個(gè)謂詞的關(guān)聯(lián)規(guī)則稱為多維關(guān)聯(lián)規(guī)則.許多算法只關(guān)注單維或者布爾型關(guān)聯(lián)規(guī)則挖掘,這種方法只能發(fā)現(xiàn)單個(gè)屬性或?qū)傩灾档挠袩o(wú)信息,例如:

buy(X,"laptop")?buy(X,"printer")

只能記錄是否購(gòu)買,這種算法并不適合現(xiàn)在的數(shù)據(jù)挖掘情況.在實(shí)際挖掘數(shù)據(jù)庫(kù)時(shí),經(jīng)常會(huì)遇到多謂詞表達(dá)的信息,例如：

age(X,"20…29")∧occupation(X,"student")?buy(X,"laptop")

這種表達(dá)方式就能更多的體現(xiàn)信息的豐富程度,更有利于信息的挖掘.

在關(guān)聯(lián)規(guī)則挖掘中還有兩個(gè)非常重要的概念:支持度和置信度.它們是衡量規(guī)則興趣度重要的標(biāo)準(zhǔn),分別反映了規(guī)則的有用性和確定性.如果一條規(guī)則A?B成立,并且具有支持度s和置信度c,在這個(gè)規(guī)則中認(rèn)為有:

support(A?B)=P(A∪B)，

(1)

confidence(A?B)=P(A|B).

(2)

如果規(guī)則A?B的支持度和置信度同時(shí)滿足最小支持度和最小置信度,認(rèn)為A?B這條規(guī)則是一條強(qiáng)規(guī)則.在關(guān)聯(lián)規(guī)則挖掘中,最后發(fā)現(xiàn)的規(guī)則通常是由規(guī)則以及這條規(guī)則的支持度和置信度共同構(gòu)成,進(jìn)而為判斷挖掘的模式是否具有參考價(jià)值提供依據(jù).

針對(duì)如何解決多維關(guān)聯(lián)規(guī)則中復(fù)雜的屬性值問(wèn)題,提出對(duì)多值屬性數(shù)據(jù)進(jìn)行預(yù)處理以及對(duì)算法進(jìn)行改進(jìn)來(lái)實(shí)現(xiàn)高效率的挖掘.

2 多值屬性數(shù)據(jù)及特點(diǎn)分析

實(shí)驗(yàn)時(shí)所采用的多值屬性數(shù)據(jù)樣例，如表1,數(shù)據(jù)來(lái)源于醫(yī)院的醫(yī)療數(shù)據(jù),用于記錄病人和用藥信息.數(shù)據(jù)已經(jīng)進(jìn)行了清洗與整理,在處理之后基礎(chǔ)上,將有用的屬性信息保存下來(lái),得到實(shí)驗(yàn)數(shù)據(jù)樣例.

表1 處理后的多值屬性數(shù)據(jù)樣例

數(shù)據(jù)中包含的屬性有性別、年齡、項(xiàng)目代號(hào)、藥品編號(hào)、劑量和影響,每個(gè)屬性都有若干個(gè)屬性值.其中在影響這一屬性中,測(cè)試內(nèi)容包含病人在用藥前、用藥過(guò)程中、以及用藥后三種狀態(tài)下體內(nèi)某指標(biāo)的指數(shù)高低,使用代號(hào)a表示指數(shù)過(guò)低,b代表正常,c代表過(guò)高.abb就代表病人在使用藥品這個(gè)過(guò)程中,體內(nèi)某指標(biāo)由用藥前指數(shù)過(guò)低,用藥過(guò)程中指數(shù)正常,用藥后也正常.

多值屬性關(guān)聯(lián)規(guī)則的目標(biāo)是挖掘頻繁項(xiàng)集[10].針對(duì)多值屬性數(shù)據(jù),發(fā)現(xiàn)每一條規(guī)則中含有很多個(gè)屬性,但是針對(duì)于每個(gè)屬性都只有一個(gè)值與其屬性相對(duì)應(yīng);對(duì)于一條規(guī)則中如果出現(xiàn)兩個(gè)或者多個(gè)屬性值同時(shí)對(duì)應(yīng)于一個(gè)屬性的情況,這種挖掘出來(lái)的數(shù)據(jù)信息是不合理的.例如在樣例數(shù)據(jù)中,若使用Apriori算法進(jìn)行挖掘,會(huì)出現(xiàn)這樣的候選項(xiàng)集：

age(X,"61…70")∧age(X,"71…80")∧age(X,"80…90")

很顯然這種候選集是不正確的,滿足這種規(guī)則的數(shù)據(jù)是不會(huì)存在的,它對(duì)應(yīng)的支持度在數(shù)據(jù)庫(kù)里面的支持度和置信度為0.就是利用這種多值屬性數(shù)據(jù)的性質(zhì),在挖掘的結(jié)果中,同一種屬性的多個(gè)屬性值只能出現(xiàn)一次,由此對(duì)Apriori算法進(jìn)行改進(jìn).

3 算法改進(jìn)

在主要的算法結(jié)構(gòu)上,使用Apriori算法的結(jié)構(gòu)和層次.通過(guò)使用逐層搜索的迭代方法,從低數(shù)據(jù)項(xiàng)集一直找到高數(shù)據(jù)項(xiàng)集.這個(gè)算法的過(guò)程是首先掃描數(shù)據(jù)庫(kù),計(jì)算出每個(gè)數(shù)據(jù)項(xiàng)的數(shù)量,將滿足不小于最小支持度的數(shù)據(jù)項(xiàng)定為頻繁1項(xiàng)集L1,然后通過(guò)使用連接步,找到頻繁2項(xiàng)集L2,繼續(xù)下去可以找到L3,…Lk,直到結(jié)束為止.

輸入:

D:事務(wù)數(shù)據(jù)庫(kù)

min_sup:最小支持度閾值

輸出:

L,D中的頻繁項(xiàng)集

1)L1=find_frquent_1-itemsets(D)

2)for(k=2;Lk-1≠?;k++){

3)Ck=Apriori_gen(Lk-1)

4)for each transactiont∈D{ //掃描數(shù)據(jù)庫(kù)D進(jìn)行計(jì)數(shù)

5)Ct=subset(Ck,t) //得到t的子集,它們是頻繁項(xiàng)集

6)for each candidatec∈Ct

7)c.count++}

8)Lk={c∈Ck∣c.count≥min_sup}}

9)ReturnL=UkLk

主要內(nèi)容介紹是如何在連接步的過(guò)程中實(shí)現(xiàn)更快更簡(jiǎn)潔的發(fā)現(xiàn)知識(shí).通過(guò)分析所要挖掘數(shù)據(jù)的信息和數(shù)據(jù)的結(jié)構(gòu),選擇合適的挖掘方案和步驟.不難發(fā)現(xiàn)所要挖掘的數(shù)據(jù)量龐大而且繁雜,數(shù)據(jù)的屬性有性別、年齡、項(xiàng)目編號(hào)、藥品編號(hào)、劑量和影響,而且對(duì)于每個(gè)屬性內(nèi)部,都有各自不同的屬性值,這在挖掘時(shí)候難免會(huì)變得繁雜.為了避免這種情況的發(fā)生,通過(guò)使用編碼的方式對(duì)每個(gè)屬性和屬性值都進(jìn)行編碼,使用一系列的編碼來(lái)表達(dá)每條數(shù)據(jù)所隱藏的信息,這樣既方便了屬性值復(fù)雜的表達(dá),而且在使用過(guò)程中能和算法進(jìn)行結(jié)合.通過(guò)布爾型關(guān)聯(lián)規(guī)則挖掘算法進(jìn)行實(shí)驗(yàn),這就使復(fù)雜的數(shù)據(jù)挖掘得到了較好的解決.

不同于其他的布爾型關(guān)聯(lián)規(guī)則,在探討挖掘過(guò)程中出現(xiàn)的問(wèn)題時(shí),由于數(shù)據(jù)中有很多的屬性,而且每種屬性都有很多的屬性值,在挖掘過(guò)程中,屬性值之間的連接,可能會(huì)出現(xiàn)同一種屬性的不同屬性值進(jìn)行連接,這是不合適的挖掘結(jié)果.如果采取傳統(tǒng)的方法,將挖掘出來(lái)的信息會(huì)與原有的數(shù)據(jù)庫(kù)內(nèi)容進(jìn)行掃描和驗(yàn)證對(duì)比,對(duì)于出現(xiàn)同種屬性的不同屬性值的挖掘信息就會(huì)舍棄掉,但是這種方法無(wú)疑會(huì)耗費(fèi)巨大的計(jì)算資源,讓挖掘的效率變得比較低.本文探討的是在連接步之后,通過(guò)比較能提前判斷是否有重復(fù)屬性值的連接,這樣能避免重復(fù)連接的同時(shí),也不需要再和數(shù)據(jù)庫(kù)中的數(shù)據(jù)進(jìn)行驗(yàn)證對(duì)比,節(jié)約了計(jì)算資源,有較好的挖掘效率.

在算法上,通過(guò)下面的算法步驟實(shí)現(xiàn)避免出現(xiàn)同種屬性不同屬性值的重復(fù)連接.

Procedure Apriori_gen (Lk-1: frequent(k-1) itemset)

1)for each項(xiàng)集l1∈Lk-1

2)for each項(xiàng)集l2∈Lk-1

3)if(l1[1]=l2[1])&&…&&

(l1[k-2]=l2[k-2])&&(l1[k-1]=l2[k-1])

then{

4)c=l1連接l2

//連接步:產(chǎn)生候選

5)ifl1與l2中有相同的屬性且屬性值不同then

6)deletec

//刪除重復(fù)連接的候選

7)else if has_infrequent_subset(c,Lk-1) then

8)deletec

//刪除非頻繁的候選

9)else addctoCk}

10)returnCk

在算法的過(guò)程中加入了相同屬性值連接的檢測(cè).通過(guò)比較新連接屬性對(duì)應(yīng)的編碼和已經(jīng)存在于頻繁項(xiàng)集中屬性對(duì)應(yīng)的編碼是否有重合,如果重合，說(shuō)明新連接的屬性已經(jīng)存在,將刪除該新連接;若編碼不重合,說(shuō)明該連接可以形成新的候選項(xiàng)集,直到不能發(fā)現(xiàn)新的頻繁項(xiàng)集為止.通過(guò)掃描數(shù)據(jù)之前進(jìn)行提前判斷候選項(xiàng)集是否滿足多值屬性數(shù)據(jù)的性質(zhì),即同一種屬性的多個(gè)屬性值只能出現(xiàn)一次,這樣能夠有效避免出現(xiàn)相同屬性的不同屬性值出現(xiàn)連接,進(jìn)而提高挖掘效率.

4 實(shí)驗(yàn)及分析

實(shí)驗(yàn)是在Core i5-3470 CPU 3.2 GHz,4 G內(nèi)存的硬件環(huán)境下,操作系統(tǒng)為Windows環(huán)境,使用eclipse編程實(shí)現(xiàn).數(shù)據(jù)采用醫(yī)院的醫(yī)療數(shù)據(jù),數(shù)據(jù)已經(jīng)經(jīng)過(guò)預(yù)處理和清洗,作為實(shí)驗(yàn)的原始數(shù)據(jù),開(kāi)始實(shí)驗(yàn)并得到實(shí)驗(yàn)結(jié)果.針對(duì)不同的條件,給出以下兩種情況,一是在相同的支持度情況下,比較挖掘采用數(shù)據(jù)量和挖掘所耗費(fèi)的時(shí)間之間的關(guān)系;二是在相同數(shù)據(jù)量的情況下,比較支持度和挖掘耗費(fèi)時(shí)間之間的關(guān)系.改進(jìn)后算法對(duì)于數(shù)據(jù)量的要求和數(shù)據(jù)內(nèi)容的要求相對(duì)嚴(yán)格,針對(duì)不同量級(jí)的數(shù)據(jù)量,挖掘效率的體現(xiàn)也不一樣.

當(dāng)將支持度設(shè)置為0.2%時(shí),Apriori算法和改進(jìn)Apriori算法的挖掘效果比較,如表2和圖1.

表2 實(shí)驗(yàn)數(shù)據(jù)記錄表

圖1 耗費(fèi)時(shí)間t和數(shù)據(jù)量之間的關(guān)系曲線Figure 1 Curve between time-consuming and the amount of data

針對(duì)不同的數(shù)據(jù)量,改進(jìn)算法效率優(yōu)于原算法.當(dāng)隨著數(shù)據(jù)量的增加,改進(jìn)Apriori算法和Apriori算法的效率差距越來(lái)越大,一方面隨著數(shù)據(jù)的增大,耗用時(shí)間差也增大;另一方面,數(shù)據(jù)量的增大,使得數(shù)據(jù)中的的屬性值數(shù)量增多,出現(xiàn)同屬性值連接的情況就更多,改進(jìn)算法的優(yōu)越性更加明顯.

當(dāng)將數(shù)據(jù)量的值設(shè)置為50 000時(shí),Apriori算法和改進(jìn)Apriori算法的挖掘效果進(jìn)行比較,如表3和如圖2.

表3 實(shí)驗(yàn)數(shù)據(jù)記錄表

圖2 耗費(fèi)時(shí)間和支持度之間的關(guān)系曲線Figure 2 Curve between time-consuming and the support

針對(duì)于不同的支持度,改進(jìn)算法的表現(xiàn)優(yōu)于Apriori算法.隨著支持度的減小,兩種算法的差距也逐漸擴(kuò)大,因?yàn)殡S著支持度減小,產(chǎn)生的候選項(xiàng)集就越多,出現(xiàn)同屬性值連接的情況就會(huì)越多,改進(jìn)算法效果就更明顯.

5 結(jié) 論

本文提出了一種改進(jìn)的Apriori算法,在關(guān)聯(lián)規(guī)則連接步驟中,通過(guò)提前判斷已經(jīng)連接好的頻繁項(xiàng)集中屬性值的屬性,并將即將要連接的屬性值所在屬性與之比較.如果即將連接的屬性值已經(jīng)存在于已經(jīng)連接好的頻繁項(xiàng)集中,則停止當(dāng)前連接,就不再需要將新連接的候選項(xiàng)集與數(shù)據(jù)庫(kù)中的原始數(shù)據(jù)進(jìn)行比較,在屬性值比較繁多的時(shí)候,能有效避免同種屬性值發(fā)生重復(fù)連接,可以有效降低掃描數(shù)據(jù)庫(kù)的次數(shù),進(jìn)而提高挖掘效率.通過(guò)實(shí)驗(yàn)，改進(jìn)的Apriori與傳統(tǒng)的Apriori算法比較后有一定的優(yōu)勢(shì),效率提高了很多.但是同時(shí),改進(jìn)算法依然是基于Apriori算法,掃描數(shù)據(jù)庫(kù)時(shí)依然有很大開(kāi)銷,對(duì)于這方面的改進(jìn)工作,以后會(huì)繼續(xù)進(jìn)行.

[1] AGRAWAL R, IMIELINSKI T, SWAMI A. Mining association rules between sets of items in large databases[J].

ACM Sigmod Record,1993,22(2):207-216.

[2] SRIKAN R, AGRAWAL R. Mining quantitative association rules in large relational table[C]//Proceedings of the ACM Sigmod Conference on Management of Data. San Diego, California: ACM Press,1996:1-12.

[3] KAREL F. Quantitative and ordinal association rules mining (QAR Mining)[C]//10th International Conference on Knowledge-Based Intelligent Information and Engineering Systems, KES 2006. Berlin: Springer Verlag,2006:195-202.

[4] 李國(guó)雁,沈炯夏.一種基于矩陣的多值關(guān)聯(lián)規(guī)則的挖掘算法[J].計(jì)算機(jī)工程與科學(xué),2008,30(5):72-77. LI G Y, SHEN J X. A quantitative association rules mining algorithm based on matrix[J].Computer Engineering & Science,2008,30(5):72-77.

[5] NADERI DEHKORDI M, SHENASSA MH, BADIE K. Multi level exceptions mining in OLAP data cubes[C]//Computer and Communication Engineering 2008. Piscataway: Computer Society,2008:747-751.

[6] KUMAR ASWANI C. Mining association rules using non-negative matrix factorization and formal concept analysis[C]//5th International Conference on Information Processing, ICIP 2011. Berlin: Springer Verlag,2011:31-39.

[7] DIANA M, ALEJANDRO R, JESS A. A new multiobjective evolutionary algorithm for mining a reduced set of interesting positive and negative quantitative association rules[J].IEEE Transactions on Evolutionary Computation,2014,18(1):54-69.

[8] EIRINI S, DEBIE T, MARIO B. Interesting pattern mining in multi-relational data[C]//Data Mining and Knowledge Discovery. Netherlands: Springer Netherlands,2014:808-849.

[9] VAHID B, MOHAMAD M, AZURALIZA A. multi-objective PSO algorithm for mining numerical association rules without a priori discretization[J].Expert Systems with Applications,2014,41(9):4259-4273.

[10] STANISIC P, TOMOVIC S. Apriori multiple algorithm for mining association rules[J].Information Technology and Control,2008,37(4):311-320.

An improved Apriori algorithm based on multi-valued attributes

ZHAO Long, YANG Xiaobing, WU Qiang, GAO Yu
(College of Information Engineering,China Jiliang University, Hangzhou 310018, China)

As data mining becomes more and more complex, multi-dimensional association rules become one of the most useful in association rules mining. In this paper, a solution was proposed on the case of repeated connection of the same attribute data in the mining of multi-dimensional association rules. By comparing multi-valued attribute information, the algorithm removed the attribute information of duplicate connection, retained the effective information, and reduced scanning of the database. The algorithm improved the connection steps of the Apriori algorithm and obtained the data information and results by using the Boolean association rules. Compared to the Apriori algorithm, the improved algorithm is more quick and accurate to discover knowledge and shorten the time of mining.

multi-dimensional association rule; multi-valued attribute; Apriori algorithm; Boolean association rule

2096-2835(2017)01-0108-05

10.3969/j.issn.2096-2835.2017.01.019

2016-12-01 《中國(guó)計(jì)量大學(xué)學(xué)報(bào)》網(wǎng)址：zgjl.cbpt.cnki.net

趙 龍(1991- ),男,安徽省淮北人,碩士研究生,主要研究方向?yàn)閿?shù)據(jù)挖掘.E-mail:745198363@qq.com 通信聯(lián)系人：楊小兵,男,副教授.E-mail:xyang@cjlu.edu.cn

TP391

A