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

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

2、屬性.對于圖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為所有對象的集合,Y為所有屬性的集合,形式背景是映射:XYf0,1,如果對象xX具有屬性yY,則f(x,y) =1,否則f(x,y) =0.一個包含對象集1,2,3,4,5,屬性集a,b,c,d的形式背景可用表1表示.表1形式背景的表示對象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、上的形式背景,對于XX,則C (X) = yY f(x,y) =1, xX表示X中全體對象所共有的屬性集.定義3設(shè)f為XY上的形式背景,對于Y Y,則C (Y) = xX f(x,y) =1, yY表示同時具有Y中所有屬性的對象集.定義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個形式概念,規(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上的一個偏序關(guān)系,可誘導(dǎo)出XY上的一個格結(jié)構(gòu),可以證明其為一個完備格15.相應(yīng)的上確界與下確界定義為l= (C (C (jJXj),jJYj),g= (jJXj,C (C (jJYj).其中, (Xj,Yj)XY;J為指標(biāo)集.該完備格稱為形式背景f的概念格,在無歧義情況下仍然記為XY.2基于FCA的模式匹配方法基于FCA的模式匹配方法分為3個階段:歸類階段,對給定的2個模式,分別根據(jù)字段名、字段描述和類型信息對源模式與目標(biāo)模式的字段進(jìn)行分類;FCA階段,

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

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

7、3-段解析后的文本作為待分類數(shù)據(jù),送入已經(jīng)訓(xùn)練好的樸素貝葉斯學(xué)習(xí)器,計算出該目標(biāo)字段屬于各源字段類別的估計概率,各源模式字段以及按概率大小降序排列的前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中每個字段ei,i1,m;按選取的策略切割ei后

8、得到的所有單詞形成集合SourceEleIniSeti;對SourceEleSet中每個字段ei(i1,m ):ciei,文本集Ti ;CCci;擴(kuò)展SourceEleIniSeti中每個單詞的同義詞,并加入SourceEleIniSeti形成新集合SourceEleSeti;對SourceEleSeti中的每個單詞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 ;對TargetEleSet中每個字段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);對C中每個分類ci,i1,m將EleValuesMapping中與ci匹配的各目標(biāo)字段按估計概率大小降序排列;取前l(fā)項(xiàng)匹配的目標(biāo)模式字段,與ci亦即ei共同組成分類向量piesi,et1,et2etl;PPpi;返回名稱分類向量集P;212描述分類算法字段的描述在語義上提供了對匹配的支持.與字段名比起來,描述更能解釋字段的含義.由于字段描述的質(zhì)量很難控制,為了獲得更好的分類

11、效果,本文一方面在描述中加入了字段名,作為冗余信息加強(qiáng)描述的針對性;另一方面從可能的角度對字段名再描述,豐富字段的含義.每個源模式字段為一個類別,優(yōu)化后的源模式各字段描述作該類別的訓(xùn)練樣例,目標(biāo)模式的字段描述作為待分類文本,得出該目標(biāo)字段屬于各源字段類別的估計概率.同上,各源模式字段以及按概率大小降序排列的前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ù);對SourceEleSet中每個字段ei,i1,mciei,Ti ;CCci;對字段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 ;對TargetEleSet中每個字段ei:ResultSetiResultSe

13、tiCLASSIFY-NAIVE-BAYES-TEXT(di);EleValuesMappingEleValuesMappingei與對應(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);對C中每個分類ci,i1,m將E

14、leValuesMapping中與ci匹配的各目標(biāo)字段按估計概率大小降序排列;取前l(fā)項(xiàng)目標(biāo)模式字段,與ci亦即ei共同組成分類向量qiesi,et1,et2etl;QQqi;返回描述分類向量集Q.213類型分類策略通過類型分類策略,主要完成模式數(shù)據(jù)模式類型的整合,以MySQL數(shù)據(jù)庫為例,類型分為以下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;日期及時間: DATE, TIME, DATETIME, TIMES-TAMP,YEAR.22形式概念分析在歸類階段的基礎(chǔ)之上,以主鍵、外鍵、名稱分類、描述分類、類型分類的類別名為屬性即I=k1,k2,p1,pm,q1,qm,Number, String, Time,其中,m為源模式字段的數(shù)目.同時以源模式及目標(biāo)模式中各字段為對象,構(gòu)建形式概念上下文.根據(jù)第1階段的歸類結(jié)果,各字段在對應(yīng)的分類處設(shè)值“1”.以形式概念上下文為基礎(chǔ),根據(jù)定義3,檢索形式概念上下文中的形式概念,根據(jù)定義4,確定形式概念之間的偏序關(guān)系,構(gòu)造概念格.2.3相似度計算采用文獻(xiàn)16的相似評

16、估模型,計算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,意為相似計算是對稱性的,即a與b的相似度等于b與a的相似度.以圖1為例,計算結(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)涵最多的概念為完全覆蓋該字段的概念,通過找到完全覆蓋各字段的概念便可確定各字段之間的匹配度,本文取匹配閾值=05來獲取最終的匹配關(guān)系.算法整體描述如下:分別根據(jù)源模式和目標(biāo)模式的字段名以及字段描述對各字段進(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)模式中各字段作為對象,構(gòu)建形式概念上下文.以此為基礎(chǔ),構(gòu)建概念格.利用相似評估模型,即:S(a,b) =| (ab)| (ab)|+| (a -b)|+(1-) | (b -a)|,計算概念之間的相似度,取閾值=05獲取最終字段間的匹配關(guān)系.3實(shí)驗(yàn)結(jié)果為了評估匹配質(zhì)量,將本文算法與基于字典的模式匹配算法(DM)7以及基于Corpus的模式匹配算法(CBNB11)做了比較,評估采用3個通用指標(biāo):查準(zhǔn)率(匹配結(jié)果

19、中正確結(jié)果的比率):=T /P=T /(T+F );查全率(匹配結(jié)果中正確結(jié)果占實(shí)際結(jié)果的比率):=T /R;全面性(評估后期匹配所需要的工作量):=(2-1/).其中,T為正確識別的匹配結(jié)果;P為匹配方法返回的匹配結(jié)果;R為手工返回的匹配結(jié)果;F為錯誤的匹配.實(shí)驗(yàn)中源模式為自主開發(fā)的在線目標(biāo)制定系統(tǒng)24Hourz,目標(biāo)數(shù)據(jù)庫為開源在線日志或論壇系統(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可以看出,在問題復(fù)雜度較小的設(shè)計規(guī)范的

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

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

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同義詞對算法匹配結(jié)果與質(zhì)量的影響匹配結(jié)果和質(zhì)量帶同義詞去除同義詞aim-id-post-id T Taim-author-id-post-writer T Taim-title-pos