데이터 스트림 마이닝

데이터 스트림 마이닝(Data Stream Mining, 스트림 데이터 마이닝)은 센서·로그·거래·클릭처럼 끝없이 빠르게 들어오는 데이터 흐름(스트림)에서, 모든 데이터를 저장하지 않고 한 번 지나가는 동안 제한된 메모리와 시간으로 요약·근사 계산을 하여 패턴·모델을 뽑아내는 데이터 마이닝 기법이다.

개요

전통적인 데이터 마이닝은 데이터를 디스크에 모두 쌓아 둔 뒤 여러 번 훑어 분석한다. 스트림은 크기가 사실상 무한하고 도착 속도가 처리 속도보다 빠를 수 있으며, 시간이 지나면서 데이터의 분포 자체가 바뀐다. 그래서 스트림 마이닝 알고리즘은 다음 제약을 전제로 설계한다.

제약	내용	대응
단일 패스(one-pass)	데이터를 한 번만 볼 수 있다. 다시 읽을 수 없다	도착할 때마다 요약 구조를 갱신하는 증분 알고리즘
제한된 메모리	전체 데이터보다 훨씬 작은 메모리만 쓴다	표본, 시놉시스, 스케치로 요약
실시간 처리	항목 하나를 처리하는 시간이 짧아야 한다	상수·로그 시간 갱신
근사 허용	정확한 답 대신 오차 범위가 보장된 근사 답을 낸다	(ε, δ) 근사, 확률적 보장
개념 표류(concept drift)	데이터를 만드는 분포가 시간에 따라 바뀐다	윈도우, 망각 계수, 표류 탐지 후 모델 갱신

알고리즘 개발에 쓰는 기법

데이터 축소: 샘플링

스트림 전체 대신 대표 표본만 유지한다 → 표본추출

저수지 샘플링(reservoir sampling) - 크기 k 의 저수지를 두고, n 번째로 들어온 항목을 확률 k/n 으로 저수지의 임의 항목과 바꾼다. 스트림 길이를 몰라도 지금까지 들어온 모든 항목이 같은 확률로 표본에 남는다
부하 차단(load shedding) - 처리량이 넘치면 일부 항목을 일정 비율로 버려 지연을 막는다

데이터 축소: 시놉시스와 스케치

데이터를 작은 요약 구조(시놉시스)로 바꾸어 질의에 근사로 답한다.

구조	답하는 질의	원리
카운트-민 스케치(Count-Min Sketch)	항목별 빈도, 상위 빈발 항목	해시 함수 여러 개로 카운터 배열을 갱신하고 최솟값을 답한다. 과대 추정만 생긴다 → 해시
블룸 필터(Bloom filter)	이미 본 항목인가(멤버십)	비트 배열과 해시 여러 개. 거짓 양성은 있지만 거짓 음성은 없다
HyperLogLog	서로 다른 항목의 수(카디널리티)	해시값의 앞자리 0 의 개수로 개수를 추정한다
히스토그램·웨이블릿	값의 분포, 범위 질의	분포를 구간·계수 몇 개로 압축한다 → 히스토그램
Lossy Counting·Misra-Gries	빈발 항목·빈발 패턴	정해진 크기의 카운터만 두고 작은 것을 주기적으로 지운다

윈도우 모델

최근 데이터에 초점을 맞추고 오래된 데이터의 영향을 줄인다.

랜드마크 윈도우 - 특정 시점부터 지금까지 전부
슬라이딩 윈도우 - 가장 최근 N 개(또는 최근 t 초)만. 새 항목이 들어오면 가장 오래된 항목이 빠진다. 지수 히스토그램으로 근사해 메모리를 줄인다
텀블링 윈도우 - 겹치지 않는 고정 구간으로 끊어 처리한다
감쇠(fading) 윈도우 - 모든 데이터를 쓰되 오래될수록 가중치를 지수적으로 줄인다

증분 학습 모델

VFDT(Very Fast Decision Tree, 호에프딩 트리) - 노드마다 충분한 표본이 모였는지를 호에프딩 부등식으로 판단해, 데이터를 한 번만 보면서 일괄 학습한 의사결정 나무와 거의 같은 분할을 확률적으로 보장한다. 표류에 대응하는 CVFDT 가 있다
앙상블 - 데이터 묶음마다 분류기를 학습해 더하고, 성능이 떨어진 것을 가중치를 낮추거나 버린다(정확도 가중 앙상블, 적응형 랜덤 포레스트)
온라인 경사 하강법 - 항목 하나마다 모델 파라미터를 조금씩 갱신한다 → 기계 학습

스트림 군집과 빈발 패턴

CluStream - 온라인 단계에서 마이크로 클러스터(점의 개수·합·제곱합 같은 요약 특징 벡터)를 갱신하고, 오프라인 단계에서 필요할 때 이를 묶어 최종 군집을 만든다. 시점별 스냅숏을 남겨 기간별 군집을 비교한다 → 군집 분석
DenStream·D-Stream - 밀도 기반으로 임의 모양의 군집과 잡음을 다룬다
빈발 패턴은 윈도우 안의 근사 빈도(Lossy Counting)로 찾는다 → 연관 분석

개념 표류 탐지

분포가 바뀌면 기존 모델의 오류율이 오른다. 이를 감지해 모델을 다시 학습한다.

DDM(Drift Detection Method) - 분류 오류율과 표준편차가 최소일 때보다 일정 배 이상 커지면 경고·표류로 판단한다
ADWIN(ADaptive WINdowing) - 윈도우를 두 부분으로 나누어 평균 차이가 통계적으로 유의하면 오래된 부분을 버려 윈도우 크기를 자동으로 조정한다
표류의 모양은 갑작스러운(sudden), 점진적(gradual), 증가하는(incremental), 되풀이되는(recurring) 것으로 나눈다

처리 기반

스트림 마이닝 알고리즘은 실시간 처리 엔진 위에서 돈다. 메시지 큐로 데이터를 받고(아파치 카프카), 스트림 처리 엔진(아파치 스파크 Structured Streaming, 아파치 플링크)이 윈도우·상태를 관리하며, MOA(Massive Online Analysis) 같은 라이브러리가 VFDT·ADWIN·CluStream 을 제공한다. 전통적 데이터 마이닝과 비교하면 다음과 같다.

구분	전통적 데이터 마이닝	데이터 스트림 마이닝
데이터	저장된 유한 데이터	끝없이 들어오는 흐름
접근	여러 번 읽기	한 번 읽기
결과	정확한 답	오차가 보장된 근사 답
모델	한 번 학습하고 고정	계속 갱신, 표류에 적응
쓰임	고객 분석, 장바구니 분석	이상 거래 탐지, 네트워크 침입 탐지, 센서·설비 감시, 실시간 추천

같이 보기