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

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

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


本文編號(hào)：2525146