Python et list
Bonjour,
J'aimerais savoir comment on peut réduire la taille du code suivant si vous voyez ce que je veux dire merci pour le coup de main !
J'aimerais savoir comment on peut réduire la taille du code suivant si vous voyez ce que je veux dire merci pour le coup de main !
S=0 for i in range(C): for X in clusters[ i]: print("X", X) print("G", G[ i]) S = S + d2(X,G[ i]) print(S)
Réponses
-
C’est difficile si on ne connaît pas la structure de clusters et de G.
Essaie peut-être avec zip.Algebraic symbols are used when you do not know what you are talking about.
-- Schnoebelen, Philippe -
On doit pouvoir faire quelque chose comme ça :
S = sum([ d2(X, G[ i]) for i in range(C) for X in clusters[ i] ])
Mais si le but est d'accélérer l'exécution, il faudrait sans doute plutôt regarder du côté de NumPy pour calculer les distances d2(X, G[ i]) « vectoriellement ». Pour ce faire, il faudrait sans doute expliciter d2 avec une ou des fonctions que Numpy peut exécuter sur un couple de vecteurs (ou peut-être directement entre une valeur et chaque composante d'un vecteur : je ne suis pas assez familier de Numpy). -
Tu peux te passer des crochets :
S = sum( d2(X, G[ i]) for i in range(C) for X in clusters[ i] )
Algebraic symbols are used when you do not know what you are talking about.
-- Schnoebelen, Philippe -
En effet, c'est ce que j'allais ajouter car si C est grand, ça doit prendre beaucoup moins de mémoire ainsi (generator expression).
-
Cela dit, si l'occupation mémoire n'est pas un problème, la solution avec list comprehension est un peu plus rapide que celle avec une generator expression sur mon ordinateur :
>>> import timeit >>> timeit.timeit( "sum( [ 0 for i in range(100000) ] )", number=1000) 5.139831292000963 >>> timeit.timeit( "sum( 0 for i in range(100000) )", number=1000) 6.275311594999948 >>>
(c'est reproductible). -
Il faudrait tester avec de vraies données. Peut-être que le « compilateur » optimise la présence des zéros.Algebraic symbols are used when you do not know what you are talking about.
-- Schnoebelen, Philippe -
J'aimerais vous répondre mais là j'ai un autre problème.
NameError: name 'self' is not defined
Je peux vous montrer ce que j'ai faitclass Kmeans(): """"" Input : C : Number of clusters X : Training set """"" def __init__(self, C, data, Bool): self.C = C self.data = data self.N = len(X) # Number of points self.display = Bool def d2(data, G): """"" Input : clusters_label : A numpy vector of size data set and each coordinate is the number of the clusters whoose the data point belongs. G : A set centroids Output : """"" return np.array([ [np.sum((x-g)**2) for g in G] for x in data]) def Inertia(clusters_label, G): """"" Input : clusters_label : A numpy vector of size data set and each coordinate is the number of the clusters whoose the data point belongs. G : A set centroids Output : """"" return def assignement(G): """"" Input : C : Number of clusters X : Training set Output : Cluster_labels """"" return np.argmin( d2(data, G), axis = 1) def centroids(clusters_labels, G): """"" Input : C : Number of clusters X : Training set """"" Gnew = np.zeros(G.shape) for j in range(C): if sum(clusters_label == j) == 0: Gnew[j] = G[j] else: Gnew[j] = np.mean(data[cluster_label == j, :], axis=0) def display(clusters_labels, step): """"" Input : C : Number of clusters X : Training set Out : Display step """"" def train(self,C,data, G): """"" Input : C : Number of clusters data : Training set G : Set of centroids set up as a list of points """"" IB = 0 # Inertia before IA = 0 # Intertia after step = 0 epsilon = 10**(-3) # inertia's variation minimum value. # Represent the clusters as a list with C lines each lines is a cluster clusters = [[G[ i]] for i in range(C)] # Initialization of the clusters set clusters_label = np.zeros(len(data)) while np.abs(IB-IA) > epsilon or step==0 : # While inertia doesn't stagnate #Display step if self.display : display(clusters_label, G, step) # Training step IB = IA # Old interia to compute variation IA = Inertia(clusters, G) # Update Inertia clusters_labels = assignement(G) # Update clusters G = centroids(clusters_labels, G) # Update centroids step = step +1 # Update step
Etclass KLoyds(KMeans): def __init__(self, C, data, Bool): super().__init__(self, C, data, Bool) # Initialisation step G = np.random.choice(self.data, self.C) self.train(self.C, self.data, G)
-
Je n'ai pas lu grand-chose, mais vu l'indentation à la fin, ces deux lignes :
G = np.random.choice(self.data, self.C) self.train(self.C, self.data, G)
ne font pas partie de la méthode KLoyds.__init__(), ce qui est probablement une erreur et la cause du problème (ou d'un des problèmes). Elles sont exécutées lors de la définition de la classe (exécution de l'instruction 'class'). Il n'y a pas de variable 'self' à ce moment-là. -
Oui il y a quelques erreurs c'est normal je suis en train d'écrire. Ma question est juste sur la problème que j'ai évoqué. Je ne comprends pas l'idée en fait. Pour moi je veux simplement faire hériter Floyds de Kmean et utiliser du coup la méthode mère train. Je pourrais le faire sans créer une sous classe mais j'ai bien envie de le faire comme ça pour apprendre.
-
Il n’empêche que self n’est pas défini. Peut-être que ces deux lignes devaient être décalées d’un alinéa vers la droite.Algebraic symbols are used when you do not know what you are talking about.
-- Schnoebelen, Philippe -
@mini_callli
Tu n'es pas clair car on ne sait même pas sur quelle ligne portait l'erreur dont tu as donné le message. Je crois qu'il faut que tu enlèves l'argument 'self' dans :super().__init__(self, C, data, Bool)
Cela dit, je préfèrerais faire :KMeans.__init__(self, C, data, Bool)
dans KLoyds.__init__() même si cela répète la classe de base, car il y a des subtilités avec cette façon d'utiliser super() (voir ici et là ; cela fait fort longtemps que j'ai lu ces liens et honnêtement, j'en ai oublié le contenu ; mais j'en ai retenu que super() utilisé ainsi peut réserver de mauvaises surprises). -
Merci pour vos réponses, j'ai fini d'écrire mon code. Il fonctionne du moins il tourne si je puis dire !
Comme je n'ai pas compris le problème de classes j'ai utilisé l'écritureclassifer = Kmeans(2, data, False) G = [data[0], data[1]] clus, Gn = classifer.train(G)
A présent je vais lire vos réponses. -
@nicolas.patrois : Décalé d'un alignât vers la droite hum.
ok je crois que j'avanceclass KLoyds(Kmeans): def __init__(self, C, data, Bool): super().__init__(self, C, data, Bool) self.G = np.random.choice(self.data, self.C) # Initialisation step def train(self): self.train(self.C, self.G)
A présent il est pas content car TypeError: __init__() takes 4 positional arguments but 5 were given j'ai l'impression que ce n'est pas de me faute parce que j'ai bien quatres arguments même si positional argument est un mot inconnu pour moi. -
Bilan : super() n'est pas super pour moi :)o.
-
Autre question comment on fait pour selectionner $n$ éléments aléatoirement dans un tableau à plusieurs dimensions ? Typiquement dans un tableau de coordonées 2D ?
Comme je savais pas comment faire j'ai mis
self.G = [self.data[0], self.data[1]] # Initialisation step
Mais bien évidement j'aimerais tirer deux points aléatoirement du tableau (500,2) appelé data -
@mini_calli
Les listes Python sont très flexibles et faciles à manipuler. On peut mettre n'importe quels objets dedans, y compris d'autres listes. Pour pouvoir gérer sainement le remplacement d'un élément par un autre, la permutation de deux éléments, le tri... il faut que ces opérations puissent être faites en modifiant quelque chose qui occupe très peu de mémoire : un pointeur vers l'objet remplit ce critère. Donc pour accéder à un élément, il faut 1) accéder au pointeur correspondant à l'indice spécifié (se fait en $O(1)$ d'après cette page SO et la FAQ de CPython), 2) lire ce pointeur et 3) le déréférencer, i.e. : lire ce qu'il y a à l'adresse du pointeur : un ou des octets représentant l'objet qui nous intéresse.
À l'inverse, les tableaux NumPy (à $n$ dimensions) contiennent un paquet d'objets tous du même type, qui prennent tous la même place. Ils peuvent donc a priori être stockés directement et de manière contiguë, ce qui permet d'y accéder plus vite en lecture comme en écriture (adresse de l'élément $L[k_1, \dotsc, k_n]$ du type $(\text{adresse début de } L) + k_1 S_1 + \dotsb + k_n S_n$ où $k_1, \dotsc, k_n$ représentent les indices et $S_1, \dotsc, S_n$ les tailles des « lignes » à chaque niveau, $S_n$ étant la taille d'un élément du tableau). Avec ce système, à l'adresse calculée, on a directement l'objet stocké dans telle ou telle case du tableau. Pas besoin de déréférencer un pointeur.
NumPy peut sans doute aussi effectuer des opérations simultanément sur divers éléments d'un tableau en utilisant les instructions vectorielles des processeurs actuels, à confirmer toutefois. Bref, NumPy permet d'être plus efficace lorsqu'on manipule des tableaux de nombres qui sont tous du même type (au sein d'un tableau donné). Par contre, cela nécessite un apprentissage. paul18 du forum a l'air de bien connaître et avait posté un exemple ici ainsi que des liens sur la vectorisation là (c.-à-d. la façon de traiter les données de type tableau qui permet d'obtenir du code efficace).
Pour ton accès à un élément aléatoire, je dirais que soit tu utilises random.randint() pour calculer chacun des deux indices, soit tu fais deux appels successifs à random.choice() : le premier renvoie une ligne choisie aléatoirement et le second un élément de cette ligne. -
Un truc qui peut bien marcher, c’est d’aplatir ton tableau (il y a une méthode pour les tableau de numpy).Algebraic symbols are used when you do not know what you are talking about.
-- Schnoebelen, Philippe -
J'ai un peu modifié mon message précédent : d'après cette page de SO (edit : et la FAQ de CPython), les listes Python sont implémentées comme des tableaux de pointeurs, ce qui est très différent des listes chaînées. L'accès à un élément d'indice donné se fait donc a priori en temps constant, mais l'insertion et la suppression doivent être en $O(n)$, où $n$ est le nombre d'éléments de la liste après la position d'insertion ou de suppression.
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.2K Toutes les catégories
- 9 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 65 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 314 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 773 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres