應(yīng)用k-means算法實(shí)現(xiàn)標(biāo)記分布學(xué)習(xí)

邵東恒，楊文元，趙紅

(閩南師范大學(xué) 粒計(jì)算重點(diǎn)實(shí)驗(yàn)室，福建 漳州 363000)

應(yīng)用k-means算法實(shí)現(xiàn)標(biāo)記分布學(xué)習(xí)

邵東恒，楊文元，趙紅

(閩南師范大學(xué) 粒計(jì)算重點(diǎn)實(shí)驗(yàn)室，福建 漳州 363000)

標(biāo)記分布學(xué)習(xí)是近年來(lái)提出的一種新的機(jī)器學(xué)習(xí)范式，它能很好地解決某些標(biāo)記多義性的問(wèn)題。現(xiàn)有的標(biāo)記分布學(xué)習(xí)算法均利用條件概率建立參數(shù)模型，但未能充分利用特征和標(biāo)記間的聯(lián)系。本文考慮到特征相似的樣本所對(duì)應(yīng)的標(biāo)記分布也應(yīng)當(dāng)相似，利用原型聚類(lèi)的k均值算法(k-means)，將訓(xùn)練集的樣本進(jìn)行聚類(lèi)，提出基于k-means算法的標(biāo)記分布學(xué)習(xí)(label distribution learning based onk-means algorithm，LDLKM)。首先通過(guò)聚類(lèi)算法k-means求得每一個(gè)簇的均值向量，然后分別求得對(duì)應(yīng)標(biāo)記分布的均值向量。最后將測(cè)試集和訓(xùn)練集的均值向量間的距離作為權(quán)重，應(yīng)用到對(duì)測(cè)試集標(biāo)記分布的預(yù)測(cè)上。在6個(gè)公開(kāi)的數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，并與3種已有的標(biāo)記分布學(xué)習(xí)算法在5種評(píng)價(jià)指標(biāo)上進(jìn)行比較，實(shí)驗(yàn)結(jié)果表明提出的LDLKM算法是有效的。

標(biāo)記分布；聚類(lèi)；k-means；閔可夫斯基距離；多標(biāo)記；權(quán)重矩陣；均值向量；softmax函數(shù)

中文引用格式：邵東恒，楊文元，趙紅.應(yīng)用k-means算法實(shí)現(xiàn)標(biāo)記分布學(xué)習(xí)[J]. 智能系統(tǒng)學(xué)報(bào)， 2017, 12(3): 325-332.

英文引用格式：SHAO Dongheng， YANG Wenyuan， ZHAO Hong.Label distribution learning based onk-means algorithm[J]. CAAI transactions on intelligent systems, 2017, 12(3): 325-332.

近年來(lái)，標(biāo)記多義性問(wèn)題是機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘領(lǐng)域的熱門(mén)問(wèn)題。目前已有的兩種比較成熟的學(xué)習(xí)范式是對(duì)每個(gè)實(shí)例分配單個(gè)標(biāo)記的單標(biāo)記學(xué)習(xí)(single-label learning)和對(duì)一個(gè)實(shí)例分配多個(gè)標(biāo)記的多標(biāo)記學(xué)習(xí)(multi-label learning)[1]。多標(biāo)記學(xué)習(xí)是對(duì)單標(biāo)記學(xué)習(xí)的拓展[2]。通常多標(biāo)記學(xué)習(xí)能處理一個(gè)實(shí)例屬于多個(gè)標(biāo)記的分歧情況。通過(guò)大量的研究和實(shí)驗(yàn)[3-5]表明，多標(biāo)記學(xué)習(xí)是一種有效且應(yīng)用范圍較廣的學(xué)習(xí)范式。

多標(biāo)記學(xué)習(xí)雖然對(duì)于一個(gè)實(shí)例允許標(biāo)上多個(gè)標(biāo)記，拓展了單標(biāo)記學(xué)習(xí)。但是仍有一些問(wèn)題是不太適合用多標(biāo)記學(xué)習(xí)解決的，例如，標(biāo)記集中的每一個(gè)標(biāo)記描述實(shí)例的準(zhǔn)確度是多少。事實(shí)上，現(xiàn)實(shí)世界中有著比大多數(shù)人想象的多得多的關(guān)于每個(gè)標(biāo)記的準(zhǔn)確描述度的數(shù)據(jù)。在許多科學(xué)實(shí)驗(yàn)中[6]，它們的輸出結(jié)果不是單個(gè)值的，而是一系列的數(shù)值輸出，例如，基因在不同時(shí)間點(diǎn)上的表達(dá)水平。這些輸出中的單個(gè)數(shù)值可能不是那么重要，真正重要的是這一系列輸出數(shù)值的分布情況。如果一個(gè)機(jī)器學(xué)習(xí)的任務(wù)是要預(yù)測(cè)一個(gè)數(shù)值分布，那么它很難放到多標(biāo)記學(xué)習(xí)的框架中實(shí)現(xiàn)。因?yàn)樵谝粋€(gè)分布中每一個(gè)數(shù)值輸出的準(zhǔn)確度是至關(guān)重要的，而且這里也不再有相關(guān)標(biāo)記與無(wú)關(guān)標(biāo)記的區(qū)分了。因此，為了解決這類(lèi)問(wèn)題，Geng等[7]拓展了多標(biāo)記學(xué)習(xí)，提出了標(biāo)記分布學(xué)習(xí)(label distribution learning，LDL)范式。對(duì)于一個(gè)特定的實(shí)例，標(biāo)記集合中所有標(biāo)記的描述度構(gòu)建一個(gè)類(lèi)似于概率分布的數(shù)據(jù)形式，稱(chēng)之為標(biāo)記分布[8]，即每個(gè)訓(xùn)練實(shí)例與一個(gè)標(biāo)記分布相對(duì)應(yīng)。與多標(biāo)記學(xué)習(xí)輸出一個(gè)標(biāo)記集不同，標(biāo)記分布學(xué)習(xí)輸出的是一個(gè)標(biāo)記分布，分布中的每個(gè)分量表示對(duì)應(yīng)標(biāo)記對(duì)實(shí)例的描述程度。事實(shí)上，標(biāo)記分布學(xué)習(xí)是一種適用場(chǎng)景更廣的學(xué)習(xí)范式，能夠解決更多的標(biāo)記多義性問(wèn)題。單標(biāo)記學(xué)習(xí)和多標(biāo)記學(xué)習(xí)都可以看成標(biāo)記分布學(xué)習(xí)的特例,相關(guān)的研究成果[7, 9-10]也說(shuō)明了這一點(diǎn)。

目前，已有一些標(biāo)記分布學(xué)習(xí)算法[7, 11]被提了出來(lái)。這些算法的設(shè)計(jì)策略主要可以分為以下3類(lèi)。

1)問(wèn)題轉(zhuǎn)換，即將標(biāo)記分布學(xué)習(xí)問(wèn)題轉(zhuǎn)換成單標(biāo)記學(xué)習(xí)問(wèn)題后，再利用相應(yīng)范式中已有的算法進(jìn)行求解，例如：PT-SVM算法和PT-Bayes算法。

2)算法適應(yīng)，即擴(kuò)展現(xiàn)存的學(xué)習(xí)算法來(lái)處理標(biāo)簽分布學(xué)習(xí)問(wèn)題，例如：LDSVR[12]算法和AA-BP算法。

3)專(zhuān)用化的算法，即根據(jù)LDL的特點(diǎn)設(shè)計(jì)特殊的算法，例如：SA-IIS算法、CPNN[13]和SA-BFGS算法。

在這3種策略中，第3種直接針對(duì)標(biāo)記分布學(xué)習(xí)設(shè)計(jì)專(zhuān)門(mén)算法的效果是最好的。事實(shí)上，專(zhuān)用化的算法是通過(guò)條件概率或邏輯回歸方式訓(xùn)練模型，然后以這個(gè)模型預(yù)測(cè)想要的標(biāo)記分布。但是在這個(gè)過(guò)程中算法并未充分考慮訓(xùn)練實(shí)例與對(duì)應(yīng)標(biāo)記分布之間的關(guān)系，例如：特征與標(biāo)記間的函數(shù)關(guān)系，特征與標(biāo)記間的分布關(guān)系和標(biāo)記分布數(shù)據(jù)內(nèi)部的分布關(guān)系。同時(shí)，現(xiàn)有的專(zhuān)門(mén)算法在處理較大數(shù)據(jù)集時(shí)花費(fèi)的時(shí)間較多。

聚類(lèi)[14]是研究分類(lèi)問(wèn)題的一種統(tǒng)計(jì)分析方法，同時(shí)也是數(shù)據(jù)挖掘的一個(gè)重要算法，在研究過(guò)程中也有許許多多的應(yīng)用和改進(jìn)[15]。聚類(lèi)以相似性為基礎(chǔ)，試圖將數(shù)據(jù)集中的樣本劃分為若干個(gè)不相交的子集，每個(gè)子集稱(chēng)為一個(gè)簇，同一簇中樣本之間的相似性比不在同一簇中的更高。在聚類(lèi)算法中常用的k-means算法[16]及改進(jìn)算法[17]是原型聚類(lèi)的一種，它假設(shè)聚類(lèi)結(jié)構(gòu)能通過(guò)一組原型刻畫(huà)。通常情況下，算法先對(duì)原型進(jìn)行初始化，然后對(duì)原型進(jìn)行迭代更新求解，直到均值向量不再改變或達(dá)到最大迭代次數(shù)，此時(shí)就能得到每一個(gè)簇的均值向量。

在同一個(gè)數(shù)據(jù)集中，特征相近的實(shí)例，它們的標(biāo)記分布往往也相似，同時(shí)依據(jù)聚類(lèi)的特性，本文提出一種新的標(biāo)記分布算法：基于k-means的標(biāo)記分布學(xué)習(xí)算法(label distribution learning algorithm based onk-means，LDLKM)。首先，利用k-means聚類(lèi)算法求得訓(xùn)練樣本集中每個(gè)簇的均值向量，此時(shí)與每一個(gè)訓(xùn)練樣本對(duì)應(yīng)的標(biāo)記分布也相應(yīng)被劃分成簇。然后，求得標(biāo)記分布的每個(gè)簇的均值向量。其次，測(cè)試集的樣本到各個(gè)簇的均值向量的距離矩陣可通過(guò)常用的求距離方式，閔可夫斯基距離(Minkowski distance)[18]求得。最后，將距離矩陣通過(guò)一個(gè)softmax函數(shù)變換得到一個(gè)權(quán)重矩陣。權(quán)重矩陣和訓(xùn)練樣本集的標(biāo)記分布的均值向量的積就是測(cè)試集樣本的標(biāo)記分布，即需要預(yù)測(cè)的標(biāo)記分布。本文提出的LDLKM算法與現(xiàn)有的專(zhuān)用化的算法相比并未采用條件概率的方式建立模型，而是充分考慮了特征間的分布關(guān)系和特征與對(duì)應(yīng)的標(biāo)記分布之間的聯(lián)系，利用k-means聚類(lèi)和權(quán)重矩陣將特征和標(biāo)記分布聯(lián)系到一起。事實(shí)上，特征之間的分布與對(duì)應(yīng)標(biāo)記之間的分布的關(guān)系是一種更加直接和強(qiáng)烈的聯(lián)系。而直接利用這種關(guān)系預(yù)測(cè)得到的標(biāo)記分布可以繼續(xù)保持與對(duì)應(yīng)特征的分布關(guān)系，從而得到一個(gè)較好的結(jié)果。LDLKM和現(xiàn)有的3種LDL算法在6個(gè)公開(kāi)數(shù)據(jù)集[7]上采用5種評(píng)價(jià)方式進(jìn)行實(shí)驗(yàn)比較，實(shí)驗(yàn)的結(jié)果表明本文提出的標(biāo)記分布學(xué)習(xí)算法在使用的所有數(shù)據(jù)集上均取得較好的效果，在其中的5個(gè)數(shù)據(jù)集上所有評(píng)價(jià)方式的結(jié)果均為最優(yōu)。

1 標(biāo)記分布學(xué)習(xí)的形式化

目前的標(biāo)記分布學(xué)習(xí)算法的輸出模型是一個(gè)最大熵模型[7]：

2 基于k-means的標(biāo)記分布學(xué)習(xí)算法

計(jì)算訓(xùn)練集樣本xj與各均值向量μi(i=1,2,…,k)的距離。根據(jù)距離最近的均值向量確定xj的簇標(biāo)記：

更新簇Cλj的均值向量。式(3)～式(5)這個(gè)過(guò)程不斷迭代直到當(dāng)前均值向量保持不變或迭代次數(shù)達(dá)到所規(guī)定的最大次數(shù)。

其次，當(dāng)?shù)Y(jié)束求出所要?jiǎng)澐值木垲?lèi)和對(duì)應(yīng)的均值向量后，便可以依據(jù)標(biāo)記分布與訓(xùn)練樣本集的對(duì)應(yīng)關(guān)系得到標(biāo)記分布的簇劃分和標(biāo)記分布每個(gè)簇的均值向量u。同時(shí)利用常用的距離計(jì)算公式“閔可夫斯基距離”公式，即

求得測(cè)試集每個(gè)樣本與各個(gè)簇的均值向量的距離矩陣T。閔可夫斯基距離是歐式距離的推廣，具有廣泛的應(yīng)用，當(dāng)p=1時(shí)是曼哈頓距離，p=2就是歐式距離，而當(dāng)p趨于無(wú)窮大時(shí)就是切比雪夫距離。本文中將距離矩陣T的每個(gè)元素求倒數(shù)再通過(guò)一個(gè)softmax函數(shù)進(jìn)行處理轉(zhuǎn)換，從而得到從訓(xùn)練集樣本的標(biāo)記分布的均值向量轉(zhuǎn)化為預(yù)測(cè)標(biāo)記分布的權(quán)重矩陣。對(duì)矩陣T作以下處理，先對(duì)T中每個(gè)元素求導(dǎo)數(shù)：

式中：n是測(cè)試集樣本實(shí)例數(shù)，W為最后預(yù)測(cè)標(biāo)記分布所使用的權(quán)重矩陣。

最后將W與訓(xùn)練集對(duì)應(yīng)的標(biāo)記分布的均值向量矩陣U相乘，即

式中:U=[u1u2…ub];P就是所需要求的預(yù)測(cè)標(biāo)記分布。

上述的算法過(guò)程可以通過(guò)圖1的流程圖來(lái)表示。

圖1 LDLKM算法流程圖Fig.1 The flowchart of LDLKM

本文提出的LDLKM算法具體步驟如下：

算法 基于k-means算法的標(biāo)記分布學(xué)習(xí)(LDLKM)。

輸入 聚類(lèi)的簇?cái)?shù)k，聚類(lèi)迭代的最大次數(shù)d，閔可夫斯基距離參數(shù)p,訓(xùn)練集S={(x1,D1),(x2,D2),…,(xn,Dn)}。

輸出 測(cè)試集的預(yù)測(cè)標(biāo)記分布P。

2)迭代開(kāi)始，令Ci(1≤i≤k)為空，利用式(3)計(jì)算樣本xj與各均值向量μi的距離。

3)依據(jù)式(4)，根據(jù)距離最近的均值向量確定xj的簇標(biāo)記λj；將樣本xj劃入相應(yīng)的簇。

5)若當(dāng)前的均值向量均未更新或達(dá)到規(guī)定的最大迭代次數(shù)，繼續(xù)下一步；否則，返回2)，重復(fù)3)到5)直到所有測(cè)法樣本劃分完畢。

6)依據(jù)式(6)求得測(cè)試集每個(gè)樣本與各個(gè)均值向量的距離矩陣T。

7)利用式(7)和式(8)求得預(yù)測(cè)標(biāo)記分布的權(quán)重矩陣W。

8)根據(jù)式(9)得出預(yù)測(cè)標(biāo)記分布P。

3 實(shí)驗(yàn)與結(jié)果分析

在這部分，將通過(guò)實(shí)驗(yàn)來(lái)驗(yàn)證本文提出的基于k-means的標(biāo)記分布學(xué)習(xí)算法。

標(biāo)記分布學(xué)習(xí)算法的輸出是一個(gè)標(biāo)記分布，與單標(biāo)記學(xué)習(xí)的單標(biāo)記輸出和多標(biāo)記學(xué)習(xí)的標(biāo)記集輸出都不同。因此，標(biāo)記分布學(xué)習(xí)算法的評(píng)價(jià)方式，應(yīng)該與單標(biāo)記學(xué)習(xí)和多標(biāo)記學(xué)習(xí)算法不同。這種方式不是通過(guò)預(yù)測(cè)標(biāo)記的準(zhǔn)確度來(lái)評(píng)價(jià)算法優(yōu)劣，而是通過(guò)測(cè)量預(yù)測(cè)結(jié)果和真實(shí)標(biāo)記分布之間的距離或相似度來(lái)衡量算法效果。有很多測(cè)量概率分布之間的距離或相似度的方法[7]可以用來(lái)很好地測(cè)量標(biāo)記分布之間的距離或相似度。例如，表1中根據(jù)文獻(xiàn)[7]和[22]選出的5種測(cè)量方式就能很好地用來(lái)評(píng)價(jià)標(biāo)記分布算法。評(píng)價(jià)標(biāo)準(zhǔn)距離名稱(chēng)之后的“↓”代表距離值越小越好，相似度名稱(chēng)之后的“↑”表示相似值越大越好。這5種評(píng)價(jià)方法分別是切比雪夫距離(Chebyshev)、克拉克距離(Clark)、堪培拉量度(Canberra)、弦系數(shù)(Cosine)以及交叉相似性(Intersection)，前3種以距離作為評(píng)價(jià)，即越小越好，后兩種以相似度作為評(píng)價(jià)，即越大越好。

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

3.1 實(shí)驗(yàn)設(shè)置

通過(guò)上述5種評(píng)價(jià)方式，本次實(shí)驗(yàn)在6個(gè)公開(kāi)的數(shù)據(jù)集上進(jìn)行，它們分別是Yeast-alpha、 Yeast-cdc、 Yeast-elu、 SJAFFE、 Human Gene和Movie，詳細(xì)的信息如表2所示。

表2 實(shí)驗(yàn)數(shù)據(jù)集描述

第1個(gè)到第3個(gè)數(shù)據(jù)集(從Yeast-alpha到Y(jié)east-elu)是從釀酒酵母[6]的4個(gè)生物實(shí)驗(yàn)上收集的真實(shí)數(shù)據(jù)集。每個(gè)數(shù)據(jù)集總共包括2 465個(gè)酵母基因，每個(gè)基因通過(guò)24個(gè)特征表示。標(biāo)記對(duì)應(yīng)于離散的時(shí)間點(diǎn)，標(biāo)記分布是每個(gè)時(shí)間點(diǎn)的基因表達(dá)水平。第四個(gè)數(shù)據(jù)集拓展來(lái)自一個(gè)臉部表情圖像數(shù)據(jù)集JAFFE，它包括來(lái)自10個(gè)日本女性的213張灰度圖，并利用局部二值模式[23]從每張圖像中采集243個(gè)特征，每張圖像由60個(gè)人在6種感情上打分。第5個(gè)數(shù)據(jù)集Human Gene是一個(gè)大規(guī)模的真實(shí)數(shù)據(jù)集，來(lái)自于人類(lèi)基因和疾病的關(guān)系生物實(shí)驗(yàn)[24]。在數(shù)據(jù)集中總共包括30 542個(gè)人類(lèi)基因，每一個(gè)都被一個(gè)基因序列的36個(gè)特征數(shù)值表示。68個(gè)標(biāo)記對(duì)應(yīng)于68種疾病，標(biāo)記分布是基因在68種疾病上的表達(dá)水平。第6個(gè)數(shù)據(jù)集Movie是關(guān)于電影的用戶(hù)評(píng)級(jí)。評(píng)級(jí)數(shù)據(jù)來(lái)源于Netflix，范圍是15級(jí)(5個(gè)標(biāo)記)。標(biāo)記分布描述了每個(gè)評(píng)級(jí)所占的比例。特征則提取自電影的元數(shù)據(jù)，一共有1 869個(gè)特征。

為了能使實(shí)驗(yàn)結(jié)果更具說(shuō)服力，采用了十折交叉的方式進(jìn)行實(shí)驗(yàn)。聚類(lèi)劃分的簇的數(shù)目為5，最大迭代次數(shù)設(shè)置為20，閔可夫斯基距離參數(shù)p設(shè)置成5。在表2的數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，并采用表1中的五種評(píng)價(jià)方式，分別與現(xiàn)有的3種標(biāo)記分布學(xué)習(xí)算法進(jìn)行比較。這3種比較算法分別是PT-Bayes、AA-BP和SA-IIS。

3.2 實(shí)驗(yàn)結(jié)果分析

表3～8分別列出在6個(gè)不同的數(shù)據(jù)集上，4種算法對(duì)應(yīng)不同評(píng)價(jià)標(biāo)準(zhǔn)的測(cè)量值。前3個(gè)評(píng)價(jià)指標(biāo)(Cheby、Clark和Canbe)值越小表示算法效果越好，后兩個(gè)評(píng)價(jià)指標(biāo)(Cosine和Interse)值越大表示算法效果越好。在每個(gè)表中最后一列是本文算法的結(jié)果。從表中可以看出本文提出的算法在5種評(píng)價(jià)標(biāo)準(zhǔn)下都有很好的效果。前3個(gè)酵母基因數(shù)據(jù)集和第5個(gè)人類(lèi)基因數(shù)據(jù)集完全優(yōu)于和它對(duì)比的算法，第4個(gè)和第6個(gè)數(shù)據(jù)集也優(yōu)于其他兩個(gè)對(duì)比算法，并在總體上優(yōu)于第3個(gè)對(duì)比算法。整體上來(lái)看，LDLKM在基因數(shù)據(jù)集上可以取得比在其他類(lèi)型數(shù)據(jù)集上更好的效果，在非基因數(shù)據(jù)集SJAFFE和Movie上的效果略微差于在基因數(shù)據(jù)集上的效果，而在Human Gene 數(shù)據(jù)集上LDLKM的效果與SA-IIS較為接近，提升效果不大。這說(shuō)明不同類(lèi)型的數(shù)據(jù)集對(duì)我們的算法有著一定的影響。同時(shí)，可以進(jìn)一步看到，專(zhuān)用化的算法SA-IIS比算法PT-Bayes和AA-BP的效果更好，處于第二的位置。

表3 數(shù)據(jù)集Yeast-alpha的實(shí)驗(yàn)結(jié)果

表4 數(shù)據(jù)集Yeast-cdc的實(shí)驗(yàn)結(jié)果

表5 數(shù)據(jù)集Yeast-elu的實(shí)驗(yàn)結(jié)果

表6 數(shù)據(jù)集JAFFE的實(shí)驗(yàn)結(jié)果

表7 數(shù)據(jù)集Human Gene的實(shí)驗(yàn)結(jié)果

表8 數(shù)據(jù)集Movie的實(shí)驗(yàn)結(jié)果

4種標(biāo)記分布算法在6個(gè)數(shù)據(jù)集上的預(yù)測(cè)結(jié)果如圖2所示，內(nèi)容是標(biāo)記分布算法對(duì)數(shù)據(jù)集中某個(gè)實(shí)例的標(biāo)記分布預(yù)測(cè)結(jié)果和實(shí)際標(biāo)記分布的比較。從圖2中可以看出，LDLKM的預(yù)測(cè)結(jié)果與實(shí)際標(biāo)記分布最為接近，曲線的形狀最為相似，即預(yù)測(cè)效果最好。在實(shí)驗(yàn)過(guò)程中，由于LDLKM直接利用了特征與標(biāo)記之間的分布關(guān)系，訓(xùn)練模型的時(shí)間比現(xiàn)有的專(zhuān)用化的算法還要少。

(a)Yeast-alpha數(shù)據(jù)集上的預(yù)測(cè)結(jié)果

(b)Yeast-cdc數(shù)據(jù)集上的預(yù)測(cè)結(jié)果

(c)Yeast-elu數(shù)據(jù)集上的預(yù)測(cè)結(jié)果

(d)JAFFE數(shù)據(jù)集上的預(yù)測(cè)結(jié)果

(e)Human-Gene數(shù)據(jù)集上的預(yù)測(cè)結(jié)果

(f)Movie數(shù)據(jù)集上的預(yù)測(cè)結(jié)果

4 結(jié)束語(yǔ)

本文提出的基于k-means標(biāo)記分布學(xué)習(xí)算法，是在標(biāo)記分布框架下，利用標(biāo)記分布和樣本集所具有的聯(lián)系，通過(guò)求得一個(gè)權(quán)重矩陣來(lái)得到預(yù)測(cè)標(biāo)記分布，而不是與現(xiàn)有的算法一樣，通過(guò)求每一個(gè)標(biāo)記的條件概率來(lái)得到預(yù)測(cè)標(biāo)記分布。LDLKM主要通過(guò)將訓(xùn)練集的樣本作為k-means聚類(lèi)的樣本，獲得每個(gè)簇的均值向量。然后將求得的測(cè)試集樣本與均值向量的距離矩陣，作為預(yù)測(cè)標(biāo)記分布與訓(xùn)練集對(duì)應(yīng)的標(biāo)記分布間的關(guān)系，直接求得所需的預(yù)測(cè)標(biāo)記分布。本算法充分利用了特征和標(biāo)記之間的分布關(guān)系，又通過(guò)softmax函數(shù)減小了與測(cè)試樣本距離較遠(yuǎn)的均值向量的影響，同時(shí)本算法相對(duì)于現(xiàn)有的專(zhuān)門(mén)化的算法在較大的數(shù)據(jù)集上花費(fèi)的時(shí)間更少。在公開(kāi)的6個(gè)數(shù)據(jù)集上進(jìn)行的實(shí)驗(yàn)所得的結(jié)果說(shuō)明，本文提出的基于k-means的標(biāo)記分布學(xué)習(xí)算法是有效的。在以后的工作中，我們將對(duì)算法進(jìn)一步優(yōu)化，還可以引入集成學(xué)習(xí)來(lái)強(qiáng)化聚類(lèi)效果,或采用一種改進(jìn)的聚類(lèi)算法[25]，或針對(duì)標(biāo)記分布學(xué)習(xí)的特性來(lái)專(zhuān)門(mén)設(shè)計(jì)一個(gè)聚類(lèi)算法。

[1]ZHANG M L, ZHOU Z H. A review on multi-label learning algorithms[J]. IEEE transactions on knowledge and data engineering, 2014, 26(8): 1819-1837.

[2]WEI Yunchao, XIA Wei, HUANG Junshi, et al. CNN: Single-label to multi-label[J]. Computer science, 2014,11: 26-56.

[3]TSOUMAKAS G, KATAKIS I, TANIAR D. Multi-label classification: an overview[J]. International journal of data warehousing and mining, 2007, 3(3): 1-13.

[4]READ J, PFAHRINGER B, HOLMES G, et al. Classifier chains for multi-label classification[J]. Machine learning, 2011, 85(3): 333-359.

[5]READ J, PFAHRINGER B, HOLMES G. Multi-label classification using ensembles of pruned sets[C]// Proceedings of Eighth IEEE International Conference on Data Mining, Pisa, Italy, 2008. Washington, USA: IEEE Computer Society, 2008: 995-1000.

[6]EISEN M B, SPELLMAN P T, BROWN P O, et al. Cluster analysis and display of genome-wide expression patterns[J]. Proceedings of the national academy of sciences of the united states of America, 1998, 95(25): 14863-14868.

[7]Geng X. Label distribution learning[J]. IEEE transactions on knowledge and data engineering, 2014, 28(7): 1734-1748.

[8]季榮姿. 標(biāo)記分布學(xué)習(xí)及其應(yīng)用[D]. 南京：東南大學(xué), 2014. JI Rongzi. Label distribution learning and its application[D].Nanjing: Southeast University, 2014.

[9]ZHANG Z, WANG M, GENG X. Crowd counting in public video surveillance by label distribution learning[J]. Neurocomputing, 2015, 166(C): 151-163.

[10]GENG X, WANG Q, XIA Y. Facial age estimation by adaptive label distribution learning[C]// Proceedings of IEEE International Conference on Pattern Recognition, Stockholm, Sweden, 2014. Washington, USA: IEEE Computer Society, 2014: 4465-4470.

[11]GENG X, XIA Y. Head pose estimation based on multivariate label distribution[C]//Proceedings of IEEE International Conference on Computer Vision and Pattern Recognition, Columbus, USA, 2014. Washington, USA: IEEE Computer Society, 2014:1837-1842.

[12]GENG X, HOU P. Pre-release prediction of crowd opinion on movies by label distribution learning[C]// Proceedings of the International Joint Conference on Artificial Intelligence, Buenos Aires, Argentina, 2015. San Francisco, USA:Morgan Kaufmann, 2015: 3511-3517.

[13]GENG X, YIN C, ZHOU Z H. Facial age estimation by learning from label distributions.[J]. IEEE transactions on pattern analysis and machine intelligence, 2013, 35(10): 2401-2412.

[14]JAIN A K. Data clustering: a review[J]. ACM computing surveys, 1999, 31(3): 264-323.

[15]程旸, 王士同. 基于局部保留投影的多可選聚類(lèi)發(fā)掘算法[J]. 智能系統(tǒng)學(xué)報(bào), 2016, 11(5): 600-607. CHENG Yang， WANG Shitong. A multiple alternative clusterings mining algorithm using locality preserving projections[J]. CAAI transactions on intelligent systems, 2016, 11(5): 600-607.

[16]HARTIGAN J A, WONG M A. Ak-means clustering algorithm[J]. Applied statistics, 2013, 28(1): 100-108.

[17]申彥, 朱玉全. CMP上基于數(shù)據(jù)集劃分的k-means多核優(yōu)化算法[J]. 智能系統(tǒng)學(xué)報(bào), 2015(4):607-614. SHEN Yan, ZHU Yuquan. An optimized algorithm ofk-means based on data set partition on CMP systems[J]. CAAI transactions on intelligent systems, 2015, 10(4): 607-614.

[18]GROENEN P J F, KAYMAK U, VAN Rosmalen J. Fuzzy clustering with minkowski distance functions[J]. Fuzzy sets and systems, 2001, 120(2): 227-237.

[19]趙權(quán), 耿新. 標(biāo)記分布學(xué)習(xí)中目標(biāo)函數(shù)的選擇[J]. 計(jì)算機(jī)科學(xué)與探索， 2017,11(5): 1-12. ZHAO Quan, GENG Xin. Selection of target function in label distribution learning[J]. Journal of frontiers of computer science and technology, 2017,11(5): 1-12.

[20]周志華. 機(jī)器學(xué)習(xí)[M]. 北京：清華大學(xué)出版社, 2016.

[21]ALOISE D, DESHPANDE A, HANSEN P, et al. NP-hardness of euclidean sum-of-squares clustering[J]. Machine learning, 2009, 75(2): 245-248.

[22]CHA S H. Comprehensive survey on distance/similarity measures between probability density functions [J]. International journal of mathematical models and methods in applied sciences, 2007, 1(4): 300-307.

[23]AHONEN T, HADID A, PIETIKINEN M. Face description with local binary patterns: application to face recognition[J]. IEEE trans pattern anal mach intell, 2006, 28(12): 2037-2041.

[24]YU J F, JIANG D K, XIAO K, et al. Discriminate the falsely predicted protein-coding genes in Aeropyrum Pernix K1 genome based on graphical representation[J]. Match communications in mathematical and in computer chemistry, 2012, 67(3): 845-866.

[25]周治平, 王杰鋒, 朱書(shū)偉,等. 一種改進(jìn)的自適應(yīng)快速AF-DBSCAN聚類(lèi)算法[J]. 智能系統(tǒng)學(xué)報(bào), 2016, 11(1):93-98. ZHOU Zhiping, WANG Jiefeng, ZHU Shuwei, et al. An improved adaptive and fast AF-DBSCAN clustering algorithm[J]. CAAI transaction on intelligent systems, 2016, 11(1): 93-98.

Label distribution learning based onk-means algorithm

SHAO Dongheng， YANG Wenyuan， ZHAO Hong

(1. Lab of Granular Computing, Minnan Normal University, Zhangzhou 363000, China)

Label distribution learning is a new type of machine learning paradigm that has emerged in recent years. It can solve the problem wherein different relevant labels have different importance. Existing label distribution learning algorithms adopt the parameter model with conditional probability, but they do not adequately exploit the relation between features and labels. In this study, thek-means clustering algorithm, a type of prototype-based clustering, was used to cluster the training set instance since samples having similar features have similar label distribution. Hence, a new algorithm known as label distribution learning based onk-means algorithm (LDLKM) was proposed. It firstly calculated each cluster’s mean vector using thek-means algorithm. Then, it got the mean vector of the label distribution corresponding to the training set. Finally, the distance between the mean vectors of the test set and the training set was applied to predict label distribution of the test set as a weight. Experiments were conducted on six public data sets and then compared with three existing label distribution learning algorithms for five types of evaluation measures. The experimental results demonstrate the effectiveness of the proposed KM-LDL algorithm.

label distribution; clustering;k-means; Minkowski distance; multi-label; weight matrix; mean vector; softmax function

10.11992/tis.201704024

http://kns.cnki.net/kcms/detail/23.1538.TP.20170704.0925.002.html

2017-04-19. 網(wǎng)絡(luò)出版日期：2017-07-04.

國(guó)家自然科學(xué)基金項(xiàng)目(61379049， 61379089).

楊文元. E-mail：yangwy@xmu.edu.cn.

TP181

A

1673-4785(2017)03-0325-08

邵東恒，男，1992年生，碩士研究生，主要研究方向?yàn)闃?biāo)記分布學(xué)習(xí)。

楊文元，男，1967年生，副教授，博士，主要研究方向?yàn)闄C(jī)器學(xué)習(xí)、標(biāo)記分布學(xué)習(xí)。發(fā)表學(xué)術(shù)論文20余篇。

趙紅，女，1979年生，副教授，主要研究方向?yàn)榱Ｓ?jì)算、分層分類(lèi)學(xué)習(xí)。發(fā)表學(xué)術(shù)論文40余篇。