0 引言

粗糙集理论是20世纪80年代提出的一种研究不完整、不确定知识和数据的表达、学习、归纳的理论方法^[1].由于粗糙集理论无需提供问题所需处理的数据集合以外的任何先验信息，可充分体现数据的客观性.因此，粗糙集理论被广泛应用于数据挖掘、模式识别、人工智能等领域^[2-3].随着现实世界中大量应用数据在结构和形式上日益复杂化和多样化，基于划分和等价关系的经典粗糙集模型已经很难满足大量现实问题的实际需要，于是有些学者将论域的划分扩展为覆盖，将等价关系扩展为非等价关系，提出了一些新的粗糙集模型.

粗糙集利用信息粒对数据集合的近似，描述对象之间的不确定关系.而信息粒化过程在很大程度上取决于对象之间的关系，既可以采用基于等价关系、相似关系、邻域关系的方法对信息进行粒化，也可以利用聚类分析的方法对信息进行粒化，由聚类分析得到的相似类可视为信息粒.在聚类分析的粒化方面，文献[4]提出了一种基于数据聚类的信息粒化方法，文献[5]提出了基于聚类的数值数据信息粒化方法.因此，可以利用聚类分析的粒化结果与粗糙集理论相结合进行知识约简.

属性约简是一种删除不相关和冗余属性的降维方法.基于信息熵、正域、可辨识矩阵、决策成本和知识粒度等已提出了许多启发式属性约简算法^[6]，文献[7-8]分别提出了基于近似决策熵、强化正域的属性约简方法，文献[9]提出了一种最小测试代价约简的改进算法，文献[10]提出了基于贴近度的协调序决策系统属性约简算法，文献[11]提出了基于α信息熵的模糊粗糙属性约简方法.然而这些方法都把对象平等对待，但是现实生活中对象的权重往往都不相同.文献[12]提出了基于代价敏感的对象权重确定方法，并将该权重用于粗糙集的约简之中，但是该权重确定方法过分依赖专家，使得权重的确定受到较大的主观因素的影响.本文结合粗糙集理论与聚类分析的方法，给出了一种新的对象权重确定方法与加权熵的定义方式，并提出一种相容关系下的属性约简算法.

1 预备知识

首先，在给出新的约简算法之前先回顾一下关于粗糙集和熵的相关知识和已有结论.

定义1^[2]  设S=(U, A=C∪D, V, f)是一个信息系统，U为非空有限论域，C为条件属性集，D为决策属性集. $\bigcup\limits_{a \in A} {{V_a}} $为属性值的集合，f:U×A→V为信息函数，表示U中每个对象x的属性值.

(1) 对于每个属性子集B⊆A，等价关系R_B={(x, y)(x, y)∈U², ∀b∈B, f(x, b)=f(y, b)}；由R_B生成的等价类记为[x]_RB={y(x, y)∈R_B}. ${R_B} = \bigcap\limits_{b \in B} {{R_b}} $构成论域U的一个划分，记作U/R_B，简记为U/B；

(2) 设R为U上的等价关系，[x]_R为U上的由R生成的等价类，X⊆U是U上的子集，记R(X)={x∈U|[x]_R⊆X}，R(X)={x∈U|[x]_R∩X≠∅}，则称R(X)为X的下近似，R(X)为X的上近似.若R(X)≠R(X)，则称X是R粗糙集，否则称X为R精确集.

信息熵是粗糙集的一种不确定性度量，度量了信息系统提供的平均信息量的大小.经典粗糙集中信息熵和条件信息熵的定义如下.

定义2^[13]  设S=(U，C∪D，V，f)是一个信息系统，U为非空有限论域，C为条件属性集，D为决策属性集.P为U上的概率分布，B⊆C∪U，令U/B={X₁, X₂, …, X_n}，P(X_i)=|X_i|/|U|，|·|表示集合中包含元素的个数，则U/B的信息熵$ H\left( B \right) =-\sum\limits_{i = 1}^n {P\left( {{X_i}} \right){{\log }_2}P\left( {{X_i}} \right)} $.设Ψ={Z₁, Z₂, …, Z_n}，Φ={Y₁, Y₂, …, Y_m}是U上的两个划分，则Φ和Ψ下的条件信息熵$H\left( {\mathit{\Phi} /\mathit{\Psi} } \right) =-\sum\limits_{i = 1}^n {P\left( {{Z_i}} \right)} \sum\limits_{j = 1}^m {P\left( {{Y_j}/{Z_i}} \right){{\log }_2}P\left( {{Y_j}|{Z_i}} \right)} $，其中P(Y_j|Z_i)=|Z_i|∩|Y_j|/|U|.

条件信息熵度量了两个属性集之间的依赖程度，即表示知识Φ从知识Ψ中所获得的信息量.

定义3^[14]  设M=(a₁, a₂, …, a_n)，N=(b₁, b₂, …, b_n)表示两个n维向量，0表示零向量，$\left\| \mathit{\boldsymbol{M}} \right\| = \sqrt {\sum\limits_{i = 1}^n {{{\left( {{a_i}} \right)}^2}} } $，$\left\| \mathit{\boldsymbol{N}} \right\| = \sqrt {\sum\limits_{i = 1}^n {{{\left( {{b_i}} \right)}^2}} } $表示向量M和N的模(二范数)，则向量M与N的余弦相似度定义为

$ \cos \left( {\mathit{\boldsymbol{M}}, \mathit{\boldsymbol{N}}} \right) = \\ \begin{align} \left\{ \begin{array}{l} 0, \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;&\mathit{\boldsymbol{M}} = {\bf{0}}或\mathit{\boldsymbol{N}} = {\bf{0}}, 但\mathit{\boldsymbol{M}} \ne \mathit{\boldsymbol{N}}, \\ \left( {\mathit{\boldsymbol{M}}, \mathit{\boldsymbol{N}}} \right)/\left( {\left\| \mathit{\boldsymbol{M}} \right\| \times \left\| \mathit{\boldsymbol{N}} \right\|} \right) = \sum\limits_{i = 1}^n {\left( {{a_i} \times {b_i}} \right)/\left( {\sqrt {\sum\limits_{i = 1}^n {{{\left( {{a_i}} \right)}^2}} } \times \sqrt {\sum\limits_{i = 1}^n {{{\left( {{b_i}} \right)}^2}} } } \right)}, \;\;\;\;\;\;&\mathit{\boldsymbol{M}} \ne {\bf{0}}且\mathit{\boldsymbol{N}} \ne {\bf{0}}, \\ 1, \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;&\mathit{\boldsymbol{M}} = \mathit{\boldsymbol{N}} = {\bf{0}}. \end{array} \right. \end{align} $

若将余弦相似度应用于信息系统的对象中，由于信息系统中的属性值往往都是正数，若信息系统出现负值时，利用文献[15]中的公式a′=(a－a_min)/(a_max－a_min)对数据进行模糊化处理，将属性值归一化为[0, 1]区间上的值后再对对象求余弦相似度.因此，余弦相似度在信息系统中有如下性质.

性质1  设S=(U, C∪D, V, f)是一个信息系统，M和N分别表示对象x_i和x_j在属性集C∪D上的属性值构成的向量，0表示零向量，则对象x_i和x_j的余弦相似度cos′()满足以下性质：

(1) 0≤cos′(M, N)≤1; (2) cos′(M, M)=1;

(3) cos′(0, N)=0，其中N≠0; (4) cos′(M, N)=cos′(N, M).

定义4^[16]  设S=(U, C∪D, V, f)是一个信息系统，U为非空有限论域，m:2^U→[0, 1]是一个映射，若满足m(∅)=0且$\sum\limits_{{X_i} \subseteq U} {m\left( {{X_i}} \right) = 1} $，则称m:2^U→[0, 1]是一个mass函数.

定义5^[2]  设S=(U, C∪D, V, f)是一个决策信息系统，U为非空有限论域，C为条件属性集，D为决策属性集.记R_C={(x_i, x_j): f_l(x_i)=f_l(x_j)(a_l∈C)}，R_D={(x_i, x_j): f_d(x_i)=f_d(x_j)(a_d∈D)}，若R_C⊆R_D，则称(U, C∪D, V, f)为协调决策信息系统，否则称(U, C∪D, V, f)为不协调决策信息系统.

定义6^[2]  设S=(U, C∪D, V, f)是一个决策信息系统，B_k(k≤r)为所有决策约简集，记$Core = \bigcap\limits_{k \le r} {{B_k}}, K = \bigcup\limits_{k \le r} {{B_k}-Core}, I = U-\bigcup\limits_{k \le r} {{B_k}} $.a∈Core时称a为决策核心，称Core为决策核心集；a∈K时称a为决策相对必要属性，称K为决策相对必要属性集；a∈I时称a为决策不必要属性，称I为决策不必要属性集.

2 一种基于聚类思想的相容关系

经典粗糙集中的关系都是等价关系，但是现实生活中的关系往往都是非等价关系.因此，结合聚类思想给出一种新的相容关系，并利用这种相容关系构造信息粒.在聚类分析中，余弦相似度常常用于衡量两个个体间差异的大小.余弦相似度利用余弦值表示向量的相似程度，两个向量的余弦值越接近1，则两个向量越相似.余弦值等于1，则两个向量相等，可以用聚类分析中的这种想法去构造信息系统中的相似类.但是在粗糙集中不仅要度量两个对象属性值构成的向量的夹角，还要度量它们的模.显然，余弦相似度无法满足度量向量模的要求.例如设对象x₁和x₂的属性值构成的向量分别为M=(2，4)和N=(3，6)，可得M和N的余弦相似度为1，即x₁和x₂归为一类，但是在粗糙集中，这样的结果显然不符合实际，因此对此相似性度量进行了改进.给出如下新的相似性度量的定义.

定义7  设S=(U, A=C∪D, V, f)为一个信息系统，U为非空有限论域，C为条件属性集，D为决策属性集，x_i, x_j∈U，M和N分别表示对象x_i和x_j在属性集A下的属性值构成的向量，则对象x_i和x_j的sim相似度sim_A(x_i, x_j)=cos′(M, N)×(1－‖M‖－‖N‖/max{‖M‖, ‖N‖})，其中|·|表示绝对值，规定当M=N=0时，‖M‖－‖N‖/max{‖M‖, ‖N‖}=0.

由sim相似度定义得$si{m_A}\left( {{x_1}, {x_2}} \right) = 1 \times \left( {1-\left| {\sqrt {20}-\sqrt {45} } \right|/\max \left\{ {\sqrt {20}, \sqrt {45} } \right\}} \right) = 2/3 $，消除了对应成比例的对象相似度为1的弊端.下面讨论改进的相似性度量的一些性质.

性质2  在信息系统S=(U, A=C∪D, V, f)中，∀x_i, x_j, x_k∈U，M、N和Q分别表示对象x_i、x_j和x_k在属性集A下的属性值构成的向量，0表示零向量，则sim相似度满足以下性质：

(1) 0≤sim_A(x_i, x_j)≤1; (2) sim_A(x_i, x_i)=1;

(3) sim_A(x_k, x_j)=0，其中Q=0，N≠0；(4) sim_A(x_i, x_j)=sim_A(x_j, x_i);

(5) 若sim_A(x_i, x_j)=1，则必有M=N.

定义8  设S=(U, A=C∪D, V, f)为一个信息系统，U为非空有限论域，C为条件属性集，D为决策属性集，A=C∪D的值集是全序集.根据sim相似度定义如下一种新的关系：

$ R_A^\varepsilon = \left\{ {\left( {{x_i}, {x_j}} \right)|si{m_A}\left( {{x_i}, {x_j}} \right) \ge \varepsilon, \forall {x_i}, {x_j} \in U} \right\}, $

其中0≤ε≤1，称R_A^ε为信息系统S=(U, A=C∪D, V, f)确定的A上的一个sim二元关系.

性质3  设S=(U, A=C∪D, V, f)为一个信息系统，R_A^ε为由A生成的sim二元关系，0≤ε≤1，则sim二元关系满足以下性质：

(1) 自反性：(x_i, x_i)∈R_A^ε; (2)对称性：(x_i, x_j)∈R_A^ε，则(x_j, x_i)∈R_A^ε.

证明  (1)因为sim_A(x_i, x_i)=1≥ε，所以(x_i, x_i)∈R_A^ε;

(2) 若(x_i, x_j)∈R_A^ε，则有sim_A(x_i, x_j)≥ε，又因为sim_A(x_j, x_i)=sim_A(x_i, x_j)≥ε，所以(x_j, x_i)∈R_A^ε.

注：sim二元关系不满足传递性，即若(x_i, x_j)∈R_A^ε，(x_j, x_k)∈R_A^ε，则(x_i, x_k)∈R_A^ε未必成立.设对象x₁、x₂、x₃的属性值构成的向量分别为M=(2，3，4，5)、N=(3，4，6，7)和Q=(2，6，4，1)，令阈值ε=0.68，由于sim_A(x₁, x₂)=0.7≥0.68，sim_A(x₁, x₃)=0.75≥0.68，即(x₁, x₂)∈R_A^ε，(x₁, x₃)∈R_A^ε，但是sim_A(x₂, x₃)=0.55≤0.68，即(x₂, x₃)∉R_A^ε.因此，R_A^ε是一个相容关系.

定义9  设S=(U, A=C∪D, V, f)为一个信息系统，U为非空有限论域，C为条件属性集，D为决策属性集，R_A^ε是U上关于A的相容关系.设(U, R_A^ε)为近似空间，由(U, R_A^ε)产生的相容类为R_A^ε(x_i)={x_j:(x_i, x_j)∈R_A^ε}，并且U/R_A^ε={R_A^ε(x_i):x_i∈U}，此时U/R_A^ε为论域U上的一个覆盖；对任意X⊆U，记$\underline {R_A^\varepsilon } $(X)={x_i:R_A^ε(x_i)_R⊆X}，$\overline {R_A^\varepsilon } $(X)={x_i:R_A^ε(x_i)_R∩X≠∅}，则称$\underline {R_A^\varepsilon } $(X)为X的sim下近似，$\overline {R_A^\varepsilon } $(X)为X的sim上近似.基于sim下近似与sim上近似得到的粗糙集称为sim粗糙集.

性质4  对于任意的X, Y⊆U，sim上、下近似满足以下性质：

(1) $ \underline {R_A^\varepsilon } \left( X \right) \subseteq X \subseteq \overline {R_A^\varepsilon } \left( X \right);$(2) $\underline {R_A^\varepsilon } \left( \emptyset \right) = \emptyset = \overline {R_A^\varepsilon } \left( \emptyset \right), \underline {R_A^\varepsilon } \left( U \right) = U = \overline {R_A^\varepsilon } \left( U \right); $

(3) $\overline {R_A^\varepsilon } \left( {X \cup Y} \right) = \overline {R_A^\varepsilon } \left( X \right) \cup \overline {R_A^\varepsilon } \left( Y \right); $ (4) $\underline {R_A^\varepsilon } \left( {X \cap Y} \right) = \underline {R_A^\varepsilon } \left( X \right) \cap \underline {R_A^\varepsilon } \left( Y \right); $

(5) $ X \subseteq Y \Rightarrow \underline {R_A^\varepsilon } \left( X \right) \subseteq \underline {R_A^\varepsilon } \left( Y \right);$ (6) $X \subseteq Y \Rightarrow \overline {R_A^\varepsilon } \left( X \right) \subseteq \overline {R_A^\varepsilon } \left( Y \right); $

(7) $ \underline {R_A^\varepsilon } \left( {X \cup Y} \right) \supseteq \underline {R_A^\varepsilon } \left( X \right) \cup \underline {R_A^\varepsilon } \left( Y \right);$ (8) $\overline {R_A^\varepsilon } \left( {X \cap Y} \right) \subseteq \overline {R_A^\varepsilon } \left( X \right) \cap \overline {R_A^\varepsilon } \left( Y \right); $

(9) $\underline {R_A^\varepsilon } \left( { \sim X} \right) = \sim \overline {R_A^\varepsilon } \left( X \right); $ (10) $\overline {R_A^\varepsilon } \left( { \sim X} \right) = \sim \underline {R_A^\varepsilon } \left( X \right). $

3 基于聚类思想的对象权重确定方法

现有的权重确定方法主要集中在属性权重上，虽然属性权重会对决策和约简产生较大的影响，但在现实生活中对象权重也会对约简结果产生影响.一些学者利用代价敏感和AHP方法在对象权重的确定方法上做出了一些成果，但是这些方法都受到较大的主观因素的影响.因此，利用聚类分析的思想构造二元关系的方法来给出对象权重，从而降低主观因素的影响.

定义10  设S=(U, A=C∪D, V, f)是一个信息系统，X={X₁, X₂, …, X_n}表示由关系R_A^ε生成的覆盖，其中X_i为包含x_i的相容类，p表示U上的概率分布，则相容类X_i的mass函数定义为

$ m\left( {{X_i}} \right) = p\left( {{X_i}} \right)/\sum\limits_{{X_i} \in X} {p\left( {{X_i}} \right)} . $

易证m(X_i)满足mass函数的基本性质，因此是一个mass函数.mass函数是2^U上的概率分布函数，可以构造出2^U上的每个信息粒的一个不确定性度量——粒的权重.

定义11  设S=(U, A=C∪D, V, f)是一个信息系统，对于x, y∈U，R_A^ε(x)和R_A^ε(y)分别表示由属性集A生成对象x、y的相容类，|·|表示集合的基数，则x的权重定义为

$ \omega \left( x \right) = m\left( {R_A^\varepsilon \left( x \right)} \right)/\left| {y|R_A^\varepsilon \left( x \right) = R_A^\varepsilon \left( y \right)} \right|. $

定义12  设X，Y⊆U，若令ω(X)、ω(Y)和ω(X∩Y)分别表示X、Y和X∩Y的权重，ω(x_i)是x_i∈U的权重，则X∪Y的权重ω(X∪Y)=ω(X)+ω(Y)－ω(X∩Y).特别地，$ \omega \left( X \right) = \sum\limits_{{x_i} \in X} {\omega \left( {{x_i}} \right)} $.

性质5  设S=(U, A=C∪D, V, f)是一个信息系统，ω(x_i)是对象x_i∈U的权重，则ω(x_i)满足以下性质：

(1) 0 < ω(x_i)≤1；(2) $\sum\limits_{{x_i} \in U} {\omega \left( {{x_i}} \right) = 1} $.

证明  (1)设R_A^ε(x_i)={x_j:(x_i, x_j)⊆R_A^ε}是包含x_i的相容类，由自反性知(x_i, x_i)⊆R_A^ε，即有x_i∈R_A^ε(x_i)，所以R_A^ε(x_i)≠∅，由于x_i∈{x_j|R_A^ε(x_i)=R_A^ε(x_j)}，所以|{x_j:R_A^ε(x_i)=R_A^ε(x_j)}|>0.由已知可知p为U上的概率分布，所以p(R_A^ε(x_i))>0，因而0 < m(R_A^ε(x_i))=p(R_A^ε(x_i))/$\sum\limits_{R_A^\varepsilon \left( {{x_i}} \right) \subseteq U/R_A^\varepsilon } {p\left( {R_A^\varepsilon \left( {{x_i}} \right)} \right)} $ < 1，从而有0 < ω(x_i)=m(R_A^ε(x_i))/|{x_j|R_A^ε(x_i)=R_A^ε(x_j)}|≤m(R_A^ε(x_i))/|{x_i}|≤m(R_A^ε(x_i))≤1，所以得0 < ω(x_i)≤1；

(2) 设R_A^ε(x_i)={x_j:(x_i, x_j)⊆R_A^ε}是包含x_i的相容类，X={X₁, X₂, …, X_n}是由关系R_A^ε生成的相容类，则$ \sum\limits_{{x_i} \in U} {\omega \left( {{x_i}} \right)} = \sum\limits_{{X_n} \in X} {\sum\limits_{\left\{ {{x_i}|R_A^\varepsilon \left( {{x_i}} \right) = {x_n}} \right\}} {\omega \left( {{x_i}} \right)} } = \sum\limits_{{X_n} \in X} {m\left( {{X_n}} \right)} = 1.$

4 基于加权条件信息熵的属性重要度确定方法与约简算法

信息熵是信息论的主要内容之一，它可以对信息量进行量化度量.知识从信息中获得，所以知识也是一种特殊的信息^[13].因此，熵理论也可用于粗糙集的研究中.下面给出一种基于对象权重的加权条件熵的定义方式，并提出了基于加权条件熵的属性重要度确定方法和属性约简算法.

定义13  设S=(U, A=C∪D, V, f)是一个信息系统，X={X₁, X₂, …, X_n}表示由关系R_A^ε生成的相容类，|·|表示集合的基数，则由X得到的加权信息熵${H_\omega }\left( X \right){\rm{ = }}\left( {4/n} \right) \cdot \sum\limits_{i = 1}^n {\omega \left( {{X_i}} \right)} \cdot \left( {\left| {{X_i}} \right|/\left| U \right|} \right) \cdot \left( {1-\left| {{X_i}} \right|/\left| U \right|} \right) $.因为|X_i|/|U|=1/2时，(|X_i|/|U|)·(1－|X_i|/|U|)=1/2×(1－1/2)=1/4达到最大值.因此，选择4/n而非1/n会使得加权信息熵具有一些特殊的性质.

性质6  由X得到的加权信息熵满足以下性质:

(1) $0 \le {H_\omega }\left( X \right) \le \left( {1/n} \right) \cdot \sum\limits_{i = 1}^n {\omega \left( {{x_i}} \right)} $; (2)对于∀X_i∈X，若X_i=U，则H_ω(X)=0;

(3) 若所有的相容类权重都相同，即ω(X₁)=ω(X₂)=…=ω(X_n)=ω时，则当|X_i|/|U|=1/2时，H_ω(X)取得最大值，并且H_ω(X)=ω.

证明  (1)因为0≤(|X_i|/|U|)·(1－|X_i|/|U|)≤1/4，所以有$0 \le \left( {4/n} \right) \cdot \sum\limits_{i = 1}^n {\omega \left( {{X_i}} \right)} \cdot \left( {\left| {{X_i}} \right|/\left| U \right|} \right) \cdot \left( {1-\left| {{X_i}} \right|/\left| U \right|} \right) \le \left( {4/n} \right) \cdot \sum\limits_{i = 1}^n {\omega \left( {{X_i}} \right)} \times 1/4 = \left( {1/n} \right) \cdot \sum\limits_{i = 1}^n {\omega \left( {{X_i}} \right)} $，即$ 0 \le {H_\omega }\left( X \right) \le \left( {1/n} \right) \cdot \sum\limits_{i = 1}^n {\omega \left( {{x_i}} \right)} $；

(2) 对于∀X_i∈X，若X_i=U，则${H_\omega }\left( X \right) = \left( {4/n} \right) \cdot \sum\limits_{i = 1}^n {\omega \left( {{X_i}} \right)} \cdot \left( {\left| {{X_i}} \right|/\left| U \right|} \right) \cdot \left( {1-\left| {{X_i}} \right|/\left| U \right|} \right) = $$\left( {4/n} \right) \cdot \sum\limits_{i = 1}^n {\omega \left( {{X_i}} \right)} \cdot \left( {\left| U \right|/\left| U \right|} \right) \cdot \left( {1-\left| U \right|/\left| U \right|} \right) = \left( {4/n} \right) \cdot \sum\limits_{i = 1}^n {\omega \left( {{X_i}} \right)} \times 1 \times \left( {1-1} \right) = 0 $；

(3) 因为ω(X₁)=ω(X₂)=…=ω(X_n)=ω，所以有${H_\omega }\left( X \right) = \left( {4/n} \right) \cdot \sum\limits_{i = 1}^n {\omega \left( {{X_i}} \right)} \cdot \left( {\left| {{X_i}} \right|/\left| U \right|} \right) \cdot \left( {1-\left| {{X_i}} \right|/\left| U \right|} \right) = $$\left( {4/n} \right) \cdot \sum\limits_{i = 1}^n \omega \cdot \left( {\left| {{X_i}} \right|/\left| U \right|} \right) \cdot \left( {1- \left| {{X_i}} \right|/\left| U \right|} \right) = \left( {4\omega /n} \right) \cdot \sum\limits_{i = 1}^n {\left[{1/4-{{\left( {\left| {{X_i}} \right|/\left| U \right|-1/2} \right)}^2}} \right]} $$\le \left( {4\omega /n} \right) \cdot \sum\limits_{i = 1}^n {\left( {1/4} \right)} = \left( {4\omega /n} \right) \times n/4 = \omega $，当且仅当|X_i|/|U|=1/2时等号成立.

令~X_i表示X_i的补集，由于ω(~X_i)与ω(X_i)不一定相等，因此，H_ω(~X)和H_ω(X)不一定相等，即加权信息熵不满足对称性.新定义的加权信息熵满足上面几条性质，符合加权信息熵的条件.下面给出相应的加权条件熵的定义.

定义14  设S=(U, C∪D, V, f)是一个决策信息系统，U为有限非空论域，C为条件属性集，D为决策属性集.X={X₁, X₂, …, X_n}是由相容关系R_C^ε产生的U上的一个覆盖，D={D₁, D₂, …, D_m}是由等价关系R_D产生的U上的一个划分，ω(X_i∩D_j)表示集合X_i∩D_j的权重，则X相对于D的条件熵${H_\omega }\left( {D|X} \right) = \left( {4/\left| U \right|} \right) \cdot \sum\limits_{j = 1}^m {\sum\limits_{i = 1}^n {\omega \left( {{X_i} \cap {D_j}} \right)} } \cdot \left( {\left| {{X_i} \cap {D_j}} \right|/\left| U \right|} \right) \cdot \left[{1-\left| {{X_i} \cap {D_j}} \right|/\left| {{X_i}} \right|} \right] $.

性质7  X相对于D的加权条件熵满足以下性质：

(1) H_ω(D|X)≥0; (2)若R_C^ε⊆R_D，则H_ω(D|X)=0; (3)若$ R_C^\varepsilon \not\subseteq {R_D}$，则H_ω(D|X)>0.

证明  (1)因为∅≤X_i∩D_j≤U，∅≤X_i∩D_j≤X_i，所以0≤|X_i|∩|D_j|/|U|≤|U|/|U|=1，0≤|X_i|∩|D_j|/|U|≤|X_i|/|X_i|=1，又因为ω(X_i∩D_j)≥0，4/|U|>0，所以由加权条件熵公式知${H_\omega }\left( {D|X} \right) = \left( {4/\left| U \right|} \right) \cdot \sum\limits_{j = 1}^m {\sum\limits_{i = 1}^n {\omega \left( {{X_i} \cap {D_j}} \right)} } \cdot \left( {\left| {{X_i} \cap {D_j}} \right|/\left| U \right|} \right) \cdot \left[{1-\left| {{X_i} \cap {D_j}} \right|/\left| {{X_i}} \right|} \right] \ge 0 $；

(2) 因为R_C^ε⊆R_D，所以对于任意的X_i存在一个D_j有X_i⊆D_j，即X_i∩D_j=X_i，因此有|X_i|∩|D_j|/|X_i|=1，所以${H_\omega }\left( {D|X} \right) = \left( {4/\left| U \right|} \right) \cdot \sum\limits_{j = 1}^m {\sum\limits_{i = 1}^n {\omega \left( {{X_i} \cap {D_j}} \right)} } \cdot \left( {\left| {{X_i} \cap {D_j}} \right|/\left| U \right|} \right) \cdot \left[{1-\left| {{X_i} \cap {D_j}} \right|/\left| {{X_i}} \right|} \right] = 0 $；

(3) 因为$R_C^\varepsilon \not\subseteq {R_D} $，则存在一个X_i对于任意的D_j有${X_i} \not\subseteq {D_j} $，所以X_i∩D_j ⊂X_i，又因为X是U上的一个覆盖，D是U上的一个划分，所以一定存在X_i和D_j有X_i∩D_j≠∅，故存在一个ω(X_i∩D_j)>0与0 < |X_i∩D_j|/|X_i| < 1，4/|U|>0，所以得${H_\omega }\left( {D|X} \right) = \left( {4/\left| U \right|} \right) \cdot \sum\limits_{j = 1}^m {\sum\limits_{i = 1}^n {\omega \left( {{X_i} \cap {D_j}} \right)} } \cdot \left( {\left| {{X_i} \cap {D_j}} \right|/\left| U \right|} \right) \cdot \left[{1-\left| {{X_i} \cap {D_j}} \right|/\left| {{X_i}} \right|} \right] > 0 $.

现有的属性约简算法主要是在对象重要度相同的基础上给出的，但是在现实生活中，对象的重要性往往都是不相同的.虽然文献[12]考虑了对象权重对约简的影响，但是其考虑的对象权重需要依赖专家的先验知识得到，增加了主观因素对约简算法的影响.为了降低这种影响，根据聚类分析与粗糙集相结合所得的属性重要度与熵理论给出新的基于加权条件熵的属性约简算法，该算法是一种基于熵不变的约简算法.

定义15  设S=(U, C∪D, V, f)是一个信息系统，U为有限非空论域，C为条件属性集，D为决策属性集.若对于B⊆C，有H_ω(D|B)=H_ω(D|C)，且对于B的任何真子集B′都有H_ω(D|B′)≠H_ω(D|C)，则称B为C的一个熵约简.

定理1  设S=(U, C∪D, V, f)是一个信息系统，U为有限非空论域，C为条件属性集，D为决策属性集，则有

(1) 若S为协调信息系统，则H_ω(D|C)=0；

(2) 若S为不协调信息系统，则H_ω(D|C)>0；

(3) 若S是一个协调信息系统，a是决策核心，则有H(D|C)=0，H_ω(D|C－{a})>0;

(4) 若S是一个不协调信息系统，a是核心属性，则有H_ω(D|C－{a})≠H_ω(D|C).

定义16  对于加权目标信息系统S_ω=〈U, W, C·D, V, f〉，U为有限非空论域，C为条件属性集，D为决策属性集，W为权重集合.设B⊂C，则对于任意属性a∈C－B，属性a对属性集B的内部属性重要度为SGF(a, B, D)_in=|H_ω(D|B)－H_ω(D|B－a)|；属性a对属性集B的外部属性重要度为SGF(a, B, D)_out=|H_ω(D|B)－H_ω(D|B∪a)|.

基于给出的内部属性重要度和外部属性重要度，提出了两种启发式约简算法，见表 1.算法首先选取信息系统的核心属性，然后添加外部属性重要度大的属性，最后再删除多余属性即可得到最终约简.算法1和算法2分别介绍了协调信息系统和不协调信息系统的属性约简算法.

例1  为了说明算法的合理性，以表 2的信息表为例进行仿真计算.

给定阈值ε=0.6，可得sim相容类R_C^ε(x₁)=R_C^ε(x₃)={x₁, x₂, x₃, x₄, x₅, x₇}, R_C^ε(x₂)=R_C^ε(x₄)=R_C^ε(x₅)=R_C^ε(x₇)={x₁, x₂, x₃, x₄, x₅, x₆, x₇, x₈}, R_C^ε(x₆)=R_C^ε(x₈)={x₂, x₄, x₅, x₆, x₇, x₈}, U/{d}={{x₁, x₂, x₃}, {x₄, x₅, x₇, }, {x₆, x₈}}.因为计算的加权条件熵为H_ω(D|C)=0.234 1，即原信息系统是不协调信息系统，所以设定参数θ=0.002，根据mass函数的定义可得m[R_C^ε(x₁)]=m[R_C^ε(x₃)]=0.3，m[R_C^ε(x₂)]=m[R_C^ε(x₄)]=m[R_C^ε(x₅)]=m[R_C^ε(x₇)]=0.4，m[R_C^ε(x₆)]=m[R_C^ε(x₈)]=0.3，由权重定义可得ω(x₁)=ω(x₃)=0.15，ω(x₂)=ω(x₄)=ω(x₅)=ω(x₇)=0.1，ω(x₆)=ω(x₈)=0.15.

由重要度定义求得a₁的内部重要度SGF(a₁, B, D)_in=|H_ω(D|B)－H_ω(D|B－a₁)=0，同理可得a₂, a₃, a₄的内部重要度SGF(a₂, B, D)_in=0.013 3，SGF(a₃, B, D)_in=0.124，SGF(a₄, B, D)_in=0，又由于原信息系统是不协调的信息系统，所以根据SGF(a_i, B, D)>0.002得RED={a₂, a₃}.又由于此时满足H_ω(D|C)－H_ω(D|B∪{a_max}) < θ，再逐个删除多余属性即得最后约简RED={a₂, a₃}.

为了验证所提出的算法在大数据中的有效性，从UCI数据库找出几组数据分别与文献[11, 17]中的α-FRS算法和FNRS算法进行了对比实验，进行约简之前按照文献[11, 17]的方法对有数据缺失的对象进行了删除，并将处理后的数据集描述列于表 3中.对几组数据集选取合适的ε与θ值，本文算法与α-FRS算法和FNRS算法的约简结果对比分别列于表 4和表 5中.数据集Ecoli在不同参数下的约简结果列于表 6中.

根据表 6参数的变化可以看出，随着ε的减小，信息系统会变得不协调，而参数θ的变大会使得约简越来越小.根据专家的经验对数据集设置合适的ε与θ值，就能得到一个合适的约简结果.

5 结束语

将粗糙集理论与聚类分析的方法相结合提出了一种新的对象权重的确定方法，并且将对象权重与熵理论相结合给出了一个新的加权条件熵的定义，同时给出了基于加权条件熵属性重要度的新定义.最后基于此属性重要度给出了属性约简算法，并且用UCI中选取的几组数据集验证了该算法的合理性和有效性.