# DPS Clustering: New Results
## 2 Materials and Methods
### DPS-Algorithms
#### 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},\ldots,x_{n}\) in \(A\) with the beginning \(x_{0}=x\), and the end \(x_{n}=y\) and distances \(d(x_{i},x_{i+1})\leq r\), \(i=0,\ldots,n-1\). The \(r\)-connectivity relation is an equivalence splitting the set \(A\) into \(r\)-connectivity components, which, depending on the context, willbe denoted \(cA(k)=c_{r}A(k)\), \(k=1,\ldots,k^{*}=k^{*}(A,r)\). Let us denote their collection by \(C(A)=C_{r}(A)=\{cA=c_{r}A(k)|_{1}^{k^{*}}\}\). Thus:  
\[A=\vee_{cA\in C(A)}cA=\vee_{k=1}^{k^{*}}cA(k), \tag{5}\]  
where the sign \(\vee\) 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)\leq 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}(x)=P_{D_{A}(x,r)}(x) \tag{6}\]  
Definition 4: If the density \(P\)\(r\)-local, then every \(r\)-connected component of the set \(X(\alpha)\) is \(\alpha\)-perfect. Proof: According to (2), for any \(k=1,\ldots,k^{*}\), it is necessary to establish the equality of the component \(c_{r}X(\alpha)(k)\) with the set \(\{x\in X:P_{c_{r}X(\alpha)(k)}(x)\geq\alpha\}\), which we denote by \(c_{r}X(\alpha)(k)\)1. Footnote 1: The inclusion of \(c_{r}X(\alpha)(k)\subseteq\{x\in X:P_{c_{r}X(\alpha)(k)}(x)\geq\alpha\}\). \(x\in c_{r}X(\alpha)(k)\Rightarrow x\in X(\alpha)\Rightarrow P_{X(\alpha)}(x)\geq\alpha\). Furthermore, \(D_{X(\alpha)}(x,r)=D_{c_{r}X(\alpha)(k)}(x,r)\), since \(d(x,c_{r}X(\alpha)(\bar{k}))>r\) for \(\bar{k}\
eq k\). Due to the \(r\)-locality of \(P\)\(P_{c_{r}X(\alpha)(k)}(x)=P_{D_{c_{r}X(\alpha)(k)}(x,r)}(x)=P_{D_{X(\alpha)}(x,r)}( x)=P_{X(\alpha)}(x)\geq\alpha\), \(x\in c_{r}X(\alpha)(k)\)1. Footnote 1: The inclusion of \(c_{r}X(\alpha)(k)\supseteq\{x\in X:P_{c_{r}X(\alpha)(k)}(x)\geq\alpha\}\). First case \((x\
otin c_{r}X(\alpha)(k))\wedge(x\
otin X(\alpha))\). Then, \(P_{c_{r}X(\alpha)(k)}(x)\leq P_{X}(\alpha)(x)<\alpha\Rightarrow x\
otin c_{r}X (\alpha)(k)\)1. Second case \((x\
otin c_{r}X(\alpha)(k))\wedge(x\in X(\alpha))\). Then, \((x\in c_{r}X(\alpha)(\bar{k}))\) and \(d(x,c_{r}X(\alpha)(\bar{k}))>r\), and therefore \(D_{c_{r}X(\alpha)(\bar{k})}(x,r)=\varnothing\). Taking into account the normalization of the density \(P\) and its \(r\)-locality, \(P_{c_{r}X(\alpha)(k)}(x)=0\). Thus, in this case, \(x\
otin c_{r}X(\alpha)(k)\)1. Definition 4: \(DPS\)-algorithm depends on three parameters: radius \(r\), \(r\)-local density \(P\) and level \(\alpha\): \(DPS=DPS(P,\alpha,r)\) and has two stages:  
1. _The first stage of_ \(DPS\)__\(\Leftrightarrow\) _the process of constructing for FMS_ \((X,d)\) _based on the_ \(r\)_-local density_ \(P\) _its_ \(\alpha\)_-envelope_ \(X(\alpha)\)_:_ \[DPS(P,\alpha,r)\Leftrightarrow X\Rightarrow X(\alpha)\]
2. _The second stage of_ \(DPS\)__\(\Leftrightarrow\) _the partitioning of the_ \(\alpha\)_-envelope_ \(X(\alpha)\) _into_ \(r\)_-connected components:_ \[DPS_{c}(P,\alpha,r)\Leftrightarrow X\Rightarrow C(X(\alpha))\subset 2^{2X}.\]  
Further in the text, \(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: 1 st stage \(DPS(P,\alpha,r)\) carves the maximal subset \(X(\alpha)\) dense in the common background from the  
Figure 2: Flowchart of the DPS-algorithm. original space \(X\); 2 nd stage \(\text{DPS}_{c}(P,\alpha,r)\) partitions \(X(\alpha)\) into components of \(r\)-connectivity \(cX(\alpha)\), 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).