基于概念格因子分解的零件三维CAD模型检索

吴强 董雁 吴域西 谢丽萍

对于概念格来说,即使是一个小的数据集可能产生大量的形式概念[1].这是源于其存在高组合复杂性和结构.最坏的情况可以达到2min(|G|,|M|)(|G|,|M|分别为对象和属性的总数).此外,产生的形式概念的数量和概念之间关系的复杂性使得最终格的分析十分困难[2].

为简化概念格,现有的研究主要采用了知识约简的方法.所谓知识约简,就是针对不同的目的要求,保持知识库分类能力不变,删除其中不相关或不重要的属性,使知识表示简化的同时又不丢失基本信息.

已有研究者研究了从给定的二元形式背景[3]、决策形式背景[4−5]、模糊形式背景[6−7]、实决策形式背景[8]中约简生成形式概念.Dias和Vieira[9]提出了一种分析概念格约简的方法.它是基于存在于原始与约简后的形式背景,或概念格间的特有的蕴含集合的.通过这些蕴含集合,设计的约简方法能够显现数据信息的保持、消失、增加及变化.他们从方法论的角度分析了三类约简技术,强调了其在转换时的共同之处.Konecny[10]的研究表明,虽然有各种扩展,Ganter和Wille的概念格属性约简和解释依然是优于基于可辨识矩阵约简的.Singh等[11]提出了一种在形式概念分析中用模糊属性减少形式概念数目的方法.其以香农熵计算模糊形式概念的权重.用计算的权重选择粒约简模糊形式概念.结果表明,所提出的方法得到的结果与Levenshtein距离法以及区间值模糊形式概念的方法一致,但计算复杂度更低.因为是基于属性的,这些方法的结果很难直观地、易于理解地反映出对象— 属性关系(即形式概念)的重要程度.

就目前的结果来说,关注重要概念选择以至于对概念格进行分解的研究较为鲜见.Babin和Kuznetsov[12]引进了概念稳定性来测度概念的重要性.Belohlavek和Macko[1]利用权重研究了重要的概念并讨论其应用.Dias和Viera[13]提出基于连接的对象相似(JBOS)方法约简形式概念的数目.Li等[14]讨论了加权概念格及其应用.Kang等[15]提出一种在不同粒度下减少模糊概念格大小的方法.Li等[16]提出了一种采用K-medoids聚类来压缩近似概念格的方法.Martin等[17]提出一种使用Levenshtein距离测度模糊概念格的变化的方法.Singh等[18]推出了一个使用香农熵来计算给定模糊形式概念的权重的方法,选择根据所计算出来的权重的粒度约简模糊形式概念.Aswani等[19]新近提出了在形式背景上用非负矩阵分解约简知识,但仅提出了一个思想,对矩阵存在与约束条件尚无探讨.

将概念格与因子分析联系起来的是Keprt和Snášel[20].他们提出了基于形式概念分析计算非层次二元因子分析的方法.尽管计算概念格本身也是十分繁杂的,它仍然帮助加快了二元因子分析的计算.Belohlavek和Vychodil[21]提出了一个有序数据的矩阵分解和因子分析的方法.这些因子对应于输入数据的形式概念成为数量最少的因子,并可以十分简单的解释分解.

由于图能较好地描述三维CAD模型的几何、拓扑乃至语义信息,近年来基于图的模型表征和检索方法受到了更多关注[22−23].典型的用于CAD模型检索的工作有属性邻接图[24−27]、完全二分图[28]、扩展特征树[29]等描述子方法.这些基于图的检索方法尽管可以采用各种“图结构”较好地表征模型的几何、拓扑乃至语义信息,但最终都要通过繁琐的图匹配来实现对应模型间的相似性比较,十分复杂而耗时,因此这些检索方法效率很低.虽然有文献[24,27]对CAD模型用向量化表征在一定程度上可提高匹配和检索效率,但其只能表达模型的整体形状,当模型较大型且复杂时,其局部细节特征描述能力不足,局部特征信息不突出.检索精度和检索效率存在一定程度的矛盾.徐静等提出了一种基于装配结构相似的零件三维模型检索方法[30],借鉴化学符号表示零件功能表面、相对位置、朝向以及面与面之间拓扑关系,并对装配结构进行编码,建立检索机制,但随着零件复杂程度增加编码变得十分庞杂.近来朱文博等[31]利用机械零件形状和工艺的特点,将复杂的机械零件拆分成若干相对简单的形体,随后再进行匹配检索.然而有些零件形状非常复杂,使得拆分较困难,而且拆分后可能破坏形状的完整性,因此要使该方法具有更广泛的适应性,还需后续更深入地研究.皇甫中民等[32−33]提出一种基于图谱及空间词袋表征的CAD模型层次特征描述子构建和检索方法,同时基于图索引过滤机制对三维CAD模型局部检索方法进行了研究.

现有的三维模型检索方法大多关注网格模型.然而,在制造业中三维实体模型更有可能重用.构造立体几何(Constructive solid geometry,CSG)和边界表示法(Boundary representation,B-rep)是两个流行的三维实体模型描述手段.CSG允许建模者创建一个复杂的表面或用布尔操作合成对象.B-rep是通过一定的限制表示形状的实体建模方法.一个实体集连接表面元素、实体和非实体之间的边界为一体.由于产品模型数据交换标准(STEP)在一个产品的生命周期提供了一种机制来呈现和交换数据,不同的B-rep模型用STEP很容易交换.鉴于一个三维实体模型的CSG描述是不唯一的,通常用B-rep表示和分析实体模型[34−35].此外,面邻接图(Face adjacency graphs,FAGs)可以很容易地从B-rep模型建立,现有的图或子图匹配可以用于三维模型的形状比较.FAGs是一个有序对Gf=(Vf,Ef),Vf是一组用其属性描述模型表面的顶点集,Ef是一组用其属性描述模型边的边的集合.因此,一些基于FAGs的三维实体模型检索方法被提了出来[24,36−39].

然而,在一个实际的复杂模型中观察到的数以百计的面,以及其有限的面粒度(如多边形平面和圆柱面),产生的FAGs具有很大的规模和很高的复杂性.最近提出的解决这个问题的方法是分割三维实体模型为一组大粒度的面区域以取代CAD模型的面[40−41].在三维模型被分解为一组面区域后,三维形状检索的另一个任务是面区域之间的形状匹配.研究者将区域属性代码引入表示CAD模型的面区域.CAD模型主要是由常规的几何面(如平面、圆柱、圆锥和球体)构成,机械零件的拓扑结构取决于邻接面的类型,对CAD模型面和区域描述是可行的.此外,区域属性代码很容易创建,并且区域代码的比较比子图匹配的模型形状比较要快.于是,区域属性代码相似性就是两个比较模型之间的相似性.在面区域方法中,三维分割对三维形状检索是必不可少的,因为它能用增加模型元素的粒度来明显降低CAD模型的复杂性,并且提取的面区域通常包含一些有效模型比较的语义信息[30].尽管如此,三维分割本身的巨大工作量却也无法回避.本文提出的功能表面划分零件与面区域方法相类似,重要形式概念确定的关键结构关注关键“分割”,可以有效地减少分割带来的工作量,提高检索效率.

零件功能表面具有功能和结构的双重属性,从功能上讲,功能表面直接体现零件的基本功能;从几何上讲,功能表面是实现零件基本功能的最小造型单元,这些功能表面及其空间布局决定了零件功能的物理结构.因此,在相似零件检索过程中,可只用功能表面及其相互关系作为评价零件相似性的特征.

本文拟在功能表面及其相互关系构成的零件工程图结构模型映射的形式背景上研究概念格因子,进而找出反应零件本质特征的关键结构,以此提高零件模型检索的效率.

1 预备知识

概念格存在于形式背景,形式背景反映的是对象、属性的二元关系,其实质上是一个关于对象、属性的布尔矩阵.

定义1.一个布尔代数是一个非空集合β和两个定义在β上的二元运算∨与∧构成的数学系统(β,∨,∧),其满足下列条件:

1)∀a,b∈β,a∨b=b∨a,a∧b=b∧a;

2)∀a,b,c∈β,a∧(b∨c)=(a∧b)∨(a∧c),a∨(b∧c)=(a∨b)∧(a∨c);

3)∃0,1∈β,0̸1,∀a∈β,a∨0=a,a∧1=a;

4)∀a∈β,∃ac∈β,a∨ac=1,a∧ac=0.

如果β只包含两个元素,则称它为二元布尔代数,记为β0.

定义 2.β0上的矩阵称为布尔矩阵.所有m行、n列的布尔矩阵构成的集合记为{0,1}m×n.

定义 3.β0上的一个有序n元组(a1,a2,···,an)是一个n维布尔向量.

令Mr=[µij]∈{0,1}m×n.

这里µi=[µi1,µi2,···,µin]被称作第i行布尔向量,[µ1j,µ2j,···,µmj]T称作第j列布尔向量.也使用Mr[i,:](Mr[:,j])表示的第i行(j列)布尔向量.

定义 4[42].如果U=[µij]∈{0,1}m×n并且V=[νij]∈{0,1}m×n,矩阵U和V的布尔和定义为

布尔乘积为

定义 5[43].如果G={g1,···,gm}和M={w1,···,wn}是对象和属性集,I是G和M间的二元关系,那么三元组(G,M,I)称作形式背景.(G,M,I)的形式概念是一对集合(A,B),A⊆G,B⊆M,满足

A′=B并且B′=A,A′={g∈G|w∈M,(g,w)∈I},B′={w∈M|g∈G,(g,w)∈I}.其中A称为概念(A,B)的外延,B称为概念(A,B)的内涵.

所有(G,M,I)的形式概念集合用ß(G,M,I)表示.

因为G和M间的二元关系可以用布尔矩阵表示,所以对应的布尔矩阵也用I表示.也就是说,I的元Iij=1当且仅当(gi,wj)属于关系I,(gi,wj)不属于关系I则Iij=0.

概念格因子分解将着手于形式背景布尔矩阵的分解,因此,下面引入布尔矩阵分解的概念.

布尔矩阵分解的目的是对给定的I ∈{0,1}n×m,找出U∈{0,1}n×k和V∈{0,1}k×m使得

这里的表示可以按一定程度近似的分解,也就是说对象i有属性j当且仅当存在l个因子使得l应用于i和j是l的一种具体表示.

表1 一个形式背景Table 1 An example of formal context

例1.表1是一个形式背景,它可以表示为布尔矩阵并分解为两个布尔矩阵的乘积.

2 概念格因子分解及算法

定理 1.(乘积展开式)如果Mr能表示为两个矩阵U,V的布尔乘积,那么

证明.定理可直接由式(1)和(2)得到.

定义6.如果(A,B)是一个形式概念,则A,B分别对应一个对象(属性)布尔列(行)向量p=[p1p2···pm]T和q=[q1q2···qn].其中

p, q也可以视为对象(属性)列(行)矩阵.

定理 2.假设(A,B)是一个形式概念,p=[p1p2···pm]T,q=[q1q2···qn]是对应的布尔列、行矩阵,存在

证明.由定义6及布尔矩阵乘积定义可知式(5)成立.

根据文献[43]所有的对象形式概念集、属性形式概念集定义为

定义7.如果F是一个形式概念集合,由属于F的概念(A,B)的对象布尔列向量为列构成矩阵记为AF,属性布尔行向量为行构成矩阵记为BF.

对象、属性形式概念是概念格分解的强制性因子.

定理3[44].(强制性因子)对F⊆ß(A,B,I),如果I=AF◦BF,那么O(G,M,I)∩A(G,M,I)⊆F.

定理4.(有限分解)对于形式背景(G,M,I)上的对象和属性形式概念O(G,M,I),A(G,M,I),有为O(G,M,I),A(G,M,I)的对象(属性)布尔列(行)矩阵,k=|O(G,M,I)|,t=|A(G,M,I)|.

证明.令(Ak,Bk)∈O(G,M,I)是一个形式概念,我们有pk=[p1p2···pm]T和qk=[q1q2···qn]使得p◦q=[bij]∈{0,1}m×n,bij=pi∧qj.由于(Ak,Bk)是对象概念,所以可以按对象序排序,,根据定理1式(4):,其中pk除重复的外,按序对应每个对象,U[:,k]◦V[k,:]覆盖所有“1”矩形,即映射所有可能的属性,故有.同理可证属性形式概念成立.

定理 5.对于形式背景(G,M,I),I=AF◦BF,F=O(G,M,I)或者F=A(G,M,I).

证明.由定理4可直接得到结果.

定理 6.(优化因子)如果F=O(G,M,I)∩是F概念的布尔列 (行)矩阵,存在I∗的O∗(G,M,I∗)∩A∗(G,M,I∗)的概念对象、属性集合包含在O(G,M,I)的对应概念对象、属性集中,那么这样循环的O(G,M,I)对象概念构成I的较O(G,M,I)更小的分解.结论对A(G,M,I)同样成立.

证明.由定理5知I=AF◦BF,F=O(G,M,I), 而 (A∗,B∗)∈ O∗(G,M,I∗)∩A∗(G,M,I∗) 且A∗⊆ A,B∗⊆ B,(A,B)∈O(G,M,I),表明O(G,M,I)中的(A,B)可以加入分解因子集合.当I∗=0时表明作为分解因子新的对象概念集合已完全能表示I.|F∪(A,B)|≤|F|,显然,F∪(A,B)⊆O(G,M,I)是更小的分解.

对于属性形式概念可以用同样的方法证明.

由于有下列定理的结论,我们有必要估计分解的近似程度.

定理 7[45−46].分解n×m布尔矩阵I为一个n×k二元矩阵U和k×m二元矩阵V,I=U◦V,具有尽可能小k的问题是NP-hard,相应的决策问题(即对给定的I和正整数k决定是否存在一个分解的I=U◦V具有内在维度k)是NP-complete.

假设C是一个形式概念集合C⊆ß(G,M,I),Area(C)=|{(i,j)(AC◦BC)ij=1}|是由C的形式概念覆盖的I的1的数量.

因子分解近似程度定义为:Ap(I,F)=Area(F)/Area(ß(G,M,I)).

根据前面的结果,可以给出概念格因子分解的算法.

算法1.概念格因子分解算法.

输入.形式背景(G,M,I)布尔矩阵I.

输出.概念格因子集合F.

1)设定形式背景(G,M,I),对于每一个g∈G,w∈M, 求出O(G,M,I)={({g}′′,{g}′)|g∈G},A(G,M,I)={({w}′,{w}′′|w∈M)};

2)计算公共集合F=O(G,M,I)∩A(G,M,I);

3)求I∗=I−AF◦BF;

4)如果I∗̸0,对于(G,M,I∗)的每一个g∈G,w∈M, 求出O∗(G,M,I∗)={({g}′,{g}′)|g∈G}和A∗(G,M,I∗)={({w}′,{w}′′|w∈M)};

5) 取F∗=O∗(G,M,I∗)∩A∗(G,M,I∗),如果有(C,D)∈F∗且C⊆A,D⊆B,(A,B)∈O(G,M,I),那么F=F∪(C,D),继续步骤3)计算;

6)如果I∗=0表明有最小分解,F即为优化因子概念集合;

7)如果I∗0且没有 (C,D)∈F∗满足C⊆A,D⊆B,(A,B)∈O(G,M,I),表明最小分解无法确定,则可计算近似程度Ap(I,F)=Area(F)/Area(ß(G,M,I)).

例 3.我们以文献[46]中的例子(Example1)为例来演示算法的求解过程.G={1,2,3,4,5,6},M={a,b,c,d,e},

得到({1,6},{b}),而{1,6}⊆{1,3,5,6},{b}⊆{b},({1,3,5,6},{b})∈A(G,M,I),因此概念格分解因子为{({3,5},{b,c}),({1,2,4,5},{d}),({1,2,5,6},{a}),({2,6},{a,e}),({1,3,5,6},{b})}=A(G,M,I).这个例子的分解,因子仍为属性形式概念.

值得一提的是,我们这里求出的分解因子并不一定是最优的,读者容易验证F={({1,5,6},{a,b}),({1,2,4,5},{d}),({2,6},{a,e}),({3,5},{b,c})}也是一个分解.我们的方法只是确定可以找出一个比原概念格小得多的因子集合.

3 因子分解应用于零件三维CAD模型检索

零件三维CAD模型的检索可以通过对工程图视图结构模型的“并”运算,构造零件三维结构模型并进行编码,通过零件三维模型结构码的匹配实现检索.一般来讲这种编码的量是十分巨大的.因此,找出反应零件特征的关键结构对提高检索效率是十分有益的.图1为功能表面视图表达实例,图1中分别用大写字母P、C、H和S表示平面、圆柱面、孔和槽[30].视图表达时,法线(轴线)平行于投影面形成的视图称为功能表面的剖面视图,垂直于投影面形成的视图称为功能表面的外形视图.功能表面间的拓扑关系通过连接边的凹凸性表示,约定:凹边用“0”标记,凸边用“1”标记.两相连功能表面均为回转面时,拓扑关系通过回转面是内表面还是外表面来定义,并用“!”标记.

功能表面间的位置关系包括方位关系和领域关系.方位关系通过方位矢量的空间方位关系来定义,有平行(∥)、同轴(⊙)、垂直(⊥)和偏斜(∠).领域关系指功能表面占据的空间区域间的关系,领域关系的种类与方位关系类型有关,二元领域关系见表2,表3[30].因为平面功能表面占据区域的长度为0,所以平面–回转面间的相遇、重叠、共点关系合并为相遇.两垂直平面之间不定义二元领域关系,并用“!”标记.符号“!♯”表示两功能表面拓扑相连,而符号“♯”则表示拓扑不相连.符号“?”表示功能表面间的位置关系不能通过单个视图确定.

图1 几个常用零件功能表面的视图表达Fig.1 View expression of functional surfaces of several common parts

表2 功能表面二元领域关系(1)Table 2 Two-dimensional domain relation of functional surface(1)

表3 功能表面二元领域关系(2)Table 3 Two-dimensional domain relation of functional surface(2)

分布关系有线性分布(l)、圆周分布(p)、矩形阵列分布(r)和对称分布(m).分布关系用符号“::”标识.

将图1零件工程图的功能表面进行标记,再根据判断拓扑相连功能表面的几何条件、功能表面间位置关系的确定方法以及分布关系的定义,得到零件工程图结构模型如图2所示.

如果将零件工程图的功能表面看作是对象,功能表面间的关系看作是属性,就可以构造零件工程图结构模型的形式背景,进而用概念格分析不同功能面集合间的关系.

图2 零件工程图结构模型Fig.2 The structural model of part engineering drawing

这种转换是比较直接的:

1)对给定零件的工程图结构模型找出所有功能表面建立对象集合G,所有的功能表面间关系为属性集合M;

2)如果g∈G,且与某功能表面有关系w,则(g,w)∈I.

表4就是图1(a)的形式背景(仅列出外形视图).

表4 零件工程图模型图1(a)的形式背景Table 4 The formal context of the part engineering drawing model Fig.1(a)

与一般概念格一样,零件工程图结构模型形式背景上的概念格也存在形式概念数量较大的问题,因此,我们将用因子分解的方法找出能反映零件特征的集对—因子概念.

概念格因子为{({P3,H},{1//m}),({C1,C2,P3,P4},{1⊥b}),({C1,C3},{!⊥b}),({P1,P2},{♯⊙s,0⊙m}),({C1,C2},{1⊥b,0⊙m})}(图3中黑点圈表示的结点).

从图中可以看出,平面P3与四个孔H间凸边平行相遇;圆柱面C1,C2分别和平面P3,P4凸边垂直偏斜;圆柱面C1和C3垂直偏斜;平面P1与P2拓扑不相连同轴分离、凹边同轴相遇;圆柱面C1,C2凸边垂直偏斜、具有凹边同轴相遇的特性足以刻画拉杆轴的功能特征.同理可以计算出摆轴和波导开关转子的关键结构(概念格因子).

图3 零件工程结构模型图1(a)的概念格Fig.3 The concept lattice of part engineering structure model Fig.1(a)

摆轴概念格因子为{({C1,P1},{0⊙s}),({C4,P2},{1⊙s}),({C3,Sr},{1⊙d}),({C2,C3,P2},{1⊥b}),({C2,P1},{1⊙m})}.

波导开关转子概念格因子为{({C4,C5,P1,P2,H2,Hw1},{1//m}),({C3,P4},{1⊥b}),({C2,C3,P2,P3},{0⊙m}),({C1,C4},{1//c}),({C1,C2,P1,P2,P3},{1⊙m})}.

零件三维CAD模型相似性是将功能面邻接图和功能面定性几何约束图中各顶点之间的最短路径定义为一个子结构,通过对子结构进行编码,构成了零件装配结构的分支结构码,以分支结构码的匹配程度作为零件结构的相似度量,检索相似结构的零件[47−49].

分支结构码相似度定义为

式中cij表示零件i,j关键结构码相同的数目,ci,cj表示零件i,j的分支结构码数目.

图4 零件工程结构模型图1(b)的概念格Fig.4 The concept lattice of the part engineering structure model Fig.1(b)

图5 零件工程结构模型图1(c)的概念格Fig.5 The concept lattice of the part engineering structure model Fig.1(c)

算法2.零件三维CAD模型检索算法

1)建立零件装配结构模型.通过交互方式定义功能表面.可先对模型进行简化或直接通过交互方式定义功能表面间的拓扑关系.功能表面间的定性几何约束采用自动提取和交互定义相结合的方法.

2)根据编码方法,通过系统自动生成零件结构码.

零件的结构码包括基本结构码和定性几何约束结构码两类.基本结构码是基于功能面邻接图的结构编码;定性几何约束结构码是基于定性几何约束图的结构编码.

3)概念格因子分解:将结构码转化为形式背景,对形式背景进行概念格因子分解,求出最小因子即关键结构.

4)利用关键结构码实现零件全结构、子结构和相似结构检索.计算基本分支结构码相似度.

4 实例验证

为验证本文算法的可行性,将模型一、二(图6,图7)与自行开发的机械零件检索系统零件库中的零件进行相似性检索.将模型一、二与零件库中所有的零件(9010个)一一进行相似性比较.表5和表6是模型库中部分零件与模型一、二的相似度值.

图6 模型一:连杆Fig.6 Model 1:connecting rod

图7 模型二:箱体Fig.7 Model 2:box

图8是波导开关转子的关键结构分图.其关键结构为({C4,C5,P1,P2,H2,Hw1},{1//m}),孔和上下平面及内圆柱面凸平行相遇 (图 8(a));({C3,P4},{1⊥b}),顶端圆柱面和小平面凸垂直偏斜(图8(b));({C2,C3,P2,P3},{0⊙m}),顶端的两个圆柱面与平台凹同轴相遇(图8(c));({C1,C4},{1//c}),体内半圆柱面与外圆柱面凸平行共点(图8(d));({C1,C2,P1,P2,P3},{1⊙m}),两个主要圆柱面与主要平面凸同轴相遇(图8(e)).

图8 波导开关转子关键结构Fig.8 The key structure of waveguide switch rotor

实验结果表明,该方法具有较高的计算效率和判断精度,对孔、洞、槽以及棱柱类的零件能取得很好的效果.本文将基于图的描述方法和关键结构结合起来,与单独基于子图匹配的检索方法相比,在检索效率上有很大提高.但是对一些不规则的几何体应用本文的方法时,在提取关键结构时往往出现较多的小面片,而这些小面片并不反映零件的主要特征.另外,对于不规则形状零件,最后形成的相关功能面结构的数量也非常多,这也会影响后续的匹配和检索.

由于基于功能表面的装配结构进行编码是需要在检索之前完成的,且编码对空间占用十分有限,因此空间复杂度较低.算法的时间复杂度主要取决于概念格因子的获取.

在算法1第1)步计算属性、对象概念集,需m+n次.对于最坏情况 2)、3)步可能计算2×max(m,n)次,4)、5)步最多n(n+1)/2+m(m+1)/2.也就是说计算时间复杂度O(n2+m2).由于都用到了结构编码,我们将算法与文献[40]进行了比较.

其零件检索采用两个策略:1)将分割区域的全体组合作为一个基本检索单元,加入到区域结构倒排索引中.2)将零件中每个邻接区域结构对看成一个子结构,建立零件的二元区域结构索引,通过对邻接区域结构对倒排记录表求交集,实现包含3个及以上区域结构的整体子结构查询.第一种策略,由于组合爆炸,其复杂度没有优势.策略二区域结构本身粒度较大,虽然减少了匹配的次数,但出错的概率增加了.

将模型一和模型二在VisualC++,ACIS和HOOPS环境下进行检索.实验用微机CPU为Intel 3.30GHz,内存为4.0GB.表7,表8是两种方法检索比较的结果.

5 实验分析

实验的目的是测试检索算法的有效性.在图9中的检索算法查准率–查全率(precision-recall)曲线表示了八个不同概念节点的情形:节点数量是2(图中标为n=2,其他类似),4,6,7,8,9,11和15.图中参数k意为零件关键结构的数量.查准率–查全率曲线的与零件的节点数量相关.当节点的数量从2增加到6时,性能显著降低.从n=8算法的性能变得不稳定并降低很快.所以在检索复杂零件时,算法并不是十分有效,特别是零件有超过8的节点.究其原因是,在我们的模型背景中,概念节点的数量是基本计算单元.概念节点越多、越相似,精度较低.图10的n−k表明,随着n值的增加,k开始增加,并且增长率变化越来越大.特别是在k大于9后.所以很明显,在零件关键结构(关键特性)小于9时,检索算法具有良好的性能,否则效果不能令人满意.不过,这已经可以满足一般实际应用要求.

图9 不同概念节点数的查准率–查全率曲线Fig.9 Precision rate-recall(precision-recall)curves of the number of different conceptual nodes

图10 n−k曲线图Fig.10 The n−k curve

6 结论

概念格理论是一种有效的数据分析和知识处理的工具,在人工智能的许多研究领域已经被成功地运用.但在实际中,一个中等大小的输入数据集通常可以产生相当大的一组形式概念,这直接影响着它的应用.本文引入了形式背景布尔矩阵分解的概念,讨论基于对象概念、属性概念的概念格因子分解的特性,并提出了概念格因子发现的方法和近似测度的公式,给出了相应的概念格因子生成算法.通过实例把本文提出的因子分解理论应用于零件模型检索,优点是可以用较少的结构较高的效率确定被查找的对象.本文进一步扩充了概念格的约简理论(是对概念格无前置条件的约简),对概念格的研究和应用都有重要意义.