郭瑛潔，王士同

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

ISSN 1673-9418 CODEN JKYTA8

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

?

利用邊信息的混合距離學(xué)習(xí)算法*

郭瑛潔+，王士同

江南大學(xué)數(shù)字媒體學(xué)院，江蘇無(wú)錫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 (國(guó)家自然科學(xué)基金). Received 2015-05,Accepted 2015-08.

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

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

關(guān)鍵詞：距離學(xué)習(xí)；混合距離；距離函數(shù)；邊信息

1　引言

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

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

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

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

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

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

本文組織結(jié)構(gòu)如下：第2章提出了一種距離學(xué)習(xí)的新方法——利用邊信息學(xué)習(xí)基于線性組合的混合距離，并給出了求解距離分量對(duì)應(yīng)權(quán)值的公式與方法；第3章將學(xué)習(xí)得到的距離函數(shù)應(yīng)用于聚類算法中；第4章給出了算法的對(duì)比實(shí)驗(yàn)，通過(guò)實(shí)驗(yàn)說(shuō)明本文方法的有效性；第5章給出結(jié)論。

2　混合距離學(xué)習(xí)

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

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

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

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

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

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

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

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

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

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

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

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

距離分量越多越能夠擬合出好的距離函數(shù)，而越多的距離分量會(huì)導(dǎo)致距離學(xué)習(xí)的計(jì)算量增加。為了更好地?cái)M合出合適的距離函數(shù)，在考慮學(xué)習(xí)效率的前提下，本文預(yù)設(shè)10個(gè)經(jīng)典的距離度量進(jìn)行組合以學(xué)習(xí)得到一個(gè)新的距離函數(shù)。這10個(gè)距離度量如下：

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

2.2混合距離學(xué)習(xí)

在距離學(xué)習(xí)的過(guò)程中，借鑒文獻(xiàn)[1]的思想，利用最大間隔的框架優(yōu)化以下目標(biāo)函數(shù)：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

通過(guò)構(gòu)建拉格朗日函數(shù)和梯度下降的方法對(duì)目標(biāo)函數(shù)進(jìn)行優(yōu)化，完成了距離學(xué)習(xí)。下面將詳細(xì)描述求解權(quán)值ωi的過(guò)程。

2.3算法描述

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

因而，式（12）被簡(jiǎn)化為：

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

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

h-1

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

h

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

算法2學(xué)習(xí)距離函數(shù)

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

輸出：距離權(quán)值ω；閾值β。

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

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

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

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

4.1更新學(xué)習(xí)率：γ=1/t， t=t+1

4.2更新訓(xùn)練集子集：

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

4.3計(jì)算梯度：?βJ=Cyk

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

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

4.6更新ω

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

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

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

一般來(lái)說(shuō)，學(xué)習(xí)得到的距離函數(shù)可以被應(yīng)用在任何需要距離度量的應(yīng)用中。下面會(huì)將上文學(xué)習(xí)得到的距離函數(shù)應(yīng)用在k-means聚類算法[13]中以檢驗(yàn)距離函數(shù)。

3.1 P2C混合距離k-means聚類

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

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

（2）更新每一個(gè)類的聚類中心。

對(duì)于每一個(gè)樣本點(diǎn)xq，使用以下公式計(jì)算它與聚類中心wl之間的距離：

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

3.2 P2P混合距離k-means聚類

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

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

算法3點(diǎn)到點(diǎn)的混合距離k-means（HDK-P2P）

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

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

1.設(shè)置t=0

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

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

2.2計(jì)算聚類分配：

2.3更新聚類結(jié)果：

end for

t=t+1

4　實(shí)驗(yàn)

本文通過(guò)將距離函數(shù)應(yīng)用在聚類算法中的表現(xiàn)來(lái)評(píng)價(jià)該距離函數(shù)。下面將本文提出的距離學(xué)習(xí)算法與其他距離學(xué)習(xí)算法進(jìn)行對(duì)比，并均應(yīng)用于kmeans聚類算法中進(jìn)行驗(yàn)證。

4.1數(shù)據(jù)集與實(shí)驗(yàn)設(shè)置

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

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

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

在實(shí)驗(yàn)中，首先隨機(jī)選取數(shù)據(jù)集中的一個(gè)子集（比如全部數(shù)據(jù)集的10%）來(lái)生成邊信息，即根據(jù)這些樣本點(diǎn)的原有類標(biāo)來(lái)生成成對(duì)約束作為訓(xùn)練集。其中，擁有相同類標(biāo)的樣本點(diǎn)之間生成正約束對(duì)，擁有不同類標(biāo)的樣本點(diǎn)之間生成負(fù)約束對(duì)。生成全部的正約束對(duì)，再隨機(jī)抽取相同數(shù)目的負(fù)約束對(duì)。

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

4.2對(duì)比算法

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

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

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

4.3評(píng)價(jià)方法

為了評(píng)估聚類效果，本文采用一些標(biāo)準(zhǔn)的評(píng)價(jià)方法，包括Precision、Recall和F1[18]。定義如下：

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

4.4實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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

Table 2　 Evaluation of clustering performance表2　聚類性能對(duì)比

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

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

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

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

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

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

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

5　結(jié)束語(yǔ)

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

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.

附中文參考文獻(xiàn)：

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

[8]王駿,王士同,鄧趙紅.特征加權(quán)距離與軟子空間學(xué)習(xí)相結(jié)合的文本聚類新方法[J].計(jì)算機(jī)學(xué)報(bào), 2012, 35(8): 1655-1665.

[15]董俊,王鎖萍,熊范綸.可變相似性度量的近鄰傳播聚類[J].電子與信息學(xué)報(bào), 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—），女，河南信陽(yáng)人，江南大學(xué)碩士研究生，主要研究領(lǐng)域?yàn)閿?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—），男，江蘇揚(yáng)州人，江南大學(xué)教授、博士生導(dǎo)師，主要研究領(lǐng)域?yàn)槿斯ぶ悄芘c模式識(shí)別，圖像處理及應(yīng)用。在國(guó)內(nèi)外重要核心期刊上發(fā)表論文近百篇，其中SCI、EI收錄50余篇，主持或參加過(guò)6項(xiàng)國(guó)家自然科學(xué)基金，1項(xiàng)國(guó)家教委優(yōu)秀青年教師基金項(xiàng)目，其他省部級(jí)科研項(xiàng)目10多項(xiàng)。先后獲國(guó)家教委、中船總公司和江蘇省省部級(jí)科技進(jìn)步獎(jiǎng)5項(xiàng)。

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

文獻(xiàn)標(biāo)志碼：A

中圖分類號(hào)：TP181