Data Reduction

• Data reduction하는 이유
• curse of dimensionality
• dimensionality가 커지면 데이터가 엄청 sparse하게 됨.
• 클러스터링을 할 경우, 각 points와의 차이(혹은 distance)가 커야 의미이쓰는데, dimension이 클 수록 유의미한 distance를 구하기가 힘듦. ( Dimensionality가 증가함에 따라서 log((MAX_DIST - MIN_DIST)/MIN_DIST) 가 엄청 작아짐.)
• Dimensionality Reduction
• 동기
• curse of dimensionality를 피할 수 있음
• 데이터 마이닝을 하는데 시간과 메모리 사용량을 줄일 수 있음
• 쉽게 시각화할 수 있음
• 관련없는 features와 노이즈를 제거할 수 있음
• Techniques
• Wavelet transform
• wavelet: 기존 function이나 signal을 다른 scale components로 바꾸는 수학적 function을 말함.
• DWT(Discrete Wavelet transform)
• Haar Wavelet
• one-dimensional Haar wavelet transform
• Pricinple Component analysis(PCA)
• correlated variables를 uncorrelated variables(called principle components)의 set으로 변형시킴.
• principle components의 수는 original variables의 수보다 작거나 같음.
• 가장 큰 variance를 가진 principle component를 가지도록 transformation을 함.
• Feature selection
• redundant하고 irrelevant한 features를 제거함
• 휴리스틱
• Stepwise forward selection
• best single attribute부터 순차적으로 선택함.
• Stepwise backward elimination
• worst attribute를 순차적으로 제거함.
• Combination of forward and backward
• Decision tree induction
• Numerosity reduction
• 다른 data representation을 사용하여 데이터를 표현함으로써 데이터 크기를 줄임
• 종류
• Parametric methods
• ex. regression
• Non-parametric methods
• 모델을 가정하지 않음
• histogram, clustering, sampling
•  Sampling
• 데이터 중에 일부만을 선택하여 사용함
• 종류
• simple random sampling
• sampling without replacement
• sampling with replacement
• stratified sampling
• 비율에 맞추어서 샘플링함
• Data cube aggregation
• 목적에 적합한 기준으로 값을 합침
• 예를 들어, 판매량을 개별적으로 사용하지 말고, 일별, 주별, 월별 판매량을 사용함.
• Data Compression
• 기존 representation보다 적은 bits로 표현할 수 있도록 encoding함.
• disk I/O cost를 줄일 수 있음
• ex. Run-length encoding, Dictionary encoding
• Data transformation
• Normalization
• min-max normalization
• z-score normalization
• Discretization