◆仝 瑤

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

增量序列模式挖掘研究進(jìn)展

◆仝 瑤

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

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

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

0 前言

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

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

（1）插入新的序列;

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

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

1 基于Apriori的算法

早期的序列模式挖掘算法都廣泛地應(yīng)用了Apriori性質(zhì)。基于Apriori特性的算法可以根據(jù)數(shù)據(jù)庫(kù)類(lèi)型被劃分為兩類(lèi):水平格式算法和垂直格式算法。水平數(shù)據(jù)庫(kù)的每條記錄由一個(gè)序列標(biāo)識(shí)符和序列組成; 垂直數(shù)據(jù)庫(kù)的每條記錄由一個(gè)序列標(biāo)識(shí)符、一個(gè)項(xiàng)集標(biāo)識(shí)符和項(xiàng)集組成。水平數(shù)據(jù)庫(kù)和垂直數(shù)據(jù)庫(kù)之間可以相互轉(zhuǎn)換。

1.1 水平格式挖掘算法

1.1.1 ISE算法

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

ISE是一種迭代算法。首先遍歷數(shù)據(jù)庫(kù)的增量部分db，計(jì)算所有至少出現(xiàn)一次的項(xiàng)集的支持度。結(jié)合之前原始數(shù)據(jù)庫(kù)DB的項(xiàng)集，可以得知哪些項(xiàng)集在U（DB∪db）上是頻繁的，稱(chēng)之為L(zhǎng)1db?？梢栽诖嘶A(chǔ)上生成新的頻繁序列:1.將L1db加入到DB的頻繁序列中; 2.DB中的頻繁子序列可以作為L(zhǎng)1db的前綴生成長(zhǎng)度為2的候選序列; 3.遍歷數(shù)據(jù)庫(kù)從2-候選序列根據(jù)支持度閾值的判定方法得到 2-頻繁序列。一直迭代這個(gè)過(guò)程直到?jīng)]有候選集產(chǎn)生。

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

1.1.2 IUS算法

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

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

1.2 垂直格式挖掘算法

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

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

2 基于投影的算法

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

2.1 IncSpan算法

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

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

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

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

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

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

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

2.2 IIMSP算法

IIMSP算法是由Liu等人[8]提出的一種基于頻繁序列樹(shù)的增量挖掘算法。頻繁序列樹(shù)是一種序列存儲(chǔ)結(jié)構(gòu)，存儲(chǔ)滿(mǎn)足頻繁序列樹(shù)支持度閾值tree_sup的所有序列模式及其支持度。

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

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

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

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

2.3 PBIncSM算法

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

PBIncSM算法利用了PrefixSpan的前綴樹(shù)結(jié)構(gòu)，前綴樹(shù)每條路徑表示一個(gè)序列模式，并且每個(gè)結(jié)點(diǎn)都存儲(chǔ)了對(duì)應(yīng)的投影數(shù)據(jù)庫(kù)，每個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)都通過(guò)掃描投影數(shù)據(jù)庫(kù)得到。該算法提出了兩種剪枝方法，廣度剪枝和深度剪枝，并且給出了相關(guān)證明。

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

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

3 總結(jié)

序列模式挖掘早期的工作主要集中在利用新的數(shù)據(jù)結(jié)構(gòu)或這在主存管理數(shù)據(jù)庫(kù)來(lái)提高算法的效率。由于數(shù)據(jù)庫(kù)的更新，先前挖掘出來(lái)的模式有可能會(huì)失效，并且可能產(chǎn)生新的模式。因此ISPM得到了廣泛的研究，因?yàn)樗靡呀?jīng)被發(fā)現(xiàn)的知識(shí)來(lái)解決動(dòng)態(tài)更新數(shù)據(jù)庫(kù)的維護(hù)問(wèn)題，而不用重新開(kāi)始挖掘。本文詳細(xì)介紹了基于Apriori和基于投影兩大類(lèi)增量模式挖掘算法。目前的多數(shù)增量算法都只考慮了更新的數(shù)據(jù)，沒(méi)有考慮先前的挖掘數(shù)據(jù)可能會(huì)過(guò)時(shí)的問(wèn)題，這也是增量序列挖掘的一個(gè)新的研究趨勢(shì)。

[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].計(jì)算機(jī)工程，2012.

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