빈번한 Itemset 마이닝 성능

Question

샘플 데이터를위한 잘 작동하는 아이템 세트를 마이닝하기위한 apriori 알고리즘을 구현했지만 소매 데이터 세트를 실행하려고 시도했을 때 http://fimi.ua.ac.be/data/retail.dat은 88k 트랜잭션 및 1600 개의 고유 항목이있는 약 3MB 데이터입니다. 약 29 시간이 걸립니다. 성능 저하의 원인을 찾아서 후보 항목 집합을 생성하는 알고리즘에 많은 시간이 걸리는 것으로 나타났습니다. 아무도 성능을 향상시키는 방법에 대해 나를 도울 수 있습니까 아니면 이러한 정상적인 알고리즘 동작이 있습니다.

Answer 1

사용하고있는 알고리즘, 그리고 임계 값은 무엇입니까?

최소 지원을 충족하는 n 개의 항목 세트가있는 경우 Apriori (및 많은 다른 제품)는 n*(n-1)/2 2 개 항목 세트를 고려해야합니다. 이것은 물론 다소 비쌉니다. Apriori에서 2- 항목 세트는 종종 가장 크고 가장 비싼 단계입니다 (설정에 따라 3- 항목 집합이 더 나쁠 수도 있지만 일반적으로 그렇게 멀리 가지 않습니다 ...)

데이터 특성에 따라 다릅니다 , Eclat는 더 잘 수행 할 수 있습니다 - 또는 더 나빠질 수 있습니다. FP 성장은 매우 영리하지만 올바르게 구현하는 것은 매우 까다로운 일입니다.

무수히 많은 변형이 존재하며, 일부는 확률 론적이며 실질적으로 더 빠를 수도 있습니다.

그러나 본질적으로 구현 및 데이터 세트/매개 변수 설정은과 관련됩니다. 하나의 접근법은 동일한 데이터 집합에서 다른 접근법보다 낫습니다. 구현은 10 배의 성능 차이를 쉽게 가질 수 있습니다. 특히 APRIORI에서는 많은 사람들이 사용 된 잘라 내기 트릭을 완전히 이해하지 못하고 너무 많은 작업을 수행합니다.

예제 데이터 세트 (불행히도 숫자를 설명하는 사전이 없으면 전혀 도움이되지 않습니다)의 경우, APRIORI는 minSupport = 1000 인 저가형 Atom CPU에서 약 1 분 만에 완료됩니다.발견 된 4 itemsets이었다 :

32, 38, 39, 48: 1236 
32, 39, 41, 48: 1646 
36, 38, 39, 48: 1080 
38, 39, 41, 48: 1991 
38, 39, 48, 110: 1031 
38, 39, 48, 170: 1193 

하지만, 이전에 언급 한 바와 같이, 매개 변수는 APRIORI와 많은을 중요. APRIORI는 트랜잭션 수 (주 메모리보다 많을 수도 있음)에서 잘 조정되지만, 후보 수가 많아서이 많으므로 minSupport를 충분히 높게 설정해야합니다. minSupport = 1000

:와

1-frequentItemsets (56) 
2-frequentItemsets (49) 
3-frequentItemsets (24) 
4-frequentItemsets (6) 
APRIORI runtime: 55401 ms 

minSupport은 = 500 :

1-frequentItemsets (185) 
2-frequentItemsets (191) 
3-frequentItemsets (79) 
4-frequentItemsets (13) 
5-frequentItemsets (0) 
APRIORI runtime: 136594 ms 

당신이 볼 수있는 바와 같이, 런타임은 배 이상. 그 이유는 1 항목 집합이 증가하여 2 항목 집합 후보를 더 많이 생성하기 때문입니다. 3- 및 4- 항목 집합에서 차이가 더 이상 크지 않습니다. 하지만 전반적으로 로우 엔드 CPU에서의 2 분 런타임은 아직 나쁘지 않습니다. 최소 지원 감소

250 :

1-frequentItemsets (587) 
2-frequentItemsets (640) 
3-frequentItemsets (273) 
4-frequentItemsets (54) 
5-frequentItemsets (4) 
APRIORI runtime: 954984 ms 

지금 런타임은 폭발하기 시작합니다. 당신이 볼 수 있듯이, 38, 39, 41, 48 4 항목 집합이 데이터 세트에 중요한 역할을하고있다

32, 38, 39, 41, 48: 448 
36, 38, 39, 41, 48: 334 
38, 39, 41, 48, 110: 346 
38, 39, 41, 48, 170: 413 

(하지만 우리는 이미 첫 번째 실행이 발견) : 거의 16분는 5 itemsets를 찾을 수 있습니다. 우리는 또한 38, 39, 41, 48 -> 32에 대한 확신을 줄 수 있습니다. 이는 5 가지 항목을 포함하는 가장 확실한 규칙이 될 것입니다. 첫 번째 4 건을 포함하는 거래 중 약 22.5% 또한 32과 관련이 있습니다. 그러나 AFAICT가이 데이터 세트에 대한 숫자의 의미를 알 수 없기 때문에이 규칙이 실제 실제로 흥미로운 지 또는 장난감 운동인지는 알 수 없습니다.

은 성장 또한 minSupport = 100 런타임가는 :

1-frequentItemsets (1857) 
2-frequentItemsets (2785) 
3-frequentItemsets (1475) 
4-frequentItemsets (306) 
5-frequentItemsets (28) 
6-frequentItemsets (0) 
APRIORI runtime: 8256507 ms 

즉 두 시간 이상. 이 시간의 대부분은 2 가지 항목 세트에 소비됩니다. 170 만 명의 후보자가 있으며 그 중 2785 명이 자주 있습니다. 3 품목 세트의 경우 약 1000 명의 후보자가있을 것이라고 대략 추정 할 수 있지만 더 이상 수백만 명의 후보자는 없을 것으로 예상됩니다. 후보자 수에 따라 두 codepath 사이를 전환하여 구현을 더욱 개선하는 계획이 있습니다. ('' '업데이트 :' ''는 간단한 수정으로 실행 시간을 20 배 줄였습니다. '예' '구현 문제' '는 쉽게 100-1000 배 이상을 만들 수 있습니다. 예를 들어, APRIORI 프룬이 완전히 구현되지 않은 경우)

Eclat 알고리즘을 읽고 구현할 시간을 찾은 경우이를 결과로 업데이트 할 수 있습니다. 나는 여기가 훨씬 더 빠를 것이며 FP 성장도 그렇게 될 것이라고 믿는다.

Answer 2

그 (0,1)의 모든 theta 적어도 theta의 주파수를 가진 항목을 찾기 위해 데이터 (이 기본적으로 스트림 처리를 위해 설계되었습니다)에서 하나의 통과에 후보자를 찾는하는 pretty efficient algorithm proposed by Karp Papadimtrioue Shanke 있습니다.

높은 수준의 알고리즘 : PF에

• 수집 요소, 계산 자신의 모습
1/θ 고유 요소가 발생 될 때마다 한 모든 카운터를 감소시키고, 그 카운터 사람들은 제로이다 PF에서 제거

알고리즘 수율 (최대) 1/세타 후보들이 처리 생존하고 더 위음성이없는 PF에서 원소 ( 하지 않는 출력

어떤 후보도 놓치지 마십시오.) - 그러나 일부 오탐이 있습니다 (일부 후보자는 빈번하지 않습니다).

단순화를 위해 1/쎄타는 정수라고 가정합니다.

의사 코드 :

PF = {} //empty dictionary 
for each element e: 
    if PF.contains(e): 
     PF[e] = PF[e] + 1 
    else: 
     PF[e] = 1 
     if PF.size() == 1/Theta: 
      for each element k in PF: 
       PF[k] = PF[k] - 1 
       if PF[k] == 0: 
        remove k from PF 
When done, all elements in PF are your candidates. 

Answer 3

구현에 따라 다릅니다. Apriori를 구현할 때 만들 수있는 많은 최적화가 있습니다.

처음으로 Agrawal & Srikant로 원래 Apriori 논문을 읽으면 후보자 지원을 효율적으로 계산하기 위해 특별한 해시 트리를 사용하는 것이 좋습니다. 이 구현이 어떻게 작동하는지 알고 싶다면 SPMF 오픈 소스 데이터 마이닝 라이브러리에 HashTree로 구현 된 Apriori 버전이 있습니다. 그것은 AprioriHT라는 이름입니다.

데이터베이스를 여러 번 스캔하지 않도록하는 또 다른 최적화 이름은 AprioriTID입니다.각 항목 집합은 트랜잭션을 포함하는 트랜잭션 ID 집합으로 주석 처리됩니다 (tid 집합). 그런 다음 데이터베이스를 검색하지 않고 AUB의 지원을 직접 계산하기 위해 두 개의 항목 집합 A와 B를 결합하여 후보가 생성되면 A와 B의 tid 집합의 교차를 수행 할 수 있습니다. 추가 최적화를 위해 다음과 같이 tid 집합을 구현할 수 있습니다. 비트 벡터. 이 APriori 버전은 AprioriTID라고합니다.

파스칼 알고리즘에서 또 다른 최적화가 제안되었습니다. 형식적 개념 분석의 생성 항목 집합 개념을 사용하여 데이터베이스를 검색하지 않고 일부 항목 집합의 지원 임계 값을 추론하는 것은 생성자 개념을 사용하는 것입니다.

또 다른 최적화는 Apriori의 각 레벨에 대한 아이템 세트를 사전 편집 순서로 정렬하고 각 항목 세트의 모든 항목을 사전 편집 순서로 정렬하는 것입니다. 그런 다음 후보를 생성 할 때이 순서를 사용하여 모든 항목 집합을 서로 비교하지 않아도 큰 후보를 생성 할 수 있습니다.

다른 최적화도 있습니다. FIMI 웹 사이트에는 다양한 최적화가 적용된 다양한 구현이 있습니다.

최적화 된 버전을 보려면 SPMF data mining library in Java에서 구현 한 내용을 살펴보십시오. 또한 동일한 웹 사이트에서 FPGrowth와 같은 더 빠른 알고리즘을 구현할 수 있습니다.