Ai tech Day23

Lee·2021년 2월 24일

네이버 커넥트 부스트 캠프

그래프의 구조 분석

군집 구조와 군집 탐색 문제

군집의 정의

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

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

수학적으로 엄밀한 정의는 아닙니다. (많은, 적은이라는 추상적 개념)
예시 그래프에는 11개의 군집이 있는 것으로 보입니다.

실제 그래프에서의 군집들

온라인 소셜 네트워크의 군집들은 사회적 무리(Social Circle)을 의미하는 경우가 많습니다.

온라인 소셜 네트워크의 군집들은 부정행위와 관련된 경우도 많습니다.

조직 내의 분란이 소셜 네트워크 상의 군집으로 표현된 경우도 있습니다.

아래 그래프는 대학교 가라테 동아리 내 친구 관계를 보여줍니다. 내분으로 동아리가 둘로 나뉘어지는 사건이 발생했습니다. 그 결과 두 개의 군집이 형성되었습니다.

키워드 - 광고주 그래프에서는 동일한 주제의 키워드들이 군집을 형성합니다.

아래 그림은 키워드 - 광고주 그래프의 인접행렬을 시각화한 것입니다. 원소중 0은 흰색, 나머지는 검은색으로 표시한 것입니다.

뉴런간 연결 그래프에서는 군집들이 뇌의 기능적 구성 단위를 의미합니다.

군집 탐색 문제

그래프를 여러 군집으로 잘 나누는 문제를 군집 탐색(Community Detection) 문제 라고합니다.

보통은 각 정점이 한 개의 군집에 속하도록 군집을 나눕니다. 비지도 기계학습 문제인 클러스터링(Clustering)과 상당히 유사합니다.

클러스터링은 Feature들의 벡터 형태로 표현된 인스턴스들을 그룹으로 묶는거라면 군집 탐색 문제는 정점들을 그룹으로 묶는다.

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

비교대상: 배치모형

성공적인 군집 탐색을 정의하기 위해 먼저 배치 모형(Configuration Model)을 소개합니다.

주어진 그래프에 대한 배치 모형은
1) 각 정점의 연결성(Degree)을 보존한 상태에서
2) 간선들을 무작위로 재배치하여서 얻은 그래프를 의미합니다.

배치 모형에서 임의의 두 정점 $i$ 와 $j$ 사이에 간선이 존재할 확률은 두 정점의 연결성에 비례합니다.

군집성의 정의

군집 탐색의 성공 여부를 판단하기 위해서, 군집성(Modularity)이 사용됩니다.

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

구체적으로 군집성은 다음 수식으로 계산됩니다.

$\cfrac{1}{2|E|}$ : 정규화 과정
배치 모형이 무작위성을 띄기 때문에 기대값으로 한다.

즉 배치 모형과 비교했을때 그래프에서 군집 내부 간선의 수가 월등히 많을수록 성공한 군집 탐색입니다.

즉, 군집성은 무작위로 연결된 배치 모형과의 비교를 통해 통계적 유의성을 판단합니다.

군집성은 항상 –1 과 +1 사이의 값을 갖습니다.
보통 군집성이 0.3 ~ 0.7 정도의 값을 가질 때, 그래프에 존재하는 통계적으로 유의미한 군집들을 찾아냈다고 할 수 있습니다.

군집 탐색 알고리즘

Girvan-Newman 알고리즘

Girvan-Newman 알고리즘은 대표적인 하향식(Top-Down) 군집 탐색 알고리즘입니다.

Girvan-Newman 알고리즘은 전체 그래프에서 탐색을 시작합니다.
군집들이 서로 분리되도록 간선을 순차적으로 제거합니다.

어떤 간선을 제거해야 군집들이 분리될까요?
바로 서로 다른 군집을 연결하는 다리(Bridge) 역할의 간선입니다.

아래 예시에서 파란색선을 따라 간선을 제거한다고 생각해보세요.

서로 다른 군집을 연결하는 다리 역할의 간선을 어떻게 찾아낼 수 있을까요?

간선의 매개 중심성(Betweenness Centrality)을 사용합니다.
이는 해당 간선이 정점 간의 최단 경로에 놓이는 횟수를 의미합니다.

정점 $i$ 로부터 $j$ 로의 최단경로 수를 $\sigma_{i, j}$ 라고 하고
그 중 간선 $(x, y)$ 를 포함한 것을 $\sigma_{i,j}(x,y)$ 라고 합시다. 간선 $(x,y)$ 의 매개 중심성은 다음 수식으로 계산됩니다.

\sum_{i < j} \cfrac{\sigma_{(i,j)}(x,y)}{\sigma_{(i,j)}}

매개 중심성을 통해 서로 다른 군집을 연결하는 다리 역할의 간선을 찾아낼 수 있습니다.

아래 그림은 전화 그래프입니다. 매개 중심성이 높을 수록 붉은 색에 가깝습니다. 실제로 매개 중심성이 높은 간선들이 서로 다른 군집을 연결하는 다리 역할을 하는 것을 확인할 수 있습니다.

Girvan-Newman 알고리즘은 매개 중심성이 높은 간선을 순차적으로 제거합니다.

간선이 제거될 때마다 매개 중심성을 다시 계산하여 갱신합니다.

간선이 모두 제거될 때까지 반복합니다.

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

간선을 어느 정도 제거하는 것이 가장 적합할까요?

앞서 정의한 군집성을 그 기준으로 삼습니다.
즉, 군집성이 최대가 되는 지점까지 간선을 제거합니다.

단, 현재의 연결 요소들을 군집으로 가정하되, 입력 그래프에서 군집성을 계산합니다.

정리하면, Girvan-Newman 알고리즘은 다음과 같습니다.

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

즉, 전체 그래프에서 시작해서 점점 작은 단위를 검색하는 하향식(Top-Down) 방법입니다.

Louvain 알고리즘

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

Louvain 알고리즘은 개별 정점에서 시작해서 점점 큰 군집을 형성합니다.

그러면 어떤 기준으로 군집을 합쳐야 할까요?
정답은 이번에도 군집성입니다!

구체적으로 Louvain 알고리즘의 동작 과정은 다음과 같습니다.

1) Louvain 알고리즘은 개별 정점으로 구성된 크기 1의 군집들로부터 시작합니다.

2) 각 정점 $u$ 를 기존 혹은 새로운 군집으로 이동합니다. 이때, 군집성이 최대화 되도록 군집을 결정합니다.

3) 더 이상 군집성이 증가하지 않을 때까지 2)를 반복합니다.

4) 각 군집을 하나의 정점으로 하는 군집 레벨의 그래프를 얻은 뒤 3)을 수행합니다.

5) 한 개의 정점이 남을 때까지 4)를 반복합니다.

Louvain 알고리즘을 이용해 소셜 네트워크의 군집을 탐색한 결과를 살펴봅시다.

그래프의 정점들은 실제로는 여러 정점들로 구성된 군집입니다.
불어를 사용하는 사람의 비율이 높을 수록 녹색에, 독어를 사용하는 사람의 비율이 높을 수록 붉은색에 가깝습니다.

대부분 군집들이 높은 비율의 불어를 사용하는 사람들 혹은 높은 비율의 독어를 사용하는 사람들로 구성되어 있습니다.

예외적으로 가운데 군집 하나는 두 언어를 사용하는 사람들이 혼합되어 있으며 다리 역할을 합니다.

중첩이 있는 군집 탐색

중첩이 있는 군집구조

실제 그래프의 군집들은 중첩되어 있는 경우가 많습니다.

예를 들어 소셜 네트워크에서의 개인은 여러 사회적 역할을 수행합니다. 그 결과 여러 군집에 속하게 됩니다.

앞서 배운 Girvan-Newman 알고리즘, Louvain 알고리즘은 군집 간의 중첩이 없다고 가정합니다. 그러면 중첩이 있는 군집은 어떻게 찾아낼 수 있을까요?

중첩 군집 모형

이를 위해 아래와 같은 중첩 군집 모형을 가정합니다.

1) 각 정점은 여러 개의 군집에 속할 수 있습니다.

2) 각 군집 $A$ 에 대하여, 같은 군집에 속하는 두 정점은 $P_A$ 확률로 간선으로 직접 연결됩니다.

3) 두 정점이 여러 군집에 동시에 속할 경우 간선 연결 확률은 독립적입니다. 예를들어 두 정점이 군집 $A$ 와 $B$ 에 동시에 속할 경우 두 정점이 간선으로 직접 연결 될 확률은 $1 - (1 - P_A)(1 - P_B)$ 입니다.

4) 어느 군집에도 함께 속하지 않는 두 정점은 낮은 확률 $\epsilon$ 으로 직접 연결됩니다.

중첩 군집 모형이 주어지면, 주어진 그래프의 확률을 계산할 수 있습니다.

그래프의 확률은 다음 확률들의 곱입니다.
1) 그래프의 각 간선의 두 정점이 (모형에의해) 직접 연결될 확률
2) 그래프에서 직접 연결되지 않은 각 정점 쌍이 (모형에의해) 직접 연결되지 않을 확률

중첩 군집 탐색은 주어진 그래프의 확률을 최대화하는 중첩 군집 모형을 찾는 과정입니다.

통계 용어를 빌리면, 최우도 추정치(Maximum Likelihood Estimate)를 찾는 과정입니다.

완화된 중첩 군집 모형

중첩 군집 탐색을 용이하게 하기 위하여 완화된 중첩 군집 모형을 사용합니다.

완화된 중첩 군집 모형에서는 각 정점이 각 군집에 속해 있는 정도를 실숫값으로 표현합니다.

즉, 기존 모형에서는 각 정점이 각 군집에 속하거나 속하지 않거나 둘 중 하나였는데, 중간 상태를 표현할 수 있게 된 것입니다.
(실제로 우리가 속해 있는 여러 무리가 있을 때 어떤 무리에는 더 소속감을 느끼고 어떤 무리에는 덜 소속감을 느끼는 경우가 있습니다.)

최적화 관점에서는 모형의 매개변수들이 실수값을 가지기 때문에 익숙한 최적화 도구(경사하강법등)을 사용하여 모형을 탐색할 수 있다는 장점이 있습니다.

그래프와 추천시스템

우리 주변의 추천 시스템

아마존에서의 상품 추천

Amazon.com 메인 페이지에는 고객 맞춤형 상품 목록을 보여줍니다.

Amazon.com 에서 특정 상품을 살펴볼 때, 함께 혹은 대신 구매할 상품 목록을 보여줍니다.

넷플릭스에서의 영화 추천

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

유튜브에서의 영상 추천
유튜브 메인 페이지에는 고객 맞춤형 영상 목록을 보여줍니다.

유튜브는 현재 재생 중인 영상과 관련된 영상 목록을 보여줍니다.

페이스북에서의 친구 추천

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

내용 기반 추천시스템

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

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

예시는 다음과 같습니다.

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

내용 기반 추천은 다음 네 가지 단계로 이루어집니다.

첫 단계는 사용자가 선호했던 상품들의 상품 프로필(Item Profile)을 수집하는 단계입니다.

어떤 상품의 상품 프로필이란 해당 상품의 특성을 나열한 벡터입니다.

영화의 경우 감독, 장르, 배우 등의 원-핫 인코딩이 상품 프로필이 될 수 있습니다.

다음 단계는 사용자 프로필(User Profile)을 구성하는 단계입니다.

사용자 프로필은 선호한 상품의 상품 프로필을 선호도를 사용하여 가중 평균하여 계산합니다. 즉 사용자 프로필 역시 벡터입니다.

앞선 영화 프로필 예시에서는 다음과 같은 형태의 사용자 프로필을 얻을 수 있습니다.

다음 단계는 사용자 프로필과 다른 상품들의 상품 프로필을 매칭하는 단계입니다.

사용자 프로필 벡터 $\vec{u}$ 와 상품 프로필 벡터 $\vec{v}$ 의 코사인 유사도 $\cfrac{\vec{u} \cdot \vec{v}}{||\vec{u}||\;||\vec{v}||}$ 를 계산합니다.

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

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

마지막 단계는 사용자에게 상품을 추천하는 단계입니다.

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

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

내용 기반 추천시스템은 다음 장점을 갖습니다.

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

예시: 당신은 로맨스 영화를 선호 했기 때문에, 새로운 로맨스 영화를 추천합니다.

왜 이 영화를 추천했는지 코사인 유사도에서 큰 일치가 일어나는 부분(로맨스)를 갖고 추천의 이유를 제공할 수 있습니다.

내용 기반 추천시스템은 다음 단점을 갖습니다.

(1) 상품에 대한 부가 정보가 없는 경우에는 사용할 수 없습니다.
(2) 구매 기록이 없는 사용자에게는 사용할 수 없습니다.
(3) 과적합(Overfitting)으로 지나치게 협소한 추천을 할 위험이 있습니다. (우연히 로맨스 영호를 많이 봤을 경우)

협업 필터링 추천시스템

협업 필터링의 원리

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

추천의 대상 사용자를 $x$ 라고 합시다.
우선 $x$ 와 유사한 취향의 사용자들을 찾습니다.
다음 단계로 유사한 취향의 사용자들이 선호한 상품을 찾습니다.
마지막으로 이 상품들을 $x$ 에게 추천합니다.

사용자-사용자 협업 필터링의 핵심은 유사한 취향의 사용자를 찾는 것입니다.
그런데 취향의 유사도는 어떻게 계산할까요?

위 예시는 사용자 별 영화 평점입니다.
'?'는 평점이 입력되지 않은 경우를 의미합니다.
지수와 제니의 취향이 유사하고, 로제는 둘과 다른 취향을 가진 것을 알 수 있습니다.

취향의 유사성은 상관 계수(Correlation Coefficient)를 통해 측정합니다.

사용자 $x$ 의 상품 $s$ 에 대한 평점을 $r_{xs}$ 라고 합시다.
사용자 $x$ 가 매긴 평균 평점을 $\bar{r}_x$ 라고 합시다.
사용자 $x$ 와 $y$ 가 공동 구매한 상품들을 $S_{xy}$ 라고 합시다.
사용자 $x$ 와 $y$ 의 취향의 유사도는 아래 수식으로 계산합니다.

sim(x,y)=\cfrac{\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}}

즉, 통계에서의 상관 계수(Correlation Coefficient)를 사용해
취향의 유사도를 계산합니다.

예시에서 취향의 유사도를 계산해봅시다.

지수와 로제의 취향의 유사도는 0.88 입니다.

\cfrac{(4-3)(5-3)+(1-3)(1-3)+(5-3)(4-3)}{\sqrt{(4-3)^2 + (1-3)^2 + (5-3)^2}\sqrt{(5-3)^2+(1-3)^2+(4-3)^2}} = 0.88

즉 둘의 취향은 매우 유사합니다.

지수와 로제의 취향의 유사도는 -0.94 입니다.

\cfrac{(4-3)(2-4)+(1-3)(5-4)+(2-3)(5-4)}{\sqrt{(4-3)^2 + (1-3)^2 + (2-3)^2}\sqrt{(2-4)^2+(5-4)^2+(5-4)^2}} = -0.94

즉 둘의 취향은 매우 상이합니다.

따라서, 지수의 취향을 추정할 때는 제니의 취향을 참고하게 됩니다.

예를 들면, 지수는 미녀와 야수를 좋아할 확률이 낮습니다.
지수와 제니의 취향은 유사하고, 제니는 미녀와 야수를 좋아하지 않았기 때문입니다.

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

사용자 $x$ 의 상품 $s$ 에 대한 평점을 $r_{xs}$ 를 추정하는 경우를 생각합시다.

앞서 설명한 상관 계수를 이용하여 상품 $s$ 를 구매한 사용자 중에
$x$ 와 취향이 가장 유사한 $k$ 명의 사용자 $N(x; s)$ 를 뽑습니다.

평점 $r_{xs}$ 는 아래의 수식을 이용해 추정합니다.

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

즉, 취향의 유사도를 가중치로 사용한 평점의 가중 평균을 계산합니다.

마지막 단계는 추정한 평점이 가장 높은 상품을 추천하는 단계입니다.

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

협업 필터링의 장단점

협업 필터링은 다음 장점과 단점 갖습니다.

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

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