近年来，标记多义性问题是机器学习和数据挖掘领域的热门问题。目前已有的两种比较成熟的学习范式是对每个实例分配单个标记的单标记学习(single-label learning)和对一个实例分配多个标记的多标记学习(multi-label learning)^[1]。多标记学习是对单标记学习的拓展^[2]。通常多标记学习能处理一个实例属于多个标记的分歧情况。通过大量的研究和实验^[3-5]表明，多标记学习是一种有效且应用范围较广的学习范式。

多标记学习虽然对于一个实例允许标上多个标记，拓展了单标记学习。但是仍有一些问题是不太适合用多标记学习解决的，例如，标记集中的每一个标记描述实例的准确度是多少。事实上，现实世界中有着比大多数人想象的多得多的关于每个标记的准确描述度的数据。在许多科学实验中^[6]，它们的输出结果不是单个值的，而是一系列的数值输出，例如，基因在不同时间点上的表达水平。这些输出中的单个数值可能不是那么重要，真正重要的是这一系列输出数值的分布情况。如果一个机器学习的任务是要预测一个数值分布，那么它很难放到多标记学习的框架中实现。因为在一个分布中每一个数值输出的准确度是至关重要的，而且这里也不再有相关标记与无关标记的区分了。因此，为了解决这类问题，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]是研究分类问题的一种统计分析方法，同时也是数据挖掘的一个重要算法，在研究过程中也有许许多多的应用和改进^[15]。聚类以相似性为基础，试图将数据集中的样本划分为若干个不相交的子集，每个子集称为一个簇，同一簇中样本之间的相似性比不在同一簇中的更高。在聚类算法中常用的k-means算法^[16]及改进算法^[17]是原型聚类的一种，它假设聚类结构能通过一组原型刻画。通常情况下，算法先对原型进行初始化，然后对原型进行迭代更新求解，直到均值向量不再改变或达到最大迭代次数，此时就能得到每一个簇的均值向量。

在同一个数据集中，特征相近的实例，它们的标记分布往往也相似，同时依据聚类的特性，本文提出一种新的标记分布算法：基于k-means的标记分布学习算法(label distribution learning algorithm based on k-means，LDLKM)。首先，利用k-means聚类算法求得训练样本集中每个簇的均值向量，此时与每一个训练样本对应的标记分布也相应被划分成簇。然后，求得标记分布的每个簇的均值向量。其次，测试集的样本到各个簇的均值向量的距离矩阵可通过常用的求距离方式，闵可夫斯基距离(Minkowski distance)^[18]求得。最后，将距离矩阵通过一个softmax函数变换得到一个权重矩阵。权重矩阵和训练样本集的标记分布的均值向量的积就是测试集样本的标记分布，即需要预测的标记分布。本文提出的LDLKM算法与现有的专用化的算法相比并未采用条件概率的方式建立模型，而是充分考虑了特征间的分布关系和特征与对应的标记分布之间的联系，利用k-means聚类和权重矩阵将特征和标记分布联系到一起。事实上，特征之间的分布与对应标记之间的分布的关系是一种更加直接和强烈的联系。而直接利用这种关系预测得到的标记分布可以继续保持与对应特征的分布关系，从而得到一个较好的结果。LDLKM和现有的3种LDL算法在6个公开数据集^[7]上采用5种评价方式进行实验比较，实验的结果表明本文提出的标记分布学习算法在使用的所有数据集上均取得较好的效果，在其中的5个数据集上所有评价方式的结果均为最优。

1 标记分布学习的形式化

在标记分布中，标记一个实例x的方式是为它的每一个可能的标记y分配一个实数d_x^y，用来表示标记y对实例x的描述程度。不失一般性，假设实数d_x^y∈[0, 1]，进一步假设所有标记能够完整地描述实例，则$\sum\limits_y {d_x^y = 1} $。

标记分布学习是一种更为灵活复杂的标记学习范式，然而学习中更好的灵活性通常意味着更大的输出空间^[19]。从单标记学习到多标记学习，再到标记分布学习，学习过程的输出空间的维度变得越来越大。更为详细地，对于标记集合中有c个不同标记的学习问题，单标记学习的分类器有c个可能的输出，多标记学习的分类器有2^c－1个可能的输出。对标记分布学习的分类器来讲，只要在满足d_x^y∈[0, 1]和$\sum\limits_y {d_x^y = 1} $这两个约束条件的前提下，它的输出空间的维度可能是无穷大的^[19]。

标记分布学习定义的实例矩阵为X=[x₁ x₂ … x_n]，x_i∈R^d表示第i个实例，i=1, 2, …, n。给定对应标记矩阵Y=[y₁ y₂… y_c]，y_j表示第j个标记，j=1, 2, …, c；给定样本的标记分布集是D=[D₁ D₂ … D_n]，D_i=d_xi^y₁ d_xi^y₂ … d_xi^y_c表示实例x_i的标记分布集，d_xi^y_j表示标记y_j对实例x_i的描述度。基于此，标记分布学习的一个训练集能够表示为S={(x₁, D₁), (x₂, D₂), …, (x_n, D_n)}。

目前的标记分布学习算法的输出模型是一个最大熵模型^[7]：

$ p\left( {y\left| {x;\theta } \right.} \right) = \frac{1}{Z}\exp \left( {\sum\limits_j {{\theta _{y, j}}} {f_j}\left( x \right)} \right) $

(1)

式中：$Z = \sum\limits_y {\exp \left( {\sum\limits_j {{\theta _{y, j}}} {f_j}\left( x \right)} \right)} $是归一化因数；θ_{y, j}是模型参数；f_j(x)是x的第j个特征。随着标记分布的发展逐渐提出许多基于式(1) 的标记分布学习方法^{[7, 9-10]}。这些算法先通过条件概率建立参数模型，再利用现有的模型求解参数θ。

2 基于k-means的标记分布学习算法

k-means算法是所有聚类算法中简单常用的一种算法^[20]。它假设聚类结构能被一组原型刻画，先初始化一组原型，然后对原型进行迭代更新求解，最终得到每一个簇的均值向量。给定训练集H=[x₁ x₂ … x_m], m为训练集样本数。k-means算法针对聚类所得簇划分G={C₁, C₂, …, C_k}, 最小化平方误差为

$ E = \sum\limits_{i = 1}^k {\sum\limits_{x \in {C_i}} {\left\| {\mathit{\boldsymbol{x}}-{\mathit{\boldsymbol{\mu }}_i}} \right\|_2^2} } $

(2)

式中：${\mathit{\boldsymbol{\mu }}_i} = \frac{1}{{\left| {{C_i}} \right|}}\sum\limits_{x \in {C_i}} \mathit{\boldsymbol{x}} $是簇C_i的均值向量。直观来看，式(2) 在一定程度上刻画了簇内样本围绕簇均值向量的紧密程度，E值越小则簇内样本相似度越高。最小化式(2) 并不容易，找到其最优解需考察训练集H所有可能的簇划分，这是一个NP难^[20-21]的问题。因此，k-means算法采用了贪心策略，通过迭代优化来近似求解式(2)。

首先，聚类过程中在H中随机选择k个样本作为初始均值向量{μ₁, μ₂, …，μ_k}，可以通过下式：

$ {d_{ji}} = {\left\| {{\mathit{\boldsymbol{x}}_j}-{\mathit{\boldsymbol{\mu }}_i}} \right\|_2} $

(3)

计算训练集样本x_j与各均值向量μ_i(i=1, 2, …, k)的距离。根据距离最近的均值向量确定x_j的簇标记：

$ {\lambda _j} = \arg {\min _{i \in \left[{1, 2, \cdots, k} \right]}}{d_{ji}} $

(4)

式中λ_j∈(1, 2, …, k)表示样本x_j的簇标记。将样本x_j划入相应的簇，即

$ {C_{{\lambda _j}}} = {C_{{\lambda _j}}} \cup \left[ {{\mathit{\boldsymbol{x}}_j}} \right] $

(5)

更新簇C_λj的均值向量。式(3)~式(5) 这个过程不断迭代直到当前均值向量保持不变或迭代次数达到所规定的最大次数。

其次，当迭代结束求出所要划分的聚类和对应的均值向量后，便可以依据标记分布与训练样本集的对应关系得到标记分布的簇划分和标记分布每个簇的均值向量u。同时利用常用的距离计算公式“闵可夫斯基距离”公式，即

$ {\rm{dis}}{{\rm{t}}_{{\rm{mk}}}}\left( {{\mathit{\boldsymbol{x}}_i}, {\mathit{\boldsymbol{x}}_j}} \right) = {\left( {\sum\limits_{u = 1}^n {{{\left| {{\mathit{\boldsymbol{x}}_{iu}}-{\mathit{\boldsymbol{x}}_{ju}}} \right|}^p}} } \right)^{\frac{1}{p}}} $

(6)

求得测试集每个样本与各个簇的均值向量的距离矩阵T。闵可夫斯基距离是欧式距离的推广，具有广泛的应用，当p=1时是曼哈顿距离，p=2就是欧式距离，而当p趋于无穷大时就是切比雪夫距离。本文中将距离矩阵T的每个元素求倒数再通过一个softmax函数进行处理转换，从而得到从训练集样本的标记分布的均值向量转化为预测标记分布的权重矩阵。对矩阵T作以下处理，先对T中每个元素求导数：

$ \mathit{\boldsymbol{T}}{'_{ab}} = \frac{1}{{{\mathit{\boldsymbol{T}}_{ab}}}} $

(7)

然后，为了尽量减小与测试样本实例距离较远的均值向量的影响和便于之后的计算，利用softmax函数$ {Z_k} = {\rm{softmax}}\left( {{x_k}} \right) = \frac{{\exp \left( {{x_k}} \right)}}{{\sum\nolimits_{i = 1}^k {\exp \left( {{x_i}} \right)} }}$再作以下处理：

$ {\mathit{\boldsymbol{W}}_a} = \frac{{\exp \left( {\mathit{\boldsymbol{T}}{'_{ab}}} \right)}}{{\sum\limits_{b = 1}^k {\exp \left( {\mathit{\boldsymbol{T}}{'_{ab}}} \right)} }}, \;\;a = 1, 2, \cdots, n $

(8)

式中：n是测试集样本实例数，W为最后预测标记分布所使用的权重矩阵。

最后将W与训练集对应的标记分布的均值向量矩阵U相乘，即

$ \mathit{\boldsymbol{P = WU}} $

(9)

式中:U=[ u₁ u₂ … u_b]; P就是所需要求的预测标记分布。

上述的算法过程可以通过图 1的流程图来表示。

本文提出的LDLKM算法具体步骤如下：

算法  基于k-means算法的标记分布学习(LDLKM)。

输入  聚类的簇数k，聚类迭代的最大次数d，闵可夫斯基距离参数p, 训练集S={(x₁, D₁), (x₂, D₂), …, (x_n, D_n)}。

输出  测试集的预测标记分布P。

1) 从训练集样本H中随机选择k个样本作为初始向量(μ₁, μ₂, …, μ_k}。

2) 迭代开始，令C_i(1≤i≤k)为空，利用式(3) 计算样本x_j与各均值向量μ_i的距离。

3) 依据式(4)，根据距离最近的均值向量确定x_j的簇标记λ_j；将样本x_j划入相应的簇。

4) 更新均值向量，分别计算划分完簇后的新的均值向量：${\mathit{\boldsymbol{\mu }}_i} = \frac{1}{{\left| {{C_i}} \right|}}\sum\limits_{x \in {C_i}} \mathit{\boldsymbol{x}} $。

5) 若当前的均值向量均未更新或达到规定的最大迭代次数，继续下一步；否则，返回2)，重复3) 到5) 直到所有测法样本划分完毕。

6) 依据式(6) 求得测试集每个样本与各个均值向量的距离矩阵T。

7) 利用式(7) 和式(8) 求得预测标记分布的权重矩阵W。

8) 根据式(9) 得出预测标记分布P。

3 实验与结果分析

在这部分，将通过实验来验证本文提出的基于k-means的标记分布学习算法。

标记分布学习算法的输出是一个标记分布，与单标记学习的单标记输出和多标记学习的标记集输出都不同。因此，标记分布学习算法的评价方式，应该与单标记学习和多标记学习算法不同。这种方式不是通过预测标记的准确度来评价算法优劣，而是通过测量预测结果和真实标记分布之间的距离或相似度来衡量算法效果。有很多测量概率分布之间的距离或相似度的方法^[7]可以用来很好地测量标记分布之间的距离或相似度。例如，表 1中根据文献[7]和[22]选出的5种测量方式就能很好地用来评价标记分布算法。评价标准距离名称之后的“↓”代表距离值越小越好，相似度名称之后的“↑”表示相似值越大越好。这5种评价方法分别是切比雪夫距离(Chebyshev)、克拉克距离(Clark)、堪培拉量度(Canberra)、弦系数(Cosine)以及交叉相似性(Intersection)，前3种以距离作为评价，即越小越好，后两种以相似度作为评价，即越大越好。

3.1 实验设置

通过上述5种评价方式，本次实验在6个公开的数据集上进行，它们分别是Yeast-alpha、Yeast-cdc、Yeast-elu、SJAFFE、Human Gene和Movie，详细的信息如表 2所示。

第1个到第3个数据集(从Yeast-alpha到Yeast-elu)是从酿酒酵母^[6]的4个生物实验上收集的真实数据集。每个数据集总共包括2 465个酵母基因，每个基因通过24个特征表示。标记对应于离散的时间点，标记分布是每个时间点的基因表达水平。第四个数据集拓展来自一个脸部表情图像数据集JAFFE，它包括来自10个日本女性的213张灰度图，并利用局部二值模式^[23]从每张图像中采集243个特征，每张图像由60个人在6种感情上打分。第5个数据集Human Gene是一个大规模的真实数据集，来自于人类基因和疾病的关系生物实验^[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个人类基因数据集完全优于和它对比的算法，第4个和第6个数据集也优于其他两个对比算法，并在总体上优于第3个对比算法。整体上来看，LDLKM在基因数据集上可以取得比在其他类型数据集上更好的效果，在非基因数据集SJAFFE和Movie上的效果略微差于在基因数据集上的效果，而在Human Gene数据集上LDLKM的效果与SA-IIS较为接近，提升效果不大。这说明不同类型的数据集对我们的算法有着一定的影响。同时，可以进一步看到，专用化的算法SA-IIS比算法PT-Bayes和AA-BP的效果更好，处于第二的位置。

4种标记分布算法在6个数据集上的预测结果如图 2所示，内容是标记分布算法对数据集中某个实例的标记分布预测结果和实际标记分布的比较。从图 2中可以看出，LDLKM的预测结果与实际标记分布最为接近，曲线的形状最为相似，即预测效果最好。在实验过程中，由于LDLKM直接利用了特征与标记之间的分布关系，训练模型的时间比现有的专用化的算法还要少。

4 结束语

本文提出的基于k-means标记分布学习算法，是在标记分布框架下，利用标记分布和样本集所具有的联系，通过求得一个权重矩阵来得到预测标记分布，而不是与现有的算法一样，通过求每一个标记的条件概率来得到预测标记分布。LDLKM主要通过将训练集的样本作为k-means聚类的样本，获得每个簇的均值向量。然后将求得的测试集样本与均值向量的距离矩阵，作为预测标记分布与训练集对应的标记分布间的关系，直接求得所需的预测标记分布。本算法充分利用了特征和标记之间的分布关系，又通过softmax函数减小了与测试样本距离较远的均值向量的影响，同时本算法相对于现有的专门化的算法在较大的数据集上花费的时间更少。在公开的6个数据集上进行的实验所得的结果说明，本文提出的基于k-means的标记分布学习算法是有效的。在以后的工作中，我们将对算法进一步优化，还可以引入集成学习来强化聚类效果, 或采用一种改进的聚类算法^[25]，或针对标记分布学习的特性来专门设计一个聚类算法。