BACKGROUND: Patient-reported joint instability after total knee arthroplasty (TKA) is difficult to quantify objectively. Here, we apply machine learning to cluster TKA subjects using nine literature-proposed gait parameters as knee instability predictors and explore cluster reliability and consistency with self-organizing map (SOM) and k-means computation. METHODS: Subjects with TKA were retrieved from a data repository, supplemented by TKA patients with self-reported knee instability. Healthy elderly subjects, serving as control group for gait features, were added as well. All subjects have undergone identical gait analysis testing. Gait parameters (in singularity or combination) were used to cluster subjects using SOM and k-means and to identify the best split. Once clustered, comparisons between groups were performed. RESULTS: From all gait parameter combinations tried across the 91 TKA subjects, dynamic joint stiffness (DJS) was the single parameter that gave high reliability, was reasonably consistent, and singularly clustered all but one of the known unstable subjects. This TKA cluster, which contained 11 presumably unstable subjects, showed higher DJS (0.57) than the cluster containing the remaining TKA subjects (0.23). Interestingly, the latter had a DJS similar to that of the 34 healthy subjects (0.24). Additionally, during swing, the cluster with the presumably unstable subjects exhibited lower antero-posterior motion with a higher-than-normal biceps/rectus femoris activity ratio. CONCLUSION: Using machine learning, DJS emerged as the most powerful variable to cluster TKA subjects into presumably stable and unstable groups based on gait. Future hypothesis driven, prospective research has to verify the observations made in this retrospective discovery work.