數(shù)據(jù)流環(huán)境下的頻繁項集挖掘綜述

吳丹　劉賀

基金項目：長春理工大學經(jīng)濟管理學院大學生創(chuàng)新創(chuàng)業(yè)訓練項目《可視化流數(shù)據(jù)挖掘的交互平臺》;項目編號：201910186046。

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

關(guān)鍵詞：數(shù)據(jù)流;頻繁項集挖掘

中圖分類號：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數(shù)據(jù)流環(huán)境中的頻繁項集挖掘概述

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

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

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

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

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

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

③Pattern-tree的更新。

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

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

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

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

核心步驟如下：

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

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

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

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

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

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

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

1）ni為非頻繁節(jié)點。若ni變得頻繁，必須檢查ni兄弟節(jié)點能否創(chuàng)建出包含ni的子節(jié)點，若創(chuàng)建成功，調(diào)用函數(shù)判斷節(jié)點類型;

2）ni為無希望節(jié)點。若包含ni兄弟節(jié)點的子節(jié)點支持數(shù)小于ni的支持數(shù)，則ni將變?yōu)橛邢Ｍ?jié)點，原來被修剪的分支需重新判斷節(jié)點類型;

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

4）ni為中間節(jié)點。當ni的一個子節(jié)點具有與它相同的支持數(shù)s時，其仍為中間節(jié)點;如果新添加的事務(wù)t包含ni，并且ni的子女中沒有一個和它有相同的s時，ni變?yōu)殚]合節(jié)點。

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

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

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

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

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

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

基本思想如下：

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

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

③位頻繁模式樹的建立

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

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

主要內(nèi)容如下：

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

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

2結(jié)語

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

參考文獻：

[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]黃威.數(shù)據(jù)流的頻繁模式挖掘算法研究[D].西安科技大學，2010.

[3]杜志剛.基于數(shù)據(jù)流的挖掘算法研究[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：挖掘數(shù)據(jù)流頻繁閉項集算法[J].應(yīng)用科學學報，2019，37（3）：389-397.

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

[7]毛伊敏.數(shù)據(jù)流頻繁模式挖掘關(guān)鍵算法及其應(yīng)用研究[D].中南大學，2011.

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