Je veux regrouper les nombres dans une liste, en fonction de la taille des nombres par rapport à leurs voisins, mais je veux le faire en continu et via le clustering si possible. Pour clarifier, laissez-moi vous donner un exemple:
Supposons que vous ayez la liste
import numpy as np from sklearn.cluster import KMeans lst = [10, 11.1, 30.4, 30.0, 32.9, 4.5, 7.2] km = KMeans(3,).fit(np.array(lst).reshape(-1,1)) print(km.labels_) # [0 0 1 1 1 2 2]: OK output lst = [10, 11.1, 30.4, 30.0, 32.9, 6.2, 31.2, 29.8, 12.3, 10.5] km = KMeans(3,).fit(np.array(lst).reshape(-1,1)) print(km.labels_) # [0 0 1 1 1 2 1 1 0 0]. Desired output: [0 0 1 1 1 1 1 1 2 2]
alors, si nous avons 3 groupes, il est évident comment regrouper. L'exécution de l'algorithme k-means à partir de sklearn (voir le code) le confirme. Mais, lorsque les chiffres de la liste ne sont pas si «pratiques», je rencontre des problèmes. Supposons que vous ayez la liste:
lst = [0,0,1,1,1,1,1,1,2,2]
Mon problème est maintenant double:
Je veux une sorte de clustering «linéaire, préservant l'ordre», qui prend en compte l'ordre des données. Pour la liste ci-dessus, l'algorithme de clustering devrait me donner une sortie souhaitée du formulaire
lst = [10, 11.1, 30.4, 30.0, 32.9, 6.2, 31.2, 29.8, 12.3, 10.5]
Si vous regardez cette sortie ci-dessus, vous voyez également que je veux que la valeur 6.2 soit regroupée dans le deuxième cluster, c'est-à-dire que je veux que l'algorithme de cluster le voie comme une valeur aberrante, pas comme un cluster entièrement nouveau .
MODIFIER Pour clarifier, je veux être en mesure de spécifier la quantité de clusters dans le processus de clustering linéaire, c'est-à-dire le «total final» des clusters.
Code:
lst = [10, 11.1, 30.4, 30.0, 32.9, 4.5, 7.2]
4 Réponses :
J'aborderais cela en quelques passes. Tout d'abord, j'aurais une première fonction / méthode pour faire l'analyse pour déterminer les centres de regroupement, pour chaque groupe et renvoyer un tableau de ces centres. Je prendrais ensuite ces centres avec la liste dans une autre fonction / méthode pour assembler une liste de l'identifiant de cluster de chaque numéro de la liste. Je retournerais alors cette liste triée.
Comme mentionné, je pense qu'un moyen simple (ish) d'obtenir les résultats souhaités est simplement d'utiliser un clustering K-means normal, puis de modifier la sortie générée comme vous le souhaitez.
Explication: L'idée est d'obtenir les résultats K-means, puis de les parcourir: en gardant une trace du groupe de clusters de l'élément précédent et du groupe de clusters actuel, et en contrôlant les nouveaux clusters créés sous conditions. Explications dans le code.
print(km.labels_) result = linear_order_clustering(km.labels_) print(result) [1 1 0 0 0 2 0 0 1 1] [0, 0, 1, 1, 1, 1, 1, 1, 2, 2]
Notez que je n'ai testé cela qu'avec une tolérance pour 1 valeur aberrante, et je ne peux pas promettre que cela fonctionne tel quel dans tous les cas. Cela devrait cependant vous aider à démarrer.
Résultat:
import numpy as np
from sklearn.cluster import KMeans
lst = [10, 11.1, 30.4, 30.0, 32.9, 4.5, 7.2]
km = KMeans(3,).fit(np.array(lst).reshape(-1,1))
print(km.labels_)
# [0 0 1 1 1 2 2]: OK output
lst = [10, 11.1, 30.4, 30.0, 32.9, 6.2, 31.2, 29.8, 12.3, 10.5]
km = KMeans(3,).fit(np.array(lst).reshape(-1,1))
print(km.labels_)
# [0 0 1 1 1 2 1 1 0 0]. Desired output: [0 0 1 1 1 1 1 1 2 2]
def linear_order_clustering(km_labels, outlier_tolerance = 1):
'''Expects clustering outputs as an array/list'''
prev_label = km_labels[0] #keeps track of last seen item's real cluster
cluster = 0 #like a counter for our new linear clustering outputs
result = [cluster] #initialize first entry
for i, label in enumerate(km_labels[1:]):
if prev_label == label:
#just written for clarity of control flow,
#do nothing special here
pass
else: #current cluster label did not match previous label
#check if previous cluster label reappears
#on the right of current cluster label position
#(aka current non-matching cluster is sandwiched
#within a reasonable tolerance)
if (outlier_tolerance and
prev_label in km_labels[i + 1: i + 2 + outlier_tolerance]): label = prev_label #if so, overwrite current label
else:
cluster += 1 #its genuinely a new cluster
result.append(cluster)
prev_label = label
return result
à moins que je ne me trompe, vous pouvez maintenant vous retrouver avec plus de clusters qu'initialement donné en entrée?
oui, comme c'est nécessaire pour le clustering linéaire. essentiellement, un groupe tel que [0,0,0,1,1,1,1,0,0,0] serait nécessairement regroupé en 3 clusters linéaires.
Je vois, j'aurais peut-être dû être plus clair: je veux être capable de spécifier la quantité de clusters avec lesquels nous nous retrouvons (donc après le clustering linéaire). Une idée de la manière la plus efficace? Je ne peux pas imaginer qu'une sorte de boucle for soit la meilleure solution.
Ah oui, ça a du sens. dans ce cas, à moins que vous ne souhaitiez simplement travailler avec une solution itérative (choisir des clusters de plus en plus petits pour le k initial signifie le regroupement et le nombre de clusters finaux après le regroupement par ordre linéaire), Vous avez peut-être conçu une solution de clustering personnalisée. Vous pouvez également modifier la sortie actuelle pour obtenir la sortie souhaitée, en prenant simplement les sorties à cette étape et en fusionnant les clusters les plus proches les uns des autres (mais en ne vérifiant que les clusters adjacents pour les candidats à la fusion)
Définissez un seuil.
Si les valeurs de x [i] et x [i-1] diffèrent trop, commencez un nouveau segment .
Pour de meilleurs résultats, regardez les approches KDE et CUSUM.
N'utilisez pas de clustering. Il a un objectif différent.
J'ai eu un problème similaire et je l'ai résolu comme suit:
Il semble que la méthode ascendante donne de meilleurs résultats, mais YMMV.
Voici le code de la méthode ascendante (en R). Il construit:
merge où chaque ligne comprend deux colonnes avec les indices des deux éléments suivants à fusionner - index négatif pour les éléments et index positif pour les sous-clusters créés précédemment (R utilise des indices basés sur 1 ) height contenant la distance entre les deux éléments / sous-clusters fusionnés. Ceci est ajouté à la hauteur maximale des éléments fusionnés (hauteur 0 pour les éléments feuille) afin que les hauteurs augmentent toujours (pour l'affichage de l'arbre, ou comme R l'appelle, le "dendogramme"). Ceci peut être utilisé pour créer des objets R hclust qui peuvent être affichés et manipulés de différentes manières.
Ce n'est pas l'implémentation la plus efficace possible, mais il fait le travail dans un laps de temps raisonnable. Une approche plus efficace consisterait à réduire la taille de la matrice de distances (cela nécessiterait plus de tenue de livres pour garder une trace de la correspondance des indices entre la matrice plus petite et les éléments d'origine):
bottom_up <- function(distances, aggregation) {
aggregate <- switch(aggregation, mean=mean, min=min, max=max)
rows_count <- dim(distances)[1]
diag(distances) <- Inf
merge <- matrix(0, nrow=rows_count - 1, ncol=2)
height <- rep(0, rows_count - 1)
merged_height <- rep(0, rows_count)
groups <- -(1:rows_count)
for (merge_index in 1:(rows_count - 1)) {
adjacent_distances <- pracma::Diag(distances, 1)
low_index <- which.min(adjacent_distances)
high_index <- low_index + 1
grouped_indices <- sort(groups[c(low_index, high_index)])
merged_indices <- which(groups %in% grouped_indices)
groups[merged_indices] <- merge_index
merge[merge_index,] <- grouped_indices
height[merge_index] <- max(merged_height[merged_indices]) + adjacent_distances[low_index]
merged_height[merged_indices] <- height[merge_index]
merged_distances <- apply(distances[,merged_indices], 1, aggregate)
distances[,merged_indices] <- merged_distances
distances[merged_indices,] <- rep(merged_distances, each=length(merged_indices))
distances[merged_indices, merged_indices] <- Inf
}
return (list(merge=merge, height=height))
}
Le pracma :: Diag (distances, 1) récupère la diagonale décalée par 1 (au-dessus de la diagonale principale).
la façon dont je le vois, pourquoi ne pas obtenir la sortie de cluster normale en premier, puis la contraindre à la manière que vous jugez appropriée?
@ParitoshSingh, la seule façon pour moi de voir ce travail est de le faire manuellement et comme j'ai beaucoup de listes, je cherche un moyen de le faire sans surveillance.
oh, non, pas manuel. Si vous êtes d'accord avec la solution parfois dérangeante (comme tout outil d'apprentissage automatique le peut à la fin de la journée), vous devriez pouvoir coder quelque chose. Voyons si je peux préparer un prototype.