本文是一篇評高工論文發(fā)表范文，主要針對基于類別重要度的MIMLBoost改進(jìn)算法進(jìn)行了一些論述，搜論文知識網(wǎng)收錄了大量的免費文獻(xiàn)以供大家參考，有需要發(fā)表論文的作者可以聯(lián)系本站在線編輯進(jìn)行咨詢。

　　摘要：針對多示例多標(biāo)記學(xué)習(xí)算法MIMLBoost中退化過程造成的類別不平衡問題，運用人工降采樣思想，引入類別重要度，提出一種改進(jìn)的基于類別標(biāo)記評估的退化方法。該方法通過對示例空間中的示例包進(jìn)行聚類，把標(biāo)記空間中的標(biāo)記量化到聚類簇上，再以聚類簇為單位，利用TFIDF算法對每個類別標(biāo)記進(jìn)行重要度評估和篩選，去除重要度低的標(biāo)記，并將簇中的示例包與其余的類別標(biāo)記拼接起來，以此來減少大類樣本的出現(xiàn)，完成多示例多標(biāo)記樣本向多示例單標(biāo)記樣本的轉(zhuǎn)化。在自然數(shù)據(jù)集上進(jìn)行了實驗，實驗結(jié)果發(fā)現(xiàn)，改進(jìn)算法的性能整體上優(yōu)于原算法，尤其在Hamming loss、 coverage、 ranking loss三個評測指標(biāo)上尤為明顯，說明所提算法能夠有效降低分類的出錯率，提高算法的精度和分類效率。

　　關(guān)鍵詞：多示例多標(biāo)記,MIMIBoost算法,TFIDF算法,聚類,類別不平衡

　　0引言

　　多示例多標(biāo)記(MultiInstance MultiLabel， MIML)學(xué)習(xí)[1-2]是基于對象的歧義性[3]而提出的一種學(xué)習(xí)框架，是對多示例學(xué)習(xí)和多標(biāo)記學(xué)習(xí)的擴展。在該學(xué)習(xí)框架下，真實世界的對象由包含多個示例的示例包所描述，且其對應(yīng)的類別標(biāo)記不再唯一，而是多個標(biāo)記組成的集合。例如在文檔分類中，一篇文檔可劃分為不同的章節(jié)段落，每一個章節(jié)段落都可用一個示例來描述，且一篇文檔既可認(rèn)為屬于“體育”類，也可認(rèn)為屬于“娛樂”類，具有多種類別;又比如一幅圖像可劃分為幾個區(qū)域，每個區(qū)域都可用一個示例來表示，且根據(jù)圖像具有的不同內(nèi)容，可將其歸為多個類別等。

　　學(xué)習(xí)系統(tǒng)通過對訓(xùn)練集中具有多個標(biāo)記的示例包進(jìn)行學(xué)習(xí)，以盡可能地預(yù)測未知對象的類別標(biāo)記集合。為了發(fā)揮MIML框架的能力，研究者已設(shè)計了多種有效的算法，如MIMLBoost[1-2]、MIMLSVM[1-2]、INSDIF[4]、M3MIML[5]等算法。其中，較直觀的方法是把多示例多標(biāo)記問題以多示例學(xué)習(xí)[6]或多標(biāo)記學(xué)習(xí)[7]為橋梁，退化為傳統(tǒng)的監(jiān)督學(xué)習(xí)問題進(jìn)行求解，代表性的有MIMLBoost算法和MIMLSVM算法。其中，MIMLBoost算法通過示例包與類別標(biāo)記的拼接，實現(xiàn)多示例多標(biāo)記樣本向多示例單標(biāo)記樣本的退化。這種方法簡捷方便，而且效率高，在場景分類與文本分類上取得了比多示例學(xué)習(xí)框架和多標(biāo)記學(xué)習(xí)框架更好的學(xué)習(xí)效果。

　　1MIMLBoost算法思想

　　設(shè)χ為示例空間，Y表示標(biāo)記空間，數(shù)據(jù)集D={(X1，Y1)，(X2，Y2)，…，(Xm，Ym)}，其中： Xi是χ的一組示例{xi1，xi2，…，xini}，xij∈χ(j=1，2，…，ni)為第i個包的第j個示例，YiY為Xi的一組合適的類別標(biāo)記，{yi1，yi2，…，yiki}，ni為Xi所含示例的個數(shù)，ki為Yi所含標(biāo)記的個數(shù)。多示例多標(biāo)記學(xué)習(xí)的目標(biāo)是得到f：2χ→2Y，MIMLBoost算法以多示例學(xué)習(xí)為橋梁，將學(xué)習(xí)目標(biāo)轉(zhuǎn)換為fm：2χ×y→{-1，+1}，然后在進(jìn)一步轉(zhuǎn)換為傳統(tǒng)監(jiān)督學(xué)習(xí)問題。具體做法是：對示例空間和標(biāo)記空間進(jìn)行拼接，將每個示例包Xi與類別標(biāo)記y拼接起來，原樣本(Xi，Yi)就變?yōu)閨Y|個多示例單標(biāo)記樣本{([Xi，y]，φ [Xi，y])|y∈Y}，其中， [Xi，y]包含ni個示例{(xi1，y)，(xi2，y)，…，(xini，y)}，φ[Xi，y]=+1當(dāng)且僅當(dāng)y∈Yi，否則φ[Xi，y]=-1。上述轉(zhuǎn)換過程完成后，再利用文獻(xiàn)[8]中的多示例學(xué)習(xí)算法MIBoosting進(jìn)行求解。以上就是MIMLBoost算法的基本過程，其在場景分類及文本分類問題上取得了良好的學(xué)習(xí)效果。

　　實際上，在大多數(shù)問題中，由于獲取正例的成本比反例高，所以訓(xùn)練集中具有多個類別標(biāo)記的樣本所占比例并不高。那么，大部分樣本在被拼接轉(zhuǎn)化后，得到的反包將多于正包。例如，對于一個多示例多標(biāo)記樣本(X1，Y1)，假設(shè)標(biāo)記空間含有5個類別標(biāo)記{y1，y2，y3，y4，y5}且Y1={y11，y12}，則此樣本轉(zhuǎn)化后為：([X1，y1]，+1)、([X1，y2]，+1)、([X1，y3]，-1)、([X1，y4]，-1)、([X1，y5]，-1)，其中反包3個、正包2個。這就使得整個訓(xùn)練集樣本轉(zhuǎn)化為多示例單標(biāo)記樣本后，出現(xiàn)的反包將遠(yuǎn)遠(yuǎn)多于正包，造成類別間的不平衡[9]，如此訓(xùn)練得到的分類器具有很大的偏向性，影響算法的性能。

　　針對這一問題，本文采用人工降采樣思想，引入類別標(biāo)記重要度概念，通過聚類和TFIDF算法[10]評估每個標(biāo)記在各個聚類簇中的重要度，并以聚類簇為單位，去除重要度較低的類別標(biāo)記，來減少拼接過程出現(xiàn)的反包樣本，使轉(zhuǎn)化后的訓(xùn)練集樣本類別趨于平衡，降低噪聲出現(xiàn)的概率，提高算法的性能。

　　2MIMLBoost算法改進(jìn)

　　MIMLBoost算法在解決實際問題時，其拼接過程會造成數(shù)據(jù)集的類別不平衡問題，使訓(xùn)練出的分類器性能下降。為解決此問題，本文運用人工降采樣思想，提出了一種新的退化方法。該方法首先通過聚類算法將示例包樣本聚成d簇，每個簇可以看作是包含在示例包中的概念;將每個類別標(biāo)記量化到這d個簇上，運用文本檢索中的TFIDF算法評估出每個類別標(biāo)記y(y∈Y)對于每個簇的重要度;最后篩選對于每個簇重要度高的類別標(biāo)記與簇中的示例包拼接起來，這樣不僅考慮了類別標(biāo)記與示例包潛在概念的關(guān)系，還能有效減少反包的出現(xiàn)，使數(shù)據(jù)趨于平衡。

　　2.1利用TFIDF算法計算類別標(biāo)記的重要度

　　TFIDF算法是一種用于資訊檢索與資訊探勘的常用加權(quán)技術(shù)，用以評估一個字詞對于一個文件集或一個語料庫中的其中一份文件的重要程度。其主要思想是：如果某個詞或短語在一篇文章中出現(xiàn)的頻率高，并且在其他文章中很少出現(xiàn)，則認(rèn)為此詞或者短語具有很好的類別區(qū)分能力，適合用來分類。

　　TFIDF包含兩個部分：TF(詞頻)和IDF(逆向文件頻率)。TF指的是某一個給定的詞語在某個文件中出現(xiàn)的次數(shù);IDF則是一個詞語普遍重要性的度量，其計算方法分別為： 　　TF： tfi， j=ni， j∑knk， j(1)

　　IDF： idfi=lbD{j：ti∈dj}(2)

　　對于數(shù)據(jù)集D，通過聚類算法將其聚成d簇Q={Q1，Q2，…，Qd}，標(biāo)記空間Y={y1，y2，…，yg}含有g(shù)個類別標(biāo)記，將各個類別標(biāo)記量化到每個簇上。如果把每個簇看成一篇文章，每個標(biāo)記看成一個詞，那么就可以利用式(1)、(2)得到第s個標(biāo)記對于第t個簇的重要度wst：

　　wst=lbQ{t：ys∈Qt}+1×ns，t∑knk，t(3)

　　其中：Q表示聚類總簇數(shù)，t：ys∈Qt表示出現(xiàn)ys(1≤s≤g)標(biāo)記的簇的數(shù)量，ns，t表示簇Qt(1≤t≤d)中屬于標(biāo)記ys的示例包數(shù)，∑knk，t表示簇Qt中屬于各個標(biāo)記的示例包數(shù)之和。

　　2.2基于類別標(biāo)記評估的退化方法

　　本文運用人工降采樣思想，結(jié)合聚類和TFIDF方法，在原算法的退化過程中引入類別重要度，提出一種新的基于類別標(biāo)記評估的退化方法。其主要目的是，根據(jù)類別標(biāo)記重要度有選擇地將聚類簇中的示例包與標(biāo)記相拼接，以減少拼接過程中出現(xiàn)的反包。實際上，由于訓(xùn)練集數(shù)據(jù)分布較為均勻，所以每個標(biāo)記的IDF值相差不大，標(biāo)記的重要度高低主要受其TF值影響。若某個標(biāo)記對于某個簇的重要度較低，則說明該簇中屬于該標(biāo)記的示例包較少，簇中的示例包在與該標(biāo)記拼接時，就會出現(xiàn)大量的反包。因此，對于一個簇來說，可以把這類標(biāo)記去除，讓簇中的示例包與其他重要度高的標(biāo)記拼接，這樣就可以減少反包的出現(xiàn)，使訓(xùn)練集趨于平衡。對于某個聚類簇，這種做法雖然會丟失部分樣本信息，但相對于整個訓(xùn)練集來說，這部分損失很少，對實驗結(jié)果的影響也很小，可以忽略。

　　改進(jìn)算法的偽代碼如下所示：

　　程序前

　　Label_Evaluating (Train_bags， d， Cluster， Y， Classifier，

　　MIBoosting)

　　Description：Train_bags： a train set of m bags

　　d： the number of the cluster

　　Y： the label space

　　Cluster： clustering algorithm

　　Λ ←

　　For Bi∈Train_bags do

　　Λ ← Λ∪{Bi}

　　End

　　/*把所有示例包聚成d簇*/

　　{Q1，Q2，…，Qd}=Cluster(Λ， d)

　　/*把類別標(biāo)記量化到d個簇*/

　　NumTrain←

　　For yj∈Y do

　　For k∈{1，2，…，d} do

　　njk←Count(yj， Qk)

　　End

　　NumTrain← NumTrain∪{(nj1，nj2，…，njd)}

　　End

　　/*利用TFIDF方法評估每個標(biāo)記對于d個簇的重要度*/

　　ConvertTrainBags←

　　For k∈ {1，2，…，d} do

　　For yj∈Y do

　　Tf(k， j)=CountTF(NumTrain)

　　Idfj=CountIDF(NumTrain)

　　TFIDF (k， j)=Tf (k， j)*Idfj

　　End

　　Z ←

　　/*篩選出重要度高的標(biāo)記與簇中示例包拼接*/

　　Z ← Select(TFIDF (k， j)， n， Y)

　　For Bi∈Qk do

　　For yj∈Z do

　　If yj∈Yi then

　　ConvertTrainBags←ConvertTrainBags∪ {[(Bi， yj)，+1]}

　　Else

　　ConvertTrainBags←ConvertTrainBags∪ {[(Bi， yj)，-1]}

　　Endif

　　End

　　End

　　End

　　/*利用MIBoosting算法學(xué)習(xí)轉(zhuǎn)化后的訓(xùn)練集得到分類器*/

　　Classifier←MIBoosting (ConvertTrainBags)

　　程序后

　　3實驗與分析

　　3.1實驗數(shù)據(jù)

　　實驗均在Matlab平臺上完成，數(shù)據(jù)集選用自然場景分類數(shù)據(jù)。該數(shù)據(jù)集包含2000幅自然場景圖像，所有可能的概念類為desert、 mountains、 sea、 sunset，以及trees，數(shù)據(jù)集中具有兩個或兩個以上標(biāo)記的圖像約占數(shù)據(jù)集的22%，表2給出了該數(shù)據(jù)集的具體描述信息。

　　3.2實驗結(jié)果與分析

　　算法的性能評估選用以下5個評測指標(biāo)[11]：Hamming loss↓、oneerror↓、coverage↓、ranking loss↓、Average precision↑(↓表示值越小越好，↑表示值越大越好)。本文方法中的聚類算法選用kmedoids[12]算法，k表示聚類簇數(shù)，實驗比較結(jié)果如表2～4所示。

　　由表2和表4可以看出，本文算法性能明顯優(yōu)于AdaBoost.MH[13]算法，且各項評測指標(biāo)相差較大;由表2和表3可以看出，本文算法在Hamming loss、 coverage、 ranking loss三個指標(biāo)上優(yōu)于原算法，在oneerror、 Average precision兩個指標(biāo)上與原算法相當(dāng)，說明本文解決類別不平衡問題的方法是有效的。對比實驗結(jié)果，可以看出本文算法能夠有效降低反例樣本對算法分類性能的影響，降低分類的出錯率，提高算法的精度。 　　3.3簇數(shù)k對算法性能的影響

　　表5和表6是改進(jìn)算法在不同簇數(shù)下的實驗結(jié)果。

　　由表2、表5和表6可以看出，改進(jìn)算法的評測性能隨著簇數(shù)k的增大而不斷提高。為了進(jìn)一步研究算法性能與k值之間的關(guān)系，分別在不同的數(shù)據(jù)集上進(jìn)行了實驗，設(shè)定簇的數(shù)量變化范圍為50到400，實驗結(jié)果如圖1所示。

　　從圖1可以看出，無論使用哪個數(shù)據(jù)集，隨著聚類簇數(shù)的變化，改進(jìn)算法的分類正確率呈現(xiàn)先遞增后在一定范圍上下波動的規(guī)律。簇數(shù)量的變化，可以看作是對數(shù)據(jù)集挖掘程度高低的變化。簇數(shù)量較少時，數(shù)據(jù)挖掘的程度較低，生成的潛在概念相對較少，數(shù)據(jù)仍存在很大的不平衡性，因此分類正確率不高;隨著簇數(shù)量的不斷增加，對數(shù)據(jù)集挖掘程度越來越高，數(shù)據(jù)趨于平衡，分類正確率也不斷增加;但隨著簇數(shù)量的進(jìn)一步增加，一些起到關(guān)鍵性作用的概念被分解成更小的概念，從而使正確率有所下降，與此同時，另一些起到關(guān)鍵作用的概念也被挖掘出來，又致使正確率有所回升，因此造成了正確率在一定范圍內(nèi)上下波動。

　　4結(jié)語

　　本文針對MIMLBoost算法退化過程引起的類別不平衡問題，采用人工降采樣思想，結(jié)合TFIDF及聚類算法，評估類別標(biāo)記的重要度，通過去除重要度低的標(biāo)記，達(dá)到減少反包的目的。實驗證明，改進(jìn)后的方法能有效減少大類樣本，使訓(xùn)練集趨于平衡，提高算法的性能。另外，改進(jìn)算法的性能受到數(shù)據(jù)分布的影響，在考慮數(shù)據(jù)分布特點的同時，研究數(shù)據(jù)不平衡對于改進(jìn)算法的影響將是未來的工作重點。

　　參考文獻(xiàn)：

　　[1] ZHOU Z， ZHANG M. Multiinstance multilabel learning with application to scene classification[C]// Proceedings of the 2006 Conference Advances in Neural Information Processing Systems. Cambridge： MIT Press， 2007： 1609-1616.

　　[2] ZHOU Z， ZHANG M， HUANG S， et al. Multiinstance multilabel learning[J]. Artificial Intelligence， 2012， 176(1)： 2291-2320.

　　[3] HOMAN P， RALPH M A L， ROGERS T T. Semantic diversity： a measure of semantic ambiguity based on variability in the contextual usage of words[J]. Behavior Research Methods， 2013， 45(3)：718-730.

　　[4] ZHANG M， ZHOU Z. Multilabel learning by instance differentiation[C]// Proceedings of the 22nd Conference on Articial Intelligence. Menlo Park： AAAI Press， 2007： 669-674.

　　[5]

　　ZHANG D， HE J， LAWRENCE R. MI2LS： multiinstance learning from multiple information sources[C]// Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2013： 149-157.

　　評高工論文發(fā)表期刊推薦《電子測量與儀器學(xué)報》旨在開展學(xué)術(shù)交流活動，溝通同行業(yè)科技人員之間的信息，以促進(jìn)國內(nèi)、外電子測量儀器的發(fā)展和科學(xué)技術(shù)的進(jìn)步。