第12卷第4期 智能系统学报 Vol.12 No.4 2017年8月 CAAI Transactions on Intelligent Systems Aug.2017 D0I:10.11992/is.201607019 网络出版地址：http://kns.cmki.net/kcms/detail/23.1538.tp.20170407.1734.004.html 基于混合距离学习的鲁棒的模糊C均值聚类算法 卞则康，王士同 (江南大学数字蝶体学院，江苏无锡214122) 摘要：距离度量对模糊聚类算法FCM的聚类结果有关键性的影响。实际应用中存在这样一种场景，聚类的数据集 中存在着一定量的带标签的成对约束集合的辅助信息。为了充分利用这些辅助信息，首先提出了一种基于混合距 离学习方法，它能利用这样的辅助信息来学习出数据集合的距离度量公式。然后，提出了一种基于混合距离学习的 鲁棒的模糊C均值聚类算法(HR-FCM算法).它是一种半监督的聚类算法。算法HR-FCM既保留了GFP-FCM (Generalized FCM algorithm wit汕h improved fuz四partitions)算法的鲁棒性等性能，也因为所采用更为合适的距离度量而 具有更好的聚类性能。实验结果证明了所提算法的有效性。 关键词：距离度量：FCM聚类算法：成对约束：辅助信息：混合距离：半监督：GIFP-FCM:鲁棒性 中图分类号：TP181文献标志码：A文章编号：1673-4785(2017)04-0450-09 中文引用格式：卞则康，王士同.基于混合距离学习的鲁棒的模糊C均值聚类算法[J].智能系统学报，2017,12(4)：450-458. 英文引用格式：BIAN Zekang,WANG Shitong..Robust FCM clustering algorithm based on hybrid-distance learning[J].CAAI transactions on intelligent systems,2017,12(4):450-458. Robust FCM clustering algorithm based on hybrid-distance learning BIAN Zekang,WANG Shitong (School of Digital Media,Jiangnan University,Wuxi 214122,China) Abstract:The distance metric plays a vital role in the fuzzy C-means clustering algorithm.In actual applications, there is a practical scenario in which the clustered data have a certain amount of side information,such as pairwise constraints with labels.To sufficiently utilize this side information,first,we propose a learning method based on hybrid distance,in which side information can be utilized to attain a distance metric formula for the data set.Next, we propose a robust fuzzy C-means clustering algorithm(HR-FCM algorithm)based on hybrid-distance learning, which is semi-supervised.The HR-FCM inherits the robustness of the GIFP-FCM(generalized FCM algorithm with improved fuzzy partitions)and has better clustering performance due to the more appropriate distance metric.The experimental results confirm the effectiveness of the proposed algorithm. Keywords:distance metric;FCM clustering algorithm;pairwise constraints;side information;hybrid distance; semi-supervised;GIFP-FCM;robustness 聚类分析作为一种重要的数据处理技术已经 离的方法通常是假设所有变量都是不相关的，并且 被广泛地应用到各种领域，如模式识别、数据挖掘 数据所有维度的方差都为1，所有变量的协方差为 等。在聚类分析中，需要根据数据点之间的相似或 0):2)欧式距离仅仅适用于特征空间中的超球结 相异程度，对数据点进行区分和分类。因此对于不 构，对于其他结构的数据集不太理想：3)欧式距离 同的数据集，选择合适的距离度量方式对算法的聚 对噪声比较敏感，聚类结果容易受到噪声的干 类性能有重要的影响)。欧式距离是较为常用的 扰[)。因此，欧式距离在实际应用中受到了限制。 距离度量方式，但其具有以下不足：1)采用欧式距 针对这些问题，近年来提出了多种距离学习的 方法，根据在距离学习过程中是否有先验的训练样 收稿日期：2016-07-23.网络出版日期：2017-04-07 本，距离学习可以分为有监督距离学习4和无监 基金项目：国家自然科学基金项目(61272210). 通信作者：卞则康.E-mail:bianzekang@163.com. 督距离学习7-)。在有监督距离学习的方法中，需
第 １２ 卷第 ４ 期 智 能 系 统 学 报 Ｖｏｌ．１２ №．４ ２０１７ 年 ８ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ａｕｇ． ２０１７ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ．２０１６０７０１９ 网络出版地址：ｈｔｔｐ： ／ ／ ｋｎｓ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ｔｐ．２０１７０４０７．１７３４．００４．ｈｔｍｌ 基于混合距离学习的鲁棒的模糊 Ｃ 均值聚类算法 卞则康，王士同 （江南大学 数字媒体学院，江苏 无锡 ２１４１２２） 摘 要：距离度量对模糊聚类算法 ＦＣＭ 的聚类结果有关键性的影响。 实际应用中存在这样一种场景，聚类的数据集 中存在着一定量的带标签的成对约束集合的辅助信息。 为了充分利用这些辅助信息，首先提出了一种基于混合距 离学习方法，它能利用这样的辅助信息来学习出数据集合的距离度量公式。 然后，提出了一种基于混合距离学习的 鲁棒的模糊 Ｃ 均值聚类算法（ＨＲ⁃ＦＣＭ 算法），它是一种半监督的聚类算法。 算法 ＨＲ⁃ＦＣＭ 既保留了 ＧＩＦＰ⁃ＦＣＭ （Ｇｅｎｅｒａｌｉｚｅｄ ＦＣＭ ａｌｇｏｒｉｔｈｍ ｗｉｔｈ ｉｍｐｒｏｖｅｄ ｆｕｚｚｙ ｐａｒｔｉｔｉｏｎｓ）算法的鲁棒性等性能，也因为所采用更为合适的距离度量而 具有更好的聚类性能。 实验结果证明了所提算法的有效性。 关键词：距离度量；ＦＣＭ 聚类算法；成对约束；辅助信息；混合距离；半监督；ＧＩＦＰ⁃ＦＣＭ；鲁棒性 中图分类号：ＴＰ１８１ 文献标志码：Ａ 文章编号：１６７３－４７８５（２０１７）０４－０４５０－０９ 中文引用格式：卞则康，王士同．基于混合距离学习的鲁棒的模糊 Ｃ 均值聚类算法［Ｊ］． 智能系统学报， ２０１７， １２（４）： ４５０－４５８． 英文引用格式：ＢＩＡＮ Ｚｅｋａｎｇ， ＷＡＮＧ Ｓｈｉｔｏｎｇ． Ｒｏｂｕｓｔ ＦＣＭ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｈｙｂｒｉｄ⁃ｄｉｓｔａｎｃｅ ｌｅａｒｎｉｎｇ ［ Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， ２０１７， １２（４）： ４５０－４５８． Ｒｏｂｕｓｔ ＦＣＭ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｈｙｂｒｉｄ⁃ｄｉｓｔａｎｃｅ ｌｅａｒｎｉｎｇ ＢＩＡＮ Ｚｅｋａｎｇ， ＷＡＮＧ Ｓｈｉｔｏｎｇ （Ｓｃｈｏｏｌ ｏｆ Ｄｉｇｉｔａｌ Ｍｅｄｉａ， Ｊｉａｎｇｎａｎ Ｕｎｉｖｅｒｓｉｔｙ， Ｗｕｘｉ ２１４１２２， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅ ｄｉｓｔａｎｃｅ ｍｅｔｒｉｃ ｐｌａｙｓ ａ ｖｉｔａｌ ｒｏｌｅ ｉｎ ｔｈｅ ｆｕｚｚｙ Ｃ⁃ｍｅａｎｓ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ． Ｉｎ ａｃｔｕａｌ ａｐｐｌｉｃａｔｉｏｎｓ， ｔｈｅｒｅ ｉｓ ａ ｐｒａｃｔｉｃａｌ ｓｃｅｎａｒｉｏ ｉｎ ｗｈｉｃｈ ｔｈｅ ｃｌｕｓｔｅｒｅｄ ｄａｔａ ｈａｖｅ ａ ｃｅｒｔａｉｎ ａｍｏｕｎｔ ｏｆ ｓｉｄｅ ｉｎｆｏｒｍａｔｉｏｎ， ｓｕｃｈ ａｓ ｐａｉｒｗｉｓｅ ｃｏｎｓｔｒａｉｎｔｓ ｗｉｔｈ ｌａｂｅｌｓ． Ｔｏ ｓｕｆｆｉｃｉｅｎｔｌｙ ｕｔｉｌｉｚｅ ｔｈｉｓ ｓｉｄｅ ｉｎｆｏｒｍａｔｉｏｎ， ｆｉｒｓｔ， ｗｅ ｐｒｏｐｏｓｅ ａ ｌｅａｒｎｉｎｇ ｍｅｔｈｏｄ ｂａｓｅｄ ｏｎ ｈｙｂｒｉｄ ｄｉｓｔａｎｃｅ， ｉｎ ｗｈｉｃｈ ｓｉｄｅ ｉｎｆｏｒｍａｔｉｏｎ ｃａｎ ｂｅ ｕｔｉｌｉｚｅｄ ｔｏ ａｔｔａｉｎ ａ ｄｉｓｔａｎｃｅ ｍｅｔｒｉｃ ｆｏｒｍｕｌａ ｆｏｒ ｔｈｅ ｄａｔａ ｓｅｔ． Ｎｅｘｔ， ｗｅ ｐｒｏｐｏｓｅ ａ ｒｏｂｕｓｔ ｆｕｚｚｙ Ｃ⁃ｍｅａｎｓ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ （ＨＲ⁃ＦＣＭ ａｌｇｏｒｉｔｈｍ） ｂａｓｅｄ ｏｎ ｈｙｂｒｉｄ⁃ｄｉｓｔａｎｃｅ ｌｅａｒｎｉｎｇ， ｗｈｉｃｈ ｉｓ ｓｅｍｉ⁃ｓｕｐｅｒｖｉｓｅｄ． Ｔｈｅ ＨＲ⁃ＦＣＭ ｉｎｈｅｒｉｔｓ ｔｈｅ ｒｏｂｕｓｔｎｅｓｓ ｏｆ ｔｈｅ ＧＩＦＰ⁃ＦＣＭ （ｇｅｎｅｒａｌｉｚｅｄ ＦＣＭ ａｌｇｏｒｉｔｈｍ ｗｉｔｈ ｉｍｐｒｏｖｅｄ ｆｕｚｚｙ ｐａｒｔｉｔｉｏｎｓ） ａｎｄ ｈａｓ ｂｅｔｔｅｒ ｃｌｕｓｔｅｒｉｎｇ ｐｅｒｆｏｒｍａｎｃｅ ｄｕｅ ｔｏ ｔｈｅ ｍｏｒｅ ａｐｐｒｏｐｒｉａｔｅ ｄｉｓｔａｎｃｅ ｍｅｔｒｉｃ． Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｃｏｎｆｉｒｍ ｔｈｅ ｅｆｆｅｃｔｉｖｅｎｅｓｓ ｏｆ ｔｈｅ ｐｒｏｐｏｓｅｄ ａｌｇｏｒｉｔｈｍ． Ｋｅｙｗｏｒｄｓ： ｄｉｓｔａｎｃｅ ｍｅｔｒｉｃ； ＦＣＭ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ； ｐａｉｒｗｉｓｅ ｃｏｎｓｔｒａｉｎｔｓ；ｓｉｄｅ ｉｎｆｏｒｍａｔｉｏｎ； ｈｙｂｒｉｄ ｄｉｓｔａｎｃｅ； ｓｅｍｉ⁃ｓｕｐｅｒｖｉｓｅｄ； ＧＩＦＰ⁃ＦＣＭ； ｒｏｂｕｓｔｎｅｓｓ 收稿日期：２０１６－０７－２３． 网络出版日期：２０１７－０４－０７． 基金项目：国家自然科学基金项目（６１２７２２１０）． 通信作者：卞则康． Ｅ⁃ｍａｉｌ：ｂｉａｎｚｅｋａｎｇ＠ １６３．ｃｏｍ． 聚类分析作为一种重要的数据处理技术已经 被广泛地应用到各种领域，如模式识别、数据挖掘 等。 在聚类分析中，需要根据数据点之间的相似或 相异程度，对数据点进行区分和分类。 因此对于不 同的数据集，选择合适的距离度量方式对算法的聚 类性能有重要的影响［１］ 。 欧式距离是较为常用的 距离度量方式，但其具有以下不足：１） 采用欧式距 离的方法通常是假设所有变量都是不相关的，并且 数据所有维度的方差都为 １，所有变量的协方差为 ０ ［２］ ；２）欧式距离仅仅适用于特征空间中的超球结 构，对于其他结构的数据集不太理想；３） 欧式距离 对噪声 比 较 敏 感， 聚 类 结 果 容 易 受 到 噪 声 的 干 扰［３］ 。 因此，欧式距离在实际应用中受到了限制。 针对这些问题，近年来提出了多种距离学习的 方法，根据在距离学习过程中是否有先验的训练样 本，距离学习可以分为有监督距离学习［４－６］ 和无监 督距离学习［７－８］ 。 在有监督距离学习的方法中，需
第4期 卞则康，等：基于混合距离学习的鲁棒的模糊C均值聚类算法 ·451- 要借助数据集的辅助信息进行距离学习，其中辅助 在距离学习中，借鉴文献[2]的思想，利用最大 信息通常以约束对的形式来表示[。由数据集辅 边界的框架，优化目标函数： 助信息学习得到的距离函数，可以有效地反映数据 集的自身特点，对数据集具有很好的适用性。 2o-c宫w套d比- k三1 在之前的研究中，人们提出了许多利用辅助信 息进行距离学习的算法。比如，将距离学习转化为 tn)B)0 凸优化问题的方法)、相关成分分析法[)、区分成 分分析法等。然而这些方法大多数将目标函数 0=1,0≤a,≤1，i=1,2… (2) 假设在马氏距离的框架下，本质上来说，针对马氏 式中：山，(x。,x)表示第k对约束对的第i个距离分 量，为了便于表示，在之后的介绍中用来代替 距离学习得到的新距离是欧式距离的线性变换，仍 然有欧式距离的缺点。在含有辅助信息的数据集 d(x。,x)。y为该对样本点的对应类标，C为惩罚 中，欧式距离的聚类性能和鲁棒性不理想。 因子，B为阈值。 因此，本文提出了一种基于混合距离学习的鲁 使用拉格朗日乘子法优化式(2)，其拉格朗日 函数为 棒模糊C均值聚类算法(HR-CM)。在此算法中， 数据集的未知距离被表示成若干候选距离的线性 - L=- (2w,d(x,x)-B)+ k=1 组合，在候选的距离度量中加入了非线性的距离度 量。与其他有监督的聚类算法-不同的是，HR (3) FCM利用数据集本身含有的少数的辅助信息进行 式中：9：和入为拉格朗日乘子。则式(3)的KKT条 混合距离的学习，相对于欧式距离没有考虑到数据 件为 集本身的特征，利用数据集的辅助信息学习得到的 aL 混合距离融合了数据集的一些特征，提高了提高算 .=0 a0i 法的聚类性能和鲁棒性。 (4) P:≥0 1混合距离学习 (9,w:=0 显然由式(4)无法求得o,因此先舍弃ω：非负 1.1混合距离 的条件，则可重新构建新的拉格朗日函数，如式(5) 由于数据集结构特征不同，为了合理地计算不 所示： 同数据集之间的距离，在距离学习中引入权重已经 L= 成为一种常用的方法。本文定义数据集中的混合 2 k=1 i=1 距离度量的线性组合如下： 入(1- (5) D(x,y)= aa 可以求得 s20,=1,0≤，≤1，i=1,2,…p() (6) 由文献[13]可证式(1)中D(x,y)是一个距离 由式(6)可以看出，即使在成功的优化过程下 函数。下面将介绍距离学习的过程。 ω：也可能出现负值，由前文看出，在考虑ω：为负的 本文的数据集分为两个部分：1)训练集，它是 条件下，无法用拉格朗日函数求解。因此，在受到 以约束对形式存在的辅助信息：2)用来聚类的数据 加权中心模糊聚类算法[4的启发，可以将w:改写 集。本文将所有的训练样本集合表示为D= 为式(7)的形式： {(x。,x,y),k=1,2,…,n,},其中n,为成对约束的 0, iep 对数。每一对约束对都是一个包含3个元素的元组 W; (x,x,y),其中x和x哈为d维向量的样本点，y 立，iep 是点对x和x之间关系的类标。当x和x属于 (7) 同一类样本时，y为正；相反，y为负。使用X= 式中：P表示所有使w,取正值的i的集合，p表示无 {x1,x2,…,x}来表示D中所有的训练样本点，其 法使w.取正值的i的集合，使用|p|和p|来分别 中N表示样本点的个数。 表示集合p和p的大小
要借助数据集的辅助信息进行距离学习，其中辅助 信息通常以约束对的形式来表示［９］ 。 由数据集辅 助信息学习得到的距离函数，可以有效地反映数据 集的自身特点，对数据集具有很好的适用性。 在之前的研究中，人们提出了许多利用辅助信 息进行距离学习的算法。 比如，将距离学习转化为 凸优化问题的方法［４］ 、相关成分分析法［５］ 、区分成 分分析法等［１０］ 。 然而这些方法大多数将目标函数 假设在马氏距离的框架下，本质上来说，针对马氏 距离学习得到的新距离是欧式距离的线性变换，仍 然有欧式距离的缺点。 在含有辅助信息的数据集 中，欧式距离的聚类性能和鲁棒性不理想。 因此，本文提出了一种基于混合距离学习的鲁 棒模糊 Ｃ 均值聚类算法（ＨＲ⁃ＦＣＭ）。 在此算法中， 数据集的未知距离被表示成若干候选距离的线性 组合，在候选的距离度量中加入了非线性的距离度 量。 与其他有监督的聚类算法［１１－１２］ 不同的是，ＨＲ⁃ ＦＣＭ 利用数据集本身含有的少数的辅助信息进行 混合距离的学习，相对于欧式距离没有考虑到数据 集本身的特征，利用数据集的辅助信息学习得到的 混合距离融合了数据集的一些特征，提高了提高算 法的聚类性能和鲁棒性。 １ 混合距离学习 １．１ 混合距离 由于数据集结构特征不同，为了合理地计算不 同数据集之间的距离，在距离学习中引入权重已经 成为一种常用的方法。 本文定义数据集中的混合 距离度量的线性组合如下： Ｄ（ｘ，ｙ） ＝ ∑ ｐ ｉ ＝ １ ωｉｄｉ（ｘ，ｙ） ｓ．ｔ．∑ ｐ ｉ ＝ １ ωｉ ＝ １，０ ≤ ωｉ ≤ １，ｉ ＝ １，２，…，ｐ （１） 由文献［１３］可证式（１）中 Ｄ（ ｘ，ｙ）是一个距离 函数。 下面将介绍距离学习的过程。 本文的数据集分为两个部分：１） 训练集，它是 以约束对形式存在的辅助信息；２）用来聚类的数据 集。 本文 将 所 有 的 训 练 样 本 集 合 表 示 为 Ｄ ＝ （ｘ ｋ ａ ，ｘ ｋ ｂ，ｙｋ），ｋ ＝ １，２，…，ｎｐ { } ，其中 ｎｐ 为成对约束的 对数。 每一对约束对都是一个包含 ３ 个元素的元组 （ｘ ｋ ａ ，ｘ ｋ ｂ，ｙｋ），其中 ｘ ｋ ａ 和 ｘ ｋ ｂ 为 ｄ 维向量的样本点，ｙｋ 是点对 ｘ ｋ ａ 和 ｘ ｋ ｂ 之间关系的类标。 当 ｘ ｋ ａ 和 ｘ ｋ ｂ 属于 同一类样本时， ｙｋ 为正；相反， ｙｋ 为负。 使用 Ｘ ＝ ｘ１ ，ｘ２ ，…，ｘＮ { } 来表示 Ｄ 中所有的训练样本点，其 中 Ｎ 表示样本点的个数。 在距离学习中，借鉴文献［２］的思想，利用最大 边界的框架，优化目标函数： ｍｉｎ ωｉ ，β Ｊ ＝ １ ２ ∑ ｐ ｉ ＝ １ ω ２ ｉ － Ｃ∑ ｎ ｋ ＝ １ ｙｋ（∑ ｐ ｉ ＝ １ ωｉｄｉ（ｘ ｋ ａ ，ｘ ｋ ｂ） － β） ｓ．ｔ． ｙｋ（∑ ｐ ｉ ＝ １ ωｉｄｉ（ｘ ｋ ａ ，ｘ ｋ ｂ） － β） ＞ ０ ∑ ｐ ｉ ＝ １ ωｉ ＝ １，０ ≤ ωｉ ≤ １，ｉ ＝ １，２，…，ｐ （２） 式中：ｄｉ（ｘ ｋ ａ ，ｘ ｋ ｂ）表示第 ｋ 对约束对的第 ｉ 个距离分 量，为了便于表示，在之后的介绍中用 ｄ ｋ ｉ 来代替 ｄｉ（ｘ ｋ ａ ，ｘ ｋ ｂ）。 ｙｋ 为该对样本点的对应类标，Ｃ 为惩罚 因子，β 为阈值。 使用拉格朗日乘子法优化式（２），其拉格朗日 函数为 Ｌ ＝ １ ２ ∑ ｐ ｉ ＝ １ ω ２ ｉ － Ｃ∑ ｎｐ ｋ ＝ １ ｙｋ（∑ ｐ ｉ ＝ １ ωｉｄｉ（ｘ ｋ ａ ，ｘ ｋ ｂ） － β） ＋ λ（１ － ∑ ｐ ｉ ＝ １ ωｉ） ＋ ∑ ｐ ｉ ＝ １ φｉωｉ （３） 式中：φｉ 和 λ 为拉格朗日乘子。 则式（３）的 ＫＫＴ 条 件为 Ｌ ωｉ ＝ ０ φｉ ≥ ０ φｉωｉ ＝ ０ ì î í ï ïï ï ï （４） 显然由式（４）无法求得 ωｉ，因此先舍弃 ωｉ 非负 的条件，则可重新构建新的拉格朗日函数，如式（５） 所示： Ｌ ＝ １ ２ ∑ ｐ ｉ ＝ １ ω ２ ｉ － Ｃ∑ ｎｐ ｋ ＝ １ ｙｋ（∑ ｐ ｉ ＝ １ ωｉｄｉ（ｘ ｋ ａ ，ｘ ｋ ｂ） － β） ＋ λ（１ － ∑ ｐ ｉ ＝ １ ωｉ） （５） 可以求得 ωｉ ＝ １ ｐ ＋ Ｃ∑ ｎｐ ｋ ＝ １ ｙｋｄ ｋ ｉ － Ｃ ｐ ∑ ｐ ｊ ＝ １ ∑ ｎｐ ｋ ＝ １ ｙｋｄ ｋ ｊ （６） 由式（６）可以看出，即使在成功的优化过程下 ωｉ 也可能出现负值，由前文看出，在考虑 ωｉ 为负的 条件下，无法用拉格朗日函数求解。 因此，在受到 加权中心模糊聚类算法［１４］ 的启发，可以将 ωｉ 改写 为式（７）的形式： ωｉ ＝ ０， ｉ ∈ ｐ － １ ｐ ＋ ＋ Ｃ∑ ｎｐ ｋ ＝ １ ｙｋｄ ｋ ｉ － Ｃ ｐ ＋ ∑ ｐ ｊ ＝ １ ∑ ｎｐ ｋ ＝ １ ｙｋｄ ｋ ｊ ， ｉ ∈ ｐ ＋ ì î í ï ï ïï （７） 式中：ｐ ＋表示所有使 ωｉ 取正值的 ｉ 的集合，ｐ －表示无 法使 ωｉ 取正值的 ｉ 的集合，使用 ｐ ＋ 和 ｐ － 来分别 表示集合 ｐ ＋和 ｐ －的大小。 第 ４ 期 卞则康，等：基于混合距离学习的鲁棒的模糊 Ｃ 均值聚类算法 ·４５１·
.452 智能系统学报 第12卷 对于阈值B,使用梯度下降的方法进行求解，通 过求偏导，得到B的梯度如下： n={y4∈D:y(∑w,d(,)-B>0)} V-GZn ③计算梯度： (8) k=1 7J=C∑a ken 为了满足约束条件：（∑，4(c)-B)> ④更新阈值：B=B-yVgJ: 0,参考w:的表示方式，则符合约束条件的y4的集合： ⑤更新集合p和p,使用算法1： m={beD(∑0,4()->0，重新 ⑥更新w。 定义了B的梯度公式： 至此，通过对训练集的距离学习，得到的权值 1n1 ω：，从而得到新的距离函数。通过数据集本身构成 J=c21 (9) 的辅助信息学习得到的混合距离，对数据集自身的 适应性更高，更有利于聚类效果的改善。 式中：n|表示集合n,的大小。使用梯度下降的 1.2时间复杂度分析 方法，求解B=B-yVJ,其中，y表示为梯度下降的 这个部分主要讨论所提算法的时间复杂度， 学习速率，设置y=。 HR-FCM算法的时间复杂度主要讨论的是混合距离 学习的时间复杂度。总的来说，混合距离学习的最 由于集合n不断改变，则等式进一步修改为 大时间复杂度为O(N2d),其中N表示训练数据集 如下形式： 中样本的个数，d表示样本的维度，p表示候选距离 0,iEp 的个数。算法的主要时间消耗在求解距离矩阵D (10) +CE,i∈p 中，时间复杂度为O(Ndp)。在迭代循环中，每一步 都有一个线性的时间复杂度，为O(max(V,n,))。 式中： 2 基于混合距离学习的鲁棒的FCM (11) 算法 具体的算法描述如下： 模糊C均值聚类算法(FCM),它是一种基于目 求解集合p*和p的算法，算法1如下： 标函数的聚类算法，是迄今为止应用最广泛、理论 1)初始化p=,Po={1,2,…,P},h=0; 最为完善的聚类算法。传统的FCM聚类算法使用 2)h=h+1,P=Pt+{i},P=Pi-,-{,其中i= 欧式距离作为距离度量函数导致其聚类性能和鲁 arg max 棒性较差。 icP-1 3)通过式(10)计算w,并判断其是否大于0。 针对传统FCM算法的缺点，近年来研究者们提 其中g=arg max{E}。如果ω，>0，则返回2)，否则 出了一些改进的FCM算法，例如：基于改进的模糊 划分的模糊C均值聚类算法(IFP-FCM)[1s)]和基于 设置p=p1Pi=P-,并终止。 改进的模糊划分的泛化的模糊C均值聚类算法 求解ω具体算法，算法2步骤如下： (GFP-FCM)[I6)。IFP-FCM算法是由Hoppner和 输入数据矩阵X∈R,惩罚因子C,成对约 Klawonn提出的一种改进的FCM聚类算法。FP 束(x。,xy),其中y={+1,-1) FCM算法通过对每个数据增加一个隶属约束函数， 输出距离权值ω，阈值B。 以降低算法对噪声的敏感性，增加了算法的鲁棒 步骤： 性。但是此算法仍然沿用的是传统的欧式距离作 1)初始化：o=w0=二，B=B(在初始权值下 为距离度量，受到IFP-FCM算法的启发，朱林等提 出了GIFP-FCM算法。 取距离的最大值作为B的初值)。 在此启发下，本文提出了一种基于混合距离学 2)计算距离矩阵：D(i,k), 习的鲁棒的FCM聚类算法，算法描述如下： 3)设置迭代步数：t=1, 假设给定一个样本集合X={x1,x2,…,x},其 4)循环，直至收敛： 中n是样本的个数，每一个样本是d维，预设聚类中 ①更新学习率：y=1/1,t=t+1 心的集合为V={y:,1≤i≤c},其中c表示类别数。 ②更新训练子集： 令u:表示第j个样本隶属于第i类的程度。则隶属
对于阈值 β，使用梯度下降的方法进行求解，通 过求偏导，得到 β 的梯度如下： Ñβ Ｊ ＝ Ｃ ∑ ｎｐ ｋ ＝ １ ｙｋ （８） 为了满足约束条件： ｙｋ ∑ ｐ ｉ ＝ １ ωｉｄｉ ｘ ｋ ａ，ｘ ｋ ｂ ( ( ) － β) ＞ ０，参考 ωｉ 的表示方式，则符合约束条件的 ｙｋ 的集合： ｎ ＋ ｐ ＝ ｙｋ ∈ Ｄ：ｙｋ ∑ ｐ ｉ ＝ １ ωｉｄｉ ｘ ｋ ａ，ｘ ｋ ｂ { ( ( ) － β) ＞ ０} ，重新 定义了 β 的梯度公式： Ñβ Ｊ ＝ Ｃ∑ ｜ ｎｐ ＋｜ ｋ ＝ １ ｙｋ （９） 式中： ｎ ＋ ｐ 表示集合 ｎｐ ＋ 的大小。 使用梯度下降的 方法，求解 β′＝ β－γ Ñβ Ｊ，其中，γ 表示为梯度下降的 学习速率，设置 γ ＝ １ ｔ 。 由于集合 ｎｐ ＋ 不断改变，则等式进一步修改为 如下形式： ωｉ ＝ ０， ｉ ∈ ｐ － １ ｐ ＋ ＋ ＣＥｉ， ｉ ∈ ｐ ＋ ì î í ï ï ïï （１０） 式中： Ｅｉ ＝ ∑ ｎｐ ｋ ＝ １ ｙｋｄ ｋ ｉ － １ ｐ ＋ ∑ ｊ ＝ ｐ ＋∑ ｎｐ ｋ ＝ ｎ ＋ ｐ ｙｋｄ ｋ ｊ （１１） 具体的算法描述如下： 求解集合 ｐ ＋和 ｐ －的算法，算法 １ 如下： １）初始化 ｐ ＋ ＝∅，ｐ － ０ ＝{１，２，…，ｐ} ，ｈ ＝ ０； ２）ｈ ＝ ｈ＋１，ｐ ＋ ｈ ＝ ｐ ＋ ｈ－１ ＋{ｉ} ，ｐ － ｈ ＝ ｐ － ｈ－１ －{ｉ} ，其中 ｉ ＝ ａｒｇ ｍａｘ ｉ∈ｐ － ｈ－１ Ｅｉ { } ； ３）通过式（１０） 计算 ωｇ 并判断其是否大于 ０。 其中 ｇ ＝ ａｒｇ ｍａｘ ｉ∈ｐ ＋ ｈ Ｅｉ { } 。 如果 ωｇ ＞０，则返回 ２），否则 设置 ｐ ＋ ｈ ＝ ｐ ＋ ｈ－１ ，ｐ － ｈ ＝ ｐ － ｈ－１并终止。 求解 ω 具体算法，算法 ２ 步骤如下： 输入 数据矩阵 Ｘ∈Ｒ ｄ×Ｎ ，惩罚因子 Ｃ，成对约 束（ｘ ｋ ａ ，ｘ ｋ ｂ，ｙｋ），其中 ｙｋ ＝{＋１，－１} ； 输出 距离权值 ω，阈值 β。 步骤： １）初始化：ω＝ ω （０） ＝ １ ｐ ，β ＝ β （０） （在初始权值下 取距离的最大值作为 β 的初值）。 ２）计算距离矩阵：Ｄ（ｉ，ｋ）， ３）设置迭代步数：ｔ ＝ １， ４）循环，直至收敛： ①更新学习率：γ ＝ １ ／ ｔ，ｔ ＝ ｔ＋１ ②更新训练子集： ｎ ＋ ｐ ＝ ｙｋ ∈ Ｄ：ｙｋ ∑ ｐ ｉ ＝ １ ωｉｄｉ（ｘ ｋ ａ ，ｘ ｋ { ( ｂ） － β ＞ ０) } ③计算梯度： ∇ β Ｊ ＝ Ｃ∑ｋ∈ｎ ＋ ｐ ｙｋ ④更新阈值：β′＝ β－γ Ñβ Ｊ； ⑤更新集合 ｐ ＋和 ｐ － ，使用算法 １； ⑥更新 ω。 至此，通过对训练集的距离学习，得到的权值 ωｉ，从而得到新的距离函数。 通过数据集本身构成 的辅助信息学习得到的混合距离，对数据集自身的 适应性更高，更有利于聚类效果的改善。 １．２ 时间复杂度分析 这个部分主要讨论所提算法的时间复杂度， ＨＲ⁃ＦＣＭ 算法的时间复杂度主要讨论的是混合距离 学习的时间复杂度。 总的来说，混合距离学习的最 大时间复杂度为 Ｏ（Ｎ ２ ｄｐ），其中 Ｎ 表示训练数据集 中样本的个数，ｄ 表示样本的维度，ｐ 表示候选距离 的个数。 算法的主要时间消耗在求解距离矩阵 Ｄ 中，时间复杂度为 Ｏ（Ｎｄｐ）。 在迭代循环中，每一步 都有一个线性的时间复杂度，为 Ｏ（ｍａｘ（Ｎ，ｎｐ））。 ２ 基于混合距离学习的鲁棒的 ＦＣＭ 算法 模糊 Ｃ 均值聚类算法（ＦＣＭ），它是一种基于目 标函数的聚类算法，是迄今为止应用最广泛、理论 最为完善的聚类算法。 传统的 ＦＣＭ 聚类算法使用 欧式距离作为距离度量函数导致其聚类性能和鲁 棒性较差。 针对传统 ＦＣＭ 算法的缺点，近年来研究者们提 出了一些改进的 ＦＣＭ 算法，例如：基于改进的模糊 划分的模糊 Ｃ 均值聚类算法（ ＩＦＰ⁃ＦＣＭ） ［１５］ 和基于 改进的模糊划分的泛化的模糊 Ｃ 均值聚类算法 （ＧＩＦＰ⁃ＦＣＭ） ［１６］ 。 ＩＦＰ⁃ＦＣＭ 算法是由 Ｈöｐｐｎｅｒ 和 Ｋｌａｗｏｎｎ 提出的一种改进的 ＦＣＭ 聚类算法。 ＩＦＰ⁃ ＦＣＭ 算法通过对每个数据增加一个隶属约束函数， 以降低算法对噪声的敏感性，增加了算法的鲁棒 性。 但是此算法仍然沿用的是传统的欧式距离作 为距离度量，受到 ＩＦＰ⁃ＦＣＭ 算法的启发，朱林等提 出了 ＧＩＦＰ⁃ＦＣＭ 算法。 在此启发下，本文提出了一种基于混合距离学 习的鲁棒的 ＦＣＭ 聚类算法，算法描述如下： 假设给定一个样本集合 Ｘ ＝ ｘ１ ，ｘ２ ，…，ｘｎ { } ，其 中 ｎ 是样本的个数，每一个样本是 ｄ 维，预设聚类中 心的集合为 Ｖ ＝ ｖ{ ｉ，１≤ｉ≤ｃ} ，其中 ｃ 表示类别数。 令 ｕｉｊ表示第 ｊ 个样本隶属于第 ｉ 类的程度。 则隶属 ·４５２· 智 能 系 统 学 报 第 １２ 卷
第4期 卞则康，等：基于混合距离学习的鲁棒的模糊C均值聚类算法 ·453. 矩阵为U={u,l1≤i≤c,1≤j≤n}。对于每一个样 式中：ω：是通过距离学习得到的权值。 本x,通过构造一个新的隶属约束函数f(“)= 算法3HR-FCM算法 ∑“，(1-写)，同时为每一个样本增加一个惩 输入数据矩阵X∈RW,权值向量w,聚类数 罚项α，以提高算法的鲁棒性，那么得到新的目标函 目c,阈值e,模糊指数m,抗噪参数α，最大迭代次 数为 数T; 输出最终的隶属矩阵U。 步骤： 1)初始化：山，=，t=1; 三与=山，0≤4，≤1,1≤i≤c,1≤≤n 2)使用式(16)计算新的聚类中心； (12) 3)使用式(17)计算新的隶属矩阵售； 式中：a,=a×mind(x,y,),0≤a≤1，a为抗噪参数。 4)如果‖U+1-U‖<ε或者t>T,输出最终的隶 1多se 属矩阵，否则t=t+1返回2)。 使用拉格朗日乘数法对式(12)进行优化，得到 HR-FCM算法通过使用距离学习得到的新的混 新的聚类中心和隶属函数如式(13)和式(14)： 合距离代替传统FCM算法中的欧式距离，进一步增 ∑写 加了算法的抗噪性能。再者，通过数据集本身的辅 13) ∑写 助信息进行距离的学习的得到的混合距离，比原有 1 的欧式距离更加适合数据集，提高了算法的适用 性。HR-FCM算法与传统的FCM算法相比，具有更 d(x,y)-a×mind(,y,） 佳的聚类性能和鲁棒性。 d(x,y)-a×mind(x,y,) 3实验研究和分析 (14) 本章通过实验检测本文提出的HR-FCM算法 4,(,)=(-P)st1<p<2 的聚类性能和鲁棒性能。本章的实验主要分为两 (15) 个部分：1)将本文提出的HR-FCM算法与现有的基 式(15)是表示样本与类中心的距离度量公式，当p= 于欧氏距离的聚类算法作比较，如：FCM、K-means 2时，式(15)就是传统的欧氏距离。 和K-medoids,检测算法的聚类性能；2)主要是检测 本文提出的HR-FCM算法，加入了距离学习的 算法的鲁棒性能，通过对实验数据加入不同程度的随 过程，通过距离学习出来的距离度量比传统的欧式 机噪声，并与FCM算法和GIFP-FCM算法作比较。 距离更佳适合具有辅助信息的数据集，增加了算法 3.1实验设置和实验数据 的聚类性能和鲁棒性。因此，用新的混合距离D替 本文的实验参数设置如下：阈值ε=10，最大 换式(13)和式(14)中的距离度量dn,得到新的聚类 迭代次数T=300,模糊指数T=300,m∈{1.5,2,3， 中心公式(16)和隶属度计算公式(17)： 4},a∈{0.5,0.7,0.9,0.99}。为了实验结果的公平 重复每次聚类过程20，实验结果取均值。 实验中对于候选距离的选取，选择了基于欧式 了： (16) 距离的含有方差的距离分量d(x,y),非线性的距 1 离分量d(x,y),曼哈顿距离分量d2(x,y)。由这3 g= 种距离分量线性组合后的混合距离D(x,y)是一个 D'(x,)-a×minD(x,y ∑k=D2(x,y)-a×minD'(E.g 非线性的距离函数。本文预设的3个距离度量如式 (19)所示： (17) d (x,y)=(x-y)"(x-y) 式中距离度量D的定义如式(18)： D(x.y)= d(x,） 4(x.3)= (19) s.t. ∑0：=1,0≤0，≤1 (18) 4(xJ)=1-exp(--3‖r-y2)
矩阵为 Ｕ ＝ ｛ｕｉｊ １≤ｉ≤ｃ，１≤ｊ≤ｎ｝。 对于每一个样 本 ｘｊ， 通过构造一个新的隶属约束函数 ｆ（ｕｉｊ） ＝ ∑ ｃ ｉ ＝ １ ｕｉｊ（１ － ｕ ｍ－１ ｉｊ ） ，同时为每一个样本增加一个惩 罚项 ａｊ 以提高算法的鲁棒性，那么得到新的目标函 数为 Ｊ＝∑ ｃ ｉ ＝ １ ∑ ｎ ｊ ＝ １ ｕ ｍ ｉｊ ｄ ２ ｐ（ｘｊ，ｖｉ） ＋∑ ｎ ｊ ＝ １ ａｊ∑ ｃ ｉ ＝ １ ｕｉｊ（１ － ｕ ｍ－１ ｉｊ ） ｓ．ｔ． ｍ＞１ ∑ ｃ ｉ ＝ １ ｕｉｊ ＝ １， ０ ≤ ｕｉｊ ≤ １， １ ≤ ｉ ≤ ｃ，１ ≤ ｊ ≤ ｎ （１２） 式中：ａｊ ＝α× ｍｉｎ １≤ｓ≤ｃ ｄ ２ ｐ（ｘｊ，ｖｓ），０≤α≤１，α 为抗噪参数。 使用拉格朗日乘数法对式（１２）进行优化，得到 新的聚类中心和隶属函数如式（１３）和式（１４）： ｖｉ ＝ ∑ ｎ ｊ ＝ １ ｕ ｍ ｉｊ ｘｊ ∑ ｎ ｊ ＝ １ ｕ ｍ ｉｊ （１３） ｕｉｊ ＝ １ ∑ ｃ ｋ ＝ １ ｄ ２ ｐ（ｘｊ，ｖｉ） － α × ｍｉｎ １≤ｓ≤ｃ ｄ ２ ｐ（ｘｊ，ｖｓ） ｄ ２ ｐ（ｘｊ，ｖｋ） － α × ｍｉｎ １≤ｓ≤ｃ ｄ ２ ｐ（ｘｊ，ｖｓ） æ è çç ö ø ÷÷ １ ｍ－１ （１４） ｄｐ（ｘｊ，ｖｉ） ＝ （∑ ｎ ｋ ＝ １ ｘｊ － ｖｉ ｐ ） １ ｐ ｓ．ｔ． １ ＜ ｐ ＜ ２ （１５） 式（１５）是表示样本与类中心的距离度量公式，当ｐ ＝ ２ 时，式（１５）就是传统的欧氏距离。 本文提出的 ＨＲ⁃ＦＣＭ 算法，加入了距离学习的 过程，通过距离学习出来的距离度量比传统的欧式 距离更佳适合具有辅助信息的数据集，增加了算法 的聚类性能和鲁棒性。 因此，用新的混合距离 Ｄ 替 换式（１３）和式（１４）中的距离度量 ｄｐ，得到新的聚类 中心公式（１６）和隶属度计算公式（１７）； ｖｉ ＝ ∑ ｎ ｊ ＝ １ ｕ ｍ ｉｊ ｘｊ ∑ ｎ ｊ ＝ １ ｕ ｍ ｉｊ （１６） ｕｉｊ ＝ １ ∑ ｃ ｋ ＝ １ Ｄ ２ （ｘｊ，ｖｉ） － α × ｍｉｎ １≤ｓ≤ｃ Ｄ ２ （ｘｊ，ｖｓ） Ｄ ２ （ｘｊ，ｖｋ） － α × ｍｉｎ １≤ｓ≤ｃ Ｄ ２ （ｘｊ，ｖｓ） æ è çç ö ø ÷÷ １ ｍ－１ （１７） 式中距离度量 Ｄ 的定义如式（１８）： Ｄ（ｘ，ｙ） ＝ ∑ ｐ ｉ ＝ １ ωｉｄｉ（ｘ，ｙ） ｓ．ｔ． ∑ ｐ ｉ ＝ １ ωｉ ＝ １，０ ≤ ωｉ ≤ １ （１８） 式中：ωｉ 是通过距离学习得到的权值。 算法 ３ ＨＲ⁃ＦＣＭ 算法 输入 数据矩阵 Ｘ∈Ｒ ｄ×Ｎ ，权值向量 ω，聚类数 目 ｃ，阈值 ε，模糊指数 ｍ，抗噪参数 α，最大迭代次 数 Ｔ； 输出 最终的隶属矩阵 Ｕ。 步骤： １）初始化：ｕｉｊ ＝ ｕ １ ｉｊ，ｔ ＝ １； ２）使用式（１６）计算新的聚类中心 ｖ ｔ＋１ ｉ ； ３）使用式（１７）计算新的隶属矩阵 ｕ ｔ＋１ ｉｊ ； ４）如果‖Ｕ ｔ＋１－Ｕ ｔ‖＜ε 或者 ｔ＞Ｔ，输出最终的隶 属矩阵，否则 ｔ ＝ ｔ＋１ 返回 ２）。 ＨＲ⁃ＦＣＭ 算法通过使用距离学习得到的新的混 合距离代替传统 ＦＣＭ 算法中的欧式距离，进一步增 加了算法的抗噪性能。 再者，通过数据集本身的辅 助信息进行距离的学习的得到的混合距离，比原有 的欧式距离更加适合数据集，提高了算法的适用 性。 ＨＲ⁃ＦＣＭ 算法与传统的 ＦＣＭ 算法相比，具有更 佳的聚类性能和鲁棒性。 ３ 实验研究和分析 本章通过实验检测本文提出的 ＨＲ⁃ＦＣＭ 算法 的聚类性能和鲁棒性能。 本章的实验主要分为两 个部分：１）将本文提出的 ＨＲ⁃ＦＣＭ 算法与现有的基 于欧氏距离的聚类算法作比较，如：ＦＣＭ、Ｋ⁃ｍｅａｎｓ 和 Ｋ⁃ｍｅｄｏｉｄｓ，检测算法的聚类性能；２）主要是检测 算法的鲁棒性能，通过对实验数据加入不同程度的随 机噪声，并与 ＦＣＭ 算法和 ＧＩＦＰ⁃ＦＣＭ 算法作比较。 ３．１ 实验设置和实验数据 本文的实验参数设置如下：阈值 ε ＝ １０ －５ ，最大 迭代次数 Ｔ ＝ ３００，模糊指数 Ｔ ＝ ３００，ｍ∈｛１．５，２，３， ４｝，α∈｛０．５，０．７，０．９，０．９９｝。 为了实验结果的公平， 重复每次聚类过程 ２０，实验结果取均值。 实验中对于候选距离的选取，选择了基于欧式 距离的含有方差的距离分量 ｄ１（ ｘ，ｙ），非线性的距 离分量 ｄ３（ｘ，ｙ），曼哈顿距离分量 ｄ２（ｘ，ｙ）。 由这 ３ 种距离分量线性组合后的混合距离 Ｄ（ｘ，ｙ）是一个 非线性的距离函数。 本文预设的 ３ 个距离度量如式 （１９）所示： ｄ１（ｘ，ｙ） ＝ （ｘ － ｙ） Ｔ １ σ ２ （ｘ － ｙ） ｄ２（ｘ，ｙ） ＝ ∑ ｄ ｉ ＝ １ ｘｉ － ｙｉ σ ２ ｄ３（ｘ，ｙ） ＝ １ － ｅｘｐ（ － － ３ ‖ｘ － ｙ‖２ σ ２ ） ì î í ï ï ï ï ï ï ï ï （１９） 第 ４ 期 卞则康，等：基于混合距离学习的鲁棒的模糊 Ｃ 均值聚类算法 ·４５３·
454. 智能系统学报 第12卷 本文选取的实验数据集均来自UCI数据集，数 知标签的原始数据的聚类结果，I(X,Y)定义了X和 据集细节如表1。由于UCI数据集中没有约束对形 Y之间的互信息，H(X)和H(Y)分别代表了X和Y 式的辅助信息，需要选取数据集中的一部分带标签 的嫡，a定义了X和Y中任意两个具有相同类标签 的数据集构成约束对作为训练集。其中，拥有相同 并且属于同一个样本的数目，b定义了X和Y中任 的类标的样本点构成正约束对，不同的类标的构成 意两个具有不同标签并且属于不同类的样本的个 负约束对，选取相同数目的正负约束对进行距离学 数，n表示原始样本的个数。显而易见，NMl和RI 习。对于本文中的数据集，前6个取10%的数据集 的值都是介于0~1的，NMI和RI的值越大，表示X 构成训练集，最后两个取1%的数据集。 和Y之间的相似度就越高，即算法的效果越好。 在抗噪声实验中，在数据集中随机加入10%和 3.3实验结果和分析 20%的高斯白噪声(SNR=40d山或者30d山)，分别 在第1部分的实验中，为了检测算法的聚类性 计算本文提出的HR-FCM算法、传统FCM聚类算法 能，设置HR-FCM算法中的抗噪参数a=0,比较使 和GFP-FCM算法的聚类性能。 用了混合距离的HR-FCM算法与使用欧氏距离的 表1数据集信息 FCM算法和其他常用的基于欧氏距离的聚类算法， Table 1 Description of data sets 检测混合距离对聚类性能的影响。选取上述7个数 数据集 样本数 特征数 类别数 据集作为本次实验的实验数据集，每组数据集运行 breast 683 10 2 20次，实验结果选取I和N值的均值，实验结果 2 如图1和图2所示。 wdbe 569 30 第1部分的实验结果表明：对于小数据集，HR vowel 528 10 10 FCM算法的聚类性能不仅比传统的基于欧氏距离 sonar 208 60 2 的FCM聚类算法要好，也比基于欧氏距离的K wine 178 13 mean和K-medoids的聚类算法性能好。对于大样 本数据集，由于样本数对于CM聚类算法的影响比 vehicle 846 18 4 K-means和K-medoids的大，此时，距离度量对于聚 led 3200 24 10 类性能的影响力下降，因此，K-means和K-medoids waveform 5000 21 算法的聚类性能较佳，但是与传统的FCM聚类算法 3.2评价方法 相比，本文提出的基于混合聚类的HR-FCM算法具 为了评估算法的聚类效果，本文采用了一些标 有较好的聚类性能，如waveform数据集。 准的评价方法，包括归一化互信息(NM)1)和芮氏 从表2的实验中还可以得到，对于高维的数据 指数(RI)[18-9),这些将用来评价HR-FCM算法与 集，4种算法聚类性能都有一定的下降。由于数据 FCM的聚类效果。 维度的增加，单个样本的信息增加，在这些信息中 I(X,Y) 存在着不同类型的信息，本文提出的混合距离度量 NMI(X.Y)=- 20 √H(X)·H(Y 函数相比传统的欧氏距离能够充分地度量出样本 之间的距离，学习出样本之间的有效信息，提高算 RI(X,Y)= a+b (21) n×(n-1)/2 法的聚类性能。对于数据集wdbc和sonar,表2的 式中：X定义了已知标签的原始数据，Y定义了对未 实验结果显示了混合距离的有效性。 表2聚类算法性能 Table 2 The performance of clustering algorithm breast wdbe sonar vehicle waveform 算法 RI NMI RI NMI RI NMI RI NMI RI NMI HR-FCM 0.88690.67200.85110.59420.50880.01710.66160.17090.6644 0.3490 FCM 0.51990.00450.75040.46720.50360.00910.65060.18020.6600 0.3209 K-means 0.52060.00470.75040.46720.50320.64300.65230.18680.6673 0.3622 K-medoids 0.52060.00470.77070.49990.50220.00710.65090.18660.6701 0.3681
本文选取的实验数据集均来自 ＵＣＩ 数据集，数 据集细节如表 １。 由于 ＵＣＩ 数据集中没有约束对形 式的辅助信息，需要选取数据集中的一部分带标签 的数据集构成约束对作为训练集。 其中，拥有相同 的类标的样本点构成正约束对，不同的类标的构成 负约束对，选取相同数目的正负约束对进行距离学 习。 对于本文中的数据集，前 ６ 个取 １０％的数据集 构成训练集，最后两个取 １％的数据集。 在抗噪声实验中，在数据集中随机加入 １０％和 ２０％的高斯白噪声（ ＳＮＲ ＝ ４０ ｄｂ 或者 ３０ ｄｂ），分别 计算本文提出的 ＨＲ⁃ＦＣＭ 算法、传统 ＦＣＭ 聚类算法 和 ＧＩＦＰ⁃ＦＣＭ 算法的聚类性能。 表 １ 数据集信息 Ｔａｂｌｅ １ Ｄｅｓｃｒｉｐｔｉｏｎ ｏｆ ｄａｔａ ｓｅｔｓ 数据集 样本数 特征数 类别数 ｂｒｅａｓｔ ６８３ １０ ２ ｗｄｂｃ ５６９ ３０ ２ ｖｏｗｅｌ ５２８ １０ １０ ｓｏｎａｒ ２０８ ６０ ２ ｗｉｎｅ １７８ １３ ３ ｖｅｈｉｃｌｅ ８４６ １８ ４ ｌｅｄ ３ ２００ ２４ １０ ｗａｖｅｆｏｒｍ ５ ０００ ２１ ３ ３．２ 评价方法 为了评估算法的聚类效果，本文采用了一些标 准的评价方法，包括归一化互信息（ＮＭＩ） ［１７］ 和芮氏 指数（ＲＩ） ［１８－１９］ ，这些将用来评价 ＨＲ⁃ＦＣＭ 算法与 ＦＣＭ 的聚类效果。 ＮＭＩ（Ｘ，Ｙ） ＝ Ｉ（Ｘ，Ｙ） Ｈ（Ｘ）·Ｈ（Ｙ） （２０） ＲＩ（Ｘ，Ｙ） ＝ ａ ＋ ｂ ｎ × （ｎ － １） ／ ２ （２１） 式中：Ｘ 定义了已知标签的原始数据，Ｙ 定义了对未 知标签的原始数据的聚类结果，Ｉ（Ｘ，Ｙ）定义了 Ｘ 和 Ｙ 之间的互信息，Ｈ（Ｘ）和 Ｈ（Ｙ）分别代表了 Ｘ 和 Ｙ 的熵，ａ 定义了 Ｘ 和 Ｙ 中任意两个具有相同类标签 并且属于同一个样本的数目，ｂ 定义了 Ｘ 和 Ｙ 中任 意两个具有不同标签并且属于不同类的样本的个 数，ｎ 表示原始样本的个数。 显而易见，ＮＭＩ 和 ＲＩ 的值都是介于 ０～１ 的，ＮＭＩ 和 ＲＩ 的值越大，表示 Ｘ 和 Ｙ 之间的相似度就越高，即算法的效果越好。 ３．３ 实验结果和分析 在第 １ 部分的实验中，为了检测算法的聚类性 能，设置 ＨＲ⁃ＦＣＭ 算法中的抗噪参数 α ＝ ０，比较使 用了混合距离的 ＨＲ⁃ＦＣＭ 算法与使用欧氏距离的 ＦＣＭ 算法和其他常用的基于欧氏距离的聚类算法， 检测混合距离对聚类性能的影响。 选取上述 ７ 个数 据集作为本次实验的实验数据集，每组数据集运行 ２０ 次，实验结果选取 ＲＩ 和 ＮＭＩ 值的均值，实验结果 如图 １ 和图 ２ 所示。 第 １ 部分的实验结果表明：对于小数据集，ＨＲ⁃ ＦＣＭ 算法的聚类性能不仅比传统的基于欧氏距离 的 ＦＣＭ 聚类算法要好，也比基于欧氏距离的 Ｋ⁃ ｍｅａｎ 和 Ｋ⁃ｍｅｄｏｉｄｓ 的聚类算法性能好。 对于大样 本数据集，由于样本数对于 ＦＣＭ 聚类算法的影响比 Ｋ⁃ｍｅａｎｓ 和 Ｋ⁃ｍｅｄｏｉｄｓ 的大，此时，距离度量对于聚 类性能的影响力下降，因此，Ｋ⁃ｍｅａｎｓ 和 Ｋ⁃ｍｅｄｏｉｄｓ 算法的聚类性能较佳，但是与传统的 ＦＣＭ 聚类算法 相比，本文提出的基于混合聚类的 ＨＲ⁃ＦＣＭ 算法具 有较好的聚类性能，如 ｗａｖｅｆｏｒｍ 数据集。 从表 ２ 的实验中还可以得到，对于高维的数据 集，４ 种算法聚类性能都有一定的下降。 由于数据 维度的增加，单个样本的信息增加，在这些信息中 存在着不同类型的信息，本文提出的混合距离度量 函数相比传统的欧氏距离能够充分地度量出样本 之间的距离，学习出样本之间的有效信息，提高算 法的聚类性能。 对于数据集 ｗｄｂｃ 和 ｓｏｎａｒ，表 ２ 的 实验结果显示了混合距离的有效性。 表 ２ 聚类算法性能 Ｔａｂｌｅ ２ Ｔｈｅ ｐｅｒｆｏｒｍａｎｃｅ ｏｆ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ 算法 ｂｒｅａｓｔ ｗｄｂｃ ｓｏｎａｒ ｖｅｈｉｃｌｅ ｗａｖｅｆｏｒｍ ＲＩ ＮＭＩ ＲＩ ＮＭＩ ＲＩ ＮＭＩ ＲＩ ＮＭＩ ＲＩ ＮＭＩ ＨＲ⁃ＦＣＭ ０．８８６ ９ ０．６７２ ０ ０．８５１ １ ０．５９４ ２ ０．５０８ ８ ０．０１７ １ ０．６６１ ６ ０．１７０ ９ ０．６６４ ４ ０．３４９ ０ ＦＣＭ ０．５１９ ９ ０．００４ ５ ０．７５０ ４ ０．４６７ ２ ０．５０３ ６ ０．００９ １ ０．６５０ ６ ０．１８０ ２ ０．６６０ ０ ０．３２０ ９ Ｋ⁃ｍｅａｎｓ ０．５２０ ６ ０．００４ ７ ０．７５０ ４ ０．４６７ ２ ０．５０３ ２ ０．６４３ ０ ０．６５２ ３ ０．１８６ ８ ０．６６７ ３ ０．３６２ ２ Ｋ⁃ｍｅｄｏｉｄｓ ０．５２０ ６ ０．００４ ７ ０．７７０ ７ ０．４９９ ９ ０．５０２ ２ ０．００７ １ ０．６５０ ９ ０．１８６ ６ ０．６７０ １ ０．３６８ １ ·４５４· 智 能 系 统 学 报 第 １２ 卷