# A Technique of Recursive Reliability-Based Missing Data Imputation for Collaborative Filtering
## 4 k-Recursive Reliability-Based Imputation (k-RRI)
### k-RRI
1:\(\mathcal{R}^{\prime}\leftarrow\mathcal{R}\);// initialize the imputed matrix
2:for\(r\gets 1\) until\(k\)do
3: calculate \(\eta_{r}\), \(\theta_{r}\);
4:\(\mathcal{U}_{a}\leftarrow\{u_{a^{\prime}}|\;\eta_{r}<sim^{\prime}(u_{a^{\prime}},\;u_{a})\leq\;\eta_{r-1},\;u_{a^{\prime}}\
eq u_{a}\}\);
5:\(\mathcal{I}_{s}\leftarrow\{i_{s^{\prime}}|\;\theta_{r}<sim^{\prime}(i_{s^{ \prime}},\;i_{s})\leq\theta_{r-1},\;i_{s^{\prime}}\
eq i_{s}\}\);
6:\(\mathcal{N}_{a,s}\leftarrow\{r_{a^{\prime}s^{\prime}}|u_{a^{\prime}}\in \mathcal{U}_{a}\;\vee\;i_{s^{\prime}}\in\mathcal{T}_{s}\}\);
7:for each \(r_{a^{\prime}s^{\prime}}\in\mathcal{N}_{a,s}\)do
8:if\(r_{a^{\prime}s^{\prime}}=\emptyset\)then
9: calculate \(\hat{r}_{a^{\prime}s^{\prime}}\);
10:\(\mathcal{R}^{\prime}(u_{a^{\prime}},\;i_{s^{\prime}})\leftarrow\hat{r}_{a^{ \prime}s^{\prime}}\);
11:endif
12:endfor
13:endfor
```  
**Algorithm 1****k-RRL**  
Example. Figures 1 and 2 show the user and item similarity matrices, respectively, where \(u_{1}\) and \(i_{1}\) are the active user and active item, respectively, which are computed by the similarity measure employed by the k-RRI algorithm. Let the number of k-RRI steps be set at \(k=3\) and the user threshold values in steps 1-3 be \(\eta_{1}=0.3\), \(\eta_{2}=0.2\), and \(\eta_{3}=0.1\), respectively. Then, the set of users \(\mathcal{U}_{1}\) selected in step 1 is \(\{u_{4}\}\) because its similarity with the active user \(u_{1}\) exceeds threshold \(\eta_{1}=0.3\). Similarly, let the item threshold values in steps 1-3 be \(\theta_{1}=0.6\), \(\theta_{2}=0.3\), and \(\theta_{3}=0.1\). Then, the set of the items \(\mathcal{I}_{1}\) selected in step 1 is \(\{i_{5}\}\) because its similarity with the active item \(i_{1}\) exceeds \(\theta_{1}=0.6\). Accordingly, the ratings that \(\{u_{4}\}\) gives to all items and the ratings that \(\{i_{5}\}\) receives from all users become the set of key neighbors \(\mathcal{N}_{1,1}\) in step 1. The missing data to be imputed are the unrated values among the key neighbors (the parts marked in Figure 3). On the other hand, the set of users \(\mathcal{U}_{1}\) selected in step 2 \(is\)\(\{u_{9}\}\), whose similarity with the active user \(u_{1}\) is between threshold \(\eta_{2}=0.2\) and \(\eta_{1}=0.3\), and the set of items \(\mathcal{I}_{1}\) is \(\{i_{10}\}\), whose similarity with the active item \(i_{1}\) is between threshold \(\theta_{2}=0.3\) and \(\theta_{1}=0.6\). Accordingly, the ratings that \(\{u_{9}\}\) gives to all items and the ratings that \(\{i_{10}\}\) receives from all users become the set of key neighbors \(\mathcal{N}_{1,1}\) in step 2. The missing data to be imputed are the unrated values among the key neighbors (the parts marked in Figure 4). Figure 3: An example of missing data imputation of k-RRI. Figure 2: An example of item similarity matrix of k-RRI. Lastly, the set of users \(\mathcal{U}_{1}\) selected in step 3 is \(\varnothing\), whose similarity with the active user \(u_{1}\) is between threshold \(\eta_{3}=0.1\) and \(\eta_{2}=0.2\), and the set of items \(\mathcal{I}_{1}\) is \(\{i_{4}\}\), whose similarity with the active item \(i_{1}\) is between threshold \(\theta_{3}=0.1\) and \(\theta_{2}=0.3\). Accordingly, the ratings that \(\{i_{4}\}\) receives from all users become the set of key neighbors \(\mathcal{N}_{1,1}\) in step 3, and the missing data to be imputed are the unrated values among the key neighbors (the parts marked in Figure 5).