基于密度聚類和鄰域的主動(dòng)學(xué)習(xí)方法

劉志秀，胡峰,，鄧維斌，于洪,

(1.重慶郵電大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,重慶 400065;2.重慶郵電大學(xué) 計(jì)算智能重慶市重點(diǎn)實(shí)驗(yàn)室,重慶 400065)

0 引言

機(jī)器學(xué)習(xí)可以用來解決工程或科學(xué)領(lǐng)域當(dāng)中的一些復(fù)雜問題,因此得到了廣泛的應(yīng)用和研究。傳統(tǒng)的有監(jiān)督機(jī)器學(xué)習(xí)算法需要大量的標(biāo)記數(shù)據(jù)來訓(xùn)練具有良好泛化能力的模型,但是在實(shí)際應(yīng)用中很多數(shù)據(jù)是無標(biāo)記數(shù)據(jù),需要對這些數(shù)據(jù)進(jìn)行標(biāo)注才能有效地應(yīng)用傳統(tǒng)的監(jiān)督學(xué)習(xí)方法。然而,對數(shù)據(jù)進(jìn)行準(zhǔn)確標(biāo)注十分困難和昂貴,因?yàn)檫@通常需要具有特定領(lǐng)域經(jīng)驗(yàn)的人工標(biāo)注者的努力,從領(lǐng)域?qū)＜夷抢铽@得這些標(biāo)簽存在較高的隱性成本,尤其是涉及大量類標(biāo)簽學(xué)習(xí)的項(xiàng)目[1]。例如深度學(xué)習(xí)通常用于圖像處理,但圖像標(biāo)注尤其是醫(yī)學(xué)圖像需要相關(guān)領(lǐng)域的專業(yè)人員才能進(jìn)行準(zhǔn)確標(biāo)注,因此數(shù)據(jù)標(biāo)注成為深度學(xué)習(xí)模型的主要瓶頸[2]。主動(dòng)學(xué)習(xí)是機(jī)器學(xué)習(xí)的一個(gè)分支,是一種適用于具有大量未標(biāo)注數(shù)據(jù)場景的機(jī)器學(xué)習(xí)算法。主動(dòng)學(xué)習(xí)主要由兩個(gè)部分組成[3]:一個(gè)是算法的學(xué)習(xí)引擎,通過這一部分可以完成對有標(biāo)記樣本的學(xué)習(xí)并對無標(biāo)記樣本進(jìn)行預(yù)測;另一個(gè)是算法的采樣引擎,通過一定的樣本選擇策略與標(biāo)注者交互,獲得樣本的標(biāo)簽,加入有標(biāo)記樣本集合,供分類器學(xué)習(xí)。相對于對全部無標(biāo)記的樣本進(jìn)行標(biāo)注或者隨機(jī)選擇樣本進(jìn)行標(biāo)注的代價(jià)高昂和容易出錯(cuò),主動(dòng)學(xué)習(xí)的主要目的是通過選擇盡可能有價(jià)值的樣本,從而以較少的有標(biāo)簽樣本來獲得較為準(zhǔn)確的模型。由于主動(dòng)學(xué)習(xí)有選擇地處理樣本以及與專家交互等特點(diǎn),近年來得到較好的發(fā)展。主動(dòng)學(xué)習(xí)目前在文本分類、圖像識(shí)別等領(lǐng)域得到廣泛研究,例如文[4-5]將基于支持向量機(jī)的主動(dòng)學(xué)習(xí)用于文本分類;文[6]運(yùn)用不確定性抽樣的思想,將基于邊緣的不確定性推廣到多類的情況,大大減少了圖像識(shí)別所需要的訓(xùn)練樣本的數(shù)量和計(jì)算開銷。

本文在聚類算法的基礎(chǔ)上開展了主動(dòng)學(xué)習(xí)的研究,由于聚類算法具有挖掘數(shù)據(jù)內(nèi)部結(jié)構(gòu)信息等優(yōu)點(diǎn),因此早已有研究將聚類算法與主動(dòng)學(xué)習(xí)相結(jié)合,豐富了主動(dòng)學(xué)習(xí)的應(yīng)用。例如文[7]提出的算法首先在聚類的代表性樣本點(diǎn)的集合上構(gòu)造一個(gè)分類器,然后通過局部噪聲模型將分類決策傳播到其他樣本,該模型可以選擇最具代表性的樣本,避免在同一簇中重復(fù)標(biāo)記樣本。文[8]利用層次聚類得到分層聚類樹形結(jié)構(gòu),通過對樹形結(jié)構(gòu)進(jìn)行剪枝操作來最小化分類誤差,然后選擇有效的樣本來提高分類效果。本文算法的另一重點(diǎn)是鄰域模型的應(yīng)用,在鄰域模型的基礎(chǔ)上利用樣本的鄰域信息,選擇數(shù)據(jù)集中信息量較高的樣本進(jìn)行類別標(biāo)注。算法的總體過程是:首先對數(shù)據(jù)進(jìn)行初步聚類;其次,從聚類效果不好的類簇中通過樣本選擇策略選擇樣本進(jìn)行標(biāo)注,之后進(jìn)行下一輪迭代,直到滿足迭代的停止條件。將文中提出的方法與部分有監(jiān)督學(xué)習(xí)算法以及主動(dòng)學(xué)習(xí)算法進(jìn)行了對比,實(shí)驗(yàn)結(jié)果表明,文中提出的方法是一種高效的主動(dòng)學(xué)習(xí)的算法,能在較少的有標(biāo)記樣本的基礎(chǔ)上取得較好的實(shí)驗(yàn)結(jié)果。

0.1 主動(dòng)學(xué)習(xí)模型

主動(dòng)學(xué)習(xí)模型可以由A=(C,L,S,Q,R)表示[9],其中C為基分類器;L為有標(biāo)記樣本集;Q為查詢函數(shù);R為無標(biāo)記樣本集;S為人工標(biāo)注者。用初始有標(biāo)記樣本集L訓(xùn)練一個(gè)基分類器C,然后根據(jù)樣本選擇策略Q從無標(biāo)記樣本集U中選擇有價(jià)值的樣本交由專家S進(jìn)行打標(biāo),以擴(kuò)大有標(biāo)記樣本集合。

主動(dòng)學(xué)習(xí)需要考慮選擇哪些樣本進(jìn)行標(biāo)記,以盡量少的樣本或者盡量低的代價(jià)訓(xùn)練出能夠準(zhǔn)確進(jìn)行預(yù)測的模型。主動(dòng)學(xué)習(xí)的樣本選擇策略可以分為基于流的采樣策略[10]、基于池的采樣策略[11]以及基于合成樣本的采樣策略[12]?；跀?shù)據(jù)流的采樣策略中樣本以流的形式逐個(gè)到達(dá),而基于池的采樣策略每次從樣本構(gòu)成的數(shù)據(jù)池中選擇樣本?；诤铣蓸颖镜牟杉呗允侵苯訌奶卣骺臻g里合成出新的樣本進(jìn)行查詢。從無標(biāo)記樣本進(jìn)行采樣主要有以下幾種樣本選擇策略:

(1)基于不確定性的選擇策略。當(dāng)分類器對樣本類別越不確定的時(shí)候,越容易導(dǎo)致分類錯(cuò)誤,因此增加對這一類樣本的學(xué)習(xí)可以提高分類器的性能?？梢酝ㄟ^各種指標(biāo)評(píng)價(jià)不確定性,比如二分類問題中,類別概率為0.5的樣本具有較高的不確定性;信息熵是用來描述信源的不確定度的概念,因此也可以用于評(píng)價(jià)不確定性?；诓淮_定性的方法適用于多種基分類器,如邏輯回歸[13-14],隱形馬爾科夫模型[15],支持向量機(jī)[16-17]等。但是這類方法可能忽略數(shù)據(jù)的整體結(jié)構(gòu)而導(dǎo)致采樣偏差[18]。

(2)基于代表性的選擇策略。由于基于不確定性的方法有可能造成采樣偏差,有相關(guān)研究利用聚類算法,選擇未標(biāo)記數(shù)據(jù)中有代表性的樣本進(jìn)行標(biāo)記[19-20],例如文[21]選擇聚類中心進(jìn)行標(biāo)注。但是單純基于聚類的方法可能選擇到缺乏信息量的樣本,因此文[22]將聚類算法與支持向量機(jī)相結(jié)合,標(biāo)記每個(gè)類簇中與另一個(gè)類更相似的樣本。

(3)基于版本空間的選擇策略。版本空間是學(xué)習(xí)過程中與數(shù)據(jù)集一致的所有假設(shè)的子集,這一類方法傾向于選擇那些能夠盡可能減小版本空間的樣本來標(biāo)記,比如基于委員會(huì)的啟發(fā)式方法[23-24],選擇當(dāng)前版本空間中的委員會(huì)成員分類最不一致的樣本進(jìn)行標(biāo)記,投票熵[25]可以用于評(píng)價(jià)分歧度。

(4)基于誤差縮減的選擇策略。這一方法選取盡可能降低分類器泛化誤差的實(shí)例進(jìn)行標(biāo)注。這種樣本選擇策略直接通過分類器表現(xiàn),根據(jù)樣本分布來進(jìn)行樣本選擇,因此可以很好地避免野點(diǎn)的選擇,但是這類方法需要大量計(jì)算,并且會(huì)受到損失函數(shù)的準(zhǔn)確性的影響。

0.2 密度峰值聚類算法

Rodriguez等在文[26]當(dāng)中提出了密度峰值聚類算法,該算法基于密度空間且能發(fā)現(xiàn)任意形狀的簇,包括兩點(diǎn)核心思想,一是簇中心樣本點(diǎn)的密度要高于其周圍鄰近點(diǎn)的密度;二是簇中心點(diǎn)之間相距較遠(yuǎn)。因此需要對每個(gè)數(shù)據(jù)點(diǎn)計(jì)算兩個(gè)值,一是密度ρ,二是與特定樣本之間的距離δ。

這里的密度指的是小于預(yù)先設(shè)定的截?cái)嗑嚯x內(nèi)的樣本數(shù),計(jì)算方法如式(1)所示。

(1)

其中dij為樣本i和樣本j之間的距離,dc為截?cái)嗑嚯x。δi為當(dāng)前樣本與密度更高的樣本點(diǎn)的距離的最小值,對于密度值最大的樣本點(diǎn),δi為與其最遠(yuǎn)的樣本點(diǎn)之間的距離。具體計(jì)算方法為:

(2)

在進(jìn)行聚類的時(shí)候,如果一個(gè)數(shù)據(jù)點(diǎn)的ρ與δ都取值較大,則更有可能成為簇的中心點(diǎn)。其余樣本將距離其最近的具有更高密度的樣本視為自己的中心點(diǎn),應(yīng)劃分到同一個(gè)簇中,從而實(shí)現(xiàn)聚類。至于類簇個(gè)數(shù)的選取,文獻(xiàn)中給出的方法是分別以ρ和δ為橫坐標(biāo)和縱坐標(biāo)畫出決策圖,選擇圖中ρ和δ同時(shí)取值較大的樣本點(diǎn)作為聚類的中心。文[27]給出了一種根據(jù)ρ與δ乘積的變化趨勢選擇類簇中心的方法。

0.3 鄰域模型

Lin等人提出了鄰域模型[28],通過樣本點(diǎn)的鄰域?qū)颖究臻g進(jìn)行粒化,將鄰域作為描述空間中其他概念的基本信息粒子。胡清華等人在鄰域模型和經(jīng)典粗糙集的基礎(chǔ)上提出了鄰域粗糙集模型[29],定義如下:

定義1 對于?xi∈U,B?C,xi在屬性子集B上的鄰域定義為:

(3)

其中,ΔB(xi,xj)表示xi與xj之間的距離,σ為樣本的鄰域半徑,表示為:

σ=min(dis(xi,s))+w×range(dis(xi,xj)) ，

(4)

其中min(dis(xi,s))表示樣本s與其他樣本xi之間的距離的最小值,range(dis(xi,s))為樣本s與其他樣本之間的距離范圍,即距離的最大值與最小值之差,w為取值(0,1)區(qū)間內(nèi)的半徑權(quán)重。

1 基于密度聚類和鄰域的主動(dòng)學(xué)習(xí)方法

基于密度聚類的主動(dòng)學(xué)習(xí)算法可以處理初始有標(biāo)記數(shù)據(jù)集為空的數(shù)據(jù),且能利用大量無標(biāo)記數(shù)據(jù)的分布信息選擇代表性的樣本,在一定程度上避免采樣偏差。本文在密度聚類的主動(dòng)學(xué)習(xí)的基礎(chǔ)上[23],融入鄰域模型制定樣本選擇策略,提出了一種基于密度聚類和鄰域的主動(dòng)學(xué)習(xí)方法(Active Learning Methods Based on Density Clustering and Nerghborhood,簡寫為DCN_AL)。

本文方法主要通過聚類算法對數(shù)據(jù)進(jìn)行類別劃分,因而算法性能受到聚類效果的影響。采用的處理方法是利用輪廓系數(shù)[30]選擇出劃分不明確的類簇,優(yōu)先從這些聚類效果不好的類簇中選擇樣本進(jìn)行標(biāo)注。樣本選擇策略同樣是主動(dòng)學(xué)習(xí)的核心。本文結(jié)合鄰域的思想,充分考慮了樣本鄰域信息以及有標(biāo)記樣本和無標(biāo)記樣本的分布信息,動(dòng)態(tài)地計(jì)算樣本的重要程度,優(yōu)先選擇當(dāng)前更為重要的樣本進(jìn)行標(biāo)注。對選擇樣本進(jìn)行標(biāo)注后,用標(biāo)注結(jié)果對聚類結(jié)果進(jìn)行修正,從而達(dá)到節(jié)約有限的標(biāo)注資源的同時(shí)改善算法的效果。

1.1 算法思路

本文采用了交替地執(zhí)行聚類算法和選擇樣本進(jìn)行標(biāo)注的過程,具體步驟介紹如下:

1.1.1 計(jì)算樣本間的距離

首先采用式(5)的方式進(jìn)行距離計(jì)算,本文使用p取2的歐氏距離。為了避免樣本不同屬性間的取值范圍量級(jí)差距較大,因此在距離計(jì)算之前對數(shù)據(jù)進(jìn)行歸一化化處理。

(5)

1.1.2 對所有樣本進(jìn)行密度峰值聚類

分別采用式(1)和(2)所示的方式計(jì)算所有樣本的密度ρ=(ρ1,ρ2,…,ρN)和特殊距離值δ=(δ1,δ2,…,δN),選擇ρ×δ取值靠前的樣本作為聚類的中心,其余樣本點(diǎn)與其中心點(diǎn)劃分到同一個(gè)類簇當(dāng)中。只選取兩個(gè)初始的聚類中心劃分類簇。

1.1.3 計(jì)算輪廓系數(shù)評(píng)價(jià)聚類效果

輪廓系數(shù)不需要樣本的實(shí)際類別信息,可以表示出類內(nèi)聚合度和類間分離度,計(jì)算方式如式(6)所示。

(6)

其中,a(xi)為樣本xi與同一個(gè)簇內(nèi)樣本的平均距離;b(xi)為樣本xi與不在同一個(gè)簇內(nèi)的樣本的平均距離;s(xi)則為樣本xi的輪廓系數(shù)。某一個(gè)類簇的輪廓系數(shù)為簇內(nèi)樣本輪廓系數(shù)的平均值。

1.1.4 劃分樣本鄰域

樣本的鄰域表示的是該樣本鄰域半徑內(nèi)的樣本,鄰域半徑的計(jì)算公式如式(4)所示。為了表達(dá)出每一個(gè)樣本在有標(biāo)記和無標(biāo)記樣本中的分布信息,分別劃分出每個(gè)樣本在有標(biāo)記樣本當(dāng)中的鄰域和無標(biāo)記樣本當(dāng)中的鄰域。

1.1.5 選擇樣本進(jìn)行標(biāo)注

在通過輪廓系數(shù)評(píng)價(jià)出的聚類效果不好的簇當(dāng)中,根據(jù)ρ×δ的值,選擇一個(gè)樣本擴(kuò)大簇中心點(diǎn)集合,以便進(jìn)一步劃分類簇,同時(shí)根據(jù)樣本的鄰域信息,選擇一定數(shù)量的樣本進(jìn)行標(biāo)注。

(1)為了避免選擇到的有標(biāo)記樣本過于集中,因此將每個(gè)樣本與有標(biāo)記樣本鄰域交集的大小作為衡量樣本重要程度的一個(gè)因素,計(jì)算方式如式(7)所示。

(7)

其中δ(s)為樣本s的鄰域,δ(xi)為有標(biāo)記樣本xi的鄰域。如圖1所示,與有標(biāo)記樣本x1鄰域交集更小的s1更有可能被選擇。通過樣本s與有標(biāo)記鄰域內(nèi)各個(gè)類別占鄰域內(nèi)全部有標(biāo)記樣本的比例,作為衡量樣本被劃分為該類別的概率,然后用這個(gè)概率值計(jì)算樣本的信息量。如圖2所示,鄰域內(nèi)類別更多的樣本s1更有可能被選擇,計(jì)算公式如式(8)和式(9)所示。

(8)

(9)

圖2 f2示意圖Fig.2 Schematic diagram of f2

(2)對于輪廓系數(shù)接近0的樣本,可能是類簇劃分不明確的樣本,因此將輪廓系數(shù)作為影響樣本重要程度的因素之一,如圖3所示,與其他類簇相距較近的樣本s1和s2更有可能被選擇,所以樣本s的重要程度的表示如式(11)所示。

f3(s)=c(1-|s(s)|) ，

(10)

importance=f1(s)+f2(s)+f3(s) 。

(11)

圖3 f3示意圖Fig.3 Schematic diagram of f3

1.2 DCN-AL算法描述

輸入:無標(biāo)記的數(shù)據(jù)集U,鄰域半徑參數(shù)w,初始聚類中心數(shù)目k,查詢樣本數(shù)目上限m;

輸出:樣本的預(yù)測標(biāo)簽。

(1) 根據(jù)公式(5)計(jì)算樣本間的距離;

(2) 計(jì)算密度聚類的半徑參數(shù);

(3) 根據(jù)公式(1)計(jì)算樣本密度ρ;

(4) 根據(jù)公式(2)計(jì)算距離其最近的具有更高密度的樣本之間的距離δ;計(jì)算ρ與δ的乘積γ;

(5) 選擇k個(gè)γ值靠前的樣本進(jìn)行密度峰值聚類;

(6) 根據(jù)公式(6)計(jì)算樣本的輪廓系數(shù),以及每個(gè)簇的輪廓系數(shù);

(7) 根據(jù)輪廓系數(shù)評(píng)價(jià)聚類效果;

(8) 在聚類效果不好的類簇中根據(jù)公式(11)計(jì)算樣本的重要性;

(9) 選擇重要性靠前的樣本查詢樣本標(biāo)簽;執(zhí)行步驟(6)進(jìn)行下一輪迭代,直到查詢的樣本數(shù)目達(dá)到指定的上限值。

2 實(shí)驗(yàn)

2.1 實(shí)驗(yàn)描述

實(shí)驗(yàn)采用的數(shù)據(jù)集為加州大學(xué)提供的用于機(jī)器學(xué)習(xí)的標(biāo)準(zhǔn)測試數(shù)據(jù)集,數(shù)據(jù)集可在官網(wǎng)進(jìn)行下載(https:∥archive.ics.uci.edu/ml/index.php)。實(shí)驗(yàn)部分包括分別與有監(jiān)督學(xué)習(xí)和主動(dòng)學(xué)習(xí)的對比實(shí)驗(yàn)。

2.2 實(shí)驗(yàn)方法

本文的方法中,密度聚類的半徑參數(shù)是參照文獻(xiàn)[28]中提供的方法進(jìn)行計(jì)算的,計(jì)算結(jié)果乘以一個(gè)(0,1)區(qū)間內(nèi)的常數(shù)作為鄰域半徑參數(shù)w的取值;查詢樣本上限m為樣本總數(shù)的20%、40% 或60%;初始聚類中心數(shù)目k的取值為log2(m)。第一部分實(shí)驗(yàn)為與部分傳統(tǒng)的有監(jiān)督學(xué)習(xí)方法對比,試驗(yàn)方法對比在不同有標(biāo)記數(shù)據(jù)集大小的情況下,各個(gè)算法準(zhǔn)確率的比較,用五折交叉驗(yàn)證的方法對各個(gè)有監(jiān)督學(xué)習(xí)算法的參數(shù)進(jìn)行一定的調(diào)優(yōu);第二部分實(shí)驗(yàn)是將算法與部分主動(dòng)學(xué)習(xí)算法進(jìn)行對比,試驗(yàn)方法為在不同有標(biāo)簽樣本數(shù)的情況下,各個(gè)算法的精確率的比較。并且在劃分?jǐn)?shù)據(jù)集時(shí),使訓(xùn)練集與測試集樣本分布一致。

2.3 與有監(jiān)督學(xué)習(xí)方法的對比

將本文的方法與幾個(gè)有監(jiān)督方法進(jìn)行對比,包括KNN、CART、GuassianNB以及Logistic Regression算法,這些算法采用scikit-learn開源框架當(dāng)中的實(shí)現(xiàn)。對比在有標(biāo)記樣本的數(shù)目分別占樣本總數(shù)的20%、40%、60%時(shí),各個(gè)算法在測試集上的準(zhǔn)確率,其中準(zhǔn)確率的取值為十次實(shí)驗(yàn)結(jié)果的平均值。表1至表3展示了具體實(shí)驗(yàn)結(jié)果,表格最后一行為排序的均值,本算法分別取得2.2、1.8、1.35,均高于其他算法排序的平均值。

2.4 與主動(dòng)學(xué)習(xí)算法的對比

將本文提出的方法和基于委員會(huì)的主動(dòng)學(xué)習(xí)方法QBC[31],基于不確定性的主動(dòng)學(xué)習(xí)方法Uncertain[4],基于代表性的主動(dòng)學(xué)習(xí)方法Representative[8]以及隨機(jī)選擇樣本策略的主動(dòng)學(xué)習(xí)Random進(jìn)行對比,對比在有標(biāo)記樣本的數(shù)目分別占樣本總數(shù)的20%、40%、60%時(shí),各個(gè)算法在測試集上的精確率,其中精確率的取值為10次實(shí)驗(yàn)結(jié)果的平均值。表4至表6展示了具體實(shí)驗(yàn)結(jié)果,表格最后一行為排序的均值,本算法分別取得2.4、2.5、1.8,均高于其他算法排序的平均值。

表1 20%有標(biāo)記樣本時(shí)各算法準(zhǔn)確率

表2 40%有標(biāo)記樣本時(shí)各算法準(zhǔn)確率

表3 60%有標(biāo)記樣本時(shí)各算法準(zhǔn)確率

表4 20%有標(biāo)記樣本時(shí)各個(gè)主動(dòng)學(xué)習(xí)算法精確率

表5 40%有標(biāo)記樣本時(shí)各個(gè)主動(dòng)學(xué)習(xí)算法精確率

表6 60%有標(biāo)記樣本時(shí)各個(gè)主動(dòng)學(xué)習(xí)算法精確率

3 結(jié)論

本文提出了一種基于密度聚類和鄰域的主動(dòng)學(xué)習(xí)方法,該方法可以解決初始有標(biāo)記數(shù)據(jù)集為空的打標(biāo)問題,結(jié)合樣本的鄰域信息迭代地選擇樣本進(jìn)行類別標(biāo)注,從而提升算法的性能。算法首先對數(shù)據(jù)集進(jìn)行密度峰值聚類;其次用輪廓系數(shù)評(píng)價(jià)聚類效果,再從聚類效果不好的類簇中根據(jù)鄰域信息計(jì)算出的樣本重要性選擇樣本進(jìn)行標(biāo)記,然后進(jìn)行下一輪的聚類;最后滿足一定條件時(shí)結(jié)束主動(dòng)學(xué)習(xí)過程。在主動(dòng)學(xué)習(xí)的每一輪迭代過程中,有標(biāo)記樣本會(huì)對聚類的結(jié)果進(jìn)行一定修正,模擬了與人工標(biāo)注者的交互過程。在UCI數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明,本文提出的方法能在初始數(shù)據(jù)集為空的情況下,在使用較少的有標(biāo)記樣本時(shí),使算法取得較好的結(jié)果。但是本文的方法仍有很多可以改進(jìn)的地方,比如改進(jìn)對樣本選擇策略、選取更優(yōu)的參數(shù)取值等,以提升選擇樣本的價(jià)值與類簇劃分的準(zhǔn)確性等。今后的研究重點(diǎn)是提升算法的分類效果和泛化能力。