Loss functions

딥러닝 하다보면 그냥 사용했던 Loss Function들에 대해서 한번 다뤄 본다.

Entropy

정보를 최적으로 인코딩하기 위해 필요한 bit의 수
$$\log_{2}^{}{N}$$

요일 예시 (Uniform)

만약 요일에 대한 정보를 메시지에 실어서 보내야 한다면 가장 최소의 bit를 사용한다면 얼마나 될까?
Yes/No수준이라면 그냥 1 bit만으로 충분하다.

그렇다면 econding을 day of the week을 해야한다고하면, 7 values를 encode 해야한다.
결국 $\log_{2}^{}{7}$
월화수..일 7가지를 bit로 전송하기 위해선 3bit필요 하게 된다.

• bits (000 – Monday, 001 – Tuesday, …, 110 – Sunday, 111- unused).

  bit의 발생 빈도가 uniform 하다는 가정에 의해서 발생

Speech of a sequence of words (skewness)

만약 영어 단어를 말하는것을 encode 하는 것을 생각해 보자.
그냥 단순히 uniform하다고 가정하면 $$\log_{2}^{}{40} = 5.3$$ 이다.

하지만 4개의 Tag값들이 90%가 발생한다면 좀 더 효율적인 bit encode를 만들어 낼 수 있다.

40개의 문자가 있고 상위 4개가 90%로 발생한다.

• ART, P, N, V

아이디어는 첫 번째 bit를 단순히 위 네개의 TAG를 구분하는데 사용 한다.

• YES 이면 추가로 2bit를 더 필요로 해서 구분하게 된다.
• NO 이면 6bit를 더 필요로 한다. 40-4 = 36이고, $$\log_{2}^{}{36}=5.16$$

정리하면 아래 표와 같다.

이것을 생각한 방식으로 계산하면 아래와 같다.
필요한 bit수 계산 = $$0.9 \times 3 + 0.1 \times 7 = 3.4$$

원래 아이디어 보다 bit수가 더 줄어 들었다. 거의 반만큼.
여기서 더 최적화 할 수 있을까?

Information theory provides an answer.

As mentioned before, Entropy is a measure of randomness in a probability distribution.
A central theorem of information theory states that the entropy of p specifies the minimum number of bits needed to encode the values of a random variable X with probability function p.

Definition of Entropy

X를 random variable이라고 하면 p는 probability function이다.
$$ p(x_{i}) = P(X=x_{i}) $$
이라고 한다 (보통 algebra variable과 혼동하지 않기 위해서 capital로 표기하지만 여기선 간소화를 위해서 assumption을 만들고 시작).

Entropy of X (or p)의 정의는 아래와같다.

$$H(X) = H(p) = - \sum_{i}{p(x_i) \times \log{p(x_i)} }$$,

where

$$x_{i}$$ ranges over the vocabulary of

$$X$$

위 식으로 다시 계산해보면 TAG random variable에 대해서 actual probability distribution을 표1에서와 같이 알기 때문에 TAG의 entropy는 아래와 같이 계산된다.

$$ H(TAG) = -(4 \times (.225 \times \log_{2}{.225}) + 36 \times (.0028 \times \log_{2}{.0028})) = -(-1.04 + -.82 + -.85) = 2.72 $$

결과 값을 통해서 그냥 단순하게 coding 했던것 보다 좋았던 3.4보다 더 낮은 2.72가 optimal 이라는것을 알게 되었다.
하지만, entropy의 문제는 이게 가장 best한 conding 디자인이 아니라는것만 알려주지 실제로 그래서 어떻게 coding 해야 optimal에 도달하는지를 알려주지 않는다. 더 나아가 physically이게 가능한 것인지도 알 수 없다.

Data science에서 보는 값에 따른 해석

• High Entropy는 x가 uniform한 distribution을 가지게 된다. 즉 boring하다고 해석할수도 있고 diversity가 높다고 할수도 있다. Active Learning에서 그래서 이러한 Entropy를 이용해서 smapling을 할지 말지를 고려할 수도 있다.
• Low Entropy는 skewness가 높다고 할 수 있다. 결국 varied distribution이라 할 수 있고 peak나 valley가 많다고 할 수 있다.

R Shannon Entropy 계산

setosa_subset <- iris[iris$Species=="setosa",]

#compute Shannon entropy
entropy <- function(target) {
  freq <- table(target)/length(target)
  # vectorize
  vec <- as.data.frame(freq)[,2]
  #drop 0 to avoid NaN resulting from log2
  vec<-vec[vec>0]
  #compute entropy
  -sum(vec * log2(vec))
}

entropy(setosa_subset$Species)

참조: Entropy, Information Gain, and Data Exploration in R

Cross-Entropy

두개의 probability function을 비교하는것이 cross entropy이다.

• p와 q로 구분한다.
  이러한 Cross Entropy는 symmetric하지 않기 때문에 그 역은 성립하지 않는다.
  p를 보통 target으로 q를 estimated one으로 설정한다.
  그렇게 비교해서 얼마나 서로 가까운지를 알아내서 그것을 최적화하는 방법으로 학습에 사용한다.

$$ H(p,q)= -\sum { i }{ p(x{ i }) } \log { q(x_{ i }) } $$

$$p_{y=1} = y$$
이고
$$p_{y=0} = 1-y$$
라면,
$$p \in (y, 1-y), q \in (\hat{y} ,1-\hat{y})$$

$$H(p,q)= -\sum { i }{ p(x{ i }) } \log { q(x_{ i }) } = -y\ln{\hat{y}} + (1-y)\ln(1-\hat{y})$$

MSE의 문제점
$$MSE = C = \frac{{(y-a)^2}}{2}$$
$$a = \sigma(z)$$
$$z = wx+b$$
위의 것을 미분하면,
$$ \frac{\partial C}{\partial w} = (a-y)\sigma^{\prime} {(z)} x $$
$\sigma^{\prime} {(z)}$ 값이 최대 0.25가 나오고 대부분 0이기 때문에 vanishing gradient가 생기는건 잘알려진 사실이다.

cross entropy 미분

$$ C= -\frac{1}{n} \sum_{x}^{}{y\ln{a} + (1-y)\ln(1-a)} $$

$$ \frac { \partial C }{ \partial w_{ j } } =-\frac { 1 }{ n } \sum { x }{ (\frac { y }{ \sigma (z) } -\frac { (1-y) }{ 1-\sigma (z) } ) } \frac { \partial \sigma }{ \partial w{ j } } \ =-\frac { 1 }{ n } \sum { x }{ (\frac { y }{ \sigma (z) } -\frac { (1-y) }{ 1-\sigma (z) } ) } \sigma ^{ \prime }(z)x{ j }\ =\frac { 1 }{ n } \sum { x }{ \frac { \sigma ^{ \prime }(z)x{ j } }{ \sigma (z)(1-\sigma (z)) } } \sigma ^{ \prime }(z)-y $$

최종적으로 아래식 처럼 $\sigma(z)$가 살아있기 때문에 vanishing 문제를 적게 발생 시키는 좋은 폼을 형성한다.
$$ \frac{\partial C}{\partial w_{j}} = \frac{1}{n} \sum_{x}^{}{x_{j}(\sigma(z)-y) } $$

KL-divergence

두 분포 차이를 줄이기 위해서는 KL-Divergence를 사용한다.

$$ D_{KL}(P \parallel Q) = -\sum_{x}^{}{p(x) \log{q(x)}} + \sum_{x}^{}{p(x) \log{p(x)}} $$

$$ = H(P,Q) - H(P) $$

정의

• P라는 확률 분포로 부터 발생한 데이터를 Q라는 확률 분포에서 나왔다고 가정했을 경우 이로 인해 발생되는 추가 정보량을 KL-divergence라고 한다.

• 즉, 두 분포 P와 Q가 같으면 KL 값은 0. 서로 다르면 KL 값은 0보다 크다. 클수록 차이가 크다.

• 단순 면접이나, 거리 개념은 아니고 entropy개념이 들어가거 높은 확률을 가지는 지점을 잘 근사해야 KL값이 작아지는 특성을 가진다.

참고자료

Lecture6: Using Entropy for Evaluating and Comparing Probability Distributions

정보량을 나타내는 앤트로피(Entropy)

4.1. Cross entropy와 KL divergence

어떤 feature를 뽑아야 좋은 model을 생성 할 수 있을까?

해당 질문은 매우 어려운 문제이다.

해당 분야에 대한 깊은 지식이 없는 사람은 feature를 선택하기가 쉽지 않다.

Feature selection이란 결국 가장 관련있는 feature들의 subset을 골라 내는 작업을 말한다.

이것은 Dimensionality reduction과 유사해 보일 수 있지만 그렇지 않다.

Feature Selection을 통해서 해결 되는 문제점들

관련 없는 데이터 제거

중복성 제거

정확도에 높은 모델에 기여되는 feature들이 무엇인지를 알아냄

심지어 어떤 feature들은 참여 됨으로써 정확도를 떨어뜨림 이런것들을 찾아냄

feature들을 최대한 적게 써서 model을 만드는 것이 좋다.

왜냐하면, 성능도 좋고 복잡하지 않으므로 이해하기도 쉽다. 그리고 설명도 쉽게 된다.

Feature Selection Algorithms

일반적으로 feature 선택 알고리즘은 세가지로 구분 된다.

filter method

wrapper method

embedded method

- Filter Method

각각의 feature들에 통계적인 점수를 부여하는 방법이다.

그리고 각각의 feature들은 score에 의해서 rank매겨 진다.

Example of some filter methods include the Chi squared test, information gain and correlation coefficient scores.

- Wrapper Method

search problem으로써 feature들의 집합을 선택한다.

An example if a wrapper method is the recursive feature elimination algorithm.

- Embedded Method

어떻 feature가 가장 크게 기여하는지를 찾아내는 방법이다.

Examples of regularization algorithms are the LASSO, Elastic Net and Ridge Regression.

Feature Selection Tutorials and Recipes

We have seen a number of examples of features selection before on this blog.

Weka: For a tutorial showing how to perform feature selection using Weka see “Feature Selection to Improve Accuracy and Decrease Training Time“.

Scikit-Learn: For a recipe of Recursive Feature Elimination in Python using scikit-learn, see “Feature Selection in Python with Scikit-Learn“.

R: For a recipe of Recursive Feature Elimination using the Caret R package, see “Feature Selection with the Caret R Package“

Single Attribute Evaluator: infoGainAttributeEval

Evaluate attribute based on information 

Ensemble Method

Random Forests

decision tree classifier들을 위해서 디자인 된것으로써 다중 decision tree를 이용 한다.

각각의 트리들은 독립적인 랜덤 셋 백터를 생성하게 된다.

semi-supervised machine learning 

이것은 interactively query를 이용해서 desired output을 새로운 데이터 포인트에서 획득 하는 방식을 의미한다.

사용하는 상황은

unlabeled data가 매우 많아서 수작업으로 그것을 라벨링 하기 어려울 때

active learning 알고리즘을 이용해서 지도자에게 질의 하여 라벨링을 할 수 있다.

즉 uncertainty sampling 데이터가 많은 상황에서 사용하는 방법이다.

좋은점은

학습에 필요한 라벨된 데이터의 양을 줄일 수 있다.

이유는 학습자가 능도적으로 데이터를 선택하기 때문이다.

원제: Best Programming Language for Machine Learning

아래는 기계학습을 위해서 사람들이 선택한 언어를 나타낸다.

We ran a brief analysis on the tools Kagglers used and wanted to share the results.  The open source package R was a clear favorite, with 543 of the 1714 users listing their tools including it.  Matlab came in second with 218 users.  The graph shows the tools that at least 20 users listed in their profile.

Machine Learning Languages

MATLAB/Octave

깊이 있게 내부를 구현해보고 싶을때 사용할 수 있는 언어이다.

matrix 연산에 특화된 도구이다.

R

statistical analysis에 특화된 언어이다.

machine learning 알고리즘도 많이 구현 되어있다.

확장성도 용이하다.

Python

NumPY로 MATLAB과 같은 행렬 연산 가능

SciPy로 machine learning 알고리즘 구현 가능

Java-family / C-family

여기에는 강건한 라이브러리르 들이 많이 있다.

Weka(java), LibSVM(C++) 등이 하나의 예이다.

성능관점에도 C는 유용하다.

Programming Languages for Machine Learning Implementations

Speed

python과 java 같은 경우 garbage collection이 문제이다.

Programming Ease

매우 주관적인 부분이지만 그래도 차이는 존재 한다.

1) Syntax: 일반언어처럼 자연스러우며 간결해야 한다. 

2) Library support: linear algebra, graphics, IO 등과 같은 라이브러리를 효율적으로 제공 해줘야 한다.

3) Built in Functionality: 자료구조, module 등을 의미 한다.

4) Scalability: 

5) Familiarity

The existing significantly used machine learning code bases seem to favor lower level languages.

1. Weka is one of the best known general purpose machine learning toolkits. It is implemented in Java and has far more algorithmic coverage than any other system I know of.
2. LibSVM is implemented in C++ and Java.
3. SVMlight is implemented in C.
4. C4.5 is implemented in C.
5. SNNS is written in C.

분석에 사용되는 feature들이 시간적 특성을 지닌다.

e.g., 지진파, 음성, 주식 거래량, 온라인 필기 문자 등

이러한 데이터를 sequential data 또는 context-dependent data라고 부른다.

시간성의 없는 데이터 선후 관계를 바꿔도 아무런 의미 변화가 없다.

시간성이 있는 데이터의 경우 선후 관계가 매우 중요해서

그것을 변경하면 새로운 결과가 나오게 된다.

HMM을 배우기 전에 기본적으로 Markov model이 무엇인지 부터 보자.

러시아 수학자 Andrey Markov 제안

시간 t에서의 관측은 가장 최근 r개 관측에만 의존한다는 가정 하의 확률 추론

예제

최근 4일간의 날씨 정보를 가지고 오늘 날씨를 추론하는것을 생각해 보자.

해 해 해 비 

1차 마코브 모델을 사용하면 어제의 날씨 변화만 오늘에 영향을 미치므로 아래와 같이 4가지 경우가 모두 같게 된다.

1차 마커브 모델을 표로 표현하면 아래와 같다.

오늘 비 였을때 내일 {비,구름,해}의 확률을 모두 합하면 1이 되야한다. 계산해 보면 1이 된다.

하지만, 내일 {비}라고해서 오늘 {비,구름,해}일 확률의 합이 1은 아니다. '역'의 관계에서는 어떠한 시간적 의미도 없기 때문이다.

여기서 2차 마코브 모델을 고려한다고 생각해보자.

선후 관계가 있으므로 순서가 있는 경우다. 즉 순열이며

{비,비,비}와 같은 중복을 허용한다.

따라서 2차 마코브 일때의 경우의 수는 아래와 같다.

위 표를 이용해서 3x3 matrix를 생성한다. 이것을 이용해서 마크브 모데의 상태전이도를 만들게 된다.

아래와 같은 조건을 만족 한다.

마코브 모델을 이용해서 무엇을 할 수 있을 까?

관측백터 x를 구할 수 있게 된다.

P(x|마코브 모델) = P(x|A)라는 식이 나온다.

여기서 마코브 모델을 나타내는 A는결국 joint probability가 되므로

마크모델 A와 관측 벡터 O간의 독립이면 P(O|A) = P(O)로 기술 할 수 있다.

그리고 joint probability가 갑자기 3->4로 넘어갈때 간단해 지는데 이러한 이유는

DAG 그래프 형태로, 즉 노드가 바로 직전의 부모에만 의존적인 베이시안 네트워크 구조를 가지기 때문이다.

즉 우리가 가정한 마코브는 1차원 바코브기 때문에 조인트 확률이 바로 직전의 노드에만 의존적이므로 뒷 부분을 모두 다 날려 버릴 수 있게 된다.

1차 마코브라도 계산을 위해서는 초기 확률이 필요하다.

초기 확률은 해가 되기위한 "파이3" 이다

곱의 확률이기 때문에 확률이 너무 적게 된다.

히든 마코브와 그냥 마코브와의 근본적인 차이점.

- 마코브 모델은 상태를 나타내는 노드에 관측 (비,해,구름) 그 자체가 들어 있다. 즉 상태를 볼 수 있다.

- HMM에서는 상태를 볼수 없게 했다. 즉 상태를 은닉 하게 된다.

동기

r차 마크브에서는 m^r (m-1)개의 매개변수가 생성 된다.

차수에 따라 모델의 크기가 너무 크게 증가 한다.

HMM

- 차수를 미리 고정하지 않고 모델 자체가 확률 프로세스에 따라 적응적으로 정함

- 따라서 아무리 먼 과거의 관측도 현재에 영향을 미침

- 즉 P(해 |비,비), P(해 | 비,비,비) , P(해,비,비,...,비) 모든 것에 따라서 확률 값이 다르게 된다. 즉 특정 어떤 차수에 고정적이지 않다.

- 이런 뛰어난 능력에도 불구하고 모델의 크기는 감당할 정도 이다.

비결

- 상태를 감추자

상태를 가지는 대신에 모든 노드가 모든 상태를 가질 수 있는 확률을 가지게 된다.

이용방법

예를 들어서 고나측 데이터로써 해->해->비->구름 이렇게 4일간의 관측 데이터가 존재한다고 하자.

그냥 마코브 모델을 사용한다면, 저러한 상태 전이는

s3 -> s3 -> S1 -> s2가 된다.

하지만 HMM의 경우

모든 상태에서 {비,해,구름}이 관측이 가능 하므로 가능한 시퀀스가 여러개 존재한다.

상태가 3개이니

3*3*3*3 의 경우의 수가 나온다.

3^4 = 81

이중에서 하나만 골라서 계산해 보면 

s3-> s3 -> s1 -> s2

HMM의 예제 (1) 

n개의 항아리에 공의 색깔 m개가 존재함

이러한 구성이 아래의 그림처럼

항아리 3개이고 공의 색깔은 4개이다.

이제 관측 백터에 대한 확률을 하나를 구해보자.

모델이 학습을 통해서 위와 같이 생성 되었다면,

관측 백터 O가 {진파, 연파, 검, 흰}이고

상태전이가 s1->s1->s1->s1 일때의 확률을 구하라

구하면 위와 같다.

그러면, 관측 백터 O가 {진파, 연파, 검, 흰} 나올 확률은 어떻게 구할까?

상태가 3개이고 4단계 이므로 나오는 확률의 경우의 수는 3^4 즉 81개이다.

이 81개의 확률을 모두 더해주면 관측 백터 O의 확률이 된다.

더하기다. 즉 그냥 Markov 모델은 곱하기인데, HMM은 더하기로 연산이 된다. 당연히 확률이 클 수 밖에 없다.

HMM의 예제 (2) 

여자친구의 삶 [Wikipedia]

-여자 친구의 일상을 관찰, V={산책, 쇼핑, 청소}

- 날씨는 {해,비} 2가지 상태 존재

- 수집한 정보는 아래와 같다.

답할 수 있는 문제

- 그녀가 일주일 연속으로 쇼핑만 할 확률은 ? (평가문제)

- { 산책, 산책, 청소 } 이렇게 했다면, 3일동안 날씨는 각각 어떠했는가 ? (디코딩 문제)

- { 산책, 산책, 청소} 했다면 오늘과 내일은 무엇을 할까? {복합적인 문제}

HMM의 구성요소와 세가지 문제

- 모델을 알고 있을 때 확률을 추론하라.(평가)

- 어느 것이 상태인가? 상태는 몇가지 인가? (아키텍쳐 설계)

- 확률 분포는 어떻게 구하나? (학습)

아키텍쳐 설계

HMM은 통상 가중치 방향 그래프로 표현 한다.

노드가 상태가 된다.

상태로 사용할 것이 명확한 경우도 있지만 그렇지 않은 경우도 있다.

대표적인 아키텍처

어고딕 모델과 좌우 모델

응용의 특성에 따라 적절한 아키텍처 선택이 중요

예를들어 음성인식은 좌우 모델이 좋다.

세개의 변수 결정

- 상태전이 확률 행렬 구성

- 관측 행렬 구성

- 초기 확률 백터 구성

세가지 문제점

평가: 모델 A가 주어졌을 때 관측 백터 O를 얻었을 때의 확률 P(O|A)는?

디코딩: 모델 A가 주어진 상화에서, 관측 벡터 O를 얻었을 때 최적의 상태열은 ? 역으로 가는 형태이다.

학습: 훈련집합을 가지고 모델 A를 도출 하는 과정이다.

HMM으로 Classficiation을 하는 방법은

Class 라벨마다 HMM을 생성해서 가장 높은 값을 가지는 Class 라벨로 prediction 하는 방법이 있다.

세가지 문제점에 적용 가능한 방법

평가: 동적 프로그래밍 이용

디코딩: 동적 프로그래밍 이용 (Viterbi 알고리즘)

학습: EM 알고리즘 (Baum-Welch 알고리즘)

평가: 동적 프로그래밍 이용

계산은 할 수 있어도

만약 관측 백터가 시퀀스 4이고 상태가 2이라면 (여자친구의 생활 패턴 문제)

2^4 = 16개를 계산 해야한다.

이것을 일반화 하면

상태수 n 관축 백터 O의 길이 T에 대해서

n의 t제곱 * t가 된다. 마지막 T는 더하기 연산 때문에 발생

동적 프로그래밍을 통한 중복 계산의 제거

비정상적인 데이터를 찾는 문제이다.

응용분야는

신용카드 사기, 전화 사기, 네트웍 침입, Fault Detection 등이 있다.

Challenge

얼마나 많은 outlier를 찾을 것인가?

unsupervised이므로 찾기가 어렵다.

가정

정상저인 데이터가 비정상보다 확연하게 더 많다.

Types of anomaly detection schemes

- model based or statistical approaches

- distance based

- Density based

1) model based or statistical approaches

일단 모델을 생성하던가 어떤 잘 알려진 분포를 따라야 한다.

normal distribution과 같이 특정 파라메터로 분포를 설명 할 수 있어야 한다.

이럴때 outlier란 결국 probability가 낮은 분포에 속하는 데이터가 된다.

아래와 같은 분포인 Gaussian distribution이 많이 사용된다.

파라메터는 mean과 standard deviation이다.

위는 PDF로

N(0,1)의 값을 나타낸다.

2차원 PDF를 나타내므로, 결국 원래 값은 1차원 분포인 것이다. 변수가 x 하나이다.

Statistical 접근법의 한계점

Attribute가 1개이다. 대부분

데이터 분포가 잘알려진 분포를 따르기가 쉽지 않다.

고차원 데이터 분포에서는 적용하기가 쉽지 않다.

2) Distance based approach

3) Density based LOF Approach 

Outliers in Lower Dimensional Projection

고차원에서는 빈공간도 너무 많고, proximity의 개념 자체가 잘동작 하지 않는다.

따라서 대부분의 point들이 outlier로 판별되는 문제가 존재 한다.

이것을 방지하기 위해서 Lower dimensional projection을 수행 해야 한다.

데이터들의 분포에서 어떠한 그룹을 찾는 것이 cluster Analysis 이다.

대표적인 Unsupervised learning 방법이다. 정답을 모르는 상태에서 데이터들의 분포를 가지고 그룹을 결정 하기 때문이다.

위와 같이 그룹을 생성 했을때 Cluster안에서의 각각의 Data들 사이의 거리는 작아야한다. 즉 조밀한 배치를 이루고 있어야 한다.

Cluster들간의 거리는 최대한 먼 상태가 좋은 것이다.

기본적인 Clustering의 종류는 다음과 같이 나뉜다.

1) Partitional Clustering

각각의 그룹이 overlapping 되어지지 않고 정확히 하나의 그룹으로 구성되는 형태를 의미한다.

2) Hierarchical Clustering

계층적인 트리 형태로 구성되는 것을 말하며 그룹이 중첩되서 클러스터를 이루는 형태를 말한다.

Clustering Algorithms: K-means and its variants

가장 기본적인 Clustering 알고리즘이다.

초기 K를 정해서 각각의 초기 중심을 잡는다.

각각의 초기 중심을 기점으로 흩어져있는 데이터들중에서 가장 가까운 것을 그 중심을 기준으로한 클러스터에 편입 시킨다.

각각의 클러스터에대한 중심을 새로 계산 한다.

모든 중심이 변하지 않을때까지 반복한다.

하지만 어떤 경우에서는 끝나지 않을 수도 있다. 

따라서 몇 %이상 변하지 않을 때 까지나, SSE를 계산해서 변화량을 볼수도 있고

iteration 횟수를 고정해서 줄 수도 있다.

특성은 아래와 같다.

partitional clustering approach: 정확히 하나의 그룹에만 들어가지는 형태이다. 오버랩핑 되지 않는다.

Each cluster is associated with a centroid (or center point)

Each point is assigned to the cluster with the closest centroid

Number of clusters, K, must be specified 

The basic algorithm is very simple

- Complexity O(n*K*I*d)

n: number of points

K: number of clusters

I: number of iterations

d: number of attributes

- 어려운점

K값을 알기가 어렵다.

distance measure에 너무 민감하게 작용 한다.

초기 값의 선택이 매우 중요 한다.

결국 K-means cluster의 성능은 초기 center point의 선택으로 좌우 하는데,

성능 측정 지표가 있어야 계속 중심 포인트를 변경해 가면서 테스트를 수해할 수 있다.

제안된 성능 측정 방식은

Sum of Squared Error (SSE) 

방법이다.

아중 시크마의 의미는 아래와 같다

만약 K가 3이라고 가정하자.

즉 3개의 클러스터로 분할하고 싶어서 3이라고 준것이다.

각각의 클러스터에서의 중심 즉 평균과 각각의 데이터 포인트들간의 distance를 계산해서 제곱한다음 합을 구해주게 된다.

이렇게 해서 다 더하기 때문에 위와 같은 더블 시크마 공식이 나오게 된다.

이렇게해서 구한 SEE를 가지고 초기 seed를 변경해 가면서 

더 좋은 cluster를 찾을 수 있게 된다.

하지만 SSE measure의 한계점도 존재한다.

이것은 Intra개념만을 포함한 수치이다.

즉 클러스터들 간의 거리는 고려하지 않았다. inter 개념이 빠졌기 때문에

SSE가 최적의 k-means cluster를 찾는 가장 좋은 measure 라고 할 수 없다.

초기 중앙 점을 찾는 문제

• 여러번 수행한다.

• 계층적 클러스터를 구성해서 시각적으로 분석한 다음 적절히 K를 설정한다.

• 의도적으로 더 많은 K를 설정한 다음 이중에서 적절히 초기 K를 선택한다. 즉 가장 넓게 분할되는 K를 선택 하는 거이다.

• Bisecting K-means 알고리즘을 수행 한다. Not as susceptible to initialization issues

Bisecting K-means

하나의 클러스터에서 출발해서 반복하는 숫자만큼 클러스터를 분할하는 방법이다.

bisection에서 가장 작은 SSE를 가지는 2개의 클러스터를 list of clusters로 추가한다.

이 작업을 cluster 리스트가 K 클러스터를 포함할 때 까지 반복 하게 된다.

아래는 Bisecting K-means를 수행 했을 때의 그림이다.

기본적인 K-means algorithm의 문제는 바로 empty cluster의 생성 이다.

즉 클러스터를 계속 생성하는데, 가장 가까운 data가 하나도 없는 경우가 과정중에 자주 발생한다.

이때 어떻게 처리할 것인가?

해결방법

가장 멀리있는 포인트로 새로 시작

가장 높은 SSE로 새로 출발

동시에 몇개의 empty cluster가 발생하면 위가정을 몇번 더 반복 한다.

한번에 하나씩만 Center들을 업데이트 하는 방법. 시간이 오래걸리지만 empty는 생성되지 않는다.

Limitations of K-means

1) Differing Size 문제

크기가 서로 다른 클러스터를 만들어야 할 때 그렇게 하지 못하고,

큰것을 분할하는 성향이 강하다.

2) Differing Density

각각의 클러스터가 밀도가 서로 다르다면 문제가 또 발생 한다.

3) Non-Globular Shapes

구형태를 추구하는것이 K-means Algorithm의 특징이다. 

하지만 구형태가 아니라면 문제가 발생 한다. 

극복방법: 많이 쪼개서 합치는 방법이다. 아래와 같이

Hierarchical Clustering

중첩된 클러스터들로 구성된 계층적인 트리를 생성 한다.

시각적으로 볼 수 있는 특징이 있다.

생성하면 아래와 같은 모습을 볼 수 있다.

이러한 시각적인 모습을 통해서 적절히 클러스터를 생성 할 수 있다.

따라서 K를 설정할 필요가 없게 된다.

2가지 종류의 전략

Agglomerative:

Start with the points as individual clusters

At each step, merge the closest pair of clusters until only one cluster (or k clusters) left

단, 하나의 cluster가 남을 때 까지 이 방법을 반복 한다.

Divisive:

Start with one, all-inclusive cluster

At each step, split a cluster until each cluster contains a point (or there are k clusters)

Distance 또는 similarity matrix를 사용해서 clustering 과정을 수행 하게 된다.

클러스터를 합칠 때 어떻게 클러스터들간의 Similarity를 계산 할 수 있을까?

• MIN

• MAX

• Group Average

• Distance Between Centroids

• Other methods driven by an objective function

object function means that an measure such as SSE

각각의 방법을 그림으로 표현하면 아래와 같다.

예제

Min (single llinkage)으로 계산해 보자.

5개의 point data에 대해서 similarity를 모두 계산한다.

min이니 가장 가까운 것을 합치게 된다.

similarity 가 1이면 가장 높은것을 의미 한다.

1 v 2 : 3 (0.1 or 0.7)

1 v 2 : 4 (0.65 or 0.6)

1 v 2 : 4 v 5 (0.65 or 0.5)

1,2,4,5의 경우 조합의 수는 총 4가지 이다. 왜 이것을 고려 하지 않을까? 이유는 둘중 가장 Similarity가 큰 것을 골랐기 때문에 나온 결과 2개중 하나만 고르게되면 이미 그것이 Similarity가 가장 큰것이 된다.

3 : 4 v 5 (0.4 or 0.3)

최종적으로 Min 방식인 둘 사이의 유사도가 가장 큰것을 합치는 방식으로 했을 때의

계층적 트리는 아래와 같다.

큰것에서 작은것으로 쪼개는 방식이다.

MST를 생성한다음 쪼개면서 수행하게 된다.

Density-based Clustering 

밀도가 가장 낮은 영역에 의해서 두개의 밀도가 높은 영역으로 분할되는 클러스터링을 말한다.

DBSCAN 이 대표적인 알고리즘이다.

Density는 EPS즉 어떤 radius 안에 있는 point들의 수를 말한다.

core point를 결정하는 것이 중요한데

이것은 EPS 안에 특정 최소한의 포인트의 개수보다 더 높은 포인트들이 있을때 이것을 결정하는 EPS를 코어라 한다.

border point는 특정 포인트 개수 보다는 적지만 코어 포인트의 이웃일때를 의미한다.

noise 포인트의 경우 코어도 아니고 border도 아닐 때를 의미 한다.

Eps =1 

MinPts = 4 

일때의 값일때의 DBSCAN의 모습이다.

보통 비지니스에서 거래의 결과를 분석하기 위해서 많이 쓴다.

가장 성공적인 사례가, 아기 기저귀 옆에 맥주이다.

기저귀를 사고 맥주를 많이사는 연관 관계를 찾아낸 것이다.

위와 같이 거대한 데이터 셋에 숨어 있는 재미있는 관계가 존재할 수 있다.

Bioinformatics, medical diagnosis, Web Mining, 그리고 Scientific data analysis.

Earth science data의 경우 ocean, land 그리고 atmosphere processes간의 재미 있는 관계를 파악할 수 있다.

각각의 Earth system element들이 서로 어떻게 상호 작용하는지을 알아 낼 수 있기 때문이다.

비록 이겨서는 market basket data를 가지고 설명하지만, 다양한 분야에 적용할 수 있음을 염두 해야 한다.

Association analysis를 market basket data에 적용하려 할때 생기는 큰 2가지 이슈가 있다.

1) pattern을 거대한 거래 데이터로 부터 찾아내는것은 많은 컴퓨팅 파워를 필요로 한다.

2) 발결된 패턴이 거짓일 수도 있다.

따라서, 어떻게 효과적으로 마이닝을 할 것인가와

어떻게 이러한 생성한 연관 규칙을 평가해서 거짓을 찾아낼 것인가에 대한 것으로 나눠서 설명 한다.

Apriori Algorithm

Association Rule이라고 하면 가장 기본적으로 배우는 알고리즘이 Apriori Algorithm이다.

위의 요소로 했을 때 Support와 Confidence를 계산해 보자.

X->Y 라는 규칙이 있다고 할 때

Support(s)의 경우 X와 Y가 존재하는 transaction의 수를 의미한다.

Confidence(c)의 경우 X를 포함하는 Transaction중에서 Y를 포함하는 것의 수를 의미 한다.

각각에 대해서 계산 하면 아래와 같다. 

Confidence는 당연히 생성괸 규칙의 신뢰성을 의미하므로 높을 수록 좋다고 할 수 있다.

X->Y 일때의 가능성의 1이면 가장 좋은 것이다.

Rule Mining Task

최소 support와 최소 confidence를 지원하기 위해서 그것을 데이터 셋속에서 찾아내는 것이 중요하다.

가장 기본적인 알고리즘은 Brute-force approach 이다.

하지만 이 방법은 계산 복잡도가.

이므로 실제 사용하기가 어렵다.

위 같은 예제를 Brute-force approach로 계산할 경우 602번의 계산 연산을 필요로 한다.

모든 support 값이 0.4 이다.

결국 Itemset이 같기 때문이 발생하는 문제점 이다.

따라서 support와 confidence를 decouple하여 계산하면 계산의 복잡도를 줄일 수 있다.

4개의 원소에 대한 부분집합의 갯수는 2^4으로 16개이다.

각각은 아래와 같다.

Brute force approach를 계산하는 복잡도는

O(NMw) 인데 여기서 M이 2^d므로 그 복잡도를 무시할 수가 없다.

Apriori Algorithm

Mining Association Rule은 크게 2단계로 이뤄 지며 각각에 대해서 최적화를 하는 방법을 다루겠다.

1) Frequent itemset generation

원칙

만약 어떤 아이템셋이 빈번한 빈도를 가진다면 그것의 부분집합들은 반드시 빈번한 빈도를 가진다.

이 말의 의미는 당현이 ABC의 support가 50이 넘었어서 frequent itemset으로 정해졌다면,

그것의 부분집합인 AB와 BC 같은 것들의 support는 당연히 50을 넘는 다는 의미이다.

이것을 다시 정리하면 아래와 같은 수식을 얻는다.

어떤 item-set의 support 값은 절대로 그것의 subset들의 support 값을 초과할 수 없다는 의미를 가진다.

이러한 특성은 anti-monotone이라는 특성으로 잘 알려져 있다.

이러한 특성을 통해서 pruning을 할 수 있다.

만약 AB가 infrequent 하다면 그것의 subset은 모두 계산할 필요도 없다.

Algorithm

2) Candidate Generation

1단계: Candidate Generation

새료운 후보 아이템 셋 k개를 빈도 아이템 셋 k-1개에서 뽑아낸다.

2단계: Candidate Pruning

support-based pruning 전략을 사용해서 

후보 k-itemset을 제거 한다.

support 값에 기반해서 pruning은 할 수 있는데 추가로 중복값을 제거하는 것도 중요 하다.

Candidate 생성 방법

Brute force method

모든 k 아이템에 대해서 생성할수 있는 Candidate로 고려 한다.

레벨 3으로해서 즉 k=3

d가 6개라고 하면, Brute force method로 할 경우

 의 조합으로 계산을 해야 한다. 20개가 후보가 되고 아래와 같이 많은 후보군이 생성 된다.

후보군을 생성하는 것 자체는 복잡한 일이 아니지만, 그것을 pruning 하는것은 복잡한일 이다. 그래서 이방법은 좋지 않다.

F_k-1 X F_1 Method

3) Rule Generation

만약 4개의 속성이 있다면 그것에 대한 rule은 아래와 같다.

그리고 |L|의 숫자는 k이고 이것은 2^k 이다.

어떻게하면 효율적으로 rule을 frequent itemset으로 부터 생성할 수 있을까?

일반적으로 confidence는 anti-monotone한 성질이 없다.

c(ABC->D)는 c(AB->D)보다 클수도 잇고 작을 수도 있다.

하지만, 같은 itemset으로 부터 생성된 rule의 confidence는 anti-monotone한 성징을 가진다.

Confidence는 오른쪽의 아이템 숫자에 관해서 anti-monotone한 성질을 가진다.

약간 반대의 개념이 된다. support pruning일 때와

왜냐하면 support가 크다면, confidence 계산은 분모가 커지므로 값이 작아 지기 떄문이다.

위 처럼 subset이 high confidence를 가지지 않을 경우 그것의 superset은 그것보다 작은 confidence를 가지기 때문에 pruning의 대상이 된다.

앞선 support와 반대의 개념을 가지는 것을 알 수 있다.

핵심은 RHS의 super와 sub의 관계를 봐야한다는 것이다. 왼쪽이 아니라 오른쪽이다.

Apriori Algorithm의 Complexity

Choice of minimum support threshold

- lowering support threshold results in more frequent itemsets

- this may increase number of candidates and max length of frequent itemsets

Dimensionality (number of items) of the data set

- more space is needed to store support count of each item

- If number of frequent items also increases, both computation and I/O costs may also increase

Size of database

- since apriori makes multiple passes, run time of algorithm may increase with number of transactions

Average transaction width

- Transaction width increases with denser data sets

- This may increase max length of frequent itemsets and traversals of hash tree (number of subsets in a transaction increases with its width)

연습문제 (exercise)

min-support = 2/10 일때 Frequent itemset을 구하라.

 {e} = 8 / 10

 {b,d} = 2 / 10

 {b,d,e} = 2 / 10

계산해 본결과 subset들이 당연히 support 값이 더 높거나 같았다.

위와 같은 공식을 가지고 아래 계산을 수행해 보자.

{b,d,e} 총 6개가 생성 된다.

{b,d,e}의 support는 2/10으로 minsup를 만족하기 때문에 frequent itemset으로 고려 한다.

b,e -> d  2/5

d,e -> b 2/5

e -> b,d x  2/8  (b의 superset)

d -> b,e x  2/6  (b의 superset)

b->d,e 2/6 (e의 superset)

b,d->e  2/2

FP-growth Algorithm

이것은 FP tree라고 불리우는 것을 사용 하는 것이다.

FP tree를 생성한 다음에 divide and conquer 방법을 통해서 frequent itemset을 찾을 수 있다.

일단 item 셋들을 아래와 같이 support count가 내림차순으로 정렬 한다.

왜냐하면 맨 첫번째 아이템이 root node가 되므로 가장 빈번한 아이템 셋으로 시작하는것이 tree가 올바르게 그려지게 된다.

그렇지 않으면 root에서 너무 많은 branch들이 생성되서 tree 생성이 복잡하며 해석이 어려워 진다.

이제 각각의 Transaction을 이용해서 tree를 생성하면 아래와 같다.

생성방법

이렇게 만들어진 tree를 이용해서 이제 frequent itemset을 생성 하게 된다.

바닥에서 top으로 점진적으로 올라가면서 그것을 찾게 된다.

recursive divide and conquer 방법을 이용해서 하게 된다.

de, ce, be, ae 로 끝나는 것들에 대해서만 그것을 찾게 된다.

모든 path의 node가 다 처리 될 때까지 반복 한다.

어떤 특정 경우에서는 FP-Growth algorithm이 apriori algorithm보다 성능이 수십배가 좋게 된다.

단점으로는 tree가 메모리에 모두 올라가야 하므로 압축률이 좋아야 한다. 

너무 큰 데이터 사이즈에 대해서는 수행이 쉽지 않다.

예제

minimum support count: 2

우선 e로 시작 한다.

위와 같이 생성된 tree를 가지고 e로 끝나는 포인트들을 찾으면 3개가 있다.

3/10 support를 가지므로 minsup를 만족 한다.

따라서 frequent itemset이다.

트리를 재조정 한다.

1) prefix 노드들을 e를 가지는 것들에 대해서만 고려해서 frequency count를 업데이트 한다. 

-> 그냥 단순히 트리 경로를 계산 하는것이 아니라 가지고 있는 데이터 샘플 중에서 e를 포함한 경로들을 카운트 해줘야 한다.

2) 노드 e를 제거 한다.

3) 모든 infrequent item을 제거 한다.

최종적으로 아래와 같은 모습이 된다.

e를 위한 FP-tree로 부터 prefix path가 d인것들만 다시 수집 해서 tree를 형성 한다. 

여기서 다시 계산을 해보면 d가 frequent itemset인 것을 알 수 있다.

따라서, {d,e}는 frequent itemset이 된다.

빈도수를 d를 포함하는 것들로만으로 재종함.

d를 제거함

infrequent itemset을 제거함. 그럼 c가 제거대고 아래와 같은 FP-tree가 구성됨. 

이 트리를 이용해서는 {a,d,e}를 뽑아 낼 수 있다.

이제 e->d는 모두 했으니,

다른 경로인 e->c를 수행 하자.

c를 시작으로하는 것으로 tree를 구성한다.

c는 frequent itemset이다.

따라서 {c,e}로 설정 된다.

그다음 {c,e}를 가지고 FP-tree를 구성 하게 되면

c에 의해서 발생된 것들에 대해서만 빈도수를 재조정하고

c를 제거한다음

infrequent itemset에 대해서 설정을 하면 null만 아래 처럼 남는 FP-tree가 구성 된다.

마지막으로 a를 prefix path로 고려해서 시작하면

위와 같은 tree를 구성하며 a가 frequent itemset이기 때문에

{a,e}는 frequent imtemset이 된다.

이제 suffix e에 대한 FP-tree를 이용한 Divide and conquer 방식을 모두 수행 했다.

최종적으로 찾아낸 frequent Itemset은

{e}, {d,e}, {a,d,e}, {c,e}, {a,e} 이다.

이러한 과정을 suffix 

d,c,b,a,에 대해서도 모두 수행하면 아래와 같은 표를 얻을 수 있다. 

Conditional Probability를 이용해서 Classifier를 구현 하는 방법이다.

이번 장에서는 Theorem에 대해서 주로 다루고 실제 구현은 R을 통해서 수행한다.

구현 부분이 궁금하다면 Naive Bayes Classification with R을 보자.

Conditional Probability 계산법

$$P\left( { C }|{ A } \right) =\frac { P(A\cap C) }{ P(A) } $$

이라면, A일때 C의 확률을 구하는 조건부 확률 문제이다.

하지만, A 조건이 결합 확률로써 여러 조건들이 연속적으로 발생 할때의 확률이라면 계산하기는 쉽지 않다.

이때 Bayes Theorem을 적용하면 쉽게 계산을 할 수 있게 된다.

이 알고리즘은

P를 정확히 계산할 수 있다는 전제 하에 가장 성능이 좋은 알고리즘으로 알려져 있다.

하지만 이것은 이론상 그런것일 뿐 실제로는 P를 정확히 계산하기 어렵기 떄문에 그렇지는 않다.

Bayes Theorem의 기초 문제

팀 0은 65% 승리, 이중 30%만이 팀1의 Home 장소에서 이긴것이다.

팀1의 경우 35%의 승리가 있고 그중 75%가 자신의 홈에서 승리한 것이다.

이러한 상황에서 

팀 1이 팀0의 홈에서 경기를 한다면 확률상 어느 팀이 승리할 것인가?

해설

X는 홈이 되는 팀을 나타낸다.

Y는 경기에서 승리한 팀을 나타낸다.

이럴때, X와 Y는 각각 {0,1}사이의 값을 가질 수 있다.

P(Y=0) = 0.65

P(Y=1) = 0,35

P(X=1 | Y=1) = 0.75

P(X+1 | Y=0) = 0.3

이것을 예측하기 위해서는 다음과 같다.

P(Y=1|X=1)와 P(Y=0|X=1) 이 둘의 확률을 계산해서 더 큰 쪽으로 Prediction 하면 된다.

계산 방법은 아래와 같다.

Bayesian Classifier

Bayes Theorem을 이용해서 모든 class에 대한

posterior probability를 계산하여 classifier를 만드는 것이다.

그런다음, 각각의 Class에 대한 확률 값 P중에서 최대가 되는 것을 선택해서 예측 하게 된다.

Bayes theorem을 쓰면, 원래 수식 보다는 조건부가 더 간단해져서 계산하기 쉽지만, 

그래도 여전히 아래와 같이 Joint Probability 이므로 계산하기 쉽지 않다. 

Naive Bayes Classifier 

Unseen Data가 들어 오면, Traning Data를 그대로 사용하여 majority voting을 통해서 class를 결정하는 방법을 말한다.

구현을 위해서 필요한 사항

1) 트레이닝 데이터들을 모두 보관한다.

2) Distance Metric을 사용하여 Unknown record와의 거리를 계산 한다.

3) k개의 neighbor와 반복해서 Distance를 계산 한다.

4) 최종적으로 Majority voting을 통해서 prediction 한다.

입력된 테스트 데이터 (x', y')과 Traning Data (x,y)와의 distance 또는 Similarity를 계산 한다.

그다음 nearest - neighbor list로 구성된 D_z가 발견되면, D_z 내에서 majority voting을 통해서 class를 파악 한다.

Majority voting 방법은 아래와 같다.

위 식에서 

v는 + 또는 -와 같은 어떤 class label을 나타냄.

y_i는 nearest neighbors의 class label이다. 

I() 함수는 true 이면 1을 아니면 0을 return하는 indicator 이다.

위와 같은 경우 아래와 같이 된다.

는 최대가 되는 argument 즉, v를 return 하는 것이다.

K-NN의 특징

결국 Distance metric을 이용해서 nearest neighbor를 계산하는 방법이기 때문에 Distance metrix에 다분히 의존적인 방법이다.

보통 사용하는 Distance Metric은 아래와 같다.

위 Metric 중에서 우리가 Euclidean을 사용 한다면, 아래와 같은 문제점이 생길 수 있다.

□ Scaling issues: Distance measure를 사용 하므로 이러한 문제가 발생 한다.

모든 크기를 0~1 사이로 맞추는 방법을 사용할 수있다.

Mahalanobis distance를 사용하는것이 해결 방법이 될 수도 있다.

□ High Dimensionality: curse of dimensionality

위와 같이 2개의 Euclidean measure는 동일한 값을 나타낸다.

하지만,

0은 의미 없는 값이라고 했을 때 0이 많다고해서 두개가 유사한것은 문제가 된다.

이것을 보정하기 위해서 vector의 길이로 각각을 나누어 준다.

첫번째 vector의 length = 

두 번째 vector의 length = 

이것으로 각각을 계산하면

□ Laze Learner의 방법

명시적으로 model을 생성하지 않으므로 상대적으로 online prediction time이 길어 진다.

performance에 영향을 주는 factors

Distance metric의 종류

K의 수를 얼마로 정할 것인가 이다.

어떻게 성능을 측정할 것인가?

이것은 Learning 알고리즘에 의존적인 문제이다. 생각해 볼 수 있는 지표들은 아래와 같다.

Class of distribution: 균등함의 정도를 나타낸다.

Cost of misclassification

Size of training and test sets

Holdout 방법 

Reserve 2/3 for training and 1/3 for testing 으로

Metrics for Performance Evaluation

Computing Cost of Classification

주어진 Cost  Matrix

Sensitivity and Specificity

바이너리 classification test에서 주로 사용 하는 통계적인 measure가 Sensitivity와 specificity 이다.

Wikipedia: URL

Sensitivity는 

True positive rate

recall

로 불린다.

Specificity는

True negative rate

예측한것 들 중에서 실제로 negative 인것 / 전체 negative 인것

좀 더 읽어보기

Practical Machine Learning post

Receiver Operating Characteristic, Cross validation

Classification은 미리 정의된 카테고리들 안으로 어떤 하나의 object를 어사인하는 작업을 말한다.

이것은 많은 응용들이 가지는 문제에 적용 되어 질 수 있다.

예를 들면, spam 찾기, 세포의 malignant 구분, galaxy의 종류 구분 등에 적용 할 수 있다.

이러한 것들은 supervised learning의 한 종류이며,

가장 간단한 형태인 Decision Tree에 대해서 다루도록 하겠다.

Hunt's Algorithm

해당 알고리즘을 이해하기 위해서 채무 불이행 (Defaulted Borrower)문제를 풀어 보도록 하자.

D_t는 node t와 연관된 training record들의 set이라고 하자.

y = {y1, y2, ... yc}는 class label들 이라고 하자.

위와 같은 조건하에서 아래와 같이 Algorithm을 정의 한다.

Step1: 

D_t에 있는 모든 레코드가 같은 class y_t륵 가진다면, t는 어떤 leaf node가 되고 y_t로써 labeling 되어 진다.

Attribute test를 또 할필요도 없이 impurity가 0이므로, 즉 100%인 것이다. 논란의 여지 없이 leaf node를 y_t로 만들면 된다.

Step2: 

    만약 D_t가 empty set이라면, t에서의 leaf node는 default class y_d로 라벨 되어 진다.

y_d는 전체에서 다수의 test set을 가지는 것을 말한다.

Step3:

D_t에 있는 레코들이 두개 이상의 y_t 클래스를 가진다면, attribute test를 사용해서 data를 더 작은 subset들로 분할 한다.

이 작업을 나눠진 각각의 subset에대가 반복 한다.

핵심은 이 attribute test로 적절한 condition을 찾는 것이다.

위의 이전 데이터를 가지고 아래의 Decision Tree를 생성하는 과정을 보여 준다.

(a)를 보면 채부 불이행(Defaulted)가 No이다. 이러한 의미는 모든 사용자가 대출이 가능하다는 것을 뜻한다.

(b)와 같이, Home Owner를 Root로 해서 더 작은 Subset으로 나눠지는 형태의 트리를 구성 한다.

이렇게 어떤 Root 노드를 선택할 것인지에 대한 Attribute test에 관한 이야기는 나중에 다룬다. 일단 저렇게 했다고 생각하자. 

단지, HomeOwner는 spliting을 하기 위환 best criterion이라고 생각하자.

Hunt's Algorithm은 이제 다시, 각각의 child node들의 root에 똑같은 방법을 다시 적용하게 된다 (recursively).

(c)에서 HomeOnwer =yes 인 사람들은 모두 Defaulted = No 이므로 더이상 분할 하지 않는다.

하지만 오른쪽의 경우 즉 HomeOwner=No인 경우를 보면, 

총 7개의 Training Data중에서 

3개의 Defaulted = Yes

4개의 Defaulted = No 로 구성 되어 진다.

따라서 단일 class로 구성 될 때 까지 계속 분할 해야 한다.

이러한 작업을 반복하면 (d)와 같은 모습을 나타내게 된다.

Measures for Selecting the Best Split

가장 최적의 split way를 찾는 문제는 많이들 연구를 해왔다. 이중 몇가지를 소개 하겠다.

p(i|t)라는 것을 t 노드에서의 i class의 비율이라고 생각하자.

C0에 대해서 10개의 레코드가 있고,

C1에 대해서 10개의 레코드가 있다고 하면

P(C0,C1)은 P(0.5, 0.5)가 된다. 동일한 수의 레코드가 각각의 class에 대해서 존재하기 때문이다.

하지만, 이것을 하나의 Attribute를 기준으로 Split하게 된다면 아래와 같은 Tree 형태로 나타내어 진다.

이떄 과연 우리는 무엇이 더 좋은 구조라고 말 할 수 있는가.

이것을 measure 하기 위해서 impurity라는 개념을 도입 한다.

impurity란 class의 분포가 skewed (편향됨) 한 정도를 나타낸다.

즉, impurity가 높다는 것은 평향되지 않다는 것을 의미한다.

P(0,1)이 zero impurity를 가지며, P(0.5, 0.5)가 가장 높은 impurity를 가진다.

Gain이 클려면 결국, M12, M34와 같은 Impurity가 낮아야한다.

그리고 M12, M34를 구하기 위해서는 weighted average를 이용해서 구하게 된다.

결국 impurity가 높다는것은 error가 높다는 것을 의미한다, 편향됨의 정도가 높아야 prediction 했을 떄의 error가 적게 된다.

이러한 impurity를 measure는 지표는 아래와 같다.

위 식에서 c는 number of classes가 된다.

위식과 weighted average를 이용해서 각각을 split node를 찾기위한 수식은 아래와 같다.

주어진 Node t에서의 GIni Index는 아래와 같다.

P(j|t)는 t의 노드에서 j 클래스의 빈도를 나타낸다.

최대의 경우 n_c가 클래스의 총 숫자를 나타내는데, 모든 래코드가 모든 클래스에 대해서 분포를 가진다면, 그 때 GINI indext가 가장 큰 값을 나타낸다. 즉, 10개의 클래스가 존재하는데 해당 노드 t에서 포함되는 모든 레코들이 10개의 클래스에 대해서 모두 분포를 가지고 있다며, 이때 가장 impurity가 높게 되는 것이다. 이러한 때를, least interesting information 이라 한다.

최소의 경우, 모든 record가 단 하나의 클래스만을 가지고 있을 때이다. 이때는 0이되며, most interesting information 이라고 한다.

어떤 노드 p에서 k partitions (children)으로 split 할때 split의 quality를 다음의 수식으로 계산 한다.

n_i / n은 weighted average를 구하기 위한 수식 이다.

주어진 노드 t에 대해서 Entropy 계산은 아래와 같다.

위 식의 의미를 살펴 보면,

의 식이 계속 확률에다가 곱해지는 형태가 된다. 즉 확률이 크면 클수록 로그값이 작아진다,

따라서 확률이 높은 것들은 확률을 낮춰주고, 확률이 낮은것들은 확률을 높여주게 된다.

이것을 이용해서 사용되어지는 평균 비트수를 줄일 수 있다고 한다.

허프만 코드 적용에 유용하게 사용 할 수 있다.

Information Gain

Parent Node p is split into k partitions

n_i is number of records in partition i

node t에서 Classification error를 이용하는 방법.

계산 방법 예제

Binary Classification Problem에 대해서 3개의 measures를 기하학 적으로 표현 하면 아래와 같다.

x축은 p의 확률 이며,

y축은 impurity 이다.

Gini의 경우에 살펴보면,

C0: P

C1: 1-P

Gini Index의 정의에 따르면 Impurity 수식은

의사결정트리 분석의 장점

결정트리를 통한 데이터 분석의 결과는 나무(Tree) 구조로 표현되기 때문에 분석가가 결과를 쉽게 이해하고 설명할 수 있는 장점이 있다. 

분류율에 대한 정확도만 따지자면 신경망(Neural Network) 또는 로지스틱 회귀분석 등의 분류 방법들 보다 낮게 평가되기도 하지만 결과를 쉽게 이해하고 설명할 수 있으며 의사결정을 하는데 직접적으로 사용할 수 있는 장점이 있기 때문에 데이터마이닝 적용시 매우 많이 사용되고 있다. 

의사결정트리 분석의 한계

일반적인 결정트리 알고리즘은 갖는 한계, 단점을 아래에 나열하였다. 

[1] 데이터의 특성이 특정 변수에 수직/수평적으로 구분되지 못할 때 분류율이 떨어지고, 트리가 복잡해지는 문제가 발생한다. 신경망 등의 알고리즘이 여러 변수를 동시에 고려하지만 결정트리는 한 개의 변수만을 선택하기 때문에 발생하는 당연한 문제이다. 

[2] 결정트리는 Hill Climbing 방식 및 Greedy 방식을 사용하고 있다. 일반적인 Greedy 방식의 알고리즘이 그렇듯이 이 방식은 최적의 해를 보장하지는 못한다. 

[3] 약간의 차이에 따라 (레코드의 개수의 약간의 차이) 트리의 모양이 많이 달라질 수 있다. 두 변수가 비슷한 수준의 정보력을 갖는다고 했을 때, 약간의 차이에 의해 다른 변수가 선택되면 이 후의 트리 구성이 크게 달라질 수 있다.  

Data Type

categorical or qualitative attribure

Nominal: values that are distinct symbols

ex: ID numbers, eye color, zip codes

Ordinal - possible to rank the categories

ex: height in (tall, medium, short)

numeric or quantitative attribure

interval: values that are ordered and measured in fixed and equal units

ex; calendar dates, temperatures in celsius or fahrenheit

ratio: treated as real numbers

ex: length, mass, counts

Attribute values의 특성

Nominal attribute는 distinctness 로 구별이 가능한 것들을 말한다.

Ordinal attribute는 distinctness & order 이다. 

Interval attribute는 distinctness, order & addtion

Ratio attribute: all 4 properties

Types of data sets

- Record data

레코드들이란 고정된 attribute들의 집합으로 구성 된 것들을 말한다.

- Data Matrix

여러개의 dimension을 지원하는 데이터 형태이며,

각각의 dimension들은 하나의 distinct attribute가 된다.

- Document Data

각 도큐먼트들은 어떤 'term' vector가 된다.

각각의 term들은 백터의 컴포넌트가 된다.

- Transaction Data

레코드 데이터의 특별한 타입을 말한다.

- Graph Data

HTML 이나 Web에서 주로 사용 한다.

- Ordered Data

Genomic sequence data

Data pre-processing

Aggregation

Sampling

Dimensionality Reduction

Feature selection

Feature extraction

Discretization and Binarization

Attribute Transformation

The curse of Dimensionality

Dimension이 증가하면 전체 공간에서 data가 차지하는 비중이 작아 지게 된다.

Similarity and Dissimilarity

Similarity

두 데이터가 numerical 할때 둘 사이의 유사도를 비교하는 것이다.

값이 높다면 좀더 유사하다고 할 수 있다.

이것은 [0,1] 사이의 값을 가진다.

Dissimilarity

Numerical measure에 대해서 두개의 object들이 얼마만큼 다른지를 판별 한다.

낮은 값은 좀더 alike 하다고 할 수 있다.

최소의 dissimilarity는 0이다.

최대는 보통 제한이 없다.

1로 맞추기 위해서는 range를 알아서 그 값으로 나누어야 하는데, 구지 그러한 노력을 하는 것이 큰 의미가 없기 때문이다.

Distance의 종류

• Euclidean
• Minkowski 
• Mahalanobis 

Euclidean Distance

백터의 개념을 집어 넣을 수 있기 때문에,

n은 dimensions(attributes)의 수이다.

하나의 attribute들이 x,y,z,... 이 되고

이것들이 각각 차원이 되므로

공간상에 두 점을 잊는 백터의 길이가 Euclidean Distance라고 할 수 있다.

예제를 통한 계산

p1과 p2

Minkowski Distance 

Mahalanobis Distance  

co-variance (공분산)을 구하는 방법.

m은 데이터의 갯수를 의미한다.

i는 하나의 attribute, 하나의 dimension을 의미하고

j는 또 다른 하나의 Attribute를 의미한다.

각각의 데이터를 평균과 뺀 다음 둘을 곱한것들의 합이기 때문에

양수가 나오는 경우 (+)(+), (-)(-) 형태의 데이터가 많은 것을 나타내며,

음수가 나오는 경우 (+)(-), (-)(+) 형태의 데이터가 많은 것을 나타낸다.

따라서,

Covariance가 양수면 두개의 attribute들이 비례 관계를 가지는 것을 의미한다.

음수라면, 두개의 attribute들이 반비례 관계를 가지는 것을 의미한다.

마지막, 

의 뜻은

각 dimension에서의 covariance combination을 타나내는 matrix을 의미한다.

two dimension의 경우 2x2 matrix이 생성 되고

n dimension의 경우 nxn의 matrix이 생성된다.

Distance와 Similarity 사이 에서의 일반적인 성질에 다해서 다루워 보겠다.

Cosine Similarity

Binary Vector의 경우

Simple Matching Coefficient (SMC)

number of matches / number of attributes

Jaccard Coefficient (useful for asymmetric attribute)

J = number of 11 matches / number of not-both-zero attributes values

Correlation

Classification technique 의 한 종류이다.

statistical learning theory에 근간을 두고 있다.

해당 알고리즘은 많은 실제 응용프로그램에서 높은 성능을 나타내게 된다.

handwritten digit recognition to text categorization 등에 사용된다.

curse of dimensionality에 강건한 모습을 가진다.

이것의 unique한 ascpect는

traning data의 subset만을 가지고 decision boundary를 결정 한다는 점이다.

이러한 training data의 subset을 support vector라고 한다.

일단은 linearly separable data를 가지고 linear SVM을 트레이닝 하는 방법을 배운다.

Linear SVM: Separable Case

그다음 non-linearly separable data에 대해서 SVM을 이끌어내는 방법을 배운다.

아래와 같이 2개의 영역으로 Classification 하는 문제에서

Hyper-plane은 무수히 많이 나올 수 있다.

이중 최적의 Hyper-plane은 무엇 일까?

그것은 아래와 같이 최대의 margin을 가지는 hyper plane일 것이다.

이렇게 최대 마진을 가지는 B1은 B2보다 노이즈에 강건하기 때문에 좋은 성능을 가지게 된다.

즉, generalization error가 적어지는 효과가 있다.

이러한 최대 margin을 가지는 hyperplane을 찾는 방법은 아래와 같다.

Wiki 피디아

Linear Decision Boundary

각각의 Example의 Tuple (xi,yi) 이다. i는 1,2,...N 이다.

그리고 전통적으로 y는 2개의 class 문제로써

이럴때 Decision Boundary는 아래와 같이 정의 된다.

여기서 w와 b는 모델의 파라메터가 값이 된다.

b는 bias로 threshold 값이 된다.

결정을 할때 특정 임계값을 줘서 그 강도를 조절 할 수 있다. 

위 그림은 이차원 training set 데이터를 나타낸다. 각각의 training data들은 사각형과 원형을 가지고 있다.

만약 2개의 점이 decision boundary 안에 위치 한다면, 아래의 식을 만족 한다.

여기서 x_b - x_a는 

Decision boundary와 병렬인 어떠한 벡터가 된다. 그리고 이것은 x_a에서 x_b로 직접적으로 가게 된다.

w와의 dot product는 0이기 때문에 벡터 w의 방향은 decision boundary와 반드시 직교하게 된다. 이것의 그림은 위와 같다.

이제 x_s는 decision boundary의 위에 위치 한다고 하고 우리는 이것을 아래와 같이 기술 할 수 있다.

Margin of a Linear Classifier 

Dual Problem

기존의 문제가 Lagrange multipliers를 이용해서 Dual problem으로 변경 되어 질 수 있다.

Linear SVM: Non-separable Case

이전에 정의한 decision boundary는 mistake-free 한것들만 정의 했었다.

하지만, 소수의 데이터가 대부분의 데이터 보다 너무 멀리 떨어져있고, 이것이 Noise일 가능성이 있다면,

어느정도 이러한 noise들을 무시하는 tolerable to small training error를 가지는 SVM을 설계할 수있다. 이것을 soft margin이라고 한다.

더욱이 not linearly separable 하다면 이러한 soft margin은 더더욱 필요하게 된다.

Nonlinear Support Vector Machine

이제는 아에 not linearly separable data들에 대해서 다루도록 하겠다.

이때는 original coordinate space x를 아에 새로운 space로 transform 하게 된다.

아래의 기존 2차원 space를 transform 하게 되면,

더 높은 dimensional space로 변경하게 되면 아래와 같이 된다.

이것은 linearly separable data의 분포로 변경이 되어진다.

Kernel Method

하지만 위와 같은 transform 되는 higher dimensional space의 존재 여부를 알아내는 것이 매우 어려운 문제가 된다.

이것을 해결하기 위해서 Kernel Method를 사용하게 된다.

이것을 통해 의 존재를 알 수 있다.

Characteristics of SVM

Try to find the global minimum of the objective function

 - ANN tends to find locally optimum solutions

SVM is an algorithm for binary class problem

How to apply for multi-class problems

- one-against rest approach

- one-against-one approach

- Error-correcting output coding (ECOC)

perceptron이란 가장 간단한 형태의 Neural Network을 말한다.

위와 같은 형태를 가지며, Hidden layer가 존재 하지 않는다.

입력 노드들은 X1~Xn까지 존재하며 각각의 weighted link들과 product 되어 진다.

어떠한 Activation function을 작동 시키는 t가 존재하며, 이러한 t는 threshold의 약자이다.

이것을 정리하면 아래와 같은 수식을 얻을 수 있다.

위 식을 다시 정리 하기위해서, threshold를 표현하면 아래와 같다.

이것을 이용해서 다시 표현하면,

이제 우리는 학습을 통해서 linearly separable한 data에 대해서 구분을 해주는

hyperplane을 찾는 것을 수행 하는 것이 목적이다.

Perceptron Learning Algorithm (PLA) 을 나타내면 아래와 같다.

1) 초기의 weight vector를 결정해 준다. 이것을 통해서 초기의 hyperplane을 생성 한다.

2) 을 예측 한다.

3) 예측된 y값과 실제값을 비교 한다. 아래의 수식에 의해서 값이 다를 경우 weight 값이 보정되고 hyperplane이 이동하게 된다.

실제값은 결국 {1,-1} 사이의 값을 같는다고 하면,

1인데 -1이 나오면 2가 되고

-1인데 1이 나오면 -2 가 된다.

위와 같이 prediction이 정확하지 않는다고 하면, 아래의 방법대로 weight 값을 업데이트 하게 된다.

예측값이 음수인 경우, y=+1 ,y(hat) = -1 ( y-y(hat)) = +2

에러에 대한 보상을 위해서 예측되는 값을 증가 시켜줘야 한다. 

이것을 위해서 양수인 입력 값들에 대해서는 weight 값을 증가 시켜 준다.

음수인 입력 값에 대해서는 weight 값을 낮춰 준다.

예측값이 양수 인 경우, y=-1,y(hat) = + 1 ( y-y(hat)) = -2

에러에 대한 보상을 위해서 예측된 값을 낮춰 준다.

이것을 위해서 양수인 입력 값에 대해서는 weight 값을 낮춰 준다.

음수인 입력 값에 대해서는 weight 값을 증가 시킨다.

실전 문제 풀이

초기 직선의 방정식: w2x2 + w1x1 + w0x0 = 0이라는 직선의 방정식으로 구성된 hyperplane을 생각해 보면

실제 데이터 vector는 아래와 같다고 가정한다.

위 알고리즘에 따라 순차적으로 실행해 보면,

1) y와 y^ 이 동일, weight 수정 없음

2) y = -1 , Y^ =1

위와 같이 weight 값이 조정되어서

수정된 직선의 방정식은 1x1 + 2x2  -1 = 0  

새롭게 수정된 Hyperplane에 의해서 나머지 데이터들은 모두 제대로 prediction 된다.

실제와는 다르지만 아래와 같은 느낌으로 계속 조금씩 이동하면서 Hype-plane을 찾아 간다고 생각하면 된다.

If not linearly separable ?

위와 같은 경우를 XOR 문제라고 하며 linearly separable한 Hyper-plane을 찾을 수 없는 경우이다.

이것을 해결하기 위해서 Hidden Layer라는 것을 위치 시키게 된다.

이제 XOR 문제를 풀어 보면 아래와 같다.

hyper-plane 1: x1-x2+0.5 = 0

hyper-plane 2: x1-x2-0.5 = 0

마지막 activation function의 hyperplane = -[x1+x2+0.5] =0

앞에 -를 붙이는 이유는 (-1,1)이 -1 이게 떄문이다. Hyperplane이 반대로 작용하게 된다.