潘俊輝 張 強(qiáng) 王 輝 王浩暢

（東北石油大學(xué) 大慶 163318）

1 引言

數(shù)據(jù)挖掘（Data Mining）是指從大量的數(shù)據(jù)中挖掘出有價(jià)值的、潛在有用的、最終可理解的模式或規(guī)律等知識(shí)的非平凡過(guò)程［1］，它是一門涉及范圍十分廣泛的學(xué)科技術(shù)，通過(guò)它能過(guò)解決許多生活中的問(wèn)題［2］。而關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘中的一個(gè)重要領(lǐng)域，指的是在大量數(shù)據(jù)中挖掘出數(shù)據(jù)項(xiàng)之間潛在的有趣的關(guān)聯(lián)，目前關(guān)聯(lián)規(guī)則已經(jīng)被廣泛的應(yīng)用在眾多領(lǐng)域，如智能推薦、搜索引擎等。關(guān)聯(lián)規(guī)則最早是通過(guò)對(duì)市場(chǎng)的購(gòu)物籃問(wèn)題進(jìn)行分析由Agrawal在1993 年首先提出來(lái)［3～4］，之后諸多的學(xué)者對(duì)關(guān)聯(lián)規(guī)則挖掘進(jìn)行了大量的研究。實(shí)現(xiàn)關(guān)聯(lián)規(guī)則挖掘的經(jīng)典算法稱為Apriori算法，該算法主要通過(guò)對(duì)事務(wù)數(shù)據(jù)庫(kù)中的事務(wù)進(jìn)行不斷地掃描來(lái)發(fā)現(xiàn)所有的頻繁項(xiàng)集，該算法的優(yōu)點(diǎn)是通俗易懂，操作實(shí)現(xiàn)簡(jiǎn)單；缺點(diǎn)是在處理大項(xiàng)集時(shí)，算法的計(jì)算量非常大，導(dǎo)致算法效率明顯下降［5］。因此，如何降低算法的效率是Apriori算法目前面臨的最大的問(wèn)題，也是當(dāng)前關(guān)聯(lián)規(guī)則挖掘算法研究的熱點(diǎn)。

Park 等［6］學(xué)者提出了基于hash 的改進(jìn)方法，該方法通過(guò)簡(jiǎn)化2-項(xiàng)集的產(chǎn)生過(guò)程進(jìn)行改進(jìn)；Savaser 等［7］學(xué)者提出了基于分片的并行改進(jìn)方法，該方法通過(guò)分片提高算法的并行效果；基于采樣的方法是通過(guò)從完整的事務(wù)數(shù)據(jù)庫(kù)選擇它的子集作為樣本進(jìn)行關(guān)聯(lián)規(guī)則的挖掘，然后將子集的結(jié)果作為完整數(shù)據(jù)庫(kù)的結(jié)果［8］；基于矩陣的Apriori算法則通過(guò)把事務(wù)數(shù)據(jù)庫(kù)表示成布爾矩陣的形式完成對(duì)關(guān)聯(lián)規(guī)則的挖掘，它也是Apriori 的一種改進(jìn)，但這種方法在實(shí)現(xiàn)時(shí)易產(chǎn)生過(guò)多無(wú)用元素，浪費(fèi)較多的內(nèi)存空間。本文針對(duì)基于矩陣的Apriori 算法所存在的不足，在此基礎(chǔ)上提出了一種基于壓縮矩陣的高效關(guān)聯(lián)規(guī)則挖掘方法CMEAR 算法（Compressed Matrix Efficient Association Rules Algorithm）。該方法通過(guò)對(duì)矩陣的壓縮，改進(jìn)矩陣的存儲(chǔ)方式及對(duì)項(xiàng)目集進(jìn)行排序等多種方式實(shí)現(xiàn)關(guān)聯(lián)規(guī)則的挖掘，改進(jìn)后的方法不但節(jié)省了存儲(chǔ)空間，同時(shí)也使算法的效率得以提高，最后通過(guò)實(shí)驗(yàn)將改進(jìn)后的方法與傳統(tǒng)Apriori 算法以及基于矩陣的Apriori 算法進(jìn)行了對(duì)比分析，實(shí)驗(yàn)結(jié)果表明基于壓縮矩陣的高效關(guān)聯(lián)規(guī)則挖掘方法在算法的性能上更優(yōu)。

2 關(guān)聯(lián)規(guī)則及基于矩陣的Apriori算法

2.1 關(guān)聯(lián)規(guī)則

設(shè) I={i1，i2，…，im} 是 一 個(gè) 項(xiàng) 的 集 合，記D={t1，t2，…，tn}為事務(wù)T 的集合，對(duì)應(yīng)每一個(gè)事務(wù)有唯一的標(biāo)識(shí)，記作TID，這里事務(wù)T 是項(xiàng)的集合，并且T ?I 。設(shè)X 是一個(gè)I 中項(xiàng)的集合，如果X ?T ，那么稱事務(wù)T 包含X 。

關(guān)聯(lián)規(guī)則是指X ?Y 的這種蘊(yùn)涵式，其中X ?I，Y ?I ，并且X ∩Y=φ。關(guān)聯(lián)規(guī)則中有兩個(gè)重要的概念，分別是支持度和置信度，而關(guān)聯(lián)規(guī)則最終的目的就是從事務(wù)數(shù)據(jù)庫(kù)中找出支持度和置信度都大于用戶設(shè)定的最小支持度和最小置信度的關(guān)聯(lián)規(guī)則［3］，其中支持度是指事務(wù)集中包含X 和Y的事務(wù)數(shù)與所有事務(wù)數(shù)之比，即Supp(X ?Y)=P(X ∪Y)，而置信度是指包含X 和Y 的事務(wù)數(shù)與包含X 的交易數(shù)之比，即Conf(X ?Y)=P(X|Y)。

2.2 基于矩陣的Apriori算法

該算法是對(duì)傳統(tǒng)算法Apriori的一種改進(jìn)，主要是通過(guò)使用矩陣將其融入到Apriori算法中，即把要處理的事務(wù)數(shù)據(jù)庫(kù)以矩陣的形式進(jìn)行表示。下面分步驟簡(jiǎn)要給出基于矩陣的Apriori 算法的實(shí)現(xiàn)過(guò)程。

Step 1：首先把事務(wù)數(shù)據(jù)庫(kù)轉(zhuǎn)換成布爾矩陣，布爾矩陣中的行表示事務(wù)數(shù)據(jù)庫(kù)中的每一項(xiàng)，而列表示事務(wù)數(shù)據(jù)庫(kù)中每一條事務(wù)［9］；計(jì)算布爾矩陣中每一行1 的個(gè)數(shù)，該數(shù)量即是每一項(xiàng)的支持度。如果該值不小于設(shè)定的最小支持度，就構(gòu)成了頻繁1-項(xiàng)集；

Step 2：將比較得到的k-項(xiàng)集（k ≥1）進(jìn)行連接操作，從而產(chǎn)生候選的k+1項(xiàng)集，然后對(duì)候選k+1項(xiàng)集進(jìn)行剪枝操作［10］；

Step 3：掃描并計(jì)算布爾矩陣中行向量的內(nèi)積以得到對(duì)應(yīng)項(xiàng)的支持度大小［9］，如果設(shè)定的最小支持度小于計(jì)算得到的支持度，就得到了k-項(xiàng)集。

由于是通過(guò)將事務(wù)數(shù)據(jù)庫(kù)轉(zhuǎn)換成布爾矩陣之后進(jìn)行掃描，因此基于矩陣的Apriori算法會(huì)減少掃描的次數(shù)，另外在挖掘過(guò)程中是通過(guò)掃描行并做與運(yùn)算進(jìn)行計(jì)算的，相對(duì)傳統(tǒng)的Apriori算法而言也會(huì)提高計(jì)算速度。但該算法在挖掘過(guò)程中也存在一些不足，主要是在連接時(shí)會(huì)產(chǎn)生過(guò)多的候選集，導(dǎo)致占用空間內(nèi)存較多，使得該算法在生成候選集這一方面并沒(méi)有比Apriori算法有明顯的提高，反而易產(chǎn)生較多的候選集。

3 基于壓縮矩陣的高效關(guān)聯(lián)規(guī)則挖掘算法CMEAR

針對(duì)基于矩陣的Apriori算法所存在的缺點(diǎn)，本文在此基礎(chǔ)上進(jìn)行了一定的改進(jìn)，提出了一種基于壓縮矩陣的高效關(guān)聯(lián)規(guī)則挖掘算法CMEAR（Compressed Matrix Efficient Association Rules Algorithm），該算法主要通過(guò)改進(jìn)矩陣的存儲(chǔ)方式，對(duì)矩陣進(jìn)行壓縮以及對(duì)項(xiàng)目集進(jìn)行排序三個(gè)方面進(jìn)行了改進(jìn)。下面對(duì)具體的改進(jìn)過(guò)程分別進(jìn)行詳細(xì)的介紹，最后給出CMEAR算法的具體實(shí)現(xiàn)流程。

3.1 改進(jìn)矩陣的存儲(chǔ)方式

針對(duì)基于矩陣的Apriori 算法易在連接時(shí)產(chǎn)生過(guò)多的候選集，導(dǎo)致占用空間內(nèi)存較多的不足，可以對(duì)矩陣的存儲(chǔ)方式進(jìn)行改進(jìn)。實(shí)現(xiàn)的具體方法為：在算法實(shí)現(xiàn)過(guò)程中增加一個(gè)數(shù)組A，讓它來(lái)存儲(chǔ)布爾矩陣中每列中1 的數(shù)量。之所以加入該數(shù)組的原因是因?yàn)樵讷@得事務(wù)長(zhǎng)度時(shí)可以不用再掃描整個(gè)布爾矩陣，通過(guò)該數(shù)組A 就可以取出事務(wù)的長(zhǎng)度，從而可以減少掃描的時(shí)間，加快對(duì)矩陣的壓縮，同時(shí)節(jié)省了空間。

3.2 矩陣的壓縮

對(duì)矩陣進(jìn)行壓縮主要是為了改進(jìn)基于矩陣的Apriori算法在連接時(shí)所產(chǎn)生的無(wú)用事務(wù)，矩陣的壓縮包括行壓縮和列壓縮兩個(gè)方面。對(duì)于矩陣行的壓縮，首先掃描布爾矩陣，然后通過(guò)文獻(xiàn)［11～12］給出的定理和推論，將一個(gè)子集不能和它相鄰的項(xiàng)集連接就可以刪除這個(gè)項(xiàng)集所對(duì)應(yīng)的行向量，修改新增數(shù)組A，最后剩下的行向量可按照順序組成新的矩陣，從而實(shí)現(xiàn)矩陣行的壓縮。對(duì)于矩陣列的壓縮要在矩陣的行壓縮之后進(jìn)行，當(dāng)對(duì)矩陣的行壓縮后，再對(duì)數(shù)組A 進(jìn)行一次掃描，然后根據(jù)文獻(xiàn)［13～14］的定理和推論，將矩陣中對(duì)應(yīng)值不大于1 的列向量進(jìn)行刪除，進(jìn)一步實(shí)現(xiàn)矩陣的壓縮，從而得到一個(gè)變得更小的新的矩陣。

3.3 項(xiàng)目集排序

基于矩陣的Apriori 算法在進(jìn)行連接時(shí)易產(chǎn)生較多的候選集，因此為了減少它的數(shù)量，改進(jìn)了項(xiàng)目集的排序方式。在改進(jìn)的過(guò)程中根據(jù)文獻(xiàn)［15］中所提出的推論實(shí)現(xiàn)對(duì)矩陣的排序，具體實(shí)現(xiàn)方法為：先找到所有的頻繁1 項(xiàng)集，然后把矩陣中行向量不是頻繁集的刪除掉，然后對(duì)矩陣中頻繁1 項(xiàng)集的行向量對(duì)應(yīng)的支持度大小進(jìn)行增序排列，排列之后會(huì)得到一個(gè)新的矩陣。隨著算法迭代的逐步進(jìn)行，每一步都會(huì)對(duì)項(xiàng)目集進(jìn)行排序，那么算法執(zhí)行的時(shí)間也會(huì)逐漸的減少［16］。

3.4 算法實(shí)現(xiàn)具體步驟

對(duì)基于矩陣的Apriori 算法進(jìn)行了如上述的幾點(diǎn)改進(jìn)之后，下面就來(lái)介紹一下基于壓縮矩陣的高效關(guān)聯(lián)規(guī)則挖掘算法CMEAR 的具體實(shí)現(xiàn)過(guò)程，圖1給出了該算法的流程圖。

Step 1：設(shè)置最小支持度minsup，令k=1。初始化數(shù)組A，該數(shù)組用于存儲(chǔ)布爾矩陣中每列1 的數(shù)量。

Step 2：將要處理的事務(wù)數(shù)據(jù)庫(kù)D 轉(zhuǎn)換為與其對(duì)應(yīng)的布爾矩陣M。

Step 3：掃描布爾矩陣M，計(jì)算出矩陣中每個(gè)行向量的支持度大小，即每行1 的個(gè)數(shù)。比較每個(gè)行向量的支持度與最小支持度的大小關(guān)系，然后刪除小于最小支持度minsup 的那些行向量，而將大于minsup 的行向量所對(duì)應(yīng)的頻繁項(xiàng)則組合得到頻繁1 項(xiàng)集L1，同時(shí)根據(jù)L1中各項(xiàng)支持度的大小進(jìn)行排序得到一個(gè)新的初始矩陣M1。

Step 4：將矩陣M1的行行之間按照順序分別進(jìn)行向量的內(nèi)積運(yùn)算，運(yùn)算之后將計(jì)算結(jié)果不小于最小支持度minsup 的那些行向量組成頻繁2 項(xiàng)集L2，同時(shí)又得到一個(gè)新矩陣M2。同時(shí)對(duì)那些不小于最小支持度的行向量按位累加到數(shù)組A中，令k=2。

當(dāng)k 的值大于等于2 時(shí)將按照如下的Step 5、Step 6、Step 7循環(huán)進(jìn)行操作。

Step 5：掃描矩陣Mk，刪除Lk中不能和其相鄰的項(xiàng)集進(jìn)行連接操作的那些行向量，然后將數(shù)組A 的值進(jìn)行修改，最后對(duì)刪除之后保留下的那些行向量順序排列并組合得到一個(gè)新矩陣Mk。

Step 6：掃描數(shù)組A，刪除數(shù)組A 中所有其值小于1 的列向量，然后將保留下的列向量順序排列得到一個(gè)新的矩陣Mk。

Step 7：清空數(shù)組A。然后將Mk中的可以相互連接的那些項(xiàng)集分別進(jìn)行內(nèi)積運(yùn)算，不小于minsup的行向量組成頻繁k+1項(xiàng)集Lk+1，并得到新矩陣Mk+1，同時(shí)對(duì)那些不小于minsup 的行向量按位累加到數(shù)組A 中。接著判斷得到的新矩陣Mk+1的行數(shù)和k+2之間的大小關(guān)系，如果不小于k+2，那么將k值加1，繼續(xù)執(zhí)行循環(huán)，否則跳出循環(huán)，算法自動(dòng)結(jié)束。

4 實(shí)驗(yàn)及結(jié)果分析

本文對(duì)關(guān)聯(lián)規(guī)則的傳統(tǒng)算法Apriori、基于矩陣的Apriori 算法和基于壓縮矩陣的高效關(guān)聯(lián)規(guī)則挖掘算法CMEAR進(jìn)行了實(shí)驗(yàn)和實(shí)驗(yàn)結(jié)果的對(duì)比分析。實(shí)驗(yàn)中采用兩組數(shù)據(jù)進(jìn)行對(duì)比，第一組采用不同的支持度進(jìn)行分析，第二組則采用具有不同條數(shù)的事務(wù)數(shù)據(jù)庫(kù)。表1 和表2 分別給出了對(duì)比分析結(jié)果。其中支持度的單位為百分比（%），事務(wù)數(shù)據(jù)庫(kù)的單位為條，運(yùn)行時(shí)間以秒（s）為單位。

由表1可見(jiàn)，無(wú)論哪一種算法，隨著支持度的增加，運(yùn)行時(shí)間都在逐漸的減少，但從表中可以明顯地看出CMEAR算法所用時(shí)間遠(yuǎn)遠(yuǎn)小于另外兩種算法，特別優(yōu)于傳統(tǒng)的Apriori 算法，并且支持度越小，算法在時(shí)間上的差別越明顯。

表1 同一事務(wù)數(shù)據(jù)庫(kù)設(shè)置不同支持度的實(shí)驗(yàn)對(duì)比分析結(jié)果

表2 不同條數(shù)的事務(wù)數(shù)據(jù)庫(kù)實(shí)驗(yàn)對(duì)比分析結(jié)果

由表2 可見(jiàn)，對(duì)于不同的事務(wù)條數(shù)，CMEAR 算法在運(yùn)行時(shí)間上同樣遠(yuǎn)遠(yuǎn)小于另外兩種算法，而且隨著事務(wù)條數(shù)的增加，雖然CMEAR 算法運(yùn)行時(shí)間也在增加，但其增加幅度較另外兩種算法，特別是傳統(tǒng)的Apriori算法而言更加趨于平緩。

5 結(jié)語(yǔ)

針對(duì)關(guān)聯(lián)規(guī)則挖掘的改進(jìn)算法基于矩陣的Apriori算法，文中通過(guò)分析給出了該方法的不足之處，在該算法的基礎(chǔ)上提出了一種基于壓縮矩陣的高效關(guān)聯(lián)規(guī)則挖掘方法CMEAR，介紹了該方法的具體改進(jìn)的措施和實(shí)現(xiàn)過(guò)程，最后通過(guò)實(shí)驗(yàn)對(duì)三種方法的效率進(jìn)行了對(duì)比分析，實(shí)驗(yàn)結(jié)果均表明CMEAR算法在時(shí)間性能上更優(yōu)。