The pervasive application of Small Private Online Course (SPOC) provides a powerful impetus for the reform of higher education. During the teaching process, a teacher needs to understand the difficulty of SPOC videos for students in real time to be more focused on the difficulties and key points of the course in a flipped classroom. However, existing educational data mining techniques pay little attention to the SPOC video difficulty clustering or classification. In this paper, we propose an approach to cluster SPOC videos based on the difficulty using video-watching data in a SPOC. Specifically, a bipartite graph that expresses the learning relationship between students and videos is constructed based on the number of video-watching times. Then, the SimRank++ algorithm is used to measure the similarity of the difficulty between any two videos. Finally, the spectral clustering algorithm is used to implement the video clustering based on the obtained similarity of difficulty. Experiments on a real data set in a SPOC show that the proposed approach has better clustering accuracy than other existing ones. This approach facilitates teachers learn about the overall difficulty of a SPOC video for students in real time, and therefore knowledge points can be explained more effectively in a flipped classroom.