Closed Patterns and Max-Patterns

- An itemset X is closed frequent if X is frequent and there exists no super pattern Y ⊃ X, with the same support as X

 

- An itemset X is a max frequent if X is frequent and there exists no frequent super patter Y ⊃ X​

 

- 아래의 표를 바탕으로 생성가능한 itemset 을 표현해보면 1-itemset 부터 5-itemset 까지 만들 수 있다. Total item set의 크기: 2^5-1

   minsup = 2 로 설정하여 그래프를 그려보면 아래와 같다. 

 

    

 

 

 

 

 

 

 

- 위의 node 에서 빨간색으로 표현된 숫자는 Tid 를 나타낸다. 즉, {A} 는 Tid 1, 2, 4 에 포함되고, {A,C,D} 는 Tid 2, 4 에서 관찰된다.

  

- closed patterns 과 maximal patterns 를 찾기위해서는 먼저 frequent patterns 을 먼저 알아야한다.

minsup = 2 이므로 , {A}, {B}, {C}, {D}, {E}, {A,B}, {A,C}, {A,D}, {B,C} {C,D}, {C,E}. {D,E}, {A,B,C}, {A,C,D} 이 frequent pattern 이 된다.

 

closed frequent pattern 은 frequent pattern 이면서 해당 itemset 의 support 와 같은 support 를 가지면서 포함하는 itemset 이 없어야한다.

한글로 풀이한 해석이 좀 어지럽지만, 풀어서 설명하자면 {A} =3 는 {A,C} 가 support 3을 가지면서 {A}를 포함하고 있기 때문에 closed frequent pattern 이 될 수 없고 {C}=4 의 경우, {B,C} 가 {C}를 포함하지만 그 support 가 3 이므로 closed frequent pattern 이 될 수 있다.

  =>  {C},{D},{E},{A,C},{B,C},{C,E},{D,C},{A,B,C}, {A,C, D}

 

maximal frequent pattern 은 closed frequent pattern 중에서 itemset을 포함하는 frequent super itemset 이 없어야 하는데, {C} 는 {C,E}에 {D} 는 {D,E}에 포함되므로 maximal frequent pattern 의 자격을 갖춘 itemset은 {C,E}, {D,E}, {A,B,C}, {A,C,D} 이다.

 

ex) itemset 의 관계를 아래와 같다.