基于FCM聚類的時(shí)間序列模糊關(guān)聯(lián)規(guī)則挖掘

呂 志 軍， 王 照 飛， 謝 福 鼎， 桑 雪

（1.大連理工大學(xué) 管理學(xué)院，遼寧 大連 116024；2.遼寧師范大學(xué) 計(jì)算機(jī)信息與技術(shù)學(xué)院，遼寧 大連 116081；3.大連理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，遼寧 大連 116024）

0 引 言

時(shí)間序列是按照時(shí)間順序取得的一系列觀察值，它經(jīng)常出現(xiàn)在諸如經(jīng)濟(jì)、商業(yè)、工程等領(lǐng)域中.生活中時(shí)間序列的數(shù)據(jù)很多[1、2]，如一個(gè)工廠裝船貨物數(shù)量的月度序列、股票每日波動(dòng)、某化工過(guò)程產(chǎn)出的按小時(shí)觀測(cè)值等.在科技期刊出版的評(píng)議方面，特別是網(wǎng)絡(luò)環(huán)境下科技期刊的評(píng)議方面也可以發(fā)現(xiàn)時(shí)間序列的數(shù)據(jù).如針對(duì)某一科技期刊累積5 a的月平均評(píng)議數(shù)據(jù)序列，針對(duì)某一篇學(xué)術(shù)論文1 a中某一時(shí)間段的平均評(píng)議數(shù)據(jù)序列等.近年來(lái)人們開始對(duì)時(shí)間序列進(jìn)行深入的研究，尤其在時(shí)態(tài)數(shù)據(jù)的關(guān)聯(lián)規(guī)則挖掘方面，做了大量的研究.其中，文獻(xiàn)[3]研究了時(shí)間序列局部形態(tài)的確定性關(guān)聯(lián)問(wèn)題，文獻(xiàn)[4]研究了時(shí)間序列形態(tài)和后期趨勢(shì)的關(guān)聯(lián)問(wèn)題.事實(shí)上，時(shí)間序列中的形態(tài)形式具有不確定性和模糊性，將時(shí)間序列形態(tài)進(jìn)行確定性歸類和訓(xùn)練是不確切和不合理的，因而有必要引入模糊關(guān)聯(lián)規(guī)則的概念.為此，本文提出能使每一個(gè)局部序列軟化到代表形態(tài)中的模糊離散化處理方法，進(jìn)而研究反映局部形態(tài)關(guān)聯(lián)特征的模糊關(guān)聯(lián)規(guī)則.

1 時(shí)間序列的預(yù)處理

1.1 時(shí)間序列的分解

用Y表示某個(gè)時(shí)間序列，該序列可以用下面幾個(gè)部分表示：

其中T為趨勢(shì)項(xiàng)，表示長(zhǎng)期看時(shí)間序列逐漸增加或減少的變化；C為循環(huán)項(xiàng)，表示時(shí)間超過(guò)1 a的周期性變動(dòng)；S為季節(jié)項(xiàng)，表示1 a內(nèi)的周期性變動(dòng)；e為隨機(jī)項(xiàng)，表示不可預(yù)期的偶然因素對(duì)時(shí)間序列的影響.

1.2 時(shí)間序列的預(yù)處理

時(shí)間序列往往受到偶然因素的影響產(chǎn)生隨機(jī)變化.所以有時(shí)使用一些技術(shù)方法對(duì)數(shù)據(jù)進(jìn)行平滑和反季節(jié)性處理，以便于更好地發(fā)現(xiàn)數(shù)據(jù)的規(guī)律.本文使用的是統(tǒng)計(jì)學(xué)中的一種時(shí)間序列清洗方法[5]，具體步驟如下.

第一步 估計(jì)趨勢(shì)項(xiàng)T，然后得到季節(jié)項(xiàng)和誤差項(xiàng)的乘積Se＝Y(jié)/T；使用中心滑動(dòng)平均估計(jì)趨勢(shì)項(xiàng)對(duì)月度數(shù)據(jù)使用6個(gè)月的中心滑動(dòng)平均，將數(shù)據(jù)平滑：

對(duì)于季度數(shù)據(jù)使用2個(gè)月中心滑動(dòng)平均，將數(shù)據(jù)平滑：

平滑后的數(shù)據(jù)已經(jīng)沒有季節(jié)性

其中s為規(guī)范化后的季節(jié)因子.

第二步 去掉誤差項(xiàng)，估計(jì)季節(jié)項(xiàng)S，把與不同季節(jié)對(duì)應(yīng)的數(shù)字稱為季節(jié)因子，對(duì)季節(jié)因子進(jìn)行規(guī)范化；去掉長(zhǎng)期趨勢(shì)后的數(shù)據(jù)y/y＾包括季節(jié)和隨機(jī)誤差項(xiàng).把不同年份相同季節(jié)的數(shù)據(jù)進(jìn)行平均，就可以去掉誤差項(xiàng).

假設(shè)有4 a的月度數(shù)據(jù)，第一個(gè)數(shù)據(jù)用y1表示，依此類推，所有的數(shù)據(jù)可以表示為y1，y2，…，y48，用x1，x2，…，x48表示平滑后的數(shù)據(jù)，為了去掉誤差項(xiàng)，把每一年的相同月份求平均：

去掉隨機(jī)誤差項(xiàng)后就只剩季節(jié)項(xiàng)了，為了保證季節(jié)指數(shù)的平均數(shù)等于1，需要把季節(jié)因子規(guī)范化：

第三步 從原始數(shù)據(jù)中去掉季節(jié)項(xiàng)，得到經(jīng)過(guò)季節(jié)調(diào)整的數(shù)據(jù).

2 模糊C均值（FCM）聚類算法

1973年，Bezdek提出了模糊C均值（FCM）聚類算法[6]，F(xiàn)CM聚類算法依據(jù)每個(gè)數(shù)據(jù)點(diǎn)的隸屬度來(lái)確定其屬于某個(gè)類的程度.它首先將n個(gè)樣本點(diǎn)xi（i＝1，2，…，n）劃分為c個(gè)模糊類，然后求出每個(gè)模糊類的聚類中心，使得相似性價(jià)值函數(shù)達(dá)到最大，其中，每個(gè)樣本點(diǎn)的隸屬度取值范圍為[0，1]，即隸屬矩陣U的元素取值在[0，1]上.根據(jù)歸一化原則，數(shù)據(jù)集隸屬度的總和等于1：

那么，F(xiàn)CM的價(jià)值目標(biāo)函數(shù)被定義如下：

其中Ji為組i內(nèi)的價(jià)值函數(shù)；uij∈[0，1]指第j個(gè)樣本點(diǎn)屬于第i個(gè)模糊類的程度；ci是第i個(gè)模糊類的聚類中心；dij＝‖ci－xj‖，指聚類中心ci與樣本點(diǎn)xj之間的歐幾里德距離；m∈ [1，∞），為加權(quán)指數(shù).

若使得式（2）達(dá)到最小值，則必要條件為

其中λj為式（1）中n個(gè)約束的拉格朗日乘子，j＝1，2，…，n.將所有輸入?yún)⒘壳髮?dǎo)，最小化式（2）的必要條件為

通過(guò)批處理方式，F(xiàn)CM以4個(gè)步驟確定聚類中心ci和隸屬矩陣U：

步驟1 初始化隸屬矩陣U，U中元素取為[0，1]的隨機(jī)數(shù)，使其滿足式（2）中的約束條件.

步驟2 根據(jù)式（4）計(jì)算聚類中心ci，i＝1，2，…，c.

步驟3 根據(jù)式（2）計(jì)算目標(biāo)函數(shù).若函數(shù)值小于預(yù)先定義的閾值，或相對(duì)上次目標(biāo)函數(shù)的變化量大于預(yù)先定義的閾值，則算法中止.

步驟4 根據(jù)式（5）更新矩陣U作為新的隸屬矩陣.返回步驟2.

對(duì)于一長(zhǎng)度為n的時(shí)間序列按1.2中的預(yù)處理方法進(jìn)行處理后，將其采用FCM聚類算法劃分屬性.

把每月相對(duì)于平均趨勢(shì)的波動(dòng)情況作為新的時(shí)間序列來(lái)替代原時(shí)間序列，而后對(duì)其使用上述方法進(jìn)行模糊聚類，將其中的每一個(gè)局部序列軟化到代表形態(tài).

設(shè)X＝ ｛X1，X2，…，Xn｝為新時(shí)間序列，將一寬度為w的時(shí)間窗作用于X，形成一長(zhǎng)度為w的子序列Yi＝ ｛Xi，Xi＋1，…，Xi＋w－1｝，將時(shí)間窗在時(shí)間序列X上從始點(diǎn)至終點(diǎn)進(jìn)行單步滑移，形成一系列寬度為w的子序列M1，M2，…，MN－w＋1，記W（X，w）＝｛Mi｜i＝1，2，…，N－w＋1｝為由該時(shí)間序列X用寬度為w的滑窗移動(dòng)出的子序列集合，將W（X，w）看做w維歐氏空間中的（N－w＋1）個(gè)點(diǎn)，然后用FCM方法進(jìn)行聚類.

3 關(guān)聯(lián)規(guī)則的并行挖掘

Apriori算法[7]是最著名的關(guān)聯(lián)規(guī)則算法，已經(jīng)為大部分商業(yè)產(chǎn)品所采用.目前，基于Apriori已經(jīng)提出了若干種發(fā)現(xiàn)頻繁屬性集的并行算法.算法將候選項(xiàng)集并行化，對(duì)其進(jìn)行劃分并在每個(gè)處理器上分別計(jì)數(shù)，各處理器之間通過(guò)消息傳遞進(jìn)行通信.計(jì)數(shù)分配（CD）是著名的關(guān)聯(lián)規(guī)則并行算法，每個(gè)處理器對(duì)本地?cái)?shù)據(jù)的候選進(jìn)行計(jì)數(shù)，并將這些計(jì)數(shù)傳播到所有其他處理器上.然后每個(gè)處理器進(jìn)行全局計(jì)數(shù)，這些全局計(jì)數(shù)用于確定大項(xiàng)目集并生成下趟掃描時(shí)的候選.CD算法具有好的規(guī)模增長(zhǎng)性、可擴(kuò)展性和加速比性能.

利用并行算法處理后得到時(shí)間序列，對(duì)連續(xù)屬性進(jìn)行離散化，得到新的模糊屬性數(shù)據(jù)集，將其劃分在每個(gè)處理器上.本文設(shè)計(jì)了一個(gè)新的關(guān)聯(lián)規(guī)則并行挖掘算法，采用SPMD模式，各處理器之間只交換本地模糊支持?jǐn)?shù)，不進(jìn)行數(shù)據(jù)交換.在數(shù)據(jù)掃描過(guò)程中，處理器可以異步、獨(dú)立地計(jì)算本地模糊支持?jǐn)?shù).每次掃描結(jié)束時(shí)保持同步，并且所有處理器保存相同的候選集.下面是模糊關(guān)聯(lián)規(guī)則并行挖掘算法.

輸入：最小模糊支持度minSup；最小模糊信任度minConf

輸出：關(guān)聯(lián)規(guī)則集Sar

步驟1 設(shè)置并行處理器p1，p2，…，pn.

步驟2 將事務(wù)數(shù)據(jù)庫(kù)劃分為多個(gè)分區(qū)，并分別分配到每個(gè)處理器上.

步驟3 對(duì)每個(gè)處理器，采用FCM算法進(jìn)行聚類，將其轉(zhuǎn)化為新的數(shù)據(jù)集，結(jié)合連續(xù)屬性離散化技術(shù)將得到的時(shí)間序列轉(zhuǎn)換為新數(shù)據(jù)庫(kù)，并根據(jù)最小模糊支持度minSup和最小模糊信任度minConf構(gòu)建前綴樹.

步驟4 依據(jù)步驟3在每個(gè)處理器上進(jìn)行局部計(jì)數(shù)；對(duì)于事務(wù)數(shù)據(jù)庫(kù)中的每個(gè)事務(wù)和候選項(xiàng)目集中的每個(gè)項(xiàng)目，如果某個(gè)項(xiàng)目屬于某個(gè)處理器上的事務(wù)，則進(jìn)行局部計(jì)數(shù)，并將它們傳播到其他站點(diǎn).

步驟5 計(jì)算全局計(jì)數(shù)，生成規(guī)則集.

4 實(shí) 驗(yàn)

本文的實(shí)驗(yàn)數(shù)據(jù)是1992－01至2008－12美國(guó)洛杉磯?mèng)[市區(qū)臭氧每月平均記錄.表1為將數(shù)據(jù)統(tǒng)計(jì)記錄按一年12個(gè)月進(jìn)行分段后得到的數(shù)據(jù).

表1 洛杉磯?mèng)[市區(qū)臭氧每月時(shí)均記錄Tab.1 Monthly averages of hourly readings of ozone in downtown Los Angeles

通過(guò)公式計(jì)算，得到每月相對(duì)于平均趨勢(shì)的波動(dòng)情況（見表2）.

本文的關(guān)聯(lián)規(guī)則是在滑窗參數(shù)w（w＝3）、聚類類數(shù)（類數(shù)＝4）固定的條件下進(jìn)行的.首先產(chǎn)生了A、B、C、D4種代表形態(tài)，如圖1所示.

表2 相對(duì)于平均趨勢(shì)的波動(dòng)情況Tab.2 The fluctuations compared with the average trend %

圖1 波動(dòng)關(guān)聯(lián)規(guī)則的4種形態(tài)Fig.1 Four patterns of fluctuated association rules

再通過(guò)本文提出的算法對(duì)其進(jìn)行規(guī)則的挖掘[8]，所得的模糊關(guān)聯(lián)規(guī)則集如下：

支持度13.33%，置信度50%時(shí)，有

（1）2B＼3C＝＞7B＼9A

（2）7C＼8A＝＞10C＼12B

支持度13.33%，置信度67%時(shí)，有

（3）1C＼2A＝＞7C＼9D

（4）2A＼3D＝＞8A＼9D

（5）4D＼5A＝＞7C＼8C

（6）5D＼6A＝＞7D＼8A＼9D

（7）1B＼3A＝＞4B＼6C

（8）2A＼3B＝＞4D＼5A＼6B

（9）2A＼3D＝＞4A＼5B＼6B

支持度13.33%，置信度100%時(shí)，有

（10）8D＼9A＝＞10B＼11C＼12A

（11）4A＼5B＼6B＝＞7C＼8A＼9D

（12）4D＼5A＼6B＝＞10B＼12C

（13）1B＼2B＝＞5D＼6A

（14）8C＼9A＝＞10D＼11C＼12A

得到以上規(guī)則集后，對(duì)于2007年以后出現(xiàn)的新數(shù)據(jù)，通過(guò)本文所給出的方法進(jìn)行反季節(jié)化處理和模糊離散化處理后，就可以對(duì)未發(fā)生的事件進(jìn)行模糊形態(tài)估測(cè).雖然2008年下半年的數(shù)據(jù)已經(jīng)發(fā)生，但為便于實(shí)驗(yàn)，這里假定并未發(fā)生，采用上述方法進(jìn)行了預(yù)測(cè)，預(yù)測(cè)結(jié)果與真實(shí)事件形態(tài)基本符合，證明了本文方法的有效性.

5 結(jié) 語(yǔ)

本文提出了基于FCM聚類的時(shí)間序列模糊關(guān)聯(lián)規(guī)則挖掘算法.此挖掘算法首先采用FCM聚類算法對(duì)清洗后的時(shí)間數(shù)據(jù)進(jìn)行模糊離散化處理，將每一個(gè)局部序列軟化到代表形態(tài)中.采用改進(jìn)的關(guān)聯(lián)規(guī)則并行挖掘算法以發(fā)現(xiàn)頻繁模糊屬性集，最后由多個(gè)處理器并行地產(chǎn)生滿足最小模糊信任度的模糊關(guān)聯(lián)規(guī)則.實(shí)驗(yàn)證明，該并行算法具有好的可擴(kuò)展性、規(guī)模增長(zhǎng)性和加速比性能.

[1]GAO L，WANG X Y S.Continuous similarity－based queries on streaming time series [J]. IEEE Transactions on Knowledge and Data Engineering，2005，17（10）：1320－1332

[2]ZHANG Z G，CHAN Shing－chow.Robust adaptive Lomb periodogram for time－frequency analysis of signals with sinusoidal and transient components[C]//IEEE ICASSP.Philadelphia：IEEE，2005：493－496

[3]DAS G，LIN King－ip，MANNILA H，etal.Rule discovery from time series[C]//Proceeding of the 3rdInternational Conference of Knowledge Discovery and Data Mining.California：AAAI Press，1998：16－22

[4]MARK L，KLEIN Y，KANDEL A.Knowledge discovery in time series databases [J].IEEE Transactions on Systems，Man and Cybernetics，2001，31（1）：160－169

[5]GEORGE E P B，JENKINS G M，REINSEL G C，etal.時(shí)間序列分析預(yù)測(cè)與控制[M].顧 嵐，等譯.北京：中國(guó)統(tǒng)計(jì)出版社，1997

[6]高新波.模糊聚類分析及其應(yīng)用[M].西安：西安電子科技大學(xué)出版社，2004

[7]AGRAWAL R，SHAFER J C.Parallel mining of association rules：design， implementation and experience[J].IEEE Transactions on Knowledge and Data Engineering，1996，8（6）：962－969

[8]TAN Pang－ning，STEINBACH M，KUMA V.數(shù)據(jù)挖掘?qū)д揫M].范 明，范宏建，等譯.北京：人民郵電出版社，2006