[기계학습] Clustering

Unsupervised Learning

✔️ 레이블을 정확하게는 모르지만 비슷하니까 구분하는 것 ...

Unsupervised learning

✔️ 결과값 없이 데이터에서 패턴을 찾는 방법
✔️ 숨겨진 구조나 계층을 찾아냄
✔️ 숨은 사용자 그룹을 찾음
✔️ 문서별로 주제를 분류
✔️ 로그 데이터를 활용한 사용 패턴 분석

비지도 학습의 종류

✔️ Clustering (클러스터링)
✔️ Density estimation (밀도 추정)
✔️ Dimensionality reduction (차원 축소)

Clustering

Clustering

✔️ 하나의 데이터를 여러개의 부분 집합으로 나누는 것
✔️ 유사성 기반으로 데이터를 나눔
ex) 하늘, 나무, 모래 등 이미지에서 객체를 뽑아내는 데 사용
or
각 사진의 특징을 추출하여 인물/풍경 등으로 분류
✔️ 정확히 레이블은 없지만 그냥 비슷한 애들끼리 묶음

클러스터링의 종류

📍 Hard clustering
✔️ 한 객체는 하나의 클러스터에만 속함
✔️ 이렇게 제한을 두면 조금 더 쉽게 클러스터를 찾을 수 있음
✔️ 단, 현실 세계를 완벽히 반영하기엔 무리가 있음
ex) K-means

📍 Fuzzy clustering
✔️ 하나의 객체가 여러 클러스터에 부분적으로 속할 수 있음
✔️ 현실세계를 반영하기에는 이게 더 적합함
✔️ degree of belonging의 합이 1임
ex) Fuzzy K-means

목적

✔️ 데이터 샘플의 숨겨진 구조를 파악
✔️ 전체 데이터의 구조에 대한 통찰을 얻음
✔️ 가설 설정 및 이상치 탐지에 활용
✔️ 같은 클러스터에 속한 데이터를 동일한 값으로 표현 -> 데이터 압축
✔️ 머신러닝을 위한 전처리 작업에도 사용

성능 측정

✔️ 클러스터 내 분산과 클러스터 간 거리

Density estimation

밀도 추정

✔️ 각 클래스가 생성한 데이터의 확률 분포를 추정
✔️ 목적

1. 특정 데이터가 어떤 클래스에서 나올 확률 계산
2. 가장 가능성 높은 클래스로 분류
   

파라미터 기반 밀도 추정

✔️ 분포가 어떤 수학적 함수(ex: 정규분포)를 따른다고 가정
✔️ 주어진 데이터에 가장 잘 맞는 파라미터 값 찾아냄
-> 가우시안(정규분포) 함수 or 몇몇의 가우시안
ex) mixture of gaussian (정규분포 혼합)

비파라미터 밀도 추정

✔️ 특정 함수의 가정 없이 데이터 자체의 모양을 기반으로 분포 추정
✔️ 파라미터 필요 없음
ex) 히스토그램

비파라미터 밀도 추정의 한계

✔️ 히스토그램의 한계

1. 계급구간의 경계가 불연속적
2. 계급구간의 시작 위치에 따라 히스토그램 분포가 달라짐
3. 계급구간의 크기에 따라 히스토그램 분포가 달라짐
4. 그 외에도 고차원 데이터에 대해서는 메모리 문제 등으로 사용하기 어려움

Kernel Function

✔️ 위의 문제를 해결하기 위한 방법
✔️ 커널 함수가 겹치는 곳은 크게 표현하면 됨
(초록 - 커널함수 겹처놓은 것)
✔️ 커널 함수들을 겹쳐서 부드럽고 연속적인 밀도 함수 표현

Dimension Reduction

차원 축소

✔️ 고차원 데이터를 정보 손실을 최소화하여 낮은 차원으로 변환
✔️ 목적

목적

✔️ 2D or 3D로 변환하여 데이터 분석을 직관적으로 시각화
✔️ 고차원의 저주 현상 완화

Curse of dimension

✔️ 차원의 저주
✔️ 차원이 늘어날수록 거리 계산이 무의미해짐
✔️ 가능한 서브스페이스 수가 기하급수적으로 증가

PCA

✔️ Principle Component Analysis
✔️ 주성분 분석
✔️ 데이터를 분산이 큰 축 기준으로 저차원으로 투영
✔️ 공분산 행렬의 고유값이 큰 고유벡터들을 새로운 축으로 선택

✔️분산이 큰 축 == 정보가 많은 방향
PCA는 원래 고차원 데이터가 있을 때, 그걸 중요한 정보가 많이 퍼진 축 방향으로 차원을 축소함
-> 데이터가 많이 퍼져있음 == 서로 다른 특징이 잘 드러난다는 것이기 때문

✔️ 그 축을 어떻게 찾을까?
전체 데이터의 공분산 행렬을 생성
-> 데이터의 분포와 관계를 수학적으로 요약
여기에 고유값 분해
-> 고유벡터(축방향) + 고유값(분산크기)이 나옴

Outlier Detection

Outlier

✔️ 이상값 탐지 (이상치 탐지)
✔️ 다른 데이터와 확연히 달라서 다른 생성 메커니즘에 의해 만들어진 것으로 의심되는 데이터
✔️ 주목의 대상이 될 수 있음
(이상치 자체가 분석의 주요 대상이 될 수 있다는 의미)
✔️ 새로운 패턴을 찾는 일(novelty detection)과도 연관되어 있음

Noise

✔️ 노이즈
✔️ 관측 오류 또는 시스템 내의 무작위 오류
✔️ 관심 대상이 아닌 제거 대상

outlier 예시

✔️ point outlier
대부분의 데이터와 비교했을 떄 확연히 다른 하나의 데이터

✔️ contextual outlier
상황/문맥을 고려하였을 때 어울리지 않는 데이터

✔️ collective outlier
개별로 보면 괜찮지만, 여러 개가 모이면 비정상적인 패턴을 가지는 집합

사용 예시

✔️ 부정사용감지 시스템
fraud detection system (FDS)
이상한 거래 승인 요청 시에 카드 소유자에게 자동으로 경고 메시지 전송
✔️ 침입 탐지 시스템
instrusion detection system (IDS)
네트워크 트래픽을 관찰하여 이상 접근 식별
✔️ 자율주행 시스템
✔️ 시스템의 고장 진단
✔️ 임상에서 질환 진단 및 모니터링
✔️ 공공보건에서 유행병의 탐지
✔️ 스포츠 통계학에서 특이 사건 감지
✔️ 관측 오류의 감지

Clustering Algorithm

Clustering

✔️ 유사한 데이터들을 모아 그룹화하는 것
✔️ 클러스터 간 유사성은 적고, 클러스터 내부 유사성은 큼

Hierarchical clustering

✔️ 계층적 클러스터링
✔️ 결과가 트리 형태인 계층 구조를 가짐
📍 Agglomerative hierarchical clustering
✔️ 상향식(병합형)
✔️ 각 데이터가 하나의 클러스터로 시작해서 가까운 것끼리 합쳐나감
✔️ 더 많이 사용됨

📍 Divisive hierarchical clustering
✔️ 하향식(분할형)
✔️ 모든 데이터를 하나의 클러스터로 시작해서 점점 나눔

✔️ 계층적 클러스터링 시각화

Partitioning clustering

✔️ 분할형 클러스터링
✔️ 계층구조 없이 전체 데이터를 유사한 그룹들로 나누는 방식
✔️ ex) K-means

K-means clustering

✔️ 분할형 클러스터링 알고리즘

✔️ 프로세스

1. 클러스터 중심을 임의로 초기화
2. 각 데이터를 가장 가까운 중심에 할당
3. 클러스터 내 평균 위치 계산
4. 클러스터 중심을 평균 위치로 이동
5. 수렴할 때까지 2~4 반복

K-means clustering 예시

1.

✔️ 각 클러스터의 중심을 랜덤하게 선택함
✔️ 각 데이터가 어느 중심과 가장 가까운지 확인

2.

✔️ 각 데이터를 가장 가까운 중심에 할당
✔️ 이 과정에서 중심 좌표도 점점 조정되어야 함 (평균값으로)

3.

✔️ 클러스터 중심을 새로 계산된 평균 위치로 이동
✔️ 데이터들이 더 잘 모이도록 중심값 재조정

4.

✔️ 재조정된 중심을 기준으로 각 데이터의 소속 클러스터를 다시 결정
✔️ 이렇게 몇 번 반복하다보면 점점 안정된 그룹이 형성됨

5.

✔️ 중심 위치가 바뀌면서 몇몇 데이터가 클러스터를 바꾸게 되는 포인트 발생

6.

✔️ 클러스터 평균을 다시 계산
✔️ 중심값들을 계속해서 업데이트하는 것

7.

✔️ 중심 좌표를 클러스터 평균 위치로 계속 이동
✔️ 이 과정을 반복하여 중심 위치와 소속이 더 이상 변화하지 않을 때까지 반복

K-means clustering 정리

✔️ 중심이 𝜇𝑖, 소속된 데이터 집합이 Si일 때 전체 분산 V를 최소화하는 Si를 찾는 것

✔️ 과정 요약

1. 초기 중심을 랜덤으로 설정
2. 두 단계를 군집이 더이상 생기지 않을 때까지 반복

✔️ 특징

1. 클러스터 수 k를 미리 정해야 함

-> k가 많아질수록 원래 원본과 더 가까워 짐
-> 보통은 배경과 배경이 아닌 것을 구분하기 위해서 사용됨

2. 초기 중심값에 매우 민감
   

K-means - Elbow method

✔️ 클러스터 수 k를 정할 때 쓰는 기법
✔️ 군집 수에 따른 제곱 오차 합(SSE)을 그래프로 그리고 그래프가 꺾이는 지점에서 적절한 k를 선택

✔️ 문제점

1. k를 사전에 모르는 경우가 대부분임
2. 사람이 직접 판단해야하는 어려움이 존재

-> 그래서 elbow method가 필요한 것

K-nearest Neighbor

✔️ 입력과 출력이 함께 주어진 데이터가 있을 때 새로운 입력값에 대해 출력이 이미 알려진 가장 가까운 K를 참고해서 결과를 예측
✔️ 과정

1. 입력값과 각 데이터간의 거리를 계산
2. 가장 가까운 이웃을 효율적으로 탐색
3. 가까운 이웃들의 결과를 이용해 예측
   

KNN에서 사용하는 거리

✔️ 대표적으로 Euclidian distance 사용
✔️ 유클리디안 거리
✔️ 두 점 사이의 직선 거리를 의미

KNN의 결과 예측 방식

✔️ K개의 최근접 이웃을 이용하여 결과를 예측할 때 사용하는 방식 2가지

📍 Classification (분류)
✔️ 출력값이 범주형 카테고리일 때 사용
✔️ ex) 강아지/고양이/토끼 같은 분류
✔️ 다수결 투표 방식으로 (Majority voting)
-> 가까운 K개 중 가장 많이 등장한 클래스 선택

📍 Regression analysis (회귀-숫자를 예측)
✔️ 출력값이 수치형일 때 사용
✔️ ex) 키, 온도, 가격, 점수 등
✔️ 방법 1: K개의 이웃 값의 평균을 사용해서 예측
✔️ 방법 2: 거리에 반비례하는 가충지를 적용한 평균
-> 가까운 이웃일수록 더 많은 영향을 줌

KNN에서 발생하는 문제

📍 정규화 필요
✔️ 서로 다른 범위의 값을 0~1 사이로 변환
✔️ 평균과 표준편자를 기준으로 Z-score로 변환

📍 K값 선택
✔️ K가 너무 작으면 과적합
✔️ K가 너무 크면 과소적합
✔️ 따라서 적절한 K 값 선택이 중요함

클러스터 간 거리 계산 방식

📍 Simple linkage
✔️ 단순 연결 방식
✔️ 가장 가까운 두 점의 거리

📍 Complete linkage
✔️ 완전 연결 방식
✔️ 가장 먼 두 점의 거리

📍 Average linkage
✔️ 평균 연결 방식
✔️ 클러스터 내 모든 점 간의 평균 거리

📍 Centroid linkage
✔️ 중심 연결 방식
✔️ 클러스터 중심 간의 거리

클러스터 내 거리 계산

📍 Ward linkage
✔️ 와드 연결 방식
✔️ 병합 전/후의 제곱 편차 합의 차이를 기준으로 병합
✔️ 수식적으로는 정확하지만 계산이 너무 복잡함