Mining Association Rules between Sets of Items in Large Databases (1993)
March 2, 2024ある商品と一緒に買われやすい商品を小売の購買履歴から分析する初期の手法にMining Association Rules between Sets of Items in Large Databasesがある。 抽出される規則は、商品の集合と1つの商品のペアからなり、集合のすべての商品を買われるときに他方の商品も買われやすいことを意味する。 アルゴリズムは、規則を抽出するだけでなく、規則の確信度と支持度も計算する。 確信度は、規則の前提にある商品の集合を含むトランザクションのうち規則を満たすものの割合であり、規則の信憑性を意味する。 支持度は、すべてのトランザクションに対する規則に表れる商品を含むトランザクションの割合であり、規則を適用できる機会の多さを意味する。 アルゴリズムは、しきい値以下の支持度の規則を無視することで、現実的な速度で実行できる。
アルゴリズムはトランザクションの集合と支持度のしきい値を引数にとり、しきい値より大きい規則の集合を返す。 以下にアルゴリズム LargeItemsets の疑似コードを示す。 アルゴリズムにおけるlargeはしきい値の支持度よりも大きいことを意味する。
procedure LargeItemsets(database tuples, minsupport)
let L = {} // Large set
let F = {{}} // Frontier set
while F != {}:
// make a pass over the database
let C = {} // Candidate set
for t in database tuples:
for f in F:
if t.contains(f):
let C_f = []
Extend(f, t, C_f)
for c_f in C_f:
if c_f in C:
c_f.count++
else:
c_f.count = 0
C += c_f
// consolidate
let F = {}
for c in C:
if c.count / size(database tuples) > minsupport:
L += c
if c should be used as a frontier in the next pass:
F += c
return L
procedure Extend(X: itemset, t: tuple, results: List[itemset])
let item I_j such that forall I_l in X, I_j >= I_l
for t in I_k such that I_k > I_j:
results.append([X, I_k])
if (XI_k) is exptected to be large:
Extend(XI_k, t, results)
Frontier set Fは、商品を追加すれば規則になりえる商品の集合をfとすると、fの集合であり、最初は空集合で初期化される。
fを真部分集合とするトランザクション tがあれば、tにありf にない商品を1つ追加された商品の集合c_fの支持度を計算する。
その支持度がしきい値より大きければ、返り値になる規則の集合 L に加える。
すべてのトランザクションを調べた後は、直前に見つけた規則よりも1つ商品の数が多い規則のためのFrontier setをつくる。
支持度の期待値sがしきい値より低いが実際の支持度がしきい値よりも大きいc_fの集合が次のFrontier setになる。
トランザクションに商品が含まれる確率は互いに独立であると仮定し、c_fの期待値sを、fを含むトランザクションの割合とc_fの1つ追加された商品を含むトランザクションの割合の積とみなす。
その結果Frontier setが空集合であれば、アルゴリズムを終了する。