結(jié)合支持向量機(jī)與半監(jiān)督K-means的新型學(xué)習(xí)算法

杜陽(yáng)　姜震　馮路捷

摘 要：半監(jiān)督學(xué)習(xí)結(jié)合少量有標(biāo)簽樣本和大量無(wú)標(biāo)簽樣本，可以有效提高算法的泛化性能。傳統(tǒng)的半監(jiān)督支持向量機(jī)（SVM）算法在目標(biāo)函數(shù)中引入無(wú)標(biāo)簽樣本的依賴項(xiàng)來(lái)推動(dòng)決策面通過(guò)低密度區(qū)域，但往往會(huì)帶來(lái)高計(jì)算復(fù)雜度和局部最優(yōu)解等問(wèn)題。同時(shí)，半監(jiān)督K-means算法面臨著如何有效利用監(jiān)督信息進(jìn)行質(zhì)心的初始化及更新等問(wèn)題。針對(duì)上述問(wèn)題，提出了一種結(jié)合SVM和半監(jiān)督K-means的新型學(xué)習(xí)算法（SKAS）。首先，提出一種改進(jìn)的半監(jiān)督K-means算法，從距離度量和質(zhì)心迭代兩個(gè)方面進(jìn)行了改進(jìn);然后，設(shè)計(jì)了一種融合算法將半監(jiān)督K-means算法與SVM相結(jié)合以進(jìn)一步提升算法性能。在6個(gè)UCI數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，所提算法在其中5個(gè)數(shù)據(jù)集上的運(yùn)行結(jié)果都優(yōu)于當(dāng)前先進(jìn)的半監(jiān)督SVM算法和半監(jiān)督K-means算法，且擁有最高的平均準(zhǔn)確率。

關(guān)鍵詞：支持向量機(jī);K-means;半監(jiān)督聚類;分類;融合

中圖分類號(hào)： TP181;TP301.6算法理論文獻(xiàn)標(biāo)志碼：A

Novel learning algorithm combining support vector machine and semi-supervised K-means

DU Yang， JIANG Zhen*， FENG Lujie

（College of Computer Science and Communication Engineering， Jiangsu University， Zhenjiang Jiangsu 212013， China）

Abstract： Semi-supervised learning can effectively improve the generalization performance of algorithm by combining a few labeled samples and large number of unlabeled samples. The traditional semi-supervised Support Vector Machine （SVM） algorithm introduces unlabeled sample dependencies into the objective function to drive the decision-making surface through the low-density region， but it often brings problems such as high computational complexity and local optimal solution. At the same time， semi-supervised K-means algorithm faces the problems of how to effectively use the supervised information to initialize and update the centroid. To solve these problems， a novel learning algorithm of Semi-supervised K-means Assisted SVM （SKAS） was proposed. Firstly， an improved semi-supervised K-means algorithm was proposed， which was improved from two aspects： distance measurement and centroid iteration. Then， a fusion algorithm was designed to combine semi-supervised K-means algorithm with SVM in order to further improve the performance of the algorithm. The experimental results on six UCI datasets show that， the proposed method outperforms the current advanced semi-supervised SVM and semi-supervised K-means algorithms on five datasets and has the highest average accuracy.

Key words： Support Vector Machine （SVM）; K-means; semi-supervised clustering; classification; fusion

0 引言

傳統(tǒng)的機(jī)器學(xué)習(xí)算法需要大量的有標(biāo)簽樣本作為訓(xùn)練集，但現(xiàn)實(shí)生活中大量數(shù)據(jù)往往是沒(méi)有被標(biāo)注的，人工標(biāo)注數(shù)據(jù)的代價(jià)太高。半監(jiān)督學(xué)習(xí)[1-3]則利用大量無(wú)標(biāo)簽樣本和少量有標(biāo)簽樣本來(lái)提高學(xué)習(xí)模型的泛化性能，主要可分為兩大類：

1）半監(jiān)督分類算法利用無(wú)標(biāo)簽樣本結(jié)合有標(biāo)簽樣本進(jìn)行模型訓(xùn)練，獲得性能更優(yōu)的分類器，彌補(bǔ)有標(biāo)簽樣本不足的缺陷。其中半監(jiān)督支持向量機(jī)（Support Vector Machine， SVM）[4-7]是目前應(yīng)用較為廣泛的一種半監(jiān)督分類算法，其主要思想是在同時(shí)考慮有標(biāo)記樣本和未標(biāo)記樣本的前提下，找到最大間隔劃分超平面并穿過(guò)數(shù)據(jù)低密度區(qū)域。大量無(wú)標(biāo)簽樣本的引入提高了算法的復(fù)雜度，并且容易陷入局部最優(yōu)解。半監(jiān)督SVM集成是[8-10]當(dāng)前的一個(gè)研究熱點(diǎn)，通過(guò)集成多個(gè)半監(jiān)督SVM基分類器來(lái)進(jìn)一步提高泛化性能;但仍面臨著算法復(fù)雜性和局部最優(yōu)解等問(wèn)題。

2）半監(jiān)督聚類算法通過(guò)利用額外的監(jiān)督信息來(lái)獲得更好的聚類效果。目前所用的監(jiān)督信息主要有兩種形式：第一種形式是“必連”（must-link）與“勿連”（cannot-link），即兩個(gè)樣本屬于同一類為“必連”，不屬于同一類則為“勿連”[11];第二種形式是利用少量樣本的類別標(biāo)簽，即用有標(biāo)簽樣本初始化K值和質(zhì)心[12]。但簇的個(gè)數(shù)不一定等于類別數(shù)以及質(zhì)心迭代等問(wèn)題依然對(duì)算法性能有著較大的影響。

半監(jiān)督分類和聚類分別從不同的角度結(jié)合有標(biāo)簽樣本和無(wú)標(biāo)簽樣本進(jìn)行樣本的劃分，將二者結(jié)合是提高學(xué)習(xí)性能的一種可行方向，但是當(dāng)前類似的研究極少。本文提出了一種結(jié)合SVM和半監(jiān)督K-means的新型學(xué)習(xí)算法（novel learning algorithm of Semi-supervised K-means Assisted SVM， SKAS）。該算法融合了SVM和半監(jiān)督K-means（Semi-Supervised K-means， SSK）的預(yù)測(cè)結(jié)果，通過(guò)二者的優(yōu)勢(shì)互補(bǔ)提升了算法的分類性能。特別地，從距離度量和質(zhì)心迭代兩個(gè)方面對(duì)半監(jiān)督K-means算法進(jìn)行了改進(jìn)，進(jìn)一步提高了算法的泛化性能。

1 相關(guān)工作

1.1 半監(jiān)督SVM

半監(jiān)督SVM是目前半監(jiān)督分類算法中較流行的一種分類算法。其中，半監(jiān)督SVM的目標(biāo)函數(shù)優(yōu)化問(wèn)題是一個(gè)混合整數(shù)規(guī)劃問(wèn)題，難以有效地解決。目前，針對(duì)該問(wèn)題人們已經(jīng)提出了各種方法，經(jīng)典的方法有：Belkin等[4]提出的Laplacian SVM算法，Joachims等[5]提出的Transductive SVM算法，Chapelle等[6]提出的半監(jiān)督支持向量機(jī)（Semi-Supervised Support Vector Machines， S3VMs）算法，以及Li等 [7]提出的安全半監(jiān)督SVM（Safe Semi-Supervised SVMs， S4VMs）算法等。

另一方面，一些研究者發(fā)現(xiàn)：半監(jiān)督SVM與集成學(xué)習(xí)相結(jié)合可以進(jìn)一步提高分類性能[9-10]。Zhang等 [8]提出了一種新的半監(jiān)督SVM集成算法。該算法綜合考慮了多種干擾因素對(duì)數(shù)據(jù)分布的影響，并提出了一種基于聚類評(píng)價(jià)方法的綜合評(píng)價(jià)方法。

1.2 半監(jiān)督聚類

目前，關(guān)于半監(jiān)督聚類的研究主要基于約束信息[13-16]。根據(jù)用戶提供的約束信息，相應(yīng)地修改聚類算法的目標(biāo)函數(shù)來(lái)指導(dǎo)聚類過(guò)程。Wagstaff等 [11]提出了Constranined K-means算法，根據(jù)樣本集以及“必連”和“勿連”關(guān)系進(jìn)行算法的迭代[17-18]。Basu等[12]提出了Constrained Seed K-means算法，即將有標(biāo)簽樣本作為“種子”，用它們初始化K個(gè)質(zhì)心，并且在聚類簇迭代更新過(guò)程中不改變種子樣本的簇隸屬關(guān)系[19-20]。Pelleg等[14]提出了線性時(shí)間約束向量化誤差算法。Zeng等[15]引入有效損失函數(shù)克服了成對(duì)約束違反問(wèn)題，提出了成對(duì)約束最大間隔聚類算法。何萍等 [16]研究成對(duì)約束對(duì)周圍無(wú)約束樣本點(diǎn)的影響，將在頂點(diǎn)上低層隨機(jī)游走和在組件上高層隨機(jī)游走相結(jié)合，提出了一種雙層隨機(jī)游走半監(jiān)督聚類算法。

2 SKAS

本文提出了一種改進(jìn)的半監(jiān)督K-means算法，并結(jié)合SVM來(lái)提高分類算法的性能，其基本思想如圖1所示。

設(shè)訓(xùn)練樣本Dl、測(cè)試樣本Du、訓(xùn)練樣本的標(biāo)簽C分別為：

Dl={（x1，y1），（x2，y2），…，（xm，ym）}

Du={（xm+1，ym+1），（xm+2，ym+2），…，（xm+l，ym+l）}

C={C1，C2，…，CK}

其中：m為訓(xùn)練樣本的個(gè)數(shù);l為測(cè)試樣本的個(gè)數(shù);K為類別個(gè)數(shù)。

2.1 SVM算法

2.1.1 訓(xùn)練

基于訓(xùn)練集Dl，在樣本空間中找到劃分超平面，將不同類別的樣本分開(kāi)。得到基于SVM訓(xùn)練的模型。

minw，b，ξ=12‖w‖2+c∑mi=1ξi

s. t. yi（（w*xi）+b）≥1-ξi; i=1，2，…，m

ξi≥0; i=1，2，…，m（1）

其中：w是法向量，決定了超平面的方向;b是位移項(xiàng);m是樣本個(gè)數(shù);ξi為標(biāo)準(zhǔn)數(shù)據(jù)上的松弛變量;c是給定的懲罰因子。

2.1.2 測(cè)試

SVM的決策函數(shù)f（x）為：

f（x）=sgn（wTψ（x）+b）=

sgn（∑li=1yiαiK（xi，x）+b）（2）

式（2）第二個(gè)等式右邊括號(hào)里面的量是一個(gè)與超平面的距離成正比的量。這種算法的思想是離超平面越遠(yuǎn)的點(diǎn)認(rèn)為分對(duì)的可能性越大。

基于上述原理，利用sigmoid函數(shù)將決策函數(shù)f（x）投射到[0，1]上，得到SVM輸出樣本預(yù)測(cè)概率值的計(jì)算式為：

Pr（y=1|x）≈PA，B（f）≡11+exp（Af+B）（3）

其中f為式（2）中的f（x）。

式（3）中的A和B值這兩個(gè)參數(shù)是用來(lái)調(diào)整映射值的大小，這兩個(gè)參數(shù)是未知的，需要估計(jì)，計(jì)算式如下：

min{-∑i（ti lb（pi）+（1-ti）lb（1-pi））}（4）

其中：

Pi=11+exp（Afi+B）

t+=N++1N-+2

t-=1N-+2（5）

式中：t+表示樣本屬于正類; t-表示樣本屬于負(fù)類。

在處理多分類問(wèn)題上采用one-versus-one法，在任意兩類樣本之間找到一個(gè)超平面，樣本屬于每個(gè)類有一個(gè)概率函數(shù)。因此K個(gè)類別的樣本就需要設(shè)計(jì)K（K-1）/2個(gè)超平面。當(dāng)對(duì)一個(gè)未知樣本進(jìn)行分類時(shí)，根據(jù)投票法原則，最后得票最多的類別即為該未知樣本的類別。

2.1.3 置信度計(jì)算

為了計(jì)算預(yù)測(cè)樣本的置信度，最直接的方法是將數(shù)據(jù)預(yù)測(cè)類別的概率作為權(quán)重，選擇最大的類預(yù)測(cè)概率PSVM（y=cmax_ j|xj）作為置信度CSVM（xj），即：

CSVM（xj）=PSVM（y=cmax_ j|xj）（6）

但僅將類的最大預(yù)測(cè)概率作為置信度不夠合理，因此采用一種新的置信度計(jì)算方法[21]，其通過(guò)類別最大的概率與第二大概率的差值來(lái)衡量置信度，即：

CSVM（xj）=PSVM（y=cmax_ j|xj）-

PSVM（y=csub_max_ j|xj）（7）

這種置信度計(jì)算方法可以針對(duì)類重疊區(qū)域的數(shù)據(jù)，有效解決SVM在類重疊情況下性能下降的問(wèn)題。

2.2 半監(jiān)督K-means算法

2.2.1 初始化質(zhì)心

K-means算法有著K值和初始質(zhì)心難以確定的問(wèn)題，一般認(rèn)為：同一個(gè)簇內(nèi)的樣本應(yīng)該屬于一個(gè)類，而同一個(gè)類的樣本可能位于不同的簇。本文假定簇個(gè)數(shù)K等于類別數(shù)，若一個(gè)類對(duì)應(yīng)多個(gè)簇，則將這些簇當(dāng)作一個(gè)大簇的子簇進(jìn)行處理，從而在尋找最優(yōu)的K值的過(guò)程中實(shí)現(xiàn)算法簡(jiǎn)化。因此，本文首先根據(jù)訓(xùn)練集中的類別確定K值以及每個(gè)簇的標(biāo)簽。其次，根據(jù)訓(xùn)練集中每個(gè)樣本的標(biāo)簽，把它們依次劃分入每一個(gè)簇中，計(jì)算每個(gè)簇的初始質(zhì)心：

μi = 1|Ci|∑xi∈Ci xi（8）

其中Ci表示當(dāng)前樣本屬于的簇。

確定了K值并初始化質(zhì)心后，計(jì)算樣本與各個(gè)質(zhì)心的距離，將樣本劃入相應(yīng)的簇并更新質(zhì)心，直到滿足某個(gè)停止條件為止。

對(duì)于給定的質(zhì)心μ和樣本x，傳統(tǒng)的距離計(jì)算公式為：

distance（μ，x）=∑Dd=1（μd-xd）2（9）

由于數(shù)據(jù)集中各類別之間的樣本數(shù)會(huì)存在差異，訓(xùn)練過(guò)程會(huì)向樣本數(shù)較多的類別傾斜。針對(duì)該問(wèn)題，本文提出了一種基于權(quán)重的改進(jìn)距離公式如下：

distance（μ，x）=ViV∑|D|d=1（μd-xd）2（10）

其中：Vi代表訓(xùn)練集中質(zhì)心i所屬的類別中樣本的個(gè)數(shù); V代表訓(xùn)練集中所有樣本的個(gè)數(shù);D代表數(shù)據(jù)集中樣本的維度。

根據(jù)式（10），將樣本劃入相應(yīng)的簇，并確定其所屬類別。

2.2.2 質(zhì)心迭代的終止條件

傳統(tǒng)的聚類學(xué)習(xí)中，質(zhì)心迭代的終止條件往往有兩種：第一種是預(yù)先設(shè)置好迭代次數(shù);第二種是計(jì)算迭代前后的誤差，若小于某個(gè)值，則終止迭代。這種迭代的終止條件往往會(huì)造成迭代次數(shù)超過(guò)最優(yōu)迭代次數(shù)時(shí)，算法的性能會(huì)急劇下降。特別地，在半監(jiān)督K-means中，由于簇中的噪聲會(huì)影響到質(zhì)心的計(jì)算，并可能造成算法性能的下降。因此，本文提出一種新的迭代終止條件，根據(jù)Dl上預(yù)測(cè)結(jié)果的準(zhǔn)確率進(jìn)行判斷。

ACC（Dl）

其中：ACC為基于當(dāng)前質(zhì)心的預(yù)測(cè)準(zhǔn)確率;old_ACC為基于上一輪質(zhì)心的準(zhǔn)確率。當(dāng)準(zhǔn)確率下降即滿足式（11）時(shí)，表明受簇內(nèi)噪聲的影響，繼續(xù)迭代所產(chǎn)生的質(zhì)心會(huì)降低算法性能。此時(shí)，停止迭代并恢復(fù)上一輪的質(zhì)心。

該方法兼顧了聚類的傳統(tǒng)指標(biāo)誤差平方和（Sum of Squares of Errors， SSE）和分類的準(zhǔn)確度，在實(shí)驗(yàn)中表現(xiàn)出比較明顯的優(yōu)勢(shì)。

2.2.3 置信度計(jì)算

P[i]代表樣本i屬于當(dāng)前簇的概率，其計(jì)算式為：

P[i]=（1/d[cluster[i]]）/sum（12）

其中：cluster[i]代表樣本i屬于的簇標(biāo)號(hào);d[j]代表第j個(gè)簇中，當(dāng)前樣本i到達(dá)質(zhì)心的距離;sum=∑Kj=11d[j]代表當(dāng)前樣本i到達(dá)每個(gè)質(zhì)心的距離的倒數(shù)和。

置信度的計(jì)算式如下：

CSKAS（xj）=PSKAS（y=cmax_ j|xj）-

PSKAS（y=csub_max_ j|xj）（13）

2.3 融合算法

結(jié)合2.1節(jié)和2.2節(jié)中的算法，并為了進(jìn)一步提高準(zhǔn)確率，將SVM和半監(jiān)督K-means結(jié)合起來(lái)進(jìn)行最終的預(yù)測(cè)。SVM和半監(jiān)督K-means的預(yù)測(cè)結(jié)果都轉(zhuǎn)化為概率的形式，但二者預(yù)測(cè)的概率并不在同一尺度上，直接把預(yù)測(cè)的結(jié)果結(jié)合起來(lái)并不能得到滿意的結(jié)果。因此，對(duì)SVM和半監(jiān)督K-means預(yù)測(cè)的置信度做了歸一化處理，然后給出了最終的分類結(jié)果。

P（yi|xi）SKAS=

P（yi|xi）SSK， μ·CSSK（xi）∑xj∈UCSSK（xj）>（1-μ）CSVM（xi）∑xj∈UCSVM（xj）

P（yi|xi）SVM，其他 （14）

其中，μ∈[0，1]，是一個(gè)用來(lái)調(diào)節(jié)SVM和半監(jiān)督K-means權(quán)重的參數(shù)。為了獲得更好的效果，根據(jù)SVM和半監(jiān)督K-means在訓(xùn)練集上的準(zhǔn)確率來(lái)調(diào)節(jié)其權(quán)重，如式（15）所示：

μ=W1/（W1+W2）（15）

其中，W1、W2分別代表SVM和半監(jiān)督K-means對(duì)有標(biāo)簽樣本所屬類別預(yù)測(cè)的準(zhǔn)確率。

2.4 SKAS

SKAS的流程如下：

輸入 Dl={（x1，y1），（x2，y2），…，（xm，ym）}，Du={（xm+1，ym+1），（xm+2，ym+2），…，（xm+l，ym+l）};

輸出 Du中每個(gè)樣本的預(yù)測(cè)標(biāo)簽。

步驟1 在Dl上訓(xùn)練SVM，然后分類Du中樣本，根據(jù)式（7）得到每個(gè)樣本的置信度。

步驟2 根據(jù)Dl中的有標(biāo)簽樣本初始化K個(gè)質(zhì)心，并根據(jù)距離公式（10）將Dl∪Du中的所有樣本劃分到最近的簇中。

步驟3 重復(fù)步驟4～5直到質(zhì)心不再變化或滿足式（11）。

步驟4 根據(jù)式（8）更新每個(gè)簇里面的質(zhì)心。

步驟5 根據(jù)距離公式（10）重新把Dl∪Du中所有的樣本劃分到最近的簇中。

步驟6 根據(jù)迭代終止后每個(gè)簇的質(zhì)心，把Du中樣本重新劃分到最近的簇中，根據(jù)式（13）得到每個(gè)樣本的置信度。

步驟7 對(duì)SVM和半監(jiān)督K-means的預(yù)測(cè)結(jié)果進(jìn)行融合，根據(jù)式（14）計(jì)算Du中樣本所屬類別及其概率。

3 實(shí)驗(yàn)與結(jié)果分析

3.1 數(shù)據(jù)集

針對(duì)本文提出的算法模型，使用來(lái)自UCI的六個(gè)數(shù)據(jù)集作為性能測(cè)試數(shù)據(jù)，隨機(jī)選取30%作為訓(xùn)練集。同時(shí)，為了防止類別不平衡或樣本數(shù)量較少導(dǎo)致訓(xùn)練集未能覆蓋所有類別的情況，當(dāng)隨機(jī)選取的訓(xùn)練集中缺少某個(gè)類別的樣本時(shí)，則向訓(xùn)練集中補(bǔ)充一個(gè)缺失類別的樣本，從而保證K值等于訓(xùn)練集中類別的個(gè)數(shù)。數(shù)據(jù)集的詳細(xì)信息如表1所示。

3.2 結(jié)果分析

為了評(píng)估SKAS的分類性能，在標(biāo)準(zhǔn)SVM的基礎(chǔ)上加入S4VMs[7]、EnsembleS3VM[8]和Constrained Seed K-means算法[12]進(jìn)行實(shí)驗(yàn)對(duì)比。對(duì)于每種算法，均使用與SKAS相同的訓(xùn)練預(yù)測(cè)方法，即基于LIBSVM使用五折交叉檢驗(yàn)，所有算法均使用五次結(jié)果的平均值作為最終結(jié)果;其五折交叉驗(yàn)證通過(guò)調(diào)用LIBSVM軟件包中的grid函數(shù)實(shí)現(xiàn)，并對(duì)特征值進(jìn)行了歸一化的處理，通過(guò)調(diào)用svm-scale來(lái)實(shí)現(xiàn)。

表2給出了四種不同算法對(duì)六個(gè)數(shù)據(jù)集進(jìn)行訓(xùn)練預(yù)測(cè)的實(shí)驗(yàn)結(jié)果。實(shí)驗(yàn)采用跟文獻(xiàn)[8]相同的參數(shù)設(shè)置，對(duì)比后發(fā)現(xiàn)：在所有數(shù)據(jù)集中，SKAS中的五個(gè)數(shù)據(jù)集具有最高的準(zhǔn)確率，剩下一個(gè)接近最好算法的準(zhǔn)確率，并且SKAS的平均準(zhǔn)確率為75.77，優(yōu)于其他三種算法。實(shí)驗(yàn)結(jié)果表明SKAS能夠提高預(yù)測(cè)模型的準(zhǔn)確率。

選擇其中三個(gè)數(shù)據(jù)集iris、glass和thyroid，分別給出它們的準(zhǔn)確率在SVM、Constrained Seed K-means和本文提出的SKAS迭代訓(xùn)練過(guò)程中的變化情況。

首先，由圖2可以看出，本文提出的SKAS在迭代開(kāi)始的準(zhǔn)確率都有上升，并在到達(dá)峰值后開(kāi)始下降，峰值點(diǎn)在圖中已標(biāo)出。根據(jù)2.2.2節(jié)中本文提出的新的迭代終止條件，發(fā)現(xiàn)圖2（a）至圖2（c）中SKAS的峰值即為迭代的終止點(diǎn)，進(jìn)一步說(shuō)明，根據(jù)新設(shè)置的迭代終止條件提前終止迭代可以取得更好的聚類效果。

其次，從圖2可以發(fā)現(xiàn)，SKAS的準(zhǔn)確率均高于SVM算法和半監(jiān)督K-means算法。這也表明了本文提出的融合算法綜合了SVM和半監(jiān)督K-means的預(yù)測(cè)結(jié)果，確實(shí)能有效地提高模型的泛化性能。

圖2（c）中，SKAS的準(zhǔn)確率遠(yuǎn)遠(yuǎn)高于其他兩種算法，主要是因?yàn)閠hyroid的樣本數(shù)量較大，且樣本的不平衡率較高。本文提出的算法有效地解決了在樣本數(shù)量較多以及類別不平衡時(shí)，SVM算法分類性能下降的問(wèn)題。此外，圖2（c）中半監(jiān)督K-means的準(zhǔn)確率低于SVM，分析其原因可能是thyroid的特征數(shù)較多，類重疊現(xiàn)象較為嚴(yán)重。

4 結(jié)語(yǔ)

本文對(duì)半監(jiān)督K-means算法進(jìn)行了相應(yīng)改進(jìn)，提出了一種結(jié)合SVM與半監(jiān)督K-means算法的新型學(xué)習(xí)算法——SKAS，該算法可以實(shí)現(xiàn)半監(jiān)督聚類和分類算法的優(yōu)勢(shì)互補(bǔ)。實(shí)驗(yàn)結(jié)果表明，SKAS相較于對(duì)比算法取得了更好的性能結(jié)果，特別是在樣本數(shù)量較大的情況下，本文算法的優(yōu)勢(shì)更為明顯。

為進(jìn)一步優(yōu)化學(xué)習(xí)算法，我們后續(xù)工作將主要集中在半監(jiān)督K-means算法的進(jìn)一步改進(jìn)上，特別是簇的數(shù)量與實(shí)際類別數(shù)量不一致的問(wèn)題。此外，我們還將關(guān)注類別不平衡問(wèn)題，研究通過(guò)改進(jìn)算法的目標(biāo)函數(shù)以提高小類別樣本的查全率。

參考文獻(xiàn) （References）

[1]ZHU X， GOLDBERG A B. Introduction to Semi-Supervised Learning [M]. San Rafael： Morgan and Claypool Publishers， 2009： 130.

[2]ZHANG Z， SCHULLER B. Semi-supervised learning helps in sound event classification [C]// Proceedings of the 37th IEEE International Conference on Acoustics， Speech， and Signal Processing. Piscataway： IEEE， 2012： 333-336.

[3]ZHU X. Semi-supervised learning [C]// Proceedings of the 2011 International Joint Conference on Artificial Intelligence. Menlo Park： AAAI， 2011： 1142-1147.

[4]BELKIN M， NIYOGI P， SINDHWANI V. Manifold regularization： a geometric framework for learning from labeled and unlabeled examples [J]. Journal of Machine Learning Research， 2006， 7： 2399-2434.

[5]JOACHIMS T. Transductive inference for text classification using support vector machines [C]// Proceedings of the 1999 International Conference on Machine Learning. San Francisco： Morgan Kaufmann Publishers Inc.， 1999： 200-209.

[6]CHAPELLE O， CHI M， ZIEN A. A continuation method for semi-supervised SVMs [C]// Proceedings of the 2006 Twenty-Third International Conference on Machine Learning. New York： ACM， 2006： 185-192.

[7]LI Y， ZHOU Z. Towards making unlabeled data never hurt [C]// Proceedings of the 28th International Conference on Machine Learning. Madison： Omnipress， 2011： 1081-1088.

[8]ZHANG D， JIAO L， BAI X， et al. A robust semi-supervised SVM via ensemble learning [J]. Applied Soft Computing， 2018， 65： 632-643.

[9]ZHOU Z. When semi-supervised learning meets ensemble learning [C]// Proceedings of the 8th International Workshop on Multiple Classifier Systems， LNCS 5519. Berlin： Springer， 2009： 529-538.

[10]PLUMPTON C O， KUNCHEVA L I， OOSTERHOF N N， et al. Naive random subspace ensemble with linear classifiers for real-time classification of fMRI data [J]. Pattern Recognition， 2012， 45（6）： 2101-2108.

[11]WAGSTAFF K， CARDIE C， ROGERS S， et al. Constrained K-means clustering with background knowledge [C]// Proceedings of the 8th International Conference on Machine Learning. San Francisco： Morgan Kaufmann Publishers Inc.， 2001： 577-584.

[12]BASU S， BANERJEE A， MOONEY R J. Semi-supervised clustering by seeding [C]// Proceedings of the 9th International Conference on Machine Learning. San Francisco： Morgan Kaufmann Publishers Inc.， 2002： 27-34.

[13]DING S， JIA H， ZHANG L， et al. Research of semi-supervised spectral clustering algorithm based on pairwise constraints [J]. Neural Computing and Applications， 2014， 24（1）： 211-219.

[14]PELLEG D， BARAS D. K-means with large and noisy constraint sets [C]// Proceedings of the 18th European Conference on Machine Learning. Berlin： Springer， 2007： 674-682.

[15]ZENG H， CHEUNG Y. Semi-supervised maximum margin clustering with pairwise constraints [J]. IEEE Transactions on Knowledge and Data Engineering， 2012， 24（5）： 926-939.

[16]何萍，徐曉華，陸林，等.雙層隨機(jī)游走半監(jiān)督聚類[J].軟件學(xué)報(bào)，2014，25（5）：997-1013.（HE P，? XU X H， LU L， et al. Semi-supervised clustering via two-level random walk [J]. Journal of Software， 2014， 25（5）： 997-1013.）

[17]STEINLEY D， BRUSCO M J. K-means clustering and mixture model clustering： reply to McLachlan （2011） and Vermunt （2011） [J]. Psychological Methods， 2011， 16（1）： 89-92.

[18]HONG Y， KWONG S. Learning assignment order of instances for the constrained K-means clustering algorithm [J]. IEEE Transactions on Systems， Man， and Cybernetics， Part B： Cybernetics， 2009， 39（2）： 568-574.

[19]LI K， ZHANG C， CAO Z. Semi-supervised kernel clustering algorithm based on seed set [C]// Proceedings of the 2009 Asia-Pacific Conference on Information Processing. Piscataway： IEEE， 2009： 169-172.

[20]GU L， SUN F. Two novel kernel-based semi-supervised clustering methods by seeding [C]// Proceedings of the 2009 Chinese Conference on Pattern Recognition. Piscataway： IEEE， 2009： 1-5.

[21]尹玉，詹永照，姜震.偽標(biāo)簽置信選擇的半監(jiān)督集成學(xué)習(xí)視頻語(yǔ)義檢測(cè)[J].計(jì)算機(jī)應(yīng)用，2019，39（8）：2204-2209.（YIN Y， ZHAN Y Z， JIANG Z. Semi-supervised integrated learning video semantic detection with false label confidence selection [J]. Journal of Computer Applications， 2019， 39（8）： 2204-2209.）

This work is partially supported by the National Natural Science Foundation of China （61672268）， the Research Initiation Fund for Senior Talents of Jiangsu University （14JDG036）.

DU Yang， born in 1994， M. S. candidate. His research interests include machine learning.

JIANG Zhen， born in 1976， Ph. D.， associate professor. His research interests include machine learning.

FENG Lujie， born in 1996， M. S. candidate. Her research interests include machine learning.

收稿日期：2019-05-14;修回日期：2019-07-23;錄用日期：2019-07-25。

基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目（61672268）;江蘇大學(xué)高級(jí)人才科研啟動(dòng)基金資助項(xiàng)目（14JDG036）。

作者簡(jiǎn)介：杜陽(yáng)（1994—），男（漢族），江蘇揚(yáng)州人，碩士研究生，主要研究方向：機(jī)器學(xué)習(xí); 姜震（1976—），男（漢族），山東煙臺(tái)人，副教授，博士，主要研究方向：機(jī)器學(xué)習(xí); 馮路捷（1996—），女（漢族），江蘇淮安人，碩士研究生，主要研究方向：機(jī)器學(xué)習(xí)。

文章編號(hào)：1001-9081（2019）12-3462-05 DOI：10.11772/j.issn.1001-9081.2019050813