多變量時間序列的模糊決策樹挖掘
2009-01-01 00:00:00國宏偉劉燕馳梁合蘭武森
計算機應用研究 2009年1期
（北京科技大學， 北京 100083）
摘 要：針對目前時間序列決策研究方法的一些缺陷，提出了多變量時間序列模糊決策樹挖掘方法，并給出了該方法的實驗分析。實驗結果證明該方法能夠找出多變量時間序列子序列的形態與某個序列的后期趨勢或狀態的決策信息。
關鍵詞：數據挖掘; 時間序列; 模糊決策樹
中圖分類號：TP311.1 文獻標志碼：A
文章編號：10013695(2009)01005402
Multivariable time series fuzzy decision tree mining
GUO Hongwei， LIU Yanchi， LIANG Helan， WU Sen
(University of Science Technology Beijing， Beijing 100083， China)
Abstract:Focused on the limitations of the research approaches of time series decision making at present， this paper put forward an approach of multivariable time series fuzzy decision tree mining， also gave out the experimental analysis of the approach. The experimental result shows that the approach is capable of finding out the decision relationship between the subsequences pattern of multivariable time series and the future trend or state of time series.
Key words：data mining; time series; fuzzy decision tree
0 引言
時間序列研究的核心就是通過歷史的時間序列數據建立模型獲取知識，為未來的決策提供支持。傳統時間序列研究是通過時序建模的方法，主要有AR（自回歸）、MA（滑動平均）、ARMA（自回歸滑動平均）和ARIMA模型等[1]。隨著人工智能研究的深入，研究時序的方法有專家系統的時序研究[2]、人工神經網絡時序研究、基于遺傳算法的人工神經網絡時序研究、混沌與非線性理論時序研究、基于模糊理論的時序研究等[3]。但是專家系統存在知識獲取困難和推理速度慢等缺點；神經網絡雖然能實現知識的自動獲取且具有很高的推理速度，但仍存在學習收斂速度慢、知識表示隱含、推理過程隱含等不足；模糊推理雖能很好地處理模糊性和不確定性問題，但也存在模糊規則獲取困難和推理速度慢等缺陷[4]。
模糊決策樹作為一種數據挖掘方法，繼承了模糊理論和決策樹的優點，不僅具有很強的決策分析能力，而且能很好地處理模糊性和不確定性問題。另外模糊決策樹學習是以實例為基礎的歸納學習，能實現知識的自動獲取與表示，且所得的知識具有很高的推理效率[5~7]。但目前決策樹挖掘的對象多是靜態數據[8~10]，而實際中復雜系統產生的是多變量時間序列數據。因此在借鑒前人對模糊決策樹研究的基礎上，提出了多變量時間序列模糊決策樹挖掘方法，并給出了該方法的實驗分析。
1 時間序列模糊離散化
對時間序列的決策樹挖掘之前，需要對時間序列進行離散化處理。這里并非將時間序列形態進行確定性歸類，而是將每一個局部序列依據模糊原理歸入到某代表形態中[11]。
M變量時間序列為{S1，S2，…，Sm，…，SM}（1≤m≤M），設Sm=(xm1，xm2，…，xmN)為其中m變量的時間序列，將一寬度為w的時間窗作用于Sm形成一長度為w的子序列smi=(xmi，xmi+1，…，xmi+w-1)，將時間窗在時間序列Sm上從始點至終點進行單步滑移，形成一系列寬度為w的子序列sm1，sm2，…，smN-w+1，記
w(Sm，w)={smi｜i=1，2，…，N-w+1}（1）
為由該時間序列Sm用寬度w的滑窗滑出的子序列集合。
a）將w(Sm，w)看做w維歐氏空間中的N-w+1個點，并將它們隨機地分到km類中，計算每類中心。第j類的中心第l的坐標為
xmj，l=（1/h） ∑hi=1xmj，l，i l=1，2，…，w; j=1，2，…，k
（2）
b）以這些中心作為每類的代表點，計算集合w(Sm，w)中每元素smi屬第j類代表點的隸屬度函數：
μxmj(smi)=(1/‖smi-xmj‖2)1/(b-1)/∑kmc=1(1/‖smi-xmc‖2)1/(b-1) j=1，2，…，km; b＞1（3）
其中：b＞1是一個可以控制聚類結果的模糊程度常數；‖smi-xmj‖2表示每一點到第j類代表點距離的平方。
c）用當前的隸屬度函數更新計算各類中心：
xmj，l=∑N-w+1i=1[μxmj(smi)]b×xmj，l，i/∑N-w+1i=1[μxmj(smi)]bj=1，2，…，k; l=1，2，…，w（4）
重復b) c)的計算，直到各個樣本的隸屬度穩定，并將代表點集合記做Xm={xm1，xm2，…，xmkm}。其中：xmj表示m變量的時間序列的第j個代表點。
2 模糊決策樹的挖掘
決策樹是由決策屬性節點、分支（決策屬性值）和葉節點（類別標志屬性的類別）構成的以決策分析和分類為目的的樹。學習是以實例為基礎的歸納學習，模糊決策樹以不同的信任度同時沿著多個分支向前搜索，最終到達多個葉節點。當前有許多模糊決策樹學習算法，本文采用的是FID3算法。模糊決策樹FID3算法如下：
a)用戶根據實際需求以及所處理數據的特性，選擇類別標志屬性和決策樹的決策屬性集。
b)在決策屬性集中選擇具有最大信息增益(或最大熵減方向)的決策屬性作為決策樹的當前決策屬性節點。
c)根據當前決策節點屬性取值的不同，將訓練樣本數據集劃分為若干子集，即產生模糊決策樹的分支。
d)針對c)中得到的每一個子集，重復進行上述的b)c)兩個步驟，直到最后的子集符合下列三個條件之一：
（a)如果子集中某類的置信水平大于β;
（b)如果該子集是遍歷了所有決策屬性的;
（c)如果模糊信息增益小于給定值α，說明子集中的所有剩余決策屬性取值完全相同，已不能根據這些決策屬性進一步進行子集劃分。
所得的決策樹葉節點不是一個惟一的類別，而是以信任度標定的類。
e）將產生的模糊決策樹轉換成模糊產生式規則。
模糊信息增益的計算如下：
設多變量時間序列數據集為D，屬性集D中有M個時間序列變量{S1，S2，…，Sm，…，SM}，時間序列變量Sm離散化后的時間子序列為{sm1，sm2，…，smN-w+1}（1≤m≤M）。模糊決策樹挖掘選擇時間序列變量Sm在決策變量前的Tm個時序點作為挖掘的范圍，所以時間序列變量Sm有Tm個屬性，用Stm（1≤t≤Tm，1≤m≤M）表示時間序列變量Sm的第t個時序點，Stm的取值為{xmt1，xmt2，…，xmtkm}，時間序列變量Sm不同時點t具有相同的類別數km。所有類別標志屬性所要劃分的類為C={C1，C2，…，CL}。設DCl為類別Cl的數據子集，｜D｜為D中所有隸屬值的總和，則數據集D的信息熵為
I(D)=-∑Ll=1(pl×log2 pl)(5)
其中：L為分類個數；pl=｜DCi｜/｜D｜。而用Stm的類別劃分數據集D后的模糊熵為
E(Stm，D)=∑kitj=1(pmtj×I(Dxmtj))(6)
其中：Dxmtj為Stm劃分D所得的子集，且pmtj=｜Dxmtj｜/∑kmj=1Dxmtj。則屬性Stm相對于數據集D的信息增益為
G(Stm，D)=I(D)-E(Stm，D)(7)
根據式(5)～(7)就可以計算每個屬性相對于數據集的信息增益；同時根據最大信息增益原理，每次選擇信息增益最大的屬性作為當前決策屬性節點，實現對數據集的劃分，以生成模糊決策樹。
3 實驗
多變量時間序列的部分數據如圖1所示。其中變量R為類別標志屬性（有五個類別），變量S1和S2的時間序列決定變量R的類別。
對S1和S2時間序列，選擇寬度為w=3的時間窗，采用單步滑移，形成一系列寬度為w的子序列。對這些子序列進行聚類，設置k1=7，k2=6，得到圖2所示的變量S1和S2的時間子序列代表形態。設T1=3，T2=3，則可得到如表1所示的數據記錄。
表1 整理的子序列記錄
IDS1S2R
7
S11μx11(s11)=0.89S12μx26(s21)=0.88
S21μx15(s12)=0.93S22μx26(s22)=0.97
S31μx15(s13)=0.87S32μx22(s23)=0.91R3
8
S11μx15(s12)=0.93S12μx26(s22)=0.97
S21μx16(s13)=0.87S22μx22(s23)=0.91
S31μx15(s14)=0.94S32μx26(s24)=0.79R5
S11、S21、S31、S12、S22、S32作為決策屬性，R為類別標志屬性（預測屬性），采用模糊決策樹挖掘可得到如圖3所示的結果。為了顯示的方便，圖3中R變量的類別選擇了信任度最高的類別標志。從圖3的決策樹中可以看出，只用S11、S21、S12、S22、S32子序列形態就可以決策R變量的類別，而不需要S31的參與。所以多變量時間序列模糊決策樹挖掘能夠分析多變量時間序列的子序列形態的關系，找到重要的決策信息，利用建立好的變量時間序列模糊決策樹挖掘模型。根據S11、S21、S12、S22、S32子序列形態就可以預測下一時刻R變量的類別。
4 結束語
本文提出的多變量時間序列模糊決策樹挖掘方法經過實驗分析，證明該方法能夠很好地找出多變量時間序列的子序列形態與某個序列的后期趨勢或狀態的決策信息，從而為多變量時間序列的決策提供信息支持。但是本方法也有一定的局限性，當時間序列的子序列形態聚類后，類的數量太多或類別的區別不明顯時，會影響挖掘決策樹的效果。但對于研究某些特定形態模式的決策研究還是很有意義的。
參考文獻：
［1］常學將，陳敏，王明生. 時間序列分析[M].北京：高等教育出版社，1993.
[2]ADYA M， COLLOPY F，ARMSTRONG J S，et al. Automatic identification of time series features for rulebased forecasting[J]. International Journal of Forecasting， 2001，17(2):143157.
[3]NIKOLAE Y， IBAB H. Polynomial harmonic GMDH learning networks for time series modeling[J]. Neural Networks，2003，16(10):15271540.
[4]白建社，樊波，薛鈞義.基于模糊決策樹的變電站電壓無功控制方法研究[J].中國電力，2003，38(12):6265.
[5]王熙照，孫娟，楊宏偉，等.模糊決策樹算法與清晰決策樹算法的比較研究[J].計算機工程與應用，2003，39（21）:7275.
[6]YUAN Yufei， SHAW M J. Induction of fuzzy decision trees[J]. Fuzzy Sets and Systems， 1995，69(2): 125139.
[7]OLARU C， WEHENKEL L. A complete fuzzy decision tree technique[J]. Fuzzy Sets and Systems， 2003，138(2):221254.
[8]MUGAMBI E M， HUNTER A， OATLEY G， et al. Polynomialfuzzy decision tree structures for classifying medical data[J]. Knowledgebased Systems， 2004，17(24):8187.
[9]BEYNON M J， PEEL M J， TANG Yucheng. The application of fuzzy decision tree analysis in an exposition of the antecedents of audit fees[J]. Omega， 2004，32(3):231244.
[10]王煜，王正歐.基于模糊決策樹的文本分類規則抽取[J].計算機應用，2005，25(7):16341637.
[11]王炳雪.時間序列模糊關聯規則的挖掘[J].計算機工程與應用，2004，40（12）:177179.
