데이터 마이닝- 1. intro

데이터 마이닝

• 큰 데이터집합으로부터 의미 있는 정보를 추출하는 일

데이터 마이닝 method

• Descriptive methods: 데이터를 묘사하기 위해 인간이 해석가능한 패턴을 찾는 방법
• Predictive methods:  알려지지 않은 것, 미래값을 예측하는 방법

 

* Issue

1. 네트워크로 데이터를 복사하는 건 오래 걸린다

-> 해결방안

• 계산을 데이터가 있는 곳으로 보낸다.
• 데이터를 중복해서 여러 곳에 보관한다.
  -> 분산 컴퓨팅
• spark/Hadoop이 이 문제를 해결할 수 있는 모델
  -> 저장 인프라 제공
  프로그래밍 모델 제공: MapReduce

2. 만약 노드가 실패한다면, 어떻게 데이터를 영구적으로 보관할까?

-> 해결방안

• 분산 파일 시스템
  -> 가능한 패턴
  1. 큰 파일
  2. 거의 업데이트하지 않아도 되는 데이터
  3. 읽기와 덧붙이기가 흔한 데이터

 

 

분산 파일 시스템

• Chunk server: 파일이 분산되어 저장돼 있는 덩어리 서버
  각 chunk는 보통 2~3개 복제되어 서로 다른 랙에 보관해 놓는다.
  -> 같은 렉에 보관하면 분산의 의미가 떨어 
• Master node: 파일이 어디 보관되어 있는지(어느 Chunk server에 보관되어 있는지)에
  대한 데이터(metedata)가 보관되어 있다.
  -> client에게 chunk server가 어디에 있는지만 말해줌. 혹은 바로 연결
  (서버 부하를 막기 위해 직접 가져다주지는 않는다.)

 

 

MapReduce

• 병렬프로그래밍
• 하드웨어와 소프트웨어의 결함을 관리해 준다.
• 큰 데이터들을 관리해 준다.

MapReduce 3단계 방법

1. Map: 각각의 input들에 Map function(정해진 규칙에 맞게 분류)을 적용한다.
-> output은 key-value 쌍

2. Group by key: output들을 정렬한다.

3. Reduce: output들에 Reduce function(key에 속하는 모든 값들을 합친다)을 적용한다.

예) Word Counting

Map worker(Map을 실행하는 장치)가 실패했을 경우

• Map을 완료했거나 아직 진행 중이었을 때 서버가 다운된 경우
  -> 다른 장치에서 리셋 후 다시 시작하도록 한다.
  * 완료했는데도 다시 시작하는 이유
  1. 완료된 걸 로컬에 저장하면 되지 않는가?
   -> 다른 장치로 파일을 보내려고 할 때 시간이 오래 걸린다.
  2. 완료된 걸 Reduce 단계로 바로 보내면 되지 않는가?
  -> Reduce를 진행하고 있던 장치도 하던 일이 있다. 그러므로 갑자기 받기 힘들다.
  
  

MapReduce의 문제

1. 많은 문제들은 Map-Reduce로 쉽게 묘사되지 않는다

2. 디스크에서 데이터를 가져오므로 느리다. 

-> spark가 이를 보완
: 중간 결과를 디스크에 저장하지 않고 캐시에 저장

 

MapReduce의 장점

• 연속적인 데이터 접근을 필요로 하는 문제에 효과적
  * 랜덤 데이터 접근을 필요로 하는 문제는 비효화적
• 여러 개 모아놓은 일들(상호작용적이지 않고, 실시간 작업)에 효과적

 

 

Spark

• Key pair 구성
  -> RDD(Resilient Distributed Dataset)로
• RDD: Read-only, 디스크에서 가져오지 않고 메모리에서,
  다른 RDD 변형 가능, 모든 원소들에 같은 작업을 하고 싶을 때 적합
• sql를 지원

 

RDD

• action이 필요할 때까지 계산하지 않는다.
  -> Lazy evaluation
• Transformation 함수들: map, filter, join, union, intersection, distinct
• Action 함수들: count, collect, reduce, save 
• Task Scheduler: General DAGs
  1. 가능한 Pipeline 함수(여러 단계를 묶어서 하나의 단계인 것처럼 추상화하는 기술) 사용
  2. 데이터에 위치를 캐시가 안다
  3. 어떻게 분할되어 있는지 알고 있어 shuffle을 피할 수 있다.

 

DataFrame

• RDD와 달리 데이터가 테이블 형식으로 구성되어 있다.
• 관계형 데이터베이스 형식
• RDD로 변환가능하

 

Dataset

• 타입 안정화, 객체지향 프로그래밍 인터페이스를 제공하는 
  Dataframe의 API

 

Map-Reduce Join

• 조인으로 Map을 하기 위해선 
  (조인하는 칼럼이름, (A칼럼  값, 테이블 이름))으로 구성해야 한다.
  -> group by를 할 때 key값이 같은 걸로 묶기 때문에 key자리에 조인칼럼이름을 넣는다.

위와 같을 때 Map: (b, (a, R))와 (b, (c, S))

Reduce: (a, b, c)

 

 

Cost Measures for Algorithms

• Communication cost: total I/O
  -> 얼마나 데이터를 읽고 썼는가를 알아보기 위해 측정
• Elapsed communication cost: max of I/O
  -> 병렬을 얼마나 잘했나를 알아보기 위해 측정
• (Elapsed) computation cost
  -> 작업의 실행속도(running time)를 알아보기 위해 측정

map-reduce 알고리즘의 Cost Measure 예) 

• Communication cost= input file size + 2* map process로부터 reduce process 할 때까지 
  읽은 파일의 크기(2를 곱하는 이유는 group by key를 할 때 정렬을 하는데 정렬할 때 2번은
  읽어야 하기 때문) + reduce process의 output 크기의 합 
• Elapsed communication cost= 가장 큰 input의 합 + 맵 프로세스의 출력
  +그 출력에 의한 reduce 프로세스의 출력