DPS Clustering: New Results

Abstract

The results presented in this paper are obtained as part of the continued development and research of clustering algorithms based on the discrete mathematical analysis. The article briefly describes the theory of Discrete Perfect Sets (DPS-sets) that is the basis for the construction of DPS-clustering algorithms. The main task of the previously constructed DPS-algorithms is to search for clusters in multidimensional arrays with noise. DPS-algorithms have two stages: the first stage is the recognition of the maximum perfect set of a given density level from the initial array, the second stage is the partitioning of the result of the first stage into connected components, which are considered to be clusters. Study of qualities of DPS-algorithms showed that, in a number of situations in the first stage, the result does not include all clusters which have practical sense. In the second stage, partitioning into connected components can lead to unnecessarily small clusters. Simple variation of parameters in DPS-algorithms does not allow for eliminating these drawbacks. The present paper is devoted to the construction on the basis of DPS-algorithms of their new versions, more free from these drawbacks.

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.

The present work is devoted to correcting these disadvantages.

2. Materials and Methods

This section defines DPS-sets and describes DPS-clustering algorithms.

2.1. Discrete Perfect Sets

DMA has a rigorous theory of discrete perfect sets (DPS-sets) in finite spaces, which is summarized in [5]. A complete rigorous justification can be found in [3].

Let X be a finite set, and let $A,B,\dots$ and $x,y,\dots$ be subsets and points in it, respectively.

Definition 1.

Let us call a density P on a set X a product of mapping $2^X\times X$ to non-negative numbers ${\mathbb{R}}^{+}$, increasing on the first argument and trivial on the empty:

$$\begin{array}{c}P(A,x)=P_A\left(x\right)\\ \forall x\in X,A\subset B\Rightarrow P_A\left(x\right)\le P_B\left(x\right),P_{⌀}\left(x\right)=0\end{array}$$

(1)

For a fixed x, the function $P_A\left(x\right)$ is a non-normalized fuzzy measure on X, so the density P is a family of such measures parameterized by X itself.

By fixing a density level $\alpha$ and interpreting it as a limit level, one can define any topological notions in X, and discrete perfection with level $\alpha$ particularly.

Definition 2.

A set A consisting of exactly all α-perfect points of the original space X is called an α-discrete perfect (just perfect, DPS-) set in X:

$$A-\mathit{DPS-set}\mathrm{in}X\iff A=\{x\in X:P_A\left(x\right)\ge \alpha \}$$

(2)

Numerous studies and examples below show that DPS-sets are clusters in X and are closely related to clustering in X.

In the works [2,3,5], a construction is given that allows a subset $A\left(\alpha \right)\subset X$ to be constructed from a subset A in the space X and the level $\alpha$ of the density P. Under the condition of nontriviality, it will be an $\alpha$-DPS-set in X. It does not have to lie in A, but if A itself is an $\alpha$-DPS-set in X, then the set $A\left(\alpha \right)$ constructed for it will coincide with it. Thus, the construction $A\Rightarrow A\left(\alpha \right)$ depends on the space X, subset A, density P, and level $\alpha$. To emphasize this fact, we introduce the notation

$$A\left(\alpha \right)=A_P\left(\alpha \right|X).$$

(3)

The properties of the construction $A\Rightarrow A_P\left(\alpha \right|X)$ are formulated in Statement 1, which is proved in [3].

Statement 1. 

The dependences on A, P and X are increasing, and the dependence on α is decreasing:

(1)

If $A\subseteq B$, then $A\left(\alpha \right)\subseteq B\left(\alpha \right)$;

(2)

If P, Q are densities on X and $P_A\left(x\right)\le Q_A\left(x\right)\forall x\in X$, then $A_P\left(\alpha \right)\le A_Q\left(\alpha \right)$;

(3)

If $\alpha <\beta$, then $A\left(\beta \right)\subseteq A\left(\alpha \right)$.

(4)

If $A\subseteq X\subset Y$ and density P is given on Y, then $A\left(\alpha \right|X)\subseteq A(\alpha \left|Y\right)$.

2.2. DPS-Algorithms

In the case of the entire space X, the transition $X\Rightarrow X\left(\alpha \right)$ is an iterative cutting:

$$\begin{array}{c}X\left(\alpha \right)={\cap }_i{X}^i\left(\alpha \right)\\ X^{i+1}\left(\alpha \right)=\{x\in X:P_{X^i\left(\alpha \right)}\left(x\right)\ge \alpha \},X^0\left(\alpha \right)=X\end{array}$$

(4)

If there is a metric on the space X and the density P is compatible with it, the property of $\alpha$-perfectness is inherited by the connected components of the set $X\left(\alpha \right)$. Precisely, they most closely correspond in the first approximation to empirical clusters.

In what follows, a metric d is given on the space X, so that $(X,d)$ is a FMS.

2.2.1. Topological Digression

Two points x and y in A are called r-connected if there exists a chain of r-close to each other points $x_0,\dots ,x_n$ in A with the beginning $x_0=x$, and the end $x_n=y$ and distances $d(x_i,x_{i+1})\le r$, $i=0,\dots ,n-1$. The r-connectivity relation is an equivalence splitting the set A into r-connectivity components, which, depending on the context, will be denoted $cA\left(k\right)=c_{r}A\left(k\right)$, $k=1,\dots ,k^{*}=k^{*}(A,r)$. Let us denote their collection by $C\left(A\right)=C_r\left(A\right)=\{cA=c_{r}A\left(k\right){|}_1^{k^{*}}\}$. Thus:

$$A={\vee }_{cA\in C\left(A\right)}cA={\vee }_{k=1}^{k^{*}}cA\left(k\right),$$

(5)

where the sign ∨ denotes a disjoint union of sets.

For $x\in X$, $A\subset X$, we denote by $D_A(x,r)$ the closed ball in A centered at x with radius r: $D_A(x,r)=\{a\in A:d(x,a)\le r\}$.

Definition 3.

Let P be a density on X, $r>0$. A density P is called r-local if

$$\forall x\in X,A\subset X\Rightarrow P_A\left(x\right)=P_{D_A(x,r)}\left(x\right)$$

(6)

Statement 2.

If the density Pr-local, then every r-connected component of the set $X\left(\alpha \right)$ is α-perfect.

Proof. 

According to (2), for any $k=1,\dots ,k^{*}$, it is necessary to establish the equality of the component $c_{r}X\left(\alpha \right)\left(k\right)$ with the set $\{x\in X:P_{c_{r}X\left(\alpha \right)\left(k\right)}\left(x\right)\ge \alpha \}$, which we denote by $c_{r}X\left(\alpha \right){\left(k\right)}^1$.

The inclusion of $c_{r}X\left(\alpha \right)\left(k\right)\subseteq \{x\in X:P_{c_{r}X\left(\alpha \right)\left(k\right)}\left(x\right)\ge \alpha \}$. $x\in c_{r}X\left(\alpha \right)\left(k\right)\Rightarrow x\in X\left(\alpha \right)\Rightarrow P_{X\left(\alpha \right)}\left(x\right)\ge \alpha$. Furthermore, $D_{X\left(\alpha \right)}(x,r)=D_{c_{r}X\left(\alpha \right)\left(k\right)}(x,r)$, since $d(x,c_{r}X\left(\alpha \right)\left(\overline{k}\right))>r$ for $\overline{k}\ne k$. Due to the r-locality of P $P_{c_{r}X\left(\alpha \right)\left(k\right)}\left(x\right)=P_{D_{c_{r}X\left(\alpha \right)\left(k\right)}(x,r)}\left(x\right)=P_{D_{X\left(\alpha \right)}(x,r)}\left(x\right)=P_{X\left(\alpha \right)}\left(x\right)\ge \alpha$, $x\in c_{r}X\left(\alpha \right){\left(k\right)}^1$.

The inclusion of $c_{r}X\left(\alpha \right)\left(k\right)\supseteq \{x\in X:P_{c_{r}X\left(\alpha \right)\left(k\right)}\left(x\right)\ge \alpha \}$.

First case $(x\notin c_{r}X\left(\alpha \right)\left(k\right))\wedge (x\notin X\left(\alpha \right))$. Then, $P_{c_{r}X\left(\alpha \right)\left(k\right)}\left(x\right)\le P_X\left(\alpha \right)\left(x\right)<\alpha \Rightarrow x\notin c_{r}X\left(\alpha \right){\left(k\right)}^1$.

Second case $(x\notin c_{r}X\left(\alpha \right)\left(k\right))\wedge (x\in X\left(\alpha \right))$. Then, $(x\in c_{r}X\left(\alpha \right)\left(\overline{k}\right))$ and $d(x,c_{r}X\left(\alpha \right)\left(\overline{k}\right))>r$, and therefore $D_{c_{r}X\left(\alpha \right)\left(k\right)}(x,r)=⌀$.

Taking into account the normalization of the density P and its r-locality, $P_{c_{r}X\left(\alpha \right)\left(k\right)}\left(x\right)=0$. Thus, in this case, $x\notin c_{r}X\left(\alpha \right){\left(k\right)}^1$. □

Definition 4. 

DPS-algorithm depends on three parameters: radius r, r-local density P and level α: $\mathit{DPS}=\mathit{DPS}(P,\alpha ,r)$ and has two stages:

1.

The first stage of $\mathit{DPS}\iff$ the process of constructing for FMS $(X,d)$ based on the r-local density P its α-envelope $X\left(\alpha \right)$:

$$\mathit{DPS}(P,\alpha ,r)\iff X\Rightarrow X\left(\alpha \right)$$

2.

The second stage of $\mathit{DPS}\iff$ the partitioning of the α-envelope $X\left(\alpha \right)$ into r-connected components:

$${\mathit{DPS}}_c(P,\alpha ,r)\iff X\Rightarrow C\left(X\left(\alpha \right)\right)\subset 2^{2^X}.$$

Further in the text, $\mathit{DPS}(P,\alpha ,r)$ denotes, depending on the context, either the algorithm itself or its first stage.

Let us present a flowchart of the DPS-algorithm (Figure 2).

Let us summarize the above from the perspective of a cluster analysis: 1st stage $\mathrm{DPS}(P,\alpha ,r)$ carves the maximal subset $X\left(\alpha \right)$ dense in the common background from the original space X; 2nd stage ${\mathrm{DPS}}_c(P,\alpha ,r)$ partitions $X\left(\alpha \right)$ into components of r-connectivity $cX\left(\alpha \right)$, each of which combines density on background and connectivity, i.e., formally expresses empirical clustering [5].

DPS-clustering has developed methods for choosing the parameters $\alpha$, r, which are described in detail in [5] (see also Section 4.3.1). In particular, the density index $\alpha$ is determined through the level of its extremity $\beta \left(\alpha \right)$, which answers the question on the scale $[-1,1]$: “To what extent can $\alpha$ be considered large against the background of all values of the density P on X?”.

When constructing $\beta \left(\alpha \right)$, a fuzzy comparison of n between non-negative numbers is used. It is expressing on the scale $[-1,1]$ the degree of superiority of the larger of them over the smaller one (the left part in (7))

$$\beta \left(\alpha \right)=\frac{{\sum }_{x\in X}n(P_X\left(x\right),\alpha )}{\left|X\right|},\frac{{\sum }_{x\in X}n(P_X\left(x\right),\alpha \left(\beta \right))}{\left|X\right|}=\beta .$$

(7)

Due to the properties of n, the correspondence $\alpha \Rightarrow \beta \left(\alpha \right)$ is unique and the inverse dependence $\beta \Rightarrow \alpha \left(\beta \right)$ is implicitly given by the right side of (7). Thus, the DPS algorithm has a second parameterization, which will be used in the future:

$$\begin{array}{ccc}\hfill X\left(\beta \right)& \iff & X\left(\alpha \right(\beta \left)\right)\hfill \\ \hfill \mathrm{DPS}(P,\beta ,r)& \iff & \mathrm{DPS}(P,\alpha (\beta ),r)\hfill \\ \hfill {\mathrm{DPS}}_C(P,\beta ,r)& \iff & {\mathrm{DPS}}_C(P,\alpha \left(\beta \right),r)\hfill \end{array}$$

(8)

2.2.2. SDPS-Algorithm

Historically, the first in a series of DPS-algorithms was the set-theoretic SDPS. It is based on the density S, which has the name “Number of points” (“Amount of space”) [2,3,6] and conveys the degree of concentration of space X around each of its points x (the most natural understanding of the density X in x).

The density $S_A\left(x\right)$ depends on the localization radius r and the non-negative parameter p, which takes into account the distance to x in the ball $D_A(x,r)$:

$$S_A\left(x\right)=S_A\left(x\right|p)=\sum _{y\in D_A(x,r)}{\left(1-\frac{d(x,y)}{r}\right)}^p.$$

(9)

With $p=0$, we obtain the usual number of points, which explains the name S:

$$S_A\left(x\right|0)=\left|D_A(x,r)\right|.$$

The density S is r-local, and the SDPS-algorithm is the operation of a DPS-scheme based on S: $\mathrm{SDPS}=DPS(S,\beta ,r)$.

The result of SDPS-condensing in $X\iff$ sets locally containing “many X”. They are formally the most consistent with empirical clusters. By varying the SDPS parameters, one can obtain a fairly complete idea of the hierarchy of clusters in X.

The SDPS-algorithm will serve as a testing ground where new results for the DPS-series algorithms will be tested and shown.

3. Results: Iterative DPS

The first DPS-stage of the $\mathrm{DPS}(P,\beta ,r)$ algorithm carves a maximal perfect subset $X\left(\beta \right)$, $\beta$-extremely P-dense in the background of X at each of its points, from the space X.

Let us turn to Figure 3b: it shows the result $X\left(\beta \right)$ of the DPS algorithm on array X (Figure 3a) in red when $\beta =0.02$. It is easy to see that not all noteworthy condensations from X were included. The reason for their non-inclusion in the result $X\left(\beta \right)$ is explained by the contradiction between the r-local character of the view of X and the global approach to determine the level $\alpha \left(\beta \right)$ of density P by its extremality level $\beta$ based on the whole image $P_X\left(X\right)$ (7) and (8): the density level of worthy condensations in the complement $\overline{X\left(\beta \right)}$ appears to be below $\alpha \left(\beta \right)$.

To include them in the final result, we need to lower the extremum level $\beta$: $\beta \Rightarrow \overline{\beta }<\beta$ and switch from the $\mathrm{DPS}(P,\beta ,r)$ to the $\mathrm{DPS}(P,\overline{\beta },r)$ algorithm. In the control example, the first level of $\overline{\beta }$, for which the result $X\left(\overline{\beta }\right)$ will include all worthy condensations, will be $\overline{\beta }=-0.25$. The result is shown in red in Figure 3c: we see that the result $X\left(\overline{\beta }\right)$ of the algorithm $\mathrm{DPS}(P,\overline{\beta },r)$, along with $X\left(\beta \right)$ and worthy condensations from $\overline{X\left(\beta \right)}$, included weak points of the r-halo of the set $X\left(\beta \right)$, and it helped them in this.

It can be done otherwise: keep the extremum level $\beta$, but change the original space by transition from X to $\overline{X\left(\beta \right)}$. The result of $\mathrm{DPS}(P,\beta ,r)$ on $\overline{X\left(\beta \right)}$ is shown in green in Figure 3b. If we make another similar transition, a blue cluster appears in Figure 3b.

Such way of using the DPS scheme is called the ‘‘iterative DPS’’ algorithm.

3.1. Iterations by Extremality

It will be remembered that the level $\alpha \left(\beta \right)$ of density P by extremality level $\beta$ is determined in the $\mathrm{DPS}(P,\beta ,r)=\mathrm{DPS}(P,\alpha (\beta ),r)$ algorithm from Equation (8). Let us introduce the partition $X=X\left(\beta \right)\vee \overline{X\left(\beta \right)}$. According to (7) and (8),

$$\begin{array}{cc}\hfill \beta =& n(P_X\left(X\right),\alpha \left(\beta \right))=\frac{{\sum }_{x\in X\left(\beta \right)}n(P_X\left(x\right),\alpha \left(\beta \right))+{\sum }_{x\in \overline{X\left(\beta \right)}}n(P_X\left(x\right),\alpha \left(\beta \right))}{\left|X\right|}=\hfill \\ \hfill =& \frac{\left|X\right(\beta \left)\right|}{\left|X\right|}\frac{{\sum }_{x\in X\left(\beta \right)}n(P_X\left(x\right),\alpha \left(\beta \right))}{\left|X\right(\beta \left)\right|}+\frac{|\overline{X\left(\beta \right)}|}{\left|X\right|}\frac{{\sum }_{x\in \overline{X\left(\beta \right)}}n(P_X\left(x\right),\alpha \left(\beta \right))}{|\overline{X\left(\beta \right)}|}.\hfill \end{array}$$

From the properties of convexity, hence the inequality

$$max\left(\frac{{\sum }_{x\in X\left(\beta \right)}n(P_X\left(x\right),\alpha \left(\beta \right))}{\left|X\right(\beta \left)\right|},\frac{{\sum }_{x\in \overline{X\left(\beta \right)}}n(P_X\left(x\right),\alpha \left(\beta \right))}{|\overline{X\left(\beta \right)}|}\right)\ge \beta .$$

However, the left mean $\le 0$ because $\forall x\in X\left(\beta \right)\Rightarrow P_X\left(x\right)\ge P_{X\left(\beta \right)}\left(x\right)\ge \alpha \left(\beta \right)$. Hence, if $\beta \ge 0$, the right mean must be $\ge \beta$:

$${\sum }_{x\in \overline{X\left(\beta \right)}}\frac{n(P_X\left(x\right),\alpha \left(\beta \right))}{|\overline{X\left(\beta \right)}|}\ge \beta .$$

Then, from the inequalities $\forall x\in X\Rightarrow P_{\overline{X\left(\beta \right)}}\left(x\right)\le P_X\left(x\right)$ and the properties of fuzzy comparison n, we have:

$$\begin{array}{cc}\hfill n\left(P_{\overline{X\left(\beta \right)}}\left(\overline{X\left(\beta \right)}\right),\alpha \left(\beta \right)\right)& =\frac{{\sum }_{x\in \overline{X\left(\beta \right)}}n(P_{\overline{X\left(\beta \right)}}\left(x\right),\alpha \left(\beta \right))}{|\overline{X\left(\beta \right)}|}\ge \hfill \\ & \ge {\sum }_{x\in \overline{X\left(\beta \right)}}\frac{n(P_X\left(x\right),\alpha \left(\beta \right))}{|\overline{X\left(\beta \right)}|}\ge \beta .\hfill \end{array}$$

It follows that the density level ${\alpha }_1\left(\beta \right)$, required for the operation of $\mathrm{DPS}(P,\beta ,r)$ algorithm on the space $\overline{X\left(\beta \right)}$:

$$n\left(P_{\overline{X\left(\beta \right)}}\left(\overline{X\left(\beta \right)}\right),{\alpha }_1\left(\beta \right)\right)=\beta$$

does not exceed the level $\alpha \left(\beta \right)$, which we will consider as zero: $\alpha \left(\beta \right)={\alpha }_0\left(\beta \right)$, and can be strictly less than it. In addition, this, in turn, means the possible nontriviality of such operation, i.e., the set $\overline{X\left(\beta \right)}\left(\beta \right)$. Let us denote it by $X_1\left(\beta \right)$.

In the situation of non-triviality $X_1\left(\beta \right)$, one can define the first iteration on the extremity $X(\beta ,1)$ of the set $X\left(\beta \right)$, which is naturally considered as its null iteration, assuming $X(\beta ,0)=X\left(\beta \right)$.

Definition 5.

Let $X_1\left(\beta \right)$ be non-trivial, and we will call by the first iteration of the space X with respect to the extremity level β the disjoint union

$$X(\beta ,1)=X(\beta ,0)\vee X_1\left(\beta \right).$$

Note 1.

Given this definition, the above can be understood as the first precondition for the existence of the first iteration on extremality when β is non-negative. In this connection, the zero level of β appears to be the most productive and interesting, at which the second precondition (non-triviality of the result) will be the weakest.

A direct check shows that $P_{X(\beta ,1)}\left(x\right)\ge {\alpha }_1\left(\beta \right)$$\forall x\in X(\beta ,1)$, so, by repeating the above deduction with replacement ${\alpha }_0\left(\beta \right)\Rightarrow {\alpha }_1\left(\beta \right)$, $X(\beta ,0)\Rightarrow X(\beta ,1)$, we obtain the level ${\alpha }_2\left(\beta \right)\le {\alpha }_1\left(\beta \right)$ of the $\mathrm{DPS}(P,\beta ,r)$ algorithm on the complement $\overline{X(\beta ,1)}$ and the possible nontriviality of its result $X_2\left(\beta \right)=\overline{X(\beta ,1)}\left(\beta \right)$.

If all this can be continued up to and including the i-th step, i.e., the sets $X_1\left(\beta \right),\dots ,X_i\left(\beta \right)$, will be nontrivial, then their union with $X(\beta ,0)=X\left(\beta \right)$ will be called the i-th iteration of X by extremum level $\beta$:

$$X(\beta ,i)=X(\beta ,0)\vee X_1\left(\beta \right)\vee \dots X_i\left(\beta \right).$$

(10)

3.2. Iterations of the DPS Algorithm

Considering the algorithms $\mathrm{DPS}(P,\beta ,r)$ and ${\mathrm{DPS}}_c(P,\beta ,r)$ as their zero iterations: ${\mathrm{DPS}}^0(P,\beta ,r)=\mathrm{DPS}(P,\beta ,r)$, ${\mathrm{DPS}}_c^0(P,\beta ,r)={\mathrm{DPS}}_c(P,\beta ,r)$, we define their i-th iterations as processes of building for space X its i-th iteration $X(\beta ,i)$ and then breaking it into r-connectivity components:

$$\begin{array}{ccc}\hfill {\mathrm{DPS}}^i(P,\beta ,r)& \iff & X\Rightarrow X(\beta ,i)\hfill \\ \hfill {\mathrm{DPS}}_c^i(P,\beta ,r)& \iff & X\Rightarrow C_r\left(X(\beta ,i)\right)\hfill \end{array}$$

(11)

Due to the disjunctive nature of the decomposition (10), the iteration index ind is correctly defined at the i-th iteration of $X(\beta ,i)$:

$$\forall x\in X(\beta ,i)\Rightarrow ind\left(x\right)=\left\{\begin{array}{c}0,\mathrm{if}x\in X\left(\beta \right)\hfill \\ \overline{i}\in [1,i],\mathrm{if}x\in X_{\overline{i}}\left(\beta \right)\hfill \end{array}\right..$$

The index ind moves from points to connectivity components $c=cX(\beta ,i)$, thus becoming multivalued:

$$ind\left(c\right)=\{ind(x):x\in c\}.$$

In addition, this, in turn, makes it possible for any subset $I\in [0,i]$ to define a conditional version of the ${\mathrm{DPS}}^I$ algorithm:

$$\begin{array}{c}{\mathrm{DPS}}^I(P,\beta ,r)={\vee }_{i\in I}{X}_i\left(\beta \right)\hfill \\ {\mathrm{DPS}}_c^I(P,\beta ,r)=\{c\in C\left(X(\beta ,i)\right):ind\left(c\right)\in I\}\hfill \end{array}.$$

(12)

Example 1.

Figure 4b–d show the sets $X_i\left(\beta \right)$, $i=0,1,2$ for the array X shown in Figure 4a, obtained as a result of the operation of the SDPS-algorithm at $\beta =-0.09$ based on the fuzzy comparison $n(t,s)=(s-t)/(s+t)$ of non-negative numbers s and t [1].

Figure 5 shows both stages of the ${\mathrm{SDPS}}^1$-algorithm. Its result ${\mathrm{SDPS}}_e^1\left(X\right)$ indicates that, in the general case, the second stage of DPS cannot be considered final: many components of the r-connectivity in Figure 5b need further connection. This will be done by the third stage of DPS, the results of which on a given array X for a given SDPS-algorithm will be shown in Example 4.

4. Results: Third Stage of DPS

The first stage of the algorithm $\mathrm{DPS}\iff \mathrm{DPS}(P,\alpha ,r)$ cuts out from the original FMS X the maximum $\alpha$-perfect subset $X\left(\alpha \right):\mathrm{DPS}\left(X\right)=X\left(\alpha \right)$. The second stage of the algorithm ${\mathrm{DPS}}_C\iff {\mathrm{DPS}}_C(P,\alpha ,r)$ is considered to be its result and is the set of all components of the r-connectivity of the set $X\left(\alpha \right):{\mathrm{DPS}}_C\left(X\right)=C_{r}X\left(\alpha \right)$. Each $c_{r}X\left(\alpha \right)$ component is considered to be a DPS-cluster because, by virtue of the initial assumption that the initial density is r-local, P is a DPS-set in X and, in particular, is $\alpha$-dense at each of its points.

At this stage, the result ${\mathrm{DPS}}_C\left(X\right)$ is taken as a given and is not subject to further transformation. The radius r is assumed to be infinitely small, and the level $\alpha$ of P is infinitely large. As a consequence, each component $cX\left(\alpha \right)$ is considered to be a single and indivisible spot (large point).

Spots $cX\left(\alpha \right)$ are interpreted as fragmentary manifestations (exits) of global anomalous entities in X. To understand their true scales, if possible, further connection of spots is necessary. This is the third and final stage of the DPS-algorithm.

4.1. Logic and Action Plan

A collection of spots $C\subset {\mathrm{DPS}}_c\left(X\right)$ is considered by the expert as a whole if the degree of advantage in the closeness of internal transitions (paths) between any of its spots over external transitions from C to $\overline{C}$, allows the expert to conclude that C is non-random.

Thus, the cluster of spots C must have a tighter internal connection between them in the general background of all spots from ${\mathrm{DPS}}_c\left(X\right)$. There are no other constraints on C, in particular on shape.

Because of the $\alpha$-perfectness of the $cX\left(\alpha \right)\left(k\right)$ spots, it is natural to consider the minimum distance between the closest points in them as the distance between them:

$$d(cX\left(\alpha \right)\left(k\right),cX\left(\alpha \right)\left(\overline{k}\right))=min\{d(y,\overline{y}):y\in cX\left(\alpha \right)\left(k\right),\overline{y}\in cX\left(\alpha \right)\left(\overline{k}\right)\}.$$

(13)

It will no longer be a metric since there are no triangle inequalities for d (13), as the example below shows:

Example 2.

Consider subsets of the real line: $A=[1,1]$, $B=[2,3]$, $C=[4,4]$. It is obvious $d(A,B)+d(C,B)<d(A,C)$, $d(A,B)=|2-1|$, $d(B,C)=|4-3|$, $d(A,C)=|4-1|$.

Based on the distance d, the formalization of the expert’s logic for connecting spots is constructed: in each cluster of spots C, any two spots can be connected by a chain of spots whose distance d between neighboring links will be smaller than the distance d from C to $\overline{C}$. This is the d-clustering condition necessary for C. Its formal analysis will be the first part of the functioning program to algorithmise the third stage of the DPS. Note that d-clustering and DPS-clustering are different interpretations of clustering: the first is based on connectivity, and the second on limiting.

The second part of this program consists of constructing, based on the initial distance d in the original space X, measures of proximity and distance between spots expressing in this the expert. Based on these, only those spots are selected from the d-clusters of spots in which the proximity advantage of the inner transitions over the range of the outer ones will be non-random in the expert’s opinion.

4.2. FirstPart: The Theory of d-Clusters

Initial data and designations: X is a finite set, d is a quasi-metric in X ($(X,d)$ is a quasi-metric space)

$$\begin{array}{c}\forall x\in X\Rightarrow d(x,x)=0\hfill \\ \forall x,y\in X\Rightarrow d(x,y)=d(y,x)\ne 0\hfill \end{array}$$

Definition 6.

By the enumeration $X\left(x\right)$ of space X with origin at the point x, we call the sequence $x=x_0,\dots ,x_{\left|X\right|-1}$ for which for any $i=0,\dots ,\left|X\right|-2$

$$d(x_{i+1},X_i\left(x\right))=d\left(X_i\left(x\right),\overline{X_i\left(x\right)}\right),$$

(14)

where $X_i\left(x\right)=\{x_0,\dots ,x_i\}$.

4.2.1. The Notation

$d\left(x\right)$ is a numerical sequence of distances $d_i\left(x\right)=d\left(X_{i-1}\left(x\right),\overline{X_{i-1}\left(x\right)}\right)$:

$$d\left(x\right)=\{d_1\left(x\right),\dots ,d_{\left|X\right|-1}\left(x\right)\}$$

(15)

Definition 7.

Let us call an eigen d-cluster $C=C_k\left(x\right)$, $1\le k\le \left|X\right|-2$ with center (origin) in x the eigen segment $X_k\left(x\right)$ of the enumeration $X\left(x\right)$, for which ${max}_{i=1}^k{d}_i\left(x\right)<d_{k+1}\left(x\right)$:

$$C=C_k\left(x\right)\iff \begin{array}{c}\mathit{eigen}\\ d-\mathit{cluster}\end{array}\iff \left(C=C_k\left(x\right)\right)\wedge \left({max}_{i=1}^k{d}_i\left(x\right)<d_{k+1}\left(x\right)\right)$$

(16)

Statement 3.

The cluster $C_k\left(x\right)$ is independent of the choice of origin within itself:

$$C_k\left(x\right)=C_k\left(y\right)\forall y\in C_k\left(x\right)\setminus x$$

In other words, in the case of d-clustering, there is a set-theoretic equality $X_k\left(x\right)=X_k\left(y\right)$ that is, for any $y\in C_k\left(x\right)$, the first $k+1$ terms in the enumeration $X\left(y\right)$ will lie in $C_k\left(x\right)$.

Proof. 

Induction on the number i of steps $y_{i-1}\Rightarrow y_i$, $i=1\le i\le k$ in the enumeration $X\left(y\right)$. Let $y=x_j$, $j=1,\dots ,k$.

•

$i=1$. We have to show that $y_1\in C_k\left(x\right)$. By virtue of $y\in C_k\left(x\right)$, we have

$$d\left(y,\overline{C_k\left(x\right)}\right)\ge d\left(C_k\left(x\right),\overline{C_k\left(x\right)}\right)=d_{k+1}\left(x\right).$$

The element $y=x_j$ in $C_k\left(x\right)=X_k\left(x\right)$ has two neighbors $x_{j-1}$ and $x_{j+1}$, if $1\le j<k$, and one neighbor $x_{k-1}$, if $j=k$ and $y=x_k$. To any of the neighbors, the distance from y will be less than $d_{k+1}\left(x\right)$, so the next element after $y=y_0$ in the sequence $X\left(y\right)$ necessarily lies $C_k\left(x\right)$.

•

Let the assumption that the first i steps of $y_i$, $i\le k-1$ in the sequence $X\left(y\right)$ lie in $C_k\left(x\right)$ be satisfied. Let us show that the element $y_{i+1}$ will also lie in $C_k\left(x\right)$.

Under our assumptions $X_i\left(y\right)\subset C_k\left(x\right)$, therefore

$$d(X_i\left(y\right),\overline{C_k\left(x\right)})>d(C_k\left(x\right),\overline{C_k\left(x\right)})=d_{k+1}\left(x\right).$$

Assume $y_m=x_{s\left(m\right)}$, $m=0,\dots ,i$. If $s_0<\dots <s_i$ is the correct ordering of array ${s\left(m\right)|}_0^i$, then two cases are possible:

1st:

the array $s_p{|}_0^i$ has no gaps, that is, it is an eigensegment in $[0,k]$. In this case, $C_k\left(x\right)$ necessarily contains either an element $x_{s_0-1}$, or an element $x_{s_i+1}$, whose distance from $X_i\left(y\right)$ is nontrivial and less than $d_{k+1}\left(x\right)$. Hence, the term $y_{i+1}$ in the sequence $X\left(y\right)$ necessarily lies in $C_k\left(x\right)$:

2nd:

$s_p{|}_0^i$ array has gaps. Let $p^{*}$ be the first number for which $s_{p^{*}+1}-s_{p^{*}}>1$. In this case, in the array $s_p{|}_0^i$, it has no number $s_{p^{*}}+1$ and in the set $X_i\left(y\right)$ of an element $x_{s_{p^{*}}+1}$, whose distance from $x_{s_{p^{*}}}$ will be less than $d_{k+1}\left(x\right)$. Hence, in this case too, the term $y_{i+1}$ in the sequence $X\left(y\right)$ lies in $C_k\left(x\right)$.

□

Consequence 1.

Eigen d-clusters behave like non-Archimedean balls: either one contains the other or they do not intersect. In particular, two d-clusters of the same order either coincide or do not intersect.

Proof. 

Let $C=C_k\left(x\right)$, $\overline{C}=C_{\overline{k}}\left(\overline{x}\right)$ and $y\in C\cap \overline{C}$. According to Statement 3, $C=X_k\left(y\right)$, $\overline{C}=X_{\overline{k}}\left(y\right)$. If $k\le \overline{k}$, then $C\subseteq \overline{C}$. □

The d-clusters of $C_k\left(x\right)$ are eigennonpoint subsets in X. Let us remove this restriction on k in Definition 7 using the notion of a connectivity exponent, which develops and continues the topic of finite connectivity Section 2.2.1.

Definition 8. 

1.

Connectivity index $r\left(A\right)$ of a subset $A\iff$ minimum r for which A is r-connected:

$$r\left(A\right)=min\{r:A\mathit{r-connected}\}.$$

2.

The isolation index $e\left(A\right)$ of a subset $A\iff$ the distance to its complement $\overline{A}$:

$$e\left(A\right)=d(A,\overline{A}).$$

Statement 4.

$$r\left(X_k\left(x\right)\right)={max}_{i=1}^k{d}_i\left(x\right)$$

Proof. 

1.

Proof of the inequality $r\left(X_k\left(x\right)\right)\le {max}_{i=1}^k{d}_i\left(x\right)$. Induction on k, $1\le k\le \left|X\right|-2$

• $k=1$: $X_1\left(x\right)=\{x_0,x_1\}$ and $d(x_0,x_1)=d_1\left(x\right)$ according to (14) and (15).
• Suppose that $r\left(X_{k-1}\left(x\right)\right)\le {max}_{i=1}^{k-1}{d}_i\left(x\right)$, that is, any two points in $X_{k-1}\left(x\right)$ can be connected by a path with distance transitions $\le {max}_{i=1}^{k-1}{d}_i\left(x\right)$. Let $x^{*}$ be the point in $X_{k-1}\left(x\right)$, closest to $x_k$. According to (15), $d_k\left(x\right)=d(x^{*},x_k)$. Through $x^{*}$ any point in $X_{k-1}\left(x\right)$ can be connected to $x_k$ by a path with distance transitions $\le {max}_{i=1}^k{d}_i\left(x\right)$.

2.

Proof of the inequality $r\left(X_k\left(x\right)\right)\ge {max}_{i=1}^k{d}_i\left(x\right)$: let $d_{i^{*}}\left(x\right)={max}_{i=1}^k{d}_i\left(x\right)$, then $d_{i^{*}}\left(x\right)=d\left(X_{i^{*}-1}\left(x\right),\overline{X_{i^{*}-1}\left(x\right)}\right)$, and any path with ends in $X_{i^{*}-1}\left(x\right)$ and $\overline{X_{i^{*}-1}\left(x\right)}$ has at least one jump between them. Therefore, $r\left(X_k\left(x\right)\right)\ge d_{i^{*}}\left(x\right)$.

□

For the eigen d-cluster C (Definition 7), the proved statement means that the necessary condition is fulfilled

$$r\left(C\right)<e\left(C\right).$$

(17)

It is invariant not only from the beginning of the enumeration but also from the enumeration itself, which is obligatory at this point for the definition of C. Therefore, it is natural to check this condition for sufficiency of d-clustering.

Statement 5.

If (17) is satisfied for an eigensubset of A in X, then A is a d-cluster and $A=C_{\left|A\right|-1}\left(x\right)$$\forall x\in A$.

Proof. 

There exists $r^1$: $r\left(A\right)\le r^1<d(A,\overline{A})$ for which the set A is $r^1$-connected. Hence, in the enumeration $X\left(x\right)$ of space X from any point $x\in A$ the elements from $\overline{A}$ will appear only at the $\left|A\right|$-th step. □

The result of Definition 8, Statement 4 and Statement 5 is a new invariant and more complete definition of a d-cluster.

Definition 9.

Let us call a d-cluster in X the subset C for which there is a true inequation: $r\left(C\right)<d(C,\overline{C})$.

To the eigenclusters C$(1<|C|<|X\left|\right)$ will be added all points $x\in X$: $x=C_0\left(x\right)$, and all space X: $X=C_{\left|X\right|-1}\left(x\right)\forall x\in X$.

Thus, the restrictions in Definition 7 on k$(1\le k\le |X|-2)$ are removed:

•

$x\iff d$-cluster, since $0=r\left(x\right)<e\left(x\right)$$\forall x\in X$,

•

$X\iff d$-cluster, since $r\left(X\right)<e\left(X\right)=\infty$: no appearance for X means that it is at infinity.

4.2.2. Conclusions

The collection of d-clusters $C(X,d)$ forms a hierarchy of sets on X based on the notion of discrete connectivity and different from traditional hierarchical cluster analysis hierarchies, usually binary [10].

$C(X,d)$ is the first part of the formalization of the third stage of DPS.

4.3. Second Part: Final Selection of D-Clusters

Thanks to (14)–(16), the search for d-clusters in the space of r-connectivity components ${\mathrm{DPS}}_C\left(X\right)$ with respect to distance (13), that is, the formation of the space $C({\mathrm{DPS}}_C\left(X\right),d)$ is constructive. Each d-cluster $C\in C({\mathrm{DPS}}_C\left(X\right),d)$ has two characteristics: internal $r\left(C\right)$ and external $e\left(C\right)$ (17). Based on this information, expert E must decide: is it necessary to combine the spots from C into a single whole or not?

Let ${\mathrm{DPS}}_f\left(X\right)={\mathrm{DPS}}_f\left(X\right|\mathrm{E})$ denote the set of maximal d-clusters in ${\mathrm{DPS}}_C\left(X\right)$, obtained after joining spots by expert E. According to Consequence 1, they are all disjoint.

Under the condition that ${\mathrm{DPS}}_f\left(X\right)$ is nontrivial in the set $X\left(\alpha \right)$, a partition appears in the general case larger than the partition (5) into r-connectivity components:

$$X\left(\alpha \right)=\{C:C\in {\mathrm{DPS}}_f\left(X\right)\}\vee \{cX\left(\alpha \right):\forall C\in {\mathrm{DPS}}_f\left(X\right)\Rightarrow cX\left(\alpha \right)\notin C\}$$

(18)

Let it also denote by ${\mathrm{DPS}}_f\left(X\right)$ and consider it the third and final stage of the DPS algorithm. Full history is presented in Figure 6.

Thus, for each component $c_{r}X\left(\alpha \right)$, one of three things can happen:

• $c_{r}X\left(\alpha \right)\in {\mathrm{DPS}}_f\left(X\right)\iff$ component $c_{r}X\left(\alpha \right)$ is sufficiently isolated from the rest to be of interest to the expert, it is the only way out of the global entity behind it on X;
• $c_{r}X\left(\alpha \right)\notin {\mathrm{DPS}}_f\left(X\right)$, but $c_{r}X\left(\alpha \right)\subset C\in {\mathrm{DPS}}_f\left(X\right)\iff$ component $c_{r}X\left(\alpha \right)$ is part of the d-cluster C, which is of interest to the expert and in the team represents a global entity in X;
• $c_{r}X\left(\alpha \right)\notin C\forall C\in {\mathrm{DPS}}_f\left(X\right)\iff$ any d-cluster containing $c_{r}X\left(\alpha \right)$ is of no interest to the expert: either it is not internally dense enough, or it is externally separable. According to the expert, if $c_{r}X\left(\alpha \right)$ is a fragment of the output of the global entity on X, then it is not clear enough.

Furthermore, Example 3 will show that all options for $c_{r}X\left(\alpha \right)$ are possible.

At stage 3.2 (Figure 6), the expert can act in different ways. Let us present the simplest Boolean variant of actions for the formation of ${\mathrm{DPS}}_f\left(X\right)$.

4.3.1. Boolean Variant

Expert E decides whether d-cluster C is included in the final result ${\mathrm{DPS}}_f\left(X\right)$ based on comparison of $r\left(C\right)$ and $e\left(C\right)$ with their proximity and distance thresholds $r_{\mathrm{E}}$ and $e_{\mathrm{E}}$: $C\in DP{S}_f\left(X\right)\iff r\left(C\right)\le r_{\mathrm{E}}$ and $e\left(C\right)\ge e_{\mathrm{E}}$.

Expert E considers the parameter r of the DPS-algorithm to be very small (infinitesimal), much less than $r_{\mathrm{E}}$, which, in turn, according to E, is much less than $e_{\mathrm{E}}$:

$$r\le r_{\mathrm{E}}\le e_{\mathrm{E}}.$$

The threshold $r_{\mathrm{E}}$, like the radius r in the DPS-algorithm, is built using the Kolmogorov averaging of non-trivial distances of the FMS X [5]

$$r_{\mathrm{E}}={\left(\frac{{\sum }_{x\ne y\in X}d(x,y)}{\left|X\right|\left(\right|X|-1)}\right)}^{1/q},q=q\left(r_{\mathrm{E}}\right)$$

For the parameter r, numerous applications of DPS-series algorithms have established that the choice of $q\left(r\right)\in [-3,-2]$ can be considered optimal. The studies carried out within the framework of present paper show that $q\left(r_{\mathrm{E}}\right)\in [-2.5,-1,5]$. The intersection of the areas of parameters r, $r_{\mathrm{E}}$ is explained both by the fuzzy perception of proximity by the expert and by the diversity in the arrangement of an arbitrary FMS.

The threshold $e_{\mathrm{E}}$ is obtained from $r_{\mathrm{E}}$ by formalizing the expert judgment ‘‘$r_{\mathrm{E}}\ll e_{\mathrm{E}}$’’ using fuzzy comparison. For the comparison given in Example 1, this would be the inequality $e_{\mathrm{E}}/r_{\mathrm{E}}\ge 5/3$.

Example 3.

Array X in Figure 7a has already been seen above: it was a testing ground for DPS, DBSCAN, and OPTICS algorithms. Figure 7b–d show the complete DPS-scenario with parameters $\beta =-0.25$, $q\left(r\right)=-2.7$, $q\left(r_{\mathrm{E}}\right)=-2.3$, $e_{\mathrm{E}}/r_{\mathrm{E}}=5/3$.

The result of cutting at the first stage (Figure 7b) was divided into eight r-connectivity components at the second stage (Figure 7c). Two components (blue and light brown) and two more in a green combination passed independently to the third stage (Figure 7d). The remaining four brown components did not pass the third stage.

Example 4.

In the conditions, notation and parameters of Example 1 Figure 8a–c show the original array and two stages of the SDPS algorithm on it. Figure 8d–f show the complete scenario for his second iteration of ${\mathit{SDPS}}^2$.

Comparison of Figure 8c,f serves as clear evidence of the work done in the paper: the full version of the second iteration of ${\mathit{SDPS}}^2$ with the same parameters performs better than the incomplete zero version (the original SDPS algorithm) that existed before this article.

5. Discussion

The density P on a finite space X is a definition in X in the language of fuzzy mathematics of the property of limiting. From a formal point of view, P is a fuzzy structure on the direct product $2^X\times X$, monotonic in the first argument (1).

Fixing a level $\alpha \in [0,1]$ for P, we can define a closure operator on $2^X$ and, through it, the usual topology ${\tau }_{\alpha }$ on X. Thus, an increasing family of topologies $\{{\tau }_{\alpha },\alpha \in [0,1]\}$, arises on X, starting at zero with a trivially inseparable minimal topology of sticking together points and ending with a trivially separable maximal topology of all subsets.

Each density on the space X gives its own view of it and its own program of its study. It is a concept that does not lie in classical mathematics.

In addition to the density S Section 2.2.2, nontrivial densities always exist in a finite metric space. The description of the most important densities and their significance for data analysis are given in [5,11].

The study of the space X with the help of the density P defined on it began with the study of perfect sets in the topology ${\tau }_{\alpha }$. The explanation for this is as follows: setting P on X defines a clustering in X: K is a cluster (P-cluster) in X if it consists of exactly all points that are P-limit to it. If $\alpha$ is the limit threshold, then the formal expression of what has been said coincides with $\alpha$-perfection: $K=\{x\in X:P_K\left(x\right)\ge \alpha \}$.

The DPS-algorithm builds all such clusters, but there are too many of them for meaningful cluster analysis in X: first of all, we need ‘‘connected components’’ of the maximal $\alpha$-perfect subset $X\left(\alpha \right)$ in X.

All this exists when X is FMS and the density P is local on it. It is in this situation that the DPS-algorithm operates. It depends on the design of the density P, its level $\alpha$ and the localization radius r: $\mathrm{DPS}=\mathrm{DPS}(P,\alpha ,r)$. DPS operates in two stages: first, it cuts out a subset $X\left(\alpha \right)$ in X (first stage), and then splits it into r-connected components, which it considers to be DPS-clusters in X (second stage).

Despite generally good results and efficient applications [4,5,11,12,13], the DPS-algorithm in its current version has drawbacks: at the first stage, the cutting $X\Rightarrow X\left(\alpha \right)$ is not always thorough and of high quality; at the second stage, the partitioning of $X\left(\alpha \right)$ into r-connectivity components is too small and detailed due to the locality of the radius r. A proper partition of $X\left(\alpha \right)$ must come from the global view of $X\left(\alpha \right)$ induced by the entire space X.

In the present paper, we have made attempts to correct or mitigate these drawbacks: our answers were at the first stage—the iterative cutting scheme ${\mathrm{DPS}}^i\left(X\right)$, at the second—its third stage ${\mathrm{DPS}}_f\left(X\right)$ of connecting the components of the r-connectivity.

The iterations allowed the DPS-algorithm at the first stage to achieve the completeness of its $\mathrm{DPS}\left(X\right)$ result, while maintaining a high level of extremality of cutting.

At the moment, the result ${\mathrm{DPS}}_C\left(X\right)$ of the second stage of the DPS-algorithm is considered its final result. The additional connections of components from ${\mathrm{DPS}}_C\left(X\right)$ proposed in the paper occur in two stages. On the first of them, which has the necessary character, d-clusters are searched in ${\mathrm{DPS}}_C\left(X\right)$. According to the results of the article, their search is constructive. d-clustering is a necessary condition for connecting components from ${\mathrm{DPS}}_C\left(X\right)$ into a single whole. The set of d-clusters $C({\mathrm{DPS}}_C\left(X\right),d)$ serves as the basis for the second stage, which is already sufficient. The main thing here is the expert: his criteria form the final choice of ${\mathrm{DPS}}_f\left(X\right)$ in $C({\mathrm{DPS}}_C\left(X\right),d)$ and at the same time the final partition of ${\mathrm{DPS}}_C\left(X\right)$. There are various formal variants of this choice in DMA. The simplest one of them is given in Section 4.3.1.

DPS-series algorithms are actively applied in many geological and geophysical studies (analysis of seismic catalogs, search for signals on geophysical records, in the problem of radioactive waste disposal, etc.) [1,4,5,7,11,12,13]. It seems that the new version of DPS developed in the present paper will make it possible to improve this application.

The addition of the third stage to the DPS according to the authors makes its architecture sufficient. Further development of DPS-algorithms should take place through their parameters: new constructions of densities and their connection with fuzzy logic will give (and already give [5]) the possibility of deep study of finite metric spaces. Furthermore, the following circumstance is fundamental: in contrast to the Euclidean space, the FMS X is local at each of its points x; as a rule, it is arranged differently; therefore, the parameters $\alpha$, r of the DPS-algorithm, which have a local nature, must depend on x: $r=r\left(x\right)$, $\alpha =\alpha \left(x\right)$. The iterative carving scheme only softens the matter.