劉彥戎，楊 云

(1.陜西國際商貿(mào)學院 信息工程學院，陜西 西安 712000；2.陜西科技大學 電子信息與人工智能學院，陜西 西安 710021)

0 引 言

在互聯(lián)網(wǎng)產(chǎn)業(yè)急速發(fā)展的情況下，信息技術(shù)和信息經(jīng)濟也發(fā)展迅速，由此在各行各業(yè)中數(shù)據(jù)挖掘技術(shù)的應用越來越廣泛。數(shù)據(jù)挖掘技術(shù)從現(xiàn)有的未知數(shù)據(jù)中可以發(fā)現(xiàn)大量具有潛在價值的信息或模式，當這個理論提出時，立刻引起了科學界的廣泛關(guān)注。在數(shù)據(jù)挖掘領域中最重要的研究方向是關(guān)聯(lián)規(guī)則挖掘，關(guān)聯(lián)規(guī)則技術(shù)的實現(xiàn)是以數(shù)據(jù)之間的聯(lián)系為基礎來實現(xiàn)其可信度的支持。該算法最初是被P.-G. Cheng[1]作為市場購物籃分析理論提出的，在此過程中通過研究顧客購買行為建立關(guān)聯(lián)知識，來指導商業(yè)貿(mào)易中交易事項的數(shù)據(jù)集合[2]。由于數(shù)據(jù)具有多樣性的特點，從海量數(shù)據(jù)中通過有效探索和篩選可得到有效數(shù)據(jù)，從而可以為智能人機交互提供技術(shù)支持。在數(shù)據(jù)挖掘過程中，關(guān)聯(lián)規(guī)則技術(shù)得到了長足發(fā)展，已在銀行風險預警、金融證券分析和移動通信方面深入應用，并顯示出較好的應用前景和巨大的發(fā)展?jié)摿Α?/p>

許多學者在數(shù)據(jù)挖掘方面做了大量的研究，為其發(fā)展做出了貢獻。傳統(tǒng)關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘的改進大多是基于Apriori[3-5]算法，Apriori算法最大的缺陷是需要對數(shù)據(jù)庫進行多次掃描[6]才能得到頻繁項目集，這就嚴重影響了數(shù)據(jù)挖掘的運行效率。魏玲等人提出了NFUP算法[7]，該算法基于強大項目集的概念，將強大項目集加入到候選項目集的小數(shù)量中，并采用早期裁剪策略來減少掃描數(shù)據(jù)庫的次數(shù)。Dean. J等人[8]提出一種改進的基于客戶關(guān)系管理系統(tǒng)的數(shù)據(jù)挖掘關(guān)聯(lián)規(guī)則Apriori算法，該算法刪除了大量無效事務，隨著事務的減少，數(shù)據(jù)庫的規(guī)模也隨之變小，減少了后續(xù)掃描的記錄，提高了數(shù)據(jù)挖掘的處理效率[9-10]。Rakesh等人[11]針對候選項集數(shù)量多、掃描數(shù)據(jù)庫耗時長等問題，提出了一種有效的挖掘候選項集的算法，該算法克服了數(shù)據(jù)庫掃描時間長的缺陷，減少了候選項集的數(shù)量，提高了執(zhí)行效率。Linden G等人[12]提出了一種基于模糊技術(shù)的數(shù)據(jù)類型統(tǒng)一識別方法，該技術(shù)可以使所有不同的數(shù)據(jù)類型都能以統(tǒng)一的方式進行處理。Borthakur D[13]針對Apriori算法中對數(shù)據(jù)庫進行多次掃描并生成大量候選項集的性能瓶頸，提出了一種新的算法，該算法通過一個預先設定的過濾器過濾掉與挖掘目標無關(guān)的事務，這種方法大大提高了算法的整體性能。錢光超等人[14]提出了一種新的基于布爾矩陣的Apriori算法，該算法通過關(guān)聯(lián)圖和矩陣裁剪的方法減少了候選項集的數(shù)量，實驗結(jié)果表明，該算法使用一次就降低了系統(tǒng)數(shù)據(jù)采集的性能。S. Anekritmongkol等人[15]提出了一種新的基于布爾模型的關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘壓縮算法，主要思想就是通過壓縮數(shù)據(jù)可以大大減少掃描數(shù)據(jù)庫的次數(shù)。J.Pavon等人[16]提出了一種結(jié)合兩者最佳特征算法的矩陣算法，該種組合算法利用矩陣和向量等簡單結(jié)構(gòu)來生成頻繁模式，同時對候選集的數(shù)量進行了最小化處理，從而實現(xiàn)比Apriori算法和FP-growth[17]算法更高效的計算。

基于相似度的Apriori算法是Li X等人[18]所提出的，他們把余弦相似度的閾值作為Apriori算法的改進策略。研究調(diào)查發(fā)現(xiàn)Apriori算法主要存在的問題就是在結(jié)束掃描庫之后生成過多的候選項目集，所以改進關(guān)聯(lián)規(guī)則的主要方式就是縮短掃描時間，提高掃描效率。采用矩陣算法對數(shù)據(jù)庫進行掃描，將項目集改變?yōu)椴紶栔悼梢蕴岣咝?，但是無法刪減重復的事務和項目集，還會導致計算量的增加，所以該文提出了新型的矩陣和排序索引關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘算法，這種方法可以在一次掃描過程當中提高算法的執(zhí)行效率，而且刪除不需要的項目集。

1 一種矩陣和排序索引關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘算法

該文在深入探討了傳統(tǒng)關(guān)聯(lián)規(guī)則之后，提出一種改進的矩陣和排序索引關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘算法，該算法簡稱為IMSIA。算法的基本思想是：結(jié)合矩陣算法k-頻繁項集生成中的高效率和排序索引的高搜索速度的優(yōu)點，將交易數(shù)據(jù)庫轉(zhuǎn)換為交易矩陣，然后不再掃描和使用交易數(shù)據(jù)庫，直接掃描交易矩陣，刪除之前的初始矩陣，在刪除矩陣之前，將矩陣按標記序列放置隨后搜索表，刪除后更新兩個標記序列。將刪除的矩陣與其通過新矩陣獲得的轉(zhuǎn)置矩陣相乘，在矩陣的上三角中分析其數(shù)據(jù)并搜索序列，從而得出兩個準確的頻繁項集。利用所計算出來的頻繁項集，建立排序索引矩陣，矩陣和頻繁項集之間可以使用向下的方式進行連接。

1.1 Apriori關(guān)聯(lián)規(guī)則挖掘算法

在關(guān)聯(lián)規(guī)則算法當中，I表示項目，D表示事務數(shù)據(jù)庫，T表示數(shù)據(jù)庫當中的一組項目。且元素T?I，TID表示任何一個事務的標識符。當滿足A∩B=?、A?I、B?I條件時，A?B的形式稱為關(guān)聯(lián)規(guī)則。A?B的關(guān)聯(lián)規(guī)則是在存在支持度的事務數(shù)據(jù)庫中D建立的，其中p指概率，s指事務數(shù)據(jù)庫中所占的百分比。關(guān)聯(lián)規(guī)則在交易數(shù)據(jù)庫中存在置信度c，如式(1)和式(2)：

sup(A?B)=P(A∪B)

(1)

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

(2)

一個項目集即是包含一組項目的集合，包含k個項目的集合稱為k-項集。在一個項目集中若是存在頻繁項集，則必定具有最小支持度min_sup，關(guān)聯(lián)規(guī)則中若是存在強關(guān)聯(lián)規(guī)則，該規(guī)則中的隱含條件一定是包含最小支持度閾值和最小置信度閾值。

Apriori算法的思想是先搜索而后逐層迭代搜索項集的過程，在搜索的過程中首先掃描事務數(shù)據(jù)庫，并計算每個數(shù)據(jù)項的支持度，生成候選項集C1，利用支持閾值生成頻繁為1-項集L1。Apriori算法的思想是先搜索而后逐層迭代搜索項集的過程，在搜索的過程中首先掃描事務數(shù)據(jù)庫，并計算每個數(shù)據(jù)項的支持度，生成候選項集C1，利用支持閾值生成頻繁為1-項集L1。將生成的L1項集與L1項集自身進行與運算得到候選項集C2，完成事務數(shù)據(jù)庫的再次搜索并將計算得出的候選項集C2的支持度與最小支持度min_sup相比，取其最小者為2-項集L2，以此類推，若事務數(shù)據(jù)庫中找不到頻繁項集，則算法結(jié)束。

1.2 矩陣關(guān)聯(lián)規(guī)則挖掘算法

要實現(xiàn)矩陣關(guān)聯(lián)算法的規(guī)則，首先將事務數(shù)據(jù)庫集合D轉(zhuǎn)變?yōu)椴紶柧仃嘯19]，然后對其中所包含的n個事物和m個項目進行排序，用項目矩陣表示的整個數(shù)據(jù)庫如下所示：

其中，Aij∈I(0≤i≤m,0≤j≤m)，元素{Aij}在矩陣Amn中的定義方程為:

(3)

在矩陣Amn中包含了表示每一事務的行m和表示每一項的列n。在定義方程中若任意一個事務數(shù)據(jù)庫Di存在項目i的第j項，則{Aij}的值為1，若不存在項目i的第j項，則{Aij}的值為0，當矩陣A是一個事務向量時，也可表示為a1,a2,…,am(具有m行向量的矩陣)。

矩陣關(guān)聯(lián)規(guī)則具有屬性1：不包含任何頻繁出現(xiàn)的項目集中，一定也不包含(k-1)頻繁項目集；屬性2：任何非頻繁項集的子集也是非頻繁項集。

1.3 改進的事務矩陣和標記序列掃描

Apriori算法在求解的過程中首先需要求出候選項集Ck，然后對頻繁項集Lk執(zhí)行批處理操作，生成頻繁項集的候選集數(shù)量較大，同時所有頻繁項集要對數(shù)據(jù)庫進行掃描，該操作占用系統(tǒng)內(nèi)存空間較大和CPU處理時間較長，因此很難適應海量數(shù)據(jù)挖掘。矩陣關(guān)聯(lián)規(guī)則挖掘算法雖然不刪除非頻繁項和事務，但還需要搜索數(shù)據(jù)以找到頻繁項集，從而增加了計算量。盡管這些算法已經(jīng)能夠減少候選集的數(shù)量或通過修剪策略來提高挖掘效率，但仍不能完全解決候選集產(chǎn)生的問題。

索引最關(guān)鍵的特征是可以讓檢索信息速度更快，利用索引號可以完成向搜索項目集跳轉(zhuǎn)，假如該行不滿足下行連接條件，則不需要增加掃描量，從而提高了項目集挖掘的速度。在生成2-頻繁項集的算法過程中有計算量大的缺點，由此導致算法的效率低下，矩陣算法在得到頻繁項集前先將事務數(shù)據(jù)庫轉(zhuǎn)換為事務矩陣，然后通過分析得到上三角矩陣，這個過程中省略了向下連接和修剪的步驟，這樣就大大減少了計算步驟，提高了項集的生成效率。該文在分析實驗結(jié)果的基礎上，提出結(jié)合改進的關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘方法和索引優(yōu)點的IMSIA算法，此算法較好地解決了多個數(shù)據(jù)庫連接過程中產(chǎn)生大量候選集的問題。

步驟如下：將事務數(shù)據(jù)庫轉(zhuǎn)換為布爾數(shù)據(jù)庫事務矩陣D，并將標記序列事務對應的矩陣保存到表中相應的項目中，建立一個事務數(shù)據(jù)庫，該事務數(shù)據(jù)庫包含m×n個項目、對應的標記序列為Lr={1,2,…,m}和Lc={1,2,…,n}。在刪除矩陣的屬性時，必須為刪除的相應項目序列進行標記。刪除矩陣后，可以通過相乘獲得S=A×AT。

1.4 改進的自適應排序索引矩陣

由于驗證算法需要搜索數(shù)據(jù)庫并生成候選項，因此會占用大量內(nèi)存并增加I/O成本。索引可以提高檢索信息的速度，但是內(nèi)存編號中保存排列索引所占內(nèi)存較少，并能通過索引號來跳轉(zhuǎn)搜索序列，如果該行不滿足向下連接的條件，則無需進行掃描，在此基礎上減少了搜索時間、搜索數(shù)量、內(nèi)存占用搜索項集量和I/O開銷。該文在改進矩陣算法的基礎上，結(jié)合改進的自適應排序索引矩陣，僅掃描數(shù)據(jù)庫一次，無需生成候選集，并根據(jù)選擇排序規(guī)則進行排序，提高了計算效率和算法的執(zhí)行效率。具體實現(xiàn)步驟如下：

(1)當頻繁項集滿足k>2時，使用改進的自適應排序索引方法以搜索第k個項集(k≥3)。

(2)使用降序排列的1個項目集L作為矩陣的列，在建立排序索引的過程中，按照降序(k-1)項進行設置。例如：行項目集I2對應于值1，I4對應的值為1，則該行表示2個項目集I2I4。其中，每個項目集的每行(k-1)項目也與安排的編號遞減順序保持一致。

(3)由于排序規(guī)則對排序結(jié)果的影響較大，通常是按照自行確定規(guī)則的方法，無法選擇最優(yōu)排序規(guī)則，因此提出了置信度和支持度之間的自適應最優(yōu)選擇規(guī)則。通過計算每個項目集的支持度和置信度，比較min_sup和min_conf的值，如果匹配的項目集數(shù)量較少，則選擇相應的min_sup或min_conf(如果數(shù)據(jù)庫僅給出一個參數(shù))作為給定參數(shù)默認的排序規(guī)則。

(4)依據(jù)每一列當中非零元素的行號順序，將其保存到數(shù)組當中，如果最小支持度的閾值大于項目數(shù)，可以將其所對應的頻繁項目集刪除，對于每一列，使用V(i+j)項集的行號值來替換第j個項集的非零元素，用下一個位置號作為搜索來替換原始列值1，分配最后一個非零元素為當前列的值。對頻繁k-項集Lk(k≥3)，在進行數(shù)據(jù)挖掘時采用的是向下連接排序索引矩陣的方式實現(xiàn)的。

當k=3時，以R1為目標開始掃描，此時完成以索引號為目標的最后一列掃描，之后通過索引號的導引完成Rx的掃描，將掃描得到的結(jié)果與對應的R1和Rx相連得到3-項集。得到的項目集再與具有最小支持數(shù)的項目集連接，對項集進行掃描按照行排列的方式，直到所有的頻繁項集都處于連接轉(zhuǎn)態(tài)，此時得到新的項集。最后根據(jù)關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘的屬性確定是否繼續(xù)進行掃描生成4-項集。當k=3時，按以下步驟生成頻率k-項目集：

①利用向下連接的方法掃描以建立好的排序索引矩陣，如果在掃描的行中不存在“1”，但是具有與k-2相同的索引號時，則直接按照對應的索引號進行跳轉(zhuǎn)，跳轉(zhuǎn)到的行與(k-1)Ry連接形成k-項目集。如果沒有在掃描數(shù)據(jù)庫的過程當中找到繼續(xù)連續(xù)的條件，則可以跳過該行繼續(xù)進行下一行掃描過程。

②使用較小的兩個(k-1)-項目集支持數(shù)作為連接的k-項目集的支持數(shù)。

③按行方式，直到掃描最后一行，將所有的頻繁(k-1)-項目集連接，得到所有的頻繁k-項目集。然后根據(jù)關(guān)聯(lián)規(guī)則屬性確定是否繼續(xù)生成頻繁(k+1)-項目集。

2 實驗結(jié)果

2.1 舉例分析

假如存在事務數(shù)據(jù)庫，設最低支持度為20%，事務數(shù)目為10，如表1所示。

表1 事務數(shù)據(jù)庫D

根據(jù)上述數(shù)據(jù)庫，可以得到矩陣A：

根據(jù)編號對形成的6個頻繁2-項集進行排序，在項目I4對應的列中只存在一個“1”，由此形成的I2I4項目集與其他2個項目集無法進行連接，故刪除事務數(shù)據(jù)庫中與I4對應的列和行，生成結(jié)果如表2所示。

表2 排序索引矩陣

如表2所示，a，b，c，d和e分別表示序號，即在表中5個序號表示的行號只具有索引的作用。首先，用I2I1掃描第1行，將I1的搜索列刪除，以索引號c跳到第三行，即I1I3的行，將第1行和第3行連接起來，獲得頻繁3-項集I2I1I5。I2I1I3的支持度為4，I2I1和I5I1的支持度分別為4和2，因此I2I1I5的支持度為2。繼續(xù)掃描第2行和第3行，直到最后一行，Apriori算法在此步驟中形成候選3個項集，并且有6個，故該方法不利于算法效率的提高。頻繁3-項集L3是{I2I1I3(4),I2I1I5(2)}通過使用排序索引關(guān)聯(lián)矩陣得到的，在生成L3后，對其中的兩個項集再次建立排序索引，用索引號a和b進行向下連接，在此連接過程中不滿足產(chǎn)生4-頻繁項集的條件，至此算法運行結(jié)束，如表3所示。

表3 L3排序索引矩陣

頻繁1-項集L1、頻繁2-項集L2、頻繁3-項集L3、頻繁4-項集L4的取值分別為{I2(7),I1(6),I3(6),I4(2),I5(2)}、{I2I3(4),I2I1(4),I1I3(4),I2I5(2),I2I4(2),I1I5(2)}、{I2I1I3(4),I2I1I5(2)}及空，因此頻繁3-項集L3為最大。

2.2 實驗結(jié)果和數(shù)據(jù)庫分析

依據(jù)算法的時間復雜度可以發(fā)現(xiàn)，IMSIA算法和Apriori算法在對數(shù)據(jù)庫進行掃描時的時間復雜度分別是Q(m)和Q(n×m)，對比后發(fā)現(xiàn)，IMSIA算法掃描數(shù)據(jù)庫的時間較短。在實驗中，利用隨機函數(shù)Random()生成所需數(shù)據(jù)集，當每次輸入項目集|I|和事務|T|時，數(shù)據(jù)庫當中的隨機函數(shù)會生成數(shù)據(jù)集。在數(shù)據(jù)集的生成過程中不存在外界干擾因素，可以充分反映所提出算法的高效性能。

為了進一步深入了解改進算法的優(yōu)勢，對矩陣算法、Apriori算法和IMSIA算法的內(nèi)存使用情況和算法運行時間進行比較。實驗環(huán)境采用Java語言下的Eclipse環(huán)境搭建，操作系統(tǒng)用Windows 7，硬件使用Pentium(R)雙核2.8 GHz/5.0 GB。

分析不同算法在最小支持度和相同數(shù)據(jù)集下的運行時間，IMSIA在k=2時的運行時間為生成矩陣乘以矩陣。當k≥3時，改進后的IMSIA算法所使用的運行時間是矩陣當中搜索項目集和將項目進行排序時間的總和。計算Apriori算法總運行時間時，需要生成候選項目集時間、掃描數(shù)據(jù)庫時間和修剪項目集時間相加得出。圖1對比了多種支持度運行時間，分析該圖可得，處于同一個數(shù)據(jù)集(|T|=1 000，|I|=30)下，改進后的IMSIA算法和每種支持度下的運行時間均小于Apriori算法和矩陣算法。這表明在計算頻繁2-項集之前先刪除了無用的項目和事務，減少不必要的計算量，提高了計算效率，因此改進算法在計算時間上具有較好的優(yōu)越性。在支持度不同的情況之下，對比三種算法所使用的計算時間，可以發(fā)現(xiàn)IMSIA算法效率較高，消耗時間較短，因此優(yōu)勢更為明顯。

圖1 不同算法的運行時間支持度

在數(shù)據(jù)集不同、支持度相同的前提下對比運行時間，結(jié)果如圖2所示。7個隨機生成的長度不同的數(shù)據(jù)集為：D1(|T|=100，|I|=15)，D2(|T|=300，|I|=30)，D3(|T|=500，|I|=40)，D4(|T|=1 000，|I|=50)，D5(|T|=1 500，|I|=60)，D6(|T|=5 000，|I|=80)和D7(|T|=10 000，|I|=120)，將min_sup計數(shù)設置為28。當設置參數(shù)不同時，矩陣算法的運行時間小于Apriori算法、大于IMSIA算法，由此可以得出，改進算法具有更好的執(zhí)行效率，此外，當數(shù)據(jù)集的數(shù)量成線性增長時，所提出的IMSIA算法更能體現(xiàn)其高效率和可擴展的性能。

圖2 不同數(shù)據(jù)集下不同算法的運行時間比較

考慮到算法成本，提出的IMSIA算法只掃描數(shù)據(jù)庫一次，并將索引和排序放入緩存中，降低了I/O操作的成本。在相同數(shù)據(jù)集(|T|=1 000，|I|=30)的情況下設置min_sup=28，通過對比表4中的內(nèi)存使用數(shù)據(jù)，發(fā)現(xiàn)Apriori算法內(nèi)存使用量占15.38%；矩陣算法的內(nèi)存使用量占12.56%；改進的IMSIA算法內(nèi)存使用量占8.31%。通過對比矩陣關(guān)聯(lián)規(guī)則算法與Apriori算法的使用率，前者低于后者2.82%，三種算法中內(nèi)存使用率最低的為IMSIA算法，通過對比內(nèi)存使用率提高了7.05%，進一步驗證了該算法效率高，內(nèi)存使用率低，I/O成本低。

表4 不同算法的內(nèi)存使用情況比較

3 結(jié)束語

提出了一種IMSIA關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘算法，該算法首先通過掃描數(shù)據(jù)庫建立事務標記序列和事務矩陣，而后對矩陣中的無用事務集進行刪除操作，并對標記序列進行從新標記，最后將刪除的矩陣與其轉(zhuǎn)置矩陣相乘，得到頻繁2-項集，再結(jié)合排序索引，得出其余的頻繁k-項集。該算法在運行過程中只對數(shù)據(jù)庫進行了一次掃描，且不生成候選項集，從而大大減少了內(nèi)存的使用率并降低了I/O成本，而且還支持數(shù)據(jù)挖掘的實時更新，提高了數(shù)據(jù)挖掘效率。