第5期 刘贝贝，等：基于密度的统计合并聚类算法 ·715· 由上述合并顺序的获取过程可以看出，k邻域 大小的选择直接影响了数据点密度的大小，进而影 1(11 2 响了DSMC算法的合并顺序。因此，k邻域的大小 根据定理1，取=gG十Gg血谷>0， 也被看作是DSMC算法的一个重要参数。 则 在该算法中，密度的大小不仅受到k邻域的影 P(I(C-C)-E(G-C)l≥ 响，也会受到距离度量(x,y)的影响。针对不同特 征的数据集，选取合适的f(x,y)可以得到更好的聚 171 类结果。在算法中较为常见的距离度量有欧式距 离，马氏距离，最大/最小值距离等。本文实验中主 2r2 < 要应用一种距离度量，它利用数据点最大特征差异 2 进行排序，使得d=max,eks(max(x:-y:),(i=A, 推论得证。 B,C,…),K(x)表示点x的k邻域。随机生成含 由推论1可知，当δ取值接近于零时（本文 有20个点的数据集，选取k邻域大小为4，利用上 若未特别标明，8取为1/(61X12),类别组合 述距离度量，得到DSMC算法的合并顺序如图2 (C,C2)满足不等式1(C-C3)-E(C,-C)1≤ 所示。 b(C1,C2)的概率接近于1，其中b(C1,C2)= 20TG,7G方：若(G,G)可以合并，说 1 明在数据集X·中2者属于同一类别，则有 E(C,-C,)=0。根据这2个前提条件得到如下统计 合并判定准则： ● M(C1,C2)= |ue,1(G-C)l≤b(C,c) false,其他 当类别组合(C,C,)满足|(C-C)|≤ (a)原图 b(C1,C2)时，则合并(C1,C2);反之则不然。 将该准则扩展到具有多个特征信息的数据集 中，形式如下： ftue,a∈{A,B,…f, M(C,C2上 I(G-Ca)|≤b(C,G) false,其他 1.3合并顺序 建立合适的合并准则后，聚类算法的结果受合 并顺序的影响。与随机选取数据点进行合并判定的 算法不同，DSMC算法利用了数据点的密度信息以 获得合并顺序。获取过程可叙述如下：首先，计算数 (b)k=4时的合并顺序 图2DSMC算法的合并顺序 据集中任意2点之间的距离度量（例如欧式距离、 Fig.2 Merging order of DSMC algorithm 最大/最小距离、马氏距离等)，获得度量矩阵：然 后，确定每一数据点的k邻域，选取k邻域中所有点 2DSMC算法的实现 与稠密点距离度量的最大值，作为稠密点的局部密 度信息：最后，根据获得的局部密度信息，将所有数 2.1DSMC算法的实现细节 据点按密度从大到小排序，得到算法的合并顺序。 通过对DSMC算法的详细介绍可知，DSMC算 在整个算法过程中，基于密度的合并顺序保证了在 法主要通过2个步骤实现：步骤1是根据数据点的 任意2个不同的类别进行合并判定时，其自身已经 密度信息获得合并顺序及每一数据点的k邻域：步 完成所有可能的合并。 骤2是按照合并顺序依次将稠密点与其k邻域中的ｇ ２ Ｑ １ Ｃ１ ＋ １ Ｃ２ æ è ç ö ø ÷ 根据定理 １，取 τ ＝ ｇ １ ２Ｑ １ Ｃ１ ＋ １ Ｃ２ æ è ç ö ø ÷ｌｎ ２ δ ＞０， 则 Ｐ Ｃ１ ( － Ｃ２ ( ( ) － Ｅ Ｃ１ ( － Ｃ２ ( ( ( ) ≥ ｇ １ ２Ｑ １ Ｃ１ ＋ １ Ｃ２ æ è ç ö ø ÷ ｌｎ ２ δ ö ø ÷ ≤ ｅｘｐ － ２τ ２ ∑ｋ ｒｋ ( ) ２ æ è çç ö ø ÷÷ ＝ δ ２ ＜ δ 推论得证。 由推论 １ 可知，当 δ 取值接近于零时（ 本文 若未 特 别 标 明， δ 取 为 １ ／ （ ６ ｜ Ｘ ｜ ２ ） ， 类 别 组 合 （ Ｃ１ ，Ｃ２ ） 满 足 不 等 式 ｜ Ｃ１ ( －Ｃ２ ( ( ) － Ｅ Ｃ１ ( －Ｃ２ ( ( ) ｜ ≤ ｂ（ Ｃ１ ，Ｃ２ ） 的 概 率 接 近 于 １， 其 中 ｂ Ｃ１ ，Ｃ２ ( ) ＝ ｇ １ ２Ｑ （ １ Ｃ１ ＋ １ Ｃ２ ）ｌｎ ２ δ ；若（Ｃ１ ，Ｃ２ ） 可以合并，说 明在 数 据 集 Ｘ ∗ 中 ２ 者 属 于 同 一 类 别， 则 有 Ｅ（Ｃ１ ( －Ｃ２ ( ）＝ ０。 根据这 ２ 个前提条件得到如下统计 合并判定准则： Ｍ Ｃ１ ，Ｃ２ ( ) ＝ ｔｒｕｅ， Ｃ１ ( － Ｃ１ ( ( ) ≤ ｂ Ｃ１ ，Ｃ２ ( ) ｆａｌｓｅ， 其他 { 当 类 别 组 合 （ Ｃ１ ， Ｃ２ ） 满 足 Ｃ１ ( －Ｃ２ ( ( ) ≤ ｂ（Ｃ１ ，Ｃ２ ）时，则合并（Ｃ１ ，Ｃ２ ）；反之则不然。 将该准则扩展到具有多个特征信息的数据集 中，形式如下： Ｍ Ｃ１，Ｃ２ ( )＝ ｔｒｕｅ， ∀ａ ∈｛Ａ，Ｂ，…｝， Ｃａ１ ( － Ｃａ２ ( ( ) ≤ｂ（Ｃ１，Ｃ２） ｆａｌｓｅ，其他 ì î í ï ï ï ï １．３ 合并顺序 建立合适的合并准则后，聚类算法的结果受合 并顺序的影响。 与随机选取数据点进行合并判定的 算法不同，ＤＳＭＣ 算法利用了数据点的密度信息以 获得合并顺序。 获取过程可叙述如下：首先，计算数 据集中任意 ２ 点之间的距离度量（例如欧式距离、 最大／ 最小距离、马氏距离等），获得度量矩阵；然 后，确定每一数据点的 ｋ 邻域，选取 ｋ 邻域中所有点 与稠密点距离度量的最大值，作为稠密点的局部密 度信息；最后，根据获得的局部密度信息，将所有数 据点按密度从大到小排序，得到算法的合并顺序。 在整个算法过程中，基于密度的合并顺序保证了在 任意 ２ 个不同的类别进行合并判定时，其自身已经 完成所有可能的合并。 由上述合并顺序的获取过程可以看出，ｋ 邻域 大小的选择直接影响了数据点密度的大小，进而影 响了 ＤＳＭＣ 算法的合并顺序。 因此，ｋ 邻域的大小 也被看作是 ＤＳＭＣ 算法的一个重要参数。 在该算法中，密度的大小不仅受到 ｋ 邻域的影 响，也会受到距离度量 ｆ（ ｘ，ｙ）的影响。 针对不同特 征的数据集，选取合适的 ｆ（ｘ，ｙ）可以得到更好的聚 类结果。 在算法中较为常见的距离度量有欧式距 离，马氏距离，最大／ 最小值距离等。 本文实验中主 要应用一种距离度量，它利用数据点最大特征差异 进行排序，使得 ｄ ＝ ｍａｘｙ∈Ｋ（ｘ） ｍａｘ ｘｉ －ｙｉ ( ( ) ) ，（ ｉ ＝ Ａ， Ｂ， Ｃ，…）， Ｋ（ ｘ）表示点 ｘ 的 ｋ 邻域。 随机生成含 有 ２０ 个点的数据集，选取 ｋ 邻域大小为 ４，利用上 述距离度量，得到 ＤＳＭＣ 算法的合并顺序如图 ２ 所示。 （ａ）原图 （ｂ）ｋ ＝ ４ 时的合并顺序 图 ２ ＤＳＭＣ 算法的合并顺序 Ｆｉｇ．２ Ｍｅｒｇｉｎｇ ｏｒｄｅｒ ｏｆ ＤＳＭＣ ａｌｇｏｒｉｔｈｍ ２ ＤＳＭＣ 算法的实现 ２．１ ＤＳＭＣ 算法的实现细节 通过对 ＤＳＭＣ 算法的详细介绍可知，ＤＳＭＣ 算 法主要通过 ２ 个步骤实现：步骤 １ 是根据数据点的 密度信息获得合并顺序及每一数据点的 ｋ 邻域；步 骤 ２ 是按照合并顺序依次将稠密点与其 ｋ 邻域中的 第 ５ 期 刘贝贝，等：基于密度的统计合并聚类算法 ·７１５·