基于概念格因子分解的零件三維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},g0gggggg),({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},g0gggggg),({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 結論

概念格理論是一種有效的數據分析和知識處理的工具,在人工智能的許多研究領域已經被成功地運用.但在實際中,一個中等大小的輸入數據集通常可以產生相當大的一組形式概念,這直接影響著它的應用.本文引入了形式背景布爾矩陣分解的概念,討論基于對象概念、屬性概念的概念格因子分解的特性,并提出了概念格因子發現的方法和近似測度的公式,給出了相應的概念格因子生成算法.通過實例把本文提出的因子分解理論應用于零件模型檢索,優點是可以用較少的結構較高的效率確定被查找的對象.本文進一步擴充了概念格的約簡理論(是對概念格無前置條件的約簡),對概念格的研究和應用都有重要意義.