數據挖掘約簡算法的應用

黑龍江 洪學銀

系統應用中，S=(U,C,D,V,f)每一元素表示決策規則。在決策規則中條件的屬性取值不是必要的。規則的約簡算法就是要約去規則中的不必要的屬性參數，計算規則的核和簡化。屬性約簡之后，對規則的冗余參數進行剔除。粗糙集理論的應用重點在約簡屬性和提取規則，但粗糙集知識中上下近似元素約簡出的規則不一定是最優化規則。因此，組建粗糙集知識與信息熵的關系圖，得出粗糙性理論的度量性表示，把信息熵理論和粗糙集理論相結合，提出規則集，得出信息熵約簡算法應用方法。

一、基本概念

2.條件熵：知識屬性集合Y(U|IND(Y)={Y1,Y2，…,Ym})相對于知識(屬性集合)

U/ind(X)={X1,X2,…,Xn}的條件熵：H(Y|X)為：

3.互信息：T=是一個決策系統表,R=CD,條件屬性集合是C,決策屬性集合是D=g0gggggg,且AC,對于任意屬性a∈A，a相對于決策D的重要性為:SGF(a,A,D)=H(D|A)-H(D|A∪{a})，是屬性重要性公式。若A=Φ，則SGF(a,A,D)=H(D)-H(D|{a})，是屬性a和決策D的互信息,記為I(a,D)。條件熵H(Q|R)量化在事件R出現的前提下，事件Q的不確定性?；バ畔(R;Q)表示包含在事件R中有關事件Q的信息。

二、方法描述

應用粗糙集知識約簡出的規則不一定是最簡規則，規則中會存在屬性值是不必要的。在決策表中添加屬性引起互信息的改變大小為該屬性重要性的度量，SGF(a,A,D)值越大，表示在已知A的條件下，屬性a對于決策D就越重要。論域上的不可分辨關系和信息熵知識可以對確定性規則進行約簡。

三、實例分析

假設論域 U={1，2，3，4，5，6，7，8}，屬性的集合 C={Solar energy,Volcanic activity,Residual CO2}，決策屬性D為Temperature，原始數據表見表1-1：

表1-1 一個天氣決策表

計算C對于D約簡過程，得出C0={solar，volcanic}是C對于D的約簡。

提取規則：

計算決策屬性同類相對于U/C0的下近似值，得出確定性的規則

計算表1-1中決策屬性的信息熵，約簡的屬性solar，volcanic的互信息是：

H（D）=-1*（130/270*log2(130/270)+140/270*log2(140/270)）=0.999

屬性Solar Energy的條件熵是：

H （D|C1）=-1*(110/270)*(110/110)*log2(110/110)-1*（20/270）*20/20*log2(20/20)-1*（140/270）*（140/140）*log2(140/140)=0

屬性Volcanic Activity的條件熵是：

H（D|C2）=-1*140/270*（120/140*log2(120/140)+20/140*log2(20/140)）-1*130/270*(120/130log2(120/130)+10/130*log2(10/130))=0.345

兩種屬性的互信息是：

Gain(Solar Energy)=0.999

Gain(Volcanic Activity)=0.654

因為屬性solar互信息較大，決策重要性高，Volcanic較小，得出要先在量化規則中去掉Volcanic屬性值，當去掉Volcanic,當Solar Energy為高時，規則中沒有沖突的規則，所以對應的規則2、規則3中屬性Solar Energy的值標是1；若Solar Energy為低，沒有產生沖突性規則，所以對應的規則4、規則5中屬性Solar Energy的值也是1；池Solar Energy為中，規則1，規則6與規則7產生沖突性規則，所以確定性規則1屬性Solar Energy值標記3。然后按照約簡方法進行計算，簡化得出確定性規則集是：

四、小結

通過研究基于應用的粗糙集知識和信息論結合的約簡算法，將信息論實例應用在決策信息規則約簡算法中，規劃出信息熵與知識的關系結構，得到基于應用的信息熵約簡算法，通過實例應用，約簡算法得出合理的最優化的約簡規則，更有效地應用到數據統計中。

[1]童舟，羅可.基于Rough Set帶結論域的關聯規則挖掘[J].計算機工程與應用，2006，42.

[2]Pawlak Z.Rough sets[J].International Journal of Computer and Information Science，1982，11(5)：341～356.