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

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

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

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

①BP算法的學習速度很慢，其原因主要有：

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

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

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

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

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

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

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

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

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

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