최대 빈도 항목집합의 정의
최대 빈도 항목집합(maximal frequent itemset)은 직접 상위집합(direct superset) 가운데 어느 하나도 빈도 항목집합에 해당하지 않는 빈도 항목집합을 의미합니다. 격자(lattice) 구조 안의 항목집합들은 빈도 항목집합과 비빈도 항목집합이라는 두 그룹으로 나뉘며, 이 두 그룹을 구분하는 경계를 '빈도 항목집합 경계(frequent itemset border)'라고 부릅니다. 이 경계는 보통 점선으로 표시됩니다.
경계 위에 위치한 항목집합은 모두 빈도 항목집합이고, 경계 아래에 있는 항목집합(음영 처리된 노드)은 비빈도 항목집합입니다. 경계 근처에 있는 항목집합 중 {a, d}, {a, c, e}, {b, c, d, e}는 직접 상위집합이 모두 비빈도 항목집합이기 때문에 최대 빈도 항목집합으로 간주됩니다.
예를 들어 {a, d}는 직접 상위집합인 {a, b, d}, {a, c, d}, {a, d, e}가 모두 비빈도 항목집합이므로 최대 빈도 항목집합입니다. 반면 {a, c}는 직접 상위집합 {a, c, e}가 여전히 빈도 항목집합이기 때문에 최대가 아닌(non-maximal) 항목집합입니다.
간결한 표현을 가능하게 하는 최대 빈도 항목집합
최대 빈도 항목집합은 빈도 항목집합 전체를 압축된 형태로 기술할 수 있게 해줍니다. 다시 말해, 모든 빈도 항목집합을 도출해낼 수 있는 가장 작은 항목집합의 집합을 형성합니다. 예를 들어 빈도 항목집합은 다음과 같이 두 그룹으로 나눌 수 있습니다.
- 항목 a로 시작하며 c, d, e를 포함할 수 있는 빈도 항목집합 — 이 그룹에는 {a}, {a, c}, {a, d}, {a, e}, {a, c, e} 등이 속합니다.
- 항목 b, c, d, e로 시작하는 빈도 항목집합 — 이 그룹에는 {b}, {b, c}, {c, d}, {b, c, d, e} 등이 속합니다.
첫 번째 그룹의 빈도 항목집합은 {a, c, e} 또는 {a, d}의 부분집합이며, 두 번째 그룹의 빈도 항목집합은 {b, c, d, e}의 부분집합입니다. 따라서 최대 빈도 항목집합 {a, c, e}, {a, d}, {b, c, d, e}만으로도 모든 빈도 항목집합을 간결하게 표현할 수 있습니다.
최대 빈도 항목집합의 장점과 한계
데이터셋에서 생성될 수 있는 빈도 항목집합의 수가 지수적으로 증가하는 경우, 최대 빈도 항목집합은 매우 유용한 요약 정보를 제공합니다. 다만 이 방법이 실용적으로 활용되려면 부분집합을 일일이 열거하지 않고도 최대 빈도 항목집합만을 효율적으로 발견하는 알고리즘이 필요합니다.
그러나 간결한 표현을 제공하는 대신, 최대 빈도 항목집합은 자신의 부분집합에 대한 지지도(support) 정보를 포함하지 않습니다. 예컨대 최대 빈도 항목집합 {a, c, e}, {a, d}, {b, c, d, e}의 지지도만으로는 그 부분집합들의 지지도를 알 수 없습니다.
따라서 최대가 아닌 빈도 항목집합의 지지도 개수를 구하려면 데이터셋을 한 번 더 스캔하는 추가 과정이 필요합니다. 경우에 따라서는 지지도 정보까지 보존하면서 빈도 항목집합을 최소 형태로 기술하는 것이 더 바람직할 수 있습니다.