PDMiner:基于云计算的并行分布式数据挖掘工具平台

随着信息技术和互联网的发展,各种信息呈现爆炸性增长,且包含丰富的知识.从海量数据信息中挖掘得到有用的知识仍然是一个挑战性的课题.近几十年来,数据挖掘技术,作为从海量数据信息中挖掘有用信息的关键技术已经引起了广泛的兴趣和研究.但是由于数据规模的增长,以往的很多研究工作并不能有效地处理大规模数据,因此,开发设计或者扩展已有算法使之能处理大规模数据集,已经成为数据挖掘中非常重要的研究课题.近年来,基于云计算的数据挖掘技术研究已经成为一个热点话题,本文中我们研究开发一个基于大规模数据处理平台Hadoop的并行分布式数据挖掘工具平台PDMiner.在PDMiner中,开发实现了各种并行数据挖掘算法,比如数据预处理、关联规则分析以及分类、聚类等算法.实验结果表明,并行分布式数据挖掘工具平台PDMiner中实现的并行算法:1)能够处理大规模数据集,达到TB级别;2)具有很好的加速比性能;3)大大整合利用已有的计算资源,因为这些算法可以在由这些商用机器构建的并行平台上稳定运行,提高了计算资源的利用效率;4)可以有效地应用到实际海量数据挖掘中.此外,在PDMiner中还开发了工作流子系统,提供友好统一的接口界面方便用户定义数据挖掘任务.更重要的是,我们开放了灵活的接口方便用户开发集成新的并行数据挖掘算法.     

关联规则算法优化研究与实现

本文主要针对Apriori算法采用最小支持度和最小信任度阈值来发现知识,而没有考虑交易中数量问题的不足,提出一种快速的基于频繁模式树FP-tree的最大频繁项目集挖掘算法.该算法不需要产生频繁项集,而且只需要扫描事务数据库D一次,从而提高了算法的执行效率.该方法结合大量的实际项目数据进行关联规则挖掘测试发现,不仅能较好地分析非稠密数据,也能处理现实世界中稠密数据. 结果 表明该优化算法可显著降低关联规则挖掘在数据挖掘工作中的时间开销.     

采用内嵌边界方法模拟流体中颗粒运动的并行算法

提出了一种采用内嵌边界方法模拟流体中颗粒运动的并行算法．当计算区域分区并行时,该算法能够很好的处理颗粒穿过亚区域边界时颗粒与流体之间的耦合问题．模拟计算了两维颗粒在密闭方形区域中自由沉降问题来验证该方法的有效性．     

大规模薄膜生长的格子MC模拟并行计算

基于1000×1000个原子的Ti薄膜淀积生长过程的模拟, 在分布式并行系统上提出了区域重叠划分和异步通信的有效并行计算策略, 并运用Monte Carlo方法实现了模拟真实沉积速率下的大规模薄膜生长的并行计算过程, 缩短了薄膜生长模拟计算时间. 实现的并行算法能够模拟比以前粒子数大得多的真实沉积速率下薄膜生长问题, 从而为运用计算机方法模拟薄膜生长提供了有效的手段.     

攻防对抗防空导弹飞行力学建模和计算机仿真研究

提出模块化建模的基本方法,将全系统模型分为进攻模型、防御模型、数据库模型、可视化模型等几部分,它便于实现模型的置换和扩充.在建立正确、合理的攻防对抗飞行力学模型的基础上,计算机仿真采用并行算法和串型算法的任一种方法都可以实现实时仿真.     

基于自适应抽样的超点检测算法

超点是在一个测量时间区间内链接了大量源IP（宿IF）的宿IP（源IF），实时超点检测对网络安全和管理具有重要意义．现有的算法不能控制内存空间的使用和超点的测量精度，论文提出了一个具有自适应抽样功能的超点实时检测算法．该算法采用流抽样保留技术以减少非超点的测量并提高超点的测量精度；设计一个数据流结构维护流记录，并统计补偿Hash映射中产生的冲突；提出一个基于不等概率的自适应策略以维护内存空间．采用实际网络数据将论文的算法和其他算法进行分析比较，实验和数学分析表明论文算法在资源可控性、测量精度等方面优于现有的其他算法．     

星敏感器星点聚类提取方法

星敏感器现有的星点提取方法运算时间长、存储需求大,从而限制星敏感器姿态初始捕获时间、轻小化等性能指标的提高.针对以上问题,提出了一种星敏感器星点聚类提取方法.首先,介绍和分析了星点聚类提取方法中的预处理滤波算法和聚类算法;然后,给出了该方法在北京控制工程研究所新研小型星敏感器中的实现方式和实现效果,该星敏感器在探月三期月地高速再入返回飞行器中成功实现了首次在轨飞行实验;最后,通过星敏感器观星实验对星点传统提取方法和星点聚类提取方法进行了比对验证,并通过小型星敏感器在轨飞行实验对星点聚类提取方法进行了在轨验证.实验显示,该方法提取星点所需时间最大约为传统方法的16%,星图存储需求不到传统方法的1%,且星点提取正确,在轨表现良好.结果表明,星敏感器星点聚类提取方法能有效减小星点提取所需时间,不需大容量星图存储器件,且逻辑简单、移植性好,适用于各类光学成像敏感器.     

基于模块双向迭代的电力系统仿真新算法研究

提出了一种基于模块双向迭代的电力系统暂态稳定仿真新算法. 首先将电力网络划分成以树形结构相联的多个子网, 将划分后的电力网络和发电机、励磁系统等元件分别单独处理为计算模块; 由各计算模块联接构成电力系统计算树; 而后通过沿计算树进行的前向简化和后向回代计算来实现电力系统方程的Newton法求解. 该算法有效提高了电力系统方程联立求解的效率, 为大规模电力系统并行仿真的实现提供了新方法. 在新英格兰测试系统和我国华北东北联网系统上对该算法进行了仿真测试, 与商业软件BPA结果进行了比较.     

混合SQP的基于完全学习的粒子群优化算法在电力系统中经济分配问题的应用

电力系统经济负荷分配(ELD)问题是电力系统运行中一个重要的优化问题.此前,多种经典数学逼近方法和启发式搜索算法被用于对该问题进行了求解.但是,这些方法仍然存在两个很重要而未引起足够重视的问题:1)算法的稳定性得不到有效保证;2)算法在大规模ELD问题上的性能仍然不能令人满意.CLPSO是一种新的高效全局优化算法.针对其存在的多样性保持能力强但收敛性不足的问题,文中引入序列二次规划SQP,提出了一种新的混合SQP的CLPSO算法SQP-CLPSO.用其求解多个典型ELD问题,并与多种知名算法进行了对比.实验结果表明,SQP-CLPSO具有优秀的收敛性、多样性和可拓展性,是求解复杂ELD问题的有效算法.     

一种面向深度数据包检测的紧凑型正则表达式匹配算法

深度数据包检测(Deep Packet Inspection,DPI)采用正则表达式匹配算法,将每个数据包内容与一组预定义的特征进行匹配.正则表达式匹配算法是一种多模式特征匹配算法,采用确定型有限自动机(Deterministic Finite Automaton,DFA)表示一组正则表达式特征,实现一次内容扫描可匹配多个特征.基于硬件的正则表达式匹配算法面临存储空间需求大等挑战,即片上嵌入式存储器难以存储日益增长的DFA存储空间需求,从而限制了DPI的性能和可伸缩性.近年来,Smith等人提出了一种基于扩展有限自动机(eXtended Finite Automaton,XFA)的正则表达式匹配算法,即在状态上增加辅助变量和简单操作指令,消除了DFA状态空间爆炸问题,从状态方面减少存储空间需求.为了进一步减少XFA存储空间需求,本文提出了一种基于紧凑型有限自动机(Compact Finite Automaton,CFA)的正则表达式匹配算法,称为紧凑型正则表达式匹配算法.CFA是一种存储高效的有限自动机,即从迁移边方面减少XFA存储空间需求.在CFA构建过程,本文提出了基于优先级的迁移边压缩方法,融合相同目的状态最多的迁移边,从而减少存储空间需求;在CEA匹配过程,本文提出了基于位图的迁移边查找方法,并行查找不同优先级的迁移边子集,从而确保匹配效率.Snort特征规则集的实验结果表明:与XFA相比,CFA在迁移边条数上减少了88.2%,在存储空间大小上减少了83%,在匹配时间上减少了12%.     

并行延时LMS算法

通过将并行处理方法引入延时LMS(DLMS) 算法, 提出一种新的并行延时LMS(PDLMS) 算法. 与DLMS算法相比, PDLMS算法具有更小的延时, 更高的数据吞吐率, 更快的收敛速度, 同时对相关输入具有一定去相关作用. 特别适用于滤波器阶数高, 要求系统收敛速度快的应用场合. 同时它可以直接映射到具有高速、高流水特性的硬件结构中.     

基于总空闲时间增量的无等待流水作业计划优化算法

将NP难的最小化最长完工时间无等待流水作业计划问题等价转化为最小化总空闲时间的问题.分析任务之间的独立性,给出算法基本算子的目标增量性质,通过计算目标增量而不是整个目标函数值来判断新作业计划的优劣,可将算法的时间复杂度降低1阶.提出生成初始作业计划算法,实验分析出迭代构造解和再改进解的有效方法;构造出有效的快速迭代启发式算法FCH(fast composite heuristic).FCH和目前求解该问题的有效算法比较,实验结果表明,FCH接近目前的最好性能,需要最少的计算时间.FCH可为大规模无等待作业计划、实时调度和重调度等问题提供有效方法.     

GPU加速的表意式体模型线绘制算法

现有的体模型线绘制算法采用跟踪随机种子的方式得到特征线,存在严重的时空连续性问题.本文提出一种GPU加速的体模型线绘制算法,能够在每一帧抽取全部的特征线,从而彻底解决绘制中的不连续现象.我们首先提出一种并行的特征线抽取方法,在GPU的几何处理器中计算每个立方体单元中的特征线片段.为了解决可见性判定问题,我们采用splatting的方式生成深度图,取代已有方法中的光线投射方法,获得了明显的性能提升.采用自适应的深度偏移获得满意的可见性检测结果.为了将大量的体数据存储到高速显存中,我们通过剔除无关数据和压缩编码的方式,在不影响结果的前提下显著地减少了存储和带宽消耗.实验结果表明,本文算法能够生成时空连续的线绘制结果,并且绘制速度比已有CPU算法提高一个数量级.     

自适应频域块LMS算法在抵消干扰方面的研究

分析了无线通信系统中自适应滤波算法中的LMS算法,并提出了利用自适应抵消输入信号中的干扰而获取有用信号的在频域实现的干扰抵消方法,该方法基于时域中的数据块最小均方误差LMS算法和该块LMS算法中存在线性相关和线性卷积的过程,通过1/2重叠保留法的快速傅立叶变换FFT,在频域以直接相乘的计算方式实现快速相关和快速卷积,利用自适应滤波器在频域实现LMS算法.通过实验仿真比较可以看出,该频域块LMS算法不仅保证了与时域自适应滤波算法有相同的收敛性,而且由于利用了快速FFT技术,使运算量大大减少.     

带信息反馈的凝聚层次聚类算法

本文针对传统的基于相似性的层次聚类算法存在的两个问题(相似性度量中方向信息的丢失和算法的适应能力弱)提出了一种带有信息反馈的凝聚层次聚类算法.首先将无法预知的复杂数据结构描述成3个基本的结构特征单元,并对其进行建模构建一种相似性度量定义的泛型和一种凝聚的层次聚类算法.在凝聚的层次聚类算法中加入类信息的反馈机制,并在不同阶段对相似性定义的泛型进行具体化,充分利用数据点对之间的方向信息和距离信息进行聚类.该聚类算法主要有两大优势:(i)算法的适应能力较强,不需要假设的前提下可以处理无法预知的复杂数据结构;(ii)算法对噪声具有较强的鲁棒性,在不需要对数据集进行预处理的情况下能够在聚类的过程中识别噪声点或者噪声类.从人工数据和真实数据的试验结果可以看出新算法的优越性能.     

基于Wasserstein距离的在线机器学习算法研究

本文主要研究基于Wasserstein距离的在线机器学习算法,并分别针对分类和回归问题,提出两个鲁棒的在线学习算法.本文首先在特征-标签空间中对Wasserstein距离进行变形,得到了易于处理和计算的变形式.进而,将在线梯度下降(online gradient descent, OGD)算法和Wasserstein距离变形式结合,分别针对在线分类问题和在线回归问题提出了两种具有较好鲁棒性的在线机器学习算法.文章对提出的新算法累积误差值(Regret,后面用Regret指代)进行了分析,证明了算法的Regret与训练轮次T满足O(■)关系.算法的收敛性可基于算法Regret分析得到,可证明在算法训练轮次T趋于无穷时,算法训练出的模型会收敛到理论最优模型.最后,将所提出算法与FTRL(follow-the-regularized-leader)算法、OGD算法、采用批量学习训练方法的机器学习算法进行数值实验对比.在模拟数据集和真实数据集的实验中,所提出在线学习算法准确率、鲁棒性和模型泛化性能均优于FTRL算法和OGD算法;针对大规模数据集时,虽然所提出的在线学习算法准确率与批量学习相关算...     

基于RTP/RTCP协议的音视频同步算法研究

视频和音频是流媒体传输的主要数据,各个媒体流在时间上彼此关联,互相约束.针对多媒体业务传输中出现的音视频不同步问题,提出一种将RTP时间戳映射到RTCP绝对时间NTP轴的方法,建立音视频之间的同步点和同步检测判决准则.通过仿真实验,该算法能够实现音视频的基本同步.     

一种生成渐进动画网格模型的改进算法

在计算机图形学中,动画网格模型被广泛地用来表示时变数据,而模型的渐进网格表示方法经常可以用来加快处理、传输和存储速度.文中提出一种生成渐进动画网格模型的高效方法.该方法使用一种改进的基于曲率的二次误差测量准则来计算边折叠代价,可以有效地保持曲面上更多的局部特征.同时,定义了原始动画序列的变形程度权值,并将其加入到累加的边折叠代价中,这样动画模型中的动作变形特征就得到了有效的保持.最后,对动画序列提出了一种优化算法,可以有效地减少动画输出的视觉跳变,提高相邻帧的时间一致性.实验结果证明,本方法高效、易于实现,并且可以在任意细节层次上生成高质量的渐进动画网格模型.     

基于体绘制的三维交互算法研究

提出了基于体绘制的三维交互算法.该算法将三维对象组织成为树状节点,并利用对象的三维骨架化特征为索引,快速计算三维坐标系中坐标对应的三维对象,从而解决了体绘制中缺乏有效的交互问题,且具有较高的响应速度,可对海量医学影像数据集进行操作.以该架构为基础建立的肝外科辅助手术规划系统,可交互显示肝段、血管等信息,使得医生能更准确的了解组织空间结构和解剖信息,精确的掌握病变组织特性.     

基于单形体几何的高光谱遥感图像解混算法

提出一种新的基于单形体几何的高光谱遥感图像混合像元丰度估计算法.该算法的目标是在已知端元矩阵的基础之上,估计高光谱图像中各个观测像素点中每个端元的丰度.根据凸几何理论,基于线性混合模型的高光谱解混问题可以看成一个凸几何问题,其中端元位于包含整个高光谱数据集的单形体的顶点,而它们对应的重心坐标则可以看作各个观测像素的丰度.提出的方法由3部分组成,分别为基于单形体体积的重心坐标计算方法、距离几何约束问题和基于内点的单形体子空间定位算法.与其他基于单形体几何的算法相比,该方法具有诸多优点.Cayley-Menger矩阵的引入使得欧式空间上的运算转化为距离空间上的运算,在降低运算复杂度的同时很好地兼顾到数据集的几何结构.而且,单形体重心的使用确立了一种快速而精确的判断方法来确定观测像素所属的子空间,进而利用递归的思想得到丰度值.此外,算法核心仅仅涉及观测点与端元之间的距离,而与波段数无关.因此,该算法无须对数据执行降维处理,从而可以避免因数据降维而造成的有用信息的丢失.仿真和实际高光谱数据的实验结果表明,所提出的算法与同类其他优秀的算法如FCLS和SPU相比,具有更高的运算精度,同时在端元数目较小时具有较快的运算速度.