Missing Value Prediction Using Co-clustering

In [2],[4], it has been shown that the missing value prediction problem can be formulated as a weighted matrix approximation problem where the weights are 1's for known values and 0's for unknown ones, then we can use co-clustering for finding the best matrix approximation based on some criteria. The assumption is that the original matrix has a low parameter structure involving properties of row and column clusters. By minimizing a desired loss function, co-clustering can find that low parameter structure and this structure is used for reconstructing the approximate matrix. Let $Z$ be the random variable that takes values in the matrix, $U$ and $V$ be discrete random variables whose values are the row and column indices respectively, and $\hat{U}$ and $\hat{V}$ be discrete random variables which takes values on the row cluster and column cluster indices. Then [2] shows that, for a given co-clustering, there are only six distinct sets of summary statistics or co-clustering bases which can be used for approximating the matrix $\hat{Z}$:

$$\begin{array}{ll} C_1 = \{\{\hat{U}\},\{\hat{V}\}\} & C_2... ...}\}\} & C_6= \{\{\hat{U},V\},\{U,\hat{V}\}\} \\ \end{array}$$

We also call these co-clustering bases as schemes. Moreover, using the Minimum Bregman Information (MBI), we can find the best approximation matrix $\hat{Z}$ for a given co-clustering, a given co-clustering basis, and a given Bregman divergence. Table 1 and 2 present the best approximation solutions of each basis for squared Euclidean distance and I-divergence, where the expectation in those formulae are interpreted as follows:

• $E[Z]$: the average value of the entire matrix
• $E[Z\vert U]$ and $E[Z\vert V]$: row averages and column averages respectively
• $E[Z\vert\hat{U}]$ and $E[Z\vert\hat{V}]$: row cluster averages and column cluster averages respectively
• $E[Z\vert U,\hat{V}]$ and $E[Z\vert\hat{U},V]$: row column cluster averages and column row cluster averages respectively. In other words, they are the average of each row in a column cluster and the average of each column in a row cluster.
• $E[Z\vert\hat{U},\hat{V}]$: co-cluster averages

Table 1: Best matrix approximation for squared Euclidean distance

Coclustering basis $C$	Approximation matrix $\hat{Z}$
$C_1$	$E[Z\vert\hat{U}]$ + $E[Z\vert\hat{V}]$ - $E[Z]$
$C_2$	$E[Z\vert\hat{U},\hat{V}]$
$C_3$	$E[Z\vert U]$ - $E[Z\vert\hat{U}]$ + $E[Z\vert\hat{U},\hat{V}]$
$C_4$	$E[Z\vert V]$ - $E[Z\vert\hat{V}]$ + $E[Z\vert\hat{U},\hat{V}]$
$C_5$	$E[Z\vert U]$ - $E[Z\vert\hat{U}]$ + $E[Z\vert V]$ - $E[Z\vert\hat{V}]$
	+ $E[Z\vert\hat{U},\hat{V}]$
$C_6$	$E[Z\vert U,\hat{V}]$ + $E[Z\vert\hat{U},V]$ - $E[Z\vert\hat{U},\hat{V}]$

Table 2: Best matrix approximation I-divergence

Coclustering basis $C$	Approximation matrix $\hat{Z}$
$C_1$	$\frac{E[Z\vert\hat{U}] \times E[Z\vert\hat{V}]}{E[Z]}$
$C_2$	$E[Z\vert\hat{U},\hat{V}]$
$C_3$	$\frac{E[Z\vert U] \times E[Z\vert\hat{U},\hat{V}]}{E[Z\vert\hat{U}]}$
$C_4$	$\frac{E[Z\vert V] \times E[Z\vert\hat{U},\hat{V}]}{E[Z\vert\hat{V}]}$
$C_5$	$\frac{E[Z\vert U] \times E[Z\vert V] \times E[Z\vert\hat{U},\hat{V}]}{E[Z\vert\hat{U}] \times E[Z\vert\hat{V}]}$
$C_6$	$\frac{E[Z\vert U,\hat{V}] \times E[Z\vert\hat{U},V]}{E[Z\vert\hat{U},\hat{V}]}$