k-NN

k-Nearest Neighbors

---

• 정의 : 기하 거리를 규칙으로 하여 관측치를 분류하는 알고리즘

  

  \[\hat{y}=\text{arg} \max_{C}{\sum_{i=1}^{k}{I(y_{i}=C)}}\]

• 한계점

  • 검색 비용 문제
    • 관측치 갯수만큼 거리를 계산해야 함
  • 거리 측정 함수 설정 문제
    • 분석가가 문제에 적합한 함수를 판단해야 함
    • 고차원으로 갈수록 거리 개념이 무의미해짐
    • 범주형 변수의 경우 각 범주 간 거리를 정의해야 함

Distance

---

Manhattan Distance

• 맨해튼 거리(Manhattan Distance; L1) : 두 점 사이의 엣지(Edge) 갯수

  • $\overrightarrow{i_{1}}, \overrightarrow{i_{2}}, \cdots, \overrightarrow{i_{n}}$ 를 기저벡터로 사용하는 $n$ 차원 좌표계에 위치한 두 벡터 $\overrightarrow{a}, \overrightarrow{b}$ 에 대하여 각 축 방향으로의 기저벡터 단위 거리를 합산한 값

• 계산 방법

  • 벡터 $\overrightarrow{a},\overrightarrow{b}$ 를 다음과 같이 정의하자

    \[\begin{aligned} \overrightarrow{a} &= \begin{pmatrix}a_1&a_2&\cdots&a_n\end{pmatrix}\\ \overrightarrow{b} &= \begin{pmatrix}b_1&b_2&\cdots&b_n\end{pmatrix} \end{aligned}\]

  • $\overrightarrow{a}$ 와 $\overrightarrow{b}$ 의 맨해튼 거리 $d_{L1}(\overrightarrow{a},\overrightarrow{b})$ 는 다음과 같음

    \[\begin{aligned} d(\overrightarrow{a},\overrightarrow{b}) &= || \overrightarrow{a} - \overrightarrow{b} ||_{L1} \\ &= \displaystyle\sum_{i=1}^{n} |a_i - b_i| \end{aligned}\]

Euclidean Distance

• 유클리드 거리(Euclidean Distance; L2) : 두 점 사이의 직선 거리
  • $\overrightarrow{i_{1}}, \overrightarrow{i_{2}}, \cdots, \overrightarrow{i_{n}}$ 를 기저벡터로 사용하는 $n$ 차원 좌표계에 위치한 두 벡터 $\overrightarrow{a}, \overrightarrow{b}$ 에 대하여 각 축 방향으로의 기저벡터 단위 거리의 제곱을 합산한 후 제곱근한 값
• 계산 방법

  • 벡터 $\overrightarrow{a},\overrightarrow{b}$ 를 다음과 같이 정의하자

    \[\begin{aligned} \overrightarrow{a} &= \begin{pmatrix}a_1&a_2&\cdots&a_n\end{pmatrix}\\ \overrightarrow{b} &= \begin{pmatrix}b_1&b_2&\cdots&b_n\end{pmatrix} \end{aligned}\]

  • $\overrightarrow{a}$ 와 $\overrightarrow{b}$ 의 유클리드 거리 $d_{L2}(\overrightarrow{a},\overrightarrow{b})$ 는 다음과 같음

    \[\begin{aligned} d(\overrightarrow{a},\overrightarrow{b}) &= || \overrightarrow{a} - \overrightarrow{b} ||_{L2} \\ &= \sqrt{\displaystyle\sum_{i=1}^{n} (a_i - b_i)^2} \end{aligned}\]

Cosine Distance

• 코사인 거리(Cosine Distance; $\cos$) : 임의의 두 점에 대하여, 원점과 각 점을 잇는 직선의 사이각 $\theta$ 의 코사인 값

• 계산 방법

  • 벡터 $\overrightarrow{a},\overrightarrow{b}$ 를 다음과 같이 정의하자

    \[\begin{aligned} \overrightarrow{a} &= \begin{pmatrix}a_1&a_2&\cdots&a_n\end{pmatrix}\\ \overrightarrow{b} &= \begin{pmatrix}b_1&b_2&\cdots&b_n\end{pmatrix} \end{aligned}\]

  • $\overrightarrow{a}$ 와 $\overrightarrow{b}$ 의 코사인 거리 $d_{cos}(\overrightarrow{a},\overrightarrow{b})$ 는 다음과 같음

    \[\begin{aligned} d(\overrightarrow{a},\overrightarrow{b}) &= \cos{\theta}\\ &= \frac{\overrightarrow{a}^{T}\overrightarrow{b}}{||a||\cdot||b||}\\ &= \frac{\sum_{i=1}^{n}{a_{i}b_{i}}}{\sqrt{\sum_{i=1}^{n}{a_{i}^{2}}} \cdot \sqrt{\sum_{i=1}^{n}{b_{i}^{2}}}}\;(a_{i^{\forall}}\in\overrightarrow{a},b_{i^{\forall}}\in\overrightarrow{b}) \end{aligned}\]

Haversine Distance

• 하버사인 거리(Haversine Distance; $\text{hav}$) : 구 표면상에 존재하는 두 지점에 대하여, 위도($\varphi$), 경도($\lambda$) 및 호 중심각($\Theta$)을 활용하여 측정한 호의 길이

• 계산 방법

  • 반지름이 $r$, 호 $\overline{AB}$ 의 중심각이 $\Theta$ 일 때, 호 $\overline{AB}$ 의 길이 $d(A,B)$ 는 다음과 같음

    \[\begin{aligned} d(A,B) &= r \cdot \Theta \end{aligned}\]

  • 점 $A$,$B$ 의 위도가 $\varphi_{A}$,$\varphi_{B}$, 경도가 $\lambda_{A}$,$\lambda_{B}$ 이고, 호 $\overline{AB}$ 의 중심각이 $\Theta$ 일 때, 호의 길이 $\text{hav}{\Theta}$ 는 다음과 같음

    \[\begin{aligned} \text{hav}{\Theta} &= \text{hav}(\varphi_{B}-\varphi_{A}) + \cos{\varphi_{A}} \cdot \cos{\varphi_{B}} \cdot \text{hav}(\lambda_{B}-\lambda_{A}) \end{aligned}\]

  • $\sin$, $\cos$, $\text{hav}$ 의 관계는 다음과 같음

    \[\begin{aligned} \text{hav}{\Theta} &= \sin^{2}{\frac{\Theta}{2}}\\ &= \frac{1-\cos{\Theta}}{2} \end{aligned}\]

  • 따라서 반지름, 경도, 위도가 주어졌을 때 호 $\overline{AB}$ 의 길이 $d(A,B)$ 는 다음과 같음

    \[\begin{aligned} d(A,B) &= r \cdot \Theta\\ &= r \cdot \text{archav}(\text{hav}{\Theta})\\ &= 2r \cdot \arcsin(\sqrt{\text{hav}{\Theta}})\\ &= 2r \cdot \arcsin\left(\sqrt{\text{hav}(\varphi_{B}-\varphi_{A}) + \cos{\varphi_{A}} \cdot \cos{\varphi_{B}} \cdot \text{hav}(\lambda_{B}-\lambda_{A})}\right) \end{aligned}\]

---

이미지 출처

• https://076923.github.io/posts/Python-opencv-43/