第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
息加入到新增数据中，即每次都有 ｃ ＋ ｎ０ 个样本点加 入到新增数据中参与聚类，那么这些历史信息的加入 势必将影响新增数据的聚类效果。 如果历史信息恰 好位于新增数据附近，则其聚类效果将变好，如果历 史信息远离它们，历史信息的加入反而会导致一个很 差的聚类效果。 对于 ＳＰＦＣＭ 算法和 ＯＦＣＭ 算法而 言，它们通过添加样本权值以增加聚类效果，在一定 程度上比仅仅添加历史信息得到的聚类效果要好，但 也存在上面所提到的一些问题。 为了克服以上问题， 提到的 ＩＦＣＭ（ｃ＋ｐ）算法添加了平衡项，通过平衡项 中的平衡因子去改变数据块间聚类中心的相互影响 程度，此时即便历史信息远离新增数据，通过合理调 节平衡因子 α 的取值也可以使得聚类中心吸引它周 围的新增数据，从而提高聚类效果。 ２．３ 算法复杂度 文献［１５］ 详细介绍了 ｒｓｅＦＣＭ、ＳＰＦＣＭ 算法的 时间和空间复杂度，如表 １ 所示，本文提到的 ＦＣＰＭ 及 ＩＦＣＭ（ ｃ＋ｐ） 算法的时间和空间复杂度也如表 １ 所示。 其中 ｔ 表示非增量式算法的迭代次数， ｔ ＇ 表 示增量式算法中每个数据块的平均迭代次数， ｄ 表 示数据集维数， ｃ 表示未知类的聚类个数， ｐ 表示已 知类的聚类个数， ｓ 表示数据块的个数， ｎ０ 表示在 ＩＦＣＭ（ｃ＋ｐ）算法中距每个数据块的聚类中心最近的 样本点个数。 表 １ 各算法的时间、空间复杂度 Ｔａｂｌｅ １ Ｔｉｍｅ ａｎｄ ｓｐａｃｅ ｃｏｍｐｌｅｘｉｔｙ ｏｆ ａｌｇｏｒｉｔｈｍｓ 算法 时间复杂度 空间复杂度 ＦＣＰＭ Ｏ（ｔｎｄ（ｃ ＋ ｐ） ＋ ｔｃ） Ｏ（ｎ（ｄ ＋ ｃ ＋ ｐ）） ｒｓｅＦＣＭ Ｏ（ｔｃ ２ ｄｎ ／ ｓ） Ｏ（（ｄ ＋ ｃ）ｎ ／ ｓ） ＳＰＦＣＭ Ｏ（ｎｄｔ′ｃ ２ ） Ｏ（（ｄ ＋ ｃ）ｎ ／ ｓ） ＩＦＣＭ（ｃ＋ｐ） Ｏ（ｔ′ｎｄ（ｃ ＋ ｐ） ＋ ｔ′ｃ） Ｏ（（ｄ ＋ ｃ ＋ ｐ ＋ ｎ０ ）ｎ ／ ｓ） 如表 １ 所示，本文提到的算法均在相同环境下 运行，都对同一数据集 Ｘ 进行处理，时间复杂度都 为 Ｏ（ｎ） 。 然而从第 ３ 部分的实验可以看出，各算 法的运行时间存在着显著不同。 对于增量式模糊聚 类算法，由于它们在每个数据块的处理中能够快速 收敛因而可以使得算法总的运行时间减少。 本文提到的增量式模糊聚类算法都是对数据进 行分块处理，因此需要计算每个数据块所占用的空 间即为 ｎ ／ ｓ 。 如表 １ 所示，同 ｒｓｅＦＣＭ 和 ＳＰＦＣＭ 算 法相比，由于 ＩＦＣＭ（ｃ＋ｐ）算法需要存储聚类中心及 其周围的一些样本，因此需要占用相对较多的存储 空间，也就拥有相对高的空间复杂度。 ３ 相关实验研究 ３．１ 评价指标 为了公正地对各聚类算法的聚类效果做出合理 的评价，本文采用如下 ３ 种评价指标进行算法的性 能分析。 ３．１．１ 算法运行时间的加速比 ｓｐｅｅｄｕｐ 该指标反映了聚类算法在指定数据集下运行时 间的比较情况。 定义加速比： ｓｐｅｅｄｕｐ ＝ ｔ ｆｕｌｌ ／ ｔ ｉｎｃｒｅｍｅｎｔａｌ 式中： ｔ ｆｕｌｌ 表示在整个数据集下采用 ＦＣＰＭ 算法所运 行的时间； ｔ ｉｎｃｒｅｍｅｎｔａｌ 表示采用增量式算法比如 ＳＰＦ⁃ ＣＭ、ＩＦＣＭ（ｃ＋ｐ）等所运行的时间。 ２） 归一化互信息 （ ｎｏｒｍａｌｉｚｅｄ ｍｕｔｕａｌ ｉｎｆｏｒｍａ⁃ ｔｉｏｎ，ＮＭＩ） ［２０⁃２１］ ＮＭＩ ＝ ∑ ｃ ｉ ＝ １ ∑ ｃ ｊ ＝ １ Ｎ ｊ ｉ ｌｏｇ Ｎ·Ｎ ｊ ｉ Ｎｉ·Ｎｊ æ è ç ö ø ÷ ∑ ｃ ｉ ＝ １ Ｎｉ ｌｏｇ Ｎｉ Ｎ æ è ç ö ø ÷ · ∑ ｃ ｊ ＝ １ Ｎｊ ｌｏｇ Ｎｊ Ｎ æ è ç ö ø ÷ 式中： Ｎ 表示样本总数， Ｎｉ 表示经本文聚类算法之 后第 ｉ 簇的样本总数， Ｎｊ 表示真实数据集的第 ｊ 类 的样本总数， Ｎ ｊ ｉ 表示第 ｉ 簇与第 ｊ 类的契合程度，即 二者共有的样本总数。 ３）芮氏指标（ｒａｎｄ ｉｎｄｅｘ，ＲＩ） ［２０⁃２２］ ＲＩ ＝ ｆ ００ ＋ ｆ １１ Ｎ（Ｎ － １） ／ ２ 式中： ｆ ００ 表示样本点具有不同的类标签并且属于不 同类的配对样本数目， ｆ １１ 则表示样本点具有相同的 类标签并且属于同一类的配对样本数目， Ｎ 表示样 本总数。 以上 ＮＭＩ、ＲＩ 两种指标，其取值范围均为［ ０， １］，且取值越靠近 １ 越能反映该聚类算法在某数据 集下的聚类效果越好，反之越靠近 ０ 则反映该聚类 算法的聚类效果越差。 加速比 ｓｐｅｅｄｕｐ 越大反映了 增量式聚类算法的运行时间越短。 ３．２ 实验结果 １）实验环境 本文所有的实验均在如表 ２ 的环境中进行。 ２）实验数据集 实验所选取的数据集包括人工数据集 ２Ｄ１５ （ ｈｔｔｐ： ／ ／ ｗｗｗ． ｕｅｆ． ｆｉ ／ ｅｎ ／ ｓｉｐｕ ／ ｄａｔａｓｅｔｓ）、ＵＣＩ （ ｈｔｔｐ： ／ ／ ａｒｃｈｉｖｅ．ｉｃｓ． ｕｃｉ． ｅｄｕ ／ ｍｌ ／ ｄａｔａｓｅｔｓ． ｈｔｍｌ）、 标准数据集 ｗａｖｅｆｏｒｍ、ｆｏｒｅｓｔ 和手写数字数据集 ＭＮＩＳＴ（ ｈｔｔｐ： ／ ／ ｙａｎｎ．ｌｅｃｕｎ． ｃｏｍ ／ ｅｘｄｂ ／ ｍｎｉｓｔ ／ ）。 各数据集的分布情 况如表 ３。 ·１９２· 智 能 系 统 学 报 第 １１ 卷