class FpGrowth::Miner::ConditionalTreeBuilder

Public Class Methods

new(pattern_base=[], threshold=1) click to toggle source
# File lib/fpgrowth/miner/conditional_tree_builder.rb, line 8
def initialize(pattern_base=[], threshold=1)
  @pattern_base = pattern_base
  @threshold = threshold
end

Public Instance Methods

continue_pattern(cursor_tree, pattern_base) click to toggle source
# File lib/fpgrowth/miner/conditional_tree_builder.rb, line 115
def continue_pattern(cursor_tree, pattern_base)
  cursor_tree.support+=pattern_base.support
  traverse(cursor_tree, Pattern.new(pattern_base.content[1..-1], pattern_base.support))
end
execute(pattern_base=@pattern_base, threshold=@threshold) click to toggle source
# File lib/fpgrowth/miner/conditional_tree_builder.rb, line 13
def execute(pattern_base=@pattern_base, threshold=@threshold)
  @pattern_base = pattern_base
  @threshold = threshold
  first_pass
  second_pass
end
first_pass(pattern_base=@pattern_base, threshold=@threshold) click to toggle source
# File lib/fpgrowth/miner/conditional_tree_builder.rb, line 30
def first_pass(pattern_base=@pattern_base, threshold=@threshold)
  @pattern_base = pattern_base
  @threshold = threshold
  scan
  pruning
  sort
end
fork_pattern(cursor_tree, pattern_base) click to toggle source
# File lib/fpgrowth/miner/conditional_tree_builder.rb, line 107
def fork_pattern(cursor_tree, pattern_base)
  node = FpTree::Node.new(pattern_base.content.first, pattern_base.support)
  @fp_tree.append_node(cursor_tree, node)
  cursor_tree = node
  traverse(cursor_tree, Pattern.new(pattern_base.content[1..-1], pattern_base.support))
end
pruning(pattern_base=@pattern_base, supports=@supports, threshold=@threshold) click to toggle source

discard unfrequent items @param supports Hash

# File lib/fpgrowth/miner/conditional_tree_builder.rb, line 52
def pruning(pattern_base=@pattern_base, supports=@supports, threshold=@threshold)

  total = 0
  pattern_base.each { |x| total += x.support}
  minimum = total.to_f / 100 * threshold

  for pattern in pattern_base
    for item in pattern.content
      pattern.content.delete(item) if supports[item] < minimum
    end
    pattern_base.delete_if { |value| value.content.empty? }
  end
  supports.delete_if { |key, value| value < minimum }

  return supports
end
scan(pattern_base=@pattern_base) click to toggle source
# File lib/fpgrowth/miner/conditional_tree_builder.rb, line 38
def scan(pattern_base=@pattern_base)
  @supports= Hash.new(0)
  for pattern in pattern_base
    for item in pattern.content
      @supports[item] += pattern.support
    end

  end
  return @supports
end
second_pass(pattern_base=@pattern_base) click to toggle source
# File lib/fpgrowth/miner/conditional_tree_builder.rb, line 20
def second_pass(pattern_base=@pattern_base)
  @fp_tree = FpTree::FpTree.new(@supports)
  for pattern in pattern_base
    pattern = sort_by_support(pattern)
    #Look for leaf
    traverse(@fp_tree.root, pattern)
  end
  return @fp_tree
end
sort(supports=@supports) click to toggle source

Ordonner les items en fonction de le support Cet ordre est utilisé pour la construction du Tree lors de la seconde passe

# File lib/fpgrowth/miner/conditional_tree_builder.rb, line 72
def sort(supports=@supports)
  Hash[(supports.sort_by { |_key, value| value }.reverse)]
end
sort_by_support(pattern_base, fp_tree=@fp_tree) click to toggle source
# File lib/fpgrowth/miner/conditional_tree_builder.rb, line 77
def sort_by_support(pattern_base, fp_tree=@fp_tree)
  lookup = fp_tree.item_order_lookup
  pattern_base.content.sort_by! do |item|
    fp_tree.supports.fetch(item, fp_tree.supports.size + 1)
  end
  pattern_base.content.reverse!
  return pattern_base
end
test_execute_pattern_base(value = []) click to toggle source
# File lib/fpgrowth/miner/conditional_tree_builder.rb, line 128
def test_execute_pattern_base(value = [])
  if  value == @pattern_base
  then  return true
  end
  return false
end
test_execute_threshold(value = 1) click to toggle source

fonction qui sert uniquement pour les tests

# File lib/fpgrowth/miner/conditional_tree_builder.rb, line 121
def test_execute_threshold(value = 1)
  if   value == @threshold
  then  return true
  end
  return false
end
traverse(cursor_tree, pattern_base) click to toggle source
# File lib/fpgrowth/miner/conditional_tree_builder.rb, line 87
def traverse(cursor_tree, pattern_base)
  if pattern_base and pattern_base.size > 0
    found = false
    if cursor_tree.item == pattern_base.content.first
      continue_pattern(cursor_tree, pattern_base)
      found = true
    end
    i = 0
    while found == false and i < cursor_tree.children.size
      if cursor_tree.children[i].item == pattern_base.content[0] then
        continue_pattern(cursor_tree.children[i], pattern_base)
        found = true
      end
      i+=1
    end
    fork_pattern(cursor_tree, pattern_base) unless found
  end
end