基于多目標(biāo)決策的時間序列數(shù)據(jù)挖掘算法

賈曉強

（渭南師范學(xué)院計算機學(xué)院，陜西 渭南 714099）

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

1 目標(biāo)決策理論與方法

1.1 多目標(biāo)決策

在多個決策者相互之間出現(xiàn)矛盾的情況下如何解決多目標(biāo)決策問題[1-3]就需要做目標(biāo)規(guī)劃、找出多個指標(biāo)點、利用多屬性效用方法求解多目標(biāo)問題等。在對某個決策做出選擇的時候，會預(yù)先設(shè)計出多個解決方案，在進行多目標(biāo)決策時，為了能夠?qū)ふ业阶顑?yōu)解，主要將其中剛好可以解決的問題，但不是超出及格線的解決方案剔除掉，再通過科學(xué)分析的方式將類似的解決方案進行合并，選擇幾個綜合的目標(biāo)。

1.2 多目標(biāo)決策的方法

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

1.2.1 層次分析法AHP

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

1）構(gòu)建由目標(biāo)層、方案層、準(zhǔn)則層組成的決策層級結(jié)構(gòu)。

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

3）計算最大特征向量、權(quán)重和特征根。

4）根據(jù)一致比率進行一致性校驗。

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

AHP比例標(biāo)度表如表1所示。

表1 AHP比例標(biāo)度表

1.2.2 TOPSIS方法

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

2 時間序列數(shù)據(jù)挖掘

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

3 算法構(gòu)造

3.1 時間序列數(shù)據(jù)挖掘研究背景

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

3.2 多目標(biāo)決策方式在時間序列數(shù)據(jù)挖掘算法的應(yīng)用

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

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

1）構(gòu)建初始矩陣

選擇m個評價指標(biāo)和n個評價對象，并構(gòu)成矩陣。其中，效益指標(biāo)和效用指標(biāo)的公式分別為：

標(biāo)準(zhǔn)矩陣為：

2）AHP確定指標(biāo)權(quán)重

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

3）加權(quán)標(biāo)準(zhǔn)化矩陣

根據(jù)式（1）和式（2）得到加權(quán)標(biāo)準(zhǔn)化矩陣：

由上述過程可以得到標(biāo)準(zhǔn)化矩陣到正理想解的距離為：

標(biāo)準(zhǔn)化矩陣到負理想解的距離為：

4）時間序列處理

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

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

5）K-means聚類

K-means聚類是以距離為依據(jù)的分類方法，可直接劃分出結(jié)果。可直接將上述得到的國家效用值進行排序，對排序結(jié)果進行聚類，對聚類的結(jié)果計算加速比，其中，p表示節(jié)點數(shù)量，T1表示順序執(zhí)行算法的時間，Tp表示當(dāng)有p個節(jié)點時，并行算法所執(zhí)行的時間。

4 實驗結(jié)果仿真

4.1 實驗數(shù)據(jù)

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

4.2 實驗?zāi)繕?biāo)

文中提出基于多目標(biāo)決策時間序列數(shù)據(jù)挖掘方法，對國家主權(quán)信用違約風(fēng)險進行了定量分析，預(yù)通過模型發(fā)現(xiàn)高危的國家（效用值最低），來分析經(jīng)濟危機時的國家信用風(fēng)險情況。

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

圖1 K-means聚類結(jié)果

4.3 實驗結(jié)果

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

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

圖2 基于多目標(biāo)決策的時間序列數(shù)據(jù)挖掘算法的加速比

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

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

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

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

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

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

4.4 實驗評估

為了驗證模型的有效性，進行敏感性分析。發(fā)現(xiàn)改變?nèi)我庖粋€權(quán)重，不影響排序的結(jié)果。而TOPSIS方法是動態(tài)的，所以通過敏感性分析可以進一步研究動態(tài)TOPSIS模型的權(quán)重參數(shù)的臨界值，尋找關(guān)鍵指標(biāo)的變化區(qū)間，對模型參數(shù)的適用性進行分析，提高該模型的魯棒性。以國外直接投資為例發(fā)現(xiàn)其區(qū)間為[0.08,1]，即該區(qū)間內(nèi)的取值將不影響其國家主權(quán)信用風(fēng)險[16]排序。由此可以發(fā)現(xiàn)使用多目標(biāo)決策方法TOPSIS得到的效果是良好的，可證明所建模型具有很強的魯棒性。

5 結(jié)束語

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