An extensive analysis of the interaction between missing data types, imputation methods, and supervised classifiers

An extensive analysis of the interaction between missing data types, imputation methods, and supervised classifiers Unai Garciarena∗ , Roberto Santana∗ Faculty of Informatics, University of the Basque Country. P Manuel Lardizabal, 1 - 20018 Donostia-San Sebasti´an, Gipuzkoa, Spain. Abstract When data-mining real-world data, we often find ourselves facing observations that have no value recorded for some attributes. This can be caused by several phenomenon, such as a machine’s incapability to record certain characteristics or a person refusing to answer a question in a poll. Depending on that motivation, values gone missing may follow one kind of pattern or another, or describe no regularity at all. One approach to palliate the effect of missing data on machine learning tasks is to replace the missing observations. Imputation algorithms attempt to calculate a value for a missing gap, using information around it, i.e., the attribute and/or the value of the observation. While several imputation methods have been proposed in the literature, few works have addressed the question of the relationship between the type of missing data, the choice of the imputation method, and the effectiveness of classification algorithms that used the imputed data. In this paper we address the relationship among these three factors. By constructing a benchmark of hundreds of databases containing different types of missing data, and applying several imputation methods and classification algorithms, we empirically show that a interaction between imputation methods and supervised classification can be deduced. Besides, differences in terms of classification performance for the same imputation method ∗Corresponding author Email addresses: [email protected] (Unai Garciarena), [email protected] (Roberto Santana) This is the accepted manuscript of the article that appeared in final form in Expert Systems with Applications 89 : 52-65 (2017), which has been published in final form at https://doi.org/10.1016/j.eswa.2017.07.026. © 2017 Elsevier under CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/) in different missing data patterns have been found. This points to the convenience of considering the combined choice of the imputation method and the classifier algorithm according to the missing data type. Keywords: missing data, imputation methods, supervised classifiers, machine learning 1. Introduction Missing values are ubiquitous in almost every type of real-world datasets. They can be particularly detrimental for certain applications of the datasets, especially when the distribution of the missing data (MD) is not uniform and a possible mechanism that could explain the lost values is unknown. Perhaps the most used among the non-trivial alternatives to deal with MD are imputation methods (IMs). These methods replace the missing values by estimates that can be taken from the database (DB), derived from statistics of known values (e.g., the mean of a given variable), or obtained using more sophisticated algorithms. There is consensus on the importance of the application of IMs, especially when DBs with MD are used as a basis for learning supervised classifiers. However, the choice of the IM, and its impact on the classifier performance can be very dependent on the MD type. For example, an improper choice of the IM can bias the learned classifier, producing a low classification quality on test data. When the problem of supervised classification is considered, these three elements are strongly intertwined. In this paper we analyze this relationship by investigating problems with different types of MD, addressed using a set of IMs with the final goal of supervised classification by means of different types of classifiers. Our aim is to determine to what extent there is a relationship between the choice of the IM and the precision of the classifiers when considering DBs that exhibit different types of MD. Previous work (Batista & Monard, 2003; Luengo et al., 2012) has analyzed the relationship between the IMs used for treating MD and classifiers. Batista & Monard (2003) evaluated four IMs for two different classifiers concluding that 2 the choice of the IM influences the performance of the classifiers. A more indepth study on the relationship between IMs and classifiers was presented by Luengo et al. (2012). Authors conducted an extensive evaluation of classifiers and IMs on real-world DBs and concluded that the choice of the IM should indeed be conditioned on the type of classification method used. In this paper we go beyond the analysis of the relationship between IMs and classification algorithms, and consider as another factor the particular characteristics of the MD. We hypothesize that the three previously mentioned factors can influence the classification results and should be considered in their interaction. We investigate this hypothesis by devising procedures that generate DBs with different types of MD, and using them as a benchmark, we evaluate the effect of the MD type and the IMs on the performance provided by the classifier. Another contribution of our work is the simultaneous use of real-world DBs, which are used as a basis to construct the benchmark, with an artificially generated MD type which is introduced in the original DB. Following this strategy, we can control the characteristics of the MD and evaluate the effect on the other factors analyzed. In our investigation we also evaluate an extensive number of classifiers, including many of those investigated in previous work and some other more recent classification approaches. The paper is organized as follows. In the next section, some essential background on the main concepts covered in the paper is given. Related work, emphasizing the connection with our proposal, is discussed in Section 3. Section 4 gives a formal presentation of the methods used to generate the different types of MD. This section also describes the databases selected to evaluate the relationships between the methods and algorithms. Sections 5 and 6 respectively present the imputation and classification methods investigated. In Section 7 we describe the experimental framework, the results of the experiments, and discuss some of our findings. Section 8 concludes the paper and presents some lines for future research. 3 2. Background 2.1. Missing data types Many different reasons can cause missing data (MD) in real-world databases. Identifying any pattern in the MD values is a key aspect at the time of conceiving methods to deal with the missing observations. In particular, the type of MD can directly impact the quality of the predictions of the classification methods applied to the data. Therefore, several works have been devoted to characterize the types of MD, proposing methods to detect these types and suggesting algorithms for imputation. In this section we review the most common accepted classes of MD and their expected effect on the behavior of supervised classification techniques (Batista & Monard, 2003; Gelman & Hill, 2006; Hernndez-Pereira et al., 2015; Blomberg & Ruiz, 2013; Luengo et al., 2012): •Missing Completely At Random (MCAR): When the database’s measurement failures occur randomly, there is no specific pattern to be identified. The impact of MCAR on a classification algorithm will depend on the MD distribution over the data. The more uniform the distribution of the MD is, the less bias is expected to be introduced in the database. •Missing At Random (MAR): MD is cataloged as MAR when a pattern can be identified, i.e., we can find a common factor in all the observations with missing values. For example, we find that when a certain variable (with no MD) takes extreme values for an observation, two other variables tend to be missing for that same observation. •Missing Not At Random (MNAR): This MD type is similar to MAR. However, in this case the values causing others to be missing are not known, this can have two origins: –Missingness depending on unobserved Variables (MuOV): One of the reasons these values are not known can be that simply they were not observed. 4 –Missingness depending on its Value Itself (MIV): An element can be missing depending on its value itself. This could happen when a variable takes a value out of its representation range. In general, it is not possible to identify the MCAR type of MD since in real databases there is no way to track the cause of this MD. MCAR can be caused by a huge variety of reasons, from data loss during an information transference, to a person’s refusal to provide personal data in a poll, etc. As stated above, assuming that the missing values are uniformly distributed, the dataset will not experience a considerable loss of information. As long as the amount of missing values is not significant, even discarding observations containing MD will not necessarily have an impact on posterior classification. However, even if the amount of information lost regarding missing observations may be small1, IM quality could be as important as in other MD type. The MAR kind of MD is not as common as MCAR, but it is easier to infer its origin by studying other variables of the dataset. For example, in a situation in which people are asked about their habits and health, some information about sedentary lifestyle might be available. However, while some subjects may be open to share information about their weight, other subjects (more likely those with an overweight condition) might be more reluctant to disclose this type of information. This example illustrates situations in which a cause for MAR can be inferred from an analysis of the characteristics of the database. MAR type of MD can be a potential source of problems for the performance offered by the classification algorithms. Since in this case there is an underlying reason for the MD, it is likely that observations containing MD will be similar to each other and will be tagged in the same class. This could lead to an unbalanced database that will potentially affect the classification. In this case, discarding data is not an advisable option, and the use of IMs is a requirement. Finally, MNAR presents a considerably more difficult situation. Following 1Johnny, I’m not sure if this sentence is clear and correct 5 the previous example, the task would become much more tedious if we had not asked about other medical and lifestyle parameters (MuOV). Another scenario needs to be addressed when an individual is ashamed and refuses to disclose information about the amount of money he or she spends on drugs. This variable most likely depends only on itself. In this second case we would have (MIV). These two situations are the most problematic ones, since it can be as harmful as MAR for the data, but it can be easily misidentified as MCAR, as a result of the impossibility to identify a pattern in the unobserved variables. 2.2. Imputation methods There are two main ways of handling MD. Ignoring observations with missing data is generally a good choice when the cardinal of missing values is relatively small and the MD is homogeneously distributed. Nevertheless, when these measurement failures are concentrated in a single variable, or when ignoring them would suppose a big loss of information, we consider techniques to fill the gaps. This is essentially what imputation does. Several strategies have been proposed for this purpose and they can exhibit important differences in terms of complexity, and output quality (Brownstone & Valletta, 2001; Liu & Brown, 2013; Batista & Monard, 2003; Lakshminarayan et al., 1999). Section 5 will present a number of imputation methods relevant for our work. 2.3. Classification problems and supervised classification algorithms Classification is the task of learning a target function that maps an attribute collection to a predefined class. Algorithms that solve this problem could be defined as processes that generalize patterns from a set of given observations. These operations, which are able to both predict and describe data, can be divided into two major branches: Supervised and Unsupervised Classification (SC and UC). In a supervised classification problem (Tan et al., 2006; Hilbert & Lpez, 2011), a set of (training) data is given and, for each case in the training set, the associated class (or label) is known. The classification problem consists 6 of using the information the training data contains to infer or predict the class of new cases that are not labeled. We focus on the analysis of SC algorithms and how their behavior is impacted by MD and imputation methods. This supervised classification paradigm can be very sensitive to the MD problem. We expect that if a considerable amount of the data is missing for a certain variable in a certain class, the classifier may struggle to offer an acceptable behavior when tagging an observation with that mentioned class. However, the way in which different types of MD influence the behavior of the classifiers has not been previously studied in detail. We notice that, considering the classification scenario, MD can be present in the training data, for which we know the class and also in the test data, for which information about the label is unknown. In this paper, we consider these two situations as the same scenario, i.e., we do not consider methods that use class information at the time of implementing the imputation algorithm. In Section 6, we present the classifiers that will be used in the experimental part of this paper. 3. Related work Not many recent studies have researched the interaction between missing data configurations, MD handling methods, and supervised classification algorithms from this approach. In the following paragraphs, some papers that have investigated this question are reviewed. 3.1. General data The most exhaustive investigation on the joint behavior of IMs and classification algorithms is the paper by Luengo et al. (2012). They performed an analysis with 23 classification algorithms (grouped in three classes) combined with 14 ways of dealing with MD. They selected 21 DBs, all of them containing natural missing values, ranging from 0.06 to 21.82 percent from the total values in the tables. Since they have no knowledge about the MD distribution, they 7 assumed it followed a MAR pattern. This is a fundamental difference with the approach we follow in this paper, since our focus is on the influence of the MD type and therefore the methods we propose to create the testing benchmark are completely different and more sophisticated to the one proposed in Luengo et al. (2012). However, the experiments conducted by the authors proved the positive effect of imputing data, and found evidence of the relation between the classifier type and the IM. The same authors developed the work presented in (Luengo et al., 2010), which focuses on the Radial Basis Function Network (RBFN) classifier, pointing out the improvement of the classifier results when combined with an Event Covering imputer, proposed by Wong & Chiu (1987). Batista & Monard (2003) studied the effects of imputation over the C4.5 and CN2 classifiers. They chose four databases from which 3 had no MD, and inserted varying percentages of missing values (10, 20, 30, 40, 50 and 60%) and then proceeded to classify them. The observations containing MD were removed, as they represented only about 2% of the total for that DB. The DBs with missing values were classified with no imputation (note that C4.5 and CN2 have their own way of working with MD), mean/mode imputation, and K-nearest neighbors imputation (KNNI) (with k= 10). 10-NNI showed better performance than the other simple treatments, but the experiments found limitations in the way MD was inserted, since only some of all the attributes chosen were affected. Also, only two basic IMs were considered in Batista & Monard (2003). Acuna & Rodriguez (2004) evaluated the effect of three methods for dealing with MD on the misclassification error rate. They used the mean, median and KNNI IMs, and also investigated the results for case deletion. Then they tested the results with two classifiers, Linear Discriminant Analysis (LDA) and Knearest neighbors (KNN). This work adopted 12 datasets, 4 of which contained natural MD. These four DBs were pretreated in order to make their starting points similar by applying the IM. The results achieved by Acu˜na and Rodr´ıguez showed that the IM effect on accuracy has a higher dependence on the problem rather than on the classification algorithm. These results point in the direction 8 of the question we investigate in this paper, since one of the features characterizing a given DB is the MD type. However, the work presented by Acuna & Rodriguez (2004) did not address this question explicitly and the number of IMs and classification methods was limited in comparison to the study we present here. Farhangfar et al. (2008) examined the impact of performing MD imputation as a preprocessing step for posterior classification. They combined different versions of four imputation methods (Hot Deck, Na¨ıve Bayes Polynomial multiple Regression and Mean) with six classifiers (Ripper 2, C4.5, RBFN, Support Vector Machine (SVM), KNN and na¨ıve Bayes). They selected 15 DBs and considered 5, 10, 20, 30, 40 and 50% of MCAR-type MD in their experiments. They concluded that the improvement in the accuracies obtained from the dataset with MD and the imputed one had no relation with the percentage of MD. Also, differences in the improvement were shown for different IM-classification algorithm combinations, which led them to conclude that no universally best IM exists. The paper finally resolves that imputation is beneficial for machine learning tasks, overall. Hruschka Jr et al. (2007) introduced two IMs based on Bayesian Networks and contrasted them with four other classic methods, namely, ExpectationMaximization, Data Augmentation, Decision Trees, and Mean/Mode. Four datasets were used as a benchmark, which combined natural and artificial missing values introduced in the experiments. Four classifiers were considered in the experiments. This work concluded that IM obtaining closer values to original data (comparing imputations in artificially generated MD to values originally in those cells) did not necessarily produce better results when classifying. Song et al. (2008) performed an analysis similar to the one presented by Batista & Monard (2003), in which the effect of KNN-imputation over C4.5 classification was investigated. However, in their paper they considered three MD types (MCAR, MAR and NMAR). Their conclusions regarding IM-C4.5 coincide with those found by Batista & Monard (2003) , and also state that the MD mechanism influences the classifying task. Nevertheless, an in-depth 9 4.1.3. MIV This algorithm is very similar to the one used to create the MAR pattern of MD, but instead of generating variables that will lose their values depending on the values of a causative variable, it will be the causative itself which loses variables. The pseudocode is shown in Algorithm 3 Input: data: Database mdp: MD percentage nV: number of variables losing their values Output:Database with mdp% generated MD begin x = numObservations(data) y = numVariables(data) causatives = random([0,y], nV) for i∈[0,length(causatives)] do aux = data[:,causatives[i]] for j∈[0, x ·y·mdp/100//nV] do observations[j] = minIndex(aux) aux[observation[j]]=maxInt end for j∈[0,length(observations)] do data[observations[j], causative] = “NaN” end return (data) end end Algorithm 3: MIV generating algorithm. 4.1.4. MuOV This algorithm is also quite similar to the one proposed for generating MAR MD type, but in this case the causative variable is unobserved. Therefore, 16 the observations that will have missing values will be chosen randomly. The pseudocode is shown in Algorithm 4. Input: data: Database mdp: MD percentage nV: number of variables losing their values Output:Database with mdp% generated MD begin x = numObservations(data) y = numVariables(data) MDVariables = random([0,y], nV) for i∈[0, x ·y·mdp/100)//nV] do observations[i] = random([0,x]) end for i∈[0,length(observations)] do for j∈[0, length(MDVariables)] do data[observations[i], MDVariables[j] = “NaN” end end return (data) end Algorithm 4: MuOV generating algorithm. As previously indicated, this algorithm follows the same structure, but since in this case the causative variables are unknown, the observations to lose their values will be chosen randomly. Some of our methods to introduce the missing data seek to simulate the different types of MD which depend on visible or hidden dependencies between the variables in the DB. Therefore, some of the algorithms select the observations where MD will be introduced based on the values of the causative variable. We notice that other criteria to define the MD types have been proposed in the literature. In particular, the MD patterns could be defined in terms of the percentage of MD within a single observation (Deb & Liew, 2016). 17 4.2. Description of the databases investigated We have selected a set of 10 datasets from the UCI Machine Learning Repository (Lichman, 2013) built in completely different contexts in order to achieve results which are as generic as possible, avoiding biasing the IMs and classifiers with a specific behavior from the data. We have databases observing diverse natural aspects (Forest, Biodeg, Climate, Leaf), medical matter measurements (Diabetic, BUPA, Thoracic), credit denial/approval (German), vehicle dimension analysis (Vehicle) and image pixel interpretation (Segmentation). Table 1 contains a structural description of the DBs. The first three columns (Categorical, Integer and Real) provide information about the type of the elements contained in the DB. The following two columns, (N. Variables, N. Cases) refer to the number of measurements for each observation (including the class tag) and the amount of observations the DB contains. Then, the index each DB has been assigned in order to simplify future references to distinct datasets. The last two columns refer exclusively to the class of the data. n is the number of classes, while Hnrepresents the normalized entropy, computed as: Hn(p) = −P i pi·logb(pi) logb(n) where piis the probability of class i,bis the logarithm base (in our case we used ebase, the natural logarithm), and nis the number of classes in the data. The result of this procedure produces a number between 0 and 1, which may be interpreted as the nearer to 1, the more uncertainty we find in a class, and thus, the better distributed is. And the nearer to 0, the more unbalanced towards one certain class it is. This coefficient is normalized by the number of classes. We used this measure in order to equilibrate measurements between binary and multi-class databases. 18 Database Categ. Int. Real N.Feats. N.Cases DB Index n Hn Biodeg 7 3 3 41 1055 5 2 0.92 BUPA 3 3 3 7 345 4 2 0.98 Climate 7 7 3 18 540 8 2 0.42 Diabetic 7 3 3 20 1151 7 2 1 Forest 3 3 3 27 326 6 4 0.91 German 3 3 7 20 1000 3 2 0.88 Leaf 7 7 3 16 340 1 30 1 Segmentation 7 7 3 19 2310 9 7 1 Thoracic 3 3 7 17 470 10 2 0.61 Vehicle 7 3 7 18 946 2 4 1 Table 1: Description of the original datasets used to generate the benchmark. 5. Imputation methods IMs differ in the class of DBs they can be applied to, their computational complexity, and the sophistication of the methods used to replace the MD. There are straightforward techniques to replace missing observations (Batista & Monard, 2003; Lakshminarayan et al., 1999; Gelman & Hill, 2006), that simply copy values from other observations (using similarity as a criterion, for example). Other more elaborated imputation algorithms use Parameter Estimation (PE) (Yuan, 2010; Honaker & King, 2010) to replace the missing values from the available data. The first class of methods require less computational time and their results could be sufficiently good for some DBs. When these simpler strategies do not produce results that fit the expectations, PE can presumably provide more accurate results. In this paper we have selected 8 imputation methods, including some of the most frequently used and more sophisticated approaches: The initial three methods considered are Mean-Mode,Median and Most Frequent Value imputation. These methods have self-explanatory names, as they calculate the statistics and simply ascribe them to gaps. Last Value Carried Forward imputation is also self-explanatory. This function searches the variable for the last available value, and uses it as its guess for 19 the missing value. Interpolation’s working system can also be easily deduced from its name, but this method considers a parameter that may change its complexity, thus affecting its computational cost. The interpolation method calculates a function that fits both the previous and later values of a missing value stretch and fills it using the function. Hot Deck imputation can also have a high computational cost, since it depends on the number of observations and variables the DB has. This method computes the distance (e.g., euclidean distance) between an observation with one (or more) missing value(s) and replicates the value for that certain variable in the nearest observation. Iterative Imputation basically imputes the same missing values multiple times. The common operation of these methods is to make initial simple guesses for missing values (e.g., mean imputation) and reimputates the same missing values using other (more complex, usually) methods. Once all the variables have been reimputed, the cycle is repeated. An iteration limit or a tolerance threshold could be set as a halting condition. Multiple Imputation also belongs to the computationally complex method spectrum. This strategy duplicates the DB mtimes and imputes them separately. Submethods used to perform imputation on these replicas may or may not be different strategies. Next, one of two strategies can be followed. The first one applies the analysis algorithm (Supervised Classification in our case) and then combines their results. The second option first performs the combination step, forming one single DB again, being able this way to know the variance of the imputed values. Then the analysis is applied. The recommended mvalue used for this procedure has (and still is) increased as computation capacity has risen, being the classical advice 3 ≤m≤5, having reached to 20 ≤m≤100 by some authors, i.e., Van Buuren (2012). This work has used two imputation methods that perform Multiple Imputation; MICE (Multivariate Imputation by Chained Equations) (Buuren & Groothuis-Oudshoorn, 2011) and Amelia (Honaker et al., 2011). 20 We notice that some of the IMs considered here are more appropriate for a particular type of data (e.g., the interpolation method is conceived for data with a temporal component). However, at the time of applying the IMs we do not take into account the characteristics of the data. We expect that if a given IM is not appropriate for one DB, this fact will be translated in the result obtained by the classifier for that particular DB. 6. Supervised classification methods In this section we describe the classification methods evaluated in the paper. Details about the implementation are described in Section 7.1.2. When no details about the parameters used by the classifiers are provided, it is assumed that they were applied with their default parameters in the used implementations. We use the following classifiers: 1. Regularized logistic regression with norm l1 (Ll1) (Yu et al., 2011) 2. Regularized logistic regression with norm l2 (Ll2) (Yu et al., 2011) 3. Linear discriminant analysis (LDA) (Least Squares) (Fisher, 1936) 4. Quadratic discriminant analysis (QDA) (reg param = 0.01) (Friedman, 1989) 5. Deep Neural Network (hidden layers = 2, optimizer = Adagrad, activation = ReLu, max steps = 20,000) (Bishop, 1995; Gron, 2017) (More details available in Section 6.1) 6. Support Vector Machine (kernel = linear, max iter= 5000000) (Joachims, 1998) 7. Support Vector Machine (kernel = Polynomic, degree = 3, gamma = 0.01, max iter= 5000000) (Joachims, 1998) 8. Radial Basis Function (gamma = 0.1, max iter = 5000000) (Park & Sandberg, 1991) 9. Gaussian Na¨ıve Bayes classifier (GNB) (Manning et al., 2008) 10. Gradient boosting (GB) (max depth = 11) (Friedman, 2001) with number of trees nt= 100 and maximum depth of trees maxd= 11 21 11. Random forests (RF) (Breiman, 2001) with nt= 100 and maxd= 11 12. Decision tree (DT) (Olshen et al., 1984) maxd=n 13. k-nearest neighbor classifier (1NN) algorithm (Aha et al., 1991) with k= 1 and using the Euclidean distance 14. k-nearest neighbor classifier (3NN) algorithm (Aha et al., 1991) with k= 3 and using the Euclidean distance Some of these classifiers consider interactions between the features, some others incorporate regularization techniques, or take into account similarity metrics between the data. According to Luengo et al. (2012), classifiers 13 and 14 are lazy classifiers, while 11 and 12 are tagged in the decision tree class. The rest, 1-10, are model constructing classifiers. 6.1. Deep Neural Network Classifier The fifth classifier used in this experimentation is based on an artificial neural network architecture, a multi layer perceptron (MLP), to be more specific. These classifiers are composed of neurons, which are nothing more than simple functions that receive multiple inputs and produce one output. These neurons are organized in layers, which are connected with each other, in a sequential manner. Two neurons in one layer cannot be connected while all the nodes in two adjacent layers are fully interconnected via varying weights. Finally, the input layer must have the same amount of neurons as variables a database has, while the output layer should have as many as classes in the data, following a softmax architecture. The values produced by these neurons are to be treated as the probabilities of an observation introduced in the input layer belonging to a certain class. The training process consists on recomputing the previously mentioned weights based on the knowledge of a desired output given a certain input (Pal & Mitra, 1992; Bishop, 1995; Gron, 2017). In our case, the structure was composed of two hidden layers with 2n 3and n 3nodes respectively, being nthe amount of variables in a database. 22 6.2. F-1 Score To measure the results of the classification methods, we use the F-1 score. This metric is computed as follows: F1= 2 ·1 1 r+1 p where rstands for recall, which is the result of dividing the labels correctly predicted as true by all the actual true labels. And prepresents precision, computed by dividing the correctly predicted true labels by all the labels predicted as true (including the wrongly predicted ones): r=T rueP ositive Originaltruelabels , p =T rueP ositive Alllabelspredictedastrue As it can be seen, this metric is only intended for binary classification problems, while our benchmark contains multi-label DBs. For non-binary classification problems, we have computed the weighted average of the metric for each class, separately. More details about the implementation of this method are provided at the end of Section 7.1.2. 7. Experiments In this section we conduct an in-depth empirical investigation of the relationship among the MD types, IMs and classification methods. Among the questions we address in this section are the following: 1. Do different MD types produce different effects on the prediction quality of the classifiers? 2. What is the overall behavior of the IMs when all DBs, MD types, and classification methods are considered? 3. Is it possible to identify any joint effect of IMs and classifiers on the score achieved for different DBs? Does this potential effect depend on the type of MD? 23 7.1. Experimental Framework To study the MD-IM/PE-SC relation, ten non-temporal databases from the UCI Machine Learning Repository (Lichman, 2013) without missing values were chosen. Using these DBs, we applied the methods proposed for inserting different types of MD as presented in Section 4. The next step consisted of imputing the missing values using eight different IM. Finally, the benchmark of new DBs with the inserted MD was used to apply the different classifiers, which were validated using stratified 5-fold cross validation. To guarantee a representative sample of the possible DBs with different MD types, we created, for each of the 10 DBs, five different variants, using a 5-fold stratified methodology. We thus separated the training and testing parts at the beginning of the algorithms. We did this in order to limit the information used by the imputer to the training and testing sets separately and to totally control the percentage of missing data present in each partition. For each one of these 5 variants produced by the 5-fold stratified strategy and each of the 4 MD types, 30 different DBs containing MD were created. This was done using Algorithms 1-4. Therefore, we obtained 10DBs ×5folds ×4MDtypes×30instances = 6,000DBs with missing values. From now on, when we refer to the “benchmark” we refer to this set of 6,000 DBs, 1,500 for each of the four MD types. Due to the stochastic nature of the algorithms used to generate the MD, all DBs were different. Even if they come from only 10 original DBs, the methods used to insert missing values make each DB unique. Again, note that MD was separately introduced on both training and testing partitions, in order to guarantee that the percentage of missingness is exactly the same. In the next phase we focus on studying the behavior of the IMs and classifiers on the benchmark. The eight different IMs described in Section 5 were applied to the benchmark, to obtain a total of 6,000DB ×8IM = 48,000 different, complete DBs. Finally, all these databases were classified by applying the 14 classification algorithms described in Section 6, obtaining a final output of 48,000DBs/5folds ×14Classifiers = 134,400 distinct scores. Figure 1 captures this complete process for one single DB. 24 Figure 1: General scheme describing the experimental framework used to evaluate the influence of MD types, IMs, and classification algorithms on the classifier performance. 25 IMs Mean Median Mt. Freq. LVCF Interp. HD MICE EM Total Mean 0 2 2 16 17 9 9 9 64 Median 20 0 1 19 20 12 11 14 97 Mt. Freq. 68 53 0 47 49 29 31 32 309 LVCF 36 30 13 0 9 11 12 10 121 Interp. 38 32 16 12 0 12 10 11 131 HD 68 62 50 61 59 0 15 16 331 MICE 68 63 48 65 60 29 0 6 339 EM 65 63 50 66 67 40 28 0 379 Total 363 305 180 286 281 142 116 98 1771 Table 5: Table 4 results filtered by MIV MD type. IMs Mean Median Mt. Freq. LVCF Interp. HD MICE EM Total Mean 0 2 18 20 29 14 14 11 108 Median 13 0 15 21 31 14 15 13 122 Mt. Freq 14 6 0 11 22 11 13 11 88 LVCF 16 15 22 0 19 11 11 10 104 Interp. 16 16 16 10 0 11 11 11 91 HD 61 61 59 65 70 0 8 11 335 MICE 61 61 58 65 70 27 0 13 355 EM 61 61 62 68 71 15 15 0 353 Total 242 222 250 260 312 103 87 80 1556 Table 6: Table 4 results filtered by MAR MD type. IMs Mean Median Mt. Freq. LVCF Interp. HD MICE EM Total Mean 0 4 31 41 54 20 20 14 184 Median 15 0 38 44 53 18 18 15 201 Mt. Freq. 8 5 0 10 28 13 13 13 90 LVCF 11 11 18 0 27 14 13 13 107 Interp. 14 9 13 9 0 13 12 13 83 HD 56 56 59 59 64 0 12 32 338 MICE 59 58 61 62 64 17 0 29 350 EM 58 55 65 65 67 15 12 0 337 Total 221 198 285 290 357 110 100 129 1690 Table 7: Table 4 results filtered by MuOV MD type. 32 IMs Mean Median Mt. Freq. LVCF Interp. HD MICE EM Total Mean 0 7 45 56 59 19 16 12 214 Median 19 0 51 58 61 24 17 12 242 Mt. Freq. 12 8 0 44 45 12 12 9 142 LVCF 17 13 26 0 36 19 12 11 134 Interp. 11 11 22 9 0 17 12 10 92 HD 49 47 59 58 64 0 11 21 309 MICE 63 60 67 63 68 40 0 38 399 EM 59 52 70 68 69 39 15 0 372 Total 230 198 340 356 402 170 95 113 1904 Table 8: Table 4 results filtered by MCAR MD type. The analysis of Table 4 reveals some facts about the behavior of the IMs: •Three clear groups of IMs can be distinguished when observing overall ratings. •The complex methods have a largely positive score when subtracting (o−) from (o+), with values near 800-1,000. •The second group, composed by the simple methods, produced negative values when performing the same subtraction, by a large margin. Regarding solely this group, we see that median imputation stands out from the rest, as it stands in a negative assessment of -261, while the other two obtained around -500. •Finally, the temporal methods performed the worst, by a large margin. Analysis of Tables 5-8 shows how the performance of the IMs is related to the MD types. •Starting from the most biased MD type, MIV (Table 5), we see how its results vary from what could be observed in the overall Table 4. To start, the temporal imputers seemed to perform better than the simple methods, opposed to what the first Table 4 showed. Additionally, Most Frequent imputation excelled in this category, as it obtained almost as good results as the complex methods, which, as expected, topped the ranking. 33 •Regarding MAR (Table 6), more similar results to the global scores were obtained. In this case, LVCF was the outlier, as it could be grouped with the simple methods. •As for MuOV (Table 7), the results also follow a similar pattern to the general rankings. In this case, a fourth cluster could be distinguished, as Most Frequent and LVCF stand considerably close to each other, and relatively away from their original groups. •Finally, the absolutely random MCAR (Table 8) offered considerably different results. The result distribution changed substantially, as MICE and EM remained in the top, but the other complex method, HD, stood closer to Median imputation rather than the top group it is supposed to belong to. Mean appears to stand in no-man’s land, while Most Frequent and LVCF could be grouped together. Ending with an isolated Interpolation. The pair-wise comparison between IMs reveals only a partial picture of the overall behavior of the IMs. To further understand the relation between IM and MD type, we designed another experiment to evaluate the rank of the IMs. First, all the scores were divided in 40 groups. Each group contains all classification results for the combinations of the 10 original DBs and the 4 MD types. Each group comprises 8 ×14 ×30 = 3360 classification scores. In each group, the scores were sorted from the highest to the lowest, and split into 3 equally sized groups: High: the experiments with the highest score; Low: experiments with the lowest score; Medium: the rest of the experiments. By inspecting each group we can determine, for each original DB and MD method, which combination of IMs and classifiers were the most frequent in each of the groups, allowing us to detect high performing IMs, classifiers, and combinations of the two. In the following analysis, the 10 High groups (one for each DB) that have a common MD type are joined in a single “supergroup”. Similarly, a single Low supergroup is created for each MD type. We then compute the proportion of each IM included in the High and Low supergroups. This way, we obtain the 34 IMs that had the best performance independently of the DB (since they were not merged until the final step), and MD type. Figure 2 shows the polar charts describing the frequency of the IMs in the supergroups High and Low according to the MD type. Each section of the chart is proportional to the frequency of a given IM in the cases where the classifiers achieved high (respectively low) scores. A regular circular shape in these charts indicates that all IMs where present with a similar frequency in high and low quality cases, thus indicating no significant impact of the IM in the score. Conversely, more irregular shapes indicate that, for the given MD type, there is an influence of the IMs in the scores. Furthermore, a big gap between the size of the high and low sections for a given IM clearly indicates whether or not the application of the IM contributes to improve the F1 scores. An analysis of Figure 2 shows some clear regularities between different MD types, as all three complex IMs had a much larger appearance rate in the top group rather than in the low one. Moreover, all MD configurations also converge in the null effectiveness of the temporal methods for non-temporal data. However, when it comes to the simple methods, MIV (Figure 2a) and the other MD types (MAR, Figure 2b, MuOV, Figure 2c and MCAR, Figure 2d) contain substantial differences. MIV grants Most Frequent imputation an almost top performing degree, producing similar results to the complex methods. Additionally, the higher appearance frequency of this method, produced that its peers in the simple IM cluster suffered a decrease of their appearance ratio in the high performance group, while the appearance in the low group increased substantially. 7.3. Interactions between MD types, imputation methods, and classifiers In this section we address the following questions: Is it possible to identify any joint effect of IMs and classifiers on the score achieved for different DBs? Does this potential effect depend on the type of MD ? To investigate this question we use the same supergroups of High and Low configurations but in this case we compute the frequencies of all 8 ×14 = 112 35 mean High mean Low median High median Low m.freq. High m.freq. Low lvcf High lvcf Low inter. High inter. Low HD High HD Low mice High mice Low EM High EM Low (a) MIV mean High mean Low median High median Low m.freq. High m.freq. Low lvcf High lvcf Low inter. High inter. Low HD High HD Low mice High mice Low EM High EM Low (b) MAR mean High mean Low median High median Low m.freq. High m.freq. Low lvcf High lvcf Low inter. High inter. Low HD High HD Low mice High mice Low EM High EM Low (c) MuOV mean High mean Low median High median Low m.freq. High m.freq. Low lvcf High lvcf Low inter. High inter. Low HD High HD Low mice High mice Low EM High EM Low (d) MCAR Figure 2: Frequency of the IMs in the configuration with highest (High) and lowest (Low) classification score. 36 SVM−3 RBFN 3−NN 1−NN LDA QDA C−SVM NaiveB CART Regr.L2 Regr.L1 Grad.B. Rnd.Fr. DNN Mean Median M.Freq. LVCF Interp. HD MICE EM 0 50 100 150 200 250 Classifier Imputer 50 100 150 200 250 (a) MIV RBFN SVM−3 3−NN 1−NN QDA LDA NaiveB CART C−SVM Regr.L2 Grad.B. Rnd.Fr. Regr.L1 DNN Mean Median M.Freq. LVCF Interp. HD MICE EM 0 50 100 150 200 250 Classifier Imputer 50 100 150 200 250 (b) MAR 3−NN RBFN SVM−3 1−NN NaiveB CART LDA QDA C−SVM Regr.L2 Grad.B. Rnd.Fr. Regr.L1 DNN Mean Median M.Freq. LVCF Interp. HD MICE EM 0 50 100 150 200 250 Classifier Imputer 50 100 150 200 250 (c) MuOV 3−NN SVM−3 RBFN 1−NN CART QDA NaiveB LDA Regr.L2 C−SVM Rnd.Fr. Regr.L1 Grad.B. DNN Mean Median M.Freq. LVCF Interp. HD MICE EM 0 50 100 150 200 250 Classifier Imputer 50 100 150 200 250 (d) MCAR Figure 3: Amount of IM-Classifier pairs present in the High score section. 37 pairs of IMs and classifiers. This information is shown in Figure 3, in which values are ranked by classification performance (x axis). From Figure 3a we can see how the partial conclusions about the positive relationship between this MDT and Most Frequent imputation are corroborated. For an extensive set of classifiers, this imputer has provided results in a similar range to those obtained by the complex IMs. Besides, it is noticeable that the results are more balanced between classifiers than in the rest of figures. Figure 3b represents the frequency of the pairs considering only MAR MD type. The first difference observable between this and the previous Figure 3a is the scale it is drawn. In this case, the top classifier appeared more frequently, which denotes a worse relation between the DNN and MIV compared to MAR. Additionally, in this case Most Frequent imputation did not stand out from the methods of its same category. This causes a better visualization of the classifiers that require a complex imputation for producing an optimal performance. Good examples of this collection are L2-penalized Regression, or C-SVM. On the contrary, we also have some other classifiers that are unaffected by the IM applied. Random Forest and Gradient Boosting classifiers are excellent exemplars of this set. Results filtered by MuOV MD type are presented by Figure 3c. Again, we distinguish between classifiers that produce similar results regardless the imputer that precedes it. However, this time more contrast can be found in this aspect. The difference between the simple and complex IMs for LDA and QDA classifier supports this distinction between SCs. Finally, Figure 3d, representing MCAR, shows an almost non existing set of midfield classifiers. The differences between contiguous classifiers in the previous figures were quasi-constant. This instance, however, presents a considerable gap in terms of high group appearance rate between Na¨ıve Bayes and LDA classifier, specially for the complex methods. Considering all four figures, we can conclude that a strong relation between IM and MD type exists (MIV and Most Frequent imputation, for example). Additionally, we distinguish between classifiers that need quality imputation 38 to produce a top performance (Deep Neural Network and Logistic Regression classifiers) and others that do not (Gradient Boosting and Random Forest Classifiers). There seems to be a certain regularity on the classifiers ranking, as there is no significant variation between any two MD types in the classifiers axis (x axis) in Figure 3. 7.4. Secondary experimentation For this secondary experimentation, we address the question: How does the amount of MD affect the performances of both classifiers and imputers? To answer this question, we have conducted a similar set of experiment as in the previous experimentation Section 7.1. As explained in Section 7.1.1, we selected two databases, and inserted MCAR MD with varying percentages (742%) for further imputation. These databases were subjected to 5 fold cross validation using two classifiers and F1 score as a metric. To visually interpret these results, Figure 4 has been created. These heatmaps show the mean of all F1 scores computed in all 30 runs. Each subfigure presents the data obtained from a certain database, and a certain classifier. Accordingly, Figure 4a shows the mean F1 score of each pair of imputer and MD percentage obtained in the Leaf database, with the Gradient Boosting classifier. In the figures a dark color represents a better F1 score, and, therefore, a better performance. From this Figure 4 we can list the following findings: •As expected, the more MD, the worse performance offered by the classifiers. •Again following expectations, the classifier more sensitive to imputation quality (Regression) showed an increased need of quality imputation as the amount of MD rose. •Gradient Boosting classifier was selected due to its relatively reduced need of a good imputation for offering a good performance. However, as the MD increased in a DB, this changes, as complex imputers (i.e., MICE) produce more stable results than the rest. 39 7 14 21 28 35 42 Percentages EM MICE HD Interp. LVCF Mt.Freq. Median Mean ImputationMethods MeanF1scores 0.18 0.24 0.30 0.36 0.42 0.48 (a) Leaf DB, Gradient Boosting classifier. 7 14 21 28 35 42 Percentages EM MICE HD Interp. LVCF Mt.Freq. Median Mean ImputationMethods MeanF1scores 0.12 0.15 0.18 0.21 0.24 0.27 (b) Leaf DB, Logistic Regression classifier. 7 14 21 28 35 42 Percentages EM MICE HD Interp. LVCF Mt.Freq. Median Mean ImputationMethods MeanF1scores 0.52 0.56 0.60 0.64 0.68 (c) Vehicle DB, Gradient Boosting classifier. 7 14 21 28 35 42 Percentages EM MICE HD Interp. LVCF Mt.Freq. Median Mean ImputationMethods MeanF1scores 0.48 0.54 0.60 0.66 0.72 (d) Vehicle DB, Logistic Regression classifier classifier. Figure 4: Mean F1 scores for the 30 runs of the experimentation. 40 •Comparing the two pairs generated from the same database, we see how the patterns are very similar, which is indicative of a strong dependency of the results on the problem. •Overall, complex imputers (specially MICE, but also Hot Deck and EM, in a lesser extent) keep reporting acceptable results as MD increases in a DB, while the accuracy of other methods (i.e., Median imputation) seems to be keep up the pace. 8. Conclusions Although it is generally accepted that different patterns of MD can produce a different effect on the data, and some researchers have suggested that these patterns should be taken into account at the time of selecting the IM, an indepth analysis of this question had not been previously approached. This may be due to the complexity of defining an experimental framework that facilitates investigating all the factors involved. In this paper we have proposed a way to study the interactions between algorithms dealing with missing data, supervised classification methods and missing data itself, taking into account its different configurations (MCAR, MIV, MAR and MuOV). A key characteristic of our approach has been the combination of original DBs without MD with specially devised methods for injecting MD consistent with the desired MD types: MCAR, MIV, MAR and MuOV. Ten datasets with no missing values were chosen, and were cloned 30 times. Then the four different MD patterns were applied to them, separately. The resulting benchmark comprising 1,200 datasets was then used to apply the 8 different IMs. Fourteen classification algorithms were applied to the imputed DBs. Statistical significant differences were detected in the performance of the classifiers when using different IMs. The patterns of differences were dependent on the MD type. Results showed significant relation between IM complexity and classification algorithms, since MICE (which implements Multiple Imputation) and Hot Deck (also Expectation-Maximization, to a lesser extent) were more 41 Pal, S. K., & Mitra, S. (1992). Multilayer perceptron, fuzzy sets, and classification. IEEE Transactions on neural networks,3, 683–697. Park, J., & Sandberg, I. W. (1991). Universal approximation using radial-basisfunction networks. Neural computation,3, 246–257. Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., & Dubourg, V. (2011). Scikit-learn: Machine learning in Python. The Journal of Machine Learning Research,12, 2825–2830. Silva, P. F., Marcal, A. R., & da Silva, R. M. A. (2013). Evaluation of features for leaf discrimination. In International Conference Image Analysis and Recognition (pp. 197–204). Springer. Song, Q., Shepperd, M., Chen, X., & Liu, J. (2008). Can k-NN imputation improve the performance of C4. 5 with small software project data sets? A comparative evaluation. Journal of Systems and software,81, 2361–2370. Tan, P.-N., Steinbach, M., Kumar, V., & others (2006). Introduction to data mining volume 1. Pearson Addison Wesley Boston. Twala, B. (2009). An empirical comparison of techniques for handling incomplete data using decision trees. Applied Artificial Intelligence,23 , 373–405. Van Buuren, S. (2012). Flexible imputation of missing data. CRC press. Wong, A. K., & Chiu, D. K. (1987). Synthesizing statistical knowledge from incomplete mixed-mode data. IEEE Transactions on Pattern Analysis and Machine Intelligence, . Yu, H.-F., Huang, F.-L., & Lin, C.-J. (2011). Dual coordinate descent methods for logistic regression and maximum entropy models. Machine Learning,85, 41–75. Yuan, Y. C. (2010). Multiple imputation for missing data: Concepts and new development (Version 9.0). SAS Institute Inc, Rockville, MD,49. 48 Ziba, M., Tomczak, J. M., Lubicz, M., & witek, J. (2014). Boosted SVM for extracting rules from imbalanced data in application to prediction of the postoperative life expectancy in the lung cancer patients. Applied soft computing, 14, 99–108. 49