Mining Data Stream(Part 1)

Overview

• 많은 데이터 마이닝 상황에서 전체 데이터 세트를 미리 알지 못합니다.
• 스트림 관리는 입력 속도가 외부에서 제어될 때 중요합니다.
  • Google 쿼리
  • Twitter 또는 Facebook 상태 업데이트
• 데이터를 무한하고 비정상적이라고 생각할 수 있습니다(시간에 따라 분포가 변경됨).
• 스트림 마이닝은 연속적인 데이터 스트림에서 지식이나 패턴을 발견하는 프로세스입니다.

The Data Stream Model

• 입력 요소는 하나 이상의 입력 포트(즉, 스트림)에서 빠른 속도로 입력됩니다.
• 스트림 튜플의 요소를 호출합니다.
• 시스템이 전체 스트림을 액세스 가능하게 저장할 수 없습니다. • 데이터가 메모리에 맞지 않습니다.
• 디스크 저장 및 액세스 속도가 느림

General Stream Processing Model

Problems on Data Streams

• 데이터 스트림의 답변에 대해 원하는 쿼리 유형:
  • 데이터 스트림 필터링
    - 스트림에서 속성 x가 있는 요소 선택
  • 고유한 요소 계산
    - 스트림의 마지막 k 요소에 있는 고유한 요소의 수
  • 모멘트 추정
    - 평균/표준 추정. 개발 마지막 k개 요소
  • 빈번한 요소 찾기

Applications

• 센서 네트워크
  • 많은 센서가 중앙 컨트롤러에 공급됨 
  • 습도, 온도, 누수 등.
• 소셜 네트워크 뉴스 피드 마이닝
  • 예: Twitter, Facebook에서 인기 있는 주제 찾기
• 쿼리 스트림 마이닝
  • 예: Google, Naver, Daum 등 어떤 검색어가 더 자주 발생하는지 알고 싶습니다.

Sampling from a Data Stream

• 전체 스트림을 저장할 수 없으므로 한 가지 분명한 접근 방식은 샘플을 저장하는 것입니다.
  • 두 가지 다른 문제:
    1. 스트림에서 고정된 비율의 요소 샘플링(예: 1/10)
    2. 잠재적으로 무한한 스트림에 대해 고정 크기의 무작위 샘플 유지
      • 임의의 "시간" k에서 s 요소의 무작위 샘플을 원합니다.
      • 유지하려는 샘플의 속성은 무엇입니까? 모든 시간 단계 k에 대해 지금까지 본 k개의 요소 각각은 샘플링될 확률이 동일합니다.

Sampling a Fixed Proportion

• 문제 1: 고정 비율 샘플링
• 시나리오: 검색 엔진 쿼리 스트림
  • 튜플 스트림: (사용자, 쿼리, 시간)
  • 다음과 같은 질문에 답하십시오. 사용자가 하루에 동일한 쿼리를 얼마나 자주 실행했습니까?
    => 사용자가 동일한 쿼리를 두 번 이상 실행한 빈도는?
  • 쿼리 스트림의 1/10을 저장할 공간이 있어야 합니다.
• Naive 솔루션:
  • 각 쿼리에 대해 [0..9]에 임의의 정수를 생성합니다. 
  • 정수가 0이면 쿼리를 저장하고, 그렇지 않으면 폐기합니다.

Problem with Naive Approach

• Q? : 평균적인 검색 엔진 사용자의 쿼리 중 중복되는 비율은 얼마입니까?
  • 각 사용자가 x 쿼리를 한 번, d 쿼리를 두 번 실행한다고 가정합니다(총 x+2d 쿼리). 
    • 정답:d/(x+d)
  • 제안된 솔루션: 쿼리의 10%를 유지합니다.
    • 샘플에는 싱글톤 쿼리의 x/10과 중복 쿼리의 d*19/100이 최소 한 번 포함됩니다.
    • 단 d/100 쌍의 중복
      -> d/100 = 1/10 ∙ 1/10 ∙ d
    • d개의 "중복" 중 18d/100이 정확히 한 번 나타납니다.
    • 18d/100 = ((1/10 ∙ 9/10)+(9/10 ∙ 1/10)) ∙ d 
  • 따라서 표본 기반 답은 (d/100)/(x/10)+(d/100)+(18d/100) = d/(10x+19d)

Solution: Sample Users

• 간단한 솔루션:
  • 1/10𝑡h의 사용자를 선택하고 샘플에서 모든 검색을 수행합니다.
  • 사용자 이름 또는 사용자 ID를 10개의 버킷으로 균일하게 해시하는 해시 함수 사용

Generalized Solution

• 키가 있는 튜플 스트림:
  • 키는 각 튜플 구성 요소의 일부 하위 집합입니다. 
    • 예를 들어 튜플은 (사용자, 검색, 시간)입니다. 키는 사용자입니다
  • 키 선택은 애플리케이션에 따라 다릅니다.
• 스트림의 a/b 부분 샘플을 얻으려면: 
  • 각 튜플의 키를 b 버킷에 균일하게 해시합니다.
  • 해시 값이 최대 a인 경우 튜플을 선택합니다.
  
• 예: 30% 샘플을 생성하는 방법은 무엇입니까? 
     b=10 버킷에 해시하고 처음 3개 버킷 중 하나에 해시되면 튜플을 사용합니다.

Maintaining a fixed-size sample

• 문제 2: 고정 크기 샘플
• 크기가 정확히 s 튜플인 임의의 샘플 S를 유지해야 한다고 가정합니다.
  • 예: 주 메모리 크기 제약
• 왜? 미리 스트림의 길이를 모른다
• 시간 n에 n개의 항목을 보았다고 가정합니다.
• 각 항목은 확률이 동일한 표본 S에 있습니다. s/n
• **비현실적인 솔루션은 지금까지 본 모든 n 튜플을 저장하고 그 중에서 무작위로 선택하는 것입니다.

Solution: Fixed Size Sample

• 저수지 샘플링
  • 스트림의 모든 첫 번째 s 요소를 S에 저장
  • n-1개의 요소를 보았고 이제 𝑛𝑡h 요소가 도착한다고 가정합니다(n > s).
    • 확률 s/n으로 𝑛𝑡h 요소를 유지하고, 그렇지 않으면 버립니다.
    • 𝑛𝑡h 요소를 선택하면 무작위로 균일하게 선택된 샘플 S에 있는 s 요소 중 하나를 교체합니다.
• Claim:
• 이 알고리즘은 원하는 속성을 가진 샘플 S를 유지합니다.
  • n개의 요소 이후에 샘플은 지금까지 s/n의 확률로 본 각 요소를 포함합니다.

Discussion

• Claim: 시간 t에서 모든 요소는 샘플에 포함될 동일한 확률 s/t가 제공됩니다.
• n 시간에 샘플에 속하고 n+1 시간에 살아남은 항목에 대해 위의 주장이 사실입니까?
  • Yes
• (n+1)번째 항목에 대해 위의 주장이 사실입니까? 
  • (n+1)번째 항목은 버리거나 포함될 수 있습니다.

Sliding Windows

• 스트림 처리의 유용한 모델은 쿼리가 길이 N - 가장 최근에 수신된 N개의 요소에 관한 것입니다.
• Interesting Case: N이 너무 커서 데이터를 메모리나 디스크에도 저장할 수 없습니다.
  • 또는 스트림이 너무 많아 전체 창을 저장할 수 없습니다.

Sliding Window: 1 Stream

• 단일 스트림의 슬라이딩 창: 창 크기 𝑁 =6

Counting Bits(1)

• 문제:
  • 0과 1의 스트림이 주어졌을 때
  • 양식의 질문에 답할 준비를 하십시오.
    • 마지막 k 비트에는 몇 개의 1이 있습니까? 여기서 k ≤ N
    
• 명백한 해결책: 가장 최근의 N 비트 저장
  • 새 비트가 들어오면 𝑁 + 1𝑠𝑡 비트를 버립니다.

Counting Bits(2)

• 전체 창을 저장하지 않고는 정확한 답을 얻을 수 없습니다
• 실제 문제: N 비트를 저장할 여유가 없으면 어떻게 합니까? 
  • 예: 우리는 10억 개의 스트림을 처리하고 있으며
  • 창 크기 N = 10억.
  • 데이터를 많은 스트림으로 생각하십시오.
  • 실제 스트림에 x가 없으면 x에 대한 스트림의 비트는 0입니다.

An attempt: Simple solution

• Q: 마지막 N 비트에 몇 개의 1이 있습니까?
• 우리의 문제를 실제로 해결하지 못하는 간단한 솔루션: 균일성 가정

• 2개의 카운터 유지:
  • S: 스트림 시작부터 1의 수 
  • Z: 스트림 시작부터 0의 수
  • 마지막 N 비트에는 몇 개의 1이 있습니까? 𝑵 ∙ 𝑺/(𝑺+𝒁)
• 위 방법의 문제점은 무엇인가?

DGIM Method

• 균일성을 가정하지 않는 DGIM 솔루션

• 스트림당 O(log^2N) 비트만 저장합니다. 
  • N = 창 크기.
• 대략적인 답변을 제공하며 절대 50% 이상 떨어지지 않습니다.
  • 오류 요인은 더 복잡한 알고리즘과 비례하여 더 많은 저장 비트를 사용하여 
    분수(ε) > 0으로 줄일 수 있지만 O(log^2N) 공간 요구 사항은 동일합니다.
    
• Main Idea
  • 블록 크기(1의 개수)가 기하급수적으로 증가하는 특정 개수의 1로 블록을 요약합니다.

DGIM: Timestamps

• 스트림의 각 비트에는 0, 1, ...로 시작하는 타임스탬프가 있습니다.
• 모든 관련 타임스탬프를 O(log2N) 비트로 나타낼 수 있도록 타임스탬프를 모듈로 N(창 크기)으로 기록합니다.

DGIM: Buckets

• 버킷은 1로 끝나는 창의 세그먼트입니다. 다음으로 구성된 레코드로 표시됩니다:
  1. 끝의 타임스탬프 [O(log N) 비트].
  2. 시작과 끝 사이의 1의 수.
    • 1의 수 = 버킷 크기.
• 버킷 크기에 대한 제약: 1의 수는 2의 거듭제곱이어야 합니다.
  • 따라서 이 카운트에는 O(log log N) 비트만 필요합니다.

Representing a Stream by Buckets

• 1의 2의 거듭제곱이 동일한 버킷 1개 또는 2개
• 버킷은 타임스탬프에서 겹치지 않습니다.
• 모든 1은 하나의 버킷에 있습니다. 0은 버킷에 있을 수도 있고 아닐 수도 있습니다.
• 버킷은 크기별로 정렬됩니다.
  • 이전 버킷은 이후 버킷보다 작지 않습니다.
• 종료 시간이 과거의 N 시간 단위보다 크면 버킷이 사라집니다.

Example: Bucketized Stream

유지 관리되는 버킷의 세 가지 속성:
• 1의 2의 거듭제곱이 동일한 버킷 1개 또는 2개
• 버킷은 타임스탬프에서 겹치지 않습니다.
• 버킷은 크기별로 정렬됩니다.

Storage Requirement

• 각 버킷에는 O(log N) 비트가 필요합니다.
  • 끝의 타임스탬프 [O(log N) 비트]
  • 시작과 끝 사이의 1 수 [O(log log N) 비트]
• 따라서 총 저장 요구 사항은 
  • O(log N) * O(log N) = O(log^2 𝑁)

Updating Buckets(1)

• 새 비트가 들어올 때 종료 시간이 현재 시간보다 N 시간 단위 이전인 경우 마지막(가장 오래된) 버킷을 삭제합니다.
• 2가지 경우: 현재 비트가 0 또는 1인 경우
• 현재 비트가 0인 경우: 다른 변경이 필요하지 않습니다.

Updating Buckets(2)

• 현재 비트가 1인 경우:
1. 이 비트에 대해 크기가 1인 새 버킷을 만듭니다.
  • 종료 타임스탬프 = 현재 시간
2. 크기가 1인 버킷이 3개 있는 경우 가장 오래된 버킷을 결합합니다.
크기 2의 양동이에 두 개
3. 크기 2의 버킷이 3개 있는 경우 가장 오래된 두 개를 크기 4의 버킷으로 결합합니다.
4. 등등...

Example: Managing Buckets

How to Query?

• 가장 최근 N 비트에서 1의 수를 추정하려면:
  • 1. 마지막을 제외한 모든 버킷의 크기 합계(참고 "크기"는 버킷의 1 개수를 의미함)
  • 2. 마지막 버킷 크기의 절반 추가
• Remember: 마지막 버킷의 1이 원하는 창 내에 아직 몇 개나 있는지 모릅니다.

Error Bound

• 범위 내에서 가장 오래된 버킷의 크기가 2^i라고 가정합니다.
• 그런 다음 1의 2^(i -1)이 여전히 창 안에 있다고 가정하면 최대 2^(i -1)의 오류가 발생합니다.
• 2i보다 작은 각 크기의 버킷이 하나 이상 있고 가장 오래된 버킷에서 하나 이상이 있으므로 
  실제 합은 2^i보다 더 작지 않습니다.
  1+2+4+...+2^(j-1) = 2^j-1
• 따라서, 에러는 거의 50%입니다.

Further Reducing the Error

• 각 크기의 버킷을 1개 또는 2개 유지하는 대신 x-1 또는 x 버킷(x > 2)을 허용합니다.
  • 가장 큰 크기의 버킷 제외; 우리는 그 중 1과 x 사이의 숫자를 가질 수 있습니다.
• 오류는 최대 O(1/x)입니다.
• x를 적절하게 선택하여 저장하는 비트 수와 오류 사이의 균형을 맞출 수 있습니다.
  • x 증가 => 더 많은 메모리 공간, 더 적은 오류

Exponentially Decaying Windows

• 동기 부여; E.D.W.의 빈번한 항목 집합에 대한 효율적인 유지 관리
• 관점: 스트림에서 중요한 것은 가장 최근 요소의 유한한 창이 아닙니다.
• 그러나 모든 요소가 똑같이 중요하지는 않습니다. "오래된" 요소는 최근 요소보다 덜 중요합니다.
• 상수 c << 1을 선택하고 도착하는 i번째 가장 최근 요소의 "가중치"가 (1-c)^i에 비례하도록 합니다.