Regroupement non supervisé avec un nombre inconnu de clusters

Question

J'ai un grand ensemble de vecteurs en 3 dimensions. J'ai besoin de regrouper ces vecteurs en fonction de la distance euclidienne de sorte que tous les vecteurs dans un cluster particulier aient une distance euclidienne entre eux inférieure à un seuil "T".

Je ne sais pas combien de clusters existent. À la fin, il peut y avoir des vecteurs individuels qui ne font pas partie d'un cluster parce que leur distance euclidienne n'est pas inférieure à "T" avec aucun des vecteurs de l'espace.

Quels algorithmes / approches existants devraient être utilisés ici?

Answer 1

Vous pouvez ne pas avoir de solution : c'est le cas lorsque la distance entre deux points de données d'entrée distincts est toujours supérieure à T. Si vous voulez calculer le nombre de clusters uniquement à partir des données d'entrée, vous pouvez consulter MCG, une méthode de regroupement hiérarchique avec un critère d'arrêt automatique : consultez l'article de séminaire gratuit sur https://hal.archives-ouvertes.fr/hal-02124947/document (contient des références bibliographiques).

Answer 2

Je avais besoin d'un moyen de trier "fuzzy" les lignes de la sortie OCR, lorsque la sortie est parfois désordonnée, mais au sein des blocs, les lignes sont généralement en ordre. Dans ce cas, les éléments à trier sont des dictionnaires, qui décrivent des mots à une position 'x', 'y' et avec une taille 'w', 'h'. Les algorithmes de clustering généraux semblaient superflus et je devais maintenir l'ordre des éléments pendant le tri. Ici, je peux définir la tolérance tol à environ 1/4 de l'espacement des lignes, et cela est appelé avec le champ étant 'y'.

def fuzzy_lod_sort(lod, field, tol):
    # tri flou des lod en bacs dans +/- tol
    # maintenir l'ordre original.

    # déterminer d'abord les bacs.
    val_list = [d[field] for d in lod]
    vals_sorted = sorted(val_list)

    bins_lol = []
    i = 0
    for j, v in enumerate(vals_sorted):
        if not j:
            bins_lol.append([v])
            continue

        cur_bin_avg = statistics.mean(bins_lol[i])
        if abs(cur_bin_avg - v) <= tol:
            bins_lol[i].append(v)
            continue

        i += 1
        bins_lol.append([v])

    # maintenant trier dans les bacs, en maintenant l'ordre original.
    # les bacs seront le centre de la plage de 'y'.
    bins = [statistics.mean(binlist) for binlist in bins_lol]

    # initialiser la liste des bacs
    lolod = []
    for _ in range(len(bins)):
        lolod.append([])

    for d in lod:
        bin_idx = closest_bin_idx(bins, d[field])
        lolod[bin_idx].append(d)

    # maintenant joindre les bacs.
    result_lod = []
    for lod in lolod:
        result_lod.extend(lod)

    return result_lod

def closest_bin(bins, val):
    return min(bins, key=lambda bin:abs(bin - val))

def closest_bin_idx(bins, val):
    return bins.index(closest_bin(bins, val))

Le problème est que les coordonnées 'y' de la sortie OCR sont basées sur le contour autour du mot et un mot ultérieur sur la même ligne pourrait avoir une coordonnée 'y' inférieure à un mot précédent. Un tri complet par 'y' ne fonctionne donc pas. C'est très similaire à l'algorithme de clustering, mais l'intention est un peu différente. Je ne suis pas intéressé par les statistiques des points de données, mais je suis intéressé par le cluster exact dans lequel chaque élément est placé et il est également important de maintenir l'ordre original.

Peut-être y a-t-il un moyen de tri flou en utilisant les fonctions de tri intégrées, et cela pourrait être une alternative aux options de clustering pour les problèmes 1-D.