水質(zhì)時(shí)間序列模式挖掘

夏 達(dá)，李士進(jìn)

(河海大學(xué) 計(jì)算機(jī)與信息學(xué)院，江蘇 南京 210098)

0 引 言

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

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

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

1 問(wèn)題定義

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

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

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

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

定義5：對(duì)于位置序列I=i1i2…im，1≤i1≤…≤im≤n，若滿足對(duì)于任意的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條件，因?yàn)閮纱纬霈F(xiàn)共用了位置0。

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

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

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

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

定義11：對(duì)于模式P=p1p2…pm，模式Q=q1q2…qm，若對(duì)于任意的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)算法首先掃描序列獲得所有長(zhǎng)度為1的頻繁模式集，并記錄每個(gè)1-項(xiàng)頻繁模式的尾序列，緊接著進(jìn)行模式的連接過(guò)程。在由長(zhǎng)度k-1的頻繁模式連接生成長(zhǎng)度為k的候選模式集的過(guò)程中，由兩個(gè)符合可連接條件的長(zhǎng)度為k-1的頻繁模式的尾序列進(jìn)行連接，連接過(guò)程中只需考慮k-項(xiàng)模式的最后一個(gè)字符的可能位置即可，在完成連接后再?gòu)膋-模式的最后可能位置序列通過(guò)反復(fù)提取其最大前綴模式的方法向1-模式回溯，回溯過(guò)程中遵循One-Off條件并采取右優(yōu)先策略直至計(jì)算完成k-模式的支持度。

FOFM算法的具體步驟如下：

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

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

(3)遍歷當(dāng)前長(zhǎng)度的所有頻繁模式進(jìn)行兩兩比較，將可連接的模式連接形成新的模式。

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

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

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

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

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

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

(3)將最大前綴模式設(shè)為當(dāng)前模式，重復(fù)步驟2，直到無(wú)法獲得最大前綴模式，即模式長(zhǎng)度為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-頻繁模式。

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

對(duì)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)}，通過(guò)檢查支持度刪除不符合要求的bbb和ccc。

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

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

3 實(shí)驗(yàn)結(jié)果與分析

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

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

圖1 不同支持度下模式個(gè)數(shù)及運(yùn)行時(shí)間結(jié)果對(duì)比

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

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

圖2 不同通配符長(zhǎng)度下挖掘模式個(gè)數(shù)及運(yùn)行時(shí)間結(jié)果對(duì)比

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

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

4 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

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

[2] 馬樂(lè)寬,王金南,王 東.國(guó)家水污染防治“十二五”戰(zhàn)略與政策框架[J].中國(guó)環(huán)境科學(xué),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].軟件學(xué)報(bào),2013,24(8):1804-1815.

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

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

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

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