【摘要】：如何有效地對未知類別的新樣例進行分類是數據挖掘領域中一項非常重要的研究課題。集成學習作為解決這一問題的一種強有力的技術自提出以來受到了廣泛的關注和研究,并在實際應用中取得了極大的成功。集成學習已發(fā)展成數據挖掘領域中的一個重要研究分支。目前學者們已經提出了一些經典的集成學習算法,如Bagging、AdaBoost、DECORATE等,并取得了一些重要的研究成果。然而,對于這些集成學習算法的有效性,還不存在一種對其進行充分解釋的較為通用的理論工具;此外,在特定訓練環(huán)境下某些集成學習算法的性能還不夠理想。本文致力于解決這些問題,具體的,可將本文的主要貢獻總結如下。(1)由于不同的集成學習算法是學者們從不同角度提出的,自然的它們具有不同的工作機理。因此,若能從理論上對現有的經典集成學習算法的有效性進行分析,可使人們對這些算法產生更深刻的理解,更重要的是有助于發(fā)現一種能對集成學習算法有效性進行解釋的較為通用的理論工具,從而為設計新的有效集成學習算法提供一定的理論指導。受margin理論所啟發(fā),本文嘗試使用該理論對Bagging、AdaBoost和DECORATE這三種最有代表性的經典集成學習算法的有效性進行實證分析和比較。實驗結果表明,對于探討的每種集成學習算法,它在訓練集上生成的margin分布越好,則其取得的測試精度就越高。也就是說,margin理論能夠很好地解釋這些算法的有效性。因此可得出結論:margin理論是對集成學習算法的有效性進行解釋的一種較為通用的理論工具�；谶@一發(fā)現,本文建議將margin分布作為設計新的集成學習算法時的優(yōu)化目標。(2)為了得到理想的泛化性能,集成學習算法通常生成大量的基分類器來構成集成系統。然而在得到的集成系統中,可能存在一些精度較低或者相似的分類器,這不僅會增加集成系統的存儲和計算開銷而且會降低它的分類效率和泛化性能。為解決這一問題,本文提出了一種基于平均margin排序的基分類器選擇方法,以便從初始集成系統中選擇一個近似最優(yōu)的分類器子集。該方法使用平均margin作為性能評價度量來對初始集成中個體分類器的性能進行評估。另外,本文還將平均margin與accuracy和diversity這兩種常用的性能評價度量進行了全面比較。實驗結果表明,本文的基分類器選擇方法能有效地提高初始集成系統的分類效率和泛化性能,并且平均margin是一種比accuracy和diversity更好的性能評價度量。這對改善數據挖掘中分類任務的性能具有重要的理論和實踐意義。(3)在一些多分類問題中,訓練集有時會包含很多類標簽被錯誤標記的噪聲樣例。集成學習算法AdaBoost對這些誤標記噪聲樣例非常敏感并且容易產生過度擬合,從而對誤標記噪聲樣例不具有魯棒性。針對這一問題,本文提出了一種魯棒的誤標記噪聲數據多分類方法Rob_MulAda。在Rob_MulAda中,形式地設計了一種基于噪聲檢測的多分類損失函數,并通過證明一個命題求解了其最小化問題;另外,給出了一種新的權值更新方式來克服誤標記噪聲樣例的影響。在不同的噪聲水平下將Rob_MulAda與其它幾種相關方法進行了詳細的實驗比較,實驗結果表明Rob_MulAda能夠很好地改善AdaBoost在多分類問題中對誤標記噪聲樣例的魯棒性。(4)很多實際應用中收集的訓練集往往具有不平衡的類分布。由于大多數基分類器學習算法被提出時都基于這一假設:訓練集應該具有大體平衡的類分布,因此它們在類不平衡訓練集上生成的分類器通常具有較差的泛化性能,尤其是對少數類樣例不能有效地進行分類。鑒于集成學習在提高個體分類器性能方面的優(yōu)勢,本文嘗試利用集成學習來提高分類器在類不平衡訓練環(huán)境下的泛化性能,提出了一種基于進化欠抽樣的Bagging集成方法EUS-Bag。在EUSBag中,為了使進化欠抽樣EUS更加適合Bagging框架、以生成一些具有良好性能且多樣化的個體分類器,本文設計了一種考慮了三個因素的新適應度函數,從而更好地將EUS和Bagging的優(yōu)勢進行結合。在類不平衡數據集上進行的比較實驗表明,EUS-Bag能夠有效地提高分類器對類不平衡數據的分類性能。
【圖文】：

學習任務的種類括起來，數據挖掘領域研究的學習任務主要分為以下幾類[1]：分類（classificatioegression）、聚類（clustering）、頻繁模式挖掘（frequent pattern mining）。) 分類，直觀上說，就是為每個新來的未知類別的對象指派一個明確的類標簽，以確定該對象屬于哪一個類別。形式上，給定一些具有類標簽的訓練樣例組即訓練集（training set）：1 1 2 2{( , ),( , ),...,( , )}tr N ND = x y x y x y，其中1 2( , ,..., i i i ix = x x x 1是屬性的個數）是描述第 i （1 ≤ i ≤ N）個樣例的屬性元組（attribute tuple），iy樣例的類標簽（Y是該分類問題中所有不同類標簽的集合），一般用 0、1、2 等，iy也稱為該樣例的目標屬性（target attribute）。對于一個分類任務，可通過以完成。（1）分類器構造階段。使用某種分類器學習算法 Learn（如決策樹[27 29]、[30 32]等）在訓練集trD上進行學習，以生成一個分類器C：( )trC = Learn D。該分屬性的取值1 2_ , _ ,..., _pattri v attri v attri v與類標簽y ∈ Y之間建立了一種函數關系1 2( _ , _ ,..., _ )p attri v attri v attri v；（ 2 ）分類階段。當遇到一個新的未知類別的1 2 , ,..., )t t tpx x x時，分類器 C 根據該樣例的各個屬性值對它的類標簽進行預測，從而類結果ty：( )t ty = C x。圖 1.1 展示了分類任務的總體過程。

簡單的說，就是把非常類似的對象放在同一個集合中，把存在較大差別的對象放 在 不 同 的 集 合中 ，下 面 給 出 聚 類 的形 式化 描 述 。 給 定N個 未 知類 別 的 樣 例：D =1 2{ , ,..., }Nx x x =11 12 1 21 22 2{( , ,..., ),( , ,..., ),...,p px x x x x x1 2( , ,..., )}N N Npx x x，當采用像 k means[33 34]這樣的經典聚類算法時，聚類的大體過程如下。（1）從樣例集 D 中隨機選擇k （ k ≥ 2）個樣例作 為初始的k個 簇中心：1 2, ,...,ko o o（,jo ∈ Dj = 1,2,...,k）， 則初始時 每個簇iCluster（1 ≤ i ≤ k）中只有一個樣例io：{ }i iCluster = o，其中 k 是期望得到的簇數，即樣例子集的數目；（2）對 D 中的每個樣例jx（j = 1,2,...,N），使用某種距離度量（常用的是歐氏距離[1]）計算其與每個簇中心lo（l = 1, 2,...,k）之間的距離jld，并將jx分到與其最近的那個簇中心so（1 ≤ s ≤ k）所在的簇中： { }s s jCluster = Cluster ∪ x。對 D 中的所有樣例分配完畢后，對得到的每個新簇的中心進行重新計算：1 1 11 2, ,...,ko o o；（3）將這些新的簇中心1 1 11 2, ,...,ko o o與之前的那些簇中心1 2, ,...,ko o o進行比較，若它們相同，則結束聚類過程，否則將1 1 11 2, ,...,ko o o作為當前的簇中心（即用1 1 11 2, ,...,ko o o更新1 2, ,...,ko o o）并重復執(zhí)行步驟（2）和（3）。圖 1.2 展示了聚類的總體過程，其中左邊的子圖表示根據隨機選擇的 3 個初始簇中心（用加號‘+’標示）對所有樣例進行初次劃分后所得到的結果，，中間的子圖表示上面（2）、
【學位授予單位】：南京航空航天大學
【學位級別】：博士
【學位授予年份】：2016
【分類號】：TP181


本文編號：2525146