Class: GeneValidator::HierarchicalClusterization

Inherits:
Object
  • Object
show all
Defined in:
lib/genevalidator/clusterization.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(values) ⇒ HierarchicalClusterization

Object initialization Params: values :vector of values



311
312
313
314
 
# File 'lib/genevalidator/clusterization.rb', line 311

def initialize(values)
  @values = values
  @clusters = []
end

Instance Attribute Details

#clusters ⇒ Object

Returns the value of attribute clusters.



305
306
307
 
# File 'lib/genevalidator/clusterization.rb', line 305

def clusters
  @clusters
end

#values ⇒ Object

Returns the value of attribute values.



304
305
306
 
# File 'lib/genevalidator/clusterization.rb', line 304

def values
  @values
end

Instance Method Details

#hierarchical_clusterization(no_clusters = 0, distance_method = 0, vec = @values, debug = false) ⇒ Object

Makes an hierarchical clusterization until the most dense cluster is obtained or the distance between clusters is sufficintly big or the desired number of clusters is obtained Params: no_clusters: stop test (number of clusters) distance_method: distance method (method 0 or method 1) vec: a vector of values (by default the values from initialization) debug: display debug information Output: vector of Cluster objects



415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
 
# File 'lib/genevalidator/clusterization.rb', line 415

def hierarchical_clusterization(no_clusters = 0, distance_method = 0, vec = @values, debug = false)
  clusters = []
  vec = vec.sort

  if vec.length == 1
    hash = { vec[0] => 1 }
    cluster = Cluster.new(hash)
    clusters.push(cluster)
    clusters
  end

  # Thresholds
  threshold_distance = (0.25 * (vec.max - vec.min))
  threshold_density = (0.5 * vec.length).to_i

  # make a histogram from the input vector
  histogram = Hash[vec.group_by { |x| x }.map { |k, vs| [k, vs.length] }]

  # clusters = array of clusters
  # initially each length belongs to a different cluster
  histogram.sort { |a, b| a[0] <=> b[0] }.each do |elem|
    $stderr.puts "len #{elem[0]} appears #{elem[1]} times" if debug
    hash = { elem[0] => elem[1] }
    cluster = Cluster.new(hash)
    clusters.push(cluster)
  end

  clusters.each(&:print) if debug

  return clusters if clusters.length == 1

  # each iteration merge the closest two adiacent cluster
  # the loop stops according to the stop conditions
  iteration = 0
  loop do

    # stop condition 1
    break if no_clusters != 0 && clusters.length == no_clusters

    iteration = iteration + 1
    $stderr.puts "\nIteration #{iteration}" if debug

    min_distance = 100_000_000
    cluster      = 0
    density      = 0

    clusters[0..clusters.length - 2].each_with_index do |_item, i|
      dist = clusters[i].distance(clusters[i + 1], distance_method)
      $stderr.puts "distance between clusters #{i} and #{i + 1} is #{dist}" if debug
      current_density = clusters[i].density + clusters[i + 1].density
      if dist < min_distance
        min_distance = dist
        cluster = i
        density = current_density
      elsif dist == min_distance && density < current_density
        cluster = i
        density = current_density
      end
    end

    # stop condition 2
    # the distance between the closest clusters exceeds the threshold
    if no_clusters == 0 && (clusters[cluster].mean - clusters[cluster + 1].mean).abs > threshold_distance
      break
    end

    # merge clusters 'cluster' and 'cluster'+1
    $stderr.puts "clusters to merge #{cluster} and #{cluster + 1}" if debug

    clusters[cluster].add(clusters[cluster + 1])
    clusters.delete_at(cluster + 1)

    if debug
      clusters.each_with_index do |elem, i|
        $stderr.puts "cluster #{i}"
        elem.print
      end
    end

    # stop condition 3
    # the density of the biggest clusters exceeds the threshold
    if no_clusters == 0 && clusters[cluster].density > threshold_density
      break
    end
  end

  @clusters = clusters
end

#hierarchical_clusterization_2d(no_clusters = 0, distance_method = 0, vec = @values, debug = false) ⇒ Object 



316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
 
# File 'lib/genevalidator/clusterization.rb', line 316

def hierarchical_clusterization_2d(no_clusters = 0, distance_method = 0, vec = @values, debug = false)
  clusters = []

  if vec.length == 1
    hash = { vec[0] => 1 }
    cluster = PairCluster.new(hash)
    clusters.push(cluster)
    clusters
  end

  # Thresholds
  # threshold_distance = (0.25 * (vec.max-vec.min))
  threshold_density = (0.5 * vec.length).to_i

  # make a histogram from the input vector
  histogram = Hash[vec.group_by { |a| a }.map { |k, vs| [k, vs.length] }]

  # clusters = array of clusters
  # initially each length belongs to a different cluster
  histogram.each do |elem|
    if debug
      $stderr.puts "pair (#{elem[0].x} #{elem[0].y}) appears #{elem[1]} times"
    end
    hash = { elem[0] => elem[1] }
    cluster = PairCluster.new(hash)
    clusters.push(cluster)
  end

  clusters.each(&:print) if debug

  return clusters if clusters.length == 1

  # each iteration merge the closest two adiacent cluster
  # the loop stops according to the stop conditions
  iteration = 0
  loop do
    # stop condition 1
    break if no_clusters != 0 && clusters.length == no_clusters

    iteration = iteration + 1
    $stderr.puts "\nIteration #{iteration}" if debug

    min_distance = 100_000_000
    cluster1     = 0
    cluster2     = 0
    density      = 0

    [*(0..(clusters.length - 2))].each do |i|
      [*((i + 1)..(clusters.length - 1))].each do |j|
        dist = clusters[i].distance(clusters[j], distance_method)
        $stderr.puts "distance between clusters #{i} and #{j} is #{dist}" if debug
        current_density = clusters[i].density + clusters[j].density
        if dist < min_distance
          min_distance = dist
          cluster1 = i
          cluster2 = j
          density = current_density
        elsif dist == min_distance && density < current_density
          cluster1 = i
          cluster2 = j
          density = current_density
        end
      end
    end

    # merge clusters 'cluster1' and 'cluster2'
    $stderr.puts "clusters to merge #{cluster1} and #{cluster2}" if debug

    clusters[cluster1].add(clusters[cluster2])
    clusters.delete_at(cluster2)

    if debug
      clusters.each_with_index do |elem, i|
        $stderr.puts "cluster #{i}"
        elem.print
      end
    end

    # stop condition 3
    # the density of the biggest clusters exceeds the threshold
    if no_clusters == 0 && clusters[cluster].density > threshold_density
      break
    end
  end

  @clusters = clusters
end

#most_dense_cluster(clusters = @clusters) ⇒ Object

Returns the cluster with the maimum density Params: clusters: list of Clususter objects



508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
 
# File 'lib/genevalidator/clusterization.rb', line 508

def most_dense_cluster(clusters = @clusters)
  max_density = 0
  max_density_cluster = 0

  if clusters.nil?
    nil
  end

  clusters.each_with_index do |item, i|
    if item.density > max_density
      max_density = item.density
      max_density_cluster = i
    end
  end
  clusters[max_density_cluster]
end