nagdmc impute em

NAG DMC

Data Imputation: nagdmc impute em
Purposenagdmc impute em imputes missing values in data by using an expectation maximisation (EM)algorithm, assuming a multivariate Normal distribution over m variables.
nagdmc impute em returns an array containing the indexes of imputed values (see ‘ExplanatoryCode’). The memory used by this array should be returned to the operating system by the user asindicated in the Essential Introduction.

Declaration#include <nagdmc.h>long *nagdmc impute em(long rec1, long nvar, long nrec, long dblk, double data[],long nxvar, long xvar[], double wt[], double mval,
double tol, long maxit, long *it, long *nrepl,
long *nempty, double mean[], double cov[], double *sumwts,
int *info);

Parameters1:

rec1 – long

Input

On entry: the index in the data of the first data record used in the analysis.
Constraint: rec1 ≥ 0.
2:

nvar – long

Input

On entry: the number of variables in the data.
Constraint: nvar ≥ 1.
3:

nrec – long

Input

On entry: the number of consecutive records, beginning at rec1, used in the analysis.
Constraint: nrec > 1.
4:

dblk – long

Input

On entry: the total number of records in the data block.
Constraint: dblk ≥ rec1 + nrec.
5:

data[dblk ∗ nvar] – double

Input/Output

On entry: data values for the jth variable (for j = 0, 1, . . . , nvar − 1) are stored in data[i ∗ nvar + j],
for i = 0, 1, . . . , dblk − 1.
On exit: missing values in data are replaced by their estimates.
6:

nxvar – longInput

On entry: the number of variables in the analysis. If nxvar = 0, all variables in the data are usedin the analysis.
Constraint: 0 ≤ nxvar ≤ nvar.
7:xvar[nxvar] – long

Input

On entry: the indices indicating the position in data in which the variables in the analysis are stored.
If nxvar = 0 then xvar must be 0, and the indices of variables are given by j = 0, 1, . . . , nvar − 1.
Constraints: if nxvar > 0, 0 ≤ xvar[i] < nvar, for i = 0, 1, . . . , nxvar − 1; otherwise xvar must be 0.
8:

wt[dblk] – double

Input

On entry: wt[i] contains the weight on the ith data record, for i = 0, 1, . . . , dblk − 1. If the weighton each record is the same, wt should be set equal to 0.
Constraint: if wt 6= 0, wt[i] ≥ 0.0, for i = 0, 1, . . . , dblk − 1.

nagdmc impute em.1

nagdmc impute em

NAG DMC9:mval – double
Input
On entry: all values in data equal within machine precision to mval are considered missing fromthe analysis.
Suggested value: a value outside the interval [a, b], where a and b are the minimum and maximum
value in your data, respectively.

10:

tol – double
On entry: the convergence tolerance of the EM algorithm.
Constraint: tol > 0.0.

Input

11:

maxit – long
On entry: the maximum number of iterations of the EM algorithm.
Constraint: maxit ≥ 1.

Input

12:

it – long
On exit: the actual number of iterations performed by the EM algorithm.

Output13:

nrepl – long *OutputOn exit: the number of imputed values in data, and equals the number of values in data equal tomval.

14:

nempty – long *OutputOn exit: the number of data records for which the m variables in the analysis each take the value
mval.

15:

mean[m] – double
OutputOn exit: if mean 6= 0, mean[i] contains the mean value of the ith variable in the analysis after
imputation, for i = 0, 1, . . . , m − 1; otherwise mean is not referenced.

16:

cov[m ∗ (m + 1)/2] – double
OutputOn exit: if cov 6= 0, the first m ∗ (m + 1)/2 elements of cov contain the upper-triangular part of thevariance-covariance matrix of the m variables in the analysis, packed by row; otherwise cov is notreferenced.

17:

sumwts – double *OutputOn exit: the sum of the case weights in the model. If wt is set to 0, sumwts equals the number ofdata records.

18:

info – int *On exit: info gives information on the success of the function call:

Output0: the function successfully completed its task.
-20: the EM algorithm has not converged and all results should be treated with caution.
The value of maxit should be increased before executing the function again. If the EMalgorithm persists in having difficulty converging, a lower value of tol should be considered.
i; i = 1, 2, 3, 4, 6, 7, 8, 10, 11: the specification of the ith formal parameter was incorrect.
19: covariance matrix not positive definite.
20: no missing values were found in the data; check your definition of mval.
99: the function failed to allocate enough memory.

Notation
nrec
data
nxvar
mval
tol
nrepl
mean
cov

the number of data records, n.
the data set X.
determines the number of variables, m.
the value of missing data values, z.
the tolerance for terminating the EM algorithm, τ .
the number of replaced values, r.
the estimated sample means, sb.
bthe estimated sample variance-covariances, Σ.

nagdmc impute em.2

nagdmc impute em

NAG DMC

Description
The EM algorithm is used to estimate the mean and variance-covariance matrix of a multivariate
Normal probability distribution given a set, X, of n data records with m variables and r > 0 values
missing at random.
Let z be the value of a real scalar used to identify values missing at random in the data. Excluding
data values equal to z, the first step is to compute initial estimates of the sample means sb andb In each iteration of the EM algorithm the estimates sb and Σb are
variance-covariance matrix Σ.
revised in three steps.
Firstly, given a data record xi with p < m known values and q = m − p missing values, letb ∈ IRp×p be the estimated variance-covariance matrix over the variables with known values andΣkkp×qbΣbe the estimated variance-covariance matrix of the variables with known values andkm ∈ IR
b Then the linear regression
the variables with missing values, both of which are obtained from Σ.
of variables with missing values on variables with known values has coefficients B given by,b −1 Σb
B=Σ
kk km .
Secondly, the q missing values in xi are replaced by their conditional expectation values given theb by using the regression model:
p known values and the estimates of sb and Σuu = vu + (uk + vk )B,
whereuu∈ IR1×q contains the estimates of the q missing values,
vu ∈ IR1×q contains the estimated sample means from sb for the variables with missing values,uk ∈ IR1×p contains the data values from xi for the variables with known values,and vk ∈ IR1×p contains the estimated sample means from sb for the variables with known values.
Finally, as each data record containing at least one missing value is updated, the revised estimates ofthe sample means and variance-covariance matrix are computed by using West’s update algorithm.
At the end of the jth iteration of the EM algorithm, the largest value, say w ∈ IR, of the absoluteb (j−1) − Σb (j) is compared against a tolerance τ and thevalues of the differences sb(j−1) − sb(j) and ΣEM algorithm terminates if w ≤ τ .

References and Further Reading
Dempster A P N, Laird N M and Rubin D B (1977) Maximum likelihood estimation from incomplete
data via the EM algorithm J. Roy. Stat. Soc. B 39 1–38.
Little R J A and Rubin D B (1987) Statistical Analysis with Missing Data Wiley.
West D H D (1979) Updating mean and variance estimates: an improved method Comm. ACM 22(9) 532–535.

Explanatory CodeThe following C function prints the index in the data and the imputed value of each of the nrepl
replaced values after a successful call to nagdmc impute em returning indexes.
#include <stdio.h>void imputed_values(long nvar, double data[], long nrepl, long indexes[]) {long i, j, k;#define MISSING_ROW(I) indexes[I]#define MISSING_COL(I) indexes[I+nrepl]#define DATA(I,J) data[(I)*nvar+J]
printf("\n\tRow \tCol \tValue\n");for (i=0; i<nrepl; ++i) {j = MISSING_ROW(i);k = MISSING_COL(i);printf("\t%-4li\t%-4li\t%-8.4f\n",j,k,DATA(j,k));}}nagdmc impute em.3

NAG DMC

nagdmc impute em

See Also
nagdmc free impute returns memory allocated by nagdmc impute em to the operating system.
impute em ex.cthe example calling program.

nagdmc impute em.4