趙 龍,楊小兵,吳 強,高 宇

(中國計量大學 信息工程學院,浙江 杭州 310018)

一種基于多值屬性的改進Apriori算法

趙 龍,楊小兵,吳 強,高 宇

(中國計量大學 信息工程學院,浙江 杭州 310018)

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

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

數(shù)據(jù)在當今時代已經(jīng)成為一種重要的資源,面對龐大復雜的信息數(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].它們在面對不同的事務(wù)類型時采取不同的挖掘方式,交易型數(shù)據(jù)庫和關(guān)系型數(shù)據(jù)庫是它們主要處理的事務(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ī)則,然后再通過Apriori算法進行挖掘計算.但是這種方法也存在著不足之處,會使事務(wù)數(shù)據(jù)庫的屬性值不斷增加,數(shù)據(jù)會變得復雜,給挖掘過程帶來了不少難處.近年來,還有很多關(guān)于多值屬性算法的嘗試,國內(nèi)和國外一些研究者嘗試用矩陣的方法來處理多值屬性的數(shù)據(jù)[4-6],這在一定程度上解決了關(guān)聯(lián)規(guī)則轉(zhuǎn)化帶來的問題;但同時矩陣在進行數(shù)據(jù)存儲和處理也帶來了其他問題,當數(shù)據(jù)量很大時,可能無法處理這些由矩陣存儲的數(shù)據(jù),這會使計算變得相當復雜.還有很多使用關(guān)聯(lián)規(guī)則改進算法進行數(shù)據(jù)挖掘的嘗試[7-9],但是過程中都出現(xiàn)了不可避免的同種屬性值連接的情況,一方面數(shù)據(jù)復雜的屬性值影響了算法的效率,另一方面算法的使用中沒涉及到處理同種屬性值連接的情況,影響了算法的挖掘效率.

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

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

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

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

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

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

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

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

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

(1)

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

(2)

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

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

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

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

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

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

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

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

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

3 算法改進

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

輸入:

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

min_sup:最小支持度閾值

輸出:

L,D中的頻繁項集

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ù)庫D進行計數(shù)

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

6)for each candidatec∈Ct

7)c.count++}

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

9)ReturnL=UkLk

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

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

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

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

1)for each項集l1∈Lk-1

2)for each項集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

//刪除重復連接的候選

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

8)deletec

//刪除非頻繁的候選

9)else addctoCk}

10)returnCk

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

4 實驗及分析

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

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

表2 實驗數(shù)據(jù)記錄表

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

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

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

表3 實驗數(shù)據(jù)記錄表

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

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

5 結(jié) 論

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

[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ān)聯(lián)規(guī)則的挖掘算法[J].計算機工程與科學,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 《中國計量大學學報》網(wǎng)址：zgjl.cbpt.cnki.net

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

TP391

A