基于譜聚類的高階模糊時序自適應預測方法

周春楠，黃少濱，遲榮華，李雅，郎大鵬

?

基于譜聚類的高階模糊時序自適應預測方法

周春楠，黃少濱，遲榮華，李雅，郎大鵬

（哈爾濱工程大學計算機科學與技術學院，黑龍江哈爾濱 150001）

結合數據特征及分布特點提出一種基于譜聚類的模糊時間序列自適應預測方法。首先基于譜聚類的思想，根據樣本數據特征獲取其所屬論域的個數及范圍，實現向模糊時間序列的自適應轉化；然后基于Markov概率模型表示模糊時間序列中的模糊關系，從而對多步模糊關系、高階模糊關系及模糊關系的穩態進行求解；最后獲取預測值的可能模糊狀態，進而利用去模糊化方法將其還原為預測值。在真實以及人工時間序列數據上的實驗表明了所提方法的合理性與有效性。

模糊時間序列；譜聚類；論域劃分；Markov概率模型；模糊關系

1 引言

時間序列數據是在自然界、工程技術以及經濟社會等領域廣泛存在著的一種重要數據類型，如氣象上的降水量和氣溫數據、天文上的太陽黑子數據、經濟領域的GDP和股指數據、醫學上的心/腦電波序列、移動通信行業的話務流量、復雜工業系統運行過程中的狀態監測數據等均屬于時間序列數據。對時間序列數據研究的一項主要內容就是時間序列的預測，即根據歷史時間序列數據發現數據的內在特性和發展規律，并構造隨時間變化的序列模型，然后基于一定的規則推測未來的數據，從而為相應領域的決策提供依據。

時間序列數據包括線性和非線性數據，相應的預測（建模）方法也分為線性方法和非線性方法。其中，線性預測方法主要包括基于傳統統計學時間序列隨機模型的經典回歸分析等方法，而非線性預測方法則主要包括人工智能領域的神經網絡、支持向量機等方法。上述回歸方法、神經網絡方法、支持向量機方法均利用傳統的確定性關系表示數據所屬的集合，并且過于依賴歷史數據的完整性、精確性和確定性；然而歷史數據往往是不完整的、不精確的、不確定的。

面對這種時間序列的觀測值中包含大量不完整或噪聲信息的情況，模糊時間序列（fuzzy time series）[1]引入了模糊理論，將歷史數據中的不確定性變量利用模糊變量進行表示，相應的預測方法也被成功地用于多個領域，如學生登記[1~3]、溫度[4,5]、電信業務[6]等，其中，在股票預測上的效果尤為明顯[7]，而隨著成功案例的不斷涌現，許多非信息科學領域，如臨床醫學[8]、環境治理[9]以及旅游[10]等也開始采用模糊方法進行建模和分析。

模糊時間序列預測方法的核心內容是論域的劃分和模糊規則的提取，合理有效的方法確保了模型的預測精度。而模糊規則的提取又是以劃分論域的結果為基礎，針對這一環節，近年來出現了很多關于論域劃分問題的改進方法。較具代表性的有以均勻等分為思想的論域劃分方法，這種方法相對簡單，建模復雜度較低，但是均勻劃分不能體現信息的真實分布，預測精度也較低[2~5]?；趩l式來確定論域劃分的方法，考慮了劃分間隔對預測結果的影響[11]。另外，還有基于自然劃分[12]、基于分布密度[13~15]、基于比例的間隔長度[16]、基于遺傳算法[17]，基于多變量[18]以及單變量約束的優化算法[19]等方法來劃分論域。除了對算法核心內容的改進之外，混合方法也是提高算法效果的有效途徑，例如與模糊聚類和神經網絡相結合的方法[20,21]，與粒子群優化與支持向量機結合的方法[22]以及與改進的遺傳算法相結合的方法[23]。

上述方法大多是以時間序列數據服從均勻分布或短尾分布為假設而提出的。然而進一步的研究發現，真實時間序列數據（特別是經濟領域）由于系統的涌現行為更多的是聚集出一種長尾的密度分布，上述方法便缺乏一定的合理性。同時又有研究表明，根據數據的真實分布來確定論域的劃分往往能夠獲得較好的效果，其中尤以基于聚類思想的論域劃分方法更為突出，因為它能夠發現數據的真實密度分布，進而可獲得較高的預測準確性[24]。

例如文獻[25,26]基于層次聚類方法獲得聚簇，并將其轉化為對應論域的間隔細分，然后根據細分的間隔模糊化時間序列，提取模糊關系并構建預測模型。文獻[27]則結合基于密度的聚類以及公理模糊集分類技術構建模糊預測模型。即通過聚類產生的聚簇進行論域劃分，并基于公理模糊集分類方法構建預測模型。然而這些方法在聚類之前需先對數據進行排序，如此便失去了聚類能夠發現數據分布情況的最大優勢。文獻[28,29]基于模糊C均值（FCM, fuzzy C-means）算法構建模糊時間序列預測模型，根據聚類結果劃分論域并提取模糊關系。雖然模糊聚類方法有助于發現時間序列中的模糊關系，但FCM算法需要預先設定聚簇數目，而時序數據的增長會使數據分布密度也發生變化，如此便會導致預測精度的下降。

如前所述，真實的時間序列數據往往呈現長尾分布的現象，這是因為時間序列數據之間存在一定的關聯。另外，根據現有的研究成果可知聚類有助于獲取數據分布區域，從而能夠更準確地進行論域劃分，因此聚類結果的準確性影響著模糊時間序列預測的精度。實際上模糊時間序列中數據之間的關聯關系可以利用一個關聯矩陣來描述，而譜聚類[30]是基于關系矩陣的一種有效聚類算法，同時它不易陷入局部最優，而且能夠識別非云狀等特殊分布特點的聚簇，因此譜聚類有助于有效劃分模糊時間序列中的數據分布情況。

因此，本文提出一種基于譜聚類的模糊時間序列預測方法。首先基于譜聚類對時間序列數據的論域進行劃分，實現由原始時間序列向模糊時間序列的自適應轉化，并獲得對應的模糊集合；然后利用模糊集表示模糊時間序列；對于時序觀測值變化的不確定性，提取模糊時間序列中的高階模糊關系，并引入高階Markov概率模型描述這種模糊關系，據此對后續數據進行預測。從而使所提模型可在不對數據分布進行假設的基礎上，有效地劃分原時間序列數據的論域；同時高階Markov的引入使模型考慮了之前時刻的數據影響后續數據的各種可能性。從論域劃分以及模糊關系提取2個方面保證了模型預測的準確性。

2 相關知識

2.1 模糊時間序列定義及表示

模糊集理論最早由Zadeh提出用于處理不確定性問題。Song和Chissom[1]成功地將該理論用于時間序列預測上，其基本思想是根據時間序列的值域確定一個論域及其對應的一種劃分，根據劃分的論域構建對應的模糊集合，每個劃分的隸屬度代表了劃分的論域在該模糊集中的權重，然后將時間序列的觀測值映射為所屬論域劃分所對應的模糊集，模糊時間序列即為由模糊集表示的時間序列。上述方法的具體定義如下。

2.2 基于譜聚類的自適應論域劃分方法

譜聚類是一種非無督學習過程，相對于其他聚類算法，它能夠有效解決數據分布復雜的情況，且收斂于全局最優解[30]。當前部分關于譜聚類的研究集中于利用拉普拉斯矩陣的性質，其中，較典型的是基于矩陣攝動理論的譜聚類算法[31]。

基于攝動理論的譜聚類算法，相較于傳統譜聚類算法，具有自適應的能力，可自動確定聚簇個數，該方法主要過程如下所述。

1) 計算數據集中各元素間的相似性，構建的相似矩陣，矩陣中的元素根據高斯相似性有。

3) 計算拉普拉斯矩陣的特征值，將其升序排列。

該方法仍遵循譜聚類的基本思想，不同之處在于它對拉普拉斯矩陣的特征值序列進行了判斷，即當矩陣的第個特征值相對于其前一個第個特征值變化較大時，則由前個特征向量所構成的特征矩陣所代表的元素間的關系越穩定，因此可利用特征值的差值來確定聚簇的個數，但多大程度的差值可以得到最佳的聚簇個數需要通過計算特征值的方差來判斷。

3 基于譜聚類的模糊時間序列自適應預測方法

面對真實時間序列數據中存在大量不完整或噪聲信息的情況，本文所提模型的基本思想是利用無監督學習的聚類方法對時間序列數據的論域進行劃分并計算模糊集，用模糊集表示原始時間序列數據所對應的模糊時間序列。然后構建原始時間序列數據中的模糊邏輯關系，并由高階Markov概率轉移矩陣對其進行建模。最后計算已知模糊狀態在高階狀態轉移中發生概率最高的下一狀態，并通過去模糊化方法將下一模糊狀態還原為下一時刻的預測數值。那么基于譜聚類的模糊時間序列預測方法（SFTP，spectral-based fuzzy time-series prediction）構建的具體方法如下所述。

由上述分析可知時間序列數據之間存在一定相似性，在劃分論域時需充分考慮它們之間的相似性。譜聚類算法基于對象間的相似矩陣，將聚類問題轉化為圖劃分問題，并且不對數據的分布進行假設?？梢娮V聚類的特點使其更適合于處理劃分論域的問題。那么基于譜聚類確定時間序列論域劃分的具體步驟如下。

①計算描述時間序列數據間相似度的相似矩陣，若樣本數據對應的趨勢變化序列為，那么相似矩陣的元素如式(2)所示，其中，。

解決圖劃分問題的有效方法是將其轉化為求解對應矩陣的譜分解問題，即根據矩陣的特征值和特征向量對數據集進行劃分。同時，由矩陣的攝動理論可知，矩陣的第和個特征值之間的差距越顯著，由所選的個特征向量構成的子空間就越穩定。

③獲取趨勢變化序列的聚類結果。由譜聚類的思想可知，拉普拉斯矩陣對應的特征向量即為嵌入空間中的點，然后利用-means 算法對嵌入空間中的點進行劃分，得聚簇集合，其中，。其具體含義為：若第行屬于第個聚簇，說明屬于第個聚簇。

,

,

…,

步驟7 構建模糊關系矩陣。由引言可知，影響模糊時間序列預測準確性的核心內容除了論域劃分外，還包括模糊關系的提取。對于時間序列而言，各時刻的預測值往往是不確定的，而傳統的模糊邏輯關系表示往往忽略了這一點。

若將模糊集視為狀態，模糊關系即為狀態間的轉移關系，即可利用高階Markov概率模型表示上述高階模糊邏輯關系，方便考慮之前時刻的數據影響后續數據的各種可能性；并將其描述為矩陣的形式，從而可以利用矩陣分析方法對其進行分析以獲得時間序列的整體特性。構建的二階模糊關系矩陣如式(4)所示。

4 實驗分析

本文在真實以及人工數據集上進行實驗，并通過與當前2種主流時間序列預測方法：自回歸和基于神經網絡的預測方法，以及3種模糊時間預測方法：平均劃分論域、基于-means和層次聚類的論域劃分方法的預測結果進行對比，說明所提模糊時間序列預測方法能夠獲得相對較準確的預測效果。

為了分析預測效果，選取2種常用的度量時間序列預測準確性的指標：預測誤差方差（MSE, mean square error）和泰爾不等系數（TIC, Theil inequality coefficient）[32]

4.1 真實數據集

隨著通信技術的發展，通話行為的方式發生了較大變化，人們由較早的以手機通話為主的業務模式轉變為以數據為主的業務模式，由于數據業務可支撐的應用極多，較難從中分析通話模式，因此本文選擇相對較早的純通話業務數據，進行通話行為模式的分析。同時選用粒度過細的長期數據樣本構建預測模型會使模型極不穩定，導致預測結果誤差增大[33]。那么以中國某省會城市2004年~2009年各月的電信話務量真實時間序列數據作為驗證所提模型有效性的實驗數據集，并選取其中2004年1月~2009年5月的數據作為訓練樣本數據集，2009年6月~2009年12月的數據則作為測試數據集。預測目的是希望基于歷史話務量數據，對未來的話務量進行預測。該時間序列數據的原始分布如圖1(a)所示，按式(1)計算的原始數據所對應的趨勢值分布情況如圖1(b)所示?？梢娳厔蒉D化后的數據分布特點相較于原始數據而言分布特征更明顯。

如圖2所示，趨勢轉化后的數據也在一定程度上出現了相關性，因此本文所提模型將以趨勢轉化后的數據作為預測的基礎，并且在獲得話務量趨勢數據后，利用高斯相關函數構建相似矩陣，相似矩陣的數值分布如圖3所示。根據譜聚類特征值計算方法求得特征值序列，在圖4所示的特征值序列中，在第6、12、20個特征值處，特征值的差值有明顯地變化，且在數值上呈現遞增。因此選取前6個、前12個以及前20個特征向量作為特征向量子空間，分別對趨勢數據進行擬合，擬合效果如圖5所示，通過比較3個特征值可知，模型擬合的效果隨著特征向量的增加而提高，且在特征向量為20時最好，但相對于12個特征向量時，模型擬合效果提升不大，且容易出現過擬合影響適應能力。

圖6所示的各典型預測方法的擬合曲線對比也顯示了相較于其他預測方法，本文所提模型SFTP得到的值更加接近于原始數據，適應性更強，具有更好的擬合效果。

此外，進一步對幾種預測方法關于2種預測指標MSE與TIC的結果進行對比，如圖7所示，其中MSE值為利用小數定標規范化后的結果?？梢园l現所提SFTP算法相較于其他算法，能夠取得較低的評價指標值，即可以獲得較好的預測效果。主要是相較于普通的時間序列預測方法， SFTP利用了模糊時間序列建模方法，充分考慮了數據的原始特征；而相較于幾種對比的模糊時間序列預測方法，基于譜聚類進行論域劃分并不需要預先對數據的分布進行假設，并且它基于數據間的相似矩陣，將聚類問題轉換為對矩陣的譜分解問題，如前所述，模糊時間序列數據之間具有一定的關聯關系，因此基于譜聚類的方法能夠較準確地獲取數據的分布情況，從而有助于論域劃分；另外，基于高階Markov概率模型描述模糊時間序列中的高階模糊關系的方法，也充分考慮了時間序列中歷史數據對未來數據產生的各種可能的影響?？梢姳疚乃崮Ｐ驮谡撚騽澐忠约澳：P系提取這2個影響模糊時間序列預測準確性的核心內容上，均提供了有效的解決方法。

4.2 人工數據集

為了進一步驗證所提算法的有效性，本文還選取了4個常見的人工時間序列數據集[33]：Stock、Room Nights、Male Incidence和Sale，進行對比實驗。如圖8所示為幾種預測算法在該4個數據集上關于2種預測指標MSE與TIC的對比結果，同樣的，其中MSE值為利用小數定標規范化后的結果。其中在Stock與Room Nights數據集上，SFTP與AR算法均獲得了較低的MSE和TIC值，即預測結果較準確；而在另2個數據集上，相較于幾種對比算法，SFTP也均能表現出較準確的預測效果。這主要是因為SFTP利用數據原始特征，無需對數據分布進行預先假設，基于譜聚類可較準確地獲取數據的分布情況；同時充分考慮了時間序列中歷史數據對未來數據產生的各種可能的影響。而AR在幾個數據集上也能獲得較好的預測效果，說明簡單的預測模型在簡單的時間序列數據中即能發揮較準確的預測作用。

通過上述分析可知，在幾種典型時間序列人工數據集上的實驗結果也進一步驗證了所提SFTP算法的有效性。

5 結束語

針對模糊時間序列預測方法中存在的問題，本文提出一種基于譜聚類的模糊時間序列預測方法。該模型基于譜聚類進行論域劃分，在不對數據分布進行預先假設的基礎上，能夠有效地劃分原時間序列數據的論域；另外模型利用高階Markov概率模型描述模糊時間序列中的高階模糊關系，并據此對后續數據進行預測，使之前時刻的數據對后續數據產生的各種可能影響均被處理。即從論域劃分以及模糊關系提取2個方面保證了模型預測的準確性。在真實時間序列數據集上的實驗表明了所提預測方法的有效性。

[1] SONG Q, CHISSOM B S. Fuzzy time series and its models [J]. Fuzzy Sets System, 1993, 54(3): 269-277.

[2] SONG Q, CHISSOM B S. Forecasting enrollments with fuzzy time series [J]. Part I Fuzzy Sets System, 1993, 54(1): 1-9.

[3] SONG Q, CHISSOM B S. Forecasting enrollments with fuzzy time series [J]. Part II Fuzzy Sets System, 1994, 62(1): 1-8.

[4] LEE L W, WANG L H, CHEN S M. Temperature prediction and TAIEX forecasting based on high-order fuzzy logical relationships and genetic simulated annealing techniques [J]. Expert Systems with Applications, 2008, (34): 328-336.

[5] CHEN S M, HWANG J R. Temperature prediction using fuzzy time series [J]. IEEE Transactions on Systems, Man, Cybernetics-Part B: Cybernetics, 2000, 30(2): 263-275.

[6] 王兆霞,孫雨耕. 基于模糊神經網絡的網絡業務量預測研究[J]. 通信學報, 2005,26(3):136-140.

WANG Z X, SUN Y G. Study of predicting network traffic using fuzzy neural networks[J].Journal on Communications, 2005,26(3):136-140.

[7] YU H K. Weighted fuzzy time-series models for TAIEX forecasting [J]. Physical A, 2004, (349): 609-624.

[8] 張韜, 馮子健. 模糊時間序列分析在腎綜合征出血熱發病率預測的應用初探[J]. 中國衛生統計, 2011, 2:146-150.

ZHANG T, FENG Z J. Application of fuzzy time series analysis in incidence of hemorrhagic fever with renal syndrome prediction [J].China Health Statistics, 2011, 2:146-150.

[9] 倪明. 模糊時間序列預測模型研究及其在污水處理上的應用[D]. 西南石油大學,2012.

NI M. Fuzzy time series forecasting model and its application in wastewater treatment[D]. Southwest Pe troleum University, 2012.

[10] ALADAG C H, EGRIOGLU E. A high order seasonal fuzzy time series model and application to international tourism demand of turkey[J]. Applications in Engineering and Technology, 2014, 26(1):295-302.

[11] HUARNG K. Effective lengths of intervals to improve forecasting in fuzzy time series[J]. Fuzzy Sets and Systems, 2001, 123(3): 387-394.

[12] LI S T, CHEN Y P. Natural partition-based forecasting model for fuzzy time series[C]//The IEEE International Conference on Fuzzy Systems Budapest. Hungary, c2004:25-29.

[13] CHEN S M, HSU C C. A new method to forecast enrollments using fuzzy time series [J]. International Journal of Applied Science and Engineering, 2004, 2(3): 234-244.

[14] TRAN T N, WEHRENS R, BUYDENS L. KNN-kernel density-based clustering for high-dimensional multivariate data [J]. Computational Statistics and Data Analysis, 2006, 51(2): 513-525.

[15] CHENG C H, CHANG J R, YEH C A. Entropy-based and trapezoid fuzzification-based fuzzy time series approaches for forecasting IT project cost [J]. Technological Forecasting and Social Change, 2006, 73(5): 524-542.

[16] HUARNG K, YU T H. Ratio-based lengths of intervals to improve fuzzy time series forecasting [J]. IEEE Transactions on Systems,Man, and Cybernetics-Part B: Cybernetics, 2006, 36(2): 328-340.

[17] LEE L W, WANG L H, CHEN S M. Temperature prediction and TAIFEX forecasting based on fuzzy logical relationships and genetic algorithms [J]. Expert Systems with Applications, 2007, (33): 539-550.

[18] CHENG C H, CHENG G W, WANG J W. Multi-attribute fuzzy time series method based on fuzzy clustering [J]. Expert Systems with Applications, 2008, 34(2): 1235-1242.

[19] YOLCU U, EGRIOGLU E, USLU V R. A new approach for determining the length of intervals for fuzzy time series [J]. Applied Soft Computing, 2009, 9(2): 647-651.

[20] EGRIOGLU E, ALADAG C H. Fuzzy time series forecasting with a novel hybrid approach combining fuzzy c-means and neural networks[J]. Expert Systems with Application, 2013, 40(3):854-857

[21] KHASHEI M. Fuzzy artificial neural network p, d, q model for incomplete financial time series forecasting[J]. Applications in Engineering and Technology, 2014, 26(2):831-845.

[22] CHEN S M, KAO P Y. TAIEX forecasting based on fuzzy time series, particle swarm optimization techniques and support vector machines[J]. Information Sciences, 2013, 247(15):62-71.

[23] BAS E, USLU V R, YOLCU U. A modified genetic algorithm for forecasting fuzzy time series[J]. Applied Intelligence, 2014, 41(2): 453-463.

[24] 曹盼盼, 閻春寧. 人類通信模式的冪律分布和Zipf定律[J]. 復雜系統與復雜科學, 2009, 6(4):51-56.

CAO P P, YAN C N. The power law and Zipf’s law in human communication patterns [J]. Complex Systems and Complexity Science, 2009, 6(4):51-56.

[25] CHEN S M, WANG N Y, PAN J S. Forecasting enrollments using automatic clustering techniques and fuzzy logical relationship [J]. Expert Systems with Applications, 2009, 36(8): 11070-11076.

[26] CHEN S M, TANUWIJAYA K. Multivariate fuzzy forecasting based on fuzzy time series and automatic clustering techniques [J]. Expert Systems with Applications, 2011, 38(8):10594-10605.

[27] MILLS T C. Time series techniques for economists[M]. Cambridge: Cambridge University Press, 1990.

[28] LI S T, KUO S C, CHENG Y C, et al. A vector forecasting model for fuzzy time series [J]. Applied Soft Computing, 2011, 11(3): 3125-3134.

[29] WANG W, LIU X. Fuzzy forecasting based on automatic clustering and axiomatic fuzzy set classification [J]. Information Sciences, 2015, 294(294): 78-94.

[30] NG A Y, JORDAN M I, WEISS Y. On spectral clustering: analysis and an algorithm [J]. Advances in Neural Information Processing Systems, 2002, 2(8):849-856.

[31] LUXBURG U V. A tutorial on spectral clustering [J]. Statistics and Computing, 2007, 17(4):395-416.

[32] LI M, LI Y C, LENG J X. Powertype functions of prediction error of sea le-vel time series[J]. Entropy, 2015, 17(7): 4809-4837.

[33] LI M, LI J Y. On the predictability of long-range dependent series[J/OL]. Mathematical Problems in Engineering, 2010, article ID 397454. http://datamarket.com/data/

High-order fuzzy time series self-adaption prediction method based on spectral clustering

ZHOU Chun-nan, HUANG Shao-bin, CHI Rong-hua, LI Ya, LANG Da-peng

(College of Computer Science and Technology, Harbin Engineering University, Harbin 150001, China)

A fuzzy time series self-adaption prediction method based on spectral clustering and data characteristics was proposed. First, based on spectral clustering and the characteristics of data, the number and scope of the discourses was obtained to convert into fuzzy time series self- adaptively. Then, fuzzy relationships based on Markov probability model was presented, and the multi-steps, high-order and steady fuzzy relationship are gotten. Finally, proposed meted obtained the probable fuzzy states, and got its predicted values based on defuzzification methods. Experiments on real-world and synthetic time series data indicate the rationality and effectiveness of the proposed method.

fuzzy time series, spectral clustering, discourse partition, Markov probability model, fuzzy relationship

TP399

A

10.11959/j.issn.1000-436x.2016036

2015-05-11；

2015-09-16

中央高校基本科研業務專項基金資助項目（No.HEUCF100603, No.HEUCFZ1212）

The Fundamental Research Funds for the Central Universities (No.HEUCF100603, No.HEUCFZ1212)

周春楠（1971-），男，黑龍江哈爾濱人，哈爾濱工程大學博士生，主要研究方向為時間序列預測、數據挖掘、不確定性研究等。

黃少濱（1965-），男，黑龍江哈爾濱人，哈爾濱工程大學教授、博士生導師，主要研究方向為分布式計算與仿真、模型檢測、數據集成等。

遲榮華（1981-），男，黑龍江哈爾濱人，哈爾濱工程大學博士生，主要研究方向為復雜網絡、不確定性研究等。

李雅（1985-），女，黑龍江哈爾濱人，哈爾濱工程大學博士生，主要研究方向為模型監測等。

郎大鵬（1983-），男，黑龍江哈爾濱人，哈爾濱工程大學博士生，主要研究方向為模型監測等。