Algorithme de regroupement d'objets indépendants

Question

J'ai un ensemble d'objets. Chaque objet est placé dans "l'espace" et je connais la distance entre chaque objet. Je cherche un algorithme pour grouper des objets loin les uns des autres. Je choisis le nombre de groupes. Et les groupes doivent être "équilibrés" (chaque groupe doit contenir le même nombre d'éléments).

Exemple:

Supposons que j'ai 4 objets

{ A, B, C, D } 

et i les représenter dans un espace à deux dimensions:

the points in a 2-dimension space http://i61.tinypic.com/b4ho51.png

je sais que la distance entre chaque objet donc

{ 
    AB = 1 
    AC = 3.6 
    AD = 5 
    BC = 2.8 
    BD = 4.2 
    and so on... 
} 

Je veux l'algorithme aux objets du groupe en deux groupes et devrait afficher

{[ A, C ][ B, D ]} 

the desired result http://i60.tinypic.com/2v19ok2.png

Bien sûr, cela est facile avec 4 objets, mais il est difficile avec plus d'articles.

J'ai beaucoup cherché, mais je n'ai rien trouvé pour un tel regroupement. J'ai lu beaucoup de choses sur le clustering k-means et d'autres méthodes de clustering, mais elles ne conviennent pas car elles regroupent des objets similaires.

Quelle est la meilleure solution?

EDIT

La formalisation du problème pourrait être la maximisation de la distance entre les éléments dans chaque groupe. C'est pourquoi l'algorithme devrait regrouper A et C, B et D.

A et D, B et C ce n'est pas une bonne solution.

L'algorithme doit traiter des points N (N> 2) et les groupes K (K < N, je choisis combien de groupes)

Answer 1

Mon problème n'était pas l'algorithme.Le problème formalisait le problème lui-même. Et Gene m'a aidé avec son commentaire

Vous devez formaliser la définition d'une "bonne" solution. Je suggère la somme maximale des carrés des distances par paires. Je suis convaincu que le problème de la maximisation de cette quantité est NP difficile. La solution triviale consistant à sélectionner et retirer à plusieurs reprises la «paire la plus éloignée» est facile. Alors maintenant vous êtes à une sorte de recherche. - Gene 6 juillet à 15:36

Merci

Answer 2

Vous pouvez probablement abuser des algorithmes de regroupement ici, en leur donnant une distance quand ils attendent une similitude, ou l'inverse. Jetez un oeil à la classification hiérarchique, il devrait être facile de "casser" comme vous le souhaitez. Mais plus probablement, les résultats ne seront pas très convaincants sur autre chose que de tels scénarios de jouets, parce que la «dissimilitude» n'est pas transitive.

Habituellement, lorsque A est similaire à B, et B est similaire à C, vous voudrez avoir A, B et C dans le même groupe.

Mais lorsque A est différent de B, B est différent de C, alors A et C pourraient être très similaires; donc vous ne voulez pas qu'ils se regroupent ... '' peut-être '' le regroupement complet des liens (quand les abus, comme discuté ci-dessus) peuvent fonctionner pour vous, cependant.