Automated Data-Driven and Stochastic Imputation Method

Abstract

Machine learning algorithms may have difficulty processing datasets with missing values. Identifying and replacing missing values is necessary before modeling the prediction for missing data. However, studies have shown that uniformly compensating for missing values in a dataset is impossible, and no imputation technique fits all datasets. This study presents an Automated and data-driven Stochastic Imputer (ASI). The proposed ASI is based on automated distribution detection and estimation of the imputed value by stochastic sampling with controlled error probability. The significant advantage of this method is the use of a data-driven approximation ratio for the stochastic sampling, which bound the samples to be, at most, one standard deviation from the original distribution. The ASI performance was compared to traditional deterministic and stochastic imputation algorithms over seven datasets. The results showed that ASI succeeded in 61.5% of cases compared to other algorithms, and its performance can be improved by controlling the sampling error probability.

1. Introduction

Currently, most Artificial Intelligence (AI) research and development is conducted in industry and academia, where vast quantities of information are generated daily. Furthermore, developing and deploying machine learning systems requires large amounts of data. Developing AI procedures is challenging since complete datasets (without missing values) are required. It is possible to remove missing values from a dataset or to impute them (e.g., replace them with comparative values), depending on the feature type [1]. There are established rules to decide which strategy to use for different types of missing values. Researchers have found that there is no one way to compensate for missing values in datasets. Also, specific datasets and types of missing data may respond well to specific strategies but not others [2, 3]. Data analysis can be affected by missing data by increasing or decreasing the value of specific categories when there is a large amount of missing data. In particular, missing data could affect machine learning (ML) algorithms and result in inaccurate and biased analysis.

Generally, numeric features are imputed using mean imputation (to avoid outliers and keep the data centralized), median, or mode. For categorical features, a “missing” category is often added, or the most frequently occurring value assigned [4, 5, 6] is assigned. The use of ML algorithms and advanced statistical methods to complete missing values has been added to the conventional methods. KNN imputers [7, 8, 9] are commonly used to find neighbors and calculate values based on feature means. An additional imputation technique is a Multivariate Imputation by Chained Equations (MICE) algorithm [10]. MICE is a robust, informative method that imputes missing data in a dataset through an iterative series of predictive models [11, 12]. When examining more complex models, models with a higher learning capacity can complete missing values. Many deep learning architectures have been created to solve imputation challenges using the latent representation of the data in the hidden layers [13] and a combination of ML techniques [14], autoencoders [15], and multilayer perceptron [16]. In addition to the techniques discussed above, stochastic imputation techniques, such as regression models [17, 18, 19], add random errors to the target value and examine whether they correlate with the independent variable. Extrapolation and interpolation can be used to estimate unknown values by extending a known sequence of values or facts to unknown values [20, 21]. Conversely, non-deck techniques require substituting observations from “similar” units for each missing value [22, 23].

A new field of research is emerging in addition to machine learning techniques: automated machine learning (AutoML). ML problems can be solved more efficiently and effectively with AutoML [24, 25]. It requires search and optimization methods to find the best hyperparameters for a given problem [26]. It is challenging to impute the missing values in each feature, even with automatic methods [27]. This challenge may be due to high anomaly rates or data without patterns. As only some datasets have the same distribution and dependencies, human intervention is necessary to determine the appropriate value to impute.

The main challenge in the imputation process occurs among datasets with noisy distributions and anomalous values [28, 29]. When the distributions are inconsistent and contain many abnormal values, the imputation process becomes a challenge since all the statical measures are biased according to the behavior of the noises [30, 31, 32]. As part of stochastic processes and the use of randomization in algorithms, there is a need to allow a probability of failure. Since randomized decisions can change the entire process, analyzing the probability of the worst case of an algorithm is essential [33]. Moreover, it is useful to know the probability of whether the received answer is incorrect and handle it accordingly [34].

Three inequalities analyze the farthest value the random variable can be taken from its mean: (1) Markov inequality, which bounds the probability by the expected value of the variables [35]; (2) Chebyshev inequality, which bounds the probability by the variance [36, 37]; and (3) Chernoff inequality, which aims to achieve a binomial distribution (i.e., the sum of Bernoulli variables) that bounds the probability by exponential function [38, 39]. With the help of these inequalities, it is possible to develop random algorithms and control the result obtained by analyzing the correctness of the algorithm [40].

At times, complete independence can imply exponentially better bounds. Compared to Chebyshev, which only uses pairwise independence, Chernoff gives a tighter bound for deviation probability since it uses complete independence between the random variables. Although the Chernoff bound requires stronger assumptions, it is generally tighter than Markov and Chebyshev inequalities.

This study presents the Automated Stochastic Imputer (ASI), a new automated data-driven and stochastic method to impute numeric values in a dataset. It is based on the automated detection of distribution and estimation of the imputed value by sampling with controlled error probability. The innovation of this method is the use of a data-driven approximation ratio based on the distribution measures and the determination of the number of samples required for an accurate estimation. Section 2 presents the method, its implementation, correctness, and computational complexity analysis. Section 3 describes the empirical study and a detailed scenario in which the results of the proposed method are compared to the existing imputation algorithm, with the results presented in Section 4. Last, Section 5 discusses the main conclusions and suggestions for future directions.

2. Automated Stochastic Imputer

This section presents and describes the ASI method. First, the definitions and distributions used in this study will be presented, followed by the method and description of its implementation. Last, the correctness of the method and the computational complexity will be detailed.

2.1 Definitions

The following are the definitions and methods employed in this study:

1. Chernoff bound [40] was used to bound the error probability. Let $X_1,\dots ,X_t$ be independent and identically distributed random variables with a range between zero to one, such that for all $1\le i\le t$ it holds that $E\left[X_i\right]=\mu .$ According to Chernoff bound, it holds that for any $0<ϵ<1$, the probability of the sample’s mean average (i.e., $\frac{1}{t}{\sum }_{i=1}^t{X}_i$) to be $ϵ$-far from the distribution mean is:

   $$P\left[\left|\frac{1}{t}\sum _{i=1}^t{X}_i-\mu \right|\ge \mathit{ϵ\mu }\right]\le 2e^{-\frac{\mathit{\mu t}{ϵ}^2}{3}}$$E1

2. Let $\mathbb{D}$ be a distribution, as listed in Appendix A. To determine whether each feature is indeed close enough to $\mathbb{D}$ distribution, a Kolmogorov-Smirnov test is performed [41]. The Kolmogorov-Smirnov test is a general nonparametric method. This test compares the empirical cumulative distribution functions of a sample with a postulated theoretical distribution. The Kolmogorov-Smirnov test is performed for each feature. In this case, the test interpretation is as follows:

H_o: The sample follows a$\mathbb{D}$distribution.

H₁: The sample does not follow a$\mathbb{D}$distribution.

2.2 Algorithm and implementation

Let $F=\left\{F_1,\dots ,F_m\right\}$ be a set of features in dataset $D$ and let $\delta$ be the desired imputer failure probability, where $0<\delta <1$. First, the method is iterated over each feature $f\in F$ and normalizes the values into a range between zero to one by min-max normalization, i.e., each value of $v\in f$ is transformed to:

$$\frac{v-min\left(f\right)}{max\left(f\right)-min\left(f\right)}$$E2

Next, the method estimates the distribution of $f$ using the Kolmogorov-Smirnov test [41]. Let $\mathbb{D}\left(f\right)$ be the estimated distribution with a confidence level of $\alpha$, and let $f_{\mu },f_{\sigma }$ be the feature’s expected value and standard deviation, respectively. The method defines $q$, the number of required samples necessary to estimate missing values, with a probability of $1-\delta$, as:

$$q=⌈-3\left(\frac{f_{\mu }}{f_{\sigma }}\right)ln\left(\frac{\delta }{2}\right)⌉$$E3

Let $V_f$ be a set of missing values in $f$. The method iterates over each $u_i\in V_f$ and samples $q$ independent and identically distributed values from $\mathbb{D}\left(f\right)$, denoted as $x_1,\dots ,x_q$. Last, the method imputes the missing values according to their average.

Automated Stochastic Imputer ($D,\alpha ,\delta$)

1. $F\leftarrow \left\{F_1,\dots ,F_m\right\}$ set of features in $D$

2. For $f\in F$

   • $\mathbb{D}\left(f\right)\leftarrow$ distribution of $f$ with confidence level of $\alpha$

   • $q\leftarrow ⌈-3\left(\frac{f_{\mu }}{f_{{\sigma }^2}}\right)ln\left(\frac{\delta }{2}\right)⌉$

   • $V_f\leftarrow$ set of missing values in $f$

   • For $u_i\in V_f$:

     1. Sample $x_1,\dots ,x_q$ from $\mathbb{D}\left(f\right)$

     2. $u_i\leftarrow \frac{1}{q}\sum _{j=1}^q{x}_j$

3. Return D

2.3 Correctness

Let $D$ be a dataset consisting of $m$ features, denoted as $F=\left\{F_1,\dots ,F_m\right\}$. Initially, the method is iterated over the feature values and normalized by min-max normalization. For each value of $f\in F$, let $v\in f$be transformed to:

$$\frac{v-min\left(f\right)}{max\left(f\right)-min\left(f\right)}$$E4

Therefore, the dataset is normalized into a range between zero and one, preserving the original data distribution. For $v_a,v_b\in f$, such that $v_a\le v_b$, it holds that:

$$v_a-min\left(f\right)\le v_b-min\left(f\right)$$E5

$$\frac{v_a-min\left(f\right)}{max\left(f\right)-min\left(f\right)}\le \frac{v_b-min\left(f\right)}{max\left(f\right)-min\left(f\right).}$$E6

Let $\mathbb{D}\left(f\right)$ be the detected distribution acquired by the Kolmogorov-Smirnov test with a confidence level of $\alpha$, and let $x_1,\dots ,x_q\sim \mathbb{D}\left(f\right)$ be the independent and identical distributed random variables, such that $\forall 1\le i\le q:E\left[x_i\right]={\mu }_x$ and $V\left[x_i\right]={\sigma }_x^2$. The average of all samples, denoted as $\overline{X}$, is defined as:

$$\overline{X}=\frac{1}{q}\sum _{i=1}^q{x}_i$$E7

Let $\mu ,{\sigma }^2$ be the expected value and the variance of $\overline{X}$, respectively. The method uses $\overline{X}$ as a single imputed value. By the linearity of expectation, it holds that the expected value of $\overline{X}$ is:

$$\mu =E\left[\overline{X}\right]=E\left[\frac{1}{q}\sum _{i=1}^q{x}_i\right]=\frac{1}{q}E\left[\sum _{i=1}^q{x}_i\right]=\frac{q·E\left[x_i\right]}{q}={\mu }_x$$E8

Given that all $x_i$ are independently and identically distributed, it holds that:

$$\forall i\ne j:\mathit{Var}\left[x_i+x_j\right]=\mathit{Var}\left[x_i\right]+\mathit{Var}\left[x_j\right]$$E9

$${\sigma }^2=\mathit{Var}\left[\overline{X}\right]=\mathit{Var}\left[\frac{1}{q}\sum _{i=1}^q{x}_i\right]=\frac{1}{q^2}\sum _{i=1}^q\mathit{Var}\left[x_i\right]=\frac{q·\mathit{Var}\left[x_i\right]}{q^2}=\frac{{\sigma }_x^2}{q}$$E10

The probability error of each sample to be $ϵ$-far from the expected value of the feature can be bound by Chernoff inequality:

$$P\left[\left|\frac{1}{q}\sum _{i=1}^t{X}_i-\mu \right|\ge \mathit{ϵ\mu }\right]\le 2e^{-\frac{\mathit{\mu q}{ϵ}^2}{3}}$$E11

Let $ϵ=\frac{{\sigma }_x}{{\mu }_x}$ be the approximation factor. By bounding the failure probability with $\delta$, a lower bound will be received for the number of samples required:

$$P\left[\left|\frac{1}{q}\sum _{i=1}^t{X}_i-\mu \right|\ge \left(\frac{{\sigma }_x}{{\mu }_x}\right){\mu }_x\right]\le 2e^{-\frac{q·{\mu }_x{\left(\frac{{\sigma }_x}{{\mu }_x}\right)}^2}{3}}<\delta$$E12

Thus, the probability of $\overline{X}$ to be $ϵ$-far from the expected value is equal to its probability to be the distance of, at most, one standard deviation:

$$P\left[\left|\frac{1}{q}\sum _{i=1}^t{X}_i-\mu \right|\ge \left(\frac{{\sigma }_x}{{\mu }_x}\right){\mu }_x\right]=P\left[\left|\frac{1}{q}\sum _{i=1}^t{X}_i-\mu \right|\ge {\sigma }_x\right]\le 2e^{-\frac{q·{\mu }_x{\left(\frac{{\sigma }_x}{{\mu }_x}\right)}^2}{3}}<\delta$$E13

Applying algebraic simplification:

$$q>-\frac{3{\mu }_{x}ln\left(\frac{\delta }{2}\right)}{{\sigma }_x^2}=-\frac{3{\mu }_x}{{\sigma }_x^2}ln\left(\frac{\delta }{2}\right)=-3\left(\frac{{\mu }_x}{{\sigma }_x^2}\right)ln\left(\frac{\delta }{2}\right)$$E14

Since all the dataset distributions are normalized into the range [0,1], its expected value and standard deviation are non-negative values. Given that $0<\delta <1$, the number of samples (i.e., $q$) is a positive number:

$$0<\delta <1\Rightarrow ln\left(\frac{\delta }{2}\right)<0$$E15

$$q>-3\left(\frac{{\mu }_x}{{\sigma }_x^2}\right)ln\left(\frac{\delta }{2}\right)>0$$E16

Therefore, it can be concluded that the total number of samples required to estimate an imputed value depends on the ratio between the expectation and the distribution variance.

Last, for a more accurate analysis of the imputed values, the following is the proof that all values will be typically distributed around the feature mean: Let $V_f=\left(m_1,\dots ,m_M\right)$ be a set of M missing values in feature $f$. For all $1\le i\le q$, it holds that $x_i\sim \mathbb{D}\left(f\right)$, and by the imputation technique:

$$\forall 1\le j\le M:m_j=\frac{1}{q}\sum _{i=1}^q{x}_i$$E17

As long as $M\leftarrow \infty$, by the central limit theorem, the imputed values will be normally distributed:

$$\overline{M}=\frac{1}{M}\sum _{j=1}^M{m}_i\sim N\left({\mu }_x,\frac{{\sigma }_x^2}{M}\right)$$E18

2.4 Computational complexity

Let $m$ be the number of features in a dataset with $n$ records. For each feature with at least one missing value, the method iterates over the missing values. Therefore, the maximum number of such features is $m$. The upper bound of missing values in each feature is $n$. Let $q$ be the number of samples required to estimate the missing value of each iteration. Thus, sampling and averaging their results require $2q$ operations, and the total complexity time is:

$$O\left(m·n·\left(2q\right)\right)\approx O\left(\mathit{mnq}\right)$$E19

In a standard dataset, there are fewer features and records, i.e., $m\le n$, and the complexity running time can be bound by:

$$O\left(\mathit{mnq}\right)\approx O\left(n^{2}q\right)$$E20

3. Empirical study

3.1 Data sources

Seven datasets were compared to examine the ASI method:

1. Fetal health [42]—a medical dataset that aims to prevent child and maternal mortality. The dataset consists of 2126 observations over 21 features and a target variable with three values: normal, suspect, or pathological.

2. Students’ academic success [43]—this dataset contains information about students with different undergraduate degrees from higher education institutions. It includes information on 4424 students’ enrollment and academic performance over 36 features. The target variable has three options: graduate, dropout, or enrolled.

3. Heart failure [44]—a dataset with a total of 299 patients who experienced heart failure. It contains 12 clinical features and a Boolean target variable representing whether the patient had heart failure.

4. Diabetes [45]—a dataset of 768 diabetic and non-diabetic women. It consists of six medical features, two demographic variables and a Boolean target variable.

5. Haberman’s survival [46]—a dataset collected from 1958 to 1970 that includes details on 306 survivors after breast cancer surgery. The dataset and study were conducted at the University of Chicago’s Billings Hospital.

6. Breast cancer [47]—a dataset with a total of 30 features extracted from digitized images of diagnosed breast cancer of 568 patients. The target variable indicates whether the “mass” diagnosis was benign or malignant.

7. Bank [48]—over 45,210 observations of direct marketing campaigns by Portuguese banks are included in the dataset, including seven numerical (continuous) and nine categorical features. The Boolean target variable indicates whether the client subscribed to a term deposit or not.

3.2 Experiment procedure

For each dataset described in Section 3.1, the following parameters were defined and used:

1. At the beginning of each experiment, 25% of the data were randomly chosen, removed, and stored as a version of the original dataset to compare the imputation techniques.

2. For the distribution estimation using the Kolmogorov-Smirnov test, a total of 100 samples with a significance level of $\alpha =0.05$ were used.

3. The results of the proposed ASI method were compared to the existing algorithms implemented in scikit-learn [49] as follows:

   1. KNN imputer—imputation for completing missing values using nearest neighbors’ algorithm.

   2. Iterative imputer—multivariate imputation by chained equations (MICE) [10]. As this imputer has stochastic phases, a random state was set equal to zero in all runs presented in this study.

4. For each comparison, the values $\delta =0.1,0.05,0.01$ were examined for the probability of failure in estimation.

3.3 Use case: the heart failure dataset

To simplify the demonstration, the heart failure dataset, consisting of 12 features over 299 observations, was chosen. The feature names were denoted as $F_i$ for all $1\le i\le 12$. A broader comparison, including higher-dimensional datasets, can be found in Section 4. For the scenario demonstration, $56$ arbitrary values were randomly removed ($\approx 25\%$) and selected from 5 arbitrary features. Their value was then stored to compare to the proposed method. Table 1 presents the initial number of missing values for each feature and the automated distribution detected by the Kolmogorov-Smirnov test.

Feature	Missing values	Expectation	Standard deviation	Distribution
F1	15	0.438	0.497	Normal
F4	10	38.059	11.725	Exponential
F5	10	0.416	0.494	Exponential
F6	11	1.372	0.995	Gamma
F8	13	129.272	78.065	Beta

Table 1.

Number of missing values in each feature and its detected distribution.

Once the distributions were detected, the method calculated the number of samples required for each feature (i.e., $q$) by the ratio between its expected value and variance. Table 2 compares the values of $q$ and the performance of the ASI method, the KNN imputer, and the MICE imputer. Since the proposed method input an upper bound on the probability of failure (i.e., $\delta$), between $\delta =0.1,0.05,0.01$ was compared. As the probability of error was smaller, the number of samples required to estimate the missing value increased, and the performance of the ASI method improved. For example, feature 5 for probability 0.1 yielded 40% success; 50% success was obtained for probability 0.05, and when the probability of error was bounded by 1% (i.e., 0.01), it increased to 60% success compared to the other algorithms.

Feature	$q$	ASI	KNN	MICE
$\mathit{\delta }\mathit{=}\mathbf{0.1}$
F1	8	11 (73%)	1 (7%)	3 (20%)
F4	8	5 (50%)	2 (20%)	3 (30%)
F5	30	4 (40%)	4 (40%)	2 (20%)
F6	13	7 (64%)	1 (9%)	3 (27%)
F8	15	5 (38%)	3 (24%)	5 (38%)
$\mathit{\delta }\mathit{=}\mathbf{0.05}$
F1	10	12 (80%)	1 (7%)	2 (13%)
F4	10	6 (60%)	2 (20%)	2 (20%)
F5	36	5 (50%)	3 (30%)	2 (20%)
F6	16	7 (64%)	2 (18%)	2 (18%)
F8	19	6 (46%)	3 (23%)	4 (31%)
$\mathit{\delta }\mathit{=}\mathbf{0.01}$
F1	15	12 (80%)	1 (7%)	2 (13%)
F4	14	7 (70%)	1 (10%)	2 (20%)
F5	52	6 (60%)	2 (20%)	2 (20%)
F6	22	7 (64%)	2 (18%)	2 (18%)
F8	27	10 (77%)	1 (8%)	2 (15%)

Table 2.

A comparison between the performance of the three imputation algorithms.

Notes. The data is represented as A(B), where A is the count of successes, and B is their percentages. $q$ is the number of samples required for ASI.

For each compared delta (i.e., the probability of wrong estimation), the percentage of total successes of each imputation algorithm was calculated. The results are presented in Figure 1. The smaller the probability of error, the more samples from the distribution were required to estimate the imputed value. Accordingly, the performance of the ASI algorithm increased. For a 10% chance of wrong estimation, the proposed method succeeded in 54% of the cases, compared to 27% of MICE and 19% of KNN. When the chance of error was only 1%, the proposed method succeeded in 71% of cases, representing a significant increase compared to KNN’s 12%.

Figure 1.

Performance of three imputation algorithms compared by failure probability.

4. Results

To illustrate the ASI method, seven datasets (for details, see Section 3.1) were compared with the parameters defined in Section 3.2. For each dataset, the four algorithms were evaluated, and their performances were compared. First, the comparison results and analysis will be described. Then, the sensitivity analysis of the proposed method will be presented. Table 3 presents the total missing value for each dataset and the success percentages for each imputer.

Dataset	Missing values	ASI	KNN	MICE
Fetal health	425	210 (49%)	98 (23%)	117 (28%)
Students	94	49 (52%)	27 (29%)	18 (19%)
Diabetes	152	84 (55%)	42 (28%)	26 (17%)
Heart failure	59	42 (71%)	7 (12%)	10 (17%)
Haberman survival	26	20 (77%)	1 (4%)	5 (19%)
Cancer	113	78 (69%)	16 (14%)	19 (17%)
Bank	13,276	7687 (58%)	2276 (17%)	3313 (25%)

Table 3.

Performance of the three imputation algorithms compared by dataset.

Notes. The data is represented as A(B), where A is the count of successes, and B is their percentages. The comparison used $\delta =0.05$ for the ASI.

The ASI method achieved the highest success rates for all seven tested datasets compared to the KNN and MICE imputers. An extreme case was demonstrated in the Haberman survival dataset, for which a 77% success rate was recorded for the proposed method (i.e., 20 correct answers out of 26). Upon further analysis, this dataset consisted of discrete value features. Therefore, the suitability of the proposed method for discrete versus continuous values should be further examined in future studies.

To examine the error distributions, the errors obtained for each algorithm were calculated by subtracting the original value from the imputed value. These errors were then averaged for each dataset. Since this comparison was between the average values (and not distributions), polynomial interpolation was performed [50]. The results are shown in Figure 2.

Figure 2.

Polynomial interpolation of success rates of the three compared algorithms.

Two conclusions can be drawn from Figure 2. First, there is a high level of agreement between the three algorithms; that is, the ASI algorithm behaved similarly (distributive) to the KNN and MICE algorithms. Second, the ASI algorithm presented a low percentage of all the errors examined compared to the others. However, the ASI algorithm was probabilistic and dependent on input parameters that controlled the probability of failure. Thus, further analysis and comparison of different probabilities is required.

4.1 Sensitivity analysis

This section compares the performance of the ASI algorithm regarding different values of failure probabilities. The proposed algorithm was evaluated using each dataset with probabilities ranging from 0.1 to 0.9 with jumps of 0.1. Then, the percentage of successes the algorithm made was calculated and compared to the actual value. The results are shown in Table 4. Since the goal was to examine the algorithm’s behavior and compare the success percentages, polynomial interpolation was performed [50], as presented in Figure 3.

Dataset	$\delta$
	0.1	0.2	0.3	0.4	0.5	0.6	0.7	0.8	0.9
Fetal health	35.4	34.2	32.8	32.5	33.7	32.1	33.2	31.6	28.3
Students	40.2	37.1	40.1	39.1	37.2	42.3	37.1	40.2	39.4
Diabetes	38.2	36.9	35.9	35.3	33.6	34.4	38.2	39.6	30.3
Heart failure	43.1	42.7	46.5	41.3	42.1	39.6	39.1	39.4	39.9
Haberman survival	70.1	85.2	77.3	78.4	75.2	75.1	71.6	69.6	63.9
Cancer	74.3	75.2	73.8	73.4	74.1	71.6	70.4	70.9	67.2
Bank	49.8	47.4	46.1	44.6	42.6	41.6	40.3	40.8	40.2

Table 4.

Performance of the ASI algorithm, compared by probability of failure.

Figure 3.

A comparison between success rates of ASI over different probabilities.

In the sensitivity analysis of the ASI algorithm, it can be seen that each dataset behaved similarly for different probabilities. This conclusion indicates the consistency of the proposed method. It can also be concluded that noisier results were obtained for extreme probabilities (low and high) due to more substantial constraints on the method’s inputs (e.g., probabilities 0.9 and 0.2). One non-intuitive result was a probability of failure of 0.1, whose values appeared to be “outliers” from the rule. This result might be due to the randomness of the algorithm since, for each probability, the sampled data changed according to the method. However, this specific result was unusual because the other probabilities agreed on the general behavior of the proposed algorithm.

5. Discussion and conclusions

This study proposed a new automated data-driven and stochastic imputation method, ASI, to complete missing values in a dataset. The ASI is based on automated distribution detection and estimation of the imputed value by sampling with controlled error probability. This study’s innovation was the use of a data-driven approximation ratio based on the distribution measures and determination of the number of samples required for an accurate estimation. Thus, the imputer successfully bound the distance between the imputed value and the original expectation by, at most, one standard deviation. The following are the main conclusions:

1. The ASI method succeeded in imputing the missing values in 61.5% of the cases, compared to the deterministic KNN and stochastic MICE algorithms. According to the analysis, there was a slightly difference in the performance of the proposed algorithm on features with discrete and continuous values.

2. The number of samples required to estimate missing values increased as the error probability decreased. Thus, more samples yielded better estimation performance, although it increased the runtime complexity. For example, in the heart failure dataset (Section 3.3), the first feature required eight samples to yield a success rate of 73%, while the use of 15 samples improved the success rate to 80%.

3. A sensitivity analysis of the ASI algorithm on different probabilities found consistency in its performance on seven datasets. It can be concluded that the correctness of the proposed method is tight and presents an accurate imputation of missing values in a given distribution.

Results are known to be affected by the data quality, especially when considering data imputation and stochastic models. Failures may result from a lack of data or incorrect adjustment of the parameters, as mentioned in this method. Future studies should address two main issues presented in this study. First, the performance of ASI over continuous and discrete random variables should be explored, which may be done by examining different values for the parameters or an extension of the distribution exploration. Second, this study assumed a confidence level of $\alpha =0.05$ for distribution testing using the Kolmogorov-Smirnov test. Different significance levels may yield different results of distributions and, thus, the ASI algorithm’s results.

Conflict of interest

The authors declare no conflict of interest.

Appendix

See Table A1.

Type	Distribution	Parameters	Expectation	Variance
Discrete	Uniform	$U\left(a,b\right)$	$\frac{a+b}{2}$	$\frac{{\left(b-a+1\right)}^2-1}{12}$
	Binomial	$\mathit{Bin}\left(n,p\right)$	$\mathit{np}$	$\mathit{np}\left(1-p\right)$
	Geometric	$G\left(p\right)$	$\frac{1}{p}$	$\frac{1-p}{p^2}$
	Hypergeometric	$\mathit{HG}\left(N,D,n\right)$	$\frac{\mathit{nD}}{N}$	$\frac{\mathit{nD}}{N}\left(1-\frac{D}{N}\right)\left(\frac{N-n}{N-1}\right)$
	Poisson	$\mathit{\text{Pois}}\left(\lambda \right)$	$\lambda$	$\lambda$
	Negative Binomial	$\mathit{NB}\left(n,p\right)$	$\frac{n\left(1-p\right)}{p}$	$\frac{n\left(1-p\right)}{p^2}$
Continuous	Uniform	$U_c\left(a,b\right)$	$\frac{a+b}{2}$	$\frac{{\left(b-a\right)}^2}{12}$
	Exponential	$exp\left(\lambda \right)$	$\frac{1}{\lambda }$	$\frac{1}{{\lambda }^2}$
	Normal	$N\left(\mu ,{\sigma }^2\right)$	$\mu$	${\sigma }^2$
	Gamma	$\mathit{\text{Gamma}}\left(n,\lambda \right)$	$\frac{n}{\lambda }$	$\frac{1}{{\lambda }^2}$
	Beta	$\mathit{\text{Beta}}\left(a,b\right)$	$\frac{a}{a+b}$	$\frac{\mathit{ab}}{\left(a+b+1\right){\left(a+b\right)}^2}$
	Chi2	${\chi }^2\left(k\right)$	$k$	$2k$
	F	$F\left(m,n\right)$	$\frac{n}{n-2}$	$\frac{2n^2\left(m+n-2\right)}{m{\left(n-2\right)}^2\left(n-4\right)}$
	T	$T\left(m\right)$	$0$	$\frac{m}{m-2}$

Table A1.

List of distributions to determine the feature.