Regroupement de réseaux de numéros 1D

Question

Disons que j'ai un tableau comme celui-ci :

[1,1,2,3,10,11,13,67,71]

Existe-t-il un moyen pratique de partitionner le tableau comme ceci ?

[[1,1,2,3],[10,11,13],[67,71]]

J'ai parcouru des questions similaires, mais la plupart des gens ont suggéré d'utiliser les k-means pour regrouper les points, par exemple scipy qui est assez déroutant à utiliser pour un débutant comme moi. De plus, je pense que les k-means sont plus appropriés pour le clustering à deux ou plusieurs dimensions, n'est-ce pas ? Existe-t-il des moyens de partitionner un tableau de N nombres en plusieurs partitions/clusters en fonction des nombres ?

Certaines personnes suggèrent également un partitionnement rigide des plages, mais cela ne donne pas toujours les mêmes résultats que attendus

Answer 1

N'utilisez pas d'algorithmes de clustering multidimensionnels pour un problème unidimensionnel. Une seule dimension est beaucoup plus spécial que vous ne le pensez naïvement, car vous pouvez en fait trier ce qui rend les choses beaucoup plus faciles.

En fait, on ne parle généralement pas de regroupement, mais plutôt de segmentation ou d'optimisation des ruptures naturelles.

Vous pouvez consulter Jenks Natural Breaks Optimisation et des méthodes statistiques similaires. Estimation de la densité par noyau est également une bonne méthode à examiner, avec un solide bagage statistique. Les minima locaux de densité sont de bons endroits pour diviser les données en clusters, avec des raisons statistiques pour le faire. KDE est peut-être la méthode la plus solide pour regrouper des données unidimensionnelles.

Avec KDE, il devient à nouveau évident que les données unidimensionnelles se comportent beaucoup mieux. En 1D, vous avez des minima locaux ; mais en 2D, vous pouvez avoir des points de selle et de tels points de fractionnement "peut-être". Voyez ceci Illustration Wikipedia d'un point de selle comme la façon dont un tel point peut ou non être approprié pour diviser les clusters.

Voir cette réponse pour un exemple de la façon de procéder en Python (les marqueurs verts sont les modes de regroupement ; les marqueurs rouges sont les points où les données sont coupées ; l'axe y est une log-vraisemblance de la densité) :

Answer 2

Cet algorithme simple fonctionne :

points = [0.1, 0.31,  0.32, 0.45, 0.35, 0.40, 0.5 ]

clusters = []
eps = 0.2
points_sorted = sorted(points)
curr_point = points_sorted[0]
curr_cluster = [curr_point]
for point in points_sorted[1:]:
    if point <= curr_point + eps:
        curr_cluster.append(point)
    else:
        clusters.append(curr_cluster)
        curr_cluster = [point]
    curr_point = point
clusters.append(curr_cluster)
print(clusters)

L'exemple ci-dessus regroupe les points dans un groupe, de sorte que chaque élément d'un groupe a une taille maximale de 1 000 pixels. eps loin d'un autre élément du groupe. C'est comme l'algorithme de clustering DBSCAN con eps=0.2, min_samples=1 . Comme d'autres l'ont fait remarquer, les données 1d vous permettent de résoudre le problème directement, au lieu d'utiliser les gros calibres comme DBSCAN .

L'algorithme ci-dessus est 10-100x plus rapide pour certains petits ensembles de données avec <1000 éléments que j'ai testés.

Answer 3

Vous pouvez rechercher des algorithmes discrétisés. Le problème de discrétisation 1D est très similaire à ce que vous demandez. Ils décident des points de coupure, en fonction de la fréquence, de la stratégie de binning, etc.

weka utilise les algorithmes suivants dans son processus de discrétisation.

weka.filters.supervised.attribute.Discretize

utilise soit la méthode MDL de Fayyad & Irani soit le critère MDL de Kononeko

weka.filters.unsupervised.attribute.Discretize

utilise le binning simple

Answer 4

CKwrap est une fonction de clustering k-means rapide et simple, bien qu'un peu légère en termes de documentation.

Exemple d'utilisation

pip install ckwrap

import ckwrap

nums= np.array([1,1,2,3,10,11,13,67,71])
km = ckwrap.ckmeans(nums,3)

print(km.labels)
# [0 0 0 0 1 1 1 2 2]

buckets = [[],[],[]]
for i in range(len(nums)):
    buckets[km.labels[i]].append(nums[i])
print(buckets)
# [[1, 1, 2, 3], [10, 11, 13], [67, 71]]
exit()

Je pense que les auteurs souhaitaient que vous utilisiez la fonctionnalité de tableau nd plutôt que de créer une liste de listes.

d'autres mesures :

km.centers
km.k
km.sizes
km.totss
km.betweenss
km.withinss

L'algorithme sous-jacent est basé sur ce qui suit article .

Answer 5

Réponse tardive et juste pour mémoire. Vous pouvez partitionner un tableau 1D en utilisant Ckmeans.1d.dp .

Cette méthode garantit l'optimalité et elle est O(n^2), où n est le nombre d'observations. L'implémentation est en C++ et il existe un wrapper en R.