Interpretable clustering using unsupervised binary trees

We herein introduce a new method of interpretable clustering that uses unsupervised binary trees. It is a three-stage procedure, the first stage of which entails a series of recursive binary splits to reduce the heterogeneity of the data within the new subsamples. During the second stage (pruning), consideration is given to whether adjacent nodes can be aggregated. Finally, during the third stage (joining), similar clusters are joined together, even if they do not share the same parent originally. Consistency results are obtained, and the procedure is used on simulated and real data sets.

Authors and Affiliations

1. Universidad de San Andrés and Universidad de la República, Vito Dumas 284, 1644 Victoria, Buenos Aires, Argentina

   Ricardo Fraiman

2. Département de Mathématiques, Université de la Méditerrannée Faculté des Sciences de Luminy, 163 Avenue de Luminy, 13288 , Marseille Cedex 09, France

   Badih Ghattas

3. Universidad de San Andrés and Conicet, Vito Dumas 284, 1644 Victoria, Buenos Aires, Argentina

   Marcela Svarc

Corresponding author

Correspondence to Marcela Svarc.

Appendix

1.1 Proof of Lemma 3.1

We first observe that because \(t_l\) and \(t_r\) are disjoint, \(\mathbb{E }(X_{t_l \cup t_r}) = \gamma \mu _l + (1 - \gamma ) \mu _r\), where \(\gamma = P(\mathbf{X} \in t_l \vert \mathbf{X} \in t_l \cup t_r)\). Given that \(j = 1, \ldots , p\), we use \( M^{(j)}_{2i} = \int _{t_i} x(j)^2 dF(x),{\quad }i=l,r\), where \(F\) stands for the distribution function of the vector \(\mathbf{X}\).

It then follows that \(\mathbb{E }(X_{t_l \cup t_r}(j)^2) = \gamma M^{(j)}_{2l}+ (1 - \gamma )M^{(j)}_{2r}\) , and therefore that

By summing the terms in \(j\) we get the desired result.

1.2 Proof of Theorem 3.1

Let \(\mathbb{T }\) be the family of polygons in \( \mathbb{R }^p\) with faces orthogonal to the axes, and fix \(i \in \{1, \ldots , p\}\) and \(t \in \mathbb{T }\). For \(a \in \mathbb{R }\) denote by \(t_l = \{ x \in t: x(i) \le a\}\) and \(t_r = t \setminus t_l\). We define \(r(t,i,a) = R(t) - R(t_l) - R(t_r)\) and \(r_n(t,i,a) = R_n(t) - R_n(t_l) - R_n(t_r)\), the corresponding empirical version.

We start showing the uniform convergence

By Lemma 3.1,

where \(\alpha _A = P(\mathbf{X} \in A)\) and \( \mu _j(a) = \mathbb{E }(X_{t_j}),{\quad }j=l,r\). Then, the pairs \((i_{jn}, a_{jn})\) and \((i_{j}, a_{j})\) are the arguments that maximise the right-hand side of equation (9) with respect to the measures \(P_n\) and \(P\) respectively. We observe that the right-hand side of equation (9) equals

In order to prove Eq. (8) it is sufficient to show that:

1. 1.

   \(\sup _{a \in \mathbb{R }} \sup _{t \in \mathbb{T }}\vert P_n(t_j) - P(t_j)\vert \rightarrow 0 \, \, a.s. \, \, j=l,r\)

2. 2.

   \(\begin{array}{l} \sup _{a \in \mathbb{R }}\sup _{t \in \mathbb{T }}\vert \int _{t_j} \Vert x \Vert ^2 dP_n(x) - \int _{t_j} \Vert x \Vert ^2 dP(x) \vert \rightarrow 0\\ a.s. \, \, j=l,r\\ \end{array}\)

3. 3.

   \(\begin{array}{l} sup_{a \in \mathbb{R }}\sup _{t \in \mathbb{T }} \vert \int _{t_j}\ x (i) dP_n(x) - \int _{t_j} x(i) dP(x) \vert \rightarrow 0\\ a.s. \, \, j=l,r, i=1, \ldots , p. \end{array}\)

Since \(\mathbb{T }\) is a Vapnik–Chervonenkis class, we have that (1) holds. Now observe that the conditions for uniform convergence over families of sets still hold if we are dealing with signed finite measures. Therefore if we consider the finite measure \( \Vert x \Vert ^2dP(x)\) and the finite signed measure given by \(x(i)dP(x)\) we also have that (2) and (3) both hold.

Since

we have that

a.s.

In the first step of the algorithm, \(t=\mathbb{R }^p\) and we obtain \( i_{n1} = i_1\) for \(n\) large enough and \(a_{n1} \rightarrow a_1\) a.s. In the next step, we observe that the empirical procedure begins to work with \(t_{nl}\) and \(t_{nr}\), while the population algorithm will do so with \(t_{l}\) and \(t_{r}\). However, we have that

for \(j=l,r\).

We already know that the first term on the right hand side of equation(12) converges to zero almost surely. In order to show that the second term also converges to zero, it is sufficient to show that

1. 1.

   \( \sup _{a \in \mathbb{R }} \vert P(t_{nj})- P(t_j)\vert \rightarrow 0{\quad }a.s.{\quad }j=l,r\)

2. 2.

   \( \sup _{a \in \mathbb{R }}\vert \int _{t_j} \Vert x \Vert ^2 dP(x) - \int _{t_{nj} } \Vert x \Vert ^2 dP(x) \vert \rightarrow 0{\quad }a.s.{\quad }j=l,r\)

3. 3.

   \( sup_{a \in \mathbb{R }} \vert \int _{t_j}\ x (i) dP(x) - \int _{t_{nj}} x(i) dP(x) \vert \rightarrow 0{\quad }a.s.{\quad }j=l,r, \ i=1, \ldots , p,\)

which follows from the assumption that \(\Vert x \Vert ^2 f(x)\) is bounded. This concludes the proof since \(minsize/n \rightarrow \tau \).

1.3 Proof of Theorem 3.2

We need to show that we have consistency in both steps of the backward algorithm.

(i) Convergence of the pruning step. Let \(\{t^*_{1n}, \ldots , t^*_{mn}\}\) be the output of the forward algorithm. The pruning step partition of the algorithm converges to the corresponding population version from

• the conclusions of Theorem 3.1.

• the fact that the random variables \(W_{lr} \quad \tilde{d}_l, \tilde{d}_r\) are positive.

• the uniform convergence of the empirical quantile function to its population version.

• the Lebesgue dominated convergence theorem.

The proof of convergence of the joining step is mainly the same as that for (i).

Reprints and permissions