·604. 智能系统学报 第11卷 阵以及核矩阵决定，因为它们的时间复杂度均为 果，并与其他算法进行比较。第1组人工数据集 0(n2d),因此整体的时间复杂度也为0(n2d)。 Sym1分布在二维空间内，分为4部分，每部分由200 个数据点组成，共8O0个数据，点。使用数据集Syml 6 实验与分析 的目的是检验算法是否能够尽可能多的发现可供选 6.1聚类结果评估 择的聚类结果，且所有结果均满足与初始聚类结果 聚类结果根据聚类质量和相异性两方面进行评 正交的条件。第2组人工数据集Sym2的结构较为 估。聚类质量分为两种情况：如果已知正确的类标， 复杂，每部分的形状都是非凸的。使用数据集Sy2 则可选聚类结果和正确的类标之间通过F-measure 的目的是检验算法是否能够处理非线性的数据结 计算，计算公式为F=2P×R/(P+R),其中P和R分 构，并且发掘出嵌入在高维数据中的低维流形结构。 别表示准确率(precision)和召回率(recall);否则， 图1中的第1行表示的是RLPP使用数据集 使用Dunn Index计算，表示为Dl(g。数学上，Dunn Syml得到的运行结果。其中，第1列表示的是所提 min均{8(c,9)} 供的参考聚类结果C),第2列表示的是由RLPP ndex定义为Dlo-742,其中8：GxC一 得到的可供选择的聚类结果C2)。从图中可以直观 R。,表示类与类之间的距离，△：C→R。表示类内 地看出，RLPP成功地找到了与所提供的参考聚类 直径。对于评估聚类结果的相异性，使用了两种不 结果完全不相同，但是聚类质量很高的可选聚类结 同的方法。第1种是最为常用的标准化互信息 果。另外，如果我们把该结果C2)看作除C)外新 (normalized mutual information,NMl),第2种是杰 增的参考聚类结果，并且寻找第2个可选的参考聚 卡德指数(Jaccard index,.JI)。 类结果C),RLPP会得到第3列所显示的聚类结 对于NMI和JⅡ指标，值越小意味着不同聚类结 果。C3)在欧氏距离下与前两个聚类结果相比不是 果之间的相似度越高；对于F-measure和Dunn Index 特别得自然，但是C)仍然很有启发性，并且它完全 指标，值越大意味着更高的聚类质量。 独立于前2个参考聚类结果C)和C2)。同时注意 6.2人工数据集 到，RPCA算法无法寻找出合适的C)。在表1中， 使用两种流行的人工数据集评估LPP的效 提供了这些算法的表现。 14 2 10 2 6 1012 14 -4 2 0 246 101214-4-202 468101214 (a)Synl数据集可选聚类结果C (b)Syml数据集可选聚类结果C (c)Synl数据集可选聚类结果C ② 88 4-4-3 -2 4-4-3 -2-1 01234 (d)Syn2数据集可选聚类结果C (e)Syn2数据集可选聚类结果Ca (f)Syn2数据集可选聚类结果C 图1由数据集Synl(第1行)和Syn2(第2行)得到的可选聚类结果 Fig.1 Alternative clusterings uncovered from Synl(1"row)and Syn2(24 row)datasets阵以及核矩阵决定，因为它们的时间复杂度均为 Ｏ（ｎ ２ ｄ），因此整体的时间复杂度也为 Ｏ（ｎ ２ ｄ）。 ６ 实验与分析 ６．１ 聚类结果评估 聚类结果根据聚类质量和相异性两方面进行评 估。 聚类质量分为两种情况：如果已知正确的类标， 则可选聚类结果和正确的类标之间通过 Ｆ⁃ｍｅａｓｕｒｅ 计算，计算公式为 Ｆ ＝ ２Ｐ×Ｒ ／ （Ｐ＋Ｒ），其中 Ｐ 和 Ｒ 分 别表示准确率（ ｐｒｅｃｉｓｉｏｎ） 和召回率（ ｒｅｃａｌｌ）；否则， 使用 Ｄｕｎｎ Ｉｎｄｅｘ 计算，表示为 ＤＩ（Ｃ） 。 数学上，Ｄｕｎｎ Ｉｎｄｅｘ 定义为 ＤＩ（Ｃ） ＝ ｍｉｎｉ≠ｊ｛δ（ｃｉ，ｃｊ）｝ ｘ１≤ｌ≤ｋ｛Δ（ｃｌ）｝ ，其中 δ：Ｃ×Ｃ→ Ｒ ＋ ０ ，表示类与类之间的距离，Δ：Ｃ→Ｒ ＋ ０ 表示类内 直径。 对于评估聚类结果的相异性，使用了两种不 同的方法。 第 １ 种是最为常用的标准化互信息 （ｎｏｒｍａｌｉｚｅｄ ｍｕｔｕａｌ ｉｎｆｏｒｍａｔｉｏｎ， ＮＭＩ），第 ２ 种是杰 卡德指数（Ｊａｃｃａｒｄ ｉｎｄｅｘ， ＪＩ）。 对于 ＮＭＩ 和 ＪＩ 指标，值越小意味着不同聚类结 果之间的相似度越高；对于 Ｆ⁃ｍｅａｓｕｒｅ 和 Ｄｕｎｎ Ｉｎｄｅｘ 指标，值越大意味着更高的聚类质量。 ６．２ 人工数据集 使用两种流行的人工数据集评估 ＲＬＰＰ 的效 果，并与其他算法进行比较。 第 １ 组人工数据集 Ｓｙｎ１ 分布在二维空间内，分为 ４ 部分，每部分由 ２００ 个数据点组成，共 ８００ 个数据点。 使用数据集 Ｓｙｎ１ 的目的是检验算法是否能够尽可能多的发现可供选 择的聚类结果，且所有结果均满足与初始聚类结果 正交的条件。 第 ２ 组人工数据集 Ｓｙｎ２ 的结构较为 复杂，每部分的形状都是非凸的。 使用数据集 Ｓｙｎ２ 的目的是检验算法是否能够处理非线性的数据结 构，并且发掘出嵌入在高维数据中的低维流形结构。 图 １ 中的第 １ 行表示的是 ＲＬＰＰ 使用数据集 Ｓｙｎ１ 得到的运行结果。 其中，第 １ 列表示的是所提 供的参考聚类结果 Ｃ （１） ，第 ２ 列表示的是由 ＲＬＰＰ 得到的可供选择的聚类结果 Ｃ （２） 。 从图中可以直观 地看出，ＲＬＰＰ 成功地找到了与所提供的参考聚类 结果完全不相同，但是聚类质量很高的可选聚类结 果。 另外，如果我们把该结果 Ｃ （２） 看作除 Ｃ （１） 外新 增的参考聚类结果，并且寻找第 ２ 个可选的参考聚 类结果 Ｃ （３） ，ＲＬＰＰ 会得到第 ３ 列所显示的聚类结 果。 Ｃ （３）在欧氏距离下与前两个聚类结果相比不是 特别得自然，但是 Ｃ （３）仍然很有启发性，并且它完全 独立于前 ２ 个参考聚类结果 Ｃ （１）和 Ｃ （２） 。 同时注意 到，ＲＰＣＡ 算法无法寻找出合适的 Ｃ （３） 。 在表 １ 中， 提供了这些算法的表现。 图 １ 由数据集 Ｓｙｎ１（第 １ 行）和 Ｓｙｎ２（第 ２ 行）得到的可选聚类结果 Ｆｉｇ．１ Ａｌｔｅｒｎａｔｉｖｅ ｃｌｕｓｔｅｒｉｎｇｓ ｕｎｃｏｖｅｒｅｄ ｆｒｏｍ Ｓｙｎ１（１ ｓｔ ｒｏｗ） ａｎｄ Ｓｙｎ２（２ ｎｄ ｒｏｗ） ｄａｔａｓｅｔｓ ·６０４· 智 能 系 统 学 报 第 １１ 卷