다차원 스트림 데이터의 온라인 진 학습을 한 순차 측 모델 419

․본 연구는 2012년도 정부(산업통상자원부)의 재원으로 한국산업기술평가원

지원으로 수행된 연구이며(KEIT-10035348, mLife), 한국연구재단의 지원

(NRF-2010-0017734-Videome, NRF-2013M3B5A2035921-HyperIntel-

ligence) BK21-IT 로그램에서 일부 지원되었음

․이 논문은 제39회 추계학술발표회에서 ‘다차원 스트림 데이터의 온라인

진 학습을 한 순차 측 모델’의 제목으로 발표된 논문을 확장한 것임

†

††

학생회원

종신회원

논문 수

심사완료

:

:

:

:

서울 학교 컴퓨터공학부

moheo@bi.snu.ac.kr

slee@bi.snu.ac.kr

서울 학교 컴퓨터공학부 교수

btzhang@bi.snu.ac.kr

(Corresponding author임)

2013년 2월 7일

2013년 5월 10일

CopyrightⒸ2013 한국정보과학회ː개인 목 이나 교육 목 인 경우, 이 작

물의 체 는 일부에 한 복사본 혹은 디지털 사본의 제작을 허가합니다.

이 때, 사본은 상업 수단으로 사용할 수 없으며 첫 페이지에 본 문구와 출처

를 반드시 명시해야 합니다. 이 외의 목 으로 복제, 배포, 출 , 송 등 모든

유형의 사용행 를 하는 경우에 하여는 사 에 허가를 얻고 비용을 지불해야

합니다.

정보과학회논문지: 컴퓨 의 실제 터 제19권 제8호(2013.8)

다차원 스트림 데이터의

온라인 진 학습을

한 순차 측 모델(A Sequential Prediction Model

for Online Incremental Learning

of Mutidimensional Stream Data)

허 민 오† 이 상 우

†

(Min-Oh Heo) (Sang-Woo Lee)

장 병 탁††

(Byoung-Tak Zhang)

요 약 실생활 속에서 존재하는 다양한 센서 데이터 스

트림은 실시간으로 끊임없이 유입되면서도 장기 으로 분포

가 변할 수 있는 특성을 지닌다. 이러한 데이터의 학습에는

진 인 학습을 수행하면서도 동시에 순차 측이 가능

한 모델을 필요로 한다. 이에 따라, 본 고에서는 다차원 스

트림 데이터를 한 시계열 측을 다루는 새로운 모델을

제안한다. 이 모델은 순차 인 정보를 지닌 패턴들의 집합

과 해당 패턴들이 나타난 빈도를 이용하여 표 되며, 이를

기반으로 시계열 측을 수행한다. 본 모델의 타당성을 평

가하기 해, 분포를 아는 문자서열을 생성하여 조건부 확

률분포가 학습됨을 보 다. 한, 스마트폰 내 GPS 센서를

이용하여 수집한 실제 사용자의 이동 데이터를 이산화하여

이제까지 이동해온 도로를 통해 다음에 이동할 도로를

측하는 문제를 해결하고, 그 분석 결과를 통해 본 모델의

특성을 실험 으로 확인하 다.

키워드: 데이터 스트림, 온라인 진학습, 순차 측,

스마트폰 센서 데이터

Abstract Data streams from real-world sensors

inherently have features of open-ended inflow and of

changeable distribution in the long term (e.g., concept

drift). To learn these data, we need sequential prediction

models learnable online incrementally. Here, we propose

novel models for multidimensional time-series data

stream. The models are represented with a set of sequen-

tial patterns and the corresponding frequencies, and

perform probabilistic sequential prediction tasks based on

them. As model regularization, the maximum number of

patterns is able to be limited. To validate the learning

methods, we show that they successfully learn condi-

tional distributions with random generated strings.

Moreover, next-position prediction task also performed

using street sequences from GPS sensors embedded in

smartphones. From them, we validate the characteristics

of the model experimentally.

Keywords: data stream, online incremental learning,

sequential prediction, smartphone sensor

data

1. 서 론

최근 스마트폰과 같이 실생활 속에 쉽게 다양한 센서

데이터를 제공하는 기기가 나타남에 따라, 실시간으로

끊임없이 유입되면서도 장기 으로 분포가 변할 수 있

는 데이터가 늘어나고 있다[1]. 통 인 시계열 형태의

순차 데이터 모델링 기법은 오 라인 학습이 주로 사

용되었으며, 장기 인 변화를 다루기 해서는 긴 기간

의 데이터 수집이 불가피 하 다[2-4]. 즉, 한번 확보하

던 데이터를 이용하여 모델을 구축한 후, 문제해결에

활용하는 방식을 주로 취해왔다. 흔히 사용하는 시계열

데이터 모델링 방법으로 재귀 뉴럴 네트워크(recurrent

neural network (RNN))[2], 은닉 마코 모델(hidden

Markov model (HMM))[3]이 사용되는데, 주로 단기

인 패턴학습에 사용된다. 특히, HMM과 같이 모델에 마

코 가정을 용하 을 경우, 이 시간의 값에 따라

재값이 결정된다.

끊임없이 유입되는 데이터, 즉, 스트림 데이터를 학습

하기 해서는 오 라인 형태가 아니라, 시간의 흐름에

따라 함께 학습을 수행하는 온라인 학습(online learn-

ing)이 가능해야 한다[5]. 장기 에서 사용자의 환

경변화에 향을 받아 유입되는 데이터의 분포가 변할

경우에도 지속 인 학습을 통해 concept drift를 다룰 수

있어야 함을 의미한다[6,7]. 한, 이러한 과정을 지속

으로 수행하면서도 사용자의 요청에 따라 재 모델을

420 정보과학회논문지 : 컴퓨 의 실제 터 제 19 권 제 8 호(2013.8)

이용하여 추론하는 것이 가능해야 한다. 즉, 스트림 데이

터를 이용하여 진 인 온라인 학습을 수행하면서도 동

시에 순차 측이 가능한 모델이 요구되고 있다.

본 고에서는 스트림 데이터를 한 시계열 측을 다

루는 새로운 모델을 제안한다. 이 모델은 순차 인 정보

를 나타내는 패턴들의 집합과 해당 패턴들이 나타난 빈

도를 모델로서 가지고 있으며, 이를 기반으로 시계열

측을 시도한다. 진 인 온라인 학습은 데이터가 유입

되는 매 시 마다 등장한 패턴의 빈도를 늘리는 것으로

단순하게 진행되며, 유입된 데이터와 비교하여 정보가

부족하거나 수정이 필요하다고 단될 경우, 패턴집합

내에 새로운 패턴을 추가하거나 수정/삭제를 수행한다.

이후, 본 논문은 다음과 같이 구성된다. 2장에서는 다

루려는 순차 측 문제를 설명하고, 3장에서 스트림

데이터의 진 온라인 학습을 한 모델과 학습

추론 방법을 소개한다. 4장에서는 실험을 통해 모델의

용 를 보인 후, 5장에서 결론을 맺는다.

2. 스트림 상에서의 순차 측 문제

순차 측 문제는 최근 k 개의 이산변수에 한 입

력이 주어졌을 때, 바로 다음 단계 는 n 단계 후의

입력이 무엇일지 측하는 문제로서, 다음과 같이 표

된다.

:ˆ argmax ( | )t n t n t k tx

x P X x X+ + −= = (1)

여기서, n과 k는 임의의 양의 정수이다. 여기서, n이

1이고 시계열 길이 체가 조건으로 주어질 경우(즉, k

= t-1)에는 통 인 filtering 문제이며, n이 0보다 큰

경우에는 prediction 문제이다.

이러한 문제를 다루는 일반 인 근 방법은 식 (1)

에서 심 상인 n과 k를 결정하고, 시계열 데이터의

조건부 확률분포를 학습하여 확률이 최 가 되는 값을

구하는 방법이다. 특히, filtering 문제에 한 표 모

델로는 은닉 마코 모델(HMM)이 있다[3]. 하지만, 이

러한 방법론은 기본 으로 스트림 상의 확률 분포가 변

하지 않는다는 가정을 가지고 있으며, concept drift와

같이 스트림 상의 분포가 변하는 것을 다루는 모델로는

합하지 않다.

본 고에서는 체 입력 길이보다 작은 임의의 정수 k

가 주어진 경우에 하여, 순차 측 문제를 다루고자

한다. 한, 스트림 데이터의 특성상 실시간으로 유입되

는 형태를 가지므로, 학습 추론 과정이 진 이어야

하며, 온라인 학습이 가능해야 한다[8]. 즉, 학습 추

론에 필요한 계산 비용이 크지 않아야 한다. 이러한 특

성을 고려하여 순차 측을 수행하는 방법을 다음 장

에서 소개한다.

3. 모델 표 과 학습 추론 방법

앞에서 설명한 순차 측 문제를 다룰 수 있으면서

도 진 으로 온라인 학습을 수행하기 하여, 스트림

데이터를 패턴 집합과 그 빈도로 바꾸어 표 하는 모델

을 도입한다.

이 모델에서는 최근 스트림 데이터에서 나타난 순차

패턴의 빈도를 갱신하는 것으로 학습을 수행하며, 존재

하지 않는 패턴이 나타날 경우에는 패턴집합에 새로이

추가한다. 한, 패턴이 무한히 늘어나는 것을 막기 해

오랫동안 사용되지 않으면 패턴이 삭제되도록 한다.

추론과정으로서, 어떤 시 에 사용자가 특정 입력이

주어졌을 때 n 시간 이후 나타날 값이 무엇일지 측하

는 문제에 한 답을 하기 하여, 이 모델로부터 사후

확률을 구하고 최 확률에 해당되는 값을 출력하는 것

으로 요약할 수 있다. 그림 1에 학습, 추론 과정을 간략

히 나타내었다.

그림 1 제안 방법의 기능 개요도

Fig. 1 Overall functional structure of the proposed methods

3.1 모델 정의

앞에서 간략히 설명한 모델을 엄 히 정의한다. 모델

M=<H, w>은 패턴의 집합 H와 패턴의 빈도 w의

으로 정의된다. H는 임의의 순차 패턴 E를 원소로

갖는 색인된 집합이며, i 번째 패턴을 Ei 로 표기한다.

한, w는 각 E가 스트림 데이터에서 등장한 빈도를

원소로 갖는 색인된 집합이며, Ei 에 한 원소를 wi 로

표기한다. 모든 E는 특정 시 을 기 으로 시간 차이와

값을 표 하는 순차패턴을 나타낸다. 이를 표 하기

해, 상 시간 색인 u와 인자 색인 f가 부여된 이산

변수 X fu와 변수에 할당된 값 c로 이루어진 3-tuple

(f,u,c)를 원소로 하는 집합 𝓚 를 정의하자. 𝓟 E (𝓚 )는

𝓚 의 멱집합 𝓟 (𝓚 )의 부분집합으로, 시간과 인자 이

복되지 않는 것들을 원소로 하는 집합이며, 패턴 E는

𝓟 E(𝓚 )의 임의의 원소이자, (f,u,c)들의 집합이 된다. 즉,

다차원 스트림 데이터의 온라인 진 학습을 한 순차 측 모델 421

( ) { | ( ), , , ( , ) ( , )}E i i j jE E i j in E f u f u= ∈ ∀ ≠P X P X (2)

단, i, j는 E 안에 있는 원소의 색인을 나타내는 양의

정수이다.

3.2 추론 방법

t-k시 부터 t까지의 값이 질의로서 주어졌을 때,

t+n 시 에 한 측을 다룰 경우, 조건부 확률 P가

최 가 되는 x가 결정되며, 주어진 M으로부터 다음과

같은 근사 인 비례 계를 얻는다.

,

,

| |, : , 0

: : | |, :

| | ( , ) ( , )( | )

| | ( , )

i u n

i

i u n

i

Ei i u n t k t i u t n

E Ht n t k t t k t E

i i u n t k tE H

c w E x E xP X X x

c w E x

δ δ

δ

≥

≥

≥ − = +∈

+ − −≥ −

∈

⋅ ⋅ ⋅= ∝

⋅ ⋅

∑

∑(3)

상기 식에서 , :( , )i u n t k tE xδ ≥ − 은 i 번째 패턴 Ei 에서

시간 색인이 n 보다 큰 부분의 값이 질의와 동일하면

( 는 가까우면) 1, 아니면 0을 출력하는 함수이며,

, 0( , )i u t nE xδ = + 는 패턴 Ei 의 u = 0인 원소와 측하려는

값이 동일 ( 는 가까움) 여부를 출력하는 함수이다. 즉,

식 (3)은 다음 두 단계를 하나의 수식으로 표 한 것이

다. 모델이 가진 패턴 집합 내에서 1) 질의와 련된 패

턴들을 matching과정을 통해 찾고, 2) 그 안에서 빈도

정보, 패턴 내 시간 차이 정보와 패턴의 경우의 수를 이

용하여 사후 조건부 확률을 계산하게 된다.

3.3 학습 방법

모델 M은 이상 으로는 고려하는 시간 색인 길이 k

에 따라 패턴 E의 개수가 지수 으로 증가한다. 이를

극복하기 해 데이터에 나타나지 않은 패턴의 빈도는

0이므로, 실제 모델에는 아직 추가될 필요가 없으며, k

가 클 경우, 모든 조합을 다 다룰 수 없으므로 가능한

패턴 일부를 무작 로 선택하여 모델에 반 한다.

이를 수행하는 학습 알고리즘을 그림 2에 제시하 다.

스트림 데이터가 입력됨에 따라, 스트림 데이터의 Xt-w

～Xt 상에서 무작 로 시 과 인자를 선택하여 h개의

후보를 만든 후, M 안에 해당 패턴이 없을 경우 M에

포함시킨다. 그 후, 포함된 패턴에 해서 입력되는 데

이터와 비교, 맞는 패턴에 해 해당 w를 증가시킨다.

여기서, 데이터 스트림의 특성에 따라 학습된 모델이

수렴하지 않고 새로운 패턴이 무한히 발견될 경우, 모델

도 이를 포함시켜야 하며, 이는 계산불능문제를 야기시

킨다. 이를 회피하기 한 부분이 필요하며, 그림 2의

revise 부분이 이에 해당된다. 두 가지 략이 사용될

수 있다. 첫 번째 략은 패턴 수의 상한선을 정해두고,

새로운 패턴을 추가해야 할 경우, w, |E|를 기 으로 모

델에 향이 작은 패턴부터 삭제하는 략이다. 두 번째

략은 각 패턴마다 fading constant를 두어 문턱값 이

상 사용되지 않은 패턴을 삭제하는 략이다.

그림 2 간략히 표 한 학습 알고리즘

Fig. 2 Briefly sketched Learning Algorithm

4. 실험 결과

본 에서는 실험을 통해 제안한 모델이 분포학습을

잘 하는지 확인한 후, 실세계 데이터를 이용하여 순차

측문제에 용할 것이다. 먼 , 분포학습 특성을 확인

하기 해, 특정 분포로부터 무작 로 생성한 데이터를

제안한 모델에 학습시키고 이로부터 원본 분포와의 차

이를 분석한다. 실생활 속 응용으로서, [9]에서 쓰인 스

마트폰으로 수집한 GPS 치정보 데이터를 스트림 형

태로 입력시키면서, 이후 시 에 치할 도로 측 문제

를 다루었다.

4.1 조건부 확률분포 학습

분포학습 여부를 확인하기 해서는 분포를 알고있는

데이터가 필요하다. 이를 해, 다음과 같이 스트림 데

이터의 체 데이터를 생성하 다. 숫자 ‘1,2,3,4’를 가능

한 알 벳으로 한 문자열을 무작 로 만들되, 이 두

개의 문자에만 의존 으로 다음 문자가 나타나도록 하

다. 이 때, 4×4×4개의 가능한 패턴에 한 이산 확

률을 명시해야 한다. 패턴 ‘1 2 3’, ‘2 3 4’, ‘3 4 1’, ‘4 1

2’는 다른 가능한 패턴에 비해 4배 더 나타날 확률이 높

도록 하여 길이 1000짜리 시계열 데이터를 생성하 고,

이 데이터를 입력 스트림으로 사용하여 학습하 다. 무

작 로 생성하 으므로, 사 에 정한 분포와 생성된 데

이터에 한 실제 분포는 차이가 존재하지만, 입력이 많

아질수록 그 차이가 어든다(그림 3(a)). 한, 조건부

확률의 경우에는 Xt-1 Xt-2 의 값에 따라 매 시 다른

분포를 나타내야 하므로 (b)에서와 같이 변동이 측된다.

이 데이터로 학습을 해 사용한 모델은 n = 1, k = 4,

각 E가 가질 수 있는 최 원소수(이후, order라고 부

름)는 4로 라미터를 설정한 모델이다. 그림 4에서 볼

수 있듯이, 학습을 진행함에 따라 제안한 모델이 측한

확률과 등장 패턴에 따른 통계 사이의 거리가 차

어드는 것을 확인할 수 있다. 이는 입력 데이터 스트림

이 분포를 유지할 경우, k 값이 생성 확률의 조건과 딱

맞지 않더라도 분포를 학습할 수 있음을 의미한다.

422 정보과학회논문지 : 컴퓨 의 실제 터 제 19 권 제 8 호(2013.8)

그림 3 학습을 한 문자열 스트림의 생성분포와 각 시 까지의 패턴 통계와의 차이

Fig. 3 Difference between the generating distribution and pattern statistics in the training stream of string

그림 4 조건부 분포 학습 결과

Fig. 4 Result of learning the conditional distribution

4.2 스마트폰 센서 스트림을 이용한 치 측 문제

상기 방법론은 스마트폰 내에 임베딩된 다양한 센서

로부터 다음시 는 미래시 의 센서값을 측하는

문제에 사용될 수 있으며, 이 측치로부터 사용자의 컨

텍스트를 추론하는 문제를 다룰 수 있다. 본 고에서는

개념증명으로서 GPS 센서로부터 얻은 치정보로부터

다음 시 의 치 측 문제에 용한 결과를 보고한다.

이를 한 테스트용 스트림 데이터로서, [9]에서 사용된

로그 기록기인 Action Logger를 이용하여 실제 사용자

(1명)의 이동 로그를 1 간격으로 4건(각 1247 , 1170

, 1719 , 1338 )을 수집하 다. 실수인 GPS 값을

신하여 이산화를 해 네비게이션 모듈을 이용하여

가까운 도로로 사 시켰다(그림 5). 이 과정은 GPS의

측 노이즈를 이는 효과를 가지지만, 갈림길 는 이

면도로가 있는 경우 다른 도로로 사 되기도 하므로, 여

히 노이즈를 가진 이산화된 순차 데이터가 된다.

상기 데이터를 입력 데이터 스트림으로 하여 학습과

추론을 함께 수행하 다. (n = 1, k = 10, order: 2～3,

2～4, 2～5 사용) 학습이 진행 됨에 따라 그림 6(a)와

같이 매치된 각 패턴의 빈도 수가 늘어나게 된다. k는

고려할 과거값의 길이를 나타내며, 학습된 모델은 k-order

Markov 모델을 근사하게 된다. Order가 커지면 지수

으로 경우의 수가 늘어나므로, 직 모델링을 시도할 경

우 연산가능 범 를 쉽게 넘어선다. 이를 해 비교모델

로서 naïve Bayes 모델을 사용하여 k-order Markov

모델을 근사하 다. 한, order 값이 커지면 고려해야

할 패턴의 다양성이 커짐에 따라 모델 내의 총 패턴 수

도 늘어나게 된다.

학습을 수행하며 온라인으로 추론한 결과는 다음과 같

다. 기에 1번 로그까지만 학습했을 때보다 1～2, 1～3,

1～4 등 여러 로그가 추가된 모델은 그에 따른 방해가

생겨 측 정확도는 다소 하락한다. 하지만 order를 늘리

면 더 많은 정보를 이용하게 되어 성능이 증가하는 것을

볼 수 있다. 학습과정에서 무작 로 패턴을 추가하 기

때문에 4번까지 반복 학습을 수행하더라도 그림 6(b)와

같이 모델 내의 패턴 수는 완만하게 증가한다.

5. 결론 향후 연구

본 고에서는 스트림 데이터를 다룰 수 있는 진

온라인 학습 모델을 소개하고 추론 학습 방법을 보

다. 제시 방법의 타당성을 확인하기 해 분포를 아는

데이터 스트림과 학습된 모델이 근사하는 조건부 확률

을 비교하 으며, 실생활의 응용 로서 스마트폰 센서

데이터 학습 결과를 제시하 다.

향후에는 장기 의존성을 다룰 수 있는 모델과 추론

/학습 방법에 한 연구를 진행할 정이며, 이를 측

다차원 스트림 데이터의 온라인 진 학습을 한 순차 측 모델 423

그림 5 학습에 사용한 이동 로그의 (1번 로그). GPS 값( )을 도로로 변경하여(아래) 학습데이터로 이용

Fig. 5 GPS based log sequence sample in training dataset. Raw GPS values (1st row) are converted into streets (2

nd row)

그림 6 스마트폰 센서 데이터를 이용한 학습 측 결과

Fig. 6 Learning & prediction result with smartphone sensor data stream

스트림 데이터 요약에 용하고자 한다. 본 연구를

통해 더욱 개선된 추론/학습 방법에 한 연구와 다른

응용에의 용을 기 한다.

References

[ 1 ] N. D. Lane, E. Miluzzo, H. Lu, D. Peebles, T.

Choudhury, and A. T. Campbell, "A Survey of

Mobile Phone Sensing," IEEE Communications

Magazine, vol.48, no.9, pp.140-150, 2010.

[ 2 ] S. Haykin, Neural Networks and Learning Machine,

Prentice Hall, 2009.

[ 3 ] D. Koller and N. Friedman, Probabilistic Graphical

Models: Principles and Techniques, MIT Press, 2009.

[ 4 ] D. Barber, T. Cemgil, and S. Chiappa, Bayesian Time

Series Models, Cambridge University Press, 2011.

[ 5 ] S. Shalev-Shwartz, "Online Learning and Online

Convex Optimization," Foundations and Trends® in

Machine Learning, vol.4, no.2, pp.107-194, 2012.

[ 6 ] G. Widmer and M. Kurat, "Learning in the Pre-

sence of Concept Drift and Hidden Contexts,"

Machine Learning, vol.23, pp.69-101, 1996.

[ 7 ] I. Zliobaite, "Learning under Concept Drift: an

Overview," Technical Report, Faculty of Mathe-

matics and Informatics, Vilnius University, 2009.

[ 8 ] C. Aggarwal, Data Streams: Models and Algorithms,

Springer, 2007.

[ 9 ] M.-O. Heo, M. Kang, B.-K. Lim, K.-B. Hwang,

Y.-T. Park and B.-T. Zhang, "Real-time Route Infer-

ence and Learning for Smartphone Users using Pro-

babilistic Graphical Models," Journal of KIISE: Soft-

ware and Applications, vol.39, no.6, pp.425-435, 2012.