공돌이는 파닥파닥

http://cvlab.epfl.ch/~ksmith/tutorial/rjmcmc.php

지난 글에서는 보다 빨리 Frequent itemset(이하 Fset)을 찾는 방법을 소개하였다. 그러나, 이전에 소개한 내용은 판매 상품들의 계층적인 구조를 생각하지 않았다. 실제로 판매되는 상품들은 대부분 계층적인 구조로 나타낼 수 있고 이러한 구조에서, Category1을 구입한 사람이 Category2를 구입하거나, Sub Category1을 구입하는 경우를 찾고 싶다면 어떻게 해야할까? 이번에는 계층적인 구조를 가지는 자료에서 Fset을 찾는 방법을 알아보자. 참고논문 : R. Srikant and R. Agrawal, "Mining Generalized Association Rules", VLDB 1995. PDF ps.gz Abstract Google Scholar Jacket과 Hiking..

지난 게시글에 Naïve한 Frequent Associatoin Rule Algorithm은 2의 n승만큼의 연산이 필요하다고 했었다. 이는 만일 데이터의 크기가 10개라면… 1024번의 연산이 필요하다는 의미이다. (아이템이 중복되어도 10개인 것이다. 같은 것이 있어도 또 세고 넘어가야 한다.) 이를 해결하기 위한 알고리즘으로 Apriori 알고리즘을 소개한다. Apriori 알고리즘의 중요한 원칙은 다음과 같다. 원칙: Frequent하지 않은 item set은 그 superset 역시 Frequent 하지 않다. 이 간단한 원칙 하나로, 연산의 수를 크게 줄일 수 있다. 참고 논문 : R. Agrawal and R. Srikant, "Fast Algorithms for Mining Associat..