On using prototype reduction schemes to optimize kernel-based nonlinear subspace methods

The subspace method of pattern recognition is a classification technique in which pattern classes are specified in terms of linear subspaces spanned by their respective class-based basis vectors. To overcome the limitations of the linear methods, kernel-based nonlinear subspace (KNS) methods have been recently proposed in the literature. In KNS, the kernel principal component analysis (kPCA) has been employed to get principal components, not in an input space, but in a high-dimensional space, where the components of the space are nonlinearly related to the input variables. The length of projections onto the basis vectors in the kPCA are computed using a kernel matrix K, whose dimension is equivalent to the number of sample data points. Clearly this is problematic, especially, for large data sets.In this paper, we suggest a computationally superior mechanism to solve the problem. Rather than define the matrix K with the whole data set and compute the principal components, we propose that the data be reduced into a smaller representative subset using a prototype reduction scheme (PRS). Since a PRS has the capability of extracting vectors that satisfactorily represent the global distribution structure, we demonstrate that data points which are ineffective in the classification can be eliminated to obtain a reduced kernel matrix, K, without degrading the performance. Our experimental results demonstrate that the proposed mechanism dramatically reduces the computation time without sacrificing the classification accuracy for samples involving real-life data sets as well as artificial data sets. The results especially demonstrate the computational advantage for large data sets, such as those involved in data mining and text categorization applications.     

On using prototype reduction schemes and classifier fusion strategies to optimize kernel-based nonlinear subspace methods

In kernel-based nonlinear subspace (KNS) methods, the length of the projections onto the principal component directions in the feature space, is computed using a kernel matrix, K, whose dimension is equivalent to the number of sample data points. Clearly this is problematic, especially, for large data sets. In this paper, we solve this problem by subdividing the data into smaller subsets, and utilizing a prototype reduction scheme (PRS) as a preprocessing module, to yield more refined representative prototypes. Thereafter, a classifier fusion strategy (CFS) is invoked as a postprocessing module, to combine the individual KNS classification results to derive a consensus decision. Essentially, the PRS is used to yield computational advantage, and the CFS, in turn, is used to compensate for the decreased efficiency caused by the data set division. Our experimental results demonstrate that the proposed mechanism significantly reduces the prototype extraction time as well as the computation time without sacrificing the classification accuracy. The results especially demonstrate a significant computational advantage for large data sets within a parallel processing philosophy.     

On using prototype reduction schemes to optimize dissimilarity-based classification

The aim of this paper is to present a strategy by which a new philosophy for pattern classification, namely that pertaining to dissimilarity-based classifiers (DBCs), can be efficiently implemented. This methodology, proposed by Duin and his co-authors (see Refs. [Experiments with a featureless approach to pattern recognition, Pattern Recognition Lett. 18 (1997) 1159-1166; Relational discriminant analysis, Pattern Recognition Lett. 20 (1999) 1175-1181; Dissimilarity representations allow for buillding good classifiers, Pattern Recognition Lett. 23 (2002) 943-956; Dissimilarity representations in pattern recognition, Concepts, theory and applications, Ph.D. Thesis, Delft University of Technology, Delft, The Netherlands, 2005; Prototype selection for dissimilarity-based classifiers, Pattern Recognition 39 (2006) 189-208]), is a way of defining classifiers between the classes, and is not based on the feature measurements of the individual patterns, but rather on a suitable dissimilarity measure between them. The advantage of this methodology is that since it does not operate on the class-conditional distributions, the accuracy can exceed the Bayes’ error bound. The problem with this strategy is, however, the need to compute, store and process the inter-pattern dissimilarities for all the training samples, and thus, the accuracy of the classifier designed in the dissimilarity space is dependent on the methods used to achieve this. In this paper, we suggest a novel strategy to enhance the computation for all families of DBCs. Rather than compute, store and process the DBC based on the entire data set, we advocate that the training set be first reduced into a smaller representative subset. Also, rather than determine this subset on the basis of random selection, or clustering, etc., we advocate the use of a prototype reduction scheme (PRS), whose output yields the points to be utilized by the DBC. The rationale for this is explained in the paper. Apart from utilizing PRSs, in the paper we also propose simultaneously employing the Mahalanobis distance as the dissimilarity-measurement criterion to increase the DBCs classification accuracy. Our experimental results demonstrate that the proposed mechanism increases the classification accuracy when compared with the “conventional” approaches for samples involving real-life as well as artificial data sets—even though the resulting dissimilarity criterion is not symmetric.     

On using prototype reduction schemes to optimize locally linear reconstruction methods

This paper concerns the use of prototype reduction schemes (PRS) to optimize the computations involved in typical k-nearest neighbor (k-NN) rules. These rules have been successfully used for decades in statistical pattern recognition (PR) [1], [15] applications and are particularly effective for density estimation, classification, and regression because of the known error bounds that they possess. For a given data point of unknown identity, the k-NN possesses the phenomenon that it combines the information about the samples from a priori target classes (values) of selected neighbors to predict the target class of the tested sample, or to estimate the density function value of the given queried sample. Recently, an implementation of the k-NN, named as the locally linear reconstruction (LLR) [2], has been proposed. The salient and brilliant feature of the latter is that by invoking a quadratic optimization process, it is capable of systematically setting model parameters, such as the number of neighbors (specified by the parameter, k) and the weights. However, the LLR takes more time than other conventional methods when it has to be applied to classification tasks. To overcome this problem, we propose a strategy of using a PRS to efficiently compute the optimization problem. In this paper, we demonstrate, first of all, that by completely discarding the points not included by the PRS, we can obtain a reduced set of sample points, using which, in turn, the quadratic optimization problem can be computed far more expediently. The values of the corresponding indices are comparable to those obtained with the original training set (i.e., the one which considers all the data points) even though the computations required to obtain the prototypes and the corresponding classification accuracies are noticeably less. The proposed method has been tested on artificial and real-life data sets, and the results obtained are very promising, and could have potential in PR applications.     

基于一种改进的类内散布矩阵的核鉴别分析法

基于核的非线性判别方法及算法的研究近年来得到广泛的研究。在这些方法中,一个主要的缺点是对L类判别问题,判别向量最多只有[L-1]个。定义一种改进的核类间散布矩阵,并对两类问题给出改进的核鉴别分析法,该方法克服了以上缺陷。试验结果表明所提出的方法与其他方法相比具有很好的识别性能。     

On using prototype reduction schemes to enhance the computation of volume-based inter-class overlap measures

In most pattern recognition (PR) applications, it is advantageous if the accuracy (or error rate) of the classifier can be evaluated or bounded prior to testing it in a real-life setting. It is also well known that if the two class-conditional distributions have a large overlapping volume (almost all the available work on “overlapping of classes” deals with the case when there are only two classes), the classification accuracy is poor. This is because if we intend to use the classification accuracy as a criterion for evaluating a PR system, the points within the overlapping volume tend to lead to maximal misclassification. Unfortunately, the computation of the indices which quantify the overlapping volume is expensive. In this vein, we propose a strategy of using a prototype reduction scheme (PRS) to approximately, but quickly, compute the latter. In this paper, we demonstrate, first of all, that this is an extremely expedient proposition. Indeed, we show that by completely discarding (we are not aware of any reported scheme which discards “irrelevant” sample (training) points, and which simultaneously attains to an almost-comparable accuracy) the points not included by the PRS, we can obtain a reduced set of sample points, using which, in turn, the measures for the overlapping volume can be computed. The value of the corresponding figures is comparable to those obtained with the original training set (i.e., the one which considers all the data points) even though the computations required to obtain the prototypes and the corresponding measures are significantly less. The proposed method has been rigorously tested on artificial and real-life datasets, and the results obtained are, in our opinion, quite impressive—sometimes faster by two orders of magnitude.     

基于核线性分类分析的三维模型检索算法

为提高检索精确度,提出了一种利用核线性分类分析来对模型特征进行优化的新方法。其主要思想是通过满足Mercer条件的非线性映射将低维空间下线性不可分的样本映射到高维空间,在高维空间中利用线性分类分析将原有的三维模型特征投影到特定的子空间。该方法能够在保持类间距离基础上得到具有鉴别信息的低维特征用于三维模型检索。实验结果表明,核线性分类分析方法速度较快,可在秒级完成三维特征优化,同时优化特征在本文测试数据集上可平均提高搜索准确度15%。     

基于Fisher鉴别分析的支持向量机训练样本缩减策略

提出一种用于支持向量机训练样本集的缩减策略。该策略运用Fisher鉴别分析方法快速地提取潜在的支持向量,并构成用于SVM的新的训练样本集。仿真实验表明,该算法能在保证不降低分类精度的前提下,对较大规模的样本进行有效的缩减,提高运算效率。     

Feature scaling for kernel fisher discriminant analysis using leave-one-out cross validation

Kernel fisher discriminant analysis (KFD) is a successful approach to classification. It is well known that the key challenge in KFD lies in the selection of free parameters such as kernel parameters and regularization parameters. Here we focus on the feature-scaling kernel where each feature individually associates with a scaling factor. A novel algorithm, named FS-KFD, is developed to tune the scaling factors and regularization parameters for the feature-scaling kernel. The proposed algorithm is based on optimizing the smooth leave-one-out error via a gradient-descent method and has been demonstrated to be computationally feasible. FS-KFD is motivated by the following two fundamental facts: the leave-one-out error of KFD can be expressed in closed form and the step function can be approximated by a sigmoid function. Empirical comparisons on artificial and benchmark data sets suggest that FS-KFD improves KFD in terms of classification accuracy.     

A fast kernel-based nonlinear discriminant analysis for multi-class problems

Nonlinear discriminant analysis may be transformed into the form of kernel-based discriminant analysis. Thus, the corresponding discriminant direction can be solved by linear equations. From the view of feature space, the nonlinear discriminant analysis is still a linear method, and it is provable that in feature space the method is equivalent to Fisher discriminant analysis. We consider that one linear combination of parts of training samples, called “significant nodes”, can replace the total training samples to express the corresponding discriminant vector in feature space to some extent. In this paper, an efficient algorithm is proposed to determine “significant nodes” one by one. The principle of determining “significant nodes” is simple and reasonable, and the consequent algorithm can be carried out with acceptable computation cost. Depending on the kernel functions between test samples and all “significant nodes”, classification can be implemented. The proposed method is called fast kernel-based nonlinear method (FKNM). It is noticeable that the number of “significant nodes” may be much smaller than that of the total training samples. As a result, for two-class classification problems, the FKNM will be much more efficient than the naive kernel-based nonlinear method (NKNM). The FKNM can be also applied to multi-class via two approaches: one-against-the-rest and one-against-one. Although there is a view that one-against-one is superior to one-against-the-rest in classification efficiency, it seems that for the FKNM one-against-the-rest is more efficient than one-against-one. Experiments on benchmark and real datasets illustrate that, for two-class and multi-class classifications, the FKNM is effective, feasible and much efficient.     

基于相对Fisher判别分析理论的故障诊断方法

随着现代工业过程的不断发展,自动化设备越来越复杂。系统的安全性与可靠性是设备现代化的重要方面。数据驱动的故障诊断技术是复杂工业生产过程安全性与可靠性的重要保障之一。传统的Fisher判别分析方法:常常忽视了量纲在各过程变量特征提取过程中的影响。本文在回顾传统Fisher判别分析理论的基础上,指出了量纲及量纲标准化过程对判别分析过程产生的影响,并建立了一种相对Fisher判别分析方法:。先通过预处理的方法:消除量纲差异带来的虚假影响,然后根据系统要求对观测数据做相对化变换,从而更有效地获取各观测数据的代表信息及不同运行模式的判断阈值。最后,利用计算机仿真实验验证了本文方法:的有效性。     

Enhancing prototype reduction schemes with LVQ3-type algorithms

Various prototype reduction schemes have been reported in the literature. Foremost among these are the prototypes for nearest neighbor (PNN), the vector quantization (VQ), and the support vector machines (SVM) methods. In this paper, we shall show that these schemes can be enhanced by the introduction of a post-processing phase that is related, but not identical to, the LVQ3 process. Although the post-processing with LVQ3 has been reported for the SOM and the basic VQ methods, in this paper, we shall show that an analogous philosophy can be used in conjunction with the SVM and PNN rules. Our essential modification to LVQ3 first entails a partitioning of the respective training sets into two sets called the Placement set and the Optimizing set, which are instrumental in determining the LVQ3 parameters. Such a partitioning is novel to the literature. Our experimental results demonstrate that the proposed enhancement yields the best reported prototype condensation scheme to-date for both artificial data sets, and for samples involving real-life data sets.     

改进的核费舍判别分析法应用于故障诊断

化工过程采样数据具有强非线性和噪声,针对化工过程状态监控的问题,提出一种改进的核费舍判别分析法（KFDA）的故障诊断算法。首先采样数据经过小波变换方法去除噪声,去除噪声后的数据进行KFDA建模,然后在建模同时采用特征向量选择（FVS）算法降低复杂性。Tennessee Eastman process实验结果表明了该算法的有效性,同时该算法加强了KFDA故障诊断的准确性,并明显地减少了存储空间和运算时间。     

A brief taxonomy and ranking of creative prototype reduction schemes

Various Prototype Reduction Schemes (PRS) have been reported in the literature. Based on their operating characteristics, these schemes fall into two fairly distinct categories — those which are of a creative sort, and those which are essentially selective. The norms for evaluating these methods are typically, the reduction rate and the classification accuracy. It is generally believed that the former class of methods is superior to the latter. In this paper, we report the results of executing various creative PRSs, and attempt to comparatively quantify their capabilities. The paper presents a brief taxonomy of the various reported PRS schemes. Our experimental results for three artificial data sets, and for samples involvingreal-life data sets, demonstrate that no single method is uniformly superior to the others for all kinds of applications. This result, though consistent with the findings of Bezdek and Kuncheva [1], is, in one sense, counter-intuitive, because the various researchers have presented their specific PRS with the hope that it would be superior to the previously reported methods. However, the fact is that while one method is superior in certain domains, it is inferior to another method when dealing with a data set with markedly different characteristics. The conclusion of this study is that the question of determining when one method is superior to another remains open. Indeed, it appears as if the designers of the pattern recognition system will have to choose the appropriate PRS based to the specific characteristics of the data that they are studying. The paper also suggests answers to various hypotheses that relate to the accuracies and reduction rates of families of PRS.     

Unsupervised feature selection based on kernel fisher discriminant analysis and regression learning

In this paper, we propose a new feature selection method called kernel fisher discriminant analysis and regression learning based algorithm for unsupervised feature selection. The existing feature selection methods are based on either manifold learning or discriminative techniques, each of which has some shortcomings. Although some studies show the advantages of two-steps method benefiting from both manifold learning and discriminative techniques, a joint formulation has been shown to be more efficient. To do so, we construct a global discriminant objective term of a clustering framework based on the kernel method. We add another term of regression learning into the objective function, which can impose the optimization to select a low-dimensional representation of the original dataset. We use L_2,1-norm of the features to impose a sparse structure upon features, which can result in more discriminative features. We propose an algorithm to solve the optimization problem introduced in this paper. We further discuss convergence, parameter sensitivity, computational complexity, as well as the clustering and classification accuracy of the proposed algorithm. In order to demonstrate the effectiveness of the proposed algorithm, we perform a set of experiments with different available datasets. The results obtained by the proposed algorithm are compared against the state-of-the-art algorithms. These results show that our method outperforms the existing state-of-the-art methods in many cases on different datasets, but the improved performance comes with the cost of increased time complexity.

     

Kernel machine-based one-parameter regularized fisher discriminant method for face recognition.

This paper addresses two problems in linear discriminant analysis (LDA) of face recognition. The first one is the problem of recognition of human faces under pose and illumination variations. It is well known that the distribution of face images with different pose, illumination, and face expression is complex and nonlinear. The traditional linear methods, such as LDA, will not give a satisfactory performance. The second problem is the small sample size (S3) problem. This problem occurs when the number of training samples is smaller than the dimensionality of feature vector. In turn, the within-class scatter matrix will become singular. To overcome these limitations, this paper proposes a new kernel machine-based one-parameter regularized Fisher discriminant (K1PRFD) technique. K1PRFD is developed based on our previously developed one-parameter regularized discriminant analysis method and the well-known kernel approach. Therefore, K1PRFD consists of two parameters, namely the regularization parameter and kernel parameter. This paper further proposes a new method to determine the optimal kernel parameter in RBF kernel and regularized parameter in within-class scatter matrix simultaneously based on the conjugate gradient method. Three databases, namely FERET, Yale Group B, and CMU PIE, are selected for evaluation. The results are encouraging. Comparing with the existing LDA-based methods, the proposed method gives superior results.     

Multi-period portfolio selection using kernel-based control policy with dimensionality reduction

This paper studies a nonlinear control policy for multi-period investment. The nonlinear strategy we implement is categorized as a kernel method, but solving large-scale instances of the resulting optimization problem in a direct manner is computationally intractable in the literature. In order to overcome this difficulty, we employ a dimensionality reduction technique which is often used in principal component analysis. Numerical experiments show that our strategy works not only to reduce the computation time, but also to improve out-of-sample investment performance.     

基于FDA-KDE间歇过程在线监控

针对基于传统的多向主元分析(Multiway Principal Component Analysis,MPCA)方法用于间歇过程在线监控时需要对新批次未反应完的数据进行预估,从而易导致误诊断,且统计量控制限的确定是以主元得分呈正态分布为假设前提的缺陷,结合Fisher判别分析(Fisher Discriminant Analysis,FDA)在数据分类及非参数统计方法核密度估计(Kernel Density Estimation,KDE)在计算概率密度函数方面的优势,提出了一种FDA-KDE的间歇过程监控方法。该方法首先利用FDA求取正常工况数据和故障数据的Fisher特征向量和判别向量,获得Fisher特征向量的相似度:然后在提出偏平均集成平方误差(Biased Mean Integrated Squared Error,BMISE)交叉验证法确定KDE的带宽从而获得相似度统计量控制限的基础上,利用已获得的数据测量值对过程进行监控,避免了基于MPCA方法对未来测量值的预估;最后采用基于Fisher判别向量权重的贡献图方法来进行故障诊断。通过对青霉素发酵间歇过程应用表明,所提出的方法比传统的MPCA方法能更及时地监测出过程异常情况,更准确地判断异常发生的原因。     

Audio-visual speaker diarization using fisher linear semi-discriminant analysis

Speaker diarization aims to automatically answer the question “who spoke when” given a speech signal. In this work, we have focused on applying the FLsD approach, a semi-supervised version of Fisher Linear Discriminant analysis, both in the audio and the video signals to form a complete multimodal speaker diarization system. Extensive experiments have proven that the FLsD method boosts the performance of the face diarization task (i.e. the task of discovering faces over time given only the visual signal). In addition, we have proven through experimentation that applying the FLsD method for discriminating between faces is also independent of the initial feature space and remains relatively unaffected as the number of faces increases. Finally, a fusion method is proposed that leads to performance improvement in comparison to the best individual modality, which is the audio signal.     

因子分析判别准则的线性降维方法研究

提取稳定且具有判别性的低维特征是模式识别研究中的关键问题。在深入研究Fisher判别准则的基础上,从因子分析的实际角度考虑,提出基于因子分析的判别准则,解决Fisher判别准则类内和类间散布矩阵非最优定义问题。通过在合成数据集和真实人脸数据集上进行实验比较表明,该方法在解决数据集中的边缘类和人脸的表情、姿态变化等问题上比Fisher判别准则更优。