Discussion :

[camboui]

J'ai un ensemble d'objets et un ensemble de propriétés (tous indépendants).
Chaque objet possède un certain nombre de propriétés.

Je souhaiterais trouver 3 sous-ensembles (disjoints) de l'ensemble des propriétés de sorte à ce qu'un maximum d'objets puissent retrouver ses propriétés dans un des 3 sous-ensembles (donc de minimiser les objets ne trouvant pas ses propriétés groupées dans un même sous-ensemble).
En d'autres mots, il s'agit de grouper (en 3) un maximum d'objets qui partagent les mêmes propriétés.

Exemples de propriété:
rond, triangle, carré, vert, rouge, bleu.

Exemples d'objets:
rond-rouge, triangle-vert, carré-bleu, triangle-carré, vert-bleu, rond-vert-bleu.

Les sous-ensembles de propriétés pourraient être:
(1) rond, rouge
(2) triangle, vert
(3) carré, bleu

Ainsi donc "rond-rouge" se trouve dans (1), "triangle-vert" dans (2) et "carré-bleu" dans (3).
"triangle-carré", "vert-bleu" et "rond-vert-bleu" seraient exclus des 3 sous-ensembles.

Voilà, je ne vois pas trop comment faire ce genre de groupement optimisé (et pouvoir le prouver).
Merci pour vos lumières

[Matthieu Brucher]

Je pense que c'est plus de la modélisation que de l'algorithmie, non ?

Faire une composition de ta classe pour qu'elle prenne en plus un ensemble de propriétés par exemple.

[camboui]

Euh... je ne comprends pas.

La modélisation est faite: des objets possédant des propriétés.

Je cherche désormais à grouper les objets au mieux en fonction des propriétés partagées (en passant par un groupement des propriétés). Je dois obtenir 3 groupes. Non pas que "3" soit important, mais ce nombre est un paramètre imposé et indépendant du nombre d'objets et de propriétés.
Pour faire ce groupement, il me faut une méthode, un algorithme. Enfin, il me semble, non?

[ToTo13]

Bonjour,

ceci est un problème typique de classification.
Essais de regarder du coté des classificateur déjà existant, il y en a des génériques.
Sinon il te faudra en faire un toit même en apprenant les réseaux bayésiens, ...

[camboui]

Merci.
C'est la première fois que j'entends parler des réseaux Bayésiens.
Je viens de fouiller un peu sur google, et ça semble être utile à mon problème. Mais je n'ai pas trouvé de classificateurs "génériques". Tu as des exemples?

Un problème analogue serait de répartir au mieux les marchandises dans les rayons d'un supermarché en fonction des habitudes des consommateurs (afin de minimiser leurs allées et venues). Les "objets" sont les consommateurs et les "propriétés" sont les marchandises.

Autre exemple, répartir les livres dans les 3 bâtiments d'une bibliothèque en fonction des habitudes des lecteurs (afin de minimiser leurs déplacements d'un bâtiment à l'autre). Les "objets" sont les lecteurs et les "propriétés" sont les livres (classés par thème).

Vous l'aurez compris, mon problème est très proche de ce deuxième cas de figure
On m'a confié cette tâche en croyant que se serait résolu "rapidement" rien qu'en passant dans une "petite moulinette" la liste des lecteurs et des thèmes qu'ils consultent.
Je constate que la "petite moulinette" est loin d'être triviale...

[Matthieu Brucher]

Les réseaux bayesiens, ça sert surtout quand on a des lois de probabilités, pour modéliser les dépendances, pas sûr que ce soit le meilleur ici. En plus, c'est un peu le marteau pour écraser une mouche.
Tu as donc plusieurs propriétés, chacune étant une dimension, en quelque sorte, la forme, la couleur, ... Et tu essaies de faire passer 3 demis-plans là-dedans pour les séparer, c'est ça ?

[camboui]

Euh.. des demi-plans? Désolé je ne comprends pas

Les propriétés sont des valeurs booléennes. L'objet possède oui ou non telle ou telle propriété. "Couleur" et "forme" ne sont pas des propriétés, ce sont "rouge", "vert", "triangle", etc, qui sont des propriétés (toutes dans le même sac). J'ai sans doute semé une part de confusion en choisisant ces valeurs-là. N'en tenez pas compte, je l'ai dit, elles sont indépendantes.

Je reprends l'exemple de la bibliothèque. Il est simple finalement.
La bibliothèque contient des livres classés par thème (histoire, géographie, mathématiques, physique, etc). La bibliothèque est constituée de trois bâtiments, les thèmes sont ainsi au départ répartis "empiriquement" dans ces trois bâtiments.
Après de longues années, suite à des travaux, on se propose de réorganiser la répartition des thèmes dans les bâtiments en fonction des habitudes des lecteurs afin de les faire se déplacer le moins possible entre les bâtiments. Pour cela, on a conservé une base de données avec les thèmes consultés par les lecteurs.
Supposons que lorsque l'on regarde la base de données, on constate que les lecteurs "d'histoire" consulte souvent les "mathématiques", et que les lecteurs de "géographie" consultent souvent la "physique". Il semblera cohérent de vouloir grouper "histoire" avec "mathématiques" et "géographie" avec "physique". Mais lorsque l'on a plusieurs centaines de thèmes et plusieurs dixaines de miliers de lecteurs, il est impossible d'établir ce genre de corrélation à "la main".

A propos de probabilités, il me semble au contraire qu'elles sont peut-être utiles quelque part. Supposons par exemple que sur 10 lecteurs ayant consulté "l'histoire", 7 d'entre eux ont aussi consulté les "mathématiques". On peut en conclure qu'il y a une probabilité de 0,7 pour qu'un lecteur consultant "l'histoire" consulte aussi les "mathématiques".
Sur cette base, on pourrait construire un graphe où les sommets sont les thèmes et les arcs sont la probabilité que 2 thèmes soient consultés ensemble par un lecteur.
Mais bon, je ne vois pas trop à quoi cela servirait pour assembler les thèmes en 3 grands groupes.
Le graphe pourrait éventuellement ne pas être connexe et être constitué d'au moins 3 sous-graphes, ce qui donnerait une solution triviale (et encore, il faudrait que les sous-graphes soient de taille proportionnée). Mais ce serait un cas d'école. Dans le cas général, le graphe serait connexe.

J'espère avoir bien posé toutes les bases du problème
Merci.