夏 達，李士進

(河海大學 計算機與信息學院，江蘇 南京 210098)

0 引 言

水資源與人們的生產(chǎn)生活密切相關(guān)，水污染治理問題受到政府的高度重視[1-2]。隨著各地水質(zhì)監(jiān)測站點的建設(shè)及水質(zhì)監(jiān)測水平的提高，得到了大量的水質(zhì)時間序列，對這些序列進行相應(yīng)的序列模式挖掘研究，找出水質(zhì)時間序列中隱藏的模式，對當前水質(zhì)的保護及改善水資源環(huán)境研究相關(guān)水質(zhì)對策都有極其重要的意義。

序列模式挖掘由Agrawal和Srikant提出，主要用于在給定的數(shù)據(jù)集中搜索反復出現(xiàn)的模式。隨后，學者們陸續(xù)提出了多種序列模式挖掘算法[3-11]。文獻[12]研究了滿足One-Off條件的單序列模式挖掘問題，通過使用兩種不同的搜索方法計算其支持度并取較大值，提高了模式挖掘的完備性。文獻[13]結(jié)合了One-Off條件和通配符對單序列模式進行挖掘，并提出MAIL算法，算法同樣采用兩種策略結(jié)合計算模式支持度，有效提高了模式挖掘的效率及完備性。文獻[14]在MAIL算法的基礎(chǔ)上，提出了OFMI算法及I-OFMI算法，OFMI是一種快速的帶通配符和One-Off條件的序列模式挖掘算法，但同時它也不可避免地會遺失部分模式。為了解決OFMI算法缺失模式的問題，文獻[14]進一步提出了基于前向搜索和后向?qū)ふ医獾哪Ｊ街С侄鹊挠嬎惴椒↖-OFMI,進一步提高了解的完備性。I-OFMI算法相較于OFMI算法提升了模式發(fā)現(xiàn)的完備性，但同時也不可避免地犧牲了模式發(fā)現(xiàn)的效率。盡管與傳統(tǒng)算法相比，OFMI和I-OFMI算法分別提升了模式挖掘的效率及完備性，但較完備算法其效率仍較差。

水質(zhì)時間序列具有高維性、復雜性、動態(tài)性等特點[15]。水質(zhì)的變化不僅受多種環(huán)境因素的影響，如氣候變化、季節(jié)變化等[16-18]，一些突發(fā)事件如工廠違規(guī)排放污水、藍藻暴發(fā)等也會導致水質(zhì)急劇變化，這使得水質(zhì)時間序列還具有一定的隨機性[18]。目前相關(guān)算法應(yīng)用于水質(zhì)時間序列存在完備性較差或效率較差的問題。因此，為了提高模式挖掘的效率，文中設(shè)計了一種新的算法應(yīng)用于水質(zhì)時間序列，并通過實驗對其進行驗證。

1 問題定義

定義1：給定序列S=s1s2…sn,其序列長度為n，序列字符集記為Σ，代表序列中包含的所有不同字符，序列字符集長度記為|Σ|。例如序列：cccccbabbb，其序列長度為10，序列字符集為{a,b,c}，序列字符集長度為3。

定義2：通配符記為*，代表序列字符集中的任意字符。

定義3：間隔約束即通配符的個數(shù)范圍，最小間隔記為N，最大間隔記為M，M-N+1為間隔靈活度。

定義4：模式為序列字符集中的字符和通配符所組成的序列，記為P=p1p2…pm，其中pi(1≤i≤m)為通配符或字符，模式中通配符可以省略，即pi代表字符集中的字符，其中pi與pi-1(2≤i≤m)的位置需滿足相應(yīng)間隔約束。文中的模式均為省略了通配符的模式。

定義5：對于位置序列I=i1i2…im，1≤i1≤…≤im≤n，若滿足對于任意的k(1≤k≤m)使得sik=pk，則稱位置序列I為模式P在序列S中的一次出現(xiàn)。

定義6：One-Off條件即模式在序列中的任意兩次出現(xiàn)均滿足兩次出現(xiàn)的位置序列不共用相同的位置，例如bcbc，bc{(0,1)，(2,3)}滿足One-Off條件而bc{(0,1)，(0,3)}不滿足One-Off條件，因為兩次出現(xiàn)共用了位置0。

定義7：模式在序列中所有滿足One-Off條件的出現(xiàn)個數(shù)即為模式的支持度，若模式的支持度大于相應(yīng)的支持度閾值，則稱該模式為頻繁模式。

定義8：對于模式P=p1p2…pm，模式Q=q1q2…qt(t≤m)，如果存在1≤i1≤…≤it≤m滿足pik=qk(1≤k≤t)，則稱Q為P的子模式，P為Q的父模式。若該位置序列為一個公差為1的等差序列，則稱Q為P的連續(xù)子模式，P為Q的連續(xù)父模式。

定義9：對于模式P=p1p2…pm，模式Q=q1q2…qt(t

定義10：對于模式P=p1p2…pm，將pm在序列S中所有可能出現(xiàn)的位置序列記為模式P的尾序列。尾序列的大小即為pm在序列S中所有可能出現(xiàn)的位置個數(shù)。

定義11：對于模式P=p1p2…pm，模式Q=q1q2…qm，若對于任意的k(2≤k≤m)均滿足pk=qk-1，則稱模式P與模式Q是可連接的，其連接結(jié)果為p1q1q2…qm。將模式P的尾序列記為新模式的前序列，模式Q的尾序列記為新模式的后序列。

定理1：根據(jù)Apriori性質(zhì)，若模式P為頻繁模式，則P的所有非空連續(xù)子模式也一定是頻繁的，也即如果模式P為非頻繁模式，則P的所有連續(xù)父模式也一定是非頻繁的。

2 一種新的序列模式挖掘算法

文中提出的FOFM(fast one-offing mining)算法首先掃描序列獲得所有長度為1的頻繁模式集，并記錄每個1-項頻繁模式的尾序列，緊接著進行模式的連接過程。在由長度k-1的頻繁模式連接生成長度為k的候選模式集的過程中，由兩個符合可連接條件的長度為k-1的頻繁模式的尾序列進行連接，連接過程中只需考慮k-項模式的最后一個字符的可能位置即可，在完成連接后再從k-模式的最后可能位置序列通過反復提取其最大前綴模式的方法向1-模式回溯，回溯過程中遵循One-Off條件并采取右優(yōu)先策略直至計算完成k-模式的支持度。

FOFM算法的具體步驟如下：

(1)遍歷序列S，獲得序列S的字符集及字符集中每個字符對應(yīng)的位置序列，將結(jié)果存儲在相應(yīng)結(jié)構(gòu)中。

(2)檢查字符集中每個字符所對應(yīng)的位置序列的大小，去掉小于最小支持度的字符，使得每個字符為1-頻繁模式。

(3)遍歷當前長度的所有頻繁模式進行兩兩比較，將可連接的模式連接形成新的模式。

(4)根據(jù)已經(jīng)存儲的結(jié)果，獲得用于連接的兩個模式的位置序列，對兩個位置序列中的位置進行兩兩比較。如果間隔大于最大間隔，則繼續(xù)使用前序列中的下一個位置與后序列進行比較；如果間隔滿足間隔約束，則存儲該后序列中的當前位置并使用后序列的下一個位置繼續(xù)進行比較；如果間隔小于最小間隔，則使用后序列的下一個位置繼續(xù)進行比較，直到兩個序列中某一個遍歷完畢。

(5)獲得步驟4得到的新模式的尾序列后，如果新模式的尾序列的大小小于最小支持度，則說明新模式不是頻繁模式，去除該模式，否則檢查新模式的支持度，如果新模式的支持度滿足最小支持度，則存儲該模式及其尾序列。

(6)所有當前模式處理完畢后，將新的頻繁模式視為當前模式轉(zhuǎn)入步驟3進行處理，直至無法連接形成新的模式。

支持度檢查的具體步驟如下：

(1)從新模式的尾序列開始，從大到小選取一個未被標記的位置，記錄進標記數(shù)組。

(2)獲得當前模式的最大前綴模式的尾序列，從大到小與之前選取的位置比較，直到找到滿足間隔約束的未被標記位置，將該位置記錄進標記數(shù)組。

(3)將最大前綴模式設(shè)為當前模式，重復步驟2，直到無法獲得最大前綴模式，即模式長度為1。

以序列S=cccccbabbb為例，間隔約束設(shè)為[0,2]，最小支持度設(shè)為2。FOFM算法首先遍歷序列S獲得c{0,1,2,3,4}，b{5,7,8,9}，a{6}，很明顯模式a不符合最小支持度要求，去除模式a后，c和b都是1-頻繁模式。

對1-頻繁模式c和b連接形成bb{7,8,9}，bc{}，cb{5,7}，cc{1,2,3,4}，bc不符合最小支持度要求被刪除，對剩余模式bb，cb，cc檢查其支持度，bb存在{(8,9)，(5,7)}兩個位置序列符合要求，同理cb{(3,5)，(4,7)}，cc{(3,4)，(1,2)}符合要求，至此獲得2-頻繁模式bb，cb，cc。

對2-頻繁模式兩兩連接形成bbb{8,9}，cbb{8,9}，ccb{5,7}，ccc{2,3,4}，分別檢查支持度得bbb{(7,8,9)}，cbb{(4,7,9)，(3,5,8)}，ccb{(3,4,7)，(1,2,5)}，ccc{(2,3,4)}，通過檢查支持度刪除不符合要求的bbb和ccc。

對3-頻繁模式兩兩連接形成ccbb{8,9}，檢查支持度的ccbb{(3,4,7,9)，(1,2,5,8)}符合支持度要求。

由于無法繼續(xù)連接形成新的模式，F(xiàn)OFM算法終止。

3 實驗結(jié)果與分析

選取南京土橋，東臺梁一，鹽城新洋港3個水質(zhì)站點2007-2016年的水質(zhì)時間序列，序列1土橋長度為521，序列2梁一長度為511，序列3新洋港長度為509，使用算法OFMI、I-OFMI、FOFM進行挖掘。為充分比較算法，分別在不同支持度、不同通配符的長度下對3種算法的模式挖掘數(shù)量及算法的運行時間進行對比。

實驗一：min_sup分別設(shè)為6,8,10,12,1 416,18，間隔約束為[0,2]，結(jié)果如圖1所示。

圖1 不同支持度下模式個數(shù)及運行時間結(jié)果對比

通過實驗一可以發(fā)現(xiàn)，所有算法挖掘的模式個數(shù)和運行時間都隨著最小支持度的增加而減少，這其中OFMI算法挖掘的模式個數(shù)最少，其效率處于FOFM算法與I-OFMI算法之間。I-OFMI算法挖掘的模式較多但效率最差。文中提出的FOFM算法在不同支持度下運行速度都較快，F(xiàn)OFM算法挖掘的模式個數(shù)與I-OFMI算法的挖掘結(jié)果差距較小，如序列1在最小支持度為6的情況下，I-OFMI運行時間為14.7 s時，算法挖掘模式個數(shù)為843，而FOFM算法運行時間為2.1 s時，挖掘模式個數(shù)為826。相比OFMI算法，F(xiàn)OFM算法挖掘的模式個數(shù)比OFMI算法更多，運行時間卻更少。

實驗二：min_sup設(shè)為20，最小間隔為0，最大間隔長度分別為2,3,4,5,6,7,8，結(jié)果如圖2所示。

圖2 不同通配符長度下挖掘模式個數(shù)及運行時間結(jié)果對比

通過實驗二可以發(fā)現(xiàn)，所有算法挖掘的模式個數(shù)和運行時間都隨著通配符長度的增加而增加。I-OFMI算法挖掘的模式個數(shù)較多，但算法運行時間消耗巨大。FOFM算法在通配符長度較大時仍能保持一定的完備性，運行時間小于I-OFMI算法，如序列2在通配符長度為8時FOFM算法耗時7.6 s，I-OFMI算法耗時146.6 s。相比OFMI算法，F(xiàn)OFM算法挖掘的模式個數(shù)比OFMI算法更多，運行時間只有模式數(shù)量差距較大時才會大于OFMI算法，其他情況下均優(yōu)于OFMI算法。

通過以上實驗可以發(fā)現(xiàn)，F(xiàn)OFM算法的運行效率明顯優(yōu)于OFMI算法及I-OFMI算法，在通配符長度較小時，F(xiàn)OFM算法挖掘模式個數(shù)與I-OFMI算法差距較小，相比OFMI算法挖掘模式個數(shù)更多，這主要是因為FOFM算法在模式連接時選擇保留模式的尾序列，避免了重復掃描序列和列舉模式中事件的可能位置。

4 結(jié)束語

文中提出了一種新的帶間隔約束的序列模式挖掘算法FOFM，算法記錄了模式連接形成的候選模式最后事件的可能位置，并采用回溯策略掃描模式的前綴模式以檢查支持度。實驗結(jié)果表明，F(xiàn)OFM算法是一種快速的帶通配符和One-Off條件的單序列模式挖掘算法，可以有效地挖掘滿足One-Off條件的帶間隔約束的序列模式，在一定通配符長度下其時間效率較高，同時保證了較高的完備性。但由于FOFM算法僅從后向前選取事件，在通配符長度較大時算法的完備性較差，有待進一步完善。

參考文獻：

[1] 張 曉.中國水污染趨勢與治理制度[J].中國軟科學,2014(10):11-24.

[2] 馬樂寬,王金南,王 東.國家水污染防治“十二五”戰(zhàn)略與政策框架[J].中國環(huán)境科學,2013,33(2):377-383.

[3] PEI Jian,HAN Jiawei,MORTAZAVI-ASL B,et al.PrefixSpan:mining sequential patterns efficiently by prefix-projected pattern growth[C]//Proceedings of the 17th international conference on data engineering.[s.l.]:IEEE,2001:215-224.

[4] ZAKI M J.Sequence mining in categorical domains:incorporating constraints[M]//Proceedings of the ninth international conference on information and knowledge management.McLean,Virginia,USA:IEEE,2001:422-429.

[5] JI Xiaonan,BAILEY J,DONG Guozhu.Mining minimal distinguishing subsequence patterns with gap constraints[C]//Proceedings of the fifth IEEE international conference on data mining.[s.l.]:IEEE,2005:194-201.

[6] LI Chun,WANG Jianyong.Efficiently mining closed subsequences with gap constraints[C]//SIAM international conference on data mining.Atlanta,Georgia,USA:IEEE,2008:313-322.

[7] ZHANG Minghua,KAO Ben,CHEUNG D W,et al.Mining periodic patterns with gap requirement from sequences[J].ACM Transactions on Knowledge Discovery from Data,2007,1(2):7.

[8] ZHU Xingquan,WU Xindong.Mining complex patterns acro-ss sequences with gap requirements[C]//Proceedings of the 20th international joint conference on artificial intelligence.Hyderabad,India:Morgan Kaufmann Publishers Inc.,2007:2934-2940.

[9] KEMMAR A,LEBBAH Y,LOUDNI S,et al.Prefix-projection global constraint and top-k,approach for sequential pattern mining[J].Constraints,2017,22(2):265-306.

[10] HUYNH B,VO B,SNASEL V.An efficient method for mining frequent sequential patterns using multi-core processors[J].Applied Intelligence,2017,46(3):703-716.

[11] BANDARU S,NG A H C,DEB K.Data mining methods for knowledge discovery in multi-objective optimization:part B-new developments and applications[J].Expert Systems with Applications,2017,70:119-138.

[12] HE Yu,WU Xindong,ZHU Xingquan,et al.Mining frequent patterns with wildcards from biological sequences[C]//IEEE international conference on information reuse and integration.[s.l.]:IEEE,2007:329-334.

[13] XIE Fei,WU Xindong,HU Xuegang,et al.Sequential pattern mining with wildcards[C]//IEEE international conference on tools with artificial intelligence.Arras,France:IEEE,2010:241-247.

[14] 吳信東,謝 飛,黃詠明,等.帶通配符和One-Off條件的序列模式挖掘[J].軟件學報,2013,24(8):1804-1815.

[15] 劉祥明.水質(zhì)時間序列數(shù)據(jù)挖掘及其應(yīng)用集成研究[D].重慶:重慶大學,2011.

[16] 張永勇,花瑞祥,夏 瑞.氣候變化對淮河流域水量水質(zhì)影響分析[J].自然資源學報,2017,32(1):114-126.

[17] 方曉波,駱林平,李 松,等.錢塘江蘭溪段地表水質(zhì)季節(jié)變化特征及源解析[J].環(huán)境科學學報,2013,33(7):1980-1988.

[18] 梁中耀,劉 永,盛 虎,等.滇池水質(zhì)時間序列變化趨勢識別及特征分析[J].環(huán)境科學學報,2014,34(3):754-762.