데이터 마이닝의 기법

데이터 마이닝의 기법

   

데이터 마이닝 : 장남식.홍성완.장재호 지음, 대청미디어, 1999

   

1. 광의 대 협의의 분류 2. 의사결정나무(Decision Tree) (1) 장점 (2) 단점 3. 신경망(Neural Networks) (1) 장점 (2) 단점

4. 동시발생 매트릭스(Co-Occurrence Matrix) (1) 장점 (2) 단점 5. K-평균군집화(K-Means Clustering) (1) 장점 (2) 단점

   

data mining의 개요에서 우리는 지식발견(KDD)은 데이터로부터 유용한 정보를 발견하는 프로세스 전 과정이고, data mining은 지식발견 프로세스 중에서 데이터로부터 정보를 추출하기 위해 기법을 적용하는 특정단계라 정의했다. 특히 data mining 기법을 선정하여 데이터에 적용하는 과정은 지식발견 프로세스 중에서도 가장 흥미로운 단계임이 분명하다. 지금까지 알려진 data mining 기법들은 그 종류가 상당히 다양할 뿐 아니라 지금도 새로운 기법들이 대학과 연구소를 통해 계속 소개되고 잇다. 이 중에서도 이론적인 검증을 거쳐 상품적 가치를 인정받은 일부 기법들은 소프트적인 검증을 거쳐 상품적 가치를 인정받은 일부 기법들은 소프트웨어 공급업체들에 의해 상용화되어 시장에 등장하고 잇다. 그러나 data mining을 처음 접하는 초보자 뿐만 아니라 실제 사례에 적용해본 경험이 있는 사람들에게도 자신들의 상황에 적합한 data mining 기법을 선택하는 작업은 그리 쉽지 않다. 이것은 data mining 작업 유형에 관계없이 가장 탁월한 성능을 제공하는 특정기법이 존재하는 것도 아니고 유사 기법이라고 하더라도 분석 대상이 되는 데이터의 특성이나 도출하고자 하는 정보의 성격에 따라 상이한 결과를 낳을 수 있기 때문이다.
  이장에서는 data mining 기법들의 종류를 살펴보고 그 중에서 각 작업 유형별로 가장 많이 사용하는 기법들을 간단한 사례를 곁들여 소개하려고 한다. 그러나 회귀분석 (regression analysis)이나 판별분석 (discriminant analysis) 등과 같이 이미 널리 알려져 있는 전통적인 통계기법에 대한 소개는 제외시켰다. 이와 더불어 적절한 data mining 기법을 선정하기 위해서는 기법의 근간이 되는 이론이나 알고리즘을 확실히 이해하는 것이 바람직하나, 이들을 너무 강조하다 보면 자칫 초보자들의 data mining에 대한 흥미와 관심을 반감시킬 수 있으므로 data mining의 전반적인 개념과 사례를 소개한다.

   

1. 광의 대 협의의 분류

  일반적으로 데이터를 분석하는데 사용되는 기법들은 다음과 같다.

• 일반질의(Query)
• 시각화(Visualization)
• OLAP(On-Line Analytical Processing)
• 전통적 통계(Statistics) (예: 회귀분석, 판별분석)
• 의사결정나무(Decision Tree)
• 신경망(Neural Networks)
• 동시발생 매트릭스(Co-Occurrence Matrix)
• 발생 알고리즘(Genetic Algorithm)
• K-평균군집화(K-Means Clustering)

  data mining 기법이란 대량의 데이터로부터 새롭고 의미있는 정보를 추출하는 기술이다. 따라서 위에서 나열한 기법들은 공히 데이터로부터 정보를 뽑아내는 기능을 제공하기 때문에 넓은 의미에서 data mining 기법이라 해석할 수 있으며, 일부 data mining 관련 서적들도 이러한 해석에 따르고 있다. 그러나 일반질의 시각화, 그리고 OLAP 기법은 그 동안 알려지지 않은 새로운 정보를 사용자의 가이드 없이 찾을 수 있는가 하는 관점에서 볼 때, 단지 기존에 가지고 있던 정보(가설)를 확인하는 기능을 제공한다고 할 수 있기 때문에 통상적으로 data mining 기법에서 제외시키는 경향이 많다. 그러나 광의적인 해석의 배경에는 숨겨진 정보를 찾아냈다고 하더라도 검증을 위해 시각화 기법이나 OLAP도구를 사용해야 한다는 의견이 포함된다.
  협의적으로 해석하면 위의 세 가지 기법을 제외한 나머지 모두가 data mining 기법이다. 그러나 이 중에서도 의사결정나무와 신경망 기법 등과 같이 인공지능(artificial intelligence)에 기반을 둔 기법들이 대표적인 data mining 기법이라고 하는 의견과 이들 모두를 기존의 통계기법 범주에 포함시키는 의견이 학자들간에 분분하다. 실제로 의사결정나무나 신경망과 같이 기계학습(machine learning)에 근거한 기법들에 대한 활발한 연구가 시작된 원인중의 하나가 전통적인 통계기법을 통한 데이터 분석의 한계이다. 전통적인 통계기법들은 오랜 역사와 탄탄한 이론을 배경으로 한 검증된 기법으로 변수간의 상관관계를 발견하거나, 목표변수(부류)에 영향을 미치는 주요 속성들을 선별하고 이들의 영향력을 해석 가능한 수식으로 제공하는 능력을 지니고 있다. 특히 연속형 데이터 값을 갖는 각각의 속성이 목표변수에 미치는 영향에 대한 설명력은 타 기법들에 비해 월등하다. 반면 데이터 값들의 정규분표, 공분산(covariance) 등과 같이 여러 가지 통계학적 가정을 요구하는 경우가 많고, 데이터에 다수의 범주형(categorical) 변수가 포함되어 있을 때 이들을 가변수(dummy variable)로 변환시키는 과정에서 발생할 수 있는 치우침(bias) 등의 한계를 지니고 있다. 따라서 이러한 가정을 만족하지 않는 데이터를 분석하여 얻어지는 정보는 신뢰도가 낮고 data mining의 정의에서 요구하는 '의미있는' 정보가 될 수 없다. 그러나 통계는 데이터 분석 작업에 항상 기초가 되는 분야로서, 실제로 기계학습을 근간으로 하는 기법들의 이론적 근거가 되며 기법을 통해 도출되는 정보를 평가하고 해석하는데 있어서도 반드시 필요하다. 이러한 이유로 data mining 작업에 있어서 유능한 통계전문가의 존재유무는 작업 성패에 절대적인 영향을 미친다.

   

2. 의사결정나무(Decision Tree)

  의사결정나무는 data mining의 분류 작업에 주로 사용되는 기법으로, 과거에 수집된 데이트의 레코드들을 분석하여 이들 사이에 존재하는 패턴, 즉 부류별 특성을 속성의 조합으로 나타내는 분류모형을 나무의 형태로 만드는 것이다. 그리고 이렇게 만들어진 분류모형은 새로운 레코드를 분류하고 해당 부류의 값을 예측하는데 사용된다. 의사결정나무가 어떻게 새로운 레코드의 해당 부류값을 예측하는가는 어렸을 때 자주 하던 '스무고개' 놀이를 떠올려보면 이해하기 쉽다. 이 놀이에서는 한 사람이 특정한 사물이나 사건, 또는 인물이나 장소와 같은 개체 한 가지를 마음 속으로 생각한다. 그러면 나머지 사람들은 "그것이 사람입니까?"와 같은 질문을 반복하며 정답을 맞출 때까지 최고 20회의 질문 기회를 갖는다. 그러나 놀이에 능숙한 사람들은 20회의 질문 기회를 모두 사용하기 보다는 정답을 유도할 수 있는 예리한 질문을 몇 번 던지고는 정답을 맞추는 경우가 많다. 이 놀이와 마찬가지로 의사결정나무도 새로운 레코드의 부류값을 예측하기 위해 이미 만들어진 분류모형(의사결정나무)이 지시하는 바에 따라 레코드의 속성값을 질문하는 작업을 반복적으로 수행한다. 특히 결정적인 질문을 던지게 되면 다른 모든 속성의 값을 묻지 않고도 레코드의 부류값을 정확히 예측할 수 잇다. 따라서 레코드를 분류하고 예측할 수 있는 나무(모형)를 얼마나 잘 만드느냐가 의사결정나무 기법의 핵심이다.
  의사결정나무는 순환적 분할(recursive partitioning) 방식을 이용하여 나무를 구축하는 기법으로, 나무의 가장 상단에 위치하는 뿌리마디(root node), 속성의 분리기준을 포함하는 내부마디(internal nodes), 마디와 마디를 이어주는 가지(link), 그리고 최종 분류를 의미하는 잎(leaf)들로 구성된다. 그림 1은 data mining의 개요에서 작업유형 중 분류규칙에서 예시하였던 통신기기 판매업체의 고객반응 데이터를 이용하여 의사결정나무를 구축한 것인데, 긍정적('예')으로 응답한 고객들과 부정적('아니오')으로 응답한 고객들을 특성에 따라 분류하고, 향후 DM(Direct Mail) 발송시 긍정적인 반응을 보일 만한 고객들을 예측하는 것을 목적으로 한다. 데이터는 '직업', '성별', '거주지', '나이'라는 4가지의 속성과 부류에 해당하는 '응답'으로 구성되어 있고, 전체 레코드(고객)의 수는 14개이며, 이 중 5명의 고객이 '아니오', 9명이 '예'라고 응답했다. 의사결정나무 기법은 먼저 각 속성들이 고객들을 분류하는데 영향을 미치는 정도를 측정한 후, 그 중에서 가장 영향력이 있는 속성을 선정하여 나무의 뿌리마디에 지정한다. 위의 의사결정나무의 경우 '직업'이라는 속성이 나무의 뿌리 마디로 선정되었으며, 고객들은 해당 속성의 값에 따라 '고용', '자영', '무직'이라는 3개의 가지로 분리되었다.

그림 1 의사결정나무를 이용한 고객분류 모형

  여기에서 우리는 고객의 직업이 '자영'인 경우 '성별'과 '거주지', 그리고 '나이'에 관계없이 '예'라고 응답한다는 첫 번째 규칙을 발견할 수 있다. 반면에 전체 14명의 고객들 중에서 직업이 '고용'인 가지에 속한 고객의 수는 5명으로서 이 가운데 2명이 '아니오', 3명이 '예'라고 응답했다. 의사결정나무 기법은 이들 5명의 고객을 계속 분류하기 위해 나무를 확장시키는데, 가장 큰 영향력을 미치는 속성이 '나이'라는 것을 찾아내어 내부마디로 지정하였고 분리의 기준이 되는 값은 43세로 산정하였다. 특히 나이가 43세 이상인 2명 고객 모두는 '아니오'라고 응답했는데, 이를 근거로 직업이 '고용'이고 나이가 '43세' 이상인 고객은 '아니오'라고 응답한다는 두 번째 규칙이 도출된다. 이와 같은 방법으로 나무를 확장한 결과 총 5가지의 분류규칙이 만들어졌다. 이제 직장에 다니고, 거주지가 강남이며, 나이가 48세인 새로운 남성고객에게 DM을 발송하면 과연 어떻게 반응할 것인가를 판단해 보면, 위의 규칙에 따라 '아니오'라 응답하리라고 예측할 수 있다. 따라서 이러한 고객은 DM발송 대상자 명단에서 제외시키는 것이 비용과 노력 절감 차원에서 유리할 것이다.
  그림 1에서는 데이터상에 오류값이나 결손값(missing) 등이 존재하지 않았기 때문에 모든 레코드들을 완벽하게 분류할 때까지 나무를 확장시킨 후, 분류규칙을 도출하였다. 그러나 실제 업무 현장에서 데이터를 수집해보면 다소간의 차이는 있지만 대부분의 데이터가 오류값이나 결손값을 지니고 잇다. 이러한 경우 데이터에 포함된 모든 레코드들을 완벽하게 분류할 때까지 나무를 확장하여 분류모형을 만들게 되면, 불필요한 속성들이 나무의 마디에 포함되기 때문에 모형이 제공하는 규칙 자체가 엉뚱한 의미를 갖게 될 수 있으며, 이로 인해 새로운 레코드에 대한 예측력이 감소하는 결과를 초래한다. 이것을 소위 모형의 '과잉맞춤(overfitting)'이라 하며, 과잉맞춤으로 인해 불필요하게 복잡해진 나무의 의미없는 마디(속성)들을 제거하는 작업을 나무 '가지치기(pruning)'라 한다. 특히 가지치기 작업은 의사결정나무 모형을 구축할 때 거의 필수적으로 사용된다.

  (1) 장점

• 분류나 예측의 근거를 알려주기 때문에 이해하기가 쉽다.
• 데이터를 구성하는 속성의 수가 불필요하게 많을 경우에도 모형구축시 분류에 영향을 미치지 않는 속성들을 자동으로 제외시키기 때문에 데이터 선정이 용이하다.
• 연속형이나 명목형 데이터 값들을 기록된 그대로 처리할 수 있기 때문에 지식발견 프로세스 중 데이터의 변환단계에서 소요되는 기간과 노력을 단축시킨다.
• 어떠한 속성들이 각각의 부류값에 결정적인 영향을 주는가를 쉽게 파악할 수 있다.
• 모형구축에 소요되는 시간이 짧다.

  (2) 단점

• 나이나 소득 등과 같은 연속형 데이터를 처리하는 능력이 신경망이나 통계기법에 비해 떨어지며, 결과적으로 예측력도 감소한다. 따라서 데이터에 다수의 연속형 변수(속성)가 포함되어 있을 경우 값들을 그룹화하여 이산형(discrete)이나 범주형 값으로 변환시킬 필요가 있는데, 그룹화하는 과정에서 발생하는 치우침을 배제할 수 없다. 변환 과정에 대한 자세한 내용은 그림 3을 참고하기 바란다.
• 부류가 주가나 주택의 가격등과 같은 연속형 변수의 형태를 취하며, 이것을 예측하는 모형을 구축하는 것이 목적일 경우에는 적합하지 않다.
• 모형을 구축하는데 사용되는 표본의 크기에 지나치게 민감하다. 따라서 보다 정확한 모형을 만들기 위해서는 서로 상이한 값을 갖는 레코드들을 가능한 한 많이 포함하는 데이터가 필요하다.

3. 신경망(Neural Networks)

   신경망은 인간 두뇌의 신경세포를 모방한 개념으로 마디(node)와 고리(link)로 구성된 망구조를 모형화하고, 의사결정나무와 마찬가지로 과거에 수집된 데이터로부터 반복적인 학습과정을 거쳐 데이터에 내재되어 있는 패턴을 찾아내는 모델링 기법이다. 신경망은 분류, 군집, 연관규칙 발견과 같은 작업에 널리 사용되는 data mining 기법으로 신용평가, 카드 도용패턴 분석, 수요 및 판매 예측, 고객세분화(customer segmentation) 등 여러 가지 목적으로 다양한 산업분야에 폭 넓게 적용되고 있다.
  그러면 신경망 모형은 어떻게 구현되어 작동하는가? 이해를 돕기 위해 신경망 모형을 통해 주택이나 건물의 가격을 평가하는 사례를 살펴보기로 하자(자료원: Data Mining Techniques for Marketing, Sales, and Customer Support by M. Berry and G. Linoff, John Wiley & Sons, 1997).
  주택의 매매 중개나 감정을 위해서는 주택의 가치를 제대로 평가해야 한다. 특히 장기 대출을 통해 주택을 구입하는 방식이 관례화되어 있는 미국의 경우, 주택을 담보로 대출을 행하는 금융기관들에게는 정확히 가격을 평가하는 능력이 무엇보다도 중요하다. 실제로 주택 장기대출 업무를 주로 하며 전국적 체인을 보유한 미국의 후레디맥(Freddie Mac)사는 미국 전역에 흩어져 있는 주택들의 가격을 자동적으로 평가하는 '론 프로스펙터(Loan Prospector)'라는 시스템을 외주를 주어 개발하였는데, 이 시스템의 기반이 된 것이 바로 신경망 기법이다. 이 시스템을 개발하게 된 배경에는 주택 가격평가 전문가들이 경험한 자신들의 지식의 한계가 결정적인 원인이 되었다. 그들은 대도시에 위치한 주택의 가격이 도시 근교의 주택들에 비해 비싸다는 점, 그리고 방의 개수, 주차공간의 크기, 주택의 평수 등 다양한 요소들이 주택의 가격을 결정한다는 것을 알고 있었다. 그러나 이들을 조합해서 가격 예측 모형을 만드는데 많은 어려움을 겪었다. 물론 회귀분석과 같은 통계기법을 사용하여 모형을 만들어 보았으나, 예측의 정확도가 만족스럽지 못했다. 이러한 이유로 신경망 기법에 관심을 기울이게 된 것이다.
  이제 1,000건의 레코드로 구성된 가상 데이터를 이용하여 신경망 모형이 만들어지는 과정을 살펴보도록 하자. 표 1은 데이터를 구성하는 속성들의 이름과 내용, 그리고 값의 범위를 나타내고 있다. 물론 이들 속성 외에도 주변의 환경, 소속된 학군, 주택의 상태 등과 같이 주택의 가격을 결정하는데 영향을 줄 수 있는 속성들을 고려할 수 있으나 여기서는 사례를 간단히 하기 위해 제외 시키도록 한다.

표 1 주택가격예측 모형을 구축하는데 사용된 데이터

속성 명	내    용	값의 범위	역     할
방의 개수	방의 개수	1~6	입력변수
연도	주택이 건축된 연도	1945~1999
난방	난방의 형식	{A, B}
주차공간	최대 주차차량의 수	0~3
거실	거실의 크기 (평수)	5~50
층수	주택의 층수	1~3
크기	건평	10~1000
방향	거실의 정면이 향한 방향	{동, 서, 남, 북}
팔린 시기	이달을 기준으로 개월 수	0~23
가격	판매 가격(단위: 만원)	5,000~30,000	목표변수

   신경망 모형은 모든 입력변수와 목표변수가 0에서 1사이 범위의 값을 취할 때 최적의 성능을 제공한다. 따라서 변수의 성격에 상관없이 모든 변수의 값을 0과 1사이의 값으로 변환시키는 것이 바람직하다. 표 2는 1,000개의 레코드 중 첫 번째 레코드가 갖는 실제 값들을 속성별로 나열하고, 이들을 변환시킨 값을 나타낸다. 여기에서 방의 개수 '4'는 다음의 식을 통해 0에서 1사이의 값으로 변환되었다. (4-1)/(6-1)=0.6000. 난방과 같은 이진(binary) 변수의 경우에는 값 'A'를 '0'으로, 값 B를 '1'로 변환하였으며, 방향과 같이 4개의 값을 갖는 이산형 변수는 4개의 이진 변수를 만들어 각각 '0' 또는 '1'을 취하도록 하였다. 그러나 이와 같은 경우 이진 변수를 추가하는 대신, 첫 번째 값을 '0.00', 둘째 값을 '0.33', 셋째 값을 '0.67', 그리고 마지막 값을 '1.00'으로 변환하기도 한다.

표 2 속성의 실제 값과 변환된 값

속성 명	값의 범위	실제 값	변환된 값
방의 개수	1~6	4	0.6000
연도	1945~1995	1980	0.7000
난방	{A, B}	B	1.0000
주차공간	0~3	1	0.3333
거실	5~50	25	0.5555
층수	1~3	2	0.5000
크기	10~100	60	0.667
방향(동)	{예, 아니오}	0	0.0000
방향(서)	{예, 아니오}	0	0.0000
방향(남)	{예, 아니오}	1	1.0000
방향(북)	{예, 아니오}	0	0.0000
팔린 시기	0~23	8	0.3478
가격	5,000~30,000	10,000	0.2000

  그림 2는 자주 사용되는 신경망 구조들이다. (a)는 다수의 마디들을 포함한 입력층(input layer)과 하나의 출력마디로 구성된 가장 간단한 망구조로서, 통계의 로지스틱 회귀분석(logistic regression)과 동일한 모형을 제공한다. (b), (c), (d)의 구조는 입력층과 출력층(output layer) 사이에 은닉층(hidden layer)을 추가한 것으로 은닉층의 마디 수를 증가시키게 되면 분류능력이 향상되어 더 많은 패턴을 인식할 수 있지만 자칫 과잉맞춤의 결과를 초래하기 쉽다. 이것은 마치 의사결정나무 구축시 모든 레코드들을 완벽하게 분류할 때까지 나무를 확장하여, 새로운 레코드에 대한 예측력을 감소시키는 것과 유사하다. 따라서 의사결정나무에서는 적절한 수준에서 나무의 확장을 중단하는 것이 필요하듯이, 신경망에서는 적정한 은닉마디의 수를 결정하는 것이 필요하다. 신경망은 또한 (d)의 구조에서 보듯이 두 가지 이상의 값을 갖는 이산형 출력변수의 값을 예측할 수도 있다.

그림 2 다양한 신경망 구조

   신경망 기법 중에서 가장 널리 사용되는 후진전파(back propagation) 방식은 (b), (c), (d)의 경우와 같이 은닉층을 포함하는 구조이다. 이 방식은 마디와 마디들을 연결하는 고리들에 임의로 초기 강도(weight) 값을 지정하여 초기 모형을 설정한 후, 모형을 만들기 위해 준비한(모형 구축용이라 정의함) 데이터의 레코드를 하나씩 모형에 입력시켜 모형이 제시하는 부류의 값과 실제 부류의 값을 비교한다. 만약 이 둘의 값에 차이(오류)가 있으면 차이를 최소화하도록 강도의 값을 조정한다. 이와 같은 과정을 학습과정(learning process)이라 하는데, 학습과정은 강도 값의 변화가 미비해질 때까지 또는 미리 정해진 횟수만큼 모형 구축용 레코드들을 입력시킬 때까지 계속된다. 그림 3은 주택의 가격을 평가하는 모형을 후진전파 방식을 이용하여 구현하는 예이다.

그림 3 신경망을 이용한 주택가격 평가모형

  이렇게 만들어진 모형은 시험용 데이터를 이용하여 모형의 예측 정확도를 검증받은 후, 업무현장에 적용된다. 특히 모형은 0에서 1사이의 출력변수 값을 제시하기 때문에 이 값을 실제 값으로 재변환시키는 작업이 필요하다. 예를 들어, 이 모형을 이용하여 한 주택의 가격을 예측하기 위해 해당 속성의 값을 입력하니 모형이 제시하는 예측 값이 0.60이었다고 하자. 그러면 실제 예측 값은 가격의 범위 값 25,000에 0.6을 곱한 후, 최소 기준 값 5,000 가격을 더한 20,000이 된다.

  (1) 장점

• 입력과 출력 마디에 이산형, 연속형 변수를 모두 사용할 수 있다. 따라서 기법을 적용할 수 있는 문제의 영역이 의사결정나무나 통계기법들에 비해 넓다.
• 의사결정나무나 통계기법들과는 달리 결과를 입력변수(속성)들의 비선형조합(non-linear combination)을 통해 제공하기 때문에 예측력이 우수하다.
• 신경망 기법을 지원하는 상용화된 data mining 제품이 많으며, 보다 다양한 기능을 제공하면서도 사용이 간편한 제품들이 지속적으로 소개되고 있다. 따라서 제품 선택의 폭이 넓고 취득하기가 쉽다.

  (2) 단점

• 분류나 예측 결과만을 제공할 뿐 어떻게 그러한 결과가 나왔는가에 대한 이유를 설명하지 못한다. 따라서 대출심사의 기준이나 이탈고객의 특성 파악 등과 같이 결과의 근거가 요구되는 영역에는 적합하지 않다.
• 모든 입력변수와 출력변수의 값을 0에서 1사이의 값으로 변환해야 하기 때문에 추가적인 시간과 노력이 요구된다. 그러나 최근에 소개되고 있는 몇몇 제품들은 이 작업을 자동으로 실행시켜 준다.
• 복잡한 학습과정을 거치기 때문에 모형을 구축하는데 상당한 시간이 소요된다. 특히 입력변수의 수가 너무 많으면 망을 형성하는데 더욱 오랜 시간이 걸리며 예측력도 감소한다. 이 경우에는 통계나 의사결정나무를 이용해 변수를 선별한 후, 신경망을 구축하는 대안을 고려할 수도 있다.
• 망을 설계하는 작업과 다양한 매개변수(parameter) 값을 설정하는 작업이 전문성을 필요로 하기 때문에 비전문가들이 사용하기에 어려움이 따른다.

   

4. 동시발생 매트릭스(Co-Occurrence Matrix)

  동시발생 매트릭스는 거래(사건) 속에 포함된 품목(항목)간의 연관관계를 발견하고자 할 때 사용하는 data mining 기법이다. 분석의 대상이 되는 데이터는 두 개의 변수, 즉 거래와 품목으로 구성되며, 각각의 거래에 대해 한 개 이상의 품목들이 존재한다. 일반적으로 하나의 거래는 한 고객에 의한 구매를 의미하며, 품목은 그 구매를 통해 구입된 물건이다. 동시발생 매트릭스는 확률을 이용하여 연관규칙을 제공하는데 먼저 하나의 품목에 대해, 다음으로 두 품목간의 연관규칙을 생성하며 계속해서, 세 품목간, 네 품목간 등으로 이어진다. 연관규칙은 "(품목 A)⇒(품목 B)"의 형태로 표현되며, "품목 A를 포함한 거래는 품목 B도 포함한다."라 해석한다.
  그림 4는 동시발생 매트릭스가 제공하는 연관규칙의 예인데, 상위 5개는 두 개 품목간의, 나머지는 세 개 품목간의 연관규칙이다. 그러나 이러한 식으로 품목간의 연관관계를 도출할 경우 만약 한 상점에서 유통되는 품목의 수가 30가지라고만 하더라도 거래들에 의해 만들어지는 모든 가능한 연관규칙의 수는 (2³⁰-1), 즉 1,073,741,823개이며, 품목의 수가 늘어날수록 규칙의 수는 기하급수적으로 증가한다. 따라서 이들을 여과하여 의미있는 규칙들만을 뽑아내는 기준이 필요한데, 이것이 근거확률(support), 신뢰확률(confidence), 그리고 리프트(lift)이다.

그림 4 동시발생 매트릭스가 제공하는 연관규칙의 예

• 근거확률(Support)
  연관규칙 'A⇒B'의 근거확률은 두 품목이 함께 구매되는 확률 'Pr(A∩B)'이며, 다음과 같이 추정한다.
  (품목 A와 품목 B를 포함하는 거래의 수) / (전체 거래의 수)
   
  근거확률은 상호 대칭적으로 규칙 'A⇒B'의 근거확률은 규칙 'B⇒A'의 근거확률과 같다. 이것은 두 품목의 동시 구매가 얼마나 자주 발생하는가를 측정하는 것이지만, 보다 관심 있는 질문은 "품목 A를 구매하였을 경우 품목 B를 구매하는 가능성은 얼마인가?"이다.
   
• 신뢰확률(Confidence)
  연관규칙 'A⇒B'의 신뢰확률은 품목 A를 구매한 거래가 발생했을 때 그 거래가 품목 B를 포함하는 조건부 확률 'Pr(B/A)', 즉 'Pr(A∩B) / Pr(A)'로서, 다음과 같이 추정한다.
  (품목 A와 품목 B를 포함하는 거래의 수) / (품목 A를 포함하는 거래의 수)
  
  신뢰확률은 근거확률과는 달리 상호 대칭적이 아니며, 만약 품목 A와 품목 B의 구매가 상호 독립적일 경우에는 Pr(B/A)는 Pr(B)와 같게 된다. 그림 5는 연관규칙 'A⇒B'의 근거확률과 신뢰확률을 도식화해서 보여주고 있다.

그림 5 근거확률과 신뢰확률

• 리프트(Lift)
  연관규칙 'A⇒B'의 리프트는 신뢰확률을 기대 신뢰확률로 나눈 값 'Pr(B/A) / Pr(B)'로 정의한다. 따라서 Pr(B/A)의 값은 Pr(B)의 값보다 리프트 비율만큼 크다. 이것은 리프트의 값이 1에 가까우면 품목간에는 상관관계가 거의 없음을 뜻하며, 1보다 크면 클수록 품목간에 양의 상관관계가 많음을 의미한다. 표 3은 리프트 값이 갖는 의미와 예이다.

표 리프트의 의미 및 예

리프트	의미	예
1	품목 상호 독립적인 관계	과자와 후추
>1	품목 상호 양의 상관관계	식빵과 버터
<1	품목 상호 음의 상관관계	변비약과 지사제

   동시발생 매트릭스를 이용하여 연관규칙을 도출할 때는 근거확률, 신뢰확률, 그리고 리프트의 최소기준치(lower bound)를 미리 설정하고, 이 기준을 만족하는 규칙만을 생성하게 함으로써 규칙의 수를 제한할 수 있다. 아울러 근거확률, 신뢰확률, 그리고 리프트는 동시발생 매트릭스가 제시하는 규칙들을 평가하는데 상호보완적인 기능을 제공하는데 예를 들어, 어느 한 연관규칙의 신뢰확률이 크더라도 두 품목의 공통 구매율, 즉 근거확률이 어느 정도 수준이 되어야 의미가 있다. 또한 연관규칙 'A⇒B'의 신뢰확률이 높은 경우에도 품목 B가 구매되는 기본 확률이 커야 A를 고려해서 B를 생각하는 것이 의미가 있으므로 리프트 값이 1보다 커야 유용한 정보가 된다.
  그림 6은 개요에서 data mining 작업유형의 연관규칙에서 예시한 의류상점 판매 데이터로부터 두 품목간의 연관관계를 도출한 후, 근거확률, 신뢰확률, 그리고 리프트를 계산한 예이다. 여기에서 제시한 두 종류의 연관규칙은 상호대칭적인데 근거확률과 리프트는 변화가 없으나 신뢰확률은 바뀌었음을 알 수 있다.

그림 6 연관규칙의 근거확률, 신뢰확률, 리프트 산출 예

  (1) 장점

• 결과가 "If-then'의 형식으로 제공되기 때문에 이해하기 쉽다.
• 연관관계 모형을 구축하는데 특별한 전문지식이 필요없다.
  따라서 초보자도 손쉽게 사용할 수 있다.
• 근거확률(교집합), 신뢰확률(조건부확률) 등을 지원하기 때문에 도출된 규칙간의 상호 비교·평가가 쉽다.

  (2) 단점

• 연관규칙을 도출하는데 소요되는 시간은 데이터에 포함되어 있는 품목들의 수에 비례하여 기하급수적으로 늘어나기 때문에 품목의 수를 줄이는 작업이 필요하다. 그러나 이러한 작업은 쉽지 않을 뿐 아니라, 전혀 예상하지 못했던 품목들간의 연관관계를 찾아낸다는 data mining의 본래 목적에 위배된다.
• 분석하고자 하는 품목의 수에 비해 레코드(거래)의 수가 상대적으로 충분하지 못하면 신뢰확률이 낮은 엄청난 수의 연관규칙들이 발견되곤 한다. 이 경우 연관규칙들을 비교·평가하여 선별하기가 어렵다.

   

5. K-평균군집화(K-Means Clustering)

  K-평균군집화는 data mining의 군집화 작업에 주로 사용된다. 이 기법은 N개의 속성으로 구성되는 각각의 레코드를 벡터로 표시하여 N차원의 데이터 공간(space)에 나타낼 때, 유사한 특성을 갖는 레코드들은 서로 근접하여 위치한다는 가정에 근거하고 있다. 여기에서 영문자 'K'는 K개의 군집을 의미한다.
  다음의 사례는 K-평균군집화 기법을 2차원 공간에서 적용하는 예(자료원 : Data Mining Techniques for Marketing, Sales, and Customer Support by M. Berry and G. Linoff, John Wiley & Sons, 1997)로서, (월수입, 연령)으로 구성된 20개의 레코드들을 3종류(K=3)의 군집(부류)으로 분류하는 작업을 단계별로 설명하고자 한다.
  첫 단계는 그림 7과 같이 20개의 레코드들 중에서 3개의 레코드를 임의로 선택하여 각 군집의 중심값으로 지정한 후, 나머지 레코드들이 소속될 군집을 결정하고 군집간의 경계선을 긋는다.

그림 7 군집별 초기 중심값과 경계선

  단, 소속 군집의 결정 기준은 각 레코드와 3개 중심값과의 직선 거리 중에서 가장 짧은 중심값으로 한다. 예를 들어 첫 번째 군집의 중심값이 (80, 25), 두 번째 군집의 중심값이 (100, 40), 세 번째가 (125, 30)이고, 첫째 레코드의 값이 (90, 45)이라면 이 레코드와 첫 번째 군집의 중심값과의 직선거리는 다음과 같이 계산된다.

  마찬가지 방법으로 두 번째, 세 번째 군집의 중심값과의 직선거리를 계산하면 각각 11.2와 38.1이 된다. 따라서 첫째 레코드는 일단 두 번째 군집으로 분류된다. 또한 두 군집간의 경계선은 두 중심값과 같은 거리에 위치한 좌표들의 집합, 즉 직선이 된다. 그림에서는 첫 번째, 두 번째, 세 번째 군집에 속한 레코드들을 각각 삼각형, 원, 사각형으로 표시하고 있다.
  다음 단계로는 각 군집에 속한 레코드들의 중심값을 재측정한다. 즉 첫 번째 군집의 새로운 중심값은 군집에 속한 레코드들의 월수입 평균값과 연령 평균값이 된다. 중심값이 구해지면 첫 단계에서와 마찬가지로 각 레코드에 대해 군집의 중심값과 직선 거리를 측정하여 가장 근접한 군집에 포함시킨 후, 군집간의 경계선을 표시한다. 그림 8은 과거의 중심값들이 새로운 중심값(십자형으로 표시된 곳)으로 이동하는 모습과 군집별 경계선, 그리고 각 군집에 속하는 레코드들을 보여주고 있다. 특히 첫 번째 군집에 속한 레코드(삼각형으로 표시) 중 하나는 중심값이 이동함에 따라 새롭게 이 군집에 포함된 것을 알 수 있다. 새로운 군집이 형성되면 이전 단계의 과정을 중심값의 이동이 미비할 때까지, 즉 경계선의 변화가 거의 없을 때까지 반복적으로 실행한다.
  위의 사례에서 보듯이 K-평균군집화 기법은 이해하기가 쉽고, 연령이나 월수입 등과 같이 모든 속성이 크기를 가름할 수 있는 연속형 값을 취할 경우에 적용하기 쉽다. 그러나 데이터에 성별이나 학력 등과 같은 명목형 값들이 포함되어 있으면 레코드간의 직선거리를 측정하기 어렵다는 문제가 있다. 또한 거리 측정시 N차원 공간에서 모든 속성의 공헌도를 같다고 인정한다. 예를 들어 한 레코드의 (월수입, 연령)의 값이 (100, 30)이고 다른 레코드의 값이 (90, 40)이면, 이들 두 레코드와 군집의 중심값 (80, 20)과의 직선거리는 같기 때문에 동일한 군집에 속하게 된다. 그러나 실제로는 어느 한 속성의 중요도가 다른 속성보다 높은 경우가 많으며, 이러한 점을 반영하여 군집을 만들어야 의미가 있다. 이와 같은 문제점들을 감안하여 거리 계산에 있어 명목형 데이터의 값이 서로 다를 경우 0으로 간주한다든지, 속성별로 서로 다른 가중치를 부여하는 방식 등 새롭게 변형된 K-평균군집화 기법들이 등장하고 있다.

그림 8 군집별 중심값 및 경계선의 이동

  (1) 장점

• K-평균군집화 기법을 지원하는 상용화된 제품이 많으며, 사용 또한 쉽고 간편하다. 따라서 사용자가 자신이 원하는 사양을 갖춘 제품을 이용하여 손쉽게 문제의 영역에 적용할 수 있다.
• 군집분석 이외에도 분류·예측을 위한 선행작업, 특이 오류값이나 결손값 처리작업 등 다양한 분석에 사용할 수 있다.

  (2) 단점

• 속성들의 형태가 다르거나 같은 형태의 속성이라도 값의 범위가 다양할 경우 거리 측정기준을 설정하는데 어려움이 따른다.
• K-평균군집화 기법은 사용자가 지정한 K값에 따라 데이터를 K개의 군집으로 나눈다. 그러나 실제 데이터의 구조가 이 값보다 작거나 큰 수의 군집 특성을 갖고 있다면 좋은 결과를 기대하기 어렵다.
• 군집결과에 대한 해석이 용이하지 않다.