郭瑛潔，王士同

江南大學數(shù)字媒體學院，江蘇無錫214122

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology 1673-9418/2016/10(03)-0414-11

?

利用邊信息的混合距離學習算法*

郭瑛潔+，王士同

江南大學數(shù)字媒體學院，江蘇無錫214122

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology 1673-9418/2016/10(03)-0414-11

E-mail: fcst@vip.163.com

http://www.ceaj.org

Tel: +86-10-89056056

* The National Natural Science Foundation of China under Grant No. 61272210 (國家自然科學基金). Received 2015-05,Accepted 2015-08.

CNKI網(wǎng)絡優(yōu)先出版: 2015-08-28, http://www.cnki.net/kcms/detail/11.5602.TP.20150828.1604.010.html

摘要：使用邊信息進行距離學習的方法在許多數(shù)據(jù)挖掘應用中占有重要位置，而傳統(tǒng)的距離學習算法通常使用馬氏距離形式的距離函數(shù)從而具有一定的局限性。提出了一種基于混合距離進行距離學習的方法，數(shù)據(jù)集的未知距離度量被表示為若干候選距離的線性組合，利用數(shù)據(jù)的邊信息學習得到各距離所占權值從而得到新的距離函數(shù)，并將該距離函數(shù)應用于聚類算法以驗證其有效性。通過與其他已有的距離學習方法進行對比，基于UCI（University of California，Irvine）數(shù)據(jù)集的實驗結果證明了該算法具有明顯的優(yōu)勢。

關鍵詞：距離學習；混合距離；距離函數(shù)；邊信息

1　引言

合適的距離度量在數(shù)據(jù)挖掘和機器學習領域占有重要的位置，是科學和工程領域中的基礎問題，對許多應用都有著重要的影響，比如信息檢索、基于內(nèi)容的圖像視頻檢索、手寫識別等。

在眾多的數(shù)據(jù)挖掘應用中，使用最多的距離度量是歐氏距離。但是采用歐氏距離的方法通常先假設所有的變量都是不相關的，并且數(shù)據(jù)所有維度的方差為1，所有變量的協(xié)方差為0[1]。然而這些條件在實際應用中很難實現(xiàn)。此外，歐氏距離僅適用于特征空間中超球結構的數(shù)據(jù)集，對超立方體結構、超橢球結構的數(shù)據(jù)集效果不太理想[2]。因此，在許多實際應用中，歐氏距離并不是最理想的選擇。

針對這些問題，近年來在數(shù)據(jù)挖掘和機器學習領域已經(jīng)提出了多種方法來學習數(shù)據(jù)集中的未知距離。研究者們嘗試自動地從數(shù)據(jù)集中學習新的距離函數(shù)來替代歐式距離。

在眾多的距離學習方法中，有一類方法利用數(shù)據(jù)的邊信息來進行距離學習，而其中邊信息通常以成對約束的形式來表示[3]。與用來訓練分類模型的類標不同的是，由成對約束表示的邊信息在實際應用中更容易獲得，且付出的代價更少。比如，對于多媒體應用，邊信息可以從用戶的相關反饋日志中獲得。

在之前的研究中，人們提出了許多利用邊信息進行距離學習的方法，比如將距離學習轉化為凸優(yōu)化問題的方法[4]、相關成分分析法[5]、區(qū)分成分分析法[6]等。然而這些方法大多數(shù)都將目標距離函數(shù)假設在馬氏距離定義的框架下，即給定兩個點x、y，它們之間的距離公式為d(x，y)=(x-y)TA(x-y)。其中，矩陣A為要學習的距離矩陣。如果A取單位矩陣I，則以上公式表示歐式距離。因此，本質上來說，針對馬氏距離學習得到的新距離是歐式距離的線性變換。這些距離在數(shù)據(jù)集結構和特點未知的情況下，不一定能很好地表示數(shù)據(jù)點之間的遠近。

針對這些問題，本文提出了一種新的距離學習方法。與傳統(tǒng)的距離學習方法不同的是，本文方法沒有局限于學習馬氏距離形式的距離度量，而是將適合于數(shù)據(jù)集的未知距離表示為若干候選距離的線性組合，其中未知距離的權值將通過數(shù)據(jù)的邊信息學習得到。在候選距離的選擇上采用了一些非線性的距離度量進行組合，以提升聚類效果。

本文組織結構如下：第2章提出了一種距離學習的新方法——利用邊信息學習基于線性組合的混合距離，并給出了求解距離分量對應權值的公式與方法；第3章將學習得到的距離函數(shù)應用于聚類算法中；第4章給出了算法的對比實驗，通過實驗說明本文方法的有效性；第5章給出結論。

2　混合距離學習

2.1基于線性組合的混合距離

由于不同數(shù)據(jù)集的結構和特點不同，為了合理地計算不同數(shù)據(jù)集之間的距離，在聚類過程或距離函數(shù)中引入權重已經(jīng)成為一種常用的方法。通過學習得到的權重可以強化重要的特征或距離，削減冗余的信息。比如，通過特征加權的方式來優(yōu)化聚類算法[7]，在距離函數(shù)中加入特征權重的方法[8]，組合距離的方法[2]等。

本文通過以下線性組合來表示數(shù)據(jù)集中的位置距離度量：

其中，D(x，y)表示數(shù)據(jù)點x到數(shù)據(jù)點y之間的距離，由p個距離分量組成；di(x，y)是其第i個距離分量；ωi是第i個距離分量對應的權值。

距離度量D(x，y)本質上是一個函數(shù)，給出了兩個模式之間標量距離的大小。對于任意的向量x、y、z，距離度量函數(shù)應滿足如下性質[9]：

（1）非負性，D(x，y)≥0；

（2）自反性，D(x，y)=0當且僅當x=y；

（3）對稱性，D(x，y)=D(y，x)；

（4）三角不等式，D(x，y)≤D(x，z)+D(z，y)。

定理如果di(x，y)是一個距離，則其線性組合D(x，y)=ωidi(x，y)也是一個距離。

證明條件（1）、條件（2）、條件（3）易證。以下將證明線性組合距離滿足條件（4）：

即D(x，y)≤D(x，z)+D(z，y)。因此，線性組合D(x，y)是一個距離。

距離分量越多越能夠擬合出好的距離函數(shù)，而越多的距離分量會導致距離學習的計算量增加。為了更好地擬合出合適的距離函數(shù)，在考慮學習效率的前提下，本文預設10個經(jīng)典的距離度量進行組合以學習得到一個新的距離函數(shù)。這10個距離度量如下：

對于距離分量的選取，出于以下考慮：首先，歐式距離d1(x，y)并沒有考慮到數(shù)據(jù)集各個維度的特征，因此使用若干含有方差的距離分量以保留數(shù)據(jù)各特征分量上的特征，如距離分量d2(x，y)、d3(x，y)。其次，這些距離均為基于歐式的距離度量，對其進行線性組合后，得到的距離函數(shù)仍為馬氏距離，因此根據(jù)Wu等人提出的新距離[10]，本文給出了距離分量d6(x，y)~d10(x，y)。這些距離均為非線性的距離度量，如此便可以組成非線性的距離函數(shù)。曼哈頓距離可以視為數(shù)據(jù)點之間在各個維度的平均差，它在一定程度上使得離群點的影響減弱，因此本文加入曼哈頓距離d4(x，y)、d5(x，y)以增加距離分量的多樣性。

2.2混合距離學習

在距離學習的過程中，借鑒文獻[1]的思想，利用最大間隔的框架優(yōu)化以下目標函數(shù)：

由上述公式可以看到，距離學習問題被轉化為帶有約束條件的優(yōu)化問題，可以使用拉格朗日乘子法對式（2）所表示的優(yōu)化問題進行求解，所得到的拉格朗日函數(shù)如下：

其中，λ和?i為拉格朗日乘子。則式（3）的最優(yōu)化（Karush-Kuhn-Tucker，KKT）條件為：

顯然由方程組（4）無法求得ωi，因此本文先暫時舍棄ωi非負的條件，構建如下拉格朗日函數(shù)：

對上述拉格朗日函數(shù)進行求解得到：

求解方程組（6）分別得到如下等式：

將式（7）代入式（9）得到：

再將式（10）代入式（7）得到：

由式（11）可以明顯看到，即使在成功的優(yōu)化過程中ωi也可能會出現(xiàn)負值。由前文可知，在考慮ωi非負條件的情況下，無法通過構建拉格朗日函數(shù)求解。因此，受加權中心模糊聚類算法[11]的啟發(fā)，將ωi的解改寫為：其中，p+表示所有使得ωi取正值的i的集合；p-表示無法使ωi取正值的i的集合。本文使用|p+|和|p-|來分別表示集合p+和p-的大小。

求解集合p+和p-的細節(jié)將在算法1中給出。

對于閾值β，使用梯度下降的方法進行求解，通過對式（2）進行求導，得到β的梯度如下：為了滿足式（2）中的約束條件ykωidi()-β)>0，參考式（12）的表示方式，將符合約束條件的yk使用集合n+={yk?D: ykωidi(，)-β) >0}表示，重新定義了β的梯度公式：

其中，|n+|表示集合n+的大小。

因此，根據(jù)梯度下降，新的解β′可被表示如下：

β′=β-γ?βJ（16）其中，γ表示梯度下降的學習速率，本文參考Pegasos Algorithm[12]中的方法，設置γ=1/t。

由于在求解β的過程中集合n+在不斷改變，進一步修改式（12）為如下形式：

通過構建拉格朗日函數(shù)和梯度下降的方法對目標函數(shù)進行優(yōu)化，完成了距離學習。下面將詳細描述求解權值ωi的過程。

2.3算法描述

為了便于求解集合p+和p-，給出如下定義：

因而，式（12）被簡化為：

由式（19）顯然可得，當Ei越大，則ωi為正值的幾率越大。因此，求解集合p+和p-的算法總結如下。

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

h-1

3.通過式（19）計算ωg并判斷其是否大于0，其中g= argmini ?p+{Ei}。如果ωg>0則回到步驟2，否則設置p+=

h

下面將介紹求解權值ωi的算法。其中初始化ωi的方法比較簡單，令==...=，根據(jù)式（2）中的約束條件有=1/p。而對于閾值β的初值設定，隨機取一些點，在初始權值下取距離的最大值作為β的初值。

算法2學習距離函數(shù)

輸入：數(shù)據(jù)矩陣X?Rd′N；成對約束(，yk)，其中yk={+1，-1}；懲罰因子C。

輸出：距離權值ω；閾值β。

1.初始化：ω=ω(0)， β=β(0)

2.計算距離矩陣：D(i，k)

3.設置迭代步數(shù)：t=1

4.循環(huán)，直至收斂，即ω的值不再變化

4.1更新學習率：γ=1/t， t=t+1

4.2更新訓練集子集：

n+={yk?D: ykωidi(，)-β) >0}

4.3計算梯度：?βJ=Cyk

4.4更新閾值：β′=β-γ?βJ

4.5更新集合p+和p-：算法1

4.6更新ω

通過以上算法即可求出參數(shù)ωi，進而得到新的距離函數(shù)。

由上述算法步驟可知，混合距離學習算法的時間復雜度為O(pT1n+pT2n)，其中p為待組合的距離分量的個數(shù)，n為成對約束的個數(shù)，T1為算法1中收斂時的迭代次數(shù)，T2為算法2中收斂時的迭代次數(shù)。下面將介紹如何將距離函數(shù)應用在聚類算法中。

3　半監(jiān)督聚類應用

一般來說，學習得到的距離函數(shù)可以被應用在任何需要距離度量的應用中。下面會將上文學習得到的距離函數(shù)應用在k-means聚類算法[13]中以檢驗距離函數(shù)。

3.1 P2C混合距離k-means聚類

一種簡單的方法是直接將傳統(tǒng)k-means算法中的歐氏距離用混合距離函數(shù)替換掉。因此，根據(jù)傳統(tǒng)的k-means聚類算法，可以通過以下兩步迭代實現(xiàn)聚類：

（1）使用混合距離函數(shù)將每一個點分配至距離它最近的類中，以形成k個類；

（2）更新每一個類的聚類中心。

對于每一個樣本點xq，使用以下公式計算它與聚類中心wl之間的距離：

在上述聚類算法中，通過混合距離函數(shù)來計算樣本點與聚類中心之間的距離，本文將該算法記為點到中心的混合距離k-means聚類算法（point-to-centroid hybrid distance k-means clustering method，HDK-P2C）。

3.2 P2P混合距離k-means聚類

與傳統(tǒng)的k-means聚類算法相似，上述P2C混合距離聚類算法通過每個類的聚類中心來表示這個類，這也就暗中假設了數(shù)據(jù)集為球形結構，然而并不是所有的真實數(shù)據(jù)集都滿足該結構。為了解決這種限制，受文獻[1]啟發(fā)，本文將距離函數(shù)應用在了另一種點到點的k-means聚類算法（point-to-point hybrid distance k-means clustering method，HDK-P2P），該算法并未假設數(shù)據(jù)集為球形結構。相似的想法在之前的聚類研究中也被提出過，比如凝聚層次聚類[14]和近鄰傳播聚類[15]。

與HDK-P2C方法不同的是，HDK-P2P聚類算法是通過計算樣本點xq到類Wl中所有點的平均距離來衡量點xq到類Wl的親近度。由于不需要在聚類過程中不斷更新聚類中心，并且點到點的距離可以在聚類之前就計算完畢存儲起來，HDK-P2P算法的效率要高于HDK-P2C算法。其具體實現(xiàn)步驟如下：

算法3點到點的混合距離k-means（HDK-P2P）

輸入：數(shù)據(jù)矩陣Xtest?Rd′Nt；權值向量ω；聚類數(shù)目k；聚類中心cen ?Rd′k。

輸出：分類結果W={Wl}=1，Wl的聚類中心是wl。

1.設置t=0

2.循環(huán)，直至聚類中心不再改變

for q=1，2，...，Nt do

2.2計算聚類分配：

2.3更新聚類結果：

end for

t=t+1

4　實驗

本文通過將距離函數(shù)應用在聚類算法中的表現(xiàn)來評價該距離函數(shù)。下面將本文提出的距離學習算法與其他距離學習算法進行對比，并均應用于kmeans聚類算法中進行驗證。

4.1數(shù)據(jù)集與實驗設置

實驗數(shù)據(jù)集包含了12個來自UCI（University of California，Irvine）的真實數(shù)據(jù)集。其中7個為二類數(shù)據(jù)集，另外5個為多類數(shù)據(jù)集。各數(shù)據(jù)集的細節(jié)如表1。

Table 1　　 List of datasets表1　實驗中使用的數(shù)據(jù)集信息

本文選擇這些數(shù)據(jù)集對算法進行測試是基于以下考慮。首先，這些數(shù)據(jù)集都擁有不同的性質，它們的類別數(shù)與特征數(shù)都不盡相同。再者，這些數(shù)據(jù)集作為基準數(shù)據(jù)集被廣泛應用在機器學習的各項應用中。最后，它們都是真實的數(shù)據(jù)集，這些真實數(shù)據(jù)集可以驗證本文算法在真實應用中是否可行。

在實驗中，首先隨機選取數(shù)據(jù)集中的一個子集（比如全部數(shù)據(jù)集的10%）來生成邊信息，即根據(jù)這些樣本點的原有類標來生成成對約束作為訓練集。其中，擁有相同類標的樣本點之間生成正約束對，擁有不同類標的樣本點之間生成負約束對。生成全部的正約束對，再隨機抽取相同數(shù)目的負約束對。

根據(jù)成對約束學習得到新的距離函數(shù)后，將其應用在全部的數(shù)據(jù)集中進行聚類。在聚類算法中，聚類數(shù)目依據(jù)數(shù)據(jù)集的類別數(shù)給定，初始聚類中心從數(shù)據(jù)集中隨機抽取。為了保證可比性，本文所有的對比算法都將使用相同的初始聚類中心。重復每個聚類過程20次，實驗結果取20次結果的均值。

4.2對比算法

本文將兩種混合距離k-means聚類算法與已有的經(jīng)典聚類算法和距離學習算法進行對比。包括以下算法：使用歐式距離的經(jīng)典k-means聚類算法（k-means with Euclidian distance，Euc），使用歐式距離含有約束條件的k-means聚類算法（constrained k-means with Euclidian distance，C-Euc）[16]，通過凸優(yōu)化算法學習得到的全局距離度量進行k-means聚類的算法（probabilistic global distance metric learning，PGDM）[4]。

與本文提出的算法類似，使用歐式距離含有約束條件的k-means聚類算法（C-Euc）也是一種常用的利用邊信息的半監(jiān)督聚類算法。它在傳統(tǒng)k-means算法的基礎上加上成對約束，在這些約束的“監(jiān)督”下進行聚類。選擇k個初始聚類中心，進入類似k-means算法的迭代過程，在迭代過程中始終要求每一步劃分都滿足己知的約束對信息，每個樣本在沒有違反成對約束條件下，被劃分給最近的類，最終得到滿足所有約束對信息的聚類結果[17]。

PGDM算法由Xing等人提出，是一種基于凸規(guī)劃的全局距離度量學習算法。它將正約束對構成的集合記為S，負約束對構成的集合記為D。待求的距離矩陣A就可以通過以下凸規(guī)劃問題進行求解：其中，||xi，xj=(xiA(xi，xj)表示兩個樣本點xi和xj之間的距離。根據(jù)預期得到的矩陣A的不同可以有不同的解法。如果期望得到對角形式的距離矩陣，可以通過牛頓法進行求解，本文將此算法記為PGDM-Ad（PGDM with diagonal A）。如果期待得到普通矩陣形式的距離矩陣，那么可以通過梯度下降加上逐次映射的方法進行求解，本文將此算法記為PGDM-Af（PGDM with full A）。在實驗中，將學習得到的距離矩陣和其他算法一樣應用于k-means聚類算法中進行評價。

4.3評價方法

為了評估聚類效果，本文采用一些標準的評價方法，包括Precision、Recall和F1[18]。定義如下：

其中，#True Positive表示將正約束對預測為正約束對的個數(shù)；#False Positive表示將負約束對預測為正約束對的個數(shù)；#False Negative表示將正約束對預測為負約束對的個數(shù)。

4.4實驗結果與分析

本文所有實驗均在Matlab平臺下進行，所有訓練數(shù)據(jù)集和測試數(shù)據(jù)集均先歸一化至[0,1]區(qū)間內(nèi)。對于不同的數(shù)據(jù)集和不同的算法均取相同百分比的子集構成成對約束（比如10%）。不同的距離度量均從這些成對約束中學習得到，然后均應用于k-means聚類算法中。

本文算法與其他算法實驗結果對比如表2所示。表2展示了不同算法在相同的聚類中心和等量的約束對下，聚類效果的F1指標均值。每一個數(shù)據(jù)集中，對效果最好的兩個算法的F1指標進行了加粗。圖1展示了部分聚類效果表現(xiàn)優(yōu)異的數(shù)據(jù)集的聚類效果圖。表3展示了本文算法相對于基于歐氏距離的k-means算法聚類效果的提升率。使用如下公式計算得到：

從實驗結果可以看出，本文的距離學習算法HDK-P2C和HDK-P2P在整體上有較好的表現(xiàn)，特別是從表3和圖1中可以看出在數(shù)據(jù)集breast-cancer、wine、thyroid和segment中相對于其他算法有卓越的表現(xiàn)。從表2可以看出，本文算法在大多數(shù)數(shù)據(jù)集中獲得了最好的表現(xiàn)，在利用相同數(shù)量的邊信息條件下，本文提出的距離函數(shù)應用在k-means算法中的聚類效果整體上優(yōu)于利用了同樣邊信息約束條件的CEuc算法，也優(yōu)于同樣是利用邊信息進行距離學習的PGDM算法。

由表3可以看出，雖然本文算法在pima和dermatology數(shù)據(jù)集中只取得了次優(yōu)的聚類效果，但是其相對于傳統(tǒng)的歐氏距離仍有聚類效果的提升。由此可見，本文提出的距離學習算法得到的距離函數(shù)相對于歐式距離，在聚類應用中具有更好的表現(xiàn)。

結合表1和表3也可以看到，本文算法不僅對于二類數(shù)據(jù)集有較好的聚類效果，對于多類數(shù)據(jù)集也有很好的效果。比如，數(shù)據(jù)集wine為3類數(shù)據(jù)集，數(shù)據(jù)集segment為7類數(shù)據(jù)集，它們的聚類效果都取得了30%以上的提升。

在聚類算法中，由于傳統(tǒng)的k-means聚類是無監(jiān)督的聚類方法，它沒有融入數(shù)據(jù)集的邊信息，從而對于數(shù)據(jù)集的適應性不是很好。而C-Euc算法雖然引入了數(shù)據(jù)集的邊信息，但是其使用的距離度量仍然是歐氏距離，并不適用于所有的數(shù)據(jù)集。PGDM在引入了邊信息的基礎上學習出了新的距離度量，但是該距離函數(shù)仍然是馬氏距離的形式，屬于線性的距離學習方法。本文算法不僅引入了數(shù)據(jù)的邊信息，而且組合了預設的線性距離度量和非線性距離度量以形成新的距離函數(shù)，使得其對于數(shù)據(jù)集有較好的適應性。

Table 2　 Evaluation of clustering performance表2　聚類性能對比

Fig.1　 Clustering result of a portion of datasets圖1　部分數(shù)據(jù)集的聚類效果圖

Table 3　 Upgrade of this paper algorithm表3　本文算法的提升率%

表4給出了含有約束條件的k-means在采用歐式距離和本文提出的距離函數(shù)時聚類效果F1指標的對比。這兩種方法均為有約束的聚類算法，其中采用混合距離的有約束條件的k-means聚類算法被表示為C-HD（constrained k-means with hybrid distance）?？梢钥吹?，總體來說在有約束條件的前提下，采用本文提出的距離函數(shù)的聚類算法在聚類效果上也具有更為優(yōu)秀的表現(xiàn)。

為了進一步證明本文提出的混合距離在其他典型應用中也具有較好的性能，將混合距離應用在了經(jīng)典分類算法——K最近鄰（K-nearest neighbor，KNN）分類算法中，并與使用歐氏距離的KNN分類算法進行對比。在表5中，使用歐式距離的經(jīng)典KNN算法被表示為KNN，使用混合距離的KNN算法被表示為KNN-HD（K-nearest neighbor with hybrid distance），表中的數(shù)據(jù)為分類效果的F1指標。從表5中可以看出，整體上來說，采用了混合距離的KNN算法在分類效果的表現(xiàn)上優(yōu)于使用歐式距離的KNN算法。分類算法和聚類算法類似，都是利用距離函數(shù)來判別數(shù)據(jù)點之間的相似性，因此具有較好適應性的混合距離在分類算法上也能取得較好的效果。以上實驗可以證明本文算法具有有效性。

Table 4　 Comparision between C-Euc and C-HD表4　 C-Euc算法與C-HD算法效果對比

Table 5　 Comparision between KNN and KNN-HD表5　 KNN算法和KNN-HD算法效果對比

在算法性價比方面，本文算法和利用凸優(yōu)化的距離學習算法（PGDM）都是利用數(shù)據(jù)的邊信息學習新的距離函數(shù)，而本文算法相對于PGDM算法在時間上具有明顯的優(yōu)勢，比如對于blood數(shù)據(jù)集，PGDM算法的平均用時為2.866 3 s，而本文算法用時為1.446 9 s。由于本文使用的是實驗用的數(shù)據(jù)集，在邊信息的生成上占用了一定的時間，但是在實際應用中邊信息相對于明確的類標而言更易于獲取。因此，本文算法在保證有效性的前提下，具有一定的性價比。

5　結束語

本文提出了一種利用邊信息的混合距離學習算法。首先構建了一個由候選距離線性組合而成的距離函數(shù)模型，然后利用數(shù)據(jù)的邊信息進行距離學習，得到新的距離函數(shù)，并將其應用于半監(jiān)督的k-means聚類算法中檢驗其有效性。最后，使用UCI數(shù)據(jù)集對算法的聚類效果進行了驗證，并使用F1指標來衡量，通過與其他距離學習方法和半監(jiān)督聚類算法進行對比，證明了本文算法的有效性。

References:

[1] 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.

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

[3] He Ping, Xu Xiaohua, Hu Kongfa, et al. Semi-supervised clustering via multi-level random walk[J]. Pattern Recognition, 2014, 47(2): 820-832.

[4] Xing E P, Ng AY, Jordan M I, et al. Distance metric learning with application to clustering with side information[C]// Advances in Neural Information Processing Systems 15: Proceedings of the 2003 Neural Information Processing Systems, Vancouver, Canada, Dec 8-13, 2003. Cambridge, USA: MIT Press, 2003: 505-512.

[5] Bar-Hillel A, Hertz T, Shental N, et al. Learning a Mahalanobis metric from equivalence constraints[J]. Journal of Machine Learning Research, 2005, 6(12): 937-965.

[6] Hoi S C H, Liu Wei, Lyu M R, et al. Learning distance met-rics with contextual constraints for image retrieval[C]//Proceedings of the 2006 IEEE Conference on Computer Vision and Pattern Recognition, New York, USA, 2006. Piscataway, USA: IEEE, 2006: 2072-2078.

[7] Bai Liang, Liang Jiye, Dang Chuangyin, et al. A novel attribute weighting algorithm for clustering high-dimensional categorical data[J]. Pattern Recognition, 2011, 44(12): 2843-2861.

[8] Wang Jun, Wang Shitong, Deng Zhaohong.Anovel text clustering algorithm based on feature weighting distance and soft subspace learning[J]. Chinese Journal of Computers, 2012, 35(8): 1655-1665.

[9] Duda R O, Hart P E, Stork D G. Pattern classification[M]. Toronto, Canada: John Wiley & Sons, 2012.

[10] Wu K L, Yang M S. Alternative C-means clustering algorithms[J]. Pattern Recognition, 2002, 35(10): 2267-2278.

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

[12] Shwartz S S, Singer Y, Pegasos N S. Primal estimated subgradient solver for SVM[J]. Mathematical Programming, 2011, 27(1): 807-814.

[13] Hartigan J A, Wong M A. A K-means clustering algorithm[J]. Applied Statistics, 1979, 28(1): 100-108.

[14] Beeferman D, Berger A. Agglomerative clustering of a search engine query log[C]//Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Boston, USA, Aug 20-23, 2000. New York, USA: ACM, 2000: 407-416.

[15] Dong Jun, Wang Suoping, Xiong Fanlun. Affinity propagation clustering based on variable- similarity measure[J]. Journal of Electronics & Information Technology, 2010, 32(3): 509-514.

[16] Wagstaff K, Cardie C, Rogers S, et al. Constrained k-means clustering with background knowledge[C]//Proceedings of the 18th International Conference on Machine Learning, Williamstown, USA, 2001. San Francisco, USA: Morgan Kaufmann Publishers Inc, 2001: 577-584.

[17] Covoes T F, Hruschka E R, Ghosh J.Astudy of K-means-based algorithms for constrained clustering[J]. Intelligent Data Analysis, 2013, 17(3): 485-505.

[18] Liu Yi, Jin Rong, Jain A K. Boostcluster: boosting clustering by pairwise constraints[C]//Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Jose, USA, Aug 12- 15, 2007. New York, USA:ACM, 2007: 450-459.

附中文參考文獻：

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

[8]王駿,王士同,鄧趙紅.特征加權距離與軟子空間學習相結合的文本聚類新方法[J].計算機學報, 2012, 35(8): 1655-1665.

[15]董俊,王鎖萍,熊范綸.可變相似性度量的近鄰傳播聚類[J].電子與信息學報, 2010, 32(3): 509-514.

GUO Yingjie was born in 1991. She is an M.S. candidate at Jiangnan University. Her research interests include data mining and artificial intelligence.郭瑛潔（1991—），女，河南信陽人，江南大學碩士研究生，主要研究領域為數(shù)據(jù)挖掘，人工智能。

WANG Shitong was born in 1964. He is a professor and Ph.D. supervisor at Jiangnan University. His research interests include artificial intelligence and pattern recognition, image processing and application.王士同（1964—），男，江蘇揚州人，江南大學教授、博士生導師，主要研究領域為人工智能與模式識別，圖像處理及應用。在國內(nèi)外重要核心期刊上發(fā)表論文近百篇，其中SCI、EI收錄50余篇，主持或參加過6項國家自然科學基金，1項國家教委優(yōu)秀青年教師基金項目，其他省部級科研項目10多項。先后獲國家教委、中船總公司和江蘇省省部級科技進步獎5項。

Hybrid Distance Metric Learning Method with Side-Information?

GUO Yingjie+, WANG Shitong
School of Digital Media, Jiangnan University, Wuxi, Jiangsu 214122, China
+ Corresponding author: E-mail: ying_dm@163.com

GUO Yingjie, WANG Shitong. Hybrid distance metric learning method with side- infomation. Journal of Frontiers of Computer Science and Technology, 2016, 10(3)：414-424.

Abstract:Learning distance function with side-information plays a key role in many data mining applications. Conventional metric learning approaches often use the distance function which is represented in form of Mahalanbobis distance which has some limitations. This paper proposes a new metric learning method with hybrid distance. In detail, the unknown distance metric is represented as the linear combination of several candidate distance metrics. A new distance function is achieved by learning weights with side-information. This paper applies the new distance function into clustering algorithm to verify the effectiveness. It also chooses the datasets from UCI machine learning repository to do experiments. The comparison with approaches for learning distance functions with side-information reveals the advantages of the proposed techniques.

Key words:distance metric learning; hybrid distance metric; distance function; side-information

doi:10.3778/j.issn.1673-9418.1505005

文獻標志碼：A

中圖分類號：TP181