基于自动终止准则改进的kd-tree粒子近邻搜索研究

对于大规模运动模拟问题而言,近邻点的搜索效率将对整体的运算效率产生显著影响。本文基于关联性分析建立kd-tree的最大深度dmax与粒子总数N的自适应关系式,提出了kd-tree自动终止准则,即ATC-kd-tree,同时还考虑了叶子节点大小阈值n0对近邻搜索效率的影响。实验表明ATC-kd-tree具有更高的近邻搜索效率,适用性更强,可求解不同N值的近邻搜索问题,解决了粒子总数N发生改变时需要再次率定最大深度dmax的问题。同时,本文还提出了网格搜索法组合坐标下降法的两步参数优化算法GSCD法。通过参数优化效率对比实验发现,GSCD法可更为快速地率定ATC-kd-tree的可变参数,其优化效率相比于网格搜索法最高提升了205%,相较于改进网格搜索法最高提升了90%。     

一种快速的反向k近邻查找算法及其改进

提出一种快速的反向k近邻查找算法,该方法利用现代计算机具有外存便宜、运行速度快的特点,预先计算数据之间的距离,并组织为数据索引块存储于外存,由计算机在空闲时自动进行维护.在进行反向最近邻查询时,只需读入相应的索引块,就可进行直接查询,其时间复杂度为O(N),而且不受k的影响.为减少索引块的读取时间,提出一种改进方法来有效地压缩索引块,仅用必要的二进制位来存储对象之间的距离,并将冗余减少到最低水平,提高了算法的效率.最后通过实验分析评估算法的有效性和效率.     

近似最近邻大数据检索哈希散列方法综述

近似最近邻检索已成为人工智能时代海量数据快速检索主要技术之一。作为高效的近似最近邻检索方法,哈希散列方法受到广泛关注并且层出不穷。到目前为止还没有文献对主流哈希散列方法进行全面地分析和总结。鉴于此,本文首先系统地介绍哈希散列的基本知识,包括距离计算、损失函数、离散约束和外样本计算等。然后,深入对比分析主流哈希散列算法优缺点,并在主流数据库上进行性能评估。最后,总结哈希散列技术目前存在的问题,并提出若干潜在的哈希散列研究方向。本文对设计高效的哈希散列方法具有重要借鉴意义。     

基于V~＋图的移动K近邻查询研究

移动K近邻查询（MkNN）找到一个移动查询点的K个连续最近邻。目前解决此类查询的方法有两种：利用采样的方法和基于安全区域的方法。在传统的安全区域方法基础上提出一种基于安全区域的技术来计算MkNN,称为V＋图。此方法除了数据对象外还利用查询点和查询空间的信息,给出基于V＋图的MkNN查询算法和相应定理及其证明。     

时空数据库中基于TPR-树的反向最近邻查询

为研究动态环境下解决反向最近邻查询的算法,采用TPR-树索引结构给出了解决动态环境下的最近邻查询算法,并提出反向最近邻查询算法.该算法可有效解决平面上连续移动点的反向最近邻查询.     

近似最近邻搜索算法——位置敏感哈希

寻找查询点的最近邻是信息处理相关领域的主要任务之一。在数据规模较大时需要采用快速检索算法,常用的快速检索算法主要是基于树的算法,但是当数据点维数较高时,这些算法的效率会变低。位置敏感哈希是当前解决高维搜索的最快的算法,文章对汉明空间、欧式空间下的位置敏感哈希算法的实现方案进行了详细分析,对算法中数据点冲突概率、空间时间消耗、参数调整对算法性能的影响进行了详尽的研究和试验,最后讨论算法的优点和缺点,说明了算法应用于视觉聚类的可能性。     

一种连续最近邻查询的优化方法

连续最近邻查询是空间数据库中最重要的查询之一,在地理信息系统和位置定位服务等领域有重要应用.给定一个空间数据集P和查询线段q,连续最近邻查询返回结果＜R,T＞,其中T是一个间隔,R是这个间隔中所有点的最近邻.已有的连续最近邻查询算法无法实现I/O的优化,为此,提出一种优化的连续最近邻查询方法,该方法具有较高的I/O效率,不仅在减少磁盘访问数量方面进行优化,同时也提高CPU的性能.     

一种相似性保持的线性嵌入哈希方法

In order to implement quick and effective search, save the storage space and improve the poor performance of affinity relationshaps between high dimensional data and its codes in image retrieval, a new linear embedding hashing is proposed by introducing the preserving similarity. First, the whole data set is clustered into several classes, and then the similarity predicted function is used to maintain affinity relationships between high dimensional data and its codes so as to establish the objective function. By minimizing the margin loss function, the optimal embedded matrix can be obtained. Compared with the existing classic hashing algorithm, experimental results show that the performance of the linear embedding hash algorithm is superior to the other binary encoding strategy on precision and recall.     

旅行商问题的较优可行解的搜索算法的设计

利用问题本身的特点和相关的已有结论,结合最近邻法和深度优先搜索算法设计了产生旅行商问题较优可行解的方法。首先,将与每个城市关联的城市由近到远排序,并将城市之间距离较远的边删除。然后选择一个城市作为出发地,按排序利用深度优先搜索算法在有限步内搜索可行解。若搜索到多个可行解,从中选择较优的作为以该城市为出发地的可行解;否则,重新选择出发地开始新的搜索。对经典的st70、a280问题依次将每个城市作为出发地进行实验,该方法产生的可行解的性能明显优于随机搜索算法。但仍不及最近邻法。     

顾客需求模板的动态分类树研究

顾客需求模板是质量功能配置(QFD)系统对设计实例和规则进行规范化的工具。文章基于质量功能配置中顾客需求动态获取的特点,分析了顾客需求模板实例提取和动态进化过程,规范了设计实例及设计规则的描述,提出了实现模板动态进化的动态分类树的概念,探讨了动态分类树的存储、规则调整方式以及实例归类方法。结果表明:基于数据结构的二叉树定义,将动态分类树的存储设计为三重链接方式,实例规则调整采用自下而上的方式检索规则并存储,实现系统存储的近似最小变量空间;基于最近相邻策略设计实例归类标准及其算法,通过指定归类标准值达到调整顾客需求模板中实例分类的目的,提高推理决策的准确性。     

基于交叉覆盖算法的改进算法-最近邻交叉覆盖算法

交叉覆盖算法分类时着重在于两类的交界部分,混杂在另外一类中往往无助于提高分类器的效率,反而会增加分类器的计算负担。本文提出一种基于交叉覆盖算法的最近邻交叉覆盖算法(NN-ACA):对进行训练的原始样本数据进行预处理,删除这些不同类的最近邻点,得到精简后的样本集,再对该样本集使用交叉覆盖算法。文章在介绍算法的同时,给出了相关实验数据,并对其和SVM进行了讨论,结果表明NN-ACA在一定的样本规模表现了速度和分类正确性上的优越性。     

推荐系统中物品召回技术的研究进展

信息技术的快速发展导致信息过载.推荐系统是解决信息过载最有效的方式之一.近年来,深度学习的快速发展也带动了推荐系统的进步,各种深度推荐算法层出不穷.然而由于候选物品数量巨大且用户兴趣动态变化,深度推荐算法的推荐复杂度巨大,难以在实际系统中单独使用.在深度推荐技术发展的同时,物品召回技术(也称近似搜索技术)也有了较大的发展与进步.本文先介绍基于距离最小化的物品召回的研究进展,再从向量索引、局部敏感哈希、哈希学习、向量量化四个方面来深入探讨基于内积最大化的物品召回技术的研究进展.     

数据挖掘中两种简单分类算法的比较

分类是一类重要的数据挖掘问题,它的一般过程是先根据样本数据利用一定的分类算法得到分类规则,再依据该规则对新的数据进行类别的划分。文章详细介绍了两种简单但有效的分类方法：基于最小二乘法的线性分类器和k-最近邻分类器。通过对这两种分类器的比较,发现线性分类器计算简便、拟合具有低方差,适合处理类别之间相互重叠的区域比较小的数据。KNN分类器分类灵活,拟合偏差比较小,由于计算量比较大,该算法更适合于类别界限不是很明显,数据之间交叉或重叠比较多的数据集。     

基于相关反馈的高维图像检索方法

传统索引方法在高维情况下会面临维数灾难问题,基于向量近似的索引方法是有效的高维检索方法．对向量近似方法中k近邻搜索算法加以改进,应用到基于相关反馈的交互式图像检索系统中．根据反馈过程前后的距离变化特性,在进行k近邻搜索过程中,将上轮次的查询结果和用户反馈信息用作过滤信息,可减少特征向量的访问数量．在大容量真实图像数据库上的实验表明,将新算法应用干相关反馈过程的图像检索中,可提高k近邻搜索速度．     

在网格计算机上所有最近邻近点的算法

给出了在网络结构的计算机上求平面点集的所有最近邻近点的一个算法，分析了算法的正确性和时间复杂性。     

一种构建严格平衡二叉搜索树的非递归算法

针对传统算法所构造的平衡二叉搜索树并非真正平衡的二叉搜索树,设计了一种构建严格平衡二叉搜索树的非递归算法。改进后的算法具有计算速度快、占用内存小、计算机易于实现等优点。改进算法的核心是生成严格二叉搜索树的先序序列,提出了对升序序列的进行二分得到严格二叉搜索树的先序序列,讨论并给出了构建严格二叉搜索树的快速算法,该算法充分利用了栈在计算过程中提供的二分信息得到严格二叉搜索树的先序序列,该算法与传统算法相比可更快地构建严格二叉搜索树。     

基于DCT和KDA的人脸特征提取新方法

提出了一种新的人脸特征提取方法,该方法采用DCT对人脸图像进行降维和去噪,并通过KDA提取人脸特征。基于该特征,采用NN分类器,对ORL人脸库进行分类识别,仅用28个特征平均识别率就达到97.3%,\"留一法\"识别率为99.5%。仿真结果表明:该方法有效地滤除了人脸图像中的高频干扰信息,明显增强了特征的辨别能力,同时显著地降低了特征维数和计算复杂度。     

改进的共享型最近邻居聚类算法

聚类效果往往依赖于密度和相似度的定义,并且当数据的维增加时,其复杂度也随之增加。该文基于共享型最近邻居聚类算法SNN,提出了一种改进的共享型最近邻居聚类算法RSNN,并将RSNN应用于高速公路交通数据集上,解决了SNN算法在\"去噪\"、孤立点和代表点的判断、聚类效果等方面的不足之处。实验结果表明,RSNN算法比SNN算法在时空数据集上具有更好的聚类效果。     

基于最近邻优先的高效聚类算法

针对高维空间中任意形状的多层次聚类问题，基于“同类相近”的思想，提出并实现了最近邻优先吸收聚类算法NNAF算法。证明了最近邻点搜索定理，基于这一定理又提出了SNN(Searching Nearest Neighbors)算法和GSNN(Grid-based Searching Nearest Neighbors)算法，其时间复杂度为O(n*log(n))，当用扫描图像所得数据时，时间复杂度会降为O(n)；而使用传统的搜索算法，时间复杂度为O(n^2)；提出了实现任意形状高维空间聚类的NNAF算法，时间复杂度为O(n)；提出了MLCA(Multi-layer Cluster Algorithm)算法并证明了两个相关的定理，在改变阈值后重新聚类时，使用MLCA算法可以节省90％以上的时间。实验结果显示，以上算法适应于任意形状的高维空间数据的聚类，可以有效过滤噪声数据，且用户需要的先验知识少、可快速获得各种层次的聚类结果。