class Evoc::ClosedRules

Public Class Methods

closed_rules(tx_store:,query:) click to toggle source
# File lib/evoc/algorithms/closed_rules.rb, line 3
def self.closed_rules(tx_store:,query:)
  # @@store = tx_store
  # create initial trees, one tree per consequent
  tree = self.initialize_tree(tx_store,query)
  # puts "INIT TREE:"
  # tree.print_tree(1,nil,lambda {|node,pre| puts "#{pre} #{@@store.ints2names(node.name.map(&:to_i))}"})
  closed_rules = Evoc::RuleStore.new(query: query)
  tree.children.each do |consequent|
    self.extend_nodes(consequent).each do |frequency, closed_sets|
      closed_sets.each do |closed_set| 
        antecedent = closed_set - consequent.name
        closed_rules << Evoc::Rule.new(lhs: antecedent.map(&:to_i), rhs: consequent.name.map(&:to_i),tx_store: tx_store, m_support: frequency.to_r/tx_store.size)
      end
    end
  end
  return closed_rules
end

Private Class Methods

compare(a,b) click to toggle source
# File lib/evoc/algorithms/closed_rules.rb, line 125
def self.compare(a,b)
      if a == b
        return 'EQUAL'
      # 2. when A is a subset of B
      #    - replace all A with union of A and B
      elsif (a - b).empty?
        return 'A_IN_B'
      # 2. when B is a subset of A
      #    - remove B
      #    - add the union as new child
      elsif (b - a).empty?
        return 'B_IN_A'
      # 4. contain different elements
      #    - add the union as new child
      else
        return 'NOT_EQUAL'
      end  
end
extend_nodes(root,closed_rules: {}) click to toggle source
# File lib/evoc/algorithms/closed_rules.rb, line 52
def self.extend_nodes(root,closed_rules: {})
  current_node = root.first_child
  while(!current_node.nil?) do
    a = current_node
    b = a.next_sibling
    while(!b.nil?) do
      # print "Checking #{@@store.ints2names(a.name.map(&:to_i))}:{#{a.content}} against #{@@store.ints2names(b.name.map(&:to_i))}:{#{b.content}}"
      ab = a.name | b.name
      a_txes = a.content
      b_txes = b.content
      ab_txes = a_txes & b_txes
      # check properties
      # 1. when txes are the same
      #    - remove B
      #    - replace all A with union of A and B
      if ab_txes.size > 0
        case self.compare(a_txes,b_txes)
        when 'EQUAL'
          # puts "  EQUAL"
          # puts "    removing #{@@store.ints2names(b.name.map(&:to_i))}"
          # puts "    renaming #{@@store.ints2names(a.name.map(&:to_i))} to #{@@store.ints2names(ab.map(&:to_i))}"
          temp = b.previous_sibling
          root.remove!(b)
          b = temp
          a.each {|n| n.rename(ab | n.name)}
        when 'A_IN_B'
          # puts "  A in B"
          # puts "    renaming #{@@store.ints2names(a.name.map(&:to_i))} to #{@@store.ints2names(ab.map(&:to_i))}"
          a.each {|n| n.rename(ab | n.name)}
        when 'B_IN_A'
          # puts "  B in A"
          # puts "    removing #{@@store.ints2names(b.name.map(&:to_i))}"
          # puts "    adding child #{@@store.ints2names(ab.map(&:to_i))} to #{@@store.ints2names(a.name.map(&:to_i))}"
          temp = b.previous_sibling
          root.remove!(b)
          b = temp
          a << Tree::TreeNode.new(ab,ab_txes)
        when 'NOT_EQUAL'
          # puts "  NOT EQUAL"
          # puts "    adding child #{@@store.ints2names(ab.map(&:to_i))} to #{@@store.ints2names(a.name.map(&:to_i))}"
          a << Tree::TreeNode.new(ab,ab_txes)
        end
      end
      # puts "NEW TREE:"
      # root.print_tree(1,nil,lambda {|node,pre| puts "#{pre} #{@@store.ints2names(node.name.map(&:to_i))}:#{node.content.size}"})
      b = b.next_sibling
      # puts "A siblings #{a.right_siblings.map(&:name).map {|n| @@store.ints2names(n.map(&:to_i))}}"
      # puts "A next sibling #{@@store.ints2names(a.next_sibling.name.map(&:to_i))}}"
      # puts "A:#{@@store.ints2names(a.name.map(&:to_i))}, B:#{b.nil? ? nil : @@store.ints2names(b.name.map(&:to_i))}"
    end # siblings.each
    if !a.children.empty?
      # puts "TRAVERSING DOWN"
      self.extend_nodes(a, closed_rules: closed_rules)
    end
    # add node as closed rule if not subsumed by another rule already added
    rule_frequency = a.content.size
    rule = a.name
    if closed_rules[rule_frequency].nil?
      # puts "ADDING NEW CLOSED RULE: #{@@store.ints2names(rule.map(&:to_i))}:#{rule_frequency}"
      closed_rules[rule_frequency] = [rule] 
    else
      if !closed_rules[rule_frequency].any? {|closed| (rule - closed).empty? }
        # puts "ADDING NEW CLOSED RULE: #{@@store.ints2names(rule.map(&:to_i))}:#{rule_frequency}"
        closed_rules[rule_frequency] << rule
      else
        # puts "RULE SUBSUMED, NOT ADDING: #{@@store.ints2names(rule.map(&:to_i))}:#{rule_frequency}"
      end
    end
    current_node = current_node.next_sibling
  end # children.each
  return(closed_rules)
end
initialize_tree(tx_store, query) click to toggle source
# File lib/evoc/algorithms/closed_rules.rb, line 22
def self.initialize_tree(tx_store, query)
  tree = Tree::TreeNode.new([])
  # find all items that changed with something in the query
  query_changed_in = tx_store.transactions_of_list(query)
  # store all items from the query that have changed with each consequent
  query_changed_in.each do |tx_id|
    tx = tx_store.get_tx(id:tx_id,id_type: :index)
    antecedent = (query & tx.items)
    consequents = (tx.items - antecedent)
    if consequents.size != 0
      consequents.each do |consequent|
        consequent_key = [consequent.to_s]
        if tree[consequent_key].nil?
          # initialize candidates
          tree << Tree::TreeNode.new([consequent.to_s],tx_store.transactions_of(consequent))
        end
        txes_consequent = tree[consequent_key].content
        antecedent.each do |item|
          union = [item.to_s,consequent.to_s]
          if tree[consequent_key][union].nil?
            txes_union = tx_store.transactions_of(item) & txes_consequent
            tree[consequent_key] << Tree::TreeNode.new(union,txes_union)
          end
        end
      end
    end
  end
  return(tree)
end