Physical education occupies a very important position in university programs. Cultivating students’ physical fitness and comprehensive ability is the important significance of the existence and development of university sports. In this paper, after collecting and processing data related to students’ physical fitness tests, the K-means clustering algorithm is improved to cluster and analyze the physical fitness data of different students. Then, the FP-growth algorithm based on association rules mines the relationship between the physical fitness indicators of different groups of students, obtains the optimization strategy of physical education teaching, and introduces the logistic regression model to analyze the correlation relationship between the physical education teaching strategy based on big data optimization and students’ physical fitness. The results showed that whether the 20m round-trip running (students’ speed) was qualified or not was positively correlated with the frequency of application of physical education teaching strategies (sometimes used, not used, or occasionally used) (OR values of 1.49 and 2.12, respectively, with p-values less than 0.05) and that it was conducive to promoting the normal development of college students’ physique and physical fitness through the application of physical education teaching strategies.