·328 智能系统学报 第12卷 最后将W与训练集对应的标记分布的均值向 8)根据式(9)得出预测标记分布P。 量矩阵U相乘，即 实验与结果分析 P=WU (9) 式中：U=[u12…u,];P就是所需要求的预测标记 在这部分，将通过实验来验证本文提出的基于 分布。 k-means的标记分布学习算法。 上述的算法过程可以通过图1的流程图来 标记分布学习算法的输出是一个标记分布，与 表示。 单标记学习的单标记输出和多标记学习的标记集 输入 输出都不同。因此，标记分布学习算法的评价方 式，应该与单标记学习和多标记学习算法不同。这 [选择初始均值向量 种方式不是通过预测标记的准确度来评价算法优 计算样本与均值向量的距离 劣，而是通过测量预测结果和真实标记分布之间的 划分样本筷 距离或相似度来衡量算法效果。有很多测量概率 分布之间的距离或相似度的方法)可以用来很好 更新均值向量 地测量标记分布之间的距离或相似度。例如，表1 <是否更新一 Y 中根据文献[7]和[22]选出的5种测量方式就能很 N 好地用来评价标记分布算法。评价标准距离名称 样本到均值向量的距离矩阵 之后的“↓”代表距离值越小越好，相似度名称之后 预测标记分布权重矩阵 的“↑”表示相似值越大越好。这5种评价方法分 别是切比雪夫距离(Chebyshev)、克拉克距离 (输出预测标记分布○ (Clark)、堪培拉量度(Canberra)、弦系数(Cosine)以 图1 LDLKM算法流程图 及交叉相似性(Intersection),前3种以距离作为评 Fig.1 The flowchart of LDLKM 价，即越小越好，后两种以相似度作为评价，即越大 本文提出的LDLKM算法具体步骤如下： 越好。 算法基于k-means算法的标记分布学习 表1评价指标 (LDLKM)。 Table 1 Evaluation index 输入聚类的簇数k,聚类迭代的最大次数d,闵可 评价标准 计算形式 夫斯基距离参数P,训练集S={(x1,D),(x2,D2),…, Chebyshev↓ (x,D) Dis,=maxdd 输出测试集的预测标记分布P。 1)从训练集样本H中随机选择k个样本作为 (d,-4,)月 Clark↓ Dis,= 初始向量{u1,u2,…,“}。 V(d.d) 2)迭代开始，令C,(1≤i≤k)为空，利用式(3)】 计算样本x与各均值向量u:的距离。 Canberra↓ 3)依据式(4)，根据距离最近的均值向量确定 ,=刻 d,d x的簇标记入；将样本x,划入相应的簇。 4)更新均值向量，分别计算划分完簇后的新的 ∑4d Cosine Dis, 均简向量：，向三。 √G√∑话 5)若当前的均值向量均未更新或达到规定的 Intersection↑ Dis5=∑i.1min(d,d） 最大迭代次数，继续下一步：否则，返回2)，重复3) 到5)直到所有测法样本划分完毕。 3.1实验设置 6)依据式(6)求得测试集每个样本与各个均值 通过上述5种评价方式，本次实验在6个公开 向量的距离矩阵T。 的数据集上进行，它们分别是Yeast-.alpha、Yeast- 7)利用式(7)和式(8)求得预测标记分布的权 cdc、Yeast--elu、SJAFFE、Human Gene和Movie,详 重矩阵W。 细的信息如表2所示。最后将 Ｗ 与训练集对应的标记分布的均值向 量矩阵 Ｕ 相乘，即 Ｐ ＝ ＷＵ （９） 式中：Ｕ ＝ ［ｕ１ ｕ２… ｕｂ］；Ｐ 就是所需要求的预测标记 分布。 上述的算法过程可以通过图 １ 的流程图来 表示。 图 １ ＬＤＬＫＭ 算法流程图 Ｆｉｇ．１ Ｔｈｅ ｆｌｏｗｃｈａｒｔ ｏｆ ＬＤＬＫＭ 本文提出的 ＬＤＬＫＭ 算法具体步骤如下： 算法 基 于 ｋ⁃ｍｅａｎｓ 算 法 的 标 记 分 布 学 习 （ＬＤＬＫＭ）。 输入 聚类的簇数 ｋ，聚类迭代的最大次数 ｄ，闵可 夫斯基距离参数 ｐ，训练集 Ｓ ＝｛（ｘ１，Ｄ１ ），（ｘ２，Ｄ２ ），…， （ｘｎ，Ｄｎ）｝。 输出 测试集的预测标记分布 Ｐ。 １）从训练集样本 Ｈ 中随机选择 ｋ 个样本作为 初始向量 μ１ ， μ２ ， …， μｋ { } 。 ２）迭代开始，令 Ｃｉ（１≤ｉ≤ｋ）为空，利用式（３） 计算样本 ｘｊ 与各均值向量 μｉ 的距离。 ３）依据式（４），根据距离最近的均值向量确定 ｘｊ 的簇标记 λｊ；将样本 ｘｊ 划入相应的簇。 ４）更新均值向量，分别计算划分完簇后的新的 均值向量： μｉ ＝ １ Ｃｉ ∑ｘ∈Ｃｉ ｘ。 ５）若当前的均值向量均未更新或达到规定的 最大迭代次数，继续下一步；否则，返回 ２），重复 ３） 到 ５）直到所有测法样本划分完毕。 ６）依据式（６）求得测试集每个样本与各个均值 向量的距离矩阵 Ｔ。 ７）利用式（７）和式（８）求得预测标记分布的权 重矩阵 Ｗ。 ８）根据式（９）得出预测标记分布 Ｐ。 ３ 实验与结果分析 在这部分，将通过实验来验证本文提出的基于 ｋ⁃ｍｅａｎｓ 的标记分布学习算法。 标记分布学习算法的输出是一个标记分布，与 单标记学习的单标记输出和多标记学习的标记集 输出都不同。 因此，标记分布学习算法的评价方 式，应该与单标记学习和多标记学习算法不同。 这 种方式不是通过预测标记的准确度来评价算法优 劣，而是通过测量预测结果和真实标记分布之间的 距离或相似度来衡量算法效果。 有很多测量概率 分布之间的距离或相似度的方法［７］ 可以用来很好 地测量标记分布之间的距离或相似度。 例如，表 １ 中根据文献［７］和［２２］选出的 ５ 种测量方式就能很 好地用来评价标记分布算法。 评价标准距离名称 之后的“↓”代表距离值越小越好，相似度名称之后 的“↑”表示相似值越大越好。 这 ５ 种评价方法分 别是 切 比 雪 夫 距 离 （ Ｃｈｅｂｙｓｈｅｖ ）、 克 拉 克 距 离 （Ｃｌａｒｋ）、堪培拉量度（Ｃａｎｂｅｒｒａ）、弦系数（Ｃｏｓｉｎｅ）以 及交叉相似性（ Ｉｎｔｅｒｓｅｃｔｉｏｎ），前 ３ 种以距离作为评 价，即越小越好，后两种以相似度作为评价，即越大 越好。 表 １ 评价指标 Ｔａｂｌｅ １ Ｅｖａｌｕａｔｉｏｎ ｉｎｄｅｘ 评价标准 计算形式 Ｃｈｅｂｙｓｈｅｖ ↓ Ｄｉｓ１ ＝ｍａｘ ｌ ｄｌ －ｄ ∧ ｌ Ｃｌａｒｋ ↓ Ｄｉｓ２ ＝ ∑ｃ ｌ＝ １ （ｄｌ －ｄ ∧ ｌ） ２ （ｄｌ，ｄ ∧ ｌ） ２ Ｃａｎｂｅｒｒａ ↓ Ｄｉｓ３ ＝ ∑ ｃ ｌ ＝ １ ｄｌ － ｄｌ ∧ ｄｌ ＋ ｄｌ ∧ Ｃｏｓｉｎｅ ↑ Ｄｉｓ４ ＝ ∑ ｃ ｌ ＝ １ ｄｌ ｄｌ ∧ ∑ ｃ ｌ ＝ １ ｄ ２ ｌ ∑ ｃ ｌ ＝ １ ｄ ２ ｌ ∧ Ｉｎｔｅｒｓｅｃｔｉｏｎ ↑ Ｄｉｓ５ ＝∑ｃ ｌ＝ １ｍｉｎ（ｄｌ，ｄｌ ∧ ） ３．１ 实验设置 通过上述 ５ 种评价方式，本次实验在 ６ 个公开 的数据集上进行，它们分别是 Ｙｅａｓｔ⁃ａｌｐｈａ、 Ｙｅａｓｔ⁃ ｃｄｃ、 Ｙｅａｓｔ⁃ｅｌｕ、 ＳＪＡＦＦＥ、 Ｈｕｍａｎ Ｇｅｎｅ 和 Ｍｏｖｉｅ，详 细的信息如表 ２ 所示。 ·３２８· 智 能 系 统 学 报 第 １２ 卷