Recomendação de usuários simples – básico em python
Publicado; 20 de janeiro de 2013 Arquivado em: Desenvolvimento, Tutorial | Tags: grafo, graph, language python, networkx, python, recomendação, recomendação de usuario Deixe um comentárioUm sistema de computador que faz sugestões é chamado de Sistema de Recomendação, sempre que vejo um sistema assim tento pensar quais variáveis o site está levando em conta, já fiquei um bom tempo imaginando como o Linkedin, Youtube, Netflix e Facebook levam em conta em seus sistemas de recomendações, um sistema de recomendações depende muito do tipo de rede que você quer criar. Por exemplo um ponto que observei é que o sistema de recomendações do Linkedin é totalmente diferente do Facebook. Um foca em amizades pessoas que realmente se conhecem o outro foca em contatos pessoas com muitas conexões “500+” .
Fiz um exemplo de código baseado em uma homework que encontrei na internet. Primeira vez que programei em Python, o código é muito simples e foi utilizado a biblioteca Networkx (sugiro ver os tutoriais)
1º Construí o Grafo conforme o exercício mostra
G=nx.Graph() G.add_node('Nurse') G.add_node('Juliet') G.add_node('Tybalt') G.add_node('Capulet') G.add_node('Friar Laurence') G.add_node('Romeo') G.add_node('Benvolio') G.add_node('Montague') G.add_node('Mercutio') G.add_node('Escalus') G.add_node('Paris') G.add_edges_from([('Nurse','Juliet')]) G.add_edges_from([('Tybalt','Juliet')]) G.add_edges_from([('Capulet','Juliet')]) G.add_edges_from([('Romeo','Juliet')]) G.add_edges_from([('Romeo','Benvolio')]) G.add_edges_from([('Romeo','Montague')]) G.add_edges_from([('Romeo','Mercutio')]) G.add_edges_from([('Benvolio','Montague')]) G.add_edges_from([('Escalus','Montague')]) G.add_edges_from([('Escalus','Paris')]) G.add_edges_from([('Friar Laurence','Juliet')]) G.add_edges_from([('Friar Laurence','Romeo')]) G.add_edges_from([('Capulet','Tybalt')]) G.add_edges_from([('Capulet','Escalus')]) G.add_edges_from([('Capulet','Paris')]) G.add_edges_from([('Mercutio','Paris')]) G.add_edges_from([('Mercutio','Escalus')])
Foram criadas algumas funções como listar amigos, amigos de amigos, amigos em comum
def friends(graph, user): """método do networx para buscar os vizinhos de um node""" return set(graph.neighbors(user)) def friends_of_friends(graph,user,radius): """método do networx para buscar um subgraph a partir de um centro passo o radius dele depois disso removo os amigos para manter uma set de amigos de amigos""" return set(nx.ego_graph(G,user,radius,False).nodes()) - friends(G,user) def common_friends(graph, user1, user2): return friends(graph,user1).intersection(friends(graph,user2))
Primeiro fiz o algorítimo de apenar pegar os meus amigos de amigos e ordenar para os que mais tem amigos em comum.
def number_of_common_friends_map(graph, user): friends = friends_of_friends(graph,user,2) bigList = dict() for friend in friends: bigList[friend] = len(common_friends(graph,user,friend)) return bigList def number_map_to_sorted_list(map): return sorted(map.iteritems(), key=operator.itemgetter(1,0),reverse=True) def recommend_by_number_of_common_friends(graph, user,top): return number_map_to_sorted_list(number_of_common_friends_map(graph,user))[:top]
Uma outra forma de calcular esse algorítimo é criando algum tipo de score para os amigos mais prováveis, existem varias formas diferentes de fazer isso.
Uma forma simples de fazer isso quando se tem poucas informações é imaginar que um amigo seu que possui amizades de forma indiscriminadas (2 mil amigos), tem altas chances de trazer muitas recomendações não relevantes, comparada a amigos que possuem poucos amigos como (200~300).
[Não li nenhum artigo sobre isso, é só uma lógica]
Dado que um usuário A tem três amigos em comum com um usuario B = (f1, f2, f3).
O score dessa amizade pode ser feito por s = (1/(f1) + 1/(f2) + 1/(f3))
def influence_map(graph, user): friendsList = friends_of_friends(graph,user,2) bigList = dict() for friend in friendsList: commons = common_friends(graph,user,friend) bigList[friend] = 0 for common in commons: bigList[friend] += (1.0/len(friends(graph,common))) return bigList def recommend_by_influence(graph, user,top): return number_map_to_sorted_list(influence_map(graph,user))[:top]
Vale lembrar que esse problema é simples em casos com poucos usuários, em casos gigantes não existem memoria que aguente e é preciso trabalhar com outras soluções como banco de dados, escutei boas recomendações sobre o neo4j.