In this paper, we propose a clustering linear discriminant analysis algorithm (CLDA) to accurately decode hand movement directions from a small number of training trials for magnetoencephalography-based brain computer interfaces (BCIs). CLDA first applies a spectral clustering algorithm to automatically partition the BCI features into several groups where the within-group correlation is maximized and the between-group correlation is minimized. As such, the covariance matrix of all features can be approximated as a block diagonal matrix, thereby facilitating us to accurately extract the correlation information required by movement decoding from a small set of training data. The efficiency of the proposed CLDA algorithm is theoretically studied and an error bound is derived. Our experiment on movement decoding of five human subjects demonstrates that CLDA achieves superior decoding accuracy over other traditional approaches. The average accuracy of CLDA is 87% for single-trial movement decoding of four directions (i.e., up, down, left, and right).