アルゴリズムの理解のために、Apriori algorithm を Ruby で実装してみました。 お勉強用なので、性能は度外視しています。

apriori.rb

# -*- coding: utf-8 -*-

# Apriori algorithm の実装です
#
# http://en.wikipedia.org/wiki/Apriori_algorithm の擬似コードと
# http://www.codeproject.com/Articles/70371/Apriori-Algorithm を
# 参考にしています

require 'set'

#
# アイテムセットを表します
#
class Itemset
  def initialize(items)
    # items には、item (数値) の昇順に要素が格納されていることを
    # 前提としています
    @items = items
    @count = 0
  end

  attr_reader :count
  attr_reader :items

  #
  # 指定されたトランザクション内にこのアイテムセットが
  # 存在する場合に、出現回数をインクリメントします
  #
  def increment_if_exist_in(tran)
    @items.each do |item|
      # TODO この実装では性能がでないが、面倒なのでとりあえずこうしておく
      if !tran.include?(item)
        return
      end
    end

    @count += 1
  end

  #
  # 指定された item を加えて生成される新しいアイテムセットが
  # 正規なアイテムセットである場合に true　を返却します
  #
  # @items が item の昇順に格納されていることを利用し、
  # 組み合わせの重複が発生しないようにこのメソッドで制御します
  #
  def canonical?(item)
    return @items[-1] < item
  end

  #
  # item を加えた新しい Itemsset を生成して返却します
  #
  def new_candidate(item)
    new_itemset = Array.new(@items)
    new_itemset << item
    return Itemset.new(new_itemset)
  end

  def to_s
    return "#{@items.to_s} -> #{@count}"
  end
end


class Apriori
  #
  # 与えられたトランザクションから
  #
  def initialize(transactions, min_support)
    @transactions = transactions
    @min_support = min_support
    @rules = []

    items = Set.new
    transactions.each do |tran|
      tran.each { |item| items << item }
    end

    @current_itemsets = []
    items.to_a.sort.each do |item|
      @current_itemsets << Itemset.new([item])
    end

    # L1 相当のアイテムセットを求める
    count_itemset_frequencies(@current_itemsets)
    @current_itemsets = extract_frequent_itemsets(@current_itemsets)

    # アイテムセットを順次拡張していく際に利用する、support の閾値を
    # 超えたアイテムの集合 @freq_items を求めておく
    @freq_items = []
    @current_itemsets.each do |itemset|
      @freq_items << itemset.items[0]
    end

    @rules << @current_itemsets
  end

  #
  # 全トランザクションをスキャンして、指定された各アイテムセットの
  # 出現回数を数え上げます
  #
  def count_itemset_frequencies(itemsets)
    @transactions.each do |tran|
      itemsets.each do |itemset|
        itemset.increment_if_exist_in(tran)
      end
    end
  end

  #
  # 指定されたアイテムセットから、頻出するアイテムセットのみを
  # 抽出します
  #
  def extract_frequent_itemsets(itemsets)
    result = []

    itemsets.each do |itemset|
      result << itemset if itemset.count >= @min_support
    end

    return result
  end

  #
  # 既存のアイテムセットから、候補となる次のアイテムセットを
  # 生成します
  #
  def generate_candidates(base_itemsets)
    candidate_itemsets = []

    base_itemsets.each do |itemset|
      @freq_items.each do |item|
        candidate_itemsets << itemset.new_candidate(item) if itemset.canonical?(item)
      end
    end

    return candidate_itemsets
  end

  #
  # 既存のアイテムセットをもとに、次のアイテムセットを求めます
  #
  # 次のアイテムセットが求まらなかった場合、false を返却します。
  #
  def generate_next()
    candidate_itemsets = generate_candidates(@current_itemsets)
    count_itemset_frequencies(candidate_itemsets)
    next_itemsets = extract_frequent_itemsets(candidate_itemsets)
    @rules << next_itemsets
    @current_itemsets = next_itemsets
    
    return !next_itemsets.empty?
  end

  def to_s
    result = ""

    @rules.each do |itemsets|
      itemsets.each do |itemset|
        result += itemset.to_s + "\n"
      end
    end

    return result
  end
end

# アプリオリアルゴリズムを実行するデモプログラムです
def demo
  # アソシエーションルールを求める対象のトランザクション
  transactions = [
    [:A, :C, :D],
    [:B, :C, :E],
    [:A, :B, :C, :E],
    [:B, :E]
  ]

  min_support = 2

  apriori = Apriori.new(transactions, min_support)

  start_time = Time.now

  while apriori.generate_next() do
    end_time = Time.now
    puts end_time - start_time
    start_time = Time.now
  end

  puts "--"

  puts apriori.to_s
end

demo() if $0 == __FILE__