결정트리에 대한 소개 자료입니다. 아래의 도서에서 몇 단락을 발췌하였으니 참고바랍니다. 좀 더 자세한 학습을 원하는 경우는 아래의 도서를 준비하여 공부하시기 바랍니다.

[도서] CRM을 위한 데이터마이닝, 대청, 알렉스 버슨 외 지음 / 홍성완 외 옮김 / p.151-152

차세대 기법

이 장에서는 지난 20여년 간 학계나 연구소 등을 통해 개발되어 현재 널리 사용되고 있는 데이터마이닝 기법 중에서 정보기술 관련 서적이나 매체에서 자주 회자되는 대표적인 기법들 몇 가지를 소개하려고 한다. 이들 기법들은 주로 대용량의 데이터베이스로부터 과거에 인지하지 못했던 가치있는 정보를 추출하거나 새로운 자료/정보에 대한 예측 모델을 만드는데 사용되곤 한다. 또한 새로운 기법들을 지속적으로 개발하여 기존의 기법들을 대체하거나 보완하고 있는데, 예를 들어 의사결정나무 기법 중에서도 CHAID 와 같이 오래 전부터 사용되어 오던 기법보다는 CART 와 같은 새로운 기법을 선호하는 추세이다.

의사결정나무

의사결정나무란?

용어에서 의미하는 바와 같이 의사결정나무는 나무의 구조에 기반한 예측 모델로 나무의 가지는 데이터를 분류하기 위한 질문이며, 잎은 분류 결과에 따라 분리된 데이터 세트라고 할 수 있다. 그림 7-1은 한 이동통신 회사가 계약이 만료된 후 재계약을 하지 않은 고객(이탈고객)의 특성을 파악하기 위하여 만든 의사결정나무 모델의 일부인데, 여기에서 우리는 다음과 같은 특징을 발견할 수 있다.

  • 의사결정나무의 가지는 단 하나의 레코드도 빠짐없이 모두 분할한다. (부모마디에 속해 있는 레코드의 수는 두 개의 자식마디에 속한 레코드의 수의 합과 같다.)
  • 전체 이탈고객 및 잔류 고객의 수는 동일하며 나무의 상단 또는 하단으로 이동함에 따라 마디별 이탈고객및 잔류 고객의 수를 파악할 수 있다.
  • 신경망이나 전통적인 통계기법에 비해 모델의 구조를 이해하기 쉽다. 
     
  • 이탈 가능성이 높은 집단을 파악한 후, 그들을 상대로 마케팅 활동을 전개하는 것이 목적이라면 이 모델을 사용하는 것이 바람직하다.

  • 고객군별 특성(예, 수년간 우리의 고객이었으며 현재 최신형 단말기를 가지고 있으면 최우량 고객이다.)을 만들어 낼 수도 있다.  

 

 

 

by 에이아이 2009. 8. 12. 00:35
by 에이아이 2009. 8. 12. 00:25

참고주소: http://synap.tistory.com/entry/조건부-확률베이지안의-이해를-위한-예제-및-풀이

자료설명
:

위의 글(참고주소)에서는 조건부 확률에 의한 분류 알고리즘인 <나이브-베이지안> 분류 방법을 설명하고 있습니다. 예제를 통하여 자세하게 설명하여 나이브-베이지안 알고리즘의 동작 원리를 이해하는 데 도움이 되는 자료입니다.

내용일부


 예제1) 하얀별사탕, 분홍별사탕

건빵 2봉지를 샀다. 그래서 별사탕도 2봉지다. 첫번째 봉지에는 하얀별사탕이 10개, 분홍별사탕이 30개 들었고, 두번째 봉지에는 각각 20개씩 들었다. 두봉지의 별사탕을 하나의 접시에 담고, 눈을 감은채 별사탕하나를 집어들었다. 눈을 뜨고 집어든 별사탕을 지그시 살펴보니 분홍별사탕이다. 이 별사탕이 첫번째 봉지에서 나왔을 확률은?

별사탕이 40개씩 들었다는게 알려지면 엄청 잘팔리겠군.
음... 첫번째봉지에 분홍별사탕이 더 많이 있었으니,
아무리못해도 50%이상의 확률이 나와야 한다.

풀어보자. 일단 문제를 확률적으로 표현해보면 아래와 같다.
P(첫번째봉지|분홍별사탕) = P(분홍별사탕|첫번째봉지)P(첫번째봉지)/P(분홍별사탕)

P(분홍별사탕|첫번째봉지) = 30/40
P(첫번째봉지) = 40/80
P(분홍별사탕) = 50/80

각각의 확률을 적용하면,
P(첫번째봉지|분홍별사탕) = (30/40) * (40/80) / (50/80)
 = (30 * 40 * 80) / (40 * 80 * 50) = 30/50 = 60/100 = 60%

따라서, 답은 60%이다.

 

예제3) 99% 폐암진단시약

우리나라 충청,전북 등 자연적으로 우랴늄 함량이 높은 지역 일부에서 평생 1백명 가운데 1명이 폐암에 걸려 사망할 위험이 있는 등 라돈 농도가 위험수위인 것으로 밝혀졌다. 해당지역 주민한명이 폐암을 99% 진단하는 시약으로 진단한 결과 폐암 양성반응을 확인했을 경우, 이 주민이 실제로 폐암에 걸렸을 확률은?

가정이 많이 필요한 문제로군.
먼저, 흡연자 비흡연자 성별, 직업 등 다른 모든 조건은 별개로 하고
해당지역주민이 폐암에 걸릴 확률은 1%라고 하자.

(음... 폐암에 걸려 사망한 사람을 전체주민에서 빼게되면,
문제가 복잡해진다. 폐암에 걸려도 사망하지 않는다고 하고)
문제를 좀 더 간단히 해서 전체주민의 1%가 폐암환자라고 하자.

99% 진단이라는 건 무슨 뜻일까?
알려진 폐암환자 100명을 대상으로 했을 때 99명을 양성으로 판정하고,
알려진 정상인 100명을 대상으로 했을 때 1명을 양성으로 판정한다고 보면 되겠군.

풀어보자. 문제를 확률적으로 표현해보면 아래와 같다.

P(폐암|양성) = P(양성|폐암)P(폐암)/P(양성)

P(양성|폐암) = 99/100
P(폐암) = 1/100
P(양성) = ??? 여기서 한번 생각을 해야하는군...

모든 주민을 대상으로 진단했을 때 양성반응이 나올 확률은?
(주민은 99%의 정상인과 1%의 폐암환자로 구성됨을 기억하자)
P(양성) = P(양성|정상)P(정상) + P(양성|폐암)P(폐암)
= (1/100)*(99/100) + (99/100)*(1/100) = 198/10000
따라서 대략2%정도가 된다

여기서 잠깐! 베이스의 정리의 형태를 조금 수정해보자.
베이스의 정리에서 P(B) = P(B|A)P(A) + P(B|~A)P(~A) 로 쓸 수 있으므로

P(A|B) = P(B|A)P(A)/P(B)

 =           P(B|A)P(A)            
   P(B|A)P(A) + P(B|~A)P(~A)


공식의 새로운 형태는 P(B)의 계산을 아예 공식에 적용한 것이다.

이제, 각각의 확률을 적용하면,
P(폐암|양성) = (99/100) * (1/100) / (198/10000) = 1/2 = 50%

따라서, 답은 50%이다. 양성반응이 나와도 조금만 겁먹자.
확률은 반반이니까...

 

 

by 에이아이 2009. 8. 12. 00:03

2000년대 초반(2001년 5월) 데이터마이닝이 한창 이슈일 때 마이크로소프트 지에 실린 데이터마이닝 관련 소개 기사의 내용입니다. 참고하시기 바랍니다.

심규석 (KAIST 전산학과 교수)

마이크로소프트 2001년 5월호

원문보기 : http://maso.zdnet.co.kr/20010509/specplan/article.html?id=139

걷히는 안개를 바라보면서, 데이터마이닝

데이터 마이닝은 여러 가지로 정의할 수 있지만 쉽게 설명하면 많은 양의 데이터에 함축적으로 들어 있는 지식이나 패턴을 찾아내는 기술이다. 데이터 마이닝은 비교적 최근에 연구가 시작되고 관련 소프트웨어가 개발되고 있는 최첨단의 전산학 분야 중 하나다. 1983년에 IBM Almaden 연구소에서 Rakesh Agrawal 박사를 중심으로 Quest 데이터 마이닝 프로젝트가 시작된 이후로 선진국의 유수 연구소와 대학원을 중심으로 활발하게 연구가 되어왔다.

1994년 필자가 IBM Almaden 연구소에서 Rakesh Agrawal 박사의 지도 아래 데이터 마이닝 연구를 시작할 때만 하더라도 이 새로운 분야가 정말 성공할 수 있을지, 또 사람들을 위해 정말로 유용하게 쓰일 수 있는지 확실하지 않았다. 정말로 안개가 가득한 산속에서 어디로 가야할지 모르고 헤매는 듯한 기분으로 데이터 마이닝 연구를 시작했다. 하지만 그 뒤로 IBM Almaden 연구소와 벨 연구소에서 데이터 마이닝과 관련된 여러 가지 기술을 개발했고 논문을 썼으며 또 미국 특허들을 취득하거나 신청했다. 그러는 가운데 데이터 마이닝에 관한 필자의 안목도 조금씩 넓어졌다. 뿌연 안개 속에서 헤매는 것 같았던 처음에 비하면 이제는 필자에게는 그 안개가 하나씩 걷히는 것 같은 기분이다. 이제 데이터 마이닝에 관해 좀 더 확실하게 볼 수 있게 되었으므로 독자들에게 이에 대해 소개하고 이해를 돕고자 한다.

데이터 마이닝, 왜 알아야 하나

이제는 많은 회사들이 자신의 비즈니스에 관련된 여러 가지 데이터를 모아 데이터베이스 시스템에 넣어두고 있고 이 데이터의 양은 해다마 끊임없이 증가하고 있다. 또한 인터넷과 전자상거래가 급속하게 보급되면서 소비자와 구매에 관련된 많은 양의 데이터가 자동으로 컴퓨터에 모이게 됐다. 이로 인해 과거에는 가능하지 않았던 거대한 양의 데이터를 우리 주변에서 쉽게 찾아볼 수 있는 시대가 됐다. 하지만 이렇게 모아놓은 데이터로부터 아주 유용한 정보를 찾아내 마케팅이나 회사의 이익을 효율적으로 증대하기 위해 사용하는 데는 아직도 어려움이 많다. 그 이유 중 하나는 이 정보가 아주 많은 양의 데이터 안에 함축적으로 숨어 있어 사람의 눈으로 일일이 조사하는 것이 불가능하기 때문이다. 다행히도 데이터 마이닝 분야에서 개발된 기술을 통해 이러한 데이터로부터 유용하고 값진 정보를 효과적으로 찾아내 회사뿐만 아니라 개인의 일상생활도 편리하게 도와줄 수 있게 됐다.

가트너 그룹(Gartner Group)은 데이터 마이닝 기술을 이용한 타겟 마케팅(target marketing)이 아직까지 일반 회사에서 5%도 안되게 쓰이고 있지만 10년 내로 80% 이상 사용될 것이라 내다보고 있다. 현재 데이터 마이닝 시장의 크기도 10억 달러를 넘었다고 보고 있다. 그렇기 때문에 미국에서는 많은 상용 데이터 마이닝 소프트웨어를 개발해 팔고 있고, 여러 분야에서 효과적으로 이용되기 시작했다. 국내에도 이미 상륙해 국내 시장을 향해 힘차게 돌진하고 있다.

하지만 국내에서는 아직 데이터 마이닝에 대한 이해나 노력이 별로 이뤄지지 않고 있는 실정이다. 그래서 데이터 마이닝 기술이 어떤 유용한 일을 우리에게 해줄 수 있는지도 사람들이 잘 알지 못할 뿐더러 어떤 소프트웨어를 써야 할지 모르는 경우도 많다. 이런 시점에서 부족하나마 데이터 마이닝의 본고장에서 실제 소프트웨어를 개발했던 필자의 경험을 바탕으로 기본적인 개념과 응용 분야에 관해 간단하게 설명하고, 어떤 상용 소프트웨어가 있는지 중요한 판매사(vendor)와 실제 사용된 예를 소개하고 독자들에게 자신의 일터에서 어떻게 사용할 수 있는지에 대한 기본적인 아이디어를 제공하려고 한다. 데이터 마이닝 기술 자체가 너무나 방대해 모든 것을 나열하기에는 어려운 점이 많다. 또한 데이터 마이닝 기술을 자기 회사의 이익을 위해 아주 효과적으로 사용하고 있는 회사라 하더라도 경쟁사에 정보를 제공하지 않기 위해 사용 예와 얼마나 많은 효과를 얻고 있는지에 관해 제대로 발표하지 않는 경우가 많아 그 내용을 자세히 알아내기도 무척 힘들다. 그러므로 필자는 그 동안 경험한 것을 바탕으로 알고 있는 분야나 개발된 기술을 서술하려고 한다(혹시 부족한 점이 많이 있더라도 데이터 마이닝 기술을 알리고자 하는 필자의 열정을 봐서 많은 이해를 부탁한다).

데이터 마이닝이란

앞서 설명한 것처럼 데이터 마이닝은 많은 양의 데이터에 함축적으로 들어 있는 지식이나 패턴을 찾아내는 기술이라고 정의할 수 있다. 데이터 마이닝 기술은 백화점에서 물건을 진열할 때 고객의 움직임을 줄여주기 위해 활용할 수 있고, 고객의 구매 패턴을 보고 유용한 패턴을 찾아내 소비자가 살 물건을 미리 예측하고, 쿠폰을 발행해 관심을 유발함으로써 판매를 촉진할 수도 있다. 보험 회사에서는 고객이 다른 회사로 옮기는 것을 방지하거나 고객의 위험성에 따라 보험료를 차등화해 제공하는 데 사용할 수 있다. 또 신용카드 회사에서는 훔친 신용카드를 사용하는 경우를 발견해 더 이상의 불법 사용을 막거나 새로운 고객이 신용카드를 신청할 경우에 카드 발급 결정에 사용할 수도 있다.

전자상거래를 위한 웹 서버인 경우에는 소비자가 방문한 웹 페이지와 구매한 물건과 소비자의 특징을 보관하고 있기 때문에 이 데이터를 분석하면 각각의 사용자에 맞는 웹 페이지를 동적으로 그때 그때 생성해주거나, 웹 페이지의 캐싱(Caching), 프리페칭(Prefetching), 스와핑(Swapping)을 효율적으로 제공할 수 있어 성능을 높이고 수행속도를 빠르게 할 수 있다. 더욱이 웹 액세스의 다차원 웹 로그 분석을 이용한 트렌드 분석을 통해 웹에서 어떤 일이 일어나고 있는지에 대해서도 대략적인 정보를 제공해줄 수 있다. 또한 모든 소비자에게 동일한 웹 페이지를 제공하는 것이 아니라 소비자의 관심에 따라 다른 웹 페이지를 동적으로 만들어 제공하는 개인화(pesonalization) 서비스를 가능하게 할 수도 있다.

네트워크 분야에서는 네트워크에 이상이 생기기 전에 과거의 네트워크에 관련된 데이터를 이용해 앞으로 몇 시간 안에 네트워크에 생길지도 모르는 문제를 미리 예측해낼 수도 있다. 피자헛 가게를 새로운 장소에 개점할 경우에 과거의 다른 피자헛 가게가 세워진 곳에 관련된 정보로부터 새로 세우는 장소에서 성공할지를 예측하는 데도 사용할 수 있다.

교차 판매(cross-selling)나 상승 판매(up -selling) 등을 통해 회사의 판매 실적을 더 높일 수도 있다. 교차 판매란 서로 다른 부류에 속하는 상품이지만 서로 연관돼 고객들이 구매하는 경우를 찾아 연관된 상품을 고객에게 추천해 판매하는 것을 뜻한다. 예를 들어 장난감을 사는 고객이 생명보험에 들 가능성이 많다면 장난감을 사는 고객에게 생명보험에 관한 정보도 제공해 보험에 가입할 수 있도록 만드는 것을 말한다. 상승 판매란 1억원의 생명보험을 가입하려는 고객에 대한 정보를 분석해보고 만일 그 고객이 2억원짜리 보험에 가입할 가능성이 많은 고객이라면 2억원의 보험에 대해 같이 소개하고 추천해 더 비싼 보험을 들도록 유도하는 것을 말한다. 이 밖에도 여러 분야에서 데이터 마이닝 기술을 유용하게 사용할 수 있다.

대표적인 데이터 마이닝 기술

현재 상용 데이터 마이닝 소프트웨어에서 제공되는 주요한 알고리즘 중에서 필자가 생각하기에 최근에 개발된 중요한 기술을 소개하자면 연관 규칙, 순차 패턴, 분류, 군집화, 아웃라이어 판별 등이 있다. 이 중에서 데이터 마이닝 알고리즘의 대표적인 예가 될 수 있는 연관 규칙과 관련된 알고리즘부터 설명하고 나머지 다른 기술들에 관해 간략하게 소개하겠다.

연관 규칙(Association Rules)

데이터 마이닝을 소개할 때 대표적으로 언급되는 기술로 백화점이나 슈퍼마켓에서 한 번에 함께 산 물건들에 관한 연관 규칙을 찾아내는 기술이다. 실제 데이터를 이용해 발견됐던 아주 유명한 연관 규칙 중 하나는, 미국의 대형 편의점의 소비자 구매 데이터에 이 기술을 적용한 결과, 아기 일회용 기저귀를 사는 사람은 맥주도 같이 산다는 연관 규칙을 발견한 것이다. 이러한 패턴을 발견하고 소비자들에 관해 조사해 본 결과, 보통 아기 엄마가 남편에게 기저귀를 사오라고 하면 남편이 편의점에 들러 기저귀를 사면서 같이 맥주도 사간다는 것을 발견했다. 이러한 연관 규칙이 발견됐을 경우 맥주의 판매를 늘리기 위해 일부러 기저귀 값을 할인해 더 많은 맥주가 팔리도록 할 수 있다.

이 기술을 사용하기 위해 가장 보편적인 입력 데이터의 각각의 원소는 슈퍼마켓에서 한 번에 사는 장바구니에 들어있는 상품들이라 할 수 있다. 이 때 장바구니 하나에 들어가는 데이터의 집합을 한 트랜잭션(tran saction)이라 한다. <표 1>에 네 개의 트랜잭션으로 구성된 구매 데이터를 테이블로 나타냈다. 첫 번째 소비자는 라면, 오렌지 쥬스, 커피라는 세 가지 물건을 샀고, 두 번째 소비자는 라면과 소시지를 함께 구매했다. 연관 규칙 기술을 적용할 때 두 가지 설정값을 입력해야 하는데 이들은 지지도(sup port)와 신뢰도(confidence)라 불린다. 어떤 규칙의 지지도가 10%라면 그 의미는 전체 트랜잭션 중에서 그 규칙을 따르고 있는 트랜잭션이 10%를 차지한다는 것을 의미한다. 예를 들어 <표 1>의 경우, ‘ → ’라는 연관 규칙은 ‘라면을 산 사람은 커피도 같이 산다’는 의미인데, 네 가지 트랜잭션 중 1번과 3번 소비자가 구매한 물건들에 들어 있는 규칙이므로 지지도는 50%가 된다. 그리고 신뢰도는 규칙의 왼쪽에 있는 것을 산 사람들 중에서 오른쪽에 있는 물건들을 모두 산 사람들의 퍼센트를 말한다. 예를 들어 앞의 규칙에서 라면을 산 사람들은 세 사람인데 그 중에서 커피를 산 사람은 두 사람이므로 이 규칙의 신뢰도는 66.7%가 된다. 연관 규칙 알고리즘을 제공하는 소프트웨어를 쓸 경우에 최소 지지도와 최소 신뢰도를 데이터와 함께 설정하면 두 조건을 만족하는 모든 연관 규칙을 다 찾아낸다. 이 때 연관 규칙에는 왼쪽과 오른쪽 모두 여러 개의 상품이 올 수 있다. 예를 들면 ‘{라면, 오렌지 쥬스} → ’라는 연관 규칙도 가능한데, 이 연관 규칙은 ‘라면과 오렌지를 사는 사람은 커피도 산다’는 뜻이다.

앞에서 설명한 데이터는 불린 속성(boolean attribute)을 가진 데이터다. 다시 말하면 어떤 항목을 ‘구매했다’ 또는 ‘아니다’만을 나타낸다. 하지만 더 나아가 <표 2>와 같이 관계형 데이터베이스의 테이블과 같은 형식의 데이터를 이용해 연관 규칙을 찾을 수 있는데 이것을 정량적(Quantitative) 연관 규칙이라 한다. <표 2>의 데이터는 고객들에 대한 구매 정보가 아니라 각각 고객의 신상 명세에 관한 데이터로 숫자 속성(numericat tribute)과 범주 속성(categorical attribute)이 있다. 여기서 결혼 유무를 나타내는 열이 범주 속성에 해당한다. 앞의 데이터에서 찾을 수 있는 연관 규칙의 예를 들면 ‘[나이: 30...39]와 [결혼 유무 : Yes] → [자가용수 : 2]’인데 이 규칙은 지지도가 40%, 신뢰도가 100%다. 이 규칙은 ‘30대의 결혼한 사람들은 대부분 자가용을 두 대씩 갖고 있음’을 나타낸다. 앞에서 말한 구매 데이터 외에도 이와 같이 우리 주변에서 흔히 볼 수 있는 관계형 데이터에서도 연관 규칙을 찾는 기술이 이미 개발돼 있다. 그 외에 연관 규칙 알고리즘에 관한 자세한 내용은 관련 논문을 참조하기 바라며 이 글에서는 지면 관계상 생략하기로 한다.

연관 규칙을 사용할 수 있는 응용 분야로는 우선 백화점이나 잡화점에서 쿠폰이나 우편으로 상품 정보를 보낼 때 소비자가 산 물건들을 보고 구매할 가능성이 높은 항목들에 대해서만 상품 정보를 제공하는 것이 있다. 또 물건을 진열할 때 같이 구매할 가능성이 높은 항목들은 같이 배열해 소비자의 동선을 줄일 수 있다. 또한 웹 페이지를 디자인할 때 고객 부류에 따른 웹 페이지나 배너를 제공할 수 있다. 또한 의사가 환자에게 불필요한 검사나 치료를 해 의료 보험을 불법으로 과다하게 청구하는지 알아내는 데도 연관 규칙 기술을 사용할 수 있다.

순차 패턴(Sequential Patterns)

연관 규칙은 물건을 한 번에 살 때 같이 구매한 것들을 이용해 규칙을 찾는 것인 반면, 순차 패턴 발견은 순서대로 일어난 데이터를 분석해 빈도수가 높은 순차 패턴을 찾아내는 기술을 말한다. 예를 들어 비디오테이프 대여점에서 고객의 데이터를 분석해 ‘포리스트 검프’를 빌려본 고객은 나중에 아폴로 13이나 캐스트 어웨이를 함께 빌려 본다는 패턴을 발견했다고 가정하자. 이러한 패턴 정보를 편의상 ‘({포리스트 검프}) → ({아폴로 13, 캐스트 어웨이})’로 나타내보자. 이 순차 패턴 정보에 따라 다른 고객 역시 포리스트 검프를 빌려본 사람이고 나머지 두 영화를 아직 빌려 보지 않았다면 대여점을 방문했을 때 이 두 영화를 추천해 줄 수 있다. 순차 패턴의 또 다른 예를 살펴보자. 가전제품 회사에서 고객의 구매 패턴을 조사해본 결과 ‘(, ) → ()’라는 패턴을 발견했다고 가정하자. 이 패턴의 의미는 세탁기를 먼저 사고, 그 다음에 건조기를 산 사람들은 나중에 HDTV를 사는 경우가 많다는 것이다.

 <표 3>은 비디오 테이프 대여점의 고객 네 명의 대여 데이터다. 예를 들어, 3번 고객은 먼저 러브레터라는 영화를 대여한 후에 사월 이야기와 동감을 함께 대여했고, 그 다음에는 시월애라는 영화를 대여했다는 것을 의미한다. <표 3>에서 보면 ‘({포리스트 검프}) → ({캐스트 어웨이})’라는 패턴은 네 명 중에서 두 명이 갖고 있는 패턴이므로 지지도는 50%가 되고, 만일 최소 지지도를 50%라고 했다면 앞의 데이터에서 발견할 수 있는 순차 패턴은 ‘({포리스트 검프}) → ({캐스트 어웨이})’와 ‘({포리스트 검프}) → ({아폴로 13})’ 등이 있고 둘 다 지지도는 50%이다.

이 기술의 응용 사례를 살펴보자. 홈쇼핑 회사에서 소비자가 구매한 물건을 보고 다음에 살 것으로 예상되는 물건들의 쿠폰이나 카탈로그를 발송하는 데 사용할 수 있고, 학습지 회사에서는 국어 학습지를 구독하는 학생들이 그 다음에 어떤 다른 과목을 주로 더 구독하는지 알아내 판매를 촉진하는 데 사용할 수도 있다. 우편 주문이나 전자상거래 사이트에서 고객이 미래에 구매할 물건을 예측하는 데 사용할 수 있고 웹 페이지 방문자들의 액세스 로그를 분석해 웹 페이지를 고객에 따라 다른 구조를 갖게 하는 데 사용할 수도 있다. 또 병원에서 진료 받은 환자들의 진료 기록을 보고 과거의 어떤 증상이나 치료 과정(또는 결과)이 지금 현재 걸린 병을 유발하는 원인이었는지 찾아내는 데 이용할 수도 있다.

분류(Classification)

분류는 주어진 데이터와 각각의 데이터에 대한 클래스가 주어진 경우, 그것을 이용해 각각의 클래스를 갖는 데이터들은 어떤 특징이 있는지 분류 모델을 만들고, 새로운 데이터가 있을 때 그 데이터가 어느 클래스에 속하는지 예측하는 것을 뜻한다. 예를 들어 신용카드를 발행하는 은행의 고객 데이터에 고객의 나이, 연봉, 결혼 유무, 성별 등의 데이터와 신용 불량자인지 나타내는 클래스가 있다고 하자. 이러한 경우에 이 데이터를 결정 트리 알고리즘에 입력한다면, 신용 불량자는 나이가 23세 이하이고 연봉이 없는 사람들임을 발견한 규칙을 제공할 수 있다. 또한 미국에서는 어떤 동네든지 그 동네의 대형 슈퍼마켓에서 구매된 데이터를 사서 보면 그 동네의 아이와 젊은 여성, 노인의 비율을 대략적으로 알 수 있다고 한다. 이러한 데이터를 이용해 과거 다른 동네의 데이터와 비교해 성공했는지 실패했는지를 나타내는 클래스을 사용하면 새로운 동네에 새 슈퍼마켓을 만들려고 할 때 성공 가능성을 예측하는 데 사용할 수 있다. 또 새로운 의약품을 개발했을 때 여러 부류의 사람들, 즉 연령, 인종, 성별, 체중, 키 등이 서로 다른 사람들에게 임상 실험을 한 후, 그 약품이 효능이 좋았는지, 부작용이 있었는지를 나타내는 정보를 클래스로 만들어 입력한 후 각각의 클래스의 특징을 결정 트리 기법을 사용해 만들어 의사가 약을 처방할 때 주의 깊게 사용하도록 감독할 수 있다. 또 전자상거래 사이트에서 고객들의 구매 데이터를 보고 어떤 특징이 있는 고객이 비싼 수입 명품을 구매하는지 예측하는 데도 사용할 수 있다.

이러한 분류를 위해 개발된 알고리즘으로는 결정 트리 알고리즘, 베이지안 네트(Ba yesian Network), 신경망(Neural Net work) 등이 있다. 예를 들어 <표 4>와 같은 보험 회사 고객의 데이터가 있고 위험도가 클래스를 나타내는 열이라 한다면, 의사 결정 트리 알고리즘은 <그림 1>과 같은 의사 경정 트리를 만들어 준다. 이 트리를 루트 노드부터 살펴보면 나이가 30세 미만이면 위험도가 높고, 그 반대일 경우에는 소유하고 있는 자동차의 종류에 따라 사고를 낼 위험성이 달라짐을 나타낸다. 분류는 이처럼 각 부류에 속하는 데이터의 특징을 찾아 새로운 데이터의 클래스를 결과로 나타내어 주는 기술을 말한다.

군집화(Clustering)

군집화 기술은 전체 데이터의 분포 상태나 패턴 등을 찾아내는 데 유용하게 이용할 수 있다. 군집화란 주어진 n개의 점을 K개의 그룹으로 나누는 것을 말한다. 분류와 다른 점은 각 클래스에 해당되는 정보가 제공되지 않는다는 것이다. 연관 규칙에 관한 부분에서 언급한 예를 들어 설명하면 주어진 여러 고객의 구매 데이터를 바탕으로 그 구매 상품의 특징에 따라 고객을 여러 그룹으로 나누는 것이라 할 수 있다. 또 모든 고객의 신상 정보를 이용해 그 유사성에 따라 그룹을 나누는 데 사용할 수도 있다. 인터넷 검색엔진 회사에서는 웹 페이지의 내용에 따라 그룹을 만드는 ‘categorization’에 사용할 수 있다. 군집화에는 여러 가지 알고리즘이 개발됐는데 알고리즘에 따라 다른 군집화를 만들어 낸다. 그러므로 모든 알고리즘의 특성을 잘 알고 있어야 자기 응용 분야에 맞는 것을 잘 사용할 수 있다. 또한 숫자 형태의 데이터인가 범주 형태의 데이터인가에 따라 다른 형태의 알고리즘이 존재한다.

아웃라이어 판별 (Outlier discovery)

대부분의 데이터마이닝 기술은 데이터를 나타내는 패턴에 관심을 갖고 찾아내려 한다. 하지만 아웃라이어 판별 기법은 이와 반대로 대부분의 데이터와 다른 소수 또는 일부를 찾아내는 기술이다. 이 기술은 여러 유용한 곳에서 사용할 수 있다. 예를 들면 전화카드를 훔쳐서 사용할 경우 자신의 카드를 사용하는 대다수의 선의의 고객들과 당연히 사용 패턴이 다를 것이다. 또 훔친 신용카드를 쓰는 사람들의 사용 패턴은 자기 카드를 사용하는 고객과 다를 수밖에 없을 것이다. 또 회사나 백화점 같은 곳에서 일반 고객의 동선과 도둑의 동선은 다를 것이다. 또 시스템에 침입한 크래커들이 사용한 명령어(command)들은 정상적인 사용자들과 다를 것이다. 이러한 아웃라이어를 판별하는 데 여러 가지 기술이 이미 통계학 분야에서 사용됐는데, 여기서 사용되는 알고리즘들은 주로 데이터를 일정한 통계적 분포(statis tical distribution)로 가정해 모델을 설정하고 그 모델에 따라 아웃라이어를 판단하게 된다. 하지만 많은 경우에 사용자가 자신이 이용하려는 데이터의 분포를 알고 있지 않은 경우가 더 많다. 이를 위해 데이터베이스 분야에서 distance-based outlier discovery 알고리즘들이 개발돼 있다. 자세한 내용은 참고 자료를 보기 바란다.

데이터 마이닝 기술을 사용할 때 유의할 점

데이터 마이닝 기술을 성공적으로 사용하기 위해 유의해야 할 사항은 다음과 같다. 우선 값비싼 소프트웨어보다는 작업을 수행할 팀이 더욱 중요하다는 점이다. 비즈니스, 재무, 통계학, 인공지능, 데이터베이스 등에 관해 모두 잘 알고 있어야 할 뿐 아니라 각각의 데이터 마이닝 도구에서 사용된 가정이나 장단점 같은 것을 잘 알고 사용해야 한다. 그렇지 않으면 데이터 마이닝 도구에서 만들어낸 결과에 대해 잘못된 결론을 만들 수도 있기 때문이다. 또 사용할 데이터를 잘 이해하고 있어야 한다. 예를 들어 데이터에 빠져 있는 정보가 어떤 것인지 아는 것도 중요하고 외부로부터 얻을 수 있는 데이터들도 함께 사용해 분석하면 더욱 가치 있는 정보를 추출할 수 있다. 그리고 최근에 개발되어 많이 사용하지 않은 기술보다는 이미 사람들이 많이 사용하고 있고 그 성질이나 장단점이 잘 알려진 데이터 마이닝 알고리즘을 사용하는 것이 더 바람직하다. 잘 모르는 알고리즘을 사용하면 얻어진 결과에 대해 제대로 이해하거나 평가하기가 힘들기 때문이다.

데이터 마이닝에 관한 잘못된 인식들

데이터 마이닝에 관해 흔히 잘못 이해하고 있는 것이 몇 가지 있다. 보통 사람들은 데이터 마이닝은 데이터 웨어하우스를 구축해야만 가능하다고 생각한다. 하지만 데이터 마이닝은 디스크 파일로 된 데이터일지라도 가능하다. 대부분의 상용 소프트웨어는 텍스트 파일 형태의 데이터라 할지라도 입력해 사용할 수 있게 되어 있다. 또 어떤 사람들은 데이터 마이닝을 인공지능이나 통계학으로 단순하게 생각하는 경우가 있다. 하지만 데이터 마이닝에 두 분야의 지식이 도움이 되긴 하지만 인공지능이나 통계학이라고 간단하게 단정지어 말할 수 없다는 점을 강조하고 싶다(물론 데이터 마이닝에 통계학 지식이 전혀 필요 없는 것은 아니다). 데이터 마이닝 기술은 무조건 도움이 되기 때문에 아무데나 사용하라고 하는 사람들이 있지만 이것도 잘못된 생각이다. 기술을 잘 이해하지 못하면서 무조건 함부로 뛰어들 경우 실패할 확률도 높아지기 때문이다. 하지만 그렇다고 데이터 마이닝 기술이 성공적으로 사용될 수 없다고 함부로 단정짓는 것도 역시 잘못된 생각이다.

데이터 마이닝, 어디로 향하고 있는가

지금까지 짧은 역사이지만 많은 유용한 데이터 마이닝 기술과 소프트웨어가 개발됐다. 하지만 이 기술들이 우리 일상생활을 정말로 얼마나 편리하게 도와줄 수 있을지는 아직 두고 봐야 할 단계에 있다. 따라서 우리 모두가 자신의 분야에서 데이터 마이닝 기술을 효과적으로 적용하기 위해 노력할 필요가 있다.

한편 인터넷과 웹의 발전은 여러 가지 웹 마이닝 문제를 우리에게 새롭게 제시하고 있다. 인터넷의 많은 웹 사이트에서는 고객들이 스스로 자신의 ID를 등록하고 자신에 관한 신상명세서를 스스로 입력한다. 그리고 여러 가지 사용 기록이 자신도 모르는 사이에 자동으로 컴퓨터에 저장된다. 이러한 많은 양의 데이터는 과거에 감히 상상할 수 없었던 것이다. 웹의 데이터는 비정형 구조(semistructured)이기 때문에 이를 이용해 유용한 정보를 추출하기가 훨씬 더 어렵다. 또한 하이퍼링크(hyper-link)를 통해 여기저기에 흩어져 있는 방대한 데이터를 잘 이용해 유용한 정보를 뽑아낼 수 있도록 하는 것도 아주 중요하다. 웹에는 너무나 많은 데이터가 있지만 또 한 편으로는 쓸모없는 데이터도 많아 원하는 정보를 찾으려고 할 때 어려움이 있다. 웹에 적용할 수 있는 웹 마이닝 기술의 개발이 현재로는 시급하면서도 앞으로 가장 매력적인 데이터 마이닝의 한 분야가 될 것이다.

 <박스1>

데이터 마이닝의 대부, Rakesh Agrawal 박사

1983년도에 University of Wisconsin at Madison에서 박사학위를 받고 벨연구소에서 1983년부터 1989년까지 Ode라는 객체지향형 데이터베이스에 관해 연구했다. 그 후 IBM Almaden 연구소에서 일했고 1993년도부터 Quest 데이터 마이닝 프로젝트를 시작하고 주도했다. 그는 데이터 마이닝이라는 분야가 개척되고 자리잡는 데 크게 기여한 인물이다. 그가 개발한 데이터 마이닝 기술로는 OLAP, 연관규칙, 순차 패턴, 분류, 군집화, 유사시 계열 시퀸스(Similar Time Sequences), 텍스트 마이닝, 데이터베이스 마이닝 통합(Database-Mining Integration) 등이 있고, IBM Intelli gent Miner라는 데이터 마이닝 소프트웨어의 개발에 주도적인 역할을 하기도 했다. 그는 데이터 마이닝 분야에서 학문적인 것 뿐만 아니라 상용 소프트웨어의 개발에 기여한 공로를 인정받아 2000년도에는 ACM SIGKDD Innovation Award를 수상했다(http://www.almaden.ibm.com/cs/people/ragrawal/bio.html 참조).

<박스2>

연관 규칙 알고리즘

연관 규칙을 찾아주는 알고리즘 중에서 가장 먼저 개발됐고, 또 가장 많이 쓰이는 알고리즘은 Apriori 알고리즘이다. 이 알고리즘은 두 가지 단계로 구성된다. 우선 첫 번째 단계에서는 최소 지지도 설정값에 따라 빈도수가 높은 항목의 집합들을 찾아내고 그 다음 단계에서는 이들 집합들로부터 신뢰도 설정값을 만족하는 연관 규칙을 모두 뽑아낸다. Apriori 알고리즘에서 사용하는 중요한 법칙은 빈도수가 높은 항목의 집합의 모든 부분 집합도 다 빈도수가 높다는 사실이다. 예를 들어 데이터에 {라면, 커피, 설탕}이 최소 지지도에 의해 빈도수가 높다면 당연히 {라면, 커피}만을 봐도 빈도수가 높고, {커피, 설탕}을 봐도 빈도수가 높다. 다시 말해 어떤 집합이 주어졌을 때 새로운 항목을 더해주면 지지도는 절대로 전보다 증가할 수 없다.

주어진 n개의 항목이 있을 때 이 항목을 이용해 만들 수 있는 모든 항목 집합은 2n개가 있다. 예를 들어 {a, b, c}의 모든 부분 집합은 {}, , , , {a, b}, {a, c}, {b, c}, {a, b, c}가 있다. 그렇기 때문에 주어진 2n개의 항목에 대해 모든 부분 집합을 만든 후에, 각각에 대해 데이터를 보고 지지도 계산을 위해 카운트하려고 하면 이 부분집합의 개수가 너무 많아 모두 메인 메모리에 넣고 카운트할 수 없게 된다. 이해를 돕기 위해 설명하면, 만일 1000개의 물건을 판매하는 잡화점에서 그 물건들을 함께 살 수 있는 모든 경우를 다 따지면 21000이 되고 이것은 너무나 큰 숫자다. 그래서 간단하게 만드는 초보적인 알고리즘은 이 기술을 실제 생활에 사용할 수 없게 만든다.

하지만 앞에서 말한 법칙을 사용하면 그것을 가능하게 만들어 준다. Apriori 알고리즘은 우선 사이즈 한 개의 빈도수가 높은 항목들을 먼저 구하고, 그 다음에 이것들을 이용해 사이즈가 두 개인 빈도수가 높은 항목들의 집합을 구하는 방식으로 한 사이즈씩 차례로 수행한다. 그렇기 때문에 데이터에 있는 사이즈가 가장 큰 빈도 높은 항목 집합의 크기가 k라면 대략적으로 데이터를 k번 스캔하게 된다(여기서 집합의 사이즈란 그 집합에 들어있는 원소 개수를 말한다). 사이즈가 k인 빈도 높은 항목들을 지금 막 구한 단계라고 하자. 이 때 이들을 이용해 사이즈가 k+1인 후보 항목들의 집합들을 먼저 구한다. 예를 들면 {라면, 커피}와 {라면, 설탕}이 사이즈가 2인 빈도 높은 항목들 집합에 들어 있다면 이것으로부터 {라면, 커피, 설탕}이라는 사이즈가 3인 후보 항목들의 집합이 만들어진다. 이 때 이 집합의 원소로 구성된 사이즈가 2인 모든 부분집합이 사이즈 2인 빈도 높은 항목 집합들에 다 들어있는지 체크하고 만일 하나라도 없다면 후보에서 탈락시킨다. 이런 식으로 후보들을 만든 후에는 실제 데이터를 스캔해 후보들을 카운트하고 그런 후에 지지도를 만족하는 것들만 뽑아내 사이즈가 3인 후보 항목 집합을 만들어 낸다. 그 다음에는 다시 이들을 이용해 사이즈가 4인 후보들을 만들어 내고 더 이상 후보 집합을 만들지 못할 때까지 같은 과정을 반복한다.

<리스트>에서 Apriori 알고리즘의 첫 번째 단계를 의사 코드(pseudo code)로 나타냈다. <리스트>에서 Fk는 원소의 수가 k인 빈도 높은 항목 집합들을 다 모아 놓은 것을 뜻하고 Ck는 원소의 수가 k인 후보 항목 집합들을 다 모아 놓은 것이다.

<그림>은 <리스트>의 알고리즘이 어떻게 수행되는지 나타낸 것이다. 여기서는 편의상 구매 데이터 항목을 숫자로 표시했다. 그리고 최소 지지도는 75%라고 가정했다. 우선 모든 항목들에 대해 D를 스캔하면서 지지도를 계산하고 그 중에서 75%의 최소 지지도를 만족하는 항목들을 뽑아낸다. 이들은 <그림>에서 F1로 나타냈고 , , 등이 있다. 그러면 F1을 이용해 다음 크기의 후보 항목들 집합 C2를 만든다. , , 로부터 만들어질 수 있는 모든 항목의 집합이 C2에 나타나 있다. 그러면 다시 D를 스캔해 이 후보항목 집합들의 지지도를 계산하고 최소 지지도를 만족하는 {2, 5}만 F2로 남게 된다. 이 때 F2에 하나의 원소만 있으므로 더 이상 그 다음 크기의 후보 항목 집합을 만들 수 없고 이 알고리즘은 여기서 멈추게 된다.

앞에서처럼 첫 번째 단계에서 얻어진 빈도 높은 모든 항목 집합으로부터 두 번째 단계에서 모든 연관 규칙을 뽑아낼 수 있다. 예를 들어 {라면, 커피, 설탕}이라는 항목 집합이 빈도수가 높다고 판명됐다면, 이것으로부터 {라면, 커피} → , {라면, 설탕} → , {커피, 설탕} → 등과 같은 연관 규칙이 만들어지고 이것들에 대해 신뢰도를 계산한 후 최소 신뢰도를 만족하는 것만 남긴다.

<박스3>

군집화 알고리즘

군집화 알고리즘은 크게 파티션 알고리즘(partitional algorithm)과 계층 알고리즘(hierarchical algorithm)으로 나눌 수 있다. 전자에 해당되는 알고리즘은 K개의 모든 가능한 파티션을 모두 열거해 보고 군집화가 얼마나 잘 됐는지 나타내는 척도를 나타내는 함수 값이 가장 좋은 것으로 그룹들을 정한다. 이 때 대표적으로 많이 사용하는 척도 중의 하나는 square-error criterion인데 다음과 같은 식으로 나타낼 수 있다. 이 때 Ci는 각각의 그룹을 말하며, p는 각 그룹에 속한 각각의 데이터이고 mi는 각 그룹의 점들의 평균에 해당한다. 또 ∥∥는 벡터의 크기를 말한다.

숫자 속성(numeric attribute) 데이터를 군집화하는 데 쓰이는 가장 오래되고 잘 알려진 파티션 알고리즘 중에 K-평균(K-means) 군집화 알고리즘이라는 것이 있다. 이 알고리즘을 사용하려면 몇 개의 그룹으로 나누기 원하는지 K를 입력해야 한다. 그러면 알고리즘은 일단 K개의 평균점을 지정하고, 모든 데이터를 하나씩 보면서 가장 가까운 평균점에 해당되는 그룹에 할당한다. 그 후에, 다시 평균점들을 조금씩 바꾸어 나가면서 데이터를 가까운 그룹에 재할당하는 과정을 군집 상태를 나타내는 척도 함수가 더 이상 변하지 않을 때까지 반복한다. 더 이상 변하지 않게 되면 그 상태의 그룹들을 군집화의 결과로 정한다.

계층 알고리즘에는 top-down과 bottom-up 알고리즘이 있다. 그 중에서 다음과 같은 bottom-up 알고리즘을 agglomerative hierarchical clustering 알고리즘이라 한다. 이 알고리즘에서는 우선 모든 n개의 데이터가 n개의 서로 다른 그룹이라 가정한 후에 그룹간의 유사성(similarity)을 보고 가장 유사한 두 개의 그룹을 합병(merge)해 그룹 수를 줄여가는 과정을 전제 그룹 수가 K개가 될 때까지 반복함으로써 K개의 그룹을 찾아낸다. 예를 들어 <그림>은 1차원 데이터를 이용해 군집화하는 과정을 나타낸다.

유사성을 나타내는 함수는 두 점간의 Euclidean 거리를 쓰기로 한다고 가정하자. <그림>을 보면 데이터 4번과 5번이 가장 거리가 가깝기 때문에 먼저 합친다. 이 합쳐진 그룹을 4’라 하자. 그 다음에는 2번과 3번 데이터가 가장 가깝기 때문에 합쳐서 2’라 부르도록 하자. 그러면 그룹은 세 개로 줄어들었다. 다시 두 개의 그룹을 합하려 할 때는 그룹 2’와 4’가 가장 가까우므로 합쳐서 한 개의 그룹으로 만든다. 이런 방식으로 남아있는 그룹의 개수가 K일 때까지 반복한다. 이 알고리즘의 장점 중 하나는 군집화를 마칠 때까지의 과정이 트리 구조를 가지고 있어 drill down하거나 drill up하면서 어느 단계에서 군집화를 멈추는 것이 가장 잘 된 군집화인지를 사용자가 모두 확인해 보고 가장 좋다고 생각되는 것을 선택할 수 있다는 것이다. 예를 들어 만일 세 가지 그룹으로 <그림>의 데이터를 나누고자 한다면 맨 왼쪽 점은 한 개의 그룹으로 혼자 남고 나머지 점들은 그 다음 왼쪽부터 둘씩 그룹을 지어주면 된다.

일반적으로 다차원 데이터를 군집화하기 위해 유사성을 계산할 때 여러 가지 함수를 쓸 수 있다. Euclidean 거리, Manhattan 거리 등 여러 가지가 있는데 그 중에 어떤 것을 사용해 군집화를 하느냐에 따라 다른 특성을 갖는 군집화가 이뤄진다. 자세한 내용은 참고 자료를 보기 바란다.

이러한 두 종류의 군집화 알고리즘은 컴퓨터 이론 분야에서 이미 잘 알려진 알고리즘인데, 수행 속도를 이론적으로 표현할 때 입력 데이터의 수를 n이라 하면 적어도 n2에 비례한다고 나타낼 수 있다. 하지만 n2에 비례할 경우에는 모든 데이터를 메인 메모리에 넣고 알고리즘을 수행해야만 실제 쓸 수 있게 된다. 다시 말해 데이터가 메인 메모리에 다 들어가지 못하면 수행 시간이 너무 길어 사용할 수 없다. 이러한 문제점을 극복하기 위해 BIRCH라는 알고리즘이 개발됐다. 데이터가 너무 많아 메인 메모리에 다 넣을 수 없을 경우 우선 데이터를 메인 메모리에 들어갈 수 있는 만큼 요약된 대표들을 뽑아내는 초기 군집화(pre-clustering)를 먼저 행한 후 그 요약된 데이터만 갖고 기존 K-평균 군집화 알고리즘이나 그 밖의 다른 메인 메모리용 알고리즘을 수행한다. 실제 데이터로 군집화를 수행하는 것이 아니라 전체 데이터의 분포 상태를 나타내는 요약된 정보를 가지고 군집화를 행한다. 따라서 이 과정이 다 끝난 후에는 원래 데이터에서 하나씩 보면서 이미 형성된 군집들의 특성을 보고 가장 가까운 그룹으로 배정한다.

지금까지는 주로 숫자 속성을 가진 데이터의 군집화 알고리즘을 설명했는데 백화점 고객의 구매 데이터와 같은 범주 속성(categorical attribute) 데이터에 대한 군집화 알고리즘도 여러 가지가 개발됐다. 자세한 내용은 참고 자료를 찾아보기 바란다. 대표적인 범주 속성을 위한 알고리즘으로는 ROCK 알고리즘 등이 있다.


<박스4>

데이터 마이닝에 관한 최신 정보는 이 곳에서

데이터 마이닝 분야와 관련된 최근 기술 동향을 알고 싶다면 우선 ACM SIGKDD(Special Interest Group on Knowledge Discovery in Data and Data Mining)라는 단체에 관심을 갖기 바란다. ACM은 전산학 분야에서 가장 권위 있는 단체의 하나로 각기 다른 소분야마다 그룹이 나누어져 있고, 국제 학술회의를 열거나 뉴스레터를 제공한다. ACM SIGKDD의 홈페이지 주소는 http://www.acm.org/sigkdd/이고, 매년 2회 발행되는 뉴스 레터 SIGKDD Explorations의 홈페이지 주소는 http://www.acm.org/sigkdd/explorations/이다. 이 곳에 가면 필자가 객원 편집자(Guest Editor)로 참여했던 최근호뿐만 아니라 과월호도 온라인으로 모두 읽어볼 수 있다. 또한 ‘Data Mining and Knowledge Discovery’라는 국제 저널도 최근에 만들어져 새로운 기술이 소개되고 있다. 그 외에도 ACM SIGMOD, VLDB, ICDE와 같은 국제 학술회의에도 데이터 마이닝에 관련된 기술이 소개되고 있고, ACM TODS, IEEE TKDE, Information Systems 등과 같은 국제 학술지에도 데이터 마이닝 관련 기술이 소개되고 있다.

<박스5>

주요 데이터 마이닝 솔루션과 공급 업체

IBM 인텔리전트 마이너(Intelligent Miner)

◆주요 기술 : 연관 규칙 의사 결정 트리, 신경망 회로, 군집화, 순차 패턴, 유사시 계열 시퀸스, 텍스트 마이닝

오라클 다윈(Darwin)

◆주요 기술 : 연관 규칙 의사 결정 트리, 신경망 회로, regression, 군집화, Bayesian learning, self-organizing maps, memory-based reasoning

 

SAS 엔터프라이즈 마이너(Enterprise Miner)

◆주요 기술 : 연관 규칙 의사 결정 트리, 신경망 회로, regression

◆장점: SAS와 뛰어난 통합 기능

◆다양한 샘플링 도구 제공: 랜덤 샘플링, stratified 샘플링, n-th observation 샘플링, first-n sampling and cluster sampling

 

SGI MineSet

◆주요 기술 : 연관 규칙 의사 결정 트리, regression, 군집화, simple Bayes, decision table, boosting, automatic feature selection, cross-validation

◆특징: SAS 파일 import/export 유틸리티 제공, 뛰어난 visualizer를 제공

 

SPSS 클레멘타인(Clementine)

◆주요 기술 : 연관 규칙 의사 결정 트리, 신경망 회로, regression, 군집화
 

 

 

by 에이아이 2009. 8. 11. 23:48

<출처 : SERI 마케팅전략실 정.태.수. 연구원>

 

http://www.seri.org/kz/kzKsosv.html?ucgb=KZKSOS&no=23021&cateno=8 

 

여러분은 혹시 맥주와 기저귀의 상관 관계에 대해서 아십니까? 예전에 월마트에서는 고객의 장바구니에 들어있는 물건들을 분석한 결과 '기저귀를 사는 젊은 남성 고객은 맥주도 사더라' 라는 구매 경향을 발견한 적이 있습니다. 데이터 속에 숨어 있는 규칙을 찾는 이른바 '데이터마이닝' 기법을 사용해서 도출한 결과였는데요, 이와 비슷한 사례가 얼마 전에 또 있었습니다.

 

월마트에서는 허리케인(프랜시스)이 곧 상륙할 거라는 예보를 듣고, 허리케인 상륙 이전의 고객들의 과거구매이력을 분석했는데요, 그 결과 허리케인이 상륙하기 전에는 딸기과자와 맥주가 많이 팔린다는 다소 의외의 사실을 발견하게 됩니다. 물론 월마트는 이 분석결과를 바탕으로, 즉시 허리케인 진행방향에 놓여 있는 월마트 점포들의 재고를 신속하게 채워 넣었고, 당연히 상당한 매출실적을 올렸지요. 재미있지 않나요?

, 그럼 오늘은 월마트의 데이터 활용전략에 대해 알아보도록 하겠습니다. 월마트는 미국 내에서만 매주 1억 명의 고객을 확보하고 있습니다. 이들로부터 기본구매정보에서, 부동액제품을 주로 어디에서 구입하는지에 이르기까지 광범위한 정보를 얻고 있지요. 이러한 정보는 품목별로 계산대 통로에서 수집된 후에 매장별, 시간별, 지역별로 기록되어 면밀한 분석을 거쳐 업데이트 됩니다. 현재, 월마트는 460테라바이트 규모의 고객데이터를 보유하고 있는데요, 이는 구글(Google)이 보유한 웹페이지 데이터량의 2배를 훨씬 상회하는 정도로 실로 어마어마한 규모입니다. 이러한 방대한 규모 때문에 최근 월마트의 고객정보남용에 대해 우려의 목소리가 있는 것도 사실입니다.  

월마트의 데이터 전략의 기본은 바로 이러한 광범위한 데이터를 요약하지 않고 사용하는데 있습니다. , 고객의 구매 이력도 요약 데이터가 아닌 상세 데이터를 그대로 가지고 분석하는 것이지요. 월마트의 전 CIO인 랜디 모트는 "요약된 정보를 가지고, 평균화된 정보를 가지고 내리는 의사결정은 평균적인 결과만 가져온다." 면서 데이터웨어하우스 구축의 중요성을 역설한 바 있지요.

 

이러한 '상세 데이터 창고' , 데이터웨어하우스를 통해 점포별, 개인별, 부서별, 지역별 등의 가능한 모든 영역의 분석을 수행하고 이것을 다양한 의사결정에 사용하는 것이지요. 월마트는 이러한 데이터웨어하우스를 크게 2가지 목표를 위해 활용합니다.

 

첫째는 '점포 내 재고상품의 효율화'입니다. 앞서 언급한 장바구니 분석도 이것에 포함되지요. 고객의 장바구니 안에 무엇이 들었는지 기존의 고객 프로파일과 구매 이력 정보를 분석해서 적절하게 상품을 분류하고 고객의 구매 동향과 패턴을 예측합니다. 이 결과를 통해 지역별, 점포별, 시간별로 상품을 다르게 구성하고 매장 내 효율적인 상품 배치에도 활용하게 되지요. 또한, 특정 매장에서 특정한 시간 동안 얼마나 많은 출납원들이 필요한지에 대한 정보를 통해 인력계획에 이용하기도 합니다. 월마트의 현 CIO인 린다 딜먼은 "매장을 새로 세울 때 우리는 그 지역의 모든 고객에 대해 이미 알고 있다", "월마트는 거의 모든 상황을 파악하고 있어 '사건'에 대해 만반의 준비를 갖추고 있다" 라고 언급하고 있지요.


다음은 공급망(Supply chain) 관리입니다. 거대한 데이터를 분석하여 발주에 필요한 모든 요소를 파악하는 것이지요. 데이터웨어하우스로부터 재고 데이터, 재무 데이터, 배송 중인 상품 데이터, 인구통계적 데이터, 공급일정 데이터를 받아 분석하고 상품별, 점포별로 필요량을 예측하게 됩니다.

예측결과에 따른 상품은 즉시 공급망을 통해 신속하게 채워지게 되는데요. 이것은 3기의 인공위성을 통해 전 점포의 획기적인 네트워크 시스템을 구축하고 있기 때문입니다.

 

이 같은 데이터활용전략으로 월마트는 세계에서 가장 많은 점포를 운영하고 있으면서도 모든 점포를 단일점포와 같은 시스템으로 운용하고 있습니다. 월마트의 'Every Day Low Price', 'Low Cost Operation' 이라는 모토는 거대한 데이터를 수집하여 최대한 활용하는 데이터활용전략이 없다면 불가능한 것이었겠지요.

월마트는 이밖에도 판매 후, 제품이 어디로 가는 지까지 추적하는 전자상품태그를 시험 중에 있다고 합니다. 이렇게 되면, 또 하나의 물류혁명이 시작된다고 해도 과언이 아닐 텐데요, 방대한 데이터를 십 분 활용하여 고객에 대한 새로운 룰을 창조해 왔던 월마트의 또 다른 혁신이 기대되는군요.

 

by 에이아이 2009. 8. 9. 13:16

연관규칙 분석 기법 설명한 동영상 자료입니다.

본 자료는 <즐거움을 가져다 주는 자유인> 다음 카페에서 제공하고 있습니다.

   동영상1 (11강_5장 연관규칙의 발굴1)

사용자 삽입 이미지
 

http://cafe.daum.net/ppa2005/Q8bc/97?docid=1F1hZ|Q8bc|97|20090206230817&q=%BF%AC%B0%FC%B1%D4%C4%A2&srchid=CCB1F1hZ|Q8bc|97|20090206230817 

   동영상2 (12강_5장 연관규칙의 발굴2)

사용자 삽입 이미지
 

http://cafe.daum.net/ppa2005/Q8bc/97?docid=1F1hZ|Q8bc|97|20090206230817&q=%BF%AC%B0%FC%B1%D4%C4%A2&srchid=CCB1F1hZ|Q8bc|97|20090206230817


by 에이아이 2009. 8. 4. 19:48

회귀분석이란?


회귀분석 관련 자료 

[1] 회귀분석에 대한 자세한 소개자료
      http://cafe.daum.net/statstory 카페로 부터 얻음.
    


    
[2] 회귀분석에서 문제가 되는 <다중공선성> 설명
      http://cafe.daum.net/statstory 카페로 부터 얻음.

 

by 에이아이 2009. 8. 4. 19:34

참고주소 : http://www.rulequest.com/see5-comparison.html

0. C4.5와 C5.0은 어떻게 다른가?

C4.5 is a widely-used free data mining tool that is descended from an earlier system called ID3 and is followed in turn by See5/C5.0. To demonstrate the advances in this new generation, we will compare See5/C5.0 Release 2.06 with C4.5 Release 8 using three sizable datasets:


Sleep stage scoring data (sleep, 105,908 cases). Every case in this monitoring application is described by six numeric-valued attributes and belongs to one of six classes. C5.0 and C4.5 use 52,954 cases to construct classifiers that are tested on the remaining 52,954 cases. The data are available from here.
Census income data (income, 199,523 cases). The goal of this application is to predict whether a person's income is above or below $50,000 using seven numeric and 33 discrete (nominal) attributes. The data are divided into a training set of 99,762 cases and a test set of 99,761. They can be obtained from the UCI KDD Archive.
Forest cover type data (forest, 581,012 cases); also from UCI. This application has seven classes (possible types of forest cover), and the cases are described in terms of 12 numeric and two multi-valued discrete attributes. As before, half of the data -- 290,506 cases -- are used for training and the remainder for testing the learned classifiers.
Since C4.5 is a Unix-based system, results for the Unix version C5.0 are presented to facilitate comparison. Both were compiled using the Intel C compiler 10.1 with the same optimization settings. Times are elapsed seconds for an unloaded Intel Q9550 (2.8GHz) with 2GB of RAM running 64-bit Fedora Core.
So, let's see how C5.0 stacks up against C4.5.

1. Rulesets: often more accurate, much faster, and much less memory

 These graphs show the accuracy on unseen test cases, number of rules produced, and construction time for the three datasets. Results for C5.0 are shown in blue.

Both C4.5 and C5.0 can produce classifiers expressed either as decision trees or rulesets. In many applications, rulesets are preferred because they are simpler and easier to understand than decision trees, but C4.5's ruleset methods are slow and memory-hungry. C5.0 embodies new algorithms for generating rulesets, and the improvement is dramatic.

Accuracy: The C5.0 rulesets have noticeably lower error rates on unseen cases for the sleep and forest datasets. The C4.5 and C5.0 rulesets have the same predictive accuracy for the income dataset, but the C5.0 ruleset is much smaller.
Speed: The times are almost not comparable. For instance, C4.5 required more than 84 minutes to find the ruleset for income, but C5.0 completed the task in just over 4 seconds.
Memory: C5.0 commonly uses an order of magnitude less memory than C4.5 during ruleset construction. For the forest dataset, C4.5 needs more than 3GB (the job would not complete on earlier 32-bit systems), but C5.0 requires less than 200MB.

2. 기능적인 차이 (C5.0 에서 추가된 기능)

New functionality
C5.0 incorporates several new facilities such as variable misclassification costs. In C4.5, all errors are treated as equal, but in practical applications some classification errors are more serious than others. C5.0 allows a separate cost to be defined for each predicted/actual class pair; if this option is used, C5.0 then constructs classifiers to minimize expected misclassification costs rather than error rates.

The cases themselves may also be of unequal importance. In an application that classifies individuals as likely or not likely to "churn," for example, the importance of each case may vary with the size of the account. C5.0 has provision for a case weight attribute that quantifies the importance of each case; if this appears, C5.0 attempts to minimize the weighted predictive error rate.

C5.0 has several new data types in addition to those available in C4.5, including dates, times, timestamps, ordered discrete attributes, and case labels. In addition to missing values, C5.0 allows values to be noted as not applicable. Further, C5.0 provides facilities for defining new attributes as functions of other attributes.

Some recent data mining applications are characterized by very high dimensionality, with hundreds or even thousands of attributes. C5.0 can automatically winnow the attributes before a classifier is constructed, discarding those that appear to be only marginally relevant. For high-dimensional applications, winnowing can lead to smaller classifiers and higher predictive accuracy, and can even reduce the time required to generate rulesets.

C5.0 is also easier to use. Options have been simplified and extended -- to support sampling and cross-validation, for instance -- and C4.5's programs for generating decision trees and rulesets have been merged into a single program.

The Windows version, See5, has a user-friendly graphic interface and adds a couple of interesting facilities. For example, the cross-reference window makes classifiers more understandable by linking cases to relevant parts of the classifier.

RuleQuest provides free source code for reading and interpreting See5/C5.0 classifiers. After the classifiers have been generated by See5/C5.0, this code allows you to access them from other programs and to deploy them in your own applications.

For more information on See5/C5.0, please see the tutorial.


3. Decision trees: faster, smaller

 For all three datasets, C4.5 and C5.0 produce trees with similar predictive accuracies (although C5.0's are marginally better for the sleep and income applications). The major differences are the tree sizes and computation times; C5.0's trees are noticeably smaller and C5.0 is faster by factors of 6.5, 4.6, and 21 respectively.

4. Boosting

 Based on the research of Freund and Schapire, this is an exciting new development that has no counterpart in C4.5. Boosting is a technique for generating and combining multiple classifiers to improve predictive accuracy.

The graphs above show what happens in 10-trial boosting where ten separate decision trees or rulesets are combined to make predictions. The error rate on unseen cases is reduced for all three datasets, substantially so in the case of forest for which the error rate of boosted classifiers is more than 40% below that of the corresponding C4.5 classifier. Unfortunately, boosting doesn't always help -- when the training cases are noisy, boosting can actually reduce classification accuracy. C5.0 uses a proprietary variant of boosting that is less affected by noise, thereby partly overcoming this limitation.

C5.0 supports boosting with any number of trials. Naturally, it takes longer to produce boosted classifiers, but the results can justify the additional computation! Boosting should always be tried when peak predictive accuracy is required, especially when unboosted classifiers are already quite accurate.


by 에이아이 2009. 8. 4. 19:19

출처: http://cafe.daum.net/statsas/B3o/447?docid=5G5|B3o|447|20070714124050&q=%BF%AC%B0%FC%B1%D4%C4%A2&srchid=CCB5G5|B3o|447|20070714124050

Inside I.E.에서는 산업공학 및 경영과학 분야의 최근 연구동향에 대해 안내합니다.
비즈니스 의사결정 프로세스의 핵심요소로 자리잡고 있는 데이터마이닝을 연속해서 다루고 있습니다.
이번 호에서는 그 마지막 내용으로 데이터마이닝 기법 중 연관규칙의 탐사에 대해 알아보도록 하겠습니다.

데이터마이닝 기법 : 연관규칙의 탐사

(포항공대 전 치 혁 교수)
 

1. 서언

연관규칙(association rule)이란 간단히 말하면 데이터의 항목들 간의 조건-결과 식으로 표현되는 유용한 패턴을 말한다. 연관규칙의 탐사는 기업의 활동, 특히 마케팅에서 가장 널리 사용되고 있다. 예를 들면, 미국의 슈퍼마켓에서 목요일 기저귀를 사는 고객은 맥주도 동시에 구매한다는 연관성을 알아냈다고 한다. 이때, 조건은 ‘목요일, 기저귀’이며 결과는 ‘맥주’라 할 수 있다. 이와 같은 연관규칙의 탐사가 가능하게 된 것은 컴퓨터기술의 발전을 들 수 있겠다. 한 고객이 슈퍼마켓의 계산대에서 계산할 때 쇼핑카트에 담긴 물품들이 바코드를 통하여 컴퓨터에 데이터베이스 형태로 입력되고 이로부터 고객들의 구매행태를 분석할 수 있게 되었다.

위에서 언급한 데이터의 형태는 소위 바스켓(basket) 데이터라 한다. 이 때 한 고객, 즉 한 바스켓의 정보를 하나의 트랜잭션(transaction)이라 한다. 바스켓 형태의 데이터에서는 주로 트랜잭션 내의 연관성을 살펴보고자 하는 것으로, 수많은 트랜잭션을 분석하여 빈번히 나타나는 규칙을 찾아내는 것이다. 이렇게 찾아낸 규칙은 마케팅에 활용된다. 예를 들어, 위의 기저귀-맥주의 규칙을 활용하여 기저귀와 맥주를 가까운 곳에 진열함으로써 매출 신장을 기할 수 있다. 이와 같이 바스켓 데이터로부터 연관규칙을 탐사하는 것을 시장바구니분석(market basket analysis)이라 한다.

연관규칙의 탐사는 한 고객의 시간에 따른 구매정보를 활용하여 이루어지기도 한다. 예를 들면, 가전제품 대리점에서 고객별 시간별 구매제품의 데이터를 활용하여 ‘제품 A를 사는 고객은 추후에 제품 B도 구매한다’는 연관규칙을 이끌어낼 수 있을 것이다. 이와 같은 패턴을 얻어 제품 A를 구매하였으나 제품 B를 구매하지 않은 고객에게 판매활동을 할 수 있다. 이런 시간에 따른 고객데이터를 시퀀스(sequence) 데이터라 한다.

당연한 사실이지만 탐사에서 도출된 연관규칙은 분명하고 유용한 것이어야 한다. 유용하다(useful)는 것은 새롭고도 실행가능하며 설명할 수 있는 것을 말한다고 하겠다. 이에 비해 사소한(trivial) 규칙이란 이미 잘 알려진 사실을 말한다. 예를 들면, ‘페인트를 사면 페인트 붓을 산다’ 는 규칙 같은 것이다. 또한, 설명할 수 없는 규칙은 데이터의 오류일 가능성도 있으며 마케팅에 활용할 수 없기 때문에 역시 유용하다고 볼 수 없다.


2. 연관규칙의 정의 및 성능척도

데이터베이스가 총 n개의 트랜잭션 데이터로 구성되며 전체 m개의 항목으로 구성된다고 하고 이를 I 라 하자. 연관규칙 R은 조건부와 결과부로 구성되며 항목집합인 X와 Y에 대하여 ‘X가 일어나면 Y 도 일어난다’는 의미로 다음과 같이 표현할 수 있다.

R : X ⇒ Y

여기서 X,Y⊆I 이고, X∩Y=Φ이어야 한다. 따라서 연관규칙을 탐사함은 적절한 항목집합 X와 Y를 선택하는 문제로 볼 수 있으며 이를 위해 몇 가지 척도를 고려하고 있다. 우선, 항목집합 X 및 규칙 R에 대한 지지도(support)는 각각 다음과 같이 정의된다.

supp(X) = 집합 X의 항목을 동시에 포함하는 트랜잭션 수의 전체 수(n)에 대한 비율
supp(R) = supp(X∪Y)

즉, 규칙 R에 대한 지지도는 집합 X 또는 집합 Y에 있는 항목을 동시에 포함하는 트랜잭션수의 비율을 나타낸다.

예 1. 다음과 같은 5개의 트랜잭션을 고려해 보자.

트랜잭션
항목
1 b, c, g
2 a, b, d, e, f
3 a, b, c, g
4 b, c, e, f
5 b, c, e, f, g

이때 전체 항목집합 I는 I = {a, b, c, d, e, f, g} 이다. 몇 가지 항목집합에 대한 지지도를 구하면 다음과 같다.

supp({a}) = 2/5 = 0.4, supp({b, c}) = 4/5 = 0.8

다음과 같은 규칙을 고려해 보자.

R: “항목 b와 항목 c가 일어나면, 항목 g도 일어난다”

이 때 규칙 R에 해당하는 항목집합 X와 Y는 다음과 같다.

X={b, c}, Y={g}.

이 경우 X 및 규칙 R에 대한 지지도는 각각 아래와 같이 산출된다.

supp(X) = supp({b, c}) = 0.8
supp(R) = supp({b, c, g}) = 3/5 = 0.6

연관규칙 R의 가치를 평가할 때 통상 다음과 같이 정의되는 신뢰도(confidence)를 사용한다.

conf(R)= supp(X∪Y)/supp(X)

이 신뢰도는 조건부 확률의 개념으로 집합 X(조건)가 발생한다고 할 때 집합 Y(결과)도 동시에 발생할 확률을 의미한다. 즉, 트랜잭션에 X의 항목들을 포함하는 경우 Y의 항목들도 동시에 포함할 확률을 나타내며, 신뢰도가 큰 규칙일수록 의미가 크다고 하겠다.
또한, 신뢰도 이외에 연관규칙의 개선도(lift or improvement)를 함께 사용하는데, 이는 결과가 단독으로 발생할 빈도에 대한 조건과 연계하여 결과가 발생할 가능성의 빈도의 비로 정의된다.

개선도가 1이 됨은 가 성립하므로 항목 집합 X와 Y의 발생이 독립임을 의미한다고 하겠다. 그리고 개선도가 1 전후의 값에 따라 다음과 같은 해석을 할 수 있다.

- lift(R) > 1인 경우, X와 Y의 발생이 양의 상관관계
- lift(R) < 1인 경우, X와 Y의 발생이 음의 상관관계

따라서 개선도가 1보다 큰 규칙이야말로 우연한(랜덤한) 관계가 아닌 필연적 관계를 나타낸다고 하겠다.


3. 연관규칙의 탐사

연관규칙의 탐사는 결국 신뢰도 또는 개선도가 높은 규칙 R을 트랜잭션 데이터로부터 도출하는 과정이다. 따라서 규칙이 R : X ⇒ Y의 형태일 때 적절한 항목집합 X와 Y를 찾는 것이라 할 수 있겠다. 그러나 모든 항목의 조합을 고려하여 성능이 좋은 규칙을 찾는 일은 쉬운 것이 아니므로 이를 위한 효율적인 알고리즘이 요구된다. 예로써 예 1.의 7개 항목으로 구성된 5건의 트랜잭션 데이터에 대하여 집합 X의 후보가 되는 경우수를 볼 때, 1개 항목으로 구성되는 경우가 7가지, 2개의 항목으로 구성되는 경우가 21가지, 3개의 항목으로 구성되는 경우가 35가지 등이 될 것이다.
연관규칙의 탐사를 위한 알고리즘으로 기본적이며 가장 널리 사용되는 것은 1994년에 Agrawal 및 Srikant가 발표한 Apriori 알고리즘으로 다음의 두 단계로 구성된다.

단계 1. 미리 결정된 최소지지도 smin 이상의 지지도를 갖는 모든 빈발 항목집합들(large itemsets)을 찾는다.
단계 2. 빈발 항목집합 L에 대한 부분집합 A를 고려한다. 미리 결정된 최소신뢰도 cmin에 대하여 supp(L)/supp(A) ≥ cmin 이면, R: A ⇒ (L-A) 형태의 규칙을 출력한다. 즉, 이 규칙의 지지도는 supp(R)=supp(L)이며, 신뢰도는 conf(R)=supp(L)/supp(A) 가 된다.

3.1. 빈발 항목집합 생성

빈발 항목집합을 도출하기 위하여 우선 하나의 항목으로 이루어지는 후보집합군(C1)을 형성하고 최소지지도 이상을 갖는 집합군(L1)을 생성한다. 다음으로 L1으로부터 두개의 항목으로 이루어지는 후보집합군(C2)를 만들고 최소지지도 이상을 갖는 집합군(L2)을 생성하며, 다시 L2로부터 세 항목으로 이루어지는 후보집합군(C3)과 빈발 항목집합군 L3를 만드는 등 이러한 과정을 더 이상 새로운 집합이 생성되지 않을 때까지 반복한다.
로부터 를 생성할 때 접합(join)연산자(*)를 사용한다. L1으로부터 C2를 만드는 경우에는 L1의 한 항목에 대한 모든 조합이 2-항목 집합인 C2가 될 것이다. 그러나 L2에서 두 집합의 조합은 최대 4개의 항목을 포함할 수 있으므로 C3를 형성할 때 L2의 집합 중 하나의 항목이 동일한 것들만 대상으로 하여야 한다. 마찬가지로 L3로부터 C4를 형성할 때는 L3의 집합 중 두개의 항목이 동일할 때 가능하게 된다. 예로써, L2=[{a,b}, {a,c}, {b,d}]라 할 때 {a,b,c}와 {a,b,d}가 3-항목 집합의 후보가 될 것이다. 그러나, C3를 구성할 때 {a,b,c}는 제외된다. 왜냐하면, {a,b,c}의 지지도는 {b,c}의 지지도 이하인데 {b,c}가 L2에 포함되지 않았다는 것은 이의 지지도가 최소지지도 미만이라는 것을 나타내기 때문이다. 이러한 과정은 Apriori 알고리즘 중 'apriori-gen' 함수에 의하여 수행된다.

예 2. (예 1.의 계속). 예 1.의 트랜잭션 데이터를 바탕으로 빈발 항목집합을 만들어보자. 우선, C1은 다음과 같다.

C1=[{a}, {b}, {c}, {d}, {e}, {f}, {g}]

최소 지지도를 0.4(5개의 트랜잭션 중 2개)라 하면 1-항목으로 이루어지는 빈발 항목집합군은 다음과 같다.

L1=[{a}, {b}, {c}, {e}, {f}, {g}]

2-항목 빈발집합의 후보 C2에 다시 최소지지도 0.4를 적용하면 L2는 다음과 같다.

L2=[{a,b}, {b,c}, {b,e}, {b,f}, {b,g}, {c,e}, {c,f}, {c,g}, {e,f}]

C3를 구성하기 위하여 L2의 집합에 접합연산자를 적용하면 다음과 같다.

C3=[{b,c,e}, {b,c,f}, {b,c,g}, {b,e,f}, {c,e,f}]

이 때 {a,b,c} 는 {a,c}가 L2에 포함되지 않았으므로 C3에 포함될 수 없음을 볼 수 있다.
C3의 모든 집합은 최소지지도 이상이므로 L3는 C3와 동일하다.

Apriori 알고리즘을 단계별로 정리하면 다음과 같다.

단계 0. 최소지지도 smin을 정한다.

k=1
C₁=[{i₁},{i₂},...,{im}]
L₁={c∈C₁| supp(c) ≥ smin

단계 1. k=k+1

Lk-1로부터 Ck 형성 (apriori-gen 함수)
단계 1-1. (join) Lk-1의 집합들을 접합하여 k- 항목 집합군을 형성한다.

C= Lk-1 * Lk-1

단계 1-2. (prune) C의 (k-1)- 항목 부분집합이 Lk-1에 속하지 않을 때 이를 모두 제거한 후 Ck를 형성한다. Ck=Φ이면 Stop.

단계 2. Ck의 집합 중 지지도가 최소지지도 이상인 것을 모아 Lk를 생성한다.

Lk={c∈Ck | supp(c) ≥ smin}

3.2. 규칙의 탐사

앞에서 언급한 바와 같이 규칙의 탐사를 위하여 우선 도출된 빈발 항목집합 L 각각에 대한 부분집합 A를 고려한다. 여기서 L은 위의 L2, L3 등을 포함한다. 그리고, 미리 결정된 최소신뢰도 cmin에 대하여 supp(L)/supp(A) ≥ cmin 이면, R: A ⇒ (L-A) 형태의 규칙을 출력한다. 즉, 이 규칙의 신뢰도 conf(R)=supp(L)/supp(A) 가 cmin 이상 되도록 하는 것이다.
현실의 경우 결과부에 하나의 항목만을 포함시키는 규칙을 도출하는 것이 이의 적용성 때문에 널리 사용되나, Agrawal & Srikant (1994)의 알고리즘에는 모든 가능한 규칙을 보다 효율적으로 탐사하는 방법이 소개되고 있다.

예 3. 예 1.의 트랜젝션 데이터에 대하여 예 2.에서 구해진 빈발 항목집합군 중 집합 L={b,c,g}을 고려해 보자. 이 때 결과부에 1-항목을 포함하는 규칙의 후보와 이에 대응되는 신뢰도는 다음과 같다.

R1: {b,c}⇒{g} conf(R1)=0.6/0.8 = 0.75
R2: {b,g}⇒{c} conf(R2)=0.6/0.6 = 1
R3: {c,g}⇒{b} conf(R3)=0.6/0.6 = 1

따라서 최소신뢰도를 0.7이라 하면 R1, R2, R3 모두 최소신뢰도 이상이 된다.

4. 결언

서언에서 언급한 시퀀스 데이터에 대하여도 유사한 알고리즘이 적용되고 있으나 여기서는 생략한다

한편, 분석할 트랜잭션 데이터에 어떤 항목들을 포함시킬 것인가는 분석에 앞서 결정하여야 할 중요한 문제 중 하나라 하겠다. 통상 슈퍼마켓 등에서 취급하는 제품 수는 수만 가지가 넘기 때문에 이러한 제품 하나하나를 모두 항목으로 선정하기에는 여러 어려움이 있다. 따라서 제품을 계층적으로 분류하여 적절한 계층에 속하는 것들을 항목으로 선정하는 방안을 사용한다. 제품분류에서 상위수준으로 갈수록 보다 포괄적인 항목(generalized item)이 사용된다.

항목이 너무 세분화되어 많은 경우 공통 항목의 트랜잭션 수가 적어 유용한 규칙을 도출하기 어려울 수 있으며, 반대로 항목이 너무 작은 경우에는 도출된 규칙이 쓸모없을 수 있기 때문에 항목의 선정이 중요하다 하겠다. 또한, 항목이 증가함에 따라 규칙탐사에 소요되는 계산시간이 급속도로 증가하기 때문에 원하는 계산복잡도에 알맞은 항목수를 결정할 필요가 있다. 항목을 선정하는데 있어 하나의 가이드라인은, 트랜잭션 데이터에 드물게 나타나는 것은 제품의 계층적 분류에서 보다 상위 수준의 항목을 사용하고, 자주 나타나는 경우에는 보다 하위 수준의 항목을 사용하여 결과적으로 트랜잭션 데이터에 빈도수가 비슷하게 되도록 하라는 것이다.

by 에이아이 2009. 8. 4. 19:10


다중공선성의 상태는 데이터 분석 시 문제를 야기하는 하나의 특성으로 알려져있다. 특히 회귀분석에서 다중공선성의 입력 데이터의 분석은 부정적인 영향을 미치는 것으로 알려져있고, 이를 해결하는 방법에 대해서도 오래전부터 많은 연구가 있었다.

관련 연구가 불충분하기는 하지만 아마 회귀분석 뿐 아니라 다른 분석 방법 등(결정트리 등)에서도 다중공선성이 부정적인 영향을 줄 것으로 예상된다. 이에 대한 추가적인 연구들이 필요하다고 생각된다. 

상관성(피어슨 상관계수)는 익숙하지만, 다중공선성 이란 단어는 익숙하지 않은 경우가 많다. 본 자료에서는 다중공선성에 대해서 정리하고자 한다.

< 목 차 >
1. 소개 및 정의              4. 해결방법
2. 문제점                      5. SPSS에서의 활용      
3. 진단방법                   6. 참고자료    
 
1. 소개 및 정의

다중공선성(Multicollinearity)은 입력변수들 간의 상관정도가 높은 상태를 말한다.

좀 더 자세히 설명하면,
데이터가 (p+1)개의 수치형(양적) 변수를 가지며, 
x1, x2, ... , xp의 p개의 입력(독립)변수와 Y 라는 1개의 종속변수로 구성되어 있다고 하자.
다중공선성이란 위의 데이터에서 p개의 입력변수들 사이에 상관관계가 존재하는 상태를 의미한다.

그럼, 이런 의문이 들지 않는가?

다중공선성(multicollinearity)과 상관성(Correlation)이 같은 것 아닌가?
(여기서 상관성이란 피어슨 상관계수와 같이 두 변수 간의 관계를 의미한다.)

정확한 이해를 위하여 다중공선성과 상관성의 차이를 구분해보자.

상관성은 (피어슨 상관계수 등에 의해 계산되는) (1) 두 변수 간의 상관정도를 계산하고 (2) 독립변수와 종속변수를 구분하지 않는다. 반면, 다중공선성은 (1) 두개 이상의 변수들 간의 상관정도를 계산하고 (2) 독립변수들 간의 관계 만을 고려한다.

상관성과 다중공선성은 측정하는 방법에도 차이가 있다. 

 상관성  Pearson Correlation 등
 다중공선성  VIF(분산팽창계수 또는 분산팽창인수)
 Tolerance(공차한계) 등

그럼, 사전적으로 좀 더 정확하게 다중공선성의 정의 및 의미를 살펴보고 소개를 마무리하자.
아래 내용은 위키피디아 백과사전에서 <다중공선성문제>에 대한 정의(설명)을 가져온 것이다.  

다중공선성문제(Multicollinearity)는 통계학의 회귀분석에서 독립변수들 간에 강한 상관관계가 나타나는 문제이다. 독립변수들간에 정확한 선형관계가 존재하는 완전공선성의 경우와 독립변수들간에 높은 선형관계가 존재하는 다중공선성으로 구분하기도 한다. 이는 회귀분석의 전제 가정을 위배하는 것이므로 적절한 회귀분석을 위해 해결해야 하는 문제가 된다. 위키피디아 백과사전

다중공선성은 다른 용어로 공선성이라 불리기도 한다. 두 개가 같은 의미로 사용된다. 영어로도 마찬가지이다. Multicollinearity 와 Collinearity 는 같은 의미로 사용된다. multi-collinearity 라는 쓰기도 한다.

사전(영어사전, 국어사전 등)을 찾아보면 위 용어가 포함되어 있는 않는 경우가 많다. 원래 전통적으로 존재하던 단어는 아니고 통계학을 연구하는 과정에서 만들어진 신조어로 이해할 수 있다. 그러나 통계학 분야, 데이터 분석 분야에서는 연구 논문, 서적 등에서 널리 사용되는 단어이므로 통계 및 데이터마이닝 등 데이터 분석 분야를 연구한다면 많이 접하게 되는 단어이다.

2. 문제점

이번에는 데이터에 다중공선성의 특성이 존재할 때 발생하는 문제점을 고려해보자.

분석하고자 하는 데이터에 <다중공선성>이 강하게 존재할 때

이 데이터를 <회귀분석>에 적용하면 어떤 문제가 생길까?
이 데이터를 <결정트리>에 적용하면 어떤 문제가 생길까?
( 그 외의 다른 방법(알고리즘)들도 차후 고려해봐야하겠다.. )

다중공선성 데이터를 <회귀분석>에 적용하는 경우 어떤 문제가 발생할까? 

분석 결과인 회귀 계수가 불안정해지는 것이다. 회귀계수가 해당 변수의 종속변수에 미치는 영향력을 올바로 설명하지 못하게 된다. 즉, 다중공선성을 고려하지 않고 회귀분석을 수행한 후 그 결과를 해석하면 잘못된 결론(변수의 중요성을 설명할 때)을 내리게 되는 문제가 발생한다.  

다중공선성 데이터를 <결정트리>에 적용하는 경우 어떤 문제가 발생할까?
분류에 중요한 영향을 미치는 변수가 결정트리의 분리 조건에 나타나지 않게 되는 문제가 발생한다.
또한 중요변수가 사용되지 않음으로 인해서 분류율(정확도)가 낮아지게 되는 문제가 있다.

3. 다중공선성 진단(측정) 방법

이번에는 데이터에 다중공선성의 정도를 진단하는 방법에 대해서 알아보겠다.
상관성을 계산하는 방법은 잘 알다시피 피어슨 상관계수가 있다. 물론, 그 외에도 여러가지방법이 있다.

다중공선성을 계산하는 방법은 그와 별도로 존재한다.
2개 이상의 변수들 간의 상관성을 측정하기 때문에 당연히 피어슨 상관계수로는 계산할 수 없다.

물론, 상관성 매트릭스 Correlation Matrix 를 작성하여 데이터의 다중공선성을 판단하는 경우도 있지만, 각 변수의 다중공선성을 정확히 판단하기 위해서는 별도의 측정 방법이 필요하다.  

이 같이 각 변수들을 행/열의 값으로 하는

행렬을 구성한다. 대각선은 자기자신과 상관관계이므로 1이며, 행렬의 값은 대칭이므로 한쪽면만 계산한다.

이 데이터는 다중공선성의 문제가 없어 보인다.

그러나 정확한 진단을 위해서는 위의 <상관성 행렬> 보다는 진단방법과 기준을 사용해야 한다.

다중공선성의 수식으로는 VIF, Tolerance, CN 등의 계산 방법이 존재한다. (VIF:분산확대인자 또는 분산팽창계수, Tolerance:공차한계, CN:상태지수)

VIF (Variation Inflation Factor, 분산팽창지수) 측정법이 이 들중에서도 가장 많이 (일반적으로) 사용된다.
SPSS 통계 프로그램에서도 회귀분석 수행 창에서 VIF 측정을 선택하여 점검할 수 있도록 지원해주고 있다.

각 방법에 대해서는 나중에 자세히 설명해야 하겠다. (개념, 계산 방법 및 자세한 수식)  

일반적으로
VIF 즉, 분산팽창계수가 10 이상 일때 다중공선성이 존재한다고 판단한다.
Tolerance 즉, 공차한계는 0.1 이하 일때 다중공선성이 존재한다고 판단한다.
(사실, VIF 와 Tolerance는 같은 방법이다. Tolerance의 역수를 취한 값이 VIF 값이다.)  

그런데 왜 VIF 가 10이상일때 다중공선성이 존재한다고 판단할까?

참고로 VIF 값은 0에서 무한대의 값의 범위를 갖는다. 여기서 10이라는 기준값은 명확하게 정해진 것은 아니다. 단지 일반적인 기준일 뿐이다. 그러나 10 이상이라는 기준이 일반적으로 사용되는 기준이므로 구지 다른 기준값을 사용하기보다는 우리도 연구할 때 10 을 기준으로 사용하는 것이 좋겠다.


이해를 돕기 위하여 다른 질문을 해보자.

피어슨 상관계수를 계산했을 때 얼마 이상이면 두 변수간에 상관성이 있다고 할 수 있을까?
잘 알고있는 바와 같이, 피어슨 상관계수는 -1 에서 1 의 값의 범위를 갖는다.
어떤 분야, 어떤 연구에서는 절대값 0.5 이상을 기준으로 하고, 어떤 경우에는 0.7 이상을 기준으로 한다. 
즉, 명확한 기준값은 없으며 연구자, 연구분야, 연구내용에 따라 기준값을 정해야 할 것이다.  

SPSS를 사용하여 다중공선성을 측정하는 방법을 아래 글에 정리하였다.
http://ai-times.tistory.com/142


4. 해결책

이번에는 다중공선성의 문제를 해결하는 방법에 대해서 알아보자.

(0) 기본적인 방법들
- 각 입력변수를 제거/추가하면서 회귀계수의 변동정도를 파악한다.
- 다중공선성이 높다고 판단된 변수들 중에서 몇 개를 제거한 후 분석을 한다.

(1) PLS 회귀분석
PLS는 Partial Least Square 또는 Projection to Latent Structures 의 약자이다.
SPSS 18.0 버전의 프로그램에 추가된 기능이다. (2008/06 SPSS 세미나 자료 참고)  
인자분석(요인분석)을 사용하여 Latent(잠재) 변수를 찾고 활용하는 방법이다.  

(2) OLS 회귀분석
다중공선성에 적합하도록 알고리즘을 개선한 기존과 다른 회귀분석 알고리즘이다.


5. SPSS에서의 다중공선성 측정 방법 

SPSS 통계 프로그램에서는 <다중공선성>에 관련된 기능들을 지원하고 있다.

(1) 다중공선성의 진단
각 입력변수 별로 VIF 수치를 제시해준다.
이 값을 가지고 입력 데이터에 다중공선성의 정도를 파악할 수 있다. 만약, VIF 값이 높은 변수가 있다면
분석 및 모델 해석 시 고려해 주어야 한다.
 
SPSS를 사용하여 다중공선성을 측정하는 방법을 아래 글에 정리하였다.
http://ai-times.tistory.com/142


(2) PLS 회귀분석
다중공선성에 견고한 새로운 알고리즘(기능)을 버전. 18.0 (?) 부터 지원하고 있다.
기본 기능은 아니므로 이 기능을 사용하려면 사용하려면 해당 모듈을 추가 설치해야 한다.




6. 참고 자료 (인터넷 글)  

[1] http://kr.blog.yahoo.com/skk1991/754126

[2] http://cafe.daum.net/statstory/Lnxm/35?docid=10OJP|Lnxm|35|20090514174020&q=%B4%D9%C1%DF%B0%F8%BC%B1%BC%BA&srchid=CCB10OJP|Lnxm|35|20090514174020

[3] http://blog.daum.net/kjh325/5649828
     ( SPSS에서 VIF 를 측정하고 해석하는 방법 ) 

[4] http://blog.naver.com/ibuyworld/110048919032

[5] http://blog.naver.com/azureguy/130035562492

[6] http://blog.naver.com/leespecia/20089849767
     (VIF 및 Tolerance 측정 결과 및 의미)


7. 참고 자료 (파일)  

[1] 회귀분석과 다중공선성

[2] 다중공선성의 진단방법


[3] 다중공선성 진단 (한글파일)
 

by 에이아이 2009. 8. 4. 18:42
| 1 2 3 4 5 6 |