Adaptive Time Clustering Algorithm

gap_algorithms_test.rb

require 'time'

class GapMean

  THE_ANSWER_TO_LIFE_AND_EVERYTHING = 42
  K = Math.log(THE_ANSWER_TO_LIFE_AND_EVERYTHING)

  attr_reader :gaps, :running_total, :exp, :window
  def initialize(seq)
    @seq = seq
    calc_gaps
    @window = 15
  end

  def adjust_window(sum, window, gapnum)
    tmean = K + (sum * (1.0 / (2 * window + 1)))
    tgap  = Math.log(@gaps[gapnum])
    puts "TMEAN (#{tmean}), TGAP (#{tgap})"
    (tgap >= tmean) ? window - 1 : window
  end

  def adaptive_calc
    win = @window
    mem = 0
    @gaps.each_with_index do |n, idx|
      mem += Math.log(n)
      if idx > 0
        win = adjust_window(mem, win, idx - 1)
      end
    end
    @amean = K + (mem * (1.0 / (2 * win + 1)))
  end

  def calc_mean
    sum = @gaps.inject(0) do |mem, n|
      mem + Math.log(n)
    end
    @gmean = K + (sum * (1.0 / (2 * window + 1)))
  end

  def events(type = :geometric)
    mean = (type == :geometric) ? @gmean : @amean
    @gaps.each_with_index do |g, idx|
      if Math.log(g) >= mean
        puts "New Event detected at gap index #{idx}"
      end
    end
  end

  def gap_logs
    @gaps.each do |g|
      puts "#{g}: #{Math.log(g)}"
    end
  end

  private

  def root(num, exp)
    Math.exp(Math.log(num) / exp)
  end

  def to_time(str)
    Time.parse "#{str} UTC"
  end

  def calc_gaps
    @gaps = []
    seq = @seq.clone
    ctime = to_time(seq.shift)
    seq.each do |t|
      ntime = to_time(t)
      @gaps << (ntime - ctime) / 60
      ctime = ntime
    end
  end

end

start_times = %w{8:30 8:44 9:30 11:30 13:43 13:50 14:55 15:15 16:00}

gm = GapMean.new(start_times)
gmean = gm.calc_mean
amean = gm.adaptive_calc
puts "Geometric MEAN: #{gmean}"
puts " Adaptive MEAN: #{amean}"

puts "Running geometric events"
gm.events
puts "Running adaptive events"
gm.events(:adaptive)

time_gap_geometric_mean.rb

require 'benchmark'

THE_ANSWER_TO_LIFE_AND_EVERYTHING = 42
K = Math.log(THE_ANSWER_TO_LIFE_AND_EVERYTHING)
window = 15

def root_of(num, exponent)
  Math.exp(Math.log(num)/exponent.to_f)
end

def sum(nums)
  nums.inject(0) do |mem, n|
    mem + Math.log(n)
  end
end

def by_sum(nums)
  win = 15
  K + (sum(nums) * (1.0 / (2 * win + 1)))
end

def by_mult(nums)
  win = 15
  gm = root_of(nums.inject(:*), nums.length)
  K + (Math.log(gm) * nums.length) * (1.0 / (2 * win + 1))
end

nums = []
1.upto(240) do
  nums << rand(1..30)
end

Benchmark.bm(7) do |x|
  x.report { puts by_sum(nums) }
  x.report { puts by_mult(nums)}
end