Classification with Network Information

가정

- friendship 네트워크와 판매할 상품이 있음

- 네트워크상에서 일정부분에 해당하는 사람들의 구매 여부에대한 정보가 주어짐

  (아직까지 구매여부가 없는 사람들에 대해서 classification을 하는 것임)

- 링크 정보를 활용하여 잠재적 고객을 예측하는 것이 목적

1로 표시된 v1, v2는 이미 구매의사가 있는 사람

0으로 표시된 v5는 구매의사가 없는 사람

v3, v4, v6의 구매의사를 예측해보자. 

이때 위와 같이 vi노드가 구매할 확률은

N(vi) neighbor의 정보를 고려하여 결정됨

이때 사용하는 방법: wvRN

 

Weighted-vote Relational-Neighbor (wvRN)

vi의 neighbor인 vj를 고려하기위해 vj의 neighbor를 고려(회귀적인 모형임)

P(y4|N(v4)) = { P(y2=1 | N(v2)) + P(y6=1 | N(v6)) }/2 = 0.75

** P(y6=1 | N(v6)) = 0.5 (절반의 확률 그냥 가져옴)

** 초기에는 모르는 확률은 모두 0.5로 함

** 반복하는 순서의 sequence는 같게 반복해야함

 

 

Unsupervised - clustering

Clustering Goal: Group together similar items

사용하는 2가지 measure

1. distance

 - Euclidean distance(좌표상 직선거리)

 - Pearson Linear Correlation

2. similarity

distance와 similarity는 반비례 관계임

(distance가 작으면 similarity가 크다)

군집을 대표하는 것: cluster centroids

 

2가지의 군집화 알고리즘

1. Partitional algorithms

 - dataset을 몇개의 cluster로 나눈다.

 - 하나의 데이터는 한개의 그룹에만 속한다.

 - 그룹에 속하지 않은 데이터는 없다.

2. Hierarchical algorithms(범위 제외)

 

K-means

- k-means의 2가지 step:

1. assignment step

2. update step

- convergence 조건 3가지:

1. 더이상 centroids가 변경되지 않을 경우

2. clustering에 속하는 데이터들의 변동이 없을 경우

3. center가 바뀌는 값이 threshold보다 작을 경우

- 단점: 사용자가 k값을 정해줘야함

 

 

군집화 평가방법

1. Evaluation with ground truth

2. Evaluation without ground truth

 - cohesiveness: 그룹안에 데이터들이 얼마나 밀착되어있는지(그룹내 간격)

 - separateness: 그룹간에 얼마나 잘 분리되어있는지(그룹간 간격)

 

Cohesiveness: (작은게 좋음)

 

 

separateness: (큰게 좋음)

 

Silhouette index

cohesive와 separte를 하나의 값으로 표현하여 더 비교하기 쉽게 해줌

a(x): within-cluster average distance(클러스터 내의 거리)

b(x): 다른 클러스터내에 있는 점과의 거리의 평균중 최소값

 

silhouette index는 0~1사이의 값이며, 1과 가까울 수록 좋은 클러스터링임

아래 내용 꼭 직접 풀어보기

최종 silhouette index의 평균은 (0.92+0.84+0.84+0.92)/4 = 0.88임