通过评估示例中概念的重要性来解决多示例学习问题.pdf

第 卷第期 年月计算机科学 到稿日期：返修日期：甘睿（），男，博士生，主要研究方向为数据挖掘、机器学习，：。通过评估示例中概念的重要性来解决多示例学习问题甘睿印鉴（中山大学信息科学与技术学院广州 ）摘要在多示例学习问题中，训练数据集里面的每一个带标记的样本都是由多个示例组成的包，其最终目的是利用这一数据集去训练一个分类器，使得可以利用该分类器去预测还没有被标记的包。在以往的关于多示例学习问题的研究中，有的是通过修改现有的单示例学习算法来迎合多示例的需要，有的则是通过提出新的方法来挖掘示例与包之间的关系并利用挖掘的结果来解决问题。以改变包的表现形式为出发点，提出了一个解决多示例学习问题的算法 概念评估算法。该算法首先利用聚类算法将所有示例聚成簇，每一个簇可以看作是包含在示例中的概念；然后利用原本用于文本检索的 （）算法来评估出每一个概念在每个包中的重要性；最后将包表示成一个维向量 概念评估向量，其第个位置表示第个簇所代表的概念在某个包中的重要程度。经重新表示后，原有的多示例数据集已不再是“多示例”，以至于一些现有的单示例学习算法能够用来高效地解决多示例学习问题。关键词多示例学习，重新表示，单示例学习，概念评估中图法分类号 文献标识码 （，），（），“”，多示例学习（）这一概念，是由 等人在 研究药物活性预测问题时提出的，其目的是为了让学习系统通过分析已经被标记为适合或不适合制药的分子来预测还没有被标记的新分子。其难点在于，每一个分子里面都包含了很多种低能形状（），专家们能够知道的是哪个分子适合制药，至于该分子里面哪种低能形状起决定性作用，则一无所知。一开始，等人尝试用监督学习的方法来解决问题，并把所有在适合制药的分子里面的低能形状当作是正例，不适合的分子里面的低能形状当作反例。但是，他们很快就发现这样做是行不通的，因为在一个被标记为适合的分子里面包含着很多种低能形状，而在这些低能形状集合中可能就只有一种起到决定性作用，其他的根本起不了作用。等人的做法是把不起作用的也当作正例，从而增加数据的噪音，影响了学习系统的学习效果。于是，等人把分子定义为包，分子里面的低能形状当作是包中的示例。并假设，如果一个包被标记为正，那么该包至少包含一个正示例；如果一个包被标记为反，那么该包里面的所有示例都是反例。而在训练集中只给出了包的标记，并没有给出示例的标记。由此，一种新的机器学习问题诞生了。相关工作在 等人的研究之后，很多关于这一新的机器学习问题的研究陆续展开。在这些研究中，有的是以示例为出发点，通过挖掘示例与包之间的关系，并利用挖掘的结果来解决多示例学习问题。例如，多样性密度（，）算法把每包表示成由示例构成的集合，其任务就是在由示例形成的属性空间中找到具有最大多样性密度的那个点。在这里，多样性密度是一种度量，如果一个点附近出现的正包数越多，而反包示例出现得越远，那么该点的多样性密度越大。找到该点后，就可以把这个点作为参照点来标记新的包。但多样性密度算法有个很大的缺点，就是效率低。要在由示例形成的属性空间中找到目标点，是一件很耗时的事情；而且在寻找的过程中，由于采用梯度下降法使得算法并不能确保找到全局最优解，寻找结果的好坏直接影响到最终的分类结果。即使是后来提出的期望最大多样性密度（，）算法，结合了算法的思想来针对多样性密度算法效率低的缺点进行了改进，但仍然需要耗费一定的时间才能获取到最终结果。随着研究的深入，有些研究者发现通过对现有的基于单示例的监督学习算法进行改进，可以使这些算法能够用于解决多示例学习问题。例如 算法就是对近邻分类算法的一种改进，该算法认为一个包的标记不但由这个包的近邻来决定，还应该由把这个包当作近邻的那些包来决定。在寻找包的近邻时，该算法使用最小化豪斯多夫距离（）来衡量包与包之间的距离，而不是使用传统的欧氏距离（）。直到现在，算法依旧是众多经典的多示例算法中分类效果相对较好的算法之一，但是其效率不高，这也是它唯一缺点。虽然与多样性密度算法相比，该算法在效率方面有了很大的提高，但是要在一个数据集中同时查找两类近邻，也需要耗费一定的时间来计算包与包之间的距离，尤其是在数据集相对较大的情况下更为明显。本文从改变包的表现形式入手，提出了概念评估算法。首先通过聚类算法挖掘出包含在所有示例中的概念；再运用文本 检 索 中 的 （）算法评估出每个概念在每个包的重要性；最后把包表示成概念重要性向量形式，不但考虑了概念在包中出现的次数，还把概念在整个数据集中的重要性也考虑进去。其具体做法如下。通过评估示例中概念的重要性解决多示例学习问题在多示例分类中，我们获取到的是一个由包构成的训练集合（，），（，），其中每个包又由多个示例构成，而，这里的表示构成包的示例集合的大小，是包的标记集合。从词袋模型入手，尝试找出解决多示例问题的算法。词袋模型（）的主要思想词袋模型主要运用于自然语言处理和文本信息检索方面，大大简化了文本的表现形式。它把文本表示成一堆单词的集合，在表示过程中，每个词的出现都是独立的，并不需要考虑单词出现的先后顺序，也不用考虑文本的语法和句法。由于在文本挖掘方面取得成功，词袋模型已经开始被运用到其他领域，例如图像中的对象分类。其主要思想是把图像里面的每个特征点量化到几个有代表性的关键点上面，然后利用量化的结果重新表示原图像。从这里可以看出，要想利用词袋模型解决其他领域的问题，首先要做以下两步工作：（）发现关键点，一般采用聚类方法；（）把所有的特征点量化到关键点上。因此我们做的第一件事情是利用聚类算法把数据集中所有示例划分为簇（这里并没有考虑各示例所在的包的标记）；然后把每个包中的示例量化到这簇上。表给出了一个量化结果的例子。在这里，假设在聚类时设定了簇的数量为。每一个格子里面的数字表示在一个包中有多少个示例属于某个簇。表包示例量化到个簇上的结果包 每个簇又可以被看作是一个包含在所有示例中的概念。如果一个包包含个示例属于簇，那么可以把看作是概念在这个包出现的次数。利用 方法评估概念在包中的重要性 （）是一种用于资讯检索与资讯探勘的常用加权技术，用以评估某个词语对于一个文件集中的一份文件的重要程度。其主要思想是：如果某个词语在一篇文章中出现的频率高，并且在其他文章中很少出现，则认为此词具有很好的类别区分能力，适合用来分类。实际上是 。表示词频（），指的是某一个给定的词语在某个文件中出现的次数，其计算方法如下：，（）式中，分子，表示在文件中出现的次数，分母则是在文件中所有的词出现的次数之和。则表示逆向文件 频 率（），是某一个给定的词语普遍重要性的度量，其计算方法如下：（）式中，分子表示文件集的文件总数，分母：表示包含词语的总文件数。如果把表中的每个包均看成是一篇文章，每个簇均看成是一个词，那么就可以运用 方法来评估每个簇所代表的那个概念在每个包中的重要性。概念评估算法结合词袋模型和 方法，提出了一个解决多示例学习问题的算法 概念评估算法。其主要思想是，要把原来多示例数据集中的每一个包表示成如下向量。在这里，把这种表现形式命名为概念评估向量。（，），（，），（，）式中，（，）表示通过 方法获得的第个簇在 中的重要性。经过重新表示后，原来的多示例数据集变成了普通的单示例数据集，一些基于单示例的监督学习方法可以用来解决原来的多示例学习问题。整个概念评估算法的伪代码见表。表概念评估算法伪代码概念评估算法（）（，）：（，），（，）：，：把所有示例聚成个簇 （，）把训练集中的包量化到个簇 （，）表示包中属于簇的示例数 利用 方法计算个簇在训练集中每个包的重要性并把每个包表示成带标记概念重要性向量形式 （，）（）计算 的 值 （）计算 的 值 （，）（，）（，）（，），利用改变后的训练集训练分类器 （）把测试集中的包量化到个簇 （，）表示包中属于簇的示例数 利用 方法计算个簇在测试集中每个包的重要性并把每个包表示成不带标记的概念重要性向量形式 （，）（）计算 的 值 （）计算 的 值 （，）（，）（，）（，）利用训练好分类器标记经过转变的测试集 ：（）实验结果与比较 多示例数据集 数据集是由 等人提供的专门用于测试多示例学习算法的公共数据集。它包括两个独立数据集，即 和 。包含 个正包和 个反包，每个包所含的示例个数从到 不等；则包含 个正包和 个反包，每个包所含的示例个数从到 不等。关于这两个数据集的详细信息见表。表 数据集详细信息数据集维度包包总数正包数反包数示例总数 ，单示例学习算法与多示例学习算法比较为了找出哪个单示例学习算法最适合充当概念挖掘算法的分类器，我们选择了个由 所支持的单示例学习算法分别作为概念挖掘算法的分类算法；然后选择个经典多示例学习算法，分别比较这两类算法在 和 数据集上的分类效果。关于这个单示例学习算法的详细信息见表。表个算法的详细信息 内部名称描述利用序列最小最优化（）法 实 现 的 支 持 向 量 机（）采用反向传播的神经网络 近邻分类算法 决策树 贝叶斯（）分类器对于个单示例学习算法，首先利用概念挖掘算法，把数据集中的每一个包都转变成概念向量形式，然后将其交给这个算法来进行训练。实验重复了 次 折交叉验证，在转变包的过程中采用了 算法对所有示例进行聚类，聚簇数设为。表给出了这个单示例学习算法在 数据集上实验结果。在这里，除了 设定近邻数为之外，其他所有单示例学习算法都是以 设定的默认值来运行。表给出了个经典的多示例学习算法在 数据集上的最好分类正确率。表个单示例算法在 数据集上 次 折交叉验证的结果算法 上的分类正确率（）上的分类正确率（）表多个示例学习算法在 数据集上的最好分类结果算法 上的分类正确率（）上的分类正确率（）从表和表中可以看到，对于 数据集，当选择 （神经网络）充当分类算法时，概念评估算法的分类正确率为 ，仅次于 和 算法，但比其他个多示例学习算法的分类正确率要高。对于 数据集，同样选择 充当分类算法时，概念评 估算 法的分 类 正 确 率为 ，仅 次 于 算法，但比其他个多示例学习算法的分类正确率都要高。实验结果表明，使用我们提出的概念评估算法来改变包的表现形式后，一些单示例学习算法能够被用来解决多示例学习问题，其效果比一些经典的多示例学习算法还要好。簇的数量对正确率的影响从第节提出的方法可以看出，在聚类过程中，设定不同的簇数量，会生成不同维度的概念向量，因此会产生不同版本的数据集。如下实验主要研究分类正确率与不同簇数量之间的关系。这里设定簇数量的变化范围为到。图是个单示例算法在经过转变后的 数据集上 次 折交叉验证的结果与簇数量之间的关系，图是在经过转变后的 数据集上的结果。图 数据集上分类正确率与簇数量之间的关系图 数据集上分类正确率与簇数量之间的关系从上两图中可以看出，无论使用哪个数据集，随着簇数量的改变，个单示例学习算法的分类准确率先递增后在一定的范围内上下波动。簇数量的递增，可以看作是对数据集的理解从肤浅到深入的过程。簇数量较少时，生成的概念数也相对较少，对数据集理解相对肤浅，因此分类准确率不高；随着簇数量越来越大，生成的概念数也就越来越多，对数据集的理解越来越深入，分类准确率也逐步提高；当到达一定幅度后，分类准确率相对稳定，然后在一定的范围里上下波动。这是因为随着簇数量的进一步增加，一些起决定性作用的概念被分成更加小的概念，从而使分类准确率有所下降；同时，一些新的起决定性作用的概念又被分割出来，从而导致分类准确率有所回升。表对上面的实验进行了总结。表簇数量与算法分类正确率之间的关系总结算法 最高正确率（）最好簇数量最高正确率（）最好簇数量 ，、从表可以看出，对于不同的多示例数据集，使用不同的单示例学习算法来充当分类器的概念评估算法，在获取到最好的分类正确率时，对簇数量的要求各不相同。如何根据不同的数据集以及不同的单示例学习算法来自动找出最好的簇数量，是我们下一步研究工作的重点。结束语本文从改变包的表现出发，结合词袋模型和 统计方法，提出概念评估算法。该算法把包转变成概念评估向量的形式，经过转变后，原来的多示例数据集变成了普通的单示例数据集，则可以利用现有的基于单示例的监督学习算法来解决多示例学习问题。实验证明，数据集的表现形式虽然发生了改变，但分类的效果并没有受到影响，分类准确率比一些经典的多示例学习算法还要好。参 考 文 献 ，（）：，：，：，：，：，：，（）：，：，：