吳強(qiáng) 董雁 吳域西 謝麗萍

對(duì)于概念格來說,即使是一個(gè)小的數(shù)據(jù)集可能產(chǎn)生大量的形式概念[1].這是源于其存在高組合復(fù)雜性和結(jié)構(gòu).最壞的情況可以達(dá)到2min(|G|,|M|)(|G|,|M|分別為對(duì)象和屬性的總數(shù)).此外,產(chǎn)生的形式概念的數(shù)量和概念之間關(guān)系的復(fù)雜性使得最終格的分析十分困難[2].

為簡(jiǎn)化概念格,現(xiàn)有的研究主要采用了知識(shí)約簡(jiǎn)的方法.所謂知識(shí)約簡(jiǎn),就是針對(duì)不同的目的要求,保持知識(shí)庫分類能力不變,刪除其中不相關(guān)或不重要的屬性,使知識(shí)表示簡(jiǎn)化的同時(shí)又不丟失基本信息.

已有研究者研究了從給定的二元形式背景[3]、決策形式背景[4?5]、模糊形式背景[6?7]、實(shí)決策形式背景[8]中約簡(jiǎn)生成形式概念.Dias和Vieira[9]提出了一種分析概念格約簡(jiǎn)的方法.它是基于存在于原始與約簡(jiǎn)后的形式背景,或概念格間的特有的蘊(yùn)含集合的.通過這些蘊(yùn)含集合,設(shè)計(jì)的約簡(jiǎn)方法能夠顯現(xiàn)數(shù)據(jù)信息的保持、消失、增加及變化.他們從方法論的角度分析了三類約簡(jiǎn)技術(shù),強(qiáng)調(diào)了其在轉(zhuǎn)換時(shí)的共同之處.Konecny[10]的研究表明,雖然有各種擴(kuò)展,Ganter和Wille的概念格屬性約簡(jiǎn)和解釋依然是優(yōu)于基于可辨識(shí)矩陣約簡(jiǎn)的.Singh等[11]提出了一種在形式概念分析中用模糊屬性減少形式概念數(shù)目的方法.其以香農(nóng)熵計(jì)算模糊形式概念的權(quán)重.用計(jì)算的權(quán)重選擇粒約簡(jiǎn)模糊形式概念.結(jié)果表明,所提出的方法得到的結(jié)果與Levenshtein距離法以及區(qū)間值模糊形式概念的方法一致,但計(jì)算復(fù)雜度更低.因?yàn)槭腔趯傩缘?這些方法的結(jié)果很難直觀地、易于理解地反映出對(duì)象— 屬性關(guān)系(即形式概念)的重要程度.

就目前的結(jié)果來說,關(guān)注重要概念選擇以至于對(duì)概念格進(jìn)行分解的研究較為鮮見.Babin和Kuznetsov[12]引進(jìn)了概念穩(wěn)定性來測(cè)度概念的重要性.Belohlavek和Macko[1]利用權(quán)重研究了重要的概念并討論其應(yīng)用.Dias和Viera[13]提出基于連接的對(duì)象相似(JBOS)方法約簡(jiǎn)形式概念的數(shù)目.Li等[14]討論了加權(quán)概念格及其應(yīng)用.Kang等[15]提出一種在不同粒度下減少模糊概念格大小的方法.Li等[16]提出了一種采用K-medoids聚類來壓縮近似概念格的方法.Martin等[17]提出一種使用Levenshtein距離測(cè)度模糊概念格的變化的方法.Singh等[18]推出了一個(gè)使用香農(nóng)熵來計(jì)算給定模糊形式概念的權(quán)重的方法,選擇根據(jù)所計(jì)算出來的權(quán)重的粒度約簡(jiǎn)模糊形式概念.Aswani等[19]新近提出了在形式背景上用非負(fù)矩陣分解約簡(jiǎn)知識(shí),但僅提出了一個(gè)思想,對(duì)矩陣存在與約束條件尚無探討.

將概念格與因子分析聯(lián)系起來的是Keprt和Sná?el[20].他們提出了基于形式概念分析計(jì)算非層次二元因子分析的方法.盡管計(jì)算概念格本身也是十分繁雜的,它仍然幫助加快了二元因子分析的計(jì)算.Belohlavek和Vychodil[21]提出了一個(gè)有序數(shù)據(jù)的矩陣分解和因子分析的方法.這些因子對(duì)應(yīng)于輸入數(shù)據(jù)的形式概念成為數(shù)量最少的因子,并可以十分簡(jiǎn)單的解釋分解.

由于圖能較好地描述三維CAD模型的幾何、拓?fù)淠酥琳Z義信息,近年來基于圖的模型表征和檢索方法受到了更多關(guān)注[22?23].典型的用于CAD模型檢索的工作有屬性鄰接圖[24?27]、完全二分圖[28]、擴(kuò)展特征樹[29]等描述子方法.這些基于圖的檢索方法盡管可以采用各種“圖結(jié)構(gòu)”較好地表征模型的幾何、拓?fù)淠酥琳Z義信息,但最終都要通過繁瑣的圖匹配來實(shí)現(xiàn)對(duì)應(yīng)模型間的相似性比較,十分復(fù)雜而耗時(shí),因此這些檢索方法效率很低.雖然有文獻(xiàn)[24,27]對(duì)CAD模型用向量化表征在一定程度上可提高匹配和檢索效率,但其只能表達(dá)模型的整體形狀,當(dāng)模型較大型且復(fù)雜時(shí),其局部細(xì)節(jié)特征描述能力不足,局部特征信息不突出.檢索精度和檢索效率存在一定程度的矛盾.徐靜等提出了一種基于裝配結(jié)構(gòu)相似的零件三維模型檢索方法[30],借鑒化學(xué)符號(hào)表示零件功能表面、相對(duì)位置、朝向以及面與面之間拓?fù)潢P(guān)系,并對(duì)裝配結(jié)構(gòu)進(jìn)行編碼,建立檢索機(jī)制,但隨著零件復(fù)雜程度增加編碼變得十分龐雜.近來朱文博等[31]利用機(jī)械零件形狀和工藝的特點(diǎn),將復(fù)雜的機(jī)械零件拆分成若干相對(duì)簡(jiǎn)單的形體,隨后再進(jìn)行匹配檢索.然而有些零件形狀非常復(fù)雜,使得拆分較困難,而且拆分后可能破壞形狀的完整性,因此要使該方法具有更廣泛的適應(yīng)性,還需后續(xù)更深入地研究.皇甫中民等[32?33]提出一種基于圖譜及空間詞袋表征的CAD模型層次特征描述子構(gòu)建和檢索方法,同時(shí)基于圖索引過濾機(jī)制對(duì)三維CAD模型局部檢索方法進(jìn)行了研究.

現(xiàn)有的三維模型檢索方法大多關(guān)注網(wǎng)格模型.然而,在制造業(yè)中三維實(shí)體模型更有可能重用.構(gòu)造立體幾何(Constructive solid geometry,CSG)和邊界表示法(Boundary representation,B-rep)是兩個(gè)流行的三維實(shí)體模型描述手段.CSG允許建模者創(chuàng)建一個(gè)復(fù)雜的表面或用布爾操作合成對(duì)象.B-rep是通過一定的限制表示形狀的實(shí)體建模方法.一個(gè)實(shí)體集連接表面元素、實(shí)體和非實(shí)體之間的邊界為一體.由于產(chǎn)品模型數(shù)據(jù)交換標(biāo)準(zhǔn)(STEP)在一個(gè)產(chǎn)品的生命周期提供了一種機(jī)制來呈現(xiàn)和交換數(shù)據(jù),不同的B-rep模型用STEP很容易交換.鑒于一個(gè)三維實(shí)體模型的CSG描述是不唯一的,通常用B-rep表示和分析實(shí)體模型[34?35].此外,面鄰接圖(Face adjacency graphs,FAGs)可以很容易地從B-rep模型建立,現(xiàn)有的圖或子圖匹配可以用于三維模型的形狀比較.FAGs是一個(gè)有序?qū)f=(Vf,Ef),Vf是一組用其屬性描述模型表面的頂點(diǎn)集,Ef是一組用其屬性描述模型邊的邊的集合.因此,一些基于FAGs的三維實(shí)體模型檢索方法被提了出來[24,36?39].

然而,在一個(gè)實(shí)際的復(fù)雜模型中觀察到的數(shù)以百計(jì)的面,以及其有限的面粒度(如多邊形平面和圓柱面),產(chǎn)生的FAGs具有很大的規(guī)模和很高的復(fù)雜性.最近提出的解決這個(gè)問題的方法是分割三維實(shí)體模型為一組大粒度的面區(qū)域以取代CAD模型的面[40?41].在三維模型被分解為一組面區(qū)域后,三維形狀檢索的另一個(gè)任務(wù)是面區(qū)域之間的形狀匹配.研究者將區(qū)域?qū)傩源a引入表示CAD模型的面區(qū)域.CAD模型主要是由常規(guī)的幾何面(如平面、圓柱、圓錐和球體)構(gòu)成,機(jī)械零件的拓?fù)浣Y(jié)構(gòu)取決于鄰接面的類型,對(duì)CAD模型面和區(qū)域描述是可行的.此外,區(qū)域?qū)傩源a很容易創(chuàng)建,并且區(qū)域代碼的比較比子圖匹配的模型形狀比較要快.于是,區(qū)域?qū)傩源a相似性就是兩個(gè)比較模型之間的相似性.在面區(qū)域方法中,三維分割對(duì)三維形狀檢索是必不可少的,因?yàn)樗苡迷黾幽Ｐ驮氐牧６葋砻黠@降低CAD模型的復(fù)雜性,并且提取的面區(qū)域通常包含一些有效模型比較的語義信息[30].盡管如此,三維分割本身的巨大工作量卻也無法回避.本文提出的功能表面劃分零件與面區(qū)域方法相類似,重要形式概念確定的關(guān)鍵結(jié)構(gòu)關(guān)注關(guān)鍵“分割”,可以有效地減少分割帶來的工作量,提高檢索效率.

零件功能表面具有功能和結(jié)構(gòu)的雙重屬性,從功能上講,功能表面直接體現(xiàn)零件的基本功能;從幾何上講,功能表面是實(shí)現(xiàn)零件基本功能的最小造型單元,這些功能表面及其空間布局決定了零件功能的物理結(jié)構(gòu).因此,在相似零件檢索過程中,可只用功能表面及其相互關(guān)系作為評(píng)價(jià)零件相似性的特征.

本文擬在功能表面及其相互關(guān)系構(gòu)成的零件工程圖結(jié)構(gòu)模型映射的形式背景上研究概念格因子,進(jìn)而找出反應(yīng)零件本質(zhì)特征的關(guān)鍵結(jié)構(gòu),以此提高零件模型檢索的效率.

1 預(yù)備知識(shí)

概念格存在于形式背景,形式背景反映的是對(duì)象、屬性的二元關(guān)系,其實(shí)質(zhì)上是一個(gè)關(guān)于對(duì)象、屬性的布爾矩陣.

定義1.一個(gè)布爾代數(shù)是一個(gè)非空集合β和兩個(gè)定義在β上的二元運(yùn)算∨與∧構(gòu)成的數(shù)學(xué)系統(tǒng)(β,∨,∧),其滿足下列條件:

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.

如果β只包含兩個(gè)元素,則稱它為二元布爾代數(shù),記為β0.

定義 2.β0上的矩陣稱為布爾矩陣.所有m行、n列的布爾矩陣構(gòu)成的集合記為{0,1}m×n.

定義 3.β0上的一個(gè)有序n元組(a1,a2,···,an)是一個(gè)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}是對(duì)象和屬性集,I是G和M間的二元關(guān)系,那么三元組(G,M,I)稱作形式背景.(G,M,I)的形式概念是一對(duì)集合(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)的內(nèi)涵.

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

因?yàn)镚和M間的二元關(guān)系可以用布爾矩陣表示,所以對(duì)應(yīng)的布爾矩陣也用I表示.也就是說,I的元Iij=1當(dāng)且僅當(dāng)(gi,wj)屬于關(guān)系I,(gi,wj)不屬于關(guān)系I則Iij=0.

概念格因子分解將著手于形式背景布爾矩陣的分解,因此,下面引入布爾矩陣分解的概念.

布爾矩陣分解的目的是對(duì)給定的I ∈{0,1}n×m,找出U∈{0,1}n×k和V∈{0,1}k×m使得

這里的表示可以按一定程度近似的分解,也就是說對(duì)象i有屬性j當(dāng)且僅當(dāng)存在l個(gè)因子使得l應(yīng)用于i和j是l的一種具體表示.

表1 一個(gè)形式背景Table 1 An example of formal context

例1.表1是一個(gè)形式背景,它可以表示為布爾矩陣并分解為兩個(gè)布爾矩陣的乘積.

2 概念格因子分解及算法

定理 1.(乘積展開式)如果Mr能表示為兩個(gè)矩陣U,V的布爾乘積,那么

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

定義6.如果(A,B)是一個(gè)形式概念,則A,B分別對(duì)應(yīng)一個(gè)對(duì)象(屬性)布爾列(行)向量p=[p1p2···pm]T和q=[q1q2···qn].其中

p, q也可以視為對(duì)象(屬性)列(行)矩陣.

定理 2.假設(shè)(A,B)是一個(gè)形式概念,p=[p1p2···pm]T,q=[q1q2···qn]是對(duì)應(yīng)的布爾列、行矩陣,存在

證明.由定義6及布爾矩陣乘積定義可知式(5)成立.

根據(jù)文獻(xiàn)[43]所有的對(duì)象形式概念集、屬性形式概念集定義為

定義7.如果F是一個(gè)形式概念集合,由屬于F的概念(A,B)的對(duì)象布爾列向量為列構(gòu)成矩陣記為AF,屬性布爾行向量為行構(gòu)成矩陣記為BF.

對(duì)象、屬性形式概念是概念格分解的強(qiáng)制性因子.

定理3[44].(強(qiáng)制性因子)對(duì)F??(A,B,I),如果I=AF?BF,那么O(G,M,I)∩A(G,M,I)?F.

定理4.(有限分解)對(duì)于形式背景(G,M,I)上的對(duì)象和屬性形式概念O(G,M,I),A(G,M,I),有為O(G,M,I),A(G,M,I)的對(duì)象(屬性)布爾列(行)矩陣,k=|O(G,M,I)|,t=|A(G,M,I)|.

證明.令(Ak,Bk)∈O(G,M,I)是一個(gè)形式概念,我們有pk=[p1p2···pm]T和qk=[q1q2···qn]使得p?q=[bij]∈{0,1}m×n,bij=pi∧qj.由于(Ak,Bk)是對(duì)象概念,所以可以按對(duì)象序排序,,根據(jù)定理1式(4):,其中pk除重復(fù)的外,按序?qū)?yīng)每個(gè)對(duì)象,U[:,k]?V[k,:]覆蓋所有“1”矩形,即映射所有可能的屬性,故有.同理可證屬性形式概念成立.

定理 5.對(duì)于形式背景(G,M,I),I=AF?BF,F=O(G,M,I)或者F=A(G,M,I).

證明.由定理4可直接得到結(jié)果.

定理 6.(優(yōu)化因子)如果F=O(G,M,I)∩是F概念的布爾列 (行)矩陣,存在I?的O?(G,M,I?)∩A?(G,M,I?)的概念對(duì)象、屬性集合包含在O(G,M,I)的對(duì)應(yīng)概念對(duì)象、屬性集中,那么這樣循環(huán)的O(G,M,I)對(duì)象概念構(gòu)成I的較O(G,M,I)更小的分解.結(jié)論對(duì)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)可以加入分解因子集合.當(dāng)I?=0時(shí)表明作為分解因子新的對(duì)象概念集合已完全能表示I.|F∪(A,B)|≤|F|,顯然,F∪(A,B)?O(G,M,I)是更小的分解.

對(duì)于屬性形式概念可以用同樣的方法證明.

由于有下列定理的結(jié)論,我們有必要估計(jì)分解的近似程度.

定理 7[45?46].分解n×m布爾矩陣I為一個(gè)n×k二元矩陣U和k×m二元矩陣V,I=U?V,具有盡可能小k的問題是NP-hard,相應(yīng)的決策問題(即對(duì)給定的I和正整數(shù)k決定是否存在一個(gè)分解的I=U?V具有內(nèi)在維度k)是NP-complete.

假設(shè)C是一個(gè)形式概念集合C??(G,M,I),Area(C)=|{(i,j)(AC?BC)ij=1}|是由C的形式概念覆蓋的I的1的數(shù)量.

因子分解近似程度定義為:Ap(I,F)=Area(F)/Area(?(G,M,I)).

根據(jù)前面的結(jié)果,可以給出概念格因子分解的算法.

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

輸入.形式背景(G,M,I)布爾矩陣I.

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

1)設(shè)定形式背景(G,M,I),對(duì)于每一個(gè)g∈G,w∈M, 求出O(G,M,I)={({g}′′,{g}′)|g∈G},A(G,M,I)={({w}′,{w}′′|w∈M)};

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

3)求I?=I?AF?BF;

4)如果I??0,對(duì)于(G,M,I?)的每一個(gè)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),繼續(xù)步驟3)計(jì)算;

6)如果I?=0表明有最小分解,F即為優(yōu)化因子概念集合;

7)如果I?0且沒有 (C,D)∈F?滿足C?A,D?B,(A,B)∈O(G,M,I),表明最小分解無法確定,則可計(jì)算近似程度Ap(I,F)=Area(F)/Area(?(G,M,I)).

例 3.我們以文獻(xiàn)[46]中的例子(Example1)為例來演示算法的求解過程.G={1,2,3,4,5,6},M={a,b,c,d,e},

得到({1,6},),而{1,6}?{1,3,5,6},?,({1,3,5,6},)∈A(G,M,I),因此概念格分解因子為{({3,5},{b,c}),({1,2,4,5},2mawq2q),({1,2,5,6},{a}),({2,6},{a,e}),({1,3,5,6},)}=A(G,M,I).這個(gè)例子的分解,因子仍為屬性形式概念.

值得一提的是,我們這里求出的分解因子并不一定是最優(yōu)的,讀者容易驗(yàn)證F={({1,5,6},{a,b}),({1,2,4,5},emm0euo),({2,6},{a,e}),({3,5},{b,c})}也是一個(gè)分解.我們的方法只是確定可以找出一個(gè)比原概念格小得多的因子集合.

3 因子分解應(yīng)用于零件三維CAD模型檢索

零件三維CAD模型的檢索可以通過對(duì)工程圖視圖結(jié)構(gòu)模型的“并”運(yùn)算,構(gòu)造零件三維結(jié)構(gòu)模型并進(jìn)行編碼,通過零件三維模型結(jié)構(gòu)碼的匹配實(shí)現(xiàn)檢索.一般來講這種編碼的量是十分巨大的.因此,找出反應(yīng)零件特征的關(guān)鍵結(jié)構(gòu)對(duì)提高檢索效率是十分有益的.圖1為功能表面視圖表達(dá)實(shí)例,圖1中分別用大寫字母P、C、H和S表示平面、圓柱面、孔和槽[30].視圖表達(dá)時(shí),法線(軸線)平行于投影面形成的視圖稱為功能表面的剖面視圖,垂直于投影面形成的視圖稱為功能表面的外形視圖.功能表面間的拓?fù)潢P(guān)系通過連接邊的凹凸性表示,約定:凹邊用“0”標(biāo)記,凸邊用“1”標(biāo)記.兩相連功能表面均為回轉(zhuǎn)面時(shí),拓?fù)潢P(guān)系通過回轉(zhuǎn)面是內(nèi)表面還是外表面來定義,并用“!”標(biāo)記.

功能表面間的位置關(guān)系包括方位關(guān)系和領(lǐng)域關(guān)系.方位關(guān)系通過方位矢量的空間方位關(guān)系來定義,有平行(∥)、同軸(⊙)、垂直(⊥)和偏斜(∠).領(lǐng)域關(guān)系指功能表面占據(jù)的空間區(qū)域間的關(guān)系,領(lǐng)域關(guān)系的種類與方位關(guān)系類型有關(guān),二元領(lǐng)域關(guān)系見表2,表3[30].因?yàn)槠矫婀δ鼙砻嬲紦?jù)區(qū)域的長(zhǎng)度為0,所以平面–回轉(zhuǎn)面間的相遇、重疊、共點(diǎn)關(guān)系合并為相遇.兩垂直平面之間不定義二元領(lǐng)域關(guān)系,并用“!”標(biāo)記.符號(hào)“!?”表示兩功能表面拓?fù)湎噙B,而符號(hào)“?”則表示拓?fù)洳幌噙B.符號(hào)“?”表示功能表面間的位置關(guān)系不能通過單個(gè)視圖確定.

圖1 幾個(gè)常用零件功能表面的視圖表達(dá)Fig.1 View expression of functional surfaces of several common parts

表2 功能表面二元領(lǐng)域關(guān)系(1)Table 2 Two-dimensional domain relation of functional surface(1)

表3 功能表面二元領(lǐng)域關(guān)系(2)Table 3 Two-dimensional domain relation of functional surface(2)

分布關(guān)系有線性分布(l)、圓周分布(p)、矩形陣列分布(r)和對(duì)稱分布(m).分布關(guān)系用符號(hào)“::”標(biāo)識(shí).

將圖1零件工程圖的功能表面進(jìn)行標(biāo)記,再根據(jù)判斷拓?fù)湎噙B功能表面的幾何條件、功能表面間位置關(guān)系的確定方法以及分布關(guān)系的定義,得到零件工程圖結(jié)構(gòu)模型如圖2所示.

如果將零件工程圖的功能表面看作是對(duì)象,功能表面間的關(guān)系看作是屬性,就可以構(gòu)造零件工程圖結(jié)構(gòu)模型的形式背景,進(jìn)而用概念格分析不同功能面集合間的關(guān)系.

圖2 零件工程圖結(jié)構(gòu)模型Fig.2 The structural model of part engineering drawing

這種轉(zhuǎn)換是比較直接的:

1)對(duì)給定零件的工程圖結(jié)構(gòu)模型找出所有功能表面建立對(duì)象集合G,所有的功能表面間關(guān)系為屬性集合M;

2)如果g∈G,且與某功能表面有關(guān)系w,則(g,w)∈I.

表4就是圖1(a)的形式背景(僅列出外形視圖).

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

與一般概念格一樣,零件工程圖結(jié)構(gòu)模型形式背景上的概念格也存在形式概念數(shù)量較大的問題,因此,我們將用因子分解的方法找出能反映零件特征的集對(duì)—因子概念.

概念格因子為{({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中黑點(diǎn)圈表示的結(jié)點(diǎn)).

從圖中可以看出,平面P3與四個(gè)孔H間凸邊平行相遇;圓柱面C1,C2分別和平面P3,P4凸邊垂直偏斜;圓柱面C1和C3垂直偏斜;平面P1與P2拓?fù)洳幌噙B同軸分離、凹邊同軸相遇;圓柱面C1,C2凸邊垂直偏斜、具有凹邊同軸相遇的特性足以刻畫拉桿軸的功能特征.同理可以計(jì)算出擺軸和波導(dǎo)開關(guān)轉(zhuǎn)子的關(guān)鍵結(jié)構(gòu)(概念格因子).

圖3 零件工程結(jié)構(gòu)模型圖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})}.

波導(dǎo)開關(guān)轉(zhuǎn)子概念格因子為{({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模型相似性是將功能面鄰接圖和功能面定性幾何約束圖中各頂點(diǎn)之間的最短路徑定義為一個(gè)子結(jié)構(gòu),通過對(duì)子結(jié)構(gòu)進(jìn)行編碼,構(gòu)成了零件裝配結(jié)構(gòu)的分支結(jié)構(gòu)碼,以分支結(jié)構(gòu)碼的匹配程度作為零件結(jié)構(gòu)的相似度量,檢索相似結(jié)構(gòu)的零件[47?49].

分支結(jié)構(gòu)碼相似度定義為

式中cij表示零件i,j關(guān)鍵結(jié)構(gòu)碼相同的數(shù)目,ci,cj表示零件i,j的分支結(jié)構(gòu)碼數(shù)目.

圖4 零件工程結(jié)構(gòu)模型圖1(b)的概念格Fig.4 The concept lattice of the part engineering structure model Fig.1(b)

圖5 零件工程結(jié)構(gòu)模型圖1(c)的概念格Fig.5 The concept lattice of the part engineering structure model Fig.1(c)

算法2.零件三維CAD模型檢索算法

1)建立零件裝配結(jié)構(gòu)模型.通過交互方式定義功能表面.可先對(duì)模型進(jìn)行簡(jiǎn)化或直接通過交互方式定義功能表面間的拓?fù)潢P(guān)系.功能表面間的定性幾何約束采用自動(dòng)提取和交互定義相結(jié)合的方法.

2)根據(jù)編碼方法,通過系統(tǒng)自動(dòng)生成零件結(jié)構(gòu)碼.

零件的結(jié)構(gòu)碼包括基本結(jié)構(gòu)碼和定性幾何約束結(jié)構(gòu)碼兩類.基本結(jié)構(gòu)碼是基于功能面鄰接圖的結(jié)構(gòu)編碼;定性幾何約束結(jié)構(gòu)碼是基于定性幾何約束圖的結(jié)構(gòu)編碼.

3)概念格因子分解:將結(jié)構(gòu)碼轉(zhuǎn)化為形式背景,對(duì)形式背景進(jìn)行概念格因子分解,求出最小因子即關(guān)鍵結(jié)構(gòu).

4)利用關(guān)鍵結(jié)構(gòu)碼實(shí)現(xiàn)零件全結(jié)構(gòu)、子結(jié)構(gòu)和相似結(jié)構(gòu)檢索.計(jì)算基本分支結(jié)構(gòu)碼相似度.

4 實(shí)例驗(yàn)證

為驗(yàn)證本文算法的可行性,將模型一、二(圖6,圖7)與自行開發(fā)的機(jī)械零件檢索系統(tǒng)零件庫中的零件進(jìn)行相似性檢索.將模型一、二與零件庫中所有的零件(9010個(gè))一一進(jìn)行相似性比較.表5和表6是模型庫中部分零件與模型一、二的相似度值.

圖6 模型一:連桿Fig.6 Model 1:connecting rod

圖7 模型二:箱體Fig.7 Model 2:box

圖8是波導(dǎo)開關(guān)轉(zhuǎn)子的關(guān)鍵結(jié)構(gòu)分圖.其關(guān)鍵結(jié)構(gòu)為({C4,C5,P1,P2,H2,Hw1},{1//m}),孔和上下平面及內(nèi)圓柱面凸平行相遇 (圖 8(a));({C3,P4},{1⊥b}),頂端圓柱面和小平面凸垂直偏斜(圖8(b));({C2,C3,P2,P3},{0⊙m}),頂端的兩個(gè)圓柱面與平臺(tái)凹同軸相遇(圖8(c));({C1,C4},{1//c}),體內(nèi)半圓柱面與外圓柱面凸平行共點(diǎn)(圖8(d));({C1,C2,P1,P2,P3},{1⊙m}),兩個(gè)主要圓柱面與主要平面凸同軸相遇(圖8(e)).

圖8 波導(dǎo)開關(guān)轉(zhuǎn)子關(guān)鍵結(jié)構(gòu)Fig.8 The key structure of waveguide switch rotor

實(shí)驗(yàn)結(jié)果表明,該方法具有較高的計(jì)算效率和判斷精度,對(duì)孔、洞、槽以及棱柱類的零件能取得很好的效果.本文將基于圖的描述方法和關(guān)鍵結(jié)構(gòu)結(jié)合起來,與單獨(dú)基于子圖匹配的檢索方法相比,在檢索效率上有很大提高.但是對(duì)一些不規(guī)則的幾何體應(yīng)用本文的方法時(shí),在提取關(guān)鍵結(jié)構(gòu)時(shí)往往出現(xiàn)較多的小面片,而這些小面片并不反映零件的主要特征.另外,對(duì)于不規(guī)則形狀零件,最后形成的相關(guān)功能面結(jié)構(gòu)的數(shù)量也非常多,這也會(huì)影響后續(xù)的匹配和檢索.

由于基于功能表面的裝配結(jié)構(gòu)進(jìn)行編碼是需要在檢索之前完成的,且編碼對(duì)空間占用十分有限,因此空間復(fù)雜度較低.算法的時(shí)間復(fù)雜度主要取決于概念格因子的獲取.

在算法1第1)步計(jì)算屬性、對(duì)象概念集,需m+n次.對(duì)于最壞情況 2)、3)步可能計(jì)算2×max(m,n)次,4)、5)步最多n(n+1)/2+m(m+1)/2.也就是說計(jì)算時(shí)間復(fù)雜度O(n2+m2).由于都用到了結(jié)構(gòu)編碼,我們將算法與文獻(xiàn)[40]進(jìn)行了比較.

其零件檢索采用兩個(gè)策略:1)將分割區(qū)域的全體組合作為一個(gè)基本檢索單元,加入到區(qū)域結(jié)構(gòu)倒排索引中.2)將零件中每個(gè)鄰接區(qū)域結(jié)構(gòu)對(duì)看成一個(gè)子結(jié)構(gòu),建立零件的二元區(qū)域結(jié)構(gòu)索引,通過對(duì)鄰接區(qū)域結(jié)構(gòu)對(duì)倒排記錄表求交集,實(shí)現(xiàn)包含3個(gè)及以上區(qū)域結(jié)構(gòu)的整體子結(jié)構(gòu)查詢.第一種策略,由于組合爆炸,其復(fù)雜度沒有優(yōu)勢(shì).策略二區(qū)域結(jié)構(gòu)本身粒度較大,雖然減少了匹配的次數(shù),但出錯(cuò)的概率增加了.

將模型一和模型二在VisualC++,ACIS和HOOPS環(huán)境下進(jìn)行檢索.實(shí)驗(yàn)用微機(jī)CPU為Intel 3.30GHz,內(nèi)存為4.0GB.表7,表8是兩種方法檢索比較的結(jié)果.

5 實(shí)驗(yàn)分析

實(shí)驗(yàn)的目的是測(cè)試檢索算法的有效性.在圖9中的檢索算法查準(zhǔn)率–查全率(precision-recall)曲線表示了八個(gè)不同概念節(jié)點(diǎn)的情形:節(jié)點(diǎn)數(shù)量是2(圖中標(biāo)為n=2,其他類似),4,6,7,8,9,11和15.圖中參數(shù)k意為零件關(guān)鍵結(jié)構(gòu)的數(shù)量.查準(zhǔn)率–查全率曲線的與零件的節(jié)點(diǎn)數(shù)量相關(guān).當(dāng)節(jié)點(diǎn)的數(shù)量從2增加到6時(shí),性能顯著降低.從n=8算法的性能變得不穩(wěn)定并降低很快.所以在檢索復(fù)雜零件時(shí),算法并不是十分有效,特別是零件有超過8的節(jié)點(diǎn).究其原因是,在我們的模型背景中,概念節(jié)點(diǎn)的數(shù)量是基本計(jì)算單元.概念節(jié)點(diǎn)越多、越相似,精度較低.圖10的n?k表明,隨著n值的增加,k開始增加,并且增長(zhǎng)率變化越來越大.特別是在k大于9后.所以很明顯,在零件關(guān)鍵結(jié)構(gòu)(關(guān)鍵特性)小于9時(shí),檢索算法具有良好的性能,否則效果不能令人滿意.不過,這已經(jīng)可以滿足一般實(shí)際應(yīng)用要求.

圖9 不同概念節(jié)點(diǎn)數(shù)的查準(zhǔn)率–查全率曲線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 結(jié)論

概念格理論是一種有效的數(shù)據(jù)分析和知識(shí)處理的工具,在人工智能的許多研究領(lǐng)域已經(jīng)被成功地運(yùn)用.但在實(shí)際中,一個(gè)中等大小的輸入數(shù)據(jù)集通?？梢援a(chǎn)生相當(dāng)大的一組形式概念,這直接影響著它的應(yīng)用.本文引入了形式背景布爾矩陣分解的概念,討論基于對(duì)象概念、屬性概念的概念格因子分解的特性,并提出了概念格因子發(fā)現(xiàn)的方法和近似測(cè)度的公式,給出了相應(yīng)的概念格因子生成算法.通過實(shí)例把本文提出的因子分解理論應(yīng)用于零件模型檢索,優(yōu)點(diǎn)是可以用較少的結(jié)構(gòu)較高的效率確定被查找的對(duì)象.本文進(jìn)一步擴(kuò)充了概念格的約簡(jiǎn)理論(是對(duì)概念格無前置條件的約簡(jiǎn)),對(duì)概念格的研究和應(yīng)用都有重要意義.