The vast range of cloud service offerings can easily overwhelm users and cause them to select ones that are unsuitable for their needs. As such, the literature has a number of proposals to predict application performance based on a history of executing a certain application or benchmark. However, this requires significant cost to pre-run the application on different service levels before identifying the most suitable one. We propose a machine learning model that enables a cloud user to select the optimal cloud service based on real-time execution without the need to do an exhaustive search. We develop and test this model using a popular benchmark suite on Microsoft Azure, a leading cloud provider. The key insight of this work is that fluctuations in rather than the absolute amount of utilization levels of CPU and memory can be strongly indicative of how well an application is executing.