一种基于有效修剪的最大频繁项集挖掘算法

对关联挖掘中的最大频繁项集挖掘问题进行了研究,提出了一种基于项集格修剪机制的最大频繁项集挖掘算法.采用项集格生成树的数据结构,将最大频繁项集挖掘过程转化为对项集格生成树进行深度优先搜索获取所有最大频繁节点的过程. 其中提高算法效率的一个重要措施是在遍历项集格生成树的过程中对生成树进行修剪.给出了项集格生成树的三个性质,并在此基础上提出了直接超集修剪、间接超集修剪与事务集等价修剪三种修剪机制,尽可能忽略非频繁节点及其所生成的扩展节点以减少遍历的节点数目.试验结果表明,三种修剪机制都能够有效地减少搜索空间,其中事务集等价修剪机制的效果最好,算法的性能与输入数据集的稠密程度相关.      

数据流频繁闭集的在线挖掘

基于算法LossyCounting,提出了数据流频繁闭集的在线挖掘算法LC_Closed(LossyCounting_Closed).设计了基于前缀树的频繁闭集压缩存储结构CI-forest(ClosedItemsets-forest),利用该数据结构可以快速的插入和查询闭集模式,且在处理新的事务数据时能够快速定位相关的历史闭集模式.该算法采用在线的处理方式,提高了算法的实时性.实验的结果证明该算法是有效的.      

LALR(1)分析器快速生成

根据LR(0)自动机的构造理论及Deremer和Pennello的LALR(1)向前看符号集计算公式,提出求解公式中的lookback关系和includes关系的高效算法. 研究过程表明,LR(0)项目集闭包计算和项目集的查找是LR(0)分析器构造过程中的主要性能瓶颈.对这两个计算过程给出了高效的数据结构和算法设计,实现了LALR(1)分析器的快速生成.系统实现及实验数据表明,LALR(1)分析器的生成速度超过了自由软件基金会的LALR(1)分析器生成器Bison.      

基于参数矩阵计算全体极小碰集的方法

极小碰集计算是基于模型诊断的关键步骤之一.针对参数化求解方法的局限性,以及大型系统诊断中由于状态空间规模增加导致诊断能力下降甚至无法诊断等问题,研究了一种非参数化极小碰集求解算法M-MHS(Matrix-based Minimal Hitting Set)算法.该算法利用参数矩阵描述元素与集合的关系,通过矩阵分解将原始问题逐步分解为多个子问题,并采用有效的剪枝规则避免对无解子问题的计算.仿真结果表明:该算法能够计算全体极小碰集,且在进行较大规模碰集计算时性能优于HSSE(Hitting Set-Set Enumeration)算法和去参数化后的BNB-HSSE(Branch and Bound-HSSE)算法,并对不同规律数据能够维持性能稳定,从而为大型系统基于模型诊断提供了可行方法.     

基于树模型机器学习方法的GNSS-R海面风速反演

GNSS-R是基于GNSS卫星反射信号的一种新技术.GNSS-R技术可以运用到海面风场反演中，传统的GNSS-R技术反演海面风场主要有波形匹配和经验函数两种方法，风速反演精度约为2m·s-1.波形匹配方法耗时多，计算量大；经验函数方法通常只使用少量物理观测量，会造成信息浪费，损失一定的反演精度.为了提高海面风速的反演精度，引入机器学习领域常用的树模型算法决策树、随机森林、GBDT等对海面风速进行预测.利用GNSS-R与ECMWF数据构成训练集和验证集，训练集用于模型学习，验证集用于检验模型的反演效果.实验结果显示，决策树和随机森林预测误差约为0.6m·s-1，GBDT等算法的预测误差约为2m·s-1，满足风速反演要求.与GNSS-R传统反演方法相比，机器学习树模型算法效果更好，在验证集上表现稳定且误差较小.因此，可以将机器学习树模型算法运用到海面风速反演中.      

一种有效压缩频繁模式挖掘的算法

频繁模式挖掘的研究最近致力于在一个合理的容错范围内寻找有代表性的模式来压缩庞大的挖掘结果集.一种新型启发式算法AMSA(Approximating Mining based Simulated Annealing)被提出,其采用了模拟退火思想来保证有效性和压缩的质量.依据FIMI(Frequent Itemset Mining Implementations Repository)提供的公用数据集进行的实验结果也证明了这一结论.通过与FPclose算法和RPglobal算法分别进行了性能的比较,AMSA挖掘的结果集规模小于FPclose算法和RPglobal算法得到的结果集规模,特别是当支持度阈值很低时,RPglobal不可在合理时间内产生结果集,AMSA却可在合理时间内得出较精准的结果集.     

具有容错特性的两层数据流聚类方法

提出一种具有容错能力的进化数据流聚类算法FTGDStream (Fault-Tolerant Grid-Density Clustering over Data Stream),通过在聚类过程中引入适当的松弛条件,从而在含有噪声的真实世界数据中获取更加泛化的有用知识.首先利用基于相似性度量和小波技术的HLSFTS (Hierarchical Lifting Scheme Fault-Tolerant Synopses)层次概要数据结构实现在线微聚类过程,然后采用基于网格密度的聚类算法实现离线宏聚类过程.在线算法所构造的小波概要数据结构对原始数据的高压缩率降低了离线网格密度聚类算法的计算负载,提高了二层数据流聚类算法的效率.在UCI数据集上的仿真实验结果表明,FTGDStream算法可以聚类任意空间形状的数据并且适用于高维数据流环境,是一种具有容错能力的高效数据流聚类算法.     

一种XML相似重复数据的清理方法研究

针对半结构化数据XML在数据清理中的重要性,研究了如何清理XML相似重复数据,主要工作有:提出一种有效的XML相似重复数据清理方法,该方法具有较强的适应性,任何XML相似检测算法都适用于此;给出一种基于树编辑距离的相似检测算法,该算法能有效地检测XML相似重复数据;采用树编辑距离的上下限优化基于树编辑距离的相似检测算法,避免了不必要的树编辑距离计算,降低了相似检测计算的复杂度,提高了运算效率.此工作为研究XML相似重复数据清理打下基础.      

R*-树结点自适应聚类分簇算法

为提高逆向工程中点云、三角网格等数据的索引效率,提出一种R^*-树结点自适应聚类分簇算法,采用均匀分布数据作为参考点集,基于间隙统计法及k-均值算法获得使结点相似度之和开始收敛的自然簇数,进而实现R^*-树的结点自适应聚类分簇.实验证明,该算法可实现各类复杂几何对象的R^*-树结点分簇问题,并能降低R^*-树结点分簇的参数依赖性,减少结点重合度,提高R^*-树空间数据查询效率.     

UKF参数估计在三体Lambert问题中的应用

为了快速精确地求解三体Lambert问题,提出了一种新的基于无损卡尔曼滤波(UKF)参数估计的数值求解算法,该算法由初值猜测和精确解求解两部分组成.首先,基于地月系统二体模型,通过简单迭代求解三体Lambert问题的初值.然后,将三体Lambert问题对应的两点边值问题转化为参数估计问题,通过UKF滤波算法求解,可得到收敛的精确解.该算法是基于概率估计理论的,不仅避免了传统数值方法推导相关梯度矩阵的复杂性,而且降低了三体Lambert问题对初值精确度的要求,从而显著降低了三体Lambert问题求解的难度.数值仿真表明,该方法求解效率较高,具有良好的鲁棒性,与微分修正算法、二阶微分修正算法对比具有更大的收敛域.      

基于多最小支持度的加权关联规则挖掘算法

针对交易数据库中数据项重要性不同的现象,提出了新的加权关联规则模型,并基于该模型设计了一个基于多最小支持度的加权关联规则挖掘新算法,允许用户设定多个最小支持度,为数据项设置不同的权重,从而解决数据项的重要性各不相同且出现频率不均匀的问题,发现更多有趣的规则.理论证明了相关性质,并实验验证了算法的有效性.      

基于前缀树的数据流容错概要结构构造

应用于数据流环境的数据挖掘算法应首要考虑算法的时空复杂性,而要实现消耗巨大计算资源的容错模式挖掘则更要专注于算法的效率.容错模式挖掘是为了从被噪声干扰的真实世界数据中获取允许一定程度错配的、更加泛化的有用知识.提出一种新的单遍历、高压缩的容错前缀树形概要结构DSFT-tree(Data Stream Fault-Tolerant Frequent Pattern Tree),用来捕捉最近到达的数据流中的数据元素,并且能够高效移除过期数据,实现最大限度地降低计算资源消耗.利用滑动窗指针和位向量表达法实现容错树形概要结构的高效重构,并进一步基于滑动窗口技术实现了数据流环境下的容错频繁项挖掘.实验采用IBM数据发生器产生事务数据,在合理时间内最终挖掘频繁项的数量为FP-stream算法的1.5倍.      

Ad Hoc网络中一种新的能量优化多播路由算法

探讨了Ad Hoc网络中能量优化的多播路由问题.在一次多播会话中节点功率不变的假设前提下,分析了NJT(Node-Join-Tree)算法,针对NJT算法所生成的多播树中可能存在冗余发送节点的问题,提出了一种新的能量优化多播路由算法——RMT(Refine-Multi-cast-Tree)算法,给出了RMT算法的复杂性分析,并设计了RMT算法的分布式实现方案.RMT算法在已有多播树中进行本地搜索,寻找是否存在冗余的发送节点,若存在冗余发送节点则将其从多播树发送节点集合中删除,重构多播树,从而达到减少多播树能量消耗的目的,生成能量更优的多播树.仿真实验表明RMT算法性能优于NJT算法.     

基于ICA和BP神经网络相结合的掌纹识别

提出了一种基于独立成分分析(ICA,Independent Comment Analysis)和多层前馈(BP,Back Propagation)神经网络相结合的方法对掌纹进行识别.首先采用一种新的方法检测角点,得到掌纹图像的不变特征点,根据这些点校正掌纹方向并得到掌纹的感兴趣区域.对该区域采用定点快速ICA算法(FastICA),得到掌纹特征子空间,然后构建BP神经网络,并采用训练样本得到的掌纹特征进行训练,得到合适的权值.对香港理工大学掌纹数据库进行测试,与主成分分析(PCA,Principal Components Analysis)提取特征的方法进行比较,取得了较高的识别率.      

应用关联规则构建质量活动链模型

介绍了作业质量成本的概念,提出了以作业质量成本数据为基础描述质量活动间关联关系的方法,并设定了作业质量成本之间相互影响的规则.着重研究了关联规则挖掘技术,将布尔型关联规则用于质量活动间作用关系的挖掘,并应用Apriori算法,研究了应用作业质量成本数据及其变化趋势构建基于作业质量成本的质量活动链模型的方法.该模型有助于在质量成本预测与分析过程中从经济的角度发现质量管理过程的瓶颈问题,为以质量成本分析为基础,系统地进行质量改进决策提供了有效的方法和手段.      

基于Delaunay三角剖分的全天自主星图识别算法

在地球物理建模中,Delaunay三角剖分因其对给定点集进行三角剖分具有剖分结果唯一性这一重要特点而得到广泛应用.采用Delaunay 剖分这一性质,首次将Delaunay剖分算法应用到星图识别中.利用全天球星图的剖分不变性,采用有界曲面剖分的边界递归法,生成有序且容量小的完备导航星库;利用二维Delaunay三角剖分对视场内恒星星图进行剖分,将其结果进行快速匹配识别.仿真实验结果表明与现有的星图识别算法相比,此算法具有高的识别率,良好的实时性和鲁棒性,且所需导航星库的容量小,检索速度快.     

基于模糊关联分类器的民机超限事件诊断方法

现有的民用飞机超限事件智能诊断模型大多属于“黑盒”模型,不利于分析超限事件发生的原因.为此提出了一种基于模糊关联分类器(FAC,Fuzzy Associative Classifier)的民用飞机超限事件诊断方法.该方法抽取发生超限事件时对应的QAR(Quick Access Recorder)参数快照取值,采用模糊C均值(FCM,Fuzzy C-Means)聚类算法对抽取的QAR参数取值模糊预处理,然后基于Apriori算法生成模糊关联分类规则库,并由遗传算法对其进行裁剪,结合模糊分类推理方法形成FAC.采用B737-800实际样本数据进行了验证.实验结果表明,所提出的FAC能有效诊断超限事件,FAC识别超限事件的错误率与最小二乘支持向量机(LS-SVM,Least Squares Support Vector Machine)模型相当,但其解释性方面优于LS-SVM.