一種矩陣和排序索引關聯規則數據挖掘算法

劉彥戎，楊 云

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

0 引 言

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

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

基于相似度的Apriori算法是Li X等人[18]所提出的，他們把余弦相似度的閾值作為Apriori算法的改進策略。研究調查發現Apriori算法主要存在的問題就是在結束掃描庫之后生成過多的候選項目集，所以改進關聯規則的主要方式就是縮短掃描時間，提高掃描效率。采用矩陣算法對數據庫進行掃描，將項目集改變為布爾值可以提高效率，但是無法刪減重復的事務和項目集，還會導致計算量的增加，所以該文提出了新型的矩陣和排序索引關聯規則數據挖掘算法，這種方法可以在一次掃描過程當中提高算法的執行效率，而且刪除不需要的項目集。

1 一種矩陣和排序索引關聯規則數據挖掘算法

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

1.1 Apriori關聯規則挖掘算法

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

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

(1)

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

(2)

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

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

1.2 矩陣關聯規則挖掘算法

要實現矩陣關聯算法的規則，首先將事務數據庫集合D轉變為布爾矩陣[19]，然后對其中所包含的n個事物和m個項目進行排序，用項目矩陣表示的整個數據庫如下所示：

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

(3)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 實驗結果

2.1 舉例分析

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

表1 事務數據庫D

根據上述數據庫，可以得到矩陣A：

根據編號對形成的6個頻繁2-項集進行排序，在項目I4對應的列中只存在一個“1”，由此形成的I2I4項目集與其他2個項目集無法進行連接，故刪除事務數據庫中與I4對應的列和行，生成結果如表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。繼續掃描第2行和第3行，直到最后一行，Apriori算法在此步驟中形成候選3個項集，并且有6個，故該方法不利于算法效率的提高。頻繁3-項集L3是{I2I1I3(4),I2I1I5(2)}通過使用排序索引關聯矩陣得到的，在生成L3后，對其中的兩個項集再次建立排序索引，用索引號a和b進行向下連接，在此連接過程中不滿足產生4-頻繁項集的條件，至此算法運行結束，如表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 實驗結果和數據庫分析

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

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

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

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

在數據集不同、支持度相同的前提下對比運行時間，結果如圖2所示。7個隨機生成的長度不同的數據集為：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計數設置為28。當設置參數不同時，矩陣算法的運行時間小于Apriori算法、大于IMSIA算法，由此可以得出，改進算法具有更好的執行效率，此外，當數據集的數量成線性增長時，所提出的IMSIA算法更能體現其高效率和可擴展的性能。

圖2 不同數據集下不同算法的運行時間比較

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

表4 不同算法的內存使用情況比較

3 結束語

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