SLSB-forest:高维数据的近似k近邻查询

近似k近邻查询的研究一直受到广泛关注,局部敏感散列(LSH)是解决此问题的主流方法之一.LSH及目前大部分改进版本都会面临以下问题:数据散列以后在桶里分布不均匀;无法准确计算对应参数k的查询范围建立索引.基于此,将支持动态数据索引的LSH和B-tree结合,构建新的SLSB-forest索引结构,使散列桶里的数据维持在一个合理的区间.针对SLSB-forest提出了两种查询算法:快速查找和准确率优先查找,并通过理论和实验证明查找过程中查询范围的动态变化.     

一种高维大数据全k近邻查询算法

全k近邻(all k-nearest neighbor,AkNN)查询,是k近邻查询的一个变型,旨在在一个查询过程中为给定数据集的每个对象确定k个最近邻.提出了一种在Hadoop分布式平台下处理高维大数据的AkNN查询算法.首先使用行条化思想结合p-stable LSH算法将高维数据对象降维,然后结合空间填充曲线Z-order的优良特性,把降维后的数据嵌入一维空间中,接着进行范围查询.整个过程使用MapReduce框架分布式并行处理.实验结果表明,所提出的算法可以高效处理高维大数据的AkNN查询.     

M2LSH:基于LSH的高维数据近似最近邻查找算法

在许多应用中,LSH(Locality Sensitive Hashing)以及各种变体,是解决近似最近邻问题的有效算法之一.虽然这些算法能够很好地处理分布比较均匀的高维数据,但从设计方案来看,都没有针对数据分布不均匀的情况做相应的优化.针对这一问题,本文提出了一种新的基于LSH的解决方案(M2LSH,2 Layers Merging LSH),对于数据分布不均匀的情况依然能得到一个比较好的查询效果.首先,将数据存放到具有计数功能的组合哈希向量表示的哈希桶中,然后通过二次哈希将这些桶号投影到一维空间,在此空间根据各个桶中存放的数据个数合并相邻哈希桶,使得新哈希桶中的数据量能够大致均衡.查询时仅访问有限个哈希桶,就能找到较优结果.本文给出了详细的理论分析,并通过实验验证了M2LSH的性能,不仅能减少访问时间,也可提高结果的正确率.     

散乱数据点的k近邻搜索算法

文章提出了一种基于八叉树的快速k近邻搜索算法，即通过对点集建立包围盒。利用八叉树记录分割过程，从而使近邻点的搜索只局限于采样点所在包围盒及周围的包围盒，并通过剪枝策略，使搜索范围近一步缩小．提高了搜索的速度，并能对噪声点自动删除。     

散乱数据点的k近邻快速搜索算法

提出了一种改进的散乱数据点k近邻搜索算法,该问题是逆向工程曲面重构技术中的关键环节。采用传统分块算法对点云空间进行首次分割,在此基础上估算点云平均点距,并利用平均点距估算结果对点云数据空间重新进行划分。分块结果使得k近邻搜索算法的搜索范围大大缩小,搜索速度明显提高。     

基于网络Voronoi图的道路网络连续k近邻查询

道路网络中的连续查询是查找在一条路径上满足查询条件的对象。它是空间网络数据库中的一种重要查询类型。现提出了道路网络中基于k阶Voronoi图的连续k近邻查询方法，该查询方法用分枝限界的思想动态地创建局部Voronoi图，降低了查询代价。     

基于节点伪近邻的电路板近邻网络排序算法

在运用近邻网络排序集生成边界扫描测试向量方法中,多以网络局部或全局信息进行节点近邻关系排序,导致伪近邻点的识别排序能力较差。该文结合LeaderRank算法引入节点伪近邻作为局部重要性指标,首先利用LeaderRank求得网络节点的全局重要度,然后基于相关邻居关系提出节点伪近邻比计算方法,最后综合LeaderRank的全局重要度值与节点伪近邻性求得总体重要度,从而获得近邻网络重要度排序。采用所提方法和以往近邻排序算法对实际电路板网络模型进行近邻关系排序,对排序结果进行比较,并用SIR传染病模型进行仿真分析。实验结果表明,所提方法能够弥补以往排序算法的不足,从而获得更为精确的排序结果。     

基于相对距离的反k近邻树离群点检测

针对分布复杂且离群类型多样的数据集进行离群检测困难的问题,提出基于相对距离的反k近邻树离群检测方法RKNMOD（Reversed K-Nearest Neighborhood）.首先,将经典欧氏距离、对象局部密度和对象邻域结合,定义了对象的相对距离,能同时有效检出全局和局部离群点.其次,以最小生成树结构为基础,采取最大边切割法以快速分割离群点和离群簇.最后,人工合成数据集和UCI数据集试验均表明,新算法的检测准确率更高,为分布异常且离群类型多样的数据集的离群检测提供了一条有效的新途径.     

基于加权K近邻算法的缺失数据填补研究

针对数据缺失问题,本文在完全随机缺失的前提下,对完整数据集进行不同比例的挖空处理,并使用K近邻算法进行缺失值填补;采用交叉验证法优化K值;最后借用高斯函数,对传统K近邻算法进行加权处理,提出加权K近邻算法.实验结果表明,不论K取值多大,加权K近邻算法填补效果均优于传统K近邻算法;且K=2时,两种算法填补效果达到最佳.     

基于K近邻算法的网络敏感信息过滤方法

面对当前方法受到数据稀疏性影响,导致敏感信息过滤效果差的问题,提出了基于K近邻算法的网络敏感信息过滤方法。以K近邻算法中用到的评分实际数据稀疏度为评判依据,对网络敏感信息进行分类,避免了过滤过程受数据稀疏性的影响。构造敏感信息决策树,在树节点上添加敏感关键词,利用K近邻分类算法计算特征值方差矩阵的权重和累积权重。将计算结果添加到反敏感信息库中,引入时间和主题相关度变量参数计算相似度,通过查找网络上的敏感素材,筛选符合条件的敏感信息。由实验结果可知,该方法平均绝对误差和标准化平均绝对误差与其他方法相比数值最小,分别为0.19和0.20,说明其网络敏感信息过滤效果较好。     

哈德码变换域等均值等方差最近邻矢量量化码字搜索算法

本文提出一种基于哈德码变换的等均值等方差最近邻(HTEENNS)快速矢量量化码字搜索算法.在编码前,该算法预先计算每个码字的哈德码变换,然后根据各码字哈德码变换的第一维系数大小的升序排列对码字进行排序.在编码过程中,首先计算输入矢量的哈德码变换和方差,然后选取与输入矢量哈德码变换的第一维系数最近的码字作为初始匹配码字,然后利用两条有效的删除准则在该码字附近进行上下搜索与输入矢量最近的码字.测试结果表明,本文算法比等均值最近邻搜索算法(ENNS)、等均值等方差最近邻搜索(EENNS)算法和哈德码变换域部分失真搜索算法等算法有效得多.     

等均值等范数最近邻矢量量化码字搜索算法

本文提出了一种等均值等范数最近邻(EENNS)矢量量化码字搜索算法.在编码前,该算法预先计算每个码字的均值和范数,然后根据均值大小的升序排列对码字进行排序.在编码过程中,首先选取与输入矢量均值最近的码字作为初始匹配码字,然后利用两条有效的删除准则在该码字附近进行上下搜索与输入矢量最近的码字.测试结果表明,本文算法比等均值最近邻搜索算法(ENNS)和最近提出的范数排序搜索(NOS)算法有效得多.     

一种运动数据检索的相关反馈算法

本文提出了一种基于RankBoost的运动数据检索相关反馈算法.该算法具有以下二个方面的特点:首先,以KNN-DTW作为RankBoost集成学习的弱排序器,在适应变长多变量时间序列(Variable-Length Multivariate Time Series,VLMTS)数据的同时,利用RankBoost的集成性与高效性解决相关反馈实时性要求与VLMTS数据计算复杂度高的矛盾;其次,以本文提出的最小化排序经验损失和泛化损失风险作为RankBoost集成学习目标,有效地克服了相关反馈小样本学习环境下的过拟合问题.在CMU动作库上的实验结果验证了该方法的有效性.     

面向数据中心网络的分层式故障诊断算法

首次提出一种面向数据中心网络的分层式故障诊断算法---HFD（Hierarchical Fault Diagnosis）算法。算法根据数据中心网络的结构特点,将网络系统分为两个逻辑层。在第一层,通过对“基本单元组”进行多次最简测试,将其划分为“相对故障单元组”与“相对正常单元组”两大类;在第二层,结合本文首次提出的“正-反关联性”思想和笔者曾经提出的“绝对故障基”思想,设计出AD-FAFD算法进行各单元间的相互测试与诊断。仿真实验结果表明,HFD算法在保持良好的诊断精确度的同时,有效降低了时间复杂度。     

基于车辆数据的k近邻联合概率数据关联算法

在交通场景中采用一些预警措施能够有效地减少交通事故发生。例如,对车辆轨迹进行跟踪并预测车辆的驾驶行为,就是一个常用的预警方法。在对车辆进行跟踪的过程中,数据关联是很重要的部分,它可以对车辆的观测点和轨迹进行关联,从而更新车辆的轨迹,完成跟踪过程。在此背景下,提出了一种新的数据关联算法,即k近邻联合概率数据关联算法(k Nearest Neighbor-Joint Probability Data Association,kNN-JPDA)。实验结果表明,该算法能够较好地解决在交通场景下车辆数据的数据关联问题,在精度以及运行效率方面都有所提高。     

主流大数据处理开源架构的分析及对比评测

结合电信增值业务领域中对大数据处理的实际需求,对现有主流的分布式大数据处理架构(Hive、Impala、Spark)的核心进行分析与实测,比较它们在大数据处理过程中的优劣及适用的场景,从而为大数据分析所面临的架构适用性选型提供参考.     

一种用于语音转换的区域最近邻迭代训练算法

针对非对称语音库情况下的语音转换,该文提出一种新的改进的语音转换训练算法ILNCA。与原有的训练算法INCA不一样的是,ILNCA首先利用高斯混合模型(GMM)分别对源、目标语音特征参数空间进行分类。然后根据KullbackLeibler(KL)距离最小原则对源、目标GMM模型的子空间进行匹配,最后利用最近邻准则在相对应的子空间中进行源、目标语音特征参数矢量的对齐。客观测试和主观听觉实验都表明由于该文算法采用了更加精确的矢量对齐方法,能取得比INCA算法更优异的转换性能。     

面向大数据处理的高精度多维计数布鲁姆过滤器

分析了现有多维布鲁姆过滤器查询算法的工作原理和特点,针对大数据处理特点提出了一种基于双射函数的高精度多维计数布鲁姆过滤器(AMD-CBF)查询算法.AMD-CBF中元素表示和查找分两步进行,第1步将元素各属性哈希映射到各自对应的高精度计数布鲁姆过滤器(A-CBF)中;第2步将元素的所有属性通过双射函数转换为一个值来表示元素整体信息,然后将这个值哈希映射到联合计数布鲁姆过滤器中(C-CBF),完成元素整体的表示和查询确认.理论分析和仿真实验结果表明,AMD-CBF能够支持多维集合元素的高效表示和查询及删除,相比同类研究查询假阳性降低明显,查询精度大幅度提高.