一種基于圖的數據流關聯規則挖掘算法

汪峰坤，張婷婷

計算機及其應用

一種基于圖的數據流關聯規則挖掘算法

汪峰坤，張婷婷

針對經典的數據流挖掘算法Lossy Counting算法空間性能較差，并且在搜索指定長度的頻繁項所用時間較長等缺點.提出了基于改進的有向圖結構的數據流挖掘算法.改進的算法可在圖中雙向查詢和增加頻繁項，并且結構中包含了頻繁項的長度，在進行指定長度頻繁項查詢時，無需遍歷整個數據結構.實驗表明，改進算法比Lossy Counting算法執行效率有所提高.

數據流挖掘；關聯規則；頻繁項集

數據流上的關聯規則挖掘是數據挖掘重要的研究方向［1］.隨著網絡應用，特別是物聯網應用的快速發展，針對數據流的處理越來越多［2］.如各種傳感器監測信號分析、網絡中連接地址分析、股市實時分析等領域.數據流是指具有無窮、實時、不確定、連續、隨時間變化等特點的數據序列.數據流無法全部保存在主存中，數據流挖掘算法必須滿足對數據只掃描一次，處理速度要足夠快.

Manku和Motwani于2002年提出了“有損計數算法”［3］，近似挖掘數據流中的數據頻繁項.算法使用了兩個參數：支持度閾值s和允許錯誤范圍ε.將數據流中數據分成“桶”，每“桶”共條記錄，當“桶”滿時進行挖掘.當滿一個“窗口”（多個“桶”）時進行剪枝，挖掘的中間結果以Trie樹形式保存在內容中.該算法的優點是計數比較準確，任意元素統計個數最大誤差不超過εN（其中N是數據流的長度）.缺點是算法空間性能不是很好，數據存儲結構不太緊湊.Li等提出了基于前綴樹的數據結構“頻繁項集的項后綴森林（Item-suffix Frequent Itemset forest）”和基于此數據結構的算法：DSM-FI［4］.Item-suffix forest由三個部分組成：OFI-List、FI-List和 SFI-Tree.優點的是插入數據時較快.缺點是增加刪除結點要在多個數據結構中進行.Chang和Lee提出了舊數據作用隨時間衰減的數據流挖掘算法［5］.該算法優點是通過定義衰減因子d，當新數據到來時，對已有數據個數按衰減因子減少，體現了新到數據的重要性.缺點是衰減因子大小不好定義.

數據流關聯規則挖掘算法主要由兩部分組成：數據頻繁集的生成和數據頻繁項的查詢.對于數據頻繁集的生成，一般是在主存中生成數據流的頻繁集的數據摘要.因為算法要針對連續到達、數據量巨大的有序序列進行挖掘，所以數據頻繁集生成算法要足夠快，即數據頻繁集生成算法的時間復雜度要低.頻繁項實時查詢操作過程中，用戶往往對指定頻繁項長度范圍的頻繁項感興趣.例如：在某次查詢中，用戶可能想查看長度大于4的頻繁項.在常見的數據流挖掘算法中，如果查看指定長度的頻繁項，需要遍歷所有頻繁項，然后根據長度進行篩選顯示.

針對上述應用場景，本文提出了基于圖結構的數據存儲結構BNG（雙向結點圖）和基于BNG的數據流挖掘算法DSM_BNG.當向BNG數據結構中插入頻繁項時，算法可以從頭結點和尾結點同時進行查詢與增加.并且BNG中包含了頻繁項的長度，在進行指定長度頻繁項查詢時，無需遍歷整個數據結構.通過仿真實驗，驗證了本文算法的有效性.

1 數據流關聯規則的基本概念和理論

設DS={I1,I2,...,In,...}表示一個數據長度可以是無限的數據流，其中Ii表示在數據流中的第i條事務（或數據）.事務I={x1,x2,...,xk}，xi為事務中一項，如果事務I中項的個數為k，則稱此事務的長度為k，也記作：k=||I.所有長度為k的事務組成的集合稱為事務的k項集（k-itemset）.為了表示的方便，我們設每條事務都包含一個唯一標識tid，即I=(tid,x1,x2,...,xk).

定義1 對事務I={x1,x2,...,xk}中的項按某種規則排序（一般比較ASCII碼值）后得到的新事務I'={x1',x2',...,xk'}，稱為有序的事務I.在本文中不區分I和I'，認為它們是等價的.本文中提到的事務，默認是指排序的事務.

定義2 在算法處理過程中，將數據流中按時間讀取的固定事務個數的數據序列稱為窗口，記作：W，其中在窗口中所包含的事務個數稱為窗口大小，記作：| |W.

定義3 給定支持度閾值s(0＜s＜1)，如果事務Ik在數據流中出現的次數大于等于sN（N為當前已接收的數據流長度），則稱事務Ik為真實頻繁的，記作：FI(Ik).

定義4 給定允許錯誤范圍ε(0＜ε＜1)，如果事務Ik在數據流中出現的次數小于εN（N為當前已接收的數據流長度），則稱事務Ik為不頻繁的.

定義5 如果事務Ik在數據流中出現的次數大于等于(s-ε)N（N為當前已接收的數據流長度），則稱事務Ik為計算頻繁的.

定義6 如果事務I={x1,x2,...,xk}，則其尾插結點集合為I'={{x1,x2,...,xk},{x2,...,xk},...{xk-1xk}}，顯然，對于長度為k為事務，則其尾結點集合中共有k-1條事務.

由于數據流的無窮性，所以在有限的存儲空間和運算時間的挖掘過程中，我們不能以枚舉的方式生成某條事務的所有子集，所以在算法中我們用某事務尾插結點集合代替事務的子集進行計數統計.同理，算法求出的頻繁項集是有誤差的，很難保證能挖掘出所有的真實頻繁項集.通常情況下，針對數據流的挖掘，求出的是計算頻繁項集.在本文中，認為計算頻繁項集和真實頻繁項集是一樣的，簡稱頻繁項集，記作：FI(Ik).

2 改進算法

2.1 算法的基本數據結構

算法的數據結構稱為雙向結點圖（BNG），它的組成部分如下：

（1）頭結點哈希表（HeadHashTable）.頭結點列表中保存事務的第一項相關信息的哈希表.

列表中每一項由5個屬性組成：(item,freq,wId,level,nextLinks).其中item指事務中某項內容.freq指item項出現的次數.wId指item項最早加入的窗口編號.level指以item項為第一項的頻繁事務項的最大層次（即最大長度）.nextLinks：指向下一元素的指針集合.

（2）尾結點哈希表（TailHashTable）.尾結點列表中保存事務的最后一項相關信息的哈希表.

列表中每一項由5個屬性組成：(item,freq,wId,level,prewlLinks).其中item指事務中某項內容.freq指item項出現的次數.wId指item項最早加入的窗口編號.level指以item項為最后項的頻繁事務項的最大層次（即最大長度）.prewLinks：指向上一元素的指針集合.

（3）頻繁候選項集圖結構（FICG）.FICG是在內存中存儲頻繁候選項集的數據結構，每個頻繁候選項的首項和尾項鏈接到頭尾結點哈希表.

FICG中每個結點由4個部分組成：(item,freq,wId,prewLink,nextLinks).其中，item指事務中某項內容.freq指item項出現的次數.wId指item項最早加入的窗口編號.prewLink：指向上一元素的指針.nextLinks：指向下一元素的指針集合.

2.2 算法流程

類似于算法Lossy Counting算法，本算法中生成內存摘要樹也分成三個部分：Buffer、CreateG和SetGen.另外本算法中包括針對實時搜索頻繁項的部分FISearch算法.

Buffer部分是從數據流中讀取多條事務到內存中，然后對每條事項按項進行排序，當讀取的事務長度等于窗口大小| |W時，按順序生成窗口編號，轉到CreateG部分進行處理.

CreateG部分針對Buffer部分傳遞過來的事務進行處理，在內存中生成數據流的數據摘要結構：雙向結點圖.CreateG部分的算法如下.

①遍歷Buffer中每一條事務，并求出每一條事務的尾插結點集合.

②遍歷尾插結點集合中的所有事務.

③根據事務的第一項在HeadHashTable查找是否存在相應項的頭結點，如果存在，更新頭結點中最大頻繁候選項長度level，且轉步驟⑤.否則建立該項的頭結點，然后轉步驟⑤.

④根據事務的最后一項在TailHashTable查找是否存在相應項的尾結點，如果存在，則轉步驟⑤.否則建立該項的尾結點，然后轉步驟⑤.

⑤根據HeadHashTable頭結點指針集nextLinks查找FICG與事務中下一項相同的結點，同時從TailHashTable尾結點指針集prewLinks查找FICG與事務中上一項相同的結點.如果頭查找和尾查找到同一結點，則說明此頻繁候選項已經存在，更新查詢路徑上的結點的freq數值，轉到步驟②.如果未查找到同一結點，轉到步驟⑥.

⑥將未找到的事務項生成FICG結點，其中freq=1，wId為當前窗口編號.將生成的結點按順序連接到FICG中.當在FICG中一條事務路徑生成結束時，更新頭尾結點哈希表中相應頭結點freq為freq+1.轉到步驟②.

⑦算法結束.

SetGen部分用于內存中候選頻繁項集摘要結構的剪枝，刪除FICG中結點的條件是：該結點滿足：freq＜εN，其中N表示當前已讀取的數據流長度.SetGen部分的算法如下.

①遍歷HeadHashTable中每個頭結點.

②如果頭結點滿足freq＜εN，則表示以此頭結點開始的候選頻繁項集都是非頻繁項.刪除頭結點和頭結點下的所有后續結點，轉到步驟①.否則轉到步驟③.

③按廣度優先方式遍歷頭結點后的所有結點，如果被訪問的結點滿足freq＜εN，則刪除該結點和該結點下的所有后繼結點.

④算法結束.

FISearch算法可根據用戶輸入的最短頻繁項長度（MinItemLength），快速在候選頻繁項集中搜索滿足條件的頻繁項.在本算法中不輸出長度為1的頻繁項，即MinItemLength≥2.

FISearch部分的算法如下.

①遍歷HeadHashTable中每個頭結點.

②如果頭結點的level屬性小于MinItemLength則說明此頭結點下的所有頻繁候選項不滿足最短頻繁項長度的要求，轉到步驟①.否則轉到步驟③.

③按深度優先方式遍歷頭結點后的所有后繼結點，如果被訪問的結點滿足freq＞(s-ε)N，則被訪問結點是頻繁項，直到訪問到尾結點.如果深度優先遍歷的頻繁項長度大于或等于MinItemLength，則輸出.

本算法相對于經典的數據流挖掘算法，如：DSM-FI、Lossy Counting等，主要是針對內存中存儲的數據流摘要信息所使用的數據結構進行了改進.通過使用支持頭尾結點雙向搜索并且保存有頻繁項最大層次數屬性的圖結構，可以提高數據流摘要信息的增加刪除操作的性能，同時，也提高了指定最短頻繁項長度的頻繁項集的搜索操作性能.

3 DSM_BNG算法實驗與分析

3.1 算法流程實驗

設讀取某數據流時，當前窗口Wj共有6個事務，N=6，Wj={I1,I2,I3,I4,I5,I6}，各事務內容為 ：I1={a,c,d,f}，I2={a,b,e}，I3={d,f}，I4={c,e,d,f}，I5={a,c,d,e,f}，I6={c,e,f}.假設錯誤范圍ε=0.2，支持度閾值s=0.5，則剪枝條件是結點頻繁數小于等于εN≈2，頻繁項條件是頻繁數大于等于sN=3.算法流程如下.

（1）生成數據流內容摘要HeadHashTable、TailHashTable和FICG.

處理第一條事務：I1={a,c,d,f}.排序后生成尾插結點集合：I1'={{a,c,d,f},{c,d,f},{d,f}}.對于I1'中的第一條事務{a,c,d,f}，到HeadHashTable中判斷首結點a是否存在，不存在生成首結點a.首結點a有(item,freq,wId,level,nextLinks)5個屬性，對應的值為：(a,1,j,4,null).然后判斷直接后繼結點c是否存在，生成結點c，相應的屬性有(c,1,j,*a,null).處理到最后一項時，判斷尾結點f是否存在，不存在生成首結點f.當I1'處理完成時，生成的數據流內容摘要如圖1所示.

圖1 處理第一條事務后的內存摘要數據結構

處理完窗口Wj的6個事務后，生成的數據流內容摘要如圖2所示.

圖2 窗口Wj中數據處理完成時的內存摘要數據結構

（2）對數據流內容摘要進行剪枝操作.

當處理完成窗口中數據后，將執行剪枝操作，通過剪枝去除頻繁項小于或等于εN≈2的結點，減少內存開銷.

例如：對于頭結點b，其頻繁個數為1小于εN，刪除頭結點b和它的所有后繼結點.對于頭結點a的直接后繼結點b的頻繁個數為1小于εN，刪除頭結點a中以b為直接后繼結點的所有結點.剪枝后內存摘要數據結構如圖3所示.

圖3 剪枝完成時的內存摘要數據結構

顯然，當前滿足頻繁數大于等于sN=3的頻繁項集為：{e,f}.

3.2 算法性能比較

針對多維多值數據頻繁模式生成為例，比較了經典的Lossy Counting算法和本文提出的DSM_BNG算法.

圖4 不同數據量上算法運行時間

圖4比較的是不同數據量時數據流關聯規則挖掘的算法效率.測試數據由IBM數據生成器生成.算法參數為：最小支持度1%，錯誤率為0.1%，數據窗口W為100，數據維數為9，數據量1萬條升到10萬條.

由圖4中可見，在數據量較大時，DSM_BNG算法比Lossy Counting算法性能更好.

4 結束語

本文根據數據流關聯規則挖掘特點，提出了基于有向圖數據存儲結構的數據流挖掘算法DSM_BNG.通過仿真，本算法性能相對于經典的Lossy Counting算法有了一定的提升.

A Graph Based on Algorithm for Mining Association Rules in Data Streams

WANG Feng-kun，ZHANG Ting-ting
（Anhui Technical College Of Mechanical and Electrical Engineering，Wuhu，Anhui 241000，China）

In view of the classic data stream mining algorithm Counting Lossy algorithm has a poor performance in space，and in the search for the specified length of the frequent items with a long time and other shortcomings.A data stream mining algorithm based on the improved directed graph is proposed.The improved algorithm can be bidirectional query and add frequent items in the graph，and the structure contains the length of the frequent items，which is not required to traverse the entire data structure when the frequent item of the specified length is carried out.The experiments show that the improved algorithm is more efficient than the Counting Lossy algorithm.

data stream mining；association rules；frequent itemsets

TP301.6

A

1008-7974（2018）01-0065-05

10.13877/j.cnki.cn22-1284.2018.02.017

2017-02-23

2016年安徽省高校省級自然科學研究重點項目（KJ2016A136）；2017年安徽省高校省級自然科學研究重點項目（KJ2017A759）；安徽省質量工程項目（2014mooc093）.

汪峰坤，安徽霍邱人，安徽機電職業技術學院講師；張婷婷，女，安徽蕪湖人，安徽機電職業技術學院講師（安徽 蕪湖241000）.

［1］Agrawal R，Srikant R.Fast algorithms for mining association rules［C］//Bocca JB，Jarke M，Zaniolo C，eds.Proc.of the 20thInt’l Conf.on Very Large Data Bases.Santiago：Morgan Kaufmann Publisher，1994：487-499.

［2］Estan C，Verghese G.New directions in traffic measurement and accounting：Focusing on the elephants，ignoring the mice［J］.ACM Trans，on Computer Systems，2003，21（3）：270-313.

［3］G.S.Manku and R.Motwani.Approximate Frequency Counts OverData Streams［C］.In Proc.Of VLDB，2002.

［4］H.Li，S.Leeand M.Shan.An EfficientAlgorithm for Mining Itemsets over the Entire History of Data Streams［C］//In Proc.Of First International Workshop on Knowledge Discovery In Data Streams，2004.

［5］J.H.Chang and W.S.Lee.Finding RecentFrequent Itemsets Adaptively over Online Data Streams［C］.In Proc.of KDD，2003.

王前）