流形學(xué)習(xí)算法中鄰域大小參數(shù)的遞增式選取

邵 超，萬春紅，趙靜玉

(河南財(cái)經(jīng)政法大學(xué)計(jì)算機(jī)與信息工程學(xué)院，鄭州 450002)

1 概述

近年來，人們陸續(xù)發(fā)現(xiàn)實(shí)際中的很多高維數(shù)據(jù)都分布在某個(gè)低維非線性流形上［1-2］，為此提出了多種能有效學(xué)習(xí)這種結(jié)構(gòu)的流形學(xué)習(xí)算法如等距映射［3-4］(Isometric Mapping，ISOMAP)和局部線性嵌入［5-6］(Locally Linear Embedding，LLE)。現(xiàn)有的大多數(shù)流形學(xué)習(xí)算法能否成功應(yīng)用還依賴于其鄰域大小參數(shù)的選取是否合適，然而，目前該參數(shù)在實(shí)際中通常還難以高效選取，另外，數(shù)據(jù)中的噪音對鄰域大小參數(shù)的合適性也會(huì)產(chǎn)生一定的影響［7］，從而限制了它們的實(shí)際應(yīng)用［7-10］。

針對流形學(xué)習(xí)算法敏感于鄰域大小參數(shù)的這一問題，目前大多數(shù)方法都基于殘差來選取合適的鄰域大小參數(shù)［3，11-12］，但這需要多次運(yùn)行整個(gè)流形學(xué)習(xí)算法以計(jì)算相應(yīng)的殘差(盡管文獻(xiàn)［11 -12］都只對其中具有極小重建誤差或極小成本函數(shù)的少數(shù)幾個(gè)鄰域大小參數(shù)分別計(jì)算相應(yīng)的殘差);另外，殘差只是維數(shù)約簡過程中產(chǎn)生的誤差，難以正確指導(dǎo)鄰域大小參數(shù)的合適選取［13］。

通過對采用不同鄰域大小參數(shù)得到的多個(gè)運(yùn)行結(jié)果進(jìn)行集成可以在一定程度上減輕流形學(xué)習(xí)算法對鄰域大小參數(shù)的敏感程度［9］，但算法的時(shí)間復(fù)雜度會(huì)顯著增加。通過識別和刪除鄰域圖中可能出現(xiàn)的“短路”邊也能在一定程度上避免鄰域大小參數(shù)難以高效選取的問題，例如，文獻(xiàn)［14］刪除每一個(gè)數(shù)據(jù)點(diǎn)中具有最小重建權(quán)重的幾個(gè)近鄰點(diǎn)，文獻(xiàn)［15］刪除每一個(gè)數(shù)據(jù)點(diǎn)中具有最大圖距離的幾個(gè)近鄰點(diǎn)，但它們又引入了一個(gè)同樣難以選取的額外參數(shù)。文獻(xiàn)［16 -17］通過組合若干個(gè)最小生成樹來創(chuàng)建鄰域圖，沒有了鄰域大小參數(shù)，但最小生成樹的數(shù)量同樣難以有效確定。文獻(xiàn)［18 -19］可以自適應(yīng)地為每一個(gè)數(shù)據(jù)點(diǎn)選取不同的鄰域大小參數(shù)，但計(jì)算比較復(fù)雜。

根據(jù)流形的局部歐氏性，鄰域圖上的所有鄰域都呈線性或近似線性，是鄰域大小參數(shù)被認(rèn)為合適的基礎(chǔ)，此時(shí)所有鄰域的線性度量可聚成一類;而鄰域大小參數(shù)一旦變得不合適，鄰域圖上的某些鄰域就不再呈線性或近似線性［20］，其線性度量也不再能聚成一類。本文用加權(quán)主成分分析［21］(Principal Component Analysis，PCA)得到的重建誤差對鄰域圖上所有鄰域的線性程度進(jìn)行度量，然后用貝葉斯信息準(zhǔn)則［2，22］(Bayesian Information Criterion，BIC)對其聚類個(gè)數(shù)進(jìn)行探測，從而能遞增式地選取合適的鄰域大小參數(shù)。

2 鄰域大小的遞增式選取

具有合適鄰域大小參數(shù)的鄰域圖應(yīng)能正確表達(dá)數(shù)據(jù)的鄰域結(jié)構(gòu)，按照流形的局部歐氏性，所有鄰域都應(yīng)呈線性或近似線性;而鄰域大小參數(shù)一旦變得不合適，鄰域圖中開始出現(xiàn)“短路”邊，從而使某些鄰域不再呈線性或近似線性。線性度量有很多，考慮到魯棒性，本文采用的是加權(quán)PCA［21］重建誤差。當(dāng)鄰域大小k 合適時(shí)，鄰域圖上所有鄰域的加權(quán)PCA重建誤差都相對較小，可聚成一類，如圖1 所示;而鄰域大小k 一旦變得不合適，某些不再線性的鄰域其加權(quán)PCA 重建誤差就會(huì)變得很大，這樣就使鄰域圖上所有鄰域的加權(quán)PCA 重建誤差不再能聚成一類，如圖2 所示。因此，根據(jù)鄰域圖上所有鄰域的加權(quán)PCA 重建誤差所聚成的類別個(gè)數(shù)即可遞增式地選取合適的鄰域大小k。本文采用BIG［2，22］來探測其聚類個(gè)數(shù)。

圖1 當(dāng)鄰域大小k 合適時(shí)的加權(quán)PCA 重建誤差

圖2 當(dāng)鄰域大小k 不合適時(shí)的加權(quán)PCA 重建誤差

2.1 加權(quán)PCA 重建誤差的計(jì)算

PCA 重建誤差可用來度量數(shù)據(jù)的線性程度，一般而言，線性程度越大，PCA 重建誤差就越小。然而，PCA 對數(shù)據(jù)中的異常點(diǎn)(outlier)比較敏感［21］，異常點(diǎn)的加入會(huì)極大地改變主成分，從而使PCA 重建誤差難以準(zhǔn)確度量數(shù)據(jù)的線性程度。如圖3 所示，異常點(diǎn)(圖中標(biāo)注為“* ”)的加入使原本以實(shí)線標(biāo)注的主成分變成了以虛線標(biāo)注的主成分，從而降低了該數(shù)據(jù)集合的最大PCA 重建誤差。

圖3 異常點(diǎn)對PCA 的影響

鄰域大小參數(shù)一旦變得不合適，鄰域圖上就會(huì)有某些鄰域由線性變成非線性，和之前線性鄰域中的那些數(shù)據(jù)點(diǎn)相比，新加入的導(dǎo)致鄰域非線性的數(shù)據(jù)點(diǎn)就類似于異常點(diǎn)，其PCA 重建誤差(通常也是該鄰域中的最大PCA 重建誤差)用來度量該鄰域線性程度隨鄰域大小的變化趨勢是比較合適的。然而，為準(zhǔn)確計(jì)算這些“異常點(diǎn)”的PCA 重建誤差，需要盡量降低異常點(diǎn)對PCA 的影響，因此，本文采用加權(quán)PCA 算法［21］，通過迭代給異常點(diǎn)賦以較小的權(quán)重，從而得到盡可能接近于原始主成分(圖3 中標(biāo)注為實(shí)線)的主成分(圖3 中標(biāo)注為點(diǎn)劃線)。

加權(quán)主成分分析算法可簡要描述如下［21］:

(1)采用標(biāo)準(zhǔn)PCA 算法獲得數(shù)據(jù)集合X 的初始數(shù)據(jù)中心μ(0)和初始主成分p(0);

(2)t=0;

(3)DO

1)t=t+1;

2)按照式(1)計(jì)算每一個(gè)數(shù)據(jù)點(diǎn)Xi在數(shù)據(jù)中心μ(t-1)和主成分p(t-1)下的PCA 重建誤差

3)按照式(2)計(jì)算每一個(gè)數(shù)據(jù)點(diǎn)Xi的權(quán)重wi:

4)重新計(jì)算數(shù)據(jù)中心μ(t)=

Until μ(t)和p(t)都相對穩(wěn)定下來。

如上所述，本文用每一個(gè)鄰域Nk(Xi)(即數(shù)據(jù)點(diǎn)Xi及其k 個(gè)最近鄰數(shù)據(jù)點(diǎn)的集合，也就是加權(quán)PCA 算法中的數(shù)據(jù)集合X，因此有s=k +1)的最大加權(quán)PCA 重建誤差(一個(gè)標(biāo)量值，維數(shù)為1)來度量其線性程度，進(jìn)而探測該鄰域中是否出現(xiàn)了“短路”邊。

2.2 貝葉斯信息準(zhǔn)則的計(jì)算

由于具有不同聚類個(gè)數(shù)的聚類模型可以看作是不同的模型，因此BIC 作為模型選擇準(zhǔn)則就可以用來探測數(shù)據(jù)的聚類個(gè)數(shù)［2，22］。BIC 使用一個(gè)帶修正項(xiàng)的對數(shù)似然統(tǒng)計(jì)量對不同的模型進(jìn)行打分，BIC分值越大的模型就越適合于對應(yīng)的數(shù)據(jù)集合。

模型Mj的BIC 分值BIC(Mj)如式(3)所示［2，22］:

本文采用K-均值聚類算法對鄰域圖上所有鄰域的線性度量(即最大加權(quán)PCA 重建誤差max(norm進(jìn)行聚類，因此，數(shù)據(jù)集合D 就由鄰域圖上所有鄰域的最大加權(quán)PCA 重建誤差組成，即D=，則有m=n，pj=K(R +1)，其中，K 為聚類個(gè)數(shù);R=1 為D 的維數(shù)。

不同的聚類個(gè)數(shù)K 就對應(yīng)了不同的K-均值聚類模型，因此，分別用BIC(K=1)和BIC(K=2)表示聚類個(gè)數(shù)為1 和2 時(shí)對應(yīng)K-均值聚類模型的BIC 分值。例如，圖4 所示的2 個(gè)數(shù)據(jù)集合，其聚類個(gè)數(shù)分別為1和2，與之相適應(yīng)的K-均值聚類模型的BIC 分值都相對較大(圖4(a)中BIC(K=1)=-354.373 6，BIC(K=2)=-458.869 9，圖4(b)中BIC(K=1)=-558.274 3，BIC(K=2)=-507.237 9)。

圖4 BIC 用于探測聚類個(gè)數(shù)的數(shù)據(jù)集合

2.3 算法流程

該方法可簡要描述如下:

(1)使用廣度優(yōu)先搜索算法獲得能使鄰域圖連通的最小鄰域大小參數(shù)kmin，作為遞增式選取鄰域大小參數(shù)的起點(diǎn);

(2)k=kmin-1;

(3)DO

1)k=k+1;

2)對鄰域圖上的每一個(gè)鄰域Nk(Xi)執(zhí)行加權(quán)PCA 算法，獲得鄰域圖上每一個(gè)鄰域的最大加權(quán)PCA 重建誤差，即式(4)中的數(shù)據(jù)集合D;

3)計(jì)算BIC(K=1)(由于只有一類，所以數(shù)據(jù)中心即為聚類中心);

4)計(jì)算BIC(K=2)，這需要對數(shù)據(jù)集合D 執(zhí)行K-均值聚類算法將其聚成2 類;

Until BIC(K=1)＜BIC(K=2)

(4)kselected=k-1。

通過該方法的遞增式選取，最終的kselected即為合適的鄰域大小參數(shù)。和傳統(tǒng)的基于殘差的參數(shù)選取方法相比，該方法只需遞增式地執(zhí)行加權(quán)PCA 算法和K-均值聚類算法，并計(jì)算相應(yīng)的BIC(K=1)和BIC(K=2)，而無需運(yùn)行整個(gè)流形學(xué)習(xí)算法和計(jì)算相應(yīng)的殘差。

2.4 時(shí)間復(fù)雜度分析

該方法主要涉及以下3 個(gè)部分的計(jì)算:

(1)為確定kmin，需要從k=1 開始反復(fù)執(zhí)行廣度優(yōu)先搜索算法(共執(zhí)行kmin次)。廣度優(yōu)先搜索算法的時(shí)間復(fù)雜度為O(n +e)=O(kn)(e 為鄰域圖的邊數(shù))，因此，這一部分的時(shí)間復(fù)雜度為通常情況下，kmin都比較小。

(2)對于鄰域大小k 的每一次迭代(共迭代(kselected-kmin+2)次)，在鄰域圖的每一個(gè)鄰域(包括k+1 個(gè)d 維數(shù)據(jù)點(diǎn)，d 即為數(shù)據(jù)的維數(shù))上分別執(zhí)行加權(quán)主成分分析算法(共執(zhí)行n 次)。加權(quán)主成分分析算法的時(shí)間復(fù)雜度為O(((k +1)d2+d3)c)(c為加權(quán)主成分分析算法的迭代次數(shù)，通常都比較小)，因此，這一部分的時(shí)間復(fù)雜度為O(((k +1)d2+d3)cn(kselected-kmin+2))。

(3)對于鄰域大小k 的每一次迭代(共迭代(kselected-kmin+2)次)，對數(shù)據(jù)集合D(包括n 個(gè)1 維數(shù)據(jù)點(diǎn))執(zhí)行K-均值聚類算法將其聚成兩類。K-均值聚類算法的時(shí)間復(fù)雜度為O(nKpl)=O(2nl)(n和p=1 分別為D 中數(shù)據(jù)點(diǎn)的個(gè)數(shù)及其維數(shù)，K=2為聚類個(gè)數(shù)，l 為K-均值聚類算法的迭代次數(shù)，通常都比較小)，因此，這一部分的時(shí)間復(fù)雜度為O(2nl(kselected-kmin+2))。

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

為驗(yàn)證該方法的有效性，本文采用具有2 000 個(gè)隨機(jī)樣本點(diǎn)的Swiss roll［3］和S-curve［5］數(shù)據(jù)集合(為了降低計(jì)算量，本文采用K-均值算法分別從中選取了n=500 個(gè)代表點(diǎn)，如圖5 所示)，該方法的運(yùn)行結(jié)果如圖6 所示。

從圖6 可以看出，對于Swiss roll 數(shù)據(jù)集合，該方法選取的鄰域大小參數(shù)為k=8;對于S-curve 數(shù)據(jù)集合，該方法選取的鄰域大小參數(shù)為k=16。它們的合適性可通過ISOMAP 算法的運(yùn)行結(jié)果得以證實(shí)。

眾所周知，數(shù)據(jù)中的噪音對鄰域大小參數(shù)的合適性也會(huì)產(chǎn)生一定的影響［7］。為了驗(yàn)證該方法的魯棒性，本文在以上2 個(gè)數(shù)據(jù)集合上分別加入一定的噪音［7］(如圖7 所示)，該方法的運(yùn)行結(jié)果如圖8 所示。

圖5 實(shí)驗(yàn)中的2 個(gè)數(shù)據(jù)集合

圖6 在不同數(shù)據(jù)集合上的運(yùn)行結(jié)果

圖7 加入了噪音的2 個(gè)數(shù)據(jù)集合

圖8 本文方法在不同數(shù)據(jù)集合上的運(yùn)行結(jié)果

從圖8 可以看出，對于加入了噪音的Swiss roll數(shù)據(jù)集合，該方法選取的鄰域大小參數(shù)為k=6;對于加入了噪音的S-curve 數(shù)據(jù)集合，該方法選取的鄰域大小參數(shù)為k=11。它們的合適性同樣可通過ISOMAP 算法的運(yùn)行結(jié)果得以證實(shí)。

此外，該方法基于的是流形的局部歐氏性，那么在由于采樣不均勻而出現(xiàn)“空洞”的數(shù)據(jù)集合上是否依然有效?為了驗(yàn)證這一點(diǎn)，本文采用帶有“空洞”的Swiss roll 和S-curve 數(shù)據(jù)集合(如圖9 所示)，該方法的運(yùn)行結(jié)果如圖10 所示。

圖9 帶有“空洞”的2 個(gè)數(shù)據(jù)集合

從圖10 可以看出，對于帶有“空洞”的Swiss roll數(shù)據(jù)集合，該方法選取的鄰域大小參數(shù)為k=8;對于帶有“空洞”的S-curve 數(shù)據(jù)集合，該方法選取的鄰域大小參數(shù)為k=11。它們的合適性同樣可通過ISOMAP 算法的運(yùn)行結(jié)果得以證實(shí)。

與傳統(tǒng)的基于殘差的參數(shù)選取方法(括號內(nèi)指定的是鄰域大小的選取范圍)相比，本文方法不但能選取合適的鄰域大小(分別如圖6、圖8 和圖10 所示)，而且還具有較高的運(yùn)行效率，如表1 所示(計(jì)算機(jī)配置為Intel i3-2120 CPU，主頻為3.30 GHz，內(nèi)存容量為4 GB)。

圖10 本文方法在不同數(shù)據(jù)集合上的運(yùn)行結(jié)果

表1 2 種方法在運(yùn)行時(shí)間上的對比 s

4 結(jié)束語

按照流形的局部歐氏性，本文方法通過對鄰域圖上每一個(gè)鄰域的線性程度進(jìn)行度量，并對其聚類個(gè)數(shù)進(jìn)行探測，能夠高效地選取合適的鄰域大小參數(shù)，且無需任何額外參數(shù)(在數(shù)據(jù)維數(shù)不是特別高的情況下)。下一步的研究方向是當(dāng)數(shù)據(jù)的維數(shù)非常高時(shí)，如何高效地選取合適的鄰域大小。

［1］Seung H S，Lee D D.The Manifold Ways of Perception［J］.Science，2000，290(5500):2268-2269.

［2］楊 劍，李伏欣，王 玨.一種改進(jìn)的局部切空間排列算法［J］.軟件學(xué)報(bào)，2005，16(9):1584-1590.

［3］Tenenbaum J B，de Silva V，Langford J C.A Global Geometric Framework for Nonlinear Dimensionality Reduction［J］.Science，2000，290(5500):2319-2323.

［4］王耀南，張 瑩，李春生.基于核矩陣的Isomap 增量學(xué)習(xí)算法研究［J］.計(jì)算機(jī)研究與發(fā)展，2009，46(9):1515-1522.

［5］Roweis S T，Saul L K.Nonlinear Dimensionality Reduction by Locally Linear Embedding［J］.Science，2000，290(5500):2323-2326.

［6］Zhang S.Enhanced Supervised Locally Linear Embedding［J］.Pattern Recognition Letters，2009，30(13):1208-1218.

［7］Balasubramanian M，Shwartz E L，Tenenbaum J B，et al.The ISOMAP Algorithm and Topological Stability［J］.Science，2002，295(5552):7-17.

［8］Saul L K，Roweis S T.Think Globally，F(xiàn)it Locally:Unsupervised Learning of Low Dimensional Manifolds［J］.Journal of Machine Learning Research，2003，4(1):119-155.

［9］詹德川，周志華.基于集成的流形學(xué)習(xí)可視化［J］.計(jì)算機(jī)研究與發(fā)展，2005，42(9):1533-1537.

［10］邵 超，黃厚寬，趙連偉.一種更具拓?fù)浞€(wěn)定性的ISOMAP 算法［J］.軟件學(xué)報(bào)，2007，18(4):869-877.

［11］Kouropteva O，Okun O，Pietikainen M.Selection of the Optimal Parameter Value for the Locally Linear Embedding Algorithm［C］//Proc.of the 1st International Conference on Fuzzy Systems and Knowledge Discovery，Orchid Country Club.Singapore:IEEE Press，2002:359-363.

［12］Samko O，Marshall A D，Rosin P L.Selection of the Optimal Parameter Value for the Isomap Algorithm［J］.Pattern Recognition Letters，2006，27(1):968-979.

［13］黃啟宏，劉 釗.流形學(xué)習(xí)中非線性維數(shù)約簡方法概述［J］.計(jì)算機(jī)應(yīng)用研究，2007，24(11):19-25.

［14］Saxena A，Gupta A，Mukerjee A.Non-linear Dimensionality Reduction by Locally Linear Isomaps［C］//Proc.of the 11th International Conference on Neural Information Processing.Calcutta，India:Springer，2004:1038-1043.

［15］Wen G，Jiang L，Shadbolt N R.Using Graph Algebra to Optimize Neighborhood for Isometric Mapping［C］//Proc.of the 20th International Joint Conference on Artificial Intelligence.Hyderabad，India:AAAI Press，2007，2398-2403.

［16］Carreira-Perpinan M A，Zemel R S.Proximity Graphs for Clustering and Manifold Learning［C］//Proc.of the 18th Annual Conference on Neural Information Processing Systems.Vancouver，Canada:MIT Press，2004:225-232.

［17］Yang L.Building k Edge-disjoint Spanning Trees of Minimum Total Length for Isometric Data Embedding［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27(10):1680-1683.

［18］Zhang Z，Wang J，Zha H.Adaptive Manifold Learning［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2012，34(2):1473-1480.

［19］文貴華，江麗君，文 軍.鄰域參數(shù)動(dòng)態(tài)變化的局部線性嵌入［J］.軟件學(xué)報(bào)，2008，19(7):1666-1673.

［20］邵 超，張 斌，萬春紅.流形學(xué)習(xí)中鄰域大小參數(shù)的合適性判定［J］.計(jì)算機(jī)工程與應(yīng)用，2010，46(20):172-175.

［21］Chang H，Yeung D.Robust Locally Linear Embedding［J］.Pattern Recognition，2006，39(6):1053-1065.

［22］Pelleg D，Moore A.X-means:Extending K-means With Efficient Estimation of the Number of Clusters［C］//Proc.of the 17th International Conference on Machine Learning.San Francisco，USA:Morgan Kaufmann Publishers，2000:727-734.