|
图2最小能耗优化云模型 Driver为主控结点（机架服务器），Task1,Task2等分别表示计算任务列表T_List中输入任务，TL是T_List的简称,i1,i2等分别计算结点（刀片服务器），tl是计算任务列表,/nitialOp()为系统初始化操作函数,将计算任务列表T_List放入到任务调度队列TL中，根据参数设置表1相关参数。ChooseOp()为随机轮流选择与轮盘赌选择相结合的算法，使得搜索结点与最优结果相接近，并且避免可早地陷入到局部最优。CrossverOp()为多点交叉操作函数。UpdateOp()为更新操作函数，对新的分配方案进行随机更新,以增强方案的多样性与扩展搜索空间。 4动态图挖掘方法 4.1动态图 在最小能耗优化云中进行动态图挖掘首先要解决动态图的表示与挖掘算法的并行化问题。下面给出相关概念与定义。 定义1(动态图）令五元组G=(V,E,U,P)表示一个动态图G5,其中，V表示顶点集合;E表示边的集合;乏为标记集合;映射A:(VUE)-$表示入每个顶点与每条边分配一个标记;P为权值集合。在时间段te=(t-t')内，图G=(VE)由一种状态转变为另一个状态G'=(V',E'),若满足条件：（1)V'=V;(2)E'=E-E1其中，(Vx V)-E,则称图G为动态图,G'为转变图。 图的转变本质是边与结点的产生与消失，将权值集合P作为边的存在可能性函数,定义为(0,1],则动态图就是_种所有边带权值的图结构。如果所有边的权值为1,表示图中边不会发生改变，图是确定的，因此确定图是一个所有边权值为1的特殊动态图。 动态图数据库是动态图的集合，令GDB={^, G2,…，表示一个动态图数据库，其中G2,…，分别表示不同的动态图。在动态图数据库中挖掘频繁子图模式需要考虑树的变化特征，同时传统的支持度定义方法在动态图挖掘中也并不适用，因此本文需要根据图的变化特征对支持度进行重新定义。 定义2(动态图的转变概率）给定一个动态图G=(VE)和一个转变图G'=在时刻t下 转变图G'出现的概率为H: P((G/〇-)^)=ne)on(1-p(e)) eeEeeE*-E (13) 其中,P(e)表示边的转变概率,本文假设动态图中不同边的存在与否是相互独立的，根据概率统计可知：对于动态图G,可用函数P((G/G')|t)表示在样本空间的S(G)的概率分布，其中S(G)={G'1,G'2,ooo,G'"}表示图的集合。 定义3(S(G)转变概率）给定一个动态图数据库GDB和S(G),在有效时间段te=(t-t')内S(G)出现的概率为： n P((GDB/S{G)V)|te)=nG,/G')(14) 定理对于_个给定的动态图数据库GDB,函数P((GDB/S(G)V)|te)定义在样本空间S(GDB)上的概率分布,S(GDB)表示动态图数据库下所有S(G)的集合。 定义4(期望支持度）对于一个给定的动态图数据库GDB,在有效时间段te内子图g在GDB中的期望支持度定义为： n ESGDB(g|te)=XS,oPCS,|te)(15) i=1 或： ESGDB(g|te)=XSq(g)o qeSTGDB) P((GDB/q)|te)(16) 其中，q=S(G),子图g在动态图G中出现，当且仅当g存在于S(G)中任意一个图中，根据概率统计,将上述公式转化以简化计算过程，得到下式： 1|GDB| ESGDB(g|te)=|GDB|XP((g.G)|te)(17) 定义5(动态支持度）对于给定的动态图数据库GDB,子图g在时间段te内的期望支持度为ESGDB(gIte),则称ESGDB(gIte)为g的动态支持度。 将动态图的期望支持度作为挖掘支持度，不仅可以体现动态图的变化特征，而且根据定义，转变概率与期望支持度都满足Apriori性质，因此在动态图挖掘过程中可以利用Apriori性质进行剪枝，提高挖掘的效率。 4.2算法基本思想 与传统频繁子图挖掘算法相比，动态图挖掘不仅需要考虑图搜索空间，而且还需考虑图的变化特征。在给定动态图数据库GDB与时间段te内，算法进行深度优先搜索,对于所有子搜索空间，首先得到频繁边与结点，然后进行边的扩展生成候选子图g,在生成完成后,计算候选图在GDB与时间段te内的动态支持度ESGDB(g|te),若ESGDB(g|te)大于等于最小支持度阈值，则g是频繁的，并继续深度优先搜索g的所有超图，若ESGDB(gIte)小于最小支持度，则g是非频繁，根据前面的定义，动态支持度满足Apriori性质，因此可知g的所有超图非频繁,则停止该次深度优先搜索，并返回到上一级搜索空间。在候选子图生成过程中，考虑到动态支持度的计算公式,在计算g动态支持度ESGDB(gIte)时，需要计算g的存在概率P((g.G)k),而对任意2个子图gt，且g^g,有ESGDB(gIU^ESGDB(gIU+ESGDB(g1IU,右边 是子图g动态支持度上限，而在搜索空间中，gi的支持度要先于g得到，因此可以利用先验知识来对候选子图进行裁剪操作。 在算法执行过程中，利用线性表随机访问与hash表快速查找的特性，设计一个基于线性表与hash表的图数据存储结构，将挖掘过程产生的数据存储保存起来，其中hash表存储频繁子图信息，线性表指向hash表。利用该结构可以快速存储频繁子图，也可以较快获得频繁子图，有利于图的快速匹配与候选子图的剪枝操作。 基于上述算法分析过程，本文采用MapReduce的分布式编程模型来设计动态图挖掘算法，并将算法应用于最小能耗优化云模型中，以达到系统能耗与性能的最优。主要包括如下3个阶段： (1)并行扫描动态图数据库，得到边集合E_List与结点的集合V_List。 (2)串行构建基于哈希表结构的频繁边集FE_List与频繁1子图F1_List。 (3)并行挖掘频繁子图。 4.3算法设计 根据最小能耗优化云模型，选取一个计算结点作为主控结点。第一阶 段挖掘边集合E_List与结点的集合V_List,算法MEV(MiningEdgeandVertex)描述如下： 算法2MEV 输入动态图数据库GDB 输出边集合E_List与结点的集合V_List (1)Map操作 扫描动态图数据库GDB,将图进行格式化<id,G>,其中，id为图标号,G为图字符串，分别统计结点与边的数量并作为中间分键值对<eIv,num>,并将此键值对发送到Reduce操作。 (2)Reduce操作 接受键值对并进行扫描操作，按节点与边的标识进行升序排列，将相同标识的结点与边进行合并，统计边与结点，以及边的权值，分别添加到边集合与结点的集合V_List中。 上述过程为并行执行过程，获得结点与边的效率较高，特别是在海量数据环境下，本文算法较传统算法效率提升显著。在得到所有的边与结点之后，通过一个串行算法获得频繁边集与频繁点集F1_List,由主控节点Driver随机选取一个计算结点来执行。算法GF1(GenerateFrequent1)执行过程如下： 算法3GF1 输入E_List与V_List,最小支持度s输出频繁边集与频繁点集F1_List (1)构建图数据存储结构ArrayList<Pair<int, string>>。 (2)扫描E_List与V_List,分别统计支持度计数，并根据最小支持度s,判断是否频繁，若频繁则将边与点添加到FE_List与F1_List中。 将得到的FE_List与F1_List进行排序，按支持度大小升序，若相同则按边的权值降序，并依次添加到图数据存储结构中。 在得到所有的频繁边与频繁点之后，进行候选子图的扩展,深度优先搜索其他频繁子图，直到产生所有的频繁子图，此过程为并行过程，并且需要扫描 动态图数据库。算法MFG(MiningFrequentGraph)执行过程如下： 算法4MFG 输入动态图数据库GDB,最小支持度s, List、F1_List、时间段te 输出频繁子图集合FG_List (1)Map操作 并行扫描GDB,将图存储到hash表中，将List与F1_List中频繁边与点对应的图id为键，频繁结点与边为值作为键值对发送到Reduce操作。 (2)Reduce操作 扫描键值对，获得频繁边与点，对边进行深度优先扩展生成候选子图，访问图数据存储结构与hash表计算其动态支持度，如果小于s则非频繁并返回上一层继续搜索，否则将其添加到FG_List中，并继续扩展点生成候选，若点的数量大于等于3,则需先判断，上限支持度进行剪枝,如果上限小于s,则非频繁,否则再计算其动态支持度。 5实验结果与分析 5.1实验环境与实验数据 实验验证任务分配算法、最小能耗优化云模型以及动态图挖掘算法的有效性与运行效率等。在学校工程实训中心搭建实验所需的软硬件环境，其中硬件环境如表3所示。 |
|
核心期刊网（www.hexinqk.com）秉承“诚以为基，信以为本”的宗旨，为广大学者老师提供投稿辅导、写作指导、核心期刊推荐等服务。 核心期刊网专业期刊发表机构，为学术研究工作者解决北大核心、CSSCI核心、统计源核心、EI核心等投稿辅导咨询与写作指导的问题。 投稿辅导咨询电话：18915033935 投稿辅导客服QQ： 投稿辅导投稿邮箱：1003158336@qq.com |
| 你好，欢迎来到！ 设为首页 ｜收藏本站 | ||
|
