论文研究-ISOMAP算法参数的递增式选取.pdf

所需积分/C币:10 2019-09-08 07:34:51 996KB .PDF
10
收藏 收藏
举报

ISOMAP算法能否被成功应用依赖于其唯一参数——邻域大小的选取是否合适,然而,如何高效地选取一个合适的邻域大小目前还是一个难题。当邻域大小变得不合适时,短路边将会出现在邻域图中,从而严重破坏与之相关的最短路径距离对测地距离的逼近能力。和非短路边不同,短路边的两个端点虽然在欧氏空间中相距较近,但在流形上却相距甚远。基于短路边的这一特点,采用序来近似度量一条边的两个端点在流形上的远近程度,因而能够递增式地对邻域大小进行合适的选取。和基于残差的参数选取方法不同,该方法只需递增式地运行广度优先搜索算法,而无需就每一个可能的邻域大小分别运行整个ISOMAP算法,从而具有比较高的运行效率。最终的实验结果
邵超: ISOMAP算法参数的递增式选取 2008,44(21)121 (i=1,2,…,n)。在k成为最大的合适邻域大小之前,也就是说, 从图4可以看岀,在最大序值第一次陡然增加之前,最大 在(k+1)-阶邻域图依旧没有包含任何短路边之前,所有序都将序值随邻域大小的增加都呈单调减小的趋势,这意味着递增式 保持在很小的水平。另外,随着k的增加,数据的无序性会越来地对邻域大小进行选取是可行的;而第一次陡然增加的那个最 越小,k-阶邻域图会越来越稠密,越来越逼近丁数据的内在流大序值对应的就是我们所要选取的邻域大小,在 swiss rol数 形结构;显然,作为正常的非短路边,所有数据点的第k+1条边据集中为k=8,在加入了噪音的 swiss rol数据集中为k=6,I 也都将越来越贴近于此前的k-阶邻域图,其结果是最大序值 SOMAP算法的运行结果分别如图5(a)和图5(c)所示。为了进 nax(Oa)将会单调减小,即有max(O)≥max(Oakn)≥ 步说明选取的邻城大小是最大的合适邻域大小,将相应的邻 l≤i≤n max(Oa)。而当最大序值max(Ok)第一次陡然增加时,即有域大小分别加1,得到的运行结果分别如图5(b)和图5(d所示。 20 max(Oa)≥max(Okm)≥…≥max(Oak)<max(Oa),这 10副的∴… 意味着存在某个数据点它的第k+1条边将作为第一条短路边55: 出现在(k+1)-阶邻域图中,此时的k就是所要选取的合适的邻 二”营 景垂小 年#, 域大小,更确切地说应该是最大的合适邻域大小 该参数选取方法的时间复杂度相对较小因为该方法无需:…灬2 运行比较耗时的最短路径算法和古典MDs算法( SOMAP算1560102002040-2502010"10200 法的第3步和第4步)即可选取一个合适的邻域大小,它只需 (a)k=8, swiss roll数据集 (b)k=9, swiss rol数据集 递增式地计算所有数据点的序,而计算所有数据点的序只需运15 行n次广度优先搜索算法即可,其时间复杂度仅为O(n2) 03呢………? 的以 4实验结果 在这一章,将使用以下两个数据集来对该参数选取方法进 “:“ -20 行验证: 锻 (1)具有2000个随机样本点的 swiss rol数据集叫。为降低60-40-200204060-40-30-20-10010203040 计算量,在 ISOMAP算法的第1步,采用 Matlab v65工具箱中的 (ch=6,加入了噪音的 (d)h=7,加入了噪音的 k-均值算法从中选取了n=500个代表点,如图3(a)所示。 swiss roll数据集 swiss roll数据集 (2)加入了噪音的 swiss roll a数据集s。该数据集是在如上 图5 ISOMAP算法的运行结果 所述的 swiss roll a数据集的每一个数据点上都加入了一服从正 态分布的噪音,该正态分布的期望为0,标准差为各维跨度最 此外,通过计算相应的残差(如图6所示),同样可以证明 小值的2%。为降低计算量,采用同样的方法从中选取了n=500 用该参数选取方法选取出来的这些邻域大小都是合适的,而且 个代表点,如图3(b)所示。 还都是最大的合适邻域大小。 0.40 0.35 0.3 0.30 》知 0.30 0.25 0.25 0.20 袋0.20}--1-T 0.1 0.10 0.1 认 0.05 15J 05 10-50 0 246810121416182022246810121416182022 (a) swiss roll数据集 (b)加入了噪音的 swiss roll数据集 图3实验中用到的两个数据集 ( aiswiss roll 3数据集 (b)加入了噪音的 swiss roll数据集 图6不同数据集上的残差随邻域大小的变化情况 为验证该参数选取方法的可行性,就每一个可能的邻域大 小k∈[km,km(km是预先设定的一个最大可能k值,将其设 从图4~图6还可以看出,噪音对邻域大小的合适与否影 定为km=km+20,事实上,该参数在递增式的参数选取方法中响很大,这也是造成 ISOMAP算法拓扑不稳定的重要原因。本 是不必要的)分别计算了所有数据点的序,其最大值随邻域大文提出的参数选取方法在有噪音的情况下依然能够选取合适 小的变化情况如图4所示。 的邻域大小(如图4(b)所示),这说明该参数选取方法具有一 20 定的鲁棒性。 18-|- -+1-十-↑ l 5结论 众所周知, ISOMAP算法能否被成功应用依赖于其唯一参 数——邻域大小的选取是否合适,然而,如何高效地选取一个 合适的邻域大小目前还是一个难题。目前大多数的参数选取方 24681012141618202224681012141618202 法都基丁残差,因而都非常耗时。 (a) swiss roll数据集 (b)加入了噪音的 swiss roll数据集 和非短路边相比,短路边的两个端点在流形上相距明显要 图4不同数据集的最大序值随邻域大小的变化情况 远得多,本文用序对此进行近似度量,从而能够递增式地对邻 1222008,44(21) Computer Engineering and Applications计算机工程与应用 域大小进行合适的选取。和基于残差的参数选取方法不同,该 New York, NY, USA: John Wiley Sons Inc, 2000 方法只需递増式地运行广度优先搜索算法,而无需就每一个可[10 I Kohonen TSelf- organized formation of topologically correct fea- 能的邻域大小分别运行整个 ISOMAP算法,从而具有比较高的 ture maps[J]. Biological Cybernetics, 1982, 43(1): 59-69 运行效率。在实验中也发现,该参数选取方法具有一定的鲁棒性。[1 1 Tenenbaum I E, de silva v, Langford I O. a global geometric framework for nonlinear dimensionality reduction[J]. Science, 2000 参考文献 290(5500):2319-2323 [1] Cleveland W SVisualizing Data[M].Summit, NJ, USA: Hobart Press [12 Roweis S T, Saul L KNonlinear dimensionality reduction by lo cally linear embedding[J).Science, 2000, 290(5500): 2323-2326 [2] Keim D A Designing pixel-oriented visualization techniques: Theory [13] Belkin M, Niyogi P Laplacian eigenmaps for dimensionali and applications[J. IEEE Transactions on Visualization and Com- tion and data representation [J]. Neural Computation, 2003, 15(6) Graphics,2000,6(1):59-78 1373-1396 puter [3] Inselberg A, Dimsdale B Parallel coordinates: a tool for visualizing [14] Donoho D L, Grimes C Hessian eigenmaps: locally linear embed multi-dimensional geometry[C] /Proceedings of IEEE Conference on ding techniques for high dimensional data[ C]/Proceedings of the Visualization90. San Francisco, CA. USA. 1990: 361-378 National Academy of Scicnccs, 2003, 100(10): 5591-5596 [4 Kandogan E Visualizing multi-dimensional clusters, trends, and [15] Balasubramanian M, Shwartz E L, Tenenbaum J B, et al. The i outliers using star coordinates[C]Proceedings of the seventh ACM somap algorithm and topological stability [J].Science, 2002, 295 SIGKDD InlernaliOnal Conlerence on Kilowledye Discovery and Data Mining, San Francisco, CA, USA, August 2001: 107-116 [16] Kouropteva 0, Okun O, Pietikainen M Selection of the optimal [5 LeBlanc J, Ward M O, Wittels N Exploring n-dimensional databas parameter value for locally linear embedding algorithm[Cp/pro- es[C/proceedings of IEEE Conference on Visualization 90, San ceedings of the Ist International Conference on Fuzzy Systems Francisco, CA, USA, October 1990: 230-237 and Knowledge Discovery, Singapore, 2002: 359-363 16 Shneiderman BTree visualization with treemaps: a 2d space-filling 17] Saxena A, Gupta A, Mukerjee A Non-linear dimensionality reduc- approach[J].ACM Transactions on Graphics, 1992, 11(1): 92-99 tion by locally linear isomaps [C //Proceedings of the 1lth In- [7 Chernoff H. The use of faces to represent points in k-dimensional ternational Conference on Neural Information Processing, Calcutta space graphically[J]Journal of the American Statistical As India,2004:1038-1043 ociation, 1973,68(342):36-368. [18] Bernstein M, de Silva V, Langford J C, et al. Graph approximations [8] PickelL R M, Grinslein GGIconographic displays for visualizing to geodesics on embedded manifolds[R] .Technical Report, Depart multidimensional data[ C]//Proceedings of the 1988 IEEE Confer ment of psychology, Stanford University, 2000 ence on Systems, Man and Cybernetics, Beijing and Shenyang, [19] Lee J A, Lendasse A, Verleysen MNonlinear projection with China. august 1998: 514-519 curvilinear distances: isomap versus curvilinear distance analysis[J] 9] Duda R O, Hart P E, Stork D G Pattern classification [M].2nd ed Neurocomputing, 2004, 57(1): 49-76 (上接118页) 较为规则的文本知识的形式处理方法,今后将深入研究一般性 L(k1)×L(k2)的映射φ::φ(lA1×A2,F(B1×B2))=(A1,B1l,A2,文本知识的概念格挖掘以及分析。 B)是一个∧-维持的序嵌入。 证明由命题10以及定义4和定义5容易证明。 参考文献: [1 Wille R Formal concept analysis as mathematical theory of con 4总结和进一步的问题 cepts and concept hierarchies[ Cy/Ganter B LNAI 3626: Formal Con 本文主要是把概念格理论引入文本知识挖掘领域,用于描 cept Analysis, 2005 1-33 述较为规则的文本知识的数据挖掘。为更简洁地从文本知识中[2] Lei yuxia, Wang Yan, Cao baoxiang,etal. Concept interconnection 抽取概念格,适当修改了 Galois联通,从而避免了在概念换算 based on many-valued context analysis[C]/Zhou Z H, Li H, Yang 中概念格结构因使用属性标尺不同可能差别很大的问题。由于 QLNAI 4426: PAKDD 2007, Nanjing China, 2007: 623-630 创建了一些概念本体,所以基本上可以自动地把描述规则的文3 KiI M, Coplon P Formal concept analysis for domain= specific 本知识翻译为多值上下文。例如基于人物概念本体(战役本体) document retrieval systems(C /Brooks M, Corbett D, Stumptner M 就可以自动地从描述人物(著名战役)的文本知识中抽取出多 LNAI2256:2001:237-248 值上下文。本文假设已经把文本知识转化为多值上下文,然后 [4] Lei Y, Cao C, Sui Y Acquiring military knowledge from texts in 分析了两类情况:一是当在一个多值上下文中增加/删除一些 the electronic encyclopedia of China [C/cYCs 2001, Hangzhou 对象或属性时,即当多值上下文动态变化时概念的变化情况 China,2001,1:367-371 二是多值上下文乘积的概念与因子上下文的概念间的关联 [5 Hahn U, Schnattinger K Knowledge mining from textual sources[C/ Proceedings of the Sixth International Conference on Information 本文得到一些重要命题,这些命题可用来判定执行一些操 and Knowledge Management, 1997: 83-90 作后哪些概念保持不变以及概念格之间的结构关联。本文主要 [6 Mooney R J, Bunescu R Mining knowledge from text using infor- 从理论上分析了多值上下文的一些操作对概念以及概念格结 mation extraction[Jl.SIGKDD Explorations, 2005, 7(1): 3-10 构的影响。实践证明,概念格理论更适合处理较规则的文本知71 Pechsiri C, Kawtrakul A Mining causality for explanation knowledge 识。依据一定的原则,增加一些对象或一些属性并不会改变原 rom text[J)-Journal of Computer Science and Technology, 2007, 22 有的概念。反过来,依据一定的策略,也可由多值上下文中的概 (6):877-889 念确定子多值上下文的概念。另外,多值上下文乘积的概念格8] Ganter B, Wille e. Formal concept analysis: mathematical founda 可嵌入到两个因子概念格的乘积中。目前本文分析的只是描述 tions(M]-[SI]: Springer, 1999

...展开详情
试读 4P 论文研究-ISOMAP算法参数的递增式选取.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
关注 私信
上传资源赚钱or赚积分
最新推荐
论文研究-ISOMAP算法参数的递增式选取.pdf 10积分/C币 立即下载
1/4
论文研究-ISOMAP算法参数的递增式选取.pdf第1页

试读结束, 可继续读1页

10积分/C币 立即下载