Airbnb에서는 어떻게 이상치를 탐지하는가?
우리가 보는 수많은 data 속에는 대다수가 O를 가르킬때, 나혼자 X 라고 외치는 data가 있습니다. 나홀로 X를 외치는 데이터가 이상한 data인지를 파악하는 방법을 Anomaly Detection 이라고 합니다. (여기서 X라고 외치는 data는 이상치라고하는데 평균 데이터의 범위에서 많이 벗어난 아주 작은 값이나 아주 큰 값을 말합니다. )
이상치 탐지 알고리즘을 사용하는 몇가지 분야를 몇가지 살펴보면
- Industrial damage detection
제품을 제조함에있어서 불량 여부를 확인하는데 활용할 수 있고, 품질관리를 할 때 불량의 원인을 추적할 때 사용할 수 있습니다. - fraud detection
웹사이트를 이용하는 많은 사람들 중에서 이상한 행동을하는 사용자를 판별하여 문제가 있다고 생각되는 사용자를 파악할 수 있습니다.
다음과 같은 분야들이 있습니다.
실제 기업에서는 어떠한 방식으로 이상치를 탐지하는지 알아보기위해 airbnb의 data science 팀에서 사용한 방법에대해 알아보겠습니다.
이번 포스팅은 2015년 8월 18일 Jingxiao Lu이 작성한 Anomaly Detection for Airbnb’s Payment Platform에 관한 내용을 정리한것입니다.
해외 여행을 떠날때면 찾게되는 Airbnb는 전세계 2억명이 이용하며 190개의 국가에서 운영됩니다. 그렇기때문에 각 국가에서 사용되는 통화와 결제 방식이 각기 다르고 매우 다양합니다. 브라질의 경우에는 헤알(Real)이라는 통화를 사용하며, Boleto를 결제수단으로 사용하는 것처럼 Airbnb에서는 다양한 통화 (currency)와 결제 수단을 지원합니다.
그렇기때문에 많은 시스템을 관리해야하는데, 특정 통화를 처리할 수 없거나 결제가 안되는 경우가 발생할 때 어디에서 문제가 발생하는지 실시간으로 문제를 파악하기 위해서 Data science 팀은 문제가 발생했을 때 실시간으로 문제를 식별할 수 있는 이상치 탐지 시스템을 구축하였습니다.
다른 모의 데이터(mock data)의 예로 이상치를 찾기위한 아이디어와 어떤 방식으로 모델이 작동되는지 설명하겠습니다.
Motivation
첫번째 모의 데이터(mock data)로는 2020년 여름에 모니터, 키보드, 마우스 세가지 항목을 판매하는 e-commerce shop을 운영하는 사람으로 두개의 공급업체(lima와 hacker)로부터 납품받아 판매를 합니다.
납품받은 모니터의 수를 나타내주는 그래프를 보면 normal한 형태를 띄고있는 것을 볼 수 있습니다. 이상치 탐지 시스템의 주요 목적은 시계열 데이터에서 특이점을 찾는것인데 위와같은 그래프에서는 이상치라고 생각되는 곳을 볼 수 없습니다.
하지만 Fig. 2 공급업체별로 나눠서 살펴보면 Lima의 경우는 많은 양을 공급하는 주요 공급업체인데 2020년 8월 17일과 24일 사이에 납품하리라고 예상되어지는 양만큼의 수를 납품하지 못하였습니다. 그래서 이 기간동안에 2차공급업체인 Hackberry에서 Lima에서 납품하지못한만큼의 모니터를 납품받았습니다.
Fig. 1 의 그래프만봤다면 발견할 수 없었던 문제를 좀 더 deep하게 살펴보면 문제를 발견할 수 있습니다.
The model
Simple regression model
일반적인 추세를 파악하는데 도움이 되는 직관적인 방법으로는 OLS 회귀분석을 하는 것입니다.
(y : 추정량 , t : 시간 변수, I_day_i : 오늘이 i번째 요일인지 나타내는 지표 변수 , e : error term)
그러나 몇가지 단점이있습니다.
- 첫번째로 predictor는 선형이기때문에, 만약에 기하급수적인 증가한다면 trend를 모델링하는데 좋지 않습니다.
- 두번째로 시계열에서는 weekly seasonality만 보여주는 강한 가정이있기 때문에, 다른 seasonality 패턴은 다룰 수 없습니다.
- 마지막으로 더미변수가 많게되면 바람직한 유의수준을 얻기 위해서는 많은 표본이 필요합니다.
만약에 우리가 강한 monthly seasonality 나 yearly seasonality를 발견했을 때 더미변수를 추가적으로 더할 수 있는데 이렇게 모델의 형식을 수동으로 변경하게된다면 프로세스는 일반화해서 사용할 수 없게됩니다.
seasonality를 확인하는 자동화된 방법은 우리의 bias를 피하는데 도움이되고, payment 방식에 사용하려던것을 넘어서 일반화되어 사용할 수 있게됩니다.
우리의 Bias를 피해 제안되어지는 모델은 Trend 와 Seasonality를 나타내는 시계열 모델을 사용하는것입니다.
Fast Fourier Transform model
Object : seasonality 와 trend를 모델로 고려해 error term이 평균과 멀리 떨어져있는 곳을 이상치로 찾을 것입니다.
대부분의 이상치 탐지 모델에는 Trend 와 Seasonality를 나타내는 시계열 모델을 사용합니다. 시계열 모델에는 Multiplicative model (yt = Tt x St x Rt) 방식과 Additive model(yt = Tt+St+Rt) 이 있는데, Airbnb의 포스팅에서는 Additive model 방식인 Y=S+T+e 를 사용하였습니다.
(Y : Metric , S : seasonality , T : trend , e : error term)
여기서 seasonality와 trend를 감지하는 새로운 방법을 개발할 것인데, 두번째 모의 데이터(mock data)인 키보드와 마우스의 판매 데이터를 사용하여 모델이 어떻게 작동하는지 설명하겠습니다.
Fig. 3 의 그래프는 키보드와 마우스의 판매 데이터로 키보드는 2016년 9월부터 판매된 데이터이고, 마우스는 2017년 8월에 출시되어 이때부터의 판매량이 나타나있습니다.
Seasonality
Seasonality를 탐지하기위해서 고속푸리에변환(FFT)를 사용합니다.
Simple linear regression model의 경우 weekly seasonality가 있다고 가정하는데, 위에 Fig. 3를 보면 마우스에는 강한 weekly pattern이 없으므로 불필요한 더미변수를 만들게된다면 모델을 손상시킬 수 있습니다. 그렇기 때문에 일반적으로 FFT 방식을 사용하는데, 이는 Historical data가 많을 때 seasonality를 찾는데 유용한 도구로 사용됩니다.
여기서 고속 푸리에 변환(FFT)은 이산 푸리에 변환(Discrete Fourier Transform, DFT)과 그 역변환을 빠르게 수행하는 효율적인 알고리즘입니다.
그렇다면 이산 푸리에 변환(DFT)은 무엇인지 알아보면 타임시리즈 데이터인 판매량 데이터의 입력 신호를 다양한 주파수를 갖는 주기함수들의 합으로 분해하여 표현하는 것입니다. 쉽게 말해서 Fig. 5 처럼 푸리에 변환은 시간영역의 Domain을 주파수영역의 Domain으로 변환하는 것을 말합니다.
위와같은 방식으로 키보드와 마우스의 판매량 데이터에 고속 푸리에 변환(FFT)을 적용하면 Fig. 4에 오른쪽 그래프와같이 나타납니다.
MATLAB 을 사용하면 고속 푸리에 변환(FFT)한 모습을 쉽게 그릴수있는데 푸리에 스펙트럼이 원점 대칭인 주기함수이기때문에 Fig. 6 에 빨간색 추세선과같이 좌우 대칭으로 나옵니다. 그렇기때문에 여기에서는 좌우 대칭으로 되어있는 부분 중 절반을 사용합니다. 이 포스팅에서 사용된 그래프는 대칭의 좌측 부분을 사용하였기때문에 season_day라고 되어있는 x 축이 우측부터 시작합니다.
FFT로부터 발생된 키보드와 마우스의 seasonality는 아래 Fig. 7 와같이 표현됩니다.
Fig. 7 에서 보이는것처럼 키보드의 게절성의 진폭은 시간이 지나면서 커지는 반면, 마우스의 진폭은 weekly trend 의 모습과 40일 정도의 중요한 seasonality의 모습을 보여줍니다.
Trend
시계열의 trend를 파악하기위해서는 rolling median 방식을 사용합니다.
여기서 14일의 median 값을 사용였습니다. 오늘이 5월 23일이라고한다면 14일이전인 5월 9일부터의 10일, 11일부터 22일까지의 판매량 수치들의 median값을 5월 23일의 trend level로 사용합니다. 이때 mean 대신 median을 사용하는 이유로는 outlier에 대해 안정적이기때문입니다. 평소 판매량의 10배가 갑자기 팔리게된다면 mean의 경우는 trend level에 큰 영향을 미치지만, median을 사용하게된다면 영향을 미치지 않는다는점에서 median 방식을 사용하였습니다.
가정 추가
Error
이제 seasonality와 trend를 파악했으니 error term을 평가할것입니다. 시계열데이터에 이상치가있는지 결정하기위해 error term을 사용할 것입니다. Error term은 original sales data 에서 trend와 seasonality를 더한 값을 뺀 값입니다.
Fig. 9 는 키보드와 마우스 각각의 error term를 그린 그래프인데, error term 그래프에 몇몇의 spike가 있습니다. 이때, 우리는 허용할 수 있는 정도에 따라 standard deviations을 정할 수 있습니다. 여기서는 4 standard deviation을 허용할 수 있는 수준으로 정하였습니다.
4 standard deviation에서 벗어난 값들을 원래 판매데이터에 표시하게되면 fig. 10과 같이 나타날 수 있습니다.
Fig. 10 의 키보드와 마우스의 이상치 값들을 보면 처음에 판매데이터를 봤을 때 이상치라고 생각할 수 없었던 부분들이 4 standard deviation을 벗어난 이상치였다는것을 알수있습니다. 사람의 눈으로 볼 때는 이상하지 않을 수도 있지만 seasonality pattern을 사용하면 확실하게 이상치라는 것을 알수있습니다.
전반적으로 이 모델은 데이터에대한 가정을 최소화함으로써 이상치를 찾는데 효과적입니다.
Conclusion
이 포스팅은 이상치를 감지하는 모델을 만드는데 insight를 제공해줍니다. 모델링의 핵심 요소였던 가정을 가능한 작게하는 것인데, 가정을 적게하면 모델을 훨씬 더 많은 상황에서 적용할 수 있게 일반화되어 사용할 수 있습니다. 하지만, 가정을 함으로써 모델링 프로세스가 더 단순화된다면 가정을 하는 것도 나쁘지 않은 방법입니다.
※이상치(Outlier)와 같은 의미로 사용되는 용어
Outliers are also referred to as abnormalities, discordants, deviants, or anomalies in the data mining and statistics literature.
Aggarwal, Charu C. Outlier Analysis. Springer New York, 2017,
