Strategy
- Dimensionality reduction
- wavelet transform
- Pincipal components analysis (PCA)
- Feature subset selection, feature creation
- Munerosity reduction (data reduction)
- regression
- histograms, clustering, sampling
- data cube aggregation
- Data compresison
Curse of dimensionality
차원이 증가하면 데이터는 점점 sparse하게 공간을 차지하게 된다.
sparse해지기 때문에 앞서 배운 distance가 작아져 데이터들간의 distance가 의미가 거의 없어지게 된다.
차원이 $d$인 hypercube(초입방체) 내부에 반지름이 $r$인 구가 내접한다고 하자.
hypercube의 부피는 $(2r)^d$이고, 구의 부피는 $\cfrac{2r^d \pi^{d/2}}{d\Gamma(\frac{d}{2})}$이므로
구 안의 정사각형의 부피비는 $\cfrac{\pi^{d/2}}{d2^{d-1}\Gamma(\frac{d}{2})}$이다. $d \to \infty$가 되면 이 부피는 $0$으로 수렴한다. 이때문에 distance function은 고차원에서 의미를 잃는다.
출처: https://en.wikipedia.org/wiki/Curse_of_dimensionality
Data Reduction 1 - Dimensionality Reduction
- 차원의 저주 피하기
- 데이터 마이닝 알고리즘을 적용할 때 소모되는 시간과 메모리를 줄이기 위해
- 데이터 시각화에 용이하기 위해
- 상관없는 특징(irrelevant feature)를 제거할 수도 있다.
Principal Component Analysis, PCA
주성분(principal component)는 분산이 가장 큰 방향의 고유벡터를 갖는다.
eigenvector는 방향성을, eigenvalue는 데이터의 (eigenvector 방향의) 분산을 갖는다.
주성분의 개수는 원 데이터의 차원보다 적거나 같으므로 dimensionality reduction 효과를 갖는다.
Feature Selection
데이터의 차원을 축소하는 다른 방법은 중복되거나 상관없는 데이터를 제거하는 것이다.
- Redundnat features
- 여러 attribute에서 나타나는 데이터가 중복 또는 포함할 수 있다.
- 예를 들어, 제품 가격과 판매 세금은 중복된 데이터이다.
- Irrelevant features
- 데이터 마이닝을 할 때 전혀 정보가 없는 데이터
- student ID는 학생의 성적을 예측하는데 전혀 도움이 되지 않는다.
Attribute Subset Selection
목적은 minimum set of attributes를 찾는 것이다. $n$개의 attribute의 경우 최대 $2^n$개의 subset이 존재하는데 이것을 모두 확인할 수는 없다. 따라서 heuristic한 방법으로 subset을 찾는 방법이 많이 사용된다.
Stepwise forward selection
best attribute를 반복적으로 선택하여 subset을 구성한다.
Stepwise backward selection
worst attribute를 반복적으로 제거하여 subset을 구성한다.
Combination of forward selection and backward elimination
Decision tree induction
information gain에 따른 decision tree를 이용한다.
Discrete Wavelet Transform, DWT
wavelet은 연속적인 신호를 여러개의 신호 크기로 분해하는 함수이다.
이제 신호의 위상을 데이터로 생각하여 데이터를 분해할 수 있다.
Haar Wavelet
4개의 신호(이자 데이터)가 $[9, 7, 3, 5]$가 주어져있다. 이때 pairwise average를 통해 새로운 average 배열을 만들고, 동시에 coefficient 차이를 저장한다.
예를 들어, $9, 7$의 평균인 $8$과 $3, 5$의 평균인 $4$를 저장하고, 이렇게 구한 평균에서 뒷 데이터를 뺀 값($8-7=1, 4-5=-1$)을 저장한다.
이렇게 최종적으로 얻은 데이터는 $[6, 2, 1, -1]$이고 wavelet을 이용하여 원래 데이터인 $[9, 7, 3, 5]$로 복원할 수 있다.
그러면 데이터를 줄이는 것은 어떻게 하느냐?
| Resolution | Averages | Detail Coefficients |
| 8 | $[2, 2, 0, 2, 3, 5, 4, 4]$ | |
| 4 | $[2, 1, 4, 4]$ | $[0, -1, -1, 0]$ |
| 2 | $[1.5, 4]$ | $[0.5, 0]$ |
| 1 | $[2.75]$ | $[-1.25]$ |
이 경우 wavelet transform 데이터가 $[2.75, -1.25, 0.5, 0, 0, -1, -1, 0]$이다. 이때 $0$이나 매우 작은 숫자들은 무시할 만 하다. 따라서 small value들을 truncate, remove 하여 재복원하면 원래 데이터인 $[2, 2, 0, 2, 3, 5, 4, 4]$에 가까운 숫자 분포를 얻게 된다.
Data Reduction 2 - Numerosity Reduction
- Parametric methods: 데이터가 어떤 모델에 fit하다고 가정하고, 그 모델의 파라미터를 구하는 방법이다.
- linear regression
- Non-parametric methods: 어떠한 모델을 가정하지 않는다.
- histograms, clustering, sampling, ...
Linear Regression
독립변수와 종속변수로 나누어 데이터에 best fit한 모델을 찾는 분석이다.
가장 많이 사용되는 평가지표는 least squares method이고 다른 방법들도 사용된다.
Sampling
모집단의 지식을 얻기 위한 subset을 구하는 방법이다. 샘플링을 하는 이유는 mining algorithm의 complexity가 가급적 선형시간을 갖도록 하기 위함이다.
skew한 데이터의 경우 단순 random sampling은 좋지 않은 성능을 가질 수 있다.
- Simple random sampling
- Simple random sampling without replacement (SRSWOR)
- Simple random sampling with replacement (SRSWR)
- Statified sampling
Stratified Sampling
각 층(stratum)의 비율에 맞추어 샘플링을 하는 방법이다.
데이터에 youth가 4명, middle_aged가 8명, senior가 2명 총 14명이라 할 때 7명을 sampling한다고 하자. youth, middle_age, senior의 비율에 맞추어 뽑으면 각각 2, 4, 1명씩 뽑으면 된다.
대량 (표본 수) $\times$ (class 비율) 이라고 생각하면 된다.
youth의 경우, $7 \times \frac{4}{14} = 2$, middle_aged의 경우 $7 \times \frac{8}{14} = 4$, senior의 경우 $7 \times \frac{2}{14}=1$이다.
Data Reduction 3 - Data Compression
데이터를 보다 더 적은 비트수를 이용하여 저장하는 방법이다.
데이터 크기 뿐만 아니라, query performance에도 많은 효과를 보인다.
대부분의 data warehouse system은 데이터를 load할 때 data compression 과정을 거친다.
Run-Length Encoding
일반적으로 문자열을 압축할 때 쓰는 간단한 알고리즘이다.
이를 확장하여 제품에 대한 데이터 product id가 1차원 배열로 이어진다고 하자. 그러면 run-length encoding을 적용하면 압축된 데이터는 (value, start_pos, run_length)를 갖게 된다.
예를 들어, $[1, 1, 1, 1, 1, 2, 2, \cdots,1, 1, 1, 2, \cdots]$같은 배열이 있다고 하자. 이를 압축하면
\[ [(1, 1, 5), (2, 6, 2), \cdots, (1, 301, 3), (2, 304, 1), \cdots] \]
와 같이 저장할 수 있다.
Dictionary Encoding
unique value(possible value)가 작을 때 유용하다.
'스터디 > 데이터사이언스' 카테고리의 다른 글
| [Data Science] Association Rule Mining (1) - Introduction (0) | 2023.04.01 |
|---|---|
| [Data Science] Data Preprocessing (5) - Data Transformation (0) | 2023.03.28 |
| [Data Science] Data Preprocessing (3) - Data Integration (0) | 2023.03.28 |
| [Data Science] Data Preprocessing (2) - Data Cleaning (0) | 2023.03.28 |
| [Data Science] Measuring Data Similarity and Dissimilarity (0) | 2023.03.22 |
