1. Association Rule Discovery association rule mining은 market-basket model로 불리기도 한다. 목표는 충분히 많은 고객에 대해 함께 구매되는 물품을 찾는 것이다. 예를 들어 빵과 우유와 같은 것은 같이 구매될 확률이 높을 것이다. 이러한 물품의 집합을 찾는다면 다음과 같은 활용이 가능하다. 먼저, 같은 코너에 배치하여 추가 구매를 유도할 수 있다. 또한, 한 물품의 가격을 내리면서 (sale on) 다른 물품의 가격을 올린다면 (raise) 판매량(sales)을 늘릴 수 있다. 실제 market basket에서는 테라바이트 단위의 데이터를 저장한다. 이는 아마존의 상품 추천 시스템에도 사용될 수 있다. X를 샀다면 추천으로 다른 사람들이 많이 구..
1. 개요 (overview) 그래프 데이터는 소셜 네트워크, 정보망, 인터넷 등에 사용된다. 특히 인터넷에서, node를 웹 페이지라고 생각하고 edge를 하이퍼링크라고 생각하면 웹은 방향그래프이다. 웹 서치에서, 어떤 웹 페이지를 신뢰할 것인지, 그리고 키워드 쿼리에 가장 알맞은 페이지는 무엇인지 알 수 있어야 한다. 따라서 그래프에서 각 node의 중요도를 계산하기 위한 link analysis 방법을 다룰 것이다. 이 분석에는 page rank, topic-specific page rank, 스팸 탐지 알고리즘이 포함된다.2. Page rank 한 페이지에서 다른 페이지로 가는 링크를 그래프로 나타내자. 한 페이지의 중요도가 높다는 것은 in-coming link의 개수가 많다는 것이다. 그러나..
1. 개요 (overview) 1.1. 데이터 스트림 (data stream) 데이터 마이닝을 하는 많은 경우에, 특히 데이터가 외부에서 지속적으로 들어올 때, 우리는 데이터셋 전부를 알지 못한다. 웹 브라우저 쿼리 등이 대표적이다. 우리는 이러한 데이터를 무한하고 정적이지 않은, 즉 시간에 따라 분포가 변할 수 있는 데이터로 생각할 수 있으며, 이를 데이터 스트림이라고 부른다. 각 시각에, 데이터는 하나 이상의 입력 포트를 통해 전달되며 (즉, 한 시각에 여러 입력이 주어질 수 있음) 이를 요소(elements) 또는 튜플(tuples)이라고 부른다. 1.2. 스트림에서의 쿼리 (queries) 데이터는 빠른 속도로 들어오기 때문에 메모리는 모든 데이터를 저장하기에 맞지 않고, 디스크는 매번 접근하..
1. 개요 (motivation) 데이터마이닝에서, item들의 유사성을 계산하는 것은 중요하다. 한 예로, 20,000개의 이미지 중 주어진 이미지와 가장 비슷한 10개의 이미지를 찾는 경우를 생각하자. 각 이미지는 수많은 픽셀로 이루어져 있으므로, 이 문제는 high-dimensional space에서 가까운 점을 찾는 문제와 같다. 이외에도, 구매자가 구매한 상품과 비슷한 상품을 띄워야 할 때, 특정 사이트의 미러 사이트를 찾을 때, 특정 기사와 유사한 기사를 찾을 때 비슷한 문제에 직면한다.2. 목표 (goal) 고차원 데이터 \(x_1, x_2, ...\)와 거리함수 \(d\), 특정 역치 \(s\)에 대하여, 거리가 특정 역치보다 짧은, 즉 \(d(x_i, x_j)\leq s\)을 만족하는 데..
1. 문서에서 단어의 중요도 계산하기 (importance of a word) 1.1. 왜 중요한가? Search engine에서, 특정 단어가 등장하는 문서는 수없이 많다. 그러나 그 단어가 각 문서 내에서 중요할 수도, 중요하지 않을 수도 있다. 이때, 단어의 중요도를 계산할 수 있다면 그 단어의 중요도가 더 높은 문서들을 더 상단에 rank할 수 있다. 1.2. TF.IDF TF.IDF는 한 문서 \(j\)에서 특정 단어 \(i\)의 중요도를 판단하는 대표적인 척도이다. 먼저, TF(Term Frequency)는 문서 \(j\)에서 가장 많이 나타나는 단어 대비 특정 단어 \(i\)가 나타나는 빈도이다. 항상 \(0\)과 \(1\) 사이 값을 갖는다. \[TF_{ij}=\frac{f_{ij}}..
