邵東恒，楊文元，趙紅

(閩南師范大學 粒計算重點實驗室，福建 漳州 363000)

應用k-means算法實現標記分布學習

邵東恒，楊文元，趙紅

(閩南師范大學 粒計算重點實驗室，福建 漳州 363000)

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

標記分布；聚類；k-means；閔可夫斯基距離；多標記；權重矩陣；均值向量；softmax函數

中文引用格式：邵東恒，楊文元，趙紅.應用k-means算法實現標記分布學習[J]. 智能系統(tǒng)學報， 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.

近年來，標記多義性問題是機器學習和數據挖掘領域的熱門問題。目前已有的兩種比較成熟的學習范式是對每個實例分配單個標記的單標記學習(single-label learning)和對一個實例分配多個標記的多標記學習(multi-label learning)[1]。多標記學習是對單標記學習的拓展[2]。通常多標記學習能處理一個實例屬于多個標記的分歧情況。通過大量的研究和實驗[3-5]表明，多標記學習是一種有效且應用范圍較廣的學習范式。

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

目前，已有一些標記分布學習算法[7, 11]被提了出來。這些算法的設計策略主要可以分為以下3類。

1)問題轉換，即將標記分布學習問題轉換成單標記學習問題后，再利用相應范式中已有的算法進行求解，例如：PT-SVM算法和PT-Bayes算法。

2)算法適應，即擴展現存的學習算法來處理標簽分布學習問題，例如：LDSVR[12]算法和AA-BP算法。

3)專用化的算法，即根據LDL的特點設計特殊的算法，例如：SA-IIS算法、CPNN[13]和SA-BFGS算法。

在這3種策略中，第3種直接針對標記分布學習設計專門算法的效果是最好的。事實上，專用化的算法是通過條件概率或邏輯回歸方式訓練模型，然后以這個模型預測想要的標記分布。但是在這個過程中算法并未充分考慮訓練實例與對應標記分布之間的關系，例如：特征與標記間的函數關系，特征與標記間的分布關系和標記分布數據內部的分布關系。同時，現有的專門算法在處理較大數據集時花費的時間較多。

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

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

1 標記分布學習的形式化

目前的標記分布學習算法的輸出模型是一個最大熵模型[7]：

2 基于k-means的標記分布學習算法

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

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

其次，當迭代結束求出所要劃分的聚類和對應的均值向量后，便可以依據標記分布與訓練樣本集的對應關系得到標記分布的簇劃分和標記分布每個簇的均值向量u。同時利用常用的距離計算公式“閔可夫斯基距離”公式，即

求得測試集每個樣本與各個簇的均值向量的距離矩陣T。閔可夫斯基距離是歐式距離的推廣，具有廣泛的應用，當p=1時是曼哈頓距離，p=2就是歐式距離，而當p趨于無窮大時就是切比雪夫距離。本文中將距離矩陣T的每個元素求倒數再通過一個softmax函數進行處理轉換，從而得到從訓練集樣本的標記分布的均值向量轉化為預測標記分布的權重矩陣。對矩陣T作以下處理，先對T中每個元素求導數：

式中：n是測試集樣本實例數，W為最后預測標記分布所使用的權重矩陣。

最后將W與訓練集對應的標記分布的均值向量矩陣U相乘，即

式中:U=[u1u2…ub];P就是所需要求的預測標記分布。

上述的算法過程可以通過圖1的流程圖來表示。

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

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

算法 基于k-means算法的標記分布學習(LDLKM)。

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

輸出 測試集的預測標記分布P。

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

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

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

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

7)利用式(7)和式(8)求得預測標記分布的權重矩陣W。

8)根據式(9)得出預測標記分布P。

3 實驗與結果分析

在這部分，將通過實驗來驗證本文提出的基于k-means的標記分布學習算法。

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

表1 評價指標

3.1 實驗設置

通過上述5種評價方式，本次實驗在6個公開的數據集上進行，它們分別是Yeast-alpha、 Yeast-cdc、 Yeast-elu、 SJAFFE、 Human Gene和Movie，詳細的信息如表2所示。

表2 實驗數據集描述

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

為了能使實驗結果更具說服力，采用了十折交叉的方式進行實驗。聚類劃分的簇的數目為5，最大迭代次數設置為20，閔可夫斯基距離參數p設置成5。在表2的數據集上進行實驗，并采用表1中的五種評價方式，分別與現有的3種標記分布學習算法進行比較。這3種比較算法分別是PT-Bayes、AA-BP和SA-IIS。

3.2 實驗結果分析

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

表3 數據集Yeast-alpha的實驗結果

表4 數據集Yeast-cdc的實驗結果

表5 數據集Yeast-elu的實驗結果

表6 數據集JAFFE的實驗結果

表7 數據集Human Gene的實驗結果

表8 數據集Movie的實驗結果

4種標記分布算法在6個數據集上的預測結果如圖2所示，內容是標記分布算法對數據集中某個實例的標記分布預測結果和實際標記分布的比較。從圖2中可以看出，LDLKM的預測結果與實際標記分布最為接近，曲線的形狀最為相似，即預測效果最好。在實驗過程中，由于LDLKM直接利用了特征與標記之間的分布關系，訓練模型的時間比現有的專用化的算法還要少。

(a)Yeast-alpha數據集上的預測結果

(b)Yeast-cdc數據集上的預測結果

(c)Yeast-elu數據集上的預測結果

(d)JAFFE數據集上的預測結果

(e)Human-Gene數據集上的預測結果

(f)Movie數據集上的預測結果

4 結束語

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

[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]季榮姿. 標記分布學習及其應用[D]. 南京：東南大學, 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]程旸, 王士同. 基于局部保留投影的多可選聚類發(fā)掘算法[J]. 智能系統(tǒng)學報, 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上基于數據集劃分的k-means多核優(yōu)化算法[J]. 智能系統(tǒng)學報, 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]趙權, 耿新. 標記分布學習中目標函數的選擇[J]. 計算機科學與探索， 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]周志華. 機器學習[M]. 北京：清華大學出版社, 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]周治平, 王杰鋒, 朱書偉,等. 一種改進的自適應快速AF-DBSCAN聚類算法[J]. 智能系統(tǒng)學報, 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. 網絡出版日期：2017-07-04.

國家自然科學基金項目(61379049， 61379089).

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

TP181

A

1673-4785(2017)03-0325-08

邵東恒，男，1992年生，碩士研究生，主要研究方向為標記分布學習。

楊文元，男，1967年生，副教授，博士，主要研究方向為機器學習、標記分布學習。發(fā)表學術論文20余篇。

趙紅，女，1979年生，副教授，主要研究方向為粒計算、分層分類學習。發(fā)表學術論文40余篇。