Human mobility literature is limited in their ability to capture the novelty-seeking or the exploratory tendency of individuals. Mainly, the vast majority of mobility prediction models rely uniquely on the history of visited locations (as captured in the input dataset) to predict future visits. This hinders the prediction of new unseen places and reduces prediction accuracy. In this paper, we show that a two-dimensional modeling of human mobility, which explicitly captures both regular and exploratory behaviors, yields a powerful characterization of users. Using such model, we identify the existence of three distinct mobility profiles with regard to the exploration phenomenon-Scouters (i.e., extreme explorers), Routiners (i.e., extreme returners), and Regulars (i.e., without extreme behavior). Further, we extract and analyze the mobility traits specific to each profile. We then investigate temporal and spatial patterns in each mobility profile and show the presence of recurrent visiting behavior of individuals even in their novelty-seeking moments. Our results unveil important novelty preferences of people, which are ignored by literature prediction models. Finally, we show that prediction accuracy is dramatically affected by exploration moments of individuals. We then discuss how our profiling methodology could be leveraged to improve prediction.