大規(guī)模脈沖星候選體信號(hào)的無(wú)監(jiān)督聚類分析研究?

劉 瑩 馬 智 游子毅 王 培 黨世軍 趙汝雙 董愛(ài)軍

(1貴州師范大學(xué)物理與電子科學(xué)學(xué)院 貴陽(yáng) 550025)

(2中國(guó)科學(xué)院國(guó)家天文臺(tái) 北京 100012)

1 引言

脈沖星領(lǐng)域的發(fā)現(xiàn)有力地推動(dòng)了天文學(xué)、物理學(xué)及導(dǎo)航等相關(guān)領(lǐng)域的發(fā)展[1–2].隨著500 m口徑球面射電望遠(yuǎn)鏡(Five-hundred-meter Aperture Spherical radio Telescope,FAST)的建成和19波束脈沖星漂移掃描巡天項(xiàng)目的開展,其高靈敏度且更大天區(qū)覆蓋面的特點(diǎn),在帶來(lái)脈沖星信號(hào)搜尋范圍的優(yōu)勢(shì)同時(shí)也產(chǎn)生了海量的觀測(cè)數(shù)據(jù),如何有效地從海量數(shù)據(jù)中篩選出脈沖星候選體成為脈沖星搜尋的關(guān)鍵.

基本的脈沖星搜尋中所需完成的工作為在周期(Period,P)-色散量(Dispersion Measure,DM)組成的兩維空間中搜索穩(wěn)定周期性脈沖信號(hào).目前,圖形工具輔助或基于統(tǒng)計(jì)的傳統(tǒng)方法已無(wú)法滿足如此龐大數(shù)據(jù)量處理的需要.人工智能技術(shù)運(yùn)用于脈沖星的候選體篩選根據(jù)方法原理主要分為3類.第1類是基于經(jīng)驗(yàn)公式的候選體排序算法,Lee等[3]提出的PEACE(Pulsar Evaluation Algorithm for Candidate Extraction)算法依賴于一些假設(shè),如信噪比、脈沖輪廓形狀等,在實(shí)際處理得到的脈沖星候選體中很多特征都不能很好地?cái)M合理想的特征形狀,從而可能導(dǎo)致一些有特殊形狀脈沖,如寬脈沖、偏離色散量-信噪比(DM-S/N)曲線或者低流量的脈沖星被遺漏.第2類是直接利用候選體診斷圖自動(dòng)提取特征的神經(jīng)網(wǎng)絡(luò)圖像識(shí)別模型.Wang等[4]提出基于FAST漂移掃描測(cè)量的神經(jīng)網(wǎng)絡(luò)群方法,標(biāo)志著深度神經(jīng)網(wǎng)絡(luò)圖像模式識(shí)別系統(tǒng)(Pulsar Image-based Classification System,PICS)的進(jìn)一步發(fā)展.Zeng等[5]通過(guò)改進(jìn)周期信號(hào)篩選算法(sifting)設(shè)計(jì)了一種Concat卷積神經(jīng)網(wǎng)絡(luò)(Concat Convolutional Neural Network,CCNN)來(lái)識(shí)別從FAST收集到的候選體.劉曉飛等[6–7]提出基于深層殘差網(wǎng)絡(luò)的脈沖星候選體分類,可以有效提高脈沖星候選體自動(dòng)識(shí)別的精度.這類方法促使模型通過(guò)數(shù)據(jù)驅(qū)動(dòng)學(xué)習(xí),從診斷子圖中自主學(xué)習(xí)“類脈沖星”的模式.相比傳統(tǒng)機(jī)器學(xué)習(xí)方法泛化性更好,但需要手動(dòng)標(biāo)記每個(gè)訓(xùn)練數(shù)據(jù)的子圖且樣本訓(xùn)練需求量較大,導(dǎo)致大量額外工作量的投入.第3類是基于機(jī)器學(xué)習(xí)的分類算法,包括基于人工神經(jīng)網(wǎng)絡(luò)的SPINN(Straightforward Pulsar Identification using Neutral Networks)分類器[8]、高斯-黑林格快速?zèng)Q策樹(Gaussian Hellinger Very Fast Decision Tree,GH-VFDT)[9–10]、偽最近質(zhì)心鄰域分類器(Pseudo-nearest Centroid Neighbour Classifier,PNCN)[11]以及基于自歸一化神經(jīng)網(wǎng)絡(luò)的候選體選擇方法[12]等.上述方法中,依靠人類經(jīng)驗(yàn)篩選的特征選擇是影響脈沖星篩選2值分類結(jié)果的關(guān)鍵.不全面的特征設(shè)計(jì)方案可能會(huì)弱化模型的性能,所以特征設(shè)計(jì)問(wèn)題尤為關(guān)鍵.此外,一些多方法集成的混合模型也取得顯著效果[13–14].

在實(shí)際的大規(guī)模脈沖星數(shù)據(jù)計(jì)算和搜索中,由于輸入數(shù)據(jù)集中大部分都是無(wú)標(biāo)簽數(shù)據(jù),而且存在脈沖星與非脈沖星樣本數(shù)據(jù)比例極不均衡的問(wèn)題,導(dǎo)致使用有監(jiān)督學(xué)習(xí)分類方法來(lái)識(shí)別脈沖星候選體的時(shí)間代價(jià)和工作量都相當(dāng)大.本文在Rodriguez等[15]和Wang等[16]工作的基礎(chǔ)上,提出一種基于混合聚類算法的脈沖星候選體篩選方案.通過(guò)基于滑動(dòng)窗口的數(shù)據(jù)劃分策略以及基于MapReduce模型的并行化設(shè)計(jì),該方案在提高候選體篩選效率的同時(shí),能聚類出更有參考意義的分類以促進(jìn)特殊脈沖星的發(fā)現(xiàn).在Parkes高時(shí)間分辨率宇宙脈沖星巡天(High Time Resolution Universe Survey,HTRU)數(shù)據(jù)集HTRU2[17]上與其他常用機(jī)器學(xué)習(xí)分類方法進(jìn)行實(shí)驗(yàn)對(duì)比,結(jié)果表明所提出方案在精確度(Precision)和召回率(Recall)上均取得較優(yōu)的結(jié)果,分別為0.946和0.905;根據(jù)Sun-Ni定理[18],當(dāng)并行執(zhí)行節(jié)點(diǎn)足夠且通信代價(jià)可忽略時(shí),該算法的總運(yùn)行時(shí)間理論上會(huì)明顯減少.

2 相關(guān)工作基礎(chǔ)

實(shí)驗(yàn)數(shù)據(jù)集HTRU2來(lái)自澳大利亞Parkes望遠(yuǎn)鏡的多波束(13個(gè)波束)的觀測(cè)[9],所用脈沖星信號(hào)搜尋管道的DM值設(shè)定為0–2000 cm?3·pc,描述了在高時(shí)間分辨率宇宙勘測(cè)期間收集的基于PRESTO(Pulsar Exploration and Search Toolkit)軟件處理的脈沖星候選樣本數(shù)據(jù).該數(shù)據(jù)集共包含17898個(gè)數(shù)據(jù)樣本,其中16259個(gè)射頻干擾(Radio Frequency Interference,RFI)虛假樣本和1639個(gè)真實(shí)脈沖星樣本,特征值包含脈沖輪廓的均值、脈沖輪廓的標(biāo)準(zhǔn)差、脈沖輪廓的超額峰度、脈沖輪廓的偏度、DM-S/N曲線的均值、DM-S/N曲線的標(biāo)準(zhǔn)差、DM-S/N曲線的超峰額度和DM-S/N曲線的偏度8個(gè)屬性.HTRU2是一個(gè)開放的、樣本相對(duì)豐富的數(shù)據(jù)集,認(rèn)可度較高,因此被廣泛用于評(píng)估脈沖星候選體分類算法的性能.

聚類是處理大型數(shù)據(jù)挖掘問(wèn)題的關(guān)鍵方法之一,包含基于劃分、基于密度、基于網(wǎng)格等聚類算法.K-Means[19]作為一種基于劃分的聚類算法得到廣泛應(yīng)用.但原始K-Means存在聚類效果依賴于初始中心點(diǎn)的選擇、只能應(yīng)對(duì)數(shù)值型數(shù)據(jù)、異常值干涉大等缺陷.因此,不少學(xué)者一直在對(duì)該算法進(jìn)行改進(jìn).Arthur等[20]提出一種選擇盡可能相距較遠(yuǎn)的數(shù)據(jù)點(diǎn)作為初始中心的K-Means++算法,改進(jìn)中心點(diǎn)的選擇;Nguyen[21]提出K-modes算法用于解決K-Means只能應(yīng)對(duì)數(shù)值型數(shù)據(jù)的缺點(diǎn).基于密度的聚類方法,比如典型的DBSCAN(Density Based Spatial Clustering of Applications with Noise)算法[22],能發(fā)現(xiàn)任意形狀的聚類,但聚類樣本大、收斂時(shí)間長(zhǎng),對(duì)于簇密度不均勻情況聚類效果不佳.Rodriguez等[15]提出了一種基于密度峰值的快速搜索聚類算法CFSFDP(Clustering by Fast Search and Find of Density Peaks),其主要思想是簇類中心的密度應(yīng)大于周圍鄰居的密度,且不同簇類中心之間的距離相對(duì)較遠(yuǎn).由于該算法僅關(guān)注了密度較大且距離相對(duì)遠(yuǎn)的點(diǎn)作為中心點(diǎn),容易將含有多個(gè)高密度點(diǎn)的同一簇類錯(cuò)誤地分成多個(gè)簇類.為克服這個(gè)缺陷,Wang等[16]進(jìn)一步提出一種基于密度層次劃分的多中心密度峰值聚類算法McDPC(Multi-center Density Peak Clustering).

基于層次的聚類不需要預(yù)先指定聚類數(shù)且可以發(fā)現(xiàn)類的層次關(guān)系,但計(jì)算復(fù)雜度太高.本文借鑒國(guó)內(nèi)外理論研究和實(shí)踐應(yīng)用的成功經(jīng)驗(yàn),就如何將這些不同聚類算法的優(yōu)點(diǎn)有效結(jié)合并用于大規(guī)模候選體信號(hào)的聚類分析提出建議對(duì)策.

3 混合聚類算法

本文所提出的方法結(jié)合了基于密度層次和劃分的聚類思想.首先,采用K近鄰的多項(xiàng)式核(Polynomial)函數(shù)計(jì)算數(shù)據(jù)點(diǎn)密度(見(jiàn)下文(2)式),排除密度過(guò)小的離群點(diǎn)干擾;其次,結(jié)合密度峰值及層次思想,用于多密度簇類層次的劃分,從而確定初始聚類中心點(diǎn).再次,運(yùn)用基于高斯徑向基核(Radial Basis Function,RBF)距離的K-Means迭代進(jìn)行數(shù)據(jù)點(diǎn)分配與簇中心優(yōu)化.具體步驟如下:

步驟(1)進(jìn)行數(shù)據(jù)預(yù)處理,通過(guò)主成分分析方法(Principal Component Analysis,PCA)對(duì)脈沖星觀測(cè)數(shù)據(jù)進(jìn)行特征選擇和降維,從而得到特征向量為b的新特征空間輸入數(shù)據(jù)集.可選的候選體物理特征值包括脈沖輻射(單峰、雙峰和多峰)、周期、色散值、信噪比、噪聲信號(hào)、信號(hào)斜波、非相干功率之和、相干功率等等.

步驟(2)數(shù)據(jù)點(diǎn)i和j之間的馬氏距離由下式計(jì)算:

其中,T表示轉(zhuǎn)置,S是多維隨機(jī)變量的協(xié)方差矩陣,再根據(jù)上式計(jì)算各數(shù)據(jù)點(diǎn)基于K近鄰的局部Polynomial核密度ρi.Polynomial核函數(shù)擁有的全局特性,使其泛化性能增強(qiáng).

其中,Knearest(i)表示樣本i的K個(gè)近鄰對(duì)象構(gòu)成的集合,c為偏置系數(shù),d為多項(xiàng)式的階.為消除數(shù)據(jù)變異大小和數(shù)值大小的影響,分別對(duì)d ij和ρi均采用離差標(biāo)準(zhǔn)化處理成D ij和Rhoi,如下.

其中,mind和minρ分別代表d ij和ρi的最小值,maxd和maxρ分別代表d ij和ρi的最大值.

步驟(3)根據(jù)(5)式剔除離群點(diǎn).設(shè)定密度的閾值為threshold,inlier表示密度大于閾值的數(shù)據(jù)對(duì)象的集合.

再由(6)式計(jì)算非離群點(diǎn)之間的距離δi.δi表示inlier集合中,若對(duì)象i非該集合中的最大密度對(duì)象max(Rhoinlier),i到密度比它大且距離最近的樣本j的距離.若i為最大密度對(duì)象,則表示i到密度比它小且距離最遠(yuǎn)的樣本j的距離.剔除離群點(diǎn)有助于簇類中心點(diǎn)的選擇.另外,密度過(guò)小的數(shù)據(jù)點(diǎn)數(shù)量少且分布邊緣化.由于其稀缺性及低密度化,在數(shù)據(jù)分布中呈異常,而異?，F(xiàn)象可能是純?cè)肼暬蛱厥饷}沖星.這部分?jǐn)?shù)據(jù)后續(xù)將作進(jìn)一步的確定.

步驟(4)所有距離δi大于某個(gè)已定義閾值(λ)的數(shù)據(jù)點(diǎn)可生成2維決策圖,例如,1組隨機(jī)生成數(shù)據(jù)的2維決策圖如圖1所示,其中,橫軸表示密度Rhoi,縱軸表示距離δi.

假定對(duì)該2維決策圖實(shí)例的Rhoi軸和δi軸分別按照大小為θ和γ的間隔進(jìn)行劃分,如圖2所示.

若在Rhoi軸或δi軸劃分區(qū)域包含兩個(gè)或兩個(gè)以上的無(wú)數(shù)據(jù)點(diǎn)存在區(qū)域,則稱該空隙區(qū)域?yàn)榭諈^(qū).在圖2(a)和2(b)中,空區(qū)把所有的數(shù)據(jù)點(diǎn)劃分為兩個(gè)密度區(qū)域,將最右的密度區(qū)域稱作最大密度區(qū)域,其余為低密度區(qū)域.

在低密度區(qū)域,由于區(qū)分度不高,將該低密度區(qū)域相應(yīng)的小簇均合并成一個(gè)簇類;在最大密度區(qū)域,若所有的代表點(diǎn)都在同一個(gè)δi區(qū)域,則將這些代表點(diǎn)均選作獨(dú)立的簇類中心;若代表點(diǎn)不在同一個(gè)δi區(qū)域,則這些代表點(diǎn)間距離區(qū)分度不高,可能屬于同一個(gè)簇類,因此需要將相應(yīng)的小簇合并成一個(gè)大簇.

圖1 決策圖實(shí)例Fig.1 Example of decision graph

步驟(5)確定簇類數(shù)k以及對(duì)應(yīng)集群C m(1≤m≤k)的中心centerm.

步驟(6)根據(jù)就近原則將各個(gè)數(shù)據(jù)點(diǎn)i分配給距離最近的centerm所在簇類,相似性度量方式采用RBF核距離,如(7)式所示.RBF核函數(shù)擁有局部特性且學(xué)習(xí)能力強(qiáng),通過(guò)RBF核距離可實(shí)現(xiàn)對(duì)i和j間測(cè)度距離向高維空間的轉(zhuǎn)換.

其中,η代表核函數(shù)寬度.按照(8)式計(jì)算新簇內(nèi)數(shù)據(jù)點(diǎn)均值作為新的中心center′m,n m表示屬于的數(shù)據(jù)點(diǎn)總數(shù).

圖2 隨機(jī)生成數(shù)據(jù)集的Rho i劃分和δi劃分.左:Rho i劃分;右:δi劃分.θ=2,γ=0.2.Fig.2 Rho i andδi division of randomly generated data set.Left:Rho i division;Right:δi division.θ=2,γ=0.2.

步驟(7)計(jì)算數(shù)據(jù)集所有對(duì)象的誤差平方和SSE:

直到SSE值不再發(fā)生變化,算法停止,否則回到步驟(6).

整體算法流程圖如圖3所示.

4 并行化設(shè)計(jì)

4.1 基于滑動(dòng)窗口的數(shù)據(jù)集劃分策略

為劃定更全面的脈沖星識(shí)別范圍,根據(jù)數(shù)據(jù)結(jié)構(gòu)最大化地準(zhǔn)確篩選候選體,采用滑動(dòng)窗口理念[23]進(jìn)行數(shù)據(jù)劃分,將數(shù)據(jù)劃分為L(zhǎng)個(gè)數(shù)據(jù)塊,每個(gè)數(shù)據(jù)塊表示為Block(o)(1≤o≤L).擬通過(guò)從真實(shí)樣本中挑選一組較完備的各類脈沖星候選體特征數(shù)據(jù)作為樣本,用v表示,每輪劃定Batchsize=w的窗口,按特定比例(v:w)加入到待檢測(cè)數(shù)據(jù),w表示滑動(dòng)窗口Batchsize數(shù).滑動(dòng)窗口數(shù)據(jù)分配方法如圖4所示.目前,聚類存在一基本假設(shè),即處在相同聚類中的示例有較大的可能擁有相同標(biāo)記.因此,根據(jù)各類數(shù)據(jù)分布的稠密或稀疏區(qū)域設(shè)定決策邊界,從而確定脈沖星數(shù)據(jù)分布區(qū)域,進(jìn)行對(duì)脈沖星信號(hào)與非脈沖星干擾信號(hào)的區(qū)域劃分.通過(guò)計(jì)算各簇內(nèi)部脈沖星樣本分布密度以統(tǒng)計(jì)相似程度,選取脈沖星樣本占有率大于某個(gè)比例的簇進(jìn)入脈沖星候選體列表;聚類流程步驟(3)所排除的噪聲點(diǎn)則有可能是特殊脈沖星.

圖3 混合聚類算法的流程圖Fig.3 Flow chart of hybrid clustering algorithm

4.2 基于MapReduce/Spark模型的并行化設(shè)計(jì)方案

針對(duì)大規(guī)模的脈沖星數(shù)據(jù)處理,依據(jù)Sun-Ni定理,研究該聚類算法在實(shí)現(xiàn)MapReduce計(jì)算模型的并行化時(shí)是非常有必要的.一方面,可提高聚類結(jié)果的精確度;另一方面,能夠降低數(shù)據(jù)比較的次數(shù).Sun-Ni定理中引入了一個(gè)函數(shù)G(p)表示存儲(chǔ)容量受限時(shí)工作負(fù)載的增加量,p表示并行節(jié)點(diǎn)數(shù).該定律提出在滿足固定時(shí)間加速比所規(guī)定的時(shí)間限制的前提下且擁有足夠的內(nèi)存空間時(shí),對(duì)問(wèn)題進(jìn)行縮放能有效地利用內(nèi)存空間.圖5是基于MapReduce/Spark模型的并行化設(shè)計(jì)流程圖,首先通過(guò)上述基于滑動(dòng)窗口的方法將數(shù)據(jù)劃分為L(zhǎng)個(gè)數(shù)據(jù)塊后并行執(zhí)行.下一步,由Map1和Reduce1函數(shù)完成Block(o)(1≤o≤L)中數(shù)據(jù)點(diǎn)的密度計(jì)算以及初始聚類中心點(diǎn)(cluster centers)的選取.需要說(shuō)明的是在Map階段的輸入項(xiàng)中,key是行號(hào),value是當(dāng)前樣本各維度的值組成的列表.而在Reduce階段的輸出中,key.id即初始聚類中心.最后,Map2和Reduce2函數(shù)迭代完成Block(o)內(nèi)每個(gè)數(shù)據(jù)點(diǎn)到cluster centers(o)的距離計(jì)算并重新標(biāo)記其所屬簇類(每個(gè)簇C m均有對(duì)應(yīng)編號(hào)).其中用Reduce2函數(shù)計(jì)算出新的簇中心為下一輪聚類任務(wù)作準(zhǔn)備.比較當(dāng)前輪簇中心與上一輪對(duì)應(yīng)簇中心之間的距離,若變化小于給定的閾值,則運(yùn)行結(jié)束;否則將新簇中心作為下一輪的聚類中心.在聚類結(jié)束后,提取出脈沖星簇和噪聲點(diǎn).Spark作為一種大規(guī)模數(shù)據(jù)處理通用的計(jì)算引擎,其計(jì)算過(guò)程與MapReduce類似.

5 實(shí)驗(yàn)對(duì)比分析

單機(jī)實(shí)驗(yàn)的硬件環(huán)境為:處理器Intel Core i7-9700K@3.6GHz,內(nèi)存48GB DDR4 3000 MHz,顯卡Nvidia GeForce RTX 2080 Ti;軟件環(huán)境為:Windows 10 64bit系 統(tǒng) 下Anaconda4.8+python3.8+numpy1.18.5框架.

5.1 數(shù)據(jù)劃分

實(shí)驗(yàn)采用公開數(shù)據(jù)集HTRU2,其中共包含1639顆真實(shí)脈沖星樣本和16259個(gè)由RFI產(chǎn)生的虛假樣本.從該數(shù)據(jù)集的1639顆已知脈沖星中隨機(jī)選取1600顆作為脈沖星樣本集s,而剩余39顆被隨機(jī)混入到虛假數(shù)據(jù)樣本中形成待檢測(cè)數(shù)據(jù)集.根據(jù)4.1節(jié)的數(shù)據(jù)劃分策略,將滑動(dòng)窗口大小Batchsize設(shè)置為2,單位大小為1161,待檢測(cè)數(shù)據(jù)集按Batchsize被均分為(t1,t2,...,t13,t14),由此實(shí)驗(yàn)數(shù)據(jù)劃分為{Block(1):[s,t1,t2],Block(2):[s,t2,t3],...,Block(13):[s,t13,t14],Block(14):[s,t14,t1]}共14個(gè)數(shù)據(jù)塊.各個(gè)Block(i)分別進(jìn)行聚類,當(dāng)聚類完成后,選取脈沖星樣本占有率≥50%的簇進(jìn)入脈沖星候選體列表.

圖4 基于滑動(dòng)窗口的數(shù)據(jù)分配Fig.4 Data distribution scheme based on sliding window

5.2 評(píng)價(jià)指標(biāo)

候選體分類常采用準(zhǔn)確率(Accuracy)、精度(Precision)、召回率(Recall)和F1-分?jǐn)?shù)(F1-Score)4個(gè)指標(biāo)對(duì)算法進(jìn)行評(píng)估.Accuracy能大致反映整體判斷正確與否,但當(dāng)數(shù)據(jù)不均衡時(shí)并不能客觀地反映分類的性能.Precision用于判斷正類樣本數(shù)中真實(shí)正類樣本數(shù)所占之比,Recall則是判斷正確的正樣本數(shù)與所有正類樣本數(shù)之比.由于聚類的Precision和Recall往往相互矛盾,所以可選取F1-Score來(lái)綜合度量這兩個(gè)指標(biāo).表1表示分類的混淆矩陣.

結(jié)合4.2節(jié)并行化設(shè)計(jì)方法,則實(shí)驗(yàn)的評(píng)價(jià)指標(biāo)采用總體Precision、Recall和F1-Score設(shè)定如下:

其中,TP表示被正確歸類為正樣本的數(shù)量,FN是被錯(cuò)誤歸類為負(fù)樣本的數(shù)量,FP為被錯(cuò)誤歸類為正樣本的數(shù)量,TPo、FNo和FPo則分別表示L個(gè)數(shù)據(jù)塊中第o個(gè)數(shù)據(jù)塊的TP、FN和FP值,UTP=TP1∪TP2∪TP3···TPL代表每個(gè)小數(shù)據(jù)塊識(shí)別脈沖星的并集,Recallo和Precisiono分別表示單個(gè)數(shù)據(jù)塊的召回率和精度,Recalltotal則表示實(shí)驗(yàn)的總體召回率.

表1 混淆矩陣Table 1 Confusion matrix

5.3 參數(shù)設(shè)置

實(shí)驗(yàn)涉及的參數(shù)包括計(jì)算數(shù)據(jù)點(diǎn)密度的K近鄰參數(shù),密度的閾值threshold,Polynomial核參數(shù)c和d,RBF核參數(shù)η,篩選小簇的閾值λ,對(duì)密度區(qū)域劃分的θ值以及對(duì)距離區(qū)域劃分的γ值.具體設(shè)置如表2.

表2 算法參數(shù)Table 2 Parameters of algorithm

圖5 MapReduce流程圖Fig.5 Flow chart of MapReduce

5.4 聚類結(jié)果分析

表3顯示了不同監(jiān)督學(xué)習(xí)和無(wú)監(jiān)督學(xué)習(xí)算法在HTRU2數(shù)據(jù)集上的性能對(duì)比.在無(wú)監(jiān)督算法中,混合聚類算法具有最高的Recall值即90.5%.與有監(jiān)督學(xué)習(xí)算法相比,該算法的Recall值僅低于GMO SNNNNNNNNN (Genetic,Synthetic Minority Over-sampling and Self-normalizing Neural Networks)[12],F1-Score低于GMO SNNNNNNNNN、Random Forest[24]和KNN(K-Nearest Neighbor)[25]算法,但高于SVM(Support Vector Machines)[11]和PNCN[11].另外,經(jīng)多輪的對(duì)照實(shí)驗(yàn)(每輪隨機(jī)挑選出39顆脈沖星形成待檢測(cè)數(shù)據(jù)集),得出被該算法檢測(cè)出的脈沖星數(shù)最高一次達(dá)到36顆,均值為34顆.由于混合聚類的無(wú)監(jiān)督學(xué)習(xí)和快速收斂的優(yōu)點(diǎn),適用于大規(guī)模脈沖星數(shù)據(jù)快速分類挖掘的場(chǎng)景.實(shí)驗(yàn)結(jié)果表明,所提出的基于混合聚類的方案具有可行性和有效性.在實(shí)際脈沖星搜索場(chǎng)景下,隨著相關(guān)參數(shù)、脈沖星樣本集以及數(shù)據(jù)劃分策略的優(yōu)化,其聚類效果將進(jìn)一步提升.

5.5 時(shí)間復(fù)雜度分析

設(shè)實(shí)驗(yàn)數(shù)據(jù)集的樣本數(shù)為n,所提出算法與McDPC[16]、PNCN[11]的時(shí)間復(fù)雜度如表4所示.對(duì)于McDPC,計(jì)算ρi和δi時(shí)間復(fù)雜度為O(n2),基于不同密度水平的聚類時(shí)間復(fù)雜度也為O(n2),所以整個(gè)算法的時(shí)間復(fù)雜度為O(n2);PNCN時(shí)間復(fù)雜度取自其最壞情況下的計(jì)算量O(2nM K+F M K2/2),M為元素的特征數(shù),F為類別數(shù),M和F設(shè)定為常量.所提出混合聚類算法在不使用4.1、4.2節(jié)的并行化方案的情形下,其串行時(shí)間復(fù)雜度為O(n2+nk H M),H為迭代次數(shù).由于k、H、M為常量,其復(fù)雜度簡(jiǎn)化為O(n2),這接近于McDPC但比PNCN高.然而,若運(yùn)行在所設(shè)計(jì)的并行模型上,依據(jù)Sun-Ni定理,其復(fù)雜度變?yōu)镺((G(p)z)2),其中G(p)為因子,z為Block(o)的樣本個(gè)數(shù)且z?n;當(dāng)并行節(jié)點(diǎn)數(shù)p足夠(p值趨近于被劃分的數(shù)據(jù)塊L達(dá)到某個(gè)閾值)且通信開銷可忽略時(shí),G(p)→1,即復(fù)雜度趨近于O(z2).可見(jiàn),該算法的并行化方案理論上在確保聚類效果的同時(shí)較大地改善了算法執(zhí)行時(shí)間.

表3不同方法在HTRU2數(shù)據(jù)集上的效果Table 3 Results with different methods on HTRU2 data set

表4 算法復(fù)雜度Table 4 Time complexity statistics of various algorithms

6 總結(jié)與展望

為解決FAST天文大數(shù)據(jù)背景下的脈沖星候選體智能篩選問(wèn)題,提出一種基于混合聚類分析算法的快速篩選方案.其新穎之處在于,結(jié)合了基于密度層次和劃分的聚類方法的特點(diǎn)以提高聚類性能;為更好展現(xiàn)數(shù)據(jù)間分布的“疏密程度”,體現(xiàn)聚類結(jié)果中不同簇的數(shù)據(jù)結(jié)構(gòu)差異,采用K近鄰的局部Polynomial核函數(shù)方法改善密度計(jì)算,并且利用RBF核函數(shù)將數(shù)據(jù)轉(zhuǎn)化至高維空間進(jìn)行相似性度量;通過(guò)基于滑動(dòng)窗口的分組策略與MapReduce/Spark并行化設(shè)計(jì),進(jìn)一步提升篩選召回率并減少執(zhí)行時(shí)間.

對(duì)比實(shí)驗(yàn)分析和時(shí)間復(fù)雜度分析,證明所提出方案具有可行性和有效性,隨著實(shí)際場(chǎng)景中數(shù)據(jù)分組與相關(guān)參數(shù)的優(yōu)化,其各項(xiàng)性能指標(biāo)會(huì)有更大提升.無(wú)監(jiān)督聚類方法更適用于大量無(wú)標(biāo)簽數(shù)據(jù)集的分類以及脈沖星與非脈沖星樣本數(shù)據(jù)比例極不均衡情形.下一步,將通過(guò)較完備的FAST實(shí)驗(yàn)數(shù)據(jù)繼續(xù)對(duì)混合聚類方案進(jìn)行改進(jìn);另一方面,研究該方案接入到PRESTO脈沖星搜索流程pipeline進(jìn)行實(shí)際測(cè)試,為FAST觀測(cè)的大量候選體信號(hào)篩選提供理論和實(shí)踐參考.