基于圖的半監督學習的距離度量改進

蘭遠東　高蕾

摘 要：基于圖的半監督學習的一個關鍵問題是：圖上頂點之間的距離度量的有效性問題。為了解決這個問題，提出了基于圖的半監督學習的距離度量改進方法。通過在現有密度敏感的距離度量方案中添加補償參數的方法，使得改進的距離度量方案不但能夠有效的擴大不同類別的高密度區域樣本間的距離，同時還能縮小相同類別中樣本之間的距離。將改進的距離度量方案應用到聚類算法中，來驗證改進的距離度量方案的有效性。實驗結果表明：改進的距離度量方法能夠有效的擴大不同類別間距離，增強類內聚合度。

關鍵詞：半監督學習；距離度量；聚類；機器學習

中圖分類號：TP319.4 文獻標識號：A 文章編號：2095-2163（2014）02-

Improved Distance Measure for Graph Based Semi Supervised Learning

LAN Yuandong， GAO Lei

（Department of Computer Science， Huizhou University， Huizhou Guangdong 516007， China）

Abstract： A key problem in graph-based semi supervised learning is the effectiveness of distance measurement between the vertices of graph. In view of this， an improved distance measure method is proposed for semi-supervised learning. The method cans effective amplification the distance between data points in different high density region and reduces the distance between data points in the same high density region by adding an offset parameter. Then， a graph based semi supervised clustering algorithm is presented based on this improved distance measurement. Experimental results shows that the improved method can effectively increase the scatter of inter classes and reduce the scatter of intra-class.

Keyword： semi supervised learning； distance measurement； clustering； machine learning

0 引 言

半監督學習的目的是利用無標記數據來改進機器學習的性能[1]。聚類假設認為決策邊界應該存在于數據的低密度區域，而不是存在于高密度區域[2]。幾乎所有有效的半監督學習方法都是基于聚類假設，或者間接使用了聚類假設。基于圖的半監督學習方法通過利用所有數據來構建一個圖，圖上的節點就是數據集中的樣本點（包含標記數據和未標記數據），連接圖上任意兩個頂點之間的邊則是兩個樣本點之間相似性的表征[3]。學習方法通常并不需要數據點本身，而是需要兩個點之間的距離。這樣的學習方法都假定樣本點的標記在圖上平滑分布，而圖則是基于圖的半監督學習方法的核心所在[4-8]。通常將要構建的圖需要能夠反映數據的真實分布，但是圖的構建方法卻并未取得卓有成效的研究成果[9]。大多數基于圖的半監督學習算法都是通過高斯函數來計算兩個頂點之間的連接邊的權值，即[10]：

（1）

學習算法的性能對參數 比較敏感[11]，并且在處理復雜的現實問題時，這種簡答的基于歐幾里德距離的相似性度量方法，并不能真實全面地反映復雜空間數據的分布，可以通過圖1來說明這個問題。

圖1 距離度量示例

Fig. 1 Example for distance measurement

在圖1中，點B和點C之間的歐幾里德距離相對較近，但是根據聚類假設，點A與點B則屬于同一個類別，也就是A與B更加相似，意即更加接近。公式（1）的距離計算方法，并不能反映圖1中的這種情況。

為了解決這個問題，文獻[12，13]中提出了兩個版本的密度敏感的距離度量方法。兩個版本的距離方法都能夠度量流行上的最短路徑，并且能夠反映數據集的內在的流行結構。通過使用短邊來連接高密度同類樣本中的樣本點，而用長邊來連接不同的高密度區域之間的樣本點。在對這兩個版本的密度敏感的距離度量進行了深入分析之后，本文提出了一種改進的密度敏感的距離度量方法。并且基于改進的密度敏感的距離度量方法，更進一步地提出了一種新的密度敏感的半監督聚類（a new density-sensitive semi-supervised clustering， NDS-SSC） 算法。

1 密度敏感的距離度量

通過聚類假設可以知道，同類樣本趨向于聚集在一個相同的高密度區域內，在不同的聚類之間存在相對稀疏的數據分布區域，這就能夠推知決策邊界應該存在于低密度區域。研究中，需要找到一種距離度量方法，能夠刻畫數據的局部一致性和全局一致性。由于密度敏感的距離度量方法能夠反映數據聚類的空間分布，由此即獲得了機器學習界的廣泛關注。在本小節中，介紹兩個版本的密度敏感的距離度量方法。每個方法都包含兩個步驟，通過這兩個步驟，不同類別的樣本之間的距離得到拉伸，而同類樣本之間的距離得到壓縮。文獻[12]即使用下面的兩個步驟來執行密度敏感的距離度量，具體論述如下：

步驟（1）：通過給定的拉伸函數來計算圖上頂點之間的距離長度，并且可以通過該步驟調節樣本的密度；計算公式為：

（2）

其中， 是樣本 和 之間的歐幾里德距離， 是拉伸因子。

步驟（2）：定義 是圖G=（V，E，W）上的長度為 的路徑，如果 且 ，則 。路徑 指的是連接節點 到 之間的路徑， 表示所有連接 和 的路徑的集合，可以得到：

（3）

其中， 是圖上 到 之間的最短路徑。

除此之外，文獻[12]中還給出了另外一種距離度量公式：

（4）

文獻[13]和文獻[12]使用相同的聚類假設和前提條件，但是在兩個步驟中卻使用了不同的公式來度量距離，具體如下：

步驟（1）：采用的公式為：

（5）

步驟（2）：采用的公式為：

（6）

其中， 表示 到 之間的路徑長度。

2 改進的距離度量與算法

聚類假設表明，決策邊界不應穿過數據空間的高密度區域，而應存在于低密度區域。回顧一下Chapelle的密度敏感的距離度量方法[12]，其計算公式為：

（4）

該方法使用拉伸函數 來拉伸距離 ，其后尋找拉伸后的 與 之間的最短距離。問題主要在于：經過特征歸一化的處理，距離 通常存在于區間[0，1]中，在這個區間中 變化緩慢，也就是對距離的拉伸效果不明顯。在此借助圖2來說明該問題。拉伸函數的拉伸效果如圖2所示。

圖2 拉伸函數的拉伸效果示例

Fig. 2 Example for the effect of strench function

在圖2中，可以看到拉伸函數改變緩慢，拉伸效果并不明顯。為了改善這個問題，本文在公式中加入一個補償參數 ，具體如下：

（7）

其中， 是拉伸因子， 是補償參數。可以選擇合適的 值，來達到最佳的拉伸效果。基于此，可以按照下面的方法重新定義密度敏感的距離度量。

定義 是圖G=（V，E，W）上的長度為 的路徑，如果 其中 ，則 。路徑 指的是連接節點 到 之間的路徑， 表示所有連接 和 的路徑的集合，密度敏感的距離度量定義如下：

（8）

當 時， 是圖上 和 之間的最短的歐幾里德距離；當 時，結果即與公式（4）相同。

綜上所述，通過密度敏感的距離度量，可以得到密度敏感的相似矩陣如下：

（9）

接下來，使用與文獻[14]中相似的方法，采用公式（10）所示的正則化框架來解決標記數據不足的情況。

（10）

公式（10）的封閉解是：

（11）

求解公式（11）將具有很高的時間復雜度，因此本文使用迭代防范來求解公式（11），即：

（12）

根據公式（12），得到下面的聚類算法。方法步驟為：

步驟（1）：根據數據空間中的樣本，建立一個全連圖G=（V，E，W），V是所有樣本（包含有標記和無標記數據）的集合，E是邊的集合，W是權值集合，W中的 ，在W中的每一行保留K個最小的值；

步驟（2）：通過公式（8）計算密度敏感的距離度量矩陣 ；

步驟（3）：通過公式（9）構建密度敏感的相似矩陣W；

步驟（4）：使用迭代方法求解公式（12），得到 ；

步驟（5）：使用聚類算法來聚類數據集FU。

3 實驗結果與分析

3.1 實驗數據集

為了評估算法的聚類性能，實驗采用機器學習領域中比較流行的基準數據集：UCI（UC Irvine machine learning repository）數據集（http：//archive.ics.uci.edu/ml/）。主要采用UCI數據集中的Iris，Ionosphere，Glass和Image segmentation數據集，表1列出了4個數據集的主要信息。

在實驗中，首先驗證參數 和 對聚能性能的影響；然后在將本文的算法與基于公式（1）的GB-SSC（Gaussian-Based Semi-Supervised Clustering， GB-SSC）算法以及基于公式（4）的DS-SSC（Density-Sensitive Semi-supervised Clustering， DS-SSC）算法進行對比。在上述4個數據集上單獨進行實驗，最后給出平均測試錯誤。

3.2 參數選擇

由于參數 能夠改善對數據空間中的樣本間距離的拉伸效果，為了驗證 對聚類性能的影響，從每個數據集中隨機選擇20個樣本作為標記數據，實驗結果如圖3所示。

圖3 補償參數 對聚類性能的影響

Fig. 3 Impact of the offset parameter to clustering performance

從圖3可以看出：當 時，參數 對公式（8）沒有影響，所以性能曲線是一條水平線。總體來說，在 =5的附近，測試錯誤率最小。但是，當 時， =8的性能曲線最優。這是因為當 ，拉伸函數改變緩慢，就需要更大的補償參數 才能獲得較好的聚類結果。

同樣，實驗還給出了參數 對聚類性能的影響結果，圖4是在不同的 值時的測試錯誤率即如圖4所示。

圖4 參數 對聚類性能的影響

Fig. 4 Impact of parameter on the clustering performance

由圖4可以清楚地看到，NDS-SSC的測試錯誤率要明顯低于算法DS-SSC的錯誤率，特別是在 時，聚類性能最優。當 時，兩個算法具有相同的測試錯誤率，這是因為當 時，補償參數 對聚類性能沒有任何影響。

最后，從每個數據集中隨機選擇20個樣本作為標記樣本，建立K近鄰圖（K-nearest neighbors graph），并設定K=30。然后通過聚類算法來判別余下樣本的所屬的類別，分別進行10次實驗，最后計算每個算法的平均錯誤率，結果如表2所示。

從實驗結果可以看出密度敏感的半監督聚類算法的錯誤率，要明顯低于GB-SSC。這表明保持原始數據的空間信息一致性，對于聚類效果起著至關重要的作用。隨著訓練數據的增加，錯誤率也隨之下降，這就表明要真實地反映數據空間的結構，單獨使用少量的標記樣本是很難做到的，還需要充分利用未標記的樣本來認識數據的分布結構，這正是半監督學習得以發展的原因所在。另外，本文算法的聚類效果要優于DS-SSC和GB-SSC，這也說明補償參數 能夠有效地擴大不同樣本之間的距離，并縮小同類樣本之間的距離。

4 結束語

本文通過構建一個圖來反映數據的真實分布，確保聚類假設的有效性。通過對兩種密度敏感的距離度量方法的研究與分析，提出了一種改進的密度敏感的距離度量方法。該方法能夠有效擴大不同密度區域之間樣本的距離，同時還能縮小同一密度區域中樣本之間的距離。另外，本文還給出了基于改進的密度敏感的距離度量方法的聚類算法，并在UCI基準數據集上進行實驗，驗證了本文算法的有效性。

參考文獻：

[1] 俞亞君， 霍靜， 史穎歡， 等. SSXCS： 半監督學習分類系統[J]. 南京大學學報： 自然科學版， 2013， 49（005）： 611-618.

[2] 吳燁， 鐘志農， 熊偉， 等. 一種高效的屬性圖聚類方法[J]. 計算機學報， 2013， 36（8）： 1704-1713.

[3] 郭濤， 李貴洋， 蘭霞. 基于圖的半監督協同訓練算法[J]. 計算機工程， 2012， 38（13）： 163-168.

[4] TEICHMAN A， THRUN S. Tracking-based semi-supervised learning[J]. The International Journal of Robotics Research， 2012， 31（7）： 804-818.

[5] BUNKE H， RIESEN K. Towards the unification of structural and statistical pattern recognition[J]. Pattern Recognition Letters， 2012， 33（7）： 811-825.

[6] XU X， LU L， HE P， et al. Protein Classification Using Random Walk on Graph[M]//Emerging Intelligent Computing Technology and Applications. Springer Berlin Heidelberg， 2012： 180-184.

[7] LUO D， DING C H Q， HUANG H， et al. Forging the graphs： a low rank and positive semidefinite graph learning approach[C]//BARTLETT P， PEREIRA F C N， BRUGES C J C， et al. NIPS， 2012： 2969-2977.

[8] PLESS N M， MAAK T， STAHL G K. Developing responsible global leaders through international service-learning programs： The Ulysses experience[J]. Academy of Management Learning & Education， 2011， 10（2）： 237-260.

[9] ZHANG C， WANG F. Graph-based semi-supervised learning[J]. Frontiers of Electrical and Electronic Engineering in China， 2011， 6（1）： 17-26.

[10] 蘭遠東. 基于圖的半監督學習理論， 算法及應用研究[D]. 廣州：華南理工大學， 2012.

[11] 陳詩國， 張道強. 半監督降維方法的實驗比較[J]. 軟件學報， 2011， 22（1）： 28-43.

[12] CHAPELLE O， ZIEN A. Semi-supervised classification by low density separation[C]//Proceedings of the 10th International Workshop on Artificial Intelligence and Statistics， pp. 57-64， 2005.

[13] WANG L， BO L F， JIAO L C. Jiao. Density-sensitive semi-supervised spectral clustering. [J]. Journal of Software，2007，18（10）.

[14] CAI D， WANG X， HE X. Probabilistic dyadic data analysis with local and global consistency[C]//Proceedings of the 26th Annual International Conference on Machine Learning. ACM， 2009：105-112.