빈발 집합 하나가 있으면 그 부분집합이 모두 빈발이라, 빈발 패턴을 다 적으면 목록이 감당할 수 없이 길어진다. 닫힌 패턴은 “더 큰 집합으로 늘려도 지지도가 줄지 않는” 집합을 버리고 나머지만 남긴다. 이것만 있으면 모든 빈발 패턴과 그 지지도를 되살릴 수 있다(손실 없는 압축). 최대 패턴은 더 늘리면 빈발이 아니게 되는 가장 큰 집합만 남겨 더 짧지만, 각 패턴의 지지도는 잃는다.
예시로 보기
{A, B, C, D}가 빈발이면 그 부분집합 15개가 모두 빈발이다. 다 계산하고 저장해야 할까?
거래가 2개뿐인 자료를 본다. 거래 1은 \(\{a_1, \dots, a_{50}\}\), 거래 2는 \(\{a_1, \dots, a_{100}\}\)이고 최소 지지 개수는 1이다.
- 빈발 패턴은 \(\{a_1, \dots, a_{100}\}\)의 공집합 아닌 부분집합 전부, \(2^{100} - 1\)개다.
- \(\{a_1, a_2\}\)는 지지 2인데, 이것을 늘린 \(\{a_1, \dots, a_{50}\}\)도 지지 2다. 늘려도 지지도가 같으니 \(\{a_1, a_2\}\)는 더 큰 집합이 대신 말해 준다. 닫힌 패턴은 \(\{a_1, \dots, a_{50}\}{:}2\)와 \(\{a_1, \dots, a_{100}\}{:}1\) 두 개뿐이다.
- 더 늘리면 빈발이 아니게 되는 가장 큰 집합, 즉 최대 패턴은 \(\{a_1, \dots, a_{100}\}\) 하나다.
\(\{a_2, a_{45}\}\)의 지지도를 알고 싶다. 닫힌 패턴 중 이것을 포함하는 것은 둘이고, 그중 큰 지지도 2가 답이다. 최대 패턴만 있으면 “1 이상”이라는 것밖에 모른다.
정의
빈발 항목 집합 \(X\)에 대해
- 닫힌 빈발 패턴: 지지도가 같은 더 큰 집합이 없다. \(\nexists\, Y \supsetneq X\) such that \(\operatorname{sup}(Y) = \operatorname{sup}(X)\). (\(\nexists\)는 “존재하지 않는다”, \(Y \supsetneq X\)는 “\(Y\)가 \(X\)를 담고 더 크다”이다.)
- 최대 빈발 패턴: 빈발인 더 큰 집합이 없다. \(\nexists\, Y \supsetneq X\) such that \(\operatorname{sup}(Y) \ge \text{min\_sup}\).
더 큰 집합의 지지도는 작은 집합의 지지도 이하다. 그래서 더 큰 집합 \(Y\)와 \(X\)의 관계는 둘뿐이다.
- \(\operatorname{sup}(Y) = \operatorname{sup}(X)\): \(X\)와 \(Y\)의 정보량이 같다. \(X\)를 따로 저장할 이유가 없다.
- \(\operatorname{sup}(Y) < \operatorname{sup}(X)\): \(X\)에 \(Y\)에 없는 정보가 있다.
| 조건 | 잃는 정보 | 목적 | |
|---|---|---|---|
| 빈발 | 지지도 ≥ min_sup | 없음 | 모든 패턴 |
| 닫힌 | 지지도가 같은 더 큰 집합이 없다 | 없음 | 손실 없는 압축 |
| 최대 | 빈발인 더 큰 집합이 없다 | 지지도 | 패턴 수 최소화 |
그래서 빈발 ⊇ 닫힌 ⊇ 최대다. 최대 패턴은 닫혀 있다. 지지도가 같은 더 큰 집합이 있다면 그 집합도 빈발이라 최대가 아니기 때문이다.
flowchart TB
subgraph F["빈발 패턴: 2¹⁰⁰ − 1개"]
subgraph C["닫힌 패턴: 2개"]
C1["a1…a50, 지지 2"]
subgraph M["최대 패턴: 1개"]
M1["a1…a100, 지지 1"]
end
end
X["a1, a2 같은 나머지 전부"]
end
예시로 보기의 거래 2개 예를 상자 안의 상자로 그렸다. 바깥 상자에서 안쪽 상자로 갈수록 남는 패턴이 확 줄어든다. 닫힌 상자의 두 패턴에는 지지도가 붙어 있어, 나머지 패턴의 지지도를 모두 되살릴 수 있다.
지지도 되살리기. 빈발 집합 \(X\)의 지지도는 \(X\)를 포함하는 닫힌 패턴들의 지지도 중 가장 큰 값이다1. \(X\)에서 지지도를 유지하며 늘릴 수 있는 데까지 늘린 집합(닫힘)이 그 목록에 반드시 있기 때문이다.
연결
확인 문제
C1 닫힌 빈발 패턴과 최대 빈발 패턴을 정의하고, 각각 무엇을 잃는지 쓰라.
답: 닫힌 패턴은 지지도가 같은 더 큰 집합이 없는 빈발 집합이고, 잃는 것이 없다. 최대 패턴은 빈발인 더 큰 집합이 없는 빈발 집합이고, 부분집합들의 지지도를 잃는다.
C2 거래 9개 ABE, ABD, BC, BD, AC, BC, AC, ABCE, ABC(최소 지지 개수 2)의 빈발 패턴은 13개다. 이 중 닫힌 패턴과 최대 패턴을 찾으라.
답: 닫힌 패턴 9개: A6, B7, C6, AB4, AC4, BC4, BD2, ABC2, ABE2. (D2는 BD2에, E2·AE2·BE2는 ABE2에 같은 지지도로 포함되어 닫히지 않았다.) 최대 패턴 3개: BD, ABC, ABE1.
C3 모든 최대 패턴은 닫힌 패턴이다. 이유를 대라.
답: 최대 패턴 \(X\)가 닫히지 않았다고 하자. 그러면 지지도가 같은 더 큰 집합 \(Y\)가 있고, \(\operatorname{sup}(Y) = \operatorname{sup}(X) \ge\) min_sup이라 \(Y\)는 빈발이다. 빈발인 더 큰 집합이 있으니 \(X\)는 최대가 아니다. 모순이다(귀류법).