论文研究-用于多流形分类的核等距映射算法.pdf

所需积分/C币:15 2019-09-12 07:15:14 670KB .PDF
28
收藏 收藏
举报

核等距映射(Kernel ISOMAP)算法具有较好的泛化性能,但不能直接用于多流形的分类。在多流形下,准确判定新数据点所在的流形是其获得良好泛化性能的基础,因此,提出了能够用于多流形分类的核等距映射算法。该算法根据同一流形上邻近局部切空间的相似性能够准确判定新数据点所在的流形,并对目前核等距映射算法中新数据点低维表示的计算过程进行了简化,从而具有良好的泛化性能。实验结果证实,该算法具有较高的分类准确率。
邵超,万春红,李洁颖:用于多流形分类的核等距映射算法 2016,52(4)123 (x)x)>(0是由Mrer核矩阵5所定义的从原始其中,f(=∑∑(xx)-n2((,x)-k)仅 空问到特征空问的非线性映射函数),计算如下∞: k(x,x,)=<(x),p(x) 与x相关,而与广无关,即有: (d2(x,x)- K)(9 ∑f(x)「=f(x)∑=0 其中,dl(x,x,)=a(x,x)+c 因此,式(8)可简写为 3用于多流形分类的核 ISOMAP算法 以上核 ISOMAP算法存在的主要问题有 ∑(d(x,x)-1∑(x,x) (1)c的确定需要计算矩阵L的最大特征值c*,时 间复杂度太大 (2)1为λ1的‖线性平移,需要对S重新执行 2√(2(x)-1∑(x,x),(20 SVD操作以得到v和A。 相对于式(8),式(20)的计算要简单得多,它无需重新 (3)式(8)的计算比较复杂。 执行sVD操作以得到讠和,也无需显式计算S=K(D) (4)需要计算出新数据点x到所有训练数据点x以得到k和k。。因为需要计算∑“(x,x),所以 的测地距离d1(x,x)0 第(1)-(2)个问题可以通过另外一种常数平移方通过式(20)计算新数据点x低维表示y的时间复杂度 法悶来解决 为O(n2p) D=D+c(1-n) (10) 第(4)个问题中d(x,x)的计算是必须的,但要准 S=k(62)=-1HDH (11)确逼近它,首先需要根据新数据点的加入对邻城图进行 修正,然后在修正的邻域图上执行最短路径算法(或增 或S=S+SH (12)量最短路径算法),时间复杂度将会很大。 因为此吋的c只需要满足c≥-2λn即可,所以通常 为了提高效率,利用 ISOMAP算法已经计算出来的 就取C=-20可以证明,此时的特征向量和特征值分所有训练数据点之间的测地距离,可以以线性时问复杂 别为: 度近似计算出新数据点到它们的测地距离,如式(21)所 ;=v (13)示,其中,d(x,x)为新数据点x到其邻近数据点x的 (14 欧氏距离,这需要将x正确地加入到邻域图中(即正确 确定x的邻近数据点x),在多流形的情况下首先需要 即λ为λ的线性平移,从而无需对S重新执行SVD操作。准确判定x所在的流形。 对于第(3)个问题,式(8)可以进行如下简化: dv(r, x )=min(d(x.x)+dy(r, x)) (21) 由于 d-(x,x,)=d-(x,x)+c (15) 根据式(21)和式(20)可以快速地近似计算出新数据 点x的低维表示y,从而具有良好的泛化性能。然而,在 kn=Kn+52(- 16)多流形的情况下,l(x,x)的算不同于 ISOMAP算法, d(x,x)的计算首先也需要准确判定x所在的流形 3.1dn(x,x)的计算 ∑2(x,x)+1∑∑(x,x) 为了降低多流形下邻域大小的选取难度,本文并不 “(x,x)-1∑∑a(x,x)(17)苛求能得到严格反映不同流形的邻域图,即将其等同于 单流形,但这样做的后果是在不同流形之间可能存在多 因此有 条连接边,从而产生在各流形之间绕行的最短路径(称 k(x,x)=<a(x),(x)> 之为流形之间的“短路”边),如图1所示 图1中,同一流形上的两个 数据点用五角星表 2(2(x,x)-n2(a(x,x))=它们之间的最短路径用粗实线表示途径∫其他流形。 根据拓扑空间的性质,同一·流形上两个数据点之问的测 (d(x,x)-E-nd(x)=K,)=地线仍然在该流形上:因此在多流形的情况下,为了能 正确逼近相应的测地距离,需要研究不在各流形之问绕 (d,(x, x dy(x x2 ) +f(x) 行的最短路径算法 124 016,52(4) Computer Engineering and4 pplications计算机工程与应用 6420 15-10-505101526y (a)双螺旋数据集 (b)双 Swiss roll数据集 =3.a=0.65 k=8.a=0.65 图1不同数据集上的邻城图 先考虑最简单的情况,假设数据集是由两个不同的 1.0 流形M1和M2组成的,那么各自流形上数据点之间的 最短路径距离直接在相应的子邻域图(完全由同一流形 上的所有数据点组成)上运行传统的最短路径算法即可 得到(和单流形的情况完全相同)。为了避免不合适的 邻域大小会在子邻域图中引入“短路”边的这一问题,本 ).5 文算法采川文献[21]中的方法,根据在最小连通邻域图 -1.0 ( Minimal connected neighborhood(raph)上:得到的成 本(cost)厶有效识別并删除子邻域图中可能出现的“愆 图2三流形数据集的邻域图(k=5) 路"边,这可以在一定程度上降低邻域大小的选取难度 1.0 对于不同流形上的数据点x∈M和x,∈M2,它们之间 的最短路径距离按式(22)进行计算: d1(x,x)=d(x,x+d(x,x)+(x,x)(22) 其中,4(xx)=。min。4(x”,x0),d(x,x”)为分 属不同流形但在邻域图上有边直接相连的数据点x"和 -0.5 x"之间的欧氏距离,d(x2,x,)为其中的最小值,d(x2x 0.51.01.52.02.53.0 和d(x,x)分别为各自流形上相应数据点之间的最短 路径距离。 图3以图2中的各流形作为顶点的最小生成树 当流形的个数大于2时,邻城图上可能会有某些流 dx(x2x1)=d1(x,x)+d(x,x)+d(x2’,x)(23) 形并不直接相连,如图2中的M和M3;另外,为了保持 dr(xp, xp=dr(xp,Xk)+de(xk x,)du(x,',x, )(24) 各流形之间的邻近关系(如图2所示,相对于M3而言, d(r,x, )= min(dm(x,x2)+d(xk, x)) (2 M1和M2更加邻近。这在某些情况下非常有用,例如, 在手写数字识别中,数字1和7容易混淆就是由于它们其中,x∈M1、x∈M2和x∈M3分别为使d(x,x 的流形更加邻近的缘故),本文创建以各流形作为顶点、和d(x,x取最小值的相应流形上的数据点 以邻域图上各流形之间最小欧氏距离即d2(x,x作为 假设数据集共包含c(c≤<n)个流形,邻域图上不同 相应顶点之间距离的最小生成树( Minimal spanning流形之间的连接边平均有m(m<<kn/c)条,那么找出各 Tree, MST,如图3所示,按照最小生成树上各流形之间流形之间最小欧氏距离的时间复杂度为O(cm);以各 的连通路径可逐步计算出不同流形数据点之间的最短 流形作为顶点的最小生成树采用Prim算法得到,其时 路径距离。采用以各流形作为顶点的最小生成树可以 间复杂度为O(c2),都远远小于计算各自流形上数据点 避免最短路径在各流形之问绕行,从而降低多流形下邻 域大小的选取难度。 之间最短路径距离的时间复杂度O∑n2(n)(其中 如图2和图3所示,令x∈M1、∈M2和x:∈M2, 它们之间的最短路径距离按式(23)~(25)逐步计算 n:为第i个流形上的数据点个数,即有∑n1=n)。因此, 邵超,万春红,李洁颖:用于多流形分类的核等距映射算法 2016,52(4)125 该方法计算最短路径距离的时间复杂度和 ISOMAP算操作得到,时间复杂度为O(P2+P)。因此,根据同 法(即O(n21b(m))相当。 流形上邻近局部切空间的相似性来判定新数据点所在 为了在分类多流形时能将不同的流形明显分开,和流形的时间复杂度为O(P2+P)(k+2),在P<<n的情 现有算法一样,本文也将增大不同流形数据点之间的距离:况下相对较小。 d(x,x)=d2(x,x)+A(-8) (26) 在确定了新数据点x所在的流形(假设为M1)之 其中,△为一个正常数,本文取&=里xn((x,x)10,后,根据其邻近数据点(即x0,x2,…,x”),即可按照式 1,x,和x位于同一个流形 (21)以线性时问复杂度(即O(n))近似计算出x到所有 0,其他 训练数据点x的测地距离d(x,x)。 32d(x,x)的计算 3.3算法流程 综上所述,本文算法与2.1介绍的 ISOMAP算法不 根据式(21),d(x,x)的计算需要确定新数据点X同之处在于第2步和第3步: 的邻近数据点x,在多流形的情况下首先需要准确判 (2)按照式(26)对训练数据点之问的欧氏距离进 定x所在的流形。 行调整,然后用k-最近邻法创建邻域图G,并用成本和 在多流形的情况下,传统的单纯依靠距离的判定方以各流形作为顶点的最小生成树分别消除流形内和流 法已不再适用。按照流形的局部k氏特性,同一流形上形之间可能存在的“短路”边。 的邻近数据点具有相似的局部切空间。因此,本文算法 (3)按照3.1介绍的方法,计算任意两个训练数据 根据同一流形上邻近局部切空间的相似性来准确判定点x和x之间的d(nx)。 新数据点所在的流形。 对于新数据点x,本文算法将按照以下两步计算其 由于对邻近局部切空间的相似性度量主要看它们 在方向上的相似性,因此,本文采用夹角余弦来作为邻低维表示y 近局部切空间的相似性度量。 (1)按照3.2节介绍的方法,准确判定x所在的流 对于新数据点x,如果其邻近数据点x"(i=1,2,…,k) 形.确定κ的邻近数据点κ,然后按照式(21)近似计算 都属于同一个流形,那么x也属于这个流形;如果它们 出x到所有训练数据点x的测地距离d(x,x,)。 分属不同的流形,不失一般性,假设x,x2),…,x∈M1 (2)按照式(20)计算x的低维表示y。 (r+11{:+2) x"∈M2,则需要按照以下步骤对x所在 这两步的时间复杂度分别为O(P2+P)(k+2)+m) 和O(n2p),在P<<n的情况下相对较小 的流形进行判定: (1)分别计算邻城{x,x",x"2,…,x}(x及其在流 形M1上的邻近数据点集合)和{x,x1x+204实验结果 为了验证本文算法的有效性,将使用如图4所示的 (x及其在流形M2上的邻近数据点集合)的局部切空间双螺旋数据集和双 Swiss roll数据集(它们的内在维数 r1和2,以及x在流形M上的邻近数据点分别为1和2,都包含2个数据流形,分别记作“*”和“o 0.x),…,x处的局部切空间1,x,…,,x在流未知类别标记的新数据点分别随机采样于这两个数据 形M2上的邻近数据点x),x”,…,x处的局部切流形,分别以大小五角星表示 空问 r12) 本文算法以不同的邻域大小k分别运行在这两个 1)(2 数据集上,运行结果分别如图5和图6所小 (2)计算1和x1,r1 r1之间的平均夹角余弦5 从图5和图6可以看出,本文算法不但能将不同的流 以及2和x2,r2,…,2之间的平均夹角余弦 形正确分开,实现有效的分类,而且还能准确判定新数据 51=1∑1x 点所在的流形,即小五角星表示的新数据点位于“o”数据 =1 流形,大五角星表示的新数据点位于“*数据流形,与图 S2 4完全一致:此外,本文算法计算得到的新数据点的低维 其中,s(x,y)为计算切空间x和y之间夹角余弦的函数 表示也能较好地保持它们与各自邻近数据点之问的局部 欧氏距离(图5中“*”数据流形的全局几何结构在一定程 (3)如果5>52,则x∈M1;否则x∈M2。当推厂到 度上被扭曲了,这是因为CMDS算法对所有距离都一·视 m(m≥2)个流形时,则有:x∈M1,其中,l= arg max s 同仁,从而在一定程度上牺牲了短距离的侏持精度,但大 局部切空间可以通过在相应的邻域(由于限制在同五角星表示的新数据点的低维表示仍然在该流形正确 一个流形上,因此每一个邻域中数据点的个数通常都小的一端,只不过又折了回来)这说明本文算法能很好地 于邻城大小k,假设平均为r个,维数为P)上执行PCA实现新数据点的低维嵌入,从而具有良好的泛化性能 126 016,52(4) Computer Engineering and4 pplications计算机工程与应用 25 8642 )2468 1o-505101526 (a)双螺旋数据集 (b)双 Swiss roll数据集 图4实验中用到的两个2-流形数据集 2.0 1.4 1.2 12 0.6 0.6 0.2 0 20 6 60-40-200 r (b)k=20 图5本文算法在双螺旋数据集上的运行结果 322 505 25 10 (a)k=20 图6本文算法在双 Swiss roll数据集上的运行结果 另外,从图5和图6还可以看出,本文算法对邻域大同文献「21),如图7所示。本文算法仍然以不同的邻域 小并不敏感,在不同的邻域大小下(如双螺旋数据集上的大小k分别运行在该数据集上,运行结果如图8所示。 k=10和k=20,双 Swiss roll教据集上的k=20和k=30) 从图8可以看出,在加入了噪音的双 Swiss rol数 都能很好地实现新数据点的低维嵌入。这是为本文据集上,本文算法采用与图6完全相同的邻域大小仍然 算法不但采用成本来消除由不合适邻域大小所带来的能将不同的流形正确分开,实现有效的分类,还能很好 同一流形內的“短路”边,而且还采用以各流形作为顶点地实现新数据点的低维嵌入:不但能准确判定新数据点 的最小生成树来消除不同流形之间可能形成的“短路”所在的流形,而且还能较好地保持它们与各自邻近数据 边,从而在一定程度上克服了多流形下邻域大小更加难点之间的局部欧氏距离。因此,本文算法对噪音也具有 以有效选取的问题 一定的鲁棒性 众所周知,流形学习算法对噪音比较敏感,在多流 为了验证本文算法对多于2个流形的数据集的分 形的情况下问题会更加严重。为了验证本文算法的鲁类和泛化性能,将使用如图9所示的三 Swiss roll数据 棒性,在双 Swiss roll数据集上加入∫一定的噪音(方法集和加入∫噪音(方法同文献[22])的三 Swiss rol数据 邵超,万春红,李洁颖:用于多流形分类的核等距映射算法 2016,52(4)127 以大、中、小五角星表示)。本文算法仍然以不同的邻域 大小k分别运行在这两个数据集上,运行结果分别如图 0和图11所 从图10和图11可以看出,本文算法在3-流形数据集 上仍然具有良好的分类和泛化性能:不但能准确判定新 数据点所在的流形,而且还能比较正确地得到新数据点 15 在各自流形上的相对位置;对邻域大小和噪音也具有 定的鲁棒性。此外,本文算法还能保持各流形之问的邻 近关系,如图10所示,相对于“∧A¨数据流形而言,“o”数 图7加入了噪音的双 Swiss roll数据集 据流形和“*”数据流形更加邻近(然而,在图11中,“Δ”数 集(这3个数据流形分别记作“△”、“*”和“0”;未知类别据流形和“o”数据流形更加邻近,这是噪音干扰的结果)。 标记的新数据点分别随机采样于这三个数据流形,分别 如上所述,在多流形的情况下单纯依靠欧氏距离如 20 20 40 100-50050100150200 (a)k=20 (b)k=30 图8本文算法在加入了噪音的双 Swiss ro数据集上的运行结果 20 10 言 5 (a)三 Swiss roll数据集 (b)加入了噪音的三 Swiss rol数据集 图9实验中川到的两个3-流形数据集 150 150 100 100 50 100-50050100150200 1500-50050100150200 (a)k=20 (b)k=30 图10本文算法在三 Swiss roll数据集上的运行结果 128 016,52(4) Computer Engineering and Applications计算机工程与应用 80r 0 小、小6 p(2小少。9小少小 (a)k=20 (b)k=30 图11本文算法在加入了噪音的三 Swiss rollz数据集上的运行结果 長Ⅰ不同算法对双螺旋数据集的分类准确率比较 =1 k=5 k=10 κ-最近邻法本文算法k-最近邻法本文算法k-最近邻法本文算法k-最近邻法本文算法 双螺旋数据集 0 0.425 長2不同算法对其他数据集的分类淮确率比较 片=1 k=30 k=40 k-最近邻法本文算法k·最近邻法本文算法k-最近邻法本文算法k-最近邻法本文算法 双 Swiss roll!.据集 0.995 0.895 1.00 0.800 1.U0 0.750 U00 加入了噪音的双 Swiss roll.据集 0.985 0.830 1.000 0.795 0.975 0.770 1.000 三 Swiss roll:数据集 0.865 1.000 0.805 1.000 0.645 0.975 加入了噪音的三 Swiss roll数据集 0.850 0.7 4.925 0).550 0.950 ).630 4.925 k-最近邻法难以对新数据点进行正确分类。为了验证 lity reduction and data representation[J]. Neural Compu 这一点,在上述数据集上分别运行本文算法和k-最近邻 tation,2003,15(6):1373-1396 法,它们对新数据点的分类准确率如表1和表2所示。4 Donoho d l, Grimes C Hessian eigenmaps; locally linear 从表1和表2可以看出,本文算法在这几个多流形数据 embedding techniques for high-dimensional data[J. PNAS 集上都具有更高的分类准确率 2003,100(10):5591-5596 [5 Zhang Z, Zha H Principal Manifolds and Nonlinear Dimension Reduction via Local Tangent Space Alignment[J]SIAM 5结束语 Journal of Scicntific Computing, 2004, 26(1): 313-338 为了提高核 ISOMAP算法在多流形下的分类和泛[6]杨剑,李伏欣,王玕.一种改进的局部切空间排列算法软 化性能,按照流形的局部欧氏特性,本文提岀了一种能 件学报,2005,16(9):1584-1590 够用于多流形分类的核 ISOMAP算法。该算法根据同[]陶剑文,王土同.局部学刁支持向量机[门控制与决策,2012 流形上邻近局部切室闾的相似性能够准确判定新数 27(10):1010-1015 据点所在的流形,并对目前核等距映射算法中新数据点[81雷霖,熊伟,景宁,等,一种基」流形距离的中文语块聚类分 低维表示的计算过程进行了简化,从而具有良好的泛化 析方法叮北京大学学报:自然科学版,2013,49(1):126-132 性能。实验结果证实,该算法具有较高的分类准确率。 [9]王勇基于流形学习的分类与聚类方法及其应用研究[D 长沙:国防科学技术大学,2011 然而,当数据集的观测维度很高时,局部切空间的计算 [10] Wolpert D I, Macready W GCoevolutionary free lunches[J] 代价会很大,这将是今后改进的方向 IEEE Transactions on Evolutionary Computation, 200.5 9(6):721-735 参考文献 [11 Bengio Y, Monperrus M. Non-local manifold tangent [1 Tenenbaum J B, de Silva v, Langford J C a global geo learning[J]. Advances in Neural Information Processing metric frame work for nonlinear dimensionality reduction[J] Systems,2005,17(1):129-136. Science,2000,290(22):2319-2323 [12 Geng X. Zhan D, Zhou Z Supervised nonlinear dimen [2 Roweis S T, Saul L K Nonlinear dimensionality reduction sionality reduction for visualization and classification[J]. by locally linear embedding[J]. Science, 2000, 290(5500 IEEE Transactions on Systems, Man and Cybernetics 2323-2326. 2005,35(6):1098-1107 [3 Belkin M, Niyogi P Laplacian eigenmaps for dimension (下转187页)

...展开详情
试读 8P 论文研究-用于多流形分类的核等距映射算法.pdf
立即下载 身份认证后 购VIP低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
  • 至尊王者

关注 私信
上传资源赚钱or赚积分
最新推荐
论文研究-用于多流形分类的核等距映射算法.pdf 15积分/C币 立即下载
1/8
论文研究-用于多流形分类的核等距映射算法.pdf第1页
论文研究-用于多流形分类的核等距映射算法.pdf第2页

试读结束, 可继续读1页

15积分/C币 立即下载