The Android operating system is the most used mobile operating system in the world, and it is one of the most popular operating systems for different kinds of devices from smartwatches, IoT, and TVs to mobiles and cockpits in cars. Security is the main challenge to any operating system. Android malware attacks and vulnerabilities are known as emerging risks for mobile devices. The development of Android malware has been observed to be at an accelerated speed. Most Android security breaches permitted by permission misuse are amongst the most critical and prevalent issues threatening Android OS security. This research performs several studies on malware and non-malware applications to provide a recently updated dataset. The goal of proposed models is to find a combination of noise-cleaning algorithms, features selection techniques, and classification algorithms that are noise-tolerant and can achieve high accuracy results in detecting new Android malware. The results from the empirical experiments show that the proposed models are able to detect Android malware with an accuracy that reaches 87%, despite the noise in the dataset. We also find that the best classification results are achieved using the RF algorithm. This work can be extended in many ways by applying higher noise ratios and running more classifiers and optimizers.