袁興梅,謝雪蓮
(南京工程學院信息化建設(shè)與管理辦公室,江蘇 南京211167)
目前,許多應(yīng)用中分類器的設(shè)計都是通過帶有類別標簽的樣本訓(xùn)練得到的。但是,隨著訓(xùn)練樣本數(shù)目的逐漸增多以及復(fù)雜度的加大,人工對樣本進行標記費時又費力,在訓(xùn)練之前很難獲得完全標記的樣本集;相反,獲得沒有標簽的樣本集則比較容易。介于這兩種情況之間,利用已經(jīng)標記的樣本集和沒有被標記的樣本集一起學習的“半監(jiān)督學習”成為了一種新穎而又具有很強實用價值的方法。半監(jiān)督學習方法[1]結(jié)合了有監(jiān)督與無監(jiān)督學習方法的優(yōu)點,適用于已知數(shù)據(jù)量少且具有大量未知數(shù)據(jù)的分類問題。在已知數(shù)據(jù)的幫助下,半監(jiān)督分類方法能夠比較好地描述未知數(shù)據(jù)的分布。
半監(jiān)督學習近年來引起了眾多學者的關(guān)注,將這種方法成功地應(yīng)用到了集成學習、數(shù)據(jù)分類、特征選擇等領(lǐng)域[2~5]。張博鋒等人[6]在文本分類應(yīng)用上提出基于自訓(xùn)練EM算法的半監(jiān)督文本分類方法,通過引入中間結(jié)果的自訓(xùn)練機制,在迭代時將中間分類器最有把握對類別進行預(yù)測的未標記樣本轉(zhuǎn)移至標記樣本集,來提高半監(jiān)督分類的訓(xùn)練精度。Wang等人[7]在 Houle提出的RSC模型[8]基礎(chǔ)上提出了SFRSC半監(jiān)督特征選擇方法,在半監(jiān)督無標簽樣本學習中,充分考慮標簽擴展過程中重疊區(qū)域樣本的類別標記。在半監(jiān)督分類研究方面,Self-training算法[9]的學習過程 用有標 簽的樣本來訓(xùn)練初始分類器,然后用初始分類器分類無標簽樣本,求出與標簽樣本最近的k個無標簽數(shù)據(jù),把它們從無標簽樣本集移入有標簽樣本集中。然后,再用新的有標簽樣本重新訓(xùn)練分類器,并再次分類無標簽樣本數(shù)據(jù)。郝建柏等人[10]提出無標簽樣本的類別不從有標簽樣本處直接學習獲得,而是從k個近鄰數(shù)據(jù)學習獲得模糊的類別標簽,最后通過去模糊化,實現(xiàn)對無標簽樣本的分類。
雖然上述多種算法有效地對半監(jiān)督學習方法進行了改進,將其廣泛地應(yīng)用在各種領(lǐng)域,但是,在半監(jiān)督學習中,無標簽樣本類別的擴展在訓(xùn)練過程中起著至關(guān)重要的作用,以上方法在半監(jiān)督訓(xùn)練過程中都沒有主動考慮噪聲數(shù)據(jù)樣本在半監(jiān)督訓(xùn)練中的影響,容易引起標簽擴展過程中的錯誤,并造成錯誤分類擴散,最終導(dǎo)致分類器產(chǎn)生錯誤的分類邊界。如何選取有利于學習模型訓(xùn)練的樣本以及如何進行噪聲處理,這是半監(jiān)督學習方法所需要解決的問題[11]。針對這個問題,本文在RSC標簽擴展模型基礎(chǔ)上,借鑒文獻[9]在標簽擴展過程中對重疊區(qū)域的處理方法,同時在標簽擴展中加入對噪聲數(shù)據(jù)的處理,提出了一種新的半監(jiān)督訓(xùn)練算法RSCNR(semi-supervised training approach based on RSC model and Noise Removing)。通過噪聲樣本的去除可以避免在噪聲樣本基礎(chǔ)上進一步的標簽擴展,防止因噪聲的存在得到錯誤的分類邊界。
首先作如下定義,樣本集S中有t個樣本用Pi(i=1,…,t)表示,它們可以分為c類。用Pi,j表示樣本集中的第i個樣本屬于第j類。
由于在給定的樣本中,有標簽的樣本只占很少的比例,我們可以將原始的有標簽的樣本作為“核心樣本”,對這些核心樣本使用公式(1)來擴展未標記的樣本,通過公式(1)找出集合S中與pi關(guān)系最密切的k個樣本。
公式(1)中,Q(p,k)={π(p,i)|1≤i≤k,1≤k≤|S|},對于集合S中的某個樣本p,假定存在唯一的一個次序π(p)=(p1,p2,…,p|s|),當i<j時,表示pi與pj相比,元素p與pi的關(guān)系更加緊密。這個序列中第i個元素表示為π(p,i)。DR()是用于衡量集合內(nèi)元素相關(guān)程度的量,用自相關(guān)值與外相關(guān)值之差表示。公式(3)用于計算集合A內(nèi)元素自相關(guān)性值,公式(4)用于計算集合A與集合A 外元素的外相關(guān)性,公式中V=Q(v,|A|),v∈A;W=Q(w,|A|),w ?A。公式(3)和公式(4)中的R用公式(5)進行計算,R(A,B)表示樣本集S中的子集A與子集B之間的關(guān)系。
通過公式(1),可計算出與pi關(guān)系最密切的k個樣本,這k個樣本組成了集合A,使集合A中的樣本具有相同的標簽,由此集合A中之前未被標記樣本的標簽就可以被確定,同時這些新被標記的樣本又可以作為新的“核心樣本”。然后,再對這些新的“核心樣本”進行擴展,如此循環(huán)往復(fù),不斷地將未標記的樣本擴展。但是,最后仍然可能存在一些無法被標記的樣本,對于此類樣本,本文將其作為噪聲樣本去除。
在對未標記樣本打標簽過程中,如果某個樣本v已經(jīng)被標記為A類,但是在擴展過程中又被標記為B類。使用公式(6),根據(jù)v對這兩個集合的影響力來判斷其應(yīng)該屬于A還是B。
IR1(v|A,B)表示將v劃入A 集合且B 集合減去v元素后,v對A 的重要性程度。若IR1(v|A,B)比IR1(v|B,A)大,則說明v對集合A 的重要性程度大于其對B集合的重要性,此時v應(yīng)該屬于集合A。若兩者相等,可以隨機選擇。
基于RSC模型的標簽擴展方法,在學習過程中不斷擴大標簽數(shù)據(jù)集,但是傳統(tǒng)方法缺少控制錯誤標簽擴展的機制。在未標記的訓(xùn)練樣本標簽擴展中,一旦出現(xiàn)樣本被錯誤標記,RSC模型無法避免和控制以錯誤標簽為核心的繼續(xù)擴展。而噪聲處理在一般算法中作為預(yù)處理部分對待,絕大多數(shù)的半監(jiān)督學習對噪聲考慮很少。如果在標簽擴展過程中將噪聲樣本打上標簽加入有標簽的樣本集,然后再在此基礎(chǔ)上繼續(xù)擴展,必定會使錯誤擴展,最終導(dǎo)致分類器產(chǎn)生錯誤的分類邊界。
本文提出的RSCNR算法相比其他半監(jiān)督訓(xùn)練方法的創(chuàng)新之處在于對未標記樣本打標簽的過程中,不斷地判斷該樣本是否為噪聲樣本。根據(jù)本文所提算法對樣本的判別,若某無標簽樣本被識別為噪聲樣本,則將該樣本去除,避免將該噪聲樣本打上標記,作為新的“核心樣本”做進一步擴展訓(xùn)練。RSCNR算法的提出,一方面大大降低了產(chǎn)生錯誤分類邊界的可能性,提高算法的訓(xùn)練精度和分類精度;另一方面,通過對噪聲樣本的去除,也可以提高算法的訓(xùn)練效率。
噪聲的判別是通過其與周圍樣本的不一致程度以及孤立程度這兩個因素來決定的。本文在區(qū)分某一樣本是否為噪聲時,引入了一個衡量該樣本與集合內(nèi)其他樣本不一致程度的正則化量Reg(x)。
公式(7)中,con(x,y)表示樣本x被標記為y類的概率,Lk(x)表示使用公式(1)對樣本x進行擴展后與該樣本x關(guān)系最密切的k個樣本,Q表示樣本類別屬性的集合。Reg(x)值越大表示對x估計的標簽y與當前標簽集L越不一致,是噪聲的可能性越大。
通過對樣本區(qū)分度量Reg項是否超過閾值來判定該樣本是否屬于一個噪聲樣本。Reg項值越大,該樣本為噪聲的可能性越大。
本文在RSC標簽擴展的過程中判斷每個待標記的樣本是否為噪聲樣本,通過噪聲樣本的去除可以避免在噪聲樣本基礎(chǔ)上進一步的標簽擴展,防止因噪聲的存在得到錯誤的分類邊界。
extendedL:當前迭代時根據(jù)某個樣本擴展得到的有標簽的數(shù)據(jù)集;
newBornL:新生成的下一次待擴展的樣本;
toExtendL:每次迭代中待擴展的樣本;
currentUL:當前無標簽的樣本;
初始化過程:extendedL、newBornL初始化為空,toExtendL=L
repeat
for every p∈toExtendLdo
1.1對樣本p進行無標簽樣本的擴展,找出與樣本p關(guān)系最密切的樣本集extendedL;
1.2依次判斷新擴展出來的k個樣本是否為噪聲樣本;
1.3對集合extendedL中已有標記的樣本進行重疊區(qū)域的處理;
1.4得到新生成的下一次待擴展的樣本newBornL;
1.5 toExtendL=newBornL,進行下一次迭代。
互聯(lián)網(wǎng)金融的安全交易有賴于互聯(lián)網(wǎng)信息技術(shù)的安全體系,只有構(gòu)筑出健全的互聯(lián)網(wǎng)安全體系,才能為互聯(lián)網(wǎng)金融的安全運行提供保障。這就對互聯(lián)網(wǎng)的硬件、軟件提出了新的要求。在互聯(lián)網(wǎng)領(lǐng)域,應(yīng)該加大安全網(wǎng)絡(luò)的研發(fā)力度,增加計算機網(wǎng)絡(luò)防御能力。此外,在針對互聯(lián)網(wǎng)金融的交易安全上,應(yīng)該使用更強的安全技術(shù)對信息加密。對金融交易信息進行保護,是互聯(lián)網(wǎng)金融交易得以成功進行的基礎(chǔ)。
end
until|currentUL|≤0
step2:半監(jiān)督訓(xùn)練結(jié)束后,仍可能存在一些無法被擴展標記的樣本,將其作為噪聲樣本去除后,使用最近鄰分類器對測試樣本進行分類。
本文為了驗證加入噪聲去除過程的算法效果,將基于RSC標簽擴展的半監(jiān)督學習算法與RSCNR算法進行比較,進行了兩組實驗。第一組實驗采用人工合成的正態(tài)分布數(shù)據(jù)來檢驗算法的可行性;第二組實驗使用國際通用的UCI數(shù)據(jù)集[12]中的bupa、heart和glass進行樣本訓(xùn)練和測試實驗,用于驗證該算法處理實際數(shù)據(jù)的能力。兩組實驗均采用最近鄰分類器,用分類的正確率對本文提出的RSCNR算法與基于RSC標簽擴展的半監(jiān)督學習算法進行比較。實驗中判定樣本是否為噪聲的閾值Noise=0.45,該值是在多次實驗中得到的比較合理的經(jīng)驗值。若Reg項值大于Noise,則將該樣本判定為噪聲樣本。
該實驗的訓(xùn)練樣本是兩類呈正態(tài)分布的樣本,每類包含若干有類別標簽的數(shù)據(jù),其余為無標簽的樣本數(shù)據(jù)。所使用的數(shù)據(jù)集如圖1和圖2所示,圖中“▲”為正類樣本,“*”為負類樣本,其余為無類別標簽的樣本。圖1為兩類呈正態(tài)分布的人工數(shù)據(jù),圖2為在原始正態(tài)分布數(shù)據(jù)基礎(chǔ)上加入噪聲數(shù)據(jù)后的數(shù)據(jù)。測試樣本數(shù)據(jù)為兩類呈同樣正態(tài)分布的數(shù)據(jù),每類各包含500個數(shù)據(jù)樣本。
Figure 1 Normal distribution artificial data set圖1 正態(tài)分布人工數(shù)據(jù)集
Figure 2 Artificial data set added noise data圖2 加入噪聲數(shù)據(jù)后的人工數(shù)據(jù)集
對于加入噪聲數(shù)據(jù)后的人工數(shù)據(jù)集,分別采用RSC標簽擴展的方法和帶有去噪功能的RSCNR方法來對訓(xùn)練樣本中的未標記樣本進行標簽擴展操作。圖3為采用RSC標簽擴展方法得到的訓(xùn)練集,圖4為使用RSCNR方法得到的訓(xùn)練樣本集。
由標簽擴展結(jié)果圖比較分析得出:帶有噪聲去除功能的算法在分類器訓(xùn)練過程中能夠有效去除偽邊界樣本,同時避免了真邊界樣本的丟失。
最后使用最近鄰分類法,用測試樣本對其進行測試。使用RSC標簽擴展訓(xùn)練法得到的測試精度為451/500,使用RSCNR半監(jiān)督訓(xùn)練方法得到的測試精度為484/500,可以得出RSCNR算法能更加準確地對無標簽樣本進行標記,訓(xùn)練出分類邊界,得到更好的分類性能。
Figure 3 Training data set after RSC label extension圖3 RSC標簽擴展得到的訓(xùn)練數(shù)據(jù)集
Figure 4 Training data set after RSCNR algorithm圖4 RSCNR算法得到的訓(xùn)練數(shù)據(jù)集
為了驗證算法處理實際數(shù)據(jù)的能力,本文從UCI數(shù)據(jù)集選擇了bupa、heart和glass三個數(shù)據(jù)集進行實驗。在這三個數(shù)據(jù)集的實驗中,從總樣本集中隨機選取一半數(shù)據(jù)用作有訓(xùn)練集,剩下的一半數(shù)據(jù)用作測試數(shù)據(jù)集。然后從訓(xùn)練集中隨機選取1/5的樣本用作標簽數(shù)據(jù)集,其余為無標簽樣本。本文在實驗中使用的數(shù)據(jù)集信息如表1所示。
Table 1 bupa,heart and glass data表1 bupa、heart和glass數(shù)據(jù)信息
表1是bupa、heart和glass數(shù)據(jù)集在運用基于RSC標簽擴展方法的半監(jiān)督訓(xùn)練以及本文所提出的RSCNR半監(jiān)督方法的訓(xùn)練基礎(chǔ)上,使用最近鄰分類器對測試樣本進行分類測試的結(jié)果。每個數(shù)據(jù)集實驗重復(fù)10輪,以測試數(shù)據(jù)被正確分類的個數(shù)與總測試樣本的個數(shù)比為實驗結(jié)果,實驗結(jié)果取10輪實驗的平均值。
Table 2 Experimental results between RSC label extension method and RSCNR algorithm表2 RSC標簽擴展方法與RSCNR算法在bupa、heart、glass數(shù)據(jù)集的實驗結(jié)果
由表2可見,與單純的標簽擴展訓(xùn)練得到的分類器相比,加入噪聲處理的半監(jiān)督分類處理RSCNR算法的半監(jiān)督分類精度更高,分類的性能更加顯著。
綜上所述,使用人工合成數(shù)據(jù)實驗以及國際通用的UCI數(shù)據(jù)集實驗分析可以得出,本文所提出的算法通過樣本訓(xùn)練過程中噪聲的去除,在避免真實邊界樣本丟失的前提下有效去除偽邊界樣本,得到更加準確的分類邊界。通過測試樣本對所訓(xùn)練分類邊界測試得出,RSCNR算法具有較高的分類精度和泛化能力。
針對傳統(tǒng)半監(jiān)督訓(xùn)練方法對噪聲數(shù)據(jù)不進行處理、容易影響分類器分類效果的問題,本文在RSC標簽擴展模型用有標簽數(shù)據(jù)為核心樣本來擴展無標簽數(shù)據(jù)的方法的基礎(chǔ)上,提出在標簽擴展的過程中加入噪聲判別去除噪聲樣本。實驗結(jié)果表明,本文所提方法通過在訓(xùn)練過程中噪聲的去除,可以更加準確地對無標簽樣本進行訓(xùn)練,得到更加準確的分類邊界,提高分類器的性能。但是,半監(jiān)督分類中需要研究的問題有很多,如何把集成學習、主動學習融入到半監(jiān)督學習中,以及如何將有監(jiān)督學習算法用于半監(jiān)督學習,都是今后的研究方向和需要解決的問題。
[1] Zhu Xiao-jin.Semi-supervised learning literature survey[R].Computer Sciences Techincal Report 1530,Madison:University of Wisconsin-Madison,2005.
[2] Zhou Zhi-hua,Chen Ke-jia,Yuan Jiang.Exploiting unlabeled data in content-based image retrieval[C]∥Proc of the 15th European Conference on Machine Learning,2004:525-536.
[3] Tang Jin-hui,Hua Xian-sheng,Qi Guo-jun,et al.Structuresensitive manifold ranking for video concept detection[C]∥Proc of the 15th International Conference on Multimedia,2007:852-861.
[4] He Jing-rui,Li Ming-jing,Zhang Hong-jiang,et al.Manifoldranking based image retrieval[C]∥Proc of the 12th Annual ACM International Conference on Multimedia,2004:9-16.
[5] Zhou Zhi-hua.When semi-supervised learning meets ensemble learning[C]∥Proc of Mutiple Classifier Systems(MCS’09),2009:529-538.
[6] Zhang Bo-feng,Bai bing,Su Jin-shu.Semi-supervised text classification based on self-training EM algorithm[J].Journal of National University of Defense Technology,2007,29(6):65-69.(in Chinese)
[7] Wang Bo,Jia Yan,Yang Shu-qiang.Forward semi-supervised feature selection based on relevant set correlation[C]∥Proc of International Conference on Computer Science and Software Engineering,2008:210-213.
[8] Houle M E.The relevant-set correlation model for data clustering[J].Statistical Analysis and Data Mining,2008,1(3):157-176.
[9] Rosenberg C,Hebert M,Schneiderman H.Semi-supervised selftraining of object detection models[J].Application of Computer Vision,2005,1(5):29-36.
[10] Hao Jian-bai,Chen Xian-fu,Huang Shuang-fu,et al.Semisupervised classification algorithm using fuzzy nearest neighborhood label propagation[J].Micro Electronics and Computer,2010,27(2):30-33.(in Chinese)
[11] Liang Ji-ye,Gao Jia-wei,Chang Yu.Semi-supervised learning research progress[J].Journal of Shanxi University:Natural Science,2009,32(4):528-534.(in Chinese)
[12] Blake C,Keogh E,Merz C J.UCI repository of machine learning database[EB/OL].[1998-01-25].http://www.ics.uci.edu/~mlearn/MLRepository.html.
附中文參考文獻:
[6] 張博鋒,白冰,蘇金樹.基于自訓(xùn)練EM算法的半監(jiān)督文本分類[J].國防科技大學學報,2007,29(6):65-69.
[10] 郝建柏,陳賢富,黃雙福,等.一種基于模糊近鄰標簽傳遞的半監(jiān)督分類算法[J].微電子學與計算機,2010,27(2):30-33.
[11] 梁吉業(yè),高嘉偉,常瑜.半監(jiān)督學習研究進展[J].山西大學學報:自然科學版,2009,32(4):528-534.