Lecture 5 10:12

대해서 공부를 해봤는데 이번에는 조금 더 응용된 여러가지 패턴 마이닝 방법들에 대해서 추가적으로 더 알아보도록 하겠습니다. 그래서 목차는 다음과 같고요. 먼저 이제 다양한 종류의 패턴 우리가 지난번에는 가장 기본적인 패턴에 대해서만 마이닝 분석을 진행을 했었는데 조금 더 다양한 형태의 패턴을 어떻게 분석할 수 있는지 먼저 알아보도록 하겠습니다.

먼저 지난 시간까지 단일 레벨에서의 패턴이 빈번한지 프리퀀트한지 아닌지에 대해서 분석을 계속해서 진행했는데요. 실제 데이터 같은 경우에는 오른쪽과 같이 어떤 계층 구조를 갖는 그러한 경우가 많이 있습니다. 그래서 이러한 멀티레벨로 구성된 데이터, 아이템이 멀티레벨로 구성되어 있을 때

어떻게 패턴을 분석할 수 있는지에 대한 방법입니다. 그래서 예를 들어서 오른쪽과 같이 우유를 예를 들어서 우유라는 상품이 있다고 했을 때 세부적인 상품명이 또 이렇게 나눠지는 경우가 있겠죠 예를 들은 것은 2% 밀크, 그리고 스킨드 밀크 이런 식으로 어떤 세부 품목이 또 이렇게 나눠지는 경우가 있습니다

그랬을 때 여기서 우리가 고려해야 될 것은 결국에는 그럼 이렇게 레벨이 여러 개 있을 때 민서포트 값을 어떻게 설정해 줘야 되는지가 사실 멀티레벨 프리퀀트 패턴을 분석할 때 가장 고려해야 될 부분이라고 생각을 해 줄 수 있습니다. 그래서 우리는 결국에 민서포트보다 서포트가 큰, 자주 나오는 패턴을 찾고 싶은 거죠.

그래서 여기서 민서포트를 만약에 둘 다 5%라고 모드 레벨에서 설정을 해 준다고 가정을 하겠습니다. 위에 있는 밀크 같은 경우에는 민 서포트보다 서포트가 크죠. 그렇기 때문에 프리퀀트 하다라고 우리가 패턴을 탐지를 할 수 있고요. 이 밑에 두 번째 레벨 같은 경우에도 왼쪽에 있는 2% 밀크 같은 경우에는 서포트가 6위니까 이 조건을 통과를 하는데

오른쪽에 있는 스킨드 밀크 같은 경우에는 서포트가 2밖에 되지 않을까 이 경우에는 해당이 그래서 여기서는 사실 왼쪽처럼 모든 레벨에서 서포트를 동일하게 설정을 할 수 있지만 우리가 일반적으로 생각했을 때 하위 카테고리로 갈수록 서포트가 줄어들 수밖에 없겠죠. 일반적으로. 왜냐하면 품목을 세분화하다 보니까

세분화된 품목은 당연히 서포트가 감소하는 현상을 놓을 수밖에 없습니다. 그래서 사실 오른쪽처럼 이렇게 레벨별로 서포트를 다르게 설정하는 것이 유리하고요. 그래서 정확한 수치는 상황마다 다르겠지만 일반적으로 하위 레벨로 갈수록 서포트를 더 낮게 설정해줍니다. 일단 이 부분만 알아두시면 될 것 같습니다.

그래서 결국에는 멀티레벨 불서가할 때 중요한 것은 레벨별로 서포트를 다르게 결정을 해야 됩니다. 사실 이게 두 번째 경우가 조금 더 많이 활용되는, 조금 더 알아둬야 될 그러한 경우인데요. 앞에는 레벨이 여러 개 있을 때 마이닝을 하는 방법에 대해서 알아 봤다면 이번에는 디멘전이 여러 개 있을 때 다차원적인 측면에서 패턴 마이닝을 진행하는 그런 방법에 대해서 알아보도록 하겠습니다.

그래서 지난 시간에 어소시에이션 룰을 계산을 했었죠. 예를 들어서 위와 같이 우유를 구매를 했을 때 빵도 구매하는 이러한 확률을 우리가 알아봤습니다. 이러한 관계를 어소시에이션 룰이라고 말을 했었는데요. 지난 시간까지는 단일 차원 싱글 디멘지언에 대해서만 이러한 어소시에이션 룰을 계산을 했습니다.

그래서 예를 들어서 이것은 어떤 구매에 대한 그런 한 가지 차원 또는 한 가지 관점에 대해서만 이러한 분석을 진행을 했습니다. 하지만 이러한 차원을 늘려가지고 여러 차원에서, 즉 다시 말해서 여러 관점에서 패턴 마이닝을 수행을 할 수도 있습니다. 예를 들어서 이러한 어떤 구매

구매 정보뿐만 아니라 구매자의 나이, 구매자의 직업, 어떤 상품을 구매를 했는지 이러한 다양한 정보들을 종합을 해서 이런 association 룰을 계산하는 경우도 있겠죠. 이것을 이제 multi-dimensional 룰이라고 일반적으로 부르고 있습니다. 그래서 여기에서는 두 개 이상의 어떤 dimension이 포함이 되고요. 이러한 dimension을 predicate라고 표현을 하기도 하는데요.

predicate는 이 아래에 있는 것 같이 예를 들어서 어떤 나이죠. 나이가 18세에서 25세 사이다. 이러한 조건을 만족시키는 것을 의미하죠. 이러한 조건식을 특정한 속성에 대한 조건식을 프리디케이트라고 부르고 있습니다. 그래서 이렇게 멀티딘젤널 물 같은 경우에는 여러 개의 프리디케이트 혹은 다 차원을 사용해서 분석을 하고요.

이것에 크게 두 가지로 분류를 할 수 있습니다. 첫 번째는 Inter-Dimension Association 룰입니다. 용어에서 알 수 있듯이 서로 다른 차원들 간의 연관관계만 분석을 하는 것을 의미합니다. 그래서 아래에 예시가 하나 나와 있는데요. 이 예시를 보면 어떤 연관관계를 의미를 하냐.

라고 했을 때 구매자의 나이가 18세에서 25세 사이고 그리고 직업이 학생일때 코크라는 상품을 구매하는 그러한 연관관계를 여기서 의미를 하게 됩니다 여기서 우리가 알아야 될 것은 동일한 속성에 대한 동일한 속성이 한 번씩만 사용이 되었습니다. 즉 이 속성을 차원이라고 부를 수 있겠죠. 즉 나이라는 차원, 직업이라는 차원, 그리고 구매라는 차원이 다 한 번씩만 등장해서 이 차원간의 연관관계를

분석하는 그러한 룰을 의미합니다. 그래서 아까 사용했던 predicate라는 용어를 사용을 해서 predicate가 즉 같은 차원이 반복되서는 안됐다 라는 것을 의미합니다. 그 다음 두 번째로는 hybrid dimension association 룰인데요. 이 하이브리드 같은 경우에는 동일한 차원 즉 동일한 프리리케이트가 여러 번 중복해서 나타날 수 있습니다.

그래서 다른 차원 간 분석도 진행을 하지만 같은 차원 내에서의 분석도 함께 진행을 하게 됩니다. 그래서 안에 예시를 보면 나이가 18세에서 25세이고 이런 사람이 팝콘을 구매를 했습니다. 팝콘을 구매한 이런 사람들 중에 콜라까지 구매한 사람이 얼마나 될까라는 이런 연관관계를 나타내고 있고요.

여기서 이 바이라는 디멘전이 중복해서 나왔죠. 왼쪽 오른쪽에. 그렇기 때문에 이것은 이제 같은 디멘전 내에 어떤 연관관계도 분석을 해주기 때문에 이제 하이브리드 디멘전 어소시에이션 롤에 해당이 됩니다. 그리고 추가적으로 이 어트리뷰트 위에서 나온 이런 어트리뷰트가 범주형일 수도 있고요 수치형일 수도 있겠죠.

그래서 사실 범주형 어트리뷰트 같은 경우에는 우리가 계속해서 다뤄온 그러한 것들을 의미합니다. 예를 들어서 직업 상품 등이 해당이 되는데요. 여기서 이 밀크 브랜드와 같은 이러한 상품은 범주형 속성에 해당이 되죠. 그래서 우리가 지금까지 계속해서 공부해왔던 그런 어소시에이션 룰을 그대로 활용을 해서 이 범주형 속성일 때 분석은 가능합니다. 그 다음에 quantitative attribute 수치형을 의미하는데요.

이 경우에는 추가적인 처리가 필요하게 됩니다. 그래서 그 방법에 대해서 다음 슬라이드에서 다뤄보도록 하겠습니다. 그래서 대표적으로 예를 들어서 앞에서 나온 age, 나이나 salary 같은 경우에는 수치형 속성에 해당이 되죠. 이러한 경우에는 가질 수 있는 값이 무수히 많기 때문에 결국에는 이것을 그룹핑을 시켜줘야 됩니다. 즉 수치형일 때는 이러한 속성들을, 이런 속성의 값들을

그룹화를 해서 결국 범주 형태로 만든 다음에 그 상태에서 어소시에이션 룰을 분석을 해주게 됩니다. 그래서 범주형 속성으로 그루핑을 하는 방법은 여러가지가 있을 수가 있겠죠. 그래서 대표적으로 이산화 방법을 사용할 수 있는데요. 첫번째로 스태틱 정적인 방법 같은 경우에는

우리가 미리 정의해준 컨셉 하이라키가 있죠. 이것을 사용해서 결국에는 미리 정의된 대로 그룹을 만드는 방법입니다. 나이다 라고 하면은 우리가 이것을 예를 들어서 0~10세 그리고 10~20세 이런 식으로 분류를 해 놓을 수 있습니다. 그러면 그 분류된 사전 정의된 그런 기준에 따라서 먼저 age를 그룹화를 할 수 있고요.

그리고 추가적으로 여러 차원의 hierarchy가 있으니까 이것을 한 번 더 진행을 해서 다시 한번 번요. 미드에이지, 올드 이런 식으로 더 압축을 해서 그룹화를 진행할 수 있습니다. 그래서 결국 핵심은 미리 사전 정의된 그런 계층 정보를 이용을 한다. 라는 그런 이상한 방법이고요. 두 번째는 동적인 이산화 방법을 사용할 수 있습니다.

미리 정해둔 기준이 아니고 그 데이터의 분포를 보면서 그 분포에 맞게 이산화를 진행하는 방법입니다. 그래서 이런 방법들은 우리가 이전 챕터에서 배웠던 통계분석에서 사용하는 그런 이산화 방법들을 사실 그대로 사용을 할 수 있습니다. 그 다음에 클러스터링을 진행을 할 수도 있겠죠. 그래서 각 속성의 각별로 거리를 측정을 해서 거리가 가까운 것끼리 클러스터링을

수행을 할 수 있습니다. 그래서 각 클러스터끼리 결국에는 association 룰을 분석을 하는 그런 방법을 사용할 수 있습니다. - Mm-hmm. 다음은 레어 패턴, 그리고 네거티브 패턴에 관한 내용인데요. 우리가 일반적으로 지금까지는 항상 프리퀀트 패턴, 자주 함께 나타나는 그런 패턴에 대해서만 인석을 진행을 했습니다.

일반적으로는 자주 함께 발생하는 그런 프리퀀트 패턴이 많은 의미를 지니고 있을 경우가 많습니다. 하지만 이제 때때로 굉장히 드물게 등장하는 레어 패턴이 의미가 있는 경우도 있을 수 있고요 그렇게 되면 이러한 레어 패턴도 우리가 마이닝을 진행을 해줘야겠죠 그래서 레어 패턴은 굉장히 드물게 나타나지만 즉 굉장히 낮은 서포트를 가지고 있지만 그러나 어떤 의미를 가질 수 있는 그런 패턴을 의미합니다.

예를 들어서 구매내역을 볼 때 이런 명품 시계를 구매한다는 것은 이런 구매 이력이 굉장히 자주 나타나지는 않겠죠. 상대적으로 하지만 이런 패턴이 완전히 의미 없다고 할 수는 없는게 어떤 특정 소비층의 소비 패턴을 분석을 하는 데는 이러한 패턴이 중요하게 사용될 수도 있습니다. 그래서 이러한 경우에는 이러한 레어 패턴을 분석을 해줘야겠죠.

그래서 레어 패턴을 분석을 하기 위해서는 그래서 민서포트 값을 기존에 설정을 할 때 사실 일괄적으로 모든 아이템에 대해서 동일하게 설정을 해주면 이러한 레어 패턴을 찾을 수가 없고요. 일반적으로 우리의 분석 목적에 맞게 이 민서포트 값을 아이템의 어떤 성격에 따라서 혹은 그룹화해서 그룹별로 다르게 설정하는 그러한 전략이 필요합니다. 이런 일을 넣어서 명품 같은 경우에는 일반적으로 붐의 이런 패턴이 많이 발생하지 않으니까 그런 그룹에 대해서는 민서포트 값을 다른 그룹보다 낮게 설정을 해준다.

이렇게 진행을 해주게 되면은 일부 레어 패턴도 우리가 잘 마이닝을 진행을 해줄 수가 있습니다. 그 다음으로 우리가 네거티브 패턴도 분석을 해줄 필요가 있는데요. 네거티브 패턴은 레어 패턴과 유사한 점을 가지고 있는 것은

두 아이템이 함께 잘 등장하지 않는 경우를 의미합니다. 그래서 결국에는 서포트 값이 비교적 낮은 경우를 의미하겠죠. 그런데 레어 패턴과 차이점은 뭐냐면 레어 패턴은 단순히 그 패턴이 드물게 등장하는 것을 레어 패턴이라고 하고요. 레거티브 패턴은 이 두 개의 각각보다 두 개가 이제 같이 등장할 확률이 낮은 경우를 의미를 합니다.

즉 어떠한 두 개의 아이템 혹은 여러 개의 아이템이 서로 음의 상관관계를 가지고 있는 그런 패턴을 의미를 합니다. 합니다. 그래서 아래 메시가 있는데요. 예를 들어서 어떤 고객이 자동차를 구매를 하는 상황인데 예를 들어서 이 두 가지 포드사의 SUV 자동차와

하이브리드 자동차를 동시에 구매하는 일은 거의 없겠죠. 일반적으로 자동차 자체는 구매를 많이 하지만 자동차를 한 대에만 한 번에 구매를 하지 이런 두 가지 자동차를 동시에 구매하는 경우는 굉장히 드뭅니다. 그래서 각각은 어떤 서포트 값이 낮지 않지만 이 두 개가 조합됐을 때 그 서포트 값이 굉장히 작아지는 것을 즉 음해 상용음해를 가진다고 하구요.

이러한 패턴들을 이제 네거티브 패턴 이라고 합니다. 그래서 음의 상황은 어떻게 하나의 패턴에 해당이 되기 때문에 이러한 것들도 분석을 잘 진행을 해주면 좋겠죠. 그래서 이러한 네거티브 패턴을 어떻게 우리가 정의를 해서 마이닝을 수행할 수 있을지에 대해서 추가적으로 좀 더 구체적으로 알아보도록 하겠습니다. 그래서 이 네거티브 패턴 혹은 네거티브 코렐레이티드 패턴 이라고 하는 것을 이제 정의를 해줄 건데요.

가장 쉽게 정의를 하는 방법은 이제 서포트 기반으로 이제 정의를 하는 겁니다. 그래서 아까 말씀드렸던 것처럼 각각 독립적으로 나타나는 것보다 함께 나타날 확률이 유의미하게 적은 것을 네거티브 패턴 이라고 한다고 했으니까 이제 아래와 같이 정의할 수 있습니다. 오른쪽은 A라는 아이템 그리고 B라는 아이템이 각각 나타날 확률이죠.

그래서 이 두 개가 독립일 때 각각 나타날 확률을 의미합니다. 왼쪽은 A와 B가 함께 등장할 확률이죠. 그래서 독립일 때 각각 두 개가 등장할 확률보다 같이 묶여서 한 번에 등장할 확률이 유의미하게 낮다면 이것을 네거티브 패턴이다 라고 우리가 정의를 해줄 수가 있습니다. 그런데 이렇게 서포트로 정의를 하게 되면 단순하게 정의를 할 수 있지만 조금 하나의 문제점이 발생하게 되는데요.

그 문제점에 대해서 한번 아래와 같은 예시로 알아보도록 하겠습니다. 그래서 먼저 어떤 문제인지 그냥 말씀을 드리냐면 전체 거래의 개수에 크게 이러한 패턴의 영향을 받는다. 이 패턴이 전체 거래 수에 큰 영향을 받는다라는 그런 단점을 가지고 있습니다. 그래서 아래에 어떤 상황을 가정을 할 거냐면 어떤 바늘 상품을 두 가지를 우리가 구매를 한다고 가정을 하도록 하겠습니다.

그래서 A라는 상품, B라는 상품 두 개가 있는데요. 각각 100번씩 우리가 거래가 됐다고 가정을 하도록 하겠습니다. 그래서 A라는 상품 100번, 트랜잭션이 거래 트랜잭션에 A라는 상품이 100번 포함이 되어 있고요. 전체 트랜젝션에 B라는 상품이 100번 포함이 되어 있습니다. 그리고 A와 B를 함께 구매한 트랜젝션은 오직 하나밖에 없다고

이러한 상황을 우리가 가정을 해보도록 하겠습니다. 그럼 먼저 첫번째 케이스는 전체 거래량이 200개인 경우입니다. 그래서 총 트랜잭션이 200번 수행을 됐을 때 한번 이러한 이게 이제 네거티브 패턴인지를 한번 찾도록 하겠습니다. 그럼 먼저 A와 B가 동시에 일어나는 경우는 이제 한 번밖에 없었죠.

전체 200번 중에 한 번 일어났으니까 1/200이 되겠죠. A와 B가 함께 일어나는 경우에 Relative Support 같은 경우에는 1/200입니다. 그래서 0.005 값이 나오는 걸 확인할 수 있고요. 그리고 S가 발생하는 경우는 전체 200번 중에 100번 구매가 됐으니까 1/200이죠. 그래서 1/2이니까 50%고요. B도 마찬가지로 Support가 50%입니다.

그러니까 이거 두 개를 곱하니까 1/4을. 0.255가 나오게 됩니다. 그래서 A와 B가 독립이라고 가정을 했을 때는 0.25만큼 발생을 해야 되는데 실제로 0.005만 발생이 되었으니까 이거는 의외상관 의외를 가지고 있다. 즉 네거티브 패턴이라고 여기서 우리가 판단을 할 수가 있겠죠. 근데 여기서 거래량이 한번 바뀌었다고 가정을 해보도록 하겠습니다.

그래서 원래는 200번 거래가 일어났다고 가정을 했는데 10에 5승만큼 거래가 발생을 했다고 가정을 해보도록 하겠습니다. 그럼 A와 B가 동시에 발생하는 경우에 서포트를 계산을 하면은 거래가 발생을 했으니까 전체 10의 5승분의 1이 되겠죠. 그리고 A와 B가 각각 발생할 확률은 전체 10의 5승분의 100번이 거래가 됐으니까

각각 10의 5승분의 100이 되겠죠. 그러니까 약분을 해서 10/3승분의 1만큼 각각의 서포트가 계산이 됩니다. 이 두 개를 곱하니까 결국에는 10/3승분의 1이 되겠죠. 그래서 이 경우에는 왼쪽과 오른쪽을 비교를 했을 때 서포트 값이 A와 B가 동시에 발생하는 게 15승이고 오른쪽이 16승이니까 오히려 커지게 됩니다.

그러니까 이 경우에는 음의 상황이 아니라 오히려 양의 상황을 가진다 이렇게 우리가 잘못 판단을 해줄 수도 있겠죠. 결국에는 이 밑의 경우에는 우리가 양의 상황을 가진다 이렇게까지 말할 수는 없지만 이 기준으로 봤을 때는 음의 상황을 가지지 않는다 라고 즉 네거티브 패턴이 아니다 라고 판단을 해주게 됩니다. 결국에 이렇게 서포트 베이스로 정의를 해줬을 때 문제점은

전체 트랜잭션의 영향을 이 결과가 받아버린다는 그러한 단점을 가지고 있습니다. 즉, Null Transaction이 많이 포함이 될수록 Null Transaction은 결국에는 A라는 아이템, B라는 아이템 이 두 개 다 포함되지 않는 그러한 우리가 원하는 거래에 해당되지 않는 그러한 나머지 Transaction을 의미합니다.

그래서 이 Null Transaction에 영향을 많이 받는다는 특성을 가지고 있고요. 이것을 우리가 어떻게 표현을 하냐면 Null invariant 하지 않다 라고 표현을 합니다. 그래서 다시 정리를 하자면 이러한 서포트 기관의 정의는 Null invariant 하지 않습니다. 그래서 전체 거래량에 크게 영향을 받게 됩니다.

그런데 사실 우리가 어떤 분석을 진행을 할 때 A의 거래량 B의 거래량 같이 발생한 거래량 이게 중요하지 그것과 상관없는 전체 거래량에 영향을 받으면 안 되겠죠. 그래서 사실 우리는 이 정의를 다시 해서 결국 Null Invariant 한 그러한 좋은 정의로 다시 이러한 네거티브 패턴을 마이닝 할 필요가 있습니다.

그래서 이렇게 Null Transaction에 영향을 받지 않는 이런 Null Invariant 한 좋은 정의 중의 하나가 쿨친스키 매저에 기반한 이러한 정의가 대표적으로 있습니다. 그래서 컬치스키 매저 같은 경우에는 이 오른쪽 조건을 만족할 때 이것을 아이템을 프리퀸트하다. 즉 이 아이템이 네거티브 패턴이다 라고 판단을 하는 그런 방법을 의미합니다.

그래서 오른쪽 메저를 사용을 하게 되면 결과적으로는 네거티브 패턴까지 데이터 마이닝을 수행할 수 있겠죠. 그래서 오른쪽 measure를 살펴보면 결국 a가 발생할 확률 대비 a와 b가 동시에 발생할 확률. 즉 a가 포함된 것 중에 b도 얼마나 함께 포함이 되어 있는지. 그리고 반대로 b가 포함이 되어 있을 경우에 a도 얼마나 함께 포함이 되어 있는지를 각각 구해서 이것의 평균을 내게 됩니다.

그리고 이 값이 최종적으로 입실롱보다 작을 경우에 아예 네거티브 패턴이라고 판단을 해주게 됩니다. 그러면 이렇게 계산을 하면 왜 널 임패리언트 하냐고 한다면 이제 앞에 식을 한번 다시 볼 수 있는데요. 이 서포트 기반의 정의가 왜 null invariant 하지 않냐면

이 계산 방식 때문인데요. 이 왼쪽의 식을 보면 결국에는 전체 거래 중에 전체 거래를 n 이라고 하면은 전체 거래 중에 A와 B가 동시에 발생하는 그런 경우를 구하고 있죠. 그리고 오른쪽을 보면은 이 SA 같은 경우에는 전체 거래 중에 A가 발생하는 경우이고요. SB 같은 경우에는 전체 거래 중에 B가 발생하는 경우에 해당이 됩니다.

그래서 왼쪽과 같은 경우에는 사실 왼쪽이 분자가 된다고 생각할 수 있는데 이 n이 한 번밖에 안 곱해지고요. 오른쪽은 이 분모에 n 제곱이 들어가게 됩니다. 그래서 이 오른쪽 좌변과 우변에 n을 하나씩 상쇄를 하더라도 이 오른쪽에 n이 전체의 개수가 하나가 남게 되죠. 그렇기 때문에 이러한 측정 방식 같은 경우에는 이 전체 거래 개수의 영향을 받을 수밖에 없게 됩니다.

그래서 nullimperior는 하지 않게 되는데요. 이렇게 계산을 하게 되면 이 분자를 보면 분자에도 n이 한 개 들어가고요. 이 분모에도 n이 한 개 들어가죠. 즉, 이거는 예를 들어서 앞에 것만 하면 전체에서 A와 B가 발생할 확률, 분모 같은 경우에도 전체 중에 A가 발생할 확률 이렇게 우리가 약분을 하니까 N과 N이 결국에는 상쇄돼서 이 전체 식 같은 경우에는 전체 거래 개수인 N에 영향을 받지 않게 됩니다.

그래서 결국에는 전체 거래 횟수가 200번이든 10의 5승이든 그것과 상관없이 항상 동일하게 네거티브 패턴인지 아닌지를 평가할 수 있게 됩니다. 예를 들어서 200번의 거래가 발생을 했다고 가정을 하겠습니다. 이 왼쪽 같은 경우에는 200번 중에 A는 100번 거래가 발생했고요.

동시에 발생한 것은 1번이죠. 그러니까 이 값은 항상 100분의 1 값을 갖게 됩니다. 거래량이 10에 5승으로 늘어났어도 역시 이 앞에 값은 100분의 1이겠죠. 이 뒤에 값도 마찬가지로 100분의 1이고요. 그래서 전체적으로 이제 왼쪽 값을 계산하면 항상 100분의 1이라는 값이 나오게 됩니다. 그래서 우리가 입실론을 0.02로 설정을 했다면은 이것은 네거티브 패턴이다 라고 전체 거래량에 상관없이 항상 그렇게 판단을 해 줄 수 있게 됩니다.

그 다음으로는 우리가 패턴 마이닝을 진행을 하다보면 굉장히 많은 패턴들을 우리가 찾을 수 있게 됩니다.

그래서 우리가 찾게 되는 경우에는 패턴이 너무 많기 때문에 이것을 다 표현하게 되면 저장공간이 너무 많이 필요하게 될 수도 있죠. 그리고 우리가 실제로 그 패턴을 보기에도 너무 많은 패턴들이 있으니까 오히려 중요한 정보를 잘 파악하지 못할 수도 있습니다. 그래서 굉장히 많은 패턴을 압축해주는 마이닝 압축 기술에 대해서 한번 알아보도록 하겠습니다.

그래서 왼쪽과 같이 이런식으로 어떤 각 패턴에 대한 소프트 값이 있다고 가정을 한번 해보도록 하겠습니다. 여기서 P1과 P2를 보면은 이 두개의 패턴은 사실 굉장히 유사한 패턴에 해당이 됩니다. 왜냐하면 여기에 포함되어 있는 일단 아이템 셋이 굉장히 유사하죠. 이 두개의 차이는 나머지는 다 유사하고 P2에만 17이라는 아이템만 추가가 되어 있습니다.

그리고 두 번째로 서포트 값이 또 다를 수도 있는데 서포트 값이 완전히 같지는 않지만 굉장히 그래서 사실 P1과 P2는 굉장히 유사한 패턴이다 라고 생각을 해 줄 수 있고요. 반면에 P2와 P3 같은 경우에는 유사한 패턴이라고 생각을 해 주기는 힘듭니다. 왜냐하면 사실 아이템셋은 굉장히 유사합니다. 다른 곳이 포함되어 있다 빼고는 나머지 아이템이 동일하죠.

근데 문제는 이 서포트 값이 굉장히 많이 차이가 납니다. 그래서 이 하나의 아이템이 추가가 됐을 때 결국에는 서포트가 굉장히 크게 달라지고 있으니까 이 P2와 P3는 비슷한 패턴이라고 보기는 어렵겠죠. 그리고 P4와 P5도 보면 아까와 같은 이유로 아이템도 비슷하고 서포트도 비슷하니까 아 이거를 이제 비슷한 패턴이다 라고 이렇게 묶어 줄 수 있습니다

그럼 우리가 이렇게 정성적으로 봤을 때는 이렇게 비슷한 패턴끼리 묶을 수 있는데 이것은 어떤 룰을 정해줘야지 우리가 자동으로 이렇게 비슷한 패턴을 압축을 시킬 수 있겠죠. 그래서 어떻게 이렇게 압축을 시킬 수 있는지에 대해서 한번 알아보도록 했습니다. 사실 그래서 우리가 지난 시간에 굉장히 기본적인 어떤 아이템셋의 압축 기술에 대해서 공부를 해봤습니다.

그래서 첫 번째로 이제 Closed Pattern 이라는 것에 대해서 공부를 했었는데요. 이 Closed Pattern은 결국에는 같은 서포트를 가지고 있는 패턴들끼리 압축을 진행을 합니다. 같은 서포트를 가지고 있는 것 중에 가장 큰, 크기가 큰 슈퍼셋 하나로 압축을 진행하는 것을'Closed Pattern'이라고 했습니다. 그런데 여기서는 그런 Closed Pattern을 적용할 수가 없는게

사실 이 서포트 값이 완전히 같지는 않죠. 그런데 Closed Pattern은 같은 서포트 값을 가지는 것끼리만 압축을 진행할 수 있기 때문에 여기서는 적용하기가 어렵습니다. 그래서 사실 클로즈드 패턴 방식을 적용해도 압축이 전혀 되지 않고요. P1부터 P5가 그대로 이렇게 남게 됩니다. 두 번째 우리가 배운 압축 기술은 더 크게 압축을

대신에 손실이 발생하는 압축 기술이 맥스패턴이라는게 있습니다. 맥스패턴 같은 경우에는 서포트에 상관없이 가장 크기가 큰 슈퍼셋 하나로만 압축을 진행하는 방식입니다. 여기서 P3를 보면은 이 P3가 나머지 패턴을 모두 다 포함하고 있는걸 확인할 수 있습니다. 이 나머지 패턴에 있는 아이템들이 모두 P3의 부분집합에 해당되기 때문에 이 P3는 나머지의 슈퍼셋에 해당이 됩니다.

그래서 결국에는 서포트 값에 상관없이 P3로 한번에 이렇게 압축을 진행을 할 수 있습니다. 이렇게 하게 되면 압축은 잘 되는데 P1, P2, P4, P5가 가지고 있는 각각의 서포트 값이 모두 다 날아가 버리죠. 그렇기 때문에 굉장히 많은 손실이 발생을 해서 사실 적합한 압축 기술은 역시 아닙니다. 우리가 원하는 것은 아래와 같이 P1과 P2가 비슷하니까 P2 이렇게 하나 압축을 하고요.

P3는 독립적이니까 그대로 놔두고, P4와 P5가 서로 비슷하니까 이 중에서 하나 P4 이렇게 남겨서 P2, P3, P4 이렇게 압축을 하는게 사실 가장 적합하겠죠. 그래서 이렇게 압축을 할 수 있는 방법이 오른쪽에 있는 델타 클러스터링이라는 방법이고요. 이 델타 클러스터링은 위와 같은 패턴 디스턴스 매저를 사용합니다. 먼저 패턴 디스턴스 매저에 대해서 설명을 드리면

이런 매저 같은 경우에는 어떤 아이템 셋에 포함된 아이템 자체가 유사한지를 판단을 하는게 아니고요. 어떤 특정한 패턴이 포함되는 트랜잭션 셋이 있죠. 그 트랜잭션 셋이 얼마나 많이 겹치는지를 판단을 하게 됩니다. 예를 들어서 P1에 대한 패턴을 포함하는 트랜잭션의 집합이 있겠죠.

그리고 P2라는 패턴이 포함되는 트랜잭션 집합이 있을 겁니다. 그 두 개가 얼마나 많이 겹치는지에 따라서 이렇게 거리를 판단하게 됩니다. 많이 겹칠수록 유사한 트랜잭션에 계속 반복적으로 같이 등장하니까 당연히 거리가 낮고요. 그렇지 않을수록 이제 거리가 더 커지게 됩니다.

그래서 P1과 P2를 한번 계산을 하면은 사실 P2가 만약에 등장을 했다는 것은 P1도 당연히 그 트랜젝션에는 포함이 되어 있다는 것을 의미하겠죠. P2가 P1의 슈퍼스태이기 때문입니다. 그래서 결국 P1과 P2의 교집합은 여기서는 함께 등장하는 것은 P2가 등장하는 서포트와 동일해지게 됩니다.

그래서 오른쪽에 이 분자에 해당되는 것은 P2의 서포트겠죠. 그리고 P1과 P2의 합체판 같은 경우에는 결국 P1의 서포트가 되겠죠. 그렇기 때문에 이렇게 Distance를 계산을 하게 되면은 결국에 P1과 P2 같은 경우에는 합집합인 205227분의 교집합인 P2의 서포트.

그래서 205211이 디스턴스로 계산되게 됩니다. 그럼 이 값은 거의 0에 가까운 이러한 값이 나오게 되겠죠. 왜냐면 앞에 이제 1에서 2값을 빼니까 결국 최종적인 값은 1에서 2값을 빼게 되면 거의 0에 가까운 distance가 나오게 됩니다. 그래서 P1과 P2는 같은 그룹에 포함이 되어 있다고 우리가 판단을 해 줄 수 있게 됩니다.

그러면 P2와 P3도 계산을 해보도록 하겠습니다. 여기서는 P3가 P2의 superset입니다. 그래서 교집합 같은 경우에는 결국에 p3의 서포트 값이 되고요. 합집합은 p2의 서포트 값이 되겠죠. 그래서 이 경우에는 결국에 1-205211분의 10

1층, 5, 8이 되겠죠. 그러면 이 값은 대략적으로 1/2 값이 나오게 됩니다. 그래서 P2와 P3의 패턴 디스턴스를 구하면 0.5 정도가 나오니까 이 두 개는 같은 그룹으로 묶을 수 없다에 해당이 됩니다. 판단 기준, Threshold 같은 경우에 우리가 정해줘야겠죠. 0.1을 기준으로 할건지, 0.2를 기준으로 할건지, 이런 것을 정해줘야 됩니다.

그래서 이렇게 Distance를 계산하게 되면 결국 우리가 원했던 대로 P1과 P2가 하나의 그룹으로 묶이고요. P3가 동류적으로 묶이고 P4와 P5도 거의 지금 유사하게 되겠죠. 그렇기 때문에 P4와 P5가 하나의 그룹으로 바뀌게 됩니다. 그래서 이렇게 델타 클러스터링을 수행할 수 있는데요. 델타 클러스터링은 결국에 방금 전에 했던 것처럼 이러한 패턴 디스턴스를 기반으로 해서

어떤 델타 나는 우리가 Threshold를 정해주게 되고요. 이 델타 거리내에 있는 모든 패턴들을 하나의 그룹으로 묶게 됩니다. 예를 들어서 델타를 0.1로 설정을 하면 이 패턴간의 거리가 0.1 이내에 있는 모든 패턴들을 하나의 그룹으로 묶게 되고요. 그 하나의 그룹 또는 하나의 클러스터를 대표하는

하나의 대표 패턴으로 표현을 해주게 됩니다. 결국에 각 델타 범위에 있는 패턴을 묶은 다음에 하나의 대표 패턴으로 표현을 해주는 방식인데 그러면 대표 패턴은 어떻게 봐냐 라고 하면은 대표 패턴은 그 하나의 클러스터 안에 있는 모든 패턴들을 다 포함을 하는 그런 패턴이어야 합니다. 예를 들어서 P1과 P2가 하나의 클러스터로 붙이겠죠.

P2로 P1도 표현할 수 있고 P2도 표현할 수 있으니까 이 P2가 여기서는 대표 패턴이 됩니다. 그래서 P1과 P2는 대표 패턴 P2로 나타내주십니다. P4와 P5 같은 경우에도 P4가 P5를 포함하고 있으니까 P4로 대표 패턴을 지정을 해서 나타내 주고 있습니다. 그리고 이렇게 하나의 대표 패턴이 델타 범위에 있는 다른 모든 패턴을 표현을 해주고 있죠.

델타 커버라고 부르고 있습니다. 즉 델타 범위만큼을 하나의 대표 패턴이 커버해주고 있다는 것을 의미합니다. 네 그러면 이제 압축 기술에 대해서 한번 알아봤고 그 다음에는 컨스트라인트 기반의 패턴 마이닝 기법에 대해서 추가적으로 알아보도록 하겠습니다.

실질적으로 우리가 패턴 마이닝을 진행을 할 때는 여러가지 제약 조건들이 많이 붙을 수가 있습니다. 그래서 뭐 예를 들어서 사용자가 원하는 조건 분석 목적에 따른 조건이 있을 수도 있겠죠. 특정 아이템에 대한 분석만 진행해 달라든지 아니면 특정한 나이대에 대한 그런 분석만 진행을 해 달라든지

이러한 특정 제약 조건들이 붙을 수 있습니다. 그래서 실제로 유저는 이러한 쿼리 랭기지를 직접 사용을 해서 이러한 제약 조건들을 명시를 할 수도 있고요. 아니면 편하게 GUI를 사용해서 결국에 이러한 제약 조건들을 설정을 해줄 수도 있습니다. 그래서 이러한 결국에는 다양한 제약 조건들을 반영을 해서 패턴 마이닝을 수행을 우리가 해줘야 됩니다.

그래서 패턴 마이닝을 수행을 할 때 우리가 배울 constraint based mining은 무엇을 의미하냐 라고 한다면 우리는 기존의 패턴을 찾을 때 어떤 조건으로만 패턴을 찾아내면 서포트를 기준으로만 패턴을 찾았죠 그래서 서포트가 win-support 보다 큰 패턴만 그러한 하나의 조건을 가지고 우리가 패턴 마이닝을 수행을 했습니다.

그런데 이제 컨스트레인트 기반의 마이닝 같은 경우에는 그러한 민서포트보다 서포트가 커야 된다라는 조건 말고도 사용자가 직접 설정한 다양한 제약 조건을 함께 고려를 해서 패턴 마이닝을 수행을 하는 것을 의미를 합니다. 이러한 컨스트레인트 기반의 마이닝을 수행을 했을 때 장점은

첫 번째로 사용자가 자유롭게 자기가 원하는 분석 목적에 따라서 이러한 제약 조건들을 추가해서 데이터 마이닝을 진행할 수 있다는 장점이 당연하게도 하나 있고요. 두 번째로는 더 효율성도 증가가 되게 됩니다. 왜냐하면 우리가 만약에 처음에 모든 패턴을 패턴 마이닝을 통해서 쭉 다 찾았습니다.

그 다음에 마지막에 거기서 우리가 찾은 패턴들 중에서 제약조건에 맞는지 맞지 않는지를 찾아내는 방법을 사용할 수도 있겠죠. 예를 들어서 특정 상품이 포함이 되어야 된다 라고 하면은 일단 그걸 무시하고 패턴 마이닝을 다 끝내는 다음에 마지막 나온 패턴에서 그 상품이 포함되지 않는 것을 제외하면 됩니다. 그런데 이렇게 했을 때의 단점은 즉 일반적인 패턴 마이닝을 수행을 했을 때의 단점은

탐색 공간이 전혀 줄어들지 않는다는 그런 점이 있습니다. 하지만 우리가 제약 조건을 만약에 미리 패턴 마이닝을 수행을 할 때부터 우리가 제약 조건을 기반으로 수행을 하게 되면은 탐색 공간 자체를 미리 줄일 수 있습니다. 패턴 분석을 수행할 때 이 아이템이 포함되지 않는 것을 미리 제거를 해서 탐색 공간을 애초부터 줄이게 되면 마이닝을 하는데 필요한 저장 공간이나

아니면 연산량이 크게 줄어들 수 있게 되겠죠. 그래서 우리가 알아야 될 것은 어떻게 이렇게 포턴 마이닝을 수행하는 단계에서 제약 조건을 미리 반영을 해서 탐색 공간을 줄일 수 있을까 하는 그 점에 대해서 이제 알아보도록 하겠습니다. 그래서 그게 이제 두 번째 장점입니다. 그래서 이렇게 마이닝이 다 끝난 다음에 이러한 제약 조건을 고려하는 게 아니고 마이닝 프로세스 자체에

이런 컨스트레이트를 고려하는 것을 이 컨스트레이트를 푸싱한다고 일발적으로 표현합니다. 컨스트레이트를 푸싱한다는 것은 마이닝을 진행할 때 미리 이런 컨스트레이트를 고려해서 탐색공간을 줄이는 작업을 진행한다. 다른 것은? 미안합니다.

그런데 모든 컨스트레인트가 탐색 공간을 줄일 수 있는 것은 아니고요. 그 컨스트레인트의 특성에 따라서 효율적으로 탐색 공간을 잘 줄일 수 있는 컨스트레인트도 있고요. 이러한 효과가 많이 없는 제약 조건이 있을 수도 있습니다. 그래서 일반적으로 중요하게 생각되는 제약 조건의

몇 가지 특성에 대해서 알아보도록 하겠습니다. 먼저 안티모노토닉 혹은 안티 모노톤하다 라고 얘기되는 그런 컨스트레이트의 특징입니다. 그래서 어떠한 컨스트레이트 C가 안티 모노톤하다 라고 말이 되는 것은 어떠한 아이템셋 S가 이러한 제약 그 제약 조건을 만족하지 않다면 그 S의 모든 슈퍼셋도 그 제약 조건을 역시 만족하지 않는 경우를 의미합니다.

이런 경우에는 굉장히 효율적으로 탐색 공간을 우리가 줄일 수 있는데요. 어떤 S라는 아이템이 제약 조건을 만족하지 않으면 그 슈퍼셋도 제약 조건을 만족하지 않으니까 그 슈퍼셋을 탐색을 할 필요가 없겠죠. 어차피 제약 조건을 만족하지 않는 것은 우리가 탐색을 진행할 필요가 없기 때문입니다. 이러한 안티 모토는 우리가 기존에 지난 시간에 공부했던

A'라인 프루닝 방법과 굉장히 유사합니다. 기존에 이러한 프루닝 방법도 결국에는 어떠한 오리와 패턴의 서포트가 윈 서포트 조건을 만족하지 않는다면 즉 어떠한 패턴의 서포트가 윈 서포트보다 작다면 애초에 그것의 슈퍼셋도 서포트가 더 낮아질 수밖에 없겠죠.

아이템이 추가가 되면은 당연히 등장 빈도가 낮아지니까요. 그렇기 때문에 그 패턴의 슈퍼셋도 모두 다 탐색을 하지 않고 애초에 푸르닝 할 수 있다는 그런 원리가 A'PRIORI 프로닉 방식이었습니다. 사실 그 원리를 동일하게 사용한다 라고 생각을 할 수 있고요. 사실 뒤에서 나오겠지만 그래서 이러한 A'PRIORI 방법도 이러한 안티 모노토닉한 특성 중의 하나에 결국에는 해당이 됩니다.

그래서 이러한 다양한 예시를, 몇 가지 예시를 통해서 아마 어떤 제약 조건이 이러한 안티 모노토닉한 성질을 만족하는지 한번 알아보도록 하겠습니다. 먼저 첫번째로 어떤 아이템셋의 가격의 총합이 V보다 작거나 같다는 제약 조건입니다. 이러한 제약 조건은 Anti-Monotone 합니다.

왜냐하면 어떤 아이템셋이 이미 그러면 이 V보다 총 합이 가격이 크다는 거죠. 그럼 아이템이 새로 추가가 되면 가격은 일반적으로 양수니까 이 가격의 합이 커질 수밖에 없겠죠. 그럼 당연히 그 슈퍼셋도 이 조건에 만족하지 않게 됩니다. 그래서 어떤 한순간에 아이템 셋이 이 조건을 만족하지 않는다면 모든 슈퍼셋도 이 조건을 만족하지 않기 때문에

이러한 제약 조건은 안티 모노톤에 해당이 됩니다. 두번째는 어떤 이익의 레인지가 15보다 작거나 같다는 조건입니다. 여기서 range라는 것은 최소값과 최대값의 차이를 의미합니다. 이미 최소값과 최대값의 차이가 15보다 컸다는 것을 의미하겠죠. 그러면 새로운 아이템이 추가가 됐을 때

최대값, 최소값은 당연히 그 범위가 더 커질 수만 있고 더 작아질 수는 없겠죠. 이미 있는 아이템을 뺄 수는 없으니까요. 그렇기 때문에 역시 이것도 모든 슈퍼셋도 이 조건을 마주하지 않기 때문에 안티 모노톤입니다. 세 번째로 어떤 가격의 아이템의 아이템 셋의 가격의 합산이 부위보다 크거나 같다 인데요. 이 경우는 안티 모노톤 하지 않습니다.

왜냐하면 어떠한 아이템 셋이 이 조건을 만족하지 않는다는 것은 총합이 부위보다 작다는 거겠죠. 그런데 아이템이 추가될수록 슈퍼셋이 아이템이 추가될수록 이 조건을 만족할 수도 있습니다. 비싼 아이템이 추가되면 갑자기 이 조건을 만족할 수도 있겠죠. 그렇기 때문에 이 과거 같은 경우는 안티 모노톤 하지 않다 입니다. 그리고 마지막으로 이 조건은 우리가 지난 시간에 배웠던 A'라인 프라이 프루닉에서 사용했던 조건식에 해당이 됩니다.

그래서 어떠한 아이템셋의 서포트가 윈 서포트보다 크거나 같다. 이것도 결국에는 우리가 지난 시간에 공부했던 것처럼 안티 모노톤에 해당이 됩니다. 두 번째 특성은 모노톤이라는 특성인데요.

모노톤은 안티 모노톤에 반대겠죠. 그런데 왜 안티 모노톤을 먼저 설명을 드렸냐고 하면 사실 안티 모노톤이 더 유용한 특징이기 때문입니다. 어떠한 제약 조건이 모노톤하다 모노톤하다 라는 것은 어떠한 제약조건이, 어떤 아이템셋이 그 제약조건을 만족한다면 그 모든 슈퍼셋도 역시 그 제약조건을 만족한다 라는 것을 배우는 겁니다.

그래서 앞에서 배웠던 안티 모노톤과 반대되는 개념이죠. 그래서 어떤 제약 조건이 모노토닉하다라는 것을 만족하게 되면 어떤 아이템셋이 조건을 만족하면 그 슈퍼셋도 어차피 조건을 만족하니까 그 슈퍼셋에 대해서 제약 조건을 일일이 확인을 하지 않아도 됩니다. 그래서 그 슈퍼셋은 그냥 그 제약 조건을 성립한다라고 그냥 가정을 하고

생략을 진행을 할 수 있습니다. 하지만 이 모노톤은 이제 앞에서 배운 안티 모노톤 보다 덜 유용한데요. 그 이유는 이제 탐색 공간을 제외할 수는 없습니다. 그 이유는 왜 그러냐면 어떠한 아이템셋이 이 조건을 만족합니다. 그러면 그 슈퍼셋도 조건을 만족하죠. 그런데 그 슈퍼셋이 이러한 제약 조건을 만족한다는 이유만으로 무조건 그게 유용한 패턴이라고 판단할 수가

없겠죠. 왜냐하면 그 패턴이 다른 제약 조건이 있을 때 다른 제약 조건을 만족하는지도 다시 검사를 해봐야 되고요. 그리고 서포트 값이 윈서포트를 넘는지도 어차피 우리가 판단을 해야 되겠죠. 그렇기 때문에 앞에 안티 모노토닉 같은 경우에는 어차피 한 개의 제약 조건만 만족하지 않는다면 걔는 이미 탐색할 필요가 없으니까 제외를 했는데

여기서는 어떠한 제약 조건을 만족한다고 하더라도 그것을 탐색해서 우리가 제외할 수는 없습니다 단지 우리가 그 제약 조건을 검사하는 과정만 생략을 할 수 있다는 이런 장점을 우리가 얻을 수 있습니다 그래서 세 가지 예시가 있는데요. 첫 번째 예시로 어떤 총 가격의 합이 V보다 크다는 것은 모노톱입니다.

왜냐하면 아이템이 추가될수록 이 값은 더 커지겠죠. 그러니까 어느 한순간에 만족을 했으면 그 슈퍼셋은 항상 이 조건을 만족을 하니까 모노톤에 해당이 됩니다. 그리고 두번째, 가격의 최소값이 부위보다 작다 입니다. 최소값은 더 작아질 수 있고 더 커질 수는 없죠. 이미 있는 아이템을 뺄 수는 없으니까요. 그렇기 때문에 이것도 어느 한순간에 만족하면

그 뒤에 슈퍼셋도 항상 만족을 하니까 모노톤입니다. 그 다음에는 어떤 이익의 범위가 C목보다 크다 인데요. 범위는 최소값과 최대값의 범위니까 그 범위가 더 커질 수만 있지 더 작아질 수는 없죠. 그렇기 때문에 이것도 모노톤에 해당이 됩니다. *Slow-O-O-O-O-O-O-O-O-O*

그 다음으로는 우리가 앞에 배웠던 것 중에 가장 중요한 성질은 안티 모노톤이었죠. 그래서 어떤 컨스트레인트가 안티 모노톤일 때 이것을 어떻게 활용을 해서 우리가 쿨링을 진행을 해서 탐색 공간을 줄일 수 있는지를 알아보도록 하겠습니다. 그래서 지난 시간에 공부했던 A-Priorate 알고리즘을 그대로 적용을 하면서 거기에 플러스로 컨스트레이트에 대한

푸르니까지 함께 한번 진행을 해보도록 하겠습니다. 그래서 원래 기존에는 이 조건이 하나밖에 없었죠. 서포트가 민서포트보다 크거나 같아야 된다. 이러한 어떤 프리퀀트에 대한 조건 하나만 있었습니다. 그런데 여기에서는 이제 컨스트레이트 기반의 푸드닝을 진행할 거기 때문에 이렇게 안티 모노톤한 제약 조건 하나를 더 추가하도록 하겠습니다.

그래서 총 가격의 합이 5보다 작아야 된다는 조건을 추가하도록 하겠습니다. 그래서 이러한 조건을 만족하는 패턴 방울기가 찾을 겁니다. 이것은 한 번 만족하지 않으면 그 이후에 슈퍼셋도 모두 만족하지 않기 때문에 이제 안티고르톤 하다라고 할 수 있습니다. 먼저 이 두 가지 조건을 통해서 우리가 한번 패턴을 찾아보도록 하겠습니다.

먼저 이렇게 왼쪽과 같은 데이터베이스가 있고요. 이 데이터베이스를 스캔을 해서 먼저 각 아이템에 대한 서포트를 계산을 해줘야겠죠. 그 각 서포트를 계산을 했습니다. 우리가 설정해준 min sub이 2이기 때문에 이 4 같은 경우에는 support가 1 밖에 안되니까 이걸 하나 제외를 해주게 됩니다. 첫번째, 후보에서 우리가 실제로 구한 frequent set에서는

이 4가 포함이 되지 않습니다. 1,2,3,5,4개의 아이템셋만 포함이 되고요. 여기서 우리가 추가적으로 제약조건에 대한 검사도 진행을 해주게 됩니다. 이 O 같은 경우에는 왼쪽에 이 프라이스가 나타나있거든요. 이 프라이스가 이제 아이템의 아이디와 가격이 똑같습니다. 그래서 이 O 같은 경우에는 가격이 오니까 제약조건을 우리가 만족하지 못하죠.

그러니까 이 O를 제거를 할 수 있습니다. 그리고 이 제약조건은 안티 모노톤한 특성을 가지고 있기 때문에요. 이 5가 포함되는 모든 슈퍼셋 또한 우리가 제외를 할 수 있습니다. 그래서 이 위에 있는 F1으로 만들 수 있는 모든 아이템셋의 조합이 이 아래와 같죠? 이렇게 6개의 조합을 만들 수 있는 게

이 중에서 O가 포함되는 건 어차피 제압 조건을 만족하지 않을 거니까 이 세 개를 미리 제거를 이렇게 해줄 수 있습니다. 그럼 여기서 다시 한번 두 번째 레벨에서 스캔을 진행할 때 이 세 개, O가 포함된 세 개는 스캔을 진행을 해줄 필요가 없겠죠. 1,2,1,3,2,3에 해당되는 이 세 개만 스캔을 진행을 해주면 됩니다.

그리고 이 세 개에 대해서 다음에 다시 이 candidate를 구성을 한 다음에 support를 계산을 해주게 되겠죠. 여기서 support를 만족하지 않는 것은 1,2입니다. 그래서 212 첫번째 이 아이템셋은 제거를 해주고요. 나머지 13 그리고 23만 이렇게 포함을 해주게 됩니다. 그런데 여기서 13과 23 중에 23 같은 경우에는 Constraint를 확인을 했을 때 제약조건을 초과를 하게 되죠.

가격이 합이 오니까요. 그렇기 때문에 이것도 미리 제거를 해줄 수가 있습니다. 그럼 여기서 남은 아이템셋은 1, 3만 남게 되죠. 그리고 남은 아이템셋, 밑에 있는 나머지 아이템셋은 어차피 우리가 이걸로 추가적인 아이템셋을 구성을 해도 제약조건을 만족하지 않기 때문에 그냥 푸르닝을 진행을 할 수 있습니다. 그래서 그 다음에 만들 수 있는 아이템셋이 존재하지 않기 때문에 여기서 모든 탐색이 진행이 되게 됩니다.

그래서 미리 이 제약조건을 통해서 프로닝을 진행을 함으로써 훨씬 더 마이닝 과정을 간결하게 간소화시킬 수 있습니다. 마지막 특성인데요. succinctness 라는 그런 특성에 대해서 알아보도록 하겠습니다. 이거는 좀 앞에 배웠던 특성과는 조금 다른 차원의 특성인데요.

이 특성 같은 경우에는 어떠한 제약 조건을 우리가 직접 이 데이터 차원에서 조작을 해서 직접 적용시킬 수 있는 그런 특성을 의미합니다. 그래서 데이터 차원에서 어떤 컨스트레이트를 직접 우리가 적용을 시킬 수 있냐 라는 특성을 의미하고요. 예를 들어서 좀 더 쉽게 이해할 수 있는데요. 어떤 아이템 특정한 아이템 i가 패턴을 포함될 수 있는지 입니다.

특정한 아이템이 포함된 패턴만 찾아라 이런 컨스트레이트가 있을 수 있는데요. 이러한 경우에는 우리가 데이터 베이스에서 그 데이터 베이스에서 트랜잭션을 불러올 때 아이템'I'가 포함된 것만 애초에 프로젝션해서 우리가 가져오면 되겠죠. 그래서 데이터 차원에서 우리가 그 데이터 공간의 범위 자체를 직접 줄일 수 있기 때문에 이러한 예시가 해당이 됩니다.

그래서 이러한 것을 데이터 스페이스 푸르닝이라고 합니다. 두번째 예시도 마찬가지인데요. 아이템 i가 포함되지 않는 패턴만 찾아라 라고 하면은 우리가 데이터베이스에서 i라는 것을 제거하고 이제 나머지만 우리가 가져올 수 있겠죠. i가 포함되지 않는 나머지 것들만 데이터를 가져오면 되기 때문에 역시 이것도 탐색 공간을 줄일 수 있습니다.

그리고 세 번째 예시 같은 경우에는 가격의 최소값이 V보다 작거나 같다 인데요. 이 경우에는 우리가 이 아이템들 중 가격이 최소값보다 작은 것만 쭉 찾습니다. 왜냐하면 최소값이 어쩜 V보다 작아야 되니까 이 값이 우리가 설정해준 V값보다 작은 아이템을 쭉 찾은 다음에

그러한 아이템이 한 개도 포함되지 않는 트랜잭션을 제거를 해서 데이터를 가져올 수가 있습니다. 어차피 그 부위보다 작은 아이템이 포함되지 않는 트랜잭션 같은 경우에는 이 조건에 해당이 될 수가 없기 때문에 데이터 측면에서 그것을 미리 제외를 시킬 수 있습니다. 그래서 이것도 이제 SUG SYNCHRONIST 특성에 해당이 된다 라고 할 수 있습니다. 그리고 마지막 네 번째 예시 같은 경우에는 어떠한 가격의 총합이 V보다 크거나 같다인데요.

사실 이번에는 마이닝을 진행하고 슈퍼셋을 만드는 과정에서 이 합계가 더 커지게 되면서 V보다 커질지 아닐지를 미리 데이터 측면에서 우리가 실제 마이닝을 진행을 해야 이게 만족하는지 아닌지를 알 수 있기 때문에 이것 같은 경우에는 이러한 succinctness의 특징을 만족하지 않습니다.

그래서 마지막으로 이제 우리가 배운 이러한 특성을 한번 기준으로 다양한 크게 두 가지 방식의 푸르닝을 진행할 수 있는데요. 첫 번째는 패턴 스페이스 푸르닝을 할 수 있는 이러한 제약 조건들을 의미하고요. 두 번째는 이러한 제약 조건의 특성에 따라서 데이터 스페이스 푸르닝을 할 수 있는 이런 제약 조건. 이렇게 특성에 따라서 두 가지로 구분할 수 있습니다.

그래서 패턴 스페이스 프로닝이라는 것은 우리가 앞서 했던 것처럼 패턴 마이닝을 진행을 하면서 특정 조건을 만족하지 않는 그러한 패턴들을 미리 제거를 할 수 있는 그러한 것들을 의미하고요. 데이터 스페이스 프로닝은 우리가 방금 전에 공부했던 것처럼 마이닝을 진행하는 과정이 아니라 미리 데이터 분포에서 우리가 탐색 공간을 줄이는 그러한 것들을 해당합니다.

그래서 패턴 스페이스 풀링 제약 조건 같은 경우에는 우리가 공부했던 안티 모노토닉이 여기에 해당이 되겠죠. 그래서 제약조건을 위반하면 그 이후에 슈퍼셋도 검사를 해보지 않아도 되기 때문에 여기에 해당이 되고요. 모노토닉 같은 경우에는 위만큼 큰 효과는 없지만 특정한 제약조건을 검사를 하지 않아도 되니까 여기에 해당이 되고요. Subsygnosis 같은 경우에도 역시 이 Pattern Space Pooling도 우리가 진행을 할 수 있겠죠.

앞으로 나올 패턴도 우리가 한 번에 미리 제거를 사실 해줄 수 있기 때문에 이 특성 같은 경우에는 이 Pattern Space Pooling 그리고 오른쪽에 있는 Data Space Pooling 두 개 다 진행을 해 줄 수 있는 그런 제약 조건에 해당이 됩니다. 데이터 스페이스 같은 경우에는 앞에 했던 데이터 석싱트라는 이러한 특성이 여기에 해당이 되고요. 두 번째는 데이터 안티 모노토닉이라는 특성도 있는데요.

Anti-Monotonic이라는 특성을 확장을 해서요. 어떤 트랜잭션 기반으로 어떤 트랜잭션이 컨스트레인트를 만족하지 않으면 그 트랜잭션이 포함이 된 더 큰 그런 트랜잭션도 그 특성을 만족하지 않기 때문에 그것을 미리 데이터 단위에서 우리가 푸르닝을 진행을 할 수 있습니다. 이렇게 되면 데이터 스페이스에서 푸르닝을 진행을 하는 것이기 때문에

이러한 데이터 Anti-Monotonic 신청도 이러한 제약 조건에 해당이 됩니다. 그럼 오늘 수업은 여기까지 진행하도록 하겠습니다.