강의 복습 내용

  • 그래프 군집 구조와 군집탐색
    • 군집 탐색 알고리즘
      • Girvan-Newman
        • 하향식
      • Louvain
        • 상향식
    • 중첩이 있는 군집 탐색
      • 완화된 중첩 군집 모형
    • 군집참고
  • 추천시스템
    • 내용기반 추천 시스템
      • 새로운 상품에 대한 추천
      • 상품에 대한 부가정보 있을때 가능
    • 협업 필터링
      • 부가정보가 없어도 가능
      • 새로운 상품 추천 불가
    • 추천 시스템 평가
      • MSE

얻은 지식

군집

  • 집합에 속하는 정점 사에는 많은 간선이 존재
  • 집합에 속하는 정점과 아닌 정점사이네는 적은 간선이 존재
    • 수학적인 정의가 아님

군집 예시

  • SNS의 사회적 무리(social circle)를 의미하는 경우가 많다.
    • 동창, 회사
  • 조직내의 분란
  • 키워드-광고주 그래프에서 동일한 키워드 들이 군집을 형성
  • 뉴런간 연결그래프
    • 뇌의 기능적 구성단위

군집 탐색 문제(community detection)

  • 그래프를 여러 군집을 잘 나누는 문제
  • 비교를 통해서 정의된다.
    • 비교 대상이 배치 모형(configuration model)이다.

배치 모형

  • 그림
    • 각 정점의 연결성(degree)을 보존
    • 간선들을 무작위로 재배치하여 얻은 그래프

군집성(Modularity)

  • 군집탐색의 성공 여부를 판단하기 위해 사용
  • 그래프, 탐색한 군집들의 집합S
  • 군집 \(s \in S\)가 군집의 성질을 잘 만족하는지 확인해야 한다.
    • 군집 내부의 간선수를 그래프와 배치 모형에서 비교

\(\frac{1}{2\mid E\mid}\Sigma_{s\in S}(그래프의 군집s내부 간선의 수- 배치모형의 군집s 내부 간선수의 기댓값)\)

  • 배치모형의 군집s 내부 간선수의 기댓값
    • 그래프를 통해 만들어진 여러개의 배치모형에대해
    • 해당 군집s내부 간선수들을 계산하여 평균한거
    • (생각)왜냐면 여러 연결요소가 잇을수 있고 단순 랜덤하게 만들기때문에 군집이 아닌게 섞이거나 할 수 있으니까?
  • 기댓값은 배치모형이 무작위성이므로
  • 차이가 크다는것은 그래프의 군집s 내부간선의 수가 많음을 의미
    • 군집s가 군집의 성질을 만족함
    • 차이가 클수록 좋다.
  • 정규화를 통해 -1부터1사이의 값을 갖도록 한다.
  • 배치 모형과 비교 했을때, 그래프에서 군집 내부 간선수가 많을수록 성공한 군집탐색
  • 군집성이 0.3~0.7정도의 값을 가질때, 유의미한 군집이라 할 수 있다.

군집탐색 알고리즘

  • Girvan-Newman알고리즘
  • Luvain알고리즘

Girvan-Newman 알고리즘

  • 하향식(top-down)군집 탐색알고리즘
    • 전체 그래프에서 탐색을 시작
    • 군집들이 서로 분리되도록 간선을 순차적으로 제거
      • 다리 역할을 하는 간선을 제거
  • 다리 역할 간선을 찾기
    • 매개중심성(betweenness centrality)을 사용
    • 정점간의 최단 경로에 놓이는 횟수
    • 그림
      • 중간의 간선은 왼쪽과 오른쪽의 최단경로를 위해 경유하는 간선이다.
      • 좌우의 정점간의 최단경로의 수는 4x4하여 16개가 된다.
    • \[\Sigma_{i<j}\frac{\sigam_{i,j}(x,y)}{\sigma_{i.j}}\]
      • 매개 중심성을 구하는 수식
      • i부터 j로의 최단 경로수를 \(\sigma_{i,j}\)
      • 간선(x,y)를 포함한것은\(\sigma_{i,j}(x,y)\)
  • 간선의 제거 정도에 따라 다른 입도(granularity)의 군집구조가 나타난다.
    • 그림
    • 간선을 하나 제거할때 2개의군집, 4개를 제거하니 4개의 군집이 나온다.
    • 언제까지 간선을 제거하냐면, 군집성이 제일 클때까지
  • 알고리즘 방식
    • 1) 매개 중심성이 높은 간선을 순차적으로 제거
      • 간선이 삭제될때마다 다시 계산
    • 2) 군집성 계산
    • 3) 군집성이 가장 커지는 상황을 확인
    • 4) 군집성이 가장 클때의 연결요소들을 군집으로 정한다.

Louvain 알고리즘

  • 상향식(bottom-up)군집 탐색 알고리즘
    • 개별 정점에서 시작해서 점점 큰 군집을 형성
    • 군집성을 기준으로 군집 만들기
  • 그림
    • 하나의 pass를 통해 같은색의 군집들을 하나의 정점으로 만들어서 그래프를 만든다.
    • 이게 군집레벨의 그래프.
  • 알고리즘 방식
    • 1) 개별 정정으로 구성된 크기1의 군집에서 시작
    • 2) 각 정점 u를 기존,새로운 군집으로 이동
      • 군집성이 최대화 되도록 군집 구성
    • 3) 군집성이 증가하지 않을때까지 2)반복
    • 4) 군집을 하나의 정점으로 표현 하는 군집레벨의 그래프를 구함 이후 3)을 수행
    • 5) 한개의 정점이 남을때까지 4) 반복

중첩이 있는 군집 구조

  • 실제 그래프의 군집들은 중첩되어있는 경우가 많다.
  • 앞의 그래프 탐색 알고리즘은 중첩이 없다고 가정한다.
    • 중첩이 있을대 군집찾기

중첩 군집 모형

그림

  • 각 정점은 여러 군집에 속할 수 있다.
  • \[P_A\]
    • A라는 같은 군집에 속하는 두 정점이 간선으로 연결될 확률
  • \[1-(1-P_A)(1-P_B)\]
    • 여러 군집에 동시에 속할 경우, 간선이 연결될 확률은 독립적(곱셈)
    • 두 정점이 A와 B에 속할경우, 두 정점이 간선으로 직접 연결될 확률
  • \[\epsilon\]
    • 어느 군집에도 속하지 않고, 두정점이 연결될 확률
    • 매우 작다.

중접 군집 모형을 이용한 그래프 확률계산

  • 그림
  • 1)그래프의 각 간선의 두 정점이 직접 연결될 확률
  • 2)그래프에서 직접연결되지 않은 각 정점 쌍이 직접 연결되지 않을 확률
  • 이 두개의 확률의 곱

중첩군집 탐색

  • 중첩 군집 탐색은 그래프의 확률을 최대화 하는 중첩 군집 모형을 찾아내는것
  • 현실에서는 그래프는 주어지지만, 중첩 군집 모형은 주어지지 않는다.
    • 중첩그래프 -> 중첩군집 모형
    • 최우도 추정치(MLE maximum likelihood estimate)를 찾는 과정
    • 이산적인 값으로 되어있어서 구하기 어렵다.
    • 각 정점이 군집에 속하거나, 속하지 않거나 둘중 하나로 표현된다.

완화된 중집 군집 모형

  • 중첩 군집 탐색을 용이하게 하기위해 사용
  • 각 정점이 각 군집에 속해 있는 정도를 실숫값으로 표현

그림

  • 각 정점이 각 군집에 속해 있는 정도를 실숫값으로 표현
    • 선의 두깨로 군집에 속한 정도를 표현
  • 중간상태를 표현하게됨
  • 현실적인 모형으로 사람들도 여러 집단중 일부 소속에 소속감을 느끼고 더 참여하는부분을 표현할 수 있다.
  • 최적화 관점에서 경사 하강법을 사용하여 모형을 탐색

그래프 추천 시스템

추천시스템 예시

  • 아마존 상품추천
  • 넷플릭스 영화목록
  • 유튜브 영상추천
  • 페이스북 친구 추천
  • 사용자가 각 구매할 만한, 선호할 만한 상품을 추천
    • 암시적인 선호(구매기록)
    • 명시적인 선호(평점)
  • 그래프 관점의 추천 시스템
    • 미래의 간선을 예측하는 문제
    • 누락된 간선의 가중치를 추정하는 문제

내용 기반 추천 시스템

  • 내용 기반(content-based)추천
    • 각 사용자가 구매/만족했던 상품과 유사한 것을 추천
  • 내용 기반 추천 단계

그림

  • 1) 선호했던 상품들의 상품 프로필을 수집
    • 해당 상품의 특성을 나열한 벡터
    • one-hot 인코딩으로 상품프로필을 만든다.
  • 2) 사용자 프로필(user profile) 구성
    • 선호한 상풍 프로필들을 선호도를 사용하여 가중편균하여 계산
    • 사용자가 선호하는 상품들의 특성이 집약된 벡터
  • 3) 사용자 프로필과 다른 상품 프로필을 매칭
    • 사용자 프로필벡터 u와 상품 프로필 벡터 v 코사인 유도를 계산
      • \[\]
  • 4) 사용자에게 상품을 추천
    • 코사인 유사도가 높은 상품들을 추천

장단점

  • 장점
    • 다른 사용자의 구매기록이 필요없다.
    • 독특한 취향의 사용자에게도 추천
    • 새 상품에대해서도 추천
    • 추천의 이유를 제공
  • 단점
    • 상품에 부가 정보가 없는 경우 사용 부락
    • 구매기록이 없는 사용자는 불가
    • 과적합(overfittign)으로 지나치게 협소한 추천
      • 우연히 로맨스를 봤다고 로맨스를 계속 추천하게 된다.
      • 추천이 너무 치우칠수있다.

협업 필터링

  • 사용자-사용자 협업필터링
    • 추천의 대상 사용자를 x라고 한다.
    • 1) x와 유사한 취향의 사용자 찾기
    • 2) 유사한 취향의 사용자들이 선호한 상품 찾기
    • 3) 이 상품들을 x에게 추천
  • 유사한 취향의 사용자를 찾기
    • 취향의 유사도 계산

취향의 유사도

| | 반지의 제왕 | 겨울왕국 | 라푼젤 | 해리포터 | 미녀와 야수 | | —- | ———– | ——– | —— | ——– | ———– | | 지수 | 4 | 1 | 2 | 5 | ? | | 제니 | 5 | 1 | ? | 4 | 2 | | 로제 | 2 | 5 | 5 | ? | 4 |

  • 지수와 제니는 취향 유사
  • 제니와 로제는 취향이 다르다는것이 보인다.
  • 상관 계수를 통해 수치적으로 계산

상관 계수(correlation coefficient)

  • \[r_{xs}\]
    • x가 s에 매긴 평점
  • \[\bar{r_x}\]
    • x가 매긴 평균 평점
  • \[S_{xy}\]
    • x와 y가 공동 구매한 상품
  • 취향의 유사도 계산식
\[sim(x,y) = \frac{\Sigma_{s \in S_{x,y}{(r_{xs}-\bar{r_x})(r_{ys} - \bar{r_y})}}}{\sqrt{\Sigma_{s \in S_{x,y}{(r_{xs}-\bar{r_x})^2}}}\sqrt{\Sigma_{s \in S_{x,y}{(r_{ys} - \bar{r_y})^2}}}}\]
  • 모든 공동 구매한 상품 S들을 확인
    • x의 평점\((r_{xs}-\bar{r_x})\)
    • y의 평점\((r_{ys} - \bar{r_y})\)
    • x과 y가 매긴 평점을 확인
      • x의 평점 곱하기 y의 평점이된다.
      • 서로 평가가 같으면 +, 서로 평점이 다르면 - 가된다.
    • 이 결과들을 더한값을사용
  • 평준화 하여 결과를 출력

새로운 물건에 대한 평점을 추정하기

  • 취향의 유사도를 가중치로 사용한 평점의 가중평균을 사용하여 평점을 추정한다.
  • \(r_{xs}\)를 추정하는 경우
    • 사용자x가 물건s에 대한 평점
  • N(x;s)
    • 물건s를 구매한 사용자중, 사용자x와 상관계수가 높은(취향이 가장유사한) k명의 사용자
\[\hat{r_{xy}} = \frac{\Sigma_{y\in N(x;s)}{sim(x,y)\cdot r_{ys}}}{\Sigma_{y\in N(x;s)}{sim(x,y)}}\]
  • \(\hat{r_{xy}}\)은 \(r_{xy}\)의 추정

추정한 평점이 가장 높은 상품을 추천

  • x가 아직 구매하지 않은 상품에 대해 평점을 추정
  • 추정한 평점이 가장 높은 상품들을 추천

장단점

  • 장점
    • 상품에 부가정보가 없어도 사용
  • 단점
    • 충분한 수의 데이터가 필요
    • 새상품, 새로운 사용자에게 추천이 불가
    • 독특한 취향의 사용자에게 추천이 어려움

      • 비슷한 취향의 사용자가 없음

추천시스템 평가

그림

  • 데이터를 분리
    • 훈련(파란영역)
    • 평가(빨간부분)
      • 평가데이터부분은 지운다.
      • 빨간 영역에 대해 실제 추천을 진행
  • 측정
    • 가려진 평가데이터와 실제 평가데이터를 비교

평가 지표

  • 추정한 평점과 실제 평가 데이터를 비교하여 오차 측정
    • 평균제곱오차(Mean Squared Error,MSE)를 많이 사용
      • \[\frac{1}{\mid T\mid}\Sigma_{r_{xi}\in T}{(r_{xi}-\hat{r_{xi}})^2}\]
      • 모든 평가데이터 T에 대해 (실제값-예측값)을 제곱한 값을 평균
    • 평균 제곱근 오차(RMSE)도 사용

실습

Girvan-Newman 알고리즘 구현

  • girvan_newman(G)
  • greedy_modularity_communities(G)
  • kernighan_lin_bisection(G)
    • 그래프를 두개의 군집으로만 분류

      협업필터링 구현

  • 코드확인

좀더 찾아보기

  • 군집성
  • 군집레벨 그래프

피어세션 정리