260610_강의 정리 (KNN, K-Means)

 

machine learning · 거리 기반 알고리즘

KNN과 K-Means — 거리로 분류하고, 거리로 묶는다

• KNN: 가장 가까운 이웃 K개의 다수결로 클래스를 결정하는 지도학습 분류기
• K-Means: 데이터를 K개 군집으로 묶는 비지도학습 클러스터링
• 두 알고리즘 모두 유클리디안 거리를 핵심 척도로 사용하며, 스케일링이 필수임

📐

0. 모든 것의 출발 — 거리(Distance)

"이 데이터와 저 데이터가 얼마나 비슷한가?" — 거리 기반 알고리즘의 핵심 질문

• 머신러닝에서 거리는 두 데이터 포인트(벡터)가 얼마나 다른지를 수치로 표현한 것임
• 거리가 작을수록 두 데이터는 비슷하고, 클수록 다름
• 가장 널리 쓰이는 방식이 유클리디안 거리(Euclidean Distance) — 우리가 일상에서 자로 재는 직선 거리와 동일한 개념임

d(p, q) = √Σ(pᵢ − qᵢ)²

d(p, q)두 점 p와 q 사이의 거리 (최종 결과값)

√ (루트)제곱합의 제곱근 — 단위를 원래 스케일로 되돌리는 역할

Σ (시그마)모든 특성(feature)에 대해 합산 — i번째부터 n번째까지

(pᵢ − qᵢ)²각 특성값의 차이를 제곱 — 음수 방지, 큰 차이에 더 가중치 부여

💡 새 개념

스케일링 Feature Scaling

• 거리 계산 전, 각 특성의 값 범위를 통일시키는 전처리 작업
• 단위가 다른 특성(예: 나이 vs 연봉)이 섞이면 큰 숫자의 특성이 거리를 지배함
• 대표 방법: Min-Max 정규화(0~1 범위), 표준화(평균 0, 표준편차 1)

나이(25~60)와 연봉(2000~8000만원)을 같이 쓰면 연봉이 거리를 독점함 → 스케일링으로 동등한 영향력 부여

핵심 원칙
· 거리 기반 알고리즘을 쓸 때는 반드시 스케일링 먼저
· 스케일링 없이 학습하면 큰 수치의 특성이 결과를 왜곡함

🔍

1. KNN — K-최근접 이웃 알고리즘

"새 데이터가 들어오면, 가장 가까운 K명의 이웃을 찾아 다수결로 정한다" — 직관적인 지도학습 분류기

• Instance-Based Learning(사례 기반 학습): 별도의 모델 파라미터를 학습하지 않고, 학습 데이터 자체를 기억해뒀다가 예측 시점에 사용함
• 새로운 데이터가 입력되면 학습 데이터 전체와의 거리를 계산하고, 가장 가까운 K개를 선택함
• K개 이웃 중 가장 많은 클래스로 분류 결정 (분류 문제 기준)
• 비선형 경계를 자연스럽게 처리함 — 데이터 분포에 따라 복잡한 결정 경계도 형성 가능
• 이상치(outlier)에 상대적으로 강건함 — K가 크면 소수 이상치의 영향이 희석됨
• 데이터셋이 작을 때 특히 효과적임

💡 새 개념

K (하이퍼파라미터) Number of Neighbors

• 몇 명의 이웃을 참고할지 결정하는 값 — 사용자가 직접 지정함
• K가 작으면: 이웃 1~2명만 보므로 민감하고 불안정 (과적합 위험)
• K가 크면: 많은 이웃을 평균내므로 안정적이지만 경계가 흐릿해짐 (과소적합 위험)

k=1이면 가장 가까운 딱 1명의 클래스를 따름 → 이상치 하나가 있으면 바로 틀릴 수 있음

이웃 검색 알고리즘 Neighbor Search Algorithm

• brute: 모든 학습 데이터와 거리를 일일이 계산 — 데이터 적을 때 단순하고 정확
• kd_tree: 데이터를 이진 트리 구조로 분할해 탐색 범위를 줄임 — 저차원 데이터에 빠름
• ball_tree: 데이터를 구(ball) 형태로 분할 — 고차원·비선형 분포에 적합

데이터 1만 건 이상이면 brute보다 kd_tree나 ball_tree 권장

새 데이터 입력

→

전체 학습 데이터와 거리 계산

→

가장 가까운 K개 선택

→

다수결로 클래스 결정

⚠ 주의사항
· KNN은 예측 시마다 전체 데이터와 거리를 계산 → 데이터가 많아질수록 예측 속도 저하
· 고차원 데이터(특성이 수백 개 이상)에서는 "차원의 저주"로 성능 하락 가능
· 반드시 스케일링 후 사용할 것

🔵

2. 군집 분석 — Clustering 이란?

"레이블 없이 데이터 스스로 무리를 짓게 하는" 비지도학습의 핵심 기법

• 군집 분석은 정답 레이블 없이 데이터 간의 유사도(거리)만으로 자연스러운 그룹을 찾아내는 비지도학습임
• 목적은 정확한 분류가 아니라 데이터의 구조 파악 — 복잡한 데이터를 단순한 그룹으로 요약
• 결과 평가는 정확도 대신 군집 간 거리(응집성·분리성)로 측정함
• 후속 작업으로 각 군집의 통계적 특성(평균, 분포 등)을 분석하는 것이 일반적임

항목	Clustering (군집)	KNN Classification (분류)
학습 방법	비지도학습 (레이블 없음)	지도학습 (레이블 있음)
거리 활용	군집 내 유사도 측정	이웃 탐색 기준
목적	데이터 구조 파악 (복잡 → 단순)	새 데이터의 정확한 클래스 예측
성능 평가	군집 간 거리, 혼잡성(실루엣 계수)	정확도(Accuracy)
후속 작업	군집별 통계 분석 (중심값, 분포)	없음

✕

3. K-Means — 중심 기반 군집 알고리즘

"각 데이터를 가장 가까운 중심(Centroid)에 배정하고, 중심을 계속 갱신해 군집을 완성한다"

• 데이터를 K개의 군집으로 나누는 가장 대표적인 클러스터링 알고리즘
• 각 군집의 중심(Centroid)까지의 거리를 기준으로 데이터를 배정함
• 원형(구 형태)에 가까운 군집을 잘 찾아냄 — 복잡한 모양의 군집에는 한계 있음
• 이상치에 민감 — 극단적 이상치 하나가 중심을 크게 끌어당길 수 있음

💡 새 개념

중심값 Centroid

• 각 군집에 속한 모든 데이터 포인트의 좌표 평균값
• 군집의 "대표 위치" 역할을 함

군집 내 점들의 x, y 좌표를 각각 평균내면 그 군집의 중심(Centroid) 좌표가 됨

WSS (Within-Cluster Sum of Squares)

• 각 데이터 포인트와 해당 군집 중심 사이의 거리 제곱합
• K-Means가 최소화하려는 목적 함수 — WSS가 작을수록 군집이 촘촘함

WSS = Σ(xᵢ - cᵢ)² → 각 점 xᵢ에서 가장 가까운 중심 cᵢ까지의 제곱 거리를 모두 합산

K-Means 학습 과정 (3단계 반복)

1

초기 중심값 설정

K개의 초기 중심점을 무작위로 배치함. 초기값에 따라 결과가 달라질 수 있으므로 여러 번 반복하거나 K-Means++ 초기화를 사용함

2

군집 재배정 (Re-assign)

각 데이터 포인트를 가장 가까운 중심에 배정함. 즉, 모든 점에 대해 K개 중심까지의 거리를 계산하고 최솟값을 선택

3

중심 재계산 → 수렴까지 반복

새로 배정된 군집 내 데이터들의 평균 좌표로 중심을 갱신함. 배정이 더 이상 변하지 않을 때까지 2-3단계를 반복

K 값을 어떻게 정할까?
· Elbow Method: K를 늘려가며 WSS를 그리면 꺾이는 지점(elbow)이 최적 K
· 실루엣 계수(Silhouette Score): 군집 응집도와 분리도를 동시에 측정 (-1~1, 높을수록 좋음)

📊

4. 실루엣 계수 — 군집 품질 평가

"내 군집 안에서 얼마나 촘촘하고, 다른 군집과 얼마나 잘 분리됐나?" — 군집 품질의 종합 점수

s(i) = (b(i) − a(i)) / max(a(i), b(i))

s(i)데이터 포인트 i의 실루엣 계수 (-1에서 1 사이)

a(i)같은 군집 내 다른 점들까지의 평균 거리 → 작을수록 군집 내 응집도가 높음

b(i)가장 가까운 다른 군집의 점들까지의 평균 거리 → 클수록 군집 간 분리가 잘 됨

max(...)두 값 중 큰 것으로 나눠 -1~1 범위로 정규화

s(i) ≈ 1

자기 군집에 잘 속하고 다른 군집과 확실히 분리됨 → 이상적인 배정

s(i) ≈ 0

군집 경계에 걸쳐 있음 → 어느 군집에도 명확히 속하지 않는 상태

s(i) ≈ −1

잘못된 군집에 배정됨 → K 값을 바꾸거나 전처리를 재검토할 필요 있음

전체 평균 실루엣 계수
· 모든 데이터 포인트의 s(i)를 평균낸 값으로 전체 군집 품질을 한 수치로 요약
· 일반적으로 0.5 이상이면 합리적인 군집, 0.7 이상이면 우수한 군집 구조로 봄

🌐

5. DBSCAN — 밀도 기반 군집 알고리즘

"K-Means가 못하는 것을 한다 — 불규칙한 형태의 군집 찾기 + 이상치 자동 제거"

• 밀도 기반 클러스터링: 중심이 아니라 데이터가 밀집된 영역을 군집으로 정의함
• K-Means와 달리 K(군집 수)를 미리 지정하지 않아도 됨 — 데이터가 알아서 군집 수를 결정함
• 이상치(노이즈)를 아예 군집에서 제외해 별도 처리함 — 노이즈 제거 효과
• 원형이 아닌 불규칙한 형태의 군집도 탐지 가능
• 구현과 파라미터 튜닝이 복잡하지만, 이상치 많은 실무 데이터에 강력함

💡 새 개념

Epsilon (ε) 탐색 반경

• 한 점 주변에서 "이웃"으로 볼 수 있는 최대 거리
• 이 반경 안에 든 점들을 이웃으로 간주함

ε = 0.5이면, 반경 0.5 안에 있는 점들만 이웃으로 봄

Minimum Points (MinPts) 최소 이웃 수

• ε 반경 안에 MinPts개 이상의 점이 있어야 그 점을 Core Point로 인정
• 이 조건을 못 채우면 Border Point 또는 Outlier(노이즈)로 분류됨

MinPts = 3이면, 반경 내 점이 3개 미만이면 군집의 핵심 멤버로 인정하지 않음

Core / Border / Outlier 포인트

• Core Point: ε 안에 MinPts 이상 → 군집의 핵심
• Border Point: Core가 아니지만 Core의 ε 안에 있음 → 군집의 가장자리
• Outlier(Noise): 어떤 Core Point의 이웃도 아님 → 이상치로 처리, 군집 미배정

DBSCAN이 이상치 제거에 강한 이유 — Outlier를 아예 군집에 넣지 않음

K-Means vs DBSCAN 선택 기준
· 원형 군집 + 이상치 적음 + K 알고 있음 → K-Means (빠르고 단순)
· 불규칙 형태 + 이상치 많음 + K 모름 → DBSCAN (강력하지만 파라미터 튜닝 필요)

🗺️

6. 전체 요약 — 세 알고리즘 한눈에 비교

항목	KNN	K-Means	DBSCAN
유형	지도학습 (분류)	비지도학습 (군집)	비지도학습 (군집)
핵심 아이디어	가장 가까운 K개 이웃 다수결	중심과의 거리 최소화	밀도 높은 영역 확장
K 지정	필요 (이웃 수)	필요 (군집 수)	불필요
이상치 처리	상대적으로 강건	민감 (중심 왜곡)	자동 제거 (노이즈 처리)
군집 형태	—	원형에 최적	임의 형태 가능
주요 파라미터	k, algorithm	n_clusters, init	eps, min_samples
평가 방법	정확도(Accuracy)	실루엣 계수, Elbow	실루엣 계수

거리 계산 (스케일링 필수)

→

KNN: 이웃 K개로 분류

|

K-Means: 중심으로 군집

|

DBSCAN: 밀도로 군집

KNeighborsClassifier KMeans DBSCAN silhouette_score StandardScaler MinMaxScaler