Transcript Missing Completely at Random

Missing values problem in
Data Mining
JELENA STOJANOVIC
03/20/2014
Outline

Missing data problem
Missing values in attributes
 Missing values in target variable
 Missingness mechanisms


Aapproaches to Missing values
Eliminate Data Objects
 Estimate Missing Values
 Handling the Missing Value During Analysis

Experimental analisys
 Conclusion

Missing Data problem

There are a lot of serious data quality problems in real datasets:
incomplete, redundant, inconsistent and noisy

reduce the performance of data mining algorithms

Missing data is a common issue in almost every real dataset.

Caused by varied factors:

high cost involved in measuring variables,

failure of sensors,

reluctance of respondents in answering certain questions or

an ill-designed questionnaire.
Missing values in datasets

The missing data problem
arises when values for one
or more variables are
missing from recorded
observations.
10
Tid Refund Marital
Status
Taxable
Income Cheat
1
Yes
Single
125K
No
2
No
Married
100K
No
3
No
Single
70K
No
4
Yes
Married
120K
No
5
No
Divorced 95K
Yes
6
No
Married
No
7
Yes
Divorced 220K
No
8
No
Single
85K
Yes
9
No
Married
75K
No
10
No
Single
90K
Yes
60K
Missing values in attributes
(independant variables)
Missing labels
Missingness mechanism

Missing Completely At Random

Missing At Random

Missing Not At Random
Missing Completely at Random - MCAR




Missing Completely at Random - the
missingness mechanism does not depend
on the variable of interest, or any other
variable, which is observed in the dataset.
The data are collected and observed
arbitrarily and the collected data does
not depend on any other variable of the
dataset.
The case when respondents decide to
reveal their income levels based on coinflips
This type of missing data is very rarely
found and the best method is to ignore
such cases.
MCAR (continued)

Estimate E(X) from partially observed data:
X* = [0, 1, m, m,1,1, m, 0, 0, m…]

True data:
X = [0, 1, 0, 0, 1, 1, 0, 0, 0, 1…]


E(X)=?
E(X) = 0.5
Rx = [0, 0, 1, 1, 0, 0, 1, 0, 0, 1…]
If MCAR:

X* = [0, 1, m, m,1,1, m, 0, 0, m…]
and
E(X) = 3/6 =0.5
Missing At Random - MAR

Missing at random - when the probability of an
instance having a missing value for an attribute may
depend on the known values, but not on the value
of the missing data itself;

Missingness can only be explained by variables that
are fully observed whereas those that are partially
observed cannot be responsible for missingness in
others; an unrealistic assumption in many cases.

Women in the population are more likely to not
reveal their age, therefore percentage of missing
data among female individuals will be higher.
Missing Not Ar Random- MNAR

When data are not either MCAR or MAR

Missingness mechanism depends on another
partially observed variable

Situation in witch the missingness mechanism
depends on the actual value of missing data. The
probability of an instance having a missing value
for an attribute could depend on the value of
that attribute

Difficult task; model the missingness
Missing data consequences

They can significantly bias the outcome of research studies.

Response profiles of non-respondents and respondents can be significantly
different from each other.

Performing the analysis using only complete cases and
ignoring the cases with missing values can reduce the sample
size thereby substantially reducing estimation efficiency.

Many of the algorithms and statistical techniques are generally
tailored to draw inferences from complete datasets.

It may be difficult or even inappropriate to apply these algorithms and
statistical techniques on incomplete datasets.
Handling missing values


In general, methods to handle missing values belong
either to sequential methods (preprocessing methods)
or to parallel methods (methods in which missing
attribute values are taken into account during the main
process of acquiring knowledge).
Existing approaches:

Eliminate Data Objects or Attributes

Estimate Missing Values

Handling the Missing Values During Analysis
Eliminate data objects
Eliminating data attributes
Estimate Missing Values
most
common/
mean
value
Imputation
Imputation- nearest neighbor
Handling the Missing Value During Analysis

Missing values are taken into account during the main process of acquiring
knowledge

Some examples:

Clustering - similarity between the objects calculated using only the attributes
that do not have missing values.

C4.5 - splitting cases with missing attribute values into fractions and adding
these fractions to new case subsets.

CART -A method of surrogate splits to handle missing attribute values

Rule-based induction algorithms- missing values „do not care conditions“

Pairwise deletion is used to evaluate statistical parameters from available
information

CRF-marginalizing out effect of missing label instances on labeled data
Internal missing data strategy used by C4.5

C4.5 uses a probabilistic approach to handle missing data

C4.5:

Multiple split (Each node T can be partitioned into T1 , T2 … Tn subsets)

Evaluation measure: Information Gain ratio

If there exist missing values in an attribute X, C4.5 uses the subset with all
known values of X to calculate the information gain.

Once a test based on an attribute X is chosen, sC4.5 uses a probabilistic
approach to partition the instances with missing values in X
Internal missing data strategy used by C4.5


When an instance in T with known value is assigned to a subset Ti,

probability of that instance belonging to subset Ti is 1

probability of that instance belonging to all other subsets is 0
C4.5 associates to each instance in Ti a weight representing the probability of
that instance belonging to Ti.

If the instance has a known value, and satisfies the test with outcome Oi, then this instance is
assigned to Ti with weight 1

If the instance has an unknown value, this instance is assigned to all partitions with different
weights for each one:

The weight for the partition Ti is the probability that instance belongs to Ti.

This probability is estimated as the sum of the weights of instances in T known to satisfy the
test with outcome Oi, divided by the sum of weights of the cases in T with known values on
the attribute X.
Experimental Analysis*

Using cross-validation estimated error rates compare performance of :

K-nearest neighbour algorithm as an imputation method

Mean or mode imputation method

Internal algorithms used by C4.5 and CN2 to learn with missing data

Missing values were artificially implanted, in different rates and attributes
(more than 50%)

Data sets from UCI [10]: Bupa, Cmc, Pima and Breast
*G. Batista and M.C. Monard, “An Analysis of Four Missing Data Treatment Methods for Supervised Learning,”Applied
Artificial Intelligence,vol. 17, pp. 519-533, 2003
Comparative results for the Breast data set
Comparative results for the Bupa data set
Comparative results for the Cmc data set
Comparative results for the Prima data set
Conclusion

Missing data huge data quality problem

Vast variety of causes of missingess

In general, there is no best, universal method of handling missing
values

Different types of missingness mechanism (MCAR, MAR, MNAR)
and datasets require different approaches of dealing with
missing values
Thank you for your attention!
Questions?
Homework problem:

1. List the types of missingness mechanisms. State one
way you think should be appropriate for solving each of
them and shortly explain way.
Eliminate data objects or attributes


Eliminate objects with missing values (listwise deletion)

Simple and effective strategy

Even partially specified objects contains some information

If there are many objects- reliable analysis can be difficult or impossible

Unless data are missing completely at random, listwise deletion can bias the outcome.
Eliminate attributes that have missing values


Carefully: These attributes maybe critical for analysis
Listwise deletion and pairwise deletion used in approximately 96% of studies in the
social and behavioral sciences.
Estimate Missing Values

Missing data sometimes can be estimated reliably using values of remaing cases or
attrubutes:

replacing a missing attribute value by the most common value of that attribute,

replacing a missing attribute value by the mean for numerical attributes,

assigning all possible values to the missing attribute value,

assigning to a missing attribute value the corresponding value taken from the closest case,

replacing a missing attribute value by a new value, computed from a new data set, considering
the original attribute as a decision (imputation)


For this strategy, comonly used are machine learning algorithms:

Unstructured (Decision trees, Naive Bayes, K-Neares neighbors…)

Structured (Hidden Markov Models, Conditional Random Fields, Structured SVM…)
Some of these methods are more accurate, but more computationaly expensive, so different situations
require different solutions
Handling the Missing Value During Analysis

Missing attribute values are taken into account during the main process of acquiring knowledge

In clustering, similarity between the objects calculated using only the attributes that do not have missing values.
Similarity in this case only approximation, but unless the total number of attributes is small or the numbers of
missing values is high, degree of inaccuracy may not matter much.

C4.5 induces a decision tree during tree generation, splitting cases with missing attribute values into fractions
and adding these fractions to new case subsets.

A method of surrogate splits to handle missing attribute values was introduced in CART.

In modification of the LEM2 (Learning from Examples Module, version 2) rule induction algorithm rules are
induced form the original data set, with missing attribute values considered to be "do not care" conditions or
lost values.

In statistics, pairwise deletion is used to evaluate statistical parameters from available information:


to compute the covariance of variables X and Y , all those cases or observations in which both X and Y
used regardless of whether other variables in the dataset have missing values.
are observed are
In CRFs, marginalizing out effect of missing label instances on labeled data, and thus utilizing information of all
observations and preserving the observed graph structre.