第3期 邵东恒，等：应用k-neans算法实现标记分布学习 ·327· 数d!∈[0,1]，进一步假设所有标记能够完整地描 高。最小化式(2)并不容易，找到其最优解需考察 述实例，则∑d=1。 训练集H所有可能的簇划分，这是一个NP难20- 的问题。因此，k-means算法采用了贪心策略，通过 标记分布学习是一种更为灵活复杂的标记学 迭代优化来近似求解式(2)。 习范式，然而学习中更好的灵活性通常意味着更大 的输出空间。从单标记学习到多标记学习，再到 首先，聚类过程中在H中随机选择k个样本作 标记分布学习，学习过程的输出空间的维度变得越 为初始均值向量{μ12，…“}，可以通过下式： da=lx-u:‖2 (3) 来越大。更为详细地，对于标记集合中有c个不同 标记的学习问题，单标记学习的分类器有c个可能 计算训练集样本x与各均值向量4：(i=1,2,…,k) 的距离。根据距离最近的均值向量确定x:的簇 的输出，多标记学习的分类器有2-1个可能的输 出。对标记分布学习的分类器来讲，只要在满足 标记： 入y=arg minie[1,2.…分 (4) d∈[0,1]和∑d心=1这两个约束条件的前提下， 式中入，∈(1,2，…，k)表示样本的簇标记。将样 它的输出空间的维度可能是无穷大的1] 本x划入相应的簇，即 标记分布学习定义的实例矩阵为X= C=CU [x;] (5) [x1x2…xn],x∈R表示第i个实例，i=1,2,…,no 更新簇C,的均值向量。式(3)~式(5)这个过程不 给定对应标记矩阵Y=[y1y2…y],y表示第j个 断迭代直到当前均值向量保持不变或迭代次数达 标记，j=1,2,…,c:给定样本的标记分布集是D= 到所规定的最大次数。 [D,D2…D.],D=[dd…d]表示实例x:的标 其次，当迭代结束求出所要划分的聚类和对应 记分布集，d表示标记y对实例x:的描述度。基于 的均值向量后，便可以依据标记分布与训练样本集 此，标记分布学习的一个训练集能够表示为 的对应关系得到标记分布的簇划分和标记分布每 S={(x1,D1),(x2,D2),…,(xn,Dn)}。 个簇的均值向量“。同时利用常用的距离计算公式 目前的标记分布学习算法的输出模型是一个 “闵可夫斯基距离”公式，即 最大嫡模型)： dist(x,s)=(∑lxn-xP） (6) pl:0)=zn(0,✉） (1) 求得测试集每个样本与各个簇的均值向量的距离 式中：Z=∑exp(∑0wf(x)）是归一化因数；9。 矩阵T。闵可夫斯基距离是欧式距离的推广，具有 广泛的应用，当p=1时是曼哈顿距离，p=2就是欧 是模型参数；f(x)是x的第j个特征。随着标记分 布的发展逐渐提出许多基于式(1)的标记分布学习 式距离，而当p趋于无穷大时就是切比雪夫距离。 方法[7,9-o。这些算法先通过条件概率建立参数模 本文中将距离矩阵T的每个元素求倒数再通过一 个softmax函数进行处理转换，从而得到从训练集样 型，再利用现有的模型求解参数日。 本的标记分布的均值向量转化为预测标记分布的 2 基于k-means的标记分布学习算法 权重矩阵。对矩阵T作以下处理，先对T中每个元 素求导数： k-means算法是所有聚类算法中简单常用的一 种算法[0。它假设聚类结构能被一组原型刻画，先 1 (7) 初始化一组原型，然后对原型进行迭代更新求解， 然后，为了尽量减小与测试样本实例距离较远 最终得到每一个簇的均值向量。给定训练集H= 的均值向量的影响和便于之后的计算，利用softmax [x1x2…xm],m为训练集样本数。k-means算法针 对聚类所得簇划分G={C,C2,…,C},最小化平方 exp(x:) 函数Zk=softmax(xg)= 再作以下 误差为 ∑ep() E=Σ∑Ix-:I 处理： (2 exp(T') W。= a=1,2,…,n (8) 人∑x是簇C,的均值向量。直观来 式中：u:=C2 exp(T'au) 6=1 看，式(2)在一定程度上刻画了簇内样本围绕簇均 式中：n是测试集样本实例数，W为最后预测标记分 值向量的紧密程度，E值越小则簇内样本相似度越 布所使用的权重矩阵。数 ｄ ｙ ｘ∈ [０，１] ，进一步假设所有标记能够完整地描 述实例，则 ∑ｙ ｄ ｙ ｘ ＝ １。 标记分布学习是一种更为灵活复杂的标记学 习范式，然而学习中更好的灵活性通常意味着更大 的输出空间［１９］ 。 从单标记学习到多标记学习，再到 标记分布学习，学习过程的输出空间的维度变得越 来越大。 更为详细地，对于标记集合中有 ｃ 个不同 标记的学习问题，单标记学习的分类器有 ｃ 个可能 的输出，多标记学习的分类器有 ２ ｃ －１ 个可能的输 出。 对标记分布学习的分类器来讲，只要在满足 ｄ ｙ ｘ∈ [０，１] 和 ∑ｙ ｄ ｙ ｘ ＝ １ 这两个约束条件的前提下， 它的输出空间的维度可能是无穷大的［１９］ 。 标记 分 布 学 习 定 义 的 实 例 矩 阵 为 Ｘ ＝ ｘ１ ｘ２… ｘｎ [ ] ，ｘｉ∈Ｒ ｄ 表示第 ｉ 个实例，ｉ ＝ １，２，…，ｎ。 给定对应标记矩阵 Ｙ ＝ ｙ１ ｙ２… ｙｃ [ ] ，ｙｊ 表示第 ｊ 个 标记， ｊ ＝ １，２，…，ｃ；给定样本的标记分布集是 Ｄ ＝ Ｄ１ Ｄ２… Ｄｎ [ ] ，Ｄｉ ＝ ｄ ｙ１ ｘｉ ｄ ｙ２ ｘｉ … ｄ ｙｃ ｘｉ [ ] 表示实例 ｘｉ 的标 记分布集，ｄ ｙｊ ｘｉ表示标记 ｙｊ 对实例 ｘｉ 的描述度。 基于 此， 标 记 分 布 学 习 的 一 个 训 练 集 能 够 表 示 为 Ｓ ＝ （ｘ１ ，Ｄ１ ），（ｘ２ ，Ｄ２ ），…，（ｘ { ｎ ，Ｄｎ ）} 。 目前的标记分布学习算法的输出模型是一个 最大熵模型［７］ ： ｐ（ｙ ｘ；θ） ＝ １ Ｚ ｅｘｐ ∑ ｊ θｙ，ｊ ｆ ( ｊ（ｘ） ) （１） 式中： Ｚ ＝ ∑ｙ ｅｘｐ ∑ ｊ θｙ，ｊ ｆ ( ｊ（ｘ） ) 是归一化因数；θｙ，ｊ 是模型参数； ｆ ｊ（ｘ） 是 ｘ 的第 ｊ 个特征。 随着标记分 布的发展逐渐提出许多基于式（１） 的标记分布学习 方法［７，９－１０］ 。 这些算法先通过条件概率建立参数模 型，再利用现有的模型求解参数 θ。 ２ 基于 ｋ⁃ｍｅａｎｓ 的标记分布学习算法 ｋ－ｍｅａｎｓ 算法是所有聚类算法中简单常用的一 种算法［２０］ 。 它假设聚类结构能被一组原型刻画，先 初始化一组原型，然后对原型进行迭代更新求解， 最终得到每一个簇的均值向量。 给定训练集 Ｈ ＝ ｘ１ ｘ２… ｘｍ [ ] ，ｍ 为训练集样本数。 ｋ⁃ｍｅａｎｓ 算法针 对聚类所得簇划分 Ｇ ＝ Ｃ１ ，Ｃ２ ，…，Ｃｋ { } ，最小化平方 误差为 Ｅ ＝ ∑ ｋ ｉ ＝ １ ∑ｘ∈Ｃｉ ‖ｘ － μｉ‖２ ２ （２） 式中： μｉ ＝ １ Ｃｉ ∑ｘ∈Ｃｉ ｘ 是簇 Ｃｉ 的均值向量。 直观来 看，式（２） 在一定程度上刻画了簇内样本围绕簇均 值向量的紧密程度，Ｅ 值越小则簇内样本相似度越 高。 最小化式（２） 并不容易，找到其最优解需考察 训练集 Ｈ 所有可能的簇划分，这是一个 ＮＰ 难［２０－２１］ 的问题。 因此，ｋ⁃ｍｅａｎｓ 算法采用了贪心策略，通过 迭代优化来近似求解式（２）。 首先，聚类过程中在 Ｈ 中随机选择 ｋ 个样本作 为初始均值向量 μ１ ，μ２ ，…，μｋ { } ，可以通过下式： ｄｊｉ ＝ ‖ｘｊ － μｉ‖２ （３） 计算训练集样本 ｘｊ 与各均值向量 μｉ（ ｉ ＝ １，２，…，ｋ） 的距离。 根据距离最近的均值向量确定 ｘｊ 的簇 标记： λｊ ＝ ａｒｇ ｍｉｎｉ∈［１，２，…，ｋ］ ｄｊｉ （４） 式中 λｊ∈(１，２，…，ｋ) 表示样本 ｘｊ 的簇标记。 将样 本 ｘｊ 划入相应的簇，即 Ｃλｊ ＝ Ｃλｊ ∪ ［ｘｊ］ （５） 更新簇 Ｃλｊ的均值向量。 式（３） ～ 式（５）这个过程不 断迭代直到当前均值向量保持不变或迭代次数达 到所规定的最大次数。 其次，当迭代结束求出所要划分的聚类和对应 的均值向量后，便可以依据标记分布与训练样本集 的对应关系得到标记分布的簇划分和标记分布每 个簇的均值向量 ｕ。 同时利用常用的距离计算公式 “闵可夫斯基距离”公式，即 ｄｉｓｔｍｋ（ｘｉ，ｘｊ） ＝ ∑ ｎ ｕ ＝ １ ｘｉｕ － ｘｊｕ ｐ ( ) １ ｐ （６） 求得测试集每个样本与各个簇的均值向量的距离 矩阵 Ｔ。 闵可夫斯基距离是欧式距离的推广，具有 广泛的应用，当 ｐ ＝ １ 时是曼哈顿距离，ｐ ＝ ２ 就是欧 式距离，而当 ｐ 趋于无穷大时就是切比雪夫距离。 本文中将距离矩阵 Ｔ 的每个元素求倒数再通过一 个 ｓｏｆｔｍａｘ 函数进行处理转换，从而得到从训练集样 本的标记分布的均值向量转化为预测标记分布的 权重矩阵。 对矩阵 Ｔ 作以下处理，先对 Ｔ 中每个元 素求导数： Ｔ′ａｂ ＝ １ Ｔａｂ （７） 然后，为了尽量减小与测试样本实例距离较远 的均值向量的影响和便于之后的计算，利用 ｓｏｆｔｍａｘ 函数 Ｚｋ ＝ ｓｏｆｔｍａｘ（ｘｋ） ＝ ｅｘｐ（ｘｋ） ∑ ｋ ｉ ＝ １ ｅｘｐ（ｘｉ） 再作以下 处理： Ｗａ ＝ ｅｘｐ（Ｔ′ａｂ） ∑ ｋ ｂ ＝ １ ｅｘｐ（Ｔ′ａｂ） ， ａ ＝ １，２，…，ｎ （８） 式中：ｎ 是测试集样本实例数，Ｗ 为最后预测标记分 布所使用的权重矩阵。 第 ３ 期 邵东恒，等：应用 ｋ⁃ｍｅａｎｓ 算法实现标记分布学习 ·３２７·