[4기 강남 안태형] 쉽게 사용할 수 있는 예측 알고리즘 2

예측 알고리즘 - SPAR

안녕하세요? ^^

강남 멤버십 21-2기 안태형입니다.

예측 알고리즘 두 번째 시간으로 SPAR에 대해서 소개하도록 하겠습니다.

 

1. SPAR(Sparse Periodic Auto Regression)

SPAR은 마이크로소프트의 MSN 메신저 사용자들의 Login Rate를 예측하기 위하여 제안되었다. SPAR은 MSN 메신저 Login 시 네트워크 등의 문제로 인해서 Login이 실패하여 사용자들이 재로그인을 시도하여 Login Rate이 급격하게 상승하는 Spike를 무시하기 위하여 과거 주기의 값을 이용하였다. 알고리즘의 효율성에 대한 증명에 관해서는 [1]에 증명되어 있다.

SPAR은 자기회귀 모델(Auto-Regression Model)을 반영하여 매 주기 T마다의 값은 관계가 있다는 가정 하에 과거 주기 T 동안 n개의 값을 이용하여 주기적인 예측을 하는 부분과 예측하는 데이터는 직전의 과거 값과 관련이 있다는 것을 의미하는 지역 적응(Local Adjustment) 부분 m개의 값에 각각 계수 ak, bj를 이용하여 시간 t에서의 예측 값 y(t)를 다음과 같이 구한다[1].

 

 

SPAR(4,2)는 T=1주로서 지난 4주 동안 과거 T 주기 4개의 값과 최근 관찰된 2개의 값을 이용하는 것을 말한다. 따라서 SPAR는 예측 직전의 과거 값만을 사용하는 것이 아니라 과거 주기의 값도 사용하여 예측을 하기 때문에 정확도가 높은 것을 볼 수 있다. [2]에서도 정확성 측면에서는 FUSD보다 SPAR이 높은 것을 나타낸다. 그림 1은 MSN 메신저 1주일 동안의 Login Rate를 예측한 것을 나타낸 것이다. 재로그인으로 인하여 급격하게 Login Rate가 상승하는 Spike부분을 무시하고 실제 Login Rate 예측이 옳은 것을 볼 수 있다.

그림 1는 구글 클러스터 데이터를 기반으로 SPAR을 이용하여 서비스 발생량을 예측한 것을 나타낸다. 그림 2를 보면 SPAR은 과거주기의 값을 이용하기 때문에 값의 급격한 상승에 잘 적응하지 못하고 예측되는 값이 실제 값들의 중간을 지나는 것을 볼 수 있다. 또한 SPAR을 사용하기 위해서는 사전에 계수 ak, bj를 결정하기 위한 훈련(Training)을 필요로 하고 과거 주기의 값이 없는 초반에는 예측을 못한다.

       Figure 1. 1주일 동안의 Login Rates[1]

     Figure 2. 구글 클러스터 데이터 기반의 제안하는 SPAR을 이용한 서비스 발생량 예측

 

[1] G. Chen, H. Wenbo, J. Liu, S. Nath, L. Rigas, L. Xiao, and F. Zhao, “Energy-aware server provisioning and load dispatching for connection-intensive internet services,” in Proc. USENIX Symposium on NSDI, pp.337-350, Berkeley, USA, April, 2008.

[2] Z. Xiao, W. Song, Q. Chen, "Dynamic resource allocation using virtual machines for cloud computing environment," IEEE Transactions on Parallel and Distributed Systems, vol.24, no.6, pp.1107-1117, June. 2013.