[Data Mining] Classification : Basic Concepts

데이터 마이닝 진창호 교수님 (19-1)

 

Classification의 Goal

- Previously unseen records should be assigned a class as accurately as possible

>> A test set is used to determine the accuracy of the model

>> training set => bulid a model

>> test set => validate

>> 내가 알고 있는 지식으로는 validate set이 따로 있는데... 그냥 그러려니 하고 넘어가자. 

 

Purpose of Classification Model

- Descriptive Modeling

>> 서로 다른 class를 갖고 있는 object를 구별하는 설명 도구 역할을 한다. 

>> Ex. 척추동물이라고 예측된 생물들은 양서류와 다른 어떤 점들이 있나(feature들이 어떤 값을 띄고 있나?)

Descriptive	Predictive
같은 카테고리에서(같은 target attribute) 반복적으로 나타내는 현상을 통해 (특정 attribute에서 특정 값이 계속 반복해서 나타나는 것) 카테고리를 설명한다.	알고 있는 값을 통해서 모르는 값에 카테고리 값을 부여한다(target attribute value를 부여한다.) 즉 category와 나머지 attribute 사이의 관계를 모델이 표현한다.
과거	미래 혹은 알지 못하는 현재
About more than one data	About on data
Model은 항상 historical data를 대표한다. (historical data로 부터 생성하니까)	과거 데이터를 기반으로 만들어지기 때문에 과거 패턴이 더이상 유의미하지 않다면 model은 미래를 대변할 수 없다.

 

*참고사항

- ordinal target attribute 에서는 비교적 덜 효과적이다, 왜냐면 모델이 order 정보를 고려하지 않기 때문에.(poor, good best를 예측하는 건 어렵다)

- most suited for predicting or describing data set with binary or nominal categories.

- Subclass-superclass relationships among categories are ignored. (사람과 유인원은 둘 다 영장류이며, 그 둘의 subclass는 포유류이다. 하지만 이러한 정보들은 무시된다.)

 

- Training set으로 학습 모델 만들고 output 출력

>> 모델을 평가해야지! => confusion matrix

>> Accuracy = 맞은 것 / 나머지 전부 =  (f11+f00) / (f11+f00+f10+f01)

>> error rate = 1-accuracy

- 그리고 Test set으로 검증하기

 

SVM

- margin을 최대화 하는 hyperplane을 찾자.

 

Decision tree induction

- 어떻게 만들어?

>> 질문을 던지고

>> 그 질문을 적절한 위치에 배치시킨다.(root node, internal node, leaf node)

- 각각의 leaf node는 class label을 할당받는다. 

- 완벽하게 분류하는 decision tree를 만드는 건 계산 비용이 매우 high!

- algorithms developed to induce(설득하다) a reasonably accurate, albeit suboptimal decision tree.

- 기본적인 Hunt's 알고리즘을 먼저 살펴보자. 

 

Hunt's algorithm

- class y = { y1, y2, ..yc} : c는 존재하는 target attribute value의 가짓수

- Dt = {T1, T4, T7} : Dt는 해당 node에 존재하는 object들이 뭐가 있느냐~?

- 목적 : Dt에 단일 class만 존재하도록 계속 node를 split 한다. 

- 제약조건 : attribute를 한 번만 쓴다.(일단은 그런 거 같음) 모두 사용했는데 단일 class만 존재하지 않으면 일단 stop

- 절차

 1) node: 질문을 던지기

 2) branch : 질문 대답에 따라서 가지 치기

 3) node : 계속 split할지 stop 할지 결정하기

 4) stop : leaf node가 단일 class로만 존재한다. 

     split : internal node with question => 다시 1번으로 돌아간다. 

 

Assumption for Hunt's algorithm

- basic assumption

1) every combination of attribute values is present in the training data

>> (a1의 value type 2개) * (a2의 value type 2개) * (a3의 value type 2개) = 8가지 조합이 데이터 상에 있으면 좋다. 

2) each combination of attribute has a unique class label

Y   S  1.3k     => target = YES

Y   S  1.3k     => target = NO

이런 식으로 같은 attribute인데 target만 다른 경우는 안좋다는 것

========> Too stringent(엄한)  => 약간의 조건을 추가한다.

1) split을 했는데 없다? => 그전의 majority class를 따른다. => 이렇게까지 하는 이유는 미래에는 이런 상황이 올 수 있으니까

2) 마찬가지로 같은 attribute인데 target만 다르면 majority를 따른다. 

 

Tree induction

- greedy 하다.

- issues

1) Determine how to split the records

>> 어떤 attr 먼저 사용하지?

>> how to determine the best split?

2) Determine when to stop splitting 

>>  leaf node에 있는 모든 record가 same class에 속할 때

>> depth로 판별할 수 있음