chapter 3. Filtering Patterns

Presentation on theme: "chapter 3. Filtering Patterns"— Presentation transcript:

1 chapter 3. Filtering Patterns
서울시립대학교 전기전자컴퓨터공학과 G 이가희 Data mining Lab. 병렬소프트웨어설계

2 0. Contents filtering bloom filtering top 10 distinct
Filtering Patterns 0. Contents filtering bloom filtering top 10 distinct

3 1. Filtering : Pattern Description
Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 1. Filtering : Pattern Description 관심 없는 레코드들은 필터링 단계에서 버림 큰 데이터를 쪼갠 데이터에서 관심 있는 것만 후속 분석을 하고 싶을 때 수행 레코드 단위 파싱, 높은 분류 성능 필터링 결과 : 선택 기준들을 통과한 레코드들의 subset closer view of data / distributed Grep / data cleansing / simple random sampling f true false an evaluation function 레코드 유지 레코드 버림 관심 있는 레코드만 취함

4 1. Filtering : Pattern Description
Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 1. Filtering : Pattern Description no “reducer” map-only 잡이기 때문에 효율적이다. 데이터가 맵과 리듀스 단계 간에 전송될 필요가 없다. 또한 정렬 단계와 리듀스 단계가 제외된다.

5 1. Filtering : Pattern Examples
Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 1. Filtering : Pattern Examples Distributed Grep 입력 파일로 주어진 파일 내에 존재하는 특정한 문자열 패턴을 추출 입력 파일 : hotlist.txt regex ? .

6 1. Filtering : Pattern Examples
Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 1. Filtering : Pattern Examples Distributed Grep : mapper null 입력 : <, hotlist.txt record> 출력 : <null, record> map에서 필요한 변수 선언 map에서 필요한 resource 할당 (파일 검색 방법으로 정규식 설정) context : job과의 통신 및 입출력 담당 특정 패턴에 매칭되는 라인 리턴 (key, record)

7 1. Filtering : Pattern Examples
Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 1. Filtering : Pattern Examples Distributed Grep : driver

8 1. Filtering : Pattern Examples
Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 1. Filtering : Pattern Examples <regex> <input> <output> h.* .

9 1. Filtering : Pattern Examples
Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 1. Filtering : Pattern Examples Simple Random Sampling (SRS) 각각의 파일에서 일정 비율만큼 랜덤 추출 0~100 % ? .

10 1. Filtering : Pattern Examples
Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 1. Filtering : Pattern Examples Simple Random Sampling (SRS) : mapper 입력 : <, hotlist.txt record> 출력 : <null, record> map에서 필요한 resource 할당 (파일 검색 방법으로 비율(%) 설정) 조건에 맞는 라인 리턴 (key, record)

11 1. Filtering : Pattern Examples
Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 1. Filtering : Pattern Examples Simple Random Sampling (SRS) : driver 입력한 수 호출 (0~100)

12 1. Filtering : Pattern Examples
Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 1. Filtering : Pattern Examples <percentage> <input> <output> 100 records 20 records .

13 2. Bloom Filtering : Pattern Description
Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 2. Bloom Filtering : Pattern Description Bloom filter : 원소가 집합에 속하는지 효율적으로 테스트 할 수 있는 자료구조 이 집합에 A가 있는가? 없는가? ‘h의 해시 값이 빈 곳을 가리키고 있기 때문에 bloom filter에는 h가 없어!’ 집합에 원소를 추가하는 것은 가능하나, 집합에서 원소를 삭제하는 것은 불가능하다. 집합 내 운소의 숫자가 증가할수록 긍정 오류 발생 확률도 증가한다. False Positive 존재 bloom filter (m=50, k=3)

14 2. Bloom Filtering : Pattern Description
Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 2. Bloom Filtering : Pattern Description a는 꼭 남아 있어야 해! f는 필요없어 버려! hot value! a,b,c,d,e 어떤 값들을 미리 멤버로 정의한 레코드들을 유지하고 싶을 때 : hot value 집합에 해당 data가 들어있는 유무를 판단하는 기준으로 bloom filter를 이용 데이터는 레코드들로 분리될 수 있다. (filtering) hot value를 각각의 레코드에서 추출할 수 있다. (특징 추출) hot value를 위한 item set을 미리 결정해둘 수 있다. False Negative는 절대 일어날 수 없다.

15 2. Bloom Filtering : Pattern Description
Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 2. Bloom Filtering : Pattern Description structure : training + actual filtering bloom filter에 원소 추가 bloom filter 원소 유무 확인 새로운 data에 대한 해시 값 계산 후 비트 값 읽기 data가 bloom filter에 존재하는지 검사

16 2. Bloom Filtering : Examples
Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 2. Bloom Filtering : Examples 주어진 사용자 코멘트 목록에 대해 특정 키워드를 갖고 있지 않은 코멘트를 걸러내라 train data : a Bloom filter is trained with a hot list of keywords (100 terms) test data : inputComments.txt (Id, PostId, Score, Text, CreationDate, UserId) .

17 2. Bloom Filtering : Examples
Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 2. Bloom Filtering : Examples Bloom filter training inputFile (.gz) numMembers (training data 개수) falsePosRate (False Positive rate) bfFile (최종 bloom filter) bloom filter의 m, k 설정 bloom filter 생성

18 2. Bloom Filtering : Examples
Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 2. Bloom Filtering : Examples Bloom filter training training할 file 읽기 (hotlist) bloom filter에 data 추가 (training) bloom filter를 file형태로 내보냄

19 2. Bloom Filtering : Examples
Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 2. Bloom Filtering : Examples <inputfile> <nummembers> <falseposrate> <bfoutfile> .

20 2. Bloom Filtering : Examples
Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 2. Bloom Filtering : Examples Bloom filtering 주어진 사용자 코멘트 목록에 대해 특정 키워드를 갖고 있지 않은 코멘트를 걸러내라 inputComments.txt Id, PostId, Score, Text, CreationDate, UserId hotlistwords.bf

21 2. Bloom Filtering : Examples
Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 2. Bloom Filtering : Examples Bloom filtering : mapper 입력 : <, inputComments record> 출력 : <record, null> 인스턴스 생성 the ≠The

22 2. Bloom Filtering : Examples
Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 2. Bloom Filtering : Examples Bloom filtering : driver reduce task 사용하지 않음 job에 입력한 파일 위치 정보를 보냄 출력 파일이 저장될 위치 정보를 보냄 분산 캐시에 등록

23 2. Bloom Filtering : Examples
Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 2. Bloom Filtering : Examples Bloom filtering : <cachefile> <input> <output>

24 3. Top Ten : Pattern Description
Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 3. Top Ten : Pattern Description 데이터들을 순위를 매겨 상위 K개의 레코드들만 검색하고 싶을 때 사용 활용 이상치 분석 가장 관심 있는 레코드 선별 구체적인 기준에 가장 부합하는 레코드 선별

25 3. Top Ten : Pattern Description
Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 3. Top Ten : Pattern Description mapper, reducer 관심 있는 레코드만 취함 find local top ten setup / map / cleanup setup / reduce 리듀서가 너무 많은 데이터를 가지고 있으면 성능이 좋지 않다 1개의 reducer 10*M record -> the final top ten

26 3. Top Ten : Examples Filtering Patterns 1 filtering 2 bloom filtering
4 distinct 3. Top Ten : Examples 주어진 사용자 정보 목록에서 Reputation을 기준으로 top 10 사용자 정보를 출력하라 input data : inputUser.txt (Id, Reputation, CreationDate, DisplayName, …)

27 3. Top Ten : Examples Filtering Patterns 1 filtering 2 bloom filtering
4 distinct 3. Top Ten : Examples Top Ten : mapper 입력 : < , inputUsers record> 출력 : <null, local top10 record> treemap 생성 (키를 기준으로 정렬 가능) (내림차순) 10위 이상이면 해당 레코드 버림

28 3. Top Ten : Examples Filtering Patterns 1 filtering 2 bloom filtering
4 distinct 3. Top Ten : Examples Top Ten : mapper 마무리작업 (최종적으로 남은 레코드를 리듀서로 전송) (null key)

29 3. Top Ten : Examples Filtering Patterns 1 filtering 2 bloom filtering
4 distinct 3. Top Ten : Examples Top Ten : reducer 입력 : <null, local top10 record > 출력 : <null, final top10 record>

30 3. Top Ten : Examples Filtering Patterns 1 filtering 2 bloom filtering
4 distinct 3. Top Ten : Examples Top Ten : driver reducer의 수 = 1

31 3. Top Ten : Examples Filtering Patterns 1 filtering 2 bloom filtering
4 distinct 3. Top Ten : Examples <input> <output> . .

32 4. Distinct : Pattern Description
Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 4. Distinct : Pattern Description 유일한 값들만 모인 집합을 구하고 싶을 때 사용 중복제거 / 내부 조인 급증 방지 무작위 파티셔닝 (순서 유지 불가능) reducer 수는 필요한 만큼 사용 reducer 개수 = reduce 슬롯 수*2 값만 출력 (중복 데이터 처리) 값에 대한 키값 출력

33 4. Distinct : Pattern Example
Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 4. Distinct : Pattern Example 주어진 사용자 코멘트 목록에서 사용자 id를 구별한 집합을 구하라. test data : inputComments.txt (Id, PostId, Score, Text, CreationDate, UserId) mapper : 각각의 입력 레코드에서 UserId를 얻는다. combiner : 중복 키 제거 reducer : 입력 받은 레코드에서 키를 파일 시스템에 출력

34 4. Distinct : Pattern Example
Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 4. Distinct : Pattern Example Distinct : driver

35 4. Distinct : Pattern Example
Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 4. Distinct : Pattern Example Distinct : map 입력 : < , inputComments record> 출력 : <UserId, >

36 4. Distinct : Pattern Example
Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 4. Distinct : Pattern Example Distinct : reducer 입력 : <UserId, > 출력 : <UserId, >

37 4. Distinct : Pattern Example
Filtering Patterns 1 filtering 2 bloom filtering 3 top ten 4 distinct 4. Distinct : Pattern Example <input> <output> .

38 End