|
연관 규칙과 의사결정트리를 이용한 패턴 탐사
지난 시간에 공부한 데이터 마이닝을 토대로 이번 시간에는 어떤 사건이 일어나면 다른 사건이 일어날 수 있는 지지도와 신뢰도를 바탕으로 트랜잭션 데이터의 각 아이템간의 연관성을 찾는 연관 규칙에 대해 알아보고 아울러 의사결정트리의 알고리즘과 이를 이용한 패턴 탐사에 대해 공부해 보도록 하겠다.
연재순서
1회(99.12) : 뉴밀레니엄의 경영 도구, 데이터 마이닝
2회(2000.01) : 연관 규칙과 의사결정트리를 이용한 패턴 탐사
3회 : 신경망을 이용한 예측 시스템, 다중퍼셉트론의 구현
컴퓨터 시스템의 급속한 발전과 데이터베이스 시스템 사용의 보편화는 데이터베이스에 저장되는 데이터의 양적 증가를 초래하게 됐고 그러한 대용량의 데이터베이스 안에는 일정한 형식의 질의로는 검색이 쉽지 않은, 그래서 사용자가 미처 파악하지 못한 중요한 정보가 존재할 수가 있게 됐다. 본 프로젝트에서 구현한 데이터 마이닝 시스템은 이러한 대용량의 데이터베이스 안에 숨겨져 있는 유용한 패턴, 지식을 추출하는 방법론이라는 것을 지난 시간을 통해 얘기한바 있다. 그러므로 이번 시간에는 많은 지식 탐사 기법 중에서 연관 규칙과 의사결정트리에 대해 알아본다.
연관 규칙의 정의
연관 규칙이란 어떤 사건이 일어나면 다른 사건이 일어난다와 같은 연관성을 이야기한다. 주어진 트랜잭션의 집합이 있고 서로 소 관계인 두 개의 부분 집합의 연관 규칙은 "A→B"로 표시할 수 있다. 이때 전체 항목들의 집합 A는 결론 항목들의 집합 B를 야기한다고 정의할 수 있다. 트랜잭션의 모임으로부터 한 항목 집합의 존재와 다른 항목 집합과의 연관 관계를 요약할 수 있는데, 연관 관계는 항목들 사이에 존재하는 유사성 또는 패턴을 의미한다. 연관 규칙의 기본 개념은 item set, 즉 트랜잭션의 집합이 있고 이 트랜잭션 집합을 I라고 표현했을 경우 공집합이 아닌 항목 집합 X, Y에 대해서 X⊂I, Y⊂I일 경우 가정 X라는 사건이 발생했을 때 결과 Y라는 사건이 발생한다라는 것을 말한다. X와 Y의 교집합이 공집합이라는 특성을 갖고 항목 집합 I의 부분 집합 X에 대해 X⊆T이면 T는 X를 만족한다고 정의할 수 있다
.
예를 들면 편의점에서 목요일에 기저귀를 구매하는 고객들은 맥주도 동시에 구매한다는 연관성이 있음을 연관 규칙 탐사의 결과로 얻어 낼 수 있는 것이다. 편의점에서 각 고객이 구매하는 물품들의 집합을 한 트랜잭션이라고 하고 이런 물품 구매에 관련한 트랜잭션이 일정한 기간동안 데이터베이스에 저장돼 있다면 기저귀를 사는 사람이 맥주를 구매하는 연관성을 연관 규칙으로 다음과 같이 표현할 수 있다.
기저귀→맥주(2% 지지도, 30% 신뢰도)
여기에서 의미하는 2%의 지지도(Support)는 주어진 데이터베이스의 트랜잭션들 중에서 2%가 기저귀와 맥주를 동시에 구입한다는 것이고 30%의 신뢰도(Confidence)라는 것은 기저귀를 사는 고객들 중에서 30%가 맥주를 산다는 것을 의미한다. 바꿔 얘기하면 물품 구매 트랜잭션 중에서 2%의 지지도는 맥주와 기저귀를 모두 구입한 트랜잭션의 비율을 의미하며, 30%의 신뢰도는 맥주를 구입한 고객 중에서 기저귀를 구입한 고객의 비율을 의미한다. 연관 규칙 탐사에서는 사용자가 지지도와 신뢰도의 값을 적절하게 명시해 트랜잭션 데이터베이스에서 사용자가 정한 정도의 모든 상호 연관성을 발견해 낼 수 있고, 편의점 데이터베이스와 같은 성격의 데이터베이스에서 고객들의 구매 패턴을 찾을 수 있다. 이러한 연관성과 구매 패턴을 바탕으로 시장성 예측에 적용할 수도 있을 것이다.
지지도와 신뢰도
앞에서 밝힌 바와 같이 연관 규칙이란 지지도와 신뢰도를 바탕으로 트랜잭션 데이터의 각 아이템간의 연관성을 찾는 것을 말한다. 그러면 여기에서 연관 규칙의 척도라 말할 수 있는 지지도와 신뢰도의 개념에 더욱 확실하게 정리하는 것이 필요할 것이다. 지지도란 다음과 같이 전체 트랜잭션에 대한 x와 y를 만족하는 트랜잭션의 비율을 의미한다.
S(x,y) = P(x, y) / 전체 트랜잭션의 수
이러한 지지도는 규칙의 통계적 중요성으로 인식될 수 있으며 빈번하게 발생하는 패턴 또는 규칙의 빈도를 의미하므로 그 패턴이나 규칙의 유용성이 증대되려면 지지도가 커야 한다는 것을 알 수 있다. 신뢰도는 x를 만족하는 트랜잭션에 대한 y를 만족하는 트랜잭션의 비율을 의미하며, 이러한 신뢰도는 가정 x일 경우 결론 y의 규칙에 대한 정확도를 측정할 수 있는 지표가 되고, 따라서 높은 지지도는 정확한 예측을 가능하게 해준다.
C(x,y) = P(x,y) / p(x)
예를 들어 빵과 버터를 구입한 고객 중에서 90%의 고객이 우유도 함께 구매한다는 규칙이 있다고 하자. 식료품점에는 다양한 구매 패턴이 존재할 수 있고 모든 경우의 구매 패턴 가지수는 식료품점의 전체 트랜잭션 수가 된다. 이중에서 전체 트랜잭션 수에 대한 빵, 버터, 우유를 구매한 패턴의 비율이 바로 지지도가 된다.
지지도(Support) = 빵, 버터, 우유를 구입한 트랜잭션의 수 / 전체 트랜잭션의 수
신뢰도는 빵과 버터를 구입한 트랜잭션 수에 대해 빵, 버터, 우유를 구입한 트랜잭션의 수에 대한 비율로 나타낼 수 있다.
신뢰도 = 빵, 버터, 우유를 구입한 트랜잭션의 수 / 빵, 버터를 구입한 트랜잭션의 수
결론적으로 어떤 규칙의 신뢰도는 얼마나 조건부에 대해 결과부가 자주 적용될 수 있는지를 나타내고, 반면에 지지도는 그 규칙의 전부가 얼마나 믿을만한지를 나타낸다고 말할 수 있다.
빈발 항목 집합
트랜잭션 데이터베이스는 중복을 허용하지 않고 순수한 집합의 개념을 확장해 트랜잭션과 다른 모든 항목 집합들 내에 존재하는 항목들은 이미 정렬돼 있는 것으로 가정해야 한다. n개의 트랜잭션들로 이루어진 데이터베이스 D가 존재할 때 고유한 트랜잭션 번호인 TID가 부여된다. 어떤 항목들의 집합 X를 포함하는 트랜잭션 T를 생각해 보자. 만일 트랜잭션 T가 X⊆T일 경우 연관 규칙은 X→Y 형태로 나타날 수 있고 항목들의 부분 집합인 X와 Y의 교집합은 공집합이 된다.
트랜잭션 데이터베이스에서 연관 규칙을 찾는다는 것은 사용자가 명세한 최소 지지도(minsup)와 최소 신뢰도(minconf) 보다 큰 지지도와 신뢰도를 갖는 아이템셋을 찾는 것이라고 말할 수 있고, 최소 지지도보다 큰 지지도를 갖는 집합들을 빈발하다라고 말한다. 이런 경우에 항목들의 집합 X를 빈발 항목 집합(Large Itemset)이라고 한다. 우리가 최소 지지도에 관심이 있는 이유는 트랜잭션 데이터베이스에 대해 관심있을 정도로 자주 일어나는 항목만을 고려해야 하기 때문이다. 지금까지의 내용을 간략하게 정리한다면 주어진 데이터베이스에서 연관 규칙을 찾는다는 것을 다음과 같이 두 단계로 나눠 생각할 수 있다.
단계 1
명세된 최소 지지도 이상의 트랜잭션 지지도를 갖는 모든 항목 집합(itemsets)들을 찾는다. 하나의 항목 집합에 대한 지지도는 해당 항목 집합을 포함한 트랜잭션의 수로 생각할 수 있으며, 최소 지지도를 만족하는 항목 집합을 빈발 항목 집합(Large Itemsets)이라 하며, 그외 모든 항목 집합들을 작은 항목 집합(Small Itemsets)이라 한다. 본 프로젝트에서는 빈발 항목 집합을 찾기 위해서 Apriori 알고리즘을 사용할 것이다.
단계 2
데이터베이스로부터 연관 규칙을 생성하기 위해 빈발 항목 집합을 사용하게 되는데, 모든 빈발 항목 집합 l에 대해서 l의 공집합이 아닌 모든 부분 집합을 찾아야 한다. 이러한 각각의 부분 집합 a에 대해 만약 지지도(a)에 대한 지지도(1)의 비율이 적어도 최소 신뢰도 이상이면, 다시 말해 '지지도(1)/지지도(a) ≥ 최소 신뢰도'이면 'a→(l-a)' 형태의 규칙을 찾을 수 있다. 이 규칙의 지지도는 지지도(1)이고 신뢰도는 지지도(l)/지지도(a)가 된다. 실제적으로 연관 규칙 탐사의 전체적인 성능은 첫째 단계에서 결정되고 먼저 빈발 항목 집합을 확인한 후에 해당되는 연관 규칙을 단계 2의 방법으로 쉽게 유도할 수 있다.
빈발 항목 집합 찾기
빈발 항목 집합들의 수는 모든 항목들의 멱집합의 크기와 같고 이것은 관심이 있는 항목들의 수가 많아지면 많아질수록 기하급수적으로 증가하게 된다. Apriori 알고리즘에서 빈발 가능성이 있는 항목 집합들을 후보 항목 집합(Candidates)이라고 하며 이들 후보 항목 집합들 중에서 빈발 항목 집합을 찾기 위해서 데이터베이스를 스캔하면서 지지도를 계산하게 된다. 이 후보 항목 집합의 수가 많다면 연관 규칙의 성능은 좋아질지도 모르지만 사실 연관 규칙을 찾기 위한 계산은 많은 프로세싱 시간과 메모리를 요구하기 때문에 후보 항목 집합의 수를 적절히 고려할 수도 있다.
Apriori 알고리즘
그러면 이제부터 Apriori 알고리즘을 이용해 빈발 항목을 찾는 과정을, 다시 말해 LargeItem 테이블을 생성하는 과정에 대해 알아보겠다. (리스트 1)은 Apriori 알고리즘에 대한 의사 코드이다. 첫째 과정에서 'large 1 - itemset'을 생성하기 위해 단순히 아이템이 나타난 회수를 세고 있다. 3번째 줄과 4번째 줄을 살펴보자. 먼저 (k-1)번째 경로에서 발견된 'Large itemset L '은 Apriori-gen 함수를 이용해 k번째 Candidate itemset인 C 를 발생하는데 이용된다. 또한 Apriori-gen 함수는 (리스트 2)에 보이고 있다. 다음 단계로 데이터베이스를 스캔하고 k번째 후보 항목 집합 C 의 후보 항목들의 지지도를 계산하게 되고 계산을 더욱 빠르게 하기 위해 C 안의 후보 항목들을 효율적으로 결정해야 한다.
다음은 (리스트 1)의 5번째 줄에 나와 있는 subset 함수에 대해 알아보자. 후보 항목 집합 C 는 해시 트리에 저장된다. 해시 트리의 한 노드는 아이템셋들의 리스트를 종단 노드(Leaf Node)에 저장할 뿐만 아니라 해시 테이블을 내부 노드에 저장한다. 해시 트리의 루트 노드(Root Node)는 깊이를 1로 하고 깊이가 d인 내부 노드는 d+1의 깊이를 가졌고 종단 노드에는 각각의 아이템셋이 저장된다. 우리가 하나의 아이템셋 c를 추가하고자 할 때는 루트에서 출발해 종단 노드에 도착할 때까지 트리를 탐색하게 된다. 깊이가 d인 내부 노드에서 아이템셋의 d번째 아이템은 해시 함수를 이용해 분기를 결정하게 된다.
종단 노드에 있는 아이템셋들의 수가 증가하게 되면 종단 노드를 내부 노드로 변환시켜야 한다. 루트 노드에서 출발할 때 subset 함수는 트랜잭션 t에 관계된 모든 후보 항목들을 찾게 되고 종단 노드에 도착하게 되면 t에 포함된 종단 노드 안의 아이템 셋들의 후보 항목을 찾게 된다. 만약 아이템 i를 해시하면서 내부 노드에 도착했다면 t에서 i번째 있는 아이템을 해시하게 되고 이러한 절차를 버켓에 대응하는 노드에 순환적으로 적용시키면 된다.
Apriori Gen 함수
Apriori-gen 함수는 후보 집합을 생성하는 데 중요한 역할을 하는 함수이다. Apriori gen 함수는 후보 항목 집합의 수를 줄일 수 있으며 이 방법은 조인(Join) 단계와 전지(Prune) 단계로 구성된다. (리스트 2)는 Apriori-gen의 의사 코드이다. (리스트 2)의 알고리즘처럼 Apriori-gen은 빈발 항목 집합 L 를 입력으로 사용하고 그들의 k-1개의 같은 항목들과 두 개의 다른 항목들을 찾아 후보 (k+1) 항목 집합을 형성하기 위해 조인된다.
두 번째 단계에서는 만들어진 후보 (k+1)-항목 집합의 부분 집합 k-항목 집합들이 이미 L 에 있는지 조사하고, 없으면 이 후보 항목 집합을 전지하게 된다. 예를 들어 L 가 {{1 2 3}, {1 2 4}, {1 3 4}, {1 3 5}, {2 3 4}}라고 했을 때 조인 단계를 거치고 나면 C 는 {{1 2 3 4}, {1 3 4 5}}가 될 것이다. 전지 단계에서 {1 3 4 5}는 삭제돼야 하는데 왜냐하면 {1 4 5}는 L 가 아니기 때문이다. 따라서 결국엔 C 에는 {1 2 3 4}만 남게 된다.
지금까지의 얘기가 조금은 지루하고 무슨 말인지 잘 이해가 되지 않는 독자들이 있을 것이다. 그래서 다음과 같이 하나의 예를 들어 지금까지의 빈발 항목을 찾는 과정을 설명하고 정리하고자 한다. (표 1)과 같은 트랜잭션 데이터 베이스가 있다고 가정한다.
첫째 패스에서 각 항목의 발생 빈도수를 세기 위해 단순히 모든 트랜잭션들을 스캔해 후보 1-항목 집합들의 집합 C 을 얻을 수가 있다. 최소 지지도가 2라고 가정하면(S = 2), 필요로 하는 최소 지지도를 만족하는 빈발 1-항목 집합들의 집합 L 을 얻을 수 있다. 빈발 2-항목 집합들의 집합을 얻어내기 위해 모든 부분 집합도 역시 최소 지지도를 가져야 한다는 사실에 입각해 Apriori는 후보 항목 집합들의 집합 C 를 생성하기 위해 L 과 L 을 조인하게 된다. C 는 (|L | / 2)개의 2-항목 집합들로 이뤄진다. |L |이 크게 되면 (|L | / 2)도 커지게 됨을 알 수 있다. 다음으로 D에 속한 네 개의 트랜잭션들이 스캔돼 읽히고 C 에 속한 후보 항목 집합의 지지도는 계산되고 빈발 2-항목 집합들의 집합 L 는 C 에 속한 각 후보 2-항목 집합의 지지도에 기초해 결정된다.
이제 독자의 이해력이 요구되는 중요한 부분이다. 후보 항목 집합들의 집합 C 가 L 에서 어떻게 구해지는 살펴보기 바란다. L 에서 첫 항목이 같은 두 개의 빈발 2-항목 집합들을 먼저 구하면 2가 동일 항목이기 때문에 {2 3}과 {2 5}를 구할 수 있다. 다음으로 {2 3}과 {2 5}의 두 번째 항목들로 구성된 2-항목 집합 {3 5}가 빈발 2-항목 집합들에 속하는 가를 검사한다. {3 5}가 L 의 원소로 빈발 집합이므로 {2 3 5}의 모든 부분 집합들은 빈발하다는 것을 알았고, 그러므로 {2 3 5}는 후보 3-항목 집합이 된다. L 에서 더이상의 다른 후보 3-항목 집합을 구할 수 없고 트랜잭션들을 스캔하면서 빈발 3-항목 집합을 생성하게 된다. L 에서부터 구성될 수 있는 후보 4-항목 집합이 더이상 존재하지 않으므로 빈발 항목 집합 발견 과정은 끝나게 된다.
알고리즘 구현
그러면 지금까지 설명한 연관 규칙에 대한 기본 지식과 Apriori 알고리즘을 이용해 제작된 자동차보험회사 사고 관련 데이터베이스를 기반으로 구현한 마이닝 시스템의 실제 구현 내용을 살펴보자. 그 첫째 단계로 자동차 사고 데이터베이스에서 트랜잭션 데이터베이스가 있어야 한다는 것을 눈치챈 독자들도 있을 것이다. 그렇다면 트랜잭션 데이터베이스 생성 과정부터 알아보겠다. 그전에 본 프로젝트에서 구현한 데이터 마이닝 시스템의 전반적인 시스템 구성에 대해 간략히 소개하고 알고리즘 구현으로 들어가겠다. 우리가 구현한 데이터 마이닝 시스템은 소켓을 이용한 클라이언트/서버 환경으로 되어 있고 서버에서는 생성된 트랜잭션 데이터베이스를 바탕으로 연관 규칙, 의사결정트리, 신경망 알고리즘을 이용해 데이터 마이닝 결과를 데이터 베이스에 저장하게 된다.
연관 규칙의 경우 지역, 성별, 나이, 보험회사 종류, 사고 종류, 자동차 종류의 아이템셋으로 빈발 1-항목 집합, 빈발 2-항목 집합, 빈발 3-항목 집합을 구하고 지지도와 신뢰도를 계산해 데이터베이스에 저장하게 된다. 클라이언트에서 최소 지지도와 최소 신뢰도를 명시해 서버로 요청하면 명시된 지지도와 신뢰도를 만족하는 아이템셋을 결과로 클라이언트에 전송하는 루틴을 가지고 있다. 데이터 웨어하우스, 트랜잭션 데이터베이스, 그리고 마이닝 알고리즘을 수행한 후 결과를 저장하는 데이터베이스 모두 MS-SQL 7.0을 사용했고 비주얼 C++ 6.0을 사용해 클라이언트와 서버를 프로그램했다.
트랜잭션 데이터베이스
그러면 트랜잭션 데이터베이스 구현에 대해 알아보자. 연관 규칙에 사용할 트랜잭션 데이터베이스는 다차원 모델링을 통해 작성된 데이터 웨어하우스를 이용했으며 다차원 모델링 및 데이터 웨어하우스에 관련된 내용은 지난 시간에 언급했으므로 생략하겠다. 구축돼 있는 데이터 웨어하우스로부터 사고 큐브를 대상으로 트랜잭션 데이터베이스를 생성했으며 사고 관련 큐브의 각각의 차원(Dimension)을 연관 규칙을 적용할 아이템셋으로 사용했고 사고 큐브의 차원은 나이, 보험료 지불방법, 지역, 성별, 가입 보험회사명, 사고 유형으로 이뤄져 있다. 다음은 본 프로젝트에서 자동차 보험 회사의 자동차 사고와 관련된 데이터베이스에서 자동차 사고와 관련된 트랜잭션 데이터베이스를 생성하는 코드의 일부분이다.
void CSetTranView::MyCompute()
{
int count = 1;
int temp = 1;
m_pDWSet->MoveFirst();
m_pDW2Set->MoveFirst();
while(!m_pDWSet->IsEOF())
{
m_pTranSet->AddNew();
m_pTranSet->m_TID = count++;
temp = count;
while(!m_pDW2Set->IsEOF())
{
if(m_pDW2Set->m_Customer_ID == m_pDWSet->m_AFact_Customer_ID)
{
m_pTranSet->m_region = m_pDW2Set->m_Customer_Region_ID;
m_pTranSet->m_sex = m_pDW2Set->m_Customer_Gender_ID;
m_pTranSet->m_age = m_pDW2Set->m_Customer_Age_ID;
break;
}
m_pDW2Set->MoveNext();
if(m_pDW2Set->IsEOF())
m_pDW2Set->MoveFirst();
}
m_pTranSet->m_insuredCompany = m_pDWSet->m_AFact_Insure_ID;
m_pTranSet->m_accident = m_pDWSet->m_AFact_Accident_ID;
m_pTranSet->m_carKind = m_pDWSet->m_AFact_CarKind_ID;
m_pTranSet->m_time = m_pDWSet->m_AFcat_Time;
m_pTranSet->Update();
m_Progress.SetPos(count);
SetDlgItemInt(IDC_NUM, count);
}
}
m_pDWSet과 m_pDW2Set은 데이터 웨어하우스에 연결된 레코드셋이고 데이터 웨어하우스를 스캔하면서 트랜잭션 데이터베이스를 생성하게 된다.
빈발 항목 집합 테이블
다음은 빈발 항목 집합을 생성하고 지지도와 신뢰도를 계산하는 코드 중에서 발췌한 부분이다. 사실 앞에서 언급한 빈발 항목 집합의 개념을 엄밀히 적용시킨다면 빈발 항목 집합을 생성하는 부분이 아닐 수도 있으나, 최소 지지도와 최소 신뢰도가 아직 정해지지 않은 상태이고 최소 지지도와 최소 신뢰도는 클라이언트에서 명세하기 때문에 그전에 모든 조합이 가능한 모든 항목 집합들을 빈발 항목 집합으로 간주하고 이들에 대한 지지도와 신뢰도를 계산해 서버의 데이터베이스에 저장해야만 했다. 출력 인터페이스는 어떤 방식의 출력을 선택하느냐에 따라 코드가 달라지므로 생략했으며, 참고로 본 프로젝트에서는 리스트 컨트롤을 이용해 최소 지지도와 최소 신뢰도를 만족하는 빈발 항목들을 출력하도록 했다.
void CMiningServerView::OnMining()
{
... 생략 ...
/////// 라지테이블 1 ////////////////
//^^;
m_pTranSet->MoveFirst();
while(!m_pTranSet->IsEOF())
{
// 라지테이블1 카운트...
regionCount[m_pTranSet->m_region-1]++;
sexCount[m_pTranSet->m_sex-1]++;
ageCount[m_pTranSet->m_age-2]++;
... 중략 ...
// 라지테이블 2 카운트...
regionSexCount[m_pTranSet->m_region-1][m_pTranSet->m_sex-1]++;
...
sexAgeCount[m_pTranSet->m_sex-1][m_pTranSet->m_age-2]++;
...
ageCompanyCount[m_pTranSet->m_age-2][m_pTranSet->
m_insuredCompany-1]++;
...
companyAccidentCount[m_pTranSet->m_insuredCompany-1]
[m_pTranSet->m_accident-1]++;
...
accidentCarKindCount[m_pTranSet->m_accident-1][m_pTranSet->m_carKind-1]++;
...
// 라지테이블 3 카운트...
regionSexAgeCount[m_pTranSet->m_region-1][m_pTranSet->m_sex-1]
[m_pTranSet->m_age-2]++;
...
sexAgeCompanyCount[m_pTranSet->m_sex-1][m_pTranSet->m_age-2]
[m_pTranSet->m_insuredCompany-1]++;
...
ageCompanyAccidentCount[m_pTranSet->m_age-2][m_pTranSet->
m_insuredCompany-1][m_pTranSet->m_accident-1]++;
...
companyAccidentCarKindCount[m_pTranSet->m_insuredCompany-1]
[m_pTranSet->m_accident-1][m_pTranSet->m_carKind-1]++;
m_pTranSet->MoveNext();
}
//// Large Table 1 작성...////
for(i = 0; i < REGION; i++)
CreateLargeTable(regionCount[ i ], &cnt, itemNum, i);
m_pStatus->SetPaneText(0, "L1:지역 Done!");
...
///// 라지테이블 2 작성///
for(i = 0; i < REGION; i++)
for(j = 0; j < SEX; j++)
CreateLargeTable(regionSexCount[ i ][ j ], &cnt, itemNum, i, j);
...
////// LARGE TABLE 3!!!!!! //////
for(i = 0; i < REGION; i++)
for(j = 0; j < SEX; j++)
for(k = 0; k < AGE; k++)
CreateLargeTable(regionSexAgeCount[ i ][j][k], &cnt, itemNum, i, j, k);
...
}
void CMiningServerView::CreateLargeTable(int allCount, int *cnt, itemCount item, int i)
{
CString str1, str2;
float allSupport;
// 지지도 조사...
allSupport = ((float)allCount / (float)m_TotalCount)*100;
// 지지도 비교...
if(allSupport >= m_nGetSupportValue)
출력루틴(생략)...
}
void CMiningServerView::CreateLargeTable(int allCount, int *cnt,
itemCount item, int i, int j)
{
CString str1, str2, str3, str4;
float allSupport;
int firstCount;
float allConfidence;
// 지지도 계산 ...
allSupport=((float)allCount / (float)m_TotalCount)*100;
// 신뢰도 계산..
// 각 항목에 대해 카운트
... 생략 ...
allConfidence = (allCount / (float)firstCount) * 100;
// 지지도와 신뢰도 비교...
if(allSupport >= m_nGetSupportValue && allConfidence >= m_nGetConfidenceValue)
출력루틴(생략)
}
void CMiningServerView::CreateLargeTable(int allCount, int *cnt,
itemCount item, int i, int j, int k)
{
CString str1, str2, str3, str4, str5;
float allSupport;
int firstCount;
float allConfidence;
// 지지도 계산...
allSupport=((float)allCount / (float)m_TotalCount)*100;
// 신뢰도 계산...
// 각 항목에 대해 카운트
... 생략 ...
allConfidence = (allCount / (float)firstCount) * 100;
// 지지도와 신뢰도 비교...
if(allSupport >= m_nGetSupportValue && allConfidence >= m_nGetConfidenceValue)
출력 루틴(생략)
}
빈발-1 항목을 작성하기 위해 자동차 사고 큐브에서 선택한 지역, 성별, 나이, 보험회사명, 자동차 사고 종류, 자동차 종류를 아이템셋으로 한 트랜잭션 테이블을 스캔하면서 각 아이템의 출현 회수를 L (빈발-1 항목)에 저장하게 된다. 이렇게 해서 작성된 빈발-1 항목의 아이템들을 조인해 빈발-2 항목을 작성하게 되는데, 앞서 언급했던 것처럼 최소 지지도와 최소 신뢰도가 결정되지 않은 상태이기 때문에 모든 경우의 후보 항목에 대해 계산했다. 이 후보 항목이 빈발 항목으로 결정되는 것은 클라이언트에서 최소 지지도와 최소 신뢰도가 명세될 때라는 것을 짐작하리라 생각한다. 빈발 항목(또는 후보 항목)의 지지도와 신뢰도는 오버로드 함수인 CreateLargeTable()에서 처리했다.
위에서 이야기했던 바와 같이 후보 항목 집합의 발생 빈도를 계산하는 것은 상당량의 프로세싱 시간과 고용량의 메모리를 요구하게 된다. 따라서 클라이언트/서버 환경에서 클라이언트에서 전송한 최소 지지도와 최소 신뢰도를 만족하는 빈발 항목 집합을 계산한다는 것은 많은 시간적인 지연을 초래하게 될 것이다. 따라서 계산된 모든 빈발 항목 집합의 지지도와 신뢰도는 데이터베이스로 저장해 클라이언트의 요구에 대해 즉각적인(?) 반응을 보이도록 시스템을 설계했다. (화면 1)과 (화면 2)는 마이닝 시스템(클라이언트) 중에서 연관 규칙을 실행한 화면의 일부분과 결과를 그래프로 출력한 화면이다.
이상으로 연관 규칙에 대해 살펴봤고 다음으로는 지난 시간에 잠시 설명했던 의사결정트리 알고리즘에 대해 알아보겠다.
의사결정트리
한 달 전의 내용을 기억하고 있는 독자가 몇 명이나 될지는 모르겠지만 알고리즘이라는 것이 아직은 '골치아픈 것'이라는 통념 때문에 읽는 순간 잊어버리는 독자도 적지 않을 것이다. 의사결정트리 알고리즘도 마찬가지일테지만 다른 골치아픈 알고리즘에 비해 이해가 힘든 알고리즘은 아니므로 기억해두는 것도 나쁘지 않을 듯 싶다. 지난 시간에는 의사결정트리는 데이터의 클러스터링(Clustering)이나 분류화(Classification)에 많이 사용되고 어떤 결과가 일어났을 때 그 결과가 일어나기 위해서 왜 그런 현상이 나타났는지를 설명하기 위해 사용된다고 말했다. 이번 시간에는 그 의사결정트리의 여러 종류의 알고리즘 중에 우리 프로젝트에 사용됐던 ID3 알고리즘에 대해 예를 들어 살펴보고 이 알고리즘이 프로젝트 상에서 어떻게 구현되었는지를 알아보겠다. 그러면 본격적으로 의사결정트리 - ID3에 대해 알아보자
의사결정트리, ID3 알고리즘
의사결정트리로서의 ID3는 연관 규칙에서처럼 어떤 예제로부터 대상을 끄집어낸다. 다시 말해 ID3는 어떤 한 프로퍼티에 대해 그것의 value를 테스트함으로써 대상을 분류화하는데 사용된다. 무슨 말인지 잘 모르겠다면 (표 3)을 참고하기 바란다. 앞으로 이 표를 가지고 개인의 신용 리스크에 대해 알아보도록 하겠다.
(표 3)은 개인의 신용 상태에 대한 리스크를 추정할 수 있도록 수집된 데이터이다. 여기서 신용기록(Credit History), 부채(Debt), 담보(Collateral), 개인수입(Income) 등이 프로퍼티에 해당되며, 그 프로퍼티에 대한 각각의 값들(가령 부채에 대해서는 높음, 낮음을 신용기록에서는 좋음, 나쁨, 모름 등)이 value 값이 된다. 대상은 알아내고자 하는 결과를 말하므로 여기서는 리스크가 대상값이 된다. 그러니까 ID3는 한 프로퍼티에 대해 그것이 어떤 값을 가지고 있는지에 따라 분류하고 또 다른 프로퍼티에 대해 같은 작업을 반복함으로서 궁극적으로는 그것들이 어떤 리스크 결과를 갖는지를 알아낼 수 있다. (그림 1)은 단순히 위와 같은 작업을 반복해 얻어낸 트리이다.
먼저 이 트리의 구조를 살펴보자. 여기서 루트 노드(Root Node)는 처음 가지치기가 시작되는 신용기록을 말하며, 내부 노드는 부채, 개인수입, 담보와 같은 여러 프로퍼티가 속한다. 이 프로퍼티들은 그것들이 가지고 있는 value에 의해 가지치기(branch)가 되어 있음을 알 수 있다. 또한 종단 노드(Leaf Node)는 리스크 낮음, 리스크 높음, 리스크 적당함 등의 값을 갖는, 가지의 끝에 있는 노드를 말하며 이 트리에서 보듯이 모든 종단 노드가 리스크 값을 가지고 있어야 하며 이러한 식으로 분류화 작업이 진행된다. 상식적으로 트리는 이러한 노드와 가지를 가지고 종단 노드에 도달할 때까지, 또는 구하고자 하는 대상이 완전히 분류화가 끝날 때까지 계속된다.
이번에는 신용기록이 '모름(Unknown)'인 한 가지를 따라가 보자. <표 3>에서 보듯이 신용기록과 모름(Unknown)인 것의 리스크 값은 다양하기 때문에 이 한 번의 가지치기로는 알고자 하는 결과를 얻어낼 수가 없다. 그래서 남아 있는 프로퍼티 중에 다른 하나를 선택해 또 한 번의 가지치기를 한다. 그리고 부채로 또 한 번의 가지치기를 한다. 부채가 낮을 경우 역시 리스크 값이 다양하기 때문에 이후에 또 다른 프로퍼티로 가지치기를 해야 하나 부채가 높을 경우는 '리스크 높음' 만이 나타나기 때문에 우리는 이런 경우에 신용기록이 '모름'이고 부채가 높은 경우는 '리스크 높음'일 확률이 크다고 말할 수 있다.
이 트리를 자세히 보면 우리는 이 트리에서의 가지들에서 리스트에 존재하는 모든 프로퍼티를 사용하지 않았다는 것을 알 수 있다. 다시 말해 만약 신용기록의 가치가 좋음이고 부채값이 낮음인 사람은 리스크 낮음으로 분류가 되는데 있어 담보나 개인수입 등은 무시된다는 것이다. 이러한 프로퍼티를 생략했는데도 불구하고 이 의사결정트리는 이 리스트에 있는 모든 대상을 정확하게 분류화한다.
일반적으로 어떤 샘플을 분류함에 있어 트리의 크기(Depth)는 프로퍼티들을 어떤 순서로 정렬하느냐에 따라 다양하게 나올 수 있다. (그림 2)의 의사결정트리는 또 다른 방법으로 분류화한 것이다. 여기서도 마찬가지로 리스트의 대상들을 정확히 분류화했음에도 불구하고 앞서 본 의사결정트리보다 비교적 간단하다는 것을 알 수 있을 것이다.
이 시점에서 우리는 어떤 것이 더 잘 분류화를 한 것인지에 대한 의문을 가질 수 있을 것이다. 일반적으로 ID3는 모든 대상을 포함하면서도 크기가 작고 비대칭으로 트리가 나타나게 되는 경우에 분류화가 잘된 것이라고 가정한다. 여기서도 알 수 있듯이 의사결정트리에 관건은 어떤 프로퍼티로 먼저 가지치기를 시작해야 하는가이며 이를 위해 기준이 될 수 있는 하나의 잣대를 만들어 놓았다. 앞으로는 그 잣대인 Information Gain 값을 가지고 위의 리스트를 분류화하는 과정에 대해 알아볼 것이다.
탑다운 의사결정트리
ID3는 탑다운(top-down) 형식으로 생성된다. 이 알고리즘은 각각의 노드에서 서브트리의 생성이 계속해서 반복된다. 이미 알고 있듯이 이러한 반복은 노드 값이 같은 범주의 클래스(리스크 낮음, 리스크 높음, 리스크 적당함)에 속할 때까지, 또는 노드가 종단 노드가 될 때까지 계속된다. ID3 알고리즘은 다음과 같다.
Function induce_tree(example_set, Properties(Attribute))
begin
if all entries in example_set are in the same class
then return a leaf node labeled with that class
else if Properties is empty
then return leaf node labeled with disjunction of all classes in example_set
else begin
select a property, P, to text on and make it the root of the current tree;
delete P from properties;
for each value, V, of P,
begin
create a branch of the tree labeled with V
let partition be elements of example_set with V for property P;
call induce_tree(partition, Properties), attach result to branch V
end;
end;
end
예를 들어보자. (그림 2)의 의사결정트리는 리스트로부터 앞의 알고리즘을 따라서 만든 것이다. 이 트리에서는 루트 노드로 개인수입을 선택해 반복적으로 서브트리를 만들어 가고 있다. (그림 3)은 그 과정을 설명하는 그림이며 여기서 나타난 번호는 리스트에서의 레코드 번호이다.
ID3는 Induce_tree 함수에 의해 반복적으로 계속 분할을 해 나간다. 예제 는 리스크가 모두 하나의 범주 - 리스크 높음 - 에 속하므로 ID3는 종단 노드를 생성한다. 나머지 두 가지에서는 다시 induce_tree를 호출하면서 같은 과정을 반복한다. 루트 노드 바로 아래의 자식 노드로 신용기록을 선택한다면 to k의 예제 {2, 3, 12, 14}는 (그림 4)처럼 신용기록에 따라 , , 로 분할돼 나쁨인 가지는 리스크 적당함 범주에, 좋음인 가지는 리스크 낮음 범주에 속하게 된다. 이러한 과정을 반복으로 완성된 트리가 우리가 두번째로 보았던 트리이다.
정보 이론 테스트 선택
이미 알고리즘을 통해 어떤 식으로 반복적으로 트리가 생성되는지 살펴봤으나 아직 미비하다. "어느 프로퍼티를 트리의 루트 노드에서 테스트할 것인가?"라는 의문이 아직 해결되지 않았기 때문이다. 이것의 해답이 바로 Information Gain에 있다. ID3는 정보 획득 - 어떤 프로퍼티가 타겟 분류화에 가장 적합하게 테스트되는 예제를 분리하는 정도 - 을 측정해 현재의 서브트리의 루트 노드로 어떤 것이 선택돼야 하는지를 결정한다. 보통 Information gain 값이 큰 프로퍼티를 루트 노드로 선택한다. 참고로 Information 이론은 현재 컴퓨터 공학이나 텔레커뮤니케이션(Telecommunication), 데이터 압축 알고리즘 등에서 광범위하게 사용되고 있다. ID3에서 Information 이론은 트레이닝 예제의 분류 작업에서 Information gain이 큰 값을 선택해 테스트하기 위해 이용된다.
다음은 앞에서의 리스트를 가지고 Information gain을 구해보겠다. Information gain 값을 구하기 위해서는 먼저 Entropy(E(p))와 Information value(I(P)) 값이 필요하기 때문에 먼저 정보 값(Information Value)을 구한다.
정보 값(Information value) : I(P) = ((-P(mi) Log2 (P(mi)))
(알아내고자 하는 대상의 프로퍼티를 P로 잡는다.)
P(리스크 높음) = 6/14
P(리스크 적당함) = 3/14
P(리스크 낮음) = 5/14
여기서 말하는 P는 프로퍼티에 대한 확률이다. 가령 리스크 낮음의 확률은 전체 14개의 레코드 중에서 5 레코드에 존재하므로 리스크 낮음의 확률은 5/14이다.
I(C) = - (6/16) Log2 (6/14) - (3/14) Log2 (3/14) - (5/14) Log2 (5/14)
= - (4/16) * (-1.222) - (3/14) * (-2.222) - (5/14) * (-1.485)
= 1.531 bits
한 노드에서 테스트가 될 또 다른 프로퍼티를 C로 가정하고 현행의 서브트리의 루트 노드가 n개의 값을 가진 프로퍼티 P라고 한다면, C는 {C , C , ... C }로 나눠진다. 이럴 경우 Information gain을 구하기 위해서는 엔트로피(Entropy) 값이 필요한데 이것은 다음과 같이 구한다.
엔트로피(Entropy) : E(P) = Σ(|C |/|C|) * I(C )
또한 Information Value와 엔트로피가 구해지면 다음의 식으로 Information Gain을 구할 수 있다.
gain(P) = I(C) - E(P)
리스트의 예로 <그림 1>에서처럼 개인수입을 루트 노드로 테스트한다면 파티션은 C = {1, 4, 7, 11}, C = {2, 3, 12, 14}, C = {5, 6, 8, 9, 10, 13}이 된다. 여기서의 Information gain은 다음과 같이 구할 수 있다.
E(income) = (4/14) * I (C ) + (4/14) * I (C ) + (6/14) * I (C )
= (4/14) * 0.0 + (4/14) * 1.0 + (6/14) * 0.650
= 0.564비트
따라서 gain(income) = I(C) - E(income)
= 1.531 - 0.564 = 0.967비트
마찬가지 방법으로 다른 파티션(C , C )의 gain 값을 구하면 다음과 같다.
gain(credit history) = 0.266
gain(debt) = 0.581
gain(collateral) = 0.756
여기에서 알 수 있듯이 개인수입(Income) 항목의 information gain 값이 가장 크기 때문에 ID3는 이 트리의 루트 노드로 income 프로퍼티를 선택할 것이다. 이 알고리즘은 트리가 끝날 때까지 각각의 서브트리에 같은 방법으로 계속 적용된다. 여태까지 우리는 의사결정트리를 생성하는 방법에 대해 알아봤다. 독자들도 느끼겠지만 그렇게 머리를 복잡하게 할만큼 알고리즘 자체가 난해한 것은 아니다. 그러나 다른 마이닝 알고리즘과 마찬가지로 ID3 알고리즘 역시 모든 예제의 분류화나 예측에 있어서 항상 정확하지는 않다. 어떠한 경우에 어떤 알고리즘이 더 효율적인지를 알아내서 적절하게 적용시킨다는 것이 어렵고 그 결과가 현실세계에 있어 얼마나 정확히 예측하는 지를 판단하기가 힘이 들기 때문에 마이닝이 어렵다는 생각을 다시 한 번 해본다. 이것을 마지막으로 알고리즘의 배경 지식은 마치고 이제부터는 우리 프로젝트에서 이러한 알고리즘을 어떻게 적용시켰는가에 대해 살펴보도록 할 것이다.
알고리즘의 구현
고객의 행동에 관한 데이터를 가지고 있는 데이터베이스가 있다고 하자. 이 데이터를 분류하거나 예측하는 경우 그 결과치를 비교 분석해 본다면 우리는 분류 작업과 예측 작업이 매우 긴밀하게 연결돼 있다는 것을 알 수 있을 것이다. 다시 말해 어떤 고객이 어떠한 유형의 행동을 보일 것이라는 것을 예측하려는 것은 사실 그 고객이 특정한 유형의 고객 그룹에 속하여 이와 같은 특정한 행동을 보일 것이라는 가정을 의미하고 있다. 같은 방법으로 우리 프로젝트에서 사고를 내는 사람들이 속한 그룹의 특정한 행동유형을 찾아보고자 의사결정트리를 구현했고 그 중에서 ID3 알고리즘을 사용했다.
알고리즘을 구현하는데 있어 크게 두 부분으로 나눠 생각해 봤다. 한 부분은 엔트로피(Entropy)와 information gain을 구하는 부분이고 나머지 한 부분은 그 gain 값을 근거로 트리를 만들어가면서 퍼센티지를 구하고 현재 노드가 종단 노드(Leaf Node)인지를 확인해 가며 저장하는 부분이다. 이렇게 두 부분으로 나누어 생각하는 이유는 프로젝트에서 모두 10개 정도의 트리가 만들어져야 하기 때문에 먼저 각각의 엔트로피 계산 값을 데이터베이스에 저장해 놓고 그 값을 꺼내서 언제든지 트리를 다시 만들어 낼 수 있게끔 하기 위해서이다.
이 프로젝트에서 또 하나의 단순화는 사고의 fact 테이블에 있는 모든 속성(Attribute)들을 프로퍼티로 취하지 않고 임의로 5개의 속성만 선택했다는 것이다. 이는 너무 많은 단계의 분류화로 인해 어떠한 결과값도 얻지 못하는 경우가 생길 수 있다는 판단으로 여기서는 그래도 사고와 관련해 그 연관성을 얻어내고 싶은 속성에 한해 트리를 생성하기로 했다. 성별(Sex), 나이(Age), 차종(CarKind), 지역(Region), 시간(Time)이 그것들이다. 우선 전체 알고리즘 구현 과정을 (그림 5)와 같이 도식화했다. 이 순서를 따라가며 그 과정을 살펴볼 것이다.
주제의 선정
사고 부분에 있어 나올 수 있는 주제는 다양하다. 사고의 원인을 알아볼 수도 있고 어느 시간대에, 또는 어느 계절에 사고가 나는지에 대해서도 알아볼 수 있다. 그러나 우리 프로젝트는 자동차 보험회사가 고객에 대해 보험률을 책정할 때 사고를 많이 내거나 큰 사고를 냈었던 사람들에 대해 차별적인 보험률을 적용시키기 위해 과거의 사고자료를 가지고 예측할 수 있어야 하기 때문에 사고 유형별로 사고를 냈던 사람들에 대한 유형을 살펴보기로 하고 그에 따라 알고리즘을 구현했다.
좀더 자세히 말한다면 10가지 사고유형(무면허, 음주운전, 뺑소니, 신호위반, 과속 등) 중에서 특정사고를 낸 사람들은 어떠한 특성을 갖는 사람인지, 가령 나이는 얼마이고, 성별은 무엇이고, 어떤 종류의 차를 가진 사람이며, 지역적인 특징이 있는지, 또는 특정 사고를 낸 사람들 사이에 연관성이 있는지 등을 알아보기로 했다. 과거의 사고 경력이나 보상받은 보험료 등에 대한 자료가 더 있다면 좀더 의미있는 결과를 얻을 수 있을 것이다.
결과물 선정
다른 알고리즘도 마찬가지일테지만 ID3는 어떤 결과물(Output)을 갖는지에 따라 트리의 크기가 달라질 수 있고 복잡해질 수도 간단해질 수도 있다. 우선은 주제가 사고유형에 따른 유형별 분류이기 때문에 결과물은 크게 사고유형으로 정할 수 있다. 처음에는 10개의 사고유형별로 분류해 나가려고 했는데 그렇게 되면 트리를 생성하는데 있어 그 과정이 복잡해지고 나오는 결과값들이 과연 의미가 있는 값들이 나올지에 대한 의문에 좀더 단순하게 생각해 보기로 했다.
결국 사고가 났는지 안났는지 Yes인지 No인지로 분류하기로 했으며 10개의 사고유형을 구분하기 위해 각 사고 유형별로 따로 트리를 생성했다. 예를 들어 루트 노드가 무면허일 때 그 사고가 났으면 Yes, 안났으면 No, 루트 노드가 뺑소니일 때 그 사고가 났으면 Yes, 아니면 No인 식으로 했다.
엔트로피 및 Information Gain 계산
우선은 구현 과정을 먼저 살펴보자.
#define ACCIDENT 10
#define ATTRNUM 5
CString attr[ATTRNUM] = {"Sex", "Age", "Region", "CarKind", "Time"};
int m_valNum[ATTRNUM] = {2, 6, 16, 3, 4};
void CMinID3View::Entropy(double Entro_Acc){
double entropy[] = {0, 0, 0, 0, 0}; // 각각의 속성의 엔트로피를 저장할 배열
double eSex, eAge, eRegion, eCarKind, eTime;
int NUM, valNum;
// 엔트로피 구하기
for(int j=0; j {
for(int i=0; i {
NUM = Count[j][ i ];
valNum = AttCount[j][ i ];
if(NUM==0||valNum==0) entropy[j] += 0;
else
entropy[j] += (double)NUM/TOTALNUM
*(-(((double)valNum/NUM)*(log10((double)valNum/NUM))/(log10(2.)))
-(((double)(NUM - valNum)/NUM)
*(log10((double)(NUM - valNum)/NUM))/(log10(2.))));
}
}
// Information Gain 구하기
eSex = Entro_Acc - entropy[0];
eAge = Entro_Acc - entropy[1];
eRegion = Entro_Acc - entropy[2];
eCarKind = Entro_Acc - entropy[3];
eTime = Entro_Acc - entropy[4];
}
첫째 단락에서 몇 가지 정의를 내린 것을 볼 수 있다. 첫째 줄은 사고유형의 개수로 10개의 사고유형별 트리를 만들기 위해 루프를 돌리거나 인덱스를 주기 위한 정의(Define)이고 두 번째부터는 속성에 관련된 정의이다. 두 번째는 속성의 개수이고 셋째 줄은 속성에 인덱스를 지정하는 부분으로 앞으로의 모든 구현은 이 인덱스에 기준을 두어 돌아가게 구현했다. 마지막 줄은 각각의 속성들의 value의 개수이다. 예를 들어 첫째 인덱스의 성별은 남과 여의 두 개 value를 갖는다. 엔트로피는 앞서 이론에서 말한 것과 같은 방법으로 구현했다. 예를 들어 현재의 사고유형이 신호위반이라고 한다면 신호위반에 대한 엔트로피는 다음과 같다.
E = - P Log P - P Log P
두 번째로 각각의 속성별 엔트로피를 구한다면(속성이 성별이라면) 다음과 같다.
Function Entropy(Attribute : sex)
Begin
현재의 사고유형에 대한 각각의 속성별별 엔트로피
E = - P Log P -P Log P
그 다음으로는 먼저 구한 엔트로피를 기준으로 Information Gain을 구한다. Information Gain은 예제를 속성으로 나눌 때 엔트로피가 줄어드는 양을 나타내는 것이며 이 값이 어떤 것이 루트 노드로 적합한지를 정해준다. Information Gain은 다음의 식으로 구할 수 있다.
Gain(S, A) = Entropy(S) - Σ(|S |/|S|) * Entropy(S )
쉽게 설명한다면 위에서 구한 두 개의 엔트로피의 차가 구하고자 하는 Gain 값이 된다.
Gain(Sex) = E(신호위반) - E(사고유형이 신호위반이면서 속성이 sex인 것)
여기서 Entro_Acc는 먼저 구해놓은 사고에 관한 전체 엔트로피이다.
정렬
다음과 같이 선언된 order_gain 배열에 위에서 구해진 Information Gain을 근거로 하여 큰 순서대로 값을 채워 넣는다. 그렇게 하기 위해서 각각의 gain을 큰 순서대로 정렬(sorting)하고 gain 값 대신 그 순서대로 속성의 인덱스를 배열에 넣는다. 여기에서 정렬 알고리즘은 select_sort 알고리즘을 사용했다.
int order_gain[ACCIDENT][ATTRNUM];
트리의 생성과 데이터베이스 저장
트리를 생성하는데 있어 중요한 부분은 어떤 데이터 구조를 사용해 어떤 자료구조를 가지고 트리를 생성하느냐인 것 같다. 데이터 구조는 다음과 같이 구현했다.
struct Tree_Node{
tree_ptr link[MAXVALNUM];
int depth; // 속성 인덱스
int percent; // 전체중에 yes일 확률
short int result; // 0이면 no, 1이면 yes
short int flag_leaf; // leaf이면 0, 아니면 1
int val_index[ATTRNUM]; // 속성의 값을 나타내는 인덱스
}
typedef struct Tree_Node* tree_ptr;
여기에서 link[MAXVALNUM]는 링크가 될 노드들의 포인터형이고 Depth는 트리의 크기를 말하며 결과는 그 노드가 Yes 값을 갖는지, 아니면 No 값을 갖는지를 저장하는 int 형의 변수이고 flag_leaf는 종단 노드인지 아닌지를 나타낸다. 마지막으로 val_index[ATTRNUM]는 자신과 연결된 부모 노드들의 인덱스를 차례대로 저장할 배열이다.
tree_ptr CMinID3View::Build_Tree( int val, tree_ptr pRootNode)
{
tree_ptr pNewNode;
pNewNode = (tree_ptr)malloc(sizeof(Tree_Node));
pNewNode->depth = Depth(pRootNode);
for(int i = 0; i pNewNode->val_index[ i ] = pRootNode->val_index[ i ];
pNewNode->val_index[pNewNode->depth] = val;
pNewNode->percent = Percent(pNewNode);
pNewNode->flag_leaf= IsLeaf(pNewNode, pRootNode);
{
CString str;
if(!m_acc4Set.IsOpen()) m_acc4Set.Open();
m_acc4Set.AddNew();
m_acc4Set.m_Depth = pNewNode->depth;
str.Format("%d", pNewNode->depth);
m_Flexgrid.SetTextMatrix(ROWS, 1, str);
m_acc4Set.m_FlagLeaf = pNewNode->flag_leaf;
str.Format("%d", pNewNode->flag_leaf);
m_Flexgrid.SetTextMatrix(ROWS, 2, str);
m_acc4Set.m_Accpercent = pNewNode->percent;
str.Format("%d", pNewNode->percent);
m_Flexgrid.SetTextMatrix(ROWS, 3, str);
m_acc4Set.m_Result = pNewNode->result;
str.Format("%d", pNewNode->result);
m_Flexgrid.SetTextMatrix(ROWS, 4, str);
m_acc4Set.m_VarIndex = pNewNode->val_index[pNewNode->depth];
str.Format("%d", pNewNode->val_index[pNewNode->depth]);
m_Flexgrid.SetTextMatrix(ROWS, 5, str);
if(pNewNode->depth==0)
{
m_acc4Set.m_Link = -1;
str.Format("%d", -1);
m_Flexgrid.SetTextMatrix(ROWS, 6, str);
m_acc4Set.m_Link2 = -1;
m_Flexgrid.SetTextMatrix(ROWS, 7, str);
m_acc4Set.m_Link3=-1;
m_Flexgrid.SetTextMatrix(ROWS, 8, str);
m_acc4Set.m_Link4 = -1;
m_Flexgrid.SetTextMatrix(ROWS, 9, str);
}
else if(pNewNode->depth==1)
{
m_acc4Set.m_Link = pNewNode->val_index[pNewNode->depth-1];
str.Format("%d", pNewNode->val_index[pNewNode->depth-1]);
m_Flexgrid.SetTextMatrix(ROWS, 6, str);
m_acc4Set.m_Link2 = -1;
str.Format("%d", -1);
m_Flexgrid.SetTextMatrix(ROWS, 7, str);
m_acc4Set.m_Link3 = -1;
m_Flexgrid.SetTextMatrix(ROWS, 8, str);
m_acc4Set.m_Link4 = -1;
m_Flexgrid.SetTextMatrix(ROWS, 9, str);
}
else if(pNewNode->depth==2)
{
m_acc4Set.m_Link = pNewNode->val_index[pNewNode->depth-1];
str.Format("%d", pNewNode->val_index[pNewNode->depth-1]);
m_Flexgrid.SetTextMatrix(ROWS, 6, str);
m_acc4Set.m_Link2 = pNewNode->val_index[pNewNode->depth-2];
str.Format("%d", pNewNode->val_index[pNewNode->depth-2]);
m_Flexgrid.SetTextMatrix(ROWS, 7, str);
m_acc4Set.m_Link3 = -1;
str.Format("%d", -1);
m_Flexgrid.SetTextMatrix(ROWS, 8, str);
m_acc4Set.m_Link4 = -1;
m_Flexgrid.SetTextMatrix(ROWS, 9, str);
}
else if(pNewNode->depth == 3)
{
m_acc4Set.m_Link = pNewNode->val_index[pNewNode->depth-1];
str.Format("%d", pNewNode->val_index[pNewNode->depth-1]);
m_Flexgrid.SetTextMatrix(ROWS, 6, str);
m_acc4Set.m_Link2 = pNewNode->val_index[pNewNode->depth-2];
str.Format("%d", pNewNode->val_index[pNewNode->depth-2]);
m_Flexgrid.SetTextMatrix(ROWS, 7, str);
m_acc4Set.m_Link3 = pNewNode->val_index[pNewNode->depth-3];
str.Format("%d", pNewNode->val_index[pNewNode->depth-3]);
m_Flexgrid.SetTextMatrix(ROWS, 8, str);
m_acc4Set.m_Link4 = -1;
m_Flexgrid.SetTextMatrix(ROWS, 9, str);
}
else
{
m_acc4Set.m_Link = pNewNode->val_index[pNewNode->depth-1];
str.Format("%d", pNewNode->val_index[pNewNode->depth-1]);
m_Flexgrid.SetTextMatrix(ROWS, 6, str);
m_acc4Set.m_Link2 = pNewNode->val_index[pNewNode->depth-2];
str.Format("%d", pNewNode->val_index[pNewNode->depth-2]);
m_Flexgrid.SetTextMatrix(ROWS, 7, str);
m_acc4Set.m_Link3 = pNewNode->val_index[pNewNode->depth-3];
str.Format("%d", pNewNode->val_index[pNewNode->depth-3]);
m_Flexgrid.SetTextMatrix(ROWS, 8, str);
m_acc4Set.m_Link4 = pNewNode->val_index[pNewNode->depth-4];
str.Format("%d", pNewNode->val_index[pNewNode->depth-4]);
m_Flexgrid.SetTextMatrix(ROWS, 9, str);
}
m_acc4Set.Update();
ROWS++;
m_ctrlProgress.SetPos(ROWS);
}
if(pNewNode->flag_leaf != 0)
{
if(pNewNode->depth {
for(int j=0; jlink[j] = 0;
int loop =
((CMinID3App*)AfxGetApp())->order_gain[0][pNewNode->depth+1];
for(int i=0; i {
pNewNode->link[ i ] = Build_Tree(i, pNewNode);
free(pNewNode->link[ i ]);
}
}
}
return pNewNode;
}
크기
트리의 크기(Depth)를 말하며 인자로 tree_ptr을 받는다.
FUNCTION Depth(tree_ptr pOldNode) RETURN int
BEGIN
IF OldNode의 크기가 ATTRNUM보다 작다.
THEN OldNode의 depth + 1 을 리턴
END IF
END
퍼센트
신호위반 사고를 낸 사람의 총 수와 어떤 크기에서 신호위반을 낸 사람만의 수를 구해 그 값으로 퍼센트를 구한다.
Value와 Leaf
현재 노드(Current Node)가 종단 노드인지 아닌지를 나타내며 만약 종단 노드이면 그때의 분류 유형(사고가 났는지 안났는지, Yes인지 No인지)을 value에 나타낸다. 가령 어떤 depth에서 사고를 낸 사람과 신호위반을 낸 사람의 수가 같거나 퍼센트 값이 100과 같으면 종단 노드가 되고 결과는 no가 된다. 또 다른 경우 어떤 depth에서 사고를 낸 사람과 신호위반을 낸 사람의 수가 0이거나 퍼센트 값이 0이면 그 노드는 종단 노드가 되고 결과값이 Yes가 된다. 여기에서 return 값은 퍼센트를 구해서 너무 작은 값들은(소수점 이하의 값들) 무시하고 int형으로 넘겨 받는다.
링크
클라이언트 애플리케이션에서 트리를 생성하는 부분에 있어서 Parent Item을 제대로 찾기 위해서 옛날 노드(Old Node)들의 인덱스를 저장한다. 여기에서의 인덱스는 속성들의 value들의 인덱스이며 속성의 인덱스는 노드들의 depth로 찾아간다.
백프로퍼게이션 알고리즘
이번 시간에 설명된 연관 규칙 알고리즘과 의사결정트리 알고리즘의 배경 지식과 본 프로젝트에서 구현한 내용이 마이닝 시스템에 관심이 있고 한 번쯤 구현해 보고 싶어하는 독자에게 조금이나 보탬이 됐으면 한다. 다음 시간에는 우리가 구현한 마이닝 시스템에서 핵심적인 부분으로 자동차 사고와 관련해 보험료를 예측하는 예측 시스템을 신경망 알고리즘의 하나인 백프로파게이션 알고리즘으로 구현한 내용과 FX 차트 컨트롤(Chart Control)을 이용해 데이터 마이닝의 가시화 기법을 어떻게 구현했는지 살펴보도록 하겠다.
http://www.zdnet.co.kr/develop/backend/db/article.jsp?id=566&page=2&forum=0
|
