Last active
November 14, 2016 16:17
-
-
Save MaxHalford/8496a65571d0693593d42c9c46dd2a0e to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
''' | |
Le principe de cet algorithme est de parcourir les utilisateurs en "chaînant" | |
leurs attributs. Chaque utilisateur est défini par un tuple de valeurs, par | |
exemple un utilisateur peut être défini par un tupe (email, téléphone). | |
L'algorithme parcourt les utilisateurs de façon récursive. On commence avec le | |
premier utilisateur. On regarde alors son premier attribut (l'email par | |
exemple, ca n'a pas d'importance). On va alors chercher tous les utilisateurs | |
qui possède le même attribut et va alors faire exactement pareil pour cet | |
utilisateur. A chaque que l'on étudie un utilisateur on peut le retirer de la | |
liste initiale et le mettre dans un cluster (qui correspond à un utilisateur | |
unique). Cela permet de ne pas re-éssayer de matcher un utilisateur à cluster | |
alors qu'il l'a déjà. | |
En d'autres termes on a une liste de "pseudo-utilisateurs" que l'on va fusionner | |
en un cluster en chaînant les attributs qui se correspondent. | |
L'exemple suivant créé 3 clusters (de taille 3, 2 puis 1). Le premier | |
utilisateur est un tuple ('a', '1'). On créé un cluster à partir de cet | |
utilisateur. On cherche les utilisateurs qui ont 'a' pour email et on en trouve | |
aucun. On cherche les utilisateurs qui ont pour numéro '1' et on trouve le | |
deuxième utilisateur. On l'ajoute alors au cluster formé par le premier | |
utilisateur. L'algorithme est récursif et donc on va réitérer ce qu'on a fait | |
pour l'utilisateur 2. On trouve alors que l'utilisateur 3 a le même email que | |
l'utilisateur 2. Les utilisateurs 1 et 3 n'ont rien en commun mais l'utilisateur | |
2 fait le lien entre les deux. | |
Pour ceux que ça intéresse je me suis inspiré de l'algorithme DBSCAN. | |
''' | |
# Original data | |
users = [ | |
{ | |
'email': 'a', | |
'number': '1', | |
}, | |
{ | |
'email': 'b', | |
'number': '1', | |
}, | |
{ | |
'email': 'b', | |
'number': '2', | |
}, | |
{ | |
'email': 'd', | |
'number': '3', | |
}, | |
{ | |
'email': 'd', | |
'number': '4', | |
}, | |
{ | |
'email': 'e', | |
'number': '5', | |
}, | |
] | |
clusters = [] | |
def merge(index=0, cluster=None, depth=0): | |
new_user = users[index] | |
del users[index] | |
if cluster is None: | |
cluster = [new_user] | |
# For each coordinate, find the users that share it | |
for key, value in new_user.items(): | |
for i, user in enumerate(users): | |
if user[key] == value: | |
cluster.append(user) | |
merge(index=i, cluster=cluster, depth=depth+1) | |
if depth == 0: | |
clusters.append(cluster) | |
return | |
while len(users) > 0: | |
merge() | |
for i, cluster in enumerate(clusters): | |
print(i, cluster) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment