CN114386466A - Parallel hybrid clustering method for candidate signal mining in pulsar search - Google Patents

Abstract

The invention discloses a parallel hybrid clustering method for candidate signal mining in pulsar search, which comprises the following steps: clustering analysis of pulsar candidate signals; grouping the data sets based on a grouping strategy of a sliding window, dividing the data sets according to a specific window value Batchsize =1160, and setting the size of the sliding window to be w = 2; selecting more complete various pulsar candidate body characteristic data 1600 from real samples as a group of samples, respectively adding the samples into the data to be detected corresponding to each sliding window to form 1 data block, and dividing a data set into a plurality of parallel data blocks with the same size; and parallelizing the data blocks based on the MapReduce/Spark calculation model to realize the clustering. The invention can improve the clustering performance, improve the screening recall rate and reduce the execution time.

Description

A Parallel Hybrid Clustering Method for Candidate Signal Mining in Pulsar Searching

technical field

The invention belongs to the technical field of astronomy, and in particular relates to a parallel hybrid clustering method for candidate body signal mining in pulsar searching.

Background technique

The discovery of pulsars has favorably promoted the development of related fields such as astronomy, physics, and navigation. With the completion of the 500-meter-aperture spherical radio telescope FAST and the 19-beam receiver sky survey detection, its high sensitivity and larger sky area coverage have The advantages of the pulsar signal search range are accompanied by the huge growth of observation data. How to effectively screen out pulsar candidates from the massive data becomes the key to pulsar search;

The work that needs to be done in the basic pulsar search is to search for stable periodic pulse signals in the two-dimensional space composed of P (period)-DM (dispersion quantity). The need for processing such a huge amount of data; the candidate screening of pulsars applied by artificial intelligence technology is mainly divided into three categories according to the method principle; the first category is the candidate sorting algorithm based on empirical formula; this kind of algorithm relies on some assumptions, such as Signal-to-noise ratio, pulse profile shape, etc., many of them cannot be well fitted in practice, which may cause some pulses with special shapes, such as wide pulses, partial DM curves or low-flow pulsars to be missed; the second type is to directly use candidate A neural network image recognition model that automatically extracts features from body diagnostic maps; this kind of algorithm has better generalization than traditional machine learning methods, but it needs to manually label the subgraphs of each training data and requires a large amount of sample training, resulting in a lot of extra labor input; the third category is the classification algorithm based on machine learning; the feature selection based on human experience screening is the key to affecting the binary classification results of pulsar screening. Incomplete feature design schemes may weaken the performance of the model, so the feature selection The design problem is particularly critical; in addition, some mixed models of multi-method ensemble have also achieved remarkable results;

In the actual large-scale pulsar data calculation and search, since most of the input data sets are unlabeled data, and there is an extremely unbalanced proportion of pulsar and non-pulsar sample data, the supervised learning classification method is used to identify The time cost and workload of pulsar candidates are quite large;

The experimental dataset HTRU2 from the multi-beam (13 beams) observations of the Parkes Telescope in Australia, using the DM value of the pulsar signal search pipeline set from 0 to 2000cm-3pc, describes the The pulsar candidate sample data processed by PRESTO (Pulsar Exploration and Search Toolkit) software; the pulsar search and analysis suite developed by the PRESTO NRAO Radio Astronomy Observatory in the United States, which has been used for multiple sky surveys to process short integration time data and X-ray data; HTRU2 The dataset contains a total of 17,898 data samples, of which 16,259 are false examples generated by RFI or noise and 1,639 are real pulsar examples; eigenvalues include the mean of the pulse profile, the standard deviation of the pulse profile, the excess kurtosis of the pulse profile, the pulse profile The skewness of the profile, the mean of the DM-S/N curve, the standard deviation of the DM-S/N curve, the excess peak limit of the DM-S/N curve, and the skewness of the DM-S/N curve are eight attributes; HTRU2 is An open dataset with relatively abundant samples, with a high degree of recognition, and is therefore widely used to evaluate the performance of pulsar candidate classification algorithms;

Clustering is one of the key methods to deal with large-scale data mining problems, including clustering algorithms based on partitioning, density-based and grid-based; k-means is widely used as a partition-based clustering algorithm. But the original k-means The clustering effect depends on the selection of the initial center point, can only deal with numerical data, and the outliers interfere greatly. Therefore, many scholars have been improving the algorithm. (Privacy-Preserving Mechanisms for k-ModesClustering, Computers and Security, 2018) proposed the K-MODES algorithm to solve the disadvantage that k-means can only deal with numerical data; density-based clustering methods, such as the typical DBSCAN (Density Based SpatialClustering of Applications with Noise) algorithm can find clusters of any shape, but the clustering samples are large and the convergence time is long, and the clustering effect is not good for uneven cluster density; (Clustering by fast search and find of density peaks, Science, 2014) proposed a fast search clustering algorithm based on density peaks, the main idea of which is that the density of cluster centers should be greater than that of surrounding neighbors, and the distances between different cluster centers are relatively far; since the algorithm only focuses on In order to overcome this defect, (McDPC: multi-center densitypeak clustering, Neural Computing and Applications, 2020) further proposed a multi-center clustering method based on density hierarchical division; hierarchical clustering does not need to pre-specify the number of clusters and can discover the hierarchical relationship of classes, but the computational complexity is too high.

SUMMARY OF THE INVENTION

The purpose of the present invention is to overcome the above shortcomings and provide a parallel hybrid clustering method for candidate body signal mining in pulsar searching, which improves clustering performance, improves screening recall rate and reduces execution time.

The purpose of the present invention and the solution to its main technical problems are achieved by adopting the following technical solutions:

A parallel hybrid clustering method for candidate body signal mining in pulsar search of the present invention includes the following steps:

(1) Cluster analysis of pulsar candidate signals:

The polynomial function of K nearest neighbors is used to calculate the density of data points, and the samples whose density value is less than the threshold 0.01 are screened out. These samples will be further judged by the candidate diagnostic map to determine whether it is noise or a new astronomical phenomenon, and outliers with too small density will be excluded. interference;

Combined with the characteristics of the density peak and hierarchical clustering process, it is used to divide the multi-density cluster level in the data set, merge some micro-clusters with similar densities and distances in the same area, and determine the initial cluster center point;

The k-means iteration based on Gaussian Radial Basis Kernel (RBF) distance is used to assign all data points and optimize the cluster center, and the (RBF) kernel function is used to calculate the similarity between sample data points, which can realize the measurement distance to high-dimensional transformation of space;

(2) Group the data set based on the sliding window grouping strategy, divide it according to a specific window value Batchsize=1160, and set the sliding window size to w=2; it is planned to select relatively complete various types of pulsar candidates from real samples 1600 pieces of volume feature data are used as a set of samples, and are added to the data to be detected corresponding to each round of sliding windows to form a data block, and the data set is divided into multiple parallel data blocks of the same size;

(3) The clustering is realized by data block parallelization based on the MapReduce/Spark computing model.

The above-mentioned parallel hybrid clustering method for candidate body signal mining in pulsar search, wherein the clustering analysis method described in step (1) is:

① Carry out data preprocessing, through feature extraction method (Fifty Years of Pulsar Candidate Selection: From simple filters to a new principled real-time classification approach, Monthly Notices of the Royal Astronomical Society, 2016) and principal component analysis (PCA) Feature selection and dimension reduction are performed on the pulsar candidate data in the pulsar search process of PRESTO (Pulsar Exploration and Search Toolkit) software, so as to obtain a new feature space input dataset with feature vector b; optional physical eigenvalues of the candidate body Including pulse radiation (single-peak, double-peak and multi-peak), period, dispersion value, signal-to-noise ratio, noise signal, signal ramp, sum of incoherent power, coherent power;

② According to formula (1), the Mahalanobis distance between data points i and j is calculated as

Among them, S is the covariance matrix of multi-dimensional random variables; then calculate the local Polynomial kernel density of each data point based on K nearest neighbors according to formula (2).

Among them, c is the bias coefficient, and d is the order of the polynomial; in order to eliminate the influence of the data variation size and numerical value, the dispersion standardization is used for both d _ij and ρ _i as follows;

Among them, min _d and min _ρ represent the minimum value of d _ij and ρ _i respectively, and max _d and max _ρ represent the maximum value of d _ij and ρ _i respectively;

(3) Eliminate outliers according to formula (5), and then calculate the distance δ _i between non-outlier points by formula (6). Elimination of outliers is helpful for the selection of cluster center points; in addition, data with too small density The number of points is small and the distribution is marginal; due to its scarcity and low density, it is abnormal in the data distribution, and the abnormal phenomenon may be pure noise or astronomical new phenomena (such as special pulsars); this part of the data will be passed through the corresponding Candidate diagnostic map for further determination;

inlier={ρ _i >ρ _threhold }, ρ _threhold =0.01 (5)

④ All data points whose distance δ is greater than the threshold λ can generate a two-dimensional decision map; in which, the horizontal axis is represented by density ρ, and the vertical axis is represented by distance δ; on the two-dimensional decision map, density-level micro-clusters are merged, The method is: if there are two or more areas without data points on the ρ-axis or δ-axis division area, the void area is called an empty area; the empty area divides all data points into two density areas, The rightmost density area is called the maximum density area, and the rest are low density areas;

(A) In the low-density area, due to the low degree of discrimination, the corresponding micro-clusters in this area are merged into one cluster class;

(B) In the maximum density area, if all the representative points are in the same delta area, these representative points are selected as independent cluster centers; if they are not in the same delta area, the distance discrimination between these representative points is different. high, may belong to the same cluster class, so the corresponding micro-clusters need to be merged into a large cluster;

⑤ Determine the number of clusters k and the center center _i of the corresponding cluster C _i (1≤i≤k);

⑥ According to the principle of proximity, each data point x _j is allocated to the cluster class where the nearest center _i is located, and the similarity measurement method adopts the RBF kernel distance, as shown in formula (7); the RBF kernel function has local characteristics and strong learning ability, The transformation of measured distance to high-dimensional space can be realized through RBF kernel distance;

Wherein, n represents the kernel function width; According to formula (8), calculate the mean value of all data points in the new cluster C _i ' as the new center center _i ', and n _i represent the total number of data points belonging to C _i ';

⑦ Calculate the sum of squared errors SSE for all objects in the dataset:

Until the SSE value no longer changes, the algorithm stops, otherwise go back to step ⑥;

The above-mentioned parallel hybrid clustering method for candidate body signal mining in pulsar search, wherein the method for grouping data sets based on a sliding window grouping strategy in step (2) is: maximizing and accurately screening candidates according to data structure First, define the window size (Batchsize=1160), and divide the data set to be detected into L blocks (the data volume of the last block is not enough, and the data of the first block can be used for filling); Set the size of the sliding window w = 2, the first round starts from the first and second blocks, and the sliding window advances 1 bit in each round, pointing to the corresponding data block; the last round points to the combination of the last block and the first block, A total of L rounds of segmentation need to be performed; it is planned to select a set of 1600 relatively complete types of pulsar candidate feature data from the real samples as samples, and each round is added to the data corresponding to the sliding window to form the data block to be detected. Therefore, The data set is divided into L parallel data blocks to be detected; at present, there is a basic assumption in clustering, that is, the examples in the same cluster are more likely to have the same label; therefore, according to the distribution of various data The decision boundary is set in the dense or sparse area, so as to determine the pulsar data distribution area, and the area division of the pulsar signal and the non-pulsar interference signal; by calculating the distribution density of the pulsar samples in each cluster to calculate the similarity degree, select the pulsar Clusters with sample occupancy greater than 50% enter the pulsar candidate list; the list of noise points excluded in step 3 in the cluster analysis method may lead to the discovery of new phenomena.

The above-mentioned parallel hybrid clustering method for candidate body signal mining in pulsar search, wherein in step (3), the method for realizing the clustering by parallelizing data blocks based on the MapReduce/Spark computing model is: for large-scale For pulsar data processing, according to the Sun-Ni theorem, it is very necessary to study the parallel implementation of the clustering algorithm in the MapReduce computing model; on the one hand, it can improve the accuracy of the clustering results; on the other hand, it can reduce the data comparison The number of times; the Sun-Ni theorem introduces a function G(p) to represent the increase in workload when the storage capacity is limited; the law proposes that there is enough memory under the premise of satisfying the time limit specified by the fixed time speedup ratio When the space is large, scaling the problem can effectively utilize the memory space; first, the data is divided into L data blocks (Block(1),...,Block(L)) by the above sliding window-based method and then executed in parallel; Next, the Map1 and Reduce1 functions complete the density calculation of the data points in each Block(i) (1≤i≤L) and the selection of the initial cluster centers (it should be noted that the <key of the Map stage) , value> input: key is the row number, value is a list of the values of each dimension of the current sample; the output of the Reduce stage: key.id is the initial cluster center); finally, the Map2 and Reduce2 functions iteratively complete each block in Block(i). Calculate the distance from each data point to the cluster centers (cluster centers(i)) and re-label the cluster category to which it belongs, and use the Reduce 2 function to calculate the new cluster center to prepare for the next round of clustering tasks; compare the current round The distance between the cluster center and the corresponding cluster center of the previous round, if the change is less than the given threshold, the operation ends; otherwise, the new cluster center is used as the cluster center of the next round; after the clustering is over, the pulsar is extracted Clusters and abnormal noise points; Spark is a general computing engine for large-scale data processing, and its computing process is similar to MapReduce.

Compared with the prior art, the present invention has obvious advantages and beneficial effects. As can be seen from the above technical solutions, the present invention firstly uses a polynomial kernel (Polynomial) function of K-nearest neighbors to calculate the density of data points to eliminate the interference of outliers with too small density; secondly, combined with density peaks and levels, it is used for multi-density cluster hierarchy. Then, use the k-means iteration based on Gaussian Radial Basis Kernel (RBF) distance to perform data point allocation and cluster center optimization; The parallel design of the Spark model has greatly improved the running time of the scheme while ensuring the effect of candidate clustering; in the Parkes High Time Resolution Universe Survey 2 (HTRU2) data Compared with other commonly used machine learning classification methods, the results show that the proposed scheme achieves better results in both precision and recall, which are 0.946 and 0.905, respectively; according to the Sun-Ni theorem, When the parallel execution nodes are sufficient and the communication cost is negligible, the total running time of the algorithm will theoretically be significantly reduced; due to the similarity clustering characteristics of clustering, this method can improve the efficiency of candidate screening while clustering more Informative classification to facilitate the discovery of new phenomena (such as special pulsar signals).

Description of drawings

Figure 1a is a two-dimensional decision ρ division diagram of density hierarchical clustering;

Figure 1b is a two-dimensional decision δ partition diagram of density hierarchical clustering;

Fig. 2 is based on the data distribution of sliding window;

Figure 3 MapReduce flow chart;

Figure 4 Comparison of average runtimes.

Detailed ways

Example:

Referring to FIG. 1 to FIG. 3 , a parallel hybrid clustering method for candidate body signal mining in pulsar search according to the present invention includes the following steps:

1. Hybrid cluster analysis

(1) Carry out data preprocessing, through feature extraction method (Fifty Years of Pulsar Candidate Selection: From simple filters to a new principled real-time classification approach, Monthly Notices of the Royal Astronomical Society, 2016) and principal component analysis (PCA) Feature selection and dimension reduction are performed on the pulsar candidate data in the pulsar search process based on PRESTO (Pulsar Exploration and Search Toolkit) software, so as to obtain a new feature space input dataset with feature vector b. The optional candidate physical characteristic values include pulsed radiation (single-peak, double-peak and multi-peak), period, dispersion value, signal-to-noise ratio, noise signal, signal ramp, sum of incoherent power, coherent power and so on.

(2) Calculate the Mahalanobis distance between data points i and j according to formula (1) as

where S is the covariance matrix of a multidimensional random variable. Then calculate the local Polynomial kernel density based on K nearest neighbors of each data point according to formula (2). The global characteristics of the Polynomial kernel function make it have strong generalization performance.

where c is the bias coefficient and d is the order of the polynomial. In order to eliminate the influence of data variation size and numerical size, both d _ij and ρ _i are treated with dispersion standardization as follows.

Among them, min _d and min _ρ represent the minimum value of d _ij and ρ _i , respectively, and max _d and max _ρ represent the maximum value of d _ij and ρ _i , respectively.

(3) Eliminate outliers according to formula (5), and then calculate the distance δ _i between non-outliers by formula (6). Eliminating outliers is helpful for the selection of cluster center points. In addition, the number of data points that are too low in density is small and the distribution is marginal. Due to their scarcity and low density, they are anomalies in the data distribution, and the anomalies may be pure noise or astronomical new phenomena (such as special pulsars). This part of the data will be further determined by the corresponding candidate diagnostic map in the future.

inlier={ρ _i >ρ _threhold }, ρ _threhold =0.01 (5)

(4) All data points whose distance δ is greater than the threshold λ can generate a two-dimensional decision map. For example, a two-dimensional decision diagram of a group of randomly generated data is shown in Figure 1, where the horizontal axis represents the density ρ, and the vertical axis represents the distance δ.

Assume that the ρ-axis and δ-axis of this two-dimensional decision graph instance are divided into intervals of size θ and γ, respectively. Figure 1 ρ division and δ division of randomly generated dataset. Left: ρ division; Right: δ division. θ=2γ=0.2;

If there are two or more regions where no data points exist on the ρ-axis or δ-axis division region, the void region is called an empty region. In Figures 1(a) and 1(b), the empty area divides all data points into two density areas, the rightmost density area is called the maximum density area, and the rest are low density areas.

1) In the low-density area, due to the low degree of discrimination, the corresponding micro-clusters in the area are merged into one cluster class;

2) In the maximum density area, if all the representative points are in the same delta area, these representative points are selected as independent cluster centers; if they are not in the same delta area, the distance between these representative points is not high. , may belong to the same cluster class, so the corresponding microclusters need to be merged into a large cluster.

(5) Determine the number of clusters k and the center _i of the corresponding cluster C _i (1≤i≤k).

(6) According to the principle of proximity, each data point x _j is assigned to the cluster class where the nearest center _i is located, and the similarity measurement method adopts the RBF kernel distance, as shown in formula (7). The RBF kernel function has local characteristics and strong learning ability. Through the RBF kernel distance, the conversion of measured distance to high-dimensional space can be realized.

where η represents the kernel function width. According to formula (8), the mean of all data points in the new cluster C _i ' is calculated as the new center center _i ', and _ni represents the total number of data points belonging to C _i '.

(7) Calculate the sum of squared errors SSE for all objects in the dataset:

Until the SSE value no longer changes, the algorithm stops, otherwise go back to step (6).

2. Dataset partition strategy based on sliding window

In order to delineate a more comprehensive range of pulsar identification and maximally and accurately screen candidates according to the data structure, the sliding window concept is used to divide the data. As shown in Figure 2, define the window size (

Batchsize=1160), it is planned to select a set of 1600 relatively complete types of pulsar candidate feature data from real samples as samples, and add the data corresponding to the sliding window (its size w=2) in each round to form the data to be detected piece. Currently, clustering has a fundamental assumption that examples in the same cluster are more likely to have the same label. Therefore, the decision boundary is set according to the dense or sparse areas of various data distributions, so as to determine the pulsar data distribution area, and to divide the area of pulsar signals and non-pulsar interference signals. By calculating the distribution density of pulsar samples in each cluster to calculate the similarity degree, the clusters with pulsar sample occupancy greater than 50% are selected to enter the pulsar candidate list; the list of noise points excluded in the mixed cluster analysis step (3) may be will lead to the discovery of new astronomical phenomena.

3. Parallel design based on MapReduce/Spark model

For large-scale pulsar data processing, it is necessary to study the parallel implementation of the clustering algorithm in the MapReduce computing model according to the Sun-Ni theorem. On the one hand, it can improve the accuracy of clustering results; on the other hand, it can reduce the number of data comparisons. As shown in Figure 3, the data is firstly divided into L data blocks (Block(1), ..., Block(L)) by the above sliding window-based method and executed in parallel. Next, the Map1 and Reduce1 functions complete the density calculation of the data points in each Block(i) (1≤i≤L) and the selection of the initial cluster centers (it should be noted that the <key of the Map stage) , value> input: key is the row number, value is a list of the values of each dimension of the current sample. Reduce phase output: key.id is the initial cluster center). Finally, the Map2 and Reduce2 functions iteratively complete the calculation of the distance from each data point in Block(i) to the cluster centers (cluster centers(i)) and re-label the cluster category to which it belongs, and the Reduce 2 function is used to calculate the new cluster The center prepares for the next round of clustering tasks. Compare the distance between the cluster center of the current round and the corresponding cluster center of the previous round. If the change is less than the given threshold, the operation ends; otherwise, the new cluster center is used as the cluster center of the next round. After clustering, pulsar clusters and abnormal noise points are extracted.

Experimental example:

The hardware environment is: Linux cluster environment with 4 physical computing nodes, including 2 Intel Core i7-9700K@3.6GHz CPU, 1 Intel Core i7-1065G7@1.5GHz CPU and 1 Intel Core i5-9300H@2.4GHz CPU , with 32 CPU cores (total RAM is 68G, total disk space is 3T); the software environment is: Anaconda3-4.2.0, Hadoop-2.7.6 and Spark-2.3.1-bin-hadoop2.6 under centos7 system frame.

1. Data division

The public dataset HTRU2 was used, which was processed by a feature extraction method (Fifty Years of Pulsar Candidate Selection: From simple filters to a new principled real-time classification approach, Monthly Notices of the Royal Astronomical Society, 2016). The sliding window size Batchsize is set to 1160, 1600 pulsars are randomly selected from the known pulsars as the pulsar sample set s, and the remaining 39 are randomly mixed into the non-pulsar data samples to form the data set to be detected. According to the data division strategy in Section 4.1, the data set to be tested is divided into (t ₁ , t ₂ , ..t ₁₄ ) according to the Batchsize, so the experimental data is divided into {Block(1):[s,t ₁ , t ₂ ],Block(2):[s,t ₂ ,t ₃ ],...,

Block(13):[s,t ₁₃ ,t ₁₄ ],Block(14):[s,t ₁₄ ,t ₁ ]} a total of 14 data blocks. Each Block(i) is clustered separately. When the clustering is completed, the clusters with pulsar sample occupancy ≥ 50% are selected to enter the pulsar candidate list.

2. Evaluation indicators

Candidate classification often uses four indicators to evaluate the algorithm: Accuracy, Precision, Recall, and F1-score.

Accuracy can roughly reflect whether the overall judgment is correct or not, but it cannot objectively reflect the classification performance when the data is unbalanced. Precision is used to judge the ratio of the number of true positive samples in the number of positive samples, and Recall is the ratio of the number of correct positive samples to the number of all positive samples. Since the Precision and Recall of clustering are often contradictory, F1-Score can be selected to comprehensively measure these two indicators. Table 2 shows the classified confusion matrix.

Table 1 Confusion matrix

The evaluation indicators of the experiment use the overall Precision, Recall and F1-Score, which are set as follows:

Among them, L represents the number of divided data blocks, UTP=TP ₁ ∪TP ₂ ∪TP ₃ ...TP _L represents the union of the pulsars identified in each small data block, Recall _O represents the recall rate of a single data block, Recall _total represents the overall recall rate of all data blocks.

3. Parameter setting

The parameters involved in the experiment include the K-nearest neighbor parameter for calculating the density of data points, the density threshold ρ _threhold , the Polynomial kernel parameters c and d, the RBF kernel parameter η, the threshold λ for screening small clusters, the θ value for dividing the density region and the distance region. The gamma value of the division. The specific settings are as follows.

Table 2 Parameter settings

4. Analysis of clustering results

Table 3 shows the performance comparison of different supervised learning and unsupervised learning algorithms on the HTRU2 dataset. Among the unsupervised algorithms, the parallel hybrid clustering algorithm has the highest Recall value i.e. 90.5%. Compared with the supervised learning algorithm, the Recall value of this algorithm is only lower than

GMO_SNNNNNNNNN (Pulsar Candidate Selection Based on Self-Normalized Neural Network, Acta Physica Sinica, 2020), F1-Score is lower than GMO_SNNNNNNNNN, Random Forest (Fifty years of pulsar candidates selection: from simple filters to a new principled real-time classificationapproach, Monthly Notices of the Royal Astronomical Society, 2016) and KNN algorithm, but higher than SVM and PNCN (Pulsar candidate selection using pseudo-nearest centroidneighbour classifier, Monthly Notices of the Royal Astronomical Society, 2020). In addition, after multiple rounds of control experiments of randomly selecting 39 pulsars to form the data set to be detected, it is concluded that the number of pulsars detected by the algorithm reaches 36 at one time, with an average of 34. Due to the advantages of unsupervised learning and fast convergence of hybrid clustering, it is suitable for the scene of fast classification and mining of large-scale pulsar data. The experimental results show that the proposed hybrid clustering-based scheme is feasible and effective. In the actual pulsar search scenario, with the optimization of related parameters, pulsar sample set and data partitioning strategy, the clustering effect will be further improved.

Table 3. Effects of different methods on the HTRU2 dataset

5. Time complexity analysis

Let the number of samples in the experimental dataset be n, and the time complexity of other algorithms (kmeans++, McDpc, PNCN) is shown in Table 4. Among them, the time complexity of kmeans++ is O(nkTM), usually k, T, M are considered as constants, which can be simplified to O(n); for McDpc, the time complexity of calculating ρ and δ is O(n ² ), The time complexity of clustering based on different density levels is also O(n ² ), so the time complexity of the whole algorithm is O(n ² ); the time complexity of PNCN is taken from its worst-case calculation amount O(2nMK+ FMK ² /2), F and M are set as constants. The serial time complexity of the hybrid clustering algorithm is O(n ² +nkTM). Since k, T, and M are constants, the complexity is simplified to O(n ² ). Under the parallel computing platform, according to the Sun-Ni theorem, the complexity becomes O((G(P)m) ² ), where G(P) is the factor, m is the number of samples of Block(i) and m n ; When the number of parallel nodes P is sufficient (the value of P approaches the divided data block L reaches a certain threshold) and the communication overhead is negligible, G(P)→1, that is, the complexity approaches O(m ² ), Slightly worse than k-means++ and PNCN, but better than McDpc. This shows that the proposed scheme can improve the clustering effect while the running time is significantly reduced.

Table 4 Algorithm Complexity

^a T is the number of iterations, M is the number of features of the element, F is the number of categories, m is the number of samples of Block(i), and k is the number of cluster centers.

Comparing the experimental analysis and time complexity analysis, it is proved that the proposed scheme is feasible and effective. With the optimization of data grouping and related parameters in the actual scene, its various performance indicators will be greatly improved. The unsupervised clustering method is more suitable for the classification of a large number of unlabeled data sets, and the situation where the proportion of pulsar and non-pulsar sample data is extremely unbalanced.

6. Actual runtime

Figure 4 shows the average runtime comparison of the proposed method (parallel and serial) with McDPC, k-means++ and KNN on the same experimental equipment. As can be seen from the figure, the average running time of serial hybrid clustering is the longest, but parallel hybrid clustering (23.07s) is very short compared to other systems. Therefore, we can believe that the proposed parallel scheme significantly reduces the execution time while guaranteeing the classification performance.

The above are only preferred embodiments of the present invention, and do not limit the present invention in any form. Any simple modifications made to the above embodiments according to the technical essence of the present invention without departing from the technical solution content of the present invention, Equivalent changes and modifications still fall within the scope of the technical solutions of the present invention.

Claims (4)

1. A parallel hybrid clustering method for candidate body signal mining in pulsar search, comprising the following steps: (1) Cluster analysis of pulsar candidate signals: The polynomial kernel function of K-nearest neighbors is used to calculate the density of data points, and the samples whose density value is less than the threshold 0.01 are screened out. These samples will be further judged as noise or new astronomical phenomenon through the candidate diagnostic map, and the interference of outliers with too small density will be excluded; Combined with the characteristics of the density peak and hierarchical clustering process, it is used to divide the multi-density cluster level in the data set, merge some micro-clusters with similar densities and distances in the same area, and determine the initial cluster center point; The k-means iteration based on the Gauss radial basis kernel distance is used to allocate all data points and optimize the cluster center, and the kernel function is used to calculate the similarity between the sample data points, which can realize the conversion of the measurement distance to the high-dimensional space; (2) Group the data set based on the sliding window grouping strategy, divide it according to a specific window value Batchsize=1160, and set the sliding window size to w=2; it is planned to select relatively complete various types of pulsar candidates from real samples 1600 pieces of volume feature data are used as a set of samples, and are added to the data to be detected corresponding to each round of sliding windows to form a data block, and the data set is divided into multiple parallel data blocks of the same size; (3) The clustering is realized by data block parallelization based on the MapReduce/Spark computing model. 2. a kind of parallel hybrid clustering method for candidate body signal mining in pulsar search as claimed in claim 1, wherein the clustering analysis method described in step (1) is: ① Carry out data preprocessing, and perform feature selection and dimension reduction on the pulsar candidate data in the pulsar search process based on PRESTO software by feature extraction method and principal component analysis (PCA) method, so as to obtain a new feature vector with b Feature space input dataset; optional candidate physical feature values include pulsed radiation (single-peak, double-peak and multi-peak), period, dispersion value, signal-to-noise ratio, noise signal, signal ramp, sum of incoherent power , coherent power; ② According to formula (1), the Mahalanobis distance between data points i and j is calculated as

Among them, S is the covariance matrix of multi-dimensional random variables; then calculate the local Polynomial kernel density of each data point based on K nearest neighbors according to formula (2).

Among them, c is the bias coefficient, and d is the order of the polynomial; in order to eliminate the influence of the data variation size and numerical value, the dispersion standardization is used for both d _ij and ρ _i as follows;

Among them, min _d and min _ρ represent the minimum value of d _ij and ρ _i respectively, and max _d and max _ρ represent the maximum value of d _ij and ρ _i respectively; (3) Eliminate outliers according to formula (5), and then calculate the distance δ _i between non-outlier points by formula (6). Elimination of outliers is helpful for the selection of cluster center points; in addition, data with too small density The number of points is small and the distribution is marginal; due to its scarcity and low density, it is abnormal in the data distribution, and the abnormal phenomenon may be pure noise or astronomical new phenomena (such as special pulsars); this part of the data will be passed through the corresponding Candidate diagnostic map for further determination; inlier={ρ _i >ρ _threhold }, ρ _threhold =0.01 (5)

④ All data points whose distance δ is greater than the threshold λ can generate a two-dimensional decision map; in which, the horizontal axis is represented by density ρ, and the vertical axis is represented by distance δ; on the two-dimensional decision map, density-level micro-clusters are merged, The method is: if there are two or more areas without data points on the ρ-axis or δ-axis division area, the void area is called an empty area; the empty area divides all data points into two density areas, The rightmost density area is called the maximum density area, and the rest are low density areas; (A) In the low-density area, due to the low degree of discrimination, the corresponding micro-clusters in this area are merged into one cluster class; (B) In the maximum density area, if all the representative points are in the same delta area, these representative points are selected as independent cluster centers; if they are not in the same delta area, the distance discrimination between these representative points is different. high, may belong to the same cluster class, so the corresponding micro-clusters need to be merged into a large cluster; ⑤ Determine the number of clusters k and the center center _i of the corresponding cluster C _i (1≤i≤k); ⑥ According to the principle of proximity, each data point x _j is allocated to the cluster class where the nearest center _i is located, and the similarity measurement method adopts the RBF kernel distance, as shown in formula (7); the RBF kernel function has local characteristics and strong learning ability, The transformation of measured distance to high-dimensional space can be realized through RBF kernel distance;

Wherein, n represents the kernel function width; According to formula (8), calculate the mean value of all data points in the new cluster C _i ' as the new center center _i ', and n _i represent the total number of data points belonging to C _i ';

⑦ Calculate the sum of squared errors SSE for all objects in the dataset:

Until the SSE value no longer changes, the algorithm stops, otherwise go back to step ⑥. 3. a kind of parallel hybrid clustering method for candidate body signal mining in pulsar search as claimed in claim 2, wherein the grouping strategy based on sliding window in step (2) is to carry out grouping method to data set: according to data The structure maximizes the accurate screening of candidates, and uses the sliding window concept to divide the data; first, the window size is defined (Batchsize=1160), and the data set to be detected is divided into L blocks (the amount of data in the last block is not enough, you can choose the first one The data of the block is filled); set the size of the sliding window w=2, the first round starts from the 1st and 2nd blocks, and the sliding window advances 1 bit in each round, pointing to the corresponding data block; the last round points to the last block In combination with the first block, a total of L rounds of segmentation need to be performed; it is planned to select a set of 1600 relatively complete types of pulsar candidate feature data from real samples as samples, and each round will be added to the data corresponding to the sliding window The data block to be detected is formed, so the data set is divided into L parallel data blocks to be detected; at present, there is a basic assumption in clustering, that is, the examples in the same cluster are more likely to have the same label; therefore , the decision boundary is set according to the dense or sparse areas of various data distributions, so as to determine the pulsar data distribution area, and to divide the area of pulsar signals and non-pulsar interference signals; by calculating the distribution density of pulsar samples in each cluster, Statistical similarity, select clusters with a pulsar sample occupancy greater than 50% to enter the pulsar candidate list; the noise point list excluded in step 3 in the cluster analysis method may lead to the discovery of new phenomena. 4. A parallel hybrid clustering method for candidate body signal mining in pulsar search as claimed in claim 1 or 2, wherein in step (3), the data block parallelization based on the MapReduce/Spark computing model realizes the clustering. The class method is: for large-scale pulsar data processing, according to the Sun-Ni theorem, it is very necessary to study the parallel implementation of the clustering algorithm in the MapReduce computing model; on the one hand, it can improve the accuracy of the clustering results. On the other hand, the number of data comparisons can be reduced; a function G(p) is introduced in the Sun-Ni theorem to represent the increase in workload when the storage capacity is limited; the law proposes to satisfy the time specified by the fixed time speedup ratio Under the premise of limitations and when there is enough memory space, scaling the problem can effectively utilize the memory space; first, the data is divided into L data blocks (Block(1),..., Block(L)) and execute in parallel; in the next step, the Map1 and Reduce1 functions complete the density calculation of the data points in each Block(i) (1≤i≤L) and the selection of the initial cluster centers (needs It is explained that the <key, value> input of the Map stage: key is the row number, value is a list of the values of each dimension of the current sample; the output of the Reduce stage: key.id is the initial cluster center); finally, Map2 and Reduce2 The function iteratively completes the calculation of the distance from each data point in Block(i) to the cluster centers (cluster centers(i)) and re-labels the cluster category to which it belongs, and the new cluster center calculated by the Reduce 2 function is the next round. Prepare for the clustering task; compare the distance between the cluster center of the current round and the corresponding cluster center of the previous round, if the change is less than the given threshold, the operation will end; otherwise, the new cluster center will be used as the clustering center of the next round; After clustering, pulsar clusters and abnormal noise points are extracted; Spark, as a general computing engine for large-scale data processing, has a similar computing process to MapReduce.

Images