# DPS Clustering: New Results
## 1 Introduction  
One of the most interesting and widely used approaches to the multidimensional data analysis are cluster analysis or clustering methods. Currently, there are many clustering algorithms. Despite significant differences between them, they all rely on the initial postulate of compactness: in the space of objects, all \"close\" objects must belong to the same cluster, and all different objects, respectively, must be in different clusters. The concepts of \"proximity\" are interpreted differently in different clustering algorithms. Within the framework of Discrete Mathematical Analysis (DMA)--an original approach to data analysis that uses fuzzy mathematics and fuzzy logic [1], methods of so-called DPS-clustering are being developed. The present study is devoted to DPS clustering and continues the series of papers on this problem [2, 3, 4, 5, 6, 7]. The initial notion of DPS-clustering is a fuzzy model of the fundamental mathematical property \"limit\". It is called the density and represents a non-negative function depending on an arbitrary subset and any point in the initial space in which clustering is supposed. The value of density can be understood as the strength of the connection between a subset and a point, as the degree of influence of a subset on a point, or dually, as the degree of limiting a point to a subset. This view of density automatically requires its monotonicity over a subset: the larger the subset, the stronger its impact on the point, and it is more limiting for it. Nontrivial densities always exist in a finite metric space (FMS). Each density on the FMS gives a new look at it and a new program of its study, so that the density is a new mathematical concept. Fixing the density level \(\alpha\) and interpreting it as a limit level, we can introduce the concept of discrete perfection with level \(\alpha\): a subset is called discretely perfect with level \(\alpha\) (\(\alpha\)-DPS- or simply DPS-set) if it consists of exactly all points of the original space \(\alpha\)-limit to it. A rigorous theory of DPS-sets has been constructed within the framework of DMA. In particular, it has been shown that DPS-sets have the properties of clusters. This, as well as the comparison of DPS-clustering with modern cluster analysis algorithms and its applications, is described in detail in [5]. The DPS-clustering algorithms created to date operate in finite metric spaces, depend on three parameters (density \(P\), density level \(\alpha\), and local coverage radius \(r\)) and have two stages. At the first stage, topological filtering of the original space is carried out. It is cleaned from noise. The DPS-algorithm iteratively cuts out from the original space (Figure 1a) the maximum \(\alpha\)-perfect subset (Figure 1b). At the second stage, the DPS-algorithm splits the result of the second stage into r-connected components for which it considers to be clusters (Figure 1c). For the array in Figure 1a and for the SDPS-algorithm that is the most known of the DPS-algorithms Section 2.2.2, the clusters are shown in different colors in Figure 1b. Similar clusters obtained as a result of working on a given array of well-known cluster analysis algorithms DBSCAN [8] and OPTICS [9] practically coincide and are shown in Figure 1c. This allows us to conclude that DPS-algorithms, like the DBSCAN and OPTICS algorithms, represent a new stage in cluster analysis, since they not only split the initial space into homogeneous parts, but also preliminarily clear it of noise (filter). Studies show that there are situations where the result of the first stage does not include all noteworthy clusters. Decreasing the limitation level \(\alpha\) leads to a decrease in the quality of a cluster recognition and is not a way out of the situation. Furthermore, due to the locality of the radius, the partitioning into \(r\)-connected components of the maximum \(\alpha\)-perfect subset in the second stage is often too shallow, and detailed, and needs to be enlarged as can be seen in Figure 1b.