基于標記特定特征和相關性的ML-KNN改進算法①

李 永,許 鵬

(北京工業大學 軟件學院,北京 100124)

傳統監督學習認為一個對象只具有一個標記類別,屬于“單示例,單標記”類型.在上述單一語義的情境中,監督學習已經取得了巨大的發展成果.然而在真實世界中,一個對象往往同時具有多種語義信息,屬于“單示例,多標記”類型.例如在一篇新聞稿中可同時包含改革和經濟兩個主題,一張風景圖中天空和云朵往往會伴隨出現,在這種情況下很難用單一語義標記去描述對象信息.為此,多標記學習框架應運而生,用于解決真實世界中一個對象同時具有多個語義標記的問題.因其可以良好的反映真實世界中包含的多語義信息,目前在文本分類[1],圖像標注[2],生物基因分析[3]等領域得到了廣泛應用.同時眾多學者也提出了一些多標記學習算法,并取得了一定的成功.但是目前大部分已有的多標記學習算法所采用的共同策略是基于同一特征屬性空間預測所有標記類別,忽略了每個標記獨有的特征信息,因此這種思路存在改進優化的空間.其中ML-KNN[4]作為一種使用簡單,分類性能優異的多標記學習算法,其數學形式相對簡單,模型易于優化,在實際應用和學術科研中得到了廣泛應用.但是ML-KNN算法在模型訓練過程中并沒有考慮標記之間的相關性,同時也忽略了標記特定特征信息.因此,在模型訓練過程中考慮標記相關性和引入標記特定特征信息,可以進一步提高算法的分類性能,基于此提出了本文算法.本文的整體組織結構如下:第1 部分介紹相關工作,第2 部分描述本算法的實現,第3 部分給出實驗以及實驗結果,最后進行了總結.

1 相關工作

在傳統“單示例,單標記”的單語義環境中,傳統監督學習已經取得了巨大的發展[5–8].然而在真實世界中,語義信息往往是豐富多彩的,傳統監督學習已經不能對同時從屬于多個標記類別下的單個示例進行很好的語義表達.相比于傳統監督學習,多標記學習可以更好的反映真實世界中包含的語義信息.不同于傳統監督學習所假設的“單示例,單標記”情形,多標記學習所研究的任務場景屬于“單示例,多標記”類型.我們假設X=Rd代表d維特征空間,Y={l1,l2,···,lq}代表包含q個標記類別的標記空間.多標記學習的任務是在訓練集D={(xi,Yi)|1≤i≤m} 中訓練一個分類器h:X→2Y,預測未知示例x∈X 所從屬的標記集合h(x)?Y,其中xi∈X為特征空間中的一個示例,是一個d維特征向量,Yi∈Y 為示例xi所從屬的標記集合,是標記空間 Y中的一個子集.

目前多標記學習研究所面臨的主要挑戰是標記空間爆炸性增長的問題[9].即類別標記集合數隨著標記種類的增加而呈指數級增長,假設樣本中包含有q個類別標記信息,則標記輸出空間規模即可達到 2q級別的大小,為每個標記子集單獨訓練一個分類器是不切實際的.為了解決這個標記空間爆炸的問題,目前關于多標記學習的研究大都集中在通過挖掘標記之間的相關性來降低指數級別增長的標記空間.根據標記相關性的利用策略,可以將多標記學習算法分為3 類:(1)一階策略,完全忽略標記之間的相關性,只是將一個多分類問題轉換為多個獨立的二分類問題,這類方法雖然實現簡單但是缺少良好的泛化性能.(2)二階策略,考慮標記之間的成對關聯,例如相關標記與無關標記之間的排序關系,兩兩標記之間的交互關系等構造多標記學習框架.這類算法具有一定的泛化性能,但是無法很好的解決標記之間的關系超過二階時的問題.(3)高階策略,考慮單個標記與其它全部標記之間的相關性,這類算法可以很好的反映真實世界的標記相關性,但同時模型復雜度往往較高.目前眾多學者也提出了一些多標記學習算法,例如由Boutell 等提出的一階策略算法BR (Binary Relevance)[10],由Fürnkranz 等提出的二階策略算法Calibrated Label Ranking[11],由Read 等提出的高階策略算法Classifer Chains[12]等.上述算法的共同點是將多分類問題分解為多個二分類問題進行解決,屬于問題轉換型.由Clare 等提出的一階策略算法ML-KNN,ML-DT[13]和Elisseeff A 提出的二階策略算法Rank-SVM[14]等算法是采用當前的機器學習算法直接處理多分類問題,屬于算法適應型.但無論是問題轉換型算法還是算法適應型算法,上述提到的算法在預測標記時都是假設所有標記共享同一特征空間,并未對每種類別標記獨有的特征信息進行考慮.即多標記學習框架得到的q個實值函數 {f1,f2,···,fq}都是基于相同的屬性特征空間訓練而來.但是這種思路可能并不是最優的,例如在圖像識別領域,在判斷“天空”和“沙漠”時,顏色特征是需要優先考慮的,而在判斷“藍天”和“大海”時,考慮紋理特征相關屬性會大大提高分類器的性能.由此可見,每個標記都可能具有與其最大相關性的屬性特征,考慮每個標記獨有的屬性特征對于提高算法分類性能具有一定的幫助,這些屬性特征是對該標記最有區別度的特征,稱為標記特定特征信息.

其中,ML-KNN 作為一種使用簡單,分類性能高效的算法,在實際應用中得到了廣泛應用.但是ML-KNN算法屬于一階策略,并未對標記之間相關性進行考慮,同時也沒有考慮標記特定特征信息.雖然該算法取得了巨大的成果,但是并未對標記相關性和標記特定特征信息加以利用,存在優化改進的空間.由Zhang 等提出了LIFT 算法[15]首次提出從引入標記特定特征信息這一角度出發的研究思路,針對每一個標記信息提取其特征信息,從而構建標記特征空間,之后基于標記特征空間進行模型訓練.該算法基于多種公開數據集證明了其思路的有效性,為多標記學習指明了一個新的研究方向.但是該算法并未考慮標記之間的相關性,屬于一階策略算法.基于此,我們通過融入標記相關性和引入標記特定特征信息對ML-KNN 算法進行改進,進一步提高算法分類性能.

2 ML-KNN 算法以及改進算法

2.1 ML-KNN 算法

ML-KNN 算法是在k近鄰算法的基礎上,綜合貝葉斯理論提出的能夠處理多標記分類問題的KNN 算法.在此引入一些符號用于對該算法進行說明.在多標記訓練數據集D={(xi,Yi)|1≤i≤m} 中,xi∈X,Yi∈Y,Yx為示例xi所對應的q維標記向量.如果示例x具有類別標記l(1≤l≤q),則定義Yx(l)=1,否則Yx(l)=0.另外假設N(x)代表示例x在訓練集D中的k個近鄰集合,對這k個近鄰集合中擁有標記l的樣本數量用Cx(l)表示,其中:

其中,Cx代表了示例x所對應的k個近鄰集合中所包含的標記信息.ML-KNN 算法為懶惰算法,當有新的測試示例t需要進行預測分類時,ML-KNN 首先識別示例t在訓練數據集D中的k個近鄰集合N(t),在這里設定H1l代表示例t擁有標記l,相反,當示例t沒有標記l時用H0l表示.另外引入Elj表示在N(t)中有j個示例擁有標記l,其中j∈{0,1,···,k},基于向量Ct,示例t所對應的類別向量Yt可以使用如下最大后驗概率來計算.

該式所代表的含義為已知在測試示例t的k個近鄰集合中有Ct(l)個樣本與標記l相關,示例t與標記l是否相關取決于N(t)中是否與標記l相關的最大概率.根據貝葉斯規則,上式可以進一步變換為:

由上述公式可知,計算Yt(l)需要得到先驗概率和條件概率這兩個值都是可以從訓練數據樣本計算得到的.

2.2 基于ML-KNN 算法的改進算法

LIFT 算法是由張敏靈等學者在研究多標記學習算法時提出的一種全新的算法.該算法不同于之前研究點集中于挖掘標記之間相關性上,而忽略了標記特定特征信息.LIFT 算法從挖掘標記特征這一角度出發,針對每一個標記類別,通過挖掘其特征信息構建標記特征空間,在模型訓練過程中引入標記特征,并且經過大量實驗表明LIFT 算法分類性能在公開數據集上優于其它多標記學習算法,同時也證明了在模型訓練過程中引入標記特定特征信息提高算法分類性能這一思路的有效性,為后續多標記學習研究提供了一種新的思路.

2.2.1 LIFT 算法基本模型

LIFT 算法通過對訓練樣本中的每個類別標記進行聚類操作,分析每個標記的特征信息,將原始樣本集合根據特征標記劃分為與當前標記呈正相關的樣本和負相關的樣本.具體來說,對于標記lj∈Y,根據式(4)和式(5)分別計算其正相關的示例集合Pj和負相關示例集合Nj.

其中,Yi表示實例xi所對應的標記向量,D為訓練數據集,Pj代表包含標記lj的示例集合,Nj代表不包含標記lj的示例集合.之后采用K-means 聚類算法分別對兩個示例集合進行聚類操作,得到在Pj上的個聚類中心和在Nj上的個聚類中心為了解決聚類中心不平衡的問題,LIFT算法設定mj==,其中這兩個聚類中心集合分別代表著正負相關示例集合的內在特征結構,可作為構建標記特定特征空間的基礎.為了構建標記lj的特定特征空間Zj,采用如下映射φj:X→Zj,φj表達如下:

其中,d(·,·)代表兩個向量之間的歐式距離.根據映射φj,可以將原始訓練數據集D轉換為標記lj對應的二分類訓練集Z.之后在新的訓練集Z上進行模型的訓練,可以構建出一個基于標記特定特征推導出的二分類器簇一般地,對于標記lj∈Y,其對應的二分類訓練數據集可由映射φj表示為:

其中,如果標記lj∈Yi,Yi(j)=1,否則Yi(j)=0.基于訓練數據集,可推導出一個分類器:Zj→R.對于未知示例u,其對應的標記集合可以形式化的表示為其中t代表一個闕值函數,一般設置為常數0.

2.2.2 MLF-KNN 算法

ML-KNN 算法屬于一階策略算法,在模型訓練過程中沒有考慮標記之間的相關性信息,同時在預測標記時是基于相同的屬性特征集合,忽略了每個標記所獨有的屬性特征信息,因此ML-KNN 算法存在優化改進的空間.LIFT 算法經過大量實驗表明該算法的分類性能與其它多標記學習算法相比具有一定的競爭力,證明了在模型訓練過程中引入標記特定特征信息可以提高算法分類性能這一思路的可行性和有效性.為此,我們借鑒該思路,對ML-KNN 算法進行改進,并且融入標記相關性信息,提出基于標記特定特征新的多標記分類新算法MLF-KNN (Multi-Label Feature-K Nearest Neighbor).本算法首先對多標記訓練樣本集合進行預處理,通過對每個類別標記進行聚類分析構建基本標記特征,之后通過稀疏正則化的方式協同增強與其它類別標記的信息從而增強對每個標記特征信息的表述,進而引入當前標記與其它標記之間的相關性.基于得到的標記特定特征,使用改進后的ML-KNN 算法進行分類.不失一般性,引入一些符號進行本算法的說明.在模型訓練之前,首先需要構建每個標記所對應的正負相關示例集合.對于訓練樣本中的每個標記lk∈Y(1≤k≤q),MLF-KNN 算法根據式(4)和式(5)將原始示例集合分為mk個 正相關特征集合Pk和mk個負相關特征集合Nk,其中mk=r·min(|lk∈Yk|,|lk?Yk|).之后在集合Pk>和Nk中采用K-means 聚類算法構建聚類中心,用于構建基本標記特征空間.在正相關示例集合Pk中聚類中心可以通過表示,負相關特征集合Nk中聚類中心可以通過表示.對于示例x∈X,可通過計算示例x與聚類中心之間的距離構建其基本標記特征,最終生成的基本標記特征空間是一個大小為2mk的矩陣φk:X→R2mk.

其中,d(·,·)不在采用LIFT 算法中的歐式距離進行度量,而是采用標準歐式距離進行計算,相比于歐式距離,標準歐式距離對于兩個向量中的維度不一致的情況進行了考慮,對于維度不一致的示例具有更好的包容性,根據式(7),生成標記lk的基本特定特征空間.此時基本標記特定特征空間只是針對標記lk所構建,并未考慮lk與其它標記之間的相關性.假設代表標記向量lk,類似的,如果lk∈Yi,則yki=1,否則yki=0.進一步,設定:

其中,φk(x)表示除標記lk以外的其它所有類別標記的特定特征信息,是一個維度為dk的特征向量,其中dk=將映射 φk應用于全部訓練樣本上,從而可以構建出關于標記lk并且維度為m×dk的標記特定特征矩陣Xk,其中為了解決ML-KNN 算法并未考慮標記之間相關性的問題,我們需要對標記之間相關性進行挖掘并將相關性信息引入標記特定特征空間中.具體來說,需要通過引入標記lk與其它類別標記之間的相關性對之前生成的基本標記特征空間Xk進行增強.在本方法中將標記之間相關性問題轉換為最小二乘法優化問題,通過引入L1正則化項對其進行優化求解從而引入標記lk與其它類別標記之間的相關性,優化最小二乘法問題如下:

根據之前生成的基本標記特征空間 φk中的數值取值介于0 到1 之間,在此我們將闕值 γ設定為常數值0.5.對于標記lk,通過融合標記相關性信息后對基本標記特征進行增強,即可生成最終標記特定特征ψk:X→Zk,其中ψk(x)表示形式如下:

針對訓練樣本中的每一個標記類別分別構造其特定特征空間,在標記空間集合中應用改進后的ML-KNN算法進行模型訓練,其中在計算兩個標記之間距離時MLF-KNN 算法不同于ML-KNN 采用歐式距離直接計算,而是采用如下r階Minkowski 距離進行計算[16].

其中,xl代表示例x的第l維,||·||表示取該實數值的絕對值.在計算兩個樣本之間的距離時采用Minkowski距離度量方法的主要出發點是考慮到不同數據集內數據可能具有不同分布從而需要采取不同的距離計算方法,采用Minkowski 方法可以提高本算法對不同數據集的包容性.當階數取值為1 時,可以轉換為曼哈頓距離.當階數取值為2 時,可以轉換為歐氏距離.當階數繼續增大到無窮大時可轉換為切比雪夫距離.在本實驗中所采用的數據集中的數據取值規范,分布較為獨立,因此設定r值為2 轉換為歐式距離進行試驗.當數據集中的數據分布具有關聯性或者局限性時,可以改變r值的取值以適配不同的數據分布.MLF-KNN 算法描述如算法1 所示.

算法1.MLF-KNN 算法步驟1.構造基本標記特征集.lk Y={l1,l2,···,lq}For in do利用式(4)和式(5)構建標記正相關樣本集 和負相關樣本集;End for lk Y={l1,l2,···,lq}For in do Pk Nk通過式(8)構建針對 的標記特征映射;lk φk End for

步驟2.增強基本標記特征集,構建標記特征.lk Y={l1,l2,···,lq}For in do通過對式(10)進行L1-范數正則化計算權重向量;βk通過式(11),式(12),構建最終標記特征;End for步驟3.構建二分類訓練集.lk Y={l1,l2,···,lq}For in do Dk根據式(13)構建標記 的二分類訓練集;End for步驟4.計算先驗概率.lk Y={l1,l2,···,lq}For in do lk Dk計算標記 的先驗概率:P(Hlb)(b∈{0,1},l∈Y)lk;End for步驟5.計算示例在標記特定特征空間中的k 近鄰集合.xki Dk For in do通過式(14)計算k 近鄰集合,從而根據式(1)計算N(x)Cx(l)End for P(ElCx(l)|Hl1)P(ElCx(l)|Hl0)步驟6.計算各類標記條件概率 和條件概率.步驟7.對待測樣例t 進行分類,通過式(8)構建新的樣本表達,分別在計算和,利用式(3)計算其對應的標記向量.tk DkN(t)Ct(l)Yt

3 實驗

為了檢驗MLF-KNN 算法的分類效果,將本算法與ML-KNN,LIFT,Rank-SVM 等3 個多標記學習算法在公開酵母數據集yeast 和圖像數據集image 上進行比較.其中ML-KNN 算法基于傳統k近鄰技術處理多標記問題,基于已有樣本的先驗概率,通過在訓練樣本中尋找距離最近的k個實例從而對未知示例進行標記預測.但是該方法沒有考慮標記之間的關聯信息,屬于算法適應型一階策略算法.LIFT 算法通過構造每一個標記獨有的特征信息,基于標記獨有的示例集合進行模型訓練,是從標記特征信息研究的新型算法,但是同樣沒有引入標記之間的相關信息,也屬于一階策略算法.Rank-SVM 算法使用最大化間隔思想處理多標記問題,該算法的核心是通過一組線性分類器對Ranking Loss 指標進行優化,并通過引入“核技巧”處理非線性分類問題[9],屬于算法適應型二階策略算法.實驗所采用的數據集yeast 和image 在多標記學習領域是兩個公開的數據集,分別在生物領域和圖像領域具有一定的代表性,兩個數據集詳細信息如表1所示.

表1 數據集詳細信息

由于每個示例同時類屬于多個標記,因此傳統的單標記評價指標例如精度(accuracy)、查準率(precision)和查全率(recall)等指標不再適用.本文評價指標基于Haming Loss,One-error,Coverage,Ranking Loss,Average Precision[17]等5 種在多標記學習領域廣泛使用的評價指標.其中,對于Average Precision 指標信息,數值越大代表分類性能越好,在表中使用 ↑表示,其余評價指標數值越小則代表其分類性能越好,在表中使用 ↓表示.表2為各個算法在數據集yeast 上的測試結果,表3為在數據集image 上的測試結果.本文提出的算法基于ML-KNN 改進而來,圖1為MLF-KNN 算法與ML-KNN 算法在數據集yeast 上的隨k值變化的Coverage 評價指標對比結果圖

表2 本文算法與其它算法在數據集yeast 上的實驗結果對比

表3 本文算法與其它算法在數據集image 上的實驗果對比

圖1 MLF-KNN 與ML-KNN 算法在數據集yeast 數據集隨k 值變化的Coverage 變化曲線圖

由圖1可以看出,本文提出的算法相比于ML-KNN算法在Coverage 評價指標上表現性能十分優異,當k值繼續增大時,Coverage 值可以接近最優解1.0,代表MLF-KNN 算法對于測試樣本的預測所有相關性標記的平均查找深度小,分類性能有所提高.由表2和表3的對比實驗結果圖可以看出,本文所提出的算法MLFKNN 在數據集yeast 當中表現優異.反映在具體評價指標上,MLF-KNN 算法在One-error,Ranking Loss 和Average Precision 指標上表現不是最優,雖然Ranking Loss 指標上的表現低于LIFT 算法,但是相比ML-KNN算法而言該評價指標有所提高.在數據集image 中,本算法同樣在評價指標Haming Loss 和Coverage 上表現最優.實驗結果表明對ML-KNN 算法引入標記特定特征和標記相關性進行改進可以進一步提高算法分類性能,尤其在Coverage 上表現更為明顯,同時也證明了從標記特定特征對算法進行改進創新這一思路的有效性.

4 結論與展望

ML-KNN 算法在模型訓練過程中沒有考慮到標記之間的相關性,同時在預測不同標記時基于同一特征空間,忽略了每個標記所特定的標記特征.LIFT 算法從利用每個標記所獨有的特征出發,為多標記學習研究指明了一個新的方向.基于此,我們對ML-KNN 算法進行改進,在構造標記特征空間的同時對其進行增強,引入與其它標記之間的相關性,提高了算法分類性能.在之后的工作中,可以進一步對構建標記特征空間的方法進行創新,另外本算法并未對標記不平衡的問題進行考慮,當正負標記樣本數量差異過大時會制約算法的分類性能,所以下一步工作可以將當前多標記學習領域對正負標記不平衡問題的研究[18]引入到本算法當中.