快速全局C-均值聚类（精选六篇）
快速全局C-均值聚类 篇1
交通状态的识别问题是属于没有先验知识情况下的分类问题,聚类分析可以解决此类问题。道路交通状态所反映的道路拥挤程度是一个模糊的概念,很难用具体数字来界定。因此有一些研究者利用模糊聚类方法进行了道路交通状态判别的研究[1,2,3]。从目前的研究现状来看,笔者认为在判别变量、样本数量、样本周期等方面还需要进一步完善。本文的研究背景是三相流理论。将采用流量、占有率和速度作为判别变量,利用能涵盖所有状态的大量样本,以及缩短样本周期为1 min的数据进行研究。应用模糊C均值聚类方法,根据广州城市快速路检测到的数据,对快速路交通流相态划分问题进行研究,试图给出适合广州快速路特点的交通状况划分的方法和关键参数,为快速路交通控制和管理提供依据。
1 三相交通流理论
近年来,德国物理学家Kerner和合作伙伴Rehborn总结了前人的研究成果,通过大量的实践和实验,发现了原本交通流理论中某些基础假设的缺陷,提出了一种基于交通流特征分析法的交通流理论——三相交通流理论[4]。三相交通流理论把实际交通流划分为3类相态:自由流、同步流和宽移动堵塞。其中同步流和宽移动堵塞同属于拥挤流。如图1所示。
自由流状态下车辆的特征表现为:当车辆密度较低时,车速较快,车辆间的间距比较理想,驾驶员的行驶自由度好。由于车辆的行驶具有一定的自由性,所以此状态下的交通流称为自由流。
同步流指随着车流密度增加,车辆间距减小,车辆的行驶速度急剧降低,不仅前后车辆间的影响增强,在多车道的道路条件下相邻车道间的车辆也会互相制约。因为在同步流产生的初始阶段,车辆为提高行驶速度,自然而然地向速度较高和密度较低的车道转移,使得相邻车道的车辆行驶速度接近一致时,车辆间的间距也趋于稳定,整个道路交通流呈现同步跟驰状态,相邻车道的车辆速度也趋向同化。
宽移动堵塞反映了车流状态跳跃式的变化情况。这种状态的样本点即图1中宽移动堵塞斜线的两端,该情况下的车辆在行驶中走走停停,不具有连续性。所以,无法用模糊聚类方法进行判别。本文仅仅对三相流理论中的自由流和同步流进行相态划分。
2 模糊C均值算法(FCM)原理
2.1 模糊C均值算法(FCM)
模糊聚类的概念最早由Ruspini提出[5]。模糊C 均值(fuzzy C-means,FCM) 聚类是一种比较典型的模糊聚类算法, 由Bezdek在1981年提出[6],用于将多维数据空间分布的数据点分成特定数目的类。在模糊聚类中,每一个数据点以某种程度属于某一类,它用隶属度来表示每个数据点属于某个聚类的程度。FCM 把n个向量xi(i=1,2,…,n)分为c个模糊组,并求每组的聚类中心数,使得非相似性指标的目标函数达到最小。
目标函数为:
式中:n为检测器采集的交通信息集经过数据标准化后得到的3个特征(流量、速度和占有率)的样本个数;c为聚类组数,也即聚类中心数;uij为U矩阵的第i行第j列,表示第j个样本属于第i个聚类中心的隶属度;V={v1,v2,v3}为聚类中心矩阵;dij=‖xj-vi‖为第i个聚类中心与第j个样本间的欧几里德距离;m为加权指数。
m∈(1, ∞),当m=1时,模糊聚类就退化为硬C均值聚类;有研究表明[7],m的最佳选择范围为1.5～2.5,通常m=2是比较理想的取值。
构造拉格朗日乘子,对所有输入参量求偏导,可得到使目标函数最小的必要条件为:
推导过程见文献[7]。
2.2 FCM的迭代过程
快速路交通流是一种不受交叉口信号干扰的连续交通流,具有随机性、模糊性等特点。基于FCM的城市快速路交通流相态划分方法的基本步骤如下:
1) 数据标准化。用极差标准化将原始样本标准化,
2) 初始化。给定聚类中心数c,设定迭代停止阈值ε,初始化聚类中心V(0),设置迭代计数器b=0。
3) 用下式计算隶属度矩阵U(b):
对于∀i,j,如果 d
如果存在i,r,使得d
4) 用下式更新聚类中心矩阵V(b+1):
5)如果‖V(b)-V(b+1)‖<ε ,则算法停止并输出隶属度矩阵U和聚类中心矩阵V,否则令b=b+1,转向步骤3,继续迭代。
3 案例结果与分析
3.1 数据采集和参数取值
数据来源于广州市城市快速路,本文选择该路的直线路段上的某点微波检测器检测到的数据。该检测器检测整个道路断面,包括最内侧车道,中间车道和最外侧车道,数据的采集周期为1 min。本文选择2005年11月22日某点检测的24 h数据,共有1 440个样本数据。模型中参数取值为m=2,c={2,3,4}。原始交通流数据如图2所示,包括车流量、时间占有率和速度。
3.2 交通相态聚类分析结果
以上数据按照2.2中的FCM分析步骤,利用Matlab语言编程求解,对样本进行多次迭代,得到聚类组数c分别为2、3、4的相态划分结果。从结果来看,只有聚类组数为3的划分结果清晰明显。限于篇幅,下面只给出组数为3的聚类结果,并对其分析。
交通状态的聚类中心:
该矩阵第1行代表流量(veh/min);第2行代表时间占有率(%);第3行代表速度(km/h)。
分类情况如图3、4、5所示,图6表示了该算法的迭代过程。
从图3、4、5中可以看出:
1) 分类结果可以明显的区分三相流理论中的自由流和拥挤流,且把自由流细分为了2类,暂记为自由流1相态(用符号*表示)和自由流2相态(用符号+表示)。
2) 时间占有率很高(大于30%),且速度很低(小于30 km/h)的交通流明显属于拥挤流相态(用符号o表示)。
3) 时间占有率小于30%和速度高于30 km/h的交通流属于自由流相态。其中,当占有率小于9%,且流量小于17 veh/min时,交通流属于自由流1相态(*);当占有率大于12%小于30%,且流量大于21 veh/min时,交通流属于自由流2相态(+);占有率介于9%～12%之间,流量介于17～21 veh/min之间的区域为过渡区域。
从上面的分析看出,拥挤流(即本文针对的同步流)能够被划分出来。一般来说,城市快速路的自由流的特性是:夜间流量小,占有率小;白天流量大,占有率大;但是2个时段的速度基本是一致的。这是由于驾驶员在自由流情况下驾驶时,除了保持车头间距,还需要控制自身的速度,不会因为离前车距离较远而一味提高车速。因此,速度对于自由流和拥挤流的划分影响最明显。
聚类组数为3时,自由流被划分为自由流1相态和自由流2相态,这2个相态可以比较清晰地聚类出Kerner的自由流相态,基于模糊C均值的点聚类可以起到线性聚类的效果。
4 结束语
交通流相态划分对于正确选择交通控制和诱导策略有非常重要的作用。以往对交通流的判断大多是根据经验性的判断,本文试图给出一种较为科学的判断方法。根据实测的快速路交通流数据,尝试用模糊C均值聚类方法对交通流相态分类进行研究。在得出了交通流相态的聚类中心以后,根据算法很容易判断新测的交通流数据属于何种交通相态。通过实验, 我们发现用模糊C均值聚类方法进行交通流相态划分是一种可行的方法, 并给出了适用于广州市快速路交通流相态划分的一些关键参数。
需要指出的是,如何对交通流所有相态进行科学的分类是一个值得深入研究的课题,模糊C 均值聚类只是其中的一种方法。该算法只是得出了该路段的2种常见的主要相态,由于Kerner提出的同步流相态和宽移动堵塞相态在流量-密度相平面图上有重叠,且后者表征为线状(J线),FCM不能得出该相态的分析结果。如何用改进的FCM算法或者基于原型的模糊聚类算法,如模糊C线(FCL)、模糊C面(FCP)、模糊C壳(FCS)或模糊C二次曲线(FCQ)等来对同步流和宽移动堵塞相态进行划分有待进一步研究。另外,本文给出的一些关键参数只是适合该段快速路, 其它快速路路段的关键参数需要根据实测交通流数据计算得出。快速路各路段的交通流相态划分是否有很大的相似性以及如何根据多点多天交通流数据判断整个路段的交通流相态也值得进一步研究。今后将探索更好的分类方法并探讨如何将其应用于快速路控制和诱导。
摘要：交通相态的识别问题是智能交通系统里一个关键问题,基于模糊C均值聚类分析可以很好地解决这种没有先验知识情况下的分类问题。文中介绍了三相流理论,根据我国实测快速路交通流数据,利用模糊C均值聚类方法对交通流相态的分类进行了研究,实现了一种交通相态的划分方法,研究结果表明:该方法能够识别出三相流理论中的自由流和同步流状态。
关键词：城市快速路,交通流,相态,模糊C均值聚类
参考文献
[1]赵风波,孙敏.基于模糊聚类分析的交通状态识别方法[J].微型电脑应用,2006,22(2):9-11
[2]任其亮,谢小淞.基于遗传动态模糊聚类的道路交通状态判定方法[J].交通运输工程与信息学报,2007,5(3):12-15
[3]陈德望.基于模糊聚类的快速路交通流状况分类[J].交通运输系统工程与信息,2005,5(1):62-67
[4]Kerner B S.The physics of traffic:Empirical free-way pattern features[C]//.Engineering applica-tions,and theory.New York,Springer Berlin,Heidelberg,2004
[5]Ruspini E H.A new approach to clustering[J].InfCont,1969,15(1):22-32
[6]Bezdek J C.Pattern recognition with fuzzy objectivefunction algorithms[M].New York:PlenumPress,1981
模糊C均值聚类算法及应用 篇2
关键词：FCM,聚类树形图,隶属度
聚类分析是一种多元统计分析方法, 属于无监督模式识别方法, 被广泛应用于模式识别、图像处理、数据分析等领域[1~3]。模糊聚类分析建立了样本对类别的不确定描述, 更能客观地反应样本的实际情况, 从而成为聚类分析的主要方法[4~5]。
在模糊聚类算法中, 模糊C均值聚类算法 (Fuzzy C-means, 简称FCM) 应用最为广泛。FCM是基于目标函数的模糊聚类算法中理论最完善、应用最广泛的一种算法。为了借助目标函数法求解聚类问题, 类内平方误差和WGSS (Within-Groups S um of Sq ua r ed E r r or) 成为聚类目标函数的普遍形式。随着模糊划分概念的提出, Dunn[6]首先将其推广到加权WGSS函数, 后来由Bezdek[7]扩展到加权WGSS的无限族, 形成了FCM聚类算法的通用聚类准则。
1模糊C均值聚类算法原理
模糊C均值聚类算法原理[8]描述如下:
F C M的聚类准则即确定U、V, 使J (U, V) 最最小。
FCM一般步骤如下:
Step2:利用下式计算第l步的聚类中心
Step3:修正隶属度矩阵 (l) U, 计算目标函数 (l) J:
Step4:判断是否满足终止条件, 满足则退出程序;否则, l=l+1, 转Step2。
2实验仿真
为了验证算法的有效性, 选取数据如表1所示。数据选自2013年《中国统计年鉴》[9]。
程序利用matlab软件编写, 具体流程如下:
Step1:利用matlab内置函数dendrogram绘制聚类树形图, 根据树形图大概确定分类数c;
Step2:初始化, m=3, =1e-6, 随机化U (0) ;
Step3:调用f cm函数。
树形图如图1所示。
由图1可知, 大体上可以分为四类, 所以c=4。调用fcm函数, 结果如下。
第一类:北京、上海、广州。
第二类:石家庄、长春、哈尔滨、福州、济南、郑州、长沙、西安。
第三类:太原、呼和浩特、合肥、厦门、南昌、南宁、海口、贵阳、昆明、拉萨、兰州、西宁、银川、乌鲁木齐。
第四类:天津、沈阳、大连、南京、杭州、宁波、青岛、武汉、深圳、重庆、成都。
3结论
由实验结果可知, FCM算法能较好地对数据样本进行分类, 但由于算法本身对初始聚类中心、初始隶属度的依赖性较强, 所以, 要使其发挥更好地作用, 则需要进一步对其进行改进。
参考文献
[1]E.Hartuv and R.Shamir, A clustering algorithm based on graph connectivity[J].Inf.Process.Lett, 2000 (76) :175-181.
[2]Laszlo M, Mukherjee S.A genetic algorithm using hyper-quadtrees for lowdimensional K-means clustering[J].IEEE Trans.Pattern Analysis and Machine Intelligence, 2006, 28 (4) :533-543.
[3]肖宇.聚类分析及其在图像处理中的应用[D].北京交通大学, 2012.
[4]J.Chiang and P.Hao, A new kernelbased fuzzy clustering approach:Support vector clustering with cell growing[J].IEEE Trans.Fuzzy Syst, 2003, 11 (4) :5 1 8-5 2 7.
[5]曾山.模糊聚类算法研究[D].华中科技大学, 2012.
[6]高新波.模糊聚类分析及其应用[M].西安电子科技大学出版社, 2004.
[7]Bezdek J C.Pattern Recognition with Fuzzy Objective Function Algorithms[M].Plenum Press, New York, 1981.
[8]何正风.MATLAB概率与数理统计分析[M].2版.机械工业出版社, 2012.
基于模糊C均值聚类的岩性识别研究 篇3
模糊C均值聚类是一种基于划分的聚类算法, 其目的是使被划分到同一簇的对象之间相似度最大, 而不同簇之间的相似度最小, 自从L.A.Zadeh教授提出模糊集理论以后, 为数据划分提供了有力的分析工具, 人们为使事物或对象之间能更好地反映现实世界, 开始用模糊的方法来处理聚类问题, 模糊C均值得到了广泛的应用。文章旨在对搜集到的测井数据进行深入分析, 提高数据辨识度与分辨率, 挖掘数据之间的深层次关系, 依据不同岩性在常规测井资料中的不同响应, 利用模糊C均值算法对井中的岩性进行自动分类, 这有利于油气藏地质特征的描述, 从而减少不合理投入, 进而提高油气藏开发效率。
1 模糊C均值聚类
模糊C均值聚类算法是基于目标函数最小这个条件的误差平方和准则算法。目标函数是Dunn按照Ruspini定义的模糊划分的概念, 把硬聚类的目标函数推广到模糊聚类上, 目标函数反映了在某种情况下的类内紧致性, 所以其值越小, 说明聚类效果越好。通过优化目标函数计算出每个样本点到聚类中心的隶属度, 根据隶属度的大小决定分类。
假设有n个样本点, 每个样本点都是s维的, 通过模糊C均值聚类算法, 按照每个样本点的物理特性不同, 将他们分为c类。
此时的目标函数表示为:
其中, dik是一种距离范数, 表示样本点xk与第i类的聚类中心vi之间的距离。uik是样本点xk属于第i类的隶属度。
迭代过程如下:
(1) 在uik上运用拉格朗日乘数法求偏导数。
(2) 运用以上公式计算由隶属度的值所组成的划分矩阵U (b) , 其中b为迭代次数。
(3) 更新聚类中心
(4) 若出现, 则算法停止, 否则转入第一步。
2数据来源及分析
文章的数据来源于川科1井, 该井经过657天钻至深度达7566.50m, 将井深5614.00m处设为编号1, 依次类推, 共提取了马鞍塘组 (5614.00m-5681.50m) 的676组数据进行实验。主要测量储层发育情况、岩性特征、电性和物性特征等。
主要测量储层发育情况、岩性特征、电性和物性特征等。
结合马鞍塘组的地质特点, 主要采用声波时差 (AC) 、补偿中子 (CNL) 、密度 (DEN) 、自然伽玛 (GR) 、浅侧向电阻率 (RS) 、自然电位 (SP) 这6种响应特征。这些参数对研究区域岩性特征反应最敏感, 是灰岩储层岩性识别最常用的测井数据。
3岩性识别
在勘探开发中, 一般来说, 测井仪器和标准刻度器的型号和使用规则不完全相同, 再加上地理位置和所处环境的变化, 使得测井数据存在系统误差。在运用测井数据进行区域化研究时, 必须对测井数据进行标准化处理。
测井曲线中包含了丰富的岩性信息, 不同的测井曲线对地层和岩性具有不同的区分度, 其差异主要取决于岩石的矿物成分、结构和岩石中所含流体的性质等, 对于一组特定的测井参数值就有一种岩性与之对应。
文章综合考虑测井参数受环境、人为因素的影响, 筛选出自然伽马、声波时差、电阻率这三种测井响应值。通过岩屑录井资料可知马鞍塘组总有四种岩性, 经过模糊C均值算法精确计算和分析得出马鞍塘组各数据点所属类别如表1。
对比岩屑录井资料和测井报告可知, 1类为泥晶白云质灰岩, 2类为泥晶含云灰岩, 3类为砂屑灰岩, 4类为灰色泥晶灰岩。
利用模糊C均值聚类对川科1井马鞍塘组岩性数据进行聚类分析的结果如图1所示, 由图1可以看出各岩性均表现出了较好的分类结果, 各组岩石基本以聚类中心为中心点分布, 识别率比较高。
文章运用Carbon Explorer地质绘图软件分析研究区域的测井数据, 得出川科1井马鞍塘组单井岩性分析图如图2所示。将FCM模糊聚类岩性与录井岩性对比, 结合各种测井曲线可知, 聚类岩性与岩屑录井岩性吻合度达85%以上。
4 结果分析
文章使用模糊C均值聚类使岩性自动分类的效果比较明显, 与已知岩屑录井资料吻合度高, 在岩性定量识别上面的可行性和有效性证明它是比较理想的一种岩性识别工具。不仅在实践工作中简便易行, 也能满足科学研究的需要。同时也存在着一些不足, 比如对初始值敏感, 容易陷入局部最优等, 充分利用其优势, 在目标函数中增加惩罚项进一步提高算法精度。
参考文献
[1]马海, 王延江, 胡睿, 等.测井岩性识别新方法研究[J].地球物理学进展, 2009 (1) .
[2]魏友华, 郭科, 许江浩.模糊C均值聚类算法在测井相分析中的应用[J].国土资源科技管理, 2012 (6) .
[3]Raz Tzvi, Yaung, Alan T.Application of Clustering Techniques to Information Systems Design[J].Information and Software Technology, 1995, 37 (3) :86.
[4]高志军, 李浪, 吴庭.聚类分析在砂岩储层评价中的应用:以王集油田东区为例[J].石油地质与工程, 2009 (5) .
[5]Bezdek J C.Pattern Recognition With Fuzzy Objective Function Algorithm[M].New York:Plenum Press, 1981.
快速全局C-均值聚类 篇4
在模糊聚类算法中,模糊C-均值(FCM)聚类算法是最著名和应用最广泛的聚类算法,尽管FCM得到了广泛的应用,却存在如下缺点:收敛速度慢,对噪声敏感,不能自动选取特征。
针对传统聚类算法对数据的各个特征平等对待,不能自动选择数据相关特征的问题,众多学者提出了基于特征加权的聚类算法[1,2]。Wang等人首先[3]提出了特征加权型FCM(WFCM),Hichem等人[4]详细讨论了WFCM聚类算法,通过用类似于FCM聚类算法中隶属函数的求解方法来计算特征权值,并将所得的WFCM算法应用于彩色图像分割和监督分类问题;李洁[5],Hung[6]和陈新泉[7]等人也从不同角度研究了特征加权的FCM聚类算法。由于WFCM算法是在原FCM算法的基础上加入特征权重的迭代计算,这便使得WFCM运行时间比FCM更长,不便于实际应用。另外实际工程应用过程中不可避免地会出现噪声但上述的特征加权FCM聚类算法都没有考虑噪声问题,这使得所提算法在实际应用过程中很难达到预期的效果。
为了进一步提高FCM的收敛速度,裴继红等人[8]基于模糊集理论中的截集概念,提出了截集模糊C-均值(SFCM)聚类算法,SFCM符合人类思维的分类习惯,能够极大地提高算法的收敛速度。Yang等人[9]进一步深入分析了SFCM,不仅证明SFCM的收敛性,并且指出SFCM能产生“聚类核”,当选取较大的模糊参数时,SFCM具有良好的对噪声不敏感性。尽管SFCM具有收敛速度快和对噪声不敏感的优点,但SFCM与FCM一样,不能自动选取特征。
鉴于WFCM能够自动选择特征,SFCM收敛速度快并对噪声不敏感,本文考虑将二者的优点相结合,提出截集型WFCM聚类(或者特征加权型SFCM聚类)。为了方便,本文采用术语:截集型WFCM聚类(SWFCM)。在WFCM算法基础上,用截集思想对WFCM产生的隶属度函数值进行修改。与SFCM和WFCM相比较,SWFCM既具有自动特征选取能力,又具有较快的收敛速度和良好的噪声稳健性,是一个有效的聚类算法
1 截集FCM算法和特征加权FCM聚类算法
众所周知,对于欧式空间RM数据集X={x1,x2,…,xN},FCM的目标函数为:
满足:
运用拉格朗日乘子法可求得JFCM(U,V)最小化的必要条件为:
FCM通过交替迭代计算式(2)和式(3)来最小化JFCM(U,V)。
截集FCM(SFCM)的基本思想较为简单,就是在原FCM算法的基础上,在FCM对隶属度的每一次迭代求解过程中加一步对隶属度值的修改:对于给定的0<α<1,如果uij=1m≤la≤xcuil>α,则令uij=1,uij′=0(j′≠j);否则隶属度函数仍按式(3)计算。
虽然SFCM是FCM经上述简单改动的算法,但是与FCM相比较,SFCM却具有更快的收敛速度和更好的对噪声稳健性。文献[8]比较了SFCM与FCM的收敛速度;文献[9]详细讨论了SFCM的稳健性,指出SFCM不但能够产生“聚类核”,而且当模糊因子取较大值时,SFCM具有良好的噪声不敏感性。
特征加权FCM(WFCM)有众多版本,这里以Hichem[4]提出的WFCM为基本算法进行讨论。Hichem运用类似FCM中隶属函数的求解方法给出特征加权FCM聚类算法中权函数的一种迭代求解算法,该算法在特征权重的计算过程中赋予不同聚类以不同特征权重,是一种局部特征加权聚类算法。用JWFCM(U,V,W)表示WFCM的目标函数,该算法的目标函数为:
满足:
WFCM通过迭代计算式(5)～式(7)来最小化式(4)。
式中:交替迭代优化式(5)～式(7)可实现最小化式(4)。
2 截集型特征加权FCM聚类算法
虽然WFCM具有自动特征选取的优点,但是由于它是在原FCM算法的基础上加了特征权值的迭代计算,所以WFCM的收敛速度较慢,不便于实际应用。而SFCM算法具有收敛速度快和噪声稳健的优点,为此,结合二者的优点,用截集方式对WFCM算法的隶属度值进行修改,提出截集型特征加权FCM(SWFCM)算法。在WFCM算法的基础上,对由式(6)计算所得的隶属度值做如下修改:
对于给定的0<α<1,如果uij=1m≤la≤xcuil>α,则令uij=1,uij′=0(j′≠j);否则隶属度值仍按式(6)计算。
SWFCM算法的描述如下:
(1)选择聚类数C,ε>0,参数β<0或β>1,参数0<α<1;选择初始聚类中心矩阵V,特征权重W;
(2)用式(6)更新隶属度矩阵U′;
(3)对给定的0<α<1,用截集方式修改隶属度矩阵得到新的隶属度矩阵U″;
(4)用式(7)更新特征权矩阵W′;
(5)用式(5)更新聚类中心矩阵V′,如果‖V′-V‖<ε,则停止;否则转到(2)。
3 实验结果及分析
为了验证本文提出SWFCM算法的有效性,这里对SFCM,WFCM和SWFCM进行对比仿真实验。在实验中,初始权重取为wjk(0)=1/M,j=1,2,…,C,k=1,2,…,M,最大迭代次数设为200。
3.1 人造数据
人造数据来自文献[10],记为data1。data1是一个四维空间{X1,X2,X3,X4}中的4类{C1,C2,C3,C4}数据,其中每一类包括100个数据点。类C1和类C2在由特征X1和特征X2构成的子空间中以正态分布的形式形成两类,而特征X3和特征X4是C1和C2的白噪声特征,类C1和类C2在每一维特征上的均值分别为μC1=[0.5,-0.5,0,0]和μC2=[-0.5,-0.5,0,0],标准差为σC1=[0.1,0.2,0.4,0.4]和σC2=[0.1,0.2,0.4,0.4];类似地,类C3和类C4在由特征X2和特征X3构成的子空间以正态分布的形式形成两类,而X1和X4是类C3和类C4的白噪声特征,类C3和类C4在每一维特征上的均值分别为μC3=[0,0.5,0.5,0]和μC4=[0,0.5,-0.5,0],标准差为σC3=[0.4,0.2,0.1,0.4]和σC4=[0.4,0.2,0.1,0.4]。data1在不同特征维数空间上的投影如图1所示。其中图1(a)为data在由特征X1和特征X2构成的子空间中的投影;图1(b)为data1在由特征X2和X3特征构成的子空间中的投影;图1(c)为data1在由特征X1和X3特征构成的子空间中的投影。
在该实验中,为了测试孤立噪声点对聚类算法的影响,在data1中加入一个孤立噪声点,坐标为(100,100,100,100),所构成的数据记为data2。为避免算法陷入局部极值,用从数据中随机选取聚类中心的方法初始聚类中心100次,三个算法用这相同的100组初始聚类中心各自运行100次选最优结果为最终聚类的结果。在该次实验中,参数α=0.3,β=3,模糊因子m=5。对加了噪声数据的分类结果如表1所示,用N,T,A分别表示三个算法迭代次数、运行时间和准确率。其中,准确率A定义为(nj表示第j类正确分类数据的个数)。
由表1可知,WFCM受噪声影响不能正确选取特征,分类准确率较低,SFCM和SWFCM受噪声影响较小准确率都高于并且能够正确选取数据的相关特征,因此可以获得很高的准确率。
3.2 真实数据
Iris数据和Breast-cancer数据来源于UCI repository of machine learning databases[11],数据特性如表2所示。
在该实验中,为避免算法陷入局部极值,用从数据中随机选取聚类中心的方法初始聚类中心100次,3个算法用这相同的100组初始聚类中心各自运行100次选最优结果作为最终聚类结果。用N,T,A分别表示3个算法迭代次数、运行时间和准确率,参数α取为0.3,β取值为2,模糊因子m取为2。对Iris数据和Breast-cancer数据的分类结果如表3和表4所示。
由表3可知,尽管WFCM和SWFCM的用时多于SFCM,由于具有自动特征选择能力,WFCM和SWFCM的准确率都高于SFCM;WFCM与SWFCM相比较,SWFCM的迭代次数更少,用时也更少。
由表4可见,SWFCM的准确率远远高于SFCM和WFCM。从迭代次数和用时来看,WSFCM比WFCM要少得多。
4 结语
基于特征加权的FCM(WFCM)聚类算法是当前聚类算法研究的热点,WFCM存在的主要缺点是:收敛速度慢,对噪声敏感。考虑到实际工程应用中不可避免会有噪声所使用的聚类算法必须对噪声不敏感为此,本文将截集FCM(SFCM)聚类算法和特征加权FCM(WFCM)聚类算法相结合,提出了截集型特征加权模糊C-均值(SWFCM)聚类算法。实验结果表明,SWFCM不仅具有良好的特征选择能力和很强的抗噪声性能,而且具有较高的收敛速度,是一种经济有效、可供选择的聚类算法
参考文献
[1]CHIEHYUAN Tsai,CHI U Chuang-cheng.Developing afeature weight self-adjust ment mechanism for a K-meansclustering algorithm[J].Computational Statistics and DataAnalysis,2008,52(10):4658-4672.
[2]JING L,NG M K,HUANG J Z.An Entropy WeightingK-Means Algorithmfor Subspace Clustering of High-di men-sional Sparse Data[J].IEEE Trans.on Knowledge and Da-ta Engineering,2007,19(8):1026-1041.
[3]WANG X Z,WANG Y D,WANG L J.I mproving fuzzyfeature C-means clustering based on feature-weight learning[J].Pattern Recognition Letters,2004,25(10):1123-1132.
[4]FRIGUI H,NASRAOUI O.Unsupervised learning of pro-totypes and attribute weights[J].Pattern Recognition,2004,37(3):567-581.
[5]李洁,高新波,焦李成.基于特征加权的模糊聚类新算法[J].电子学报,2006,34(1):89-92.
[6]HUNG WL,YANG MS,CHEN D H.Bootstrapping ap-proach to feature-weight selection in fuzzy C-means algo-rithms with an application in color i mage segmentation[J].Pattern Recognition Letters,2008,29(9):1317-1325.
[7]陈新泉.特征加权的模糊C聚类算法[J].计算机工程与设计,2007,28(22):5329-5333.
[8]裴继红,范九伦,谢维信.一种新的高效软聚类算法:截集模糊C-均值聚类算法[J].电子学报,1998,26(2):83-86.
[9]YANG Miin-shen,WU Kuo-lung.Alpha-cut i mplementedfuzzy clustering algorithms and switching regressions[J].IEEE Trans.on Systems,Man and Cybernetics,Part B,2008,38(3):588-603.
[10]LI Y H,DONG M,HUA J.Localized feature selectionfor clustering[J].Pattern Recognition Letters,2008,29(1):10-18.
快速全局C-均值聚类 篇5
模糊C-均值 (Fuzzy C-Means, FCM) 算法是目前众多的聚类算法中应用最广泛且较成功的[1,2], 1974 年由Dunn提出该算法[3]。该算法虽然具有收敛速度快、局部搜索能力强等优点, 但它对初始条件极为敏感。国内外很多相关研究人员对这个问题进行了深入的研究, 如文献[4]提出基于GA的聚类方法, 在一定程度上解决FCM的初值敏感性问题, 但是由于遗传算法本身的缺陷, 仍会出现未成熟收敛现象。
文献[5]利用免疫机制改进GA, 并将C-均值算法与免疫GA有机结合, 形成一种混合算法。文献[6]提出了基于PSO算法的改进模糊聚类算法 (PSFC) , 该算法是一种实用的、速度更快、效率更高的改进聚类算法。本文提出了基于改进量子粒子群优化算法的模糊C-均值聚类, 充分利用量子粒子群算法收敛速度快、局部搜索能力强的特点, 并对量子门更新策略进行了改进。
1 模糊C-均值聚类概述
将数据集X ={x1, x2, ..., xn}∈ Rm分为C类, X中任意样本xk对i类的隶属度为群n , 分类结果用一个模糊隶属度矩阵U ={uik}∈ Rm表示, 模糊C-均值聚类是通过最小化关于隶属度矩阵U和聚类中心V的目标函数Jm (U, V) 来实现的。
如何为分类找到一个标准是一个非常关键的问题, 目前使用较多对于数据集X的划分实际上就是求有约束条件函数W的最小值 (最小平方误差和) :
式中U与P分别为数据集X的划分矩阵与聚类中心矩阵。
得到如下公式:
其中dlk≠ 0, 1≤ l ≤ c。
uir=1, 且对k≠r, uik=0;, r, 有dir=0。
2 量子粒子群优化算法简介
1995 年美国研究人员J.Kennedy以及R.C.Eberhart受鸟群觅食行为的启发, 提出了粒子群优化算法 (Particle Swarm Optimization, PSO) [6]。粒子群优化算法自提出以来, 已经取得了巨大的成功。目前, 粒子群算法在如下领域得到了广泛的应用:故障诊断、模糊控制、生物医学、通信网络、分布式网络、电子与信息、组合优化、自动控制、规划设计、图像与视频、能源规划、神经网络、水文气象预测、机器人、军事安全、传感器网络、信号处理等。显然, 由于粒子群优化简单容易扩展, 能被不同的应用领域采用[7,8]。
2004 年J.Sun等人提出了量子粒子群 (Quantum-behaved Particle Swarm Optimization, QPSO) [7], 主要的改进是在标准的粒子群算法基础上引入量子行为, QPSO是以DELTA势阱为基础, 认为粒子具有量子的行为, 该算法的迭代公式如下[9,10,11,12]:
式中:m Best为平均最优位置;M为粒子的数目;D为粒子的维数;Pi (Pi1, Pi2, ..., Pid) 为第i个粒子的个体最优位置;Xi (Xi1, Xi2, ..., Xid) 为第i个粒子的位置;Pg为全局最优位置;u、R1d、R2d是介于 (0, 1) 之间的随机数, β 称为收缩扩张系数。
3 基于量子粒子群优化算法的模糊C-均值聚类算法
3.1 量子粒子编码
量子粒子群优化算法是采用量子染色体对问题进行描述的, 量子染色体具体形式描述如下:
式中: m表示量子比特的个数, j= 1, 2, ⋯, n。在这种编码方式中, 一条染色体能够同时表达多个态的叠加, 而传统的编码方式只能表示一个具体的状态, 所以QPSO比其他传统进化算法更容易保持种群的多样性。
QPSO中的每个微粒的位置代表一个聚类中心的集合Ui= (zi1, zi2, ⋯, zik) , 其中zik (1 k K) 为一个聚类中心, K为聚类数, 如果数据集有m个属性, 那么zik为m维。故粒子由zik顺序连接而成, 其长度为K × m。
3.2 量子门更新
量子门的构造是算法的关键所在。目前在QPSO中主要采用的是量子旋转门:
更新过程如下:
旋转量子门示意图如图1 所示。
一般方法是通过查询表得到角度的设置。为了防止算法陷入早熟收敛, 本文提出一种R&Nε门旋转策略。 R&Nε门由旋转门和Nε门构成。非门 (Not-gate) 是经典的量子门, 它的作用是交换量子比特位的参数。Nε门即是经改进的带概率 ε 的非门, 它的转换矩阵如下所示:
with probabilityε;
with probability1-ε;where0<ε≪1。
在R&Nε门的作用下, 量子比特Q-bit更新公式如下:
3.3 算法流程
改进QPSO算法流程如图2 所示。
4 实验结果与分析
实验以UCI中的3 个实际数据集作为聚类对象, 分别用PSO算法与FCM结合以及本文算法对数据对象进行聚类分析。各算法的聚类中心数为其类别数。评价指标如下:
式中: N表示总对象数; n表示错误分类的对象数。实验结果见表1。
对于UCI中的3 个实际数据集, 本文算法聚类指标E均比PSO-FCM要小, 聚类正确率尤其是对于Soybeansmall样本得到了较大的提高, 本文算法的代价函数最大值远小于PSO-FCM, 且平均值比PSO-FCM要小, 这充分体现了本文改进算法的全局寻优能力强于PSO-FCM。
5 结论
快速全局C-均值聚类 篇6
关键词：刀具磨损,振动信号,模糊C-均值聚类,贴近度
切削过程中刀具的磨损与机床加工精度、加工效率及加工成本有密切联系, 因此对于刀具磨损的预测已成为机床加工过程测试的主要内容之一。由于刀具磨损不同阶段的区别是模糊的, 较难准确辨认, 往往为了保证加工质量, 对刀具磨损的估计较为保守, 长此以往造成生产成本的增加, 本文针对刀具磨损预测中遇到的模糊性, 选择模糊C-均值聚类算法, 对振动信号特征值进行划分类别, 利用模糊C-均值聚类软划分的优势, 对刀具磨损各个阶段进行有效划分, 并且由于选取了不同工况下的多个特征值来表征刀具磨损状态, 避免了单一指标预测时发生的误判了漏判现象。
一、预测原理
由于刀具磨损过程的不同阶段之间没有明确分界点, 模糊C-均值聚类算法在处理模糊分类方面具有明显优越性, 能够保证划分的准确性, 故提出采用模糊C-均值聚类算法来划分刀具磨损状态模式, 样本采用了多个特征值。具体方法如下:一是通过实验, 利用时域分析方法选取振动信号的特征域;二是从特征域中求得多个特征值, 构成样本特征矩阵;三是利用模糊C-均值聚类方法进行划分工作, 然后由样本矩阵计算得到隶属度矩阵;四是计算聚类中心;五是利用欧几里得贴近度方法对待测特征值与样本聚类中心进行比较, 并由此确定刀具磨损状态。
二、算法
(一) 模糊C-均值聚类算法。
传统的聚类分析HCM严格地将每一个待辨识对象划分到某一类, 故此分类界限分明。而客观世界大量存在着的聚类问题界限并不分明, 它们存在中介类属与性态。由Zadeh提出的模糊集理论正为传统的硬划分的改进提供了方向, 在硬划分向软划分转变的进程中做出了努力。普遍的模糊聚类方法包括:传递闭包法、最大树法、模糊C均值法等, 模糊聚类算法较之传统的聚类法最大特点是采用值在0, 1间隶属度来描述每个给定数据点属于各个组的程度, 让我们切实看到了划分方法灵活性的一面。下面是模糊C-均值聚类算法原理:
模糊C-均值聚类算法旨在引入中心矢量的概念, 以样本去此矢量中心加权距离的平方和最小来确定这一概念。首先, 设有样本集为X={x1, x2, …, xn }, 每个样本为r维向量, 有xi={xi1, xi2, …, xir}·然后引入C个不同的“类”这个概念, 让每一个样本与各个C之间都产生映射关系, 最后用一个概念——隶属度 ( μij) 来描述映射的数值关系即, 第i个样本对第j个类的隶属度, 用以下约束条件来描述隶属度:
undefined
对目标函数则采用总体组内误差平方和, 其定义如下:
式中, U为原始隶属度矩阵;m∈ (1, +∞) 为权重指数V= (v1, v2, …, vn) T;dij为样本去中心矢量距离, 定义dij‖xj-vi‖, xj为第j个样本, vi为第i类聚类中心矢量, 定义为:
undefined
聚类分析的检验指标:
1. 划分系数undefined
2. 划分熵undefined
模糊C均值聚类算法的迭代流程如下:
步骤1. 求各个隶属度, 构成隶属度矩阵;
步骤 2. 用式5-5计算聚类中心;
步骤3. 用式5-4计算目标函数, 若小于确定的最小阈值时, 算法停止;
步骤4. 计算新的U矩阵, 返回步骤2。
(二) 模糊集合贴近度理论。
贴近度是指两个模糊集接近的程度, 在模糊数学中的地位非常重要, 模糊集合的分类结果直接取决于贴近度的计算方式, 贴近度通常包括:海明贴近度、测量贴近度、欧几里得贴近度以及格贴近度等, 其中以欧几里得贴近度的应用最为广泛, 定义如下:
若U={u1, u2, …, un}则
若U为实数域上的闭区间[a, b]时, 有
undefined
三、刀具破损预测的实现
本实验机床采用自行研制的微小铣床, 振动信号的获取采用压电式加速度传感器, 并通过铁磁材料吸附于工件之上, 切削时传感器获得振动信号, 经放大处理后传送到A/D转换器进行模数转换, 由计算机对数字信号进行采集与数据处理, 检测装置的示意图如图1所示。在本文的刀具磨损预测实验中将刀具的磨损状态分为:初期磨损阶段、正常磨损阶段和急剧磨损阶段三个状态模式。通过对固定的硬质合金刀具从启用到破损过程中, 检测其在不同转速下的全程磨损状态。值得注意的是, 通过获取不同条件下的特征值, 可以保证所设计的预测模型能够涵盖比较全面的状态模式, 确保了模糊模型的准确性。
(一) 选择特征域。
从刀具启用到破损过程中, 通过经验对比, 确定特征域的具体区域, 拾取了三段特征较明显的波形图如图5.1所示。初期磨损阶段波形图未见到明显冲击, 波形走势比较平稳;正常磨损阶段波形图出现较大波动和起伏, 波形走势不平缓;急剧磨损阶段波形图发生强烈振幅变化, 随着采样点的增加波动越来越明显。
Fig.1the schematic diagram of detection device急剧磨损阶段
(二) 特征值选择。
在时域中, 通过对20多种能够表征机械信号特征的参数进行求值, 观察其在各阶段模式下的变化趋势, 抽取能将各阶段清晰分类, 并且能够保证类间距离较大而类内距离较小的特征值, 作为三个模式的特征值。本文经过多次实验, 最终确定的特征值是:均值、方差、峭度。它们的表达式及其物理意义如下:
1. 均值。
在随机振动信号中, 均值被用来表征样本函数{Xt}在时域上的均值, 表达式如下:
undefined
2. 方差。
定义: 不含直流分量的均方值, 表达式为:undefined
3. 峭度。
峭度顾名思义为信号陡峭程度, 表示大幅值脉冲出现的概率 对于时域波形中所含冲击较多者, 峭度一般较大, 反之则小。
undefined
(三) 特征矩阵的形成。
理论上, 在模糊聚类算法过程中, 对数据进行预处理提出粗大值的前提下, 实现越高分类结果就需要越多的样本。本文一共提取了18组数据, 首先经过观察大致分为三个阶段提取数据:从初期磨损阶段的信号中选取部分信号作为前6个样本;从正常磨损阶段的信号中选取部分信号作为第7至第12个样本;从急剧磨损阶段的信号中选取部分信号作为后6个样本。特征矩阵如表1所示。
(四) 模糊C均值的聚类分析。
权重系数和分类数分别取作m=2、C=3, 通过模糊C均值聚类算法划分样本, 并评估其分类结果 。所求的隶属度矩阵如表2所示, 所求的聚类中心如表3所示。划分系数F= 0.87, 划分熵H=0.13, 说明达到了较好的分类效果 (分类效果随着样本的增加愈加精确, 而且F越是接近于1, H就越向0靠拢) 。分析隶属度矩阵, 对比之前凭经验对刀具磨损波形图的观察分化, 则可发现文中所用的模糊算法的聚类结果与实际是相符的。故证明了模糊C-均值的聚类算法在刀具模式辨别上的有效性。
实际工况不变的情况下, 本文在不同转速下分别从三个刀具状态模式的特征区域中提取4个点上的主轴振动信号, 求出对应特征值, 作为待测样本。
标准样本是以已经获得的三种磨损模式的聚类中心, 通过映射, 用欧几里得贴近度法计算得出待测样本与标准样本聚类中心贴近度, 从贴近度的比重可知待测样本属于哪一模式, 预测情况如表4所示。
四、预测结果验证
待测样本的磨损状态是已知的, 通过实验结果对比发现预测结果与实际情况相符, 从而验证了本文所提出的基于模糊C-均值聚类算法的刀具破损预测方法能够很好地完成刀具破损预测工作, 而且预测效果很明显, 可以推广使用。
五、结语
本章主要是针对微机床加工过程刀具磨损状态预测实验研究, 实验选择刀具振动信号为刀具磨损的表征信号, 通过经验对比确定特征域, 提取特征值后, 利用模糊C-均值的聚类算法对刀具磨损模式进行分类, 最后利用欧几里德几何贴近度法求出待预测样本与标准样本聚类中心的贴近度, 对待测样本进行分类, 预测结果表明分类结果与待测样本的实际磨损状态相符, 证明该方法在解决刀具磨损模式模糊分类问题上有一定的应用价值, 应当予以推广和进一步研究。
参考文献
[1].万军.系统辨识的刀具磨损特征量提取方法[J].清华大学学报, 1996, 8:13～17
[2].王海丽, 张广鹏, 翁德玮.刀具破损状态的特征提取及自动识别[J].制造技术与机床, 2001, 12:2～5
[3].高成秀.基于振动信号的数控铣床刀具破损诊断方法[J].兰州工业高等专科学院学报, 2004, 3:5～7
[4].章建, 王珉, 张幼桢.切削过程多参量监测策略研究[J].航空学报, 2003, 8:3～6
[5].M.P.Vogler, R.E.Devor, S.G.Kapoor.On the modeling and anslysis of machining performance in micro milling Journal of Manufacturing Science and Engineering.2004
[6].Chummun R, Kirubarajan T.Fast date association using multi-dimensional assignment with clustering.IEEE Trans on Aeros pace and Electronic System, 2001
[7].Pulford W G.Date fusion of multi radar system by usinggenetic algorithm[J].IEEE Trans on Aerospace and Elec tronic System.2002
[8].Wu Xiaohong, Zhou Jianjiang.Allied Fuzzy c Means Clustering Model.Transaction of Nanjing University of Aeronautics&Astronautics, 2006
[9].Boryczka U.Finding groups in date:Cluster analysiswith ants.Applied Soft Computing.2009
【快速全局C-均值聚类】相关文章：
一种基于层次聚类的快速楼层判别算法09-11
站位全局 提升素质04-22
全局工作会议制度04-26
把方向谋全局评论04-25
全局内部管理整改措施01-31
全局干部大会讲话稿04-10
全局干部进状态动员大会讲话04-21
责任意识+全局意识+奉献精神=能力05-06
论企业给排水工程的全局设计09-12