The Chemistry and Camera (ChemCam) instrument on board the MSL rover Curiosity has collected a very large and unique dataset of in-situ spectra and images of Mars since landing in August 2012. More than 800,000 single shot LIBS (laser-induced breakdown spectroscopy) spectra measured on more than 2,500 individual targets were returned so far by ChemCam. Such a dataset is ideally suited for the application of statistical methods for the recognition of patterns that are difficult to observe by humans. In this work, we develop an approach relying on the feature extraction method non-negative matrix factorization (NMF) and the repetition of k-means clustering to classify ChemCam spectra. A strong consistency of the clustering results among the repetitions were found, which allowed us to identify six clusters representing the dominant compositions measured by ChemCam in Gale crater so far. By tracking clusters across the rover traverse from landing to sol 2756, we are able to provide a chemostratigraphic overview of Gale crater from the ChemCam perspective. Transitions between major geologic groups (such as the Bradbury and the Mt. Sharp groups) are identifiable demonstrating that they are compositionally distinct, consistent with previous work. Compositional differences between their members also appear in the results. Furthermore, a first approach in which a random forest classifier was trained and validated with the obtained cluster assignments, reveals promising results for predicting cluster memberships of new ChemCam LIBS data acquired after sol 2756.