분류(classification)이란 어떤 항목(item)이 어느 그룹에 속하는지를 판별하는 기능을 말한다.
분류는 data analysis의 기본이며 응용 분야도 가장 넓다.
9.1 기본 개념
분류에서 가장 자주 사용되는 모델은 주어진 샘플 항목의 몇 가지 특성 변수를 보고 이 샘플이 어떤 그룹에 속하는지를 판단하는 것이다.
분류 분석 문제에서는 알고자 하는 목적 변수(target variable)가 있다.
또한 분류를 하는데 사용한 변수를 특성 변수(feature) 또는 속성 변수(attribute)이라고 한다.
9.2 Decision Tree
분류를 처리하는데 가장 많이 사용되는 방법이 decision tree다.
decision tree는 분류 작업을 수행하기 위해서 한 번에 한 특성 변수씩 따져보는 방법이다.
decision tree는 동작을 직관적으로 이해하기 쉽고 구현도 간단해서 널리 사용되며 대부분의 통계처리 패키지나 data mining 도구에서 제공하고 있다.
동작 원리
decision tree에서 가장 중요한 부분은 어떤 변수를 가지고 판별을 시작하는가이다.
여기서 그룹을 '잘 나눈다' 함은 그룹을 나눈 후에 생성되는 하위 그룹들에 가능하면 같은 종류의 아이템들이 끼리끼리 모이도록 하는 것을 기준으로 삼는 것이다.
한 그룹에 같은 종류의 item이 많이 모여 있는 정도를 순수(pure)하다고 표현하는데, 만일 나누어진 하위 그룹이 100% 같은 항목들로만 구성되면, 즉 완벽하게 나누어지면 순수도(purity)가 100%라고 한다.
decision tree의 동작은 데이터의 순도가 가장 빨리 높아지도록 그룹을 나누는 작업이라고 할 수 있다.
어떤 항목의 분포 상태로부터 순도를 나타내는 방법으로 정보량 개념이 주로 사용된다.
정보량
정보량이란 어떤 데이터가 포함하고 있는 정보의 총 기대치(가치)를 나타낸다.
같은 정보라도 그 가치는 사람마다 다르게 느끼는 주관적인 양인데 어떻게 이를 객관적으로 측정할 수 있을까?
이에 대해 수학자들이 오래 곤민한 끝에 정보량을 표현하기 위해 그 사건이 발생할 확률을 사용하는 방법을 생각했다.
정보량은 일어날 확률의 역수에 비례한다고 가정할 수 있다.
그래서 수학자들은 어떤 사건이 발생할 확률이 p이면 그 사건의 정보량을 다음과 같이 정의했다.
log(1/p)정보량이 확률에 반비례한다는 것, 즉 1/p로 표현되는 것은 앞의 설명으로 이해가 되는데 이 값에 왜 로그를 붙였을까?
로그의 도입
Log function은 사람이 어떤 현상에 대해 실제로 느끼는 체감 수치를 나타내는데 자주 등장한다.
즉, 같은 감정의 변화를 느끼려면 나에게 주어지는 절대량이 같아서는 안 되고, 현재 내가 보여한 양에 비례하는 변화가 주어져야 한다.
이런 현상은 사람이 자연적으로 느끼는 느낌의 양을 수학적 모델로 설명할 때 자주 등장한다.
정보량과 엔트로피
정보량의 기대치를 구해보자.
기대치란 어떤 사건이 갖는 가치에 그 사건이 발생할 확률을 곱해서 얻는다.
따라서 어떤 사건의 "정보량의 기대치"를 구하려면 그 사건의 정보량 log(1/p)에 그 사건이 발생할 확률(p)를 곱해주어야 하며 이를 식으로 표현하면 다음과 같다.
plog(1/p) = -plog(p)위와 같이 정의한, 어떤 사건이 갖는 정보량 기대치를 entropy라고 한다.
어떤 사건이 발생할 확률이 거의 없으면, 즉 p = 0 이면 1/p 값은 매우 커지지만 이 사건이 발생할 확률 p가 거의 0이 되어 엔트로피는 0이 된다. 반면에 p가 1에 가까우면, 즉 발생이 거의 확실하면 1/p이 1이 되고 log(1) = 0 이므로 엔트로피 값은 거의 0이 된다.
엔트로피는 p가 0과 1의 중간 값, 즉 p = 0.5 일 때가 가장 높다.
의사 결정 트리에 적용
한 그룹의 동질성(순도)이 낮으면 엔트로피가 높고, 한 그룹의 동질성이 높으면 엔트로피가 낮다고 하겠다.
이제 의사결정 트리 알고리즘에서 각 단계별로 어떻게 나누는 것이 가장 좋은지는 가장 엔트로피가 작아지는 방향으로, 즉 순도가 높아지는 방향으로 정하면 된다.
가장 우수한 구분 변수 찾기
우리가 찾아야 할 것은 매 의사결정 단계마다 그룹을 가장 잘 나누는 변수다.
잘 나눈다는 기준은 같은 것끼리 한 곳에 모으는 것, 즉 순도를 높이는 것이다.
순도의 변화를 나타내기 위해 그룹을 나누기 전후의 엔트로피 변화량을 계산하는데 이를 정보 이득(IG : information Gain)이라고 한다.
트리 구조를 만드는 작업을 멈추는 조건은 모든 항목의 분류가 완성되어 각 그룹에는 같은 클래스의 항목이 배정되거나, 트리의 크기가 미리 정해진 최대 크기에 도달했을 때다.
트리 크기가 너무 커지는 것을 방지하기 위해서 보통 최대 트리 크기를 지정한다.
Confusion matrix
confusion matrix란 분류의 결과가 잘 맞았는지를 평가하는데 자주 사용되는 도구다.
Overfitting
Decision tree를 주어진 훈련 데이터에 너무 잘 맞추는 것은 오히려 실제 상황에서는 잘 맞지 않게 된다.
주어진 데이터의 일부를 훈련 데이터로 사용하지 않고 남겨두었다가 나중에 모델의 성능을 test하기 위해 사용하는 데이터를 hold out 데이터라고 한다.
훈련용 데이터와 테스트 데이터를 순차적으로 섞어서 사용하는 hold out 방식을 cross validation이라고 한다.
cross validation 방식에서는 데이터셋을 5~10개로 나누는 것이 일반적이다.
cross-validation 방식의 극단적인 예로 leave-one-out 방식이 있는데, 테스트용으로 단 한 개의 샘플 데이터만 사용하는 것이다.
decision tree 알고리즘은 overfitting을 피하기 위해 내부적으로 가지치기(pruning)을 수행한다.
Pruning이란 너무 세세하게 트리가 만들어지지 않게 나무의 잔가지 치듯 트리의 크기를 줄인다는 뜻이다.
Pruning에는 pre-pruning과 post-pruning 방식이 있다.
실제로는 주로 post-pruning 방식이 사용된다.
반면에 트리 구조를 너무 단순하게 만들어 동작이 제대로 되지 않는 것을 underfitting이라고 한다.
Decision tree의 특징
Decision tree는 거의 모든 종류의 분류에서 사용할 수 있는 범용 모델이다.
분류 알고리즘의 정확도와 분류 속도를 높이려면 분석에서 사용할 특징 변수(feature)를 잘 선택하는 것이 무엇보다 중요하다.
특징 변수 선택이 잘 되어야 모델의 정확도도 높아지고, 동작속도도 빨라질 수 있다.
분석에 적합한 적절한 특징변수를 찾아내려면 해결하려는 문제 도메인을 잘 이해해야 한다.
Random Forest
Decision tree의 성능을 개선한 방법으로 Random Forest 방식이 있다.
이 방식은 여러 모델의 평균치를 구하는 ensemble 모델인데, 주어진 훈련 데이터 전체를사용해서 하나의 트리 모델을 만드는 것이 아니라, 데이터의 일부만 사용하여 의사결정 트리 자체를 여러 가지 만들어 보고 그 중 가장 나은 모델을 선택하는 방식이다.
이 방식은 모델을 만들 때 모든 변수를 사용하지 않고 영향력이 큰 특징 변수들을 찾아서 사용한다.
따라서 특징 변수가 많은 경우에도 사용하기에 적합하다.
but, random forest 방식은 decision tree와 달리 모델의 동작을 직관적으로 설명하기가 어려우며 최적의 모델을 찾기 위해서 계산량이 많아진다는 단점이 있다.
협업 필터링
Decision tree와 함께 분류에 널리 사용되는 방법이 collaborative filtering이다.
collaborative filtering은 추천 시스템에서 많이 사용되는데 적절한 추천을 하기 위해서는 사람의 성향을 미리 분류하고 같은 성향의 사람들이 좋아하는 품목을 추천하는 방식을 사용한다.
여기서 사람의 성향을 미리 분류하기 위해 collaborative filtering가 사용된다.
기본 개념
- ex) 서점에서 어떤 사람(A)에게 도서를 추천한다고 하자.
서점에서는 그 사람과 독서 취향이 비슷한 사람들 그룹을 먼저 찾는다.
서점에서는 평소 고객들이 어떤 책들을 사서 보는지, 그리고 책에 대한 평가들은 어땠었는지를 보고 취향이 비슷한 사람들을 구분해 낼 수 있다.
이제 추천할 사람(A)과 취향이 비슷한 사람들 사이에서 평이 가장 좋은 책 중에 아직 A가 보지 않은 책을 추천하면 된다.
여기서 협업이라는 말을 쓰는 이유는 여러 사람의 협력을 받기 때문이다.
위와 같이 취향이 비슷한 '사람'을 기반으로 하는 collaborative filtering을 user-based collaborative filtering이라 한다.
collaborative filtering에는 user-based collaborative filtering 외에 상품을 기반으로 하는 방법이 있다.
ex) a라는 상품을 좋아하는 사람들은 대부분 b나 c 상품도 같이 좋아한다고 하자.
그러면 상품 입장에서 유사한 상품 그룹을 만들 수 있을 것이다.
이런 방식을 item-based collaborative filtering이라고 한다.
실제 아마존도 item-based collaborative filtering 방식으로 추천을 하고 있다.
k-NN 알고리즘
collaborative filtering을 다른 표현으로 k-NN(k-nearest neighbor) 알고리즘 이라 한다.
k-NN 이라는 이름의 의미는 어떤 사람(item)과 가장 가까운 특성을 가지는 이웃(neighbor)을 k개 선택하고 이들의 평균치를 보고 분류를 결정하기 때문이다.
k-NN 알고리즘에서 최적의 k값을 선택하려면 원하는 분류 동작이 어떤 k값에 대해 가장 잘 이루어지는지를 비교해봐야 한다.
k값을 너무 작게 잡으면 참고할 주변 데이터가 적어서 오차가 발생하고 k값을 너무 크게 잡으면 주변에 너무 많은 데이터의 평균치를 사용하므로 분류가 불명확해진다.
적절한 k 값의 선택은 원하는 목적에 얼마나 적합한지를 보고 판단해야 한다.
k를 크게 잡을수록 noise에 강한 장점이 있으나 세밀한 분류, 즉 분류의 정확도는 떨어지고 k값을 작게 잡으면 noise에 민감하나 정확도는 올라간다.
보통 k 값은 3~9 사이를 선택한다.
k-NN 알고리즘의 장점은 알고리즘이 매우 간단하고 성능도 좋다는 것이다.
모델링을 하기 위한 파라미터를 정의할 필요도 없다.
훈련 시간도 거의 없고 특성 변수들만 잘 선정하면 된다.
k-NN 알고리즘의 단점은 명시적인 분류 모델을 가지고 있지 않으므로 어떤 변수가 더 중요한지 파악하기 어렵다는 것이다.
훈련시간이 거의 없는 것에 비해 분류를 처리하는 시간, 즉 알고리즘을 수행하는 시간이 길다.
이렇게 나중에 계산량이 많은 종류의 알고리즘을 lazy 알고리즘이라고 한다.
범주형 데이터 처리
범주형 변수에 대해서는 유클리디언 거리를 구할 수가 없다.
ex) 남녀를 구분하는 변수를 알고리즘에서 반영하려면 dummy coding을 사용한다.
ex) 남자면 M=1, 여자면 M=0으로 코딩하여 일반수치형 변수와 같이 처리할 수 있다.
더미 코딩의 의미는 범주형 특성을 숫자 0과 1로 매핑하고 이를 특성간의 거리 계산에 반영한다는 것이다.
즉, 더미 코드 사이의 거리는 0이거나 1이 된다.
