云计算环境下的负荷特征曲线提取

　　【 摘 要 】 文章针对电网运行产生的数据呈爆炸式增长，EMS系统有效信息往往淹没在海量数据中这一问题，提出一种云计算模式下的聚类分析处理方法，基于Hadoop平台的MapReduce计算模型与分布式文件存储，将系统聚类法进行拆分，在云环境中对多个计算模块进行并行分析。作为试验性验证，提取某大用户近三年的负荷特征曲线，选取不同数据量、不同节点数，进行算法加速比的测试。结果表明，在云计算架构中该算法可以有效提高计算效率，适用于电力系统海量数据的挖掘分析。
　　1 引言
　　电力负荷特征曲线表征了同类负荷曲线的整体特征，在负荷坏数据辨识与修正、电力负荷预测、负荷建模、需求侧管理等领域有重要作用。聚类分析是一种常用的特征曲线提取方法，但是在面对电力系统海量数据时，现有算法在时间和空间复杂度上不能很好满足需求，解决该问题的一种有效方法是将串行算法并行化处理。
　　作为一种崭新的计算模式，云计算是并行计算、分布式计算与网格计算的发展，在海量数据处理方面具有与生俱来的优势。云计算是由接入到Internet中的一系列硬件资源提供的服务，它将计算任务分配到由大量计算机构成的资源池中，使云中的应用程序获得并行计算支撑以及易扩展的存储空间，来自于不同平台的用户可以共享云中的资源。目前，主流的云计算架构主要在Hadoop平台上实现，Apache的开源项目Hadoop实现了分布式文件系统与MapReduce计算模型。开源项目Mahout实现了基于MapReduce的k-means聚类计算，但是k-means方法要求以聚类个数作为参数进行运算，对于电力负荷数据而言，由于无法事先确定可以分为几类，导致应用存在一定的局限性。针对这一问题，以系统聚类法代替k-means聚类方法，避免聚类参数的不确定问题。在此基础上，提出云计算环境下的系统聚类并行算法，提高海量数据处理的计算效率。
　　2 系统聚类法
　　系统聚类法是本文算法的基础，其完全依据距离进行聚类，不需要事先明确聚类个数，其具体有几个步骤。
　　1） 将每个初始样品作为一类，计算类之间的距离，距离计算方法有欧氏距离、曼哈顿距离、切比雪夫距离等，形成距离矩阵D（0）。它是一个对角元素为0的对称矩阵，设Gi为第i个聚类。
　　2） 寻找D（0）中的最小元素，设其为D（KL），其中K为矩阵行号，L为列号，则将GK和GL合并成一类，记为GM，有GM = {GK，GL}。
　　3） 计算GM与其他类GJ之间的距离，更新距离矩阵D（0），将GK和GL所在行和所在列合并成一个新行新列，对应于GM，新行新列上的距离由递推公式计算得到，其余矩阵元素值不变，得到的新距离矩阵记为D（1）。
　　4） 对D（1）重复上述对D（0）的2步操作，得到距离矩阵D（2）；依此迭代处理，直至所有元素合并成一类，或距离矩阵中的最小距离大于设定阈值为止。
　　距离计算可以采用多种方法，不失一般性，本文采用中间距离法作为距离递推公式。
　　3 MapReduce
　　在云计算的各种编程模型中，MapReduce逐渐成为主流。MapReduce是一种可用于海量数据处理的编程模型，在Hadoop平台下，每个MapReduce工作单元被定义为一个作业（Job）。有两类计算节点参与作业的执行，一个jobtracker（相当于作业调度机构）和若干个tasktracker（子任务）。后者以心跳服务的形式，不断将执行进度向jobtracker报告。
　　输入数据被划分成等长度数据块（输入分片input split），与一个map任务对应。map和reduce函数的输入输出遵从以下格式：
　　map：（K1，V1）→ list（K2， V2）；
　　reduce：（K2，list（V2））→ list（K3，V3）。
　　从map输出到reduce输入之前的处理过程称为混洗（shuffle），混洗阶段完成map输出的排序（sort），分区，合并（merge）等，并最终形成（K2，list（V2））形式的键值对供reduce函数获取，经处理后输出至分布式文件系统中（DFS，Hadoop中称为HDFS），整个过程如图1所示。
　　图2所示为Hadoop平台下，MapReduce作业的原理：客户节点运行MapReduce程序，计算输入分片，并将运行所需的资源文件（包括Jar文件，配置文件以及输入分片）复制到HDFS中，然后向jobtracker提交作业；jobtracker将收到的作业放入内部队列，交予作业调度器处理，作业调度器在空闲的时候获取输入分片，根据分片数创建map任务，根据程序设置的reduce数量，创建等量的reduce任务，交予tasktracker群执行；tasktracker从HDFS获取需要的资源，对每个任务启动一个新的JVM进程，通过循环定期发送心跳告知jobtracker其是否存活以及传递消息，reduce任务完成后，将结果写入HDFS，清除诸如map输出到本地磁盘的中间结果，Job client从HDFS获取结果信息供后续处理，一次MapReduce作业完成。
　　4 MapReduce框架下的系统聚类法
　　将系统聚类法进行并行化处理，可以有效提高海量数据处理的计算效率。系统聚类的计算过程包括数据初始化、距离矩阵初始化、迭代计算过程。迭代计算又包括距离矩阵最小元素的查询、距离矩阵的更新（包括新值计算与矩阵降维）、聚类数据的合并。
　　聚类数据和距离矩阵的初始化需要用到所有数据，将其进行并行化处理需要很大的网络带宽消耗和空间复杂度，而且其在算法中只执行一次，对于整个算法时间消耗很小（表1（a）显示了对于1794个24维负荷矢量的系统聚类，串行算法的时间消耗分布），因此仍旧采用串行方法作为此阶段算法。
　　在每次迭代过程中，寻找最小元素的时间复杂度为O（n2），此阶段适合用MapReduce框架处理，本文中将该作业称为JobFindMin。考虑到距离矩阵是对角元为0的对称矩阵，只需存储以及处理不包括对角元的上三角或下三角部分，采用以行为单位，进行输入分片的切分过程中，会导致每个分片包含的数据个数不统一，造成各map负载不均匀，因此将距离矩阵重新组合，以每行k个元素的形式重新生成输入文件，此时文件中一行可能包含矩阵多行的数据或矩阵一行的一部分，因此，文件中每个元素都需要带有行列信息。map函数的输出键值对类型为，MatrixElement是实现了WritableComparable接口的矩阵元素三元组。对每个map设置一个combiner以保证最后输出到网络的数据个数为1，以此降低网络传输消耗；reduce函数设置为1个，其汇总combiner输出的最小值，进一步计算这些数据之中 的最小值，以获取最短距离及其行列号。
　　聚类数据的合并是将最小距离行列号对应的数据集合进行合并，合并过程只需移动相应的指针，计算量很小（在串行算法迭代中占用的时间如表1（b）所示，仅有1%），对其仍旧采用串行算法。
　　在矩阵更新阶段前，根据作业JobFindMin的输出结果（行i、列j、值v），形成只包含距离矩阵第j行和第j列数据的矩阵，本文中称为关联矩阵。对于可变法和重心法等需要其他额外参数的公式需要形成更多信息文件。矩阵更新是最费时的阶段，将其利用MapReduce框架处理，作业名为JobUpdate。map输入同JobFindMin，对于每个map设置setup函数，读取关联矩阵和其他信息文件，map函数的输出为，对应为距离矩阵元素的行列值和元素值。
　　map函数对于每个输入的矩阵元素行列号进行判断，如果其在关联矩阵中存在，则将其抛弃（对应于矩阵降维）；如果其需要更新，则根据关联矩阵中对应的元素按照距离递推公式进行更新；否则原值写回。reduce函数设置为1个，其输出为，其作用仅为统一map的输出并且将数据进行格式化，封装成矩阵三元组的形式的矩阵单元集。
　　图3所示为选择中间距离法作为距离递推公式时两个作业的实现细节，其中距离矩阵以三元组链表形式存储于客户端内存。图4所示为完整的算法流程图。
　　5 仿真分析
　　5.1 性能测试
　　采用的实验平台由若干台CPU采用英特尔i5-3210M的计算机组成，Linux 32位操作系统，Hadoop版本1.1.2，JDK版本1.7.0，采用千兆以太网通信。实验中采取加速比作为主要评价指标，对于10GB、30GB的24维数据，实验结果如表2所示。
　　表2结果表明，算法加速比随节点数增加近似以线性增长，同时，数据量越大，算法性能越好，这主要是由于每次启动一个MapReduce作业，系统需要启动一系列JVM，并通过网络传输数据，这需要消耗一定的时间，在节点数较少的情况下，算法并行度不高，并且相比于串行算法存在上述额外开销；同样，在数据量较少的情况下，串行算法本身需要的时间不多，并行化之后效率得不到显著提升，因此，该算法适合用于对大数据量高并发的处理。
　　5.2 特征曲线提取
　　特征曲线关注的是曲线的形状，对于两条曲线A = {xi}，B = {xi+ d}，其距离应为0，需要对每条曲线进行归一化处理，即
　　x'i= （i = 1， 2， … n） （1）
　　试中xi为曲线每点数据，xmin为最小值，xmax为最大值，x'i为归一化后的每点数据。
　　对某类用户近三年的负荷数据进行聚类，设置阈值为0.8，聚类后总共得到6类曲线，如图5所示。
　　其中，最后两类只包含一条曲线，且存在明显的不合理点，为坏数据。第一类包含的数据个数占了数据总量的95.04%，可以认定包含该用户的负荷特征曲线，取均值得到的该类用户的负荷特征曲线如图6所示。
　　图6表明，该类用户三年内的用电规律没有发生明显变化，最小负荷量出现在凌晨3-5点间，最大负荷出现在中午10-12点间，并在14-22点时间内保持较高用电量。
　　从聚类结果本身直接获得的信息量非常有限，其更大的用处体现在后续的数据综合处理中，如作为负荷预测，需求侧管理，负荷数据稽查等的数据清理与数据分类阶段的实用工具。
　　6 结束语
　　云计算是大数据时代的产物，近年受到越来越广泛的关注，在互联网搜索、移动通信等领域，已获得较大范围的应用，但在电力系统中的应用，尚且处于理论研究阶段。Hadoop作为一种云计算模型IaaS层，实现了分布式文件系统和并行计算模型，这是云计算技术中的两个关键技术。本文提出的基于MapReduce的系统聚类法主要实现了并行计算部分，数据主体部分还是采用普通的关系数据库存储，是一种串行与并行相结合的算法，串行部分完成数据量需求大但运行耗时少的操作（只需要操作指针），并行部分完成数据量需求少，运行耗时长的操作。总体上减轻了网络数据传输的负担，充分发挥了并行计算的优势。
　　在大数据时代，电力系统EMS中的数据量呈爆炸式增长，云计算的分布式存储模式可以很好解决这一问题，下一步工作中，将结合分布式数据库处理技术，从理论和实践两方面，充分发挥云技术在电力海量数据挖掘中的应用能力。
　　参考文献
　　[1] 顾民， 葛良全， 秦健. 基于改进ART2 网络的电力负荷脏数据辨识与调整[J]. 电力系统自动化， 2007， 31（16）： 70-74.
　　[2] 赵俊华， 文福拴， 薛禹胜， 林振智. 云计算：构建未来电力系统的核心计算平台[J]. 电力系统自动化， 2010， 34（15）： 1-8.