一种基于预分类的高效最近邻分类器算法

本文的最近邻分类器算法是采用多分类器组合的方式对测试样本进行预分类,并根据预分类结果重新生成新的训练和测试样本集。对新的测试样本采用最近邻分类器进行分类识别,并将识别结果与预分类结果结合在一起进行正确率测试。在ORL人脸库上的实验结果说明,该算法对小样本数据的识别具有明显优势。     

基于异构分类器集成的增量学习算法

将集成学习的思想引入到增量学习之中可以显著提升学习效果,近年关于集成式增量学习的研究大多采用加权投票的方式将多个同质分类器进行结合,并没有很好地解决增量学习中的稳定-可塑性难题。针对此提出了一种异构分类器集成增量学习算法。该算法在训练过程中,为使模型更具稳定性,用新数据训练多个基分类器加入到异构的集成模型之中,同时采用局部敏感哈希表保存数据梗概以备待测样本近邻的查找;为了适应不断变化的数据,还会用新获得的数据更新集成模型中基分类器的投票权重;对待测样本进行类别预测时,以局部敏感哈希表中与待测样本相似的数据作为桥梁,计算基分类器针对该待测样本的动态权重,结合多个基分类器的投票权重和动态权重判定待测样本所属类别。通过对比实验,证明了该增量算法有比较高的稳定性和泛化能力。     

A new k-harmonic nearest neighbor classifier based on the multi-local means

The k-nearest neighbor (KNN) rule is a classical and yet very effective nonparametric technique in pattern classification, but its classification performance severely relies on the outliers. The local mean-based k-nearest neighbor classifier (LMKNN) was firstly introduced to achieve robustness against outliers by computing the local mean vector of k nearest neighbors for each class. However, its performances suffer from the choice of the single value of k for each class and the uniform value of k for different classes. In this paper, we propose a new KNN-based classifier, called multi-local means-based k-harmonic nearest neighbor (MLM-KHNN) rule. In our method, the k nearest neighbors in each class are first found, and then used to compute k different local mean vectors, which are employed to compute their harmonic mean distance to the query sample. Finally, MLM-KHNN proceeds in classifying the query sample to the class with the minimum harmonic mean distance. The experimental results, based on twenty real-world datasets from UCI and KEEL repository, demonstrated that the proposed MLM-KHNN classifier achieves lower classification error rate and is less sensitive to the parameter k, when compared to nine related competitive KNN-based classifiers, especially in small training sample size situations.     

Performance evaluation of pattern classifiers for handwritten character recognition

This paper describes a performance evaluation study in which some efficient classifiers are tested in handwritten digit recognition. The evaluated classifiers include a statistical classifier (modified quadratic discriminant function, MQDF), three neural classifiers, and an LVQ (learning vector quantization) classifier. They are efficient in that high accuracies can be achieved at moderate memory space and computation cost. The performance is measured in terms of classification accuracy, sensitivity to training sample size, ambiguity rejection, and outlier resistance. The outlier resistance of neural classifiers is enhanced by training with synthesized outlier data. The classifiers are tested on a large data set extracted from NIST SD19. As results, the test accuracies of the evaluated classifiers are comparable to or higher than those of the nearest neighbor (1-NN) rule and regularized discriminant analysis (RDA). It is shown that neural classifiers are more susceptible to small sample size than MQDF, although they yield higher accuracies on large sample size. As a neural classifier, the polynomial classifier (PC) gives the highest accuracy and performs best in ambiguity rejection. On the other hand, MQDF is superior in outlier rejection even though it is not trained with outlier data. The results indicate that pattern classifiers have complementary advantages and they should be appropriately combined to achieve higher performance. Received: July 18, 2001 / Accepted: September 28, 2001     

The nearest subclass classifier: a compromise between the nearest mean and nearest neighbor classifier

We present the Nearest Subclass Classifier (NSC), which is a classification algorithm that unifies the flexibility of the nearest neighbor classifier with the robustness of the nearest mean classifier. The algorithm is based on the Maximum Variance Cluster algorithm and, as such, it belongs to the class of prototype-based classifiers. The variance constraint parameter of the cluster algorithm serves to regularize the classifier, that is, to prevent overfitting. With a low variance constraint value, the classifier turns into the nearest neighbor classifier and, with a high variance parameter, it becomes the nearest mean classifier with the respective properties. In other words, the number of prototypes ranges from the whole training set to only one per class. In the experiments, we compared the NSC with regard to its performance and data set compression ratio to several other prototype-based methods. On several data sets, the NSC performed similarly to the k-nearest neighbor classifier, which is a well-established classifier in many domains. Also concerning storage requirements and classification speed, the NSC has favorable properties, so it gives a good compromise between classification performance and efficiency.     

Nearest neighbor classification from multiple feature subsets

Combining multiple classifiers is an effective technique for improving accuracy. There are many general combining algorithms, such as Bagging, Boosting, or Error Correcting Output Coding, that significantly improve classifiers like decision trees, rule learners, or neural networks. Unfortunately, these combining methods do not improve the nearest neighbor classifier. In this paper, we present MFS, a combining algorithm designed to improve the accuracy of the nearest neighbor (NN) classifier. MFS combines multiple NN classifiers each using only a random subset of features. The experimental results are encouraging: On 25 datasets from the UCI repository, MFS significantly outperformed several standard NN variants and was competitive with boosted decision trees. In additional experiments, we show that MFS is robust to irrelevant features, and is able to reduce both bias and variance components of error.     

基于组合分类器的相关反馈算法研究

基于内容的矢量图形检索系统可以通过使用相关反馈算法获得较好的检索性能。提出了一种新的基于组合分类器的相关反馈算法,该算法以每一个正负反馈样本作为唯一的训练样本,形成各个独立的最近邻分类器,融合各个分类器的预估结果,计算库中每个图形的相关分数,并引入贝叶斯查询点移动技术来优化相关分数。实验结果表明,该算法在进一步提高矢量图形检索系统查准率的同时,还能保证系统的查全率。     

独立分量分析在模式识别中的应用

模式识别中关键的两个环节是模式的特征提取及利用分类器分类识别。采用独立分量分析进行特征提取 ,并比较了最近邻分类器和cos分类器的分类识别性能。利用ORL人脸图像数据库进行实验 ,结果表明独立分量分析与cos分类器相结合可得到更好的识别结果。     

Adaptive Graph Embedding Discriminant Projections

Graph embedding based learning method plays an increasingly significant role on dimensionality reduction (DR). However, the selection to neighbor parameters of graph is intractable. In this paper, we present a novel DR method called adaptive graph embedding discriminant projections (AGEDP). Compared with most existing DR methods based on graph embedding, such as marginal Fisher analysis which usually predefines the intraclass and interclass neighbor parameters, AGEDP applies all the homogeneous samples for constructing the intrinsic graph, and simultaneously selects heterogeneous samples within the neighborhood generated by the farthest homogeneous sample for constructing the penalty graph. Therefore, AGEDP not only greatly enhances the intraclass compactness and interclass separability, but also adaptively performs neighbor parameter selection which considers the fact that local manifold structure of each sample is generally different. Experiments on AR and COIL-20 datasets demonstrate the effectiveness of the proposed method for face recognition and object categorization, and especially under the interference of occlusion, noise and poses, it is superior to other graph embedding based methods with three different classifiers: nearest neighbor classifier, sparse representation classifier and linear regression classifier.     

负样本信息继承的矩阵式瀑布分类器高效学习算法

针对矩阵式瀑布分类器学习算法在负样本自举过程中无法快速自举出训练所需的高质量样本,自举过程严重影响整体学习效率及最终检测器性能等问题,提出了一种高效学习算法——负样本信息继承的矩阵式瀑布分类器高效学习算法。其自举负样本过程为样本继承与层次自举相结合,首先从训练上一层强分类器所用的负样本集中继承有效负样本,样本集不足部分再从负图像集中自举。样本继承压缩了有效样本的自举范围,可以快速自举出训练所需样本;并且自举负样时对样本进行预筛选,增加了样本复杂度,提升了最终分类器性能。实验结果表明:训练完成方面,本算法比矩阵式瀑布分类器算法节省20h;检测性能方面,比矩阵式瀑布型分类器高出1个百分点;与其他17种人体检测算法性能相比也有很好的性能表现。所提算法较矩阵式瀑布分类器学习算法在训练效率及检测性能上都有很大提升。     

Fisher鉴别特征的最近邻凸包分类

基于Fisher准则的特征提取方法是模式识别技术的重要分支,其中,Foley-Sammon变换和具有统计不相关性的最佳鉴别变换是这一技术典型代表,本文将它们与一种新型分类器一最近邻凸包分类器相结合,从而实现Fisher鉴别特征的有效分类。最近邻凸包分类器是一类以测试样本点到各类训练集生成类别凸包的距离为分类判别依据的模式分类新方法,具有非线性性,无参性,多类别适用性等特点。实验证实了本文方法的有效性。     

l1范数最近邻凸包分类器在人脸识别中的应用

l1范数作为重要的距离测度,在模式识别中有着较为广泛的应用。在不同的范数定义下,相同分类机理的分类算法一般会有不同的分类效果。本文提出l1范数下的最近邻凸包人脸识别算法。该算法将最近邻凸包分类算法的范数定义由l2范数推广到l1范数,以测试点到各训练类凸包的l2范数距离作为最近邻分类的相似性度量。在ORL标准人脸数据库上的验证实验中,该方法取得了良好的识别效果。     

From classifiers to discriminators: A nearest neighbor rule induced discriminant analysis

The current discriminant analysis method design is generally independent of classifiers, thus the connection between discriminant analysis methods and classifiers is loose. This paper provides a way to design discriminant analysis methods that are bound with classifiers. We begin with a local mean based nearest neighbor (LM-NN) classifier and use its decision rule to supervise the design of a discriminator. Therefore, the derived discriminator, called local mean based nearest neighbor discriminant analysis (LM-NNDA), matches the LM-NN classifier optimally in theory. In contrast to that LM-NNDA is a NN classifier induced discriminant analysis method, we further show that the classical Fisher linear discriminant analysis (FLDA) is a minimum distance classifier (i.e. nearest Class-mean classifier) induced discriminant analysis method. The proposed LM-NNDA method is evaluated using the CENPARMI handwritten numeral database, the NUST603 handwritten Chinese character database, the ETH80 object category database and the FERET face image database. The experimental results demonstrate the performance advantage of LM-NNDA over other feature extraction methods with respect to the LM-NN (or NN) classifier.     

Linear reconstruction measure steered nearest neighbor classification framework

The linear reconstruction measure (LRM), which determines the nearest neighbors of the query sample in all known training samples by sorting the minimum L₂-norm error linear reconstruction coefficients, is introduced in this paper. The intuitive interpretation and mathematical proofs are presented to reveal the efficient working mechanism of LRM. Through analyzing the physical meaning of coefficients and regularization items, we find that LRM provides more useful information and advantages than the conventional similarity measure model which calculates the distance between two entities (i.e. conventional point-to-point, C-PtP). Inspired by the advantages of LRM, the linear reconstruction measure steered nearest neighbor classification framework (LRM-NNCF) is designed with eight classifiers according to different decision rules and models of LRM. Evaluation on several face databases and the experimental results demonstrate that these proposed classifiers can achieve greater performance than the C-PtP based 1-NNs and competitive recognition accuracy and robustness compared with the state-of-the-art classifiers.     

Active learning based on coupled KNN pseudo pruning

It is very expensive and time-consuming to annotate huge amounts of data. Active learning would be a suitable approach to minimize the effort of annotation. A novel active learning approach, coupled K nearest neighbor pseudo pruning (CKNNPP), is proposed in the paper, which is based on querying examples by KNNPP method. The KNNPP method applies k nearest neighbor technique to search for k neighbor samples from labeled samples of unlabeled samples. When k labeled samples are not belong to the same class, the corresponded unlabeled sample is queried and given its right label by supervisor, and then it is added to labeled training set. In contrast with the previous depiction, the unlabeled sample is not selected and pruned, that is the pseudo pruning. This definition is enlightened from the K nearest neighbor pruning preprocessing. These samples selected by KNNPP are considered to be near or on the optimal classification hyperplane that is crucial for active learning. Especially, in order to avoid the excursion of the optimal classification hyperplane after adding a queried sample, CKNNPP method is proposed finally that two samples with different class label (like a couple, annotated by supervisor) are queried by KNNPP and added in the training set simultaneously for updating training set in each iteration. The CKNNPP can provide a good performance, and especially it is simple, effective, and robust, and can solve the classification problem with unbalanced dataset compared with the existing methods. Then, the computational complexity of CKNNPP is analyzed. Additionally, a new stopping criterion is applied in the proposed method, and the classifier is implemented by Lagrangian Support Vector Machines in iterations of active learning. Finally, twelve UCI datasets, image datasets of aircrafts, and the dataset of radar high-resolution range profile are used to validate the feasibility and effectiveness of the proposed method. The results illuminate that CKNNPP gains superior performance compared with the other seven state-of-the-art active learning approaches.     

基于近邻密度和半监督KNN的集成自训练方法

针对集成自训练算法随机初始化有标记样本容易在迭代中局部过拟合,不能很好地泛化到样本原始空间结构和集成自训练算法用WKNN分类器做数据剪辑时没有考虑到无标记样本对待测样本类别判定有影响的问题,提出结合近邻密度和半监督KNN的集成自训练算法。该算法用近邻密度方法选取初始化的已标注样本,避免已标注样本周围[k]个近邻样本成为已标注候选集。这样使初始化的已标注样本间的距离尽量分散,以更好地反应样本原始空间结构。同时在已标注样本候选集中选取密度最大的样本作为已标注样本。为了提高数据剪辑的性能,用半监督KNN代替WKNN,弥补WKNN做数据剪辑的时候只考虑到了有标记样本对待测样本类别的影响,而没有利用待测样本周围的无标记样本的问题,在UCI数据集上的对比实验验证了提出算法的有效性。     

基于余类零空间与最近距离的人脸识别算法

提出了一种新的人脸识别算法,即基于余类零空间与最近距离的人脸识别算法. 通过构建不同类别的人脸图像的余类零空间与子空间,可以将不同类别的人脸最大化地区别出来. 本算法的主要思想在于：测试图像与所属类别图像的子空间之间的距离最小,而与所属类别的图像的余类零空间距离最大. 本算法基于ORL数据集与AR数据集进行了测试. 从这些人脸数据集上的测试结果可以看出,本文提出的算法在PCA降维方法的基础上,比一些常见的算法所使用的判别方式更有效,如最近邻分类器（NN）所使用的最近距离判别方式、最近空间分类器（NS）所使用的最近空间距离判别方式、最近最远子空间分类器（NFS）所使用的最近最远空间距离判别方式等.     

K nearest neighbor reinforced expectation maximization method

K nearest neighbor and Bayesian methods are effective methods of machine learning. Expectation maximization is an effective Bayesian classifier. In this work a data elimination approach is proposed to improve data clustering. The proposed method is based on hybridization of k nearest neighbor and expectation maximization algorithms. The k nearest neighbor algorithm is considered as the preprocessor for expectation maximization algorithm to reduce the amount of training data making it difficult to learn. The suggested method is tested on well-known machine learning data sets iris, wine, breast cancer, glass and yeast. Simulations are done in MATLAB environment and performance results are concluded.     

基于Gabor变换和双方向PCA的人脸识别

提出了一种可以解决小样本问题的人脸识别新算法。算法首先把人脸图像经过Gabor小波变换后得到的每个输出图像都看成是独立的样本,从而大大增加了每一类人脸样本的样本数。然后采用双方向PCA算法来提取人脸特征,并专门设计了针对人脸特征矩阵的最近邻分类器和最小距离分类器来进行分类判决。在ORL人脸库和FERET人脸库中的实验结果表明,算法能有效地解决人脸识别中的小样本问题,甚至当每类训练样本数仅为1时,也能得到较高的识别率。     

基于自适应距离度量的最小距离分类器集成

提出了一种基于自适应距离度量的最小距离分类器集成方法,给出了个体分类器的生成方法。首先用Bootstrap技术对训练样本集进行可重复采样,生成若干个子样本集,应用生成的子样本集建立自适应距离度量模型,根据建立的模型对子样本集进行训练,生成个体分类器。在集成中,将结果用相对多数投票法集成最终的结论。采用UCI标准数据集实验,将该方法与已有方法进行了性能比较,结果表明基于自适应距离度量的最小距离分类器集成是最有效的。