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

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

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

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

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

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

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

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

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

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

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

1 多維關聯規(guī)則

在關聯規(guī)則中,每個不同的謂詞稱為維,規(guī)則中只出現一種謂詞的稱之為單維關聯規(guī)則,涉及到兩個或者多個謂詞的關聯規(guī)則稱為多維關聯規(guī)則.許多算法只關注單維或者布爾型關聯規(guī)則挖掘,這種方法只能發(fā)現單個屬性或屬性值的有無信息,例如:

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

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

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

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

在關聯規(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ī)則挖掘中,最后發(fā)現的規(guī)則通常是由規(guī)則以及這條規(guī)則的支持度和置信度共同構成,進而為判斷挖掘的模式是否具有參考價值提供依據.

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

2 多值屬性數據及特點分析

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

表1 處理后的多值屬性數據樣例

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

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

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

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

3 算法改進

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

輸入:

D:事務數據庫

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{ //掃描數據庫D進行計數

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

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

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

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

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

//連接步:產生候選

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

6)deletec

//刪除重復連接的候選

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

8)deletec

//刪除非頻繁的候選

9)else addctoCk}

10)returnCk

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

4 實驗及分析

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

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

表2 實驗數據記錄表

圖1 耗費時間t和數據量之間的關系曲線Figure 1 Curve between time-consuming and the amount of data

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

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

表3 實驗數據記錄表

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

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

5 結 論

本文提出了一種改進的Apriori算法,在關聯規(guī)則連接步驟中,通過提前判斷已經連接好的頻繁項集中屬性值的屬性,并將即將要連接的屬性值所在屬性與之比較.如果即將連接的屬性值已經存在于已經連接好的頻繁項集中,則停止當前連接,就不再需要將新連接的候選項集與數據庫中的原始數據進行比較,在屬性值比較繁多的時候,能有效避免同種屬性值發(fā)生重復連接,可以有效降低掃描數據庫的次數,進而提高挖掘效率.通過實驗，改進的Apriori與傳統的Apriori算法比較后有一定的優(yōu)勢,效率提高了很多.但是同時,改進算法依然是基于Apriori算法,掃描數據庫時依然有很大開銷,對于這方面的改進工作,以后會繼續(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ī)則的挖掘算法[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 《中國計量大學學報》網址：zgjl.cbpt.cnki.net

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

TP391

A