How to find Optimal K for each group in data with Kmeans clustering

The optimal number of clusters is based either on your presumptions, e.g. equal to the highest number of items, or you can determine it empirically. To do that, you run the algorithm for different numbers of k and calculate the error of the clustering, for example by calculating MSE between all members of a cluster and the cluster center. Then you'd have to make a decision between the acceptable error (which most likely decreases with the number of clusters) and whether a larger number of clusters still makes sense for the task at hand.

To reduce time complexity of the empirical approach, you can change three variables: the maximum for K, the number of iterations and the number of samples used in the parameter sweep. If you want the most optimal solution, you are best served to take the day to run this. However, if you are hard pressed for time or suspect you need to rerun this at some point, I advise you to use a subset of your data for hyperparameter searches.

More practically speaking, I think you will find k << len(items, so your search range can probably be greatly reduced. Combine that with a subset of the data points and you should save a lot of time.