第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. 从训练样本中学习出合适的距离度量是近年来
第 １０ 卷第 ６ 期 智 能 系 统 学 报 Ｖｏｌ．１０ №．６ ２０１５ 年 １２ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｄｅｃ． ２０１５ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ．２０１５０４０２７ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ｔｐ．２０１５１１１１．１６３３．００６．ｈｔｍｌ 基于最大间隔理论的组合距离学习算法 郭瑛洁，王士同，许小龙 （江南大学 数字媒体学院 ，江苏 无锡 ２１４０００） 摘 要：从已知数据集中学习距离度量在许多机器学习应用中都起着重要作用。 传统的距离学习方法通常假定目 标距离函数为马氏距离的形式，这使得学习出的距离度量在应用上具有局限性。 提出了一种新的距离学习方法，将 目标距离函数表示为若干候选距离的线性组合，依据最大间隔理论利用数据集的边信息学习得到组合距离中各距 离分量的权值，从而得到新的距离度量。 通过该距离度量在模糊 Ｃ 均值聚类算法中的表现来对其进行评价。 在 ＵＣＩ 数据集上，与其他已有的距离学习算法的对比实验结果证明了该文算法的有效性。 关键词：距离学习；组合距离；最大间隔；ＦＣＭ；模糊聚类；聚类算法；距离；学习算法 中图分类号：ＴＰ１８１ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１５）０６⁃０８４３⁃０８ 中文引用格式：郭瑛洁，王士同，许小龙． 基于最大间隔理论的组合距离学习算法［Ｊ］． 智能系统学报， ２０１５， １０（６）： ８４３⁃８５０． 英文引用格式：ＧＵＯ Ｙｉｎｇｊｉｅ， ＷＡＮＧ Ｓｈｉｔｏｎｇ， ＸＵ Ｘｉａｏｌｏｎｇ． Ｌｅａｒｎｉｎｇ ａ ｌｉｎｅａｒ ｃｏｍｂｉｎａｔｉｏｎ ｏｆ ｄｉｓｔａｎｃｅｓ ｂａｓｅｄ ｏｎ ｔｈｅ ｍａｘｉｍｕｍ⁃ ｍａｒｇｉｎ ｔｈｅｏｒｙ［Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１５， １０（６）： ８４３⁃８５０． Ｌｅａｒｎｉｎｇ ａ ｌｉｎｅａｒ ｃｏｍｂｉｎａｔｉｏｎ ｏｆ ｄｉｓｔａｎｃｅｓ ｂａｓｅｄ ｏｎ ｔｈｅ ｍａｘｉｍｕｍ⁃ｍａｒｇｉｎ ｔｈｅｏｒｙ ＧＵＯ Ｙｉｎｇｊｉｅ， ＷＡＮＧ Ｓｈｉｔｏｎｇ， ＸＵ Ｘｉａｏｌｏｎｇ （Ｓｃｈｏｏｌ ｏｆ Ｄｉｇｉｔａｌ Ｍｅｄｉａ， Ｊｉａｎｇｎａｎ Ｕｎｉｖｅｒｓｉｔｙ， Ｗｕｘｉ ２１４０００， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｌｅａｒｎｉｎｇ ａ ｄｉｓｔａｎｃｅ ｍｅｔｒｉｃ ｆｒｏｍ ｇｉｖｅｎ ｔｒａｉｎｉｎｇ ｓａｍｐｌｅｓ ｉｓ ａ ｃｒｕｃｉａｌ ａｓｐｅｃｔ ｏｆ ｍａｎｙ ｍａｃｈｉｎｅ ｌｅａｒｎｉｎｇ ｔａｓｋｓ． Ｃｏｎｖｅｎｔｉｏｎａｌ ｄｉｓｔａｎｃｅ ｍｅｔｒｉｃ ｌｅａｒｎｉｎｇ ａｐｐｒｏａｃｈｅｓ ｏｆｔｅｎ ａｓｓｕｍｅ ｔｈｅ ｔａｒｇｅｔ ｄｉｓｔａｎｃｅ ｆｕｎｃｔｉｏｎ ｔｏ ｂｅ ｒｅｐｒｅｓｅｎｔｅｄ ｉｎ ｔｈｅ ｆｏｒｍ ｏｆ Ｍａｈａｌａｎｏｂｉｓ ｄｉｓｔａｎｃｅ， ａｎｄ ｔｈｅ ｍｅｔｒｉｃ ｈａｓ ｌｉｍｉｔａｔｉｏｎｓ ｆｏｒ ｔｈｉｓ ａｐｐｌｉｃａｔｉｏｎ． Ｔｈｉｓ ｐａｐｅｒ ｐｒｏｐｏｓｅｓ ａ ｎｅｗ ｍｅｔｒｉｃ ｌｅａｒｎｉｎｇ ａｐｐｒｏａｃｈ ｉｎ ｗｈｉｃｈ ｔｈｅ ｔａｒｇｅｔ ｄｉｓｔａｎｃｅ ｆｕｎｃｔｉｏｎ ｉｓ ｒｅｐｒｅｓｅｎｔｅｄ ａｓ ａ ｌｉｎｅａｒ ｃｏｍｂｉｎａｔｉｏｎ ｏｆ ｓｅｖｅｒａｌ ｃａｎｄｉｄａｔｅ ｄｉｓｔａｎｃｅ ｍｅｔｒｉｃｓ． Ｔｈｉｓ ｍｅｔｈｏｄ ｏｂｔａｉｎｓ ａ ｎｅｗ ｄｉｓｔａｎｃｅ ｍｅｔｒｉｃ ｂｙ ｌｅａｒｎｉｎｇ ｗｅｉｇｈｔｓ ｆｒｏｍ ｓｉｄｅ ｉｎｆｏｒｍａｔｉｏｎ ａｃｃｏｒｄｉｎｇ ｔｏ ｔｈｅ ｍａｘｉｍｕｍ⁃ｍａｒｇｉｎ ｔｈｅｏｒｙ． Ｔｈｅ ｎｅｗ ｄｉｓｔａｎｃｅ ｆｕｎｃｔｉｏｎ ｉｓ ａｐｐｌｉｅｄ ｔｏ ｆｕｚｚｙ Ｃ⁃ｍｅａｎｓ ｃｌｕｓｔｅｒｉｎｇ ｆｏｒ ｅｖａｌｕａｔｉｏｎ． Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔｓ ｗｅｒｅ ｐｅｒｆｏｒｍｅｄ ｕｓｉｎｇ ＵＣＩ ｄａｔａ， ａｎｄ ａ ｃｏｍｐａｒｉｓｏｎ ｏｆ ｔｈｅ ｒｅｓｕｌｔｓ ｗｉｔｈ ｔｈｏｓｅ ｏｆ ｏｔｈｅｒ ａｐｐｒｏａｃｈｅｓ ｒｅｖｅａｌｓ ｔｈｅ ａｄｖａｎｔａｇｅｓ ｏｆ ｔｈｅ ｐｒｏｐｏｓｅｄ ｔｅｃｈｎｉｑｕｅ． Ｋｅｙｗｏｒｄｓ： ｍｅｔｒｉｃ ｌｅａｒｎｉｎｇ； ｈｙｂｒｉｄ ｄｉｓｔａｎｃｅ ｍｅｔｒｉｃ； ｍａｘｉｍｕｍ⁃ｍａｒｇｉｎ ｔｈｅｏｒｙ； ｆｕｚｚｙ Ｃ⁃ｍｅａｎｓ； ｆｕｚｚｙ ｃｌｕｓｔｅｒｉｎｇ； ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ； ｍｅｔｒｉｃ； ｌｅａｒｎｉｎｇ ａｌｇｏｒｉｔｈｍ 收稿日期：２０１５⁃０４⁃１９． 网络出版日期：２０１５⁃１１⁃１１． 基金项目：国家自然科学基金资助项目（６１２７２２１０）；江苏省自然科学基 金资助项目（ＢＫ２０１１４１７， ＢＫ２０１１００３）． 通信作者：郭瑛洁． Ｅ⁃ｍａｉｌ：ｙｉｎｇ＿ｄｍ＠ １６３．ｃｏｍ． 如何表示 ２ 点之间的距离是模式识别中的基础 问题。 一个好的距离度量能够根据数据的结构与分 布适用于不同的应用。 欧氏距离是众多数据挖掘应 用中使用最多的距离度量，但是欧氏距离仅适用于 特征空间中超球结构的数据集，对于超立方体结构、 超椭球结构的数据集效果不太理想［１］ 。 除了欧氏 距离，余弦距离是另一个应用广泛的距离度量。 尽 管余弦距离在文本检索中有优秀的表现，但是其预 先假设了数据集每一维度都是等权重的［２］ ，这一特 性显然限制了余弦距离的应用范围。 因此，欧式距 离和余弦距离在实际应用中都不是最理想的选择。 从训练样本中学习出合适的距离度量是近年来
·844 智能系统学报 第10卷 的研究热点，它对于提高聚类和分类效果有着重要 的影响。一般的距离学习方法都是首先假定一个距 s..0=1. i=1 离函数模型并进行求解，其中大部分的距离函数假 0≤ω：≤1，i=1,2,…,p 定在马氏距离定义的框架之下，即对于2点x、y,使 式中：D(x。,x6)表示数据点x。到数据点x。之间的 用距离公式d(x,y)=(x-y)A(x-y),其中A为 距离，它由p个距离分量组成，d,(x,x6)是其第i 所要学习的距离矩阵。比如文献[3]中通过使相似 个距离分量，w:是第i个距离分量所对应的权值。 样本之间距离减小学习了一个全局距离度量：区分 ω，需要满足各个分量权值均为正且和为1的条件。 成分分析(DCA)[4)通过最小化相似样本之间距离 在距离分量的选择上，除了经典的欧式距离之 的同时最大化不相似样本之间的距离来学习距离矩 外，本文选择了若干含有数据维度方差的距离分量 阵：近邻成分分析(NCA)[)通过最优化最近邻分类 (如：dxx)=(x。-x)'乙(x-x),其中B 器的精度去学习马氏距离度量：最大边界近邻分类 Bo 方法(LMNN)[在NCA的框架下拓展了最大边界 为常数，I为单位矩阵，σ为数据点之间的标准差) 的目标，但是学习的目标仍然是得到一个马氏距离。 以保留数据各特征分量上的特征。但是这些距离均 当马氏距离中的矩阵A取单位矩阵I时，则马氏距 为马氏距离定义框架下的距离度量，对其进行线性 离表示欧氏距离。因此，本质上来说，以马氏距离为 组合后，得到的距离函数仍为马氏距离形式。因此 目标学习得到的新距离是欧式距离的线性变换，其 根据Wu等提出的新距离8】，本文给出了若干形如 无法准确地度量所有样本之间的距离。 d(x。,x。)=1-exp(-B‖x.-x‖2)的距离分量 有别于传统的距离学习方法，本文提出的距离 进行组合，其中B为常数，这些距离均为非线性的距 学习方法并没有将学习目标单纯设定为马氏距离， 离度量，通过组合可以形成非线性的距离函数以克 而是学习由若干候选距离线性组合而成的新距离。 服马氏距离的缺点。 基于最大间隔理论建立目标函数，利用数据的边信 2基于最大间隔理论的距离学习 息通过对目标函数进行优化从而得到组合距离中的 权重进而得到新的距离度量。对于候选距离的选择 2.1距离学习方法 也不仅仅局限于马氏距离，本文选择了其他形式的 本文所提出的距离学习算法将利用数据集的边 距离度量进行组合，以扩大距离度量的适用范围。 信息进行学习，而边信息通常以成对约束的形式表 现。因此，本文以成对约束的集合作为训练集并表 1 组合距离表示 示为D={(x,x,y),k=1,2,…,n},其中n为成 为了更好地表示数据点之间的距离，在距离函 对约束的对数。D中每一对成对约束(x,x,y)都 数中引入权重来强化有积极作用的部分，削减冗余 是一个包含三个元素的元组，其中x和x是被表示 的部分，已经成为一种常用的方法。在之前的方法 为d维向量的样本点，y是表示样本点x和x之间 中，研究者往往使用特征加权距离的方法)来改进 关系的类标。当x和x为同一类的样本点时，y 聚类算法，特征加权距离的计算表达式为 为正（如：y=+1);反之，y为负（如：yk=-1)。 使用X=(x1,x2,…,xx)来表示D中出现的所有的 0(x,y）= ∑(-y4)2,a>1 训练样本点，其中N表示样本点的个数。 h= 式中： 统计学习中常用的经验风险最小化并不能保证 [x1x2… xalT,y [y2·y]T为特征空间R中的任意2点， 良好的泛化性能，因此间隔理论[9]就伴随着过拟合 的问题研究被提出，并逐渐成为机器学习领域中的 仙，为特征权重且满足0，=1。 一个重要评价标准。本文依据最大间隔理论并受 h=1 受特征加权距离的启发，引入权值将距离函数 L2-SVM方法[o]和文献[2]的启发，构建目标函数 改写为若干候选距离的线性组合，将特征加权改为 如式(2)： 距离加权，从而强化对某一数据集有更好度量效果 min/= +c +B2-p 的距离分量。 21 k=1 本文通过以下线性组合来表示数据集中的距离 t(∑u,d(xx)-B)≥p- (2) 度量： D(xa,6)= (1) 20=10≤a≤1i=1,2p 三1
的研究热点，它对于提高聚类和分类效果有着重要 的影响。 一般的距离学习方法都是首先假定一个距 离函数模型并进行求解，其中大部分的距离函数假 定在马氏距离定义的框架之下，即对于 ２ 点 ｘ、ｙ ，使 用距离公式 ｄ（ｘ，ｙ） ＝ （ｘ － ｙ） ＴＡ（ｘ － ｙ） ，其中 Ａ 为 所要学习的距离矩阵。 比如文献［３］中通过使相似 样本之间距离减小学习了一个全局距离度量；区分 成分分析（ＤＣＡ） ［４］ 通过最小化相似样本之间距离 的同时最大化不相似样本之间的距离来学习距离矩 阵；近邻成分分析（ＮＣＡ） ［５］ 通过最优化最近邻分类 器的精度去学习马氏距离度量；最大边界近邻分类 方法（ＬＭＮＮ） ［６］ 在 ＮＣＡ 的框架下拓展了最大边界 的目标，但是学习的目标仍然是得到一个马氏距离。 当马氏距离中的矩阵 Ａ 取单位矩阵 Ｉ 时，则马氏距 离表示欧氏距离。 因此，本质上来说，以马氏距离为 目标学习得到的新距离是欧式距离的线性变换，其 无法准确地度量所有样本之间的距离。 有别于传统的距离学习方法，本文提出的距离 学习方法并没有将学习目标单纯设定为马氏距离， 而是学习由若干候选距离线性组合而成的新距离。 基于最大间隔理论建立目标函数，利用数据的边信 息通过对目标函数进行优化从而得到组合距离中的 权重进而得到新的距离度量。 对于候选距离的选择 也不仅仅局限于马氏距离，本文选择了其他形式的 距离度量进行组合，以扩大距离度量的适用范围。 １ 组合距离表示 为了更好地表示数据点之间的距离，在距离函 数中引入权重来强化有积极作用的部分，削减冗余 的部分，已经成为一种常用的方法。 在之前的方法 中，研究者往往使用特征加权距离的方法［７］ 来改进 聚类算法，特征加权距离的计算表达式为 ｗｄｉｓｔ（ｘ，ｙ） ＝ ∑ ｄ ｈ ＝ １ ω α ｈ （ｘｈ － ｙｈ ） ２ ，α ＞ １ 式 中： ｘ ＝ ｘ１ ｘ２ … ｘｄ [ ] Ｔ ，ｙ ＝ ｙ１ ｙ２ … ｙ [ ｄ ] Ｔ 为特征空间 Ｒ ｄ 中的任意 ２ 点， ωｈ 为特征权重且满足 ∑ ｄ ｈ ＝ １ ωｈ ＝１。 受特征加权距离的启发，引入权值将距离函数 改写为若干候选距离的线性组合，将特征加权改为 距离加权，从而强化对某一数据集有更好度量效果 的距离分量。 本文通过以下线性组合来表示数据集中的距离 度量： Ｄ（ｘａ ，ｘｂ） ＝ ∑ ｐ ｉ ＝ １ ωｉｄｉ（ｘａ ，ｘｂ） （１） ｓ．ｔ．∑ ｐ ｉ ＝ １ ωｉ ＝ １， ０ ≤ ωｉ ≤ １， ｉ ＝ １，２，…，ｐ 式中： Ｄ（ｘａ ，ｘｂ） 表示数据点 ｘａ 到数据点 ｘｂ 之间的 距离，它由 ｐ 个距离分量组成， ｄｉ（ ｘａ ， ｘｂ） 是其第 ｉ 个距离分量， ωｉ 是第 ｉ 个距离分量所对应的权值。 ωｉ 需要满足各个分量权值均为正且和为 １ 的条件。 在距离分量的选择上，除了经典的欧式距离之 外，本文选择了若干含有数据维度方差的距离分量 （如： ｄ（ｘａ ，ｘｂ） ＝ （ｘａ － ｘｂ） Ｔ Ｉ βσ ２ （ｘａ － ｘｂ） ，其中 β 为常数， Ｉ 为单位矩阵， σ 为数据点之间的标准差） 以保留数据各特征分量上的特征。 但是这些距离均 为马氏距离定义框架下的距离度量，对其进行线性 组合后，得到的距离函数仍为马氏距离形式。 因此， 根据 Ｗｕ 等提出的新距离［８］ ，本文给出了若干形如 ｄ（ｘａ ，ｘｂ） ＝ １ － ｅｘｐ（ － β ‖ ｘａ － ｘｂ‖２ ） 的距离分量 进行组合，其中 β 为常数，这些距离均为非线性的距 离度量，通过组合可以形成非线性的距离函数以克 服马氏距离的缺点。 ２ 基于最大间隔理论的距离学习 ２．１ 距离学习方法 本文所提出的距离学习算法将利用数据集的边 信息进行学习，而边信息通常以成对约束的形式表 现。 因此，本文以成对约束的集合作为训练集并表 示为 Ｄ ＝ ｘ ｋ ａ ，ｘ ｋ ｂ，ｙｋ { ( ) ，ｋ ＝ １，２，…，ｎ} ，其中 ｎ 为成 对约束的对数。 Ｄ 中每一对成对约束 ｘ ｋ ａ ，ｘ ｋ ｂ，ｙｋ ( ) 都 是一个包含三个元素的元组，其中 ｘ ｋ ａ 和 ｘ ｋ ｂ 是被表示 为 ｄ 维向量的样本点， ｙｋ 是表示样本点 ｘ ｋ ａ 和 ｘ ｋ ｂ 之间 关系的类标。 当 ｘ ｋ ａ 和 ｘ ｋ ｂ 为同一类的样本点时， ｙｋ 为正（如： ｙｋ ＝ ＋ １）；反之， ｙｋ 为负（如： ｙｋ ＝ － １）。 使用 Ｘ ＝ ｘ１ ，ｘ２ ，…，ｘＮ ( ) 来表示 Ｄ 中出现的所有的 训练样本点，其中 Ｎ 表示样本点的个数。 统计学习中常用的经验风险最小化并不能保证 良好的泛化性能，因此间隔理论［９ ］ 就伴随着过拟合 的问题研究被提出，并逐渐成为机器学习领域中的 一个重要评价标准。 本文依据最大间隔理论并受 Ｌ２⁃ＳＶＭ 方法［１０ ］和文献［２］ 的启发，构建目标函数 如式（２）： ｍｉｎＪ ＝ １ ２ ∑ ｐ ｉ ＝ １ ω ２ ｉ ＋ Ｃ∑ ｎ ｋ ＝ １ ξ ２ ｋ ＋ β ２ － θρ ｓ．ｔ．ｙｋ（∑ ｐ ｉ ＝ １ ωｉｄｉ（ｘ ｋ ａ ，ｘ ｋ ｂ） － β） ≥ ρ － ξｋ ∑ ｐ ｉ ＝ １ ωｉ ＝ １，０ ≤ ωｉ ≤ １，ｉ ＝ １，２，…，ｐ （２） ·８４４· 智 能 系 统 学 报 第 １０ 卷
第6期 郭瑛洁，等：基于最大间隔理论的组合距离学习算法 ·845· 式中：d,(x,x)表示第k对成对约束的第i个距离 将拉格朗日函数式(5)分别对ω：Bp、专、入求 分量，为了便于表示，本文在后续的介绍中将使用符 偏导，并令其等于0得到 号d来代替d,(x。,x)。此外，y为该约束对的类 aL 标，C为惩罚因子，C值大时对训练错误的惩罚增 =w:- dw, A04A=0 大，0为已知参数，B为阀值，最大间隔为P aL wⅡ =29- ar=0 在优化的过程中最大化p,最小化‖wⅡ2，并使训 aL =-9+∑a4=0 (5) 练误差专.最小化，其中k≥0。 ap =1 本文的目标是通过优化该目标函数求得距离分 aL 量的权值ω：，下面将具体介绍求解ω：的方法。为 a店 =2C吃k-a4=0 了求解上述优化问题，将它作为原始最优化问题，应 用拉格朗日对偶性，通过求解对偶问题得到原始问 1 名=0 题的最优解。接下来将介绍具体求解过程。 进而得到 首先，构建拉格朗日函数如式(3)： (6) k=1 =1 B= (7) 26=1 i=1 -名 =∑a4 (8) (3) k=1 Q: 式中：a=【a,a…a,】T、A均为拉格朗日乘子。 5:-2C (9) 如果此时考虑式(2)中ω：≥0的约束条件，并 (10) 将该条件加入拉格朗日函数，则得到 将式(6)代入式(10)得到 L'=L- 名m (11) 将该拉格朗日函数分别对ω：Bp、专：、入求偏 A=-文ad 导，并令其等于0得到 进而，将式(11)代入式(6)得到 aL' =w:- dw. 2d4-A-9,=0 k=1 aL' 将式(7)~(10)、(12)代入拉格朗日函数(3) aβ =2B- a=0 中，即得 k=1 aL' =-0+】 (4) ap 4=0 =1 aL' =2C54-ak=0 (名三ad)P- a店 OL' =1- 2(店42ax4)+ a入 2,=0 i= 显然由方程组(4)无法求得ω：，因此本文先暂 喜，京ax 时不考虑ω：≥0的约束条件，使用式(3)进行后续 即 的求解。 根据拉格朗日对偶性，原始问题的对偶问题是 (w,B,5,a,)=写 B,5 极大极小问题： max minL(w,B,5,a,入) .8,E 所以，需要先求L(w,B,专，x,入)对于ω、入的 极小值
式中： ｄｉ（ｘ ｋ ａ ，ｘ ｋ ｂ） 表示第 ｋ 对成对约束的第 ｉ 个距离 分量，为了便于表示，本文在后续的介绍中将使用符 号 ｄｉ．ｋ 来代替 ｄｉ（ｘ ｋ ａ ，ｘ ｋ ｂ） 。 此外， ｙｋ 为该约束对的类 标， Ｃ 为惩罚因子， Ｃ 值大时对训练错误的惩罚增 大， θ 为已知参数， β 为阈值，最大间隔为 ρ ‖ω‖ 。 在优化的过程中最大化 ρ ，最小化 ‖ω‖２ ，并使训 练误差 ξ ｋ 最小化，其中 ξ ｋ ≥ ０。 本文的目标是通过优化该目标函数求得距离分 量的权值 ωｉ， 下面将具体介绍求解 ωｉ 的方法。 为 了求解上述优化问题，将它作为原始最优化问题，应 用拉格朗日对偶性，通过求解对偶问题得到原始问 题的最优解。 接下来将介绍具体求解过程。 首先，构建拉格朗日函数如式（３）： Ｌ ＝ １ ２ ∑ ｐ ｉ ＝ １ ω ２ ｉ ＋ Ｃ∑ ｎ ｋ ＝ １ ξ ２ ｋ ＋ β ２ － θρ ＋ ∑ ｎ ｋ ＝ １ αｋ ρ － ξｋ － ｙｋ ∑ ｐ ｉ ＝ １ ωｉｄｉ，ｋ ( ( － β) ) ＋ λ １ － ∑ ｐ ｉ ＝ １ ( ωｉ) （３） 式中：α ＝ α１ α２ … αｎ [ ] Ｔ 、λ 均为拉格朗日乘子。 如果此时考虑式（２）中 ωｉ ≥ ０ 的约束条件，并 将该条件加入拉格朗日函数，则得到 Ｌ′ ＝ Ｌ － ∑ ｐ ｉ ＝ １ φｉωｉ 将该拉格朗日函数分别对 ωｉ、β、ρ、ξ ｋ、λ 求偏 导，并令其等于 ０ 得到 ∂Ｌ′ ∂ωｉ ＝ ωｉ － ∑ ｎ ｋ ＝ １ αｋ ｙｋｄｉ，ｋ － λ － φｉ ＝ ０ ∂Ｌ′ ∂β ＝ ２β － ∑ ｎ ｋ ＝ １ αｋ ｙｋ ＝ ０ ∂Ｌ′ ∂ρ ＝ － θ ＋ ∑ ｎ ｋ ＝ １ αｋ ＝ ０ ∂Ｌ′ ∂ξｋ ＝ ２Ｃξｋ － αｋ ＝ ０ ∂Ｌ′ ∂λ ＝ １ － ∑ ｐ ｉ ＝ １ ωｉ ＝ ０ ì î í ï ï ï ï ï ï ï ï ï ï ï ï ï ï （４） 显然由方程组（４）无法求得 ωｉ ，因此本文先暂 时不考虑 ωｉ ≥ ０ 的约束条件，使用式（３）进行后续 的求解。 根据拉格朗日对偶性，原始问题的对偶问题是 极大极小问题： ｍａｘ α ｍｉｎ ω，β，ξ Ｌ（ω，β，ξ，α，λ） 所以，需要先求 Ｌ（ω，β，ξ，α，λ） 对于 ω、λ 的 极小值。 将拉格朗日函数式（５）分别对 ωｉ、β、ρ、ξ ｋ、λ 求 偏导，并令其等于 ０ 得到 ∂Ｌ ∂ωｉ ＝ ωｉ － ∑ ｎ ｋ ＝ １ αｋ ｙｋｄｉ，ｋ － λ ＝ ０ ∂Ｌ ∂β ＝ ２β － ∑ ｎ ｋ ＝ １ αｋ ｙｋ ＝ ０ ∂Ｌ ∂ρ ＝ － θ ＋ ∑ ｎ ｋ ＝ １ αｋ ＝ ０ ∂Ｌ ∂ξｋ ＝ ２Ｃξｋ － αｋ ＝ ０ ∂Ｌ ∂λ ＝ １ － ∑ ｐ ｉ ＝ １ ωｉ ＝ ０ ì î í ï ï ï ï ï ï ï ï ï ï ï ï ï ï （５） 进而得到 ωｉ ＝ ∑ ｎ ｋ ＝ １ αｋ ｙｋｄｉ，ｋ ＋ λ （６） β ＝ １ ２ ∑ ｎ ｋ ＝ １ αｋ ｙｋ （７） θ ＝ ∑ ｎ ｋ ＝ １ αｋ （８） ξｋ ＝ αｋ ２Ｃ （９） １ － ∑ ｐ ｉ ＝ １ ωｉ ＝ ０ （１０） 将式（６）代入式（１０）得到 λ ＝ １ ｐ １ － ∑ ｎ ｋ ＝ １ αｋ ｙ ( ｋｄｉ，ｋ ) （１１） 进而，将式（１１）代入式（６）得到 ωｉ ＝ １ ｐ － １ ｐ ∑ ｐ ｉ ＝ １ ∑ ｎ ｋ ＝ １ αｋ ｙｋｄｉ，ｋ ＋ ∑ ｎ ｋ ＝ １ αｋ ｙｋｄｉ，ｋ （１２） 将式（７） ～ （１０）、（１２） 代入拉格朗日函数（３） 中，即得 Ｌ ＝ １ ２ｐ － １ ｐ ∑ ｐ ｉ ＝ １ ∑ ｎ ｋ ＝ １ αｋ ｙｋｄｉ，ｋ ＋ １ ２ｐ ∑ ｐ ｉ ＝ １ ∑ ｎ ｋ ＝ １ αｋ ｙ ( ｋｄｉ，ｋ ) ２ － １ ２ ∑ ｐ ｉ ＝ １ ∑ ｎ ｑ ＝ １ αｑ ｙｑｄｉ，ｑ∑ ｎ ｒ ＝ １ αｒ ｙ ( ｒｄｉ，ｒ) ＋ ∑ ｎ ｑ ＝ １ αｑ ｙｑ∑ ｎ ｒ ＝ １ αｒ ｙｒ 即 ｍｉｎ ω，β，ξ Ｌ（ω，β，ξ，α，λ） ＝ １ ２ｐ － １ ｐ ∑ ｐ ｉ ＝ １ ∑ ｎ ｋ ＝ １ αｋ ｙｋｄｉ，ｋ ＋ １ ２ｐ ∑ ｐ ｉ ＝ １ ∑ ｎ ｋ ＝ １ αｋ ｙ ( ｋｄｉ，ｋ ) ２ － １ ２ ∑ ｐ ｉ ＝ １ ∑ ｎ ｑ ＝ １ αｑ ｙｑｄｉ，ｑ∑ ｎ ｒ ＝ １ αｒ ｙ ( ｒｄｉ，ｒ) ＋ 第 ６ 期 郭瑛洁，等：基于最大间隔理论的组合距离学习算法 ·８４５·
·846. 智能系统学报 第10卷 表示无法使w,取正值的i的集合，2个集合p和p 的大小分别使用lp|和p|来表示。 求minL(w,B,专，a,入)对x的极大，即得对偶问题： B,5 至此完成求解距离分量权值ω：的目标，求解集 合p和pˉ的算法描述将在下一小节给出。 max 2印p台台 最大几何间隔0中的p亦可在求解权值 ω：的过程中求得。与原始SVM类似，目标函数(3) 的分商超平面为名如4。一B)=p.即可得最大 ain=0 函数间隔p=y (∑a,ds一B)。在求得最优解后 立4=0 由式(9)可得B的最优解B·= ay进而可得 ak≥0，k=1,2,…,n (13) 将式(13)的目标函数由求极大转换为求极小， 最大函数同隔p=名如，d。一B产)。 就得到下面与之等价的对偶最优化问题： 2.2算法描述 本节将给出求解距离分量权值ω：的具体算法 步骤。 为了便于表示，将式(14)简化： 0,i E p (15) Ue'I +CV:,i∈p aav-g 式中： 含=0 k=1 由式(16)观察可得，若想满足®，为正值，则V: a4≥0，k=1,2,…,n 需要足够大，且当V:越大，ω：为正值的几率就越大。 如此，可以通过二次规划的求解方法得到最优 因此，求解集合p和p的算法总结如下。 解a·=[a1a…a]T,进而代人式(12)得 算法1求解集合p和p。 到w,的最优解： 1)初始化：P。=☑，P={1,2,…,p,h=0: =-ad+4 pp i=ik=1 2)h=h+1,P=P,+{i计，P%=pP-,-i,其 可以明显地观察到，即使成功的优化得到最优 中，i=arg maxi{V}; 解，也不能保证w:完全满足式(2)中ω：≥0的约束 3)通过式(14)计算w。并判断其是否大于0。 条件，受P℉℃算法[的启发，在之前的基础上对ω， 其中，g=arg min,ex{V}。如果w,>0则回到2)， 做如下修改： 否则设置p*=PP=P-1并终止。 下面将介绍学习距离函数中权值ω：的算法，其 0:= 中ω，将采用如下方法初始化：在式(1)中ω：的约束 0,i∈p 条件下，令ω0=ω)=…=ω0，因此有ω0= 1/P。 算法2学习距离函数。 (14) 输入： 式中： 1)数据矩阵：X∈Rw; p={i:w:=0明 2)成对约束：(xy)其中，y={+1,-1: p={i:ω：>0} 3)参数：C、0: p表示所有使得ω：取正值的i的集合，相对应的p 输出：距离权值：ω；
∑ ｎ ｑ ＝ １ αｑ ｙｑ∑ ｎ ｒ ＝ １ αｒ ｙｒ 求 ｍｉｎ ω，β，ξ Ｌ（ω，β，ξ，α，λ） 对 α 的极大，即得对偶问题： ｍａｘ α １ ２ｐ － １ ｐ ∑ ｐ ｉ ＝ １ ∑ ｎ ｋ ＝ １ αｋ ｙｋｄｉ，ｋ ＋ １ ２ｐ ∑ ｐ ｉ ＝ １ ∑ ｎ ｋ ＝ １ αｋ ｙ ( ｋｄｉ，ｋ ) ２ － １ ２ ∑ ｐ ｉ ＝ １ ∑ ｎ ｑ ＝ １ αｑ ｙｑｄｉ，ｑ∑ ｎ ｒ ＝ １ αｒ ｙ ( ｒｄｉ，ｒ) ＋ ∑ ｎ ｑ ＝ １ αｑ ｙｑ∑ ｎ ｒ ＝ １ αｒ ｙｒ ｓ．ｔ．∑ ｎ ｋ ＝ １ αｋ ｙｋ ＝ ０ ∑ ｎ ｋ ＝ １ αｋ ＝ θ αｋ ≥ ０，ｋ ＝ １，２，…，ｎ （１３） 将式（１３）的目标函数由求极大转换为求极小， 就得到下面与之等价的对偶最优化问题： ｍｉｎ α － １ ２ｐ ＋ １ ｐ ∑ ｐ ｉ ＝ １ ∑ ｎ ｋ ＝ １ αｋ ｙｋｄｉ，ｋ － １ ２ｐ ∑ ｐ ｉ ＝ １ ∑ ｎ ｋ ＝ １ αｋ ｙ ( ｋｄｉ，ｋ ) ２ ＋ １ ２ ∑ ｐ ｉ ＝ １ ∑ ｎ ｑ ＝ １ αｑ ｙｑｄｉ，ｑ∑ ｎ ｒ ＝ １ αｒ ｙ ( ｒｄｉ，ｒ) － ∑ ｎ ｑ ＝ １ αｑ ｙｑ∑ ｎ ｒ ＝ １ αｒ ｙｒ ｓ．ｔ．∑ ｎ ｋ ＝ １ αｋ ｙｋ ＝ ０ ∑ ｎ ｋ ＝ １ αｋ ＝ θ αｋ ≥ ０，ｋ ＝ １，２，…，ｎ 如此，可以通过二次规划的求解方法得到最优 解 α ∗ ＝ ［α ∗ １ α ∗ ２ … α ∗ ｎ ］ Ｔ ，进而代入式（１２）得 到 ωｉ 的最优解： ω ∗ ｉ ＝ １ ｐ － １ ｐ ∑ ｐ ｉ ＝ １ ∑ ｎ ｋ ＝ １ α ∗ ｋ ｙｋｄｉ，ｋ ＋ ∑ ｎ ｋ ＝ １ α ∗ ｋ ｙｋｄｉ，ｋ 可以明显地观察到，即使成功的优化得到最优 解，也不能保证 ωｉ 完全满足式（２）中 ωｉ ≥ ０ 的约束 条件，受 ＰＦＣ 算法［１１ ］的启发，在之前的基础上对 ωｉ 做如下修改： ωｉ ＝ ０，ｉ ∈ ｐ － １ ｐ ＋ － １ ｐ ＋ ∑ ｊ∈ｐ ＋∑ ｎ ｋ ＝ １ α ∗ ｋ ｙｋｄｊ，ｋ ＋ ∑ ｎ ｋ ＝ １ α ∗ ｋ ｙｋｄｉ，ｋ，ｉ ∈ ｐ ＋ ì î í ï ï ïï （１４） 式中： ｐ － ＝ ｛ｉ：ωｉ ＝ ０｝ ｐ ＋ ＝ ｛ｉ：ωｉ ＞ ０｝ ｐ ＋ 表示所有使得 ωｉ 取正值的 ｉ 的集合，相对应的 ｐ － 表示无法使 ωｉ 取正值的 ｉ 的集合，２ 个集合 ｐ ＋ 和 ｐ － 的大小分别使用 ｐ ＋ 和 ｐ － 来表示。 至此完成求解距离分量权值 ωｉ 的目标，求解集 合 ｐ ＋ 和 ｐ － 的算法描述将在下一小节给出。 最大几何间隔 ρ ‖ω‖ 中的 ρ 亦可在求解权值 ωｉ 的过程中求得。 与原始 ＳＶＭ 类似，目标函数（３） 的分离超平面为 ｙｋ（∑ ｐ ｉ ＝ １ ωｉｄｉ，ｋ － β） ＝ ρ ，即可得最大 函数间隔 ρ ＝ ｙｋ（∑ ｐ ｉ ＝ １ ωｉｄｉ，ｋ － β） 。 在求得最优解后 由式（９）可得 β 的最优解 β ∗ ＝ １ ２ ∑ ｎ ｋ ＝ １ α ∗ ｋ ｙｋ 进而可得 最大函数间隔 ρ ＝ ｙｋ（∑ ｐ ｉ ＝ １ ωｉ ∗ ｄｉ，ｋ － β ∗ ） 。 ２．２ 算法描述 本节将给出求解距离分量权值 ωｉ 的具体算法 步骤。 为了便于表示，将式（１４）简化： ωｉ ＝ ０，ｉ ∈ ｐ － １ ｐ ＋ ＋ ＣＶｉ，ｉ ∈ ｐ ＋ ì î í ï ï ïï （１５） 式中： Ｖｉ ＝ － １ ｐ ＋ ∑ ｊ∈ｐ ＋∑ ｎ ｋ ＝ １ α ∗ ｋ ｙｋｄｊ，ｋ ＋ ∑ ｎ ｋ ＝ １ α ∗ ｋ ｙｋｄｉ，ｋ （１６） 由式（１６）观察可得，若想满足 ωｉ 为正值，则 Ｖｉ 需要足够大，且当 Ｖｉ 越大， ωｉ 为正值的几率就越大。 因此，求解集合 ｐ ＋ 和 ｐ － 的算法总结如下。 算法 １ 求解集合 ｐ ＋ 和 ｐ － 。 １）初始化： ｐ ＋ ０ ＝ ∅，ｐ － ０ ＝ ｛１，２，…，ｐ｝，ｈ ＝ ０； ２） ｈ ＝ ｈ ＋ １，ｐ ＋ ｈ ＝ ｐ ＋ ｈ－１ ＋ ｛ｉ｝，ｐ － ｈ ＝ ｐ － ｈ－１ － ｛ｉ｝， 其 中， ｉ ＝ ａｒｇ ｍａｘｉ∈ｐ － ｈ－１ ｛Ｖｉ｝ ； ３）通过式（１４） 计算 ωｇ 并判断其是否大于 ０。 其中， ｇ ＝ ａｒｇ ｍｉｎｉ∈ｐ ＋ ｈ ｛Ｖｉ｝ 。 如果 ωｇ ＞ ０ 则回到 ２）， 否则设置 ｐ ＋ ＝ ｐ ＋ ｈ－１ ，ｐ － ＝ ｐ － ｈ－１ 并终止。 下面将介绍学习距离函数中权值 ωｉ 的算法，其 中 ωｉ 将采用如下方法初始化：在式（１）中 ωｉ 的约束 条件下，令 ω （０） １ ＝ ω （０） ２ ＝ … ＝ ω （０） ｐ ，因此有 ω （０） ｉ ＝ １ ／ ｐ。 算法 ２ 学习距离函数。 输入： １）数据矩阵： Ｘ ∈ Ｒ ｄ×Ｎ ； ２）成对约束： ｘ ｋ ａ，ｘ ｋ ａ，ｙｋ ( ) 其中， ｙｋ ＝ ｛ ＋ １， － １｝； ３）参数： Ｃ、θ ； 输出：距离权值： ω ； ·８４６· 智 能 系 统 学 报 第 １０ 卷
第6期 郭瑛洁，等：基于最大间隔理论的组合距离学习算法 .847. 方法： 多类数据集。各个数据集的信息如表1所示。 1)初始化：w=w; 表1实验中使用的数据集信息 2)计算距离矩阵：D(i,k); Table 1 List of data sets 3)计算二次规划参数H和f: 数据集 样本数 特征数 类别数 H= breast 683 10 2 点（店三4dow小-日（含三4）+ sonar 208 60 2 wdbe 569 30 2 1A宫d heart 270 2 2 wine 178 13 3 4)利用二次规划优化算法求解得到最优解：α·= 1473 9 3 [aiag…ar]T; cme thyroid 215 3 5)计算集合p和p:算法1： 6)利用式(15)计算ω。 segment 2310 19 7 在数据集的选择上基于以下考虑：首先，这些数 3实验 据集的特征数和类别数都各不相同。另外，这些数 为了与传统CM算法之间有可比性，本文将简 据集是机器学习研究中被广泛使用的基准数据集， 单的以学习得到的距离函数替换传统FCM算法中 因而具有代表性。最后，由于数据集均为真实数据 的欧式距离。根据传统FCM算法的实现方法，本文 集，因此可以检验算法在真实应用中是否可行。 将通过以下步骤实现聚类： 文中所有实验均在MATLAB平台下进行，所有 训练数据集和测试数据集均先归一化至[0,1]内。 1)初始化隶属度矩阵U,使得 ∑4g=1,j= 带有边信息的训练集将通过如下方法产生：首先，随 1,2,…,n,u∈[0,1]。 机选取数据集的10%组成一个子集。然后，根据子 集中样本点带有的类标是否相同来生成约束对 2)计算聚类中心：c:= (x。,xy)集合。其中，类标相同的成对约束为正 约束对，反之为负约束对。将取个数相同的正负约 =1 束对组成训练集。 3)计算价值函数： 在组合距离分量的选择上，本文依据第2节的 94 J=) 理论，在实验中选取如下10个距离度量进行组合： d(x,y)=(x-y)1(x-y) 当其相对于上次价值函数值的改变量小于某个 阈值时，算法停止。 4）=(x-)rx-y) 4)更新隶属度矩阵： 1 d0x=21s- uj= =1 2/(m-1) d(x,y)=】 其中对于样本点x:,它与聚类中心c:之间的距 -31x 离使用如下公式计算： d6(x,y）=1-e2 d,=u,d(x,c） d(x,)=1-e 将上述聚类算法记为基于组合距离(hybrid dis- d(x,）=1-e tance)的FCM聚类算法(HDFCM)。 d,(x,)=1-eg 本节将上述HDCM算法与已有的经典距离学 dio(x,y)=1-e-lx12 习算法进行对比与分析。 在使用组合距离进行聚类的算法中，本文将依 3.1实验设置 据数据集的类别数给定聚类数目，初始隶属度矩阵 本文使用了8个来自UCI机器学习数据库的 随机生成。为了保证可比性，实验中所有的对比算 真实数据集。其中4个为二类数据集，其余4个为 法将使用相同的初始隶属度矩阵，训练集和其他参
方法： １）初始化： ω ＝ ω （０） ； ２）计算距离矩阵： Ｄ（ｉ，ｋ） ； ３）计算二次规划参数 Ｈ 和 ｆ ： Ｈ ＝ ∑ ｐ ｉ ＝ １ ∑ ｎ ｑ ＝ １∑ ｎ ｒ ＝ １ ｄｉ，ｑｄｉ，ｒ ｙｑ ｙ ( ｒ) － １ ｄ ∑ ｐ ｉ ＝ １ ∑ ｎ ｋ ＝ １ ｙ ( ｋｄｉ，ｋ ) ２ ＋ ｙ ２ ｋ ｆ ＝ １ ｐ ∑ ｐ ｉ ＝ １ ∑ ｎ ｋ ＝ １ ｙｋｄｉ，ｋ ４）利用二次规划优化算法求解得到最优解： α ∗ ＝ ［α ∗ １ α ∗ ２ … α ∗ ｎ ］ Ｔ ； ５）计算集合 ｐ ＋ 和 ｐ － ：算法 １； ６）利用式（１５）计算 ω 。 ３ 实验 为了与传统 ＦＣＭ 算法之间有可比性，本文将简 单的以学习得到的距离函数替换传统 ＦＣＭ 算法中 的欧式距离。 根据传统 ＦＣＭ 算法的实现方法，本文 将通过以下步骤实现聚类： １）初始化隶属度矩阵 Ｕ ，使得 ∑ ｃ ｉ ＝ １ ｕｉｊ ＝ １，∀ｊ ＝ １，２，…，ｎ，ｕｉｊ ∈ [０，１] 。 ２）计算聚类中心： ｃｉ ＝ ∑ Ｎ ｊ ＝ １ ｕ ｍ ｉｊ ｘｊ ∑ Ｎ ｊ ＝ １ ｕ ｍ ｉｊ 。 ３）计算价值函数： Ｊ ＝ ∑ ｃ ｉ ＝ １ ∑ Ｎ ｊ ＝ １ ｕ ｍ ｉｊ ｄ ２ ｉｊ 当其相对于上次价值函数值的改变量小于某个 阈值时，算法停止。 ４）更新隶属度矩阵： ｕｉｊ ＝ １ ∑ ｃ ｋ ＝ １ ｄｉｊ ｄｋｊ æ è ç ö ø ÷ ２／ (ｍ－１ ) 其中对于样本点 ｘｊ ，它与聚类中心 ｃｉ 之间的距 离使用如下公式计算： ｄｉｊ ＝ ∑ ｐ ｒ ＝ １ ωｒｄｒ（ｘｊ，ｃｉ） 将上述聚类算法记为基于组合距离（ｈｙｂｒｉｄ ｄｉｓ⁃ ｔａｎｃｅ）的 ＦＣＭ 聚类算法（ＨＤＦＣＭ）。 本节将上述 ＨＤＦＣＭ 算法与已有的经典距离学 习算法进行对比与分析。 ３．１ 实验设置 本文使用了 ８ 个来自 ＵＣＩ 机器学习数据库的 真实数据集。 其中 ４ 个为二类数据集，其余 ４ 个为 多类数据集。 各个数据集的信息如表 １ 所示。 表 １ 实验中使用的数据集信息 Ｔａｂｌｅ １ Ｌｉｓｔ ｏｆ ｄａｔａ ｓｅｔｓ 数据集 样本数 特征数 类别数 ｂｒｅａｓｔ ６８３ １０ ２ ｓｏｎａｒ ２０８ ６０ ２ ｗｄｂｃ ５６９ ３０ ２ ｈｅａｒｔ ２７０ １２ ２ ｗｉｎｅ １７８ １３ ３ ｃｍｃ １ ４７３ ９ ３ ｔｈｙｒｏｉｄ ２１５ ５ ３ ｓｅｇｍｅｎｔ ２ ３１０ １９ ７ 在数据集的选择上基于以下考虑：首先，这些数 据集的特征数和类别数都各不相同。 另外，这些数 据集是机器学习研究中被广泛使用的基准数据集， 因而具有代表性。 最后，由于数据集均为真实数据 集，因此可以检验算法在真实应用中是否可行。 文中所有实验均在 ＭＡＴＬＡＢ 平台下进行，所有 训练数据集和测试数据集均先归一化至 [０，１] 内。 带有边信息的训练集将通过如下方法产生：首先，随 机选取数据集的 １０％组成一个子集。 然后，根据子 集中样本点带有的类标是否相同来生成约束对 ｘ ｋ ａ ，ｘ ｋ ｂ，ｙｋ ( ) 集合。 其中，类标相同的成对约束为正 约束对，反之为负约束对。 将取个数相同的正负约 束对组成训练集。 在组合距离分量的选择上，本文依据第 ２ 节的 理论，在实验中选取如下 １０ 个距离度量进行组合： ｄ１（ｘ，ｙ） ＝ （ｘ － ｙ） Ｔ Ｉ（ｘ － ｙ） ｄ３（ｘ，ｙ） ＝ （ｘ － ｙ） Ｔ ３Ｉ σ ２ （ｘ － ｙ） ｄ４（ｘ，ｙ） ＝ ∑ ｄ ｉ ＝ １ ｘｉ － ｙｉ ｄ５（ｘ，ｙ） ＝ ∑ ｄ ｉ ＝ １ ｘｉ － ｙｉ σ ２ ｄ６（ｘ，ｙ） ＝ １ － ｅ －３‖ｘ－ｙ‖２ σ ２ ｄ７（ｘ，ｙ） ＝ １ － ｅ －‖ｘ－ｙ‖２ σ ２ ｄ８（ｘ，ｙ） ＝ １ － ｅ －‖ｘ－ｙ‖２ ３σ ２ ｄ９（ｘ，ｙ） ＝ １ － ｅ －‖ｘ－ｙ‖２ ５σ ２ ｄ１０（ｘ，ｙ） ＝ １ － ｅ －‖ｘ－ｙ‖２ 在使用组合距离进行聚类的算法中，本文将依 据数据集的类别数给定聚类数目，初始隶属度矩阵 随机生成。 为了保证可比性，实验中所有的对比算 法将使用相同的初始隶属度矩阵，训练集和其他参 第 ６ 期 郭瑛洁，等：基于最大间隔理论的组合距离学习算法 ·８４７·
·848. 智能系统学报 第10卷 数(m=2,e=10-5,T=100,C=10-5)。实验将重 算法一样应用于FCM聚类算法中以评价。 复每个聚类过程20次，实验结果取其均值。 3.3实验结果与分析 为了评估聚类效果，采用一种类似F,-measure 对于各个数据集，本文所提出算法与其他算法 的成对约束评价方法，评价参数包括：pairwise Preci- 在8个数据集上的实验结果对比如图1所示，其中 sion,pairwise Recall和pairwise F,定义为[ 每一个子图的纵坐标表示了各个算法在相同参数下 #TruePositive 在该数据集上的聚类效果的评价指标均值，横坐标 Precision #TruePositive +#FalsePositive 上的柱形分为3组，每一组分别表示F,、precsion和 #TruePositive Recall = recall。每个颜色代表一个算法，从左至右分别为 #TruePositive #FalseNegative FCM算法[a,C-Euc算法[)，PGDM-Ad算法[)， 2 X Precision×Recall F1= PGDM-Af算法[]和HDFCM算法，数据集名称标注 Precision Recall 在图标题上。表2展示了本文算法相对于传统 式中：#TruePositive为将正约束对预测为正约束对 FCM算法聚类效果的提升率，提升率使用如下公式 的个数，#FalsePositive为将负约束对预测为正约束 计算得到： 对的个数，#FalseNegative为将正约束对预测为负 HDFCM_F FCM_F 约束对的个数。由于该评价方法的对象为约束对， 提升率= -×100% FCM_F 因此不仅可以应用于二分类的评价，也可应用于多 从图1可以看出，本文提出的算法在大部分数 类分类的评价。 据集上获得了最好的表现。相对于其他距离学习算 3.2对比算法 法而言，本文算法在sonar数据集和cmc数据集中 本文使用了若干经典距离学习算法进行对比， 虽未获得最好的表现，但是结合表2可以发现本文 包括：使用欧式距离的传统FCM算法(FCM),使用 算法的聚类效果相对于传统CM算法仍有一定的 欧氏距离但含有约束条件的K-均值聚类算法(C- 提升。由于本文使用的距离分量有限，因此对于不 Ec)【2),基于凸优化的全局距离学习算法(PG 同的数据集不一定能拟合出最适合于该数据集的距 DM)[3] 离度量。此外，从表2可以观察到，本文算法在 与本文提出的算法类似，C-Euc算法也是一种利 breast数据集和wine数据集上有相当卓越的表现。 用边信息进行距离学习的半监督聚类算法，它在传统 结合图1和表1可以得出，本文算法不仅适用 K-均值算法的基础上加上成对约束，在这些约束的监 于2类数据集，对于多类数据集也有较好的聚类效 督下进行聚类。C-Euc算法在聚类的过程中要求每 果。比如，2类数据集breast,3类数据集wine,7类 一次划分都满足已知的约束条件，每个样本在没有违 数据集segment在聚类效果上均取得了30%以上的 反约束条件的情况下，被划分给最近的类，最终得到 提升。 的聚类结果将满足所有的约束对信息[]。 1.0 PGDM算法由Xing等提出，是一种基于凸优化 0.8 的全局距离度量学习算法。它将正约束对构成的集 合记为S,负约束对构成的集合记为D。通过以下 凸优化问题对距离矩阵A进行求解： FCM min∑Ix-x,I C-Euc (xi》eS 0.2 PGDM-Ad GDM-Af st.∑‖x-xI4≥1，A≥0 HDFCM ()eD F precision recall (a)breast 式中：Ⅱ：，‖A=√(x,)A(,x)表示2个 1.0 样本点x,和x之间的距离。根据预期得到的矩阵 0.8 A的不同将有不同的解法。如果期望得到对角形式 的距离矩阵，可以通过牛顿法进行求解，本文将此算 0.6 法记为PGDM-Ad。如果期待得到全矩阵形式的距 0.4 IFCM 离矩阵，则可以通过梯度下降和逐次映射的方法进 C-Euc 0.2 PGDM-Ad 行求解，本文将此算法记为PGDM-Af。为了保证对 PGDM-AF HDFCM 比性，在实验中本文将学习得到的距离矩阵和本文 precision recall (b)sonar
数（ ｍ ＝ ２，ε ＝ １０ －５ ，Ｔ ＝ １００，Ｃ ＝ １０ －５ ）。 实验将重 复每个聚类过程 ２０ 次，实验结果取其均值。 为了评估聚类效果，采用一种类似 Ｆ１ ⁃ｍｅａｓｕｒｅ 的成对约束评价方法，评价参数包括：ｐａｉｒｗｉｓｅ Ｐｒｅｃｉ⁃ ｓｉｏｎ，ｐａｉｒｗｉｓｅ Ｒｅｃａｌｌ 和 ｐａｉｒｗｉｓｅ Ｆ１ ， 定义为［２］ Ｐｒｅｃｉｓｉｏｎ ＝ ＃ＴｒｕｅＰｏｓｉｔｉｖｅ ＃ＴｒｕｅＰｏｓｉｔｉｖｅ ＋ ＃ＦａｌｓｅＰｏｓｉｔｉｖｅ Ｒｅｃａｌｌ ＝ ＃ＴｒｕｅＰｏｓｉｔｉｖｅ ＃ＴｒｕｅＰｏｓｉｔｉｖｅ ＋ ＃ＦａｌｓｅＮｅｇａｔｉｖｅ Ｆ１ ＝ ２ × Ｐｒｅｃｉｓｉｏｎ × Ｒｅｃａｌｌ Ｐｒｅｃｉｓｉｏｎ ＋ Ｒｅｃａｌｌ 式中： ＃ＴｒｕｅＰｏｓｉｔｉｖｅ 为将正约束对预测为正约束对 的个数， ＃ＦａｌｓｅＰｏｓｉｔｉｖｅ 为将负约束对预测为正约束 对的个数， ＃ＦａｌｓｅＮｅｇａｔｉｖｅ 为将正约束对预测为负 约束对的个数。 由于该评价方法的对象为约束对， 因此不仅可以应用于二分类的评价，也可应用于多 类分类的评价。 ３．２ 对比算法 本文使用了若干经典距离学习算法进行对比， 包括：使用欧式距离的传统 ＦＣＭ 算法（ＦＣＭ），使用 欧氏距离但含有约束条件的 Ｋ⁃均值聚类算法（Ｃ⁃ Ｅｕｃ） ［１２ ］ ，基于凸优化的全局距离学习算法 （ ＰＧ⁃ ＤＭ） ［３］ 。 与本文提出的算法类似，Ｃ⁃Ｅｕｃ 算法也是一种利 用边信息进行距离学习的半监督聚类算法，它在传统 Ｋ⁃均值算法的基础上加上成对约束，在这些约束的监 督下进行聚类。 Ｃ⁃Ｅｕｃ 算法在聚类的过程中要求每 一次划分都满足已知的约束条件，每个样本在没有违 反约束条件的情况下，被划分给最近的类，最终得到 的聚类结果将满足所有的约束对信息［１３ ］ 。 ＰＧＤＭ 算法由 Ｘｉｎｇ 等提出，是一种基于凸优化 的全局距离度量学习算法。 它将正约束对构成的集 合记为 Ｓ ，负约束对构成的集合记为 Ｄ 。 通过以下 凸优化问题对距离矩阵 Ａ 进行求解： ｍｉｎ Ａ （ｘ∑ｉ ，ｘｊ ）∈Ｓ ‖ ｘｉ － ｘｊ‖２ Ａ ｓ．ｔ． （ｘ∑ｉ ，ｘｊ ）∈Ｄ ‖ ｘｉ － ｘｊ‖Ａ ≥ １，Ａ ≥ ０ 式中： ‖ ｘｉ，ｘｊ‖Ａ ＝ （ｘｉ，ｘｊ） ＴＡ（ｘｉ，ｘｊ） 表示 ２ 个 样本点 ｘｉ 和 ｘｊ 之间的距离。 根据预期得到的矩阵 Ａ 的不同将有不同的解法。 如果期望得到对角形式 的距离矩阵，可以通过牛顿法进行求解，本文将此算 法记为 ＰＧＤＭ⁃Ａｄ。 如果期待得到全矩阵形式的距 离矩阵，则可以通过梯度下降和逐次映射的方法进 行求解，本文将此算法记为 ＰＧＤＭ⁃Ａｆ。 为了保证对 比性，在实验中本文将学习得到的距离矩阵和本文 算法一样应用于 ＦＣＭ 聚类算法中以评价。 ３．３ 实验结果与分析 对于各个数据集，本文所提出算法与其他算法 在 ８ 个数据集上的实验结果对比如图 １ 所示，其中 每一个子图的纵坐标表示了各个算法在相同参数下 在该数据集上的聚类效果的评价指标均值，横坐标 上的柱形分为 ３ 组，每一组分别表示 Ｆ１ 、ｐｒｅｃｓｉｏｎ 和 ｒｅｃａｌｌ。 每个颜色代表一个算法，从左至右分别为 ＦＣＭ 算法［ １４ ］ ， Ｃ⁃Ｅｕｃ 算法［１２］ ， ＰＧＤＭ⁃Ａｄ 算法［３］ ， ＰＧＤＭ⁃Ａｆ 算法［３］和 ＨＤＦＣＭ 算法，数据集名称标注 在图标题上。 表 ２ 展示了本文算法相对于传统 ＦＣＭ 算法聚类效果的提升率，提升率使用如下公式 计算得到： 提升率 ＝ ＨＤＦＣＭ＿Ｆ１ － ＦＣＭ＿Ｆ１ ＦＣＭ＿Ｆ１ × １００％ 从图 １ 可以看出，本文提出的算法在大部分数 据集上获得了最好的表现。 相对于其他距离学习算 法而言，本文算法在 ｓｏｎａｒ 数据集和 ｃｍｃ 数据集中 虽未获得最好的表现，但是结合表 ２ 可以发现本文 算法的聚类效果相对于传统 ＦＣＭ 算法仍有一定的 提升。 由于本文使用的距离分量有限，因此对于不 同的数据集不一定能拟合出最适合于该数据集的距 离度量。 此外，从表 ２ 可以观察到， 本文算法在 ｂｒｅａｓｔ 数据集和 ｗｉｎｅ 数据集上有相当卓越的表现。 结合图 １ 和表 １ 可以得出，本文算法不仅适用 于 ２ 类数据集，对于多类数据集也有较好的聚类效 果。 比如，２ 类数据集 ｂｒｅａｓｔ，３ 类数据集 ｗｉｎｅ，７ 类 数据集 ｓｅｇｍｅｎｔ 在聚类效果上均取得了 ３０％以上的 提升。 ·８４８· 智 能 系 统 学 报 第 １０ 卷
第6期 郭瑛洁，等：基于最大间隔理论的组合距离学习算法 ·849. 1.0 1.01 0.8 0.8 0.6 敏0.6 0.4 FCM IFCM C-Euc C-Euc 0.2 PGDM-Ad 0.2 PGDM-Ad PGDM-Af PGDM-Af HDFCM HDFCM precision recal precision recall (c)wdbe (f)cme 1.0 1.0 0.8 0.8 0.6 FCM FCM C-Euc C-Euc 02 PGDM-Ad 0 PGDM-Ad PGDM-Af PGDM-Af HDFCM HDFCM precision recal precision recall (d)heart (g)thyroid 1.0 .0 0.8 0.8 0.6 0.6 0. FCM C-Euc .4 FCM PGDM-Ad C-Euc PGDM-Af 0.2 PGDM-Ad HDECM PGDM-Af precision recall HDFCM (h)segment precision recall (e)wine 图1算法对比图 Fig.1 Clustering performance comparison 表2本文算法相对于传统FCM的提升率 Table 2 Upgrade rate of our algorithm 数据集 breast sonar wdbe heart wine cmc thyroid segment 提升率/% 60.16 5.62 10.98 26.28 64.24 5.33 24.71 31.29 4 由于传统FCM算法使用的是欧式距离，且其为 结束语 无监督聚类算法，因此在应用的过程中不一定适合 本文提出了一种基于线性组合的混合距离学习 所有类型的数据集。而C-Euc算法虽然引入了数据 算法。该算法构建了一个由若干候选距离线性组合 集的边信息，但是其使用的距离度量仍然为欧氏距 而成的距离目标函数，利用数据集的边信息学习得 离，因此在使用的时候也具有局限性。PGDM在引 到各候选距离对应权值，从而得到新的距离函数。 入了边信息的基础上学习出了新的距离度量，但是 本文将学习得到的距离函数应用于模糊C均值算法 该距离函数仍是在马氏距离定义框架下的距离度 中以构成一个半监督聚类算法。通过使用UCI真实 量，属于线性的距离学习方法。本文提出的算法不 数据集将该半监督聚类算法的聚类效果与其他距离 仅引入了数据集的边信息，而且组合了预设的多种 学习算法进行对比，证明了本文算法的有效性。 形式的距离度量，学习得到一个非线性的距离度量， 参考文献： 使其对于数据集有较好的适应性。上述实验可以证 明本文算法的有效性。 [1]王骏，王士同.基于混合距离学习的双指数模糊C均值 算法[J].软件学报，2010,21(8)：1878-1888
图 １ 算法对比图 Ｆｉｇ．１ Ｃｌｕｓｔｅｒｉｎｇ ｐｅｒｆｏｒｍａｎｃｅ ｃｏｍｐａｒｉｓｏｎ 表 ２ 本文算法相对于传统 ＦＣＭ 的提升率 Ｔａｂｌｅ ２ Ｕｐｇｒａｄｅ ｒａｔｅ ｏｆ ｏｕｒ ａｌｇｏｒｉｔｈｍ 数据集 ｂｒｅａｓｔ ｓｏｎａｒ ｗｄｂｃ ｈｅａｒｔ ｗｉｎｅ ｃｍｃ ｔｈｙｒｏｉｄ ｓｅｇｍｅｎｔ 提升率／ ％ ６０．１６ ５．６２ １０．９８ ２６．２８ ６４．２４ ５．３３ ２４．７１ ３１．２９ 由于传统 ＦＣＭ 算法使用的是欧式距离，且其为 无监督聚类算法，因此在应用的过程中不一定适合 所有类型的数据集。 而 Ｃ⁃Ｅｕｃ 算法虽然引入了数据 集的边信息，但是其使用的距离度量仍然为欧氏距 离，因此在使用的时候也具有局限性。 ＰＧＤＭ 在引 入了边信息的基础上学习出了新的距离度量，但是 该距离函数仍是在马氏距离定义框架下的距离度 量，属于线性的距离学习方法。 本文提出的算法不 仅引入了数据集的边信息，而且组合了预设的多种 形式的距离度量，学习得到一个非线性的距离度量， 使其对于数据集有较好的适应性。 上述实验可以证 明本文算法的有效性。 ４ 结束语 本文提出了一种基于线性组合的混合距离学习 算法。 该算法构建了一个由若干候选距离线性组合 而成的距离目标函数，利用数据集的边信息学习得 到各候选距离对应权值，从而得到新的距离函数。 本文将学习得到的距离函数应用于模糊 Ｃ 均值算法 中以构成一个半监督聚类算法。 通过使用 ＵＣＩ 真实 数据集将该半监督聚类算法的聚类效果与其他距离 学习算法进行对比，证明了本文算法的有效性。 参考文献： ［１］王骏， 王士同． 基于混合距离学习的双指数模糊 Ｃ 均值 算法［Ｊ］． 软件学报， ２０１０， ２１（８）： １８７８⁃１８８８． 第 ６ 期 郭瑛洁，等：基于最大间隔理论的组合距离学习算法 ·８４９·
.850. 智能系统学报 第10卷 WANG Jun,WANG Shitong.Double indices FCM algorithm [10]TSANG I W H,KWOK J T Y,ZURADA J A.Generalized based on hybrid distance metric learning[J].Journal of Soft- Core Vector Machines [J].IEEE Transaction on Neural ware,2010,21(8):1878-1888. Networks,2006,17(5):1126-1140. [2]WU Lei,HOI S C H,JIN Rong,et al.Learning Bregman [11]MEI Jianping,CHEN Lihui.Fuzzy clustering with weighted distance functions for semi-supervised clustering[J].IEEE medoids for relational data[J].Pattern Recognition,2010, Transactions on Knowledge and Data Engineering,2012,24 43(5):1964-1974. (3):478-491. [12]WAGSTAFF K,CARDIE C,ROGERS S,et al.Constrain- [3]XING E P,NG A Y,JORDAN M I,et al.Distance metric ed k-means clustering with background knowledge C]// learning with application to clustering with side information BAR-HILLEL A,HERTZ T,SHENTAL N,et al.Proceed- [C]//Advances in Neural Information Processing Systems. ings of the Eighteenth International Conference on Machine Vancouver,Canada,2002:521-528. Learning.Williamstown,Australia,2001:577-584. [4]HOI S C H,LIU Wei,LYU M R,et al.Learning distance [13]COVOES T F,HRUSCHKA E R,GHOSH J.A study of k- metrics with contextual constraints for image retrieval[C]// means-based algorithms for constrained clustering[J].In- Proceedings of 2006 IEEE Computer Society Conference on telligent Data Analysis,2013,17(3):485-505. Computer Vision and Pattern Recognition.New York,Amer- [14]BEZDEK J C.Pattern recognition with fuzzy objective func- ica,2006,2:2072-2078. tion algorithms[M.New York:Plenum Press,1981:56- [5]GOLDBERGER J,HINTON G,ROWEIS S,et al.Neigh- 57. borhood component analysis[C]//Advances in Neural Infor- 作者简介： mation Processing Systems.Cambridge,United Kingdom, 郭瑛洁，女，1991生，硕士研究生， 2005:451-458. 主要研究方向为人工智能，模式识别。 [6]WEINBERGER K Q,BLITZER J C,SAUL L K.Distance metric learning for large margin nearest neighbor classifica- tion[C]//Advances in Neural Information Processing Sys- tems.Cambridge,United Kingdom,2006:1473-1480. [7]王骏，王土同，邓赵红.特征加权距离与软子空间学习 相结合的文本聚类新方法[J].计算机学报，2012,35 王士同，男，1964生，教授，博士生 (8):1655-1665. 导师，主要研究方向为人工智能、模式 WANG Jun,WANG Shitong,DENG Zhaohong.A novel text 识别和生物信息。 clustering algorithm based on feature weighting distance and soft subspace learning[J].Chinese Journal of Computers, 2012,35(8):1655-1665. [8]WU K L,YANG M S.Alternative c-means clustering algo- 许小龙，男，1989生，硕士研究生， rithms J].Pattern Recognition,2002,35 (10):2267- 主要研究方向为人工智能，模式识别。 2278. [9]CORTES C.VAPNIK V.Support-vector networks[J].Ma- chine Learning,1995,20(3):273-297
ＷＡＮＧ Ｊｕｎ， ＷＡＮＧ Ｓｈｉｔｏｎｇ． Ｄｏｕｂｌｅ ｉｎｄｉｃｅｓ ＦＣＭ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｈｙｂｒｉｄ ｄｉｓｔａｎｃｅ ｍｅｔｒｉｃ ｌｅａｒｎｉｎｇ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｓｏｆｔ⁃ ｗａｒｅ， ２０１０， ２１（８）： １８７８⁃１８８８． ［２］ＷＵ Ｌｅｉ， ＨＯＩ Ｓ Ｃ Ｈ， ＪＩＮ Ｒｏｎｇ， ｅｔ ａｌ． Ｌｅａｒｎｉｎｇ Ｂｒｅｇｍａｎ ｄｉｓｔａｎｃｅ ｆｕｎｃｔｉｏｎｓ ｆｏｒ ｓｅｍｉ⁃ｓｕｐｅｒｖｉｓｅｄ ｃｌｕｓｔｅｒｉｎｇ［ Ｊ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｋｎｏｗｌｅｄｇｅ ａｎｄ Ｄａｔａ Ｅｎｇｉｎｅｅｒｉｎｇ， ２０１２， ２４ （３）： ４７８⁃４９１． ［３］ＸＩＮＧ Ｅ Ｐ， ＮＧ Ａ Ｙ， ＪＯＲＤＡＮ Ｍ Ｉ， ｅｔ ａｌ． Ｄｉｓｔａｎｃｅ ｍｅｔｒｉｃ ｌｅａｒｎｉｎｇ ｗｉｔｈ ａｐｐｌｉｃａｔｉｏｎ ｔｏ ｃｌｕｓｔｅｒｉｎｇ ｗｉｔｈ ｓｉｄｅ ｉｎｆｏｒｍａｔｉｏｎ ［Ｃ］ ／ ／ Ａｄｖａｎｃｅｓ ｉｎ Ｎｅｕｒａｌ Ｉｎｆｏｒｍａｔｉｏｎ Ｐｒｏｃｅｓｓｉｎｇ Ｓｙｓｔｅｍｓ． Ｖａｎｃｏｕｖｅｒ， Ｃａｎａｄａ， ２００２： ５２１⁃５２８． ［４］ＨＯＩ Ｓ Ｃ Ｈ， ＬＩＵ Ｗｅｉ， ＬＹＵ Ｍ Ｒ， ｅｔ ａｌ． Ｌｅａｒｎｉｎｇ ｄｉｓｔａｎｃｅ ｍｅｔｒｉｃｓ ｗｉｔｈ ｃｏｎｔｅｘｔｕａｌ ｃｏｎｓｔｒａｉｎｔｓ ｆｏｒ ｉｍａｇｅ ｒｅｔｒｉｅｖａｌ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ２００６ ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ ａｎｄ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ． Ｎｅｗ Ｙｏｒｋ， Ａｍｅｒ⁃ ｉｃａ， ２００６， ２： ２０７２⁃２０７８． ［５］ＧＯＬＤＢＥＲＧＥＲ Ｊ， ＨＩＮＴＯＮ Ｇ， ＲＯＷＥＩＳ Ｓ， ｅｔ ａｌ． Ｎｅｉｇｈ⁃ ｂｏｒｈｏｏｄ ｃｏｍｐｏｎｅｎｔ ａｎａｌｙｓｉｓ［Ｃ］ ／ ／ Ａｄｖａｎｃｅｓ ｉｎ Ｎｅｕｒａｌ Ｉｎｆｏｒ⁃ ｍａｔｉｏｎ Ｐｒｏｃｅｓｓｉｎｇ Ｓｙｓｔｅｍｓ． Ｃａｍｂｒｉｄｇｅ， Ｕｎｉｔｅｄ Ｋｉｎｇｄｏｍ， ２００５： ４５１⁃４５８． ［６］ＷＥＩＮＢＥＲＧＥＲ Ｋ Ｑ， ＢＬＩＴＺＥＲ Ｊ Ｃ， ＳＡＵＬ Ｌ Ｋ． Ｄｉｓｔａｎｃｅ ｍｅｔｒｉｃ ｌｅａｒｎｉｎｇ ｆｏｒ ｌａｒｇｅ ｍａｒｇｉｎ ｎｅａｒｅｓｔ ｎｅｉｇｈｂｏｒ ｃｌａｓｓｉｆｉｃａ⁃ ｔｉｏｎ［ Ｃ］ ／ ／ Ａｄｖａｎｃｅｓ ｉｎ Ｎｅｕｒａｌ Ｉｎｆｏｒｍａｔｉｏｎ Ｐｒｏｃｅｓｓｉｎｇ Ｓｙｓ⁃ ｔｅｍｓ． Ｃａｍｂｒｉｄｇｅ， Ｕｎｉｔｅｄ Ｋｉｎｇｄｏｍ， ２００６： １４７３⁃１４８０． ［７］王骏， 王士同， 邓赵红． 特征加权距离与软子空间学习 相结合的文本聚类新方法［ Ｊ］． 计算机学报， ２０１２， ３５ （８）： １６５５⁃１６６５． ＷＡＮＧ Ｊｕｎ， ＷＡＮＧ Ｓｈｉｔｏｎｇ， ＤＥＮＧ Ｚｈａｏｈｏｎｇ． Ａ ｎｏｖｅｌ ｔｅｘｔ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｆｅａｔｕｒｅ ｗｅｉｇｈｔｉｎｇ ｄｉｓｔａｎｃｅ ａｎｄ ｓｏｆｔ ｓｕｂｓｐａｃｅ ｌｅａｒｎｉｎｇ ［ Ｊ］． Ｃｈｉｎｅｓｅ Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒｓ， ２０１２， ３５（８）： １６５５⁃１６６５． ［８］ＷＵ Ｋ Ｌ， ＹＡＮＧ Ｍ Ｓ． Ａｌｔｅｒｎａｔｉｖｅ ｃ⁃ｍｅａｎｓ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏ⁃ ｒｉｔｈｍｓ［ Ｊ］． Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ， ２００２， ３５ （ １０ ）： ２２６７⁃ ２２７８． ［９］ＣＯＲＴＥＳ Ｃ， ＶＡＰＮＩＫ Ｖ． Ｓｕｐｐｏｒｔ⁃ｖｅｃｔｏｒ ｎｅｔｗｏｒｋｓ［ Ｊ］． Ｍａ⁃ ｃｈｉｎｅ Ｌｅａｒｎｉｎｇ， １９９５， ２０（３）： ２７３⁃２９７． ［１０］ＴＳＡＮＧ Ｉ Ｗ Ｈ， ＫＷＯＫ Ｊ Ｔ Ｙ， ＺＵＲＡＤＡ Ｊ Ａ． Ｇｅｎｅｒａｌｉｚｅｄ Ｃｏｒｅ Ｖｅｃｔｏｒ Ｍａｃｈｉｎｅｓ ［ Ｊ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎ ｏｎ Ｎｅｕｒａｌ Ｎｅｔｗｏｒｋｓ， ２００６， １７（５）： １１２６⁃１１４０． ［１１］ＭＥＩ Ｊｉａｎｐｉｎｇ， ＣＨＥＮ Ｌｉｈｕｉ． Ｆｕｚｚｙ ｃｌｕｓｔｅｒｉｎｇ ｗｉｔｈ ｗｅｉｇｈｔｅｄ ｍｅｄｏｉｄｓ ｆｏｒ ｒｅｌａｔｉｏｎａｌ ｄａｔａ［Ｊ］． Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ， ２０１０， ４３（５）： １９６４⁃１９７４． ［１２］ＷＡＧＳＴＡＦＦ Ｋ， ＣＡＲＤＩＥ Ｃ， ＲＯＧＥＲＳ Ｓ， ｅｔ ａｌ． Ｃｏｎｓｔｒａｉｎ⁃ ｅｄ ｋ⁃ｍｅａｎｓ ｃｌｕｓｔｅｒｉｎｇ ｗｉｔｈ ｂａｃｋｇｒｏｕｎｄ ｋｎｏｗｌｅｄｇｅ ［ Ｃ］ ／ ／ ＢＡＲ⁃ＨＩＬＬＥＬ Ａ， ＨＥＲＴＺ Ｔ， ＳＨＥＮＴＡＬ Ｎ， ｅｔ ａｌ． Ｐｒｏｃｅｅｄ⁃ ｉｎｇｓ ｏｆ ｔｈｅ Ｅｉｇｈｔｅｅｎｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｍａｃｈｉｎｅ Ｌｅａｒｎｉｎｇ． Ｗｉｌｌｉａｍｓｔｏｗｎ， Ａｕｓｔｒａｌｉａ，２００１： ５７７⁃５８４． ［１３］ＣＯＶÕＥＳ Ｔ Ｆ， ＨＲＵＳＣＨＫＡ Ｅ Ｒ， ＧＨＯＳＨ Ｊ． Ａ ｓｔｕｄｙ ｏｆ ｋ⁃ ｍｅａｎｓ⁃ｂａｓｅｄ ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｃｏｎｓｔｒａｉｎｅｄ ｃｌｕｓｔｅｒｉｎｇ［ Ｊ］． Ｉｎ⁃ ｔｅｌｌｉｇｅｎｔ Ｄａｔａ Ａｎａｌｙｓｉｓ， ２０１３， １７（３）： ４８５⁃５０５． ［１４］ＢＥＺＤＥＫ Ｊ Ｃ． Ｐａｔｔｅｒｎ ｒｅｃｏｇｎｉｔｉｏｎ ｗｉｔｈ ｆｕｚｚｙ ｏｂｊｅｃｔｉｖｅ ｆｕｎｃ⁃ ｔｉｏｎ ａｌｇｏｒｉｔｈｍｓ［Ｍ］． Ｎｅｗ Ｙｏｒｋ： Ｐｌｅｎｕｍ Ｐｒｅｓｓ， １９８１： ５６⁃ ５７． 作者简介： 郭瑛洁，女，１９９１ 生，硕士研究生， 主要研究方向为人工智能、模式识别。 王士同，男，１９６４ 生，教授，博士生 导师，主要研究方向为人工智能、模式 识别和生物信息。 许小龙，男，１９８９ 生，硕士研究生， 主要研究方向为人工智能、模式识别。 ·８５０· 智 能 系 统 学 报 第 １０ 卷