분류 (Classification) 2014년 가을학기 강원대학교 컴퓨터과학전공 문양세

의사결정 트리 (Decision Trees) 규칙기반 분류기 (Rule-Based Classifiers) 강의 내용 Classification 분류 정의와 적용사례 의사결정 트리 (Decision Trees) 규칙기반 분류기 (Rule-Based Classifiers) 인접 이웃 분류기 (Nearest Neighbor Classifiers) 베이지안 분류기 (Bayesian Classifiers) 인공 신경망 (Artificial Neural Networks) 지지도 벡터 머신 (Support Vector Machines)

분류 (Classification) 주어진 훈련 집합(training set, 레코드의 집합)에 대해서, 각 레코드는 속성들의 집합으로 구성되어 있으며, 이중 하나는 클래스이다. 속성들의 값을 입력으로, 클래스를 출력으로 하는 함수(모델)을 찾는 작업이 분류이다. 분류의 목표는 클래스가 결정되지 않은 레코드에 대해서, 가능한 정확하게 클래스를 부여하는 것이다. 시험 집합(test set)은 찾아낸 모델에 대한 정확도를 결정하는 역할을 한다.

척추동물 데이터 집합 Classification 클래스 속성 (타겟 속성) 입력 속성

분류 작업의 도식화 Classification

분류 모델의 평가 Classification 클래스 문제를 위한 혼동 행렬 (confusion matrix) 정확도와 오류율

분류 작업의 예제 (1/2) 종양 세포(tumor cells)가 양성인지 음성(악성)인지를 판별한다. Classification 종양 세포(tumor cells)가 양성인지 음성(악성)인지를 판별한다. 신용카드 트랜잭션이 정상인지 사기인지 구분한다.

분류 작업의 예제 (2/2) Classification 단백질(protein)의 2차 구조가 alpha-helix인지, beta-sheet인지, random coil인지 분류한다. 신문 기사를 경제, 날씨, 연예, 스포츠 등으로 구분한다.

분류 기술의 종류 의사결정 트리 (Decision Trees) 규칙기반 분류기 (Rule-based Classifiers) Classification 의사결정 트리 (Decision Trees) 규칙기반 분류기 (Rule-based Classifiers) 인접 이웃 분류기 (Nearest Neighbor Classifiers) 베이지안 분류기 (Bayesian Classifiers) 인공 신경망 (Artificial Neural Networks) 지지도 벡터 머신 (SVM: Support Vector Machines)

의사결정 트리 (Decision Trees) 규칙기반 분류기 (Rule-Based Classifiers) 강의 내용 Classification 분류 정의와 적용사례 의사결정 트리 (Decision Trees) 규칙기반 분류기 (Rule-Based Classifiers) 인접 이웃 분류기 (Nearest Neighbor Classifiers) 베이지안 분류기 (Bayesian Classifiers) 인공 신경망 (Artificial Neural Networks) 지지도 벡터 머신 (Support Vector Machines)

의사결정 트리의 예제 Classification

의사결정 트리의 다른 예제 Classification

의사결정 트리의 분류 작업 Classification

모델을 시험 데이터에 적용 (1/6) Classification

모델을 시험 데이터에 적용 (2/6) Classification

모델을 시험 데이터에 적용 (3/6) Classification

모델을 시험 데이터에 적용 (4/6) Classification

모델을 시험 데이터에 적용 (5/6) Classification

모델을 시험 데이터에 적용 (6/6) Classification

의사결정 트리의 분류 작업 Classification

의사결정 트리 구축 방법 헌트 알고리즘 (Hunt Algorithm)  현존하는 대부분 알고리즘의 기초 CART Classification 헌트 알고리즘 (Hunt Algorithm)  현존하는 대부분 알고리즘의 기초 CART ID3, C4.5 SLIQ, SPRINT ...

헌트 알고리즘의 일반적 구조 Dt를 노드 t와 연관된 훈련 레코드 집합이라 하자. 일반적 프로시져 Classification Dt를 노드 t와 연관된 훈련 레코드 집합이라 하자. 일반적 프로시져 Dt의 모든 레코드가 동일한 클래스 yt에 속한다면 노드 t는 yt로 레이블된 단말 노드가 된다. Dt가 공집합이라면, 노드 t는 디폴트 클래스(= yd)로 레이블 된다. Dt가 두 개 이상의 클래스를 포함한다면, Dt를 부분집합들로 분할하기 위하여 속성 시험(attribute test)을 사용한다. 분할된 부분집합들에 대해서 상기 과정을 재귀적(recursively)으로 적용한다.

헌트 알고리즘 Classification

트리 구축(귀납) – Tree Induction Classification 탐욕적 접근법 (Greedy Strategy) 특정 기준(certain criterion)에 최적인 속성 시험(attribute test)에 기반하여 훈련 레코드들을 분할한다. 쉽게 말해, 특정 기준에 가장 부하는 속성을 분할 기준으로 선택하는 것이다. [주요 이슈] 레코드들을 어떻게 분할할 것인가? 속성 시험 조건(attribute test condition)을 어떻게 지정할 것인가? 최선의 분할(best split)은 어떻게 결정할 것인가? 분할을 언제 멈출 것인가?

속성 시험 조건을 어떻게 표현하나? 속성의 종류에 따라 다름 분할 개수에 따라 다름 명목형 (Nominal) Classification 속성의 종류에 따라 다름 명목형 (Nominal) 서열형 (Ordinal) 연속형 (Continuous) 분할 개수에 따라 다름 이진 분할 (Binary split) 다중 분할 (Multi-way split)

명목형 속성에 기반한 분할 다중 분할: 각기 다른 속성 값을 사용하여 가능한 많은 파티션으로 분할한다. Classification 다중 분할: 각기 다른 속성 값을 사용하여 가능한 많은 파티션으로 분할한다. 이진 분할: 속성 값을 두 개의 부분집합으로 분할한다. (최적 파티셔닝이 필요함)

서열형 속성에 기반한 분할 다중 분할: 각기 다른 속성 값을 사용하여 가능한 많은 파티션으로 분할한다. Classification 다중 분할: 각기 다른 속성 값을 사용하여 가능한 많은 파티션으로 분할한다. 이진 분할: 속성 값을 두 개의 부분집합으로 분할한다. (최적 파티셔닝이 필요함) 그런데… 오른쪽 분할은 어떤가?

연속형 속성에 기반한 분할 (1/2) 연속형 속성을 처리하는 두 가지 방법 Classification 연속형 속성을 처리하는 두 가지 방법 서열형 속성이 되도록 이산화(discretization)를 적용함 정적 방법: 시작 시점에 이산화를 한번만 적용한다. 동적 방법: 분할이 필요할 때 마다, 동일 너비, 동일 빈도, 클러스터링 등으로 이산화를 적용한다. 이진 결정(binary decision): (A < v) or (A  v) 모든 가능한 분할을 고려하고, 이중 최선의 분할을 찾는다. 아주 많은 계산을 필요로 한다.

연속형 속성에 기반한 분할 (2/2) Classification

트리 구축(귀납) – Tree Induction Classification 탐욕적 접근법 (Greedy Strategy) 특정 기준(certain criterion)에 최적인 속성 시험(attribute test)에 기반하여 훈련 레코드들을 분할한다. 쉽게 말해, 특정 기준에 가장 부하는 속성을 분할 기준으로 선택하는 것이다. [주요 이슈] 레코드들을 어떻게 분할할 것인가? 속성 시험 조건(attribute test condition)을 어떻게 지정할 것인가? 최선의 분할(best split)은 어떻게 결정할 것인가? 분할을 언제 멈출 것인가?

최선의 분할을 어떻게 할 것인가? (1/3) Classification 첫 번째의 “Own Car”를 사용하는 경우보다 두 번째의 “Car Type”을 사용하는 경우가 보다 순도(purity)가 높은 분할이다! 분할을 위해서 불순도(impurity) 혹은 불순 척도(impurity measure) 개념을 도입하고, 이 불순도를 낮추는 방향으로 분할을 시도한다.

최선의 분할을 어떻게 할 것인가? (2/3) 탐욕적 접근법 Classification 탐욕적 접근법 각 노드는 동종 클래스(homogeneous class) 분포가 되도록 분할한다. 노드의 불순도를 측정할 필요가 있다.

최선의 분할을 어떻게 할 것인가? (3/3) 노드에서 클래스 비율을 나타내는 척도 p(i|t) 오른 예에서, Classification 노드에서 클래스 비율을 나타내는 척도 p(i|t) 노드 t에서 클래스 i를 갖는 레코드들의 비율(분수)을 나타낸다. 두 클래스 0, 1로 구성된 경우라면, p(1|t) = 1 – p(0|t)가 성립한다. 간략히 pi로 나타내기도 한다. 오른 예에서, 분할 전 클래스 분포는 (0.5,0.5)이고 Own Car로 분할 시 (0.6,0.4)와 (0.4,0.6)이며, Car Type으로 분할 시 (0.25,0.75), (1,0), (1/8,7/8)이다.  결국, 각 노드에서 클래스 분포가 편중(skewed)이 되도록 분할하는 것이 좋은 분할방법이다.

불순 척도(Impurity Measure)의 종류 (1/2) Classification 앗! 이게 뭐지? 결국, 클래스 분류가 잘 된 경우(특정 클래스에 편중된 경우)에는 불순도가 작아지고, 잘되지 않은 경우(클래스가 고르게 분포된 경우)에는 불순도가 커진다.  다음 장의 그래프 참조

불순 척도(Impurity Measure)의 종류 (2/2) Classification 특정 클래스의 비율(p)이 아주 작거나 높을 경우엔 불순도가 낮아지나, (이진 분류에서) 0.5에 가까운 경우에는 불순도가 높아진다.

정보 이득 (Information Gain) (1/2) Classification 시험 조건이 얼마나 잘 수행되었는가?  정보 이득 “분할 전 부모 노드의 불순도”와 “분할 후 자식노드들의 불순도”의 차이 정보 이득을 최대화 하는 방향으로 노드를 분할한다.

정보 이득 (Information Gain) (2/2) Classification

트리 구축(귀납) – Tree Induction Classification 탐욕적 접근법 (Greedy Strategy) 특정 기준(certain criterion)에 최적인 속성 시험(attribute test)에 기반하여 훈련 레코드들을 분할한다. 쉽게 말해, 특정 기준에 가장 부하는 속성을 분할 기준으로 선택하는 것이다. [주요 이슈] 레코드들을 어떻게 분할할 것인가? 속성 시험 조건(attribute test condition)을 어떻게 지정할 것인가? 최선의 분할(best split)은 어떻게 결정할 것인가?  GINI 분할을 언제 멈출 것인가?

Gini Index 정의 Classification

Gini 계산 예제 Classification

Gini 기반의 분할 Classification

Gini – 이진 속성의 분할 Classification

Gini – 명목형 속성의 분할 Classification

Gini – 연속형 속성의 분할 (1/2) Classification

Gini – 연속형 속성의 분할 (2/2) Classification

트리 구축(귀납) – Tree Induction Classification 탐욕적 접근법 (Greedy Strategy) 특정 기준(certain criterion)에 최적인 속성 시험(attribute test)에 기반하여 훈련 레코드들을 분할한다. 쉽게 말해, 특정 기준에 가장 부하는 속성을 분할 기준으로 선택하는 것이다. [주요 이슈] 레코드들을 어떻게 분할할 것인가? 속성 시험 조건(attribute test condition)을 어떻게 지정할 것인가? 최선의 분할(best split)은 어떻게 결정할 것인가?  Entropy 분할을 언제 멈출 것인가?

Entropy 정의 Classification

Entropy 계산의 예제 Classification

Entropy 기반 분할 Classification

트리 구축(귀납) – Tree Induction Classification 탐욕적 접근법 (Greedy Strategy) 특정 기준(certain criterion)에 최적인 속성 시험(attribute test)에 기반하여 훈련 레코드들을 분할한다. 쉽게 말해, 특정 기준에 가장 부하는 속성을 분할 기준으로 선택하는 것이다. [주요 이슈] 레코드들을 어떻게 분할할 것인가? 속성 시험 조건(attribute test condition)을 어떻게 지정할 것인가? 최선의 분할(best split)은 어떻게 결정할 것인가?  분류 오류 (Misclassification Error) 분할을 언제 멈출 것인가?

분류 에러(Classification Error) 정의

분류 에러의 예제 Classification

트리 구축(귀납) – Tree Induction Classification 탐욕적 접근법 (Greedy Strategy) 특정 기준(certain criterion)에 최적인 속성 시험(attribute test)에 기반하여 훈련 레코드들을 분할한다. 쉽게 말해, 특정 기준에 가장 부하는 속성을 분할 기준으로 선택하는 것이다. [주요 이슈] 레코드들을 어떻게 분할할 것인가? 속성 시험 조건(attribute test condition)을 어떻게 지정할 것인가? 최선의 분할(best split)은 어떻게 결정할 것인가? 분할을 언제 멈출 것인가?

트리 구축의 중단 시점? 노드에 속하는 모든 레코드들이 동일한 클래스를 갖는다면, 더 이상 분할하지 않고 멈춘다. Classification 노드에 속하는 모든 레코드들이 동일한 클래스를 갖는다면, 더 이상 분할하지 않고 멈춘다. 노드에 속하는 모든 레코드들이 동일한(유사한) 속성 값을 갖는다면, 더 이상 분할하지 않고 멈춘다. 노드의 레코드 수가 임계치 이하로 떨어지면 분할을 멈춘다. 미리 멈춤(early termination)?

의사결정 트리 기반 분류의 장점 Classification

의사기반 트리 분류의 예제: C4.5 Classification

의사결정 트리의 주요 이슈들 Overfitting (과잉적합) Missing Values (누락 값) Classification Overfitting (과잉적합) (일반적으로) 트리가 너무 크고 자세하게 형성되어, 오히려 정확도가 떨어지는 문제 훈련집합에 과잉적합하게 생성되다 보니, 테스트 집합이나 실제 분류되지 않은 데이터에 대해서는 큰 에러가 발생하는 문제 Missing Values (누락 값) 누락 값이 있는 경우, 부정확한 트리가 구축됨 Costs of Classification (분류 비용) 대용량 데이터 집합, 고차원 데이터, 복잡한 데이터의 경우, 분류에 많은 시간이 걸림 정확도 높은 의사결정 트리를 생성하기 위해서 많은 비용이 요구됨

Overfitting의 예제 Classification 가우시안 분포(o)와 균일 분포(+)로 생성된 데이터 집합에서 일부는 훈련집합으로 선택하고, 일부는 시험 집합으로 선택하였다.

Overfitting의 예제 공간(속성 값)을 계속 분할할 수록 훈련집합에 대한 분류 에러는 줄어든다. Classification 공간(속성 값)을 계속 분할할 수록 훈련집합에 대한 분류 에러는 줄어든다. 반면에, 트리가 너무 세분화 되어 분할되었기 때문에, 시험 집합을 적용했을 경우는 특정 시점부터는 오히려 분류 에러가 증가한다.

노이즈에 의한 Overfitting 예제 Classification

Overfitting의 고찰 Overfitting 은 의사결정 트리가 불필요하게 복잡하게 하는 결과를 낳는다. Classification Overfitting 은 의사결정 트리가 불필요하게 복잡하게 하는 결과를 낳는다. 훈련 오류(training error)의 최소화가 가장 좋은 의사결정 트리를 생성하지는 않는다.  어떻게 하면 Overfitting을 해결할 것인가?

Overfitting 문제의 해결 (1/2) Classification Pre-Pruning (Early Stopping Rule): 트리를 생성하는 중간 과정에서 가지치기 수행

Overfitting 문제의 해결 (2/2) Classification Post-Pruning (Early Stopping Rule): 완전한 트리를 생성한 후에 가지치기 수행 Overfitting 등의 추가적 기술적 이슈에 대한 내용은 생략

의사결정 트리 (Decision Trees) 규칙기반 분류기 (Rule-Based Classifiers) 강의 내용 Classification 분류 정의와 적용사례 의사결정 트리 (Decision Trees) 규칙기반 분류기 (Rule-Based Classifiers) 인접 이웃 분류기 (Nearest Neighbor Classifiers) 베이지안 분류기 (Bayesian Classifiers) 인공 신경망 (Artificial Neural Networks) 지지도 벡터 머신 (Support Vector Machines)

규칙기반 분류기 (Rule-Based Classifier) Classification

규칙기반 분류기 예제 Classification

규칙기반 분류기의 적용 Classification

규칙 적용범위(Coverage)와 정확도(Accuracy) Classification

규칙기반 분류기의 동작 방법 Classification

규칙기반 분류기의 (바람직한) 특징 Classification 상호 배타적 규칙 (Mutually exclusive rules): 각 레코드는 하나의 규칙에만 지배를 받아야 한다. 포괄적 규칙 (Exhaustive rules): 분류기의 규칙은 모든 가능한 레코드에 적용될 수 있어야 한다.

의사결정 트리  규칙 생성 Classification

(생성된) 규칙의 단순화 Classification

규칙 단순화에 의한 효과 Classification

순서화된 규칙 집합 (Ordered Rule Set) Classification

분류 규칙의 생성 방법 Classification

직접 방법: 순차적 커버링(Sequential Covering) Classification

순차적 커버링 예제 Classification

간접 방법: 의사결정 트리 등 사용 Classification

규칙기반 분류기의 장점 Classification

의사결정 트리 (Decision Trees) 규칙기반 분류기 (Rule-Based Classifiers) 강의 내용 Classification 분류 정의와 적용사례 의사결정 트리 (Decision Trees) 규칙기반 분류기 (Rule-Based Classifiers) 인접 이웃 분류기 (Nearest Neighbor Classifiers) 베이지안 분류기 (Bayesian Classifiers) 인공 신경망 (Artificial Neural Networks) 지지도 벡터 머신 (Support Vector Machines)

인스턴스 기반 분류기 (1/2) Classification

인스턴스 기반 분류기 (2/2) Classification

인접 이웃 분류기 (Nearest Neighbor Classifiers) Classification

인접 이웃 분류기 개념 Classification

인접 이웃 분류기 정의 Classification

1 인접 이웃 (1-Nearest Neighbor) Classification

인접 이웃 분류기 이슈 (1/4) Classification

인접 이웃 분류기 이슈 (2/4) Classification

인접 이웃 분류기 이슈 (3/4) Classification

인접 이웃 분류기 이슈 (4/4) Classification

의사결정 트리 (Decision Trees) 규칙기반 분류기 (Rule-Based Classifiers) 강의 내용 Classification 분류 정의와 적용사례 의사결정 트리 (Decision Trees) 규칙기반 분류기 (Rule-Based Classifiers) 인접 이웃 분류기 (Nearest Neighbor Classifiers) 베이지안 분류기 (Bayesian Classifiers) 인공 신경망 (Artificial Neural Networks) 지지도 벡터 머신 (Support Vector Machines)

베이지안 분류기 (Bayesian Classifiers) Classification

베이스 정리의 예제 Classification

베이지안 분류기 개념 (1/2) Classification

베이지안 분류기 개념 (2/2) Classification

순수 베이지안 분류기 (Naïve Bayes Classifier) Classification

훈련 집합에서 확률 구하기 (1/3) Classification

훈련 집합에서 확률 구하기 (2/3) Classification

훈련 집합에서 확률 구하기 (3/3) Classification

순수 베이지안 분류기 예제 (1/2) Classification

순수 베이지안 분류기 예제 (2/2) Classification

베이지안 분류기 요약 Classification

의사결정 트리 (Decision Trees) 규칙기반 분류기 (Rule-Based Classifiers) 강의 내용 Classification 분류 정의와 적용사례 의사결정 트리 (Decision Trees) 규칙기반 분류기 (Rule-Based Classifiers) 인접 이웃 분류기 (Nearest Neighbor Classifiers) 베이지안 분류기 (Bayesian Classifiers) 인공 신경망 (Artificial Neural Networks) 지지도 벡터 머신 (Support Vector Machines)

인공 신경망 개념 (1/3) Classification

인공 신경망 개념 (2/3) Classification

인공 신경망 개념 (3/3) Classification

인공 신경망의 일반적 구조 Classification

인공 신경망의 학습 알고리즘 Classification

의사결정 트리 (Decision Trees) 규칙기반 분류기 (Rule-Based Classifiers) 강의 내용 Classification 분류 정의와 적용사례 의사결정 트리 (Decision Trees) 규칙기반 분류기 (Rule-Based Classifiers) 인접 이웃 분류기 (Nearest Neighbor Classifiers) 베이지안 분류기 (Bayesian Classifiers) 인공 신경망 (Artificial Neural Networks) 지지도 벡터 머신 (Support Vector Machines)

SVM (Support Vector Machines) (1/7) Classification

SVM (Support Vector Machines) (2/7) Classification

SVM (Support Vector Machines) (3/7) Classification

SVM (Support Vector Machines) (4/7) Classification

SVM (Support Vector Machines) (5/7) Classification

SVM (Support Vector Machines) (6/7) Classification

SVM (Support Vector Machines) (7/7) Classification

비선형 SVM (Nonlinear SVM) (1/2) Classification

비선형 SVM (Nonlinear SVM) (2/2) Classification

의사결정 트리 (Decision Trees) 규칙기반 분류기 (Rule-Based Classifiers) 강의 내용 Classification 분류 정의와 적용사례 의사결정 트리 (Decision Trees) 규칙기반 분류기 (Rule-Based Classifiers) 인접 이웃 분류기 (Nearest Neighbor Classifiers) 베이지안 분류기 (Bayesian Classifiers) 인공 신경망 (Artificial Neural Networks) 지지도 벡터 머신 (Support Vector Machines)