吳丹　劉賀

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

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

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

中圖分類號(hào)：TP18;O157.5文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：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)境中的頻繁項(xiàng)集挖掘概述

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

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

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

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

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

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

③Pattern-tree的更新。

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

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

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

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

核心步驟如下：

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

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

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

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

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

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

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

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

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

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

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

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

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

CFMoment算法對(duì)CET樹更新的改進(jìn)之處：

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

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

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

基本思想如下：

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

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

③位頻繁模式樹的建立

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

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

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

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

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

2結(jié)語

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

參考文獻(xiàn)：

[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].西安科技大學(xué)，2010.

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

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

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

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