Clustering into teams of fixed size There is a particular team-based video game that exposes a ladder of individual ratings for each player that looks like this (player, rating, wins, losses):


*

*A, 2000, 35, 12

*B, 1900, 41, 19

*C, 1800, 20, 4

*D, 1700, 17, 5

*E, 1700, 30, 19


On each iteration players form teams of certain size (let's say 2) and play against each other. Their individual ratings change based on the outcome of the game (some kind of an ELO system).
Problem
Given sequence of those ladders find out which teams participated on each turn.
Example
Let's imagine that the next ladder is the following:


*

*A, 2014, 36, 12

*B, 1875, 41, 20

*C, 1776, 20, 5

*D, 1715, 18, 5

*E, 1700, 30, 19


It is safe to assume that teams that played were {A, D} and {B, C}. Who played vs who is not important, only which players played together in the same team.
Dimensions: total number of players ~5000, total players playing on each ladder iteration after grouping them by winners/losers (obviously they can't be in the same team) ~30 .
What I tried
My current more or less successful ad-hoc approach was to run lots of K-means with different seeds and pick one clustering that minimizes number of teams of incorrect sizes. That seems to be very crude as a) running K-means with different seeds does not actually yield lots of different results, b) it eliminates tons of valid teams.
It's kind of a unsupervised learning problem because I do not actually know if the algorithm guessed right or wrong, except I can turn it into a supervised learning problem by programmatically generating test ladders and controlling who plays who on each turn.
Thanks for reading this. Would love to hear if there are any known approaches to similar problems I can try.
 A: I don't think this is a clustering problem at all. You may have been using the wrong tool for the problem.
See: clustering algorithms like k-means will try to force all your data objects into k clusters, minimizing the sum of squared deviations.
But does it make sense in your case to minimize the sum of squared deviations? IMHO, it doesn't.
Instead, you need to choose an approach that uses all your knowledge of the data (which k-means doesn't).
In particular, you may want to break your data into three groups first: players who didn't play, players who won, and players who lost. By doing so, you will effectively eliminate the last two columns, but that is okay.
Then you may want to figure out a derived measure for your score. For example, compute the relative change in score, i.e.
$$ f(x) = \frac{\text{score}_t(x) - \text{score}_{t-1}(x)}{\text{score}_{t-1}(x)}$$
which hopefully makes players much more similar; since I assume the score change depends on the average score of the opponents.
Then, plug in your team size. If you know the teams are always of size 2, find the partitioning of the data into pairs of two player, such that the errors are the smallest. Most likely, you can just sort your data and pair even and odd.
