第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个聚类中心及 聚类中心，这个最终的聚类中心就是我们所要求的 距其最近的。个样本点作为一次聚类结果的历史信下面采用拉格朗日极值法求模糊划分矩阵 Ｕ、 Ｔ 以及聚类中心 Ｖ 的更新公式。 Ｇ（Ｕ，Ｔ，Ｖ，λ） ＝ Ｊ（Ｕ，Ｔ，Ｖ，α） － λ（∑ ｃ ｉ ＝ １ μｉｋ ＋ ∑ ｐ ｊ ＝ １ ζｊｋ － １） ＝ Ｊ（Ｕ，Ｔ，Ｖ） ＋ α∑ ｃ ｉ ＝ １ ‖ ｖｉ － ｖ ｏ ｉ ‖２ － λ（∑ ｃ ｉ ＝ １ μｉｋ ＋ ∑ ｐ ｊ ＝ １ ζｊｋ － １） ＝ ∑ ｃ ｉ ＝ １ μ ｍ ｉｋ ‖ ｘｋ － ｖｉ‖２ ＋ ∑ ｐ ｊ ＝ １ ζ ｍ ｊｋ ‖ ｘｋ － ｚｊ‖２ ＋ α∑ ｃ ｉ ＝ １ ‖ ｖｉ － ｖ ｏ ｉ ‖２ － λ（∑ ｃ ｉ ＝ １ μｉｋ ＋ ∑ ｐ ｊ ＝ １ ζｊｋ － １） ∀ｋ ∈ ［１，Ｎ］ （８） 对 Ｇ（Ｕ，Ｔ，Ｖ，λ） 中的各个变量分别求偏导并 令其等于零得： ∂Ｊ（Ｕ，Ｔ，Ｖ，λ） ∂μｉｋ ＝ ｍ∑ ｃ ｉ ＝ １ μ ｍ－１ ｉｋ ‖ ｘｋ － ｖｉ‖２ － λ ＝ ０ ∂Ｊ（Ｕ，Ｔ，Ｖ，λ） ∂ζｉｋ ＝ ｍ∑ ｃ ｉ ＝ １ ζ ｍ－１ ｊｋ ‖ ｘｋ － ｚｊ‖２ － λ ＝ ０ ∂Ｊ（Ｕ，Ｔ，Ｖ，λ） ∂λ ＝ ∑ ｃ ｉ ＝ １ μｉｋ ＋ ∑ ｐ ｊ ＝ １ ζｊｋ － １ ＝ ０ ∂Ｊ（Ｕ，Ｔ，Ｖ，λ） ∂ｖｉ ＝ － ２∑ ｃ ｉ ＝ １ μ ｍ ｉｋ‖ ｘｋ － ｖｉ‖ ＋ ２α∑ ｃ ｉ ＝ １ ‖ ｖｉ － ｖ ｏ ｉ ‖ ＝ ０ ì î í ï ï ï ï ï ï ï ï ï ï ï ï ï ï ïï （９） 通过（９）可以很容易地求出模糊划分矩阵的更 新公式 μｉｋ 和 ζｊｋ ，如式（４）、（５）所示。 可以发现，模 糊划分矩阵 Ｕ 和 Ｔ 与平衡因子 α 无关。 由式（９）第 ４ 个等式可得 ｖｉ ＝ ∑ Ｎ ｋ ＝ １ μ ｍ ｉｋ ｘｋ ＋ α ｖ ｏ ｉ ∑ Ｎ ｋ ＝ １ μ ｍ ｉｋ ＋ α ，∀ｉ ∈ ［１，ｃ］ （１０） 从式（１０）可以看出，根据平衡因子 α 是否等于 ０，又可以分为两种情况。 当 α ＝ ０ 即不考虑数据块间聚类中心的相互影 响时，在每一个数据块的聚类过程中，将某个数据块 产生的聚类中心加入下一个数据块中参与聚类，为 了增大对数据块间聚类效果的影响程度，把距聚类 中心最近的 ｎ０ 个样本点也一同加入下一个数据块 参与聚类，以此类推，直至计算出最后一个数据块的 聚类中心，这个最终的聚类中心就是我们所要求的 整个数据集的聚类中心。 α ＝ ０ 时的情况仅仅考虑了某一数据块的聚类 中心及其周围的 ｎ０ 个样本点对下一个数据块的聚 类性能的影响，这样得出的聚类效果并不理想。 为 了提高聚类性能，应该考虑数据块间聚类中心的相 互影响即 α ≠ ０ 时的情况，此时平衡项的加入很好 地提高了聚类性能。 如下所述为 ＩＦＣＭ（ｃ＋ｐ）算法的具体计算步骤。 输入：Ｘ， ｃ，ｐ，ｍ，ｎ０ ，ε ； 输出：聚类中心 Ｖ。 １）把样本集 ｘ 随机划分成大小相等的 ｓ 个子集 即 ｘ ＝ ｛Ｘ１ ，Ｘ２ ，…，Ｘｓ｝ ； ２）定义一个空的集合 Ｘｉｎｃｒｅ 和 Ｘｎｅａｒ ； ３）遍历所有的数据块获取聚类中心： ｆｏｒ ｌ ＝ １，２，…，ｓ ①初始化未知类和已知类的聚类中心 Ｖ、Ｚ； ②把从上一数据块获得的样本 Ｘｉｎｃｒｅ 添加到当 前数据块，即 Ｘｌ ＝ ｛Ｘｌ ∪ Ｘｉｎｃｒｅ｝ ； ③使用式（ ４） 、（ ５） 和（ １０） 计算当前数据块 的聚类中心 Ｖｌ ； ④取出距当前数据块的聚类中心最近的 ｎ０ 个 样本点存入 Ｘｎｅａｒ 中； ⑤把聚类中心 Ｖｌ 及其附近的 ｎ０ 个样本点存入 Ｘｉｎｃｒｅ 中，即 Ｘｉｎｃｒｅ ＝ ｛Ｖｌ ∪ Ｘｎｅａｒ｝ ； ｅｎｄ ｆｏｒ 上述算法步骤 ２）的 Ｘｉｎｃｒｅ 用以存放每一个数据 块产生的聚类中心及其附近的 ｎ０ 个样本点 Ｘｎｅａｒ ， ３）对这 ｓ 个数据块进行遍历，求其聚类中心。 ３）中 的主要迭代过程在每个数据块中使用 ＦＣＰＭ 算法计 算聚类中心，使用欧氏距离求距聚类中心最近的 ｎ０ 个样本点，并把它们一同加入到下一个数据块中去 参与聚类。 注意在初始化聚类中心时，采用前面提 到的 ＦＣＰＭ 算法的初始化方法对已知类和未知类的 聚类中心 Ｚ、Ｖ 进行初始化，聚类中心 Ｖ 和模糊隶属 度矩阵 Ｕ 的更新公式分别为（１０）、（４）， ‖·‖ 表 示求欧氏距离。 ＦＣＰＭ 算法的迭代终止于聚类中心 的连续变化值的 Ｆｒｏｂｅｎｉｕｓ 范数小于 ε。 整个 ＩＦＣＭ （ｃ＋ｐ）算法终止于所有的数据块遍历结束并获得最 终的聚类中心。 ２．２ 算法的可行性分析 正如传统的增量式聚类算法一样，ＩＦＣＭ（ｃ＋ｐ）算 法对每个数据块进行聚类。 在 ＩＦＣＭ（ｃ＋ｐ）算法中， 没有添加平衡项时，将每个数据块的 ｃ 个聚类中心及 距其最近的 ｎ０ 个样本点作为一次聚类结果的历史信 第 ２ 期 李滔，等： 适合大规模数据集的增量式模糊聚类算法 ·１９１·