·420· 智能系统学报 第11卷 X作为输入信息[s):第2种建模方式则只以聚类集 论的直观理解在于，若一个聚类成员作出的连接决 合Ⅱ为输入信息，而不需要访问数据集X中的数据 策数量越小（即越稀有），则其正确率往往越高（即 特征o。两种建模方式的区别就在于除聚类成员 越宝贵)：若其连接决策数量越大，则其决策出错的 的信息之外是否可访问原始数据特征。在聚类集成 比例往往越高。当一个聚类成员将全体数据点都归 研究中，第2种建模方式对原始数据的依赖度更低， 入同一个簇时，其连接决策数达到最大值，此时该聚 亦被更广泛采用o]:本文的聚类集成研究按照第2 类成员的连接决策失去意义。 种建模方式进行，即以聚类集合Ⅱ为输入，不要求访 0.8 问原始数据特征，依此得到最终聚类结果π‘。 2.2决策加权 0.7 在聚类集成问题中，每一个聚类成员可以视作 是一个包含若干个连接决策的集合。如果数据点x: 0.6 和x在聚类成员πm中被划分在同一个簇，那么我 0.5 们称m对xi和x作出了一个连接决策，由此可得 一个簇C∈π"所作出的连接决策的数量为 0.4 (1-1C|)1Cg 米 #Decisions(Cπ)= 2 0.3 0 0.5 1.015 20*10 式中C表示簇C中数据点的个数。进而，可得聚 #Decisions 类成员π"所作出的连接决策的数量，即为π中所有 图1对于MNST数据集，各聚类成员的连接决策数与 簇的连接决策数之和： 正确决策率之间的关系 Fig.1 The relation between #Decisions and RatioCD #Decisions(πm)= ∑#Decisions(C) (1) for the MNIST dataset k= 每个聚类成员包含一定数量的连接决策：聚类 一个聚类成员的正确决策率，是其对于数据点两 成员的可靠度估计与加权问题，可视作是对聚类成 两之间处于同一个簇的判断的正确比例，可视作该聚 员连接决策的可靠度估计与加权问题。我们在实例 类成员的可靠度。由于聚类决策数与可靠度的负相 研究中发现，聚类成员的可靠度与其连接决策总数 关关系，为减小低可靠度决策的不良影响以提高聚类 存在显著的负相关关系。 集成鲁棒性，一个可行策略是采取权值与聚类决策数 具体地，我们以MNIST数据集[1)为例。该数 负相关的加权集成方案。在本文中，我们对每个聚类 据集包含5000个数据点。我们使用k均值聚类算 成员分配一个单位的可信度，该可信度由聚类成员内 法为该数据集生成100个聚类成员，每次生成均采 的全体决策共同分享。那么，聚类成员π"中每个连 用随机聚类个数及随机初始化。如果两个数据点x: 接决策分享到的可信度是l/#Decisions(πm)个单位。 和x:在聚类成员πm中被划分在同一个簇，并且这 根据各个聚类成员中连接决策的平均可信度对其加 两个数据点在MNIST数据集的真实类别中也属于 权，则聚类成员πm的权值计算公式为 同一个类，那么称聚类成员πm对数据点x:和x作 1 出了一个正确决策，并将π"作出的正确决策的数 花（πm)= #Decisions(m) 量记作#CorrectDecisions(πm)。我们将聚类成员m" 1 作出的所有连接决策中正确决策所占的比例，称为 #Decisions( 正确决策率，记作RatioCD(πm),计算公式为 进而可得： RatioCD(#CorrectDecisions() 1 (2) 10(πm)= #Decisions(π") 图1显示了MNIST数据集的1O0个聚类成员 Deciston(r)∑Decision( 的连接决策数与正确决策率之间的关系。对每一个 (3) 聚类成员，根据式(1)计算其连接决策数，根据式 由定义可知，全体聚类成员的权值之和为1，即 (2)计算其正确决策率，从而在图1中描出对应的 (r）=1 坐标点。由图1可以看到，聚类成员的连接决策数 m=1 与其正确决策率存在显著的负相关关系。此实验结 2.3二部图构造与聚类集成 在聚类成员可靠度分析与权值分配的基础上，Ｘ 作为输入信息［１５⁃１７］ ；第 ２ 种建模方式则只以聚类集 合 Π 为输入信息，而不需要访问数据集 Ｘ 中的数据 特征［１⁃１０］ 。 两种建模方式的区别就在于除聚类成员 的信息之外是否可访问原始数据特征。 在聚类集成 研究中，第 ２ 种建模方式对原始数据的依赖度更低， 亦被更广泛采用［１⁃１０］ ；本文的聚类集成研究按照第 ２ 种建模方式进行，即以聚类集合 Π 为输入，不要求访 问原始数据特征，依此得到最终聚类结果π ∗ 。 ２．２ 决策加权 在聚类集成问题中，每一个聚类成员可以视作 是一个包含若干个连接决策的集合。 如果数据点 ｘｉ 和 ｘｊ在聚类成员 π ｍ 中被划分在同一个簇，那么我 们称 πｍ 对 ｘｉ 和 ｘｊ 作出了一个连接决策，由此可得 一个簇 Ｃ ｍ ｋ ∈π ｍ 所作出的连接决策的数量为 ＃Ｄｅｃｉｓｉｏｎｓ（Ｃ ｍ ｋ ） ＝ （１ － Ｃ ｍ ｋ ） Ｃ ｍ ｋ ２ 式中 Ｃ ｍ ｋ 表示簇Ｃ ｍ ｋ 中数据点的个数。 进而，可得聚 类成员π ｍ所作出的连接决策的数量，即为π ｍ中所有 簇的连接决策数之和： ＃Ｄｅｃｉｓｉｏｎｓ（π ｍ ） ＝ ∑ ｎｍ ｋ ＝ １ ＃Ｄｅｃｉｓｉｏｎｓ（Ｃ ｍ ｋ ） （１） 每个聚类成员包含一定数量的连接决策；聚类 成员的可靠度估计与加权问题，可视作是对聚类成 员连接决策的可靠度估计与加权问题。 我们在实例 研究中发现，聚类成员的可靠度与其连接决策总数 存在显著的负相关关系。 具体地，我们以 ＭＮＩＳＴ 数据集［１８］ 为例。 该数 据集包含 ５ ０００ 个数据点。 我们使用 ｋ 均值聚类算 法为该数据集生成 １００ 个聚类成员，每次生成均采 用随机聚类个数及随机初始化。 如果两个数据点 ｘｉ 和 ｘｊ 在聚类成员 π ｍ 中被划分在同一个簇，并且这 两个数据点在 ＭＮＩＳＴ 数据集的真实类别中也属于 同一个类，那么称聚类成员 π ｍ 对数据点 ｘｉ 和 ｘｊ 作 出了一个正确决策，并将 π ｍ 作出的正确决策的数 量记作＃ＣｏｒｒｅｃｔＤｅｃｉｓｉｏｎｓ（π ｍ ）。 我们将聚类成员 π ｍ 作出的所有连接决策中正确决策所占的比例，称为 正确决策率，记作 ＲａｔｉｏＣＤ（π ｍ ），计算公式为 ＲａｔｉｏＣＤ π ｍ ( ) ＝ ＃ＣｏｒｒｅｃｔＤｅｃｉｓｉｏｎｓ（π ｍ ） ＃Ｄｅｃｉｓｉｏｎｓ（π ｍ ） （２） 图 １ 显示了 ＭＮＩＳＴ 数据集的 １００ 个聚类成员 的连接决策数与正确决策率之间的关系。 对每一个 聚类成员，根据式（１） 计算其连接决策数，根据式 （２）计算其正确决策率，从而在图 １ 中描出对应的 坐标点。 由图 １ 可以看到，聚类成员的连接决策数 与其正确决策率存在显著的负相关关系。 此实验结 论的直观理解在于，若一个聚类成员作出的连接决 策数量越小（即越稀有），则其正确率往往越高（即 越宝贵）；若其连接决策数量越大，则其决策出错的 比例往往越高。 当一个聚类成员将全体数据点都归 入同一个簇时，其连接决策数达到最大值，此时该聚 类成员的连接决策失去意义。 图 １ 对于 ＭＮＩＳＴ 数据集，各聚类成员的连接决策数与 正确决策率之间的关系 Ｆｉｇ．１ Ｔｈｅ ｒｅｌａｔｉｏｎ ｂｅｔｗｅｅｎ ＃ Ｄｅｃｉｓｉｏｎｓ ａｎｄ ＲａｔｉｏＣＤ ｆｏｒ ｔｈｅ ＭＮＩＳＴ ｄａｔａｓｅｔ 一个聚类成员的正确决策率，是其对于数据点两 两之间处于同一个簇的判断的正确比例，可视作该聚 类成员的可靠度。 由于聚类决策数与可靠度的负相 关关系，为减小低可靠度决策的不良影响以提高聚类 集成鲁棒性，一个可行策略是采取权值与聚类决策数 负相关的加权集成方案。 在本文中，我们对每个聚类 成员分配一个单位的可信度，该可信度由聚类成员内 的全体决策共同分享。 那么，聚类成员π ｍ中每个连 接决策分享到的可信度是 １／ ＃Ｄｅｃｉｓｉｏｎｓ（π ｍ ）个单位。 根据各个聚类成员中连接决策的平均可信度对其加 权，则聚类成员 π ｍ 的权值计算公式为 ｗ π ｍ ( ) ＝ １ ＃Ｄｅｃｉｓｉｏｎｓ（π ｍ ） ∑ Ｍ ｋ ＝ １ １ ＃Ｄｅｃｉｓｉｏｎｓ（π ｋ ） 进而可得： ｗ π ｍ ( ) ＝ １ ＃Ｄｅｃｉｓｉｏｎｓ（π ｍ ）∑ Ｍ ｋ ＝ １ １ ＃Ｄｅｃｉｓｉｏｎｓ（π ｋ ） （３） 由定义可知，全体聚类成员的权值之和为 １，即 ∑ Ｍ ｍ ＝ １ ｗ π ｍ ( ) ＝ １ ２．３ 二部图构造与聚类集成 在聚类成员可靠度分析与权值分配的基础上， ·４２０· 智 能 系 统 学 报 第 １１ 卷