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