[U] Day 23 - 군집 탐색 & 추천시스템 (기초)

[Graph 5강] 그래프의 구조를 어떻게 분석할까?

군집 구조와 군집 탐색 문제

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

군집 탐색 알고리즘

중첩이 있는 군집 탐색

실습 코드

[Graph 6강] 그래프를 추천시스템에 어떻게 활용할까? (기본)

추천 시스템과 그래프

내용 기반 추천시스템

협업 필터링 추천시스템

추천 시스템의 평가

실습 코드

Reference

---

[Graph 5강] 그래프의 구조를 어떻게 분석할까?

💡

그래프 데이터에서 군집을 어떻게 정의하는지, 군집을 찾기위한 알고리즘은 무엇이 있는지 알아본다.

군집 구조와 군집 탐색 문제

군집이란, 노드들의 특정 형태의 집합을 의미한다. 이 형태는 집합 내에서는 간선이 많고, 집합 외적으로는 간선이 적은 형태이다. 수학적으로 엄밀한 정의는 아니나, 직감적으로 이해할 수 있다.

직감적으로 군집을 구분 해낼 수 있다.

실제 세계에 존재하는 다양한 그래프로부터 우리는 군집형태를 확인할 수 있다. 예를 들어, 온라인 소셜 네트워크의 그래프에서는 사회적 의미를 갖는 사회적 무리를 군집형태로 식별할 수 있다. 이외에도 소셜 네트워크의 군집의 형태를 통해서 우리는 새로운 정보를 얻을수도 있다. 예를 들어, 치팅을 하는 사람들을 식별하거나, 조직내의 분열 등의 정보를 찾아낼 수 있다.

사회적 무리를 의미하는 군집

치팅 계정과 연루된 계정들의 군집

조직 내의 분열을 의미하는 군집

이와 같이 군집을 통해 우리는 많은 정보를 얻을 수 있다. 그래프를 여러 군집으로 잘 구분하는 문제를 군집 탐색 문제라고 한다. 군집 탐색을 '잘'하는 것은 무엇인지, 기준에 대해 먼저 알아보자.

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

군집 구조를 찾아내는 것의 성패는 비교를 통해 이루어진다. 비교는 해당 그래프를 재배치 한 배치모형과 수행된다.

배치모형은 다음과 같은 규칙 하에 무작위적으로 생성된다.

1. 각 정점의 연결성을 유지한다.

2. 간선들을 무작위로 재배치한다.

각 노드의 간선은 동일하게 유지된다. 본인으로부터 출발하고 도착하는 간선은 2개의 간선을 갖는 것으로 판단한다.

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

군집 탐색의 기준으로 삼을 기준 수치는 군집성이다. 군집성은 군집으로 판단한 서브 그래프와, 배치 모형과의 차이를 통해 구해진다. 먼저, 군집으로 판단한 모든 서브 그래프 $s$의 집합인 $S$를 정의한다.

배치 모형은 무작위성을 포함하기 때문에 기댓값으로 계산을 수행한다.

이 값이 커질수록, 즉, 그래프에서 군집 내부의 간선의 수가 많을수록, 군집 탐색을 성공했다고 판단할 수 있다. 군집성은 $\frac{1} {2|E|}$에 의해 정규화되어, 항상 -1~1의 값을 가지고, 통상 0.3~0.7정도의 값을 가질때, 통계적으로 유의미한 군집을 찾아냈다고 판단한다.

군집 탐색 알고리즘

군집 탐색의 기준을 알았으니, 실제로 군집을 탐색하는 알고리즘에 대해 알아보자.

Girvan-Newman 알고리즘은 하향식(Top-Down)으로 이루어진다. 전체 그래프에서 시작하여, 모든 간선이 제거될 때까지 수행하며 가장 높은 군집성을 가지는 순간을 기준으로 군집을 판단한다.

다리의 역할을 하는 간선을 제거하면, 군집을 구할 수 있을 것이다.

간선의 제거는 다리의 역할을 수행하는 간선부터 제거해나간다. 어떤 간선이 다리의 역할을 수행하는지 확인하기 위해, 매개 중심성을 사용한다.

매개 중심성이란 각 정점 간의 최단경로를 만들었을 때, 경로에 사용되는 횟수를 의미한다.

다리의 역할을 하는 경우 매개 중심성이 높고, 군집 내에 있는 경우에는 낮다.

$\sigma_{i,j}$는 $i$부터 $j$까지의 최단 경로의 수이다. $x, y$는 간선을 의미한다.

매개 중심성이 높은 간선을 순차적으로 제거하고, 간선이 모두 제거될 때까지 반복한다.

원래의 그래프 형태

단계별 간선 제거의 예시

모든 간선을 제거한 형태

간선을 제거해 나가는 과정 속에서, 각기 다른 군집의 구조가 나타난다. 이 중에서 군집성이 가장 높은 형태를 복원하고, 각 연결성의 노드를 군집으로 판단한다.

어떤 것을 사용할지에 대한 예시

기준은 군집성이다.

Louvain 알고리즘은 상향식(Bottom-Up) 방식의 알고리즘이다. 처음에는 각 노드를 하나의 군집으로 판단하고, 이를 점점 병합해나가면서 군집화한다. 최종적으로는 모든 노드가 하나의 군집이되고, 이 과정 중에 군집성이 가장 높은 순간의 연결성을 군집으로 판단한다.

Louvain 알고리즘의 동작 예시

중첩이 있는 군집 탐색

실제 세계의 그래프는 군집이 중첩되어 있는 경우가 많다. 예를 들어, 각 개인은 사회에서 여러가지 역할을 동시에 수행하기 때문에 여러 군집에 속할 수 있다.

실제 세계의 그래프 예시

위에서 알아본 두 알고리즘은 중첩이 없다고 가정한다. 그럼 이와 같은 그래프에서 군집은 어떻게 찾아낼 수 있을지 알아보자.

중첩이 없는 그래프와 중첩이 있는 그래프

중첩 군집 모형은 다음과 같은 가정을 통해 모델링된다.

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

2. 각 군집 $A$에 대하여, 같은 군집에 속하는 정점끼리는 $P_A$의 확률로 직접 연결된다.

3. 두 정점이 여러 군집에 동시에 속할 경우 간선의 연결 확률은 독립적이다.

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

중첩 군집 모형이 주어진 상태에서 확률이 주어지면, 정확한 그래프와 각 확률을 계산할 수 있다.

중첩 군집 모형과 확률로부터 그래프를 계산하는 예시

하지만 현실에서는 모수에 해당하는 중첩 군집 모형은 주어지지 않고, 관찰된 그래프만 존재한다. 우리는 그래프로부터 최대 우도 추정을 통해 가능성이 높은 중첩 군집모형을 찾아나가게 된다.

주어진 그래프로부터 중첩 군집 모형을 추정해나가는 과정의 예시

기존의 가정은 각 노드가 특정 군집에 '속하거나', '속하지 않거나' 두 가지의 값만 가질 수 있었다. 이와 같이 이산확률을 통해 계산을 하게 되면, 추정에 어려움이 있기 때문에 완화된 중첩 군집 모형을 사용하게 된다. 이는, 각 정점이 군집에 속해있는 정도를 실수값으로 표현하는 형태이다. 이렇게 연속적인 값을 사용함으로써 우리는 여러가지 최적화 기법을 사용할 수 있게 되었다.

선의 두께는 각 군집에 속하는 가중치를 표현한 것이다.

실습 코드

GitHub Gist Link

---

[Graph 6강] 그래프를 추천시스템에 어떻게 활용할까? (기본)

💡

내용 기반 추천 알고리즘과 협업 필터링 알고리즘에 대해 알아본다.

추천 시스템과 그래프

추천 시스템은 사용자와 상품의 정보를 통해 사용자 각각이 구매할만한 혹은 선호할만한 상품을 추천하는 체계이다. 사용자별 구매기록은 암시적인 선호도로 판단되며, 평점과 같은 명시적인 선호가 있는 경우도 있다.

암시적인 선호도의 예시

명시적인 선호도의 예시

이와 같은 정보를 통해서, 사용자의 구매나 선호를 추정하는 것이다. 그래프의 관점에서는, 누락된 간선의 가중치를 추정하는 문제로 해석할 수 있다.

상호작용이 없는 상품에 대한 선호도를 예측하는 문제로 해석할 수 있다.

내용 기반 추천시스템

내용 기반 추천은 각 사용자가 구매했거나 만족한 상품과 유사한 상품을 추천하는 방법이다.

내용 기반 추천의 예시

내용 기반 추천시스템은 다음과 같은 순서로 동작한다.

1. 상품의 프로필을 벡터형태로 변환한다.

2. 사용자가 상품에 보인 선호도를 가중평균하여 사용자 프로필을 벡터형태로 생성한다.

3. 다른 상품들의 프로필과 코사인 유사도를 계산한다.

4. 코사인 유사도가 높은 상품을 추천한다.

이 방법의 장점과 단점은 다음과 같다.

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

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

협업 필터링 추천시스템

사용자-사용자 협업 필터링은 유사한 사용자가 선호했던 상품에 대해 추천하는 방식이다. 이는 다음과 같은 순서로 동작한다.

1. 사용자 $x$와 유사한 취향의 사용자를 찾는다.

2. 유사한 취향의 사용자가 선호하는 상품을 찾는다.

3. 선택된 상품을 사용자 $x$에게 추천한다.

협업 필터링 추천시스템의 동작 예시

여기에서 중요한 것은 취향의 유사도를 계산하는 방법이다. 취향의 유사도는 상관계수를 통해 측정된다.

상관계수를 계산하는 수식의 예시

구체적으로는 취향의 유사도를 가중치로 사용해 평점의 가중평균으로 평점을 추정하는 방식을 사용한다. 여기에서 구해진 평점이 높을수록 사용자가 선호할 것이라 예측하는 것이다.

이 방법의 장점과 단점은 다음과 같다.

협업 필터링 추천시스템의 장단점

추천 시스템의 평가

추천 시스템의 정확도를 측정하는 기본적인 방법부터 알아보자.

먼저, 주어진 데이터를 훈련 데이터와 평가 데이터로 분리한다. 학습 시에는 평가 데이터를 사용하지 않고 학습을 진행한다. 이후, 훈련 데이터를 통해서 평가 데이터의 평점을 추정한다.

주어진 데이터를 분리하고, 평가데이터를 가린채 학습을 진행한다.

훈련 데이터만으로 학습하고, 가려진 데이터에 대해 추정을 실시한다.

이후 추정한 평점과 실제 평가 데이터를 비교하여 오차를 측정한다. 오차의 측정 지표로는 MSE나 RMSE를 사용할 수 있다. 이외에도 순위를 기준으로 한 상관계수를 사용하기도하고, 상품의 구매율이나 다양성까지 고려하는 지표들도 사용할 수 있다.

실습 코드

Collaborative Filtering

---

Reference

Explain Social Graph

Explain Recommendation System

Uploaded by Notion2Tistory v1.1.0