[Data Reduction] Numerosity Reduction

Numerosity Reduction

기존과 다른 형태로 데이터를 표현함으로써 데이터의 크기를 줄이는 방법이다.

 

• Parametric method
  • data에 fit하는 모델을 생성하고 그의 파라미터만 저장한다.
  • 파라미터만 저장하기 때문에 outlier은 무시된다.
  • 모델이 데이터와 맞지 않으면 결과가 전체적으로 무너지는 단점이 있다.
  • 예 : regression
• Non-parametric method
  • 모델을 생성하지 않고 다른 방식으로 데이터를 표현한다.
  • 예 : histogram, clustering, sampling

 

---

Regression Analysis

Independent variable로 dependent variable을 예측하는 모델을 만든다.

• independent variable
  • 결과를 만들어내는 원인이 되는 변수들
  • $y = ax$에서의 x
• dependent variable
  • = response variable 
  • 다른 변수에 의해 결정되는 변수들
  • $y = ax$에서의 y

 

데이터에 가장 fit하는 파라미터를 계산해야 한다.

이를 위해서 주로 least squares method를 사용한다.

Prediction, inference, hypothesis testing, casual relationship modeling 등에 사용되기도 한다.

 

종류

• linear regression : $Y = wX + b$
  • 직선으로 표현
  • dependent variable 1개 → independent variable 1개
• multiple regression : $Y = b_0 + b_1X_1 + b_2X_2 + ...$
  • 직선으로 표현
  • dependent variable 1개 → independent variable 2개 이상
• non-linear regression : $Y = b_0 + b_1X + b_2X^2 + ...$
  • 직선이 아닌 다항식으로 표현
  • $X \rightarrow X_1, X^2 \rightarrow X_2$와 같이 고차항을 다른 변수로 두어서 multiple regression처럼 풀 수 있다.

 

---

Histogram Analysis

Non-parametric reduction method이다.

데이터를 일정 구간으로 나누고 그 구간의 frequency를 막대 형태로 표현한 그래프이다.

 

Partitioning 방법은 크게 equal-with와 equal-frequency로 나눌 수 있다.

• Equal-width : bucket의 range가 동일하도록 나눈다.
• Equal-frequency
  • = Equal-depth
  • 구간에 속하는 데이터들의 frequency가 같도록 나눈다.

 

---

Clustering

Similarity(dissimilarity)를 이용해서 데이터셋을 cluster로 나누고 cluster representation(centroid + diameter)만 저장하는 방법이다.

 

특징

• 데이터의 cluster가 정의되어 있으면 매우 compact하게 데이터를 저장할 수 있다.
• Hierarchical clustering은 multi-dimensional index tree 구조로 저장할 수 있다.
• Clustering의 정의나 알고리즘에 따라 많은 방법이 존재한다.

 

---

Sampling

전체 데이터셋 중 일부의 데이터만 뽑아서 저장하는 방법이다.

데이터 크기에 linear하게 mining complexity를 줄일 수 있다.

 

Key Principle

데이터의 subset을 대표하는 샘플들을 모으는 것이 중요하다.

즉 전체 데이터를 대표할 만한 샘플들을 모으는 것이 중요하다.

 

전체 데이터를 이용한 결과와 sampled data로 나온 결과가 다르면 안좋은 sampling이다.

Stratified sampling을 통한 방법을 사용할 수 있다.

 

Disk I/O

Sampled data가 여러 DB에 저장되어있을 수 있기 때문에 샘플링 방법은 DB I/O를 줄이지 않는다.

그러나 sampled data를 한 곳에 저장하면 disk I/O를 줄일 수 있기도 하다.

 

Sampling Type

• simple random sampling
  • 전체 데이터 중 랜덤하게 뽑는다.
  • 선택될 확률은 전체 데이터가 동일하다.
• Sampling without replacement
  • 뽑은 후 population에서 제거한다.
  • 즉, 한번 뽑힌 데이터는 다시 뽑히지 않는다.
• Sampling with replacement
  • 뽑은 후 population에 다시 넣는다.(제거하지 않는다.)
  • 한번 뽑힌 데이터는 다시 뽑힐 수 있다.
• Stratified sampling
  • 전체 데이터를 기준에 따라 나누고 비율에 맞게 샘플링 한다.
  • 전체 데이터의 distribution과 sampled 데이터의 distribution이 동일하게끔 샘플링하는 방법이다.
  • skewed data를 다룰 수 있다.
• Cluster sampling
  • 한 cluster 전체를 뽑는 방법이다.