Toivonen’s Algorithm
해당 포스팅은 스탠포드의 Jeff Ullman 교수님의 강의 와 Mining of Massive Datasets(Jure Leskovec, Anand Rajaraman, Jeff Ullman) 책 을 참고하였습니다.
Toivonen’s Algorithm
Toivonen 알고리즘은 샘플링에서의 무작위성을 사용합니다.
이 알고리즘은 작은 샘플을 거치는 하나의 패스를 수행하고,
하나의 full 패스를 사용하여 전체를 거칩니다.
여기서는 false negative, false positive 가 발생하지 않습니다.
그러나 전체에 패스를 수행할 때 알고리즘이 실패할 확률이 약간 있습니다.
이 상황에서는 성공할 때까지 반복합니다.
전체 패스 이전 작업은, 작은 샘플만 가지고 수행하는 패스이므로 실패할 때의 loss 가 크진 않습니다.
Toivonen 알고리즘은 입력 데이터셋에서 샘플을 선택하는 것 부터 시작됩니다.
선택된 샘플 안에서 후보 빈도 아이템셋(candidate frequent itemset)을 찾습니다.
이 작업은 거의 simple 알고리즘과 동일하며,
차이는 임계값을 더 작게 설정하는 것입니다.
만약 support 임계값이 s 이고, 샘플이 전체의 p 의 크기일 때,
샘플에서 임계값은 0.8ps, 0.9ps 정도로 설정합니다.
임계값을 더 적게 만들수록,
샘플의 빈도 아이템셋이 늘어나 메모리가 더 많이 필요합니다.
대신 알고리즘이 실패할 확률을 낮춰줍니다.
샘플에 대한 빈도 아이템셋의 모음을 구성하였다면,
negative border 를 생성할 수 있습니다.
negative border 은 샘플에서 그 자체가 빈번하진 않지만 그것들의 모든 immediate subset(부분 집합 중 |s| = |S|-1 인 부분집합)들이 빈번한 아이템셋의 모음입니다.
예를들어
샘플에는 {A,B,C,D,E} 가 있고, 빈번한 것이 {A} {B} {C} {D} {B,C} 인 경우
여기서 negative border 는 {A,B} {A,C}, {A,D}, {B,D} 입니다.
Toivonen 알고리즘을 완성하기 위해, 전체 데이터를 거치는 패스를 만듭니다.
모든 아이템 셋이 샘플에서 빈번하거나, negative border 에 있는 아이템셋을 카운팅합니다.
출력은 두가지로 나올 수 있습니다.
- negative border 의 맴버가 전체 데이터셋에서 빈번하지 않습니다.
이와 같은 경우, 빈도 아이템의 실제 집합이 정확하게 전체에서 빈번하게 발견된 아이템셋 입니다.(샘플에서) - 전체에서 negative border 의 일부가 빈번합니다.
이런 경우, Negative border 나 샘플에서의 빈도 아이템셋의 모음 둘다 아니면서, 전체에서는 빈번한 더 큰 집합이 없다는 것을 확신할 수 없습니다.
즉, 다른 빈도 아이템셋이 없다는 것을 확신하지 못합니다.
그래서 이 상황에서는, 새로운 샘플로 다시 알고리즘을 반복해야합니다.
Why Toivonen’s Algorithm Works
이 알고리즘은 false positive 는 생성하지 않습니다.
전체 패스에서 빈도 아이템셋을 확인하기 때문입니다.
이 알고리즘에서 false negative 가 없다고 주장하기 위해서는,
전체에서 negative border 중 빈번한 맴버가 없을 때,
다음과 같은 아이템셋이 없다는 것을 보여 주어야합니다.
- 전체에서 빈번하지만
- 샘플에서의 빈도 아이템셋의 모음과, negative border 에 둘 다 없는 경우
반대로 생각해봅시다.
집합 S 가 있고,
전체에서는 빈번하지만,
샘플에서는 빈번하지 않고,
negative border 에도 없다고 칩니다.
monotonicity 에 의해,
S 의 모든 부분 집합은 전체에서 모두 빈번합니다.
T를 S의 부분집합 중
샘플에서는 빈번하지 않은, 가장 작은 크기의 부분집합이라 합시다.
- 여기서 T 는 반드시 negative border 에 있어야 합니다.
- 확실히 T 는 negative border 에 포함될 조건 중 하나를 만족합니다.
- T는 샘플에서 빈번하지 않습니다.
다른 조건 또한 만족합니다. - T의 immediate subset 은 각각은 샘플에서 빈번합니다.
만약 어떤 T 의 immediate subset 이 샘플에서 빈번하지 않다면,
이는 S의 부분 집합이고, 이는 T 보다 작지만 샘플에서 빈번하지 않습니다.
앞서 T를 정의 할 때, S의 부분집합 중 샘플에서 빈번하지 않은 가장 작은 부분집합이라고 했습니다.
이는 모순이므로,
T는 반드시 negative border 에 있어야 합니다.
T 는 negative border 이고 전체에서 빈번합니다.
결론적으로 위의 증명이 완료됩니다.
정리하자면
A : 전체에서 negative border 가 빈번한 것이 없다.
B : 전체에서 빈번하지만, 샘플에서 빈도 아이템셋과, negative border 둘 다에 없는 경우가 없다.
이고 $A\rightarrow B$ 입니다.
B’ : 집합 S 는 전체에서 빈번하고, 샘플에서 빈도 아이템셋과, negative border 에 없는 경우 이다.
A’ : 전체에서 negative border 가 빈번한 T 가 있다.
$B’ \rightarrow A’$ 이므로 $A\rightarrow B$ 와 동치로 증명이 됩니다.
Comments