Pt-Ni alloy nanoclusters are essential for high-performance catalysis, and the full description for the finite temperature properties is highly desired. Here we developed an efficient machine learning method to evaluate the accurate structure-stability correspondence in a Pt(85-x)-Nix nanocluster over the structural space with a dimension of 3.84 × 1025. On the basis of the physical model and big-data analysis, for the first time, we demonstrated that the segregation-extent bond order parameter (BOP) and the shell-resolved undercoordination ratio play the key roles in the structural stability. This a priori knowledge extremely reduced the computational costs and enhanced the accuracies. With the 500-sample train data set generated by density functional theory (DFT)-level geometry optimizations, we fit the machine-learning excess energy potential and verified the mean-square-error is <0.13. Our physically niche genetic-machine learning program (PNG-ML) searched 2.5 × 105 structures and predicted precisely the most stable Pt43-Ni42 (x = 42). The structural space dimension was reduced by 1020 fold using our PNG-ML method. The Pt/Ni ratio of the most stable nanocluster is 1.02, which is highly consistent with the experimental observation of 1.0. The above results provide reliable theoretical references for the realistic applications of Pt-Ni nanoclusters and suggest feature engineering for future studies on binary alloys nanostructures.