第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的更新公式。由于分类学习的一部分。 最为经典的模糊聚类算法之一 就是 Ｊ．Ｃ．Ｂｅｚｄｅｋ 教授在 ２０ 世纪 ８０ 年代提出的模糊 ｃ 均值聚类算法［１］ ，该算法被成功地应用到了在诸 多问题的解决上。 随着科学技术的发展，数据库中的数据更新速 度日益加快、数据容量不断增大，若仍然采用原来的 聚类算法对这样的大规模数据进行聚类将产生以下 几个问题：１）数据更新前得到的聚类结果可能与数 据更新后的聚类结果不匹配；２）对更新后的数据进 行重新聚类会导致较高的时间复杂度和计算资源的 浪费；３）还可能由于系统内存不足的原因而导致该 算法失效。 鉴于这些问题，Ｆａｚｌｉ Ｃａｎ 教授在 １９９０ 年 提出的增量式聚类算法［２］ 使得这些问题得以解决。 所谓增量式聚类是指利用前期数据已取得的聚类结 果，对新增数据进行分批或者逐批次地进行聚类的 过程。 研究增量式模糊聚类算法对于避免重复聚类 造成的计算资源浪费，提高聚类性能等都具有十分 重要的意义。 近几年，研究者们提出了很多关于增量式聚类 的算法。 这些算法大致可以被分为 ３ 类：１）对大数 据进行随机抽样获取小样本进行计算， 例如， Ｌ． Ｋａｕｆｍａｎ 等提出的 ＣＬＡＲＡ ［３］ ， Ｓ． Ｇｕｈａ 等［４］ 提出的 ＣＵＲＥ；２） 按序将小样本加载进内存的单程算法 （ｓｉｎｇｌｅ⁃ｐａｓｓ），具有代表性的有 Ｆ． Ｃａｎ 在文献［５］和 ［６］中提出的增量式算法；３）采取类图表结构的数 据转换算法，如 Ｔ． Ｚｈａｎｇ 等提出的 ＢＩＲＣＨ ［７］ 和 Ｒ． Ｎｇ 等［８］ 提出的 ＣＬＡＲＡＮＳ，对于增量式模糊聚类算 法；Ｂ． Ｕ． Ｓｈａｎｋａｒ 等［９］ 提出了快速模糊 ｃ 均值算法 ＦＦＣＭ，Ｔ． Ｃｈｅｎｇ ［１０］提出了多阶段的随机模糊 ｃ 均值 算法 ＭＲＦＣＭ，Ｊ． Ｆ． Ｋｏｌｅｎ 等［１１］ 提出了随机抽样模 糊 ｃ 均值算法 ｒｓＦＣＭ，Ｄｈａｎｅｓｈ Ｋｏｔｈａｒｉ 等［１２］ 提出了 将随机抽样的结果扩展到整个数据集上的扩展随机 抽样模糊 ｃ 均值算法 ｒｓｅＦＣＭ。 除此之外，还有基于 ＦＣＭ 的单程模糊 ｃ 均值算法 ＳＰＦＣＭ ［１３］ 、在线模糊 ｃ 均值算法 ＯＦＣＭ ［１４］ ，以及在这基础上发展的基于核 的模糊 ｃ 均值算法 ｓｐｋＦＣＭ 和 ｏｋＦＣＭ ［１５］ ，Ｙａｎｇｔａｏ Ｗａｎｇ 等［１６］提出的基于多重中心的增量式模糊聚类 算法在相关性大数据上的应用。 最近 Ｂöｈｍ 等［１７］ 受到动力学中同步现象的启发提出了一种新颖的同 步聚类算法 Ｓｙｎｃ，但是这种算法在大规模数据集上 的聚类受到了相当大的限制，基于此应文豪等［１８］ 在 此基础上提出了快速自适应同步聚类算法 ＦＡＫＣＳ。 传统的 ＦＣＭ 算法对初始聚类中心敏感且容易 陷入局部最优， 同时也忽略了类间的相互影响。 Ｊａｃｅｋ Ｍ． Ｌｅｓｋｉ 对 ＦＣＭ 算法进行了改进，提出了模 糊 ｃ＋ｐ 均值聚类算法 ＦＣＰＭ，并采用了新的方法初 始化聚类中心［１９］ 。 对于某一类的聚类中心，它能吸 引属于该类的样本并排斥属于其他类的样本，这样 更清楚地确定了样本的“归属” 问题。 对于小样本 数据，ＦＣＰＭ 算法可以保持不错的聚类性能，但其在 大规模数据集上的聚类性能明显降低而且有较大的 时间花费，甚至可能由于无法加载进内存而导致算 法失效。 对于以往的增量式模糊聚类算法，比如 ＳＰＦＣＭ 算法和 ＯＦＣＭ 算法都是通过对样本加权以 影响每个数据块产生的聚类中心，但数据块间聚类 中心的相互影响程度不明显甚至可能会由于上一次 聚类结果的加入而干扰新的数据进行聚类。 为了解 决以上问题，通过 ＦＣＰＭ 算法计算每个数据块的聚 类中心，把离聚类中心最近的一些样本点连同聚类 中心一起加入到下一个数据块中参与聚类，同时添 加平衡项以提高聚类性能，文中提出了适合大规模 数据集的增量式聚类算法 ＩＦＣＭ（ｃ＋ｐ）。 １ 相关算法 设 Ｎ 元样本集合 Ｘ ＝ ｛ ｘ１ ，ｘ２ ，…，ｘＮ｝ ， ｘｋ（ｋ ＝ １，２，…，Ｎ） 表示其中的某一个样本，其中每一个样 本都有 Ｄ ＝ ｛ｄ１ ，ｄ２ ，…，ｄｎ ｝ ⊂ Ｒ ｎ 一共 ｎ 个特征， ｄｊ （ｊ ＝１，２，…，ｎ） 表示其中的某一个特征。 ＦＣＭ 算法 将 Ｎ 个样本按照它所固有的特征划分成 ｃ 簇，用 μｉｋ 表示第 ｋ 个样本隶属于第 ｉ 簇的程度，那么划分成 ｃ 簇后得到的隶属度矩阵是 Ｕ ＝ ｛μｉｋ｝ ⊂ Ｒ ｃ×Ｎ ，ｉ ∈ ［１， ｃ］，ｋ ∈ ［１，Ｎ］ 。 对于模糊划分而言，所有的样本都 需要满足下面的条件： ＭｆｃＮ ＝ ｛Ｕ ∈ Ｒ ｃ×Ｎ ｜ μｉｋ ∈ ［０，１］， ∀ｉ ∈ ［１，ｃ］，ｋ ∈ ［１，Ｎ］｝； ∑ ｃ ｉ ＝ １ μｉｋ ＝ １， ∀ｋ ∈ ［１，Ｎ］；∑ Ｎ ｋ ＝ １ μｉｋ ∈ （０，Ｎ），∀ｉ ∈ ［１，ｃ］ ì î í ï ï ï ï ï ï ï ï 由此可见，模糊划分矩阵 Ｕ 的每一列的和都必 须等于 １，这样才能确保每一个样本都能够被完整 地划分到它所属的簇中。 通过使用欧式距离寻求最小均方误差，可以得 到 ＦＣＭ 模型的目标函数（其中 ｍ 为模糊指数）： Ｊ（Ｕ，Ｖ） ＝ ∑ ｃ ｉ ＝ １ ∑ Ｎ ｋ ＝ １ μ ｍ ｉｋ‖ ｘｋ － ｖｉ‖ ２ （１） 在式（１）的条件下通过拉格朗日乘子法可以得 出隶属度矩阵 Ｕ 和聚类中心 Ｖ 的更新公式。 由于 第 ２ 期 李滔，等： 适合大规模数据集的增量式模糊聚类算法 ·１８９·