圖像分類器技術(shù)報(bào)告

研究生技術(shù)報(bào)告題目：圖像分類器編號(hào)：2011001執(zhí)筆人：趙劍瑩完成時(shí)間：2011.3.1PAGEPAGE5圖像分類器技術(shù)報(bào)告課題意義為了提高圖像搜索引擎的搜索質(zhì)量，實(shí)現(xiàn)對(duì)搜索結(jié)果進(jìn)行篩選分類，剔除與其他結(jié)果圖像相似度較低的圖像，將會(huì)有助于提高搜索的結(jié)果質(zhì)量。由于搜索引擎的及時(shí)性要求，需要一個(gè)比較簡潔快速的方法進(jìn)行圖像分類，圖像分類技術(shù)是圖像處理的基礎(chǔ)，而采用不用的分類器對(duì)圖像的分類效果也是截然不同的。目前對(duì)多種類別圖片進(jìn)行分類的分類器有很多種，如神經(jīng)網(wǎng)絡(luò)、支持向量機(jī)、決策樹、貝葉斯、K-近鄰、基于關(guān)聯(lián)規(guī)則的分類等。其分類效果各異，而組合分類器和加強(qiáng)分類器也逐漸得到人們的重視，如隨機(jī)森林、Boosting算法等進(jìn)行圖像分類。2.分類器介紹2.1BP神經(jīng)網(wǎng)絡(luò)BP網(wǎng)絡(luò)模型處理信息的基本原理是：輸入信號(hào)Xk通過中間節(jié)點(diǎn)(隱層點(diǎn))作用于輸出節(jié)點(diǎn)，經(jīng)過非線性變換，產(chǎn)生輸出信號(hào)Yk，網(wǎng)絡(luò)訓(xùn)練的每個(gè)樣本包括輸入向量X和期望輸出量t，網(wǎng)絡(luò)輸出量Y與期望輸出量t之間的偏差，通過調(diào)整輸入節(jié)點(diǎn)與隱層節(jié)點(diǎn)的聯(lián)接強(qiáng)度取值Wij和隱層節(jié)點(diǎn)與輸出節(jié)點(diǎn)之間的聯(lián)接強(qiáng)度Tik以及閾值，使誤差沿梯度方向下降，經(jīng)過反復(fù)學(xué)習(xí)訓(xùn)練，確定與最小誤差相對(duì)應(yīng)的網(wǎng)絡(luò)參數(shù)(權(quán)值和閾值)，訓(xùn)練即告停止。此時(shí)經(jīng)過訓(xùn)練的神經(jīng)網(wǎng)絡(luò)即能對(duì)類似樣本的輸入信息，自行處理輸出誤差最小的經(jīng)過非線性轉(zhuǎn)換的信息。2.2支持向量機(jī)SVM最初是在模式分類中提出的，其基本思想是：通過非線性變換φ(·)將輸入空間映射到一個(gè)高維特征空間，在這個(gè)特征空間中求取最大間隔分類超平面f(x)=wTφ(x)+b，其中w、b分別是這個(gè)超平面的權(quán)值和閾值。特征空間的維數(shù)可能是非常高的，通常導(dǎo)致計(jì)算非常復(fù)雜。SVM算法通過核函數(shù)K(x,y)巧妙地解決了這個(gè)問題。SVM不直接計(jì)算復(fù)雜的非線性變換φ(·),而是計(jì)算非線性變換φ(·)的內(nèi)積K(x,y),即核函數(shù)K(x,y)=φ(x)·φ(y)，從而大大簡化了計(jì)算，核函數(shù)K(x,y)的利用時(shí)由于在原空間和高維特征空間只用到了內(nèi)積運(yùn)算。2.3決策樹決策樹起源于概念學(xué)習(xí)系統(tǒng)CLS，其思路是找出最有分辨能力的屬性，把數(shù)據(jù)庫劃分為多個(gè)子集(對(duì)應(yīng)樹的一個(gè)分枝)，構(gòu)成一個(gè)分枝過程，然后對(duì)每一個(gè)子集遞歸調(diào)用分枝過程，直到所有子集包含同一類型的數(shù)據(jù)。最后得到的決策樹能對(duì)新的例子進(jìn)行分類。CLS學(xué)習(xí)算法是Hunt.E.B等人在1966年提出的。它第一次提出用決策樹進(jìn)行概念學(xué)習(xí)，后來的許多決策樹學(xué)習(xí)算法都可以看作CLS算法的改進(jìn)與更新。CLS的主要思想是從一個(gè)空的決策樹出發(fā)，通過添加新的判定結(jié)點(diǎn)來改善原來的決策樹，直到該決策樹能夠正確的將訓(xùn)練實(shí)例分類為止。它對(duì)決策樹的構(gòu)造過程也就是假設(shè)特化的過程，所以CLS可以看作是只帶一個(gè)操作符的學(xué)習(xí)算法，次操作符可以表示為：通過添加一個(gè)新的判定條件(新的判定結(jié)點(diǎn))，特化當(dāng)前假設(shè)。CLS算法遞歸調(diào)用這個(gè)操作符，作用在每個(gè)葉結(jié)點(diǎn)，來構(gòu)造決策樹。2.4貝葉斯貝葉斯（Bayes）分類算法是一類利用概率統(tǒng)計(jì)知識(shí)進(jìn)行分類的算法，如樸素貝葉斯（NaiveBayes）算法。這些算法主要利用Bayes定理來預(yù)測一個(gè)未知類別的樣本屬于各個(gè)類別的可能性，選擇其中可能性最大的一個(gè)類別作為該樣本的最終類別。由于貝葉斯定理的成立本身需要一個(gè)很強(qiáng)的條件獨(dú)立性假設(shè)前提，而此假設(shè)在實(shí)際情況中經(jīng)常是不成立的，因而其分類準(zhǔn)確性就會(huì)下降。為此就出現(xiàn)了許多降低獨(dú)立性假設(shè)的貝葉斯分類算法，如TAN（TreeAugmentedNa?veBayes)算法，它是在貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)的基礎(chǔ)上增加屬性對(duì)之間的關(guān)聯(lián)來實(shí)現(xiàn)的。2.5隨機(jī)森林RFA模型是許多決策樹集成在一起的分類器，如果把決策樹看成分類任務(wù)中的一個(gè)專家，那隨機(jī)森林就是許多專家在一起對(duì)某種任務(wù)進(jìn)行分類。實(shí)驗(yàn)證明隨機(jī)森林在分類中對(duì)各個(gè)類別的分類性能比較好，也比較穩(wěn)定，最重要的是它的泛化能力很強(qiáng)。隨機(jī)森林是由多個(gè)決策樹{h(x,θk)}組成的分類器,其中{θk}是相互獨(dú)立且同分布的隨機(jī)向量.最終由所有決策樹綜合決定輸入向量X的最終類標(biāo)簽。2.6Boosting算法傳統(tǒng)的基于filer策略的特征選擇方法對(duì)于替身分類器的性能所能提供的貢獻(xiàn)有限，很多研究嘗試通過更加復(fù)雜的技術(shù)來使得分類器性能更好。例如Adaboost方法通過在訓(xùn)練數(shù)據(jù)上進(jìn)行boosting學(xué)習(xí)選擇特征。然后，根據(jù)其錯(cuò)誤率，每個(gè)樣本的權(quán)值會(huì)被重新計(jì)算。最終，這些被選擇的特征組合成一個(gè)完整的分類器。這種方法是一種基于提升和加法樹的方法，通過貪心策略迭代尋找當(dāng)前的特征，將弱分類器組合強(qiáng)分類器，從而優(yōu)化指數(shù)損失函數(shù)。采用boosting方法為分類器選擇特征，這些方法采用和分類器算法行為分離的策略，在分類之前就已經(jīng)在原始特征集中選擇出特征子集。所以它們不依賴于特定的學(xué)習(xí)方法，而提供獨(dú)立的特征子集。在這些方法中，他們采用信息量測度模型來估算每個(gè)特征導(dǎo)致的錯(cuò)誤率，因而可以作為分類器的預(yù)處理過程，從而和任意的分類器結(jié)合。這樣的結(jié)果是他們選擇的特征并沒有和分類器行為進(jìn)行交互，從而也沒有利用到分類器產(chǎn)生的反饋信息。3.分類器的優(yōu)缺點(diǎn)3.1BP神經(jīng)網(wǎng)絡(luò)多層前向BP網(wǎng)絡(luò)是目前應(yīng)用最多的一種神經(jīng)網(wǎng)絡(luò)形式,但它也不是非常完美的,為了更好的理解應(yīng)用神經(jīng)網(wǎng)絡(luò)進(jìn)行問題求解,這里對(duì)它的優(yōu)缺點(diǎn)展開討論:多層前向BP網(wǎng)絡(luò)的優(yōu)點(diǎn)：

①網(wǎng)絡(luò)實(shí)質(zhì)上實(shí)現(xiàn)了一個(gè)從輸入到輸出的映射功能，而數(shù)學(xué)理論已證明它具有實(shí)現(xiàn)任何復(fù)雜非線性映射的功能。這使得它特別適合于求解內(nèi)部機(jī)制復(fù)雜的問題；②網(wǎng)絡(luò)能通過學(xué)習(xí)帶正確答案的實(shí)例集自動(dòng)提取“合理的”求解規(guī)則，即具有自學(xué)習(xí)能力；

③網(wǎng)絡(luò)具有一定的推廣、概括能力。多層前向BP網(wǎng)絡(luò)的問題：

①BP算法的學(xué)習(xí)速度很慢，其原因主要有：

a由于BP算法本質(zhì)上為梯度下降法，而它所要優(yōu)化的目標(biāo)函數(shù)又非常復(fù)雜，因此，必然會(huì)出現(xiàn)“鋸齒形現(xiàn)象”，這使得BP算法低效；

b存在麻痹現(xiàn)象，由于優(yōu)化的目標(biāo)函數(shù)很復(fù)雜，它必然會(huì)在神經(jīng)元輸出接近0或1的情況下，出現(xiàn)一些平坦區(qū)，在這些區(qū)域內(nèi)，權(quán)值誤差改變很小，使訓(xùn)練過程幾乎停頓；

c為了使網(wǎng)絡(luò)執(zhí)行BP算法，不能用傳統(tǒng)的一維搜索法求每次迭代的步長，而必須把步長的更新規(guī)則預(yù)先賦予網(wǎng)絡(luò)，這種方法將引起算法低效。

②網(wǎng)絡(luò)訓(xùn)練失敗的可能性較大，其原因有：

a從數(shù)學(xué)角度看，BP算法為一種局部搜索的優(yōu)化方法，但它要解決的問題為求解復(fù)雜非線性函數(shù)的全局極值，因此，算法很有可能陷入局部極值，使訓(xùn)練失??；b網(wǎng)絡(luò)的逼近、推廣能力同學(xué)習(xí)樣本的典型性密切相關(guān)，而從問題中選取典型樣本實(shí)例組成訓(xùn)練集是一個(gè)很困難的問題。

③難以解決應(yīng)用問題的實(shí)例規(guī)模和網(wǎng)絡(luò)規(guī)模間的矛盾。這涉及到網(wǎng)絡(luò)容量的可能性與可行性的關(guān)系問題，即學(xué)習(xí)復(fù)雜性問題；

④網(wǎng)絡(luò)結(jié)構(gòu)的選擇尚無一種統(tǒng)一而完整的理論指導(dǎo)，一般只能由經(jīng)驗(yàn)選定。為此，有人稱神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)選擇為一種藝術(shù)。而網(wǎng)絡(luò)的結(jié)構(gòu)直接影響網(wǎng)絡(luò)的逼近能力及推廣性質(zhì)。因此，應(yīng)用中如何選擇合適的網(wǎng)絡(luò)結(jié)構(gòu)是一個(gè)重要的問題；

⑤新加入的樣本要影響已學(xué)習(xí)成功的網(wǎng)絡(luò)，而且刻畫每個(gè)輸入樣本的特征的數(shù)目也必須相同；

⑥網(wǎng)絡(luò)的預(yù)測能力（也稱泛化能力、推廣能力）與訓(xùn)練能力（也稱逼近能力、學(xué)習(xí)能力）的矛盾。一般情況下，訓(xùn)練能力差時(shí)，預(yù)測能力也差，并且一定程度上，隨訓(xùn)練能力地提高，預(yù)測能力也提高。但這種趨勢有一個(gè)極限，當(dāng)達(dá)到此極限時(shí)，隨訓(xùn)練能力的提高，預(yù)測能力反而下降，即出現(xiàn)所謂“過擬合”現(xiàn)象。此時(shí)，網(wǎng)絡(luò)學(xué)習(xí)了過多的樣本細(xì)節(jié)，而不能反映樣本內(nèi)含的規(guī)律。

3.2支持向量機(jī)SVM是Vapnik等人在1995年提出的一種新的模式識(shí)別方法，它在解決小樣本、非線性以及高維模式識(shí)別問題中表現(xiàn)出許多優(yōu)勢，并能夠推廣應(yīng)用到函數(shù)擬合等其他機(jī)器學(xué)習(xí)問題中。SVM有重大的潛在應(yīng)用價(jià)值，但也存在內(nèi)存龐大和計(jì)算復(fù)雜度高等缺點(diǎn)。3.3決策樹優(yōu)點(diǎn)：1)可以生成可以理解的規(guī)則；2)計(jì)算量相對(duì)來說不是很大；3)可以處理連續(xù)和種類字段；4)決策樹可以清晰的顯示哪些字段比較重要。缺點(diǎn)：1)對(duì)連續(xù)性的字段比較難預(yù)測；2)對(duì)有時(shí)間順序的數(shù)據(jù)，需要很多預(yù)處理的工作；3)當(dāng)類別太多時(shí)，錯(cuò)誤可能就會(huì)增加的比較快；4)一般的算法分類的時(shí)候，只是根據(jù)一個(gè)字段來分類。3.4貝葉斯分類優(yōu)點(diǎn)：1)貝葉斯分類并不把一個(gè)對(duì)象絕對(duì)地指派給某一類，而是通過計(jì)算得出屬于某一類的概率，具有最大概率的類便是該對(duì)象所屬的類；2)一般情況下在貝葉斯分類中所有的屬性都潛在地起作用，即并不是一個(gè)或幾個(gè)屬性決定分類，而是所有的屬性都參與分類；3)貝葉斯分類對(duì)象的屬性可以是離散的、連續(xù)的，也可以是混合的。缺點(diǎn)：貝葉斯定理給出了最小化誤差的最優(yōu)解決方法，可用于分類和預(yù)測。但在實(shí)際中，它并不能直接利用，它需要知道證據(jù)的確切分布概率，而實(shí)際上我們并不能確切的給出證據(jù)的分布概率。3.5隨機(jī)森林優(yōu)點(diǎn)：它可以產(chǎn)生高準(zhǔn)確度的分類器。它可以處理大量的輸入變量。它可以在決定類別時(shí)，評(píng)估變量的重要性。在建造森林時(shí)，它可以在內(nèi)部對(duì)于一般化后的誤差產(chǎn)生不偏差的估計(jì)。它包含一個(gè)好方法可以估計(jì)遺失的資料，而且，如果有很大一部分的資料遺失，仍可以維持準(zhǔn)確度。它提供一個(gè)實(shí)驗(yàn)方法，可以去偵測變量間的相互作用。對(duì)于不平衡的分類資料集來說，它可以平衡誤差。它計(jì)算各例中的親近度，對(duì)于數(shù)據(jù)挖掘、偵測偏離著和將資料視覺化非常有用。它可被延伸應(yīng)用在未標(biāo)記的資料上，這類資料通常是使用非監(jiān)督式聚類。也可偵測偏離者和觀看資料。學(xué)習(xí)過程是很快速的。缺點(diǎn)：隨機(jī)森林在一些數(shù)據(jù)集產(chǎn)生過擬合。在噪聲分類/回歸任務(wù)中表現(xiàn)突出。隨機(jī)森林不處理大量的無關(guān)特征以及熵減決策樹。選擇隨機(jī)決策邊界比熵減決策邊界要更有效率，因此使得更多的組合變得可行。雖然這可能是個(gè)優(yōu)勢，它轉(zhuǎn)換從訓(xùn)練時(shí)間到評(píng)估時(shí)間的計(jì)算，對(duì)于大多數(shù)應(yīng)用實(shí)際上是一個(gè)不