Missing value imputation package for high-performance computing

## Project description

# para-impute

The para-impute package is a parallelized missing value imputation Python package specialized for high-performance computing (HPC) environment. Currently, the package includes iterative random forest imputation algorithm, (also known as MissForest in R) [1].

### Installation

```
pip install para-impute
```

## Random Forest Imputer

In order to fully utilize the advantage provided by HPC, the package uses a novel parallelization approach to the missing value imputation task:

- Splitting dataset features into different nodes
- Splitting decision trees of random forest into different cores within each node

Random forest imputer relies on RandomForestRegressor [2] and RandomForestClassifier [3] of Scikit-learn, so it is currently not available to directly take categorical variables. Instead, please use one-hot encoder [5] to transform your dataset. You should also input a list of column indices of categorical variable while fitting missing value datasets (see Methods in API section).

### Pseudocode

```
PROGRAM RFImputer(Xmis)
N <- nrows(Xmis)
P <- ncols(Xmis)
Ximp <- Arrange the columns of Xmis in ascending order of the amount of missing values
Ximp <- Impute each missing values by the mean of all observed values in the same column
For each column C of Ximp
Obsi[C] <- indices of observed values
Misi[C] <- indices of missing values
While not meeting stopping criteria, iterate
Xold <- Copy Ximp
For each column D of Ximp
ObsX <- Ximp[Obsi[D], All columns except D]
ObsY <- Ximp[Obsi[D], D]
MisX <- Ximp[Misi[D], All columns except D]
MisY <- RandomForest(X_train=Obs, Y_train=ObsY, X_test=MisX)
Ximp[Misi[D], D] <- MisY
return Ximp
```

Note: Stopping criteria is defined as follow: when the first time the difference between the dataset of current and previous iteration increases, it stops the iteration and returns the dataset of previous iteration. The metrics for calculating difference are different for numerical and categorical variables.

- For numerical variables, the difference is calculated by Root Mean Square Error (RMSE):

```
diff = sum((Ximp - Xold) ** 2) / sum(Ximp ** 2)
```

- For categorical variables, the difference is calculated by error rate:

```
diff = count(Ximp!=Xold) / #NA
```

For mixed-type dataset (containing both numerical and categorical variables), either one of differences will trigger the stopping criteria.

### Usage

#### Input

An array-like data structure, with missing values represented by either float('nan') or np.nan:

# Example 1 >>> nan = float('nan') >>> Xmis = [[1.0, 2.0, 3.0], [1.5, nan, 2.0], [2.0, 1.0, nan]] # Example 2 >>> nan = np.nan >>> Xmis = np.array([[1.0, 2.0, 3.0], [1.5, nan, 2.0], [2.0, 1.0, nan]])

#### Output

A Numpy Array having the same shape and the same value, except the missing values, as the input:

# Example 1 >>> from pimpute import RFImputer >>> imputer = RFImputer(parallel='local') >>> Ximp = imputer.impute(Xmis) >>> Ximp array([[1. , 2. , 3. ], [1.5 , 1.51, 2. ], [2. , 1. , 2.27]]) # Example 2 >>> Xmis = array([[1. , 2. , 3. , 1. , 0. ], [1.5, nan, 2. , 0. , 1. ], [2. , 1. , nan, nan, nan]]) >>> Ximp = imputer.impute(Xmis, cat_var=[3, 4]) >>> Ximp array([[1. , 2. , 3. , 1. , 0. ], [1.5 , 1.52, 2. , 0. , 1. ], [2. , 1. , 2.45, 0. , 1. ]])

#### SLURM

If you run on 'slurm' mode, make sure you have accessed in machines that have installed SLURM.

>>> from pimpute import RFImputer >>> nan = np.nan >>> Xmis = np.array([[1.0, 2.0, nan], [1.1, 2.2, 3.3], [1.5, nan, 5.0]]) >>> imputer = RFImputer(max_iter=10, n_estimators=100, n_nodes=3, n_cores=10, parallel='slurm') >>> Ximp = imputer.impute(Xmis) iteration 1 Submitted batch job 4836926 Submitted batch job 4836927 Submitted batch job 4836928 iteration 2 Submitted batch job 4836929 Submitted batch job 4836930 Submitted batch job 4836931 iteration 3 Submitted batch job 4836932 Submitted batch job 4836933 Submitted batch job 4836934 >>> Ximp array([[1. , 2. , 3. ], [1.5 , 1.6 , 2. ], [2. , 1. , 2.2]])

## API

```
RFImputer(self, max_iter=10, init_imp='mean', n_estimators=100,
max_depth=None, min_samples_split=2, min_samples_leaf=1,
min_weight_fraction_leaf=0.0, max_features='sqrt',
max_leaf_nodes=None, min_impurity_decrease=0.0,
bootstrap=True, random_state=None, verbose=0,
warm_start=False, class_weight=None, partition=None,
n_cores=1, n_nodes=1, node_features=1, memory=2000,
time='1:00:00', parallel='local'):
Parameters
__________
NOTE: Parameters are consisted by RFImputer parameters, RandomForest
parameters, and SLURM parameters. Since RandomForest is implemented in
scikit-learn, many parameters description will be directly referred to [2],
[3], [4] that also use scikit-learn.
max_iter : int, optional (default=10)
The maximum number of iterations to achieve convergence. [What happens when it passes this? Warning?]
init_imp : string (default='mean')
The mode of initial imputation during the preprocessing:
- If 'mean', each missing value will be imputed with mean/mode value
- If 'zero', each missing value will be imputed with zero
n_estimators : integer, optional (default=100)
The number of trees in the forest.
max_depth : integer or None, optional (default=None)
The maximum depth of the tree. If None, then nodes are expanded until all
leaves are pure or until
all leaves contain less than min_samples_split samples.
min_samples_split : int, float, optional (default=2)
The minimum number of samples required to split an internal node:
- If int, then consider min_samples_split as the minimum number.
- If float, then min_samples_split is a fraction and ceil(
min_samples_split * n_samples) are the minimum number of samples for
each split.
min_samples_leaf : int, float, optional (default=1)
The minimum number of samples required to be at a leaf node. A split point
at any depth will only be considered if it leaves at least
min_samples_leaf training samples in each of the left and right branches.
This may have the effect of
smoothing the model, especially in regression.
- If int, then consider min_samples_leaf as the minimum number.
- If float, then min_samples_leaf is a fraction and ceil(min_samples_leaf
* n_samples) are the minimum number of samples for each node.
min_weight_fraction_leaf : float, optional (default=0.)
The minimum weighted fraction of the sum total of weights (of all the
input samples) required to be at a leaf node. Samples have equal weight
when sample_weight is not provided.
max_features : int, float, string or None, optional (default='sqrt')
The number of features to consider when looking for the best split:
- If int, then consider max_features features at each split.
- If float, then max_features is a fraction and int(max_features *
n_features) features are considered at each split.
- If 'auto', then max_features=sqrt(n_features).
- If 'sqrt', then max_features=sqrt(n_features) (same as “auto”).
- If 'log2', then max_features=log2(n_features).
- If None, then max_features=n_features.
Note: the search for a split does not stop until at least one valid
partition of the node samples is found, even if it requires to effectively
inspect more than max_features features.
max_leaf_nodes : int or None, optional (default=None)
Grow trees with max_leaf_nodes in best-first fashion. Best nodes are
defined as relative reduction in impurity. If None then unlimited number
of leaf nodes.
min_impurity_decrease : float, optional (default=0.)
A node will be split if this split induces a decrease of the impurity
greater than or equal to this value.
The weighted impurity decrease equation is the following:
N_t / N * (impurity - N_t_R / N_t * right_impurity
- N_t_L / N_t * left_impurity)
where N is the total number of samples, N_t is the number of samples at
the current node, N_t_L is the number of samples in the left child, and
N_t_R is the number of samples in the right child.
N, N_t, N_t_R and N_t_L all refer to the weighted sum, if sample_weight is
passed.
bootstrap : boolean, optional (default=True)
Whether bootstrap samples are used when building trees. If False, the
whole datset is used to build each tree.
random_state : int, RandomState instance or None, optional (default=None)
If int, random_state is the seed used by the random number generator; If
RandomState instance, random_state is the random number generator; If
None, the random number generator is the RandomState instance used by
np.random.
verbose : int, optional (default=0)
Controls the verbosity when fitting and predicting.
warm_start : bool, optional (default=False)
When set to True, reuse the solution of the previous call to fit and add
more estimators to the ensemble, otherwise, just fit a whole new forest.
See the Glossary.
class_weight : dict, list of dicts, “balanced”, “balanced_subsample” or None,
optional (default=None)
Weights associated with classes in the form {class_label: weight}. If not
given, all classes are supposed to have weight one. For multi-output
problems, a list of dicts can be provided in the same order as the columns
of y.
Note that for multioutput (including multilabel) weights should be defined
for each class of every column in its own dict. For example, for
four-class multilabel classification weights should be [{0: 1, 1: 1}, {0:
1, 1: 5}, {0: 1, 1: 1}, {0: 1, 1: 1}] instead of [{1:1}, {2:5}, {3:1},
{4:1}].
The “balanced” mode uses the values of y to automatically adjust weights
inversely proportional to class frequencies in the input data as n_samples
/ (n_classes * np.bincount(y))
The “balanced_subsample” mode is the same as “balanced” except that
weights are computed based on the bootstrap sample for every tree grown.
For multi-output, the weights of each column of y will be multiplied.
Note that these weights will be multiplied with sample_weight (passed
through the fit method) if sample_weight is specified.
partition : string, optional (default=None)
SLURM parameter, specify your partition on SLURM. Default is specified by
the administrator of your HPC
n_cores : int, optional (default=1)
The number of cores to process. If parallel == 'local', then n_cores is
exactly the same as n_jobs of Scikit-learn. Setting n_jobs to -1 on local
machine will use all available cores. If parallel = 'slurm', each node
uses n_cores number of cores, and it is no longer available to be set to
-1.
n_nodes : int, optional (default=1)
SLURM parameter, specify how many machines (nodes) to use to process
node_features : int, optional (default=1)
SLURM parameter, specify how many variables to run in each node
concurrently. Set the number as high as possible to minimize the overhead
of parallelization. However, if you set this number too high, it will not
guarantee you will use all n_nodes number of nodes. Recommended number of
this parameter is #features / #n_nodes.
memory : int, optional (default=2000)
SLURM parameter. specify how much memory in term of MB to allocate for
each node.
time : string, optional (default='1:00:00')
SLURM parameter, specify the time limit of your process to survive. The
format should be strictly follow:
- 'minutes'
- 'minutes:seconds'
- 'hours:minutes:seconds'
- 'days-hours'
- 'days-hours:minutes'
- 'days-hours:minutes:seconds'
parallel : string, optional (default='local')
- If 'local', impute on local machine
- If 'slurm', impute in parallel on SLURM machines
Attributes
__________
var_ : list
A list having the same length as the number of variables. Its elements are
1, 0, and 1 for numerical, 0 for categorical
Methods
_______
fit_transform(self, xmis, cat_var=None)：
return the imputed dataset
Parameters
__________
xmis : {array-like}, shape (n_samples, n_features)
Input data, where 'n_samples' is the number of samples and
'n_features' is the number of features.
cat_var : list of ints (default=None)
Specifying the index of columns of categorical variable.
Return
______
ximp : {array_like}, shape (n_samples, n_features)
Acquired after imputing all nan of xmis.
```

## Credits

- ChengEn Tan helped the implementation of parallelization
- Ilias Tagkoupolos as the project advisor

## Reference

- [1] Stekhoven, Daniel J., and Peter Bühlmann. "MissForest—non-parametric missing value imputation for mixed-type data." Bioinformatics 28.1 (2011): 112-118.
- [2] https://scikit-learn.org/stable/modules/generated/sklearn.ensemble.RandomForestRegressor.html#sklearn.ensemble.RandomForestRegressor
- [3] https://scikit-learn.org/stable/modules/generated/sklearn.ensemble.RandomForestClassifier.html#sklearn.ensemble.RandomForestClassifier
- [4] https://github.com/epsilon-machine/missingpy
- [5] https://scikit-learn.org/stable/modules/generated/sklearn.preprocessing.OneHotEncoder.html

## Project details

## Release history Release notifications

## Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Filename, size | File type | Python version | Upload date | Hashes |
---|---|---|---|---|

Filename, size para-impute-1.0.0.tar.gz (16.7 kB) | File type Source | Python version None | Upload date | Hashes View hashes |