利用矩阵行秩生成概念格的一种算法

《利用矩阵行秩生成概念格的一种算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第26卷第1期大学数学Vo1．26，№．12010年2月C0LLEGEMATHEMATICSFeb．2O1O利用矩阵行秩生成概念格的一种算法毛华，杨蕾，窦林立。(1．河北大学数学与计算机学院，保定071002；2．河北满城中学，河北满城o72150；3．中国地质大学长城学院，保定07lOOO)[摘要]概念格是根据二元关系提出的一种概念层次结构，它描述了对象和属性的关系，利用矩阵行秩的层次思想提出了一种基于矩阵行秩的概念格生成算法，并用实例描述了对象和属性之间的概念关系．[关键词]概念；概念格；矩阵行秩[中图分类号]TP181；O153．1[文献标识码]A[文章编号]1672—1454(2

2、010)01—0115一O31引言与预备知识形式概念分析是由德国的whi1e教授于1982年提出的用数学的思维方式进行数据分析和知识处理的有利工具．概念格的生成实际上是一个概念聚类过程．本文把矩阵看成形式背景利用矩阵行秩的概念及概念格上的二元运算提出了一种基于矩阵行秩的概念格生成算法．在形式概念分析中，数据是用形式背景来表示的．下面给出它的形式化定义．定义1l】一1一个形式背景就是一个三元组(G，M，)，这里G和M是集合，jG×M为G和M之间的二元关系．G和M的元素相应的被称为对象和属性．对于gEG，mEM，(g，)E“表示对象g具有属性”．对于AG，BM，A一{，，!∈MlVg∈A，(

3、g，)∈J}；B一{gEGlV711∈M，(g，m)∈j}．称(A，B)为(G，M，I)的一个概念，如果A一B，B一A_此时称A为(A，B)的外延，B为(A，B)的内涵．用p(C，M，J)表示(G，M，)的所有概念组成的集合．定义2L3(i)设(G，M，J)为一形式背景，(A，B)，(A，B。)∈口(G，M，I)，规定(A，B)≤(Az，B。)∞AAz．此时称(Az，B)为(A，B)的超概念，(A，B)为(Az，B)的子概念．(ii)设(G，M，』)为一形式背景，显然它可以看作是一个由0，1表示的矩阵．对于某个属性mEM，在(G，M，J)的矩阵中，如果7r／对应的列有t个1时，则称该属性

4、的秩为t，记为r(m)=t．一max{r(rn)lm∈M}称为形式背景的秩．引理1关系“≤”可诱导出口(G，M，j)的一个完备格结构，格中元素满足(A，B1)V(A2，B2)一((B1nB2)，(BlnB2))，(A1，B)八(A，B2)一((AnA)，(AnA))，其中(A，B)，(A，B。)为(G，M，J)的两个概念．称此完备格为(G，M，J)的概念格．为了下面定理叙述方便，给出如下定义：定义3设(G，M，)为一形式背景，(A1，B)，(A，B2)E口(G，M，工)，(A，B)<(A2，B2)~aAl(二二A．此时称(Az，B)为(A，B)的真超概念，(A，B)为(A，B)的真子概念

5、．[收稿日期]2007—06—13[基金项目]河北省教育厅基金(2oo6lo5)116大学数学第26卷2主要定理及算法本节主要是利用矩阵行秩的层次思想来构造概念格的生成算法．定理1设(G，M，j)为一形式背景，对于EM，r(m)===t，则(G，M，D中存在一个概念(A，B)，使得IAI—t．证当r()一t时恰有t个g使得(g，m)∈．令A一{gI(g，)EJ}．由定义1(ii)得A==={m)，从而({)，{))为(G，M，D的概念，其中l{)l—lAI—t，B一{}．定理2设(G，M，)为一形式背景，p(G，M，J)为(G，M，J)的概念格．令(A，B)Efl(G，M，D，则(A，B

6、)或者是存在m∈B，使得r(m)=lAl，且(A，B)一({}，{})，或者为(A，B)的两个真超概念的交集．证分两种情况完成证明．令lAl—t．情况1．如果有mEB使得r(m)一t，由定理1有({)，{})为概念．由mEB知VgEA，都有(g，)E，故有gE(m}，从而A{}．再由(}一fAI—t知A={}，故(A，B)一({}，{})．情况2．假设对VEB，r(m)≠lA1．因为(A，B)为一个概念，VmEB，gEA都有(g，)EJ，所以Ac{)．由情况1的证明知IAI≠{m}，所以lAI(=={m)t．由于fl(G，M，)为一个完备格，所以(A，B)必然可以表示成它的两个真超概念的

7、交集．即存在(A，B)，(A，B。)为(A，B)的两个真超概念，(A，B)一(A，B)^(A，Bz)一(AnAz，(A】NA2))．设(G，M，J)为一形式背景，由定理2知(G，M，J)上的任何概念(A，B)或者为M上的元素生成，或者由fl(G，M，D上的(A，B)的两个真超概念的交生成．由此可以给出概念格的一个生成算法．利用矩阵行秩生成概念格的一种算法．①第一层概念：(G，G)．②第二层概念：求形式背景(G，M，)的秩．n—max