计  算  机  学  报  2019 年  relatedness among the tasks to avoid negative transfer. Nevertheless, existing multi-task clustering methods have not  accomplished  either  of  them  well.  This  paper  proposes  a  weighted  multi-task  clustering  method  based  on feature and instance transfer, which is called as MTCFIR. On one hand, MTCFIR transfers both the knowledge of feature representation and instances across the related tasks, thus making better use of the cross-task knowledge than  most  existing  multi-task  clustering  methods.  On  the  other  hand,  MTCFIR  automatically  learns  the  task relatedness  to  avoid  negative  transfer,  and  it  does  not  have  the  limitations  of  the  existing  multi-task  clustering methods which can assess the task relatedness, e.g., all the tasks should have the same cluster numbers, and the label marginal distribution in each task distributes evenly. There are three steps in the MTCFIR method. First, it learns a common feature representation among the related tasks with marginalized stacked denoising autoencoders (SDA). SDA can abstract a set of high-level features that indicate the generic concepts, learning these features for multi-task  data  is  beneficial  to  extract  commonality  from  the  original  features  in  different  tasks.  This  step  can reduce the distribution difference among the tasks by transferring the knowledge of feature representations, which is  the  premise  of  learning  the  consistent  similarity  matrix  in  the  second  step.  Second,  it  learns  a  consistent similarity matrix for each task by transferring the instance knowledge across the related tasks, and determines the contribution degree of different tasks for learning the consistent similarity  matrix of each task by weighting the tasks. This step can avoid the negative effects caused by enforcing the knowledge transfer among the tasks that are not too related, thus taking full advantage of the relevant instance knowledge among the tasks. Third, it performs the symmetric nonnegative matrix factorization (SNMF) on the consistent similarity matrix of each task to get the clustering  results.  SNMF  is  a  clustering  technique  which  can  capture  the  cluster  structure  embedded  into  the similarity  matrix. Experimental results on several real  world data sets show that the proposed method MTCFIR performs much better than traditional single-task clustering methods and existing multi-task clustering methods, and is more efficient than existing multi-task clustering methods in general. The learned task relatedness shown in the experiments further verify the effectiveness of the proposed MTCFIR. Key words  multi-task  clustering;  feature  representation  transfer;  instance  transfer;  task  relatedness  learning; consistent similarity matrix learning        1  引言 传统的聚类算法对一个单独的数据集进行聚类，但是一个数据集中的信息可能不足以挖掘正确的簇结构。多任务聚类以传统的聚类方法为手段，通过学习任务之间的相关知识并在任务之间迁移这些知识来提高每个任务的聚类性能。一个好的多任务聚类算法应该能够完成两方面的工作：（1）充分利用其它任务中的知识；（2）评估任务相关性来避免负面迁移问题[1]。然而，现有的多任务聚类算法并不能很好地完成这两个工作。 早期的多任务聚类算法通常基于一个理想的假设，即所有的任务是完全相关的（所有任务共享相同的簇标签），所以它们只能处理第一个工作。在多任务聚类中，主要有三种方式来迁移相关知识[1]：特征表示迁移在相关任务之间学习一个共有的特征表示；实例迁移利用其它任务中的相关实例来帮助每个任务进行聚类；模型参数迁移为所有任务学习它们的共享模型参数或者模型超参数的先验分布。早期的多任务聚类方法通常只能在任务之间迁移一种知识[2]。最近，以 MTCTKI[2]为代表的多任务聚类算法能够在任务之间同时迁移特征表示和实例知识，从而更充分地利用其它任务中的知识。 在现实生活中，任务通常是部分相关的（任务之间只共享一部分簇标签），强制地在部分相关任务之间迁移知识会降低任务的聚类性能。在任务之间迁移知识导致任务聚类性能变差的现象被称为负面迁移[1]。因此第二个工作对于多任务聚类算法是必不可少的。目前有两个代表性的多任务聚类算法可以自动评估任务的相关性。（1）DMTRC[3]通过高斯先验来学习任务相关性。但是它基于一个很严格的假设，即所有任务的聚类个数是相同的并且每个任务的簇标签边缘分布是均匀的。（2）SAMTC[4]为每对任务学习一对可能相关的子任务，然后评估计算机学报张晓彤等：基于特征和实例迁移的加权多任务聚类  3  每对子任务之间的相关性。但是它将子任务外的数据直接丢弃，这可能会丢失一些在其它任务中潜在相关的有用信息。 在本文中，我们提出了一个基于特征和实例迁移的加权多任务聚类算法 MTCFIR，它不仅能够在任务之间同时迁移特征表示和实例知识，并且能够自动地学习任务之间的相关性，从而避免负面迁移问题。MTCFIR 算法执行以下三个步骤：（1）共有特征表示学习：该步骤用边缘堆栈降噪自编码器方法 m SDA[5]来为所有任务学习一个共有的特征表示。该步骤通过迁移特征表示知识来降低任务之间的分布差异，这是一致相似度矩阵学习的前提。（2）一致相似度矩阵学习：该步骤通过在任务之间迁移实例知识来为每个任务学习一个一致相似度矩阵。同时该步骤自动学习任务相关性来对每个任务进行加权，以决定其它任务对于当前任务的一致相似度矩阵学习的贡献程度。（3）对称非负矩阵分解：该步骤对每个任务的一致相似度矩阵进行对称非负矩阵分解[6]，从而得到每个任务的聚类结果。在真 实 数 据 集 上的 实 验 结果 验 证 了 本 文提 出 的MTCFIR 算法相比于传统的单任务聚类算法和现有多任务聚类算法具有更好的聚类性能。 2  相关工作 2.1   多任务聚类 多任务聚类是一种无监督的多任务学习方法，它在近十年来获得了越来越多的关注。多任务聚类通过在相关任务之间迁移知识来提升每个任务的聚类性能。现有的多任务聚类算法有三种迁移知识的方式。 （1）特征表示迁移：该方式在任务之间学习一个共有的特征表示，这个共有特征表示会降低任务之间的分布差异。该方式基于相关任务之间通常会共享一些相同语义特征的观察。由于该共有特征表示是利用所有任务的特征知识一起学习出来的，因此不同任务的特征知识都融入到该共有特征表示中。之后每个任务都会用该共有特征表示重新进行特征构造，所以每个任务都会利用到其它任务中的特征知识，即该共有特征表示起到在任务之间迁移特征知识的作用。LSSMTC 算法[7]学习一个所有任 务 共 享 相 同 质 心 的 子 空 间 。 LNKMTC 和LSKMTC 算法[8]学习一个所有任务分布相近且保留原始数据几何结构的核空间。MCDA 算法[9]学习一个所有任务分布相近的共享子空间。ITCC 算法[10]利用信息论联合聚类为每对任务学习一个特征关联矩阵。 （2）实例迁移：该方式利用其它任务中的相关实例来帮助每个任务进行聚类。该方式基于相关任务之间会共享一些相同的簇标签，而不同任务之间具有相同簇标签的数据通常是相关的观察。MBC算法[11]和它的两个改进算法 S-MBC 和 S-MKC [12][13]交替进行簇质心学习和任务间质心相关性学习。SMT-NMF 算法[14]引入一个需要人工设置的任务间偏差来对不同任务之间的任意两个数据点的距离进行加权，但是该方法只能处理具有两个簇的任务。SAMTC 算法[4]首先通过可用实例寻找步骤来为每对任务构造一对子任务，然后学习每对子任务之间的相关性，最后其它子任务中的数据参与到每个任务共享最近邻相似度矩阵的计算中。 （3）模型参数迁移：该方式为所有任务学习一个共享模型参数或者模型超参数的先验分布。该方式基于相关任务之间会共享一些相同的簇标签，而任务之间相同簇标签所对应的模型参数应该是相似的观察。DMTFC 和 DMTRC 算法[3]分别学习特征相关性和任务相关性，这两种方法首先引入模型参数的高斯先验，然后通过计算高斯先验中的协方差矩阵来学习特征相关性和任务相关性。上述方法要求每个任务具有相同的簇个数，并且每个任务中的簇标签是均匀分布的，即每个任务中不同簇中的数据个数是相同的。MTSC[15]  为每个任务引入一个线性回归模型，然后在所有任务的模型参数上加入ℓ2,�范数正则化，从而使模型参数只在任务之间的某部分特征上进行迁移。 由于基于实例迁移和模型参数迁移的方法都是在没有考虑任务分布差异的情况下，直接在原始空间中迁移实例或模型参数知识的，因此这些方法更适合处理分布相近的任务。 最近的研究提出一种同时迁移特征表示和实例知识的 MTCTKI 算法[2]。它首先采用最大平均差异分布度量方法来学习一个任务分布互相接近的共享子空间。然后在这个共享子空间中，对于每个任务中的两个数据点，该方法通过利用它们在其它任务中的共享最近邻来参与计算它们的相似度。最后，该方法在每个任务的共享最近邻相似度矩阵上执行谱聚类来得到最终的聚类结果。但是，MTCTKI只考虑任务完全相关的情况，因此它在处理部分相关任务时，会强制其它任务中的实例知识完全参与计算机学报 计  算  机  学  报  2019 年  到每个任务的相似度矩阵学习中。 在上述多任务聚类算法中，大部分方法都是针对完全相关任务的，因此该类方法强制在任务之间迁移所有知识。但是在现实生活中，任务通常是部分相关的，这时在任务之间强制迁移所有知识会导致负面迁移问题[1]。一种避免负面迁移问题的手段是评估任务相关性，即通过任务相关性来控制任务之间知识的迁移量。在多任务聚类的文献中，以DMTRC[3]和 SAMTC[4]为代表的多任务聚类算法能够自动学习任务相关性，但是它们有一些限制条件。DMTRC 算法假设所有任务的聚类个数是相同的并且每个任务的各个簇具有相同的数据个数。SAMTC 算法直接丢弃了子任务外的数据，这可能会导致其它任务中潜在相关信息的丢失。此外，这两个算法直接在原始空间中迁移模型参数或实例知识，它们没有考虑任务的分布差异，因此更适合于处理分布差异较小的任务。 根据上述分析，现有的多任务聚类方法还不能够同时做到既迁移多种知识，又自动学习任务之间的相关性。为了解决这一问题，本文提出一个基于特征和实例迁移的加权多任务聚类算法 MTCFIR。一方面，通过同时迁移特征和实例知识，MTCFIR可以利用更多的任务间知识对每个任务进行聚类。另一方面，通过学习任务之间的相关性，MTCFIR可以只让一个任务中一定比例的实例知识迁移给另一个任务，从而避免负面迁移问题。 2.2   多任务学习 多任务学习（监督多任务学习）[16]比无监督的多任务聚类研究得更加成熟。多任务学习通过在任务之间迁移知识来提高所有任务的预测性能。与多任务聚类方法类似，多任务学习方法也主要迁移三种类型的知识：特征表示、实例和模型参数。 最近的多任务学习文献中也提出一种同时迁移特征表示和模型参数的多任务学习方法[17]，该方法可以充分利用任务之间的特征表示和模型参数知识，来提高每个任务的预测性能。 在多任务学习中，有很多方法都是针对部分相关任务而被提出来的。一种解决部分相关任务的方式是将任务划分成簇[18][19]，簇内的任务是相关的，不同簇中的任务是不相关的。因此该类方法只对每个簇内部的任务迁移知识，而不同簇中的任务不迁移任何知识。由于该类方法过于绝对地区分任务是相关或不相关的，这样的假设过于理想。另一种解决部分相关任务的方式是评估任务之间的相关性。一种评估任务相关性的方式是像 DMTRC 算法那样假设任务之间的模型参数共享高斯先验，然后通过学习协方差矩阵来学习任务之间的相关性[20][21]。另一种评估任务相关性的方式是假设有一个任务关联矩阵，然后在监督多任务学习过程中自动学习该任务关联矩阵[22]。从目前的监督多任务学习方法可以看出，评估任务相关性来处理部分相关任务是一种主流趋势。因此，本文也采用此类方式来解决任务部分相关的情况。 3  MTCFIR 算法 3.1   多任务数据符号定义 给 定 � 个 聚 类 任 务 ， 第 � 个 任 务�=  �1, �2�, … , ���  ∈ ℝ�×�，其中�是第�个任务的样本个数，�是特征个数。在多任务聚类领域，不同的任务会被预处理到一个相同的特征空间中[7]。例如，对于文本任务，如果一个任务不包含其它任务中的某些单词特征，我们会对该任务的这些单词特征进行补零操作；对于图像任务，我们会将所有任务的图像缩放到相同的像素尺寸。虽然这�个聚类任务被预处理到相同的�维特征空间中，但是这样简单的特征预处理方法并没有改变每个任务的分布特性，即这些任务的分布差异依然很大。 3.2   算法概览 MTCFIR 算法包含三个步骤，其总体算法流程如算法 1 所示。 算法 1.   MTCFIR. 输入：�个任务 � =1�，所有任务的聚类个数 �� =1�，任务内部最近邻个数 � =1�，共有特征表示学习层数，特征加入噪声的概率�。 输出：簇划分 � =1�。 1.  共有特征表示学习步骤（算法 2）。 2.  一致相似度矩阵学习步骤（算法 3）。 3.  对称非负矩阵分解聚类步骤（算法 4）。 图 1 展示了 MTCFIR 算法中三个步骤的衔接关系。在共有特征表示学习步骤中，原始特征表示下的�个任务 � =1�转化为新特征表示下的�个任务 � =1�。在一致相似度矩阵学习步骤中，根据 � =1�来为每个任务学习一个一致相似度矩阵 � =1�。在对称非负矩阵分解聚类步骤中，通过对 � =1�执行对称非负矩阵分解聚类来得到每个任务的簇指示矩阵 � =1�。 计算机学报———— 本课题得到国家自然科学基金(No.61632019)资助.  张晓彤(通信作者)，女，1990年生，博士，计算机学会(CCF)会员（48345G），主要研究领域为多任务聚类、多任务学习. E-mail: zxt.dut@hotmail.com.  张宪超，男，1971年生，博士，教授，主要研究领域为数据挖掘、机器学习. E-mail: xczhang@dlut.edu.cn.  刘晗，男，1990年生，博士，主要研究领域为不确定数据挖掘、多任务聚类. E-mail: liu.han.dut@gmail.com. 基于特征和实例迁移的加权多任务聚类  张晓彤1), 2)   张宪超1), 2)    刘晗1), 2)   1)(大连理工大学  软件学院,  大连  辽宁  116620) 2)(大连理工大学  辽宁省泛在网络与服务软件重点实验室,  大连  辽宁  116620)  摘  要  传统聚类方法只对每个数据集单独进行聚类，但是有时单个数据集中的数据不足以挖掘一个良好的簇结构。在现实生活中，有很多数据集包含相同的类标签，因此存在多个相关的聚类任务。多任务聚类通过在相关任务之间迁移知识来提升每个任务的聚类性能，近些年来它已经获得越来越多的关注。一个好的多任务聚类算法要完成以下两方面工作：(1)它应该充分利用来自其它任务中的知识；(2)它能够自动地评估任务相关性来避免负面迁移。然而，现有多任务聚类方法还不能很好地完成任意一方面工作。本文提出一个基于特征和实例迁移的加权多任务聚类算法 MTCFIR。一方面，它在任务之间既迁移特征表示知识又迁移实例知识，因此要比大部分现有多任务聚类方法更充分地利用跨任务知识。另一方面，它自动地学习任务相关性来避免负面迁移，并且没有现有评估任务相关性的多任务聚类方法的限制条件。MTCFIR 执行以下三个步骤。首先，它利用边缘堆栈降噪自编码器在任务之间学习一个共有的特征表示。该步骤通过迁移特征表示知识来降低任务之间的分布差异，这是一致相似度矩阵学习的前提。其次，它通过在任务之间迁移实例知识来为每个任务学习一个一致相似度矩阵，并且通过对任务进行加权来决定不同任务对于每个任务的一致相似度矩阵学习的贡献程度。该步骤可以避免在不太相关的任务之间强制迁移知识所带来的负面影响。最后，它在每个任务的一致相似度矩阵上执行对称非负矩阵分解来得到聚类结果。在真实数据集上的实验结果说明本文提出的方法比传统单任务聚类方法和现有多任务聚类方法具有更好的聚类效果，并且要比大部分多任务聚类方法高效。 关键词  多任务聚类；特征表示迁移；实例迁移；任务相关性学习；一致相似度矩阵学习 中图法分类号  TP18 Weighed Multi-Task Clustering by Feature and Instance Transfer ZHANG Xiaotong1),2)   ZHANG Xianchao1),2)   LIU Han1),2) 1)(School of Software, Dalian University of Technology, Dalian Liaoning 116620)  2)(Key Laboratory for Ubiquitous Network and Service Software of Liaoning Province, Dalian University of Technology, Dalian Liaoning 116620)  Abstract  Traditional  clustering  methods  cluster  the  samples  in  each  data  set  individually  by  only  using  the knowledge within each data set, but sometimes the data samples in a single data set are not enough to discover a good cluster structure. There are many data sets which contain the same class labels in the real world, hence there exist  many  related  clustering  tasks.  Multi-task  clustering  can  transfer  the  relevant  knowledge  across  the  related tasks to improve the clustering performance of each task, which has received more and more attentions in recent years.  A  good  multi-task  clustering  algorithm  should  accomplish  both  the  following  two  aspects  of  work:  (1)  it should make full use of the useful knowledge from the other related tasks; (2) it can automatically assess the task 计算机学报张晓彤等：基于特征和实例迁移的加权多任务聚类  5   图 1  MTCFIR 算法的三个步骤衔接关系 MTCFIR 算法的三个步骤的职能如下： （1）共有特征表示学习步骤会输出表示所有任务的新的特征集合，该特征集合包含两部分：每个任务的原始特征和所有任务的共有特征。每个任务的原始特征中包含任务独有特征，这些独有特征有利于对任务本身进行聚类。所有任务的共有特征是指任务共享的语义特征，它是利用边缘降噪自编码器根据所有�个任务一起学习到的。这些共有特征可以降低任务的分布差异，这有利于从其它任务中学习到关联值较大的数据。本步骤输出的特征会重新表示所有任务的数据，进而用于下一步骤的一致相似度矩阵构造中。 （2）一致相似度矩阵学习步骤利用所有�个任务为每个任务学习一个一致相似度矩阵。它基于的思想是一个任务中两个相似的数据点与其它数据点的关联值也很相似。由于每个任务的数据点都能为第�个任务学习一个相似度矩阵，因此对于第�个任务，我们会得到�个相似度矩阵。但是因为每个任务应该具有一个确定的聚类结果，所以我们用一个一致相似度矩阵去表示这�个相似度矩阵。此外，考虑到任务之间的关联性强弱，我们为每对任务施加一个权重，以控制任务之间实例知识迁移的程度，这样有助于避免任务之间的负面迁移问题[1]。本步骤输出的一致相似度矩阵会用于下一步骤的聚类过程中。 （3）对称非负矩阵分解聚类步骤对每个任务的一致相似度矩阵进行对称非负矩阵分解聚类，从而得到每个任务的聚类结果。 3.3   共有特征表示学习 当任务分布差异较大时，我们通常找不到任务之间关联较大的数据，因此我们希望能够学习任务之间的共有特征，从而降低任务之间的分布差异。该步骤为下一步骤的一致相似度矩阵学习提供了前提条件。 考虑到相关任务通常会共享一些具有相同语义的特征，我们利用边缘堆栈降噪自编码器 m SDA方法[5]来学习任务之间共有的语义特征，即共有特征表示。m SDA 是堆栈降噪自编码器 SDA[23]的改进方法。m SDA 和 SDA 是一类深度特征学习方法，它们都能够学习高层次的具有语义概念的特征[5]，但是 m SDA 要比 SDA 更高效。 在 m SDA 中，数据是通过随机将某些特征的值置零来进行加噪的[5]。m SDA 的目标是学习一个特征映射矩阵�，通过�的特征映射，加噪后的数据能够恢复成原始的数据。这里�起到降噪的作用。 由于不同任务中具有相同类标签的数据通常只是在某些特征上存在差异，因此 m SDA 的加噪降噪思想特别适用于为这些任务学习出共有的语义特征。具体地说，m SDA 对同一数据�进行多次随机加噪所得到的数据可以类比于不同任务中具有相同类标签的数据。对多次随机加噪的数据降噪为原始数据�可以类比于学习不同任务中具有相同类标签的数据的共有特征表示。 为了学习所有任务共有的特征表示，我们将所有任务的数据合并起来，然后利用 m SDA 学习一个特征映射矩阵�，其具体计算过程如下。 令� =  �1, … , ��  ∈ ℝ�×� ，其中� 是所有任务的数据个数。将一个常数特征加入到�中，即� =  �; �  ∈ ℝ �+1 ×� ，其中� ∈ ℝ1×� ，利用 m SDA学习单层共有特征表示的优化目标为   min�12��   � − ��  2��=1 (1) 其中，� 是�的第�个加入噪声的版本，�是加入噪声的总次数。如果一个特征被加入噪声，那么该特征将被置为 0。 公式(1)可以被简化为   min� �  − ��  2 (2) 其 中 ， �  =  �, … , �  是 � 的 � 次 重 复 版 本 ，�  =  � 1, … , � �  是 �  的 加 入 噪 声 的 版 本 。� =  �, �  ∈ ℝ �+1 × �+1 是一个特征映射矩阵，� ∈ ℝ �+1 ×1是一个偏差项。 公式(2)可以通过最小二乘方法[24]来解决，即   � = ��−1 (3) 其中，� = � � �，� = � � �。公式(3)的结果依赖于数据点的哪些特征被随机地加入噪声。为了提高结果的鲁棒性，需要加入噪声的次数�尽可能高。根据弱大数定律，当� → +∞时，�和�的期望� � 和� � 以及�的计算方式如下所示。 令每个原始特征加入噪声的概率为�，常数特征加入噪声的概率永远是 0，可得所有特征未被加入 噪 声 的 概 率 向 量 � =  1 − �, … ,1 − �, 1 ∈�    �共有特征表示学习步骤一致相似度矩阵学习步骤对称非负矩阵分解聚类步骤�    ��    ��    �计算机学报 计  算  机  学  报  2019 年  ℝ �+1 ×1，其中�是第�个特征未被加入噪声的概率。令� = ��，有   � = � � � � −1 (4) 其中，   � �  �= ����� (5)    � �  �=  ������   如果� ≠ �����     如果� = �  (6) 在实践中，公式(4)能够通过 MATLAB 中的右除� � /� � 来计算，这可以避免代价较高的矩阵求逆过程[5]。 在计算出�后，可以得到还原的数据�1:�,:�，其中�1:�,:是�的前�行。为了确保生成的特征是非线性的，我们将非线性编码函数���ℎ赋予给还原的数 据 ， 即 单 层 共 有 特 征 表 示 下 的 数 据 为���ℎ �1:�,:� 。 对于多层共有特征表示学习，令第�层的输出数据为ℎ，第�层的特征映射矩阵为��，原始输入数据为�0=  �1, … , �� ，层数为。第�层的输出数据为�= ���ℎ �1:�,:�ℎ �−1 ，其中� �−1=  ��−1; � 是加入常数特征的数据。 每个任务的原始特征既包含任务独有的特征，又隐含任务之间共有的语义特征，前者有利于聚类任务本身，后者有利于降低任务之间的分布差异。由于多层共有特征表示学习输出的是任务之间共有的语义特征，因此为了保留任务独有的特征，最终得到的数据既包括数据的原始特征，又包括共有特 征 表 示 学 习 中 各 层 输 出 的 特 征 ， 即 � = �0; … ; �  ∈ ℝ� +1 ×� ，这里的分号是对矩阵按行叠加。根据所有任务的数据集�，可以得到每个任务 的 数 据 集  � =1�， 其 中 ��=  �1, … , ���  ∈ℝ +1 ×��。 共有特征表示学习步骤的算法流程如算法 2 所示。 算法 2.   共有特征表示学习步骤. 输入：�个任务 � =1�，共有特征表示学习层数，特征加入噪声的概率�。 输出：新特征表示下的�个任务 � =1�。 1.  设置�0=  �1, … , �� 。 2.  FOR  � = 1  TO    DO 3.     对�−1加入常数特征� �−1=  ��−1; � 。 4.     根据公式(4)计算第�层的特征映射矩阵�。 5.  计 算 第 � 层 的 共 有 特 征 表 示 下 的 数 据 �=���ℎ �1:�,:�� �−1 。 6.  END FOR 7.  计算所有任务在原始特征和共有特征表示下的数据� =  �0; … ; � ，从而得到每个任务的数据集 � =1�。 3.4   一致相似度矩阵学习 直觉上，对于一个任务中任意两个数据点，如果它们与其它数据点的关联值很接近，那么它们通常具有较高的相似度。 给定第�个任务的任意两个数据点�i和�j�，以及它们和第�个任务�中数据点的关联值�,：��和�,：��，利用第�个任务来为第�个任务学习相似度矩阵��∈ ℝ��×��的优化目标为  min��   �,：��− �,：�� 22 �� ����=1���=1+ � �� 2 �. �.     �� ����=1= 1,  �� �≥ 0 (7) 其中，�,：��∈ ℝ1×�是��的第�行。���∈ ℝ��×��是任务�和任务�数据之间的关联值矩阵，它可以通过余弦相似度或者高斯核相似度等度量方法来计算。�是一个正则化参数。 公式(7)的第一项意味着�,：��和�,：��之间的欧几里得距离越小，它们的相似度 �� �越高。公式(7)的第二项� �� 2可以防止��的每一列中，只有最近的�,：��和�,：��之间具有相似度 �� �等于 1，其余的相似度 �� �均为 0 的这种情况发生。约束  �� ����=1= 1更有利于计算出��，约束 �� �≥ 0可以确保相似度 �� �的非负性。 根据公式(7)，对于每个任务�，�个相似度矩阵 �� =1�∈ ℝ�×��可以从�个任务中学习到。由于每个任务�应该具有一个确定的相似度矩阵，从而获得一个确定的聚类结果，因此我们令这�个相似度矩阵 �� =1�趋向于同一个相似度矩阵��∈ ℝ�×��。这里�就是我们要学习的一致相似度矩阵，实例知识可以通过一致相似度矩阵�在任务间进行迁移。 计算机学报张晓彤等：基于特征和实例迁移的加权多任务聚类  7  考虑到任务之间相关性有强弱之分，我们在计算�时赋予不同任务的数据不同的权重。因此为任务�学习一致相似度矩阵�的优化目标为  min��    �� �,：��− �,：�� 22�����=1���=1���=1+ � � 2 �. �.   ������=1= 1, ���≥ 0 � = 1, … , ��  (8) 其中，��是任务�对于任务�的关联系数，该参数用于控制任务�中多少比例的实例知识来计算�。 公式(8)包含变量�、参数�以及任务关联系数��，其计算过程如下。 （1）求解�： 最 小 化公 式 (8) 来 求解 �的 每 一列 �:,�� � =1, … , � 的优化目标为  min�:,��   �� �,：��− �,：�� 22�����=1���=1+ � �:,�� 22 �. �.     ������=1= 1, ���≥ 0 (9) 其中，�:,��是��的第�列。公式(9)可以通过二次规划来求解，但是因为二次规划对于较大的数据量不够高效，因此本节采用一种更高效的方法来优化�:,��，其求解过程如下。 令��=   ��� �,：��− �,：�� 22��=1，�:,�是�的第�列，公式(9)可以被改写为  min�:,��12 �:,��+12��:,� 22 �. �.     ������=1= 1, ���≥ 0 (10) 公式(10)的拉格朗日函数为  �(�:,��) =12 �:,��+12��:,� 22− � ��:,��− 1 − ��:,�� (11) 其中，�是一个实数的拉格朗日乘子，� ∈ ℝ�×1是一个非负拉格朗日乘子，� ∈ ℝ�×1。根据 KKT 条件∂� �:,�� ∂�:,��= 0，有   �:,��+12��:,�− �� − � = 0 (12) �:,��的第�个元素为   ���= −12���+ � + �� (13) 其中，�是�的第�个元素。 由于一个稀疏相似度矩阵通常能够获得更好的聚类性能[25]，所以 MTCFIR 只保留�:,��的前��个最大的元素，令其它元素和���均为 0。根据 KKT条件����= 0，有  ���=  −12���+ � 如果��∈ � ��  0          否则             (14) 其中，�(��)是��的��个最近邻集合，这可以通过将�:,�升序排列来获得。 （2）求解�和�： 将公式(14)代入到约束  ������=1= 1中，并定义�:,�的升序排列为�:,�，有     −12���+ �    = 1��+1�=2 (15) 则   � =1��+12�� �  ����+1�=2 (16) 根据公式(13)和(14)，当��∈ � �� 时，有−12���+ � > 0；当��∉ � �� 时，由于���= 0，� ≥ 0，有−12���+ � ≤ 0，即  −12���+1,�+ � > 0, −12���+2,�+ � ≤ 0 (17) 其中，��+1,�是�的第�+ 1行第�列元素。将公式(16)代入到公式(17)中，有  12 ���+1,�−  �����+1�=2  < � (18) 计算机学报 计  算  机  学  报  2019 年  ≤12 ���+2,�−  �����+1�=2  因此可得   � =12 ���+2,�−  �����+1�=2  (19) （3）求解��： 直觉上，一对任务越相关，它们具有越多的相关实例。由于我们已经计算了任意两个任务之间的数据关联值矩阵��，因此两个任务的相关性可以通过��中具有较高关联值的元素比例来计算。为了筛选较高关联值的元素，我们为每个任务设置了一个阀值�= median ��+1,:�� ，其中median ��+1,:�� 是��+1,:��的中位数，���是���按列的降序排列。设置这样的阀值主要是因为只有任务�中�个最近邻的关联值被认为比较高。 在为每个任务�设置阀值�后，任务�和任务�之间的关联值矩阵��中具有较高关联值的元素比例就是任务�相对于任务�的关联系数。   ��= ��≥ �� ����  (20) 一致相似度矩阵学习步骤的算法流程如算法 3所示。 算法 3.   一致相似度矩阵学习步骤. 输入：新特征表示下的�个任务 � =1�，任务内部最近邻个数 � =1�。 输出：每个任务的一致相似度矩阵 � =1�。 1.  FOR  � = 1  TO  �  DO 2.     FOR  � = 1  TO  �  DO 3.       根据 � =1�计算关联值矩阵���。 4.  根据公式(20)计算任务�相对于任务�的关联系数��。 5.     END FOR 6.     根据公式��=   ��� �,：��− �,：�� 22��=1计算 �。 7.     FOR  � = 1  TO  �  DO 8.       分别根据公式(16)和(19)计算�和�。 9.       根据公式(14)计算�的每一列�:,��。 10.     END FOR 11.  END FOR 在算法 3 中，每个任务的一致相似度矩阵�的计算公式(14)包含 3 个变量：矩阵�、参数�和�。由于矩阵�的计算需要利用任务间的关联系数��，所以��参与到��的计算过程中，这控制了��从其它任务中获取的实例知识量。这样，在对�进行对称非负矩阵分解聚类时，就可以避免其它任务中的负面实例知识降低第�个任务的聚类性能了。 3.5   对称非负矩阵分解聚类 在计算出任务�的一致相似度矩阵�后，我们希望利用对称非负矩阵分解方法[6]将每个任务�划分为�个簇。对称非负矩阵分解是一种利用相似度矩阵来对数据进行聚类的方法，它能够挖掘嵌入到相似度矩阵中的簇结构，其优化目标为  min�� �− �� �� � 2 �. �.  �≥ 0 (21) 其中，�∈ ℝ��×��是任务�的一致相似度矩阵，�∈ ℝ��×��是任务�的簇指示矩阵。 根据公式(21)，可以看出在对称非负矩阵分解中，有���= �,:� �,:� 。在理想情况下，如果任务�的两 个 数 据 点 �i和 �j�属 于 同 一 个 簇 ， 那 么 应 有���= 1，否则有���= 0。但是公式(8)中的约束  ������=1= 1使����远小于 1，这不利于获取真实的聚类结果。因此，我们将�的每一列元素�:,��同比例 扩 大 ， 使 �:,��中 最 大 的 元 素 扩 大 为 1 ， 即max �:,��  = 1，其中max �:,�� 是�:,��中最大的元素。最 后 ， 为 了 使 �对 称 ， 我 们 令�=  ��+  �� �  2。 在对每个任务�的一致相似度矩阵�进行上述操作后，我们再通过对称非负矩阵分解即公式(21)来对任务�进行聚类，其求解过程如下。 公式(21)的拉格朗日函数为  � �  =  ��− �� �� � 2 −�� � � �  (22) 其中，� ∈ ℝ�×��是拉格朗日乘子。 令∂� �� ∂��= 0，有   � = −2���+ 2�� �� ��� (23) 根据 KKT 条件�����= 0，有   −���+ �� �� ��� ����= 0 (24) 根据非负矩阵分解的乘法更新规则[6]，任务�中数据的簇指示矩阵�的计算公式为   ���← ���  ���� � �� �� ��� � (25) 计算机学报  张晓彤等：基于特征和实例迁移的加权多任务聚类  9  在初始化�时，MTCFIR 遵循传统的非负矩阵分解方法[26]，即用�均值聚类方法初始化�，然后设置�= ��+ 0.2。这里采用�均值聚类方法初始化�是因为传统聚类方法计算的��要比随机初始化的�更好地指示相对正确的簇划分，因此这有利于后续迭代更新的�朝着指示正确簇划分的方向计算。但是因为�均值聚类方法得到的�中存在零元素，如果初始化的���= 0，根据公式(25)会有���永远是 0，这样公式(25)并没有起到迭代更新�的作用，因此我们设置�= ��+ 0.2来避免��中存在零元素。 对称非负矩阵分解聚类步骤的算法流程如算法 4 所示。 算法 4.   对称非负矩阵分解聚类步骤. 输入：每个任务的一致相似度矩阵 � =1�，所有任务的聚类个数 � =1�。 输出：簇划分 � =1�。 1.  FOR  � = 1  TO  �  DO 2.     根据公式(25)计算簇指示矩阵�。 3.  END FOR 3.6   时间复杂度分析 令�为每个任务的样本个数，�为特征个数，�为每个任务的簇个数，�为任务个数，为共有特征表示学习的层数，� 为�均值聚类的迭代次数，� 为对称非负矩阵分解的迭代次数。计算共有特征表示下所有任务的数据集�的时间复杂度为� ��2� 。计算一致相似度矩阵�的时间复杂度为� �2�2� 。运行对称非负矩阵分解的时间复杂度为� �� ��� +�� �2� 。由于�、�、、� 和� 通常比�和�小很多，因此 MTCFIR 整体的时间复杂度可以简化为� �2� + �2� 。 4  实验 4.1   数据集 由于现有提出的大部分多任务聚类方法都是基于很严格的假设，这些假设主要呈现在以下两个方面：不同任务具有相同的真实类标签、不同任务具有相同的簇个数。为了充分验证本文提出的MTCFIR 方法在遵循或违反以上假设的多任务数据集上的聚类性能，本实验构造了三种常见的多任务数据集形式。 表 1  数据集 数据集  任务    类标签（每类样本数）   维度 WebKB4 1  Cornell.course(44)  Cornell.faculty(34)  Cornell.project(20)  Cornell.student(127)  2500 2  Texas.course(38)  Texas.faculty(46)  Texas.project(20)  Texas.student(146)  2500 3  Washington.course(77)  Washington.faculty(31)  Washington.project(21)  Washington.student(126)  2500 4  Wisconsin.course(85)  Wisconsin.faculty(42)  Wisconsin.project(25)  Wisconsin.student(154)  2500 Handdigits 1  0(509)  1(554)  2(488)  3(514)  4(476)  5(475)  6(473)  7(489)  8(520)  9(502)  256 2  0(813)  1(685)  2(497)  3(449)  4(449)  5(378)  6(465)  7(436)  8(373)  9(455)  256 20NewsGroups 1  Comp.graphics(387)  Rec.auto(395)  Sci.crypt(395)   3000 2  Comp.os.ms-win.misc(391)  Rec.motocycle(397)  Sci.electronics(393)  Talk.politic.mideast(376)  3000 3  Comp.sys.ibm.pc.hw(392)  Rec.sport.baseball(396)  Sci.med(392)   3000 4  Comp.sys.mac.hw (383)  Rec.sport.hockey(399)  Sci.space(392)  Talk.religion.misc(250)  3000 Reuters 1  Economic index.gnp(63)  Metal.gold(90)  Food.cocoa(53)   5000 2  Economic index.cpi(60)  Energy.nat gas(33)  Metal.iron steel(37)   5000 3  Economic index.ipi(36)  Metal.copper(44)  Food.coffee(110)   5000  （1）任务是完全相关的，即不同任务具有相同的真实类标签且具有相同的簇个数。本实验用WebKB41和 Handdigits2表示这种形式。                                                                 1 http://www.cs.cmu.edu/afs/cs.cmu.edu/project/theo-20/www/data/ WebKB4 包含来自 4 个大学计算机科学学院网站的网页，这 4 个大学分别是康奈尔大学、德克萨斯大学、华盛顿大学和威斯康星大学。每个大学的                                                                                                      2 http://www.cad.zju.edu.cn/home/dengcai/Data/MLData.html 计算机学报