張艷瓊鄧三鴻

（1．南京特殊教育師范學院信息科學學院，江蘇南京210038；2．南京大學信息管理學院，江蘇南京210023；3．江蘇省數據工程與知識服務重點實驗室（南京大學），江蘇南京210023）

基于云變換的突發(fā)事件屬性概念樹的構建

張艷瓊1，2，3鄧三鴻2，3

（1．南京特殊教育師范學院信息科學學院，江蘇南京210038；2．南京大學信息管理學院，江蘇南京210023；3．江蘇省數據工程與知識服務重點實驗室（南京大學），江蘇南京210023）

針對突發(fā)事件屬性具有模糊性、隨機性等特點，將云變換理論引入到突發(fā)事件屬性概念樹構建研究中，在原有算法基礎上，引入梯形云模型，提出一種基于多類型云的概念提取方法，不僅較好地解決了突發(fā)事件屬性的模糊性、隨機性等不確定性問題，而且在提高擬合數據分布曲線精度的同時減少云模型的個數。以全球恐怖主義研究數據庫為例，正確有效地構建nkill屬性概念樹，為高質量地進行數據挖掘提供科學而有效的數據預處理方法。

突發(fā)事件；概念樹；云變換；梯形云

突發(fā)事件是指突然發(fā)生，造成或者可能造成嚴重社會危害，需要采取應急處置措施予以應對的自然災害、事故災難、公共衛(wèi)生事件和社會安全事件［1］。隨著人口、環(huán)境和能源等方面問題的日益突出，全球范圍內的突發(fā)事件頻繁發(fā)生，多年來，積累了海量的各類突發(fā)事件案例，以恐怖事件為例，僅全球恐怖主義研究數據庫（Global Terrorism Database，GTD）就收錄了125 000多項案例［2］。突發(fā)事件案例是重要的數據資源，如何對這些數據資源進行分析和處理，發(fā)現其中潛在、未知的知識和規(guī)律，為突發(fā)事件管理決策服務，是目前急需解決的問題。一方面，直接面對數據庫中原始概念層的海量細節(jié)信息，往往無法得到有意義的知識，而對原始較低粒度的概念進行提升，抽象出較高的概念層，可以發(fā)現更普遍、更有指導意義的知識；另一方面，對于在論域上不同概念之間的關系，人們習慣劃分層次，從宏觀、中觀、微觀上理解概念之間的層次關系，形成概念的樹狀結構，所謂的宏觀、中觀、微觀又涉及到概念的粒度表征，概念粒度越大，涵蓋的數據范圍越廣，概念越抽象和宏觀，概念粒度越小，涵蓋的數據范圍越窄，概念越具體和精細［3］。因此，如何表示不同粒度的概念以及概念之間的層次關系，即構建概念樹，成為知識發(fā)現研究面臨的一個基礎問題。

突發(fā)事件具有事發(fā)突然、隨機性、模糊性等不確定性特點，如何在構建突發(fā)事件屬性概念樹的過程中體現層次之間的不確定性呢？等距離和等頻率區(qū)間法等傳統的概念提取方法對論域實行硬劃分，不允許概念中有模糊性，不符合人的認知規(guī)律，而且傳統概念樹的形成也無法反映數據的實際分布情況［3］，因此，傳統構建方法無法滿足突發(fā)事件屬性概念樹的構成。李德毅、蔣嶸、杜 等在結合概率論和模糊數據學理論的基礎上提出的云模型能統一刻畫概念中的隨機性、模糊性及其關聯性，并在云模型的基礎上提出云變換（Cloud Transformation）思想實現概念的軟劃分，此方法不僅較好地體現出概念的不確定性，而且能夠根據數據的實際分布實現概念的劃分［4－5］。用云變換實現概念劃分的方法，具有一定的優(yōu)勢，得到不少學者的關注。Liu等采用數據場與云模型相結合的方法構建范概念樹，用于空間數據挖掘［6］；Weng等將基于云變換構建的概念樹用于電價的預測［7］；秦昆等針對云變換過程中，用云模型對頻率分布函數進行擬合部分進行算法改進，提出了一種新的云變換曲線擬合方法［8］；孟暉等對原有的概念躍升算法進行改進，在進行概念云合并時考慮幅度系數的影響［9］；蔣建兵等在分析現有正態(tài)云的概念劃分和概念提升方法的基礎上，提出了引入梯形云后新的云變換和軟或操作方法，但文章中并沒有給出實例論證［10］；Z Wang提出基于梯形云模型的數值關聯規(guī)則的挖掘方法［11］；馬政朝等運用梯形云概念提升算法對物聯網安全數據的定義域進行劃分，并對劃分結果進行合理提升［12］。趙會園等對傳統的云變換算法中熵的估計步驟進行改進，并應用到農業(yè)領域本體概念的構建中［13］；劉玉超提出用云模型中數字特征構建概念含混度作為概念外延共識程度的衡量，設計并實現了高斯云變換算法，將問題域中的數據分布自動轉換為多粒度的不同概念，構建出人類概念認知中的泛概念樹［14］。

本文借鑒上述的算法思想，針對突發(fā)事件屬性特征，提出一種基于多類型云的云變換的算法，對突發(fā)事件屬性實現原子概念的歸納提取，通過對原子概念的提升，逐層構建出突發(fā)事件屬性概念樹。這種突發(fā)事件屬性概念樹的構建方法，避免了傳統概念劃分邊界過硬的問題，較好地解決突發(fā)事件存在的模糊性和隨機性等不確定性問題，為更好地進行突發(fā)事件知識發(fā)現提供了一種科學而有效的數據預處理的方法。

1 相關理論簡介

1.1 云模型概念

云模型是用自然語言值表示的定性概念與其定量數據表示之間的不確定性轉換模型，主要反映客觀世界中事物或人類知識中概念的模糊性和隨機性，并把兩者完全集成在一起，構成定性概念和定量數據相互間的轉換，深刻揭示了客觀對象具有的模糊性和隨機性［3］。云模型用期望Ex、熵En、超熵He 3個數字特征整體表征一個概念，見圖1。期望Ex是云滴在論域空間分布的期望，是最能夠代表定性概念的點，或者說是這個概念量化的最典型樣本。熵En是定性概念不確定性的度量，由概念的隨機性和模糊性共同決定。一方面，熵En是定性概念隨機性的度量，反映了能夠代表這個定性概念的云滴的離散程度；另一方面，又是定性概念亦此亦彼性的度量，反映了在論域空間可被概念接受的云滴的取值范圍。超熵He是熵的不確定性度量，即熵的熵，由熵的隨機性和模糊性共同決定［3］。云分為完整云、左半云和右半云，半云表示單側特性，見圖2。

圖1 正態(tài)云模型（25，3，0.3）的云圖［15］

1.2 梯形云模型

從圖1中可以看出，在正態(tài)云圖中，只有當定量值x取值為期望Ex時，x的確定度才為1，而在現實生活中，描述某一類概念時，經常是不止一個元素完全屬于此概念，而是一個區(qū)間的元素都屬于此概念，因此，期望為一數值區(qū)間的時候更具一般性。當期望取值為數值區(qū)間時，便成為梯形云模型。梯形云較正態(tài)云更具有一般性，正態(tài)云是梯形云中一特殊類型，見圖3。梯形云模型的數字特征由4個特征值來表示，即C（Exl，Exr，En，He），其中Ex1≤Ex2，期望區(qū)間為［Exl，Exr］，當Exl＝Exr時，C表示正態(tài)云模型。

當通過梯形云期望和熵可以確定梯形云期望曲線方程：

從圖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）的疊加，每個云代表一個離散的定性的概念，這種從連續(xù)的數值區(qū)間到離散的概念的轉換過程，稱為“云變換”［3］。

其數學表達式為：

其中，ai為幅度系數；n為變換后生成離散概念的個數；ε（x）為誤差曲線。

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

從數據挖掘的角度看，云變換是從某個粗粒度概念的某一屬性的實際數據分布中抽取更細粒度概念，出現頻率高的數據值對定性概念的貢獻率大于出現頻率低的數據值［3］。

2 突發(fā)事件屬性概念樹的構建

突發(fā)事件種類繁多，每一類型的突發(fā)事件由不同的屬性進行描述，具有不同的知識范疇，即使是屬于同一大類別的突發(fā)事件的屬性也不盡相同，如，同屬于自然災害的火災和地震。因此，很難用統一的模型來描述所有的突發(fā)事件的屬性。但經分析發(fā)現，突發(fā)事件的屬性特征的類型是有限的。本文將這些屬性類型分為：字符型、數值型和語言值型。字符型是指精確的文本字符值，如突發(fā)事件發(fā)生的地點、突發(fā)事件所屬的類別等。數值型是指通過觀察、統計可以得到的數值，如死亡人數、財產損失值等，語言值型是指用語言值表達某定性值，如恐慌程度等。一般字符型和語言值型的屬性概念樹的構建需要領域專家的參與，不在本文的討論范圍內，因此本文只對數值型屬性概念樹進行研究。

2.1 概念提取

概念提取就是從連續(xù)的數據中提取出離散的概念的過程。傳統的方法主要有：等距離區(qū)間法和等頻率區(qū)間法。等距離區(qū)間法是將論域主觀劃分為多個寬度相等的子區(qū)間。等頻率區(qū)間法是依據屬性值發(fā)生的頻率，將論域劃分為頻率寬度相同的子區(qū)間。這些方法都沒有考慮實際的數據分布情況，也不能反映從實際的連續(xù)數據中抽取定性概念的不確定性。為解決上述問題，在云模型表示定性概念的基礎上，引入云變換的思想，可以實現連續(xù)數據的離散化［3］。

設突發(fā)事件某屬性X的頻率分布函數f（x），根據X的實際頻率分布情況，自動生成若干粒度不同的云C（Exi，Eni，Hei）的疊加，每個云代表一個離散、定性的概念，實現從連續(xù)數值區(qū)間到離散概念的轉換過程。文獻［5］提出一種基于峰值法的云變換方法，即數據頻率分布中的局部極大值點是數據的匯聚中心，可作為概念的中心，云模型的數學期望；峰值越高，表示數據匯聚越多，優(yōu)先考慮其反映的定性概念，在原分布中減去該定性概念對應的數值部分，再尋找局部極大值，依次類推。但此方法就如何擬合變化的頻率分布曲線沒有做具體說明，對于峰值波動不大的情況，擬合精度較高時，就會出現較多的擬合云模型，增加計算復雜度。文獻［8］用梯形云模型代替正態(tài)云模型進行曲線擬合進行了改進，本文借鑒文獻［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）≤θ，則繼續(xù)尋找下一個右波峰點，直到abs（r－l）＞θ，Exri＝r；

b．若r＝g，則云模型為右半梯形云，Exri＝g；若abs（r－l）≤θ，則繼續(xù)尋找下一個左波峰點，直到abs（r－l）＞θ，Exli＝l；

c．若l≠g且r≠g，如果abs（r－l）＞θ，則云模型為正態(tài)云Exli＝Exri＝g；否則，從左右兩邊繼續(xù)尋找下一個波峰點，直到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根據突發(fā)事件屬性域中數據值的分布情況，自動生成一系列由云模型表示的基本概念，實現對論域的軟劃分。概念躍升就是在這些云模型表示的基本概念的基礎上，通過合并相鄰云概念，生成更高層次的云概念，達到概念提升來提升知識的粒度。概念躍升主要有3種策略：（1）用戶預先指定躍升的概念粒度，即用戶指定概念個數；（2）自動躍升，不預先由用戶指定，而是根據具體情況，自動將概念躍升到合適的概念粒度；（3）人機交互式地躍升，即用戶干預并具體指導概念的躍升［3］。本文采用第（2）種策略進行概念躍升。概念粒度提升主要是通過云綜合來完成，即將兩朵或多朵相同類型的子云進行綜合，生成有朵新的高層概念的父云?？梢允褂谩败浕颉痹凭C合法和“積分”云綜合法?！败浕颉痹凭C合法簡單易于計算，本文采用“軟或”云綜合法。一般，只會在頻率分布曲線的兩端才會出現半云模型，因此，兩類云模型進行云綜合只會出現3種情形：（1）右半云與全云；（2）全云與全云；（3）全云與左半云；其中，全云包括正態(tài)云和梯形云。

算法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規(guī)則，δ的取值一般小于3。

算法3：概念樹的生成

輸入：云變換生成的原子概念集合C，距離閾值δ

輸出：概念樹Clay

算法步驟：

3 實 例

本文實驗數據來源于全球恐怖主義研究數據庫（簡稱數據庫）［2］，該數據庫包含了從1970－2013年全球超過125 000例恐怖襲擊的相關信息，每個案例至少包含45個特征屬性變量，其中最近發(fā)生的事件包含有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，但是從概念意義實現了從“無”到“有”的飛躍，在突發(fā)事件的數值分類上一般把“0”值單獨劃分為一類，在本文的處理中，“0”不參與計算，如果處于別的考慮也可以將其加入計算，計算方法不變。

3.1 不確定性概念提取

圖6是恐怖主義研究數據庫中nkill字段數據的頻率分布圖。從圖6中可以看出，nkill數據的分布具有非常嚴重的偏倚現象，為了更好地進行概念提取，必須對頻率進行對數變換，令頻率′＝log2（頻率＋1），經轉換后nkill數據分布曲線如圖7所示。

圖6 原始數據曲線分布圖

圖7 變換后數據的曲線分布圖

經過對nkill數據進行算法1運算，得到一系列由半云、梯形云和正態(tài)云組成的原子概念。圖8給出了這些定性概念所對應的云模型，以及這些云模型的期望曲線的疊加。從圖7可以看出，通過云變換得到的定性概念所對應的云模型的期望曲線的疊加非常好地反映了實際的數據分布情況。為了說明此算法的優(yōu)越性，本文將其與基于正態(tài)云擬合的云變換算法進行比較。在相同參數設置環(huán)境下，相同數據經過基于正態(tài)云擬合的云變換算法運算后，得到的原子概念所對應的云模型如圖9所示。本文算法共得到44個不同類型的云模型，而基于正態(tài)云的云變換算法得出59個云模型，前者的殘差方差值為0.1231，后者的殘差方差值為0.1577。由此可以本文改進的算法不僅提高了擬合的精度，而且減少了云模型的個數。

圖8 基于多類型云模型的數據分布圖

圖9 基于正態(tài)云模型的數據分布圖

3.2 概念躍升及概念樹的構建

按照概念云綜合算法，對原子概念進行第一輪合并，得到12個較細粒度的不確定概念，見圖10。然后對這12個較細度的不確定型概念進行近一步的合并，最后得到5個粗粒度的不確定型概念，其對應的云模型，見圖11，圖12表示概念云的合并過程，圖12中每個方框表示一個概念云，格式為C（Ex1，Ex2，En，He，Type），其中，Type表示概念云的類型，1表示右半梯形云，2表示左半梯形云，3表示完整梯形云，4表示完整正態(tài)云。

圖10 經過概念合并后得到的12個不確定性概念

圖11 經過概念合并后得到的5個不確定性概念

圖12 概念云的合并過程

最終得到的5個不確定性概念較為客觀地反映了突發(fā)事件nkill數據的分布情況。從最初的44個概念躍升至最終的5個概念的過程，就是突發(fā)事件屬性nkill概念樹的構建過程。該方法不需要人為參與干預，可以直接從數據庫中抽取概念，構建概念層次關系，形成概念樹。

4 結束語

本文通過分析現有的概念提取和概念躍升方法，將梯形云模型引入到突發(fā)事件屬性的概念提取和概念躍升的過程中，對現有的云變換算法進行適當的改進，提出一種基于多類型云模型的云變換算法。此算法主要的特點是能根據數據分布曲線，自動選用合適的云模型類型去擬合數據分布函數，既能提高擬合精度，又能減少云模型的個數。

基于云變換構建的突發(fā)事件屬性概念樹充分考慮了原始數據的分布情況，較好地體現了概念的不確定性，而且還能隨著數據庫中數據的和誤差閾值的不斷變化進行相應的調整，為高質量地進行數據挖掘提供了一種行之有效的數據預處理方法，更有利于突發(fā)事件管理決策。

［1］國家突發(fā)公共事件總體應急預案［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］．北京：國防工業(yè)出版社，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］趙會園，李紹穩(wěn)，劉超，等．基于云變換的農業(yè)領域本體概念構建方法研究［J］．安徽師范大學學報：自然科學版，2015，（2）：123－128．

［14］劉玉超．一種自適應的多粒度概念提取方法——高斯云變換［J］．計算機工程與應用，2015，（9）：1－8．

［15］張艷瓊，陳祖琴，蘇新寧，等．基于云模型的突發(fā)事件分級模型研究［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

國家社會科學基金重大項目“面向突發(fā)事件應急決策的快速響應情報體系研究”（項目編號：13&ZD174）；地震科技星火計劃攻關項目“面向地震應急的空間智能決策方法”（項目編號：XH15019）。

張艷瓊（1982－），女，講師，在讀博士，研究方向：數據挖掘、智能信息處理。