基于Spark的并行ISOMAP算法

为了实现大数据环境下非线性高维数据的降维,提出了基于Spark的并行ISOMAP算法.在该方法中,为了快速求解大规模矩阵的特征值和特征向量,设计并实现了基于Spark的并行块Davidson方法;同时,针对大规模矩阵计算和传输困难的问题,提出了基于RDD分区的行块式矩阵乘法策略,该策略把每个分区中的矩阵行转换成块矩阵,行块式矩阵可不受map算子对RDD逐条计算的限制,并可以利用Spark中的线性代数库参与矩阵级别的运算.实验结果表明,行块式矩阵乘法策略有效提高了矩阵运算的效率,并行块Davidson方法能够快速求解大规模矩阵特征值和特征向量,有效提高了并行ISOMAP算法的性能,表明并行ISOMAP算法可以适应大数据环境下的降维处理.     

基于Spark的大规模文本KNN并行分类算法

在使用KNN算法进行大规模文本分类,需要处理频繁的迭代运算,针对现有Hadoop平台迭代运算效率较低的问题,本文提出一种基于Spark平台的并行优化KNN算法.主要从3个方面对算法进行优化,首先,对于训练数据集通过剪枝算法控制有效数据的规模,从而减少迭代运算的次数;其次,针对高维数据集采用ID3算法利用信息熵进行属性降维,减少文本相似度的运算量;最后,使用Spark并行计算平台,引入内存计算最大限度地减少了迭代运算的I/O次数,提高处理速度.通过实验,与常用的KNN算法相比,基于Spark的KNN文本并行分类算法在加速比、扩展性等主要性能指标上表现较优,能够较好地满足大规模文本分类的需求.     

基于分治法求解对称三对角矩阵特征问题的MPI/Cilk混合并行算法

对称稠密矩阵特征问题的求解通常转化为三对角矩阵特征问题的求解,基于对称三对角矩阵特征求解的分而治之方法,提出了一种基于消息传递接口(message passing interface,MPI)+Cilk多任务并行模型的混合求解算法,采用进程间数据并行和进程内多线程任务并行的方法,实现了对分而治之算法中分治阶段和合并阶段的多任务划分和动态调度。进程内利用Cilk任务执行的有向无环图模型,解决了线程级并行的数据依赖和饥饿等待等问题,提高了程序的并行性;进程间通过粗粒度计算任务的划分,优化了MPI部分的数据通信流程和负载均衡问题。数值实验表明,混合并行算法在计算性能和可扩展性方面都要优于纯MPI并行算法。     

一种新的软聚类投票法及其并行化实现

聚类集成作为数据挖掘的重要应用工具,得到了广泛的认可和研究.本文在投票法的基础上提出一种新的软聚类投票(VMSC)算法.算法首先求取平均隶属度矩阵,然后进行迭代优化.该算法能够消除噪声点影响,具有很好的稳定性.Spark云计算平台能够高效处理大数据.为了提出的算法处理大数据,在Spark云计算平台上实现并行的VMSC算法.VMSC算法实验用12组UCI数据集进行验证,并与sCSPA、sMCLAs HGBF及SVCE等软聚类算法进行对比.结果表明,VMSC算法对软聚类算法具有较好的集成效果.在Spark云计算平台上对VMSC算法并行实现.实验表明,该算法具有较理想的并行效果,能够有效处理大数据.     

基于GPU加速的全源对最短路径并行算法

针对最短路径算法处理大规模数据集低效的问题，提出了基于图形处理器（Graphics Processing Unit,GPU）加速的全源对最短路径并行算法.首先通过优化矩阵乘法算法实现了在工作组内和组间进行并行运算数据，然后减少了非规则行造成的工作项分支，最后降低了工作项对邻接矩阵计算条带存储资源的访问延时.实验结果表明，与基于AMD Ryzen5 1600X CPU的串行算法、基于开放多处理（Open Multi-Processing, OpenMP）并行算法和基于统一计算设备架构（Compute Unified Device Architecture, CUDA）并行算法相比，最短路径并行算法在开放式计算语言（Open Computing Language, OpenCL）架构下NVIDIA GeForce GTX 1 070计算平台上分别获得了196.35、36.76和2.25倍的加速比，验证了提出的并行优化方法的有效性和性能可移植性.     

一种厄米特矩阵特征值并行求解方法

厄米特矩阵特征值特征向量快速求解是在实际工程中常常会碰到的问题,但大部分基于计算机实现的算法都是利用串行思想进行编程求解,不能满足实时求解需求。本文提出基于FPGA的并行算法来求解本类问题。首先,将厄米特矩阵实数化。其次,通过并行雅克比分解和特征值快速排序来恢复厄米特矩阵的特征值特征向量。最后,通过MATLAB仿真验证了算法的有效性,并通过蒙特卡洛仿真确定了雅克比sweep的迭代次数,同时通过FPGA实现验证了算法的实时性。     

CPU+GPU异构并行的矩阵转置算法研究

针对当前算法优化研究一般局限于单一硬件平台、很难实现在不同平台上高效运行的问题,利用图形处理器(GPU)提出了基于开放式计算语言(OpenCL)的矩阵转置并行算法.通过矩阵子块粗粒度并行、矩阵元素细粒度并行、工作项与数据的空间映射和本地存储器优化方法的应用,使矩阵转置算法在GPU计算平台上的性能提高了12倍.实验结果表明,与基于CPU的串行算法、基于开放多处理(OpenMP)并行算法和基于统一计算设备架构(CUDA)并行算法性能相比,矩阵转置并行算法在OpenCL架构下NVIDIA GPU计算平台上分别获得了12.26,2.23和1.50的加速比.该算法不仅性能高,而且实现了在不同计算平台间的性能移植.     

基于CUBLAS和CUDA的MNF并行算法设计与优化

为实现高光谱影像数据快速降维,基于nVidia的图像处理单元(graphic processing unit,GPU)研究最大噪声分数变换(Maximum Noise Fraction Rotation,MNF Rotation)降维算法的并行设计与优化,通过对加速热点并行优化,择优整合,设计并实现基于CUBLAS(CUDA Basic Linear Algebra Subprograms)库的MNF-L(MNF-on-Library)算法和基于CPU/GPU异构系统的MNF-C(MNF-on-CUDA)算法.实验结果显示MNF-L算法加速11.5~60.6倍不等,MNF-C算法加速效果最好,加速46.5~92.9倍不等.研究结果表明了GPU在高光谱影像线性降维领域的巨大优势.     

流动人口城市融入的复杂性逻辑

为实现高光谱影像数据快速降维,基于nVidia 的图像处理单元(graphic processing unit, GPU)研究最大噪声分数变换（Maximum Noise Fraction Rotation,MNF Rotation）降维算法的并行设计与优化,通过对加速热点并行优化,择优整合,设计并实现基于CUBLAS(CUDA Basic Linear Algebra Subprograms)库的MNF-L（MNF-on-Library）算法和基于CPU/GPU异构系统的MNF-C(MNF-on-CUDA)算法.实验结果显示MNF-L算法加速11.5~60.6倍不等,MNF-C算法加速效果最好,加速46.5~92.9倍不等.研究结果表明了GPU在高光谱影像线性降维领域的巨大优势.     

基于自然梯度的概率主组件分析在线学习算法

对于主组件分析模型,传统方法利用特征值分解的方法求解,其计算复杂度为O(ND~2),其中N表示数据规模,D表示数据的维度.概率主组件分析是从概率的角度理解主组件分析模型,此时可以使用期望最大化算法迭代求解,其计算复杂度为O(NDM),其中M表示选取的维度,对于大规模高维数据可有效提高模型效率.但是,在参数更新过程中,概率主组件模型的期望最大化算法需要遍历整个数据集才能更新一次参数,参数更新较慢,同时该算法很难扩展到大规模数据集.本文提出基于自然梯度的概率主组件分析在线学习算法,通过结合概率主组件分析的自然梯度,实现在线增量学习模型.进一步将降维后的数据通过全连接神经网络进行分类,并通过实验证明,该方法在降维效果及算法运行效率上有明显提高.     

结合PCA的t-SNE算法的并行化实现方法

为了提高大数据环境下高维非线性数据的处理速度和精确度,提出一种结合主成分分析(PCA)的基于t分布的随机近邻嵌入(t-SNE)算法.首先,通过主成分分析法对原始数据进行预处理,去除噪声点;然后,结合t-SNE算法,构建K最邻近(K-NN)图,以表示高维空间中数据的相似关系;最后,在Spark平台上进行并行化运算,并在BREAST CANCER,MNIST和CIFAR-10数据集上进行实验.结果表明:文中算法完成了高维数据至低维空间的有效映射,提升了算法的效率和精确度,可应用于大规模高维数据的降维.     

大数据环境下决策树的研究

传统决策树在中小型数据集的预测分类上表现优秀,但在大数据集的处理上仍然存在效率低下、准确率较低等问题.为了适应大数据集环境,国内外学术界和工业界提出了将决策树与分布式处理平台相结合的分布式决策树算法,面向大数据处理的Hadoop和Spark分布式计算系统的出现,为研究分布式决策树算法提供了新的契机.为此,面向以基于大数据系统的分布式决策树算法为研究对象,从决策树基础算法、大数据平台的分布式并行机制和大数据平台下分布式决策树实现的三个方面进行剖析,以呈现Hadoop和Spark平台下的分布式决策树算法当前研究现状,并分析未来分布式决策树的研究方向.     

Spark上的等值连接优化

等值连接作为数据分析中最常用、代价最高的操作之一,在Spark上的实现和优化与传统并行数据库有很大的差别,传统并行数据仓库中基于数据预划分的连接算法在Spark上难以实现,而目前被广泛采用的Broadcast Join和Repartition Join性能较差,如何提高连接性能成为基于Spark的海量数据分析的关键.本研究将Simi-Join与Partition Join的优势相结合,并基于Spark上的特性提出了一种优化的等值连接算法.代价分析和实验表明本算法比现有基于Spark的数据分析系统中的连接算法性能提升1~2倍.     

基于机群结构的关联规则并行挖掘算法

在比较当前几种并行关联规则挖掘算法的基础上,为了解决CD、FDM、DDM算法的候选集和执行时间方面存在的问题,结合关联规则的性质定理,提出了一种改进的并行关联规则算法IPARM.在无共享的工作站机群上进行性能测试,采用改进并行算法的执行效率提高了,达到了算法优化的目的.     

一种基于并行免疫网络的大数据分类算法

为了解决数据量增加时串行免疫网络算法难以实现大数据处理的问题,提出了并行免疫网络训练和分类模型,并在Spark并行框架下设计了并行免疫网络分类算法.给出了入侵检测大数据背景知识;建立了Ainet并行算法框架,详述了并行免疫网络分类算法步骤;采用cup99入侵检测数据集进行了试验,进而将并行Ainet算法同其他算法做了比较.试验结果表明:较串行Ainet算法,并行Ainet算法训练时间下降了11/12,检测时间降低了19/20,准确率提高了10%,同时检测率提高了5%,而误报率降低了20%,可见并行Ainet算法各方面都取得较好的效果;试验验证了分类效果对训练数据集数量敏感的特点;并行Ainet算法在准确率、检测率和误报率方面优于其他算法,但运行时间较长.     

基于CUDA架构并行算法的带地形AMT二维反演实现与应用

并行计算是提高音频大地电磁（audio-frequency magnetotelluric method,AMT）数据反演效率的有效途径。本文在统一计算设备架构(compute unified device architecture,CUDA) 下开展带地形的AMT数据二维反演并行算法研究,旨在利用GPU强大的计算能力及并行计算技术实现高精度、快速度的AMT数据二维反演。首先利用有限元和自适应正则化反演算法实现AMT数据二维反演的串行化计算;然后在PGI Visual Fortran+ CUDA5.5环境下编写基于CPU+GPU的CUDA并行代码,将正演中的频率循环、反演中的模型灵敏度矩阵计算和反演方程正则化求解部分进行并行化处理;通过不同复杂程度的理论模型正反演模拟验证了该并行算法的有效性和准确性。不同模型和不同模式下的数值模拟结果对比表明,基于CPU+GPU的CUDA并行算法相较于传统的CPU串行算法,在灵敏度矩阵计算和反演方程正则化方面耗时更少,加速比最高可达10倍以上。最后将该并行算法应用于某矿区实测AMT数据的二维反演中,取得了较好的应用效果。     

局部测地距离估计的增量等距特征映射算法

基于经典等距特征映射（ISOMAP）算法易受噪声干扰和邻域大小影响,采用局部测地距离估计输入数据点的初始邻域,并结合增量学习思想,提出一种基于局部测地距离估计的增量ISOMAP算法进行降维,以提高ISOMAP算法的分类能力.人脸识别试验表明,该算法识别性能优越,对噪声和几何形变具有鲁棒性.
     

矩阵特征值问题一种求解方法的并行处理

矩阵特征值问题已成为数值计算中的一个重要组成部分，为了有效求解此类问题，提出了一种求解特征值的算法：基于Jacobi方法，利用非线性方程组的一种并行算法求解特征向量，引入同伦思想，利用插值方法，从而快速囊出问题的具有高精度的解，最后进行了稳定性分析．     

一种新的基于FP_Growth的频繁项目集并行挖掘算法

频繁项目集挖掘用于发现项目之间的关联规则.为了高效求解面向大数据的频繁项目集,本文提出一种新的基于FP_Growth的频繁项目集并行挖掘算法NPFP_Growth(New Parallel algorithm based on FP_Growth),该算法对频繁模式树的存储结构进行改进,基于Map/Reduce并行计算模型,利用HDFS实现数据存储,在各自计算节点上构造局部频繁模式树,求解该局部频繁模式树中每个分支的最长全局频繁项目集;对于全局非频繁项目集,计算其支持数,发送至相应计算节点进行支持度统计,从而以较为简单的算法实现频繁项目集并行挖掘.实验表明,NPFP_Growth算法具有较高的计算效率和良好的可伸缩性.     

基于MATLAB的数字化共轭曲面求解研究

为了实现数字化共轭曲面求解的目的,采用曲线插值替代曲面插值,从离散的数字化曲面得到一个连续的曲面,从而实现了共轭曲面法向量和相对运动速度的求解,在此基础上,提出了基于降维插值求解方法的数字化共轭曲面求解数学模型;运用计算软件MATLAB的强大数值计算和图形显示功能开发了数字化共轭曲面的求解算法,并用V isual C++实现了人机界面和数据的处理.计算实例的结果表明该方法能有效实现数字化共轭曲面求解.