一种基于Markov模型的实体基本信息自动生成系统及方法

摘要

一种基于Markov模型的实体基本信息自动生成系统及方法，适用于信息系统试验、试用场景的基本数据生成，该系统及方法所涉及的实体属性数据具有枚举型特征，所述方法包括定义属性优先级排序步骤、构建多值依赖统计决策树步骤、以及进行参数学习和剪枝算法步骤，所述系统包括定义属性优先级排序装置、构建多值依赖统计决策树装置、以及进行参数学习和剪枝算法装置。

说明书

一、技术领域

本发明涉及一种基于Markov模型的实体基本信息自动生成系统及方法，适用于信 息系统试验、试用场景的基本数据生成，特别涉及具有枚举型特征的基本属性数据自动 生成。

二、技术背景

信息系统模拟数据生成是用计算机模拟的方式快速生成信息系统模拟数据。从时效 性、安全性、经济性的角度，信息系统在试验、试用等场景下都需要生成信息系统模拟 数据。

当前，信息系统中主要使用的是关系型数据，而关系型数据中实体之间的联系分为 一对一联系、一对多联系、多对多联系。例如，根据《中国人民解放军军官军衔条例》 (领域知识)，一个职务级别对应多个军衔，反之，一个军衔也可对应多个职务级别，二 者之间存在典型的多对多联系，这种多对多联系被称为多值依赖。

对于具有多个属性的实体而言，不是任意两个属性的属性值之间都存在多值依赖关 系，不存在依赖的属性值之间的分布是随机的，因此，在数据生成之前，应根据映射关 系对枚举型属性进行分组，数据生成时对不同的枚举型分组单独处理。

针对数据生成需求，一些研究团队开发了如审计数据模拟数据生成系统、人员档案 模拟数据生成系统等模拟数据生成系统。审计数据模拟数据生成系统可以生成不同规 模、含有不同长度要求的相似重复数据或不符合业务规则的数据；系统主要借助开源网 站提供的数据为源数据，通过调用源数据来生成所需的数据，但没有考虑关系型数据的 特点，所生成的数据并没有真实的领域背景，适用性有限。人员档案模拟数据生成系统 可以生成人员的姓名、性别、民族、出生年月、籍贯、政治面貌、学历、学位等属性值； 系统利用随机数函数，随机选择给定域的值生成各属性值，但没有考虑各属性值的分布 及属性值间的依赖关系。

本发明涉及的基于Markov模型的实体基本信息自动生成器能针对现有系统的这些 缺点，实现具有枚举型特征的基本属性数据自动生成。

三、发明内容

本发明的目的是：克服以上不足，设计了一种基于Markov模型的实体基本信息自动 生成系统及方法。

基于Markov模型的实体基本信息自动生成系统及方法可以据此生成信息系统试验、 试用等场景的测试数据。该生成器利用样本数据，充分挖掘属性之间的依赖关系，构建基于 关系马尔柯夫模型的多值依赖统计决策树，通过参数学习和剪枝算法，得到生成树，依据此 生成树可以生成大规模的测试数据，这些测试数据既符合客观分布的统计规律，又能兼顾各 属性值的分布及属性间的依赖关系，较好地满足了信息系统的试验、试用数据需求。

根据本发明的一个方面，提供一种基于Markov模型的实体基本信息自动生成方法， 适用于信息系统试验、试用场景的基本数据生成，该方法所涉及的实体属性数据具有枚 举型特征，实体属性之间存在一对一联系、一对多联系、多对多联系，这种多对多联系 被称为多值依赖，所述方法包括以下步骤：定义属性优先级排序步骤、构建多值依赖统 计决策树步骤、以及进行参数学习和剪枝算法步骤，

其中，所述定义属性优先级排序步骤包括：为提高生成数据的性能，在数据生成之 前，应根据实体属性关系进行分组，以便数据生成时对不同的枚举型分组单独处理，分 组中的一个重要的信息是属性组中属性的优先级；以下定义了如下的属性优先级排序策略：

1)时间先后，属性所描述的实体存在时间先后顺序；

2)空间从属，属性所描述的实体存在空间从属关系；

3)概念层次，属性间存在层次分类关系；

4)业务主次，在业务领域中，根据相关领域知识，存在某属性值受另一属性值约束的情 况；

对一个枚举型属性分组，按照以上策略进行优先级排序，排序一旦确定，该分组中的属 性值按此顺序依次生成；

其中，构建多值依赖统计决策树步骤包括：对一个有序枚举型属性集G＝＜a₁，a₂，...， a_n＞，各属性对应的域为V＝[V₁，V₂,...，V_n]，其中i＝1，2，...，n为具体取值 范围，依据概率分布，进而构建基于Markov模型的多值依赖统计决策树模型；

其中，进行参数学习和剪枝算法步骤包括：通过参数学习得到上述模型中的概率参 数，学习公式如下：

$P(a_1=v_{{1m}_1})=1-\underset{k_1=1}{\overset{m_1-1}{\Sigma }}P(a_1=v_{{1k}_1})$

$P(a_i=v_{{\mathrm{im}}_i}|a_{i-1}=v_{(i-1)k_{i-1}})=1-\underset{k_i=1}{\overset{m_i-1}{\Sigma }}P(a_i=v_{{\mathrm{ik}}_i}|a_{i-1}=v_{(i-1)k_{i-1}})=1,i=\mathrm{2,3},...,n$

表示样本数据中的概率，表示在属性a_i-1取值 的条件下，属性a_i取值的概率，k₁＝1，2，...，m₁，k_i＝1，2，...，m_i；

在学习过程中，利用剪枝算法，将不会出现关联的节点删除，具体算法如下：

若或则将该树枝连接的结点为树根的子树删 除；

数据生成时，从根结点出发，依概率依次生成各属性值，直到生成树的叶子结点，完成 实体基本信息自动生成。

根据本发明的另一方面，一种基于Markov模型的实体基本信息自动生成系统，适用 于信息系统试验、试用场景的基本数据生成，该系统所涉及的实体属性数据具有枚举型 特征，实体属性之间存在一对一联系、一对多联系、多对多联系，这种多对多联系被称 为多值依赖，所述系统包括：定义属性优先级排序装置、构建多值依赖统计决策树装置、 以及进行参数学习和剪枝算法装置，

其中，所述定义属性优先级排序装置包括：为提高生成数据的性能，在数据生成之 前，应根据实体属性关系进行分组，以便数据生成时对不同的枚举型分组单独处理，分 组中的一个重要的信息是属性组中属性的优先级；以下定义了如下的属性优先级排序策略：

1)时间先后，属性所描述的实体存在时间先后顺序；

2)空间从属，属性所描述的实体存在空间从属关系；

3)概念层次，属性间存在层次分类关系；

4)业务主次，在业务领域中，根据相关领域知识，存在某属性值受另一属性值约束的情 况；

对一个枚举型属性分组，按照以上策略进行优先级排序，排序一旦确定，该分组中的属 性值按此顺序依次生成；

其中，构建多值依赖统计决策树装置包括：对一个有序枚举型属性集G＝＜a₁，a₂，...， a_n＞，各属性对应的域为V＝[V₁，V₂，...，V_n]，其中i＝1，2，...，n为具体取值 范围，依据概率分布，进而构建基于Markov模型的多值依赖统计决策树模型；

其中，进行参数学习和剪枝算法装置包括：通过参数学习得到上述模型中的概率参 数，学习公式如下：

$P(a_1=v_{{1m}_1})=1-\underset{k_1=1}{\overset{m_1-1}{\Sigma }}P(a_1=v_{{1k}_1})$

$P(a_i=v_{{\mathrm{im}}_i}|a_{i-1}=v_{(i-1)k_{i-1}})=1-\underset{k_i=1}{\overset{m_i-1}{\Sigma }}P(a_i=v_{{\mathrm{ik}}_i}|a_{i-1}=v_{(i-1)k_{i-1}})=1,i=\mathrm{2,3},...,n$

表示样本数据中的概率，表示在属性a_i-1取值 的条件下，属性a_i取值的概率，k₁＝1，2，...，m₁，k_i＝1，2，...，m_i；

在学习过程中，利用剪枝算法，将不会出现关联的节点删除，具体算法如下：

若或则将该树枝连接的结点为树根的子树删 除；

数据生成时，从根结点出发，依概率依次生成各属性值，直到生成树的叶子结点，完成 实体基本信息自动生成。

本发明的优点：

本发明设计的一种基于Markov模型的实体基本信息自动生成器，生成的数据适用 于信息系统试验、试用等场景，有如下的优点：

■优先级排序策略。本发明定义了属性优先级排序策略，根据此策略对属性生成次 序排序，可以确保属性值符合由领域知识所决定的顺序关系，保证了数据生成 过程的合理性。

■多值依赖统计决策策略。本发明在多值依赖统计决策树构建的过程中，涵盖了由 领域知识决定的对应关系，所生成的每一条数据的多个属性值符合客观分布， 保证生成的数据结果合理，接近真实数据。

■参数学习及剪枝策略。本发明的参数学习是在样本数据的基础上实现的，对不符 合客观分布的值，在参数学习和剪枝的过程中即已删除，保证生成的多条数据符合客 观实体数据的统计规律，进而保证在此数据基础上得出的试验、试用结果可靠。

■可扩展性。目前提出的一些模拟数据生成方法都是针对特定应用场景的，只适 用于具体应用场景，通用的、与应用领域无关的方法较少，而我们设计的方法 是领域无关的，适用范围较广。

本发明附加的方面和优点将在下面的描述中部分给出，部分将从下面的描述中变得明显， 或通过本发明的实践了解到。

四、附图说明

本发明上述的和/或附加的方面和优点从下面结合附图对实施例的描述中将变得明显和 容易理解，其中：

图1为基于关系马尔柯夫模型的多值依赖统计决策树；以及

图2示出了根据本发明实施例的基于Markov模型的实体基本信息自动生成方法流程 图。

五、具体实施方式

下面详细描述本发明的实施例，通过参考附图描述的实施例是示例性的，仅用于解 释本发明，而不能解释为对本发明的限制。

对一个有序枚举型属性集(元组)G＝＜a₁，a₂，...，a_n＞，各属性对应的域为V＝[V₁，V₂，...，V_n]， 其中i＝1，2，...，n为具体取值范围，先根据以下原则对枚举型属性进行分 组：

1)将存在映射关系的属性分为一组，使每一个属性属于且仅属性于一个分组；

2)对1)划分的枚举型属性分组，一个关系中两个不同的枚举型分组相互独立，在数据 生成时分别进行处理。

由此形成的分组中的各属性，在属性数据生成时具有不同的优先级顺序，合理的优先级 排序才能保证生成的数据更加接近真实值。因此，本发明设计了如下策略对属性进行排序：

1)时间先后。某些属性所描述的实体存在时间先后顺序。如出生年、工作年；第一学历、 最高学历。

2)空间从属。有些属性所描述的实体存在空间从属关系。如城市、大学；省、市、学校、 院系、专业。

3)概念层次。某些属性间存在层次分类关系。如一级学科、二级学科；师、团、营、连 等。

4)业务主次。在某些业务领域中，根据相关领域知识，存在某属性值受另一属性值约束 的情况。如部队中职务级别对军衔的限定，即军衔从属于职务级别，此时，职务级别优先级 应高于军衔，学历优先级应高于学位。

以上即为优先级排序策略。属性分组排序完成后，利用Markov模型对属性分布概率建 模如下：

$P(a_i=v_{{\mathrm{ik}}_i}|a_1=v_{{1k}_1},a_2=v_{{2k}_2},...,a_{i-1}=v_{(i-1)k_{i-1}})=P(a_i=v_{{\mathrm{ik}}_i}|a_{i-1}=v_{(i-1)k_{i-1}}),i=\mathrm{2,3},...,n$

表示在属性a_i-1取值的条件下，属性a_i取值的概率， k_i＝1，2，...，m_i。

在概率分布建模完成后，我们可利用概率参数，构建基于Markov模型的多值依赖 统计决策树模型，如图1所示那样。此即多值依赖统计决策策略。

对于模型中的概率参数，可以在样本数据的基础上，通过下列公式学习得出：

$P(a_1=v_{{1m}_1})=1-\underset{k_1=1}{\overset{m_1-1}{\Sigma }}P(a_1=v_{{1k}_1})$

$P(a_i=v_{{\mathrm{im}}_i}|a_{i-1}=v_{(i-1)k_{i-1}})=1-\underset{k_i=1}{\overset{m_i-1}{\Sigma }}P(a_i=v_{{\mathrm{ik}}_i}|a_{i-1}=v_{(i-1)k_{i-1}})=1,i=\mathrm{2,3},...,n$

其中，若或则将该树枝连接的结点为树根的 子树删除，此即上述的参数学习和剪枝策略。

综上所述，如图2所示，根据本发明的实施例，提供了一种基于Markov模型的实体基 本信息自动生成方法，适用于信息系统试验、试用场景的基本数据生成，该方法所涉及 的实体属性数据具有枚举型特征，实体属性之间存在一对一联系、一对多联系、多对多 联系，这种多对多联系被称为多值依赖，所述方法包括以下步骤：定义属性优先级排序 步骤、构建多值依赖统计决策树步骤、以及进行参数学习和剪枝算法步骤，

其中，所述定义属性优先级排序步骤包括：为提高生成数据的性能，在数据生成之 前，应根据实体属性关系进行分组，以便数据生成时对不同的枚举型分组单独处理，分 组中的一个重要的信息是属性组中属性的优先级；以下定义了如下的属性优先级排序策略：

1)时间先后，属性所描述的实体存在时间先后顺序；

2)空间从属，属性所描述的实体存在空间从属关系；

3)概念层次，属性间存在层次分类关系；

4)业务主次，在业务领域中，根据相关领域知识，存在某属性值受另一属性值约束的情 况；

对一个枚举型属性分组，按照以上策略进行优先级排序，排序一旦确定，该分组中的属 性值按此顺序依次生成；

其中，构建多值依赖统计决策树步骤包括：对一个有序枚举型属性集G＝＜a₁，a₂，...， a_n＞，各属性对应的域为V＝[V₁，V₂，...，V_n]，其中i＝1，2，...，n为具体取值 范围，依据概率分布，进而构建基于Markov模型的多值依赖统计决策树模型；

其中，进行参数学习和剪枝算法步骤包括：通过参数学习得到上述模型中的概率参 数，学习公式如下：

$P(a_1=v_{{1m}_1})=1-\underset{k_1=1}{\overset{m_1-1}{\Sigma }}P(a_1=v_{{1k}_1})$

$P(a_i=v_{{\mathrm{im}}_i}|a_{i-1}=v_{(i-1)k_{i-1}})=1-\underset{k_i=1}{\overset{m_i-1}{\Sigma }}P(a_i=v_{{\mathrm{ik}}_i}|a_{i-1}=v_{(i-1)k_{i-1}})=1,i=\mathrm{2,3},...,n$

表示样本数据中的概率，表示在属性a_i-1取值 的条件下，属性a_i取值的概率，k₁＝1，2，...，m₁，k_i＝1，2，...，m_i；

在学习过程中，利用剪枝算法，将不会出现关联的节点删除，具体算法如下：

若或则将该树枝连接的结点为树根的子树删 除；

数据生成时，从根结点出发，依概率依次生成各属性值，直到生成树的叶子结点，完成 实体基本信息自动生成。

根据本发明实施例，提供一种基于Markov模型的实体基本信息自动生成系统，适用 于信息系统试验、试用场景的基本数据生成，该系统所涉及的实体属性数据具有枚举型 特征，实体属性之间存在一对一联系、一对多联系、多对多联系，这种多对多联系被称 为多值依赖，所述系统包括：定义属性优先级排序装置、构建多值依赖统计决策树装置、 以及进行参数学习和剪枝算法装置，

其中，所述定义属性优先级排序装置包括：为提高生成数据的性能，在数据生成之 前，应根据实体属性关系进行分组，以便数据生成时对不同的枚举型分组单独处理，分 组中的一个重要的信息是属性组中属性的优先级；以下定义了如下的属性优先级排序策略：

1)时间先后，属性所描述的实体存在时间先后顺序；

2)空间从属，属性所描述的实体存在空间从属关系；

3)概念层次，属性间存在层次分类关系；

4)业务主次，在业务领域中，根据相关领域知识，存在某属性值受另一属性值约束的情 况；

对一个枚举型属性分组，按照以上策略进行优先级排序，排序一旦确定，该分组中的属 性值按此顺序依次生成；

其中，构建多值依赖统计决策树装置包括：对一个有序枚举型属性集G＝＜a₁，a₂，...， a_n＞，各属性对应的域为V＝[V₁，V₂，...，V_n]，其中i＝1，2，...，n为具体取值 范围，依据概率分布，进而构建基于Markov模型的多值依赖统计决策树模型；

其中，进行参数学习和剪枝算法装置包括：通过参数学习得到上述模型中的概率参 数，学习公式如下：

$P(a_1=v_{1m_1})=1-\underset{k_1=1}{\overset{m_1-1}{\Sigma }}P(a_1=v_{1k_1})$

$P(a_i=v_{i{m}_i}|a_{i-1}=v_{(i-1)k_{i-1}})=1-\underset{k_i=1}{\overset{m_i-1}{\Sigma }}P(a_i=v_{{\mathrm{ik}}_i}|a_{i-1}=v_{{(i-1)k}_{i-1}})=1,i=\mathrm{2,3},...,n$

表示样本数据中的概率，表示在属性a_i-1取值 的条件下，属性a_i取值的概率，k₁＝1，2，...，m₁，k_i＝1，2，...，m_i；

在学习过程中，利用剪枝算法，将不会出现关联的节点删除，具体算法如下：

若或则将该树枝连接的结点为树根的子树删 除；

数据生成时，从根结点出发，依概率依次生成各属性值，直到生成树的叶子结点，完成 实体基本信息自动生成。

在实际应用时，多值依赖统计决策树的构建可以与参数学习和剪枝策略同步进行，在参 数学习和剪枝完成时，也完成了决策树的构建。构建出的决策树即为对应枚举型属性组的生 成树，数据生成时，从根结点出发，依概率依次生成各属性值，直到生成树的叶子结点。

尽管已经示出和描述了本发明的实施例，对于本领域的普通技术人员而言，可以理 解在不脱离本发明的原理和精神的情况下可以对这些实施例进行多种变化、修改、替换 和变型，本发明的范围由所附权利要求及其等同限定。