Optimal reference subset selection for nearest neighbor classification by tabu search

This paper presents an approach to select the optimal reference subset (ORS) for nearest neighbor classifier. The optimal reference subset, which has minimum sample size and satisfies a certain resubstitution error rate threshold, is obtained through a tabu search (TS) algorithm. When the error rate threshold is set to zero, the algorithm obtains a near minimal consistent subset of a given training set. While the threshold is set to a small appropriate value, the obtained reference subset may have reasonably good generalization capacity. A neighborhood exploration method and an aspiration criterion are proposed to improve the efficiency of TS. Experimental results based on a number of typical data sets are presented and analyzed to illustrate the benefits of the proposed method. The performances of the result consistent and non-consistent reference subsets are evaluated.     

基于FLANN改进的KNN医疗分类算法

本文通过研究KNN（K-最近邻）算法在疾病预测领域的使用与分析,总结出KNN的2点不足,针对不足进行相应改进并提出F_KNN（循环最近邻搜索）算法：1）针对KNN计算量大、效率低下的缺点,本文采用FLANN（快速最近邻搜索）循环搜索与待测样本距离最近的点,记录若干个最近邻点作为最近邻点子集,利用此子集取代全集对待测样本进行计算,可以降低计算量,极大地提高了KNN算法效率;2）针对KNN难以对高维数据集分类的缺点,本文采用AHP（层次分析法）对样本的特征属性进行相关性研究,使用合适的参数分配权重,提高了KNN算法准确率。本文采用一组脑中风数据集对优化后的算法进行实验,实验结果表明,F_KNN准确率达96.2%。与传统KNN相比,F_KNN提高了分类性能且极大地提高了算法效率。在处理高维且较大的数据集时,F_KNN算法优势明显,具有较好的应用前景。     

改进的全局最近邻查询算法及其在空间数据库中的应用

针对基础数据集合和参考数据集合为相同数据集的情况,给出了一种新型的空间数据库全局最近邻查询算法,该算法能够利用数据最近邻结果的自身特点,避免较大的查询过程中的资源开销.实验结果表明,算法的效率要明显优于常用最近邻查询算法,并且对于不同的数据维数和数据元素数量,特别是对于高维的空间数据集合,算法具有较高的稳定性.     

K最近邻算法理论与应用综述

k最近邻算法（kNN）是一个十分简单的分类算法,该算法包括两个步骤：（1）在给定的搜索训练集上按一定距离度量,寻找一个k的值。（2）在这个kNN算法当中,根据大多数分为一致的类来进行分类。kNN算法具有的非参数性质使其非常易于实现,并且它的分类误差受到贝叶斯误差的两倍的限制,因此,kNN算法仍然是模式分类的最受欢迎的选择。通过总结多篇使用了基于kNN算法的文献,详细阐述了每篇文献所使用的改进方法,并对其实验结果进行了分析;通过分析kNN算法在人脸识别、文字识别、医学图像处理等应用中取得的良好分类效果,对kNN算法的发展前景无比期待。     

基于查询集空间分布的聚合最近邻查询算法

聚合最近邻查询涉及到多个查询对象,因此比传统最近邻查询更复杂,而且其查询集空间分布特征暗含了查询集聚合最近邻的区域分布信息。充分考虑查询集分布特征,给出了利用分布特征指导聚合最近邻搜索的方法,并以此提出了一种新的聚合最近邻查询算法——AM算法。AM算法能动态地捕捉并利用查询集空间分布特征,使得对数据点的搜索按正确的次序进行,避免对不必要数据点的搜索。最后通过实验验证了AM算法的高效性。     

空间数据库中的线段k近邻查询研究

K近邻查询是空间数据库中的重要查询之一,k近邻查询在内容的相似性检索、模式识别、地理信息系统中有重要应用。针对现有k近邻查询都是基于点查询的情况,提出基于平面线段的k近邻查询,查找线段集中给定查询点的k个最近线段。给出基于Voronoi图的线段k近邻查询算法及给出相关定理和证明。该算法通过线段Voronoi图的邻接特性找到一个候选集,然后从中找到最终结果。通过随机数据的实验证明,所提算法明显优于线性扫描算法和基于R树的k近邻查询算法。     

基于最近邻子空间搜索的两类文本分类方法

在文本分类中,最近邻搜索算法具有思想简单、准确率高等优点,但通常在分类过程中的计算量较大。为克服这一不足,提出了一种基于最近邻子空间搜索的两类文本分类方法。首先提取每一类样本向量组的特征子空间,并通过映射将子空间变换为高维空间中的点,然后把最近邻子空间搜索转化为最近邻搜索完成分类过程。在Reuters-21578数据集上的实验表明,该方法能够有效提高文本分类的性能,具有较高的准确率、召回率和F1值。     

利用细胞自动机模型约减最近邻分类规则

目前常见的最近邻分类规则约减算法,只注重约减后分类器的分类精度和被约减的规则数量,而不注重约减效率和约减后分类器的泛化能力。针对该问题,提出了一种细胞自动机(cellular automata,CA)基础上的最近邻分类规则约减方法。该方法只保留不同类边界上的样本点,约减规则的数量可以由细胞自动机网格的粒度动态调节。其优势在于:在给定的大数据集前提下,可以利用较少的运行时间来约减给定的规则样本;可以利用积累或迭代的方式来分步获得原给定样本集的一致性子集。采用13个不同的数据集进行仿真实验,结果显示该算法简单、有效,较好地解决了大样本集的约减问题。     

基于时间加权的个性化推荐算法研究

协同过滤算法是个性化推荐系统中应用最成功的推荐算法之一,但传统的算法没有考虑在不同时间段内寻找最近邻居问题,导致寻找的邻居集合可能不是最近邻居集合。针对这个问题,本文提出了基于时间加权的协同过滤算法。该算法赋予每项评分一个按时间逐步递减的权重,利用加权后的评分寻找目标用户的最近邻居。实验表明,改进的算法提高了协同过滤推荐系统的推荐质量。     

基于概率分布估计算法的进化规划码书设计算法

提出一种以最近邻划分变异为搜索策略,并以EP(进化规划)与EDA(概率密度估计算法)相结合的混合进化方法作为搜索引擎的新型码书设计算法.在最近邻划分上,引入最近邻划分控制因子作为进化算法的染色体表示,实现最近邻划分变异,从而改变质心运动轨迹.染色体与矢量同维,编码空间相对较小,并且进化操作易于控制和实现.在混合进化方法中,EDA为EP提供了最优个体的搜索方向,加速了算法的收敛速度.实验结果表明该方法是能有效提高码书性能的一种优化方法.     

基于概率的两层最近邻自适应度量分类算法

针对有限样本下,KNN算法距离量的选择以及以前距离量学习研究中没有充分考虑样本分布的情况,提出了一种新的基于概率的两层最近邻自适应度量算法（PTLNN）。该算法分为两层,在低层使用欧氏距离来确定一个未标记的样本局部子空间;在高层,用AdaBoost在子空间进行信息提取。以最小化平均绝对误差为原则,定义一个基于概率的自适应距离度量进行最近邻分类。该算法结合KNN与AdaBoost算法的优势,在有限样本下充分考虑样本分布能降低分类错误率,并且在噪声数据下有很好的稳定性,能降低AdaBoost过度拟合现象发生。通过与其他算法对比实验表明,PTLNN算法取得更好的结果。     

A nonparametric two-dimensional display for classification

A two-dimensional display whose coordinates are related to the distance to the kth-nearest neighbor of each class is presented. Applications of the display to minimum error, minimum cost, minimax, and Neyman-Pearson type classifier designs are given. The display is shown to present risk information in a manner that easily allows the specification of reject regions. Two methods of error estimation using the display, an error counting technique and a risk averaging method, are detailed. It is shown that the classifiers that result are generalizations of the standard k-NN majority vote classifier. As a result of the properties of the display, classifiers can be readily evaluated and modified. In addition, a condensing algorithm that preserves the nearest neighbor error count of any preclassified data set is described. The display is used to graphically illustrate the distance relationships that are central to the algorithm.     

改进邻居集合的个性化推荐算法

协同过滤算法是目前个性化推荐系统中应用最成功的推荐算法之一,但传统的算法没有考虑在不同时间段内寻找最近邻居问题,导致寻找的邻居集合可能不是最近邻居集合。针对此问题,提出一种改进邻居集合的个性化推荐算法。该算法赋予每项评分一个按时间逐步递减的权重,利用加权后的评分寻找目标用户的最近邻居。实验表明,改进的算法提高了推荐系统的推荐质量。     

Distributed Nearest Neighbor-Based Condensation of Very Large Data Sets

In this work, the parallel fast condensed nearest neighbor (PFCNN) rule, a distributed method for computing a consistent subset of a very large data set for the nearest neighbor classification rule is presented. In order to cope with the communication overhead typical of distributed environments and to reduce memory requirements, different variants of the basic PFCNN method are introduced. An analysis of spatial cost, CPU cost, and communication overhead is accomplished for all the algorithms. Experimental results, performed on both synthetic and real very large data sets, revealed that these methods can be profitably applied to enormous collections of data. Indeed, they scale up well and are efficient in memory consumption, confirming the theoretical analysis, and achieve noticeable data reduction and good classification accuracy. To the best of our knowledge, this is the first distributed algorithm for computing a training set consistent subset for the nearest neighbor rule.     

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

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

基于粒计算的多标签懒惰学习算法

多标签学习用于处理一个样本同时拥有多个标签的问题。已有的多标签懒惰学习算法IMLLA未充分考虑样本分布的特点,即在构建样本的近邻点集时,近邻点个数取固定值,这可能会将相似度高的点排除在近邻集之外,或者将相似度低的点包括在近邻集内,影响分类方法的性能。针对IMLLA的缺陷,将粒计算的思想加入近邻集的构建,提出一种基于粒计算的多标签懒惰学习算法(GMLLA)。该方法通过粒度控制,确定样本近邻点集,使得近邻集内的样本具有高相似度。实验结果表明,本算法的性能优于IMLLA。     

室内概率阈值反向最近邻查询

室内空间变得越发的庞大和复杂,随之产生了越来越多的室内空间查询需求.目前已有文献提出了针对室内空间环境的范围查询和最近邻查询,而作为常见的空间查询类型的反向最近邻查询,尚未有相关的研究.为此,提出了室内概率阈值反向最近邻查询和基于定位设备的设备可达图模型.在图模型基础上,提出了室内概率阈值反向最近邻查询处理算法,该算法由基于图模型的批量剪枝、基于室内距离的剪枝、基于概率的剪枝和概率计算4部分构成,通过剪枝策略修剪掉不可能出现在结果集中的对象,从而缩小了查询空间,提高了效率.     

Bayes Error Estimation Using Parzen and k-NN Procedures

The use of k nearest neighbor (k-NN) and Parzen density estimates to obtain estimates of the Bayes error is investigated under limited design set conditions. By drawing analogies between the k-NN and Parzen procedures, new procedures are suggested, and experimental results are given which indicate that these procedures yield a significant improvement over the conventional k-NN and Parzen procedures. We show that, by varying the decision threshold, many of the biases associated with the k-NN or Parzen density estimates may be compensated, and successful error estimation may be performed in spite of these biases. Experimental results are given which demonstrate the effect of kernel size and shape (Parzen), the size of k (k-NN), and the number of samples in the design set.     

求解决策表最小属性约简的SAGA

首先给出求解决策表核属性集的算法,然后采用动态调节近邻子集的方法改进模拟退火遗传算法,应用于求解决策表的最小属性约简。该约简算法利用核属性集优化初始种群,并采用自适应方式动态选取交叉和变异概率,有效地抑制了早熟收敛现象,提高了算法在解空间中的探索能力和效率。实验结果显示该算法能有效求解决策表最小属性约简问题。     

微阵列数据中Top-k频繁闭合项集挖掘

现有大部分微阵列数据中频繁闭合项集的挖掘需要事先给定最小支持度,但在实际应用中该最小支持度很难确定。针对该问题,提出top-k频繁闭合项集挖掘算法,基于自顶向下宽度优先搜索策略挖掘项集长度不小于min_l的top-k频繁闭合项集,并对搜索空间进行有效修剪,从而提高搜索速度。实验结果表明,该算法的时间性能在多数情况下优于CARPENTER算法。