基于最大間隔理論的組合距離學習算法

郭瑛潔，王士同，許小龍

(江南大學 數字媒體學院 ，江蘇 無錫 214000)

?

基于最大間隔理論的組合距離學習算法

郭瑛潔，王士同，許小龍

(江南大學 數字媒體學院 ，江蘇 無錫 214000)

摘要：從已知數據集中學習距離度量在許多機器學習應用中都起著重要作用。傳統的距離學習方法通常假定目標距離函數為馬氏距離的形式，這使得學習出的距離度量在應用上具有局限性。提出了一種新的距離學習方法，將目標距離函數表示為若干候選距離的線性組合，依據最大間隔理論利用數據集的邊信息學習得到組合距離中各距離分量的權值，從而得到新的距離度量。通過該距離度量在模糊C均值聚類算法中的表現來對其進行評價。在UCI數據集上，與其他已有的距離學習算法的對比實驗結果證明了該文算法的有效性。

關鍵詞：距離學習；組合距離；最大間隔；FCM；模糊聚類；聚類算法；距離；學習算法

中文引用格式：郭瑛潔，王士同，許小龍. 基于最大間隔理論的組合距離學習算法[J]. 智能系統學報， 2015, 10(6): 843-850.

如何表示2點之間的距離是模式識別中的基礎問題。一個好的距離度量能夠根據數據的結構與分布適用于不同的應用。歐氏距離是眾多數據挖掘應用中使用最多的距離度量，但是歐氏距離僅適用于特征空間中超球結構的數據集，對于超立方體結構、超橢球結構的數據集效果不太理想[1]。除了歐氏距離，余弦距離是另一個應用廣泛的距離度量。盡管余弦距離在文本檢索中有優秀的表現，但是其預先假設了數據集每一維度都是等權重的[2]，這一特性顯然限制了余弦距離的應用范圍。因此，歐式距離和余弦距離在實際應用中都不是最理想的選擇。

從訓練樣本中學習出合適的距離度量是近年來的研究熱點，它對于提高聚類和分類效果有著重要的影響。一般的距離學習方法都是首先假定一個距離函數模型并進行求解，其中大部分的距離函數假定在馬氏距離定義的框架之下，即對于2點x、y，使用距離公式d(x,y)=(x-y)TA(x-y)，其中A為所要學習的距離矩陣。比如文獻[3]中通過使相似樣本之間距離減小學習了一個全局距離度量;區分成分分析(DCA)[4]通過最小化相似樣本之間距離的同時最大化不相似樣本之間的距離來學習距離矩陣;近鄰成分分析(NCA)[5]通過最優化最近鄰分類器的精度去學習馬氏距離度量;最大邊界近鄰分類方法(LMNN)[6]在NCA的框架下拓展了最大邊界的目標，但是學習的目標仍然是得到一個馬氏距離。當馬氏距離中的矩陣A取單位矩陣I時，則馬氏距離表示歐氏距離。因此，本質上來說，以馬氏距離為目標學習得到的新距離是歐式距離的線性變換，其無法準確地度量所有樣本之間的距離。

有別于傳統的距離學習方法，本文提出的距離學習方法并沒有將學習目標單純設定為馬氏距離，而是學習由若干候選距離線性組合而成的新距離。基于最大間隔理論建立目標函數，利用數據的邊信息通過對目標函數進行優化從而得到組合距離中的權重進而得到新的距離度量。對于候選距離的選擇也不僅僅局限于馬氏距離，本文選擇了其他形式的距離度量進行組合，以擴大距離度量的適用范圍。

1組合距離表示

為了更好地表示數據點之間的距離，在距離函數中引入權重來強化有積極作用的部分，削減冗余的部分，已經成為一種常用的方法。在之前的方法中，研究者往往使用特征加權距離的方法[7]來改進聚類算法，特征加權距離的計算表達式為

受特征加權距離的啟發，引入權值將距離函數改寫為若干候選距離的線性組合，將特征加權改為距離加權，從而強化對某一數據集有更好度量效果的距離分量。

本文通過以下線性組合來表示數據集中的距離度量：

(1)

式中：D(xa,xb)表示數據點xa到數據點xb之間的距離，它由p個距離分量組成，di(xa,xb)是其第i個距離分量，ωi是第i個距離分量所對應的權值。ωi需要滿足各個分量權值均為正且和為1的條件。

2基于最大間隔理論的距離學習

2.1距離學習方法

統計學習中常用的經驗風險最小化并不能保證良好的泛化性能，因此間隔理論[9]就伴隨著過擬合的問題研究被提出，并逐漸成為機器學習領域中的一個重要評價標準。本文依據最大間隔理論并受L2-SVM方法[10]和文獻[2]的啟發，構建目標函數如式(2)：

(2)

本文的目標是通過優化該目標函數求得距離分量的權值ωi，下面將具體介紹求解ωi的方法。為了求解上述優化問題，將它作為原始最優化問題，應用拉格朗日對偶性，通過求解對偶問題得到原始問題的最優解。接下來將介紹具體求解過程。

首先，構建拉格朗日函數如式(3)：

(3)

如果此時考慮式(2)中ωi≥0的約束條件，并將該條件加入拉格朗日函數，則得到

將該拉格朗日函數分別對ωi、β、ρ、ξk、λ求偏導，并令其等于0得到

(4)

顯然由方程組(4)無法求得ωi，因此本文先暫時不考慮ωi≥0的約束條件，使用式(3)進行后續的求解。

根據拉格朗日對偶性，原始問題的對偶問題是極大極小問題：

所以，需要先求L(ω,β,ξ,α,λ)對于ω、λ的極小值。

將拉格朗日函數式(5)分別對ωi、β、ρ、ξk、λ求偏導，并令其等于0得到

(5)

進而得到

(6)

(7)

(8)

(9)

(10)

將式(6)代入式(10)得到

(11)

進而，將式(11)代入式(6)得到

(12)

將式(7)~(10)、(12)代入拉格朗日函數(3)中，即得

即

(13)

將式(13)的目標函數由求極大轉換為求極小，就得到下面與之等價的對偶最優化問題：

可以明顯地觀察到，即使成功的優化得到最優解，也不能保證ωi完全滿足式(2)中ωi≥0的約束條件，受PFC算法[11]的啟發，在之前的基礎上對ωi做如下修改：

(14)

式中：

至此完成求解距離分量權值ωi的目標，求解集合p+和p-的算法描述將在下一小節給出。

2.2算法描述

本節將給出求解距離分量權值ωi的具體算法步驟。

為了便于表示，將式(14)簡化：

(15)

式中：

(16)

由式(16)觀察可得，若想滿足ωi為正值，則Vi需要足夠大，且當Vi越大，ωi為正值的幾率就越大。因此，求解集合p+和p-的算法總結如下。

算法 1求解集合p+和p-。

算法 2 學習距離函數。

輸入：

1)數據矩陣：X∈Rd×N；

3)參數：C、θ；

輸出：距離權值：ω；

方法：

1)初始化：ω=ω(0)；

2)計算距離矩陣：D(i,k)；

3)計算二次規劃參數H和f：

H=

5)計算集合p+和p-：算法1；

6)利用式(15)計算ω。

3實驗

為了與傳統FCM算法之間有可比性，本文將簡單的以學習得到的距離函數替換傳統FCM算法中的歐式距離。根據傳統FCM算法的實現方法，本文將通過以下步驟實現聚類：

3)計算價值函數：

當其相對于上次價值函數值的改變量小于某個閾值時，算法停止。

4)更新隸屬度矩陣：

其中對于樣本點xj，它與聚類中心ci之間的距離使用如下公式計算：

將上述聚類算法記為基于組合距離(hybriddistance)的FCM聚類算法(HDFCM)。

本節將上述HDFCM算法與已有的經典距離學習算法進行對比與分析。

3.1實驗設置

本文使用了8個來自UCI機器學習數據庫的真實數據集。其中4個為二類數據集，其余4個為多類數據集。各個數據集的信息如表1所示。

表1　實驗中使用的數據集信息

在數據集的選擇上基于以下考慮：首先，這些數據集的特征數和類別數都各不相同。另外，這些數據集是機器學習研究中被廣泛使用的基準數據集，因而具有代表性。最后，由于數據集均為真實數據集，因此可以檢驗算法在真實應用中是否可行。

在組合距離分量的選擇上，本文依據第2節的理論，在實驗中選取如下10個距離度量進行組合：

在使用組合距離進行聚類的算法中，本文將依據數據集的類別數給定聚類數目，初始隸屬度矩陣隨機生成。為了保證可比性，實驗中所有的對比算法將使用相同的初始隸屬度矩陣，訓練集和其他參數(m=2,ε=10-5,T=100,C=10-5)。實驗將重復每個聚類過程20次，實驗結果取其均值。

為了評估聚類效果，采用一種類似F1-measure的成對約束評價方法，評價參數包括：pairwise Precision，pairwise Recall和pairwise F1，定義為[2]

式中：#TruePositive為將正約束對預測為正約束對的個數，#FalsePositive為將負約束對預測為正約束對的個數，#FalseNegative為將正約束對預測為負約束對的個數。由于該評價方法的對象為約束對，因此不僅可以應用于二分類的評價，也可應用于多類分類的評價。

3.2對比算法

本文使用了若干經典距離學習算法進行對比，包括：使用歐式距離的傳統FCM算法(FCM)，使用歐氏距離但含有約束條件的K-均值聚類算法(C-Euc)[12]，基于凸優化的全局距離學習算法(PGDM)[3]。

與本文提出的算法類似，C-Euc算法也是一種利用邊信息進行距離學習的半監督聚類算法，它在傳統K-均值算法的基礎上加上成對約束，在這些約束的監督下進行聚類。C-Euc算法在聚類的過程中要求每一次劃分都滿足已知的約束條件，每個樣本在沒有違反約束條件的情況下，被劃分給最近的類，最終得到的聚類結果將滿足所有的約束對信息[13]。

PGDM算法由Xing等提出，是一種基于凸優化的全局距離度量學習算法。它將正約束對構成的集合記為S，負約束對構成的集合記為D。通過以下凸優化問題對距離矩陣A進行求解：

3.3實驗結果與分析

對于各個數據集，本文所提出算法與其他算法在8個數據集上的實驗結果對比如圖1所示，其中每一個子圖的縱坐標表示了各個算法在相同參數下在該數據集上的聚類效果的評價指標均值，橫坐標上的柱形分為3組，每一組分別表示F1、precsion和recall。每個顏色代表一個算法，從左至右分別為FCM算法[14]，C-Euc算法[12]，PGDM-Ad算法[3]，PGDM-Af算法[3]和HDFCM算法，數據集名稱標注在圖標題上。表2展示了本文算法相對于傳統FCM算法聚類效果的提升率，提升率使用如下公式計算得到：

從圖1可以看出，本文提出的算法在大部分數據集上獲得了最好的表現。相對于其他距離學習算法而言，本文算法在sonar數據集和cmc數據集中雖未獲得最好的表現，但是結合表2可以發現本文算法的聚類效果相對于傳統FCM算法仍有一定的提升。由于本文使用的距離分量有限，因此對于不同的數據集不一定能擬合出最適合于該數據集的距離度量。此外，從表2可以觀察到，本文算法在breast數據集和wine數據集上有相當卓越的表現。

結合圖1和表1可以得出，本文算法不僅適用于2類數據集，對于多類數據集也有較好的聚類效果。比如，2類數據集breast，3類數據集wine，7類數據集segment在聚類效果上均取得了30%以上的提升。

圖1　算法對比圖Fig.1　Clustering performance comparison

表2　本文算法相對于傳統FCM的提升率

由于傳統FCM算法使用的是歐式距離，且其為無監督聚類算法，因此在應用的過程中不一定適合所有類型的數據集。而C-Euc算法雖然引入了數據集的邊信息，但是其使用的距離度量仍然為歐氏距離，因此在使用的時候也具有局限性。PGDM在引入了邊信息的基礎上學習出了新的距離度量，但是該距離函數仍是在馬氏距離定義框架下的距離度量，屬于線性的距離學習方法。本文提出的算法不僅引入了數據集的邊信息，而且組合了預設的多種形式的距離度量，學習得到一個非線性的距離度量，使其對于數據集有較好的適應性。上述實驗可以證明本文算法的有效性。

4結束語

本文提出了一種基于線性組合的混合距離學習算法。該算法構建了一個由若干候選距離線性組合而成的距離目標函數，利用數據集的邊信息學習得到各候選距離對應權值，從而得到新的距離函數。本文將學習得到的距離函數應用于模糊C均值算法中以構成一個半監督聚類算法。通過使用UCI真實數據集將該半監督聚類算法的聚類效果與其他距離學習算法進行對比，證明了本文算法的有效性。

參考文獻:

[1]王駿, 王士同. 基于混合距離學習的雙指數模糊C均值算法[J]. 軟件學報, 2010, 21(8): 1878-1888.

WANG Jun, WANG Shitong. Double indices FCM algorithm based on hybrid distance metric learning[J]. Journal of Software, 2010, 21(8): 1878-1888.

[2]WU Lei, HOI S C H, JIN Rong, et al. Learning Bregman distance functions for semi-supervised clustering[J]. IEEE Transactions on Knowledge and Data Engineering, 2012, 24(3): 478-491.

[3]XING E P, NG A Y, JORDAN M I, et al. Distance metric learning with application to clustering with side information[C]//Advances in Neural Information Processing Systems. Vancouver, Canada, 2002: 521-528.

[4]HOI S C H, LIU Wei, LYU M R, et al. Learning distance metrics with contextual constraints for image retrieval[C]//Proceedings of 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. New York, America, 2006, 2: 2072-2078.

[5]GOLDBERGER J, HINTON G, ROWEIS S, et al. Neighborhood component analysis[C]//Advances in Neural Information Processing Systems. Cambridge, United Kingdom, 2005: 451-458.

[6]WEINBERGER K Q, BLITZER J C, SAUL L K. Distance metric learning for large margin nearest neighbor classification[C]//Advances in Neural Information Processing Systems. Cambridge, United Kingdom, 2006: 1473-1480.

[7]王駿, 王士同, 鄧趙紅. 特征加權距離與軟子空間學習相結合的文本聚類新方法[J]. 計算機學報, 2012, 35(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 algorithms[J]. Pattern Recognition, 2002, 35(10): 2267-2278.

[9]CORTES C, VAPNIK V. Support-vector networks[J]. Machine Learning, 1995, 20(3): 273-297.

[10]TSANG I W H, KWOK J T Y, ZURADA J A. Generalized Core Vector Machines[J]. IEEE Transaction on Neural Networks, 2006, 17(5): 1126-1140.

[11]MEI Jianping, CHEN Lihui. Fuzzy clustering with weighted medoids for relational data[J]. Pattern Recognition, 2010, 43(5): 1964-1974.

[12]WAGSTAFF K, CARDIE C, ROGERS S, et al. Constrained k-means clustering with background knowledge[C]//BAR-HILLEL A, HERTZ T, SHENTAL N, et al. Proceedings of the Eighteenth International Conference on Machine Learning. Williamstown, Australia,2001: 577-584.

[14]BEZDEK J C. Pattern recognition with fuzzy objective function algorithms[M]. New York: Plenum Press, 1981: 56-57.

郭瑛潔，女，1991生，碩士研究生，主要研究方向為人工智能、模式識別。

王士同，男，1964生，教授，博士生導師，主要研究方向為人工智能、模式識別和生物信息。

許小龍，男，1989生，碩士研究生，主要研究方向為人工智能、模式識別。

網絡出版地址：http://www.cnki.net/kcms/detail/23.1538.tp.20151111.1633.006.html

英文引用格式：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

作者簡介：

通信作者：郭瑛潔. E-mail：yingdm@163.com.

基金項目：國家自然科學基金資助項目(61272210);江蘇省自然科學基金資助項目(BK2011417, BK2011003).

收稿日期：2015-04-19. 網絡出版日期：2015-11-11.

中圖分類號：TP181

文獻標志碼：A

文章編號：1673-4785(2015)06-0843-08

DOI:10.11992/tis.201504027