張永梅,許 靜,郭 莎

(北方工業(yè)大學(xué) 計算機學(xué)院，北京 100144)

基于堆排序的重要關(guān)聯(lián)規(guī)則挖掘算法研究

張永梅,許 靜,郭 莎

(北方工業(yè)大學(xué) 計算機學(xué)院，北京 100144)

現(xiàn)有的關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘算法或方法中，獲取規(guī)則的計算時間很大一部分都耗費在關(guān)聯(lián)項目集的掃描、數(shù)據(jù)庫頻繁掃描和生成冗余候選頻繁項目集中。傳統(tǒng)方法雖然得到的挖掘結(jié)果比較全面，但并不是所有挖掘結(jié)果中的規(guī)則都是重要的，以往的方法沒有反映出重要的關(guān)聯(lián)規(guī)則而使得挖掘結(jié)果的有效性不高，不利于得到需要的重要目標(biāo)結(jié)果。針對重要目標(biāo)的挖掘，提出一種基于堆排序及鏈表結(jié)構(gòu)的改進(jìn)Apriori算法。算法通過掃描數(shù)據(jù)庫，統(tǒng)計得到各個項目集在所有事務(wù)集中出現(xiàn)的頻率，并按照項目集的頻率次數(shù)進(jìn)行堆排序。然后根據(jù)建立的堆得到所有k階候選項目集并計算其相對應(yīng)的支持度，將不同項目集的支持度與預(yù)先設(shè)定的最小支持度進(jìn)行比較，若滿足最小支持度，就將對應(yīng)的頻繁項目集加入鏈表中，否則依據(jù)剪枝策略剪去這個對應(yīng)項，將通過連接運算生成的候選k+1階項目集采用同樣的操作可以生成k+1階頻繁項目集。這樣可以很大程度上優(yōu)化算法的頻繁項目集的生成過程并加速了重要關(guān)聯(lián)規(guī)則的生成過程，從整體上提高了運算速度。

主要目標(biāo)；Apriori算法；關(guān)聯(lián)規(guī)則；頻繁項目集；排序

0 引 言

隨著現(xiàn)代技術(shù)的飛速發(fā)展，知識正在以一種前所未有的方式飛速向前發(fā)展，如果還是按照以往的技術(shù)去分析所得到的知識，將很難得到所需要有價值的信息，即使能得到，也將會付出很大的代價，而這是所不希望的。

現(xiàn)有的數(shù)據(jù)挖掘算法及其改進(jìn)算法，很多都是針對數(shù)據(jù)的存儲以及數(shù)據(jù)的結(jié)構(gòu)進(jìn)行相應(yīng)優(yōu)化，雖然能夠在一定程度上提高算法的挖掘效率，但是在一些方面還是不能夠滿足應(yīng)用上的需求[1]，因此改進(jìn)算法還是有一定的需求。

堆排序是利用樹的一種結(jié)構(gòu)，可以很快得到需要的數(shù)據(jù)，并且還可以動態(tài)調(diào)整堆的結(jié)構(gòu)，保持堆排序的正常和維護(hù)堆的平衡，是一種具有很高效率的結(jié)構(gòu)。鏈表是一種具有動態(tài)分配并且可以動態(tài)增長的數(shù)據(jù)結(jié)構(gòu)，可以根據(jù)需要來調(diào)整鏈表。文中根據(jù)堆排序的結(jié)果來選取前n項(這個根據(jù)需要調(diào)整，比如前20%、前10%等)，目的是為了得到重要的關(guān)聯(lián)規(guī)則，并且可以優(yōu)化頻繁項目集的生成和掃描等操作。

關(guān)聯(lián)規(guī)則挖掘是從大量的事物集中發(fā)現(xiàn)事物之間潛在的關(guān)聯(lián)關(guān)系，以發(fā)現(xiàn)隱藏在其中的客戶行為模式等[2]。通常頻繁率越高的規(guī)則在實際中具有越重要的價值。基于此，文中要挖掘事物之間聯(lián)系最密切的關(guān)聯(lián)規(guī)則，即重要關(guān)聯(lián)規(guī)則，以便于發(fā)現(xiàn)事物集中最緊密的關(guān)聯(lián)關(guān)系，而不是得到所有與之相聯(lián)系的關(guān)系，需要的是精確而又有所針對性的關(guān)聯(lián)關(guān)系，這才是日益需要挖掘的結(jié)果[3]。

文中提出一種基于堆排序算法以及鏈表相結(jié)合的方法[4]，以優(yōu)化頻繁項目集的產(chǎn)生以及生成過程，從而可以快速得到數(shù)據(jù)挖掘結(jié)果。首先算法通過掃描數(shù)據(jù)庫，統(tǒng)計得到各個項目集在所有事務(wù)集中出現(xiàn)的頻率，并按照項目集的頻率次數(shù)進(jìn)行堆排序，然后可以從建立的堆中選取前n項并計算它們的支持度，比較項目集的支持度是否滿足最小支持度。若滿足最小支持度，就將對應(yīng)的頻繁項目集加入鏈表中，否則依據(jù)剪枝策略剪去這個對應(yīng)項，這樣就可以得到相對應(yīng)的k階頻繁項目集[5-7]。確定的k階頻繁項目集是從已經(jīng)生成的頻繁項目集中選取前n項得到的。而k+1階項目集的生成是根據(jù)已經(jīng)確定的k階頻繁項目集進(jìn)行連接操作而得到的。至于k+1階頻繁項目集則是進(jìn)行前面相同的操作得到的，而沒有新的項目集生成是終止操作的條件。進(jìn)行排序操作是為了便于得到前n項，而選取n項是為了縮減頻繁項目集的掃描及生成運算。

1 Apriori算法及其改進(jìn)

1.1 關(guān)聯(lián)規(guī)則相關(guān)概念

關(guān)聯(lián)規(guī)則可以簡單表示為在已有的數(shù)據(jù)集D中，若由X出現(xiàn)可以得出Y的出現(xiàn)，并且X∩Y=0，則稱X為規(guī)則的前提，Y為結(jié)果。一般情況下將每一個可能出現(xiàn)的情況稱為一項項目集[8-10]。

(1)支持度：在數(shù)據(jù)集D中，項目集X的支持度為項目集X出現(xiàn)的總次數(shù)除以項目集D上的總次數(shù)，即sup(X)=X/D。一般用Minsup表示最小支持度。

(2)頻繁項目集：若項目集X的支持度滿足預(yù)先設(shè)定的最小支持度，則稱項目集X為頻繁項目集。

1.2 Apriori算法步驟

Apriori算法為了得到所有的頻繁項目集需要對數(shù)據(jù)集進(jìn)行多次掃描。算法開始時，為了得到1階項目集，需要對數(shù)據(jù)集進(jìn)行第一次掃描，計算支持度并比較計算的支持度是否滿足最小支持度的要求，若滿足就得到了1階頻繁項目集，然后2階項目集是由1階頻繁項目集進(jìn)行擴展得到的。生成2頻繁項目集的條件是對已經(jīng)得到的2階項目集需要計算其支持度，而支持度滿足最小支持度的要求。這樣k+1階項目集每次都是由k階頻繁項目集得到的，而通過得到的k+1階項目集又可以確定k+1頻繁項目集，直到滿足結(jié)束條件時結(jié)束，從而得到所有的頻繁項目集[11-12]。算法流程圖如圖1所示。

圖1 Apriori算法流程圖

Apriori算法可以通過挖掘數(shù)據(jù)集得到數(shù)據(jù)集中的聯(lián)系。但是Apriori算法需要重復(fù)掃描數(shù)據(jù)庫，消耗了很多運算時間在數(shù)據(jù)的掃描上，且在生成每個候選規(guī)則時都需要判斷低階項目集是否是頻繁項目集導(dǎo)致大量重復(fù)操作，并且由k階頻繁項目集生成k+1階項目集的過程中需要重復(fù)比較項目集是否滿足要求，然而滿足要求的項目集需要再次掃描數(shù)據(jù)集。這是Apriori算法的不足之處。

2 算法的改進(jìn)及分析

2.1 算法的改進(jìn)

由于在實際應(yīng)用的數(shù)據(jù)庫中是不斷增長的，并且具有不確定性，而且每次掃描數(shù)據(jù)集都十分浪費資源，不能夠滿足生產(chǎn)和生活的需求，所以文中針對傳統(tǒng)算法的缺點以及應(yīng)用進(jìn)行了改進(jìn)：

(1)標(biāo)記每一個項目集的數(shù)目；

(2)采用基于動態(tài)堆排序的方法獲取滿足要求的前n項；

(3)將以后新收集到的數(shù)據(jù)集加入到已有的結(jié)果中，而不用再重新計算。

具體策略為在掃描數(shù)據(jù)集的過程中，需要標(biāo)記每一個項目集出現(xiàn)的總數(shù)目，并計算該項目集的支持度[13]。若支持度大于預(yù)先設(shè)定的最小支持度，則對該項目集進(jìn)行標(biāo)記并加入隊列，然后進(jìn)行堆排序(文中采用大堆方式，這樣便于選取前n項以及合并后來的選項)。采用這種方式可以很快地找到滿足要求的頻繁項目集[14]，而且對以后收集到新的數(shù)據(jù)集，如果要加入現(xiàn)有的結(jié)果中，也是十分方便的。

2.2 算法改進(jìn)的步驟

(1)確定n值和最小支持度。這樣可以進(jìn)行后續(xù)的相關(guān)操作，否則無法選取數(shù)據(jù)，進(jìn)行后續(xù)計算。

(2)開始第一次掃描數(shù)據(jù)集D，標(biāo)記每一個項目集出現(xiàn)的次數(shù),并進(jìn)行堆排序。首先從1階項目集的堆排序序列開始，計算1階項目集的支持度并將其支持度與最小支持度進(jìn)行比較。若大于最小支持度，則加入堆排序隊列，并標(biāo)記出現(xiàn)的次數(shù)，否則將其忽略，進(jìn)行下一個項目集的掃描和計算，直到完成所有的1階項目集的掃描和計算[15]。根據(jù)確定的n值從已經(jīng)得到的1階頻繁項目集中選取前n項。若得到的1階頻繁項目集數(shù)目小于n，則全部加入，否則選取前n項1階頻繁項目集，然后根據(jù)1階頻繁項目集生成2階項目集。為了得到2階頻繁項目集需要進(jìn)行同樣的操作運算[16-17]。

(3)根據(jù)上一步確定的k階頻繁項目集產(chǎn)生新的k+1階項目集，計算支持度，然后與最小支持度進(jìn)行比較，若滿足要求，則進(jìn)行堆排序。而算法結(jié)束的條件是沒有新的頻繁項目集生成。

(4)若在現(xiàn)有的運行條件下又有新的數(shù)據(jù)集E加入，則只需掃描新加入的數(shù)據(jù)集E，得到各個新加入的項目集的計數(shù)，并將新加入的項目集的計數(shù)與原來項目集的計數(shù)進(jìn)行合并，然后比較前n項是否改變。若前n項有所改變，則重新計算該階頻繁項目集，若沒有添加或新增新的項目集到前n項，則該階頻繁項目集是不需要改變的。

(5)綜合上述步驟，可以很快得到頻繁項目集，并且有新的數(shù)據(jù)集加入時，也可以很快得到結(jié)果。

圖2為改進(jìn)后的算法流程圖。

在算法的執(zhí)行過程中，主要操作是掃描、排序及比較操作。具體內(nèi)容如下：

(1)掃描。通過對數(shù)據(jù)庫的預(yù)處理，掃描數(shù)據(jù)集，標(biāo)記每一項目集的計數(shù)，并對同一長度的項目集進(jìn)行堆排序，這樣便于查找前n項的項目集，為后續(xù)操作提供基礎(chǔ)。

(2)排序。主要是針對同最小支持度比較以后，通過堆排序算法將頻繁項目集進(jìn)行排序，因為堆排序可以很方便地找到前n項，并且可以很快地調(diào)整前n項的順序，便于動態(tài)增長和刪除頻繁項目集。

(3)比較。主要包含兩部分：第一部分是項目集的支持度與最小支持度的比較，如果某一項目集的支持度大于最小支持度，則將該項目集加入頻繁項目集的堆排序的序列中，否則，刪減掉該項目集。第二部分是比較新加入的數(shù)據(jù)集的項目集是否影響已經(jīng)選取的前n項的頻繁項目集。對新加入的數(shù)據(jù)集進(jìn)行統(tǒng)計分析，從1階項目集開始，合并已有的和新加入的1階項目集的數(shù)目，看是否影響了前n項的項目集，若更改了前n項，則需對1階頻繁項目集進(jìn)行調(diào)整。對調(diào)整后的2階項目集需要進(jìn)行同樣的操作運算。

經(jīng)過上面的幾步操作，避免了重復(fù)掃描數(shù)據(jù)集，不僅優(yōu)化了剪枝方案，而且可以得到重要的關(guān)聯(lián)規(guī)則。

圖2 改進(jìn)算法的流程圖

3 實驗結(jié)果及分析

為了檢驗改進(jìn)算法效率的提升程度，需要在同樣的實驗條件下，將改進(jìn)前與改進(jìn)后的算法進(jìn)行比較。文中在實驗中采用的是人工模擬隨機產(chǎn)生的數(shù)據(jù)集。

根據(jù)實驗條件選取了一定量的事務(wù)集，對改進(jìn)前后的算法的挖掘結(jié)果進(jìn)行比較，如圖3所示。

從圖中可以很明顯地看出，改進(jìn)算法的挖掘結(jié)果比Apriori算法的結(jié)果在頻繁項目集上有所縮減，開始縮減的程度比較高，但是隨著支持度的不斷提高這種差異越來越小。從改進(jìn)算法所得到的挖掘結(jié)果中可以看到，文中所提算法的實驗結(jié)果中明顯減少了一些不太重要的關(guān)聯(lián)規(guī)則，降低了結(jié)果的冗余性，提高了挖掘結(jié)果的有效性。

圖3 運行結(jié)果對比圖

為了驗證改進(jìn)后算法效率的提升程度，將改進(jìn)前和改進(jìn)后的算法在挖掘結(jié)果的運行時間上進(jìn)行比較，如圖4所示。

圖4 運行時間對比圖

從結(jié)果圖中可以看到，改進(jìn)后的算法在同樣的最小支持度條件下，開始時時間提高的不是很明顯，但隨著支持度的加大，時間也隨之增長。這就是改進(jìn)后的方法不用每次掃描數(shù)據(jù)集的優(yōu)勢。

4 結(jié)束語

對重要關(guān)聯(lián)規(guī)則的挖掘算法進(jìn)行了研究，采用一種基于堆排序及鏈表結(jié)構(gòu)的改進(jìn)Apriori算法。雖然Apriori算法是一種經(jīng)典的關(guān)聯(lián)規(guī)則挖掘算法且在數(shù)據(jù)挖掘、數(shù)據(jù)分析及電商平臺等方面應(yīng)用廣泛，但是存在數(shù)據(jù)挖掘效率低且難以適用于較大數(shù)據(jù)量的致命缺陷。通過研究Apriori算法和重要目標(biāo)關(guān)聯(lián)規(guī)則的特征，結(jié)合堆排序的特點并將其應(yīng)用于規(guī)則發(fā)現(xiàn)的過程中，優(yōu)化了數(shù)據(jù)集的選擇以及生成候選集的運算，同時同剪枝策略的結(jié)合也優(yōu)化了剪枝的過程。另外在一定程度上可以利用已有的挖掘結(jié)果，方便將現(xiàn)有的結(jié)果

和未來的數(shù)據(jù)集相結(jié)合，能更好地發(fā)現(xiàn)重要規(guī)則并利用其價值推斷相應(yīng)的規(guī)律等。改進(jìn)算法在挖掘速度上有了一定的提高，并且數(shù)據(jù)挖掘的結(jié)果有一定的縮減。

[1] 黃紅星.挖掘完全頻繁項集的蟻群算法[J].微電子學(xué)與計算機,2014,31(12):144-147.

[2] 馬玉玲.基于clustering算法的事務(wù)抽樣關(guān)聯(lián)規(guī)則挖掘算法[J].計算機應(yīng)用,2015,35(S2):77-79.

[3] 孟海東,李丹丹,吳鵬飛.基于數(shù)據(jù)場的量化關(guān)聯(lián)規(guī)則挖掘研究與實現(xiàn)[J].計算機應(yīng)用與軟件,2014,31(7):40-42.

[4] 楊繡丞,李 彤,趙 娜,等.計算排序算法設(shè)計與分析[J].計算機應(yīng)用研究,2014,31(3):658-662.

[5] 鄭 麟.一種直接生成頻繁項集的分治Apriori算法[J].計算機應(yīng)用與軟件,2014,31(4):297-301.

[6] 陳方健,張明新,楊 昆.一種具有跳躍式前進(jìn)的Apriori算法[J].計算機應(yīng)用與軟件,2015,32(3):34-36.

[7] 崔 亮,郭 靜,吳玲達(dá).一種基于動態(tài)散列和事務(wù)壓縮的關(guān)聯(lián)規(guī)則挖掘算法[J].計算機科學(xué),2015,42(9):41-44.

[8] 羅 丹,李陶深.一種基于壓縮矩陣的Apriori算法改進(jìn)研究[J].計算機科學(xué),2013,40(12):75-80.

[9] 吳 斌,肖 剛,陸佳煒.基于關(guān)聯(lián)規(guī)則挖掘領(lǐng)域的Apriori算法的優(yōu)化研究[J].計算機工程與科學(xué),2009,31(6):116-118.

[10] 張 敏,姚良威,侯 宇.基于向量和矩陣的頻繁項集挖掘算法研究[J].計算機工程與設(shè)計,2013,34(3):939-943.

[11] 畢 巖,章 韻,徐小龍.基于關(guān)系矩陣和頻集樹的關(guān)聯(lián)規(guī)則算法及動態(tài)更新算法[J].南京郵電大學(xué)學(xué)報:自然科學(xué)版,2015,35(4):96-103.

[12] 胡維華,馮 偉.基于分解事務(wù)矩陣的關(guān)聯(lián)規(guī)則挖掘算法[J].計算機應(yīng)用,2014,34(S2):113-116.

[13]HuangYF,LaiCJ.Integratingfrequentpatternclusteringandbranch-and-boundapproachesfordatapartitioning[J].InformationSciences,2016,328:288-301.

[14]FerrerU.ThemultipleaprioriofsocialactsinAdolfReinach[J].LosmúltipleaprioridelosactossocialesenAdolfReinach,2015,49:209-230.

[15]QinShanshan,LiuFeng,WangChen.Spatial-temporalanalysisandprojectionofextremeparticulatematter(PM10andPM2.5)levelsusingassociationrules:acasestudyoftheJing-Jin-Jiregion,China[J].AtmosphericEnvironment,2015,120:339-350.

[16]KhaliliA,SamiA.SysDetect:asystematicapproachtocriticalstatedeterminationforindustrialintrusiondetectionsystemsusingApriorialgorithm[J].JournalofProcessControl,2015,32:154-160.

[17]LinJC,GanWensheng,HongTP.Efficientalgorithmsforminingup-to-datehigh-utilitypatterns[J].AdvancedEngineeringInformatics,2015,29(3):648-661.

Research on Association Rules Mining Algorithm for Main Target

ZHANG Yong-mei,XU Jing,GUO Sha

(School of Computer Science，North China University of Technology，Beijing 100144，China)

The existing association rule mining algorithms or methods waste most of their time on the correlation set database scanning,the frequent scanning and the generating of redundant frequent itemsets candidates during their rule acquisition computation.The traditional methods can get more comprehensive mining results,but not all of the rules that came from the mining result are important.Traditional methods don’t reflect the importance of association rules so as to have inefficiency for mining results,and they are not conducive to the gaining of main target results.Aimed at the mining of important goal,an improved Apriori algorithm based on linked list structure and heap sort is proposed.The algorithm scans the whole database to get the frequency of the appearance of each item set among the whole datasets and do the heap sort.Then,according to the established heap,all thekrankcandidatesetsareobtainedandtherelativesupportiscalculated.Thesupportdegreeofdifferentprojectsetsiscomparedwiththeminimumsupportdegree.Iftheminimumsupportismet,thecorrespondingfrequentitemsetshouldbeaddedtothelist,oritshouldbecutaccordingtotheshearorpruningstrategy.Byconnectingoperation,thecandidatek+1orderitemsetcanbeobtainedfromthegeneratedkorderfrequentitemsets,sotogeneratethek+1orderfrequentitemsets.Inthisway,thegenerationoffrequentitemsetscanbegreatlyimproved,andtheminingresultsofimportantassociationrulescanbeprovided,whichcanimprovethespeedofoperation.

main target;Apriori algorithm;association rules;frequent itemsets;sorting

2016-02-01

2016-06-02

時間：2016-11-22

國家自然科學(xué)基金資助項目(61371143)；北京市自然科學(xué)基金項目(4132026)

張永梅(1967-)，女，教授，碩士研究生導(dǎo)師，CCF會員，研究方向為圖像處理、人工智能、數(shù)據(jù)挖掘；許 靜(1990-)，男，碩士研究生，研究方向為圖像處理、數(shù)據(jù)挖掘。

http://www.cnki.net/kcms/detail/61.1450.TP.20161122.1227.002.html

TP

A

1673-629X(2016)12-0045-04

10.3969/j.issn.1673-629X.2016.12.010