第16卷第3期 智能系统学报 Vol.16 No.3 2021年5月 CAAI Transactions on Intelligent Systems May 2021 D0:10.11992/tis.202001027 三角距离相关性的标签分布学习 黄雨婷，徐媛媛，张恒汝，闵帆 (西南石油大学计算机科学学院，四川成都610500) 摘要：针对标签相关性的表征问题，提出一种基于三角距离相关性的标签分布学习算法。首先，构建距离映 射矩阵，描述标签分布和特征矩阵之间的映射关系。其次，设计新的三角距离，以表征标签之间的相关性。最 后，结合标签相关性，设计基于Kullback-Leibler散度的目标函数。在8个数据集上的实验结果表明，与8种主 流算法相比，本文提出的算法在6个准确性指标上占优势。 关键词：标签分布学习：标签相关性；三角距离：距离映射矩阵：多标签学习：最大嫡模型：Kullback-Leibler散 度：L-BFGS方法 中图分类号：TP391文献标志码：A 文章编号：1673-4785(2021)03-0449-10 中文引用格式：黄雨婷，徐媛媛，张恒汝，等.三角距离相关性的标签分布学习W.智能系统学报，2021,16(3)：449-458. 英文引用格式：HUANG Yuting,XU Yuanyuan,ZHANG Hengru,etal.Label distribution learning based on triangular distance correlation[J.CAAI transactions on intelligent systems,2021,16(3):449-458. Label distribution learning based on triangular distance correlation HUANG Yuting,XU Yuanyuan,ZHANG Hengru,MIN Fan (College of Computer Science,Southwest Petroleum University,Chengdu 610500,China) Abstract:Aiming at the representation problem of label correlation,a label distribution learning algorithm based on tri- angular distance correlation is proposed in this paper.First,a distance-mapping matrix is constructed to describe the mapping relationship between the label distribution and the feature matrix.Then a new triangle distance is designed to characterize the correlation between the labels.Finally,based on the label correlation,the Kullback-Leibler divergence- based objective function is designed.Results on eight datasets show that the proposed algorithm is superior in six evalu- ation measures in terms of accuracy compared with eight mainstream algorithms. Keywords:label distribution learning;label correlation;triangular distance;distance mapping matrix;multi-label learn- ing;maximum entropy model;Kullback-Leibler divergence;L-BFGS method 标签分布学习(label distribution learning,LDL)提出了LDLLC(label distribution learning by exploit- 是多标签学习(muti--label earing,MLL)的泛化。 ing label correlation)算法，使用皮尔逊相关系数 MLL用标签集的部分标签来描述实例，LDL 描述了标签之间的相关性。Zheng等1提出了 用标签集所有标签的表征程度构成的分布来描述 LDL-SCL(label distribution learning by exploiting 实例2-1。文献[l2]将年龄估计问题泛化到LDL sample correlation locally)算法，考虑实例之间的相 中，降低了平均绝对误差(mean absolute deviation, 关性。后2种方法显著提高了模型对标签分布的 MAE)。文献[I3]将人群计数问题泛化到LDL中， 预测能力。 提高了人群计数的准确率。 本文提出了一种三角距离相关性的标签分布 Geng等W提出了SA-IS(specialized algorithm 学习算法(label distribution learning based on trian- improithm Iternative scaling)算法，将单个标签数据 gular distance correlation,T-LDL)o首先，令X和D 转换为分布数据，但未考虑标签的相关性。Ja等 分别表示特征矩阵和标签分布矩阵，构建距离映 射矩阵0描述X和D之间的映射关系。其次，设 收稿日期：2020-01-20. 基金项目：国家自然科学基金项目(61902328). 计新的相似度距离，以表征标签之间的相关性。 通信作者：张恒汝.E-mail:zhanghrswpu(@l63.com 最后，结合标签相关性，设计基于KL(kullback-lei-
DOI: 10.11992/tis.202001027 三角距离相关性的标签分布学习 黄雨婷，徐媛媛，张恒汝，闵帆 （西南石油大学 计算机科学学院，四川 成都 610500） 摘 要：针对标签相关性的表征问题，提出一种基于三角距离相关性的标签分布学习算法。首先，构建距离映 射矩阵，描述标签分布和特征矩阵之间的映射关系。其次，设计新的三角距离，以表征标签之间的相关性。最 后，结合标签相关性，设计基于 Kullback-Leibler 散度的目标函数。在 8 个数据集上的实验结果表明，与 8 种主 流算法相比，本文提出的算法在 6 个准确性指标上占优势。 关键词：标签分布学习；标签相关性；三角距离；距离映射矩阵；多标签学习；最大熵模型；Kullback-Leibler 散 度；L-BFGS 方法 中图分类号：TP391 文献标志码：A 文章编号：1673−4785(2021)03−0449−10 中文引用格式：黄雨婷, 徐媛媛, 张恒汝, 等. 三角距离相关性的标签分布学习 [J]. 智能系统学报, 2021, 16(3): 449–458. 英文引用格式：HUANG Yuting, XU Yuanyuan, ZHANG Hengru, et al. Label distribution learning based on triangular distance correlation[J]. CAAI transactions on intelligent systems, 2021, 16(3): 449–458. Label distribution learning based on triangular distance correlation HUANG Yuting，XU Yuanyuan，ZHANG Hengru，MIN Fan (College of Computer Science, Southwest Petroleum University, Chengdu 610500, China) Abstract: Aiming at the representation problem of label correlation, a label distribution learning algorithm based on triangular distance correlation is proposed in this paper. First, a distance-mapping matrix is constructed to describe the mapping relationship between the label distribution and the feature matrix. Then a new triangle distance is designed to characterize the correlation between the labels. Finally, based on the label correlation, the Kullback-Leibler divergencebased objective function is designed. Results on eight datasets show that the proposed algorithm is superior in six evaluation measures in terms of accuracy compared with eight mainstream algorithms. Keywords: label distribution learning; label correlation; triangular distance; distance mapping matrix; multi-label learning; maximum entropy model; Kullback-Leibler divergence; L-BFGS method 标签分布学习 (label distribution learning，LDL) 是多标签学习 (muti-label learning，MLL) 的泛化[1-8]。 MLL 用标签集的部分标签来描述实例[9-11] ，LDL 用标签集所有标签的表征程度构成的分布来描述 实例[12-15]。文献 [12] 将年龄估计问题泛化到 LDL 中，降低了平均绝对误差 (mean absolute deviation， MAE)。文献 [13] 将人群计数问题泛化到 LDL 中， 提高了人群计数的准确率。 Geng 等 [1] 提出了 SA-IIS(specialized algorithm improithm lternative scaling) 算法，将单个标签数据 转换为分布数据，但未考虑标签的相关性。Jia 等 [16] 提出了 LDLLC(label distribution learning by exploiting label correlation) 算法，使用皮尔逊相关系数 描述了标签之间的相关性。Zheng 等 [17] 提出了 LDL-SCL(label distribution learning by exploiting sample correlation locally) 算法，考虑实例之间的相 关性。后 2 种方法显著提高了模型对标签分布的 预测能力。 本文提出了一种三角距离相关性的标签分布 学习算法 (label distribution learning based on triangular distance correlation，T-LDL)。首先，令 X 和 D 分别表示特征矩阵和标签分布矩阵，构建距离映 射矩阵 θ 描述 X 和 D 之间的映射关系。其次，设 计新的相似度距离，以表征标签之间的相关性。 最后，结合标签相关性，设计基于 KL (kullback-lei- 收稿日期：2020−01−20. 基金项目：国家自然科学基金项目 (61902328). 通信作者：张恒汝. E-mail：zhanghrswpu@163.com. 第 16 卷第 3 期 智 能 系 统 学 报 Vol.16 No.3 2021 年 5 月 CAAI Transactions on Intelligent Systems May 2021
·450· 智能系统学报 第16卷 bler divergence)散度I的目标函数，利用从训练 表征度较高，{森林，沙漠}2个标签对图1(a)的表 数据直接获取的X和D拟合0以预测标签分布。 征度较低。 在8个真实数据集上，将本文提出算法与8种 主流算法进行对比实验，利用Euclidean距离I例 Sorensen距离o、Squardx距离u、KL散度u、In- tersection相似度2a和Fidelity相似度2共6种指 标进行评价。结果表明，本文提出的算法在其中 3个数据集上所有指标均为最优，在其余的数据 集上部分指标占优。 1相关工作 (a)示例图 1.0 首先提出LDL的问题描述与运行实例，然后 0.8 讨论流行的LDL算法及其目标函数。表1列出 0.6 了本文的符号系统。 0.4 表1符号系统 0.2 Table 1 Notations 符号 含义 0 森林海洋沙漠城市 森林海洋沙漠城市 R q维的输入空间 (b)多标签学习 (c)标签分布学习 上 完整标签集 图1MLL与LDL的比较 训练集 Fig.1 Differences between MLL and LDL 第个实例 表2和表3为一个标签分布学习的运行实例， d x对应的实际标签分布 分别为特征矩阵X和实际标签分布矩阵D,这里 Pi x对应的预测标签分布 S={(x1,d1),(x2,d2),…,(x4,d)},q=5,c=4。{天 Xir 第个实例的第r个特征 空，水，房屋，沙子，树木}5个特征表征了图1(a) dy 第个标签对x,的实际表征度 中包含的信息。{森林，海洋，城市，沙漠}为完整 a 距离映射矩阵 + 标签集。以加粗行为例，x1=[0.38,0.35,0.00,0.12, 特征矩阵 0.15],d1=[0.16,0.55,0.10,0.19],其中x1=0.38表 D 实际标签分布矩阵 示天空占图片面积的38%，d:=0.16表示森林描 1.1LDL问题描述 述该图片的程度为16%。 标签分布学习相对于单标签和多标签学习而 表2特征矩阵X 言，以一种更自然的方式去标记实例，并且为它 Table 2 Feature matrix X 的每个可能的标签分配一个数值。下面给出它的 特征分布 天空 水 房屋沙子 树木 形式化定义四。令X=R为q维输入空间，表示 X1 0.380.350.00 0.12 0.15 特征矩阵；Y={,2,…,}为完整标签集，c为标 0.12 0.20 0.50 0.11 0.07 签的数量；D表示实际标签分布矩阵；给定一个 X3 0.11 0.10 0.05 0.19 0.55 0.20 0.01 0.07 0.70 0.02 训练集S={XD}={x,d},{x2,d},…,{xm,dn}. 其中x,=[x1x2…x]∈X为第i个实例，d,= 表3 标签分布矩阵D [d1d2…de]∈[0，l]为x对应的实际标签分布， Table 3 Label distribution matrix D d是标签y对x的实际表征度，且d=l。 类别 森林 海洋 沙漠 城市 d 0.16 0.55 0.10 0.19 1.2运行实例 d 0.14 0.20 0.10 0.56 图1(a)为需要标记的一个示例图片2，其完 d3 0.85 0.05 0.03 0.07 整标签集为{森林，海洋，沙漠，城市}。图1b)表明 0.10 0.05 0.76 0.09 MLL中仅有{海洋，城市}2个标签能够描述图l(a)。 X和D之间的映射关系可以通过距离映射矩 图1(c)说明LDL利用这4个标签构成的分布来 阵0来描述。给定训练集后，LDL的目标为学习 描述该图片，且{海洋，城市}2个标签对图1(a)的 到该距离映射矩阵6，再通过0计算出预测标
bler divergence) 散度[18] 的目标函数，利用从训练 数据直接获取的 X 和 D 拟合 θ 以预测标签分布。 在 8 个真实数据集上，将本文提出算法与 8 种 主流算法进行对比实验，利用 Euclidean 距离[19] 、 Sørensen 距离[20] 、Squardχ2 距离[21] 、KL 散度[18] 、Intersection 相似度[22] 和 Fidelity 相似度[23] 共 6 种指 标进行评价。结果表明，本文提出的算法在其中 3 个数据集上所有指标均为最优，在其余的数据 集上部分指标占优。 1 相关工作 首先提出 LDL 的问题描述与运行实例，然后 讨论流行的 LDL 算法及其目标函数。表 1 列出 了本文的符号系统。 表 1 符号系统 Table 1 Notations 符号 含义 R q q维的输入空间 Y 完整标签集 S 训练集 xi 第i个实例 di xi对应的实际标签分布 pi xi对应的预测标签分布 xir 第i个实例的第r个特征 dij 第j个标签对xi的实际表征度 θ 距离映射矩阵 X 特征矩阵 D 实际标签分布矩阵 1.1 LDL 问题描述 ∑c j=1 di j = 1 标签分布学习相对于单标签和多标签学习而 言，以一种更自然的方式去标记实例，并且为它 的每个可能的标签分配一个数值。下面给出它的 形式化定义[1]。令 X = R q 为 q 维输入空间，表示 特征矩阵；Y = {y1 , y2 , …, yc}为完整标签集，c 为标 签的数量；D 表示实际标签分布矩阵；给定一个 训练集 S = {X, D} = {{x1 , d1}, {x2 , d2},…,{xn , dn}}， 其中 xi = [xi 1 xi 2 … xi q ]∈X 为第 i 个实例， di = [di1 di2 … dic]∈[0,1]c 为 xi 对应的实际标签分布， dij 是标签 yj 对 xi 的实际表征度，且 。 1.2 运行实例 图 1(a) 为需要标记的一个示例图片[24] ，其完 整标签集为{森林，海洋，沙漠，城市}。图 1(b) 表明 MLL 中仅有{海洋，城市}2 个标签能够描述图 1(a)。 图 1(c) 说明 LDL 利用这 4 个标签构成的分布来 描述该图片，且{海洋，城市}2 个标签对图 1(a) 的 表征度较高，{森林，沙漠}2 个标签对图 1(a) 的表 征度较低。 (a) 示例图 森林 海洋 沙漠 城市 0 1 dij dij 森林 海洋 沙漠 城市 1.0 0.8 0.6 0.4 0.2 0 (b) 多标签学习 (c) 标签分布学习 图 1 MLL 与 LDL 的比较 Fig. 1 Differences between MLL and LDL 表 2 和表 3 为一个标签分布学习的运行实例， 分别为特征矩阵 X 和实际标签分布矩阵 D，这里 S = {(x1 ,d1 ), (x2 , d2 ), …, (x4 , d4 )}，q = 5，c = 4。{天 空，水，房屋，沙子，树木}5 个特征表征了图 1(a) 中包含的信息。{森林，海洋，城市，沙漠}为完整 标签集。以加粗行为例，x1 = [0.38, 0.35, 0.00, 0.12, 0.15]，d1 = [0.16, 0.55, 0.10, 0.19]，其中 x11 = 0.38 表 示天空占图片面积的 38%，d11 = 0.16 表示森林描 述该图片的程度为 16%。 表 2 特征矩阵 X Table 2 Feature matrix X 特征分布 天空 水 房屋 沙子 树木 x1 0.38 0.35 0.00 0.12 0.15 x2 0.12 0.20 0.50 0.11 0.07 x3 0.11 0.10 0.05 0.19 0.55 x4 0.20 0.01 0.07 0.70 0.02 表 3 标签分布矩阵 D Table 3 Label distribution matrix D 类别 森林 海洋 沙漠 城市 d1 0.16 0.55 0.10 0.19 d2 0.14 0.20 0.10 0.56 d3 0.85 0.05 0.03 0.07 d4 0.10 0.05 0.76 0.09 X 和 D 之间的映射关系可以通过距离映射矩 阵 θ 来描述。给定训练集后，LDL 的目标为学习 到该距离映射矩阵 θ [16] ，再通过 θ 计算出预测标 ·450· 智 能 系 统 学 报 第 16 卷
第3期 黄雨婷，等：三角距离相关性的标签分布学习 ·451· 签分布矩阵P={p,p2,…,p},其中p,=[papn d P,Pg为标签y对x,的预测表征度，该表征度用 0=arg min (2) p(vix:0) 最大嫡模型的表示，如式(1)所示： 1.3 已有的LDL算法 表4列出了4种流行的LDL算法及其目标函 pyx;)月 (1) 数，表中第一行的SA-IS和SA-BFGS(special- 2n②a ized algorithm effective quasi-newton)两种算法使 用相同的目标函数，它们均采用KL散度表征所 为优化求解0，LDL算法的目标函数需约束 有实例的真实分布与预测分布之间的差异。前者 预测分布与真实分布之间的差异。文献[]构建 使用类似于改进迭代缩放的策略作为其优化方 了以KL散度为基础的目标函数，通过求解式 法，后者使用BFGS算法作为其优化方法。该目 (2),可得到最优距离映射矩阵0，即 标函数缺少正则项，易导致欠拟合。 表4已有的4种流行的LDL算法及其目标函数 Table 4 Objective functions of four popular LDL algorithms 方法 目标函数 d SA-IS、SA-BFGSIM 0=argmin =1 p6y;) LDLLCI6 0=argmin d p: ）+hIo啡+2∑sn(Pdis） =1=1 EDLP网 =argmin2(du-p) 台台a+p0: wxe,-0tl旧 n k=1=1 =1j1k= LDLLC1在IS-LLD算法的目标函数基础上 本文设计的目标函数为 增加了正则项和标签相关性项。如表4中第2行 所示，等号右边第2项为距离映射矩阵0的F-范 ro-(3) 数，以防止过拟合。第3项为符号函数与不同距 式中：等号右侧第1项用KL散度表征所有实例 离共同决定的标签相关性项，其中符号函数由皮 的真实分布与预测分布之间的差异；等号右侧第 尔逊相关系数决定。但皮尔逊相关系数存在 二项为本文亮点，设计标签相关性项以获得更好 “2个输入向量间应有线性关系”的约束条件，而 的预测结果。 距离映射矩阵0中的任意2个向量要满足该条件 2.1 标签相关性 较为困难。 本文的亮点为结合三元相关性和距离相关性 EDL(emotion distribution learning from 来描述标签之间的相关性，如式(4)所示： texts)2通过采用新散度公式表征所有实例的真 n(0.0）=sgn(triangle(0,0)-Dis(0,0）(4) 实分布与预测分布之间的差异，并增加2个约束 式中：sgn(triangle(0,0)表征三元相关性，Dis(0: 项。如表4中第3行所示，等号右边第2项为距 0)表征距离相关性。sgn(triangle(0,0)》用三角距 离映射矩阵0的1-范数，以防止过拟合。第3项 离来表征标签之间存在何种相关性，即正相关 用不同标签的特征向量之差的2-范数，再乘以基 不相关或负相关；Dis(0,O)用Euclidean距离9表 于Plutchik的情绪轮得到的权重，表征不同标签 征标签之间的相关程度。 之间的关系。该算法在情绪分类场景下表现 由于使用皮尔逊相关系数时需要考虑任意 较好。 2个向量是否存在线性关系，故提出一种不考虑 该约束条件的新三角距离来衡量2个向量是否相 2本文工作 关。这里，仅考虑2个向量0g以及2个向量之差0-0， 设计该三角距离，且使得其取值范围为[-1,1]，如 常见的LDL算法的输入为特征矩阵X与实 式（⑤）所示： 际标签分布矩阵D,输出为预测标签分布矩阵P, 构建距离映射矩阵0描述X和D之间的映射关 0-0)2 系。为了得到更精准的预测标签分布矩阵P,设 triangle(,） 计目标函数是LDL算法工作的重点。本节重点介 绍如何设计目标函数以及本文提出的T-LDL算法
签分布矩阵 P = {p1 , p2 , …, pi}，其中 pi = [pi1 pi2 … pic]，pij 为标签 yj 对 xi 的预测表征度，该表征度用 最大熵模型[25] 表示，如式 (1) 所示： p(yj |xi ;θ)= exp ∑q r=1 θkr xir ∑c k=1 exp ∑q r=1 θkr xir (1) 为优化求解 θ，LDL 算法的目标函数需约束 预测分布与真实分布之间的差异。文献 [1] 构建 了以 KL 散度为基础的目标函数，通过求解式 (2)，可得到最优距离映射矩阵 θ * ，即 θ ∗= argmin θ ∑n i=1 ∑c j=1 ( di j ln di j p ( yj |xi ;θ ) ) (2) 1.3 已有的 LDL 算法 表 4 列出了 4 种流行的 LDL 算法及其目标函 数，表中第一行的 SA-IIS[1] 和 SA-BFGS(specialized algorithm effective quasi-newton)[1] 两种算法使 用相同的目标函数，它们均采用 KL 散度表征所 有实例的真实分布与预测分布之间的差异。前者 使用类似于改进迭代缩放的策略作为其优化方 法，后者使用 BFGS 算法作为其优化方法。该目 标函数缺少正则项，易导致欠拟合。 表 4 已有的 4 种流行的 LDL 算法及其目标函数 Table 4 Objective functions of four popular LDL algorithms 方法 目标函数 SA-IIS、SA-BFGS[1] θ ∗= argmin θ ∑n i=1 ∑c j=1 ( di j ln di j p ( yj |xi ;θ ) ) LDLLC[16] θ ∗= argmin θ ∑c j=1 ( di j ln di j p ( yj |xi ;θ ) ) +λ1 ||θ||2 F +λ2 ∑c i=1 ∑c j=1 sgn(ρθi,θj )dis(ρθi,θj ) EDL[26] θ ∗= argmin θ 2 ∑n i=1 ∑c j=1 (di j − p(yj |xi ;θ))2 (di j + p(yj |xi ;θ))2 + λ1 n ∑c k=1 ∑q r=1 |θkr|1+ λ2 n ∑c u=1 ∑q j=1 ∑q k=1 ωjk||θu j −θuk||2 2 LDLLC[16] 在 IIS-LLD 算法的目标函数基础上 增加了正则项和标签相关性项。如表 4 中第 2 行 所示，等号右边第 2 项为距离映射矩阵 θ 的 F-范 数，以防止过拟合。第 3 项为符号函数与不同距 离共同决定的标签相关性项，其中符号函数由皮 尔逊相关系数决定。但皮尔逊相关系数存在 “2 个输入向量间应有线性关系”的约束条件，而 距离映射矩阵 θ 中的任意 2 个向量要满足该条件 较为困难。 EDL(emotion distribution learning from texts)[26] 通过采用新散度公式表征所有实例的真 实分布与预测分布之间的差异，并增加 2 个约束 项。如表 4 中第 3 行所示，等号右边第 2 项为距 离映射矩阵 θ 的 1-范数，以防止过拟合。第 3 项 用不同标签的特征向量之差的 2-范数，再乘以基 于 Plutchik 的情绪轮得到的权重，表征不同标签 之间的关系。该算法在情绪分类场景下表现 较好。 2 本文工作 常见的 LDL 算法的输入为特征矩阵 X 与实 际标签分布矩阵 D，输出为预测标签分布矩阵 P， 构建距离映射矩阵 θ 描述 X 和 D 之间的映射关 系。为了得到更精准的预测标签分布矩阵 P，设 计目标函数是 LDL 算法工作的重点。本节重点介 绍如何设计目标函数以及本文提出的 T-LDL 算法。 本文设计的目标函数为 T(θ) = ∑n i=1 ∑c j=1 ( di j ln di j p ( yj |xi ;θ ) ) +λ1 ∑c i=1 ∑c j=1 η ( θi ,θj ) (3) 式中：等号右侧第 1 项用 KL 散度表征所有实例 的真实分布与预测分布之间的差异；等号右侧第 二项为本文亮点，设计标签相关性项以获得更好 的预测结果。 2.1 标签相关性 本文的亮点为结合三元相关性和距离相关性 来描述标签之间的相关性，如式 (4) 所示： η ( θi ,θj ) = sgn(triangle ( θi ,θj ) )·Dis( θi ,θj ) (4) 式中：sgn(triangle(θi , θj )) 表征三元相关性，Dis(θi , θj ) 表征距离相关性。sgn(triangle(θi , θj )) 用三角距 离来表征标签之间存在何种相关性，即正相关、 不相关或负相关；Dis(θi , θj ) 用 Euclidean 距离[19] 表 征标签之间的相关程度。 由于使用皮尔逊相关系数时需要考虑任意 2 个向量是否存在线性关系，故提出一种不考虑 该约束条件的新三角距离来衡量 2 个向量是否相 关。这里，仅考虑2个向量θi、θj以及2个向量之差θi−θj， 设计该三角距离，且使得其取值范围为 [−1,1]，如 式 (5) 所示： triangle ( θi ,θj ) = 1− 2 √∑m k=1 (θik −θjk) 2 √∑m k=1 θik 2 + √∑m k=1 θjk 2 (5) 第 3 期 黄雨婷，等：三角距离相关性的标签分布学习 ·451·
·452· 智能系统学报 第16卷 将该三角距离代入符号函数，用于判断标签 表5数据集 之间存在何种相关性：正相关、不相关或负相关。 Table 5 Datasets 1, 0<triangle(a,0)≤1 数据集名称 实例个数 特征个数 标签个数 sgn (triangle(,0))= 0.triangle(00)=0 Alpha 2465 24 18 -1,-1 triangle(0.0)<0 (6) Cdc 2465 24 15 式中，sgn()为1、0、-1分别表示标签之间为正相 Elu 2465 24 关、不相关或负相关。 Diau 2465 24 > 由于上述部分只能判断标签之间存在何种相 Heat 2465 24 6 关性，并不能判断标签之间的相关程度，故引入 Euclidean距离9表示标签之间的相关程度： Spo 2465 24 6 Cold 2465 24 4 Dis(0,0) (0k-0)月 (7) Dtt 2465 24 4 2.2本文提出的T-LDL算法 Alpha数据集记录在a因子的影响下酵母在 T-LDL描述见算法1。首先将距离映射矩阵 有丝分裂期间的基因表达情况；Cdc数据集记录 0和逆拟Hessian矩阵Bo初始化为单位矩阵， 酵母在细胞分裂期间停滞的cdc-l5基因表达情 再通过式(3)计算初次目标函数的梯度7T(0。 况：E山数据集记录酵母经离心淘洗后的基因表 进入迭代，收敛条件为7T0<。当不满足收 敛条件时，采用L-BFGS方法P1优化并更新0和 达情况；Diau数据集记录酵母在双峰转换过程中 的基因表达情况：Heat数据集记录酵母在经过高 B。当满足收敛条件时，计算标签y,对x,的预测 温冲击后的基因表达情况；Spo数据集记录酵母 表征度p,)。 算法1T-LDL算法 在孢子形成过程中的基因表达情况：Cold数据集 输入XD,: 记录酵母经低温处理后的基因表达情况；D壮数据 输出p0k;)。 集记录酵母经还原剂处理后的基因表达情况。 1)初始化距离映射矩阵g和逆拟Hessian矩 3.2评价指标 阵B; 表6列出了评估LDL算法的6个评价指标的 2)通过式(3)计算梯度vTd； 名称和公式。其中，P是标签y对x的预测表征 3)如果lvT(0)l2>5,使用L-BFGS方法2列 度；d是标签y对x,的实际表征度；“」”表示“越 优化更新0和B: 小越好”；“↑”表示“越大越好”。 4)end if; 表6LDL算法的评价指标 5)1←-1+1： Table 6 Evaluation measures for the LDL algorithms 6)通过式(1)计算py:0)。 指标名称 公式 3实验及结果分析 Euclidean dis (Pu-di)2 本节首先介绍实验使用的8个数据集和6个 评价指标，再将本文提出的T-LDL算法与 Slp-dd LDLLC6、PT-Bayes!、PT-SVM,1I、AA-kNN,J Sorensen dis= AA-Bpl、SA-llS,1o、SA-BFGS(specialized al-- 2w+ gorithm effective quasi--newton)l,】和EDL26l 8种主流的LDL算法进行比较，最后对实验结果 Squard dis=pu-du) 进行讨论。 台p%+d西 3.1数据集 Kullback-Leibler (KL) dis=∑pw d 表5列出了从芽殖酵母的8个生物学实验中 收集得到的8个真实数据集2。实例为2465个 Intersection sim=∑nmin(pd) 酵母基因，特征是长度为24的系统发育谱，标签 1 为不同生物实验中的离散时间点，数量范围为 Fidelity sim=∑p,4 418。 =1
将该三角距离代入符号函数，用于判断标签 之间存在何种相关性：正相关、不相关或负相关。 sgn( triangle ( θi ,θj )) = 1, 0 < triangle ( θi ,θj ) ⩽ 1 0, triangle ( θi ,θj ) = 0 −1, −1 ⩽ triangle ( θi ,θj ) < 0 (6) 式中，sgn(·) 为 1、0、−1 分别表示标签之间为正相 关、不相关或负相关。 由于上述部分只能判断标签之间存在何种相 关性，并不能判断标签之间的相关程度，故引入 Euclidean 距离[19] 表示标签之间的相关程度： Dis( θi ,θj ) = tv∑m k=1 ( θik −θjk)2 (7) 2.2 本文提出的 T-LDL 算法 ∇ ∇ T-LDL 描述见算法 1。首先将距离映射矩阵 θ (0) 和逆拟 Hessian 矩阵 B (0) 初始化为单位矩阵， 再通过式 (3) 计算初次目标函数的梯度 T(θ (0))。 进入迭代，收敛条件为|| T(θ (l) )||2 < ξ。当不满足收 敛条件时，采用 L-BFGS 方法[27] 优化并更新 θ 和 B。当满足收敛条件时，计算标签 yj 对 xi 的预测 表征度 p(yj |xi ;θ)。 算法 1 T-LDL 算法 输入 X, D, ξ； 输出 p(y|x;θ)。 1) 初始化距离映射矩阵 θ (0) 和逆拟 Hessian 矩 阵 B (0) ； 2) 通过式 (3) 计算梯度 ∇ T(θ (0))； 3) 如果|| ∇ T(θ (l) )||2 > ξ，使用 L-BFGS 方法[27] 优化更新 θ 和 B； 4)end if； 5)l ← l + 1； 6) 通过式 (1) 计算 p(yj |xi ;θ)。 3 实验及结果分析 本节首先介绍实验使用的 8 个数据集和 6 个 评价指标，再将本文提出 的 T-LD L 算 法 与 LDLLC[16] 、PT-Bayes[1] 、PT-SVM[1, 17] 、AA-kNN[1, 4] 、 AA-BP[1] 、SA-IIS[1, 16] 、SA-BFGS(specialized algorithm effective quasi-newton)[ 1 , 2 ] 和 EDL[ 2 6 ] 8 种主流的 LDL 算法进行比较，最后对实验结果 进行讨论。 3.1 数据集 表 5 列出了从芽殖酵母的 8 个生物学实验中 收集得到的 8 个真实数据集[28]。实例为 2 465 个 酵母基因，特征是长度为 24 的系统发育谱，标签 为不同生物实验中的离散时间点，数量范围为 4~18。 表 5 数据集 Table 5 Datasets 数据集名称 实例个数 特征个数 标签个数 Alpha 2 465 24 18 Cdc 2 465 24 15 Elu 2 465 24 14 Diau 2 465 24 7 Heat 2 465 24 6 Spo 2 465 24 6 Cold 2 465 24 4 Dtt 2 465 24 4 Alpha 数据集记录在 α 因子的影响下酵母在 有丝分裂期间的基因表达情况；Cdc 数据集记录 酵母在细胞分裂期间停滞的 cdc-15 基因表达情 况；Elu 数据集记录酵母经离心淘洗后的基因表 达情况；Diau 数据集记录酵母在双峰转换过程中 的基因表达情况；Heat 数据集记录酵母在经过高 温冲击后的基因表达情况；Spo 数据集记录酵母 在孢子形成过程中的基因表达情况；Cold 数据集 记录酵母经低温处理后的基因表达情况；Dtt 数据 集记录酵母经还原剂处理后的基因表达情况[28]。 3.2 评价指标 表 6 列出了评估 LDL 算法的 6 个评价指标的 名称和公式。其中，pij 是标签 yj 对 xi 的预测表征 度；dij 是标签 yj 对 xi 的实际表征度；“↓”表示“越 小越好”；“↑”表示“越大越好”。 表 6 LDL 算法的评价指标 Table 6 Evaluation measures for the LDL algorithms 指标名称 公式 Euclidean[19] ↓ dis = vt∑c j=1 (pi j −di j) 2 Sørensen[20] ↓ dis = ∑c j=1 |pi j −di j| ∑c j=1 |pi j +di j| Squard χ2[21] ↓ dis = ∑c j=1 ( pi j −di j)2 pi j +di j Kullback-Leibler (KL)[18] ↓ dis = ∑c j=1 pi j ln pi j di j Intersection[22] ↑ sim = ∑c j=1 min( pi j,di j) Fidelity[29] ↑ sim = ∑c j=1 √ pi jdi j ·452· 智 能 系 统 学 报 第 16 卷
第3期 黄雨婷，等：三角距离相关性的标签分布学习 ·453· 3.3 实验结果 对于数据集Elu和Cold,本文提出的方法在 表7~14的第1~6列列出了10次实验的平均 所有评价指标上都比其他8种方法表现更好。对 结果±标准差（当前方法性能的排名），末列为前 于数据集Alpha、Cdc和Heat,本文提出的方法在 6列平均性能排名。首先比较表7~14中的平均 大多数评价指标上排名第一。对于其余3个数据 值，如果平均值相同，再比较标准差。 集，本文提出的方法排在第二或者第三。 表7 Alpha数据集上的实验结果 Table 7 Experimental results on the Alpha dataset 算法 Euclideanl Sorensenl Squard KLI Intersection Fidelity 平均值 0.0231±0.00020.0378±0.00050.0055±0.00030.0055±0.0002 0.9622±0.00050.9986±.0002 T-LDL 1.2 (1) (1) (1) (1) (1) (2) 0.0232±0.00040.0379±0.0006 0.0056±0.00030.0055±0.0003 0.9621±0.0006 0.9986±.0001 LDLLC 1.8 (2) (2) (2) (2) (2) (1) 0.22980.01240.3485±0.0154 0.3879±0.02770.5607±0.07100.6515±0.01540.8777±0.0100 PT-Bayes 9.0 (9) (9) (9) (9) (9) (9) 0.0276±0.0006 0.0445±0.0009 0.0071±0.00030.0071±0.0003 0.9565±0.00090.9981±0.0001 PT-SVM 6.0 (6 (6) (6) (6) (6) (6) 0.0279±0.0006 0.0449±0.0012 0.0073±0.00030.0074±0.00040.9561±0.00120.9980±0.0001 AA-kNN 7.2 (7) (7) (7) (8) (7) (7) 0.08710.00700.1475±0.0131 0.1399±0.05010.0073±0.00580.8538±0.01170.983940.0017 AA-BP 7.8 (8) (8) (8) (7) (8) (8) 0.0269±0.0004 0.0429±0.0012 0.0069±0.00040.0069±0.00040.9571±0.00120.9983±0.0011 SA-IIS 4.7 (5) (4) (5) (5) (4) (5) 0.0251±0.0004 0.0408±0.0011 0.0063±0.0008 0.0063±0.0004 0.9574±0.0009 0.9985±0.0011 SA-BFGS 3.0 (3) (3) (3) (3) (3) (3) 0.0260±0.0011 0.0429±0.0022 0.0067±0.0006 0.0068±0.0006 0.9570±0.0022 0.9983±0.0002 EDL 4.3 (4) (5) (4) (4) ⑤ (4) 表8Cdc数据集上的实验结果 Table 8 Experimental results on the Cde dataset 算法 Euclideanl Sorensenl Squardx KLI Intersection↑ Fidelity 平均值 0.0280±0.00030.0428±0.00070.0071±0.00050.006940.00010.9587±0.0004 0.9984±0.0002 T-LDL 1.5 (1) (2) (2) (2) (1) (1) 0.0280±0.0005 0.0427±0.00090.0071±0.00070.0067±0.00050.9573±0.0009 0.9982±0.0003 LDLLC 2.2 (2) (1) (3) (1) (2) (4) 0.239940.01030.3455±0.0111 3853±0.02100.537440.05030.6545±0.0111 0.8778±0.0075 PT-Bayes 9.0 (9) (9) (9) (9) (9) (9) 0.0298±0.00070.0458±0.00120.0077±0.00040.0076±0.00040.9554±0.00120.9980±0.0001 PT-SVM 5.8 (5) (6) (6 (6) (6) (6 0.0301±0.00090.0462±0.00130.0080±0.00040.007940.00040.9538±0.00130.9980±0.0001 AA-kNN 6.8 (7 (7) (7) (7) (7) (6) 0.076940.00810.1192±0.01090.0842±0.02810.0511±0.01210.8829±0.01340.9879±0.0051 AA-BP 8.0 (8) (8) (8) (8) (8) (8) 0.029040.00100.0445±0.00150.0073±0.00050.0072±0.00050.9556±0.00150.9982±0.0012 SA-IIS 5.0 (6) (4) (5 (5) (5) (5) 0.0284±0.00110.0449±0.00160.0070±0.00040.0070±0.00050.9558±0.00160.9983±0.0011 SA-BFGS 3.2 (4) (5) (1) (3) (4) (2) 0.0283±0.00060.0429±0.00080.0072±0.00040.0072±0.00040.9571±0.00080.9982±0.0001 EDL 3.3 (3) (3) (4) (4) (3) (3)
3.3 实验结果 表 7~14 的第 1~6 列列出了 10 次实验的平均 结果±标准差 (当前方法性能的排名)，末列为前 6 列平均性能排名。首先比较表 7~14 中的平均 值，如果平均值相同，再比较标准差。 对于数据集 Elu 和 Cold，本文提出的方法在 所有评价指标上都比其他 8 种方法表现更好。对 于数据集 Alpha、Cdc 和 Heat，本文提出的方法在 大多数评价指标上排名第一。对于其余 3 个数据 集，本文提出的方法排在第二或者第三。 表 7 Alpha 数据集上的实验结果 Table 7 Experimental results on the Alpha dataset 算法 Euclidean↓ Sørensen↓ Squard χ2 ↓ KL↓ Intersection↑ Fidelity↑ 平均值 T-LDL 0.023 1±0.000 2 (1) 0.0378±0.000 5 (1) 0.0055±0.000 3 (1) 0.0055±0.0002 (1) 0.962 2±0.0005 (1) 0.9986±.000 2 (2) 1.2 LDLLC 0.023 2±0.000 4 (2) 0.0379±0.000 6 (2) 0.0056±0.000 3 (2) 0.0055±0.0003 (2) 0.962 1±0.0006 (2) 0.9986±.000 1 (1) 1.8 PT-Bayes 0.229 8±0.012 4 (9) 0.3485±0.015 4 (9) 0.3879±0.027 7 (9) 0.5607±0.0710 (9) 0.651 5±0.0154 (9) 0.8777±0.010 0 (9) 9.0 PT-SVM 0.027 6±0.000 6 (6) 0.0445±0.000 9 (6) 0.0071±0.000 3 (6) 0.0071±0.0003 (6) 0.956 5±0.0009 (6) 0.9981±0.000 1 (6) 6.0 AA-kNN 0.027 9±0.000 6 (7) 0.0449±0.001 2 (7) 0.0073±0.000 3 (7) 0.0074±0.0004 (8) 0.956 1±0.0012 (7) 0.9980±0.000 1 (7) 7.2 AA-BP 0.087 1±0.007 0 (8) 0.1475±0.013 1 (8) 0.1399±0.050 1 (8) 0.0073±0.0058 (7) 0.853 8±0.0117 (8) 0.9839±0.001 7 (8) 7.8 SA-IIS 0.026 9±0.000 4 (5) 0.0429±0.001 2 (4) 0.0069±0.000 4 (5) 0.0069±0.0004 (5) 0.957 1±0.0012 (4) 0.9983±0.001 1 (5) 4.7 SA-BFGS 0.025 1±0.000 4 (3) 0.0408±0.001 1 (3) 0.0063±0.000 8 (3) 0.0063±0.0004 (3) 0.957 4±0.0009 (3) 0.9985±0.001 1 (3) 3.0 EDL 0.026 0±0.001 1 (4) 0.0429±0.002 2 (5) 0.0067±0.000 6 (4) 0.0068±0.0006 (4) 0.957 0±0.0022 (5) 0.9983±0.000 2 (4) 4.3 表 8 Cdc 数据集上的实验结果 Table 8 Experimental results on the Cdc dataset 算法 Euclidean↓ Sørensen↓ Squard χ2 ↓ KL↓ Intersection↑ Fidelity↑ 平均值 T-LDL 0.0280±0.0003 (1) 0.0428±0.000 7 (2) 0.007 1±0.000 5 (2) 0.006 9±0.0001 (2) 0.958 7±0.0004 (1) 0.9984±0.0002 (1) 1.5 LDLLC 0.0280±0.0005 (2) 0.0427±0.000 9 (1) 0.007 1±0.000 7 (3) 0.006 7±0.0005 (1) 0.957 3±0.0009 (2) 0.9982±0.0003 (4) 2.2 PT-Bayes 0.2399±0.0103 (9) 0.3455±0.011 1 (9) 3853±0.0210 (9) 0.537 4±0.0503 (9) 0.654 5±0.0111 (9) 0.8778±0.0075 (9) 9.0 PT-SVM 0.0298±0.0007 (5) 0.0458±0.001 2 (6) 0.007 7±0.000 4 (6) 0.007 6±0.0004 (6) 0.955 4±0.0012 (6) 0.9980±0.0001 (6) 5.8 AA-kNN 0.0301±0.0009 (7) 0.0462±0.001 3 (7) 0.008 0±0.000 4 (7) 0.007 9±0.0004 (7) 0.953 8±0.0013 (7) 0.9980±0.0001 (6) 6.8 AA-BP 0.0769±0.0081 (8) 0.1192±0.010 9 (8) 0.084 2±0.028 1 (8) 0.051 1±0.0121 (8) 0.882 9±0.0134 (8) 0.9879±0.0051 (8) 8.0 SA-IIS 0.0290±0.0010 (6) 0.0445±0.001 5 (4) 0.007 3±0.000 5 (5) 0.007 2±0.0005 (5) 0.955 6±0.0015 (5) 0.9982±0.0012 (5) 5.0 SA-BFGS 0.0284±0.0011 (4) 0.0449±0.001 6 (5) 0.007 0±0.000 4 (1) 0.007 0±0.0005 (3) 0.955 8±0.0016 (4) 0.9983±0.0011 (2) 3.2 EDL 0.0283±0.0006 (3) 0.0429±0.000 8 (3) 0.007 2±0.000 4 (4) 0.007 2±0.0004 (4) 0.957 1±0.0008 (3) 0.9982±0.0001 (3) 3.3 第 3 期 黄雨婷，等：三角距离相关性的标签分布学习 ·453·