劉 旭

（北京信息科技大學 計算機學院，北京 100192）

一種高效的稀有天體光譜檢索方法

劉 旭

（北京信息科技大學 計算機學院，北京 100192）

隨著國內(nèi)外光譜巡天計劃的發(fā)展，人們已經(jīng)獲得了海量的光譜數(shù)據(jù)。如何利用機器學習方法對海量光譜數(shù)據(jù)進行系統(tǒng)地分析和處理，是天文學研究中一項非常重要的研究內(nèi)容。本文提出了一種能夠在天體光譜數(shù)據(jù)庫中高效地進行稀有光譜檢索的PU學習（PU Learning）方法。在給定少量的稀有天體光譜的條件下，如何在龐大的光譜數(shù)據(jù)庫中系統(tǒng)地搜索與給定稀有光譜同類型的光譜是天文數(shù)據(jù)挖掘中的一個常見的問題?，F(xiàn)有的大多數(shù)方法都是基于二分類來解決此類問題，但是當給定的稀有光譜樣本數(shù)目非常有限時，利用二分類來解決此類問題往往會導致搜索結(jié)果的完備性比較差。事實上，基于排序的方法更加適合于解決此類問題。在調(diào)研了許多可以用于稀有天體光譜檢索的方法后，我們建立了一種新的非常高效的稀有光譜檢索方法，稱作 BaggingTopPush。BaggingTopPush方法主要使用了二部排序（Bipartite Ranking）和引導聚合（Bagging）技術。

機器學習，數(shù)據(jù)挖掘，稀有光譜檢索，二部排序

0 引言

隨著天文觀測技術的發(fā)展，天文學已經(jīng)進入了一個信息豐富的大數(shù)據(jù)時代，天文數(shù)據(jù)正在以 TB級甚至PB量級的速度不斷增長。被譽為“大數(shù)據(jù)時代的預言家”維克托·邁爾·舍恩伯格的國外大數(shù)據(jù)系統(tǒng)研究的先河之作《大數(shù)據(jù)時代：生活、工作與思維的大變革》書里“大數(shù)據(jù)先鋒”一節(jié)中寫到：“天文學，信息爆炸的起源”。近年來，隨著科學技術的不斷發(fā)展，人類獲取天文數(shù)據(jù)的能力大大增強。面對大量的數(shù)據(jù)信息，運用機器學習技術[1]在光譜大數(shù)據(jù)分析和挖掘任務中起到了非常重要的作用[2]。

在很多應用中，只有少數(shù)具有某一共同屬性的樣本是已知的，而目標是根據(jù)這些已知樣本從大規(guī)模未標記樣本集中來搜尋與已知樣本具有共同屬性的樣本。例如，在稀有天體光譜搜尋任務中，僅有屬于特定類型的少量稀有（與主序星相比）光譜（如碳星，DZ白矮星，L矮星等），而目標是從龐大的天體光譜數(shù)據(jù)庫中盡可能多地搜尋與給定稀有光譜屬于同一類型的光譜。在這種情形下，正類樣本（即我們感興趣的稀有樣本）是非常有限的，而未標記的樣本占據(jù)了數(shù)據(jù)集的絕大部分。

從概念上講，這種從正類樣本和未標記樣本學習的過程通常被稱作PU學習（PU learning）。假設X = {x1,…, xp+u}代表樣本空間X = {x ∈ Rd}中的一個樣本集合，P = {x1,…, xp}代表X中的少量正類樣本組成的集合，U ={xp+1,…, xp+u}代表X中的大量未標記樣本組成的集合。要做的是從P和U中來學習出某種規(guī)則，以便于能從U中盡可能精確地識別出其中的正類樣本。PU學習的目標是從集合P和U中學習到一個評分函數(shù)f : X → R。這個評分函數(shù)f能夠為U中的每一個未標記樣本分配一個分值。對任意一個樣本 xi∈ U，其所分配到的分值 f(xi)越高表明它屬于正類樣本的可能性越大。

關于 PU學習問題，過去二十年里已經(jīng)出現(xiàn)了很多種方法，它們大致可以總結(jié)為兩種基本類型：基于分類的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 等人已經(jīng)證明Bagging SVM的效果與Biased SVM相當，甚至超過Biased SVM。此外，當未標記樣本占據(jù)了數(shù)據(jù)集的絕大部分時Bagging SVM相比于Biased SVM大大減輕了計算負擔。

基于排序的 PU學習其核心思想是建立一個排序模型，使得該排序模型能夠根據(jù)未標記樣本與給定正類樣本間的相關度來對未標記樣本進行排序?；趫D的排序模型已經(jīng)被廣泛應用于 PU學習問題中，如標簽傳播算法（Label Propagation, LP）[7]和流形排序算法（Manifold Ranking, MR）[8]。在這類方法中，負類樣本集是根據(jù)一定的規(guī)則從未標注樣本集U中抽取而來的，如相似度原則[9]和隨機抽樣原則[10]。一旦U中的某個樣本被選中為負類樣本，在訓練階段這個樣本將會被賦予一個負的標簽。從U中抽取完負類樣本以后，U中剩余的正類樣本和負類樣本分別被稱為相關樣本和不相關樣本。然后，基于正類樣本和抽取到的負類樣本就可以訓練一個二部排序模型。該二部排序模型在訓練階段的任務是盡可能地把正類樣本排在負類樣本的前面。得到這樣一個訓練好的二部排序模型后，就有理由相信該模型能夠?qū)中的相關樣本排在不相關樣本的前面。

我們將稀有光譜檢索看做是二部排序問題，并且建立了一種新的PU學習方法。Bagging技術已經(jīng)被證實能夠有效地提高機器學習算法的穩(wěn)定性和預測準確率[11]?？紤]到這個事實，我們建立了一種結(jié)合了Bagging和TopPush[12]模型的PU學習方法，稱為BaggingTopPush。BaggingTopPush方法旨在最大化排序列表頂端的排序準確率。此外，由于其計算復雜度關于訓練樣本數(shù)目是線性的，因此BaggingTopPush是一種效率非常高的PU學習方法。在稀有光譜檢索應用中，僅有少量正類樣本和大量未標記樣本，并沒有明確的負類樣本數(shù)據(jù)集可以直接使用。頻繁地從未標記數(shù)據(jù)集中手動挑選負類樣本是一件非常耗時的事。即便從未標記樣本集中人工挑選出來一些負類樣本，這些被挑選出的負類樣本也僅僅是冰山一角，并不能夠代表所有負類樣本的整體信息。因此，同Mordelet等人[13]一樣，這里采用隨機抽樣的辦法從未標注樣本集中產(chǎn)生“負類”樣本。在這種條件下，BaggingTopPush方法會訓練出多個二部排序模型，其中每個模型的訓練都是基于一次隨機抽樣所產(chǎn)生的“負類”樣本和已知的正類樣本。對一個新樣本進行預測時，BaggingTopPush方法會集成所有二部排序模型的結(jié)果，進行綜合排序。為了證明BaggingTopPush方法在稀有光譜檢索應用中的有效性和效率優(yōu)勢，引入了一些其他常用的PU學習方法作為對比。為了方便用戶使用Bagging TopPush方法，還研究了不同的模型參數(shù)選擇對排序性能的影響，并且給出了可靠的參數(shù)選擇范圍。

1 二部排序模型

近年來，得益于在信息檢索和推薦系統(tǒng)中的成功應用，二部排序得到了廣泛的關注。二部排序的目標是學習到一種排序模型使得某一類樣本的排列位置總是在另外一類之前。在一些數(shù)據(jù)挖掘應用中，比如網(wǎng)頁搜索和稀有光譜搜索等，人們尤其重視排序列表頂端的準確率狀況。這是因為在實際應用中，只有排序列表頂端的那部分樣本才有可能被人工查驗[14]。

Li等人提出的TopPush方法就是一種旨在優(yōu)化排序列表頂端準確率的二部排序模型。與其他二部排序模型相比，TopPush的計算復雜度關于訓練樣本數(shù)是線性的而不是二次的。下面首先介紹一下TopPush算法的基本思想和框架，然后再利用Bagging策略建立一種用于稀有光譜檢索的PU學習方法。

1.1 TopPush方法

令S = S+∪ S?為一組訓練數(shù)據(jù)，包括從P中隨機抽取的m個正類樣本和從U中隨機抽取的n個負類樣本，即 S

TopPush的目標是學習一個排序函數(shù) f : X →R，使得其能夠?qū)⒈M可能多的正類樣本排在第一個負類樣本前面。這個目標可以通過最小化下面的損失來實現(xiàn)：

其中Ⅱ(·)是指示函數(shù)，即當括號內(nèi)條件為真時函數(shù)值為一，否則函數(shù)值為零。最小化式（1），實際上就可以迫使負類樣本遠離排序序列的頂端，從而能保證盡可能多的正類樣本排在序列頂端位置。由于指示函數(shù)I(·)并非平滑函數(shù)，Li等人將式（1）中的指示函數(shù)用其非減可微的凸代理損失函數(shù)?(·)來代替，從而得到以下?lián)p失：

在實際應用中，凸代理損失函數(shù)包括截斷二次損失?(z) = max(0, 1 + z)2，指數(shù)損失?(z) = ez和logistic損失?(z) = log(1+ez)等。這里使用截斷二次損失函數(shù)來作為凸代理損失函數(shù)。

對于線性排序函數(shù)f(x) = wTx，學習過程可以用以下的優(yōu)化目標來描述：

其中w ∈ Rd是待學習的權值向量，λ ＞ 0是控制模型復雜度的正則化參數(shù)。關于TopPush模型的優(yōu)化方法，計算復雜度，和性能分析可以參見[3]。

1.2 用于稀有光譜檢索的BaggingTopPush方法

在稀有光譜檢索應用當中，給定一些已知的稀有光譜樣本，目標是將其他與之相關的樣本排在與之不相關樣本的前面。為了達到這個目標，可以通過將 P中的稀有樣本排在未標記樣本集 U 的任意一小部分樣本前面來實現(xiàn)。然而，未標記樣本集 U中可能隱含了一定比例的正類樣本，并且這個比例在實際應用中通常是未知的。因此對于從U中隨機抽取的一個樣本子集，其中含有的正類樣本可能很少也可能很多，這會使排序結(jié)果變得非常不穩(wěn)定性。幸運的是，這種情形恰好可以被 Bagging方法所利用，因為 Bagging方法的出發(fā)點就是去提高機器學習算法的穩(wěn)定性和精確度[15]。

假設K是每次從U中隨機抽取的樣本數(shù)，T是總的隨機抽樣的次數(shù)。BaggingTopPush方法首先利用正類樣本和每次隨機抽取的負類樣本訓練多個二部排序模型。每一個訓練好的二部排序模型ft都可以對U中的任一樣本分配一個分值。分配給U中的某個樣本的最后分值 f可以通過多個二部排序模型所分配分值的平均來計算。然后可以根據(jù)U中樣本的分值 f對其進行降序排序，并且返回排在序列頂端的一部分樣本作為候選體。Algorithm 1清晰地展示BaggingTopPush方法的流程。需要注意的是輸入變量 λ在這里所起的作用跟其在式(1.3)中所起的作用是相同的，即控制每個TopPush模型的復雜度。λ取值越小，模型越復雜，在訓練階段所消耗的時間也就越長。

Algorithm 1 用于稀有光譜檢索的BaggingTopPush輸入： P, U, K, T, 入.輸出： 排序函數(shù)f : X → R.1. 對于t = 1 to T 執(zhí)行從未標記樣本集U中抽取K個樣本，記為子集Ut。訓練TopPush模型ft使之能夠?qū)中樣本排在Ut中樣本的前面。2. 返回f=1T T ∑ft t1=

2 結(jié)論

在進行稀有天體光譜檢索時，如何從原始光譜特征中提取出對后續(xù)學習過程最有利的特征是一個非常具有挑戰(zhàn)性的問題。由于碳星光譜的特征比較寬比較明顯，所以可以直接使用PCA方法來提取特征。然而，如果稀有光譜的特征比較細小，那么需要通過定義一些線指數(shù)來提取其特征。

本文主要討論了稀有天體光譜搜索中的PU學習問題，并且提出了一種用于稀有光譜檢索的BaggingTopPush方法。基于二部排序和Bagging技術，BaggingTopPush方法集成了一系列的TopPush模型，其中每個子模型都能夠?qū)⒄悩颖九帕性趶腢中隨機抽取的負類樣本的前面。該方法的主要優(yōu)點是不僅能夠保證排序列表頂端位置處的準確率并且排序速度非常快，這對于海量光譜巡天數(shù)據(jù)的分析和挖掘是非常有意義的。與其他稀有光譜檢索方法相比，BaggingTopPush方法不僅具有最好的檢索效果而且消耗的時間最少。并且，合理的參數(shù)取值范圍，可以使 BaggingTopPush方法更加簡單易用。

用于稀有光譜檢索的BaggingTopPush方法的源代碼可以從此處下載：

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

[1] 黃炳良, 張忠琳. 預測市場技術在機器學習中的應用[J].軟件, 2014, 35(11): 31-35.

[2] 楊澤民. 數(shù)據(jù)挖掘中關聯(lián)規(guī)則算法的研究[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-)，研究生，主要研究方向：數(shù)據(jù)挖掘。