Class: RankAggregation::Ranker

Inherits:
Object
  • Object
show all
Defined in:
lib/rank-aggregation/ranker.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Ranker

Returns a new instance of Ranker.



11
12
13
14
15
16
17
18
19
 
# File 'lib/rank-aggregation/ranker.rb', line 11

def initialize
  @less_scores = {}
  @items = Set.new
  @smoothing = 5
  @vote_count = 0
  @rank_count = 0
  self.logger = Logger.new(STDERR)
  self.logger.level = Logger::WARN
end

Instance Attribute Details

#items ⇒ Object

Returns the value of attribute items.



9
10
11
 
# File 'lib/rank-aggregation/ranker.rb', line 9

def items
  @items
end

#less_scores ⇒ Object

Returns the value of attribute less_scores.



9
10
11
 
# File 'lib/rank-aggregation/ranker.rb', line 9

def less_scores
  @less_scores
end

#logger ⇒ Object

Returns the value of attribute logger.



9
10
11
 
# File 'lib/rank-aggregation/ranker.rb', line 9

def logger
  @logger
end

#smoothing ⇒ Object

Returns the value of attribute smoothing.



9
10
11
 
# File 'lib/rank-aggregation/ranker.rb', line 9

def smoothing
  @smoothing
end

Instance Method Details

#add_ranking(xs) ⇒ Object 



21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
 
# File 'lib/rank-aggregation/ranker.rb', line 21

def add_ranking(xs)
  xs = xs.uniq
  return if xs.size <= 1

  @rank_count += 1

  reset_cached
  xs.each{|x| @less_scores[x] ||= Hash.new(0.0); items.add x }

  weight = 1.0 / (0.5 * xs.size * (xs.size - 1))

  (0...xs.length).each{|i|
    ((i+1)...xs.length).each{|j|
      @less_scores[xs[i]][xs[j]] += weight
    }
  }

  @vote_count += 1
end

#combined_rankings ⇒ Object 



99
100
101
102
103
 
# File 'lib/rank-aggregation/ranker.rb', line 99

def combined_rankings
  @_combined_rankings ||= begin
    triangle_shuffle(rough_combined_rankings)
  end
end

#kendall_distance ⇒ Object 



105
106
107
 
# File 'lib/rank-aggregation/ranker.rb', line 105

def kendall_distance
  @_kendall_distance ||= kendall_distance_for(combined_rankings)
end

#less_chances ⇒ Object 



41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
 
# File 'lib/rank-aggregation/ranker.rb', line 41

def less_chances
  @_less_chances ||= begin 
    logger.debug "calculating less_chances"
    less_chances = Hash.new{|h, k| h[k] = Hash.new(0.5)}

    less_scores.each{|x, vs|
      vs.each{|y, c|
        p = (c + 0.5 * self.smoothing) / (self.smoothing + c + less_scores[y][x])
        less_chances[x][y] = p
        less_chances[y][x] = 1 - p
      }
    }
    logger.debug "calculating less_chances complete"
    less_chances    
  end
end

#rough_combined_rankings ⇒ Object 



93
94
95
96
97
 
# File 'lib/rank-aggregation/ranker.rb', line 93

def rough_combined_rankings
  @_rough_combined_rankings ||= begin
    @items.sort{|x, y| rough_scores[x] <=> rough_scores[y] }
  end
end

#rough_scores ⇒ Object 



58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
 
# File 'lib/rank-aggregation/ranker.rb', line 58

def rough_scores
  @_rough_scores ||= begin
    logger.debug "calculating rough_scores"
    # This markov chain is based off MC4. The idea is as follows:
    # Starting at an item we pick one of the other items at random. 
    # We then transition to that item with probability P(i < j). 
    # If we fail to transition we stay where we are.
    # i.e. the probability of transitioning form i to j with i != j is 1/(n-1) P(i < j).

    logger.debug "calculating transition probabilities"
    transitions = {}

    @items.each{|i|
      transitions[i] = {}
      tot = 0.0
      @items.each{|j|
        next if i == j
        p = less_chances[i][j] / (@items.size - 1)
        tot += p
        transitions[i][j] = p
      }
      if tot <= 1
        transitions[i][i] = 1 - tot
      else
        transitions[i][i] = 0
      end
    }

    logger.debug "calculating transition probabilities complete"
    result = MarkovChain.new(@items, transitions, logger).stationary_distribution
    logger.debug "calculating rough_scores complete"
    result
  end
end