留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

高维数据非参数密度估计的低维流形代表点法

王树良 李英 耿晶

王树良, 李英, 耿晶. 高维数据非参数密度估计的低维流形代表点法[J]. 武汉大学学报 ● 信息科学版, 2021, 46(1): 65-70. doi: 10.13203/j.whugis20160115
引用本文: 王树良, 李英, 耿晶. 高维数据非参数密度估计的低维流形代表点法[J]. 武汉大学学报 ● 信息科学版, 2021, 46(1): 65-70. doi: 10.13203/j.whugis20160115
WANG Shuliang, LI Ying, GENG Jing. A Low-Dimensional Manifold Representative Point Method to Estimate the Non-parametric Density for High-Dimensional Data[J]. Geomatics and Information Science of Wuhan University, 2021, 46(1): 65-70. doi: 10.13203/j.whugis20160115
Citation: WANG Shuliang, LI Ying, GENG Jing. A Low-Dimensional Manifold Representative Point Method to Estimate the Non-parametric Density for High-Dimensional Data[J]. Geomatics and Information Science of Wuhan University, 2021, 46(1): 65-70. doi: 10.13203/j.whugis20160115

高维数据非参数密度估计的低维流形代表点法

doi: 10.13203/j.whugis20160115
基金项目: 

国家重点研发计划 2020YFC0832600

国家自然科学基金 62076027

详细信息

A Low-Dimensional Manifold Representative Point Method to Estimate the Non-parametric Density for High-Dimensional Data

Funds: 

The National Key Research and Development Program of China 2020YFC0832600

the National Natural Science Fundation of China 62076027

More Information
  • 摘要: 非参数核方法由于采用统一的度量标准,在大数据中利用高维样本数据学习时容易遭遇维数灾难问题。挖掘高维空间中的低维几何特性,有助于揭示数据分布的流形结构,进而利用有限样本的高维数据在低维子空间逼近数据的真实分布。基于此,提出一种新的高维数据密度非参数估计的低维流形代表点法,通过从高维空间中挖掘数据分布的几何结构来估计密度。首先,通过寻找局部区域内能够代表流形结构主方向的点,计算局部协方差矩阵,描述局部的数据分布;然后,考虑流形结构中附近数据点不同的影响,根据每个样本数据点对密度的贡献进行加权。与传统的核密度估计方法和流形核密度方法进行了对比实验,结果表明,该方法能够快速稳健地进行密度估计,反映数据的真实分布。
  • 图  1  最近邻流形学习的密度估计方法的参数选择

    Figure  1.  Parameter Selection of Nearest Neighbor Manifold Method

    图  2  本文方法的参数选择

    Figure  2.  Parameter Selection of Our Proposed Method

    图  3  二维空间中3种密度估计方法的非参数密度估计结果

    Figure  3.  Non-parametric Density Estimation Results of Three Different Methods in Two-Dimensional Space

    图  4  数据样本1的非参数密度估计结果

    Figure  4.  Non-parametric Density Estimation Results of Dataset 1

    图  5  数据样本2的非参数密度估计结果

    Figure  5.  Non-parametric Density Estimation Results of Dataset 2

    表  1  3种密度估计方法的结果比较

    Table  1.   Comparison Results of Three Different Density Estimation Methods

    方法 最优参数 预测误差(训练集) 似然误差均值(测试集)
    传统的核密度估计方法 σ=0.01 1.386 5 1.425 5
    基于最近邻流形学习的密度估计方法 d=1, k=20, σ=0.01 2.312 6 2.264 2
    本文方法 d=1, k =5, σ=0.01 6.316 6 6.522 2
    下载: 导出CSV
  • [1] Bellman R. Adaptive Control Processes: A Guided Tour[M]. New Jersey: Princeton University Press, 1961
    [2] 刘瑜, 康朝贵, 王法辉.大数据驱动的人类移动模式和模型研究[J].武汉大学学报·信息科学版, 2014, 39(6):660-666 doi:  10.13203/j.whugis20140149

    Liu Yu, Kang Chaogui, Wang Fahui. Towards Big Data-Driven Human Mobility Patterns and Models[J].Geomatics and Information Science of Wuhan University, 2014, 39(6): 660-666 doi:  10.13203/j.whugis20140149
    [3] Shankar K, Lakshmanaprabu S K, Gupta D.et al. Optimal Feature-Based Multi-Kernel SVM Approach for Thyroid Disease Classification[J]. The Journal of Supercomputing, 2020, 76(2): 1 128-1 143 doi:  10.1007/s11227-018-2469-4
    [4] 周源, 方圣辉, 李德仁.利用光谱角敏感森林的高光谱数据快速匹配方法[J].武汉大学学报·信息科学版, 2011, 36(6): 687-690 http://ch.whu.edu.cn/article/id/577

    Zhou Yuan, Fang Shenghui, Li Deren. A Fast Spectral Matching Algorithm for Larger-Scale Hyperspectral Data:Spectral Angle Sensitive Forest[J]. Geomatics and Information Science of Wuhan University, 2011, 36(6): 687-690 http://ch.whu.edu.cn/article/id/577
    [5] Ibtehaz N, Rahman M S. MultiResUNet : Rethinking the U-Net Architecture for Multimodal Biomedical Image Segmentation[J]. Neural Networks, 2020, 121: 74-87 doi:  10.1016/j.neunet.2019.08.025
    [6] 张晓祥.大数据时代的空间分析[J].武汉大学学报·信息科学版, 2014, 39(6): 655-659 doi:  10.13203/j.whugis20140143

    Zhang Xiaoxiang. Spatial Analysis in the Era of Big Data[J]. Geomatics and Information Science of Wuhan University, 2014, 39(6): 655-659 doi:  10.13203/j.whugis20140143
    [7] Candes E J, Li X, Ma Y, et al. Robust Principal Component Analysis[J]. Journal of the ACM, 2011, 58(3):1-11
    [8] Jolliffe I T, Cadima J. Principal Component Analysis: A Review and Recent Developments[J]. Philosophical Transactions of the Royal Society A, 2016, 374(2 065): 20150202 https://pubmed.ncbi.nlm.nih.gov/26953178/
    [9] Scornet E. Random Forests and Kernel Methods[J].IEEE Transactions on Information Theory, 2016, 62(3): 1 485-1 500 doi:  10.1109/TIT.2016.2514489
    [10] Cox T, Cox M. Multidimensional Scaling[C]. Chapman & Hall, London, UK, 1994
    [11] Vincent P, Bengio Y. Manifold Parzen Windows[C]. Advances in Neural Information Processing Systems, Cambridge, UK, 2003
    [12] Goldberger J, Roweis S, Hinton G, et al. Neighbourhood Component Analysis[C].Advances in Neural Information Processing Systems, Cambridge, UK, 2005
    [13] Akaike H. An Approximation to the Density Function[J]. Annals of the Institute of Statistical Mathematics, 1954, 6:127-132 doi:  10.1007/BF02900741
    [14] Parzen E. On the Estimation of a Probability Density Function and the Mode[J]. Annals of Mathematical Statistics, 1962, 33:1 065-1 076 doi:  10.1214/aoms/1177704472
    [15] Rosenblatt F. Remarks on Some Nonparametric Estimates of a Density Function[J]. Annals of Mathematical Statistics, 1956, 27:832-837 doi:  10.1214/aoms/1177728190
    [16] Padhraic S. Model Selection for Probabilistic Clustering Using Cross-Validated Likelihood[J]. Statistics and Computing, 2000, 9: 63-72 doi:  10.1023/A:1008940618127
  • [1] 吴京航, 桂志鹏, 申力, 吴华意, 刘洪波, 李锐, 梅宇翱, 彭德华.  顾及格网属性分级与空间关联的人口空间化方法 . 武汉大学学报 ● 信息科学版, 2022, 47(9): 1364-1375. doi: 10.13203/j.whugis20200379
    [2] 陈镜渊, 朱武, 张勤, 李振洪.  联合全极化SAR和IRI估计三维电子密度分布 . 武汉大学学报 ● 信息科学版, 2021, 46(11): 1677-1685. doi: 10.13203/j.whugis20210061
    [3] 郭宇达, 朱欣焰, 呙维, 佘冰.  基于Spark计算框架的路网核密度估计并行算法 . 武汉大学学报 ● 信息科学版, 2020, 45(2): 289-295. doi: 10.13203/j.whugis20180473
    [4] 田宇, 柯小平, 王勇.  利用航空重力梯度反演Kauring试验场三维密度结构 . 武汉大学学报 ● 信息科学版, 2019, 44(4): 501-509. doi: 10.13203/j.whugis20160503
    [5] 王腾, 王艳东, 赵晓明, 付小康, 蒋波涛.  顾及道路网约束的商业设施空间点模式分析 . 武汉大学学报 ● 信息科学版, 2018, 43(11): 1746-1752. doi: 10.13203/j.whugis20160558
    [6] 王娇, 周成虎, 程维明.  全月球撞击坑的空间分布模式 . 武汉大学学报 ● 信息科学版, 2017, 42(4): 512-519. doi: 10.13203/j.whugis20140893
    [7] 杨喜平, 方志祥, 赵志远, 萧世伦, 尹凌.  顾及手机基站分布的核密度估计城市人群时空停留分布 . 武汉大学学报 ● 信息科学版, 2017, 42(1): 49-55. doi: 10.13203/j.whugis20150646
    [8] 禹文豪, 艾廷华, 杨敏, 刘纪平.  利用核密度与空间自相关进行城市设施兴趣点分布热点探测 . 武汉大学学报 ● 信息科学版, 2016, 41(2): 221-227. doi: 10.13203/j.whugis20140092
    [9] 简涛, 黄晓冬, 王捷, 何友.  基于修正最大似然估计的距离扩展目标检测器 . 武汉大学学报 ● 信息科学版, 2016, 41(6): 791-796. doi: 10.13203/j.whugis20140651
    [10] 姚宜斌, 余琛, 胡羽丰, 刘强.  利用非气象参数对流层延迟估计模型加速PPP收敛 . 武汉大学学报 ● 信息科学版, 2015, 40(2): 188-192+221.
    [11] 周新刚, 乐阳, 叶嘉安, 王海军, 仲腾.  动态数据空间分析的不确定性问题——以城市中心识别为例 . 武汉大学学报 ● 信息科学版, 2014, 39(6): 701-705. doi: 10.13203/j.whugis20140074
    [12] 甄艳, 刘学军, 王美珍.  匹配点分布密度约束下的基础矩阵估计 . 武汉大学学报 ● 信息科学版, 2013, 38(10): 1167-1171.
    [13] 孙伟伟, 刘春, 施蓓琦, 李巍岳.  等距映射降维用于高光谱影像低维流形特征提取 . 武汉大学学报 ● 信息科学版, 2013, 38(6): 642-647.
    [14] 徐爱萍, 圣文顺, 舒红.  时空积和模型的数据插值与交叉验证 . 武汉大学学报 ● 信息科学版, 2012, 37(7): 766-769.
    [15] 陈传法, 卢秀山.  利用改进非参数估计法的DEM误差置信区间估计 . 武汉大学学报 ● 信息科学版, 2011, 36(11): 1340-1343.
    [16] 杜培军, 王小美, 谭琨, 夏俊士.  利用流形学习进行高光谱遥感影像的降维与特征提取 . 武汉大学学报 ● 信息科学版, 2011, 36(2): 148-152.
    [17] 王新洲, 游扬声, 刘星, 史文中.  GIS叠置图层方差分量的极大似然估计 . 武汉大学学报 ● 信息科学版, 2005, 30(10): 892-896.
    [18] 游扬声, 王新洲.  基于信息扩散的极大似然估计 . 武汉大学学报 ● 信息科学版, 2003, 28(5): 562-565.
    [19] 童恒庆.  使用正交多项式核的密度导数估计 . 武汉大学学报 ● 信息科学版, 1996, 21(3): 302-305.
    [20] 周世健.  方差的边缘极大似然估计 . 武汉大学学报 ● 信息科学版, 1993, 18(2): 48-54.
  • 加载中
图(5) / 表(1)
计量
  • 文章访问数:  715
  • HTML全文浏览量:  117
  • PDF下载量:  35
  • 被引次数: 0
出版历程
  • 收稿日期:  2019-05-25
  • 刊出日期:  2021-01-05

高维数据非参数密度估计的低维流形代表点法

doi: 10.13203/j.whugis20160115
    基金项目:

    国家重点研发计划 2020YFC0832600

    国家自然科学基金 62076027

    作者简介:

    王树良,博士,教授,主要研究方向为空间数据挖掘。slwang2005@whu.edu.cn

    通讯作者: 耿晶,博士后。janegeng@bit.edu.cn
  • 中图分类号: P208

摘要: 非参数核方法由于采用统一的度量标准,在大数据中利用高维样本数据学习时容易遭遇维数灾难问题。挖掘高维空间中的低维几何特性,有助于揭示数据分布的流形结构,进而利用有限样本的高维数据在低维子空间逼近数据的真实分布。基于此,提出一种新的高维数据密度非参数估计的低维流形代表点法,通过从高维空间中挖掘数据分布的几何结构来估计密度。首先,通过寻找局部区域内能够代表流形结构主方向的点,计算局部协方差矩阵,描述局部的数据分布;然后,考虑流形结构中附近数据点不同的影响,根据每个样本数据点对密度的贡献进行加权。与传统的核密度估计方法和流形核密度方法进行了对比实验,结果表明,该方法能够快速稳健地进行密度估计,反映数据的真实分布。

English Abstract

王树良, 李英, 耿晶. 高维数据非参数密度估计的低维流形代表点法[J]. 武汉大学学报 ● 信息科学版, 2021, 46(1): 65-70. doi: 10.13203/j.whugis20160115
引用本文: 王树良, 李英, 耿晶. 高维数据非参数密度估计的低维流形代表点法[J]. 武汉大学学报 ● 信息科学版, 2021, 46(1): 65-70. doi: 10.13203/j.whugis20160115
WANG Shuliang, LI Ying, GENG Jing. A Low-Dimensional Manifold Representative Point Method to Estimate the Non-parametric Density for High-Dimensional Data[J]. Geomatics and Information Science of Wuhan University, 2021, 46(1): 65-70. doi: 10.13203/j.whugis20160115
Citation: WANG Shuliang, LI Ying, GENG Jing. A Low-Dimensional Manifold Representative Point Method to Estimate the Non-parametric Density for High-Dimensional Data[J]. Geomatics and Information Science of Wuhan University, 2021, 46(1): 65-70. doi: 10.13203/j.whugis20160115
  • 在大数据背景下,高维数据灾难是机器学习、数据压缩、模式识别、可视化等领域面临的关键问题之一[1-6]。统计学习算法通常要求一定的取样密度才能进行有效学习,然而随着数据维数的增加,所需数据量成指数级增加。如何利用有限样本高维数据进行有效的学习和处理,为下一步的分类、去噪、跟踪定位等工作提供有意义的信息是研究热点之一。在无监督学习过程中,通常使用降维和密度估计方法分析数据,揭示大数据集本身的特征和结构。降维是有效处理高维数据的方法,通过对高维数据进行变换提取子空间,在低维空间保留原始数据的重要信息,常用的方法包括主成分分析[7-8]、基于核的主成分分析[9]、多维尺度分析[10]等。密度估计方法通过学习数据的真实分布对新的对象进行预测和评判,可分为参数密度估计方法和非参数密度估计方法。参数密度估计方法通常能够有效地逼近简单的密度函数,但是不能准确地逼近多峰密度函数。非参数方法可以灵活地模拟复杂的密度分布。然而对于高维数据,非参数核方法更易遭遇维数灾难问题。在利用非参数方法估计密度时,高维空间和低维空间有很大不同,所需样本量随着维数的增加会讯速增加。

    为了克服维数灾难问题,文献[11]提出基于流形结构的非参数密度估计方法,假设高维数据中嵌入一些低维流形且真实的密度函数,其分布接近高维空间中的低维流形,则数据点分布在流形或流形附近。根据每个数据点的最近邻点分布,估计局部协方差矩阵,推断流形的局部结构,进而估计核密度[12]。但该方法计算成本较高,且算法不稳健。

    通过挖掘嵌入在高维空间中的低维几何特性,可以在流形上建立模型,避免高维空间中的维数灾难问题。当高维数据中嵌入一个低维流形时,概率密度分布取决于流形结构。在进行密度估计时不仅要考虑数据的属性关系,还要考虑数据的几何结构。由于数据潜在的分布取决于流形的结构,密度估计主要受局部区域流形上的点影响,因此本文提出一个更稳健的方法来捕捉流形的局部结构,通过寻找局部区域内能够代表流形结构主方向的点,计算局部协方差矩阵,考虑流形结构上或附近数据点不同的影响,根据样本数据点对密度的贡献进行加权。

    • 假定XRn是一个n维的随机变量,给定样本集合$ X = \left\{ {{\boldsymbol{x}_1}, {\boldsymbol{x}_2} \cdots {\boldsymbol{x}_l}} \right\}, {\boldsymbol{x}_i} = {\left( {{x_{i1}}, {x_{i2}} \cdots {x_{in}}} \right)^\prime } $是n维向量。参数高斯核密度估计是围绕每个数据点xi以均值、方差为超参数形成一个高斯模型。任意数据点xRn的核密度估计值由所有样本点的高斯模型相互叠加形成,密度估计[13-15]可定义为:

      $$ \hat p\left( \boldsymbol{x} \right) = \frac{1}{l}{N_{{x_i}, h}}\left( \boldsymbol{x} \right) $$ (1)

      式中,h代表窗宽。式(1)常用的核是高斯核,计算如下:

      $$ {N_{{\boldsymbol{x}_i}, h}}\left( \boldsymbol{x} \right) = \frac{1}{{\sqrt {{{\left( {2{\rm{ \mathsf{ π} }}{h^2}} \right)}^n}} }}{{\rm{e}}^{ - \frac{1}{{2{h^2}}}\boldsymbol{x} - {\boldsymbol{x}_i}^2}} $$ (2)

      固定的标量参数意味着观测数据点的能量分布向各个方向均匀散开。考虑到数据不同维度上具有不同的尺度,需要对数据进行白化。白化又称漂白或者球化,是对原始数据进行变换,使变换后数据的协方差矩阵为单位阵。非参数密度估计的步骤如下:(1)对数据进行线性变换,计算其单位协方差阵;(2)对变换后的数据进行核密度估计;(3)再变换回去得到最终的估计,等价于在原始数据上的核估计时使用全高斯核,协方差矩阵与训练集的协方差成正比。

    • 假定数据中存在低维流形,则通过计算局部协方差学习流形上的局部结构来估计密度[11]。如果每个样本点的近邻点可以反映此样本点局部的流形特征,从而更好地估计密度,则函数密度估计如下:

      $$ \hat p\left( \boldsymbol{x} \right) = \frac{1}{l}{N_{{x_i}, {C_i}}}\left( \boldsymbol{x} \right) $$ (3)

      式中,$ {N_{{x_i}, c}}\left( \boldsymbol{x} \right) $是多维高斯核函数;Ci协方差矩阵。式(3)中的多维高斯密度函数的定义为:

      $$ {N_{{x_i}, {C_i}}}\left( \boldsymbol{x} \right){\rm{ = }}\frac{1}{{\sqrt {{{\left( {2{\rm{ \mathsf{ π} }}} \right)}^n}\left\| {{\boldsymbol{C}_i}} \right\|} }}{{\rm{e}}^{ - \frac{1}{2}{{\left( {\boldsymbol{x} - {\boldsymbol{x}_i}} \right)}^\prime }{\boldsymbol{C}^{ - 1}}\left( {\boldsymbol{x} - {\boldsymbol{x}_i}} \right)}} $$ (4)

      式中,‖Ci‖是协方差矩阵Ci的秩。

      给定样本点xi,通过xi及其最近邻点分布揭示流行的局部几何结构。对于每个样本点xi,找到其k个最近邻点来计算一个局部的协方差矩阵Ci。事实上,如果xi及其周围的点沿着特定的方向集中分布,那么在正交方向上协方差取值趋向于零。

    • 为了使协方差Ci能够更好地反映流形局部结构的主方向且降低噪声的干扰,我们试图发现每个样本xi沿着流形主方向分布的近邻点而不是最近邻点。

      给定样本xi及所有的样本数据$ X = \left\{ {{\boldsymbol{x}_1}, {\boldsymbol{x}_2} \cdots {\boldsymbol{x}_l}} \right\} $。首先找到样本xim个最近邻点$ \left\{ {{\boldsymbol{y}_1}, {\boldsymbol{y}_2} \cdots {\boldsymbol{y}_m}} \right\} \subset \left\{ {{\boldsymbol{x}_1}, {\boldsymbol{x}_2} \cdots {\boldsymbol{x}_l}} \right\} $,通过计算找到其中一个沿着流形主方向分布的点设为ytt∈{1, 2…m}则样本点yt即为第一个优化的近邻点。同理,通过在yt的最近邻点中找到下一个优化后的近邻点,直到找到m个近邻点。

      进一步给定数据点x,考虑其密度估计主要来自于附近点的高斯模型相互叠加,因此密度估计定义如下:

      $$ \hat p\left( \boldsymbol{x} \right) = \frac{1}{m}{N_{{\boldsymbol{x}_{v\left( i \right)}}, \boldsymbol{C}\left( {{x_{v\left( i \right)}}} \right)}}\left( \boldsymbol{x} \right) $$ (5)

      式中,v(·)为x在最近邻点在所有样本中编号的索引函数;$ C\left( {{\boldsymbol{x}_{v\left( i \right)}}} \right) $为样本点$ {{\boldsymbol{x}_{v\left( i \right)}}} $优化的近邻点的局部协方差。

      给定n维数据集$ X = \left\{ {{\boldsymbol{x}_1}, {\boldsymbol{x}_2} \cdots {\boldsymbol{x}_l}} \right\} $,可得:

      $$ \hat p\left( \boldsymbol{x} \right) \to \frac{1}{l}{N_{{\boldsymbol{x}_{v\left( i \right)}}, \boldsymbol{C}\left( {{x_{v\left( i \right)}}} \right)}}\left( \boldsymbol{x} \right) $$ (6)

      当$ \forall {\boldsymbol{x}_j} \in X - {V_x} $。因为$ \boldsymbol{C}\left( {{\boldsymbol{x}_{v\left( i \right)}}} \right) $具有半正定性,同理C(xj)-1也是半正定矩阵,所以有:

      $$ \boldsymbol{C}{({\boldsymbol{x}_j})^{ - 1}} = \boldsymbol{VDV'} $$ (7)

      式中,D是对角特征值矩阵,$ \boldsymbol{D} = {\rm{diag}}\left( {{\lambda _1}, {\lambda _2} \cdots {\lambda _n}} \right), {\lambda _q} \ge 0, q = 1, 2 \cdots n;\boldsymbol{V} $是对应的特征列向量。

      非参数密度估计的低维流代表点法估计密度分布的步骤如下:(1)给定测试样本x,找到其最近邻点$ {\boldsymbol{x}_i}, i \in \left\{ {v\left( 1 \right), v\left( 2 \right) \cdots v\left( m \right)} \right\} $。(2)通过发现每个最近邻点xi的最优邻近点,计算局部协方差矩阵。由于需要计算协方差矩阵的逆矩阵,因此通常添加一个足够小的扰动确保协方差矩阵可逆,即$ \boldsymbol{C}\left( {{\boldsymbol{x}_{v\left( i \right)}}} \right) = \boldsymbol{C}\left( {{\boldsymbol{x}_{v\left( i \right)}}} \right) + {\sigma ^2}\boldsymbol{I} $。对规则化后的局部协方差矩阵进行特征值分解,将特征值按照从大到小进行排序,即$ \boldsymbol{C} = \boldsymbol{VDV'} $,前d个最大特征值对应的特征向量反映局部邻域分布的主方向。(3)假定后n-d个特征值及其对应的特征向量是噪声,为了提高算法的运行速度,令后n-d个特征值具有相同的噪声。零化后n-d个特征值,若后n-d个特征值取零值,再添加σ2到所有特征值上,由此可以快速地逼近计算$ {N_{{\boldsymbol{x}_{v\left( i \right)}}, \boldsymbol{c}\left( {{\boldsymbol{x}_{v\left( i \right)}}} \right)}}\left( \boldsymbol{x} \right) $。(4)重复实施步骤(2)、(3),直到对测试样本x的所有最近邻点xi计算得到$ {N_{{\boldsymbol{x}_{v\left( i \right)}}, \boldsymbol{c}\left( {{\boldsymbol{x}_{v\left( i \right)}}} \right)}}\left( \boldsymbol{x} \right) $,再根据式(5)进行密度估计。

    • 本文针对有限高维样本数据的维数灾难,提出了新的低维流形代表点法,通过发现数据在低维子空间的几何分布来逼近真实密度。为了验证密度估计是否能够反映数据的真实分布,利用5次交叉验证似然估计方法来评价本文方法的性能[16]

      给定τ:{1,1⋯l} → {1,2,3,4,5}是一个索引,指示数据点被随机划分成5个子集,比如τ(1)=5是指第一个数据点被分配到第5个子集中。最终所有分割的训练数据被分配到5个子集中,则预测误差计算如下:

      $$ V\left( {\hat p} \right) = \frac{1}{l}\mathop \sum \limits_{i = 1}^l {\rm{log}}\left( {{{\hat p}^{ - \tau \left( i \right)}}\left( {{\boldsymbol{x}_i}} \right)} \right) $$ (8)

      将本文方法与传统的核密度估计、基于最近邻方法学习流形结构的核密度估计[11]进行对比。传统的高斯核密度估计方法通过窗宽参数σ来决定估计的结果;基于最近邻流形学习的密度估计方法涉及3个参数,包括最近邻个数k、局部数据分布的主方向个数d和噪声参数σ;本文提出的低维流形代表点法中,参数包括局部区域内优化的近邻点个数m、局部数据分布的主方向个数d和噪声参数σ

      高斯核密度估计方法的算法复杂度为O(l2);基于最近邻流形学习的密度估计方法的算法复杂度为O(lk)。本文提出的低维流形代表点法的算法复杂度为O(m2)。显然,对于大数据集,ml,因此,本文方法具有最低的算法复杂度,运行速度最快。5次交叉验证似然估计评价模型时,实验数据划分为训练集和测试集。训练集用来训练模型并获得最优参数。基于训练模型,在测试集中评估上述3种方法进行密度估计的结果。

    • 为了更好地验证本研究提出的低维流形代表点法的实用性和有效性,分别在二维、三维空间中进行对比实验。

      在第1组实验中,训练数据由500个数据点组成,测试数据集由10 000个数据点组成。训练集和测试集由以下分布生成:

      $$ \left\{ {\begin{array}{*{20}{l}} {x = 0.04t\;{\rm{sin}}t + {\epsilon_x}}\\ {y = 0.04t{\rm{cos}}t + {\epsilon_y}} \end{array}} \right. $$ (9)

      式中,变量t服从均匀分布t~U(3.15);$ { \epsilon_x}和 { \epsilon_y} $服从正态分布,$ { \epsilon_x} \sim N\left( {0, 0.01} \right), { \epsilon_y} \sim N\left( {0, 0.01} \right) $。

      为了选择合适的参数值,首先对参数dkmσ取不同数值进行评估实验。根据式(4),利用5次交叉验证似然估计方法分别对不同参数取值的子模型进行评估,从而选择最优参数值。

      图 1(a)1(b)为基于最近邻流形学习的密度估计方法在参数d分别取值1、2,kσ取不同值时进行密度估计的评估结果。图 2(a)2(b)为本文算法在参数d分别取值1、2,kσ取不同值时进行密度估计的评估结果。

      图  1  最近邻流形学习的密度估计方法的参数选择

      Figure 1.  Parameter Selection of Nearest Neighbor Manifold Method

      图  2  本文方法的参数选择

      Figure 2.  Parameter Selection of Our Proposed Method

      图 1图 2可知,基于最近邻流形学习的密度估计方法和本文方法中参数d=1时的子模型表现均优于d=2时的子模型表现。这说明二维数据中嵌入一个一维流形,与生成的数据相符。而且本文方法中所有子模型的效果均优于相应的基于最近邻流形学习算法中的子模型效果,更能够捕捉数据中的低维流形结构,从而更准确地刻画数据的潜在分布。

      基于交叉验证似然方法可得到每种密度估计方法的最优参数设置。给定最优参数后,在测试集上进一步比较3种方法进行密度估计的结果(见表 1),3种方法在二维空间中的密度估计结果如图 3所示。红色的数据点是训练集,灰色的区域是由密度估计大于给定阈值的测试数据点。图 3(a)为传统的核密度估计方法结果,窗宽为一个单一超参数,σ=0.01;图 3(b)是基于最近邻流形学习的密度估计方法结果,其中参数配置为d=1,k=20,σ=0.01;图 3(c)是本文方法的密度估计结果,其中参数配置为d=1,k=5,σ=0.01。

      表 1  3种密度估计方法的结果比较

      Table 1.  Comparison Results of Three Different Density Estimation Methods

      方法 最优参数 预测误差(训练集) 似然误差均值(测试集)
      传统的核密度估计方法 σ=0.01 1.386 5 1.425 5
      基于最近邻流形学习的密度估计方法 d=1, k=20, σ=0.01 2.312 6 2.264 2
      本文方法 d=1, k =5, σ=0.01 6.316 6 6.522 2

      图  3  二维空间中3种密度估计方法的非参数密度估计结果

      Figure 3.  Non-parametric Density Estimation Results of Three Different Methods in Two-Dimensional Space

      图 3可知,传统的核密度估计中出现过多的断口,不能很好地描述数据的分布特征。基于最近邻流形学习的密度估计方法是通过每个数据点的k个最近邻点来估计局部流形几何结构,所以密度估计能够反映数据潜在的流形结构。然而某些数据点的k个最近邻点并不能捕捉到流形主方向,从而出现小的断口。本文方法通过发现数据点分布流形上或周围的点来刻画流形主方向,能够更稳健地反映数据的分布。因此,本文方法效果最好,基于最近邻流形学习的方法次之。

      在第2组实验中,以三维实验数据为例,图 4(a)图 5(a)为从真实数据分布中抽取的数据样本1、数据样本2,图 4(b)4(c)4(d)图 5(b)5(c)5(d)分别是使用传统的核密度估计方法、基于最近邻流形学习的密度估计方法和本文方法获得的结果。显然,三维数据实验更能清晰地反映本文方法的稳健性。

      图  4  数据样本1的非参数密度估计结果

      Figure 4.  Non-parametric Density Estimation Results of Dataset 1

      图  5  数据样本2的非参数密度估计结果

      Figure 5.  Non-parametric Density Estimation Results of Dataset 2

    • 针对非参数核密度估计遭遇维数灾难问题,本文提出了一种改进的核密度估计方法,逼近数据的真实分布。该方法假定高维数据中嵌入了低维流形,数据分布在流形上或附近。由此,每个样本的贡献主要由低维子空间中局部的流行结构决定。通过学习局部流形的结构来估计样本点对密度的贡献。本文方法考虑到每个数据点的密度主要受局部流形区域内近邻样本点的影响,因此,在估计密度时加权叠加分布在流形上或附近的样本点的贡献;而且在估计每个样本点的贡献时,通过搜索局部流形上的近邻点而不只是样本点的最近邻点来更好地计算样本点的贡献。为了验证本文方法的效果,与传统的核密度估计、基于最近邻流形学习的密度估计方法进行了对比实验。实验结果表明,本文方法能够更稳健、有效地逼近数据的真实分布。

参考文献 (16)

目录

    /

    返回文章
    返回