Clustering avec contrainte sur le nombre d'éléments

Hello,

J'ai une question concernant un problème de "location allocation".

La problématique:

J'ai environ 400 points répartis sur une portion de territoire. Chacun de ces points est définis par un nombre X de paramètres (ensoleillement, densité de population, nombre de moutons dans la zone...). Je cherche à effectuer un clustering qui puisse prendre en compte une condition.

Exemple

Je veux créer une clusterisation de ces points. Mais si on somme le nombre de moutons par cluster, ce nombre ne doit pas excéder 1000. Si un des clusters est pas exemple constituer de 40 points mais que la somme des moutons de ces 40 points dépassent 1000 alors il faut réduire la taille du cluster.

Je connais différents moyens d'effectuer un cluster (PCA,k-means... etc) mais aucune de ces méthodes permet d'imposer une conditions. Toutes se basent uniquement sur la maximisation de la variance des paramètres.

Connaissez-vous donc un algorithme/méthode capable d'intégrer une condition à une clusterisation ?

Merci =)

Bonjour Petchi,

Ton problème me semble très spécifique et je ne sais pas si tu vas trouver un algorithme exact que tu cherches.

Je pense que tu vas devoir toi même devoir implémenter une partie de ton problème.

À l'aide d'un arbre de décision, ne peux-tu pas segmenter de nouveau les "grappes" que tu trouves trop importantes ? Ce qui n'est sans une solution sans effet de bord.

Cordialement.

:salut:

En y réfléchissant quelques secondes (moins de temps que la rédaction de ce message), je tenterais avec un nombre de groupes décroissant : d'abord avec k (le nombre de groupes que tu souhaites atteindre) ; si cette solution ne te satisfait pas, tu essaies avec k-1 : si un groupe ne satisfait pas ta condition, tu peux tenter de le séparer en deux, avec le même algorithme de groupement, mais uniquement sur ces données (si plusieurs groupes ne satisfont pas la contrainte, passer à k-2). C'est peut-être plus intelligent de décroître du nombre de groupes qui violent ta contrainte, à voir (les deux variantes ne doivent pas être compliquées à implémenter).

Citation:

---

Envoyé par petchi

Je connais différents moyens d'effectuer un cluster (PCA,k-means... etc) mais aucune de ces méthodes permet d'imposer une conditions. Toutes se basent uniquement sur la maximisation de la variance des paramètres.

Connaissez-vous donc un algorithme/méthode capable d'intégrer une condition à une clusterisation ?

---

Ben un paramètre à ajouter (si on considère ta condition comme un paramètre) pourrait être le nombre total dans le cluster, avec une variance = 0 tant que c'est inférieur à 1000, = 1 si supérieur (pas calculée mais forcée à ce chiffre).

Sinon de toutes façons tu dois avoir une fonction dans les methodes de clustering dans laquelle tu peux insérer ce nombre total et rejeter cette solution si nb total > 1000, non ?

Je ne connais pas les algos de clustering en tant que tels mais ça doit être faisable....