데이터마이닝 2016.08 충북대학교조완섭
목차 데이터마이닝의개관 연관규칙 분류 군집화 데이터마이닝의다른문제들 데이터마이닝의응용들 데이터마이닝도구 2016-09-30 CBU / MIS 2
데이터마이닝 (DM) 개요 대용량데이터로부터패턴과규칙형태의새로운지식을발견하는작업 데이터마이닝결과가실질적으로유용하려면대용량의파일들이나데이터베이스에대하여마이닝과정이수행되어야하며, DBMS 와의통합이필요함 여기서는인공지능, 통계학, 신경망, 유전자알고리즘등다양한데이터마이닝분야를깊이다루는대신현재데이터마이닝분야의상황을간략히살펴봄 데이터마이닝분야의장래 Gartner Report 등에서데이터마이닝을가까운장래의가장유망한기술중하나로주목하고있음 2016-09-30 CBU / MIS 3
개요 Knowledge 데이터마이닝도구데이터마이닝알고리즘 ( 방법론 ) 기본적인자료검색 (SQL) 다차원자료분석 (OLAP ) 숨겨진지식발견 (data mining) 감추어진지식 ( 단서가있어야가능 ) 기존데이터작고, 정형화된, 느린데이터 2016-09-30 CBU / MIS 4
개요 데이터마이닝과관련학문 Visualization Statistics Data Mining Artificial Intelligence Databases 2016-09-30 CBU / MIS 5
데이터마이닝성공요인 개요 명확한비즈니스문제에대한인식과정의 문제이해 목적의명확한정의 충분한양질의데이터 DW + 그외필요한자료 Garbage in garbage out Good mining tools 숙련된마이너 원활한조직간협력과전사적지원 2016-09-30 CBU / MIS 6
OLAP 과 Data Mining 데이터마이닝과데이터웨어하우징 데이터마이닝은데이터웨어하우스내의가공된데이터나메타데이터혹은단순질의에의해발견할수없는의미있는새로운지식의발견을도와줌 데이터마이닝응용들은 DW 설계초기단계에서중요하게고려되어야하며, 데이터마이닝도구들도데이터웨어하우스와의연계사용을감안하여개발되는것이바람직 수십테라바이트의대용량데이터베이스에서데이터마이닝응용의성공적인수행여부는 DW의구축에크게의존 2016-09-30 CBU / MIS 7
OLAP & DM 의차이 OLAP 과 Data Mining OLAP 주어진자료를미리정해진다차원으로분석 / 요약 What?-why 에대한대답 정해진가설의확인 데이터에대한기본적인이해증진 데이터마이닝의효과극대화 Data Mining 예상치못한지식의발견 Why? 에대한대답 예측및룰의발견 의사결정의고급정보제공 OLAP의차원정보로 feedback Mailing 결과지역별 / 연령별응답율은? 기존고객은신상품중어느것을주로구매했나? 지난해수익성이높은고객 top 10은? 이탈한고객의지역별 / 분기별분포는? 재무상태가좋지않은고객은누구인가? Mailing을받고응답할것같은고객의프로파일은? 신상품을구매할것같은고객은? 어떤특징을지닌고객들이수익성이가장높은가? 이탈고객의특성은? 재무상태가좋지않은고객의특성은? 2016-09-30 CBU / MIS 8
11-01-2002 경영정보학과 9 상호보완적관계 OLAP 과 Data Mining OLAP 자료를다차원적으로이해 Data Mining 숨겨진지식의발견 DB or DW - DW 는 OLAP/DM 의기반제공 - OLAP 은 DM 에유용한정보제공 ( 단서 ) - 발견된지식은 DW & DB 에저장, 분석되어상호보완적운영 => 효과극대화
OLAP 과 Data Mining 비교 Top-Down Methodology Bottom-Up Methodology Surface Shallow Corporate Data Hidden DB & DW Analytical Tools Used SQL (Structured Query Language) for simple queries and reporting Statistical & OLAP for summaries, analysis, & forecasting Data Mining for classification, clustering and predictions 2016-09-30 CBU / MIS 10
Data Mining 프로세스 지식발견과정으로서의데이터마이닝 데이터베이스내에서단순검색과집계를넘어지식발견은중요한의미를가짐 => 인공지능 지식발견의단계 데이터추출 (data selection) 데이터정제 (data cleansing) 데이터내용강화 (data enrichment) 데이터변형 (data transformation) 또는인코딩 (encoding) 데이터검색, 집계, 다차원분석 데이터마이닝 (data mining) 보고서작성 (reporting) 단계 데이터마이닝에서는데이터로부터연관규칙, 연속패턴, 분류트리등을발견함 2016-09-30 CBU / MIS 11
Data Mining 프로세스 데이터마이닝절차 (Cycle) 문제 / 목적설정 필요한데이터확인 Business Domain Expert DBA Data Analyst 데이터준비 Model Building & Testing DW & DBs Data Mart 외부데이터 결과해석 / 평가 Java Developer Data Analyst 적합성 결과전달사용자환경구축실제업무와통합 End Users 2016-09-30 CBU / MIS 12
Data Mining 프로세스 Ad-hoc vs. Repeatable approaches Data mining tools: ad hoc data mining One or two (data analyst) users Extensive overhead of extracting and preparing data for each data mining exercise Data stays in the files or databases One-time results; not a repeatable process Data mining infrastructure: repeatable data mining Many users throughout the organization Data stays in the databases or DW s Automatically sift through data to find new business intelligence Enable applications with predictions and insights Data mining benefits for non-expert(s) 2016-09-30 CBU / MIS 13
마이닝과지식발견의목표 마이닝의목표와종류 데이터마이닝의목표는예측, 식별, 분류, 최적화의네가지로분류됨 예측에서는향후발생할사건을예측함 구매고객예측, 판매량예측등 식별에서는사건 (event) 및활동 (activity) 의존재를식별하는데이용되는패턴을발견함 해커의활동패턴발견, 유전자패턴식별등 분류에서는데이터를클래스혹은카테고리로분할함 쇼핑몰에서고객의분류 최적화에서는주어진제약조건하에서시간과공간, 자금과재료등과같은제한된자원을최적으로사용하여이익을최대화하는데있음 2016-09-30 CBU / MIS 14
마이닝의목표와종류 마이닝기법의종류와응용분야 기능기법적용분야 연관분석 association 분류 classification 군집분석 clustering 순차패턴 Seq. patterns 예측 forecasting Association rules generations 의사결정나무 사례기반추론 신경망 판별분석 / 로짓분석 신경망 K-means algorithm 의사결정나무 Sequential pattern analysis 시계열분석 회귀분석 사례기반추론 (case-based reasoning) 신경망등 장바구니분석타겟마케팅신용평가질병진단등시장세분화 Web 구조개선시간개념을이용한장바구니분석주가 / 환율예측수요예측재고및품질관리등 2016-09-30 CBU / MIS 15
연관분석 연관분석 (association analysis) 한데이터와다른데이터사이의관련성이있음을찾는규칙 연관규칙은 X Y 의형태로표현됨 구매부문에서 X Y 의의미는만일한고객이 X 를구매하면, Y 도함께구매할가능성이있음을의미함 지지도 (support) : 전체트랜잭션중에서 X Y 항목들이함께나타나는트랜잭션들의비율 신뢰도 (confidence) : X 를포함하는트랜잭션중에서 Y 까지포함하는트랜잭션의비율 Transaction-id Time Items-Brought 101 6:35 milk, bread, juice 792 7:38 milk, juice 1130 8:05 milk, eggs 1735 8:40 bread, cookies, coffee Milk Juice 는 50% 의지지도와 66.7% 의신뢰도를가짐 Bread Juice 는 25% 의지지도와 50% 의신뢰도를가짐 2016-09-30 CBU / MIS 16
연관분석 연관분석과정탐사하는 2 가지단계 최소지지도이상인항목집합 ( 빈발항목집합, frequently itemset) 을생성해나가는방식으로연관규칙을찾음 2016-09-30 CBU / MIS 17
항목의개수가많은경우에문제점 연관분석 항목의개수가 m 개이면서로다른항목집합의수는 2 m 개이며, 따라서계산오버헤드가심각해짐 (1 천개항목 => 2 1000 ) Apriori 알고리즘, 샘플링알고리즘, 빈발 - 패턴트리알고리즘, 분할알고리즘등이제안되었으며, 대규모항목집합에서성능향상에초점을맞춤 2016-09-30 CBU / MIS 18
계층구조들간의연관규칙 연관분석 응용분야의특성상항목집합을계층형태로구분하는것이자연스럽다면계층내의연관규칙과함께계층간에존재하는연관규칙을발견하는것이특별한의미를가짐 ( 다음 slide) 2016-09-30 CBU / MIS 19
BEVERGES CARBONATED NONCARBONATE COLAS CLEAR MIXED BOTTLED BOTTELD WINE DRINKS DRINKS JUICES WATER COOLERS beverages desserts 또는 desserts beverages 형태의연관규칙을생성하지는못할수도있으나 Healthy-bread frozen yougurt bottled water 또는 Richcream-brand ice cream wine cooler ORANGE APPLE OTHERS PLAIN CLEAR DESSERTS ICE_CREAMS BAKED FROZEN YOGHURT RICH CREAM REDUCE HEALTHY 그림. 슈퍼마켓에서항목들의계층구조 2016-09-30 CBU / MIS 20
연관분석 다차원연관성 지금까지소개한연관규칙은단지하나의차원 ( 속성 ) 만을포함하지만실제로두개이상의차원에대한연관규칙도중요함 예 단일차원연관규칙 : 구입한물건 ( 우유 )=> 구입한물건 ( 주스 ) 2차원연관규칙 : 시간 (6:30 8:00)=> 구입한물건 ( 우유 ) 차원들은범주 ( 예 : 구입한물품 ) 나양적 ( 예 : 시간, 소득 ) 속성이될수있음 양적속성은값들을겹치지않는구간들로파티션하고, 각구간에레이블을주는방식이주로사용됨 예 : 저소득 ( 급여 <1000만원 ), 중간소득 (1000만원 <= 급여 <5000만원 ), 고소득 (5000만원 <= 급여 ) 2016-09-30 CBU / MIS 21
연관분석 부정연관성 두항목간에연관이없음을나타내는규칙 예 : 포테이토칩을사는고객중에서 60% 는병에든물을사지않는다. ( 여기서 60% 는부정연관규칙의신뢰도를가리킨다.) 발견되는부정연관성의규칙중에는유용하지않은것이많을수있음 관심있는부정연관성을발견하기위해서는도메인지식을이용하는것이것이중요함 2016-09-30 CBU / MIS 22
연관분석 연관규칙을위한부가적고려사항들 대부분상황에서항목집합들의카디널리티는매우크며, 트랜잭션도많다. 소매업과통신회사들에서운영하는데이터베이스에는하루에수천만개의트랜잭션이모아진다. 트랜잭션들은지리적위치나계절과같은요인에민감할수있으며, 이것이샘플링을더욱어렵게만들게된다. 항목의분류도여러차원에서이루어질수있다. 그러므로도메인지식을가지고부정규칙을발견하는것이어려울수있다. 데이터의질 (quality) 도변화한다. 따라서여러기업으로부터입력되는데이터의중복뿐아니라, 데이터결여와데이터오류및데이터불일치등과관련된중요한문제가발생할수있다. 2016-09-30 CBU / MIS 23
분류의정의 분류 데이터를서로다른부류혹은클래스 ( 미리결정되어있음 ) 로나누는모델을학습하는과정 classifies data (constructs a model) based on the training set and the values (class labels) in a classifying attribute and uses it in classifying new data [Jiawei Han] 예를들어, 신용카드를신청한고객들을 poor risk, fair risk, good risk 로나누어주는모델의개발 모델은대개결정트리 (decision tree) 나규칙들의집합형태로표시됨 이미분류되어있는훈련데이터집합을사용하여일단모델이구축하고, 그모델을이용하여새로운데이터를분류함 2016-09-30 CBU / MIS 24
분류 결정트리 데이터에대한분류규칙들을트리형태로간단히표현한것 yes married no 사람에관한정보 salary acct balance <20k >=20k >=50k <5k >=5k <50k poor risk fair risk good risk poor risk age <25 >=25 그림. 신용카드응용에대한결정트리예 fair risk god risk 2016-09-30 CBU / MIS 25
분류 훈련단계 Classification : (1) model construction Cases Historic Data Attributes Name Income Age....... Jones 30,000 30 Smith 55,000 67 Lee 25,000 23 Rogers 50,000 44 Buy my Product? 1 =, 0 = 1 1 0 0 Functional Relationship: Model Y = F(X 1, X 2,, X m ) X 1 X 2... Xm Y Predictive Attributes Supplemental Attribute Target Attribute 2016-09-30 CBU / MIS 26
분류 실전단계 (2) Classification of new data Cases Attributes Name Income Age....... Jones 30,000 30 Smith 55,000 67 Lee 25,000 23 Rogers 50,000 44 Campos40,500 Hornick 37,000 Habers 57,200 Berger 95,600 Historic Data New Records 52 73 32 34 Buy my Product? 1 =, 0 =???? Predictions 1 1 0 0 1 0 0 1.85.74.93.65 Functional Relationship: Model Y = F(X 1, X 2,, X m ) Confidence 2016-09-30 CBU / MIS 27
분류 다른예제 (2) The weather data with ID code IDCode Outlook Temp Humidity Windy Play A Sunny Hot High F B Sunny Hot High T C Overcast Hot High F D Rainly Mild High F E Rainly Cool rmal F F Rainly Cool rmal T G Overcast Cool rmal T H Sunny Mild High F I Sunny Cool rmal F J Rainly Mild rmal F K Sunny Mild rmal T L Overcast Mild High T M Overcast Hot rmal F N Rainly Mild High T Input data - Outlook - Temp - Humidity - Windy Target Attribute - Play 2016-09-30 CBU / MIS 28
분류 다른예제 (2) Which attribute to select? Outlook Temp Humidity Windy sunny overcast rainly hot mild cool high rmal false true 0.48 0 0.48 G( 평균 )=0.32 0.5 0.44 0.38 G( 평균 )=0.44 0.49 0.24 G( 평균 )=0.37 Gf=0.38 Gt=0.5 G( 평균 )=0.44 2016-09-30 CBU / MIS 29
분류 다른예제 (2) Which attribute to select? sunny Outlook sunny Outlook sunny Outlook Temp Windy Humidity hot mild cool false true high rmal 2016-09-30 CBU / MIS 30
분류 다른예제 (2) Which attribute to select? sunny Humidity Outlook overcast rainy Windy high rmal false true 2016-09-30 CBU / MIS 31
분류 결정트리생성법 자식노드로분할할때각노드에포함된데이터의동질성이높게 ( 다양성이최소화되 도록 ) 하는것이바람직함 세가지방법이사용됨 피어슨카이제곱검정에대한 P 값 (Chi-square) 지니지수 (Gini Index) 엔트로피 (Entropy) 2016-09-30 CBU / MIS 32
분류 지니계수 : 데이터셋에서임의로두원소를복원추출할때서로다를확률 원소가동질할수록 0 에가깝고, 이질적일수록 1 에가까운값을갖는척도 Set1 Set2 A, B, C, A, C, C, A, D A, A, A, A, B, B, B, B 원소의개수 G(Set1) = 1 ( 전체원소갯수 ( ) ( 원소의개수전체원소갯수 ) 원소의개수원소의개수 ) ( 전체원소갯수전체원소갯수 ) = 1 ( ) ( ) ( ) ( ) = 0.69 원소의개수 G(Set2) = 1 ( 전체원소갯수 = 1 ( ) ( ) = 0.5 ) ( 원소의개수전체원소갯수 ) Set3 A, A, A, A, A, A, A, A 원소의개수 G(Set3) = 1 ( 전체원소갯수 ) = 1 ( ) = 0 Set4 A, B, C, D, E, F, G, H G(Set4) = 1 8 ( ) = 0.88 2016-09-30 CBU / MIS 33
분류,,,,,,,,,,,,, Outlook Humidity Which? G = 1 (9/14) (5/14) = 0.46 sunny overcast rainly high rmal G(sunny) = 1 (2/5) (3/5) = 0.48 G(overcast) = 1 (4/4) = 0 G(rainly) = 1 (3/5) (2/5) = 0.48 평균지니 = (0.48 + 0 + 0.48)/3 = 0.32 G(high) = 1 (3/7) (4/7) = 0.49 G(normal) = 1 (6/7) (1/7) = 0.24 평균지니 = (0.49 + 0.24)/2 = 0.37 지니감소량이더많은 ( 즉, 더동질하게분할하는 ) Outlook 를기준으로 split 2016-09-30 CBU / MIS 34
분류 또다른예제 Rid Married Salary Acct balance Age Loanworthy (class) 1 no >=50k <5k >=25 yes 2 yes >=50k >=5k >=25 yes 3 yes 20k 50k <5k <25 no 4 no <20k >=5k <25 no 5 no <20k <5k >=25 no 6 yes 20k 50k >=5k >=25 yes Salary <20k 20k 50k >=50k class= no {4,5 } age {1,2} class= yes < 25 >=25 class= no {3} {6} class= yes 2016-09-30 CBU / MIS 35
군집화 군집화 훈련샘플을갖지않는데이터의분할에사용되는자율적학습 (unsupervised learning) 형태 유사한레코드들은같은그룹에배치하고서로다른레코드들은다른그룹에배치시킴 ; 그룹들간에는서로겹치지않음 수치데이터일때, 거리에바탕을둔유사성함수를사용해서유사성을측정함 K-평균알고리즘 (k-means algorithm) 이주로사용됨 2016-09-30 CBU / MIS 36
군집화 K- 평균알고리즘 원하는클러스터개수 k를임의로선택 K개클러스터를위한중간값 (means) 으로임의의 k개레코드선택 모든레코드들을중간값과레코드의간격을기반으로주어진클러스터에배치 각클러스터의중간값이재계산됨 다시각레코드를조사하여중간값이가장가까운클러스터에레코드를배치 레코드들의변동이더이상이루어지지않을때까지반복수행 2016-09-30 CBU / MIS 37
군집화 : K- 평균알고리즘 10 10 1단계. 레코드를원하는클러스터개수 9 8 7 6 5 9 8 7 6 5 2단계. 현재분할된클러스터의 k=2 로분할 4 3 4 3 중간값을계산 2 2 1 1 0 0 1 2 3 4 5 6 7 8 9 10 0 0 1 2 3 4 5 6 7 8 9 10 10 10 4 단계. 9 8 9 8 3 단계. (2단계반복수행 ) 새롭게분할된클러스터의 7 6 5 4 3 7 6 5 4 3 각레코드를중간값이가장가까운 중간값을재계산 2 1 0 0 1 2 3 4 5 6 7 8 9 10 2 1 0 0 1 2 3 4 5 6 7 8 9 10 클러스터에재할당 2016-09-30 CBU / MIS 38
순차패턴 순차패턴의발견 항목집합들이연속적으로발생하는경우, 이들로부터빈번하게발생하는패턴을발견 예 : 시장바구니트랜잭션에서 {milk, bread, juice}, {bread, eggs}, {cookies, milk, coffee} 는한고객이상점을 3 번방문하여구매한항목집합들의시퀀스 (sequence) 임 여러고객의구매시퀀스들에서빈번하게나타나는부분시퀀스들을찾으면이로부터 고객들의구매패턴을예측할수있음 비디오점의대여기록 data 고객번호 구매기록 1 { 겨울연가 } => { 아폴로 13, 캐스트웨이 } 2 { 겨울연가 } => { 아폴로 13, 공동경비구역 } 3 { 러브레터 } => { 시월이야기, 동감 }{ 시월애 } 4 { 겨울연가 } => { 캐스트웨이 } ---------------------------------------------------------------------------------- 지지도 50% 이상의순차패턴은? { 겨울연가 } => { 아폴로 13} and { 겨울연가 } => { 캐스트웨이 } 2016-09-30 CBU / MIS 39
시계열분석 시계열분석의사례 주식의폐장가격은주말마다발생하는사건이며, 일정기간동안의폐장가격은시계열을형성함 시계열에대하여 ( 부분 ) 시퀀스를발견함으로써주가분석과예측가능 시애틀부동산데이터 2016-09-30 CBU / MIS 40
회귀분석 회귀 회귀는분류규칙의특별한응용으로많은연구분야에서데이터를분석하기위하여널리사용되는일반적인도구임 분류규칙이변수들에대한함수이고, 특히그변수들을목표클래스의변수로매핑한다면, 그분류규칙을회귀규칙 (regression rule) 이라고함 예 : 한환자에대하여 n번연속된테스트로부터얻어진결과값들을투플로저장한다고하자 : (patientid, test_1, test_2,,test_n) 환자의생존확률을 P라고하고, P=f(test_1, test_2,,test_n) 인함수 f를회귀함수하고부른다. 함수 f가도메인변수 test_i에대하여선형인경우에 f 를유도하는과정을선형회귀 (linear regression) 라고부른다. 2016-09-30 CBU / MIS 41
신경망모델 신경망모델 샘플집합으로부터커버-핏팅접근법 (curve-fitting approach) 을이용하여적절한함수 ( 선형및비선형 ) 를추론하고, 이를이용하여데이터를분류함 지도신경망 (supervised network) 과자율신경망 (unsupervised network) 으로분류할수있음 신경망모형들은특정의문제에관한정보로부터학습을하는자체적응적 (self-adapt) 임 다양한문제에적용할수있으며, 데이터의잡음에대하여비교적견고하고, 다양한소프트웨어패키지가개발되어있음 결과에대한설명이어려움 2016-09-30 CBU / MIS 42
유전자알고리즘 유전자알고리즘 (Genetic Algorithm) 탐색공간이매우큰경우에좋은효과를내는임의검색기법 (randomized search procedures) 의한종류 인간의유전개념을모방한알고리즘으로부모개체 ( 문자열 ) 로부터절단과병합의교차연산 (cross-over operation) 을수행하면서새로운개체 ( 해 ) 를생성해나가면서원하는정도의해를구함 최근에는데이터마이닝을위한강력한툴로활용되기도함 2016-09-30 CBU / MIS 43
데이터마이닝의응용분야 마이닝응용 마케팅 - 고객의구매패턴에기반을둔고객성향분석, 광고와점포의위치및타겟메일링등을포함하는마케팅전략의수립, 고객과상점및상품의분류, 그리고카탈로그와상점레이아웃및광고캠페인등의디자인에사용된다. 금융 - 고객의신용가치분석과, 계좌분류, 주식이나채권및투자신탁과같은금융투자분석, 금융옵션들의평가, 사기행위적발등에사용된다. 제조 - 기계, 인력, 재료와같은자원들의최적화, 제조과정의최적설계, 작업현장구조개선, 제품디자인 ( 예를들어고객의요구사항을반영한자동차설계 ) 등에사용된다. 의료 - 치료에대한효과분석, 병원내에서치료과정의최적화, 환자의약의부작용분석, 유전자를이용한제약개발과질병치료등에이용된다. 2016-09-30 CBU / MIS 44
마이닝응용 데이터마이닝의활용과정 (CRM 의예 ) 비즈니스환경분석 고객정보수집 DW 이용가능점수이탈가능점수교차판매가능점수평생가치점수 고객점수화 고객세분화 DM classification 고객반응분석 마케팅실행 마케팅전략수립 목표고객프로파일분석 2016-09-30 CBU / MIS 45
대부분의마이닝도구들은 마이닝응용 연관규칙, 클러스터링및분류, 신경망모형, 연속패턴, 통계적분석의기법등을지원함 ODBC 표준인터페이스를이용하여데이타베이스에접근하므로다양한 DBMS와연계되어사용가능함 사용자인터페이스로는대부분정교한시각화기술을가진 GUI가사용됨 선택적으로응용프로그래밍인터페이스를제공함 : C 라이브러리와동적링크라이브러리들 (dynamic link libraries; DLLs) 2016-09-30 CBU / MIS 46
마이닝응용 향후기술동향 현재데이타마이닝에서빠른처리는클라이언트-서버아키텍처, 병렬데이타베이스, 데이타웨어하우징등에서분산처리와같은최신데이타베이스기술을이용하여수행되고있음 데이타마이닝과인터넷기술의밀접한결합이이루어질것으로보임 마이닝도구에서대규모데이타집합들을다룰수있도록해야하며, ODBC 표준을사용하여다양한데이터소스로부터자료를수집하여분석할수있어야함 또한데이타마이닝을위한소스데이타로서이미지와멀티미디어데이타등을포함시키는것도중요한과제이나아직멀티미디어데이타를대상으로하는데이타마이닝기술은상용화될만큼성숙되지는못한상황임 최근들어빅데이터와마이닝의결합 => 딥러인, 알파고 2016-09-30 CBU / MIS 47
마이닝도구들 2016-09-30 CBU / MIS 48