Video transcoding is to convert one compressed video stream to another. In this paper, a fast H.264/AVC to High Efficiency Video Coding (HEVC) transcoding method based on machine learning is proposed by considering the similarity between compressed streams, especially the block partition correlations, to reduce the computational complexity. This becomes possible by constructing three-level binary classifiers to predict quad-tree Coding Unit (CU) partition in HEVC. Then, we propose a feature selection algorithm to get representative features to improve predication accuracy of the classification. In addition, we propose an adaptive probability threshold determination scheme to achieve a good trade-off between low coding complexity and high compression efficiency during the CU depth prediction in HEVC. Extensive experimental results demonstrate the proposed transcoder achieves complexity reduction of 50.2% and 49.2% on average under lowdelay P main and random access configurations while the rate-distortion degradation is negligible. The proposed scheme is proved more effective as comparing with the state-of-the-art benchmarks.