摘要
模式识别是一门以应用为基础的学科,模式识别研究的理论和方法在很多方面得到了成功的应用,所有这些应用都是和问题的性质密不可分的,至今还没有发展成统一有效的可应用于所有问题的模式识别方法。由于大量实际的模式识别问题是具有多类别的高维复杂模式的识别,因此研究复杂模式的分析和分类方法是必要而且有意义的。
基于核函数的学习方法(简称为核方法)是从统计学习理论中发展出来的较新的学习方法,它有效克服了传统模式识别方法的局部极小化和不完全统计分析的缺点。核方法本质上是非线性的信息处理工具,它在处理具有非线性关系的高维复杂模式识别问题时,有着其它学习方法无法比拟的优越性。核方法的研究和应用目前正方兴未艾,新的算法不断地被提出,但是作为一种尚未成熟的技术,仍然存在着许多不完善和有待解决的问题,如核函数的构造和选择、多类分类等问题,因此研究基于核方法的复杂模式识别理论具有重要的意义。
本论文研究的内容主要侧重于如何用核方法实现高维多模式对象的特征提取和模式分类,论文所作的工作包括以下几部分内容:
1.针对奇异情况下如何更好地解决核Fisher描述分析中非线性最优鉴别矢量集的求解问题,提出了改进的核直接描述分析(IKDDA)方法。根据再生核理论,定义核类内散度矩阵和核类间散度矩阵,将高维特征空间中的Fisher描述准则函数转化为核Fisher描述准则函数。基于同构映射原理和奇异值分解定理,在一个更小的空间内将核Fisher描述准则函数的极大值问题转化为其倒数的极小值问题,使最终的解不需要分开考虑核类内散度矩阵的零空间和非零空间。在ORL和UMIST人脸库上的实验结果表明了IKDDA方法与其他方法相比具有较低的误识率和较快的运行速度。
2.针对高维、小样本模式识别中的特征提取问题,提出了一种约束线性描述分析方法(CLDA)。以线性变换后样本的类内距离与类间距离之比最小作为准则函数,同时加上约束条件使变换后的样本中心沿着特定的正交方向,通过白化变换、Gram-Schimdt正交化和正交子空间投影求解约束准则函数得到最优变换矩阵。针对人脸识别的小样本问题,根据奇异值分解定理实现白化变换。运用核技巧,将CLDA推广到非线性的约束核描述分析(CKDA),给出了原理与算法过程。对ORL和UMIST人脸库进行了仿真研究,结果表明CLDA方法和CKDA方法的有效性。
3.针对如何有效地设计决策树支持向量机(SVM)多类分类器的层次结构这个关键问题,提出了一种基于向量投影的类间可分性测度的设计方法,并给出了基于该类间可分性测度设计决策树SVM多类分类器层次结构的偏二叉树方法和完全二叉树方法。为了加快每个SVM子分类器的训练速度且保持其高推广性,将改进的基于向量投影的支持向量预选取方法用于每个子分类器的训练中。对不同类型的数据的仿真实验,结果表明新方法有效地提高了决策树SVM多分类器的分类精度和速度。
4.提出了改进的基于投影和三角不等式的k近邻搜索法以及改进的基于向量投影的边界向量预选取方法。针对样本总体分布已知的分类问题,提出了一种新的分类方法。通过非线性映射将训练样本映射到高维特征空间,基于向量投影法从训练样本中选择边界向量,运用k近邻搜索法确定每个边界向量同类中的k近邻,运用统计理论中的大数定理估计样本的类条件概率密度函数,由边界向量与相应的密度函数构成新的训练样本对。对每一类建立一个径向基函数(RBF)网络,以相应类的边界向量作为中心,通过训练,最终以RBF网络来估计样本的类条件概率密度。在此基础上,基于最小错误率的贝叶斯决策实现分类。对机器学习数据的仿真研究结果表明该方法能快速有效地实现多类分类。
Pattern recognition is an application oriented subject, its theories and methods have been successfully applied in many areas, and all these applications are consanguineous with the property of idiographic problem. Up to present, no method can be applied to all problems. It is necessary and significative to study pattern recognition method for problems with complex patterns owing to the fact that most practical problems comprise high dimension and complex multi-class patterns.
Kernel-based learning method is a new tool developed from statistic learning theory, it has effectively overcome the problems of local minima and overfitting. Kernel-based learning method is essentially a nonlinear information processing tool, and has been proven more effective than other learning methods on the pattern recognition of high dimension complex problem with nonlinear pattern. The research and application of Kernel-based learning method is just in the ascendant and many new algorithms are continually proposed. But as an immature technology, it still has to cope with many problems in the structure, function, classification and so on. Generally speaking, the research in complex pattern recognition based on Kernel learning method is of great significance.
The main content of this paper contains kernel-based extraction and pattern classification methods. The main contributions are as following:
1. In order to find a better method to compute the optimal discrimination vectors for the kernel-based Fisher discrimination analysis in the singular cases, In this paper, an improved kernel direct Fisher discrimination analysis (IKDDA) is proposed. Based on the theory of reproducing kernel, the kernel within-class and kernel between-class scatter matrices are defined, the Fisher discrimination criterion in the high feature space is transformed to kernel Fisher discrimination criterion. Based on the theory of isomorphic mapping and singular value decomposition theorem, the maximum of the kernel Fisher discrimination criterion can be skillfully acquired by solving the minimum of its reciprocal in a small space, and the final solution is acquired without taking account of the null space and non-null space of the kernel within-class scatter matrices separately. Experiment results on the ORL and the UMIST face image database indicate that the proposed methodology is able to achieve lower error rate and quicker speed compared with other methods.
2. A constrained linear discrimination analysis (CLDA) method is proposed for the feature extraction in the pattern recognition of problems with high dimension and small samples. Applying whitening process and Gram-Schimdt orthogonalization and orthogonal subspace projection, an optimal transformation matrix is designed to minimize the ratio of intra-class distance to inter-class distance while imposing the constraint that different class centers after transformation are along specifically directions that are orthogonal each other. For the small sample problem of face recognition, the whitening process is realized by singular value decomposition. Using kernel tricks, the CLDA is generalized to constrained kernel discrimination analysis (CKDA). Experimental results on face images show that both CLDA and CKDA are effective and feasible.
3. Designing the hierarchical structure is a key issue for the decision-tree-based (DTB) support vector machines multi-class classification. Inter-class separability is an important basis for designing the hierarchical structure. A new method based on vector projection is proposed to measure inter-class separability. Furthermore, two different DTB support vector multi-class classifiers are designed based on the inter-class separability: one is in the structure of DTB-balanced branches and another is in the structure of DTB-one against all. Experiment results on three large-scale data sets indicate that the proposed method speeds up the decision-tree-based support vector machines multi-class classifiers and yields higher precision.
4. An improved k-nearest-neighbor search method based on projection and triangular inequality is presented, some inequalities are used to delete impossible data points and reduce distance computations. An improved method based on vector projection is proposed to address the problem of pre-extracting boundary vectors. A novel data classification method was prompted for the classification problem about samples with known distribution. A nonlinear function was chosen to map the input to a higher-dimensional space, vectors near the boundaries were pre-extracted from the training samples. By the law of large numbers in statistics, the value of the class-conditional probability density function of each boundary vector was estimated by k-nearest-neighbor estimation method. The learning algorithm constructed a radial basis function network with the boundary vectors as the network centers to approximate the class-conditional probability density function of each class of the objects in the training data set. The classification was conformed by the minimum error rate Bayesian decision rule. The experiment on machine learning data sets proved that the proposed algorithm can quickly and effectively carry out data classification with more than two classes of objects.
引文
[1]边肇棋,张学工.模式识别[M].北京:清华大学出版社,2000.
[2]严红平,潘春宏,模式识别简介[J].自动化博览,2006,(2):23-26.
[3]孙即祥.现代模式识别[M].长沙:国防科技大学出版社,2002.
[4]Picard R,Affective Computing,MIT press,1997.2.
[5]Devijver P A and Kittler J,Pattern Recognition,a Statistical Approach,Prentice Hall,Englewood Cliffs,London,1982.
[6]Friedman M and Kandel A,Introduction to Pattern Recognition,statistical,structural,neural and fuzzy logic approaches,World Scientific,Signapore,1999.
[7]Fukunaga K,Introduction to Statistical Pattern Recognition(Second Edition),
[8]Jain A K,Duin R P W,Jianchang Maol Statistical pattern recognition:a review,IEEE Transactions on Pattern Analysis and Machine Intelligence,2000,22(1):4-37.
[9]K S Fu,Syntactic Methods in Pattern Recognation.New York:Academic Press,1974.
[10]K S Fu,Syntatic Methods in Pattern Recognation:Application.New York:Springer-Verlag,1977.
[11]A Zadeh,Fuzzy Sets.Information and Control,1965(8):338-353.
[12]高新波.模糊聚类分析及其应用[M].西安:西安电子科技大学出版社,2004.
[13]Rosenblatt F,Principles of Neurodynamics:Perceptrons and the theory of brain mechanisms,Spartan Books,Washington,D.C.,1962
[14]MERCER J,Functions of positive and negative type and their connection with the theory of integral equations.Phi los.Trans.Roy.Soc.London,A 209:415-446,1909.
[15]Watanabe S,Pattern Recognition:Human and Mechanical,Wiley,New York,1985.
[16]Aizerman,M A,Braverman,E.M.,Rozono6r,L.I.Theoretical foundation of the potential function method in pattern recognition learning.Automation and Remote Control,25:81-837,1964.
[17]Vapnic V N,The Nature of statistical learning theory[M].New York:Springer-Verlag,1995.
[18]SCHOLKOFP B,SMOLA A,MULLER K R.Nonlinear component analysis as a kernel eigenvalue problem[J].Neural computation,1998,10(5):1299-1319.
[19]SCHOLKOFP B,M1KA S,BURGE J C et al.Input Space Versus Feature Space in Kernel-based Methods[J].IEEE Trans on Neural Networks,1999,10(5):1000-1017.
[20]MIKA S,RATSCH G WESTON J,et al.Fisher discriminant analysis with kernels[A].Proceedings of IEEE International workshop on Neural Networks for Signal Processing[C].Madison,Wisconsin,August,1999,41-48.
[21]YANG Ming-Hsuan.Kernel eigenfaces vx.Kernel Fisherfaces:face recognition using kernel methods[A].Proceedings of the Fifth IEEE International Conference on Aautomatic Face and Gesture Recognition(RGR'02)[C].Washington D.C.2002,215-220.
[22]GAUDAT G AND ANOUAR F.Generalized discriminate analysis using a kernel approach[J].Neural computation,2000,12(10):2385-2404.
[23]LU Juwei,PLATANIOTIS K N,VENETSANOPOULOS A N.Face recognition using kernel direct discriminant analysis algorithms[J].IEEE Transactions on Neural Networks,2003.14(1):117-126.
[24]高秀敏,杨静宇,杨健.一种最优的核Fisher鉴别分析与人脸识别[J].系统仿真学报,2004,16(12):2864-2868.
[25]ZHANG P,PENG J,DOMENICONI C.Kemel Pooled Local Subspaces for Classification[J].IEEE Transactions on Systems,Man and Cybernetics,2005,35(3):489-502.
[26]FENG G,HU D,ZHANG D,ZHOU Z.An alternative formulation of kernel LPP with Appllication to Image Recognition[J].Neurocomputing,2006,69(13-15):1733-1738.
[27]BEN-HUR A,HORN D et al.Support Vector Clustering[J].Machines Learning Research,2001,2:125-137.
[28]SAKETHA NATH J,SHEVADE S K.An Efficient Clustering Scheme Using Support Vector Mathods[J].Pattern Recognition,2006,39:1473-1480.
[29]LEE D,LEE J.Domain Described Support Vector Classifier for Multi-classification Problems[J].Pattern Recognition,2007,40:41-51.
[30]PRIETO R,JIANG J,CHOI C H.A New Spectral Algorithm for Large Training Sets[C].Proceedmgs of the Second International Conference on Machine Learning and Cybernetics,Xi'an,2-5 November 2003,147-153.
[31]WANG C J,LI W J,DING L et al,Image Segmentation Using Spectral Cluster[C].Proceedings of the 17th IEEE International Conference on Tools with Artificial Intelligence(ICTAI'05),2005.
[32]JOHN S T,NELLO C.Kernel methods for pattern analysis[M].China machine press,2005.
[33]柳回春,马树元,吴平东.UK心理测试自动分析系统的手写体数字识别.北京理工大学学报,2002,22(5):599-603
[34]高学,金连文,尹俊勋等.一种基于支持向量机的手写汉字识别方法,电子学报,2002,30(5):651-654
[35]张燕昆,杜平,刘重庆.基于主元分析与支持向量机的人脸识别方法.上海交通大学学报,2002,36(6):884-886
[36]马勇,丁晓青.基于层次型支持向量机的人脸检测.清华大学学报(自然科),2003,43(1):35-38
[37]ZIEN A,RATSCH G C,MIKA S et al.Engineering Support Vector Machine Kernels that Recognize Translation Initiation Sites in DNA[J].Bioinformatics,2000,16:799-807.
[38]陈光英,张千里,李星.基于SVM分类机的入侵检测系统.通信学报,2002,23(5):51-56
[39]刘学军,陈松灿,彭宏京.基于支持向量机的计算机键盘用户身份验真.计算机研究与发展,2002,39(9):1082-1086
[40]JOACHIMS T.Text Categorization with Support Vector Machines:Learning with Many Relevant Features[C].Proceeding of 10~(th) Eruopean Conference on Machine Learning,Berlin,Germany:Springer-Verlag,1998:137-142.
[41]李晓黎,刘继敏,史忠植.基于支持向量机与无监督聚类相结合的中文网页分类器.计算机学报,2001,24(1):62-68
[42]张浩然,韩正之.基于支持向量机的非线性模型预测控制.系统工程与电子技术,2003,25(3):330-334
[43]王华忠,俞金寿.基于支持向量机的故障诊断方法研究.华东理工大学学报(自然科学版),2004,30(21:179-182
[44]尉询楷,李应红.支持向量机在航空发动机故障诊断中的应用[J].航空动力学报,2004,19(6):844-848.
[45]王定成,方延健,唐毅等.支持向量回归理论与控制的综述.模式识别与人工智能,2003, 16(2):192-197
[46]孔锐,张冰.基于核Fisher判决分析的高性能多类分类算法[J].计算机应用,2005,25(6):1327-1329。
[47]AMRI,WU S.Improving Support Vector Machine Classifier by Modifying Kernel Function[J].Nerural Networks,1999,12:783-789.
[48]孔锐,施泽生,郭立等.利用组合核函数提高核主分量分析的性能[J].中国图象图形学报,2004,9(1):40-45。
[49]AYAT N E,CHERIET M,SUEN C Y.Automatic Model Selection for the Optimization of SVM Kernels[[J].Pattern Recognition,2005,38:1733-1745.
[50]Zhang D Q,CHEN SC,ZHOU Z H.Learning the Kernel Parameters in Kernel Minimum Distance Classifier[J].Pattern Recognition,2006,39:133-135.
[51]CORTES C,VAPNIK V N.Support Vector Networks[J].Machine Learning,1995,20:273-297.
[52]OSUNA E,FREUND R,GIROSI F.An Improved Training Algorithm for Support Vector Machines[C].J Principle,L Gile,N Morgan eds.Proceedings of 1997 IEEE Workshop on Nerual Networks Dignal Processing Ⅶ,Cambridge,MA:MIT Press,1997:276-285.
[53]JOACHIMES T.Making Large-scale SVM Learning Practical[C].Advances in Kernel Methods-Support Vector Learning.Cambridge,MA:MIT Press,1999:169-184.
[54]Platt J C.Fast Training of Support Vector Machines using Sequential Minimal Optimization[DB/OL].[1998-10-22].http://research.microsoft.com/～jplatt.
[55]焦李成,张莉,周伟达.支撑向量预选取的中心距离比值法[J].电子学报,2001,29(3):383-386.
[56]李青,焦李成,周伟达.基于向量投影的支撑向量预选取[J].计算机学报,2005,28(2):145-152.
[57]汪西莉,焦李成.一种基于马氏距离的支持向量快速提取算法[J].西安电子科技大学学报(自然科学版),2004,31(4):639-643.
[58]Weston J,Watkins C.Multi-class Support Vector Machines,Royal Holloway University of London,Technical report,CSD-TR-98-04,May 20,1998.
[59]Bottou L,Cortes C,Denker J.Comparison of Classifier Methods:a Case Study in Handwriting Digit Recognition[A].Proceedings of the 12~(th) IAPR International Conference on Pattern Reconiton[C].Jerusalem:IEEE,1994:77-82.
[60]Kebel U.Pairwise Classification and Support Vector Machines[A].Advaces in Kernel Methods-Support Vector Learning[C].Cambridge,MA:MIT Press,1999,255-258.
[61]Platt J,Cristianini N,Shawe-Taylor J.Large Margin DAG's for Multiclass Classification[A].Advances in Neural Information processing systems 12[C].Cambridge,MA:Press,2000:547-553.
[62]Sahbi Hichem,Geman Donald,Perona Pietro.A Hierarchy of Support Vector Machines for Pattern Detection[J].Journal of Machine Learning Research,2006,7(10):2087-2123.
[63]Hsu C W,Lin C J.A Comparison of Methods for Multi-class Support Vector Machines[J].IEEE Transaction on Neural Network,2002,13(2):415-425.
[64]唐发明,王仲东,陈绵云.支持向量机多类分类算法研究[J].控制与决策,2005,20(7):746-754.
[65]Wang X D,Shi Z W,Wu C M and Wang W.An Improved Algorithm for Deision-Tree-Based SVM[A].Proceedings of the 6~(th) world congress on intelligent control and automation,June 21-23,2006,Dalian.China.4234-4237.
[66]赵晖,荣莉莉,李晓.一种设计层次支持向量机多分类器的新方法[J].计算机应用研究, 2006,6:34-37.
[67]张莉,核方法和支持向量机,西安电子科技大学博士论文,2001.
[68]BELHUMEUR P N,HESPANHA J P,KRIEGMAN D J.Eigenfaces vs.Fisherfaces[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1997,19(7):711-720.
[69]Chen Li-fen,Liao H-Y Mark,Ko M-T,et al.A new LDA-based face recognition system which can solve the small sample size problem[J].Pattern Recognition,2000,33(10):1713-1726.
[70]HUA Yu and YANG Jie.A direct LDA algorithm forhigh-dimensional data with application to face recognition[J].Pattern Recognition,2001,34(11):2067-2070.
[71]LU Juwei,PLATANIOTIS K N,VENETSANOPOULOS A N.Regurarization studies of linear discriminant analysis in small sample size scenarios with application to face recognition[J].Pattern Recognition Letters,2005,26(2):181-191.
[72]杨健,杨静宇,叶晖.Fisher线性鉴别分析的理论研究及其应用[J].自动化学报,2003,29(4):481-493.
[73]陈伏生,张生亮,高秀敏,杨靖宇.小样本情况下Fisher鉴别分析的理论及验证[J].中国图象图形学报,2005,10(8):984-991.
[74]YAELA,YAEL M,and SHIMON U,Face Recognition:The Problem of Compensating for Changes in Illumination Direction,IEEE Trans.on Pattern Analysis and Machine Intelligence.1997,19:721-731.
[75]程云鹏.矩阵论[M].西安:西北工业大学出版社,1989.
[76]张贤达.矩阵分析与应用[M].北京:清华大学出版社,2004.
[77]SOLTNIAN-ZADEH H,WINDHAM P,PECK D J.Optimal linear transformation for MRI feature extraction[J].IEEE Trans.Med.Imaging,1996,15(6):749-767.
[78]杜树新,吴铁军.模式识别中的支持向量机方法[J].浙江大学学报:工学版,2003,37(5):520-527.
[79]OSUNA E,FREUND R,GIRROSI F.Improved training algorithm for support vector machines[C]//PRO IEEE NNSP'97.New Jersey:IEEE,1997.
[80]安金龙,王正欧,马振平.一种新的支持向量机多分类方法[J].信息与控制,2004,33(3):261-267.
[81]OYANG Y J,HWANG S C,OU Y Y,et al.Data classification with radial basis function networks based on a novel kernel density estimation algorithm[J].IEEE Transaction on Neural networks,2005,16(1):225-236.
[82]孙健,申瑞民,韩鹏.一种新颖的径向基(RBF)网络学习算法[J].计算机学报,2003,26(11):1562-1567.
[83]RAPHAEL R,FABRICE O.A methodology to explain neural network classification[J].Neural Networks,2002,(15):237-246.
[84]RICHARD O D,PETER E H,DAVID G S.Pattern classification[M].Beijing:China Machine Press,2003.
[85]刘丁西.矩阵分析[M].武汉:武汉大学出版社,2003:226-256.
[86]AURENHAMMERF,Voronoi Diagrams-A Survey of a Fundamental Geometric Data Structure,ACM Computing Surveys,1991,23(3):345-405.
[87]NENE A A.NAYAR S K.A Simple Algorithm for Nearest Neighbor Search in High Dimensions.IEEE Trans PAMI.1997,19(9):989-1003.
[88]BENTLEY J L.Multidimensional binary search trees used for associative searching[J]. Commun.Ass.Comput.Mach.,1975,18(9):509-517.
[89]FREDMAN J H,BENTLEY J L and FINKEL R A,An algorithm for finding best matches in logarithmic expected time[J].ACM Trans.Math.Software,1977,3(3):209-226.
[90]CHAVEZ E,et al.Searching in Metric Spaces,ACM Compuing Surveys,2001,3(3):273-321
[91]KIM B S,PARK S B.A Fast k nearest neighboring finding algorithm based on the ordered partitioin,IEEE Trans.PAMI,1986,8(6):761-766.
[92]MICO L,ONC1NA J,CARRASCO R C,A fast branch & bound nearest neighbor classifier in metric spaces,Pattern Recognition Letter,1996,(17):731-739.
[93]MCNAMES J,A fast nearest-neighbor algorithm based on a principal axis search tree,IEEE Trans.PAM1,2001,23(9):964-976.
[94]BEI C D,GRAY R M,An improvement of the minimum distortion encoding algorithm for vector quantization,IEEE Trans.Commun.,1985,33(10):1132-1133.
[95]CHEN S H,PAN J S,Fast searching algorithm for VQ based recognition of isolated words[J].IEE Proc.I(Commun.Speech Vision),1989,136(6):391-396.
[96]RAMASUBRAMANIAN V,KULDIP K K,Fast k-dimensional tree algorithms for nearest neighbor search with application to vector quantization encoding[J].IEEE Trans.Signal Processing,1992,40(3):518-531.
[97]RA S W,KIM J K,Fast mean-distance-ordered partial codebook search algorithm for image vector quantization[J].IEEE Trans.Circuits System Ⅱ:Analog Digital Signal Process,1993,40(9):576-579.
[98]BAEK S J,JEON B K,SUNG K M,A fast encoding algorithm for vector quantization[J].IEEE Signal Process.Lett.,1997,4912):325-327.
[99]TAI S C,LAI C C,LIN Y C,Two fast nearest neighbor searching algorithms for image vector quantization[J].IEEE Trans.Commun.,1996,44(12):1623-1628.
[100]LAI J Z C,LUE C C,Fast search algorithm for VQ codebook generation[J].J.Visual Commun.Image Represent,1996,7(2):163-168.
[101]LAI J Z C,LIAW Y C,Fast searching algorithm for vector quantization using projection and triangular inequality[J].IEEE Trans.Image Process,2004,13(2):1554-1558.
[102]JOHN GP,DIMITRIS G M,数字信号处理[M].北京:电子工业出版社,2007.
[103]LAI J Z C,LIAW Y C,LIU J L,Fast k-nearest-neighbor search based on projection and triangular inequality[J].Pattern Recognition,2007,(40):351-359.
[104]MICHIE D,SPIEGELHALTER D,TAYLOR C.Machine learning,neural and statistical classification[DB/OL].[1994].http://www.niadd.liacc.up.pt/old/statlog/datasets,html.
[105]高林,宋枫溪,杨靖宇,正交化Fisher鉴别向量集及应用[J].数据采集与处理,2006,21(1):16-21.