Peer Session Badge

그래프 구조 분석

  • 군집 구조와 탐색

    • 군집(community)
      • 집합에 속하는 정점 사이에는 많은 간선 존재
      • 집합에 속하는 정점과 그렇지 않은 정점 사이에는 적은 수의 간선 존재
    • 군집 탐색(detection) 문제
      • 클러스터링(feature들이 벡터형태로 표현된 instance들을 그룹화)과 유사
      • 정점들을 그룹화하여 그래프를 여러 군집으로 잘 나누는 문제
    • 통계적 유의성과 군집성
      • 배치 모형(configuration model)
        • 각 정점의 연결성을 보존한 상태에서, 간선들을 무작위로 재배치하여 얻은 그래프
        • 임의의 두 정점 $i$ $j$ 사이에 간선이 존재할 확률은 두 정점의 연결성에 비례
      • 군집성(modularity)
        • 그래프와 군집들의 집합 $S$ 주어짐

        • 각 군집 $s \in S$가 군집의 성질을 잘 만족하는지 살펴보기 위해, 군집 내부 간선의 수를 그래프와 배치 모형에서 비교

          $\frac{1}{2 \vert E \vert} \sum_{s \in S} (\text{N in graph - E in batch})$

          $N$: 군집 $s$ 내부 간선의 수

          $E$: 군집 $s$ 내부 간선의 수의 기댓값

        • 배치 모형과 비교했을 때, 그래프에서 군집 내부 간선의 수가 월등히 많을 수록 성공한 군집 탐색
        • -1 ~ 1 사이 값 가짐
        • 보통 0.3 ~ 0.7 정도에서 통계적으로 유의미한 군집 찾았다고 할 수 있음
    • 탐색 알고리즘
      • Girvan-Newman
        • Top-Down
        • 전체 그래프에서 시작, 군집들이 서로 분리되도록 간선들을 순차적으로 제거
        • 서로 다른 군집을 연결하는 다리(bridge) 역할의 간선을 제거

        • 간선의 매개 중심성(betweenness centrality), 즉 정점 간 최단 경로에 놓이는 횟수를 사용해 다리 역할 간선 찾음

          매개 중심성: $\sum_{i < j} \frac{\sigma_{i,j}(x,y)}{\sigma_{i,j}}$

          $\sigma_{i,j}:$ 정점 $i$로부터 $j$로의 최단 경로 수

          $\sigma_{i,j}(x,y)$: 그 중 간선 $(x,y)$를 포함한 것

        • 간선의 제거 정도에 따라 다른 입도(granularity)의 군집 구조가 나타남
        • 군집성이 최대가 되는 지점까지 간선을 제거
      • Louvain
        • Bottom-up
        • 크기 1의 군집인 개별 정점에서 시작해 점점 큰 군집 형성
    • 중첩 군집 모형
      • 각 정점은 여러 개의 군집에 속할 수 있음
      • 중첩 군집 탐색
        • 주어진 그래프의 확률을 최대화하는 중첩 군집 모형을 찾는 과정
        • 최우도 추정치(maximum likelihood estimate)를 찾는 과정

추천시스템

  • 추천시스템 실제 사례

    • 아마존
      • 고객 맞춤형 상품 목록
      • 특정 상품 페이지에서, 함께 혹은 대신 구매할 상품 목록
    • 넷플릭스
      • 고객 맞춤형 영화 목록
    • 유튜브
      • 고객 맞춤형 영상 목록
      • 재생 중인 영상과 관련된 영상 목록
    • 페이스북
      • 추천 친구 목록

  • 그래프와 추천시스템

    • 사용자별 구매 기록을 그래프로 표현 가능
      • 구매 기록: 암시적(implicit)인 선호
      • 평점: 명시적(explicit)인 선호
    • Tasks
      • 사용자별 구매를 예측
      • 사용자의 선호를 추정

  • 내용 기반(content-based) 추천시스템

    • 구매/만족했던 상품과 유사한 것 추천
    • 장르, 카테고리 등 부가 정보 활용
    • 순서
      1. 사용자가 선호한 상품들의 상품 프로필(item profile, 해당 상품의 특성 벡터) 수집
      2. 사용자 프로필(user profile, 상품 프로필을 선호도로 가중평균한 벡터) 구성

      3. 사용자 프로필과 다른 상품들의 상품 프로필을 매칭

        사용자 프로필 벡터 $\overrightarrow{u}$와 상품 프로필 벡터 $\overrightarrow{v}$의 코사인 유사도 $\frac{\overrightarrow{u} \cdot{} \overrightarrow{v}}{\Vert \overrightarrow{u} \Vert \Vert \overrightarrow{v} \Vert}$ 계산

      4. 코사인 유사도가 높은 상품들을 추천
    • 장점
      • 다른 사용자 구매 기록 필요 x
      • 독특한 취향의 사용자에게도 추천 가능
      • 새 상품에 대해 추천 가능
      • 추천의 이유 제공 가능
    • 단점
      • 부가 정보가 없는 경우 불가능
      • 구매 기록이 없는 사용자에게 사용 불가능
      • overfitting으로 지나치게 협소한 추천 위험 있음

  • 협업 필터링

    • 순서
      1. 추천의 대상 사용자 $x$와 유사한 취향의 사용자를 찾기
      2. 유사한 취향의 사용자들이 선호한 상품 찾기
      3. 해당 상품을 $x$에게 추천
    • 취향의 유사도 계산

      • 상관계수(correlation coefficient)를 통해 측정

        $sim(x,y) = \frac{\sum_{s \in S_{xy}} (r_{xs} - \bar{r_x})(r_{ys} - \bar{r_y})}{\sqrt{\sum_{s \in S_{xy}} (r_{xs} - \bar{r_x})^2} \sqrt{\sum_{s \in S_{xy}} (r_{ys} - \bar{r_y})^2}}$

        $r_{xs}$: 사용자 $x$의 상품 $s$에 대한 평점

        $\bar{r_x}$: $x$가 매긴 평균 평점

        $S_{xy}$: $x$와 $y$가 공동 구매한 상품들

    • 취향의 유사도를 가중치로 사용한 평점의 가중 평균 $\rightarrow$ 평점을 추정

      $\hat{r_{xs}} = \frac{\sum_{y \in N(x;s)} sim(x,y) r_{ys}}{\sum_{y \in N(x;s)} sim(x,y)}$

    • 장점
      • 상품에 대한 부가 정보가 없는 경우도 사용 가능
    • 단점
      • 충분한 수의 평점 데이터 누적 필요
      • 새 상품, 새 사용자에 대한 추천 불가
      • 독특한 취향의 사용자에게 추천 어려움

  • 추천시스템 평가

    • 데이터 분리: 훈련/평가
    • 평가 지표

      • MSE

        $\frac{1}{\vert T \vert} \sum_{r_{xi} \in T} (r_{xi} - \hat{r_{xi}})^2$

        $T$: 평가 데이터 내의 평점들의 집합

      • RMSE

        $\sqrt{MSE}$

      • 추정 평점 순위와 실제 평점 순위와의 상관계수
      • 추천 상품 중 실제 구매로 이루어진 비율
      • 추천의 순서, 다양성까지 고려하는 지표