Chapter 10. Distance and Network Methods

Nearest Neighbor Classification

- 어떤 training example이 target에 가장 가까운지 확인해서 class label을 붙이는 것

- distance function을 올바르게 정의하는 것이 중요

- 장점: simplicity, interpretability, non-linearity

- k-nearest neighbor

 

Distance Metrics

다음과 같은 조건을 만족하는 경우

- d(x, y) >= 0 for all x, y (positivity)

- d(x, y) = 0 iff x = y (identity)

- d(x, y) = d(y, x) (symmetry)

- d(x, y) <= d(x, z) + d(z, y) (triangle inequality)

 

Not a Metric

다음과 같은 자연 유사성 측정 값들은 distance metric이 아니다.

- correlation coefficient (-1~1)

- cosine similarity, dot product

- mutual information measures

- cheapest airfare 

 

Euclidean Distance Metric

c_i : weighted sum

- 최소한 정규화를 통해 차원을 비교가능하게 해야 함

 

L_k Distance Norms

- 유클리드 거리를 일반화하기 위해서는 다음과 같은 식 사용

- k=1 일 때, Manhattan distance metric

- k=∞ 일 때, maximum component 

- k는 largest and total dimensional difference 사이의 tradeoff를 조절

p1(2, 0), p2(1.5, 1.5) 중 (0, 0)에서 더 먼 점은?

- k=1일 때, k=2일 때, k=∞일 때 먼 점이 다르다.

- distance metric은 어떤 점이 더 가까운지 설정

 

Circles for different k

- L_k circle의 모양은 원점에 대해 어떠한 점이 동등한 것들인지 나타낸 것

 

Projections from higher dimensions

- Projection method (ex.SVD): 표현 복잡도를 줄이기 위해 차원을 축소

- nearest neighbor는 원래 공간에 비해 확고해질 것

 

Regression / Interpolation by NN

- NN이라는 컨셉을 function interpolation에 이용할 수 있다.

- k개의 근접 점의 값의 평균을 내는 방식

- weighted average scheme는 (1) distance rank, (2) actual distances에 의해 따라 점들을 다르게 값을 매길 수 있다.

- 분류에도 비슷한 방식을 이용할 수 있다.

 

Gender Classification by Height/Weight

- k가 커지면 더 매끄러운 구분선을 만들 수 있음

 

Seeking good analogies

- 많은 지식의 분야는 analogy(비유)에 기초해 있다.

* Law: 어떤 법적 판례가 이 사례와 비슷한가?

* Medicine: 비슷한 증상을 가졌던 환자를 과거에 어떻게 치료했고, 그 환자가 살아남았는가?

* Real Estate: 이웃 지역에 비교 가능한 자산이 어느정도 가격에 팔렸는가?

 

Finding Nearest Neighbors

- n개의 점이 주어진 d차원에서 NN을 구하는 것은 O(nd)의 시간복잡도를 가진다.

- training set이 커지거나 차원이 커지면 시간이 굉장히 많이 든다.

-> grid indices, kd-trees, Voronoi diagrams, locality sensitive hashing 등을 이용

 

Voronoi Diagrams / Kd-trees

- Voronoi Diagrams: 가장 근접한 이웃을 공유하는 지역으로 공간을 분할

- kd-tree 등은 저차원에서 가장 근접한 이웃을 찾는 효율적인 알고리즘이다.

- 정확한 NN search는 충분히 고차원의 데이터에 대해서는 linear research로 축소되어야 한다.

 

Grid files

- 일정한 간격으로 나뉘어진 격자에 찍힌 점을 버켓팅 (Bucketting) 하는 것은 유사성으로 점들을 그룹화하는 방법 중 하나임

- 차원이 증가하면 index는 expensive해진다. -> 주변 격자들도 모두 탐색해야 하므로, exponential하게 증가할 수밖에 없음

왼: Voronoi Diagram / 오: Grid file

Locality Sensitive Hashing

- Hashing은 이웃하는 점이 같은 bucket으로 hash 되었을 때 NN search를 더 빠르게 진행될 수 있도록 함

* hashing: 검색을 빠르게 하기 위해 hash key 값을 가져와서 빠르게 찾도록 함

- normal hashing은 distance bucket으로 유사한 점들을 퍼뜨림

- Locality Sensitive Hashing (LSH): 점이나 벡터 a, b를 가져와서 a가 b와 인접하면 h(a)=h(b)일 것이라고 생각함.

 

LSH for points on a sphere

1) 원점을 가로지르는 랜덤 면을 선택

2) 서로 이웃해 있다면 두 점은 그 면의 같은 면에 존재할 것임. (왼쪽 또는 오른쪽)

3) d개의 랜덤 면에 대한 L/R 패턴은 d-bit LSH hash code를 생성

예시를 살펴보자! 파란 색 점에 대해서 코드를 살펴볼 것.

1번 선을 그었을 때, 해당 점은 오른쪽에 있어서 0

2번 선을 그었을 때 해당 점은 왼쪽에 있어서 1

3번 선은 오른쪽이므로 0

4번 선은 왼쪽이므로 1 --> 최종 LSH 코드는 0101

 

Network data

	vertices	edges
social network	people	friendships
WWW	pages	hyperlinks
Product/customer networks	product, customer - bipartite graph	sales
genetic networks	genes	interactions

 

Point Sets and Graphs

- Point set: graph를 정의함 -> x, y 점이 서로 이웃하면 (x, y) edge를 추가 / threshold 기준으로 거리가 가까우면 긋기

- graph: point set을 정의함 -> 인접 행렬의 SVD를 수행

ex) 2차원 SVD를 진행하여, 주성분 1/2까지 뽑아내기

 

Classical Graph Algorithms

- 두 vertices 사이의 최소 거리는 곧 그래프에서의 거리가 된다.

- 최소 거리를 찾는 클래식한 알고리즘, connected components, spanning trees, cuts, flows, matchings, topological sorting 등이 적용될 수 있음

 

PageRank

- PageRank(v, G): G에서의 random walk가 vertex v에 멈춘다는 뜻

- 반복적으로 정의됨

- 실제 상황에서는 빠르게 수렴함.

- 예) 중요한 친구가 표를 희소하게 나눠줄 때 -> 계속 업데이트가 되어 변하지 않게 됨 (수렴)

- centrality, importance 등을 측정하는 데 중요한 지표로 사용됨

- 예) 위키피디아 페이지

- PageRank에서 사용할 수 있는 의사 결정

* 관련성이 떨어져보이는 vertices/edges 편집

* outdegree가 0인 vertices 다루기

* random jump을 허가하는 문제: damping factor

 

Clustering

- 정의: 유사도를 기준으로 점을 그룹화하는 문제

- 요소들이 적은 수의 source로부터 유래한 상황에 이러한 origin을 나타내기 위해 클러스터링을 이용할 수 있다.

- ill-defined problem: 보는 사람에 따라 클러스터를 나누는 기준이 달라질 수 있음. 주관적인 부분

- 예시: 유전자 데이터 그룹화

- 클러스터링을 사용하는 이유

* hypothesis development: 내 데이터에 구별되는 데이터가 얼마나 있는가?

* Modeling over smaller groups: 각각의 클러스터에 대해 구분되는 예측 모델을 생성할 수 있음

* Data reduction: 각 클러스터의 centroid를 이용하여 클러스터를 대체/대표

* Outlier detection: 어떤 항목이 클러스터의 중심으로부터 멀리 떨어져있거나 아주 작은 클러스터에 갇혀있는가?

 

K-means Clustering

- 정의: k개의 점을 중심으로 정의 -> 모든 항목들을 가장 가까운 중심에 할당 -> 중심을 다시 계산 -> 이 과정을 계속 반복하여 충분히 안정되도록 함

- 문제점: local optima에 갇힐 위험이 있음

 

Centroids or Center Points?

- Centroid: color, gender 등 숫자로 정의되지 않은 특성에 대해 그룹화를 진행할 때는 명확하지 않다.

* 보통 이러한 데이터에서는 one-hot encoding으로 인코딩 진행

- center로 input example 중 가장 가운데에 가까운 점을 이용하는 것은 우리가 의미있는 거리 함수를 이용하기만 한다면 k-means를 이용할 수 있다는 뜻이다.

 

How Many Clusters?

- 올바른 클러스터의 개수는 클러스터링을 진행하기 전에는 알 수 없다.

- 클러스터를 더해갈 때, 점과 중심 사이의 MSE 값은 점진적으로 감소해야 한다.

- 올바른 클러스터의 개수를 초과하게 되면 MSE 값이 감소하는 속도가 느려진다.

elbow method로 최적 클러스터 개수 구하기

K-means의 한계

- nested cluster, long thin cluster에 대해서 좋지 않은 성능을 보임

- 반복적으로 클러스터링을 진행하는 것은 local optima를 피할 수 있게 함 (random seed 값을 달리 함)

 

Expectation Maximization (EM)

- EM 알고리즘의 대표적인 예시가 K-means

- E-step: 추정되는 클러스터에 점을 할당

- M-step: 할당을 이용하여 parameter 추정을 향상시킴

 

Agglomerative Clustering

- 이런 bottom up 방식은 반복적으로 2개의 근접한 클러스터를 병합시킴

 

가장 가까운 클러스터가 의미하는 것

- 보통 Average, Centroid 방식을 채택

 

Linkage Criteria

Advantages of Cluster Hierachies

- 클러스터 및 서브클러스터의 조직화

- 클러스터링 과정 시각화

- 새로운 항목의 클러스터링을 효율적으로 할 수 있음

 

어떤 클러스터링 알고리즘을 사용할까?

- 올바른 거리 함수 사용

- 올바르게 변수를 정규화

- 최종 클러스터를 시각화해서 제대로 되었는지 확인하기