增量序列模式挖掘研究進展

◆仝 瑤

（河北工業(yè)大學計算機科學與軟件學院 天津 300130）

增量序列模式挖掘研究進展

◆仝 瑤

（河北工業(yè)大學計算機科學與軟件學院 天津 300130）

序列模式挖掘是數(shù)據(jù)挖掘領域的一個重要研究分支，近年來在諸多領域得到了廣泛地應用。由于現(xiàn)實應用中序列數(shù)據(jù)庫是不斷地更新的，僅采用靜態(tài)數(shù)據(jù)的序列模式挖掘方法，不僅效率低下，而且是對先前的挖掘結果的極大浪費。有鑒于此，提出的增量序列模式挖掘算法能夠適應數(shù)據(jù)庫的動態(tài)性。本文總結近幾年來增量模式挖掘取得的重大成果和進展，特別分析研究了其中幾個經典算法，最后對增量序列模式挖掘發(fā)展趨勢進行了展望。

增量序列模式挖掘; Apriori; 投影數(shù)據(jù)庫

0 前言

序列模式挖掘是數(shù)據(jù)挖掘的一個重要研究領域，最初是由Agrawal和Srikant[1]兩名研究者為了研究用戶多次購買行為之間的關系提出的。序列模式挖掘是是指從序列數(shù)據(jù)庫中尋找出現(xiàn)頻率高的子序列的過程。它具有廣闊應用領域，如客戶購物交易分析、DNA序列破譯、Web訪問分析等等。

目前的序列模式挖掘算法都是基于靜態(tài)的數(shù)據(jù)庫進行挖掘，但在許多實際應用中，序列數(shù)據(jù)庫是增量更新的，已有的挖掘結果或規(guī)則可能不再有效。為了提高挖掘效率，一般通過增量式序列模式挖掘算法（ISPM）對數(shù)據(jù)庫中新增數(shù)據(jù)序列進行挖掘。例如，由于老顧客添加新購買的物品，或者插入新客戶購物的新序列，顧客購物交易數(shù)據(jù)庫會日益增長。在應用中存在兩種數(shù)據(jù)庫更新:

（1）插入新的序列;

（2）在已存在的序列后追加新的序列。

由于原始數(shù)據(jù)庫的更新，一些現(xiàn)有的模式可能成為無效的，因為更新可能會使最小支持度變得不充分。也有可能會產生新的頻繁模式。增量序列模式挖掘需要處理在數(shù)據(jù)庫更新的情況下，不需要重新挖掘數(shù)據(jù)庫，充分利用上一次的挖掘結果進行挖掘。下面我們將重點介紹幾種增量模式挖掘。

1 基于Apriori的算法

早期的序列模式挖掘算法都廣泛地應用了Apriori性質。基于Apriori特性的算法可以根據(jù)數(shù)據(jù)庫類型被劃分為兩類:水平格式算法和垂直格式算法。水平數(shù)據(jù)庫的每條記錄由一個序列標識符和序列組成; 垂直數(shù)據(jù)庫的每條記錄由一個序列標識符、一個項集標識符和項集組成。水平數(shù)據(jù)庫和垂直數(shù)據(jù)庫之間可以相互轉換。

1.1 水平格式挖掘算法

1.1.1 ISE算法

Masseglia等人提出了一種增量挖掘算法ISE[2]，可用于計算當原始交易數(shù)據(jù)庫增加新的交易和新的客戶時的頻繁序列。它通過把增量數(shù)據(jù)庫中的序列和原始數(shù)據(jù)庫中的序列進行連接產生整個數(shù)據(jù)庫的候選序列。因此當原始數(shù)據(jù)庫中的數(shù)據(jù)被更新時不需要重新計算這些序列。

ISE是一種迭代算法。首先遍歷數(shù)據(jù)庫的增量部分db，計算所有至少出現(xiàn)一次的項集的支持度。結合之前原始數(shù)據(jù)庫DB的項集，可以得知哪些項集在U（DB∪db）上是頻繁的，稱之為L1db。可以在此基礎上生成新的頻繁序列:1.將L1db加入到DB的頻繁序列中; 2.DB中的頻繁子序列可以作為L1db的前綴生成長度為2的候選序列; 3.遍歷數(shù)據(jù)庫從2-候選序列根據(jù)支持度閾值的判定方法得到 2-頻繁序列。一直迭代這個過程直到沒有候選集產生。

ISE算法的優(yōu)勢是內存消耗小，不用額外的空間存儲潛在的頻繁模式，但還是有一些限制，首先會產生大量的候選集，使得挖掘速度慢; 其次層次明確的計算方式需要對整個數(shù)據(jù)庫進行多次掃描，當序列很長的時候這是非常耗費時間的。

1.1.2 IUS算法

IUS算法[3]的主要思想是,通過重用原始數(shù)據(jù)庫中的負邊界序列和頻繁序列使計算開銷達到最小。算法中除了最小支持度min _sup外,還定義了一個新的支持度——負邊界序列最小支持度，用min_nbd_sup表示。只有支持度在min_sup和min_nbd_sup之間的序列才能加入負邊界序列集中。通過調整min_nbd_sup的值，我們可以去掉負邊界序列中那些支持度很小，對計算結果影響較小的序列，從而節(jié)約了負邊界序列所消耗的內存空間。

IUS算法分為兩個部分，第一部分將原始數(shù)據(jù)庫和新增數(shù)據(jù)庫中的頻繁序列和負邊界序列作為候選序列，將其中符合條件的部分插入到更新后數(shù)據(jù)庫的頻繁序列集和負邊界序列集中。第二部分將用這兩種方法產生新的負邊界序列集，作為下一次循環(huán)的候選序列，并重新計算這些候選序列在更新后數(shù)據(jù)庫中的支持集。

1.2 垂直格式挖掘算法

Parthasarathy等人提出了一個基于SPADE算法的增量挖掘算法ISM[4]。為了達到降低重新計算和重新掃描數(shù)據(jù)庫的要求，ISM 使用垂直數(shù)據(jù)的存儲方式，建立了一個增量序列格（IS L），序列格由原始數(shù)據(jù)庫中所有頻繁序列（FS）和負邊界（NB）內的所有序列和組成。FS表示在更新數(shù)據(jù)庫中的所有頻繁序列集; 負邊界是由非頻繁序列但是其最大的兩個子序列是頻繁的所有序列組成的集合。同時序列格也存儲了子序列的支持度。

ISM算法的優(yōu)點是顯而易見的，只需要掃描一次數(shù)據(jù)庫的新增部分，而不用重新掃描整個數(shù)據(jù)庫，與其他大多數(shù)序列模式挖掘算法相比在速度上有很大提升。但是ISM需要維護否定邊界，如果序列數(shù)據(jù)庫非常龐大，那么否定邊界也會相應增大，這將會增加存儲成本。另外ISM 算法僅考慮數(shù)據(jù)庫增加新序列的情況。

2 基于投影的算法

Apriori 算法由于會產生大量的候選集并且需要多次掃描數(shù)據(jù)庫，因此在挖掘長序列模式方面效率很低。為了克服這些缺點，Pei等人提出了一種投影算法PrefixSpan[5]，該算法采用完全不同的挖掘策略，通過對頻繁前綴投影，產生頻繁后綴項，進而連接產生新的模式?；谕队八惴ǖ膬?yōu)勢在于僅掃描原始數(shù)據(jù)庫兩次，并且通過分而治之的思想，把數(shù)據(jù)庫投影縮減成更小的數(shù)據(jù)庫。每次迭代挖掘都限定在投影后的更小的數(shù)據(jù)庫中，節(jié)省了運行時間。

2.1 IncSpan算法

Cheng等人[6]提出一種基于PrefixSpan算法的增量式挖掘算法IncSpan，該算法提出了半頻繁序列的概念，半頻繁模式不是頻繁模式，但是卻在更新的數(shù)據(jù)庫中有可能成為頻繁模式。在挖掘原始數(shù)據(jù)庫時，將頻繁序列和半頻繁序列放入緩存中。在挖掘更新數(shù)據(jù)庫時只計算在緩存中的序列的支持度。另外該算法引入兩個優(yōu)化方法，反轉模式匹配和共享投影。反向模式匹配可以匹配一個序列中的序列模式，縮小搜索空間。共享投影用于降低數(shù)據(jù)庫投影的占用的空間。

該算法利用最小支持閾值min_sup和因素μ將模式劃分成三類:

頻繁的序列:其支持度不小于min_sup;

半頻繁的序列:其支持度小于min_sup且不小于μ*min_sup;

不頻繁的序列:其支持度小于μ*min_sup。

本算法提出了一條重要理論:對于頻繁模式p滿足supLDB（p）〈（1-μ）*min_sup,那么就不存在由p作為前綴的序列p’，使p’從在D中不頻繁變?yōu)樵贒’中頻繁（LDB是更新后的數(shù)據(jù)庫）。

Nguyen等人[7]發(fā)現(xiàn)IncSpan算法不能找出完備的序列模式，提出了IncSpan+算法，該算法延用了IncSpan的半頻繁模式和剪枝策略，修正了IncSpan在生成頻繁模式集和半頻繁模式集上的一些錯誤。

2.2 IIMSP算法

IIMSP算法是由Liu等人[8]提出的一種基于頻繁序列樹的增量挖掘算法。頻繁序列樹是一種序列存儲結構，存儲滿足頻繁序列樹支持度閾值tree_sup的所有序列模式及其支持度。

IIMSP算法在第一次挖掘過程中，把所有滿足tree_sup的序列模式及其支持度存儲在頻繁序列樹中。當數(shù)據(jù)發(fā)生變化時，II MSP算法分兩種情況對頻繁序列樹進行更新。

（1）如果最小支持度min_sup大于等于頻繁序列樹的支持度閾值tree_sup,IIMSP只需要遍歷頻繁序列樹就能得到所有序列模式;

（2）如果最小支持度小于頻繁序列樹的支持度閾值，IIMSP需要對原有數(shù)據(jù)庫構造投影數(shù)據(jù)庫，并找到滿足支持度的所有序列模式，實現(xiàn)頻繁序列樹的更新操作。

頻繁序列樹的結構特點使IIMSP算法能夠充分利用先前挖掘的結果，當數(shù)據(jù)庫發(fā)生變化時，IIMSP算法不需要對原始數(shù)據(jù)庫構造投影數(shù)據(jù)庫，只需對與增量數(shù)據(jù)庫相關的序列構造投影數(shù)據(jù)庫，大大減小了投影數(shù)據(jù)庫的規(guī)模。

2.3 PBIncSM算法

PBIncSM算法[9]是由Zhang等人提出的一種基于前綴樹的增量序列挖掘算法。該算法和IncSpan算法一樣，都是基于投影的算法。IncSpan和IncSpan+雖然在半頻繁模式轉化成頻繁模式中節(jié)省了時間，但由于算法要保證可持續(xù)性，因此還需要維護半頻繁模式。半頻繁模式的維護難度不低于頻繁模式的維護難度，利用半頻繁模式來挖掘序列模式不能提高效率。

PBIncSM算法利用了PrefixSpan的前綴樹結構，前綴樹每條路徑表示一個序列模式，并且每個結點都存儲了對應的投影數(shù)據(jù)庫，每個結點的子結點都通過掃描投影數(shù)據(jù)庫得到。該算法提出了兩種剪枝方法，廣度剪枝和深度剪枝，并且給出了相關證明。

廣度剪枝:如果某結點的投影數(shù)據(jù)庫保持不變,可進行剪枝。

深度剪枝:假定p結點的父節(jié)點在掃描過程中未引入新的節(jié)點，且p的增量元素集與p及其兄弟結點的交集為空，則D’的p及其子樹保持不變。

3 總結

序列模式挖掘早期的工作主要集中在利用新的數(shù)據(jù)結構或這在主存管理數(shù)據(jù)庫來提高算法的效率。由于數(shù)據(jù)庫的更新，先前挖掘出來的模式有可能會失效，并且可能產生新的模式。因此ISPM得到了廣泛的研究，因為它利用已經被發(fā)現(xiàn)的知識來解決動態(tài)更新數(shù)據(jù)庫的維護問題，而不用重新開始挖掘。本文詳細介紹了基于Apriori和基于投影兩大類增量模式挖掘算法。目前的多數(shù)增量算法都只考慮了更新的數(shù)據(jù)，沒有考慮先前的挖掘數(shù)據(jù)可能會過時的問題，這也是增量序列挖掘的一個新的研究趨勢。

[1]Agrawal R，Srikant R.Mining sequential patterns[C].In: Proceedings of the 11th International Conference on Data En gineering.Taipei,Taiwan,1995.

[2]Masseglia F,Poncelet P,Teisseire M.Incremental mining of sequential patterns in large databases[J].Data and Knowledge Engineering,2003.

[3]Zheng Q,Xu K,Ma S,et al.The algorithms of updating sequential patterns[C].In:Proceedings of 5th International Wor kshop on High Performance Data Mining（HPDM），in Conj unction with 2nd SIAM Conference on Data Mining USA,20 02.

[3]Parthasarathy S,Zaki M,Ogihara M,et al.Incremental an d interactive sequence mining[J].In:Proceedings of the 8th Inte rnational Conference on Information and Knowledge Manage ment,Kansas City,MO,USA,1999.

[4]Pei J,Han J,Mortazavi-Asl B.PrefixSpan:Mining Sequent ial Patterns Efficiently by Prefix-Projected Pattern Growth[C]. In:Proceedings of International Conference on Data Engineerin g，Heidelberg,Germany,2001.

[5]Cheng H,Yan X,Han J.IncSpan:Incremental mining of sequential patterns in large database[C].In:Proceedings of the te nth ACM SIGKDD international conference on Knowledge di scovery and data mining,Seattle,WA,USA,2004.

[6]Nguyen SN,Sun X,Orlowska ME.Improvements of Inc Span:Incremental mining of sequential patterns in large databas e[C].In:Proceedings of the 9th Pacific-Asia Conference on Kn owledge Discovery and Data Mining,Heidelberg,SpringerVerlag, 2005.

[7]劉佳新.一種高效的增量式序列模式挖掘算法[J].計算機工程，2012.

[8]張坤，陳越，朱楊勇.一種基于前綴樹的增量序列挖掘算法[J].計算機工程，2007.