Barriers, such as the lack of confidence in the robustness of disease signatures based on gene expression measurements, still hinder progress toward personalized medicine. It is therefore important that once derived, a signature is verified via an unbiased process. The IMPROVER initiative was set up to establish an impartial view of methods and results for the classification of patients, based on molecular profiles of disease-relevant or surrogate tissues. Here, the focus is on the Lung Cancer Signature Challenge, in which participants have been asked to classify lung tumor gene expression profiles into 4 classes: adenocarcinoma (AC) and squamous cell carcinoma (SCC), each at either stage 1 or 2. The method reported here was the best performing method in the 4-way classification. The original method is presented as well as an algorithmic approach to replace the empirical (non-computational) steps used in the challenge. In the discussion, the difficulty in classifying stages of tumors as compared with the relatively good classification of subtypes is examined. Hypotheses are made concerning possible reasons for erroneous classification of some of the samples, in view of additional information on the test samples that was not made available to challenge participants.