Fast and versatile algorithm for nearest neighbor search based on a lower bound tree

In this paper, we present a fast and versatile algorithm which can rapidly perform a variety of nearest neighbor searches. Efficiency improvement is achieved by utilizing the distance lower bound to avoid the calculation of the distance itself if the lower bound is already larger than the global minimum distance. At the preprocessing stage, the proposed algorithm constructs a lower bound tree (LB-tree) by agglomeratively clustering all the sample points to be searched. Given a query point, the lower bound of its distance to each sample point can be calculated by using the internal node of the LB-tree. To reduce the amount of lower bounds actually calculated, the winner-update search strategy is used for traversing the tree. For further efficiency improvement, data transformation can be applied to the sample and the query points. In addition to finding the nearest neighbor, the proposed algorithm can also (i) provide the k-nearest neighbors progressively; (ii) find the nearest neighbors within a specified distance threshold; and (iii) identify neighbors whose distances to the query are sufficiently close to the minimum distance of the nearest neighbor. Our experiments have shown that the proposed algorithm can save substantial computation, particularly when the distance of the query point to its nearest neighbor is relatively small compared with its distance to most other samples (which is the case for many object recognition problems).     

基于最近邻互信息的特征选择算法

针对邻域信息系统的特征选择模型存在人为设定邻域参数值的问题。分别计算样本与最近同类样本和最近异类样本的距离,用于定义样本的最近邻以确定信息粒子的大小。将最近邻的概念扩展到信息理论,提出最近邻互信息。在此基础上,采用前向贪心搜索策略构造了基于最近邻互信息的特征算法。在两个不同基分类器和八个UCI数据集上进行实验。实验结果表明：相比当前多种流行算法,该模型能够以较少的特征获得较高的分类性能。     

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

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

空间数据库中的组障碍最近邻查询研究

已有的关于组最近邻查询的研究都是基于欧氏距离的,无法解决存在障碍情况下基于障碍距离的组最近邻查询问题.为此,提出障碍物环境中组最近邻查询的一种新的变体,即组障碍最近邻(group obstacle nearest neighbor, GONN)查询.GONN返回数据集中与查询点集中所有点的障碍距离之和最小的点.根据数据集中的点与查询点集的最小外包距离(minimum bounding rectangle, MBR)之间的不同位置关系,构造各种情况下查询点集的MBR相对于数据集中点的剪枝区域.利用剪枝区域剪去障碍集中对障碍距离计算无影响的障碍,给出数据集中点与查询点集之间障碍距离的计算算法.定义组障碍最近邻查询的剪枝规则,根据障碍距离计算给出组障碍最近邻查询的算法.并给出相关定理和证明.实验结果证明算法具有较高效率.     

基于自适应近邻参数的密度峰聚类算法

针对基于共享最近邻的密度峰聚类算法中的近邻参数需要人为设定的问题,提出了一种基于自适应近邻参数的密度峰聚类算法。首先,利用所提出的近邻参数搜索算法自动获得近邻参数;然后,通过决策图选取聚类中心;最后,根据所提出的代表点分配策略,先分配代表点,后分配非代表点,从而实现所有样本点的聚类。将所提出的算法与基于共享最近邻的快速密度峰搜索聚类（SNN?DPC）、基于密度峰值的聚类（DPC）、近邻传播聚类（AP）、对点排序来确定聚类结构（OPTICS）、基于密度的噪声应用空间聚类（DBSCAN）和K-means这6种算法在合成数据集以及UCI数据集上进行聚类结果对比。实验结果表明,所提出的算法在调整互信息（AMI）、调整兰德系数（ARI）和FM指数（FMI）等评价指标上整体优于其他6种算法。所提算法能自动获得有效的近邻参数,且能较好地分配簇边缘区域的样本点。     

面向密度分布不均数据的近邻优化密度峰值聚类算法

密度分布不均数据是指类簇间样本分布疏密程度不同的数据.密度峰值聚类(DPC)算法在处理密度分布不均数据时,倾向于在密度较高区域内找到类簇中心,并易将稀疏类簇的样本分配给密集类簇.为避免上述缺陷,提出一种面向密度分布不均数据的近邻优化密度峰值聚类(DPC-NNO)算法.DPC-NNO算法结合逆近邻和k近邻定义新的局部密度,提高稀疏样本的局部密度,使算法能更准确地找到类簇中心;定义分配策略时引入共享近邻,计算样本间相似性,构造相似矩阵,使同一类簇样本联系更紧密,避免错误分配样本.将所提出的DPC-NNO算法与IDPC-FA、DPCSA、FNDPC、FKNN-DPC、DPC算法进行对比,实验结果表明,DPC-NNO算法在处理密度分布不均数据时能获得优异的聚类效果,对于复杂数据集和UCI数据集,DPC-NNO算法的综合性能优于对比算法.     

Large-margin nearest neighbor classifiers via sample weight learning

The nearest neighbor classification is a simple and yet effective technique for pattern recognition. Performance of this technique depends significantly on the distance function used to compute similarity between examples. Some techniques were developed to learn weights of features for changing the distance structure of samples in nearest neighbor classification. In this paper, we propose an approach to learning sample weights for enlarging margin by using a gradient descent algorithm to minimize margin based classification loss. Experimental analysis shows that the distances trained in this way reduce the loss of the margin and enlarge the hypothesis margin on several datasets. Moreover, the proposed approach consistently outperforms nearest neighbor classification and some other state-of-the-art methods.     

基于粒计算的K近邻多标签学习算法

K近邻多标签学习算法的近邻点个数取固定值,而没有考虑样本分布的特点,可能会将相似度高的点排除在近邻集外,或者将相似度低的点包含在近邻集内,影响分类器的性能。为此,将粒计算的思想引入近邻集的构建,提出一种新的K近邻多标签学习算法。通过粒度控制,确定近邻点集,使得领域内的样本点有高相似性,且此类样本能进入近邻集。实验结果表明,该算法的大多数评价指标均优于现有的多标签学习算法。     

基于Voronoi图的组最近邻查询

组最近邻查询由于涉及多个查询点,因此比传统的最近邻查询更为复杂.充分考虑查询点的分布特征以及它们构成的几何图形的性质和特点,给出组最近邻所应满足的条件及判断组最近邻的理论方法.提出基于Voronoi图的组最近邻查询的VGNN算法,可以精确求解查询点集的最近邻.对于查询点不共线的情况,该算法的查询方式是以一点为中心、向外扩张式的;对于查询点共线的情况,该算法给出搜索范围,限定了参与计算的数据点的个数.给出基于Voronoi图的VTree索引.实验结果表明,基于VTree索引的VGNN算法具有较好的性能,并且当查询点不共线时,其性能具有较高的稳定性.     

k近邻约束的稀疏子空间聚类

稀疏子空间聚类是近年提出的高维数据聚类框架，针对实际数据并不完全满足线性子空间模型的假设，提出[k]近邻约束的稀疏子空间聚类算法。该算法结合数据的子空间结构，[k]近邻及距离信息，在稀疏子空间模型上，添加[k]近邻约束项。添加的约束项符合距离越小，相似系数越大的直观认识且不改变系数矩阵的稀疏性。在人脸数据集Extended YaleB、ORL、AR，物体图像数据集COIL20及手写数据集USPS上的聚类实验表明提出的算法具有良好的性能。     

基于CMAC的非参数化近似策略迭代增强学习

为解决在线近似策略迭代增强学习计算复杂度高、收敛速度慢的问题，引入CMAC结构作为值函数逼近器，提出一种基于CMAC的非参数化近似策略迭代增强学习（NPAPI-CMAC）算法。算法通过构建样本采集过程确定CMAC泛化参数，利用初始划分和拓展划分确定CMAC状态划分方式，利用量化编码结构构建样本数集合定义增强学习率，实现了增强学习结构和参数的完全自动构建。此外，该算法利用delta规则和最近邻思想在学习过程中自适应调整增强学习参数，利用贪心策略对动作投票器得到的结果进行选择。一级倒立摆平衡控制的仿真实验结果验证了算法的有效性、鲁棒性和快速收敛能力。     

粒向量与K近邻粒分类器

K近邻(K nearest neighbor, KNN)分类器是一种经典的分类器,它简单而又有效,已经在人工智能与机器学习领域得到了广泛的应用.针对传统分类器难以处理不确定性数据的问题,研究样本单特征邻域粒化技术,构造粒的向量形式,提出一种基于粒向量的K近邻分类方法.该方法引入邻域粗糙集模型,对分类系统中的样本进行单特征邻域粒化,形成特征邻域粒子.并由多个特征邻域粒子构成一个粒向量,定义了多种粒向量运算算子,提出了2种粒向量距离：相对粒距离与绝对粒距离,证明了粒向量距离的单调性原理.进一步,基于粒向量距离定义了K近邻粒向量概念,提出了K近邻粒分类器.最后,结合UCI数据集,采用K近邻粒分类器与经典K近邻分类器进行比较测试.理论分析和实验表明:针对合适的粒化参数与k值,K近邻粒分类器具有较好的分类性能.     

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

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

基于新型四叉树分割的快速分形图像编码

针对现有的基于四叉树的分形编码算法比较耗时的问题,提出了一种基于新型四叉树分割的快速分形编码方法。首先根据人眼视觉系统（HVS）特性分割出子块,再将各不同尺寸子块所对应的父块库中的父块按标准差排序。对于每一子块,在对应的父块库中寻找其在标准差意义下的最近邻父块,然后在该父块的邻域内进一步搜索最佳匹配父块,同时引进误差阈值来控制子块的搜索过程。实验结果证明,该算法的编码速度大大提高。     

基于局部密度和测地距离的谱聚类

传统根据[K]-近邻图计算测地距离的方法,虽然能够发现流形分布数据间的相似关系,但是当不同类的点存在粘连关系时,依此计算相似度时不能体现样本间的真实关系,从而无法有效聚类。针对传统测地距离计算相似度的方法不能有效处理粘连数据集的问题,提出了基于局部密度和测地距离的谱聚类方法。计算样本的局部密度,寻找每个样本点的最近高密度点,并选择边缘点和非边缘点;在边缘点和其最近高密度点之间构造边、非边缘点之间的[K]个近邻点构造边,依此计算测地距离和相似度并进行聚类。在人工数据集和UCI数据集上的实验表明,该算法在处理粘连数据集时有效提高了聚类准确率。     

基于SURF和快速近似最近邻搜索的图像匹配算法

针对高维特征向量存在的最近邻匹配正确率低的问题, 提出了一种基于SURF和快速近似最近邻搜索的图像匹配算法。首先用Fast-Hessian 检测子进行特征点检测, 并生成SURF特征描述向量; 然后通过快速近似最近邻搜索算法得到初匹配点对, 再对得出的单向匹配结果进行双向匹配; 最后采用鲁棒性较好的PROSAC算法进一步剔除误匹配点对。实验证明了该算法不仅提高了SURF算法匹配的正确率, 还保证了算法的实时性。     

一种基于加权KNN的大数据集下离群检测算法

传统KNN算法是在基于距离的离群检测算法的基础上提出的一种在大数据集下进行离群点挖掘的算法, 然而KNN算法只以最近的第k个部居的距离作为判断是否是离群点的标准有时也失准确性。给出了一种在大数据 集下基于KNN的离群点检测算法,即在传统KNN方法的基础上为每个数据点增加了权重,权重值为与最近的k个 邻居的平均距离,离群点为那些与第k个部居的距离最大且相同条件下权重最大的点。算法能提高离群点检测的准 确性,通过实验验证了算法的可行性,并与传统KNN算法的性能进行了对比。     

一种属性不一致性加权的K近邻分类方法

针对传统的K近邻算法在计算样本之间相似度时将每个属性视为同等重要的问题,提出了一种基于推土机距离的方法来计算每个条件属性的权重。首先根据近邻关系划分用于比较一致性的两个分布;之后根据推土机距离设计不一致性评价函数,用于衡量每个属性下各个样本的近邻样本集与这一集合由决策属性细化的等价划分之间的不一致性程度;最后将近邻的不一致性程度转换为相应属性的重要性,用于实现属性加权K近邻分类器。通过在多个数据集上进行实验,该方法对参数的敏感程度低,在多个参数下可以显著提高K近邻的分类精度,并且在多个指标下的表现优于现有的一些分类方法。结果表明,该方法可以通过属性加权选择出更加准确的近邻样本,可广泛应用于基于近邻的机器学习方法中。     

改进K近邻和支持向量机相融合的天气识别

天气受到多种因素综合影响,具有时变性和不确定性,单一模型难以获得较高的识别正确率,为此,提出一种改进K近邻和支持向量机相融合的天气识别模型（IKNN-SVM）。首先计算待识别样本与超平面间距离,然后将距离与预设阈值进行比较,如果大于阈值,则采用支持向量机对天气进行识别,否则利用K近邻算法对天气进行识别,并引入样本密度对K近邻算法进行改进,最后采用仿真实验对模型性能进行测试。仿真结果表明,相对于单一的KNN或SVM,IKNN-SVM提高了天气识别正确率,较好地克服单一模型存在的缺陷。     

基于标准差的快速分形图像编码

由于基本分形图像编码过程非常耗时,本文提出了一种基于标准差的快速分形编码方法.先将子、父块按标准差分为平滑块和非平滑块.码本由所有非平滑父块构成,并按标准差赋序.若子块为平滑块,直接存储其均值,否则在赋序码本中寻找其在标准差意义下的最近邻父块,进而在该父块的邻域内进一步搜索最佳匹配父块,搜索时需对父块进行8种等距变换,同时引进误差阈值来控制子块搜索的邻域范围.实验证明,该算法编码速度大大提高,并且该算法在相近编码时间前提下的解码图像质量及在相近峰值信噪比（PSNR）情况下的编码速度均优于基于图像块叉迹的快速算法.