Classification(2)

NN(Neural Network)

장점: 가장 강력한 분류 도구, noisy에 매우 강함. 임의의 non-linear discrimination(판별식) 제공

단점: 적절한 구조(hidden layer, unit 개수 등)을 모름(->overfit 정도를 바탕으로 판단)

         NN이 학습한 것을 통역 불가능(->통역 가능한 DT보다 성능 좋음)

 

 

MLP(Multi-Layer Perceptron, shallow NN)

perceptron의 x1, x2 -> hidden layer h1, h2 -> y

1~2개의 hidden layer 추가: hidden layer의 에러값을 알 수 없음. layer마다 우리가 알지 못하는 새로운 feature(hidden unit), 임의의 decision boundary를 스스로 만들어 냄

단점: training이 느림. local minima에 빠질 수 있음. 해석이 어려움. 적절한 구조를 모름.

 

• MLP의 layer의 개수와 구조 (성능과 관련 - underfit, overfit 등)
  • Input layer: attribute별로 1개씩 (numeric or binary해야 함. 0~1로 nomalization)
  • output layer: class별로 1개씩 (sigmoid function 사용)
  • hidden layer: 0개 - linear한 영역 / 1개 - 볼록한 영역 / 2개 - 임의의 decision boundary 생성
    • 역할: non-linearity를 만들기 위함
    • 한 데이터에 대한 MLP와 perceptron 성능 차이를 통해 데이터가 linear / non-linear한 지 알 수 있음
  • hidden unit: error가 충분이 작거나 성능이 향상되지 않으면 early stopping
    • 그 외의 prune, training with noisy samples, weight decay and elimination, weight sharing

• w를 찾는 학습 알고리즘: Backpropagation learning
  • perceptron의 활성함수를 sigmoid라고 할 때
  • hidden layer가 증가할 때마다 중첩되면서 f(w,a) = sig(sig(sig( ... )))
  • hidden layer의 개수가 많아지는 DNN에서는 활성함수로 Relu 사용: 중첩되면서 미분한 값이 매우 작아져서 없어짐
  • Output Layer에서 시작하여 직전 레이어로 이동하면서 Cost를 구하는 최적화 알고리즘
  • error function e(w) = 1/2 * ∑(T-y(w))^2을 0으로 만들고자 함 -> 편미분을 0으로 만들어 minima를 찾음
  • random point에서 시작해 iterative approach 이용. 작은 쪽으로 이동. (gradient descent)
  • 문제점: local minima에 빠질 가능성이 있음(=overfitting)
  • 해결방법: random 위치에서 시작, 한 feature가 큰 관련이 없을 때 weight 값의 변화가 없으므로 그 값을 더 작아지게 함으로써 사라지게 함.
• MLP overfit의 원인
  • hidden layer/unit의 개수가 너무 많은 경우
  • 관련 없는 feature가 많아 feature space가 너무 복잡한 경우

---

KNN(k-nearest neighbor) : classification, regression , clustering 가능

• Instance-based Learning (IBK): 새로운 데이터에 대하여 각각의 유사도를 비교한 후 가장 비슷한 데이터의 class로 분류
  • 데이터가 충분히 많아야 함
  • 유사도(distance, similarity function)은 어떻게 정의?
    1. 유클라디안 
    2. non 유클라디안 거
  • 시간이 많이 걸림
  • noise와 일치하는 경우: 비슷한 k를 찾아 majority voting -> KNN
• KNN Distance Function
  • 유클라디안
    
    1. Manhatton: |a1-a1'| + ... + |an - an'|
    2. 각 좌표의 차이를 n제곱한 후 n루트
    3. Max of dimension: 좌표 차이의 최대값
    4. 문제점: 특정 attribute에 의해 전체 값 차이가 많이 날 수 있음 -> nomalization
  • non 유클라디안
    • Cosine vector: D(x,y) = 1 - xy / √(x^2) √(y^2)
    • 두 데이터 사이의 각도를 봄
• kNN classification boundary: 각 데이터마다 region을 가짐. 근처 데이터와 선을 그었을 때 그 선을 직교하는 선들로 표현.

• k의 개수
  • k=1: unstable decision boundary
  • k=n(전체개수): 항상 같은 결과 P(y)
  • k는 항상 홀수여야 함.
• 복잡도: Training O(1) testing O(nd)

---

• kNN을 사용한 clustering 알고리즘
  1. k-mean
     • 방법:
       1. k 선택 후 random으로 k개의 cluster centers를 선택
       2. 각 instance를 가장 가까운 cluster center로 할당
       3. 각 cluster 내의 instances의 centroid(=mean) 계산
       4. centroid들을 새로운 cluster center로 한 후 cluster center가 바뀌지 않을 때까지 반복
     • cluster들이 비슷한 크기일 때 가장 성능이 좋음. cluster들의 특성 설명 불가능.
     • 두 가지 문제:
       • k 선택: 서로 다른 k값으로 여러 번 알고리즘을 돌려 cluster의 개수 파악
       • initial random point가 cluster에 미치는 영향: 서로 다른 초기 값으로 약 다섯 번 반복 후 응집도가 가장 좋은 것을 선택
       • 응집도: centroid와 instances 간의 거리의 제곱의 합의 루트.
  2. EM 알고리즘 (확률 이용)
     • 각 label에 해당하는 데이터들의 mean, standard deviation, sampling probability를 설정하고 정규 분포 그래프를 그림
     • 전체 likelihood를 maximization함으로써 세 변수를 추정하는 과정을 반복
     • instance x가 A에 속할 확률은 P(A|x): 확률 밀도 함수를 통해 계산한 P(x|A)를 이용해 알 수 있음