基于FCM快速路交通状态判别加权指数研究

1671—1815(2017)06-02-07

科学技术与工程

Science Technology and Engineering

Vol. 17 No. 6 Feb. 2017

© 2017 Sci. Tech. Engrg.

基于FCM快速路交通状态判别

加权指数研究

蔡明

(重庆交通大学交通运输学院，重庆400074)

摘要加权指数m是影响模糊C-均值聚类（fuzzy C-means，FCM )的一个关键参数，为提高快速路交通状态模糊判别性能，

针对m取值的问题，提出了一种兼顾算法判别精度和聚类效果的优选方法。该方法以流量、速度为交通状态评价参数，在不 同加权指数m和样本量；i下进行聚类分析，从算法判别精度、类内间距、类间间距、目标函数收敛性四个方面对m的最优取值 进行了深入研究。以某市快速路为例，利用MATLAB模糊逻辑工具箱分析实验数据的隶属度和聚类中心，以上四个方面在™

吴启顺蔡晓禹*

xm种组合情形下综合分析，得出快速路交通状态模糊判别m的最优取值，并进一步验证了该方法的可行性。实验结果表明，

以流量、速度为状态评价参数的快速路交通状态模糊判别，加权指数m的最佳取值为2. 25。关键词交通工程 加权指数 模糊C-均值聚类 交通状态判别 快速路中图法分类号U491; 文献标志码A

模糊C-均值聚类是目前最流行的一种无监督 聚类分析方法，已被广泛应用于模式识别、图像分 析、医学诊断等领域[1]。加权指数™是FCM算法 的一个重要参数，控制着模式在类别间的分享程度， ™的选取对算法的性能至关重要。

学者Bezdek[2]给出一个m经验范围[1. 1，5 ]， 并从物理解释上得到m = 2时最有意义;Chan和

CheUng[3]从汉字识别的应用背景获得m的最佳取

度最优，算法聚类的环境一定稳定。现以快速路交通 状态判别为背景，以算法聚类精度和效果为着眼点，

重点研究了加权指数™的最优取值，为后续FCM算 法在快速路交通状态判别中的应用提供依据。

1 FCM算法

模糊C-均值聚类（FCM)算法[6]是一种基于目 标函数最小化的聚类分析方法，该方法把聚类归结 为一个约束的非线性规划问题，通过优化求解获得 数据集的模糊划分和聚类。

设;f =丨*1,*2,.\元数据集合,卩0\\1聚 类方法就是将X划分为C个子集Si, S2，…，S„，记4 =丨叫，％，…，aj为C个子集的聚类中心,表7K 样本5对S，的隶属度，则目标函数为

c

n

Z

^

II

值范围为[1. 25,1. 75 ] ; Bezdek 和 Hathaway 等[4]从 算法收敛角度研究发现m的取值与样本数《有关， 建议m取值大于《/(«-2) ;Pal等人[5]则从聚类有 效性得到™的最佳取值区间[1. 5,2. 5 ]。

现有关于™的取值和范围大都来自实验和经 验，均为启发式，对于™的取值尚无具体优选方法。

实际应用中加权指数™多数默认取值2,缺少对m 的深入研究，这就无法保证™为2时算法聚类的精

J7cu(U,A,X) =

、满足约束条件：

•* c

X

xi ~

II

⑴

'1 ^ J ^ «

2016年7月30日收到

重庆市社会事业与民生保障

科技创新项目（cstc2015shms - ztzx30002)资助

第一作者简介:吴启顺（1992—），硕士研究生。研究方向：交通信息工程及控制。E-mail :wqs0101@ sina. com。

Z 〜=1;

i = 1

s. t. < Uy g [0,1];

n

1 矣 j 矣 n，l 矣 i 矣 c (2)*通信作者简介:蔡晓禹（1979—），博士，教授级高级工程师。研究 方向:交通网络特征与控制方法E-mail:caixiaoyu@ cqjtu. edu. cn。 引用格式:吴启顺，蔡晓禹，蔡明.基于FCM快速路交通状态判 别加权指数研究[J]•科学技术与工程，2017, 17(6) : 2—295 Wu Qishun, Cai Xiaoyu, Cai Ming. A study of weighting exponent in ex­pressway traffic state estimation based on fuzzy C-means [ J ]. Science Technology and Engineering, 2017, 17(6) ： 2—295

L

〇 <

j = i

< n ； 1 ^ i ^ c模糊聚类过程就是使目标函数最小化的迭代收

敛过程。在迭代求解最小值过程中，由La­

grange 乘数法得到：

/ / 二 x 2/(m-l)

^ = V丨 (Y,d/dk) \\ k=1 '

⑶

290

科学技术与工程

17卷

% = X (〜)'/ X (〜广

⑷

d, =

|| ； (5)式(5)中，《即样本' 与第；个聚类中心的欧式 距离。

迭代求解过程中聚类中心矩阵和隶属度矩阵都 在不断更新，直至II W+1) - F⑷|| < ^，目标函数 /rcM(t/3，Z)达到极小值，迭代终止。

2

加权指数

m影响机理

加权指数[7] m是控制着模式在模糊类间的分享 程度、影响目标函数凹凸性和收敛性的重要参数，取 值[1，〇〇]。肌取值不同，聚类的结果也不同。当m =1时，FCM算法变成硬C-均值（HCM)算法，聚类 过程是非此即彼的划分情形；当m — 〇)时，FCM算 法失去模式划分能力；当m — 1+时，FCM算法以概 率1退化为HCM算法[8]。可见，m取值不合理，势 必影响聚类的精度和效果，下面用示例对此进行 解释。

以4 J为参数的38组样本聚类分析，图1 ( a) 是m合理取值％时的聚类效果，图1(b)是m不合 理取值％ (% > %

，常见情形）时的聚类效果。

当加权指数变为％时，状态I、状态n、状 态m聚类中心均不同程度地发生了变化，此时样本 模式在类别间分享度增加。图i(b)状态n数据集 编号1、2、3的三组样本由于与状态I聚类中心距离 更为接近，由式(3)可知，三组样本隶属状态I的权 值更高，于是三组样本从状态n脱离转而进入状态

I所属的数据集，变为了状态I。状态n数据集对

状态I数据集贡献了 3组样本，原本属于状态n数

据集的样本进入了本不属于状态I的数据集当中， 算法精度下降。以上是模式在类别间的不均等分 享，存在％取值不合理时出现模式在类别间均衡分 享的情况，但最终算法精度也必然不会上升。总言 之，m改变，聚类中心一定发生变化。

聚类中心发生改变，引起样本与聚类中心间距 离的变动，当样本与聚类中心距离关系不平衡，则样 本与其对应类别的聚类中心相似度不再稳定。比较 图1(a)与图1(b)状态I聚类中心，图1(a)状态I 样本与其对应类别的聚类中心相似度稳定。相反， 图1(b)状态I样本与聚类中心相似度不稳定。以 图1(b)状态I中4号样本为例，状态I聚类中心改 变后，4号样本与聚类中心距离由L14增大到L'14，状 态I聚类中心左侧其他样本与聚类中心均变大，右 侧样本与状态I聚类中心距离变小，模糊聚类不稳 定。当以新结构的数据集聚类时，m取值不当，也就

图1

Figm取值合理与不合理聚类效果比较

. 1 Comparison of clustering results between

reasonable and unreasonable m

难以平衡好类间模式的分享过程，最终聚类结果也 就很难达到期望。

综上分析，实际应用中m的选取既应保证符合 实际的聚类精度也要具有一定的聚类稳定性。

3

加权指数

m优选方法

对于快速路交通状态判别，加权指数m的选取 既要保证符合实际的交通状态聚类精度，又要满足 良好的聚类效果，而聚类效果主要体现在类内间距、 类间间距、目标函数收敛性三个方面。为此，现兼顾

了以上四个方面，重点对快速路交通状态判别应用

w最优取值进行了研究，步骤如下。

步骤一:首先确定FCM算法进行交通状态判别

的交通参数，明确样本量〃、聚类状态数目C、有效 停止准则e，确定加权指数m的取值区间和步长， 给定若干取值。

步骤二:在〃 x m种情形下，依次采用MATLAB 模糊逻辑工具箱进行聚类分析，根据聚类中心F和 状态类别的一一对应关系，以及每组样本对应不同 聚类中心F的隶属度大小，由隶属度t/最大原则， 确定每种情形下样本的交通状态，并将聚类所得的 样本状态与实际交通状态对比，得出所有组合情形

6期

吴启顺，等:基于FCM快速路交通状态判别加权指数研究291

下交通状态判别精度。

步骤三:提取步骤二聚类中心依次计算每 种组合情形下不同交通状态的样本与其对应聚类中 心的欧式加权距离Z (类内距离加权）以及任意两组 聚类中心距离之和^ (类间距离），获得所有组合情 形下的d/Z值。

步骤四：由步骤二得到的每种组合情形目标函 数冗CM( 、迭代次数、d/Z值以及交通状态判别精度综合选出最优肌值，即同时满足目标函数值 较小，d/z值较大，交通状态判别精度较高的m值。

4实验分析

4.1算法参数及取值

道路交通状态评价常用的交通参数有速度、流

量、占有率、服务水平、延误、排队长度、排队持续时 间等，前三个参数使用率达到70%以上，是最为常 用的参数[9]。窦慧丽，等人在文献中指出速度是影 响交通流状态最大的参数，其次是占有率，之后才是 流量[1°]。蔡晓禹，蔡明在文献中指出基于流量、速 度参数组合的交通状态判别精度最高[11]。综上分 析，现采用流量、速度作为FCM算法交通状态判别 的评价参数。

文献[4]从算法收敛性角度指出加权指数m取 值受样本量影响，为全面研究快速路交通状态判别 最优m取值，实验初从某城市快速路断面中间车道 260组视频检测流量（误差< 2% )、速度（误差< 5%)数据中随机提取了 60、120、240三种样本量如 表1所示。由视频检测断面交通流特征确定聚类数 c = 4，算法停止阈值^和迭代次数均采用缺省值分 别为1CT5、100,通过启发式方法确定m取值范围 [1.25,2.5]，取值步长 0.25。

表

Table 1 1某城市快速路断面中间车道视频检测数据

some urban expressway middle lane

Video detection data from a section of

样本序号

1流量A

veh 速度/(k h-1)

224_ min _1 )33m

_320394

24263733257258302593122260272025

1917

4.2

FCM交通状态聚类分析

4.2.1交通状态判别精度

运用MATLAB模糊聚类工具箱，在《和m不同

组合情形下对上述三种样本进行聚类分析，获得18

个隶属度矩阵t/和聚类中心矩阵F，由样本矩阵、 隶属度矩阵t/和聚类中心F三者间对应关系，得到 18种情形下每个样本所属交通状态，并将算法判别 结果与实际交通状态进行比较，得到FCM算法在不 同《和m下的交通状态判别精度如表2所示。

Table 2 表

2不Accuracy of traffic state estimation

同组合情形下交通状态判别精度

in different combinations

加权指数

ni ^60n2 —120n3 —240m

准确率准确率准确率% /失误率% /% /失误率% /% /失误率%/ 1.25

60.0040.0060.0040.0073. 3326. 671.5060.0040.0063.3336.6773. 7526. 251.752. 0060.0060.0040.0040.00. 1765. 8335. 8334. 1773. 3355. 8326. 6744. 172. 2560.0040.0082. 9217.082. 50

60.0040.0069. 1730. 8365. 8334. 1768. 3331.67

样本量为60时，加权指数m取值不同，而算法 判别精度保持不变，是因为样本量较少、样本特征差 异明显，所以m的改变对算法判别精度不产生影 响。实验统计表明，不同样本量相同™值时，算法 判别精度并非全部随着™值增大而上升;相同样本 量不同m值时，算法判别精度也并非随着m值线性 变化;样本量过少，加权指数™对算法判别精度不 产生影响;样本量增加，算法判别精度整体保持上升 趋势。研究发现，™等于2.25时，算法判别精度 最好。

4. 2. 2算法聚类效果

算法聚类效果较好主要表现为类间间距较大、 类内间距较小、目标函数收敛性良好。类内间距是 样本与对应聚类中心^之间的距离，反映样本与其 对应聚类中心相似度，与聚类中心越接近，样本隶属 该聚类中心对应类别的程度越高。类间间距是聚类 中心之间的距离，每一次m值的变化，聚类中心整 体或部分都会产生位移，类间距离较大，类与类之间 的划分清晰。目标函数收敛性是算法迭代过程中随 着迭代次数增加而目标函数值始终保持在一个最 小值。

以240组样本量为例，加权指数m分别取值 2.25和2. 50时，交通状态聚类效果如图2和图3所7K〇

可以看见，随着加权指数m取值不同，图3聚 类中心位置发生了横向与纵向偏移，相邻状态之间 的边界位置发生了变化、边界线间的数据集结构也 发生改变。图2中每一状态下的聚类中心均匀分 布，图3中畅通状态下聚类中心与样本分布很不对

292

科学技术与工程

17卷

45 r Test-2.2540­35- i 30-I•域

ig 25'

%

20­

〇 样本

，

^ 15-:驪通：♦i聚i类 中心a

^®

r

叢1_

1〇5~~ir

15 20 25 30

35

^流量/(veh.miir1)

^

图2

m=2. 25下的交通状态聚类效果

^

Fig. 2 Effect of traffic state clustering at m equal 2. 25

112 23344^ ^

(

1)/■销

*图3

m = 2. 50下的交通状态聚类效果

Fig. 3 Effect of traffic state clustering at m equal 2. 50

称，畅通与较畅通状态之间的类间间距变小，致使原 本属于较畅通状态数据集的部分边缘样本，分享给 了畅通状态数据集，造成交通状态判别失误率上升。针对不同样本量相同^取值下的交通状态聚 类效果，重点在m统|取值2. 25时对其进行了 研究。

比较图4〜图6，样本量240情形时，每一状态 下的样本相对紧致，数据集结构比较规整，不同状态 边界最为清晰，可以定性判断，〃 =240时各交通状 态单位样本类内间距较小，图5较图4各状态聚类 相对发散，图4样本量为60时聚类效果比图5样本 量为120时的聚类效果总体要好。

为了准确、统一表征不同样本量、不同加权指数 下的交通状态聚类效果，从定量角度研究了类间间 距、类内间距、以及目标函数收敛性。

类间间距（《）越大，在此基础上类内间距 ()越小，即样本隶属其最近聚类中心对应的交通 状态程度越大，隶属其他交通状态的权值就越小，同 时FCM算法聚类稳定，模糊聚类效果较好，如图7 和图8所示a

Test-2.25

40

(35

1

30

备

$ %销

尜

25 ®

2

d®

-®-#-$®

1

图4 〃 = 60时的聚类效果

Fig. 4 Effect of clustering at n equal 60

Test-2.25

G—30雄

羞q

尜尜蟹

/®25%

样尜

畅本通、尜20拥® 尜 缓

类 尜通尜

1I

较杯D

51

18

、聚20 22 24 26 28 30 32 34

流量/(veh.min-1)

图5 m =

120时的聚类效果

Fig. 5 Effect of clustering at n equal 120

图6 m

= 240时的聚类效果

Fig. 6 Effect of clustering at n equal 240

提出以类间间距和^与类内距离加权总值/的 比值来作为算法整体聚类效果的一个评价指标，记 为比例系数/，/=以/。类间间距和

d = Xrj^k

k-\\

<

AT

(6)

26 28 30

期

吴启顺，等:基于FCM快速路交通状态判别加权指数研究293

32

类内加权距离

nx —,

n\\

n2Ti2

1

|)/_销

7

(V)

X nik

^ C,(j\\c G TV*)

18 16 1422

结合式（6)和式（7)创建计算程序，分别获得 60组、120组、240组样本下的类间间距和d、类内

23

图

24 25

流量

/(veh.miir1)

26 27 28 29 30

7样本与对应聚类中心间距

Fig. 7 Distance between simples and clustering centers

^3S222I221011

82086

加权距离/、比例系数/，并将/标准化后进行了比 较，如表3所示。

表3中，加权指数m取值2. 25时，/值均处于 最高水平，类与类之间相对比较分离，数据集中样本 与聚类中心之间距离关系保持紧致与稳定。

加权指数m对目标函数的收敛性的影响，主要 是通过目标函数值变化来体现的。通过对式（1)1 阶偏导，可以看出目标函数与w之间的关系：

CM(U,A9X)dJ；销

dm All <〇

IK……

u^) !g(^) 11^-

(8)式（8)表明与m之间是单调递减关系，m越

/I

22 23

图

24 25

流量

/(veh.miir1)

26 27 28 29 30

大，/rcM越小，聚类结果变模糊[1'以240组样本

为例，m为2.25时，目标函数的迭代收敛过程， /\"reM与m之间的函数关系分别如图9和图10 所示0

8

不同状态的类间间距

Fig. 8 Distance between different stste clustering centers

表3

不同组合情形下的聚类效果比较

Table 3 Comparison of clustering effect under different combinations

加权指数

m

1.251.501.752.002. 252. 50

d55.53663. 86262. 97757.08056. 67760. 348

nl = 60l42. 97249. 32949. 35342. 39741.57249. 5

0. 1660. 1660. 10. 1730. 1750. 156

，标

d

55.37254. 9ll54. 23553.61053. 00052. 349

n2 = 120l86. 787. 01492. 50482. 27480. 45680. 494

0. 1670. 1650. 1540. I7l0. 1730. 170

，标

d

88. 31488. 76988. 987. 92583. 82670. 905

n3 = 240l254. 160253.468253.152250. 100152. 1216.931

0. 1530. 1540. 1540. 1540.2420. 144

，标

Fig. 9 Iterative convergence process of objective

function value at m equal 2. 25 Fig. 10 Relationship between objective function

and weighted exponential

294

科学技术与工程

17卷

从表3和图10看，m取值2. 50虽目标函数值 最小，但是其取值不合理使得聚类效果较差。所以， 使得目标函数收敛具有真正意义的关键在于找到合 适的™，在聚类的模糊度小于一定的程度时，使

尽量小。综合分析，在算法聚类数为4、迭代次数100、迭 代停止阈值10_5的组合情形下，加权指数™取值2. 25交通状态模糊判别效果最佳。4. 2. 3 最优m取值论证

上述研究结果是以某城市快速路为例，在聚类 数目e = 4、迭代次数100、迭代停止阈值s = 1〇-5 的情形下分析所得。对于不同道路环境以及不同聚 类数目、迭代次数以及迭代停止阈值，加权指数™ 最优取值是否与上述结论一致，对此做了进一步 论证。

以该市另一条快速路为研究对象，随机选取某 断面内车道120组流量、速度视频检测数据，确定聚 类数目c = 3，迭代次数为200,迭代停止阈值10 _6, 并运用上述™优选方法，获得算法判别精度和聚类 效果如表4。

表

4

某快速路

120组样本在不同加权指数

下判别精度和聚类效果

Table 4 Accuracy and clustering effect of 120 groups

of samples from some expressway under

different weighting exponents

加权指数m

判别精度最小目标函数值

1. 2553.33/%

比例系数0. 3793 0001. 5074. 170. 3902 5001. 7574. 170. 3922 4002. 0053.330. 3802 2002. 2575.000. 3932 0002. 50

53.330. 3761 900

调整聚类数目、迭代次数以及算法迭代停止阈 值后，再次采用前述™优选方法，得到的判别精度 和聚类效果进一步证实了基于流量、速度为评价参 数的快速路交通状态模糊判别加权指数™最优取 值 2.250

5

结论

模糊c-均值聚类是理论比较成熟、运用比较广

泛的一种模糊聚类算法，加权指数m是影响交通状 态判别精度、聚类效果的关键参数之一。目前，基于 模糊C-均值聚类的交通状态判别研究中均未考虑 该参数的影响。重点从交通状态判别精度、类内间 距、类间间距以及目标函数收敛性四个方面对快速 路交通状态模糊判别最优m取值进行了深入研究。

实验结果表明：以流量、速度为参数的快速路交通状 态模糊判别，推荐m取值2. 25。文中不足之处是未以不同交通参数来验证快速 路交通状态模糊判别的最佳m是否具有普适性，以 后将进一步对算法在不同交通参数组合下快速路交 通状态模糊判别的™最优取值、最佳聚类数c进行 研究，为优化快速路交通状态模糊C-均值判别方 法、进一步提升快速路交通状态模糊判别性能提供 依据。

参考文献

1

曲福恒，崔广才，李岩芳，等.模糊聚类算法及应用.北京：国防 工业出版社，2011:61—67

Qu Fuheng, Cui Guangcai, LI Yanfang, et al. Fuzzy clustering

algorithm and applications. Beijng ： National Defense Industry Press, 2011 ：61—67

2 Bezdek J C. Pattern recognition with fuzzy objective function algorithms. New York Plenum Press, 1981 ：137 —145

3

Chan K P, Cheung Y S. Modified fuzzy isodata for the classification of handwritten Chinese characters. Proc Int Conf Chinese Comput, Singapore. 1986 ； 3 ： 61 —

4 Chan K P, Cheung Y S. Clustering of clusters. Pattern Recognition, 1992； 25(2) ：211—217

5

Pal N R, Bezdek J C. On cluster validity for the fuzzy C-means model. IEEE Transactions on Fuzzy Systems, 1995 ； 3(3)： 370—379

6

蔡静颖•模糊聚类算法及应用•北京:冶金工业出版社，2015: 39—53

Cai Jingying. Fuzzy clustering algorithm and applications. Beijing ： Metallurgical Industry Press ,2015 ：39 —53 7

石海霞，叶水生.FCM聚类算法中模糊加权指数m的优化.计算 机应用与软件，2009;26(5) :62—

Shi Haixia, Ye Shuisheng. Optimizing fuzzy weighted exponent m in fuzzy C-means algorithm. Computer Applications and Software ,2009 ； 26(5) ：62—

8

Li Y, Yu F S. A new validity function for fuzzy clustering. Proceedings of the 2009 International Conference on Computational Intelligence and Natural Computing. CINC 2009, 1 ：462—465

9

顾超然.基于模糊C均值的城市道路交通状态判别研究.北京：

北京交通大学，2012

Gu Chaoran. Research on the urban road traffic state identification based on fuzzy C-means. Beijing： Beijing Jiaotong University, 201210

窦慧丽，王国华.基于模糊聚类和判别分析的交通状态提取算 法•交通信息与安全，2010;28(2):13—15

Dou Huili, Wang Guohua. Algorithm of traffic state extraction based on fuzzy clustering and discriminant analysis. Journal of Transport 11Information and Safety ,2010 ；28 (2.) ：13 —15 蔡晓禹，蔡明基于fcm山地城市快速路交通状态判别方法

研究.公路,2016 ;61 (7) :229—233

Cai Xiaoyu, Cai Ming. Research on method of expressway traffic state estimation based on fuzzy C-means in mountain cities. Highway ,2016 ；61 (7) ：229—233 12宫改云，高新波,伍忠东.FCM聚类算法中模糊加权指数m的优

6期

吴启顺，等:基于FCM快速路交通状态判别加权指数研究

选方法.模糊系统与数学,2005;15(1) :143—147

295

Gong Gaiyun, Gao Xinbo, Wu Zhongdong. An optimal choice

method of parameter m in FCM clustering algorithm. Fuzzy Systems

and Mathematics, 2005 ； 15 (1) ： 143—147

A Study of Weighting Exponent in Expressway Traffic State

Estimation Based on Fuzzy C-Means

(School of Traffic & Transportation, Chongqing Jiaotong University, Chongqing 400074 , P. R. China)

WU Qi-shun, CAI Xiao-yu * , CAI Ming

[Abstract ] Weighting exponent m is an important parameter in fuzzy C-means (FCM) algorithm, for improving the performance of fuzzy expressway traffic state estimation, an method for accuracy of algorithm and clustering effect was proposed to optimal choice of m. Flow and velocity were selected as traffic state evaluation parameters, cluster analysis was operated under different weighting exponent m and sample size n, then an further study on optimal choice of m was made from algorithm accuracy, distance of simples to corresponding clustering centers, class distance, convergence of the objective function four aspects . Taken urban expressway as an example, MATLAB fuzzy logic of toolboxes was used to analysis membership and clustering center both of test data, a comprehensive analysis of the above four aspects was made under n by 7?i kinds of combination cases, after that optimal choice of m was determined, and then it was verified to estimate the feasibility of the method. Experimental results show that the flow and velocity as evaluation parameters of expressway traffic state fuzzy estimation, the optimal choice of weighting exponent m is 2. 25.[Key words ] traffic engineering weighting exponent fuzzy C-means traffic state estimation ex­pressway