빅데이터를 다루기 위해서, 즉 Stream Data를 다루기 위해서 Moment라는 개념을 정리해 둘 필요가 있다. 여러 물리량을 다루는 데 있어서 모멘트라는 개념이 많이 쓰이기도 하기 때문에 낯설지는 않은 개념이겠지만, 확실하게 짚고 넘어가는 것이 좋다. m(i)를 특정한 값 i가 Stream 에 등장한 횟수라고 정의할 때, kth Moment는 아래 그림과 같이 스트림에 있는 N개의 m(i)를 각각 k승 한 값들의 합으로 나타낼 수 있다. 이 모멘트는 k값에 따라 각기 다른 특정한 의미를 갖는데, 모멘트를 정의하는데 사용했던, m(i)의 의미를 생각해보면 쉽게 이해할 수 있다. 0th moment = m(i)의 값이 의미가 없어지므로, 스트림 내에서 서로 다른 원소의 개수를 의미한다. 1st mome..

Flajolet-Martin Algorithm은 Stream Data에서 서로 다른 데이터의 개수를 세는 알고리즘(Counting Distinct Element) 이다. 이는 Stream Data에서 다음과 같은 질의들에 응답하는데 사용된다 . - How many different words are found among the web pages crawled at a site? - How many different web pages does each customer request in a week? - How many distinct products have we sold in the last week? 이 질의들에 응답하기 위한 가장 명백한 방법 (Obvious Solution)은 N개의 데이터들을 특..

Stream 형태의 무한한 데이터를 다루기 위한 알고리즘 중의 하나는 '필터링 알고리즘'이다. 스트림에서 X라는 속성을 가지는 데이터들을 걸러내는 알고리즘으로써 여러 메일들의 스트림을 입력받았을 때, 스팸메일을 걸러주는 프로그램등이 이 필터링 알고리즘을 적용한 예에 속한다. Filtering Data Streams 이전 포스팅의 예제와 마찬가지로 데이터 스트림의 각 원소는 Tuple(튜플, 순서쌍)의 형태로 입력이 된다. 이때 필터링 알고리즘의 문제는 S라는 Key set이 들어왔을 때, 입력되는 튜플들의 스트림 중 S에 속하는 튜플들을 걸러내는 것이 된다. 이를 해결하기 위한 가장 명백한(Obvious) 방법은 해시 테이블(Hash Table)을 이용하는 것이다. 해시 함수는 같은 키 값이 들어오면 무..

DGIM Algorithm은 Sliding Window 방법에서 0과 1의 스트림이 입력값으로 들어올 때, 가장 최근의 N개의 데이터에서 1이 몇개 있는지를 예측하는 알고리즘이다. 여기서 Sliding Window 란, 빅데이터의 스트림들을 처리할 때 모든 데이터를 저장하지 않고, 순차적으로 n개의 데이터들을 미끄러지듯이 확인하는 방법이다. 시간순으로 들어오는 데이터들을 마치 창문이 미끄러지듯이 읽으면서 질의에 대응하는 모습 때문에 이런 이름이 붙었다 Counting Bits Counting Bits 문제는 Sliding Window 개념을 응용해서 k

빅데이터를 다뤄야 하는 많은 상황들에서, 데이터들은 끊임없이 생산되어 들어오고 이 데이터들을 저장하고 처리하기 위한 메모리는 한정되어 있기 떄문에 이들을 전부 저장할 수 없는 경우가 많다. 따라서 데이터들을 일종의 Stream으로 보고 이들을 관리하는 것이 중요하다. 이를 Stream Management라고 하는데, Stream Management에서는 데이터를 무한히 많고, 정적이지 않은(non-stationary) 즉, 데이터의 분포가 계속해서 바뀌는 성질의 것을 받아들인다. The Stream Model 데이터를 처리하는 기본적인 모델인 Stream Model은 위와 같이 구성이 된다. 이는 여러 가지 특성을 지니는데, 입력되는 데이터 값들(input elements)은 빠른 속도로 입력이 되고, ..

Data Mining 을 시작하기 전에 필요한 기본 지식들을 정의하고 나서 본격적인 Data Mining Algorthm들을 살펴보려고 한다. Data Mining Chapter에서는 쥬어 레스코벡의 "빅데이터 마이닝" 교재를 참고하였으며, 서울대학교 컴퓨터공학부 강유 교수님의 "데이터마이닝 개론" 수업을 참고하였다. 이번 포스팅에서는 데이터 마이닝을 이해하기 위한 기본 툴 중의 몇 가지에 대한 간단한 설명을 하게 될 것이다. Importance of Words in Documents 우리가 구글과 같은 검색 엔진에서 검색 쿼리를 보낼 때, (쿼리는 데이터베이스나 서버 등에 정보를 요청하는 것) 주로 키워드나 키워드의 조합을 통해 쿼리를 보낸다. 이때, 하나의 키워드와 관련된 문서들이나 블로그들이 무수히..