一种挖掘最大频繁子图的新算法

如何从大量的图中挖掘出令人感兴趣的子图模式已经成为数据挖掘领域研究的热点之一.由于其内在的计算复杂性,挖掘全部频繁子图非常困难,且得到的频繁子图过多,影响着结果的理解和应用.解决方案之一是挖掘最大频繁子图.在经典的Apriori算法的基础上,提出了一种挖掘最大频繁予图的新算法Apriori-MaxGraph.首先给出了一种新的、用于计算图的邻接矩阵规范编码的结点排序策略,大大降低了求图规范编码的复杂度,并可以加速子图规范编码序列匹配的速度.其次,针对最大频繁子图,对候选子图的生成进行了规范.最后,采用双向搜索与剪枝策略,大大减小了搜索空间,提高了算法的效率,实验结果表明,Apriori-MaxGraph算法具有较高的挖掘效率.     

建立频繁项目集向量的极大频繁项目集挖掘

在分析和研究诸多经典关联规则挖掘算法或最大频繁项目集挖掘算法的基础上,提出了一种新的极大频繁项目集挖掘算法BOFPV_MMFIA算法.该算法引入频繁项目集向量FP-V,将极大频繁项目集的挖掘过程转化为频繁项目集向量FP-V的与运算过程.算法只需扫描数据库一次,克服了Apriori及其相关算法产生大量候选集和需多次扫描数据库的缺点.又不同于BOM算法,挖掘频繁k_项目集时,需要进行 次k个向量的与运算.因此,BOFPV_MMFIA算法的效率明显高于Apriori、DMFIA及BOM算法.     

一种挖掘频繁模式的数据库划分新方法

提出了一种新的数据库划分方法。该方法应用于需要产生候选项的频繁模式的挖掘过程,可以大大减少对数据库的扫描操作,提高数据挖掘效率,特别是对于较长模式的数据挖掘更是如此。该方法是将交易数据库按照交易的长度(或者说模式的长度)划分成若干个子数据库,将等长度的交易划分到同一个子数据库中,这样在获取候选项的支持度时,只需要扫描模式长度大于等于相应候选项长度的子数据库即可,从而减少了对数据库的扫描操作。给出了基于数据库划分的挖掘算法,通过理论推导和实验证明了该方法的有效性。     

基于包含索引的频繁闭序列模式挖掘的新算法

频繁闭序列模式惟一确定全体频繁序列模式,且规模小得多.传统的闭序列模式挖掘算法对每个频繁项目都进行扩展,往往会产生大量的非闭合序列.为解决这一问题,提出了一种新的基于包含索引的频繁闭序列模式挖掘算法,其主要思想是只对闭项集进行扩展,大大减少了非闭合序列的产生.首先,论证了闭序列模式只能由闭项集组成;其次,说明了如何利用包含索引来快速发现闭项集;最后,给出了一种深度优先的挖掘频繁闭序列模式的新算法.实验结果表明,该算法具有较高的效率.     

频繁项目集二次挖掘方法研究

针对关联规则数据挖掘中频繁项目集的二次挖掘问题,提出了一种能够解决当最小支持度发生变化而交易数据库不变情况下进行二次挖掘的改进算法(UMSA)。该算法充分利用频繁项目集的特性,通过新的拼接方法来减少候选项目集的生成,在扫描交易数据库确定k维频繁项目集时,采用在交易数据库中剔除无用的交易,达到不断减小交易数据库规模的目的,克服了一些算法中存在的漏采现象,并在一定程度上解决了非确定性问题。通过举例说明该算法的执行过程及其算法的正确性和有效性,并对其性能进行了分析。     

在线挖掘数据流滑动窗口中最大频繁项集

相对于频繁项集,最大频繁项集的数目较少,挖掘最大频繁项集的算法具有较高的时空效率.提出了一种新的基于文法顺序FP-Tree的最大频繁项集单遍挖掘算法FPMFI-DS.该算法采用了一种混合搜索空间项顺序策略,并利用我们所提出的一种新的剪枝技术-"子集等价剪枝技术",有效缩小搜索空间的大小.基于该算法,提出了一种能够在线更新挖掘数据流滑动窗口中最大频繁项集的算法FPMFI-DS+.FPMFI-DS+算法能够在任意时刻都维护数据流当前窗口中的最大频繁项集.仿真实验表明,FPMFI-DS算法的效率接近于多遍挖掘算法FPMax*,并具有良好的可扩展性,FPMFI-DS+算法更新挖掘速度快.     

基于数据流频繁子图挖掘的可疑金融交易动态识别

目前,我国基于交易上报制度和静态数据挖掘的可疑金融交易识别方法存在着监测覆盖面窄、识别时效性差两大瓶颈问题。一种可行的改进是在现有方法中引入对可疑金融交易的动态识别,其中需解决的关键问题是如何及时有效地从大规模动态数据集中发现相应的可疑交易特征。设计一种基于数据流频繁子图挖掘的可疑关联特征动态识别算法,并用实验证明该算法的可行性和有效性。     

一种基于划分的带项目约束的频繁项集挖掘算法

为提高关联规则挖掘算法的效率及其对大型数据集的适应性,提出了基于划分的带项目约束的频繁项集挖掘算法Partition CHS Miner。算法按照约束条件裁减数据集,并采用基于约束的超结构CHS(con-straint-based hyper-structure)存储数据。对大型数据集,先将其划分为多个不相交的数据子集,使子集的大小适合主存,然后在子集上采用基于超结构的带项目约束的挖掘算法挖掘出局部频繁项集,最后合并所有子集中的频繁项集形成全局的带约束的候选项集,计算出全局频繁项集。实验证明了算法的有效性。     

基于兴趣度的数据流频繁模式散列挖掘算法

频繁模式挖掘是很多数据流挖掘工作的基础.现有算法虽然能够有效的在数据流中挖掘近似的频繁模式, 但是由于数据流数据的不确定性、连续性以及海量性, 始终不能有效的将算法的时间效率和空间效率控制在一个可以接受的范围内. 本文通过使用散列表作为概要数据的存储结构, 并引入关联规则兴趣度的概念, 提出了数据流频繁模式挖掘算法MIFS-HT(mining interesting frequent itemsets with hash table), 不仅有效降低现有算法的时空复杂度, 同时提高了算法的应用价值. 最后, 实验结果表明: MIFS-HT是一种高效的数据流频繁模式挖掘算法, 其性能优于FP-Stream、Lossy Counting等算法, 并且挖掘结果更具有现实意义.     

在线挖掘数据流滑动窗口中频繁闭项集

在线挖掘滑动窗口中的频繁闭项集是一类重要的数据流挖掘问题.提出了一种新的频繁闭项集挖掘算法FPCFI-DS.该算法能够在有限的存储空间中高速挖掘数据流滑动窗口中的频繁闭项集,并且能够在任意时刻维护当前窗口中精确的频繁闭项集.对于第一个窗口中的数据,FPCFI-DS算法采用单遍过程FPCFI进行挖掘,挖掘结果被保存于一棵全局闭项集树GCT中.当窗口向前滑动时,FPCFI-DS算法采用更新挖掘方式快速挖掘出当前窗口中的频繁闭项集.实验结果表明,FPCFI-DS算法的空间效率和时间效率都显著优于同类经典算法Moment.     

基于混沌自适应烟花算法的雷达信号盲源分离

针对传统独立成分分析(independent component analysis, ICA)方法存在收敛速度慢、分离性能不高的问题,将混沌映射策略与自适应爆炸半径相结合,提出一种基于混沌自适应烟花算法(chaotic adaptive fireworks algorithm, CAFWA)的盲源分离(blind source separation, BSS)方法,并应用于雷达辐射源混合信号分选问题。混沌映射策略可以将初始值在解空间内分布更加均匀,爆炸半径能够根据适应度的优劣自适应改变,保证了所提算法局部搜索的精度,满足了全局搜索的多样性。实验结果表明所提算法可以在无噪和有噪情况下均能很好地分选观测信号,而且具有比传统算法更快的收敛速度和更优异的分选性能。     

基于混沌自适应烟花算法的雷达信号盲源分离

针对传统独立成分分析(independent component analysis, ICA)方法存在收敛速度慢、分离性能不高的问题,将混沌映射策略与自适应爆炸半径相结合,提出一种基于混沌自适应烟花算法(chaotic adaptive fireworks algorithm, CAFWA)的盲源分离(blind source separation, BSS)方法,并应用于雷达辐射源混合信号分选问题。混沌映射策略可以将初始值在解空间内分布更加均匀,爆炸半径能够根据适应度的优劣自适应改变,保证了所提算法局部搜索的精度,满足了全局搜索的多样性。实验结果表明所提算法可以在无噪和有噪情况下均能很好地分选观测信号,而且具有比传统算法更快的收敛速度和更优异的分选性能。     

基于双种群协同进化的QoS全局最优

针对服务质量（quality of service, QoS）全局最优Web服务选择问题,提出了一种双种群协同进化QoS全局最优Web服务选择算法。算法在多目标离散粒子群算法基础上设计一种双种群协同进化框架以同步进行非支配排序和精英粒子保留,并定义了一种新的离散粒子位置更新算子。同时为保证粒子的多样性和算法的全局收敛能力,算法采用基于距离的粒子多样性度量算子、基于适应值排序的粒子选择算法和基于轮盘赌的全局最优解选择策略。仿真实验结果表明该算法能同时优化多个目标,并得到一组满足约束的Pareto最优解,且具有较好的性能和鲁棒性,解集的质量和分布也优于非支配排序遗传（nondominated sorting genetic algorithm,NSGA）算法的改进算法NSGA-Ⅱ,能有效解决QoS全局最优的Web服务选择问题。     

基于模糊约束的军事物资配送多目标路径优化

针对带模糊时间窗口、模糊运输费用以及模糊运输风险的多目标军事物资运输问题,利用模糊期望理论,建立了带模糊约束问题的多目标运输路径优化模型,并利用改进的多目标量子遗传算法求解该模型,算法中采用量子比特编码,引入非支配排序和精英保留策略,防止算法陷入局部最优。仿真实验结果表明,建立的模型合理、算法有效,在军事物资配送问题中具有一定的实用价值,与传统的多目标遗传算法相比较,利用改进的多目标量子遗传算法求解该问题,收敛速度更快。     

改进人工鱼群算法在外汇预测和投资组合中的应用

人工鱼群算法具有良好的全局搜索能力和自适应能力,在解决投资组合问题上有较好的应用前景.本文通过改进人工鱼群算法,分别对汇率预测和外汇投资组合双目标优化两部分进行研究.首先利用基于平均距离视野的人工鱼群优化的支持向量回归机算法对汇率进行短期预测,提高了外汇预期收益率的准确性.然后建立外汇投资组合双目标模型,通过借鉴带精英策略的快速非支配排序遗传算法(non-dominated sorting genetic algorithm-Ⅱ,NSGA-Ⅱ)的思想,提出基于Pareto排序理论的双目标非支配排序人工鱼群算法(non-dominated sorting artificial fish swarm algorithm,NSAFSA).实证分析表明该算法在求解外汇投资组合方案时,获得的Pareto前沿比NSGA-II的结果分布更均匀,多样性更好.最后对NSAFSA算法进一步改进,通过两次剪枝策略提高了解的质量,并给出了可供选择的最优外汇投资组合方案.研究结果表明人工鱼群算法可以对汇率预测和外汇投资组合提供重要参考,在外汇市场中具有较大的应用潜力.     

基于映射关联规则算法的业务流程重组关键成功因素识别

试图采用关键成功因素管理方法来研究业务流程重组(BPR)的实施, 在总结国内外学者对BPR关键成功因素研究的基础上, 根据中国的实际情况, 采用系统的思考方法, 全面考虑与流程相关的其它组织要素的变革因素, 提出了中国企业业务流程重组的关键成功因素: 企业战略管理、业务流程管理、信息技术支撑、组织结构变革、企业人员管理和企业文化管理. 在实证方法方面, 提出了一种基于映射的关联规则改进算法(MBAR), 该算法只需要经过一次数据库扫描, 就能够得到所有存在数据库中的大项集, 并应用于挖掘业务流程重组关键成功因素对BPR项目成功的影响, 得出一些有意义的关联规则, 例如: 企业战略管理Λ信息技术支撑Λ人员管理→BPR项目的成功(支持度0.614, 可信度0.706).     

SOC光刻仿真3D实时显示方法研究

光刻仿真是SOC(System On Chip)光刻工艺的重要环节,为了实现仿真数据3D可视化,在光刻仿真程序SPLAT(Simulation of Projection Lens Aberrations via TCCs)基础上,提出了自动排序算法对SPLAT输出数据进行重新排列以便三维建模,建立了光照强度与深度转换模型,将光照强度数值转变为3D可视化的深度数据,论文最后设计了3D实时图形仿真程序并进行了实验。实验证明了自动排序算法以及转换模型的正确性和先进性,为超大规模SOC数据的3D交互式实时显示奠定了基础。     

一种Frank码脉压信号的检测与参数估计方法

针对低截获概率(LPI)雷达中常用的一类多相编码(polyphase codes)信号(Frank码,P1,P3,P4码)的截获问题,研究了基于Radon-Wigner变换(RWT)的检测与参数估计方法。该方法利用这类多相编码信号具有与线性调频(LFM)信号相似的Wigner-Ville分布(WVD)的特性,通过Radon变换提取信号特征,同时实现信号的检测和参数估计。给出了应用该算法的具体步骤,分析了算法性能。以Frank码信号为例进行的仿真证明了该方法用于多相编码信号的联合检测与参数估计的有效性。     

基于多目标优化算法的多无人机协同航迹规划

多无人机协同航迹规划是无人机协同作战的关键技术之一。本文提出的一种针对多无人机协同航迹规划的多目标优化算法,即协同非支配排序进化算法(cooperated non dominated sorting genetic algorithms II,CO-NSGA II),针对多架无人机的航迹距离、安全性、时间以及空间的协同性进行规划。运用多目标优化算法,克服了传统航迹规划中需要为各目标函数取权值的不足,并且可以生成多组可供选择的解。同时引入协同进化策略,将各无人机的航迹规划视作子种群,各子种群间进行合作,子种群内采用非支配排序进化算法(non-dominated sorting genetic algorithms II,NSGA II)进行独立优化。考虑到各机间的协同约束,用时间空间协同系数替代传统算法中的“拥挤距离”参数。仿真结果表明通过本文算法能够有效实现多无人机协同航迹规划。