·302· 智能系统学报 第11卷 这样重复大量的次数后，再用评估函数（如DB-In- 量不同簇的两个最近成员的距离。全连接：度量不 dex)计算每个样本的函数值。如果原始数据集聚类 同簇的两个最远成员的距离。质心比较：度量不同 结果的函数值小于大部分随机构造的数据集聚类结 簇的中心点的距离。 果的函数值，那么说明挖掘出来的信息是可靠的，否 链接度链接度指簇中的元素成员至少要跟同 则说明聚类结果不可靠。更通俗一点，如果原来数 一个簇内的元素比较像。这个可以用来评估簇模型 据集没有好的簇结构，那么无论怎么聚类，结果都是 不是圆形或者球形的聚类结果，比如DBSCAN的聚 不好的。代表性的方法有最大熵模型抽样[】、矩阵 类结果。 元素交换9]等。利用数据集簇结构来评估聚类质 本文用一种无监督评估聚类质量的方法，Da- 量[]的方法能很好地评估出簇结构不好的聚类结 vies-Bouldin Index,DB_Index. 果。实验证实对不同数据集进行聚类，有明显簇结 构数据集的p-value会比没有明显簇结构的p-value DBI =1 、+s) max(D, =1 小很多。但是这种方法并不能准确评估聚类的质 式中：S表示第i个簇内的元素与质心的标准方差， 量。从某种意义上讲，这种方法更适合评估一个数 D,表示第i个簇与第j个簇质心间的欧几里德距 据集是否有好的簇结构。 离，k表示簇的数目。 1.2 SigClust DBI的思想是一个高质量的聚类结果需要满 SigClust!)认为如果一个数据集符合高斯分 足：同一个簇的各元素间相似度大，不同类之间的相 布，那么对这个数据集的任何分割都是不合理的。 似度小。在DBI中，分子越小意味着簇内元素相似 因此这个方法的前提假设是：一个单一的簇的元素 度越大，分母越大意味着簇间相似度越小。 符合高斯分布。SigClust主要是针对k=2的聚类评 2.2聚类评估的p-value 估。对于>2的情况，还没有比较好的解决办法。 给一个数据集X,用DB-ndex计算聚类结果的 l.3层次聚类的p-value计算 函数值为xox。数据集X所有可能的聚类结果的函 这种方法主要针对层次聚类的评估2，)。层 数值为x1,x,xN。置换检验的p-value定义为 次聚类后会形成一个二叉树。对二叉树上的每个节 点都进行置换检验，算出每个节点划分对应的p ∑a1(xn≤xo） value。这种算法的空假设为：当前节点的左子树和 N 右子树应该属于一个簇。如果算出p-value足够小 式中I是一个逻辑函数。当x.≤xo的情况下为1， 就说明空假设是一个小概率事件，应该拒绝。该方 否则为0。由于要枚举出所有的聚类方案的复杂度 法是将当前节点的左子树和右子树打乱，按照一定 是指数级别的，所以需要采取其他的策略。抽样出 的约束随机分配左子树和右子树的元素。抽样若干 所有情况的一个子集Y,并计算子集Y中所有元素 次后形成的随机样本集按照某种指标与原始划分对 的函数值为x1,x2,xw,其中N≤N。这时候置 比计算出p-value.。这个评估只能针对层次聚类，不 换检验的p-value被定义为 能对其他的聚类算法进行评估。另外这样计算出的 ∑N1(xn≤o） p-value只是每个节点上的p-value,并不是全局聚 N 类的p-value. 一些研究为了避免p-value为0的情况，将p-value 2基本概念 的定义修改为 2.1无监督聚类质量评估函数 1+1x≤w) 如果数据集中的元素没有类标签，聚类结果的 Ppeml N+1 评价就只能依赖数据集自身的特征和量值。在这种 这种方法把分子加1的理由是把x。也看作置 情况下，聚类的度量追求有3个目标：紧密度、分离 换检验一个样本的函数值。这就避免了得到p-vl- 度和链接度。 ue为0的试验结果。然而这种做法事实上是不太 紧密度簇中的每个元素应该彼此尽可能接 合理的。试想如果抽样999次没有发现比x。更小 近。紧密度的常用度量是方差，方差越小说明紧密 的统计值，这样草率地得出结论当前置换检验的结 度越大。 果为0.001显然太武断了。因为可能抽样99999次 分离度簇与簇之间应该充分分离。有3种常 依旧没有比x。更优的样本。那么依照这个计算公 用方法来度量两个不同簇之间的距离。单连接：度 式p-value又为0.000O1。而实际上p-value的值可这样重复大量的次数后，再用评估函数（如 ＤＢ⁃Ｉｎ⁃ ｄｅｘ）计算每个样本的函数值。 如果原始数据集聚类 结果的函数值小于大部分随机构造的数据集聚类结 果的函数值，那么说明挖掘出来的信息是可靠的，否 则说明聚类结果不可靠。 更通俗一点，如果原来数 据集没有好的簇结构，那么无论怎么聚类，结果都是 不好的。 代表性的方法有最大熵模型抽样［８］ 、矩阵 元素交换［９ ］ 等。 利用数据集簇结构来评估聚类质 量［１０］的方法能很好地评估出簇结构不好的聚类结 果。 实验证实对不同数据集进行聚类，有明显簇结 构数据集的 ｐ⁃ｖａｌｕｅ 会比没有明显簇结构的 ｐ⁃ｖａｌｕｅ 小很多。 但是这种方法并不能准确评估聚类的质 量。 从某种意义上讲，这种方法更适合评估一个数 据集是否有好的簇结构。 １．２ ＳｉｇＣｌｕｓｔ ＳｉｇＣｌｕｓｔ ［１１］ 认为如果一个数据集符合高斯分 布，那么对这个数据集的任何分割都是不合理的。 因此这个方法的前提假设是：一个单一的簇的元素 符合高斯分布。 ＳｉｇＣｌｕｓｔ 主要是针对 ｋ ＝ ２ 的聚类评 估。 对于 ｋ＞２ 的情况，还没有比较好的解决办法。 １．３ 层次聚类的 ｐ ⁃ｖａｌｕｅ 计算 这种方法主要针对层次聚类的评估［１２，１３］ 。 层 次聚类后会形成一个二叉树。 对二叉树上的每个节 点都进行置换检验，算出每个节点划分对应的 ｐ ⁃ ｖａｌｕｅ。 这种算法的空假设为：当前节点的左子树和 右子树应该属于一个簇。 如果算出 ｐ ⁃ｖａｌｕｅ 足够小 就说明空假设是一个小概率事件，应该拒绝。 该方 法是将当前节点的左子树和右子树打乱，按照一定 的约束随机分配左子树和右子树的元素。 抽样若干 次后形成的随机样本集按照某种指标与原始划分对 比计算出 ｐ ⁃ｖａｌｕｅ。 这个评估只能针对层次聚类，不 能对其他的聚类算法进行评估。 另外这样计算出的 ｐ ⁃ｖａｌｕｅ 只是每个节点上的 ｐ ⁃ｖａｌｕｅ，并不是全局聚 类的 ｐ ⁃ｖａｌｕｅ。 ２ 基本概念 ２．１ 无监督聚类质量评估函数 如果数据集中的元素没有类标签，聚类结果的 评价就只能依赖数据集自身的特征和量值。 在这种 情况下，聚类的度量追求有 ３ 个目标：紧密度、分离 度和链接度。 紧密度 簇中的每个元素应该彼此尽可能接 近。 紧密度的常用度量是方差，方差越小说明紧密 度越大。 分离度 簇与簇之间应该充分分离。 有 ３ 种常 用方法来度量两个不同簇之间的距离。 单连接：度 量不同簇的两个最近成员的距离。 全连接：度量不 同簇的两个最远成员的距离。 质心比较：度量不同 簇的中心点的距离。 链接度 链接度指簇中的元素成员至少要跟同 一个簇内的元素比较像。 这个可以用来评估簇模型 不是圆形或者球形的聚类结果，比如 ＤＢＳＣＡＮ 的聚 类结果。 本文用一种无监督评估聚类质量的方法， Ｄａ⁃ ｖｉｅｓ⁃Ｂｏｕｌｄｉｎ Ｉｎｄｅｘ，即 ＤＢ＿Ｉｎｄｅｘ。 ＤＢＩ ＝ １ ｋ ∑ ｋ ｉ ＝ １ ｍａｘ（ Ｓｉ ＋ Ｓｊ Ｄｉｊ ）． 式中：Ｓｉ表示第 ｉ 个簇内的元素与质心的标准方差， Ｄｉｊ表示第 ｉ 个簇与第 ｊ 个簇质心间的欧几里德距 离，ｋ 表示簇的数目。 ＤＢＩ 的思想是一个高质量的聚类结果需要满 足：同一个簇的各元素间相似度大，不同类之间的相 似度小。 在 ＤＢＩ 中，分子越小意味着簇内元素相似 度越大，分母越大意味着簇间相似度越小。 ２．２ 聚类评估的 ｐ ⁃ｖａｌｕｅ 给一个数据集 Ｘ，用 ＤＢ⁃Ｉｎｄｅｘ 计算聚类结果的 函数值为 ｘ０ ｘ０ 。 数据集 Ｘ 所有可能的聚类结果的函 数值为 ｘ１ ，ｘ２ ，…ｘＮａｌｌ 。 置换检验的 ｐ ⁃ｖａｌｕｅ 定义为 Ｐｐｅｒｍ ＝ ∑ Ｎａｌｌ ｎ ＝ １ Ｉ（ｘｎ ≤ ｘ０ ） Ｎａｌｌ 式中 Ｉ 是一个逻辑函数。 当 ｘｎ≤ｘ０ 的情况下为 １， 否则为 ０。 由于要枚举出所有的聚类方案的复杂度 是指数级别的，所以需要采取其他的策略。 抽样出 所有情况的一个子集 Ｙ，并计算子集 Ｙ 中所有元素 的函数值为 ｘ１ ，ｘ２ ，…ｘＮ，其中 Ｎ≪ Ｎ ａｌｌ。 这时候置 换检验的 ｐ ⁃ｖａｌｕｅ 被定义为 Ｐｐｅｒｍ０ ＝ ∑ Ｎ ｎ ＝ １ Ｉ（ｘｎ ≤ ｘ０ ） Ｎ ． 一些研究为了避免 ｐ ⁃ｖａｌｕｅ 为 ０ 的情况，将 ｐ ⁃ｖａｌｕｅ 的定义修改为 Ｐｐｅｒｍ１ ＝ １ ＋ ∑ Ｎ ｎ ＝ １ １（ｘｎ ≤ ｘ０ ） Ｎ ＋ １ 这种方法把分子加 １ 的理由是把 ｘ０ 也看作置 换检验一个样本的函数值。 这就避免了得到 ｐ ⁃ｖａｌ⁃ ｕｅ 为 ０ 的试验结果。 然而这种做法事实上是不太 合理的。 试想如果抽样 ９９９ 次没有发现比 ｘ０ 更小 的统计值，这样草率地得出结论当前置换检验的结 果为 ０．００１ 显然太武断了。 因为可能抽样 ９９ ９９９ 次 依旧没有比 ｘ０ 更优的样本。 那么依照这个计算公 式 ｐ ⁃ｖａｌｕｅ 又为０．０００ ０１。 而实际上 ｐ ⁃ｖａｌｕｅ 的值可 ·３０２· 智 能 系 统 学 报 第 １１ 卷