Clinicians need to routinely make management decisions about patients who are at risk for a disease such as breast cancer. This paper presents a novel clinical decision support tool that is capable of helping physicians make diagnostic decisions. We apply this support system to improve the specificity of breast cancer screening and diagnosis. The system utilizes clinical context (e.g., demographics, medical history) to minimize the false positive rates while avoiding false negatives. An online contextual learning algorithm is used to update the diagnostic strategy presented to the physicians over time. We analytically evaluate the diagnostic performance loss of the proposed algorithm, in which the true patient distribution is not known and needs to be learned, as compared with the optimal strategy where all information is assumed known, and prove that the false positive rate of the proposed learning algorithm asymptotically converges to the optimum. In addition, our algorithm also has the important merit that it can provide individualized confidence estimates about the accuracy of the diagnosis recommendation. Moreover, the relevancy of contextual features is assessed, enabling the approach to identify specific contextual features that provide the most value of information in reducing diagnostic errors. Experiments were conducted using patient data collected at a large academic medical center. Our proposed approach outperforms the current clinical practice by 36% in terms of false positive rate given a 2% false negative rate.