1. Introduction

Evaluation of the groundwater resources is a critical task, which needs quantifying groundwater by defining the boundary of the aquifers under study. Usually this task can be conducted by geophysical tools and ground penetration radar technology, which are time consuming and relatively expensive. The location of ground water wells is an indication of groundwater presence in the aquifer. These locations can be used to delineate roughly the boundary of the aquifer and grouping the wells with similar spatial (geographic) characteristics as one aquifer unit. Cluster analysis is usually used for grouping the similar homogenous features (meaningful subclasses) as one discrete group (cluster) without any prior knowledge [1].

Huge number of cluster algorithms are developed in the last decades and they can be categorized into several main groups, including hierarchical, fuzzy, center-based, search-based, graph-based, grid-based, density-based, model-based, subspace clustering approaches, etc. In this study, density-based clustering approach is selected, which is highly efficient algorithm that can detect clusters with any arbitrary irregular shape and size with various densities in data set that contains noise or outlier [2, 3]. Here, data features (objects) are separated based on their density regions, connectivity and boundary.

Several density-based clustering algorithms are available and some of them are used for spatial data, these are considered as the typical (standard) algorithms for density-based clustering, which are called Density Based Spatial Clustering of Applications with Noise (DBSCAN). It is developed by Ester et al. [4]. DBSCAN clustering can be divided into several methods including partitioning based DBSCAN, grid-based DBSCAN, hierarchical DBSCAN, Detection Based DBSCAN, Incremental DBSCAN, spatial–temporal DBSCAN clustering methodologies [5].

In this study, three density-based clustering algorithms are used, which are Density Based Spatial Clustering of Applications with Noise (DBSCAN), hierarchical Density Based Spatial Clustering of Applications with Noise (HDBSCAN) developed by Campello et al. [6], and Ordering points to identify the clustering structure (OPTICS) by Ankerst et al. [7]. These three algorithms are best suited for discovering clusters in spatial spaces with noise [8]. Their advantages include that they do not require the user to specify the number of clusters, and they can find any shape of clusters, also these methods can identify the noise and outliers in the data, while their disadvantages are that these methods are sensitive to the choice of input parameters. These methodologies are applied for clustering a set of groundwater wells in the Madinah city.

2. Study Area and Data

The selected region is the Madinah city, located in the western Kingdom of Saudi Arabia (KSA), covering an area of 522 km². It lies geographically between longitudes 39.45° and 39.71°E and latitudes 24.34° and 24.58°N. The geology of study area consists mainly of three parts; lava plateaus (harrats), alluvial deposits and rock outcrops. The first two parts are the places where the groundwater can be found. The elevation ranges from 570 m above mean sea level (a.m.s.l.) up to 1,100 m a.m.s.l.

Figure 1. Selected study area and well locations

1053 wells are collected from urban populated areas in Madinah (inside the 3rd ring road). The data are collected from groundwater well locations and taken by two methods. For the private farms, the data are taken by the field visit and the location of the wells are determined by GPS with some quantitative information (i.e. well depth, water level, well diameter), this part of the data consists of about 83% of the total collected data. The rest of the data are extracted from houses with high cultivated areas using recent satellite images of the areas. Figure 1 shows the selected study area and the location of the groundwater wells.

3. Methodology

3.1. Assessing Clustering Tendency

Clustering methods divide the data into clusters even the data do not have any clusters. So, clustering tendency assessment is the first step in the cluster analysis, which should be used to evaluate the clustering analysis process validity. Assessing clustering tendency (ATC) measures the feasibility of the cluster analysis and whether a given data is clusterable. Two methods are used in this study; Hopkin's statistics and graphical method, which is visual assessment of cluster tendency (VAT). Hopkins statistics measures the spatial randomness of the dataset and can be computed as follows [9]:

(1)

where is the distance between simulated point and its nearest neighbor, is the distance between data point and its nearest neighbor, and n is sample size. If the value of H is 0.5, this means that the data is uniformly distributed, while if H is less than 0.5 and close to zero, then the data is not uniformly distributed (i.e. contains meaningful clusters) [10, 11]. Small code in R programing language [12] is developed to compute Hopkin's statistics using “clustertend” R package [13].

VAT plot can be constructed by first computing the Euclidean distance among the sample data and then reordering the distances where the similar objects are close to each other, then the VAT plot is developed. The presence of squared shaped dark blocks along the diagonal in a VAT image is an indication that the data set has cluster structures [14]. Small code in R programming language is written to develop the VAT plot using “factroextrac” R package [15].

3.2. Parameter Estimation

Estimating the input parameter for density-based clustering algorithms is still problematic and not yet solved. Density-based clustering algorithms usually require one or more input parameter, which are the minimum number of features (neighbors) per cluster (MinPts) and the search radius distance “ε” [16]. DBSCAN estimates the density by counting the number of points in a fixed-radius neighborhood and considers two points as connected, if they lie within each other’s neighborhood. A point is called “core point” if the neighborhood of radius (ε) contains at least MinPts points [17].

The required input parameter for the three selected algorithms is MinPts, which is the minimum number of features (neighbors) for each cluster. Too small MinPts selection produces high number of clusters and vice versa. The suggested value of MinPts in the literature is around 10 [8]. The value of the search radius distance (ε) input parameter is computed by constructing K-NN distance plot where the value of k is specified by the user and corresponds to MinPts and the best value of the search radius distance (ε) is around the sharp change occurs along the k-distance curve "the knee" [18]. The K-nn distance plot is constructed by developing code in R language using “dbscan” R package [19]. This package is also used to compute the three selected cluster algorithms.

After estimating the two input paramters (MinPts and ε), the three density-based clustering algorithms are used to predict the clusters of groundwater well locations. Finally, the Convex Hulls polygons are plotted for each cluster to delineate the boundary of each groundwater aquifer.

4. Analysis and Results

4.1. Assessing Clustering Tendency

The computed Hopkin's statistics by using "clustertend" R package was found to be 0.12, which is close to zero and far below the threshold 0.5. This means that the well locations dataset is highly clusterable. VAT plot for the well location dataset is developed by using "factroextrac" R package and shown in Figure 2. The squared shaped dark blocks along the diagonal in a VAT image can be seen clearly, which is an indication that the well location data set has cluster structure.

Figure 2. Visual assessment of cluster tendency (VAT) of wells locations

4.2. DBSCAN Clustering

The MinPts parameter is estimated as 10 features per clusters and the K-NN distance plot is developed using “dbscan” R package. Figure 3 shows that the search radius distance (ε) is about 1,000 m.

Figure 3. K-NN Distance plot (using MinPts = 10)

These two parameters are used to compute the DBSCAN, which produced 6 clusters with 89 locations as noises. Figure 4 shows the spatial clusters locations while Table 1 presents the number of features for each cluster.

Figure 4. Groundwater wells clustering using DBSCAN algorithm

Table 1. Distribution of clusters per features using DBSCAN algorithm

4.3. HDBSCAN Clustering

This algorithm needs only one parameter, which is MinPts, and it is set to 10, and hence, HDBSCAN algorithm produced 19 clusters with 313 locations that are considered as noises, which are relatively high. Table 2 presents the number of features for each cluster, while Figure 5 shows the location of these clusters.

Table 2. Distribution of clusters per features using HDBSCAN algorithm

Figure 5. Groundwater wells clustering using HDBSCAN algorithm

4.4. OPTICS Clustering

This algorithm needs two input parameters, namely, MinPts that has different effects than DBSCAN algorithm [19], and Threshold to identify clusters (eps_cl <= eps). OPTICS algorithm produced 7 clusters with 95 locations as noises. Table 3 presents the number of features for each cluster, while Figure 6 shows these clusters location.

Table 3. Distribution of clusters per features using OPTICS algorithm

Figure 6. Groundwater wells clustering using OPTICS algorithm

4.5. Convex Hull Polygons

Each cluster in the three algorithms is delineated using convex Hull polygons, where each polygon is considered to represent one groundwater aquifer. Figure 7 shows the clusters delineation using convex Hull polygons for the three cluster algorithms.

Figure 7. Cluster delineation using convex hull polygons for the three cluster algorithms, (a) DBSCAN, (b) HDBSCAN, (c) OPTICS

5. Conclusions

Groundwater well locations are considered as indicator for aquifer delineation using three spatial clustering approaches, which are DBSCAN, HDBSCAN and OPTICS. The application of these methodologies is based on more than one thousand wells in Madinah, Western KSA. Hopkin's statistics and VAT plot showed that the data has high clusterability (spatial randomness). The DBCAN and OPTICS algorithms produced very reasonable results with 6 and 7 clusters, respectively. It was found that the aquifers are located in the western south, south, eastern south, middle and north of the selected area. The results are expected to be beneficial for water resources planner and decision makers in cases of groundwater related projects.