L’objectif de ce tutoriel est d’introduire quelques unes des
principales fonctions du packages c3t.
Commençons par créer une grille factice de taille 4L par 5 qui
servira d’exemple pour l’utilisation des différentes fonctions. On peut
via la fonction gen_grid choisir le nombre d’individus
présents sur la grille, si certaines cases doivent être vides et si
certaines doivent être plus peuplées que les autres (être des
métropoles).
Un contexte sera généra pour chaque individu. Le nombre de variables quantatitatives et qualitatives peut être choisi. Ici on choisit de prendre 2 variables normales centrées réduites.
set.seed(123L)
x <- 4L
y <- 5L
nbIndividuals <- 100L
nbCasesVides <- 3L
nbMetropolises <- 2L
nbVariablesQuant <- 2L
grille <- gen_grid(x, y, nbIndividuals = nbIndividuals,
nbMinEmptyZones = nbCasesVides,
nbMetropolises = nbMetropolises,
nbQuantitatives = nbVariablesQuant)
data <- grille$context
individus <- grille$repartition$nbIndividuals
contiguite <- grille$contiguityRégionalisation Ascendante Hiérarchique (RAH)
Dans l’optique de trouver une solution faisable à un problème de
régionalisation avec éventuelle contrainte de taille min / et ou max, la
fonction AHR peut être utilisée. Celle-ci permet
d’appliquer un algorithme de Classification Ascendante Hiérarchique
modifié afin de respecter les contraintes de contiguïté et taille
maximale. Cette fonction va appliquer une ou plusieurs itérations de CAH
en fonction des paramétrisations données par l’utilisateur.
Plusieurs paramètres sont disponibles. Pour plus de détails voir
help("AHR"). Comme pour la CAH classique la fonction prend
une distance de liaison (linkage). Plusieurs distances sont
déjà implémentées dans le package, et sont visibles via l’appel
suivant :
available_linkages()
#> [1] "Single" "Complete" "Centroid" "Average" "Medoid" "Hausdorff"Une distance de liaison peut également être proposée par l’utilisateur sous la forme d’une fonction prenant en argument une matrice de distances entre les éléments d’un premier cluster et les éléments d’un autre.
Plusieurs distances de liaison peut être indiquées.
Contrainte de fusion
Lorsqu’il y a une contrainte de taille min, l’algorithme n’assure pas que celle-ci sera vérifiée contrairement aux autres contraintes. Des paramètres permettent de perturber le parcours de l’arbre afin de faciliter la vérification.
fusionConstraint indique s’il faut appliquer une
contrainte sur le choix de la fusion et si oui laquelle. Les
possibilités implémentées sont les suivantes :
available_fusion_constraints()
#> [1] NA "singletonMin" "singletonAny" "minMin" "sizePenalty"NA signifiant qu’aucune contrainte n’est ajoutée.
fusionConstraintMode définit comment la contrainte de
fusion (si elle existe) doit être appliquée.
available_fusion_modes()
#> [1] "deterministic" "random"Plusieurs contraintes et modes de fusions peuvent être demandées.
Situation initiale
Plutôt que de démarrer du bas de l’arbre, c’est-à-dire de la partition triviale (1 élément = 1 cluster), il est possible de démarrer de plus profond et peut-être d’obtenir de meilleur résultat d’un point de vue global ou du point de vue du respect de l’éventuelle contrainte de taille minimale.
L’utilisateur peut choisir s’il souhaite ne démarrer que du bas de
l’arbre (de manière classique) ou également essayer de démarrer à partir
d’une ou plusieurs partitions initiales générées aléatoirement. C’est ce
que permet le paramètre nbTries, indiquant le nombre de
situations initiales à tester, dont la
classique.propFusionsInit indique à quel point les
partitions obtenues aléatoirement doivent être récupérées profondément
dans l’arbre.
Critères
Un ou plusieurs critères de classification peuvent être calculés sur les différentes solutions faisables, si elles existent. Plusieurs critères sont disponibles :
available_criteria()
#> [1] "CHI" "Dunn" "Silhouette"Le critère du score de silhouette n’est disponible que si le package
cluster est installé.
Pour cet exemple nous choisissons le critère “CHI”, c’est-à-dire l’indice de Calinski-Harabasz. Celui-ci nécessite qu’un contexte soit donné et que toutes ses variables soient quantitatives.
critere <- "CHI"Application
Appliquons l’algorithme sur nous données. Pour cet exemple nous fixons deux contraintes de taille non-triviale (i.e. qui ne sont pas systématiquement vérifiées) et utilisons la distance euclidienne.
m <- 5.0
M <- 40.0
d <- "euclidean"L’algorithme utilise de l’aléatoire pour la génération de partitions initiales et éventuellement l’application de contraintes de fusion. Nous fixons donc préalablement une graine aléatoire.
set.seed(123L)
resRAH <- AHR(contiguity = contiguite,
d = d, data = data,
sizes = individus,
m = m, M = M,
linkages = "saut_min",
criteria = critere,
fusionConstraints = available_fusion_constraints(),
fusionConstraintModes = available_fusion_modes(),
parallel = FALSE)
#> ℹ Starting time: 2023-11-28 11:58:30.315877
#> ℹ 45 AHC to evaluate
#> → 432 non-trivial regionalisations obtained
#> ✔ 56 feasible partitions obtained
#> → 18 redundancies have been removed.
#> → Calculation of the CHI criterion
#> → Execution time: 4.23357248306274La fonction renvoie une liste de 3 tibble. Les solutions
faisables sont contenues dans results :
resRAH$results %>%
select(nbClusters, partition, CHI) %>%
head()
#> # A tibble: 6 × 3
#> nbClusters partition CHI
#> <int> <named list> <dbl>
#> 1 3 <int [20]> 2.39
#> 2 4 <int [20]> 2.32
#> 3 4 <int [20]> 2.27
#> 4 3 <int [20]> 2.18
#> 5 3 <int [20]> 2.04
#> 6 5 <int [20]> 1.9538 solutions faisables distinctes ont été obtenues.
La solution en elle-même se trouve dans la colonne
partition. Voici la solution faisable qui offre le meilleur
indice de Calinski-Harabasz parmi celles trouvées :
regionalisation <- resRAH$results$partition[[1L]]
regionalisation
#> [1] 1 2 2 1 1 1 3 1 3 3 1 3 1 1 1 3 1 1 1 3Celle-ci vérifie bien les contraintes de contiguïté et de taille :
is_feasible_solution(regionalisation, contiguite,
individus, m, M)
#> [1] TRUEAmélioration de la solution faisable
Une solution faisable ayant été obtenue, on souhaite l’améliorer au
regard d’un certain critère tout en préservant les contraintes. C’est ce
que permet de faire la fonction enhance_feasible.
En conservant notre critère précédent (Calinski-Harabasz), on regarde si celui-ci peut être amélioré. On regarde également si le critère d’optimisation locale (“AHC”) permet d’améliorer l’ICH. Le critère “AHC” nécessite une distance de liaison. On propose d’utiliser les distances de saut minimal et maximal.
criteresAmelioration <- c("AHC", "CHI")
set.seed(123L)
resEnhance <- enhance_feasible(regionalisation,
contiguity = contiguite,
d = d, data = data,
sizes = individus,
m = m, M = M,
enhanceCriteria = criteresAmelioration,
linkages = c("single", "complete"),
parallel = FALSE,
verbose = TRUE)
#> → Evaluation of the 3 enhancements
#> → Calculation of 1 evaluation criteria on the initial partition
#> → Calcul of 1 evaluation criteria on the 3 enhanced partitions
resEnhance$results %>% select(-tempsCalcul_mins)
#> # A tibble: 3 × 6
#> criterion linkage statut iterations regionalisationOpti dt_CHI
#> <chr> <chr> <chr> <int> <list> <dbl>
#> 1 AHC Single amelioration 1 <int [20]> -0.258
#> 2 AHC Complete amelioration 6 <int [20]> -1.61
#> 3 CHI NA amelioration 1 <int [20]> 0.117L’optimisation sous l’ICH permet d’augmenter cet indice de 0,1 , soit une amélioration d’environ 4%. La solution proposée est bien une solution faisable :
partitionCHI <- resEnhance$results$regionalisationOpti[[3L]]
is_feasible_solution(partitionCHI,
contiguite,
individus, m, M)
#> [1] TRUERégularisation
Supposons que l’algorithme AHR n’ait pas pu fournir une
solution faisable (ce qui ne peut être le cas que s’il y a une
contrainte de taille minimale). La fonction
resolve_unfeasible va essayer de fournir une solution
faisable à partir d’une solution qui vérifie la contrainte de contiguïté
mais pas forcément les contraintes de taille.
Prenons par exemple la partition suivante :
regInfaisable <-
c(1L, 2L, 3L, 2L, 2L, 2L, 2L, 2L, 2L, 4L,
4L, 2L, 4L, 4L, 4L, 4L, 4L, 4L, 4L, 4L)Celle-ci est composée de 4L clusters. On peut vérifier que tous ses clusters sont bien des régions, mais qu’elle ne vérifie pas les contraintes de tailles fixées précédemment. Le premier cluster est trop petit et le quatrième trop grand.
is_regionalisation(regInfaisable, contiguite)
#> [1] TRUE
clusters_sizes(regInfaisable, individus)
#> 1 2 3 4
#> 3 31 23 43resolve_unfeasible va à partir de de régionalisation
proposer une solution faisable, en augmentant la taille du premier
cluster et en baissant la taille du dernier.
set.seed(123L)
resolution <- resolve_unfeasible(contiguity = contiguite,
sizes = individus,
data = data,
d = d, m = m, M = M,
regionalisation = regInfaisable,
verbose = TRUE)
#> → Transfert of elements one-by-one
#> ✔ fully resolved partition
resolution
#> $status
#> [1] "fully_resolved"
#>
#> $itTransfers
#> [1] 6
#>
#> $itFusions
#> [1] 0
#>
#> $initialSmallRegions
#> [1] 1
#>
#> $finalSmallRegions
#> NULL
#>
#> $initialBigRegions
#> [1] 4
#>
#> $finalBigRegions
#> NULL
#>
#> $resolvedRegions
#> [1] 1 4
#>
#> $initialRegionsSizes
#> 1 2 3 4
#> 3 31 23 43
#>
#> $finalRegionsSizes
#> 1 2 3 4
#> 7 35 23 35
#>
#> $regionalisation
#> [1] 1 1 2 3 3 3 3 3 3 4 4 3 4 3 3 4 4 3 3 3
#>
#> $initialNbClusters
#> [1] 4
#>
#> $finalNbClusters
#> [1] 4La fonction a obtenu une solution faisable en réalisant six transferts d’éléments. Tous les contraintes sont désormais respectées. En particulier, la solution est bien une régionalisation :
is_regionalisation(resolution$regionalisation, contiguite)
#> [1] TRUE