Association Rules

데이터에서 유의미한 아이템 간의 연관성을 찾아내는 규칙이다. 예를 들어, {a, b, c}를 구매한 소비자들이 {d, e}를 함께 구매했더라는 규칙, 즉 {a, b, c} → {d, e}라는 형태로 표현된다.

Terms

• $I$: 하나의 basket 안에 포함된 아이템 셋

• $support(I)$: $I$에 포함된 모든 아이템을 가지는 basket의 개수

• $s$: support threshold

• $c$: confidence threshold

• $P[j] = \frac{\text{number of baskets containing } j}{\text{total number of baskets}}$

• $confidence(I \to j) = \frac{support(I \cup j)}{support(I)}$

• $interest(I \to j) = |confidence(I \to j) - P[j]|$

• $frequent = support(I) \geq s$

• $confident= confidence(I \to j) \geq c$

• $interesting = interest(I \to j) \geq 0.5$

1. Naive Algorithm

Triangular Matrix

• 아이템 간 모든 pair를 비교하여 counting한다.

• 이 방법은 각 아이템 pair에 대해 4바이트가 필요하며, 메모리 사용량이 매우 크다.

• 구현이 간단하지만 메모리 사용이 비효율적이고 데이터 크기가 커질수록 성능이 저하된다.

Triples

• count가 0보다 큰 pair만을 hash table에 저장한다. 예를 들어, 아이템 pair {i, j}에 대해 count가 c이면, c = [i, j, c] 형태이다.

• 이 방법은 각 pair당 12바이트가 필요하며, 필요하지 않은 데이터는 저장하지 않으므로 메모리 사용을 줄일 수 있다.

2. A-Priori Algorithm

Naive 방법보다 효율적으로 association rules를 찾기 위해 설계되었다. 단계별로 frequent한 itemset만을 대상으로 작업을 진행하며, 불필요한 계산을 줄이는 데 중점을 둔다.

Pass1: C_i

• 각 basket을 읽고, i개의 아이템으로 구성된 모든 pair에 대한 counting을 진행한다.

• 이때, counting된 pair 중 frequent한 pair만을 선택한다.

Pass2: L_i

• 다시 basket을 읽고, Pass1에서 찾은 frequent한 pair들에 대해 추가적인 counting을 수행한다.

3. PCY(Park-Chen-Yu) Algorithm

A-Priori 알고리즘을 개선한 방식으로, 주로 대규모 데이터베이스에서 연관 규칙을 효율적으로 탐색하기 위해 설계되었다.

Pass1

• main memory에 hash table을 만드는데, 해시 충돌을 방지하기 위해 최대한 많은 bucket을 만든다.

• 각 pair의 count를 세고, key가 count인 위치에 값을 1 증가시킨다.

Pass2

• frequent한 bucket(>=s)에 있는 pair만 candidate itemsets으로 한다.

• 우리는 해당 bucket이 frequent/infrequent 한지만 볼 것이므로 bit-vector를 사용하여 frequent(1), infrequent(0)으로 표현한다.