[기계학습개론] Clustering, GMM

SUbbb·2021년 10월 26일
기계학습개론
0

기계학습개론

목록 보기
9/10
post-thumbnail

Clustering, K-Means, Gaussian Mixture Model, Anomaly Detection

Clustering

Grouping과 유사, 비슷한 것끼리 모으기(기준이 무엇인지?)

  • 비슷한 instances끼리 grouping하는 것 (cluster에 할당)
  • 유사한 정도, 또는 그렇지 않은 정도에 따라 모으는 것

Classification vs. Clustering

  • 왼쪽은 Classification으로 Label이 존재
  • 오른쪽은 Clustering으로 Label이 존재하지 않음.

Clustering: applications

  • customer segmentation
    • 그들의 구매와 활동에 기반(label이 없음)
  • data analysis
    • data를 sub-groups로 분류
  • dimensionality reduction technique
  • anomaly detection(outlier detection, 특이점 검출)
  • semi-supervised learning
  • search engines(유사한 참조 결과를 주기 위함)
  • segment an image

Clustering: K-Means

  • 몇 개의 cluster로 분류할 것인지 명시해야 함(k값)
  • kmeans.cluster_centers_로 clusters의 중심점 위치를 알 수 있다.

K-Means algorithm

1: 중심점을 random하게 선택하는 것으로 시작(cluster 개수만큼)
2: 중심점 기준으로 각 sample까지의 거리를 계산해 거리의 합을 도출하고 중심점을 변경
3: 변경된 중심점을 기준으로 각 sample들까지의 거리합을 구하는데, 더 이상 거리합이 감소하지 않으면 중심점의 변경을 멈춤

알고리즘의 흐름을 확인할 수 있다.

K-means: problem1

  • 초기 중심점 선택이 좋지 않으면 차선의 해결책이 만들어질 수 있다.

초기 시작점에 따라 결과가 달라질 수 있다.

best model을 찾기 위해, 비교를 위한 측정지표가 필요하다.

  • instances와 중심점간의 mean squared distance를 이용

K-means: problem2

  • Complexity issue
    • Time: K-Means는 학습 중 매 반복마다 전체 dataset을 사용해야 한다.(변경된 중심점에 대한 거리합 계산을 위해)
      • 즉, sample의 수가 많아지고 반복이 늘어나게 되면 Time complexity는 자연히 증가하게 된다.
    • Memory: 모든 sets을 저장(위의 모든 계산을 위해)

→\rarr 결국 clusters가 커지면, 더 치명적인 문제

Mini-batches를 사용하여 해결 가능

batch 크기를 지정해주고,
지정한 크기만큼 data를 분리하여 K-means를 수행

K-means: other problems

  • Needs:
    • 차선의 solution을 얻는 것을 피하기 위해, 알고리즘을 여러 번 수행해야 한다
    • cluster 수를 지정하는 것이 번거로울 수 있다.
  • More: K-means는 clusters가 다음과 같은 특징이 있는 경우 잘 동작하지 않는다.
    • cluster size의 불변성(자체적으로 늘릴 수가 없음)
    • 밀집도가 다르거나, 비구형의 형태

측정된 Inertia에 의해
오른쪽의 clustering을 더 적합하다고 판단해야 하지만, 실제로는 그렇게 보이지 않는 문제

Clustering: where to use

Use case: Preprocessing

  • 지도 학습 알고리즘 이전에 전처리하는 과정으로 사용가능
  • 차원 축소에도 사용 가능
  • Example: MNIST-like dataset

    Logistic Regression만 이용한 경우K-Means를 전처리기로 사용하고 Logistic Regression한 경우GridSearchCV로 최적의 cluster 수를 계산하고
    이를 적용

Use case: Semi-supervised Learning

Semi-supervised Learning이 무엇인가?

  • 세모와 네모는 label이 존재하는 data
  • label이 없는 경우, 분류의 정확도가 떨어질 수밖에 없기에, Semi-supervised learning에 clustering을 사용하여 label이 없는 data도 어느 class에 속하는 지 알 수 있다.
  • Example: MNIST-like dataset
    • training sets 중 50개만이 label이 존재하는 경우, Logistic regression을 사용하면 다음과 같은 결과를 얻을 수 있다.
    • training sets 중 50개만이 label이 존재하지만 K-means를 이용하여 Clustering을 수행하고 Logistic regression을 사용하면 다음과 같이 향상된 정확도를 얻을 수 있다.(하지만 label이 모두 존재하는 경우보다 좋을 수는 없다.)
    • 추가적으로, label이 없는 datasets에 대해 propagate labels(label을 증식시킴)를 이용하여 조금 더 향상된 정확도를 얻을 수 있다.

Gaussian Mixture Model, Anomaly Detection

GMM

Gaussian Mixtures: key concept

Gaussian Mixture Model은 data sample들이 가우시안 분포를 따를 것이라는 가정을 가지는 확률 모델

  • 모든 datasets이 하나의 분포를 따르는 것은 어렵기에, cluster가 여러 개인 경우, 여러 개의 가우시안 분포를 따른다고 가정

Mixture of Gaussians이 필요한 이유?

하나의 가우시안으로 모든 data의 밀도를 추정하게 되면,
오른쪽 경우처럼 두 개의 가우시안이 필요해보이는 data에 대한
정확한 추정이 이루어지지 않는다.위와 같이 가우시안 혼합으로 밀도를 추정해야 정확하게 되는 경우가 존재

Gaussian Mixtures: key concept

Example

  • 두 개의 가우시안 혼합을 표현하기 위한 Probability density function(PDF)
    →\rarr Density estimation task
  • PDF를 잘 찾는 것이 목표
  • 전체 sample 수가 37, 가우시안 혼합으로 밀도 추정한 그림에 대해 아래와 같은 식을 사용할 수 있다.
    P(x)=2137N(x;μ1,∑1)+1637N(x;μ2,∑2)P(x)=\frac{21}{37}N(x;\mu_1,{\sum}_1) + \frac{16}{37}N(x;\mu_2,{\sum}_2)
  • kk(cluster의 수)개의 가우시안으로 일반화하면,
    • 확률분포 P(x)P(x)는 kk개 가우시안의 선형 결합으로 표현
      P(x)=∑j=1kπjN(x;μj,∑j)P(x)=\sum^k_{j=1}\pi_jN(x;\mu_j,{\sum}_j)
      =k=k개의 정규분포의 합

Gaussian Mixtures: how to find GM

  • 최대 우도를 이용한 최적화 문제로 공식화
    주어진 데이터: 훈련집합 X={x1,x2,⋯ ,xn}X=\{x_1,x_2,\cdots,x_n\}, 가우시안의 개수 kk
    추정해야 할 매개변수집합: θ={π=(π1,π2,⋯ ,πk),(μ1,∑1),(μ2,∑2),⋯ ,(μk,∑k)}\theta=\{\pi=(\pi_1,\pi_2,\cdots,\pi_k),(\mu_1,{\sum}_1),(\mu_2,{\sum}_2),\cdots,(\mu_k,{\sum}_k)\}

    → θ^=arg max⁡θlogP(X∣θ)\rarr\,\hat\theta=\displaystyle\argmax_\theta logP(X|\theta)
  • Expectation-Maximization (EM) algorithm
    • EM 알고리즘을 이용한 θ^\hat \theta 식 풀이
    • θ\theta를 모르므로 난수로 설정하고 출발, θ\theta 값 도출
    • 가우시안으로 sample의 소속 정보 개선 (E단계) →\rarr sample의 소속 정보로 가우시안 개선 (M단계) →\rarr 가우시안으로 sample의 소속 정보 개선 (E단계) →\rarr 반복
      • K-means는 중심점이 어디서 시작될 지 모르고, 단순 거리 계산 후 개선하지만, GMM은 가우시안 분포를 이용하여 거리 측정, 개선

GM

  • Gaussian mixture model의 시각 표현
    • parameters: squares
    • random 변수: circles
    • conditional dependencies: solid arrows

code & examples

K-Means와 비교

Anomaly Detection

What is it ?

Anomaly detection은 outlier(특이한 것) detection이라고도 불리며, 일반적인 것들로부터 벗어나는 instance를 탐지하는 task

  • 이를 잘하게 되면 성능이 향상될 수도 있다.
  • fraud detection(위조지폐 검출)과 같은 경우 사용 가능

Anomaly Detection using GM

  • anomaly detection을 위해 Gaussian mixture model을 사용한다. (확률값을 사용)
    • 밀집도가 낮은 지역에 있는 어떠한 instance들은 anomaly로 간주될 수도 있다.
  • In practice:
    • density threshold(magic number)를 정의해야 한다.
    • 일반적으로 4% density 정도면 anomaly로 판단

Others for Anomaly Detection

PCA

차원 축소 →\rarr 원 차원으로 변환
⇒\Rightarrow 튀는 값들에 대한 Detection or Deletion 가능

Isolation Forest

  • DT에서 가지치기를 계속 진행하는 부분과 그렇지 않은 부분이 존재한다. 이때 그렇지 않은 부분을 outlier로 판단

profile
SUbbb
배우고 정리하고 공유하기
이전 포스트

[기계학습개론] PCA

다음 포스트

[기계학습개론] Perceptron

0개의 댓글