基于多目標決策的時間序列數據挖掘算法

賈曉強

（渭南師范學院計算機學院，陜西 渭南 714099）

計算機技術的發展使得用戶需求日益增長，同時也使得數據呈爆炸式增加，大數據的發展給各行各業帶來了前所未有的便利，特別是醫學、金融、生物、工程、通信等行業都在發展的過程中積累了許多的數據，其中有些數據的排序方式是按照時間排序的，這就是時間序列數據。當得到了這些積累下的數據之后，就需要對時間序列數據進行深度挖掘。具體到某個領域的時間序列數據是非常龐大和復雜的，從這些數據中獲得有用的信息是一項非常繁瑣的工作。而由于現有的時間序列算法挖掘的數據攜帶噪音，如何解決數據挖掘中的噪音問題就很有必要。

1 目標決策理論與方法

1.1 多目標決策

在多個決策者相互之間出現矛盾的情況下如何解決多目標決策問題[1-3]就需要做目標規劃、找出多個指標點、利用多屬性效用方法求解多目標問題等。在對某個決策做出選擇的時候，會預先設計出多個解決方案，在進行多目標決策時，為了能夠尋找到最優解，主要將其中剛好可以解決的問題，但不是超出及格線的解決方案剔除掉，再通過科學分析的方式將類似的解決方案進行合并，選擇幾個綜合的目標。

1.2 多目標決策的方法

在日常生活和管理中，常會遇到帶有相互矛盾指標的決策。例如成本和質量的指標矛盾關系，要想質量保持在上等水平的同時又要成本很少，這明顯是不太可能的事情，提高成本才能保證質量。為了能夠在矛盾的指標中尋找最好的決策方案，就需要用到多目標決策理論，其中多目標決策的方法有TOPSIS、層次分析法、灰色關聯分析法、簡單線性加權求和法等。該文將著重介紹模型所使用的兩種方法。

1.2.1 層次分析法AHP

層次分析法的基本思想就是通過將目標問題建立層次結構模型并結合專家建議構建判斷矩陣，從而得到最優的方案，具體的計算步驟如下：

1）構建由目標層、方案層、準則層組成的決策層級結構。

2）構造判斷矩陣。通過比例標度表（如表1所示），對兩兩層級進行互相打分。

3）計算最大特征向量、權重和特征根。

4）根據一致比率進行一致性校驗。

5）分析一致性檢驗結果，得出最好的方案。

AHP比例標度表如表1所示。

表1 AHP比例標度表

1.2.2 TOPSIS方法

TOPSIS方法又稱逼近于理想解的排序方法，是一種常用且有效的多目標決策方法。其步驟如下：首先，將源數據作歸一化處理；然后，從多個目標中通過矩陣找出最好和最壞目標；最后，利用歐氏距離來計算各個評價目標與正理想解和反理想解的距離，從而獲取各目標和理想解的貼近度，并按理想貼近度進行排序。若該值越接近1，則評價目標越接近最好目標，否則越接近最壞目標。

2 時間序列數據挖掘

時間序列是在不同時間上同一種現象相繼觀察值排列而成的一組數字序列，它以時間為標準來分析問題的[4-6]。對于時間序列數據來說，它存在于各行各業。例如金融數據、DNA序列、機器故障追蹤檢測等，因為時序性一般都是以時間為節點，所以導致了其數據是非常大的，這對數據挖掘工作造成了一定的困難，所以在進行時間序列數據挖掘的過程中，需要對時序數列進行一個排序，實際場景往往是基于一個或多個時間序列的數據，從數據中提取出時序的特征、數值、周期、趨勢，進行一系列科學的分析，從中挖掘到所需要的內容，去發現時序的規律。

3 算法構造

3.1 時間序列數據挖掘研究背景

互聯網技術的飛速發展和物聯網技術的興起，計算機時代已經慢慢步入大數據時代。隨著時間序列數據的出現，數據的容量變得越來越大，如何通過計算機從海量數據中挖掘出有用的時間序列數據是當務之急。時間序列是以時間為節點，通過節點在計算機上進行排序，計算出每個節點之間的歸屬度，然后對計算結果進行分析，但是在挖掘時間序列的過程中會出現噪聲干擾的情況，為了克服或者減小噪聲[7-8]對時間序列數據挖掘的影響，引入了依托于多目標決策的時間序列數據挖掘算法。

3.2 多目標決策方式在時間序列數據挖掘算法的應用

多目標決策理論一向極富挑戰性，且非常活躍，在多目標決策過程中，要關注決策背景[9-10]，在面對多個目標之間出現沖突的時候，要對矛盾和分歧進行考慮，在解決問題的時候要考慮到統籌學、統計學、管理學等多個學科交叉，排序出多個方法理論體系，將排序提出的多個方法運用在多目標決策理論的基礎上，再對時間序列數據進行深度[11-12]挖掘，得到想要的內容。

該文以國家歷史宏觀經濟指標為基礎，通過采用TOPSIS方法和層次分析法AHP計算出國家年度的貼近度并排序，使用熵權法確定時間序列的權重，用K-means聚類[13-14]方法對國家貼近度聚類，進行敏感度分析后確定模型的好壞來判斷是否計算加速比。具體步驟如下：

1）構建初始矩陣

選擇m個評價指標和n個評價對象，并構成矩陣。其中，效益指標和效用指標的公式分別為：

標準矩陣為：

2）AHP確定指標權重

由于AHP主觀因素占據較大比重，所以采用一致性檢驗的方法來避免評價不準確情況的發生。

3）加權標準化矩陣

根據式（1）和式（2）得到加權標準化矩陣：

由上述過程可以得到標準化矩陣到正理想解的距離為：

標準化矩陣到負理想解的距離為：

4）時間序列處理

在信息論中，熵越大對應的不確定性就越大。將熵引入時間序列中，其反映各評價對象在某一時間上和所有時間內的差異。對此，可引入線性規劃，得實際貼近度：

其中，vk表示各個時期的權重，k表示時期數，γ表示時期的重要性，并且其值在0～1之間，其值越接近于1，表示非常重視遠期數據，否則相反。

5）K-means聚類

K-means聚類是以距離為依據的分類方法，可直接劃分出結果?？芍苯訉⑸鲜龅玫降膰倚в弥颠M行排序，對排序結果進行聚類，對聚類的結果計算加速比，其中，p表示節點數量，T1表示順序執行算法的時間，Tp表示當有p個節點時，并行算法所執行的時間。

4 實驗結果仿真

4.1 實驗數據

該文選取的是1990-2006年間世界銀行公布的32個國家，其中歐洲、亞洲、美洲和澳洲的國家分別有17、7、6、2個，考慮到模型的有效實施，不考慮發生的突發事件等因素。

4.2 實驗目標

文中提出基于多目標決策時間序列數據挖掘方法，對國家主權信用違約風險進行了定量分析，預通過模型發現高危的國家（效用值最低），來分析經濟危機時的國家信用風險情況。

通過實驗發現，目標國家中的8個高風險國家和6個低風險國家是穩定不變的，說明具有高的主權違約風險的國家，有較大可能出現主權。對比次貸危機后主權信用違約[15]發生的實際情況，可以看到幾乎與模型結果一致。用K-means聚類方法來對國家貼近度聚類，進行敏感度分析后確定模型的好壞來判斷是否計算加速比，聚類結果如圖1所示。

圖1 K-means聚類結果

4.3 實驗結果

通過聚類分析方法得到具有良好效果的多目標決策方法TOPSIS和AHP，但是為了保證依托于多目標決策的時間序列數據挖掘算法的整體是有效的，該文選擇在Hadoop平臺上進行可擴展性和加速比的測試。

加速比主要是測量數據處理規模和計算資源增長時，算法的處理能力。例如在處理數據時，數據的處理速度隨著數據的增多和變復雜也在同時不斷優化、加速，這就表明加速比好，該文將多個時間序列數據挖掘的方式的加速比進行對比，分別為基于多目標決策、基于中心度和基于時空模式，如圖2～4所示。

圖2 基于多目標決策的時間序列數據挖掘算法的加速比

圖3 基于中心度的時間序列數據挖掘算法的加速比

圖4 基于時空模式的時間序列數據挖掘算法的加速比

從測試結果可以清晰地看出3種方法所得結果具有明顯的差別。其中基于中心度和基于時空模式的時間序列數據挖掘算法都較為明顯地偏離了理想結果，并且比較雜亂，無明顯規律，而基于多目標決策與理想結果偏差很小，并且呈線性增長。此外在處理相同數據量時，在理想結果下后兩者所需要的處理時間比采用多目標決策方法所需的處理時間多很多。這就表明基于多目標決策的時間序列數據挖掘算法的加速比很高，因為這種算法在進行時間序列數據挖掘的時候，減少了噪聲對數據挖掘的影響，提高了時間序列數據挖掘算法的加速比。

然而隨著硬件的增加，在數據挖掘中算法處理資源時，若所用的時間呈線性減少則表明算法具有良好的擴展性。為了證明基于多目標決策的時間序列數據挖掘算法具有很好的擴展性，該文將基于多目標決策、基于時空模式、基于中心度這3種方式進行對比，來證明基于多目標決策的優勢[16]。如圖5所示。

分析圖5可以發現，基于中心度和時空模式的時間序列算法圖線都在基于多目標決策時間序列算法之上，說明前兩者所用時間要明顯大于后者。此外也可以發現基于時空模式和基于中心度的時間序列數據挖掘算法所需要的時間隨著節點的增加而增多，但是基于多目標決策的時間序列數據挖掘算法隨著節點的增加呈下降的趨勢，由此可以證明基于多目標決策的時間序列數據挖掘算法具有很好的擴展性，是其他兩個方式不能比擬的。

圖5 3種不同時間序列數據挖掘算法所用時間對比

4.4 實驗評估

為了驗證模型的有效性，進行敏感性分析。發現改變任意一個權重，不影響排序的結果。而TOPSIS方法是動態的，所以通過敏感性分析可以進一步研究動態TOPSIS模型的權重參數的臨界值，尋找關鍵指標的變化區間，對模型參數的適用性進行分析，提高該模型的魯棒性。以國外直接投資為例發現其區間為[0.08,1]，即該區間內的取值將不影響其國家主權信用風險[16]排序。由此可以發現使用多目標決策方法TOPSIS得到的效果是良好的，可證明所建模型具有很強的魯棒性。

5 結束語

時間序列數據不同于傳統的數據，它是以時間為節點的，在進行數據挖掘時也是按照時間順序挖掘的。在時間軸下，時間序列數據的分布比較離散和稀疏，在數據的挖掘過程中會受到很多噪音干擾，通過3種方式來進行時間序列數據挖掘，得出基于多目標決策的時間序列數據挖掘算法是最適合的，是最能挖掘出有效信息的，效率也是最高的。而該文的不足之處在于只是研究眾多領域數據中的金融數據，并沒有將其他領域如醫學領域數據進行實驗并驗證，所以下一步工作是將不同領域的數據代入模型進行實驗和分析，并探索不同的多目標決策分析方法，對比不同的聚類方法，得到最佳的模型。