Isomap算法及其在脑电产生源分类中的应用
|
摘要
目前人类社会日益深入到信息时代,在进行科学研究的过程中,不可避免地会遇到大量的高维数据。降维是处理高维数据的一种有效手段,它的目的是找出隐藏在高维数据中的低维结构。降维算法大致可分为线性和非线性两类,PCA和Isomap分别为这两类算法的代表算法。主成分分析法(PCA)是一种常用的线性降维算法,它实现简单,可以确保发现处于高维向量空间的线性子空间上的数据集的真实几何结构,但是该算法的线性本质使其无法揭示复杂的非线性流形;Isomap算法是具有代表性的一种非线性降维算法,它是一种全局优化算法,该算法建立在经典多维尺度算法CDMS基础之上,试图保持数据间内在的几何特性,即保持数据点之间的测地线距离。本文就这两种算法进行了研究分析,重点放在对Isomap算法的研究讨论及其应用。
本文工作主要包括:
1)在降维理论的基础上,对线性降维算法主成分分析法(PCA)、非线性降维算法Isomap及其改进算法S-Isomap进行了研究和分析。同时,分别对PCA算法和Isomap算法、Isomap算法和S-Isomap算法进行了应用实例分析。
2)研究分类算法中的代表算法——支持向量机。分别从SVM的原理、数学模型及其构造几个方面对SVM进行了研究。
3)将Isomap算法与支持向量机相结合,进行脑电产生源分类的仿真实验。在仿真过程中,主要检测Isomap算法的降维能力、容噪性能和对分类仿真结果的影响等,并对仿真结果进行分析。
Scientists are working with large volumes of high-dimensional data in informational era. Dimensionality reduction is an important technique, finding meaningful low-dimensional structures hidden in their high-dimensional observations.
The algorithms of dimensionality reduction can be classified into two categories: linear and nonlinear dimensionality reduction method. PCA, a linear dimensionality reduction method, is simple to implement, and guaranteed to discover the true structure of data lying on or near a linear subspace of the high-dimensional input space. But this algorithm cannot solve nonlinear problem.
As a representational algorithm of nonlinear dimensionality reduction methods, Isomap is a global optimal algorithm. It builds on CDMS but seeks to preserve the intrinsic geometry of data, as captured in the geodesic manifold distances between all pairs of data points. In this paper we research the two method, and importantly study and discuss Isomap and its application .
The main work of this paper include:
1) On the basis of dimensionality reduction theory, we research and analyze the linear dimensionality reduction technique such as Principal Component Analysis (PCA), and nonlinear dimensionality reduction methods, such as Isometric Mapping (Isomap) and S-Isomap . Then, we respectively analyze the instance of PCA and Isomap,Isomap and S-Isomap.
2) We importantly study Support Vector Machine method, including the principle, the mathematical model and structure of SVM.
3) We do the emulation experiment of EEG generation source by combing Isomap and SVM. In our experimentation, the main work is to test the dimensionality reduction ability of Isomap, the tolerant capability to noise, and the infection to the result, and to analyze the result of the emulation experiment.
本文工作主要包括:
1)在降维理论的基础上,对线性降维算法主成分分析法(PCA)、非线性降维算法Isomap及其改进算法S-Isomap进行了研究和分析。同时,分别对PCA算法和Isomap算法、Isomap算法和S-Isomap算法进行了应用实例分析。
2)研究分类算法中的代表算法——支持向量机。分别从SVM的原理、数学模型及其构造几个方面对SVM进行了研究。
3)将Isomap算法与支持向量机相结合,进行脑电产生源分类的仿真实验。在仿真过程中,主要检测Isomap算法的降维能力、容噪性能和对分类仿真结果的影响等,并对仿真结果进行分析。
Scientists are working with large volumes of high-dimensional data in informational era. Dimensionality reduction is an important technique, finding meaningful low-dimensional structures hidden in their high-dimensional observations.
The algorithms of dimensionality reduction can be classified into two categories: linear and nonlinear dimensionality reduction method. PCA, a linear dimensionality reduction method, is simple to implement, and guaranteed to discover the true structure of data lying on or near a linear subspace of the high-dimensional input space. But this algorithm cannot solve nonlinear problem.
As a representational algorithm of nonlinear dimensionality reduction methods, Isomap is a global optimal algorithm. It builds on CDMS but seeks to preserve the intrinsic geometry of data, as captured in the geodesic manifold distances between all pairs of data points. In this paper we research the two method, and importantly study and discuss Isomap and its application .
The main work of this paper include:
1) On the basis of dimensionality reduction theory, we research and analyze the linear dimensionality reduction technique such as Principal Component Analysis (PCA), and nonlinear dimensionality reduction methods, such as Isometric Mapping (Isomap) and S-Isomap . Then, we respectively analyze the instance of PCA and Isomap,Isomap and S-Isomap.
2) We importantly study Support Vector Machine method, including the principle, the mathematical model and structure of SVM.
3) We do the emulation experiment of EEG generation source by combing Isomap and SVM. In our experimentation, the main work is to test the dimensionality reduction ability of Isomap, the tolerant capability to noise, and the infection to the result, and to analyze the result of the emulation experiment.
引文
[1] 杨质敏.高维数据的降维方法研究及其应用.长沙大学学报,2003 年 6 月第 17 卷第 2 期:58-61.
[2] 刘卓.高维数据分析中的降维方法研究:[硕士学位论文].长沙:国防科学技术大学,2002.
[3] 谭璐.高维数据的降维理论及应用:[博士学位论文].长沙:国防科学技术大学,2005.
[4] David L Donoho. High-dimensional Data Analysis: The Curses and Blessings of Dimensionality. International Conference of Mathematicians, Paris, Aug, 2000:25-68.
[5] D W Scott and J R Thompson. Probability density estimation in higher dimensions. In J E Gentle, editor, Computer Science and Statitics: Proceedings of the Fifteenth Symposium on the Interface, pages:173-179.
[6] Camastra F. Data Dimensionality Estimation Methods: A survey. Pattern Recognition, 2003,36:2945-2954.
[7] Liu XW, Srivastavab A, Wang DL.Intrinsic Generalization Analysis of Low Dimensional Representations. Neural Networks, 2003,16: 537-545.
[8] Camastra F, Vinciarelli A. Estimating the intrinsic dimension of data with a fractal-based method. IEEE Trans. on Pattern Analysis, 2002,24(10):1404-1407.
[9] 赵 连 伟 , 罗 四 维 , 赵艳敞 等 . 高维 数 据流形 的 低维 嵌 入 及本 征 维 数 研究 . 软 件 学报,2005,16(8):1423-1430.
[10] 徐蓉,姜峰,姚鸿勋.流形学习概述.智能系统学报.第 1 卷第 1 期,2006 年 3 月:44-51.
[11] 周志华,曹存根.神经网络及其应用.北京:清华大学出版社,2004:205-250.
[12] Tenenbaum JB, Silva V de, Langford JC. A Global Geometric Framework for Nonlinear Dimensionality Reduction. Science, 2000, 290(22): 2319-2323.
[13] Roweis ST, Saul LK. Nonlinear Dimensionality Reduction by Locally Linear Embedding. Science, 2000, 290(22): 2323-2326.
[14] 邹凌,朱善安,张迎春.源于脑电偶极子源定位问题.国外医学生物医学工程分册.2003 年第 26 卷第3期:103-108.
[15] 刘晓春,彭仕政,谈荣日.脑电磁场及脑内源定位的研究进展.现代生物医学进展.2006,Vol.6, No.6: 9-12.
[16] 田源.脑波偶极子源定位的研究:[硕士学位论文].广州:第一军医大学,2002.
[17] 张迎春,邹凌.脑电正问题的模型和算法.生物医学工程学杂志.2004,21(2): 337-339.
[18] Jolliffe IT. Principal Component Analysis. New York: Springer-Verlag, 1986:1-40.
[19] 王玲玲,周纪芗.常用统计方法.上海:华东师范大学出版社,1998:289-297.
[20] 余从津.非线性维数约减的研究及其应用:[硕士学位论文].天津:天津大学,2004.
[21] 翁时锋,张长水,张学工.非线性降维在高维医学数据处理中的应用.清华大学学报(自然科学版),2004,44(4):485-488.
[22] Borg I, Groenen P. Modern Multidimensional Scaling: Theory and Application. New York, Berlin, Heidelberg: Springer-Verlag, 1997:78-150.
[23] M. Balasubramanian, E. L. Schwartz, J. B. Tenenbaum. The Isomap algorithm and topological stability. Science, 2002, 295(4): 7a.
[24] Tobias Friedrich.Nonlinear Dimensionality Reduction with Locally Linear Embedding and Isomap.This Dissertation is a part requirement for the MSc in advanced Computer Science.2002, 9.
[25] Shifeng Weng, Changshui Zhang, Zhonglin Lin. Exploring the structure of supervised data by Discriminant Isometric Mapping. Pattern Recognition, 2005,38(4): 599-601.
[26] 何力,张军平,周志华.基于放大因子和延伸方向研究流形学习算法.计算机学报,2005,28(12): 2000-2009.
[27] M.Vlachos, C.Domeniconi, D.Gunopulos, G.Kollios, and N.Koudas. Non-linear dimensionality reduction techniques for classification and visualization. In Proceeding of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Edmonton, Canada, pp.645-651, 2002.
[28] Xin Geng, De-Chuan Zhan, and Zhi-Hua Zhou, Member IEEE. Supervised Nonlinear Dimensionality Reduction for Visualization and Classification.IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS-PART B: CYBERNETICS, VOL. 35, NO.6, DECEMBER 2005.
[29] 边肇琪,张学工.模式识别.北京:清华大学出版社,2000,第二版:1-10.
[30] 杨光正,吴岷,张晓莉.模式识别.合肥:中国科学技术大学出版社,2001,第一版:1-6.
[31] 杨铁建.基于支持向量机的数据挖掘技术研究:[硕士学位论文].西安:西安电子科技大学,2005.
[32] Jiswei Han, Micheline Kamber 著,范明,孟小峰译.数据挖掘概念与技术[M].北京:机械工业出版社,2001,8:75-116.
[33] 赵晖,荣莉莉,李晓.一种设计层次支持向量机多类分类器的新方法.计算机应用研究,2006年第6期:34-37.
[34] Vapnik V.统计学习理论的本质[M].张学工.北京:清华大学出版社,2000:50-65.Vapnik V. The Nature of Statistical Learning Theory [M]. Hang Xuegong .Beijing: Tshinghua University Press,2000.(in Chinese).
[35] 杜晓东,李岐强.支持向量机及其算法研究.信号处理与模式识别.2005 年第 3 期:37-40.
[36] 常军民.基于多特征分类器融合决策的印鉴识别:[硕士学位论文].浙江工业大学,2005.
[37] 唐发明,王仲东,陈锦云.支持向量机多分类算法研究.控制与决策.第 20 卷第 7 期,2005 年 7月:746-754.
[38] Mingui Sun. An Efficient Algorithm for Computing Multishell Spherical Volume Conductor Models in EEG Dipole Source Localization. IEEE Transactions On Biomedical Engineering, VOL. 44, NO. 12, December 1997:1243-1252.
[39] Mingui Sun, Ching-Chung Li, Robert J.Sclabassi. A Hierarchiacl Decision Module Based On Multiple Neural Networks, 1997:238-241.
[40] http://isomap.stanford.edu.
[41] 张智星.ATLAB 程序设计与应用.北京:清华大学出版社,2002:1-9.
[42] 张航,黄攀.精通 MATLAB6.北京:清华大学出版社,2002:1-6.
[43] Kaibo Duan, S Sathiya Keerthi, Aun Neow Poo. An empirical evaluation of simple performancemeasure for tuning SVM hyperparameters. Technical Report CD-O1-11, Control Division, Dept.of Mechanical Engineering, National University of Singapore, 2001.
[2] 刘卓.高维数据分析中的降维方法研究:[硕士学位论文].长沙:国防科学技术大学,2002.
[3] 谭璐.高维数据的降维理论及应用:[博士学位论文].长沙:国防科学技术大学,2005.
[4] David L Donoho. High-dimensional Data Analysis: The Curses and Blessings of Dimensionality. International Conference of Mathematicians, Paris, Aug, 2000:25-68.
[5] D W Scott and J R Thompson. Probability density estimation in higher dimensions. In J E Gentle, editor, Computer Science and Statitics: Proceedings of the Fifteenth Symposium on the Interface, pages:173-179.
[6] Camastra F. Data Dimensionality Estimation Methods: A survey. Pattern Recognition, 2003,36:2945-2954.
[7] Liu XW, Srivastavab A, Wang DL.Intrinsic Generalization Analysis of Low Dimensional Representations. Neural Networks, 2003,16: 537-545.
[8] Camastra F, Vinciarelli A. Estimating the intrinsic dimension of data with a fractal-based method. IEEE Trans. on Pattern Analysis, 2002,24(10):1404-1407.
[9] 赵 连 伟 , 罗 四 维 , 赵艳敞 等 . 高维 数 据流形 的 低维 嵌 入 及本 征 维 数 研究 . 软 件 学报,2005,16(8):1423-1430.
[10] 徐蓉,姜峰,姚鸿勋.流形学习概述.智能系统学报.第 1 卷第 1 期,2006 年 3 月:44-51.
[11] 周志华,曹存根.神经网络及其应用.北京:清华大学出版社,2004:205-250.
[12] Tenenbaum JB, Silva V de, Langford JC. A Global Geometric Framework for Nonlinear Dimensionality Reduction. Science, 2000, 290(22): 2319-2323.
[13] Roweis ST, Saul LK. Nonlinear Dimensionality Reduction by Locally Linear Embedding. Science, 2000, 290(22): 2323-2326.
[14] 邹凌,朱善安,张迎春.源于脑电偶极子源定位问题.国外医学生物医学工程分册.2003 年第 26 卷第3期:103-108.
[15] 刘晓春,彭仕政,谈荣日.脑电磁场及脑内源定位的研究进展.现代生物医学进展.2006,Vol.6, No.6: 9-12.
[16] 田源.脑波偶极子源定位的研究:[硕士学位论文].广州:第一军医大学,2002.
[17] 张迎春,邹凌.脑电正问题的模型和算法.生物医学工程学杂志.2004,21(2): 337-339.
[18] Jolliffe IT. Principal Component Analysis. New York: Springer-Verlag, 1986:1-40.
[19] 王玲玲,周纪芗.常用统计方法.上海:华东师范大学出版社,1998:289-297.
[20] 余从津.非线性维数约减的研究及其应用:[硕士学位论文].天津:天津大学,2004.
[21] 翁时锋,张长水,张学工.非线性降维在高维医学数据处理中的应用.清华大学学报(自然科学版),2004,44(4):485-488.
[22] Borg I, Groenen P. Modern Multidimensional Scaling: Theory and Application. New York, Berlin, Heidelberg: Springer-Verlag, 1997:78-150.
[23] M. Balasubramanian, E. L. Schwartz, J. B. Tenenbaum. The Isomap algorithm and topological stability. Science, 2002, 295(4): 7a.
[24] Tobias Friedrich.Nonlinear Dimensionality Reduction with Locally Linear Embedding and Isomap.This Dissertation is a part requirement for the MSc in advanced Computer Science.2002, 9.
[25] Shifeng Weng, Changshui Zhang, Zhonglin Lin. Exploring the structure of supervised data by Discriminant Isometric Mapping. Pattern Recognition, 2005,38(4): 599-601.
[26] 何力,张军平,周志华.基于放大因子和延伸方向研究流形学习算法.计算机学报,2005,28(12): 2000-2009.
[27] M.Vlachos, C.Domeniconi, D.Gunopulos, G.Kollios, and N.Koudas. Non-linear dimensionality reduction techniques for classification and visualization. In Proceeding of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Edmonton, Canada, pp.645-651, 2002.
[28] Xin Geng, De-Chuan Zhan, and Zhi-Hua Zhou, Member IEEE. Supervised Nonlinear Dimensionality Reduction for Visualization and Classification.IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS-PART B: CYBERNETICS, VOL. 35, NO.6, DECEMBER 2005.
[29] 边肇琪,张学工.模式识别.北京:清华大学出版社,2000,第二版:1-10.
[30] 杨光正,吴岷,张晓莉.模式识别.合肥:中国科学技术大学出版社,2001,第一版:1-6.
[31] 杨铁建.基于支持向量机的数据挖掘技术研究:[硕士学位论文].西安:西安电子科技大学,2005.
[32] Jiswei Han, Micheline Kamber 著,范明,孟小峰译.数据挖掘概念与技术[M].北京:机械工业出版社,2001,8:75-116.
[33] 赵晖,荣莉莉,李晓.一种设计层次支持向量机多类分类器的新方法.计算机应用研究,2006年第6期:34-37.
[34] Vapnik V.统计学习理论的本质[M].张学工.北京:清华大学出版社,2000:50-65.Vapnik V. The Nature of Statistical Learning Theory [M]. Hang Xuegong .Beijing: Tshinghua University Press,2000.(in Chinese).
[35] 杜晓东,李岐强.支持向量机及其算法研究.信号处理与模式识别.2005 年第 3 期:37-40.
[36] 常军民.基于多特征分类器融合决策的印鉴识别:[硕士学位论文].浙江工业大学,2005.
[37] 唐发明,王仲东,陈锦云.支持向量机多分类算法研究.控制与决策.第 20 卷第 7 期,2005 年 7月:746-754.
[38] Mingui Sun. An Efficient Algorithm for Computing Multishell Spherical Volume Conductor Models in EEG Dipole Source Localization. IEEE Transactions On Biomedical Engineering, VOL. 44, NO. 12, December 1997:1243-1252.
[39] Mingui Sun, Ching-Chung Li, Robert J.Sclabassi. A Hierarchiacl Decision Module Based On Multiple Neural Networks, 1997:238-241.
[40] http://isomap.stanford.edu.
[41] 张智星.ATLAB 程序设计与应用.北京:清华大学出版社,2002:1-9.
[42] 张航,黄攀.精通 MATLAB6.北京:清华大学出版社,2002:1-6.
[43] Kaibo Duan, S Sathiya Keerthi, Aun Neow Poo. An empirical evaluation of simple performancemeasure for tuning SVM hyperparameters. Technical Report CD-O1-11, Control Division, Dept.of Mechanical Engineering, National University of Singapore, 2001.