📋 그래프 군집 탐색
📌 군집 구조와 군집 탐색 문제
- 군집이란 다음 조건들을 만족하는 정점들의 집합을 말한다
(1) 집합에 속하는 정점 사이에는 많은 간선이 존재한다
(2) 집합에 속하는 정점과 그렇지 않은 정점 사이에는 적은 수의 간선이 존재한다
- 실제 그래프의 군집은 사회적 무리를 의미하거나 부정 행위와 관련된 경우가 많다
- 그래프를 여러 군집으로 '잘' 나누는 문제를 군집 탐색 문제 라고한다.
📌 군집 구조의 통계적 유의성과 군집성
- 비교대상: 배치 모형
(1) 각 정점의 연결성을 보존한 상태에서
(2) 간선들을 무작위로 재배치하여 얻은 그래프
- 군집 탐색의 성공여부 판단을 위해 군집성이 사용된다.
군집성은 각 군집마다 (그래프에서 군집의 내부 간선수 - 배치 모형에서 군집 내부간선 수 기댓값)을 합한 값
📌 군집 탐색 알고리즘
- Girvan-Newman 알고리즘
탑다운 방식으로 간선을 하나씩 순차적으로 제거해 가면서 군집된 정도를 체크
다리 역할을 하는 간선을 찾기 위해 간선이 정점간의 최단 경로에 놓이는 횟수인 매개 중심성을 사용
매개 중심성이 높은 간선을 순차적으로 제거하면서 군집성을 체크
- Louvain 알고리즘
바텀업 방식으로 크기가 1인 개별정점으로 부터 시작해서 각 정점이 기존 혹은 새로운 군집으로 이동 했을 때 군집성이 최대화 되도록 군집 결정
각 군집을 하나의 정점으로 보고 다시 같은 과정 정점이 하나 남을때 까지 수행
📌 중첩이 있는 군집 탐색
- 실제 그래프는 군집들이 중첩되어 있는 경우가 많다
📋 추천 시스템
📌 내용 기반 추천 시스템
- 내용기반 추천은 각 사용자가 구매/만족 했던 상품과 유사한 것을 추천하는 방법
- 사용자 프로필 벡터와 상품 프로필 벡터의 코사인 유사도가 높은 상품 추천
📌 협업 필터링 추천 시스템
- 상관 계수를 통해서 취향이 유사한 사용자를 찾는다
- 취향의 유사도룰 가중 평균으로 사용하여 상품에 대한 평점을 추정한다
📌 추천 시스템의 평가
- 데이터를 훈련 데이터와 평가 데이터로 나눈다
- 추정한 평점과 실제 평가 데이터를 비교하여 오차를 측정한다
