[BoostCamp] DAY23 Graph#3

[BoostCamp] DAY23 Graph#3

---

1. 그래프를 이용한 기계학습

1. 그래프의 구조를 어떻게 분석할까?

1.1 군집 구조와 군집 탐색 문제

군집의 정의

• 군집이란 아래의 조건들을 만족하는 정점들의 집합이다.
  • 집합에 속하는 정점사이에는 많은 간선이 존재한다.
  • 집합에 속하는 정점과 그렇지 않는 정점사이에는 적은 수 의 간선이 존재한다.
  • 

실제 그래프에서의 군집들

• 온라인 소셜 네트워크의 군집들은 사회적 무리를 의미하는 경우가 많다.
  • 
• 조직 내의 분란이 소셜 네트워크 상의 군집으로 표현된 경우도 있다.
  • 
  • 대학교 가라테 동아리 내의 친구관계를 표현하였다.
  • 내분으로 동아리가 둘로 나뉘어 졌고, 그 결과 두 개의 군집에 형성되었다.
• 키워드-광고주 그래프에서는 동일한 주제의 키워드들이 군집을 형성한다.
  • 
• 뉴런간 연결그래프에서는 군집들이 뇌의 기능적 구성 단위를 의미한다.

군집 탐색 문제

• 그래프를 여러 군집으로 잘 나누는 문제를 군집 탐색 문제라고 한다.
  • 군집 탐색문제 : 정점 분석하여 각 정점이 한 군집에 속하도록 군집을 나눈다.
  • 클러스터링 : feature들이 표현된 vector를 묶는 것

1.2 군집 구조의 통계적 유의성과 군집성

비교 대상 : 배치모형

• 성공적인 군집 탐색을 정의하기 위해 먼저 배치 모형을 알아보자.
  1. 각 정점의 연결성을 보존한 상태에서
  2. 간선들을 무작위로 재배치하여 얻은 그래프를 의미한다.
     • 
     • 임의의 두 정점 i와 j사이에 간선이 존재할 확률은 두 정점의 연결성에 비례한다.

군집성의 정의

• 군집 탐색의 성공 여부를 판단하기 위해서 군집성이 사용된다.
  • 그래프와 군집들의 집합 S가 주어졌다고 하자.
  • 집합 S에 속하는 각 군집 s가 군집의 성질을 잘 만족하는 지를 살펴보기 위해
  • 군집 내부의 간선의 수를 그래프와 배치 모형에서 비교한다.
  • 군집성 :

    기댓값? 배치모형이 무작위성을 포함하기 때문이다.

  • 즉, 배치 모형과 비교했을 때, 그래프에서 군집 내부 간선의 수가 월등이 많을 수록 성공한 군집 탐색이다.
• 군집성은 무작위로 연결된 배치 모형과의 비교를 통해 통계적 유의성을 판단한다.
  • 군집성은 정규화를 통해 -1과 +1사이의 값을 갖는다.
  • 보통 군집성이 0.3 ~ 0.7정도의 값을 가질 때, 그래프에 존재하는 통계적으로 유의미한 군집들을 찾아냈다고 할 수 있다.

1.3 군집 탐색 알고리즘

Girvan-Newman 알고리즘

• Girvan-Newman 알고리즘은 대표적인 Top-Down 군집 탐색알고리즘이다.
  • Girvan-Newman 알고리즘은 전체 그래프에서 탐색을 시작한다.
  • 군집들이 서로 분리되도록 간선을 순차적으로 제거한다.
  • 어떤 간선을 제거해야 군집들이 분리 될까?
    • 서로 다른 군집을 연결하는 다리 역할의 간선을 삭제하자.
• 더로 다른 군집을 연결하는 다리 역할역할을 하는 간선을 어떻게 찾아낼 수 있을까?
  • 간선의 매개 중심성을 사용한다.
  • 이는 해당 간선이 정점 간의 최단 경로에 높이는 횟수를 의미한다.
    • 
  • 즉, 매개 중심성을 통해 서로 다른 군집을 연결하는 다리 역할의 간선을 찾아낼 수 있다.
  • 매개 중심성이 높은 간선들이 서로 다른 군집을 연결하는 다리 역할을 하는 것이라 생각할 수 있다.
• Girvan-Newman 알고리즘은 매개 중심성이 높은 간선을 순차적으로 제거한다.
  • 간선이 제거될 때마다, 매개 중심성을 다시 계산하여 갱신한다.
  • 모든 간선이 제거될 때까지 반복한다.
• 간선의 제거 정도에 따라서 다른 입도의 군집구조를 나타낸다.
  • 
• 간선을 어느 정도 제거하는 것이 가장 적합할까?
  • 군집성을 기준으로 삼는다. 즉, 군집성이 최대가 되는 지점까지 간선을 제거한다.
  • 단, 현재의 연결 요소들은 군집으로 가정하되, 입력 그래프에서 군집성을 계산한다.

Girvan-Newman 알고리즘 과정 정리

1. 전체 그래프에서 시작한다.
2. 매개 중심성이 높은 순서로 간선을 제거하면서 군집성의 변화를 기록한다.
3. 군집성이 가장 커지는 상황을 복원한다.
4. 이때, 서로 연결된 정점들, 즉 연결 요소를 하나의 군집으로 간주한다.

즉, Girvan-Newman 알고리즘은 전체 그래프에서 시작해서 점점 작은 단위를 검색하는 Top-Down 방법이다.

Louvain 알고리즘

• Louvain 알고리즘은 대표적인 Bottom-Up 군집 탐색 알고리즘이다.
  • 개별 정점에서 시작해서 점점 큰 군집을 형성한다.
  • 어떤 기준으로 군집을 형상할까? 군집성을 이용해서 군집을 형성하자.
• 알고리즘의 동작과정을 알아보자.
  1. 개별 정점으로 구성된 크기 1인 군집들로부터 시작한다.
  2. 각 정점 u를 기존 혹은 새로운 군집으로 이동한다. 이때, 군집성이 최대화되도록 군집을 결정한다.
  3. 더이상 군집성이 증가하지 않을 때까지 2를 반복한다.
  4. 각 군집을 하나의 정점으로 하는 군집 레벨의 그래프를 얻은 뒤 3을 수행한다.
  5. 한개의 정점이 남을 때까지 4를 반복한다.
• 소셜 네트워크의 군집을 탐색한 결과를 확인 해보자.
  • 

1.4 중첩이 있는 군집 탐색

중첩이 있는 군집 구조

• 실제 그래프의 군집들을 중첩되어 있는 경우가 많다.
• 앞서 소개한 두개의 알고리즘, Girvan-Newman 알고리즘, Louvain 알고리즘은 군집간 중첩이 없다고 가정한다.
• 그렇다면 중첩이 있는 군집은 어떻게 찾아낼 수 있을 까?

중첩 군집 모형

• 아래와 같은 중첩 군집 모형을 가정해보자.
  1. 각 정점은 여러 개의 군집에 속할 수 있다.
  2. 각 군집 A에 대하여 같은 군집에 속하는 두정점은 PA의 확률로 간선으로 직접 연결된다.
  3. 다 정점이 여러 군집에 동시에 속할 경우 간선 연결 확률은 독립적이다.
     • 두 정점이 군집 A와 B에 동시에 속할 경우, 두 정점이 간선으로 직접 연결될 확률은 1 - (1 - PA)(1 - PB)이다.
  4. 어느 군집에도 함께 속하지 않는 두 정점은 낮은 확률 ε으로 직접 연결된다.
• 중첨 군집 모형이 주어지면 , 즉 어떤 정점이 어떤 군집에 속하며, 그 군집에 속하는 정점들은 어떤 확률로 연결되어 있는 지 알고 있으면,
• 그래프의 확률을 계산할 수 있다.

• 

• 중첩 군집 탐색은 주어진 그래프의 확률을 최대화하는 중첩 군집 모형을 찾는 과정이다.
• 통계 용어로는 최우도 추정치를 찾는 과정이다.

완화된 중첩 군집 모형

• 중첩 군집 탐색을 용이하게 하기 위해 완화된 중첩 군집 모형을 사용한다.
  • 완화된 중첩 군집 모형에서는 각 정점이 각 준집에 속해 있는 정도를 실숫값으로 표현한다.
  • 즉, 기존 모형에서는 각 정점이 각 군집에 속하거나 속하지 않거나 둘 중 하나였는데 중간 상태를 표현할 수 있게 된 것이다.
  • 
  • 최적화 관점에서는 모형의 매개 변수들이 실수 값을 가지기 때문에, 익숙한 최적화 도구(경사하강법 등)을 사용하여 모형을 탐색할 수 있다는 장점이 있다.

2. 그래프를 추천시스템에 어떻게 활용할까?(Basic)

2.1 우리 주변의 추천 시스템

아마존에서의 상품 추천

• Amason.com 메인페이지에는 고객 맞춤형 상품 목록을 보여준다.
• 특정 상품을 볼 때, 함께 혹은 대신 구매할 상품을 보여준다.

넷플릭스에서의 영화 추천

• 넷플리스 메인 페이지에는 고객 맞춤형 영화 목록을 보여준다.

유튜브에서의 영상 추천

• 유튜브 메인 페이지에는 고객 맞춤형 영상 목록을 보여준다.
• 유뷰브는 현재 재생 중인 영상화 관련된 영상 목록을 보여준다.

페이스북에서의 친구 추천

• 페이스 북에서는 추천하는 친구의 목록을 보여준다.

추천 시스템과 그래프

• 추천 시스템은 사용자 각각이 구매할 만한 혹은 선호할 만한 상품을 추천한다.
  • 사용자별 구매 기록은 그래프로 표현 가능하다.
  • 구매 기록이라는 암시적인 선호만 있는 경우도 있고
  • 평점이라는 명시적인 선호가 있는 경우도 있다.
  • 추천 시스템의 핵심은 사용자별 구매를 예측하거나 선호를 추정하는 것이다.
  • 그래프 관점에서 추천 시스템은 미래의 간선을 예측하는 문제 혹은 누락된 간선의 가중치를 추정하는 문제로 해석할 수 있다.
  • 

2.2 내용 기반 추천 시스템

내용기반 추천 시스템의 원리

• 내용기반 추천은 각 사용자가 구매/만족했던 상품과 유사한 것을 추천하는 방법
  • 예
    • 동일한 장르의 영화를 추천하는 것
    • 동일한 감독의 영화 혹은 동일 배우가 출현한 영화를 추천하는 것
    • 동일한 카테고리의 상품을 추천하는 것
• 내용 기반 추천의 과정을 확인해보자.
  • 내용 기반 추천은 아래의 네 단계로 이루어진다.
    1. 사용자가 선호했던 상품들의 상품 프로필을 수집한다.
       • 어떤 상품의 프로필이란 해당 상품의 특성을 나열한 벡터이다.
       • 영화를 예로 하자면, 감독, 장르, 배우 등의 원핫 인토딩이 상품 프로필이 될 수 있다.
    2. 사용자 프로필을 구성한다.
       • 사용자 프로필은 선호한 상품의 상품 프로필을 선호도를 사용하여 가중 평균하여 계산한다.
       • 즉, 사용자 프로필 역시 벡터이다.
       • 영화를 예로 보자면 각 장르에 대한 선호도 등이 될 수 있다.
    3. 사용자 프로필과 다른 상품들의 상품 프로필을 매칭한다.
       • 사용자 프로필 벡터 u와 상품 프로필 벡터 v의 코사인 유사도를 계산한다.
       • 즉 두 벡터의 사이각의 코사인 값을 계산한다.
    4. 사용자에게 상품을 추천한다.
       • 계산한 코사인 유사도가 높은 상품을 추천한다.
         *

[TODO] 유사도 종류

내용기반 추천 시스템의 장단점

• 장점
  • 다른 사용자의 구매 기록이 필요하지 않는다.
  • 독특한 취향의 사용자에게도 추천이 가능하다.
  • 새 상품에 대해서도 추천이 가능하다.
  • 추천의 이유를 제공할 수 있다.
• 단점
  • 상품에 대한 부가 정보가 없는 경우에는 사용할 수 없다.
  • 구매 기록이 없는 사용자에게는 사용할 수 없다.
  • 과적합으로 인해 지나치게 형소한 추천을 할 위험이 있다.

2.3 협업 필터링

협업 필터링의 원리

• 사용자-사용자 협업 필터링의 과정을 알아보자.
  1. 추천 대상 사용자를 x라고 하자.
  2. 우선 x와 유사한 취향의 사용자들을 찾는다.
  3. 유사한 취향의 사용자들이 선호한 상품을 찾는다.
  4. 해당 상품들을 x에게 추천한다.
• 사용자-사용자 협업 필터링의 핵심은 유사한 취향의 사용자를 찾는 것이다.
• 취향의 유사성은 상관 계수를 통해 측정한다.
  • 
• 구체적으로 취향의 유사도를 가중치로 사용한 평점의 가중 평균을 통해 평점을 추정한다.
  • 
• 추정한 평점이 가장 높은 상품을 추천해보자.
  • 추천의 대상 사용자를 x라고 하자.
  • 앞선 방법을 통해 x가 아직 구매하지 않은 상품 각각에 대해 평점을 추정한다.
  • 추정한 평점이 가장 높은 상품들을 x에게 추천한다.

협업 필터링의 장단점

• 장점
  • 상품에 대한 부가 정보가 없는 경우에도 사용할 수 있다.
• 단점
  • 충분한 수의 평점 데이터가 누적되어야 효과적이다.
  • 새 상품, 새로운 사용자에 대한 추천이 불가능하다.
  • 독특한 취향의 사용자에게 추천이 어렵다.

2.4 추천 시스템의 평가

데이터 분리

• 추천 시스템의 정확도는 어떻게 평가할까?
  1. 먼저 데이터를 training data와 test data로 분리한다.
  2. 평가 데이터는 주어지지 않았다고 가정한다.
  3. 훈련 데이터를 이용해서 가려진 평가 데이터의 평점을 추정한다.
  4. 추정한 평점과 실제 평가 데이터를 비요하여 오차를 측정한다.

평가 지표

• 추정한 평점과 실제 평가 데이터를 비교하여 오차를 측정한다.
  • 오차를 측정하는 지표로는 평균 제곱 오차가 많이 사용된다.
  • 평가 데이터 내의 평점들의 집합을 T라고 하자.
  • 평균 제곱 오차는 아래 수식으로 계산한다.
  • 

    이외에도 평균 제곱근 오차도 많이 사용된다.
    평균제곱 오차에 제곱근 연산을 하면 된다.

• 이 밖에도 다양한 지표가 사용된다.
  • 추정한 평점으로 순위를 매긴 후, 실제 평점으로 매긴 순위와의 상관 계수를 계산하기도 한다.
  • 추천한 상품 중 실제 구매로 이루어진 것의 비율을 측정하기도 한다.
  • 추천 순서 혹은 다양성까지 고려하는 지표들도 사용된다.