正在加载图片...
·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 卷
<<向上翻页向下翻页>>
©2008-现在 cucdc.com 高等教育资讯网 版权所有