Apriori Algorithm

論文: Rakesh Agrawal and Ramakrishnan Srikant. Fast Algorithms for Mining Association Rules. In Proc. of the 20th Intl Conference on Very Large Databases

アルゴリズム: 

  1. L1 = { I | support_count(I)  min_sup, |I| = 1 }

  2. for k=2 to max do
begin
  Ck = { join(I,I') | I,I'  Lk-1 and joinable(I,I') } (*1)
  Lk = { I | support_count(I)  min_sup, I  Ck }
end
    *1) (Apriori property) k-itemset Iがfrequentなら、 (k-1)-itemset I' Iは必ずfrequentである。 
    joinable(I,I')
  begin
    return I1 = I'1 and I2 = I'2 and Ik-2 = I'k-2 and Ik-1 < I'k-1 (*2)
  end
    *2) frequentなk-itemset Iに対して、 { I1, I2, ..., Ik-1 } (末尾だけ除いたもの) と { I1, I2, ..., Ik-2, Ik } (末尾の一つ前だけ除いたもの) は frequentな(k-1)-itemsetであるので、Apriori propertyから Lk-1に含まれているはずである。 
    join(I,I')
  begin
    return { I1, I2, ..., Ik-2, Ik-1, I'k-1 }
  end

yamaguch@mail.ecc.u-tokyo.ac.jp
Copyright 2008 Kazunori Yamaguchi 山口和紀@東京大学総合文化研究科