cross_chain.py

'''
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)