[BOOSTCAMP AI TECH] 23일차_군집 탑색 & 추천 시스템

• 강의 목록

- 그래프의 구조를 어떻게 분석할까?

- 그래프를 추천시스템에 어떻게 활용할까? (기본)

- UV 분해를 활용한 추천 시스템 구현

---

• 요약

강의

 

피어세션

 

---

• 학습정리

 

군집

• 다음 조건들을 만족하는 정점들의 집합이다.

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

 

 

군집 탐색 (Community Detection)

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

*클러스터링 = 군집화

---

 

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

 

배치 모형

• 성공적인 군집 탐색의 정의를 위해 비교하는 대상
• 그래프에서 각 정점의 연결성을 보존한 상태에서 간선들을 무작위로 재배치하여 얻은 그래프
• 배치 모형에서 임의의 두 정점 i와 j 사이에 간선이 존재할 확률은 두 정점의 연결성에 비례한다.

 

 

군집성 (Modularity)

• 군집 탐색의 성공 여부 판단을 위해 군집성이 사용된다.
• 군집 내부의 간선의 수를 그래프와 배치 모형에서 비교하는 것이다.
• 즉 배치 모형과 비교했을 때 그래프에서 군집 내부 간선의 수가 월등히 많을수록 성공한 군집 탐색이다.

 

• 군집성은 무작위로 연결된 배치 모형과의 비교를 통해 통계적 유의성을 판단한다.
• 군집성은 항상 -1~1 사이의 값을 가지며, 보통 0.3~0.7 정도의 값을 가질 때 통계적으로 유의미한 군집을 찾았다고 판단한다.

*배치 모형에서는 기댓값을 사용하는 이유 : 배치 모형은 무작위성을 띄기 때문.

 

---

군집 탐색 알고리즘

 

Girvan-Newman 알고리즘

• 대표적인 하향식 군집 탐색 알고리즘
• 전체 그래프에서 탐색을 시작한다.
• 군집들이 서로 분리되도록 군집들을 연결하는 다리 역할의 간선을 순차적으로 제거한다.

 

• 다리 역할의 간선을 찾아내는 법은 간선의 매개 중심성을 사용한다.
• 매개 중심성은 해당 간선이 정점 간의 최단 경로에 놓이는 횟수를 의미한다.

• 매개 중심성을 통해 서로 다른 군집을 연결하는 다리 역할의 간선을 찾아낼 수 있다.

 

• Gravin-Newman 알고리즘은 매개 중심성이 높은 간선을 순차적으로 제거한다.

1. 간선이 제거될 때마다 매개 중심성을 다시 계산하여 갱신한다.
2. 이렇게 매개 중심성이 높은 간선들을 순차적으로 제거하여, 모든 간선이 제거될 때까지 반복한다.
3. 그리고 그 과정에서 군집성의 변화를 전부 기록한다.
4. 이후 저장된 기록에서 군집성이 최대가 되는 상황을 복원한다.
5. 복원된 당시 연결된 정점들을 하나의 군집으로 간주한다.

 

#NetworkX에서 여러 군집 알고리즘 제공
grivan_newman(G)
greedy_modularity_communities(G)
kernighan_lin_bisection(G)

 

 

Louvian 알고리즘

• 대표적인 상향식 군집 탐색 알고리즘
• 개별 정점에서 시작해 점점 큰 군집을 형성한다.
• 군집을 합치는 기준은 역시 군집성이다.

 

• 구체적인 동작 과정은 다음과 같다.

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

 

• 동작 과정을 세부적으로 살펴보면 두 개의 과정을 반복하는데,

1. 한 노드를 원래의 군집에서 빼내 인접한 군집에 재배치 했을 때의 군집성 변화를 측정한다.
2. 측정 값을 기준으로 군집성이 가장 큰 폭으로 상승하는 군집에 노드를 할당한다.
3. 이러한 과정을 아무런 변화도 일어나지 않을 때까지 반복한다.

군집성 변화량

1. 1번 과정에서 생성된 군집을 하나의 노드로 취급한다.
2. 군집 내의 간선 가중치는 자기 회귀 상태의 간선으로, 군집간 연결된 노드들의 간선 가중치를 합쳐 하나의 간선으로 생성한다.
3. 이후 이 군집을 통해 1번 과정을 더 이상 변화가 없을 때까지 반복한다.

---

중첩이 있는 군집 탐색

 

중첩이 있는 군집 구조

• 앞서 배운 알고리즘들은 군집 간 중첩이 없다고 생각한다.
• 하지만 실제 그래프의 군집들은 중첩된 경우가 많다.
• 예를 들어 소셜 네트워크에서의 개인은 여러 사회적 역할을 수행하고, 그 결과 여러 군집에 속하게 된다.
• ex) 컴퓨터소프트웨어공학과 - 농구 동아리 - 인공지능 연구실

 

• 군집간 중첩이 있는 군집은 그래프의 확률을 통해 분류할 수 있다.
• 그래프의 확률은 다음 확률들의 곱이다.

1. 그래프의 각 간선의 두 정점이 직접 연결될 확률
2. 그래프에서 직접 연결되지 않은 각 정점 쌍이 직접 연결되지 않을 확률

• 중첩 군집 모형이 주어지면 그래프의 확률들을 계산할 수 있다.
• 중첩 군집 탐색은 주어진 그래프의 확률을 최대화하는 중첩 군집 모형을 찾는 과정이다.
• 통계 용어로는 최우도 추정치를 찾는 과정이다.

 

• 위의 추정 과정은 쉽지 않다. 이유는 각 노드가 군집에 속할지가 이산적으로 결정되기 때문. 즉 연속적인 값이 아니기 때문에 경사하강법 같은 최적화 기술들을 활용할 수 없다.
• 중첩 군집 탐색을 용이하게 하기 위해 완화된 중첩 군집 모형을 사용한다.

 

 

완화된 중첩 군집 모형

• 기존 모형에서는 각 정점이 각 군집에 속하거나 속하지 않거나 둘 중 하나로 표현했다.
• 하지만 완화된 중첩 군집 모형은 각 정점이 각 군집에 속해있는 정도를 실수값으로 표현한다.
• 즉, 0 or 1 로 무조건 둘 중 하나였는데, 이제 중간 상태를 표현할 수 있게 되었다.
• 비유하자면, 여러 무리에 속해있지만 특정 무리에 소속감을 크게 느끼고, 다른 무리에는 덜 느끼는 것.

 

• 최적화 관점에서 모형의 매개변수들이 실수 값을 가지기 때문에 경사하강법 등의 최적화 도구를 사용해 모형의 탐색이 가능하다.

 

 

---

 

추천 시스템

• 사용자의 취향을 이해하고 맞춤 상품과 콘텐츠를 제공하는 시스템.
• 즉, 추천 시스템은 사용자 각각이 구매할만한 혹은 선호할만한 상품을 추천한다.
• 아마존, 넷플릭스, 유튜브, 페이스북 등에서 이미 다양한 추천 시스템들이 사용되고 있다.

 

• 사용자별 구매 기록은 위의 예시처럼 그래프로 표현이 가능하다.
• 구매 기록이라는 암시적 선호만 있는 경우도 있고, 평점이라는 명시적 선호가 있는 경우도 있다.

 

• 추천 시스템의 핵심은 사용자별 구매를 예측하거나 선호를 추정하는 것이다.
• 그래프 관점에서 추천 시스템은 미래의 간선을 예측하는 문제 혹은 누락된 간선의 가중치를 추정하는 문제로 해석할 수 있다.

 

 

---

 

내용 기반 추천시스템 (콘텐츠 기반 필터링)

• 내용 기반 추천은 각 사용자가 구매/만족했던 상품과 유사한 것을 추천하는 방법
• 동일한 장르의 영화 추천, 동일한 감독의 영화 추천, 동일한 배우가 출연한 영화 추천 등

 

• 내용 기반 추천 시스템은 네 가지 단계로 이루어진다.

• 사용자가 선호했던 상품들의 상품 프로필을 수집한다.

1. 여기서 상품 프로필이란 해당 상품의 특성을 나열한 벡터이다.

• 수집한 상품 프로필을 바탕으로 사용자 프로필을 구성한다.

1. 사용자 프로필은 선호한 상품의 상품 프로필을 선호도를 사용하여 가중 평균하여 계산한 벡터
2. 구성한 사용자 프로필과 다른 상품들의 상품 프로필을 매칭한다.

• 사용자 프로필 벡터와 상품 프로필 벡터의 코사인 유사도를 계산한다.

1. 코사인 유사도가 높을수록 해당 사용자가 과거 선호했던 상품들과 해당 상품이 유사함을 의미한다.

• 계산한 코사인 유사도가 높은 상품들을 추천한다.

 

 

• 내용 기반 추천 시스템은 다음의 장점을 갖는다.

1. 다른 사용자의 구매 기록을 필요로 하지 않는다.
2. 독특한 취향의 사용자에게도 추천이 가능하다. => 사용자 본인에만 최적화 되어있기 때문
3. 새로 올라온 상품에 대해서도 추천이 가능하다. => 상품에 대한 평가가 아닌, 속성 정보만을 사용하기에
4. 추천의 이유를 제공할 수 있다. => 당신은 로맨스 영화에 높은 평점을 주었으니, 새로운 로맨스 영화를 추천한다.

 

• 하지만 다음의 단점 또한 존재한다.

1. 상품에 대한 부가 정보가 없는 경우에는 사용할 수 없다. => 상품의 속성 정보를 활용해야 하기 때문
2. 구매 기록이 없는 사용자는 사용할 수 없다. => 구매 기록을 바탕으로 사용자 프로필을 만들기 때문
3. 과적합으로 지나치게 협소한 추천을 할 위험이 있다. => 로맨스 영화를 연이어 봤더니 로맨스 영화만 추천

 

---

협업 필터링 추천 시스템

• 내용 기반 추천 시스템의 단점을 일부 보완한다.
• 유사한 취향의 사용자를 찾는 추천 시스템이다.
• 비슷한 취향을 가진 친구에게 추천을 받는 것으로 이해할 수 있다.

 

• 사용자-사용자 협업 필터링은 세 단계로 이루어진다.

1. 사용자와 유사한 취향의 사용자들을 찾는다.
2. 유사한 취향의 사용자들이 선호한 상품을 찾는다.
3. 해당 상품들을 사용자에게 추천한다.

 

• 사용자-사용자 협업 필터링의 핵심은 유사한 취향의 사용자를 찾는 것이다.
• 취향의 유사성은 상관 계수를 통해 측정한다.

분모는 결과를 0~1로 만들어주기 위한 정규화

• 위의 경우, 지수의 취향을 알기 위해서는 제니의 취향을 참고한다.
• 지수는 제니와 유사하고 로제와 상이하기에, 지수가 미녀와 야수를 좋아할 확률은 낮다.

 

• 구체적인 평점의 추정은 취향의 유사도를 가중치로 사용한 평점의 가중 평균을 통해 추정한다.

• 이러한 과정을 거쳐 추정한 평점이 가장 높은 상품들을 사용자에게 추천한다.

 

 

• 협업 필터링은 다음의 장단점을 갖는다.

1. 상품에 대한 부가 정보가 없어도 사용할 수 있다.
2. 충분한 수의 평점 데이터가 누적되어야 효과적이다.
3. 새 상품, 새로운 사용자에 대한 추천이 불가능하다.
4. 독특한 취향의 사용자에게 추천이 어렵다.

 

*협업 필터링 시스템은 최근접 이웃 기반과 잠재 요인 기반으로 나눌 수 있다.

*최근접 이웃 기반은 사용자 기반과 아이템 기반으로 다시 나눌 수 있다.

*잠재 요인 기반은 사용자-아이템 평점 매트릭스 속에 숨은 잠재 요인을 추출해 추천을 예측하는 기법.

---

추천 시스템의 평가

 

1. 데이터 분리

• 데이터를 훈련 데이터와 평가 데이터로 분리한다.
• 평가 데이터가 없다고 가정하고 가린 후 평점을 추정한다.
• 추정한 평점과 실제 평가 데이터를 비교하여 오차를 추정한다.

 

2. 오차 추정

• 위의 추정 평점과 실제 평점 간 데이터 비교에는 오차를 측정하는 지표가 필요하다.
• 평균 제곱 오차 (MSE)가 가장 많이 사용된다.
• 평균 제곱근 오차 (RMSE)도 많이 사용된다.
• 둘 다 값은 낮을 수록 좋다.

 

• MSE는 에러를 제곱하기에 1 미만의 에러는 더 작아지고 그 이상의 에러는 더 커지는 왜곡이 일어난다.
• RMSE는 제곱된 에러를 다시 루트로 풀어주기에 왜곡이 덜하다.

 

• 이 밖에도 다양한 지표가 사용된다.

1. 추정한 평점으로 순위를 매긴 후 실제 평점으로 매긴 순위와의 상관 계수 계산
2. 추천한 상품 중 실제 구매로 이루어진 것의 비율 측정
3. 추천의 순서 혹은 다양성까지 고려한 지표 사용

 

 

 

 

---

• 피어세션 회의 내용

 

---

• 해야할 일

 

---