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

예측 알고리즘 – EWMA, FUSD

안녕하세요? ^^

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

오늘 제가 다루려는 주제는 예측 알고리즘 입니다. 현재 무수히 많은 예측 알고리즘들이 존재하지만 저는 그들 중에서 정말 간편하게 사용할 수 있는 알고리즘들을 소개하려고 합니다. 첫 번째 소개해 드리는 알고리즘은 EWMA, FUSD입니다.

 

1. EWMA(Exponentially Weighted Moving Average)

EWMA[1]는 각각의 데이터에 가중치 α를 주도록 한다. EWMA는 전 분야에서 사용되는 알고리즘으로서 다음과 같이 나타낸다.

 

E(t) = α ∗ E(t − 1) + (1 − α) ∗ O(t), 0 ≤ α ≤ 1

 

2. FUSD(Fast Up Slow Down)

FUSD[2]의 경우에는 클라우드 컴퓨팅 환경에서 CPU Load를 예측하기 위하여 고안된 알고리즘이다. [3]에서는 클라우드 컴퓨팅 환경에서 사용자의 서비스 요구를 처리할 시 Overprovisioning하여 자원 낭비가 발생하는 것 보다 Underprovisioning하게 되어 사용자의 요구를 처리하지 못하는 상황이 사용자 만족도을 떨어트릴 뿐만 아니라 해당 서비스를 다시는 사용하지 않는 다고 나타낸다.

따라서 FUSD는 EWMA가 실제 값과 예측 값 사이를 지나는 한계와 급격하게 증가하는 서비스 요구량을 반영하고 하향시에는 천천히 감소하도록 EWMA를 개선하였다. FUSD는 실제 값이 상승 구간에 있을 때는 급격한 상승을 반영하기 위하여 α에 음수를 택하도록 한다. 즉, α가 -1 ≤ α ≤ 0의 범위일 때는 다음과 같이 표현된다.

 

E(t) = −|α| ∗ E(t − 1) + (1 + |α|) ∗ O(t)

 = O(t) + |α| ∗ (O(t) − E(t − 1))

 

값이 하향구간에 있을 때는 기존의 EWMA식을 사용하도록 한다. 그림 1는 [2]에서 저자의 대학교에서 DNS Server를 기반으로 CPU load 예측을 한 것이고 그림 2은 구글 클러스터 데이터(Google Cluster Data)[5]를 기반으로 서비스 요구량을 예측한 것이다.

   Figure 1. CPU load 예측(↑ α = −0.2, ↓ α = 0.7)[2]

Figure 2. 구글 클러스터 데이터 기반의 FUSD를 이용한 서비스 요구량 예측

그림 2, 3을 보면 FUSD는 일반적으로 실제 값보다 위에 나타날 뿐만 아니라 급격하게 증가하는 요구량도 만족하는 것을 볼 수 있다.

다음 시간에는 FUSD에서 비교 알고리즘을 택하고 마이크로소프트의 MSN에서 Login Rate를 예측하기 위하여 사용된 SPAR[4]에 대해서 소개하도록 하겠습니다.

 

[1] http://en.wikipedia.org/wiki/EWMA_chart

[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.

[3] M. Armbrust, A. Fox, R. Griffith, A.D. Joseph, R. Katz, A. Konwinski, G. Lee, D. Patterson, A. Rabkin, I. Stoica and M. Zaharia, "A view of cloud computing",  Communications of the ACM, vol.53, no.4, pp.50-58, 2010.

[4] 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.

[5] Google Cluster Data, http://googleresearch.blogspot.kr/2010/01/google-cluster-data.html.