With the rapid development of LocationBased Social Networks (LBSN) recommender system, PointofInterest (POI) recommendation has become a hot topic. The research of POI recommendation aims to recommend POIs for users and to provide services such as advertising and potential customer discovery. Due to the high data sparseness of users’ checkins, POI recommendation faces a great challenge. Many researches combine geographical influence, time awareness, social relevance and other factors to improve the performance of POI recommendation. However, in most POI recommendation researches, the periodicity of mobility and the user preference varying with the change of contextual scenario have not been excavated in depth. Moreover, there exists high data sparseness in Next POI recommendation. Based on the above considerations, this paper proposes a Contextaware Personalized Metric Embedding (CPME) algorithm, which is based on the user's periodic behavior pattern. It takes into account the contextual information of users’ checkins, which can enrich the valid data, alleviate the data sparseness, improve the recommendation accuracy, and further optimize the algorithm to reduce the time complexity. The experimental analysis on two real LBSN datasets show that the proposed algorithm has better recommendation performance.