next up previous
Next: Bibliography Up: CVonline_ANOVA Previous: CVonline_ANOVA

One way ANOVA - Analysis of variance

Analysis of variance (ANalysis Of VAriance) is a general method for studying sampled-data relationships [1,2]. The method enables the difference between two or more sample means to be analysed, achieved by subdividing the total sum of squares. One way ANOVA is the simplest case. The purpose is to test for significant differences between class means, and this is done by analysing the variances. Incidentally, if we are only comparing two different means then the method is the same as the $t-test$ for independent samples. The basis of ANOVA is the partitioning of sums of squares into between-class ($SS_{b}$) and within-class ($SS_{w}$). It enables all classes to be compared with each other simultaneously rather than individually; it assumes that the samples are normally distributed. The one way analysis is calculated in three steps, first the sum of squares for all samples, then the within class and between class cases. For each stage the degrees of freedom $df$ are also determined, where $df$ is the number of independent `pieces of information' that go into the estimate of a parameter. These calculations are used via the Fisher statistic to analyse the null hypothesis. The null hypothesis states that there are no differences between means of different classes, suggesting that the variance of the within-class samples should be identical to that of the between-class samples (resulting in no between-class discrimination capability). It must however be noted that small sample sets will produce random fluctuations due to the assumption of a normal distribution. If $d_{ij}$ is the sample for the $i^{th}$ class and $j^{th}$ data point then the total sum of squares is defined as:

SS_t~=~\sum_{i=1}^S\sum_{j=1}^D (d_{ij} - GM)^2
\end{displaymath} (1)

with degrees of freedom:
df_{t} ~=~ (S ~ D)-1
\end{displaymath} (2)

where $D$ is the number of data points (assuming equal numbers of data points in each class) and $S$ is the number of classes and $GM$ is the grand mean:
GM ~=~\frac{1}{(S ~ D)} ~\sum_{i=1}^S\sum_{j=1}^D d_{ij}
\end{displaymath} (3)

The second stage determines the sum of squares for the within class case, defined as:
SS_w~=~\sum_{i=1}^S\sum_{j=1}^D (d_{ij} - M_i)^2
\end{displaymath} (4)

where $M_i$ is the $i^{th}$ class mean determined by:
M_i ~=~\frac{1}{D} ~ \sum_{j=1}^{D} d_{ij}
\end{displaymath} (5)

and the within class $df$ is:
df_{w} ~=~ S(D-1)
\end{displaymath} (6)

The sum of squares for the between class case is:
SS_b~=~ \sum_{i=1}^S D ~ (M_{i} - GM)^2
\end{displaymath} (7)

with the corresponding $df$ of:
df_{b} ~=~ S-1
\end{displaymath} (8)

Defining the total degrees of freedom $df_{t}$ and the total sum of squares $SS_t$ as:
df_{t} ~=~ df_b + df_w
\end{displaymath} (9)

SS_t = SS_b + SS_w
\end{displaymath} (10)

Finally if $MSS_{b}$ is the mean square deviations (or variances) for the between class case, and $MSS_{w}$ is the reciprocal for the within class case then:
MSS_b = \frac{SS_b}{df_b}~~~~;~~~~MSS_w = \frac{SS_w}{df_w}
\end{displaymath} (11)

It is now possible to evaluate the null hypothesis using the Fisher or $F$$F$Fisher statistic statistic, defined as:
F = \frac{MSS_{b}}{MSS_{w}}
\end{displaymath} (12)

If $F>>1$ then it is likely that differences between class means exist. These results are then tested for statistical significance or $P$-value, where the $P$-value is the probability that a variate would assume a value greater than or equal to the value observed strictly by chance. If the $P$-value is small (eg. $P<0.01$ or $P<1\,\%$) then this implies that the means differ by more than would be expected by chance alone. By setting a limit on the $P$-value, (i.e. $1\,\%$) a critical $F$ value can be determined. The critical value $F_{crit}$ is determined (via standard lookup tables) through the between-class ($df_b$) and within-class ($df_w$) $df$ values. Values of $F$ greater than the critical value denote the rejection of the null hypothesis, which prompts further investigation into the nature of the differences of the class means. In this way ANOVA can be used to prune a list of features. Figure 0.1 shows example $F_{crit}$$F_{crit}$Fisher statistic critical value values for a low $df$ distribution (i.e. a small dataset). As $df$ increases (i.e. the dataset size increases) the $F$ distribution will become `tighter' and more peaked in appearance, while the peak will shift away from the $x$ axis towards $F=1$.

Figure 0.1: Example F distribution (for low $df$) showing possible $5\,\%$ and $1\,\%$ intervals.

The $F$ value gives a reliable test for the null hypothesis, but it cannot indicate which of the means is responsible for a significantly low probability. To investigate the cause of rejection of the null hypothesis post-hoc or multiple comparison tests can be used. These examine or compare more than one pair of means simultaneously. Here we use the Scheffe post-hoc test. This tests all pairs for differences between means and all possible combinations of means. The test statistic $F_S$$F_s$Scheffe post-hoc test value is:

F_S ~=~ \frac{(\overline{M_i} - \overline{M_j})^2}{MSS_w \left( \frac{1}{n_i}+\frac{1}{n_j} \right)~df_b}
\end{displaymath} (13)

where $i$ and $j$ are the classes being compared and $n_i$ and $M_i$ are the number of samples and mean of class $i$, respectively. If the number of samples (data points) is the same for all classes then $n_i=n_j=D$. The test statistic is calculated for each pair of means and the null hypothesis is again rejected if $F_S$ is greater than the critical value $F_{crit}$, as previously defined for the original ANOVA analysis. This Scheffe post hoc test is known to be conservative which helps to compensate for spurious significant results that occur with multiple comparisons [2]. The test gives a measure of the difference between all means for all combinations of means.

In terms of classification, large $F$ statistic values do not necessarily indicate useful features. They only indicate a well spread feature space, which for a large dataset is a positive attribute. It suggests that the feature has scope or `room' for more classes to be added to the dataset. Equally, features with smaller $F$ values (but greater than the critical values $F_{crit}$) may separate a portion of the dataset, which was previously `confused' with another portion. Adding this new feature, increasing the feature space dimensions, may prove beneficial. In this manner, features which appear `less good' (i.e. lower $F$ statistic values than alternative features) may, in fact, prove useful in terms of classification.

next up previous
Next: Bibliography Up: CVonline_ANOVA Previous: CVonline_ANOVA
Jamie Shutler 2002-08-15