Apriori 알고리즘의 계산 복잡도(computational complexity)는 여러 요인에 따라 달라집니다. 아래에서는 알고리즘의 성능을 좌우하는 주요 변수와 각 처리 단계별 연산 비용을 자세히 살펴봅니다.
1. 지지도 임계값(Support Threshold)
지지도 임계값을 낮추면 더 많은 항목집합이 '빈발(frequent)'로 판정됩니다. 이렇게 되면 생성·검토해야 할 후보 항목집합 수가 크게 늘어나므로 알고리즘의 계산 복잡도가 증가합니다.
또한 임계값이 낮아질수록 빈발 항목집합의 최대 크기도 커지는 경향이 있으며, 최대 크기가 커질수록 데이터셋 전체를 스캔하는 패스(pass) 횟수도 그만큼 늘어납니다.
2. 항목 수(차원성)
항목 수가 많아질수록 각 항목의 지지도 개수(support count)를 저장할 공간이 더 필요합니다. 데이터의 차원성이 높아져 빈발 항목 수가 함께 증가하면, 생성되는 후보 항목집합 수가 늘어나면서 연산량과 I/O 비용도 함께 증가합니다.
3. 트랜잭션 수(Number of Transactions)
Apriori 알고리즘은 데이터셋을 여러 번 반복 스캔하는 구조이므로, 트랜잭션 수가 많아질수록 실행 시간도 비례하여 증가합니다.
4. 평균 트랜잭션 폭(Average Transaction Width)
밀집된(dense) 데이터셋에서는 평균 트랜잭션 폭이 클 수 있으며, 이는 다음 두 가지 방식으로 복잡도에 영향을 줍니다.
- 평균 트랜잭션 폭이 커질수록 빈발 항목집합의 최대 크기도 증가하는 경향이 있습니다.
- 트랜잭션 폭이 넓으면 하나의 트랜잭션에 더 많은 항목집합이 포함되므로, 지지도 계산 과정에서 수행되는 해시 트리(hash tree) 탐색 횟수가 늘어납니다.
단계별 연산 비용 분석
① 빈발 1-항목집합 생성
각 트랜잭션마다 해당 트랜잭션에 포함된 모든 항목의 지지도 개수를 갱신해야 합니다. 평균 트랜잭션 폭을 w, 전체 트랜잭션 수를 N이라 하면 이 작업에는 O(Nw)의 시간이 소요됩니다.
② 후보 생성(Candidate Generation)
k-항목집합 후보를 생성할 때는 빈발 (k−1)-항목집합 쌍을 결합하며, 두 집합이 최소 k−2개의 공통 항목을 갖는지 확인합니다. 각 결합 연산에는 최대 k−2번의 동등성 비교가 필요합니다.
최선의 경우: 각 결합 단계마다 유효한 후보 k-항목집합 하나가 생성됩니다.
최악의 경우: 이전 반복에서 발견된 모든 빈발 (k−1)-항목집합 쌍을 결합해야 하므로, 빈발 항목집합 병합의 총 비용은 다음 범위 내에 있습니다.
$$\mathrm{\displaystyle\sum\limits_{k=2}^w\:(k-2)|C_{k}|<\:Cost\:of\:merging\:<\displaystyle\sum\limits_{k=2}^w\:(k-2)|F_{k-1}|^2}$$
③ 해시 트리 구축
후보 생성 과정에서는 후보 항목집합을 저장하기 위한 해시 트리도 함께 구축됩니다. 트리의 최대 깊이가 k이므로, 후보 항목집합으로 해시 트리를 채우는 비용은 O($\mathrm{\displaystyle\sum\limits_{k=2}^w\:k|C_{k}|}$)입니다.
④ 후보 가지치기(Candidate Pruning)
가지치기 단계에서는 각 후보 k-항목집합의 (k−2)개 부분집합이 모두 빈발인지 확인해야 합니다. 해시 트리에서 후보를 조회하는 비용이 O(k)이므로, 후보 가지치기 단계에는 O($\mathrm{\displaystyle\sum\limits_{k=2}^w\:k|C_{k}|}$)의 시간이 필요합니다.