Class: FeldtRuby::FastMap

Inherits:
Object show all
Defined in:
lib/feldtruby/statistics/fastmap.rb

Defined Under Namespace

Classes: DistanceFunction, PivotNode

Instance Method Summary collapse

Constructor Details

#initialize(distance, k = 2, choiceDepth = 1) ⇒ FastMap

Returns a new instance of FastMap.



43
44
45
 
# File 'lib/feldtruby/statistics/fastmap.rb', line 43

def initialize(distance, k = 2, choiceDepth = 1)
  @distance, @k, @choice_depth = distance, k, choiceDepth
end

Instance Method Details

#choose_distant_objects(objects, distance) ⇒ Object 



67
68
69
70
71
72
73
74
75
76
 
# File 'lib/feldtruby/statistics/fastmap.rb', line 67

def choose_distant_objects(objects, distance)
  o1 = nil
  o2 = objects.sample
  # Not sure if there is any benefit to doing this more than once. Test later.
  @choice_depth.times do
    o1 = find_most_distant_object(objects, o2, distance)
    o2 = find_most_distant_object(objects, o1, distance)
  end
  return o1, o2
end

#create_map(k, distance) ⇒ Object 



52
53
54
55
56
57
58
59
60
61
62
63
64
65
 
# File 'lib/feldtruby/statistics/fastmap.rb', line 52

def create_map(k, distance)
  return nil if k == 0
  o1, o2 = choose_distant_objects(@objects, @distance)
  node = PivotNode.new(distance, o1, o2)
  coordinate_map = {}
  if distance.calc(o1, o2) == 0.0
    @objects.each {|o| coordinate_map[o] = 0.0}
  else
    @objects.each {|o| coordinate_map[o] = node.fastmap_coordinate(o)}
  end
  node.map = coordinate_map
  node.child = create_map k-1, next_distance(distance, o1, o2, coordinate_map)
  node
end

#find_most_distant_object(objects, o, distance) ⇒ Object

Find the object in objects that is farthest from o, given a distance function.



79
80
81
 
# File 'lib/feldtruby/statistics/fastmap.rb', line 79

def find_most_distant_object(objects, o, distance)
  objects.sort_by {|oi| distance.calc(oi, o)}.last
end

#next_distance(distance, o1, o2, coordinates) ⇒ Object

Create the next distance function from a given distance func.



93
94
95
96
97
 
# File 'lib/feldtruby/statistics/fastmap.rb', line 93

def next_distance(distance, o1, o2, coordinates)
  DistanceFunction.new do |oi, oj| 
    Math.sqrt( distance.calc(oi, oj)**2 - (coordinates[oi] - coordinates[oj])**2 )
  end
end

#run(objects) ⇒ Object 



47
48
49
50
 
# File 'lib/feldtruby/statistics/fastmap.rb', line 47

def run(objects)
  @objects = objects
  create_map(@k, @distance)
end