第5期 储德润，等：公理化模糊共享近邻自适应谱聚类算法 ·901· 法(AFSSNNSC) 表1UCI实验数据集的特性 输入数据集X={x,,,x小，目标聚类数k Table 1 Characteristics of the UCI experimental datasets 输出聚类实际产生y类。 数据集 数据总量 维数 类数 1)首先为数据点的每个特征构造模糊关系 Heart 270 13 2 模糊项m Hepatitis 155 19 2 2)使用式(10)计算每个数据点的隶属度函数 Sonar 208 60 2 Wobc 699 9 2 umeM (x); Wdbc 569 30 2 3)通过式(11)找出模糊项的集合B; Iris 150 3 4)通过C.=Am构建每个样本的描述g: Wine 178 13 3 5)根据(.利用式(13)计算成对距离D: Protein 552 77 8 6)通过式(17计算σ：和σ： Libras 360 90 5 7)利用式(16)构建亲和矩阵A; LetterRec 20000 16 26 581012 54 > 8)根据Da=∑S计算对角矩阵D: Covtype 9)计算归一化拉普拉斯矩阵，拉普拉斯矩阵 基于聚类误差(CE)的实验结果如表2所示， L由L=D-S被归一化为 由表2可知所提的方法在大部分实验数据集上均 L=D-IPLD-IP =I-D-IPSD-IP 获得了优于对比算法的CE值；所提出的方法在 10)对L进行特征分解，得到前k个特征向 Heart、Hepatitis、Wdbc、Protein和Libras数据集上 量，并构建特征向量空间： 的CE分别为15.27%、27.14%、6.03%、51.12%、 11)利用经典的聚类算法如k-means对特征 52.31%,相比较AFS算法而言均改进了10%以 向量空间中的特征向量进行聚类。 上，在其他5个数据集上的CE相比较AFS也均 有所提高。证明了利用谱理论对相似矩阵进行划 3实验与结果分析 分比之前提出的传递闭包理论好得多，考虑到传 3.1实验环境及性能指标 递闭包方法的验证循环，所提出的方法也相对更 在UCI、USPS手写数字的相同数据集上，采 快、更容易实现。在Iris、Wine数据集中，所提算 用本文提出的方法和文献[10]的NJW谱聚类 法的CE分别为7.42%和2.89%，相对聚类错误率 (SC)、文献[21]的AFS聚类算法(AFS)、文献[22] 略高于ST$C算法。因为这两个数据集中只有 的self-tuning spectral clustering(STSC)算法、基于 150个样本和178个样本，但是差异实际上只有 K均值的近似谱聚类(KASP)2、基于Nystrom近 一两个样本，但相对于总体而言，所提算法CE普 似谱聚类(Nystrom)2和基于地标点谱聚类算法 遍低于其他算法在各数据集上的结果，仍具有较 LSC-R,LSC-K)2进行对比实验。本文算法实验 好的优越性；与基于距离度量的方法相比所提算 是在MATLAB2014b,计算机的硬件配置为Intel 法在给出的所有数据集中都显示出了优越性，在 Sonar数据集上更加改进5%以上，本文算法与基 i7-4770CPU3.40GHz、16 GB RAM的平台下进 于Nystrom近似谱聚类方法相比在所有数据集上 行。为了评估所提算法的聚类性能，本文使用聚 均有1%以上的优势。本文算法与基于地标点的 类误差(CE)2和归一化互信息(NM22种性能 谱聚类方法LSC-R和LSC-K相比也展现出较好 指标对本文算法与其他聚类方法的聚类结果进行 的聚类性能。这是因为通过模糊隶属函数代替距 了比较。其中CE被广泛用于评价聚类性能， 离度量数据之间的相似性，利用模糊语义结构解 CE越低聚类性能越好。NMI也是一种广泛使用 释数据之间的复杂的相互关系，增强了算法的鲁 的评估算法聚类性能的测量标准，NMI越大性能 棒性。对于Protein、Libras等多聚类数据集，AFS 越好。 的聚类错误率偏高，因为AFS聚类需要根据每个 3.2UCI数据集实验结果与分析 集群的边界选择最好的数据聚类分区。随着集群 为了验证所提出算法的有效性，本文将所提 规模数量的不断增加，将很难去清晰地找到边 的算法和其他方法应用于UCI数据库中的11个 界，这样聚类误差也会随之增高。总体而言，与对 基准数据集作为测试样本，表1为这11类数据集 比文献方法相比，所提算法的CE值在所有实验 的特征，分别是数据总量、维数以及类的个数。 数据集上均得到了改善，降低了算法的聚类错误率。法 (AFSSNNSC) 输入 数据集 X = {x1, x2,· · ·, xn} ，目标聚类数 k ； 输出 聚类实际产生 y 类。 fi mi, j 1) 首先为数据点的每个特征 构造模糊关系 模糊项 ； µm∈M (x) 2) 使用式 (10) 计算每个数据点的隶属度函数 ； B ε 3 x ) 通过式 (11) 找出模糊项的集合 ； ζx = ∧ m∈Bε x 4) 通过 m 构建每个样本的描述 ζx； 5) 根据 ζx 利用式 (13) 计算成对距离 Di j ； 6) 通过式 (17) 计算 σi 和 σj ； 7) 利用式 (16) 构建亲和矩阵 A ； Dii = ∑ 1⩽j⩽n 8) 根据 Si j 计算对角矩阵 D ； L L = D−S 9) 计算归一化拉普拉斯矩阵，拉普拉斯矩阵 由 被归一化为 L = D −1/2LD−1/2 = I− D −1/2SD−1/2 10) 对 L 进行特征分解，得到前 k 个特征向 量，并构建特征向量空间； 11) 利用经典的聚类算法如 k-means 对特征 向量空间中的特征向量进行聚类。 3 实验与结果分析 3.1 实验环境及性能指标 在 UCI、USPS 手写数字的相同数据集上，采 用本文提出的方法和文献 [10] 的 NJW 谱聚类 (SC)、文献 [21] 的 AFS 聚类算法 (AFS)、文献 [22] 的 self-tuning spectral clustering(STSC) 算法、基于 K 均值的近似谱聚类 (KASP)[23] 、基于 Nystrom 近 似谱聚类 (Nystrom)[24] 和基于地标点谱聚类算法 (LSC-R，LSC-K)[25] 进行对比实验。本文算法实验 是在 MATLAB 2014b，计算机的硬件配置为 Intel i7-4770 CPU 3.40 GHz、16 GB RAM 的平台下进 行。为了评估所提算法的聚类性能，本文使用聚 类误差 (CE)[26] 和归一化互信息 (NMI)[27] 2 种性能 指标对本文算法与其他聚类方法的聚类结果进行 了比较。其中 CE 被广泛用于评价聚类性能， CE 越低聚类性能越好。NMI 也是一种广泛使用 的评估算法聚类性能的测量标准，NMI 越大性能 越好。 3.2 UCI 数据集实验结果与分析 为了验证所提出算法的有效性，本文将所提 的算法和其他方法应用于 UCI 数据库中的 11 个 基准数据集作为测试样本，表 1 为这 11 类数据集 的特征，分别是数据总量、维数以及类的个数。 表 1 UCI 实验数据集的特性 Table 1 Characteristics of the UCI experimental datasets 数据集 数据总量 维数 类数 Heart 270 13 2 Hepatitis 155 19 2 Sonar 208 60 2 Wobc 699 9 2 Wdbc 569 30 2 Iris 150 4 3 Wine 178 13 3 Protein 552 77 8 Libras 360 90 15 LetterRec 20 000 16 26 Covtype 581 012 54 7 基于聚类误差 (CE) 的实验结果如表 2 所示， 由表 2 可知所提的方法在大部分实验数据集上均 获得了优于对比算法的 CE 值；所提出的方法在 Heart、Hepatitis、Wdbc、Protein 和 Libras 数据集上 的 CE 分别为 15.27%、27.14%、6.03%、51.12%、 52.31%，相比较 AFS 算法而言均改进了 10% 以 上，在其他 5 个数据集上的 CE 相比较 AFS 也均 有所提高。证明了利用谱理论对相似矩阵进行划 分比之前提出的传递闭包理论好得多，考虑到传 递闭包方法的验证循环，所提出的方法也相对更 快、更容易实现。在 Iris、Wine 数据集中，所提算 法的 CE 分别为 7.42% 和 2.89%，相对聚类错误率 略高于 STSC 算法。因为这两个数据集中只有 150 个样本和 178 个样本，但是差异实际上只有 一两个样本，但相对于总体而言，所提算法 CE 普 遍低于其他算法在各数据集上的结果，仍具有较 好的优越性；与基于距离度量的方法相比所提算 法在给出的所有数据集中都显示出了优越性，在 Sonar 数据集上更加改进 5% 以上，本文算法与基 于 Nystrom 近似谱聚类方法相比在所有数据集上 均有 1% 以上的优势。本文算法与基于地标点的 谱聚类方法 LSC-R 和 LSC-K 相比也展现出较好 的聚类性能。这是因为通过模糊隶属函数代替距 离度量数据之间的相似性，利用模糊语义结构解 释数据之间的复杂的相互关系，增强了算法的鲁 棒性。对于 Protein、Libras 等多聚类数据集，AFS 的聚类错误率偏高，因为 AFS 聚类需要根据每个 集群的边界选择最好的数据聚类分区。随着集群 规模数量的不断增加，将很难去清晰地找到边 界，这样聚类误差也会随之增高。总体而言，与对 比文献方法相比，所提算法的 CE 值在所有实验 数据集上均得到了改善，降低了算法的聚类错误率。 第 5 期 储德润，等：公理化模糊共享近邻自适应谱聚类算法 ·901·