基于KL散度和近邻点间距离的球面嵌入算法

针对现有球面嵌入算法在非近邻点间的距离度量不准确或缺失的情况下,不能有效地进行低维嵌入的问题,提出了一种新的球面嵌入算法,它能够只利用近邻点间的距离,将任何尺度的高维数据嵌入到单位球面上,同时求出适合原始数据分布的球面半径。该算法从一个随机产生的球面分布开始,利用KL散度衡量每对近邻点间的归一化距离在原始空间和球面空间中的差异,并基于此差异构建出目标函数,然后再用带有动量的随机梯度下降法,不断优化球面上点的分布,直到结果稳定。为了测试算法,模拟产生了两类球面分布数据:分别是球面均匀分布和球面正态分布的数据。实验结果表明,对于球面均匀分布的数据,即使在近邻点个数很少的情况下,仍然能够将数据准确地嵌入球面空间,嵌入后的数据分布与原始数据分布的均方根误差(RMSE)低于0.000 01,且球面半径的估算误差低于0.000 001;而对于球面正态分布的数据,在近邻点个数较多的情况下,该算法也可以将数据较准确地嵌入球面空间。因此,在非近邻点间距离缺失的情况下,所提方法仍然可以较准确地对数据进行低维嵌入,这非常有利于数据的可视化研究。

平面及球面嵌入图α-定向的flip-距离

为研究平面嵌入图的给定出度序列的定向问题,Felsner引入了α-定向及flip变换,并进一步证明了一个平面嵌入图的所有α-定向在flip变换下构成一个分配格.本文中给出平面嵌入图的一个α-定向可由另一个α-定向通过一系列flip变换而得到的一个充分必要条件.与之平行,证明了球面嵌入图的任意两个α-定向均可通过一系列flip变换而相互得到.最后,给出了所需最少flip变换的数目.