In this paper, we propose the concept of attack scenarios, which can be learned and selected from a set of malicious applications and described by sets of Android APIs, to characterize Android malware. Because of its characteristics that produce almost no false-positive, attack scenarios can be used as a pre-filter for machine-learning based detectors to enhance the detection performance at low false-positive rate. By combining different machine learning techniques, we demonstrate that the proposed approach can increase the detection rates. To evaluate our approach, we analyze 20,914 Android application containing 3,145 malicious samples on two different machine learning techniques, KNN and SVM. The experiment results show that the proposed approach can raise the detection rate up to 95.9% malware at 1% false positive rate and 95.9% malware at 0.1% false positive rate respectively.