알고리즘-2

kNN Classification (k-근접이웃 분류)

새로운 데이터 점이 주어지면, 주변에서 가장 가까운(유사한) k개의 점들의 클래스를 보고 판단하는 방법

kNN 분류 알고리즘

1. 주어진 모든 점들과 테스트 포인트 간의 유사도 or 거리 (𝑑(𝐱, 𝐱𝑖 )) 계산

2. 가장 가까운 점 k개를 찾고 레이블 읽기

3. k개 점들의 클래스 중 가장 빈도가 높은 클래스를 테스트 포인트의 클래스로 지정

k값의 선택

big k	small k
의사결정 경계가 smooth 해짐 -> 잘 분류를 못함 -> 과소적합 상태와 유사함 -> bias 증가, variance 감소 계산시간 증가	의사결정 경계가 복잡 -> 과적합 상태와 유사함 -> bias 감소, variance 증가 이상치에 매우 민감

* bias : 편향, 데이터 내 모든 정보를 고려하지 않아 지속적으로 잘못된 것을 학습하는 경향, under fitting 과 관련있음

* variance : 다른 training dataset 사용하여 추정했을때 추정값이 변하는 정도

여러가지 변화를 주며 일반화 성능이 좋은 k값 선택해야 함

 

분류 모델에 변화를 주는 방법

- k값의 변경

- 거리(유사도) 측도의 변경

- 측도에 대한 가중치 도입

 

kNN Regression (k-근접이웃 회귀)

새로운 데이터 점이 주어지면, 주변에서 가장 가까운(유사한) k개의 점들의 값을 보고 새로운 점의 값을 예측하는 방법

kNN 회귀 알고리즘

1) 주어진 모든 점들과 테스팅 포인트 간 유사도 혹은 거리 𝑑(𝑥, 𝑥𝑖)를 계산

2) 가장 가까운 점 k개를 찾고 그들의 레이블을 읽는다

3) k개의 최근접 이웃들의 실측값을 기반으로 테스팅 포인트의 예측값 계산(ex. 평균 이용)

 

유사도? 거리 측도?

가까움과 유사도의 정의는 상황에 따라 다름

단위 선택은 거리 측도를 정하는 방법에 큰 영향을 줌

 

평가 측도의 선택

문제에서 가장 중요하게 생각하는 것에 따라 평가 측도가 달라질 수 있음

ex. 암 예측 관련 분류

암인 사람에게 암이 아니라고 진단하는 경우를 최소화해야함

ex. 스팸 메일 분류

스팸이 아닌데 스팸으로 분류되는 경우를 최소화해야함

 

confusion matrix(혼동행렬)

분류에서 가장 많이 사용되는 오분류표

matrix 의 대각선 = 올바르게 분류한 데이터 (TP, TN)

TP : True Positive => positive 라고 예측한게 true

TN : True Negative => negative 라고 예측한게 true

FP : False Positive => positive 라고 예측한게 false -> 실제로는 negavite

FN : False Negative => negative 라고 예측한게 false -> 실제로는 positive

 

Accuracy(정확도)

일반적으로 분류문제의 경우 정확도(accuracy) 를 기준으로 성능 평가

모델이 얼만큼 positive 를 positive 로, negative 를 neagtive 로 잘 분류했는지 판단하는 수치

 

클래스가 불균형한 문제(imbalanced data) 에서 원하지 않는 결과를 얻게될 수 있음

percision(정밀도) 와 recall(재현율)

precision = positive 예측이 맞은 데이터의 수 / positive 라고 예측한 수 = TP / TP + FP

recall = positive 예측이 맞은 데이터의 수 / 실제 positive 수 = TP / TP + FN

 

왜 precision 은 정밀도, recall 은 재현율 이라고 할까 ?

precision 은 positive 라고 예측한 것(TP+FP)에 focus

실제로는 negative 지만 positive 라고 예측한것(FP)에 예민

오류가 없는 것, 즉 정밀한 것에 focus

 

recall 은 실제 positive 인 것(TP+FN)에 focus

실제로 positive 지만 negative 라고 예측한것(FN)에 예민

실제 데이터와의 유사성, 즉 실제 데이터를 얼마나 잘 재현했는지에 focus

 

positive 판단을 엄격하게 하게 될 경우, positive 라고 잘못 판단하는 경우가 줄어드니까 FP를 줄일 수 있음

precision 의 분모가 작아지므로, precision 값은 매우 커짐

positive 판단을 엄격하게 한다는 것은 positive 인데 negative 라고 판단하는 경우가 많아진다는 뜻이므로 FN은 커짐

recall 의 분모가 커지므로, recall 값은 매우 작아짐

따라서 precision 과 recall 값은 trade-off 관계

 

둘 다 높은 수치를 얻는것이 가장 좋은 성능

어느 한 평가지표만 높고, 하나는 낮으면 바람직하지 못함

 

 

ex) 연속 출력의 임계값을 기준으로 결정하는 분류기에서, 임계값을 조절하면 Precision/Recall 조정 가능

 

F1 score

precision 과 recall 의 조화평균

precision 과 recall 을 동시에 볼 수 있는 수치

분류해야하는 클래스의 불균형이 심한 경우, accuracy 가 아닌 F1 score 를 사용

0.0 ~ 1.0 사이의 값을 가지며 높을수록 분류가 잘 된 모델

 

 

 

kNN 알고리즘은 비모수적 접근방법

-> 모수 추정을 하지 않음

-> 데이터 생성과정에 관여하는 내재적분포에 대한 가정을 하지 않음

 

모델링 과정에서의 가정

- 데이터는 거리 개념이 있는 특성 공간에 존재한다

- 레이블이 달린 훈련 데이터가 있다

- k값의 선택은 경험과 시행착오를 거쳐 스스로 한다

- 관측된 특징과 레이블 값들은 어떤 식으로든 연관성이 있다

 

kNN의 장단점

장점	단점
- 구현하기 쉬움 - 특성/거리측도 선택이 유연 - 다중 클래스 문제를 위해 특별히 더 고려할 것이 없음 - 레이블이 달린 충분한 데이터셋만 있다면 실용적 - 훈련데이터를 추가하기기만 하면 됨 : 업데이트 용이	- 최근접 이웃 수 k를 결정해야 함 - 예측때마다 데이터에 대해 거리/유사도 계산을 다시해야함    -> 계산시간이 오래걸림 - 훈련 시간은 걸리지 않지만 테스트 시간이 많이 걸림 - 저장용량 커짐 - 의미있는 거리/유사도 함수를 선택해야함

 

kNN의 속도 개선 방법

훈련시간 = O, 테스트시간 = ND (N = 데이터수, D = 차원)

D의 축소 = 차원 축소

N의 축소 => 모든 훈련 데이터를 비교하지 않으려면 ?

: N 보다 많이 작은 n 개 (n << N)의 잠재적 근접 이웃을 빠르게 식별

 

군집화와 거리 측도

머신러닝 알고리즘의 종류

지도학습	정답이 있는 훈련 데이터셋으로 학습 정답 : 실제값, 예상값	선형회귀, k-근접이웃, 로지스틱회귀, 의사결정트리, 신경망, SVM
비지도학습	정답이 없는 훈련 데이터셋으로 학습	군집화, 확률분포 추정, 차원 축소, k-평균법, 기댓값 최대화EM, 주성분분석PCA, 이상치 탐색
준지도학습	지도학습과 비지도학습의 혼합 정답이 있는 훈련 데이터는 적고, 정답이 없는 데이터는 많은 환경에서 사용
강화학습	어떤 환경 안에서 정의된 에이전트가 현재의 상태를 인식하여, 선택 가능한 행동들 중 보상 을 최대화하는 행동 혹은 행동 순서를 선택하는 방법 탐색과 활용 간의 절충을 통해 최적의 행동을 찾음

 

군집화

유사한 개체들을 집합으로 집단화 하는것

군집 내 유사도를 높이고, 군집 간 유사도를 낮춤

비지도 학습이기 때문에 미리 정의된 클래스가 없음 -> 클래스 레이블과 클래스 수를 데이터에서 직접 찾아냄

데이터 분포에 대한 통찰을 얻기 좋음

다른 알고리즘을 사용하기 전 전처리용으로 많이 사용

 

군집화 알고리즘의 요건

- 확장성(시공간 측면) : 샘플 뿐만 아니라 전체 데이터를 처리할 수 있어야 함

- 다양한 데이터 형식(수치, 이산, 범주 ...) 처리가 가능해야 함

- 제약조건 기반 군집화

- 해석가능성, 효용성

 

군집화 접근방법

방법	설명	얘시
분할적 방법	여러개의 분할을 생성, 정해진 기준으로 평가	k-Means, k-Medoids, k-Modes, Fuzzy c-means
계층적 방법	정해진 기준을 기반, 데이터(또는 개체) 집합을 계층적으로 분해	Divisive(e.g., DIANA), Agglomerative(e.g., AGNES, BIRCH, CAMELEON,…)
밀도 기반 방법	연관성과 밀도함수에 기반한 군집화	DBSACN, STING, ENCLUE, OPTICS, Wave Cluster,…
격자기반 방법	다단계 입도 구조에 기반한 군집화	MST Clustering, OPSSUM, SNN Similarity Clustering
모델 기반 방법	각 군집에 대하여 모델에 대한 가설을 세우고 서로 가장 잘 맞는 모델을 찾는 것.	EM, COBWEB, Auto class, ANN Clustering
빈발 패턴 기반방법	자주 출현하는 패턴의 분석에 기반한 군집화	p-Cluster
사용자 안내 또는 제약 기반 방법	사용자가 지정한 또는 제약 사항을 고려하면서 군집화하는 방법	COD, Constrained Clustering(준지도학습)
연결 기반 방법	다양한 방법으로 서로 연결된 개체들에 대한 방법	SimRank, LinkClus

 

거리측도(Distance Metrics)

머신러닝에서의 유사성 표현방법

x, y, z 를 개체 공간의 세 개체라고 하자.

x와 y 간의 거리(비유사성, dissimilarity)은 다음과 같은 성질을 갖는 함수 𝑑(𝐱, 𝐲) 로 표시되는 실수다.

여러가지 거리 측도

1. 코사인 유사도

1 이면 동일, 0 이면 독립, -1 이면 반대

벡터의 크기는 상관 없고 방향이 중요할 때 사용

ex) 특정 단어의 출현 빈도를 사용해서 텍스트와 토픽의 유사성 판단

 

2. 자카드 유사도

 

유사성이 높을수록 자카드 유사도는 커짐

자카드 거리 = 1 - 자카드 유사도

유사성이 높을수록 거리가 짧아짐

 

3. 마할라노비스 거리

Σ: x 와 y 의 공분산 행렬, 공분산행렬의 역행렬은 data distribution 을 원형으로 보정하는 역할을 함

어떤 일이 얼마나 일어나기 힘든 값인지(일어나기 이상한 값인지) 수치화, 마할로비스 거리가 작을수록 덜 이상함

거리에 상관관계가 고려되며, 크기 불변성을 가진다

유클리드 거리로 보았을떄 x1y >  x2y

마할라노비스 거리 x1y < x2y (전체적인 분포에서 멀리 떨어져있음)

 

4. 민코프스키 거리 (p-norm)

p값에 따라 이름이 달라짐

5. Kullback‐Leibler(KL) divergence

두 확률분포의 차이를 나타내기 위해 사용되는 측도

미지의 참 확률분포 p(x) 대신 근사 확률분포 q(x)를 사용할 때, x값을 명시하기 위헤 필요한 평균 추가 정보량

or 크로스 엔트로피와 엔트로피 간 차이

 

차원의 저주

차원이 증가하면서 학습데이터 수<차원 수 가 되어 성능이 저하되는 현상 (관측치<변수 수)

차원이 증가할수록 변수가 증가, 개별 차원 내에서 학습할 데이터 수가 적어짐

차원이 증가할수록 빈공간이 많아짐

빈공간 = 정보가 없는 공간이기 때문에 빈공간이 많을수록 학습시켰을 떄 모델 성능이 저하됨

 

Sample Density (feature value들이 5 unit 내에 있다면)

 1D: sample space = 5 unit ⟹ density = 10 samples/5 units = 2 samples/interval

 2D: sample space = 25 unit squares ⟹ density = 10/25 = 0.4 samples/interval

 3D: sample space = 125 unit cubes ⟹ density = 10/125 = 0.08 samples/interval

점점 더 sparse 해져서 분리 초평면을 찾기 쉬워지지만, 저차원으로 다시 사영했을때 overfitting 된 결과물이 나옴

■ 20%를 위한 샘플 수

 1D에서 10^2 개 였다면, 3D 및 5D에서 각각 10^6 및 10^10 개의 데이터가 필요

 

- 고차원에서의 거리 차이

원점에서 데이터포인트까지의 거리의 최댓값 및 최소값의 차이가 의미없어짐

모든 점들이 유사하게 보일 수 있고, 거리 측도가 효과성을 잃음

 

군집타당성지표

최적의 군집 개수를 판단하기 위한 지표

1) 군집 간 거리

2) 군집의 지름

3) 군집의 분산

 

Dunn index (던 계수)

= 군집 거리의 최소값 / 군집 지름의 최댓값

Dunn index 가 클수록 좋은 군집화

군집 간 거리는 멀수록, 군집 내 분산은 작을수록 좋음

 

Silhouette index (실루엣 계수)

s(𝑖) > 0.5 이면 군집화가 타당한 것으로 평가

 

k-Means (k-평균법)

대표적인 군집화 알고리즘, 비계층적(분할적) 군집화 방법

 

step

1. k값을 정하고 무작위로 k개의 점을 임시 중심점(군집의 중심이 될 점)으로 정함

2. 미리 정해진 거리 측도를 사용하여 각 점과 k개 중심점들 간 거리를 계산, 모든 점들을 가장 가까운 중심점에 할당

(ex. 유클리드 거리, 코사인 유사도)

3. k개의 군집 각각에 대해 중심점에 할당된 데이터의 점들의 평균 위치를 계산하고, 그 위치로 중심점 이동

4. 소속 군집이 변경되는 사례가 없거나 정해진 기준 이하이면 알고리즘 중지 / 아니면 3으로 감

k-평균법의 장단점

장점	단점
레이블(정답)이 없는 데이터로 데용량 데이터의 자료 구조를 찾아내는 탐색적 기법 거리 척도를 잘 정의하면 거의 모든 형태 데이터에 적용가능 빠른 속도/간단 -> 다른 모델의 출발점으로 많이 사용	k값의 선택이 주관적임 근접/유사성의 정의에 따라 성능이 크게 좌우됨 이상치에 민감(이상치가 데이터 분포를 왜곡시키므로) 수렴의 문제 : 두가지 가능한 해 사이를 오가는 루프 해석의 문제 : 답이 안 유용할수도

 

k-중앙점

참조점으로 군집내 평균점을 택하는 대신, 군집내 개체들 중 가장 중앙에 위치한 중앙점을 택할 수 있음

* 중앙점 : 군집 내 다른 점들과의 거리 합이 가장 작은 점, 데이터셋 내 점들 중 하나

 

계층적 군집화

계층적 트리 모형을 이용, 개별 개체들을 순차적, 계층적으로 유사한 개체/그룹과 통합해서 군집화를 수행하는 알고리즘

k-평균법과 달리 군집 수를 사전에 정하지 않아도 됨

Dendorgram 이용해서 개체 결합 순서를 나타냄, 적절한 수준에서 트리를 자르면 몇개의 군집으로 나뉨

 

step 

0. 사전에 모든 데이터포인트간 거리/유사도를 계산해두어야 함

1. 가장 가까운 쌍을 선택 -> 묶어줌

2. 개체-개체 거리를 군집-개체 거리로 변경

3. 군집-개체 거리 중 가장 가까운 것끼리 상위 단계로 묶어줌

4. 모든 요소가 묶일때까지 반복 !