·1098· 智能系统学报 第15卷 变的情况下的属性约简方法。三支形式概念分 念，(X2,B2)是(X,B1)的父概念，记为 析20的提出丰富了概念格理论，魏玲和任睿思进 (X1,B1)≤(X2,B2) 一步研究了三支概念格的属性约简与决策规 另外，两个概念的上下确界定义分别为 则提取四。李俊余等2)研究了基于同余关系的不 (X1.B)V(X2,B2)=(g f(X1 UX2),BInB2) 协调决策形式背景的属性约简。 (X1,B)A(X2,B2)=(XinX2.fg(B:UB2)) 定义5设F=(U,A,D为形式背景，其中U 如何简化概念格结构，从而便于提取用户所 需信息是该领域的一个重要问题。上述研究中， {x,2,…,xn,x∈U,a∈A,则P(a/x)表示对象x提 往往默认形式背景中所有属性重要度是相同的， 供给属性a的平均信息量，即属性a的信息量为 然而在实际问题中，可能仅需针对特定属性进行 H(a)=-P(alx)log:P(alx) 数据挖掘，即不同属性的重要性是不同的。张继 福等通过对概念格的内涵引入权值，提出一种 信息熵值越大，表示对象集U具有该属性的 加权概念格，拓广了概念格的结构。张素兰等 不确定性越大，也即该属性的信息量越大，信息 在此基础上提出了一种基于信息熵和偏差分析的 嫡从平均意义上表示了属性的总体特性。 加权概念格的内涵权重获取方法。但上述两种加 2对象加权概念格 权概念格并没有考虑到对象权重的问题。 概念格需储存由形式背景获取的全部概念及 2.1对象权重及对象重要度偏差 属性间的偏序关系，使概念格构造过程变得异常 定义6设F=(U,A,)为形式背景，且U= 困难。同时随着大数据时代的到来，需要分析的 {,,…,xn,A={a1,a2,…,aml,每个属性：的权重 数据越来越多，如果想要将其中所有概念提取出 均已知，记为w(a)。 来，并根据概念间的偏序关系构成概念格，难度 x∈U,f)={a,a2,…,as,l,对象x的权重定 进一步加大。因此，如何删除无用的属性和对 义为 象，降低构造概念格的难度，使提取的规则更加 简洁就成为我们应该考虑的重要问题。本文通过 w() j=1 信息嫡给出单个属性权重后，进一步给出对象权 d(x)= 重和重要度偏差的定义，利用3个阈值对冗余数 通过定义6获取的对象权重能够反映该对象 据进行删除，缩小了概念格的规模，提高了构造 的总体信息量，但是却忽略了该结果可能存在偏 概念格的时间效率，并且能够让决策规则的提取 差，不利于获得具有一定偏差的信息。 过程更为简洁高效。 定义7对象x的重要度偏差定义为 1预备知识 1 D(x) t-1 (w(a,)-dx月 首先简单介绍形式背景中的相关知识。 由重要度偏差定义，特规定当t=1时，有 定义1设F=(U,A,)为形式背景，其中U= D(x)=0。 {,2,…,xn},A={a1,a2,…,am},IUXA。如果 通过定义对象权重和对象重要度偏差能够更 (x,a)∈I,则称x具有属性a。用PU表示U的幂 全面地考虑形式背景中隐含的知识。 集，PA)表示A的幂集。YX∈P(U),B∈P(4),定义： f)={a∈A:Vx∈X,(x,a)∈ 2.2对象加权概念格及其构造 g(B)={x∈U:Ya∈B,(x,a)eI 在无专家给定属性权重时，需通过信息嫡公 定义2设F=(U,A,)为形式背景，对于 式求出属性对应的信息量，再进行归一化处理获 USU,ASA,可以得到形式背景F=(U,A,), 得每个属性的权重。按照对象对于属性是否感兴 称为F的子背景，其中'=In(U×C)。 趣，给出属性权重阈值为a(0≤a≤1)，对于形式背 定义3设F=(U,A,D为形式背景，若二元 景F=(U,A,D上的任意属性aeA,如果w(a)<a, 组(X,B)∈P(U)×PA)能够满足fX)=B且g(B)=X, 则称该属性冗余。给定对象权重阈值为(0≤B≤)， 则(XB)称为形式概念或概念。其中，X称为外 对于形式背景(U,A,D上的任意对象x∈U,如果 延，B称为内涵。由形式背景(U,A,)构造的概念 (x)<B,则称该对象冗余。删除冗余概念及对象 格记为L(U,A,D。 获取的子形式背景记为F4=(U,Aa,),其构造的 定义4设(X1,B1),(X2,B2)EL(U,A,D,如果 概念格称为对象加权概念格。 X1二X2或者U2二U1则称X1,B)是(X2,B,)的子概 设对象重要度偏差阈值为6(0≤6≤1)，对于变的情况下的属性约简方法[19]。三支形式概念分 析 [20] 的提出丰富了概念格理论，魏玲和任睿思进 一步研究了三支概念格的属性约简[21] 与决策规 则提取[22]。李俊余等[23] 研究了基于同余关系的不 协调决策形式背景的属性约简。 如何简化概念格结构，从而便于提取用户所 需信息是该领域的一个重要问题。上述研究中， 往往默认形式背景中所有属性重要度是相同的， 然而在实际问题中，可能仅需针对特定属性进行 数据挖掘，即不同属性的重要性是不同的。张继 福等[24] 通过对概念格的内涵引入权值，提出一种 加权概念格，拓广了概念格的结构。张素兰等[25] 在此基础上提出了一种基于信息熵和偏差分析的 加权概念格的内涵权重获取方法。但上述两种加 权概念格并没有考虑到对象权重的问题。 概念格需储存由形式背景获取的全部概念及 属性间的偏序关系，使概念格构造过程变得异常 困难。同时随着大数据时代的到来，需要分析的 数据越来越多，如果想要将其中所有概念提取出 来，并根据概念间的偏序关系构成概念格，难度 进一步加大。因此，如何删除无用的属性和对 象，降低构造概念格的难度，使提取的规则更加 简洁就成为我们应该考虑的重要问题。本文通过 信息熵给出单个属性权重后，进一步给出对象权 重和重要度偏差的定义，利用 3 个阈值对冗余数 据进行删除，缩小了概念格的规模，提高了构造 概念格的时间效率，并且能够让决策规则的提取 过程更为简洁高效。 1 预备知识 首先简单介绍形式背景中的相关知识。 F = (U,A,I) U = {x1, x2,··· , xn} A = {a1,a2,··· ,am} I ⊆ U × A (x,a) ∈ I x a P(U) U P(A) A ∀X ∈ P(U) B ∈ P(A) 定义 1 设 为形式背景，其中 ， ， 。如果 ，则称 具有属性 。用 表示 的幂 集， 表示 的幂集。 ， ，定义： f(X) = {a ∈ A : ∀x ∈ X, (x,a) ∈ I} g(B) = {x ∈ U : ∀a ∈ B, (x,a) ∈ I} F = (U,A,I) U ′ ⊆ U A ′ ⊆ A F ′ = (U ′ ,A ′ ,I ′ ) F I ′ = I ∩(U ′ ×C ′ ) 定 义 2 设 为形式背景，对于 ， ，可以得到形式背景 ， 称为 的子背景，其中 。 F = (U,A,I) (X,B) ∈ P(U)× P(A) f(X) = B g(B) = X (X,B) X B (U,A,I) L(U,A,I) 定义 3 设 为形式背景，若二元 组 能够满足 且 ， 则 称为形式概念或概念。其中， 称为外 延， 称为内涵。由形式背景 构造的概念 格记为 。 (X1,B1) (X2,B2)∈ L(U,A,I) X1 ⊆ X2 U2 ⊆ U1 (X1,B1) (X2,B2) 定 义 4 设 ， ，如果 或者 则称 是 的子概 念， (X2,B2) 是 (X1,B1) 的父概念，记为 (X1 ,B1) ⩽ (X2 ,B2) 另外，两个概念的上下确界定义分别为 (X1,B1)∨(X2,B2) = (g f(X1 ∪ X2),B1 ∩ B2) (X1,B1)∧(X2,B2) = (X1 ∩ X2, f g(B1 ∪ B2)) F = (U,A,I) U = {x1, x2,··· , xn} xi ∈ U a ∈ A P(a/xi) x a a 定义 5 设 为形式背景，其中 ， ， ，则 表示对象 提 供给属性 的平均信息量，即属性 的信息量为 H(a) = − ∑n i=1 P(a/xi)log2P(a/xi) 信息熵值越大，表示对象集 U 具有该属性的 不确定性越大，也即该属性的信息量越大，信息 熵从平均意义上表示了属性的总体特性。 2 对象加权概念格 2.1 对象权重及对象重要度偏差 F = (U,A,I) U = {x1, x2,··· , xn} A = {a1,a2,··· ,am} ai w(ai) 定义 6 设 为形式背景，且 ， ，每个属性 的权重 均已知，记为 。 ∀x ∈ U f(x) = {as1 ,as2 ,··· ,ast ， } ，对象 x 的权重定 义为 d(x) = ∑t j=1 w (asj ) t 通过定义 6 获取的对象权重能够反映该对象 的总体信息量，但是却忽略了该结果可能存在偏 差，不利于获得具有一定偏差的信息。 定义 7 对象 x 的重要度偏差定义为 D(x) = vt 1 t−1 ∑t j=1 (w (asj )−d(x))2 t = 1 D(x) = 0 由重要度偏差定义，特规定当 时，有 。 通过定义对象权重和对象重要度偏差能够更 全面地考虑形式背景中隐含的知识。 2.2 对象加权概念格及其构造 α 0 ⩽ α ⩽ 1 F = (U,A,I) a ∈ A w(a) < α β 0 ⩽ β ⩽ 1 (U,A,I) x ∈ U d(x) < β Fd = (Ud,Ad,Id) 在无专家给定属性权重时，需通过信息熵公 式求出属性对应的信息量，再进行归一化处理获 得每个属性的权重。按照对象对于属性是否感兴 趣，给出属性权重阈值为 ( )，对于形式背 景 上的任意属性 ，如果 ， 则称该属性冗余。给定对象权重阈值为 ( )， 对于形式背景 上的任意对象 ，如果 ，则称该对象冗余。删除冗余概念及对象 获取的子形式背景记为 ，其构造的 概念格称为对象加权概念格。 设对象重要度偏差阈值为 δ ( 0 ⩽ δ ⩽ 1 )，对于 ·1098· 智 能 系 统 学 报 第 15 卷