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

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

　　關鍵詞：多示例多標記,MIMIBoost算法,TFIDF算法,聚類,類別不平衡

　　0引言

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

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

　　1MIMLBoost算法思想

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

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

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

　　2MIMLBoost算法改進

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

　　2.1利用TFIDF算法計算類別標記的重要度

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

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

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

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

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

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

　　2.2基于類別標記評估的退化方法

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

　　改進算法的偽代碼如下所示：

　　程序前

　　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)

　　/*把類別標記量化到d個簇*/

　　NumTrain←

　　For yj∈Y do

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

　　njk←Count(yj， Qk)

　　End

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

　　End

　　/*利用TFIDF方法評估每個標記對于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 ←

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

　　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算法學習轉化后的訓練集得到分類器*/

　　Classifier←MIBoosting (ConvertTrainBags)

　　程序后

　　3實驗與分析

　　3.1實驗數據

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

　　3.2實驗結果與分析

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

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

　　表5和表6是改進算法在不同簇數下的實驗結果。

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

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

　　4結語

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

　　參考文獻：

　　[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.

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