电力大数据预处理的属性约简方法

摘要

一种电力大数据预处理的属性约简方法，用于解决电力大数据属性约简的预处理问题。所述方法首先将电力系统中的属性视作变迁关系，属性值作为在相应变迁关系作用下的转换状态；然后把在某一顺序变迁关系组的转换下到达相同终止状态的一些变迁序列去掉中间的冗余状态，仅保留关键路径；最后将关键路径上的变迁关系解码为相应的属性输出。本发明将偏序理论与MapReduce框架有机结合在一起，不仅略过了传统启发式约简算法的求核过程，提高了约简算法的效率，而且能够确保电力数据集的原有信息不丢失，特别适于电力行业海量数据的并行化预处理。

说明书

技术领域

本发明涉及一种基于偏序的电力大数据属性约简方法，属电力技 术领域。

背景技术

随着智能电网建设和物联网技术在电力行业中的广泛应用，电力 数据的体量以爆炸性的速度增长。为了从这些海量数据中挖掘出对电 网管控起决定性作用的信息，就需要对这些海量数据进行层层筛选， 但这类操作需要耗费大量的时间；行之有效的方法就是对这些海量数 据进行预处理，而属性约简是其中的一个重要环节，现有的启发式属 性约简算法，诸如基于正区域的、基于边界域的及基于信息熵的算法 都是粗糙集算法的延伸，这些算法通过计算得到属性核，再把其余属 性按照重要程度从高到低的顺序依次添加到属性核中。传统的启发式 约简算法在处理小数据集时效率显著，但由于其处理方式是将要处理 的数据集一次性装入内存，随着数据规模的增大，出现了内存瓶颈问 题，导致算法的效率严重下降，而且，其在约简过程中要删除一些重 要性比较低的属性，容易造成决策表的部分有价值信息丢失。有的学 者将上述这些启发式算法应用在MapReduce框架下，虽然克服了内存 瓶颈问题，算法的效率有所提升，但依旧存在决策表有价值信息易丢 失的问题。传统的基于遗传算法的约简方法，又由于遗传算法本身的 复杂度，导致约简的效率偏低，即使将其应用在MapReduce框架下， 虽然在处理大规模数据集时具有可行性，但算法的效率依旧没有得到 很好的改善。

总之，现有的约简算法存在着效率偏低、容易丢失信息等不足， 而电力系统的运行、监测信息具有显著的并行性，传统约简方法不能 完全解决电力大数据属性约简的预处理问题，急需寻找新的适应并行 化处理的约简方法。

发明内容

本发明的目的在于针对现有技术之弊端，提供一种效率高且能够 确保电力数据集的原有信息不丢失的电力大数据预处理的属性约简 方法。

本发明所述问题是以下述技术方案实现的：

一种电力大数据预处理的属性约简方法，所述方法首先将电力系 统中的属性视作变迁关系，属性值作为在相应变迁关系作用下的转换 状态；然后把在某一顺序变迁关系组的转换下到达相同终止状态的一 些变迁序列去掉中间的冗余状态，仅保留关键路径；最后将关键路径 上的变迁关系解码为相应的属性输出。

上述电力大数据预处理的属性约简方法，所述方法包括以下步 骤：

a.把电力大数据集看作一个由三元组S＝(U,A,V)表示的电力系 统信息决策表，其中U作为论域，表示全体对象的有限非空集合； C是条件属性构成的集合，D是决策属性； V是属性a的值域，即V_a∈V，假设该决策表含有n个对象， 每个对象又包括m个条件属性，一个决策属性D；

b.把电力大数据集根据其决策属性D的不同取值划分等价类，若 决策属性D有k种不同取值则根据决策属性D的值划分等 价类如下：

$\left(\begin{array}{cccc}\left(\begin{array}{cccc}{V}_{c_{11}}& V_{c_{21}}& ...& V_{D_1}\\ V_{c_{12}}& V_{c_{22}}& ...& V_{D_1}\\ ...& ...& ...& ...\\ V_{c_{1i}}& V_{c_{2i}}& ...& V_{D_1}\end{array}\right)& \left(\begin{array}{cccc}{V}_{c_{11}}& V_{c_{21}}& ...& V_{D_2}\\ V_{c_{12}}& V_{c_{22}}& ...& V_{D_2}\\ ...& ...& ...& ...\\ V_{c_{1i}}& V_{c_{2i}}& ...& V_{D_2}\end{array}\right)& ----& \left(\begin{array}{cccc}{V}_{c_{11}}& V_{c_{21}}& ...& V_{D_k}\\ V_{c_{12}}& V_{c_{22}}& ...& V_{D_k}\\ ...& ...& ...& ...\\ V_{c_{1i}}& V_{c_{2i}}& ...& V_{D_k}\end{array}\right)\end{array}\right)$

其中，表示第j个对象在第i个属性上的取值；

c.将上述的k个不同等价类内的数据集分别再进行划分，根据 其数据量的大小依次划分为n₁,n₂,…,n_k个数据分片；

d.把步骤c划分好的各个数据分片内电力数据集中的每条记录 视作一个对象，各属性视为变迁关系，各属性值看作在相应变迁关系 作用下转换的中间状态，调用(n₁+n₂+…+n_k)台worker(集群中的计算 机)，分别将各数据分片内数据集的各个对象在相应的worker中从初 始状态O在各变迁关系的作用下朝着决策状态进行变换：

$O_j\stackrel{c_1}{\to }{V}_{c_{1j}}\stackrel{c_2}{\to }{V}_{c_{2j}}\stackrel{...}{\to }{V}_{c_{\mathrm{mj}}}\stackrel{D}{\to }{V}_{D_i},j\in [1,i]$

其中O_j表示第j个对象的初始状态且所有对象的初始状态量相 同，表示第j个对象在变迁关系c_i的作用下转换到的相应中间状 态，为初始状态O_j经各变迁关系c₁,c₂,…,c_n,D，变换之后的终止状 态；

e.针对步骤c划分好的各个数据分片内电力数据集中的所有对 象在步骤d所调用的相应worker中定义一个整型变量k，调用步骤d 的状态转换程序，执行以下循环：

定义k值从1到i：

$O_k\stackrel{c_1}{\to }{V}_{c_{1k}}\stackrel{c_2}{\to }{V}_{c_{2k}}\stackrel{...}{\to }{V}_{c_{\mathrm{mk}}}\stackrel{D}{\to }{V}_{D_i};$

f.若步骤e中相应数据分片内的各个对象，从初始状态向决策状 态转换的过程中存在多个对象都经过若干个相同状态的转换，到达相 同的决策状态，则只保留这些对象所历经的相同状态；

g.针对步骤f的处理结果，在相应worker中，把从相同状态量 经同样的变迁关系转换之后又得到相同状态量的所有对象只保留一 个；

h.根据步骤g的处理结果，若各worker中存在多个对象，则在 相应worker中，求这些对象所历经状态的并集，否则，处理结果为 步骤g中由各worker中所求得的单个对象历经状态的集合(初始状 态与决策状态除外)；

i.在相应worker中对步骤h的处理结果进行统计，若不存在步 骤f中所提及的情况，则约简结果为全部条件属性，否则遍历步骤h 的约简结果，把中间状态量的集合解码为其所对应的属性集合，作为 约简结果输出。

上述电力大数据预处理的属性约简方法，步骤b把电力大数据集 根据其决策属性D的不同取值划分等价类后，若决策属性的取值种类 超过设定值，则后续的约简过程可按照以下步骤进行：

①把步骤b划分好的各个等价类内电力数据集中的每条记录视 作一个对象，各属性视为变迁关系，各属性值看作在相应变迁关系作 用下转换的中间状态，调用k台worker(集群中的计算机)，分别将 各等价类内数据集的各个对象在相应的worker中从初始状态O在各 变迁关系的作用下朝着决策状态进行变换：

$O_j\stackrel{c_1}{\to }{V}_{c_{1j}}\stackrel{c_2}{\to }{V}_{c_{2j}}\stackrel{...}{\to }{V}_{c_{\mathrm{mj}}}\stackrel{D}{\to }{V}_{D_i},j\in [1,i]$

其中O_j表示第j个对象的初始状态且所有对象的初始状态量相 同，表示第j个对象在变迁关系c_i的作用下转换到的相应中间状 态，为初始状态O_j经各变迁关系c₁,c₂,…,c_n,D，变换之后的终止状 态；

②针对步骤b划分好的各个等价类内电力数据集中的所有对 象，在步骤①所调用的相应worker中定义一个整型变量k，调用步 骤①的状态转换程序，执行以下循环：

定义k值从1到i：

$O_k\stackrel{c_1}{\to }{V}_{c_{1k}}\stackrel{c_2}{\to }{V}_{c_{2k}}\stackrel{...}{\to }{V}_{c_{\mathrm{mk}}}\stackrel{D}{\to }{V}_{D_i};$

③若步骤②中相应等价类内的各个对象，从初始状态向决策状 态转换的过程中存在多个对象都经过若干个相同状态的转换，到达相 同的决策状态，则只保留这些对象所历经的相同状态；

④对步骤③的处理结果，在相应worker中，把从相同状态量经 同样的变迁关系转换之后又得到相同状态量的所有对象只保留一个；

⑤根据步骤④的处理结果，若各worker中存在多个对象，则在 相应worker中，求这些对象所历经状态的并集，否则，处理结果为 步骤④中由各worker中所求得的单个对象历经状态的集合(初始状 态与决策状态除外)；

⑥在相应worker中对步骤⑤的处理结果进行统计，若不存在步 骤③中所提及的情况，则约简结果为全部条件属性，否则遍历步骤⑤ 的约简结果，把中间状态量的集合解码为其所对应的属性集合，作为 约简结果输出，算法结束。

本发明将偏序理论与MapReduce框架有机结合在一起，不仅略过 了传统启发式约简算法的求核过程，提高了约简算法的效率，而且能 够确保电力数据集的原有信息不丢失，特别适于电力行业海量数据的 并行化预处理。

附图说明

下面结合附图对本发明作进一步说明。

图1是Map函数流程图(图中Y表示判断条件成立，N表示判断 条件不成立)；

图2是整体算法流程图。

文中各符号清单为：。U为论域，C是条件属性构成的集合，D是 决策属性，V是属性a的值域，表示第j个对象在第i个属性上的 取值，O_j表示第j个对象的初始状态，表示第j个对象在变迁关 系c_i的作用下转换到的相应中间状态，为初始状态O_j经各变迁关 系c₁,c₂,…,c_n,D变换之后的终止状态。

具体实施方式

本发明提出了一种基于偏序的电力大数据的属性约简方法，通过 利用偏序约简算法的并行化优势，对其进行适应性改进，结合 MapReduce框架给出一种新的适用于电力大数据的并行化约简算法。 该方法首先将电力系统中的属性视作变迁关系，属性值作为在相应变 迁关系作用下的转换状态；然后把针对在某一顺序变迁关系组的转换 下到达相同终止状态的一些变迁序列去掉中间的冗余状态，仅保留关 键路径；最后将关键路径上的变迁关系解码为相应的属性输出。

电力大数据属性偏序约简下map函数的算法流程图详见附图1， 整体算法的流程图详见附图2。

为了便于理解，以下给出本发明方案的形式化描述：

定义1设三元组S＝(U,A,V)表示一个电力系统的运行状态，也 可以叫作电力系统信息决策表。其中U作为论域，表示全体对象的有 限非空集合；C是条件属性构成的集合，D是决 策属性；V是属性a的值域，即V_a∈V。

定义2假设电力系统信息决策表中初始状态为O， 是在条件属性即变迁关系c_i作用下的中间转换状 态，相应的为初始状态O经各变迁关系c₁,c₂,…,c_n,D，变换之后的 终止状态，即$O\stackrel{c_1}{\to }{V}_{c_1}\to ...\stackrel{C_n}{\to }{V}_{c_n}\stackrel{D}{\to }{V}_{D_i}.$

定义3假设在电力系统信息决策表中，存在多个对象使得它们 从同一状态量经过若干个变迁关系c_i+1,c_i+2,…,c_i+k变换之后得到的状 态量相同(所谓的状态量相同，即是根据决策表中数据的实际情况， 这些对象的状态值相同或其状态值都属于某一特定范围，决策属性所 对应的状态除外)，并且在转换过程的中间不存在相同的状态量，即 存在多个u_i∈U，使得满足上述条件， 则可以去掉这些冗余状态。

定义4假设在电力系统信息决策表中存在多个对象，在同一状 态量经一个或多个相同变迁关系转换之后得到的状态量相同，即存在 多个u_i∈U使得$V_{c_i}\stackrel{c_{i+1}}{\to }{V}_{c_{i+1}}\to ...\stackrel{C_{i+k}}{\to }{V}_{c_{i+k}}$或$V_{c_i}\stackrel{c_{i+1}}{\to }{V}_{c_{i+1}}$满足上述条 件，则只保留其中一个对象，删去其他冗余对象。

定理1把电力系统信息决策表S中的所有对象根据决策属性D 的值划分成等价类{D₁,D₂,…,D_i}，D_i＝{u₁,u₂,…,u_t}，(t∈Z),若存在多个 数据分片DS_k(k＝1,2,…,n)同属于一个等价类，则对于该等价类内属 性集的约简结果为各数据分片内约简结果的并集即(A_k为第k个数据分片内求得的约简属性集，A_kj为由第k个数据分片求 得的第j个属性，j＝1,2,…,r)。

本发明方案的具体执行步骤如下所示：

第1步：根据定义1，把电力大数据集看作一个由三元组 S＝(U,A,V)表示的电力系统信息决策表，假设该决策表含有n个对象， 每个对象又包括m个条件属性，一个决策属性D。如表1所示：

表1电力系统信息决策表

第2步：本发明考虑到偏序约简方法在处理并发事件时相互独立 的特征，结合MapReduce模型的并行化优势，把电力大数据集根据其 决策属性D的不同取值划分等价类。若决策属性D有k种不同取值， 则根据决策属性D的值划分等价类如下(其中表示第j个对象在 第i个属性上的取值)：

$\left(\begin{array}{cccc}\left(\begin{array}{cccc}{V}_{c_{11}}& V_{c_{21}}& ...& V_{D_1}\\ V_{c_{12}}& V_{c_{22}}& ...& V_{D_1}\\ ...& ...& ...& ...\\ V_{c_{1i}}& V_{c_{2i}}& ...& V_{D_1}\end{array}\right)& \left(\begin{array}{cccc}{V}_{c_{11}}& V_{c_{21}}& ...& V_{D_2}\\ V_{c_{12}}& V_{c_{22}}& ...& V_{D_2}\\ ...& ...& ...& ...\\ V_{c_{1i}}& V_{c_{2i}}& ...& V_{D_2}\end{array}\right)& ----& \left(\begin{array}{cccc}{V}_{c_{11}}& V_{c_{21}}& ...& V_{D_k}\\ V_{c_{12}}& V_{c_{22}}& ...& V_{D_k}\\ ...& ...& ...& ...\\ V_{c_{1i}}& V_{c_{2i}}& ...& V_{D_k}\end{array}\right)\end{array}\right)---\left(1\right)$

第3步：本发明根据电力数据集中决策属性不同取值个数多少的 实际情况，有两种约简方案可供选择。方案1：如果决策属性的取值 种类较多，则顺序执行第4步；方案2：如果决策属性的取值种类较 少，则跳转至第10步。但是，为了提高数据预处理的效率，在决策 属性值种类较多的情况下，也可以选择跳转至第10步继续往下执行。

第4步：把第2步划分好的各个等价类内电力数据集中的每条记 录视作一个对象，各属性视为变迁关系，各属性值看作在相应变迁关 系作用下转换的中间状态，调用k台worker(集群中的计算机)按照 定义2，分别将各等价类内数据集的各个对象在相应的worker中从 初始状态O在各变迁关系的作用下朝着决策状态进行变换，如下所 示：

$O_j\stackrel{c_1}{\to }{V}_{c_{1j}}\stackrel{c_2}{\to }{V}_{c_{2j}}\stackrel{...}{\to }{V}_{c_{\mathrm{mj}}}\stackrel{D}{\to }{V}_{D_i},j\in [1,i]---\left(2\right)$

其中O_j表示第j个对象的初始状态且所有对象的初始状态量相同，表示第j个对象在变迁关系c_i的作用下转换到的相应中间状态。

第5步：针对第2步划分好的各个等价类内电力数据集中的所有 对象，在第4步所调用的相应worker中定义一个整型变量k，调用 步骤4的状态转换程序，执行以下循环：

定义k值从1到i：

$O_k\stackrel{c_1}{\to }{V}_{c_{1k}}\stackrel{c_2}{\to }{V}_{c_{2k}}\stackrel{...}{\to }{V}_{c_{\mathrm{mk}}}\stackrel{D}{\to }{V}_{D_i};---\left(3\right)$

第6步：根据定义3，若第5步中相应等价类内的各个对象从初 始状态在向决策状态转换的过程中存在类似以下情况：

$\left(\begin{array}{c}{O}_j\stackrel{c_1}{\to }{V}_{c_{1j}}\stackrel{...}{\to }{V}_{c_{\mathrm{pj}}}\stackrel{c_{p+1}}{\to }{V}_{c_{(p+1)j}}\stackrel{...}{\to }{V}_{c_{\mathrm{qj}}}\stackrel{...}{\to }{V}_{D_i}\\ O_{j+1}\stackrel{c_1}{\to }{V}_{c_{1(j+1)}}\stackrel{...}{\to }{V}_{c_{p(j+1)}}\stackrel{c_{p+1}}{\to }{V}_{c_{(p+1)(j+1)}}\stackrel{...}{\to }{V}_{c_{q(j+1)}}\stackrel{...}{\to }{V}_{D_i}\\ .\\ .\\ .\\ O_{j+l}\stackrel{c_1}{\to }{V}_{c_{1(j+l)}}\stackrel{...}{\to }{V}_{c_{p(j+l)}}\stackrel{c_{p+1}}{\to }{V}_{c_{(p+1)(j+l)}}\stackrel{...}{\to }{V}_{c_{q(j+l)}}\stackrel{...}{\to }{V}_{D_i}\end{array}\right)---\left(4\right)$

(j+l)∈[1,i]，l为大于等于0的整数。

p,q∈[1,m]且p<q，$V_{c_{\mathrm{pj}}}=V_{c_{p(j+1)}}=...=V_{c_{p(j+l)}}$且$V_{c_{(\mathrm{qj}}}=V_{c_{q(j+1)}}=...=V_{c_{q(j+l)}},$则在 相应worker中可简化成

$\left(\begin{array}{c}{O}_j\stackrel{...}{\to }{V}_{c_{\mathrm{pj}}}\stackrel{...}{\to }{V}_{c_{\mathrm{qj}}}\stackrel{...}{\to }{V}_{D_i}\\ O_{j+1}\stackrel{...}{\to }{V}_{c_{p(j+1)}}\stackrel{...}{\to }{V}_{c_{q(j+1)}}\stackrel{...}{\to }{V}_{D_i}\\ .\\ .\\ .\\ O_{j+l}\stackrel{...}{\to }{V}_{c_{p(j+l)}}\stackrel{...}{\to }{V}_{c_{q(j+l)}}\stackrel{...}{\to }{V}_{D_i}\end{array}\right)---\left(5\right)$

即：各个对象由初始状态向决策状态转换的过程中，假如存在多个对 象都经过若干个相同状态的转换，到达相同的决策状态，则只保留这 些对象所历经的相同状态。

第7步：对第6步的处理结果，依据定义4在相应worker中， 把从相同状态量经同样的变迁关系转换之后又得到相同状态量的所 有对象只保留一个。

第8步：根据第7步的处理结果，若各worker中存在多个对象， 则根据定理1在相应worker中，求这些对象所历经状态的并集，否 则，处理结果为第7步中由各worker中所求得的单个对象历经状态 的集合(初始状态与决策状态除外)。

第9步：在相应worker中对第8步的处理结果进行统计，若不 存在第6步中所提及的情况，则约简结果为全部条件属性，否则遍历 第8步的约简结果，根据各个中间状态量的下标还原其所对应的变迁 关系，也就是把中间状态量的集合解码为其所对应的属性集合，作为 约简结果输出，算法结束。

第10步：将上述的k个不同等价类内的数据集分别再进行划分， 为充分发挥计算机集群的优势，根据计算机集群的规模和以往经验确 定每台worker(集群中的计算机)所要处理的数据集规模，使得各 节点之间通信、调度等开销，达到最小值，又由于各等价类内数据集 规模的不同，依次划分为n₁,n₂,…,n_k个数据分片；

第11步：把第10步划分好的各个数据分片内电力数据集中的每 条记录视作一个对象，各属性视为变迁关系，各属性值看作在相应变 迁关系作用下转换的中间状态，调用(n₁+n₂+…+n_k)台worker(集群中 的计算机)按照定义2，分别将各数据分片内数据集的各个对象在相 应的worker中从初始状态O在各变迁关系的作用下朝着决策状态进 行变换，如下所示：

$O_j\stackrel{c_1}{\to }{V}_{c_{1j}}\stackrel{c_2}{\to }{V}_{c_{2j}}\stackrel{...}{\to }{V}_{c_{\mathrm{mj}}}\stackrel{D}{\to }{V}_{D_i},j\in [1,i]---\left(6\right)$

其中O_j表示第j个对象的初始状态且所有对象的初始状态量相同，表示第j个对象在变迁关系c_i的作用下转换到的相应中间状态。

第12步：针对第10步划分好的各个数据分片内电力数据集中的 所有对象在第11步所调用的相应worker中定义一个整型变量k，调 用步骤11的状态转换程序，执行以下循环：

定义k值从1到i：

$O_k\stackrel{c_1}{\to }{V}_{c_{1k}}\stackrel{c_2}{\to }{V}_{c_{2k}}\stackrel{...}{\to }{V}_{c_{\mathrm{mk}}}\stackrel{D}{\to }{V}_{D_i};---\left(7\right)$

第13步：根据定义3，若第12步中相应数据分片内的各个对象 从初始状态在向决策状态转换的过程中存在类似以下情况：

$\left(\begin{array}{c}{O}_j\stackrel{c_1}{\to }{V}_{c_{1j}}\stackrel{...}{\to }{V}_{c_{\mathrm{pj}}}\stackrel{c_{p+1}}{\to }{V}_{c_{(p+1)j}}\stackrel{...}{\to }{V}_{c_{\mathrm{qj}}}\stackrel{...}{\to }{V}_{D_i}\\ O_{j+1}\stackrel{c_1}{\to }{V}_{c_{1(j+1)}}\stackrel{...}{\to }{V}_{c_{p(j+1)}}\stackrel{c_{p+1}}{\to }{V}_{c_{(p+1)(j+1)}}\stackrel{...}{\to }{V}_{c_{q(j+1)}}\stackrel{...}{\to }{V}_{D_i}\\ .\\ .\\ .\\ O_{j+l}\stackrel{c_1}{\to }{V}_{c_{1(j+l)}}\stackrel{...}{\to }{V}_{c_{p(j+l)}}\stackrel{c_{p+1}}{\to }{V}_{c_{(p+1)(j+l)}}\stackrel{...}{\to }{V}_{c_{q(j+l)}}\stackrel{...}{\to }{V}_{D_i}\end{array}\right)---\left(8\right)$

(j+l)∈[1,i]，l为大于等于0的整数。

p,q∈[1,m]且p<q，$V_{c_{\mathrm{pj}}}=V_{c_{p(j+1)}}=...=V_{c_{p(j+l)}}$且$V_{c_{(\mathrm{qj}}}=V_{c_{q(j+1)}}=...=V_{c_{q(j+l)}},$则在 相应worker中可简化成

$\left(\begin{array}{c}{O}_j\stackrel{...}{\to }{V}_{c_{\mathrm{pj}}}\stackrel{...}{\to }{V}_{c_{\mathrm{qj}}}\stackrel{...}{\to }{V}_{D_i}\\ O_{j+1}\stackrel{...}{\to }{V}_{c_{p(j+1)}}\stackrel{...}{\to }{V}_{c_{q(j+1)}}\stackrel{...}{\to }{V}_{D_i}\\ .\\ .\\ .\\ O_{j+l}\stackrel{...}{\to }{V}_{c_{p(j+l)}}\stackrel{...}{\to }{V}_{c_{q(j+l)}}\stackrel{...}{\to }{V}_{D_i}\end{array}\right)---\left(9\right)$

即：各个对象由初始状态向决策状态转换的过程中，假如存在多个对 象都经过若干个相同状态的转换，到达相同的决策状态，则只保留这 些对象所历经的相同状态。

第14步：针对第13步的处理结果，依据定义4在相应worker 中，把从相同状态量经同样的变迁关系转换之后又得到相同状态量的 所有对象只保留一个。

第15步：根据第14步的处理结果，若各worker中存在多个对 象，则根据定理1在相应worker中，求这些对象所历经状态的并集， 否则，处理结果为第14步中由各worker中所求得的单个对象历经状 态的集合(初始状态与决策状态除外)。

第16步：在相应worker中对第15步的处理结果进行统计，若 不存在第13步中所提及的情况，则约简结果为全部条件属性，否则 遍历第15步的约简结果，根据各个中间状态量的下标还原其所对应 的变迁关系，也就是把中间状态量的集合解码为其所对应的属性集 合，作为约简结果输出，算法结束。

表2当前几种主要的并行化约简算法的性能对比

偏序理论介绍

偏序约简算法的初衷是通过减少系统模型中的状态数目，以降低 模型检测算法所搜索的状态空间规模。其依据是系统中可并发执行的 变迁关系具有交换性，即当这些变迁关系以不同的顺序执行时，都会 到达一个相同的状态，对于这些不同组合顺序的变迁关系组只需选择 其中之一即可。以下给出适应电力系统大数据属性偏序约简的相关概 念。

(1)给定一个四元组的初始状态变迁系统(S,T,S₀,L),其中S是所 有状态的集合，S₀是初始状态的集合，L为标记函数，T是变迁的集 合，对于每一个α∈T,都有

对于变迁α∈T，如果有一个状态S'，使得α(S,S')成立，则α在S'处是 激活的，反之，则称α在S'处是非激活的，在S'处所有激活的变迁 集合记为enabled(S)。对于每一个状态S'，只选择所有激活变迁的集 合enabled(S)的一个子集—充足集ample(S),而非整个enabled(S)，这是因 为从enabled(S)出发将构建全状态图，而非约简状态图。

(2)若两条无限路径$\sigma =s_0\stackrel{{\alpha }_0}{\to }{s}_1\stackrel{{\alpha }_1}{\to }...$和 是stuttering等价的，当且仅当它们满足条件： 存在两个无限的正整数序列0＝i₀＜i₁＜…和0＝j₀＜j₁＜…使得对于每 一个k≥0，都有$L\left(s_{i_k}\right)=L\left(s_{i_{k+1}}\right)=...=L\left(s_{i_{k+1}-1}\right)=L\left(r_{j_k}\right)=L\left(r_{j_k+1}\right)=...=L\left(r_{j_{k+1}-1}\right)$记为σ～_stρ。称具有相同标记集合的连续状态序列为块，在两条路径 被划分为无限个块后，如果其中一条路径的第k块的标记集合和另一 条路径第k块的标记集合相同，则称这两条路径是stuttering等价的。

(3)若独立关系是一个对称的，反自反的关系，对于任 意的状态s∈S,(每一个(α,β)∈I),满足下面两个条件：

激活性：如果(α,β)∈enabled(s)，那么α∈enabled(β(s))。

交换性：如果(α,β)∈enabled(s)，那么α(β(s))＝β(α(s))。

依赖关系D是独立关系I的补，表示为D＝(T×T)I。

(4)用L:S→2^AP表示将状态映射到原子命题集合上的标记函 数；给定一个命题集合和一个变迁α∈T,如果对于每一对 s,s'∈S,都有s'＝(α(s))，L(s)∩AP'＝L(s')∩AP'则称变迁α∈T是不可见的。

当给定的刻画在stuttering下不变时，利用交换性和不可见性可以 避免生成一些状态，基于这个原理可以得到任意状态的充足集— ample，偏序约简算法利用这些ample集来构建约简的状态图，因此， 对于每一条没有被偏序约简算法考虑的路径，在约简图内都有一条路 径与之stuttering等价，这就确保了约简状态图和全状态图是stuttering 等价的。以下给出四个选择ample集的限制条件：

C₀当且仅当

C₁在全状态图中，每一条从s出发的路径，都有下面的条件成 立：一个变迁与ample(s)中的某个变迁具有依赖关系，那么这个变迁 不能在ample(s)中的那个变迁之前执行。

C₂如果s不是完全展开的，那么每一个α∈ample(s)都是不可见 的。

C₃如果一个回路包含一个状态，在这个状态上的某个变迁α是 激活的，但是在这个回路上的所有状态s，都没有包含在ample(s)中， 这个回路是不存在的。

技术方案中出现的专业术语解释

MapReduce：是由Google推出的一种用于分布式处理超大规模数 据集的并行软件编程模型，其通过分而治之的思想对数据集进行处 理。

变迁关系：指的是促使状态之间相互转换的某种关系或性质。

论域：指的是特定对象或数据的有限非空集合。

条件属性：指的是促成某种结果的相关因素。

决策属性：指的是由某些相关因素所促成的结果。