KNN算法在天文數據挖掘中的應用

山東師范大學附屬中學 黃宇龍

KNN算法在天文數據挖掘中的應用

山東師范大學附屬中學 黃宇龍

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

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

1.概要

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

2.恒星/類星體分類

恒星和類星體的分類是天文學基本分類任務之一.恒星、類星體都是發光天體,但它們的光譜等參數有所不同,他們在不同波段所表現的性質不同,需要通過聚類算法將它們各自區分,這對我們了解恒星和類星體的演化歷史以及發現特殊天體有著重要的研究價值.尤其在面對海量的天文數據時,將天體自動分類變得尤為重要.

對于恒星與類星體,他們在不同光譜波段的表現不同,因此可以將這些參數作為它們自己的特征來區分它們.從各類分類算法中,我們挑選KNN算法來解決這個問題,KNN算法可以用于簡單的分類,其算法思路簡單,但計算量較大,適用于樣本容量較大的類域自動分類問題,與本類問題相符合并,本章節將闡述KNN算法的原理及實現,并探究這個算法的效率.

2.1 KNN方法原理

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

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

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

KNN聚類算法的主要流程包括:數據預處理、數據準備、特征選擇、聚類、結果驗證與評價.

2.2 數據預處理及數據準備

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

圖2.1 各顏色特征三維分布

2.3 KNN算法應用

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

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

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

對于K值的選擇,我們則分別選取K=3,5,9,13進行KNN算法分類,計算獲取分類準確率.

3.分類結果及分析

通過實現KNN算法程序,執行數據樣本的分類,其結果如下表:

在表中,當訓練/測試樣本數量比為1:1時,不同的K值對于準確率影響不大,在92%左右;訓練/測試樣本數量比為2:1時,選取K=5時準確率最高,為93.09%,準確率跟隨K值增大先增大后減小;訓練/測試樣本數量比為5:1時,K=5時準確率最高,為94.66%,且準確率同樣跟隨K值增大,先增大后減小.

在另一方面,當確定K值選擇后,分類的準確率跟隨訓練/測試數據量比的提高而提高,例如K=5時,分類的準確率由92.33%提高至94.66%.

在圖2.2中直觀地顯示了不同的訓練/測試數據量比在某一K值下,準確率與訓練/測試數據量比的關系;圖2.3則展示了在確定的訓練/測試數據量比下,K值的選定與準確率的關系.

圖2.2 確定K值下,訓練樣本數與正確率的關系圖

圖2.3 確定訓練樣本數,K值與正確率的關系圖

由上圖可以得出兩個結論:第一,KNN算法在訓練樣本數量達到一定的情況下,若增加訓練樣本數,正確率增長不明顯,且趨于穩定,但是由于訓練樣本數量增加,樣本的計算量也會線性的增長,最終導致耗時呈線性增加.第二,確定的訓練/測試數據量比下,正確率隨K值變化,先在某一段達到峰值,而后開始下降.算法的耗時會跟隨隨K值增長呈線性增長.當正確率經過峰段開始下降時,由于K值的增加,算法所使用的時間也線性增長,導致算法效率下降.峰段的K值由樣本的坐標分布密度決定.

因此,用K近鄰算法進行天體歸類時,若要保證正確率的同時提高效率,則應選擇合適的K值、訓練樣本容量.

4.總結

本文我們主要探索了KNN算法于恒星與類星體分類問題的應用以及算法的執行效率和正確率.由于現代技術的進步使得天文觀測設備的觀測能力大大提高,天文觀測產生的數據變得十分龐大.讓計算機來進行管理、分類這些以PB計的數據的工作可以使這項繁瑣的任務快速準確地解決.而恒星、類星體都是發光天體,但它們的光譜等參數有所不同,通過這些參數的特征可以區分它們.因此我們使用五種不同的顏色作為特征輸入,使用KNN算法解決這個問題.KNN算法在訓練樣本數量達到一定的情況下,若增加訓練樣本數,正確率增長不明顯,同時算法的耗時也會線性的增長;另一方面,分類的正確率也會隨K值變化,先在某一段達到峰值,而后開始下降,且算法耗時也跟隨K的增加而線性增加.因此,使用KNN算法進行天體歸類時,若要保證正確率的同時提高效率,則應同時考慮選擇合適的K值、訓練樣本容量.但總得來說,KNN算法在該問題中能夠很好的區分恒星與類星體,準確率在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]張彥霞,趙永恒.天文學中的數據挖掘和知識發現[J].天文學進展,2002,20(4):312-323.

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