一種自適應(yīng)參數(shù)的切換回歸聚類算法

郭華峰　陳德華　潘修強

(浙江工貿(mào)職業(yè)技術(shù)學(xué)院信息傳媒學(xué)院　浙江 溫州 325003)

?

一種自適應(yīng)參數(shù)的切換回歸聚類算法

郭華峰陳德華潘修強

(浙江工貿(mào)職業(yè)技術(shù)學(xué)院信息傳媒學(xué)院浙江 溫州 325003)

摘要自模糊c回歸模型(FCRM)聚類算法提出以來，其在收斂速度和魯棒性等方面的改進一直是研究的熱點。為此，M.S.Yang等提出模糊c回歸模型α(FCRMα)算法，該算法引入?yún)?shù)α，對FCRM算法進行了快速迭代，提高了算法的魯棒性。然而該算法存在參數(shù)α選值的問題。針對這種情況，基于相似關(guān)系理論提出一種自適應(yīng)的α參數(shù)取值方法，得到了自適應(yīng)迭代過程的SAFCRM算法。多個實驗表明，相對于FCRMα算法，SAFCRM算法具有更強的魯棒性，收斂速度更快，得到的回歸效果也更好。

關(guān)鍵詞切換回歸模糊聚類參數(shù)優(yōu)化自適應(yīng)

0引言

回歸分析是一種確定兩個或多個變量間函數(shù)關(guān)系的統(tǒng)計分析方法。單一回歸模型常常被用于對簡單數(shù)據(jù)集的擬合，探索數(shù)據(jù)的演變規(guī)律。然而，有時候數(shù)據(jù)集不止包含一個回歸模型，而是多個簡單回歸模型組合而成的混合回歸模型，這種模型被稱為切換回歸模型。Quandt和Chow最先開始了切換回歸模型的研究[1-3]，并應(yīng)用于經(jīng)濟領(lǐng)域，其后，Hathaway和Bezdek首次把模糊c均值FCM(Fuzzy c-means)算法的內(nèi)容結(jié)合到切換回歸模型中，提出了模糊c回歸模型(FCRM)聚類算法[4]。由于FCRM算法的應(yīng)用效果非常顯著，吸引了研究者越來越多的目光。

文獻[5]在FCRM算法基礎(chǔ)上，結(jié)合引力聚類算法GC，提出了新的集成模糊聚類算法GFC，提高了算法的收斂速度。文獻[6]從加強FCRM算法抗噪性的角度提出了一種新的抗噪音聚類算法，該算法可以有效地克服噪音數(shù)據(jù)的影響。文獻[7]提出了一種MCR算法，在一定程度上解決了FCRM算法初始值依賴的問題。文獻[8]從FCRM算法的收斂速度、計算數(shù)據(jù)量、類別數(shù)估計和算法魯棒性等角度提出了多種改進方案。文獻[9]在FCRM算法中引入?yún)?shù)α，提出了一種FCRMα算法，相對于其他算法，F(xiàn)CRMα使用參數(shù)α減少迭代次數(shù)，進一步加快了收斂速度，增強了算法的魯棒性。然而FCRMα并不完善，還有一些關(guān)鍵的問題等待解決。

1FCRMα算法

假設(shè)數(shù)據(jù)集S={(xk,yk)|k=1,2,…,n}，xk∈Rp,yk∈R是待分類的一系列輸入輸出數(shù)據(jù)對，S來自c個不同的回歸模型：

y=fi(x,βi)+εii=1,2,…,c

(1)

其中βi是待定的回歸參數(shù)。誤差度量準(zhǔn)則采用誤差平方和：

Eik(βi)=‖fi(xk,βi)-yk‖2

(2)

參照FCM算法，引入隸屬度矩陣:

Uik代表數(shù)據(jù)集中第k個變量隸屬第i個回歸模型的程度。

于是得到模糊c回歸模型算法的目標(biāo)函數(shù)：

(3)

其中m∈(1,∞)是一個可以控制回歸結(jié)果模糊程度的常數(shù)，最小化函數(shù)JFCRM可得到更新方程：

(4)

βi=[XtDiX]-1XtDiY

(5)

用迭代方法求解式(4)和式(5)，直至算法收斂，就是FCRM算法。

FCRMα算法在FCRM基礎(chǔ)上引入了參數(shù)α，加快了算法的迭代速度。算法步驟如下：

(1) 確定模糊參數(shù)m和回歸模型數(shù)c，設(shè)置迭代次數(shù)l=0，終止迭代參數(shù)ε>0，并初始化隸屬度矩陣U(0)，給定參數(shù)α，0.5≤α≤1;

(2) 根據(jù)式(5)計算βi；

(3) 根據(jù)式(2)計算Eik，更新U(l)→U(l+1)，使其滿足：

如果Eik>0(1≤i≤c)，則代入式(4)計算U(l+1)，

(5) 查看迭代終止條件，如果‖U(l)-U(l+1)‖<ε，迭代終止，否則l=l+1，轉(zhuǎn)到步驟(2)。

2FCRMα算法的參數(shù)選擇

2.1算法的自適應(yīng)參數(shù)選擇

考慮最簡單的一個樣本點隸屬兩個聚類中心點的情況，假設(shè)x為樣本點，m1，m2為聚類中心。樣本點x與聚類中心點m1和m2的隸屬關(guān)系之所以難確定，是因為根據(jù)模糊關(guān)系理論，聚類中心點m1和m2之間也有一定的相似性，同時具有一定的相似度值。只有當(dāng)隸屬度大過聚類中心點之間的相似度值才可以最終確定樣本點的隸屬關(guān)系。所以參數(shù)α的值可以從相似度的角度來推導(dǎo)。

(6)

式(6)提供的參數(shù)α的值將隨著迭代結(jié)果的更新自動變化，新的算法步驟如下：

(1) 確定模糊參數(shù)m和回歸模型數(shù)c，設(shè)置迭代次數(shù)l=0，終止迭代參數(shù)ε，并初始化隸屬度矩陣U(0);

(2) 根據(jù)式(5)計算βi，根據(jù)式(6)計算α;

(3) 根據(jù)式(2)計算Eik，更新U(l)→U(l+1)，使其滿足：

如果Eik>0(1≤i≤c)，則代入式(4)計算U(l+1)，

(5) 如果‖U(l)-U(l+1)‖<ε，迭代終止，否則l=l+1，轉(zhuǎn)到步驟(2)。

新算法跟原FCRMα算法步驟上基本一致，區(qū)別在于在步驟(2)中加入了對參數(shù)α的計算。因為參數(shù)α的值是由式(6)自動計算的，每次迭代根據(jù)具體情況各不相同，使得新算法更加靈活，執(zhí)行效率更好。由于α參數(shù)的自適應(yīng)特性，新算法可以命名為SelfAdaptingFCRM，簡稱SAFCRM。

2.2SAFCRM算法的收斂性分析

從算法的定義中可以發(fā)現(xiàn)，SAFCRM算法并沒有改變FCRM算法的目標(biāo)函數(shù)，只是使用自適應(yīng)的閾值對迭代中的隸屬度進行了修正。隸屬度的修正并不會改變算法的收斂性，所以SAFCRM算法的收斂性與FCRM算法的收斂性一致。

3仿真實驗

圖1　SAFCRM算法在兩條平行直線回歸中的表現(xiàn)

圖2　SAFCRM算法在兩條交叉直線回歸中的表現(xiàn)

使用文獻[9]中的數(shù)據(jù)集驗證SAFCRM算法的有效性。先考慮簡單的切換回歸模型(c=2)。圖1、圖2分別給出了SAFCRM算法在兩條平行直線和兩條交叉直線回歸時的表現(xiàn)。使用同樣的數(shù)據(jù)集，考慮m=2和m=4兩種情況，與FCRMα算法在參數(shù)α分別等于0.5、0.6、0.7、0.8、0.9、1.0時進行比較，可以得到表1所示的結(jié)果。

表1　SAFCRM算法與FCRMα算法

從表1可以看出，在迭代次數(shù)方面，不論是m=2還是m=4，SAFCRM算法只比FCRMα算法在α=0.5時迭代次數(shù)略多；由于自適應(yīng)參數(shù)α的計算需要耗費時間，SAFCRM算法在簡單數(shù)據(jù)集使用時間上的優(yōu)勢體現(xiàn)的不明顯，在m=4等較大模糊度時表現(xiàn)的更好；在MSE的表現(xiàn)上，SAFCRM算法則全部優(yōu)于FCRMα算法。由于當(dāng)α=1.0時，F(xiàn)CRMα算法等價于FCRM算法，所以SAFCRM算法在c=2時的表現(xiàn)比FCRMα算法和FCRM算法都要好。

接下來考慮c=4的情況，考慮四條交叉平行直線的回歸情況。SAFCRM算法在四條直線的回歸表現(xiàn)如圖3所示。

同樣的，在相同數(shù)據(jù)集和相同初始條件下，比較m=2和m=4時SAFCRM算法與不同α參數(shù)值FCRMα算法的回歸表現(xiàn)，可以得到如表2所示的結(jié)果。

圖3　SAFCRM算法在四條直線回歸中的表現(xiàn)

α0.50.70.91.0SAFCRMm=2迭代數(shù)1523293313使用時間0.07100.10800.13300.15300.1280MSE0.08730.08750.08770.08750.0872m=4迭代數(shù)×468510022使用時間×0.23600.43100.50700.2260MSE×0.09210.08890.08900.0873

“×”：誤分類

從表2可以看出，不論在迭代次數(shù)方面，還是在MSE方面，SAFCRM算法的表現(xiàn)都全面優(yōu)于FCRMα算法(包括FCRM算法)，在算法的使用時間上，SAFCRM算法在m=4時用時更少，說明復(fù)雜數(shù)據(jù)集情況下，SAFCRM算法使用高模糊度優(yōu)勢更大。在α某些參數(shù)值下，F(xiàn)CRMα算法會有誤分類的情況，SAFCRM算法也可以較好的避免。同時，與算法在c=2的表現(xiàn)相比較，SAFCRM在c=4的表現(xiàn)結(jié)果更優(yōu)異。這說明回歸曲線越多，SAFCRM算法的表現(xiàn)越好。

在圖3所示的數(shù)據(jù)集基礎(chǔ)上，還可以考慮加入離群點的情況。加入一個離群點(-4,7)，SAFCRM算法的表現(xiàn)如圖4所示。

圖4　SAFCRM算法在加離群點的四條直線回歸中的表現(xiàn)

表3給出了SAFCRM算法和不同α參數(shù)值FCRMα算法在圖4所示數(shù)據(jù)集中的表現(xiàn)結(jié)果。

表3　SAFCRM算法與FCRMα算法在圖4所示數(shù)據(jù)集中的回歸效果

“×”：誤分類

表3給出的結(jié)果表明，在有離群點時，SAFCRM算法的表現(xiàn)也很優(yōu)異，并全面優(yōu)于FCRMα算法，這說明相比FCRMα算法而言，SAFCRM算法有著更強的魯棒性。

4結(jié)語

切換回歸模型和模糊c回歸模型聚類算法(FCRM)的應(yīng)用十分廣泛，常被應(yīng)用于經(jīng)濟學(xué)、社會學(xué)、心理學(xué)、生物學(xué)和控制問題中。如文獻[13]就把切換回歸模型應(yīng)用于股市預(yù)測中，文獻[14]則把FCRM算法應(yīng)用到了住宅的太陽能電力分析中，文獻[15]把FCRM算法應(yīng)用于鋼廠的供應(yīng)鏈優(yōu)化中。在這些應(yīng)用中，切換回歸算法都起到了至關(guān)重要的作用。

本文基于FCRMα算法，引入相似關(guān)系理論，對參數(shù)α進行了逐步的推導(dǎo)，得到了自適應(yīng)迭代的SAFCRM算法，為切換回歸模型的估計提供了一種新的方法。

仿真實驗表明，不論回歸模型數(shù)多少，相對于FCRMα算法，SAFCRM算法都具有更快的收斂速度和更好的回歸效果。在加入離群點的情況下，SAFCRM算法的表現(xiàn)也更優(yōu)異，具有更強的魯棒性。

參考文獻

[1] Richard E Quandt. The estimation of the parameters of a linear regression system obeying two separate regimes[J]. Journal of the American Statistical Association, 1958, 53(284): 873-880.

[2] Richard E Quandt. Tests of the hypothesis that a linear regression system obeys two separate regimes[J]. Journal of the American Statistical Association, 1960, 55(290): 324-330.

[3] Chow G C. Tests of equality between sets of coefficients in two linear regressions[J]. Journal of the Econometric Society, 1960, 28(3): 591-605.

[4] Hathaway R J, Bezdek J C. Switching regression models and fuzzy clustering[J]. Transactions on Fuzzy Systems, 1993, 1(3): 195-204.

[5] 王士同, 江海峰, 陸宏鈞. 關(guān)于切換回歸的集成模糊聚類算法GFC(英文)[J]. 軟件學(xué)報, 2002, 13(10): 1905-1914.

[6] 楊小兵, 何靈敏, 孔繁勝. 切換回歸模型的抗噪音聚類算法[J]. 智能系統(tǒng)學(xué)報, 2009, 4(6): 497-501.

[7] Wu K L, Yang M S, Hsiehb J N. Mountain c-regressions method[J]. Pattern Recognition, 2010, 43(1): 86-98.

[8] 秦蓓蓓. 基于聚類分析的魯棒自適應(yīng)切換回歸算法研究[D]. 上海交通大學(xué), 2012.

[9] Yang M S, Wu K L, Hsieh J N, et al. Alpha-cut implemented fuzzy clustering algorithms and switching regressions[J]. Systems, Man, and Cybernetics, 2008, 38(3): 588-603.

[10] Zadeh L A. Similarity Relations and Fuzzy Orderings[J].Information Sciences,1971, 3(2): 177-200.

[11] Yang M S, Wu K L. A similarity-based robust clustering method [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004, 26(4): 434-448.

[12] Hung W L, Yang M S, Chen D H. Parameter selection for suppressed fuzzy c-means with an application to MRI Segmentation[J]. Pattern Recognition Letters, 2006, 27: 424-438.

[13] 廖益琴. 基于時變擴展切換回歸的股市波動組合預(yù)測研究[D]. 重慶師范大學(xué), 2010.

[14] Iwata S, Honda K, Notsu A, et al. Fuzzy c-Regression Models with direction-dependent uncertainty and its application to residential solar electric power analysis[C]//2013 IEEE International Conference on IEEE Fuzzy Systems (FUZZ), 2013: 1-5.

[15] Fazel Zarandi M H, Gamasaee R. A type-2 fuzzy system model for reducing bullwhip effects in supply chains and its application in steel manufacturing[J]. Scientia Iranica, 2013,20(3): 879-899.

A SWITCHING REGRESSION CLUSTERING ALGORITHM WITH ADAPTIVE PARAMETERS

Guo HuafengChen DehuaPan Xiuqiang

(CollegeofInformationandCommunications,ZhejiangIndustryandTradeVocationalCollege,Wenzhou325003,Zhejiang,China)

AbstractSince the presentation of fuzzy c-regression models (FCRM) clustering algorithm, the improvement on its convergence speed and robustness has been the focus of research. For this reason, M.S. Yang proposed FCRMα algorithm. In this algorithm, parameter α is introduced to expedite the iterative operation of FCRM algorithm and improves the robustness of it. However, the algorithm has the problem of parameter α selection. To solve the problem, we present an adaptive parameter α value assignation method based on similarity relation theory, and derive the SAFCRM algorithm for adaptive iteration process. Several experiments show that the SAFCRM algorithm has stronger robustness, faster convergence speed and better regression results than FCRMα algorithm.

KeywordsSwitching regressionFuzzy clusteringParameter optimisationAdaptive

中圖分類號TP301.6

文獻標(biāo)識碼A

DOI:10.3969/j.issn.1000-386x.2016.01.078

收稿日期：2013-10-20。浙江省溫州市科技計劃項目(G20130 031);浙江省高職高專院校專業(yè)領(lǐng)軍項目(lj2013146)；溫州市公益性科技計劃項目(G20140049)。郭華峰，講師，主研領(lǐng)域：圖像處理，模式識別。陳德華，副教授。潘修強，講師。