近似最優的粗糙集連續屬性離散化斷點選擇方法＊

田樹新 吳曉平 王紅霞 張 麗

（海軍工程大學電子工程學院1） 武漢 430033）

（91829部隊2） 大連 116041） （海軍工程大學圖書館3） 武漢 430033）

0 引 言

粗糙集理論是由波蘭理工大學的Z.Pawlak教授于20世紀80年代提出的一種新的處理模糊和不確定性知識的數學工具.目前，在機器學習、決策分析、模式識別與數據挖掘、故障診斷等領域粗糙集理論得到了廣泛的應用.但是在大量的決策問題中，決策信息系統中的屬性值往往是連續的，而粗糙集方法只能處理離散屬性值.為了能夠從這些含有連續屬性的數據庫中取得好的數據樣本，得到簡潔且有效的規則，常常需要對連續屬性進行離散化.離散化結果將會減小系統的存儲空間的實際需求，加快后繼數據挖掘和機器學習算法的運行速度，減小后繼算法的空間開銷，提高分類精度.然而，連續屬性的最優離散化是一個NP完全問題［1］，采用不同的離散化方法，結果也往往存在差異.

在離散化的應用和研究中，貪心及其改進算法、基于屬性重要性、基于信息熵和基于聚類的離散化方法是四類常用的方法［2］.H.S.Nguyen等人提出了一種連續屬性離散化的貪心算法，并在此基礎上出現了一些改進算法，這類算法考慮了屬性間的互補性和相關性，能夠在不分明關系保持不變的條件下得到斷點數較少的結果斷點集，但是計算代價較大，時間復雜度為n3×k；基于屬性重要性的離散化算法首先計算條件屬性的重要性，然后根據屬性重要性由小到大對條件屬性進行排列，并依次求每個條件屬性的斷點，這類算法往往會產生過多的斷點，時間復雜度為n2×k；基于信息熵的離散化算法是從條件屬性的候選斷點中選擇結果斷點，通過逐步挑選信息熵最小的候選斷點，根據屬性值大于或小于斷點值把所有等價類劃分為兩部分，當達到某種終止標準時，停止挑選候選斷點.由于在計算信息熵時需要對數據集的對象按照決策值分類，屬性集決策值分類多少，直接影響算法的計算代價，時間復雜度為n3×k.基于聚類的離散化算法分為整體離散化和單個屬性離散化，這類算法不需要設置參數，得到的斷點集也較好，但是算法的計算代價較高，時間復雜度（n×k）2.

文獻［3］在保證信息系統分辨關系的前提下，采用基數最小的斷點集合對系統進行的離散化就是基于粗糙集理論的最優離散化.從這個定義不難發現，對一個給定的信息系統，存在一種或多種最優的離散化結果.由于已經證明連續屬性的最優離散化問題是一個NP完全問題，因此本文試圖獲得近似最優的離散化結果.

1 相關概念與離散化問題描述

1.1 相關基本概念

粗糙集理論是以不可分辨關系劃分所研究論域的知識，形成知識表達系統，利用上、下近似集逼近描述對象，通過知識約簡，從而獲得最簡知識，下面介紹其基本概念.

定義1 一個信息系統定義為一個如下四元組S＝（U，R，V，F）.式中：U＝｛x1，x2，…，xn｝為對象集，即論域；R為屬性集合，若屬性集可分為條件屬性集C和決策屬性集D，即有R＝C∪D，且C∩D＝?，則該信息系統稱為一個決策系統或決策表是屬性值的集合，Vr表示屬性r∈R的屬性值范圍；F∶U×R→V是一個信息函數，它指定U中每一個樣本x的屬性值.

定義3 對于決策表S＝（U，C∪D，V，F）如果?x1，x2∈U，使得x2∈［x1］C而x?2［x1］D則稱決策表S是不相容的，否則稱決策表是相容的.

定義4 條件信息熵［4］Hc（｛d｝｜C）

式中：U／IND（｛d｝）＝｛Y1，Y2，…，Ym｝，Yj稱為決策類，U／IND（｛C｝）＝｛X1，X2，…，Xn｝）.條件信息熵能有效地度量條件向量的決策值分布情況.

1.2 離散化問題描述

決策表S＝（U，C∪D，V，F）.式中：C 為條件屬性集D 為決策屬性集.條件屬性a的值域Va上的一個斷點可以記為（a，c），其中a∈R，c為實數集.在值域Va＝［la，ra］上的任意斷點集（又稱斷點區間）｛），），…，（a，）｝定義了Va上的一個分類Pa，pa＝，…，

離散化本質上可歸結為利用選取的斷點來對條件屬性構成的空間進行劃分的問題，把這個n（n為條件屬性的個數）維空間劃分成有限區域，使得每個區域中的 的決策值相同.假設某個屬性有m個屬性值，則在此屬性上就有m－1個斷點可取，隨著屬性個數的增加，可取的斷點數將隨著屬性值的個數呈幾何增長.選取斷點的過程也是合并屬性值的過程，通過合并屬性值，減少屬性值的個數，減少問題的復雜度，這也有利于提高知識獲取過程中所得到的規則知識的適應度.根據選取斷點的過程是從包含所有斷點的斷點集中逐步刪除不必要的斷點得到離散化結果，還是一開始設斷點集為空集，逐步增加候選斷點得到離散化結果，可以把離散化過程分為“逐步刪除斷點”和“逐步增加斷點”的離散化算法.

等距離劃分算法、等頻率劃分算法、布爾邏輯和粗糙集理論相結合的離散化算法及其相應的改進算法、基于屬性重要性的離散化算法、基于信息熵的離散化算法［5－7］和基于聚類的離散化算法［8］等都屬于“逐步刪除斷點”的離散化算法；NaiveS－caler算法等屬于“逐步增加斷點”的離散化算法［9］.

對于離散化方法沒有統一的衡量標準，本文主要遵循的如下原則：（1）離散化后屬性的結果盡可能地簡單，即離散化后的斷點區間盡可能少；（2）離散化處理應該盡可能保證經過離散化處理后得到的數據集的一致性與原始數據集的一致性接近.

2 近似最優的離散化算法

近似最優的離散化方法是選取較少的斷點來劃分條件屬性構成的空間，首先選擇重要性程度最高的條件屬性，根據啟發式規則逐步增加斷點，直到斷點劃分的區間相容度一致，最后合并具有相同決策值的相鄰區間，刪除多余斷點.為了能夠劃有效分決策表，可能需要選用幾個相對重要的條件屬性依次進行再劃分.

算法步驟.

符號標記 CUT為選取的斷點的集合；L為實例被斷點集合CUT所劃分成的等價類的集合；H為決策表信息熵.

步驟1 比較條件屬性重要性，首先對最重要的屬性（記為條件屬性a）進行劃分.

步驟2 條件屬性a的屬性值按遞增順序排列為La＝＜…＜＝Ra.

步驟3 根據第二步排序的結果選取斷點的啟發式規則：

步驟3.1 若每個屬性值均不相同，則取中間點為第一個斷點；

步驟3.2 若有部分屬性值相同，則按照第二步排序依次計算每個取值出現的頻率，記為，當第j個屬性值的頻率與其他頻率的關系滿足

時，則按照下面的規則增加斷點；

步驟4 增加斷點直到決策表相容.

步驟5 檢查相鄰2個斷點對應的熵值和決策值是否相同，若相同則刪除一個斷點，2個區間合并為一個區間，更新斷點集CUT.

步驟6 若同一區間對應的決策表對應的決策值不同，則選取次重要的條件屬性，轉到步驟2，依次類推，直到根據需求，決策表能夠劃分.算法結束.

分析 設X?U，其實例個數記為｜X｜，其中決策屬性為j（j＝1，2，…，r（d））的實例個數為kj，定義此子集的信息熵為

一般有H（X）≥0.信息熵H（X）越小，說明集合X中個別決策屬性值占主導地位，因此混亂程度越小，特別有當且僅當X中實例的決策屬性值都相同時H（X）＝0.文中選用的啟發式規則保證了此離散化算法不改變決策表的相容度.與基于信息熵的離散化方法［6］結果趨于一致.

文獻［6］中候選斷點為

并計算每個候選斷點劃分兩個區間的信息熵，它雖然考慮了粗集理論的相容度，但是候選斷點非常多，需要大量的信息熵的計算，計算復雜度比較高（計算復雜度為nk2m2，n為論域元素個數，k為屬性個數，m為條件屬性取值平均個數）.本文在最壞情況下，即每個條件屬性取值均不相同的情況下，計算復雜度nk2m2；當屬性值出現的頻率比較高或者樣本數比較多時，計算復雜度將遠遠小于nk2m3.

3 實驗結果

實驗1 選擇UCI數據庫中的“Iris Plants Database”數據來對所述方法進行驗證分析.數據庫中的樣本數有150個，條件屬性4個，決策屬性1個，決策分類為3個.條件屬性4的屬性值排序及屬性值出現的頻率如表1.

表1 屬性值、出現頻率及斷點插入次序之間的關系

表1中第一行和第三行的數據是根據算法步驟3.2中“第j個屬性值的頻率與其他頻率的關系”計算獲得，對于“Iris Plants Database”中斷點數只要簡單的排序和頻率關系計算就能獲得與文獻［2，6，7］相同的斷點數，但是計算量遠遠小于文獻［2，6，7］的計算量.

實驗2 選取基于屬性重要性算法的離散化方法，基于信息熵的離散化方法，和本文的算法進行性能分析比較.實驗的數據是從UCI機器學習數據中選取的3個只包含連續屬性的數據集，分別是Iris，Wine，Heart.實驗過程為：先將數據集中的2／3數據作為訓練樣本，其他的1／3數據作為測試樣本；再對訓練樣本進行離散化，得到斷點集和離散化后的訓練樣本.最后用訓練樣本的斷點集對測試樣本進行測試.3種算法實驗結果如表2.

表2 三種算法實驗結果

分析：本文算法選用的條件屬性比較多，同時在選條件屬性時，應用了數據集的領域知識，所以相對其他算法，有較高的識別率和較低的誤識率.

4 結 論

本文所提算法是以基于信息熵的算法為基礎，選用有效的啟發式規則，為尋求最少斷點數的離散化方法提供依據.對某個重要屬性條件先進行離散化，當熵降變化不大時，在此基礎上再選用次重要的屬性條件進行離散化，以保證確定恰當的區間數使得離散效果最好.

［1］Nguyen H S，Skowron A.Quantization of real values attributes：rough set and boolean reasoning approach［C］／／Proc.of the Second Joint Annual Conference on Information Sciences，Wrightsville Beach，North Carolina，Sept 28 －Oct 1，1995：34－37.

［2］劉業政，焦 寧，姜元春.連續屬性離散化算法比較研究［J］.計算機應用研究，2007，24（9）：28－30.

［3］趙 軍，王國胤，吳中福.基于粗集理論的數據離散化新算法［J］.重慶大學學報：自然科學版，2002，25（3）：18－21.

［4］王立宏，孫立民，孟佳娜.數值離散化中粒度熵與分類精度的相關性［J］.重慶大學學報，2008，31（1）：57－60.

［5］沈永紅，王發興.基于信息熵的粗糙集屬性離散化方法及應用［J］.計算機工程與應用，2008，44（5）：221－224.

［6］謝 宏，程浩忠，牛東曉.基于信息熵的粗糙集連續屬性離散化算法［J］.計算機學報，2005，28（9）：1 570－1 574.

［7］李春貴，王 萌，原慶能.基于啟發式信息熵的粗集數值屬性離散化算法［J］.廣西科學院學報，2007，23（4）：235－237.

［8］苗奪謙.Rough Set理論中連續屬性的離散化方法［J］.自動化學報，2001，27（3）：296－302.

［9］侯利娟，王國胤，聶 能.粗糙集理論中的離散化問題［J］.計算機科學，2000，27（12）：89－94.