第十講 句法模式識別

1、1第十講第十講句法模式識別句法模式識別一、一、基本概念基本概念1、結(jié)構(gòu)模式識別：、結(jié)構(gòu)模式識別：有一些模式識別任務(wù)，不能在特征空間中用統(tǒng)計模式識別的方法得到解決。漢字的識別：漢字有偏旁部首、筆劃構(gòu)成字符的識別：字符的字體不影響識別語言的識別：語言由音節(jié)、字、詞構(gòu)成圖像識別：畫面分割，目標(biāo)識別生物識別：基因序列，染色體結(jié)構(gòu)，心電圖分類定義：以結(jié)構(gòu)基元為基礎(chǔ)，利用模式的結(jié)構(gòu)信息完成分類的過程，稱為“結(jié)構(gòu)模式識別”。其中“基元”指構(gòu)成模式結(jié)構(gòu)

2、信息的基本單元，本身不包含有意義的結(jié)構(gòu)信息。基元的選取與應(yīng)用有關(guān)：文字：筆劃或偏旁部首作為基元語音：音素作為基元心電圖：收縮波和擴(kuò)張波作為基元圖形：邊緣線段、角點(diǎn)都可作為基元accbbbdddcccbbbddabcd輪廓基元輪廓基元討論：結(jié)構(gòu)模式識別是與統(tǒng)計模式識別完全不同的一大類模式識別問題，一個基于結(jié)構(gòu)信息，一個基于特征值結(jié)構(gòu)模式識別不僅能完成分類，還可以得到每個模式的結(jié)構(gòu)性質(zhì)結(jié)構(gòu)模式識別的依據(jù)是模式間結(jié)構(gòu)上的“相似性”，這種相似度

3、的度量不能用一般特征空間中的距離來表示結(jié)構(gòu)模式識別可以采用句法方法、拓?fù)浞治龇椒?、圖論方法等多種方法基元提取和分類器訓(xùn)練上的困難使得結(jié)構(gòu)模式識別方法仍未成熟結(jié)構(gòu)模式識別系統(tǒng)的模式信息通常來源于圖像、音頻等多媒體信息源2、句法模式識別、句法模式識別（1）句法模式識別的定義：句法模式識別是利用模式的結(jié)構(gòu)信息，以形式語言理論為基礎(chǔ)來進(jìn)行結(jié)構(gòu)3預(yù)處理特征提?。ɑ崛。┚浞ǚ治鑫姆ㄍ茢嗄Ｊ叫畔⒎诸惤Y(jié)果類別文法訓(xùn)練過程分類過程（1（句法分析：判斷

4、一個樣本是否符合一定的文法，從而得到該樣本與已知類別的相似性。（2（文法推斷：從分好類的訓(xùn)練集中獲得該類所有樣本的共同特征，形成代表每個類別的文法規(guī)則。利用形式語言理論完善和堅實(shí)的數(shù)學(xué)基礎(chǔ)，可用句法分析的方法來實(shí)現(xiàn)結(jié)構(gòu)模式識別問題的求解二、二、形式語言理論形式語言理論1、基本概念：基本概念：（1）字母表：與所研究的問題有關(guān)的符號集合。例：V1=ABCDV2=abcdV3=0268（2）句子(鏈)：由字母表中的符號所組成的有限長度的符號串

5、。例如有字母表01，則0100010110就是有效句子的集合。不包括任何符號的句子稱為空句，記為λ。V：由字母表V中的符號組成的所有句子的集合，包括空句子λ在內(nèi)。例：V＝λ01001V＋：不包括空句子在內(nèi)的句子集合，即V＋＝V－(λ)（3）句子(鏈)的長度：句子所包含的符號數(shù)目，例:|a3b3c3|=9（4）語言：由字母表中的符號組成的句子集合，用L表示。例：字母表V=abL1=abaababab有限語言L2=anbm|nm=012….