relieff

Rank importance of predictors using ReliefF or RReliefF algorithm

Syntax

[idx,weights] = relieff(X,y,k)

[idx,weights] = relieff(X,y,k,Name,Value)

Description

[idx,weights] = relieff(X,y,k) ranks predictors using either the ReliefF or RReliefF algorithm with k nearest neighbors. The input matrix X contains predictor variables, and the vector y contains a response vector. The function returns idx, which contains the indices of the most important predictors, and weights, which contains the weights of the predictors.

If y is numeric, relieff performs RReliefF analysis for regression by default. Otherwise, relieff performs ReliefF analysis for classification using k nearest neighbors per class. For more information on ReliefF and RReliefF, see Algorithms.

[idx,weights] = relieff(X,y,k,Name,Value) specifies additional options using one or more name-value pair arguments. For example, 'updates',10 sets the number of observations randomly selected for computing weights to 10.

Examples

Determine Important Predictors

Load the sample data.

load fisheriris

Find the important predictors using 10 nearest neighbors.

[idx,weights] = relieff(meas,species,10)

idx = 1×4

     4     3     1     2

weights = 1×4

    0.1399    0.1226    0.3590    0.3754

idx shows the predictor numbers listed according to their ranking. The fourth predictor is the most important, and the second predictor is the least important. weights gives the weight values in the same order as the predictors. The first predictor has a weight of 0.1399, and the fourth predictor has a weight of 0.3754.

Rank Predictors by Importance

Load the sample data.

load ionosphere

Rank the predictors based on importance using 10 nearest neighbors.

[idx,weights] = relieff(X,Y,10);

Create a bar plot of predictor importance weights.

bar(weights(idx))
xlabel('Predictor rank')
ylabel('Predictor importance weight')

Select the top 5 most important predictors. Find the columns of these predictors in X.

idx(1:5)

ans = 1×5

    24     3     8     5    14

The 24th column of X is the most important predictor of Y.

Determine Important Categorical Predictors

Rank categorical predictors using relieff.

Load the sample data.

load carbig

Convert the categorical predictor variables Mfg, Model, and Origin to numerical values, and combine them into an input matrix. Specify the response variable MPG.

X = [grp2idx(Mfg) grp2idx(Model) grp2idx(Origin)];
y = MPG;

Find the ranks and weights of the predictor variables using 10 nearest neighbors and treating the data in X as categorical.

[idx,weights] = relieff(X,y,10,'categoricalx','on')

idx = 1×3

     2     3     1

weights = 1×3

   -0.0019    0.0501    0.0114

The Model predictor is the most important in predicting MPG. The Mfg variable has a negative weight, indicating it is not a good predictor of MPG.

Input Arguments

X — Predictor data

numeric matrix

Predictor data, specified as a numeric matrix. Each row of X corresponds to one observation, and each column corresponds to one variable.

Data Types: single | double

y — Response data

numeric vector | categorical vector | logical vector | character array | string array | cell array of character vectors

Response data, specified as a numeric vector, categorical vector, logical vector, character array, string array, or cell array of character vectors.

Data Types: single | double | categorical | logical | char | string | cell

k — Number of nearest neighbors

positive integer scalar

Number of nearest neighbors, specified as a positive integer scalar.

Data Types: single | double

Name-Value Pair Arguments

Specify optional comma-separated pairs of Name,Value arguments. Name is the argument name and Value is the corresponding value. Name must appear inside quotes. You can specify several name and value pair arguments in any order as Name1,Value1,...,NameN,ValueN.

Example: relieff(X,y,5,'method','classification','categoricalx','on') specifies 5 nearest neighbors and treats the response variable and predictor data as categorical.

'method' — Method for computing weights

'regression' | 'classification'

Method for computing weights, specified as the comma-separated pair consisting of 'method' and either 'regression' or 'classification'. If y is numeric, 'regression' is the default method. Otherwise, 'classification' is the default.

Example: 'method','classification'

'prior' — Prior probabilities for each class

'empirical' (default) | 'uniform' | numeric vector | structure

Prior probabilities for each class, specified as the comma-separated pair consisting of 'prior' and a value in this table.

Value	Description
'empirical'	The class probabilities are determined from class frequencies in y.
'uniform'	All class probabilities are equal.
numeric vector	One value exists for each distinct group name.
structure	A structure S with two fields: S.group contains the group names as a variable of the same type as y. S.prob contains a vector of corresponding probabilities.

Example: 'prior','uniform'

Data Types: single | double | char | string | struct

'updates' — Number of observations for computing weights

'all' (default) | positive integer scalar

Number of observations to select at random for computing weights, specified as the comma-separated pair consisting of 'updates' and either 'all' or a positive integer scalar. By default, relieff uses all observations.

Example: 'updates',25

Data Types: single | double | char | string

'categoricalx' — Categorical predictors flag

'off' (default) | 'on'

Categorical predictors flag, specified as the comma-separated pair consisting of 'categoricalx' and either 'on' or 'off'. If you specify 'on', then relieff treats all predictors in X as categorical. Otherwise, it treats all predictors in X as numeric. You cannot mix numeric and categorical predictors.

Example: 'categoricalx','on'

'sigma' — Distance scaling factor

numeric positive scalar

Distance scaling factor, specified as the comma-separated pair consisting of 'sigma' and a numeric positive scalar. For observation i, influence on the predictor weight from its nearest neighbor j is multiplied by $$e^{-{(\text{rank}(i,j)/\text{sigma)}}^2}$$. rank(i,j) is the position of the jth observation among the nearest neighbors of the ith observation, sorted by distance. The default is Inf for classification (all nearest neighbors have the same influence) and 50 for regression.

Example: 'sigma',20

Data Types: single | double

Output Arguments

idx — Indices of predictors ordered by predictor importance

numeric vector

Indices of predictors in X ordered by predictor importance, returned as a numeric vector. For example, if idx(3) is 5, then the third most important predictor is the fifth column in X.

Data Types: double

weights — Weights of predictors

numeric vector

Weights of the predictors, returned as a numeric vector. The values in weights have the same order as the predictors in X. weights range from –1 to 1, with large positive weights assigned to important predictors.

Data Types: double

Tips

• Predictor ranks and weights usually depend on k. If you set k to 1, then the estimates can be unreliable for noisy data. If you set k to a value comparable with the number of observations (rows) in X, relieff can fail to find important predictors. You can start with k = 10 and investigate the stability and reliability of relieff ranks and weights for various values of k.

• relieff removes observations with NaN values.

Algorithms

ReliefF

ReliefF finds the weights of predictors in the case where y is a multiclass categorical variable. The algorithm penalizes the predictors that give different values to neighbors of the same class, and rewards predictors that give different values to neighbors of different classes.

ReliefF first sets all predictor weights W_j to 0. Then, the algorithm iteratively selects a random observation x_r, finds the k-nearest observations to x_r for each class, and updates, for each nearest neighbor x_q, all the weights for the predictors F_j as follows:

If x_r and x_q are in the same class,

$$W_j{}^i=W_j{}^{i-1}-\frac{{\Delta }_j(x_r,x_q)}{m}\cdot d_{rq}.$$

If x_r and x_q are in different classes,

$$W_j{}^i=W_j{}^{i-1}+\frac{p_{y_q}}{1-p_{y_r}}\cdot \frac{{\Delta }_j(x_r,x_q)}{m}\cdot d_{rq}.$$

• W_jⁱ is the weight of the predictor F_j at the ith iteration step.

• p_yr is the prior probability of the class to which x_r belongs, and p_yq is the prior probability of the class to which x_q belongs.

• m is the number of iterations specified by 'updates'.

• $${\Delta }_j(x_r,x_q)$$ is the difference in the value of the predictor F_j between observations x_r and x_q. Let x_rj denote the value of the jth predictor for observation x_r, and let x_qj denote the value of the jth predictor for observation x_q.

  • For discrete F_j,

    $${\Delta }_j(x_r,x_q)=\{\begin{array}{cc}0,& x_{rj}=x_{qj}\\ 1,& x_{rj}\ne x_{qj}\end{array}.$$

  • For continuous F_j,

    $${\Delta }_j(x_r,x_q)=\frac{\left|x_{rj}-x_{qj}\right|}{\text{max}(F_j)-\text{min}(F_j)}.$$

• d_rq is a distance function of the form

  $$d_{rq}=\frac{{\tilde{d}}_{rq}}{{\displaystyle \sum _{l=1}^k{\tilde{d}}_{rl}}}.$$

  The distance is subject to the scaling

  $${\tilde{d}}_{rq}=e^{-{(\text{rank}(r,q)/\text{sigma)}}^2}$$

  where rank(r,q) is the position of the qth observation among the nearest neighbors of the rth observation, sorted by distance. k is the number of nearest neighbors, specified by k. You can change the scaling by specifying 'sigma'.

RReliefF

RReliefF works with continuous y. Similar to ReliefF, RReliefF also penalizes the predictors that give different values to neighbors with the same response values, and rewards predictors that give different values to neighbors with different response values. However, RReliefF uses intermediate weights to compute the final predictor weights.

Given two nearest neighbors, assume the following:

• W_dy is the weight of having different values for the response y.

• W_dj is the weight of having different values for the predictor F_j.

• $$W_{dy\wedge dj}$$ is the weight of having different response values and different values for the predictor F_j.

RReliefF first sets the weights W_dy, W_dj, $$W_{dy\wedge dj}$$, and W_j equal to 0. Then, the algorithm iteratively selects a random observation x_r, finds the k-nearest observations to x_r, and updates, for each nearest neighbor x_q, all the intermediate weights as follows:

$$W_{dy}{}^i=W_{dy}{}^{i-1}+{\Delta }_y(x_r,x_q)\cdot d_{rq}.$$

$$W_{dj}{}^i=W_{dj}{}^{i-1}+{\Delta }_j(x_r,x_q)\cdot d_{rq}.$$

$$W_{dy\wedge dj}{}^i=W_{dy\wedge dj}{}^{i-1}+{\Delta }_y(x_r,x_q)\cdot {\Delta }_j(x_r,x_q)\cdot d_{rq}.$$

• The i and i-1 superscripts denote the iteration step number. m is the number of iterations specified by 'updates'.

• $${\Delta }_y(x_r,x_q)$$ is the difference in the value of the continuous response y between observations x_r and x_q. Let y_r denote the value of the response for observation x_r, and let y_q denote the value of the response for observation x_q.

  $${\Delta }_y(x_r,x_q)=\frac{\left|y_r-y_q\right|}{\text{max}(y)-\text{min}(y)}.$$

• The $${\Delta }_j(x_r,x_q)$$ and d_rq functions are the same as for ReliefF.

RReliefF calculates the predictor weights W_j after fully updating all the intermediate weights.

$$W_j=\frac{W_{dy\wedge dj}}{W_{dy}}-\frac{W_{dj}-W_{dy\wedge dj}}{m-W_{dy}}.$$

For more information, see [2].

References

[1] Kononenko, I., E. Simec, and M. Robnik-Sikonja. (1997). “Overcoming the myopia of inductive learning algorithms with RELIEFF.” Retrieved from CiteSeerX: https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.56.4740

[2] Robnik-Sikonja, M., and I. Kononenko. (1997). “An adaptation of Relief for attribute estimation in regression.” Retrieved from CiteSeerX: https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.34.8381

[3] Robnik-Sikonja, M., and I. Kononenko. (2003). “Theoretical and empirical analysis of ReliefF and RReliefF.” Machine Learning, 53, 23–69.