Contents

  1. 군집 탐색
    1. 군집 구조와 군집 탐색 문제
      1. 군집의 정의
      2. 군집 탐색
    2. 군집 구조의 통계적 유의성과 군집성
      1. Configuration Model(배치모형)
    3. 군집 탐색 알고리즘
      1. Girvan-Newman 알고리즘
      2. Louvain 알고리즘
    4. 중첩이 있는 군집 탐색
      1. 중첩 군집 모형
  2. 추천시스템 Basic
    1. 내용 기반 추천시스템의 원리
      1. 내용기반 추천의 단계
    2. 협업 필터링 추천시스템
      1. Collaborative Filtering
    3. 추천시스템의 평가

이번 강의에서는 그래프에서의 군집(Community)이 무엇인지 배우고, 군집에 대한 해석, 그래프에서 군집을 탐색하는 법에 대해 배웁니다. 실제 세상에서 우리는 주변에서 여러가지 종류의 군집을 볼 수 있습니다. 인간 관계 사이에서 (ex. 동아리, 동창회), 화학 물질 내부에서 등 어디서나 군집을 발견할 수 있습니다. 그렇다면, 우리는 그래프 데이터에서 군집을 어떻게 정의하고, 어떻게 찾아낼까요? 이번 장을 통해서 그래프 데이터에서 군집을 찾아내는 알고리즘을 배워보고, 실제로 적용까지 해보겠습니다!

넷플릭스와 유투브의 컨텐츠 추천, 아마존의 상품 추천 등 우리는 일상생활 속 다양한 곳에서 추천 시스템을 사용하고 있습니다. 이번 강의에서는 다양한 형태의 추천시스템 중 아이템의 내용을 사용해 추천해주는 ‘내용 기반 추천(contents based recommendation’)과, 유저와 아이템간의 유사도를 통해 추천을 해주는 ‘협업 필터링(collaborative filtering)’에 대해 공부해봅니다. 각 알고리즘의 장단점에 집중하면서 강의를 들어봅시다!

군집 탐색

군집 구조와 군집 탐색 문제

먼저 군집의 구조와 예시를 통해 군집을 이해하고, 군집 탐색 문제를 정의하도록 한다.


군집의 정의

Community(군집)이란 다음의 조건들을 만족하는 정점을 의미한다.

  1. 집합에 속하는 정점 사이에 많은 간선이 존재한다.
  2. 집합에 속하는 정점과 그렇지 않은 정점 사이에는 적은 수의 간선이 존재한다.

‘많은’과 ‘적은 수’와 같은 단어는 수학적으로 정의하기 애매하며, 위 정의는 엄밀하지 않다. 하지만, 아래 그림과 같이 눈으로 봐도 비교적으로 군집이 분류됨을 확인할 수 있다.

image

실생활 속에서의 군집은 다양한 형태로 나타나고 있다.

  • 조직 내 분란이 소셜 네트워크 상의 군집으로 표현됨
  • 온라인 상에서의 군집은 사회적 무리를 의미함
  • 부정행위와 관련된 경우가 많음
  • 키워드 군집 - 광고에 활용
  • 뉴런간의 연결 그래프 - 뇌의 기능적 구성단위를 의미


군집 탐색

이처럼 그래프를 여러 군집으로 “잘” 나누는 문제를 군집 탐색(Community Detection) 문제라고 한다.

  • 보통은 각 정점이 한개의 군집에 빠짐없이 속하도록 군집을 나눈다.
  • 비지도 기계학습 문제인 클러스터링(Clustering)과 상당히 유사하다
    • 차이점은 클러스터링의 경우 해당 정점 혹은 인스턴스들이 사영되는 vector를 분류하는 것이 clustering이고, 정점 자체를 분류하는 것이 군집 탐색(Community detection)이다.


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

Configuration Model(배치모형)

주어진 그래프에 대하여 배치모형은 다음과 같은 그래프를 의미한다.

  • 각 정점의 연결성을 보존한 상태에서
  • 간선들을 무작위로 재배치하여 얻은 그래프

image

배치 모형에서 임의의 두 정점 $i$와 $j$ 사이에 간선이 존재할 확률은 두 정점의 연결성에 비례한다. 군집 탐색의 성공 여부를 판단하기 위해 군집성(Modularity)를 사용한다.

  • 그래프와 군집들의 집합 $S$가 주어졌을때, 각 군집 $s\in S$가 군집의 성질을 잘 만족하는 지를 살펴보기 위해, 군집 내부의 간선 수를 그래프와 배치모형에서 비교한다.
  • 군집성 : $\frac{1}{2\vert E\vert}\sum_{s\in S}$(그래프에서 군집 s의 내부 간선 수 - 배치모형에서 군집s 내부 간선 수의 기댓값)
  • 즉, 배치모형과 비교했을 때, 그래프에서 군집 내부 간선의 수가 월등히 많을 수록 성공한 군집탐색이다.

즉, Modularity는 무작위로 연결된 배치 모형과의 비교를 통해 통계적 유의성을 판단한다.

  • 항상 -1과 +1 사이의 값을 갖는다.
  • 일반적으로, 군집성 0.3~0.7 정도의 값을 가질 때, 그래프에 존재하는 통계적으로 유의미한 군집들을 찾았다고 할 수 있다.


군집 탐색 알고리즘

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


Girvan-Newman 알고리즘

  • 대표적인 top-down 군집 탐색 알고리즘이다.
  • 전체 그래프에서 탐색을 시작하여, 군집들이 서로 분리되도록, 간선들을 순차적으로 제거한다.
    • 어떤 Edge를 제거해야 군집들이 분리될까?

    • 바로 서로 다른 군집간 연결을 해주는 Bridge(다리)역할의 간선이다.

      image

  • 그렇다면 서로 다른 군집을 잇는 다리 역할의 간선은 어떻게 찾을까?
    • 간선의 매개 중심성(Betweenness Centrality)를 사용한다. 이는 해당 간선이 정점 간의 최단 경로에 놓이는 횟수를 의미한다.
    • 정점 $i$로부터 $j$로의 최단 경로 수를 $\sigma_{i,j}$라고하고, 그 중 간선 $(x,y)$를 포함한 것을 $\sigma_{i,j}(x,y)$라고하자.

    • 이때, 간선 $(x,y)$의 매개 중심성은 다음 수식으로 계산된다.

      \[\sum_{i<j}\frac{\sigma_{i,j}(x,y)}{\sigma_{i,j}}\]

      image

    • 위 그림에서 좌측 4점과 우측 4점을 잇는 중간 edge는 그래프 내의 임의의 두 점을 이을 때 총 16번을 거치게되므로 betweenness centrality는 16이 된다.

      • betweenness centrality에 대한 자세한 내용을 여기에서 확인할 수 있다.

  • 눈치 챘을지 모르겠지만, betweenness centrality이 높을 수록, 각 군집을 연결하는 bridge 역할을 하는 것을 알 수 있다.

  • 알고리즘의 순서는 다음과 같다.
    • 매개 중심성이 높은 간선을 순차적으로 제거한다.
    • 간선이 제거될 때마다, betweenness centrality를 다시 계산하여 갱신한다.
    • 간선이 모두 제거될 때까지 반복한다.

  • 간선의 제거 정도에 따라서 다른 Granularity(입도)의 군집 구조가 나타난다. image

  • 그렇다면 간선을 어느정도로 제거해야 적합할까?
    • 너무 적게 제거하면 군집의 탐색이 완전하지 않다.
    • 너무 많이 제거하면 과도한 군집 분해로 적합하지 않다.

    • 현재 time step에서의 connection을 기준으로 군집을 가정한다. 단, 이때마다 각 입력 그래프에서의 군집성(Modularity)을 계산한다.

      image

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

    즉, 전체 그래프에서 시작해서 점점 작은 단위를 검색하는 하향식(탑다운) 방법이다.


​

Louvain 알고리즘

Louvain 알고리즘은 대표적인 상향식(Bottom-Up) 군집 탐색 알고리즘이다.

  • 각 정점이 하나의 군집이라고 가정하며 시작한다.
  • 점점 군집을 병합시키면서 큰 군집을 형성한다. (이 과정을 1pass라고 한다.)
  • pass를 중첩시키면서 점점 큰 군집을 합친다.

그렇다면 어떤 기준으로 군집을 합칠까? 군집성!

  1. Louvain 알고리즘은 개별 정점으로 구성된 크기 1의 군집들로부터 시작한다.
  2. 각 정점 $u$를 기존 혹은 새로운 군집으로 이동한다. 이때, 군집성이 최대화되도록 군집을 결정한다.
  3. 더 이상 군집성이 증가하지 않을 때까지 step 2를 반복한다.
  4. 각 군집을 하나의 정점으로하는 군집 레벨의 그래프를 얻은 뒤 step 3를 수행한다. image
  5. 한 개의 정점이 남을 때까지 step 4를 반복한다.


중첩이 있는 군집 탐색

실생활에서의 그래프 군집에서는 중첩이 많다. 각 개인(vertex)는 여러 네트워크에 속하여 사회적 역할을 수행한다. 앞서 배운 Girvan-Newman 혹은 Louvain 알고리즘은 군집 간의 중첩이 없다고 가정한 상태에서 시작하는 알고리즘이다. 그렇다면, 중첩이 있는 경우에 군집을 어떻게 찾을까? image


중첩 군집 모형

아래와 같은 중첩 군집모형을 가정하자.

  1. 각 정점은 여러 개의 군집에 속할 수 있다.
  2. 각 군집 A에 대하여 같은 군집에 속하는 두 정점은 $P_A$ 확률로 간선으로 직접 연결된다.
  3. 두 정점이 여러 군집에 동시에 속할 경우 간선 연결 확률은 독립적이다.
    1. 예) 두 정점이 A, B 두 군집에 동시에 속할 경우, 두 정점이 간선으로 직접 연결될 확률은 $1-(1-P_A)(1-P_B)$이다.
  4. 어느 군집에도 속하지 않는 두 정점은 낮은 확률 $\epsilon$으로 직접 연결된다.

위와 같이 군집 모형이 주어지면 주어진 그래프의 확률을 계산할 수 있다. 그래프의 확률은 다음 확률들의 곱으로 표현가능하다.

  • 그래프의 각 간선의 두 정점이 (모형에 의해) 직접 연결될 확률
  • 그래프에서 직접 연결되지 않은 각 정점 쌍이 (모형에 의해) 직접 연결되지 않을 확률 image
  • 중첩 군집 모형을 통해 그래프의 확률을 계산할 수 있다.
  • 하지만, 현실에서는 반대로 그래프는 주어져 있지만 중첩군집모형이 주어지지 않은 경우가 많다.
  • 중첩 군집 탐색은 주어진 그래프의 확률을 최대화하는 중첩 군집 모형을 찾는 과정이다. image
  • 이는 통계적으로 Maximum Likelihood Estimate(최우도 추정치)를 찾는 과정과 동일하다. 즉, 주어진 그래프의 확률을 최대화하는 중첩 군집 모형을 찾는 과정이다.
  • 하지만 이 추정은 쉽지 않다. 그 이유는 각 vertex가 각 군집에 속하는지 여부가 이산적(discrete)으로 결정되기 때문이다. 이말은 Continuous한 도메인에서 사용할 수 있는 각종 최적화 기술들(이를테면 경사하강법)을 사용할 수 없음을 의미한다.

이에따라 중첩 군집 탐색을 용이하게 하기 위한 완화된 중첩 군집 모형이 사용된다.

  • 완화된 중첩 군집 모형은 각 정점이 각 군집에 속해있는 정도를 실수값으로 표현한다.
  • 즉, 기존 모형에서는 각 정점이 각 군집에 속함 / 안속함 둘중 하나였다면, 이 방식은 어느 그룹에 속할 확률이 얼마인지를 표현할 수 있게 된 것이다. image
  • 복잡해보이지만, 모형의 매개변수들이 실수 값을 가지기 때문에, 익숙한 최적화 도구(경사하강법 등)를 사용하여 모형을 탐색할 수 있다는 장점이 있다.


추천시스템 Basic

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

내용 기반(Content-based) 추천은 각 사용자가 구매/만족했던 상품과 유사한 것을 추천하는 방법입니다. 예시는 다음과 같습니다

  • 동일한 장르의 영화를 추천하는 것
  • 동일한 감독의 영화 혹은 동일 배우가 출현한 영화를 추천하는 것
  • 동일한 카테고리의 상품을 추천하는 것
  • 동갑의 같은 학교를 졸업한 사람을 친구로 추천하는 것


내용기반 추천의 단계

image

  • 사용자가 선호했던 상품들의 상품 프로필을 수집하는 단계

    • 해당 상품의 특성을 나열한 벡터를 의미한다.

    • 영화의 경우 감독, 장르, 배우 등의 one-hot-encoding이 프로필로 사용될 수 있다.

      image

  • 사용자 프로필(User Profile)을 구성하는 단계

    • 사용자 프로필은 선호한 상품의 상품 프로필을 선호도를 사용하여 가중 평균하여 계산합니다 즉 사용자 프로필 역시 벡터를 말한다.
    • 이 역시 상품 프로필과 비슷한 형태의 one-hot-encoding으로 표현될 수 있다.

  • 사용자 프로필과 상품 프로필을 매칭하는 단계

    • 사용자 프로필 벡터 $\vec{u}$와 상품 프로필 벡터 $\vec{v}$의 코사인 유사도 $\frac{\vec{u}\cdot\vec{v}}{\vert\vert\vec{u}\vert\vert~\vert\vert\vec{v}\vert\vert}$를 계산한다.

    • 즉, 두 벡터 사이각의 코사인 값을 계산한다.

      image

    • 코사인 유사도가 높을 수록, 해당 사용자가 과거 선호했던 상품들과 해당 상품이 유사함을 의미한다.

  • 사용자에게 상품을 추천하는 단계

    • 계산한 코사인 유사도가 높은 상품들을 추천한다.

이 같은 내용 기반 추천시스템은 다음 4가지의 장점을 갖는다.

  1. 다른 사용자의 구매 기록이 필요하지 않다.
  2. 독특한 취향의 사용자에게도 추천이 가능하다
  3. 새 상품에 대해서도 추천이 가능하다
  4. 추천의 이유를 제공할 수 있다.

반대로 이 시스템은 단점도 존재한다.

  1. 상품에 대해 부가 정보가 없는 경우 사용하기 힘들다
  2. 구매기록이 없는 사용자에게는 사용할 수 없다.
  3. 과적합(overfitting)으로 지나치게 협소한 추천을 할 위험이 존재한다.


협업 필터링 추천시스템

다양한 Collaborative Filtering 방식 중 user to user collaborative filtering에 대해 알아보도록 하자

Collaborative Filtering

사용자-사용자 협업 필터링은 다음의 세 단계로 이루어진다.

  1. 추천의 대상 사용자를 $x$라고 한다.
  2. 우선 $x$와 유사한 취향의 사용자를 찾는다.
  3. 다음 단계로 유사한 취향의 사용자들이 선호하는 상품을 찾는다.

  4. 마지막으로 이 상품을 $x$에게 추천한다.

    image

user-user 협업 필터링의 핵심은 유사한 취향의 사용자를 찾는 것이다. 이때 취향의 유사도는 어떻게 계산할까?

image-20210225180129028

  • ”?”는 평점이 입력되지 않은 경우를 의미한다.
  • 지수와 제니의 취향이 유사하고, 로제는 둘과는 다른 취향을 가진 것으로 보인다.

이때 유사성은 상관 계수(Correlation Coefficient)를 통해 측정한다.

  • 사용자 $x$의 상품 $s$에 대한 평점을 $r_{xs}$라고 한다.
  • 사용자 $x$가 매긴 평균 평점을 $\overline{r_x}$라고 하자.
  • 사용자 $x$와 $y$가 공동 구매한 상품을 $S_{xy}$라고 하자.

  • 이때, 사용자 $x$와 $y$의 취향 유사도는 아래 수식으로 계산한다.

    \[sim(x,y)=\frac{\sum_{s\in S_{xy}}(r_{xs}-\overline{r_x})(r_{ys}-\overline{r_y})}{\sqrt{\sum_{s\in S_{xy}}(r_{xs}-\overline{r_x})^2}\sqrt{\sum_{s\in S_{xy}}(r_{ys}-\overline{r_y})^2}}\]
  • 즉, 통계에서의 상관계수를 사용해 취향의 유사도를 계산한다.

예시를 들어보면

image

  • 지수와 제니의 취향의 유사도는 0.88이다. (계산은 직접 해보길 추천한다.)
  • 하지만 반대로 지수와 로제의 취향 유사도는 -0.94로 매우 상이함을 알 수 있다.
  • 따라서 지수의 취향을 추정할 때는 제니의 취향을 참고하게 된다.

구체적으로 취향의 유사도를 가중치로 사용한 평점의 가중 평균을 통해 평점을 추정한다.

  • 사용자 $x$의 상품 $s$에 대한 평점 $r_{xs}$를 추정한다고 가정하자
  • 앞서 설명한 상관계수를 이용하여 상품 $s$를 구매한 사용자 중 $x$와 취향이 가장 유사한 $k$명의 사용자 $N(x;s)$를 뽑느다.

  • 이때, 평점 $r_{xs}$는 아래와 같이 추정할 수 있다.

    \[\hat{r}_{xs}=\frac{\sum_{y\in N(x;s)}sim(x,y)\cdot r_{ys}}{\sum_{y\in N(x;s)}sim(x,y)}\]
  • 취향의 유사도를 가중치로 사용한 평점의 가중 평균을 계산한다.

마지막으로 추정한 평점이 가장 높은 상품을 추천한다.

  • 추천의 대상 사용자를 $x$라고 가정하자
  • 앞서 설명한 방법을 통해, $x$가 아직 구매하지 않은 상품 각각에 대해 평점을 추정한다.
  • 추정한 평점이 가장 높은 상품들을 $x$에게 추천한다.

Collaborative filtering의 장단점

(+) 상품에 대한 부가 정보가 없는 경우에도 사용할 수 있습니다

(−) 충분한 수의 평점 데이터가 누적되어야 효과적입니다(Cold )
(−) 새 상품, 새로운 사용자에 대한 추천이 불가능합니다
(−) 독특한 취향의 사용자에게 추천이 어렵습니다


추천시스템의 평가

추천 시스템의 평가는 전체 데이터를 Training과 Test 데이터로 분리하는 것부터 시작한다.

image

  • 여기서 평가 데이터는 주어지지 않은 상태로 가정하고, 이 평가 데이터의 평점을 추정한다.
  • 이때, 추정된 평가 데이터와 실제 데이터의 오차를 측정하여 평가를 실시한다.

평가지표

오차를 측정하는 지표로는 MSE가 많이 사용된다.

  • 평가 데이터 내의 평점들의 집합을 $T$라고 할때, MSE는 아래와 같이 게산된다.

    \[\frac{1}{\vert T\vert}\sum_{r_{xi}\in T}(r_{xi}-\hat{r}_{xi})^2\]

  • 또한 평균 제곱근 오차(RMSE)도 많이 사용한다.

    \[\sqrt{\frac{1}{\vert T\vert}\sum_{r_{xi}\in T}(r_{xi}-\hat{r}_{xi})^2}\]

  • 이 밖에도 다양한 지표가 사용되기도 한다.

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

Further Reading