第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
第 １２ 卷第 ３ 期 智 能 系 统 学 报 Ｖｏｌ．１２ №．３ ２０１７ 年 ６ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｊｕｎ． ２０１７ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ．２０１７０４０２４ 网络出版地址：ｈｔｔｐ： ／ ／ ｋｎｓ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１７０７０４．０９２５．００２．ｈｔｍｌ 应用 ｋ⁃ｍｅａｎｓ 算法实现标记分布学习 邵东恒，杨文元，赵红 （闽南师范大学 粒计算重点实验室，福建 漳州 ３６３０００） 摘 要：标记分布学习是近年来提出的一种新的机器学习范式，它能很好地解决某些标记多义性的问题。 现有的标 记分布学习算法均利用条件概率建立参数模型，但未能充分利用特征和标记间的联系。 本文考虑到特征相似的样 本所对应的标记分布也应当相似，利用原型聚类的 ｋ 均值算法（ ｋ⁃ｍｅａｎｓ），将训练集的样本进行聚类，提出基于 ｋ⁃ ｍｅａｎｓ 算法的标记分布学习（ ｌａｂｅｌ ｄｉｓｔｒｉｂｕｔｉｏｎ ｌｅａｒｎｉｎｇ ｂａｓｅｄ ｏｎ ｋ⁃ｍｅａｎｓ ａｌｇｏｒｉｔｈｍ，ＬＤＬＫＭ）。 首先通过聚类算法 ｋ⁃ ｍｅａｎｓ 求得每一个簇的均值向量，然后分别求得对应标记分布的均值向量。 最后将测试集和训练集的均值向量间的 距离作为权重，应用到对测试集标记分布的预测上。 在 ６ 个公开的数据集上进行实验，并与 ３ 种已有的标记分布学 习算法在 ５ 种评价指标上进行比较，实验结果表明提出的 ＬＤＬＫＭ 算法是有效的。 关键词：标记分布；聚类；ｋ－ｍｅａｎｓ；闵可夫斯基距离；多标记；权重矩阵；均值向量；ｓｏｆｔｍａｘ 函数 中图分类号：ＴＰ１８１ 文献标志码：Ａ 文章编号：１６７３－４７８５（２０１７）０３－０３２５－０８ 中文引用格式：邵东恒，杨文元，赵红．应用 ｋ⁃ｍｅａｎｓ 算法实现标记分布学习［Ｊ］． 智能系统学报， ２０１７， １２（３）： ３２５－３３２． 英文引用格式：ＳＨＡＯ Ｄｏｎｇｈｅｎｇ， ＹＡＮＧ Ｗｅｎｙｕａｎ， ＺＨＡＯ Ｈｏｎｇ． Ｌａｂｅｌ ｄｉｓｔｒｉｂｕｔｉｏｎ ｌｅａｒｎｉｎｇ ｂａｓｅｄ ｏｎ ｋ⁃ｍｅａｎｓ ａｌｇｏｒｉｔｈｍ［ Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， ２０１７， １２（３）： ３２５－３３２． Ｌａｂｅｌ ｄｉｓｔｒｉｂｕｔｉｏｎ ｌｅａｒｎｉｎｇ ｂａｓｅｄ ｏｎ ｋ⁃ｍｅａｎｓ ａｌｇｏｒｉｔｈｍ ＳＨＡＯ Ｄｏｎｇｈｅｎｇ， ＹＡＮＧ Ｗｅｎｙｕａｎ， ＺＨＡＯ Ｈｏｎｇ （１． Ｌａｂ ｏｆ Ｇｒａｎｕｌａｒ Ｃｏｍｐｕｔｉｎｇ， Ｍｉｎｎａｎ Ｎｏｒｍａｌ Ｕｎｉｖｅｒｓｉｔｙ， Ｚｈａｎｇｚｈｏｕ ３６３０００， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｌａｂｅｌ ｄｉｓｔｒｉｂｕｔｉｏｎ ｌｅａｒｎｉｎｇ ｉｓ ａ ｎｅｗ ｔｙｐｅ ｏｆ ｍａｃｈｉｎｅ ｌｅａｒｎｉｎｇ ｐａｒａｄｉｇｍ ｔｈａｔ ｈａｓ ｅｍｅｒｇｅｄ ｉｎ ｒｅｃｅｎｔ ｙｅａｒｓ． Ｉｔ ｃａｎ ｓｏｌｖｅ ｔｈｅ ｐｒｏｂｌｅｍ ｗｈｅｒｅｉｎ ｄｉｆｆｅｒｅｎｔ ｒｅｌｅｖａｎｔ ｌａｂｅｌｓ ｈａｖｅ ｄｉｆｆｅｒｅｎｔ ｉｍｐｏｒｔａｎｃｅ． Ｅｘｉｓｔｉｎｇ ｌａｂｅｌ ｄｉｓｔｒｉｂｕｔｉｏｎ ｌｅａｒｎｉｎｇ ａｌｇｏｒｉｔｈｍｓ ａｄｏｐｔ ｔｈｅ ｐａｒａｍｅｔｅｒ ｍｏｄｅｌ ｗｉｔｈ ｃｏｎｄｉｔｉｏｎａｌ ｐｒｏｂａｂｉｌｉｔｙ， ｂｕｔ ｔｈｅｙ ｄｏ ｎｏｔ ａｄｅｑｕａｔｅｌｙ ｅｘｐｌｏｉｔ ｔｈｅ ｒｅｌａｔｉｏｎ ｂｅｔｗｅｅｎ ｆｅａｔｕｒｅｓ ａｎｄ ｌａｂｅｌｓ． Ｉｎ ｔｈｉｓ ｓｔｕｄｙ， ｔｈｅ ｋ⁃ｍｅａｎｓ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ， ａ ｔｙｐｅ ｏｆ ｐｒｏｔｏｔｙｐｅ⁃ｂａｓｅｄ ｃｌｕｓｔｅｒｉｎｇ， ｗａｓ ｕｓｅｄ ｔｏ ｃｌｕｓｔｅｒ ｔｈｅ ｔｒａｉｎｉｎｇ ｓｅｔ ｉｎｓｔａｎｃｅ ｓｉｎｃｅ ｓａｍｐｌｅｓ ｈａｖｉｎｇ ｓｉｍｉｌａｒ ｆｅａｔｕｒｅｓ ｈａｖｅ ｓｉｍｉｌａｒ ｌａｂｅｌ ｄｉｓｔｒｉｂｕｔｉｏｎ． Ｈｅｎｃｅ， ａ ｎｅｗ ａｌｇｏｒｉｔｈｍ ｋｎｏｗｎ ａｓ ｌａｂｅｌ ｄｉｓｔｒｉｂｕｔｉｏｎ ｌｅａｒｎｉｎｇ ｂａｓｅｄ ｏｎ ｋ⁃ｍｅａｎｓ ａｌｇｏｒｉｔｈｍ （ＬＤＬＫＭ） ｗａｓ ｐｒｏｐｏｓｅｄ． Ｉｔ ｆｉｒｓｔｌｙ ｃａｌｃｕｌａｔｅｄ ｅａｃｈ ｃｌｕｓｔｅｒｓ ｍｅａｎ ｖｅｃｔｏｒ ｕｓｉｎｇ ｔｈｅ ｋ⁃ｍｅａｎｓ ａｌｇｏｒｉｔｈｍ． Ｔｈｅｎ， ｉｔ ｇｏｔ ｔｈｅ ｍｅａｎ ｖｅｃｔｏｒ ｏｆ ｔｈｅ ｌａｂｅｌ ｄｉｓｔｒｉｂｕｔｉｏｎ ｃｏｒｒｅｓｐｏｎｄｉｎｇ ｔｏ ｔｈｅ ｔｒａｉｎｉｎｇ ｓｅｔ． Ｆｉｎａｌｌｙ， ｔｈｅ ｄｉｓｔａｎｃｅ ｂｅｔｗｅｅｎ ｔｈｅ ｍｅａｎ ｖｅｃｔｏｒｓ ｏｆ ｔｈｅ ｔｅｓｔ ｓｅｔ ａｎｄ ｔｈｅ ｔｒａｉｎｉｎｇ ｓｅｔ ｗａｓ ａｐｐｌｉｅｄ ｔｏ ｐｒｅｄｉｃｔ ｌａｂｅｌ ｄｉｓｔｒｉｂｕｔｉｏｎ ｏｆ ｔｈｅ ｔｅｓｔ ｓｅｔ ａｓ ａ ｗｅｉｇｈｔ． Ｅｘｐｅｒｉｍｅｎｔｓ ｗｅｒｅ ｃｏｎｄｕｃｔｅｄ ｏｎ ｓｉｘ ｐｕｂｌｉｃ ｄａｔａ ｓｅｔｓ ａｎｄ ｔｈｅｎ ｃｏｍｐａｒｅｄ ｗｉｔｈ ｔｈｒｅｅ ｅｘｉｓｔｉｎｇ ｌａｂｅｌ ｄｉｓｔｒｉｂｕｔｉｏｎ ｌｅａｒｎｉｎｇ ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｆｉｖｅ ｔｙｐｅｓ ｏｆ ｅｖａｌｕａｔｉｏｎ ｍｅａｓｕｒｅｓ． Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｄｅｍｏｎｓｔｒａｔｅ ｔｈｅ ｅｆｆｅｃｔｉｖｅｎｅｓｓ ｏｆ ｔｈｅ ｐｒｏｐｏｓｅｄ ＫＭ⁃ＬＤＬ ａｌｇｏｒｉｔｈｍ． Ｋｅｙｗｏｒｄｓ：ｌａｂｅｌ ｄｉｓｔｒｉｂｕｔｉｏｎ； ｃｌｕｓｔｅｒｉｎｇ； ｋ⁃ｍｅａｎｓ； Ｍｉｎｋｏｗｓｋｉ ｄｉｓｔａｎｃｅ； ｍｕｌｔｉ⁃ｌａｂｅｌ； ｗｅｉｇｈｔ ｍａｔｒｉｘ； ｍｅａｎ ｖｅｃｔｏｒ； ｓｏｆｔｍａｘ ｆｕｎｃｔｉｏｎ 收稿日期：２０１７－０４－１９． 网络出版日期：２０１７－０７－０４． 基金项目：国家自然科学基金项目（６１３７９０４９， ６１３７９０８９）． 通信作者：杨文元． Ｅ⁃ｍａｉｌ：ｙａｎｇｗｙ＠ ｘｍｕ．ｅｄｕ．ｃｎ． 近年来，标记多义性问题是机器学习和数据挖 掘领域的热门问题。 目前已有的两种比较成熟的 学习范式是对每个实例分配单个标记的单标记学 习（ｓｉｎｇｌｅ⁃ｌａｂｅｌ ｌｅａｒｎｉｎｇ） 和对一个实例分配多个标 记的多标记学习（ｍｕｌｔｉ⁃ｌａｂｅｌ ｌｅａｒｎｉｎｇ） ［１］ 。 多标记学 习是对单标记学习的拓展［２］ 。 通常多标记学习能 处理一个实例属于多个标记的分歧情况。 通过大 量的研究和实验［３－５］ 表明，多标记学习是一种有效 且应用范围较广的学习范式。 多标记学习虽然对于一个实例允许标上多个
·326 智能系统学报 第12卷 标记，拓展了单标记学习。但是仍有一些问题是不 集时花费的时间较多。 太适合用多标记学习解决的，例如，标记集中的每 聚类4]是研究分类问题的一种统计分析方法， 一个标记描述实例的准确度是多少。事实上，现实 同时也是数据挖掘的一个重要算法，在研究过程中 世界中有着比大多数人想象的多得多的关于每个 也有许许多多的应用和改进)。聚类以相似性为 标记的准确描述度的数据。在许多科学实验中[6 基础，试图将数据集中的样本划分为若干个不相交 它们的输出结果不是单个值的，而是一系列的数值 的子集，每个子集称为一个簇，同一簇中样本之间 输出，例如，基因在不同时间点上的表达水平。这 的相似性比不在同一簇中的更高。在聚类算法中 些输出中的单个数值可能不是那么重要，真正重要 常用的k-means算法[16]及改进算法[7)是原型聚类 的是这一系列输出数值的分布情况。如果一个机 的一种，它假设聚类结构能通过一组原型刻画。通 器学习的任务是要预测一个数值分布，那么它很难 常情况下，算法先对原型进行初始化，然后对原型 放到多标记学习的框架中实现。因为在一个分布 进行迭代更新求解，直到均值向量不再改变或达到 中每一个数值输出的准确度是至关重要的，而且这 最大迭代次数，此时就能得到每一个簇的均值向量。 里也不再有相关标记与无关标记的区分了。因此， 在同一个数据集中，特征相近的实例，它们的 为了解决这类问题，Geng等)拓展了多标记学习， 标记分布往往也相似，同时依据聚类的特性，本文 提出了标记分布学习(label distribution learning, 提出一种新的标记分布算法：基于k-means的标记 LDL)范式。对于一个特定的实例，标记集合中所有 分布学习算法(label distribution learning algorithm 标记的描述度构建一个类似于概率分布的数据形 based on k-means,LDLKM)。首先，利用k-means聚 式，称之为标记分布⑧)，即每个训练实例与一个标 类算法求得训练样本集中每个簇的均值向量，此时 记分布相对应。与多标记学习输出一个标记集不 与每一个训练样本对应的标记分布也相应被划分 同，标记分布学习输出的是一个标记分布，分布中 成簇。然后，求得标记分布的每个簇的均值向量。 的每个分量表示对应标记对实例的描述程度。事 其次，测试集的样本到各个簇的均值向量的距离矩 实上，标记分布学习是一种适用场景更广的学习范 阵可通过常用的求距离方式，闵可夫斯基距离 式，能够解决更多的标记多义性问题。单标记学习 (Minkowski distance)Iu]求得。最后，将距离矩阵通 和多标记学习都可以看成标记分布学习的特例，相 过一个softmax函数变换得到一个权重矩阵。权重 关的研究成果[，o]也说明了这一点。 矩阵和训练样本集的标记分布的均值向量的积就 目前，已有一些标记分布学习算法[7，川被提了 是测试集样本的标记分布，即需要预测的标记分 出来。这些算法的设计策略主要可以分为以下 布。本文提出的LDLKM算法与现有的专用化的算 3类。 法相比并未采用条件概率的方式建立模型，而是充 1)问题转换，即将标记分布学习问题转换成单 分考虑了特征间的分布关系和特征与对应的标记 标记学习问题后，再利用相应范式中已有的算法进 分布之间的联系，利用k-means聚类和权重矩阵将 行求解，例如：PT-SVM算法和PT-Bayes算法。 特征和标记分布联系到一起。事实上，特征之间的 2)算法适应，即扩展现存的学习算法来处理标 分布与对应标记之间的分布的关系是一种更加直 签分布学习问题，例如：LDSVR[]算法和AA-BP 接和强烈的联系。而直接利用这种关系预测得到 算法。 的标记分布可以继续保持与对应特征的分布关系， 3)专用化的算法，即根据LDL的特点设计特殊 从而得到一个较好的结果。LDLKM和现有的3种 的算法，例如：SA-IS算法、CPNNU]和SA-BFGS LDL算法在6个公开数据集)上采用5种评价方式 算法。 进行实验比较，实验的结果表明本文提出的标记分 在这3种策略中，第3种直接针对标记分布学 布学习算法在使用的所有数据集上均取得较好的 习设计专门算法的效果是最好的。事实上，专用化 效果，在其中的5个数据集上所有评价方式的结果 的算法是通过条件概率或逻辑回归方式训练模型， 均为最优。 然后以这个模型预测想要的标记分布。但是在这 1标记分布学习的形式化 个过程中算法并未充分考虑训练实例与对应标记 分布之间的关系，例如：特征与标记间的函数关系， 在标记分布中，标记一个实例x的方式是为它 特征与标记间的分布关系和标记分布数据内部的 的每一个可能的标记y分配一个实数d,用来表示 分布关系。同时，现有的专门算法在处理较大数据 标记y对实例x的描述程度。不失一般性，假设实
标记，拓展了单标记学习。 但是仍有一些问题是不 太适合用多标记学习解决的，例如，标记集中的每 一个标记描述实例的准确度是多少。 事实上，现实 世界中有着比大多数人想象的多得多的关于每个 标记的准确描述度的数据。 在许多科学实验中［６］ ， 它们的输出结果不是单个值的，而是一系列的数值 输出，例如，基因在不同时间点上的表达水平。 这 些输出中的单个数值可能不是那么重要，真正重要 的是这一系列输出数值的分布情况。 如果一个机 器学习的任务是要预测一个数值分布，那么它很难 放到多标记学习的框架中实现。 因为在一个分布 中每一个数值输出的准确度是至关重要的，而且这 里也不再有相关标记与无关标记的区分了。 因此， 为了解决这类问题，Ｇｅｎｇ 等［７］ 拓展了多标记学习， 提出了标记分布学习 （ ｌａｂｅｌ ｄｉｓｔｒｉｂｕｔｉｏｎ ｌｅａｒｎｉｎｇ， ＬＤＬ）范式。 对于一个特定的实例，标记集合中所有 标记的描述度构建一个类似于概率分布的数据形 式，称之为标记分布［８］ ，即每个训练实例与一个标 记分布相对应。 与多标记学习输出一个标记集不 同，标记分布学习输出的是一个标记分布，分布中 的每个分量表示对应标记对实例的描述程度。 事 实上，标记分布学习是一种适用场景更广的学习范 式，能够解决更多的标记多义性问题。 单标记学习 和多标记学习都可以看成标记分布学习的特例，相 关的研究成果［７， ９－１０］也说明了这一点。 目前，已有一些标记分布学习算法［７， １１］ 被提了 出来。 这些算法的设计策略主要可以分为以下 ３ 类。 １）问题转换，即将标记分布学习问题转换成单 标记学习问题后，再利用相应范式中已有的算法进 行求解，例如：ＰＴ⁃ＳＶＭ 算法和 ＰＴ⁃Ｂａｙｅｓ 算法。 ２）算法适应，即扩展现存的学习算法来处理标 签分布学习问题， 例如： ＬＤＳＶＲ ［１２］ 算法和 ＡＡ⁃ＢＰ 算法。 ３）专用化的算法，即根据 ＬＤＬ 的特点设计特殊 的算 法， 例 如： ＳＡ⁃ＩＩＳ 算 法、 ＣＰＮＮ ［１３］ 和 ＳＡ⁃ＢＦＧＳ 算法。 在这 ３ 种策略中，第 ３ 种直接针对标记分布学 习设计专门算法的效果是最好的。 事实上，专用化 的算法是通过条件概率或逻辑回归方式训练模型， 然后以这个模型预测想要的标记分布。 但是在这 个过程中算法并未充分考虑训练实例与对应标记 分布之间的关系，例如：特征与标记间的函数关系， 特征与标记间的分布关系和标记分布数据内部的 分布关系。 同时，现有的专门算法在处理较大数据 集时花费的时间较多。 聚类［１４］是研究分类问题的一种统计分析方法， 同时也是数据挖掘的一个重要算法，在研究过程中 也有许许多多的应用和改进［１５］ 。 聚类以相似性为 基础，试图将数据集中的样本划分为若干个不相交 的子集，每个子集称为一个簇，同一簇中样本之间 的相似性比不在同一簇中的更高。 在聚类算法中 常用的 ｋ⁃ｍｅａｎｓ 算法［１６］ 及改进算法［１７］ 是原型聚类 的一种，它假设聚类结构能通过一组原型刻画。 通 常情况下，算法先对原型进行初始化，然后对原型 进行迭代更新求解，直到均值向量不再改变或达到 最大迭代次数，此时就能得到每一个簇的均值向量。 在同一个数据集中，特征相近的实例，它们的 标记分布往往也相似，同时依据聚类的特性，本文 提出一种新的标记分布算法：基于 ｋ⁃ｍｅａｎｓ 的标记 分布学习算法 （ ｌａｂｅｌ ｄｉｓｔｒｉｂｕｔｉｏｎ ｌｅａｒｎｉｎｇ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｋ⁃ｍｅａｎｓ，ＬＤＬＫＭ）。 首先，利用 ｋ⁃ｍｅａｎｓ 聚 类算法求得训练样本集中每个簇的均值向量，此时 与每一个训练样本对应的标记分布也相应被划分 成簇。 然后，求得标记分布的每个簇的均值向量。 其次，测试集的样本到各个簇的均值向量的距离矩 阵可通 过 常 用 的 求 距 离 方 式， 闵 可 夫 斯 基 距 离 （Ｍｉｎｋｏｗｓｋｉ ｄｉｓｔａｎｃｅ） ［１８］求得。 最后，将距离矩阵通 过一个 ｓｏｆｔｍａｘ 函数变换得到一个权重矩阵。 权重 矩阵和训练样本集的标记分布的均值向量的积就 是测试集样本的标记分布，即需要预测的标记分 布。 本文提出的 ＬＤＬＫＭ 算法与现有的专用化的算 法相比并未采用条件概率的方式建立模型，而是充 分考虑了特征间的分布关系和特征与对应的标记 分布之间的联系，利用 ｋ⁃ｍｅａｎｓ 聚类和权重矩阵将 特征和标记分布联系到一起。 事实上，特征之间的 分布与对应标记之间的分布的关系是一种更加直 接和强烈的联系。 而直接利用这种关系预测得到 的标记分布可以继续保持与对应特征的分布关系， 从而得到一个较好的结果。 ＬＤＬＫＭ 和现有的 ３ 种 ＬＤＬ 算法在 ６ 个公开数据集［７］上采用 ５ 种评价方式 进行实验比较，实验的结果表明本文提出的标记分 布学习算法在使用的所有数据集上均取得较好的 效果，在其中的 ５ 个数据集上所有评价方式的结果 均为最优。 １ 标记分布学习的形式化 在标记分布中，标记一个实例 ｘ 的方式是为它 的每一个可能的标记 ｙ 分配一个实数 ｄ ｙ ｘ，用来表示 标记 ｙ 对实例 ｘ 的描述程度。 不失一般性，假设实 ·３２６· 智 能 系 统 学 报 第 １２ 卷
第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值越小则簇内样本相似度越 布所使用的权重矩阵
数 ｄ ｙ ｘ∈ [０，１] ，进一步假设所有标记能够完整地描 述实例，则 ∑ｙ ｄ ｙ ｘ ＝ １。 标记分布学习是一种更为灵活复杂的标记学 习范式，然而学习中更好的灵活性通常意味着更大 的输出空间［１９］ 。 从单标记学习到多标记学习，再到 标记分布学习，学习过程的输出空间的维度变得越 来越大。 更为详细地，对于标记集合中有 ｃ 个不同 标记的学习问题，单标记学习的分类器有 ｃ 个可能 的输出，多标记学习的分类器有 ２ ｃ －１ 个可能的输 出。 对标记分布学习的分类器来讲，只要在满足 ｄ ｙ ｘ∈ [０，１] 和 ∑ｙ ｄ ｙ ｘ ＝ １ 这两个约束条件的前提下， 它的输出空间的维度可能是无穷大的［１９］ 。 标记 分 布 学 习 定 义 的 实 例 矩 阵 为 Ｘ ＝ ｘ１ ｘ２… ｘｎ [ ] ，ｘｉ∈Ｒ ｄ 表示第 ｉ 个实例，ｉ ＝ １，２，…，ｎ。 给定对应标记矩阵 Ｙ ＝ ｙ１ ｙ２… ｙｃ [ ] ，ｙｊ 表示第 ｊ 个 标记， ｊ ＝ １，２，…，ｃ；给定样本的标记分布集是 Ｄ ＝ Ｄ１ Ｄ２… Ｄｎ [ ] ，Ｄｉ ＝ ｄ ｙ１ ｘｉ ｄ ｙ２ ｘｉ … ｄ ｙｃ ｘｉ [ ] 表示实例 ｘｉ 的标 记分布集，ｄ ｙｊ ｘｉ表示标记 ｙｊ 对实例 ｘｉ 的描述度。 基于 此， 标 记 分 布 学 习 的 一 个 训 练 集 能 够 表 示 为 Ｓ ＝ （ｘ１ ，Ｄ１ ），（ｘ２ ，Ｄ２ ），…，（ｘ { ｎ ，Ｄｎ ）} 。 目前的标记分布学习算法的输出模型是一个 最大熵模型［７］ ： ｐ（ｙ ｘ；θ） ＝ １ Ｚ ｅｘｐ ∑ ｊ θｙ，ｊ ｆ ( ｊ（ｘ） ) （１） 式中： Ｚ ＝ ∑ｙ ｅｘｐ ∑ ｊ θｙ，ｊ ｆ ( ｊ（ｘ） ) 是归一化因数；θｙ，ｊ 是模型参数； ｆ ｊ（ｘ） 是 ｘ 的第 ｊ 个特征。 随着标记分 布的发展逐渐提出许多基于式（１） 的标记分布学习 方法［７，９－１０］ 。 这些算法先通过条件概率建立参数模 型，再利用现有的模型求解参数 θ。 ２ 基于 ｋ⁃ｍｅａｎｓ 的标记分布学习算法 ｋ－ｍｅａｎｓ 算法是所有聚类算法中简单常用的一 种算法［２０］ 。 它假设聚类结构能被一组原型刻画，先 初始化一组原型，然后对原型进行迭代更新求解， 最终得到每一个簇的均值向量。 给定训练集 Ｈ ＝ ｘ１ ｘ２… ｘｍ [ ] ，ｍ 为训练集样本数。 ｋ⁃ｍｅａｎｓ 算法针 对聚类所得簇划分 Ｇ ＝ Ｃ１ ，Ｃ２ ，…，Ｃｋ { } ，最小化平方 误差为 Ｅ ＝ ∑ ｋ ｉ ＝ １ ∑ｘ∈Ｃｉ ‖ｘ － μｉ‖２ ２ （２） 式中： μｉ ＝ １ Ｃｉ ∑ｘ∈Ｃｉ ｘ 是簇 Ｃｉ 的均值向量。 直观来 看，式（２） 在一定程度上刻画了簇内样本围绕簇均 值向量的紧密程度，Ｅ 值越小则簇内样本相似度越 高。 最小化式（２） 并不容易，找到其最优解需考察 训练集 Ｈ 所有可能的簇划分，这是一个 ＮＰ 难［２０－２１］ 的问题。 因此，ｋ⁃ｍｅａｎｓ 算法采用了贪心策略，通过 迭代优化来近似求解式（２）。 首先，聚类过程中在 Ｈ 中随机选择 ｋ 个样本作 为初始均值向量 μ１ ，μ２ ，…，μｋ { } ，可以通过下式： ｄｊｉ ＝ ‖ｘｊ － μｉ‖２ （３） 计算训练集样本 ｘｊ 与各均值向量 μｉ（ ｉ ＝ １，２，…，ｋ） 的距离。 根据距离最近的均值向量确定 ｘｊ 的簇 标记： λｊ ＝ ａｒｇ ｍｉｎｉ∈［１，２，…，ｋ］ ｄｊｉ （４） 式中 λｊ∈(１，２，…，ｋ) 表示样本 ｘｊ 的簇标记。 将样 本 ｘｊ 划入相应的簇，即 Ｃλｊ ＝ Ｃλｊ ∪ ［ｘｊ］ （５） 更新簇 Ｃλｊ的均值向量。 式（３） ～ 式（５）这个过程不 断迭代直到当前均值向量保持不变或迭代次数达 到所规定的最大次数。 其次，当迭代结束求出所要划分的聚类和对应 的均值向量后，便可以依据标记分布与训练样本集 的对应关系得到标记分布的簇划分和标记分布每 个簇的均值向量 ｕ。 同时利用常用的距离计算公式 “闵可夫斯基距离”公式，即 ｄｉｓｔｍｋ（ｘｉ，ｘｊ） ＝ ∑ ｎ ｕ ＝ １ ｘｉｕ － ｘｊｕ ｐ ( ) １ ｐ （６） 求得测试集每个样本与各个簇的均值向量的距离 矩阵 Ｔ。 闵可夫斯基距离是欧式距离的推广，具有 广泛的应用，当 ｐ ＝ １ 时是曼哈顿距离，ｐ ＝ ２ 就是欧 式距离，而当 ｐ 趋于无穷大时就是切比雪夫距离。 本文中将距离矩阵 Ｔ 的每个元素求倒数再通过一 个 ｓｏｆｔｍａｘ 函数进行处理转换，从而得到从训练集样 本的标记分布的均值向量转化为预测标记分布的 权重矩阵。 对矩阵 Ｔ 作以下处理，先对 Ｔ 中每个元 素求导数： Ｔ′ａｂ ＝ １ Ｔａｂ （７） 然后，为了尽量减小与测试样本实例距离较远 的均值向量的影响和便于之后的计算，利用 ｓｏｆｔｍａｘ 函数 Ｚｋ ＝ ｓｏｆｔｍａｘ（ｘｋ） ＝ ｅｘｐ（ｘｋ） ∑ ｋ ｉ ＝ １ ｅｘｐ（ｘｉ） 再作以下 处理： Ｗａ ＝ ｅｘｐ（Ｔ′ａｂ） ∑ ｋ ｂ ＝ １ ｅｘｐ（Ｔ′ａｂ） ， ａ ＝ １，２，…，ｎ （８） 式中：ｎ 是测试集样本实例数，Ｗ 为最后预测标记分 布所使用的权重矩阵。 第 ３ 期 邵东恒，等：应用 ｋ⁃ｍｅａｎｓ 算法实现标记分布学习 ·３２７·
·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所示
最后将 Ｗ 与训练集对应的标记分布的均值向 量矩阵 Ｕ 相乘，即 Ｐ ＝ ＷＵ （９） 式中：Ｕ ＝ ［ｕ１ ｕ２… ｕｂ］；Ｐ 就是所需要求的预测标记 分布。 上述的算法过程可以通过图 １ 的流程图来 表示。 图 １ ＬＤＬＫＭ 算法流程图 Ｆｉｇ．１ Ｔｈｅ ｆｌｏｗｃｈａｒｔ ｏｆ ＬＤＬＫＭ 本文提出的 ＬＤＬＫＭ 算法具体步骤如下： 算法 基 于 ｋ⁃ｍｅａｎｓ 算 法 的 标 记 分 布 学 习 （ＬＤＬＫＭ）。 输入 聚类的簇数 ｋ，聚类迭代的最大次数 ｄ，闵可 夫斯基距离参数 ｐ，训练集 Ｓ ＝｛（ｘ１，Ｄ１ ），（ｘ２，Ｄ２ ），…， （ｘｎ，Ｄｎ）｝。 输出 测试集的预测标记分布 Ｐ。 １）从训练集样本 Ｈ 中随机选择 ｋ 个样本作为 初始向量 μ１ ， μ２ ， …， μｋ { } 。 ２）迭代开始，令 Ｃｉ（１≤ｉ≤ｋ）为空，利用式（３） 计算样本 ｘｊ 与各均值向量 μｉ 的距离。 ３）依据式（４），根据距离最近的均值向量确定 ｘｊ 的簇标记 λｊ；将样本 ｘｊ 划入相应的簇。 ４）更新均值向量，分别计算划分完簇后的新的 均值向量： μｉ ＝ １ Ｃｉ ∑ｘ∈Ｃｉ ｘ。 ５）若当前的均值向量均未更新或达到规定的 最大迭代次数，继续下一步；否则，返回 ２），重复 ３） 到 ５）直到所有测法样本划分完毕。 ６）依据式（６）求得测试集每个样本与各个均值 向量的距离矩阵 Ｔ。 ７）利用式（７）和式（８）求得预测标记分布的权 重矩阵 Ｗ。 ８）根据式（９）得出预测标记分布 Ｐ。 ３ 实验与结果分析 在这部分，将通过实验来验证本文提出的基于 ｋ⁃ｍｅａｎｓ 的标记分布学习算法。 标记分布学习算法的输出是一个标记分布，与 单标记学习的单标记输出和多标记学习的标记集 输出都不同。 因此，标记分布学习算法的评价方 式，应该与单标记学习和多标记学习算法不同。 这 种方式不是通过预测标记的准确度来评价算法优 劣，而是通过测量预测结果和真实标记分布之间的 距离或相似度来衡量算法效果。 有很多测量概率 分布之间的距离或相似度的方法［７］ 可以用来很好 地测量标记分布之间的距离或相似度。 例如，表 １ 中根据文献［７］和［２２］选出的 ５ 种测量方式就能很 好地用来评价标记分布算法。 评价标准距离名称 之后的“↓”代表距离值越小越好，相似度名称之后 的“↑”表示相似值越大越好。 这 ５ 种评价方法分 别是 切 比 雪 夫 距 离 （ Ｃｈｅｂｙｓｈｅｖ ）、 克 拉 克 距 离 （Ｃｌａｒｋ）、堪培拉量度（Ｃａｎｂｅｒｒａ）、弦系数（Ｃｏｓｉｎｅ）以 及交叉相似性（ Ｉｎｔｅｒｓｅｃｔｉｏｎ），前 ３ 种以距离作为评 价，即越小越好，后两种以相似度作为评价，即越大 越好。 表 １ 评价指标 Ｔａｂｌｅ １ Ｅｖａｌｕａｔｉｏｎ ｉｎｄｅｘ 评价标准 计算形式 Ｃｈｅｂｙｓｈｅｖ ↓ Ｄｉｓ１ ＝ｍａｘ ｌ ｄｌ －ｄ ∧ ｌ Ｃｌａｒｋ ↓ Ｄｉｓ２ ＝ ∑ｃ ｌ＝ １ （ｄｌ －ｄ ∧ ｌ） ２ （ｄｌ，ｄ ∧ ｌ） ２ Ｃａｎｂｅｒｒａ ↓ Ｄｉｓ３ ＝ ∑ ｃ ｌ ＝ １ ｄｌ － ｄｌ ∧ ｄｌ ＋ ｄｌ ∧ Ｃｏｓｉｎｅ ↑ Ｄｉｓ４ ＝ ∑ ｃ ｌ ＝ １ ｄｌ ｄｌ ∧ ∑ ｃ ｌ ＝ １ ｄ ２ ｌ ∑ ｃ ｌ ＝ １ ｄ ２ ｌ ∧ Ｉｎｔｅｒｓｅｃｔｉｏｎ ↑ Ｄｉｓ５ ＝∑ｃ ｌ＝ １ｍｉｎ（ｄｌ，ｄｌ ∧ ） ３．１ 实验设置 通过上述 ５ 种评价方式，本次实验在 ６ 个公开 的数据集上进行，它们分别是 Ｙｅａｓｔ⁃ａｌｐｈａ、 Ｙｅａｓｔ⁃ ｃｄｃ、 Ｙｅａｓｔ⁃ｅｌｕ、 ＳＪＡＦＦＥ、 Ｈｕｍａｎ Ｇｅｎｅ 和 Ｍｏｖｉｅ，详 细的信息如表 ２ 所示。 ·３２８· 智 能 系 统 学 报 第 １２ 卷
第3期 邵东恒，等：应用k-means算法实现标记分布学习 ·329· 表2实验数据集描述 5个人类基因数据集完全优于和它对比的算法，第4 Table 2 Describe experimental data set 个和第6个数据集也优于其他两个对比算法，并在 数据集 样本 特征 标记 总体上优于第3个对比算法。整体上来看，LDLKM Yeast-alpha 2465 24 18 在基因数据集上可以取得比在其他类型数据集上 Yeast-cde 2465 24 15 更好的效果，在非基因数据集SJAFFE和Movie上的 效果略微差于在基因数据集上的效果，而在Human Yeast-elu 2465 24 14 Gene数据集上LDLKM的效果与SA-IIS较为接近， SJAFFE 213 243 6 提升效果不大。这说明不同类型的数据集对我们 Human Gene 30542 36 68 的算法有着一定的影响。同时，可以进一步看到， Movie 7755 1869 J 专用化的算法SA-IIS比算法PT-Bayes和AA-BP的 第1个到第3个数据集（从Yeast-alpha到 效果更好，处于第二的位置。 Yeast-elu)是从酿酒酵母6的4个生物实验上收集 表3数据集Yeast--alpha的实验结果 的真实数据集。每个数据集总共包括2465个酵母 Table 3 The experimental results of Yeast-alpha 基因，每个基因通过24个特征表示。标记对应于离 评价标准PT-Bayes AA-BP SA-IIS LDLKM 散的时间点，标记分布是每个时间点的基因表达水 平。第四个数据集拓展来自一个脸部表情图像数 Cheby 0.1010 0.0361 0.0202 0.0135 据集JAF℉E,它包括来自10个日本女性的213张灰 Clark 1.17280.7221 0.3034 0.2101 度图，并利用局部二值模式]从每张图像中采集 Canbe 4.1989 2.3831 1.0140 243个特征，每张图像由60个人在6种感情上打 0.6812 分。第5个数据集Human Gene是一个大规模的真 Cosine 0.8486 0.9485 0.9881 0.9946 实数据集，来自于人类基因和疾病的关系生物实 验[24】。在数据集中总共包括30542个人类基因，每 Interse 0.7727 0.8759 0.9428 0.9624 一个都被一个基因序列的36个特征数值表示。68 表4数据集Yeast-.cdc的实验结果 个标记对应于68种疾病，标记分布是基因在68种 Table 4 The experimental results of Yeast-cdc 疾病上的表达水平。第6个数据集Movie是关于电 评价标准 PT-Bayes AA-BP SA-IIS LDLKM 影的用户评级。评级数据来源于Netflix,范围是15 级(5个标记)。标记分布描述了每个评级所占的比 Cheby 0.1124 0.0393 0.0233 0.0162 例。特征则提取自电影的元数据，一共有1869个 Clark 1.0758 0.6073 0.2926 0.2158 特征。 为了能使实验结果更具说服力，采用了十折交 Canbe 3.5263 1.8298 0.8976 0.6467 叉的方式进行实验。聚类划分的簇的数目为5，最 Cosine 0.8491 0.95500.9870 0.9933 大迭代次数设置为20，闵可夫斯基距离参数p设置 成5。在表2的数据集上进行实验，并采用表1中 Interse 0.77120.8851 0.9397 0.9575 的五种评价方式，分别与现有的3种标记分布学习 表5数据集Yeast-.elu的实验结果 算法进行比较。这3种比较算法分别是PT-Bayes、 Table 5 The experimental results of Yeast-elu AA-BP和SA-IIS。 评价标准 PT-Bayes AA-BP SA-IIS LDLKM 3.2实验结果分析 表3~8分别列出在6个不同的数据集上，4种 Cheby 0.1098 0.0388 0.0240 0.0163 算法对应不同评价标准的测量值。前3个评价指标 Clark 1.01490.5438 0.2756 0.1995 (Cheby、Clark和Canbe)值越小表示算法效果越好， 后两个评价指标(Cosine和Interse)值越大表示算法 Canbe 3.2119 1.5841 0.8239 0.5855 效果越好。在每个表中最后一列是本文算法的结 Cosine 0.85720.9600 0.9876 0.9940 果。从表中可以看出本文提出的算法在5种评价标 准下都有很好的效果。前3个酵母基因数据集和第 Interse 0.77760.89300.9406 0.9587
表 ２ 实验数据集描述 Ｔａｂｌｅ ２ Ｄｅｓｃｒｉｂｅ ｅｘｐｅｒｉｍｅｎｔａｌ ｄａｔａ ｓｅｔ 数据集 样本 特征 标记 Ｙｅａｓｔ⁃ａｌｐｈａ ２ ４６５ ２４ １８ Ｙｅａｓｔ⁃ｃｄｃ ２ ４６５ ２４ １５ Ｙｅａｓｔ⁃ｅｌｕ ２ ４６５ ２４ １４ ＳＪＡＦＦＥ ２１３ ２４３ ６ Ｈｕｍａｎ Ｇｅｎｅ ３０ ５４２ ３６ ６８ Ｍｏｖｉｅ ７ ７５５ １ ８６９ ５ 第 １ 个到第 ３ 个数据集 （ 从 Ｙｅａｓｔ⁃ａｌｐｈａ 到 Ｙｅａｓｔ⁃ｅｌｕ）是从酿酒酵母［６］ 的 ４ 个生物实验上收集 的真实数据集。 每个数据集总共包括２ ４６５个酵母 基因，每个基因通过 ２４ 个特征表示。 标记对应于离 散的时间点，标记分布是每个时间点的基因表达水 平。 第四个数据集拓展来自一个脸部表情图像数 据集 ＪＡＦＦＥ，它包括来自 １０ 个日本女性的 ２１３ 张灰 度图，并利用局部二值模式［２３］ 从每张图像中采集 ２４３ 个特征，每张图像由 ６０ 个人在 ６ 种感情上打 分。 第 ５ 个数据集 Ｈｕｍａｎ Ｇｅｎｅ 是一个大规模的真 实数据集，来自于人类基因和疾病的关系生物实 验［２４］ 。 在数据集中总共包括３０ ５４２个人类基因，每 一个都被一个基因序列的 ３６ 个特征数值表示。 ６８ 个标记对应于 ６８ 种疾病，标记分布是基因在 ６８ 种 疾病上的表达水平。 第 ６ 个数据集 Ｍｏｖｉｅ 是关于电 影的用户评级。 评级数据来源于 Ｎｅｔｆｌｉｘ，范围是 １５ 级（５ 个标记）。 标记分布描述了每个评级所占的比 例。 特征则提取自电影的元数据，一共有１ ８６９个 特征。 为了能使实验结果更具说服力，采用了十折交 叉的方式进行实验。 聚类划分的簇的数目为 ５，最 大迭代次数设置为 ２０，闵可夫斯基距离参数 ｐ 设置 成 ５。 在表 ２ 的数据集上进行实验，并采用表 １ 中 的五种评价方式，分别与现有的 ３ 种标记分布学习 算法进行比较。 这 ３ 种比较算法分别是 ＰＴ⁃Ｂａｙｅｓ、 ＡＡ⁃ＢＰ 和 ＳＡ⁃ＩＩＳ。 ３．２ 实验结果分析 表 ３～８ 分别列出在 ６ 个不同的数据集上，４ 种 算法对应不同评价标准的测量值。 前 ３ 个评价指标 （Ｃｈｅｂｙ、Ｃｌａｒｋ 和 Ｃａｎｂｅ）值越小表示算法效果越好， 后两个评价指标（Ｃｏｓｉｎｅ 和 Ｉｎｔｅｒｓｅ）值越大表示算法 效果越好。 在每个表中最后一列是本文算法的结 果。 从表中可以看出本文提出的算法在 ５ 种评价标 准下都有很好的效果。 前 ３ 个酵母基因数据集和第 ５ 个人类基因数据集完全优于和它对比的算法，第 ４ 个和第 ６ 个数据集也优于其他两个对比算法，并在 总体上优于第 ３ 个对比算法。 整体上来看，ＬＤＬＫＭ 在基因数据集上可以取得比在其他类型数据集上 更好的效果，在非基因数据集 ＳＪＡＦＦＥ 和 Ｍｏｖｉｅ 上的 效果略微差于在基因数据集上的效果，而在 Ｈｕｍａｎ Ｇｅｎｅ 数据集上 ＬＤＬＫＭ 的效果与 ＳＡ⁃ＩＩＳ 较为接近， 提升效果不大。 这说明不同类型的数据集对我们 的算法有着一定的影响。 同时，可以进一步看到， 专用化的算法 ＳＡ⁃ＩＩＳ 比算法 ＰＴ⁃Ｂａｙｅｓ 和 ＡＡ⁃ＢＰ 的 效果更好，处于第二的位置。 表 ３ 数据集 Ｙｅａｓｔ－ａｌｐｈａ 的实验结果 Ｔａｂｌｅ ３ Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｏｆ Ｙｅａｓｔ⁃ａｌｐｈａ 评价标准 ＰＴ⁃Ｂａｙｅｓ ＡＡ⁃ＢＰ ＳＡ⁃ＩＩＳ ＬＤＬＫＭ Ｃｈｅｂｙ ０．１０１ ０ ０．０３６ １ ０．０２０ ２ ０．０１３５ Ｃｌａｒｋ １．１７２ ８ ０．７２２ １ ０．３０３ ４ ０．２１０ １ Ｃａｎｂｅ ４．１９８ ９ ２．３８３ １ １．０１４ ０ ０．６８１ ２ Ｃｏｓｉｎｅ ０．８４８ ６ ０．９４８ ５ ０．９８８ １ ０．９９４６ Ｉｎｔｅｒｓｅ ０．７７２ ７ ０．８７５ ９ ０．９４２ ８ ０．９６２４ 表 ４ 数据集 Ｙｅａｓｔ⁃ｃｄｃ 的实验结果 Ｔａｂｌｅ ４ Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｏｆ Ｙｅａｓｔ⁃ｃｄｃ 评价标准 ＰＴ⁃Ｂａｙｅｓ ＡＡ⁃ＢＰ ＳＡ⁃ＩＩＳ ＬＤＬＫＭ Ｃｈｅｂｙ ０．１１２４ ０．０３９３ ０．０２３３ ０．０１６ ２ Ｃｌａｒｋ １．０７５ ８ ０．６０７ ３ ０．２９２ ６ ０．２１５ ８ Ｃａｎｂｅ ３．５２６ ３ １．８２９ ８ ０．８９７ ６ ０．６４６７ Ｃｏｓｉｎｅ ０．８４９ １ ０．９５５ ０ ０．９８７ ０ ０．９９３ ３ Ｉｎｔｅｒｓｅ ０．７７１ ２ ０．８８５ １ ０．９３９ ７ ０．９５７ ５ 表 ５ 数据集 Ｙｅａｓｔ⁃ｅｌｕ 的实验结果 Ｔａｂｌｅ ５ Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｏｆ Ｙｅａｓｔ⁃ｅｌｕ 评价标准 ＰＴ⁃Ｂａｙｅｓ ＡＡ⁃ＢＰ ＳＡ⁃ＩＩＳ ＬＤＬＫＭ Ｃｈｅｂｙ ０．１０９ ８ ０．０３８ ８ ０．０２４ ０ ０．０１６ ３ Ｃｌａｒｋ １．０１４ ９ ０．５４３ ８ ０．２７５ ６ ０．１９９ ５ Ｃａｎｂｅ ３．２１１ ９ １．５８４ １ ０．８２３ ９ ０．５８５ ５ Ｃｏｓｉｎｅ ０．８５７ ２ ０．９６０ ０ ０．９８７ ６ ０．９９４ ０ Ｉｎｔｅｒｓｅ ０．７７７ ６ ０．８９３ ０ ０．９４０ ６ ０．９５８ ７ 第 ３ 期 邵东恒，等：应用 ｋ⁃ｍｅａｎｓ 算法实现标记分布学习 ·３２９·
·330 智能 系统学报 第12卷 表6数据集JAFE的实验结果 表8数据集Movie的实验结果 Table 6 The experimental results of JAFFE Table 8 The experimental results of Movie 评价标准 PT-Bayes AA-BP SA-IIS LDLKM 评价标准 PT-Bayes AA-BP SA-IIS LDLKM Cheby 0.1205 0.1403 0.1191 0.1179 Cheby 0.1992 0.1385 0.1467 0.1293 Clark 0.4394 0.5350 0.4246 0.4164 Clark 0.8003 0.6386 0.5806 0.5872 Canbe 0.9009 1.1022 0.8863 0.8660 Canbe 1.5490 1.2191 1.1158 1.1238 Cosine 0.9303 0.8950 0.9317 0.9288 Cosine 0.8506 0.9035 0.9088 0.9183 Interse 0.8465 0.8426 0.8490 0.8505 Interse 0.72450.79890.8041 0.8124 表7数据集Human Gene的实验结果 Table 7 The experimental results of Human Gene 4种标记分布算法在6个数据集上的预测结果 如图2所示，内容是标记分布算法对数据集中某个 评价标准 PT-Bayes AA-BP SA-IIS LDLKM 实例的标记分布预测结果和实际标记分布的比较。 Cheby 0.1834 0.0630 0.0534 0.0533 从图2中可以看出，LDLKM的预测结果与实际标记 Clark 4.6808 3.6789 2.1277 2.1133 分布最为接近，曲线的形状最为相似，即预测效果 Canbe 34.217825.229714.5778 14.4642 最好。在实验过程中，由于LDLKM直接利用了特 Cosine 0.4528 0.6900 0.8329 0.8348 征与标记之间的分布关系，训练模型的时间比现有 的专用化的算法还要少。 Interse 0.4696 0.63770.7824 0.7844 -origin ●Kmean 0.10 -Bayes 0.25 0.09 -BP -origin 0.08 x-IIS 0.20 ◆-Kmean 0.07 Bayes 号0.06 -BP 0.15 0.05单 -lIS ≤0.04 0.10 0.03 0.02 0.0 0.01 0 4 681012141618 6 8 10 121416 标记数 标记数 (a)Yeast-alpha数据集上的预测结果 (b)Yeast-cdc数据集上的预测结果 0.50 origin 0.30 origin 0.45 ●Kmean 0.28 ●-Kmean 0.40 Bayes 0.26 Baves 0.35 BP 0.24 BP --IIS 0.30 0.22 0.25 0.20 0.20 0.18 0.15 0.16 0.10 0.14 0.05 0.12 0.10 1.5 2.0 2.53.0 3.54.0 .01.52.02.53.03.54.04.55.05.56.0 标记数 标已数 (c)Yeast-.elu数据集上的预测结果 (d)JAFE数据集上的预测结果
表 ６ 数据集 ＪＡＦＦＥ 的实验结果 Ｔａｂｌｅ ６ Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｏｆ ＪＡＦＦＥ 评价标准 ＰＴ⁃Ｂａｙｅｓ ＡＡ⁃ＢＰ ＳＡ⁃ＩＩＳ ＬＤＬＫＭ Ｃｈｅｂｙ ０．１２０５ ０．１４０３ ０．１１９１ ０．１１７ ９ Ｃｌａｒｋ ０．４３９ ４ ０．５３５ ０ ０．４２４ ６ ０．４１６ ４ Ｃａｎｂｅ ０．９００ ９ １．１０２ ２ ０．８８６ ３ ０．８６６ ０ Ｃｏｓｉｎｅ ０．９３０ ３ ０．８９５ ０ ０．９３１ ７ ０．９２８８ Ｉｎｔｅｒｓｅ ０．８４６ ５ ０．８４２ ６ ０．８４９ ０ ０．８５０ ５ 表 ７ 数据集 Ｈｕｍａｎ Ｇｅｎｅ 的实验结果 Ｔａｂｌｅ ７ Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｏｆ Ｈｕｍａｎ Ｇｅｎｅ 评价标准 ＰＴ⁃Ｂａｙｅｓ ＡＡ⁃ＢＰ ＳＡ⁃ＩＩＳ ＬＤＬＫＭ Ｃｈｅｂｙ ０．１８３ ４ ０．０６３ ０ ０．０５３ ４ ０．０５３ ３ Ｃｌａｒｋ ４．６８０ ８ ３．６７８ ９ ２．１２７ ７ ２．１１３ ３ Ｃａｎｂｅ ３４．２１７ ８ ２５．２２９ ７ １４．５７７ ８ １４．４６４ ２ Ｃｏｓｉｎｅ ０．４５２ ８ ０．６９０ ０ ０．８３２ ９ ０．８３４ ８ Ｉｎｔｅｒｓｅ ０．４６９ ６ ０．６３７ ７ ０．７８２ ４ ０．７８４ ４ 表 ８ 数据集 Ｍｏｖｉｅ 的实验结果 Ｔａｂｌｅ ８ Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｏｆ Ｍｏｖｉｅ 评价标准 ＰＴ⁃Ｂａｙｅｓ ＡＡ⁃ＢＰ ＳＡ⁃ＩＩＳ ＬＤＬＫＭ Ｃｈｅｂｙ ０．１９９ ２ ０．１３８ ５ ０．１４６ ７ ０．１２９ ３ Ｃｌａｒｋ ０．８００ ３ ０．６３８ ６ ０．５８０ ６ ０．５８７ ２ Ｃａｎｂｅ １．５４９ ０ １．２１９ １ １．１１５ ８ １．１２３ ８ Ｃｏｓｉｎｅ ０．８５０ ６ ０．９０３ ５ ０．９０８ ８ ０．９１８ ３ Ｉｎｔｅｒｓｅ ０．７２４ ５ ０．７９８ ９ ０．８０４ １ ０．８１２ ４ ４ 种标记分布算法在 ６ 个数据集上的预测结果 如图 ２ 所示，内容是标记分布算法对数据集中某个 实例的标记分布预测结果和实际标记分布的比较。 从图 ２ 中可以看出，ＬＤＬＫＭ 的预测结果与实际标记 分布最为接近，曲线的形状最为相似，即预测效果 最好。 在实验过程中，由于 ＬＤＬＫＭ 直接利用了特 征与标记之间的分布关系，训练模型的时间比现有 的专用化的算法还要少。 （ａ）Ｙｅａｓｔ⁃ａｌｐｈａ 数据集上的预测结果 （ｂ）Ｙｅａｓｔ⁃ｃｄｃ 数据集上的预测结果 （ｃ）Ｙｅａｓｔ⁃ｅｌｕ 数据集上的预测结果 （ｄ）ＪＡＦＦＥ 数据集上的预测结果 ·３３０· 智 能 系 统 学 报 第 １２ 卷
第3期 邵东恒，等：应用k-neans算法实现标记分布学习 ·331· 0.50 origin 0.15 -origin 0.45 。Kmean ●-Kmean 0.40 -Bayes Bayes -BP 0.35 平BP 0.10 -IIS -0-IS 0.30 0.25 始 0.05 0.15 0.10形 0.05 6 81012141618 1.01.52.02.53.03.54.04.55.0 标记数 标记数 (e)Human-Gene数据集上的预测结果 (f)Movie数据集上的预测结果 图24种标记分布算法在6个公开数据集上预测结果 Fig.2 The prediction distribution of four LDL algorithms on six datasets classification:an overview[J].International journal of data 4 结束语 warehousing and mining,2007,3(3):1-13 本文提出的基于k-means标记分布学习算法， [4]READ J,PFAHRINGER B,HOLMES G.et al.Classifier 是在标记分布框架下，利用标记分布和样本集所具 chains for multi-label classification[J].Machine learning, 有的联系，通过求得一个权重矩阵来得到预测标记 2011,85(3):333-359 [5]READ J,PFAHRINGER B,HOLMES G.Multi-label 分布，而不是与现有的算法一样，通过求每一个标 classification using ensembles of pruned sets [C]// 记的条件概率来得到预测标记分布。LDLKM主要 Proceedings of Eighth IEEE International Conference on 通过将训练集的样本作为k-means聚类的样本，获 Data Mining,Pisa,Italy,2008.Washington,USA:IEEE 得每个簇的均值向量。然后将求得的测试集样本 Computer Society,2008:995-1000. 与均值向量的距离矩阵，作为预测标记分布与训练 [6]EISEN M B,SPELLMAN P T,BROWN P O,et al.Cluster 集对应的标记分布间的关系，直接求得所需的预测 analysis and display of genome-wide expression patterns[J]. 标记分布。本算法充分利用了特征和标记之间的 Proceedings of the national academy of sciences of the 分布关系，又通过softmax函数减小了与测试样本距 united states of America,1998,95(25):14863-14868. 离较远的均值向量的影响，同时本算法相对于现有 [7]Geng X.Label distribution learning[J].IEEE transactions 的专门化的算法在较大的数据集上花费的时间更 on knowledge and data engineering,2014,28 (7): 少。在公开的6个数据集上进行的实验所得的结果 1734-1748. [8]季荣姿.标记分布学习及其应用[D].南京：东南大 说明，本文提出的基于k-means的标记分布学习算 学，2014. 法是有效的。在以后的工作中，我们将对算法进一 JI Rongzi.Label distribution learning and its application 步优化，还可以引入集成学习来强化聚类效果，或 [D].Nanjing:Southeast University,2014. 采用一种改进的聚类算法[2]，或针对标记分布学习 [9]ZHANG Z,WANG M,GENG X.Crowd counting in public 的特性来专门设计一个聚类算法。 video surveillance by label distribution learning [J]. 参考文献： Neurocomputing,2015,166(C):151-163. [10]GENG X,WANG Q,XIA Y.Facial age estimation by [1]ZHANG M L.ZHOU Z H.A review on multi-label learning adaptive label distribution learning[C]//Proceedings of algorithms[J].IEEE transactions on knowledge and data IEEE International Conference on Pattern Recognition, engineering,2014,26(8):1819-1837. Stockholm,Sweden,2014.Washington,USA:IEEE [2]WEI Yunchao,XIA Wei,HUANG Junshi,et al.CNN: Computer Society,2014:4465-4470. Single-label to multi-label[J].Computer science,2014,11: [11]GENG X,XIA Y.Head pose estimation based on 26-56. multivariate label distribution C//Proceedings of IEEE [3]TSOUMAKAS G,KATAKIS I,TANIAR D.Multi-label International Conference on Computer Vision and Pattern
（ｅ）Ｈｕｍａｎ⁃Ｇｅｎｅ 数据集上的预测结果 （ｆ）Ｍｏｖｉｅ 数据集上的预测结果 图 ２ ４ 种标记分布算法在 ６ 个公开数据集上预测结果 Ｆｉｇ．２ Ｔｈｅ ｐｒｅｄｉｃｔｉｏｎ ｄｉｓｔｒｉｂｕｔｉｏｎ ｏｆ ｆｏｕｒ ＬＤＬ ａｌｇｏｒｉｔｈｍｓ ｏｎ ｓｉｘ ｄａｔａｓｅｔｓ ４ 结束语 本文提出的基于 ｋ⁃ｍｅａｎｓ 标记分布学习算法， 是在标记分布框架下，利用标记分布和样本集所具 有的联系，通过求得一个权重矩阵来得到预测标记 分布，而不是与现有的算法一样，通过求每一个标 记的条件概率来得到预测标记分布。 ＬＤＬＫＭ 主要 通过将训练集的样本作为 ｋ⁃ｍｅａｎｓ 聚类的样本，获 得每个簇的均值向量。 然后将求得的测试集样本 与均值向量的距离矩阵，作为预测标记分布与训练 集对应的标记分布间的关系，直接求得所需的预测 标记分布。 本算法充分利用了特征和标记之间的 分布关系，又通过 ｓｏｆｔｍａｘ 函数减小了与测试样本距 离较远的均值向量的影响，同时本算法相对于现有 的专门化的算法在较大的数据集上花费的时间更 少。 在公开的 ６ 个数据集上进行的实验所得的结果 说明，本文提出的基于 ｋ⁃ｍｅａｎｓ 的标记分布学习算 法是有效的。 在以后的工作中，我们将对算法进一 步优化，还可以引入集成学习来强化聚类效果，或 采用一种改进的聚类算法［２５］ ，或针对标记分布学习 的特性来专门设计一个聚类算法。 参考文献： ［１］ＺＨＡＮＧ Ｍ Ｌ， ＺＨＯＵ Ｚ Ｈ． Ａ ｒｅｖｉｅｗ ｏｎ ｍｕｌｔｉ⁃ｌａｂｅｌ ｌｅａｒｎｉｎｇ ａｌｇｏｒｉｔｈｍｓ［ Ｊ］． ＩＥＥＥ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｋｎｏｗｌｅｄｇｅ ａｎｄ ｄａｔａ ｅｎｇｉｎｅｅｒｉｎｇ， ２０１４， ２６（８）： １８１９－１８３７． ［２］ ＷＥＩ Ｙｕｎｃｈａｏ， ＸＩＡ Ｗｅｉ， ＨＵＡＮＧ Ｊｕｎｓｈｉ， ｅｔ ａｌ． ＣＮＮ： Ｓｉｎｇｌｅ⁃ｌａｂｅｌ ｔｏ ｍｕｌｔｉ⁃ｌａｂｅｌ［Ｊ］． Ｃｏｍｐｕｔｅｒ ｓｃｉｅｎｃｅ， ２０１４，１１： ２６－５６． ［ ３］ ＴＳＯＵＭＡＫＡＳ Ｇ， ＫＡＴＡＫＩＳ Ｉ， ＴＡＮＩＡＲ Ｄ． Ｍｕｌｔｉ⁃ｌａｂｅｌ ｃｌａｓｓｉｆｉｃａｔｉｏｎ： ａｎ ｏｖｅｒｖｉｅｗ［ Ｊ］． Ｉｎｔｅｒｎａｔｉｏｎａｌ ｊｏｕｒｎａｌ ｏｆ ｄａｔａ ｗａｒｅｈｏｕｓｉｎｇ ａｎｄ ｍｉｎｉｎｇ， ２００７， ３（３）： １－１３． ［４］ＲＥＡＤ Ｊ， ＰＦＡＨＲＩＮＧＥＲ Ｂ， ＨＯＬＭＥＳ Ｇ， ｅｔ ａｌ． Ｃｌａｓｓｉｆｉｅｒ ｃｈａｉｎｓ ｆｏｒ ｍｕｌｔｉ－ｌａｂｅｌ ｃｌａｓｓｉｆｉｃａｔｉｏｎ［ Ｊ］． Ｍａｃｈｉｎｅ ｌｅａｒｎｉｎｇ， ２０１１， ８５（３）： ３３３－３５９． ［ ５ ］ ＲＥＡＤ Ｊ， ＰＦＡＨＲＩＮＧＥＲ Ｂ， ＨＯＬＭＥＳ Ｇ． Ｍｕｌｔｉ⁃ｌａｂｅｌ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ｕｓｉｎｇ ｅｎｓｅｍｂｌｅｓ ｏｆ ｐｒｕｎｅｄ ｓｅｔｓ ［ Ｃ ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ Ｅｉｇｈｔｈ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｄａｔａ Ｍｉｎｉｎｇ， Ｐｉｓａ， Ｉｔａｌｙ， ２００８． Ｗａｓｈｉｎｇｔｏｎ， ＵＳＡ： ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ， ２００８： ９９５－１０００． ［６］ＥＩＳＥＮ Ｍ Ｂ， ＳＰＥＬＬＭＡＮ Ｐ Ｔ， ＢＲＯＷＮ Ｐ Ｏ， ｅｔ ａｌ． Ｃｌｕｓｔｅｒ ａｎａｌｙｓｉｓ ａｎｄ ｄｉｓｐｌａｙ ｏｆ ｇｅｎｏｍｅ⁃ｗｉｄｅ ｅｘｐｒｅｓｓｉｏｎ ｐａｔｔｅｒｎｓ［Ｊ］． Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ｎａｔｉｏｎａｌ ａｃａｄｅｍｙ ｏｆ ｓｃｉｅｎｃｅｓ ｏｆ ｔｈｅ ｕｎｉｔｅｄ ｓｔａｔｅｓ ｏｆ Ａｍｅｒｉｃａ， １９９８， ９５（２５）： １４８６３－１４８６８． ［７］Ｇｅｎｇ Ｘ． Ｌａｂｅｌ ｄｉｓｔｒｉｂｕｔｉｏｎ ｌｅａｒｎｉｎｇ［ Ｊ］． ＩＥＥＥ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｋｎｏｗｌｅｄｇｅ ａｎｄ ｄａｔａ ｅｎｇｉｎｅｅｒｉｎｇ， ２０１４， ２８ （ ７ ）： １７３４－１７４８． ［８］ 季荣姿． 标记分布学习及其应用［ Ｄ］． 南京：东南大 学， ２０１４． ＪＩ Ｒｏｎｇｚｉ． Ｌａｂｅｌ ｄｉｓｔｒｉｂｕｔｉｏｎ ｌｅａｒｎｉｎｇ ａｎｄ ｉｔｓ ａｐｐｌｉｃａｔｉｏｎ ［Ｄ］．Ｎａｎｊｉｎｇ： Ｓｏｕｔｈｅａｓｔ Ｕｎｉｖｅｒｓｉｔｙ， ２０１４． ［９］ＺＨＡＮＧ Ｚ， ＷＡＮＧ Ｍ， ＧＥＮＧ Ｘ． Ｃｒｏｗｄ ｃｏｕｎｔｉｎｇ ｉｎ ｐｕｂｌｉｃ ｖｉｄｅｏ ｓｕｒｖｅｉｌｌａｎｃｅ ｂｙ ｌａｂｅｌ ｄｉｓｔｒｉｂｕｔｉｏｎ ｌｅａｒｎｉｎｇ ［ Ｊ ］． Ｎｅｕｒｏｃｏｍｐｕｔｉｎｇ， ２０１５， １６６（Ｃ）： １５１－１６３． ［１０］ ＧＥＮＧ Ｘ， ＷＡＮＧ Ｑ， ＸＩＡ Ｙ． Ｆａｃｉａｌ ａｇｅ ｅｓｔｉｍａｔｉｏｎ ｂｙ ａｄａｐｔｉｖｅ ｌａｂｅｌ ｄｉｓｔｒｉｂｕｔｉｏｎ ｌｅａｒｎｉｎｇ［ Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｐａｔｔｅｒｎ Ｒｅｃｏｇｎｉｔｉｏｎ， Ｓｔｏｃｋｈｏｌｍ， Ｓｗｅｄｅｎ， ２０１４． Ｗａｓｈｉｎｇｔｏｎ， ＵＳＡ： ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ， ２０１４： ４４６５－４４７０． ［ １１ ］ ＧＥＮＧ Ｘ， ＸＩＡ Ｙ． Ｈｅａｄ ｐｏｓｅ ｅｓｔｉｍａｔｉｏｎ ｂａｓｅｄ ｏｎ ｍｕｌｔｉｖａｒｉａｔｅ ｌａｂｅｌ ｄｉｓｔｒｉｂｕｔｉｏｎ ［ Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ Ｖｉｓｉｏｎ ａｎｄ Ｐａｔｔｅｒｎ 第 ３ 期 邵东恒，等：应用 ｋ⁃ｍｅａｎｓ 算法实现标记分布学习 ·３３１·
.332. 智能系统学报 第12卷 Recognition,Columbus,USA,2014.Washington,USA: [22]CHA S H.Comprehensive survey on distance/similarity IEEE Computer Society,2014:1837-1842. measures between probability density functions [J.Intemational [12]GENG X,HOU P.Pre-release prediction of crowd opinion joumal of mathematical models and methods in applied sciences. on movies by label distribution learning[C]//Proceedings 2007.1(4):300-307. of the International Joint Conference on Artificial [23 AHONEN T,HADID A,PIETIKAINEN M.Face Intelligence,Buenos Aires,Argentina,2015.San description with local binary patterns:application to face Francisco,USA:Morgan Kaufmann,2015:3511-3517. recognition[J].IEEE trans pattern anal mach intell, [13]GENG X,YIN C,ZHOU Z H.Facial age estimation by 2006,28(12):2037-2041. learning from label distributions.[].IEEE transactions on [24]YU J F,JIANG D K,XIAO K,et al.Discriminate the falsely pattern analysis and machine intelligence,2013,35(10): predicted protein-coding genes in Aeropyrum Pemix KI 2401-2412. genome based on graphical representation [J].Match [14]JAIN A K.Data clustering:a review[J].ACM computing communications in mathematical and in computer chemistry, survey8,1999,31(3):264-323. 2012,67(3):845-866. [15]程肠，王士同.基于局部保留投影的多可选聚类发掘算 [25]周治平，王杰锋，朱书伟，等.一种改进的自适应快速 法[J].智能系统学报，2016,11(5)：600-607. AF-DBSCAN聚类算法[J].智能系统学报，2016,11 CHENG Yang,WANG Shitong.A multiple alternative (1):93-98. clusterings mining algorithm using locality preserving ZHOU Zhiping,WANG Jiefeng,ZHU Shuwei,et al.An projections[].CAAI transactions on intelligent systems, improved adaptive and fast AF-DBSCAN clustering 2016,11(5):600-607. algorithm[J].CAAI transaction on intelligent systems, [16]HARTIGAN J A,WONG M A.A &-means clustering 2016,11(1):93-98. algorithm[J].Applied statistics,2013,28(1):100-108. 作者简介： [17]申彦，朱玉全.CMP上基于数据集划分的k-means多 邵东恒，男，1992年生，硕士研究 核优化算法[J].智能系统学报，2015(4)：607-614. 生，主要研究方向为标记分布学习。 SHEN Yan,ZHU Yuquan.An optimized algorithm of means based on data set partition on CMP systems[J]. CAAI transactions on intelligent systems,2015,10(4): 607-614. [18]GROENEN P J F,KAYMAK U,VAN Rosmalen J.Fuzzy 杨文元.男.1967年生，副教授，博 clustering with minkowski distance functions [J].Fuzzy 士，主要研究方向为机器学习、标记分 sets and systems,2001,120(2):227-237. 布学习。发表学术论文20余篇。 [19]赵权，耿新.标记分布学习中目标函数的选择[J].计 算机科学与探索，2017,11(5)：1-12. ZHAO Quan,GENG Xin.Selection of target function in label distribution learning [J].Journal of frontiers of computer science and technology,2017,11(5):1-12. 赵红，女，1979年生，副教授，主要 研究方向为粒计算、分层分类学习。发 [20]周志华.机器学习[M].北京：清华大学出版社，2016 表学术论文40余篇。 [21]ALOISE D,DESHPANDE A,HANSEN P,et al.NP- hardness of euclidean sum-of-squares clustering [J]. Machine learning,2009,75(2):245-248
Ｒｅｃｏｇｎｉｔｉｏｎ， Ｃｏｌｕｍｂｕｓ， ＵＳＡ， ２０１４． Ｗａｓｈｉｎｇｔｏｎ， ＵＳＡ： ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ， ２０１４：１８３７－１８４２． ［１２］ＧＥＮＧ Ｘ， ＨＯＵ Ｐ． Ｐｒｅ⁃ｒｅｌｅａｓｅ ｐｒｅｄｉｃｔｉｏｎ ｏｆ ｃｒｏｗｄ ｏｐｉｎｉｏｎ ｏｎ ｍｏｖｉｅｓ ｂｙ ｌａｂｅｌ ｄｉｓｔｒｉｂｕｔｉｏｎ ｌｅａｒｎｉｎｇ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｉｎｔ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ａｒｔｉｆｉｃｉａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ， Ｂｕｅｎｏｓ Ａｉｒｅｓ， Ａｒｇｅｎｔｉｎａ， ２０１５． Ｓａｎ Ｆｒａｎｃｉｓｃｏ， ＵＳＡ：Ｍｏｒｇａｎ Ｋａｕｆｍａｎｎ， ２０１５： ３５１１－３５１７． ［１３］ ＧＥＮＧ Ｘ， ＹＩＮ Ｃ， ＺＨＯＵ Ｚ Ｈ． Ｆａｃｉａｌ ａｇｅ ｅｓｔｉｍａｔｉｏｎ ｂｙ ｌｅａｒｎｉｎｇ ｆｒｏｍ ｌａｂｅｌ ｄｉｓｔｒｉｂｕｔｉｏｎｓ．［Ｊ］． ＩＥＥＥ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｐａｔｔｅｒｎ ａｎａｌｙｓｉｓ ａｎｄ ｍａｃｈｉｎｅ ｉｎｔｅｌｌｉｇｅｎｃｅ， ２０１３， ３５（１０）： ２４０１－２４１２． ［１４］ＪＡＩＮ Ａ Ｋ． Ｄａｔａ ｃｌｕｓｔｅｒｉｎｇ： ａ ｒｅｖｉｅｗ［Ｊ］． ＡＣＭ ｃｏｍｐｕｔｉｎｇ ｓｕｒｖｅｙｓ， １９９９， ３１（３）： ２６４－３２３． ［１５］程旸， 王士同． 基于局部保留投影的多可选聚类发掘算 法［Ｊ］． 智能系统学报， ２０１６， １１（５）： ６００－６０７． ＣＨＥＮＧ Ｙａｎｇ， ＷＡＮＧ Ｓｈｉｔｏｎｇ． Ａ ｍｕｌｔｉｐｌｅ ａｌｔｅｒｎａｔｉｖｅ ｃｌｕｓｔｅｒｉｎｇｓ ｍｉｎｉｎｇ ａｌｇｏｒｉｔｈｍ ｕｓｉｎｇ ｌｏｃａｌｉｔｙ ｐｒｅｓｅｒｖｉｎｇ ｐｒｏｊｅｃｔｉｏｎｓ［Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， ２０１６， １１（５）： ６００－６０７． ［１６］ ＨＡＲＴＩＧＡＮ Ｊ Ａ， ＷＯＮＧ Ｍ Ａ． Ａ ｋ⁃ｍｅａｎｓ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ［Ｊ］． Ａｐｐｌｉｅｄ ｓｔａｔｉｓｔｉｃｓ， ２０１３， ２８（１）： １００－１０８． ［１７］申彦， 朱玉全． ＣＭＰ 上基于数据集划分的 ｋ－ｍｅａｎｓ 多 核优化算法［Ｊ］． 智能系统学报， ２０１５（４）：６０７－６１４． ＳＨＥＮ Ｙａｎ， ＺＨＵ Ｙｕｑｕａｎ． Ａｎ ｏｐｔｉｍｉｚｅｄ ａｌｇｏｒｉｔｈｍ ｏｆ ｋ － ｍｅａｎｓ ｂａｓｅｄ ｏｎ ｄａｔａ ｓｅｔ ｐａｒｔｉｔｉｏｎ ｏｎ ＣＭＰ ｓｙｓｔｅｍｓ ［ Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， ２０１５， １０ （ ４）： ６０７－６１４． ［１８］ＧＲＯＥＮＥＮ Ｐ Ｊ Ｆ， ＫＡＹＭＡＫ Ｕ， ＶＡＮ Ｒｏｓｍａｌｅｎ Ｊ． Ｆｕｚｚｙ ｃｌｕｓｔｅｒｉｎｇ ｗｉｔｈ ｍｉｎｋｏｗｓｋｉ ｄｉｓｔａｎｃｅ ｆｕｎｃｔｉｏｎｓ ［ Ｊ］． Ｆｕｚｚｙ ｓｅｔｓ ａｎｄ ｓｙｓｔｅｍｓ， ２００１， １２０（２）： ２２７－２３７． ［１９］赵权， 耿新． 标记分布学习中目标函数的选择［ Ｊ］． 计 算机科学与探索， ２０１７，１１（５）： １－１２． ＺＨＡＯ Ｑｕａｎ， ＧＥＮＧ Ｘｉｎ． Ｓｅｌｅｃｔｉｏｎ ｏｆ ｔａｒｇｅｔ ｆｕｎｃｔｉｏｎ ｉｎ ｌａｂｅｌ ｄｉｓｔｒｉｂｕｔｉｏｎ ｌｅａｒｎｉｎｇ ［ Ｊ ］． Ｊｏｕｒｎａｌ ｏｆ ｆｒｏｎｔｉｅｒｓ ｏｆ ｃｏｍｐｕｔｅｒ ｓｃｉｅｎｃｅ ａｎｄ ｔｅｃｈｎｏｌｏｇｙ， ２０１７，１１（５）： １－１２． ［２０］周志华． 机器学习［Ｍ］． 北京：清华大学出版社， ２０１６． ［２１］ ＡＬＯＩＳＥ Ｄ， ＤＥＳＨＰＡＮＤＥ Ａ， ＨＡＮＳＥＮ Ｐ， ｅｔ ａｌ． ＮＰ － ｈａｒｄｎｅｓｓ ｏｆ ｅｕｃｌｉｄｅａｎ ｓｕｍ⁃ｏｆ⁃ｓｑｕａｒｅｓ ｃｌｕｓｔｅｒｉｎｇ ［ Ｊ ］． Ｍａｃｈｉｎｅ ｌｅａｒｎｉｎｇ， ２００９， ７５（２）： ２４５－２４８． ［ ２２ ］ ＣＨＡ Ｓ Ｈ． Ｃｏｍｐｒｅｈｅｎｓｉｖｅ ｓｕｒｖｅｙ ｏｎ ｄｉｓｔａｎｃｅ ／ ｓｉｍｉｌａｒｉｔｙ ｍｅａｓｕｒｅｓ ｂｅｔｗｅｅｎ ｐｒｏｂａｂｉｌｉｔｙ ｄｅｎｓｉｔｙ ｆｕｎｃｔｉｏｎｓ ［Ｊ］． Ｉｎｔｅｒｎａｔｉｏｎａｌ ｊｏｕｒｎａｌ ｏｆ ｍａｔｈｅｍａｔｉｃａｌ ｍｏｄｅｌｓ ａｎｄ ｍｅｔｈｏｄｓ ｉｎ ａｐｐｌｉｅｄ ｓｃｉｅｎｃｅｓ， ２００７， １（４）： ３００－３０７． ［ ２３ ］ ＡＨＯＮＥＮ Ｔ， ＨＡＤＩＤ Ａ， ＰＩＥＴＩＫÄＩＮＥＮ Ｍ． Ｆａｃｅ ｄｅｓｃｒｉｐｔｉｏｎ ｗｉｔｈ ｌｏｃａｌ ｂｉｎａｒｙ ｐａｔｔｅｒｎｓ： ａｐｐｌｉｃａｔｉｏｎ ｔｏ ｆａｃｅ ｒｅｃｏｇｎｉｔｉｏｎ ［ Ｊ ］． ＩＥＥＥ ｔｒａｎｓ ｐａｔｔｅｒｎ ａｎａｌ ｍａｃｈ ｉｎｔｅｌｌ， ２００６， ２８（１２）： ２０３７－２０４１． ［２４］ＹＵ Ｊ Ｆ， ＪＩＡＮＧ Ｄ Ｋ， ＸＩＡＯ Ｋ， ｅｔ ａｌ． Ｄｉｓｃｒｉｍｉｎａｔｅ ｔｈｅ ｆａｌｓｅｌｙ ｐｒｅｄｉｃｔｅｄ ｐｒｏｔｅｉｎ⁃ｃｏｄｉｎｇ ｇｅｎｅｓ ｉｎ Ａｅｒｏｐｙｒｕｍ Ｐｅｒｎｉｘ Ｋ１ ｇｅｎｏｍｅ ｂａｓｅｄ ｏｎ ｇｒａｐｈｉｃａｌ ｒｅｐｒｅｓｅｎｔａｔｉｏｎ ［ Ｊ ］． Ｍａｔｃｈ ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ｉｎ ｍａｔｈｅｍａｔｉｃａｌ ａｎｄ ｉｎ ｃｏｍｐｕｔｅｒ ｃｈｅｍｉｓｔｒｙ， ２０１２， ６７（３）： ８４５－８６６． ［２５］周治平， 王杰锋， 朱书伟，等． 一种改进的自适应快速 ＡＦ⁃ＤＢＳＣＡＮ 聚类算法［ Ｊ］． 智能系统学报， ２０１６， １１ （１）：９３－９８． ＺＨＯＵ Ｚｈｉｐｉｎｇ， ＷＡＮＧ Ｊｉｅｆｅｎｇ， ＺＨＵ Ｓｈｕｗｅｉ， ｅｔ ａｌ． Ａｎ ｉｍｐｒｏｖｅｄ ａｄａｐｔｉｖｅ ａｎｄ ｆａｓｔ ＡＦ⁃ＤＢＳＣＡＮ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ［ Ｊ ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， ２０１６， １１（１）： ９３－９８． 作者简介： 邵东恒，男，１９９２ 年生，硕士研究 生，主要研究方向为标记分布学习。 杨文元，男，１９６７ 年生，副教授，博 士，主要研究方向为机器学习、标记分 布学习。 发表学术论文 ２０ 余篇。 赵红，女，１９７９ 年生，副教授，主要 研究方向为粒计算、分层分类学习。 发 表学术论文 ４０ 余篇。 ·３３２· 智 能 系 统 学 报 第 １２ 卷