Day 23. 군집탐색 & 추천시스템(기초)

1. 군집(Community)의 정의

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

 

 

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

• 성공적인 군집 탐색을 정의하기 위해 - 비교대상: 배치 모형
  • 배치모형: 각 정점의 연결성(degree)을 보존한 상태에서, 간선들을 무작위로 재배치하여 얻은 그래프
• 군집성(Modularity)
  • 그래프와 군집들의 집합 S가 주어졌을 때, 각 군집 s가 군집 집합 S의 성질을 잘 만족하는지를 살펴보기 위해, 군집 내부의 간선의 수를 그래프와 배치 모형에서 비교함
  • (그래프에서 군집 s 내부 간선의 수 - 배치 모형에서 군집 s 내부 간선의 수의 기댓값)을 정규화 한 값 → 군집성은 항상 -1과 +1 사이의 값을 갖음. 보통 군집성이 0.3~0.7 정도의 값을 가질 때, 그래프에 존재하는 통계적으로 유의미한 군집들을 찾아냈다고 할 수 있음
• 대표적은 군집 탐색 알고리즘은 Girvan-Newman 알고리즘, Louvain 알고리즘

 

 

3. Girvan-Newman 알고리즘

• 하향식(top-down) 군집 탐색 알고리즘
• 전체 그래프에서 탐색 시작 → 군집들이 서로 분리되도록, 다리 역할의 간선을 순차적으로 제거함
• 다리 역할의 간선 찾는 법: 매개 중심성(Betweenness Centrality) 사용
• 간선의 제거 정도에 따라서 다른 입도(Granularity)의 군집 구조가 나타남
• 간선을 어느 정도 제거하는 것이 좋을까?
  • 군집성(Modularity)가 기준. 즉, 군집성이 최대가 되는 지점까지 간선 제거

 

 

4. Louvain 알고리즘

• 상향식(bottom-up) 군집 탐색 알고리즘
• 개별 정점에서 시작해서 점점 큰 군집 형성
• 이번에도 군집을 합치는 정도는 군집성이 기준

 

 

5. 중첩이 있는 군집 탐색

• 각 정점은 여러 개의 군집에 속할 수 있음
• 각 군집 A에 대하여 같은 군집에 속하는 두 정점은 P_A 확률로 간선으로 직접 연결됨
• 두 정점이 여러 군집에 동시에 속할 경우 간선 연결 확률은 독립적. 예를 들어 두 정점이 군집 A와 B에 동시에 속할 경우 두 정점이 간선으로 직접 연결될 확률은 1 - (1 - P_A)(1 - P_B)
• 어느 군집에도 함께 속하지 않는 두 정점은 낮은 확률 e로 직접 연결됨
• 중첩 군집 모형이 주어지면, 주어진 그래프의 확률을 계산할 수 있음
  • 그래프의 확률: 그래프가 ~하게 그려질 확률
  • 그래프의 확률 = (그래프의 각 간선의 두 정점이 모형에 의해 직접 연결될 확률) * (그래프에서 직접 연결되지 않은 각 정점 쌍이 모형에 의해 직접 연결되지 않을 확률)
  • 중첩 군집 모형은 하나가 아니라 다양하게 제시될 수 있으므로 각 모형마다 간선이 존재할 확률이 달라지기 때문에 → '모형에 의해'
• 중첩 군집 탐색은 주어진 그래프의 확률을 최대화하는 중첩 군집 모형을 찾는 과정
  • 최우도 추정치(Maximum Likelihood Estimate)를 찾는 과정

 

 

6. 완화된 중첩 군집 모형

• 중첩 군집 탐색을 용이하게 하기 위하여 완화된 중첩 군집 모형을 사용함
• 각 정점이 각 군집에 속해 있는 정도를 실숫값으로 표현
• 즉, 기존 모형에서는 각 정점이 각 군집에 속하거나 속하지 않거나 둘 중 하나였는데, 중간 상태를 표현할 수 있게 됨

• 최적화 관점에서는, 모형의 매개변수들이 실수 값을 가지기 때문에 경사하강법 등을 사용하여 모형을 탐색할 수 있는 장점이 있음

 

 

7. 추천 시스템

• 내용 기반 추천시스템(Content-based)
  • 각 사용자가 구매/만족했던 상품과 유사한 것 추천
• 협업 필터링 추천시스템
  • 유사한 취향의 사용자들이 선호한 상품 추천
  • 취향의 유사성은 상관계수(Correlation Coefficient)를 통해 측정함
  • 구체적으로 취향의 유사도를 가중치로 사용한 평점의 가중 평균을 통해 평점을 추정함

 

 

8. 추천 시스템의 평가

• 평균 제곱근 오차(RSME), 평균 제곱 오차(MSE)가 많이 쓰임