## 2 Developed Methodology  
### Shap  
SHAP is an instance-based interpretation method of visualizing and explaining black-box classification or regression models using a game-theoretic solution, Shapley value (\(\varphi\)). The Shapley value is defined as the feature importance in specific instances. The Shapley value of the \(i\)-th feature for a specific sample \(x\) is calculated as (1) and (2) [34; 35].  
\[\varphi_{i}(x)=\frac{1}{n!}\sum_{\mathcal{O}\in\pi(n)}(\Delta(Pr^{i}(\mathcal{ O})\cup\{i\})(x)-\Delta(Pr^{i}(\mathcal{O}))(x)) \tag{1}\]  
\[\Delta(Q)(x)=\sum_{y\in\mathcal{Y}}p(y)(f(\tau(x,y,Q))-f(y)) \tag{2}\]  
In the above formulas, assuming that \(\mathcal{A}\) represents the original feature space, \(\mathcal{Y}\) is a background data set extracted from \(\mathcal{A}\) at random or by clustering algorithms. In this paper, the classical clustering algorithm, k-means (Algorithm 1), is embedded into SHAP to reduce the background data set. \(Q\) is a certain subset of features in a given instance \(x\), and \(\Delta(Q)(x)\) represents its influence. \(f\) is the function of predicting the probability of a category in the basic classifier. \(p\) is the probability of a given sample \(y\in\mathcal{Y}\). \(\tau(x,y,W)=(z_{1},z_{2},...,z_{n})\), where \(z_{i}=x_{i}\) iff \(i\in W\) and \(z_{i}=y_{i}\), otherwise. \(\pi(n)\) represents the set of all permutations of \(n\) elements, and \(Pr^{i}(\mathcal{O})\) represents the set of all features which precede the \(i\)-th feature in permutation \(\mathcal{O}\). Further, the SHAP interpretation results are obtained by using Algorithm 2. Assuming that the prediction time of the basic model is \(T(f(x))\), the time complexity of the algorithm is \(O(K\cdot n\cdot T(f(x))\).  
```
0: dataset \(x=\{x_{1},x_{2},...,x_{n}\},K\)
0:\(c=\{c_{1},c_{2},...,c_{K}\}\) \(c\leftarrow\) select \(K\) samples from \(x\) at random while the termination conditions are not satisfied do for\(k\gets 1\) to \(K\)do \(\mathbb{C}_{k}\leftarrow\{\}\)  for\(i\gets 1\) to \(n\)do \(j\leftarrow\arg\min_{j}d(x_{i},c_{k})\) \(\mathbb{C}_{j}\leftarrow\mathbb{C}_{j}\cup x_{n}\) endfor endfor for\(k\gets 1\) to \(K\)do \(c_{k}\leftarrow\frac{1}{|\mathbb{C}_{k}|}\sum_{x\in\mathbb{C}_{k}}x\) endfor endwhile return\(c\)
```  
**Algorithm 1** k-means algorithm.  
```
0:\(f\): a regression function; \(x\): a given instance; \(K\): the number of background data; \(\mathcal{A}\): a dataset representing feature space.
0:\(\varphi\): Shapley values of features.
1:\(\mathcal{Y}\leftarrow\)K-means(\(\mathcal{A}\), \(K\)) or Random(\(\mathcal{A}\), \(K\))
2:for\(i=0\) to \(n\)do
3:\(\varphi_{i}(x)\gets 0\)
4:for\(k=0\) to \(K\)do
5: select a permutation \(\mathcal{O}\in\pi(n)\) randomly
6:\(y\leftarrow\mathcal{Y}_{k}\)
7:\(x_{1}\leftarrow[\mathcal{A}_{1},...,\mathcal{A}_{i}\) from \(x\) in \(\mathcal{O}]\cup[\mathcal{A}_{i+1},...,\mathcal{A}_{n}\) from \(y\) in \(\mathcal{O}]\)
8:\(x_{2}\leftarrow[\mathcal{A}_{1},...,\mathcal{A}_{i-1}\) from \(x\) in \(\mathcal{O}]\cup[\mathcal{A}_{i},...,\mathcal{A}_{n}\) from \(y\) in \(\mathcal{O}]\)
9:\(\varphi_{i}(x)\leftarrow\varphi_{i}(x)+f(x_{1})-f(x_{2})\)
10:endfor
11:\(\varphi_{i}(x)\leftarrow\frac{\varphi_{i}(x)}{k}\)
12:endfor
```  
**Algorithm 2** SHAP algorithm.  
The Shapley values of features have a welcome nature of implicit normalization as (3), where \(f_{base}\) is the average prediction of all background samples. Thus, the interpretation results can explain how the machine learning model's output is pushed from the base value to the final prediction by each feature's influence.  
\[f(x)=f_{base}+\sum_{i}^{n}\varphi_{i}(x) \tag{3}\]