데이터 마이닝

1. 데이터 마이닝의 연관규칙

 

① 데이터 마이닝 기술의 개요

∘데이터 마이닝(Date Mining) 기술 - 대용량 데이터로부터 패턴과 규칙 형태의 새로운 지식을 발견하는 작업 - 데이터 마이닝 결과가 실질적으로 유용하려면 대용량의 파일들이나 데이터베이스에 대하여 마이닝 과정이 수행되어야 하며, DBMS와의 통합이 필요함 - 데이터 마이닝은 인공지능, 통계학, 신경망, 유전자 알고리즘 등 다양한 분야에서 깊이 다루고 있음 ∘데이터 마이닝 분야의 장래 - Gartner Report 등에서 데이터 마이닝을 가까운 장래의 가장 유망한 기술 중 하나로 주목하고 있음 ∘지식 발견 과정으로서의 데이터 마이닝 - 데이터베이스 내에서 지식 발견은 데이터 마이닝 이상의 의미를 가짐 - 지식 발견의 6 단계 . 데이터 추출(data selection): 특정 항목 또는 항목들의 부류에 관한 데이터나 특정 지역 상점들에 관한 데이터가 선택될 수 있음 . 데이터 정제(data cleansing): 부적절한 우편번호의 정정, 잘못된 전화번호를 제거함 . 데이터 내용 강화(data enrichment): 다른 소스들로부터 필요 내용 추가, 예를 들면 고객정보에 나이, 수입, 신용등급 등의 데이터를 추가로 확보하여 더해줌 . 데이터 변환(data transformation) 또는 인코딩(encoding): 입력된 데이터를 정해진 형식으로 그룹화하여 데이터 양을 줄임. 예를 들면 수입을 범위별로 구분해 줌 . 데이터 마이닝(data mining): 규칙과 패턴을 발견함. . 보고서 작성(reporting) 단계: 리스트와 그래픽, 요약테이블, 시각화 등 다양한 형태 - 데이터 마이닝에서는 연관규칙, 연속패턴, 분류트리 등을 발견함 ∘마이닝과 지식 발견의 목표 - 데이터 마이닝의 목적은 예측, 식별, 분류, 최적화의 네가지로 분류됨 - 예측에서는 향후 발생할 사건을 예측함; 구매 고객 예측, 판매량 예측 등 - 식별에서는 사건(event) 및 활동(activity)의 존재를 식별하는데 이용되는 패턴을 발견함; 해커의 활동 패턴 발견, 유전자 패턴 식별 등 - 분류에서는 데이터를 클래스 혹은 카테고리로 분할함; 쇼핑몰에서 고객의 분류 - 최적화에서는 주어진 제약 조건 하에서 시간과 공간, 자금과 재료 등과 같은 제한된 자원을 최적으로 사용하여 이익을 최대화하는데 있음

② 데이터 마이닝에서 발견되는 지식의 형태

∎데이터 마이닝에서 발견되는 지식의 형태는 5 가지로 표현됨 ∘연관규칙(association rule) - 한 항목집합의 존재와 다른 항목 집합과의 연관관계를 나타냄 - 예 1) 여성 고객이 핸드백과 모자를 구매하면, 구두도 구매함 2) a와 b의 특징을 포함하고 있는 X-ray 이미지는 c의 특징을 가짐 ∘분류계층(classification hierarchies) - 기존의 이벤트나 트랜잭션의 존재로부터 클래스들의 계층 구조를 생성하는 것 - 예 1) 이전의 신용 거래 기록을 기반으로 고객 집단을 5개의 신용등급으로 분류하거나, 2) 상점의 위치에 대한 적합도를 1-10점으로 결정하는 모델을 개발하거나, 3) 투자신탁 예금을 성장과 수입, 그리고 안전성과 같은 특성 지수에 근거하여 분류함 ∘연속패턴(sequential pattern) - 일련의 액션 혹은 이벤트들을 탐색함 - 예) 만일 한 환자가 막힌 동맥을 교정하기 위하여 심장 수술을 받은 후 많은 수혈을 공급받았다면, 환자는 다음 18개월 동안 신장병으로부터 고통 받을 가능성이 있음 (연속패턴의 검출은 시간적인 측면에서 사건들 사이의 연관성을 검출하는 것과 동일함) ∘시계열패턴(patter within time series) - 시계열 상의 시점들 내에서 유사성을 검출함 - 증권 시장의 주가 데이터에 관하여 - 예 1) 전력회사 ABC와 보안회사 XYZ의 한 해 동안 주식 종가가 동일한 패턴 지님 2) 두 상품은 여름철에 동일한 판매 패턴을 가지나 겨울철에는 다른 판매 패턴을 지님 3) 태양 자기풍의 패턴은 지구 대기 조건들에 변화를 예측하는데 이용될 수 있음 ∘분류와 분할(categorization and segmentation) - 주어진 사건과 항목들의 집단을 유사한 요소들의 집합들로 분할함 - 예 1) 질병 처치의 전체 집합은 발생되는 부작용의 유사성을 기반으로 나눌 수 있음 2) 미국의 성인들은 가장 구매 가능성이 있는 집합에서 가장 가능성이 없는 집합까지 5 가지 카테고리로 분류될 수 있음 3) 웹 문서들에 대한 사용자의 접근 데이터로부터 문서에 대한 키워드를 기준으로 사용자들을 분류할 수 있음

③ 연관 규칙(1)

∎연관 규칙(association rule) ∘X⇒Y의 형태로 표현되며, X와 Y는 각각 X=x1,x2,…,xn와 Y=y1,y2,…,yn로 표현되는 항목 xi와 yi의 집합임 ∘이 연관규칙의 의미는 만일 한 고객이 X를 구매하면, Y를 구매할 가능성이 있음을 의미함 ∘지지도(support): 전체 트랜잭션 중에서 X∪Y 집합 내 항목들이 함께 나타나는 트랜잭션들의 비율 ∘신뢰도(confidence): X를 포함하는 트랜잭션 중에서 Y까지 포함하는 트랜잭션의 비율 [그림 1] 장바구니 모델의 트랜잭션 예 ∘연관규칙을 탐사하는 2가지 단계 - 최소 지지도 이상을 가지는 모든 항목 집합을 생성하며, 이러한 항목들의 집합을 빈발항목집합(large or frequently item set)이라고 하고, 빈발의 의미는 일정값 이상의 지지도를 가진다는 의미임 - 각 빈발항목집합에 대하여 최소 신뢰도를 가지는 모든 규칙을 다음과 같이 생성한다. - 빈발항목 X에 대하여 Y⊂X, Z=X-Y라고 하면, 만일 지지도(X)/지지도(Z) 값이 최소 신뢰도 보다 크면 규칙 Z=>Y (즉, X – Y => Z)는 적합한 규칙임 ∘항목의 개수가 많은 경우에 문제점 - 항목의 개수가 m 개이면 서로 다른 항목집합의 수는 2m 개이며, 따라서 계산 오버헤드가 심각해짐 (1천개 항목 => 21000 ) ∘연관 규칙의 발견에서 탐색공간을 줄이는데 유용한 특성 - 빈발항목의 부분집합도 빈발한 특성을 가짐. 즉, 빈발항목집합의 각 부분집합도 최소 필요한 지지도를 초과함 - 반대로 작은 항목집합(small item set)의 수퍼셋도 빈발하게 되지는 않음. 즉, 충분한 지지도를 갖고 있지 않다는 것을 의미함 - 이 특성을 이용하면, 일단 항목집합이 작다(즉, 빈발항목 집합이 아니다)라는 것을 알게 되면 그 항목집합에 하나 이상의 항목을 추가하여 얻은 항목집합도 작은 항목집합이 됨 ∘제안된 알고리즘 - Apriori 알고리즘, 샘플링 알고리즘, 빈발-패턴 트리 알고리즘, 분할 알고리즘 등이 제안되었으며, 대규모 항목집합에서 성능향상에 초점을 맞춤 ∘계층구조들 간의 연관규칙 - 응용 분야의 특성상 항목집합을 계층 형태로 구분하는 것이 자연스럽다면 계층 내의 연관 규칙과 함께 계층간에 존재하는 연관규칙을 발견하는 것이 특별한 의미를 가짐

④ 연관 규칙(2)

∘다차원 연관성: 이전에 언급한 연관규칙들은 단지 하나의 차원(속성)만을 포함하지만 실제로 두 개 이상의 차원에 대한 연관규칙도 중요한 의미를 가짐 - 예) 단일차원 연관규칙; 구입한 물건(우유)=>구입한 물건(주스) 2 차원 연관규칙; 시간(6:30…8:00)=>구입한 물건(우유) - 차원들은 범주(예: 구입한 물품)나 양적(예: 시간, 소득) 속성이 될 수 있음 - 양적 속성은 값들을 겹치지 않는 구간들로 파티션하고, 각 구간에 레이블을 주는 방식이 주로 사용됨 - 예) 저소득 (0<급여<29999), 중간소득(30000<=급여<74999), 고소득(급여>75000) ∘부정 연관성 - 두 항목 간에 연관이 없음을 나타내는 규칙 - 예) 포테이토칩을 사는 고객 중에서 60%는 병에 든 물을 사지 않음 (여기서 60%는 부정 연관규칙의 신뢰도를 가리킴) - 발견되는 부정 연관성의 규칙 중에는 유용하지 않은 것이 많을 수 있음 - 관심있는 부정 연관성을 발견하기 위해서는 도메인 지식을 이용하는 것이 중요함 ∘연관 규칙을 위한 부가적 고려사항들 - 대부분 상황에서 항목 집합들의 카디널리티는 매우 크며, 트랜잭션도 많다. 소매업과 통신회사들에서 운영하는 데이터베이스에는 하루에 수천만 개의 트랜잭션이 모아짐 - 트랜잭션들은 지리적 위치나 계절과 같은 요인에 민감할 수 있으며, 이것이 샘플링을 더욱 어렵게 만들게 됨 - 항목의 분류도 여러 차원에서 이루어질 수 있다. 그러므로 도메인 지식을 가지고 부정 규칙을 발견하는 것이 어려울 수 있음 - 데이터의 질(quality)도 변화한다. 따라서 여러 기업으로부터 입력되는 데이터의 중복 뿐 아니라, 데이터 결여와 데이터 오류 및 데이터 불일치 등과 관련된 중요한 문제가 발생할 수 있음

 

 

2. 데이터 마이닝의 분류, 군집화

 

① 분류(1)

∘ 분류의 정의 - 데이터를 서로 다른 부류 혹은 클래스 (미리 결정되어 있음)로 나누어주는 모델을 학습하는 과정 - 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)나 규칙들의 집합 형태로 표시됨 - 이미 분류되어 있는 훈련 데이터 집합을 사용하여 일단 모델이 구축하고, 그 모델을 이용하여 새로운 데이터를 분류함 ∘ 결정트리의 예 - 각 클래스에 대한 분류 규칙들을 트리 형태로 간단히 표현한 것 [그림 2] 신용카드 응용에 대한 결정 트리의 예

 

② 분류(2)

∘결정트리 - 모든 훈련 표본들은 트리의 루트로 초기화됨 - 표본들은 선택된 애트리뷰트를 기초로 하여 반복적으로 분할 됨 - 정보 획득치를 최대화하는 애트리뷰트가 노드 분할에 사용 됨 - 데이터를 분류하는데 필요한 정보를 최소화하고, 새로운 레코드를 분류하는데 필요한 조건 테스트를 최소화하기 위해 엔트로피 사용 ∘정보 획득치의 계산 - 정보 획득치(information gain measure): . 클래스를 분류할 때 결정 트리의 각 노드에 최적의 속성을 선택하는데 사용됨 . 이득(A) = 전체정보량 - 무질서도(A)를 의미함 - 기대 정보(expected information): . 어떤 속성을 선택함으로써 얻을 수 있는 기대 정보량 - 엔트로피(entropy): . 어떤 속성으로 분할된 데이터들의 무질서 정도 . 클래스 j에 속하는 Si의 샘플들의 수는 Sji로 나타낼 수 있음 . I(sj1,...,sjn)은 pji=sji/s로 계산된 pji에 의해 대체된 pi를 갖는 I(s1,...,sn)에 대한 식을 사용하여 정의될 수 있음 * Entropy에 대한 이해 - 우주의 Entropy는 증가하는 방향으로 진화함 - 담배연기가 입안에 있을 때는 질서가 있다 라고 하고 입에서 나와 공중에 흩어 질 때는 질서가 없다(entropy가 높다)라고 함

 

③ 군집화

∘군집화의 개요 - 훈련 샘플을 갖지 않는 데이터의 분할에 사용되는 자율적 학습 (unsupervised learning) 형태 - 유사한 레코드들은 같은 그룹에 배치하고 서로 다른 레코드들은 다른 그룹에 배치시킴; 그룹들 간에는 서로 겹치지 않음 - 수치데이터일 때, 거리에 바탕을 둔 유사성 함수를 사용해서 유사성을 측정 함 - K-평균 알고리즘(k-Means algorithm)이 주로 사용 됨 ∘K-평균 알고리즘 - Input: m개의 레코드 r1,...,rm으로 구성된 데이터베이스 D와 원하는 클러스터 개수 k - Output: 제곱 에러 기준을 최소화하는 k개 클러스터들의 집합 - Begin K개 클러스터를 위한 중간값(means)으로 임의의 k개 레코드들을 선택함 - repeat 각 레코드 ri에 대해, k개 클러스터 중에서 ri와 클러스터 중간 값 사이의 거리가 최소가 되도록 하나의 클러스터에 ri를 지정함 각 클러스터들에 지정된 레코드들에 근거하여 클러스터의 중간값이 재계산 됨 레코드들의 변동이 더 이상 이루어지지 않을 때까지 반복 수행 - End; [그림 3] 군집화 K-평균 알고리즘의 적용 예

④ 데이터 마이닝의 기타 문제

∘연속패턴 발견 - 항목집합들이 연속적으로 발생하는 경우 이로부터 빈번하게 발생하는 패턴을 발견함 예) 시장바구니 트랜잭션에서 {milk, bread, juice}, {bread, eggs}, {cookies, milk, coffee}는 한 고객이 상점을 3번 방문하여 구매한 항목집합들의 시퀀스(sequence) 임 - 여러 고객의 구매 시퀀스들에서 빈번하게 나타나는 부분 시퀀스들을 찾으면 이로부터 고객들의 구매 패턴을 예측할 수 있음 ∘시계열 패턴의 발견 - 주식의 폐장 가격은 주말마다 발생하는 사건이며, 일정기간 동안의 폐장 가격은 시계열을 형성함 - 시계열에 대하여 (부분) 시퀀스를 발견함으로써 주가에 대한 다양한 분석과 예측이 가능해짐 ∘회귀 - 회귀는 분류규칙의 특별한 응용으로 많은 연구 분야에서 데이터를 분석하기 위하여 널리 사용되는 일반적인 도구임 - 분류 규칙이 변수들에 대한 함수이고, 특히 그 변수들을 목표 클래스의 변수로 매핑한다면, 그 분류 규칙을 회귀규칙(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)라고 부름 ∘신경망 모델 - 샘플 집합으로부터 커버-핏팅 접근법(curve-fitting approach)을 이용하여 적절한 함수 (선형 및 비선형)를 추론하고, 이를 이용하여 데이터를 분류함 - 지도 신경망(supervised network)과 자율 신경망(unsupervised network)으로 분류할 수 있음 - 신경망 모형들은 특정의 문제에 관한 정보로부터 학습을 하는 자체적응적(self-adapt)임 - 다양한 문제에 적용할 수 있으며, 데이터의 잡음에 대하여 비교적 견고하고, 다양한 소프트웨어 패키지가 개발되어 있음 - 학습의 결과물의 양은 매우 방대하여 이해하기 쉽지 않음 ∘유전자 알고리즘(Genetic Algorithm) - 탐색 공간이 매우 큰 경우에 좋은 효과를 내는 임의 검색 기법(randomized search procedures)의 한 종류 - 인간의 유전 개념을 모방한 알고리즘으로 부모개체(문자열)로부터 절단과 병합의 교차연산(cross-over operation)을 수행하면서 새로운 개체(해)를 생성해 나가면서 원하는 정도의 해를 구함 - 최근에는 데이터 마이닝을 위한 강력한 툴로 활용되기도 함

⑤ 데이터 마이닝의 응용분야 및 기술 동향

∘데이터 마이닝의 응용 분야 - 마케팅; 고객의 구매패턴에 기반을 둔 고객 성향 분석, 광고와 점포의 위치 및 타겟 메일링 등을 포함하는 마케팅 전략의 수립, 고객과 상점 및 상품의 분류, 그리고 카탈로그와 상점 레이아웃 및 광고 캠페인 등의 디자인에 사용됨 - 금융; 고객의 신용가치 분석과, 계좌 분류, 주식이나 채권 및 투자 신탁과 같은 금융 투자 분석, 금융 옵션들의 평가, 사기 행위 적발 등에 사용됨 - 제조; 기계, 인력, 재료와 같은 자원들의 최적화, 제조과정의 최적 설계, 작업 현장 구조 개선, 제품 디자인 (예를 들어 고객의 요구사항을 반영한 자동차 설계) 등에 사용됨 - 의료; 치료에 대한 효과 분석, 병원 내에서 치료 과정의 최적화, 환자의 약의 부작용 분석, 유전자를 이용한 제약 개발과 질병치료 등에 이용됨 ∘상업적 데이터 마이닝 도구의 기술 수준 - 대부분의 마이닝 도구들은 연관규칙, 클러스터링 및 분류, 신경망 모형, 연속패턴, 통계적 분석의 기법 등을 지원함 - ODBC 표준 인터페이스를 이용하여 데이터베이스에 접근하므로 다양한 DBMS에 접근하여 원하는 데이터를 검색하거나 조작할 수 있게 함 - 사용자 인터페이스로는 대부분 정교한 시각화 기술을 가진 GUI가 사용됨 - 선택적으로 응용 프로그래밍 인터페이스를 제공함; 가장 일반적인 인터페이스는 C 라이브러리와 동적 링크 라이브러리(dynamic link libraries; DLLs)가 있음 ∘향후 기술동향 - 현재 데이터 마이닝에서 빠른 처리는 클라이언트-서버 아키텍처, 병렬 데이터베이스, 데이터 웨어하우징 등에서 분산 처리와 같은 최신 데이터베이스 기술을 이용하여 수행되고 있음 - 데이터 마이닝과 인터넷 기술의 밀접한 결합이 이루어질 것으로 보임 - 데이터 마이닝 도구에서 대규모 데이터 집합들을 다룰 수 있도록 해야 하며, ODBC 표준을 사용하여 다양한 데이터 소스로부터 자료를 수집하여 분석할 수 있어야 함 - 또한 데이터 마이닝을 위한 소스 데이터로서 이미지와 멀티미디어 데이터 등을 포함시키는 것도 중요한 과제이나 아직 멀티미디어 데이터를 대상으로 하는 데이터 마이닝 기술은 상용화될 만큼 성숙되지는 못한 상황임