一種自適應參數的切換回歸聚類算法

郭華峰　陳德華　潘修強

(浙江工貿職業技術學院信息傳媒學院　浙江 溫州 325003)

?

一種自適應參數的切換回歸聚類算法

郭華峰陳德華潘修強

(浙江工貿職業技術學院信息傳媒學院浙江 溫州 325003)

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

關鍵詞切換回歸模糊聚類參數優化自適應

0引言

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

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

1FCRMα算法

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

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

(1)

其中βi是待定的回歸參數。誤差度量準則采用誤差平方和：

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

(2)

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

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

于是得到模糊c回歸模型算法的目標函數：

(3)

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

(4)

βi=[XtDiX]-1XtDiY

(5)

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

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

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

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

(3) 根據式(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，轉到步驟(2)。

2FCRMα算法的參數選擇

2.1算法的自適應參數選擇

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

(6)

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

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

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

(3) 根據式(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，轉到步驟(2)。

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

2.2SAFCRM算法的收斂性分析

從算法的定義中可以發現，SAFCRM算法并沒有改變FCRM算法的目標函數，只是使用自適應的閾值對迭代中的隸屬度進行了修正。隸屬度的修正并不會改變算法的收斂性，所以SAFCRM算法的收斂性與FCRM算法的收斂性一致。

3仿真實驗

圖1　SAFCRM算法在兩條平行直線回歸中的表現

圖2　SAFCRM算法在兩條交叉直線回歸中的表現

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

表1　SAFCRM算法與FCRMα算法

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

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

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

圖3　SAFCRM算法在四條直線回歸中的表現

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

“×”：誤分類

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

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

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

表3給出了SAFCRM算法和不同α參數值FCRMα算法在圖4所示數據集中的表現結果。

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

“×”：誤分類

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

4結語

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

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

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

參考文獻

[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] 王士同, 江海峰, 陸宏鈞. 關于切換回歸的集成模糊聚類算法GFC(英文)[J]. 軟件學報, 2002, 13(10): 1905-1914.

[6] 楊小兵, 何靈敏, 孔繁勝. 切換回歸模型的抗噪音聚類算法[J]. 智能系統學報, 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] 秦蓓蓓. 基于聚類分析的魯棒自適應切換回歸算法研究[D]. 上海交通大學, 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] 廖益琴. 基于時變擴展切換回歸的股市波動組合預測研究[D]. 重慶師范大學, 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

文獻標識碼A

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

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