7. Association Rules

Frequent Pattern을 추출했으니, 이것을 이용해서 Association Rule들을 만들고 평가해야 한다

 

Association Rules

---

• Mining Multilevel Association
• Mining Multidimensional Association
• Mining Quantitative Assocation
• Mining Interesting Correlation Patterns

 

Mining Multilevel Association Rules

---

Item들은 종종 계층 구조를 형성한다

• 예를 들면, Milk와 2% Milk
  • Milk가 2% Milk의 상위 개념이라고 볼 수 있다
• 각 계층마다 유연하게 Minimum Supoort를 설정해주는 것이 필요하다
  • 계층이 내려갈수록 당연히 Support가 작아질텐데, 이걸 고려해야한다는 주장
  • 낮은 계층의 Item들과, 높은 계층의 Item들이 Frequent Pattern에 포함될 수 있는 확률이 비슷하도록 조정을 해야 한다

 

• Uniform Setting
  • Hierarchy에 상관없이 동일한 min_sup값 적용
  • 지금까지 봐온 방식
• Flexible Setting
  • Low level 일수록 더 낮은 기준 적용

 

Redundancy Filtering

---

계층 구조가 형성되다 보면, 의미없는 Rule이 생성되는 경우가 있다

• Ancestor로 인해서 불필요한 Rule의 중복이 발생할 수 있다

 

• 위의 두 Rule은 비슷한 의미를 갖는다
  • MilK를 구매한 사람이 Wheat Bread를 구매할 확률은 70%
  • 2% Milk를 구매한 사람이 Wheat Bread를 구매할 확률은 72%
• 위의 경우에서 첫번째 Rule이 두번째 Rule의 Ancestor라고 한다

 

그렇다면 어떤 경우에 Rule이 Redundant하다고 판단 할까?

• Support가 Ancestor의 Supoort에 기반한 기대값과 유사할 때
• Confidence가 Ancestor의 Confidence와 유사할 때
• 위의 예시에서 Ancestor Rule의 Support는 8%이고, 두번째 Rule의 Support는 2%로 차이가 꽤난다고 볼 수 있다
• 그런데 기대값을 생각해보면, 마트에 비치되어 있는 전체 Milk 중에 2% Milk가 1/4 정도라면, 비슷한 기대값을 갖는다고 볼 수 있다
  • 2% * 4 = 8%

 

Mining Multi-Dimensional Associations

---

다차원의 속성이 Association Rule을 형성하는 경우

 

Single-Dimensional Rules

 

Multi-Dimensional Rules ( >= 2 Dimensions)

• Inter-Dimension Association Rules (반복되는 Dimension이 없는 경우) 

 

• Hybrid-Dimension Association Rules (반복되는 Dimension이 있는 경우)
  • 위의 예시에서는 buys가 반복

 

Attribute Types

---

Attribute, Feature, Dimension은 모두 같은 말이다

• Categorical Attributes
  • Attribute 값의 범위가 유한하고, 값들 사이에 순서가 없는 경우
  • Ex) Occupation, Buys
• Quantitative Attributes
  • Attribute 값의 도메인이 숫자 이고, 값들 사이에 명시적인 순서가 있는 경우
  • 보통 값이 연속적이기 때문에 Discretization이 필요하다
    • 연속적인 값을 범위로 자르는 것
    • Ex) 키가 150 ~ 155, 155 ~ 160, ... 
  • Ex) Age, Height, Weight

 

Quantitative Association Rules

---

정량적인 Association Rules

• Numeric한 Attributes들은 Discretize된다고 했다
• Association Rule의 틀은 다음과 같다 A_quan ^ A_quan => A_categorical
• 정량적인 값들이 모여서 범주적인 값을 결정
• 우리는 조금 더 일반적인 Rule을 생성하기 위해서 인접한 Rule끼리 클러스터링 을 하기도 한다

 

예시

• min_sup, min_conf를 만족하는 셀을 체크한다
• age(X, "34-35") ^ income(X, "30-50K") => buys(X, "high resolution TV")
• Cluster의 장점은 비슷한 Rule들을 모아서 Universal Rule을 만듦으로써 Rule의 수를 줄여준다

 

 

From Association Mining to Correlation Analysis

---

Association Rule이 의미가 있는지를 분석해야 한다

• 위와 같은 Rule이 있을 때, 오 농구를 하는 학생들은 시리얼을 먹는 경향이 있구나! 라고 잘못된 분석을 하게 된다
• 애초에 시리얼을 먹는 학생의 비율이 75%라고 한다면, 위의 Rule은 의미없는 Rule이다
• 66.7%라는 Confidence는 꽤나 높아보이기 때문에 의미있는 Rule로 생각될 수 있지만, 원래 시리얼을 먹는 비율보다 작기 때문에 의미없는 Rule이다

 

• 오히려 이렇게 되어야 의미있는 Rule이 된다
• 무조건 Support와 Confidence가 높다고 의미있는 Rule이 아니라는 것을 보여준다
• 33.3% > 25% 이기 때문에, 농구를 하는 학생들은 시리얼을 먹지 않는 경향을 보이는구나 라고 해석이 가능하다

 

Support & Confidence를 사용하는 Framework의 한계이다
=> Rule만 보고서는 Positive Correlation을 갖는지 파악하기가 어렵다

 

Lift

---

Rule의 Interestingness를 측정하는 방법

• lift값이 1보다 작으면 General trend에 비해 Negative Correlation을 갖는다는 뜻
  • lift(Basketball, Cereal) = 0.89 이므로 Negative Correlation을 갖는다
  • lift(Basketball, Not Cereal) = 1.33 이므로 Positive Correlation을 갖는다

 

정리

---

지금까지의 내용 정리

• Frequent Pattern & Association Rule Mininng은 데이터 마이닝에서 중요한 작업이다
• Pattern의 수가 너무 많아지지 않게 Scalable Frequent Pattern Mining을 하는 방법이 필요하다
  • Apriori
  • FP-growth
  • Miner Improvements
    • DIC, Partition, Sampling, MaxMiner, CHARM, ...
• 다양한 방식으로 Rule들을 마이닝할 수 있다
  • Hierarchy and Multi-attribute Settings, Lift, ...