第10卷第6期 智能系统学报 Vol.10 No.6 2015年12月 CAAI Transactions on Intelligent Systems Dee.2015 D0L:10.11992/is.201504027 网络出版地址：http://www.cnki.net/kcms/detail/23.1538.tp.20151111.1633.006.html 基于最大间隔理论的组合距离学习算法 郭瑛洁，王士同，许小龙 (江南大学数字媒体学院，江苏无锡214000) 摘要：从已知数据集中学习距离度量在许多机器学习应用中都起着重要作用。传统的距离学习方法通常假定目 标距离函数为马氏距离的形式，这使得学习出的距离度量在应用上具有局限性。提出了一种新的距离学习方法，将 目标距离函数表示为若干候选距离的线性组合，依据最大间隔理论利用数据集的边信息学习得到组合距离中各距 离分量的权值，从而得到新的距离度量。通过该距离度量在模糊C均值聚类算法中的表现来对其进行评价。在UCI 数据集上，与其他已有的距离学习算法的对比实验结果证明了该文算法的有效性。 关键词：距离学习：组合距离：最大间隔：F℃M:模糊聚类；聚类算法；距离：学习算法 中图分类号：TP181文献标志码：A文章编号：1673-4785(2015)06-0843-08 中文引用格式：郭瑛洁，王士同，许小龙.基于最大间隔理论的组合距离学习算法[J].智能系统学报，2015,10(6)：843-850. 英文引用格式：GUO Yingjie,WANG Shitong,XU Xiaolong.Learning a linear combination of distances based on the maximum: margin theory[J].CAAI Transactions on Intelligent Systems,2015,10(6):843-850. Learning a linear combination of distances based on the maximum-margin theory GUO Yingjie,WANG Shitong,XU Xiaolong (School of Digital Media,Jiangnan University,Wuxi 214000,China) Abstract:Learning a distance metric from given training samples is a crucial aspect of many machine learning tasks. Conventional distance metric learning approaches often assume the target distance function to be represented in the form of Mahalanobis distance,and the metric has limitations for this application.This paper proposes a new metric learning approach in which the target distance function is represented as a linear combination of several candidate distance metrics.This method obtains a new distance metric by learning weights from side information according to the maximum-margin theory.The new distance function is applied to fuzzy C-means clustering for evaluation.The experiments were performed using UCI data,and a comparison of the results with those of other approaches reveals the advantages of the proposed technique. Keywords:metric learning;hybrid distance metric;maximum-margin theory;fuzzy C-means;fuzzy clustering; clustering algorithm;metric;learning algorithm 如何表示2点之间的距离是模式识别中的基础 特征空间中超球结构的数据集，对于超立方体结构、 问题。一个好的距离度量能够根据数据的结构与分 超椭球结构的数据集效果不太理想四。除了欧氏 布适用于不同的应用。欧氏距离是众多数据挖掘应 距离，余弦距离是另一个应用广泛的距离度量。尽 用中使用最多的距离度量，但是欧氏距离仅适用于 管余弦距离在文本检索中有优秀的表现，但是其预 先假设了数据集每一维度都是等权重的[☒】，这一特 收稿日期：2015-04-19.网络出版日期：2015-11-11. 性显然限制了余弦距离的应用范围。因此，欧式距 基金项目：国家自然科学基金资助项目(61272210)：江苏省自然科学基 金资助项目(BK2011417,BK2011003). 离和余弦距离在实际应用中都不是最理想的选择。 通信作者：郭瑛洁.E-mail:ying_dm@163.com. 从训练样本中学习出合适的距离度量是近年来第 １０ 卷第 ６ 期 智 能 系 统 学 报 Ｖｏｌ．１０ №．６ ２０１５ 年 １２ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｄｅｃ． ２０１５ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ．２０１５０４０２７ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ｔｐ．２０１５１１１１．１６３３．００６．ｈｔｍｌ 基于最大间隔理论的组合距离学习算法 郭瑛洁，王士同，许小龙 （江南大学 数字媒体学院 ，江苏 无锡 ２１４０００） 摘 要：从已知数据集中学习距离度量在许多机器学习应用中都起着重要作用。 传统的距离学习方法通常假定目 标距离函数为马氏距离的形式，这使得学习出的距离度量在应用上具有局限性。 提出了一种新的距离学习方法，将 目标距离函数表示为若干候选距离的线性组合，依据最大间隔理论利用数据集的边信息学习得到组合距离中各距 离分量的权值，从而得到新的距离度量。 通过该距离度量在模糊 Ｃ 均值聚类算法中的表现来对其进行评价。 在 ＵＣＩ 数据集上，与其他已有的距离学习算法的对比实验结果证明了该文算法的有效性。 关键词：距离学习；组合距离；最大间隔；ＦＣＭ；模糊聚类；聚类算法；距离；学习算法 中图分类号：ＴＰ１８１ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１５）０６⁃０８４３⁃０８ 中文引用格式：郭瑛洁，王士同，许小龙． 基于最大间隔理论的组合距离学习算法［Ｊ］． 智能系统学报， ２０１５， １０（６）： ８４３⁃８５０． 英文引用格式：ＧＵＯ Ｙｉｎｇｊｉｅ， ＷＡＮＧ Ｓｈｉｔｏｎｇ， ＸＵ Ｘｉａｏｌｏｎｇ． Ｌｅａｒｎｉｎｇ ａ ｌｉｎｅａｒ ｃｏｍｂｉｎａｔｉｏｎ ｏｆ ｄｉｓｔａｎｃｅｓ ｂａｓｅｄ ｏｎ ｔｈｅ ｍａｘｉｍｕｍ⁃ ｍａｒｇｉｎ ｔｈｅｏｒｙ［Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１５， １０（６）： ８４３⁃８５０． Ｌｅａｒｎｉｎｇ ａ ｌｉｎｅａｒ ｃｏｍｂｉｎａｔｉｏｎ ｏｆ ｄｉｓｔａｎｃｅｓ ｂａｓｅｄ ｏｎ ｔｈｅ ｍａｘｉｍｕｍ⁃ｍａｒｇｉｎ ｔｈｅｏｒｙ ＧＵＯ Ｙｉｎｇｊｉｅ， ＷＡＮＧ Ｓｈｉｔｏｎｇ， ＸＵ Ｘｉａｏｌｏｎｇ （Ｓｃｈｏｏｌ ｏｆ Ｄｉｇｉｔａｌ Ｍｅｄｉａ， Ｊｉａｎｇｎａｎ Ｕｎｉｖｅｒｓｉｔｙ， Ｗｕｘｉ ２１４０００， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｌｅａｒｎｉｎｇ ａ ｄｉｓｔａｎｃｅ ｍｅｔｒｉｃ ｆｒｏｍ ｇｉｖｅｎ ｔｒａｉｎｉｎｇ ｓａｍｐｌｅｓ ｉｓ ａ ｃｒｕｃｉａｌ ａｓｐｅｃｔ ｏｆ ｍａｎｙ ｍａｃｈｉｎｅ ｌｅａｒｎｉｎｇ ｔａｓｋｓ． Ｃｏｎｖｅｎｔｉｏｎａｌ ｄｉｓｔａｎｃｅ ｍｅｔｒｉｃ ｌｅａｒｎｉｎｇ ａｐｐｒｏａｃｈｅｓ ｏｆｔｅｎ ａｓｓｕｍｅ ｔｈｅ ｔａｒｇｅｔ ｄｉｓｔａｎｃｅ ｆｕｎｃｔｉｏｎ ｔｏ ｂｅ ｒｅｐｒｅｓｅｎｔｅｄ ｉｎ ｔｈｅ ｆｏｒｍ ｏｆ Ｍａｈａｌａｎｏｂｉｓ ｄｉｓｔａｎｃｅ， ａｎｄ ｔｈｅ ｍｅｔｒｉｃ ｈａｓ ｌｉｍｉｔａｔｉｏｎｓ ｆｏｒ ｔｈｉｓ ａｐｐｌｉｃａｔｉｏｎ． Ｔｈｉｓ ｐａｐｅｒ ｐｒｏｐｏｓｅｓ ａ ｎｅｗ ｍｅｔｒｉｃ ｌｅａｒｎｉｎｇ ａｐｐｒｏａｃｈ ｉｎ ｗｈｉｃｈ ｔｈｅ ｔａｒｇｅｔ ｄｉｓｔａｎｃｅ ｆｕｎｃｔｉｏｎ ｉｓ ｒｅｐｒｅｓｅｎｔｅｄ ａｓ ａ ｌｉｎｅａｒ ｃｏｍｂｉｎａｔｉｏｎ ｏｆ ｓｅｖｅｒａｌ ｃａｎｄｉｄａｔｅ ｄｉｓｔａｎｃｅ ｍｅｔｒｉｃｓ． Ｔｈｉｓ ｍｅｔｈｏｄ ｏｂｔａｉｎｓ ａ ｎｅｗ ｄｉｓｔａｎｃｅ ｍｅｔｒｉｃ ｂｙ ｌｅａｒｎｉｎｇ ｗｅｉｇｈｔｓ ｆｒｏｍ ｓｉｄｅ ｉｎｆｏｒｍａｔｉｏｎ ａｃｃｏｒｄｉｎｇ ｔｏ ｔｈｅ ｍａｘｉｍｕｍ⁃ｍａｒｇｉｎ ｔｈｅｏｒｙ． Ｔｈｅ ｎｅｗ ｄｉｓｔａｎｃｅ ｆｕｎｃｔｉｏｎ ｉｓ ａｐｐｌｉｅｄ ｔｏ ｆｕｚｚｙ Ｃ⁃ｍｅａｎｓ ｃｌｕｓｔｅｒｉｎｇ ｆｏｒ ｅｖａｌｕａｔｉｏｎ． Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔｓ ｗｅｒｅ ｐｅｒｆｏｒｍｅｄ ｕｓｉｎｇ ＵＣＩ ｄａｔａ， ａｎｄ ａ ｃｏｍｐａｒｉｓｏｎ ｏｆ ｔｈｅ ｒｅｓｕｌｔｓ ｗｉｔｈ ｔｈｏｓｅ ｏｆ ｏｔｈｅｒ ａｐｐｒｏａｃｈｅｓ ｒｅｖｅａｌｓ ｔｈｅ ａｄｖａｎｔａｇｅｓ ｏｆ ｔｈｅ ｐｒｏｐｏｓｅｄ ｔｅｃｈｎｉｑｕｅ． Ｋｅｙｗｏｒｄｓ： ｍｅｔｒｉｃ ｌｅａｒｎｉｎｇ； ｈｙｂｒｉｄ ｄｉｓｔａｎｃｅ ｍｅｔｒｉｃ； ｍａｘｉｍｕｍ⁃ｍａｒｇｉｎ ｔｈｅｏｒｙ； ｆｕｚｚｙ Ｃ⁃ｍｅａｎｓ； ｆｕｚｚｙ ｃｌｕｓｔｅｒｉｎｇ； ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ； ｍｅｔｒｉｃ； ｌｅａｒｎｉｎｇ ａｌｇｏｒｉｔｈｍ 收稿日期：２０１５⁃０４⁃１９． 网络出版日期：２０１５⁃１１⁃１１． 基金项目：国家自然科学基金资助项目（６１２７２２１０）；江苏省自然科学基 金资助项目（ＢＫ２０１１４１７， ＢＫ２０１１００３）． 通信作者：郭瑛洁． Ｅ⁃ｍａｉｌ：ｙｉｎｇ＿ｄｍ＠ １６３．ｃｏｍ． 如何表示 ２ 点之间的距离是模式识别中的基础 问题。 一个好的距离度量能够根据数据的结构与分 布适用于不同的应用。 欧氏距离是众多数据挖掘应 用中使用最多的距离度量，但是欧氏距离仅适用于 特征空间中超球结构的数据集，对于超立方体结构、 超椭球结构的数据集效果不太理想［１］ 。 除了欧氏 距离，余弦距离是另一个应用广泛的距离度量。 尽 管余弦距离在文本检索中有优秀的表现，但是其预 先假设了数据集每一维度都是等权重的［２］ ，这一特 性显然限制了余弦距离的应用范围。 因此，欧式距 离和余弦距离在实际应用中都不是最理想的选择。 从训练样本中学习出合适的距离度量是近年来