水質時間序列模式挖掘

夏 達，李士進

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

0 引 言

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

序列模式挖掘由Agrawal和Srikant提出，主要用于在給定的數據集中搜索反復出現的模式。隨后，學者們陸續提出了多種序列模式挖掘算法[3-11]。文獻[12]研究了滿足One-Off條件的單序列模式挖掘問題，通過使用兩種不同的搜索方法計算其支持度并取較大值，提高了模式挖掘的完備性。文獻[13]結合了One-Off條件和通配符對單序列模式進行挖掘，并提出MAIL算法，算法同樣采用兩種策略結合計算模式支持度，有效提高了模式挖掘的效率及完備性。文獻[14]在MAIL算法的基礎上，提出了OFMI算法及I-OFMI算法，OFMI是一種快速的帶通配符和One-Off條件的序列模式挖掘算法，但同時它也不可避免地會遺失部分模式。為了解決OFMI算法缺失模式的問題，文獻[14]進一步提出了基于前向搜索和后向尋找解的模式支持度的計算方法I-OFMI,進一步提高了解的完備性。I-OFMI算法相較于OFMI算法提升了模式發現的完備性，但同時也不可避免地犧牲了模式發現的效率。盡管與傳統算法相比，OFMI和I-OFMI算法分別提升了模式挖掘的效率及完備性，但較完備算法其效率仍較差。

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

1 問題定義

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

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

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

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

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

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

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

定義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的連續子模式，P為Q的連續父模式。

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

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

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

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

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

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

FOFM算法的具體步驟如下：

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

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

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

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

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

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

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

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

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

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

以序列S=cccccbabbb為例，間隔約束設為[0,2]，最小支持度設為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)}符合支持度要求。

由于無法繼續連接形成新的模式，FOFM算法終止。

3 實驗結果與分析

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

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

圖1 不同支持度下模式個數及運行時間結果對比

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

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

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

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

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

4 結束語

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

參考文獻：

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

[2] 馬樂寬,王金南,王 東.國家水污染防治“十二五”戰略與政策框架[J].中國環境科學,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] 劉祥明.水質時間序列數據挖掘及其應用集成研究[D].重慶:重慶大學,2011.

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

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

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