基于云变换的突发事件属性概念树的构建

张艳琼邓三鸿

（1．南京特殊教育师范学院信息科学学院，江苏南京210038；2．南京大学信息管理学院，江苏南京210023；3．江苏省数据工程与知识服务重点实验室（南京大学），江苏南京210023）

基于云变换的突发事件属性概念树的构建

张艳琼1，2，3邓三鸿2，3

（1．南京特殊教育师范学院信息科学学院，江苏南京210038；2．南京大学信息管理学院，江苏南京210023；3．江苏省数据工程与知识服务重点实验室（南京大学），江苏南京210023）

针对突发事件属性具有模糊性、随机性等特点，将云变换理论引入到突发事件属性概念树构建研究中，在原有算法基础上，引入梯形云模型，提出一种基于多类型云的概念提取方法，不仅较好地解决了突发事件属性的模糊性、随机性等不确定性问题，而且在提高拟合数据分布曲线精度的同时减少云模型的个数。以全球恐怖主义研究数据库为例，正确有效地构建nkill属性概念树，为高质量地进行数据挖掘提供科学而有效的数据预处理方法。

突发事件；概念树；云变换；梯形云

突发事件是指突然发生，造成或者可能造成严重社会危害，需要采取应急处置措施予以应对的自然灾害、事故灾难、公共卫生事件和社会安全事件［1］。随着人口、环境和能源等方面问题的日益突出，全球范围内的突发事件频繁发生，多年来，积累了海量的各类突发事件案例，以恐怖事件为例，仅全球恐怖主义研究数据库（Global Terrorism Database，GTD）就收录了125 000多项案例［2］。突发事件案例是重要的数据资源，如何对这些数据资源进行分析和处理，发现其中潜在、未知的知识和规律，为突发事件管理决策服务，是目前急需解决的问题。一方面，直接面对数据库中原始概念层的海量细节信息，往往无法得到有意义的知识，而对原始较低粒度的概念进行提升，抽象出较高的概念层，可以发现更普遍、更有指导意义的知识；另一方面，对于在论域上不同概念之间的关系，人们习惯划分层次，从宏观、中观、微观上理解概念之间的层次关系，形成概念的树状结构，所谓的宏观、中观、微观又涉及到概念的粒度表征，概念粒度越大，涵盖的数据范围越广，概念越抽象和宏观，概念粒度越小，涵盖的数据范围越窄，概念越具体和精细［3］。因此，如何表示不同粒度的概念以及概念之间的层次关系，即构建概念树，成为知识发现研究面临的一个基础问题。

突发事件具有事发突然、随机性、模糊性等不确定性特点，如何在构建突发事件属性概念树的过程中体现层次之间的不确定性呢？等距离和等频率区间法等传统的概念提取方法对论域实行硬划分，不允许概念中有模糊性，不符合人的认知规律，而且传统概念树的形成也无法反映数据的实际分布情况［3］，因此，传统构建方法无法满足突发事件属性概念树的构成。李德毅、蒋嵘、杜 等在结合概率论和模糊数据学理论的基础上提出的云模型能统一刻画概念中的随机性、模糊性及其关联性，并在云模型的基础上提出云变换（Cloud Transformation）思想实现概念的软划分，此方法不仅较好地体现出概念的不确定性，而且能够根据数据的实际分布实现概念的划分［4－5］。用云变换实现概念划分的方法，具有一定的优势，得到不少学者的关注。Liu等采用数据场与云模型相结合的方法构建范概念树，用于空间数据挖掘［6］；Weng等将基于云变换构建的概念树用于电价的预测［7］；秦昆等针对云变换过程中，用云模型对频率分布函数进行拟合部分进行算法改进，提出了一种新的云变换曲线拟合方法［8］；孟晖等对原有的概念跃升算法进行改进，在进行概念云合并时考虑幅度系数的影响［9］；蒋建兵等在分析现有正态云的概念划分和概念提升方法的基础上，提出了引入梯形云后新的云变换和软或操作方法，但文章中并没有给出实例论证［10］；Z Wang提出基于梯形云模型的数值关联规则的挖掘方法［11］；马政朝等运用梯形云概念提升算法对物联网安全数据的定义域进行划分，并对划分结果进行合理提升［12］。赵会园等对传统的云变换算法中熵的估计步骤进行改进，并应用到农业领域本体概念的构建中［13］；刘玉超提出用云模型中数字特征构建概念含混度作为概念外延共识程度的衡量，设计并实现了高斯云变换算法，将问题域中的数据分布自动转换为多粒度的不同概念，构建出人类概念认知中的泛概念树［14］。

本文借鉴上述的算法思想，针对突发事件属性特征，提出一种基于多类型云的云变换的算法，对突发事件属性实现原子概念的归纳提取，通过对原子概念的提升，逐层构建出突发事件属性概念树。这种突发事件属性概念树的构建方法，避免了传统概念划分边界过硬的问题，较好地解决突发事件存在的模糊性和随机性等不确定性问题，为更好地进行突发事件知识发现提供了一种科学而有效的数据预处理的方法。

1 相关理论简介

1.1 云模型概念

云模型是用自然语言值表示的定性概念与其定量数据表示之间的不确定性转换模型，主要反映客观世界中事物或人类知识中概念的模糊性和随机性，并把两者完全集成在一起，构成定性概念和定量数据相互间的转换，深刻揭示了客观对象具有的模糊性和随机性［3］。云模型用期望Ex、熵En、超熵He 3个数字特征整体表征一个概念，见图1。期望Ex是云滴在论域空间分布的期望，是最能够代表定性概念的点，或者说是这个概念量化的最典型样本。熵En是定性概念不确定性的度量，由概念的随机性和模糊性共同决定。一方面，熵En是定性概念随机性的度量，反映了能够代表这个定性概念的云滴的离散程度；另一方面，又是定性概念亦此亦彼性的度量，反映了在论域空间可被概念接受的云滴的取值范围。超熵He是熵的不确定性度量，即熵的熵，由熵的随机性和模糊性共同决定［3］。云分为完整云、左半云和右半云，半云表示单侧特性，见图2。

图1 正态云模型（25，3，0.3）的云图［15］

1.2 梯形云模型

从图1中可以看出，在正态云图中，只有当定量值x取值为期望Ex时，x的确定度才为1，而在现实生活中，描述某一类概念时，经常是不止一个元素完全属于此概念，而是一个区间的元素都属于此概念，因此，期望为一数值区间的时候更具一般性。当期望取值为数值区间时，便成为梯形云模型。梯形云较正态云更具有一般性，正态云是梯形云中一特殊类型，见图3。梯形云模型的数字特征由4个特征值来表示，即C（Exl，Exr，En，He），其中Ex1≤Ex2，期望区间为［Exl，Exr］，当Exl＝Exr时，C表示正态云模型。

当通过梯形云期望和熵可以确定梯形云期望曲线方程：

从图3中可以看出，梯形云期望曲线光滑地穿过云滴“中间”，勾画出梯形云的整体轮廓，是云滴集合的骨架，所有云滴都在期望曲线附近做随机的波动［6］。图4是左半梯形云和右半梯形云图，只表示单侧特性。

图2 半云（25，3，0.3）的云图［15］

图3 梯形云模型（20，25，3，0.3）与期望曲线

1.3 云变换的简介

给定论域中某个数据属性X的频率分布函数f（x），根据X的属性值频率的实际分布自动生成若干个粒度不同的云C（Exi，Eni，Hei）的叠加，每个云代表一个离散的定性的概念，这种从连续的数值区间到离散的概念的转换过程，称为“云变换”［3］。

其数学表达式为：

其中，ai为幅度系数；n为变换后生成离散概念的个数；ε（x）为误差曲线。

图4 半梯形云（20，25，3，0.3）

从数据挖掘的角度看，云变换是从某个粗粒度概念的某一属性的实际数据分布中抽取更细粒度概念，出现频率高的数据值对定性概念的贡献率大于出现频率低的数据值［3］。

2 突发事件属性概念树的构建

突发事件种类繁多，每一类型的突发事件由不同的属性进行描述，具有不同的知识范畴，即使是属于同一大类别的突发事件的属性也不尽相同，如，同属于自然灾害的火灾和地震。因此，很难用统一的模型来描述所有的突发事件的属性。但经分析发现，突发事件的属性特征的类型是有限的。本文将这些属性类型分为：字符型、数值型和语言值型。字符型是指精确的文本字符值，如突发事件发生的地点、突发事件所属的类别等。数值型是指通过观察、统计可以得到的数值，如死亡人数、财产损失值等，语言值型是指用语言值表达某定性值，如恐慌程度等。一般字符型和语言值型的属性概念树的构建需要领域专家的参与，不在本文的讨论范围内，因此本文只对数值型属性概念树进行研究。

2.1 概念提取

概念提取就是从连续的数据中提取出离散的概念的过程。传统的方法主要有：等距离区间法和等频率区间法。等距离区间法是将论域主观划分为多个宽度相等的子区间。等频率区间法是依据属性值发生的频率，将论域划分为频率宽度相同的子区间。这些方法都没有考虑实际的数据分布情况，也不能反映从实际的连续数据中抽取定性概念的不确定性。为解决上述问题，在云模型表示定性概念的基础上，引入云变换的思想，可以实现连续数据的离散化［3］。

设突发事件某属性X的频率分布函数f（x），根据X的实际频率分布情况，自动生成若干粒度不同的云C（Exi，Eni，Hei）的叠加，每个云代表一个离散、定性的概念，实现从连续数值区间到离散概念的转换过程。文献［5］提出一种基于峰值法的云变换方法，即数据频率分布中的局部极大值点是数据的汇聚中心，可作为概念的中心，云模型的数学期望；峰值越高，表示数据汇聚越多，优先考虑其反映的定性概念，在原分布中减去该定性概念对应的数值部分，再寻找局部极大值，依次类推。但此方法就如何拟合变化的频率分布曲线没有做具体说明，对于峰值波动不大的情况，拟合精度较高时，就会出现较多的拟合云模型，增加计算复杂度。文献［8］用梯形云模型代替正态云模型进行曲线拟合进行了改进，本文借鉴文献［8］的思想，提出一种基于多类型云模型的云变换算法，此算法对拟合云模型的类型进行扩充，针对不同曲线段应用不同类型的云模型进行拟合，既减少了拟合云模型的个数，又有利于提高拟合精度，此算法思路见图5。

图5 基于多类型云模型的云变换算法流程图

具体算法步骤如下：

算法1：基于多类型云模型的云变换

输入：属性X的数据集合D；变换允许的误差阈值ε；波峰差阈值θ；

输出：n个离散的不同类型的原子概念的云模型集合Clounds。

算法步骤：

（1）对属性X的论域中每个可能属性值X，计算其在数据集合D中含有该属性值的记录个数y，得到属性X的频率分布函数f（x）。

（2）寻找频率分布函数f（x）的波峰值所在位置，将其属性值定义为云模型的中心点g。

（3）初始值设l＝g，r＝g；在中心点g的左右边寻找最相邻的波峰值，l＝左波峰值，r＝右波峰值。

（4）根据l和r的值，判断云模型的类型，并确定云模型期望Exli，Exri。

a．若l＝g，则云模型为右半梯形云，Exli＝g；若abs（r－l）≤θ，则继续寻找下一个右波峰点，直到abs（r－l）＞θ，Exri＝r；

b．若r＝g，则云模型为右半梯形云，Exri＝g；若abs（r－l）≤θ，则继续寻找下一个左波峰点，直到abs（r－l）＞θ，Exli＝l；

c．若l≠g且r≠g，如果abs（r－l）＞θ，则云模型为正态云Exli＝Exri＝g；否则，从左右两边继续寻找下一个波峰点，直到abs（r－l）＞θ，Exli＝l，Exri＝r。

（5）计算用于拟合f（x）的、以Exli，Exri为期望的云模型的熵，计算云模型的分布函数fi（x）。

（6）从f（x）中减去已知云模型的数据分布fi（x），得到新的数据分布函数f′（x），并在此基础上重复步骤（2）～（4），得到多个基于云的数据分布函数。

（7）根据已有的f（x），最后得到的拟合误差函数f′（x）及各个云模型的分布函数，计算基于云模型的定性概念的3个特征值。

2.2 概念跃升及概念树的生成

算法1根据突发事件属性域中数据值的分布情况，自动生成一系列由云模型表示的基本概念，实现对论域的软划分。概念跃升就是在这些云模型表示的基本概念的基础上，通过合并相邻云概念，生成更高层次的云概念，达到概念提升来提升知识的粒度。概念跃升主要有3种策略：（1）用户预先指定跃升的概念粒度，即用户指定概念个数；（2）自动跃升，不预先由用户指定，而是根据具体情况，自动将概念跃升到合适的概念粒度；（3）人机交互式地跃升，即用户干预并具体指导概念的跃升［3］。本文采用第（2）种策略进行概念跃升。概念粒度提升主要是通过云综合来完成，即将两朵或多朵相同类型的子云进行综合，生成有朵新的高层概念的父云。可以使用“软或”云综合法和“积分”云综合法。“软或”云综合法简单易于计算，本文采用“软或”云综合法。一般，只会在频率分布曲线的两端才会出现半云模型，因此，两类云模型进行云综合只会出现3种情形：（1）右半云与全云；（2）全云与全云；（3）全云与左半云；其中，全云包括正态云和梯形云。

算法2：“软或”云综合法

输入：给定2个云模型C1（Exl1，Exr2，En1，He1，type1），C2（Exl2，Exr2，En2，He2，type2）

输出：综合云模型C（Exl，Exr，En，He，type）

算法步骤：

（1）若type1为右半云，type2为全云，则根据下列公式计算：

（2）若type1，type2同为全云，则根据下列公式计算：

（3）若type1为全云，type2同为左半云，则根据下列公式计算：

通过对原子云模型运用云综合算法进行概念跃升可以得到较粗的粒度的概念，但不是距离最近的任何两个相邻的云模型都可以进行云综合算法，必须满足一定的条件。本文在软或操作中引入距离阈值δ，即距离函数d（C1，C2）＝Exr1－Exl2/（En1＋En2）≤δ，根据3En规则，δ的取值一般小于3。

算法3：概念树的生成

输入：云变换生成的原子概念集合C，距离阈值δ

输出：概念树Clay

算法步骤：

3 实 例

本文实验数据来源于全球恐怖主义研究数据库（简称数据库）［2］，该数据库包含了从1970－2013年全球超过125 000例恐怖袭击的相关信息，每个案例至少包含45个特征属性变量，其中最近发生的事件包含有120多个特征属性变量。本文以nkill（死亡人数）这一属性为例进行概念树的构建。由于各种原因，数据库中存在字段缺失现象，将nkill字段数据缺失的记录删除后，得到106 099例数据。从理论上说，nkill的取值范围nkill∈［0，∞），但从实际情况来看，随着nkill取值越高，数据的分布越稀疏，从本数据库的分布情况来看，nkill取值大于100，共有114例，其中nkill取值最大为1 382，由此可以看出：本数据nkill取值范围较广，数据分布非常稀疏，为了清晰的展示下文的效果图，100以后的这段数据不在示图中显示，但参与计算。另外，需要说明的是，nkill取值为0的记录共有57 363例，占总数的54.07%，nkill的取值从“0”到“1”，虽然数值之间只相差1，但是从概念意义实现了从“无”到“有”的飞跃，在突发事件的数值分类上一般把“0”值单独划分为一类，在本文的处理中，“0”不参与计算，如果处于别的考虑也可以将其加入计算，计算方法不变。

3.1 不确定性概念提取

图6是恐怖主义研究数据库中nkill字段数据的频率分布图。从图6中可以看出，nkill数据的分布具有非常严重的偏倚现象，为了更好地进行概念提取，必须对频率进行对数变换，令频率′＝log2（频率＋1），经转换后nkill数据分布曲线如图7所示。

图6 原始数据曲线分布图

图7 变换后数据的曲线分布图

经过对nkill数据进行算法1运算，得到一系列由半云、梯形云和正态云组成的原子概念。图8给出了这些定性概念所对应的云模型，以及这些云模型的期望曲线的叠加。从图7可以看出，通过云变换得到的定性概念所对应的云模型的期望曲线的叠加非常好地反映了实际的数据分布情况。为了说明此算法的优越性，本文将其与基于正态云拟合的云变换算法进行比较。在相同参数设置环境下，相同数据经过基于正态云拟合的云变换算法运算后，得到的原子概念所对应的云模型如图9所示。本文算法共得到44个不同类型的云模型，而基于正态云的云变换算法得出59个云模型，前者的残差方差值为0.1231，后者的残差方差值为0.1577。由此可以本文改进的算法不仅提高了拟合的精度，而且减少了云模型的个数。

图8 基于多类型云模型的数据分布图

图9 基于正态云模型的数据分布图

3.2 概念跃升及概念树的构建

按照概念云综合算法，对原子概念进行第一轮合并，得到12个较细粒度的不确定概念，见图10。然后对这12个较细度的不确定型概念进行近一步的合并，最后得到5个粗粒度的不确定型概念，其对应的云模型，见图11，图12表示概念云的合并过程，图12中每个方框表示一个概念云，格式为C（Ex1，Ex2，En，He，Type），其中，Type表示概念云的类型，1表示右半梯形云，2表示左半梯形云，3表示完整梯形云，4表示完整正态云。

图10 经过概念合并后得到的12个不确定性概念

图11 经过概念合并后得到的5个不确定性概念

图12 概念云的合并过程

最终得到的5个不确定性概念较为客观地反映了突发事件nkill数据的分布情况。从最初的44个概念跃升至最终的5个概念的过程，就是突发事件属性nkill概念树的构建过程。该方法不需要人为参与干预，可以直接从数据库中抽取概念，构建概念层次关系，形成概念树。

4 结束语

本文通过分析现有的概念提取和概念跃升方法，将梯形云模型引入到突发事件属性的概念提取和概念跃升的过程中，对现有的云变换算法进行适当的改进，提出一种基于多类型云模型的云变换算法。此算法主要的特点是能根据数据分布曲线，自动选用合适的云模型类型去拟合数据分布函数，既能提高拟合精度，又能减少云模型的个数。

基于云变换构建的突发事件属性概念树充分考虑了原始数据的分布情况，较好地体现了概念的不确定性，而且还能随着数据库中数据的和误差阈值的不断变化进行相应的调整，为高质量地进行数据挖掘提供了一种行之有效的数据预处理方法，更有利于突发事件管理决策。

［1］国家突发公共事件总体应急预案［EB/OL］．http：∥www．gov．cn/yjgl/2005－08/07/content-21048．htm，2013－07－22．

［2］National Consortium for the Study of Terrorism and Responses to Terrorism（START）．（2015）．Global Terrorism Database［Data file］．Retrieved from http：∥www．start．umd．edu/gtd．

［3］李德毅，杜 ．不确定性人工智能（第2版）［M］．北京：国防工业出版社，2014．5．

［4］蒋嵘，李德毅．数值型数据的泛概念树的自动生成方法［J］．计算机学报，2000，23（5）：471－477．

［5］杜 ，李德毅．基于云的概念划分及其在关联采掘上的应用［J］．软件学报，2001，12（2）：196－203．［6］Liu.YF，He.Q，Liu.W．．Cloud Segmentation of Spatial Concept Hierarchy Based on Data Field［C］．2008 4th International Conference on Wireless Communications，Networking and Mobile Computing，2008：12－17．

［7］Weng.YL，Shi.LD，zhao.JH．Price Spike Forecasting Using Concept－tree Approach based on Cloud Model［C］．2nd ISECS International Colloquium on Computing，Communication，Control and Management（CCCM 2009），2009：8－9．

［8］秦昆，王佩．基于云变换的曲线拟合新方法［J］．计算机工程与应用，2008，23：56－58，74．

［9］孟晖，王树良，李德毅．基于云变换的概念提取及概念层次构建方法［J］．吉林大学学报：工学版，2010，（3）：782－787．

［10］蒋建兵，梁家荣，江伟，等．梯形云模型在概念划分及提升中的应用［J］．计算机工程与设计，2008，（5）：1235－1237，1240．

［11］Z Wang．Quantitative Association Rules Mining Method Based on Trapezium Cloud Model［C］．Database Technology and Applications（DBTA），2010 2nd International Workshop on．IEEE，2010：1－4．

［12］马政朝，郑瑞娟，吴庆涛，等．一种物联网安全属性概念提取方法［J］．计算机仿真，2014，（3）：303－307．

［13］赵会园，李绍稳，刘超，等．基于云变换的农业领域本体概念构建方法研究［J］．安徽师范大学学报：自然科学版，2015，（2）：123－128．

［14］刘玉超．一种自适应的多粒度概念提取方法——高斯云变换［J］．计算机工程与应用，2015，（9）：1－8．

［15］张艳琼，陈祖琴，苏新宁，等．基于云模型的突发事件分级模型研究［J］．情报学报，2015，（1）：76－84．

（本文责任编辑：孙国雷）

The Building of Emergency Concept Tree based on Cloud Transformation

Zhang Yanqiong1，2，3Deng Sanhong2，3
（1．School of Information Science，Nanjing Normal University of Special Education，Nanjing 210038，China；2．School of Information Management，Nanjing University，Nanjing 210023，China；3．Jiangsu Key Laboratory of Data Engineering and Knowledge Service（Nanjing University），Nanjing 210023，China）

According to the emergency characteristics，such as fuzziness，randomness，the cloud transformation was used to build concept tree of emergency attribute．Including Trapezium cloud，a new concept extracting method based on multiple types of clouds is proposed in this paper，which not only solved the fuzziness，randomness problem，but only improved the accuracy of fitting the data distribution curve while reducing the number of cloud model．A test was given on Global Terrorism Database（GTD），the result showed that the algorithm can build concept tree of nkill property．

emergency；concept tree；cloud transformation；trapezium cloud

10．3969/j．issn．1008－0821．2016．02．009

TP393

A

1008－0821（2016）02－0046－07

2015－11－24

国家社会科学基金重大项目“面向突发事件应急决策的快速响应情报体系研究”（项目编号：13&ZD174）；地震科技星火计划攻关项目“面向地震应急的空间智能决策方法”（项目编号：XH15019）。

张艳琼（1982－），女，讲师，在读博士，研究方向：数据挖掘、智能信息处理。