一种结合Fisher编码的多示例聚类算法

芮 辰，陈艳平

(1.合肥学院 实验实训中心，安徽 合肥 230601；2.合肥学院 人工智能与大数据学院，安徽 合肥 230601)

多示例学习样本由示例所组成的集合所构成。Dietterich等人在通过机器学习方法研究麝香分子是否具有活性时发现[1]，分子具有多种形状，我们只知道分子是否具有活性，无法得知哪一种形状能够让该分子具有活性。传统监督学习中样本和样本类别一一对应，而多示例学习中的样本和包的类别是多对一的关系(如图1所示)，人工筛选具有活性的麝香分子是一件非常耗时耗力的工作。由于具有活性的分子(正包)中包含大量噪声(假正例)，监督学习算法直接应用于多示例问题时难以取得令人满意的分类精度。多示例问题的发现拓展了传统机器学习的研究领域，被认为是一种新的机器学习框架。事实上，除药物活性预测问题外，很多现实中的问题都属于多示例问题的范畴。目前，多示例学习已被广泛应用于基于内容的图像检索[2-3]，计算机辅助诊断[4-5]，计算机视觉等领域[6-7]。

图1 多示例学习问题描述

在机器学习领域，在数据集不完整、数据集自身的标记不完整或样本从属于某种类别的规则不明确时监督学习算法的分类效果可能会受影响。聚类作为一类无监督的机器学习算法，可以通过度量样本之间的相似程度，将数据集划分为多个不相交的、内部具有高度相似性的聚簇(Cluster)，在数据的类别不明确或不完整的情况下，揭示样本的分布规律。但多示例包中的大量假正例对聚类效果影响很大，将常规聚类算法直接应用于多示例问题时，无法取得理想的分类精度。

本文设计了一种无监督的多示例学习聚类算法，即MIFK-means。该方法首先通过Fisher编码对多示例数据在实现归一化的同时保留数据集原有的关键信息，有效降低多示例数据的学习复杂度。然后对转换后的多示例数据集构建聚类模型，拟合多示例数据的真实分布情况。实验结果证明了该算法的有效性。

1 相关工作

近年来，为解决多示例问题，国内外学者提出了两类多示例学习算法。一类是针对多示例学习的特点量身定制的算法，如Dietterich等人提出了三种轴平行矩形APR算法[1]，能够在数据集中用超矩形找到多示例数据每一维的上界和下界，从而找到真正例的集合。Maron设计了学习的Diverse Density(DD)算法，该方法可以在多示例数据集的示例空间内通过梯度下降过程找到一个在概率上最可能是正示例的点。Zhang Qi和Goldman对DD算法进行了改进，提出基于期望最大化算法的DD算法，即EM-DD[8]。Zhang和Zhou通过关键示例的转移提出了一种嵌入式的多示例算法MIKI[9]。另一类是对传统的机器学习算法进行改进，使之适用于多示例问题。如Liu等人设计了一个多示例学习的卷积神经网络算法并将其应用于多镜头人物识别中[10]。Gabriella Melki等人提出了多示例学习的包层次SVM算法MIRSVM[11]。Wang和Zucker首次通过懒惰学习方式，提出了基于概率的Bayesian-kNN算法和基于引证的Citation-kNN算法。Chevaleyre和Zucker提出了多示例学习的决策树方法RIPPER-MI。J.Ramon和L.Ramon等人提出了多示例学习的神经网络框架。Zhang和Zhou设计了多示例学习的BP神经网络算法。Chen等人将多示例学习问题转换为传统的有监督学习问题，提出了一种通过嵌入式示例选择的多示例学习算法MILES[8]。谢红薇和李晓亮提出了多示例学习的包层次K-means聚类算法MI_K-means[12]，该算法通过混合Hausdorff距离度量包之间的相似程度。

尽管以上算法在多示例数据的分类中取得了很高的精度，但却未能揭示多示例数据真实的分布情况。聚类作为人工智能和数据挖掘领域的一种重要方法，可以通过无监督方法揭示数据集的内部结构和分布规律。但包层次的多示例聚类算法无法避免正包中大量的反示例对聚类的影响。本文提出的MIFK-means算法首先通过Fisher编码对多示例数据集进行归一化重新表示，再通过聚类拟合多示例数据真实的分布情况。在基准数据集上的实验结果表明，MIFK-means算法的分类精度可以与现有的经典多示例学习算法相媲美，可以高效、精准地对多示例数据进行聚类。

本文的其余部分安排如下。第二节介绍MIFK-means算法的详细细节。第三节通过实验验证聚类效果和算法的有效性。最后，在第四节进行总结并展了未来的工作方向。

2 结合Fisher编码的多示例聚类算法

2.1 问题描述

给定多示例数据集X={(Bi,label)|i=1,2,...,N}，其中Bi表示多示例数据包，label为数据包的类别，label={+1,-1}。令B+={bi|i=1,2,...,p}表示一个正包，B-={bj|i=1,2,...,n}表示一个反包。数据的维度为D，d表示多示例样本的第d个维度。多示例问题是二分类问题，学习任务是正确预测包的类别为+1还是-1。

2.2 MIFK-means算法

基于内容的图像检索(CBIR)是多示例学习的典型应用之一。如图2所示，在CBIR领域中，用户感兴趣的内容可能仅仅是图片中的一小部分(如图2中的马)，这部分兴趣点可以理解为多示例正包中的真正例，如果一幅图片中不包含任何用户感兴趣的内容(不包含马)，那么可以将整幅图片理解为一个多示例反包。Fisher编码是模式识别中用少量特征来描述图像，从图像中提取语义的一种编码技术[13-14]。该方法通过对高斯分布的参数求偏导，再对结果进行归一化处理从图片中挖掘和拟合图片特征。可以使用Fisher编码在对多示例数据进行归一化的同时，保留多示例数据包的原始语义。MIFK-means算法分两步执行：归一化过程和聚类过程。算法的具体执行步骤如下。

图2 图像具有多样性的例子

2.2.1 归一化过程

1)设λ为数据模型p(x;λ),x∈X,λ∈RD的参数，通过对数似然函数的梯度G(x)=∇λlogp(x|λ)表征数据，该梯度描述了如何通过参数λ更好的拟合数据。

2)通过获取Fisher向量之间的缩放内积来定义数据的Fisher核函数k(x1,x2)=φ(x1)Tφ(x2)。其中，φ(x)=F-1/2∇λlogp(x)，F为Fisher信息矩阵F=Ep(x)[G(x)G(x)T]。

3)通过K个高斯分布的线性组合模型来拟合多示例数据。将其组成的高斯混合模型参数定义为λ={wk,μk,∑k,k=1,2,...,K}，其中wk，μk，∑k分别是高斯混合分布模型的权重，均值和协方差矩阵。

2.2.2 聚类过程

影响K-means算法聚类效果的关键是初始聚类中心的选择和数据相似度的度量方式。MI_K-means算法运行在包层次，聚类时从多示例数据包中通过随机抽样法确定初始聚类中心。但由于多示例包中的示例数各不相同，正包中含有大量假正例，每个多示例包在整个数据集中的权重事实上是不同的，因此随机选取初始化聚类中心在一定程度上限值了MI_K-means算法的聚类效果和分类精度。此外，运行在包层次的MI_K-means算法使用Hausdorff距离度量多示例包之间的相似度，最大Hausdorff距离在聚类时受多示例包中离群示例的影响很大，最小Hausdorff距离只考虑了两个多示例包中相似度最大的两个示例，混合Hausdorff距离作为折中虽然能够在一定限度上弥补最大和最小Hausdorff距离的弊端，但由于正包内大量假正例的存在，始终无法避免多示例包中噪声对包之间真实相似度的影响[12]。

本文提出的MIFK-means算法通过Fisher编码，能够在保留各个多示例包语义的前提下，通过高斯混合分布拟合示例数各不相同的多示例包，将多示例包归一化为一个个维度相同的Fisher向量，从而将多示例问题转化为了传统的机器学习问题。MIFK-means算法运行在示例层，随机初始化聚类中心点时，能够不受各个多示例包权重的限值，数据相似度的度量方式也不必使用Hausdorff距离，而是使用传统机器学习中更准确的示例层次的相似度度量函数。从而可以进一步提升聚类效果，拟合多示例数据集。

给定经过Fisher编码归一化后的多示例数据集X={x1,x2,...,xn}，聚类算法的执行流程如下。

1)从X中随机选取k个样本初始化聚类中心μ={μ1,μ2,...,μk}

2)repeat

3)根据聚类中心μ={μ1,μ2,...,μk}确定各个样本从属的聚类

4)fori=1,2,...,n

5)计算样本xi和各个聚类中心μj的相似度：dij=f(xi,μj)

6)将样本xi分配到距离最近的那个聚类：Ck=Ck∪{xi}

7)end

8)forj=1,2,...,k

10)end

11)until 达到算法的收敛条件，即所有聚类中心μ={μ1,μ2,...,μk}不再改变

3 实验结果与分析

本节介绍实验数据集，评价聚类效果并分析实验结果。实验设备的主要性能参数为Intel i5-3570 CPU @ 3.40GHz * 4 CPUs，8 GB内存。

3.1 实验数据集

麝香分子数据集是至今唯一的真实多示例数据集。分类任务是预测Musk1和Musk2两个子集中的麝香分子是否具有活性。该数据集可以从UCI机器学习数据集仓库中免费获取①。数据集的详细信息如表1所示。

表1 数据集的详细信息

3.2 实验结果和分析

3.2.1 聚类效果对比

由于所有多示例数据在包层次都具有明确的类别，因此可以采用Rand Index指标衡量通过聚类后正确决策的比例。定义TP和TN分别表示真正例和真反例数目，FP和FN分别表示假正例和假反例数目。则可以通过Rand Index测度(公示7)度量算法的划分结果和人工划分结果的耦合程度。

(7)

对于Musk1和Musk2数据集，将聚类数分别设置为10，20，30，40和50进行聚类效果实验。图3对比了MIFK-means算法和MI_K-means算法作用于麝香分子数据集时的聚类效果。

图3 MI_K-means和MIFK-means算法在Musk数据集上的聚类效果对比

实验结果表明， MIFK-means算法能够在一定程度上避免MI_K-means聚类算法运行时包中示例权重的不同对聚类效果的影响，聚类效果优于MI_K-means算法。

3.2.2 分类精度对比

尽管所有多示例包都有明确的标记，但是正包中示例的标记却是未知的。包层次多示例分类算法难以避免正包中的反示例对分类精度的影响。而MIFK-means算法通过Fisher编码在保留多示例包中语义的前提下将多示例分类问题转化为了传统的监督学习分类问题，从而在一定程度上降低了正包中的噪声对分类精度的影响。表2比较了MIFK-means算法和一些经典多示例算法的分类精度。通过10折交叉验证法进行实验。每次实验中，将多示例数据集平均分为10份，其中9份用作训练集，余下的1份用作测试集，10份样本轮流作为测试集。MIFK-means算法重复执行10次，取10次分类的平均值为10折倍交叉验证的最终的分类精度，详细的实验结果列在表2中。实验结果表明，MIFK-means算法的分类精度优于MI_K-means算法，并且可以和现有的经典多示例算法相媲美。

表2 算法分类精度的比较

4 结语

正包中大量的假正例掩盖了多示例数据之间真实的相似性，为了排除假正例的干扰，MIFK-means算法首先通过Fisher矩阵在保留多示例数据包原有语义的前提下对多示例包进行归一化，然后通过示例层次的K-means算法构建多示例数据的聚类模型。实验表明，该策略能够有效提高多示例样本的聚类效果。在未来的工作中，我们将进一步探索如何将MIFK-means算法应用于大规模的多示例数据集，以及如何将该算法应用于多示例学习的实际应用场景中。

注释：

① http://archive.ics.uci.edu/ml/machine-learning-databases/musk/.