유사도(Similarity)와 거리(Distance)


유사도는 객체를 특징벡토로 표현하는 것으로 시작합니다. 특징을 정의하는 공간에서 두 객체가 가까울수록 두 객체는 더 비슷하도고 할 수 있습니다. 거리가 가까우면 유사하고 거리가 멀면 유사하지 않습니다. 즉 0에 가까울 수록 유사하다 할 수 있고 1에 가까울수록 유사하지 않다고 할 수 있습니다.


유클리드 거리


유클리드 거리는 두 가지 객체의 특징을 2차원 공간에서 (x,y)로 A, B라는 점으로 표현하고 각각의 좌표를 직각 삼각형으로 연결하고 사선의 변을 연결한 A와 B의 거리를 유클리드 거리라고 합니다. 단, 유클리드 거리는 2차원에 국한되지 않고, 3개의 특징을 가진 객체라면 (x,y,z)로 표현할 수 있습니다. 쉽게 말하자면, 어릴 때 부터 배워온 그 거리 개념으로 x, y축으로 나타내는 그 공간을 유클리드 공간이라고 생각하시면 됩니다.


최근접 이웃 추론(Nearest Neighbor)


최근접이웃이란 가장 비슷한 객체를 말합니다. 최근접 이웃 추론은 연관규칙분석의 하나로 연관성이 높은 객체들로 구성된 규칙집합을 생성합니다. 주로 추천 시스템에 사용되고 "장바구니 분석"이라고도 불립니다. 

유클리드 거리


타겟 변수를 예측하려는 데이터를 받으면 훈련세트에 있는 모든 데이터를 조사해 예측하려는 데이터와 가장 비슷한 데이터를 몇 개 찾아냅니다. 그 다음 타겟 값을 알고 있는 최근접 이웃에 기반한 새로운 데이터의 타겟값을 예측하면 되는 것입니다.


그렇다면 최근접 이웃 추론을 하기 위해서는 얼마나 많은 이웃이 필요할까요?


두 계층의 문제의 경우 다수결로 투표할 때 동점이 되지 않도록 홀수를 사용합니다. 최근접 이웃의 알고리즘은 종종 3-NN, K-NN형태의 약자로 표현합니다. 이때 K는 이웃의 개수를 의미하며, K가 커질 수록 이웃과 잘 어울릴 확률이 높아집니다. 하지만 K가 너무 커지게 되면 과적합화를 피할 수 없게 되므로 k를 1부터 늘여나가면서 가장 성능이 좋은 K를 찾아야 합니다.

가중치 적용투표, 유사도반영투표

이웃 표본개수를 확정했더라도 표본과 이웃의 거리가 다른 점 또한 간과할 수는 없습니다. 최근접 이웃의 레이블에 거리에 대한 가중치를 반영한 것이 가중치 적용투표, 유사도반영투표라고 합니다.


기하해석, 과적합, 복접도 제어

최근접 이웃기법을 시각화한 것으로 객체공간을 체계적으로 조사하여 각 점으로 분류하고 분류가 바뀌는 경계점을 만들어가면서 계산할 수 있습니다. 다르게 분류된 객체 사이에 점선을 그으며 들쭉날쭉한 도형이 생성되는데 일반적으로 모든 최근접 이웃 분류자의 경계선은 불규칙적인 반면, 객체 공간 훈련에 사용된 데이터에 딱 맞는 경계선이 만들어집니다. 하나의 섬처럼 표현된 객체는 일종의 노이즈나 외곽객체라고 볼 수 있습니다.


k-NN분류자에서 k는 복잡도를 나타내는 지표이며, k=1일 경우 매우 복잡한 모델을 얻게 됩니다.


최근접 이웃방법의 문제점


1. 모델 명료성

모델명료성에는 결정에 대한 정당성과 전체 모델의 명료성 두 가지 측면이 있습니다. 최근접 모델은 데이터로부터 어떤 지식을 마이닝해서 알아냈는지, 깊이 있게 설명하는 일은 어렵습니다. 따라서, 최근접 이웃모델에 담겨진 지식은 일반적으로 이해하기 어려우므로 명료성과 정당성이 중요한 경우에 최근접 이웃 모델은 맞지 않는 경우가 많습니다.


2. 차원 및 영역지식

고객 DB에는 여러가지 정보가 저장되어 있습니다. 예를 들어 신용카드에 가입할 지 안할지 여부와 관련이 있을 수 있지만 관련이 없는 정보도 다수 포함하고 있습니다. 이 문제는 차원이 높아서 발생하는 고차원문제라고 하며 차원수의 저주(Curse of Dimensionality)라고 합니다. 간단히 말해 거리를 계산할 때 모든 속성을 포함시키면 관련 없는 속성들이 객체에 너무 많은 영향을 주 객체 유사도 측정에 혼란을 일으키게 되는 것을 말하며, 해결방법으로는 특징을 신중하게 결정해 데이터 마이닝 모델에 포함할지를 결정하는 특징선택(Feature Selection)과 속성마다 서로 다른 가중치를 부여해 거리함수를 조절하는 방법이 있습니다.


3. 계산효율성

객체와 가장 가까운 이웃을 찾기 위해 DB를 검색함으로 대부분의 계산은 예측 및 분류 단계에서 발생하는 데 이 때 계산량이 엄청나게 많아 처리 부담이 발생하게 됩니다. 따라서 수십미리초 안에 계산해야하는 온라인 타겟광고 등에는 최근접 이웃기법을 사용하기 어렵습니다.


유사도 및 이웃에 관한 주요 세부사항


이질적인 속성


지금까지 유클리드 거리를 이용해 거리 계산만 하였으라 속성이 추가된 사례가 있습니다. 예를 들면 나이와 화폐가치를 들 수 있는데 속성간의 단위를 차별화 하지 않으면 소득의 10원과 나이의 10살을 동일하게 처리하게 됩니다. 최근접 이웃에 기반한 시스템은 데이터 전반부에서 변수 값의 규모나 단위를 조정하거나, 고정된 개수의 항목에 배분하는 전처리 작업이 수반되어야 합니다.


다양한 거리 함수


유클리드 거리(Euclidean Distance)(L2-Norm)

앞서 말했듯이 가장 널리 사용되는 거리 측정법입니다.


맨하탄거리(Edit Distance)(L1-Norm)

격자형으로 된 맨하탄 시내 같은 곳에서 두 점 사이에 이동하는 거리 측정법으로 '가로이동거리+세로이동거리=전체이동거리' 입니다.

빨간색 거리 = 파란색 거리


자카드거리(Manhattan Distance)

객체 집합간의 거리를 표현하는 것이며 두 집합이 얼마나 유사한 지 알 수 있기때문에 양쪽 객체 모두에게 있는 특징은 중요하지만 한쪽에만 있는 특징은 중요하지 않은 경우에 사용합니다.


코사인거리(Cosine Distance)

두문서의 유사도를 분류할 때 사용되는 거리로 텍스트를 분류할 때 어떤 문서가 다른 문서보다 훨씬 길다는 점을 무시하고 단지 내용에만 집중하고자 하는 경우 사용합니다.



편집거리(Edit Distance), 레벤쉬타인 거리(Leveinshtein Distance)

문자열 간의 거리 측정할 때 사용되며 글자를 변환하고 치환하는 편집연산을 활용해 한 문자열을 다른 무자열로 변환하기 위한 편집횟수를 계산하고 혼합하여 전체적인 유사도를 구합니다. 때문에 두 문자열이 얼마나 비슷한 지 확일할 때 사용되며 편집하는 데 걸리는 편집 횟수를 측정하여 편집거리를 구할 수 있습니다.



2017/06/03 - [Cyong's 마케팅/Data Science] - [Data Science] Ch.5 과적합화

2017/05/28 - [Cyong's 마케팅/Data Science] - [Data Science] Ch.4 데이터에 대한 모델 적합화(수학 함수를 이용한 회귀분석과 로지스틱 회귀분석)

2017/05/27 - [Cyong's 마케팅/Data Science] - [Data Science] Ch.3 데이터에 대한 모델 적합화(수학 함수를 통한 분류)

2017/05/24 - [Cyong's 마케팅/Data Science] - [Data Science] Ch2. 트리구조모델

2017/03/25 - [Cyong's 마케팅/Data Science] - [Data Science] Ch1. 예측모델링_정보전달하는 속성 찾아내기



+ Recent posts