파고파고

데이터베이스에서 여러 패턴들을 mining하는 방법을 배웠다. 하지만, 방대한 크기의 데이터에서 모든 패턴을 찾는 것은 비현실적이다. data mining은 interactive해야 하는데, 이는 즉 사용자가 무엇을 mining할지를 결정해야 한다는 소리다. 그런 의미에서, Constraint-Based Mining은 '무엇을 mining 할 것인지에 대해 제약(constraints)조건을 제공'해야 하는 것에 기안한다. Constraint-Based Mining은, 효율적인 mining을 위한 constraints를 찾는 것을 의미한다. 데이터마이닝에서의 제약(Constraints) 여러가지가 있지만, Data Contraint는 SQL과 같은 쿼리(quries)문제로 생각하면 된다. 가령, '시카고'..

Frequent pattern을 넘어서, Association Rule을 Mining하는 여러 기법들을 알아보자. Mining Multi-Level Association Rules: Redundancy Filtering Item의 계층적 성질 multilevel association은, item들이 종종 계층적 (hierarchical) 이라는 점에서 기안한다. 예시를 보자. milk, 2%milk, skim milk가 item으로 있다고 하자. skim milk와 2% milk가 milk에 포함되어, lower level의 우유에 해당하는 support가 상위 레벨보다 적을 것을 예상할 수 있다. 따라서 세 item의 Min_sup을 동일하게 5%로 부여하는 것은 올바르지 않고, 아래 레벨의 item들..

지금까지 소개한 방법들은 데이터를 horizontal format으로 읽어 frequent pattern 등을 찾았다. CHARM은, 데이터를 vertical format으로 읽어 frequent pattern을 찾는 방법이다. Vertical Format 먼저 어떤 것이 Vertical Format인지 이해해보자. 우리에게 익숙한 format은 각 행이 transaction 하나하나, 행을 구성하는 열이 transaction ID와 해당 transaction ID에 속한 itemset이다. Vertical Fomat은, 각 행이 item 하나하나, 행을 구성하는 열에는 item의 ID와 해당 item을 포함하고 있는 transaction ID의 집합이 저장되어 있다. 예를 들면 이런 형식일 것이다. i..

Mining Max-Pattern: MaxMiner MaxMiner는 이름 그대로 max-pattern을 추출하는 기법이다. (* max-pattern은 자신의 super-pattern 중 frequent한 것이 없는 frequent pattern을 의미한다.) MaxMiner은 Apriori를 기반으로 한다. 기억해야 할 것은, MaxMiner의 경우 max-pattern을 찾는 것만 할 수 있으며, 모든 frequent pattern을 찾는 것은 할 수 없다는 점이다. MaxMiner의 작동방식을 살펴보자. 1. 길이 하나짜리 frequent item을 찾고, frequent ascending order로 정렬한다. (1st scan) 2. 1에서 찾은 frequent item을 조합해 길이 두개짜리..

Candidate Generation 과정 없이 Frequent Pattern을 추출해낼 수 있는 방법이 FP-Growth라고 했다. local frequent pattern item을 사용하여 짧은 패턴부터 시작해, 패턴을 늘려가는 것이 FP(frequent pattern)-growth다. Construct FP-Tree from Database FP-Growth를 이해하기 전에, FP-Tree를 만드는 방법을 먼저 알아보자. 1. single item pattern 찾기 우선, DB를 스캔해 길이가 1짜리인 item pattern을 찾는다. 아래 그림에서 frequent items의 요소 하나 하나가, 길이 1짜리 item pattern이다. 2. F-list 만들기 찾은 frequent patter..

db scan의 횟수와 candidate의 수가 많다는 점에서 apriori의 효율이 떨어진다는 것을 이야기했었다. 여기서는 이러한 apriori의 한계점을 개선하기 위한 frequent pattern mining의 여러 방법을 포스팅할 것이다. 1. DIC: Reducing the Number of Scans DIC(Dynamic Itemset Counting)는 DB에 접근하는 횟수를 줄이는 방법이다. 기존 apriori는 길이가 1짜리인 itemset 각각의 수를 모두 count 하는 것을 끝낸 후, 길이 2짜리 itemset 수를 count 했다. 반면, DIC는 itemset의 support를 계산하는 와중, frequent하다는 것이 판단되면 (minimum support를 넘는 순간), 그 ..

[ Downward Closure Property ] 어떤 itemset이 frequent하다면, 그 모든 subset들이 무조건 frequent하다는 것을 의미한다. 예를 들어, {beer, diaper, nuts}가 frequent하다는 결론이 나면, 그 subset인 {beer, diaper}은 당연히 frequent하다는 규칙으로 이해하면 되겠다. * 그 대우도 성립하는 것을 확인할 수 있다. (subset이 frequent하지 않으면, 그 super-set도 frequent할 수 없다.) 이전에 포스팅했던 내용이다. Apriori 알고리즘은, 이러한 규칙을 기반으로 frequent 패턴을 추출하는 알고리즘으로 이해하면 되겠다. [ Apriori Pruning Principle ] infreque..