一種監(jiān)督型的連續(xù)屬性離散化算法的研究

黃巧云

(福州大學(xué) 至誠學(xué)院 計算機工程系，福建 福州 350002)

連續(xù)型屬性離散化問題作為數(shù)據(jù)預(yù)處理中的一種基礎(chǔ)核心技術(shù)，一直備受關(guān)注，探索該問題的有效解決方案是提高數(shù)據(jù)處理效率的關(guān)鍵研究內(nèi)容，具有十分重要的現(xiàn)實意義。目前，國內(nèi)外學(xué)者提出了很多方法，比較著名的有：等距離劃分方法、信息熵方法，貝葉斯決策法等。但這些方法在本質(zhì)上都是對屬性的硬劃分，而現(xiàn)實中事物之間的邊界通常是模糊的，因此在劃分地過程中如何適當(dāng)?shù)匾氩淮_定性，使得對連續(xù)數(shù)據(jù)的劃分能夠與實際的數(shù)據(jù)分布相符合，是一般的硬劃分方法很難做到的。根據(jù)上述問題，提出一種監(jiān)督型的連續(xù)屬性離散化算法，利用云變換將連續(xù)屬性的定義域劃分為多個基于云的定性概念，以實現(xiàn)定義域區(qū)間的粗劃分，由于云模型軟劃分的特性，在定性概念邊界的數(shù)據(jù)存在亦此亦彼性，所以自然地引入了不確定性；接著利用屬性對類別的決定作用，通過計算云模型分界處的評價函數(shù)來判斷其重要性，并決定是否對該區(qū)域進行歸并處理；最后利用云模型邊界數(shù)據(jù)的模糊性，對邊界數(shù)據(jù)進行自適應(yīng)調(diào)整，最終實現(xiàn)離散化的目的。

1 理論研究

1.1 云模型

設(shè)論域U={x1，x2，…，xm}，A是關(guān)于U上的定性概念，若論域中的元素xi對A的隸屬確定度CA(xi）∈[0，1]是一個有穩(wěn)定傾向隨機數(shù)，則確定度CA(xi）在論域上的分布稱為云模型，簡稱云[1]。

云的數(shù)字特征可以用期望值Ex，熵En和超熵He 3個數(shù)值來表示，其中期望值Ex反映模糊概念的信息中心；熵En指云的期望曲線的帶寬，是概念模糊度的度量；超熵He反映云的離散程度[1]。如式（1）所示：

1.2 云變換

云變換[2]根據(jù)某種規(guī)律把任意一個不規(guī)則的空間數(shù)據(jù)分布進行數(shù)學(xué)變換，生成原子概念的云模型集，使之成為若干個大小不同的云的疊加。每個云代表一個離散的、定性的概念，疊加的云的個數(shù)越多，誤差越小。即：

其中g(shù)（x）為數(shù)據(jù)分布函數(shù)，fi(x）為云模型的期望函數(shù)，ci為系數(shù)，m為疊加的云的個數(shù)，e為誤差閾值。

峰值云變換算法[2]認為空間數(shù)據(jù)分布的局部最高點即數(shù)據(jù)匯聚中心。根據(jù)“高頻率元素對定性概念的貢獻大于低頻率元素對定性概念的貢獻啟發(fā)性”的原理，把它作為概念中心即云模型的數(shù)學(xué)期望是合理的。峰值越高，表示數(shù)據(jù)匯聚越多，就應(yīng)優(yōu)先考慮其所表示的定性概念，其算法步驟下所示：

Step1:初始化云模型集為空，輸入數(shù)據(jù)分布函數(shù)g（x）和誤差閾值e。

Step2：判斷g（x）的最大值是否超過誤差閾值，是則將g（x）的峰值點作為云模型的重心Ex，否則轉(zhuǎn)至步驟5。

Step3:計算用于擬合f（x）的以Ex為期望值的云模型的熵和類型，并將該擬合的云模型加入云模型集。

Step4：計算擬合殘差 g（x），轉(zhuǎn)至步驟 2。

Step5：計算各云模型的超熵，輸出云模型集。

2 監(jiān)督型的連續(xù)屬性離散化算法

在粗糙集理論中，決策表[3]是一類特殊而重要的知識表達系統(tǒng)，它表示當(dāng)滿足某些條件時，應(yīng)當(dāng)如何進行決策。通常是由一個四元組S=（U,R,V,f）來表示，其中U為對象的非空有限集合稱為論域；R為屬性集合；V=∪Vr，Vr是屬性r的值域；f：U×R→V為信息函數(shù)，它指定了U中每個對象的每個屬性值。

在具有連續(xù)屬性的決策表中，令r∈C為某一連續(xù)屬性，對其離散化可以看作是根據(jù)論域U中的每一個對象在連續(xù)屬性r上的取值，依據(jù)某種準則對論域U進行的一種劃分。對于決策表來說，如果條件屬性的劃分較粗，則可能導(dǎo)致劃分后的決策表不相容，如果劃分較細，又使得劃分后的決策表中含有很多冗余信息，不利于數(shù)據(jù)約簡。又由于現(xiàn)實中事物的邊界通常是模糊的，所以對數(shù)據(jù)的劃分過程要適當(dāng)?shù)匾氩淮_定性，使得對連續(xù)數(shù)據(jù)的劃分能夠與實際的數(shù)據(jù)分布相符合。

該算法對決策表中的條件屬性是一一進行處理的。首先利用云變換實現(xiàn)屬性定義域區(qū)間的粗劃分；接著通過評價函數(shù)計算云模型分界處對分類的重要性，以此決定是否對已劃分區(qū)域進行歸并處理；通過獲得劃分的云模型集，以實現(xiàn)連續(xù)屬性離散化目的。

2.1 相關(guān)定義

定義1設(shè)論域U={u}，A1(Ex1,En1,He1)和A2(Ex2,En2,He2)是論域U上的兩個相鄰的基本云模型.如果 Ex1＜Ex2,那么 A1與 A2進行綜合得到新的云模型 A3(Ex3,En3,He3)：A3=A1∪A2[4]。

信息熵越小，則說明子集所包含對象的類別越一致。當(dāng)H（x）=0時，子集中對象的決策屬性值都相同。

定義3假設(shè)X1和X2為兩個相鄰云模型，其對象的個數(shù)分別為和，其中決策屬性為i（1,2，…，n）所占的對象個數(shù)為ki，則該云模型分界處的評價函數(shù)定義為：

當(dāng)Y值越小，則區(qū)間X1和X2合并所引起熵的變化較小，即合并X1和X2可使信息損失較小，合并后的區(qū)間中對象類別一致性程度較大。

2.2 算法描述

輸入：決策表S=（U,R,V,f），其中R=C∪D為屬性集合，論域為U,條件屬性集C均為連續(xù)屬性，決策屬性集為D。

輸出：離散化后的決策表。

算法步驟：

Step1:根據(jù)數(shù)據(jù)分布，生成每個連續(xù)屬性的數(shù)據(jù)分布概率密度函數(shù)；

Step2:利用峰值云變換算法，將連續(xù)屬性數(shù)據(jù)分布轉(zhuǎn)換為多個云模型表征的定性概念的集合；

Step3:將連續(xù)屬性映射到概念集中的相應(yīng)概念上,并對概念集用0，1，2，3,…，進行編碼，實現(xiàn)對連續(xù)屬性初步離散化；

Step4:對論域中的對象，根據(jù)云的數(shù)字特征，計算它們對各個云模型的隸屬度，并進行標識；

Step5:輸出離散化后的決策表。

3 仿真實驗

3.1 實驗數(shù)據(jù)及參數(shù)設(shè)置

為了驗證所提出的離散化模型有效性，實驗數(shù)據(jù)采用UCI數(shù)據(jù)庫的數(shù)據(jù)集Iris，該標準數(shù)據(jù)集被廣泛用于對連續(xù)屬性離散化算法的測試。數(shù)據(jù)集中共有150條記錄，每條記錄有5個屬性，其中4個連續(xù)屬性，最后一個用于標識記錄的類別。

3.2 實驗結(jié)果及分析

圖1～4為利用云模型對Iris的4個連續(xù)屬性進行離散化所得到的結(jié)果。

由圖可知,利用云模型對決策表的連續(xù)屬性進行軟劃分，能夠較好地反映數(shù)據(jù)的實際分布情況。由于云模型具有模糊性和不確定性，同樣的數(shù)值可以得到不同的隸屬度，所以在兩個概念相交的區(qū)域，數(shù)值相同的元素，在不同的情況下，可以被劃分到不同的概念中，這就實現(xiàn)了對數(shù)據(jù)的軟劃分，且離散化結(jié)果也與實際數(shù)據(jù)分布較為符合。

圖1 連續(xù)屬性1離散化結(jié)果

圖2 連續(xù)屬性2離散化結(jié)果

圖3 連續(xù)屬性3離散化結(jié)果

圖4 連續(xù)屬性4離散化結(jié)果

由于云模型具有模糊性，可能會造成離散化后的決策表不相容。雖然一般的決策表離散化算法要求離散化后的決策表是相容的，但在實際中，為了使最后獲得的決策規(guī)則具有更好的適應(yīng)性和魯棒性，一般都要適當(dāng)?shù)匾胍欢ǖ牟淮_定性，這也符合現(xiàn)實世界中事物存在的本來狀態(tài)。

3.3 算法改進

在引入不確定性的前提下，為了進一步提高決策表的一致性水平，利用屬性對類別的決定作用，通過計算云模型分界處的評價函數(shù)，以此決定是否對已劃分區(qū)域進行歸并處理，進一步減少劃分的屬性區(qū)間的個數(shù)。

輸入：決策屬性集D，初始劃分的云模型集Cloud，誤差閾值e。

輸出：離散化后的決策表。

算法步驟：

Step1：根據(jù)公式（6），計算每個云模型的信息熵y；

Step2：根據(jù)公式 （7），依次計算相鄰兩個云模型的分界處評價函數(shù)Y并進行判斷，如果，從Cloud中刪除這兩個相鄰的云模型，并根據(jù)公式（3）～（6）計算合并后的云模型，加入至中；

Step3：如果Cloud中每個云模型的對象都有相同的決策屬性或者Cloud中云模型的個數(shù)已不再發(fā)生更改，則轉(zhuǎn)至步驟4；否則轉(zhuǎn)至步驟2；

Step4：依次判斷同時位于相鄰兩個云模型之間的對象,分別計算其隸屬于不同云模型情況下的信息熵，并將其劃分到信息熵較小的云模型，以進行一種自適應(yīng)調(diào)整；

Step5：輸出離散化后的決策表。

為了驗證該算法的有效性，對離散化后的數(shù)據(jù)用Weka數(shù)據(jù)挖掘工具提供的J－48分類器、IB1分類器和BayesNet分類器進行分類實驗，將改進前的算法（Algorithm1）以及改進后的算法（Algorithm2）作為對比。

衡量一個離散化算法的標準，通常從兩個方面著手：（1）離散化后的斷點數(shù)，即基云的個數(shù)；（2）離散化后的數(shù)據(jù)對后續(xù)分類算法是否有效。

表1表示在不同算法下的離散化結(jié)果，其中Att1，Att2，Att3，Att4分別表示Iris數(shù)據(jù)集的4個屬性；表2表示兩種離散化結(jié)果在不同分類器下的分類結(jié)果。從上表可以看出，在引入不確定性的前提下，利用云模型與信息熵相結(jié)合所構(gòu)成的離散化算法，仍可以得到較高的分類識別率。改進后的離散化算法所得到的基云個數(shù)更少，有利于降低數(shù)據(jù)規(guī)模；同時，在不同分類器的作用下，改進后的離散化算法精確度更高，誤識率更低。實驗結(jié)果證明，該監(jiān)督型的連續(xù)屬性離散化算法是一種有效的方法。

表1 離散化后基云的個數(shù)

表2 分類測試結(jié)果

3.4 算法復(fù)雜性分析

假設(shè)記錄個數(shù)為n，僅考慮對一個連續(xù)屬性進行離散化的復(fù)雜性分析。

數(shù)據(jù)的概率密度函數(shù)的生成為O（n）；云變換的執(zhí)行時間為O（m×n），其中m為生成的云模型的個數(shù)；信息熵的計算為；O（m）云模型歸并的時間為 O（m2）；邊界數(shù)據(jù)自適應(yīng)調(diào)整時間 O（n×n×（m-1））。因此，對于一個連續(xù)屬性離散化的時間復(fù)雜度為O（n×n×m），對于一張決策表的離散化時間復(fù)雜度為 O（n×n×m×k），k 為條件屬性個數(shù)。

4 結(jié)束語

本文提出的基于監(jiān)督型的連續(xù)屬性離散化模型，利用云變化實現(xiàn)屬性區(qū)間的劃分，由于云模型軟劃分的特性，適當(dāng)?shù)匾肓瞬淮_定性，這更加符合實際數(shù)據(jù)分布和人的思維方式；利用屬性對類別的決定作用，對初始劃分區(qū)域進行歸并，能夠有效提高信息系統(tǒng)中信息的粒度，并降低數(shù)據(jù)規(guī)模。實驗結(jié)果表明，該算法具有較少的離散化區(qū)間數(shù)以及具有較高的分類精度。

［1］李德毅.知識表示中的不確定性［J］.中國工程科學(xué)，2000，2（10）：73－79.

［2］杜鹢，李德毅.基于云模型的概念劃分及其在關(guān)聯(lián)采掘上的應(yīng)用［J］.軟件學(xué)報，2001，12（2）：196－203.

［3］劉清.Rough集及 Rough推理［M］.北京：科學(xué)出版社，2001.

［4］蔣嶸，李德毅，范建華.數(shù)值型數(shù)據(jù)的泛概念樹的自動生成方法［J］.計算機學(xué)報，2000，23（5）：470－476.

［5］FAYYAD U M，IRANI K B.On the handling of continuous－valued attributes in decision tree generation ［J］.Machine Learning， 1992，8（1）：87－102.