基于神经网络的大规模数据集离群点检测算法

针对传统方法在检测离群点时常因冗余数据的干扰而导致检测用时较长、检测准确率偏低的问题,设计了基于神经网络的大规模数据集离群点检测算法.采用核主成分分析方法对大规模数据集进行降维处理,去除其中存在的冗余数据,利用神经网络在误差函数的基础上实现对离群点的检测.结果表明：该算法的检测时间始终低于0.4 min,且检测准确率始终保持在90%以上,说明该算法能够快速、准确地检测大规模数据集中的离群点.     

近似最小树的哈希Dijkstra算法

为了解决Dijkstra(DK)算法对大规模数据构造最小树时效率不高的问题,结合局部敏感哈希映射(LSH),针对欧氏空间中的样本,提出了一种近似最小树的快速生成算法,即LSHDK算法.该算法通过减少查找近邻点的计算量提高运行速度.计算实验结果表明,当数据规模大于50 000个点时,LSHDK算法比DK算法速度更快且所计算的近似最小树在维数较低时误差非常小(0.00～0.05%),在维数较高时误差通常为0.1%～3.0%.     

一种基于影响区域的CBRkNN查询方法

针对以集合点为发起者的双色反向k最近邻（BRkNN）查询效率问题,提出一种联合查询方法.BRkNN查询查找的是以查询点为k最近邻的点集,双色反向k最近邻联合(CBRkNN)查询查找的是以查询集合中某一设施集合为k最近邻的点集.该方法通过构造查询集合的影响区域来处理CBRkNN查询问题,任何一个物体落入影响区域就是查询结果,反之则不属于查询结果.算法通过画出用户感兴趣设施集合和用户不感兴趣设施集合之间的所有垂直平分线,计算集合中每个设施的优势支配区域,找出被优势支配区域覆盖个数小于k次的凸多边形区域以构造影响区域.在此基础上算法对影响区域进行点包含性查询得到最终结果.通过实验验证了算法在不同的用户规模、用户感兴趣/不感兴趣设施规模和不同的k值条件下都具有较小的时间消耗,从而说明影响区域的使用可以提高查询方法的有效性.     

大规模数据集聚类算法的研究进展

聚类是机器学习领域的一个重要研究方向,在过去几十年间,针对不同类型中小规模数据集聚类算法的研究取得了很大的进展,许多行之有效的算法先后问世.然而,这些算法在处理大规模数据集时,计算复杂度较高,处理高维数据的能力较弱,难以获得令人满意的效果.随着大数据时代的到来,数据的采集和存储变得相对容易和便捷,但数据量也与日俱增,因此,针对各种实际应用的聚类问题应运而生,使得专门针对大规模数据集的聚类算法研究成为当前机器学习领域的重要任务之一.本文以大规模数据集的可计算性为切入点,对目前串行和并行计算环境下专门用于处理大规模数据集的聚类算法进行综述和分析,重点评述了串行计算环境下基于样例选择、增量学习、特征子集和特征转换的聚类算法以及并行计算环境下基于MapReduce、Spark和Storm框架的聚类算法,给出了有关未来大规模数据集聚类算法设计思路与应用前景的思考和讨论,包括基于数据并行和训练过程自动化的聚类算法设计策略及关于社交网络大数据聚类算法的若干理解.     

一种面向大规模二维点集数据的密度聚类算法

针对密度聚类算法无法应用于大规模数据集的问题,提出一种基于划分网格的密度聚类算法(GDSCAN)。将大规模二维点阵图划分为若干网格,网格最短边不小于给定邻域半径,目标点所在网格中任意点的邻域范围不会超过与该网格直接连接的网格,只需在保留网格内寻找邻域点,从而减少计算量;聚类从任意无类别核心点开始,将该点的所有密度可达组成一个簇,以此类推直至所有核心点都有类别;采用提出的GDSCAN算法对不同数量级的二维路网节点进行聚类验证。结果表明,GDSCAN算法可有效解决大规模二维点阵数据集中密度聚类的效率问题,数据量越大,效果越明显,且时间复杂度明显降低。     

基于Mumford-Shah泛函的数字信号去噪算法

针对数字信号处理中的去噪技术问题,利用Mumford-Shah泛函模型的特点进行去噪研究.对应用于图像处理中的二维Mumford-Shah泛函进行简化和降维处理,建立适合于数字信号去噪处理的一维Mumford-Shah泛函,利用能量最小化原理的变分方法导出一个新的去噪处理模型,并提出两种不同的计算算法:区域合并算法和点集扩张算法.在点集扩张算法中利用了统计学中常用的逐步分析方法,保证了处理结果的整体最优性.实验结果表明,两种算法均能有效地消除信号中的噪声,同时精确地提取出信号中的特征点.与Pollak-Willsky算法相比较,新的去噪处理模型能更好的保持信号中的原始特征信息.     

移动云计算环境下的双色反近邻查询算法

研究在移动云计算环境下的最大双色反最近邻查询优化问题,设计新的高效的双色反最近邻查询算法——SILM算法.SILM算法是基于MapReduce框架下的倒排网格索引结构,在Map函数中对分片数据区域使用PCT轮圈算法.对包含在圆区域内或与圆相交的网格的权值记为1,在Reduce函数中使用网格处理算法对分片数据区域进行扫描及合并,对重叠的网格的权值进行累加,输出网格空间中权值最大的网格区域.SILM算法可以在多计算节点上进行分布式计算,更适合于在移动云计算环境下处理大规模并行查询请求.通过实验对SILM算法的效率进行验证.实验结果表明,当数据量较大(数据点个数大于2.0×10~6)时,SILM算法的查询效率是目前解决最优选址问题最佳算法的2倍.     

大规模数据集的多层聚类算法

针对大多谱聚类算法由于计算复杂度高而不适于大规模数据的问题,提出了一种能处理大规模数据集的多层算法。该算法把海量数据根据一定的相关性逐级分组成小数据集,再对分组后的小数据集用谱聚类算法进行聚类,最后利用权核K均值聚类逐级微调,完成全部数据的聚类。通过对UCI数据库中的数据集和图像分割的仿真实验,结果表明该算法的聚类效果很好。     

基于多线程的不确定移动对象连续k近邻查询

针对不确定数据下的大规模连续k近邻查询请求,基于不确定移动对象连续k近邻查询的Rate方法,提出高效的基于多核多线程的并行查询处理框架.根据查询对象的运动速度与相对位置确定查询请求间是否采用查询复用,确定查询复用时的距离边界.提出密度网格扩展的多线程数据分发方法,解决了负载均衡问题,将空间位置相邻的查询请求划分到同一线程,提高查询复用率.通过多线程间的内存共享机制,对计算过的移动对象的预测区域实现计算复用.在大规模交通数据集上验证了所提算法的有效性与查询性能,相比传统的Rate方法,所提并行算法的加速比可达37.     

基于谱聚类的多维数据集异常数据检测方法

针对多维数据集异常数据检测过程中未对多维数据集进行降维处理,导致多维数据集中异常数据检测精度较低、误检率较高、检测时间较长的问题,提出一种基于谱聚类的多维数据集异常数据检测方法。首先,通过拉普拉斯矩阵对多维数据集中的数据进行聚类,初步分类数据;其次,采用局部线性嵌入（LLE）算法对分类后的数据进行降维处理,用特征向量表达高维数据集,去除多维数据集中的冗余信息;最后,将处理后的多维数据集输入到支持向量机模型中,根据回归估计值的计算,完成异常数据的检测。实验结果表明,本文算法进行多维数据集中异常数据检测的精度更高、误检率更低,检测时间较短。     

基于网格索引的Top-k偏好查询算法

目的设计基于网格索引的Top-k偏好查询算法,提高Top-k偏好查询问题的解决效率.方法利用网格索引,采用概念划分的方法,实现基于范围查询和NN查询两种方式的Top-k偏好查询算法.结果通过真实数据集测试结果表明算法能够结合网格索引的优点,与基于R树索引的传统算法相比,在k值不断增加的情况下,查询效率提高了50%,能适应多种空间特征数据对象集合.结论网格索引可以有效处理Top-k偏好查询.     

一种基于双重距离尺度的高维索引结构

为了提高高维数据相似查询的效率,提出一种基于双重距离尺度(DDM)的新型高维索引结构.通过建模得到该DDM的四元组数据结构, 对于高维空间中的数据点,通过k平均聚类算法将数据点聚成若干类，分别计算每个点对应的始点和质心距离,得到基于加权的质心距离, 并将加权的质心距离作为每个数据点的索引键值，且用基于分片的B+树建立索引，得到了该索引的创建算法.高维空间的查询就转变成对一维空间的检索，并研究了数据点的维数、数据量和查询请求参数对查询性能的影响.结果表明, 该DDM能更有效地缩小搜索空间，减少距离计算的开销,特别适合海量高维数据的查询.     

基于低阶条件独立测试的因果网络结构学习方法

基于条件约束的方法可从数据集中学习到变量间的因果关系，并构建出因果网络图.但是在高维数据情况下，基于条件约束方法的缺点是准确率较低且耗时多，从而严重影响此类方法在高维数据中的应用推广.因此，本文提出了一种基于低阶条件独立测试的因果网络结构学习方法，采用低阶条件独立测试来加速构建因果粗糙骨架；利用分裂?合并策略把高维网络分裂成若干个子网络，并进行因果网络结构学习以提高其准确率；最后整合成完整的因果网络图.实验结果均验证了该方法的可行性.     

Frequent item sets mining from high-dimensional dataset based on a novel binary particle swarm optimization

A novel binary particle swarm optimization for frequent item sets mining from high-dimensional dataset(BPSO-HD) was proposed, where two improvements were joined. Firstly, the dimensionality reduction of initial particles was designed to ensure the reasonable initial fitness, and then, the dynamically dimensionality cutting of dataset was built to decrease the search space. Based on four high-dimensional datasets, BPSO-HD was compared with Apriori to test its reliability, and was compared with the ordinary BPSO and quantum swarm evolutionary(QSE) to prove its advantages. The experiments show that the results given by BPSO-HD is reliable and better than the results generated by BPSO and QSE.     

二维矩阵卷积的并行计算方法

为了提高卷积神经网络模型中二维矩阵卷积的计算效率,基于FT2000多核向量处理器研究二维矩阵卷积的并行实现方法.通过使用广播指令将卷积核元素广播至向量寄存器,使用向量LOAD指令加载卷积矩阵行元素,并通过混洗操作将不易并行化的矩阵卷积操作变成可以向量化的乘加操作,实现了通过减少访存、充分复用已取数据的方式来提高算法的执行效率.设计卷积矩阵规模变化、卷积核规模不变和卷积矩阵规模不变、卷积核规模变化2种常用矩阵卷积计算方式,并对比分析不同计算方式对算法执行效率的影响.基于服务器级多核CPU和TI6678进行实验对比,实验结果显示,FT2000比多核CPU及TI6678具有更好的计算优势,相比多核CPU最高可加速11 974倍,相比TI6678可加速21倍.     

大数据环境下的相似重复记录检测方法

大数据环境下的相似重复记录影响数据统计分析结果的准确性,需要过滤相似重复记录.对相似重复记录检测的研究现状做了介绍,在此基础上提出了属性加权的思想,对属性进行加权,并根据属性权值进行排序分组;在对属性加权时,考虑到一些字段的取值是一一对应的关系,权值相同,提出了同义属性的概念,在原数据集的基础上排除部分同义属性来缩减数据集,提高重复数据检测的效率,最后给出了相似重复记录判定的方法.考虑到大数据集给重复记录检测带来的挑战,将大数据集拆分成若干小数据集,充分利用MapReduce机制进行处理,将大数据集按照权重较大的属性取值进行分组,分割成若干个map任务,分别进行处理.实验结果表明,该方法能够有效地提高相似重复记录检测的效率.     

一种基于GPU的快速半全局优化深度图计算方法

由于图像集规模巨大、匹配信息丰富,快速精准多视图立体匹配受计算效率严重制约。针对该问题,提出一种基于GPU的快速半全局优化深度图计算方法。首先,在CPU上通过平面扫描方法计算单张图像初始匹配代价。然后,提出GPU半全局优化并行计算架构,对匹配代价进行聚合,其核心算法为：在全局进行各方向聚合任务流并行以提升众核处理器的利用率;在局部通过将各像素计算任务准确分配到各线程块内实现并行处理,且注重GPU上数据重用以避免带宽限制。再通过GPU滤波剔除突变点进行图像增强。最后,将3维空间点在各深度图像上的一致性作为异常值检测和优化的约束条件。在多组数据集上测试结果显示,该方法计算速度最高为多核CPU系统中开启2线程实现方法的22.41倍,为开启8线程实现方法的9.13倍,且与两者精度相当;与同类深度图计算方法比较结果表明, 该方法在重建过程中加速效果均为其他算法的5倍及以上;通过使用开源点云比较软件在标准测试数据集上与其他算法比较,验证了该方法能有效提高重建结果的精度和完整度。     

改进的单类支持向量机的网络流量检测

单类支持向量机(OCSVM)理论对有限样本、高维空间和不平衡数据集分类有巨大优势,通过使用权重值模拟退火法与动态惯性因子的粒子群算法改进OCSVM的参数选择算法,进行流量分类,使得分类准确率提高了近10%,解决了传统流量分类方法的低准确率和开销大等弊端,对提高网络服务质量、网络管理与控制以及网络安全等领域具有重要意义。     

Data-driven sensor placement for efficient thermal field reconstruction

Complete temperature field estimation from limited local measurements is widely desired in many industrial and scientific applications of thermal engineering. Since the sensor configuration dominates the reconstruction performance, some progress has been made in designing sensor placement methods. But these approaches remain to be improved in terms of both accuracy and efficiency due to the lack of comprehensive schemes and efficient optimization algorithms. In this work, we develop a datadriven sensor placement framework for thermal field reconstruction. Specifically, we first tailor the low-dimensional model from the prior thermal maps to represent the high-dimensional temperature distribution states by virtue of proper orthogonal decomposition technique. Then, on such subspace, a recursive greedy algorithm with determinant maximization as the objective function is developed to optimize the sensor placement configuration. Furthermore, we find that the same sensor configuration can be yielded faster by the standard procedures of column-pivoted QR factorization, which allows concise software implementation with readily available function packages. When the sensor locations are determined, we advocate using the databased closed-form estimator to minimize the reconstruction error. Real-time thermal monitoring on the multi-core processor is employed as the case to demonstrate the effectiveness of the proposed methods for thermal field reconstruction. Extensive evaluations are conducted on simulation or experimental datasets of three processors with different architectures. The results show that our method achieves state-of-the-art reconstruction performance while possessing the lowest computational complexity when compared with the existing methods.     

基于聚类组织协同进化的入侵检测算法

针对组织协同进化分类算法中样本数据集数量较大时对训练样本的学习不充分,分类的效率和准确性不高的问题,提出了一种将聚类融入了组织协同的进化算法.该算法在分析组织协同进化特征的基础上,形成聚类组织协同进化算法,并将此算法应用于入侵检测问题中使得训练样本得到比较充分的学习.通过该算法对KDDCUP99数据集进行仿真对比实验,验证了该算法的有效性.