最小能耗优化云模型中的动态图挖掘方法(2)

　　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所示。

　　表3硬件配置

　　硬件名称硬件描述数量

　　2xE5560QC2.8Hz处理器,8GB

　　机架服务器PC3~8500DDR3内存，2x146GB10KB硬盘

　　高性能HS22刀片服务器，2x1

　　刀片服务器E5560QC2.8Hz处理器，8GBPC3~8500DDR3内存，2x146GB10KB硬盘10

　　光纤交换机中心存储光纤交换机含24x4GB端口，短波SFP模块2

　　存储阵列DS5300存储服务器，28TB光纤硬盘1

　　交换机Cisco6509,6电口交换机，双冗余电源1

　　将1台机架服务器作为主控结点，其他10台刀片服务器作为计算结点，通过光纤交换与存储陈列实现数据的快速存储与访问，可以满足海量数据挖掘的需求。

　　实验的软件环境为Linux操作系统，传统云平台环境是HadoopO.20.203与HadoopStudio,Java开发工具Eclipse,采用1.6.x版本，改进后的云计算环境是改进后的HadoopO.20.203,在其中加入了启发式搜索算法的中间件。

　　实验数据集分为人工模拟数据集与真实数据集2种。人工模拟数据集采用通用的图生成器来生成，可通过不同参数控制图的产生，并人为给每条边赋予一个权值并满足均值为m,方差为d2的正态分布。真实数据集采用NC/-//V化合物数据，可以从http://dtp.nci.nih.gov/上下载得到，对数据集进行预处理操作，将化合物的边与结点进行规范化命名以及根据化合物类别与边的属性添加边权值。

　　5.2实验设计与结果分析

　　实验共分为两部分，第一部分实验在模拟数据集上进行,首先生成不同规模的动态图数据库，生成参数设置为：GDB:MT40L500i22V6E6C0.2P0.5,数据规模为：D10,D15,D20,D25,D30,在最小能耗优化云与传统云平台中进行实验，在计算系统能耗时,需要对系统的运行情况进行监控，记录计算结点的数量、任务个数、执行时间等运行要素以得到系统空闲能耗与执行能耗，并最终得到平均能耗。实验结果如图3、图4所示。?

　　图3表示在传统云平台与最小能耗优化云中进行动态图挖掘的平均能耗对比，可以看出，最小能耗优化云的平均能耗要优于传统云平台，并且随着数据规模的增大，能耗优势愈明显。而能耗的优化并没有影响到算法在平台中的执行效率，图4给出了不同规模数据库在最小能耗云模型中的运行结果,从中可以看出，随着数据规模的增大，算法的加速性能越好，原因在于数据越多，所需的计算结点数量与计算任务也会越多，结点的空闲时间与消耗成本也会越少，可以充分发挥结点的计算性能，因此整个系统加速性能就越好。同时结点的数量也会影响到加速性能，结点数越多，系统计算性能越强，加速性能也就越好。

　　接着生成不同复杂程度的动态图数据库，主要调整动态图的边权值p使边的存在可能增加，生成参数设置为GDB:D10MT40L500i22V6,复杂度设置：CR1=E6C0.2P0.5,CR2=E7C0.3P0.6,CR3=E7C0.4P0.7,CR4=E8C0.5P0.8,CR5=E8C0.6P0.9。在最小能耗优化云与传统云平台中进行实验，平均能耗实验结果如图5所示。

　　从图5可知，随着边权值与图复杂程度的增加,系统的能耗也随之增加,这是由于边权值增加直接导致边的存在概率增加，候选子图在动态图数据库中的期望支持数也会增加，因此将会产生更多的频繁子图模式，所以算法需要更大的时间成本,导致了系统平均能耗的增加。同时图越复杂,计算结点的计算量会随之增加，如大量的子图同构测试等，因此系统的执行能耗与平均能耗也会增加。

　　第二部分实验在真实数据环境下测试最小能耗优化云模型与动态图挖掘算法。获取44000多个NCI4HV化合物数据并进行预处理操作，预处理后的化合物结构至少包含100个~200个结点与边。将所有数据分解成5个小的数据集，大小分别为5X103,6x103,8x103,10x103,14x103。在最小能耗优化云模型与传统云平台下进行实验，结果如图6所示。

　　从实验结果可以看出，在真实环境下，最小能耗优化云的能耗明显优于传统云计算平台，这是因为NCI4HV化合物为大图结构，结点与边的数量远大于模拟数据，因此在挖掘频繁子图模式时，需要更多的计算成本与消耗更多的系统资源，而最小能耗优化云模型能有效地对任务与资源的分配进行合理调配，在保证运行效率的前提下，最大程度减少了系统的能耗。将图6与图3、图5的实验结果进行对比可以发现，在数据量多的模拟数据集情况下，能耗反而远小于数据量少的真实数据集，这也正好验证了在复杂大图模式下的图挖掘需要付出更多的系统运行成本，消耗更多的系统资源。

　　6结束语

　　本文提出一种基于最小能耗优化的云模型与大规模动态图挖掘算法，该算法解决了海量图挖掘问题。为了改进传统云计算平台的任务随机调整策略，提出总消耗成本目标函数,并设计基于启发式的任务动态分配算法，以达到系统资源消耗的最小化。并且改进图挖掘串行执行方式，提出一种基于MapReduce的大规模动态图挖掘算法，提高了动态图挖掘效率。实验结果表明，该算法具有较高的运行效率，同时在一定程度上降低了系统能耗。下一步将继续优化最小能耗云模型与动态图挖掘算法,以进_步提升挖掘效率与降低系统能耗。同时可以扩展最小能耗云模型,并将其应用于其他数据类型的海量数据挖掘中。

　　参考文献

　　[1]覃雄派，王会举，杜小勇，等.大数据分析一一RDBMS与MapReduce的竞争与共生J.软件学报，2012,23(1)：32-15.

　　[2]TDWIChecklistReportIBigDataAnalytics[EB/OL].

　　(2010-08-40).httpl//tdwi.org/research/2010/08Big-Data-Analytics.aspx.

　　[3]ZouZhaonian,LiJianzhong,GaoHong,etal.MiningFrequentSubgraphPatternsfromUncertainGraphDataJ.IEEETransactionsonKnowledgeandDataEngineering,2010,22(9)：1203-1218.

　　[4]PotamiasM,BonchiF,GionisA,etal.K-learestNeighborsinUncertainGraphs[C]//ProceedingsofVLDBJ10.Singapore：Is.n.],2010:9974008.

　　[5]张海杰，姜守旭，邹兆年.不确定图上的高效top-^近邻查询处理算法J].计算机学报，2011,34(10):18854896.

　　[6]HuaM,PeiJ.ProbabilisticPathQueriesinRoad

　　Networks：TrafficNncertaintyAwarePathSelection//Proceedingsofthe13thInternationalConferenceonExtendingDatabaseTechnologyLausanne.Bern,

　　Switzerland:&.n.],0101347-358.

　　[7]李鸣鹏,邹兆年，高宏，等.不确定图上期望最短距离的计算J].计算机研究与发展，2012,49(10):2208-2220.

　　[8]蔡伟,张柏礼，吕建华.不确定图最可靠最大流算法研究J].计算机学报,2012,35(11):2371~2380.

　　[9]YildirimH,ChaojiV,ZakiMJ.GRAIL：AScalableIndexforReachabilityQueryiesinVeryLargeGraphs［J].TheVLDBJournal,2012,21(4)：509-534.

　　[10]AtreM,ChaojiV,ZakiMJ.BitPathLabelOrder

　　ConstrainedReachabilityQueriesoverLargeGraphsC]//

　　(上接第22页）

　　[3]HerlockerJL,KonstanJA,BorchersA,etal.AnAlgorithmicFrameworkforPerformingCollaborativeFiltering[C]//Proceedingsofthe22ndAnnualInternationalACMSIGIRConferenceonResearchandDevelopmentinInformationRetrieval.NewYork,USA：ACMPress,1999：230-237.

　　[4]Castro-SchezJJ,MiguelR,VallejoD,etal.AHighlyAdaptiveRecommenderSystemBasedonFuzzyLogicforB2CE-commercePortals[J].ExpertSystemswithApplications,2011,38(3)：2441-2454.

　　[5]SarwarB,KarypisG,KonstanJ,etal.Applicationof

　　DimensionalityReductioninRecommenderSystemA

　　CaseStudy[C]//ProceedingsofWebMiningforE-commerceWorkshop.NewYork,USA:ACMPress,2006:16-20.

　　[6]彭石,周志彬，王国军.基于评分矩阵预填充的协同过滤算法J].计算机工程,2013,39(1):175~178.

　　[7]李鹏飞,吴为民.基于混合模型推荐算法的优化J].

　　Proceedingsofthe19thInternationalConferenceonWorldWideWeb.NewYork,USA：ACMPress,2012：41-50.

　　11]SonJ,ChoiH,ChungYD.Skew-tolerantKeyDistributionforLoadBalancinginMapReduceJ].IEICETransactionsonInformationandSystems,2012,95(2):677-680.

　　12]GrzegorzM,AusternMH,BikAJCetal.Pregel:ASystemforLarge-scaleGraphProcessingC]//Proceed-ingsofSIGMOD'10.Indianapolis,USA:[s.n.]2010:135445.

　　13]AveryC.Giraph:Large-scaleGraphProcessing

　　InfrastructiononHadoop［C]//ProceedingsofHadoopSummit.SantaClara,USA:&.n.],0111215-222.

　　14]TysonC,NeilC,PeterA,etal.MapReduceOnline[C]//ProceedingsofNSDI'10.SanJose,USA:[s.n.],2010:33-48.

　　[15]谭一鸣，曾国荪，王伟.随机任务在云计算平台中能耗的优化管理方法J].软件学报，2012,23(2):266-278.

　　16]LeeYC,ZomayaAY.EnergyConsciousSchedulingforDistributedComputingSystemsUnderDifferentOperatingConditions［J].IEEETransactionsonParallelandDistributedSystems,2011,22(8):13744381.

　　17]HeSJ,GuoL,GuoYK,etal.ElasticApplicationContainer：ALightweightApproachforCloudResourceProvisioning［C]//ProceedingsofIEEEAINA'12.WashingtonD.C./USA：IEEEPress,2012：15-22.

　　18]KuehnhausenM,FrostVS,MindenGJ.FrameworkforAssessingtheTrustworthinessofCloudResources［C]//ProceedingsofIEEECogSIMA'12.WashingtonD.C.,USA：IEEEPress,2012：142-145.