[데이터 마이닝 3] 마이닝 관련 알고리즘

ㅇ Frequent Pattern 

   - 말그대로 자주 발생하는 패턴

  - 왜 중요할까 ?

    - 데이터 셋에서 본질적이고 중요한 특성을 나타낸다.

 

ㅇ 기본 개념

X -> Y의 룰에 대한 Support와 Confidence에 대해 알아보자.

Support : 경우의 확률이라고 보면 될듯하다. 예를 들어 X를 사면 Y도 산다라는 룰을 생각해보자. 그럼 이 룰에 대한 서포트는 데이터 모든 경우에서 X를 사고 Y를 산 확률을 의미한다. 다시 말해서 Support가 높다는 말은 빈도가 많으니 발생 확률이 높다는 이야기가 될 것이다.

Confidence : 신뢰도라고 볼 수 있을 듯 하다, X를 산 경우를 전체 집합이라 하고, X->Y를 산 경우의 확률이 컨피던스이다. 즉 이 룰이 맞을 확률? 정확도라고 볼 수 있겟다.

ㅇ Apriori Algorithm

이 그림을 보고 모르면 혼자 공부좀 해야죠.. 그냥 그림으로 떙칩시다.

Apriori 알고리즘에서 사용하는 규칙

※ 자주 나오는 아이템 셋의 서브셋은 당연히 서브셋 또한 자주 발생한다

{맥주, 기저귀, 땅콩 } 이 아이템 셋이 자주 발생한다면, {맥주, 기저귀} 또한 자주 발생한다는 얘기

-> 예제 가지고 태클 걸지 말자.ㅋㅋㅋㅋㅋ 좀 웃긴 얘기지만 어떤 이마트 매장에서 맥주와 기저귀, 땅콩을 산 사람이 많다면 맥주와 기저귀를 함께 산 사람도 많다는 얘기다. 맥주와 기저귀를 왜 함께 사나라고 생각하지말구   요점에 초점을 맞추자.ㅋㅋㅋㅋ

이 걸 반대로 생각하면 어떤 집합이 자주 발생하지 않는 다면 그것을 포함하는 슈퍼셋 또한 자주 발생하지 않는다. 따라서 위의 그림을 보면 min Support를 2로 두고 예제를 수행하였으므로 D 같은 경우 처음 과정에서 서포트가 1이므로 다음 과정에서 D를 포함하는 어떤 서브셋도 1이상이 나올 수 없기 때문에 고려할 필요가 없으므로 연산 과정에서 제거 된다. 

위의 그림은 서브셋의 계산시 불필요한 계산을 하지 않는 방법에 대한 설명을 나타내고 있다.

{AD}가 자주 발생하는지 검색을 하기 위해서는 {A},{D} 둘다 자주 발생해야한다는 조건이 필요하다. 만약 둘 중 하나라도 자주 발생하지 않는다면 {AD} 도 자주 발생하지 않기 때문에, 아예 계산 할 필요가 없다.

위의 그림은 실제 구현시에 사용하면 매우 좋을 듯 하다. 머리는 좀 아프겄다.

ㅇ FP- Tree

FP 트리는 Apriori 알고리즘 보다 빠른 알고리즘이다.

위의 그림은 FP 트리의 방법을 설명한 것이다. 먼저 위에 테이블은 실제 DB에 잇는 데이터라고 하자. 가장 우측에 있는 Frequent items은 header table를 만든 후에 적용된다. 헤더 테이블은 먼저 데이터베이스를 스캔해서 각 아이템마다의 발생빈도를 카운팅 하고 정해진 min-support =3 보다 작은 데이터는 삭제한 뒤에 다시 디비를 스캔하면서 자주 발생하는 아이템만을 추가해서 가장 우측 frequent items 속성에 쓴다.

물론 정렬 작업도 해야한다. 헤더 테이블을 만들때 말이다.

자 그럼 이제 준비를 마추었으니. 트리를 만들어보자. 먼저 TID가 100인 데이터를 보자 {f,c,a,m,p} 데이터가 있다. 이는 보면 알겠지만 원 데이터와 다르다. 헤더 테이블에 존재하는 아이템만 뽑았으며, 또한 발생빈도에 의해 정렬까지 되어 있는 상태이다. 그럼 이제 트리를 만든다. f가 나왔는데 현재는 트리 형태가 없으니까 일단 f노드를 만들고 1이라고 카운팅 한다. 그리고 c가 있으니까 f 밑에 c노드를 달고, 다시 1로 카운팅, -> a 노드 또한 없으므로 생성 후 1 카운팅, m도 없으니까 1카운팅, p도 없으니까 m 밑에 노드 만들고 1 카운팅한다. 이때 각각 노드를 만들때 헤더 테이블에 head 포인터가 비어있는 경우에는 노드 생성하고 노드의 주소를 쓴다. 

두번째 TID 200인 경우를 시작하자, {f,c,a,b,m}도 역시 같은  방법으로 한다. 헤더 테이블의 head값이 이전에 만들어 놓은 주소를 가지고 있다. 그래서 일단 따라가자 f가 있다 그래서 카운팅해서 2로 만든다. c가 f밑에 달려있다. 따라서 카운팅해서 2, a도 c 밑에 잇으므로 카운팅해서 2, b는 없으므로 새로 만들고 헤더 테이블에 주소를 쓴다. m은 b 밑에 없으므로 만들어야 하는데 헤더 테이블에 주소가 있다. 따라서 먼저 노드를 생성 후 헤드 주소 따라가서 next 포인터에 새로 만든 노드의 주소를 쓴다. 이런식으로 만들면 위의 그림과 같이 fp트리가 생성될 것이다.

- 정리하자면

  1. DB를 스캔하면서 헤더 테이블을 생성 (각 아이템의 발생 빈도를 카운팅)

  2. 헤더 테이블 정렬-> min-Support 만족하지 않은 데이터 삭제

  3. DB를 스캔하면서 헤더 테이블에 있는 아이템만 순서적으로 새로운 속성값이 쓰기.

  4. fp 트리 생성

    4.1 노드가 없는 경우 생성

       - 헤더에 주소가 있는 경우 따라가서 마지막에 새로 생성된 노드의 주소 쓰기

       - 헤더에 주소가 없는 경우 새로 생성된 노드의 주소 쓰기

  

FP 트리의 특성

  - 그림을 잘 보면 알수 있다. 헤더 테이블의 헤드를 따라가면서 카운팅 하면 해당 아이템의 support를 알 수 있고 상위 노드부터 원하는 노드까지 따라갓을때 그 마지막 노드의 카운팅 값이 따라온 경로의 집합인 서포트이다.

 예) F(4)->C(3)       : 이 경우에는 fc의 서포트는 즉 3이란 얘기 

 예2) p(2)->p(1)      : 이 경우는 p의 헤드를 따라 간 경우로 p의 서포트는 2+1=3 이다.

또한 이외에도 많은 특성이 숨어 있을 듯 하다. 각자 찾아보자.

위의 그림을 보면서 점선을 따라가면 옆에 테이블이 무엇을 의미하는지 알 수 있을 것이다.

이 그림도 상당히 좋은 그림인듯 하다. m이 주어졌을 때 자주 발생하는 패턴을 뽑는 방법에 대해 그림으로 설명한다. 즉 m에서 나오는 위로 올라가면 f를 만난다. m(2)와 m(1)이 있는데, f는 두 m에서 시작해도 항상 만나기 때문에 fm은 당연히 3일 것이다. 이와 값이 fp트리를 만들면 자주 발생하는 서브셋 또한 찾기 쉬울 것 같다.

ㅇ Max-pattern

- 이 것은 중요한 개념인듯하다. Max pattern이 min- support보다 크다면 그거의 부분집합은 당연히 min-support보다 클 것이다. 따라서 계산량을 줄이는 개념으로 사용할 수 있을 것 같다. 

위의 그림은 max pattern과 closed pattern을 한눈에 볼 수 있도록 그려진 그림이다. 사실 closed 잘 이해가 되지 않았는데 이 그림을 보니까 알겠다. 위에 그림에서 파란색이 closed pattern인데, 잘 보면 closed pattern의 경우 자신을 포함하는 상위 집합 중에 자신보다 크거나 같은 support가 없는 경우에만 파란색인 것을 알 수 있다. 즉 이러한 조건이 closed pattern의 정의 인듯하다.

nAn itemset X is closed if X is frequent and there exists no super-pattern Y כ X, with the same support as X (proposed by Pasquier, et al. @ ICDT’99) 

이렇게 나와 있는데, 이 의미를 이해하지 못했는데 그림을 보니 정확히 알 듯하다. 다시 설명하자면 어떤 아이템셋 X가 자주 발생하며, X를 포함 하는 슈퍼셋 중에서 X와 같은 서포트를 갖는 슈퍼셋이 존재하지 않으면 X는 Closed 패턴이다.  -> 집합과 부분 집합의 특성에서 상위 집합은 당연히 부분집합의 빈도수 보다 클 수는 없고, 가장 큰 수가 같은 수이기 때문에 같다라고 표현한 듯 하다.

 

본 게시물이 도움이 되었다면, 꾸~욱~ 눌러주세요.

포스팅 하는데 많은 힘이 됩니다~~~