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

第 26卷第 1期 大 学 数 学 Vo1．26，№ ．1 2010年 2月 C0LLEGE MATHEMATICS Feb．2O1O 利用矩阵行秩生成概念格的一种算法 毛 华 ， 杨 蕾 ， 窦林立。 (1．河北大学 数学与计算机学院，保定 071002； 2．河北满城中学，河北 满城 o72150； 3．中国地质大学 长城学院，保定 07lOOO) [摘 要]概念格是根据二元关系提出的一种概念层次结构，它描述 了对象和属性的关系，利用矩阵行秩 的层次思想提出了一种基于矩阵行秩的概念格生成算法 ，并用实例描述 了对 象和属性之间的概念关系． [关键词]概念 ；概念格 ；矩阵行秩 [中图分类号]TP181；O153．1 [文献标识码]A [文章编号]1672—1454(2010)01—0115一O3 1 引言与预备知识 形式概念分析是由德国的whi1e教授于 1982年提出的用数学的思维方式进行数据分析和知识处 理的有利工具．概念格的生成实际上是一个概念聚类过程．本文把矩阵看成形式背景利用矩阵行秩的概 念及概念格上的二元运算提出了一种基于矩阵行秩的概念格生成算法． 在形式概念分析中，数据是用形式背景来表示 的．下面给出它的形式化定义． 定义 1l】一1 一个形式背景就是一个三元组 (G，M ，)，这里 G和M 是集合 ，j G×M 为G和M 之 间的二元关系．G和M 的元素相应的被称为对象和属性．对于 gEG，mEM，(g， )E “表示对象 g具 有属性 ”． 对于 A G，B M ， A 一 {，，!∈M lVg∈A，(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。)∞A Az．此时称 (Az，B )为 (A ，B )的超概念 ，(A ，B )为 (Az，B )的子概念 ． (ii)设 (G，M，』)为一形式背景，显然它可以看作是一个 由0，1表示的矩 阵．对于某个属性 mEM， 在 (G，M ，J)的矩阵中，如果 7r／对应的列有 t个 1时 ，则称该属性 的秩为t，记为 r(m)=t．一max{r(rn)l m∈M}称为形式背景的秩． 引理 1 关系 “≤”可诱导出 口(G，M，j)的一个完备格结构 ，格 中元素满足 (A ，B1)V (A2，B2)一((B1nB2)，(BlnB2))， (A1，B )八(A ，B2)一 ((A nA )，(A nA ))， 其中(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)的真子概念． [收稿 日期]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(i