经典-经典变精度概念格的一种属性约简

李同军, 徐珍珍, 吴明瑞, 杨晓平

(1.浙江海洋大学 信息工程学院, 浙江 舟山 316022;2.浙江海洋大学 浙江省海洋大数据挖掘与应用重点实验室, 浙江 舟山 316022)

德国数学家Wille教授提出的形式概念分析(FCA)理论是用于数据分析和知识处理的一种有效方法,已经被广泛地应用于数据挖掘、知识工程、信息检索、软件工程等许多方面[1-6]。 形式背景是FCA中数据的基本框架,它包括一个对象集、一个属性集以及两者之间的一个二元关系。每个形式概念由一个对象子集和一个属性子集组成,所有形式概念形成一个完备格,即概念格。因此概念格是形式背景中数据知识的一种表现形式,其明确、简洁的数学结构为其实际应用提供了极大的便利。概念格理论的研究主要集中在概念格构造、规则提取、属性约简及应用等方面[7-12]。其中,概念格知识约简是FCA的一个重要研究方向,主要包括概念约简、属性约简和对象约简,其中属性约简是较为重要的研究领域[13-14]。张文修等在格同构意义下研究了概念格的属性约简[15]。

形式模糊背景是经典形式背景在模糊集意义下的一种推广,其主要特征是经典形式背景中对象集和属性集之间的二元经典关系变成了二元模糊关系。Burusco和Gonzalez首次将模糊集引入形式概念分析[16]。近年来,在利用模糊逻辑推理和模糊集理论拓展模糊形式概念分析研究方面取得了一定的成果。在剩余格的基础上,Belohlavek等在形式模糊背景中提出了形式模糊概念格,研究表明提出的模糊概念格具有经典概念格的几乎所有性质[17-19]。Krajic和Yahia 等独立地提出了单边模糊概念格,单边模糊概念的外延和内涵,一个是经典集,一个是模糊集[9, 20]。Zhang 等提出了变精度概念格,定义了4种类型的变精度概念[21]。在此基础上,Shao等给出了变精度概念格在减少属性和减少对象意义下的知识约简方法,并研究了粒约简等问题[22-23]。Mao和Miao用图理论给出了模糊-经典概念格保持交不可约元的属性约简方法[24]。Shi和Yang研究了模糊-经典概念格保持属性粒不变的对象约简[25]。Lin等定义了布尔矩阵和粒度矩阵,据此给出了一种形式模糊背景的粒度约简方法[26-27]。

与经典形式背景相比,形式模糊背景的知识约简研究具有更大的难度。本文针对张文修等提出的变精度概念格[21]提出一种经典-经典变精度概念格的属性约简,使得约简既能简化形式模糊背景中一类确定性规则的形式表示,又能保持规则的性能不变,同时对属性约简的判定、核心属性的特征刻画做了研究,最后通过引入辨识属性的概念,给出一种属性约简的方法。

1 预备知识

1.1 伽罗瓦连接和剩余格

(LU,⊆)是一个偏序集。

显然,这里“≤”是L(f,g)上的一个偏序关系。

这时,称L(f,g)为概念格。

定义3[21]称L=(L,∧,∨,⊗,→,0,1)是一个剩余格,如果L满足以下条件:

1) (L,∧,∨,0,1)是具有最小元素0和最大元素1的格；

2) (L,⊗,1)是交换幺半群；

3) (⊗,→)是L中的伴随对,

即

a≤(b→c)⟺a⊗b≤c。

剩余格(L,∧,∨,⊗,→,0,1)中的算子→称为剩余蕴涵,它满足下列基本性质[29]:a,b,c∈L,{ai,i∈J}⊆L,{bj,j∈J}⊆L,

(L1) 二元运算⊗关于两个变量都是单调递增的;

(L2) 剩余蕴涵→关于左变量单调递减,关于右变量单调递增;

(L3)b→c=∨{a∈L|a⊗b≤c};

(L4) 1→a=a,a→b≥b;

(L5)a→b=1⟺a≤b;

(L6) (a⊗b)→c=a→(b→c)=b→(a→c);

(L9)a⊗(a→b)≤b,b≤a→(a⊗b),

a≤(a→b)→b。

在下文,假设剩余格为

L*=([0,1],∧,∨,⊗,→,0,1),

即其支撑集为[0,1]。

L*中常见的伴随对(⊗,→)有以下几种[28]:

1) (Lukasiewicz结构)

a⊗b=max{a+b-1,0},

a→b=min{1-a+b,1};

2) (Godel结构)

3) (乘积结构)

1.2 变精度概念格

由剩余格L*上剩余蕴涵→的性质(L4)可知

(1)

(2)

从式(1)和式(2)可以看出,定义5中的两个算子*δ与剩余蕴涵算子→的类型无关,也就是说,用不同类型的剩余蕴涵定义的X*δ和B*δ是分别相等的,而且容易验证下面性质成立。

2)X⊆X*δ*δ,B⊆B*δ*δ;

3)X*δ=X*δ*δ*δ,B*δ=B*δ*δ*δ;

5)X⊆B*δ⟺B⊆X*δ。

X*={a∈A|X⊆Ia}，X⊆U,

B*={x∈U|B⊆xI}，B⊆A。

其中,

xI={a∈A|(x,a)∈I},x∈U,

Ia={x∈U|(x,a)∈I},a∈A。

记(U,A,I)中所有概念组成的集合为L(U,A,I),或L(I)。记L(I)中所有概念外延构成的集合为Ext(U,A,I),或简记为Ext(I)。

(3)

对于B⊆A,容易验证

(4)

X*δ2⊆X*δ1,B*δ2⊆B*δ1。

证明只证一个不等式,另一不等式同理可证。下面只证X*δ2⊆X*δ1。

U={x1,x2,x3,x4},A={a,b,c,d,e},

表1 一个形式模糊背景

图 1 例1中的概念格

图2 例1中的概念格

2 规则提取与属性约简的定义

2.1 规则提取

其含义可解释为:对于x∈X,当且仅当x具有属性ai1,…,aik的程度都不低于δ。

(5)

2.2 属性约简的定义

对于一个经典形式背景(U,A,I),C⊆A,记IC=I∩(U×C),则称形式背景(U,C,IC)为(U,A,I)的子背景。记(U,C,IC)上的两个*算子为*C。

(6)

(7)

由命题5可得下面结论。

推论1设(U,A,I)是一个形式背景,若C⊂A,则对于X⊆U,都有X*C*C∈Ext(I)。

命题5和推论1说明,形式模糊背景和经典形式背景的子背景的概念的外延仍然是原背景中概念的外延。

表2 例3中的形式模糊子背景

图3 例3中的概念格

证明由式(3)可知只需证明,

对于X⊆U,有

故

3 属性约简

3.1 属性约简的判定

故C为关于D的δ0-协调集。

3.2 属性约简的方法

DS((X,B)δ)=D*δ-B,

称DS((X,B)δ)为(X,B)关于D的δ0-辨识属性集,简称辨识属性集。

表3 精度δ≥0.3的辨识属性集

(D*δ∩C)-(B∩C)=C∩(D*δ-B)=

C∩DS((X,B)δ)≠∅。

DS((X,B))={a}。

利用定理4不难证明下面结论成立。

∨(∧Ck)

则属性集C1,C2,…,Ck是关于D的全部约简。

∧(d∨e)∧e∧e∧e

利用逻辑运算的吸收律、分配律和交换律将上式恒等变形,可得

a∧d∧e,

故由定理6可知,精度0.3下关于D的约简只有一个, 即{a,d,e}。

4 结语

经典-经典变精度概念格是一种类型的变精度概念格,虽然经典-经典变精度概念在形式上与经典形式概念完全一样,但是它们却是来自于对象和属性间的模糊关系,不同阈值对应不同的经典形式概念。正是由于经典-经典变精度概念的外延和内涵都是经典集合,所以经典-经典变精度概念格在实际应用中更具优势。因此研究基于经典-经典变精度概念格的形式模糊背景的属性约简具有明显的理论意义和实际应用价值。本文研究了经典-经典变精度概念格的一种属性约简问题。提出了一种保持确定性规则的后件的语义不变的属性约简概念,研究了属性协调集的判定,给出了核心属性的特征刻画。基于粗糙集理论中辨识矩阵方法,构造了经典-经典概念的辨识属性集,进而定义了辨识函数,证明了依据辨识函数可以获得全部约简。同时结合示例解释了一些主要概念、结论和方法。