第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-)。在有监督距离学习的方法中，需第 １２ 卷第 ４ 期 智 能 系 统 学 报 Ｖｏｌ．１２ №．４ ２０１７ 年 ８ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ａｕｇ． ２０１７ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ．２０１６０７０１９ 网络出版地址：ｈｔｔｐ： ／ ／ ｋｎｓ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ｔｐ．２０１７０４０７．１７３４．００４．ｈｔｍｌ 基于混合距离学习的鲁棒的模糊 Ｃ 均值聚类算法 卞则康，王士同 （江南大学 数字媒体学院，江苏 无锡 ２１４１２２） 摘 要：距离度量对模糊聚类算法 ＦＣＭ 的聚类结果有关键性的影响。 实际应用中存在这样一种场景，聚类的数据集 中存在着一定量的带标签的成对约束集合的辅助信息。 为了充分利用这些辅助信息，首先提出了一种基于混合距 离学习方法，它能利用这样的辅助信息来学习出数据集合的距离度量公式。 然后，提出了一种基于混合距离学习的 鲁棒的模糊 Ｃ 均值聚类算法（ＨＲ⁃ＦＣＭ 算法），它是一种半监督的聚类算法。 算法 ＨＲ⁃ＦＣＭ 既保留了 ＧＩＦＰ⁃ＦＣＭ （Ｇｅｎｅｒａｌｉｚｅｄ ＦＣＭ ａｌｇｏｒｉｔｈｍ ｗｉｔｈ ｉｍｐｒｏｖｅｄ ｆｕｚｚｙ ｐａｒｔｉｔｉｏｎｓ）算法的鲁棒性等性能，也因为所采用更为合适的距离度量而 具有更好的聚类性能。 实验结果证明了所提算法的有效性。 关键词：距离度量；ＦＣＭ 聚类算法；成对约束；辅助信息；混合距离；半监督；ＧＩＦＰ⁃ＦＣＭ；鲁棒性 中图分类号：ＴＰ１８１ 文献标志码：Ａ 文章编号：１６７３－４７８５（２０１７）０４－０４５０－０９ 中文引用格式：卞则康，王士同．基于混合距离学习的鲁棒的模糊 Ｃ 均值聚类算法［Ｊ］． 智能系统学报， ２０１７， １２（４）： ４５０－４５８． 英文引用格式：ＢＩＡＮ Ｚｅｋａｎｇ， ＷＡＮＧ Ｓｈｉｔｏｎｇ． Ｒｏｂｕｓｔ ＦＣＭ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｈｙｂｒｉｄ⁃ｄｉｓｔａｎｃｅ ｌｅａｒｎｉｎｇ ［ Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， ２０１７， １２（４）： ４５０－４５８． Ｒｏｂｕｓｔ ＦＣＭ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｈｙｂｒｉｄ⁃ｄｉｓｔａｎｃｅ ｌｅａｒｎｉｎｇ ＢＩＡＮ Ｚｅｋａｎｇ， ＷＡＮＧ Ｓｈｉｔｏｎｇ （Ｓｃｈｏｏｌ ｏｆ Ｄｉｇｉｔａｌ Ｍｅｄｉａ， Ｊｉａｎｇｎａｎ Ｕｎｉｖｅｒｓｉｔｙ， Ｗｕｘｉ ２１４１２２， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅ ｄｉｓｔａｎｃｅ ｍｅｔｒｉｃ ｐｌａｙｓ ａ ｖｉｔａｌ ｒｏｌｅ ｉｎ ｔｈｅ ｆｕｚｚｙ Ｃ⁃ｍｅａｎｓ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ． Ｉｎ ａｃｔｕａｌ ａｐｐｌｉｃａｔｉｏｎｓ， ｔｈｅｒｅ ｉｓ ａ ｐｒａｃｔｉｃａｌ ｓｃｅｎａｒｉｏ ｉｎ ｗｈｉｃｈ ｔｈｅ ｃｌｕｓｔｅｒｅｄ ｄａｔａ ｈａｖｅ ａ ｃｅｒｔａｉｎ ａｍｏｕｎｔ ｏｆ ｓｉｄｅ ｉｎｆｏｒｍａｔｉｏｎ， ｓｕｃｈ ａｓ ｐａｉｒｗｉｓｅ ｃｏｎｓｔｒａｉｎｔｓ ｗｉｔｈ ｌａｂｅｌｓ． Ｔｏ ｓｕｆｆｉｃｉｅｎｔｌｙ ｕｔｉｌｉｚｅ ｔｈｉｓ ｓｉｄｅ ｉｎｆｏｒｍａｔｉｏｎ， ｆｉｒｓｔ， ｗｅ ｐｒｏｐｏｓｅ ａ ｌｅａｒｎｉｎｇ ｍｅｔｈｏｄ ｂａｓｅｄ ｏｎ ｈｙｂｒｉｄ ｄｉｓｔａｎｃｅ， ｉｎ ｗｈｉｃｈ ｓｉｄｅ ｉｎｆｏｒｍａｔｉｏｎ ｃａｎ ｂｅ ｕｔｉｌｉｚｅｄ ｔｏ ａｔｔａｉｎ ａ ｄｉｓｔａｎｃｅ ｍｅｔｒｉｃ ｆｏｒｍｕｌａ ｆｏｒ ｔｈｅ ｄａｔａ ｓｅｔ． Ｎｅｘｔ， ｗｅ ｐｒｏｐｏｓｅ ａ ｒｏｂｕｓｔ ｆｕｚｚｙ Ｃ⁃ｍｅａｎｓ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ （ＨＲ⁃ＦＣＭ ａｌｇｏｒｉｔｈｍ） ｂａｓｅｄ ｏｎ ｈｙｂｒｉｄ⁃ｄｉｓｔａｎｃｅ ｌｅａｒｎｉｎｇ， ｗｈｉｃｈ ｉｓ ｓｅｍｉ⁃ｓｕｐｅｒｖｉｓｅｄ． Ｔｈｅ ＨＲ⁃ＦＣＭ ｉｎｈｅｒｉｔｓ ｔｈｅ ｒｏｂｕｓｔｎｅｓｓ ｏｆ ｔｈｅ ＧＩＦＰ⁃ＦＣＭ （ｇｅｎｅｒａｌｉｚｅｄ ＦＣＭ ａｌｇｏｒｉｔｈｍ ｗｉｔｈ ｉｍｐｒｏｖｅｄ ｆｕｚｚｙ ｐａｒｔｉｔｉｏｎｓ） ａｎｄ ｈａｓ ｂｅｔｔｅｒ ｃｌｕｓｔｅｒｉｎｇ ｐｅｒｆｏｒｍａｎｃｅ ｄｕｅ ｔｏ ｔｈｅ ｍｏｒｅ ａｐｐｒｏｐｒｉａｔｅ ｄｉｓｔａｎｃｅ ｍｅｔｒｉｃ． Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｃｏｎｆｉｒｍ ｔｈｅ ｅｆｆｅｃｔｉｖｅｎｅｓｓ ｏｆ ｔｈｅ ｐｒｏｐｏｓｅｄ ａｌｇｏｒｉｔｈｍ． Ｋｅｙｗｏｒｄｓ： ｄｉｓｔａｎｃｅ ｍｅｔｒｉｃ； ＦＣＭ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ； ｐａｉｒｗｉｓｅ ｃｏｎｓｔｒａｉｎｔｓ；ｓｉｄｅ ｉｎｆｏｒｍａｔｉｏｎ； ｈｙｂｒｉｄ ｄｉｓｔａｎｃｅ； ｓｅｍｉ⁃ｓｕｐｅｒｖｉｓｅｄ； ＧＩＦＰ⁃ＦＣＭ； ｒｏｂｕｓｔｎｅｓｓ 收稿日期：２０１６－０７－２３． 网络出版日期：２０１７－０４－０７． 基金项目：国家自然科学基金项目（６１２７２２１０）． 通信作者：卞则康． Ｅ⁃ｍａｉｌ：ｂｉａｎｚｅｋａｎｇ＠ １６３．ｃｏｍ． 聚类分析作为一种重要的数据处理技术已经 被广泛地应用到各种领域，如模式识别、数据挖掘 等。 在聚类分析中，需要根据数据点之间的相似或 相异程度，对数据点进行区分和分类。 因此对于不 同的数据集，选择合适的距离度量方式对算法的聚 类性能有重要的影响［１］ 。 欧式距离是较为常用的 距离度量方式，但其具有以下不足：１） 采用欧式距 离的方法通常是假设所有变量都是不相关的，并且 数据所有维度的方差都为 １，所有变量的协方差为 ０ ［２］ ；２）欧式距离仅仅适用于特征空间中的超球结 构，对于其他结构的数据集不太理想；３） 欧式距离 对噪声 比 较 敏 感， 聚 类 结 果 容 易 受 到 噪 声 的 干 扰［３］ 。 因此，欧式距离在实际应用中受到了限制。 针对这些问题，近年来提出了多种距离学习的 方法，根据在距离学习过程中是否有先验的训练样 本，距离学习可以分为有监督距离学习［４－６］ 和无监 督距离学习［７－８］ 。 在有监督距离学习的方法中，需