With the growing maturity of big data technology, the traditional college students’ employment guidance methods in institutions of higher education have exposed the problems of low data processing efficiency and rough data classification. In order to realize the innovation of employment guidance methods, this paper takes data mining technology as the basis, establishes the mining object and establishes the database, and after completing the pre-processing and filling of students’ employment data, improves the C4.5 algorithm in the decision tree algorithm to realize the efficient processing of data mining. The MSK algorithm based on K-means algorithm is proposed to achieve effective clustering and classification of student employment data. The employment data of college students at a higher education institution is selected as the research sample, and the clustering results are analyzed after data mining is performed. Taking the 582 students of the computer network technology major in class 2020 as an example, the clustering results of their school performance are divided into six categories: leadership, mediocrity, general, application, learning, and all-around. Regression analysis of the clustering results of the students’ school performance and the degree of students’ employment gain was carried out, and the regression coefficients of the violation penalty variable in the regression of employability, career planning ability, and entrepreneurial ability were −0.145, −0.116, and −0.112, respectively, which showed a negative impact, while the rest of the variables all had a positive impact.