一种自适应参数的切换回归聚类算法

郭华峰　陈德华　潘修强

(浙江工贸职业技术学院信息传媒学院　浙江 温州 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)。郭华峰，讲师，主研领域：图像处理，模式识别。陈德华，副教授。潘修强，讲师。