# Key Quality Indicators Prediction for Web Browsing with Embedded Filter Feature Selection
## 3 Feature Weighted ML-kNN for KQI Prediction
### Improved ML-ReliefF Feature Selection  
In order to improve the validity of the features in the training dataset for KQI prediction, feature selection is conducted after the preprocessing. As the most well-known filter FS algorithm, ReliefF is widely used in solving multi-classification and regression problem [12]. Many scholars have done a lot of work on the optimization and application of ReliefF [13; 14]. As more and more application scenarios of machine learning are multi-label classification problems, the algorithm needs to be extended to deal with multi-label data. A multi-label ReliefF (ML-ReliefF) is proposed in [15]. The algorithm assumes that the categories of multi-labeled data are co-occurring, and that the contributions of all the labels are equal. Satisfactory experimental results are observed on several public datasets by optimizing the update strategy of the feature weights. Finally, a subset of the features whose total weight is larger than a predefined threshold, or simply the top N features with the largest weight are selected for subsequent learning procedure. Another multi-label ReliefF algorithm, namely, ReliefF for multi-label (RF-ML), is proposed in [16]. The algorithm considers the interaction among features. It defines a function that characterizes the dissimilarity of the label vector between samples (such as Hamming distance), and finds the nearest neighbor by means of the multi-label dissimilarity function. It is found that ML-ReliefF actually converts the multi-label problem into a series of single-label problems, which does not consider similarity and the interaction of label vectors in the samples. For most scenarios however, the assumption of absolute independency among the labels is difficult to satisfy. In view of the above-mentioned problems, a new algorithm, namely, unified multi-label ReliefF (UML-ReliefF), is proposed based on ML-ReliefF. Specifically, for a dataset with \(q\) labels, \(k\) nearest neighbor samples with \(t\) (\(t\) = 0-\(q\)) identical labels are sequentially searched according to Hamming distance in the label space and Euclidean distance in the feature space. During the iteration of the feature weight vector, the weights are updated according to the Hamming distance of label vectors between the sample and each of its nearest neighbors. The closer the label vectors between the two samples are, the heavier the punishment is for the difference in the feature space, or vice versa. The pseudo code of the UML-ReliefF is illustrated in Algorithm 1. ```
\(W\) = UML-ReliefF(\(D^{\prime}\), \(n\), \(k\)) Input: training set \(D^{\prime}=\{x_{1}\sim x_{m}\}\), no. of iterations \(n\), no. of neighbors \(k\) Output: Feature Weight Vector \(W\)
1. Initialize \(W\) = \((w_{1},w_{2},\ldots,w_{p})\); //\(p\) refers to the dimension of feature set. 2.for\(i=1\) to \(n\)do
3. Select randomly a sample from \(D^{\prime}\) as \(R_{i}\), \(\mathit{class}(R_{i})=\mathbf{h}=(h_{1},h_{2},\ldots,h_{q})\) //\(q\) is the dimension of label set. 4.for\(t=0\) to \(q\)do
5. Search \(k\) nearest neighbors with \(t\) same labels, and denote as \(\mathbf{H}_{j}^{t}(R_{i})\), \(j=1\sim k\);
6. endfor
7.for\(l=1\) to \(p\)do
8. Update each weight according to Equation (9):
9. \(W[l]\mathbf{W}[l]+\frac{1}{\alpha k}\sum\limits_{l=0}^{q}(q-2t)\mathit{diff}\left(l,R_{i},\mathbf{H}_{j}^{t}(R_{i})\right)\) (9) //\(\mathit{diff}\left(l,R_{i},\mathbf{H}_{j}^{t}(C)\right)\) is the distance between \(R_{i}\) and \(\mathbf{H}_{j}^{t}(R_{i})\) on the \(l\)-th feature. 10. endfor
11.endfor
```  
**Algorithm 1**Pseudo code of unified multi-label ReliefF (UML-ReliefF) algorithm. Since the feature weights reflect the similarity between the two samples in the nearest neighbor searching, is it feasible to weight the distance with the instantaneous feature weights during neighbor searching? This may speed up the convergence. Specifically, the Euclidean distance can be modified to be a normalized weighted one in the search for \(\mathbf{H}_{j}^{t}(\mathbf{R}_{i})\).