Apriori 알고리즘의 계산 복잡성은 다음과 같은 요인에 의해 영향을 받을 수 있습니다. -
지원 임계값 − 지원 임계값을 낮추면 더 높은 항목 집합이 자주 표시되는 것으로 나타납니다. 이것은 더 높은 후보 항목 집합이 생성되고 계산되어야 하기 때문에 알고리즘의 계산 복잡성에 좋지 않은 영향을 미칩니다.
빈번한 항목 집합의 최대 크기는 낮은 지원 임계값으로 개선하는 데에도 영향을 미칩니다. 빈번한 항목 집합의 최대 크기가 향상됨에 따라 데이터 집합에 대해 더 많은 패스를 생성하려면 알고리즘이 필요합니다.
항목 수(차원) − 여러 아이템의 개수가 증가할수록 아이템의 지원 개수를 저장하기 위해 더 많은 공간이 필요합니다. 데이터의 차원에 따라 다중 빈도 항목도 증가하면 알고리즘에 의해 생성되는 후보 항목 집합의 수가 더 많기 때문에 계산 및 I/O 값이 증가합니다.
거래 수 − Apriori 때문에 알고리즘은 데이터 세트에 대해 반복적인 전달을 생성하고 트랜잭션 수가 많을수록 런타임이 향상됩니다.
평균 거래 폭 − 밀도가 높은 데이터 세트의 경우 평균 트랜잭션 너비가 높을 수 있습니다. 이는 평균 트랜잭션 너비가 증가할수록 빈도가 높은 항목 집합의 최대 크기가 증가하는 것과 같은 두 가지 방법에서 Apriori 알고리즘의 복잡성에 영향을 줍니다. 트랜잭션 너비가 증가하면 트랜잭션에 더 높은 항목 집합이 포함됩니다. 이렇게 하면 지원 계산 중에 구현되는 다중 해시 트리 순회가 증가합니다.
빈번한 항목 집합 생성 − 각 트랜잭션에 대해 트랜잭션에 있는 각 항목에 대한 지원 개수를 업데이트해야 합니다. w가 평균 트랜잭션 너비임을 고려할 때 이 작업에는 O(Nw) 시간이 필요하며 여기서 N은 총 트랜잭션 수입니다.
후보 생성 − 후보 k-itemsets, 빈번한 (k - 1)- itemsets의 쌍을 결합하여 최소 k - 2개의 공통 항목이 있는지 여부를 결정할 수 있습니다. 각 결합 작업은 최대 k - 2개의 동등 비교가 필요합니다. 최상의 시나리오에서 각 결합 단계는 실행 가능한 후보 k-itemset을 만듭니다.
최악의 시나리오에서 알고리즘은 이전 반복에서 발견된 빈번한 (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}| }$).
후보 가지치기(pruning) 과정에서 각 후보 k-itemset의 k - 2개 부분집합이 빈번한지 확인해야 합니다. 해시 트리에서 후보를 조회하는 비용은 O(k)이므로 후보 가지 치기 단계에는 O($\mathrm{\displaystyle\sum\limits_{k=2}^w\:k|C_{k} |}$) 시간.