基于形式概念分析的模式匹配算法

1、基于形式概念分析的模式匹配算法1形式概念分析與概念格形式概念分析(FCA)13-14是一項(xiàng)基于概念格理論以及命題演算的數(shù)據(jù)分析方法,適用于發(fā)現(xiàn)形式上下文,已經(jīng)被應(yīng)用到軟件工程、知識(shí)發(fā)現(xiàn)、策略分析和心理學(xué)等領(lǐng)域.概念格(Galiois格)是形式概念分析理論中的一種核心數(shù)據(jù)結(jié)構(gòu).概念格的每個(gè)結(jié)點(diǎn)是一個(gè)形式概念,由兩部分組成:外延,即概念覆蓋的實(shí)例;內(nèi)涵,即概念的描述,實(shí)例的共同屬性特征.概念格通過(guò)結(jié)構(gòu)化的方式抽象出人類思維中的概念,通常概念格通過(guò)Hasse圖展現(xiàn)概念之間的泛化與特化偏序關(guān)系,每個(gè)概念以結(jié)點(diǎn)表示,如果概念A(yù)在概念B之上且二者有關(guān)聯(lián),則稱概念A(yù)是概念B的泛化,即概念A(yù)僅具有概念B的部分

2、屬性.對(duì)于圖1所示概念格,概念C1為概念C2,C3,C4的泛化;概念C2,C3,C4是概念C1的特化;C4E0,E2,E3, Ib表示概念C4具有外延E0,E2,E3和內(nèi)涵Ib.圖1概念格的Hasse圖形式概念分析的相關(guān)定義如下:定義1設(shè)X為所有對(duì)象的集合,Y為所有屬性的集合,形式背景是映射:XYf0,1,如果對(duì)象xX具有屬性yY,則f(x,y) =1,否則f(x,y) =0.一個(gè)包含對(duì)象集1,2,3,4,5,屬性集a,b,c,d的形式背景可用表1表示.表1形式背景的表示對(duì)象a b c d1 1 1 0 12 1 0 1 03 0 1 1 04 1 1 0 15 1 0 0 0定義2設(shè)f為XY

3、上的形式背景,對(duì)于XX,則C (X) = yY f(x,y) =1, xX表示X中全體對(duì)象所共有的屬性集.定義3設(shè)f為XY上的形式背景,對(duì)于Y Y,則C (Y) = xX f(x,y) =1, yY表示同時(shí)具有Y中所有屬性的對(duì)象集.定義4設(shè)f為XY上的形式背景,X X,Y Y,如果X=C (Y)且Y=C (X),則稱(X,Y)為f上的形式概念,X,Y分別稱為形式概念(X,Y)的外延和內(nèi)涵.XY表示XY上形式背景f的所有形式概念集.定義5設(shè)f為XY上的形式背景,如果(X1,Y1), (X2,Y2)是f的2個(gè)形式概念,規(guī)定:X1 X2 (X1,Y1)(X2,Y2),Y2 Y1 (X1,Y1)(X2

4、,Y2)(其中“”表示偏序關(guān)系).稱(X1,Y1)為(X2,Y2)的子概念, (X2,Y2)為(X1,Y1)的超概念.顯然,關(guān)系“”是集合XY上的一個(gè)偏序關(guān)系,可誘導(dǎo)出XY上的一個(gè)格結(jié)構(gòu),可以證明其為一個(gè)完備格15.相應(yīng)的上確界與下確界定義為l= (C (C (jJXj),jJYj),g= (jJXj,C (C (jJYj).其中, (Xj,Yj)XY;J為指標(biāo)集.該完備格稱為形式背景f的概念格,在無(wú)歧義情況下仍然記為XY.2基于FCA的模式匹配方法基于FCA的模式匹配方法分為3個(gè)階段:歸類階段,對(duì)給定的2個(gè)模式,分別根據(jù)字段名、字段描述和類型信息對(duì)源模式與目標(biāo)模式的字段進(jìn)行分類;FCA階段,

5、引入形式概念分析,以上述歸類信息以及結(jié)構(gòu)信息(主外鍵特征)為屬性,以源模式與目標(biāo)模式的各字段為對(duì)象構(gòu)建形式概念上下文,抽取出其中的概念,獲得偏序關(guān)系;相似度計(jì)算階段,通過(guò)文獻(xiàn)16的相似評(píng)估模型計(jì)算概念間的匹配度,以確定字段間的匹配.2.1歸類211名稱分類算法以樸素貝葉斯學(xué)習(xí)文本分類算法的核心算法LNBT與CNBT(Doc)17為基礎(chǔ),提出名稱分類算法.采用分隔符(如“first-name”分割成“firstname”)和字段表示(如“DepNo”分割后變成“DepNo”)等2種策略對(duì)字段分割;將分割后得到的單詞進(jìn)行擴(kuò)展,即根據(jù)應(yīng)用的領(lǐng)域找出單詞對(duì)應(yīng)的同義詞,形成單詞集.以每個(gè)源模式字段為一個(gè)

6、類別,對(duì)該字段單詞集中每個(gè)單詞進(jìn)行k-段解析,解析后的數(shù)據(jù)作為該字段類別的訓(xùn)練樣例,若k取值為3,則單詞“author”解析后的數(shù)據(jù)為“aut uth thohor”.評(píng)價(jià)貝葉斯歸類算法的技術(shù)指標(biāo)為運(yùn)行時(shí)間和歸類結(jié)果的平均估計(jì)概率兩方面.不同k值對(duì)算法產(chǎn)生不同的影響,為確定合適的k值,考察k分別為15的情況(見表2).文本分類算法在切割長(zhǎng)度為3的情況下,既可維持較高的估計(jì)概率,也具備較快的運(yùn)行時(shí)間,所以合適的k值為3.表2k值對(duì)樸素貝葉斯文本分類算法的影響k時(shí)間/s平均估計(jì)概率/%1 0969 0422 1365 0733 1109 0704 1001 0635 1089 053將目標(biāo)模式字段

7、3-段解析后的文本作為待分類數(shù)據(jù),送入已經(jīng)訓(xùn)練好的樸素貝葉斯學(xué)習(xí)器,計(jì)算出該目標(biāo)字段屬于各源字段類別的估計(jì)概率,各源模式字段以及按概率大小降序排列的前l(fā)項(xiàng)目標(biāo)字段,共同組成一類:piesi,et1,et2,etl,i1,m ,l=max(2,n /5),其中m為源模式中字段的數(shù)目,n為目標(biāo)模式字段的數(shù)目.所提出的名稱分類算法具體描述如下:SOURCE-NAME-ANALYSIS(SchemaS)SourceEleSet源模式中的所有字段集,m源模式字段數(shù),k3,類別集合C ,Samples ;按字段命名特征選取分割策略分割SourceEleSet中每個(gè)字段ei,i1,m;按選取的策略切割ei后

8、得到的所有單詞形成集合SourceEleIniSeti;對(duì)SourceEleSet中每個(gè)字段ei(i1,m ):ciei,文本集Ti ;CCci;擴(kuò)展SourceEleIniSeti中每個(gè)單詞的同義詞,并加入SourceEleIniSeti形成新集合SourceEleSeti;對(duì)SourceEleSeti中的每個(gè)單詞wt(t1, SourceEleSe-ti)進(jìn)行k段解析SamplesSamples類別ci與文本集Ti的匹配關(guān)系;Textt單詞wt解析后的文本字符串;TiTiTextt;使用樸素貝葉斯文本文類算法LNBT(Samples,C)學(xué)習(xí)樣例.TARGET-NAME-ANALYSIS(

9、SchemaT)TargetEleSet目標(biāo)模式中的所有字段,k3, EleValues-Mapping ,n目標(biāo)模式字段數(shù),i1,n,ResultSeti ;對(duì)TargetEleSet中每個(gè)字段ei(i1,n)進(jìn)行k段解析:Textt單詞wt解析后的文本字符串;ResultSetiResultSetiCNBT(Textt);EleValuesMappingEleValuesMapping字段名ei與解析結(jié)果集ResultSeti的匹配關(guān)系;返回EleValuesMapping;NAME-LEARNNER(SchemaS, SchemaT)m源模式字段數(shù),n目標(biāo)模式字段數(shù),lmax2,n5,E

10、leValuesMapping ,P ;SOURCE-NAME-ANALYSIS(SchemaS);EleValuesMappingEleValuesMappingTARGET-NAME-ANALYSIS(SchemaT);對(duì)C中每個(gè)分類ci,i1,m將EleValuesMapping中與ci匹配的各目標(biāo)字段按估計(jì)概率大小降序排列;取前l(fā)項(xiàng)匹配的目標(biāo)模式字段,與ci亦即ei共同組成分類向量piesi,et1,et2etl;PPpi;返回名稱分類向量集P;212描述分類算法字段的描述在語(yǔ)義上提供了對(duì)匹配的支持.與字段名比起來(lái),描述更能解釋字段的含義.由于字段描述的質(zhì)量很難控制,為了獲得更好的分類

11、效果,本文一方面在描述中加入了字段名,作為冗余信息加強(qiáng)描述的針對(duì)性;另一方面從可能的角度對(duì)字段名再描述,豐富字段的含義.每個(gè)源模式字段為一個(gè)類別,優(yōu)化后的源模式各字段描述作該類別的訓(xùn)練樣例,目標(biāo)模式的字段描述作為待分類文本,得出該目標(biāo)字段屬于各源字段類別的估計(jì)概率.同上,各源模式字段以及按概率大小降序排列的前j項(xiàng)目標(biāo)字段,共同組成一類:qiesi,et1,et2etl,i1,m ,l=max(2,n /5),其中m為源模式中字段的數(shù)目,n為目標(biāo)模式字段的數(shù)目.算法描述如下:SOURCE-DES-ANALYSIS(SchemaS)SourceEleSet源模式中的所有字段集,m源模式字段數(shù),類別

12、集合C , Samples ,j提供的該字段描述的總數(shù);對(duì)SourceEleSet中每個(gè)字段ei,i1,mciei,Ti ;CCci;對(duì)字段ei的所有可能的描述djTiTidj;SamplesSamples類別ci與描述集Ti的匹配關(guān)系;使用樸素貝葉斯文本文類算法LNBT(Samples, C)學(xué)習(xí)樣例;TARGET-DES-ANALYSIS(SchemaT)TargetEleSet目標(biāo)模式中的所有字段,n目標(biāo)模式字段數(shù),i1,n, EleValuesMapping ,di目標(biāo)模式各字段描述,ResultSeti ;對(duì)TargetEleSet中每個(gè)字段ei:ResultSetiResultSe

13、tiCLASSIFY-NAIVE-BAYES-TEXT(di);EleValuesMappingEleValuesMappingei與對(duì)應(yīng)ResultSeti的匹配關(guān)系;返回EleValuesMapping;DESCRIPTION-LEARNNER(SchemaS, SchemaT)m源模式字段數(shù),n目標(biāo)模式字段數(shù), lmax(2,n /5),EleValuesMapping ,Q ;SOURCE-DES-ANALYSIS(SchemaS);EleValuesMappingEleValuesMappingTARGET-DES-ANALYSIS(SchemaT);對(duì)C中每個(gè)分類ci,i1,m將E

14、leValuesMapping中與ci匹配的各目標(biāo)字段按估計(jì)概率大小降序排列;取前l(fā)項(xiàng)目標(biāo)模式字段,與ci亦即ei共同組成分類向量qiesi,et1,et2etl;QQqi;返回描述分類向量集Q.213類型分類策略通過(guò)類型分類策略,主要完成模式數(shù)據(jù)模式類型的整合,以MySQL數(shù)據(jù)庫(kù)為例,類型分為以下3類:數(shù)值:TINYINT, SMALLINT,MEDIUMINT,INT,BIGINT,FLOAT,DOUBLE,DECIMAL;字符串:CHAR,VARCHAR,TINYBLOB,BLOB,ME-DIUMBLOB, LONGBLOB, TINYTEXT, TEXT,MEDIUMTEXT, LON

15、GTEXT, ENUM, SET;日期及時(shí)間: DATE, TIME, DATETIME, TIMES-TAMP,YEAR.22形式概念分析在歸類階段的基礎(chǔ)之上,以主鍵、外鍵、名稱分類、描述分類、類型分類的類別名為屬性即I=k1,k2,p1,pm,q1,qm,Number, String, Time,其中,m為源模式字段的數(shù)目.同時(shí)以源模式及目標(biāo)模式中各字段為對(duì)象,構(gòu)建形式概念上下文.根據(jù)第1階段的歸類結(jié)果,各字段在對(duì)應(yīng)的分類處設(shè)值“1”.以形式概念上下文為基礎(chǔ),根據(jù)定義3,檢索形式概念上下文中的形式概念,根據(jù)定義4,確定形式概念之間的偏序關(guān)系,構(gòu)造概念格.2.3相似度計(jì)算采用文獻(xiàn)16的相似評(píng)

16、估模型,計(jì)算FCA階段概念格中各形式概念的相似度,定義如下:S (a,b) =(ab)(ab)+(a -b)+(1-) (b -a)(1)式中, (ab)表示概念格中a,b兩結(jié)點(diǎn)公共的且只有一條向上邊的祖先結(jié)點(diǎn)集合; (a -b)表示那些只在a中出現(xiàn)但未在b中出現(xiàn)的只有一條向上邊的祖先結(jié)點(diǎn)集合; (b -a)表示只在b中出現(xiàn)但未在a中出現(xiàn)的只有一條向上邊的祖先結(jié)點(diǎn)集合.本文取值為05,意為相似計(jì)算是對(duì)稱性的,即a與b的相似度等于b與a的相似度.以圖1為例,計(jì)算結(jié)點(diǎn)a =5與結(jié)點(diǎn)b =7間的相似度: (ab)= 2, (a -b)= 3, (b -a)= 4,S (a,b) =11+051+05

17、1=033.算法所得到的匹配結(jié)果為第2階段所學(xué)習(xí)到的概念之間的匹配度.模式的字段包含在概念的外延之中,可以看出,包含某特定字段的所有概念中內(nèi)涵最多的概念為完全覆蓋該字段的概念,通過(guò)找到完全覆蓋各字段的概念便可確定各字段之間的匹配度,本文取匹配閾值=05來(lái)獲取最終的匹配關(guān)系.算法整體描述如下:分別根據(jù)源模式和目標(biāo)模式的字段名以及字段描述對(duì)各字段進(jìn)行歸類.分別產(chǎn)生歸類集:pi esi,et1,et2,etl,i1,m ,l =max(2,n /5),qi esi,et1,et2,etl,i1,m ,l =max(2,n /5).其中,m為源模式字段數(shù),n為目標(biāo)模式字段數(shù).以第步的歸類信息以及類型歸

18、類信息、結(jié)構(gòu)信息(主、外鍵)三大類作為形式概念上下文中的屬性,即:I =k1,k2,p1,pm,q1,qm,Number, String,Time,其中,m為源模式字段數(shù).以源模式以及目標(biāo)模式中各字段作為對(duì)象,構(gòu)建形式概念上下文.以此為基礎(chǔ),構(gòu)建概念格.利用相似評(píng)估模型,即:S(a,b) =| (ab)| (ab)|+| (a -b)|+(1-) | (b -a)|,計(jì)算概念之間的相似度,取閾值=05獲取最終字段間的匹配關(guān)系.3實(shí)驗(yàn)結(jié)果為了評(píng)估匹配質(zhì)量,將本文算法與基于字典的模式匹配算法(DM)7以及基于Corpus的模式匹配算法(CBNB11)做了比較,評(píng)估采用3個(gè)通用指標(biāo):查準(zhǔn)率(匹配結(jié)果

19、中正確結(jié)果的比率):=T /P=T /(T+F );查全率(匹配結(jié)果中正確結(jié)果占實(shí)際結(jié)果的比率):=T /R;全面性(評(píng)估后期匹配所需要的工作量):=(2-1/).其中,T為正確識(shí)別的匹配結(jié)果;P為匹配方法返回的匹配結(jié)果;R為手工返回的匹配結(jié)果;F為錯(cuò)誤的匹配.實(shí)驗(yàn)中源模式為自主開發(fā)的在線目標(biāo)制定系統(tǒng)24Hourz,目標(biāo)數(shù)據(jù)庫(kù)為開源在線日志或論壇系統(tǒng),包括Textpattern, Pixelpos,tWordPress,Phpbb,Discuz.本實(shí)驗(yàn)分別將24Hourz與各目標(biāo)模式進(jìn)行匹配操作(見表3).表3各算法匹配質(zhì)量比較%模式名稱查準(zhǔn)率查全率全面性DM FCABSM CBNB DM F

20、CABSM CBNB DM FCABSM CBNBTextpattern092 085 086 065 084 084 057 069 070Pixelpost086 090 087 084 090 087 070 080 074WordPress058 085 083 055 089 083 015 073 066Phpbb081 085 084 073 082 082 056 068 066Discuz075 076 074 068 080 080 045 055 052avg078 084 083 069 085 083 049 069 066由表3可以看出,在問(wèn)題復(fù)雜度較小的設(shè)計(jì)規(guī)范的

21、Textpattern模式匹配問(wèn)題中,基于字典的匹配方法能夠快速準(zhǔn)確地找到匹配關(guān)系,具備較高的查準(zhǔn)率092,但查全率不及基于Corpus及基于FCA的算法策略,只有065.當(dāng)問(wèn)題規(guī)模擴(kuò)大或者模式設(shè)計(jì)不規(guī)范時(shí),只借助于字典或者僅通過(guò)單純的文本相似性的判斷不能挖掘模式中蘊(yùn)含的匹配關(guān)系,同時(shí)也不能解決多對(duì)多的匹配問(wèn)題,具體表現(xiàn)為查全率較低,在WordPress以及Discuz的匹配查全率方面,DM僅為055與068,CBNB相對(duì)優(yōu)越但也僅有083與080,不及FCABSM的089與080.在字段及描述歸類的基礎(chǔ)之上,再借助于類型歸類和結(jié)構(gòu)信息,通過(guò)FCA整合,獲得最終的匹配結(jié)果的算法策略隨著問(wèn)題規(guī)模

22、的擴(kuò)大以及復(fù)雜度的增加,能夠有效獲取匹配項(xiàng),保證查準(zhǔn)率與查全率,減少后期人工篩選的工作量.在處理相對(duì)復(fù)雜的Phpbb及Discuz的匹配問(wèn)題時(shí), FCABSM的全面性優(yōu)勢(shì)不明顯,分別只有068與055,而CBNB為066與052,這是由于FCABSM在借助多樣信息的同時(shí)也帶來(lái)了噪聲與污染.因此,如何為FCA提供更精準(zhǔn)的屬性特征,如何引入匹配依據(jù)的權(quán)重,如何提高模式信息的質(zhì)量從而減少信息量的增加帶來(lái)的負(fù)面影響,是進(jìn)一步研究的重點(diǎn).為了考察同義詞對(duì)算法的影響,在算法的歸類階段中,對(duì)源模式各字段切割之后不再進(jìn)行同義詞及領(lǐng)域等價(jià)詞的擴(kuò)展.將去除同義詞的算法與完整算法在處理aims-posts匹配問(wèn)題上

23、的表現(xiàn)作為比較:Aims(aim-id, aim-author-id, aim-date, aim-description, aim-title, aim-type), Posts(post-id,post-writer, post-date, post-title, post-conten,tpost-category, post-type),正確匹配結(jié)果為Aims(id, a-id, date, des, title, type)Posts( id, a-id,date, title, des, type,“null”).比較結(jié)果如表4所示.表4同義詞對(duì)算法匹配結(jié)果與質(zhì)量的影響匹配結(jié)果和質(zhì)量帶同義詞去除同義詞aim-id-post-id T Taim-author-id-post-writer T Taim-title-pos