張變蘭，路永鋼，張海濤

(蘭州大學 信息科學與工程學院，蘭州 730000) (*通信作者電子郵箱ylu@lzu.edu.cn)

基于KL散度和近鄰點間距離的球面嵌入算法

張變蘭，路永鋼*，張海濤

(蘭州大學 信息科學與工程學院，蘭州 730000) (*通信作者電子郵箱ylu@lzu.edu.cn)

針對現(xiàn)有球面嵌入算法在非近鄰點間的距離度量不準確或缺失的情況下，不能有效地進行低維嵌入的問題，提出了一種新的球面嵌入算法，它能夠只利用近鄰點間的距離，將任何尺度的高維數(shù)據(jù)嵌入到單位球面上，同時求出適合原始數(shù)據(jù)分布的球面半徑。該算法從一個隨機產(chǎn)生的球面分布開始，利用KL散度衡量每對近鄰點間的歸一化距離在原始空間和球面空間中的差異，并基于此差異構建出目標函數(shù)，然后再用帶有動量的隨機梯度下降法，不斷優(yōu)化球面上點的分布，直到結果穩(wěn)定。為了測試算法，模擬產(chǎn)生了兩類球面分布數(shù)據(jù)：分別是球面均勻分布和球面正態(tài)分布的數(shù)據(jù)。實驗結果表明，對于球面均勻分布的數(shù)據(jù)，即使在近鄰點個數(shù)很少的情況下，仍然能夠?qū)?shù)據(jù)準確地嵌入球面空間，嵌入后的數(shù)據(jù)分布與原始數(shù)據(jù)分布的均方根誤差(RMSE)低于0.000 01，且球面半徑的估算誤差低于0.000 001;而對于球面正態(tài)分布的數(shù)據(jù)，在近鄰點個數(shù)較多的情況下，該算法也可以將數(shù)據(jù)較準確地嵌入球面空間。因此，在非近鄰點間距離缺失的情況下，所提方法仍然可以較準確地對數(shù)據(jù)進行低維嵌入，這非常有利于數(shù)據(jù)的可視化研究。

球面嵌入；KL散度；隨機梯度下降法；最近鄰

0 引言

近年來，數(shù)據(jù)可視化分析已經(jīng)成為處理大數(shù)據(jù)的重要方法之一。研究表明，人們從外界接收的各種信息中80%以上是通過視覺獲得的[1]。通過對大數(shù)據(jù)可視化，人們可以對數(shù)據(jù)產(chǎn)生直觀的理解，以便對其進行分析和研究，因此，數(shù)據(jù)可視化在大數(shù)據(jù)分析中正起著越來越重要的作用。為了避免維數(shù)災難帶來的影響，以及更好地對大數(shù)據(jù)進行可視化分析[2]，數(shù)據(jù)降維方法常被用來產(chǎn)生數(shù)據(jù)的一個低維可視化表示。

在計算機視覺和模式識別中，許多問題都是基于樣本點間的距離的，例如手勢識別和形狀識別等。在這些問題中，只知道樣本點間的相似性或者距離度量，而不知道樣本在原始空間的坐標或者其對應的特征向量。這時，可以使用嵌入算法來得到樣本點在對應空間中的坐標分布。在嵌入低維的情況下，也可以通過降維得到樣本的可視化表示。處理該類問題的嵌入算法有多維尺度分析(MultiDimensional Scaling, MDS)[3]、最 大 方 差 展 開 (Maximum Variance Unfolding, MVU)[4]、等距映射(Isometric Mapping, IsoMap)[5]和t分布隨機鄰域嵌入(t-Distributed Stochastic Neighbor Embedding, t-SNE)[6]等，它們都是利用所有樣本間的相似性或者距離信息來構建樣本的低維表示，并使得樣本在低維空間中的結構與高維空間的分布盡量保持一致[3,7]。

然而，這類算法大部分都是將數(shù)據(jù)嵌入線性空間。在計算機視覺中，對于很多類型的數(shù)據(jù)，其樣本都是分布在高維非線性空間中的，因此，將這些數(shù)據(jù)嵌入至低維線性空間是不可行的[8-9]。針對上述問題，出現(xiàn)了很多基于曲面的嵌入算法，例如將數(shù)據(jù)嵌入環(huán)形表面或者球面，以便對此類數(shù)據(jù)進行可視化研究。其中，關于球面嵌入的研究更為廣泛，而且球面嵌入算法有很多實際應用，例如在地球模型表面的數(shù)據(jù)表示，或類球狀物表面的紋理貼圖等[8,10]。文獻[10-11] 中的算法都能夠有效地將數(shù)據(jù)嵌入至球面空間，它們都是基于MDS算法的改進，最終成功將數(shù)據(jù)嵌入到非線性空間[8]。這類算法的關鍵步驟是優(yōu)化過程，它們首先定義一個衡量嵌入質(zhì)量的目標函數(shù)[8,10-11]，然后通過優(yōu)化算法不斷調(diào)整低維空間中樣本點的位置來優(yōu)化目標函數(shù)。文獻[11]中提出了一種球面MDS的嵌入算法，這是最早提出球面嵌入算法的論文之一。它用球面極坐標來表示樣本點，用克魯斯克系數(shù)(Kruskal Stress)[11]構造目標函數(shù)。算法采用了最速下降法進行優(yōu)化，通過調(diào)整點在球面的位置來使目標函數(shù)最小。文獻[8]中，提出了一種曲面流形嵌入算法，將已知的所有點對間距離的數(shù)據(jù)集嵌入恒定曲率的曲面空間，如球面或雙曲面，并且可求出該曲面空間的曲率半徑；該算法還可以將數(shù)據(jù)嵌入超球面空間。該算法的最大優(yōu)點是，在無需任何優(yōu)化的情況下，根據(jù)已知的對稱距離矩陣可以快速有效地將數(shù)據(jù)嵌入曲面空間，并估計出曲面空間的曲率半徑；但是，現(xiàn)有的球面嵌入算法的共同缺點是，必須利用所有點間的相似性或距離信息來進行嵌入。

而對于許多高維數(shù)據(jù)來說，只有近鄰點間的相似性度量是比較可靠的，所以大多數(shù)非線性降維算法只采用近鄰點間的距離進行低維嵌入，例如MVU[4]、IsoMap[5]和局部線性嵌入(Locally Linear Embedding, LLE)[12]等。這些算法的本質(zhì)是，先找到每個樣本點的前K個近鄰點，通過優(yōu)化目標函數(shù)，使得近鄰點間的距離盡量保持不變，從而將非線性數(shù)據(jù)嵌入至線性空間。

本文提出了一種新的球面嵌入算法，能夠在只知道近鄰點間距離的情況下將數(shù)據(jù)集嵌入到單位球面上，并盡量保持近鄰點間的結構。這樣就實現(xiàn)了只利用近鄰點間的相似性信息，將非線性數(shù)據(jù)嵌入至球面空間。據(jù)考證，目前還沒有類似的算法，而本文是首次提出了基于近鄰點間距離的球面半徑未知情況下的球面嵌入算法。該方法用KL散度[13-14]來計算嵌入球面前后每對近鄰點間的相對分布差異，并基于此差異構建出目標函數(shù)。然后利用帶有動量的隨機梯度下降法[15-16]進行優(yōu)化，使得所有近鄰點間相對分布的差異之和最小。這樣就可以將任意尺度的高維數(shù)據(jù)嵌入到單位球面上。最后，利用嵌入前后所有近鄰點間的距離之和的比值，就可估計出適合原始數(shù)據(jù)分布的球面半徑。

1 球面嵌入算法

1.1 球面上的距離計算

在球面坐標系中，球面上的點的坐標為xi=(θi,φi)，極角θi表示向量xi與z軸的夾角，方位角φi表示向量xi與x軸的夾角。在球面上，兩點間的距離為兩向量間夾角對應的球面上的弧長。若在半徑為r的球面上，兩點間的夾角記為Θij，則它們在此球面上的距離可表示為：

dij=rΘij

(1)

Θij=cos-1(cosθicosθj+sinθisinθjcos(φi-φj))

(2)

1.2 球面嵌入算法

首先，該算法將輸入的所有近鄰間的距離整體歸一化。對于樣本點xi和點xj，其歸一化距離為pij：

(3)

dij=‖xi-xj‖

(4)

嵌入單位球面空間后，用同樣的歸一化方法，可得到點yi與點yj的歸一化距離qij：

(5)

Θij=‖yi-yj‖

(6)

其中：Θij表示嵌入到單位球面上的兩點間的距離，也就是兩點對應的向量間的夾角。另外，該算法中定義了一個系數(shù)因子w，當點xi和點xj為近鄰時，wij=1，否則wij=0。算法將只利用wij=1的這部分歸一化距離進行數(shù)據(jù)嵌入。

對于任意wij=1對應的兩個近鄰點，如果嵌入單位球面后的歸一化距離qij和原始樣本點間的歸一化距離pij相等，就意味著嵌入前后這兩點的相對分布一致，因此，該算法的目標就是在嵌入的球面空間中調(diào)整近鄰點的位置分布，使得每對近鄰點之間pij和qij的差異最小，進而使得所有近鄰點間的歸一化距離在嵌入前后的差異之和達到最小。本文利用KL散度作為衡量pij和qij間差異的指標，因此，所有近鄰點之間的KL散度之和構成目標函數(shù)：

(7)

此目標函數(shù)的梯度為：

(8)

(9)

(10)

(11)

(12)

(13)

在該球面嵌入算法中，首先將單位球面上隨機產(chǎn)生的樣本點分布作為嵌入空間中的初始分布，然后采用帶有動量的隨機梯度下降法進行優(yōu)化，具體的迭代過程為：

(14)

(15)

(16)

(17)

(18)

式(16)中，α表示動量；k表示迭代次數(shù)；Δyi表示在每次迭代后樣本點i的位置的變化量，帶動量的隨機梯度下降法每次都記錄這個位置變化，并利用梯度和前一次的位置變化量的組合得出新的位置變化量；ρ(k)表示第k次迭代的最佳步長，確定最佳步長的計算過程見式(18)。在式(18)中，D(yi) 為C(yi)的二階偏導數(shù)矩陣，詳細計算過程為：。

(19)

其中:

(20)

(21)

(22)

(23)

(24)

(25)

(26)

最后，在求得嵌入單位球面的樣本之后，即可利用嵌入前后近鄰點間的距離之和的比值，求出原始樣本分布的球面半徑R，公式如下：

(27)

2 實驗和結果分析

為了驗證本文提出的球面嵌入算法的正確性，文中設計了兩類模擬數(shù)據(jù)進行測試，一類是球面均勻分布的數(shù)據(jù)集，另一類是球面正態(tài)分布的數(shù)據(jù)集。下面將在2.1節(jié)中詳細介紹產(chǎn)生這兩類模擬數(shù)據(jù)的過程，在2.2節(jié)中詳細介紹實驗過程和評價結果。

2.1 模擬數(shù)據(jù)的產(chǎn)生

下面介紹兩類模擬數(shù)據(jù)集：球面均勻分布的數(shù)據(jù)集和球面正態(tài)分布的數(shù)據(jù)集的產(chǎn)生過程。

2.1.1 球面均勻分布的模擬數(shù)據(jù)集

每個樣本點可表示為xi=(θi,φi),i=1,2,…,N，其中θi∈[0,π],φi∈[0,2π]，N為樣本總數(shù)。首先模擬產(chǎn)生了隨機均勻分布于單位球面的N=2 000個樣本，然后利用式(2)計算出這些樣本兩兩間的夾角Θij，設半徑r為0.5，利用式(1)，即可得到均勻分布于半徑為0.5的球面上的數(shù)據(jù)對應的距離矩陣。

2.1.2 球面正態(tài)分布的模擬數(shù)據(jù)集

本實驗用Kent分布[17]模擬產(chǎn)生了位于單位球面上的正態(tài)分布數(shù)據(jù)。這個數(shù)據(jù)集(N=913)主要由三部分組成，一部分是呈圓形的正態(tài)分布，另兩部分都是呈橢圓形的正態(tài)分布，而且這兩個橢圓形分布的數(shù)據(jù)，其分布大小和密度都不同。之后，得到一個分布于半徑為2的球面上的包含3個不同Kent分布的數(shù)據(jù)集對應的距離矩陣。

2.2 實驗結果

在實驗中，先取每個樣本點和其前nn(nn∈[0,N])個近鄰點的距離構成稀疏距離矩陣，將此作為球面嵌入算法的輸入。算法的輸出為所有樣本點在單位球面上的坐標。通過此坐標可以計算出嵌入單位球面空間后樣本點間的夾角Θij，然后利用式(27)計算出適合原始數(shù)據(jù)分布的球面半徑R。最后以均方根誤差(Root Mean Square Error, RMSE)為指標，衡量所有的原始數(shù)據(jù)兩兩間的夾角dij/r與嵌入球面后對應的數(shù)據(jù)兩兩間的夾角Θij間的誤差，見式(28)。用近鄰均方根誤差(Root Mean Square Error between Nearest Neighbors, NN_RMSE)來表示原始數(shù)據(jù)的近鄰點間的夾角與嵌入球面后對應的夾角之間的誤差，見式(29)。另外，半徑的估算誤差(Radius estimation Error, R_Error)計算見式(30)。

(28)

(29)

(30)

若這三個值越小，則說明將樣本嵌入球面空間的效果越好。

對于球面均勻分布的數(shù)據(jù)集，設置近鄰點個數(shù)nn={N,0.75N,0.5N,0.25N,0.05N}進行實驗，由于該算法的初始化是隨機的，因此在每個參數(shù)設置下同一個實驗都重復運行3次。最后，對于半徑為r=0.5的數(shù)據(jù)的實驗結果匯總于表1。

從表1中可以看出，針對不同的近鄰點個數(shù)設置，本文提出的嵌入算法都能得到較準確的結果，所有的均方根誤差(RMSE)基本都小于0.000 01，并且，當每個樣本點擁有的近鄰點數(shù)目越多，則算法嵌入的效果越好，得到的整體數(shù)據(jù)在單位球面上的分布與原始空間中的分布的一致性也越高。

另外，對于半徑r=3.2 的球面均勻分布的數(shù)據(jù)也做了相同的實驗，并得到了類似的測試結果?？梢妼鶆蚍植加谇蛎娴臄?shù)據(jù)，該算法即使在非近鄰點間距離信息缺失較多的情況下，仍然能夠較準確地還原出球面空間中數(shù)據(jù)的分布結構；而且算法還可以較精確地估算出適合數(shù)據(jù)分布的球面半徑。

接著，對球面正態(tài)分布(Kent分布)的數(shù)據(jù)也進行了類似的測試，其球面半徑的設置為r=2，并取近鄰點個數(shù)nn={N,700,500,300}，在每個參數(shù)設置下都重復運行3次，實驗結果見表1。在nn=300時，第一次運行的球面嵌入結果如圖1(a)所示。作為參照，圖1(b)顯示了原始數(shù)據(jù)的分布。

表1 嵌入算法對兩類模擬數(shù)據(jù)的處理結果

圖1 球面正態(tài)分布的數(shù)據(jù)

實驗結果表明，對于球面正態(tài)分布的數(shù)據(jù)，從圖1和表1都可以看出，其嵌入球面后的整體分布與原始分布比較接近，但是，整體嵌入后的誤差都明顯比表1中球面均勻分布數(shù)據(jù)的誤差大很多。另外，隨著近鄰點數(shù)目的減少，算法將其嵌入單位球面空間后，雖然可以較好地保持其近鄰點結構，但是非近鄰點間的分布卻與原始數(shù)據(jù)中的分布相差較大。例如表1中，對于球面正態(tài)分布的數(shù)據(jù)nn=300時，NN_RMSE都小于0.113，然而RMSE的值則都大于0.331；同時，對于適合原始數(shù)據(jù)分布的球面半徑的估算誤差也隨近鄰數(shù)的減小而增大。

此外，由于初始化是隨機的，本文提出的算法有時會陷入局部極小，因此導致實驗結果的不穩(wěn)定。例如，表1中，對于球面均勻分布的數(shù)據(jù)nn=1 500時，三次運行結果波動很大，第三次實驗的運行結果中RMSE和NN_RMSE比前兩次對應的誤差分別高了8個數(shù)量級。另外表1中, 對于球面正態(tài)分布的數(shù)據(jù)nn=913時，第二次運行結果的RMSE和NN_RMSE明顯比其他兩次運行結果的誤差低了8個數(shù)量級。所以，為保證實驗結果的準確性和正確性，每個實驗都要經(jīng)過多次運算。

3 結語

本文首次提出了一種針對球面半徑未知且原始數(shù)據(jù)間的非近鄰距離缺失情況下的球面嵌入算法。該算法能夠在只已知近鄰點間距離的情況下，將任意尺度的數(shù)據(jù)嵌入至單位球面，還可以估算出適合原始數(shù)據(jù)分布的球面半徑。

本文提出的算法對于球面均勻分布的數(shù)據(jù)，在非近鄰點間距離信息缺失較多的情況下，仍然能得到較準確的球面嵌入結果；但是，對于非均勻分布的數(shù)據(jù)，嵌入球面空間后，雖然近鄰點間的相對位置可以較好地保持，但是無法準確地還原非近鄰點間的相對位置，因此對于非均勻分布的數(shù)據(jù)，球面嵌入算法還有待改進。

)

[1] 田守財，孫喜利，路永鋼.基于最近鄰的隨機非線性降維[J].計算機應用,2016,36(2):377-381.(TIANSC,SUNXL,LUYG.Stochasticnonlineardimensionalityreductionbasedonnearestneighbors[J].JournalofComputerApplications, 2016, 36(2): 377-381.)

[2] 郝曉軍,閆京海,樊友誼.大數(shù)據(jù)分析過程中的降維方法[J].航天電子對抗,2014(4):58-60.(HAOXJ,YANJH,FANYY.Dimensionalityreductionoflargevolumesofdataanalysis[J].AerospaceElectronicWarfare, 2014(4): 58-60).

[3]COXMAA,COXTF.Multidimensionalscaling[J].EconometricInstituteResearchPapers, 2014, 46(2): 1050-1057.

[4]WEINBERGERKQ,SAULLK.Unsupervisedlearningofimagemanifoldsbysemidefiniteprogramming[C]//Proceedingsofthe2004IEEEComputerSocietyConferenceonComputerVisionandPatternRecognition.Washington,DC:IEEEComputerSociety, 2004: 988-995.

[5]TENENBAUMJB,DESILVAV,LANGFORDJC.Aglobalgeometricframeworkfornonlineardimensionalityreduction[J].Science, 2000, 290(5500): 2319-2323.

[6]VANDERMAATENL,HINTONG.Visualizingdatausingt-SNE[J].JournalofMachineLearningResearch, 2008, 9(11): 2579-2605.

[7]VANDERMAATENLJP,POSTMAEO,VANDENHERIKHJ.Dimensionalityreduction:acomparativereview[EB/OL]. [2016- 03- 08].https://static.aminer.org/pdf/PDF/000/272/419/comparative_investigation_on_dimension_reduction_and_regression_in_three_layer.pdf.

[8]WILSONRC,HANCOCKER,PEKALSKAE,etal.Sphericalandhyperbolicembeddingsofdata[J].IEEETransactionsonPatternAnalysisandMachineIntelligence, 2014, 36(11): 2255-2269.

[9]WILSONRC,HANCOCKER.Sphericalembeddingandclassification[C]//Proceedingsofthe2010JointIAPRInternationalConferenceonStructural,Syntactic,andStatisticalPatternRecognition.Berlin:Springer, 2010: 589-599.

[10] ELAD A, KELLER Y, KIMMEL R. Texture mapping via spherical multi-dimensional scaling [C]// Scale Space and PDE Methods in Computer Vision, LNCS 3459. Berlin: Springer, 2005: 443-455.

[11] COX M A A, COX T F. Multidimensional scaling on the sphere [M]// EDWARDS D, RAUN N E. Compstat. Berlin: Springer, 1988: 323-328.

[12] ROWEIS S T, SAUL L K. Nonlinear dimensionality reduction by locally linear embedding [J]. Science, 2000, 290(5500):2323-2326.

[13] KULLBACK S, LEIBLER R A. On information and sufficiency [J]. Annals of Mathematical Statistics, 1951, 22(1): 79-86.

[14] KULLBACK S. Information Theory and Statistics [M]. Hoboken, NJ: John Wiley and Sons, 1959.

[15] SUTSKEVER I. Training recurrent neural networks [EB/OL]. [2016- 02- 09]. http://www.cs.utoronto.ca/～ilya/pubs/ilya_sutskever_phd_thesis.pdf.

[16] SUTSKEVER I, MARTENS J, DAHL G, et al. On the importance of initialization and momentum in deep learning [EB/OL]. [2016- 02- 09]. http://www.cs.toronto.edu/～hinton/absps/momentum.pdf.

[17] KENT J T. The Fisher-Bingham distribution on the sphere [J]. Journal of the Royal Statistical Society, 1982, 44(1): 71-80.

This work is partially supported by the National Natural Science Foundation of China (61272213), the Fundamental Research Funds for the Central Universities (lzujbky-2016-k07, lzujbky-2016-142).

ZHANG Bianlan, born in 1991, M.S. candidate. Her research interests include pattern recognition.

LU Yonggang, born in 1974, Ph.D., professor. His research interests include pattern recognition, artificial intelligence, bioinformatics.

ZHANG Haitao, born in 1986, Ph.D. Her research interests include pattern recognition, software engineering.

Spherical embedding algorithm based on Kullback-Leibler divergence and distances between nearest neighbor points

ZHANG Bianlan, LU Yonggang*, ZHANG Haitao

(SchoolofInformationScienceandEngineering,LanzhouUniversity,LanzhouGansu730000,China)

Aiming at the problem that the existing spherical embedding algorithm cannot effectively embed the data into the low-dimensional space in the case that the distances between points far apart are inaccurate or absent, a new spherical embedding method was proposed, which can take the distances between the nearest neighbor points as input, and embeds high dimensional data of any scale onto the unit sphere, and then estimates the radius of the sphere which fit the distribution of the original data. Starting from a randomly generated spherical distribution, the Kullback-Leibler (KL) divergence was used to measure the difference of the normalized distance between each pair of neighboring points in the original space and the spherical space. Based on the difference, the objective function was constructed. Then, the stochastic gradient descent method with momentum was used to optimize the distribution of the points on the sphere until the result is stable. To test the algorithm, two types of spherical distribution data sets were simulated: which are spherical uniform distribution and Kent distribution on the unit sphere. The experimental results show that, for the uniformly distributed data, the data can be accurately embedded in the spherical space even if the number of neighbors is very small, the Root Mean Square Error (RMSE) of the embedded data distribution and the original data distribution is less than 0.000 01, and the spherical radius of the estimated error is less than 0.000 001; for spherical normal distribution data, the data can be embedded into the spherical space accurately when the number of neighbors is large. Therefore, in the case that the distance between points far apart are absent, the proposed method can still be quite accurate for low-dimensional data embedding, which is very helpful for the visualization of data.

spherical embedding; Kullback-Leibler (KL) divergence; stochastic gradient descent method; nearest neighbor

2016- 09- 19;

2016- 11- 11。

國家自然科學基金面上項目(61272213)；中央高校基本科研業(yè)務費專項資金資助項目(lzujbky-2016-k07，lzujbky-2016-142)。

張變蘭 (1991—)，女，山西呂梁人，碩士研究生，主要研究方向：模式識別； 路永鋼 (1974—)，男，甘肅隴南人，教授，博士，CCF會員，主要研究方向：模式識別、人工智能、生物信息； 張海濤 (1986—)，男，甘肅蘭州人，博士，主要研究方向：模式識別、軟件工程。

1001- 9081(2017)03- 0680- 04

10.11772/j.issn.1001- 9081.2017.03.680

TP181

A