Class: FpGrowth::Miner::ConditionalTreeBuilder

Inherits:
Object
  • Object
show all
Defined in:
lib/fpgrowth/miner/conditional_tree_builder.rb

Instance Method Summary collapse

Constructor Details

#initialize(pattern_base = [], threshold = 1) ⇒ ConditionalTreeBuilder

Returns a new instance of ConditionalTreeBuilder.



8
9
10
11
 
# File 'lib/fpgrowth/miner/conditional_tree_builder.rb', line 8

def initialize(pattern_base=[], threshold=1)
  @pattern_base = pattern_base
  @threshold = threshold
end

Instance Method Details

#continue_pattern(cursor_tree, pattern_base) ⇒ Object 



115
116
117
118
 
# 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) ⇒ Object 



13
14
15
16
17
18
 
# 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) ⇒ Object 



30
31
32
33
34
35
36
 
# 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) ⇒ Object 



107
108
109
110
111
112
 
# 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) ⇒ Object

discard unfrequent items

Parameters:

  • supports (defaults to: @supports) —

    Hash



52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
 
# 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) ⇒ Object 



38
39
40
41
42
43
44
45
46
47
 
# 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) ⇒ Object 



20
21
22
23
24
25
26
27
28
 
# 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) ⇒ Object

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



72
73
74
 
# 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) ⇒ Object 



77
78
79
80
81
82
83
84
 
# 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 = []) ⇒ Object 



128
129
130
131
132
133
 
# 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) ⇒ Object

fonction qui sert uniquement pour les tests



121
122
123
124
125
126
 
# 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) ⇒ Object 



87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
 
# 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