張 琳，姜高霞，王文劍

(山西大學 計算機與信息技術學院， 山西 太原 030006)

機器學習是現(xiàn)代計算機快速發(fā)展的領域之一，涉及各個領域的應用。目前，研究人員在深度學習方面取得了很多成果，但其可解釋性依然是難以解決的問題。因此，人在機器學習中的作用依然不可忽視。眾所周知，傳統(tǒng)的數(shù)據(jù)注釋依賴于領域專家，成本高且耗時長，其限制了標簽數(shù)據(jù)集的獲得。而隨著眾包系統(tǒng)的快速發(fā)展，標簽數(shù)據(jù)的獲取變得比較容易，但由于收集的標簽中存在噪聲，眾包數(shù)據(jù)訓練的學習模型質量通常低于專家標記數(shù)據(jù)訓練的模型。直觀上，學習模型的質量與標簽的質量密切相關，因此提高標簽質量是提高學習模型質量的一個直接途徑。

在眾包平臺獲取帶噪聲的標簽數(shù)據(jù)集后，通過設計算法，從多個標簽集合中歸納出一個完整的標簽，這些算法被稱為真相推理算法(ground truth inference algorithms)。在不知道某實例真實標簽的情況下，一般使用真相推理算法推斷其真實標簽，但單純的推理算法的學習是相對困難的。因此，利用實例數(shù)據(jù)分布信息幫助推理算法推斷真實標簽十分重要，且希望每個實例的集成標簽為其真實標簽。

使用重復標簽來提高標簽質量可以追溯到20多年前，Smyth等在1994年使用極大似然估計算法和重復標記去解決金星圖像標記的不確定性[1]。多人投票機制(majority vote，MV)是一種最簡單高效的方法，除了MV算法，近幾年還提出了一些其他的推理算法。這些推理算法可以根據(jù)其數(shù)學方法分為兩類：基于機器學習的算法和基于線性代數(shù)的方法?；跈C器學習的方法是當前研究的主流，早在1979年，Dawid等提出了一種基于最大似然估計的真相推理算法(Dawid-Skene model，DS)[2]，除了為每個例子推斷出集成標簽外，DS還為每個貼標簽者估計了混淆矩陣；Demartini等提出的ZenCrowd[3]算法通過對標記者質量建模來確定每個樣本屬于特定類的概率，但其沒有關注任務難度；而Whitehill等提出的GLAD[4]算法則在此基礎上，對任務難度建模，將此結果應用到對標記者質量的建模中，使推斷結果具有更高的準確性，但導致其代碼運行迭代過程十分緩慢。Sheng等和Ipeirotis等分別于2008年和2014年在研究了MV算法后，提出了簡單的概率模型來描述單樣本的標簽質量[5-6]，但其假設每個標簽的質量均相同。Jung等在2011年針對實例，提出了一種利用評分機制和權重提高MV精度的方法[7]，其中推理模型通常是基于概率圖形模型，在概率圖形模型中進行推理的一種重要的主流通用方法是期望最大化(expectation-maximization，EM)算法。2014年Li等在DS模型下推導了具有任意有限標記者和項目數(shù)的一般類型聚合規(guī)則的錯誤率邊界[8]，可用于設計最優(yōu)加權多數(shù)投票。Khetan等在2016年也分析了廣義DS模型下眾包的可靠性[9]。在基于DS改進的模型中，當類的數(shù)量較大而標簽的數(shù)量較少時，會造成混淆矩陣十分稀疏。

眾包通?；趦蓚€基本的共同假設：貼標簽者有不同的可靠性，并且獨立做決定。一些推理算法只遵循這些假設，例如DS和ZenCrowd。而Raykar等[10]還基于標簽標記者在提供標簽時的偏見，IEThresh[11]則是基于了學習者的經(jīng)驗，正標簽閾值(positive label frequency threshold，PLAT)[12]方法假設標簽者對消極和積極的例子有不同的校正率，LC-ME[13]算法假設每個項都屬于一個潛在類，標簽程序對同一類的項具有一致的視圖，但對不同類的項具有不一致的視圖。

由于僅根據(jù)帶噪音的標簽推斷實例的真實標簽比較困難，因此除了一般的真相推理算法外，近幾年一些學者提出了根據(jù)實例特征和標記者影響等因素去提高標簽集成效果的方法。Tian等在2018年提出了M3V算法[14]，Ruiz等在2018年提出了一種通過變分高斯過程從眾包中學習正確標簽的方法[15]。還有一些學者提出不學習真相推理算法，而直接根據(jù)帶噪音的標簽集學習分類算法。另一些學者利用多任務學習方法去處理眾包標簽噪音，也取得了不錯的效果。目前來看，利用其他信息提高眾包標簽集的集成算法效果是可行的。但現(xiàn)有的算法在多分類問題中的表現(xiàn)相對較差，且在眾包系統(tǒng)中獲取標簽時，標記者越少代價越小，因此希望可以在獲取的眾包標簽數(shù)較少的情況下得到較優(yōu)的標簽推斷結果。由此考慮使用聚類算法研究眾包噪音標簽過濾問題。本文提出的算法主要通過對實例特征聚類及分析標記者相似性兩部分來提高標簽推斷的準確率。

1 單標記眾包標簽的雙重置信度算法

1.1 問題描述

1.2 雙重置信度計算方法

由于提高集成標簽的質量面臨巨大的挑戰(zhàn)，許多研究人員試圖在標簽聚合過程中引入更多的先驗信息，這些方法違反了通用標簽聚合的不可知前提，即除了收集的噪聲標簽外，不能使用任何先驗知識。實例的特征攜帶有價值的信息，如果可以應用適當?shù)臋C器學習方法，這些特征可以幫助識別和分類這些項目。因此，在標簽推斷過程中完全忽略實例的特征是不明智的，且應用特征并不違反不可知論的先決條件。

本文算法主要通過設置標記者置信度推斷實例的集成標簽。標記者置信度由兩部分確定：第一部分是通過聚類算法將實例的特征部分聚類，再根據(jù)聚類結果和標記者提供的標簽，確定每位標記者的正確率，從而得到標記者置信度的第一部分基于數(shù)據(jù)分布特征的置信度；第二部分通過計算標記者提供的標簽間的相似度得到基于標記信息的置信度，若某位標記者與其他標記者提供的結果越相似，則其置信度越高。將兩部分置信度合并，由此得到完整的標記者置信度。

1.2.1 基于數(shù)據(jù)分布特征的置信度

通過對數(shù)據(jù)特征執(zhí)行聚類算法得到基于數(shù)據(jù)分布特征的置信度。通常數(shù)據(jù)集中大多數(shù)的數(shù)據(jù)標記問題是較為簡單的，標記者可以較容易地為這些問題打出正確的標簽，而對于較為困難的一部分數(shù)據(jù)，標記者所提供的標簽很有可能是錯誤的，這時可以通過聚類結果與某一組標簽的一致性來確定某個標記者的置信度，從而提高標簽推斷結果的準確率。

圖1通過一個簡單的例子來說明聚類置信度的可行性。圖中圓形、正方形、三角形分別表示3類數(shù)據(jù)，圖1(a)表示數(shù)據(jù)的真實分布情況，圖2(b)表示標記者w1提供的數(shù)據(jù)劃分結果，圖1(c)表示另一標記者w2提供的數(shù)據(jù)劃分結果，圖1(d)表示將原始數(shù)據(jù)進行聚類得到的分類結果。

圖1中兩位標記者在為眾包數(shù)據(jù)提供標簽時均存在錯誤標簽，而此時有較為可靠的聚類結果，則可利用這一結果幫助確定標記者的置信度。

由于采用了聚類算法，因此聚類結果與眾包標記結果的相似性采用常見的聚類評價指標Rand Index系數(shù)表示，將其作為標記者的第一部分置信度：

(1)

式中：Tp表示在聚類結果和標記者提供的標簽中均屬于同一類的實例數(shù)；Tn表示在聚類結果和標記者提供的標簽中均不屬于同一類的實例數(shù)；Fp表示聚類結果屬于一類，而標記者提供的標簽不屬于一類的實例數(shù)；Fn表示聚類結果不屬于一類，而標記者提供的標簽屬于一類的實例數(shù)；n表示實例數(shù)。

1.2.2 基于標簽信息的置信度

在眾包數(shù)據(jù)中，某位標記者與其他標記者所提供的標簽信息越相似，則這位標記者提供的標簽越可信。因此，將標記者之間的相似性作為標記者置信度的一部分，用以計算完整的置信度。

用pab表示標記者a與標記者b所提供的標簽信息間的相似度，pa表示標記者a與其他標記者的平均相似度，a,b∈(1,m)。

(2)

(3)

根據(jù)上文分別得到基于數(shù)據(jù)分布特征和標簽信息的置信度v1和v2，v1,v2∈(0,1)，計算兩者的幾何平均值V，即標記者置信度，其中V∈(0,1)。

(4)

圖2所示為標記者置信度V隨v1、v2變化的趨勢圖。由圖可知，v1、v2均對V有整體的影響。

(a) 原始數(shù)據(jù)的分布(a) Original data distribution

(b) w1的數(shù)據(jù)劃分結果(b) Data partitioning results of w1

(c) w2的數(shù)據(jù)劃分結果(c) Data partitioning results of w2

(d) 數(shù)據(jù)聚類結果(d) Data clustering results圖1 數(shù)據(jù)標記Fig.1 Data labeling

若使用算數(shù)平均值，則當其中一個變量不變時，另一變量對其整體的影響有限，不能充分表現(xiàn)變量較小時對整體權重的影響。

圖2 置信度的變化情況Fig.2 Variation of confidence

根據(jù)得到的標記者置信度推斷得出實例的真實標簽：

(5)

式中，p(li)表示實例推斷標簽為li的可能性，i∈(1,k)。

雙重置信度推斷(double confidence inference，DC)算法的步驟如算法1所示。

算法1 雙重置信度推斷算法

本文算法在每個數(shù)據(jù)集上的每種標記數(shù)下的計算復雜度O(n)=n·p·l，其主要由算法1的第5步推斷實例的真實標簽過程產(chǎn)生。其中：n為數(shù)據(jù)集實例數(shù)；p表示標記數(shù)，即為該實例提供標簽的人數(shù)；l為數(shù)據(jù)集的類數(shù)。

2 實驗與分析

本節(jié)對表1所示的10個真實世界數(shù)據(jù)集進行實驗，并與4種經(jīng)典的方法MV、DS、GLAD、ZC算法在標簽推斷準確率和時間效率兩方面進行了比較。

表1 實驗數(shù)據(jù)集

2.1 實驗設計

使用的數(shù)據(jù)集均為UCI數(shù)據(jù)集，參照文獻[16]中所示方法模擬生成眾包數(shù)據(jù)。首先為每位標記者隨機生成標記準確率t，t∈(0.3,0.9)；再根據(jù)每位標記者的準確率對原數(shù)據(jù)集隨機抽樣，樣本數(shù)據(jù)按照準確率t被賦予正確標簽，其他數(shù)據(jù)均被隨機賦予錯誤標簽，由此生成標簽數(shù)據(jù)集。實驗為每個數(shù)據(jù)集生成了標記者數(shù)分別為1～10的標簽數(shù)據(jù)集，為保證實驗結果可信，每次的標簽生成過程重復5次。

考慮數(shù)據(jù)分布的多樣性，實驗中采用的是經(jīng)典的噪聲環(huán)境下基于密度的聚類(density-based spatial clustering of applications with noise，DBSCAN)算法。DBSCAN算法包含3個參數(shù)，分別是X、ε、mp。其中：X為數(shù)據(jù)集的特征；ε表示樣本間的最小距離，即若兩樣本間距離小于ε，則樣本互為鄰域；mp表示形成簇類所需的最小樣本個數(shù)，將mp設定為特征數(shù)的2倍。ε和mp的計算方法分別為：

ε=d(0.005l(d))

(6)

mp=2dx

(7)

其中，d表示排序后的數(shù)據(jù)特征的距離向量，ε為該向量千分之五處的值，l(·)表示計算向量長度的函數(shù)，dx表示數(shù)據(jù)集的特征數(shù)。

2.2 實驗結果分析

為驗證本文算法的有效性，從時間效率及標簽推測準確性兩方面考慮方法效率。時間效率為各個算法在每個數(shù)據(jù)集上的5次實驗的平均運行時間，標簽準確率如式(8)所示。

(8)

2.2.1 不同標簽數(shù)對準確率的影響

圖3所示為5種算法在10個數(shù)據(jù)集上實例被標記次數(shù)為2～10的準確率。由圖3可知，5種方法的實驗準確率均隨標簽數(shù)的增多而提高。標簽數(shù)為1時的實驗結果參考性不大，因此圖中未表示出來。在標簽數(shù)為2時，MV算法與GLAD算法的實驗效果均較差，DS算法的表現(xiàn)也差強人意。在大部分數(shù)據(jù)集上，當標簽數(shù)多于2時，各個算法的準確率均隨著標簽數(shù)的增多快速提升，當每個實例的標簽數(shù)多于7時，各個算法的準確率均趨于1，效果相差較小，且?guī)缀醪辉匐S著標簽數(shù)的增多而有所提高。

(a) Svmguide2

(b) Svmguide4

(c) Vehicle

(d) Phishing

(e) Steel Plates Faults

(f) Segment

(g) Satimage

(h) Letter

(i) Australian

(j) Breast_cancer 圖3 不同標記者數(shù)目在各數(shù)據(jù)集下的算法準確率Fig. 3 Accuracy of the algorithm for the number of different markers in each data set

在真實眾包數(shù)據(jù)中，每個樣本的標簽數(shù)均大于7的可能性較小，因此主要分析標簽數(shù)為4～7的實驗結果。顯而易見，在大部分數(shù)據(jù)集上，當標簽數(shù)為4～7時，DC算法的實驗效果略優(yōu)于其他4種算法，其他情況時與另外4種算法的實驗效果相近，而在實際的標注中，得到的標簽數(shù)據(jù)往往沒有很多，因此DC算法相較其他方法有一定優(yōu)勢。DS算法及ZC算法在二分類問題中的實驗效果比MV、GLAD、DC算法好，而在多分類問題中GLAD、DC算法的效果較其在二分類中的效果有明顯的提升。

圖4給出了各算法在標簽數(shù)分別為4～7時準確率的臨界差異(critical difference，CD)圖。CD圖是基于統(tǒng)計顯著性差異的算法對比模式，可以給出不同算法的排名。圖4中算法排名越小表示算法效果越好。在標簽數(shù)為4～7時，DC算法準確率均高于其他4種算法。圖中算法的平均排名基于10個數(shù)據(jù)集和10種標簽數(shù)量。

(a) 標簽數(shù)為4(a) Number of labels is 4

(b) 標簽數(shù)為5(b) Number of labels is 5

(c) 標簽數(shù)為6(c) Number of labels is 6

(d) 標簽數(shù)為7(d) Number of labels is 7圖4 臨界差異圖Fig. 4 Critical difference diagram

2.2.2 與其他算法的比較分析

表2所示為5種方法分別在標簽數(shù)為1～10時的實驗數(shù)據(jù)均值的比較。由表2所示可知，DC算法在8個數(shù)據(jù)集上的表現(xiàn)最優(yōu)，相比最差的實驗數(shù)據(jù)分別提高了1.9%、2.23%、1.52%、2.14%、1.62%、1.45%、3.86%、5.39%；相比其他4種算法平均提高了1.12%、1.52%、0.65%、1.11%、1.06%、0.72%、1.68%、2.26%。在Segment和Satimage數(shù)據(jù)集上的表現(xiàn)也僅次于最好的算法結果，且分別相差1.03%、0.79%。這是由于數(shù)據(jù)集的類別數(shù)增多，噪音分散嚴重。

在各個數(shù)據(jù)集中，由于標記者的準確率隨機給出，且絕大部分標記者的準確率高于0.5，因此MV算法的準確率隨著標簽數(shù)的增多而提高，而在真實數(shù)據(jù)集中，標記者的準確率并沒有隨機給出的準確率高，導致MV算法的準確率其實并沒有實驗所示的那么高。又因為標簽數(shù)據(jù)中的噪音是根據(jù)給定的標記者的準確率隨機給出，所以多分類噪音沒有二分類問題中的噪音結果集中，而是被分散到了所有可能的標簽上，這樣就導致MV算法在多分類問題中的準確率更高，其他4種算法也受此影響。

當標記者準確率較低時，GLAD算法相較其他算法在各個數(shù)據(jù)集中的實驗效果較優(yōu)，但該算法的迭代時間相較其他算法過長；DS算法使用的基本算法是EM算法，其實驗效果受初值影響較大，DC算法結果為運行效果最好的結果；ZC算法在各數(shù)據(jù)集上的表現(xiàn)相對MV、DS、GLAD算法是最好的。DC算法在大部分數(shù)據(jù)集上的實驗效果相較其他4種算法均為最優(yōu)的。

表2 各算法在各數(shù)據(jù)集中的平均準確率

圖5為5種算法在10個數(shù)據(jù)集上的平均運行時間，由于GLAD算法的運行時間相較其他4種算法長很多，因此圖中所示的GLAD算法的運行時間為真實運行時間的1%。5種算法的運行時間均隨數(shù)據(jù)集數(shù)目的增大而變長，其中：MV算法的運行時間最短；ZC算法與DS算法耗時相近；DC算法實驗過程中要運行聚類算法，因此耗時較DS、ZC、MV算法略長。

圖5 算法運行時間Fig.5 Running time of algorithms

3 結論

本文考慮了數(shù)據(jù)分布和標簽信息兩方面的置信度，首先根據(jù)DBSCAN聚類算法將樣本數(shù)據(jù)聚類，由此結果得到標記者置信度的第一部分，再由標記者相似性計算得到置信度的第二部分，最后根據(jù)標記者置信度推斷實例的真實標簽。實驗結果表明，DC算法在標簽數(shù)處于3～7的情況時，效果優(yōu)于其他算法。

由于DC算法使用了聚類方法，考慮到聚類結果的準確性可能對實驗結果有一定影響，因此未來工作將針對聚類算法對實驗結果的影響以及糾正聚類結果的準確性這兩部分展開，以提高標簽推斷算法的準確性。