As more and more coding standards are developed for videos with higher resolution and higher frame rates, the conversion between them is in demand. This paper focuses on the development of fast VP9-to-HEVC transcoding algorithm. Since the decoding-and-full-re-encoding process is time consuming, we explore Naïve-Bayes based machine learning algorithm to accelerate VP9-to-HEVC transcoding. The machine learning process can bridge VP9 decoding information and HEVC splitting decision throughout training results, so the HEVC CU searching process can be simplified for faster transcoding. Two new features closely related to VP9, sub-block counting and depth map, are added for VP9-to-HEVC video transcoder. Using coding features and Naive-Bayes algorithm, several models are built for different QPs and block sizes to reduce transcoding time. Experiments show that a maximum time reduction of 53% and an average reduction of 44% can be achieved and the loss of decoded image quality in BD-rate is almost ignorable.