class Evoc::TopK
Public Class Methods
expand(rule,expansions,tx_store)
click to toggle source
# File lib/evoc/algorithms/top_k.rb, line 51 def self.expand(rule,expansions,tx_store) expansions.each do |e| # only expand rules with items lexically larger than the lhs if rule.lhs.all? {|i| e > i} expanded_rule = Evoc::Rule.new(lhs: rule.lhs+[e],rhs: rule.rhs,tx_store: tx_store) if expanded_rule.m_support.value > @@min_support self.save_rule(expanded_rule) end end end end
save_rule(r)
click to toggle source
# File lib/evoc/algorithms/top_k.rb, line 63 def self.save_rule(r) key = "#{r.m_support.value.to_f}|#{r.name}" #puts "adding rule #{key}" @@top_k_rules.push(key,r) @@expansion_candidates.push(key,r) if @@top_k_rules.size >= @@k ##puts "K is #{@@k} rules in #{@@top_k_rules.size}" #puts "new rule sup #{r.m_support.value.to_f} min sup is #{@@min_support}" if r.m_support.value > @@min_support #puts "new rule larger than min sup" # remove min sup rules until size is K while (@@top_k_rules.size > @@k) && (@@top_k_rules.min_key.to_f == @@min_support) min_rule = @@top_k_rules.delete_min #puts "ksize #{@@top_k_rules.size} after removing rule #{min_rule}" end @@min_support = @@top_k_rules.min_key.to_f #puts "set min sup to #{@@min_support}" else #puts "#{"%f" % r.m_support.value.to_f.to_s} not larger than #{@@min_support}" end end end
topk(k:,min:,max:,tx_store:,query:)
click to toggle source
# File lib/evoc/algorithms/top_k.rb, line 4 def self.topk(k:,min:,max:,tx_store:,query:) @@k = k @@top_k_rules = Containers::CRBTreeMap.new @@expansion_candidates = Containers::CRBTreeMap.new @@min_support = 0 # start with all subsets of size @min in @query query.combination(min).each do |antecedent| # check if this antecedent has min_support > 0 changed_in = tx_store.transactions_of_list(antecedent, strict: true) if changed_in.size > 0 consequents = Set.new # find all consequents for this antecedent changed_in.each do |tx_id| tx = tx_store.get_tx(id:tx_id,id_type: :index) # the tx size must be larger than the antecedent size # (so that we have items left for the consequent) if (tx.size > antecedent.size) (tx.items - query).each {|c| consequents << c} end end consequents.each do |consequent| r = Evoc::Rule.new(lhs:antecedent,rhs: [consequent], tx_store: tx_store) if r.m_support.value.to_f >= @@min_support self.save_rule(r) end end end end # now expand antecedents while !@@expansion_candidates.empty? && (@@expansion_candidates.min_key.to_f >= @@min_support) max_candidate = @@expansion_candidates.delete_max #puts "expanding #{max_candidate.name} | #{max_candidate.m_support.value}" expansions = query - max_candidate.lhs # don't make antecedents larger than @max #if (most_frequent_rule.lhs.size < max) & !expansions.empty? if (max_candidate.lhs.size < max) self.expand(max_candidate,expansions,tx_store) end # remove all rules with sup < min_sup from candidates while !@@expansion_candidates.empty? && (@@expansion_candidates.min_key.to_f < @@min_support) @@expansion_candidates.delete_min end end return Evoc::RuleStore.new(@@top_k_rules.map {|k,rule| rule}) end