# Adaptive Quick Reduct for Feature Drift Detection
## 2 Materials and Methods
### Adaptive QuickReduct  
In order to exploit the idea underlying QuickReduct in an evolving scenario, it is necessary both to detect feature drifts and to change the selected features accordingly. The ideal algorithm should not only add new features that increase the dependency degree of the selected reduct as new data are processed, but also remove the previously selected features whose contribution is no longer relevant. A typical approach to analyze data streams consists in choosing a windowing model and processing data in each windows, with a moderate overlap between consecutive windows. Assuming that a reduct \(R_{i-1}\) is available at time \(t_{i}\) in the window \(W_{i-1}\), the goal is to evaluate whether the features \(f\in R_{i-1}\)  
algorithm, called AdaptiveQuickReduct (AQR from now on) implements exactly this strategy: given a reduct \(R_{i-1}\) calculated in the time window \(W_{i-1}\), the first step iteratively removes all the features \(f\in R_{i-1}\) such that \(\gamma_{R_{i-1}\setminus\{f\}}(D_{W_{i}})>=\gamma_{C_{W_{i}}}(D_{W_{i}})\). The output of this step is a new reduct \(R_{i}\) to be eventually expanded with new features. In particular, let \(F=\{f|\gamma_{R_{i-1}\setminus\{f\}}(D_{W_{i}})>=\gamma_{C_{W_{i}}}(D_{W_{i}})\}\) be the set of features removed from \(R_{i-1}\), the second step consists in trying to add new features \(f\in C_{W_{i}}\setminus F\) to \(R_{i}\) following the QuickReduct schema. Pseudocode for AQR is reported in Algorithm 2, while Algorithm 3 reports a driver program that acts as a detector and shows how AQR can be called with a sliding window, in which parameter \(W\) represents the window size (batch) that moves forward by \(O\) instances at each iteration. ```
1:procedureAdaptiveQuickReduct(C,D,R)
2:\(C\leftarrow\) the set of all conditional features
3:\(D\leftarrow\) the set of decision features
4:\(R\leftarrow\) Reducuted computed at the previous iteration
5:repeat
6:\(T\gets R\)
7:for\(f\in(R)\)do
8:if\(\gamma_{K\setminus\{f\}}(D)>\gamma_{T}(D)\)then
9:\(T\gets R\setminus\{f\}\)
10:\(F\leftarrow\{f\}\)
11:\(R\gets T\)
12:until\(\gamma_{R}(D)==\gamma_{C}(D)\)
13:\(C\gets C\setminus F\)
14:repeat
15:\(T\gets R\)
16:for\(f\in(C\setminus R)\)do
17:if\(\gamma_{K\cup\{f\}}(D)>\gamma_{T}(D)\)then
18:\(T\gets R\bigcup\{f\}\)
19:\(R\gets T\)
20:until\(\gamma_{R}(D)==\gamma_{C}(D)\)
21:returnR
```  
**Algorithm 2** AdaptiveQuickReduct  
Although it is possible to detect gradual or incremental drift considering a thresholding function \(T\), the definition of a continuous relevance score \(S(f)\) would be required, which is not explicitly available in QR as it does not give a weight to the features to be selected. On the contrary, the sudden change that occurs at a precise moment--feature shift--is easily detectable through a qualitative analysis of the output. As stated in Section 2.1, a minimal reduct is a subset of the dataset conditional features that has equal rough dependency degree as the full set of features and such that no strict subset of this reduct exists that has a greater dependency degree. It must be stressed that the variation in dependency degree given by the addition or deletion of a single feature, even though effective, does not guarantee to predict the optimal reduct, but in general a super-reduct (a subsets that has maximal dependency but not the smallest cardinality). This limitation is in common with QR and it is due to their greedy nature, consequence of the unfeasibility of exhaustive search for the optimal reduct [15]. Nonetheless, as proven by the successful application of QR in countless domains, even the sub-optimal reduct is a sufficiently good approximation in most real world application (see for example [16]).