Le clustering spectral
Adrien Sieg
Le clustering spectral, qu’est-ce que c’est ?
“Data drives all we do”
Le 16 avril 2018, le PDG de Facebook - Mark Zuckerberg - a dû s’expliquer devant le Congrès Américain des dérives du plus grand réseau social au monde dans l’ingérence des éléctions présidentielles américaines. Facebook est tenu coupable de deux chefs d’accusations majeurs : la vente d’espaces publicitaires à la Russie - publicités qui visaient à polariser les internautes américains pendant la campagne de 2016 - mais surtout avoir permis à Cambridge Analytica d’accéder aux profils des utilisateurs de Facebook - 80 millions de profils sont concernés. Cambridge Analytica est une agence de Marketing digitale spécialisée dans l’analyse de données à grande échelle qui veut améliorer la façon de communiquer en implémentant des “Data-driven strategies”. Ainsi Cambridge Analytica se vante “de changer le comportement grâce aux données” et fonctionne en “mélangeant le traitement quantitatif de données, la psychométrie et la psychologie comportementale” selon Le monde dans “Ce qu’il faut savoir sur Cambridge Analytica, la société au cœur du scandale Facebook” - *http://www.lemonde.fr/pixels/article/2018/03/22/ce-qu-il-faut-savoir-sur-cambridge-analytica-la-societe-au-c-ur-du-scandale-facebook_5274804_4408996.html#wuQKmXFEPDrJ3d2Q.99*
A cet égard, le slogan de Cambridge Analytica ne ment pas quand il considère que la “Data drives all we do”. Autrement dit, tout ce que nous faisons - et par exetension tout ce que nous ne faisons pas ou aurions dû faire - peut trouver échos dans nos données personnelles.
Aujourd’hui quand votre caissière vous demande d’une voix mécanique votre carte de fidélité ce n’est pas pour vous faire gagner des points cadeaux ou des bons de réductions - et par extension récompenser votre fidélité exemplaire - mais pour tracer l’historique de ce que vous achetez afin d’établir les corrélations avec les autres produits acquis. Le plus célèbre d’entre eux a été raconté par The Financial Times of London (Feb. 7, 1996) via l’article “Diaper-Beer Syndrome”. En 1996, Walmart avait établi que le samedi soir un homme d’une trentaine d’années qui se rendait dans un super-marché de l’enseigne, s’il venait acheter des couches alors statistiquement celui-ci allait également acquérir des bières. Conséquences immédiates, Walmart positionnait le rayon des couches en face de celui des bières.
Outre notre consommation alimentaire, tous les pans de notre vie sont scannés au plus près par les grandes enseignes. Et quand on sait que Facebook serait utilisé par plus d’1 personne sur 4 dans le monde - soit 2 milliards d’utilisateurs - on comprend mieux les risques.
Le capitalisme de surveillance
D’ailleurs, l’universitaire Shoshana Zuboff a baptisé en 2015 notre économie actuelle de “capitalisme de surveillance”. En effet, le business model des géants du Web (Google, Facebook, Twitter, …) est basé sur la gratuité complète de leurs offres en échange de la collecte des données personnelles des utilisateurs à des fins de publicité et de segmentation marketing. En résumé, en échange de ses données personnelles, l’utilisateur peut accéder gratuitement aux services numériques - qui permettront de cibler efficacement le consommateur en lui offrant un contenu publicitaire personnalisé.
Les données personnelles comportent évidemment toutes les informations intuitives d’idendité (âge, sexe, profession, lieu de résidence, …) mais également les comportements numériques des utilisateurs (l’historique de navigation, l’heure de navigation, le parcours de navigation, …). Les données de la navigation sont aujourd’hui une mine d’or pour les publicitaires. A tel point que suivant où un internaute pointe sa souris sur un site donnée (en haut à gauche par exemple) alors l’espace publicitaire sera plus cher que s’il pointait sa souris en bas à droite.
Le clustering spectral
Le clustering spectral est un algorithme de partitionnement des données. Supposons que vous voulez diffuser une idée ou un parler d’un produit au sein d’une population entière constituée de millions de personnes. Le temps étant limité et coûteux, il est évidemment impossible d’échanger un à un avec chaque membre de la population entière. Heureusement, cette population est structurée en plein de communautés par des liens d’amitié - par amitié on suppose que deux personnes se connaissent. Pour atteindre chaque personne de la population, il suffit de cibler des membres bien choisis de chaque communauté. Dés lors, on arrive à sous-segmenter la population totale en une sous-population de personnes influentes - où il faut alors convaincre ces personnes cibles pour espérer ensuite un effet de propagation qui permettra de toucher la population entière. En analyse multivariée, le clustering spectral s’intéresse au spectre de la matrice de similarité (ou aux valeurs propres) pour assurer une réduction de dimension avant d’appliquer une segmentation de la population dans un espace en plus petite dimension.
Application à un cas réel du clustering spectral
Petite introduction de méthodologie
Le but du jeu est donc de pouvoir partitionner et segmenter un graphe en plusieurs groupe à des fins de marketing, politique, … Rappelons qu’un graphe est construit selon une matrice adjacente - matrice qui synthétise toutes les affinités entre tous les individus composant ce graphe. Ainsi, suivant les fréquentations d’un individu, celui-ci sera affecté à un groupe spécifique. Cela est sans rappeler la théorie sociologique d’Emile Durkheim où un individu est caractérisé non pas par ce qui l’est intrinsèquement mais par ceux qui l’entourent. L’entourage et les relations d’une personne considérée sont constitutifs de qui est et sera cette personne en tant qu’individu. La société est une réalité sui generis qui façonne les individus. Schématiquement on peut résumer la pensée d’Emile Weber dans Les formes élémentaires de la sociologie : “je me définis” par qui “je fréquente, vois et rencontre”. “Ma réalité sociale est défini par l’autre”. Gare aux “mauvaises fréquentations” donc …
Quand Sarte écrit dans Huit Clos (1943) que “l’enfer c’est les autres” c’est “Parce que les autres sont, au fond, ce qu’il y a de plus important en nous-mêmes, pour notre propre connaissance de nous-mêmes. Quand nous pensons sur nous, quand nous essayons de nous connaître, au fond nous usons des connaissances que les autres ont déjà sur nous, nous nous jugeons avec les moyens que les autres ont — nous ont donnés — de nous juger.” (L’existentialisme athée, 1964)
Techniquement, pour segmenter le graphe trois étapes doivent être menées :
- Construire une matrice qui représente les affinités entre les individus
- Projeter les individus sur un plan en fonction de leurs affinités
- Appliquer une méthode classique de clustering (le plus souvent une K-means) sur ces nouvelles coordonnées.
Différence entre le K-means et le clustering spectral
Le K-Means (littéralement K-moyennes) cherche à définir k moyennes de référence au sein d’un jeu de données pour affecter chaque individu à la moyenne qui lui est la plus proche (en terme de distance). On cherche donc à partitionner le jeu de données en k groupes significatifs afin d’avoir des profils types. Le k-means est la solution à un problème d’optimisation combinatoire.
Autrement dit, deux individus sont semblables si ils sont géométriquement proches. Ce qui peut poser des problèmes car la distance n’est pas forcément révélatrice - deux individus peuvent être proches car ils se connaissent effectivement mais n’appartiennent pas à la même cependant à la même catégorie. Autre problème posé par le K-means concerne la détermination a priori du nombre de groupes. Le nombre de K-moyennes doit être déterminé en amont du clustering.
La différence entre un clustering classique et le clustering spectral :
Aucune hypothèse (donc aucun biais a priori) sur la forme du cluster. Sur la photo ci-dessus, on voit qu’un algorithme classique de partitionnement - type k-means - rassemblerait les points suivant leurs proximités respectives
Les algorithmes classiques supposent un process itératif pour trouver le minimum local
Le nombre de clusters dans les algorithmes classiques (type k-means) est défini a priori
En guise de conclusion, cette vidéo Youtube donne une vision claire et structurée des atouts et limites d’un clustering spectral.
Présentation du jeux de données
Le graphe des individus propres à l’ESCP Europe
Le jeu de données a été crée à partir de l’activité sociale des individus de l’ESCP Europe sur le réseau social Twitter. Toutes ces personnes ont une relation avec l’ESCP Europe en étant étudiants, professeurs, journalistes, riverains, curieux (en ayant publié un article relatant à l’ESCP Europe). Bref, le périmètre d’étude concerne donc toutes les personnes ayant eu un lien avec l’ESCP Europe par leurs publications, ou leurs profils, … Enfin, dans la construction de cette base de données, j’ai arbitrairement considéré que deux personnes étaient connectées si :
Une personne “like” ou partage la publication d’une autre personne
Si les personnes se connaissent (sont donc amis Twitter en se suivant réciproquement)
Si une personne suit une autre personne (de façon unilatérale) - ce qui est le cas des “influencers”
Concernant le cadre méthodologique d’étude, je me suis intéressé à l’année 2017 dans son intégralité (du 01 janvier au 31 décembre), où j’ai scrappé (littéralement aspiré tous les tweets) relatif à l’ESCP Europe ou toutes les personnes affichant ESCP Europe sur leur profil suivant la définition donnée plus haut. A partir de là, j’ai dressé les relations entre les individus pour définir la matrice adjacente. La voici :
g<-graph_from_data_frame(A, directed = TRUE, vertices = NULL)
m=as.matrix(A)
g=graph.adjacency(m,mode="undirected",weighted=NULL)plot(g)
L’ESCP Europe parmi ses pairs
Pour présenter l’hypothèse précédente “avoir un lien avec l’ESCP Europe”, j’ai également regardé l’ESCP Europe parmi ses semblables / ses pairs afin d’apprécier deux choses :
- Naïvement, qu’est ce que l’ESCP Europe en terme de connexions ou autrement dit, à qui ressemble le plus l’ESCP Europe ? Voir ainsi quels sont les semblables de l’ESCP Europe à partir des individus ? On regarde les individus “appartenant à l’ESCP Europe” afin de comprendre ce qui les intéressent également. De fait, on peut tracer un historique des intérêts des individus - et voir qu’un individu qui suit l’ESCP Europe suivra statistiquement aussi d’autres écoles de commerce. Ce qui est par exemple le cas d’un candidat qui se renseigne avant ses oraux sur toutes les écoles de commerce dont il a obtenu l’admissibilité, ou un élève qui veut suivre les exploits sportifs, académiques, … de son école (une sorte de chauvinisme étudiant), ou un professeur qui s’intéresse à l’actualité académique des autres écoles. L’idée est ainsi d’avoir un point de comparaison. Cette question certes naïve, de prime abord, permet de voir que le top 20 des connexions est essentiellement tournés vers des institutions académiques.
Intuitivement on pourrait donc s’attendre à voir HEC ou l’ESSEC (les parisiennes) voire les autres écoles de commerce comme les plus connectés avec l’ESCP mais ils ne sont pas dans ce top 5. On retrouve certes des écoles mais elles ne sont pas en “concurrence directe” avec l’ESCP - il y a la Sorbonne, l’ENA et CentraleSupélec avec l’ENSAE. Vienne ensuite la Chambre de Commerce d’Île de France et HEC.
Conclusion, on retrouve donc des sponsors ou des partenariats. Etonnement par contre, on pourrait s’attendre à voir plus d’entreprises, de corps étatiques ou d’institutions diverses. On comprend donc que l’univers de l’ESCP Europe est un cercle restreint et fermé - composé exclusivement de Grandes Ecoles françaises.
- Contextualiser les individus cibles. Comprendre également d’où viennent ces individus en s’intéressant à leurs centres d’intérêts de façon perspectiviste. En effet, la première étape de notre démarche (prendre les individus qui ont un lien avec l’ESCP Europe) peut s’avérer restrictive (même si elle apparaît nécessaire dans notre démarche de modéliser puis classifier le réseau ESCP Europe)
nodes <- data.frame(id = 1:20, group = sample(c("A","B","C","D","E","F"),20,replace = T))
edges <- data.frame(from = sample(c(1:20),100,replace = T), to = sample(c(1:20),100,replace = T))
visNetwork(nodes, edges, width = "100%") %>%
visGroups(groupname = "A", shape = "icon",
icon = list(code = "f19c", size = 75)) %>%
visGroups(groupname = "B", shape = "icon",
icon = list(code = "f19c", color = "red")) %>%
visGroups(groupname = "C", shape = "icon",
icon = list(code = "f19c", color = "black")) %>%
visGroups(groupname = "D", shape = "icon",
icon = list(code = "f19c", color = "green")) %>%
visGroups(groupname = "E", shape = "icon",
icon = list(code = "f19c", color = "yellow")) %>%
visGroups(groupname = "F", shape = "icon",
icon = list(code = "f19c", color = "orange")) %>%
addFontAwesome()Graphe et matrice Laplacienne
Zoom sur la matrice adjacente
La matrice adjacente synthétise donc toutes les relations possibles entre tous les individus de notre graphe. Si deux personnes se connaissent ou intéragit ensemble alors leur relation sera définie par 1 sinon par 0 (ils n’ont eu aucune interaction). Pour apprécier visuellement cette matrice adjacente, voici une carte de chaleur (heat map) pour résumer les relations entre les individus.
heatmap.2(get.adjacency(g,sparse=FALSE),dendrogram='none',
Rowv=NA, Colv=NA,trace='none', col=c('white','blue'))
Soit A la matrice Adjacente :
Soit D la matrice des degrés :
Autrement dit, les matrices ci-dessous sont l’expression du graphe représenté ci-dessous : Pour rappel, la matrice des degrés est le nombre de liens au départ ou à l’arrivée d’un sommet alors que la matrice adjacente rend compte - de façon binaire - de l’existence ou non de liens entre les différents noeuds. Si 1 alors deux noeuds sont reliés entre eux, si 0 alors les deux noeuds ne présentent aucune connexion. En voilà un exemple :
``{r} nodes <- data.frame(id = 1:6, group = c(“A”, “A”, “B”,“A”,“B”,“B”)) edges <- data.frame(from = c(1,1,2,2,3,4,4), to = c(5,2,5,3,4,5,6))
visNetwork(nodes, edges, width = “100%”) %>% visGroups(groupname = “A”, shape = “icon”, icon = list(code = “f0c0”, size = 75)) %>% visGroups(groupname = “B”, shape = “icon”, icon = list(code = “f007”, color = “red”)) %>% addFontAwesome() ``
Construction technique de la matrice de Laplace
Une matrice Laplacienne se définit de cette façon :
La matrice Laplacienne est alors : \(L = D - A\) c’est-à-dire la matrice des degrés auquel on soustrait la matrice adjacente. Dans ce cas précis, on obtient la matrice L :
Cette matrice est donc symétrique - c’est-à-dire Hermitienne et admet une fonction Rn définit ci-dessous qui présente un intérêt utile pour déterminer les valeurs et vecteurs propres de la matrice \(A\). En effet, ces vecteurs propres coïncident exactement avec les points critiques de \(A\). Ainsi les valeurs propres de \(A\) sont les valeurs en les points critiques.
Construction de la matrice de Laplace \(L = D - A\) où D est la matrice des degrés et A la matrice Adjacente
laplacian_matrix=graph.laplacian(g, norm=FALSE, sparse=FALSE)Mathématiquement, on cherche à minimiser ce quotient de Rayleigh sur tout l’espace. “Ceci donne la plus petite valeur propre (en module) et un vecteur propre associé. On considère ensuite la restriction de la fonction à l’orthogonal du vecteur propre trouvé, et on minimise à nouveau cette fonction, mais simplement sur cet orthogonal. Ceci donne la deuxième valeur propre la plus petite en module, puis on itère le procédé.”
Source : http://www.bibmath.net/dico/index.php?action=affiche&quoi=./r/rayleigh.html
\(R (A,x) = x\times{Axx}\times{x} {\displaystyle R(A,x)={\frac {x^{*}Ax}{x^{*}x}}}\)
\(R(A,B;x)={\frac {x^{T}Ax}{x^{T}Bx}}\)
\(M v_i = A' A v_i = \lambda_i v_i\) \(\Rightarrow v_i' A' A v_i = v_i' \lambda_i v_i\) \(\Rightarrow \left\| A v_i \right\|^2 = \lambda_i \left\| v_i \right\|^2\) \(\Rightarrow \lambda_i = \frac{\left\| A v_i \right\|^2}{\left\| v_i \right\|^2} \geq 0.\)
\(Mv_{i}=\lambda _{i}v_{i}\) \(\Rightarrow v_{j}'Mv_{i}=v_{j}'\lambda _{i}v_{i}\) \(\Rightarrow \left(Mv_{j}\right)'v_{i}=\lambda _{i}v_{j}'v_{i}\) \(\Rightarrow \lambda _{j}v_{j}'v_{i}=\lambda _{i}v_{j}'v_{i}\) \(\Rightarrow \left(\lambda _{j}-\lambda _{i}\right)v_{j}'v_{i}=0\) \(\Rightarrow v_{j}'v_{i}=0\)
\(x = \sum _{i=1} ^n \alpha _i v_i\) \({\displaystyle \alpha _{i}={\frac {x'v_{i}}{{v_{i}}'{v_{i}}}}={\frac {\langle x,v_{i}\rangle }{\left\|v_{i}\right\|^{2}}}}\)
Cherchons donc les deuxièmes et troisièmes vecteurs propres et valeurs propres de la matrice de Laplace \(A\).
second_eigen_vector=eigen(laplacian_matrix)$vectors[,vcount(g)-1]
third_eigen_vector=eigen(laplacian_matrix)$vectors[,vcount(g)-2]
df<-cbind(second_eigen_vector,
third_eigen_vector)
df<-as.data.frame(df)
rownames(df)<-paste0("individu_",c(1:NROW(df)))Dés lors, on peut projeter les individus non plus en forme de graphe mais dans un espace euclidien à deux dimensions - où la première dimension (x-axis) sera le 2nd vecteur propre de la matrice de Laplace \(L\) et la deuxième dimension (y-axis) sera la troisième dimension de la matrice \(L\).
ggplot(df,aes(x=second_eigen_vector, y=third_eigen_vector)) +
geom_point(shape=23, fill="blue", color="darkred", size=3) + theme_bw()
Dés lors, on peut dessiner une matrice de similarité où l’on peut rendre compte des individus qui sont proches les uns des autres. Une couleur rouge signifie qu’il existe une petite distance entre deux individus donnés alors qu’une couleur verte signifie une grande distance sépare deux individus.
res.dist <- get_dist(df, stand = TRUE, method = "pearson")
fviz_dist(res.dist,
gradient = list(low = "#00AFBB", mid = "white", high = "#FC4E07"))
Combien de clusters ?
Cette partie s’intéresse donc à trouver le nombre de clusters idéal en jouant sur deux objectifs contradictoires.
Un objectif macro qui impose un nombre minimal de clusters pour des raisons intelligibles. Il est, en effet, plus facile d’avoir 2-3-4 clusters à présenter qu’une cinquantaine.
Un objectif micro qui demande lui un nombre maximal de clusters afin de restituer au maximum la richesse du graphe. En effet, moyenniser et enfermer les “individus” dans des clusters supposent évidemment de réduire le portrait robot de chaque cluster.
fviz_nbclust(df, kmeans, method = "gap_stat")
L’index Hubert est une méthode graphique statistique pour déterminer le nombre de clusters optimaux. Dans le graphique de l’Hubert index, on cherche à trouver une cassure (littéralement un “coude”) qui correspond à une hausse marginale plus que proportionnelle dans les différences secondes du Hubert index (le second graphe)
res.nbclust <- df %>%
scale() %>%
NbClust(distance = "euclidean",
min.nc = 2, max.nc = 10,
method = "complete", index ="all") 
## *** : The Hubert index is a graphical method of determining the number of clusters.
## In the plot of Hubert index, we seek a significant knee that corresponds to a
## significant increase of the value of the measure i.e the significant peak in Hubert
## index second differences plot.
## 
## *** : The D index is a graphical method of determining the number of clusters.
## In the plot of D index, we seek a significant knee (the significant peak in Dindex
## second differences plot) that corresponds to a significant increase of the value of
## the measure.
##
## *******************************************************************
## * Among all indices:
## * 1 proposed 2 as the best number of clusters
## * 15 proposed 3 as the best number of clusters
## * 1 proposed 5 as the best number of clusters
## * 2 proposed 8 as the best number of clusters
## * 1 proposed 9 as the best number of clusters
## * 3 proposed 10 as the best number of clusters
##
## ***** Conclusion *****
##
## * According to the majority rule, the best number of clusters is 3
##
##
## *******************************************************************fviz_nbclust(res.nbclust, ggtheme = theme_minimal())## Among all indices:
## ===================
## * 2 proposed 0 as the best number of clusters
## * 1 proposed 1 as the best number of clusters
## * 1 proposed 2 as the best number of clusters
## * 15 proposed 3 as the best number of clusters
## * 1 proposed 5 as the best number of clusters
## * 2 proposed 8 as the best number of clusters
## * 1 proposed 9 as the best number of clusters
## * 3 proposed 10 as the best number of clusters
##
## Conclusion
## =========================
## * According to the majority rule, the best number of clusters is 3 .
En conclusion, on obtient donc un nombre optimal de clusters fixé à trois, i.e. on peut regrouper toute la population selon trois portraits robots. Toujours dans le même espace orthonormé de distance euclidienne - et où l’axe des axis est le second vecteur propre quand l’axe des ordonnées est le troisième vecteur propre - on obtient ces trois populations types.
km.res <- kmeans(df, 3, nstart = 25)
fviz_cluster(km.res, data = df,
ellipse.type = "convex",
palette = "jco",
ggtheme = theme_minimal())
Visuellement, on peut regrouper les individus qui sont similaires ensembles à l’aide d’un dendogramme. C’est un arbre hiérarchique qui regroupe tous les individus selon leur appartenance à leurs clusters respectifs. On distingue donc trois groupes : Les limites de ce cas empirique repose sur le caractère exhaustif de Twitter. Comme les profils sont déclaratifs, beaucoup de profils sont mal renseignés
Les personnes très actives qui “suivent, likent et partagent”" intensivement toutes les publications de l’ESCP Europe. En regardant de façon micro, aucune tendance claire ne peut se dégager car la variété des partages est sans structure - même si ce sont majoritairement des classements de la presse éducative spécialisée (classement challenge, Etudiant, …) mais on trouve aussi bien des posts sportifs, académiques, … Cette catégorie peut se résumer par son chauvinisme éducatif : tout ce qui touche à l’ESCP Europe est partagé. Cette communauté est très soudée et présente un caractère sectaire. A partir des informations partagées (un profil sur deux est renseigné), ce sont majoritairement des étudiants également attentifs aux autres tweets des autres écoles.
Le second segment concerne des personnes curieuses qui ne s’intéressent qu’aux succès de l’ESCP Europe. Les informations partagés sont souvent des annonces, des bonnes nouvelles ou des avancées (types partenariats). On trouve dans ce segment quelques journalistes, des comptes institutionnels qui se félicitent conjointement d’un partenariat avec l’ESCP Europe ou d’un retour d’expériences. Les publications sont d’ailleurs souvent conjointes.
Le troisième segment est un public très spécialisé qui ne s’intéresse qu’à des sujets touchant à des environnements de niche. Leur participation est ponctuelle (pas plus de cinq tweets, partages, … par an). Les sujets sont très souvent académiques. Ils apparaissent comme indifférent à l’ESCP Europe car ce qui les intéresse réellement sont les sujets traités. Conséquemment, ils “tweetent ou likent” indifféremment les résultats quelque soit l’école ou l’institution de recherche. Ils sont souvent professeurs (même si leur profil respectif est peu ou pas renseigné).
{r} hc <- hclust(dist(df), "ave") dendroNetwork(hc, height = 600)
Evaluation des clusters
Cette dernière partie cherche à savoir si les trois clusters sont suffisants pour résumer les profils des personnes appartenant au graphe. C’est une méthode d’interprétation et de validation de la solidité des clusters dans leur fonction de segmentation et de partitionnement.
res.hc <- df %>%
scale() %>%
eclust("hclust", k = 3, graph = FALSE)
fviz_silhouette(res.hc) + theme_bw()## cluster size ave.sil.width
## 1 1 46 0.70
## 2 2 34 0.64
## 3 3 35 0.50