In this paper we present a method for classifying accurately SAGE (Serial Analysis of Gene Expression) data. The high dimensionality of the data, namely the large number of features, in combination with the small number of samples poses a great challenge and demands more accurate and robust algorithms for classification. The prediction accuracy of the up to now proposed approaches is moderate. In our approach we exploit the associations among the expressions of genes in order to construct more accurate classifiers. For validating the effectiveness of our approach we experimented with two real datasets using numerous feature selection and classification algorithms. The results have shown that our approach improves significantly the classification accuracy, which reaches 99%.