第1期 冯柳伟，等：最近最远得分的聚类性能评价指标 ·71 O(n2+nll)×(K-Kn+1),且(K-K+1)n。 因此，ACNFS算法总的时间复杂度即 为0(tm2+(n2+nkl)×(Kx-Kia)）。 4 实验 为了验证本文所提NFS指标和ACNFS算法的 有效性，我们进行了仿真实验。在实验中我们将采 用6个人工数据集和4个UCI真实数据，对CH指 标、BWP指标，IGP指标和NFS指标确定类别数的 2 0 性能进行比较。实验证明，基于NS指标所提出的 (d)Dataset 4 ACNFS算法可以有效地确定数据集的类别数，实现 2.0 1.5 类别中心和类别数的自动估计。 1.0 在仿真实验中，我们所采用的人工数据集如图 0.5 3所示，而真实数据集则为UCI数据库中的IRIS 0 Balance Scale,Wine以及Soybean-small数据集。为 -0.5 了方便，我们将上述所有数据集的特征总结到表1 -1.0 -1.5 中，其中n表示数据集中样本点的个数，K表示数据 -2.0 集中样本点的类别数，d表示数据集中样本点的特 -2.5 征维数，最后一列表示各类别中样本点的个数。 -2.0-1.5-1.0-0.500.51.01.52.02.5 10 (e)Dataset 5 8 6 4 0 0 6 8 10 (a)Dataset 1 2.5r -2.0-1.5-1.0-0.500.51.01.52.02.5 2.0 。h (f)Dataset 6 图3人工数据集 +料 1.0 有 Fig.3 Artificial dataset 0.5 表1 实验中所使用的10组数据集特征 0 Table 1 The characters of the ten data sets used in -0.5 our experiments -10 数据集 n K d 每类中样本点的个数 -1.0 -0.5 0 0.5 1.0 1.5 2.0 Dataset 1 800 2 2 400.400 (b)Dataset 2 Dataset 2 800 3 2 400.200.200 Dataset 3 800 3 2 400.200.200 15 Dataset 4 1 100 4 200,400,200 Dataset 5 1 000 5 2 400.200.200.300 Dataset 6 900 6 200.200,200.200,200 Iris 150 3 4 150.150.150.150.150.150 Balance Scale 630 3 4 50,50,50 -10 1015 Wine 178 3 13 54.288.288 -10 -5 0 5 Sovbean-small 47 435 59,71,48 (c)Dataset 3Ｏ（（ｎ ２＋ｎｋｌ）×（Ｋｍａｘ －Ｋｍｉｎ ＋１）），且（Ｋｍａｘ －Ｋｍｉｎ ＋１）≪ｎ。 因 此， ＡＣＮＦＳ 算 法 总 的 时 间 复 杂 度 即 为Ｏ ｔｎ ２＋（ｎ ２＋ｎｋｌ）×（Ｋｍａｘ ( －Ｋｍｉｎ ） ) 。 ４ 实验 为了验证本文所提 ＮＦＳ 指标和 ＡＣＮＦＳ 算法的 有效性，我们进行了仿真实验。 在实验中我们将采 用 ６ 个人工数据集和 ４ 个 ＵＣＩ 真实数据，对 ＣＨ 指 标、ＢＷＰ 指标、ＩＧＰ 指标和 ＮＦＳ 指标确定类别数的 性能进行比较。 实验证明，基于 ＮＦＳ 指标所提出的 ＡＣＮＦＳ 算法可以有效地确定数据集的类别数，实现 类别中心和类别数的自动估计。 在仿真实验中，我们所采用的人工数据集如图 ３ 所示，而真实数据集则为 ＵＣＩ 数据库中的 ＩＲＩＳ， Ｂａｌａｎｃｅ Ｓｃａｌｅ，Ｗｉｎｅ 以及 Ｓｏｙｂｅａｎ⁃ｓｍａｌｌ 数据集。 为 了方便，我们将上述所有数据集的特征总结到表 １ 中，其中 ｎ 表示数据集中样本点的个数，Ｋ 表示数据 集中样本点的类别数，ｄ 表示数据集中样本点的特 征维数，最后一列表示各类别中样本点的个数。 （ａ）Ｄａｔａｓｅｔ １ （ｂ）Ｄａｔａｓｅｔ ２ （ｃ）Ｄａｔａｓｅｔ ３ （ｄ）Ｄａｔａｓｅｔ ４ （ｅ）Ｄａｔａｓｅｔ ５ （ｆ）Ｄａｔａｓｅｔ ６ 图 ３ 人工数据集 Ｆｉｇ．３ Ａｒｔｉｆｉｃｉａｌ ｄａｔａｓｅｔ 表 １ 实验中所使用的 １０ 组数据集特征 Ｔａｂｌｅ １ Ｔｈｅ ｃｈａｒａｃｔｅｒｓ ｏｆ ｔｈｅ ｔｅｎ ｄａｔａ ｓｅｔｓ ｕｓｅｄ ｉｎ ｏｕｒ ｅｘｐｅｒｉｍｅｎｔｓ 数据集 ｎ Ｋ ｄ 每类中样本点的个数 Ｄａｔａｓｅｔ １ ８００ ２ ２ ４００，４００ Ｄａｔａｓｅｔ ２ ８００ ３ ２ ４００，２００，２００ Ｄａｔａｓｅｔ ３ ８００ ３ ２ ４００，２００，２００ Ｄａｔａｓｅｔ ４ １ １００ ４ ２ ２００，４００，２００ Ｄａｔａｓｅｔ ５ １ ０００ ５ ２ ４００，２００，２００，３００ Ｄａｔａｓｅｔ ６ ９００ ６ ２ ２００，２００，２００，２００，２００ Ｉｒｉｓ １５０ ３ ４ １５０，１５０，１５０，１５０，１５０，１５０ Ｂａｌａｎｃｅ Ｓｃａｌｅ ６３０ ３ ４ ５０，５０，５０ Ｗｉｎｅ １７８ ３ １３ ５４，２８８，２８８ Ｓｏｙｂｅａｎ⁃ｓｍａｌｌ ４７ ４ ３５ ５９，７１，４８ 第 １ 期 冯柳伟，等：最近最远得分的聚类性能评价指标 ·７１·