·304. 智能系统学报 第11卷 如果知道了样本DB-Index函数值的概率分布 DBI= max( Di 就可以根据原始聚类结果的函数值算出精确的p 由S,的定义可以得出： value了。聚类是一种半监督的机器学习，其本 质对元素所属类别的划分。如果对元素随机划分无 S:= 13- 穷次。那么质量特别高的划分的比例会很小。同样 m 的，质量极端差的划分占的比例也会很小。很大比 式中m,是簇zi中元素的数目。z,是簇i中第j个元 重的划分都介于它们之间。而正态分布的特点是： 素的属性向量，z是簇i质心的属性向量。由于数据 极端概率很小，中间的概率很大。经过对数据的分 是d维的，所以3-乏‖2就是各个维度的平方和。 析，聚类划分的DB-Index函数值比较符合正态分 因此可以单独对每一维计算，然后再把所有维度的 布。因此可以假设抽样样本DB-ndex的函数值符 平方相加即可： 合正态分布。实际上正态分布符合很多自然概率分 ∑3-2=∑∑(4-a,)2, 布的指标。下面要做的就是得到正态分布的参数。 对于一维的正态分布均值和方差用式(1)和(2) 式中：aa是簇i中第j个元素的第t个属性值，a,是 得到： 簇i质心的第t个属性值。下面直接讨论第t维的 计算方法： i=1 u= (1) ∑3-2∑∑(a-a)2 N m m d= (2) ∑(4-a2 N-1 有了概率分布函数，就能将原始聚类结果x。代 入概率分布算出p-value了。 其中： 这样估出概率分布函数实现了在整体复杂度没 有增加的前提下用较少的抽样得到更为精确p-val m m: ue的目的了。 因此 立.>) ∑3-2 2 m=1 2 本文利用公式P perm 一计算p-val- mi =1 mi N ∑，4，是筷中所有元素中第！维的平方和， u实际上是利用了大数定律。大数定律的本质是 如果有无穷次试验，事件出现的频率就会无限趋近 a,是簇i中所有元素第t维的平均值。所以为了计 于事件发生的概率。而由于抽样次数有限，本文假 算S,每一维只需要维护两个值就可以了：平方和与 设了DB-Index的函数值符合正态分布。不过对于 平均值。当簇标号交换的话，能在O(1)复杂度内 抽样N次后发现，已经有足够的样本可以精确算出 修正这两个值。修改完每个维度的这两个值后，就 p-vaue的话，就不需要用正态分布计算了。然而如 可以用DB-Index算出函数值了。 果抽样N次后没有足够的样本可以用大数定律精 可以看出修改一个簇的平方和与平均值复杂度 确地计算p-value的话就要拟合正态概率分布函数 是O(d)的。因此DB-Index的计算复杂度就是 了。对于有多少个样本满足x:≤x。算是足够呢？ O(k×k×d)了。没有加速的DB-Index的计算复杂度 这是一个阈值问题。上边的过程总结起来如算 是O(n×d)。一般情况下，k≤n。所以这种方法的 法4。 效率有明显的提升。 算法4ECP 3.3更准确的p-vaue 抽样N次，算出每次的函数值x 上边提到计算DB-Index的方法的复杂度为 统计x:≤x。的数目M O(kx×d)。虽然相比于原先的计算方法已经优化 如果M≥Limit利用公式P,mo计算p-value 很多，但是对于p-value非常小的情况，可能依I旧由 否则，拟合正态概率分布算出p-value 于抽样数目有限而无法算出精确的p-value。这种 其中Limit是ECP的一个参数，是用Ppmo计算 情况下算出的p-value就会为O,然而这样的结果是 出p-value的最低数目限制。ECP不同于很多其他 不准确的。 的置换检验方法。这种方法实现了用较少的抽样计ＤＢＩ ＝ １ ｋ ∑ ｋ ｉ ＝ １ ｍａｘ（ Ｓｉ ＋ Ｓｊ Ｄｉｊ ）． 由 Ｓｉ 的定义可以得出： Ｓｉ ＝ ∑ ｍｉ ｊ ＝ １‖ｚｊ － ｚ‖２ ｍｉ ． 式中 ｍｉ 是簇 ｚｉ 中元素的数目。 ｚｊ 是簇 ｉ 中第 ｊ 个元 素的属性向量，ｚ 是簇 ｉ 质心的属性向量。 由于数据 是 ｄ 维的，所以‖ｚｊ －ｚ‖２ 就是各个维度的平方和。 因此可以单独对每一维计算，然后再把所有维度的 平方相加即可： ∑ ｍｉ ｊ ＝ １‖ｚｊ － ｚ‖２ ＝ ∑ ｄ ｔ ＝ １∑ ｍｉ ｊ ＝ １ （ａｊｔ － ａｔ） ２ ， 式中：ａｊｔ是簇 ｉ 中第 ｊ 个元素的第 ｔ 个属性值， ａｔ 是 簇 ｉ 质心的第 ｔ 个属性值。 下面直接讨论第 ｔ 维的 计算方法： ∑ ｍｉ ｊ ＝ １‖ｚｊ － ｚ‖２ ｍｉ ＝ ∑ ｄ ｔ ＝ １∑ ｍｉ ｊ ＝ １ （ａｊｔ － ａｔ） ２ ｍｉ ＝ ∑ ｄ ｔ ＝ １ ∑ ｍｉ ｊ ＝ １ （ａｊｔ － ａｔ） ２ ｍｉ 其中： ∑ ｍｉ ｊ ＝ １ （ａｊｔ － ａｔ） ２ ｍｉ ＝ ∑ ｍｉ ｊ ＝ １ ａｊｔ ２ ｍｉ － ａｔ ２ 因此 ∑ ｍｉ ｊ ＝ １‖ｚｊ － ｚ‖２ ｍｉ ＝ ∑ ｄ ｔ ＝ １ ∑ ｍｉ ｊ ＝ １ ａｊｔ ２ ｍｉ － ａｔ ２ ∑ ｍｉ ｊ ＝ １ ａｊｔ ２ 是簇 ｉ 中所有元素中第 ｔ 维的平方和， ａｔ 是簇 ｉ 中所有元素第 ｔ 维的平均值。 所以为了计 算 Ｓｉ，每一维只需要维护两个值就可以了：平方和与 平均值。 当簇标号交换的话，能在 Ｏ（１） 复杂度内 修正这两个值。 修改完每个维度的这两个值后，就 可以用 ＤＢ⁃Ｉｎｄｅｘ 算出函数值了。 可以看出修改一个簇的平方和与平均值复杂度 是 Ｏ（ ｄ） 的。 因此 ＤＢ⁃Ｉｎｄｅｘ 的计算复杂度就是 Ｏ（ｋ×ｋ×ｄ）了。 没有加速的 ＤＢ⁃Ｉｎｄｅｘ 的计算复杂度 是 Ｏ（ｎ×ｄ）。 一般情况下，ｋ≪ｎ。 所以这种方法的 效率有明显的提升。 ３．３ 更准确的 ｐ ⁃ｖａｌｕｅ 上边提到计算 ＤＢ⁃Ｉｎｄｅｘ 的方法的复杂度为 Ｏ（ｋ×ｋ×ｄ）。 虽然相比于原先的计算方法已经优化 很多，但是对于 ｐ ⁃ｖａｌｕｅ 非常小的情况，可能依旧由 于抽样数目有限而无法算出精确的 ｐ ⁃ｖａｌｕｅ。 这种 情况下算出的 ｐ ⁃ｖａｌｕｅ 就会为 ０，然而这样的结果是 不准确的。 如果知道了样本 ＤＢ⁃Ｉｎｄｅｘ 函数值的概率分布 就可以根据原始聚类结果的函数值算出精确的 ｐ ⁃ ｖａｌｕｅ 了［１４］ 。 聚类是一种半监督的机器学习，其本 质对元素所属类别的划分。 如果对元素随机划分无 穷次。 那么质量特别高的划分的比例会很小。 同样 的，质量极端差的划分占的比例也会很小。 很大比 重的划分都介于它们之间。 而正态分布的特点是： 极端概率很小，中间的概率很大。 经过对数据的分 析，聚类划分的 ＤＢ⁃Ｉｎｄｅｘ 函数值比较符合正态分 布。 因此可以假设抽样样本 ＤＢ⁃Ｉｎｄｅｘ 的函数值符 合正态分布。 实际上正态分布符合很多自然概率分 布的指标。 下面要做的就是得到正态分布的参数。 对于一维的正态分布均值和方差用式（１） 和（２） 得到： μ ＝ ∑ Ｎ ｉ ＝ １ ｘｉ Ｎ （１） ∂ ＝ （ｘｉ － ｘ） ２ Ｎ － １ （２） 有了概率分布函数，就能将原始聚类结果 ｘ０ 代 入概率分布算出 ｐ ⁃ｖａｌｕｅ 了。 这样估出概率分布函数实现了在整体复杂度没 有增加的前提下用较少的抽样得到更为精确 ｐ ⁃ｖａｌ⁃ ｕｅ 的目的了。 本文利用公式 Ｐｐｅｒｍ０ ∑ Ｎ ｎ ＝ １ Ｉ（ｙｎ ＞ ｘ０ ） Ｎ 计算 ｐ ⁃ｖａｌ⁃ ｕｅ 实际上是利用了大数定律。 大数定律的本质是 如果有无穷次试验，事件出现的频率就会无限趋近 于事件发生的概率。 而由于抽样次数有限，本文假 设了 ＤＢ⁃Ｉｎｄｅｘ 的函数值符合正态分布。 不过对于 抽样 Ｎ 次后发现，已经有足够的样本可以精确算出 ｐ ⁃ｖａｌｕｅ 的话，就不需要用正态分布计算了。 然而如 果抽样 Ｎ 次后没有足够的样本可以用大数定律精 确地计算 ｐ ⁃ｖａｌｕｅ 的话就要拟合正态概率分布函数 了。 对于有多少个样本满足 ｘｉ ≤ ｘ０ 算是足够呢？ 这是一个阈值问题。 上边的过程总结起来如算 法 ４。 算法 ４ ＥＣＰ 抽样 Ｎ 次，算出每次的函数值 ｘｉ 统计 ｘｉ≤ｘ０ 的数目 Ｍ 如果 Ｍ≥Ｌｉｍｉｔ 利用公式 Ｐｐｅｒｍ０计算 ｐ ⁃ｖａｌｕｅ 否则，拟合正态概率分布算出 ｐ ⁃ｖａｌｕｅ 其中 Ｌｉｍｉｔ 是 ＥＣＰ 的一个参数，是用 Ｐｐｅｒｍ０ 计算 出 ｐ ⁃ｖａｌｕｅ 的最低数目限制。 ＥＣＰ 不同于很多其他 的置换检验方法。 这种方法实现了用较少的抽样计 ·３０４· 智 能 系 统 学 报 第 １１ 卷