一種新的基于連續屬性離散化的屬性約簡方法
2009-01-01 00:00:00胡德敏馮科峰
計算機應用研究 2009年1期
(上海理工大學計算機與電氣學院， 上海 200093)
摘 要：通過將連續屬性離散化和屬性約簡結合起來，首先對連續型的屬性列進行離散化，得到新的決策表；然后再對新的決策表作屬性約簡，解決了屬性約簡過程中由于不考慮連續屬性而無法求出準確約簡屬性的問題。最后通過具體案例表明了該方法具有較好的實用性、有效性，可以很好地應用在含有大量連續屬性的數據挖掘項目中。
關鍵詞：連續屬性； 離散化； 屬性約簡； 分辨矩陣
中圖分類號：TP182 文獻標志碼：A
文章編號：10013695(2009)01006402
One method of new attribute reduction
based on discretization of continuous attributes
HU Demin， FENG Kefeng
(College of Computer Electric， University of Shanghai for Science Technology， Shanghai 200093， China)
Abstract:Through combining the discretization algorithm of continuous attributes with attribute reduction algorithm， this paper firstly did a discretization on continuous attributes columns， and got a new decisionmaking table. Then did attribute reduction on it， dealt with the problem of getting inaccurate reduction attributes on account of thinking about notcontinuous attributes during the process of attribute reduction. Finally an illustrated example shows that the way has preferable practicality and availability，can commendably apply to data mining project which contains plentiful continuous attributes.
Key words：continuous attribute; discretization; attribute reduction; differentiation matrix
粗集理論[1]是由波蘭華沙理工大學Z.Pawlak教授等人在1982年提出的，它主要研究不完整數據、不精確知識的表達、學習、歸納等方法。這一理論從新的視角出發對知識進行了定義，它把知識看做是關于論域的劃分，并引入代數學中的等價關系來討論知識。它為智能信息處理提供了有效的處理技術，目前已經在數據挖掘、機器學習、專家系統、故障診斷、系統控制等領域發揮出越來越重要的作用。決策系統屬性約簡是粗糙集理論最重要的應用。本文介紹了一種基于連續屬性離散化的屬性約簡方法，首先根據信息熵[1，2]和相對信息熵[3]的定義求出每個連續屬性的重要性；然后按屬性重要性由小到大的順序進行離散化，找出所有連續屬性的斷點集，生成新的決策表；最后在新的決策表上使用基于分辨矩陣[4，5]和屬性重要性的方法進行屬性約簡。
1 概念描述
設決策表T=(U，A，V， f)。其中：U表示對象的非空有限集合，稱為域;A=C∪D，C∩D=，C稱為條件屬性，D稱為決策屬性集; a∈A，V=∪Va， Va是屬性值域。其分辨矩陣是一個對稱的｜U｜×｜U｜矩陣，矩陣的每一項cij定義為：如果 xi(d)≠xj(d)， cij={a∈A｜xi(a)≠xj(a)}；否則cij=。若K1=(U，P)和K2=(U，Q)是關于U的兩個知識庫，U/ IND(P)={X1，X2，…，Xn}，U/ IND(Q)={Y1，Y2，…，Ym}，知識(屬性集合) Q 相對于知識(屬性集合)P的相對熵E(Q｜P)[3]定義為
E(Q｜P)=∑ni=1∑mj=1(｜Xi∩Yj｜/ ｜U｜） (｜Ycj-Xci｜/｜U｜）=
∑ni=1∑mj=1(｜Xi∩Yj｜/｜U｜) [(｜Xi｜-｜Xi∩Yj｜)/｜U｜]
若BC ，則對任意屬性a∈{C-B}的相對于決策屬性D的重要性SGF(a，B，D)定義為:SGF(a，B，D)=E(D｜B)-E(D｜B∪{a})。當B=時，簡記為SGF(a，D)=E(D)-E(D｜{a})=E(D;a)，即為a與D的互信息。
2 屬性約簡方法
2.1 連續屬性離散化
下面結合表1所示的原始決策表數據介紹連續屬性離散化處理方法。其中：a、b、c、d、e、f、g為條件屬性且為連續屬性；D為決策屬性。
a）求屬性集的等價關系，如U/{D}={{1，3，5，7 }，{2，4，6，8，9，10}}，U/{a}={{1，3，6，10}，{7，8，9}，{2，4，5 }}，U/{b}={{1，3，5，9}，{6，7，10}，{2，4，8}}。類似可求出其他屬性列的等價關系。
b)根據定義求出決策屬性信息熵和條件屬性相對信息熵，即E(D)=90/100，E(D/a)=16/100。同理可求得E(D/b)，E(D/c)，E(D/d)，E(D/e)，E(D/f)，E(D/g)。
c)根據定義求條件屬性的重要性，即可求出SGF(a，D)=74/100。同理可求SGF(b，D)、SGF(c，D)、SGF(d，D)、SGF(e，D)、SGF(f，D)、SGF(g，D)。
d)根據c)求出的屬性重要性，按順序對屬性離散化。由c）計算結果可知先對g列離散化，方法如下：先將g列由小到大排列即0.40.71，求出中位值，組成斷點集{0.55，0.85}。優化斷點集：先看0.55，0.55在0.4和0.7之間，則將小的數變成大的數，即將原列中的0.4變成0.7，然后判斷是否沖突。若D列值也相同則說明不沖突，把0.4改成0.7，將0.55從優化斷點集中排出；若D不同，則說明沖突，0.4不能改成0.7，將 0.55加入到優化斷點集中。最后求出g斷點集為{0.55}。同理可求出其他列的斷點集，即求得d列斷點集{0.7}，a列斷點集{0.2}，c列斷點集{0.5}，e列斷點集{0.6}，b列斷點集{0.65}，f列斷點集{0.8}。
2.2 最小屬性約簡
經離散化后的決策表如表2所示。
a)初始化分辨矩陣及最小約簡屬性集，令M(Ω)=，coreη(Ω)=，生成一個｜U｜×｜U｜的空屬性集矩陣，｜U｜為決策表中案例的個數。這里｜U｜=10。
b)生成分辨矩陣
private object[][] constructDifferMatrix(object decisionTable[][]);
根據分辨矩陣的定義生成mij，mij為分辨矩陣的元素。
c)求核
/* 求約簡屬性 */
private map findReductionAttributes(object decisionTable[][]，String Matrix[][]);
若｜mij｜=1將mij加入coreη(Ω)，其中mij為分辨矩陣的元素(i，j=1，…，10)。
d)將含有coreη(Ω)中元素的矩陣元素置空。
/* 使矩陣中含有指定約簡屬性的元素置為空*/
private string[][] clearElementsFromDifferMatrix(string matrix[][]，string reductionAttribute);
e)求得矩陣中出現頻率最高的屬性q，并將含q的矩陣元素置空。
/* 計算屬性出現頻率 */
private map calFrequencyOfAttribute(object decisionTable[][]，string Matrix[][]);
f)若M(Ω)≠則轉到e);否則結束。
最后求出的最小約簡屬性集為{a， b， c， g}，再結合新的決策表可以得出所有的決策規則。
3 結束語
屬性約簡可以在保證決策系統決策能力不變的條件下，刪除不相關或冗余的屬性。但基于經典粗糙集理論的屬性約簡卻不能直接應用于大部分實際系統。因為經典的粗糙集理論的不可分關系是等價關系，只適用于屬性值域為離散值的情況，而實際決策系統屬性的值域往往既有離散的也有連續的。本文介紹的屬性約簡方法具有很好的通用性，并且可以挖掘出較準確、可靠的決策規則。
參考文獻：
［1］王國胤.Rough集理論與知識獲取[M].西安:西安交通大學出版社，2001:1226.
[2]王國胤，于洪，楊大春.基于條件信息熵的決策表約簡[J].計算機學報，2002，25(7):759766.
[3]胡逢彬， 桂現才.基于相對熵的決策表連續屬性離散化算法[J].計算機與信息技術， 2006（4）：3941.
[4]程玉勝，張佑生，江效堯.基于改進區分表的核屬性約簡算法[J].計算機仿真，2007，24(7):9597.
[5]WANG Jue， WANG Ju. Reduction algorithm based on discernibility matrix the ordered attributes method[J].Journal of Computer Science Technology，2001，16(6):489504．
[6]謝宏， 程浩忠， 牛東曉.基于信息熵的粗糙集連續屬性離散化算法[J].計算機學報，2005，28(9):15701574.
[7]張文修，梁怡，吳偉志．信息系統與知識發現[M]. 北京:科學出版社，2003.
[8]AGRAWAL R，SRIKANT R．Fast algorithms for mining association rules in large databases[C]//Proc of the 20th International Conference on Very Large Data Bases. San Francisco:Morgan Kaufmann Publishers， 1994:487499.
