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

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

강의 홈페이지 http://datamining.uos.ac.kr

본 강의의 키워드 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

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

Rstudio : R 통합개발환경

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

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

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

Hadoop Architecture

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

Hadoop: Word Count Example

HDFS (Hadoop Distributed File System)

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

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

MapReduce

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

빅데이터 처리관련 패키지 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를 지원하는 함수 제공 동국대학교 응용통계학과 서울시립대학교

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

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 서울시립대학교 동국대학교 응용통계학과

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 동국대학교 응용통계학과 서울시립대학교

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

RHadoop

RHadoop – word count

RHadoop – word count

RHadoop – word count

Rhadoop – word count

교재 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 최신 논문

Textbook 1: Data-Intensive Text Processing with MapReduce

Textbook 2: MapReduce Design Patterns

Textbook 2: MapReduce Design Patterns

Textbook 3: Big Data Analytics with R and Hadoop

Textbook 3: Big Data Analytics with R and Hadoop

Textbook 3: Big Data Analytics with R and Hadoop

Textbook 3: Big Data Analytics with R and Hadoop

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

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

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

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

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

자동분류 Classification

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

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

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

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

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

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

자동 분류 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)

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

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

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

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

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

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

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

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

군집분석 Clustering

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

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

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

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

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

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

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

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

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

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

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

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

연관분석 Association

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

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

연관규칙 마이닝 (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

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

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

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

Text Mining

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

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

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

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

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

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

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

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

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

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

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

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

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

Opinion Mining Sentiment Analysis (Opinion Mining)