# Determining the Quality of a Dataset in Clustering Terms
## 2 Materials and Methods
### Methodology
#### 2.2.3 DBSCAN Clustering  
The DBSCAN (density-based spatial clustering of applications with noise) algorithm [17] was designed to extract clusters and noise in a spatial data set. This algorithm has two parameters: \(Eps\) and \(MinPts\), where \(Eps\) defines the distance from a given point \(p\) such that each point \(q\), for which \(d(p,q)<Eps\), belongs to the neighbourhood of point \(p\), denoted by \(N_{Eps}(p)\); \(MinPts\) determines the minimum number of points that must be in the cluster. In a cluster, one can distinguish between two types of point: core points within the cluster and border points at the edge of the cluster. Two concepts are introduced regarding points in the cluster: directly density-reachable and density-reachable. The point \(p\) is directly density-reachable from point \(q\) at a given \(Eps\) and \(MinPts\), if  
1. \(p\in N_{Eps}(q)\);
2. \(|N_{Eps}(q)|\geq MinPts\) (core points condition). The direct density reachability is symmetrical for pairs among core points, but is not symmetrical for mixed pairs of core and border points. The point \(p\) is density-reachable from point \(q\) at a given \(Eps\) and \(MinPts\), if there is a chain of points \(p_{1},p_{2},\ldots,p_{n}\), \(p_{1}=q\) and \(p_{n}=p\), such that \(p_{i}+1\) is directly density-reachable from point \(p_{i}\). This relationship is transitive but not symmetrical. The two border points of a cluster are not within their density reachability. Therefore, the concept of density-connected points is also introduced. The point \(p\) is density-connected to the point \(q\) at a given \(Eps\) and \(MinPts\), if there is a point \(o\) such that both points \(p\) and \(q\) are density-reachable from point \(o\) at a given \(Eps\) and \(MinPts\). Having introduced the above definitions, we can move on to a description of the DBSCAN algorithm itself. To find a cluster, DBSCAN starts from an arbitrary point \(p\) and selects all points within its density reachability at a given \(Eps\) and \(MinPts\). If \(p\) is a core point, this procedure yields a whole cluster. If \(p\) is a border point, then no point is density-reachable from \(p\) and the algorithm proceeds to the next point in the dataset. Since global values for the \(Eps\) and \(MinPts\) parameters are used, the algorithm can merge two clusters into one if they are \"close enough\" to each other. Let the distance between sets \(S_{1}\) and \(S_{2}\) be defined as \(d(S_{1},\ S_{2})=\min d(p,q):\ p\in S_{1}\), \(q\in S_{2}\). Then, two point sets having at least the rarest cluster density will only be separated if the distance between them is greater than \(Eps\). Consequently, it may be necessary to use the DBSCAN algorithm recursively for detected clusters with a higher \(MinPts\) value. However, this is not a disadvantage, as recursion leads to an elegant and efficient underlying algorithm. Moreover, recursive clustering is only necessary under a condition that is easy to verify. The selection of \(Eps\) and \(MinPts\) can be conducted by various methods, including checking the values of metrics available for unsupervised clustering, such as the elbow criterion or the silhouette criterion. The advantage of the DBSCAN algorithm is its applicability to spatial data and not having to determine the number of clusters in advance. A more recent improvement to this algorithm is HDBSCAN [18], which allows clusters of varying density. The algorithm works similarly to the original DBSCAN method but does not have an \(eps\) parameter responsible for the cluster radius. Only the \(min\_cluster\_size\) parameter defining the minimum number of points in a cluster is responsible for the size of the clusters in this method. Both algorithms usually work well on data with noise, although the newer HDBSCAN algorithm is usually more efficient, and different cluster densities often produce a better solution. Since we obtained sufficient results with the DBSCAN method in the experimental part, we concluded that it was not necessary to compare it with the improved version of the algorithm.