留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

基于双重迭代聚类的模糊投影寻踪聚类算法

廖力 周雪芹 李清清 陈璐 周建中

廖力, 周雪芹, 李清清, 陈璐, 周建中. 基于双重迭代聚类的模糊投影寻踪聚类算法[J]. 武汉大学学报 ● 信息科学版, 2016, 41(7): 932-938. doi: 10.13203/j.whugis20140152
引用本文: 廖力, 周雪芹, 李清清, 陈璐, 周建中. 基于双重迭代聚类的模糊投影寻踪聚类算法[J]. 武汉大学学报 ● 信息科学版, 2016, 41(7): 932-938. doi: 10.13203/j.whugis20140152
LIAO Li, ZHOU Xueqin, LI Qingqing, CHEN Lu, ZHOU Jianzhong. A Dual Iterative Clustering Based Fuzzy Projection Pursuit Clustering Algorithm[J]. Geomatics and Information Science of Wuhan University, 2016, 41(7): 932-938. doi: 10.13203/j.whugis20140152
Citation: LIAO Li, ZHOU Xueqin, LI Qingqing, CHEN Lu, ZHOU Jianzhong. A Dual Iterative Clustering Based Fuzzy Projection Pursuit Clustering Algorithm[J]. Geomatics and Information Science of Wuhan University, 2016, 41(7): 932-938. doi: 10.13203/j.whugis20140152

基于双重迭代聚类的模糊投影寻踪聚类算法

doi: 10.13203/j.whugis20140152
基金项目: 

长江科学院开放研究基金 Nos. CKWV2014219/KY

长江科学院开放研究基金 Nos. CKWV2014213/KY

国家自然科学基金 Nos. 51239004

国家自然科学基金 Nos. 51309104

湖北省教育厅科学研究计划 No. Q20151407

湖北循环经济发展研究中心开放研究基金 No.HXFKY1502

详细信息
    作者简介:

    廖力,博士,副教授,主要从事模糊综合评价、智能优化算法的理论与方法研究. E-mail:amazon2008@163.com

  • 中图分类号: TP18;P208

A Dual Iterative Clustering Based Fuzzy Projection Pursuit Clustering Algorithm

Funds: 

The Open Research Program of Changjiang River Scientific Research Institute Nos. CKWV2014219/KY

The Open Research Program of Changjiang River Scientific Research Institute Nos. CKWV2014213/KY

the National Natural Science Foundation of China Nos. 51239004

the National Natural Science Foundation of China Nos. 51309104

the Scientific Research Program of Hubei Provincial Departament of Education No. Q20151407

the Open Research Program of Hubei Province Cyclic Economy Research Center No.HXFKY1502

  • 摘要: 建立了一种新的聚类算法——模糊投影寻踪聚类(fuzzy projection pursuit cluster, FPPC)算法,实现了投影寻踪聚类(projection pursuit clustering,PPC)算法与模糊聚类迭代(fuzzy clustering iterative,FCI)算法的良好融合。FPPC算法首先建立了一种新的投影指标函数,该函数由投影值标准差和投影点广义欧氏权距离平方和构成,能避免传统PPC中选取惟一参数密度窗宽时完全依赖经验来决定的问题;然后采用投影技术对高维数据进行降维处理,执行FCI步骤来对低维样本集进行初次聚类运算;接着通过寻找最优投影方向的过程,对样本集进行PPC的二重聚类。在FPPC求解过程中,运用了由混沌理论、文化算法与差分进化算法融合而成的混沌文化差分进化算法进行优化处理。实验仿真表明,FCI与PPC双重迭代聚类的FPPC算法拥有更优的聚类精度及有效性。
  • 图  1  CCDE算法基本框架

    Figure  1.  Framework of CCDE Algorithm

    图  2  FPPC详细流程

    Figure  2.  Detailed Process of FPPC

    图  3  3种方法各等级聚类效果比较

    Figure  3.  Clustering Effect Comparison of Three Methods

    表  1  测试函数运行结果

    Table  1.   Test Function Running Results

    测试函数优化算法最小值最大值平均值标准差
    PSO7.101 9×10-82.137 1×10-53.640 2×10-64.781 0×10-6
    Sphere函数DE6.123 1×10-134.468 0×10-121.945 9×10-129.513 6×10-13
    CCDE2.839 1×10-2243.403 4×10-2083.420 1×10-2090
    PSO5.593 2×10-51.970 9×10-36.696 5×10-45.007 1×10-4
    Ackley函数DE2.404 8×10-75.466 4×10-73.781 1×10-77.237 2×10-8
    CCDE3.996 8×10-153.996 8×10-153.996 8×10-150
    PSO1.879 4×10-65.895 1×10-21.146 5×10-21.288 4×10-2
    Griewangk函数DE1.424 0×10-127.778 2×10-119.585 5×10-121.145 5×10-11
    CCDE0000
    PSO11.29355.84630.3517.116 2
    Rastrigin函数DE48.704 680.208 365.062 17.393 0
    CCDE0000
    PSO0000
    Schaffer函数DE00.009 70.002 00.003 9
    CCDE0000
    下载: 导出CSV

    表  2  新疆1996年7月洪水灾害损失统计表

    Table  2.   Flood Disaster Loss in July 1996 in Xinjiang

    地区编号受灾面积/104ha受灾人口/104破坏房屋/104m2直接经济损失/107
    10.154 36.000 020.690 03.480 0
    21.374 05.970 06.235 01.608 0
    30.260 14.350 02.843 00.177 0
    42.352 09.400 054.50 007.910 0
    51.667 32.960 058.728 04.946 0
    60.545 82.620 05.105 01. 826 0
    71.079 24.540 021.713 07.880 0
    80.341 05 600 01.556 00.395 0
    90.214 020.000 01.890 01.430 0
    104.602 624.727 013.592 06.327 0
    下载: 导出CSV

    表  3  洪水聚类结果比较

    Table  3.   Comparison of Flood Clustering Results

    地区FCI类别特征连续值FCI类别特征离散值FCI聚类误差CDEFC I类别特征连续值CDEFCI类别特征离散值CDEFCI聚类误差FPPC类别特征连续值FPPC类别特征离散值FPPC聚类误差
    11.996 520.003 52.016 820.016 81.005 310.005 3
    21.287 110.287 11.384 010.384 01.998 720.001 3
    31.103 210.103 21.010 110.010 11.022 510.022 5
    42.962 130.037 92.994 930.005 12.999 930.000 1
    52.463 220.463 22.995 730.004 32.001 020.001 0
    61.333 610.333 61.104 810.104 81.003 410.003 4
    72.900 230.099 82.016 620.016 61.994 920.005 1
    81.052 910.052 91.067 310.067 31.001 410.001 4
    91.892 020.108 01.054 410.054 41.999 820.000 2
    103.997 440.002 63.999 340.000 73.999 940.000 1
    下载: 导出CSV

    表  4  各模糊聚类方法误差分析及聚类有效性指标值比较

    Table  4.   Error Analysis and Clustering Validity Comparison of Different Fuzzy Clustering Methods

    评估方法聚类误差绝对值落在下列区间的样本个数聚类绝对误差均值聚类相对误差均值/%XBPEPC最小广义欧氏权距离平方和
    [0,0.1][0,0.2][0,0.3][0,0.4][0,0.5]
    FCI5789100.149 111.110.770 60.805 00.710 81.078 7
    CDEFCI89910100.066 46.410.015 10.188 30.945 86.625 1×10-3
    FPPC10101010100.004 00.360.005 20.062 30.985 81.859 8×10-3
    下载: 导出CSV
  • [1] 孙吉贵, 刘杰, 赵连宇. 聚类算法研究[J]. 软件学报, 2008, 19(1): 48-61

    Sun Jigui, Liu Jie, Zhao Lianyu. Clustering Algorithms Research[J]. Journal of Software, 2008,19(1):48-61
    [2] 钟业勋, 胡宝清, 乔俊军. 多因素评价体系的模糊聚类分析[J]. 武汉大学学报·信息科学版, 2010, 35(6): 752-755

    Zhong Yexun, Hu Baoqing, Qiao Junjun. Fuzzy Clustering of Multi-factors Evaluated System[J]. Geomatics and Information Science of Wuhan University, 2010, 35(6): 752-755
    [3] 田晶, 何青松, 颜芬. 道路网Stroke生成问题的形式化表达与新算法[J]. 武汉大学学报·信息科学版, 2014, 39(5): 556-560

    Tian Jing, He Qingsong, Yan Fen. Formalization and New Algorithm of Stroke Generation in Road Networks[J]. Geomatics and Information Science of Wuhan University, 2014, 39(5): 556-560
    [4] 陈佳, 胡波, 左小清, 等. 利用手机定位数据的用户特征挖掘[J]. 武汉大学学报·信息科学版, 2014, 39(6): 734-738

    Chen Jia, Hu Bo, Zuo Xiaoqing, et al. Personal Profile Mining Based on Mobile Phone Location Data[J]. Geomatics and Information Science of Wuhan University, 2014, 39(6): 734-738
    [5] Friedman J H, Tukey J W. A Projection Pursuit Algorithm for Exploratory Data Analysis[J]. IEEE Trans on Computer, 1974, 23(9):881-890
    [6] Bezdek J. C. Pattern Recognition with Fuzzy Objective Function Algorithms[M]. New York: Plenum, 1981
    [7] 陈守煜. 工程模糊集理论与应用[M]. 北京: 国防工业出版社, 1998

    Chen Shouyu. Engineering Fuzzy Set Theory and Application[M]. Beijing: National Defence Industry Press, 1998
    [8] 付强, 赵小勇. 投影寻踪模型原理及其应用[M]. 北京: 科学出版社, 2006

    Fu Qiang, Zhao Xiaoyong. Principle and Application of Projection Pursuit Model [M]. Beijing: Science Press, 2006
    [9] 张鹏林, 黄丽, 吕志勇, 等. 一种改进的空间加权模糊C均值算法在遥感影像分割中的应用[J]. 武汉大学学报·信息科学版, 2013, 38(7): 774-777

    Zhang Penglin, Huang Li, Lv Zhiyong, et al. An Improved Weighted Fuzzy C-Means Algorithm with Spatial Information for Remote Sensing Image Segmentation[J]. Geomatics and Information Science of Wuhan University, 2013, 38(7): 774-777
    [10] 孔令桥, 秦昆, 龙腾飞. 利用二型模糊聚类进行全球海表温度数据挖掘[J]. 武汉大学学报·信息科学版, 2012, 37(2): 215-219

    Kong Lingqiao, Qin Kun, Long Tengfei. Global SST Data Mining Based on Fuzzy Clustering[J]. Geomatics and Information Science of Wuhan University, 2012, 37(2): 215-219
    [11] 廖力, 李蕊, 邹强, 等. 基于模糊聚类迭代模型的洪灾智能评估方法[J]. 人民长江, 2014, 45(4): 1-4

    Liao Li, Li Rui, Zou Qiang, et al. Intelligent Assessment of Flood Disaster Based on Fuzzy Clustering Iterative Model[J]. Yangtze River, 2014, 45(4): 1-4
    [12] 于雪峰, 陈守煜. 模糊聚类迭代模型在洪水灾害度划分中应用[J]. 大连理工大学学报, 2005,45(1):128-131

    Yu Xuefeng, Chen Shouyu. Application of Fuzzy Clustering Iterative Model to Classification of Flood Disaster Grade[J]. Journal of Dalian University of Technology, 2005,45(1):128-131
    [13] Liao Li, Zhou Jianzhong, Zou Qiang. Weighted Fuzzy Kernel-Clustering Algorithm with Adaptive Differential Evolution and Its Application on Flood Classification[J]. Natural Hazards, 2013, 69(1): 279-293
    [14] He Yaoyao, Zhou Jianzhong, Kou Pangao, et al. A Fuzzy Clustering Iterative Model Using Chaotic Differential Evolution Algorithm for Evaluating Flood Disaster[J]. Expert Systems with Applications, 2011, 38(8): 10 060-10 065
    [15] 卢有麟, 周建中, 宋利祥, 等. 基于 CCPSO 及 PP 模型的洪灾评估方法及其仿真应用[J]. 系统仿真学报, 2010, 22(2): 383-387

    Lu Youning, Zhou Jianzhong, Song Lixiang, et al. Flood Disaster Evaluating Method Based on CCPSO along with Projection Pursuit Model and Its Application[J]. Journal of System Simulation, 2010, 22(2): 383-387
    [16] Storn R, Price K. Differential Evolution—A Simple and Efficient Adaptive Scheme for Global Optimization over Continuous Spaces[J]. International Computer Science Institute, 1995, (8): 22-25
    [17] Storn R, Price K. Differential Evolution—A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces[J].Journal of Global Optimization, 1997, 11: 341-359
    [18] He Yaoyao, Zhou Jianzhong, Lu Ning, et al. Differential Evolution Algorithm Combined with Chaotic Pattern Search[J]. Kybernetika, 2010, 46(4): 684-696
    [19] 李超顺, 周建中, 方仍存, 等. 基于混沌优化的模糊聚类分析方法[J], 系统仿真学报, 2009, 21(10): 2 977-2 980

    Li Chaoshun, Zhou Jianzhong, Fang Rengcun, et al. Fuzzy Clustering Analytic Method Based on Chaos Optimization[J]. Journal of System Simulation, 2009, 21(10): 2 977-2 980
  • [1] 王昶, 张永生, 王旭.  基于变分法与Markov随机场模糊局部信息聚类法的SAR影像变化检测 . 武汉大学学报 ● 信息科学版, 2021, 46(6): 844-851. doi: 10.13203/j.whugis20190167
    [2] 崔晓杰, 王家耀, 巩现勇, 赵耀.  利用模糊密度聚类和双向缓冲区自动识别热点区 . 武汉大学学报 ● 信息科学版, 2019, 44(1): 84-91. doi: 10.13203/j.whugis20180358
    [3] 李延, 王大魁, 耿晶, 王树良.  数据质量聚类算法 . 武汉大学学报 ● 信息科学版, 2019, 44(1): 153-158. doi: 10.13203/j.whugis20150760
    [4] 职露, 余旭初, 李光强.  滚圆法用于空间点聚类的研究 . 武汉大学学报 ● 信息科学版, 2018, 43(8): 1193-1198. doi: 10.13203/j.whugis20160287
    [5] 林恒, 龚威, 史硕.  利用等边长正交格网进行层次聚合聚类 . 武汉大学学报 ● 信息科学版, 2018, 43(5): 786-791. doi: 10.13203/j.whugis20150668
    [6] 李玉, 胡海峰, 赵雪梅, 赵泉华.  基于可变形状参数Gamma分布的模糊聚类多视SAR图像分割 . 武汉大学学报 ● 信息科学版, 2018, 43(7): 984-992. doi: 10.13203/j.whugis20160149
    [7] 袁汉宁, 周彤, 韩言妮, 陈媛媛.  基于MI聚类的协同推荐算法 . 武汉大学学报 ● 信息科学版, 2015, 40(2): 253-257.
    [8] 黄少滨, 杨欣欣.  基于最小平方和残差的高阶模糊联合聚类算法 . 武汉大学学报 ● 信息科学版, 2015, 40(2): 238-242.
    [9] 陈西江, 花向红, 杨荣华, 张青华.  分带K-均值聚类的平面标靶定位 . 武汉大学学报 ● 信息科学版, 2013, 38(2): 167-170.
    [10] 孔令桥, 秦昆, 龙腾飞.  利用二型模糊聚类进行全球海表温度数据挖掘 . 武汉大学学报 ● 信息科学版, 2012, 37(2): 215-219.
    [11] 赵凤, 刘汉强, 范九伦, 潘晓英.  应用于遥感图像分割的原型提取谱聚类集成算法 . 武汉大学学报 ● 信息科学版, 2012, 37(12): 1472-1476.
    [12] 王海军, 邓羽, 王丽, 关兴良.  基于数据场的C均值聚类方法研究 . 武汉大学学报 ● 信息科学版, 2009, 34(5): 626-629.
    [13] 刘小利, 朱国宾, 李清泉, 贾治革.  基于并行Tabu搜索和空间信息约束的遥感影像模糊聚类 . 武汉大学学报 ● 信息科学版, 2009, 34(5): 527-530.
    [14] 钟燕飞, 张良培, 李平湘.  遥感影像分类中的模糊聚类有效性研究 . 武汉大学学报 ● 信息科学版, 2009, 34(4): 391-394.
    [15] 胡春春, 孟令奎, 谢文君, 周新忠.  空间数据模糊聚类的有效性评价 . 武汉大学学报 ● 信息科学版, 2007, 32(8): 740-743.
    [16] 闫利, 张毅.  基于法向量模糊聚类的道路面点云数据滤波 . 武汉大学学报 ● 信息科学版, 2007, 32(12): 1119-1122.
    [17] 王海军, 张德礼.  基于空间聚类的城镇土地定级方法研究 . 武汉大学学报 ● 信息科学版, 2006, 31(7): 628-631.
    [18] 邢喆, 王泽民, 伍岳.  利用模糊聚类方法筛选GPS载波相位组合观测值 . 武汉大学学报 ● 信息科学版, 2006, 31(1): 23-26.
    [19] 潘励, 郑宏, 张祖勋, 张剑清.  集成高度和彩色纹理特征的影像目标模糊聚类识别方法 . 武汉大学学报 ● 信息科学版, 2004, 29(4): 311-314.
    [20] 唐亮, 黄培之, 谢维信.  顾及数据空间分布特性的模糊C-均值聚类算法研究 . 武汉大学学报 ● 信息科学版, 2003, 28(4): 476-479.
  • 加载中
图(3) / 表(4)
计量
  • 文章访问数:  1380
  • HTML全文浏览量:  44
  • PDF下载量:  233
  • 被引次数: 0
出版历程
  • 收稿日期:  2014-11-27
  • 刊出日期:  2016-07-05

基于双重迭代聚类的模糊投影寻踪聚类算法

doi: 10.13203/j.whugis20140152
    基金项目:

    长江科学院开放研究基金 Nos. CKWV2014219/KY

    长江科学院开放研究基金 Nos. CKWV2014213/KY

    国家自然科学基金 Nos. 51239004

    国家自然科学基金 Nos. 51309104

    湖北省教育厅科学研究计划 No. Q20151407

    湖北循环经济发展研究中心开放研究基金 No.HXFKY1502

    作者简介:

    廖力,博士,副教授,主要从事模糊综合评价、智能优化算法的理论与方法研究. E-mail:amazon2008@163.com

  • 中图分类号: TP18;P208

摘要: 建立了一种新的聚类算法——模糊投影寻踪聚类(fuzzy projection pursuit cluster, FPPC)算法,实现了投影寻踪聚类(projection pursuit clustering,PPC)算法与模糊聚类迭代(fuzzy clustering iterative,FCI)算法的良好融合。FPPC算法首先建立了一种新的投影指标函数,该函数由投影值标准差和投影点广义欧氏权距离平方和构成,能避免传统PPC中选取惟一参数密度窗宽时完全依赖经验来决定的问题;然后采用投影技术对高维数据进行降维处理,执行FCI步骤来对低维样本集进行初次聚类运算;接着通过寻找最优投影方向的过程,对样本集进行PPC的二重聚类。在FPPC求解过程中,运用了由混沌理论、文化算法与差分进化算法融合而成的混沌文化差分进化算法进行优化处理。实验仿真表明,FCI与PPC双重迭代聚类的FPPC算法拥有更优的聚类精度及有效性。

English Abstract

廖力, 周雪芹, 李清清, 陈璐, 周建中. 基于双重迭代聚类的模糊投影寻踪聚类算法[J]. 武汉大学学报 ● 信息科学版, 2016, 41(7): 932-938. doi: 10.13203/j.whugis20140152
引用本文: 廖力, 周雪芹, 李清清, 陈璐, 周建中. 基于双重迭代聚类的模糊投影寻踪聚类算法[J]. 武汉大学学报 ● 信息科学版, 2016, 41(7): 932-938. doi: 10.13203/j.whugis20140152
LIAO Li, ZHOU Xueqin, LI Qingqing, CHEN Lu, ZHOU Jianzhong. A Dual Iterative Clustering Based Fuzzy Projection Pursuit Clustering Algorithm[J]. Geomatics and Information Science of Wuhan University, 2016, 41(7): 932-938. doi: 10.13203/j.whugis20140152
Citation: LIAO Li, ZHOU Xueqin, LI Qingqing, CHEN Lu, ZHOU Jianzhong. A Dual Iterative Clustering Based Fuzzy Projection Pursuit Clustering Algorithm[J]. Geomatics and Information Science of Wuhan University, 2016, 41(7): 932-938. doi: 10.13203/j.whugis20140152
  • 聚类是数据挖掘中一个必不可少的子领域。聚类算法的目的是将一个样本集中的每一类相似样本分别汇聚为各个类簇,类簇可以描述为一个包含密度相对较高的点集的多维空间中的联通区域,他们借助包含密度相对较低的点集的区域与其他区域(类簇)相分离[1]。对于聚类算法来说,要求相同类内样本相似性尽可能大,不同类别间相似性尽可能小,一般也采用根据样本间距离来描述的类内密度和类间距离两个参数对聚类效果进行评判,即类别内样本密度越大越好,而类别间隔越远越好。目前聚类算法已广泛应用于图像分割、数据挖掘及统计科学中[2-4]。投影寻踪聚类算法[5](projection pursuit clustering,PPC)和模糊聚类迭代算法[6-7](fuzzy clustering iterative,FCI)是目前应用广泛的两种聚类算法,其策略均为挖掘样本集内在分布规律,从而对关键向量进行优化,使得聚类评价结果满足目标函数最优化的要求,聚类效果良好。但两种方法建模时也有一些问题进行改进。

    传统PPC算法[8-9]用投影值标准差来表征类间密度,投影点在每一个“窗”中的分布情况来表征类内密度,密度窗宽为唯一需预设定的参数,并且其取值是否合理直接关系到聚类结果的有效性。而当前用于确定密度窗宽的计算方法均缺乏理论证明,不能验证聚类结果的科学性。除此之外,PPC往往需要根据投影点位置来主观判断聚类情况。

    FCI算法[10-14]利用隶属度矩阵、聚类中心矩阵、指标权重向量三者间的迭代运算,使得目标函数值不断优化,最终获得最优的隶属度矩阵及聚类中心矩阵,具有良好的聚类效果,受到学者们广泛关注。但是,当待评价样本数量大、指标维数高时,FCI计算复杂度较高;且FCI对样本分散情况依赖性很高,受预设聚类中心影响很大,易陷入局部收敛。

    针对上述问题,本文建立了全新的投影指标函数,将PPC技术与FCI方法相结合,提出了模糊投影寻踪聚类(fuzzy projection pursuit cluster,FPPC)算法,避开密度窗宽参数的选择问题,所有参数在运算过程中智能率定,且FCI和PPC的双重迭代聚类运算保证了该算法的聚类效果。为了克服对预设聚类中心和投影方向的依赖性,计算过程中采用了由混沌理论[14]、文化算法[15]与差分进化算法[16-18]融合而成的混沌文化差分进化算法(chaotic culture deferantial evolution,CCDE)对聚类中心及投影方向进行了寻优。

    • CCDE算法基本框架如图 1所示,可简单描述为:首先对每个个体进行适应度评判,寻找最优对象;然后两个空间平行进化,其中主群体空间进化规则为混沌差分进化算法,而信念空间采用基于分段线性混沌映射的混沌搜索进行进化;若进化代数达到指定值(本章取10)的整数倍时,则进行接受操作和影响操作。当运算终止条件达到时,停止运算,否则迭代次数加1,继续运算。

      图  1  CCDE算法基本框架

      Figure 1.  Framework of CCDE Algorithm

      接受操作和影响操作的具体流程设计如下:

      (1) 接受操作:假设信念空间的大小为M,当进行接受操作时,主群体空间将当前适应度值最高的M个解提供给信念空间,信念空间通过对比适应度值高低,取最优的M个个体替换原空间中适应度值较小个体。

      (2) 影响

      操作:当进行影响操作时,信念空间选择适应度值最高的0.5M个个体来取代主群体空间中适应度值较低个体。

      分段线性混沌映射的分布函数是均匀分布的,比传统的分布函数两端高、中间低的Logistic映射的优化性能更好。分段线性混沌映射表达式如下:

      (1)

      式中,r为控制参数。

      为评估CCDE算法的有效性,本文采用5项典型测试函数[18]进行验算。测试函数分别使用PSO、DE、CCDE三种算法各运行30次,取目标函数的最大、最小、平均及标准差值进行比较。测试结果显示CCDE优化效果最好,如表 1

      表 1  测试函数运行结果

      Table 1.  Test Function Running Results

      测试函数优化算法最小值最大值平均值标准差
      PSO7.101 9×10-82.137 1×10-53.640 2×10-64.781 0×10-6
      Sphere函数DE6.123 1×10-134.468 0×10-121.945 9×10-129.513 6×10-13
      CCDE2.839 1×10-2243.403 4×10-2083.420 1×10-2090
      PSO5.593 2×10-51.970 9×10-36.696 5×10-45.007 1×10-4
      Ackley函数DE2.404 8×10-75.466 4×10-73.781 1×10-77.237 2×10-8
      CCDE3.996 8×10-153.996 8×10-153.996 8×10-150
      PSO1.879 4×10-65.895 1×10-21.146 5×10-21.288 4×10-2
      Griewangk函数DE1.424 0×10-127.778 2×10-119.585 5×10-121.145 5×10-11
      CCDE0000
      PSO11.29355.84630.3517.116 2
      Rastrigin函数DE48.704 680.208 365.062 17.393 0
      CCDE0000
      PSO0000
      Schaffer函数DE00.009 70.002 00.003 9
      CCDE0000
    • 假设有样本集X={X1,X2,…,XN}T,每个XjM维指标,令为Xj=x1j,x2j,…,xMj;由模糊优化理论,矩阵X应按照式(2)转化成标准化指标矩阵R

      (2)

      式中,ximax、ximin分别是指标i的最大、最小值。

      为了得到最优隶属度矩阵U和最优聚类中心矩阵S,设FCI的聚类目标为使样本空间的加权广义欧氏距离平方和最小。目标函数定义为:

      (3)

      式中,uhj表示xj对第h类中的隶属度,wi是指标i的权重,rij是标准化后的样本ji项指标的特征值,sih是指标i在类别h中的聚类中心。

      根据拉格朗日函数方法,聚类中心矩阵S和隶属度矩阵U可以表示如下:

      (4)
      (5)

      FCI方法根据样本集内在特性来进行分类,能得到良好且全面客观的聚类效果。但是,当样本集维数较高并且样本数较多时,计算量很大,并且对初始聚类中心十分敏感,易陷入局部收敛。

    • 投影寻踪技术的核心思路为将样本集由高维空间投影至低维空间,再根据投影指标函数来找出原始高维空间的结构或者特性,从而进行有效处理。传统投影指标函数为:

      (6)

      其中,式中,y(i)是第i个样本的投影值;a(j)是在指标j上的投影方向;xij是样本i在指标j上的特征值;R是密度窗宽;u()是单位阶跃函数;S(y)是样本投影值标准差,用来表示整体投影点的分散程度;dij是样本i投影点到样本j投影点间的距离;D(y)是每扇“窗”内的样本点间的距离之和,用来表示类内密集程度。S(y)越大,D(y)越小,PPC的聚类效果越好。因此,目标函数为max{QF(a)}=S(y)D(y)。

      在PPC聚类算法中,密度窗宽R是唯一需要事先被确定的参数,该参数决定了最终聚类效果的好坏。然而,可靠的R的选取方法仍不存在,目前一般依靠经验确定,这也导致了PPC的最终聚类效果无法得到保证。

    • 考虑到现有FCI算法和PPC算法的不足,笔者对两者进行了研究,发现可以互相取长补短,互补融合后能大大提高聚类算法的准确性及效果。

    • 为了使FCI和PPC互补融合,本文采用投影值标准差作为S(y)表征类间距离,采用样本与聚类中心间的加权广义欧氏距离平方和作为D(y)来表征类内样本密度。该投影指标函数无须选取密度窗宽参数,并且因为欧氏距离用来描述样本间的距离更为准确,更好地满足了聚类算法对于S(y)D(y)的需求。我们可以通过求解最小化投影指标函数值即min{QF(a)}来得到最优投影方向向量。

      新的投影指标函数按照式(7)构建:

      (7)
    • 图 2所示,本文按照如下流程对PPC和FCI进行互补融合:

      图  2  FPPC详细流程

      Figure 2.  Detailed Process of FPPC

      1) 样本集标准化以及FPPC初始化。

      首先按照式(2)来标准化样本集,然后用随机函数对投影方向向量进行初始化处理,预设CCDE参量。

      2) 投影值计算

      用式(7)计算样本投影值,然后随机生成投影值聚类中心矩阵。按式(8)将投影值标准化:

      (8)

      式中,ymax、ymin分别是样本投影值的最大和最小值。

      3) FCI聚类过程

      由于高维样本集已被投影为一维投影值,M变为常量1,权重向量也降至一维,因此,w等于1,sih变为sh。隶属度矩阵和聚类中心矩阵转化为:

      (9)
      (10)

      根据式(9)、式(10)进行模糊聚类迭代运算。

      4) FCI适应度计算及比较

      由式(11)计算FCI适应度,若满足FCI终止条件,转步骤5),否则用CCDE搜索最优聚类中心矩阵,返回步骤3)。

      (11)

      5) 投影方向优化

      根据式(7)计算并比较FPPC的适应度,若达到终止条件,则转步骤6);否则采用CCDE对投影方向寻优后,转步骤2)继续运算。

      6) 计算类别特征值

      将最优隶属度代入式(12)来计算聚类类别特征值,样本的连续性类别特征值为:

      (12)

      由类别特征值可以四舍五入得到样本所属类别离散值,从而直观得到聚类结果,同时可以根据类别特征值的大小对样本进行排序。

    • FPPC通过投影降维技术降低了需进行聚类迭代运算的样本维数,从而大大降低了运算复杂度。首先将FPPC的聚类中心计算式(11)与FCI的式(4)相比较,由于降至一维,无权重影响,且聚类中心个数为FCI的1/m(m为维数),FPPC计算聚类中心需要的乘法和平方运算次数为FCI的1/(2 nm)(n为样本数);其次将FPPC隶属度计算式(9)与FCI的式(5)相比较,要的减法、乘法和平方运算次数为FCI的1/(2 m)。综上所述,鉴于通常需要进行数百次的迭代运算,FPPC的计算复杂度得到了有效降低,并且样本维数越高,效果越显著。

    • 聚类有效性指标[19]用来评判模糊聚类算法结果。本文采用了下列指标:

      (13)

      式中,PC越大且越接近于1时聚类效果越好;PEXB越小越接近0时聚类效果越好。

    • 表 2为新疆1996年7月洪水灾害样本集,本文采用FPPC将其分为特大洪灾、大洪灾、一般洪灾和小型洪灾4类来验证算法的聚类有效性。

      表 2  新疆1996年7月洪水灾害损失统计表

      Table 2.  Flood Disaster Loss in July 1996 in Xinjiang

      地区编号受灾面积/104ha受灾人口/104破坏房屋/104m2直接经济损失/107
      10.154 36.000 020.690 03.480 0
      21.374 05.970 06.235 01.608 0
      30.260 14.350 02.843 00.177 0
      42.352 09.400 054.50 007.910 0
      51.667 32.960 058.728 04.946 0
      60.545 82.620 05.105 01. 826 0
      71.079 24.540 021.713 07.880 0
      80.341 05 600 01.556 00.395 0
      90.214 020.000 01.890 01.430 0
      104.602 624.727 013.592 06.327 0

      FPPC参数设定如下:样本数量为10,指标维数为4,类别数4,适应度精度设为10-4。CCDE参数设定如下:种群规模为50,最大进化代数为500,交叉因子初值为0.9,变异因子初值为0.4,分段线性混沌映射参数r=0.8。

      经FPPC聚类,投影指标函数最小值为0.000 47,样本投影值为{1.353 0,1.214 7,1.383 3,1.006 0,1.187 2,1.354 8,1.220 9,1.357 3,1.201 8,0.561 9},最优投影值聚类中心为{1.362 0,1.206 2,1.006 1,0.561 9},最优隶属度矩阵如式(14)所示:

      (14)

      将隶属度矩阵代入式(12)可计算出各样本连续性等级特征值。评估结果与其他方法比较见表 3

      表 3  洪水聚类结果比较

      Table 3.  Comparison of Flood Clustering Results

      地区FCI类别特征连续值FCI类别特征离散值FCI聚类误差CDEFC I类别特征连续值CDEFCI类别特征离散值CDEFCI聚类误差FPPC类别特征连续值FPPC类别特征离散值FPPC聚类误差
      11.996 520.003 52.016 820.016 81.005 310.005 3
      21.287 110.287 11.384 010.384 01.998 720.001 3
      31.103 210.103 21.010 110.010 11.022 510.022 5
      42.962 130.037 92.994 930.005 12.999 930.000 1
      52.463 220.463 22.995 730.004 32.001 020.001 0
      61.333 610.333 61.104 810.104 81.003 410.003 4
      72.900 230.099 82.016 620.016 61.994 920.005 1
      81.052 910.052 91.067 310.067 31.001 410.001 4
      91.892 020.108 01.054 410.054 41.999 820.000 2
      103.997 440.002 63.999 340.000 73.999 940.000 1

      分析表 3结果可知,FPPC模型计算出的聚类结果与文献[12] 中FCI方法和文献[14] 中基于混沌差分进化算法的模糊聚类迭代方法(chaotic differential evolution fuzzy clustering iterative,CDEFCI)略有不同,出现偏差主要是由指标权重侧重点不同引起。但从表 3可以看出,FPPC类别特征连续值与类别特征离散值之间误差均在0.03以下,明显小于其他方法,说明聚类效果更好。对不同模型的误差分析以及采用式(13)所示的3个有效性指标进行评价得到的聚类效果比较见表 4

      表 4  各模糊聚类方法误差分析及聚类有效性指标值比较

      Table 4.  Error Analysis and Clustering Validity Comparison of Different Fuzzy Clustering Methods

      评估方法聚类误差绝对值落在下列区间的样本个数聚类绝对误差均值聚类相对误差均值/%XBPEPC最小广义欧氏权距离平方和
      [0,0.1][0,0.2][0,0.3][0,0.4][0,0.5]
      FCI5789100.149 111.110.770 60.805 00.710 81.078 7
      CDEFCI89910100.066 46.410.015 10.188 30.945 86.625 1×10-3
      FPPC10101010100.004 00.360.005 20.062 30.985 81.859 8×10-3

      表 4中的指标值可见,FPPC聚类效果明显更优,样本欧氏距离平方和更小,且FPPC先对样本集进行降维处理至一维数据后再对其模糊聚类,运算复杂度远低于FCI及CDEFCI。

      聚类效果比较见图 3,其中圆球半径等于同等级中连续性等级值与相应离散等级值的最大偏差。由图 3可见FPPC明显优于FCI和CDEFCI。

      图  3  3种方法各等级聚类效果比较

      Figure 3.  Clustering Effect Comparison of Three Methods

    • 本文提出了一种先进的FPPC聚类算法,该算法融合了FCI算法和PPC算法。将式(9)、式(10)与式(4)、式(5)比较知,FPPC通过样本降维,降低了计算复杂度;而由于实现了FCI与PPC双重迭代聚类,与现有模糊聚类算法比较,FPPC提高了聚类准确性及效果;此外,与CCDE优化算法的良好结合也进一步保障了FPPC的良好效果。对样本集的实例仿真验证了FPPC聚类算法的有效性、准确性及客观性。因此,FPPC可以广泛运用在分类评估、模式识别工作中,并有望取得良好的效果。

参考文献 (19)

目录

    /

    返回文章
    返回