• Input: Dataset $\mathcal{D}_{train}$, Instance $x$, lenght of explanation $\mathcal{K}$
  • Initialise $\mathcal{Y} \leftarrow {}$
  • Initialise cluster for $i$ /in/ $1,\dots,N$ do
    • $C_i \leftarrow {i}$
  • end
  • Initialise clusters to merge $\mathcal{S} \leftarrow$ for $i$ /in/ $1\dots N$
  • while /no more clusters are available for merging/ do
    • Pick two most similar cluster with minimum distance $d$:
      • $(j,k) \leftarrow \arg\min_{d(j,k)} \in \mathcal{S}$
    • Create new cluster $C_l \leftarrow C_j \bigcup C_k$
    • Mark $j$ and $k$ unavailable to merge
    • if $C_l \neq i$ in $1\dots N$ then
      • Mark $l$ as available, $\mathcal{S} \leftarrow \mathcal{S} \bigcup {l}$
    • end
    • foreach $i \in \mathcal{S}$ do
      • Update similarity matrix by computing distance $d(i, l)$
    • end
  • end
  • while $i$ /in/ $1,\dots,n$ do
    • $d(\mathbf{x}i, \mathbf{x})=\sqrt{(x{i1}-x_1)^2+\dots+(x_{im}-x_m)^2}$
  • end
  • $ind \leftarrow$ Find indices for the $k$ smallest distance $d(\mathbf{x}_i, \mathbf{x})$
  • $\hat{y} \leftarrow$ Get majority label for $x \in ind$
  • $n^s \leftarrow$ Filter $\mathcal{D}_{train}$ based on $\hat{y}$
  • foreach $i$ /in/ $1, \dots, n$ do
    • $\mathcal{Y} \leftarrow $ Pairwise distance of each instance in cluster $n^s$ with the original instance $x$
  • end
  • $\omega \leftarrow$ LinearRegression$(n^s, \mathcal{Y}, \mathcal{K})$
  • return $\omega$