[Day 23] Graph - 군집 & 군집 탐색 알고리즘 & 추천 시스템

📍 군집(Comuunity)

  - 다음 조건을 만족하는 정점들의 집합

    1. 집합에 속하는 정점 사이에는 많은 간선이 존재

    2. 집합에 속하는 정점과 그렇지 않은 정점 사이에는 적은 간선이 존재

 

  - 온라인 소셜 네트워크의 군집은 사회적 무리(Social Circle)을 의미하는 경우가 많음

 

  - 뉴런간 연결 그래프에서는 군집들이 뇌의 기능적 구성 단위를 의미

 

  🔥 그래프를 여러 군집으로 '잘' 나누는 문제를 군집 탐색(Community Detection)문제라고 함

 

📍 군집 탐색

  🔥 배치 모형(Configuration Model)

    - 각 정점의 연결성(Degree)을 보존한 상태에서 간선들을 무작위로 재배치하여 얻은 그래프

 

  🔥 군집성(Modularity)

    - 군집 탐색의 성공 여부를 판단하기 위해 사용하는 도구

    -> 무작위로 연결된 배치 모형과의 비교를 통해 통계적 유의성 판단(0.3~0.7 정도의 값일때, 유의미하다고 함)

 

  🔥 Girvan-Newman 알고리즘

    - 대표적인 하향식(Top-down) 군집 탐색 알고리즘

    - 전체 그래프에서 탐색을 시작해 군집들이 서로 분리되도록, 간선을 순차적으로 제거

    -> 간선(다리 역할)을 어떻게 찾을까?

      => 매개 중심성(Betweenness Centrality)를 사용 - 해당 간선이 정점간의 최단 경로에 놓이는 횟수

 

    - 알고리즘 순서

      1. 전체 그래프에서 시작

      2. 매개 중심성이 높은 순서로 간선을 제거하면서, 군집성 변화를 기록

      3. 군집성이 가장 커지는 상황을 복원

      4. 이때, 서로 연결된 정점들, 즉 연결 요소를 하나의 군집으로 간주

 

    - 간선의 제거 정도에 따라서 다른 입도(Granularity)의 군집 구조가 나타남

 

    - 간선을 어느정도 제거하는 것이 적합할까?

      => 군집성을 기준으로 삼음(최대가 되는 지점)

 

  🔥 Louvain 알고리즘

    - 상향식(Bottom-up) 군집 탐색 알고리즘

    - 개별 정점에서 시작해 점점 큰 군집을 형성

 

    - 과정

      1. 개별 정점으로 구성된 크기 1의 군집들로부터 시작

      2. 각 정점 u를 기존 혹은 새로운 군집으로 이동(이때, 군집성이 최대화되도록 군집을 결정)

      3. 더 이상 군집성이 증가하지 않을 때까지 2번을 반복

      4. 각 군집을 하나의 정점으로하는 군집 레벨의 그래프를 얻은 뒤 3번을 수행

      5. 한 개의 정점이 남을 때까지 4번 반복

 

  🔥 중첩이 있는 군집 모형

    - 실제 그래프의 군집들은 중첩되어 나타남

 

    - 그래프의 확률을 계산하여 그것을 최대화하는 군집 모형을 찾는 것이 중첩 군집 탐색

 

 

📍 추천 시스템

  - 종류: 아마존(상품 추천), 넷플릭스(영화 추천), 유튜브(영상 추천), 페이스북(친구 추천) 등

  - 사용자 각각이 구매할 만한 혹은 선호할 만한 상품을 추천

 

  🔥 내용 기반 추천 시스템(Content-based)

    - 각 사용자가 구매/만족했던 상품과 유사한 것을 추천하는 방법

    - 부가 정보를 활용해 유사상품을 찾음

 

    - 원리

      1. 상품 프로필(Item Profile) 수집 - 벡터(One hot encoding)으로 표현

      2. 사용자 프로필(User Profile) 구성 - 가중 평균을 계산해 벡터로 표현

      3. 사용자 프로필과 다른 상품들의 상품 프로필을 매칭 - cos 유사도 사용

      4. 사용자에게 상품을 추천

 

  🔥 협업 필터링 추천 시스템

    - 원리

      1. 사용자 x와 유사한 취향의 사용자(y)를 찾음

      2. y가 선호한 상품(z)을 찾음

      3. z를 x에게 추천

  

    - 상관 계수(Correlation Coefficient)

      -> 취향의 유사성을 측정

 

  🔥 추천 시스템 평가

    - 추정한 평점과 실제 평가 데이터를 비교(MSE - Mean Squared Error, 평균 제곱 오차 를 사용)