第3期 黄栋，等：基于决策加权的聚类集成算法 ·421· 我们将进一步将聚类集成问题构造为一个二部图模 是Glass、Ecoli、Image Segmentation(IS)、MNIST 型。在所构造的二部图模型中，聚类集合中各个聚 ISOLET、Pen Digits(PD)、USPS以及Letter Recog- 类成员的簇与数据点同时作为节点。簇节点与簇节 nition(LR)。其中，除MNIST数据集来自于文献 点之间不存在连接边：数据点节点与数据点节点之 [18]之外，其他7个数据集均来自于UCI机器学习 间亦不存在连接边。两个节点之间存在连接边，当 数据仓库(UCI machine learning repository)【o。所 且仅当其中一个节点是数据点节点，另一个节点是 用的测试数据集的具体情况如表1所示。 簇节点，并且该数据点位于该簇之内。边的权值由 表1实验数据集 该簇所在的聚类成员的权值决定（见式(3）)。由 Table 1 Description of datasets 此，可得到一个二部图结构，其左部为数据点节点的 数据集 数据点数 维度 类别数 集合，右部为簇节点的集合。我们将该二部图结构 Glass 214 9 7 表示为 Ecoli 336 7 8 G=(U,V,E) 9 2310 19 7 式中：U=X表示左部节点集（数据点集合），V=C表 示右部节点集（簇集合），E表示边的集合。给定两 MNIST 5000 784 10 个节点u,和v,两者之间的边的权值定义为 ISOLET 7797 617 26 (w(T()), :∈X,y∈C,4:∈ PD 10992 16 10 e= 0. 否则 USPS 11000 256 10 式中：π(e)表示簇U所在的聚类成员，即如果巴∈ LR 20000 16 26 π，则T(u)=π。 3.2实验设置与评价指标 接下来，利用图G的二部图结构，我们采用 在本文实验中，我们首先需要生成一个包含若 Tcut算法[1将图G快速地分割为若千块，进而将每 干聚类成员的聚类集合，以对比分析本文方法以及 一块中数据点集合作为最终聚类的一个簇，由此可 其他聚类集成方法的聚类效果。具体地，我们在每 以得到最终聚类结果。 一次运行中使用k均值聚类算法生成M个聚类成 2.4时间复杂度 员，每一个聚类成员的生成均采用随机初始化，并在 第2.3节所构造的二部图G包含有N+N。个节 区间[2，√厅]中随机选取初始聚类个数k。对于 点，其中N是数据点个数，Nc是簇个数。如果使用 每一个方法在每一个数据集上的实验，我们均运行 经典的Ncut算法[9)对图G进行分割，其时间复杂 10次（每次使用随机生成的聚类集合，如前所述）， 度是O(k(N+N)32),其中k是图分割的块数。与 然后得到各个方法的平均性能得分，以实现客观公 之相比，本文采用的Tcut算法[9)可利用图G的二 平的对比与分析。 部图结构，进行快速图分割，其时间复杂度是 我们将聚类成员个数M称为聚类集成规模：将 O(kWN+kN2):考虑式(3)中权值计算的复杂度是 数据集的数据点数N称为数据规模。在后续实验 O(N),故本文总体算法的时间复杂度即是 中，我们首先固定聚类集成规模M=10,接下来分别 O(kW+kN)。由于在实际聚类问题中数据点个 进行本文方法与聚类成员以及与其他聚类集成方法 数N通常远大于簇个数N。,因此使用Tcut算法相当 的对比实验，并进一步测试在不同聚类集成规模M 于可使时间复杂度由O(kN2)降低至O(kN)。当 下各个聚类集成方法的聚类表现。最后，将对比测 面对大数据集时，本文算法在运算效率上的优势尤 试各个聚类集成方法的运算效率。在本文实验中， 其显著；在本文后续的对比实验中，本文聚类集成算 采用标准互信息量(normalized mutual information, 法相比于现有算法的效率优势也得到了验证。 NMI)山作为评价指标。NMI可根据两个聚类之间 3 实验结果与分析 的互信息量来度量其相似性，是聚类研究中被广泛 应用的一个评价指标。一个聚类结果（与真实聚类 在本节中，我们将在多个实际数据集中进行实 比较)的NMI值越大，则表示其聚类质量越好。 验，与若干现有聚类集成算法进行对比分析，以验证 3.3与聚类成员的对比实验 本文方法的有效性及运算效率。 聚类集成的目标是融合多个聚类成员的信息以 3.1数据集 期得到一个更优聚类。在本节中，我们将本文方法 本文的实验一共使用了8个实际数据集，分别 的聚类集成结果，与聚类成员进行对比实验。在每我们将进一步将聚类集成问题构造为一个二部图模 型。 在所构造的二部图模型中，聚类集合中各个聚 类成员的簇与数据点同时作为节点。 簇节点与簇节 点之间不存在连接边；数据点节点与数据点节点之 间亦不存在连接边。 两个节点之间存在连接边，当 且仅当其中一个节点是数据点节点，另一个节点是 簇节点，并且该数据点位于该簇之内。 边的权值由 该簇所在的聚类成员的权值决定（见式（３））。 由 此，可得到一个二部图结构，其左部为数据点节点的 集合，右部为簇节点的集合。 我们将该二部图结构 表示为 Ｇ ＝ （Ｕ，Ｖ，Ｅ） 式中：Ｕ＝Ｘ 表示左部节点集（数据点集合），Ｖ ＝ Ｃ 表 示右部节点集（簇集合），Ｅ 表示边的集合。 给定两 个节点ｕｉ和ｖｊ，两者之间的边的权值定义为 ｅｉｊ ＝ ｗ π ｖｊ ( ( ) ) ， ｕｉ ∈ Ｘ，ｖｊ ∈ Ｃ，ｕｉ ∈ ｖｊ {０， 否则 式中：π ｖｊ ( ) 表示簇ｖｊ 所在的聚类成员，即如果ｖｊ ∈ π ｍ ，则 π ｖｊ ( ) ＝π ｍ 。 接下来，利用图 Ｇ 的二部图结构， 我们采用 Ｔｃｕｔ 算法［１９］将图 Ｇ 快速地分割为若干块，进而将每 一块中数据点集合作为最终聚类的一个簇，由此可 以得到最终聚类结果。 ２．４ 时间复杂度 第 ２．３ 节所构造的二部图 Ｇ 包含有 Ｎ＋Ｎｃ 个节 点，其中 Ｎ 是数据点个数，Ｎｃ 是簇个数。 如果使用 经典的 Ｎｃｕｔ 算法［１９］ 对图 Ｇ 进行分割，其时间复杂 度是Ｏ ｋ Ｎ＋Ｎｃ ( ) ３／ ２ ( ) ，其中 ｋ 是图分割的块数。 与 之相比，本文采用的 Ｔｃｕｔ 算法［１９］ 可利用图 Ｇ 的二 部图 结 构， 进 行 快 速 图 分 割， 其 时 间 复 杂 度 是 Ｏ ｋＮ＋ｋ Ｎｃ ３／ ２ ( ) ；考虑式（３）中权值计算的复杂度是 Ｏ (Ｎ) ， 故 本 文 总 体 算 法 的 时 间 复 杂 度 即 是 Ｏ ｋＮ＋ｋ Ｎｃ ３／ ２ ( ) 。 由于在实际聚类问题中数据点个 数 Ｎ 通常远大于簇个数Ｎｃ，因此使用 Ｔｃｕｔ 算法相当 于可使时间复杂度由 Ｏ ｋ Ｎ ３／ ２ ( ) 降低至 Ｏ(ｋＮ) 。 当 面对大数据集时，本文算法在运算效率上的优势尤 其显著；在本文后续的对比实验中，本文聚类集成算 法相比于现有算法的效率优势也得到了验证。 ３ 实验结果与分析 在本节中，我们将在多个实际数据集中进行实 验，与若干现有聚类集成算法进行对比分析，以验证 本文方法的有效性及运算效率。 ３．１ 数据集 本文的实验一共使用了 ８ 个实际数据集，分别 是 Ｇｌａｓｓ、 Ｅｃｏｌｉ、 Ｉｍａｇｅ Ｓｅｇｍｅｎｔａｔｉｏｎ （ ＩＳ）、 ＭＮＩＳＴ、 ＩＳＯＬＥＴ、 Ｐｅｎ Ｄｉｇｉｔｓ（ＰＤ）、 ＵＳＰＳ 以及 Ｌｅｔｔｅｒ Ｒｅｃｏｇ⁃ ｎｉｔｉｏｎ（ ＬＲ）。 其中，除 ＭＮＩＳＴ 数据集来自于文献 ［１８］之外，其他 ７ 个数据集均来自于 ＵＣＩ 机器学习 数据仓库（ＵＣＩ ｍａｃｈｉｎｅ ｌｅａｒｎｉｎｇ ｒｅｐｏｓｉｔｏｒｙ） ［２０］ 。 所 用的测试数据集的具体情况如表 １ 所示。 表 １ 实验数据集 Ｔａｂｌｅ １ Ｄｅｓｃｒｉｐｔｉｏｎ ｏｆ ｄａｔａｓｅｔｓ 数据集 数据点数 维度 类别数 Ｇｌａｓｓ ２１４ ９ ７ Ｅｃｏｌｉ ３３６ ７ ８ ＩＳ ２ ３１０ １９ ７ ＭＮＩＳＴ ５ ０００ ７８４ １０ ＩＳＯＬＥＴ ７ ７９７ ６１７ ２６ ＰＤ １０ ９９２ １６ １０ ＵＳＰＳ １１ ０００ ２５６ １０ ＬＲ ２０ ０００ １６ ２６ ３．２ 实验设置与评价指标 在本文实验中，我们首先需要生成一个包含若 干聚类成员的聚类集合，以对比分析本文方法以及 其他聚类集成方法的聚类效果。 具体地，我们在每 一次运行中使用 ｋ 均值聚类算法生成 Ｍ 个聚类成 员，每一个聚类成员的生成均采用随机初始化，并在 区间 [２， Ｎ ] 中随机选取初始聚类个数 ｋ。 对于 每一个方法在每一个数据集上的实验，我们均运行 １０ 次（每次使用随机生成的聚类集合，如前所述）， 然后得到各个方法的平均性能得分，以实现客观公 平的对比与分析。 我们将聚类成员个数 Ｍ 称为聚类集成规模；将 数据集的数据点数 Ｎ 称为数据规模。 在后续实验 中，我们首先固定聚类集成规模 Ｍ ＝ １０，接下来分别 进行本文方法与聚类成员以及与其他聚类集成方法 的对比实验，并进一步测试在不同聚类集成规模 Ｍ 下各个聚类集成方法的聚类表现。 最后，将对比测 试各个聚类集成方法的运算效率。 在本文实验中， 采用标准互信息量（ ｎｏｒｍａｌｉｚｅｄ ｍｕｔｕａｌ ｉｎｆｏｒｍａｔｉｏｎ， ＮＭＩ） ［１］作为评价指标。 ＮＭＩ 可根据两个聚类之间 的互信息量来度量其相似性，是聚类研究中被广泛 应用的一个评价指标。 一个聚类结果（与真实聚类 比较）的 ＮＭＩ 值越大，则表示其聚类质量越好。 ３．３ 与聚类成员的对比实验 聚类集成的目标是融合多个聚类成员的信息以 期得到一个更优聚类。 在本节中，我们将本文方法 的聚类集成结果，与聚类成员进行对比实验。 在每 第 ３ 期 黄栋，等：基于决策加权的聚类集成算法 ·４２１·