On Method of Attribute Reduction Based on Heuristic Binary Strategy

DS=〈U，C∪D，V，f〉为决策系统的形式化表示，其中U为非空有限论域；C为条件属性集，D为决策属性集，C∩D=Ø；V=∪_a∈(C∪D)V_a为属性值域，V_a为属性a的值域；f：U×(C∪D)V为信息函数，f(x，a)为对象x∈U在属性a上的取值.

定义1^[6] 给定决策系统DS=〈U，C∪D，V，f〉，令C={a₁，…，a_m}，U={x₁，…，x_n}，分辨矩阵M是一个|U|×|U|的矩阵，矩阵中每一元素定义为

分辨矩阵满足对称性且对于1≤∀i≤n均有c_ii=Ø，因此可仅通过下三角(1≤j＜i≤n)元素来表示矩阵.为叙述方便，令M_DS为决策系统DS的分辨矩阵M中非空元素构成的集合，即M_DS={m_ij： m_ij≠Ø}.

定义2^[6] 给定决策系统DS=〈U，C∪D，V，f〉，M_DS={m_ij}≠Ø，其分辨函数定义为

其中，∨m_ij为m_ij中所有属性的析取式，∧{∨m_ij}为所有∨m_ij的合取式.后续描述中在不影响理解时，将F_DS(C)简写为F_DS.

定义3^[12]  定义a∈C关于属性集B⊆C的布尔映射函数为

分辨函数关于属性集B⊆C的布尔映射函数为ρ_B(F_DS(C))=∧{∨ρ_B(m_ij)：m_ij∈M_DS∧m_ij≠Ø}.

性质1^[12] 给定决策系统DS=〈U，C∪D，V，f〉， M_DS={m_ij}≠Ø，则ρ_C(F_DS(C))=1.

由定义3可知对分辨矩阵任意非空元素m_ij，∨m_ij关于属性集B⊆C的布尔映射函数为

对于∀m_ij∈M_DS∧m_ij≠Ø均有m_ij∩C≠Ø，故对于分辨矩阵中任意非空元素m_ij恒有ρ_C(∨m_ij)=1，因此分辨函数F_DS关于属性集C的布尔映射函数ρ_C(F_DS(C))=∧{ρ_C(∨m_ij)：m_ij∈M_DS∧m_ij≠Ø}=1.

定义4^[8]  给定决策系统DS=〈U，C∪D，V，f〉，R(R⊆C)关于D的可辨识关系定义为：DIS(R，D)={(x_i，x_j)∈U×U：f(x_i，R)≠f(x_j，R)∧f(x_i，D)≠f(x_j，D)∧(|f([x_i]_IND(R)，D)|=1∨|f([x_j]_IND(R)，D)|=1)}.其中[x_i]_IND(R)是不可分辨关系R下由对象x_i定义的等价类，定义为[x_i]_IND(R)={x：x∈U∧f(x，R)=f(x_i，R)}.

性质2 给定决策系统DS=〈U，C∪D，V，f〉，R⊆C，则DIS(R，D)⊆DIS(C，D).

证 针对∀(x_i，x_j)∈DIS(R，D)必有f(x_i，R)≠f(x_j，R)且f(x_i，D)≠f(x_j，D)且|f([x_i]_IND(R)，D)|=1∨|f([x_j]_IND(R)，D)|=1.由f(x_i，R)≠f(x_j，R)可推出f(x_j，C)≠f(x_j，C)；由R⊆C可得[x_i]_IND(C)⊆[x_i]_IND(R)，[x_j]_IND(C)⊆[x_j]_IND(R)，又|f([x_i]_IND(R)，D)|=1∨|f([x_j]_IND(R)，D)|=1，故有|f([x_i]_IND(C)，D)|=1∨|f([x_j]_IND(C)，D)|=1.因此针对∀(x_i，x_j)∈DIS(R，D)必有f(x_i，C)≠f(x_j，C)且f(x_i，D)≠f(x_j，D)且|f([x_i]_IND(C)，D)|=1∨|f([x_j]_IND(C)，D)|=1，即(x_i，x_j)∈DIS(C，D)，性质DIS(R，D)⊆DIS(C，D)得证.

定义5^[8] 对于决策系统DS=〈U，C∪D，V，f〉，给定目标概念对象集合X⊆U，X关于R(R⊆C)的近似精度定义为

其中，∪{[x]_IND(R)：[x]_IND(R)⊆X}是论域U中通过知识R判断确定属于集合X的元素构成的集合，记为正域POS_R(X)，显然有0≤$\partial_{R}$(X)≤1.近似精度反映了通过现有知识向目标概念能够逼近的程度，当$\partial_{R}$(X)=1时，X可通过已有知识被精确描述；当$\partial_{R}$(X) < 1时，X仅可通过已有知识被粗糙定义.

定义6^[8] 给定决策系统DS=〈U，C∪D，V，f〉，若R(R⊆C)满足：

1) $\partial_{R}$(D)=$\partial_{C}$(D)；

2) ∀a∈R，$\partial$_R-{a}(D)≠$\partial_{R}$(D)

则称R为条件属性集C关于决策属性集D的相对属性约简.相对属性约简的本质在于保持决策系统近似质量不发生改变.

定理1 给定决策系统DS=〈U，C∪D，V，f〉，R⊆C，DIS(R，D)=DIS(C，D)的充要条件是$\partial_{R}$(D)=$\partial_{C}$(D).

证明：

1) 证明：若DIS(R，D)=DIS(C，D)，则$\partial_{R}$(D)=$\partial_{C}$(D)，利用反证法.

假设$\partial_{R}$(D)≠$\partial_{C}$(D)，则$\exists $x_i∈U使得[x_i]_IND(C)⊆POS_C(D)但[x_i]_IND(R)$\nsubseteq$POS_C(D)，则$\exists $x_j∈[x_i]_IND(R)使得x_j∉[x_i]_IND(C)且f(x_i，D)≠f(x_j，D).由[x_i]_IND(C)⊆POS_C(D)可得|f([x_i]_IND(C)，D)|=1，由x_j∉[x_i]_IND(C)可得f(x_i，C)≠f(x_j，C)，因此有(f(x_i，C)≠f(x_j，C))∧(f(x_i，D)≠f(x_j，D))∧(|f([x_i]_IND(C)，D)|=1∨|f([x_j]_IND(C)，D)|=1)成立，即(x_i，x_j)∈DIS(C，D).由x_j∈[x_i]_IND(R)可得f(x_i，R)=f(x_j，R)，故(x_i，x_j)∉DIS(R，D). (x_i，x_j)∈DIS(C，D)但(x_i，x_j)∉DIS(R，D)，这与前提条件DIS(R，D)=DIS(C，D)矛盾，因此假设不成立，所以$\partial_{R}$(D)=$\partial_{C}$(D).

2) 证明：若$\partial_{R}$(D)=$\partial_{C}$(D)，则DIS(R，D)=DIS(C，D)，利用反证法.

假设DIS(R，D)≠DIS(C，D)，则由性质1可推出$\exists $x_i，x_j∈U使得(x_i，x_j)∈DIS(C，D)但(x_i，x_j)∉DIS(R，D).由(x_i，x_j)∈DIS(C，D)可知有f(x_i，C)≠f(x_j，C)且f(x_i，D)≠f(x_j，D)且|f([x_i]_IND(C)，D)|=1∨|f([x_j]_IND(C)，D)|=1成立，可推出x_i，x_j中至少一个属于POS_C(D)；由(x_i，x_j)∉DIS(R，D)可推出有f(x_i，R)=f(x_j，R)或者f(x_i，D)=f(x_j，D)或者|f([x_i]_IND(R)，D)|＞1∧|f([x_j]_IND(R)，D)|＞1成立.因为f(x_i，D)≠f(x_j，D)，所以只可能有f(x_i，R)=f(x_j，R)或者|f([x_i]_IND(R)，D)|>1∧|f([x_j]_IND(R)，D)|>1成立，由f(x_i，D)≠f(x_j，D)与f(x_i，R)=f(x_j，R)可推出x_i，x_j两对象均不属于POS_R(D)，由|f([x_i]_IND(R)，D)|＞1∧|f([x_j]_IND(R)，D)|＞1也可推出x_i，x_j两对象均不属于POS_R(D)，因此POS_R(D)≠POS_C(D)，因而有$\partial_{R}$(D)≠$\partial_{C}$(D)，与前提$\partial_{R}$(D)=$\partial_{C}$(D)相矛盾，因此假设不成立，所以DIS(R，D)=DIS(C，D).

根据定理1，可将相对约简定义转换为对应于可辨识关系的等价描述.给定决策系统DS=〈U，C∪D，V，f〉，若R(R⊆C)为C相对于D的属性约简当且仅当R满足：

1) DIS(R，D)=DIS(C，D)；

2) ∀a∈R，DIS(R-{a}，D)≠DIS(C，D).

因此，可依据系统的可辨识关系是否变化，作为R(R⊆C)是否为约简的判定标准.

定理2 给定决策系统DS=〈U，C∪D，V，f〉，M_DS={m_ij}≠Ø，R⊆C，则DIS(R，D)=DIS(C，D)当且仅当ρ_R(F_DS)=ρ_C(F_DS).

证明：

1) 证明：若DIS(R，D)=DIS(C，D)则ρ_R(F_DS)=ρ_C(F_DS).

对∀m_ij∈M_DS∧m_ij≠Ø，必存在U中对象x′_i∈[x_i]_IND(C)，x′_j∈[x_j]_IND(C)，使得(x′_i，x′_j)∈DIS(C，D)，此时m_ij={a：a∈C∧f(x_i，a)≠f(x_j，a)}={a：a∈C∧f(x′_i，a)≠f(x′_j，a)}.又已知DIS(R，D)=DIS(C，D)，故当(x′_i，x′_j)∈DIS(R，D)，则必$\exists $a∈R，f(x′_j，a)≠f(x′_j，a)成立，因而有R∩m_ij≠Ø故ρ_R(∨m_ij)=1.针对∀m_ij∈M_DS∧m_ij≠Ø均有ρ_R(∨m_ij)=1，因此ρ_R(F_DS)=∧{ρ_R(∨m_ij)：m_ij∈M_DS∧m_ij≠Ø}=1.又由性质2得ρ_C(F_DS(a₁，…a_m))=1，因此ρ_R(F_DS)=ρ_C(F_DS).

2) 证明：若ρ_R(F_DS)=ρ_C(F_DS)则DIS(R，D)=DIS(C，D).

先证DIS(C，D)⊆DIS(R，D).针对∀(x_i，x_j)∈DIS(C，D)，必存在m={a：a∈C∧f(x_i，a)≠f(x_j，a)}≠Ø使得m∈M_DS.由条件ρ_R(F_DS)=ρ_C(F_DS)与性质1可得ρ_R(F_DS)=1，因此对M_DS中任意非空元素m恒有ρ_R(∨m)=1，即R∩m≠Ø，因此有f(x_i，R)≠f(x_j，R).又由(x_i，x_j)∈DIS(C，D)可得f(x_i，D)≠f(x_j，D)且|f([x_i]_IND(C)，D)|=1∨|f([x_j]_IND(C)，D)|=1，故针对∀(x_i，x_j)∈DIS(C，D)均有f(x_i，R)≠f(x_j，R)且|f([x_i]_IND(C)，D)|=1∨|f([x_j]_IND(C)，D)|=1.

假设|f([x_i]_IND(R)，D)|＞1∧|f([x_j]_IND(R)，D)|＞1成立，由|f(；x_i]_IND(C)，D)|=1∨|f([x_j]_IND(C)，D)|=1可知x_i，x_j中至少一个属于POS_C(D)，可令x_i∈POS_C(D)(同理可令x_j∈POS_C(D)，证明过程与x_i∈POS_C(D)类似)，则$\exists $x_k∈U使得x_k∈[x_i]_IND(R)∧x_k∉[x_i]_IND(C)且f(x_i，D)≠f(x_k，D)，那么必$\exists $m′∈M_DS∧m′≠Ø其行对应x_i列对应[x_k]_IND(C)中一对象，使得m′={a：a∈C∧f(x_i，a)≠f(x_k，a)}≠Ø且R∩m′=Ø，则有ρ_R(∨m′)=0故ρ_R(f_DS)=0，与前提ρ_R(F_DS)=ρ_C(F_DS)=1矛盾，故|f([x_i]_IND(R)，D)|＞1∧|f([x_j]_IND(R)，D)|＞1不成立，即有|f([x_i]_IND(R)，D)|=1∨|f([x_j]_IND(R)，D)|=1成立.因此，针对∀(x_i，x_j)∈DIS(C，D)均有f(x_i，R)≠f(x_j，R)∧f(x_i，D)≠f(x_j，D)且|f([x_i]_IND(R)，D)|=1∨|f([x_j]_IND(R)，D)|=1成立，即(x_i，x_j)∈DIS(R，D)，故DIS(C，D)⊆DIS(R，D).

又由性质2有DIS(R，D)⊆DIS(C，D)，因此有DIS(R，D)=DIS(C，D).

综上所述，当M_DS={m_ij}≠Ø时，DIS(R，D)=DIS(C，D)的充分必要条件是ρ_R(F_DS)=ρ_C(F_DS)，即DIS(R，D)=DIS(C，D)当且仅当ρ_R(F_DS)=ρ_C(F_DS).

联立定理1、定理2可得，给定决策系统DS=〈U，C∪D，V，f〉，M_DS={m_ij}≠Ø，则R(R⊆C)为C相对于D的属性约简当且仅当R满足：①ρ_R(F_DS)=1；②∀a∈R，ρ_R-{a}(F_DS)=0.换而言之，若R是保持分辨函数值为真的极小条件属性集，则R为C相对于D的一个属性约简.

性质3 给定决策系统DS=〈U，C∪D，V，f〉，M_DS={m_ij}≠Ø，R⊆C，则ρ_R(F_DS)=1当且仅当对∀m_ij≠Ø均有R∩m_ij≠Ø.

证  若ρ_R(F_DS)=1，则对∀m_ij≠Ø均有ρ_R(∨m_ij)=1，即R∩m_ij≠Ø.若对∀m_ij≠Ø均有R∩m_ij≠Ø，则对∀m_ij≠Ø均有ρ_R(∨m_ij)=1，即ρ_R(f_DS)=1.因此，当M_DS={m_ij}≠Ø时，给定R⊆C，ρ_R(F_DS)=1的充要条件是对∀m_ij≠Ø均有R∩m_ij≠Ø.

根据性质3，可将相对约简定义转换为对应于M_DS的等价描述.给定决策系统DS=〈U，C∪D，V，f〉，M_DS={m_ij}≠Ø，则R(R⊆C)为C相对于D的属性约简当且仅当R满足：

1) ∀m_ij∈M_DS(m_ij≠Ø$\Rightarrow $R∩m_ij≠Ø)；

2) ∀a∈R，$\exists $m_ij∈M_DS(m_ij≠Ø∧(R－{a})∩m_ij=Ø).

定理2表明，约简对应使分辨函数映射值为真的极小属性集.本节进一步分析分辨集、分辨函数与约简的对应关系，给出相关的定理及证明，并在此基础上设计求取决策系统全体约简的有效算法.

定理3  令G_DS是将分辨函数F_DS运用命题逻辑吸收律和分配律等值变换后的极小析取范式(即析取范式中任意两项简单合取式之间不存在属性集包含关系)，那么存在h和X_i⊆C(1≤i≤h)使得G_DS=(∧X₁)∨…∨(∧X_h)，则决策系统DS的所有约简RED(DS)={X₁，…X_h}.

证 针对∀X_i∈{X₁，…，X_h}(1≤i≤h)，由布尔映射函数定义均有ρ_Xi(∧X_i)=1，因此ρ_Xi(G_DS)=1；因G_DS中任意2项简单合取式间不会存在属性集包含关系，即对∀X_i，X_j∈{X₁，…，X_h}(1≤i，j≤h，j≠i)均有X_j-X_i≠Ø，则对∀X_i，X_j∈{X₁，…X_h}(1≤i，j≤h)与∀a∈X_i均有X_j－(X_i－{a})≠Ø，那么ρ_Xi-{a}(∧X_j)=0，因此对∀a∈X_i均有ρ_Xi-{a}(G_DS)=0.又因G_DS是将分辨函数F_DS运用吸收律和分配律等值变换后的极小析取范式，根据命题逻辑可知对∀B⊆C均有ρ_B(F_DS)=ρ_B(G_DS)，因此可将上述性质描述为：对∀X_i∈{X₁，…，X_h}(1≤i≤h)均有ρ_Xi(F_DS)=1；对∀a∈X_i均有ρ_Xi-{a}(F_DS)=0.因此∀X_i∈{X₁，…，X_h}(1≤i≤h)均是一个约简，即{X₁，…，X_h}⊆RED(DS).

依据定理2，∀R∈RED(DS)均满足：ρ_R(F_DS)=1；∀a∈R，ρ_R－{a}(F_DS)=0.又因G_DS是将分辨函数F_DS运用吸收律和分配律等值变换后的极小析取范式，根据命题逻辑可知对∀B⊆C均有ρ_B(F_DS)=ρ_B(G_DS).因此∀R∈RED(DS)均满足：ρ_R(G_DS)=1；∀a∈R，ρ_R-{a}(G_DS)=0.由ρ_R(G_DS)=1可知至少存在某项X_i∈{X₁，…X_h}(1≤i≤h)使得R⊇X_i，假设存在2项以上则$\exists $X_i，X_j∈{X₁，…X_h}(1≤i≤h，1≤j≤h，i≠j)使得R⊇X_i∧R⊇X_j，又X_i与X_j互不包含，则R-X_i≠Ø那么必$\exists $a∈R使得ρ_R-{a}(∧X_i)=1即$\exists $a∈R(ρ_R-{a}(G_DS)=1)，与∀a∈R，ρ_R-{a}(D_DS)=0相矛盾，因此当前仅存在一项X_i∈{X₁，…，X_h}(1≤i≤h)使得R⊇X_i，故此时有ρ_R(G_DS)=ρ_R(∧X_i).又因为ρ_R(G_DS)=1且∀a∈R，ρ_R－{a}(G_DS)=0，故有ρ_R(∧X_i)=1且∀a∈R，ρ_R-{a}(∧X_i)=0，则必有R=X_i.因此针对∀R∈RED(DS)均存在且仅存在一项X_i∈{X₁，…，X_h}(1≤i≤h)使得R=X_i，即对∀R∈RED(DS)均有R∈{X₁，…，X_h}，即RED(DS)⊆{X₁，…，X_h}.

综上所述，若G_DS=(∧X₁)∨…∨(∧X_h)是将F_DS运用吸收律和分配律等值变换后的极小析取范式，则决策系统DS的所有约简RED(DS)={X₁，…，X_h}.

由定理3可知，求取所有约简问题可转化为将分辨函数F_DS转化为等价的极小析取范式G_DS，G_DS中每一析取项(极小析取范式中的每一简单合取式∧X_i(1≤i≤h))对应一个约简，G_DS中全体析取项对应决策系统全体约简.为生成分辨函数的极小析取范式，需在等价变换过程中运用命题逻辑吸收律和分配律.相应地，可基于布尔函数操作对求取所有约简集问题建模.

定义7  给定决策系统DS=〈U，C∪D，V，f〉，M_DS={m_ij}≠Ø，其分辨集€定义为M_DS中所有非空元素构成的集合，即分辨集€={m_ij：m_ij∈M_DS∧m_ij≠Ø}，分辨函数可表示为F_DS=F(€)=∧{∨€_k：€_k∈€}.

定义8 给定决策系统DS=〈U，C∪D，V，f〉，分辨集€={m_ij：m_ij∈M_DS∧m_ij≠Ø}，其极小分辨集定义为min(€)={€_k：€_k∈€∧((∀€_l∈€∧k≠l)→(€_l⊄€_k))}，即min(€)是€中删除所有超集元素后形成的集合(若某元素€_l⊃€_k(k≠l)，则€_l为超集元素).

若€_k⊆€_l则据命题逻辑吸收律可得(∨€_k)∧(∨€_l)=(∨€_k)，故有F(€)=F(€-{€_l}).通过多次使用吸收律，可将分辨集€转换为其极小分辨集，因而F_DS=F(€)=F(min(€)).如此，则可按如下步骤直接得到极小分辨集：①分辨集€初始值置空；②若分辨矩阵所有元素提取完毕则转⑤，否则提取分辨矩阵当前元素M(i，j)；③若€中存在某元素包含于M(i，j)转④，否则删除€中所有包含M(i，j)的元素，然后将M(i，j)加入€；④生成下一当前元素M(i，j)转③；⑤结束.操作结束，€即为极小分辨集.

直接生成极小分辨集流程遵循了合取范式的消解原理，因此与原分辨集在求取约简结果上是等价的，且最大限度减少了存储分辨矩阵的元素数目.

为实现基于分辨矩阵求取全体属性约简的启发式算法，以下先给出分辨集核、分辨集关于特定属性的排除集定义，再给出算法的实现原理及证明.

定义9  分辨集€的核定义为€中所有单属性元素构成的集合，即CORE(€)={€_k：€_k∈€_∧|€_k|=1}.

定理4  CORE(€)=∩RED(DS)，其中RED(DS)为决策系统DS全体约简.

证  ①对∀a∈CORE(€)可知单属性a对应分辨函数F_DS中的一个合取项，由性质3对∀R∈RED(DS)，R⊆C均有ρ_R(F_DS)=1，则必有ρ_R(a)=1即a∈R.若a∈CORE(€)，则对∀R∈RED(DS)均有a∈R，所以CORE(€)⊆∩RED(DS).

② 对∀a∈∩RED(DS)，令RED(DS)={X₁，…，X_h}，则a∈X_i(1≤i≤h).若决策系统DS仅存在一个约简则G_DS=∧X₁，a∈X₁则单属性a必对应F_DS中一合取项，即a∈€则必有a∈CORE(€)；若DS存在多个约简则可将G_DS转化为G_DS=(∧X₁)∨…∨(∧X_h)=a∧(∧(X₁－{a}))∨…∨(∧(X_h－{a}))，又因为G_DS是将合取范式F_DS等值变换后的极小析取范式，故单属性a必对应F_DS中一合取项，即单属性a∈€，故a∈CORE(€).因此对∀a∈∩RED(DS)均有a∈CORE(€)，即∩RED(DS)∀CORE(€).

综合①②可得CORE(€)=∩RED(DS).

定义10 给定分辨集€≠Ø，分辨集€关于属性a(a∈C)的排除集定义为：€^-(a)={€_k-{a}：(€_k∈€)∧((€_k-{a})≠Ø)}.

性质4 给定极小分辨集€≠Ø，a为€中任一非核属性，€′=€-{€_k：(€_k∈€)∧(€_k∩{a}≠Ø)}.若€′≠Ø则F(€)=(a∧F(€′))∨(F(min(€^-(a))))；若€′=Ø，则F(€)=(a)∨(F(min(€^-(a)))).

证明：

① 若€′≠Ø，令€={€₁，…，€_r，€_r+1，…，€_s}且非核属性a∈€_k(1≤k≤r)，a∉€_k(r+1≤k≤s)，则

② 若€′=Ø，令€={€₁，…，€_r}，则对∀€_k∈€，1≤k≤r均有非核属性a∈€_k，故

给定极小分辨集€≠Ø，若其子集€′≠Ø，则€′也是极小分辨集；€^-(a)不一定为极小分辨集，可将其转化为极小分辨集，且根据命题逻辑可知F(€^－(a))与F(min(€^-(a)))等值.对F(€′)与F(min(€^-(a)))递归运用同样分解过程，F(€)必能等价转化为析取范式，再应用命题逻辑吸收律可将其化为形如(∧X₁)∨…∨(∧X_h)的极小析取范式，依据定理3，{X₁，…，X_h}即为决策系统全体约简.

定理4说明CORE(€)包含于每一约简，性质4说明，将决策系统约简可分为2类：一类包含非核属性a；另一类不包含非核属性a，那么生成所有约简的整个过程对应由极小分辨集€递归构造一棵二叉树的过程：①根结点赋值为CORE(€)，若€中不存在非核属性该结点停止扩展，否则执行②与③；②选择非核属性a，左子树赋值为由分辨集{a}∪(€′-CORE(€))所构造的二叉树；③右子树赋值为由分辨集min(€^－(a)－CORE(€))构造的二叉树.一个包含属性a的约简对应左子树中某条从根结点到叶结点的路径，一个不包含属性a的约简对应右子树中某条从根结点到叶结点的路径，此即为本文基于极小分辨集构造约简树求取全体约简的二分策略；此外，在针对约简树中每一结点向下二分扩展时，以本结点所对应极小分辨集中属性的出现频度作为启发式信息，选取频度最高的非核属性a，可加快约简树的生成过程.基于启发式二分策略的完全约简获取算法具体描述见算法1.

算法1 基于启发式二分策略的完全约简获取算法

输入：非空极小分辨集€

输出：决策系统所有约简RED(€)

初始化：RED(€)=Ø(RED(€)为全局变量)

Void RED_HBS(€)

{cur_red=Ø；

if (€=NULL) return；

if ((|∀€_k∈€|=1)

  {cur_red=€；

  将cur_red以吸收方式加入RED(€)；

  }

else

{对€中每一非核属性计算SIG(b)；

  a=max{SIG(b)}；

  €′=€-{€_k：(€_k∈€)∧(€_k∩{a}≠Ø)}；

  €′=€′∪{a}；

   RED_HBS(€′)；

   €″=€^-(a)的极小分辨集；

   RED_HBS(€″)；

   }//end if

}//end RED_HBS

设极小分辨集为€={€₁，…，€_t}，按算法1生成的二叉树结点数为N.算法对每一内部结点，均要计算核属性集CORE(€)(时间复杂度为O(t))，计算所有非核属性b在€中的频度信息SIG(b，€)(时间复杂度不超过O(t·|C|)，选择a=max{SIG(b，€)}的属性a(时间复杂度为O(|C|))，计算€^-(a)的极小分辨集(时间复杂度不超过O(t²))，又由二叉树性质可得内部结点数为(N-1)/2，故算法对所有内部结点操作的时间复杂度不超过O(N·(t·|C|+t²))，一般情形下|C| << t，因此算法对内部结点操作的时间复杂度不超过O(N·t²)；对每个叶子结点均存在一条从根结点到该叶结点的路径，由二叉树特征可得叶子结点数为(N+1)/2，故算法1对所有叶子结点收集候选约简的时间复杂度不超过O(N·|C|)，将候选约简以吸收方式加入约简集的时间复杂度不超过O(N²).因此，整个算法时间复杂度不超过O(N·t²+N²).

文献[11]所提出的扩展法则本质上可归结为按广度优先遍历求解，必须获取约简树全体路径并执行逻辑吸收操作后才能得到全体解，而算法1按深度优先遍历以吸收方式加入当前候选约简cur_red(cur_red是否为约简取决于其是否被吸收)，有效地消除了部分非真实约简，因而其耗费存储空间要少于扩展法则.

为进一步验证本文算法的性能，选用UCI机器学习数据库中的若干数据集，CPU为Intel双核2.5 GHz，内存容量为4 G，操作系统为Windows 10，使用Visual Studio 2017实现了相关实验，实验结果见表 1-表 3.

表 1给出直接提取分辨矩阵元素得到分辨集与直接生成极小分辨集的实验数据对比.其中“元素数目”代表所生成分辨集中的所有元素的数目，“元素长度和”代表所有元素中包含的属性数目之和.实验数据表明，相对于提取分辨矩阵所有元素而言，直接生成极小分辨集大大减少了存储空间.

表 2针对算法1给出其与不运用启发式信息扩展结点的实验结果对比.其中“生成分辨集时间”表示获取极小分辨集的时间(单位：s)，“路径数”表示所构造约简树从根到叶结点的路径数目，“启发式扩展结点”表示使用属性重要度作为启发式信息选择分支属性，“非启发式扩展结点”表示不运用启发式信息而仅按照预先设置的顺序选择分支属性.数据集“zoo”，“ monks-1”，“ tic-tac-toe”与“kr-vs-kp”在是否运用启发式信息求取所有约简的时间上难以体现差别，均小于0.001 s，主要原因在于此4个数据集所构造约简树的路径数目太少且相差不大.对于数据集“soybean-small”与“mushroom”，是否运用启发式信息扩展结点构造约简树的路径数目相差较大，因此前者求取全体约简时间耗费不到后者的1/10.

表 3给出了运用算法1求取所有属性约简与利用文献[11]中算法(简称扩展法则)求取全体约简所耗费空间(单位：B)的实验对比数据.数据集“zoo”，“ monks-1”，“ tic-tac-toe”与“kr-vs-kp”在2种算法上的初始候选约简集与最终约简集相等，因此所耗费的存储空间无法体现出区别.数据集“soybean-small”与“mushroom”上的实验结果表明算法1所耗费的存储空间比扩展法则少，主要原因在于算法1采取深度优先方式每当探索到候选约简均以吸收方式加入，而扩展法则通过广度优先方式必须找到所有候选约简再吸收生成全体约简.

属性约简是粗糙集理论的重要研究内容，尤其是最小约简对于泛化能力具有重要意义.本文设计了一种构造约简树获取信息系统全体约简的有效算法：该算法提取分辨矩阵元素直接生成极小分辨集，根据启发式信息运用二分策略操作极小分辨集构造一棵约简树，该约简树从根结点到叶结点的每一条路径对应一个候选约简；在约简树的构造过程中采用深度优先遍历以吸收方式加入当前候选约简，当前候选约简是否为约简取决于其是否被吸收，有效地缩减了搜索空间和存储空间.该方法适用于满足任意约简准则的分辨矩阵，能够保证全体约简求解的完备性，理论分析与实验结果说明了算法的可行性与有效性.