第12卷第3期 智能系统学报 Vol.12 No.3 2017年6月 CAAI Transactions on Intelligent Systems Jun.2017 D0I:10.11992/is.201704024 网络出版地址：http:/kns.cmki.net/kcms/detail/23.1538.TP.20170704.0925.002.html 应用k-means算法实现标记分布学习 邵东恒，杨文元，赵红 (闯南师范大学粒计算重点实验室，福建漳州363000) 摘要：标记分布学习是近年来提出的一种新的机器学习范式，它能很好地解决某些标记多义性的问题。现有的标 记分布学习算法均利用条件概率建立参数模型，但未能充分利用特征和标记间的联系。本文考虑到特征相似的样 本所对应的标记分布也应当相似，利用原型聚类的k均值算法(k-meas),将训练集的样本进行聚类，提出基于 means算法的标记分布学习(label distribution learning based on-means algorithm,LDLKM)。首先通过聚类算法k: meas求得每一个簇的均值向量，然后分别求得对应标记分布的均值向量。最后将测试集和训练集的均值向量间的 距离作为权重，应用到对测试集标记分布的预测上。在6个公开的数据集上进行实验，并与3种已有的标记分布学 习算法在5种评价指标上进行比较，实验结果表明提出的LDLKM算法是有效的。 关键词：标记分布：聚类：k-means;闵可夫斯基距离；多标记：权重矩阵；均值向量；softmax函数 中图分类号：TP181文献标志码：A文章编号：1673-4785(2017)03-0325-08 中文引用格式：邵东恒，杨文元，赵红.应用k-meas算法实现标记分布学习[J].智能系统学报，2017,12(3)：325-332 英文引用格式：SHAO Dongheng,YANG Wenyuan,ZHAO Hong.Label distribution learning based on k-means algorithm[J]. CAAI transactions on intelligent systems,2017,12(3):325-332. Label distribution learning based on k-means algorithm SHAO Dongheng,YANG Wenyuan,ZHAO Hong (1.Lab of Granular Computing,Minnan Normal University,Zhangzhou 363000,China) Abstract: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,the k-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 on k-means algorithm (LDLKM) was proposed.It firstly calculated each cluster's mean vector using the k-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 Keywords:label distribution;clustering;k-means;Minkowski distance;multi-label;weight matrix;mean vector; softmax function 近年来，标记多义性问题是机器学习和数据挖 记的多标记学习(muli-label learning)[。多标记学 掘领域的热门问题。目前已有的两种比较成熟的 习是对单标记学习的拓展[)。通常多标记学习能 学习范式是对每个实例分配单个标记的单标记学 处理一个实例属于多个标记的分歧情况。通过大 习(single-label learning)和对一个实例分配多个标 量的研究和实验3表明，多标记学习是一种有效 且应用范围较广的学习范式。 收稿日期：2017-04-19.网络出版日期：2017-07-04. 基金项目：国家自然科学基金项目(61379049,61379089) 多标记学习虽然对于一个实例允许标上多个 通信作者：杨文元.E-mail:yang叮y@xmu.cdu.cm第 １２ 卷第 ３ 期 智 能 系 统 学 报 Ｖｏｌ．１２ №．３ ２０１７ 年 ６ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｊｕｎ． ２０１７ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ．２０１７０４０２４ 网络出版地址：ｈｔｔｐ： ／ ／ ｋｎｓ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１７０７０４．０９２５．００２．ｈｔｍｌ 应用 ｋ⁃ｍｅａｎｓ 算法实现标记分布学习 邵东恒，杨文元，赵红 （闽南师范大学 粒计算重点实验室，福建 漳州 ３６３０００） 摘 要：标记分布学习是近年来提出的一种新的机器学习范式，它能很好地解决某些标记多义性的问题。 现有的标 记分布学习算法均利用条件概率建立参数模型，但未能充分利用特征和标记间的联系。 本文考虑到特征相似的样 本所对应的标记分布也应当相似，利用原型聚类的 ｋ 均值算法（ ｋ⁃ｍｅａｎｓ），将训练集的样本进行聚类，提出基于 ｋ⁃ ｍｅａｎｓ 算法的标记分布学习（ ｌａｂｅｌ ｄｉｓｔｒｉｂｕｔｉｏｎ ｌｅａｒｎｉｎｇ ｂａｓｅｄ ｏｎ ｋ⁃ｍｅａｎｓ ａｌｇｏｒｉｔｈｍ，ＬＤＬＫＭ）。 首先通过聚类算法 ｋ⁃ ｍｅａｎｓ 求得每一个簇的均值向量，然后分别求得对应标记分布的均值向量。 最后将测试集和训练集的均值向量间的 距离作为权重，应用到对测试集标记分布的预测上。 在 ６ 个公开的数据集上进行实验，并与 ３ 种已有的标记分布学 习算法在 ５ 种评价指标上进行比较，实验结果表明提出的 ＬＤＬＫＭ 算法是有效的。 关键词：标记分布；聚类；ｋ－ｍｅａｎｓ；闵可夫斯基距离；多标记；权重矩阵；均值向量；ｓｏｆｔｍａｘ 函数 中图分类号：ＴＰ１８１ 文献标志码：Ａ 文章编号：１６７３－４７８５（２０１７）０３－０３２５－０８ 中文引用格式：邵东恒，杨文元，赵红．应用 ｋ⁃ｍｅａｎｓ 算法实现标记分布学习［Ｊ］． 智能系统学报， ２０１７， １２（３）： ３２５－３３２． 英文引用格式：ＳＨＡＯ Ｄｏｎｇｈｅｎｇ， ＹＡＮＧ Ｗｅｎｙｕａｎ， ＺＨＡＯ Ｈｏｎｇ． Ｌａｂｅｌ ｄｉｓｔｒｉｂｕｔｉｏｎ ｌｅａｒｎｉｎｇ ｂａｓｅｄ ｏｎ ｋ⁃ｍｅａｎｓ ａｌｇｏｒｉｔｈｍ［ Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， ２０１７， １２（３）： ３２５－３３２． Ｌａｂｅｌ ｄｉｓｔｒｉｂｕｔｉｏｎ ｌｅａｒｎｉｎｇ ｂａｓｅｄ ｏｎ ｋ⁃ｍｅａｎｓ ａｌｇｏｒｉｔｈｍ ＳＨＡＯ Ｄｏｎｇｈｅｎｇ， ＹＡＮＧ Ｗｅｎｙｕａｎ， ＺＨＡＯ Ｈｏｎｇ （１． Ｌａｂ ｏｆ Ｇｒａｎｕｌａｒ Ｃｏｍｐｕｔｉｎｇ， Ｍｉｎｎａｎ Ｎｏｒｍａｌ Ｕｎｉｖｅｒｓｉｔｙ， Ｚｈａｎｇｚｈｏｕ ３６３０００， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｌａｂｅｌ ｄｉｓｔｒｉｂｕｔｉｏｎ ｌｅａｒｎｉｎｇ ｉｓ ａ ｎｅｗ ｔｙｐｅ ｏｆ ｍａｃｈｉｎｅ ｌｅａｒｎｉｎｇ ｐａｒａｄｉｇｍ ｔｈａｔ ｈａｓ ｅｍｅｒｇｅｄ ｉｎ ｒｅｃｅｎｔ ｙｅａｒｓ． Ｉｔ ｃａｎ ｓｏｌｖｅ ｔｈｅ ｐｒｏｂｌｅｍ ｗｈｅｒｅｉｎ ｄｉｆｆｅｒｅｎｔ ｒｅｌｅｖａｎｔ ｌａｂｅｌｓ ｈａｖｅ ｄｉｆｆｅｒｅｎｔ ｉｍｐｏｒｔａｎｃｅ． Ｅｘｉｓｔｉｎｇ ｌａｂｅｌ ｄｉｓｔｒｉｂｕｔｉｏｎ ｌｅａｒｎｉｎｇ ａｌｇｏｒｉｔｈｍｓ ａｄｏｐｔ ｔｈｅ ｐａｒａｍｅｔｅｒ ｍｏｄｅｌ ｗｉｔｈ ｃｏｎｄｉｔｉｏｎａｌ ｐｒｏｂａｂｉｌｉｔｙ， ｂｕｔ ｔｈｅｙ ｄｏ ｎｏｔ ａｄｅｑｕａｔｅｌｙ ｅｘｐｌｏｉｔ ｔｈｅ ｒｅｌａｔｉｏｎ ｂｅｔｗｅｅｎ ｆｅａｔｕｒｅｓ ａｎｄ ｌａｂｅｌｓ． Ｉｎ ｔｈｉｓ ｓｔｕｄｙ， ｔｈｅ ｋ⁃ｍｅａｎｓ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ， ａ ｔｙｐｅ ｏｆ ｐｒｏｔｏｔｙｐｅ⁃ｂａｓｅｄ ｃｌｕｓｔｅｒｉｎｇ， ｗａｓ ｕｓｅｄ ｔｏ ｃｌｕｓｔｅｒ ｔｈｅ ｔｒａｉｎｉｎｇ ｓｅｔ ｉｎｓｔａｎｃｅ ｓｉｎｃｅ ｓａｍｐｌｅｓ ｈａｖｉｎｇ ｓｉｍｉｌａｒ ｆｅａｔｕｒｅｓ ｈａｖｅ ｓｉｍｉｌａｒ ｌａｂｅｌ ｄｉｓｔｒｉｂｕｔｉｏｎ． Ｈｅｎｃｅ， ａ ｎｅｗ ａｌｇｏｒｉｔｈｍ ｋｎｏｗｎ ａｓ ｌａｂｅｌ ｄｉｓｔｒｉｂｕｔｉｏｎ ｌｅａｒｎｉｎｇ ｂａｓｅｄ ｏｎ ｋ⁃ｍｅａｎｓ ａｌｇｏｒｉｔｈｍ （ＬＤＬＫＭ） ｗａｓ ｐｒｏｐｏｓｅｄ． Ｉｔ ｆｉｒｓｔｌｙ ｃａｌｃｕｌａｔｅｄ ｅａｃｈ ｃｌｕｓｔｅｒ􀆳ｓ ｍｅａｎ ｖｅｃｔｏｒ ｕｓｉｎｇ ｔｈｅ ｋ⁃ｍｅａｎｓ ａｌｇｏｒｉｔｈｍ． Ｔｈｅｎ， ｉｔ ｇｏｔ ｔｈｅ ｍｅａｎ ｖｅｃｔｏｒ ｏｆ ｔｈｅ ｌａｂｅｌ ｄｉｓｔｒｉｂｕｔｉｏｎ ｃｏｒｒｅｓｐｏｎｄｉｎｇ ｔｏ ｔｈｅ ｔｒａｉｎｉｎｇ ｓｅｔ． Ｆｉｎａｌｌｙ， ｔｈｅ ｄｉｓｔａｎｃｅ ｂｅｔｗｅｅｎ ｔｈｅ ｍｅａｎ ｖｅｃｔｏｒｓ ｏｆ ｔｈｅ ｔｅｓｔ ｓｅｔ ａｎｄ ｔｈｅ ｔｒａｉｎｉｎｇ ｓｅｔ ｗａｓ ａｐｐｌｉｅｄ ｔｏ ｐｒｅｄｉｃｔ ｌａｂｅｌ ｄｉｓｔｒｉｂｕｔｉｏｎ ｏｆ ｔｈｅ ｔｅｓｔ ｓｅｔ ａｓ ａ ｗｅｉｇｈｔ． Ｅｘｐｅｒｉｍｅｎｔｓ ｗｅｒｅ ｃｏｎｄｕｃｔｅｄ ｏｎ ｓｉｘ ｐｕｂｌｉｃ ｄａｔａ ｓｅｔｓ ａｎｄ ｔｈｅｎ ｃｏｍｐａｒｅｄ ｗｉｔｈ ｔｈｒｅｅ ｅｘｉｓｔｉｎｇ ｌａｂｅｌ ｄｉｓｔｒｉｂｕｔｉｏｎ ｌｅａｒｎｉｎｇ ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｆｉｖｅ ｔｙｐｅｓ ｏｆ ｅｖａｌｕａｔｉｏｎ ｍｅａｓｕｒｅｓ． Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｄｅｍｏｎｓｔｒａｔｅ ｔｈｅ ｅｆｆｅｃｔｉｖｅｎｅｓｓ ｏｆ ｔｈｅ ｐｒｏｐｏｓｅｄ ＫＭ⁃ＬＤＬ ａｌｇｏｒｉｔｈｍ． Ｋｅｙｗｏｒｄｓ：ｌａｂｅｌ ｄｉｓｔｒｉｂｕｔｉｏｎ； ｃｌｕｓｔｅｒｉｎｇ； ｋ⁃ｍｅａｎｓ； Ｍｉｎｋｏｗｓｋｉ ｄｉｓｔａｎｃｅ； ｍｕｌｔｉ⁃ｌａｂｅｌ； ｗｅｉｇｈｔ ｍａｔｒｉｘ； ｍｅａｎ ｖｅｃｔｏｒ； ｓｏｆｔｍａｘ ｆｕｎｃｔｉｏｎ 收稿日期：２０１７－０４－１９． 网络出版日期：２０１７－０７－０４． 基金项目：国家自然科学基金项目（６１３７９０４９， ６１３７９０８９）． 通信作者：杨文元． Ｅ⁃ｍａｉｌ：ｙａｎｇｗｙ＠ ｘｍｕ．ｅｄｕ．ｃｎ． 近年来，标记多义性问题是机器学习和数据挖 掘领域的热门问题。 目前已有的两种比较成熟的 学习范式是对每个实例分配单个标记的单标记学 习（ｓｉｎｇｌｅ⁃ｌａｂｅｌ ｌｅａｒｎｉｎｇ） 和对一个实例分配多个标 记的多标记学习（ｍｕｌｔｉ⁃ｌａｂｅｌ ｌｅａｒｎｉｎｇ） ［１］ 。 多标记学 习是对单标记学习的拓展［２］ 。 通常多标记学习能 处理一个实例属于多个标记的分歧情况。 通过大 量的研究和实验［３－５］ 表明，多标记学习是一种有效 且应用范围较广的学习范式。 多标记学习虽然对于一个实例允许标上多个