926 电子学报 2014 年 [17] 的算法. 谢志鹏采用渐进式构造算法, 提出了树结构对概念格节点生成的作用, 有效的提高算法的效率.Tao Zhang [10] 提出形式背景的全新表示方法, 即属性拓扑表示法, 并将属性拓扑分解为子拓扑, 利用拓扑中属性对象的关联及关联强度来直接计算形式背景

Size: px

Start display at page:

Download "926 电子学报 2014 年 [17] 的算法. 谢志鹏采用渐进式构造算法, 提出了树结构对概念格节点生成的作用, 有效的提高算法的效率.Tao Zhang [10] 提出形式背景的全新表示方法, 即属性拓扑表示法, 并将属性拓扑分解为子拓扑, 利用拓扑中属性对象的关联及关联强度来直接计算形式背景"

亶邬
7 years ago
Views:

1 第 5 期 2014 年 5 月电子学报 ACTAELECTRONICASINICA Vol.42 No.5 May 2014 基于属性拓扑的可视化形式概念计算张涛 1, 任宏雷 1, 洪文学 2, 李慧 1 (1. 燕山大学信息科学与工程学院, 河北秦皇岛 ;2. 燕山大学电气工程学院, 河北秦皇岛 ) 摘要 : 形式概念计算是形式概念分析的重要研究内容之一. 本文提出一种利用属性拓扑进行概念计算的可视化算法. 该算法将属性拓扑以顶层属性为核心分解为若干子拓扑, 利用可视化全路径搜索得到当前子拓扑的所有概念, 进而得到该背景下的全概念集. 该算法使概念计算精准并易于实现. 关键词 : 形式概念分析 ; 属性拓扑 ; 全路径搜索 ; 可视化中图分类号 : TP18 文献标识码 : A 文章编号 : (2014) 电子学报 URL:htp:// DOI: /j.isn TheVisualizingCalculationofFormalConceptThat BasedontheAtributeTopologies ZHANGTao 1,RENHong lei 1,HONGWen xue 2,LIHui 1 (1.SchoolofInformationScienceandEnginering,YanshanUniversity,Qinhuangdao,Hebei066004,China; 2.SchoolofElectricalEnginering,YanshanUniversity,Qinhuangdao,Hebei066004,China) Abstract: Thecalculationofformalconceptsisaveryimportantpartinthetheoryofformalconceptanalysis.Thispaper proposesavisualizationalgorithm offormalconceptcalculationthatusedtheatributetopologyofformalcontext.thisalgorithm putsthetopatributesasthecorestodecomposethetopologyintosomesub topologies,getsaltheformalconceptsbythevisualiza tionfulpathsearchinginpresentsub topology,combinethemtogetafulsetofconceptsoftheformalcontext.throughtheanaly sisofthemethod,usingthefulpathsearchingofthesub topologytogetformalconceptsnotonlymakesthecalculationofformal conceptsimpleandeasytooperate,andwilnotresultinlostorredundantcomputingformalconcept. Keywords: formalconceptanalysis;atributetopology;fulpathsearching;visualization 1 引言 [1] 形式概念分析是对形式背景中属性对象及其关系进行分析和研究的理论, 其提供了一种与传统数据分析和知识表示完全不同的方法, 由德国的 WILLE 教授于 1982 年根据概念的哲学思想所提出 [2,3]. 目前形式概念分析的应用领域已经越来越广泛, 如软件工程 [4], 信息处理 [5], 知识发现 [6] [7], 数据挖掘等. 形式背景是形式概念分析的研究对象, 其表示方法除了经典的对象属性关系二元表和传统概念格外, 还包括属性偏序图 [8] 属性树 [9] [10] 属性拓扑等等. 其中, 形式概念的计算是各种表示方法研究的热点问题. 经过国内外学者多年研究, 目前已经从不同角度提出了多种形式概念的计算方法. 通常将概念格的计算方法分为批处理算法 [11,12], 增量算法 [13,14], 并行算法 [15,16], 快速渐进 [17] 式构造算法和基于属性拓扑的形式概念计算方法等. 其中, 批处理算法中较为典型的是 Bordat 的自顶向下算法 [11]. 该方法采用了递归计算, 可直观的表示概念格的构造, 并且有利于并行计算的实现. 但是由于过程中会产生节点的重复, 反而增大了运算量 ; 增量算法中比较典型的有 Godin 算法 [13]. 该方法将格中的节点分为不变节点更新节点和新增节点三类, 当插入一个新对象时, 只需要检查那些和新对象至少有一个相同属性的节点来判断其在格中应处的位置, 实现了格的构造速度的提升. 但是该算法需要对概念格的分支进行修整, 相对增加了算法的步骤和时间 ; 并行算法主要思想是将形式背景拆分为子形式背景构造子格后再进行相应的合并运算. 智慧来在文献 [15] 中基于概念格合并时不改变原有形式概念的父子关系原理, 对概念格的横向和纵向两个方面进行合并运算, 效率要高于单个形式概念插入收稿日期 : ; 修回日期 : ; 责任编辑 : 孙瑶基金项目 : 国家自然科学基金 (No ); 河北省自然科学基金 (No.F )

2 926 电子学报 2014 年 [17] 的算法. 谢志鹏采用渐进式构造算法, 提出了树结构对概念格节点生成的作用, 有效的提高算法的效率.Tao Zhang [10] 提出形式背景的全新表示方法, 即属性拓扑表示法, 并将属性拓扑分解为子拓扑, 利用拓扑中属性对象的关联及关联强度来直接计算形式背景的所有形式概念. 然而当前研究的方法普遍存在一些问题 : 经典的概念格计算复杂度较高且不能直观表示各属性间的关联强度 ; 属性偏序图揭示了数据的知识结构, 在大形式背景下可视性较好, 但目前尚没有利用其对形式概念进行计算的研究 ; 属性树表示法只能表示属性间的关系而不便于形式概念的计算 ; 属性拓扑能够直观的表示形式背景中各属性间的关联性及关联强度, 实现了形式背景表达与形式概念计算的统一. 但当前属性拓扑对概念的计算方法逻辑性较差且不适用大数据形式背景的形式概念计算. 本文在属性拓扑思想的基础上, 综合考虑形式背景的表示和形式概念计算问题, 结合增量算法思想提出基于属性拓扑的可视化形式概念计算方法. 本方法首先对属性拓扑进行分解, 以顶层属性为中心进行子拓扑的构造. 通过子拓扑的可视化表示, 以顶层属性为起点, 对子拓扑进行全路径搜索. 该算法可以简便的得到各个属性子拓扑中的所有形式概念, 并获得形式概念的直观计算过程. 属性子拓扑的全路径搜索计算过程中不会造成形式概念丢失或冗余, 简化了形式概念计算的过程. 2 形式背景的基本概念形式背景是形式概念分析的数据表示方式和处理对象, 以下介绍形式背景的相关定义 [1]. 定义 1 一个形式背景可以表示为 K:=(G,M, I), 是由两个集合 G 和 M 以及 G 与 M 间的关系 I 组成. 其中,G 为形式背景中的对象集合,M 为形式背景中的属性集合,I 表示 G 与 M 间的关系. 定义 2 设 K:=(G,M,I) 是一个形式背景, 若 A G,B M, 令 f(a)={m M g A,(g,m) I} 及 g(b)={g 0 G m B,(g 0,m) I} 如果 A,B 满足 f(a)=b,g(b)=a, 则我们称二元组 (A,B) 是一个形式概念.A 是形式概念 (A,B) 的外延,B 是形式概念 (A,B) 的内涵. 用 β (G,M,I) 或 β (K) 表示背景 K:=(G,M,I) 上的所有形式概念集合. 定义 3 形式背景的全局概念是指以该形式背景的所有属性为内涵, 对应的对象集为外延构成的形式概念 ( 称为全属性全局概念 ) 或者以所有的对象为外延, 对应的属性集为内涵构成的形式概念 ( 称为全对象全局概念 ). 形式背景 K:=(G,M,I) 下的全局概念只有两个, 即 (G,f(G)) 和 (g(m),m). 3 属性拓扑的构造与性质 3 1 形式背景的预处理属性拓扑主要分析形式背景中属性之间的关系, 其计算复杂度将随形式背景中的属性和对象数目增长而增长. 因此, 在不损失信息的情况下对形式背景进行预处理, 其主要目的是对形式背景中的属性和对象数目进行净化表示, 以降低后期计算复杂度. 定义 4 全局属性是指形式背景中全部的对象均包含的属性. 在形式背景 K:=(G,M,I) 中, 若有 m M 且 g(m)=g, 则属性 m 称为该形式背景中的一个全局属性. 与之对应, 全局对象, 是指具有形式背景中全部属性的对象. 全局属性定义为起点属性, 全局对象定义为终点对象. 定义 5 空属性, 是指形式背景中不属于任何对象的属性. 在形式背景 K:=(G,M,I) 中, 若有 m M 且 g(m)=, 则对象 g 称为该形式背景中的一个空对象. 与之对应, 空对象是指在该形式背景中不包含任何属性点对象. 空属性定义为终点属性, 空对象定义为起点对象. 依据格理论可知, 全局对象与全局属性不会对概念格的结构产生影响, 对于概念计算是可约简的. 从信息论的角度看, 全局对象与全局属性的相关运算包含所有属性或对象, 不具有区分特性. 空对象与空属性是不与任何其他的对象属性产生关联的独立存在, 对形式概念的计算过程也不产生影响. 因此, 运算时这四类属性对象可暂不作考虑. 定义 6 等价属性, 是指在形式背景下, 两个属性所属的对象集均一致. 同样, 等价对象是指在形式背景下, 两个对象所包含的所有属性集相等. 等价属性与等价对象均符合形式背景的净化条件, 在计算时可合并. 对于形式背景 K:=(G,M,I), 如果任意两个满足 f(g)=f(h) 的元素 g,h G 都有 g=h, 且对偶的任意两个满足 g(m)=g(n) 的元素 m,n M 都有 m=n, 称该形式背景是净化的. 下面结合一个典型的形式背景做分析, 这个形式背景中包含了属性间的相容包含互斥和互补等各种关系以及全局属性空属性和等价对象等特殊情况. 其具体内容如表 1 所示. 显然, 在这个形式背景中, 属性 a 为全局属性 ( 即起点属性 ), 属性 j 为空属性, 对象 8 与对象 9 出现了信息的重复 ( 即为等价对象 ). 因此首先需要进行形式背

3 第 5 期张涛 : 基于属性拓扑的可视化形式概念计算 927 景净化, 去除冗余信息. 净化后的形式背景如表 2. 为描述简便, 若不作特殊声明, 下文中提到的所有形式背景均为净化背景. 表 1 典型形式背景 a b c d e f g h i j 1 x x x 2 x x x x 3 x x x x x 4 x x x x x 5 x x x x 6 x x x x x 7 x x x x 8 x x x x 9 x x x x 表 2 表 1 的净化后形式背景 b c d e f g h i 1 x x 2 x x x 3 x x x x 4 x x x x 5 x x x 6 x x x x 7 x x x 8 x x x 3 2 属性拓扑的生成与表示从图论角度看, 属性拓扑表示是关于属性间关系的加权图表示. 因此在存储上可以借鉴图的存储方式. 在文献 [10] 中, 从属性包容的角度对属性拓扑进行了邻接矩阵描述. 形式背景 K:=(G,M,I) 中, 定义 T=(V,E) 为属性拓扑的表示. 其中 V=M 为拓扑的顶点集合,E 为邻接矩阵, 表示拓扑中边的权值集合. m i, 当 i=j 时, 当 m i m j = (i j) E(v i,v j )=, 当 m i m j =m i (i j) m i, 当 m i m j =m j (i j) m i m j, 其他 (1) 式 (1) 中, 当 i=j 时,E(v i,v j ) 为属性 m i 所属对象集 ; 当 m i m j = (i j) 时,m i 与 m j 互斥, 此时 E(v i, v j )= ; 当 m i m j =m i (i j) 时,m i 包含于 m j, 拓扑中表现为由顶点 m i 不能到达顶点 m j ( 式中表示为 E(v i,v j )= ), 而由顶点 m j 却能到达顶点 m i ; 当 m i 和 m j 为相容关系时,E(v i,v j )=m i m j. 在本文中, 为便于利用属性拓扑进行形式概念计算, 对文献 [10] 的邻接矩阵方法进行精简并提出关联矩阵表示. 精简后属性拓扑的邻接矩阵表达式如式 (2) 所示 : {, g(m i )-g(m j )= E(v i,v j )= 或 g(m i )-g(m j )=g(m i ) g(m i ) g(m j ), 其他 (2) 定义 T=(V,E ) 为属性拓扑的表示, 其中 V=M 为拓扑中的顶点集合,E 为关联矩阵, 表示拓扑中边的走向, 如式 (3) 所示 : { -1, g(m i )-g(m j )= E (v i,v j )= 0, g(m i )-g(m j )=g(m i ) (3) 1, 其他在式 (2) 与式 (3) 中, 当 g(m i )-g(m j )=g(m i ) 时, 包含两种情况 : (i)g(m i ) g(m j )=, 即 m i 与 m j 二者不相关, 图中表示为二者间没有直接相连的边. (i)g(m j )=, 显然, 符合背景净化条件, 在预处理中被净化掉, 该情况不可能出现. 当 g(m i )-g(m j )= 时, 包含三种情况 : (i)g(m i )=, 符合形式背景的净化条件, 这种情况不可能出现. (i)g(m i )=g(m j ), 符合被净化的条件, 不可能出现. (i)g(m i ) g(m j ),m i 为 m j 的伴生属性. 其他, 即 {g(m i )-g(m j )} (,g(m i )), 此时 g(m i ) 与 g(m j ) 间的交集既不为空集又不为 g(m i ), 包含两种情况 : (i)g(m i ) g(m j ),m j 为 m i 的伴生属性. (i) 属性 m i 与 m j 为互不包含属性, 即为相容关系. 综上,g(m i )-g(m j )=g(m i ) 即表示属性 m i 与 m j 间为互斥关系,g(m i )-g(m j )= 表示属性 m i 与 m j 间为包含关系, 其他则表示在图中与属性 m i 直接相连的边均为单向指出边或双向边. 由式 (2) 与式 (3) 可得, 表 2 对应的邻接矩阵和关联矩阵分别为 E(v i,v j ) 和 E (v i,v j ):

4 928 电子学报 2014 年 {1,2,3,5,6} {3,6} {5,6} {5,6} {1,2,3} {2,3} {3,6} {3,4,6,7,8} {6,7,8} {7} {6,8} {3,4} {3,4} {4} {5,6} {6,7,8} {5,6,7,8} {7} {5,6,8} {7} E(v i,v j )= {5,6} {6,8} {5,6,8} {1,2,3} {3,4} {1,2,3,4} {2,3,4} {4} {2,3} {3,4} {2,3,4} {4} {4 } 性. 为了形式概念计算的需要, 本文引入伴生属性定义, 并分析其性质定义 8 在 K:=(G,M,I) 中,m i M. 若存在集合 N, 对于 m j N,N M -m i, 且都满足 g(m i ) E (v i,v j )= g(m j ), 则属性 m i 为属性 m j 的伴生属性性质 1 在形式背景中, 可能存在 A M, 使得任意 a i A 均满足 g(m) g(a i ). 即属性 m 可以为多个属性的伴生. 已知形式背景, 由式 (2) 式 (3) 分别得到其邻接矩阵性质 2 伴生属性中,E(v i,v j )= 且 E (v i,v j ) 和关联矩阵.T 的属性集合作为拓扑的顶点集合, 按照 =-1. 即在属性拓扑中, 与伴生属性相连的边中至少关联矩阵画各属性间的边及其走向, 按照邻接矩阵的值存在一条单向指入边. 标注属性间的耦合关系. 对于与伴生属性相连的双向证明 : 由伴生属性的定义可知, 若属性 m i 为属性边, 图中用虚线表示, 以表明二者不能直接关联. 据此, m j 的伴生属性, 则 g(m i ) g(m j ), 即 E(v i,v j )=, 且可得到属性拓扑的图表示. 表 2 的属性拓扑如图 1 所示. E(v j,v i ), 也就是 E(v j,v i ) 是 m i 的一条单向指入边. 证毕定义 7 属性拓扑中的完全多边形是指多边形的每对顶点间都有一条边直接关联, 关联形式可以为单向边或双向边. 定理 1 形式背景 K:=(G,M,I) 中, 若满足 g(m i ) g(m j ),(i T,j T), 则在属性拓扑中 M T = {m i m i M} 必定为完全多边形. 证明 : 设 i T,j T, 若 g(m i ) g(m j ) 且 M T ={m i m i M} 为非完全多边形. 则在 M T 所属的拓扑图中, 一定存在两个属性 m a 与 m b 无直接关联, 即属性 m a 与 m b 为互斥关系, 即 g(m a ) g(m b )=. 此时与题设相矛盾. 因此, 命题得证. 证毕 3 3 基于拓扑的属性分类及其性质文献 [10] 中定义了顶层属性, 过渡属性和底层属性质 3 属性 m i 可以是属性 m j 的伴生, 即属性 m i 与属性 m j 之间为包含关系, 同时也可以是属性 m k 的互不包含属性, 即属性 m i 与属性 m k 之间为相容关系. 证明 : 在 K:=(G,M,I) 中,m i M. 显然可以存在 m j M,m k M, 满足 g(m i ) g(m j ), 同时满足 g(m i ) g(m k ),g(m i ) g(m k ),g(m k ) g(m i ). 即伴生属性同时也可以与其它属性互不包含. 证毕性质 4 属性 m i 可以为多重伴生属性. 定义 9 形式背景 K:=(G,M,I) 中若存在 g(m i ) g(m j ) g(m k ), 则属性 m i 称为属性 m k 的多重伴生属性, 记为 m i =B(m k ). 性质 5 顶层属性必不是伴生属性. 证明 : 对于伴生属性 m i M, n M-m i, 都满足 g(m i ) g(n). 显然与顶层属性的定义相矛盾. 因此顶层属性一定不是伴生属性. 证毕性质 6 顶层属性在拓扑图中表现为与之相连的边只有单向指出边和双向边, 不存在单向指入边. 证明 : 由定义可知, 顶层属性 m j 对任意的 E(m i, m j ), 都有 E(m j,m i ), 即不存在满足 E(m i, m j ), 同时 E(m j,m i )=, 条件的属性 m i. 因此不存在单向指入边. 证毕定义 10 若底层属性同时也是多重伴生属性, 则

5 第 5 期张涛 : 基于属性拓扑的可视化形式概念计算 929 称 m i 为最小伴生属性. 性质 7 过渡属性可能为伴生属性, 但不能是最小伴生属性. 证明 : 由过渡属性 m i 的定义, 与之相邻的边中, 可能存在 E(m k,m i ),i k, 使 E(m i,m k )=, 即 m i 存在单向指入边, 因此过渡属性可能为伴生属性. 同时, 与过渡属性相邻边中一定至少存在一个 E(m i,m j ),i j, 即 m i 存在指出边, 因此过渡属性不可能为最小伴生属性. 证毕显然, 图 1 中属性 b,c,d,g 为顶层属性 ; 属性 f,h 为过渡属性 ; 属性 e,i 为底层属性, 同时也是最小伴生属性 ; 属性 e,f,h,i 为伴生属性 ; 其中属性 i 为多重伴生. 4 子拓扑的可视化形式概念计算 4 1 拓扑的分解与子拓扑的构造属性拓扑的分解以顶层属性为中心, 其目的是为了减少不必要步骤, 简化形式概念的计算. 根据属性拓扑中各属性类别及其之间的关系, 可判断是否可分解为子拓扑. 下面是三种不可分解的情形 : (1) 若属性拓扑中只包含一个顶层属性, 则该拓扑不可分解. (2) 若属性拓扑为完全多边形, 则该拓扑不可分解. 证明 : 设形式背景的属性拓扑中, 有对于 i j, 有 E(m i,m j ) E(m j,m i ), 则以 T=(V,E) 中的一个顶层属性 m 0 为中心的子拓扑 subt 0 =(subv 0,subE 0 ) 中, 顶点属性集为 subv 0 =V=M, 与之对应的 G 0 =G, 子拓扑中各边的对应权值为 sube 0 (m i,m j )=E(m i, m j ),sube 0 (m j,m i )=E(m j,m i ), 其中 m i,m j M, 因此, 可以得到 subt 0 =T, 即, 原属性拓扑不可分解. 证毕 (3) 若属性拓扑非完全多边形, 但顶层属性间两两相关, 则该拓扑不可分解. 证明 : 设形式背景 K:=(G,M,I) 的属性拓扑为 T =(V,E), 假设任意一个顶层属性 m i 相连的边都满足 E(m i,m j ), j i, 则以 m i 为中心的子拓扑 subt i =(subv i,sube i ) 中, 顶点属性集为 subv i =V=M, 与之对应的 G i =G, 子拓扑中各边的对应权值为 sube i (m k, m j )=E(m k,m j ),sube i (m j,m k )=E(m j,m k ), 其中 m k,m j M, 因此, 可以得到 subt i =T, 即, 原属性拓扑不可分解. 证毕设形式背景 K:=(G,M,I) 可分解, 其属性拓扑中的顶层属性的个数为 n, 则子拓扑数最多也为 n. 拓扑的分解与子拓扑的构造步骤如下 : Step1 选点. 自顶点属性集中选取出度最小的顶层属性 m 为子图的中心属性. Step2 构图. 在属性拓扑图的剩余部分中, 将与属性 m 之间关联的属性作为属性 m 为中心子图的顶点集, 记为 subv. Step3 清理. 对于多重伴生属性 m 0 =B(a i ), 若 a i subv, 则删除顶点 m 0. Step4 画边. 对于 step3 整理后子图顶点集 subv, 取原拓扑中这些顶点间的边集作为子图边集. 即 sube ={(v i,v j ) v i subv,v j subv}. 对于与伴生属性相连的双向边, 用虚线表示. Step5 整理. 在原拓扑中, 删除顶点 m 及其相关边, 并将 m 从顶点属性集移除, 若此时顶点属性集为空, 则停止运算, 否则进行 step1. 该过程的构造流程图如图 2 所示. 由上述属性拓扑的分解和子拓扑的构造步骤, 可得图 1 的属性子拓扑如图 3 所示. 4 2 基于属性拓扑的形式概念计算由属性拓扑的构造可知, 其包含了背景中所有属性对间的关联及其关联强度, 而子拓扑的分解过程并没有破坏形式概念计算所需关联. 因此属性拓扑的形式概念计算定理在属性子拓扑中同样成立.

6 930 电子学报 2014 年引理 1 属性拓扑的全路径搜索可计算全模式集合. 证明 : 属性拓扑 T=(V,E) 中,V=M 为拓扑的顶点集合,E 为拓扑中边的集合, 其中边的权值可按式 (1) 得到, 即属性拓扑中包含了形式背景中所有的属性及各属性间关于对象的关联强度. 而搜索过程中若下一个到达的属性为 m i, 路径上已经经过的属性集为 M i, 将计算 g(m i ) g(m i ). 若 g(m i ) g(m i ), 则存储 ((g(m i ) g(m i )),(m i M i )), 并进行下一步. 如此搜索完整体属性拓扑, 得到的便是图中所有属性间的所有关联, 其对应的对象集就是其所有的关联强度. 于是二者构成的二元组, 即为属性拓扑的全模式集合. 证毕定理 2 利用属性拓扑的全路径搜索算法可以得到形式背景的所有形式概念, 并且不会产生伪概念. 证明 : 由引理 4.1 可知, 属性拓扑的全路径搜索可得到形式背景的全模式集合, 包括了所有的形式概念. 在搜索过程中若存在集合 K {M-{m i,m t }}, 其中 m i 为顶层属性,m t 为与 m i 直接关联的其中一个属性, 可使得 (g(m i m t ),m i m t K), 则将上一步所存储的 (g(m i m t ),m i m t ) 更新为 (g(m i m t ),m i m t K). 更新过程消除了伪概念产生的条件. 故属性拓扑的全路径算法可得到形式背景的所有概念, 且不会产生伪概念. 证毕属性拓扑的分解过程中, 在选点和构图步骤里都体现了全拓扑与子拓扑的一致性, 不会造成与形式概念相关的属性对象关联丢失. 因此, 对子拓扑全局搜索同样可以得到子拓扑中的所有形式概念, 而不会产生伪概念. 4 3 算法描述利用上述得到的子拓扑进行形式概念计算. 设子拓扑分别为 subt(v 1,E 1 ),subt(v 2,E 2 ),,subt(v n, E n ). 在得到子拓扑中, 设 M 为子拓扑的全部属性集. 其顶层属性集为 {A m i A}, 最小被包含属性集为 {B m j B}. 利用图的全路径搜索原理, 分别以集合 A 中的各 m i 为起点, 以集合 B 中的各 m j 为终点, 作全路径搜索. 若图中 B=, 则直接对集合 M 中的各属性进行全路径搜索. Step1 取与顶层属性 m i 直接关联的 m t, 存储 (g(m i m t ),m i m t ). Step2 若 K {M-{m i,m t }}, 使得 g(m i m t )= g(m i m t K), 则将上一步所存储的 (g(m i m t ),m i m t ) 将更新为 (g(m i m t ),m i m t K). Step3 若 n {M-{m i,m t }}, 都有 g(m i m t ) g(m i m t n), 则上一步存储不改变的情况下, 再存储 (g(m i m t n),m i m t n). Step4 判断与 m i 直接关联的属性是否全部搜索过. 若是, 则结束 ; 否则返回到 step1, 进行下一个属性 m r 的遍历. 对子拓扑 subt(v 1,E 1 ),subt(v 2,E 2 ),, subt(v n,e n ) 进行全路径搜索, 便可以得到各子拓扑中对应所有的形式概念集 β (subt(v 1,E 1 )), β (subt(v 2, E 2 )),, β (subt(v n,e n )). 该算法流程图如图 4 所示. 依据算法理论可知, 采用属性子拓扑方法进行可视化形式概念计算, 计算复杂度为 O(2 n ), 与目前主流方法复杂度相同. 依以上算法进行子图的遍历, 图 5 为遍历的过程示意图. 图 5 中, 每个节点代表遍历路径中所路过的属性集, 边为其路径, 权值为右侧节点属性集所属对象集, 其中实线边上的权值及其右侧属性集组成的二元组即为子拓扑中的形式概念, 虚线边连接的右侧属性集为伪内涵, 其在搜索过程中被内涵更新替代. 由图 5 的示意图可知 : d 为中心属性的子拓扑中 :(56,bdf),(6,bdcf), (678,cd),(7,cde),(68,cdf),(568,df). g 为中心属性的子拓扑中 :(123,bg),(3,bcgh), (23,bgh),(34,cgh),(4,cghi),(234,gh). b 和 c 为中心属性的子拓扑中 :(36,bc). 又由中心属性必为形式概念内涵 [10], 得到 :(5678, d),(1234,g),(12356,b),(34678,c). 进而直接得到了各子拓扑中的所有形式概念. 加上全局概念, 即 ( , ) 和 (,bcde

7 第 5 期张涛 : 基于属性拓扑的可视化形式概念计算 931 fghi), 得净化形式背景下的所有形式概念. 4 4 形式概念的原始形式背景恢复 4.3 节计算中得到净化形式背景下的所有形式概念, 而实际应用时需要的是净化前的原始形式背景下的形式概念. 于是, 对于形式概念的原始形式背景恢复也是必要步骤. 对于起点属性, 只需在每个形式概念的内涵直接做添加 ; 对于终点对象, 同样要在每个形式概念的外延直接添加这个对象. 而终点属性和起点对象, 由于与其他任何属性对象不产生关联, 则不需要在形式概念上做出表示. 对于等价属性与等价对象, 则需要直接将合并后的集合拆开, 分别作为内涵或外延中的元素. 如表 1 中的属性 a 为起点属性, 则在最后得到的所有形式概念的内涵集中, 均需要添加属性 a 为其元素 ; 属性 j 为终点属性, 只需在全属性全局概念的内涵中加上属性 j 作为全部内涵 ; 对象 8 与对象 9 为等价对象, 前文中用对象 8 代替了 {8,9}, 所以, 恢复时需要用对象 {8,9} 替换回对象 8. 于是得到全部形式概念的原始形式背景复原如下 : β (K)={(123,abg),(3,abcgh),(23,abgh),(34, acgh),(4,acghi),(234,agh),(36,abc),(56,abdf),(6, abdcf),(6789,acd),(7,acde),(689,acdf),(5689,adf), (56789,ad),(1234,ag),(12356,ab),(346789,ac), ( ,a),(,abcdefghij)}. 5 结论本文考虑形式背景拆分的思想, 以顶层属性为中心, 按照一定的规则纳入其他与顶层属性相关的顶点属性集, 将属性拓扑分解若干个子拓扑, 并结合增量算法思想, 以子拓扑中顶层属性为起点, 其他顶点属性为终点进行全路径搜索, 进而获得形式背景的所有形式概念. 该方法不仅使整个过程更具逻辑性和可操作性, 并且易于实现, 适用于大规模数据集. 相对于整体属性拓扑, 对分解后的子拓扑进行操作缩小了算法的搜索空间, 提高了运算效率, 降低了计算复杂度. 属性拓扑为形式背景提供了全新的表示方法, 下一步的工作将对本方法进行完善和优化, 并将之实现于应用领域. 参考文献 [1]GanterB,WileR.FormalConceptAnalysis:Mathematical Foundations[M].NewYork:Springer Verlag,1999. [2]Radim Belohlavek,ErikSigmund,JirřiZacpal.Evaluationof IPAQquestionnairessupportedbyformalconceptanalysis[J]. InformationSciences,2011,181(10): [3]TamT,Nguyen,SiuCheungHui,KuiyuChang.Alatice based approachformathematicalsearchusingformalconceptanalysis [J].ExpertSystemswithApplications,2012,39(5):5820-

8 932 电子学报 2014 年 [4]Tonela.Usingaconceptlaticeofdecompositionslicesforpro gramunderstandingandimpactanalysis[j].ieeetransactions onsoftwareengineering,2003,29(6): [5]FethiFerjani,SamirEloumi,AliJaoua,etal.Formalcontext coveragebasedonisolatedlabels:aneficientsolutionfortext featureextraction[j].informationsciences,2012,188(1): [6]Jin haili,chang linmei,yue jinlv.knowledgereductionin realdecisionformalcontexts[j].informationsciences,2012, 189(15): [7]MehdiKaytoue,SergeiO Kuznetsov,AmedeoNapoli,etal. Mininggeneexpresiondatawithpaternstructuresinformal conceptanalysis[j].informationsciences,2011,181(10): [8]Feng jiefan,wen xuehong,xinli,taozhang,xu long Liu,Wei dongchen,junjing.researchoncompatibilityof prescriptionoftcpbasedontheprincipleofatributepartial orderchart[a].proceedingsofthefirstinternationalconfer enceoninstrumentation,measurement,computer,communica tionandcontrol(imccc)[c].beijing:ieee, [9] 张涛, 洪文学, 路静. 形式背景的属性树表示 [J]. 系统工程理论与实践,2011,31(s2): ZhangTao,HongWen xue,lujing.atributetreerepresenta tionforformalcontext[j].systemsengineering Theory& Practice,2011,31(s2): (inChinese) [10]TaoZhang,Hong leiren,xiaominwang.a calculationof formalconceptbyatributetopology[j].icicexpresleters PartB:Applications,2013,4(3): [11]GanterB.FormalConceptAnalysis:AlgorithmicAspects[EB/ OL].htp:// dmsden.de/ ganter/cl02/, [12]Huai guofu.aparalelalgorithmtogenerateformalconcepts forlargedata[a].proceedingsofthesecondinternational ConferenceonFormalConceptAnalysis(ICFCA)[C].Berlin: Springer, [13]GodinR,MisaouiR,AlaouiH.Incrementalconceptforma tionalgorithmsbasedongalois(concept)latices[j].compu tationalinteligence,1995,11(2): [14]MerweDvander,ObiedkovS,KourieD.Addintent:A new incrementalalgorithm forconstructingconceptlatices[a]. ProceedingsoftheSecondInternationalConferenceonFormal ConceptAnalysis(ICFCA)[C].Berlin:Springer, [15] 智慧来, 智东杰, 刘宗田. 概念格合并原理与算法 [J]. 电子学报,2010,38(2): ZhiHui lai,zhidong jie,liuzong tian.theoryandalgo rithmofconceptlaticeunion[j].actaelectronicasinica, 2010,38(2): (inChinese) [16] 李云, 刘宗田, 陈, 徐晓华, 程伟. 多概念格的横向合并算法 [J]. 电子学报,2004,32(11): LiYun,LiuZong tian,chenling,xuxiao hua,chengwei. Horizontalunionalgorithm ofmultipleconceptlatices[j]. ActaElectronicaSinica,2004,32(11): (inChi nese) [17] 谢志鹏, 刘宗田. 概念格的快速渐进式构造算法 [J]. 计算机学报,2012,25(5): XieZhi peng,liuzong tian.afastincrementalalgorithm for buildingconceptlatice[j].chinesejournalofcomputers, 2002,25(5): (inChinese) 作者简介张涛男,1979 年 3 月生于河北省唐山市. 现为燕山大学副教授. 主要从事形式概念分析, 可视化模式识别等领域的研究. E mail:zhtao@ysu.edu.cn 任宏雷女,1989 年 4 月出生于河北省唐山市. 现为燕山大学信息科学与工程学院硕士研究生. 主要研究方向为形式概念分析, 拓扑理论. E mail:yuizhizao@163.com

标题

第 35 卷第期西南大学学报 ( 自然科学版 ) 3 年月 Vol.35 No. JouralofSouthwestUiversity (NaturalScieceEditio) Feb. 3 文章编号 :673 9868(3) 69 4 一类积分型 Meyer-KiḡZeler-Bzier 算子的点态逼近赵晓娣, 孙渭滨宁夏大学数学计算机学院, 银川 75 摘要 : 应用一阶 DitziaṉTotik