張變蘭，路永鋼，張海濤

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

基于KL散度和近鄰點(diǎn)間距離的球面嵌入算法

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

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

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

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

0 引言

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

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

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

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

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

1 球面嵌入算法

1.1 球面上的距離計(jì)算

在球面坐標(biāo)系中，球面上的點(diǎn)的坐標(biāo)為xi=(θi,φi)，極角θi表示向量xi與z軸的夾角，方位角φi表示向量xi與x軸的夾角。在球面上，兩點(diǎn)間的距離為兩向量間夾角對(duì)應(yīng)的球面上的弧長。若在半徑為r的球面上，兩點(diǎn)間的夾角記為Θij，則它們?cè)诖饲蛎嫔系木嚯x可表示為：

dij=rΘij

(1)

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

(2)

1.2 球面嵌入算法

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

(3)

dij=‖xi-xj‖

(4)

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

(5)

Θij=‖yi-yj‖

(6)

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

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

(7)

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

(8)

(9)

(10)

(11)

(12)

(13)

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

(14)

(15)

(16)

(17)

(18)

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

(19)

其中:

(20)

(21)

(22)

(23)

(24)

(25)

(26)

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

(27)

2 實(shí)驗(yàn)和結(jié)果分析

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

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

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

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

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

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

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

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

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

(28)

(29)

(30)

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

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

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

另外，對(duì)于半徑r=3.2 的球面均勻分布的數(shù)據(jù)也做了相同的實(shí)驗(yàn)，并得到了類似的測(cè)試結(jié)果。可見對(duì)均勻分布于球面的數(shù)據(jù)，該算法即使在非近鄰點(diǎn)間距離信息缺失較多的情況下，仍然能夠較準(zhǔn)確地還原出球面空間中數(shù)據(jù)的分布結(jié)構(gòu)；而且算法還可以較精確地估算出適合數(shù)據(jù)分布的球面半徑。

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

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

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

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

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

3 結(jié)語

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

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

)

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

[2] 郝曉軍,閆京海,樊友誼.大數(shù)據(jù)分析過程中的降維方法[J].航天電子對(duì)抗,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。

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

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

1001- 9081(2017)03- 0680- 04

10.11772/j.issn.1001- 9081.2017.03.680

TP181

A