距離度量學(xué)習(xí)算法的精確性研究

摘" 要： 距離度量學(xué)習(xí)是機(jī)器學(xué)習(xí)領(lǐng)域較為活躍的研究課題之一，文中利用UCI（加州大學(xué)歐文分校）數(shù)據(jù)庫(kù)的數(shù)據(jù)對(duì)度量學(xué)習(xí)算法進(jìn)行比較研究。為了尋找一種可靠的沒有明確定義標(biāo)志的算法，選擇四種算法在UCI的六個(gè)數(shù)據(jù)集上對(duì)距離矩陣進(jìn)行比較。每個(gè)樣本數(shù)據(jù)集的性質(zhì)（尺寸和維度）是不同的，因此算法的結(jié)果也不同。編碼相似度算法在大多數(shù)情況下表現(xiàn)良好。在未來的實(shí)際應(yīng)用領(lǐng)域，對(duì)于提高無標(biāo)記數(shù)據(jù)和相似集的距離度量學(xué)習(xí)算法的精確性提供了研究基礎(chǔ)。

關(guān)鍵詞： 距離度量學(xué)習(xí); 機(jī)器學(xué)習(xí); 距離矩陣; 馬氏距離; UCI數(shù)據(jù)庫(kù); 比較研究

中圖分類號(hào)： TN911.1?34; G231.5" " " " " " " " " "文獻(xiàn)標(biāo)識(shí)碼： A" " " " " " " " " "文章編號(hào)： 1004?373X（2019）21?0150?04

Abstracts： Distance metric learning is one of the most attractive research subjects in machine learning. The objective of this research is to compare and research the distance metric learning algorithms by using the data in UCI database. To find a reliable algorithm without any symbols with clear definition， four algorithms are selected. The comparison of distance matrixes is made on 6 datasets of UCI. The nature （size， dimension） of each dataset is different， so the algorithms′ results may vary. The coding similarity algorithm performs well in most cases. In the field of practical application in the future， the research foundation for the accuracy of metric learning algorithms is provided for unlabeled data and similar sets.

Keywords： distance metric learning; machine learning; distance matrix; Mahalanobis distance; UCI database; comparative study

0" 引" 言

距離度量學(xué)習(xí)或者稱為相似度學(xué)習(xí)，是指在給定的訓(xùn)練樣本集上，通過學(xué)習(xí)得到一個(gè)能夠有效反映數(shù)據(jù)樣本間的距離或者相似度的度量矩陣， 目的是使在新的樣本空間中，相同類別的樣本相似度更大，也就是分布更緊密;不同類別的樣本相似度更小，也就是分布更松散。距離度量學(xué)習(xí)算法[1?5]在計(jì)算機(jī)視覺及模式識(shí)別等領(lǐng)域應(yīng)用非常廣泛，對(duì)距離度量學(xué)習(xí)算法的研究已成為近年比較活躍的研究熱點(diǎn)之一，因此，該項(xiàng)研究具有重要的意義和價(jià)值。

距離度量學(xué)習(xí)算法依據(jù)不同分類標(biāo)準(zhǔn)，有多種分類方法。例如，依據(jù)學(xué)習(xí)方式的不同，可以將度量學(xué)習(xí)算法分為有監(jiān)督的距離度量學(xué)習(xí)算法[6?7]和無監(jiān)督的距離度量學(xué)習(xí)算法[7]兩類。有監(jiān)督的距離度量學(xué)習(xí)算法的主要思想是對(duì)于訓(xùn)練集的樣本信息建立優(yōu)化函數(shù)，獲得能夠合理反映樣本空間特性的度量矩陣，然后利用算法進(jìn)行訓(xùn)練。文獻(xiàn)[7]提出最大化互信息熵的思想，通過此方法進(jìn)行距離度量學(xué)習(xí)。無監(jiān)督的距離度量學(xué)習(xí)算法傾向于通過尋找集群來分散數(shù)據(jù)，對(duì)數(shù)據(jù)進(jìn)行標(biāo)記。其基本思想是將原始數(shù)據(jù)集通過降維映射到一個(gè)低維子空間中， 從而得到關(guān)于原始數(shù)據(jù)集更緊密的低維表示。文獻(xiàn)[8]提出基于AML 算法，結(jié)合核學(xué)習(xí)技術(shù)，提出非線性自適應(yīng)距離度量學(xué)習(xí)算法。文獻(xiàn)[9]提出自適應(yīng)距離度量學(xué)習(xí)（Adaptive Metric Learning，AML）算法，該算法將距離度量學(xué)習(xí)和聚類結(jié)合，將原始數(shù)據(jù)集進(jìn)行降維，形成新的更緊密的低維子空間后，再進(jìn)行距離度量學(xué)習(xí)。

本文研究主要是基于無監(jiān)督的距離度量學(xué)習(xí)算法。選擇單位矩陣、邢氏算法、信息論度量學(xué)習(xí)算法和編碼相似度算法，在選取的不同數(shù)據(jù)庫(kù)上進(jìn)行比較，對(duì)提高距離度量學(xué)習(xí)算法的精確性提供研究基礎(chǔ)，對(duì)于實(shí)際應(yīng)用中度量學(xué)習(xí)算法的選擇提供依據(jù)。

1" 算" 法

基于約束條件（未標(biāo)記的數(shù)據(jù)和相似集）選擇四種算法對(duì)距離矩陣進(jìn)行比較。這四種算法分別是：?jiǎn)挝痪仃嚮驓W幾里得距離;邢氏算法[10]（一種迭代算法）;信息論的度量學(xué)習(xí)[11]（一種迭代算法）;編碼相似度算法[12]。

四種算法可以用不同的方式確定相似性問題。

1.1" 邢氏算法

邢氏算法是可以考慮用來解決問題的最簡(jiǎn)單的算法。 一般的思路是最小化相似點(diǎn)與相異點(diǎn)之間的距離。為此考慮一個(gè)距離矩陣，并進(jìn)行優(yōu)化：

該算法的主要缺點(diǎn)是集合的收斂性不確定。有時(shí)根據(jù)數(shù)據(jù)集或初始條件可能無法計(jì)算出一個(gè)很好的結(jié)果，并被卡在一個(gè)循環(huán)中，每個(gè)迭代步驟產(chǎn)生的新矩陣都遠(yuǎn)離了前一個(gè)矩陣。在某些數(shù)據(jù)集上，還可能出現(xiàn)[A=0]，這是不應(yīng)該的。

在本文中，該算法僅運(yùn)用于學(xué)習(xí)全矩陣[13]。

1.2" 信息論的度量學(xué)習(xí)算法

式中：[ξ0]是描述相似性與差異性之間臨界值的集合;[ξi，j]是[S]或[D]中[i，j]的臨界值;[γ]控制著對(duì)任意矩陣[A0]進(jìn)行學(xué)習(xí)的矩陣與對(duì)預(yù)計(jì)算的閾值進(jìn)行調(diào)整之間的平衡問題，這個(gè)問題可以有很多參數(shù)，用來獲得更好的計(jì)算結(jié)果，但是在算法開始時(shí)，必須設(shè)定好[A0]，[ξ]和[γ] 的初始值，因?yàn)樗鼈兒茈y進(jìn)行預(yù)先估算。

1.3" 編碼相似度

編碼相似度指的是一個(gè)數(shù)據(jù)包含了另外一個(gè)數(shù)據(jù)的信息量的多少。相似度codsim[x，x]表示[x]傳遞了[x]的信息量，這是一個(gè)基于分布的方法。信息量的大小通過兩個(gè)分布之間編碼長(zhǎng)度的差異進(jìn)行評(píng)估：一個(gè)分布認(rèn)為[x]和[x]之間并不存在真正的聯(lián)系，另一個(gè)分布則認(rèn)為有。需要注意，這個(gè)算法只使用相似的數(shù)據(jù)對(duì)。編碼長(zhǎng)度為[clx-logpx]，最終計(jì)算公式為：

該算法通過降低維度避免了過擬合[9]。雖然它不需要進(jìn)行迭代，但是計(jì)算過程很復(fù)雜（逆矩陣），而且在求解逆矩陣的過程中容易出現(xiàn)一些問題。為了避免這種情況，將零特征值盡量減少。在本文的實(shí)驗(yàn)中，沒有計(jì)算出任何維度的減少。

2" 實(shí)驗(yàn)方法

在每個(gè)數(shù)據(jù)集中，給定每個(gè)數(shù)據(jù)的分類，通過相似或相異的數(shù)據(jù)對(duì)，對(duì)每個(gè)可能的數(shù)據(jù)對(duì)進(jìn)行標(biāo)記，作為算法的輸入。在此基礎(chǔ)上，進(jìn)行雙重交叉驗(yàn)證，另外還需要一個(gè)閾值來評(píng)估其相似度。本文使用的算法并沒有給出這個(gè)閾值，因此在評(píng)估過程中要篩選出一個(gè)閾值。在給定的距離矩陣和幾個(gè)閾值中，計(jì)算幾個(gè)混合矩陣。選擇閾值，以便描述有用值的整個(gè)范圍：從對(duì)相異數(shù)據(jù)的所有映射中，再到相似數(shù)據(jù)的所有映射中進(jìn)行選擇，然后計(jì)算接受者操作特征曲線（ROC），并且模型的精度由ROC曲線下半部分的面積（AUC）給出，ROC曲線如圖1所示。

對(duì)于信息論度量學(xué)習(xí)算法（ITML），需要初始化[ξ0]。按照經(jīng)驗(yàn)對(duì)它進(jìn)行初始值設(shè)定，盡管這種選擇是完全隨機(jī)的：所有數(shù)據(jù)對(duì)的距離分布中，5%為相似性，95%表現(xiàn)為相異。然后研究不連續(xù)的數(shù)據(jù)對(duì)整體結(jié)果的影響。這些集合表現(xiàn)出了精確的相似度，但人造的數(shù)據(jù)不具備這個(gè)屬性。因此，選擇通過“翻轉(zhuǎn)”一些數(shù)據(jù)對(duì)的相似度來添加一些矛盾數(shù)據(jù)。該方法不是添加新對(duì)，而是修改現(xiàn)有的對(duì)，因此數(shù)據(jù)集不具有矛盾對(duì)，但包含相似性評(píng)估錯(cuò)誤。

由于可能產(chǎn)生不一致性，在一個(gè)真正的數(shù)據(jù)集中選擇將它們從測(cè)試集中排除。人造的編碼不能選擇，這只會(huì)降低結(jié)果準(zhǔn)確性，并且對(duì)算法的比較也沒有幫助。

3" 實(shí)驗(yàn)結(jié)果

3.1" 電離層

電離層結(jié)果如表1所示。由表1可知，運(yùn)用歐幾里得定理得到的結(jié)果不理想;邢氏算法結(jié)果較好，但是當(dāng)內(nèi)部關(guān)聯(lián)數(shù)據(jù)出現(xiàn)時(shí)，健壯性較差;編碼相似度算法給出了基本一致的穩(wěn)定性。

3.2" 虹膜（IRIS）

虹膜層結(jié)果如表2所示。由表2可知，小規(guī)模的IRIS數(shù)據(jù)集的尺寸解釋了相似性準(zhǔn)確度上的急速下降。根據(jù)歐幾里得定理得出的結(jié)果，使用學(xué)習(xí)過的距離函數(shù)效果不好。

3.3" 酒" 類

酒類結(jié)果如表3所示。由表3可知，編碼相似度算法在正確的數(shù)據(jù)集上效果很好。但意外的是，邢氏算法針對(duì)錯(cuò)誤的數(shù)據(jù)卻得出最好的結(jié)果。而且這些精確度與歐幾里得距離得出的結(jié)果非常接近。

3.6" 平衡量表

平衡量表結(jié)果如表6所示。由表6數(shù)據(jù)可得出，邢氏算法出現(xiàn)很多錯(cuò)誤數(shù)據(jù)，因此至少在某一時(shí)間段或某些迭代的情況下是不能收斂的，就如同信息論度量學(xué)習(xí)算法一樣。這可能是由數(shù)據(jù)集尺寸導(dǎo)致的。

4" 結(jié)" 論

本文研究的主要結(jié)論是基于數(shù)據(jù)驅(qū)動(dòng)算法的準(zhǔn)確性中，算法并不處于主導(dǎo)地位的。此外，明確定義的集合的結(jié)果并不能代表隨機(jī)產(chǎn)生的數(shù)據(jù)集合的結(jié)果。當(dāng)沒有明確分類時(shí)，相似性的區(qū)別和分類問題值得研究。

由于真實(shí)數(shù)據(jù)集中可能存在錯(cuò)誤，可以選擇一種具有良好穩(wěn)固性的算法。實(shí)驗(yàn)證明，數(shù)據(jù)的不同特性影響到算法的結(jié)果。雖然加入非相關(guān)數(shù)據(jù)的方法是模擬部分壞數(shù)據(jù)集的一種快速而有效的方法，但無法評(píng)估相似性。相似性不能理解為二元評(píng)估（相似/不相似），也不能被視為二次函數(shù)。相似性評(píng)價(jià)的誤差可以遵循一定的模式，而不是完全隨機(jī)地分布。這些“選擇”也可以是個(gè)人的。如果測(cè)試集由某一用戶創(chuàng)建，那么距離矩陣就反映了對(duì)相似度的描述。數(shù)據(jù)可以是近距離的，也可以是連續(xù)的。此外，本文研究?jī)H限于Mahanalobis距離[3?10]。

某些算法的結(jié)果不理想，但并不應(yīng)該受到限制。比如，如果編碼相似性算法很好，就可以用來學(xué)習(xí)一個(gè)很好的距離函數(shù)，并且可以通過在線捕獲的數(shù)據(jù)（如ITML的在線版本）來調(diào)整矩陣。關(guān)于人造數(shù)據(jù)集和非二元距離的領(lǐng)域，在未來的實(shí)際應(yīng)用中還有很多值得研究的地方。

參考文獻(xiàn)

[1] BAR?HILLEL A， HERTZ T， SHENTAL N， et al. Learning a mahalanobis metric from equivalence constraints [J]. Journal of machine learning research， 2005， 6： 937?965.

[2] DAVIS J V， KULIS B， JAIN P， et al. Information?theoretic metric learning [C]// Proceedings of the 24th International Conference on Machine Learning. New York， NY， USA： ACM， 2007： 209?216.

[3] GLOBERSON A， ROWEIS S T. Metric learning by collapsing classes [C]// Advances in Neural Information Processing Systems（NIPS）. [S. l.： s.n.]， 2005： 451?458.

[4] HILLEL A B， WEINSHALL D. Learning distance function by coding similarity [C]// Proceedings of the 24th International Conference on Machine Learning. New York， NY， USA： ACM， 2007： 65?72.

[5] WANG X Y， HUA G， HAN T X. Discriminative tracking by metric learning [C]// Proceedings of the 11th European Confe?rence on Computer Vision. Heraklion， Greece： Springer， 2010： 200?214.

[6] CHEN J H， ZHAO Z， YE J P， LIU H. Nonlinear adaptive distance metric learning for clustering [C]// Proceedings of the 2007 International Conference on Knowledge Discovery and Data Mining. California， USA： ACM， 2007： 123?132.

[7] YE J P， ZHAO Z， LIU H. Adaptive distance metric learning for clustering [C]// Proceeding of the 2007 Computer Society Conference on Computer Vision and Pattern Recognition. Minnesota， USA： IEEE， 2007： 1?7.

[8] JIANG Liangxiao， CAI Zhihua， WANG Dianhong， et al. Bayesian citation?KNN with distance weighting [J]. International journal of machine learning and cybernetics， 2014， 5（2）： 193?199.

[9] 王燕，李鳳蓮，張雪英，等.改進(jìn)學(xué)習(xí)率的一種高效SVD++算法[J].現(xiàn)代電子技術(shù)，2018，41（3）：146?150.

WANG Yan， LI Fenglian， ZHANG Xueying， et al. An efficient SVD++ algorithm for learning rate improvement [J]. Modern electronics technique， 2018， 41（3）： 146?150.

[10] 萬韓永，左家莉，萬劍怡，等.基于樣本重要性原理的KNN文本分類算法[J].江西師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2015，39（3）：297?303.

WAN Hanyong， ZUO Jiali， WAN Jianyi， et al. The KNN text classification based on sample importance principals [J]. Journal of Jiangxi Normal University （Natural science）， 2015， 39（3）： 297?303.

[11] 沈媛媛，嚴(yán)嚴(yán)，王菡子.有監(jiān)督的距離度量學(xué)習(xí)算法研究進(jìn)展[J].自動(dòng)化學(xué)報(bào)，2014，40（12）：2674?2686.

SHEN Yuanyuan， YAN Yan， WANG Hanzi. Research progress on supervised distance metric learning algorithm [J]. Journal of automation， 2014， 40（12）： 2674?2686.

[12] RUTKOWSKI L， JAWORSKI M， PIETRUCZUK L， et al.The CART decision tree for mining data streams [J]. Information sciences， 2014， 266： 1?15.

[13] 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（NIPS）. [S. l.： s.n.]， 2003： 505?512.

[14] JINDALUANG W， CHOUVATUT V， KANTABUTRA S. Under?sampling by algorithm with performance guaranteed for class?imbalance problem [C]// Computer Science and Engineering Conference. [S. l.： s.n.]， 2014： 215?221.

[15] WANG B， JIANG J Y， WANG W， et al. Unsupervised metric fusion by cross diffusion [C]// Proceedings of the 2012 Confe?rence on Computer Vision and Pattern Recognition. Providence， RI， USA： IEEE， 2012： 2997?3004.