第6期 张晓鹤，等：基于信息嫡的对象加权概念格 ·1099· 形式背景(U,A,D上的任意对象x∈U,如果D(x)> 设(U,A,I,D,)为决策形式背景，则由形式背 6,则称x为偏差对象。不包含冗余属性、冗余对 景F=(U,A,D能够获得子形式背景Fp=(Un,AD 象、偏差对象的子形式背景，记为Fo=(Uo,AD,Io)。 ),进一步可构造对象强加权概念格，记为 由此构造的概念格称为对象强加权概念格。 L(Uo,An,Ib)。称(XB)∈L(Uo,Ao,Io)为条件概念。 通过删除不满足给定的属性权重阈值α的属 X、B均为非空集合，如果有XD=1,则称 性和不满足对象权重阈值B或对象重要度偏差阈 X (X,B)白(Dk,T)为决策形式背景的粒决策规则。 值6的对象能够节省形式背景存储空间，从而获 简记为B→T。 得简化的概念格，提升概念格构造效率，并且获 下面给出具体算法。 取的概念形式更为简单，有利于规则提取。 算法2粒决策规则获取算法 算法1对象强加权概念格的构造算法 输入(U,A,I,D,) 输入F=(U,A,D,a,B,6(其中0≤a≤1， 输出粒决策规则 0≤B≤1,0≤6≤1)： 1)compute L(Fp) 输出对象强加权概念格。 1)forl≤i≤4do 2)Vx.yEU 3)for1≤k≤ID1do 2)w(a)= H(a) 4)if di(x)=d(y)then ∑H(a) 5)(x.y)ERp 3)end for 6)end if 4)initialize d'(x )=0 7U/RD={xb:x∈U={D1,D2,…,D} 5)for1≤i≤4,1≤j≤lU1do 8)end for 6)if (xja)EI then 9)compute (D..T,) 7)d(x)←-w(a) l0)for all(X,B)eL(Fo),1≤t≤rdo 8)end if 11)f1 then X d'(x) 9)compute d(x)= 12)(XB)→(D,T) fx) 13)end if 10)D(x) Vr-i∑(wa-dsy 3实验和分析 11)end for 12)if w(a )<a,d(x)<B or D(xj)>6 then 3.1应用举例 13)delete xi,a 由表1给出人才市场大学生就业信息，处理 14)end if 后构成形式背景F=(U,A,),其中对象集为6位 15)Fp=(U/x,A/a,I') 求职者。属性集为A={a,b,c,d,eh,分别代表5个 16)return L(FD) 属性，即应届生、数学专业、教师资格证、英语四 2.3基于对象强加权概念格的决策规则提取 级、计算机二级。 通过2.2节中给出的对象强加权概念格的构 表1形式背景F=(U,A,) 造过程，能够帮助我们获取更为简单的概念格。 Table 1 Formal context:F=(U,A,D 如在决策形式背景中，利用该方法对于条件概念 序号 6 格进行简化，则能够大大降低概念提取的难度。 定义8设(U,A,I,D,)为决策形式背景，由 1 Rp=(x,y)eU×U:d(x)=dy)(d∈D)h,可产生U 3 上的一个划分： UIRo=xD:x∈U={D1,D2,…,D} 6 其中：xo=y∈U:(xy∈R;Hd∈D。如x,y∈Ds, 必有d(x)=dy),显然属于同一决策类的对象具 1)直接构造概念格 有相同的决策值，记T={d(De),d(D),…,do(D)》 由表1给出的形式背景直接构造的概念格如 为D的决策值。(D,T)称为决策概念。 图1所示，共12个概念结点。(U,A,I) x ∈ U D(x) > δ x FD =(UD,AD,ID) 形式背景 上的任意对象 ，如果 ，则称 为偏差对象。不包含冗余属性、冗余对 象、偏差对象的子形式背景，记为 。 由此构造的概念格称为对象强加权概念格。 α β δ 通过删除不满足给定的属性权重阈值 的属 性和不满足对象权重阈值 或对象重要度偏差阈 值 的对象能够节省形式背景存储空间，从而获 得简化的概念格，提升概念格构造效率，并且获 取的概念形式更为简单，有利于规则提取。 算法 1 对象强加权概念格的构造算法 F = (U,A,I) α β δ 0 ⩽ α ⩽ 1 0 ⩽ β ⩽ 1 0 ⩽ δ ⩽ 1 输 入 ， ， ， ( 其 中 ， ， )； 输出 对象强加权概念格。 1) for 1 ⩽ i ⩽ |A| do w(ai) = H(ai) ∑ |A| i=1 H (ai) 2) 3) end for d ′ 4) initialize (xj) = 0 5) for 1 ⩽ i ⩽ |A|，1 ⩽ j ⩽ |U| do (xj 6) if ,ai) ∈ I then d ′ 7) (xj) ← w(ai) 8) end if d(xj) = d ′ (xj)    f(xj)    9) compute D(xj) = √ 1    f(xj)   −1 ∑ (w (ai)−d(xj))2 10) 11) end for 12) if w(ai) < α，d(xj) < β or D(xj) > δ then 13) delete xj，ai 14) end if FD = (U/xj ,A/ai ,I ′ 15) ) 16) return L(FD) 2.3 基于对象强加权概念格的决策规则提取 通过 2.2 节中给出的对象强加权概念格的构 造过程，能够帮助我们获取更为简单的概念格。 如在决策形式背景中，利用该方法对于条件概念 格进行简化，则能够大大降低概念提取的难度。 (U,A,I,D, J) RD = {(x, y) ∈ U ×U : dl(x) = dl(y) (∀dl ∈ D)} U 定义 8 设 为决策形式背景，由 ，可产生 上的一个划分： U/RD = {[x]D : x ∈ U}= {D1,D2,··· ,Dr} [x]D= {y ∈ U : (x, y) ∈ RD} ∀dl ∈ D x y ∈ Dk dl(x) = dl(y) Tk = {d1(Dk),d2(Dk),··· ,d|D|(Dk)} Dk (Dk ,Tk) 其中： ； 。如 ， ， 必有 ，显然属于同一决策类的对象具 有相同的决策值，记 为 的决策值。 称为决策概念。 (U,A,I,D, J) F = (U,A,I) FD = (UD,AD, ID) L(UD,AD,ID) (X,B) ∈ L(UD,AD,ID) 设 为决策形式背景，则由形式背 景 能够获得子形式背景 ，进一步可构造对象强加权概念格，记为 。称 为条件概念。 X、B |X ∩ Dk | |X| = 1 (X,B) ⇒ (Dk ,Tk) B ⇒ Tk 均为非空集合，如果有 ，则称 为决策形式背景的粒决策规则。 简记为 。 下面给出具体算法。 算法 2 粒决策规则获取算法 输入 (U,A,I,D, J) 输出 粒决策规则 1) compute L(FD) 2) ∀x, y ∈ U 3) for 1 ⩽ k ⩽ |D| do 4) if dk(x) = dk(y) then 5) (x, y) ∈ RD 6) end if 7) U/RD = {[x]D : x ∈ U}= {D1,D2,··· ,Dr} 8) end for (Dt 9) compute ,Tt) 10) for all (X,B) ∈ L(FD)，1 ⩽ t ⩽ r do |X ∩ Dt | |X| 11) if = 1 then (X,B) ⇒ (Dt 12) ,Tt) 13) end if 3 实验和分析 3.1 应用举例 F = (U,A,I) A = {a,b, c,d, e} 由表 1 给出人才市场大学生就业信息，处理 后构成形式背景 ，其中对象集为 6 位 求职者。属性集为 ，分别代表 5 个 属性，即应届生、数学专业、教师资格证、英语四 级、计算机二级。 表 1 形式背景 F = (U,A,I) Table 1 Formal context：F = (U,A,I) 序号 a b c d e 1 1 1 — — — 2 1 — — 1 1 3 1 1 1 — 1 4 1 — — — — 5 — 1 — — 1 6 1 1 — 1 — 1) 直接构造概念格 由表 1 给出的形式背景直接构造的概念格如 图 1 所示，共 12 个概念结点。 第 6 期 张晓鹤，等：基于信息熵的对象加权概念格 ·1099·