# Partition KMNN-DBSCAN Algorithm and Its Application in Extraction of Rail Damage Data

Authors: Yujun Li; Zhi Yang; Shangbin Jiao; Yuxing Li
Journal: Mathematical Problems in Engineering
 (2022)

---

## Abstract

In order to realize intelligent identification of rail damage, this paper studies the extraction method of complete damage ultrasonic B-scan data based on the density-based spatial clustering of applications with noise algorithm (DBSCAN). Aiming at the problem that the traditional DBSCAN algorithm needs to manually set the Eps and Minpts parameters, a KMNN-DBSCAN (K-median nearest neighbor DBSCAN) algorithm is proposed. The algorithm first uses the dataset’s own distribution characteristics to generate a list of Eps and Minpts parameters and then determines the optimal Eps and Minpts through an optimization strategy to achieve complete self-adaptation of the two parameters of Eps and Minpts. In order to further improve the clustering performance of the algorithm, the partition idea is introduced, and the partition KMNN-DBSCAN algorithm is proposed to solve the problem that the clustering results of the DBSCAN algorithm are inconsistent with the actual categories on datasets with uneven density. The experimental results show that the KMNN-DBSCAN algorithm has higher clustering accuracy and silhouette coefficient (SC) for the D037 dataset ultrasound information group (UIG) division; compared with the KMNN-DBSCAN algorithm, the proposed partition KMNN-DBSCAN algorithm has higher clustering accuracy, F-Measure, and SC values. The partition KMNN-DBSCAN algorithm achieves accurate division of all damage UIG on the damaged B-scan data with large density differences, and completes the effective extraction of complete damage data.


---

## Body

## 1. Introduction

Ultrasonic rail flaw detection vehicles are widely used in rail damage detection with the advantages of high detection sensitivity, good directionality, and accurate defect positioning [1]. The ultrasonic rail detection vehicle collects the damage B-scan data based on the multichannel ultrasonic probe, and the technicians classify the damage based on the damage B-scan data [2]. Rail damage identification is mainly divided into two parts: complete damage data extraction and damage identification. Effective extraction of damage data is an important prerequisite for accurate damage identification [3]. Complete damage data extraction refers to dividing the adjacent ultrasonic echo points in physical locations together to form an ultrasonic information group (UIG). UIG is the complete damage data and is the smallest unit of damage identification [4]. The original B-scan data are stored in the form of data stream, which is difficult to extract manually. In this paper, the clustering algorithm is used to complete the damage data extraction.Clustering algorithms are divided into partition-based clustering, hierarchical-based clustering, model-based clustering, and density-based clustering according to different clustering criteria [5]. The partition-based clustering must determine the final classification of the dataset before clustering, and the number of damages in the B-scan data file is uncertain, so the partition-based clustering is not suitable for rail damage classification [6]. The hierarchical-based clustering is only suitable for finding spherical or spherical clusters, while UIG is irregular in shape, so this method is not suitable for UIG division [7]. The model-based clustering algorithm assumes that the input dataset has a potential probability distribution, and the clustering effect will be affected if the assumptions do not hold [8]. However, the distribution of B-scan data is random, so the model-based clustering algorithm is not suitable for UIG division of B-scan data. The density-based clustering algorithm uses density as the clustering criterion and can find clusters of any shape without presetting the number of clustering results. The representative algorithm is DBSCAN (density-based spatial clustering of applications with noise), which can filter out abnormal points as noise while clustering [9]. The DBSCAN algorithm satisfies the requirement that the number of damaged rails in ultrasonic B-scan data is unknown, the damage shape is irregular, and the noise needs to be filtered out. However, the traditional DBSCAN algorithm has two flaws. The first is that the neighborhood radius Eps and the minimum density threshold Minpts need to be manually set, which is prone to clustering failure. The second is that the traditional DBSCAN algorithm has errors when clustering datasets with large density differences. In view of the above two problems, some scholars have improved the DBSCAN algorithm. For example, the literature [10] proposed that the distance value corresponding to the region where the distance distribution curve of the input dataset “steepened” was taken as Eps. This method provides a criterion for determining Eps based on the characteristics of data distribution, which has certain guiding significance for the selection of Eps, but it needs to determine the “steepened” area through manual observation. The literature [11] proposes the AF-DBSCAN algorithm, which uses polynomial fitting to fit the distance curve corresponding to a certain K value in the input dataset, solves the inflection point of the fitted curve, and takes the maximum distance corresponding to the inflection point as the optimal value of Eps. However, the discussion on the selection of K value is lacking in the text. The literature [12] proposes the SA-DBSCAN algorithm, which uses inverse Gaussian fitting to fit the probability distribution curve of the dataset, and takes the distance value corresponding to the peak point of the distribution curve as the value of Eps. Under the same Eps, the noise points are the least when the corresponding Minpts are taken as the optimal value of Minpts. However, the SA-DBSCAN algorithm achieves complete adaptation of the two parameter values, but the algorithm makes assumptions about the distribution of the input dataset and is not applicable to all datasets. The literature [13–15] improves the DBSCAN algorithm based on the idea of grid division to achieve good clustering effect on datasets with uneven density distribution. However, the mesh size setting of the parameter adaptive algorithm based on mesh division lacks theoretical guidance and is difficult to set manually.In view of this, this paper proposes a new parameter adaptive DBSCAN algorithm KMNN-DBSCAN, which automatically determines the optimal clustering parameters based on the distance distribution characteristics of the input dataset, and realizes the fully adaptive selection of Eps and Minpts parameters. After that, the partition idea was introduced to improve the KMNN-DBSCAN algorithm, and the partition KMNN-DBSCAN algorithm was proposed. The partition KMNN-DBSCAN algorithm is proposed to solve the problem of errors in the traditional DBSCAN algorithm when clustering datasets with large density differences, and realizes the effective extraction of complete damage data.


## 2. Algorithm Principle

### 2.1. Principle of DBSCAN Algorithm

The DBSCAN (density-based spatial clustering of applications with noise) algorithm is a clustering algorithm based on high-density connected regions, which can filter out noise points while discovering any cluster. The related concepts of DBSCAN algorithm are as follows:(1)
The Eps neighborhood of element points: for a certain element pointp in a given dataset D, the Eps neighborhood of p refers to the set of all element points in the area with p as the center and Eps as the radius, denoted as Eps(p). Eps(p) expression is as follows:(1)Epsp=q∈D|distancep,q≤Eps,where distance (p, q) is the Euclidean distance between the element point p and the element point q in the dataset D.(2)
Density: DBSCAN defines the number of element points contained in the Eps neighborhood of an element point as the density of the point, and the expression is as follows:(2)Density=NumEpsp.(3)
Core point: if the Eps neighborhood of an element point contains the number of element points greater than or equal to the given minimum density threshold Minpts, the point is called a core point, and the expression is as follows:(3)NumEpsp≥Minpts.(4)
Boundary point: if the number of element points contained in the Eps neighborhood of an element point is less than the given minimum density threshold Minpts, the point is called a boundary point, and the expression is as follows:(4)NumEpsp<Minpts.(5)
Direct density reachability: for any two element pointsp and q in dataset D, if q is in the Eps neighborhood of p, and p is the core point, then point q is said to be directly density reachable from point p.(6)
Density reachable: for a set of element pointsp1, p2,…, pi,…,pn in dataset D, where p = p1, and q = pn. An element point q is said to be density-reachable from point p if it is directly density-reachable for any pi + 1 to pi.(7)
Density connection: for an element pointr in the dataset D, if the element point p and the element point q are both density-reachable from point r, then point q is said to be density-connected from point p.(8)
Cluster (C): for a nonempty subset C of the input dataset, if C meets the following conditions, C is called a cluster.(1)
For any element pointq, there is an element point p belonging to C. If q is density-reachable from p, then q belongs to C.(2)
For any two element points inC, they are density connection.Noise point: the element point that does not belong to any cluster is called noise point, denoted as noise, and the expression is as follows:(5)noise=o∈D|∀i:o∉Ci.The clustering principle of DBSCAN algorithm is the maximum density connected sample set derived from the density reachability relationship [16].


### 2.2. Principle of KMNN-DBSCAN Algorithm

The core of KMNN-DBSCAN is to generate a list of Eps and Minpts parameter pairs based on the distance distribution characteristics of the dataset. The parameters are optimized based on the Eps and Minpts parameter lists, and the optimal parameter pair is obtained, so as to realize the complete adaptation of the Eps and Minpts parameters of DBSCAN. The algorithm flow of KMNN-DBSCAN is shown in Figure1.Figure 1
KMNN-DBSCAN algorithm flow.The steps of the KMNN-DBSCAN algorithm are as follows:Step 1. Generate a list of Eps parameter values.The Eps parameter list is generated by the K-median nearest neighbor (KMNN) algorithm. The main principle of this algorithm is to first calculate the K-nearest neighbor distance matrix of the input dataset and then find the median of the K-nearest neighbor distances of all element points, and constitute the K-median nearest neighbor set. Take the K-median nearest neighbor set as the Eps parameter list, and the specific steps are as follows:(1)
Calculate the distance distribution matrix Distn × n(6)Distn×n=disti,j|1≤i≤n,1≤j≤n,wheren is the number of element points in the input dataset D, dist(i, j) is the Euclidean distance between element point i and element point j, and Distn × n is the distance matrix.(2)
Calculate the K-nearest neighbor distance matrix KNNn×n(7)KNNn×n=sortDistn×n.Arrange each row of the distance distribution matrix in ascending order to obtain the K-nearest neighbor distance matrix KNNn × n. The ith row of KNNn × n represents the distance between the element points closest to the ith element point 1∼n, and the K-th column (K = 1,2,...,n) represents the K-nearest neighbor distance corresponding to all element points. Where the first column is the distance from the element point to itself, the first column of KNNn × n is all zero.(3)
K-median nearest neighbor (KMNN) distance set KMNN1 ×nFind the median of each column of KMNN1 ×n, and all the medians form the K-median nearest neighbor distance set KMNN1 ×n. Take the K-median nearest neighbor distance set KMNN1 ×n as a list of Eps parameter values, where the Eps value corresponds to the K.Step 2. Generate a list of Minpts parameter values.Generates a list of Minpts parameter values using the median method and a given list of Eps parameter values. For the current Eps parameter list, the number of element points contained in the Eps neighborhood of all element points under different Eps is obtained in turn. The median of the number of element points contained in the Eps neighborhood of all element points is taken as the Minpts value corresponding to the current Eps value. The Minpts values corresponding to all Eps values are obtained to form the Minpts parameter list, and the Minpts values correspond to the Eps values. Different K corresponds to different Eps, Minpts parameter value pairs.Step 3. Eps and Minpts parameter pair optimization.The Eps and Minpts parameter value pairs corresponding to differentK values are selected in turn as the clustering parameters of the DBSCAN algorithm, and the number of clustering results under the Eps and Minpts parameter values corresponding to different K values is obtained. This paper considers that when the number of clustering results does not change for three consecutive times, the number of clustering results is stable, and the current number of clustering results is recorded as the optimal number of clustering results. After the number of clustering results is stable, we continue the above operations until the number of clustering results changes. The interval from the optimal number of clustering results to the change of the number of clustering results is called the stable area. For the stable area corresponding to all the Eps and Minpts parameter value pairs, the expected EPS¯ and Minpts¯ are obtained respectively, and EPS¯ and Minpts¯ are taken as the optimal Eps and Minpts value.


### 2.3. Partition KMNN-DBSCAN Algorithm Principle

In order to solve the problem that the traditional DBSCAN algorithm has errors in the clustering results on datasets with large density differences, the idea of partitioning is introduced to improve the KMNN-DBSCAN algorithm [17], and the partition KMNN-DBSCAN algorithm is proposed. The implementation steps of the partition KMNN-DBSCAN algorithm are as follows:Step 1. Partition the input dataset.Project the element points of the input dataset on theX-axis and the Y-axis, respectively, to obtain the distribution of the input dataset on the X-axis and the Y-axis. The partition points are selected at the places where the density is the most sparse among different density centers, and sub-datasets with different densities are obtained.Step 2. Perform cluster analysis on sub-datasets separately.KMNN-DBSCAN is used to adapt the parameters to the sub-datasets, respectively, and the local optimal parameters are used to cluster the sub-datasets to obtain the clustering results of the sub-datasets.Step 3. Merge local clustering results.Merge the clustering results of the sub-datasets and finally get the clustering results of the original datasets.The flow chart of the partition KMNN-DBSCAN algorithm is shown in Figure2.Figure 2
Flowchart of the partitioned KMNN-DBSCAN algorithm.


## 2.1. Principle of DBSCAN Algorithm

The DBSCAN (density-based spatial clustering of applications with noise) algorithm is a clustering algorithm based on high-density connected regions, which can filter out noise points while discovering any cluster. The related concepts of DBSCAN algorithm are as follows:(1)
The Eps neighborhood of element points: for a certain element pointp in a given dataset D, the Eps neighborhood of p refers to the set of all element points in the area with p as the center and Eps as the radius, denoted as Eps(p). Eps(p) expression is as follows:(1)Epsp=q∈D|distancep,q≤Eps,where distance (p, q) is the Euclidean distance between the element point p and the element point q in the dataset D.(2)
Density: DBSCAN defines the number of element points contained in the Eps neighborhood of an element point as the density of the point, and the expression is as follows:(2)Density=NumEpsp.(3)
Core point: if the Eps neighborhood of an element point contains the number of element points greater than or equal to the given minimum density threshold Minpts, the point is called a core point, and the expression is as follows:(3)NumEpsp≥Minpts.(4)
Boundary point: if the number of element points contained in the Eps neighborhood of an element point is less than the given minimum density threshold Minpts, the point is called a boundary point, and the expression is as follows:(4)NumEpsp<Minpts.(5)
Direct density reachability: for any two element pointsp and q in dataset D, if q is in the Eps neighborhood of p, and p is the core point, then point q is said to be directly density reachable from point p.(6)
Density reachable: for a set of element pointsp1, p2,…, pi,…,pn in dataset D, where p = p1, and q = pn. An element point q is said to be density-reachable from point p if it is directly density-reachable for any pi + 1 to pi.(7)
Density connection: for an element pointr in the dataset D, if the element point p and the element point q are both density-reachable from point r, then point q is said to be density-connected from point p.(8)
Cluster (C): for a nonempty subset C of the input dataset, if C meets the following conditions, C is called a cluster.(1)
For any element pointq, there is an element point p belonging to C. If q is density-reachable from p, then q belongs to C.(2)
For any two element points inC, they are density connection.Noise point: the element point that does not belong to any cluster is called noise point, denoted as noise, and the expression is as follows:(5)noise=o∈D|∀i:o∉Ci.The clustering principle of DBSCAN algorithm is the maximum density connected sample set derived from the density reachability relationship [16].


## 2.2. Principle of KMNN-DBSCAN Algorithm

The core of KMNN-DBSCAN is to generate a list of Eps and Minpts parameter pairs based on the distance distribution characteristics of the dataset. The parameters are optimized based on the Eps and Minpts parameter lists, and the optimal parameter pair is obtained, so as to realize the complete adaptation of the Eps and Minpts parameters of DBSCAN. The algorithm flow of KMNN-DBSCAN is shown in Figure1.Figure 1
KMNN-DBSCAN algorithm flow.The steps of the KMNN-DBSCAN algorithm are as follows:Step 1. Generate a list of Eps parameter values.The Eps parameter list is generated by the K-median nearest neighbor (KMNN) algorithm. The main principle of this algorithm is to first calculate the K-nearest neighbor distance matrix of the input dataset and then find the median of the K-nearest neighbor distances of all element points, and constitute the K-median nearest neighbor set. Take the K-median nearest neighbor set as the Eps parameter list, and the specific steps are as follows:(1)
Calculate the distance distribution matrix Distn × n(6)Distn×n=disti,j|1≤i≤n,1≤j≤n,wheren is the number of element points in the input dataset D, dist(i, j) is the Euclidean distance between element point i and element point j, and Distn × n is the distance matrix.(2)
Calculate the K-nearest neighbor distance matrix KNNn×n(7)KNNn×n=sortDistn×n.Arrange each row of the distance distribution matrix in ascending order to obtain the K-nearest neighbor distance matrix KNNn × n. The ith row of KNNn × n represents the distance between the element points closest to the ith element point 1∼n, and the K-th column (K = 1,2,...,n) represents the K-nearest neighbor distance corresponding to all element points. Where the first column is the distance from the element point to itself, the first column of KNNn × n is all zero.(3)
K-median nearest neighbor (KMNN) distance set KMNN1 ×nFind the median of each column of KMNN1 ×n, and all the medians form the K-median nearest neighbor distance set KMNN1 ×n. Take the K-median nearest neighbor distance set KMNN1 ×n as a list of Eps parameter values, where the Eps value corresponds to the K.Step 2. Generate a list of Minpts parameter values.Generates a list of Minpts parameter values using the median method and a given list of Eps parameter values. For the current Eps parameter list, the number of element points contained in the Eps neighborhood of all element points under different Eps is obtained in turn. The median of the number of element points contained in the Eps neighborhood of all element points is taken as the Minpts value corresponding to the current Eps value. The Minpts values corresponding to all Eps values are obtained to form the Minpts parameter list, and the Minpts values correspond to the Eps values. Different K corresponds to different Eps, Minpts parameter value pairs.Step 3. Eps and Minpts parameter pair optimization.The Eps and Minpts parameter value pairs corresponding to differentK values are selected in turn as the clustering parameters of the DBSCAN algorithm, and the number of clustering results under the Eps and Minpts parameter values corresponding to different K values is obtained. This paper considers that when the number of clustering results does not change for three consecutive times, the number of clustering results is stable, and the current number of clustering results is recorded as the optimal number of clustering results. After the number of clustering results is stable, we continue the above operations until the number of clustering results changes. The interval from the optimal number of clustering results to the change of the number of clustering results is called the stable area. For the stable area corresponding to all the Eps and Minpts parameter value pairs, the expected EPS¯ and Minpts¯ are obtained respectively, and EPS¯ and Minpts¯ are taken as the optimal Eps and Minpts value.


## 2.3. Partition KMNN-DBSCAN Algorithm Principle

In order to solve the problem that the traditional DBSCAN algorithm has errors in the clustering results on datasets with large density differences, the idea of partitioning is introduced to improve the KMNN-DBSCAN algorithm [17], and the partition KMNN-DBSCAN algorithm is proposed. The implementation steps of the partition KMNN-DBSCAN algorithm are as follows:Step 1. Partition the input dataset.Project the element points of the input dataset on theX-axis and the Y-axis, respectively, to obtain the distribution of the input dataset on the X-axis and the Y-axis. The partition points are selected at the places where the density is the most sparse among different density centers, and sub-datasets with different densities are obtained.Step 2. Perform cluster analysis on sub-datasets separately.KMNN-DBSCAN is used to adapt the parameters to the sub-datasets, respectively, and the local optimal parameters are used to cluster the sub-datasets to obtain the clustering results of the sub-datasets.Step 3. Merge local clustering results.Merge the clustering results of the sub-datasets and finally get the clustering results of the original datasets.The flow chart of the partition KMNN-DBSCAN algorithm is shown in Figure2.Figure 2
Flowchart of the partitioned KMNN-DBSCAN algorithm.


## 3. Ultrasound Information Group (UIG) Division Experiment

As shown in Figure3, the complete damage data extraction for the original B-scan data includes the division of UIC and UIG, and UIG is the complete damage data.Figure 3
Complete damage data extraction process.


### 3.1. Ultrasound Information Combination (UIC) Division

Ultrasonic steel rail flaw detection vehicle adopts ultrasonic probe wheel as sensor. The ultrasonic probe wheel has built-in ultrasonic sensors with four angles: 0°, 37°, straight 70°, and oblique 70°. Different angle sensors are used to detect different areas of the rail, and the combination of different ultrasonic sensor channels is used to detect different types of damage. If UIC is not divided, it will affect the complete data extraction of damage [18].Figure4 shows the detection range of ultrasonic sensors with different angles. The ultrasonic propagation range of the 0° probe is from the rail surface to the rail bottom, and the detection range is the projection area of the rail waist. The 0° probe is usually used to detect the level of crack from the rail surface to the rail bottom. The detection range of the 37° probe is from the rail surface of the rail waist projection area to the lower part of the rail waist. The 37° probe is usually used to detect the crack of the screw hole of the rail waist. The detection range of the straight 70° probe is the central area of the rail head, which is generally used to detect nuclear damage in the middle of the rail head. The detection range of the oblique 70° probe is the area on both sides of the rail head and is generally used to detect the lateral holes on the inner and outer sides of the rail head.Figure 4
Detection range of ultrasonic sensors at different angles.As shown in Figure4, there are related cases for sensors with different angles (such as 0° and 37° ultrasonic sensors), and there are also unrelated channels (such as 37° and oblique 70° ultrasonic sensors). If no distinction is made, the division of subsequent UIG will be affected, thereby affecting the effect of injury judgment. Table 1 shows the ultrasonic sensor combinations corresponding to seven common rail damages. From Table 1, it can be seen that different ultrasonic sensor combinations are used to detect different damages.Table 1
Ultrasonic sensor combination corresponding to common rail damage.
Damage locationDamage typeCorresponding ultrasonic sensor combinationRail surfaceOblique downward defect37° probeRail headInner transverse holeSlanted 70° probeRail headCentral nuclear injuryStraight 70° probeRail headOuter lateral holeSlanted 70° probeRail waistIntact screw hole0°, 37° probeRail waistHorizontal cracks in screw holes0°, 37° probeRail waistOblique crack in screw hole0°, 37° probeRail bottomCross-hole0° probeIn this paper, the raw B-scan data are divided into UIC according to the ultrasonic sensor channel and position correlation, combined with the combination of ultrasonic sensor channels corresponding to each damage type. The UIC division results are shown in Figure5.Figure 5
B-scan data UIC division.


### 3.2. KMNN-DBSCAN Algorithm Applied to Ultrasonic Information Group (UIG) Division

In order to verify the effectiveness of the KMNN-DBSCAN algorithm in this paper, the KMNN-DBSCAN algorithm is applied to the D037 UIC dataset for UIG division. The division results of the KMNN-DBSCAN algorithm are compared with those of the SA-DBSCAN and AF-DBSCAN algorithms. D037 is the 0° and 37° channel UIC data of the damage B-scan data collected in an experiment. The dataset contains 830 two-dimensional ultrasonic echo data. Figure 6 shows the corresponding B-scan of the D037 dataset. The D037 dataset contains 0 damaged UIGs; that is, the D037 dataset contains 10 clusters.Figure 6
D037 dataset corresponds to B-scan.Figure7(a)–7(c) are the UIG division results of the D037 dataset by the SA-DBSCAN algorithm, the AF-DBSCAN algorithm, and the KMNN-DBSCAN algorithm. All elements with the same point type form a cluster class, elements with different point types represent different clusters, and noise points are points that do not belong to any cluster.Figure 7
UIG division results of different parameter adaptive algorithms. (a) SA-DBSCAN. (b) AF-DBSCAN. (c) KMNN-DBSCAN.
(a)(b)(c)The UIG division results and evaluation indexes of different clustering algorithms are shown in Table2.Table 2
UIG division results and evaluation indexes of different clustering algorithms.
Algorithm nameEpsMinptsActual number of classesNumber of clustering resultsNumber of correct clustersF-MeasureSCAF-DBSCAN23.430.110760.9050.442SA-DBSCAN16.512.0103110.468KMNN-DBSCAN22.942.710770.9570.855Among them, F-Measure reflects the ability of the algorithm to identify valid data points, and the larger the F value, the stronger the ability of the algorithm to identify valid data points [19]. The silhouette coefficient comprehensively reflects the compactness within the class and the separation between the classes. The value range of SC is [−1, 1]. Within the value range, the larger the value of SC, the better the clustering result [20].Judging from the correct number of clusters in Table2, the number of clustering results of the KMNN-DBSCAN algorithm is the closest to the real number of clusters in the D037 dataset, and the number of correct clusters is also the most, indicating that the KMNN-DBSCAN algorithm has the highest UIG division accuracy. From the F-Measure in Table 2, the F values of the AF-DBSCAN algorithm, the SA-DBSCAN algorithm, and the KMNN-DBSCAN algorithm are all above 0.9, indicating that the three algorithms have a strong ability to identify valid element points. According to the SC index in Table 2, the SC value of the UIG division result of the KMNN-DBSCAN algorithm is significantly higher than that of the comparison algorithm, indicating that the clusters divided by KMNN-DBSCAN have more compact elements within the cluster and more dispersed between different clusters, which shows that the UIG division of the KMNN-DBSCAN algorithm is more reasonable.By comparing the UIG division results of the KMNN-DBSCAN algorithm and the comparison algorithm in terms of the number of clustering results, the number of correct clusters, F-Measure, and SC indicators, it can be seen that the KMNN-DBSCAN algorithm proposed in this paper not only has strong identification efficiency. The ability of element points, and the accuracy and rationality of ultrasound information group division are better.


### 3.3. Partition KMNN-DBSCAN Algorithm Applied to Ultrasound Information Group (UIG) Division

The D037 dataset contains a total of 10 rail damage UIG. The KMNN-DBSCAN algorithm divides the D037 dataset into 7 clusters and fails to correctly divide all the ultrasound information clusters. This is because the densities of the UIG ⑧∼⑩ and the UIG ①∼⑦ in the D037 dataset are quite different. The KMNN-DBSCAN algorithm uses the same clustering parameters to process the datasets with large density differences, resulting in the UIG ⑧∼⑩ is divided into noise. To solve this problem, this paper proposes a partition KMNN-DBSCAN algorithm. In order to verify the effectiveness of the partition KMNN-DBSCAN algorithm, the algorithm was used in the D037 UIC dataset to divide ultrasound information groups, and the specific process is as follows:(1)
Partitioning the D037 dataset based on the density distribution characteristics of the dataset.The D037 data points are projected on the X-axis and the Y-axis, respectively, and the spatial distribution characteristics of the data element points of the D037 dataset on the X-axis and the Y-axis are shown in Figure 8.As shown in Figure8, the density of the D037 dataset is continuous on the X-axis, and there are two dense regions on the Y-axis, and the two densities are quite different. Where the density is the most sparse between the two density centers, D037 is divided into two sub-datasets of D0371 and D0372.(2)
The D0371 and D0372 datasets are divided into UIG by KMNN-DBSCAN.Figure9 shows the results of KMNN-DBSCAN dividing the D0371 and D0372 datasets by UIG.It can be seen from Figure9 that the KMNN-DBSCAN algorithm is used to adapt the parameters of the two sub-datasets D0371 and D0372, respectively, and the local optimal parameters are used for the division of the local UIG. Both sub-datasets realize the UIG accurate division.(3)
Merge the results of sub-dataset UIG division.Figure 8
Data distribution characteristics of D037 dataset.Figure 9
Sub-dataset KMNN-DBSCAN UIG division results. (a) D0371 dataset KMNN-DBSCAN UIG division results. (b) D0372 dataset KMNN-DBSCAN UIG division results.
(a)(b)After completing the local clustering of each sub-dataset, all local clustering results should be merged to obtain the overall clustering result of the original dataset. By combining the division results of the UIG of the above two sub-datasets D0371 and D0372, the result of dividing the UIG of the original input dataset D037 by partition KMNN-DBSCAN is shown in Figure 10.Figure 10
Partition KMNN-DBSCAN algorithm for UIG division of D037 dataset.Table3 shows the comparison results of the UIG division of D037 by partition KMNN-DBSCAN and KMNN-DBSCAN. Judging from the number of clustering results and the number of correct clusters in Table 3, the partitioned KMNN-DBSCAN algorithm divides all UIGs of the D037 dataset correctly. From the F-Measure in Table 3, the F-Measure value of the partitioned KMNN-DBSCAN algorithm is 1, which indicates that the partitioned KMNN-DBSCAN algorithm has identified all valid data points. From the SC index in Table 3, the SC value of the UIG division result of the partitioned KMNN-DBSCAN algorithm is significantly higher than that of the KMNN-DBSCAN algorithm. This shows that the clusters divided by the partitioned KMNN-DBSCAN have more compact elements in the cluster and more dispersed between different clusters; that is, the partitioned KMNN-DBSCAN algorithm UIG division is more reasonable.Table 3
Division results and evaluation indexes of UIG by partition KMNN-DBSCAN algorithm and KMNN-DBSCAN algorithm.
Algorithm nameActual number of classesNumber of clustering resultsNumber of correct clustersF-MeasureSCKMNN-DBSCAN10770.9570.855Partition KMNN-DBSCAN10101010.961


## 3.1. Ultrasound Information Combination (UIC) Division

Ultrasonic steel rail flaw detection vehicle adopts ultrasonic probe wheel as sensor. The ultrasonic probe wheel has built-in ultrasonic sensors with four angles: 0°, 37°, straight 70°, and oblique 70°. Different angle sensors are used to detect different areas of the rail, and the combination of different ultrasonic sensor channels is used to detect different types of damage. If UIC is not divided, it will affect the complete data extraction of damage [18].Figure4 shows the detection range of ultrasonic sensors with different angles. The ultrasonic propagation range of the 0° probe is from the rail surface to the rail bottom, and the detection range is the projection area of the rail waist. The 0° probe is usually used to detect the level of crack from the rail surface to the rail bottom. The detection range of the 37° probe is from the rail surface of the rail waist projection area to the lower part of the rail waist. The 37° probe is usually used to detect the crack of the screw hole of the rail waist. The detection range of the straight 70° probe is the central area of the rail head, which is generally used to detect nuclear damage in the middle of the rail head. The detection range of the oblique 70° probe is the area on both sides of the rail head and is generally used to detect the lateral holes on the inner and outer sides of the rail head.Figure 4
Detection range of ultrasonic sensors at different angles.As shown in Figure4, there are related cases for sensors with different angles (such as 0° and 37° ultrasonic sensors), and there are also unrelated channels (such as 37° and oblique 70° ultrasonic sensors). If no distinction is made, the division of subsequent UIG will be affected, thereby affecting the effect of injury judgment. Table 1 shows the ultrasonic sensor combinations corresponding to seven common rail damages. From Table 1, it can be seen that different ultrasonic sensor combinations are used to detect different damages.Table 1
Ultrasonic sensor combination corresponding to common rail damage.
Damage locationDamage typeCorresponding ultrasonic sensor combinationRail surfaceOblique downward defect37° probeRail headInner transverse holeSlanted 70° probeRail headCentral nuclear injuryStraight 70° probeRail headOuter lateral holeSlanted 70° probeRail waistIntact screw hole0°, 37° probeRail waistHorizontal cracks in screw holes0°, 37° probeRail waistOblique crack in screw hole0°, 37° probeRail bottomCross-hole0° probeIn this paper, the raw B-scan data are divided into UIC according to the ultrasonic sensor channel and position correlation, combined with the combination of ultrasonic sensor channels corresponding to each damage type. The UIC division results are shown in Figure5.Figure 5
B-scan data UIC division.


## 3.2. KMNN-DBSCAN Algorithm Applied to Ultrasonic Information Group (UIG) Division

In order to verify the effectiveness of the KMNN-DBSCAN algorithm in this paper, the KMNN-DBSCAN algorithm is applied to the D037 UIC dataset for UIG division. The division results of the KMNN-DBSCAN algorithm are compared with those of the SA-DBSCAN and AF-DBSCAN algorithms. D037 is the 0° and 37° channel UIC data of the damage B-scan data collected in an experiment. The dataset contains 830 two-dimensional ultrasonic echo data. Figure 6 shows the corresponding B-scan of the D037 dataset. The D037 dataset contains 0 damaged UIGs; that is, the D037 dataset contains 10 clusters.Figure 6
D037 dataset corresponds to B-scan.Figure7(a)–7(c) are the UIG division results of the D037 dataset by the SA-DBSCAN algorithm, the AF-DBSCAN algorithm, and the KMNN-DBSCAN algorithm. All elements with the same point type form a cluster class, elements with different point types represent different clusters, and noise points are points that do not belong to any cluster.Figure 7
UIG division results of different parameter adaptive algorithms. (a) SA-DBSCAN. (b) AF-DBSCAN. (c) KMNN-DBSCAN.
(a)(b)(c)The UIG division results and evaluation indexes of different clustering algorithms are shown in Table2.Table 2
UIG division results and evaluation indexes of different clustering algorithms.
Algorithm nameEpsMinptsActual number of classesNumber of clustering resultsNumber of correct clustersF-MeasureSCAF-DBSCAN23.430.110760.9050.442SA-DBSCAN16.512.0103110.468KMNN-DBSCAN22.942.710770.9570.855Among them, F-Measure reflects the ability of the algorithm to identify valid data points, and the larger the F value, the stronger the ability of the algorithm to identify valid data points [19]. The silhouette coefficient comprehensively reflects the compactness within the class and the separation between the classes. The value range of SC is [−1, 1]. Within the value range, the larger the value of SC, the better the clustering result [20].Judging from the correct number of clusters in Table2, the number of clustering results of the KMNN-DBSCAN algorithm is the closest to the real number of clusters in the D037 dataset, and the number of correct clusters is also the most, indicating that the KMNN-DBSCAN algorithm has the highest UIG division accuracy. From the F-Measure in Table 2, the F values of the AF-DBSCAN algorithm, the SA-DBSCAN algorithm, and the KMNN-DBSCAN algorithm are all above 0.9, indicating that the three algorithms have a strong ability to identify valid element points. According to the SC index in Table 2, the SC value of the UIG division result of the KMNN-DBSCAN algorithm is significantly higher than that of the comparison algorithm, indicating that the clusters divided by KMNN-DBSCAN have more compact elements within the cluster and more dispersed between different clusters, which shows that the UIG division of the KMNN-DBSCAN algorithm is more reasonable.By comparing the UIG division results of the KMNN-DBSCAN algorithm and the comparison algorithm in terms of the number of clustering results, the number of correct clusters, F-Measure, and SC indicators, it can be seen that the KMNN-DBSCAN algorithm proposed in this paper not only has strong identification efficiency. The ability of element points, and the accuracy and rationality of ultrasound information group division are better.


## 3.3. Partition KMNN-DBSCAN Algorithm Applied to Ultrasound Information Group (UIG) Division

The D037 dataset contains a total of 10 rail damage UIG. The KMNN-DBSCAN algorithm divides the D037 dataset into 7 clusters and fails to correctly divide all the ultrasound information clusters. This is because the densities of the UIG ⑧∼⑩ and the UIG ①∼⑦ in the D037 dataset are quite different. The KMNN-DBSCAN algorithm uses the same clustering parameters to process the datasets with large density differences, resulting in the UIG ⑧∼⑩ is divided into noise. To solve this problem, this paper proposes a partition KMNN-DBSCAN algorithm. In order to verify the effectiveness of the partition KMNN-DBSCAN algorithm, the algorithm was used in the D037 UIC dataset to divide ultrasound information groups, and the specific process is as follows:(1)
Partitioning the D037 dataset based on the density distribution characteristics of the dataset.The D037 data points are projected on the X-axis and the Y-axis, respectively, and the spatial distribution characteristics of the data element points of the D037 dataset on the X-axis and the Y-axis are shown in Figure 8.As shown in Figure8, the density of the D037 dataset is continuous on the X-axis, and there are two dense regions on the Y-axis, and the two densities are quite different. Where the density is the most sparse between the two density centers, D037 is divided into two sub-datasets of D0371 and D0372.(2)
The D0371 and D0372 datasets are divided into UIG by KMNN-DBSCAN.Figure9 shows the results of KMNN-DBSCAN dividing the D0371 and D0372 datasets by UIG.It can be seen from Figure9 that the KMNN-DBSCAN algorithm is used to adapt the parameters of the two sub-datasets D0371 and D0372, respectively, and the local optimal parameters are used for the division of the local UIG. Both sub-datasets realize the UIG accurate division.(3)
Merge the results of sub-dataset UIG division.Figure 8
Data distribution characteristics of D037 dataset.Figure 9
Sub-dataset KMNN-DBSCAN UIG division results. (a) D0371 dataset KMNN-DBSCAN UIG division results. (b) D0372 dataset KMNN-DBSCAN UIG division results.
(a)(b)After completing the local clustering of each sub-dataset, all local clustering results should be merged to obtain the overall clustering result of the original dataset. By combining the division results of the UIG of the above two sub-datasets D0371 and D0372, the result of dividing the UIG of the original input dataset D037 by partition KMNN-DBSCAN is shown in Figure 10.Figure 10
Partition KMNN-DBSCAN algorithm for UIG division of D037 dataset.Table3 shows the comparison results of the UIG division of D037 by partition KMNN-DBSCAN and KMNN-DBSCAN. Judging from the number of clustering results and the number of correct clusters in Table 3, the partitioned KMNN-DBSCAN algorithm divides all UIGs of the D037 dataset correctly. From the F-Measure in Table 3, the F-Measure value of the partitioned KMNN-DBSCAN algorithm is 1, which indicates that the partitioned KMNN-DBSCAN algorithm has identified all valid data points. From the SC index in Table 3, the SC value of the UIG division result of the partitioned KMNN-DBSCAN algorithm is significantly higher than that of the KMNN-DBSCAN algorithm. This shows that the clusters divided by the partitioned KMNN-DBSCAN have more compact elements in the cluster and more dispersed between different clusters; that is, the partitioned KMNN-DBSCAN algorithm UIG division is more reasonable.Table 3
Division results and evaluation indexes of UIG by partition KMNN-DBSCAN algorithm and KMNN-DBSCAN algorithm.
Algorithm nameActual number of classesNumber of clustering resultsNumber of correct clustersF-MeasureSCKMNN-DBSCAN10770.9570.855Partition KMNN-DBSCAN10101010.961


## 4. Conclusion

In this paper, according to the characteristics of damage B-scan data, the density-based DBSCAN clustering algorithm is selected to study the extraction method of complete damage B-scan data. The main conclusions are as follows:(1)
A parameter adaptive DBSCAN algorithm KMNN-DBSCAN is proposed, which solves the defect that the traditional DBSCAN algorithm needs to manually set the clustering parameters. KMNN-DBSCAN algorithm generates the list of Eps and Minpts parameter values according to the distance distribution characteristics of the input dataset, determines the optimal Eps and Minpts according to the relationship between the clustering results of the algorithm and theK under different parameter values, and realizes the complete adaptation of the two parameter values of Eps and Minpts.(2)
The KMNN-DBSCAN algorithm is applied to the D037 dataset for UIG partitioning. The experimental results show that, compared with SA-DBSCAN algorithm and AF-DBSCAN algorithm, KMNN-DBSCAN algorithm has stronger ability to identify valid element points and performs better in the accuracy and rationality of UIG division.(3)
The proposed partition KMNN-DBSCAN algorithm solves the problem that the traditional DBSCAN algorithm has errors in the clustering of datasets with uneven density distribution. The partition KMNN-DBSCAN algorithm is applied to the D037 dataset for UIG division. The experimental results show that the partition KMNN-DBSCAN algorithm can effectively realize the accurate UIG division, further improve the correctness and rationality of UIG division, and realize the effective extraction of complete damage data.According to the principle of the partition KMNN-DBSCAN algorithm, the time complexity of the algorithm in this paper is relatively high. Therefore, how to effectively reduce the time complexity of the algorithm is the focus of our next work.



---

*Source: 4699573-2022-07-13.xml*