그래프 임베딩을 사용한 효과적 상품 추천 방법

Ⅰ. 서 론

최근의 온라인상의 구매자가 인지하지 못하는 사이에, 거의 모든 웹 페이지의 한 부분에서 추천 광고나 온라인 상점의 상품 권유와 같은 추천 시스템을 거의 매일 접하게 된다. 갈수록 증가하는 다양한 상품과 서비스에 대한 정보 과부하 문제를 해결할 수 있는 방법으로 추천 시스템은 지난 수십 년 동안 많은 주목을 받았다. 2006년과 2009년 사이의 넷플릭스 경진대회(Netflix Prize)와 추천 시스템(Recommender Systems) 컨퍼런스에서 조직 된 몇 가지 연구 과제는 기계 학습 및 데이터 마이닝 연구 분야의 수많은 연구자들로부터 주목 받았다[22].

추천 시스템은 정보 자원과 구매자를 조화하는 중요한 역할을 담당한다[1]. 지난 수년간 협업 필터링 기법, 내용 기반 기법, 하이브리드 기법 등 다양한 추천 알고리즘이 개발되었다[2]. 협업 필터링 방법은 구매자의 과거 행동뿐만 아니라 다른 유사한 구매자의 구매 의사 결정을 기반으로 모델링 한다. 내용 기반 방법은 비슷한 기능을 가진 새로운 상품을 추천하기 위해 상품의 중요한 기능 집합을 추출해서 모델링한다. 이 두 가지 유형의 방법을 혼합하는 방법을 하이브리드 방법이라 한다.

이러한 추천 방법은 어느 정도 효과적이지만, 이러한 접근법은 다음과 같은 문제가 있다. 기존 추천 알고리즘이 유사도 계산의 정확성을 높이는데 한계가 있다. 예를 들어, 고전적인 상품 기반 KNN 추천 알고리즘의 효율성은 KNN 그래프의 행렬 인수 분해는 시간과 비용이 높아 제한적인 유사도를 계산한다[3]. 따라서 추천의 성능을 높이기 위한 유사도 계산에 보다 효율적이고 성능 높은 방법을 확보하는 것은 중요한 문제이다.

본 연구는 전통적인 협업 필터링 기반의 상품추천의 한계를 극복하고자 최근 활발한 연구가 이루어지는 딥 러닝 기반의 그래프 임베딩 방법을 적용하여 보다 정확도 높고 효과적인 상품추천 방안을 제시하는 것을 목적으로 한다. 본 연구는 다음과 같은 연구 문제(Research Question)를 다룬다.

RQ: 상품-상품 네트워크에 대해 그래프 임베딩 기반의 상품 추천이 협업 필터링 방법의 상품 추천보다 성과가 좋을 것이다.

Ⅱ. 관련 연구

2-1 그래프 임베딩

그래프 임베딩의 목적은 고차원의 데이터 셋을 저차원의 벡터 공간에 임베딩하여 표현하는 것이다[4]. 그래프 임베딩과 관련한 많은 연구들이 수행되었으며, 각각의 접근법들은 서로 다른 특징과 효과를 가지고 있다[5]. 본 절에서는 전통적으로 연구되던 그래프 임베딩 방법부터 최근의 그래프 임베딩 방법까지를 고찰한다.

전통적인 그래프 임베딩 방법(Classical Graph Embedding Methods)은 원래 차원 축소(dimension reduction) 기법으로 연구가 진행되었다. 그래프는 일반적으로 이미지 데이터와 같은 데이터 세트로 표시된 자질(Feature)로부터 생성된다. 그래프 임베딩의 대표적인 방법인 Isomap은 네트워크 상의 노드 i와 j에 대한 연결 그래프 생성하고[6], 다차원 스케일링(MDS; Multi-Dimensional Scaling) 방법을 적용하여 노드 i에 대한 좌표 벡터 u_i를 얻는다. Isomap은 저차원 공간에 노드 쌍의 최단 거리를 거의 정확하게 보존하는 노드 i의 표현을 학습한다. Isomap은 노드 쌍의 최단 경로의 계산으로 인한 복잡성의 증가하는 것이 문제점으로 지적된다. 이를 극복하고자, 넓게 분리 된 항목 사이의 쌍 방향 거리를 추정 할 필요가 없도록 LLE(Locally linear embedding) 방법이 제안되었다[7]. LLE는 각 노드와 그 이웃이 여러 겹의 로컬 선형 경로 위에 있거나 그 근처에 놓여 있다고 가정한다. 부분적인 기하학적 구조를 특성화하도록 재구성 하고, 저차원 공간에서 국소 선형 복원(locally linear reconstruction)을 기반으로 한 이웃 보존 매핑(neighborhood-preserving mapping)을 구성한다. 라플라시안 아이젠맵(LE; Laplacian eigenmaps)은 KNN을 사용하여 그래프를 구성하고[8], 히트 커널(Heat Kernel)을 사용하여 그래프에서 노드 i 및 j의 가중치 W_ij를 선택한다[9]. 또 다른 방법으로는 비선형 LE의 선형 근사법인 지역 보존 표현(LPP; locality preserving projection)이 제안되었다[10]. 이러한 그래프 임베딩 방법은 주로 그래프 재구성(graph reconstruction)을 목표로 한다. 또한, 그래프 임베딩은 대부분 간선 표현에 의해 인코딩 된 노드들 사이의 인접도가 원래의 자질 공간에서 잘 정의 된 자질 표현 데이터 세트로 구성된 그래프에서 동작한다. 네트워크 재구성을 위해 학습 된 그래프 임베딩 공간은 네트워크 추론(network inference)에 반드시 좋은 것은 아니다.

그래프 임베딩에 관한 최근 연구동향은 네트워크 구조를 보존하고 네트워크의 속성을 임베딩 공간에 저장하는 것이다. 네트워크 구조는 1차 구조(first-order structure)와 2차 구조(second-order structure) 및 커뮤니티 구조(community structure)와 같은 고차원 구조(higher-order structure)가 포함된다. 네트워크 구조는 서로 다른 세분성(granularities)으로 나타나는 서로 다른 그룹으로 분류 될 수 있다. 최근의 그래프 임베딩은 이러한 네트워크 구조적인 특성을 유지하는 방법들이 많이 연구되고 있다. 그래프 임베딩에서 일반적으로 구현되는 네트워크 구조는 인접 구조(neighborhood structure), 상위 노드 근접성(high-order node proximity) 및 네트워크 커뮤니티(network communities)가 포함된다. 인접 구조 및 상위 노드 근접성 관련 그래프 임베딩의 그래프 임베딩 방법들은 DeepWalk로 부터 시작 되었다. DeepWalk는 노드의 인접 구조를 보존 할 수 있는 네트워크의 노드 표현을 학습하기 위해 제안되었다[11].

DeepWalk는 짧은 무작위 걷기(Random Walk)에 나타나는 노드의 분포가 자연 언어로 된 단어의 분포와 유사하다는 것을 발견했다. 이러한 발견에 영감을 얻어 널리 사용되는 단어 표현 학습 모델 인 Skip-Gram 모델을 DeepWalk에 적용하여 노드의 표현을 학습한다[12]. 구체적으로 DeepWalk는 그림 1.과 같이 일련의 걷기 순서(Walking Sequence)를 생성하기 위해 네트워크상에서 절단된 랜덤 워크(Truncated Random Walk)를 채택한다. Skip-Gram에 따라 각 걷기 순서 s = {v1, v2, ..., vs}에 대해 Deep walk는 식(1)과 같이 걷기 순서에서 노드 v_i의 이웃 노드의 확률을 최대화하는 것을 목표로 한다.

Fig. 1.

Overview of DeepWalk[11]

$\[ {\mathrm{m}\mathrm{a}\mathrm{x}}_{\Phi }\mathrm{P}\mathrm{r}\left(\left\{{\upsilon }_{i-w},\cdots ,{\upsilon }_{i+w}\right\}\setminus {\upsilon }_i|\Phi \left({\upsilon }_i\right)\right)=\prod _{j=i-w, j\ne i}^{i+w}Pr\left({\upsilon }_j|\Phi \left({\upsilon }_i\right)\right) \]$

(1)

여기서 w는 윈도우 크기이고, Φ(v_i)는 현재의 v_i표현이며, v_{i - w}, ⋯, v_{i + w}\ v_i는 v_i와 연결된 지역 맥락 노드(local context nodes)이다. 마지막으로 계층적 소프트 맥스(hierarchical soft-max)를 사용하여 임베딩을 효율적으로 추론한다[13].

많은 네트워크 임베딩 방법은 잠재적 인 저차원 공간에서 인접 구조, 고차원 근접 및 커뮤니티 구조를 포함하여 노드의 로컬 구조를 보존하는 것을 목표로 하는 다양한 연구들이 수행되고 새로운 방법들이 제시되면서 네트워크 추론에 더 많은 관심을 기울이고 있다. 또한 최근 그래프 임베딩 방법은 주로 소셜 네트워크(social networks), 생물 네트워크(biology networks) 및 전자 상거래 네트워크(e-commerce networks)와 같이 자연스럽게 형성된 네트워크에서 적용되는 것을 목표로 한다. 하지만, 많은 그래프 임베딩 연구들은 현재까지 연구용 데이터에만 적용이 되었고, 그래프 임베딩의 효과를 실제 비즈니스에 적용하기 위한 추가적인 연구들이 필요한 시점이다.

Ⅲ. 연구 방법

3-1 실험 절차

본 연구는 기존의 협업 필터링 추천 시스템에 그래프 임베딩을 결합하여 추천의 성능을 높이는 것을 목적으로 그림 2과 같은 실험 절차로 연구한다.

- 1단계: 본 연구의 목적에 따라 실험용 데이터를 준비한다. 연구 목적을 확인할 수 있는 데이터를 Kaggle에 공개된 구매 이력 데이터¹⁾를 다운로드 받았다. 총 구매 이력 데이터는 약 3억 5천만 건으로, 실험을 위하여 무작위 추출한 구매고객 100명에 대한 2012년 11월부터 2013년 4월까지 6개월 간의 구매이력 약 4만 4천 건을 추출하였다. 재구매, 중복구매를 제외하고 데이터 셋에 포함된 상품의 고유개수는 20,945개 이다.

Fig. 2.

The block diagram of product recommendation based on graph embedding

2단계: 거래 데이터 셋에서 구매고객과 상품에 대한 구매 빈도, 구매 수량, 월 평균 구매 수량에 대한 변수를 생성한다. 생성된 데이터의 예시는 표 1, 표 2과 같다.

Table 1.

Example of quantity of product purchase data set

Table 2.

Example of Monthly average purchase quantity data set

- 3단계: 2단계의 데이터 셋은 그래프 임베딩의 입력 데이터로 사용한다. 예를 들어, 그래프 임베딩 관점에서는 구매 고객과 상품 네트워크의 간선 가중치로 볼 수 있다. 그래프 임베딩 방법은 Perozzi가 제안한 DeepWalk를 사용한다. 각 노드 당 랜덤 워크 횟수는 10회, 워크의 길이는 80회, 생성할 벡터 차원의 수는 128차원으로 설정한다.

- 4단계: 생성된 그래프 임베딩된 자질로부터 구매고객-상품 간의 코사인 유사도를 계산하고, 협업 필터링에 입력하여 상품추천을 실행한다. 입력데이터를 7:3으로 학습 데이터 셋과 검증 셋으로 분할하고, 학습 데이터 셋으로 만들어진 추천모형으로 검증 데이터 셋에 대한 상위 10개의 상품을 추천한다. 이후 검증 데이터 셋에서 추천 성공 여부에 대한 결과를 판단한다.

Ⅳ. 연구 결과

실험의 결과는 표 3에서 표 5와 같다. 구매 빈도를 사용한 상품추천의 결과(표 3)는 그래프 임베딩 기반의 상품 추천의 F1이 4.99에서 5.44로 나타났고, 그래프 임베딩을 적용하지 않은 상품추천은 0.31에서 1.91로 나타났다. 두 방법 간의 추천 정확도 차이는 3.18에서 5.14가 나오고 있으며, 두 방법 간의 유의성 차이가 유의한 것(p=<.0001)으로 나타났다.

Table 3.

Compare product recommendations using purchase frequency

Table 4.

Product Recommendations Using Purchased Quantities

Table 5.

Product Recommendations Using Average Monthly Purchase Quantities

구매 수량을 사용한 상품 추천의 결과(표 4)는 그래프 임베딩을 사용하지 않은 상품 추천의 F1이 0.03에서 0.83이고, 그래프 임베딩을 사용한 상품 추천이 0.03에서 1을 보였다. 전반적으로 그래프 임베딩을 사용한 상품 추천의 성과가 약간 더 높지만 추천 상품의 수가 두 개인 경우는 그래프 임베딩을 사용한 추천이 더 낮았다. 두 방법 간의 정확도 차이는 –0.04에서 0.15로 나타났지만 그래프 임베딩을 사용한 상품 추천은 추천 상품의 수가 증가할수록 추천의 정확도가 증가하는 것을 보인다. 두 방법 간 추천 정확도의 유의하지 않은 것으로 나타났다(p=0.667).

월 평균 구매 수량을 사용한 상품 추천 결과는 표 5와 같다. 그래프 임베딩을 사용하지 않은 상품 추천의 F1이 0.03에서 0.44이고, 그래프 임베딩을 사용한 상품 추천이 0.07에서 0.54를 보였다. 전반적으로 그래프 임베딩을 사용한 상품 추천의 성과가 약간 더 높지만 추천 상품의 수가 세 개인 경우는 그래프 임베딩을 사용한 추천이 더 낮았다. 두 방법 간의 정확도 차이는 –0.01에서 0.14로 나타났지만, 그래프 임베딩을 사용한 상품 추천은 추천 상품의 수가 증가할수록 추천의 정확도를 평가하는 지표인 F1이 증가하는 패턴을 보인다. 두 방법 간 추천 정확도의 차이는 유의하지 않다(p=0.374).

Ⅴ. 결 론

본 연구의 결과 그래프 임베딩을 사용한 상품 추천은 전반적으로 기존의 그래프 임베딩을 사용하지 않은 상품 추천에 비해 약간 우수하거나 뚜렷하게 높은 추천 성능을 나타낸다. 특히, 구매 빈도를 사용한 그래프 임베딩 기반의 상품 추천은 이전의 상품 추천에 비해 상대적으로 유의한 상품 추천 정확도를 보여 그래프 임베딩 기반의 상품 추천이 효과적인 성과를 나타내는 것을 확인 하였다. 이것은 구매고객-상품간의 관계 매트릭스를 그래프 임베딩이 더 효과적으로 자질화하기 때문이다.

본 연구의 의의는 다음과 같다. 첫째, 최근 컴퓨터 공학 분야에서 활발한 연구가 이루어지는 그래프 임베딩을 경영학 관점에서 상품 추천과 연계해 그 효과를 실증하였다. 일부의 연구가 영화 추천 등에 활용이 되었지만, 일반적인 소매 상품 추천에 그래프 임베딩을 적용한 연구는 거의 찾아볼 수 없다. 둘째, 단순 차원 축소를 목적으로 하는 이전의 그래프 임베딩 방법에 비해 그래프의 노드나 간선을 추론하는 것에 목적을 둔 DeepWalk를 상품 추천에 적용하였다. 연구를 통해 그래프를 한정된 벡터 공간에 임베딩 할 때 더 높은 성능과 효과를 보였다. 셋째, 모든 데이터는 그래프 형태로 표현이 가능하고 이를 활용한 연구는 네크워크를 처리하는 시간의 한계로 인해 제한적인 연구가 수행되었다. 하지만, 본 연구에서 제안된 그래프 임베딩 방법으로 그래프를 제한된 벡터 공간에 표현하게 되어 보다 큰 빅 데이터를 활용한 연구에 대한 방향을 제시하였다.

또한, 실무적으로 본 연구가 제안한 방법을 기반으로 보다 효과적이고 정확도 높은 상품 추천으로 기업의 성과를 향상 시킬 수 있다. 다양한 상품들이 거래되는 온라인 마켓에서 보다 정확한 상품 추천을 하는 것은 중요한 문제이고 이를 극복하기 위한 새로운 방법을 본 연구에서 제시하였다.

본 연구의 한계는 다음과 같다. 첫째, 구매자 100명에 대한 2만 여개의 상품 데이터로 한정하여 실험을 수행하였다. 추후 연구를 통해 보다 많은 구매자와 상품이 포함된 빅 데이터를 실험해 제안된 방법의 성능을 측정해야 한다. 둘째, 보다 다양한 그래프 임베딩 방법을 사용하여 보다 성능 높은 상품 추천 방법을 찾아야 한다. 최근의 연구는 DeepWalk외에도 Node2vec, LINE등의 다양한 그래프 임베딩 기법들이 제안되고 있다. 이러한 그래프 임베딩 방법들이 상품추천, 고객이탈 등의 다양한 경영 문제에 어울리도록 하는 연구가 필요하다. 셋째, 구매고객-상품-유통사-제조사로 이어지는 네트워크에 대한 연구가 필요하다. 이러한 네트워크는 네트워크의 노드가 서로 다른 속성을 가지는 이질적 네트워크로 분석을 위한 새로운 방법이 필요하다.

Acknowledgments

이 성과는 2017년도 정부(미래창조과학부)의 재원으로 한국연구재단의 지원을 받아 수행된 연구임 (No. 2017R1A2B4010956).

References

• Deshpande, M., and Karypis, G., "Item-Based Top- N Recommendation Algorithms,", ACM Transactions on Information Systems, 22(1), p143-177, (2004). [https://doi.org/10.1145/963770.963776]
• Bobadilla, J., Ortega, F., Hernando, A., and Gutiérrez, A., "Recommender Systems Survey,", Knowledge-Based Systems, 46, p109-132, (2013). [https://doi.org/10.1016/j.knosys.2013.03.012]
• Rendle, S., and Schmidt-Thieme, L., "Pairwise Interaction Tensor Factorization for Personalized Tag Recommendation,", in Proceedings of the Third ACM International Conference on Web Search and Data Mining, New York, USA: ACM, p81-90, (2010). [https://doi.org/10.1145/1718487.1718498]
• Yan, S., Xu, D., Zhang, B., Zhang, H. j., Yang, Q., and Lin, S., 2007. "Graph Embedding and Extensions: A General Framework for Dimensionality Reduction,", IEEE Transactions on Pattern Analysis and Machine Intelligence, 29(1), p40-51, (2007).
• Fu, Y., and Ma, Y., "Graph embedding for pattern analysis", Springer Science & Business Media, (2012).
• Tenenbaum, J. B., Silva, V. de, and Langford, J. C., "A Global Geometric Framework for Nonlinear Dimensionality Reduction", American Association for the Advancement of Science, p2319-2323, (2000).
• Roweis, S. T., and Saul, L. K., "Nonlinear Dimensionality Reduction by Locally Linear Embedding", American Association for the Advancement of Science, p2323-2326, (2000).
• Belkin, M., and Niyogi, P., "Laplacian Eigenmaps and Spectral Techniques for Embedding and Clustering," in Advances in Neural Information Processing Systems 14, MIT Press, p585-591, (2002).
• Berline, N., Getzler, E., and Vergne, M., "Heat kernels and Dirac operators", Springer Science & Business Media, (2003).
• He, X., and Niyogi, P., "Locality Preserving Projections," in Advances in Neural Information Processing Systems 16, MIT Press, p153-160, (2004).
• Perozzi, B., Al-Rfou, R., and Skiena, S., "DeepWalk: Online Learning of Social Representations,", in Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, USA: ACM, p701-710, (2014).
• Mikolov, T., Chen, K., Corrado, G., and Dean, J., "Efficient Estimation of Word Representations in Vector Space", In Proceedings of Workshop at ICLR, p1-12, (2013).
• Mikolov, T., Sutskever, I., Chen, K., Corrado, G. S., & Dean, J., "Distributed representations of words and phrases and their compositionality", In Advances in neural information processing systems, p3111-3119, (2013).
• Goldberg, D., Nichols, D., Oki, B. M., and Terry, D., "Using Collaborative Filtering to Weave an Information Tapestry," Commun. ACM, New York, NY, USA : ACM, p61-70, (1992).
• Kohavi, R., and Provost, F., (2001), "Applications of Data Mining to Electronic Commerce,", Data Mining and Knowledge Discovery, 5(1–2), p5-10.
• Bobadilla, J., Ortega, F., Hernando, A., and Gutiérrez, A., "Recommender Systems Survey,", Knowledge-Based Systems, 46, p109-132, (2013). [https://doi.org/10.1016/j.knosys.2013.03.012]
• Burke, R., "Hybrid Recommender Systems: Survey and Experiments,", User Modeling and User-Adapted Interaction, 12(4), p331-370, (2002).
• Burke, R., "Evaluating the Dynamic Properties of Recommendation Algorithms,", In Proceedings of the Fourth ACM Conference on Recommender Systems, New York, USA: ACM, p225-228, (2010). [https://doi.org/10.1145/1864708.1864753]
• Pazzani, M. J., and Billsus, D., "Content-based recommendation systems", In the adaptive web, p325-341, Springer, Berlin, Heidelberg, (2007). [https://doi.org/10.1007/978-3-540-72079-9_10]
• Schafer, J. B., Konstan, J. A., & Riedl, J., "E-commerce recommendation applications", Data mining and knowledge discovery, 5(1-2), p115-153, (2001).
• Hofmann, T., "Collaborative Filtering via Gaussian Probabilistic Latent Semantic Analysis,", in Proceedings of the 26th Annual International ACM SIGIR Conference on Research and Development in Informaion Retrieval, New York, USA: ACM, p259-266, (2003). [https://doi.org/10.1145/860435.860483]
• Jeong, S. Y., Kim, H. J., "A Recommender System Using Factorization Machine.", Journal of Digital Contents Society, 18(4), p707-712, (2017).