[Recommender System] - Spark로 연관 규칙(Association Rule) 구현하기

딥 러닝, 하이브리드 CF, FM 등의 최신 추천 알고리즘이 유행이지만, 여전히 적지 않은 곳에서는 가장 기초적인 알고리즘을 잘 활용하고 있다. 그 중 하나가 바로 연관 규칙(Association Rule)이다. 이번 글에서는 추천 시스템에서 사용되는 가장 기초적이면서도 활용성이 높은 알고리즘인 Association Rule에 대해 설명하고, 이를 두 가지 버전의 Spark (PySpark, Scala) 언어로 구현하는 예제를 설명하도록 하겠다.

---

1. 연관 규칙의 개념

연관 규칙, 혹은 연관성 규칙(Association Rules)은 어떤 항목이 어떤 항목을 동반하여 등장하는 지에 대한 연구이다. 주로 유통 거래 데이터 구매항목들 사이의 연관성에 대해 규칙을 추론하였기 때문에, 장바구니 분석이라고 불리기도 한다.

연관 규칙은 복잡한 알고리즘 없이도 아주 간단하고 명료하지만, 효과적인 결과를 얻어 낼 수 있는 알고리즘이다. 연관 규칙을 통해 우리는 '만약 A가 구매되었다면, B를 구매할 것이다' 라는 아주 명쾌하고 빠르게 해결 가능한 문제 정의가 가능하다.

거래 번호	구매 물품
1	꽃, 카드, 음료수
2	인형, 꽃, 풍선, 사탕
3	카드, 사탕, 꽃
4	인형, 풍선, 음료수
5	꽃, 카드, 음료수

위와 같은 거래 데이터가 있다고 가정하자. 이러한 데이터는 유통 데이터에서 가장 기초적인 데이터라고 할 수 있다.

이 데이터에 연관 규칙을 적용해보자. if-then 형식으로 항목들 사이의 모든 가능한 규칙들을 구한다. 이때 if 조건은 선행절, then 조건은 후행절이다. 연관 규칙에서 선행과 후행은 공통원소가 없는 항목들의 집합이다. 이제 아래의 연관 규칙을 생각해보자. 

1. IF {꽃, 음료수} => THEN {카드}

2. IF {꽃, 카드} => THEN {음료수}

이 두 가지 연관규칙은 같은 동일한 경우의 수를 공유한다. 여기서 생각을 확장해본다면, 만약 꽃이나 음료수와 같은 상품이 모든 구매 물품 목록에 등장하면서 선행과 후행의 기준이 없다면 이러한 연관 규칙은 큰 의미를 가질 수 없을 것이다. 그래서 중요한 것이 순서, 선행과 후행. 그리고 조건부 확률의 개념이다.

---

2. 연관 규칙의 지표

연관 규칙의 지표는 크게 지지도(Support), 신뢰도(Confidence), 향상도(Lift) 3가지 정도가 있다. 이외에도 응용하기 나름인 몇 가지의 추가적인 지표가 있지만, 일반적으로 사용하는 3가지에 대해서만 다루도록 하겠다. 설명상의 편의를 위해, 연관 규칙의 전제는 모두 {IF A THEN B}의 조건으로 설명할 것이다.

- 지지도(Support)

Support (카드, 꽃) = 3/5 = 0.6

Support (사탕) = 2/5 = 0.4

지지도는 해당 셋({A,B}의 Set)의 빈도가 전체 Transaction 데이터 중에서 얼마의 비율을 차지하는지, 둘이 얼마나 많이 같이 등장했는지를 설명하는 수치이다. 그래서 {Set을 포함하는 거래 / 전체 거래}의 간단한 수식으로써 계산이 가능하다. 얼마나 많은 데이터가 해당 규칙의 타당성을 지지하는지를 의미한다.

- 신뢰도(Confidence)

confidence (꽃 -> 카드) = 0.6/0.8 = 0.75

confidence (카드 -> 꽃) = 0.6/0.6 = 1 

A와 B 두개의 정보만을 바탕으로 A가 출현할때의 B 라는 식으로 지엽적인 부분에 관심이 있는 수치라고 할 수 있다. 신뢰도의 경우, 조건부나 결론부 중 한 군데라도 지지도의 수치가 크게 나타나면 쓸데없는 발견이 되기도 한다. 신뢰도는 A를 포함하는 거래 중 B가 함께 포함되어 있는 거래의 비율을 의미하기 때문이다. 따라서 이 때의 규칙은 순서가 매우 중요해진다.

- 향상도(Lift) 

전체 정보를 참고하면서도 A와 B의 상관성을 보는 지표이다. 즉 규칙의 신뢰도와 기준값을 비교하는 것이다. 위의 두 가지 수치의 장점만을 하이브리드하게 사용했다고도 볼 수 있다. 주로 같은 조건일때 다르게 판단하는 기준이 되는 수치이므로, 만약 상품의 추천 랭킹 등에 활용된다면 후순위 정렬 혹은 백업 알고리즘의 기준으로써 폭넓게 사용되는 수치이다. 더 쉽게는 아래와 같은 수식으로 나타낼 수 있다.

lift(A->B) = support (A & B) / ( support (A) * support (B) )

---

3. 연관 규칙의 해석과 응용

연관 규칙은 결과를 해석할 때, 다양한 측정도구를 활용하지만 가장 대표적으로 사용되는 것은 지지도와 향상도이다. 지지도의 경우 전체 데이터의 관점에서 해당 Set의 영향력을 나타내는 수치이고, 측정하기 매우 쉽고 설명이 용이하다는 장점이 있지만 반대로 데이터의 크기가 크지 않을 경우 설득력이 없다는 단점을 가지고 있다. 또한 순서정보를 제대로 나타내지 못한다.

향상도는 선행과 후행의 관계가 얼마나 효율적인지에 대한 신뢰도를 표현하기 때문에, 훨씬 설명력이 강한 수치이다. 하지만 Set을 구성하는 상품들의 지지도가 낮다면, 효율성은 높지만 믿을 수 없는 수치가 될 수도 있기 때문에 데이터의 크기와 지지도를 동시에 고려해야만 한다.

연관 규칙과 관련된 성능적인 이슈도 있다. 상품 데이터의 경우 매우 큰 사이즈의 데이터이기 때문에, 지지도를 구하거나 하는 등의 연산량은 매우 커질 염려가 있다. 따라서 이를 효율적으로 계산하기 위한 알고리즘인 Apriori 알고리즘이 개발되었다. 이 Apriori 알고리즘은, 일정 수치 이하의 상품은 cutoff를 하고 단계적으로 계산을 진행한다는 것이 아이디어이다. 자세한 내용은 잘 설명된 블로그의 링크로 첨부하겠다.

---

4. Spark로 간단한 연관규칙 구현하기

Spark를 이용하여 연관규칙을 비롯한 머신 러닝 알고리즘을 작성하는 방법으로는 아래의 두 가지를 권한다. 필자는 PySpark를 이용하여 간단한 연관규칙을 구현하는 간단한 코드를 작성해보았다. 실행가능한 코드에서 feature, configure 정보등을 제거하였으므로, 일종의 수도코드에 가깝다.

Github 링크

- PySpark

PySpark은 파이썬에 익숙한 데이터 분석가들에게 고수준의 ML 라이브러리를 활용하여 쉽게 코딩이 가능하도록 되어있다. 실제 서비스 상에 사용하기에는 무리가 없지만, 일반적으로 Scala 언어로 작성된 Spark 보다 다소 느리다. 또한 API 업데이트도 스칼라 언어보다 느린 편이다. 그래서 나는 작업할때 PySpark으로 간단한 오프라인 테스트나 프로토타이핑을 하는 편이고, 이를 다시 Scala 언어로 포팅한다. PySpark으로 코드를 작성하면 Dataset 자료구조를 사용하는 Scala 언어로 포팅하기에 매우 쉽기 때문.

PySpark을 이용하여 연관규칙을 구현하는 방법은 두 가지가 있다. 하나는 Spark ML을 활용하는 것이고, 하나는 직접 구현하는 것이다. 연관 규칙은 간단한 조건부확률의 계산이기 때문에 구현이 어렵지 않다. 그래서 두 가지 버전, ML 라이브러리를 활용하여 apriori rule을 적용하는 버전과 apriori rule을 적용하지 않는 버전을 둘 다 해보기를 권한다. (ML 활용을 잘못 하였었는지, 이상하게 속도는 후자가 빨랐다)

- Scala

Scala는 현재 Hadoop, Spark ecosystem에서 State of the art의 지위를 차지하고 있는 언어이다. 플랫폼 자체가 JVM으로 구성되어있기 때문에 JVM으로 실행되는 Java, Scala 언어를 기준으로 Spark의 ML 라이브러리가 개발되고 있다. 데이터 분석가들에게는 대화형 프로그래밍 언어나 함수형 언어와 같은 형식이 익숙하기 때문에, Java보다는 인터렉티브 shell이 지원되는 Scala가 각광받고 있다. 같은 코드를 파이썬으로 돌릴 때와 스칼라로 돌릴 때의 성능 차이는 언어 문제때문에 꽤나 큰 편이다.