熵及條件熵的相關定理及其證明

1、熵及條件熵的相關定理及其證明設出屬性集合P和D = d 導出的對論域U（IU 1=疽的劃分分別為U I IND（P）= x ,X，X 和U IND（d）=&,Y ,.Y ，則有如下定理成立：12 n12 n定理 3.1臨H（D I P）= H（D P）= H（P）。定理3.2設U是一個論域，P, Q是U上的兩個屬性集合。若UIND（Q）= UIND（P）則 H（Q）= H（P）（逆并不成立）。定理3.3設U是一個論域，P, Q是U上的兩個屬性集合，且P c Q，若 H（Q ）= H（P ），則 UIND（Q ）= UIND（P ）。定理3.4設U是一個論域，P是U上的一個屬性集合，P中的一個屬

2、性r是 不必要的，其充分必要條件為HirP-匕=0。推論3.1 P中的一個屬性r是必要的必要條件為H（rP - 40。定理3.5設U是一個論域，P是U上的一個屬性集合，Q是P的一個約簡的 充分必要條件為H（Q）= H（P），且對任意的q e Q都有H（qQ - q0。由定理3.3、定理3.4和定理3.5可知，對于屬性約簡而言，信息嫡表示形 式與代數(shù)表示形式是等價的?？梢詮男畔⒌盏慕嵌葋硌芯繉傩约s簡問題，但上述 定理還僅僅是針對一般信息表的約簡問題（絕對約簡）而言的。對于決策表的相 對約簡問題，文獻11證明了如下定理。定理3.6設U是一個論域，P是U上的一個屬性集合，d為決策屬性，且論 域U是在

3、P上相對于 d 一致的，則P中的一個屬性r是P相對于決策屬性d不 必要的（多余的），其充分必要條件為HGdI P）= HGdI P- 。證明：首先令U I IND（P）=X ,X，X ，U I IND（d）= Y,Y ,.Y 。因為論12 n12 m域U是在P上相對于 d 一致的，即POSGd=U， 所以u I inDp）是 U I IND（d的細分，有U I IND（P +（/=U I IND（P）= kX2,.X ，H(d| P)=p(X P， I X )log P(Y I X )= 0j=1j=1必要性：假設屬性,是P相對于決策屬性d不必要的，則 POS &=POSp&=U，所以 U I

4、 IN* -#)是 U I IND(d)的細分。令 U I IND(P b+d=U I IND(P b=Z,Z2.,Z則H (d )I P r=SP(Z )pY I Z logpY I Z )= 0 故 j=1j=1H(dI P)= H(dI P-r)。充分性：假設 POS (d)o POSp(d)令 U I IND(P r)= Z,Z2 .,Z J,則至少存在Z (Z1 1 g U I IND(P b)，. J. g U I IND(d )和 Y.2 Y.2 g U I IND(d )Y.Y.2使得彳Pl Y 0且彳Pl Y.2。0。因此H(dI P t)= p(Z )pY. I Z tog

5、Wr I X U0j=1j=1H (d I P r)= H (d I P )= 0相矛盾。故假設POS (do U不成立，貝【有 POSp (d=U = POSp(d)成立。根據(jù)相對約簡的定義知，屬性r是P相對于決 策屬性d不必要的。定理3.7扇設U是一個論域，P是U上的一個條件屬性集合，d為決策屬性， 且論域U是在P上相對于由一致的。則P是相對于決策屬性d獨立的，其充分 必要條件為對于P中任意屬性r都有H(dI P)衛(wèi)H(dI P-匕成立。定理3.8成設U是一個論域，P是U上的一個條件屬性集合，d為決策屬性， 且論域U是在P上相對于由一致的。則Q u P是P相對于決策屬性d的一個約 簡的充分必要條件為H(dI Q)= H(dI P)，且Q是相對于決策屬性d獨立的。為了找出某些屬性或屬性集合的重要性，需要從屬性集合中去掉一些屬性， 再來考察沒有該屬性后分類會發(fā)生什么變化。若去掉該屬性分類情況改變較大， 說明該屬性重要性高，反之重要性低。可以想見，屬性的重要性可以用