基于FCM聚類的時間序列模糊關聯規則挖掘

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

（1.大連理工大學 管理學院，遼寧 大連 116024；2.遼寧師范大學 計算機信息與技術學院，遼寧 大連 116081；3.大連理工大學 計算機科學與技術學院，遼寧 大連 116024）

0 引 言

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

1 時間序列的預處理

1.1 時間序列的分解

用Y表示某個時間序列，該序列可以用下面幾個部分表示：

其中T為趨勢項，表示長期看時間序列逐漸增加或減少的變化；C為循環項，表示時間超過1 a的周期性變動；S為季節項，表示1 a內的周期性變動；e為隨機項，表示不可預期的偶然因素對時間序列的影響.

1.2 時間序列的預處理

時間序列往往受到偶然因素的影響產生隨機變化.所以有時使用一些技術方法對數據進行平滑和反季節性處理，以便于更好地發現數據的規律.本文使用的是統計學中的一種時間序列清洗方法[5]，具體步驟如下.

第一步 估計趨勢項T，然后得到季節項和誤差項的乘積Se＝Y/T；使用中心滑動平均估計趨勢項對月度數據使用6個月的中心滑動平均，將數據平滑：

對于季度數據使用2個月中心滑動平均，將數據平滑：

平滑后的數據已經沒有季節性

其中s為規范化后的季節因子.

第二步 去掉誤差項，估計季節項S，把與不同季節對應的數字稱為季節因子，對季節因子進行規范化；去掉長期趨勢后的數據y/y＾包括季節和隨機誤差項.把不同年份相同季節的數據進行平均，就可以去掉誤差項.

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

去掉隨機誤差項后就只剩季節項了，為了保證季節指數的平均數等于1，需要把季節因子規范化：

第三步 從原始數據中去掉季節項，得到經過季節調整的數據.

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

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

那么，FCM的價值目標函數被定義如下：

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

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

其中λj為式（1）中n個約束的拉格朗日乘子，j＝1，2，…，n.將所有輸入參量求導，最小化式（2）的必要條件為

通過批處理方式，FCM以4個步驟確定聚類中心ci和隸屬矩陣U：

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

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

步驟3 根據式（2）計算目標函數.若函數值小于預先定義的閾值，或相對上次目標函數的變化量大于預先定義的閾值，則算法中止.

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

對于一長度為n的時間序列按1.2中的預處理方法進行處理后，將其采用FCM聚類算法劃分屬性.

把每月相對于平均趨勢的波動情況作為新的時間序列來替代原時間序列，而后對其使用上述方法進行模糊聚類，將其中的每一個局部序列軟化到代表形態.

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

3 關聯規則的并行挖掘

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

利用并行算法處理后得到時間序列，對連續屬性進行離散化，得到新的模糊屬性數據集，將其劃分在每個處理器上.本文設計了一個新的關聯規則并行挖掘算法，采用SPMD模式，各處理器之間只交換本地模糊支持數，不進行數據交換.在數據掃描過程中，處理器可以異步、獨立地計算本地模糊支持數.每次掃描結束時保持同步，并且所有處理器保存相同的候選集.下面是模糊關聯規則并行挖掘算法.

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

輸出：關聯規則集Sar

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

步驟2 將事務數據庫劃分為多個分區，并分別分配到每個處理器上.

步驟3 對每個處理器，采用FCM算法進行聚類，將其轉化為新的數據集，結合連續屬性離散化技術將得到的時間序列轉換為新數據庫，并根據最小模糊支持度minSup和最小模糊信任度minConf構建前綴樹.

步驟4 依據步驟3在每個處理器上進行局部計數；對于事務數據庫中的每個事務和候選項目集中的每個項目，如果某個項目屬于某個處理器上的事務，則進行局部計數，并將它們傳播到其他站點.

步驟5 計算全局計數，生成規則集.

4 實 驗

本文的實驗數據是1992－01至2008－12美國洛杉磯鬧市區臭氧每月平均記錄.表1為將數據統計記錄按一年12個月進行分段后得到的數據.

表1 洛杉磯鬧市區臭氧每月時均記錄Tab.1 Monthly averages of hourly readings of ozone in downtown Los Angeles

通過公式計算，得到每月相對于平均趨勢的波動情況（見表2）.

本文的關聯規則是在滑窗參數w（w＝3）、聚類類數（類數＝4）固定的條件下進行的.首先產生了A、B、C、D4種代表形態，如圖1所示.

表2 相對于平均趨勢的波動情況Tab.2 The fluctuations compared with the average trend %

圖1 波動關聯規則的4種形態Fig.1 Four patterns of fluctuated association rules

再通過本文提出的算法對其進行規則的挖掘[8]，所得的模糊關聯規則集如下：

支持度13.33%，置信度50%時，有

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

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

支持度13.33%，置信度67%時，有

（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%時，有

（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

得到以上規則集后，對于2007年以后出現的新數據，通過本文所給出的方法進行反季節化處理和模糊離散化處理后，就可以對未發生的事件進行模糊形態估測.雖然2008年下半年的數據已經發生，但為便于實驗，這里假定并未發生，采用上述方法進行了預測，預測結果與真實事件形態基本符合，證明了本文方法的有效性.

5 結 語

本文提出了基于FCM聚類的時間序列模糊關聯規則挖掘算法.此挖掘算法首先采用FCM聚類算法對清洗后的時間數據進行模糊離散化處理，將每一個局部序列軟化到代表形態中.采用改進的關聯規則并行挖掘算法以發現頻繁模糊屬性集，最后由多個處理器并行地產生滿足最小模糊信任度的模糊關聯規則.實驗證明，該并行算法具有好的可擴展性、規模增長性和加速比性能.

[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.時間序列分析預測與控制[M].顧 嵐，等譯.北京：中國統計出版社，1997

[6]高新波.模糊聚類分析及其應用[M].西安：西安電子科技大學出版社，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.數據挖掘導論[M].范 明，范宏建，等譯.北京：人民郵電出版社，2006