第11卷第2期 智能系统学报 Vol.11 No.2 2016年4月 CAAI Transactions on Intelligent Systems Apr.2016 D0I:10.11992/is.201507013 网络出版地址：http://www.cnki.net/kcms/detail/23.1538.TP.20160315.1239.014.html 适合大规模数据集的增量式模糊聚类算法 李滔，王士同 (江南大学数字媒体学院，江苏无锡214122) 摘要：FCPM算法已被成功地应用到模糊系统建模上，但其在某一类的聚类中心已知的大规模数据上的聚类性能 较差。为了避免这个缺点，参照单程模糊c均值(SPFCM)聚类算法、在线模糊c均值(OFCM)聚类算法，提出了适合 大规模数据集的增量式模糊聚类算法(Incremental fuzz四y(c+p)-means clustering,IFCM(c+p))。通过在每个数据块 中使用FCPM算法进行聚类，把每个数据块的聚类中心及其附近的一些样本点加入到下一个数据块参与聚类，同时 添加平衡因子以提高算法聚类性能。同SPFCM、OFCM以及rseFCM算法相比，IFCM(c+p)对初始聚类中心不敏感。 实验表明在没有花费很多运行时间的情况下，IFCM(c+p)算法的聚类性能比SPFCM算法和rseFCM算法更具优势， 因此该算法更适合处理某一类聚类中心已知的大规模数据集。 关键词：增量式模糊聚类；FCPM;IFCM(c+p);平衡因子；大规模数据集 中图分类号：TP391.4文献标志码：A文章编号：1673-4785(2016)02-0188-12 中文引用格式：李滔，王士同.适合大规模数据集的增量式模糊聚类算法[J].智能系统学报，2016,11(2)：188-199. 英文引用格式：LITao,WANG Shitong.Incremental fuzzy(c+tp-means clustering for large data[J】.CAAI transactions on intelli- gent systems,2016,11(2):188-199. Incremental fuzzy (c+p)-means clustering for large data LI Tao,WANG Shitong (School of Digital Media,Jiangnan University,Wuxi 214122,China) Abstract:FCPM has been demonstrated to be successful in fuzzy system modeling,however,it will be ineffective for large data clustering tasks where the cluster centers of one class are known.In order to circumvent this draw- back,referring to single-pass fuzzy c-means (SPFCM)clustering algorithm and online fuzzy c-means (OFCM) clustering algorithm,the incremental fuzzy clustering algorithm for large data called IFCM(c+p)is proposed in this paper.FCPM algorithm is used to cluster for each data block at first,and then the clustering centers of data block and some of the sample points being near them are joined into the next block to be clustered,meanwhile the bal- ance factor is given to enhance the clustering performance.In contrast to SPFCM,OFCM and rseFCM,IFCM(c+ p)is not sensitive to the initial cluster centers.The experiments indicate the proposed clustering algorithm IFCM(c +p)is competitive to the clustering algorithms SPFCM and rseFCM in the clustering performance without the loss of running time a lot,hence it is especially suitable for large data clustering tasks where the cluster centers of one class are known. Keywords:incremental fuzzy clustering;FCPM;IFCM(c+p);balance factor;large data 聚类就是将物理或抽象的对象按照自己的某些 属性聚集成类的过程，并尽可能使得类（或者簇）之 间对象的差异程度最大，而类内（或者簇内）的相似 收稿日期：2015-07-06.网络出版日期：2016-03-15 基金项目：国家自然科学基金项目(61272210). 程度达到最大。聚类过程没有先验知识指导，仅凭 通信作者：李滔.E-mail:chasingdreaml19@163.com. 对象间的相似程度作为类属划分的准则，是无监督
第 １１ 卷第 ２ 期 智 能 系 统 学 报 Ｖｏｌ．１１ №．２ ２０１６ 年 ４ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ａｐｒ． ２０１６ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ．２０１５０７０１３ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１６０３１５．１２３９．０１４．ｈｔｍｌ 适合大规模数据集的增量式模糊聚类算法 李滔，王士同 （江南大学 数字媒体学院，江苏 无锡 ２１４１２２） 摘 要：ＦＣＰＭ 算法已被成功地应用到模糊系统建模上，但其在某一类的聚类中心已知的大规模数据上的聚类性能 较差。 为了避免这个缺点，参照单程模糊 ｃ 均值（ＳＰＦＣＭ）聚类算法、在线模糊 ｃ 均值（ＯＦＣＭ）聚类算法，提出了适合 大规模数据集的增量式模糊聚类算法（Ｉｎｃｒｅｍｅｎｔａｌ ｆｕｚｚｙ （ｃ＋ｐ）⁃ｍｅａｎｓ ｃｌｕｓｔｅｒｉｎｇ ，ＩＦＣＭ（ ｃ＋ｐ））。 通过在每个数据块 中使用 ＦＣＰＭ 算法进行聚类，把每个数据块的聚类中心及其附近的一些样本点加入到下一个数据块参与聚类，同时 添加平衡因子以提高算法聚类性能。 同 ＳＰＦＣＭ、ＯＦＣＭ 以及 ｒｓｅＦＣＭ 算法相比，ＩＦＣＭ（ ｃ＋ｐ）对初始聚类中心不敏感。 实验表明在没有花费很多运行时间的情况下，ＩＦＣＭ（ｃ＋ｐ）算法的聚类性能比 ＳＰＦＣＭ 算法和 ｒｓｅＦＣＭ 算法更具优势， 因此该算法更适合处理某一类聚类中心已知的大规模数据集。 关键词：增量式模糊聚类；ＦＣＰＭ；ＩＦＣＭ（ｃ＋ｐ）；平衡因子；大规模数据集 中图分类号： ＴＰ３９１．４ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１６）０２⁃０１８８⁃１２ 中文引用格式：李滔，王士同． 适合大规模数据集的增量式模糊聚类算法［Ｊ］． 智能系统学报， ２０１６， １１（２）： １８８⁃１９９． 英文引用格式：ＬＩ Ｔａｏ， ＷＡＮＧ Ｓｈｉｔｏｎｇ． Ｉｎｃｒｅｍｅｎｔａｌ ｆｕｚｚｙ （ｃ＋ｐ）⁃ｍｅａｎｓ ｃｌｕｓｔｅｒｉｎｇ ｆｏｒ ｌａｒｇｅ ｄａｔａ［Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉ⁃ ｇｅｎｔ ｓｙｓｔｅｍｓ， ２０１６， １１（２）： １８８⁃１９９． Ｉｎｃｒｅｍｅｎｔａｌ ｆｕｚｚｙ （ ｃ＋ｐ） ⁃ｍｅａｎｓ ｃｌｕｓｔｅｒｉｎｇ ｆｏｒ ｌａｒｇｅ ｄａｔａ ＬＩ Ｔａｏ， ＷＡＮＧ Ｓｈｉｔｏｎｇ （Ｓｃｈｏｏｌ ｏｆ Ｄｉｇｉｔａｌ Ｍｅｄｉａ， Ｊｉａｎｇｎａｎ Ｕｎｉｖｅｒｓｉｔｙ， Ｗｕｘｉ ２１４１２２， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：ＦＣＰＭ ｈａｓ ｂｅｅｎ ｄｅｍｏｎｓｔｒａｔｅｄ ｔｏ ｂｅ ｓｕｃｃｅｓｓｆｕｌ ｉｎ ｆｕｚｚｙ ｓｙｓｔｅｍ ｍｏｄｅｌｉｎｇ， ｈｏｗｅｖｅｒ， ｉｔ ｗｉｌｌ ｂｅ ｉｎｅｆｆｅｃｔｉｖｅ ｆｏｒ ｌａｒｇｅ ｄａｔａ ｃｌｕｓｔｅｒｉｎｇ ｔａｓｋｓ ｗｈｅｒｅ ｔｈｅ ｃｌｕｓｔｅｒ ｃｅｎｔｅｒｓ ｏｆ ｏｎｅ ｃｌａｓｓ ａｒｅ ｋｎｏｗｎ． Ｉｎ ｏｒｄｅｒ ｔｏ ｃｉｒｃｕｍｖｅｎｔ ｔｈｉｓ ｄｒａｗ⁃ ｂａｃｋ， ｒｅｆｅｒｒｉｎｇ ｔｏ ｓｉｎｇｌｅ⁃ｐａｓｓ ｆｕｚｚｙ ｃ⁃ｍｅａｎｓ （ ＳＰＦＣＭ） ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ａｎｄ ｏｎｌｉｎｅ ｆｕｚｚｙ ｃ⁃ｍｅａｎｓ （ＯＦＣＭ） ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ， ｔｈｅ ｉｎｃｒｅｍｅｎｔａｌ ｆｕｚｚｙ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｌａｒｇｅ ｄａｔａ ｃａｌｌｅｄ ＩＦＣＭ（ｃ＋ｐ） ｉｓ ｐｒｏｐｏｓｅｄ ｉｎ ｔｈｉｓ ｐａｐｅｒ． ＦＣＰＭ ａｌｇｏｒｉｔｈｍ ｉｓ ｕｓｅｄ ｔｏ ｃｌｕｓｔｅｒ ｆｏｒ ｅａｃｈ ｄａｔａ ｂｌｏｃｋ ａｔ ｆｉｒｓｔ， ａｎｄ ｔｈｅｎ ｔｈｅ ｃｌｕｓｔｅｒｉｎｇ ｃｅｎｔｅｒｓ ｏｆ ｄａｔａ ｂｌｏｃｋ ａｎｄ ｓｏｍｅ ｏｆ ｔｈｅ ｓａｍｐｌｅ ｐｏｉｎｔｓ ｂｅｉｎｇ ｎｅａｒ ｔｈｅｍ ａｒｅ ｊｏｉｎｅｄ ｉｎｔｏ ｔｈｅ ｎｅｘｔ ｂｌｏｃｋ ｔｏ ｂｅ ｃｌｕｓｔｅｒｅｄ， ｍｅａｎｗｈｉｌｅ ｔｈｅ ｂａｌ⁃ ａｎｃｅ ｆａｃｔｏｒ ｉｓ ｇｉｖｅｎ ｔｏ ｅｎｈａｎｃｅ ｔｈｅ ｃｌｕｓｔｅｒｉｎｇ ｐｅｒｆｏｒｍａｎｃｅ． Ｉｎ ｃｏｎｔｒａｓｔ ｔｏ ＳＰＦＣＭ， ＯＦＣＭ ａｎｄ ｒｓｅＦＣＭ， ＩＦＣＭ（ｃ＋ ｐ） ｉｓ ｎｏｔ ｓｅｎｓｉｔｉｖｅ ｔｏ ｔｈｅ ｉｎｉｔｉａｌ ｃｌｕｓｔｅｒ ｃｅｎｔｅｒｓ． Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔｓ ｉｎｄｉｃａｔｅ ｔｈｅ ｐｒｏｐｏｓｅｄ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ＩＦＣＭ（ｃ ＋ｐ） ｉｓ ｃｏｍｐｅｔｉｔｉｖｅ ｔｏ ｔｈｅ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍｓ ＳＰＦＣＭ ａｎｄ ｒｓｅＦＣＭ ｉｎ ｔｈｅ ｃｌｕｓｔｅｒｉｎｇ ｐｅｒｆｏｒｍａｎｃｅ ｗｉｔｈｏｕｔ ｔｈｅ ｌｏｓｓ ｏｆ ｒｕｎｎｉｎｇ ｔｉｍｅ ａ ｌｏｔ， ｈｅｎｃｅ ｉｔ ｉｓ ｅｓｐｅｃｉａｌｌｙ ｓｕｉｔａｂｌｅ ｆｏｒ ｌａｒｇｅ ｄａｔａ ｃｌｕｓｔｅｒｉｎｇ ｔａｓｋｓ ｗｈｅｒｅ ｔｈｅ ｃｌｕｓｔｅｒ ｃｅｎｔｅｒｓ ｏｆ ｏｎｅ ｃｌａｓｓ ａｒｅ ｋｎｏｗｎ． Ｋｅｙｗｏｒｄｓ： ｉｎｃｒｅｍｅｎｔａｌ ｆｕｚｚｙ ｃｌｕｓｔｅｒｉｎｇ； ＦＣＰＭ； ＩＦＣＭ（ｃ＋ｐ）； ｂａｌａｎｃｅ ｆａｃｔｏｒ； ｌａｒｇｅ ｄａｔａ 收稿日期：２０１５⁃０７⁃０６． 网络出版日期：２０１６⁃０３⁃１５． 基金项目：国家自然科学基金项目（６１２７２２１０）． 通信作者：李滔． Ｅ⁃ｍａｉｌ：ｃｈａｓｉｎｇｄｒｅａｍ１１９＠ １６３．ｃｏｍ． 聚类就是将物理或抽象的对象按照自己的某些 属性聚集成类的过程，并尽可能使得类（或者簇）之 间对象的差异程度最大，而类内（或者簇内）的相似 程度达到最大。 聚类过程没有先验知识指导，仅凭 对象间的相似程度作为类属划分的准则，是无监督
第2期 李滔，等：适合大规模数据集的增量式模糊聚类算法 ·189· 分类学习的一部分。最为经典的模糊聚类算法之一 Jacek M.Leski对FCM算法进行了改进，提出了模 就是J.C.Bezdek教授在20世纪80年代提出的模糊 糊c+p均值聚类算法FCPM,并采用了新的方法初 c均值聚类算法[)，该算法被成功地应用到了在诸 始化聚类中心[。对于某一类的聚类中心，它能吸 多问题的解决上。 引属于该类的样本并排斥属于其他类的样本，这样 随着科学技术的发展，数据库中的数据更新速 更清楚地确定了样本的“归属”问题。对于小样本 度日益加快、数据容量不断增大，若仍然采用原来的 数据，FCPM算法可以保持不错的聚类性能，但其在 聚类算法对这样的大规模数据进行聚类将产生以下 大规模数据集上的聚类性能明显降低而且有较大的 几个问题：1)数据更新前得到的聚类结果可能与数 时间花费，甚至可能由于无法加载进内存而导致算 据更新后的聚类结果不匹配：2)对更新后的数据进 法失效。对于以往的增量式模糊聚类算法，比如 行重新聚类会导致较高的时间复杂度和计算资源的 SPFCM算法和OFCM算法都是通过对样本加权以 浪费：3)还可能由于系统内存不足的原因而导致该 影响每个数据块产生的聚类中心，但数据块间聚类 算法失效。鉴于这些问题，Fazli Can教授在1990年 中心的相互影响程度不明显甚至可能会由于上一次 提出的增量式聚类算法]使得这些问题得以解决。 聚类结果的加入而干扰新的数据进行聚类。为了解 所谓增量式聚类是指利用前期数据已取得的聚类结 决以上问题，通过FCPM算法计算每个数据块的聚 果，对新增数据进行分批或者逐批次地进行聚类的 类中心，把离聚类中心最近的一些样本点连同聚类 过程。研究增量式模糊聚类算法对于避免重复聚类 中心一起加入到下一个数据块中参与聚类，同时添 造成的计算资源浪费，提高聚类性能等都具有十分 加平衡项以提高聚类性能，文中提出了适合大规模 重要的意义。 数据集的增量式聚类算法FCM(c+p)。 近几年，研究者们提出了很多关于增量式聚类 1 相关算法 的算法。这些算法大致可以被分为3类：1)对大数 据进行随机抽样获取小样本进行计算，例如，L 设N元样本集合X={x1,x2,…,xw},x(k= Kaufman等提出的CLARA),S.Guha等)提出的 1,2,…,N)表示其中的某一个样本，其中每一个样 CURE:2)按序将小样本加载进内存的单程算法 本都有D={d,d2,…,dn}CR"一共n个特征，d (single--pass),具有代表性的有F.Can在文献[5]和 (j=1,2,…,n)表示其中的某一个特征。FCM算法 [6]中提出的增量式算法：3)采取类图表结构的数 将N个样本按照它所固有的特征划分成c簇，用4 据转换算法，如T.Zhang等提出的BIRCH刀和R. 表示第k个样本隶属于第i簇的程度，那么划分成c Ng等[)提出的CLARANS,对于增量式模糊聚类算 簇后得到的隶属度矩阵是U=u:}CRxw,i∈[1， 法；B.U.Shankar等提出了快速模糊c均值算法 c],k∈[1，N]。对于模糊划分而言，所有的样本都 FFCM,T.Chengt]提出了多阶段的随机模糊c均值 需要满足下面的条件： 算法MRFCM,J.E.Kolen等[)提出了随机抽样模 MeN={U∈RexN I Lik∈[0,1]， 糊c均值算法rsFCM,Dhanesh Kothari等I]提出了 i∈[1，c],k∈[1，N]}; 将随机抽样的结果扩展到整个数据集上的扩展随机 抽样模糊c均值算法rseFCM。除此之外，还有基于 FCM的单程模糊c均值算法SPFCM)、在线模糊c N 均值算法OFCM1),以及在这基础上发展的基于核 Vk∈[1，N]; 4e(0,W,ie[1,c] k=1 的模糊c均值算法spkFCM和okFCMU1],Yangtao 由此可见，模糊划分矩阵U的每一列的和都必 Wang等i提出的基于多重中心的增量式模糊聚类 须等于1，这样才能确保每一个样本都能够被完整 算法在相关性大数据上的应用。最近Bhm等[) 地划分到它所属的簇中。 受到动力学中同步现象的启发提出了一种新颖的同 通过使用欧式距离寻求最小均方误差，可以得 步聚类算法Symc,但是这种算法在大规模数据集上 到FCM模型的目标函数（其中m为模糊指数）： 的聚类受到了相当大的限制，基于此应文豪等]在 此基础上提出了快速自适应同步聚类算法FAKCS。 J(U,V)= ZZx-v. (1)》 i=1k= 传统的F℃M算法对初始聚类中心敏感且容易 在式(1)的条件下通过拉格朗日乘子法可以得 陷入局部最优，同时也忽略了类间的相互影响。 出隶属度矩阵U和聚类中心V的更新公式。由于
分类学习的一部分。 最为经典的模糊聚类算法之一 就是 Ｊ．Ｃ．Ｂｅｚｄｅｋ 教授在 ２０ 世纪 ８０ 年代提出的模糊 ｃ 均值聚类算法［１］ ，该算法被成功地应用到了在诸 多问题的解决上。 随着科学技术的发展，数据库中的数据更新速 度日益加快、数据容量不断增大，若仍然采用原来的 聚类算法对这样的大规模数据进行聚类将产生以下 几个问题：１）数据更新前得到的聚类结果可能与数 据更新后的聚类结果不匹配；２）对更新后的数据进 行重新聚类会导致较高的时间复杂度和计算资源的 浪费；３）还可能由于系统内存不足的原因而导致该 算法失效。 鉴于这些问题，Ｆａｚｌｉ Ｃａｎ 教授在 １９９０ 年 提出的增量式聚类算法［２］ 使得这些问题得以解决。 所谓增量式聚类是指利用前期数据已取得的聚类结 果，对新增数据进行分批或者逐批次地进行聚类的 过程。 研究增量式模糊聚类算法对于避免重复聚类 造成的计算资源浪费，提高聚类性能等都具有十分 重要的意义。 近几年，研究者们提出了很多关于增量式聚类 的算法。 这些算法大致可以被分为 ３ 类：１）对大数 据进行随机抽样获取小样本进行计算， 例如， Ｌ． Ｋａｕｆｍａｎ 等提出的 ＣＬＡＲＡ ［３］ ， Ｓ． Ｇｕｈａ 等［４］ 提出的 ＣＵＲＥ；２） 按序将小样本加载进内存的单程算法 （ｓｉｎｇｌｅ⁃ｐａｓｓ），具有代表性的有 Ｆ． Ｃａｎ 在文献［５］和 ［６］中提出的增量式算法；３）采取类图表结构的数 据转换算法，如 Ｔ． Ｚｈａｎｇ 等提出的 ＢＩＲＣＨ ［７］ 和 Ｒ． Ｎｇ 等［８］ 提出的 ＣＬＡＲＡＮＳ，对于增量式模糊聚类算 法；Ｂ． Ｕ． Ｓｈａｎｋａｒ 等［９］ 提出了快速模糊 ｃ 均值算法 ＦＦＣＭ，Ｔ． Ｃｈｅｎｇ ［１０］提出了多阶段的随机模糊 ｃ 均值 算法 ＭＲＦＣＭ，Ｊ． Ｆ． Ｋｏｌｅｎ 等［１１］ 提出了随机抽样模 糊 ｃ 均值算法 ｒｓＦＣＭ，Ｄｈａｎｅｓｈ Ｋｏｔｈａｒｉ 等［１２］ 提出了 将随机抽样的结果扩展到整个数据集上的扩展随机 抽样模糊 ｃ 均值算法 ｒｓｅＦＣＭ。 除此之外，还有基于 ＦＣＭ 的单程模糊 ｃ 均值算法 ＳＰＦＣＭ ［１３］ 、在线模糊 ｃ 均值算法 ＯＦＣＭ ［１４］ ，以及在这基础上发展的基于核 的模糊 ｃ 均值算法 ｓｐｋＦＣＭ 和 ｏｋＦＣＭ ［１５］ ，Ｙａｎｇｔａｏ Ｗａｎｇ 等［１６］提出的基于多重中心的增量式模糊聚类 算法在相关性大数据上的应用。 最近 Ｂöｈｍ 等［１７］ 受到动力学中同步现象的启发提出了一种新颖的同 步聚类算法 Ｓｙｎｃ，但是这种算法在大规模数据集上 的聚类受到了相当大的限制，基于此应文豪等［１８］ 在 此基础上提出了快速自适应同步聚类算法 ＦＡＫＣＳ。 传统的 ＦＣＭ 算法对初始聚类中心敏感且容易 陷入局部最优， 同时也忽略了类间的相互影响。 Ｊａｃｅｋ Ｍ． Ｌｅｓｋｉ 对 ＦＣＭ 算法进行了改进，提出了模 糊 ｃ＋ｐ 均值聚类算法 ＦＣＰＭ，并采用了新的方法初 始化聚类中心［１９］ 。 对于某一类的聚类中心，它能吸 引属于该类的样本并排斥属于其他类的样本，这样 更清楚地确定了样本的“归属” 问题。 对于小样本 数据，ＦＣＰＭ 算法可以保持不错的聚类性能，但其在 大规模数据集上的聚类性能明显降低而且有较大的 时间花费，甚至可能由于无法加载进内存而导致算 法失效。 对于以往的增量式模糊聚类算法，比如 ＳＰＦＣＭ 算法和 ＯＦＣＭ 算法都是通过对样本加权以 影响每个数据块产生的聚类中心，但数据块间聚类 中心的相互影响程度不明显甚至可能会由于上一次 聚类结果的加入而干扰新的数据进行聚类。 为了解 决以上问题，通过 ＦＣＰＭ 算法计算每个数据块的聚 类中心，把离聚类中心最近的一些样本点连同聚类 中心一起加入到下一个数据块中参与聚类，同时添 加平衡项以提高聚类性能，文中提出了适合大规模 数据集的增量式聚类算法 ＩＦＣＭ（ｃ＋ｐ）。 １ 相关算法 设 Ｎ 元样本集合 Ｘ ＝ ｛ ｘ１ ，ｘ２ ，…，ｘＮ｝ ， ｘｋ（ｋ ＝ １，２，…，Ｎ） 表示其中的某一个样本，其中每一个样 本都有 Ｄ ＝ ｛ｄ１ ，ｄ２ ，…，ｄｎ ｝ ⊂ Ｒ ｎ 一共 ｎ 个特征， ｄｊ （ｊ ＝１，２，…，ｎ） 表示其中的某一个特征。 ＦＣＭ 算法 将 Ｎ 个样本按照它所固有的特征划分成 ｃ 簇，用 μｉｋ 表示第 ｋ 个样本隶属于第 ｉ 簇的程度，那么划分成 ｃ 簇后得到的隶属度矩阵是 Ｕ ＝ ｛μｉｋ｝ ⊂ Ｒ ｃ×Ｎ ，ｉ ∈ ［１， ｃ］，ｋ ∈ ［１，Ｎ］ 。 对于模糊划分而言，所有的样本都 需要满足下面的条件： ＭｆｃＮ ＝ ｛Ｕ ∈ Ｒ ｃ×Ｎ ｜ μｉｋ ∈ ［０，１］， ∀ｉ ∈ ［１，ｃ］，ｋ ∈ ［１，Ｎ］｝； ∑ ｃ ｉ ＝ １ μｉｋ ＝ １， ∀ｋ ∈ ［１，Ｎ］；∑ Ｎ ｋ ＝ １ μｉｋ ∈ （０，Ｎ），∀ｉ ∈ ［１，ｃ］ ì î í ï ï ï ï ï ï ï ï 由此可见，模糊划分矩阵 Ｕ 的每一列的和都必 须等于 １，这样才能确保每一个样本都能够被完整 地划分到它所属的簇中。 通过使用欧式距离寻求最小均方误差，可以得 到 ＦＣＭ 模型的目标函数（其中 ｍ 为模糊指数）： Ｊ（Ｕ，Ｖ） ＝ ∑ ｃ ｉ ＝ １ ∑ Ｎ ｋ ＝ １ μ ｍ ｉｋ‖ ｘｋ － ｖｉ‖ ２ （１） 在式（１）的条件下通过拉格朗日乘子法可以得 出隶属度矩阵 Ｕ 和聚类中心 Ｖ 的更新公式。 由于 第 ２ 期 李滔，等： 适合大规模数据集的增量式模糊聚类算法 ·１８９·
·190 智能系统学报 第11卷 篇幅有限，FCM算法的具体更新公式以及计算步骤 献[19]详细介绍了新的聚类中心初始化方法及 在此不做赘述。 FCPM算法，此处不再赘述。 传统的F℃M算法让聚类中心尽可能地靠近样 如文献[19]所示，FCPM算法在模糊系统建模 本点，概率约束也只考虑了聚类中心之间的排斥力， 上得到了很好的应用。该算法采用新的初始化聚类 所有的样本重要性相同，同时对初始聚类中心敏感、 中心的方法有效地避免了CM算法对初始聚类中 容易陷入局部最优，得到的聚类结果往往不理想。 心敏感的问题，通过先确定已知类聚类中心来求未 Jacek M.Leski考虑了类别间的相互影响，利用了新 知类聚类中心的方法以提高算法的聚类性能。通过 的方法初始化聚类中心，采用固定一类求其他类的 实验可以发现，FCPM算法对一类已知的小样本数 方法，在FCM算法的基础上提出了模糊c+p均值聚 据集有着不错的聚类性能，但对现实中的大规模数 类算法FCPM。 据集而言，该算法的聚类性能会下降、算法效率会大 FCPM算法中来自其他类的样本对本类的聚类 大降低甚至会由于样本过大而导致算法失效。基于 会产生影响，在某一类中，聚类中心应该吸引属于该 这些问题，本文提出了适合大规模数据集的增量式 类的样本，而排斥其他类的样本。设有c个聚类中 模糊聚类算法IFCM(c+p)。 心来自一类，而p个聚类中心来自另一类，该算法把 N个样本划分成为c簇，可得目标函数为 2 适合大规模数据集的增量式模糊聚 J(U,T,V)= 名AI+ 类算法IFCM(c+p) 含区1 (2) 2.1FCM(c+p)算法 在增量式模糊聚类算法中，对每一个数据块进 式中：V表示第i簇的聚类中心，表示已知的聚类 行聚类的算法起着举足轻重的作用。针对以往基于 中心。对所有的样本而言，都应该满足如下关系： FCM的增量式模糊聚类算法对初始聚类中心敏感 之4a+2a=14e[0,1]. 的问题，文中采用了FCPM算法中提到的特别的方 i=1 j=1 法初始化聚类中心。另外在传统的增量式模糊聚类 54∈[0,1]，Vk∈[1，N] (3) 算法中，不管是静态的还是动态的、单程的还是在线 式中：“表示第k个样本属于第i簇的程度，t表 的、一个中心或者是多个中心（多个中心形成了一 示第k个样本属于第j簇的程度， 利用拉格朗 个约束对)等等的方法，都没有考虑数据块之间聚 日乘子法，可以得到划分矩阵U、T以及聚类中心V 类中心的相互影响，提及的FCM(c+p)算法很好地 的更新公式： 解决了这些问题。 ‖x-:川 为了增加数据块间聚类中心的相互影响程度， 儿= 点1岳+名 1x4-2,Ⅱ房 本文添加了一个平衡项“名I-旷，其中a Vk∈[1，N],ie[1,c] (4) 被称为平衡因子，往往它的取值与J(U,T,V)有 川-子1品 关。由此，可以得到提及算法的目标函数： 三1出高+名1-21品 r=1 J0,I.V=U,70+21V-I3 Vk∈[1，N],je[1,P] (5) 立 含宫11+名含G1 k=1 V= -,ie[1,c] (6) 名I%-rI (7) 式中："：表示第i簇的聚类中心，以表示第k个样 针对FCM算法对初始聚类中心敏感的问题， 本属于第i簇的程度，(.表示第k个样本属于第j FCPM算法采用了新的方法初始化聚类中心。通过 簇的程度，乙表示已知的第j簇的聚类中心，：表 该方法初始化未知类的聚类中心V,使用FCM算法 示经过FCPM算法得到的上一个数据块的聚类中 初始化已知类的聚类中心Z,再依次通过式(4)、 心。对所有的样本而言，都应该满足式(3)所示的 (5)和(6)获取模糊划分矩阵U和聚类中心V。文 关系
篇幅有限，ＦＣＭ 算法的具体更新公式以及计算步骤 在此不做赘述。 传统的 ＦＣＭ 算法让聚类中心尽可能地靠近样 本点，概率约束也只考虑了聚类中心之间的排斥力， 所有的样本重要性相同，同时对初始聚类中心敏感、 容易陷入局部最优，得到的聚类结果往往不理想。 Ｊａｃｅｋ Ｍ． Ｌｅｓｋｉ 考虑了类别间的相互影响，利用了新 的方法初始化聚类中心，采用固定一类求其他类的 方法，在 ＦＣＭ 算法的基础上提出了模糊 ｃ＋ｐ 均值聚 类算法 ＦＣＰＭ。 ＦＣＰＭ 算法中来自其他类的样本对本类的聚类 会产生影响，在某一类中，聚类中心应该吸引属于该 类的样本，而排斥其他类的样本。 设有 ｃ 个聚类中 心来自一类，而 ｐ 个聚类中心来自另一类，该算法把 Ｎ 个样本划分成为 ｃ 簇，可得目标函数为 Ｊ（Ｕ，Ｔ，Ｖ） ＝ ∑ ｃ ｉ ＝ １ ∑ Ｎ ｋ ＝ １ μ ｍ ｉｋ ‖ ｘｋ － ｖｉ‖２ ＋ ∑ ｐ ｊ ＝ １ ∑ Ｎ ｋ ＝ １ ζ ｍ ｊｋ ‖ ｘｋ － ｚｊ‖２ （２） 式中： Ｖｉ 表示第 ｉ 簇的聚类中心， ｚｊ 表示已知的聚类 中心。 对所有的样本而言，都应该满足如下关系： ∑ ｃ ｉ ＝ １ μｉｋ ＋ ∑ ｐ ｊ ＝ １ ζｊｋ ＝ １，μｉｋ ∈ ［０，１］， ζｊｋ ∈ ［０，１］，∀ｋ ∈ ［１，Ｎ］ （３） 式中： μｉｋ 表示第 ｋ 个样本属于第 ｉ 簇的程度， ζｊｋ 表 示第 ｋ 个样本属于第 ｊ 簇的程度， 利用拉格朗 日乘子法，可以得到划分矩阵 Ｕ、Ｔ 以及聚类中心 Ｖ 的更新公式： μｉｋ ＝ ‖ ｘｋ － ｖｉ‖ ２ １－ｍ ∑ ｃ ｌ ＝ １ ‖ ｘｋ － ｖｌ‖ ２ １－ｍ ＋ ∑ ｐ ｒ ＝ １ ‖ ｘｋ － ｚｒ‖ ２ １－ｍ ∀ｋ ∈ ［１，Ｎ］，ｉ ∈ ［１，ｃ］ （４） ζｊｋ ＝ ‖ｘｋ － ｚｊ‖ ２ １－ｍ ∑ ｃ ｌ ＝ １ ‖ ｘｋ － ｖｌ‖ ２ １－ｍ ＋ ∑ ｐ ｒ ＝ １ ‖ ｘｋ － ｚｒ‖ ２ １－ｍ ∀ｋ ∈ ［１，Ｎ］，ｊ ∈ ［１，ｐ］ （５） ｖｉ ＝ ∑ Ｎ ｋ ＝ １ μ ｍ ｉｋ ｘｋ ∑ Ｎ ｋ ＝ １ μ ｍ ｉｋ ，∀ｉ ∈ ［１，ｃ］ （６） 针对 ＦＣＭ 算法对初始聚类中心敏感的问题， ＦＣＰＭ 算法采用了新的方法初始化聚类中心。 通过 该方法初始化未知类的聚类中心 Ｖ，使用 ＦＣＭ 算法 初始化已知类的聚类中心 Ｚ，再依次通过式（ ４）、 （５）和（６）获取模糊划分矩阵 Ｕ 和聚类中心 Ｖ。 文 献［１９］ 详细介绍了新的聚类中心初始化方法及 ＦＣＰＭ 算法，此处不再赘述。 如文献［１９］所示，ＦＣＰＭ 算法在模糊系统建模 上得到了很好的应用。 该算法采用新的初始化聚类 中心的方法有效地避免了 ＦＣＭ 算法对初始聚类中 心敏感的问题，通过先确定已知类聚类中心来求未 知类聚类中心的方法以提高算法的聚类性能。 通过 实验可以发现，ＦＣＰＭ 算法对一类已知的小样本数 据集有着不错的聚类性能，但对现实中的大规模数 据集而言，该算法的聚类性能会下降、算法效率会大 大降低甚至会由于样本过大而导致算法失效。 基于 这些问题，本文提出了适合大规模数据集的增量式 模糊聚类算法 ＩＦＣＭ（ｃ＋ｐ）。 ２ 适合大规模数据集的增量式模糊聚 类算法 ＩＦＣＭ（ｃ＋ｐ） ２．１ ＩＦＣＭ（ｃ＋ｐ）算法 在增量式模糊聚类算法中，对每一个数据块进 行聚类的算法起着举足轻重的作用。 针对以往基于 ＦＣＭ 的增量式模糊聚类算法对初始聚类中心敏感 的问题，文中采用了 ＦＣＰＭ 算法中提到的特别的方 法初始化聚类中心。 另外在传统的增量式模糊聚类 算法中，不管是静态的还是动态的、单程的还是在线 的、一个中心或者是多个中心（多个中心形成了一 个约束对）等等的方法，都没有考虑数据块之间聚 类中心的相互影响，提及的 ＩＦＣＭ（ｃ＋ｐ）算法很好地 解决了这些问题。 为了增加数据块间聚类中心的相互影响程度， 本文添加了一个平衡项 α∑ ｃ ｉ ＝ １ ‖ ｖｉ － ｖ ｏ ｉ ‖２ ，其中 α 被称为平衡因子，往往它的取值与 Ｊ（Ｕ，Ｔ，Ｖ） 有 关。 由此，可以得到提及算法的目标函数： Ｊ（Ｕ，Ｔ，Ｖ，α） ＝ Ｊ（Ｕ，Ｔ，Ｖ） ＋ α∑ ｃ ｉ ＝ １ ‖ Ｖｉ － Ｖ ｏ ｉ ‖２ ＝ ∑ ｃ ｉ ＝ １ ∑ Ｎ ｋ ＝ １ μ ｍ ｉｋ ‖ ｘｋ － ｖｉ‖２ ＋ ∑ ｐ ｊ ＝ １ ∑ Ｎ ｋ ＝ １ ζ ｍ ｊｋ ‖ ｘｋ － ｚｊ‖２ ＋ α∑ ｃ ｉ ＝ １ ‖ ｖｉ － ｖ ｏ ｉ ‖２ （７） 式中： ｖｉ 表示第 ｉ 簇的聚类中心， μｉｋ 表示第 ｋ 个样 本属于第 ｉ 簇的程度， ζｊｋ 表示第 ｋ 个样本属于第 ｊ 簇的程度， ｚｊ 表示已知的第 ｊ 簇的聚类中心， Ｖ ｏ ｉ 表 示经过 ＦＣＰＭ 算法得到的上一个数据块的聚类中 心。 对所有的样本而言，都应该满足式（３） 所示的 关系。 ·１９０· 智 能 系 统 学 报 第 １１ 卷
第2期 李滔，等：适合大规模数据集的增量式模糊聚类算法 ·191· 下面采用拉格朗日极值法求模糊划分矩阵U、 整个数据集的聚类中心。 T以及聚类中心V的更新公式。 α=0时的情况仅仅考虑了某一数据块的聚类 G(U.T.V,A)= 中心及其周围的o个样本点对下一个数据块的聚 J〔U,T,a)-a(h4+-= 类性能的影响，这样得出的聚类效果并不理想。为 j=I 了提高聚类性能，应该考虑数据块间聚类中心的相 J(U,T,V)+a 互影响即α≠0时的情况，此时平衡项的加入很好 地提高了聚类性能。 A(∑u 如下所述为IFCM(c+p)算法的具体计算步骤。 j=1 输入：X,c,P,m,no,E; 输出：聚类中心V。 i= 1)把样本集x随机划分成大小相等的s个子集 即x={X,X2,…,X} i=1 Hk∈[1，N] (8) 2)定义一个空的集合Xnn和Xm; 对G(U,T,V,入)中的各个变量分别求偏导并 3)遍历所有的数据块获取聚类中心： 令其等于零得： forl=1,2,…,s ①初始化未知类和已知类的聚类中心V、Z: u山=m2g1x-:2-A=0 ②把从上一数据块获得的样本X添加到当 i=1 前数据块，即X,={X,UXae}; pu=m立1-名2-A=0 ③使用式(4)、(5)和(10)计算当前数据块 的聚类中心V,; -1=0 ④取出距当前数据块的聚类中心最近的n。个 i=1 i=1 样本点存入Xm中； 》=-2∑44x4-:‖+ ⑤把聚类中心V,及其附近的n。个样本点存人 8. i=1 Xn中，即Xm={V,UX}; 2a∑Iy:-I=0 end for i=1 上述算法步骤2)的X用以存放每一个数据 (9) 块产生的聚类中心及其附近的n。个样本点Xm, 通过(9)可以很容易地求出模糊划分矩阵的更 3)对这s个数据块进行遍历，求其聚类中心。3)中 新公式u和，如式(4)、(5)所示。可以发现，模 的主要迭代过程在每个数据块中使用FCPM算法计 糊划分矩阵U和T与平衡因子α无关。 算聚类中心，使用欧氏距离求距聚类中心最近的o 由式(9)第4个等式可得 个样本点，并把它们一同加入到下一个数据块中去 参与聚类。注意在初始化聚类中心时，采用前面提 ∑x4+a 到的FCPM算法的初始化方法对已知类和未知类的 k= V:= -,ie[1,c] (10) 聚类中心Z、V进行初始化，聚类中心V和模糊隶属 ∑a+a k=1 度矩阵U的更新公式分别为(10)、(4)，‖·‖表 从式(10)可以看出，根据平衡因子α是否等于 示求欧氏距离。FCPM算法的迭代终止于聚类中心 0,又可以分为两种情况。 的连续变化值的Frobenius范数小于ε。整个IFCM 当α=0即不考虑数据块间聚类中心的相互影 (c+p)算法终止于所有的数据块遍历结束并获得最 响时，在每一个数据块的聚类过程中，将某个数据块 终的聚类中心。 产生的聚类中心加入下一个数据块中参与聚类，为 2.2算法的可行性分析 了增大对数据块间聚类效果的影响程度，把距聚类 正如传统的增量式聚类算法一样，IFCM(c+p)算 中心最近的n。个样本点也一同加入下一个数据块 法对每个数据块进行聚类。在IFCM(c+p)算法中， 参与聚类，以此类推，直至计算出最后一个数据块的 没有添加平衡项时，将每个数据块的c个聚类中心及 聚类中心，这个最终的聚类中心就是我们所要求的 距其最近的。个样本点作为一次聚类结果的历史信
下面采用拉格朗日极值法求模糊划分矩阵 Ｕ、 Ｔ 以及聚类中心 Ｖ 的更新公式。 Ｇ（Ｕ，Ｔ，Ｖ，λ） ＝ Ｊ（Ｕ，Ｔ，Ｖ，α） － λ（∑ ｃ ｉ ＝ １ μｉｋ ＋ ∑ ｐ ｊ ＝ １ ζｊｋ － １） ＝ Ｊ（Ｕ，Ｔ，Ｖ） ＋ α∑ ｃ ｉ ＝ １ ‖ ｖｉ － ｖ ｏ ｉ ‖２ － λ（∑ ｃ ｉ ＝ １ μｉｋ ＋ ∑ ｐ ｊ ＝ １ ζｊｋ － １） ＝ ∑ ｃ ｉ ＝ １ μ ｍ ｉｋ ‖ ｘｋ － ｖｉ‖２ ＋ ∑ ｐ ｊ ＝ １ ζ ｍ ｊｋ ‖ ｘｋ － ｚｊ‖２ ＋ α∑ ｃ ｉ ＝ １ ‖ ｖｉ － ｖ ｏ ｉ ‖２ － λ（∑ ｃ ｉ ＝ １ μｉｋ ＋ ∑ ｐ ｊ ＝ １ ζｊｋ － １） ∀ｋ ∈ ［１，Ｎ］ （８） 对 Ｇ（Ｕ，Ｔ，Ｖ，λ） 中的各个变量分别求偏导并 令其等于零得： ∂Ｊ（Ｕ，Ｔ，Ｖ，λ） ∂μｉｋ ＝ ｍ∑ ｃ ｉ ＝ １ μ ｍ－１ ｉｋ ‖ ｘｋ － ｖｉ‖２ － λ ＝ ０ ∂Ｊ（Ｕ，Ｔ，Ｖ，λ） ∂ζｉｋ ＝ ｍ∑ ｃ ｉ ＝ １ ζ ｍ－１ ｊｋ ‖ ｘｋ － ｚｊ‖２ － λ ＝ ０ ∂Ｊ（Ｕ，Ｔ，Ｖ，λ） ∂λ ＝ ∑ ｃ ｉ ＝ １ μｉｋ ＋ ∑ ｐ ｊ ＝ １ ζｊｋ － １ ＝ ０ ∂Ｊ（Ｕ，Ｔ，Ｖ，λ） ∂ｖｉ ＝ － ２∑ ｃ ｉ ＝ １ μ ｍ ｉｋ‖ ｘｋ － ｖｉ‖ ＋ ２α∑ ｃ ｉ ＝ １ ‖ ｖｉ － ｖ ｏ ｉ ‖ ＝ ０ ì î í ï ï ï ï ï ï ï ï ï ï ï ï ï ï ïï （９） 通过（９）可以很容易地求出模糊划分矩阵的更 新公式 μｉｋ 和 ζｊｋ ，如式（４）、（５）所示。 可以发现，模 糊划分矩阵 Ｕ 和 Ｔ 与平衡因子 α 无关。 由式（９）第 ４ 个等式可得 ｖｉ ＝ ∑ Ｎ ｋ ＝ １ μ ｍ ｉｋ ｘｋ ＋ α ｖ ｏ ｉ ∑ Ｎ ｋ ＝ １ μ ｍ ｉｋ ＋ α ，∀ｉ ∈ ［１，ｃ］ （１０） 从式（１０）可以看出，根据平衡因子 α 是否等于 ０，又可以分为两种情况。 当 α ＝ ０ 即不考虑数据块间聚类中心的相互影 响时，在每一个数据块的聚类过程中，将某个数据块 产生的聚类中心加入下一个数据块中参与聚类，为 了增大对数据块间聚类效果的影响程度，把距聚类 中心最近的 ｎ０ 个样本点也一同加入下一个数据块 参与聚类，以此类推，直至计算出最后一个数据块的 聚类中心，这个最终的聚类中心就是我们所要求的 整个数据集的聚类中心。 α ＝ ０ 时的情况仅仅考虑了某一数据块的聚类 中心及其周围的 ｎ０ 个样本点对下一个数据块的聚 类性能的影响，这样得出的聚类效果并不理想。 为 了提高聚类性能，应该考虑数据块间聚类中心的相 互影响即 α ≠ ０ 时的情况，此时平衡项的加入很好 地提高了聚类性能。 如下所述为 ＩＦＣＭ（ｃ＋ｐ）算法的具体计算步骤。 输入：Ｘ， ｃ，ｐ，ｍ，ｎ０ ，ε ； 输出：聚类中心 Ｖ。 １）把样本集 ｘ 随机划分成大小相等的 ｓ 个子集 即 ｘ ＝ ｛Ｘ１ ，Ｘ２ ，…，Ｘｓ｝ ； ２）定义一个空的集合 Ｘｉｎｃｒｅ 和 Ｘｎｅａｒ ； ３）遍历所有的数据块获取聚类中心： ｆｏｒ ｌ ＝ １，２，…，ｓ ①初始化未知类和已知类的聚类中心 Ｖ、Ｚ； ②把从上一数据块获得的样本 Ｘｉｎｃｒｅ 添加到当 前数据块，即 Ｘｌ ＝ ｛Ｘｌ ∪ Ｘｉｎｃｒｅ｝ ； ③使用式（ ４） 、（ ５） 和（ １０） 计算当前数据块 的聚类中心 Ｖｌ ； ④取出距当前数据块的聚类中心最近的 ｎ０ 个 样本点存入 Ｘｎｅａｒ 中； ⑤把聚类中心 Ｖｌ 及其附近的 ｎ０ 个样本点存入 Ｘｉｎｃｒｅ 中，即 Ｘｉｎｃｒｅ ＝ ｛Ｖｌ ∪ Ｘｎｅａｒ｝ ； ｅｎｄ ｆｏｒ 上述算法步骤 ２）的 Ｘｉｎｃｒｅ 用以存放每一个数据 块产生的聚类中心及其附近的 ｎ０ 个样本点 Ｘｎｅａｒ ， ３）对这 ｓ 个数据块进行遍历，求其聚类中心。 ３）中 的主要迭代过程在每个数据块中使用 ＦＣＰＭ 算法计 算聚类中心，使用欧氏距离求距聚类中心最近的 ｎ０ 个样本点，并把它们一同加入到下一个数据块中去 参与聚类。 注意在初始化聚类中心时，采用前面提 到的 ＦＣＰＭ 算法的初始化方法对已知类和未知类的 聚类中心 Ｚ、Ｖ 进行初始化，聚类中心 Ｖ 和模糊隶属 度矩阵 Ｕ 的更新公式分别为（１０）、（４）， ‖·‖ 表 示求欧氏距离。 ＦＣＰＭ 算法的迭代终止于聚类中心 的连续变化值的 Ｆｒｏｂｅｎｉｕｓ 范数小于 ε。 整个 ＩＦＣＭ （ｃ＋ｐ）算法终止于所有的数据块遍历结束并获得最 终的聚类中心。 ２．２ 算法的可行性分析 正如传统的增量式聚类算法一样，ＩＦＣＭ（ｃ＋ｐ）算 法对每个数据块进行聚类。 在 ＩＦＣＭ（ｃ＋ｐ）算法中， 没有添加平衡项时，将每个数据块的 ｃ 个聚类中心及 距其最近的 ｎ０ 个样本点作为一次聚类结果的历史信 第 ２ 期 李滔，等： 适合大规模数据集的增量式模糊聚类算法 ·１９１·
·192· 智能系统学报 第11卷 息加入到新增数据中，即每次都有c+n。个样本点加 3 相关实验研究 入到新增数据中参与聚类，那么这些历史信息的加入 势必将影响新增数据的聚类效果。如果历史信息恰 3.1评价指标 好位于新增数据附近，则其聚类效果将变好，如果历 为了公正地对各聚类算法的聚类效果做出合理 史信息远离它们，历史信息的加入反而会导致一个很 的评价，本文采用如下3种评价指标进行算法的性 差的聚类效果。对于SPFCM算法和OFCM算法而 能分析。 言，它们通过添加样本权值以增加聚类效果，在一定 3.l.1算法运行时间的加速比speedup 程度上比仅仅添加历史信息得到的聚类效果要好，但 该指标反映了聚类算法在指定数据集下运行时 也存在上面所提到的一些问题。为了克服以上问题， 间的比较情况。定义加速比： 提到的FCM(c+p)算法添加了平衡项，通过平衡项 speedup =tfall/tineremental 中的平衡因子去改变数据块间聚类中心的相互影响 式中：t表示在整个数据集下采用FCPM算法所运 程度，此时即便历史信息远离新增数据，通过合理调 行的时间；incremea表示采用增量式算法比如SPF 节平衡因子α的取值也可以使得聚类中心吸引它周 CM、IFCM(c+p)等所运行的时间。 围的新增数据，从而提高聚类效果。 2)归一化互信息(normalized mutual informa- tion,NMI)[20-21] 2.3算法复杂度 文献[I5]详细介绍了rseFCM、SPFCM算法的 时间和空间复杂度，如表1所示，本文提到的CPM NMI 及FCM(c+p)算法的时间和空间复杂度也如表I 会N·会g 所示。其中t表示非增量式算法的迭代次数，t表 示增量式算法中每个数据块的平均迭代次数，d表 式中：N表示样本总数，N表示经本文聚类算法之 后第i簇的样本总数，N表示真实数据集的第j类 示数据集维数，c表示未知类的聚类个数，p表示已 的样本总数，M表示第i簇与第j类的契合程度，即 知类的聚类个数，s表示数据块的个数，。表示在 二者共有的样本总数。 IFCM(c+p)算法中距每个数据块的聚类中心最近的 3)芮氏指标(rand index,RI)[20-2] 样本点个数。 表1各算法的时间、空间复杂度 foo +f RI = -N(N-1)/2 Table 1 Time and space complexity of algorithms 式中：∫表示样本点具有不同的类标签并且属于不 算法 时间复杂度 空间复杂度 同类的配对样本数目，∫，则表示样本点具有相同的 FCPM O(tnd(c p)+te) O(n(d+c+p)) 类标签并且属于同一类的配对样本数目，N表示样 rseFCM 0(te'dn/s) O((d+c)n/s) 本总数。 SPFCM 0(nd'c2) 0((d+c)n/s) 以上NMI、I两种指标，其取值范围均为[O, 1],且取值越靠近1越能反映该聚类算法在某数据 IFCM(c+p)0(t'nd(c p)+t'c)O((d +e+p+no)n/'s) 集下的聚类效果越好，反之越靠近0则反映该聚类 如表1所示，本文提到的算法均在相同环境下 算法的聚类效果越差。加速比speedup越大反映了 运行，都对同一数据集X进行处理，时间复杂度都 增量式聚类算法的运行时间越短。 为O(n)。然而从第3部分的实验可以看出，各算 3.2实验结果 法的运行时间存在着显著不同。对于增量式模糊聚 1)实验环境 类算法，由于它们在每个数据块的处理中能够快速 本文所有的实验均在如表2的环境中进行。 收敛因而可以使得算法总的运行时间减少。 2)实验数据集 本文提到的增量式模糊聚类算法都是对数据进 实验所选取的数据集包括人工数据集2D15 行分块处理，因此需要计算每个数据块所占用的空 http://www.uef.fi/en/sipu/datasets)UCI http:// 间即为n/s。如表1所示，同seFCM和SPFCM算 archive.ics.uci.edu/ml/datasets..html)、标准数据集 法相比，由于IFCM(c+p)算法需要存储聚类中心及 waveform、forest和手写数字数据集MNIST(htp:/ 其周围的一些样本，因此需要占用相对较多的存储 yann.lecun.com/exdb/mnist/)。各数据集的分布情 空间，也就拥有相对高的空间复杂度。 况如表3
息加入到新增数据中，即每次都有 ｃ ＋ ｎ０ 个样本点加 入到新增数据中参与聚类，那么这些历史信息的加入 势必将影响新增数据的聚类效果。 如果历史信息恰 好位于新增数据附近，则其聚类效果将变好，如果历 史信息远离它们，历史信息的加入反而会导致一个很 差的聚类效果。 对于 ＳＰＦＣＭ 算法和 ＯＦＣＭ 算法而 言，它们通过添加样本权值以增加聚类效果，在一定 程度上比仅仅添加历史信息得到的聚类效果要好，但 也存在上面所提到的一些问题。 为了克服以上问题， 提到的 ＩＦＣＭ（ｃ＋ｐ）算法添加了平衡项，通过平衡项 中的平衡因子去改变数据块间聚类中心的相互影响 程度，此时即便历史信息远离新增数据，通过合理调 节平衡因子 α 的取值也可以使得聚类中心吸引它周 围的新增数据，从而提高聚类效果。 ２．３ 算法复杂度 文献［１５］ 详细介绍了 ｒｓｅＦＣＭ、ＳＰＦＣＭ 算法的 时间和空间复杂度，如表 １ 所示，本文提到的 ＦＣＰＭ 及 ＩＦＣＭ（ ｃ＋ｐ） 算法的时间和空间复杂度也如表 １ 所示。 其中 ｔ 表示非增量式算法的迭代次数， ｔ ＇ 表 示增量式算法中每个数据块的平均迭代次数， ｄ 表 示数据集维数， ｃ 表示未知类的聚类个数， ｐ 表示已 知类的聚类个数， ｓ 表示数据块的个数， ｎ０ 表示在 ＩＦＣＭ（ｃ＋ｐ）算法中距每个数据块的聚类中心最近的 样本点个数。 表 １ 各算法的时间、空间复杂度 Ｔａｂｌｅ １ Ｔｉｍｅ ａｎｄ ｓｐａｃｅ ｃｏｍｐｌｅｘｉｔｙ ｏｆ ａｌｇｏｒｉｔｈｍｓ 算法 时间复杂度 空间复杂度 ＦＣＰＭ Ｏ（ｔｎｄ（ｃ ＋ ｐ） ＋ ｔｃ） Ｏ（ｎ（ｄ ＋ ｃ ＋ ｐ）） ｒｓｅＦＣＭ Ｏ（ｔｃ ２ ｄｎ ／ ｓ） Ｏ（（ｄ ＋ ｃ）ｎ ／ ｓ） ＳＰＦＣＭ Ｏ（ｎｄｔ′ｃ ２ ） Ｏ（（ｄ ＋ ｃ）ｎ ／ ｓ） ＩＦＣＭ（ｃ＋ｐ） Ｏ（ｔ′ｎｄ（ｃ ＋ ｐ） ＋ ｔ′ｃ） Ｏ（（ｄ ＋ ｃ ＋ ｐ ＋ ｎ０ ）ｎ ／ ｓ） 如表 １ 所示，本文提到的算法均在相同环境下 运行，都对同一数据集 Ｘ 进行处理，时间复杂度都 为 Ｏ（ｎ） 。 然而从第 ３ 部分的实验可以看出，各算 法的运行时间存在着显著不同。 对于增量式模糊聚 类算法，由于它们在每个数据块的处理中能够快速 收敛因而可以使得算法总的运行时间减少。 本文提到的增量式模糊聚类算法都是对数据进 行分块处理，因此需要计算每个数据块所占用的空 间即为 ｎ ／ ｓ 。 如表 １ 所示，同 ｒｓｅＦＣＭ 和 ＳＰＦＣＭ 算 法相比，由于 ＩＦＣＭ（ｃ＋ｐ）算法需要存储聚类中心及 其周围的一些样本，因此需要占用相对较多的存储 空间，也就拥有相对高的空间复杂度。 ３ 相关实验研究 ３．１ 评价指标 为了公正地对各聚类算法的聚类效果做出合理 的评价，本文采用如下 ３ 种评价指标进行算法的性 能分析。 ３．１．１ 算法运行时间的加速比 ｓｐｅｅｄｕｐ 该指标反映了聚类算法在指定数据集下运行时 间的比较情况。 定义加速比： ｓｐｅｅｄｕｐ ＝ ｔ ｆｕｌｌ ／ ｔ ｉｎｃｒｅｍｅｎｔａｌ 式中： ｔ ｆｕｌｌ 表示在整个数据集下采用 ＦＣＰＭ 算法所运 行的时间； ｔ ｉｎｃｒｅｍｅｎｔａｌ 表示采用增量式算法比如 ＳＰＦ⁃ ＣＭ、ＩＦＣＭ（ｃ＋ｐ）等所运行的时间。 ２） 归一化互信息 （ ｎｏｒｍａｌｉｚｅｄ ｍｕｔｕａｌ ｉｎｆｏｒｍａ⁃ ｔｉｏｎ，ＮＭＩ） ［２０⁃２１］ ＮＭＩ ＝ ∑ ｃ ｉ ＝ １ ∑ ｃ ｊ ＝ １ Ｎ ｊ ｉ ｌｏｇ Ｎ·Ｎ ｊ ｉ Ｎｉ·Ｎｊ æ è ç ö ø ÷ ∑ ｃ ｉ ＝ １ Ｎｉ ｌｏｇ Ｎｉ Ｎ æ è ç ö ø ÷ · ∑ ｃ ｊ ＝ １ Ｎｊ ｌｏｇ Ｎｊ Ｎ æ è ç ö ø ÷ 式中： Ｎ 表示样本总数， Ｎｉ 表示经本文聚类算法之 后第 ｉ 簇的样本总数， Ｎｊ 表示真实数据集的第 ｊ 类 的样本总数， Ｎ ｊ ｉ 表示第 ｉ 簇与第 ｊ 类的契合程度，即 二者共有的样本总数。 ３）芮氏指标（ｒａｎｄ ｉｎｄｅｘ，ＲＩ） ［２０⁃２２］ ＲＩ ＝ ｆ ００ ＋ ｆ １１ Ｎ（Ｎ － １） ／ ２ 式中： ｆ ００ 表示样本点具有不同的类标签并且属于不 同类的配对样本数目， ｆ １１ 则表示样本点具有相同的 类标签并且属于同一类的配对样本数目， Ｎ 表示样 本总数。 以上 ＮＭＩ、ＲＩ 两种指标，其取值范围均为［ ０， １］，且取值越靠近 １ 越能反映该聚类算法在某数据 集下的聚类效果越好，反之越靠近 ０ 则反映该聚类 算法的聚类效果越差。 加速比 ｓｐｅｅｄｕｐ 越大反映了 增量式聚类算法的运行时间越短。 ３．２ 实验结果 １）实验环境 本文所有的实验均在如表 ２ 的环境中进行。 ２）实验数据集 实验所选取的数据集包括人工数据集 ２Ｄ１５ （ ｈｔｔｐ： ／ ／ ｗｗｗ． ｕｅｆ． ｆｉ ／ ｅｎ ／ ｓｉｐｕ ／ ｄａｔａｓｅｔｓ）、ＵＣＩ （ ｈｔｔｐ： ／ ／ ａｒｃｈｉｖｅ．ｉｃｓ． ｕｃｉ． ｅｄｕ ／ ｍｌ ／ ｄａｔａｓｅｔｓ． ｈｔｍｌ）、 标准数据集 ｗａｖｅｆｏｒｍ、ｆｏｒｅｓｔ 和手写数字数据集 ＭＮＩＳＴ（ ｈｔｔｐ： ／ ／ ｙａｎｎ．ｌｅｃｕｎ． ｃｏｍ ／ ｅｘｄｂ ／ ｍｎｉｓｔ ／ ）。 各数据集的分布情 况如表 ３。 ·１９２· 智 能 系 统 学 报 第 １１ 卷
第2期 李滔，等：适合大规模数据集的增量式模糊聚类算法 ·193 表2实验环境 本文中所有的参数都按如下取值：模糊指数 Table 2 Experiment environment m取2，最大迭代次数均为100，迭代终止参数ε 结构 具体参数 取1e-3,聚类中心附近的样本点个数no取5，其 操作系统 Windows7专业版64位 中数据集2D15、waveform重复试验50次，由于数 处理器 Intel(R)Xeon(R)E5-1620 v2@3.7GHz 据集MNIST和forest样本过大，我们重复试验20 运行内存 64G 次。数据块的大小应由用户指定，但在实验中， 软件及版本 MATLAB7.11.0.584(R2010h) 由于计算机内存受限，forest数据集的数据块大 小依次取0.1%、0.5%、1%、2.5%、5%，其余均按 表3各数据集的分布情况 照整个数据集的1%、2.5%、5%、10%、25%、50% Table 3 Distribution of the datasets 随机抽取。取MNIST数据集70%的样本、forest 数据集 大小 维数 类别数 数据集10%的样本参与FCPM算法的聚类。平 2D15 5000 2 15 衡因子α的具体取值也由用户指定，但是必须在 waveform 5000 21 3 给定的经验值范围内取值，本文中的所有α值均 forest 581012 54 7 是在多次重复实验中，提到的聚类指标的均值达 MNIST 70000 784 10 到最好的时候的取值。我们计算提到的几种算 MNIST数据集是手写数字集的一个子集，包含了 法在各个数据集上的NMI和RI的最值、均值以 70000张28×28像素的数字0~9的图像，每个像素 及标准差，其中均值反映了算法的平均聚类性 都在整数0~255之间取值。为加快运算，对MNIST 能，最值和标准差反映了算法的稳定鲁棒性。 数据集中的所有样本分别除以255进行归一化处 4)算法性能比较 理1s。为方便计算，本文随机取forest的581000个 本文采用SPFCM算法和rseFCM算法同IFCM 样本进行计算。同样，对其他数据集也进行归一化处 (c+p)算法在聚类性能和加速比上进行比较。 理以加快运算，即用每个特征的所有样本与该特征的 1)各算法在数据集上的聚类性能比较 最小值作差再除以该特征的最大值与最小值之差。 各算法在指定数据集下的聚类性能如表4~11 3)实验参数设置 所示，其中最优均值已用黑体标出。 表4FCM(c+p)、SPFCM、rseFCM算法的NMI值 Table 4 NMI of IFCM(c+p),SPFCM,rseFCM FCM(c+p)(a=2.1) IFCM(c+p)(a=0) SPFCM rseFCM 样本大小 avg. std. avg. std. avg. std. avg. std. 0.4107 0.0233 0.4091 0.0026 0.3909 0.0074 0.3078 0.0037 1% 0.3855 0.4398 0.3980 0.4173 0.3567 0.4248 0.3061 0.3332 0.4329 0.0062 0.3484 0 0.3613 0.0018 0.3199 0.0040 2.50% 0.4320 0.4756 0.3472 0.3485 0.3488 0.3616 0.3185 0.3474 0.4194 0.0079 0.3345 0.0010 0.3369 0 0.3463 0 5% 0.3872 0.4220 0.3343 0.3415 0.3365 0.3371 0.3463 0.3464 0.3411 a 0.3332 0 0.3259 0 0.2964 0 10% 0.3409 0.3415 0.3299 0.3333 0.3258 0.3263 0.2958 0.2968 0.3350 0.0049 0.3308 0 0.3245 0 0.3362 0 25% 0.3025 0.3442 0.3307 0.3309 0.3237 0.3251 0.3361 0.3363 0.3656 0 0.3253 0 0.3311 0 0.3259 0 35% 0.3617 0.3660 0.3251 0.3254 0.3311 0.3312 0.3257 0.3265 0.3556 0 0.3354 0 0.3361 0 0.3241 50% 0 0.3554 0.3558 0.3353 0.3354 0.3349 0.3365 0.3239 0.3246 0.3285 0.0081 FCPM 0.2892 0.3302 从各表中的实验结果对比发现，增量式模糊聚 类算法的聚类性能均优于FCPM算法。在人工数据
表 ２ 实验环境 Ｔａｂｌｅ ２ Ｅｘｐｅｒｉｍｅｎｔ ｅｎｖｉｒｏｎｍｅｎｔ 结构 具体参数 操作系统 Ｗｉｎｄｏｗｓ ７ 专业版 ６４ 位 处理器 Ｉｎｔｅｌ（Ｒ）Ｘｅｏｎ（Ｒ）Ｅ５⁃１６２０ ｖ２＠ ３．７ＧＨｚ 运行内存 ６４Ｇ 软件及版本 ＭＡＴＬＡＢ ７．１１．０．５８４ （Ｒ２０１０ｂ） 表 ３ 各数据集的分布情况 Ｔａｂｌｅ ３ Ｄｉｓｔｒｉｂｕｔｉｏｎ ｏｆ ｔｈｅ ｄａｔａｓｅｔｓ 数据集 大小 维数 类别数 ２Ｄ１５ ５ ０００ ２ １５ ｗａｖｅｆｏｒｍ ５ ０００ ２１ ３ ｆｏｒｅｓｔ ５８１ ０１２ ５４ ７ ＭＮＩＳＴ ７０ ０００ ７８４ １０ ＭＮＩＳＴ 数据集是手写数字集的一个子集，包含了 ７０ ０００ 张 ２８ × ２８ 像素的数字 ０～９ 的图像，每个像素 都在整数 ０ ～ ２５５ 之间取值。 为加快运算，对 ＭＮＩＳＴ 数据集中的所有样本分别除以 ２５５ 进行归一化处 理［１５］ 。 为方便计算，本文随机取 ｆｏｒｅｓｔ 的 ５８１ ０００ 个 样本进行计算。 同样，对其他数据集也进行归一化处 理以加快运算，即用每个特征的所有样本与该特征的 最小值作差再除以该特征的最大值与最小值之差。 ３）实验参数设置 本文中所有的参数都按如下取值：模糊指数 ｍ 取 ２，最大迭代次数均为 １００，迭代终止参数 ε 取 １ｅ－３，聚类中心附近的样本点个数 ｎ０ 取 ５，其 中数据集 ２Ｄ１５、ｗａｖｅｆｏｒｍ 重复试验 ５０ 次，由于数 据集 ＭＮＩＳＴ 和 ｆｏｒｅｓｔ 样本过大，我们重复试验 ２０ 次。 数据块的大小应由用户指定，但在实验中， 由于计算机内存受限， ｆｏｒｅｓｔ 数据集的数据块大 小依次取０．１％、０． ５％、１％、２． ５％、５％，其余均按 照整个数据集的 １％、２．５％、５％、１０％、２５％、５０％ 随机抽取。 取 ＭＮＩＳＴ 数据集 ７０％ 的样本、 ｆｏｒｅｓｔ 数据集 １０％ 的样本参与 ＦＣＰＭ 算法的聚类。 平 衡因子 α 的具体取值也由用户指定，但是必须在 给定的经验值范围内取值，本文中的所有 α 值均 是在多次重复实验中，提到的聚类指标的均值达 到最好的时候的取值。 我们计算提到的几种算 法在各个数据集上的 ＮＭＩ 和 ＲＩ 的最值、均值以 及标准差，其中均值反映了算法的 平 均 聚 类 性 能，最值和标准差反映了算法的稳定鲁棒性。 ４）算法性能比较 本文采用 ＳＰＦＣＭ 算法和 ｒｓｅＦＣＭ 算法同 ＩＦＣＭ （ｃ＋ｐ）算法在聚类性能和加速比上进行比较。 １）各算法在数据集上的聚类性能比较 各算法在指定数据集下的聚类性能如表 ４ ～ １１ 所示，其中最优均值已用黑体标出。 表 ４ ＩＦＣＭ（ｃ＋ｐ）、ＳＰＦＣＭ、ｒｓｅＦＣＭ 算法的 ＮＭＩ 值 Ｔａｂｌｅ ４ ＮＭＩ ｏｆ ＩＦＣＭ（ｃ＋ｐ）， ＳＰＦＣＭ， ｒｓｅＦＣＭ 样本大小 ＩＦＣＭ（ｃ＋ｐ）（ α ＝ ２．１） ａｖｇ． ｓｔｄ． ＩＦＣＭ（ｃ＋ｐ）（ α ＝ ０） ａｖｇ． ｓｔｄ． ＳＰＦＣＭ ａｖｇ． ｓｔｄ． ｒｓｅＦＣＭ ａｖｇ． ｓｔｄ． １％ ０．４１０ ７ ０．０２３ ３ ０．４０９ １ ０．００２ ６ ０．３９０ ９ ０．００７ ４ ０．３０７ ８ ０．００３ ７ ０．３８５ ５ ０．４３９ ８ ０．３９８ ０ ０．４１７ ３ ０．３５６ ７ ０．４２４ ８ ０．３０６ １ ０．３３３ ２ ２．５０％ ０．４３２ ９ ０．００６ ２ ０．３４８ ４ ０ ０．３６１ ３ ０．００１ ８ ０．３１９ ９ ０．００４ ０ ０．４３２ ０ ０．４７５ ６ ０．３４７ ２ ０．３４８ ５ ０．３４８ ８ ０．３６１ ６ ０．３１８ ５ ０．３４７ ４ ５％ ０．４１９ ４ ０．００７ ９ ０．３３４ ５ ０．００１ ０ ０．３３６ ９ ０ ０．３４６ ３ ０ ０．３８７ ２ ０．４２２ ０ ０．３３４ ３ ０．３４１ ５ ０．３３６ ５ ０．３３７ １ ０．３４６ ３ ０．３４６ ４ １０％ ０．３４１ １ ０ ０．３３３ ２ ０ ０．３２５ ９ ０ ０．２９６ ４ ０ ０．３４０ ９ ０．３４１ ５ ０．３２９ ９ ０．３３３ ３ ０．３２５ ８ ０．３２６ ３ ０．２９５ ８ ０．２９６ ８ ２５％ ０．３３５ ０ ０．００４ ９ ０．３３０ ８ ０ ０．３２４ ５ ０ ０．３３６ ２ ０ ０．３０２ ５ ０．３４４ ２ ０．３３０ ７ ０．３３０ ９ ０．３２３ ７ ０．３２５ １ ０．３３６ １ ０．３３６ ３ ３５％ ０．３６５ ６ ０ ０．３２５ ３ ０ ０．３３１ １ ０ ０．３２５ ９ ０ ０．３６１ ７ ０．３６６ ０ ０．３２５ １ ０．３２５ ４ ０．３３１ １ ０．３３１ ２ ０．３２５ ７ ０．３２６ ５ ５０％ ０．３５５ ６ ０ ０．３３５ ４ ０ ０．３３６ １ ０ ０．３２４ １ ０ ０．３５５ ４ ０．３５５ ８ ０．３３５ ３ ０．３３５ ４ ０．３３４ ９ ０．３３６ ５ ０．３２３ ９ ０．３２４ ６ ＦＣＰＭ ０．３２８ ５ ０．００８ １ ０．２８９ ２ ０．３３０ ２ 从各表中的实验结果对比发现，增量式模糊聚 类算法的聚类性能均优于 ＦＣＰＭ 算法。 在人工数据 第 ２ 期 李滔，等： 适合大规模数据集的增量式模糊聚类算法 ·１９３·
194. 智能系统学报 第11卷 集2D15的聚类性能比较中发现数据块大小取 其他算法不具备的。另外还可以发现随着数据块大 25%、35%和50%时，rseFCM算法和SPFCM算法的 小的增加，所有增量式模糊聚类算法的聚类性能均 聚类性能略优于IFCM(c+p)算法，对类似2DI5这 呈下降趋势，这是由于本文提及的增量式算法均采 样的小样本数据集而言这种情况是可能的，而FCM 用分块处理的方式，随着数据块大小的增加直至接 (c+p)算法在大规模数据集的聚类问题上可以表现 近原数据集大小时，在某数据块中聚类就相当于在 出很好的效果。在本文提到的其他数据集中，FCM 整个数据集上进行聚类，很明显这样增加算法运行 (c+p)算法均能保持最好的聚类性能。在高维大样 时间的同时还降低了聚类性能。另外还注意到对于 本的手写数字集MNIST和大样本的forest数据集的 大样本数据，随机抽取的数据块较小时rseFCM算法 实验结果中可以发现FCM(c+p)算法在提高了聚 会由于无法加载进内存而致使该算法失效，而FCM 类性能的同时还具备很好的稳定鲁棒性，这是本文 (c+p)算法不用担心这个问题。 表5IFCM(c+p)、SPFCM、rseFCM算法在2D15数据集中的NMI值 Table 5 NMI of IFCM(c+p),SPFCM,rseFCM for 2D15 dataset FCM(c+p)(a=2.1) IFCM(c+p)(a =0) SPFCM rseFCM 样本大小 avg. std. avg. std. avg. std. avg. std. 0.9399 0.0244 0.8438 0.0312 0.9260 0.0164 0.8688 0.0213 1% 0.8785 0.9870 0.7699 0.9055 0.8972 0.9494 0.8195 0.9137 0.9348 0.0100 0.8695 0.0193 0.9302 0.0163 0.8965 0.0252 2.509% 0.9000 0.9553 0.8278 0.9238 0.9042 0.9513 0.8298 0.9410 0.9519 0.0159 0.9123 0.0086 0.943 0.0165 0.9035 0.0202 5% 0.9155 0.9715 0.8783 0.9262 0.9055 0.9606 0.8652 0.9433 0.9369 0.0084 0.8775 0.0047 0.9313 0.0115 0.9200 0.0193 10% 0.9284 0.9507 0.8717 0.8882 0.8906 0.9449 0.8776 0.9432 0.9260 0 0.8646 0.0130 0.9222 0.0147 0.9294 0.0195 25% 0.9255 0.9263 0.8259 0.8713 0.8958 0.9405 0.8866 0.9509 0.9137 0.0248 0.9097 0 0.9270 0.0157 0.9214 0.0208 35% 0.8952 0.9474 0.9087 0.9104 0.8992 0.9431 0.8652 0.9438 0.9118 0 0.9079 0 0.921 0.0174 0.9169 0.02 50% 0.9111 0.9122 0.9076 0.9083 0.8839 0.9439 0.8696 0.9425 0.8607 0 FCPM 0.8604 0.8608 表6FCM(c+p)、SPFCM、rseFCM算法在MNIST数据集中的NMI值 Table 6 NMI of IFCM(c+p),SPFCM,rseFCM for MNIST dataset FCM(c+p)(a=160) IFCM(c+p)(a =0) SPFCM rseFCM 样本大小 avg. std. avg. std. avg. std. avg. std. 0.3139 0 0.2447 0 0.2246 0.0709 1% 0.3139 0.3139 0.2447 0.2447 0.1337 0.3345 0.2606 0 0.2390 0 0.2588 0.0310 2.50% 0.2606 0.2606 0.2390 0.2390 0.1915 0.3173 0.2974 0 0.1646 0 0.2424 0.0423 5% 0.2974 0.2974 0.1646 0.1646 0.1417 0.2987
集 ２Ｄ１５ 的 聚 类 性 能 比 较 中 发 现 数 据 块 大 小 取 ２５％、３５％和 ５０％时，ｒｓｅＦＣＭ 算法和 ＳＰＦＣＭ 算法的 聚类性能略优于 ＩＦＣＭ（ ｃ＋ｐ）算法，对类似 ２Ｄ１５ 这 样的小样本数据集而言这种情况是可能的，而 ＩＦＣＭ （ｃ＋ｐ）算法在大规模数据集的聚类问题上可以表现 出很好的效果。 在本文提到的其他数据集中，ＩＦＣＭ （ｃ＋ｐ）算法均能保持最好的聚类性能。 在高维大样 本的手写数字集 ＭＮＩＳＴ 和大样本的 ｆｏｒｅｓｔ 数据集的 实验结果中可以发现 ＩＦＣＭ（ ｃ＋ｐ） 算法在提高了聚 类性能的同时还具备很好的稳定鲁棒性，这是本文 其他算法不具备的。 另外还可以发现随着数据块大 小的增加，所有增量式模糊聚类算法的聚类性能均 呈下降趋势，这是由于本文提及的增量式算法均采 用分块处理的方式，随着数据块大小的增加直至接 近原数据集大小时，在某数据块中聚类就相当于在 整个数据集上进行聚类，很明显这样增加算法运行 时间的同时还降低了聚类性能。 另外还注意到对于 大样本数据，随机抽取的数据块较小时 ｒｓｅＦＣＭ 算法 会由于无法加载进内存而致使该算法失效，而 ＩＦＣＭ （ｃ＋ｐ）算法不用担心这个问题。 表 ５ ＩＦＣＭ（ｃ＋ｐ）、ＳＰＦＣＭ、ｒｓｅＦＣＭ 算法在 ２Ｄ１５ 数据集中的 ＮＭＩ 值 Ｔａｂｌｅ ５ ＮＭＩ ｏｆ ＩＦＣＭ（ｃ＋ｐ）， ＳＰＦＣＭ， ｒｓｅＦＣＭ ｆｏｒ ２Ｄ１５ ｄａｔａｓｅｔ 样本大小 ＩＦＣＭ（ｃ＋ｐ）（ α ＝ ２．１） ａｖｇ． ｓｔｄ． ＩＦＣＭ（ｃ＋ｐ）（ α ＝ ０） ａｖｇ． ｓｔｄ． ＳＰＦＣＭ ａｖｇ． ｓｔｄ． ｒｓｅＦＣＭ ａｖｇ． ｓｔｄ． １％ ０．９３９ ９ ０．０２４ ４ ０．８４３ ８ ０．０３１ ２ ０．９２６ ０ ０．０１６ ４ ０．８６８ ８ ０．０２１ ３ ０．８７８ ５ ０．９８７ ０ ０．７６９ ９ ０．９０５ ５ ０．８９７ ２ ０．９４９ ４ ０．８１９ ５ ０．９１３ ７ ２．５０％ ０．９３４ ８ ０．０１０ ０ ０．８６９ ５ ０．０１９ ３ ０．９３０ ２ ０．０１６ ３ ０．８９６ ５ ０．０２５ ２ ０．９００ ０ ０．９５５ ３ ０．８２７ ８ ０．９２３ ８ ０．９０４ ２ ０．９５１ ３ ０．８２９ ８ ０．９４１ ０ ５％ ０．９５１ ９ ０．０１５ ９ ０．９１２ ３ ０．００８ ６ ０．９４３ ０．０１６ ５ ０．９０３ ５ ０．０２０ ２ ０．９１５ ５ ０．９７１ ５ ０．８７８ ３ ０．９２６ ２ ０．９０５ ５ ０．９６０ ６ ０．８６５ ２ ０．９４３ ３ １０％ ０．９３６ ９ ０．００８ ４ ０．８７７ ５ ０．００４ ７ ０．９３１ ３ ０．０１１ ５ ０．９２０ ０ ０．０１９ ３ ０．９２８ ４ ０．９５０ ７ ０．８７１ ７ ０．８８８ ２ ０．８９０ ６ ０．９４４ ９ ０．８７７ ６ ０．９４３ ２ ２５％ ０．９２６ ０ ０ ０．８６４ ６ ０．０１３ ０ ０．９２２ ２ ０．０１４ ７ ０．９２９ ４ ０．０１９ ５ ０．９２５ ５ ０．９２６ ３ ０．８２５ ９ ０．８７１ ３ ０．８９５ ８ ０．９４０ ５ ０．８８６ ６ ０．９５０ ９ ３５％ ０．９１３ ７ ０．０２４ ８ ０．９０９ ７ ０ ０．９２７ ０ ０．０１５ ７ ０．９２１ ４ ０．０２０ ８ ０．８９５ ２ ０．９４７ ４ ０．９０８ ７ ０．９１０ ４ ０．８９９ ２ ０．９４３ １ ０．８６５ ２ ０．９４３ ８ ５０％ ０．９１１ ８ ０ ０．９０７ ９ ０ ０．９２１ ０．０１７ ４ ０．９１６ ９ ０．０２ ０．９１１ １ ０．９１２ ２ ０．９０７ ６ ０．９０８ ３ ０．８８３ ９ ０．９４３ ９ ０．８６９ ６ ０．９４２ ５ ＦＣＰＭ ０．８６０ ７ ０ ０．８６０ ４ ０．８６０ ８ 表 ６ ＩＦＣＭ（ｃ＋ｐ）、ＳＰＦＣＭ、ｒｓｅＦＣＭ 算法在 ＭＮＩＳＴ 数据集中的 ＮＭＩ 值 Ｔａｂｌｅ ６ ＮＭＩ ｏｆ ＩＦＣＭ（ｃ＋ｐ）， ＳＰＦＣＭ， ｒｓｅＦＣＭ ｆｏｒ ＭＮＩＳＴ ｄａｔａｓｅｔ 样本大小 ＩＦＣＭ（ｃ＋ｐ）（ α ＝ １６０） ａｖｇ． ｓｔｄ． ＩＦＣＭ（ｃ＋ｐ）（ α ＝ ０） ａｖｇ． ｓｔｄ． ＳＰＦＣＭ ａｖｇ． ｓｔｄ． ｒｓｅＦＣＭ ａｖｇ． ｓｔｄ． １％ ０．３１３ ９ ０ ０．２４４ ７ ０ ０．２２４ ６ ０．０７０ ９ — — ０．３１３ ９ ０．３１３ ９ ０．２４４ ７ ０．２４４ ７ ０．１３３ ７ ０．３３４ ５ — — ２．５０％ ０．２６０ ６ ０ ０．２３９ ０ ０ ０．２５８ ８ ０．０３１ ０ — — ０．２６０ ６ ０．２６０ ６ ０．２３９ ０ ０．２３９ ０ ０．１９１ ５ ０．３１７ ３ — — ５％ ０．２９７ ４ ０ ０．１６４ ６ ０ ０．２４２ ４ ０．０４２ ３ — — ０．２９７ ４ ０．２９７ ４ ０．１６４ ６ ０．１６４ ６ ０．１４１ ７ ０．２９８ ７ — — ·１９４· 智 能 系 统 学 报 第 １１ 卷
第2期 李滔，等：适合大规模数据集的增量式模糊聚类算法 ·195. 续表6 IFCM(c+p)(a =160) IFCM(c+p)(a=0) SPFCM rseFCM 样本大小 avg. std. avg. std. avg. std. avg. std 0.3217 0 0.2089 0 0.2299 0 10% 0.3217 0.3217 0.2089 0.2089 0.2296 0.2301 0.2634 0 0.2180 0 0.1818 0 25% 0.2634 0.2634 0.2180 0.2180 0.1807 0.1832 0.3309 0 0.1712 0 0.2027 0.0131 35% 0.3309 0.3309 0.1712 0.1712 0.1763 0.2328 0.2135 0 0.2072 0 0.1744 0.0188 50% 0.2135 0.2135 0.2072 0.2072 0.16320.2037 0.1723 0 FCPM(70%) 0.1723 0.1723 表7FCM(c+p)、SPFCM、rseFCM算法在forest数据集中的NMI值 Table 7 NMI of IFCM(c+p),SPFCM,rseFCM for forest dataset IFCM(c+p)(a =21) IFCM(c+p)(a =0) SPFCM rseFCM 样本大小 avg. std. avg. std. avg. std. avg. std. 0.1593 0.0016 0.1036 0 0.1161 0.0089 0.1% 0.1583 0.1631 0.1036 0.1036 0.1042 0.1370 0.1123 0 0.1016 0 0.1012 0.0049 0.5% 0.1123 0.1125 0.1016 0.1016 0.0943 0.1143 0.1264 0 0.1055 0 0.1102 0.0056 1% 0.1260 0.1273 0.1055 0.1055 0.1036 0.1225 0.1077 0 0.1064 0 0.1003 0.0030 2.50% 0.1077 0.1077 0.1064 0.1064 0.0963 0.1075 0.1092 0 0.1021 0.1025 0.0050 5% 0.1053 0.1094 0.1021 0.1021 0.0988 0.1113 0.1015 0 FCPM(10%) 0.1015 0.1015 表8 IFCM(c+p)、SPFCM、rseFCM算法在waveform数据集中的RI值 Table 8 RI of IFCM(c+p),SPFCM,rseFCM for waveform dataset FCM(c+p)(a=2.1) IFCM(c+p)(a=0) SPFCM rseFCM 样本大小 avg. std. avg. std. avg. std. avg. std. 0.7023 0.0095 0.6804 0.0018 0.6691 0.3301 0.6572 0.0018 0.1% 0.6841 0.7176 0.6767 0.6873 0.6637 0.6882 0.65656 0.6697 0.6890 0.0015 0.6638 0 0.6743 0 0.6633 0.0028 2.50% 0.6888 0.6996 0.6627 0.6639 0.6743 0.6748 0.6623 0.6824 0.7009 0.0024 0.6659 0 0.6625 0 0.6658 0 5% 0.6911 0.7017 0.6658 0.6674 0.6622 0.6626 0.66580.6659 0.6666 0 0.6651 0 0.6619 0 0.6531 0 10% 0.6664 0.6708 0.6632 0.6652 0.6619 0.6621 0.6529 0.6533
续表 ６ 样本大小 ＩＦＣＭ（ｃ＋ｐ）（ α ＝ １６０） ａｖｇ． ｓｔｄ． ＩＦＣＭ（ｃ＋ｐ）（ α ＝ ０） ａｖｇ． ｓｔｄ． ＳＰＦＣＭ ａｖｇ． ｓｔｄ． ｒｓｅＦＣＭ ａｖｇ． ｓｔｄ． １０％ ０．３２１ ７ ０ ０．２０８ ９ ０ ０．２２９ ９ ０ — — ０．３２１ ７ ０．３２１ ７ ０．２０８ ９ ０．２０８ ９ ０．２２９ ６ ０．２３０ １ — — ２５％ ０．２６３ ４ ０ ０．２１８ ０ ０ ０．１８１ ８ ０ — — ０．２６３ ４ ０．２６３ ４ ０．２１８ ０ ０．２１８ ０ ０．１８０ ７ ０．１８３ ２ — — ３５％ ０．３３０ ９ ０ ０．１７１ ２ ０ ０．２０２ ７ ０．０１３ １ — — ０．３３０ ９ ０．３３０ ９ ０．１７１ ２ ０．１７１ ２ ０．１７６ ３ ０．２３２ ８ — — ５０％ ０．２１３ ５ ０ ０．２０７ ２ ０ ０．１７４ ４ ０．０１８ ８ — — ０．２１３ ５ ０．２１３ ５ ０．２０７ ２ ０．２０７ ２ ０．１６３ ２ ０．２０３ ７ — — ＦＣＰＭ（７０％） ０．１７２ ３ ０ ０．１７２ ３ ０．１７２ ３ 表 ７ ＩＦＣＭ（ｃ＋ｐ）、ＳＰＦＣＭ、ｒｓｅＦＣＭ 算法在 ｆｏｒｅｓｔ 数据集中的 ＮＭＩ 值 Ｔａｂｌｅ ７ ＮＭＩ ｏｆ ＩＦＣＭ（ｃ＋ｐ）， ＳＰＦＣＭ， ｒｓｅＦＣＭ ｆｏｒ ｆｏｒｅｓｔ ｄａｔａｓｅｔ 样本大小 ＩＦＣＭ（ｃ＋ｐ）（ α ＝ ２１） ａｖｇ． ｓｔｄ． ＩＦＣＭ（ｃ＋ｐ）（ α ＝ ０） ａｖｇ． ｓｔｄ． ＳＰＦＣＭ ａｖｇ． ｓｔｄ． ｒｓｅＦＣＭ ａｖｇ． ｓｔｄ． ０．１％ ０．１５９ ３ ０．００１ ６ ０．１０３ ６ ０ ０．１１６ １ ０．００８ ９ — — ０．１５８ ３ ０．１６３ １ ０．１０３ ６ ０．１０３ ６ ０．１０４ ２ ０．１３７ ０ — — ０．５％ ０．１１２ ３ ０ ０．１０１ ６ ０ ０．１０１ ２ ０．００４ ９ — — ０．１１２ ３ ０．１１２ ５ ０．１０１ ６ ０．１０１ ６ ０．０９４ ３ ０．１１４ ３ — — １％ ０．１２６ ４ ０ ０．１０５ ５ ０ ０．１１０ ２ ０．００５ ６ — — ０．１２６ ０ ０．１２７ ３ ０．１０５ ５ ０．１０５ ５ ０．１０３ ６ ０．１２２ ５ — — ２．５０％ ０．１０７ ７ ０ ０．１０６ ４ ０ ０．１００ ３ ０．００３ ０ — — ０．１０７ ７ ０．１０７ ７ ０．１０６ ４ ０．１０６ ４ ０．０９６ ３ ０．１０７ ５ — — ５％ ０．１０９ ２ ０ ０．１０２ １ ０ ０．１０２ ５ ０．００５ ０ — — ０．１０５ ３ ０．１０９ ４ ０．１０２ １ ０．１０２ １ ０．０９８ ８ ０．１１１ ３ — — ＦＣＰＭ（１０％） ０．１０１ ５ ０ ０．１０１ ５ ０．１０１ ５ 表 ８ ＩＦＣＭ（ｃ＋ｐ）、ＳＰＦＣＭ、ｒｓｅＦＣＭ 算法在 ｗａｖｅｆｏｒｍ 数据集中的 ＲＩ 值 Ｔａｂｌｅ ８ ＲＩ ｏｆ ＩＦＣＭ（ｃ＋ｐ）， ＳＰＦＣＭ， ｒｓｅＦＣＭ ｆｏｒ ｗａｖｅｆｏｒｍ ｄａｔａｓｅｔ 样本大小 ＩＦＣＭ（ｃ＋ｐ）（ α ＝ ２．１） ａｖｇ． ｓｔｄ． ＩＦＣＭ（ｃ＋ｐ）（ α ＝ ０） ａｖｇ． ｓｔｄ． ＳＰＦＣＭ ａｖｇ． ｓｔｄ． ｒｓｅＦＣＭ ａｖｇ． ｓｔｄ． ０．１％ ０．７０２ ３ ０．００９ ５ ０．６８０ ４ ０．００１ ８ ０．６６９ １ ０．３３０ １ ０．６５７ ２ ０．００１ ８ ０．６８４ １ ０．７１７ ６ ０．６７６ ７ ０．６８７ ３ ０．６６３ ７ ０．６８８ ２ ０．６５６５ ６ ０．６６９ ７ ２．５０％ ０．６８９ ０ ０．００１ ５ ０．６６３ ８ ０ ０．６７４ ３ ０ ０．６６３ ３ ０．００２ ８ ０．６８８ ８ ０．６９９ ６ ０．６６２ ７ ０．６６３ ９ ０．６７４ ３ ０．６７４ ８ ０．６６２ ３ ０．６８２ ４ ５％ ０．７００ ９ ０．００２ ４ ０．６６５ ９ ０ ０．６６２ ５ ０ ０．６６５ ８ ０ ０．６９１ １ ０．７０１ ７ ０．６６５ ８ ０．６６７ ４ ０．６６２ ２ ０．６６２ ６ ０．６６５ ８ ０．６６５ ９ １０％ ０．６６６ ６ ０ ０．６６５ １ ０ ０．６６１ ９ ０ ０．６５３ １ ０ ０．６６６ ４ ０．６７０ ８ ０．６６３ ２ ０．６６５ ２ ０．６６１ ９ ０．６６２ １ ０．６５２ ９ ０．６５３ ３ 第 ２ 期 李滔，等： 适合大规模数据集的增量式模糊聚类算法 ·１９５·
196. 智能系统学报 第11卷 续表8 FCM(c+p)(a=2.1) IFCM(c+p)(a=0) SPFCM rseFCM 样本大小 avg std. avg. std. avg. std. avg. std. 0.6643 0.0018 0.6633 0 0.6613 0 0.6633 0 25% 0.6537 0.6693 0.6633 0.6634 0.6612 0.6615 0.6632 0.6634 0.6702 0 0.6640 0 0.6632 0 0.6623 0.0024 35% 0.6692 0.6703 0.6638 0.664 0.6632 0.6633 0.6619 0.6790 0.6699 0 0.6644 0 0.6651 0 0.6607 0 50% 0.6698 0.6701 0.6644 0.6644 0.6648 0.6652 0.6607 0.6608 0.6622 0.0027 FCPM 0.6492 0.6627 表9IFCM(c+p)、SPFCM、rseFCM算法在2D15数据集中的RI值 Table 9 RI of IFCM(c+p),SPFCM,rseFCM for 2D15 dataset IFCM(c+p)a =0.2) IFCM(c+p)(a=0) SPFCM rseFCM 样本大小 avg std. avg. std. avg. std. avg. std. 0.979 0.0097 0.9383 0.0127 0.9755 0.006 0.9697 0.0079 0.1% 0.9559 0.9976 0.9135 0.9665 0.9665 0.9837 0.9504 0.9856 0.9848 0.0024 0.9605 0.0064 0.9818 0.0054 0.9773 0.008 2.509% 0.9756 0.9879 0.9461 0.9761 0.9717 0.9881 0.9561 0.9912 0.9897 0.0050 0.9767 0.0030 0.9869 0.0049 0.9787 0.0064 5% 0.9792 0.9946 0.9648 0.9805 0.9773 0.9916 0.9647 0.9915 0.9871 0.0033 0.9701 0.0019 0.9864 0.0039 0.9836 0.0067 10% 0.9836 0.9914 0.9677 0.9720 0.9743 0.9903 0.9687 0.9917 0.9835 0 0.9651 0.0029 0.9849 0.0052 0.9861 0.0061 25% 0.9834 0.9835 0.9566 0.9678 0.9763 0.9901 0.9708 0.9929 0.9832 0.0066 0.9804 0 0.9860 0.0053 0.9844 0.0067 35% 0.9783 0.9932 0.9803 0.9805 0.9779 0.9910 0.9672 0.9917 0.9801 0 0.9812 0 0.9842 0.0056 0.9829 0.0066 50% 0.9799 0.9802 0.9812 0.9813 0.9711 0.9915 0.9652 0.9913 0.9683 0 FCPM 0.9683 0.9684 表I0IFCM(c+p)、SPFCM、rseFCM算法在MNIST数据集中的RI值 Table 10 RI of IFCM(c+p),SPFCM,rseFCM for MNSIT dataset IFCM(c+p)(a =160) IFCM(c+p)(a=0) SPFCM rseFCM 样本大小 avg std. avg. std. avg. std. avg. std. 0.7864 0 0.7222 0 0.7352 0.0961 0.1% 0.7864 0.7864 0.7222 0.7222 0.6063 0.8401 0.7935 0 0.7123 0 0.7924 0.0336 2.50% 0.7935 0.7935 0.7123 0.7123 0.6925 0.8300 0.7576 0 0.6129 0 0.7541 0.0503 5% 0.7576 0.7576 0.6129 0.6129 0.6448 0.8221
续表 ８ 样本大小 ＩＦＣＭ（ｃ＋ｐ）（ α ＝ ２．１） ａｖｇ． ｓｔｄ． ＩＦＣＭ（ｃ＋ｐ）（ α ＝ ０） ａｖｇ． ｓｔｄ． ＳＰＦＣＭ ａｖｇ． ｓｔｄ． ｒｓｅＦＣＭ ａｖｇ． ｓｔｄ． ２５％ ０．６６４ ３ ０．００１ ８ ０．６６３ ３ ０ ０．６６１ ３ ０ ０．６６３ ３ ０ ０．６５３ ７ ０．６６９ ３ ０．６６３ ３ ０．６６３ ４ ０．６６１ ２ ０．６６１ ５ ０．６６３ ２ ０．６６３ ４ ３５％ ０．６７０ ２ ０ ０．６６４ ０ ０ ０．６６３ ２ ０ ０．６６２ ３ ０．００２ ４ ０．６６９ ２ ０．６７０ ３ ０．６６３ ８ ０．６６４ ０．６６３ ２ ０．６６３ ３ ０．６６１ ９ ０．６７９ ０ ５０％ ０．６６９ ９ ０ ０．６６４ ４ ０ ０．６６５ １ ０ ０．６６０ ７ ０ ０．６６９ ８ ０．６７０ １ ０．６６４ ４ ０．６６４ ４ ０．６６４ ８ ０．６６５ ２ ０．６６０ ７ ０．６６０ ８ ＦＣＰＭ ０．６６２ ２ ０．００２ ７ ０．６４９ ２ ０．６６２ ７ 表 ９ ＩＦＣＭ（ｃ＋ｐ）、ＳＰＦＣＭ、ｒｓｅＦＣＭ 算法在 ２Ｄ１５ 数据集中的 ＲＩ 值 Ｔａｂｌｅ ９ ＲＩ ｏｆ ＩＦＣＭ（ｃ＋ｐ）， ＳＰＦＣＭ， ｒｓｅＦＣＭ ｆｏｒ ２Ｄ１５ ｄａｔａｓｅｔ 样本大小 ＩＦＣＭ（ｃ＋ｐ）（ α ＝ ０．２） ａｖｇ． ｓｔｄ． ＩＦＣＭ（ｃ＋ｐ）（ α ＝ ０） ａｖｇ． ｓｔｄ． ＳＰＦＣＭ ａｖｇ． ｓｔｄ． ｒｓｅＦＣＭ ａｖｇ． ｓｔｄ． ０．１％ ０．９７９ ０．００９ ７ ０．９３８ ３ ０．０１２ ７ ０．９７５ ５ ０．００６ ０．９６９ ７ ０．００７ ９ ０．９５５ ９ ０．９９７ ６ ０．９１３ ５ ０．９６６ ５ ０．９６６ ５ ０．９８３ ７ ０．９５０ ４ ０．９８５ ６ ２．５０％ ０．９８４ ８ ０．００２ ４ ０．９６０ ５ ０．００６ ４ ０．９８１ ８ ０．００５ ４ ０．９７７ ３ ０．００８ ０．９７５ ６ ０．９８７ ９ ０．９４６ １ ０．９７６ １ ０．９７１ ７ ０．９８８ １ ０．９５６ １ ０．９９１ ２ ５％ ０．９８９ ７ ０．００５ ０ ０．９７６ ７ ０．００３ ０ ０．９８６ ９ ０．００４ ９ ０．９７８ ７ ０．００６ ４ ０．９７９ ２ ０．９９４ ６ ０．９６４ ８ ０．９８０ ５ ０．９７７ ３ ０．９９１ ６ ０．９６４ ７ ０．９９１ ５ １０％ ０．９８７ １ ０．００３ ３ ０．９７０ １ ０．００１ ９ ０．９８６ ４ ０．００３ ９ ０．９８３ ６ ０．００６ ７ ０．９８３ ６ ０．９９１ ４ ０．９６７ ７ ０．９７２ ０ ０．９７４ ３ ０．９９０ ３ ０．９６８ ７ ０．９９１ ７ ２５％ ０．９８３ ５ ０ ０．９６５ １ ０．００２ ９ ０．９８４ ９ ０．００５ ２ ０．９８６ １ ０．００６ １ ０．９８３ ４ ０．９８３ ５ ０．９５６ ６ ０．９６７ ８ ０．９７６ ３ ０．９９０ １ ０．９７０ ８ ０．９９２ ９ ３５％ ０．９８３ ２ ０．００６ ６ ０．９８０ ４ ０ ０．９８６ ０ ０．００５ ３ ０．９８４ ４ ０．００６ ７ ０．９７８ ３ ０．９９３ ２ ０．９８０ ３ ０．９８０ ５ ０．９７７ ９ ０．９９１ ０ ０．９６７ ２ ０．９９１ ７ ５０％ ０．９８０ １ ０ ０．９８１ ２ ０ ０．９８４ ２ ０．００５ ６ ０．９８２ ９ ０．００６ ６ ０．９７９ ９ ０．９８０ ２ ０．９８１ ２ ０．９８１ ３ ０．９７１ １ ０．９９１ ５ ０．９６５ ２ ０．９９１ ３ ＦＣＰＭ ０．９６８ ３ ０ ０．９６８ ３ ０．９６８ ４ 表 １０ ＩＦＣＭ（ｃ＋ｐ）、ＳＰＦＣＭ、ｒｓｅＦＣＭ 算法在 ＭＮＩＳＴ 数据集中的 ＲＩ 值 Ｔａｂｌｅ １０ ＲＩ ｏｆ ＩＦＣＭ（ｃ＋ｐ）， ＳＰＦＣＭ， ｒｓｅＦＣＭ ｆｏｒ ＭＮＳＩＴ ｄａｔａｓｅｔ 样本大小 ＩＦＣＭ（ｃ＋ｐ）（ α ＝ １６０） ａｖｇ． ｓｔｄ． ＩＦＣＭ（ｃ＋ｐ）（ α ＝ ０） ａｖｇ． ｓｔｄ． ＳＰＦＣＭ ａｖｇ． ｓｔｄ． ｒｓｅＦＣＭ ａｖｇ． ｓｔｄ． ０．１％ ０．７８６ ４ ０ ０．７２２ ２ ０ ０．７３５ ２ ０．０９６ １ — — ０．７８６ ４ ０．７８６ ４ ０．７２２ ２ ０．７２２ ２ ０．６０６ ３ ０．８４０ １ — — ２．５０％ ０．７９３ ５ ０ ０．７１２ ３ ０ ０．７９２ ４ ０．０３３ ６ — — ０．７９３ ５ ０．７９３ ５ ０．７１２ ３ ０．７１２ ３ ０．６９２ ５ ０．８３０ ０ — — ５％ ０．７５７ ６ ０ ０．６１２ ９ ０ ０．７５４ １ ０．０５０ ３ — — ０．７５７ ６ ０．７５７ ６ ０．６１２ ９ ０．６１２ ９ ０．６４４ ８ ０．８２２ １ — — ·１９６· 智 能 系 统 学 报 第 １１ 卷
第2期 李滔，等：适合大规模数据集的增量式模糊聚类算法 197. 续表10 IFCM(c+p)(a =160) IFCM(c+p)(a =0) SPFCM rseFCM 样本大小 avg. std. avg. std. avg. std. avg. std. 0.8117 0 0.6429 0 0.7947 0 10% 0.8117 0.8117 0.6429 0.6429 0.79440.7953 0.7375 0 0.6608 0 0.7274 0 25% 0.7375 0.7375 0.6608 0.6608 0.7270 0.7289 0.7729 0 0.6076 0 0.7215 0.0099 35% 0.7729 0.7729 0.6076 0.6076 0.7032 0.7408 0.6633 0 0.6612 0 0.6420 0.0224 50% 0.6633 0.6633 0.6612 0.6612 0.60940.6916 0.6134 0 FCPM(70%) 0.6134 0.6134 表I1IFCM(c+p)、SPFCM、rseFCM算法在forest数据集中的RI值 Table 11 RI of IFCM(c+p),SPFCM,rseFCM for forest dataset IFCM(c+p)a=21) IFCM(c+p)(a =0) SPFCM rseFCM 样本大小 avg. std. avg. std. avg. std. avg. std. 0.5828 0 0.5697 0 0.5804 0.0122 0.1% 0.5827 0.583 0.5697 0.5697 0.5616 0.6007 0.5648 0 0.5608 0 0.5674 0 0.5% 0.5648 0.5648 0.5608 0.5608 0.5583 0.587 0.5737 0 0.5641 0 0.5728 0.0072 1% 0.5737 0.5737 0.5641 0.5641 0.5643 0.5887 0.5680 0 0.5640 0 0.5722 0.0093 2.50% 0.5680 0.5680 0.5640 0.5640 0.5615 0.5904 0.5696 0 0.5626 0 0.5688 0.0188 5% 0.569 0.5696 0.5626 0.5626 0.5615 0.5941 0.5628 0 FCPM(10%) 0.5628 0.5628 4 -IFCPM(a=0) 12 2)各算法在数据集上运行时间的加速比比较 -IFCPM(a=0.2) 各个算法相对于FCPM算法在不同数据集上不 出 8 同大小的数据块下运行时间的加速比的比较情况下 6 图1所示。 5101520253035404550 35 。-IFCPM(a=O) 30H 数据块大小 25 IFCPM(a=2.D (b)2D15 20叶 。SPFCM 。-IFCPM(a=0) 殿15 rseFCM 。-IFCPM(a=160 10 -SPFCM 5 型3 5 101520253035404550 数据块大小 (a)waveform 05101520253035404550 数据块大小 (c)MNIST
续表 １０ 样本大小 ＩＦＣＭ（ｃ＋ｐ）（ α ＝ １６０） ａｖｇ． ｓｔｄ． ＩＦＣＭ（ｃ＋ｐ）（ α ＝ ０） ａｖｇ． ｓｔｄ． ＳＰＦＣＭ ａｖｇ． ｓｔｄ． ｒｓｅＦＣＭ ａｖｇ． ｓｔｄ． １０％ ０．８１１ ７ ０ ０．６４２ ９ ０ ０．７９４ ７ ０ — — ０．８１１ ７ ０．８１１ ７ ０．６４２ ９ ０．６４２ ９ ０．７９４ ４ ０．７９５ ３ — — ２５％ ０．７３７ ５ ０ ０．６６０ ８ ０ ０．７２７ ４ ０ — — ０．７３７ ５ ０．７３７ ５ ０．６６０ ８ ０．６６０ ８ ０．７２７ ０ ０．７２８ ９ — — ３５％ ０．７７２ ９ ０ ０．６０７ ６ ０ ０．７２１ ５ ０．００９ ９ — — ０．７７２ ９ ０．７７２ ９ ０．６０７ ６ ０．６０７ ６ ０．７０３ ２ ０．７４０ ８ — — ５０％ ０．６６３ ３ ０ ０．６６１ ２ ０ ０．６４２ ０ ０．０２２ ４ — — ０．６６３ ３ ０．６６３ ３ ０．６６１ ２ ０．６６１ ２ ０．６０９ ４ ０．６９１ ６ — — ＦＣＰＭ（７０％） ０．６１３ ４ ０ ０．６１３ ４ ０．６１３ ４ 表 １１ ＩＦＣＭ（ｃ＋ｐ）、ＳＰＦＣＭ、ｒｓｅＦＣＭ 算法在 ｆｏｒｅｓｔ 数据集中的 ＲＩ 值 Ｔａｂｌｅ １１ ＲＩ ｏｆ ＩＦＣＭ（ｃ＋ｐ）， ＳＰＦＣＭ， ｒｓｅＦＣＭ ｆｏｒ ｆｏｒｅｓｔ ｄａｔａｓｅｔ 样本大小 ＩＦＣＭ（ｃ＋ｐ）（ α ＝ ２１） ａｖｇ． ｓｔｄ． ＩＦＣＭ（ｃ＋ｐ）（ α ＝ ０） ａｖｇ． ｓｔｄ． ＳＰＦＣＭ ａｖｇ． ｓｔｄ． ｒｓｅＦＣＭ ａｖｇ． ｓｔｄ． ０．１％ ０．５８２ ８ ０ ０．５６９ ７ ０ ０．５８０ ４ ０．０１２ ２ — — ０．５８２ ７ ０．５８３ ０．５６９ ７ ０．５６９ ７ ０．５６１ ６ ０．６００ ７ — — ０．５％ ０．５６４ ８ ０ ０．５６０ ８ ０ ０．５６７ ４ ０ — — ０．５６４ ８ ０．５６４ ８ ０．５６０ ８ ０．５６０ ８ ０．５５８ ３ ０．５８７ — — １％ ０．５７３ ７ ０ ０．５６４ １ ０ ０．５７２ ８ ０．００７ ２ — — ０．５７３ ７ ０．５７３ ７ ０．５６４ １ ０．５６４ １ ０．５６４ ３ ０．５８８ ７ — — ２．５０％ ０．５６８ ０ ０ ０．５６４ ０ ０ ０．５７２ ２ ０．００９ ３ — — ０．５６８ ０ ０．５６８ ０ ０．５６４ ０ ０．５６４ ０ ０．５６１ ５ ０．５９０ ４ — — ５％ ０．５６９ ６ ０ ０．５６２ ６ ０ ０．５６８ ８ ０．０１８ ８ — — ０．５６９ ０．５６９ ６ ０．５６２ ６ ０．５６２ ６ ０．５６１ ５ ０．５９４ １ — — ＦＣＰＭ（１０％） ０．５６２ ８ ０ ０．５６２ ８ ０．５６２ ８ ２）各算法在数据集上运行时间的加速比比较 各个算法相对于 ＦＣＰＭ 算法在不同数据集上不 同大小的数据块下运行时间的加速比的比较情况下 图 １ 所示。 第 ２ 期 李滔，等： 适合大规模数据集的增量式模糊聚类算法 ·１９７·