賴(lài)德迪,羅智徽,馬應(yīng)龍

(華北電力大學(xué)控制與計(jì)算機(jī)工程學(xué)院,北京 102206)

0 引 言

分類(lèi)算法是機(jī)器學(xué)習(xí)中非常重要的研究課題。通過(guò)分類(lèi)算法可以使得機(jī)器對(duì)所分析的研究對(duì)象自動(dòng)劃分種類(lèi),從而達(dá)到識(shí)別對(duì)象、認(rèn)識(shí)對(duì)象特征的目的。在實(shí)際問(wèn)題中,一個(gè)對(duì)象所屬的類(lèi)別往往不是單一的,而可能是同時(shí)屬于多個(gè)類(lèi)別的[1-2]。例如,在一些針對(duì)復(fù)雜化、信息化的大型裝備的故障檢測(cè)任務(wù)中[3],一組設(shè)備的狀態(tài)監(jiān)測(cè)數(shù)據(jù)異常極有可能是因?yàn)橹苿?dòng)器、齒輪箱、扭矩傳感器、驅(qū)動(dòng)電機(jī)中的一個(gè)或多個(gè)部件故障引起的,因此該異常事件可以同時(shí)對(duì)應(yīng)一個(gè)或多個(gè)故障類(lèi)別。這種為每個(gè)對(duì)象準(zhǔn)確預(yù)測(cè)其所有可能類(lèi)別的分類(lèi)方法稱(chēng)為多標(biāo)簽分類(lèi)[4]。而傳統(tǒng)的分類(lèi)方法只是為每一個(gè)對(duì)象準(zhǔn)確預(yù)測(cè)一個(gè)類(lèi)別標(biāo)記。

多標(biāo)簽分類(lèi)的難點(diǎn)主要表現(xiàn)在以下方面。首先,每個(gè)對(duì)象需要預(yù)測(cè)的標(biāo)簽數(shù)量通常是不確定的,有的對(duì)象可能只有一個(gè)分類(lèi)標(biāo)簽,而有的對(duì)象的標(biāo)簽數(shù)量卻可能很多[5]。雖然一些多標(biāo)簽分類(lèi)算法當(dāng)前已經(jīng)被應(yīng)用于圖像多目標(biāo)檢測(cè)識(shí)別等領(lǐng)域,但現(xiàn)有的多標(biāo)簽分類(lèi)方法在總體分類(lèi)準(zhǔn)確率等方面還有待提高,特別是在標(biāo)簽數(shù)量很多的情況下進(jìn)行準(zhǔn)確的多標(biāo)簽預(yù)測(cè)是一個(gè)具有挑戰(zhàn)性的問(wèn)題。其次,高準(zhǔn)確率的多標(biāo)簽分類(lèi)需要深入挖掘標(biāo)簽之間的潛在關(guān)聯(lián)或依賴(lài)關(guān)系。因?yàn)樵谶M(jìn)行多標(biāo)簽分類(lèi)時(shí),大多數(shù)的標(biāo)簽之間通常存在著正向或負(fù)向的相關(guān)性。例如在多標(biāo)簽圖像目標(biāo)識(shí)別的任務(wù)中[6],如果一張圖像中包含了戰(zhàn)斗機(jī)、轟炸機(jī)、預(yù)警機(jī)等多個(gè)不同類(lèi)型的目標(biāo)對(duì)象,一旦識(shí)別出圖像中的這些目標(biāo)對(duì)象,則該圖像會(huì)被同時(shí)標(biāo)記為“戰(zhàn)斗機(jī)”“轟炸機(jī)”“預(yù)警機(jī)”等類(lèi)型標(biāo)簽。因此,如何分析和挖掘多個(gè)標(biāo)簽之間的潛在關(guān)聯(lián)或依賴(lài)關(guān)系是多標(biāo)簽分類(lèi)的另一大難點(diǎn)。

現(xiàn)有的多標(biāo)簽分類(lèi)方法大致基于兩種策略,分別是算法適應(yīng)策略[7]和問(wèn)題轉(zhuǎn)換策略[8]。算法適應(yīng)策略將多標(biāo)簽分類(lèi)問(wèn)題轉(zhuǎn)換成聚類(lèi)[9]等其他形式的問(wèn)題進(jìn)行處理。例如基于K最近鄰思想的多標(biāo)簽分類(lèi)方法[10],其對(duì)于每個(gè)測(cè)試樣本,在訓(xùn)練集中找到其K個(gè)近鄰,然后基于鄰居樣本的統(tǒng)計(jì)信息,采用最大后驗(yàn)概率決定測(cè)試樣本的標(biāo)簽集合。另一種基于標(biāo)簽排序校準(zhǔn)的多標(biāo)簽分類(lèi)方法[11]則依據(jù)測(cè)試樣本在每個(gè)標(biāo)簽分類(lèi)器上得到的值為1(或0)進(jìn)行加分(或減分)。最后按照分值大小進(jìn)行排序,取分值靠前的多個(gè)標(biāo)簽作為當(dāng)前測(cè)試樣本的標(biāo)簽集合。但由于該類(lèi)算法需要對(duì)每?jī)蓚€(gè)標(biāo)簽之間訓(xùn)練一個(gè)分類(lèi)器,使得算法時(shí)間復(fù)雜度較高,在標(biāo)簽數(shù)目較多的任務(wù)上難以展開(kāi)。近來(lái)也有學(xué)者在信息論的基礎(chǔ)上對(duì)于多標(biāo)簽分類(lèi)算法模型進(jìn)行改進(jìn)[12-13],該類(lèi)改進(jìn)算法借助于嵌入特征選擇的方法對(duì)樣本特征進(jìn)行篩選。通過(guò)去除樣本中冗余的特征,保留有效特征的方式,來(lái)減少無(wú)關(guān)特征對(duì)分類(lèi)結(jié)果的影響,從而達(dá)到優(yōu)化的效果。然而去除特征或多或少會(huì)減少了原樣本的實(shí)例信息,并影響分類(lèi)器訓(xùn)練的收斂速度和最終的分類(lèi)性能。

問(wèn)題轉(zhuǎn)換策略則主要將多標(biāo)簽分類(lèi)問(wèn)題拆解成一個(gè)多分類(lèi)問(wèn)題或多個(gè)二分類(lèi)問(wèn)題,從而簡(jiǎn)化多標(biāo)簽分類(lèi)任務(wù)。其代表性的方法,如標(biāo)簽冪集算法[14-15],其將原問(wèn)題轉(zhuǎn)換為選擇標(biāo)簽集合中一個(gè)子集,并以此來(lái)作為測(cè)試樣本的標(biāo)簽預(yù)測(cè)集。其充分考慮了給定標(biāo)簽集合可能的組合情況,但由于標(biāo)簽集合所包含的子集數(shù)量往往十分龐大,因此該算法在標(biāo)簽數(shù)目較多的情況下,時(shí)間復(fù)雜度極高。上述算法無(wú)疑都顯示了多標(biāo)簽分類(lèi)的潛力,部分算法也已經(jīng)被應(yīng)用于文本分類(lèi)[16-18]、媒體內(nèi)容標(biāo)簽[19]、在線處理[20]、蛋白質(zhì)和基因組預(yù)測(cè)[21-23]等應(yīng)用領(lǐng)域。然而,基于算法自適應(yīng)的多標(biāo)簽分類(lèi)方法往往需要建立更復(fù)雜的學(xué)習(xí)模型來(lái)進(jìn)行模型訓(xùn)練和實(shí)例標(biāo)簽的特征表示,并且往往具有較高的復(fù)雜度,而上述算法都難以在這樣的任務(wù)中有較好的表現(xiàn)。

分類(lèi)器鏈(classifier chains,CC)模型[24]作為一種最典型的基于問(wèn)題轉(zhuǎn)換策略的多標(biāo)簽分類(lèi)算法,因其簡(jiǎn)單易用而得到廣泛地應(yīng)用和發(fā)展[25-26]。CC模型基于二元相關(guān)性(binary relevance,BR)[27]原理,對(duì)每個(gè)標(biāo)簽都訓(xùn)練一個(gè)二元分類(lèi)器,所有樣本在每個(gè)分類(lèi)器上都進(jìn)行二元分類(lèi),并通過(guò)鏈?zhǔn)皆鲩L(zhǎng)的方式訓(xùn)練出多標(biāo)簽分類(lèi)模型。然而在CC模型中,二元CC序列是隨機(jī)生成的[28-30],沒(méi)有充分考慮二元分類(lèi)器對(duì)應(yīng)標(biāo)簽之間存在的隱含依賴(lài)關(guān)系,而這無(wú)疑會(huì)導(dǎo)致分類(lèi)錯(cuò)誤傳播,并直接影響多標(biāo)簽分類(lèi)性能。因此采取合理的策略?xún)?yōu)化標(biāo)簽的排序就顯得尤其重要[31]。近年來(lái)研究人員已提出很多CC算法優(yōu)化策略。文獻(xiàn)[32]提出了一種多樹(shù)增寬CC方法,該算法通過(guò)建模標(biāo)簽與屬性之間合理的條件依賴(lài)關(guān)系來(lái)近似底層依賴(lài)關(guān)系,但該方法計(jì)算復(fù)雜度極高,其預(yù)測(cè)計(jì)算代價(jià)隨標(biāo)簽數(shù)量呈指數(shù)級(jí)增長(zhǎng)。文獻(xiàn)[33]提出了基于神經(jīng)網(wǎng)絡(luò)的CC模型算法,雖能明顯提升多標(biāo)簽分類(lèi)的性能,但隨著實(shí)例和標(biāo)簽的增加,用于神經(jīng)網(wǎng)絡(luò)模型訓(xùn)練的計(jì)算復(fù)雜度將會(huì)急劇增加,因此類(lèi)似方法不適用于一些需要快速地進(jìn)行分類(lèi)預(yù)測(cè)的應(yīng)用環(huán)境,如邊緣計(jì)算環(huán)境等。

本文針對(duì)原始CC標(biāo)簽序列隨機(jī)生成導(dǎo)致多標(biāo)簽分類(lèi)性能不高的問(wèn)題,分別提出貪心CC(greedy CC,GCC)方法和基于n-gram的CC(n-gram based CC,NCC)方法對(duì)標(biāo)簽序列中的標(biāo)簽序列進(jìn)行優(yōu)化,以提升模型的多標(biāo)簽分類(lèi)性能。另外,通過(guò)與當(dāng)前流行的基于CC模型的多標(biāo)簽分類(lèi)模型進(jìn)行實(shí)驗(yàn)對(duì)比,以驗(yàn)證本文所提方法的有效性和高效性。

1 基本原理

1.1 多標(biāo)簽分類(lèi)

令X?Rk為k維實(shí)例輸入特征空間,Y={l1,l2,…,lq}標(biāo)簽的集合。由n個(gè)數(shù)據(jù)組成的訓(xùn)練樣本集D,表示為D={(xi,yi)}(i=1,2,…,n)。每個(gè)實(shí)例(xi,yi)∈D。xi=(xi,1,xi,2,…,xi,k)∈X是一個(gè)k維特征向量,xi,j代表特征向量xi的第j個(gè)元素。本文用yi=(yi,1,yi,2,…,yi,q)∈{0,1}q表示一個(gè)q維的標(biāo)簽向量,其中yi,j=1表示標(biāo)號(hào)lj與xi相關(guān),而yi,j=0則表示與xi無(wú)關(guān)。設(shè)Yi?Y是與xi相關(guān)的標(biāo)記組成的集合,則有Yi={lj|yi,j=1,1≤j≤q}。

多標(biāo)簽分類(lèi)的任務(wù)是找到一個(gè)能將yi最優(yōu)地分配給每個(gè)實(shí)例xi的分類(lèi)器f:X→{0,1}q。在BR[27]的背景下,一個(gè)多標(biāo)簽分類(lèi)器f是由q個(gè)二值分類(lèi)器f1,f2,…,fq組成。每個(gè)二值分類(lèi)器fj:X→{0,1}都可以從派生訓(xùn)練集Dj={(xi,yi,j)}(j=1,2,…,n)中根據(jù)其與lj的相關(guān)性訓(xùn)練得出。其中Dj是通過(guò)將每個(gè)實(shí)例(xi,yi)∈D轉(zhuǎn)化為對(duì)應(yīng)于標(biāo)簽lj的二進(jìn)制實(shí)例(xi,yi,j)而得到的。對(duì)于標(biāo)簽未知的實(shí)例x′,通過(guò)查詢(xún)每個(gè)分類(lèi)器fj,可以預(yù)測(cè)其關(guān)聯(lián)的標(biāo)簽集Y′={lj|fj(x′)=1,1≤j≤q}。

1.2 CC模型

CC是一種著名的基于BR模型的多標(biāo)簽分類(lèi)方法,克服了BR模型在訓(xùn)練數(shù)據(jù)中忽略標(biāo)簽間相關(guān)關(guān)系的局限性,從而獲得了較好的預(yù)測(cè)性能。該模型通過(guò)將前面分類(lèi)器的結(jié)果添加到當(dāng)前分類(lèi)器來(lái)實(shí)現(xiàn)分類(lèi)器的串行連接。具體來(lái)說(shuō),CC模型首先隨機(jī)生成一個(gè)標(biāo)簽的序列,記為Y={l1,l2,…,lq},然后CC模型按照CC的序列訓(xùn)練一組二元分類(lèi)器f1,f2,…,fq。

在訓(xùn)練階段,每個(gè)二元分類(lèi)器fj:X→{0,1}都是基于當(dāng)前標(biāo)簽lj同前j-1個(gè)標(biāo)簽l1,l2,…,lj-1的關(guān)聯(lián)性,從特定的派生訓(xùn)練數(shù)據(jù)集Dj={(xi,yi,1,…,yi,j-1,yi,j)}(i=1,2,…,n)中訓(xùn)練得到的。該訓(xùn)練數(shù)據(jù)集Dj中的每一個(gè)實(shí)例都是由原始數(shù)據(jù)集D中的相對(duì)應(yīng)的實(shí)例(xi,yi)派生得到的。

在測(cè)試階段,該方法以貪心方式來(lái)預(yù)測(cè)未知的實(shí)例x*的值fj(x*)。通過(guò)查詢(xún)每個(gè)分類(lèi)器fj(1≤j≤q),來(lái)預(yù)測(cè)實(shí)例x*的關(guān)聯(lián)標(biāo)簽集Y*,其中Y*={lj|fj(x*)=1,1≤j≤q}。

CC算法由于初始隨機(jī)生成的標(biāo)簽鏈的順序無(wú)法有效避免錯(cuò)誤傳播的風(fēng)險(xiǎn),故對(duì)CC的順序仍然非常敏感。因此,為CC選擇一個(gè)最優(yōu)的序列以保證多標(biāo)簽分類(lèi)的高精度成為一個(gè)關(guān)鍵問(wèn)題。

2 CC優(yōu)化方法框架

2.1 CC優(yōu)化方法流程

本文提出的CC優(yōu)化方法總體上可分為4個(gè)主要階段。第1階段,根據(jù)訓(xùn)練樣本集合D={(xi,yi)}(i=1,2,…,n)來(lái)構(gòu)建共現(xiàn)率矩陣M。第2階段,根據(jù)共現(xiàn)率矩陣M來(lái)確定標(biāo)簽序列的首部(優(yōu)化標(biāo)簽序列中的前兩個(gè)標(biāo)簽)。在第3階段,本文提出兩種方法生成完整的標(biāo)簽優(yōu)化序列方法,即GCC)和NCC。這兩種方法依據(jù)不同的標(biāo)簽關(guān)聯(lián)發(fā)掘方式,得到不同的標(biāo)簽優(yōu)化序列。在第4階段,通過(guò)前面階段獲得的優(yōu)化標(biāo)簽序列進(jìn)行基于CC模型的多標(biāo)簽分類(lèi)。本文CC優(yōu)化方法的總體框架如圖1所示。

圖1 CC優(yōu)化方法總體框架Fig.1 Overall framework of CC optimization method

2.2 共現(xiàn)率矩陣創(chuàng)建

共現(xiàn)分析是通過(guò)計(jì)算兩個(gè)元素一起出現(xiàn)的頻率[34-35]來(lái)定量度量?jī)蓚€(gè)元素之間潛在關(guān)系的關(guān)聯(lián)度的一種方法,目前已應(yīng)用于單詞嵌入[36]等技術(shù)中。共現(xiàn)率矩陣M的創(chuàng)建過(guò)程大致如下:

令D={(xi,yi)}(i=1,2,…,n)代表數(shù)據(jù)集,q代表標(biāo)簽的數(shù)目。令Yi?Y代表與xi相關(guān)的標(biāo)簽集合,則對(duì)yi=(yi,1,yi,2,…,yi,q)有Yi={lj|yi,j=1,1≤j≤q}。同時(shí)采用Si={(xj,yj)|(xj,yj)∈D,yj,i=1}來(lái)表示與標(biāo)簽相關(guān)的實(shí)例。相應(yīng)地用(Si={(xj,yj)|(xj,yj)∈D,yj,i=0}表示與li無(wú)關(guān)的實(shí)例集。因此,Si∩Sj={(xk,yk)|(xk,yk)∈D,yk,i=1,yk,j=1}。

在本文中,共現(xiàn)率矩陣是一個(gè)q×q大小的矩陣,對(duì)于共現(xiàn)率矩陣M中的i行j列(i≠j)的元素共現(xiàn)率Mij定義如下：

(1)

式中：|S|為集合S中元素的總數(shù)；n為訓(xùn)練集D中樣本的總數(shù)。同時(shí)注意到,共現(xiàn)率矩陣必然是對(duì)稱(chēng)矩陣,因此只需要計(jì)算矩陣的一半元素即可?；谑?1),共現(xiàn)率矩陣的一個(gè)例子如表1所示,其涉及q=5個(gè)標(biāo)簽,是一個(gè)5×5矩陣。另外,共現(xiàn)率矩陣中只需要計(jì)算不同標(biāo)簽之間的共現(xiàn)率,而無(wú)需計(jì)算相同標(biāo)簽之間共現(xiàn)率。

表1 共現(xiàn)率矩陣的例子Table 1 Example of co-occurrence rate matrix

計(jì)算共現(xiàn)率矩陣中元素Mi,j在最壞情況下的計(jì)算復(fù)雜度為O(n)。由于計(jì)算同一標(biāo)簽的共現(xiàn)性毫無(wú)意義,因此構(gòu)建共現(xiàn)率矩陣的總復(fù)雜度應(yīng)為O(n(q-1)2)。根據(jù)樣例的標(biāo)簽集合建立對(duì)應(yīng)的共現(xiàn)矩陣,可以將標(biāo)簽之間的潛在關(guān)聯(lián)關(guān)系用于后續(xù)的標(biāo)簽序列優(yōu)化。

2.3 標(biāo)簽序列首部的選定

在分析共現(xiàn)率矩陣M的基礎(chǔ)上,通過(guò)遍歷M中的每一行,找到值最大的單元格來(lái)確定前兩個(gè)標(biāo)簽的在CC上的最優(yōu)選擇。基于此,本文通過(guò)對(duì)每對(duì)標(biāo)簽(li,lj)對(duì)應(yīng)的Mi,j進(jìn)行兩兩比較,并選擇Mi值最大的兩個(gè)標(biāo)簽作為首部標(biāo)簽,從而確定最優(yōu)的首部選擇,如下所示:

(2)

式中:H表示共現(xiàn)率矩陣中具有最大共現(xiàn)率Mi,j的所有數(shù)對(duì)(i,j)的集合,每個(gè)數(shù)對(duì)(i,j)對(duì)應(yīng)的標(biāo)簽對(duì)為(li,lj)。

確定首部標(biāo)簽在鏈中的順序至關(guān)重要,其基本標(biāo)準(zhǔn)是將共現(xiàn)率較高的標(biāo)簽排序到盡可能早的位置,這樣可以有效地利用前面分類(lèi)器的結(jié)果進(jìn)行基于當(dāng)前分類(lèi)器的分類(lèi)。本文通過(guò)兩個(gè)步驟確定優(yōu)化標(biāo)簽序列的前兩個(gè)元素。

步驟 1若H只包含一個(gè)標(biāo)簽對(duì),設(shè)H={(i,j)},則需要判斷標(biāo)簽對(duì)(li,lj)是否滿足:

(3)

式(3)用于計(jì)算除(li,lj)以外分別與li和lj共現(xiàn)率最大的標(biāo)簽對(duì)(li,ls)和(lj,lt)。若式(3)成立,那么li和lj分別是標(biāo)簽序列的第1個(gè)和第2個(gè)標(biāo)簽,否則反之。

步驟 2若H包含兩個(gè)及以上標(biāo)簽對(duì),不失一般性地假設(shè)H={(i,j),(s,t)}包含兩個(gè)標(biāo)簽對(duì)(3個(gè)以上的標(biāo)簽對(duì)可以通過(guò)任意兩個(gè)標(biāo)簽對(duì)之間的兩兩比較最終確定兩個(gè)標(biāo)簽對(duì)),則需要分別計(jì)算這兩對(duì)標(biāo)簽和其他標(biāo)簽之間的最大共現(xiàn)率是否滿足：

(4)

來(lái)確定,最終選取序列首部,即優(yōu)化序列的前兩個(gè)標(biāo)簽。若式(4)成立,則確定將使用(li,lj)標(biāo)簽對(duì)作為標(biāo)簽首部,否則使用(ls,lt)標(biāo)簽對(duì)作為標(biāo)簽首部。一旦確定了一個(gè)標(biāo)簽對(duì),則可進(jìn)一步通過(guò)步驟1判斷該標(biāo)簽對(duì)中哪個(gè)標(biāo)簽是標(biāo)簽序列的第1個(gè)和第2個(gè)。

由于序列首部(優(yōu)化序列的前兩個(gè)標(biāo)簽)已經(jīng)選定了,因此只需不斷選取后續(xù)的標(biāo)簽序列即可。本文分別提出GCC算法和NCC算法來(lái)確定優(yōu)化標(biāo)簽序列中的其他標(biāo)簽。

3 GCC方法

本文提出GCC方法,其具體流程如算法1所示。GCC算法需要遍歷共現(xiàn)率矩陣M所有元素。在算法1中,第1～4行是將(s,t)按前兩個(gè)標(biāo)簽的正確順序排列,并進(jìn)行一些初始化。在第5～10行,通過(guò)貪心策略來(lái)最大化標(biāo)簽序列尾部L[c]的共現(xiàn)率ML[c],r,從而選取標(biāo)簽序列的后繼標(biāo)簽。

通過(guò)執(zhí)行算法1,將對(duì)所有的標(biāo)簽從原始的標(biāo)簽集合Y中重新排序,使之符合其編號(hào)。鏈中標(biāo)簽的最優(yōu)順序?yàn)閘L[0]→lL[1]→ … →lL[q-1],GCC算法的復(fù)雜度包括共現(xiàn)率矩陣的構(gòu)造,算法復(fù)雜度在最壞情況下僅為O(nq),其中n和q為樣本總數(shù)和標(biāo)簽總數(shù)。

4 NCC方法

本文提出的NCC方法借助于n-gram的語(yǔ)言模型實(shí)現(xiàn)。n-gram是一種用于詞序列的概率生成的模型[37-38],考慮了句子中詞的前后聯(lián)系,從條件概率的角度給出一個(gè)句子的生成概率[39]。假定當(dāng)前需要生成的詞序列共有m個(gè)詞w1,w2,…,wm,且假設(shè)當(dāng)前詞僅與其前面n-1個(gè)詞有關(guān)(n

P(w1,w2,…,wm)=
P(w1)P(w2|w1)…P(wm|wm-n+1,…,wm -1)

(5)

式中:n的取值不同對(duì)于整個(gè)序列的影響程度是不一樣的。選取過(guò)大的n會(huì)使得時(shí)間復(fù)雜度急劇變高,從而使得原本任務(wù)變得很困難?？紤]到n-gram在詞序列的特征提取上面有比較好的表現(xiàn),本文采用n-gram算法思想,將標(biāo)簽序列看成是若干個(gè)詞組合而成的序列,來(lái)對(duì)標(biāo)簽序列進(jìn)行優(yōu)化。

設(shè)L={l1,l2,…,lq}是一個(gè)由q個(gè)標(biāo)簽組成的CC序列,進(jìn)一步基于式(5),采用n-gram模型并根據(jù)

P(L)=P(l1,l2,…,lq)=
P(l1)P(l2|l1)…P(lq|lq-1,lq-2,lq-3)

(6)

將L標(biāo)簽序列發(fā)生的概率轉(zhuǎn)換為條件概率的乘積。

為了實(shí)現(xiàn)以序列增長(zhǎng)的方式產(chǎn)生CC優(yōu)化序列,標(biāo)簽li出現(xiàn)在li-1和li-2后面的條件概率為P(li|li-1,li-2),定義如下：

(7)

式中：Si-2、Si-1和Si分別表示與標(biāo)簽li-2、li-1和li相關(guān)的實(shí)例集,每個(gè)Si={(xj,yj)|(xj,yj)∈D,yj,j=1}。如果能使得所生成的標(biāo)簽序列的概率最大化,實(shí)際上就選擇出了一條優(yōu)化的分類(lèi)器標(biāo)簽序列。因此,NCC策略生成多標(biāo)簽序列的任務(wù)可以轉(zhuǎn)換為:設(shè)Li={l1,l2,…,li}表示完整序列L中前i個(gè)標(biāo)簽組成的子序列,在以迭代方式添加后續(xù)標(biāo)簽到當(dāng)前序列的過(guò)程中,需要確保標(biāo)簽添加后的新序列的概率P(Li)值最大。也就是說(shuō),假設(shè)已經(jīng)確定順序的前i-1個(gè)標(biāo)簽的序列P(Li-1)值最大。當(dāng)后面添加可能的標(biāo)簽li的時(shí)候,依然要選擇使得概率P(Li)=P(Li-1)P(li|li-1,li-2)值最大的那個(gè)標(biāo)簽。

(8)

從Y′的序列中選擇某一個(gè)標(biāo)簽li添加到序列Li-1的末尾作為其第i個(gè)標(biāo)簽。這樣不斷地選擇剩余標(biāo)簽,最終可以生成包含所有標(biāo)簽的優(yōu)化的CC的標(biāo)簽序列。

NCC方法的具體流程如算法2所示。因?yàn)闃?biāo)簽首部已經(jīng)確定,所以只需要確定標(biāo)簽序列中的剩余標(biāo)簽順序。在算法2中,第1～4行是按照前兩個(gè)標(biāo)簽的順序放置(s,t),并進(jìn)行一些初始化。在第5～18行,通過(guò)使后續(xù)標(biāo)簽的條件概率最大來(lái)選擇完整的優(yōu)化標(biāo)簽序列。在第8～15行中,選擇概率最大的P(lc|lc-2,lc-1)的標(biāo)簽作為之前已經(jīng)確定的標(biāo)簽序列的后續(xù)標(biāo)簽。算法2在最壞情況下的計(jì)算復(fù)雜度為O(|D|×|Y|2)。在現(xiàn)實(shí)世界中,標(biāo)簽的數(shù)量|Y|遠(yuǎn)遠(yuǎn)小于實(shí)例的數(shù)量|D|。因此,算法2對(duì)于訓(xùn)練的實(shí)例的數(shù)目幾乎具有線性一致性。

算法2 NCC算法輸入 數(shù)據(jù)集D={(xi,yi)},i=1,2,…,n,序列首部(s,t)∈H輸出 CC序列L[q]1.L[0]←s;2.L[1]←t;3.Y←YlL[0],lL[1]};4.c←2; ∥一種記錄標(biāo)簽數(shù)目的索引5.whileY≠?do ∥選擇條件概率最大的標(biāo)簽6. B←{(xk,yk)(D|yk,L[c-1]=1,yk,L[c-2]=1};7. max←0;8. foreachlj∈Ydo9. U←{(xk,yk)(P|yk,j=1};10. p←|U|/(|B|+1)11. ifp>maxthen12. max←p;13. L[c]←j;14. endif15. endfor16. Y←Y{lL[c]};17. c←c+1;18.endwhile19.returnL[];End

5 實(shí)驗(yàn)分析評(píng)估

實(shí)驗(yàn)主要目的是評(píng)估本文提出的GCC和NCC兩種方法的效能。

5.1 實(shí)驗(yàn)評(píng)估基線算法

與 CC模型相關(guān)的用于多標(biāo)簽分類(lèi)的典型算法包括BR算法[27]、初始CC[24]以及用于多標(biāo)記學(xué)習(xí)的局部順序CC(locally ordinal CC,LOCC)算法[40]、標(biāo)簽冪集的改進(jìn)算法(pairwise random k-labelsets,pwRakel)[15]。本文將這些算法作為基線算法用于多標(biāo)簽分類(lèi)性能比較。

5.2 數(shù)據(jù)集與實(shí)驗(yàn)設(shè)置

本文從MULAN網(wǎng)站和MEKA網(wǎng)站收集了yeast,enron,emotions[41],Slashdot-F,CAL500等5個(gè)數(shù)據(jù)集用于實(shí)驗(yàn)評(píng)估。其領(lǐng)域涵蓋文本、圖片、生物等不同類(lèi)型數(shù)據(jù)。數(shù)據(jù)集的信息細(xì)節(jié)如表2所示。

表2 數(shù)據(jù)集描述Table 2 Description of datasets

所有實(shí)驗(yàn)評(píng)估均采用python語(yǔ)言實(shí)現(xiàn),借助sklearn庫(kù)進(jìn)行相應(yīng)的實(shí)驗(yàn)。在對(duì)于基分類(lèi)器的選擇上,本文采用支持向量機(jī)作為基分類(lèi)器,核函數(shù)選擇高斯核函數(shù),懲罰參數(shù)C=100,所有算法的基分類(lèi)器采用相同參數(shù),以避免在基分類(lèi)器上存在差異從而影響序列優(yōu)化本身所帶來(lái)的效果。

5.3 評(píng)價(jià)指標(biāo)

在評(píng)價(jià)指標(biāo)上,傳統(tǒng)分類(lèi)任務(wù)中所使用的分類(lèi)準(zhǔn)確率計(jì)算并不能很好地反映多標(biāo)簽分類(lèi)算法的性能,因此本文選擇采用在文獻(xiàn)[42]中提到的針對(duì)多標(biāo)簽分類(lèi)的準(zhǔn)確率Accuracy和F1測(cè)量作為性能評(píng)價(jià)指標(biāo)。

(1)準(zhǔn)確率指標(biāo)(Accuracy)

抽取2016年1月—2017年1月該院臨床檢驗(yàn)520例患者作為研究對(duì)象,男性患者280例,女性患者240例,年齡18~76歲,平均年齡(50.4±1.8)歲,所有患者共進(jìn)行臨床檢驗(yàn)862次,其中,血液分析檢驗(yàn)262次,生化檢驗(yàn)150次,尿沉渣檢驗(yàn)300次,大便檢驗(yàn)150次。

(9)

式中:|D|為樣本個(gè)數(shù)；Yi為樣本xi的真實(shí)標(biāo)簽集合；Pi為樣本xi的預(yù)測(cè)結(jié)果集合；Yi∩Pi表示樣本xi預(yù)測(cè)正確的標(biāo)簽個(gè)數(shù)；Yi∪Pi表示樣本xi總計(jì)出現(xiàn)的標(biāo)簽次數(shù)。

(2)F-score測(cè)量指標(biāo)(F1)

(10)

(11)

(12)

(13)

(6)歸一化平均時(shí)間(Time*)

(14)

(7)歸一化準(zhǔn)確率(Accuracy*)

(15)

5.4 算法比較與評(píng)估分析

5.4.1 NCC算法的n值實(shí)驗(yàn)與驗(yàn)證

NCC算法采用基于n-gram語(yǔ)言模型的策略進(jìn)行多標(biāo)簽分類(lèi),而n值的選擇對(duì)于NCC算法分類(lèi)性能有重要影響。如果n值選擇過(guò)小,分類(lèi)準(zhǔn)確率可能會(huì)受到影響。但如果n值選擇過(guò)大則會(huì)急劇地增加NCC算法的計(jì)算復(fù)雜度。

本文為經(jīng)驗(yàn)驗(yàn)證參數(shù)n對(duì)于NCC算法的影響大小,在部分指標(biāo)數(shù)值相近的數(shù)據(jù)集上選取了不同的n值進(jìn)行實(shí)驗(yàn),計(jì)算并比較了不同n值下的NCC算法的準(zhǔn)確率和F1測(cè)量值。試驗(yàn)結(jié)果如圖2和圖3所示。

圖2 n值在不同數(shù)據(jù)集上的Accuracy比較Fig.2 Accuracy comparison over different datasets with respect to n value

圖3 n值在不同數(shù)據(jù)集上的F1比較Fig.3 F1 comparison over different datasets with respect to n value

從圖2中可以看到,對(duì)于Accuracy指標(biāo),在emotions,yeast,Slashdot-F等數(shù)據(jù)集下,當(dāng)n<4時(shí),NCC算法分類(lèi)準(zhǔn)確率表現(xiàn)不穩(wěn)定；當(dāng)n≥4時(shí),隨著n值的增大,NCC算法分類(lèi)效能基本穩(wěn)定了。從圖3中針對(duì)不同的數(shù)據(jù)集分析對(duì)應(yīng)的F1指標(biāo)值,也可以得出類(lèi)似的結(jié)論。

因此，綜合不同的數(shù)據(jù)集以及不同情況下參數(shù)n的表現(xiàn)考慮,在默認(rèn)情況下本文選擇n=4最好,這樣既可以保證NCC算法分類(lèi)性能處于基本穩(wěn)定的狀態(tài),同時(shí)也可以使得n-gram概率計(jì)算的復(fù)雜度不會(huì)過(guò)高。從另一方面來(lái)看,該實(shí)驗(yàn)也從側(cè)面驗(yàn)證了本文采用n-gram模型來(lái)挖掘標(biāo)簽之間潛在關(guān)聯(lián)關(guān)系的有效性與正確性。

5.4.2 算法指標(biāo)性能對(duì)比分析

在實(shí)驗(yàn)結(jié)果的驗(yàn)證方面,本文采用五折交叉驗(yàn)證的方式，分類(lèi)的指標(biāo)結(jié)果如表3～表5所示,其中加粗標(biāo)示的為對(duì)應(yīng)指標(biāo)最優(yōu)的結(jié)果,用下劃線標(biāo)示的為對(duì)應(yīng)指標(biāo)次優(yōu)的結(jié)果。

表3 不同算法關(guān)于Accuracy的性能比較Table 3 Accuracy comparison of different algorithms

表4 不同算法關(guān)于F1的性能比較Table 4 F1 measure comparison of different algorithms

表5 不同算法和比較Table comparison of different algorithms

如表3所示,在Accuracy指標(biāo)上可以觀察到NCC算法幾乎優(yōu)于其他所有算法。同時(shí)其在yeast、Slashdot-F和emotions等3個(gè)數(shù)據(jù)集上表現(xiàn)優(yōu)越,在yeast數(shù)據(jù)集上比原CC算法高出2個(gè)百分點(diǎn),而在Slashdot-F數(shù)據(jù)集上則比原CC算法高了3個(gè)百分點(diǎn)。在個(gè)別數(shù)據(jù)集如enron和CAL500上,PwRakel和GCC算法性能則相對(duì)較優(yōu)。

從表4可以觀察到,從F1指標(biāo)進(jìn)行衡量,GCC算法和NCC算法的性能在所有數(shù)據(jù)集上都優(yōu)于其余算法,同時(shí)在不同數(shù)據(jù)集上分別占據(jù)了算法效果最優(yōu)和次優(yōu)的位置。

本文提出的NCC和GCC兩種算法都取得明顯性能提升的原因,歸根結(jié)底是在于其在生成優(yōu)化序列時(shí),都考慮了不同長(zhǎng)度的潛在標(biāo)簽關(guān)聯(lián)關(guān)系對(duì)整個(gè)序列造成的影響。GCC算法每次考慮前一個(gè)標(biāo)簽同后一個(gè)標(biāo)簽存在的最大共現(xiàn)關(guān)聯(lián)關(guān)系,從而保證了優(yōu)化的標(biāo)簽序列能體現(xiàn)最大的共現(xiàn)率。NCC算法則更進(jìn)一步考慮到了前n-1個(gè)標(biāo)簽同當(dāng)前尾部標(biāo)簽序列的關(guān)系,并采用n-gram來(lái)發(fā)掘標(biāo)簽前后間的依賴(lài)關(guān)系。因此,這兩種算法都取得了較好的效果。

5.4.3 算法指標(biāo)綜合效能對(duì)比分析

本文評(píng)估不同算法在不同數(shù)據(jù)集上執(zhí)行時(shí)間損耗。利用式(13)求出平均時(shí)間,各種算法執(zhí)行時(shí)間損耗如圖4所示,其中Time_avg為算法在所有數(shù)據(jù)集上的平均執(zhí)行時(shí)間。

圖4 不同算法的時(shí)間損耗比較Fig.4 Comparison of time loss for different algorithms

采用歸一化式(14)和式(15),對(duì)圖4的時(shí)間損耗和表3的準(zhǔn)確率求取歸一化的平均值,利用所有算法的歸一化準(zhǔn)確率和時(shí)間損耗繪制出圖5,進(jìn)一步比較各種算法的綜合效能。從圖5可以觀察到,CC算法的耗時(shí)最短,但效果并不理想。同時(shí)，不難發(fā)現(xiàn)LOCC算法相比原算法時(shí)間損耗并不大,但是算法性能提升較少。同樣地,PwRakel算法時(shí)間損耗較大,準(zhǔn)確率的提升卻不明顯。

圖5 不同算法的綜合效能比較Fig.5 Comprehensive effectiveness comparison of different algorithms

反觀GCC和NCC算法,兩者的時(shí)間損耗與原CC算法相比雖略有提升,但小于LOCC和PwRakel等算法。但與此同時(shí),NCC算法和GCC算法效果卻提升顯著。這足以體現(xiàn)GCC和NCC算法具有優(yōu)良的綜合效能。而這歸功于本文在CC算法基礎(chǔ)上,既考慮了標(biāo)簽間潛在的關(guān)聯(lián)關(guān)系,又采用了時(shí)間復(fù)雜度相對(duì)低的策略來(lái)進(jìn)行算法的優(yōu)化。

6 總 結(jié)

本文對(duì)于CC算法在標(biāo)簽序列的生成上采用隨機(jī)生成的缺點(diǎn),創(chuàng)新性地在共現(xiàn)分析的基礎(chǔ)上,采取貪心策略和n-gram策略來(lái)對(duì)標(biāo)簽序列進(jìn)行優(yōu)化。兩種方法都一定程度上考慮了不同長(zhǎng)度標(biāo)簽的潛在關(guān)聯(lián)關(guān)系,因此都給原CC算法帶來(lái)了穩(wěn)定的提升。

在實(shí)驗(yàn)部分,本文首先經(jīng)驗(yàn)驗(yàn)證了n的不同取值對(duì)NCC算法分類(lèi)效果的影響,并選取最合適的n的取值參與后續(xù)的實(shí)驗(yàn),最后,在經(jīng)過(guò)實(shí)驗(yàn)并綜合考慮了Accuracy和F1指標(biāo)、平均指標(biāo)、綜合分類(lèi)性能等各種指標(biāo)情況下,本文發(fā)現(xiàn)NCC和GCC算法能比大多數(shù)前沿的多標(biāo)簽分類(lèi)算法取得更好的效果。證實(shí)了通過(guò)共現(xiàn)分析來(lái)優(yōu)化標(biāo)簽序列,進(jìn)而改進(jìn)整體CC分類(lèi)性能的策略是行之有效的。