劉 旭

（北京信息科技大學(xué) 計(jì)算機(jī)學(xué)院，北京 100192）

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

劉 旭

（北京信息科技大學(xué) 計(jì)算機(jī)學(xué)院，北京 100192）

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

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

0 引言

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

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

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

關(guān)于 PU學(xué)習(xí)問題，過去二十年里已經(jīng)出現(xiàn)了很多種方法，它們大致可以總結(jié)為兩種基本類型：基于分類的PU學(xué)習(xí)和基于排序的PU學(xué)習(xí)。

基于分類的 PU學(xué)習(xí)可以追溯到僅利用正類樣本來訓(xùn)練分類器的單類分類方法，如單類支持向量機(jī)（One Class Support Vector Machine, OCSVM）[3]和 SVDD（Support Vector Data Description）[4]。OCSVM和SVDD這兩種方法都需要足夠多的正類樣本才能較準(zhǔn)確地學(xué)習(xí)出正類樣本的邊界。事實(shí)上，除了已知的正類樣本外，未標(biāo)記樣本也能夠提供很多有用信息。Biased SVM（Biased Support Vector Machine）[5]就是同時利用正類樣本和未標(biāo)記樣本進(jìn)行建模的方法。后來Mordelet[6]等人利用集成學(xué)習(xí)中bagging技巧推廣和改進(jìn)了Biased SVM，他們的方法被稱為Bagging SVM。Mordelet 等人已經(jīng)證明Bagging SVM的效果與Biased SVM相當(dāng)，甚至超過Biased SVM。此外，當(dāng)未標(biāo)記樣本占據(jù)了數(shù)據(jù)集的絕大部分時Bagging SVM相比于Biased SVM大大減輕了計(jì)算負(fù)擔(dān)。

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

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

1 二部排序模型

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

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

1.1 TopPush方法

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

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

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

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

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

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

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

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

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

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

2 結(jié)論

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

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

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

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

[1] 黃炳良, 張忠琳. 預(yù)測市場技術(shù)在機(jī)器學(xué)習(xí)中的應(yīng)用[J].軟件, 2014, 35(11): 31-35.

[2] 楊澤民. 數(shù)據(jù)挖掘中關(guān)聯(lián)規(guī)則算法的研究[J]. 軟件, 2013,34(11): 71-72.

[3] 黃衍, 查偉雄. 隨機(jī)森林與支持向量機(jī)分類性能比較[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ù)挖掘。