工程科学学报,第39卷,第4期:626633,2017年4月 Chinese Journal of Engineering,Vol.39,No.4:626-633,April 2017 D0:10.13374/j.issn2095-9389.2017.04.019:htp:/journals.ustb.edu.cm 基于关联关系的仿真模型实时智能推荐方法 范国超”,许承东)区,胡春生),宋丹” 1)北京理工大学字航学院,北京1000812)宁夏大学机械工程学院,银川750021 ☒通信作者,E-mail:xucd@bit.edu.cn 摘要当全球导航卫星系统(global navigation satellite system,GNSs)分布式仿真环境中共享的模型数量非常多时,检索模 型和配置仿真任务将成为一个比较复杂的工程.为提高仿真模型选取和仿真任务配置的效率,设计了一套针对GNSS分布式 仿真环境中仿真模型的实时智能推荐方法,方法中首先定义了模型关联关系和接口形状的概念,然后提出了一种条件约束下 的频繁模式树(FPe)结构,并从理论上分析了该结构在检索任务量方面的减少程度,设计并推导了模型关联关系度的计算 方法,以及整套智能推荐方法的运行流程.推荐方法在GNS$分布式仿真环境中进行了仿真验证,仿真结果与传统智能推荐 方法做对比分析,分析结果表明,该方法针对仿真模型推荐时运行时间短,推荐结果准确度高,能够实时为用户推荐合适的 模型. 关键词全球导航卫星系统:分布式仿真:智能推荐:关联关系 分类号TP391.9 Real-time intelligent recommendation method of a simulation model based on incidence relation FAN Guo-chao,XU Cheng-dong,HU Chun-sheng?,SONG Dan School of Aerospace Engineering,Beijing Institute of Technology,Beijing 100081,China School of Mechanical Engineering,Ningxia University.Yinchuan 750021,China Corresponding author,E-mail:xucd@bit.edu.cn ABSTRACT With the availability of a large number of sharing models,model search and task design would be an extremely complex project in the global navigation satellite system (GNSS)-distributed simulation environment(GDSE).For improving the efficiency of model search and task design,a real-time intelligent recommendation method was designed for GDSE.Based on the characteristics of the simulation model,the incidence relation and interface shape of the model were defined in the method and a conditional frequent pattern tree (FP-tree)structure was designed to further improve the retrieval efficiency.The effect of the conditional FP-tree structure was proved theoretically.Then,the calculation method of the model incidence relation degree was proposed and derived based on the Bayesian statistical method.The entire processing of the intelligent recommendation method was designed for implementing it in GDSE.Hence,to check the effect of the real-time intelligent recommendation method,it was implemented in GDSE.Compared with the simulation result of the traditional recommendation method,the model intelligent recommendation method is proved to have a shor- ter running time and a high accuracy on simulation model recommendation.The computing capability and real-time performance are proved through the simulation.It is demonstrated that the intelligent recommendation method is efficient and flexible for GDSE. KEY WORDS global navigation satellite system:distributed simulation:intelligent recommendation:incidence relation 全球导航卫星系统(global navigation satellite sys- tem,GNSS)分布式仿真环境(GNSS distributed simula-- 收稿日期:2016-06-23 基金项目:国家自然科学基金资助项目(61502257,41304031)
工程科学学报,第 39 卷,第 4 期: 626--633,2017 年 4 月 Chinese Journal of Engineering,Vol. 39,No. 4: 626--633,April 2017 DOI: 10. 13374 /j. issn2095--9389. 2017. 04. 019; http: / /journals. ustb. edu. cn 基于关联关系的仿真模型实时智能推荐方法 范国超1) ,许承东1) ,胡春生2) ,宋 丹1) 1) 北京理工大学宇航学院,北京 100081 2) 宁夏大学机械工程学院,银川 750021 通信作者,E-mail: xucd@ bit. edu. cn 摘 要 当全球导航卫星系统( global navigation satellite system,GNSS) 分布式仿真环境中共享的模型数量非常多时,检索模 型和配置仿真任务将成为一个比较复杂的工程. 为提高仿真模型选取和仿真任务配置的效率,设计了一套针对 GNSS 分布式 仿真环境中仿真模型的实时智能推荐方法,方法中首先定义了模型关联关系和接口形状的概念,然后提出了一种条件约束下 的频繁模式树( FP-tree) 结构,并从理论上分析了该结构在检索任务量方面的减少程度,设计并推导了模型关联关系度的计算 方法,以及整套智能推荐方法的运行流程. 推荐方法在 GNSS 分布式仿真环境中进行了仿真验证,仿真结果与传统智能推荐 方法做对比分析,分析结果表明,该方法针对仿真模型推荐时运行时间短,推荐结果准确度高,能够实时为用户推荐合适的 模型. 关键词 全球导航卫星系统; 分布式仿真; 智能推荐; 关联关系 分类号 TP391. 9 收稿日期: 2016--06--23 基金项目: 国家自然科学基金资助项目( 61502257,41304031) Real-time intelligent recommendation method of a simulation model based on incidence relation FAN Guo-chao1) ,XU Cheng-dong1) ,HU Chun-sheng2) ,SONG Dan1) School of Aerospace Engineering,Beijing Institute of Technology,Beijing 100081,China School of Mechanical Engineering,Ningxia University,Yinchuan 750021,China Corresponding author,E-mail: xucd@ bit. edu. cn ABSTRACT With the availability of a large number of sharing models,model search and task design would be an extremely complex project in the global navigation satellite system ( GNSS) -distributed simulation environment ( GDSE) . For improving the efficiency of model search and task design,a real-time intelligent recommendation method was designed for GDSE. Based on the characteristics of the simulation model,the incidence relation and interface shape of the model were defined in the method and a conditional frequent pattern tree ( FP-tree) structure was designed to further improve the retrieval efficiency. The effect of the conditional FP-tree structure was proved theoretically. Then,the calculation method of the model incidence relation degree was proposed and derived based on the Bayesian statistical method. The entire processing of the intelligent recommendation method was designed for implementing it in GDSE. Hence,to check the effect of the real-time intelligent recommendation method,it was implemented in GDSE. Compared with the simulation result of the traditional recommendation method,the model intelligent recommendation method is proved to have a shorter running time and a high accuracy on simulation model recommendation. The computing capability and real-time performance are proved through the simulation. It is demonstrated that the intelligent recommendation method is efficient and flexible for GDSE. KEY WORDS global navigation satellite system; distributed simulation; intelligent recommendation; incidence relation 全球导航卫星系统( global navigation satellite sys- tem,GNSS) 分布式仿真环境( GNSS distributed simula-
范国超等:基于关联关系的仿真模型实时智能推荐方法 ·627 tion environment,GDSE)是最近被提出来的一种GNSS 本文从服务化模型基本性质出发,提出了模型关 仿真环境.该环境在面向互联网的前提下,结合了广 联关系和接口形状的概念,定义并推导了衡量模型关 义云计算(cloud computing,CC)核心理念一“对计 联关系的指标,在关联规则的研究基础上提出了一种 算资源进行共享”n-可和面向服务架构(service oriented 针对GNSS分布式仿真环境中仿真模型的智能推荐方 architecture,SOA)技术s-o,实现了多开发人员或用 法,方法中首先在贝叶斯分析方法的基础上提出了模 户发布并共用仿真模型或资源,达到研究新算法、新设 型关联关系度的计算方法,然后设计了一种条件约束 备和扩展新领域的目的.李伯虎等1在研究中验证 下FP-ree数据存储结构以及推荐方法工作流程,并从 了结合云计算的仿真环境可以有效地组织数据资源、 理论上推理并讨论了该方法中部分工作的任务量等指 模型资源、计算资源和存储资源,进而加速计算过程, 标.最后利用200000组虚拟仿真任务记录数据对方 实现资源共享、资源管理、资源配置、并行计算、协同工 法进行仿真验证,对模型智能推荐方法的各项性能进 作、信息服务和容错迁移.该仿真平台具有高度的共 行测试,并与基于关联规则的数据挖掘方法进行对比 享和重用能力,能够减少重复开发和投资,具备更高的 分析.分析结果表明该方法在针对仿真模型推荐时运 仿真能力.胡春生等在结合云计算的分布式仿真 行时间短,推荐结果准确度高,具有很好的实施效果 环境研究中提出了一种服务化分布式仿真环境的基本 1 模型关联关系和接口形状 构架和实施方法,初步分析了模型管理的相关问题和 研究思路,但并没有完全达到智能化管理的目的.随 不同仿真环境中,仿真模型和仿真任务流程的概 着服务化仿真平台的发展和应用,仿真模型数目会以 念差别很大,因此在定义模型关联关系和接口形状之 指数形式增大,并且应用场景和仿真需求不同,需要构 前,首先明确了这两个概念。模型关联关系和接口形 造的仿真流程的差异也较大,如何在大规模数量的模 状是本文提出的两个概念,仿真平台以模型关联关系 型中迅速找到合适仿真模型是一个十分重要的问题. 和接口形状为基础对仿真模型智能化管理,有助于仿 利用计算机推理自动检索并推送给用户恰当的模型可 真模型智能推荐方法的实现和推荐方法效率的提高 以避免用户多次手动检索模型 1.1仿真模型 日前针对计算机智能推荐方法主要基于数据挖掘 大型仿真系统(包括数学仿真、半物理仿真等)是 技术设计的,包括决策树、聚类、回归启发式方法、神经 对系统级结构或平台的功能和性能上的模拟实现.由 网络/关联规则挖掘等叨,这些方法在大规模数据挖 于整体的数学或结构上的仿真很难直接实现,通常将 掘和分析中具有很好的效果,并且多数方法已经应用 其分解为若干个既相对独立又相互联系的子系统(包 到了推荐系统上,但这些方法针对的推荐系统主要应 含一个或多个功能单元),这种子系统更方便使用数 用领域为图书、文档、电影、商品等-0,被推荐对象 学模型或物理模型表示出来,被用于表示的模型即为 为完全独立的个体,互相基本没有相关关系.GNSS分 仿真模型.不同系统的仿真可能包含相同功能的子系 布式仿真环境中模型之间具有紧密的联系,这种联系 统,即可使用相同的模型参与仿真 使得模型的推荐工作与传统推荐方法有着巨大的差 在GNSS分布式仿真环境中,利用上述思想,用户 别.仿真任务中通常为10个以上模型的集合,使用传 将能够实现部分功能的仿真模型依据接口规则共享到 统数据挖掘方法在仿真任务的大规模数据记录中提取 平台上.在有仿真需求时,根据需求用户可以挑选共 信息两模型间关联关系时准确度会明显降低。仿真模 享的模型组合形成能够实现特定系统功能的仿真 型智能推荐方法的数据检索和挖掘的过程与传统的模 任务. 式也有很大的区别,传统大数据挖掘过程通常是根据 1.2仿真任务流程 一定的支持度或置信度阈值检索出相应的集合得到其 用户在利用GNSS分布式仿真环境构建仿真任务 中元素的关联关系,而模型的智能推荐工作中将先形 时,需要调用仿真模型,配置模型之间的输入与输出关 成候选模型,再依据候选模型检索得到统计结果并排 系,配置完成后形成了一组具有关联关系的模型集合, 序.另外仿真平台中的模型还具有多种特性:模型之 这个包含配置信息和模型关联关系的模型集合即为仿 间的连接和模型本身性质具有紧密的联系:同一研究 真任务流程,用户可以直接运行仿真任务流程进行相 领域的用户设计仿真任务会受到学科内容约束,在选 应的仿真任务,获得最终想要的结果 择仿真模型时具有一定的相似性:在不同应用场景和 1.3模型关联关系 需求下,仿真任务设计所需的模型具有一定的差异性: 在GNSS分布式仿真环境中,数学方法、硬件设备 智能推荐方法需要在用户配置任务时及时为用户提供 等资源均可虚拟化为仿真模型,并经过一定形式的封 参考模型.上述性质对模型的智能推荐提出了一些新 装后形成服务化模型.这种服务化模型是完全独立的 的需求,如实时性、智能性、可配置性等. 个体,能够完成一定的特定功能,并通过统一标准的接
范国超等: 基于关联关系的仿真模型实时智能推荐方法 tion environment,GDSE) 是最近被提出来的一种 GNSS 仿真环境. 该环境在面向互联网的前提下,结合了广 义云计算( cloud computing,CC) 核心理念———“对计 算资源进行共享”[1--7]和面向服务架构( service oriented architecture,SOA) 技术[8--10],实现了多开发人员或用 户发布并共用仿真模型或资源,达到研究新算法、新设 备和扩展新领域的目的. 李伯虎等[11--13]在研究中验证 了结合云计算的仿真环境可以有效地组织数据资源、 模型资源、计算资源和存储资源,进而加速计算过程, 实现资源共享、资源管理、资源配置、并行计算、协同工 作、信息服务和容错迁移. 该仿真平台具有高度的共 享和重用能力,能够减少重复开发和投资,具备更高的 仿真能力. 胡春生等[14--16]在结合云计算的分布式仿真 环境研究中提出了一种服务化分布式仿真环境的基本 构架和实施方法,初步分析了模型管理的相关问题和 研究思路,但并没有完全达到智能化管理的目的. 随 着服务化仿真平台的发展和应用,仿真模型数目会以 指数形式增大,并且应用场景和仿真需求不同,需要构 造的仿真流程的差异也较大,如何在大规模数量的模 型中迅速找到合适仿真模型是一个十分重要的问题. 利用计算机推理自动检索并推送给用户恰当的模型可 以避免用户多次手动检索模型. 目前针对计算机智能推荐方法主要基于数据挖掘 技术设计的,包括决策树、聚类、回归启发式方法、神经 网络/关联规则挖掘等[17],这些方法在大规模数据挖 掘和分析中具有很好的效果,并且多数方法已经应用 到了推荐系统上,但这些方法针对的推荐系统主要应 用领域为图书、文档、电影、商品等[17--20],被推荐对象 为完全独立的个体,互相基本没有相关关系. GNSS 分 布式仿真环境中模型之间具有紧密的联系,这种联系 使得模型的推荐工作与传统推荐方法有着巨大的差 别. 仿真任务中通常为 10 个以上模型的集合,使用传 统数据挖掘方法在仿真任务的大规模数据记录中提取 信息两模型间关联关系时准确度会明显降低. 仿真模 型智能推荐方法的数据检索和挖掘的过程与传统的模 式也有很大的区别,传统大数据挖掘过程通常是根据 一定的支持度或置信度阈值检索出相应的集合得到其 中元素的关联关系,而模型的智能推荐工作中将先形 成候选模型,再依据候选模型检索得到统计结果并排 序. 另外仿真平台中的模型还具有多种特性: 模型之 间的连接和模型本身性质具有紧密的联系; 同一研究 领域的用户设计仿真任务会受到学科内容约束,在选 择仿真模型时具有一定的相似性; 在不同应用场景和 需求下,仿真任务设计所需的模型具有一定的差异性; 智能推荐方法需要在用户配置任务时及时为用户提供 参考模型. 上述性质对模型的智能推荐提出了一些新 的需求,如实时性、智能性、可配置性等. 本文从服务化模型基本性质出发,提出了模型关 联关系和接口形状的概念,定义并推导了衡量模型关 联关系的指标,在关联规则的研究基础上提出了一种 针对 GNSS 分布式仿真环境中仿真模型的智能推荐方 法,方法中首先在贝叶斯分析方法的基础上提出了模 型关联关系度的计算方法,然后设计了一种条件约束 下 FP-tree 数据存储结构以及推荐方法工作流程,并从 理论上推理并讨论了该方法中部分工作的任务量等指 标. 最后利用 200000 组虚拟仿真任务记录数据对方 法进行仿真验证,对模型智能推荐方法的各项性能进 行测试,并与基于关联规则的数据挖掘方法进行对比 分析. 分析结果表明该方法在针对仿真模型推荐时运 行时间短,推荐结果准确度高,具有很好的实施效果. 1 模型关联关系和接口形状 不同仿真环境中,仿真模型和仿真任务流程的概 念差别很大,因此在定义模型关联关系和接口形状之 前,首先明确了这两个概念. 模型关联关系和接口形 状是本文提出的两个概念,仿真平台以模型关联关系 和接口形状为基础对仿真模型智能化管理,有助于仿 真模型智能推荐方法的实现和推荐方法效率的提高. 1. 1 仿真模型 大型仿真系统( 包括数学仿真、半物理仿真等) 是 对系统级结构或平台的功能和性能上的模拟实现. 由 于整体的数学或结构上的仿真很难直接实现,通常将 其分解为若干个既相对独立又相互联系的子系统( 包 含一个或多个功能单元) ,这种子系统更方便使用数 学模型或物理模型表示出来,被用于表示的模型即为 仿真模型. 不同系统的仿真可能包含相同功能的子系 统,即可使用相同的模型参与仿真. 在 GNSS 分布式仿真环境中,利用上述思想,用户 将能够实现部分功能的仿真模型依据接口规则共享到 平台上. 在有仿真需求时,根据需求用户可以挑选共 享的模型组合形成能够实现特定系统功能的仿真 任务. 1. 2 仿真任务流程 用户在利用 GNSS 分布式仿真环境构建仿真任务 时,需要调用仿真模型,配置模型之间的输入与输出关 系,配置完成后形成了一组具有关联关系的模型集合, 这个包含配置信息和模型关联关系的模型集合即为仿 真任务流程,用户可以直接运行仿真任务流程进行相 应的仿真任务,获得最终想要的结果. 1. 3 模型关联关系 在 GNSS 分布式仿真环境中,数学方法、硬件设备 等资源均可虚拟化为仿真模型,并经过一定形式的封 装后形成服务化模型. 这种服务化模型是完全独立的 个体,能够完成一定的特定功能,并通过统一标准的接 · 726 ·
·628 工程科学学报,第39卷,第4期 口协议配置输入输出信息与其他仿真模型建立联系 3R(Ma,M.)-0ut(M)nIn(M)≠⑦.(5) 在多个仿真模型组合形成仿真任务时,仿真模型间需 式中,Out(A)表示M,的输出接口形状的集合,In(B) 要建立一种特殊的关系来确定模型之间资源的传递 表示M。的输入接口形状的集合,若二者存在上述关 (如数学仿真模型的输入输出参数信息等),这种关系 系,则可以建立由M到M。的连接关系. 即为仿真模型关联关系 接口形状池是指所有接口形状的集合,任意仿真 通过构建仿真任务,本文发现能够与同一仿真模 模型的输入和输出的接口均为接口形状池的子集,如 型建立关系的几个模型构成的关系在一定程度上不是 图1.将接口形状统计在一个集合下,便于对模型进行 等价的,即他们与同一模型的亲疏程度有所不同,这种 检索,给出具有相同接口形状的模型,建立模型间的关 亲疏程度表现出了用户在建立仿真任务时的习惯偏 联关系.因此,基于接口形状的检索可初步形成候选 好.本文将这种模型之间的亲疏程度定义为模型关联 模型集合,记为接口形状池,这样将为挑选候选模型减 关系度,将模型关联关系度进行量化分析,可以得到不 少大量的检索工作,加快检索速度 同模型之间的亲疏程度排序 IN OUT 确定模型关联关系度主要有两种因素,即用户操 作信息和模型接口形状,故模型关联关系度可以定 接口形 义为 状池 d(Ma,Ma)=f(Ma,Nere). (1) ■ 其中,M,、M.为两个建立关联关系的仿真模型,M 为有关用户的信息统计函数,主要由用户已选模型、仿 真任务记录、模型库等信息处理得到;八为基于模 图1 接口形状及接口形状池 型接口形状进行处理所得到的结果.由于模型关联关 Fig.1 Interface shape and its pool 系具有方向性,因此 2 智能推荐方法设计 d(M、,M.)≠d(M,M,). (2) 关联关系度是一个对不同模型关联关系亲疏程度 仿真模型智能推荐方法结合用户使用模型的基本 的量化指标.因此与同一个模型建立关系的关联关系 规律和模型的接口形状,根据当前用户所选择模型,智 度为一个动态值,且存在归一化性质,即 能推算下一个可能用到的模型,为用户设计仿真任务 ∑d(M,M,)=1. (3) 提供参考.该方法主要依靠模型本身的基本属性和统 其中,M为任意可以与M、建立由M、到M的连接关 计学方法,快速求取模型关联关系度并以此排序.同 系的模型.由上述性质可知,模型关联关系度是在一 时在数据挖掘过程中需要将相关方法依据仿真模型特 定条件下的概率问题的求解,且其概率密度符合后验 性重新设计. 分布,相应的求解方法可以贝叶斯统计为基础设计,即 图2是仿真任务智能推荐模块在GNSS分布式仿 d(M)f()M)(M) 真环境中的基本架构,该模块根据语义管理库中的接 (4) 口形状池、模型库、仿真任务记录池以及人机交互界面 ∑f(g(M,M)1M,)m(M,) 中用户当前选择的部分模型进行检索和推理,最终给 其中,g(M,M)为M,的样本信息,f(g(M,M)IM) 出一组经过排序的用户可能即将需要用到的模型集 为M:发生的概率密度函数,m为候选模型个数 合.图中可以看出,基于接口形状池的初步检索形成 1.4接口形状 了候选模型集合,在依据模型关联关系度的计算和排 仿真模型在封装后以统一的接口对外表现,主要 序,对候选模型进行二次筛选和排序,最终确定了被推 包括输入接口、输出接口和初始化接口三类,其中输入 荐模型的有序集合 接口和输出接口是用于在模型之间建立关系的,但不 2.1模型关联关系度计算方法 是任意模型之间都能够建立起模型关系,通常对于数 模型关联关系度主要根据以往配置信息记录,结 学模型来讲,只有输入输出之间存在相同的量纲关系 合权重的配置进行计算和比较分析.由公式(1)可 时才能够建立连接关系. 知,关联关系度需结合用户信息和接口形状两个方面 由于仿真模型可能包含多个输入或输出,所以本 进行求解 文规定,任意一个输入或输出均为一个模型接口,每个 (1)用户信息部分求解 模型接口根据量纲和资源属性确定其接口形状.在不 用户信息部分主要包括对模型库、用户当前操作 同模型之间,只有含有相同形状的输入接口和输出接 内容、仿真任务记录等相关信息的统计计算.在统计 口两个模型才能建立关联关系,即: 过程中采用支持度的计算方法获得对应结果
工程科学学报,第 39 卷,第 4 期 口协议配置输入输出信息与其他仿真模型建立联系. 在多个仿真模型组合形成仿真任务时,仿真模型间需 要建立一种特殊的关系来确定模型之间资源的传递 ( 如数学仿真模型的输入输出参数信息等) ,这种关系 即为仿真模型关联关系. 通过构建仿真任务,本文发现能够与同一仿真模 型建立关系的几个模型构成的关系在一定程度上不是 等价的,即他们与同一模型的亲疏程度有所不同,这种 亲疏程度表现出了用户在建立仿真任务时的习惯偏 好. 本文将这种模型之间的亲疏程度定义为模型关联 关系度,将模型关联关系度进行量化分析,可以得到不 同模型之间的亲疏程度排序. 确定模型关联关系度主要有两种因素,即用户操 作信息和模型接口形状,故模型关联关系度可以定 义为 d( MA,MB ) = f( Muser,Ninterface ) . ( 1) 其中,MA、MB 为两个建立关联关系的仿真模型,Muser 为有关用户的信息统计函数,主要由用户已选模型、仿 真任务记录、模型库等信息处理得到; Ninterface为基于模 型接口形状进行处理所得到的结果. 由于模型关联关 系具有方向性,因此 d( MA,MB ) ≠d( MB,MA ) . ( 2) 关联关系度是一个对不同模型关联关系亲疏程度 的量化指标. 因此与同一个模型建立关系的关联关系 度为一个动态值,且存在归一化性质,即 ∑ d( MA,Mi ) = 1. ( 3) 其中,Mi 为任意可以与 MA 建立由 MA 到 Mi 的连接关 系的模型. 由上述性质可知,模型关联关系度是在一 定条件下的概率问题的求解,且其概率密度符合后验 分布,相应的求解方法可以贝叶斯统计为基础设计,即 d( MA,Mi ) = f( g( MA,Mi ) | Mi ) π( Mi ) ∑ m i = 1 f( g( MA,Mi ) | Mi ) π( Mi ) . ( 4) 其中,g( MA,Mi ) 为Mi 的样本信息,f( g( MA,Mi ) | Mi ) 为 Mi 发生的概率密度函数,m 为候选模型个数. 1. 4 接口形状 仿真模型在封装后以统一的接口对外表现,主要 包括输入接口、输出接口和初始化接口三类,其中输入 接口和输出接口是用于在模型之间建立关系的,但不 是任意模型之间都能够建立起模型关系,通常对于数 学模型来讲,只有输入输出之间存在相同的量纲关系 时才能够建立连接关系. 由于仿真模型可能包含多个输入或输出,所以本 文规定,任意一个输入或输出均为一个模型接口,每个 模型接口根据量纲和资源属性确定其接口形状. 在不 同模型之间,只有含有相同形状的输入接口和输出接 口两个模型才能建立关联关系,即: R( MA,MB ) Out( MA ) ∩ In( MB ) ≠ . ( 5) 式中,Out( A) 表示 MA 的输出接口形状的集合,In( B) 表示 MB 的输入接口形状的集合,若二者存在上述关 系,则可以建立由 MA 到 MB 的连接关系. 接口形状池是指所有接口形状的集合,任意仿真 模型的输入和输出的接口均为接口形状池的子集,如 图 1. 将接口形状统计在一个集合下,便于对模型进行 检索,给出具有相同接口形状的模型,建立模型间的关 联关系. 因此,基于接口形状的检索可初步形成候选 模型集合,记为接口形状池,这样将为挑选候选模型减 少大量的检索工作,加快检索速度. 图 1 接口形状及接口形状池 Fig. 1 Interface shape and its pool 2 智能推荐方法设计 仿真模型智能推荐方法结合用户使用模型的基本 规律和模型的接口形状,根据当前用户所选择模型,智 能推算下一个可能用到的模型,为用户设计仿真任务 提供参考. 该方法主要依靠模型本身的基本属性和统 计学方法,快速求取模型关联关系度并以此排序. 同 时在数据挖掘过程中需要将相关方法依据仿真模型特 性重新设计. 图 2 是仿真任务智能推荐模块在 GNSS 分布式仿 真环境中的基本架构,该模块根据语义管理库中的接 口形状池、模型库、仿真任务记录池以及人机交互界面 中用户当前选择的部分模型进行检索和推理,最终给 出一组经过排序的用户可能即将需要用到的模型集 合. 图中可以看出,基于接口形状池的初步检索形成 了候选模型集合,在依据模型关联关系度的计算和排 序,对候选模型进行二次筛选和排序,最终确定了被推 荐模型的有序集合. 2. 1 模型关联关系度计算方法 模型关联关系度主要根据以往配置信息记录,结 合权重的配置进行计算和比较分析. 由公式( 1) 可 知,关联关系度需结合用户信息和接口形状两个方面 进行求解. ( 1) 用户信息部分求解. 用户信息部分主要包括对模型库、用户当前操作 内容、仿真任务记录等相关信息的统计计算. 在统计 过程中采用支持度的计算方法获得对应结果. · 826 ·
范国超等:基于关联关系的仿真模型实时智能推荐方法 ·629 由式(7)和式(8)可得 接口 仿真任务 模型库 Me=sup(F。-Ny)UM)· 形状池 记录池 型 1- sup(F) (9) 系管 sup(F。-N) (2)接口形状部分求解 接口形状权重因子在计算过程中主要依据前后模 根据智能 推荐算法 型本身的接口数目和建立关系的接口数目来确定,其 初步形成 选出可能 K-I项集 需要的 计算公式如下, 摸块并排序 模 N..N. 型 将结果 整理并 Nmd=Ni(N2( (10) 能 推送到 基于接口 其中,N。表示建立连接的接口形状数目,N,m…表示建 形状池 初步形成 人机交互 候选项集 界面指定 立连接模型中的前一个模型输出接口的数目,八2m表 检索 区域 示建立连接模型中后一个模型的输入接口的数目. (3)关联关系度计算. 机 点中可以与 根据关联关系度的定义和相关性质以及贝叶斯统 已选有 第N+1个模块 提供 N个 老 模块 建立关系的 计方法,可定义第n个候选模型对应的关联关系度计 候选集 当前模块 算方法为 图2仿真模型推荐算法在平台中的基本交互 d(M,M)= (aM N)/FT Fig.2 Basic interaction of the simulation model illustration 2(a M+aNai)/Fa) algorithm in the platform (11) 故对用户信息部分的统计计算为 其中,n表示候选集合中的第n候选模型,m表示候选 Mr=sup(F。UM,). (6) 集合中共有m个模型,F为所有模型与当前模型发 其中,sup()为对应模型集合在仿真任务记录中的支 生关联的总次数.a1为接口形状权重系数,a2为缺失 持度计数,F。表示用户已经配置完的n个模型. 模型后剩余权重系数,且a1+a2=1. 公式(6)在模型检索过程中会出现项集检索计数 a,和a2的值主要由用户进行配置,希望模型的全 结果为0的可能性,这时需要项集中排除部分权重较 低的模型重新检索,同时检索得到的计数结果需要给 部接口能够快速建立连接的用户可以将a,的值配置 一个权重系数.故公式(6)可修改为 的相对更高一些,而希望参考已有设计任务记录的用 Mm=sup(F。-Ny)UM)×Q,(N).(7) 户可以将α2的值配置的相对更高一些.若a1=0,则 其中,Q,(N,)为事务项集中缺失一些模型后的剩余权 表示用户完全依据任务设计流程记录对候选模型排 重因子,N,是在用户已经配置完成的n个模型中需要 序;若α2=0,则表示完全不考虑缺失模型对排序结果 去掉的部分模型(可能是一个或多个) 的影响,计算结果将主要受两个连接模型的接口形状 缺失模型后剩余权重因子需要通过分别求取包含 数目和可连接接口形状数目影响 用户已选的全部模型和去掉一部分模型的两个集合的 公式(11)可化简为 支持度,进而通过相应的计算公式得到剩余模型的权 a M+a N 重值.因此Q,(N)的计算方法为 d(M,M)= (12) sup(F) a吧+吧 Q(N)=1- (8) sup (F.-N) 由公式(9)、(10)和(12)可得 af sup((F.-N)UM)1- sup(F) d(M,Ma)= up(F。-N)] Nmo N (13) 豆{ap(R.-)ua)l- sup(F.)1 sup(F-N0)」+a2N,N6l 上述公式对新加入的模型可能会有一定的影响,导致新加入模型始终不能被检测到,因此为了对新加入模型 有一定的排序保护,将公式(13)修改为
范国超等: 基于关联关系的仿真模型实时智能推荐方法 图 2 仿真模型推荐算法在平台中的基本交互 Fig. 2 Basic interaction of the simulation model illustration algorithm in the platform 故对用户信息部分的统计计算为 Muser = sup( Fn ∪ Mk ) . ( 6) 其中,sup( ) 为对应模型集合在仿真任务记录中的支 持度计数,Fn 表示用户已经配置完的 n 个模型. 公式( 6) 在模型检索过程中会出现项集检索计数 结果为 0 的可能性,这时需要项集中排除部分权重较 低的模型重新检索,同时检索得到的计数结果需要给 一个权重系数. 故公式( 6) 可修改为 Muser = sup( ( Fn - Nj ) ∪ Mk ) × Q1 ( Nj ) . ( 7) 其中,Q1 ( Nj ) 为事务项集中缺失一些模型后的剩余权 重因子,Nj 是在用户已经配置完成的 n 个模型中需要 去掉的部分模型( 可能是一个或多个) . 缺失模型后剩余权重因子需要通过分别求取包含 用户已选的全部模型和去掉一部分模型的两个集合的 支持度,进而通过相应的计算公式得到剩余模型的权 重值. 因此 Q1 ( Nj ) 的计算方法为 Q1 ( Nj ) = 1 - sup( Fn ) sup( Fn - Nj ) . ( 8) 由式( 7) 和式( 8) 可得 Muser = sup( ( Fn - Nj ) ∪ Mk ( ) · 1 - sup( Fn ) sup( Fn - Nj ) ) . ( 9) ( 2) 接口形状部分求解. 接口形状权重因子在计算过程中主要依据前后模 型本身的接口数目和建立关系的接口数目来确定,其 计算公式如下, Ninterface = Nc N1( out) · Nc N2( in) . ( 10) 其中,Nc 表示建立连接的接口形状数目,N1( out) 表示建 立连接模型中的前一个模型输出接口的数目,N2( in) 表 示建立连接模型中后一个模型的输入接口的数目. ( 3) 关联关系度计算. 根据关联关系度的定义和相关性质以及贝叶斯统 计方法,可定义第 n 个候选模型对应的关联关系度计 算方法为 d( MA,M( n) ) = ( a( n) 1 M( n) user + a( n) 2 N( n) interface ) /FTotal ∑ m i = 1 ( ( a( i) 1 M( i) user + a( i) 2 N( i) interface ) /FTotal ) . ( 11) 其中,n 表示候选集合中的第 n 候选模型,m 表示候选 集合中共有 m 个模型,FTotal为所有模型与当前模型发 生关联的总次数. a1 为接口形状权重系数,a2 为缺失 模型后剩余权重系数,且 a1 + a2 = 1. a1 和 a2 的值主要由用户进行配置,希望模型的全 部接口能够快速建立连接的用户可以将 a1 的值配置 的相对更高一些,而希望参考已有设计任务记录的用 户可以将 a2 的值配置的相对更高一些. 若 a1 = 0,则 表示用户完全依据任务设计流程记录对候选模型排 序; 若 a2 = 0,则表示完全不考虑缺失模型对排序结果 的影响,计算结果将主要受两个连接模型的接口形状 数目和可连接接口形状数目影响. 公式( 11) 可化简为 d( MA,M( n) ) = a( n) 1 M( n) user + a( n) 2 N( n) nterface ∑ m i = 1 a( i) 1 M( i) user + a( i) 2 N( i) interface . ( 12) 由公式( 9) 、( 10) 和( 12) 可得 d( MA,M( n) ) = a( n) 1 sup( ( Fn - N( n) j ) ∪ M( n) [ ) 1 - sup( Fn ) sup( Fn - N( n) j ] ) + a( n) 2 N( n) c NA( out) N( n) c N( n) ( in) ∑ m i = { 1 ( a( i) 1 sup( ( Fn - N( i) j ) ∪ M( i) [ ) 1 - sup( Fn ) sup( Fn - N( i) j ] ) + a( i) 2 N( i) c NA( out) N( i) c N( i) ( in }) . ( 13) 上述公式对新加入的模型可能会有一定的影响,导致新加入模型始终不能被检测到,因此为了对新加入模型 有一定的排序保护,将公式( 13) 修改为 · 926 ·
·630· 工程科学学报,第39卷,第4期 b+a sup((F.-N)UM)1-- sup(F) p(F,-Na)」 +a0地o NamN高 d(Ma,Mo)= (14) b sup((F.)M)1 sup (F -NO)+a N vo sup(F) b为模型在刚加入平台中时设置的初始数目,为 了不影响后续模型的统计信息,b的取值不宜过大,通 常选取在100左右,用户可根据个人习惯进行配置. 2.2条件FP-tree数据存储结构设计 在对大量仿真任务记录进行检索时,采用频繁模 (DH (D D 式树(FP-4ree)数据记录结构可以加快检索效率. FPAree是做频繁项集等数据挖掘工作常用的数据记录 A 模式如,通常存储的不同事务之间会有若干个相同的 B 项,因此它们在Pree上可能会有部分路径重叠.路 径重叠的越多,使用FPAree结构获得的压缩的效果越 好四,提高对存储事务检索的速度就越明显,通过支 持度阈值或置信度阈值检索效率也就越高。但以仿真 图3条件FP4ree数据结构 平台中的模型为对象做关联关系检索时,已知参数不 Fig.3 Data structure of the condition FPree 再是支持度阈值或置信度阈值等约束量,而是各个候 选模型分别对应的候选项集.这样在考察各个候选模 L=∑ (17) 型对应项集的支持度时均需单独检索FPAree,设每次 每个候选模型对应的检索任务量为 FPAree的检索任务量为L,候选模型有m个,用户已选 r=dl+dl2+…+dnlm,d,∈0,p-1].(18) 模型p个,则总检索任务量为 根据d,取值范围可得 (19) R,=d,L+d,L+…+dL=∑dL,d,e0,p-l]. r∈D,(p-1)l],ie,m]. 在检索过程中,m个候选模型检索任务总量为 (15) 所以有 Re[A.0-)]= R,∈mL,m(p-1)L. (16) ,(p-1)L],i∈0,m]. (20) 在检索某一候选模型对应的项集时,其他候选模 若d=d2=…=dn,则有 型对应的FP-ree结点和分支即成为多余检索量.本 R R= (21) 文在FP-ree的基础上,提出了固连结点的概念,在固 m 连结点形成一种具有一定条件约束的FP-ree数据记 对比公式(16)可见加入固连结点约束后的 录结构.固连结点是把与FPAree根节点直接相连的 FP-ree数据存储结构在候选模型项集检索方面大幅降 节点换成固定的连接体,连接体由候选模型对应的节 低了检索任务量,由公式(20~21)可以看出,候选模 点和当前用户选中模型对应的节点构成.在固连结点 型越多检索任务量降低的效果将越明显 之后的节点采用与传统FP4ree相同的构建方法,每个 2.3推荐方法流程 条件FP-ree的固连结点的数目由候选模型数目决定. 智能推荐方法的工作主要是对模型库、接口形状 这样在针对每个候选模型做FPAree检索时,可以直接 池、仿真任务记录池等数据记录的一系列检索和计算, 检索其对应固连结点的分枝,其余固连结点的分枝直 将得到的结果依照模型关联关系度排序后提供给用 接做剪枝处理.这样可以节省大量检索时间,提高推 户,其主要工作流程如图4. 荐方法效率。 ①根据当前选中的模型,以及接口形状池的记 以固连结点为约束条件的FP4ree基本结构如 录,在模型库中提取出所有能够与当前选中模型建立 图3.图中E、F、G和H为根据接口形状池检索出的候 连接关系的模型,组成候选项集Paxm· 选模型,D为当前用户选中的模型,A、B和C为用户已 ②根据候选模型和当前模型的接口数目进行计 选的其他模型. 算,得到所有候选模型对应的接口形状权重inere 依据上述方法,假设第个候选模型对应分支的 ③将候选项集P:xm和当前需要建立连接的模 检索任务量为1,则有 型qn构建固连结点矩阵Pxm'[b。…o]xm]
工程科学学报,第 39 卷,第 4 期 d( MA,M( n) ) = b + a( n) 1 sup( ( Fn - N( n) j ) ∪ M( n) [ ) 1 - sup( Fn ) sup( Fn - N( n) j ] ) + a( n) 2 N( n) c NA( out) N( n) c N( n) ( in) b + ∑ m i = { 1 a( i) 1 sup( ( Fn - N( i) j ) ∪ M( i) [ ) 1 - sup( Fn ) sup( Fn - N( i) j ] ) + a( i) 2 N( i) c NA( out) N( i) c N( i) ( in }) . ( 14) b 为模型在刚加入平台中时设置的初始数目,为 了不影响后续模型的统计信息,b 的取值不宜过大,通 常选取在 100 左右,用户可根据个人习惯进行配置. 2. 2 条件 FP-tree 数据存储结构设计 在对大量仿真任务记录进行检索时,采用频繁模 式树( FP-tree ) 数 据 记 录 结 构 可 以 加 快 检 索 效 率. FP-tree是做频繁项集等数据挖掘工作常用的数据记录 模式[21],通常存储的不同事务之间会有若干个相同的 项,因此它们在 FP-tree 上可能会有部分路径重叠. 路 径重叠的越多,使用 FP-tree 结构获得的压缩的效果越 好[22],提高对存储事务检索的速度就越明显,通过支 持度阈值或置信度阈值检索效率也就越高. 但以仿真 平台中的模型为对象做关联关系检索时,已知参数不 再是支持度阈值或置信度阈值等约束量,而是各个候 选模型分别对应的候选项集. 这样在考察各个候选模 型对应项集的支持度时均需单独检索 FP-tree,设每次 FP-tree 的检索任务量为 L,候选模型有 m 个,用户已选 模型 p 个,则总检索任务量为 Rt = d1 L + d2 L + … + dm L = ∑ m i = 1 diL,di∈[1,p - 1]. ( 15) 所以有 Rt∈[mL,m( p - 1) L]. ( 16) 在检索某一候选模型对应的项集时,其他候选模 型对应的 FP-tree 结点和分支即成为多余检索量. 本 文在 FP-tree 的基础上,提出了固连结点的概念,在固 连结点形成一种具有一定条件约束的 FP-tree 数据记 录结构. 固连结点是把与 FP-tree 根节点直接相连的 节点换成固定的连接体,连接体由候选模型对应的节 点和当前用户选中模型对应的节点构成. 在固连结点 之后的节点采用与传统 FP-tree 相同的构建方法,每个 条件 FP-tree 的固连结点的数目由候选模型数目决定. 这样在针对每个候选模型做 FP-tree 检索时,可以直接 检索其对应固连结点的分枝,其余固连结点的分枝直 接做剪枝处理. 这样可以节省大量检索时间,提高推 荐方法效率. 以固连 结 点 为 约 束 条 件 的 FP-tree 基 本 结 构 如 图 3. 图中 E、F、G 和 H 为根据接口形状池检索出的候 选模型,D 为当前用户选中的模型,A、B 和 C 为用户已 选的其他模型. 依据上述方法,假设第 i 个候选模型对应分支的 检索任务量为 li,则有 图 3 条件 FP-tree 数据结构 Fig. 3 Data structure of the condition FP-tree L = ∑ m i = 1 li . ( 17) 每个候选模型对应的检索任务量为 ri = d1 l1 + d2 l2 + … + dm lm,di∈[1,p - 1]. ( 18) 根据 di 取值范围可得 ri∈[li,( p - 1) li],i∈[1,m]. ( 19) 在检索过程中,m 个候选模型检索任务总量为 R't∈ [ ∑ m i = 1 li,( p - 1) ∑ m i = 1 li ] = [L,( p - 1) L],i∈[1,m]. ( 20) 若 d1 = d2 = … = dm,则有 R't = Rt m . ( 21) 对比 公 式 ( 16 ) 可 见 加 入 固 连 结 点 约 束 后 的 FP-tree数据存储结构在候选模型项集检索方面大幅降 低了检索任务量,由公式( 20 ~ 21) 可以看出,候选模 型越多检索任务量降低的效果将越明显. 2. 3 推荐方法流程 智能推荐方法的工作主要是对模型库、接口形状 池、仿真任务记录池等数据记录的一系列检索和计算, 将得到的结果依照模型关联关系度排序后提供给用 户,其主要工作流程如图 4. ① 根据当前选中的模型,以及接口形状池的记 录,在模型库中提取出所有能够与当前选中模型建立 连接关系的模型,组成候选项集 P( 1 × m) . ② 根据候选模型和当前模型的接口数目进行计 算,得到所有候选模型对应的接口形状权重 Ninterface . ③ 将候选项集 P( 1 × m) 和当前需要建立连接的模 型 qn 构建固连结点矩阵[PT ( 1 × m),[on … on]T ( 1 × m) ], · 036 ·
范国超等:基于关联关系的仿真模型实时智能推荐方法 ·631 独配置到一台服务器上,网络带宽为100Mbps 接口 当前需要 建立连接 仿真任务 仿真终端 仿真终端 仿真终端 形状池 的模型q。 记录池 0 Internet 人机交 候选项集 互终端 (P(xm) 业 接口 推荐算法 组合形成固连块矩阵 模型库 仿真任务 构建条件FP-Tree 形状池 记录池 服务器 [Pro Y 图5仿真环境基本架构 检索条件FP-trre, Fig.5 Architecture of the simulation environment 筛选项集矩阵 计算出项集矩阵 11--1OP 对应的支持度SUP [sup()sup( 测试前首先人工生成了250个仿真模型(包括星 历文件读取、空间环境仿真、观测数据仿真、用户位置 扩展约束项集矩阵 l-lii0uw 去掉项集中 仿真、用户定位解算等)和200000条仿真任务记录. 权重最低 在人机交互终端进行任务设计,利用本文智能推荐方 一项,并o.=0 约束项集 where sup()=0 法在仿真任务设计过程中对下一步模型进行预测,分 (Oo 析其方法运行速度等指标,并采用传统数据挖掘方法 r(lxSUP)<m an 是 (以关联规则方法为例)对同样任务处理用于对比分 当前工作区仿真 析,另外为测试条件Pree对模型智能推荐方法运行 任务模型集 否 性能的提升,单独记录了不采用条件FP-ree数据存储 矩阵元素按值 计算关联关系度矩阵 结构的智能推荐方法的工作时间.为保证统计结果可 降序排列排序 D=lddl 靠性,使用蒙特卡洛方法分别针对200种不同仿真任 图4智能推荐算法工作流程 务测试,得到用户在已配置4个模型时各方法的平均 Fig.4 Intelligent recommendation algorithm workflow 工作时间如图6. 3500 并在固连结点的约束下检索仿真任务池,构建条件 一模型智能推荐方法(条件FP-tree) 3000 传统智能推荐方法(关联规则 FP-ree. 模型智能推荐方法(非条件FP-ree) ④根据用户已选模型形成的约束项集矩阵O:x) 2500 和候选项集矩阵P1x构建成仿真模型筛选项集矩阵 2000 [0…lx0 xPx]. Ξ1500 ⑤检索条件FP4ree,.根据支持度计算方法得到支 1000 持度矩阵SUP=[sup(),·sup().]axm,并判定 结果I×SUP是否满质,若不满质,去掉sup():=0处 中的权重最小的模型,并设置=0,重新计算. 020406080100120140160180200 测试次数 ⑥获得满质的I×SUP后,根据模型关联关系度 图6推荐算法运行时间 的计算方法,得到候选模型项集对应的关系度矩阵 Fig.6 Running time of the recording method D=☑,…d]ax,并将矩阵元素降序排列,依照 排列顺序,推送模型到人机交互界面. 图6中可以看出,使用本文中的模型智能推荐方 3仿真结果分析 法工作时间维持在500ms左右,而使用传统的基于关 联规则的数据挖掘方法在上述任务中工作时间为 为检验上述方法的可用性,在局域网环境中,构建 1500~2000ms.可见模型智能推荐方法具有更高的效 了一个GNSS分布式仿真环境原型系统,仿真平台环 率,基本能够达到实时反馈.另外不使用条件FP-ree 境搭建如图5,在该环境中,模型库、仿真任务记录池 时,模型智能推荐方法的工作时间达到800~1000s, 和接口形状池分别存储于对应的数据存储服务器中, 时间增长了近一倍,可以看出条件FPee在实际工作 仿真终端、推荐算法服务器等服务终端以面向服务框 中可以明显提高推荐方法的工作效率 架(SOA)架构面向互联网构建,其中推荐算法模块单 目前通常进行的仿真任务包含模型一般为8~15
范国超等: 基于关联关系的仿真模型实时智能推荐方法 图 4 智能推荐算法工作流程 Fig. 4 Intelligent recommendation algorithm workflow 并在固连结点的约束下检索仿真任务池,构建条件 FP-tree. ④ 根据用户已选模型形成的约束项集矩阵 O( 1 × n) 和候选项集矩阵 P( 1 × m) 构建成仿真模型筛选项集矩阵 [[1 … 1]T ( 1 × m) O( 1 × n) ,P( 1 × m)]. ⑤ 检索条件 FP-tree,根据支持度计算方法得到支 持度矩阵 SUP =[sup( ) 1 … sup( ) m]( 1 × m) ,并判定 结果 I × SUP 是否满质,若不满质,去掉 sup( ) i = 0 处 中的权重最小的模型,并设置 oij = 0,重新计算. ⑥ 获得满质的 I × SUP 后,根据模型关联关系度 的计算方法,得到候选模型项集对应的关系度矩阵 D =[d1 … dm]( 1 × m) ,并将矩阵元素降序排列,依照 排列顺序,推送模型到人机交互界面. 3 仿真结果分析 为检验上述方法的可用性,在局域网环境中,构建 了一个 GNSS 分布式仿真环境原型系统,仿真平台环 境搭建如图 5,在该环境中,模型库、仿真任务记录池 和接口形状池分别存储于对应的数据存储服务器中, 仿真终端、推荐算法服务器等服务终端以面向服务框 架( SOA) 架构面向互联网构建,其中推荐算法模块单 独配置到一台服务器上,网络带宽为 100 Mbps. 图 5 仿真环境基本架构 Fig. 5 Architecture of the simulation environment 测试前首先人工生成了 250 个仿真模型( 包括星 历文件读取、空间环境仿真、观测数据仿真、用户位置 仿真、用户定位解算等) 和 200000 条仿真任务记录. 在人机交互终端进行任务设计,利用本文智能推荐方 法在仿真任务设计过程中对下一步模型进行预测,分 析其方法运行速度等指标,并采用传统数据挖掘方法 ( 以关联规则方法为例) 对同样任务处理用于对比分 析,另外为测试条件 FP-tree 对模型智能推荐方法运行 性能的提升,单独记录了不采用条件 FP-tree 数据存储 结构的智能推荐方法的工作时间. 为保证统计结果可 靠性,使用蒙特卡洛方法分别针对 200 种不同仿真任 务测试,得到用户在已配置 4 个模型时各方法的平均 工作时间如图 6. 图 6 推荐算法运行时间 Fig. 6 Running time of the recording method 图 6 中可以看出,使用本文中的模型智能推荐方 法工作时间维持在 500 ms 左右,而使用传统的基于关 联规则的数据挖掘方法在上述任务中工作时间为 1500 ~ 2000 ms. 可见模型智能推荐方法具有更高的效 率,基本能够达到实时反馈. 另外不使用条件 FP-tree 时,模型智能推荐方法的工作时间达到 800 ~ 1000 ms, 时间增长了近一倍,可以看出条件 FP-tree 在实际工作 中可以明显提高推荐方法的工作效率. 目前通常进行的仿真任务包含模型一般为 8 ~ 15 · 136 ·
·632· 工程科学学报,第39卷,第4期 个,为测试智能推荐方法与用户已经选择模型的数目 100 40 之间的关系,分别以不同用户已配置模型数目(1~15 个)进行蒙特卡洛测试,得到用户已选模型的数量与 80 推荐方法平均工作时间的关系如图7所示 60 模型智能推荐方法条件FP-Lree) 3500 一…一传统智能推荐方法(关联规则 40 …◆…模型智能推荐方法(非条件FP-ree) 3000 2500 20 2000 -模型智能推荐方法条件FP-tne© …一传统智能推荐方法关联规则) 6 1500 mm-模型智能推荐方法非条件FP-ree) 推荐模型个数 1000 图8推荐方法准确度 500 Fig.8 Accuracy of the recording method 0123456789101112B1415 2500 模型智能推荐方法(条件FP-tree) 用户已选模型数 传统智能推荐方法(关联规 2000 …摸型智能推荐方法(非条件FP-tee) 图7推荐方法运行时间与用户已配置模型数目的关系 Fig.7 Relationship between the running time and configured model 1500 number 图7中可以看出传统智能推荐方法在开始时会随 已选模型数目的增大急剧增加,在8个左右之后会有 500 所减少,这主要是因为传统方法中不同模型数目组成 的项集数目只是简单的组合关系,项集数目具有先增 多后减少的特点,对应的运行时间也会有同样的影响 03 1.0 15 20 仿真任务记录数10 而模型智能推荐方法的候选模型是通过接口形状筛选 图9推荐方法运行时间与仿真任务记录数目的关系 的,不受组合数目的影响,因此其运行时间虽然会随着 Fig.9 Relationship between the running time and simulation task re- 用户已配置的模型数目的增加有所增大,但始终维持 cords 在500ms左右.另外,对比图中未采用条件FPAree的 运行时间的增加情况来看,智能推荐方法增加的工作 记录数目的增加会有所增大,但总体运行时间一直保 时间也主要为FP-ree检索时间. 持在500ms以内.而使用传统数据挖掘方法所消耗的 根据用户在人机交互端已配置4个模型的推荐结 时间均在1500ms以上,随着仿真任务记录的增加,方 果,统计各个方法得到的推荐模型的准确度.统计过 法所需时间也会增大.未使用条件FPee时间增加 程中,本文规定:推荐集合中包含用户所需模型即为有 的趋势更加明显,可以推测在增长到一定程度后,该方 效,若不包含即为无效.推荐模型集合中模型个数由 法所消耗的时间可能会过长,甚至不满足方法的实时 用户确定:假设用户设置为x个,则取关联关系度较大 性需求. 的前x个模型为推荐模型.得到各方法对应的推荐模 上述结果表明,本文设计的仿真模型智能推荐方 型准确度如图8所示. 法与传统方法比较,运行时间更少,并且不会随着用户 图8中可以看出,当仅取1个推荐模型时,模型智 已选模型、仿真任务记录等参量的变化有较大的变动 能推荐方法的准确度为40%~50%,推荐模型个数为 另外经过测试,条件FP-ree数据存储结构对减少模型 10个时,准确度已达到95%~98%,接近完全准确. 检索时间具有很好的作用. 而采用传统推荐方法所得结果的准确度始终在40% 4结论 以下,甚至当推荐模型为2个或以下时准确度已低于 20%.另外,无论是否采用条件FP4ree存储结构,其 根据GNSS仿真的基本原理,在其服务化共享仿 检索结果的准确度不受影响,可见数据存储结构并不 真研究的基础上,结合仿真模型的基本特性,针对 影响检索和计算的结果. GNSS分布式仿真环境中模型关联关系进行推理分析, 分别以不同仿真任务记录数目进行分析,得到推 提出了一种针对平台中仿真模型的智能推荐方法,该 荐算法的平均工作时间如图9所示. 方法结合数据挖掘的相关技术,利用仿真模型的基本 图中模型智能推荐方法的工作时间会随仿真任务 特性,基本能够实现根据现有模型及仿真任务记录自
工程科学学报,第 39 卷,第 4 期 个,为测试智能推荐方法与用户已经选择模型的数目 之间的关系,分别以不同用户已配置模型数目( 1 ~ 15 个) 进行蒙特卡洛测试,得到用户已选模型的数量与 推荐方法平均工作时间的关系如图 7 所示. 图 7 推荐方法运行时间与用户已配置模型数目的关系 Fig. 7 Relationship between the running time and configured model number 图 7 中可以看出传统智能推荐方法在开始时会随 已选模型数目的增大急剧增加,在 8 个左右之后会有 所减少,这主要是因为传统方法中不同模型数目组成 的项集数目只是简单的组合关系,项集数目具有先增 多后减少的特点,对应的运行时间也会有同样的影响. 而模型智能推荐方法的候选模型是通过接口形状筛选 的,不受组合数目的影响,因此其运行时间虽然会随着 用户已配置的模型数目的增加有所增大,但始终维持 在 500 ms 左右. 另外,对比图中未采用条件 FP-tree 的 运行时间的增加情况来看,智能推荐方法增加的工作 时间也主要为 FP-tree 检索时间. 根据用户在人机交互端已配置 4 个模型的推荐结 果,统计各个方法得到的推荐模型的准确度. 统计过 程中,本文规定: 推荐集合中包含用户所需模型即为有 效,若不包含即为无效. 推荐模型集合中模型个数由 用户确定: 假设用户设置为 x 个,则取关联关系度较大 的前 x 个模型为推荐模型. 得到各方法对应的推荐模 型准确度如图 8 所示. 图 8 中可以看出,当仅取 1 个推荐模型时,模型智 能推荐方法的准确度为 40% ~ 50% ,推荐模型个数为 10 个时,准确度已达到 95% ~ 98% ,接近完全准确. 而采用传统推荐方法所得结果的准确度始终在 40% 以下,甚至当推荐模型为 2 个或以下时准确度已低于 20% . 另外,无论是否采用条件 FP-tree 存储结构,其 检索结果的准确度不受影响,可见数据存储结构并不 影响检索和计算的结果. 分别以不同仿真任务记录数目进行分析,得到推 荐算法的平均工作时间如图 9 所示. 图中模型智能推荐方法的工作时间会随仿真任务 图 8 推荐方法准确度 Fig. 8 Accuracy of the recording method 图 9 推荐方法运行时间与仿真任务记录数目的关系 Fig. 9 Relationship between the running time and simulation task records 记录数目的增加会有所增大,但总体运行时间一直保 持在 500 ms 以内. 而使用传统数据挖掘方法所消耗的 时间均在 1500 ms 以上,随着仿真任务记录的增加,方 法所需时间也会增大. 未使用条件 FP-tree 时间增加 的趋势更加明显,可以推测在增长到一定程度后,该方 法所消耗的时间可能会过长,甚至不满足方法的实时 性需求. 上述结果表明,本文设计的仿真模型智能推荐方 法与传统方法比较,运行时间更少,并且不会随着用户 已选模型、仿真任务记录等参量的变化有较大的变动. 另外经过测试,条件 FP-tree 数据存储结构对减少模型 检索时间具有很好的作用. 4 结论 根据 GNSS 仿真的基本原理,在其服务化共享仿 真研究 的 基 础 上,结 合 仿 真 模 型 的 基 本 特 性,针 对 GNSS 分布式仿真环境中模型关联关系进行推理分析, 提出了一种针对平台中仿真模型的智能推荐方法,该 方法结合数据挖掘的相关技术,利用仿真模型的基本 特性,基本能够实现根据现有模型及仿真任务记录自 · 236 ·
范国超等:基于关联关系的仿真模型实时智能推荐方法 ·633 主推理,给出下一步用户所需仿真模型的参考模型集 ulation platform based on concept of cloud computing:cloud sim- 合,同时计算对应的模型关联关系度并排序,基本实现 ulation platform.J Syst Simul,2009.21(17):5292 了仿真模型的实时智能推荐功能。仿真验证结果和对 (李伯虎,柴旭东,侯宝存,等.一种基于云计算理念的网络 化建模与仿真平合“云仿真平台”.系统仿真学报,2009,21 比分析表明,该方法针对仿真模型推荐时运行时间短, (17):5292) 推荐结果准确度高,方法具有很好的效果,且可行性较 [12]Huang A X,Feng X W,Li JS,et al.Aviation simulation archi- 强.符合GNSS仿真任务设计中对模型推荐的实时性 tecture based on cloud computing platform.J Syst Simul,2011, 的功能和性能需求.在后续研究中将针对方法优化, 23(Suppl1):106 提高计算效率,减少计算空间,并结合模型的语义管理 (黄安样,冯晓文,李劲松,等.基于云计算平台的航空兵训 进行优化设计,进一步提高智能推荐算法在GNSS分 练仿真体系结构.系统仿真学报,2011,23(增刊1):106) [3] Armbrust M,Fox A,Griffith R,et al.Abore the Clouds:A 布式仿真环境中的性能 Berkely View of Cloud Computing.University of California Berke- 参考文献 ley,2009 [1]Armbrust M,Fox A,Griffith R,et al.A view of cloud compu- 14]Hu CS.Study on Key Techniques of Integrated Design Environ- ting.Commun ACM,2010,53(4)50 ment for Complex Product Based on Service-oriented Architecture 2]Mell P,Grance T.The NIST Definition of Cloud Computing.NIST [Dissertation].Beijing:Beijing Institute of Technology,2014 Special Publication 800-145,2011 (胡春生.面向服务的复杂产品集成设计环境关键技术研究 3]Baun C,Kunze M,Nimis J,et al.Cloud Computing Web-based [学位论文].北京:北京理工大学,2014) Dynamic it Services.Berlin:SpringerVerlag,2011 [15]Hu C S,Xu C D,Fan G C,et al.A simulation model design 4]Miller M.Cloud Computing:Web-Based Applications that Change method for cloud-based simulation environment.Adr Mech Eng, the Way You Work and Collaborate Online.Indianapolis:QUE 2013(8):1 Publishing Company,2008 [16]Hu C S,Xu C D,Zhang P F,et al.Study on simulation model [5] Chen T.On cloud computing theory and its technique.J virtualization in cloud computing environment.Huazhong Uni Chongqing Jiaotong Univ Soe Sci,20099(4):104 Sci Technol Nat Sci,2012.40(Suppl 1)135 (陈涛.云计算理论及技术研究.重庆交通大学学报(社会科 (胡春生,许承东,张鹏飞,等.云计算环境下仿真模型资源 学版),2009,9(4):104) 虚拟化研究.华中科技大学学报(自然科学版),2012,40 6]Buyya R,Ranjan R,Calheiros R N.Modeling and simulation of (增刊1):135) scalable cloud computing environments and the CloudSim toolkit: 7] Park D H,Kim H K,Choi I Y,et al.A literature review and challenges and opportunities /International Conference on High classification of recommender systems research.Expert Syst Appl, Performance Computing Simulation.IEEE,Leipzig,2009:1 2012,39(11):10059 7]Fang B L,Yin X,Tan Y,et al.The contributions of cloud tech- h8] Borras J,Moreno A,Valls A.Intelligent tourism recommender nologies to smart grid.Renewable Sustainable Energy Rev,2016, systems:a survey.Expert Syst Appl,2014,41 (16)7370 59:1326 19] Chen S N,Qian H Y,Gu J Y.A recommender system for mobile [8]Vrba P,Marik V,Siano P,et al.A review of agent and service-- commerce based on relational leaming //9th International Work- riented concepts applied to intelligent energy systems.IEEE Trans shop Multi-isciplinary Trends in Artificial Intelligence,MIWAl mdm,2014,10(3):1890 2015.Fuzho,2015,9426:415 [9]Tsai W T,Bai X Y,Huang Y.Software-s-uservice (SaaS): [20]Han JS,Kim G J.A method of intelligent recommendation using perspectives and challenges.Sci China Inf Sci,2014,57(5):1 task ontology.Cluster Comput,2014,17 (3):827 [10]Wu D Z,Greer M J,Rosen D W,et al.Cloud manufacturing: 1]Dai C Y,Chen L.An algorithm for mining frequent closed item- strategic vision and state-of-the-art.J Manuf Syst,2013,32 sets in data stream.Phys Procedia,2012,24:1722 (4):564 22]Tan P N,Steinbach M.Kumar V.Introduction to Data Mining [11]Li B H,Chai X D,Hou B C,et al.Networked modeling sim- Beijing:China Machine Press,2010:363
范国超等: 基于关联关系的仿真模型实时智能推荐方法 主推理,给出下一步用户所需仿真模型的参考模型集 合,同时计算对应的模型关联关系度并排序,基本实现 了仿真模型的实时智能推荐功能. 仿真验证结果和对 比分析表明,该方法针对仿真模型推荐时运行时间短, 推荐结果准确度高,方法具有很好的效果,且可行性较 强. 符合 GNSS 仿真任务设计中对模型推荐的实时性 的功能和性能需求. 在后续研究中将针对方法优化, 提高计算效率,减少计算空间,并结合模型的语义管理 进行优化设计,进一步提高智能推荐算法在 GNSS 分 布式仿真环境中的性能. 参 考 文 献 [1] Armbrust M,Fox A,Griffith R,et al. A view of cloud computing. Commun ACM,2010,53( 4) : 50 [2] Mell P,Grance T. The NIST Definition of Cloud Computing. NIST Special Publication 800 - 145,2011 [3] Baun C,Kunze M,Nimis J,et al. Cloud Computing Web-based Dynamic it Services. Berlin: Springer-Verlag,2011 [4] Miller M. Cloud Computing: Web-Based Applications that Change the Way You Work and Collaborate Online. Indianapolis: QUE Publishing Company,2008 [5] Chen T. On cloud computing theory and its technique. J Chongqing Jiaotong Univ Soc Sci,2009,9( 4) : 104 ( 陈涛. 云计算理论及技术研究. 重庆交通大学学报 ( 社会科 学版) ,2009,9( 4) : 104) [6] Buyya R,Ranjan R,Calheiros R N. Modeling and simulation of scalable cloud computing environments and the CloudSim toolkit: challenges and opportunities / / International Conference on High Performance Computing & Simulation. IEEE,Leipzig,2009: 1 [7] Fang B L,Yin X,Tan Y,et al. The contributions of cloud technologies to smart grid. Renewable Sustainable Energy Rev,2016, 59: 1326 [8] Vrba P,Marik V,Siano P,et al. A review of agent and service-oriented concepts applied to intelligent energy systems. IEEE Trans Ind Inf,2014,10( 3) : 1890 [9] Tsai W T,Bai X Y,Huang Y. Software-as-a-service ( SaaS) : perspectives and challenges. Sci China Inf Sci,2014,57( 5) : 1 [10] Wu D Z,Greer M J,Rosen D W,et al. Cloud manufacturing: strategic vision and state-of-the-art. J Manuf Syst,2013,32 ( 4) : 564 [11] Li B H,Chai X D,Hou B C,et al. Networked modeling & simulation platform based on concept of cloud computing: cloud simulation platform. J Syst Simul,2009,21( 17) : 5292 ( 李伯虎,柴旭东,侯宝存,等. 一种基于云计算理念的网络 化建模与仿真平台: “云仿真平台”. 系统仿真学报,2009,21 ( 17) : 5292) [12] Huang A X,Feng X W,Li J S,et al. Aviation simulation architecture based on cloud computing platform. J Syst Simul,2011, 23( Suppl1) : 106 ( 黄安祥,冯晓文,李劲松,等. 基于云计算平台的航空兵训 练仿真体系结构. 系统仿真学报,2011,23( 增刊 1) : 106) [13] Armbrust M,Fox A,Griffith R,et al. Above the Clouds: A Berkely View of Cloud Computing. University of California Berkeley,2009 [14] Hu C S. Study on Key Techniques of Integrated Design Environment for Complex Product Based on Service-oriented Architecture [Dissertation]. Beijing: Beijing Institute of Technology,2014 ( 胡春生. 面向服务的复杂产品集成设计环境关键技术研究 [学位论文]. 北京: 北京理工大学,2014) [15] Hu C S,Xu C D,Fan G C,et al. A simulation model design method for cloud-based simulation environment. Adv Mech Eng, 2013( 8) : 1 [16] Hu C S,Xu C D,Zhang P F,et al. Study on simulation model virtualization in cloud computing environment. J Huazhong Univ Sci Technol Nat Sci,2012,40( Suppl 1) : 135 ( 胡春生,许承东,张鹏飞,等. 云计算环境下仿真模型资源 虚拟化研究. 华中科技大学学报( 自然科学版) ,2012,40 ( 增刊 1) : 135) [17] Park D H,Kim H K,Choi I Y,et al. A literature review and classification of recommender systems research. Expert Syst Appl, 2012,39( 11) : 10059 [18] Borràs J,Moreno A,Valls A. Intelligent tourism recommender systems: a survey. Expert Syst Appl,2014,41( 16) : 7370 [19] Chen S N,Qian H Y,Gu J Y. A recommender system for mobile commerce based on relational learning / / 9th International Workshop Multi-disciplinary Trends in Artificial Intelligence,MIWAI 2015. Fuzhou,2015,9426: 415 [20] Han J S,Kim G J. A method of intelligent recommendation using task ontology. Cluster Comput,2014,17( 3) : 827 [21] Dai C Y,Chen L. An algorithm for mining frequent closed itemsets in data stream. Phys Procedia,2012,24: 1722 [22] Tan P N,Steinbach M,Kumar V. Introduction to Data Mining. Beijing: China Machine Press,2010: 363 · 336 ·