데사 중간 정리

- Frequent Pattern Mining

아이템셋 X={x1,...,xk}

X→Y :X와 Y의 합집합에 무조건 frequent pattern 존재

 

Support : transaction이 X를 포함할 확률(빈도)

ㄴ Supmin: X의 frequent 유무를 판단하기 위한 threshold

 

Confidence : X를 포함하는 transaction이 Y도 포함할 확률

ㄴ Confmin : threshold

 

Q1: Find all frequent patterns 

ㄴ 각 알파벳들의 빈도를 세보면 A=3, B=3, C=2, D=4, E=3, F=2, AD=3, AB=1, AC=1, CD=2 ... 이 나온다. (만약에 k개라고 하면 2^k-1개가 나옴...) 여기서 supmin이 50%이므로 2.5개이상인것들만 남기면 답은 {A=3, B=3, D=4, E=3, AD=3}이 나온다.

 

Q2: Find all association rules

ㄴ X → Y (sup XY가 둘다 있는 확률, conf X가 있는데에 Y가 있을확률) 을 구했을때 supmin confmin을 넘기는걸 구하면 된다.

따라서, A →D(60%, 100%), D →A(60%, 75%)가 정답이다.

 

 

 

---

 

Closed pattern X : X를 포함하는 superset Y중에서 X와 support가 같은게 존재 x

Max - Pattern X : X를 포함하는 frequent한 superset Y 존재 x

 

Q1. How many frequent patterns are there? : DB가100개의 원소를 가지고 있으므로 2^100-1개를 가진다.

 

Q2. What is the set of closed patterns? (각각 support도 써라) : <a1,...,a100>의 모든 원소를 가진 패턴이 DB안에 1개밖에 없으므로 support는 1이다. <a1,...,a50>의 패턴은 <a1,...,a100>에도 들어있으므로 support는 2다. 둘다 support같은 다른 셋이 없으므로 closed pattern이다.

 

Q3. What is the set of max-patterns? : <a1,...,a50>은 <a1,...,a100>에도 들어있지만 <a1,..,a100>은 다른 셋에 들어가있지 않으므로 max-pattern이다.

---

frequent한 셋의 모든 subset들은 frequent해야한다.

 

- Apriori : 어떤 집합이 frequent하지 않으면 상위집합도 frequent 안할테니까 제외하기.

스캔해서 supmin보다 작으면 frequent안한거니까 제외 -> 그다음 subset만들어서 계산 -> 더 거를거 없을때까지 반복

이런식으로 다음 subset 만들고 거름

 

 

---

 

- DIC : 만약 A,B가 frequent하다 판단되면 바로 AB도 count하기 시작함 (Apriori는 1- 다 세고 2- 세는 방식이었는데 이건 판단 즉시 그 위에것도 계산함)

- Partition : DB를 k 조각으로 나눔(partition) → 각 조각에서 local frequent pattern을 찾음 (minsup/k보다 크면 frequent하다고 판단) → 최종적으로 전체 DB에서 frequent한지 판단 (전체에서 frequent한건 하나의 partition에서 반드시 frequent, 역은 성립x)

 

- Sampling 

ㄴ simple ver : Sample만 추출해서 그 안에서 frequent pattern 찾음, 더 낮은 문턱값 사용, 단점은 sample안에서 frequent한게 DB전체에서 frequent하지 않을수도.

ㄴ advanced ver : 확인을 위해 2번 더 스캔함

전체 DB 스캔, 기존 문턱값 사용해서 거름 → 전체 DB를 다시한번 스캔해서 빠진 패턴 찾음

 

- DHP : DB스캔할때 다음 크기에 나타날 수 있는 모든 조합을 미리 기록하고 해시함수에 넣어서 해시테이블에 분류함. 해시테이블 특정 bucket에 담긴 숫자가 supmin 아래면 즉시 제외

 

 

---

 

- FP-Growth : local frequent 아이템을 이용해 short-> long pattern 성장. ex) 'a'가 frequent라면, 'a'를 포함하는 모든 transaction DB|a 를 가져옴.만약 'b'가 DB|a 에서 local frequent면, 'ab'는 frequent임. 이 과정을 반복함.

 

DB스캔해서 frequent한것들만 찾음 -> count세서 frequent한 순서대로 정렬한 F-list 만들음 -> 다시 DB스캔해서 F-list로 FP-tree 만들음 (위에 frequent items들을 트리로 만든거랑 비슷, divide-and-conquer 이용함)

정보손실x, frequent한건 share돼서 크기가 줄어들음 

---

 

 

- MaxMiner : frequent한것들을 찾고 오름차순 정렬함 -> 각 조합 뒤에 올 수 있는 가장 긴 패턴을 미리 체크하고 그 패턴이 만약 frequent하다면 하위 subset도 다 frequent하므로 체크할필요 x (set- enumeration tree 만들어서 패턴찾음)

set-enumerate tree 예시

 

 

- CLOSET : FP-growth 하는 중에 재귀적으로 closed pattern만 탐색 

여기서 m이 들어간 패턴들은 fca도 포함하므로 fcam은 frequent closed patten임

 

 

- CHARM : 크기가 (frequent size-1)인 set만 고려해서 DB 한 번만 스캔 (item수<transaction수) -> 수평 데이터를 vertical로 format -> 크기가 k인 set에서 k+1인 frequent itemset 찾음(교집합과 Apriori 이용) -> 더이상 frequent set이 찾아지지 않을때까지 반복

각 set의 frequency == TID list의 길이

 

 

- Mining Multiple-Level Association Rules 

아이템들은 종종 계층구조를 가지고, level이 낮을수록 suppor도 더 낮음. 그리고 상위와 하위 아이템들이 frequent pattern에 속하는것도 비슷함. 

일부 규칙은 ancestor 관계로 중복될 수 있음. -> 만약 자손의 support가 조상의 support로 예상한 값과 가깝고 confidence가 조상것과 가까울때 redundant 함.

X일때 Y일 확률이 Y확률보다 얼마나 올랐는지 측정하는 lift 계산법

 

 

---

 

Accuracy = 올바르게 분류 data 수 / 전체 test data 수

 

- Decision tree

선택된 feature 기준 재귀적 분할, 완벽히 분류됐을때 종료. + 더 나눌 feature가 없을땐 majority voting으로 결정

ㄴ 분류 기준: 불순도가 낮도록 하기

 

- Information Gain (Entropy이용) : 해당 특성으로 분할하기 전후 엔트로피 차를 구해서 가장 엔트로피가 크게 감소한 특성을 선택함.

Gain의 값이 가장 커지는 특성을 기준으로 분할하면 됨

- Gain Ratio (information gain 정규화한 버전)

gain을 splitinfo로 나눠서 정규화함 -> 가능한값이 큰 특징에 편향되는 단점을 커버해줌

 

- Gini index : 불순도 가장 크게 감소한게 test feature로 선택

공식만 살짝 다르고 이전것들과 비슷함

- Overfitting : 너무 branch가 많으면 이상치까지 학습해서 일반화 능력 떨어짐 -> Pruning 필요 

ㄴ Pre-pruning : 기준이 임계점 아래로 떨어지면 더이상 분할 x, 정지.

 Post-pruning : tree를 다 성장시키고 validation set보다 나빠지지 않는 선까지 pruning함

 

- Random Forest 

1. Bootstrap

데이터 개수만큼 진행, 랜덤 위치에 랜덤으로 original에 있는 데이터들 넣음

 

2. Randomly select feature : 전체 feature들 중에서 랜덤으로 feature를 선택해 나눔

3. Aggregation

1: majority voting , 2: weighted voting

-> 결과가 도출된다!

 

---

 

- Ruled-based Classification: 데이터 양 적을때 사용

ㄴ 두개 이상 조건 > 충돌생김, Size(조건 가장 까다로운게 먼저), Class-based (오분류 비용 높은게 먼저), Rule-based (기준에 따라) ordering을 사용함

ㄴ Associative classification : supmin과 confmin을 controll하면서 강한 연관성을 가지는 feature-value pair을 찾을 수 있음. 높은 confmin설정하면 여러 속성 고려한 신뢰도 높은 연관성 탐색 가능, 그러나 설정에 따라 낮은 적용범위를 가질 수 있다.

 

Eager(새 데이터 받기 전에 분류모델 만들음) vs Lazy (데이터 올때까지 학습데이터 그냥 가지고 있으면서 기다림) learning

ㄴ Lazy가 train속도는 빠르지만 predict 하는데 오래걸림

 

- k-Nearest Neighbor : n차원 평면에 있는 data points중에서 결정 공간 안에 있는 data point의 다수결로 결정. + 거리에 따른 가중치 투표도 가능

 

- Confusion matrix

 

- Evaluation Protocols

1. Holdout method : holdout k번 반복

2. Cross-validation(k-fold): 랜덤하게 데이터를 같은 크기의 partition k개로 나누고, i번째 반복에 i번 partition을 test set으로 나머지를 훈련 set으로 씀

3. Leave-one-out: k-fold에서 k가 전체 데이터의 포인트 개수임

4. Stratified cross-validation: 분할된 각 fold내 class 비율이 원본 class 비율과 거의 같아지도록 나눔

 

-Ensemble methods

1. Bagging: 각 반복마다 trainset은 bootstrap처럼 랜덤한 위치에 랜덤한 original data를 넣은거로 만들어짐, 분류모델이 학습함

-> 각 분류기가 majority vote로 class 할당함

2. Boosting: 맨처음에 각 data point에 가중치 1/d 할당 -> 각 반복마다 분류모델 학습하고 test set으로 확인함 -> 가중치 업데이트, 잘못 분류된것에 더 집중함 -> 각 분류기의 vote로 결과냄