基于PrefixSpan序列模式挖掘的改進算法

王 斌 黃曉芳 袁 平

(西南科技大學計算機學院 四川綿陽 621000)

基于PrefixSpan序列模式挖掘的改進算法

王 斌 黃曉芳 袁 平

(西南科技大學計算機學院 四川綿陽 621000)

針對PrefixSpan算法在構建投影數據庫時時間開銷過多和隨著支持度增加效率下降的問題，提出了一種基于PrefixSpan算法的改進算法AP(AprioriAll-PrefixSpan)，該算法可以減少構建投影數據庫的時間開銷和降低支持度增加對算法效率的影響。改進思想是在第一次劃分生成投影數據庫時，按投影數據庫中項集的個數從小到大排序，在第二次劃分的時候 ，從已挖掘序列模式中直接生成所需序列模式，從而減少數據庫的構建。實驗結果顯示AP 算法效率高于PrefixSpan算法。

PrefixSpan 序列模式 投影數據庫 生成序列 二次劃分

序列模式挖掘是挖掘頻繁出現的有序事件或子序列[1]。由于序列模式挖掘對先驗知識的依賴較少，可以發現未知的規律，所以得到了廣泛的應用。比如：網絡安全中的異常行為發現[2]、生物工程[3]、DNA序列分析[4]、網絡訪問模式分析[5]、用戶社交行為分析[6]等。

序列模式挖掘最先由Agrawal和Srikant在文獻[7]中提出，論文主要介紹了3種基于Apriori算法框架的AprioriAll，AprioriSome和DynamicSome算法，隨后提出了一種基于泛化GSP[8]算法。文獻[9]提出了一種基于垂直數據格式的SPADE 算法。以上算法都會產生大量的候選集。而文獻[10]提出的FreeSpan算法，是基于序列模式的增長，不產生候選集。文獻[11]的PrefixsSpan算法是對FreeSpan算法的改進，減少了投影數據庫和子序列連接次數，數據庫收斂更快，算法效率比之前的算法效率都高。

PrefixSpan算法[11]是根據前綴生成對應的投影數據庫，然后對投影數據庫進行掃描，避免了對整個數據庫進行掃描，從而減少了掃描時間。算法的主要時間開銷在構建投影數據庫，且在隨著支持度增加的時候，效率會降低。由于支持度的提高，導致投影數據庫的收斂度減少。文獻[12]對構建數據庫改進，但對數據形式要求過高。文獻[13]對內存存儲改進，當支持度增加時，效率下降。本文基于PrefixSpan算法提出了一種AP(ApriopriAll-PreFixSpan)算法。算法思想是直接從已挖掘序列模式中生成所需序列模式，減少投影數據庫的構建。隨著已挖掘序列越多，挖掘的速度會越快，且對數據形式沒特別要求。算法結合了AprioriAll算法[2]的優點，減少了支持度增加對效率的影響。

1 AP算法研究與實現

1.1 相關概念

設length-1表示數據庫S中第一次掃描數據庫，得到序列模式，Length-2表示掃描以length-1中任一序列模式劃分的投影數據庫，得到序列模式。如length-2 可以是掃描第一次以為前綴劃分的投影數據庫，產生的序列模式，也可以是掃描第一次以為前綴劃分的投影數據庫，產生的序列模式。本文采用數據庫如表1所示。

表1 數據庫Table 1 Database

定理1 設數據庫S中有序列模式，以length-1為前綴劃分產生的序列模式集設為β，以length-2為前綴劃分得到的序列模式集設為a，那么有a?β。

證明：由于數據庫S中以length-1為前綴的投影數據庫是第一次掃描數據庫所得，即數據庫S中所有包含的序列組成的序列數據庫，為含有項的最大序列數據庫集。而length-2中以為前綴的投影數據庫是第一次劃分后的投影數據庫的投影數據庫，所以是包含于S數據庫中最大序列數據庫中的。數據庫決定了序列模式集，所以有a?β。以表1為數據庫，描述一個例子如表2。

表2 投影數據庫Table 2 Projection database

從表2可知投影數據庫是包含于的投影數據庫。

本文基于AprioriAll算法中驗證候選集，并結合PrefixSpan算法產生序列的特點，提出了一種YZ方法。該方法思路：如果已知以一個序列模式為前綴的序列模式集為β以及對應投影數據庫S|a， 以序列模式集β中的序列模式為候選集，掃描投影數據庫S|a，驗證候選集中各序列模式的個數是否大于支持度來產生序列模式的序列模式集。由PrefixSpan產生序列模式的特點可以知道，如果一個序列不滿足支持度，則以該序列為前綴的序列都不滿足。所以在驗證候選集時, 如果一個序列不滿足支持度，那么以該序列為前綴的序列就不用驗證。

定理2 設數據庫S中有一個序列模式和對應投影數據庫S|a，以為前綴的序列模式集為β。如果已知序列模式集β，從投影數據庫S|a中采用YZ方法得到β的時間是小于用PrefixSpan算法在數據庫S|a得到序列模式集β。PrefixSpan算法開銷在于構造投影數據庫，而YZ方法不需要構建投影數據庫，所以效率比PrefixSpan高。且降低了支持度增加對算法效率的影響，由于YZ方法對數據庫的收斂依賴沒有PrefixSpan高。實驗 1證明了這個結論。

1.2 AP算法描述

(1) 同PrefixSpan算法，掃描數據庫得到長度為1的序列模式，然后分別以length-1為前綴劃分，再以length-1得到的投影數據庫排序，按投影數據庫中項集的個數，從小到大排序。

(2) 從最小的投影數據庫開始挖掘，掃描投影數據庫得到對應length-2 序列模式，后以length-2為前綴劃分，此時掃描結果數據集，判斷以該序列為前綴的length-1是否挖掘，如果已挖掘直接從length-1序列集用YZ方法產生所需序列模式。如果沒有同PrefixSpan算法。求以length-2為前綴的序列模式集時，由定理1知道length-2 為前綴的序列模式集是包含于length-1為前綴的序列模式集，所以可以直接從length-1采用YZ方法中產生。由定理2知，從length-1中生成序列的時間少于用PrefixSpan算法。由于PrefixSpan產生的序列模式是根據序列遞增的，如,,，此時用YZ方法時，可以先計算是否為其序列模式，如果是，再繼續驗證序列，如果不是，那么,也不是其序列模式。由于length-1集是大于等于length-2的，所以YZ方法的目的是去掉不屬于length-2的序列模式。YZ方法可以有效減少無效候選集的影響，為了提高算法的效率，應避免length-2集比length-1集過大。

算法偽代碼：

輸入：序列數據庫S和最小支持度min_sup；

輸出：所有序列模式；

函數：AP(<>,S)；

功能：第一次掃描數據庫S，產生length-1序列模式和對應投影數據庫。

函數：AP(a,S|a)；

功能：l(l≥2)次以上掃描數據庫，產生length-l序列模式和對應投影數據庫。

函數：AP(b,β,S|b)；

功能：從序列模式集β中，采用YZ方法，生成以為劃分的序列模式集。

參數：a為一個序列模式，L為序列模式的長度，如果L長度為1，數據庫為S，否則為S|a，b為一序列模式，S|b為以 為前綴的投影數據庫，β為以length-1為前綴的序列模式集。

(1)調用AP(<>,S|a)，得到length-1序列模式，對投影數據庫按項集個數從小到大排序。

(2)調用AP(a,S|a)生成對應的length-2序列模式。

(3)判斷以length-2為前綴是否已經挖掘，如果沒有挖掘，循環調用AP(a,S|a)挖掘，直到沒有頻繁項，如果已挖掘，調用AP(b,β,S|b)，從已挖掘的序列模式中產生所需模式。

(4)轉到第2步。

1.3 以表1為數據庫，描述算法過程

(1)掃描數據庫S，得到length-1的序列模式，分別是:4,:4,:4,:3,:3,:3。

(2)以第一步的序列模式為前綴劃分得到6個投影數據庫，分別是,,,,,，對6個投影數據庫按項集的個數從小到大排序。

(3)從小的投影數據庫開始挖掘。當挖掘以為前綴時，掃描的投影數據庫得到頻繁項有:2,:4,:4,:3,:3，然后分別以頻繁項為前綴劃分得到對應投影數據庫，當求前綴為的時候，查看以length-1 前綴已挖掘，采用YZ方法，直接從length-1中生成序列模式。表3給出了前綴的例子。

2 實驗分析

2.1 實驗一 對定理2的分析

該實驗采用CPU為2.1 GHZ，4 G內存，window7操作系統，算法代碼采用java編寫，實驗測試數據采用 IBM Quest Synthetic Data Generator 生成(產生數據同文獻[7])，對數據集C10T3S4I1.25進行測試，測試數據集的有關參數：|D|表示顧客數設為100；|N|表示總項數，設為3 000；其他的按默認設置。分別取支持度為3%，4%，5%，6%，7%，8%，9%，10%，11%，測試YZ方法和PrefixSpan方法。

圖1 表示PrefixSpan所用時間比YZ方法所用時間隨支持度變化， 從圖1知PrefixSpan方法所用時間與YZ算法所用時間之比隨支持度增加而增加。在10%后曲線下降，序列模式的數量減少了，雖然單個模式時間提高更多，但是整體時間提高減慢。

表3 二次投影數據庫Table 3 Two-time projection database

圖1 時間比隨支持度變化Fig.1 Time ratio diagram with change of support

圖2表示PrefixSpan所用時間比YZ所用時間隨所占該項序列的變化，從圖2可以看到對于單個模式，隨占該序列總數比例增加，PrefixSpan所用時間與YZ所用時間比增加。

圖2 時間比隨所占比例變化Fig.2 Time ratio diagram with change of occupation

實驗結果顯示YZ方法優于PrefixSpan方法，定理2是成立的。

2.2 實驗二 AP算法和PrefixSpan算法對比

實驗環境和測試數據集同實驗一，在對測試數據集分別取支持度為3%，4%，5%，6%，7%，8%，9%，10%，11%。實驗結果如圖3，從圖3可以看出支持度在4%到8%之間的時候AP算法明顯優于PrefixSpan算法。實驗一顯示隨支持度增加，YZ方法所用時間與PrefixSpan所用時間之比是越來越小，而圖3顯示在支持度超過8%以后，PrefixSpan算法和AP算法所用時間差距在減少。主要由于隨支持度的增加，序列模式的數量減少，算法所用的總時間在減少，兩個算法之間的時間差距相應的就變小了。由實驗結果知，YZ方法明顯優于PrefixSpan算法。

圖3 所用時間對比Fig.3 Comparison of time consumed

3 結束語

本文在研究PrefixSpan算法的基礎上，研究了PrefixSpan算法的開銷主要在于構建子數據庫，同時也研究了AprioriAll算法思想，AprioriAll算法在驗證候選集是高效的。本文基于PrefixSpan算法生成的序列自身特點改進了該驗證方法，提高了PrefixSpan算法，也降低了隨支持度增加對算法效率的影響。AP算法對顧客數量過大的網絡數據挖掘效率不高。下一步主要研究PrefixSpan算法在網絡安全中的具體應用，期望PrefixSpan算法能夠自動發現網絡攻擊。

[1] HAN J,KAMBER M. 數據挖掘概念與技術[M]. 北京: 機械工業出版社，2012.

[2] 李錦玲,汪斌強.基于最大頻繁序列模式挖掘的App-DDoS攻擊的異常檢測[J]. 電子與信息學報, 2013,35(7):1739-1745.

[3] 朱揚勇,熊贊. DNA序列數據挖掘技術[J]. 軟件學報,2007,18(11):2767-2781.

[4] 楊恒宇.生物序列數據挖掘技術研究[J]. 合肥工業大學學報(自然科學版),2012,35(9):1212-1216.

[5] 龔衛華,郭偉鵬,楊良懷. 信任網絡中多維信任序列模式挖掘方法研究[J].電子與信息學報,2014,36(8):1810-1816.

[6] 丁振國,宋薇,李婧. 基于序列模式挖掘的社交網絡用戶行為分析[J]. 現代情報, 2013,33(3):56-65.

[7] AGRAWAL R，SRIKANT R． Mining sequential patterns [C]．Proceedings of the 11thInternational Conference on DataEngineering． CA: Los Alamitos，IEEE Computer Society，1995: 3-14

[8] SRIKANT R，AGRAWAL R.Mining sequential pattems: generali-zations and performance improvements [C]． EDBT 96:Proceedings of the 5th International Conference on Exten-ding Database Technology: Advances in Database Technol-ogy． UK，London: Springer-Verlag， 1996: 3-17．

[9] ZAKI M． SPADE: An efficient algorithm for mining fre-quent sequences[J]． Macheine Learning，2001，42(1): 31-60．

[10] HAN J，PEI J，MORTAZAVIASL B，et al． FreeSpan: Frequentpattern-projected sequential pattern mining [C]． Proceed-ings of the 6thACM SIGKDD International Conference on,Knowledge Discovery and Data Mining． USA，New York:ACM，2000: 355-359．

[11] PEI J，HAN J，MORTAZAVIASL B，et al． Mining sequentialpatterns by pattern-growth: the prefixspan approach[J]．IEEE Transactions on Knowledge and Data Engineering，2004，16( 11) : 1424-1440．

[12] 公偉,劉培玉,賈嫻.基于改進 Prefixspan的序列模式挖掘算法[J].計算機應用,2011,31 (9) : 2405-2407.

[13] 張巍,劉峰,滕少華.改進的 PrefixSpan算法及其在序列模式挖掘中的應用[J].廣東工業大學學報,2013 ,30(4):49-54.

Improved Algorithm Based on PrefixSpan Sequence Pattern

WANG Bin, HUANG Xiaofang, YUAN Pin

(SchoolofComputerScienceandTechnology,SouthwestUniversityofScienceandTechnology,Mianyang621010,Sichuan,China)

In the construction of projection database, the time consumed is too much and the efficiency of the PrefixSpan algorithm is decreased with the degree of support reduced. An improved AP (AprioriAll-PrefixSpan) algorithm based on PrefixSpan algorithm is proposed in this paper. This new algorithm can reduce the impact caused by the time consumed for building the projection database and the reduced degree of support. During the first time of dividing the projection database, the item sets were ranked in an ascending order. During the second time of dividing the projection database, the sequence pattern was generated automatically from the already obtained database, so as to reduce the database construction. Experimental results show that the efficiency of AP algorithm is higher than that of PrefixSpan algorithm.

PrefixSpan; Sequence pattern; Projection database; Sequence generation; Two-time division

2016-09-05

國家自然科學基金資助項目(61303230)。

王斌(1989—)，男，碩士研究生，研究方向為網絡安全中數據挖掘，E-mail:2781993753@qq.com

TP311.13

A

1671-8755(2016)04-0068-05