XML频繁子树挖掘研究

本文主要研究通过引入滑动窗口模型,提出了面向XML查询数据流的频繁查询子树在线挖掘算法。算法以全局Trie树为数据缓存结构管理和维护缓存池的数据流,采用自下而上、基于前缀等价类的遍历方式快速产生所有带根查询子树和标准查询子树。实验结果表明该算法具有挖掘速度快、内存消耗稳定等特点,可以有效、平稳地处理XML查询数据流。     

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

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

基于音乐基因的乐谱存储模型

本文提出一种基于音乐基因的乐谱存储模型S-MusicXML.将乐谱的存储和处理的基本单位由音阶提升到基因,有利于通过数据挖掘技术对音乐内涵的挖掘和存储.定义了旋律基因等概念,并通过实验进一步分析了挖掘音乐基因比挖掘音乐频繁模式更有优势.     

模式伴随化的基本规则及代价分析

从程序语法结构而不是从具体问题本身出发,提出了基于最小程序行为分解的模式伴随化方法.此方法无论在算法设计上还是在软件实现上均更具普遍性,并具有许多独特的优点.它保留了断点存储技术在减少浮点计算量和降低存储开销方面的优点,同时克服了其仅仅适用于计算过程均匀可分假设的局限性.首先给出了模式伴随化实现的基本规则,详细介绍了基于最小程序行为分解的模式伴随化方法.然后,基于自动微分(AD)基本假设定义了可分程序空间和微分代价函数,得到了两个反映计算微分代价的基本常数σ和μ.在计算过程均匀可分性假设下,讨论了断点存储在浮点计算量和空间存储开销上的最优实现,证明了深度划分在这两个方面同时具有对数复杂性的结论.最后,详细论证了基于最小程序行为分解的模式伴随化方法在浮点计算量和空间存储开销两个方面同时具有过程引用和划分深度依赖性.     

模式伴随化的基本规则及其代价分析

从程序语法结构而不是从具体问题本身出发, 提出了基于最小程序行为分解的模式伴随化方法. 此方法无论在算法设计上还是在软件实现上均更具普遍性, 并具有许多独特的优点. 它保留了断点存储技术在减少浮点计算量和降低存储开销方面的优点, 同时克服了其仅仅适用于计算过程均匀可分假设的局限性. 首先给出了模式伴随化实现的基本规则, 详细介绍了基于最小程序行为分解的模式伴随化方法. 然后, 基于自动微分(AD)基本假设定义了可分程序空间和微分代价函数, 得到了两个反映计算微分代价的基本常数s和m. 在计算过程均匀可分性假设下, 讨论了断点存储在浮点计算量和空间存储开销上的最优实现, 证明了深度划分在这两个方面同时具有对数复杂性的结论. 最后, 详细论证了基于最小程序行为分解的模式伴随化方法在浮点计算量和空间存储开销两个方面同时具有过程引用和划分深度依赖性.     

基于距离的数据流离群点快速检测

提出了快速的基于距离的数据流离群点检测算法.该算法使用滑动窗口模型处理数据流,并利用向量内积不等式进行剪枝,在保证正确性的前提下,显著的提高了执行效率.实验表明,该算法是有效可行的.     

基于边缘检测的 RIP混合插值算法

图像放大是 RIP软件中十分重要的环节,其所用插值算法的优劣直接关系着输出图像的质量与速度.利用 Canny算法提取的边缘信息将低分辨率图像分为平坦区域与边缘区域,对非边缘区域采用双线性插值算法,对边缘区域使用沿4相邻降采样点确定的方向进行插值的特殊算法.经实验证明,与经典插值算法相比,放大图像边缘效果更好,且处理速度更快,可实际用于对图像质量与处理效率要求高的 RIP软件     

采用加权选通信号的扫描自测试方法

提出了一种采用扫描选通信号基于扫描的自测试方法.各扫描链所对应的权值可通过该算法计算出.在这种测试模式下,测试响应的收集可能在任意时钟进行.该方法力求最大限度地提高数字系统内部节点的可控度和可观测度,从而在几乎不带来额外硬件开销的情况下获得尽可能高的故障覆盖率.实验证明,此方法取得了很好的效果.     

基于多服务类比例公平的分组调度算法

研究了同时满足多性能目标的资源管理模型和算法, 基于服务质量模型实现比例公平性原则, 考虑了包括延迟、丢失率在内的服务质量要求及对于综合的多服务类数据流非常重要的公平性问题, 提出了一种分组网络中的比例公平调度模型, 该调度模型综合描述了网络效率、用户QoS要求和系统公平性等多维目标. 分析论证了能有效满足比例公平的调度策略PFS(proportional fairness scheduling), 同时在Linux上实现了该算法. 最后在模拟和实验测量的基础上对PFS调度算法的性能和系统开销进行了分析讨论.     

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

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

一种面向深度数据包检测的索引拆分Bloom过滤器

高速数据包处理迫切需要时空高效的深度数据包检测(DPI),满足其线速处理和低存储空间需求.Trie位图内容分析器(TriBiCa)采用片上位图Trie树来实现元素的最小完美Hash;但是,TriBiCa存在更新开销高和假阳性访问次数多等问题.共享节点快速Hash表(SFHT)采用片上计数Bloom过滤器(CBF)来实现硬件Hash表的快速查找;但是,SFHT存在更新开销高和存储空间需求大等问题.文中提出了一种索引拆分Bloom过滤器(ISBF).ISBF是由片上多组并行CBF和片外元素集构成,其核心思想是:元素的片外索引值被拆分成多组比特,每组比特采用多个片上并行CBF表示元素集;当查询元素时,每组并行CBF产生多个比特值,并合成候选元素的片外索引值.为了降低ISBF的更新开销,文中又提出了懒惰删除(lazyd eletion)算法和空缺插入(vacant insertion)算法,即采用一个片上删除位图,仅在片上并行CBF中删除或插入元素,而不需要调整其他元素的片外索引值.ISBF是一种时空高效的数据结构,其插入、删除和查询操作的平均片外存储器访问次数均为O(1);与TriBiCa和SFHT相比,ISBF在片上存储空间大小上分别减少2b倍和b倍,其中b为索引拆分的比特位数.实验结果表明,ISBF支持快速和存储高效的查找,即显著地减少片外存储器访问次数、处理时间以及片上和片外存储空间需求.     

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

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

面向装配的复杂模型几何及结构轻量化技术研究

复杂三维模型轻量化是节约存储空间、加快处理速度和实现信息隐藏的有效途径.为了快速有效地生成装配体的轻量化模型,提出了一套面向装配的复杂模型轻量化算法框架及处理流程,以零部件抑制、基于特征缝合的模型表面处理和模型整体抽壳等关键技术为手段,实现了复杂装配模型几何与结构的简化表示.该算法已顺利地运用到相关企业的装配设计,模型轻量化效率比较高,为复杂装配模型的网络协同设计和运动仿真等后续应用提供了一种有益的途径.     

基于复杂网络挖掘的用户行为感知机制

用户行为感知是进行网络管理、安全检测以及应用趋势分析的基础.针对基于流量统计特征检测方法具有计算复杂度高和"概念漂移"的缺陷,提出了一种基于用户复杂网络图的用户行为感知机制算法(UBP-CN).算法将用户标识{IP,Port}和用户交互分别抽象为一个点和一条边,构建了用户复杂网络图;应用社团挖掘算法将复杂网络图划分为互不相交的行为子簇,使得用户之间的通信抽象为一种"社会团体";通过定义基于相对熵的"用户行为模式"(UBM),表征了各个子簇背后表现出的行为特性,并使用"UBM+Port"对各个子簇进行标签映射,实现了用户行为的有效感知.仿真结果表明:在不牺牲用户行为分类准确率的前提下,算法不仅能克服"概念漂移"问题,还能有效降低算法的计算复杂度.     

基于改进Otsu和Niblack的图像二值化方法

针对常用的图像二值化方法——全局阈值方法和局部阈值方法存在的对输入图像含有噪声或不均匀光照等情况抵抗能力差以及处理速度慢的不足,提出了一种全局阈值与局部阈值相结合的图像二值化方法.通过在传统Otsu算法中引入类内方差和快速阈值搜索方法,并将其与Niblack算法结合,将图像的每一行看成一个子图,对每一子图使用改进的阈值进行二值化.实验证明,该方法抗噪声能力强,能准确获取图像的目标信息,同时能保持较快的处理速度.     

基于移动设备云迁移的节能决策算法

随着云计算的兴起,云迁移计算开始成为移动设备获取计算资源和降低功耗的有效方式.云迁移的主要想法是将移动终端的复杂任务经由无线网络迁移到云端执行,然后再接收计算结果.然而,无线网络的不稳定性和数据传输的高功耗限制了云迁移计算在移动设备中的应用.不同于已有工作,本文通过引入数据压缩的方法完善了云迁移计算决策模型,并且基于对未来时段网络期望的预测,提出了一种节能迁移计算决策算法——EPVAD.基于实际的3G网络带宽数据和开发测试平台,实验结果显示:EPVAD算法的节能效果较同类算法平均优14.9%,并且算法自身的系统开销可忽略.     

面向操作系统透明的动态内存半虚拟化技术

文中提出了动态半虚拟化方法(dynamic paravirtualization),它借用半虚拟化的方式,降低带硬件辅助支持的全虚拟化系统中的虚拟机陷出数量.在有硬件辅助的全虚拟化虚拟机管理器(VMM)下,由VMM在二进制代码层对客户操作系统(GuestOS)中频繁引起虚拟机陷出的那些热点指令进行替换、消除或合并虚拟机陷出.这种替换对GuestOS而言是透明的,GuestOS并不会感知到这些变动.文中重点关注降低内存虚拟化开销的动态内存半虚拟化方法(DMP).在VMM中实现了一套新的内存虚拟化管理机制,避免使用影子页表进行虚拟内存地址转换,并采用代码植入方法消除内存管理引起的虚拟机陷出.在采用IntelVT的KVM-54版本中实现了动态内存半虚拟化原型系统.实验表明,这种技术可以显著地减少页面中断导致的虚拟机陷出,从而降低其带来的系统开销.动态内存半虚拟化能够不修改GuestOS源代码也可达到半虚拟化的效果.     

四项加权分数Fourier变换在通信系统中的应用研究

本文由四项加权分数Fourier变换的原始定义出发,通过对加权系数矩阵的研究,揭示了加权系数与被加权函数之间的关系,并给出加权系数的多参数表达形式.在此基础上,定义了离散序列的四项加权分数Fourier变换,使其适用于数字通信系统.根据四项加权分数Fourier变换的特性,提出一种基于该变换的调制/解调方法.该方法能够使调制后信号在时域及频域上实部与虚部的统计特性、相位特性发生明显的变化,这一变化可以通过变换参数的调整进行控制.将四项加权分数Fourier变换调整为多参数对信号进行处理,对比单参数处理方法,信号具有更好的抗截获特性.     

医用血管支架非线性扩张过程快速预测方法的研究

建立了血管支架变形影响因子与其变形结果之间的具有高度非线性识别能力的神经网络模型,通过引入学习因子η和动量因子ψ,采用附加动量项的权值修正方法,优化了网络训练算法,从而提高了网络训练速度和系统鲁棒性．结合实例对网络进行训练,并对预测误差进行了统计假设检验,检验结果表明血管支架变形神经网络智能预测结果与非线性有限元分析结果误差均值低于0．03％,训练后的网络能够较好地对血管支架变形进行预测．在此基础上,基于Pro／Toolkit工具,融合血管支架扩张变形神经网络智能预测模型,建立了血管支架力学性能快速评价工具,该系统实用性强、效率高,能大幅缩短血管支架产品开发周期     

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

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