Clustering air mass trajectories is used to identify source regions of certain chemical species. Current clustering methods only use the trajectory coordinates as clustering variables, and as such, are unable to differentiate between similar shaped trajectories that have different source regions and/or seasonal differences. This can lead to a higher variance in the chemical composition within each cluster and loss of information. We propose an adaptive K-means clustering algorithm that uses both the trajectory variables and the associated chemical value. We show, using carbon monoxide data from the Cape Verde for 2007, that our method produces a far more informative clustering than the existing standard method, whilst achieving a lower level of subjectivity.