刘 旭

（北京信息科技大学 计算机学院，北京 100192）

一种高效的稀有天体光谱检索方法

刘 旭

（北京信息科技大学 计算机学院，北京 100192）

随着国内外光谱巡天计划的发展，人们已经获得了海量的光谱数据。如何利用机器学习方法对海量光谱数据进行系统地分析和处理，是天文学研究中一项非常重要的研究内容。本文提出了一种能够在天体光谱数据库中高效地进行稀有光谱检索的PU学习（PU Learning）方法。在给定少量的稀有天体光谱的条件下，如何在庞大的光谱数据库中系统地搜索与给定稀有光谱同类型的光谱是天文数据挖掘中的一个常见的问题。现有的大多数方法都是基于二分类来解决此类问题，但是当给定的稀有光谱样本数目非常有限时，利用二分类来解决此类问题往往会导致搜索结果的完备性比较差。事实上，基于排序的方法更加适合于解决此类问题。在调研了许多可以用于稀有天体光谱检索的方法后，我们建立了一种新的非常高效的稀有光谱检索方法，称作 BaggingTopPush。BaggingTopPush方法主要使用了二部排序（Bipartite Ranking）和引导聚合（Bagging）技术。

机器学习，数据挖掘，稀有光谱检索，二部排序

0 引言

随着天文观测技术的发展，天文学已经进入了一个信息丰富的大数据时代，天文数据正在以 TB级甚至PB量级的速度不断增长。被誉为“大数据时代的预言家”维克托·迈尔·舍恩伯格的国外大数据系统研究的先河之作《大数据时代：生活、工作与思维的大变革》书里“大数据先锋”一节中写到：“天文学，信息爆炸的起源”。近年来，随着科学技术的不断发展，人类获取天文数据的能力大大增强。面对大量的数据信息，运用机器学习技术[1]在光谱大数据分析和挖掘任务中起到了非常重要的作用[2]。

在很多应用中，只有少数具有某一共同属性的样本是已知的，而目标是根据这些已知样本从大规模未标记样本集中来搜寻与已知样本具有共同属性的样本。例如，在稀有天体光谱搜寻任务中，仅有属于特定类型的少量稀有（与主序星相比）光谱（如碳星，DZ白矮星，L矮星等），而目标是从庞大的天体光谱数据库中尽可能多地搜寻与给定稀有光谱属于同一类型的光谱。在这种情形下，正类样本（即我们感兴趣的稀有样本）是非常有限的，而未标记的样本占据了数据集的绝大部分。

从概念上讲，这种从正类样本和未标记样本学习的过程通常被称作PU学习（PU learning）。假设X = {x1,…, xp+u}代表样本空间X = {x ∈ Rd}中的一个样本集合，P = {x1,…, xp}代表X中的少量正类样本组成的集合，U ={xp+1,…, xp+u}代表X中的大量未标记样本组成的集合。要做的是从P和U中来学习出某种规则，以便于能从U中尽可能精确地识别出其中的正类样本。PU学习的目标是从集合P和U中学习到一个评分函数f : X → R。这个评分函数f能够为U中的每一个未标记样本分配一个分值。对任意一个样本 xi∈ U，其所分配到的分值 f(xi)越高表明它属于正类样本的可能性越大。

关于 PU学习问题，过去二十年里已经出现了很多种方法，它们大致可以总结为两种基本类型：基于分类的PU学习和基于排序的PU学习。

基于分类的 PU学习可以追溯到仅利用正类样本来训练分类器的单类分类方法，如单类支持向量机（One Class Support Vector Machine, OCSVM）[3]和 SVDD（Support Vector Data Description）[4]。OCSVM和SVDD这两种方法都需要足够多的正类样本才能较准确地学习出正类样本的边界。事实上，除了已知的正类样本外，未标记样本也能够提供很多有用信息。Biased SVM（Biased Support Vector Machine）[5]就是同时利用正类样本和未标记样本进行建模的方法。后来Mordelet[6]等人利用集成学习中bagging技巧推广和改进了Biased SVM，他们的方法被称为Bagging SVM。Mordelet 等人已经证明Bagging SVM的效果与Biased SVM相当，甚至超过Biased SVM。此外，当未标记样本占据了数据集的绝大部分时Bagging SVM相比于Biased SVM大大减轻了计算负担。

基于排序的 PU学习其核心思想是建立一个排序模型，使得该排序模型能够根据未标记样本与给定正类样本间的相关度来对未标记样本进行排序。基于图的排序模型已经被广泛应用于 PU学习问题中，如标签传播算法（Label Propagation, LP）[7]和流形排序算法（Manifold Ranking, MR）[8]。在这类方法中，负类样本集是根据一定的规则从未标注样本集U中抽取而来的，如相似度原则[9]和随机抽样原则[10]。一旦U中的某个样本被选中为负类样本，在训练阶段这个样本将会被赋予一个负的标签。从U中抽取完负类样本以后，U中剩余的正类样本和负类样本分别被称为相关样本和不相关样本。然后，基于正类样本和抽取到的负类样本就可以训练一个二部排序模型。该二部排序模型在训练阶段的任务是尽可能地把正类样本排在负类样本的前面。得到这样一个训练好的二部排序模型后，就有理由相信该模型能够将U中的相关样本排在不相关样本的前面。

我们将稀有光谱检索看做是二部排序问题，并且建立了一种新的PU学习方法。Bagging技术已经被证实能够有效地提高机器学习算法的稳定性和预测准确率[11]。考虑到这个事实，我们建立了一种结合了Bagging和TopPush[12]模型的PU学习方法，称为BaggingTopPush。BaggingTopPush方法旨在最大化排序列表顶端的排序准确率。此外，由于其计算复杂度关于训练样本数目是线性的，因此BaggingTopPush是一种效率非常高的PU学习方法。在稀有光谱检索应用中，仅有少量正类样本和大量未标记样本，并没有明确的负类样本数据集可以直接使用。频繁地从未标记数据集中手动挑选负类样本是一件非常耗时的事。即便从未标记样本集中人工挑选出来一些负类样本，这些被挑选出的负类样本也仅仅是冰山一角，并不能够代表所有负类样本的整体信息。因此，同Mordelet等人[13]一样，这里采用随机抽样的办法从未标注样本集中产生“负类”样本。在这种条件下，BaggingTopPush方法会训练出多个二部排序模型，其中每个模型的训练都是基于一次随机抽样所产生的“负类”样本和已知的正类样本。对一个新样本进行预测时，BaggingTopPush方法会集成所有二部排序模型的结果，进行综合排序。为了证明BaggingTopPush方法在稀有光谱检索应用中的有效性和效率优势，引入了一些其他常用的PU学习方法作为对比。为了方便用户使用Bagging TopPush方法，还研究了不同的模型参数选择对排序性能的影响，并且给出了可靠的参数选择范围。

1 二部排序模型

近年来，得益于在信息检索和推荐系统中的成功应用，二部排序得到了广泛的关注。二部排序的目标是学习到一种排序模型使得某一类样本的排列位置总是在另外一类之前。在一些数据挖掘应用中，比如网页搜索和稀有光谱搜索等，人们尤其重视排序列表顶端的准确率状况。这是因为在实际应用中，只有排序列表顶端的那部分样本才有可能被人工查验[14]。

Li等人提出的TopPush方法就是一种旨在优化排序列表顶端准确率的二部排序模型。与其他二部排序模型相比，TopPush的计算复杂度关于训练样本数是线性的而不是二次的。下面首先介绍一下TopPush算法的基本思想和框架，然后再利用Bagging策略建立一种用于稀有光谱检索的PU学习方法。

1.1 TopPush方法

令S = S+∪ S−为一组训练数据，包括从P中随机抽取的m个正类样本和从U中随机抽取的n个负类样本，即 S

TopPush的目标是学习一个排序函数 f : X →R，使得其能够将尽可能多的正类样本排在第一个负类样本前面。这个目标可以通过最小化下面的损失来实现：

其中Ⅱ(·)是指示函数，即当括号内条件为真时函数值为一，否则函数值为零。最小化式（1），实际上就可以迫使负类样本远离排序序列的顶端，从而能保证尽可能多的正类样本排在序列顶端位置。由于指示函数I(·)并非平滑函数，Li等人将式（1）中的指示函数用其非减可微的凸代理损失函数ℓ(·)来代替，从而得到以下损失：

在实际应用中，凸代理损失函数包括截断二次损失ℓ(z) = max(0, 1 + z)2，指数损失ℓ(z) = ez和logistic损失ℓ(z) = log(1+ez)等。这里使用截断二次损失函数来作为凸代理损失函数。

对于线性排序函数f(x) = wTx，学习过程可以用以下的优化目标来描述：

其中w ∈ Rd是待学习的权值向量，λ ＞ 0是控制模型复杂度的正则化参数。关于TopPush模型的优化方法，计算复杂度，和性能分析可以参见[3]。

1.2 用于稀有光谱检索的BaggingTopPush方法

在稀有光谱检索应用当中，给定一些已知的稀有光谱样本，目标是将其他与之相关的样本排在与之不相关样本的前面。为了达到这个目标，可以通过将 P中的稀有样本排在未标记样本集 U 的任意一小部分样本前面来实现。然而，未标记样本集 U中可能隐含了一定比例的正类样本，并且这个比例在实际应用中通常是未知的。因此对于从U中随机抽取的一个样本子集，其中含有的正类样本可能很少也可能很多，这会使排序结果变得非常不稳定性。幸运的是，这种情形恰好可以被 Bagging方法所利用，因为 Bagging方法的出发点就是去提高机器学习算法的稳定性和精确度[15]。

假设K是每次从U中随机抽取的样本数，T是总的随机抽样的次数。BaggingTopPush方法首先利用正类样本和每次随机抽取的负类样本训练多个二部排序模型。每一个训练好的二部排序模型ft都可以对U中的任一样本分配一个分值。分配给U中的某个样本的最后分值 f可以通过多个二部排序模型所分配分值的平均来计算。然后可以根据U中样本的分值 f对其进行降序排序，并且返回排在序列顶端的一部分样本作为候选体。Algorithm 1清晰地展示BaggingTopPush方法的流程。需要注意的是输入变量 λ在这里所起的作用跟其在式(1.3)中所起的作用是相同的，即控制每个TopPush模型的复杂度。λ取值越小，模型越复杂，在训练阶段所消耗的时间也就越长。

Algorithm 1 用于稀有光谱检索的BaggingTopPush输入： P, U, K, T, 入.输出： 排序函数f : X → R.1. 对于t = 1 to T 执行从未标记样本集U中抽取K个样本，记为子集Ut。训练TopPush模型ft使之能够将P中样本排在Ut中样本的前面。2. 返回f=1T T ∑ft t1=

2 结论

在进行稀有天体光谱检索时，如何从原始光谱特征中提取出对后续学习过程最有利的特征是一个非常具有挑战性的问题。由于碳星光谱的特征比较宽比较明显，所以可以直接使用PCA方法来提取特征。然而，如果稀有光谱的特征比较细小，那么需要通过定义一些线指数来提取其特征。

本文主要讨论了稀有天体光谱搜索中的PU学习问题，并且提出了一种用于稀有光谱检索的BaggingTopPush方法。基于二部排序和Bagging技术，BaggingTopPush方法集成了一系列的TopPush模型，其中每个子模型都能够将正类样本排列在从U中随机抽取的负类样本的前面。该方法的主要优点是不仅能够保证排序列表顶端位置处的准确率并且排序速度非常快，这对于海量光谱巡天数据的分析和挖掘是非常有意义的。与其他稀有光谱检索方法相比，BaggingTopPush方法不仅具有最好的检索效果而且消耗的时间最少。并且，合理的参数取值范围，可以使 BaggingTopPush方法更加简单易用。

用于稀有光谱检索的BaggingTopPush方法的源代码可以从此处下载：

http://paperdata.china-vo.org/AstroDM/BaggingT opPush.zip。

[1] 黄炳良, 张忠琳. 预测市场技术在机器学习中的应用[J].软件, 2014, 35(11): 31-35.

[2] 杨泽民. 数据挖掘中关联规则算法的研究[J]. 软件, 2013,34(11): 71-72.

[3] 黄衍, 查伟雄. 随机森林与支持向量机分类性能比较[J].软件, 2012, 33(6): 107-110.

[4] TAX, D. M., AND DUIN, R. P. Support vector data description. Machine learning 54, 1 (2004), 45–66.

[5] LIU, B., DAI, Y., LI, X., LEE, W. S., AND YU, P. S. Building text classifiers using positive and unlabeled examples. In Data Mining, 2003. ICDM 2003. Third IEEE International Conference on (2003), IEEE, pp. 179–186.

[6] MORDELET, F., AND VERT, J.-P. A bagging svm to learn from positive and unlabeled examples. Pattern Recognition Letters 37 (2014), 201–209.

[7] ZHOU, D., BOUSQUET, O., LAL, T. N., WESTON, J., AND SCH¨OLKOPF, B. Learning with local and global consistency.Advances in neural information processing systems 16,16(2004), 321–328.

[8] ZHOU, D., WESTON, J., GRETTON, A., BOUSQUET, O.,AND SCH¨O LKOPF, B. Ranking on data manifolds. Advances in neural information processing systems 16 (2004), 169–176.

[9] AMINI, M.-R., TRUONG, T.-V., AND GOUTTE, C. A boosting algorithm for learning bipartite ranking functions with partially labeled data. In Proceedings of the 31st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR 2008 (2008).

[10] LEE, C., KOYEJO, O., AND GHOSH, J. Identifying candidate disease genes using a trace norm constrained bipartite raking model. 2013, pp. 3459–3462.

[11] MORDELET, F., AND VERT, J.-P. A bagging svm to learn from positive and unlabeled examples. Pattern Recognition Letters 37 (2014), 201–209.

[12] LI, N., JIN, R., AND HUA ZHOU, Z. Top rank optimization in linear time. In Advances in Neural Information Processing Systems 27, Z. Ghahramani, M. Welling, C. Cortes, N.Lawrence, and K. Weinberger, Eds. Curran Associates, Inc.,2014, pp. 1502–1510.

[13] MORDELET, F., AND VERT, J.-P. Prodige: Prioritization of disease genes with multitask machine learning from positive and unlabeled examples. BMC bioinformatics 12, 1 (2011),389.

[14] BOYD, S., CORTES, C., MOHRI, M., AND RADOVANOVIC,A. Accuracy at the top. In Advances in neural information processing systems (2012), pp. 953–961.

[15] BREIMAN, L. Bagging predictors. Machine learning 24, 2(1996), 123–140.

An Efficient Method for Spectral Retrieval of Rare Earth Objects

LIU Xu
(Beijing Information Science and Technology Universit, College of computer science, Beijing, China)

With the development of domestic and international spectroscopic sky survey,people have obtained massive spectral data. How to use machine learning methods to analyze and process the big spectral data is a very important research content in the study of astronomy. In this paper,We treat the rare spectral retrieval in astronomical databases as the bipartite ranking task and present a new PU learning method to solve this problem. One of the most important aims of astronomical data mining is to systematically search for specific rare objects in a massive spectral data set, given a small fraction of identified samples with the same type. Most existing methods are mainly based on binary classification, which usually suffers from incompleteness when there are too few known samples.Rank-based methods could provide good solutions for such cases. After investigating several algorithms, a method combining a bipartite ranking model with bootstrap aggregating techniques was developed in this paper.

: Machine learning; Data mining; Rare spectral retrieval; Bipartite ranking

TP181

A

10.3969/j.issn.1003-6970.2017.10.037

本文著录格式：刘旭. 一种高效的稀有天体光谱检索方法[J]. 软件，2017，38（10）：185-188

刘旭，男，(1991-)，研究生，主要研究方向：数据挖掘。