해당 포스팅은 네이버 부스트캠프 AI Tech 학습 정리 자료임을 알려드립니다.
1. 강의 정리
신기정 교수님 - 그래프의 구조를 어떻게 분석할까?
1) 군집 구조와 군집 탐색 문제
군집은 다음 조건들을 만족하는 정점들의 집합입니다.
- 집합에 속하는 정점 사이에는 많은 간선이 존재합니다
- 집합이 속하는 정점과 그렇지 않은 정점 사이에는 적은 수의 간선이 존재합니다.
위에서 언급한 조건들은 많고 적다의 정확한 기준이 없어서 수학적으로 엄밀한 정의는 아닙니다. 위의 그림에서는 총 11개의 군집이 있는 것을 확인할 수 있습니다.
온라인 소셜 네트워크의 군집들은 사회적 무리(Social Circle)를 의미하는 경우가 많습니다. 위에 있는 그림에는 가족으로 이뤄진 군집, 고등학교 친구들 군집 등 다양한 군집이 존재합니다. 이러한 온라인 소셜 네트워크의 군집은 부정행위와 관련된 경우도 많습니다. 임의의 계정을 통해서 팔로워를 늘려주기도 하고, 이러한 임의의 계정들이 군집을 형성하기도 합니다.
조직 내의 분란이 소셜 네트워크 상의 군집으로 표현된 경우도 있습니다. 위의 그림은 대학교 가라테 동아리 내의 친구 관계를 보여줍니다. 내분으로 동아리가 둘로 나뉘는 사건으로 2개의 군집을 형성하는 것을 확인할 수 있습니다.
위에서 보이는 키워드 - 광고주 그래프에서는 동일한 주제의 키워드들이 군집을 형성하는 것을 확인할 수 있습니다. 그림은 키워드-광고주 그래프의 인접 행렬을 시각화한 것으로 원소 중 0은 흰색, 나머지는 검은색으로 표시한 것으로 Gambling 안에 sports betting이라는 키워드가 군집을 이루고 있습니다.
뉴런 간 연결 그래프에서는 군집들이 뇌의 기능적 구성단위를 의미합니다. 이렇게 그래프를 여러 군집으로 잘 나누는 문제를 군집 탐색(Community Detection) 문제라고 합니다. 보통은 각 정점이 한 개의 군집에 속하도록 군집을 나눕니다. 위의 모형들은 비지도 기계학습 문제인 클러스터링(Clustering)과 상당히 유사합니다. 하지만, 클러스터링은 피처들의 벡터 형태로 표현된 인스턴스를 그룹으로 묶는 것이고, 군집 탐색은 정점들을 그룹으로 묶는 차이가 있습니다.
2) 군집 구조의 통계적 유의성과 군집성
성공적인 군집 탐색은 군집 구조가 성공적인지 여부를 배치 모형과의 비교를 통해 결정하는 것입니다. 그래서 군집 구조의 통계적 유의성을 측정할 때에는 관련된 지표인 군집성을 살펴봐야 합니다.
성공적인 군집 탐색을 정의하기 위해 먼저 배치 모형(Configuration Model)을 설명해야 합니다. 배치 모형은 각 정점의 연결성(Degree)을 보존한 상태에서 간선들을 무작위로 재배치하여서 얻은 그래프를 의미합니다.
위의 그림에서 좌측의 그림처럼 1-3-2-2로 정점의 연결성을 보존한 상태에서 우측의 그림처럼 표현한 것이 바로 배치 모형이 됩니다. 배치 모형에서 임의의 두 정점 $i$와 $j$ 사이에 간선이 존재할 확률은 두 정점의 연결성에 비례합니다.
군집 탐색의 성공 여부를 판단하기 위해서, 군집성(Modularity)이 사용됩니다. 구체적으로 군집성은 아래의 수식으로 계산됩니다.
$ \frac{1}{2|E|} \sum_{s \in S}$(그래프에서 군집 s 내부 간선의 수 - 배치 모형에서 군집 s 내부 간선의 수의 기댓값)
여기서 기댓값을 사용하는 이유는 배치 모형이 무작위성을 포함하고 있기 때문입니다. 차이가 클수록 입력 그래프에서 군집 s의 내부의 간선의 수가 많다는 것을 의미하며 이는 군집 s가 군집의 성질을 잘 만족한다는 것을 알 수 있습니다. 여기서 $2|E|$는 간선의 2배의 숫자로 정규화를 위해 나눠주는 것입니다. 그래프의 각 정점에서의 간선 수를 계산해보면 항상 $2|E|$가 나오게 됩니다. 정리하면, 배치 모형과 비교했을 때, 그래프에서 군집 내부 간선의 수가 월등하게 많을수록 성공한 군집 탐색입니다. 군집성은 항상 -1과 1 사이의 값을 가지며, 보통 0.3~0.7 정도의 값을 가질 때, 그래프에 존재하는 통계적으로 유의미한 군집들을 찾아냈다고 할 수 있습니다.
3) 군집 탐색 알고리즘
여기서 다뤄볼 군집 탐색 알고리즘은 Girvan-Newman 알고리즘과 Louvain 알고리즘입니다. 먼저, Girvan-Newman 알고리즘은 대표적인 하향식(Top-Down) 군집 탐색 알고리즘으로 전체 그래프에서 탐색을 시작합니다. 군집들이 서로 분리될 수 있도록 간선을 순차적으로 제거합니다. 군집과 군집을 연결하는 간선을 다리 역할의 간선이라고 부르는 데, 이 간선들을 먼저 제거하는 방식을 사용합니다. 그러면 다리 역할의 간선을 어떻게 찾아낼 수 있을까요? 간선의 매개 중심성(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}}$$
위의 수식을 통해 매개 중심성을 계산하면 서로 다른 군집을 연결하는 다리 역할의 간선을 찾아낼 수 있습니다.
위의 그림은 Girvan-Newman 알고리즘을 이용해서 매개 중심성이 높은 간선을 순차적으로 제거했습니다. 간선이 제거될 때마다 매개 중심성을 다시 계산하여 갱신합니다. 간선이 모두 제거될 때까지 반복합니다. 간선의 제거 정도에 따라 다른 입도(Granularity)의 군집 구조가 나타납니다. 그렇다면 간선을 어느 정도 제거하는 것이 가장 적합할까요? 앞에서 언급했던 군집성을 그 기준으로 삼고, 군집성이 최대가 되는 지점까지 간선을 제거합니다.
Louvain 알고리즘은 대표적인 상향식(Bottom-Up) 군집 탐색 알고리즘입니다. 개별 정점에서 시작해서 점점 큰 군집을 형성합니다. 이 방법도 군집을 군집성을 기준으로 합치는데 동작 과정은 아래와 같습니다.
- 가장 먼저 개별 정점으로 구성된 크기 1의 군집들로부터 시작합니다.
- 각 정점 $u$ 를 기존 혹은 새로운 군집으로 이동합니다. 이때, 군집성이 최대화되도록 군집을 결정합니다.
- 더 이상 군집성이 증가하지 않으면 2번 과정을 반복합니다.
- 각 군집을 하나의 정점으로 하는 군집 레벨의 그래프를 얻은 뒤 3번 과정을 반복합니다.
- 한 개의 정점이 남을 때까지 4번 과정을 반복합니다.
Louvain 알고리즘을 이용해 소셜 네트워크의 군집을 탐색한 결과를 살펴봅시다.
그래프의 정점들은 실제로는 여러 정점들로 구성된 군집입니다. 불어를 사용하는 사람의 비율이 높을수록 녹색, 독어를 사용하는 사람의 비율이 높을수록 붉은색에 가깝습니다. 위의 그림처럼 대부분의 군집들이 높은 비율의 불어를 사용하는 사람들 혹은 높은 비율의 독어를 사용하는 사람들로 구성되어 있습니다. 예외적으로 가운데 군집 하나는 두 언어를 사용하는 사람들이 혼합되어 있으며, 다리 역할을 하고 있습니다.
4) 중첩이 있는 군집 탐색
실제 그래프에서는 군집들이 중첩되어 있는 경우가 많습니다. 예를 들어 소셜 네트워크에서의 개인은 여러 사회적 역할을 수행합니다. 그 결과 여러 군집에 속하게 됩니다. 하지만, 앞에서 배운 Girvan-Newman 알고리즘과 Louvain 알고리즘은 군집 간의 중첩이 없다고 가정합니다. 그러면 중첩이 있는 군집은 어떻게 찾아낼 수 있을까요?
이를 위해 아래와 같은 중첩 군집 모형을 가정합니다.
- 각 정점은 여러 개의 군집에 속할 수 있습니다.
- 각 군집 $A$에 대하여, 같은 군집에 속하는 두 정점은 $P_{A}$ 확률로 간선으로 직접 연결됩니다.
- 두 정점이 여러 군집에 동시에 속할 경우 간선 연결 확률은 독립적입니다. 예를 들어, 두 정점이 군집 $A$와 $B$에 동시에 속할 경우 두 정점이 간선으로 직접 연결될 확률은 $1-(1-P_{A})(1-P_{B})$입니다.
- 어느 군집에도 함께 속하지 않는 두 정점은 낮은 확률 $\epsilon$으로 직접 연결됩니다.
위의 그림에서는 중첩 군집 모형은 연결 여부에 따라 이산적으로 값을 얻을 수 있지만, 우측의 완화된 중첩 군집 모형의 경우 각 정점으로 향하는 선분의 굵기가 다른 것입니다. 이처럼 완화된 중첩 군집 모형은 연속적인 변수를 활용합니다.
위에서 언급한 중첩 군집 모형이 주어지면, 주어진 그래프의 확률을 계산할 수 있습니다. 그래프의 확률은 그래프의 각 간선의 두 정점이 모형에 의해 직접 연결될 확률과 그래프에서 직접 연결되지 않은 각 정점 쌍이 모형에 의해 직접 연결되지 않을 확률을 곱한 값이 됩니다. 중첩 군집 탐색은 주어진 그래프의 확률을 최대화하는 중첩 군집 모형을 찾는 과정입니다. 즉, 최대 우도 추정치(Maximum Likelihood Estimate)를 찾는 과정입니다. 하지만, 각 정점이 군집에 속하는 여부가 이산적이기 때문에 연속적인 경우 사용 가능한 경사 하강법 등을 사용할 수 없어서 추정 과정이 쉽지 않습니다.
이것을 용이하게 하기 위해서 나온 모형이 완화된 중첩 군집 모형입니다. 완화된 중첩 군집 모형에서는 각 정점이 각 군집에 속해 있는 정도를 실숫값으로 표현합니다. 최적화 관점에서는 모형의 매개변수들이 실수 값을 가지기 때문에 익숙한 최적화 도구인 경사 하강법 등을 사용해서 모형을 탐색할 수 있다는 장점이 있습니다.
신기정 교수님 - 그래프를 추천 시스템에 어떻게 적용할까? (기초)
1) 우리 주변의 추천 시스템
해외 직구 사이트인 아마존에 들어가 보면 메인화면에 유난히 나에게 맞춰진 상품들이 떠있는 경우를 많이 볼 수 있습니다. 예를 들어, 레고를 구매한 적이 있는 경우에는 레고와 관련된 추천 상품들이 메인 화면에서 "나를 사달라"라고 외치고 있습니다. 또는 특정 상품을 살펴볼 때, 그것과 함께 구매할 상품들도 추천해줍니다. 코로나로 인해 집에 있는 시간이 많아지면서 넷플릭스나 유튜브를 보는 사람들이 늘어났습니다. 넷플릭스와 유튜브를 보다 보면, 내가 좋아하는 장르의 영화를 추천해주거나 유튜브 영상을 추천해줘서 어느새 시간이 훌쩍 지나가기도 합니다. 페이스북의 친구 추천도 우리 주변에서 흔히 볼 수 있는 추천 시스템이 적용된 것입니다.
추천 시스템은 사용자 각자가 구매할 만한 혹은 선호할 만한 상품을 추천합니다. 그러면 어떤 것을 기준으로 활용이 가능할까요? 사용자가 온라인 사이트에서 구매하는 상황을 가정하면, 구매 기록이라는 암시적(Implicit)인 선호가 있고, 상품 평점이라는 명시적(Explicit)인 선호가 있습니다. 이러한 선호들을 바탕으로 사용자별 구매를 예측하거나 선호를 추정하는 것이 추천 시스템의 핵심입니다.
2) 내용 기반 추천 시스템
내용 기반(Content-based) 추천은 각 사용자가 구매/만족했던 상품과 유사한 것을 추천하는 방법입니다. 예를 들면, 코믹의 장르를 좋아한다면 동일한 장르의 영화를 추천해주고, 특정 배우가 등장하는 영화를 자주 본다면, 특정 배우가 등장하는 다른 영화를 추천해줍니다. 이렇게 부가정보를 활용해서 사용자에게 추천하는 방법입니다.
내용 기반 추천 시스템은 위의 그림처럼 4가지 단계로 이루어집니다.
- 사용자가 선호했던 상품들의 상품 프로필(Item Profile)을 수집하는 단계입니다. 여기서 말하는 상품 프로필은 해당 상품의 특성을 나열한 벡터입니다. 영화의 경우 감독, 장르, 배우 등의 원-핫 인코딩이 상품 프로필이 될 수 있습니다.
- 사용자 프로필(User Profile)을 구성하는 단계입니다. 사용자 프로필은 선호한 상품의 상품 프로필을 선호도로 사용하여 가중 평균하여 계산하고, 사용자 프로필 역시 벡터 형태입니다.
- 사용자 프로필과 다른 상품들의 상품 프로필을 매칭 하는 단계입니다. 사용자 프로필 벡터와 상품 프로필 벡터 사이의 코사인 유사도를 계산합니다. 코사인 유사도가 높을수록 해당 사용자가 과거 선호했던 상품들과 해당 상품이 유사함을 의미합니다.
- 계산한 코사인 유사도가 높은 상품들을 추천합니다.
이러한 방식의 내용 기반 추천 시스템은 다음의 장점을 갖습니다.
- 다른 사용자의 구매 기록이 필요하지 않습니다.
- 독특한 취향의 사용자에게도 추천이 가능합니다.
- 새 상품에 대해서도 추천이 가능합니다.
- 추천의 이유를 제공할 수 있습니다.(선호도를 알고 있기 때문에 가능합니다)
하지만 아래와 같은 단점도 존재합니다.
- 상품에 대한 부가 정보가 없는 경우에는 사용할 수 없습니다.
- 구매 기록이 없는 사용자에게는 사용할 수 없습니다.
- 과적합으로 지나치게 협소한 추천을 할 위험이 있습니다.
3) 협업 필터링 추천 시스템
사용자-사용자 협업 필터링은 다음 세 단계로 이루어집니다.
- 추천의 대상 사용자를 $x$라고 했을 때,$x$와 유사한 취향의 사용자들을 찾습니다.
- 유사한 취향의 사용자들이 선호한 상품을 찾습니다.
- 이 상품들을 $x$에게 추천합니다.
내용 기반의 추천 시스템과 다르게 사용자와 다른 사용자의 유사도를 찾는 방식을 사용합니다. 취향의 유사도는 어떻게 계산할까요? 아래의 예시를 확인해봅시다.
지수, 로제, 제니는 각자 영화를 보고 평점을 매긴 것을 위의 표로 나타냈습니다. '?'는 아직 영화를 보지 않은 경우 평점을 매기지 않은 것입니다. 위의 표를 보면, 지수와 제니는 취향이 유사하고, 로제는 둘과 다른 취향을 가진 것을 알 수 있습니다.
취향의 유사성은 상관 계수(Correlation Coefficient)를 통해 측정합니다. 사용자 $x$의 상품 $s$에 대한 평점을 $r_{xs}$, 사용자 $x$가 매긴 평균 평점을 $\bar{r_{x}}$, 사용자 $x$와 $y$가 공동 구매한 상품들을 $S_{xy}$라고 하면 $x$와 $y$의 취향의 유사도는 아래 수식으로 계산할 수 있습니다.
$$ 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}}$$
이 수식을 바탕으로 위의 지수와 로제의 유사도를 구해보면 아래와 같은 결과를 얻을 수 있습니다.
이런 방식으로 유사도를 구할 수 있고, 이번에는 평점을 추정해보려고 합니다. 평점은 취향의 유사도를 가중치로 사용한 평점의 가중 평균으로 추정할 수 있습니다. 사용자 $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)r_{ys}}{\sum_{y \in N(x;s)}sim(x,y)}$$
마지막으로 사용자 $x$가 아직 구매하지 않은 상품에 대해 평점을 추정하고 추정한 평점이 가장 높은 상품을 추천하면 됩니다.
협업 필터링은 다음과 같은 장/단점을 갖습니다.
- 상품에 대한 부가정보가 없는 경우에도 사용할 수 있습니다.
- 충분한 수의 평점 데이터가 누적되어야 효과적입니다.
- 새 상품, 새로운 사용자에 대한 추천이 불가능합니다.
- 독특한 취향의 사용자에게 추천이 어렵습니다.
4) 추천 시스템의 평가
위의 그림에서 1번처럼 주어진 데이터를 가지고 있다고 가정해보겠습니다. 그럼 먼저 2번 그림처럼 훈련 데이터와 평가 데이터를 나눠주는 작업을 합니다. 그리고 3번 그림처럼 평가 데이터는 원래 주어지지 않은 것처럼 처리합니다. 그 후 훈련 데이터를 이용해서 4번처럼 주어지지 않은 평점 데이터를 추정합니다. 이렇게 구해진 추정된 평점과 실제 평가 데이터를 비교해서 오차를 측정하는 방식으로 추천 시스템을 평가할 수 있습니다.
오차를 측정하는 평가 지표로는 평균 제곱 오차(Mean Squared Error, MSE)와 평균 제곱근 오차(Root Mean Squared Error, RMSE)가 많이 사용됩니다. 평가 데이터 내의 평점들을 집합을 T라고 합시다. 평균 제곱 오차와 평균 제곱근 오차는 아래 수식으로 계산할 수 있습니다.
$$ MSE = \frac{1}{|T|}\sum_{r_{xi} \in T}(r_{xi}- \hat{r_{xi}})^2, \, RMSE = \sqrt{\frac{1}{|T|}\sum_{r_{xi} \in T}(r_{xi}-\hat{r_{xi}})^2} $$
이밖에도 추정한 평점으로 순위를 매긴 후, 실제 평점으로 매긴 순위와의 상관 계수를 계산하기도 하고, 추천한 상품 중 실제 구매로 이루어진 것의 비율을 측정하기도 합니다. 추천의 순서 혹은 다양성까지 고려하는 지표들도 사용합니다.
