劉曉慧

摘要：該文研究了矩陣在數(shù)據(jù)庫(kù)關(guān)聯(lián)規(guī)則挖掘中的應(yīng)用，針對(duì)Apriori算法的缺陷及布爾型數(shù)據(jù)的特點(diǎn)，通過(guò)實(shí)例分析并闡述了矩陣的生成、利用矩陣運(yùn)算獲得頻繁項(xiàng)集及產(chǎn)生關(guān)聯(lián)規(guī)則的過(guò)程，并對(duì)挖掘過(guò)程中求最大頻繁項(xiàng)集的方法進(jìn)行了簡(jiǎn)要說(shuō)明。

關(guān)鍵詞：關(guān)聯(lián)規(guī)則；矩陣；權(quán)；閾值

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）23-5455-03

1 概述

Agrawal等人于1993年首次提出關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘之后，研究人員對(duì)挖掘方法進(jìn)行了大量研究，提出了多種算法，針對(duì)布爾型關(guān)聯(lián)規(guī)則的挖掘方法，目前主要有Apriori算法、FP-Tree頻集算法等，其中最有影響的是Apriori算法。在進(jìn)行數(shù)據(jù)挖掘時(shí)，Apriori算法需要多次掃描數(shù)據(jù)庫(kù)，因此數(shù)據(jù)量越大，生成的侯選集也就越龐大，既耗費(fèi)時(shí)間，也需要大量的存儲(chǔ)空間。針對(duì)算法中的不足，眾多學(xué)者提出了多種改進(jìn)方法，如頻繁閉項(xiàng)集算法、FP-Growth算法等。

對(duì)布爾型數(shù)據(jù)進(jìn)行關(guān)聯(lián)規(guī)則挖掘時(shí)，由于數(shù)據(jù)本身的特點(diǎn)，可以考慮將其映射到布爾矩陣，然后通過(guò)對(duì)布爾矩陣運(yùn)算得到頻繁項(xiàng)集，該方法只需掃描一遍數(shù)據(jù)庫(kù)，挖掘過(guò)程采取邏輯運(yùn)算，所需的空間較少，計(jì)算開(kāi)銷小。

2 基于矩陣的關(guān)聯(lián)規(guī)則挖掘方法

進(jìn)行數(shù)據(jù)映射時(shí)，事務(wù)數(shù)據(jù)庫(kù)的每個(gè)事務(wù)對(duì)應(yīng)矩陣中的一行，項(xiàng)目集中每個(gè)項(xiàng)目對(duì)應(yīng)矩陣一列，如果某個(gè)事務(wù)包含某個(gè)項(xiàng)目，則矩陣相應(yīng)元素值為1，否則為0。矩陣中元素[t0j]表示該列所對(duì)應(yīng)的項(xiàng)目在D中的支持?jǐn)?shù)，元素[ti0]為權(quán)值，表示該行在矩陣中重復(fù)出現(xiàn)的次數(shù)，如果矩陣中出現(xiàn)相同的行向量，則將其合并，權(quán)值相加。因此項(xiàng)目集中項(xiàng)目[Ij]在數(shù)據(jù)庫(kù)D中的支持度可由其支持?jǐn)?shù)與總事務(wù)數(shù)求得：

[support（Ij）=i=1ntijn] （2）

將矩陣中各項(xiàng)目對(duì)應(yīng)列根據(jù)該項(xiàng)目支持?jǐn)?shù)大小進(jìn)行降序排列，根據(jù)給定的最小支持度閾值min_sup，計(jì)算頻繁1-項(xiàng)集[L1]。利用矩陣中每個(gè)項(xiàng)目的支持?jǐn)?shù)[t0j]計(jì)算其支持度，將其與支持度閾值進(jìn)行比較，如果該項(xiàng)目支持度不小于支持度閾值，則該項(xiàng)目加入頻繁1-項(xiàng)集，否則將其刪除，由此得到[L1]。

將[L1]與[L1]進(jìn)行連接得到2-項(xiàng)候選項(xiàng)集[C2]，計(jì)算[C2]中每個(gè)候選項(xiàng)的支持?jǐn)?shù)可以通過(guò)計(jì)算[L1]對(duì)應(yīng)矩陣中兩個(gè)項(xiàng)目列向量的內(nèi)積得到，進(jìn)而可計(jì)算其支持度，同最小支持度進(jìn)行比較、剪枝得到頻繁2-項(xiàng)集[L2]。依此類推，直至得到頻繁K-項(xiàng)集[Lk]。具體操作如下：

對(duì)于矩陣中的每一個(gè)項(xiàng)目列[Ij]（j=1…m），其向量可表示為：[Rj=（t1j，t2j，...，tnj）]，則計(jì)算K-項(xiàng)集{[Ii，Ij...Ik]}（[k≥2]）的向量?jī)?nèi)積和支持度公式分別為：

上述方法中，將原始事務(wù)數(shù)據(jù)庫(kù)中的數(shù)據(jù)映射為矩陣后，通過(guò)運(yùn)算比較將所有頻繁1-項(xiàng)集和它們的支持?jǐn)?shù)保留下來(lái)，根據(jù)頻繁項(xiàng)集原理，如果一個(gè)項(xiàng)集是頻繁的，則它的所有子集一定也是頻繁的，即頻繁項(xiàng)集只能由頻繁1-項(xiàng)集通過(guò)操作得到，不可能包含1-項(xiàng)非頻繁項(xiàng)集，所以在矩陣中將非頻繁項(xiàng)集及其支持?jǐn)?shù)刪除，節(jié)省了存儲(chǔ)空間。在產(chǎn)生2-項(xiàng)候選集進(jìn)而得到頻繁2-項(xiàng)集及最后得到頻繁K-項(xiàng)集的挖掘過(guò)程中，對(duì)項(xiàng)目的支持度計(jì)算采用矩陣向量邏輯計(jì)算，減小了整個(gè)計(jì)算的開(kāi)銷。關(guān)聯(lián)規(guī)則挖掘的目的是找出數(shù)據(jù)之間的相互關(guān)系，以規(guī)則的形式給出這種聯(lián)系，而在挖掘的過(guò)程中，生成頻繁項(xiàng)集所需的計(jì)算開(kāi)銷遠(yuǎn)大于生成規(guī)則的計(jì)算開(kāi)銷，因此提高頻繁項(xiàng)集生成的效率，對(duì)于關(guān)聯(lián)規(guī)則挖掘來(lái)說(shuō)是最重要的。

3 挖掘過(guò)程

規(guī)則置信度大于最小置信度閾值，說(shuō)明所得規(guī)則有效。

該方法進(jìn)行數(shù)據(jù)挖掘時(shí)，同傳統(tǒng)的Apriori算法比較，只需掃描事務(wù)數(shù)據(jù)庫(kù)一次，得到布爾矩陣，之后事務(wù)數(shù)據(jù)庫(kù)不再使用，只針對(duì)矩陣進(jìn)行操作，挖掘過(guò)程中采用向量邏輯運(yùn)算，減小了存儲(chǔ)和運(yùn)算開(kāi)銷，提高了挖掘效率。

該方法在挖掘過(guò)程上仍然遵循了Apriori算法過(guò)程，即在挖掘過(guò)程中仍然會(huì)產(chǎn)生大量的候選項(xiàng)集，再對(duì)其進(jìn)行剪枝進(jìn)而生成頻繁項(xiàng)集。當(dāng)數(shù)據(jù)量較大時(shí)，該方法仍然存在不足。針對(duì)這一問(wèn)題，有學(xué)者對(duì)其進(jìn)行了改進(jìn)，具體過(guò)程是在將事務(wù)數(shù)據(jù)庫(kù)中的數(shù)據(jù)映射生成矩陣、并利用最小支持度閾值得到頻繁1-項(xiàng)集后，根據(jù)任何頻繁項(xiàng)集都是某一個(gè)最大頻繁項(xiàng)集的子集這一理論，將逐步挖掘頻繁項(xiàng)集的過(guò)程轉(zhuǎn)換為挖掘最大頻繁項(xiàng)集，進(jìn)而求得頻繁K-項(xiàng)集，具體方法如下：

1） 掃描事務(wù)數(shù)據(jù)庫(kù)，生成矩陣，將矩陣列項(xiàng)目按其支持?jǐn)?shù)降序排序，去除小于最小支持度的列，合并相同的行向量并將權(quán)值相加。

2） 計(jì)算得到頻繁1-項(xiàng)集。

3） 計(jì)算得到最大頻繁項(xiàng)集。

4） 計(jì)算得到頻繁K-項(xiàng)集。由頻繁1-項(xiàng)集產(chǎn)生候選2-項(xiàng)集，其中屬于最大頻繁項(xiàng)集子集的一定是頻繁的，其余候選項(xiàng)集根據(jù)公式（3） 和（4） 進(jìn)行判斷修剪，得到頻繁2-項(xiàng)集。同理，直至得到頻繁K-項(xiàng)集。

針對(duì)過(guò)程（3） 挖掘最大頻繁項(xiàng)集，[3]通過(guò)頻繁模式樹(shù)FP-tree投影生成頻繁模式矩陣FP-array，針對(duì)FP-array上的項(xiàng)進(jìn)行矩陣操作，得到該項(xiàng)的條件FP-array，再通過(guò)挖掘條件FP-array得到以該項(xiàng)為最大項(xiàng)的最大頻繁項(xiàng)集集合。該方法也只需掃描一次數(shù)據(jù)庫(kù)，在計(jì)算過(guò)程中不需要重新開(kāi)辟內(nèi)存空間存儲(chǔ)新的關(guān)聯(lián)矩陣，而且挖掘過(guò)程中采用刪除行列的方法和邏輯運(yùn)算使步驟簡(jiǎn)化，提高了挖掘效率。

4 結(jié)束語(yǔ)

Apriori算法是挖掘布爾關(guān)聯(lián)規(guī)則頻繁項(xiàng)集的經(jīng)典算法，但由于該算法在挖掘過(guò)程中需要多次掃描數(shù)據(jù)庫(kù)并產(chǎn)生大量候選項(xiàng)集，因此需要大量的存儲(chǔ)空間和時(shí)間開(kāi)銷。由于布爾型數(shù)據(jù)本身的特點(diǎn)，可將其映射至布爾矩陣，只需一次掃描數(shù)據(jù)庫(kù)，之后的挖掘過(guò)程只針對(duì)矩陣操作，并且使用邏輯運(yùn)算，提高了挖掘效率。這種挖掘方法不僅可以應(yīng)用于布爾型數(shù)據(jù)，還可以擴(kuò)展到數(shù)值型數(shù)據(jù)，結(jié)合模糊理論，挖掘發(fā)現(xiàn)數(shù)據(jù)間的關(guān)聯(lián)規(guī)則，具有重要意義。

參考文獻(xiàn)：

[1] 杜玉蘭.基于模糊理論的關(guān)聯(lián)規(guī)則挖掘算法研究[D].保定：華北電力大學(xué)，2008.

[2] 劉聞超. 加權(quán)模糊關(guān)聯(lián)規(guī)則挖掘算法研究及應(yīng)用[D].鎮(zhèn)江：江蘇大學(xué)，2010.

[3] 馮潔，陶宏才.快速挖掘最大頻繁項(xiàng)集[J].微電子學(xué)與計(jì)算機(jī)，2007（5） ：123-126.

[4] Han J，Pei J，Yin Y.Mining frequent patterns without candidate generation[C].In Proc.2000 ACM-SIGMOD Int.Conf.Management of Data，Dalas，TX，May 2000.

[5] 文拯.關(guān)聯(lián)規(guī)則算法的研[D].長(zhǎng)沙：中南大學(xué)，2009.