第3期 谷飞洋，等：基于置换检验的聚类结果评估 ·303· 能更小。因此本文把p-value的定义为PpemoP 法。算法1描述了抽样的过程。 置换检验的准确性取决于抽样的数目，一般的 算法1 Shuffle(CI,n) 置换检验抽样的次数都在1000次以上。为了得到 fori←-0ton-ldo 更精确的p-value抽样的次数越多越好，理想的情 index +rand()mod (i+1) 况是置换所有的可能。然而对于不同的数据集合， swap(CI,Cline CI,CI) 甚至很难预测需要执行多少次置换才能够得到比较 可以用数学归纳法进行证明算法1保证了每个 好的结果。往往为了得到更精确的值就会增大抽样 元素获得同一簇标号的概率是一样的。抽样的复杂 次数，但是增加抽样次数的代价是增加计算的复杂 度为O(n)。这样进行抽样N次，就得到了N个样 性。对于普通的数据集往往抽样次数达到10000 本。然后利用样本对原始聚类结果进行评估。用 次之后就不太容易提高抽样次数。而这样做又产生 DB-Index算出原始聚类的函数值x。与样本的函数 出了一个问题。如果一个聚类结果真实的p-value 值x1,x2,…,xw。有了这些值就能计算p-value了。 为0.000001。而抽样的次数只有10000次的话，那 具体算法如下。 么p-value为就为0了。针对这些问题，本文提出 算法2ECP1 了一种新的聚类评估方法，ECP,该方法能比较好地 用DB-Index计算聚类结果的函数值xo。 解决上文提到的问题。 fori←-1 to N do 3 基于置换检验的聚类结果评估 Shuffle(CI,n) 用DB-Index计算样本的函数值x 3.1基本思想 计算p-value 本文提出的置换检验方法将关注点锁定在了聚 一般情况下kn,因此DB-ndex的复杂度为 类的结果上。评估聚类结果的本质是看聚类算法对 数据集中元素的划分质量。从这个角度出发，可以 O(n×d)。抽样一次的复杂度是O(n),容易算出总 体复杂度为O(N×n×d)。这个复杂度还是比较高 枚举对数据集的划分，然后用评估函数算出枚举划 的。所以需要想一些方法来降低复杂度。N是抽样 分的函数值。如果绝大部分划分都没有要评估的聚 次数，期望越大越好。可以看到DB-ndex是影响复 类结果质量好的话，那么就说明要评估的聚类结果 杂度的主要因素。如果降低DB-ndex计算的复杂 质量比较好。相反地，就说明要评估的聚类结果质 性，那么就可以在相同的时间内抽取更多的样本来 量并不好。 因此对于一个聚类结果，本文定义了零假0： 提高p-value的准确度。本文发现了DB-ndex公式 当前聚类结果不是一个高质量的聚类。然后计算这 的特点，对上文提到的算法做了改进。 个零假设的p-value。如果这个p-value非常小，就认 3.2加速技巧 为这个划分结果可以接受，可以拒绝0。否则认为 首先选取聚类结果作为初始状态。然后随机交 这个聚类结果不能接受。 换一对簇标号不同的元素的簇标号。交换后把此时 定义数据集X是一个包含n个元素的d维数 的划分作为一个样本，直接计算DB-ndex的函数 值型矩阵。首先对数据集聚类，聚成k簇后每个元 值。接下来继续交换一对簇标号不同的元素的簇标 素都会归属于一个簇。我们对每个簇进行标号。标 号，交换后计算DB-Index的值。这样迭代N次后就 号从0开始，往后依次是1,2，…，k-1。定义C1为 会得到N个样本的函数值。利用这N个值就可以 第i个元素所属的簇标号。比如C13=2表示第3个 计算出p-value。整个算法流程如下。 元素属于标号为2的簇。 算法3ECP2 接下来是抽样。抽样要满足一定约束。本文定 用DB-Index计算聚类结果的函数值xo 义的约束是：样本中簇包含元素的数目要与待评估 for i1 to N do 聚类结果中簇中元素的数目保持一致。举个例子， 随机交换一对簇标号不同元素的簇标号 假设数据集元素数目n为100。划分成3簇，划分 用DB-Index计算抽样结果的函数值x, 簇中的数目分别是40、33、27。那么抽样出来的样 计算p-value 本也要满足这些条件，也就是要划分成3簇，并且簇 对比ECP1,ECP2只是修改了第3步的抽样方 中元素的数目也必须是40、33、27。具体的抽样方 法。为什么修改了抽样方法就可以增大抽样次数？ 法：首先搜集所有元素的簇标号，然后将这些簇标 下面将仔细讨论DB-Index的计算过程。DB-ndex 号随机地分配给每个元素。其实这个过程是洗牌算 的计算公式为能更小。 因此本文把 ｐ ⁃ｖａｌｕｅ 的定义为 Ｐｐｅｒｍ０Ｐｅｃｄｆ０ 。 置换检验的准确性取决于抽样的数目，一般的 置换检验抽样的次数都在 １ ０００ 次以上。 为了得到 更精确的 ｐ ⁃ｖａｌｕｅ 抽样的次数越多越好，理想的情 况是置换所有的可能。 然而对于不同的数据集合， 甚至很难预测需要执行多少次置换才能够得到比较 好的结果。 往往为了得到更精确的值就会增大抽样 次数，但是增加抽样次数的代价是增加计算的复杂 性。 对于普通的数据集往往抽样次数达到 １０ ０００ 次之后就不太容易提高抽样次数。 而这样做又产生 出了一个问题。 如果一个聚类结果真实的 ｐ ⁃ｖａｌｕｅ 为 ０．０００ ００１。 而抽样的次数只有 １０ ０００ 次的话，那 么 ｐ ⁃ｖａｌｕｅ 为就为 ０ 了。 针对这些问题，本文提出 了一种新的聚类评估方法，ＥＣＰ，该方法能比较好地 解决上文提到的问题。 ３ 基于置换检验的聚类结果评估 ３．１ 基本思想 本文提出的置换检验方法将关注点锁定在了聚 类的结果上。 评估聚类结果的本质是看聚类算法对 数据集中元素的划分质量。 从这个角度出发，可以 枚举对数据集的划分，然后用评估函数算出枚举划 分的函数值。 如果绝大部分划分都没有要评估的聚 类结果质量好的话，那么就说明要评估的聚类结果 质量比较好。 相反地，就说明要评估的聚类结果质 量并不好。 因此对于一个聚类结果，本文定义了零假 Ｈ０： 当前聚类结果不是一个高质量的聚类。 然后计算这 个零假设的 ｐ⁃ｖａｌｕｅ。 如果这个 ｐ⁃ｖａｌｕｅ 非常小，就认 为这个划分结果可以接受，可以拒绝 Ｈ０。 否则认为 这个聚类结果不能接受。 定义数据集 Ｘ 是一个包含 ｎ 个元素的 ｄ 维数 值型矩阵。 首先对数据集聚类，聚成 ｋ 簇后每个元 素都会归属于一个簇。 我们对每个簇进行标号。 标 号从 ０ 开始，往后依次是 １，２， …，ｋ－１。 定义ＣＩｉ 为 第 ｉ 个元素所属的簇标号。 比如ＣＩ３ ＝ ２ 表示第 ３ 个 元素属于标号为 ２ 的簇。 接下来是抽样。 抽样要满足一定约束。 本文定 义的约束是： 样本中簇包含元素的数目要与待评估 聚类结果中簇中元素的数目保持一致。 举个例子， 假设数据集元素数目 ｎ 为 １００。 划分成 ３ 簇，划分 簇中的数目分别是 ４０、３３、２７。 那么抽样出来的样 本也要满足这些条件，也就是要划分成 ３ 簇，并且簇 中元素的数目也必须是 ４０、３３、２７。 具体的抽样方 法： 首先搜集所有元素的簇标号，然后将这些簇标 号随机地分配给每个元素。 其实这个过程是洗牌算 法。 算法 １ 描述了抽样的过程。 算法 １ Ｓｈｕｆｆｌｅ（ＣＩ， ｎ） ｆｏｒ ｉ← ０ ｔｏ ｎ－１ ｄｏ ｉｎｄｅｘ ← ｒａｎｄ（） ｍｏｄ （ｉ ＋ １） ｓｗａｐ（ ＣＩｉ，ＣＩｉｎｄｅｘＣＩｉ，ＣＩｉｎｄｅｘ ） 可以用数学归纳法进行证明算法 １ 保证了每个 元素获得同一簇标号的概率是一样的。 抽样的复杂 度为 Ｏ（ｎ）。 这样进行抽样 Ｎ 次，就得到了 Ｎ 个样 本。 然后利用样本对原始聚类结果进行评估。 用 ＤＢ⁃Ｉｎｄｅｘ 算出原始聚类的函数值 ｘ０ 与样本的函数 值 ｘ１ ，ｘ２ ，…，ｘＮ。 有了这些值就能计算 ｐ ⁃ｖａｌｕｅ 了。 具体算法如下。 算法 ２ ＥＣＰ１ 用 ＤＢ⁃Ｉｎｄｅｘ 计算聚类结果的函数值 ｘ０ 。 ｆｏｒ ｉ ← １ ｔｏ Ｎ ｄｏ Ｓｈｕｆｆｌｅ（ＣＩ， ｎ） 用 ＤＢ⁃Ｉｎｄｅｘ 计算样本的函数值 ｘｉ 计算 ｐ ⁃ｖａｌｕｅ 一般情况下 ｋ≪ｎ，因此 ＤＢ⁃Ｉｎｄｅｘ 的复杂度为 Ｏ（ｎ×ｄ）。抽样一次的复杂度是 Ｏ（ ｎ），容易算出总 体复杂度为 Ｏ（Ｎ×ｎ×ｄ）。 这个复杂度还是比较高 的。 所以需要想一些方法来降低复杂度。 Ｎ 是抽样 次数，期望越大越好。 可以看到 ＤＢ⁃Ｉｎｄｅｘ 是影响复 杂度的主要因素。 如果降低 ＤＢ⁃Ｉｎｄｅｘ 计算的复杂 性，那么就可以在相同的时间内抽取更多的样本来 提高 ｐ ⁃ｖａｌｕｅ 的准确度。 本文发现了 ＤＢ⁃Ｉｎｄｅｘ 公式 的特点，对上文提到的算法做了改进。 ３．２ 加速技巧 首先选取聚类结果作为初始状态。 然后随机交 换一对簇标号不同的元素的簇标号。 交换后把此时 的划分作为一个样本，直接计算 ＤＢ⁃Ｉｎｄｅｘ 的函数 值。 接下来继续交换一对簇标号不同的元素的簇标 号，交换后计算 ＤＢ⁃Ｉｎｄｅｘ 的值。 这样迭代 Ｎ 次后就 会得到 Ｎ 个样本的函数值。 利用这 Ｎ 个值就可以 计算出 ｐ ⁃ｖａｌｕｅ。 整个算法流程如下。 算法 ３ ＥＣＰ２ 用 ＤＢ⁃Ｉｎｄｅｘ 计算聚类结果的函数值 ｘ０ ｆｏｒ ｉ← １ ｔｏ Ｎ ｄｏ 随机交换一对簇标号不同元素的簇标号 用 ＤＢ⁃Ｉｎｄｅｘ 计算抽样结果的函数值 ｘｉ 计算 ｐ ⁃ｖａｌｕｅ 对比 ＥＣＰ１，ＥＣＰ２ 只是修改了第 ３ 步的抽样方 法。 为什么修改了抽样方法就可以增大抽样次数？ 下面将仔细讨论 ＤＢ⁃Ｉｎｄｅｘ 的计算过程。 ＤＢ⁃Ｉｎｄｅｘ 的计算公式为 第 ３ 期 谷飞洋，等：基于置换检验的聚类结果评估 ·３０３·