呂 佳，黎雋男

(重慶師范大學 計算機與信息科學學院，重慶 401331)(*通信作者電子郵箱lvjia@cqnu.edu.cn)

0 引言

自訓練方法[1]是半監(jiān)督學習[2]算法中的一種，它利用少量的有標記樣本和大量的無標記樣本共同去訓練一個分類器，用來解決數(shù)據(jù)標注的瓶頸問題。由于它不需要特定的假設條件且簡單有效，受到了不少學者青睞。

Hady等[3]提出Co-Training by Committee自訓練學習框架，該方法集成多個分類器共同進行自訓練學習，其中置信度為多個分類器的平均后驗概率。針對選取最大后驗概率時，可能出現(xiàn)重復的最大后驗概率的問題，Wang等[4]引入了Naive Bayes(NB)[5]，最大后驗概率取平均后驗概率與NB后驗概率之和。同時針對這個問題，Liu等[6]引入了一種基于距離的度量方式，即當平均后驗概率相同的時候，離類別中心越近的樣本的置信度越高，越可靠。Shi等[7]提出集成SVM(Support Machine Vector)[8]、NB和Rocchio[9]三個異構分類器自訓練的方式對文本進行分類，通過按類別投票的方式選取可靠的樣本。Hajmohammadi等[10]提出結合主動學習與自訓練的方法去解決跨語言分類問題，該方法用自訓練方法選取置信度高的樣本，同時用平均余弦相似度和熵結合的方法去選取一些信息量大的樣本。Leng等[11]提出結合主動學習和自訓練方法去構建SVM分類器，用SVM分類器去選擇類中心且標記改變率為0的樣本，同時用主動學習去選擇離決策邊界近的樣本。然而，在上述自訓練方法中，如果誤標記的無標記樣本被作為可靠樣本加入到訓練集中，不僅會降低自訓練方法的性能，還會造成錯誤累積問題，使樣本原本數(shù)據(jù)空間結構發(fā)生扭曲。

數(shù)據(jù)剪輯是一種統(tǒng)計過濾技術，它一般用KNN(KNearest Neighbors)[12]作為基分類器，來去除樣本中潛在的噪聲，同時保留正確的樣本。不少學者用數(shù)據(jù)剪輯技術來去除自訓練方法中的潛在的誤標記樣本。Fan等[13-14]提出結合KNN數(shù)據(jù)剪輯技術的NB自訓練算法，用KNN數(shù)據(jù)剪輯技術過濾掉NB自訓練的噪聲樣本點。黎雋男等[15]提出結合加權KNN(WeightedKNearest Neighbors, WKNN)數(shù)據(jù)剪輯技術的NB自訓練算法，把WKNN和NB分類器投票一致且置信度都高的樣本加入到訓練集。Triguero等[16]總結數(shù)十種數(shù)據(jù)剪輯技術，并把它們結合到自訓練方法中進行了實驗性分析。

針對自訓練方法選出置信度高的無標記樣本中，所含信息量可能不大的問題，Gan等[17]提出用半監(jiān)督模糊C均值(Semi-supervised Fuzzy C Means, SFCM)去改進自訓練方法。他認為無標記樣本可能含有數(shù)據(jù)空間結構潛在信息，利用好這些潛在的信息，能更好地輔助自訓練方法，從而提高自訓練方法的泛化性。

為了解決自訓練方法中的錯誤累積問題和自訓練選出置信度高的無標記樣本所含信息量不大，從而導致自訓練方法泛化性不強的問題，并受聚類和數(shù)據(jù)剪輯技術的共同啟發(fā)，本文提出結合SMUC(Semi-supervised Metric-based fUzzy Clustering)[18]和SKNN(Semi-supervisedKNearest Neighbor)[19]數(shù)據(jù)剪輯技術的NB自訓練方法(Naive Bayes Self-Training combined SMUC and SKNN Data Editing, NBSTSMUCSKNNDE)。實驗結果表明，本文提出方法相比改進前方法具有更好的性能。

1 提出算法

傳統(tǒng)的數(shù)據(jù)剪輯技術僅僅利用有標記樣本的信息，而假設無標記樣本的類標號是不可預測的，但是自訓練方法中，有標記樣本是很少的，那么數(shù)據(jù)剪輯的性能可能因有標記樣本的數(shù)量的匱乏而下降。陳日新等[19]提出SKNN方法，它能同時利用有標記樣本信息和無標記樣本信息對待測樣本進行分類。他認為，如果無標記樣本和有標記樣本來自一個共同的序列，那么有效利用無標記樣本信息，能提高KNN算法的性能，因此，本文提出的NBSTSMUCSKNNDE引入了一種新的數(shù)據(jù)剪輯方法，用SKNN作為數(shù)據(jù)剪輯的基分類器。它能夠同時利用有標記樣本信息和無標記樣本信息進行數(shù)據(jù)剪輯，在有標記樣本不足的情況下，利用額外無標記樣本信息來提高數(shù)據(jù)剪輯的性能，從而更好地解決自訓練方法中的錯誤累積問題。

傳統(tǒng)的自訓練方法會隨機選擇一些無標記樣本給自訓練方法學習，而選擇更具有信息量的無標記樣本給自訓練方法學習，能提高自訓練方法的性能，所以本文提出的NBSTSMUCSKNNDE用半監(jiān)督聚類SMUC方法去選擇一些聚類隸屬度高的無標記樣本給自訓練方法學習。聚類隸屬度高的無標記樣本離樣本真實的類中心越近，它包含著原始樣本空間結構信息。NBSTSMUCSKNNDE的自訓練學習器如果能正確標記這樣的無標記樣本，并加入到訓練集，則可以提高自訓練方法的泛化性。

2 SKNN數(shù)據(jù)剪輯技術

傳統(tǒng)的數(shù)據(jù)剪輯技術有ENN(Edited Nearest Neighbor)[20]、RENN(Repeated Edited Nearest Neighbor)[21]、ALLKNN(AllKNearest Neighbors)[21]、MENN(Modified Edited Nearest Neighbor)[22]等，它們都是利用KNN或WKNN分類的結果與給定樣本的類標號進行對比，如果類標號不一致，就判斷為噪聲樣本，但是KNN或WKNN只考慮到了k個有標記近鄰樣本對待測樣本的類別的貢獻，沒有考慮到無標記近鄰樣本對待測樣本的影響，如果待測樣本和無標記樣本來自一個共同的序列，它們的類別就會存在一定的聯(lián)系，根據(jù)待測樣本和無標記樣本的相關性，可以提高數(shù)據(jù)剪輯的精度，從而提高算法性能。如圖1所示，如果用KNN或WKNN進行分類，待測樣本x會被分到A類，實際上樣本x應該屬于B類。針對這個問題，SKNN在對待測樣本分類時，考慮有標記樣本和無標記樣本對待測樣本的共同影響。

圖1 采用KNN或WKNN分類時的錯誤分類的情況

在SKNN中，設無標記樣本x0，x1，…，xt，那么對待測樣本xt進行分類的時候，考慮到xt與x0:t-1的樣本存在一定的相關性，為此SKNN采用聯(lián)合概率密度P(ωk|xt,x0:t-1)作為分類依據(jù)，其中ω為類標記。

首先從已標記樣本集中找出與xt的k1+1個最近的樣本，用xt(1)，xt(2)，…，xt(k1+1)表示，類標號為t(1)，t(2)，…，t(k1+1)。從無標記樣本集中找出與待測樣本最近的k2個無標記樣本，分別用xt-1，xt-2，…，xt-k2表示，組成測試樣本本序列。

接著用第k1+1個近鄰樣本xt(k1+1)到測試樣本xt的距離d(xt,xt(k1+1))來標準化前k1個近鄰樣本xt(1)，xt(2)，…，xt(k1)到測試樣本{xj，j=t，t-1，…，t-k2}的距離：

(1)

然后用高斯核函數(shù)核化標準后的距離：

(2)

最后確定xt樣本的類別表達式如下，具體推導見文獻[19]。

(3)

SKNN數(shù)據(jù)剪輯技術算法流程如下所示。

輸入：有標記近鄰樣本數(shù)k1，無標記近鄰樣本數(shù)k2，數(shù)據(jù)集D。

輸出：過濾后的樣本集Filtered_D。

過程：

forxi∈D

1)SKNN分類xi得到類標號ti，依據(jù)式(1)～(3)。

2)如果ti與xi本身的類標號不一致，則視xi為噪聲樣本，丟棄。

end

3 半監(jiān)督模糊C均值聚類

Gan等[17]提出用SFCM去輔助自訓練方法，實驗結果表明SFCM作為一種知識發(fā)掘工具，能挖掘大量無標記樣本所暗含的數(shù)據(jù)空間結構信息。新標記的有標記樣本不僅可以改善自訓練方法，而且也可以改善SFCM的性能，從而讓SFCM更好地優(yōu)化自訓練方法。SFCM損失函數(shù)如下：

(4)

其中：c為類別個數(shù)，n為樣本個數(shù)，m為參數(shù)。如式(4)所示，對于SFCM，m值的選取一直是一個棘手的問題，并且用歐氏距離來計算樣本間的距離，沒有考慮到樣本屬性之間的關聯(lián)性。Yin等[18]提出SMUC，它用正則熵的方法來解決SFCM的m值選取問題，同時用馬氏距離代替歐氏距離，考慮到實際應用中屬性之間的關系，因此，NBSTSMUCSKNNDE用SMUC替代SFCM輔助自訓練方法，能選出更具有信息量的無標記樣本交給自訓練方法進行學習。SMUC推導如下。

給定先驗隸屬度矩陣：

U′={uik′|uik′∈[0,1];i=1,2,…,n;k=1,2,…,c}

(5)

同時滿足如下條件：

(6)

首先獲得先驗質心：

(7)

接著計算協(xié)方差矩陣：

(8)

根據(jù)式(8)的協(xié)方差矩陣，給定兩個樣本x1，x2，馬氏距離計算如下：

(9)

SMUC的損失函數(shù)如下，其中等式右邊加入了熵正則表達式：

(10)

式(10)是一個凸優(yōu)化問題，進行拉格朗日優(yōu)化：

(11)

根據(jù)式(11)，對uik和vk求偏導后，得到隸屬度uik和vk的計算公式，如下：

(12)

(13)

SMUC算法流程如下所示。

輸入：數(shù)據(jù)集D，先驗隸屬度uik′，聚類數(shù)量c。

輸出：成員隸屬度uik。

過程：

依據(jù)式(7)計算先驗質心。

依據(jù)式(8)計算協(xié)方差矩陣C。

while ‖uk-uk-1‖≥ε

依據(jù)式(12)計算uik。

依據(jù)式(13)計算vk。

end

4 算法流程

首先，NBSTSMUCSKNNDE用少量的有標記樣本和大量的無標記樣本進行SMUC聚類，從而選出隸屬度高的無標記樣本給NB自訓練方法分類。然后，NBSTSMUCSKNNDE用SKNN數(shù)據(jù)剪輯技術來過濾掉聚類隸屬高但是NB自訓練方法誤分類無標記樣本。聚類隸屬度高的無標記樣本，更接近每一個聚類簇的中心，這樣的無標記樣本更好地反映了每一個聚類簇的結構。如果把這些聚類隸屬度高的無標記樣本正確標記，并加入到訓練集，能使訓練集更好地代表原始樣本空間的結構，從而提高NB自訓練方法的泛化性，但是聚類隸屬度高的無標記樣本可能是每次自訓練方法迭代中離決策邊界近的樣本，NB自訓練方法難以把這樣聚類隸屬度高的樣本分類正確。如果錯誤標記這樣的樣本，然后加入到訓練集，不僅會扭曲數(shù)據(jù)空間原始結構而且會使NB自訓練方法性能下降。SKNN數(shù)據(jù)剪輯技術能過濾掉聚類隸屬高但是NB自訓練方法誤分類無標記樣本，使標記正確的所含信息量大的無標記樣本加入到訓練集，因此，本文提出的方法通過SMUC和SKNN數(shù)據(jù)剪輯技術結合的方式，既解決了自訓練方法選出置信度高的無標記樣本所含信息量不大的問題，又解決了自訓練方法的錯誤累積問題。新標記的無標記樣本加入到訓練集，不僅可以提高自訓練方法的性能，而且可以更好地讓半監(jiān)督聚類和數(shù)據(jù)剪輯為自訓練方法服務。

NBSTSMUCSKNNDE算法流程如下所示。

輸入：有標記樣本集L，無標記樣本集U，有標記近鄰樣本k1，無標記近鄰樣本k2，參數(shù)ε1，參數(shù)ε2，參數(shù)η。

輸出：訓練好的NB。

過程：

whileU集不為空

用樣本集L和U進行SMCU聚類，選出隸屬度uik≥ε1的樣本集R1；

whileR1為空

ε1=ε1-0.05，選出隸屬度uik≥ε1的樣本集R1；

end

用樣本集L和U訓練分類器NB，用訓練后的分類器對R1分類，選出置信度大于ε2的樣本集R2，并得到其類標號Tag2；

whileR2為空

ε2=ε2-0.05，選出置信度大于ε2的樣本集R2，并得到其類標號Tag2；

end

用SKNN數(shù)據(jù)剪輯技術過濾掉R2中的噪聲樣本，得到可靠樣本集R3；

L=L+R3，U=U-R3；

end

5 實驗仿真

為了說明本文算法的有效性，選用對比算法如下：

1)NB自訓練(NB Self-Training, NBST)。

2)結合SFCM的NB自訓練(NB Self-Training combined SFCM, NBSTSFCM)。

3)結合SMUC的NB自訓練(NB Self-Training combined SMUC, NBSTSMUC)。

4)本文提出的結合SMUC和SKNN數(shù)據(jù)剪輯技術的NB自訓練(Naive Bayes Self-Training combined SMUC and SKNN Data Editing, NBSTSMUCSKNNDE)。

實驗數(shù)據(jù)集來源于UCI數(shù)據(jù)集，共8個，如表1。把每一個數(shù)據(jù)集隨機分為測試集和訓練集兩部分，其中訓練集為80%，測試集為20%。在訓練集中隨機選取10%的樣本作為初始化的有標記樣本，其余樣本去除類標記作為無標記樣本。NBSTSFCM中的參數(shù)m=2。NBSTSMUCSKNNDE中的參數(shù)ε1=0.95，ε2=0.95，η=1，其他參數(shù)在各個數(shù)據(jù)集調整至最優(yōu)進行實驗，如表2。實驗重復10次，取10次的平均分類正確率±標準差，如表3所示。為了說明有標記樣本數(shù)對算法的影響，圖2給出了當初始化的有標記樣本比例為10%～50%的時候，實驗重復10次，4個算法在8個數(shù)據(jù)集上的平均分類正確率。

表1 UCI數(shù)據(jù)集描述

表2 實驗參數(shù)設置

表3 有標記率為10%時，4個算法在8個數(shù)據(jù)集上的性能對比

從表3總體可以看出，當有標記樣本比例為10%的時候，本文提出的NBSTSMUCSKNNDE算法整體上性能好于對比算法。具體地看，當有標記樣本率為10%時：在數(shù)據(jù)集Vertebral Column、Haberman’s Survival、Blood Transfusion Service Center、Breast Cancer Wisconsin (Original)和Indian Liver Patient Dataset上，本文提出算法均優(yōu)于對比算法；但在數(shù)據(jù)集IRIS、Seeds和Wine上，本文提出算法弱于對比算法。這可能是數(shù)據(jù)集IRIS、Seeds和Wine中的樣本數(shù)太少，用過少的有標記樣本來指導SMUC聚類，難以找到信息量大的無標記樣本給NB自訓練標記。而且在迭代初期，有標記樣本過少也影響SKNN數(shù)據(jù)剪輯技術對無標記樣本利用的準確率，最終使SMUC和SKNN數(shù)據(jù)剪輯技術難以有效輔助NB自訓練方法。在8個UCI數(shù)據(jù)集上，NBSTSFCM性能微弱于NBSTSMUC，這是因為NBSTSMUC用SMUC代替SFCM，考慮到了實際應用中屬性之間的關聯(lián)性。NBSTSFCM、NBSTSMUC的分類正確率在數(shù)據(jù)集Haberman’s Survival和Blood Transfusion Service Center上高于NBST，但在其他6個數(shù)據(jù)集上，分類正確率低于NBST。這是因為聚類算法能選出無標記樣本中一些暗含數(shù)據(jù)空間結構的樣本，但是這樣的樣本可能是NB自訓練每次迭代很難正確標記的樣本。如果用SKNN數(shù)據(jù)剪輯技術過濾掉這些樣本，則能更好地提高NB自訓練性能，因此本文提出的NBSTSMUCSKNNDE優(yōu)于對比算法。

從圖2可以看出，在數(shù)據(jù)集Vertebral Column、Haberman’s Survival、Blood Transfusion Service Center、Breast Cancer Wisconsin (Original)和Indian Liver Patient Dataset上，本文提出的NBSTSMUCSKNNDE算法在有標記樣本比例為10%～50%的情況下，分類正確率都優(yōu)于對比算法。雖然當有標記樣本為10%的時候，在IRIS、Seeds數(shù)據(jù)集上，和當有標記樣本比例為10%、20%的時候，在Wine數(shù)據(jù)集上，NBSTSMUCSKNNDE算法在分類正確率上低于NBST，但是隨著有標記比例的增加，也能好于對比算法。這可能是因為IRIS、Seed和Wine樣本量過少的緣故。同時，當有標記樣本比例為10%～50%的情況下，NBSTSMUC在8個數(shù)據(jù)集上，整體性能也好于NBSTSFCM。這也證明了本文NBSTSMUCSKNNDE算法用SMUC的優(yōu)勢。

6 結語

本文針對自訓練方法在迭代中選出的置信度高的無標記樣本所含信息量不大和自訓練方法容易誤標記無標記樣本的問題，提出NBSTSMUCSKNNDE算法。在自訓練每次迭代中，該算法用SMUC選取暗含數(shù)據(jù)空間結構信息的無標記樣本給NB分類，同時用SKNN數(shù)據(jù)剪輯技術來過濾掉聚類信息量大但是NB誤分類的無標記樣本。相比傳統(tǒng)的半監(jiān)督聚類，SMUC考慮到了實際應用中屬性之間的關聯(lián)性，并且用熵正則化來優(yōu)化物理表達式，克服了SFCM難找到一個最優(yōu)參數(shù)來發(fā)掘更具有信息量的無標記樣本的問題。同時，本文首次提出了一種新的數(shù)據(jù)剪輯技術，相比以往的數(shù)據(jù)剪輯技術，SKNN能同時利用有標記樣本和無標記樣本信息進行噪聲過濾，在有標記樣本不足的情況下，它能利用額外的無標記樣本信息來過濾掉自訓練方法中誤標記的無標記樣本。最后在UCI數(shù)據(jù)集上驗證了算法的有效性。在后續(xù)的工作中，將研究如何降低本文提出方法的時間復雜度和如何提高自訓練方法在迭代中的預測準確率問題。

References)

[1] YAROWSKY D. Unsupervised word sense disambiguation rivaling supervised methods [C]// ACL ’95: Proceedings of the 33rd Annual Meeting on Association for Computational Linguistics. Stroudsburg: Association for Computational Linguistics, 1995: 189-196.

[2] ZHU X, GOLDBERG A B, BRACHMAN R, et al. Introduction to Semi-Supervised Learning [M]. San Rafael, CA: Morgan and Claypool Publishers, 2009: 130.

[3] HADY M F A, SCHWENKER F. Co-training by committee: a new semi-supervised learning framework [C]// ICDMW ’08: Proceedings of the 2008 IEEE International Conference on Data Mining Workshops. Washington, DC: IEEE Computer Society, 2008: 563-572.

[4] WANG S, WU L, JIAO L, et al. Improve the performance of co-training by committee with refinement of class probability estimations [J]. Neurocomputing, 2014, 136(8): 30-40.

[5] LEWIS D D. Naive (Bayes) at Forty: the independence assumption in information retrieval [C]// ECML ’98: Proceedings of the 10th European Conference on Machine Learning. Berlin: Springer, 1998: 4-15.

[6] LIU K, GUO Y, WANG S, et al. Semi-supervised learning based on improved co-training by committee [C]// IScIDE 2015: Proceedings of the 5th International Conference on Intelligence Science and Big Data Engineering. Big Data and Machine Learning Techniques. Berlin: Springer, 2015: 413-421.

[7] SHI L, MA X, XI L, et al. Rough set and ensemble learning based semi-supervised algorithm for text classification [J]. Expert Systems with Applications, 2011, 38(5): 6300-6306.

[8] JOACHIMS T. A statistical learning model of text classification with support vector machines [C]// SIGIR ’01: Proceedings of the 24th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New York: ACM, 2001: 128-136.

[9] JOACHIMS T. A probabilistic analysis of the Rochhio algorithm with TFIDF for text categorization [C]// ICML ’97: Proceedings of the Fourteenth International Conference on Machine Learning. San Francisco: Morgan Kaufmann, 1997: 143-151.

[10] HAJMOHAMMADI M S, IBRAHIM R, SELAMAT A, et al. Combination of active learning and self-training for cross-lingual sentiment classification with density analysis of unlabelled samples [J]. Information Sciences, 2015, 317: 67-77.

[11] LENG Y, XU X, QI G. Combining active learning and semi-supervised learning to construct SVM classifier [J]. Knowledge-Based Systems, 2013, 44(1): 121-131.

[12] COVER T M. HART P E. Nearest neighbor pattern classification [J]. IEEE Transactions on Information Theory, 1967, 13(1): 21-27.

[13] FAN X, GUO Z, MA H. An improved EM-based semi-supervised learning method [C]// IJCBS ’09: Proceedings of the 2009 International Joint Conference on Bioinformatics, Systems Biology and Intelligent Computing. Washington, DC: IEEE Computer Society, 2009: 529-532.

[14] FAN X, GUO Z, MA H. A semi-supervised text classfification method based on incremental EM algorithm [C]// ICIE ’10: Proceedings of the 2010 WASE International Conference on Information Engineering. Washington, DC: IEEE Computer Society, 2010: 211-214.

[15] 黎雋男,呂佳.結合主動學習與置信度投票的集成自訓練方法[J].計算機工程與應用,2016,52(20):167-171.(LI J N, LYU J. Ensemble self-training method based on active learning and confidence voting [J]. Computer Engineering and Applications, 2016, 52(20): 167-171.)

[16] TRIGUERO I, SáEZ J A, LUENGO J, et al. On the characterization of noise filters for self-training semi-supervised in nearest neighbor classification [J]. Neurocomputing, 2014, 132(13): 30-41.

[17] GAN H, SANG N, HUANG R, et al. Using clustering analysis to improve semi-supervised classification [J]. Neurocomputing, 2013, 101(3): 290-298.

[18] YIN X, SHU T, HUANG Q. Semi-supervised fuzzy clustering with metric learning and entropy regularization [J]. Knowledge-Based Systems, 2012, 35(15): 304-311.

[19] 陳日新,朱明旱.半監(jiān)督K近鄰分類方法[J].中國圖象圖形學報,2013,18(2):195-200.(CHEN R X, ZHU M H. Semi-supervisedK-nearest neighbor classification method [J]. Journal of Image and Graphics, 2013, 18(2): 195-200.)

[20] WILSON D L. Asymptotic properties of nearest neighbor rules using edited data [J]. IEEE Transactions on Systems Man & Cybernetics, 1972, SMC- 2(3): 408-421.

[21] TOMEK I. An experiment with the edited nearest-neighbor rule [J]. IEEE Transactions on Systems Man & Cybernetics, 1976, 6(6): 448-452.

[22] HATTOR K, TAKAHASHI M. A new editedk-nearest neighbor rule in the pattern classification problem [J]. Pattern Recognition, 2000, 33 (3): 521-528.

This work is partially supported by Chongqing Natural Science Foundation of China (cstc2014jcyjA40011), Science and Technology Project of Chongqing Municipal Education Commission (KJ1400513), Chongqing Scientific Research Project (CYS17176), Chongqing Normal University Research Project (YKC17001).

LYUJia, born in 1978, Ph. D., professor. Her research interests include machine learning, data mining.

LIJunnan, born in 1992, M. S. candidate. His research interests include machine learning, data mining.