DKNNS:面向延迟敏感型应用的可扩展精确分布式K近邻搜索算法研究

为了降低用户访问延迟,延迟敏感型网络应用需要选择合适的邻近服务节点响应用户访问请求.分布式K近邻搜索通过可扩展的选择距任意用户节点邻近的K个服务节点,可以有效满足网络应用延迟优化的目的.已有工作在精确度以及可扩展性等方面存在不足.针对可扩展精确的K近邻搜索问题,文中提出了分布式K近邻搜索方法DKNNS(distributed K nearest neighbor search).DKNNS将大量的服务节点组织为邻近性感知的多级环,通过最远节点搜索机制选择优化的K近邻搜索初始化节点,然后基于回退方式快速的在目标节点邻近区域发现K个近邻.基于理论分析,模拟测试以及真实环境下的部署实验发现,在不同规模的节点集合下,DKNNS算法能够确定近似最优的K个服务节点.且DKNNS的查询延迟,查询开销均显著低于Meridian算法.最后,DKNNS的返回结果相对于Meridian具有较高的稳定性.

基于点云分块的平均密度阈值点云滤波方法

针对传统点云滤波算法在滤除噪声点、离群点的同时会破坏点云的结构,提出一种基于点云分块的平均密度阈值点云滤波方法。该算法首先通过构建八叉树数据结构对点云数据进行体素化,然后以体素分辨率为单位分割点云;之后,对分块后的各块点云数据构建KD-Tree(K-Dimensional tree)进行K近邻搜索,使用欧几里得距离公式计算查询点与近邻点的欧式距离,取最近距离估算点云的平均密度,通过叠加各点云块的平均密度再除以点云块数计算出整个点云数据的平均密度;最后,以整个点云的平均密度作为阈值,若该点的平均密度大于整个点云的平均密度,则滤除该点,反之则保存该点。实验结果表明,相较于统计滤波算法、半径滤波算法,提出的算法在滤波效果上可以有效的去除点云数据中的噪声点和离群点,同时较好的保存点云的细节信息。

基于遗传算法的全局优化检索策略研究

案例检索是基于案例推理(CBR)系统中的关键技术,也是实现智能挖掘系统的关键环节。为了能够进一步提高案例检索效率与准确性,传统研究多是从案例属性和案例库的约减两方面入手,但是没有考虑案例属性权重。提出了一种基于遗传算法的全局优化案例检索模型,该模型利用遗传算法在搜索优化上的优势,对案例库、属性权重、K-NN中的K值进行全局同步优化。最后,通过实验验证了该模型在检索效率与准确性上优于传统模型。

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

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

基于小波变换的多分辨率高维图像检索方法

为解决传统索引方法对高维数据索引时存在的维数灾难问题,提出一种多分辨率向量近似方法.该方法通过小波变换得到一种多分辨率数据结构,在低分辨率上建立低维空间内的距离计算方式.进行近邻搜索时,从低分辨率开始计算候选向量与查询向量之间的距离下限,通过与当前的近邻距离相比较,可以在低分辨率上过滤掉大多数候选向量,避免在高维空间内对其进行距离运算,从而降低运算复杂度.在大型高维图像数据库上的实验表明,该方法可以显著提高向量近似方法的查询效率.

基于聚类和距离的大数据集离群点检测算法

针对已有的基于距离的离群点检测算法在大数据集上扩展性差的问题,提出了基于聚类和距离混合的大数据集离群检测算法。算法第一阶段采用层次聚类和k-means混合的层次k-means算法对数据进行聚类,并按照一个启发式规则对其进行排序。第二阶段在聚类的结果上采用嵌套循环算法进行离群检测,并通过两个剪枝规则进行高效剪枝,减少了离群检测时数据点之间距离计算的次数。理论分析和实验结果证明了算法的可行性和效率。

一种基于改进PointNet++网络的三维手姿估计方法

针对PointNet++网络处理点云局部特征时因分组范围区过大导致计算量较大的问题,提出一种改进的PointNet++网络的三维手姿估计方法。首先对手势点云进行基于Delaunay三角剖分算法与K中位数聚类算法相结合的三角剖分,得到手势点云的三角网格模型,并计算三角网格模型的边长均值;然后以三角网格模型边长均值为半径,对最远点采样(FPS)的采样点进行球查询搜索,再根据搜索到的采样点个数极值对采样点云进行K近邻分组,并最终输入PointNet网络,完成三维手姿的位置估计。改进后的PointNet++网络可以根据不同的点云密度自动调整网络分组区域的局部提取点个数。实验结果表明,在不影响三维手姿估计精度的情况下,该方法提高了PointNet++网络的模型训练速度,并在三维手姿估计中可有效减少特征提取的计算量,使计算机能够更快地捕捉手姿状态。

基于协同过滤算法的高校图书书目推荐系统设计

为了实现高校图书馆借阅系统中的个性化推荐,本研究以图书的借阅持续时长、借阅总次数、续借次数作为兴趣度分量,利用协同过滤算法以及k近邻搜索算法解决借阅关系矩阵稀疏问题,构建基于兴趣度与类型因子的协同过滤推荐模型并设计了五层体系的书目推荐系统,实现了两大分区12个模块的借阅与推荐类功能。经过1 000名学生的实际借阅数据验证,结果表明当近邻个数取60以上且推荐书目为20时推荐效果最佳,为高校图书管理提供了智能化推荐手段。

基于R树的非参数回归交通流预测方法

非参数回归在交通流预测中已得到广泛应用,但实际使用中存在实时性差的缺陷。为提高非参数回归预测速度,提出了使用空间索引结构R树作为模式库的存储结构,并依据R树空间聚类的特点进行K近邻搜索,最后根据搜索到的近邻点估算未来的交通流量。实验结果表明R树结构下的K近邻搜索速度比线性结构下的搜索速度提高了59.6%,但预测精度下降了8.8%。而通过缩小K近邻搜索中的距离上限这一参数,可以提高预测精度。结果表明当2种结构下的距离上限相同且小于0.02时,R树结构下的预测精度平均高于线性结构下11.9%,且搜索速度也平均提高了30.8%。因此,该算法能够在满足预测精度的条件下有效地提高预测速度,为实时短时交通流预测系统提供了1种实现算法。

基于改进密度聚类的用气异常检测

为了更好地从管网系统中挖掘数据信息,科学地计量工商业用气规律,帮助燃气公司对用户异常用气行为进行智能识别,本文提出了一种基于K-近邻距离图和网格搜索法(Grid search)的密度聚类(DBCSAN)算法,结合分段聚合近似表示方法(PAA)在包含噪声的数据集中通过寻找工业燃气数据集的内在分布规律和聚类效果的变化来识别异常点。首先以来自SCADA和智能表具采集的南方某陶瓷工厂日负荷数据为例,使用PAA方法对数据进行降维处理。其次利用改进的DBSCAN算法对案例用户监测时段中的异常数据进行识别。最后将算法在某南方陶瓷行业的325个用户数据上进行了验证。结果表明,算法的平均准确率在90%以上,人工智能算法在燃气领域的应用对于燃气经营企业实现精细化管理、以及达到降本增效的效果具有一定的指导意义。

一种基于高斯映射的三维点云特征线提取方法

提出了一种基于高斯映射的K均值方法,先对目标点进行k近邻搜索,再对由目标点及其近邻点组成的三角形集合的单位法向量进行高斯映射。选用轮廓系数作为聚类有效性指标,确定出最佳聚类数,根据不同曲面聚类分布的规律,得到三维激光点云模型的特征线。对比实验结果表明,所提方法评价指标简单易用且噪声少,可以完整高效地提取出规则点云以及不规则点云的特征线。