10_7 part 1

3,4,5 이렇게 해도 어쨌든 모든 조합은 T2의 부분집합에 해당이 되기 때문에 결국 모두 Frequent 하겠죠. 그래서 A1에서 A100으로 만들 수 있는 모든 조합은 다 Frequent Set에 해당이 됩니다. 이렇게 해서 결국에 몇 개인지를 계산을 하면 아래처럼 2의 100승계가 총 나올 수가 있겠죠.

100개의 아이템이 있으니까 2의 100승계의 아이템 셋이 나올 수 있고요. 그런데 모든 아이템이 다 포함이 되지 않은 공집합을 빼줘야 되니까 하나는 빼주면 결국에는 2의 100승 -1개가 나올 수 있습니다. 그래서 여기서 보면은 결국에는 이렇게 100개의 어트리뷰트만 가져도 마리아와 같이 굉장히 많은 수의 frequent item set이 발생될 수 있습니다.

그래서 이러한 굉장히 많은 item set을 결국에는 계산을 하게 되면은 두 가지의 문제점이 발생할 수 있는데요. 첫 번째는 이 모든 프리퀀터 아이템셋을 저장을 하려면 저장 공간이 많이 필요하게 됩니다. 그리고 두 번째, 이것들을 모두 계산을 하려면 연산량이 굉장히 많이 되게 되겠죠. 그래서 시간이 굉장히 오래 걸리게 됩니다. 그래서 첫번째 문제 공간이 너무 많이 필요하다는 문제를 해결하는 방법이 압축 기술이고요.

바로 뒤에서 공부를 할 예정입니다. 그리고 두번째 이 프리퀀트 아이템셋의 연산량, 계산량 문제를 해결하는 방법이 이제 마이닝 기술입니다. 패턴 마이닝 알고리즘입니다. 그래서 이 두 가지를 이어서 각각 한번 공부를 해보도록 하겠습니다. 먼저 두 가지 압축 기술에 대해서 압축된 형태에 대해서 공부를 해보도록 하겠습니다.

첫 번째는 Closed Pattern 입니다. Closed Pattern은 어떻게 정의가 되냐면 어떤 Closed Pattern이 Frequent하다 라는 것은 어떠한 걸 의미로 하냐면 X라는 아이템셋이 있을 때요 그것과 같은 서포트를 가지는 것 중에 X를 포함하면서 크기가 더 큰 슈퍼패턴인

Y가 없는 경우를 의미합니다. 즉, 다시 말씀드리면은 어떤 아이템셋 X가 frequent하다 라는 것은 어떤 것을 의미하냐면 같은 서포트를 가지는 여러가지 패턴이 있겠죠. 그 패턴중에 x를 포함하면서 더 큰 슈퍼패턴이 없을때만

이 closed 패턴에서 그 x가 frequent하다 라고 말을 할 수 있습니다. 그래서 아래에 아까 봤던 예시를 통해서 조금 더 쉽게 설명을 드리도록 하겠습니다. 그래서 이 min sub을 아까처럼 1로 설정을 했을 때 그러면은 몇 개의 closed 패턴이 있는지 한번 찾아보도록 하겠습니다.

아까 구했던 것처럼 여기서 일반적인 패턴을 계산을 하게 되면 굉장히 많은, 2/100승개의 패턴이 나올 수 있죠. 그런데 여기서 예를 들어서 작은 패턴을 한번 보면 예를 들어서 A1, A2 같은 이런 패턴을 한번 보도록 하겠습니다.

그런데 이런 패턴 같은 경우에는 서포트를 계산을 하면 2가 되죠. 그런데 이것과 같은 서포트를 가지면서 얘를 포함하면서 크기가 더 큰 그런 또 다른 아이템 셋이 있습니다. 예를 들어서 A1, A2, A3 이것 또 서포트가 2죠. 그러니까 여기서는 이 슈퍼 패턴이 존재한다 라고 말할 수 있습니다.

이 A1, A2, A3은 위에 있는 A1, A2의 슈퍼패턴입니다. 그런데 이 밑에 있는 이 패턴도 역시 또한 슈퍼패턴이 존재합니다. 어떤 슈퍼패턴이 존재하냐? 예를 들어서 A1, A2, A3, A4. 이렇게 이런 슈퍼패턴이 역시 존재하겠죠. 같은 서포트를 가지는 슈퍼패턴이 존재합니다.

그럼 이거를 어디까지 확장할 수 있냐. 서포트가 2면서 가장 큰 그런 패턴까지 확장을 할 수 있겠죠. 그게 뭐에 해당되냐면 여기서 나오는 이 P1의 A1부터 A50까지 포함된 서포트 2를 가지는 이 패턴은 이것보다 더 크면서 2라는 서포트를 가지는 패턴은 없죠. 그래서 왼쪽에 있는 이 패턴은 클로즈드 패턴, 프리퀀트 클로즈드 패턴이라고 우리가

마찬가지로 A51부터 아이템이 포함되면은 그거는 이제 서포트가 항상 1이겠죠. 예를 들어서 A51 같은 경우에는 서포트가 1입니다. 같은 서포트 1을 가지는 슈퍼패턴으로 계속해서 이렇게 확장을 하게 되면은 뭐 하나만 남냐? 크기가 가장 큰 A1부터 A100까지 포함된 이런 패턴 하나만 남습니다.

그래서 결국에는 같은 예시에서 클로즈드 패턴을 구한다라고 하면은 총 2개의 closed pattern만 남게 됩니다. 이 closed pattern의 가장 큰 장점은 역시 공간을 압축시킬 수 있다는 거죠. 이의 백승 -1개의 패턴을 다 저장하지 않고 이렇게 2개의 패턴으로만 대표로 해서 우리가 전체 패턴을

표현할 수 있습니다. 그런데 압축을 했을 때 중요한 점은 압축을 한 다음에 다시 이 압축을 해제할 수 있어야겠죠. 압축된 걸로 원본 패턴을 복원할 수 없다면 압축하는 게 의미가 없습니다. 여기서 중요한 특징은 이 Closed-Pack 패턴은 복원 과정에서 정보가 소실되지 않는 무손실 압축 로스레스 컴프레션에 해당이 됩니다.

그래서 이 클로즈드 패턴과 그리고 각각의 서포트 정보를 각 패턴의 서포트 정보까지 이렇게 기록이 되어 있죠. 이 서포트 정보를 함께 활용을 하면은 결국 모든 원본 패턴에 서포트 정보까지 우리가 다 복원을 해낼 수가 있습니다. 즉, 원본 프리퀀트 아이템셋이 있겠죠. 그것에 서포트 정보까지 손실 없이 이렇게 복원해낼 수 있는 방법에 해당이 되고요.

예를 들어서 아래에 있는 것 같이 A2에서 A40까지를 포함한 이 패턴 같은 경우에는 P1, P2에 모두 속하죠. 그렇기 때문에 P1이 이미 서포트가 2니까 이 서브셋도 서포트가 2다라는 것을 우리는 알 수 있습니다. 예를 들어서 두번째 A5, A51로 이루어진 이런 패턴 같은 경우에는 이 P2에만 포함이 되니까 이것은 1이구나, 서포트가 1이구나 라고 원본 패턴의 서포트까지 복원을 할 수 있습니다.

두 번째 방법은 맥스패턴이라는 방법인데요. 이 맥스패턴도 유사한데 아래와 같이 어떤 x가 맥스패턴이고 프리퀀트하다는 것은 이 x의 슈퍼패턴, 프리퀀트한 슈퍼패턴이 없는 것을 의미한다 라는 것을 나타내고 있습니다. 여기서 차이점이 뭐냐면 조건 하나가 빠졌습니다. 앞에서는

x와 소프트가 같은 슈퍼 패턴이 없어야 된다 라고 했는데 여기서는 x와 서포트가 같은 이라는게 빠졌죠. 그래서 여기서는 서포트가 같은지 틀린지를 여기서는 고려하지 않구요. 그냥 프리퀀트한 패턴이면 다 서포트와 상관없이 슈퍼패턴이 될 수 있습니다. 그래서 한번 예를 들어서 closed 패턴과 어떤 차이점이 있는지 알아보도록 하겠습니다.

아까와 같은 예시를 봤을 때 여기서 동일하게 win sub 1로 설정을 하고요. max 패턴이 어떻게 있는지 한번 확인해 보도록 하겠습니다. 아까는 두 개의 패턴이 나왔죠. 1에서 A1에서 A50까지를 포함하는 패턴 그리고 A1에서 A100까지를 포함하는 패턴 두 개가 나왔는데 사실 여기는 A1에서 A50을 포함하는 이 패턴은

맥스 패턴이 될 수 없습니다. 왜냐하면 여기서는 서포트와 상관없이 무조건 더 큰 프리퀀트한 슈퍼 패턴이 있으면 안 된다고 했죠. 그래서 A1부터 A50이 포함된 이 패턴은 더 큰 패턴인 A1부터 A100까지 포함된 이러한 슈퍼 패턴을 가지고 있기 때문에 점점 계속 확장을 해서 결국에는 A1부터 A100까지를 포함한 이러한 하나의 맥스 패턴만 여기서는

가질 수 있게 됩니다. 근데 여기서 이제 앞에 차이점은 앞에 우리가 Closed Pattern을 구할 때는 각 패턴의 이 서포트 정보를 이렇게 보존을 해줬는데 여기서는 서포트와 상관없이 그냥 가장 큰 패턴 하나만 계산을 해줬기 때문에 이 맥스 패턴은 손실 압축에 해당이 됩니다. 즉 어떠한 원본 패턴을 복원을 할 때

그 원본 패턴이 서포트가 몇인지를 정확히 알 수가 없습니다. 그래서 예를 들어서 A1부터 A40까지가 이 맥스 패턴에 포함이 되니까 이 패턴이 frequent하다 까지는 우리가 알 수 있습니다. 이 안에서 포함되어 있는 서브셋이 frequent하다 라는 것을 우리가 알 수 있는데 정확히 그러면 서포트가 몇인지는 우리가 여기서는 정보가 없기 때문에 계산을 해 줄 수는 없습니다.

그래서 맥스 패턴은 우리가 더 정보를 많이 압축을 시킬 수 있다는 장점이 있지만 이렇게 중요한 서포트 정보를 소신을 시키기 때문에 일반적으로는 이 맥스 패턴보다는 앞에 나온 클로즈드 패턴을 조금 더 데이터 분석에서는 많이 활용을 해주고 있습니다. - There you go.

여기까지 이제 기본적인 여러가지 용어들 그리고 개념들에 대해서 공부를 해봤고요. 그 다음에는 이제 효율적으로 이러한 프리퀀트 패턴을 계산을 할 수 있는 이 패턴 마이닝 기술에 대해서 공부를 해보도록 하겠습니다. 그래서 세 가지 방법을 공부를 해볼 거고요. A'Ori라는 그러한 알고리즘 그리고 그의 기반이 되는 원리부터 먼저 공부를 해보도록 하겠습니다.

먼저 다운로드 클로저라는 혹은 A'I'이라는 특성에 대해서 먼저 공부를 해보도록 하겠습니다. 아까와 같은 예를 동일하게 계속 한번 보도록 하겠습니다. 여기서 이 두 개의 데이터셋이 있고요. 여기서 이 두 개의 트랜젝션이 있고 윈서비 1이라고 설정을 됐을 때 이 A1부터 A50이 포함된 이 아이템셋은 우리가 프리퀸트하자라는 것을 이제 앞에서

우리가 계산을 이미 했습니다. 그랬을 때 A1부터 A50이 포함된 이러한 큰 아이템 셋이 프리퀀트하면 이걸로부터 만들 수 있는 모든 서브셋들 있죠. 예를 들어서 아래와 같은 A1, A2, A50, A12와 같은 이러한 것으로 만들 수 있는 모든 서브셋도 항상 프리퀸트 합니다.

그런데 이건 좀 당연하게 생각할 수 있는게 A1부터 그러면 A50까지가 어떤 트랜잭션에 포함이 되어 있다는 말이죠. 그러면 그것보다 더 작은 서브셋도 당연히 그 최소한 그 트랜잭션에는 포함이 되어 있어야 됩니다. 그렇기 때문에 어떤 아이템셋이 프리퀸트하다면 그 서브셋도 마찬가지로 항상 프리퀸트하다는 그런 특성을 가지게 되고요.

그것을 downward closure 또는 apriorite 성질, 특성이라고 우리가 부르고 있습니다. 그래서 예를 들면은 기형, 다이어펌, 너츠가 frequent하다 라고 하면 당연히 이 서브셋인 비어랑 다이어포도 프리퀸트 하겠죠. 이 앞을 포함을 하는 트랜잭션은 이 뒤에 두 개도 당연히 포함을 하고 있기 때문입니다.

그래서 어떻게 보면은 이러한 당연한 성질을 우리가 왜 여기서 공부를 하냐 라고 하면은 이 성질을 좀 반대로 뒤집으면은 우리가 굉장히 효과적으로 어떤 프리퀸트 아이템셋을 계산을 할 수 있기 때문입니다. 그럼 역으로 어떤 S라는 아이템 셋이 있을 때 그 아이템 셋의 서브 셋 중에 단 하나라도 인프리퀸트 하다면 그 아이템 셋은 인프리퀸트 하다라고

우리가 얘기를 해 줄 수 있습니다. 예를 들어서 비어랑 다이어퍼가 인프리퀸트하다, 프리퀸트하지 않다라고 하면 이게 프리퀸트하지 않으니까 그것이 포함된 비어, 다이어퍼, 너츠 같은 경우에도 당연히 프리퀸트 할 수 없겠죠. 계산을 할 수 있습니다

그래서 어떻게 할 거냐면 작은 아이템셋부터 우리가 프리퀸트한지 계산을 합니다. 근데 만약에 어떤 아이템셋이 인프리퀸트하다라고 하면은 그 아이템셋을 포함한 더 큰 패턴을 우리가 아예 계산을 해보지 않고도 그게 인프리퀸트하다는 걸 알 수 있겠죠. 그래서 이렇게 미리 계산하지 않고도 우리가 많은 패턴을 쳐낼 수 있습니다.

이러한 것을 프로닝이라고 우리는 표현을 합니다. 그래서 이러한 원리에 기반해서 우리는 먼저 A'L'I' 알고리즘에 대해서 공부를 해볼 거고요. 그리고 이것과는 크게 상관없는 다른 두 가지 효율적인 마이닝 방법을 공부를 해보도록 하겠습니다.

또 다른 방법을 두 번째로 공부해보고, 마지막으로 FPGrowth라는 세 번째 방법까지 공부를 해보도록 하겠습니다. 그래서 이 부분부터는 시간이 다 돼서 다음 시간에 공부를 할 예정이고요.

패턴 마이닝 수업 시작하도록 하겠습니다 이번 챕터에서는 패턴 마이닝에 대해서 공부를 해보도록 하겠습니다 기본적인 개념 패턴이 뭔지 또 패턴 마이닝이 뭔지 이게 왜 필요한지 등에 대해서 여러가지 용어와 개념을 알아보고요

그 다음에는 패턴 마이닝을 효율적으로 수행하기 위한 여러가지 알고리즘들이 있는데 그 알고리즘에 대해서 공부를 해보고 마지막에 우리가 발견한 여러가지 패턴들이 있으면 그 패턴이 다 유용한 것은 아닙니다. 그래서 그 패턴이 유용한지 아닌지를 판단할 수 있는 그러한 여러가지 측정량입니다. 매트릭에 대해서도 마지막으로 공부해보도록 하겠습니다. 먼저 패턴이 무엇인지를 먼저 정의를 하도록 하겠습니다.

데이터 마이닝에서 의미하는 패턴은 함께 같이 등장하는 어떤 아이템들의 집합 또는 어떤 서브 시퀀스 순서를 가지고 함께 등장하는 그러한 시퀀스 혹은 스트럭처 등을 의미합니다. 그래서 결국에 패턴의 조건은 함께

반복적으로 자주 등장하거나 아니면은 어떤 아이템 사이에 코릴레이션이 있어야 그것을 어떤 패턴이라고 부르고 있습니다. 그래서 예를 들어서 왼쪽과 같이 요리를 하는데 이 세 가지 야채가 자주 같이 사용이 된다 라고 하면은 이 세 가지는 자주 같이 등장을 하기 때문에 이런 것을 Frequent Item Set 이라고 부를 수 있습니다.

이러한 것들을 계속해서 계속 나올 거고요. 이렇게 같이 자주 등장하는 아이템들의 직합을 Frequent 빈번한 Item Set 이라고 부르고 있고요. 그리고 가운데처럼 어떤 순서를 가지고 일정한 패턴이 반복적으로 등장할 수도 있습니다. 그래서 가운데 예시와 같이 어떤 감기에 걸리게 되면은 증상이 어떤 순서를 가지고 반복적으로 나타나게 되죠.

그래서 이러한 것을 frequent sequence 라고 하고요. 그리고 마지막처럼 어떤 데이터 내의 구조가 반복적으로 나타나게 되죠. 등장을 할 수도 있습니다. 예를 들어서 오른쪽과 같은 프로그램에서는 메뉴가 있고요. 그 안에 버튼이 있고 그 안에 서브 메뉴가 있다. 이러한 구조들이 반복적으로 나타나게 되죠. 그럼 이러한 구조들을 역시 하나의 패턴이다 라고 우리는 부를 수 있고요.

이런 경우에는 frequent structure라고 일반적으로 말을 하고 있습니다. 그래서 이런 것들을 모두 합쳐서 다 패턴이라고 생각을 할 수 있고요. 이러한 패턴은 어떤 데이터셋 내부에 있는 어떤 본질적이고 중요한 그러한 특성 정보를 가지고 있는 경우가 많기 때문에 우리는 이러한 패턴을 분석을 하게 됩니다. 다음으로 패턴 디스커버리라는 용어가 나오는데요.

패턴 디스커버리 또는 패턴 마이닝이라고도 하는데 이건 말 그대로 어떤 거대한 데이터들이 이렇게 모여 있을 때 거기서 우리가 유의미한 패턴들을 발견해 나가는 그런 과정을 의미합니다. 그래서 예를 들어서 아래와 같이 어떤 쇼핑 데이터가 있다고 했을 때 이렇게 여러 개의 장바구니에 데이터가 있을 수 있습니다. 이 장바구니는 각각의 고객이 어떤 물건들을 함께 구매했는지를 나타내 주고 있습니다.

장바구니 분석을 하게 되면은 예를 들어서 밀크와 브레드가 반복적으로 여러 고객의 구매목록에서 발견되는 것을 우리가 파악을 할 수 있습니다. 그럼 여기서 우리는 예를 들어서 이런 첫번째 질문을 해결할 수 있겠죠. 예를 들어서 어떤 물건들이 함께 자주 구매되는지 이러한 패턴 분석을 통해서 우리 이러한 정보들을 얻어낼 수 있고요.

혹은 어떤 순서가 있는 이러한 정보도 우리가 분석을 해낼 수 있습니다. 아이패드를 산 다음에 그 다음에는 어떤 물건을 손님들이 자주 구매를 했는지와 같은 이런 순서가 있는 정보들도 우리가 알아낼 수 있습니다. 그래서 패턴 분석을 통해서 결국에는 어떤 아이템들이 자주 함께 등장하는지 혹은 어떤 순서를 가지고 등장하는지와 같은 이러한 정보들을 얻어내는 것을 우리는 패턴 디스커버리라고 부르고 있습니다.

다음으로 이 패턴 디스커버리가 그러면은 왜 필요하고 왜 중요한지 어떤 용도로 쓰일 수 있는지 이제 간단히 알아보도록 하겠습니다. 패턴 디스커버리는 우리가 이후에 계속해서 공부할 여러가지 데이터 마이닝 테스트의 기본이 되는 역할을 하고 있습니다. 그래서 패턴 디스커리를 굉장히 많은 테스트에 우리가 활용해서 사용할 수 있는데요.

이 패턴을 분석을 해서 우리는 어소시에이션, 연관관계 즉 어떠한 패턴들이 어떠한 것들이 자주 함께 발생하는지를 파악을 할 수 있고요 또한 코릴레이션, 상관관계도 우리가 파악을 할 수 있습니다 그리고 더 나아가서 캐주얼리티 인과관계, 어떤 사건과 사건의 인과관계, 어떤 데이터들의 인과관계가 어떻게 되는지 이러한 것들을 분석할 때 기본적으로 이러한 우리가 찾아낸 패턴을 활용을 할 수 있습니다.

그리고 이 패턴은 아까 말씀드렸던 것처럼 어떠한 항목이 함께 자주 발생하는지 뿐만 아니라 어떠한 순서적인 순서를 가지고 있는 패턴 그리고 구조를 가지고 있는, 예를 들어 그래프 같은 패턴 등 다양한 형식의 패턴을 우리가 찾아내는 데 활용할 수 있고요. 그리고 클래셰케이션이나 클러스터링 같은 다른 테스크에도 우리가 발견한 이러한 패턴을 활용해서

수행을 할 수 있습니다. 예를 들어서 어떤 하나의 클래스에서만 두드러지게 나타나는 그런 패턴을 우리가 찾게 되면은 그 패턴 분석, 우리가 찾아낸 그 패턴을 기준으로 분류 작업을 수행할 수 있겠죠. A 클래스에서 나타나는 패턴, B 클래스에서 나타나는 패턴을 이용해서 물류 작업까지 수행을 해줄 수 있고요. 그리고 마찬가지로 패턴, 어떤 특성에 대한 패턴을 기준으로

그룹화를 시킬 수 있습니다. 이러한 패턴을 갖는 A 패턴을 갖는 그룹, B 패턴을 갖는 그룹, C 패턴을 갖는 그룹 이렇게 그룹화를 시켜서 클러스터링을 수행하는데도 이런 패턴을 활용할 수 있습니다. 그리고 또한 이러한 패턴 디스커버리는 다양한 어플리케이션에 활용이 되고 있습니다. 그래서 아까 설명드렸던 장바구니 분석

활용할 수 있구요. 이것을 이용해서 여러가지 예를 들어서 크로스 마케팅이라고 하는 것은 어떠한 상품들을 함께 우리가 마케팅을 해야지 효과적인지를 결정하는 그런 테스트인데요. 그래서 장바구니 분석을 통해서 우유와 빵이 자주 함께 나온다 그러면 그 두 개를 같이 마케팅을 하는게 효과되겠죠. 마케팅에도 활용을 할 수 있고요. 그리고 카탈로그를 디자인할 때

어떤 상품을 위에 배치하는게 유리하고 어떤 상품끼리 같이 배치하는게 유리한지 이러한 것들에 사용할 수도 있고요. 아니면 뭐 세일 캠페인, 할인 행사를 했는데 그때 어떤 품목이 많이 팔렸고 매출량이 얼마나 되는지 이런 것들을 분석을 하는데도 사용할 수 있고요. 그 밖에도 웹 로그를 분석을 하거나 아니면 DNA같이 DNA에 어떤 패턴이 많이 발생이 된다라는

그런 어떤 생물학적 시퀀스 분석에도 당연히 사용을 할 수 있습니다. 그리고 마지막으로 패턴 디스커버리는 다양한 형태의 데이터에서 수행이 가능합니다. 그래서 일반적인 테이블 형태의 타블러 데이터 뿐만 아니라 시공간적 데이터, 여러가지 모이티미디어 데이터, 타입 시리즈 실시간 데이터 등 여러가지 데이터의 패턴 디스커버리 기술을 활용할 수 있습니다.

다음으로 이러한 패턴 분석에 자주 활용되는 데이터베이스 형태를 알아보도록 하겠습니다. 그래서 특히 이 데이터셋은 어떤 항목들이 함께 같이 즉 Frequent Item Set을 찾는데 많이 활용되는 데이터셋입니다.

그래서 Transactional Database 줄여서 TDB라고 많이 불리는 이러한 형태의 데이터베이스인데요. 아래와 같이 구성이 되어 있습니다. 그래서 이러한 데이터베이스는 각각의 트랜잭션 거래가 하나의 행으로 구성되어 있는 걸 확인할 수 있고요. 하나의 거래, 각 거래마다 이 거래 아이디, TID라는 것이 고유하게 구성되어 있습니다.

그래서 이제 첫 번째 행은 첫 번째 발생된 거래, 두 번째 행은 두 번째 발생된 거래, 이러한 것들을 나타내고 있습니다. 그리고 각 거래는 그 한번에 거래가 이루어졌을 때 어떤 품목들이 함께 결제가 되었는지 구매가 되었는지 그것들이 함께 표현이 됩니다. 그래서 예를 들어서 첫 번째 거래에서는 Beard, Nuts, DIA, 라는

이 3개의 품목이 거래가 되었다는 것을 우리가 확인할 수 있습니다. 여기에 추가적으로 이런 데이터를 사용할 때 각 품목마다 개수까지 포함되는 경우도 많이 있습니다. 즉, B-O는 3개, N-U는 2개 이런 식으로 개수까지 이렇게 표기가 되는 경우도 많이 있는데 이번 수업에서는 간단히 예시만 들기 위해서 그러한 개수를 일단은 생략을 하고요.

각 거래에 어떤 상품들이 거래가 되었는지만 이렇게 표기된 그러한 TDB 데이터셋을 사용을 하도록 하겠습니다. 다음으로는 기본적인 여러가지 용어들에 대해서 알아보도록 하겠습니다.

먼저 아이템셋이라는 용어가 계속해서 등장을 할텐데요. 아이템셋은 말 그대로 하나 이상의 아이템의 집합이라고 생각할 수 있습니다. 그래서 함께 거래된 이러한 하나 이상의 아이템 집합이 아이템셋이라고 할 수 있고요. 그리고 그 포함된 아이템의 개수에 따라서

k 아이템셋이라고 표현할 수 있습니다. 즉, 원 아이템셋은 한 개의 아이템만 포함한 그런 아이템 셋이고요. 이 아래와 같이 이 비어, 너츠, 다이어퍼가 포함된 이러한 아이템 셋은 아이템이 세 개가 있죠. 그러니까 이것은 3 아이템 셋에 해당이 됩니다. 그래서 이제 오른쪽에 있는 Tdbe가 주어졌을 때

이렇게 왼쪽과 같이 이 데이터베이스를 이용을 해서 아이템 셋을 우리가 만들 수 있습니다. 그리고 그 다음에는 이제 support라는 용어가 나오는데요. 이 support는 크게 두 가지로 구분이 됩니다. 그래서 두 가지 모두 많이 사용이 되고 있고요. 첫 번째는 absolute support 이고요. 두 번째는 relative support 이렇게 두 개의 용어가 있습니다. 먼저 왼쪽 absolute support 부터

설명을 드리자면 이것은 특정한 아이템 셋이 등장한 거래가 총 몇개 있는지를 나타내게 됩니다. 그래서 카운트랑 동일한 역할을 하고요. 그래서 이 오른쪽에 있는 데이터셋에서 특정한 아이템 셋이 몇번 등장했는지 그 아이템 3을 포함을 하는 정확히는 트랜잭션이 몇개가 있는지를 나타내게 됩니다.

그래서 기호로는 sup sub x 라고 이렇게 표현을 하고요. 그래서 아래와 같이 예를들어서 이렇게 비어에 먼저 서포트를 계산을 하면은 이 5개의 거래 중에서 몇 개의 비어가 등장하는지 한번 살펴보면은 첫 번째, 두 번째, 세 번째 이 세 개의 트랜잭션에서 비어가 등장하죠.

그러니까 이 값은 3입니다. 그 다음에 sub die upper를 계산을 하게 되면은 이 die upper 같은 경우에는 4개의 트랜잭션에서 등장하기 때문에 이 값은 4입니다. 그리고 이렇게 one item set 말고도 더 k item set에서 예를 들어서 아래 같은 two item set에서도 이런 서포트를 계산을 할 수 있는데요. 예를 들어서 한 개만 더 살펴보면은

비어와 다이어포가 함께 나오는 트랜잭션이 몇개인지를 물어보고 있습니다. 비어와 다이어포가 함께 나오는 트랜잭션 같은 경우에는 1번, 2번, 3번, 3개가 포함되어 있죠. 그렇기 때문에 이것의 서포트 같은 경우에는 3이 됩니다. 이런식으로 절대적인 개수를 세는 것을 absolute support라고 하고요. 그 다음에 오른쪽에 있는 negative support 같은 경우에는 비율로 포항거기를 나타내게 됩니다. 그래서 전체 transaction 중에서

X라는 특정한 아이템셋이 포함된 트랜직션이 몇 퍼센트인지로 나타내게 됩니다. 그래서 이 negative support는 소문자 S라는 기호로 이렇게 표현을 해주게 됩니다. 예를 들어서 비용한 하나 살펴보면은 이 비어 같은 경우에는 총 5개 중에 3개의 트랜젝션에서 등장하죠. 그러니까 5분의 3, 5개 중에 3개에서 등장한다. 그래서 60% 이런 식으로 나타내는 것을 의미합니다.

다음으로 이렇게 아이템셋을 정의하시니까 우리가 실제로 찾고 싶은 것은 결국에 프리퀀트 아이템셋, 함께 빈번하게 같이 계속해서 등장하는 아이템셋을 우리가 찾고 싶겠죠. 그래서 이렇게 자주 함께 등장하는 프리퀀트 아이템셋을 먼저 정의를 해보도록 하겠습니다. 그래서 어떤 아이템셋 혹은 패턴이 프리퀀트 하다라는 것은 그 아이템셋의 서포트가 우리가 정한

threshold 즉 이것을 minimum 서포트 줄여서 min sub 이라고 하는데요. 이 min sub 보다 큰 그러한 아이템셋을 리뷰합니다. 그래서 어떤 아이템셋의 서포트 값이 있겠죠. 그리고 우리가 정의한 스레시홀드 값이 있을 때 그 서포트가 스레시홀드보다 크면은 아 이거는 자주 함께 등장을 했구나 라고 우리가 판단을 해줄 수 있고요. 그러한 아이템셋만 우리가 프리퀀트 아이템셋이라고 부르고 있습니다.

그래서 아래 예시로 다시 한번 확인해 보도록 하겠습니다. 그래서 여기서는 이 minsub을 50%로 설정을 했습니다. 그래서 여기서는 relative support를 사용을 할 거고요. 이 50%의 threshold를 기준으로 우리가 frequent item set을 한번 살펴보도록 하겠습니다.

K 아이템셋이 있을 수 있는데 먼저 개수가 하나, 아이템이 하나인 원 아이템셋부터 확인을 해보도록 하겠습니다. 여기는 원 아이템셋이 여러가지가 있죠. 비어, 수, 다이어트, 커피, 에그, 밀크 이렇게 여러가지가 있을 수 있는데 이 중에서 서포트가 50% 넘는 것만 우리가 골라주게 됩니다. 그래서 아래와 같이 4개가 해당이 되는데요.

여기서 서포트가 50% 이상이라는 것은 총 5개 중에서 50% 이상 등장을 해야 되니까 최소 3개의 트랜잭션에 등장하는 그러한 아이템셋만 찾는다는 것을 의미합니다. 여기서 비어 같은 경우에는 5개 중에 1,2,3,3개의 트랜잭션에 등장을 했으니까 서포트가 60%죠. 그러니까 슬래시홀드를 넘기 때문에 프리퀀트 아이템셋에 해당이 되고요.

너츠 같은 경우는 3개 등장하니까 역시 해당이 됩니다. 다이아폼, 에그 같은 경우는 우리가 기준점으로 설정해 준 50% 민석보다 크기 때문에 모두 Frequent One Item Set이라고 부를 수 있습니다. 그 다음에는 우리가 Frequent 1아이템셋을 찾았으니까 Frequent 2아이템셋을 찾아야겠죠. 그래서 Frequent 2아이템셋은 이 두 개의 항목을 조합해서 굉장히 많은 항목을 만들 수 있는데 이 중에서 사실 기준이 넘는 것 즉

3개 이상의 트랜잭션에서 등장하는 것은 이 하나의 아이템셋밖에 없습니다. 비어랑 다이어퍼 같은 경우에는 첫번째, 두번째, 세번째 트랜잭션에 등장하니까 5개 중에 3개의 등장에서 60%가 되죠. 그러니까 50%인 Threshold를 넘어서 Frequent Two 아이템셋에 해당이 됩니다. 나머지는 어떻게 두 개를 조합을 해도 세 개 이상 등장하는 그러한 투 아이템 셋이 없습니다.

그래서 투 아이템 셋은 한 개고요. 그럼 프리퀀트 쓰리 아이템 셋이 있냐 이 세 개를 조합을 했을 때 이 세 개의 트랜잭션 이상 등장하는 애가 있냐 라고 하면 없죠. 그렇기 때문에 프리퀀트 쓰리 아이템 셋은 없습니다. 이러한 식으로 우리가 Frequent Item Set을 찾을 수 있습니다. 그럼 여기서 우리가 궁금한 점은

여기까지 우리가 찾았을 때 이 데이터셋에서 존재하는 모든 Frequent Item Set을 찾은 거냐 모든 Frequent K Item Set을 찾은 거냐 라는 질문을 할 수 있는데요. 예를 들어서 Frequent 4 item set도 있고요. Frequent 5 item set 등등등이 더 있을 수도 있겠죠. 그런데 여기서는 이 왼쪽에 찾은 Frequent item set이 전부입니다. 왜냐하면 예를 들어서 Frequent 4 item set이 만약에 있으려면

무조건 Frequent3아이템셋이 1개 이상 존재해야 합니다. 왜냐면 Frequent4아이템셋은 Frequent3아이템셋에 최소한 1개의 아이템을 더 추가해야지 Frequent4아이템셋이 만들어지겠죠. 그런데 여기서는 이미 3개의 아이템셋도 프리퀀트한 게 없는데 당연히 그것보다 한 개의 항목이 더 추가될 4 아이템셋은 프리퀀트할 수가 없습니다.

그래서 그 이상 5,6,7 아이템셋도 역시 프리퀀트할 수 없겠죠. 그렇기 때문에 이제 왼쪽은 완전한 complete settings를 우리가 여기서 얻어냈다 라고 우리가 말을 할 수 있습니다 그리고 이제 왼쪽에서는 사실 우리가 굉장히 간단한 이러한 데이터베이스를 사용을 해서

아이템셋을 계산을 했는데 이 항목이 굉장히 늘어나게 되면은 우리가 이렇게 검사를 해야 되는 서포트를 계산을 해야 되는 아이템셋의 개수가 굉장히 많이 늘어나겠죠 이 2아이템셋, 3아이템셋, 4아이템셋 이 조합이 굉장히 많이 늘어날 수 있습니다 그렇게 되면 연상량이 굉장히 많이 늘어나기 때문에 우리가 이렇게 아이템 세트를 효과적으로 계산할 수 있는 이러한 방법이 필요해지게 됩니다.

그래서 이러한 방법이 우리가 뒤에서 배울 패턴 마이닝 방법들이고요. 그래서 아이템 세트를 굉장히 많이 나올 수 있기 때문에 이것들을 효과적으로 검사하는 이러한 알고리즘이 패턴 마이딩 알고리지입니다 라고 생각을 해 줄 수 있습니다. 여기까지 저희가 함께 자주 등장하는 아이템들의 집합인 Frequent Item Set을 공부했는데요.

이것을 조금 더 확장을 해서 Frequent Item Set에서 우리는 Association Rule 이라는 것까지 계산을 진행할 수 있습니다. 그래서 Association Rule은 순서를 가진 그러한 함께 자주 등장하는 아이템들을 의뢰합니다. 그래서 기본적으로 Frequent item set과 유사하지만 이러한 방향성을 가진 그러한 관계를 의뢰합니다.

그래서 일반적인 frequent item set 보다 조금 더 유용하게 많이 활용이 될 수 있습니다. 그리고 이제 조금 더 많은 정보를 표현을 해주고 있고요. 그래서 예를 들어서 이 다이아퍼에서 비어로 이렇게 가르치고 있는 이러한 것을 association 룰이라고 우리가 표현을 해 줄 수 있는데요 이것은 다이어퍼가 트랜잭션에 포함이 되어 있을 때 비어도 얼마나 함께 많이 포함이 되어 있냐를 나타내 주게 됩니다

즉 어떤 사람이 이런 다이어퍼를 구매를 했을 때 비어도 얼마나 많이 함께 구매를 했는지를 의미를 하게 됩니다. 그래서 이 방향에 따라서 다른 것을 의미하겠죠. 만약에 이 방향이 바뀌어서 비어에서 다이어포로 간다 라고 하면은 어떤 사람이 비어를 구매를 했을 때 다이어포도 함께 구매할 확률이 얼마나 되는지.

그런 경우가 얼마나 되는지를 의미하기 때문에 방향에 따라 다른 정보를 나타내 주게 됩니다. 그래서 위에서 예시를 본 것과 같이 이런 association 룬 화살표를 활용을 해서 x 화살표 y 이런 형태로 우리가 표현을 해 줄 수 있습니다. 여기서 각각의 x, y는 아이템셋을 응용합니다.

그래서 x, y가 위에처럼 하나의 아이템일 수도 있고요. 아니면 각각의 여러개의 아이템이 포함되어 있는 k아이템셋으로 구성이 될 수도 있습니다. 그리고 위에 설명드렸던 것처럼 x 에서 y다 라고 표현을 하면은 x를 포함한 트랜잭션이 있겠죠. x를 포함한 트랜잭션이 y도 얼마나 많이 함께 포함을 하고 있는지를 나타내게 됩니다.

그리고 여기서 합집합이라는 기호도 함께 사용할 수 있는데요. 합집합 기호는 단순히 아이템셋을 의미합니다. 그래서 X라는 아이템셋이 있고요. Y라는 아이템셋이 있을 때 이 합집합을 하면은 이 X와 Y를 함께 포함하는 더 큰 아이템 셋을 의미합니다.

그래서 예를 들어서 아래와 같이 X가 다이어퍼, Y가 비어 라는 아이템 셋이 있을 때 이 둘을 합체합을 하면 아래와 같이 이 두 개의 항목을 모두 포함하는 아이템 셋을 의미한다 라고 우리가 생각을 해줄 수 있습니다. 그러면 이러한 내용을 바탕으로 실제 association 룰을 우리가 한번 어떻게 계산하고

어떻게 이 어소시에이션 룰을 우리가 실제로 평가할 수 있는지 그 매트릭에 대해서 한번 알아보도록 하겠습니다. 그래서 크게 이 어소시에이션 룰을 평가할 수 있는 즉, 얼마나 많이 연관관계가 있는지를 우리가 측정하고 평가할 수 있는 이러한 매트릭은 두 개를 사용을 할 수가 있는데요. 첫번째는 우리가 앞에서 배운 서포트를 이용할 수 있고요.

두번째는 Confidence라는 것을 활용을 할 수 있습니다. 서포트 같은 경우에는 앞에서 배운 내용과 동일합니다. 예를 들어서 다이아포 비어의 서포트를 구하면 이 두개가 함께 나올 확률이 오른쪽에서 보면은 5분의 3이다. 0.6이다. 라는 것을 확인할 수 있습니다. 그런데 이 서포트 같은 경우에는 단점이 뭐냐면

이 어소시에이션 룰이 가지고 있는 방향성은 전혀 여기서 고려를 하지 못한다는 그런 단점을 가지고 있습니다. 그래서 프리퀀트 아이템 셋을 평가할 때는 이게 유용하게 사용될 수 있지만 Association 룰의 방향성은 여기서 고려를 해 줄 수 없습니다. 단지 이 두 개가 얼만큼 함께 등장하냐만 이렇게 측정을 해 줄 수 있습니다. 그래서 사실 Association 룰을 평가하기 위해 사용하는

계산하기 위해 사용하는 그러한 매트릭은 Confidence가 많이 사용이 되고요. 이러한 Confidence는 아래와 같이 Association Rule의 정의를 그대로 활용한 조건부험료를 이용해서 측정을 진행하게 됩니다. 그래서 아래처럼 xnSupport 즉 x가 등장하는 Transaction에서 xySupport

x, y가 함께 등장하는 그런 서포트의 비율을 우리가 계산을 하게 됩니다. 여기서 하나 알아야 될 것은 위에서 그냥 이제 x, y의 서포트를 계산을 할 때는 relative 서포트를 이용을 했죠. 그래서 바로 이렇게 확률로 나타냈는데 이 confidence를 계산을 할 때는 absolute support를 이용을 하고 있습니다. 그래서 이거를 그냥 해석하자면 결국에는 x가 포함된 트랜젝션이

이 트랜젝션에서 y도 얼만큼 포함을 하고 있는지에 대한 비율을 나타낸다 라고 할 수 있습니다. 그래서 여기서 다이아4에서 B형으로 가는 이러한 어소시에이션 룰의 confidence를 계산해보도록 하겠습니다.

그럼 이 오른쪽에서 계산을 해보면 되겠죠. 다이어퍼가 등장하는 트랜젝션이 1번 2번 3번 5번 4개죠. 1번 5번 2번 3번 5번 그중에 비어가 등장하는 것은 1번 2번 3번 3개 등장합니다. 그래서 4개 중에 3개가 등장하니까 0.75다라고 아래와 같이 계산을 할 수 있습니다. 반대로 비어에서 다이어포로 가는 이런 어소시에이션 룰도 있을 수 있겠죠.

여기서 confidence를 계산을 해보면 비어가 등장하는 것 중에 다이어포가 몇 개 등장하느냐. 첫번째, 두번째, 세번째, 세개의 트랜잭션이죠. 이 중에 다이어트가 몇개 등장하냐면 첫번째, 두번째, 세번째 모두 등장합니다. 그래서 이 반대 방향은 confidence를 계산할 때 3개 중에 3개니까 1.0, 100%라는 것을 확인할 수 있습니다. 그래서 방향에 따라 다른 confidence가 나올 수 있습니다.

그래서 결국에는 이 서포트 같은 경우에는 x와 y가 얼마나 자주 함께 나오냐를 의미하고요. 그리고 confidence는 x가 등장한 것 중에 y가 얼만큼 많이 등장하냐를 의미하게 됩니다. Thank you. 그 다음으로는 우리가 마이닝의, 이러한 association 룰에 대한 개념을 공부했으니까

실제로 데이터베이스에서 이런 association 룰을 마이닝 하는 그런 방법에 대해서 알아보도록 하겠습니다. 그래서 이것을 유용한 association 룰을 데이터로부터 찾아내는 것을 association 룰 마이닝이라고 합니다. 그래서 이 마이닝에서는 일단은 두개의 threshold를 사용합니다. 우리가 공부한 support에 대한 threshold인 민서브를 사용하고요.

그리고 confidence에 대한 threshold인 민컴폰을 사용합니다. 이 두 개의 트레이셜들을 우리는 사용을 해 주도록 하겠습니다. 그리고 어떤 그러면은 association 룰을 계산을 하게 되냐 라고 하면은 x 에서 y 로 향하는 이러한 association 룰이 있다고 했을 때 이 룰 중에서 support가 relative support 멜로티브 서포트죠. 이게 민성보다 크고 그리고 컨피던스도 민컨포보다 큰

이러한 어소시에이션 룰을 우리는 찾으면 됩니다. 구체적으로 아래와 같은 두 단계로 기본적으로 진행이 됩니다. 처음부터 모든 어소시에이션 룰을 우리가 만들면 경우의 수도 굉장히 많이 나오고 만들기도 어렵기 때문에 그걸 바로 수행을 하는게 아니고요. 먼저 첫번째 단계에서는 frequent item set 부터 우리는 찾게 됩니다.

이렇게 min-sub 50%의 서포트를 가지는 그 이상의 서포트를 가지는 Frequent item set을 먼저 찾게 됩니다. 그래서 오른쪽에서 그걸 찾았을 때 아까 했죠. Frequent one item set은 4개가 나오고요. Frequent two item set 같은 경우에는 한 개 비어 다이어프로 이루어진 이러한 한 개의 투 아이템셋만 우리가 프리퀀트 하다라고 얘기를 할 수 있습니다

그러면 이 프리퀀트 아이템셋으로 우리가 구성할 수 있는 어소시에이션 룰들을 다음에 모두 계산을 하게 됩니다 그런데 여기 사실 프리퀀트 원 아이템셋은 여기서는 쓸모가 없습니다 왜냐하면 이 한 개만을 가지고 어떤 룰을 만들 수가 없죠. 그렇기 때문에 얘를 어소시에이션 룰을 계산하는데는 사용되지 않구요. 투 아이템 셋부터 우리가 사용할 수 있습니다. 그래서 여기서 비어랑 다이아퍼가 포함된 이 투 아이템 셋으로 만들 수 있는

이런 어서시에이션 룰은 두 개가 있겠죠. 비어에서 다이아퍼 혹은 다이아퍼에서 비어 이 두 가지가 있을 수 있습니다. 그래서 아래처럼 이 두가지 어소시에이션 룰에 대해서 우리가 이 두개의 어소시에이션 룰이 윈, 컴퍼를 만족하는지를 다음으로 최종적으로 확인을 하게 됩니다. 그래서 우리가 만든 첫번째 어소시에이션 룰의 컨피던스를 계산을 했는데 비어가 포함됐을 때 다이어포가 포함될 확률은 100%죠.

100%니까 이 50% 기준을 통과하고요. 두번째 같은 경우에는 다이어포가 포함된 것 중에 비어가 포함된 확률이 75%니까 역시 이 기준을 통과합니다. 그래서 결과적으로 우리가 이 데이터셋에서 얻을 수 있는 유용한 어소시에이션 룰은 두 개다 라고 결론을 낼 수 있습니다. 그래서 결론적으로 전체 과정을 정의하자면 첫번째로 먼저 바로 association 룰을 구하면 너무 겸울수가 많으니까

먼저 frequent item set을 구성합니다. 그 다음에 frequent item set에서 우리가 만들 수 있는 모든 association 룰을 만들게 되고요. 그 Association Rule에 대해서 최종적으로 Confidence를 이용해서 아 이게 많이 발생되는 Association Rule이구나 라는 것을 판단해서 그것만 최종적으로 마이닝을 수행하게 됩니다.

그리고 여기서는 이제 2아이템셋까지만 진행을 했는데 만약에 프리퀀터 아이템셋이 이렇게 3아이템셋도 있을 수가 있겠죠. 예를 들어서 비어, 다이아포, 너츠 이렇게 3개가 있을 수 있습니다. 그러면 이렇게 3 아이템이 있다면

이걸 활용해서 만들 수 있는 모든 어소시에이션 룰도 우리가 만들어 줘야겠죠. 예를 들어서 어떤 게 있냐면 여기서는 3개이기 때문에 2개, 1개로 쪼개서 어소시에이션 룰을 만들어야 됩니다. 예를 들어서 이렇게 3개 이상이 있을 때는 여기서 만들 수 있는 거. 그래서 B-er, 그리고 D-er가 있을 때 Nuts가 얼마나 나오는지

이런 식의 Association 룰을 만들 수도 있고요. 아니면 B-er가 나올 때 여기서 D-er와 Nuts가 함께 얼마나 많이 등장을 하느냐 이런식으로 만들 수도 있습니다. 그래서 총 6개의 Association Rule이 만들어질 수 있습니다. 그래서 일단 이런식으로 어떻게 우리가 Association Rule Mining을 진행을 하는지 알아봤는데요.

여기서 한가지 생각해야 될 것은 결국에 이 어소시에서 룰을 우리가 마이닝 하려면 먼저 Frequent item set을 구해야 됩니다. 그런데 이 Frequent item set이 만약에 이 아이템의 개수가 굉장히 많아지거나 거래의 개수가 굉장히 많아지면 여기서 구할 수 있는 Frequent item set의 조합이 굉장히 많아질 수 있습니다.

그러면 그것을 계산하는데도 굉장히 오래 걸리고 그리고 그 Frequent item set이 늘어나면 그에 따라서 Association 룰을 계산하는 그런 Association 룰도 굉장히 늘어나겠죠. 그래서 우리는 어떤 것을 항상 생각을 해야 되냐면 결국에는 Frequent Item Set을 어떻게 효과적으로 계산할 수 있는지. 또한 그 Frequent Item Set에서 Association Rule도 어떻게 효과적으로 우리가 얻어낼 수 있는지.

어떻게 효율적으로 계산을 해야 될지가 굉장히 중요합니다. 중요해지게 됩니다. 그래서 그 다음 페이지에서는 먼저 실제로 이런 데이터 베이스에 포함되어 있는 어트리뷰트 혹은 아이템의 항목이 늘어났을 때 얼마나 많이 프리퀀트 패턴이 증가할 수 있는지 이 문제점에 대해서 먼저 공부를 하고요.

그 다음에는 이 프리퀀트 패턴이 패턴이 너무 늘어났을 때 이것을 어떻게 효율적으로 해결할 수 있는지 그 방법에 대해서 이어서 공부를 해보도록 하겠습니다. 여기서 일단은 TDB1이라는 데이터셋이 있다고 우리가 가정을 하도록 하겠습니다. 여기에는 두 개의 트랜잭션이 포함되어 있는데요.

T1은 A1부터 A50까지의 이러한 아이템을 갖고요. T2는 아이템이 100개가 포함이 되어있습니다. 그래서 A1부터 A100까지 100개의 아이템을 포함을 하는 이러한 두 개의 트랜잭션으로 이루어진 데이터베이스가 있습니다. 그리고 여기서 우리가 어떤 Frequent 아이템셋을 찾기 위한 WinSub을 1로 설정을 했다라고 우리가 가정을 하도록 하겠습니다.

그러면 여기서 존재할 수 있는 모든 frequent item set을 한번 찾아보도록 하겠습니다. 먼저 k item set에 대해서 1 item set부터 한번 찾아봐야겠죠. 여기서 a1부터 a50까지의 item을 살펴보면 이거는 T1에도 등장하고요 T2에도 등장합니다. 그래서 서포트 총 몇 번 등장하느냐?

두 번을 등장하겠죠. 그래서 A1부터 A50까지는 서포트가 2입니다. 그리고 A51부터는 서포트가 1이겠죠. 그래서 결국에 서포트가 1만 넘으면 되니까 1 이상이면 되니까 1아이템셋은 총 100개의 모든 아이템이 모두 frequent하다는 걸 알 수 있습니다. 2아이템셋도 한번 계산을 해보도록 하겠습니다.

2아이템셋은 여기서 A1부터 A100까지 두 개를 임의로 가져와서 아이템셋을 만들 수 있겠죠. 그런데 여기서 A1과 역시 마찬가지로 A1에서 A50 사이에 있는 아이템으로 조합을 만들게 되면 모두 서포트가 2이고요. 나머지 조합은 모두 서포트가 1이 됩니다. 즉 여기서 T2가 A1부터 A100까지 모든 조합이