3-2 알고리즘 kNN,k-평균법
도서 | 데이터과학 입문 요약
데이터과학 입문의 도서를 공부하며 정리하는 글입니다.
개인적인 견해는 들어가지 않습니다.
k- 근접이웃 (k-NN, k-Nearest Neighbors )
분류되었거나 가 분류된 많은 객체가 있을 때, 아직 분류되지 않은 객체를 자동으로 분류명을 붙이는 알고리즘
ex) 별 1,2,3,4,5 개 중 예상 별점을 자동으로 메겨주는 알고리즘
k-NN 선형회귀로 풀 수 있지 않을까?
일반적으로 선형회귀는 연속적인 결과값을 받는다. ( y = f(x) )
k-NN은 범주형 결과값을 가져야 하므로 선형회귀로는 어려워 보인다.
하지만, 경계값 개념을 둔다면. 대안이 될 수 있다.
나이 + 소득 -> 신용점수라는 선형회귀 모델이 만들어지고, 300,500,700점을 기준으로 매우낮음, 낮음, 보통, 높음 등으로 분류할 수 있는 것이다.
그렇지만 연속적인 결과값을 가질 수 없는 조사 ( 선호도 , 정당지지 ) 등은 이처럼 대입하기는 어렵다.
k-NN을 직관적으로 말하자면
분류하고자 하는 것과 유사한 속성을 가진 것들을 찾아 그것들의 분류명을 보고 다수결에 의해 분류명을 부여하는 것
k-NN의 자동화를 위해
유사도, 근접성을 정의해야 한다.
이를 정의하면 유사정도를 알 수 있고, 가장 유사한 것들을 이웃이라 칭한다.
새 분류대상의 이웃들에게 투표권을 준다.
몇 명의 이웃에게 투표권을 주어 투표하게 할 것인가? 이 값을 k값이라 한다.
k-NN의 절차
유사도 or 거리 척도를 결정한다.
분류명이 있는 원래의 데이터를 훈련데이터세트, 검증세트로 나눈다.
평가척도( 훌륭하다고 판단하는 기준 )를 선택
k값을 변화시키면서 k-NN을 여러번 수행하고, 매번 평가척도의 값을 계산
평가척도가 가장 좋을 때의 k값을 최적값으로 한다.
k 값이 정해졌으면 훈련데이터세트를 사용해, 분류명을 예측하고자 하는 사람들로 구성된 검증세트를 만든다.
k-NN의 ( 유사도 또는 거리척도 분석 )
단위문제 - 모형화에서의 위험
이는 매우 중요하다.
나이를 년(year), 소득을 만원단위로 한다면
-> (30, 3500), (35, 4000),...
하지만, 나이는 같되, 소득을 천원단위로 한다면
-> (30, 35000), (35, 40000),...
이렇기에 변수의 단위는 중요하며, 통계학에서 사전정보( prior )라고 부른다.
거리척도 분석
유클리드 거리 (euclidean distance)
두 개의 서로 다른 점이 있다.
각 요소 간의 차이의 제곱을 다 더하고 제곱근을 취한 값.
코사인 유사도 (cosine similarity)
두 개의 실수값을 갖는 속성벡터 x,y간에 사용될 수 있다.
값이 1이면 완전 동일, 0이면 상호 독립, -1이면 완전 반대
자커드 거리 (jaccard distance)
객체집합간의 거리를 표현, 두 집합이 얼마나 유사한지 표시
예를들어 cathy의 친구들 { Kahn, Mark, Laura,…}
Rachel의 친구들 { Mladen, Hahn, Mark, …} 사이의 거리를 찾는 계산
마할라노비스 거리 (mahalanobis distance)
2개의 실수벡터 간에 사용.
유클리드 거리에 비해 상관을 고려할 수 있고 단위와 무관한 거리.
해밍 거리 (hamming distance)
2개의 문자열, 같은 길이의 DNA 서열 간의 거리를 구하는 데 사용
문자의 위치를 옮겨가며 그 위치에 있는 문자들이 서로 같은지 보고 다르면 1씩 늘려나간다.
맨해튼 거리 (manhattan distance)
두 개의 k-차원 실수벡터 간 거리
격자 모양인 맨해튼의 도심거리를 다니는 택시를 머릿속으로 그려보라고 권한다.(빌딩을 가로질러 대각선으로는 다닐 수 없다)
p,q -> 벡터공간, i -> 벡터의 i 번째 요소데이터 형태에 따라 사용하는 거리 척도가 있다.
각각 상황에 알맞은 알고리즘을 사용하고 필요한대로 확장시켜 사용할 수 있다.
훈련데이터세트와 검증세트
기계학습 알고리즘은 대부분 훈련 > 검증 단계를 거친다.
k-NN에서의 훈련단계는 이미 검증되어(정답이 나와있는) 분류명이 정해진 데이터를 입력하여, 원하는 분류로 얼만큼 잘 분류되는지 확인하면 된다.
평가척도의 선택
모형이 잘 설계된 것인지 판단하기 위해 민감도, 특이도를 조절해야한다.
민감도 : 환자를 환자라고 옳게 진단할 확률 ( 참긍정률 이라고도 함 )
특이도 : 정상인을 정상이라고 맞게 진단할 확률 ( 참부정률 이라고도 함 )
정확도 : 전체 분류된 숫자 중에서 옳게 분류된 갯수의 비율. -> 오분류율은 ( 1 - 정확도 )
정밀도, 재현율의 평가척도도 있음(5장에서 소개)
k의 선택
스스로 결정해야할 모수 이기때문에 여러 k값으로 시도해보고 평가척도의 값을 점검하여야 한다.
이진분류 - 둘중의 하나의 결과가 나올 경우 다수결로 결과를 낼 경우를 위해 k값은 홀수가 좋다.
k-NN 모형화 과정에서의 가정
데이터간의 ‘거리’개념을 사용할 수 있는 특징 공간을 정의한다.
훈련데이터세트는 2개 이상의 계급으로 분류 또는 분류명을 붙인다.
k를 선택한다.
관측된 특징과 분류명은 어떤식으로든 연관성이 있다고 가정한다.
선형회귀와 k-NN 모두 지도학습에 포함된다.
K-평균법
지도학습은
지도학습은 정답을 알고 선택한 평가척도 내에서 가능한 한 가장 정확한 모형을 구하는 것.
-> 이미 알고있는 수많은 [x,y] 그룹을 통해 y=f(x)가 될 가장 적합한 함수를 알아내는것
비지도학습은
목표 패턴이 주어지지 않고, 입력 패턴에 근거한 기계학습.(자율학습)
데이터를 군집화하면서 정답을 만들어 가는 것
k-평균법의 목표는 데이터를 세분화, 그룹화 하는것.
이 과정은 층화(stratify), 집단(group), 군집(cluster) 의 명칭으로 불린다.
사용사례
사용자별로 다른 경험을 제공. 프린터를 가긴 것으로 예상되는 사람에게 토너를 권함.
통계학의 계층적 모형화와 비슷
설문 결과를 모형화할 때 가족구성에 의한 영향과 지리적 영향을 분리한다.
k-평균법은
구분을 나타내는 속성을 나타내는 5차원 공간에 데이터가 있다면, 성별의 축, 소득의 축으로 구분할 수 있다.
축을 따라 분류명을 짓고. 묶음조합으로 구성된다.
하나의 격자점은 각 속성의 조합.
5차원의 각 묶음마다의 마케팅 전략을 세우는건 불가능
이를 k개로 묶을지 정하는 알고리즘이 k-평균법, k개로 묶는 군집화 알고리즘이다.
k-평균법의 수행과정은
d차원 공간에서 k개의 중심점(군집의 중심) 을 임의로 선택.
데이터에 가깝게 잡고, 서로 떨어뜨린다.
각각의 데이터포인트를 가장 가까운 중심점에 할당
중심점에 할당된 데이터 포인트의 평균위치로 중심점을 이동
할당작업에 변화가 없거나 거의 없을때까지 3-5번 반복
알고리즘 종료 후, 이를 해석하는 것이 데이터 과학자가 할 일이며 k를 조절해야할 수도 있다.
k-평균법의 문제점은
k값은 1< k < n(데이터 포인트 갯수) 이라는 측면에서 상한값이 있지만 k값은 분석자의 감에 크게 좌우
수렴의 문제 : 알고리즘이 루프에 빠져 2개의 결과 사이를 반복이동 할 경우, 결과값이 없을수도 있다.
해석의 문제 : 정답이 전혀 도움이 되지 않을 수 있다.
결론
k-NN과 k-평균법은 유사한 객체들을 묶어주는군집화 알고리즘이다.
거리, 평가척도 개념이 중요하며 선택에 주관성이 따른다.
이 밖에도 나이브베이즈, 그래프 군집화, 계층적 군집화, 모형기반 군집화가 있다.
