# Adaptive Quick Reduct for Feature Drift Detection
## 2 Materials and Methods
### QuickReduct for Feature Selection  
Let \(U\) be the universe of discourse and \(A\) be a finite set of attributes; let \(I=(U,A)\) be an information system: an _equivalence relation_\(IND(P)\) in \(I\) is the set of objects belonging to \(U\) that are not discernible by attributes in \(P\), defined as follows:  
\[IND(P)=\{(x,y)\in U\times U|\forall a\in P,a(x)=a(y).\} \tag{6}\]  
It can represent any \(P\subseteq A\), where each attribute \(A\) has values in \(V_{a}\), such that \(a:U\to V_{a}\), \(\forall a\in A\).  
Every equivalence relation defines a partition set of \(U\), called \(U/IND(P)\), that splits \(U\) in equivalence classes called \([x]_{P}\)[7]. According to [8], equivalence classes correspond to information granules and can be used to approximate any subset \(X\subseteq U\) through a pair: its _lower approximation_ (Equation (7)) and its upper approximation (Equation (8)).  
\[\underline{P}X=\{x|[x]_{P}\subseteq\ X\} \tag{7}\]  
\[\overline{P}X=\{x|[x]_{P}\bigcap X\
eq\emptyset\} \tag{8}\]  
The _positive region_--given two equivalence relations called \(C\) and \(D\) over \(U\)--is defined as:  
\[POS_{C}(D)=\bigcup_{X\in U/D}\underline{C}X \tag{9}\]and represents the union of the lower approximations of all the equivalence classes defined by \(X\in U/D\). From the definition of the positive region it is possible to derive the _degree of dependency_ of a set of attributes \(D\) on a set of attributes \(C\), called \(\gamma_{C}(D)\in[0,1]\):  
\[\gamma_{C}(D)=\frac{|POS_{C}(D)|}{|U|}. \tag{10}\]  
A reduct \(R\subseteq C\) is the subset of minimal cardinality of the set of conditional attribute \(C\) such that its degree of dependency remains unchanged:  
\[\gamma_{R}(D)=\gamma_{C}(D) \tag{11}\]  
where \(D\subseteq A\) is the set of decision features and \(C\subseteq A\) is the set of conditional attributes.  
A reduct is minimal, meaning that no attribute can be removed from the reduct itself without lowering its dependency degree with the full set of conditional attributes. Most of the feature selection algorithms used in Rough Set theory are based on the definition of reduct and on the efficient construction of the optimal reduct [9; 10; 11; 12].  
The QuickReduct [13] (please see Algorithm 1, called QR from now on) builds the reduct concatenating the attributes with the greatest increase in the dependency degree, up to its maximum in the considered dataset. Being the exploration of all possible feature combinations computationally unfeasible, QR uses a greedy choice: it adds one at a time to the empty set the attributes resulting in the greatest increase in the Rough Set dependency degree until no other attribute can be added. In this way, it is not guaranteed to find the optimal minimum number of features, however it derives a subset sufficiently close to optimal in a reasonable time, resulting in general a good compromise between time and performance to reduce the dataset dimensionality in many real world scenarios [14].  
```
1:procedureQuickReduct(C,D)
2:\(C\leftarrow\) the set of all conditional features
3:\(D\leftarrow\) the set of decision features
4:\(R\leftarrow\emptyset\)
5:repeat
6:\(T\gets R\)
7:for\(f\in(C-R)\)do
8:if\(\gamma_{R\cup\{f\}}(D)>\gamma_{T}(D)\)then
9:\(T\gets R\cup\{f\}\)
10:\(R\gets T\)
11:until\(\gamma_{R}(D)==\gamma_{C}(D)\)
12:returnR
```  
**Algorithm 1** QuickReduct