·714 智能系统学报 第10卷 别：当2个数据点对其特征至少有一个期望显著不 该统计模型对数据点及数据点特征的取样是相 同时，划分为不同类别。遍历所有的稠密点，实现对 互独立的。对于Q个独立随机变量的分布没有特 数据集的分类。 定要求，即独立不一定同分布。Q的传统取值一般 相比于上述基于密度的凝聚聚类算法（如DB- 为1，即数据点的每个特征只由一个随机变量表示， SCAN、NBC)DSMC算法在数据点生长合并的过程 但是这一取值对于较小的数据集难以获得可靠的估 中，不仅利用了数据点的密度信息，还利用了根据统 计信息。当Q增大时，数据点的特征可以被描述的 计判定准则得出的数据点每一个特征的差异性信 更加细致，因此，Q成为该算法的重要参数之一。调 息。因此，该算法对噪声具有更好的鲁棒性，也对不 整参数Q,不仅可以改变算法的统计复杂性，还可以 规则形状的数据集和密度不均匀的数据集具有更好 控制分类的精确度。将Q的取值从小调大，可以建 的聚类效果。 立一个层次由粗到细的数据聚类结果。 1 DSM 1.2统计合并判定 DSM算法对数据点的合并由一个特定的统计 1.1统计模型的建立 合并判定准则决定。为了简单起见，先只考虑含有 设给定的数据集为X,包含n个数据点，每个数 一个特征信息的数据集，即一个数据点用一组独立 据点含有多个特征信息，用2={A,B,C,…}表示特 随机变量表示。在此基础上，将得到的结果扩展到 征集合，每个特征的取值范围为[L,U:](i=A,B, 具有更多的特征信息的数据集中。 C,…)。为方便应用，对数据集X作整体移动（特征 为了得出统计合并判定准则，介绍定理如下： 信息整体改变不影响分类)，使得特征的取值范围 定理1（独立有限差分不等式[8]）设X= 变为[0，g](i=A,B,C,…),其中g:=IU,-Ll。 (X1,X2,…,X)是一组独立随机变量，X的取值范 然后，将数据点的每一个特征用Q个独立随机变量 围为A(k=1,2,…,n)。假设存在一个定义在 表示，每一个随机变量对应一个分布。以特征A为 Π4：的实值函数f,当变量X与X'仅在第k个条件 例，其可表示为A=（A1,A2,…,A),随机变量A (G=1,2,…,Q)对应第j个分布。由于Q个独立 不同时，满足fX)-f(X)1≤r4,则Hr≥0，有 随机变量和的取值应属于[0，g:](i=A,B,C,…), PfX)-u≥)≤exp(-2x2/∑.()) 则每一个随机变量的取值为[0，g,/Q](i=A,B,C, 式中：4为f代X)的期望，即μ=EfX)。 …)。这样，一个数据点的特征信息就由多组独立 根据定理1，可以推出给定数据集X中的不同 随机变量表示。 类别的绝对偏差不等式。记C为数据集X中的类 对于给定的数据集X,假设存在具有完美聚类 别（单个数据点可作为一个类别），1C1为类别内数 结果的数据集X·,那么在X·中，最优的聚类结果 据点的个数，C表示类别C与其他类别合并时的代 具有如下性质：1)同一类别中的数据点，对于任意 表点，E(C)表示该类别相关数据点Q个独立随机 给定的数据特征都具有相同的期望：2)不同的类别 变量期望和的期望。 中的数据点，对于任意给定的数据特征至少有一个 期望不同。这一性质在合并判定过程中起到非常重 推论1考虑数据集X中的类别组合(C1,C2), V0<δ≤1，下面不等式成立的概率不超过6： 要的作用。 I(C-C)-E(G-C)l≥ 数据点x的特征A G*a 11 2 当E(A,=∑E(A).xy 式中：g=max(g:)(i=A,B,C,…)。 =E(A).=∑E(A) 属于同一类别 证明已知类别C,中的数据点可由Q1C,I个 数据点的特征A 当E(4A)f∑E(A)xy 属于同一类别 独立随机变量表示，类别C2中的数据点可由Q1C2 个独立随机变量表示。(C-C)为实值函数，由于 =E(A)=∑E(A) C,C分别是C1,C,的代表点，若变动C中的变量， 「的最大取值为g/(Q1C,I),若变动C2中的变 图12个数据点任一特征聚类的统计说明 量，4的最大取值为g/(Q1C2I)。 Fig.I The statistical description of two data points 记rc,=g/(QC,),6,=g/(Q|C,l),则 clustering about any feature ∑()2=Q(IC,le,)2+IC2lr)2)=别；当 ２ 个数据点对其特征至少有一个期望显著不 同时，划分为不同类别。 遍历所有的稠密点，实现对 数据集的分类。 相比于上述基于密度的凝聚聚类算法（如 ＤＢ⁃ ＳＣＡＮ、ＮＢＣ）ＤＳＭＣ 算法在数据点生长合并的过程 中，不仅利用了数据点的密度信息，还利用了根据统 计判定准则得出的数据点每一个特征的差异性信 息。 因此，该算法对噪声具有更好的鲁棒性，也对不 规则形状的数据集和密度不均匀的数据集具有更好 的聚类效果。 １ ＤＳＭ １．１ 统计模型的建立 设给定的数据集为 Ｘ，包含 ｎ 个数据点，每个数 据点含有多个特征信息，用 Ω＝ ｛Ａ，Ｂ，Ｃ，…｝表示特 征集合，每个特征的取值范围为［ Ｌｉ，Ｕｉ ］ （ ｉ ＝ Ａ，Ｂ， Ｃ，…）。 为方便应用，对数据集 Ｘ 作整体移动（特征 信息整体改变不影响分类），使得特征的取值范围 变为［０， ｇｉ ］ （ ｉ ＝ Ａ，Ｂ，Ｃ，…），其中 ｇｉ ＝ ｜ Ｕｉ －Ｌｉ ｜ 。 然后，将数据点的每一个特征用 Ｑ 个独立随机变量 表示，每一个随机变量对应一个分布。 以特征 Ａ 为 例，其可表示为 Ａ ＝ （Ａ１ ， Ａ２ ，…， ＡＱ ），随机变量 Ａｊ （ｊ ＝ １， ２，…，Ｑ）对应第 ｊ 个分布。 由于 Ｑ 个独立 随机变量和的取值应属于［０， ｇｉ］（ｉ ＝ Ａ，Ｂ，Ｃ，…）， 则每一个随机变量的取值为［０， ｇｉ ／ Ｑ］ （ｉ ＝ Ａ，Ｂ，Ｃ， …）。 这样，一个数据点的特征信息就由多组独立 随机变量表示。 对于给定的数据集 Ｘ，假设存在具有完美聚类 结果的数据集 Ｘ ∗ ，那么在 Ｘ ∗ 中，最优的聚类结果 具有如下性质：１） 同一类别中的数据点，对于任意 给定的数据特征都具有相同的期望；２） 不同的类别 中的数据点，对于任意给定的数据特征至少有一个 期望不同。 这一性质在合并判定过程中起到非常重 要的作用。 图 １ ２ 个数据点任一特征聚类的统计说明 Ｆｉｇ． １ Ｔｈｅ ｓｔａｔｉｓｔｉｃａｌ ｄｅｓｃｒｉｐｔｉｏｎ ｏｆ ｔｗｏ ｄａｔａ ｐｏｉｎｔｓ ｃｌｕｓｔｅｒｉｎｇ ａｂｏｕｔ ａｎｙ ｆｅａｔｕｒｅ 该统计模型对数据点及数据点特征的取样是相 互独立的。 对于 Ｑ 个独立随机变量的分布没有特 定要求，即独立不一定同分布。 Ｑ 的传统取值一般 为 １，即数据点的每个特征只由一个随机变量表示， 但是这一取值对于较小的数据集难以获得可靠的估 计信息。 当 Ｑ 增大时，数据点的特征可以被描述的 更加细致，因此，Ｑ 成为该算法的重要参数之一。 调 整参数 Ｑ，不仅可以改变算法的统计复杂性，还可以 控制分类的精确度。 将 Ｑ 的取值从小调大，可以建 立一个层次由粗到细的数据聚类结果。 １．２ 统计合并判定 ＤＳＭ 算法对数据点的合并由一个特定的统计 合并判定准则决定。 为了简单起见，先只考虑含有 一个特征信息的数据集，即一个数据点用一组独立 随机变量表示。 在此基础上，将得到的结果扩展到 具有更多的特征信息的数据集中。 为了得出统计合并判定准则，介绍定理如下： 定理 １ （ 独立有限差分不等式［１ ８ ］ ） 设 Ｘ ＝ （Ｘ１ ， Ｘ２ ，…， Ｘｎ ）是一组独立随机变量，Ｘｋ的取值范 围为 Ａｋ（ ｋ ＝ １， ２，…， ｎ）。 假设存在一个定义在 ∏ｋＡｋ 的实值函数 ｆ，当变量 Ｘ 与 Ｘ′仅在第 ｋ 个条件 不同时，满足｜ ｆ(Ｘ) －ｆ（Ｘ′） ｜≤ｒｋ，则∀τ≥０，有 Ｐ(ｆ(Ｘ) － μ ≥ τ) ≤ ｅｘｐ － ２τ ２ ／ ∑ｋ ｒｋ ( ) ２ ( ) 式中：μ 为 ｆ（Ｘ）的期望，即 μ ＝Ｅｆ（Ｘ）。 根据定理 １，可以推出给定数据集 Ｘ 中的不同 类别的绝对偏差不等式。 记 Ｃ 为数据集 Ｘ 中的类 别（单个数据点可作为一个类别）， ｜ Ｃ ｜ 为类别内数 据点的个数，Ｃ ( 表示类别 Ｃ 与其他类别合并时的代 表点，Ｅ（Ｃ）表示该类别相关数据点 Ｑ 个独立随机 变量期望和的期望。 推论 １ 考虑数据集 Ｘ 中的类别组合（Ｃ１ ，Ｃ２ ）， ∀０＜δ≤１，下面不等式成立的概率不超过 δ： Ｃ１ ( － Ｃ２ ( ( ) － Ｅ Ｃ１ ( － Ｃ２ ( ( ) ≥ ｇ １ ２Ｑ １ Ｃ１ ＋ １ Ｃ２ æ è ç ö ø ÷ ｌｎ ２ δ 式中：ｇ ＝ｍａｘ ｇｉ ( ) （ｉ ＝ Ａ，Ｂ，Ｃ，…）。 证明 已知类别 Ｃ１ 中的数据点可由 Ｑ ｜ Ｃ１ ｜ 个 独立随机变量表示，类别 Ｃ２ 中的数据点可由 Ｑ｜ Ｃ２ ｜ 个独立随机变量表示。 Ｃ１ ( －Ｃ２ ( ( ) 为实值函数，由于 Ｃ１ ( ，Ｃ２ ( 分别是 Ｃ１ ，Ｃ２ 的代表点，若变动 Ｃ１ 中的变量， ｒｋ 的最大取值为 ｇ ／ （Ｑ ｜ Ｃ１ ｜ ），若变动 Ｃ２ 中的变 量，ｒｋ 的最大取值为 ｇ ／ （Ｑ｜ Ｃ２ ｜ ）。 记 ｒＣ１ ＝ ｇ ／ （Ｑ Ｃ１ ），ｒＣ２ ＝ ｇ ／ （Ｑ Ｃ２ ），则 ∑ｋ ｒｋ ( ) ２ ＝ Ｑ Ｃ１ ｒＣ１ ( ) ２ ＋ Ｃ２ ｒＣ２ ( ) ２ ( ) ＝ ·７１４· 智 能 系 统 学 报 第 １０ 卷