距離度量學習算法的精確性研究

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

關鍵詞： 距離度量學習; 機器學習; 距離矩陣; 馬氏距離; UCI數據庫; 比較研究

中圖分類號： TN911.1?34; G231.5" " " " " " " " " "文獻標識碼： A" " " " " " " " " "文章編號： 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" 引" 言

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

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

本文研究主要是基于無監督的距離度量學習算法。選擇單位矩陣、邢氏算法、信息論度量學習算法和編碼相似度算法，在選取的不同數據庫上進行比較，對提高距離度量學習算法的精確性提供研究基礎，對于實際應用中度量學習算法的選擇提供依據。

1" 算" 法

基于約束條件（未標記的數據和相似集）選擇四種算法對距離矩陣進行比較。這四種算法分別是：單位矩陣或歐幾里得距離;邢氏算法[10]（一種迭代算法）;信息論的度量學習[11]（一種迭代算法）;編碼相似度算法[12]。

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

1.1" 邢氏算法

邢氏算法是可以考慮用來解決問題的最簡單的算法。 一般的思路是最小化相似點與相異點之間的距離。為此考慮一個距離矩陣，并進行優化：

該算法的主要缺點是集合的收斂性不確定。有時根據數據集或初始條件可能無法計算出一個很好的結果，并被卡在一個循環中，每個迭代步驟產生的新矩陣都遠離了前一個矩陣。在某些數據集上，還可能出現[A=0]，這是不應該的。

在本文中，該算法僅運用于學習全矩陣[13]。

1.2" 信息論的度量學習算法

式中：[ξ0]是描述相似性與差異性之間臨界值的集合;[ξi，j]是[S]或[D]中[i，j]的臨界值;[γ]控制著對任意矩陣[A0]進行學習的矩陣與對預計算的閾值進行調整之間的平衡問題，這個問題可以有很多參數，用來獲得更好的計算結果，但是在算法開始時，必須設定好[A0]，[ξ]和[γ] 的初始值，因為它們很難進行預先估算。

1.3" 編碼相似度

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

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

2" 實驗方法

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

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

由于可能產生不一致性，在一個真正的數據集中選擇將它們從測試集中排除。人造的編碼不能選擇，這只會降低結果準確性，并且對算法的比較也沒有幫助。

3" 實驗結果

3.1" 電離層

電離層結果如表1所示。由表1可知，運用歐幾里得定理得到的結果不理想;邢氏算法結果較好，但是當內部關聯數據出現時，健壯性較差;編碼相似度算法給出了基本一致的穩定性。

3.2" 虹膜（IRIS）

虹膜層結果如表2所示。由表2可知，小規模的IRIS數據集的尺寸解釋了相似性準確度上的急速下降。根據歐幾里得定理得出的結果，使用學習過的距離函數效果不好。

3.3" 酒" 類

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

3.6" 平衡量表

平衡量表結果如表6所示。由表6數據可得出，邢氏算法出現很多錯誤數據，因此至少在某一時間段或某些迭代的情況下是不能收斂的，就如同信息論度量學習算法一樣。這可能是由數據集尺寸導致的。

4" 結" 論

本文研究的主要結論是基于數據驅動算法的準確性中，算法并不處于主導地位的。此外，明確定義的集合的結果并不能代表隨機產生的數據集合的結果。當沒有明確分類時，相似性的區別和分類問題值得研究。

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

某些算法的結果不理想，但并不應該受到限制。比如，如果編碼相似性算法很好，就可以用來學習一個很好的距離函數，并且可以通過在線捕獲的數據（如ITML的在線版本）來調整矩陣。關于人造數據集和非二元距離的領域，在未來的實際應用中還有很多值得研究的地方。

參考文獻

[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] 王燕，李鳳蓮，張雪英，等.改進學習率的一種高效SVD++算法[J].現代電子技術，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].江西師范大學學報（自然科學版），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] 沈媛媛，嚴嚴，王菡子.有監督的距離度量學習算法研究進展[J].自動化學報，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.