The number of college graduates shows a rapid growth trend, and the employment pressure of graduates increases dramatically. In order to improve the employment and entrepreneurship success rate of college graduates, this paper predicts the employment and entrepreneurship potential of college students and mines the main factors affecting their potential. The decision tree C4.5 algorithm is proposed, and the classical post pruning method is used to construct a decision tree prediction model of college students’ employment and entrepreneurship potential, according to which the corresponding classification rules are extracted. The key factors affecting college students’ employment and entrepreneurship potential are explored through the factor analysis model. Fifteen observational variables such as GPA scores are condensed and extracted, so as to extract the main factors that determine the employment and entrepreneurship potential of college students. Through analysis, it is found that the prediction model of college students’ employment and entrepreneurship potential constructed in this paper has an accuracy rate of more than 80%, and its gain assessment curve fits the best curve extremely well. The four main influencing factors that ranked top four in terms of the percentage of total variance explained were extracted through factor analysis, i.e., learning ability, practical ability, interpersonal handling ability, and vocational ability. Through the above influencing factors, the exploration and establishment of college students’ employment and entrepreneurship training mechanism is completed to provide a helpful way for college students’ smooth employment and successful entrepreneurship.