Class: Classificateur

Inherits:
Object
  • Object
show all
Defined in:
classificateur.rb

Overview

Classe modelisant un classificateur de donnees utilisant la methode des k-moyennes (k-means clustering).

Constant Summary

DEBUG =

Pour activer la trace de debogage, on definit la variable d'environnement avec une valeur differente de false. Si la valeur est 'TRUE' alors la trace de deboggage est plus detaillee.

ENV['DEBUG'] && ENV['DEBUG'] !~ /^false$/i
DEBUG_DETAILLE = 
ENV['DEBUG'] && ENV['DEBUG'] =~ /^TRUE$/
ERREUR_MAX =

Erreur permise dans le calcul du point fixe -- pour eviter de ne jamais atteindre un point fixe a cause d'erreurs d'arrondissement.

0.001
MODES =

Les differents modes d'execution pour la classification et les methodes auxiliaires.

Les differentes modes representent des strategies differentes d'execution, sequentielle ou paralleles, des principales methodes utilisees par la methode run.

[:seq,
 :par_fj_fin,
 :par_fj_adj,
 :par_fj_cyc,
 :par_sta,
 :par_dyn,
]
MODES_AVEC_TAILLE_TACHE = 
[:par_fj_cyc, :par_sta, :par_dyn]
TAILLE_TACHE_DEFAUT =

Taille par defaut des taches pour les approches a granularite grossiere avec taches.

5

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(*points) ⇒ Classificateur

Initialise un nouveau classificateur.

Parameters:

  • points (Array<Point>) —

    liste des points a classifier

Ensures:

  • self.points == points

  • nb_threads == PRuby.nb_threads

Requires:

  • points.size >= 1



133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
 
# File 'classificateur.rb', line 133

def initialize( *points )
  DBC.require( points.size >= 1,
               "Il doit y avoir au moins un point a classifier" )

  @points = points
  @nb_points = points.size

  @representants = nil
  @nb_groupes = nil
  @valeur = nil
  @moyenne_distances = nil

  @mode = :seq
  @nb_threads = PRuby.nb_threads
end

Instance Attribute Details

#mode ⇒ MODES

Mode d'execution a utiliser lors d'une classification.

Valeur par defaut = :seq

Returns:



51
52
53
 
# File 'classificateur.rb', line 51

def mode
  @mode
end

#nb_points ⇒ Fixnum (readonly)

Nombre de points a traiter par le classificateur.

Returns:

  • (Fixnum) 


159
160
161
 
# File 'classificateur.rb', line 159

def nb_points
  @nb_points
end

#nb_threads ⇒ nil, Fixnum

Nombre de threads a utiliser lors d'une classification parallele.

Valeur par defaut = nil

Returns:

  • (nil, Fixnum) 


73
74
75
 
# File 'classificateur.rb', line 73

def nb_threads
  @nb_threads
end

#points ⇒ Array<Point> (readonly)

Liste des points a traiter par le classificateur.

Returns:

  • (Array<Point>) 


153
154
155
 
# File 'classificateur.rb', line 153

def points
  @points
end

#representants ⇒ Array<Point> (readonly)

Note:

A l’interne, un representant n’est pas un vrai point,

Liste des representants des divers groupes, tels que generes par la classification (methode run).

puisque seule sa position importe dans les calculs. Toutefois, a l'externe, des "vrais" points sont generes par la presente methode.

Returns:

  • (Array<Point>)

Ensures:

  • return.size == nb_groupes specifie lors du dernier appel a run

Requires:

  • run a ete appelee au moins une fois



176
177
178
179
180
181
 
# File 'classificateur.rb', line 176

def representants
  klass = points.first.class
  (0...@representants.size).map do |k|
    klass.new "REP#{k}", @representants[k], k
  end
end

#taille_tache ⇒ nil, Fixnum

Taille des taches a utiliser lors d'une classification parallele.

Valeur par defaut = nil

Returns:

  • (nil, Fixnum) 


101
102
103
 
# File 'classificateur.rb', line 101

def taille_tache
  @taille_tache
end

Class Method Details

.memes_representants?(reps1, reps2, delta = ERREUR_MAX) ⇒ Boolean

Determine si deux listes (Array) de representants sont identiques, a une valeur ERREUR_MAX pres.

Utilise pour determiner si le processus d'iteration doit se terminer Utilise aussi pour les assertions dans les tests et pour la verification dans le programme de benchmark.

Parameters:

  • reps1 (Array<#in_delta?>)
  • reps2 (Array<#in_delta?>)
  • delta (Float) (defaults to: ERREUR_MAX)

Returns:

  • (Boolean) —

    true <=> les memes representants sont presents dans les deux (delta pres)



309
310
311
312
313
314
315
316
317
318
 
# File 'classificateur.rb', line 309

def self.memes_representants?( reps1, reps2, delta = ERREUR_MAX )
  return false if reps1.nil? || reps2.nil?
  return false unless reps1.size == reps2.size

  reps1.each do |r1|
    return false unless reps2.any? { |r2| r1.in_delta?(r2) }
  end

  true
end

Instance Method Details

#groupes ⇒ Array<Array<Point>>

Liste des groupes generes par la classification.

Returns:

  • (Array<Array<Point>>)

Ensures:

  • return.size == representants.size

Requires:

  • run a ete appelee au moins une fois



190
191
192
193
 
# File 'classificateur.rb', line 190

def groupes
  (0...representants.size)
    .map { |c| points.select { |p| p.groupe == c } }
end

#moyenne_distances ⇒ Fixnum

Moyennes de la distance de chacun des points par rapport au representant de son groupe.

Utilisee pour identifier le "point d'inflexion" lorsqu'on cherche a determiner la valeur qui semble la plus appropriee pour k.

Returns:

  • (Fixnum)

Requires:

  • la methode run a ete appelee au moins une fois



220
221
222
223
224
225
226
227
228
229
230
 
# File 'classificateur.rb', line 220

def moyenne_distances
  DBC.require( @nb_groupes,
               "La methode run n'a pas ete appelee, donc moyenne_distances n'est pas encore definie" )

  unless @moyenne_distances
    somme = points.reduce(0.0) { |val, p| val + p.distance(@representants[p.groupe]) }
    @moyenne_distances = somme / nb_points
  end

  @moyenne_distances
end

#run(nb_groupes = nil, nb_iterations_max = nil) ⇒ Fixnum

Classifie la collection de points dans le nombre de groupes indique, en utilisant un mode particulier d'execution (i.e., la mise en oeuvre sequentielle ou une des mises en oeuvre paralleles).

Parameters:

  • nb_groupes (nil, Fixnum) (defaults to: nil) —

    nombre de groupes a generer

  • nb_iterations_max (nil, Fixnum) (defaults to: nil) —

    nombre maximum d’iterations a executer

Returns:

  • (Fixnum) —

    nombre d’iterations effectivement executees. Donc, peut etre inferieur au max specifie si le point fixe est atteint avant

Ensures:

  • result <= nb_iterations_max unless nb_iterations_max.nil?

  • representants.size == nb_groupes

  • groupes.size == nb_groupes

  • groupes.reduce(:+) == points

Requires:

  • nb_groupes >= 1 unless nb_groupes.nil?

  • nb_groupes <= nombre de points distinct (points.uniq.size) unless nb_groupes.nil?



267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
 
# File 'classificateur.rb', line 267

def run( nb_groupes = nil, nb_iterations_max = nil )
  verifier_parametres_execution

  (puts; imprimer_points(0, :points)) if DEBUG_DETAILLE

  @representants = definir_representants( nb_groupes ) if representants_doivent_etre_generes?( nb_groupes )

  (imprimer_points(0, :representants); puts "\#0: valeur = nil\n\n") if DEBUG_DETAILLE

  # On itere jusqu'au point fixe ou jusqu'a ce qu'on atteigne le
  # nombre d'iterations maximum indique.
  anciens = nil
  nb_iterations = 0
  until Classificateur.memes_representants?( anciens, @representants ) ||
      iterations_completees?( nb_iterations, nb_iterations_max )
    classifier_les_points( points, @representants )
    anciens = @representants
    @representants = nouveaux_representants( @nb_groupes, points )
    @valeur = nil
    @moyenne_distances = nil
    nb_iterations += 1

    imprimer_points(nb_iterations, :representants) if DEBUG_DETAILLE
    imprimer_points(nb_iterations, :points) if DEBUG_DETAILLE
    puts "\##{nb_iterations}: valeur = #{"%.2f" % valeur}\n\n" if DEBUG_DETAILLE
  end

  nb_iterations
end

#to_s ⇒ String

Note:

Utile pour le debogage.

Chaine representant le classificateur.

Returns:

  • (String) 


238
239
240
 
# File 'classificateur.rb', line 238

def to_s
  "#<Classificateur: #{representants.join(' ')}>"
end

#valeur ⇒ Fixnum

Valeur (cout) associee a la classification effectuee = somme des distances au carre.

Returns:

  • (Fixnum)

Requires:

  • la methode run a ete appelee au moins une fois



201
202
203
204
205
206
207
208
 
# File 'classificateur.rb', line 201

def valeur
  DBC.require( @nb_groupes,
               "La methode run n'a pas ete appelee, donc valeur n'est pas encore definie" )

  @valeur ||= points.reduce(0.0) { |val, p| val + p.distance(@representants[p.groupe])**2 }

  @valeur
end