數據流環境下的頻繁項集挖掘綜述

吳丹　劉賀

基金項目：長春理工大學經濟管理學院大學生創新創業訓練項目《可視化流數據挖掘的交互平臺》;項目編號：201910186046。

摘要：近些年來，在數據流環境下進行數據挖掘已得到該領域的熱點關注。數據流與靜態數據有很大不同，它具有無限、連續、高速和實時等動態特征，這就使得以往傳統的頻繁項集挖掘算法不在適用數據流環境。因此，本文將針對數據流環境下的頻繁項集挖掘進行研究，將其分為三個方面，分別對其代表算法進行詳細分析，做出對比并進一步總結，為學者們呈現出數據流挖掘在過去十余年中的發展，同時總結現有研究中存在的不足，提出未來可能的研究方向。

關鍵詞：數據流;頻繁項集挖掘

中圖分類號：TP18;O157.5文獻標識碼：A文章編號：1672-9129（2020）07-0060-02

Abstract：In recent years， data mining in the data flow environment has attracted much attention in this field. Data flow is very different from static data. It has such dynamic characteristics as infinite， continuous， high speed and real time， which makes the traditional frequent itemset mining algorithm not suitable for data flow environment. Therefore， this article will focus on data flow under the environment of frequent itemsets mining， which can be divided into three aspects， the detailed analysis of its representative algorithms respectively， make a comparison and summary， further present a data stream mining for scholars in the past more than ten years of development， summarizes the existing shortcomings in the course of study at the same time， the future research direction is put forward.

Key words：data flow;Frequent itemset mining

1數據流環境中的頻繁項集挖掘概述

數據流環境下的頻繁項集挖掘是一個重要的研究內容，當前的頻繁項集挖掘研究中主要有3個分支：挖掘完全頻繁項集、頻繁閉項集與最大頻繁項集。

1.1獲得完全頻繁項集的方法。完全頻繁項集中包含的項集數量巨大，其經典算法是LossyCounting算法。為了體現不同時段數據的時效性，韓家煒等人于2003年首次將時間粒度的概念與窗口模型相結合提出了著名的FP-stream算法[1]。

（1） FP-stream算法。FP-stream算法在FP-growth算法的基礎上，構建并維護一個嵌入傾斜時間窗口信息的Pattern-tree結構，存儲和壓縮頻繁模式。核心步驟如下：

①傾斜窗口及其更新。傾斜時間窗口用來維護頻繁模式信息，其對應的時間窗口時刻為t，t，2t，4t，…2nt。當一批新事務B抵達傾斜時間窗時，若時刻未達2nt，需引進中間緩沖窗口，到滿后合并緩沖窗口并更新到下一窗口，直到更新完2nt的時間窗。

②頻繁模式的更新及pattern-tree的建立。i=1，首批事務B1抵達，清空結構樹。計算事務各項支持數，遞減排序創建有序列表List，并按此順序對數據項進行排序。當B1完全到達，按照List表順序構建FP-tree，并刪除所有支持度計數f<εB1的項。利用FP-growth算法對FP-tree挖掘所有的ε-頻繁項集以創建pattern-tree，隨后丟棄內存保留的批事務B1及FP-tree。

i>1，隨后抵達的每個批事務，采用相同處理方式：清空FP-tree，將每個事務t按List順序插入FP-tree。當前Bi處理完后，利用FP-growth算法挖掘出FP-tree樹結構中的所有頻繁項，并采用如下方法更新pattern-tree。

③Pattern-tree的更新。

1）查詢I是否存在于pattern-tree中。如果存在，在i的傾斜時間窗口表中增加i的出現次數，同時對時間窗口表進行尾剪枝操作。如果更新后i的傾斜時間窗口表為空，算法將停止挖掘i的所有超集，并在深度掃描pattern-tree時刪除項集i及其超集;否則，繼續挖掘i的超集;如果不存在，但fi≥εBi，將I插入pattern-tree中。

2）借用深度優先搜索算法掃描pattern-tree，對于每一個未更新的項集在時間窗口中插入0，并進行尾減枝。掃描項集I和其超集及超集兄弟結點，判斷對應的傾斜時間窗表是否為空，如果為空，刪除對應的結點。

FP-stream算法存在許多問題：（1）構建FP-tree時需兩次掃描數據庫;（2）挖掘頻繁模式時需大量動態的生成和釋放FP-tree結構;（3）FP-stream采用自底向上遍歷，查找和更新速度較慢。

（2） PSW算法。黃威于2010年提出了基于滑動窗口的數據流頻繁項集挖掘算法——PSW算法[2]。PSW算法提出PSW-tree，使頻繁項集的挖掘和更新在PSW-tree中同時進行，較FP-stream算法在挖掘頻繁模式時需要大量動態的生成和釋放FP-tree結構有更好的時空效率。

核心步驟如下：

①PSW-tree的建立。PSW-tree是基于FP-tree的改進模式樹，用child-link和brother-link鏈接節點，對數據項進行自頂向下索引，存儲（臨界）頻繁模式。將基本窗口BW1挖掘得到的（臨界）頻繁模式加入到樹中，為每一節點分配滑動窗口表，用來記錄最近幾個基本窗口計數，當新W1中事務到達完畢，將I-count插入到W1計數中。

②PSW-tree的更新。若事務t的滑動窗口表中非頻繁，則其進行預剪枝，清空Wt，用于記錄下一次新的基本窗口計數;如果Wt不為空，且t的孩子子樹不為空，采用合并策略，把t的孩子子樹的節點計數合并到其兄弟子樹中;若孩子子樹為空，進行尾剪枝。

隨后，杜志剛于2012年提出MFIS-stream算法[3]，在黃威算法的基礎上提出FIS-tree結構，添加信息窗口列表W于各項末節點，記錄末節點的窗口位置和出現次數，通過該節點的位置信息可快速找到舊窗口中的事務，只需刪除末節點列表中含i的項，就可快速更新數據。

1.2獲得頻繁閉項集的方法。在數據挖掘所生成的完全頻繁項集中，有相當大一部分是冗余的信息，降低時間、空間效率。頻繁閉項集可以在保證沒有信息損失的基礎上，減少冗余的頻繁項集，其經典算法為Closet，但在數據流挖掘的情況下并不適用。

（1）Moment算法。Moment算法[4]用加入了交易表TID的FP-tree來存儲窗口中的數據;用CET結構來挖掘FP-tree中的閉頻閉繁項集和潛在閉頻繁項集;利用哈希表（Hash Table）來維護CET中的閉頻繁項集。

①創建CET。在FP-tree中判斷節點類型，創建只含頻繁閉項集及頻繁閉項集和其余項集之間的邊界項集的CET數據結構。對任一節點ni，查看哈希表，若節點ni既不是非頻繁的也不是無希望的，則查看子節點，判斷ni是一個中間節點還是閉合節點。

②CET的維護過程。當新事務被添加到窗口或刪除時，從根節點開始遞歸進行檢驗所有相關節點的類型是否發生變化。新事務t可能導致ni更改其節點類型的情況如下：

1）ni為非頻繁節點。若ni變得頻繁，必須檢查ni兄弟節點能否創建出包含ni的子節點，若創建成功，調用函數判斷節點類型;

2）ni為無希望節點。若包含ni兄弟節點的子節點支持數小于ni的支持數，則ni將變為有希望節點，原來被修剪的分支需重新判斷節點類型;

3）ni為閉合節點。假設添加事務t，ni將保持為一個閉合節點，但會更新其在哈希表中的條目數量;

4）ni為中間節點。當ni的一個子節點具有與它相同的支持數s時，其仍為中間節點;如果新添加的事務t包含ni，并且ni的子女中沒有一個和它有相同的s時，ni變為閉合節點。

Moment算法的不足之處：（1）CET存在非閉項集，且判斷結點類型將耗費大量時間;（2）算法運行完整的更新過程，當添加的新事務與刪除的舊事務一致或存在共有項時，可能使內存中的數據結構出現大幅波動。

（2） CFMoment算法。針對Moment算法可能出現的數據顛簸問題，王金偉等人于2018年提出了一種高效的數據流頻繁閉項挖掘算法CFMoment[5]。當項集被添加或刪除時，并不直接修改CET樹，而只確定CET樹的哪些節點受新項集和舊項集的操作影響。

CFMoment算法對CET樹更新的改進之處：

當窗口滑動時能對CET產生影響的有最舊事務top的刪除和最新事務bottom+1的添加，此算法利用這一點，首先判斷top和bottom+1事務是否相同，若相同，則不更新CET，反之，取兩事務交集，記為i，將top-i的所有子集加入minus，將（bottom+1）-i的所有子集加入plus，調用函數對這兩項集的單項集進行頻繁性檢查。若某單項由頻繁變為非頻繁，則原包含它的頻繁閉項集都將被去除;反之，保持不變。

1.3 獲得最大頻繁項集的方法。挖掘最大頻繁模式的算法時空效率比其他兩種更高，其經典算法是Chang等提出的estDec+算法，采用時間衰減機制降低歷史數據的支持度作用。

（1） BFPM-Stream算法。在現實中，數據流速非恒定是很常見的，它會導致待處理數據不穩定的現象。針對此問題，陳艷于2010年提出BFPM-Stream算法[6]，借助將時間和事務相融合的滑動窗口，用位對象表示數據和位頻繁模式樹BFP-Tree進行數據存儲，解決了數據流的流速不確定性問題。

基本思想如下：

①事務和時間相結合的滑動窗口。非恒定流速的數據流挖掘，需先設置一批事務數閾值N和時間閾值T。滿足任何一個參數，便可將其作為當前滑動窗口，將其所包含的事務集作為等待挖掘的項集。

②帶權的位對象數據格式。將滑動窗口中的事務用帶權的位對象表示，即用固定長度的二進制位表示模式的一個位串，窗口W內的模式x的二進制位記為T（x），若x在W內的第i個事務中存在時T（x）的第i位為1，反之為0。

③位頻繁模式樹的建立

掃描滑動窗口中的事務，得到所有頻繁模式及其支持數，按支持度降序排序，得到頻繁項目頭表List和項目位權表;將中值為1的位所對應的位權逐個插入到模式樹中。

（2）MMFI-DS算法。挖掘最大頻繁項集需不斷計算數量龐大的項集支持數，比較耗時。毛伊敏于2011年提出了最大頻繁項集挖掘算法MMFI-DS[7]。SEFI-tree結構采用自底向上和自頂向下策略，存儲最大頻繁項集的有關信息，刪除過長的最大頻繁項集的子集和非頻繁項集的超集，減少計算項集支持度所消耗的時間。

主要內容如下：

①SEFI-tree的構造和維護。將數據流中每個項插入到SEFI-tree中，將每個事務的子集插入到存儲結構OFI-list中。讀完一個基本窗口的數據，刪除FI-list指向EIS-tree具有相同的I-item所有不頻繁的結點的所有信息。

②最大頻繁項集的挖掘。FI-list中各節點對應的OFI-list中的各項通過組合產生項目集與該節點合并，得到最大頻繁候選集。將該最大頻繁候選集平分到項集E1、E2里。對E1自頂向下搜索，將頻繁項集放入MFI項集中，并刪除E2中該項的子集;對E2自底向上搜索，若頻繁項集不是MFI的子集，則將其頻繁項集放入MFI中，否則從E1中減去含有E2的超集。

2結語

本文著重對關聯規則挖掘中的完全頻繁模式、頻繁閉模式和最大頻繁模式的代表算法進行了分析，并進行對比總結。但各種算法的性能對于不同數據集產生不同作用，沒有一種算法能夠適應所有的數據集滿足所有的需求。目前，隨數據流越來越多，模式數量巨大，如何在滿足用戶不同需求的同時盡可能的使模式壓縮;如何結合近幾年的云計算發展來提高數據挖掘效率等成為研究者進一步的研究方向。

參考文獻：

[1]Giannella G Hanj.Yup.Mining Frequent Pattern sin Data Stream sat Multiple Time Granularities.Data Mining：Next Generation Challenges and Future Directions.2004.191-212.

[2]黃威.數據流的頻繁模式挖掘算法研究[D].西安科技大學，2010.

[3]杜志剛.基于數據流的挖掘算法研究[D].西安科技大學，2012.

[4]Chi Y，Wang H，Yu P.Catch the moment：maintaining closed frequent itemsets over a data stream sliding window.Knowledge and Information Systems，2006，10（3）：265-294.

[5]王金偉，吳少華，瞿治國.CFMoment：挖掘數據流頻繁閉項集算法[J].應用科學學報，2019，37（3）：389-397.

[6]陳艷.數據流的最大頻繁模式挖掘研究[D].西安科技大學，2010.

[7]毛伊敏.數據流頻繁模式挖掘關鍵算法及其應用研究[D].中南大學，2011.

作者簡介：吳丹（1999-），女，漢族，河北唐山市人，本科生，單位：長春理工大學經濟管理學院信息管理與信息系統專業，研究方向：大數據研究。