數(shù)學(xué)建?；谛螒B(tài)特征葉子識別聚類論文

1、. 西北大學(xué)研究生數(shù)學(xué)建模競賽承諾書我們仔細(xì)閱讀了西北大學(xué)數(shù)學(xué)建模競賽的競賽規(guī)則與賽場紀(jì)律。我們完全明白，在競賽開場后參賽隊(duì)員不能以任何方式包括、電子、網(wǎng)上咨詢等與隊(duì)外的任何人研究、討論與賽題有關(guān)的問題。我們知道，抄襲別人的成果是違反競賽規(guī)則的, 如果引用別人的成果或其他公開的資料包括網(wǎng)上查到的資料，必須按照規(guī)定的參考文獻(xiàn)的表述方式在正文引用處和參考文獻(xiàn)中明確列出。我們重承諾，嚴(yán)格遵守競賽規(guī)則，以保證競賽的公正、公平性。如有違反競賽規(guī)則的行為，我們將受到嚴(yán)肅處理。我們參賽的題目是(從A/B中選擇一項(xiàng)填寫)：C參賽隊(duì)為：1069705所屬院系請?zhí)顚懲暾娜簲?shù)學(xué)學(xué)院、信息科學(xué)與技術(shù)學(xué)院參賽隊(duì)員

2、 (打印并簽名) : 1.耿妍2.朱銳3.衛(wèi)柄岐 日期：2015 年5月3日評閱由校組委會評閱前進(jìn)展：西北大學(xué)數(shù)學(xué)建模競賽專用頁評閱(由校組委會評閱前進(jìn)展):評閱記錄:評閱人評分備注評獎結(jié)果:. 世界上沒有兩片一樣的葉子摘要本文通過分析葉子圖片，建立了形狀、邊緣、顏色特征的數(shù)學(xué)模型，使得任意給出測試的葉子圖片，我們能判斷出它為*種樹葉的概率，對于大量的樹葉樣本圖片我們可以根據(jù)特征的相似性大小進(jìn)展分類。在問題一中，我們給形狀、邊緣、顏色特征分別建立數(shù)學(xué)模型并將這些特征數(shù)字化。對于形狀我們又將其細(xì)分為外表積、矩形度、伸長度，但是觀察所給的數(shù)據(jù)葉片有可能發(fā)生旋轉(zhuǎn)、平移、伸縮，為了克制這些外在因素造成

3、的誤差，我們添加不變特征，這樣我們的特征描述就比擬細(xì)致。對于邊緣這一特征，由于葉子邊緣函數(shù)沒有規(guī)性，而且在二維上表示，這樣對我們的研究帶來很大困難，所以我們通過傅里葉描述子將二維圖像通過復(fù)坐標(biāo)的形式降到一維，從而簡化了問題。對于顏色這一特征，我們將用顏色矩來表示。與顏色直方圖相比，該方法的另一個好處在于無需對特征進(jìn)展向量化。在問題二中，通過分析有關(guān)葉子的形狀，邊緣，顏色的數(shù)據(jù)可以得出葉子的形態(tài)學(xué)數(shù)據(jù)是服從正態(tài)分布的，因此我們可以算出葉子的每個形態(tài)學(xué)數(shù)據(jù)樣本的均值和方差，即可得到樣本每一個形態(tài)學(xué)數(shù)據(jù)的高斯分布圖，但比擬兩種葉子的同一個形態(tài)學(xué)數(shù)據(jù)的時候在一個圖像中卻顯示了兩個正態(tài)分布的圖像。所以綜

4、合多種特點(diǎn)，我們選擇用貝葉斯分類器對給出的測試葉子計(jì)算為*種葉片的概率。在問題三中，我們將葉片的相似性轉(zhuǎn)化為數(shù)學(xué)語言，即距離。把每個樣品看做一個點(diǎn)，將它們對應(yīng)的特征值為點(diǎn)的值，通過歐幾里得距離的大小來判斷葉片的相似性。在這一問中我們分別考慮了獨(dú)立形狀、邊緣、顏色和綜合考慮這些特征，得出了特征越多，分化越細(xì)。并且在這一問中我們通過譜系圖的建立使得分類結(jié)果更清晰。關(guān)鍵詞 不變矩陣法，貝葉斯算法，聚類分析. 一、問題描述1、通過對所給的二百二十組葉子圖片的觀察，發(fā)現(xiàn)形狀，邊緣，顏色是區(qū)分不同種類葉子的最顯著特征，所以我們的目的就是將葉子的形狀，邊緣，顏色特征通過函數(shù)數(shù)字化，從而定量的分析了不同種類葉

5、子的特征是不同的。2、同一類植物的兩片葉子特征經(jīng)過同一個函數(shù)計(jì)算，其值不可能完全一樣，所以我們需要根據(jù)問題一的模型算出給出的測試葉子有可能是那種植物，它的概率有多大。3、對于任意給出的大量葉片，根據(jù)葉子特征的相似性，將這些葉子進(jìn)展歸類。二、問題分析問題一：題目中給出的只有葉子的圖片，我們只能通過肉眼看出它的形狀、顏色、邊緣。要求出數(shù)學(xué)模型，將圖片數(shù)字化就需要知道圖片在計(jì)算機(jī)中的存儲方式。它是被分成像素，用每個像素的灰度值去存儲。這樣一來我們就可以將圖片用離散的點(diǎn)來表示。從而構(gòu)建了它們的特征模型。問題二：要想知道所給葉子是什么葉子，就要綜合考慮它們的特征，但是葉片的三個特征是相互獨(dú)立的。如何能綜

6、合多個特征求概率就是我們要解決的。問題三：葉子的相似性就是由他們的特征所決定，這在問題一將被解決。根據(jù)這些特征將葉子進(jìn)展分類，所以選取那種分類方法就是本問題的關(guān)鍵。三、根本假設(shè)1、葉片沒有殘損卷曲2、不考慮紋理特征四、符號說明符號意義每個像素點(diǎn)的灰度值灰度化后的二值矩陣葉子高度葉子寬度葉子外表積矩形度伸長度不變特征一階矩平均值顏色二階矩標(biāo)準(zhǔn)方差三階矩三次根非對稱性圖像第個顏色通道分量中灰度級為的像素出現(xiàn)的概率邊緣復(fù)坐標(biāo)五、模型的建立與求解5.1問題一：5.1.1形狀模型建立與求解：圖像在計(jì)算機(jī)里被分成像素，每個像素的灰度值被整數(shù)化。為了防止圖片平移，旋轉(zhuǎn)，縮放帶來的誤差，我們首先將圖片歸一化，

7、使之變?yōu)榫哂泄潭?biāo)準(zhǔn)形式。不考慮圖片顏色我們將在形狀方面忽略顏色的影響，即將其灰度化，設(shè)灰度化后的圖像二值矩陣為。我們將形狀分為了十個特征來描述:外表積、矩形度、伸長度以及不變矩陣的七個不變特征。對于不變矩陣的七個不變特征，我們選擇用二階和三階中心距來構(gòu)造，因?yàn)檫@樣能使它們在連續(xù)圖像變換下可以保持平移、縮放、旋轉(zhuǎn)不變。形狀模型如下:，；歸一化的中心距離定義為：，其中七個不變矩為形狀模型仿真：首先，我們?nèi)我膺x出一種葉子圖片，圖(5-1)是附件中135號樣品圖片的一個代表;圖(5-2)是附件中153號樣品圖片(5-1) (5-2)通過對葉子模型的運(yùn)行，我們得到了每片葉子的十個特征值，由于空間有限，

8、我們只列出前十個數(shù)據(jù)。其中行為葉片特征，列為葉片序號。如圖，(5-3)是樣品135的特征值；(5-4)是樣品153的特征值葉片的形狀特征圖(5-3)(樣品135)葉片的形狀特征圖(5-4)(樣品153)5.1.2邊緣模型的建立對于這一特征，由于葉子邊緣函數(shù)沒有規(guī)性，并且在二維上，這樣對我們的研究帶來很大困難，所以我們選擇用傅里葉描述子把二維圖像輪廓簡化成一維問題進(jìn)展處理。傅立葉描述子的根本思想是對圖像邊界進(jìn)展傅立葉變換作為形狀描述。首先假定物體的邊緣表示為一個坐標(biāo)序列,其中。用復(fù)數(shù)來表示每一個坐標(biāo)，即，對于封閉邊界，這一序列是周期的，為N，這樣二維坐標(biāo)下的邊界就可以在一維空間上表示。盡管對序列

9、進(jìn)展了重新解釋，但邊界本身的性質(zhì)并未改變。當(dāng)然，這種表示方法的一個優(yōu)點(diǎn)就是：把二維問題簡化為一維問題。的離散傅立葉變換DFT表示為：(1)復(fù)系數(shù)叫做邊界的傅立葉描述符.這些系數(shù)的反向傅立葉變換存在于： (2)傅立葉變換的高頻分量對應(yīng)細(xì)節(jié)而低頻分量對應(yīng)總體形狀，在圖像檢索和圖像識別中使用傅立葉描述子時，為了減少使用描述子進(jìn)展圖像相似度判別時的計(jì)算量，可以只用一局部對應(yīng)低頻分量的傅立葉系數(shù)來近似描述邊界形狀。邊緣模型仿真：同樣對樣品135和樣品153進(jìn)展分析，表中的橫坐標(biāo)表示邊緣的周長、面積、周長面積比、圓形度、方形度、比照度?？v坐標(biāo)為前十個圖片的序號。其中(5-5)是樣品135對應(yīng)的局部邊緣特征

10、；(5-6)是樣品153對應(yīng)的局部邊緣特征。 葉片的邊緣特征圖(5-5)(樣品135)葉片的邊緣特征圖(5-6) (樣品153)5.1.3顏色模型建立：對于這一特征，我們將用顏色矩來表示。與顏色直方圖相比，該方法的另一個好處在于無需對特征進(jìn)展向量化。因此，圖像的顏色矩一共只需要9個分量3個顏色分量，每個分量上3個低階矩，僅采用顏色的一階矩，二階矩，和三階矩就足以表達(dá)圖像的顏色分布。一階中心矩，二階中心矩和三階中心矩分別表示圖像或子區(qū)域圖像的平均顏色，標(biāo)準(zhǔn)方差和三次根非對稱性。三個顏色矩的數(shù)學(xué)定義：(1)(2)(3)由于每個像素具有顏色空間的三個顏色通道，因此圖像的顏色矩由9個分量來描述：顏色模

11、型仿真：對樣品135和樣品153通過模型求解得到了其對應(yīng)的局部圖(5-7)、(5-8)。圖中的橫坐標(biāo)表示圖像顏色矩的九個分量。葉片的顏色特征圖(5-7)(樣品135)葉片的顏色特征圖(5-8)(樣品153)5.2問題二5.2.1模型建立與求解通過特征提取得到有關(guān)葉子的形狀，邊緣，顏色的數(shù)據(jù)。以下我們就以樣品135的矩形度為例,通過矩形度生成分布圖可以發(fā)現(xiàn)葉子的形態(tài)學(xué)數(shù)據(jù)是服從正態(tài)分布的，因此我們可以計(jì)算出葉子的每個形態(tài)學(xué)數(shù)據(jù)樣本的均值和方差，即可得到樣本每一個形態(tài)學(xué)數(shù)據(jù)的高斯分布圖。葉子矩形度數(shù)據(jù)生成的分布圖(5-9)(樣品135)通過上面的圖可以看出，葉子形態(tài)學(xué)的數(shù)據(jù)成正太分布，正好符合貝葉

12、斯分類的先決條件。因此，我們可以利用貝葉斯來進(jìn)展葉子的分類。貝葉斯原理：貝葉斯公式：代表類別，代表特征，我們做出預(yù)測肯定是利用當(dāng)前的特征，來判斷輸出的類別。 我們可以看到貝葉斯公式先驗(yàn)與后驗(yàn)概率之間的轉(zhuǎn)換，很明顯，在我們的定義里面是后驗(yàn)概率，也是我們想要得到的東西。而我們先驗(yàn)概率,以及條件概率。對于多類的分類來說，都是一樣，所以此項(xiàng)可以略去。那最終的結(jié)果就是計(jì)算這一項(xiàng)，是可以通過觀察來解決的,我們有三類種子可以通過觀察知道。上面對于此項(xiàng)的解釋是在類中，特征出現(xiàn)的概率，其實(shí)簡單來講，就是的概率密度。這樣通過先驗(yàn)概率到后驗(yàn)概率的轉(zhuǎn)換即可進(jìn)展分類。形態(tài)學(xué)通過貝葉斯分類這里是針對葉子數(shù)據(jù)中的一個形態(tài)學(xué)

13、數(shù)據(jù)進(jìn)展的分析，當(dāng)比擬兩種葉子的同一個形態(tài)學(xué)數(shù)據(jù)的時候通過計(jì)算類條件概率曲線，可以分辨出該特征分類是否明顯。如下：是顏色矩形成的類條件概率。我們是通過對樣品135和樣品153進(jìn)展實(shí)驗(yàn)。如圖是樣品135和樣品153的顏色矩特征的分析顏色特征類條件概率密度曲線(5-10)(樣品135和樣品153)從上圖可以看出產(chǎn)生的有關(guān)顏色矩特征的概率密度曲線的閾值可以很容易的分開兩類葉子。因此，顏色特征是對樣品135和樣品153分類的重要依據(jù)。通過計(jì)算形成顏色特征后驗(yàn)概率密度曲線。顏色特征類后驗(yàn)概率曲線(5-11)(樣品135和樣品153)通過后驗(yàn)概率曲線圖也很容易看出兩類通過顏色分類很容易。實(shí)驗(yàn)結(jié)果：選取一類

14、似135類中的葉子，通過計(jì)算判定是135類的概率是0.8234。是153類葉子的概率為0.1766。通過比擬可以說明利用顏色特征，并且利用貝葉斯分類器分類效果顯著。為了增加實(shí)驗(yàn)的可靠性，我們有利用邊緣特征和形狀特征類進(jìn)一步分析驗(yàn)證。下列圖是圖片樣品135和樣品153邊緣特征形成的類條件概率。邊緣特征類條件概率密度曲線(5-12) (樣品135和樣品153)從上圖可以看出產(chǎn)生的有關(guān)邊緣特征的概率密度曲線有重疊局部，不過影響不是很大。因此，邊緣特征也是樣本135與153類葉子分類的重要依據(jù)。后驗(yàn)概率圖為：邊緣特征后驗(yàn)概率曲線(5-13)(樣本135和 樣本153)我們通過邊緣特征的分類，通過給定圖

15、片進(jìn)展測試，分別為135類葉子的概率為0.8763，為153類葉子的概率為0.1237。再通過形狀的特征進(jìn)展分類實(shí)驗(yàn)，獲得類條件概率如下列圖：形狀特征類條件概率密度曲線(5-14)(樣本135 樣本153)我們通過形狀特征的周長進(jìn)展分類，可以看出分類結(jié)果不是很明顯，所以必須綜合三個特征進(jìn)展分類。獲得后驗(yàn)概率如下列圖：形狀特征后驗(yàn)概率曲線(5-15)(樣本135 樣本153)通過上圖的分析，形狀特征對135類和153類的葉子分類效果不是很好，因此需要綜合三個特征進(jìn)展分類。通過給定測試圖片，分別為135類葉子的概率為0.6088，為153類葉子的概率為0.3912。三個特征綜合進(jìn)展分類:為什么利用

16、貝葉斯公式就可以做到區(qū)別類別的效果呢？在這里，先引入一個分布函數(shù)高斯分布公式： 利用一維數(shù)據(jù)生成三個均值不同，標(biāo)準(zhǔn)差也不一樣的高斯函數(shù)利用高斯密度函數(shù)的優(yōu)點(diǎn)：通過我們計(jì)算，每一類的均值和方差差距大。三個特征是相互獨(dú)立的，我們通過高斯函數(shù)擬合，利用貝葉斯分類器進(jìn)展分類。 通過三個特征綜合產(chǎn)生如下結(jié)果三個特征類條件概率密度曲線(5-16)(樣本135 樣本153) 從上圖可以看出分類界限更加明顯，利用三個特征的相互獨(dú)立，并且通過高斯函數(shù)的擬合，更加準(zhǔn)確的完成了分類。總特征的后驗(yàn)概率圖為：三個特征后驗(yàn)概率曲線(5-17)(樣本135 樣本153)通過給定測試圖片，分別為135類葉子的概率為0.998

17、，為153類葉子的概率為0.002。5.3問題三5.3.1模型建立與求解通過對葉子的特征提取，我們得到了葉子有關(guān)形狀，邊緣，顏色的特性，這些特征值從其所屬的角度反映了葉子的特征，對于分析的葉子樣本，其對應(yīng)的葉子的特征與樣本之間是存在關(guān)系的，我們可以利用譜系分析的方法來對葉子進(jìn)展聚類分析，即用葉子不同的特征對葉子進(jìn)展分類，這里使用譜系分析中的歐式距離法對其進(jìn)展距離的計(jì)算，運(yùn)用最短距離法對葉子進(jìn)展聚類處理。我們通過構(gòu)建進(jìn)化樹來對葉子進(jìn)展譜系分析。葉子的種類是由多個特征共同決定，所以我們將運(yùn)用歐式距離法進(jìn)展距離的計(jì)算運(yùn)用最短距離法來構(gòu)建進(jìn)化樹。譜系分析的過程大致分成四步： = 1 * GB3 * M

18、ERGEFORMAT 由于指標(biāo)變量相差比擬大，所以要對數(shù)據(jù)預(yù)處理標(biāo)準(zhǔn)化初始數(shù)據(jù)的矩陣中數(shù)值的大小不一，距離法計(jì)算的是兩兩樣本之間的歐式距離，其中*一個距離相比擬其他距離如果過大，或者*一個距離相比擬其他距離過小都會影響聚類的結(jié)果，即會犯大數(shù)吃小數(shù)的毛病。所以對矩陣的預(yù)處理標(biāo)準(zhǔn)化就顯得尤為重要，以下是矩陣標(biāo)準(zhǔn)化的過程：為了使抽樣樣本改變時它仍能保持相對的穩(wěn)定，我們使用標(biāo)準(zhǔn)化變化：實(shí)行此變換后，數(shù)據(jù)均值為，標(biāo)準(zhǔn)差為，消去了量綱的影響。我們選取了葉子樣本中的135樣本和153樣本對其進(jìn)展了數(shù)據(jù)的歸一化處理，我們在樣本135中選取了10個樣本，依次為1-10，在樣本153中選取了10個樣本，為11-2

19、0，對數(shù)據(jù)統(tǒng)一的進(jìn)展了歸一化處理處理后的結(jié)果如下列圖: 歸一化處理后的葉子邊緣特征矩陣(5-18)(樣品135和樣品153) = 2 * GB3 * MERGEFORMAT 構(gòu)造關(guān)系矩陣這一步中我們要測量樣本之間的相似程度，即用歐式距離來表示它們之間的親疏程度，樣本之間的特征值越相近他們之間的歐式距離就越小，歐式距離從*些方面反映了兩個樣本之間的關(guān)系，即相似的樣本之間的距離較小，而相異的樣本之間的距離較大。首先每個樣品有個指標(biāo)從不同方面描述其性質(zhì)，形成一個維的向量。如果把個樣品看成維空間中的個點(diǎn)，則兩個樣品間的相似程度就可以用維空間的兩點(diǎn)距離公式來度量。由于在分類之前我們已經(jīng)做了標(biāo)準(zhǔn)化處理，所

20、以本文中我們定義的距離公式為：歐幾里德距離Euclidean distance(euclidean)Euclidean distance在中使用的是函數(shù)，函數(shù)實(shí)現(xiàn)了樣本之間的計(jì)算 計(jì)算中各行向量的相互距離(是一個行列的矩陣)。這里要特別注意，是一個長為的行向量。可以這樣理解矩陣的生成：首先生成一個的距離方陣，由于該方陣是對稱的，且對角線上的元素都為，所以取此方陣的下三角元素，按照中矩陣的按列存儲的原則，此下三角各元素的引索排列即為、.、。如果使其轉(zhuǎn)化為矩陣形式輸出如果使其轉(zhuǎn)化為矩陣形式輸出則可以用命令將此行向量轉(zhuǎn)換為原距離方陣.這里選取了樣本135和樣本153的邊緣特征數(shù)據(jù)進(jìn)展了處理，樣本1-

21、10是樣本135的而樣本11-20是樣本153的數(shù)據(jù)，它們之間的距離矩陣如下列圖所示：葉子邊緣特征的距離方陣(5-19)(樣品135和樣品153) = 3 * GB3 * MERGEFORMAT 聚類根據(jù)系統(tǒng)聚類法進(jìn)展分類上一步中確定了距離矩陣后就可以對已有的樣本進(jìn)展聚類了，距離相近的樣本就先聚合成一類，距離相遠(yuǎn)的就后聚成一類，過程一直進(jìn)展下去，每個樣品總能聚到適宜的類中，在每次聚類過程中都是以距離遠(yuǎn)近做為標(biāo)準(zhǔn)。在此過程中我們定義類與之間的距離為兩類最近樣品的距離：在矩陣中尋找距離最近的樣本，使其進(jìn)展聚類，并且緊接著生成新的類。當(dāng)類與合并為一個新類記為，則任一類的距離為此時矩陣中的樣本數(shù)變少了

22、，減少的樣本數(shù)為參與聚合的樣本數(shù)減去生成樣本數(shù)，每次產(chǎn)生聚類的過程中都會使的矩陣維數(shù)減小。通俗點(diǎn)說，即距離最小的事物首先消亡了完成聚類，產(chǎn)生新類，但是在他們消亡的過程中還保存了他們與其他外物之間的關(guān)系。每次聚類完成后關(guān)系矩陣維數(shù)都會相應(yīng)的減小，直至關(guān)系矩陣變?yōu)榈木仃嚂r即完成了樣本的聚類。 在中運(yùn)用函數(shù)對矩陣進(jìn)展聚類，使用最短距離法“對之前產(chǎn)生的向量進(jìn)展數(shù)據(jù)處理葉子邊緣特征的生成樹(5-20)(樣品135和樣品153)從上圖可以看出產(chǎn)生的有關(guān)葉片的邊緣聚類效果還是很可觀的2個樣本大致聚類成了兩類，也就是葉子樣本135類和葉子樣本153類。樣本3，4，5，6，7，8，9，10首先聚成了一類而樣本11，13，14，15，16，17，18，19