基于決策強度的決策表連續(xù)屬性離散化算法

摘要：決策表中連續(xù)屬性離散化，即將一個連續(xù)屬性分為若干屬性區(qū)間并為每個區(qū)間確定一個離散型數(shù)值。該文提出一種新的決策表連續(xù)屬性離散化算法。首先使用決策強度來度量條件屬性的重要性，并據(jù)此對條件屬性按照屬性重要性從小到大排序，然后按排序后的順序，考察每個條件屬性的所有斷點，將冗余的斷點去掉，從而將條件屬性離散化。該算法易于理解，計算簡單，算法的時間復雜性為O(3kn2)。

關鍵詞：決策強度；連續(xù)屬性；離散化；決策表；粗糙集

中圖分類號：TP312文獻標識碼：A文章編號：1009-3044(2008)34-2013-03

Discretization of Continuous Attributes in Decision Table Based on Decision Power

LI Hai-peng1， GUI Xian-cai2

(1.Hujinchao Vocational Middle School， Shunde 528305， China; 2.Mathematics and Computational Science School， Zhanjiang Normal College， Zhanjiang 524048，China)

Abstract: The discretization of continuous attributes values of a decision system is divides continuous values into different space and allocates some discrete values to each space. In this paper a new discretization algorithm of continue attributes in decision table is offered. Firstly， the decision power used to measure the importance of condition attributes， according to which the condition attributes are sorted in an ascending order. Secondly， all break points of every condition attributes are examined and the redundant ones are eliminated. Finally， each value in the decision table is replaced by a number representing the break point， and then the decision table is discretized. The algorithm is constructed with good understandability and simple computation. The time complexity of this algorithm is O(3kn2).

Key words: decision power; continuous attributes; discretization; decision table; rough set

1 引言

波蘭科學家Pawlak提出的粗糙集(Rough set)理論[1，2]是一種新型的處理模糊和不確定知識的數(shù)學工具，目前已經(jīng)在人工智能、知識與數(shù)據(jù)發(fā)現(xiàn)、模式識別與分類、故障檢測等方面得到了較為成功的應用。

在一些決策系統(tǒng)中，有些條件屬性或決策屬性的值域為連續(xù)值，而運用粗糙集理論在處理決策表時，要求決策表中各值用離散值表達。 所以決策表中連續(xù)屬性的離散化，即實型屬性空間向整型屬性空間的映射，它是決策表中屬性約簡的第一步[2]。

該文形式化地描述了決策表的離散化問題，給出了決策強度的概念，利用決策強度作為屬性的重要性度量，提出了基于決策強度的決策表離散化算法，并分析了該算法的時間復雜度，最后用例子說明該算法的離散化過程。

2 基本概念

定義1[1-2] 決策表是一個四元組DT=，其中U ={x1，x2，…，xn}為論域，A=C∪D表示屬性集，C= {C1，C2，…，Cp}為條件屬性集，D ={D1，D2，…，Dq}為決策屬性集，V=■Va，V為屬性值的集合，Va表示屬性a∈A的值域；f： U×A→V是一個信息函數(shù)，它指定U中每一個對象x的屬性值，下文把決策表簡記為DT= 。

對任意B?哿A ，記RB ={(xi，xj)|f(xi，b)=f(xj，b)，?坌b∈B}，則RB是U上的等價關系，它們構成對U的劃分，記為U/B={[x]B | x∈U}，其中[x]B ={y∈U| (x，y)∈RB}。

定義2[2] 對決策表DT=，若RC?哿RD ，則稱決策表是一致的(協(xié)調(diào)的)，否則稱決策表是不一致的(不協(xié)調(diào)的)。

對一致決策表，當對象在條件屬性集上取值相同時，決策屬性值也必定相同；而不一致決策表，至少存在兩個對象，它們在條件屬性集上取值相同，但決策值卻不相等。

2.1 離散化問題的描述

在下文討論中假設決策屬性值為離散值，連續(xù)屬性變量僅出現(xiàn)在條件屬性中，不失一般性，以下僅考慮單個決策屬性的決策表。

設DT=是一個決策表，其中U ={x1，x2，…，xn}為論域，A=C∪{ｄ}表示屬性集，C ={C1 ，C2，…，Ck} 為條件屬性集合|C|=k，g0gggggg為決策屬性，設決策種類的個數(shù)為r(d)。屬性a的值域Va =[l a，ra]上的一個斷點可記為(a，c) ，其中a∈A，c為實數(shù)值。在Va=[la ，ra]上的任意一個斷點集合：Da ={(a，c1a)，(a，c2a)，…，(a ，ckaa)}定義了Va上的一個分類Pa ：

Pa ={[c0a，c1a)，[c1a，c2a)，…，[ckaa，cka+1a]}

la = c0a

Va =[c0a，c1a)∪[c1a，c2a)∪…∪[ckaa，cka+1a]

斷點集合Da將屬性a的取值分成ka+1個等價類，這里每一個cka就稱為一個斷點，離散化的目的就是對所有連續(xù)屬性都找到適宜的斷點集，因此，任意的P =■pa 定義了一個新的決策表：

DTp=(U，A，Vp，fp)，fp(xa)=i ?圳 f(xa)∈[cia，ci+1a]

對于x∈U，i∈{0，1，2，…，Ka}，即經(jīng)過離散化之后，原來的決策表被新的決策表所代替，且不同的斷點集將同一決策表轉(zhuǎn)換成不同的新決策表。

從粗糙集的觀點看，離散化的實質(zhì)是在保持決策表分類能力不變，即條件屬性和決策屬性相對關系不變的條件下，尋找合適的分割點集，對條件屬性構成的空間進行劃分。評價屬性離散化的質(zhì)量，主要看分割點的選擇和多少，以及保持決策系統(tǒng)所表達的樣本之間的“不可分辨關系”。最優(yōu)離散化，即為決策表尋找最小(最優(yōu)) 的斷點集是一個NP-hard 問題，為此必須尋找某種啟發(fā)式算法，人們提出了許多啟發(fā)式算法，可參考文獻[2-4]，該文利用條件屬性關于決策屬性的決策強度作為啟發(fā)式算法。

2.2 決策強度及其性質(zhì)

定義3[5] 給定決策表DT=，Xi∈U/C={X1，X2，…，Xn}，Yj∈U/D={Y1，Y2，…，Ym}，把sup p(Xi，Yj)=│Xi∩Yj│/│U│，稱為規(guī)則Xi→Yj的支持度。把cer(Xi，Yj)=│Xi∩Yj│/│Xi│，稱為規(guī)則的置信度或確定性因子。

支持度表明了規(guī)則適用的對象數(shù)目，亦可理解為決策規(guī)則Xi→Yj的強度。置信度反映了粗糙規(guī)則集的精確程度，規(guī)則集合的平均置信度越高，規(guī)則集合的一致性就好，精確度也高，相反粗糙規(guī)則的不確定性較大。

以上討論的是對單一規(guī)則的度量，是對單一決策規(guī)則的性質(zhì)描述。然而，在實際中，有必要從整體上討論一個決策表規(guī)則集合的整體性能，以此來衡量從一個樣本集合得到的規(guī)則知識庫的決策性能，并可對規(guī)則集合進行比較。

定義4[5] 給定決策表DT=，Xi∈U/C={X1，X2，…，Xn}，Yj∈U/D={Y1，Y2，…，Ym}， DP(C→D）=■■sup pp (Xi，Yj)cer (Xi，Yj)=■■Xi∩Yj│/│U││Xi∩Yj│/│Xi│稱DP(C→D）為條件屬性集C關于決策屬性集D的決策強度。

決策表的決策強度由所有規(guī)則的支持度與置信度共同決定的，體現(xiàn)了規(guī)則集合決策充分性判斷的整體程度，也可理解為規(guī)則集合的平均置信度。

當DP(C→D）=1，則決策表DT=為一致的決策表，否則為不一致的。

定理1[5]設U為論域，某個等價關系C1在U上形成的劃分為U/C1={X1，X2，…，Xn}，而U/C2={X1，X2，…，Xi-1，Xi+1，…，Xj-1，Xj+1，…，Xn，Xi∪Xj}是將劃分U/C1中的某兩個等價塊Xi與Xj合并為Xi∪Xj，而其余塊不變得到的新劃分，U/D={Y1，Y2，…，Ym}也是U上的一個劃分，則

DP(C1→D)≥DP(C2→D)

推論1[5]設DT=是決策表，任意 ai∈C ，i=1，2，…，m ，(m=|C|) ，則有：

DP({a1}→D)≤DP({a1}∪{a2}→D)≤…≤DP({a1} ∪…∪{am}→D)=DP(C→D)

定理1及推論1說明，如果將屬性集的分類進行合并，將可能導致決策表的決策強度的減少。從決策表屬性約簡的角度來看，當一個屬性被約簡掉，隨著屬性約簡的進行，條件屬性集關于決策屬性集的決策強度的變化規(guī)律呈現(xiàn)非嚴格單調(diào)遞減。實際也體現(xiàn)了不確定性的增大，二者具有一致性。

2.3 屬性重要性度量

粗糙集理論認為知識是將對象進行分類的能力，屬性的重要性是建立在屬性的分類能力上的，為了衡量屬性的重要性程度，可從表中刪除這一屬性，再來考察決策系統(tǒng)的分類會產(chǎn)生怎樣的變化：如果去掉屬性會相應地改變分類，則說明該屬性重要，反之，則說明該屬性的重要性低。

衡量屬性重要性程度的方法較多，有代數(shù)方法和信息論方法等[6]，本文利用條件屬性關于決策屬性的決策強度作為度量方法。

定義5設D T =〈U，C∪D，V，f 〉是一個決策表，BC ，則對任意條件屬性a∈{C-B}相對于決策屬性D的重要性SGF(a，B，D)定義為：

SGF(a，B，D)= DP(B∪{a}→D)- DP(B→D)

當B =Φ時，規(guī)定DP(Φ→D)=0，并簡記為SGF(a，D) = DP({a}→D)。

上述定義表明屬性a∈C-B關于屬性集B對決策屬性D的重要性由B中添加{a}后所引起的決策強度的變化大小來度量。SGF(a，B，D)的值愈大，說明屬性a∈C-B關于屬性集B 對決策屬性D愈重要。

3 決策表連續(xù)屬性的離散化

先介紹一下斷點的概念，斷點是將某個數(shù)值型屬性的值按照由小到大的順序排序，重復的數(shù)值只計一次，兩個相鄰屬性值的均值稱為一個斷點。在離散化之前需要先生成每個條件屬性的斷點集。

3.1 離散化算法

輸入：一個決策表DT=（U，C∪g0gggggg，V，f），其中U ={x1，x2，…，xn}，C={a1，a2，…，ak}

輸出：離散化的決策表。

Step1： 初始化候選斷點集，令CUT={ Ca1，Ca2，…，Cak }，其中Caj為屬性ai的候選斷點集

Step2： 根據(jù)條件屬性的屬性重要性由小到大對每個條件屬性ai (i=1，2，… ，k) 進行排序，在值相同的情形下，按條件屬性斷點個數(shù)從多到少進行排序，每個屬性的屬性重要性按如下步驟產(chǎn)生：

1) 令B=Φ是一鏈表，用來存儲已排過序的屬性；

2) 對C-B中的每一個屬性p，根據(jù)定義5計算其屬性重要性SGF(p，B，D)；

3) 選擇使SGF(p，B，D)最大的屬性(當同時有兩個以上的屬性達到最大值時，選取斷點個數(shù)最少的)，假設是p，則將p插入到B的頭部。如果|C|=|B|，轉(zhuǎn)step3;否則，轉(zhuǎn)2);

Step3： 對每個屬性aj ∈C 進行下面的過程：

Step4： 對屬性aj 中的每一個斷點cj ，考慮它的存在性，把決策表中與cj 相鄰的兩個屬性值的較小值改為較大值，如果決策表不引起沖突，則Caj = Caj \\{cj} ;否則，把修改過的屬性值還原。

Step5：此時CUT={ Ca1，Ca2，…，Cak }即為所求的斷點集，同時得到離散化后的決策表。

3.2 算法的時間復雜性

1) 求一個屬性的候選斷點集，要經(jīng)過排序和求平均，其時間復雜性為O(n2) ，所以Step1時間復雜性為O(kn2) ;

2) 計算決策強度DP({ai}→D)，屬性重要性SGF(p，B，D)的時間復雜性為O(kn2) ，對屬性重要性SGF(p，B，D)進行排序的時間復雜性為klogk ，所以Step2時間復雜性為O(kn2) ;

3) 把決策表中與cj相鄰的兩個屬性值的較小值改為較大值，檢驗決策表是否引起沖突的時間復雜性為O(n2)，所以完成Step3、Step4的時間復雜性為O(kn2)。

因此，整個算法的時間復雜性為O(3kn2)。

3.3 舉例

設原始決策表如表1所示[3]，其中， 條件屬性C={a，b}，決策屬性D=g0gggggg。顯然有：

U/g0gggggg={{1，4，6，7，8}，{2，3，5}}={Y1，Y2};

U/{a}={{1}，{2}，{3，6}，{4，5}，{7}，{8}}={X1，X2，X3，X4，X5，X6};

U/{b}={{1，5}，{2}，{3，7，8}，{4，6}}={Z1，Z2，Z3，Z4};

計算屬性重要性，開始B=Φ， SGF(a，D) = DP({a}→D)= ■■ │Xi∩Yj│/│U││Xi∩Yj│/│Xi│

=((1/8)+0)+(0+1/8)+((1/8)×(1/2)+(1/8)×(1/2))+((1/8)×(1/2)+(1/8)×(1/2))+(1/8+0)+(0+1/8)=6/8

SGF(b，D) = DP({b}→D)= ■■ │Zi∩Yj│/│U││Zi∩Yj│/│Zi│

=((1/8)×(1/2)+(1/8)×(1/2))+(1/8+0)+((2/8)×(2/3)+(1/8)×(1/3))+((2/8)×(2/2)+0)=■

所以SGF(a，D) > SGF(b，D)

對決策表1，其候選斷點集為：Ca={0.9，1.15，1.35，1.5，2.8}; Cb={0.75，1.5，2.5}

由上面的計算知SGF(b，D)

表1原始決策表 表2屬性b離散化后的決策表

■

同樣對屬性a的斷點Ca={0.9，1.15，1.35，1.5，2.8}進行判斷，得到的決策表為表3，最終得到的決策表為表4。

表3屬性a離散化后的決策表表4最終的決策表

■

4 結(jié)束語

提出的基于決策強度的離散化算法可在離散化數(shù)據(jù)的同時約簡冗余的屬性，而且保持決策表的一致性不變。數(shù)值離散化以后對屬性表的所有數(shù)據(jù)作屬性約簡和值約減操作，最終獲得簡化的決策表，決策表的每一條記錄就是一個決策規(guī)則。該算法易于理解，計算簡單。

參考文獻：

[1] Pawlak Z.Rough set theoretical aspects of reasoning about date[M].Poland:Warsaw，1991.

[2] 王國胤.Rough 集理論與知識獲取[M].西安:西安交通大學出版社，2001.

[3] 候利娟，王國胤，聶能，等.粗糙集理論中的離散化問題[J].計算機科學，2000，27(12):89-94.

[4] 林毓寧，冼太生，桂現(xiàn)才.基于條件信息量的決策表連續(xù)屬性離散化算法[J].洛陽師范學院學報，2006，25(2):14-16.

[5] 唐洪浪.基于決策強度的一種屬性約簡算法[J].湛江師范學院學報，2007，28(6):65-69.

[6] 王國胤，于洪，楊大春.基于條件信息熵的決策表約簡[J].計算機學報，2002，25(7):759-766.