Interpretable clustering using unsupervised binary trees

Abstract

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.

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

$$\begin{aligned} var( X_{t_l \cup t_r}(j))&= \gamma var(X_{t_r}(j)) + (1-\gamma ) var(X_{t_r}(j)) \nonumber \\&+\, \gamma (1-\gamma )( \mu _l(j) - \mu _r(j))^2. \end{aligned}$$

(7)

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

$$\begin{aligned} \sup _{a \in \mathbb{R }} \sup _{t \in \mathbb{T }}\vert r_n(t,i,a)-r(t,i,a)\vert \rightarrow 0 \ \ a.s. \end{aligned}$$

(8)

By Lemma 3.1,

$$\begin{aligned} \alpha _t r(t,i,a) = \alpha _{t_l}\alpha _{t_r} \Vert \mu _l(a) - \mu _r(a)\Vert ^2, \end{aligned}$$

(9)

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

$$\begin{aligned} \alpha _{t_r} \int _{t_l} \Vert x \Vert ^2dP(x) + \alpha _{t_l} \int _{t_r} \Vert x \Vert ^2dP(x) - 2 \left\langle \int _{t_l} xdP(x) , \int _{t_r} xdP(x)\right\rangle . \end{aligned}$$

(10)

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

• 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. $\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. $\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

$$\begin{aligned} \lim _{a \rightarrow \infty } \alpha _{t_l}\alpha _{t_r} \Vert \mu _l(a) - \mu _r(a)\Vert ^2 = \lim _{a \rightarrow -\infty } \alpha _{t_l}\alpha _{t_r} \Vert \mu _l(a) - \mu _r(a)\Vert ^2= 0, \end{aligned}$$

(11)

we have that

$$\begin{aligned} \inf {\{argmax_{a \in \mathbb{R }} r_n(t,i,a)\}} \rightarrow \inf {\{argmax_{a \in \mathbb{R }} r(t,i,a)\}} \end{aligned}$$

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

$$\begin{aligned}&\sup _{a \in \mathbb{R }} \vert r_n(t_{nj}, i, a) - r(t_j, i, a) \vert \nonumber \\&\quad \le \sup _{a \in \mathbb{R }} \sup _{t \in \mathbb{T }}\vert r_n(t_{nj}, i, a) - r(t_{nj}, i, a) \vert + \sup _{a \in \mathbb{R }} \vert r(t_{nj}, i, a) - r(t_j, i, a) \vert ,\quad \quad \end{aligned}$$

(12)

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. $\sup _{a \in \mathbb{R }} \vert P(t_{nj})- P(t_j)\vert \rightarrow 0{\quad }a.s.{\quad }j=l,r$

• 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. $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).