APP下载

模糊C均值聚类算法及应用

2014-11-14张洪艳

科技资讯 2014年5期

摘 要:在对模糊C均值聚类算法原理进行简要分析的基础上,进行了实验仿真。首先利用聚类树形图估计分类数,再利用模糊C均值聚类算法进行分类,结果表明算法具有较好的分类效果。

关键词:FCM 聚类树形图 隶属度

中图分类号:TP391.41 文献标识码:A 文章编号:1672-3791(2014)2(b)-0000-00

1 引言

聚类分析是一种多元统计分析方法,属于无监督模式识别方法,被广泛应用于模式识别、图像处理、数据分析等领域[1-3]。模糊聚类分析建立了样本对类别的不确定描述,更能客观地反应样本的实际情况,从而成为聚类分析的主要方法 [4-5]。

在模糊聚类算法中,模糊C均值聚类算法(Fuzzy C-means, 简称FCM)应用最为广泛。FCM是基于目标函数的模糊聚类算法中理论最完善、应用最广泛的一种算法。为了借助目标函数法求解聚类问题,类内平方误差和WGSS(Within-Groups Sum of Squared Error)成为聚类目标函数的普遍形式。随着模糊划分概念的提出,Dunn[6]首先将其推广到加权WGSS函数,后来由Bezdek[7]扩展到加权WGSS的无限族,形成了FCM聚类算法的通用聚类准则。

2 模糊C均值聚类算法原理

模糊C均值聚类算法原理[8]描述如下:

设样本空间为: ,数据矩阵为:

FCM思想即将n个样本划分为c类( ),记 为c个类的聚类中心,其中 。

令 为隶属度矩阵, 表示第k个样本 属于第i类的隶属度( ), 。定义目标函数: , 。

FCM的聚类准则即确定U、V,使 最小。

FCM一般步骤如下:

Step1:初始化,确定c、m、初始隶属度矩阵 及隶属度终止容限 和最大迭代次数;

Step2:利用下式计算第 步的聚类中心 :

Step3:修正隶属度矩阵 ,计算目标函数 :

其中: ;

Step4:判断是否满足终止条件,满足则退出程序;否则, ,转Step2。

3 实验仿真

为了验证算法的有效性,选取数据如表1所示。数据选自2013年《中国统计年鉴》[9]。

程序利用matlab软件编写,具体流程如下:

Step1:利用matlab内置函数dendrogram绘制聚类树形图,根据树形图大概确定分类数c;

Step2:初始化,m=3, =1e-6,随机化 ;

Step3:调用fcm函数。

树形图如图1所示:

由图1可知,大体上可以分为四类,所以c=4。调用fcm函数,结果如下:

第一类:北京、上海、广州;

第二类:石家庄、长春、哈尔滨、福州、济南、郑州、长沙、西安;

第三类:太原、呼和浩特、合肥、厦门、南昌、南宁、海口、贵阳、昆明、拉萨、兰州、西宁、银川、乌鲁木齐;

第四类:天津、沈阳、大连、南京、杭州、宁波、青岛、武汉、深圳、重庆、成都。

4 结论

由实验结果可知,FCM算法能较好地对数据样本进行分类,但由于算法本身对初始聚类中心、初始隶属度的依赖性较强,所以,要使其发挥更好地作用,则需要进一步对其进行改进。

参考文献

[1] E. Hartuv and R. Shamir, A clustering algorithm based on graph connectivity [J], Inf. Process. Lett., 76, 175 -181,2000.

[2] Laszlo M,Mukherjee S.A genetic algorithm using hyper-quadtrees for low-dimensional K-means clustering[J]. IEEE Trans. Pattern Analysis and Machine Intelligence . 28(4),533 – 543,2006.

[3] 肖宇.聚类分析及其在图像处理中的应用[D]. 北京交通大学,2012.

[4] J. Chiang and P. Hao, A new kernel-based fuzzy clustering approach: Support vector clustering with cell growing [J]. IEEE Trans. Fuzzy Syst, 2003,11(4),518-527.

[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概率与数理统计分析(第2版) [M], 机械工业出版社,2012.

[9] 中国统计年鉴,http://data.stats.gov.cn, 2013.

○1作者简介:张洪艳:女,讲师,硕士研究生。主要研究方向:机电一体化,检测技术与自动化装置,人工智能等。endprint

摘 要:在对模糊C均值聚类算法原理进行简要分析的基础上,进行了实验仿真。首先利用聚类树形图估计分类数,再利用模糊C均值聚类算法进行分类,结果表明算法具有较好的分类效果。

关键词:FCM 聚类树形图 隶属度

中图分类号:TP391.41 文献标识码:A 文章编号:1672-3791(2014)2(b)-0000-00

1 引言

聚类分析是一种多元统计分析方法,属于无监督模式识别方法,被广泛应用于模式识别、图像处理、数据分析等领域[1-3]。模糊聚类分析建立了样本对类别的不确定描述,更能客观地反应样本的实际情况,从而成为聚类分析的主要方法 [4-5]。

在模糊聚类算法中,模糊C均值聚类算法(Fuzzy C-means, 简称FCM)应用最为广泛。FCM是基于目标函数的模糊聚类算法中理论最完善、应用最广泛的一种算法。为了借助目标函数法求解聚类问题,类内平方误差和WGSS(Within-Groups Sum of Squared Error)成为聚类目标函数的普遍形式。随着模糊划分概念的提出,Dunn[6]首先将其推广到加权WGSS函数,后来由Bezdek[7]扩展到加权WGSS的无限族,形成了FCM聚类算法的通用聚类准则。

2 模糊C均值聚类算法原理

模糊C均值聚类算法原理[8]描述如下:

设样本空间为: ,数据矩阵为:

FCM思想即将n个样本划分为c类( ),记 为c个类的聚类中心,其中 。

令 为隶属度矩阵, 表示第k个样本 属于第i类的隶属度( ), 。定义目标函数: , 。

FCM的聚类准则即确定U、V,使 最小。

FCM一般步骤如下:

Step1:初始化,确定c、m、初始隶属度矩阵 及隶属度终止容限 和最大迭代次数;

Step2:利用下式计算第 步的聚类中心 :

Step3:修正隶属度矩阵 ,计算目标函数 :

其中: ;

Step4:判断是否满足终止条件,满足则退出程序;否则, ,转Step2。

3 实验仿真

为了验证算法的有效性,选取数据如表1所示。数据选自2013年《中国统计年鉴》[9]。

程序利用matlab软件编写,具体流程如下:

Step1:利用matlab内置函数dendrogram绘制聚类树形图,根据树形图大概确定分类数c;

Step2:初始化,m=3, =1e-6,随机化 ;

Step3:调用fcm函数。

树形图如图1所示:

由图1可知,大体上可以分为四类,所以c=4。调用fcm函数,结果如下:

第一类:北京、上海、广州;

第二类:石家庄、长春、哈尔滨、福州、济南、郑州、长沙、西安;

第三类:太原、呼和浩特、合肥、厦门、南昌、南宁、海口、贵阳、昆明、拉萨、兰州、西宁、银川、乌鲁木齐;

第四类:天津、沈阳、大连、南京、杭州、宁波、青岛、武汉、深圳、重庆、成都。

4 结论

由实验结果可知,FCM算法能较好地对数据样本进行分类,但由于算法本身对初始聚类中心、初始隶属度的依赖性较强,所以,要使其发挥更好地作用,则需要进一步对其进行改进。

参考文献

[1] E. Hartuv and R. Shamir, A clustering algorithm based on graph connectivity [J], Inf. Process. Lett., 76, 175 -181,2000.

[2] Laszlo M,Mukherjee S.A genetic algorithm using hyper-quadtrees for low-dimensional K-means clustering[J]. IEEE Trans. Pattern Analysis and Machine Intelligence . 28(4),533 – 543,2006.

[3] 肖宇.聚类分析及其在图像处理中的应用[D]. 北京交通大学,2012.

[4] J. Chiang and P. Hao, A new kernel-based fuzzy clustering approach: Support vector clustering with cell growing [J]. IEEE Trans. Fuzzy Syst, 2003,11(4),518-527.

[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概率与数理统计分析(第2版) [M], 机械工业出版社,2012.

[9] 中国统计年鉴,http://data.stats.gov.cn, 2013.

○1作者简介:张洪艳:女,讲师,硕士研究生。主要研究方向:机电一体化,检测技术与自动化装置,人工智能等。endprint

摘 要:在对模糊C均值聚类算法原理进行简要分析的基础上,进行了实验仿真。首先利用聚类树形图估计分类数,再利用模糊C均值聚类算法进行分类,结果表明算法具有较好的分类效果。

关键词:FCM 聚类树形图 隶属度

中图分类号:TP391.41 文献标识码:A 文章编号:1672-3791(2014)2(b)-0000-00

1 引言

聚类分析是一种多元统计分析方法,属于无监督模式识别方法,被广泛应用于模式识别、图像处理、数据分析等领域[1-3]。模糊聚类分析建立了样本对类别的不确定描述,更能客观地反应样本的实际情况,从而成为聚类分析的主要方法 [4-5]。

在模糊聚类算法中,模糊C均值聚类算法(Fuzzy C-means, 简称FCM)应用最为广泛。FCM是基于目标函数的模糊聚类算法中理论最完善、应用最广泛的一种算法。为了借助目标函数法求解聚类问题,类内平方误差和WGSS(Within-Groups Sum of Squared Error)成为聚类目标函数的普遍形式。随着模糊划分概念的提出,Dunn[6]首先将其推广到加权WGSS函数,后来由Bezdek[7]扩展到加权WGSS的无限族,形成了FCM聚类算法的通用聚类准则。

2 模糊C均值聚类算法原理

模糊C均值聚类算法原理[8]描述如下:

设样本空间为: ,数据矩阵为:

FCM思想即将n个样本划分为c类( ),记 为c个类的聚类中心,其中 。

令 为隶属度矩阵, 表示第k个样本 属于第i类的隶属度( ), 。定义目标函数: , 。

FCM的聚类准则即确定U、V,使 最小。

FCM一般步骤如下:

Step1:初始化,确定c、m、初始隶属度矩阵 及隶属度终止容限 和最大迭代次数;

Step2:利用下式计算第 步的聚类中心 :

Step3:修正隶属度矩阵 ,计算目标函数 :

其中: ;

Step4:判断是否满足终止条件,满足则退出程序;否则, ,转Step2。

3 实验仿真

为了验证算法的有效性,选取数据如表1所示。数据选自2013年《中国统计年鉴》[9]。

程序利用matlab软件编写,具体流程如下:

Step1:利用matlab内置函数dendrogram绘制聚类树形图,根据树形图大概确定分类数c;

Step2:初始化,m=3, =1e-6,随机化 ;

Step3:调用fcm函数。

树形图如图1所示:

由图1可知,大体上可以分为四类,所以c=4。调用fcm函数,结果如下:

第一类:北京、上海、广州;

第二类:石家庄、长春、哈尔滨、福州、济南、郑州、长沙、西安;

第三类:太原、呼和浩特、合肥、厦门、南昌、南宁、海口、贵阳、昆明、拉萨、兰州、西宁、银川、乌鲁木齐;

第四类:天津、沈阳、大连、南京、杭州、宁波、青岛、武汉、深圳、重庆、成都。

4 结论

由实验结果可知,FCM算法能较好地对数据样本进行分类,但由于算法本身对初始聚类中心、初始隶属度的依赖性较强,所以,要使其发挥更好地作用,则需要进一步对其进行改进。

参考文献

[1] E. Hartuv and R. Shamir, A clustering algorithm based on graph connectivity [J], Inf. Process. Lett., 76, 175 -181,2000.

[2] Laszlo M,Mukherjee S.A genetic algorithm using hyper-quadtrees for low-dimensional K-means clustering[J]. IEEE Trans. Pattern Analysis and Machine Intelligence . 28(4),533 – 543,2006.

[3] 肖宇.聚类分析及其在图像处理中的应用[D]. 北京交通大学,2012.

[4] J. Chiang and P. Hao, A new kernel-based fuzzy clustering approach: Support vector clustering with cell growing [J]. IEEE Trans. Fuzzy Syst, 2003,11(4),518-527.

[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概率与数理统计分析(第2版) [M], 机械工业出版社,2012.

[9] 中国统计年鉴,http://data.stats.gov.cn, 2013.

○1作者简介:张洪艳:女,讲师,硕士研究生。主要研究方向:机电一体化,检测技术与自动化装置,人工智能等。endprint