基于BTA算法的數據流頻繁項集挖掘

文 凱，耿小海，許萌萌

(1.重慶郵電大學 通信與信息工程學院，重慶 400065；2.重慶郵電大學 通信新技術應用研究中心，重慶 400065；3.重慶信科設計有限公司，重慶 401121)

0 引 言

數據挖掘，也可以稱為數據中知識的發現，是從大量數據中挖掘有趣模式或知識的過程，大數據的發展阻礙主要是來自于數據的“流動性”和“可獲取性”。大數據從之前的批處理，再到現在的實時處理，以及混合兩者的處理，經過了3次技術革新[1]。隨著時代在不斷的進步，人工智能、模式識別中的搜索算法和建模技術也在數據流挖掘中得到很好的應用，并且吸納了多個領域中優秀知識和思想[2]。

數據流的數據挖掘中存在著許多的機遇和挑戰，這些機遇和挑戰同時也給了我們研究的方向和機會，所以數據流頻繁項集挖掘已成為當前數據挖掘中的一項重要任務，并隨著大數據實時分析發展變得越來越重要。

在數據流處理模型中，目前使用最多的是滑動窗口模型。滑動窗口模型自引入以來就得到廣泛應用，SA-Mi-ner[3]、SYSTree[4]、FTK算法[5]采用滑動窗口模型。WOB點陣算法[6]同樣也是采用的滑動窗口模型，并且該算法巧妙使用點陣技術可以避免反復重建整個樹機構。

近年來孫杜靖等基于FP-tree的結構提出了面向數據流DPFP-Stream[7]算法的設計與實現；國內茹蓓等提出的數據流完全頻繁項集挖掘算法[8]采用GroupTree算法挖掘頻繁項集；HUISW算法[9]是一種不生成候選項集的算法挖掘頻繁項集；而寇香霞等提出的FIUT-Stream算法[10]，用位圖壓縮數據流，空間效率得到提高。

現在的應用不僅僅是在數據流中挖掘頻繁模式，數據流中非頻繁模式的挖掘也進入我們視線之中。Hemalatha等[11]提出的MIP-DS方法是一種基于最小非頻繁模式的數據流孤立點檢測方法；Cagliero等[12]通過提出的算法對不確定數據流匯總的非頻繁權重模式進行挖掘。

針對現有數據流頻繁項集挖掘算法時間消耗長、空間消耗大等問題，本文對FIUT-Stream算法進行改進。首先采用取余進行窗口更新，然后挖掘頻繁項集時采用與操作，最后在支持度更新簡單的數學運算即可。實驗結果表明，本文改進算法相較于FIUT-Stream算法在時間和空間效率有明顯提升。

1 相關知識

定義1 設項目集合I={I1,I2,I3,…，Im}，則該項集中的每一個元素稱為項，任何一個項集都是由I中的若干元素組成，包含k個元素的稱為k-項集。

定義2 數據流DS是由接連不斷到達的事務數據組成的有順序的序列DS={T1,T2,…}。其中Ti(i=1, 2, 3,…)稱為事務，同時，對于數據流中的每個事務Ti都是I中項的集合，即滿足Ti?I。

定義3 用戶設定最小支持度閾值為minsup，倘若項集X出現的頻率即sup(X)≥minsup，則稱項集X為頻繁項集。

定義4 將數據流按w大小等分成若干塊，每一塊對應一個基本窗口，每一個基本窗口有相同的事物數，這些事物數個數|w|即為基本窗口的大小。

2 頻繁項集挖掘

2.1 窗口更新

FIUT-Stream算法采用滑動窗口模型在數據流中挖掘頻繁項集。該算法將數據流壓縮到位表，即FIUT結構；在得到FIUT結構后以滑動窗口的形式進行數據更新，然后對FIUT結構位表里的數據進行聚類得到所有k-itemsets，再根據k-itemsets構建FIU-tree，最后在FIU-tree中挖掘出所有頻繁項集。

相較于其它的算法，FIUT-Stream算法采用位表壓縮數據，極大減少了內存消耗，提高了空間效率；但是該算法在構建FIUT結構時使用兩個表格，這在處理大量數據的時候內存消耗還是極大，而且在使用FIU-tree挖掘頻繁項集的時候有大量的候選項集的產生，使得挖掘效率不高；在有新的數據流到來時，支持度的更新需要對所有的數據進行重新計算，極大地消耗時間。

本文提出的改進算法只需要構建一個位表來進行數據的壓縮，而且采用數學的求與運算直接進行頻繁項集的挖掘，在支持度計算采用簡單的加減運算即可完成，減少了聚類和構建FIU-tree的消耗，在挖掘效率上面有極大的提升。具體思路如下：

表1是本文所用到的數據流，將其分為了4個簇，每一簇包含3個事物，在FIUT-Stream算法中，隨著數據流的流動，按表格的方向進行流動，新簇流入，舊簇流出。

表1 數據集

表2為表1前3個盤壓縮后的數據集，每一次對3個簇進行挖掘，每個簇包含3個事物，其將數據集壓縮存入一個位表里面，這樣在進行頻繁項集挖掘的時候的效率可以得到提高。另外，每一個簇的最下面一行計算每一簇的每一項的支持度計數，表格最后一行計算所有項的支持度計數，見表2。

FIUT-Stream算法在有新的數據到來的時候，是采用滑動窗口的形式，而本文采用文獻[13]取余的方式進行事物更新，當滑動窗口中數據已滿，新來的事物Ti，采用i%n將其插入到窗口中覆蓋原來舊數據進行數據更新。采用這種方式在有新的數據到來時不需要對所有窗口中所有的數據進行滑動，只需要對需要更新的窗口中的數據覆蓋，這對海量數據的更新可以極大提高效率，復雜度從O(m)降到了O(1)，使得挖掘效率得到極大的提升。表3是使用取余的方式將BW4中的數據更新得到的更新表。

2.2 支持度更新

在更新一個BW之后，根據這個BW的支持度計數就可以對更新后的所有項的支持度進行計算，表3是將BW4的數據更新插入BW1。如求a項的支持度時，利用新得到的支持度計算舊的支持度，即3-2=1，1+7=8得到更新后的a項的支持度為8，以此方法就能得到更新后的所有項的支持度，見表3。

表2 壓縮位

表3 更新的數據流壓縮位

2.3 頻繁項集挖掘

在經過一次掃描數據后，就可以得到表3，然后根據最后一行的支持度刪除掉非頻繁1-項集，得到所有的頻繁1-項集。設定最小支持度為4，根據表3得到所有頻繁1-項集分別為：a、b、d、f。得到如表4所示數據，利用超集檢測減少頻繁項集挖掘的項數，使挖掘效率變高。

表4 刪除非頻繁1-項集的壓縮位

接下來就是進行頻繁k-項集(k≥2)的挖掘。在挖掘頻繁k-項集的時候，本文采用的是數學中的求與操作進行頻繁項集的挖掘：如在挖掘頻繁2-項集的時候，我們只需要將要求的兩項所在的列之間進行與，與之后得到1的個數，即為該項集的支持度計數，代表這兩項在同一事物中出現。

算法1：挖掘k頻繁項集(k≥2)

輸入：刪除非頻繁1-項集和支持度計數的壓縮位表D

輸出：所有頻繁項集

for(i = 1; i

for(j = i+1; j

s = 0;

//在k值變化的時候， 這里也要進行相關變化

for(h = 1; h

鋁是目前應用最廣的輕質材料，其密度大約是鋼鐵的1/3.目前，以鋁代鋼是輕量化技術的一個發展趨勢，鋁合金的導熱率、吸收碰撞性、耐腐蝕性、加工性能都優于鋼鐵材料.經過技術的改進，提高了鋁材的強度，完全可以滿足輕量化要求.同時，研究表明，每千克鋁合金可以比高強度鋼、鋼鐵、低碳鋼減少13～20 kg 溫室氣體的排放[24].因此自20世紀70年代開始，鋁合金的地位逐漸上升，成為汽車輕量化首選材料.我國也著手將鋁合金應用于汽車，長安汽車集團與國家輕量化技術創新戰略聯盟攜手研發了“以鋁代鋼”的引擎蓋，同時，用鋁做車頭結構的高端車也在被各高端汽車企業所采用[25].

t = D[h][i]*D[h][j];

s+= t;

}

if (s≥minsup){

記錄頻繁k-項集D[1][i]、D[1][j],…

}

}

}

圖1是頻繁項集挖掘算法流程。

圖1 頻繁項集挖掘算法流程

經過以上幾個步驟，就可以從數據流中挖掘出所有的頻繁項集。該算法的改進在很大程度上提升了FIUT-Stream算法的時間和空間效率。在FIUT結構創建之后，不需要多余創建FIU-tree結構，頻繁項集的挖掘直接用位列表進行數學中的與操作就可以挖掘出所有的頻繁項集，在支持度更新計算采用簡單的加減運算。既減少了構建FIU-tree的空間內存消耗，也通過與操作和新的支持度更新方式提高了時間的效率。

這種高效率的數據流頻繁項集挖掘方式在恐怖分子搜查方面可以得到很好應用，在人流中搜尋頻繁在一個地方出現的人可以給予很大的懷疑，這可以給警方破案提供很大的幫助；另外，用戶在網上瀏覽新聞、網上購物以及查看股票的變化趨勢，都可以通過實時進行分析，給用戶進行個性化的推薦，或者給用戶做出一些指導，隨著信息化社會的發展，這方面的應用也變得越來越廣泛。

3 實驗結果分析

實驗所需要的程序采用的是Java進行編寫，實驗環境為Intel(R) Core(TM) i5-2400 CPU @ 3.1 GHz，4 GB內存，64位Windows 10操作系統。為了更好體現算法的普遍性，本次實驗采用了相對稀疏數據集T40I10D100K和相對稠密數據集connect-4這兩個數據集。其中相對稀疏數據集包含了100 000個事物和942個項；而相對稠密數據集包含了67 557個事物，129個項。為了比較真實使實驗環境為數據流，先是按時間順序使用一個線程從數據集中獲取基本窗口長的數據，然后依次將數據傳送給負責挖掘的線程，這時負責挖掘的線程就具備了時間連續到達的特征。

首先比較了GroupTree算法、FIUT-Stream算法和改進算法BTA在稀疏數據集T40I10D100K和稠密數據集connect-4中的時間開銷。在稀疏數據集T40I10D100K的實驗中，設定滑動窗口大小為4，支持度分別為(10, 15, 20, 25)；對于稠密數據集connect-4，設定滑動窗口大小2，支持度分別為(85, 88, 91, 94, 97)，得到圖2、圖3的時間消耗對比。

圖2 在數據集T40I10D100K下時間消耗對比

圖3 在數據集connect-4下時間消耗對比

由圖2、圖3可以看出，在較高和較低支持度情況下，BAT算法的時間開銷都要比FIUT-Stream算法和GroupTree算法小，在支持度越低效果越明顯，隨著支持度降低差距越來越大。因為改進算法減少了構建FIU-tree和GroupTree的時間開銷，所以在時間效率上比較優越，并且是隨著支持度越低的效果越明顯。

在考慮完時間開銷之后，接下考慮空間開銷。設panes=10 K事物，在稀疏數據集T40I10D100K的時候，滑動窗口大小設定分別為3，5，7，9。在稠密數據集connect-4中，設定滑動窗口大小分別為2，3，4，5，實驗對比結果如圖4、圖5所示。

圖4 在數據集T40I10D100K下的內存消耗

圖5 在數據集connect-4下的內存消耗

由圖4、圖5可以看出，在稀疏數據集和稠密數據集中，隨著Pane數的增加，BTA算法在內存消耗上面都低于FIUT-Stream算法和GroupTree算法，因為FIUT-Stream算法在Pane數越來越多的情況下需要構建的表格消耗內存越來越大，并且在挖掘頻繁項集的時候候選項集會越來越多，而GroupTree算法對GroupTree結構構建越來越多，所以隨著Pane數的增加，BTA算法的空間優越性越來越明顯。

4 結束語

本文針對FIUT-Stream算法在時間、空間效率不高等問題，提出了一種改進算法，改進算法同FIUT-Stream算法一樣將數據壓縮在位表結構中，但是改進算法只需要構建一個表格即可，然后通過將數據流分成等長的思想來準確挖掘數據流中的頻繁項集，而且在滑動窗口更新采用的是取余操作進行數據更新，提升了時間效率。另外，在頻繁項集挖掘采用的求與操作，減少了FIUT-Stream算法的構建FIU-tree的開銷和候選項集產生的開銷，在時間和空間效率都得到一定的提升。最后在進行支持度的更新時，分塊計算支持度計數，然后通過數學運算進行支持度更新，只需要小范圍計算支持度，進一步提高時間效率。