[Classification 1] 3. Classification algorithms - KNN

Content

• Introduction to supervised learning approach
• Data split in supervised learning
• Classification algorithms
  • KNN & distance measures
  • Decision tree
  • Random Forest, Ensemble approach
  • SVM

3. Classification algorithms - KNN 

K-NEAREST NEIGHBOR ALGORITHM

3.1 Classification example

• 주어진 표는 분류 문제의 예시를 나타내며, 훈련 데이터와 테스트 샘플로 구성되어 있다.
• 훈련 데이터
  • 각 행은 하나의 샘플을 나타내며, 'v1=strength'과 'v2=smooth'는 특성(Feature).
  • 'y=quality'는 해당 샘플의 레이블(Label)로, 'good' 또는 'bad'의 값을 가짐.
  • 훈련 데이터 내용
    • x1 샘플은 강도(v1)가 5이고 부드러움(v2)이 5일 때, 품질(y)이 'good'.
    • x2 샘플은 강도(v1)가 1이고 부드러움(v2)이 2일 때, 품질(y)이 'bad'.
    • x3 샘플은 강도(v1)가 6이고 부드러움(v2)이 7일 때, 품질(y)이 'good'.
    • x4 샘플은 강도(v1)가 3이고 부드러움(v2)이 5일 때, 품질(y)이 'bad'.
• 테스트 샘플
  • x5 샘플은 강도(v1)가 2이고 부드러움(v2)이 3입니다. 품질(y)는 알려지지 않았으며, 모델은 이 테스트 샘플의 품질을 예측해야 함.
  • 이 데이터를 바탕으로, 훈련 데이터를 사용하여 모델을 훈련시키고, 테스트 샘플 x5의 품질이 'good'인지 'bad'인지를 예측하는 것이 목표.

3.2 k-Nearest Neighbors (KNN) algorithm

• k-Nearest Neighbors (KNN) 알고리즘은 분류(classification) 또는 회귀(regression) 문제를 해결하기 위해 사용되는 간단하면서도 효율적인 기계 학습 알고리즘 중 하나.
• 이 알고리즘은 다음과 같이 작동:
  • k 결정 및 거리 측정 방법 선택:
    • 우선, 가장 가까운 이웃의 수를 정의하는 k 값을 결정.
    • 또한, 훈련 샘플과 테스트 샘플 간의 거리를 측정하기 위한 방법(예: 유클리디안 거리, 맨해튼 거리 등)을 선택.
  • 테스트 샘플에 대한 거리 계산:
    • 주어진 테스트 샘플에 대해 모든 훈련 샘플과의 거리를 계산.
  • k개의 가장 가까운 훈련 샘플 선택:
    • 계산된 거리를 기반으로 가장 가까운 k개의 훈련 샘플을 선택.
  • 다수결로 결론 도출:
    • 선택된 k개의 가까운 훈련 샘플들 중에서 가장 많이 나타나는 레이블(분류 문제의 경우) 또는 레이블 값의 평균(회귀 문제의 경우)을 계산하여 테스트 샘플의 레이블 또는 값을 예측.
• KNN 알고리즘의 성능은 k 값의 선택과 거리 측정 방법에 크게 의존.
• 너무 작은 k 값은 노이즈에 민감해질 수 있고, 너무 큰 k 값은 분류 경계가 불분명해질 수 있다.
  • 따라서, 적절한 k 값을 선택하는 것이 중요.

3.3 Example

3.4 Classification example

• 분류 예제에서 x5를 테스트 데이터로 하고, 모든 훈련 샘플과의 유클리드 거리를 계산.
• 이 거리를 기준으로 가장 가까운 k개의 훈련 샘플을 선택하고, 그 샘플들의 라벨을 통해 x5 샘플의 라벨(quality)을 예측할 수 있다.
  • 예를 들어, k를 3으로 설정했을 때, 가장 거리가 짧은 세 개의 훈련 샘플을 기준으로 다수결로 x5의 라벨을 결정하게 됨.

3.5 K-NN algorithm

• K-NN(K-Nearest Neighbors, K-최근접 이웃) 알고리즘은 간단하지만 강력한 분류 및 회귀 문제에 사용되는 알고리즘.
• K-NN의 작동 방식은 다음과 같다:
  • 1-NN (1-Nearest Neighbor, 1-최근접 이웃):
    • 1-NN에서는 단순히 테스트 샘플과 가장 가까운 하나의 트레이닝 샘플을 찾고, 그 트레이닝 샘플의 클래스 레이블을 테스트 샘플의 예측 레이블로 사용.
    • 즉, 가장 가까운 한 개의 인스턴스가 속한 클래스를 예측 클래스로 결정.
  • 일반적인 k-NN:
    • k-NN에서는 먼저 테스트 샘플과 가장 가까운 k개의 트레이닝 샘플을 찾음.
    • 이때 거리를 측정하기 위한 여러 방법들이 사용될 수 있는데, 대표적으로 유클리드 거리(Euclidean distance)가 있다.
    • 그 후, 이 k개의 트레이닝 샘플들 중 가장 많이 나타나는 클래스 레이블로 테스트 샘플의 클래스를 예측.
    • 이 과정에서 다수결(majority vote) 방식을 사용하여, k개의 이웃 중 가장 많이 나타난 클래스를 최종 예측 결과로 결정.
• K-NN 알고리즘의 성능은 k의 값과 거리를 측정하는 방법에 크게 의존.
• k의 값이 너무 작으면 노이즈에 민감하게 반응할 수 있고, 너무 크면 분류 경계가 불명확해질 수 있다.
  • 따라서 적절한 k값의 선택이 중요.
  • 또한, 거리 측정 방법에 따라서도 성능에 영향을 미칠 수 있으므로, 문제에 맞는 거리 측정 방법을 선택하는 것이 중요.

3.6 Example: Iris data classification using KNN

3.7 Computation for KNN

• KNN(K-Nearest Neighbors) 알고리즘은 인스턴스 기반 학습 또는 게으른 학습 방법에 속함.
• 이 방법의 특징:
  • 훈련 단계에서의 작업:
    • KNN 알고리즘의 훈련 단계는 다른 머신러닝 알고리즘에 비해 매우 간단.
    • 실제로 "훈련"이라고 할 것이 거의 없는데, 이는 KNN이 게으른 학습자(lazy learner)로 분류되기 때문.
    • 훈련 데이터를 단순히 저장하기만 하고, 모델을 명시적으로 학습시키는 과정이 없다.
      • 즉, 훈련 단계에서는 데이터를 저장하는 것이 전부.
  • 새로운 샘플의 라벨을 예측하기 위한 계산:
    • 새로운 샘플의 라벨을 예측할 때, KNN 알고리즘은 저장된 모든 훈련 데이터와의 거리를 계산.
    • 이후, 계산된 거리를 기반으로 가장 가까운 k개의 이웃을 찾음.
    • 마지막으로, 이 이웃들 중 다수결을 통해 새 샘플의 라벨을 결정.
    • 결과적으로, KNN 알고리즘은 훈련 단계에서는 계산 부담이 거의 없으나, 예측 단계에서는 매우 많은 계산을 필요로 함.
    • 특히, 훈련 데이터의 크기가 클 경우 또는 다차원 특성을 갖는 경우 거리 계산에 많은 시간이 소요될 수 있다.
• 이러한 특징 때문에 KNN은 게으른 학습 방법으로 분류되며, 실시간 시스템이나 매우 큰 데이터셋을 다루는 경우에는 성능상의 제약이 있을 수 있다.

3.8 Exercise

3.9 Neighbor size K

• K-최근접 이웃(K-NN) 알고리즘에서 이웃의 크기, 즉 K의 선택은 매우 중요.
  • K의 값에 따라 모델의 성능이 크게 달라질 수 있기 때문.
• K의 크기에 따른 영향을 살펴보면 다음과 같다:
  • 작은 K 값:
    • K가 작을 경우, 예측은 가장 가까운 이웃에 크게 의존.
      • 이는 모델이 훈련 데이터의 노이즈에 민감하게 반응하여 과적합(overfitting)될 위험이 있다.
      • 결과적으로, 높은 분산(high variance)을 가지며, 새로운 데이터에 대한 예측이 불안정해질 수 있다.
  • 큰 K 값:
    • 반대로 K가 크면, 예측은 더 많은 이웃을 고려하게 되어 노이즈에 대한 강인함이 증가하지만, 결정 경계가 더 단순해져 모델이 과소적합(underfitting)될 위험이 있다.
    • 이는 높은 편향(high bias)을 의미하며, 모델이 너무 단순하여 정확도가 떨어질 수 있다.
    • 따라서, 적절한 K 값을 선택하는 것은 데이터셋의 특성에 따라 달라지며, 이를 위해 몇 가지 방법을 사용할 수 있다:
      • 휴리스틱(Heuristics):
        • 일부 기본적인 규칙을 적용하여 K의 값을 선택할 수 있다.
        • 예를 들어, 데이터 포인트의 총 수의 제곱근을 K 값으로 사용하는 것이 일반적인 방법 중 하나.
      • 교차 검증(Cross-validation):
        • 더 정교한 방법으로, 데이터셋을 여러 부분으로 나누고, 일부는 훈련에, 나머지는 검증에 사용.
        • 다양한 K 값들에 대해 모델을 훈련시키고 검증 데이터셋에서의 성능을 평가하여 최적의 K 값을 찾음.
        • K-겹 교차 검증(K-fold cross-validation)이 이 방법에 자주 사용.

3.10 Neighbor size – extreme cases

• K-NN 알고리즘에서 이웃의 크기, 즉 K 값에 따른 극단적인 경우를 살펴보면 다음과 같다:
• K=1일 때의 훈련 오류:
  • K가 1인 경우, 각 훈련 샘플은 가장 가까운 이웃이 자기 자신.
    • 따라서, 각 훈련 샘플을 테스트 샘플로 사용했을 때, 예측은 항상 정확하게 자기 자신의 레이블과 일치.
    • 이 경우 훈련 오류는 0.
    • 하지만, 이는 과적합(overfitting)의 징조이며, 새로운 데이터에 대한 일반화 능력이 낮을 수 있음을 의미.
• K=n일 때 (n은 훈련 샘플의 수):
  • K가 전체 훈련 샘플의 수와 같은 경우, 모든 훈련 데이터가 이웃이 됨.
    • 이 경우, 예측은 훈련 데이터 내에서 가장 흔한 레이블(다수결)로 결정.
    • 이 방식은 매우 단순화된 모델을 만들며, 데이터의 특성이나 패턴을 잘 반영하지 못할 수 있다.
    • 결과적으로 편향(bias)이 높아지며, 훈련 데이터에 대해서도 오류가 발생할 가능성이 높아짐.
    • 이러한 극단적인 경우를 통해, 적절한 K 값의 선택이 K-NN 알고리즘의 성능에 매우 중요하다는 것을 알 수 있다.
• 너무 낮은 K 값은 과적합을, 너무 높은 K 값은 과소적합(underfitting)을 초래할 수 있으므로, 데이터의 특성과 문제에 맞는 최적의 K 값을 찾아내는 것이 필요.

3.11 K-NN (Pros)

• K-NN (K-Nearest Neighbors) 알고리즘의 장점:
  • 이해하고 프로그래밍하기 쉬움:
  • K-NN은 매우 직관적인 알고리즘이며, 구현이 간단.
  • 데이터 포인트 사이의 거리를 계산하고, 가장 가까운 이웃을 찾아 분류 또는 회귀를 수행하는 방식.
    • 명시적 거부 옵션:
      • K-NN은 다수결의 원칙에 따라 작동.
    • 만약 가장 가까운 이웃들 사이에 다수결로 결정할 수 없는 경우 (즉, 최대 표를 얻은 클래스가 없는 경우), 알고리즘은 결정을 내리지 않을 수 있는 옵션을 제공.
      • 이는 불확실성을 관리하는 데 유용할 수 있다.
    • 최적에 가까움:
      • K-NN은 클래스의 사후 확률 추정에 있어 최대 가능성 추정(maximum likelihood estimation)을 제공.
      • 즉, 데이터가 충분하고, 적절한 K 값이 선택되었을 때, K-NN은 매우 높은 성능을 낼 수 있으며, 이론적으로는 최적의 분류기에 가까울 수 있다.
• K-NN 알고리즘의 이러한 장점들은 그것을 매우 유용하고 널리 사용되는 머신러닝 도구로 만듬.
• 그러나, 모든 데이터셋에 대해 최적의 성능을 보장하는 것은 아니며, 큰 데이터셋이나 고차원 데이터셋에서는 계산 비용이 매우 높아질 수 있다.
• 따라서, 사용하기 전에 데이터의 특성과 요구 사항을 고려하는 것이 중요.

3.12 K-NN (Cons)

• K-Nearest Neighbors (K-NN) 알고리즘 단점:
  • 계산 비용이 많이 든다(O(np)):
    • K-NN은 예측을 할 때마다 모든 훈련 데이터와의 거리를 계산해야 하므로, 데이터 포인트(n)와 특성의 개수(p)가 많을수록 계산 비용이 기하급수적으로 증가.
  • 많은 메모리 요구:
    • K-NN은 모든 훈련 데이터를 메모리에 저장해야 하기 때문에, 대규모 데이터셋을 다룰 때 메모리 요구량이 큼.
  • 빈번한 클래스가 결과를 지배한다:
    • 소수 클래스보다 빈번히 발생하는 클래스가 결과에 더 큰 영향을 미칠 수 있다.
      • 이는 데이터 불균형이 결과에 부정적인 영향을 미칠 수 있음을 의미.
  • 잡음 및 무관한 특성에 민감함:
    • 모든 특성이 동등하게 취급되기 때문에, 잡음이 많거나 무관한 특성이 포함되어 있을 경우 예측 성능이 저하될 수 있다.
  • 차원의 저주:
    • 특성의 수가 많아질수록, 데이터 포인트 간의 거리가 상대적으로 커지고, 거리 계산이 더 복잡.
    • 이로 인해 고차원에서는 "가장 가까운" 이웃이 실제로는 매우 멀게 느껴질 수 있으며, "가장 가까운" 이웃이 의미를 잃게 됨.
• 이러한 단점들 때문에 K-NN 알고리즘을 사용할 때는 데이터의 특성과 요구 사항을 충분히 고려해야 하며, 필요한 경우 차원 축소, 데이터 정제, 가중치 부여 등의 전처리 작업을 통해 단점을 완화.

3.13 Curse of dimensionality

• 차원의 저주는 고차원 설정에서 KNN(또는 대부분의 거리 기반 학습 방법)이 잘 작동하지 않는 주요 이유 중 하나.
  • 차원 수가 증가함에 따라 데이터 공간의 크기가 기하급수적으로 증가하며, 동일한 밀도를 유지하기 위해서는 데이터 세트의 크기도 기하급수적으로 증가해야 함.
• KNN에서 차원의 저주를 극복하는 방법:
  • 더 많은 데이터 추가:
    • 데이터의 밀도를 높이기 위해 더 많은 데이터를 추가하는 것.
    • 이 방법은 실제로 실행하기 어려울 수 있으며, 많은 경우에 필요한 데이터의 양이 현실적으로 불가능할 수 있다.
  • 차원 축소:
    • 특성 선택(Feature Selection): 중요한 특성만을 선택하고 나머지는 제거하여 차원을 줄이는 방법.
    • 이는 변수의 수를 줄임으로써 모델의 복잡성을 감소시키고, 계산 효율성을 높일 수 있다.
  • 특성 추출(Feature Extraction):
    • 주성분 분석(PCA), 선형판별분석(LDA), 오토인코더 등의 방법을 사용하여 원래의 고차원 데이터를 저차원으로 매핑하면서도 중요한 정보를 최대한 보존하는 새로운 특성을 생성하는 방법.
• 이러한 방법을 통해 차원의 수를 효과적으로 줄이면서도 중요한 정보를 유지할 수 있으며, KNN과 같은 거리 기반 학습 방법의 성능을 향상시킬 수 있다.