李純果，張春琴，李海峰

(1.河北大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院，河北 保定 071002；2.河北省機(jī)器學(xué)習(xí)與計(jì)算智能重點(diǎn)實(shí)驗(yàn)室，河北 保定 071002；3.河北大學(xué) 計(jì)算機(jī)教學(xué)部，河北 保定 071002)

無(wú)監(jiān)督排序?qū)W習(xí)旨在根據(jù)評(píng)價(jià)對(duì)象在多個(gè)指標(biāo)上的觀測(cè)數(shù)據(jù)，提出一種合理的綜合排序模型，得到每個(gè)評(píng)價(jià)對(duì)象的綜合分值并據(jù)此排序.無(wú)監(jiān)督學(xué)習(xí)問(wèn)題的首要任務(wù)是建立一套合理的評(píng)價(jià)準(zhǔn)則，即無(wú)監(jiān)督排序模型構(gòu)造面臨一個(gè)主要的挑戰(zhàn)[1]：在沒(méi)有真實(shí)排序結(jié)果的情況下，如何保證排序模型的合理性.

目前，由于大多數(shù)無(wú)監(jiān)督排序模型的應(yīng)用背景是信息檢索問(wèn)題中搜索引擎對(duì)網(wǎng)頁(yè)、圖像或?qū)W術(shù)文章的排序[2-4]，排序模型的合理性仍然采用了監(jiān)督排序?qū)W習(xí)的評(píng)價(jià)標(biāo)準(zhǔn)[1]，例如應(yīng)用NDCG(normalized discounted cumulative gain)、MAP(mean average precision)在人工標(biāo)注數(shù)據(jù)集上評(píng)價(jià)排序模型.如果排序?qū)ο蟛煌?，例如世界?guó)家經(jīng)濟(jì)水平排名、世界大學(xué)排名，排序方法不僅不適用，而且也無(wú)法標(biāo)注排序?qū)ο?原因在于，應(yīng)用于綜合評(píng)價(jià)的排序問(wèn)題不同于網(wǎng)頁(yè)搜索，是一類靜態(tài)問(wèn)題，當(dāng)排序?qū)ο蟊粯?biāo)注后，排序?qū)W習(xí)就失去了學(xué)習(xí)的意義[5].隨著深度學(xué)習(xí)的發(fā)展，雖然無(wú)監(jiān)督學(xué)習(xí)的學(xué)習(xí)效果有了很大的進(jìn)步[6]，但是深度模型的訓(xùn)練需要億萬(wàn)級(jí)的訓(xùn)練數(shù)據(jù)，并不適用于綜合評(píng)價(jià)問(wèn)題.

在實(shí)際應(yīng)用的學(xué)習(xí)模型構(gòu)建中，應(yīng)用領(lǐng)域知識(shí)會(huì)影響到模型的選擇.在機(jī)器學(xué)習(xí)領(lǐng)域，已經(jīng)有大量的工作將領(lǐng)域知識(shí)嵌入到學(xué)習(xí)模型中，形成“數(shù)據(jù)”與“知識(shí)”共同驅(qū)動(dòng)的學(xué)習(xí)模型[7-8]，增加了模型的透明度(transparency)和可理解性[9].無(wú)監(jiān)督排序問(wèn)題也可以充分利用排序的領(lǐng)域知識(shí)，作為觀測(cè)數(shù)據(jù)的先驗(yàn)知識(shí)和選擇排序模型的參考，從而對(duì)排序?qū)ο笞龀龊侠淼呐判?胡清華等[10]針對(duì)序分類問(wèn)題提出了觀測(cè)屬性與序類標(biāo)的排序互信息的概念，刻畫更抗噪的排序一致性，作為序分類模型的選擇標(biāo)準(zhǔn)和訓(xùn)練精度指標(biāo).同時(shí)，定義的排序互信息在序分類問(wèn)題上可以進(jìn)行很有效的特征選擇，對(duì)分類效果也有很大的提高[10-11].但是，無(wú)監(jiān)督排序問(wèn)題由于沒(méi)有序類標(biāo)的存在[10],定義的排序互信息并不適用于無(wú)監(jiān)督排序模型的學(xué)習(xí)標(biāo)準(zhǔn)和特征選擇的標(biāo)準(zhǔn).

1 預(yù)備知識(shí)

給定n個(gè)排序?qū)ο蠹螦={a1,a2,…，an},V={v1,v2,…,vd}是觀測(cè)屬性集合.由于每個(gè)排序?qū)ο笤谒杏^測(cè)屬性上的觀測(cè)數(shù)據(jù)為一個(gè)n維實(shí)向量x∈Rd，從而對(duì)n個(gè)排序?qū)ο蟮呐判?，也即?duì)Rd的n個(gè)數(shù)據(jù)點(diǎn)進(jìn)行排序.

定義1給定v∈V，如果對(duì)于?x,y∈A，都有v(x)≤v(y),則稱x?vy.

上述定義中，v(x)表示對(duì)象x在屬性v上的觀測(cè)值，“?”表示一種偏序關(guān)系，具備自反性、反對(duì)稱性和傳遞性.

定義2給定U?V，如果對(duì)于?u∈U和?x,y∈A，都有u(x)≤u(y),則稱x?Uy.

定義 3[12]在屬性集U?V條件下，優(yōu)于對(duì)象xi的所有對(duì)象集合，定義

稱之為對(duì)象xi的優(yōu)勢(shì)類.定義

稱之為對(duì)象xi的劣勢(shì)類.

定義4[10]設(shè)U1?V，U2?V，定義U1和U2之間的排序互信息為

(1)

特別地，兩屬性之間的排序互信息定義為

(2)

設(shè)f為排序規(guī)則，是根據(jù)觀測(cè)數(shù)據(jù)對(duì)排序?qū)ο蠼o出的綜合評(píng)價(jià)分值，是觀測(cè)屬性V到實(shí)值的映射.排序規(guī)則需要滿足單調(diào)性，才可以作為觀測(cè)基礎(chǔ)上的綜合評(píng)價(jià)函數(shù)，得到排序?qū)ο蟮娜蚺帕?

定義5如果排序規(guī)則滿足

x?y?f(x)≤f(y),x,y∈A,

(3)

則稱f是單調(diào)的.

綜合評(píng)價(jià)函數(shù)的結(jié)果也可以看成是決策屬性D，是排序?qū)ο蟮男虻牧炕瘜傩?在序分類問(wèn)題中，D是學(xué)習(xí)目標(biāo)，使得綜合評(píng)價(jià)函數(shù)f產(chǎn)生的決策盡可能與排序目標(biāo)一致.為了反應(yīng)觀測(cè)屬性與決策屬性之間的關(guān)聯(lián)程度，在觀測(cè)屬性間的排序互信息的基礎(chǔ)上，Hu等[11]定義了觀測(cè)屬性與決策屬性間的排序互信息.

定義6設(shè)U?V，定義U和D之間的排序互信息為

(4)

根據(jù)定義6中的公式(4)，Hu等針對(duì)序分類學(xué)習(xí)問(wèn)題，計(jì)算了表1中數(shù)據(jù)的2個(gè)觀測(cè)屬性分別與決策屬性之間的排序互信息為

RMI?(a1,D)=0.428 1，RMI?(a2,D)=0.503 9.

2 無(wú)監(jiān)督排序互信息

決策屬性是監(jiān)督學(xué)習(xí)的重要學(xué)習(xí)目標(biāo)，也是評(píng)價(jià)監(jiān)督學(xué)習(xí)模型的重要指標(biāo).然而，無(wú)監(jiān)督學(xué)習(xí)問(wèn)題中沒(méi)有真實(shí)的決策屬性，評(píng)價(jià)排序?qū)W習(xí)的模型就需要獨(dú)立于決策屬性.此時(shí)，由于決策屬性的缺失，公式(4)中定義的排序互信息不適用于無(wú)監(jiān)督排序模型的排序互信息計(jì)算.對(duì)于表1中的數(shù)據(jù)，2個(gè)屬性都與決策屬性呈單調(diào)增加關(guān)系.如果其中一個(gè)屬性與決策屬性呈單調(diào)增加關(guān)系，而另一個(gè)屬性與決策屬性呈單調(diào)減少關(guān)系，例如表2中的數(shù)據(jù)，屬性與決策屬性呈單調(diào)增加關(guān)系，而屬性與決策屬性呈單調(diào)減少關(guān)系.此時(shí)，排序互信息的計(jì)算公式(4)不再適用.因此，需要提出一個(gè)新的排序互信息的計(jì)算公式，獨(dú)立于決策屬性，且能同時(shí)反應(yīng)不同屬性體現(xiàn)的不同單調(diào)關(guān)系.

表2 單增/單減混合序分類數(shù)據(jù)

由于排序問(wèn)題中涉及到的排序?qū)ο笾g的序關(guān)系，面向聚類的無(wú)監(jiān)督特征選擇方法并不適用.對(duì)于無(wú)監(jiān)督排序?qū)W習(xí)來(lái)說(shuō)，由于沒(méi)有排序真值，需要根據(jù)排序的先驗(yàn)知識(shí)對(duì)原始多指標(biāo)觀測(cè)數(shù)據(jù)進(jìn)行特征選擇.排序?qū)ο笾g的序關(guān)系滿足單調(diào)性，在實(shí)數(shù)意義上，參與排序?qū)ο筮M(jìn)行觀測(cè)的屬性或特征，與對(duì)象的最終排名成單調(diào)增加或單調(diào)減少關(guān)系，即屬性值越大，排名越靠前，或越靠后.假設(shè)屬性u(píng)和屬性v與排序結(jié)果都是單調(diào)增加的關(guān)系，則u與v之間也是單調(diào)增加的關(guān)系；而如果屬性與排序結(jié)果是單調(diào)增加的關(guān)系，屬性卻與排序結(jié)果是單調(diào)減少的關(guān)系，那么u與v之間就是單調(diào)減少的關(guān)系.但是對(duì)于給定的觀測(cè)數(shù)據(jù)來(lái)說(shuō)，由于未知各屬性與排序結(jié)果之間的單調(diào)關(guān)系，當(dāng)利用在優(yōu)勢(shì)關(guān)系下定義的排序互信息來(lái)衡量?jī)蓪傩灾g的單調(diào)特征時(shí)，不能單獨(dú)根據(jù)兩屬性之間的RMI?(u,v)或RMI(u,v)來(lái)定義排序互信息.此時(shí)，兩屬性之間的排序互信息定義為

(5)

本文用公式(5)來(lái)進(jìn)行計(jì)算無(wú)監(jiān)督排序問(wèn)題中兩兩屬性間的互信息.對(duì)表2中2個(gè)屬性與決策屬性之間的排序互信息根據(jù)公式(5)進(jìn)行計(jì)算，結(jié)果與公式(4)保持一致，說(shuō)明該公式可以涵蓋原排序互信息的公式，但公式(5)更具有實(shí)際的應(yīng)用適應(yīng)性.

3 無(wú)監(jiān)督特征選擇

在實(shí)際無(wú)監(jiān)督排序特征選擇問(wèn)題中，依據(jù)最小冗余最大相關(guān)(mRMR,minimum redundancy and maximum relevance)原則進(jìn)行特征選擇.對(duì)計(jì)算的兩屬性間的排序互信息進(jìn)行排序，選擇具有最大排序互信息的屬性對(duì)作為無(wú)監(jiān)督排序最相關(guān)的屬性集合.在這些屬性集中，如果一個(gè)屬性與其他屬性都具有最小的互信息，說(shuō)明該屬性不是單調(diào)屬性，與評(píng)價(jià)結(jié)果無(wú)關(guān)，該屬性為冗余屬性，需要從屬性集中排除.上述初步進(jìn)行特征選擇的方法為filter方法，在模型訓(xùn)練之前進(jìn)行，獨(dú)立于無(wú)監(jiān)督排序模型.

基于排序互信息的無(wú)監(jiān)督排序?qū)W習(xí)中的特征選擇算法為

輸入：排序?qū)ο蟮幕赿個(gè)屬性的觀測(cè)數(shù)據(jù).

輸出：最相關(guān)的屬性集合.

1)根據(jù)公式(5)計(jì)算屬性兩兩之間的排序互信息；

2)計(jì)算每個(gè)屬性的平均互信息；

3)把平均排序互信息進(jìn)行從大到小的排序；

4)選擇排序互信息最大的k個(gè)屬性.

構(gòu)建一組模擬數(shù)據(jù)檢驗(yàn)算法的可行性，模擬數(shù)據(jù)的散點(diǎn)圖如圖1所示.從圖1中可以看出，a2與a4兩個(gè)屬性間有明確的單調(diào)函數(shù)關(guān)系，而a1與a2、a4也有比較明顯的單調(diào)關(guān)系，而a5與其他屬性間的單調(diào)關(guān)系不明顯，不是排序的影響因素，為冗余屬性，應(yīng)從排序?qū)傩灾袆h除，以免影響決策.根據(jù)公式(5)計(jì)算的各屬性平均互信息如表3所示.可以看出，屬性與其他屬性具有最小的平均排序互信息，從而與排序無(wú)關(guān)，可以從特征集中排除.

圖1 2-維數(shù)據(jù)散點(diǎn)分布Fig.1 2-dimensional data spots distribution

表3 各屬性平均互信息

4 結(jié)論

在無(wú)監(jiān)督排序?qū)W習(xí)中，由于沒(méi)有決策屬性做參考，已有的基于排序互信息的特征選擇方法不再適用.基于屬性與潛在的決策屬性之間的單調(diào)傳遞關(guān)系，本文提出用每個(gè)屬性與其他屬性之間的平均互信息，來(lái)衡量每個(gè)屬性與排序?qū)W習(xí)結(jié)果的相關(guān)程度.根據(jù)新的排序互信息的定義能夠選出基于不同單調(diào)關(guān)系的評(píng)價(jià)屬性，這是對(duì)已有排序互信息定義的推廣.雖然本文提出的無(wú)監(jiān)督排序互信息的定義在模擬數(shù)據(jù)上的特征選擇效果更具有廣適性，但是對(duì)真實(shí)數(shù)據(jù)的效果有待于進(jìn)一步驗(yàn)證.