协调决策形式背景下概念格的属性约简

摘要：概念格是知识处理与分析中的一个有力工具，对它进行约简可以提高效率简化问题。该文在协调决策形式背景下给出了协调集及属性特征的判定定理，并在此基础上得到了一种求属性约简的方法。

关键词： 概念格；协调决策形式背景；协调集；属性约简

中图分类号：TP311文献标识码：A文章编号：1009-3044(2008)35-2225-03

Attribute Reduction in Consistent Decision Formal Context

LIU Ya-li

(School of Science,Kunming University of Science and Technoledge,Kunming 650093,China)

Abstract: The concept lattice is useful in knowledge processing and analyzing.By reducing lattice,it can get the process more efficiently and the work will be simpler.This paper gives the judgement theorems of consistent set and characters of attributes in consistent decision formal context and provides an algorithm to explore the reduction.

Key words: concept lattice;consistent decision formal context;consistent set;attribute reduction

1 引言

形式概念分析，也称概念格，是由Wille于1982年提出的[1]，它提供了一种支持数据分析的有效工具。概念格的每个节点是一个形式概念，由两部分组成：外延，即概念所覆盖的实例；内涵，即概念的描述，该概念覆盖实例的共同特征。另外，概念格通过Hasse图生动和简洁地体现了这些概念之间的泛化和特化关系。因此，概念格被认为是进行数据分析的有力工具。概念格理论已被广泛应用于知识工程、数据挖掘、信息检索、软件工程等领域[2-5]。

属性约简是知识发现研究的重要课题，所谓属性约简，就是针对不同的目的的要求，删除其中不相关或不重要的属性，使知识进行简化，又不丢失基本信息。文[6]提出了决策形式背景，本文基于决策形式背景讨论了协调集及属性特征的判定定理，得到了协调决策形式背景知识约简的一种方法。

2 基本概念

定义2.1[7] 称（U，A，I）为形式背景，其中U={x1,x2,...,xn}为对象集，每个xi（i≤n）称为一个对象；A={α1,α2,...,αm}为属性集，每个αj（j≤m）称为一个属性；I为U和A之间的二元关系，I⊆U×A 。若(x,α)∈I，则说x具有属性α，记为 xIα。

该文中，用1表示(x,α)∈I ，用0表示(x,α)∉I，这样形式背景就可以表示为只有0和1的表格。

对于X⊆U,B⊆A，定义运算：

,记{x}*为x*；，记{a}*为a*。若且，， 则称形式背景是正则的。本文所研究的形式背景都是正则的。

定理2.1[7]设（U，A，I）是形式背景，X1,X2,X⊆U和B1,B2,B⊆A，则：

定义2.2[7]设（U，A，I）为形式背景。如果一个二元组（X，B）满足X*=B且X=B*，则称（X，B）是一个形式概念，简称概念。其中X称为概念的外延，B称为概念的内涵。

用L（U，A，I）表示形式背景（U，A，I）的全体概念，规定：

容易证明“≤”是L（U，A，I）上的偏序关系。

若（X1，B1），（X2，B2）∈L（U，A，I） ，则

也是概念，从而L（U，A，I）是格。

定义2.3[8]设L（U1，A1，I1）和L（U1，A1，I1）是两个概念格，如果对于（X，B）∈L（U2，A2，I2）总存在（X'，B'）∈L（U1，A1，I1）使得X'=X ，则称L（U1，A1，I1）细于L（U1，A1，I1），记作L（U1，A1，I1）≤L（U2，A2，I2）。

在形式背景（U，A，I）下，，记，那么（U，D，ID）仍然是形式背景。对于运算，在（U，A，I）下仍用X*表示，在（U，D，ID）下用XD*表示，显然。

定义2.4[6]设（U，A，I），（U，Q，J）是两个形式背景，有形同的论域，则称（U，A，I，Q，J）为决策形式背景。若L（U，A，I）≤L（U，Q，J）称决策形式背景是协调的。若D⊆A ，有（U，D，ID）≤（L，Q，J）称D是决策形式背景的协调集，且不存在任何D的真子集是决策形式背景的协调集，称D为决策形式背景的约简集。

定义2.5 设协调决策形式背景（U，A，I，Q，J）的所有约简集为{Di|Di是约简，i∈τ}(τ是一指标集)，可将属性分为：

1) 绝对必要属性2) 不必要属性

推论2.1 α∈A是绝对必要属性⇔A-{α}不是协调集

推论2.2 α∈A是不必要属性⇔A-{α}是协调集

3 协调决策形式背景下协调集及属性特征的判定定理

引理3.1 设（U，A，I，Q，J）是协调决策形式背景，D⊂A，D≠Ф，则D是协调集当且仅当

证明：（⇐） L(U,A,I)≤L（U，Q，J） ,因此对∀（X，B）∈L（U，Q，J）一定有（X，X*）∈L（U，A，I）。由已知（X*∩D）*=（B**∩D）*=B*=X，因此（X，X*∩D）∈L（U，D，ID）,即L（U，D，ID）≤L（U，Q，J） ,所以D为约简集。

（⇒）假若D是协调集，即L（U，D，ID）≤L（U，Q，J）。因此对（F*，FQ**）∈L（U，Q，J）,存在E⊆D，（F*，E）∈L（U，D，ID），因此F*=E*。又E ＝（F*）D*=F**∩D，所以 （F**∩D）*=F

引理3.2 设（U，A，I，Q，J）是协调决策形式背景，D⊂A，D≠Ф。则D是协调集当且仅当∃E⊆D,E≠Ø , E*=F*。

证明：（⇒）由引理3.1即得。

（⇐）由已知，E*=F*，E⊆E**=F**，所以E⊆F**∩D，因此（F**∩D）*⊆E*=F*，又F**∩D⊆F**，所以（F**∩D）*⊇F***=F*，即得F**∩D=F*，由引理3.1，D为协调集。

引理3.3 设（U，A，I，Q，J）是协调决策形式背景，D⊂A，D≠Ф，则D是协调集当且仅当∀e∈Q，∃E⊆D,E≠Ø , E*=e*。

证明：（⇒）由引理3.2即证。

（⇐）对∀F⊆Q,F≠Ø，记F={ek:k∈τ}（τ为指标集）。由已知ek∈F⊆Q，∃Ek⊆D,Ek≠Ø , 使得Ek*=ek*。因此F*=ek*=Ek* ＝（Ek)*，令E=Ek，即对∀F⊆Q,F≠Ø， ∃E=Ek⊆Q使E*=F*。由引理3.2， D是协调集。

引理3.4 设（U，A，I，Q，J）是协调决策形式背景D⊂A，D≠Ф，则D是协调集当且仅当∀e∈Q， （e**∩D）*=e*

证明： （⇒）由引理3.1即证。

（⇐） 由已知e∈Q， （e**∩D）*=e*，记E=e**∩D则E⊆D，E≠Ф，且E*=e*，由引理3.3，D是协调集。

定理3.1设（U，A，I，Q，J）是协调决策形式背景，若∃e⊆Q，α∈e** ，且(e**-{α})*≠e* ，则α是绝对必要属性。

证明：若α是不必要属性，则A-{α}是协调集。那么，，即(e**-{α})*=e*，这与已知矛盾，所以α是绝对必要属性。

定理3.2设（U，A，I，Q，J）是协调决策形式背景，若∃e⊆Q，α∈e**，有(e**-{α})*=e*，则α是不必要属性。

证明：若α是绝对必要属性，则A-{α}不是协调集，那么，∃e∈Q，使，即(e**-{α})*≠e*，这与已知矛盾，所以α是不必要属性。

定理3.3设（U，A，I，Q，J）是协调决策形式背景，对于∀e∈Q ，有α∉e** ，这则α是不必要属性。

证明：若α是绝对必要属性，则存在约简集D使∀e∈Q ，，而α∉e** ，即，所以D-{α}为协调集，则与D使约简集矛盾！所以α是不必要属性。

4 一种求协调决策形式背景属性约简的算法

对于协调决策形式背景（U，A，I，Q，J）而言，若A中的每个元素均为绝对必要属性，则A即为一个约简。否则设存在Kil为A中的不必要属性，则A-{Ki1}为协调集，此时考察D=A-{Ki1}，如果D中每个元素均为协调决策形式背景（U，A，ID，Q，J）绝对必要属性，则D即为（U，A，I，Q，J）的一个约简。否则设Ki2∈D为D中的不必要属性，此时再考察D=D-{Ki2}=A-{Ki1,Ki2} ，重复上述过程，由于A使有限集，则总可以找到D⊆A ，D为约简集。基于此思想，我们可以得到如下求约简的一个算法。

int Amatrix[][]; //定义属性矩阵

int objCount;//对象个数

int propCount; //属性个数

bool isNecessaryProp[propCount]; //是否是必要属性矩阵

bool isNecessary(int prop[]);//定义是否是必要属性的子函数

main() //程序主函数

{

int i,j=0;

bool isNecessaryP;//判断某个属性是否为必要属性，是为true,否为false

for(i=0;i

{

isNecessaryP=isNecessary(Amatrix[][i]);

isNecessaryPropMatrix[i]=isNecessaryP;

}

for(i=0;i

{

if(isNecessaryPropMatrix[i])

{

hasNecessaryProp[j]=i;

j++;

}}

输出结果集(hasNecessaryProp[j]中存放了哪些是必要属性);

}

bool isNecessary(int prop[])//判断是否为必要属性的子函数，返回值为bool型，参数为属性列矩阵

{

int Qmatrix[][];//决策集

int Qcount;//决策集列数

int Qmatrix1[][];//Qmatrix*的结果集

int Qmatrix2[];//Qmatrix**的结果集

int i,j=0,k=0;

bool t=false;

for(i=0;i

{

if(Amatrix[对象obj的序号][i]==Qmatrix[对象obj的序号][i])

{

Qmatrix1[][j]=Amatrix[][i];

j++;

}

for(i=0;i

{

if(Amatrix[对象obj的序号][j]==true)

{

Qmatrix2[k]=对象obj的序号;

k++;

}

}}

for(i=0;i

{

if(Amatrix[][i]蕴涵在Qmatrix**中)

{

if(Qmatrix**-Amatrix[][i])*!=Qmatrix*

t=true;

} }

return t;

}

例：给出协调决策形式背景（U，A，I，Q，J），其中U={1,2,3,4} ，A={a,b,c,d,e,f} ，Q={g,h,k} （见下表）

我们对表所描述的协调决策形式背景求约简如下：α是A的不必要属性，则D=A-{α} ，b是D的绝对必要属性，则D不发生改变，c是D的不必要属性，则D=D-{c}=A-{a,c}，d是D的绝对必要属性，则D不发生改变，e是D的不必要属性，则D=D-{e}=A-{a,c,e}，f是D的绝对必要属性，则D不发生改变，从而D=A-{a,c,e}={b,d,f} 为协调决策形式背景（U，A，I，Q，J）的一个约简。

注：协调决策形式背景（U，A，I，Q，J）的约简可能不唯一，要求出其全部约简只需改变A中元素的排列顺序即可。

5 结束语

概念格理论是一种数据分析和知识处理的工具，已被成功应用于许多领域。本文给出了协调决策形式背景下的概念格协调集及属性特征的判定定理，并在此基础上得到了寻找约简的方法。

参考文献：

[1] Wille R.Restructuring lattice theory:an approach based on hierarchies of concepts [C]//IVAN R.Ordered Sets.Boston:Reidel,1982:445-470.

[2] Oosthuizen GD.The Application of Concept Lattice to Machine Learning [R] Technical Report,University of Pretoria,South Africa,1996.

[3] Ho T B.Incremental conceptual clustering in the framework of Galois lattie[A].in Lu H,Motoda H,Liu H,eds KDD:Techniques and Applications[C].World Scientific,1997,49-64.

[4] Kent R E,Bowman C M.Digital Libraries,Conceptual knowledge systems and the Nebula interface[R].University of Arkansas,1995.

[5]Corbett D,Burrow A L .Knowledge reuse in SEED exploiting conceptual graphs[A].International Conference on Conceptual Graphs(ICCS’96)[C].Sydney,1996,56-60.

[6] Wolff K E.A comceptual view of knowledge bases in rough set theory[C].Lecture Notes in Computer Science.Vol.2005,Spring-Berlin,2001:220-228.

[7] GanterB,Wille R.Formal Concept Analysis[M].MathematicalFoundations,Berlin:Springer,1999.

[8] 张文修,魏玲,祁建军.概念格的属性约简理论与方法[J].中国科学,2005,35(6).