[Week 5-3] 🔗군집 구조와 탐색

5주차 수요일

• 군집 구조
• 군집 탐색 알고리즘
• 추천 시스템

---

[군집 구조]

• 군집(Community)
  군집에 속하는 정점 사이에는 많은 간선이 존재해야 한다.
  군집에 속하는 정점과 그렇지 않은 정점 사이에는 적은 수의 간선이 존재해야 한다.

온라인 소셜 네트워크의 군집들은 대개 가족, 친구, 동료 등 사회적 무리를 의미한다. 그러나 어떤 경우에는 부정행위나 조직 내의 분란이 군집 형태로 나타나기도 한다.

• 군집 탐색
  그래프를 여러 군집으로 나누는 것을 군집 탐색이라고 하며, 보통 각 정점이 하나의 군집에 속하도록 군집을 나눈다. 비지도 기계학습 문제인 클러스터링과 유사하다.

먼저, 군집을 탐색하기 위해 원본 그래프의 비교 대상이 될 배치 모형을 정의한다. 배치 모형이란 각 정점의 연결성을 보존한 상태에서 간선들을 무작위로 재배치해서 얻은 그래프다.배치 모형에서 임의의 두 정점 i와 j 사이에 간선이 존재할 확률은 두 정점의 연결성에 비례한다.

• 군집성
  군집성이란 군집 탐색의 성공 여부를 판단하는 척도다. 그래프 G와 군집들의 집합 S가 주어졌을 때 각 군집 s (s∈S)가 군집의 성질을 잘 만족하는지 살펴보기 위해 해당 군집 내부의 간선 수를 그래프와 배치 모형에서 각각 비교한다. 배치 모형과 비교했을 때 그래프에서 군집 내부 간선의 수가 월등히 많다면 성공적으로 군집을 탐색한 것이다.

군집성을 수식으로 정의하면 다음과 같다.

정규화를 거치기 때문에 군집성은 항상 -1≤ ≤1 범위의 값이 된다. 보통 군집성이 0.3~0.7 정도의 값을 가질 때 그래프에 존재하는 유의미한 군집을 찾았다고 볼 수 있다.

---

[군집 탐색 알고리즘]

군집 간에 중첩이 없는 경우에 군집을 탐색하는 알고리즘이다.

• Girvan-Newman 알고리즘
  대표적인 Top-down 형식 군집 탐색 알고리즘이다. 전체 그래프에서 탐색을 시작하여 군집들이 서로 분리되도록 간선을 순차적으로 제거한다. 서로 다른 군집을 연결하는 다리 역할의 간선을 제거해야 하는데, 다리가 되는 간선을 찾기 위해 어떤 간선이 정점 간의 최단경로에 놓이는 횟수(매개 중심성)을 이용하며, 매개 중심성을 구하는 수식은 다음과 같다.
  
  
  알고리즘 동작 방식은 다음과 같다.

1. 매개 중심성이 가장 높은 간선을 제거한다.
2. 간선을 하나 제거할 때마다 매개 중심성을 다시 계산하여 갱신한다.
3. 모든 간선이 제거될 때까지 이것을 반복한다.

간선을 얼마나 제거하냐에 따라서 다른 입도(granularity, 입자가 고운 정도?)의 군집 구조를 얻을 수 있다. 적절한 군집을 찾는 것이 목표이므로, 간선을 제거할 때 군집성을 계산하여 군집성이 최대가 되는 지점까지만 간선을 제거해야 한다. 이 때 간선을 제거해서 얻은 연결 요소들을 군집으로 가정하고 입력 그래프의 군집성을 계산하다.

• Louvain 알고리즘
  대표적인 Bottom-up 형식 군집 탐색 알고리즘이다. 개별 정점이 하나의 군집을 이룬다고 가정한 뒤 점점 주변의 군집을 병합하며 군집의 크기를 키운다. 알고리즘 동작 방식은 다음과 같다.

1. 개별 정점으로 구성된 크기 1의 군집들을 가정한다.
2. 각 정점 u를 기존의 군집 또는 새로운 군집으로 이동시킨다. 이 때 군집성이 최대화되도록 정점을 이동시킨다.
3. 더 이상 군집성이 증가하지 않을 때까지 2를 반복한다.
4. 각 군집을 하나의 정점으로 보는 군집 레벨 그래프를 얻은 뒤 3을 수행한다.
5. 하나의 정점이 남을 때까지 이것을 반복한다.

---

[중첩이 있는 군집 탐색 알고리즘]

실제 그래프의 군집들은 중첩되어 있는 경우가 많다. 예를 들어 소셜 네트워크에서 개인은 학교 친구, 동호회, 직장 등 여러 군집에 속하게 되는데, 이들 군집은 중첩될 수 있다. 앞서 배치 모형을 정의했던 것처럼 중첩 군집을 탐색할 때 원본 그래프와 비교하기 위한 용도로 다음과 같은 중첩 군집 모형을 정의한다.
1. 각 정점은 여러 군집에 속할 수 있다.
2. 각 군집 A에 대하여, 같은 군집에 속하는 두 정점은 P_A 확률로 직접 연결된다.
3. 두 정점이 여러 군집에 동시에 속하는 경우 간선이 연결될 확률은 독립적이다.
두 정점이 군집 A와 B에 동시에 속할 경우 간선으로 직접 연결될 확률은 1-(1 - P_A)(1 - P_B)이 된다.
4. 어느 군집에도 함께 속하지 않는 두 정점은 낮은 확률 ε로 직접 연결된다.

중첩 군집 모형을 통해 주어진 그래프의 확률을 계산할 수 있다. 그래프의 확률은 다음 두 확률의 곱으로 나타낼 수 있다.
1. 그래프에서 간선으로 직접 연결된 두 정점이 모형에 의해 직접 연결될 확률
2. 그래프에서 직접 연결되지 않은 각 정점 쌍이 모형에 의해 직접 연결되지 않을 확률

실제로는 많은 경우에 그래프는 주어지지만 중첩 군집 모형이 주어지지 않은 상태인데, 중첩 군집 모형은 정점이 군집에 속하거나/속하지 않는 이산적 수치로 주어지기 때문에 경사하강법 등의 최적화 기법을 사용할 수 없어 중첩 군집 모형을 찾는 것이 쉽지 않다. 이를 용이하게 하기 위해 완화된 중첩 군집 모형을 사용하는데, 완화된 중첩 군집 모형에서는 각 정점이 각 군집에 속한 정도를 실수값으로 표현한다. 따라서 최적화 기법을 사용하여 군집 모형을 탐색할 수 있다는 장점이 있다.

모르겠는 거)
그래프의 확률이 뭐지? 어떤 의미를 갖는가?
그래프의 확률과 중첩군집모형은 무슨 관계인가?
중첩 군집 모형을 통해서 어떻게 군집을 찾는가?

---

[추천 시스템]

사용자 각각이 구매하거나 선호할 만한 상품을 추천하는 시스템이다. 구매 기록(암시적 선호) 또는 평점(명시적 선호)를 통해 사용자별 구매를 예측하거나 선호를 추정하는 것으로, 미래의 간선을 예측하는 문제 혹은 누락된 간선의 가중치를 추정하는 문제로 해석할 수 있다.

• 내용 기반 추천 시스템
  내용 기반 추천 시스템은 각 사용자가 구매하거나 만족했던 상품과 유사한 것을 추천하는 방법이다.
  동일한 장르/동일한 감독의 영화나 동일 배우가 출연한 영화를 추천하는 것, 동일한 카테고리에 포함되는 상품을 추천하는 것, 동갑이며 같은 학교를 졸업한 사람을 친구로 추천하는 것 등이 여기에 속한다.

내용 기반 추천을 위해서는 사용자가 선호했던 상품들의 상품 프로필을 수집해야 한다. 상품 프로필이란 해당 상품의 특성을 나타낸 벡터로, 영화의 경우 감독, 장르, 배우 등을 벡터로 나열해 원-핫 인코딩한 것이 상품 프로필이 된다. 그 다음 사용자 프로필을 구성하는데, 사용자 프로필이란 사용자가 선호한 상품의 상품 프로필과 해당 사용자의 선호도를 가중 평균하여 계산한 벡터다. 그리고 나서 사용자 프로필과 다른 상품들의 상품 프로필을 매칭하기 위해서 두 벡터의 코사인 유사도(두 벡터 사이각의 코사인 값)를 계산한다. 코사인 유사도가 높을수록 사용자가 과거에 선호했던 상품이 해당 상품과 비슷한 것이다. 이를 이용해 사용자가 선호할 만한 상품을 추천할 수 있다.

내용 기반 추천 시스템은 다른 사용자의 구매 기록이 필요 없고 독특한 취향의 사용자에게 추천이 가능하다는 등의 장점이 있지만 구매 기록이 없는 사용자에게는 추천할 수 없고 과적합으로 인해 지나치게 협소한 추천을 할 위험이 있다는 단점도 가지고 있다.

• 협업 필터링 추천 시스템
  사용자-사용자 협업 필터링 시스템은 추천을 제공할 대상 사용자와 유사한 취향의 사용자를 찾고 그들이 선호한 상품을 추천하는 방법이다. 유사한 취향의 사용자를 찾기 위해 취향의 유사도를 계산해야 하는데, 상관 계수(Correlation coefficient)를 통해 취향의 유사성을 측정한다. 사용자 x와 y의 취향 유사도는 다음과 같은 식으로 계산한다. 취향의 유사도를 가중치로 사용한 평점의 가중 평균을 통해 평점을 예측하게 된다. 예를 들어 사용자 x의 상품 s에 대한 평점 r_xs를 추정한다고 할 때, 상품 s를 구매한 사용자 중에 x와 취향이 가장 유사한 k명의 사용자 집단 N(x;s)를 뽑아 다음과 같이 추정할 수 있다. 추정을 통해 평점이 가장 높은 상품들을 선별, 사용자 x에게 추천한다.

협업 필터링 추천 시스템은 상품의 속성에 대한 부가 정보가 없는 경우에도 사용할 수 있다는 장점을 가지고 있다. 그러나 충분한 수의 평점 데이터가 누적되어야 효과적이라는 점, 새로운 상품이나 새로운 사용자 또는 독특한 취향을 가진 사용자에게 추천하기 힘들다는 단점이 있다.

• 추천 시스템의 평가
  각 행이 사용자, 각 열이 상품이 되도록 행렬을 만든다. 사용자가 구매한 상품에 해당하는 칸을 평점으로 채워 훈련 데이터를 만든다. 행렬의 일부분을 평가 데이터로 사용하기 위해 평점 정보를 가려 두고, 모델을 학습시킨 다음 가려진 부분의 평점을 추정하도록 한다. 추정한 평점과 실제 평가 데이터를 비교하기 위한 지표로는 주로 평균 제곱 오차(MSE)나 평균 제곱근 오차(RMSE) 등을 사용한다. 그 외에도 추정한 평점으로 순위를 매긴 뒤 실제 평점으로 매겨진 순위와의 상관 계수를 계산하거나, 추천한 상품 중 실제 구매로 이루어진 경우의 비율을 측정하는 등의 방법도 사용된다.