第3期 唐荣，等：不完备数据中面向特征值更新的增量特征选择方法 ·495· NDP)={(x,y)eU×UIMa∈P,fx,a=fy,a)l 征值发生更新时相容类和决策类的变化情况。由 ND(P)是具有自反性、对称性与传递性的等 于条件嫡的计算与相容类和决策类中的对象顺序 价关系。等价关系ND(P)将论域U划分为等价 无关，为了方便阐述，下文中假设决策系统中 类的集合，表示为UND(P)={[xPx∈U,其中 发生特征值修改的对象集合为{xi=p+1,P+2,…,qh, [xp=byx,y)∈ND(P)I。为了处理含有缺失值的不 则更新后不完备决策系统中相容类的更新为 完备决策系统，Kryszkiewicz提出一种新的二元关 U/T'(P)={T'(xi=1,2,…,p,p+1…, 系T(P),PsC,定义为 9,9+1,…,k,k+1,…,m T(P)={(x,y)∈U×UNa∈Pfx,a=fy,aV 式中：x(=1,2,…,p)表示相容类保持不变的对象， f(x,a)=*vf(y.a)=* 即T()=T(x;x(i=p+1,p+2,…,q)表示特征值 T(P)是具有自反性和对称性，但不具有传递性 发生变化的对象，其相容类需根据定义计算，即 的相容关系。在P下任意一个对象x∈U的相容 T(x)={西∈UI(,)eT'(P)hx=q+1,q+2,…,k)和 类定义为T(x)=y∈UI(x,y)∈T(P)I。U/T(P)表示相 x(i=k+1,k+2,…,)分别表示相容类可能出现的 容类集合{T(Px∈U。U/T(P)中构成论域U上的 两种更新模式的对象集合。对于对象集合 一个覆盖，对于论域中任意一个对象x∈U,T(x)≠O, x(i=q+1,9+2,…,k),相容类更新为T(x)=(T(x)- 并且UxeUTp(x)=U。给定一个不完备决策系统 T(x)UT(x,对于对象集合xi=k+1,k+2,…,m, DS=(U,CU{d,V,fD,决策属性d将对象分类为m 相容类更新方式为T(x)=T(x)-T(x),其中， 个确定互斥的子集U/d={D,D2,…,Dm}。目标决 Tp(x)={xlx,xl∈T(P),p+1≤l≤q小；T(x)={lx,x}∈ 策概念D:∈U/D的上、下近似集定义为 T'(P),p+1≤I≤qlo apr(D)=(xEUIT(x)C D.) 不完备决策系统中决策特征值发生变化后决 apr(D)={x∈UITp(x)nD≠O] 策类的更新为 基于粗糙集理论的特征选择方法根据特征重 U/d={Dj=1,2,…,q,q1+1,…,92,q2+1,…,m 要度的不同度量标准，可笼统地归纳为依赖性度 式中：D=1,2,…,q)表示决策类保持不变的对 量、一致性度量、距离度量和信息度量。前面 象，即D=Dj;Dj=q1+1,q1+2,…,q2)表示需要 3种度量方法都局限于数据的实际值，对含有噪 从当前决策类中删除特征值更新的可辨识对象， 声或缺失值的数据处理十分敏感。而基于信息论 即D=D,-D;Dj=q2+1,2+2,…,m)表示不仅 的度量方法仅关注随机变量的概率分布，不关注 需要删除特征值发生更新的可辨识对象集合，同 其实际值，成为了高维数据中常用的特征重要度 时要增加新特征值下不可辨识的对象集合，即 度量方式。借鉴香农熵的传统定义形式，Dai等四 D=(D-D)UD,其中D={x归x,∈D,fx,d)= 定义了一种新的满足单调性的条件熵来度量不完 fx,d0,p+1≤I≤ql,D={xl旧x,∈D,f,d)=fxr,d0, 备决策系统协调程度的不确定性。给定一个不完 p+1≤l≤ql。 备决策系统DS=(U,CUd,Vf),其中，U={x,2,…, 根据上文中不完备决策系统中特征值动态修 xn};U/T(P)={Tp(ci=1,2,…,n;UId={D,D2,… 改后相容类和决策类的更新模式，下面进一步可 Dm}。决策特征d关于条件特征子集P的条件嫡 得相容类与决策类交集的动态更新方式。 定义为 Hd=-∑∑lnDl 对于任意对象xi=1,2,…,p)的相容类和决 (1) 策类Dj=1,2…,m),有T()nD=Tn()nDl 1 IT( 成立，对于任意对象x(i=p+1,p+2,…,9),由于其 根据式(1)，通过从特征子集P删除某个特 相容类需根据定义计算，无法利用已有结果，因 征a引起的条件熵的变化大小，可定义特征的重 此相容类和决策类Dj=1,2,…,m)的交集表示为 要度度量函数： T()nD。 sig(a,P.d)=H(dlp)-H(dlp-(a) 对于任意对象x(i=q+1,q+2,…,k)的相容类 2不完备数据集中特征值更新的增 和决策类DG=1,2,…,m),其交集的更新模式为 量特征选择 IT'(x)ODI= T(x)nDl,1≤j≤q1 当不完备决策系统中特征值发生动态更新时， ITr(x)OD-ITE(x)0D- IT()ODil+IT()ODil q1+1≤j≤q2 由特征子集所诱导的相容关系和由决策特征所诱 IT()0D-ITE(ODl- 导的等价关系会随之变化，进而使得特征度量准则 IT (x)OT(x+T()0Dil+ 条件熵发生变化。下面，首先分析一组对象的特 IT:(x)ODil ,92+1≤j≤mIND(P) = {(x, y) ∈ U ×U|∀a ∈ P, f(x,a) = f(y,a)} IND(P) IND(P) U U/IND(P) = {[x]P|x ∈ U} [x]P = {y|(x, y) ∈ IND(P)} T(P),P ⊆ C 是具有自反性、对称性与传递性的等 价关系。等价关系 将论域 划分为等价 类的集合，表示为 ，其中 。为了处理含有缺失值的不 完备决策系统，Kryszkiewicz 提出一种新的二元关 系 ，定义为 T(P) = {(x, y) ∈ U ×U|∀a ∈ P, f(x,a) = f(y,a)∨ f(x,a) = ∗ ∨ f(y,a) = ∗} T(P) x ∈ U TP(x) = {y ∈ U|(x, y) ∈ T(P)} U/T(P) {T(P)|x ∈ U} U/T(P) U x ∈ U,TP(x) , Ø ∪x∈U TP(x) = U IDS = (U,C ∪ {d},V, f) d m U/d = {D1,D2,··· ,Dm} Di ∈ U/D 是具有自反性和对称性，但不具有传递性 的相容关系。在 P 下任意一个对象 的相容 类定义为 。 表示相 容类集合 。 中构成论域 上的 一个覆盖，对于论域中任意一个对象 ， 并且 。给定一个不完备决策系统 ，决策属性 将对象分类为 个确定互斥的子集 。目标决 策概念 的上、下近似集定义为 apr(Di) = {x ∈ U|TP(x) ⊆ Di} apr(Di) = {x ∈ U|TP(x)∩ Di , Ø} IDS = (U,C ∪ {d},V, f) U = {x1, x2,··· , xn} U/T(P) = {TP(xi)|i = 1,2,··· ,n} U/d = {D1,D2,··· , Dm} d P 基于粗糙集理论的特征选择方法根据特征重 要度的不同度量标准，可笼统地归纳为依赖性度 量、一致性度量、距离度量和信息度量。前面 3 种度量方法都局限于数据的实际值，对含有噪 声或缺失值的数据处理十分敏感。而基于信息论 的度量方法仅关注随机变量的概率分布，不关注 其实际值，成为了高维数据中常用的特征重要度 度量方式。借鉴香农熵的传统定义形式，Dai 等 [8,12] 定义了一种新的满足单调性的条件熵来度量不完 备决策系统协调程度的不确定性。给定一个不完 备决策系统 ，其中， ； ； 。决策特征 关于条件特征子集 的条件熵 定义为 H(d|P) = − ∑n i=1 ∑m j=1 |TP(xi)∩ Dj | |U| log2 |TP(xi)∩ Dj | |TP(xi)| (1) P a 根据式（1），通过从特征子集 删除某个特 征 引起的条件熵的变化大小，可定义特征的重 要度度量函数： sig(a,P,d) = H(d|P)− H(d|P− {a}) 2 不完备数据集中特征值更新的增 量特征选择 当不完备决策系统中特征值发生动态更新时， 由特征子集所诱导的相容关系和由决策特征所诱 导的等价关系会随之变化，进而使得特征度量准则 条件熵发生变化。下面，首先分析一组对象的特 {xi |i = p+1, p+2,··· ,q} 征值发生更新时相容类和决策类的变化情况。由 于条件熵的计算与相容类和决策类中的对象顺序 无关，为了方便阐述，下文中假设决策系统中 发生特征值修改的对象集合为 ， 则更新后不完备决策系统中相容类的更新为 U/T ′ (P) = {T ′ P(xi)|i = 1,2,··· , p, p+1,··· , q,q+1,··· , k, k+1,··· ,n} xi(i = 1,2,··· , p) T ′ P (xi) = TP(xi) xi(i = p+1, p+2,··· ,q) T ′ P (xi) = {xl ∈ U|(xi , xl) ∈ T ′ (P)} xi(i = q+1,q+2,··· ,k) xi(i = k+1, k+2,··· ,n) xi(i = q+1,q+2,··· , k) T ′ P (xi) =(TP(xi)− T − P (xi))∪T + P (xi) xi(i = k+1,k+2,··· ,n) T ′ P (xi) = TP(xi)−T − P (xi) T − P (xi)={xl |{xi , xl} ∈T(P), p+1⩽l⩽q} T + P (xi)={xl |{xi , xl} ∈ T ′ (P), p+1 ⩽ l ⩽ q} 式中： 表示相容类保持不变的对象， 即 ； 表示特征值 发生变化的对象，其相容类需根据定义计算，即 ； 和 分别表示相容类可能出现的 两种更新模式的对象集合。对于对象集合 ，相容类更新为 ，对于对象集合 ， 相容类更新方式为 ，其中， ； 。 不完备决策系统中决策特征值发生变化后决 策类的更新为 U/d = {D ′ j | j = 1,2,··· ,q1 ,q1 +1,··· ,q2 ,q2 +1,··· ,m} D ′ j (j = 1,2,··· ,q1) D ′ j = Dj D ′ j (j = q1 +1,q1 +2,··· ,q2) D ′ j = Dj − D − j D ′ j (j = q2 +1,q2 +2,··· ,m) D ′ j = (Dj−D − j )∪ D + j D − j = {xl |∃xr ∈ Dj , f(xl ,d) = f(xr ,d),p+1⩽l⩽q} D + j = {xl |∃xr ∈ Dj , f(xl ,d) = f(xr ,d), p+1 ⩽ l ⩽ q} 式中： 表示决策类保持不变的对 象，即 ； 表示需要 从当前决策类中删除特征值更新的可辨识对象， 即 ； 表示不仅 需要删除特征值发生更新的可辨识对象集合，同 时要增加新特征值下不可辨识的对象集合，即 ，其中 ， 。 根据上文中不完备决策系统中特征值动态修 改后相容类和决策类的更新模式，下面进一步可 得相容类与决策类交集的动态更新方式。 xi(i = 1,2,··· , p) D ′ j (j = 1,2,··· ,m) |T ′ P (xi)∩ D ′ j | = |TP(xi)∩ Dj | xi(i = p+1, p+2,··· ,q) D ′ j (j = 1,2,··· ,m) |T ′ P (xi)∩ D ′ j | 对于任意对象 的相容类和决 策 类 ， 有 成立，对于任意对象 ，由于其 相容类需根据定义计算，无法利用已有结果，因 此相容类和决策类 的交集表示为 。 xi(i = q+1,q+2,··· , k) D ′ j (j = 1,2,··· ,m) 对于任意对象 的相容类 和决策类 ，其交集的更新模式为 |T ′ P(xi)∩ D ′ | =    |TP(xi)∩ Dj |, 1 ⩽ j ⩽ q1 |TP(xi)∩ Dj | − |T − P (xi)∩ Dj |− |TP(xi)∩ D − j |+|T − P (xi)∩ D − j |, q1 +1 ⩽ j ⩽ q2 |TP(xi)∩ Dj | − |T − P (xi)∩ Dj |− |TP(xi)∩T − P (xi)|+|T − P (xi)∩ D − j |+ |T + P (xi)∩ D + j | , q2 +1 ⩽ j ⩽ m 第 3 期 唐荣，等：不完备数据中面向特征值更新的增量特征选择方法 ·495·