基于最小二乘法的粒度決策演化模型預(yù)測方法

摘 要：粗糙集理論是一種處理不確定知識的數(shù)學(xué)工具，目前在時(shí)間序列數(shù)據(jù)的研究已經(jīng)取得了一定的成果，但這些研究都停留在靜態(tài)表的基礎(chǔ)上，在實(shí)際應(yīng)用中有著明顯的局限性。該文研究多粒度時(shí)間序列下各個(gè)粒度所產(chǎn)生的決策間的相互關(guān)聯(lián)性，在粒度決策演化模型的基礎(chǔ)上，利用最小二乘法設(shè)計(jì)了新的預(yù)測方法，通過實(shí)例驗(yàn)證了算法適合于該模型的預(yù)測，具有良好的效果。

關(guān)鍵詞：粗糙集；時(shí)間序列；靜態(tài)表；粒度決策演化模型；最小二乘法

中圖分類號：TP18

利用粗糙集理論[1]對形成的靜態(tài)決策表信息系統(tǒng)[2，3]進(jìn)行屬性約簡和規(guī)則提取是一個(gè)有效處理數(shù)據(jù)的方法。文獻(xiàn)[4]雖然在決策信息表中考慮到了時(shí)態(tài)屬性，但仍然落腳在靜態(tài)表上，沒有研究決策信息表的演化性；在時(shí)態(tài)數(shù)據(jù)方面，文獻(xiàn)[5-8]在時(shí)間序列數(shù)據(jù)挖掘和預(yù)測相關(guān)領(lǐng)域進(jìn)行了研究。針對具有時(shí)間序列特征的決策表信息系統(tǒng)，引入多重時(shí)間粒度[9]，并對其性質(zhì)和發(fā)展趨勢進(jìn)行研究，建立了粒度決策演化模型。有關(guān)文獻(xiàn)研究了移動平均和回歸分析算法，但移動平均的數(shù)據(jù)擬合度不太好，回歸分析的計(jì)算比較復(fù)雜。因此本文在粒度決策演化模型的基礎(chǔ)上，結(jié)合最小二乘法[10]設(shè)計(jì)了模型的預(yù)測方法，相對于回歸分析[11]，該算法降低了復(fù)雜度，提高了數(shù)據(jù)的擬合度。

1 相關(guān)理論

本部分主要是粒度決策演化模型的定義和性質(zhì)，具體的定義和性質(zhì)參考文獻(xiàn)[12，13]。

定義1：在時(shí)間點(diǎn)Xi、Xi+1下，設(shè)決策信息系統(tǒng)SXi=（U，CXi∪DXi），SXi+1=（U，CXi+1∪DXi+1），SXi的值域分別為VcXi和VdXi；SXi+1值域分別為VcXi+1和VdXi+1，其中c∈CXi+1，d∈DXi+1，若滿足：

（1）CXi+1=CXi；

（2）DXi+1=DXi；

（3）VcXi+1=VcXi；

（4）VdXi+1=VdXi；

則稱決策信息系統(tǒng)SXi到?jīng)Q策信息系統(tǒng)SXi+1的變化為同源演化；否則稱為多源演化。

定義2：設(shè)決策信息系統(tǒng)S在時(shí)間序列上相鄰的兩個(gè)粒度區(qū)間為gi和gi+1，由gi和gi+1得到具有相同決策屬性值的決策規(guī)則分別記為Decision_lgi和Decision_lgi+1，gi+1相對于gi的屬性繼承度InA（gi+1|gi）（簡稱屬性繼承度）記為：

（1）

其中，∣Decision_lgic⌒Decision_lgi+1c∣表示Decision_lgi+1和Decision_lgi中具有相同條件屬性c的個(gè)數(shù)，∣Decision_lgi∣表示Decision_lgi的所有條件屬性的個(gè)數(shù)。

定義3：設(shè)決策信息系統(tǒng)S在時(shí)間序列上相鄰的兩個(gè)粒度區(qū)間為gi和gi+1，由gi和gi+1得到具有相同決策屬性值的決策規(guī)則分別記為Decision_lgi和Decision_lgi+1，gi+1相對于gi的屬性值繼承度InAV（gi+1|gi）（簡稱屬性值繼承度）記為：

（2）

其中，∣Decision_lgi+1cv⌒Decision_lgicv∣表示Decision_lgi+1和Decision_lgi中具有相同條件屬性并且屬性值相同的條件屬性cv的個(gè)數(shù)。

定義4：設(shè)由粒度gi推出的決策規(guī)則Decision_l中存在條件屬性c，c相對于決策規(guī)則Decision_l的支持度Sup_D（c|Decision_l）（簡稱屬性支持度）記為：

（3）

其中，∣Decision_lc∣表示條件屬性c在所有決策屬性值為Decision_l的決策規(guī)則中出現(xiàn)的次數(shù)，∣Decision_l∣表示所有決策規(guī)則的總數(shù)。

定義5：設(shè)由粒度gi推出的決策規(guī)則Decision_l中存在條件屬性c，屬性值為cv，則條件屬性c的屬性值cv相對于決策規(guī)則Decision_l的支持度Sup_DV（cv|Decision_l）（簡稱屬性值支持度）記為：

（4）

其中，∣Decision_lcv∣表示條件屬性c所對應(yīng)的屬性值cv在所有決策屬性值為Decision_l的決策規(guī)則中出現(xiàn)的次數(shù)。

定義6：對決策規(guī)則所有的Decision_l的支持度Sup_D（c|Decision_l）=1的條件屬性組成的集合稱為決策規(guī)則Decision_l的屬性支持核，記為coreS（Decision_l）。

定義7：對決策規(guī)則所有的Decision_l的屬性值支持度Sup_DV（cv|Decision_l）=1的條件屬性值組成的集合稱為決策規(guī)則Decision_l的屬性值支持核，記為coreSV（Decision_l）。

性質(zhì)1：決策規(guī)則Decision_l的屬性支持核在時(shí)間點(diǎn)Xi和Xi+1分別為coreSXi（Decision_l）和coreSXi+1（Decision_l），則有coreSXi（Decision_l）coreSXi+1（Decision_l）。

性質(zhì)2：決策規(guī)則Decision_l的屬性值支持核在時(shí)間點(diǎn)Xi和Xi+1分別為coreSVXi（Decision_l）和coreSVXi+1（Decision_l），則有coreSVXi（Decision_l）coreSVXi+1（Decision_l）。

性質(zhì)3：在時(shí)間點(diǎn)Xi下，c1，c2coreSXi（Decision_l），cv1，cv2coreSVXi（Decision_l），若有Sup_DXi（c2|Decision_l）﹤Sup_DXi（c1|Decision_l），Sup_DV（cv2|Decision_l）﹤Sup_DVXi（cv1|Decision_l），則prio（c2）﹤prio（c1），prio（cv2）﹤prio（cv1），其中prio（c）表示屬性c的優(yōu)先級。

2 基于最小二乘法的決策演化模型方法

2.1 基于決策演化模型的最小二乘法

定義8：設(shè)在總體數(shù)據(jù)中，影響粒度決策演化模型的預(yù)測值y變化的因素完全可以由自變量x以線性形式解釋，即粒度決策演化模型可以表示成y隨x線性變化的關(guān)系，n對觀測值（xi，yi）之間的關(guān)系符合yi=β0+β1xi+εi（i=1，2…n），這里xi表示粒gi和粒gi+1之間進(jìn)行比較，且xi=i，yi表示對應(yīng)的預(yù)測值。xi，yi是一個(gè)隨機(jī)變量，它的隨機(jī)性是由εi造成的，當(dāng)x取xi時(shí)，相應(yīng)的yi來自于一個(gè)概率分布，它的均值：

E（yi）=E（β0+β1xi+εi）=β0+β1xi （5）

即E（yi|xi）由于無法對全部數(shù)據(jù)進(jìn)行研究，只能通過一次抽樣來估計(jì)β0和β1，記β0、β1的估計(jì)值為=b0，=b1，假定通過某一方法找到了b0，b1，則有線性估計(jì)方程：

=b0+b1xi（i=1，2…n） （6）

與實(shí)際觀測值yi的偏差記為ei，即ei=（yi-），要達(dá)到好的預(yù)測效果應(yīng)使殘差的平方和最小。即∑ei2=∑（yi-）2=∑（yi-b0-b1xi）2→min，分別求關(guān)于b0，b1的偏導(dǎo)數(shù)，并令之為零，解出b0，b1，這就是基于最小二乘法的粒度決策演化模型預(yù)測方法。其求解的公式如下：

， （7）

， （8）

， （9）

， （10）

測定系數(shù)[14]是指可解釋的變異占總變異的百分比，用R2表示，有[10]

（11）

從測定系數(shù)的定義看，R2性質(zhì)如下：

（1）0≤R≤1。

（2）當(dāng)R=1時(shí)，SSE=SST，原數(shù)據(jù)的總變異完全可以由擬合值的變異來解釋，并且殘差為零（SSE=0），即擬合數(shù)據(jù)與原數(shù)據(jù)完全吻合。

（3）當(dāng)R=0時(shí)，回歸方程完全不能解釋原數(shù)據(jù)的總變異，y的變異完全由與無關(guān)的因素引起，SSE=SST。從相關(guān)度來看，擬合變量與原變量y的相關(guān)度越大，擬合直線的優(yōu)良度就越高。

2.2 基于最小二乘法的決策演化模型預(yù)測方法

結(jié)合粒度決策演化模型和最小二乘法，本文提出了最小二乘法預(yù)測方法（LSMPre），用以預(yù)測下一個(gè)粒度相應(yīng)的決策規(guī)則和粒度屬性值。具體步驟如下：

輸入：決策信息表S=（U，C∪D）。

輸出：下一粒度相應(yīng)決策規(guī)則和預(yù)測值。

步驟1：使用傳統(tǒng)靜態(tài)表的規(guī)則對每個(gè)子粒gi進(jìn)行提取得到相應(yīng)的決策規(guī)則。

步驟2：整理決策規(guī)則，把具有相同決策屬性值的決策規(guī)則歸納在一起構(gòu)成新的決策樹。

步驟3：設(shè)置初始計(jì)數(shù)器：i=1。

步驟4：處理第i個(gè)決策下的所有決策規(guī)則，計(jì)算每個(gè)屬性的屬性繼承度和屬性值繼承度。

步驟5：根據(jù)求得的兩兩相鄰粒度決策中條件元素形成新的數(shù)列，xi表示粒gi和粒gi+1之間進(jìn)行比較，且xi=i，yi表示對應(yīng)的屬性繼承度。

步驟6：應(yīng)用公式（6）求條件屬性在下一個(gè)時(shí)間粒的InA（gi+1|gi）。

步驟7：依據(jù)求得的兩兩相鄰粒度決策中條件元素形成新的數(shù)列，xi表示同上，yi表示對應(yīng)的屬性值繼承度。

步驟8：應(yīng)用公式（6）求條件屬性值，計(jì)算下一個(gè)時(shí)間粒的InAV（gi+1|gi）。

步驟9：If i

步驟10：依據(jù)計(jì)算的不同決策屬性值下各個(gè)條件屬性的InA，InAV及Sup_D，Sup_DV，計(jì)算得到下一個(gè)粒度時(shí)間的InA和InAV，預(yù)測下一個(gè)時(shí)間粒可能出現(xiàn)的決策。

步驟11：輸出這些決策和預(yù)測值，并根據(jù)預(yù)測值和測量值繪出效果對比圖。

分析知算法的時(shí)間復(fù)雜度為O（n）。

3 實(shí)例研究

文獻(xiàn)[9]和[11]分別利用移動平均和回歸分析對數(shù)據(jù)進(jìn)行預(yù)測，但復(fù)雜度和數(shù)據(jù)擬合度不太好。因此本文在粒度決策演化模型的基礎(chǔ)上提出了最小二乘法，并用實(shí)例來驗(yàn)證其效果。

設(shè)決策信息系統(tǒng)S=（U，C∪D），條件屬性C={m，n，x，y，z}，決策屬性D={ ?}，每個(gè)屬性的值域?yàn)閧0，1，2}。運(yùn)行LSMPre步驟1將決策信息系統(tǒng)S=（U，C∪D）進(jìn)行粒度劃分得到U={g1，g2，g3，g4，g5，g6，g7，g8，g9，g10，g11}，運(yùn)行LSMPre步驟2對每個(gè)子粒度gi進(jìn)行處理，得到粒度相應(yīng)的決策規(guī)則，如表1。

表1 時(shí)間序列下各粒度的決策規(guī)則

粒度 決策規(guī)則 粒度 決策規(guī)則 粒度 決策規(guī)則

g1 mon1x1y2→f0

m2n0x2y2→f1

n2x1y2z0→f2 g2 n1x1y2→f0

m1n0x2y2z0→f1

m2n2y2z2→f2 g3 m0x1y2z2→f0

m2n0x2→f1

m2x1y2→f2

g4 m0x1y2→f0

m2x2y2z1→f1

m2x1y2z2→f2 g5 n1x1y2z0→f0

n0x2y2z2→f1

m1n2x2y1→f2 m0n1x1y2z2→f0

n1x2y2z1→f1

m1n2x2y1→f2

g6

g7 m0n1x1y1z0→f0

x2y2→f1

m2n2y1→f2 g8 m0n1x1y2z2→f0

n0y2z1→f1

m2n2y2z2→f2 g9 m0n1x1y1→f0

n0x2y2z2→f1

m1y2z1→f2

g10 x1y1→f0

n0x2z2→f1

m2y2z2→f2 g11 m0n1x1y2→f0

n1x2z2→f1

m1n2z2→f2

運(yùn)行LSMPre步驟3，將表1中具有相同決策屬性值的決策規(guī)則歸納到一起得到表2。

表2 經(jīng)過整理的粒度決策表

決策 f0 f1 f2

決策規(guī)則 mon1x1y2→f0

n1x1y2→f0

m0x1y2z2→f0

m0x1y2→f0

n1x1y2z0→f0

m0n1x1y2z2→f0

m0n1x1y1z0→f0

m0n1x1y2z2→f0

m0n1x1y1→f0

x1y1→f0

m0n1x1y2→f0 m2n0x2y2→f1

m1n0x2y2z0→f1

m2n0x2→f1

m2x2y2z1→f1

n0x2y2z2→f1

n1x2y2z1→f1

x2y2→f1

n0y2z1→f1

n0x2y2z2→f1

n0x2z2→f1

n1x2z2→f1 n2x1y2z0→f2

m2n2y2z2→f2

m2x1y2→f2

m2x1y2z2→f2

m1n2x2y1→f2

m1n2x2y1→f2

m2n2y1→f2

m2n2y2z2→f2

m1y2z1→f2

m2y2z2→f2

m1n2z2→f2

由實(shí)例知LSMPre步驟4外層循環(huán)為for（i=1；i≤n；i++）（n=4）。當(dāng)n=1時(shí)表示對決策f0進(jìn)行處理。

運(yùn)行LSMPre步驟5，在決策f0下屬性繼承度分別為：InA（g2|g1）=3/4，InA（g3|g2）=2/3，InA（g4|g3）=3/4，InA（g5|g4）=2/3；屬性值繼承度分別為：InAV（g2|g1）=3/4，InAV（g3|g2）=2/3，InAV（g4|g3）=3/4，InAV（g5|g4）=2/3。

當(dāng)i=3時(shí)，運(yùn)行LSMPre步驟6得新生數(shù)列1={（x1=1，y1=3/4），（x2=2，y2=2/3）}。運(yùn)行LSMPre步驟7，得：b1=-1/12，b0=20/24，，e3=1/12，R2=1。

當(dāng)i=4時(shí)，運(yùn)行LSMPre步驟6得新生數(shù)列1={（x1=1，y1=3/4），（x2=2，y2=2/3），（x3=3，y3=3/4）}。

由新生數(shù)列1的數(shù)據(jù)，運(yùn)行LSMPre步驟7和步驟8，得：

b1=0，b0=13/18，，e4=1/18，R2=0.9。

同理可得，=0.67，e5=0；=0.65，e6=0.05；=0.60，e7=0；=0.59，e8=0.01；=0.56，e9=0.04；運(yùn)行LSMPre步驟9，并繪出表3和數(shù)據(jù)擬合效果圖1：

表3 真實(shí)值與預(yù)測值的對比圖

i 實(shí)際值 預(yù)測值

1 0.75

2 0.67

3 0.75 0.58

4 0.67 0.72

5 0.67 0.67

6 0.60 0.65

7 0.60 0.60

8 0.60 0.59

9 0.50 0.56

圖1 數(shù)據(jù)的擬合效果

根據(jù)效果圖的趨勢可以說明此方法適合于本模型數(shù)據(jù)的預(yù)測，回到LSMPre步驟10執(zhí)行下一次循環(huán)。

由于i

4 結(jié)束語

從實(shí)例研究可知，最小二乘法適合于粒度決策演化模型的預(yù)測，相對于移動平均和回歸分析，該算法更好地貼近原始數(shù)據(jù)，計(jì)算復(fù)雜度較低，是一種比較好的預(yù)測方法，因此下一步對于在實(shí)際生活中的應(yīng)用將是研究的重點(diǎn)。

參考文獻(xiàn)：

[1]張文修，吳偉志，梁吉業(yè).粗糙集理論與方法[M].北京：科學(xué)出版社，2006：1-25.

[2]黃海，王國胤，吳渝.一種不完備信息系統(tǒng)的直接約簡方法[J].小型微型計(jì)算機(jī)系統(tǒng)，2005（10）：1761-1769.

[3]徐鳳生，李海軍.不相容決策表的求核方法[J].計(jì)算機(jī)工程與科學(xué)，2007（29）：84-85.

[4]馬志鋒，邢漢承，鄭曉妹.一種基于Rough集的時(shí)間序列數(shù)據(jù)挖掘策略[J].系統(tǒng)理論工程與實(shí)踐，2001（12）：22-29.

[5]孟志青.時(shí)態(tài)數(shù)據(jù)采掘中的時(shí)態(tài)型與時(shí)間粒度研究[J].湘潭學(xué)報(bào)（自然科學(xué)版），2000（22）：1-4.

[6]Berberidis C，Walid A G，Atallah M.Multiple and partial periodicity mining in time series databases[C]//The 15th European Conference on Artificial Intelligence.Lyon，F(xiàn)rance：IOS Press，2002：370-374.

[7]國宏偉，劉燕馳.多變量時(shí)間序列的模糊決策樹挖掘[J].計(jì)算機(jī)應(yīng)用研究，2009（26）：54-55.

[8]胡玉文，徐久成.時(shí)間序列下決策表信息系統(tǒng)的最終形態(tài)研究[J].河南師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2010（38）：49-52.

[9]胡玉文，徐久成.多粒度時(shí)間序列下粒度決策的演化模型研究[J].計(jì)算機(jī)工程與應(yīng)用，2011（20）：117-120.

[10]王惠文.偏最小二乘回歸方法及其應(yīng)用[M].北京：國防工業(yè)出版社，1999：14-32.

[11]胡玉文，徐久成，張倩倩.決策表信息系統(tǒng)演化模型的回歸分析預(yù)測算法[J].煤炭技術(shù)，2010（09）：152-153.

[12]胡玉文，徐久成，李雙群.粒度決策演化模型的博弈選擇研究[J].計(jì)算機(jī)工程與應(yīng)用，2012（48）：51-54.

[13]胡玉文，徐久成，孫林.粒度決策演化模型的決策穩(wěn)定性研究[J].計(jì)算機(jī)科學(xué).2012（39）：233-236.

[14]郝鵬飛.我國臺風(fēng)災(zāi)害損失分類與估計(jì)[D].哈爾濱工業(yè)大學(xué)，2008（10）：43-45.

作者簡介：徐俊利（1990-），女，河南洛陽人，學(xué)生，本科，研究方向：粗糙集理論、粒計(jì)算、數(shù)據(jù)挖掘；黃博淘（1990-），男，河南林州人，學(xué)生，本科，研究方向：粗糙集理論、粒計(jì)算、數(shù)據(jù)挖掘；劉旭光（1988-），男，河南安陽人，學(xué)生，本科，研究方向：粗糙集理論、粒計(jì)算、數(shù)據(jù)挖掘。

作者單位：河南師范大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，河南新鄉(xiāng) 453007