# Location-Aware Deep Interaction Forest for Web Service QoS Prediction
## 3 Proposed Approach
### LDIF Approach
#### 3.2.2 Scan Interact Structure  
Aiming at the problem of data sparsity that is prevalent in service recommendation, it is often effective to consider automatic feature interactions with more fine grains. In the SIS, we interact user features and service features, obtain feature interaction information through scan window sliding and interaction calculation, and adjust the window size adaptively as the dimension grows, thus realizing explicit automatic feature interaction and avoiding complex computation. In addition, unlike the deep model, with the cooperation of the cascade layer, we concatenate the interaction information of each layer into the features of the previous layer, which is used for the scanning interaction calculation of the next layer. For example, the fourth layer can interact with the feature interaction results of the second layer to mine more efficient higher-order feature interactions. The following will take the _two_-dimensional SIS layer as an example to show the structure in detail with Figure 3:  
When the window size of scanning is 2, we define the notation of four numerical features is \(U_{1}\), \(U_{2}\), \(S_{1}\), and \(S_{2}\), which can make up matrix \(A\) as follows. When the second-order and third-order feature interaction information needs to be calculated, the calculation formulas are as follows:  
\[A= \begin{pmatrix}U_{1}&U_{2}\\ S_{1}&S_{2}\end{pmatrix}  \tag{2}\]  
\[A*A^{T}= \begin{pmatrix}U_{1}^{2}+U_{2}^{2}&U_{1}S_{1}+U_{2}S_{2}\\ U_{1}S_{1}+U_{2}S_{2}&S_{1}^{2}+S_{2}^{2}\end{pmatrix}  \tag{3}\]  
\[A*A^{T}*A= \begin{pmatrix}U_{1}^{3}+U_{1}U_{2}^{2}+U_{1}S_{1}^{2}+U_{2}S_{2}S_{1 }&U_{1}^{2}U_{2}+U_{2}^{3}+U_{1}S_{1}S_{2}+U_{2}S_{2}^{2}\\ U_{1}^{2}S_{1}+U_{1}U_{2}S_{2}+S_{1}^{3}+S_{2}^{2}S_{1}&U_{1}U_{2}S_{1}+U_{2}^{ 2}S_{2}+S_{1}^{2}S_{2}+S_{2}^{3}\end{pmatrix}  \tag{4}\]  
Figure 3: Structure of two-dimensional SIS layer. Assuming that the input vector is 18-dimensional, of which 9 dimensional vectors are user features and the other 9 are service features. We think that feature interaction is meaningful only when users and features work together, so it can be seen as 9 \(\times\) 2-dimensional features, representing the features of users and services, respectively. From the above Equations (3) and (4), the four values in the matrix can represent the different combination and its influence, respectively. Therefore, second- and third-order interaction matrices can connect with the original features to fuse feature interaction information. Next, we perform the average sum for the matrix to represent the information in now-order feature interaction. Through this mechanism one can achieve the effect of feature enhancement and the fusion of feature interaction information, as well as controlling the growth rate of feature dimensions. Extending the above situation, the calculation formula for the _n-order_ feature interaction matrix is as follows:  
\[x_{l}=\prod_{i=1}^{l}f(i) \tag{5}\]  
\[f(i)= \begin{cases}x^{T}&\text{ if }i\%2=1\\ x&\text{ if }i\%2=0\end{cases}  \tag{6}\]  
Since the LDIF approach is a layer-by-layer structure composed by dimensional SIS layers with different scanning window sizes, we take the 2-dim SIS layer as an example to illustrate: Assume that the input vector is _18_-dimensional. First, the input vector is divided into _two_ columns. According to the size of the scan window, each sample will be scanned in \(8\) times. Each time can be seen as a combination of local features to represent a sample. Each sample will compute _two_ values to describe second-order and third-order feature interaction information by Equations (3) and (4). So, it will generate _16_-dimensional feature interaction information, and we need to concatenate it with origin feature to fuse information. Until now, the raw input vector has transformed to a 34-dimensional vector. Next, one random forest and one extreme random forest will generate a _two_-dimensional primary prediction value.