Outil de grappage de graphe

Question

J'ai construit un algorithme de filtrage collaboratif (cosinus, item-item) pour révéler les relations entre les éléments. En fin de compte mes données de résultat ressemble à ceci,

itemNo relatedItemNo similarityValue 
1546301 1543903 0.10767638 
1546301 1530836 0.093250481 
1546301 1479721 0.10767638 
1557616 1573636 0.121267813 
1557616 1558024 0.161690417 
1086551 1437760 0.127000127 
1086551 1552321 0.083333333 
1086551 1578137 0.127000127 
1086551 1560842 0.081110711 
....... ....... ........... 

Maintenant, je veux faire du clustering avec. En utilisant les valeurs de similarité entre les éléments, je veux obtenir des clusters en disant 1546301, 1479721, 1543903 est dans le groupe A; 1086551,1552321, 1560842 est dans le cluster B.

Comment puis-je gérer cela? Im nouveau à l'exploration de données est donc difficile à utiliser, même des outils simples.

J'ai appris que cela s'appelle Graph Clustering et j'ai téléchargé igraph pour r, installez cluto et essayez quelques étapes mais je n'ai même pas compris le format de données d'entrée d'entre eux.

Pouvez-vous me montrer le chemin? :)

Answer 1

Le sujet du grappage de graphe est vaste et il y a beaucoup d'approches différentes, chacune avec ses propres détails spéciaux. Pour un traitement approfondi sur le sujet, s'il vous plaît voir this review. Mais, si vous cherchez quelque chose pour vous aider et en vous basant sur la description fournie jusqu'ici, vous pouvez essayer d'identifier les clusters en utilisant Centrality. Plus précisément, betweenness centrality (comme défini pour sommets) fournirait une occasion de trier les sommets du graphique (représentant des éléments) par ordre des éléments les plus couramment préférés (en supposant que votre similitude se réfère à something like this).

Faire cela en Python est une affaire de quelques lignes avec Networkx

import networkx 
G = networkx.read_edgelist("myfile.csv", delimiter="\t") #Assuming that your file is tab separated here. If it is coma separated then substitute \t for a ,. Also, it would be good to get rid of the header (i.e. the first line of the CSV. 
bc = networkx.betweenness_centrality(G) 

variable bc détient maintenant la place centrale de intermédiarité de chaque nœud. Pour trier celui-ci dans l'ordre inverse (et donc obtenir votre cluster "hubs" en premier), vous pouvez simplement bc_sorted = sorted(bc.items(),key=lambda x:x[1],reverse=True)

Vous pouvez utiliser ce qui précède comme un modèle pour "traduire" le code dans une autre langue, par exemple. R. En fait, il y a le paquet Python équivalent (igraph) qui a une métrique betweenness centrality pour les nœuds déjà implémentés ainsi qu'un Read_Edgelist qui vous permettra de lire vos données sur le disque. C'est-à-dire que le code R équivalent pour vous lancer n'est pas très différent de ces trois lignes.

Espérons que cela aide.