병렬소프트웨어설계 Han-joon Kim

Presentation on theme: "병렬소프트웨어설계 Han-joon Kim"— Presentation transcript:

1 병렬소프트웨어설계 2015. 3 Han-joon Kim
Data Mining Lab., Univ. of Seoul, Copyright ® 2015

2 강의 목표 빅데이터 처리/분석를 위한 병렬처리 프로그래밍 프레임워크인 Hadoop MapReduce 알고리즘 설계 방식을 학습
Text Mining 기술 학습 포함 MapReduce 기반 Machine Learning 기법의 최근 연구 내용을 학습

3 강의 홈페이지

4 본 강의의 키워드 Parallel processing Text Mining Big Data Analysis Tool
Hadoop, MapReduce Text Mining Machine Learning Text Analysis Big Data Analysis Tool R RHadoop = rhdfs+rmr+rhbase

5 R Data analysis framework Programming language
데이터 입출력/처리/관리/계산/분석/그래픽 관련 라이브러리의 집합체 Programming language Open-source software project Data analysis community 2백 만명 이상의 users 다양한 도메인의 분석, 도움말, 리소스 등의 교환

6 Rstudio : R 통합개발환경

7 R의 기본 사이트 http://www.r-project.org/ http://cran.r-project.org/

8

9 Hadoop Hadoop (Apache) Hadoop의 주요 구성 요소
컴퓨터 클러스터에서 대용량 자료의 분산처리를 지원하는 자바 소프트웨어 프레임워크 텍스트 검색 라이브러리 Apache Lucene 창시자인 Doug Cutting에 의해 시작 본래 Nutch의 분산 처리를 지원하기 위해 개발 HDFS + MapRecduce HDFS: 분산처리 시스템인 구글 파일 시스템을 대체 Hadoop의 주요 구성 요소 HDFS (Hadoop Distributed File System) MapReduce

10 HDFS 컴퓨터 클러스터에서 대용량 데이터를 저장하기 위한 분산 파일 시스템
Google의 파일시스템기술기반  Hadoop Distributed FS(Apache) 동국대학교 응용통계학과 서울시립대학교

11 Hadoop Architecture

12 If I want to find the most frequency words…
Million articles Million articles Million articles Million articles

13 Hadoop: Word Count Example

14 HDFS (Hadoop Distributed File System)

15 MapReduce Input K1,V1 map K2,V2 reduce K3,V3 output

16 MapReduce 대용량 데이터를 빠르고 안전하게 처리하기 위한 분산 프로그래밍 모델
대용량 데이터를 빠르고 안전하게 처리하기 위한 분산 프로그래밍 모델 HDFS 데이터에 대한 병렬 연산을 지원 (Divide & Recombine) 병렬연산은 Map 함수와 Reduce 함수를 통해 구현 동국대학교 응용통계학과 서울시립대학교

17 MapReduce

18 Problems Map-reduce can resolve
Files are very large. Files are rarely updated. Reduce function should be associative (결합법칙) and commutative (교환법칙).

19 빅데이터 처리관련 패키지 RHIPE(Saptarhis Guha, 2010, 2013)
R and Hadoop Integrated Processing Environment Google protocol buffer: HDFS files ↔ R객체로 변환 R콘솔에서 job status tracking 가능 RHadoop(REvolution Analytics, 2011) rmr: MapReduce 관련 함수 제공 rhdf: HDFS 파일 관리를 위한 함수 제공 rhbase: 분산 데이터베이스인 HBase를 지원하는 함수 제공 동국대학교 응용통계학과 서울시립대학교

20 Google protocol buffer
RHIPE 작동원리 RHIPE - Map/Reduce script - Data object Google protocol buffer 동국대학교 응용통계학과 서울시립대학교

21 RHIPE 특징 Work directly on HDFS files in R
- Google protocol buffer: HDFS files ↔ R객체로 변환 Write MapReduce in R and execute it on Hadoop Provide inter-operability with other languages Must be installed on all data nodes 서울시립대학교 동국대학교 응용통계학과

22 Rhipe / HDFS Function Description rhdel(folders) Delete HDFS files
rhls(path) List HDFS files in a specified path rhget(src, dest) Copying from the HDFS (moves files from the HDFS) to a local directory rhcp(src, dest) Copy files (or folders) on the HDFS rhwrite(list, dest) Write R object of list type to HDFS with sequence format rhread(files) Read key/value pairs from the HDFS rhgetkey(keys, path) Get value associated with a key in a map file 동국대학교 응용통계학과 서울시립대학교

23 RHadoop RHadoop (REvolution Analytics) rmr: MapReduce 관련 함수 제공
rhdf: HDFS 파일 관리를 위한 함수 제공 rhbase: 분산 데이터베이스인 HBase를 지원하는 함수 제공

24 RHadoop

25 RHadoop – word count

26 RHadoop – word count

27 RHadoop – word count

28 Rhadoop – word count

29 교재 Data-Intensive Text Processing with MapReduce, Jimmy Lin and Chris Dyer, 2013 MapReduce Design Patterns, Donald Miner and Adam Shook, 2012 Big Data Analytics with R and Hadoop, Vignesh Prajapati, 2013 Machine Learning with MapReduce 최신 논문

30 Textbook 1: Data-Intensive Text Processing with MapReduce

31 Textbook 2: MapReduce Design Patterns

32 Textbook 2: MapReduce Design Patterns

33 Textbook 3: Big Data Analytics with R and Hadoop

34 Textbook 3: Big Data Analytics with R and Hadoop

35 Textbook 3: Big Data Analytics with R and Hadoop

36 Textbook 3: Big Data Analytics with R and Hadoop

37 Machine Learning & Text Mining
Data Mining Lab., Univ. of Seoul, Copyright ® 2011

38 Machine Learning Algorithms
Supervisor가 개입 Classification technology 좁은 의미의 ML Supervised learning Supervision이 없음 clustering, association analysis Unsupervised learning Data Mining Lab., Univ. of Seoul, Copyright ® 2013

39 Machine Learning 기본 목적 기계학습 (machine learning) 패러다임 물리, 수학, 천문학
빅데이터 분석 대자연, 우주를 형성, 지배하는 법칙 만유인력 법칙 상대성 이론 케플러 법칙 ... 빅데이터를 형성, 지배하는 법칙

40 Machine Learning 기본 목적 추상화 (abstraction) 일반화 (generalization) 모델, 패턴

41 빅데이터 분석 이론적 토대: Machine Learning (기계학습)
감독형 학습 (Supervised Learning) 자동분류 (Classification) => 예측 모델 (Prediction model)의 도출 비감독형 학습 (Unsupervised Learning) 클러스터링 (Clustering), 연관규칙 마이닝 (Association) => 설명 모델 (Description model)의 도출

42 자동분류 Classification

43 자동분류 Classification 학습 알고리즘에 따라 예측(분류) 모델 형태가 다름 k-Nearest Neighbors
Support Vector Machine Statistics (ex) Bayesian Network Decision Trees Neural Network

44 자동분류: Obama vs. Romney 누구의 연설문인가? ? ?

45 자동분류: high vs. low 관광지에서 지출규모는? Low-spender ? ? High-spender

46 Classification Process
Pattern, Model (Intelligence) 학습 데이터 未知 데이터 Least loyal profitable common 과거 데이타 미래 예측 Data Mining Lab., Univ. of Seoul, Copyright ® 2008

47 자동분류: 1단계 학습 (learning) 학습데이터 집합 (training data) = {기 분류문서} 분류모델
(classification model)

48 자동분류: 2단계 분류 (classification)
분류모델 (classification model) 미 분류 문서

49 자동 분류 Classification Decision Tree Support Vector Machine
Bayesian Statistics Naïve Bayes Bayesian Networks Instance-based Learning K-Nearest Neighbor Neural Networks Meta-learning Ensemble (Committee): Bagging, Boosting Expectation-Maximization (EM)

50 학습 알고리즘: Decision Tree 학습 데이터 분류 모델 Credit Analysis 학습 레이블 (클래스)
accept reject salary < 20000 no yes Education in graduate 학습 레이블 (클래스) 학습 데이터 분류 모델

51 학습 알고리즘: Support Vector Machine
경계직선(w  x + b = 0) 기준으로 학습데이터의 값이 양수인 영역과 음 수인 영역으로 나눠짐 양/음 영역의 support vector 간 거리(즉, margin)값을 최대로 하는 W, b 값을 학습 과정을 통해 추정함

52 학습 알고리즘: Support Vector Machine
선형적으로 불가능한 문제 Kernel 함수를 통해 선형적으로 가능한 공간(차원 확장)으로 매핑

53 학습 알고리즘: Naïve Bayes Pr(c|d)를 가장 크게 하는 카테고리 c는 ? ci cj ck 문서 d 추정 확률분포

54 학습 알고리즘: k-Nearest Neighbors
+ - - 학습 데이터 ? - + - + - 미분류 데이터 Voting 적용 다른 Decision tree, SVM, Naive Bayes 와 같은 명시적 분류 모델을 만들지 않음 테스팅 단계에서 각 ‘테스트’ 데이터와 학습데이터들간의 ‘거리’ 값을 계산 Lazy Learning

55 학습 알고리즘: Neural Networks
Learning Data Mining Lab., Univ. of Seoul, Copyright ® 2008

56 학습 알고리즘: meta-learning
② 각 학습데이터를 가지고 예측모델을 생성 (machine learning 학습알고리즘) ③ 생성된 예측모델을 종합한 예측모델을 생성 (관련기술: Bagging, Boosting 메타 학습알고리즘)

57 Regression vs. Classification
주어진 데이터에 대한 “연속형 수치 데이터(continuous numeric data)” 의 예측 예: 직원 임금, 고객 가치, 키에 따른 몸무게 Classification 범주화 주어진 데이터에 대한 “카테고리(category)” 또는 “카테고리의 소속 확 률”의 예측

58 군집분석 Clustering

59 군집분석 Clustering 여행을 즐기는 직장인 골프를 즐기는 부자 노년층

60 Data Mining Lab., Univ. of Seoul, Copyright ® 2008
Clustering의 용도 Summarization of large data Understand the large customer data Data organization Manage the large customer data Outlier detection Find unusual customer data Classification/Association Rule Mining의 전 단계 Data Mining Lab., Univ. of Seoul, Copyright ® 2008

61 Data Mining Lab., Univ. of Seoul, Copyright ® 2008
Clustering의 용도 Classification의 전 단계 의미 있는 cluster로부터 class를 도출 Association mining의 전 단계 Cluster 내부의 데이터에 대하여 association mining을 수행 Data Mining Lab., Univ. of Seoul, Copyright ® 2008

62 질의Data Mining Lab., Univ. of Seoul, Copyright ® 2008
Clustering의 용도 정보 검색 Information Retrieval 관련 관련 문서의 검색에 응용 검색 결과의 재구조화 새로운 문서 카테고리 또는 주제의 발견 질의 한 cluster내에 존재하는 문서는 “relevant” 문서 질의Data Mining Lab., Univ. of Seoul, Copyright ® 2008

63 Clustering의 용도: 검색결과의 재구조화
Clusty.com vivisimo incorp. Data Mining Lab., Univ. of Seoul, Copyright ® 2008

64 Data Mining Lab., Univ. of Seoul, Copyright ® 2008
Clustering의 용도: 카테고리 탐지 Manual Automatic Entertainment (Yahoo) Comic&Animation Movie&Film Film Festival FilmMaking Animatoin Computer Animation Anime Comic Books Editorial Cartoons Magazine Comic Strip News&Media Short Films Screen Writing Animated Gifs Conventions Cartoonist Review Magna History Data Mining Lab., Univ. of Seoul, Copyright ® 2008

65 군집분석 알고리즘의 유형 거리함수(distance function) 기반 밀도(density) 기반 계층형 평면형
Hierarchical clustering Complete-linkage Single-linkage Centroid-linkage Average-linkage Ward’s method 평면형 Partitional clustering k-means k-medoids 밀도(density) 기반 DBScan

66 거리함수 Euclidean 거리함수 Manhattan 거리함수 Minkowski 거리함수

67 Data Mining Lab., Univ. of Seoul, Copyright ® 2008
계층형 clustering a b c d e a b c d e d e a b c d e 4step 3step 2step 1step 0step Data Mining Lab., Univ. of Seoul, Copyright ® 2008

68 계층형 clustering Ward’s method Sum of Square Error (SSE) 계산

69 평면형 Clustering: k-means
: centroid (i+1) 단계 Data Mining Lab., Univ. of Seoul, Copyright ® 2008

70 Data Mining Lab., Univ. of Seoul, Copyright ® 2008
밀도기반 Clustering DBSCAN: Cluster를 “density-connected set”으로 정의 density: 정해진 반경()내에 데이터의 개수 Data Mining Lab., Univ. of Seoul, Copyright ® 2008

71 연관분석 Association

72 연관규칙 마이닝 (Association Mining)
장바구니 데이터 분석 (Basket Data Analysis)

73 연관규칙 마이닝 (Association Mining)
관광 스케쥴 데이터 분석 Shopping complex City center

74 연관규칙 마이닝 (Association Mining)
Basket (Transaction) data 측정치 (X -> Y) Support (지지도) : 전체 레코드에서 상품 X, Y에 대한 거래를 모두 포함하는 비율 => Supp(X, Y) Confidence (신뢰도) : 상품 X를 구매한 거래가 발생했을 경우 그 거래가 상품 Y를 포함하는 조건부 확률 => Conf (X->Y) = Supp(X,Y)/Supp(X) Lift (향상도) : 상품 X를 구매한 경우, 그 거래가 상품 Y를 포함하는 경우와 상품 Y 가 상품 X에 관계없이 구매된 경우의 비율 => Lift (X->Y)=Supp(X,Y)/(Supp(X)∙Supp(Y)) = Conf(X->Y)/Supp(Y) 측정치 예 {Milk, Diaper} => Beer : Supp=2/5, Conf=2/3, Lift=(2/3)/(3/5)=1.1167 Transaction ID Iterms 1 Chips, Milk 2 Chips, Diaper, Beer, Cornflakes 3 Milk, Diaper, Beer, Pepsi 4 Chips, Milk, Diaper, Beer 5 Chips, Milk, Diaper, pepsi Data Mining Lab., Univ. of Seoul, Copyright ® 2008

75 연관규칙 마이닝 (Association Mining)
일반 레코드 데이터 Data Mining Lab., Univ. of Seoul, Copyright ® 2008

76 Classification vs. Association
Classification rule training data의 설계시 class 속성이 결정됨 if-then 구조에서 then 부분에는 반드시 class 값이 들어감 Association rule이 보다 포괄적 Any column is possible ! Data Mining Lab., Univ. of Seoul, Copyright ® 2008

77 Clustering & Associations
Lotte World방문자 데이터 GyroDrop -> Atlantis 학생고객(나이: 12-18) cluster 소아동반고객 cluster Marry-go-Round -> Kids Bumpercar

78 Text Mining

79 Text Mining Data Mining Text Mining Text Mining의 기반 기술 구조적 데이터를 대상
Unstructured/Semi-structured text documents를 대상 Text Mining의 기반 기술 Machine learning Information retrieval Natural language processing Statistical learning

80 Data Mining Lab., Univ. of Seoul, Copyright ® 2008
Text Mining Data Mining과의 차이 Curse of Dimensionality Feature selection 기술이 중요 Zipf’s Law, document frequency, x2 Statistics, Mutual Information Natural language process 기술과 결합 linguistic, lexical, and semantical techniques Data Mining Lab., Univ. of Seoul, Copyright ® 2008

81 Text Mining Feature Selection Stopword 제거 Zipf’s Law
DF (document frequency)-based x2 Statistics-based Mutual Information Term Strength etc Data Mining Lab., Univ. of Seoul, Copyright ® 2013

82 Text Mining Feature Selection
Stopwords Data Mining Lab., Univ. of Seoul, Copyright ® 2013

83 Text Mining Feature Selection
Zipf’s Law Data Mining Lab., Univ. of Seoul, Copyright ® 2013

84 Text Mining Feature Selection
Ex) x2 statistics-based C /C t p r /t q s Data Mining Lab., Univ. of Seoul, Copyright ® 2013

85 Text Mining Application
Document Retrieval (Search) Document Recommendation Text Classification Text Clustering Text Summarization Text (information) Extraction Text Association Rule Mining Topic Detection

86 Data Mining Lab., Univ. of Seoul, Copyright ® 2008
Text Classification Web Page Indexing Web directory-based Search Engine에서 웹문서의 자동분류 Data Mining Lab., Univ. of Seoul, Copyright ® 2008

87 Text Clustering Document Clustering Word Clustering
Big text data에 대한 조망: document cluster에 대한 description model의 생성 Cluster 내 문서집합에서 주요 단어의 추출 distance function이 중요 Word Clustering 용도: thesaurus 구축, word sense disambiguation 등 2가지 방식 Corpus-based approach Taxonomy-based approach

88 Word Associations Example: Association Rules
w1 => w3 with 50% (2/4) support and 66% (2/3) confidence w3 => w1 with 50% (2/4) support and 100% (2/2) confidence

89 Text Classification 환자본인의 유전자를 이용, 배아를 만든 후 이를 이용해 실험실에서 건강한 세포를 배양시켜 환자에 다시 주입하는 이른바 치료복제법이 실험을 통해 입증되기는 이번이 세계최초라고 연구진은 주장했는데 이 방법은 주입된 세포에 대한 인체의 거부 반응이 없어 그동안 의학계의 관심을 끌어왔다 Extraction Feature 환자 본인 환자본인 유전자 이용 배아 이용 실험실 건강 세포 배양 환자 주입 치료복제법 실험 입증 이번 세계 최초 세계최초 연구진 주장 방법 주입 세포 인체 거부 반응 의학계 관심 fication Classi- 수의학  의학,생명공학,약학  치의학  생물,미생물  성  질병,증상,죽음  . . . Data Mining Lab., Univ. of Seoul, Copyright ® 2013

90 Text Clustering 검색결과에 대한 clustering
Data Mining Lab., Univ. of Seoul, Copyright ® 2013

91 Association Mining Data Mining Lab., Univ. of Seoul, Copyright ® 2013

92 Opinion Mining Sentiment Analysis (Opinion Mining)