2019년 1학기 고려대학교 강재우 교수님 데이터 과학 정리
4 V’s of Big Data
- Volume(용량) — Scale of data
- Variety (다양성)— Different forms of data
- Velocity(속도) — Analysis of streaming data
- Veracity(진실성) — uncertainty of data
Science Paradigms
예전에는 top-down approach 였다면, 이후엔 bottom-up approach(Data-driven Science)
Big Data Challenges
- 효율적인 저장과 접근 (Infrastructure level challenge)
- 의미있는 정보를 얻어내기 위한 데이터 분석 (size가 커질수록 어려워짐)
Big Data as Bad Data
거대한 data sets은 design(top-down 방식으로 얻은 data) 보다는 opportunity에 의한 결과인데 대표적이지 않거나(unrepresentative participation — bias), 스팸/ machine-generated 콘텐츠라는 문제점이 있다.
Power-laws(멱법칙)은 많은 중복을 의미하고(많은 수의 엠파이어 스테이트 빌딩 사진이 있지만 다른 빌딩 사진은 존재하지 않음), temporal bias 에 민감하다(구글의 검색어 자동완성이 검색 쿼리의 분포 바꿈).
Large-Scale Machine Learning
우리가 일반적으로 배우는 학습 알고리즘은 거대한 data set에 잘 적용되지 않는다.
- 적은 parameter의 모델은 많은 examples의 이점을 보지 못한다. (If model is simple, no need big data)
- 알고리즘의 복잡도는 많은 데이터 셋을 돌리기 위해 선형에 가까워야한다. 하나의 샘플을 처리하는데 드는 비용을 c라고 하고, training set의 size를 n 이라고 할때 n*c를 epoch 라고 한다.
- 큰 행렬은 드문게 좋다.
Filtering Data
빅데이터에서 중요한 이점은 분석을 더 클린하게 하기 위해 많은 부분을 제거해도 된다는 점이다. 트위터에 영어 계정(34%)이 아닌 것들을 모두 제거하더라도 유의미한 분석을 위한 충분한 데이터를 남길 수 있다. 관련 없거나 해석하기 어려운 데이터를 제거할 때는 application-specific 한 지식이 필요하다.
Subsampling Data
Random 하게 고르는 것으로 특정 영역의 지식이 없이도 가능하다.
- training, testing, evaluation 데이터를 clean하게 나눠야 한다. 이를 위해선 중복된 데이터 제거 작업이 필요하다.
- 적은 파라미터수를 가진 간단하고, robust한 모델은 빅데이터가 굳이 필요하지 않다.
- Spreadsheet-sized data sets은 빠르고 쉽게 탐색할 수 있다.
Subsampling by Truncation
처음 n개의 record만 취하는 것도 subsampling 의 방법이지만 종종 record의 순서가 유의미한 경우도 있다.
- temporal biases : 시간적 편향. 오래된 데이터만 분석할 수 있다.
- lexicographic biases : 사전 편찬상의 편향. A로 시작하는 것만 분석할 수 있다. 따라서 중국인보다 아라비안 이름을 더 많이 취할 수 있다.
- numerical biases : 숫자 편향. ID 번호가 뜻을 encode 할 수도 있다. 주민 등록 번호같은 경우 생년월일이나 주소, 성별이 인코딩 되어있기에 지역, 성별, 나이 등으로 편향된 정보를 취할 수도 있다.
Stream Sampling
Stream 한 데이터(로그처럼 계속 생성되는 경우)의 전체 n을 모르는 상태로(do not know how many sample there will be) size k의 일정한 sample 를 계속 얻고 싶을 수 있다.
방법은 k active elements의 array를 가지고 있다가 마지막(nth) element가 들어왔을때, 기존의 elements 중 하나를 새롭게 들어온 element로 대체 시킬지 k/n 의 확률로 결정한다. 만약 대체됨으로 결론났다면 대체될 기존 element의 위치는 랜덤하게 고른다.
Distributed vs. Parallel Processing
machine들이 얼마나 밀접하게 결합되어 있는가에 따라 이 둘을 구분지을 수 있다.
- 병렬처리는 thread와 OS process들을 통해 하나의 머신에서 발생한다.
- 분산 처리는 네트워크 커뮤니케이션을 이용해 다수의 머신에서 발생한다.
쉬운 parallel job들은 많은 커뮤니케이션을 하지 않는다. (프로세스간 많은 영향을 주지 않는다)
Data Parallelism
여러대의 machine에 빅데이터를 나눈 후,독립적인 모델을 train 시킬 때 병렬 처리를 이용한다. 하지만 이렇게 나온 결과를 합치는 것은 일반적으로 어렵다. (k-means를 생각해보자)
- 일단 master 가 initial centroid 를 결정
- slave에게 centroid 정보 알려줌
- 각 slave에서는 가장 가까운 centroid들에 points 할당
- slave에서 local하게 새로운 centroid 만든 후 master에게 보고
- master은 weighted(slave에 할당된 data 개수 고려) average를 통해 local하게 계산된 centroid를 합침.
- step 2 로 이동
Grid Search
독립적인 데이터에 대해 독립적인 시행을 할 때에도 병렬처리를 이용할 수 있다.
Grid search는 k-means 클러스터링에서 알맞은 k 를 결정하는 것과 같이 training에서의 알맞은 hyper parameter를 찾기 위한 것이다.
다수의 독립적인 fits(각기 다른 하이퍼 파라미터)는 병렬적으로 수행되며 이후에 가장 좋은 것이 채택된다.
One, Two, Many..
분산 처리에서 복잡도(complexity)는 machine의 개수에 따라 급격히 올라간다.
- One : CPU 의 cores를 busy하게 유지한다.
- Two : 몇몇 CPU에서 수동으로 프로그램을 관리해줘야한다.
- Many : 효율적으로 다수의 머신을 관리하기 위해 MapReduce와 같은 시스템을 채택해야한다.
MapReduce / Hadoop
구글의 분산 컴퓨팅을 위한 MapReduce 패러다임은 Hadoop 이나 Spark 와 같은 오픈소스 구현으로서 널리 퍼져있으며 다음과 같은 기능을 제공한다.
- 간단한 병렬 프로그래밍 모델
- 수백, 수천개의 머신으로의 간단한 스케일링
- 중복을 통한 고장 허용(Fault tolerance through redundancy)
Divide and Conquer
Typical Big Data Problem
- 많은 record 들에 대한 반복
- 각각에 대해 흥미로운 정보 추출
- 중간의 결과의 Suffle & Sort
- 중간 결과의 합
- 최종 결과 도출
word counting 과 k-means 클러스터링 생각해보자.
위키피디아 같이 각 document에 대한 정보들이 있다고 하면, 작은 조각들로 나눠서 다수의 머신에 할당한 후 나중에 count를 combine 할 것이다.
Ideas Behind MapReduce
- Scale “out”, not “up”. (전자는 병렬적으로 기계의 개수를 늘리는 것, 후자는 좋은 CPU나 RAM 등과 같이 기계의 사양을 높이는 것)
- processing을 data로 옮김 : 클러스터는 bandwidth 가 한정되어 있다. 큰 data를 컴퓨터에 옮기는 대신(많은 시간 소요) 프로세싱을 데이터로 옮긴다.
- 순차적으로 data를 처리하고 random access를 지양
Components of Hadoop
Core Hadoop은 두가지 메인 시스템이 있다.
- Hadoop/MapReduce : 빅데이터 분산 처리 infrastructure (abstract/paradigm, fault-tolerant, schedule, execution)
- HDFS(Hadoop Distributed File System) : 고장 허용(fault-tolerant), 높은 bandwidth, 분산 스토리지의 높은 가용성(high availability distributed storage)
Map and Reduce
map과 reduce의 두가지 function이 있다.
같은 key를 가진 모든 값은 같은 reducer에게 할당된다.
MapReduce Word Count
Map : text에 있는 각각의 단어 w에 대해 Emit(w,1). 이때 w는 key값이 되고, 1은 value 값이 된다.
Word Count Execution
‘the quick brown fox’ 같은 하나의 document는 하나의 머신에서 처리되고, (the, 1), (brown, 1), (fox,1)의 key, value pair로 매핑된다. 그 후 같은 키값을 가진 pair는 동일한 reducer 로 가서 합쳐진다.
Word Count with Combiner
동일한 매퍼에서 같은 key 를 가진 pair가 나오면 Combiner에 의해 합쳐진 후 reducer로 간다.
MapReduce “RunTime”
- 스케줄링 처리 : map & reduce 작업을 위해 worker를 할당한다. 자동적으로 schedule 되므로 수동적으로 assign 할 필요가 없다.
- 데이터 분산 처리 : 프로세스를 데이터 쪽으로 옮긴다.
- 동기화 처리 : 중간의 데이터를 모으고, 정렬하고, 섞는다.
- 에러 처리 : worker 의 실패(불가피한 것)를 감지하고 재시작한다.
Hadoop Distributed File System(HDFS)
RAM은 모든 데이터를 저장하기에 충분하지 않기 때문에 클러스터에서는 노드의 로컬 디스크에 데이터를 저장한다.
디스크 access는 느리지만, 처리량(throughput)이 적절하기에 파일의 linear scan이 가능하다.
상용하드웨어에 대한 신뢰성을 위해 모든 것에 대해 3개의 복제를 진행한다.
