山東師范大學(xué)附屬中學(xué) 黃宇龍

KNN算法在天文數(shù)據(jù)挖掘中的應(yīng)用

山東師范大學(xué)附屬中學(xué) 黃宇龍

現(xiàn)代技術(shù)的進(jìn)步使得天文觀測(cè)設(shè)備的觀測(cè)能力大大提高,天文觀測(cè)產(chǎn)生的數(shù)據(jù)變得十分龐大,因此能夠借助計(jì)算機(jī)對(duì)數(shù)據(jù)進(jìn)行高效率的分析顯得尤為重要.為了解決這個(gè)問題,借助數(shù)據(jù)挖掘的技術(shù)對(duì)天文數(shù)據(jù)進(jìn)行分析勢(shì)在必行.本文主要論述了利用聚類算法中的KNN算法,通過選擇特定光波段數(shù)據(jù)作為特征,對(duì)恒星與類星體進(jìn)行分類的方法,并探索KNN算法在解決恒星和類星體分類問題的效率以及正確率.

KNN算法;分類;恒星;類星體

1.概要

隨著大型光學(xué)望遠(yuǎn)鏡的精度和深度不斷提高,其觀測(cè)能力大大提高,天文學(xué)中與光學(xué)波段相關(guān)的數(shù)據(jù)量不斷增大,數(shù)據(jù)復(fù)雜程度不斷增加.例如大型綜合巡天望遠(yuǎn)鏡在一晚上所觀測(cè)得到的數(shù)據(jù)量約為20TB數(shù)據(jù),而最后將會(huì)得到大約130PB的數(shù)據(jù).如果由計(jì)算機(jī)來進(jìn)行管理、分類這些以PB計(jì)的數(shù)據(jù)的工作,則可以快速準(zhǔn)確地解決對(duì)天文數(shù)據(jù)分析這項(xiàng)繁瑣的任務(wù).隨著計(jì)算機(jī)科學(xué)、統(tǒng)計(jì)學(xué)與數(shù)學(xué)等方面在近幾年的高速發(fā)展,數(shù)據(jù)挖掘逐漸出現(xiàn)在人們眼前,并逐步地被用于從天文數(shù)據(jù)中提取信息、發(fā)現(xiàn)稀有天體和現(xiàn)象.天文數(shù)據(jù)具有海量性、高維性、非線性等特點(diǎn),所以需要更加高效精準(zhǔn)的挖掘和分析算法或工具來應(yīng)對(duì)日益增長的需求,關(guān)于天文學(xué)中數(shù)據(jù)挖掘應(yīng)用可參見一些綜述文章[1-3].

2.恒星/類星體分類

恒星和類星體的分類是天文學(xué)基本分類任務(wù)之一.恒星、類星體都是發(fā)光天體,但它們的光譜等參數(shù)有所不同,他們?cè)诓煌ǘ嗡憩F(xiàn)的性質(zhì)不同,需要通過聚類算法將它們各自區(qū)分,這對(duì)我們了解恒星和類星體的演化歷史以及發(fā)現(xiàn)特殊天體有著重要的研究?jī)r(jià)值.尤其在面對(duì)海量的天文數(shù)據(jù)時(shí),將天體自動(dòng)分類變得尤為重要.

對(duì)于恒星與類星體,他們?cè)诓煌庾V波段的表現(xiàn)不同,因此可以將這些參數(shù)作為它們自己的特征來區(qū)分它們.從各類分類算法中,我們挑選KNN算法來解決這個(gè)問題,KNN算法可以用于簡(jiǎn)單的分類,其算法思路簡(jiǎn)單,但計(jì)算量較大,適用于樣本容量較大的類域自動(dòng)分類問題,與本類問題相符合并,本章節(jié)將闡述KNN算法的原理及實(shí)現(xiàn),并探究這個(gè)算法的效率.

2.1 KNN方法原理

K鄰近(KNN)算法,是一個(gè)理論上相對(duì)成熟的算法,也是典型的機(jī)器學(xué)習(xí)的算法之一.它基于特征空間中預(yù)測(cè)樣本周圍距離它最近的樣本類別數(shù)目作為判定依據(jù)來進(jìn)行分類.其基本思路為:如果一個(gè)樣本在特征空間中的K個(gè)最相似(即特征空間中最鄰近)的樣本中的大多數(shù)屬于某一個(gè)類別,則該樣本也屬于這個(gè)類別,而這K個(gè)所選定的鄰居樣本,則為已正確分類的樣本.

KNN算法不需要訓(xùn)練過程,但是需要大量樣本數(shù)據(jù)來確定最合適的K值用于樣本的分類.技術(shù)上K的取值需要針對(duì)不同的問題來設(shè)定,但是K值一般都是奇數(shù),為的是每個(gè)未知樣本都能夠得出確定的計(jì)算結(jié)果.因此在下面的算法應(yīng)用中,本文將分別討論設(shè)定不同的K值時(shí)所能獲得的準(zhǔn)確率,以提高分類結(jié)果的準(zhǔn)確率.

KNN算法中樣本之間,在判定最鄰近樣本的距離時(shí),一般使用的是歐式距離,其他的距離還有Cosine距離等.不同的距離計(jì)算方式,其計(jì)算復(fù)雜程度亦不相同,最終會(huì)影響分類算法執(zhí)行的效率.

KNN聚類算法的主要流程包括:數(shù)據(jù)預(yù)處理、數(shù)據(jù)準(zhǔn)備、特征選擇、聚類、結(jié)果驗(yàn)證與評(píng)價(jià).

2.2 數(shù)據(jù)預(yù)處理及數(shù)據(jù)準(zhǔn)備

在本文中所采用的數(shù)據(jù)來源于國家天文臺(tái)老師提供的望遠(yuǎn)鏡巡天得到的數(shù)據(jù),測(cè)試所使用的數(shù)據(jù)集大小為3256個(gè)樣本,其中類星體樣本數(shù)為1617,恒星樣本數(shù)為1639.在使用數(shù)據(jù)進(jìn)行分類之前,需要對(duì)原始數(shù)據(jù)進(jìn)行處理,這一步主要是要去除無效數(shù)據(jù),將數(shù)據(jù)特征進(jìn)行提取,并轉(zhuǎn)換數(shù)據(jù)格式為程序所需要的格式.在選擇數(shù)據(jù)特征時(shí),本文主要考慮恒星與類星體在不同波段的光亮強(qiáng)度不同,因此主要采用了u, g, r,i,z五個(gè)可見光波段的數(shù)據(jù)以及亮度r作為特征,應(yīng)用于樣本間距離的計(jì)算.為了直觀的展現(xiàn)恒星與類星體在不同顏色的分布,本文繪制了圖2.1來展現(xiàn)顏色特征坐標(biāo)的三維分布圖,在圖中可以明顯地看出,兩種星體的特征坐標(biāo)分布各自呈現(xiàn)大體集中、部分分散的狀態(tài).兩種星體在明顯不同的區(qū)域集中,這也是分類的條件.邊緣區(qū)域的分布呈現(xiàn)松散、交替的特點(diǎn).可以推測(cè),分類錯(cuò)誤的樣本基本分布在邊緣區(qū)域.

圖2.1 各顏色特征三維分布

2.3 KNN算法應(yīng)用

在數(shù)據(jù)預(yù)處理、提取樣本特征之后,便可以使用KNN算法進(jìn)行分類.首先,我們將整個(gè)樣本(包括1617個(gè)類星體樣本,1639個(gè)恒星樣本)隨機(jī)的切分為兩個(gè)部分:第一部分用于訓(xùn)練,第二部分用于測(cè)試.為了能夠全面的查看訓(xùn)練與測(cè)試樣本比例對(duì)于分類準(zhǔn)確率的影響,我們將訓(xùn)練及測(cè)試樣本比例設(shè)為三組,分別是1:1,2:1,5:1.

在運(yùn)用KNN算法去解決問題時(shí),需要設(shè)定算法對(duì)應(yīng)的模型參數(shù)以及輸入?yún)?shù)兩大部分.輸入?yún)?shù)即上一小節(jié)所得到的樣本的特征值;模型參數(shù)對(duì)于KNN算法即K的取值以及度量樣本距離的計(jì)算方式.樣本距離的計(jì)算方式?jīng)Q定了KNN在實(shí)際應(yīng)用中的執(zhí)行效率;K值的選擇決定了樣本分類結(jié)果的準(zhǔn)確程度.在本實(shí)驗(yàn)中,樣本距離計(jì)算方式采用歐式距離,n維空間的計(jì)算公式如下:

由于數(shù)據(jù)中u-g,g-r,r-i,i-z這四種顏色特征的取值大多數(shù)小于1,求解平方差后繼續(xù)取根號(hào)所得到的結(jié)果小數(shù)位會(huì)被裁切,導(dǎo)致精度下降,此外取根號(hào)運(yùn)算也增加了額外的計(jì)算負(fù)擔(dān),因此本文中的歐氏距離僅作平方差,距離計(jì)算方法如下:

對(duì)于K值的選擇,我們則分別選取K=3,5,9,13進(jìn)行KNN算法分類,計(jì)算獲取分類準(zhǔn)確率.

3.分類結(jié)果及分析

通過實(shí)現(xiàn)KNN算法程序,執(zhí)行數(shù)據(jù)樣本的分類,其結(jié)果如下表:

在表中,當(dāng)訓(xùn)練/測(cè)試樣本數(shù)量比為1:1時(shí),不同的K值對(duì)于準(zhǔn)確率影響不大,在92%左右;訓(xùn)練/測(cè)試樣本數(shù)量比為2:1時(shí),選取K=5時(shí)準(zhǔn)確率最高,為93.09%,準(zhǔn)確率跟隨K值增大先增大后減小;訓(xùn)練/測(cè)試樣本數(shù)量比為5:1時(shí),K=5時(shí)準(zhǔn)確率最高,為94.66%,且準(zhǔn)確率同樣跟隨K值增大,先增大后減小.

在另一方面,當(dāng)確定K值選擇后,分類的準(zhǔn)確率跟隨訓(xùn)練/測(cè)試數(shù)據(jù)量比的提高而提高,例如K=5時(shí),分類的準(zhǔn)確率由92.33%提高至94.66%.

在圖2.2中直觀地顯示了不同的訓(xùn)練/測(cè)試數(shù)據(jù)量比在某一K值下,準(zhǔn)確率與訓(xùn)練/測(cè)試數(shù)據(jù)量比的關(guān)系;圖2.3則展示了在確定的訓(xùn)練/測(cè)試數(shù)據(jù)量比下,K值的選定與準(zhǔn)確率的關(guān)系.

圖2.2 確定K值下,訓(xùn)練樣本數(shù)與正確率的關(guān)系圖

圖2.3 確定訓(xùn)練樣本數(shù),K值與正確率的關(guān)系圖

由上圖可以得出兩個(gè)結(jié)論:第一,KNN算法在訓(xùn)練樣本數(shù)量達(dá)到一定的情況下,若增加訓(xùn)練樣本數(shù),正確率增長不明顯,且趨于穩(wěn)定,但是由于訓(xùn)練樣本數(shù)量增加,樣本的計(jì)算量也會(huì)線性的增長,最終導(dǎo)致耗時(shí)呈線性增加.第二,確定的訓(xùn)練/測(cè)試數(shù)據(jù)量比下,正確率隨K值變化,先在某一段達(dá)到峰值,而后開始下降.算法的耗時(shí)會(huì)跟隨隨K值增長呈線性增長.當(dāng)正確率經(jīng)過峰段開始下降時(shí),由于K值的增加,算法所使用的時(shí)間也線性增長,導(dǎo)致算法效率下降.峰段的K值由樣本的坐標(biāo)分布密度決定.

因此,用K近鄰算法進(jìn)行天體歸類時(shí),若要保證正確率的同時(shí)提高效率,則應(yīng)選擇合適的K值、訓(xùn)練樣本容量.

4.總結(jié)

本文我們主要探索了KNN算法于恒星與類星體分類問題的應(yīng)用以及算法的執(zhí)行效率和正確率.由于現(xiàn)代技術(shù)的進(jìn)步使得天文觀測(cè)設(shè)備的觀測(cè)能力大大提高,天文觀測(cè)產(chǎn)生的數(shù)據(jù)變得十分龐大.讓計(jì)算機(jī)來進(jìn)行管理、分類這些以PB計(jì)的數(shù)據(jù)的工作可以使這項(xiàng)繁瑣的任務(wù)快速準(zhǔn)確地解決.而恒星、類星體都是發(fā)光天體,但它們的光譜等參數(shù)有所不同,通過這些參數(shù)的特征可以區(qū)分它們.因此我們使用五種不同的顏色作為特征輸入,使用KNN算法解決這個(gè)問題.KNN算法在訓(xùn)練樣本數(shù)量達(dá)到一定的情況下,若增加訓(xùn)練樣本數(shù),正確率增長不明顯,同時(shí)算法的耗時(shí)也會(huì)線性的增長;另一方面,分類的正確率也會(huì)隨K值變化,先在某一段達(dá)到峰值,而后開始下降,且算法耗時(shí)也跟隨K的增加而線性增加.因此,使用KNN算法進(jìn)行天體歸類時(shí),若要保證正確率的同時(shí)提高效率,則應(yīng)同時(shí)考慮選擇合適的K值、訓(xùn)練樣本容量.但總得來說,KNN算法在該問題中能夠很好的區(qū)分恒星與類星體,準(zhǔn)確率在90%以上,值得在該問題的研究中推廣.

[1]BALL N M,BRUNNER R J.Data Mining and Machine Learning in Astronomy[J].International Journal ofModern Physics D, 2010,19:1049-1106.

[2]張彥霞,趙永恒.天文學(xué)中的數(shù)據(jù)挖掘和知識(shí)發(fā)現(xiàn)[J].天文學(xué)進(jìn)展,2002,20(4):312-323.

[3]BORNE K.Scientific Data Mining in Astronomy[OL].ARXIV,2009,arXiv:0911.0505.