Classement des meilleurs groupes de données en fonction des regroupements observés dans le passé

Question

Aidez-moi à résoudre ce problème:

Je veux trouver un moyen de regrouper ces animaux. Disons que tous les jours vous observez un groupe d'animaux qui traînent comme des amis. Vous voulez déterminer la meilleure façon de regrouper les animaux en fonction de ceux qu'ils préfèrent.

Pour illustrer, vous observez:

Aujourd'hui, vous avez vu ces animaux se détendre ensemble: {Elephant Tiger girafe Peacock}

Le lendemain vous avez vu ces: {girafe Peacock Elephant Lion Singe}

et puis le lendemain: vous {Elephant Tiger Hyène Rhino}

donc de cela pourrait conclure que l'éléphant et e Tiger sont de bons amis parce qu'ils ont passé deux occasions différentes. Vous diriez la même chose pour le paon et l'éléphant.

Quel serait un algorithme pour déterminer la meilleure façon de regrouper ces animaux?

Pour donner un peu plus de détails, je travaille sur un gros problème de type de données et j'essaie de classer ce problème.

L'apprentissage automatique peut-il résoudre ce problème?

Les données réelles pourraient ressembler à ceci:

{A B F G R P K U J H} {A F G K B J H A S} et des millions de lignes de ce ...

me pointant dans la bonne direction serait utile aussi.

Answer 1

Il existe différentes façons d'aborder ce problème, mais une formulation simple pourrait consister à concevoir une fonction de notation pour un groupe d'animaux donné en fonction de vos données, puis effectuer une optimisation numérique telle que simulated annealing pour trouver la partition des animaux en groupes qui maximise approximativement votre score total. Ou si le nombre d'animaux est assez petit, vous pouvez simplement faire une recherche exhaustive de toutes les partitions.

Vous devez choisir votre fonction de pointage assurer soigneusement que vous ne finissent pas avec n groupes de taille 1 ou 1 groupe de taille n. Et n'oubliez pas de respecter la symétrie.

Vous pourriez commencer par le calcul des probabilités de chaque paire d'animaux apparaissant ensemble, puis l'échelle de l'ensemble de toutes les probabilités d'avoir une moyenne nulle, puis marquer chaque groupe G comme la somme des scores de par paires à l'échelle:

Ceci est juste un premier essai, vous devriez être en mesure de proposer de meilleures fonctions de notation.

appliquer ensuite recuit simulé pour k pas de temps:

Choose a random partition π 
for i = 0 to k: 
    T = i/k #floating point division 
    make a random transition to partition π' 
    if P_accept(π, π', T) > rand(0,1): 
     π <- π' 
return π 

Lorsqu'une transition aléatoire est un échange d'un animal d'un groupe à l'autre, y compris dans un nouveau groupe vide. P_accept est la fonction de probabilité d'acceptation que vous devez concevoir comme décrit dans l'article de recuit simulé. Cela devrait être basé sur les scores de deux partitions et la température. Le score d'une partition peut être la somme des scores de chaque groupe de la partition, par exemple. Pour plus d'informations sur la conception d'une fonction de probabilité d'acceptation, voir here.

Notez que vous n'avez pas réellement besoin d'un score absolu d'une partition pour exécuter un recuit simulé. Vous pourriez faire avec une fonction qui compare une partition à l'autre. Il y a plusieurs façons de concevoir une telle fonction, mais si vous voulez faire ressortir les gros canons, vous pouvez envisager d'utiliser un Generalized Bradley Terry Model [pdf]. Vous pouvez vous entraîner sur vos données d'entrée pour obtenir un paramètre numérique γ pour chaque animal avec la propriété:

Par exemple. Cela devrait vous donner une bien meilleure mesure de la désirabilité du groupe, et il devrait s'inscrire bien plus facilement dans le cadre de recuit simulé!