# DLIME

## Algorithm

• 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 \cup 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} \cup \{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} ←$ 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$$