KIPS Tr. Software and Data Eng. Vol.2, No.12 pp.855~864 pissn: 2287-5905 판단트리분류를위한 SQL 기초기능의구현에관한연구 855 http://dx.doi.org/10.3745/ktsde.2013.2.12.855 A Study on the Implementation of SQL Primitives for Decision Tree Classification An Hyoung Geun Koh Jae Jin ABSTRACT Decision tree classification is one of the important problems in data mining fields and data minings have been important tasks in the fields of large database technologies. Therefore the coupling efforts of data mining systems and database systems have led the developments of database primitives supporting data mining functions such as decision tree classification. These primitives consist of the special database operations which support the SQL implementation of decision tree classification algorithms. These primitives have become the consisting modules of database systems for the implementations of the specific algorithms. There are two aspects in the developments of database primitives which support the data mining functions. The first is the identification of database common primitives which support data mining functions by analysis. The other is the provision of the extended mechanism for the implementations of these primitives as an interface of database systems. In data mining, some primitives want be stored in DBMS is one of the difficult problems. In this paper, to solve of the problem, we describe the database primitives which construct and apply the optimized decision tree classifiers. Then we identify the useful operations for various classification algorithms and discuss the implementations of these primitives on the commercial DBMS. We implement these primitives on the commercial DBMS and present experimental results demonstrating the performance comparisons. Keywords : Data Mining, Primitive, Decision Tree, Classification 판단트리분류를위한 SQL 기초기능의구현에관한연구 안형근 고재진 요 약 판단트리분류는데이터마이닝의중요한문제의하나이고, 데이터마이닝은대형데이터베이스기술의중요한과제가되고있다. 그러므로데이터베이스와데이터마이닝시스템의결합노력은판단트리분류와같은데이터마이닝기능을지원하는데이터베이스기초기능의개발로이어지고있다. 이런기초기능은분류알고리즘의 SQL 구현을지원하는특수한데이터베이스연산들로구현되며, 특정알고리즘을구현하여데이터베이스시스템의구성모듈로사용하고있다. 데이터마이닝기능을제공하는데이터베이스기초기능의개발에는두가지관점이있다. 하나는데이터마이닝기능을분석해서그런기능들을제공하는데이터베이스공통기초기능을확인하는것, 다른하나는데이터베이스시스템의인터페이스의한부분으로이런기초기능의구현을위한확장된메커니즘을제공하는것이다. 데이터마이닝에서어떤기초기능들을 DBMS에저장할것인가는어려운문제중에하나이다. 따라서본논문에서는이러한문제를해결하기위하여, 최적화된판단트리분류기를만들고데이터베이스기초기능에대해서기술한다. 판단트리분류알고리즘의유용한연산들을확인하고, 상업적 DBMS에서이러한기초기능의구현에대해서기술하고, 성능비교를위한실험결과를제시한다. 키워드 : 데이터마이닝, 기초기능, 판단트리, 분류 1. 서론 1) 1. 서론 이논문은 2010 년울산대학교연구비에의하여연구되었음. 정회원 : 울산대학교 LINC 사업단연구교수 정회원 : 울산대학교전기공학부교수논문접수 : 2013 년 5 월 28 일수정일 :1 차 2013 년 8 월 19 일, 2 차 2013 년 9 월 23 일심사완료 : 2013 년 10 월 8 일 * Corresponding Author : Koh Jae Jin(jjkoh@ulsan.ac.kr) 판단트리분류는데이터마이닝의중요한문제의하나이고, 데이터마이닝은대형데이터베이스기술에서중요한위치를차지하고있다. 데이터마이닝하기위한데이터는대부분데이터베이스시스템 ( 이하 DBMS) 에저장되고, 이 DBMS는데이터접근 (access), 필터링 (filtering), 인덱싱
856 정보처리학회논문지 / 소프트웨어및데이터공학제 2 권제 12 호 (2013. 12) (indexing) 하는구현기능들을갖고있다. 데이터마이닝의 SQL 활용기법은대용량데이터처리, 병렬화, 필터링, 집계기능등과같은 DBMS 기술을주로활용하고데이터자체뿐만아니라질의어처리결과를마이닝하는것이특징이다 [1,11]. 그러나, 처리성능이낮아조인, 그룹핑, 집계같은 SQL 연산만으로데이터마이닝기능을수행하기에는충분하지않은문제점이있어 SQL 연산의최적화를위한인덱싱기법을사용하기도하고, 또한, 효율적인구현을위해서데이터마이닝기능들이 DBMS에서연산이나접근패턴및접근경로등의지식을활용하기도한다. 이러한상황에서데이터마이닝의어떤기능들이 DBMS로저장될것인지가가장어려운문제로되고있다 [12]. 기존연구들은주로판단트리분류를이용하여데이터마이닝기능들을확인하고 DBMS의구현기능들을이용하였으며, DBMS에서는데이터마이닝기능들을지원할몇가지기술들을서술하고있다 [2, 3]. 첫째는연관규칙에대한새로운언어구성을 SQL에추가하는것, 둘째는데이터마이닝을위한 OLE DB 같은특수한 API를사용하거나사용자정의타입과메소드를사용해서데이터마이닝기능을내부적으로구현, 셋째는 DBMS가데이터마이닝에유용한특수한연산자나기초기능을제공하는것등이있다. 이모든방법들이데이터마이닝기능들에유용하지만본논문에서는상기내용에서기술한문제점해결을위하여특수한연산자나기초기능의세번째기술관점에서연구가진행되었다 [11]. 따라서, 본논문에서는판단트리분류를위한기초기능에대해서서술하고, AVC 그룹이나 CC 테이블컴퓨팅등을상업적 DBMS의 SQL 연산자로구현한다. 이과정에서최적화된판단트리구축을위한노드통계질의어들의평가는부분대응질의어를가속화하는인덱스기법들을대상으로하였다. 또한, 새로운데이터에대한유도분류모델을적용하는연산자인 prediction join( 예측조인 ) 을구현하고, 데이터마이닝을위한 SQL 기초기능에기반한추가적연산인분류측도계산등을기술한다. 본논문에서는채무불이행자를예상하기위한주제를제시하고, 과정들의이해를돕기위하여 Table 1의훈련집합 (Training Set) 과 Table 2의시험집합 (Test Set) 을예시데이터를사용한다 [4]. 채무불이행자 (defaults) 를예상하기위하여주택의소 Table 1. Training Set id hh mrg inclev defaults 1 y unm 125,000(m) n 2 n mrg 100,000(m) n 3 n unm 70,000(l) n 4 y mrg 120,000(m) n 5 n div 95,000(m) y 6 n mrg 60,000(l) n 7 y div 220,000(h) n 8 n unm 85,000(l) y 9 n mrg 75,000(l) n 10 n unm 90,000(m) y Table 2. Test Set id hh mrg inclev defaults 11 n unm 55,000(l) 12 y mrg 80,000(l) 13 y div 110,000(m) 14 n unm 95,000(m) 15 n div 67,000(l) 유여부 (hh) 의 yes(y), no(n), 결혼상태 (mrg) 의미혼 (unm), 기혼 (mrg), 이혼 (div), 연수입 (inclev) 의경우 9만불미만이면하위 (l), 9만불이상 15만불이하이면중위 (m), 15만불이상이면상위 (h) 로하여서, 수치데이터를카테고리데이터 (category data) 로변환한속성들로구성하였다. 1장서론에이어본논문은다음과같이전개된다. 2장에서판단트리분류개념과기초기능에대해서서술하고, 3 장에서판단트리기초기능의 PL/SQL 구현, 4장에서는질의성능을비교평가를하고, 5장에서결론을내린다. 2. 판단트리분류개념과기초기능 2.1 판단트리분류개념분류 (Classification) 는데이터마이닝의중요한문제의하나로서수년간연구되어왔으며, 베이시안 (Bayesian) 분류, 신경망 (neural network), 회귀트리 (regression tree), 판단트리 (decision tree) 등과같이몇개의모델이제시되었다. 그중에서판단트리분류가단순하면서이해하기쉬워가장선호하는모델이며, 판단트리를구축하는알고리즘으로는 ID3, C4.5, SPRINT, SLIQ, PUBLIC 등이있다. 대부분의판단트리알고리즘은 greedy 접근방법을사용하며 [5, 6, 12], 본알고리즘은트리성장단계 (tree-growing phase) 에서근노드의전체데이터세트를가지고시작한다. 해당데이터세트는분류기준에의해서부분집합으로나누어지며, 이런과정은각부분집합이같은클래스 (class) 에속하는멤버 (member) 들만가지거나충분히작은부분집합으로될때까지각부분집합에대해서반복적으로수행된다. 트리가지치기단계 (Tree pruning phase) 에서구축된트리는과적합 (over-fitting) 을방지하거나, 트리의정확성을높이기위해서부분적으로잘려지게된다. 트리가지치기에대한중요한접근방법의하나는 MDL(Minimum Description Length) 원칙에기반한다 [7]. 트리성장단계에서분류기준은노드파티션의샘플들을개별클래스들로가장잘분류하는속성을선택함으로써결정되며, 이속성이노드의판단속성이된다. 분류속성이 A라면판단기준은다음과같다. A가수치속성이면 A θ v(v dom(a), θ는비교연산자 ) 이고, A가카테고리속성이라면, A V(V dom(a)) 이다. 가장좋은분류점을선택하기위해서최적화된측도로 ID3과 C4.5는분류된파티션들의 information entropy를최소화하는분류점을선택하고, SLIQ와 SPRINT는분류된파티션들의 gini index를최
판단트리분류를위한 SQL 기초기능의구현에관한연구 857 소화하는분류점을선택한다. n개의레코드들을갖는데이터세트 S에대해서 information entropy(e(s)) 는 E(S) = - p i log p i (p i : class i의상대빈도수 ) 이다. 그리고데이터세트 S를부분집합 S1과 S2로나누는분류에대해서 entropy E(S1, S2) = (n1/n)e(s1) + (n2/n)e(s2)( 여기서, n1 은 S1의레코드수, n2는 S2의레코드수이다.), 데이터세트 S에대한 gini index Gini(S) = 1 - p 2 i (p i : class, i : 상대빈도수 ) 이다. 데이터세트 S의 S1과 S2로의나눔에대한분류 gini index S는다음과같이 Gini-split(S) = (n1/n)gini(s1) + (n2/n)gini(s2) 로정의한다. 한노드에서판단속성은그노드의자식노드에서는고려되지않는다. 판단트리를위한알고리즘의 treegrowing procedure는다음과같다. procedure treegrowing(dataset S) if all records in S belong to the same class return 2.2 판단트리분류기초기능 DBMS에서단일스캔으로통계테이블을만드는것은분류기초기능을위한좋은후보가된다. 분류기준을선택하는데사용하는측도들이다르기때문에필요한통계치를계산하는기초기능이다양한알고리즘들을지원할수있다. 한노드의파티션에속하는데이터들을선택하는질의어는대부분 partial-match 질의어이며조건들은다음과같다. cond 1 and cond 2 and and cond m, 여기서 cond i 는 A j θ v(θ는비교연산자, A j V, m n, n은속성의개수 ) 형태의프레디키트 (predicate) 이며, 예로 C 4 클래스에대한 partial-match 질의어는 A 1 =2 and A 3 =1로표현할수있다. 대형데이터세트의효율적인평가를위해서는알맞은접근경로를제공하는속성들의집합으로구성된인덱스가필요하다. 따라서특수한인덱스구조에기초한 partial-match 질의어를구현함으로써한노드의파티션을얻는필터링연산이분류를위한기초기능의후보가될수있고, 이를통해통계기초기능의결과를얻을수있다. foreach attribute A i Evaluate splits on attribute A i use best split found to partition S into S1 and S2 treegrowing(s1) treegrowing(s2) 판단트리구축에있어서많은시간을소비하는부분은분류점선택이다. 구축된활동노드는논리곱 (and) 분류조건을만족하는데이터의부분집합 ( 파티션, partition) 과그노드의부모노드들이구성되어야하고, 각노드의속성은분류가능한평가가이루어져야한다. 판단트리에서직접적인데이터접근은앞서서술된측도에기초한가장좋은분류점선택이필요한것은아니며, 속성과클래스의결합이일어나는파티션의레코드개수에대한통계치는필요하다. 이러한통계치정보는속성이름 (attribute name), 속성값 (attribute value), 클래스라벨 (class-label), 횟수 (count) 로구성되는단순테이블로부터얻을수있다. 구조는 CC 테이블및 AVC group(attribute-value-class) 형태로기술되며, 표현은아래와같이 SQL 질의어를통해서만들수있다 [8, 9]. select 'att1' as attname, att1 as attvalue, cl as class, count( * ) from S group by att1, cl select 'att2' as attname, att2 as attvalue, cl as class, count( * ) from S group by att2, cl. Fig. 1. Decision Tree example 판단트리에서 MDL 가지치기는트리를상향식 (bottomup) 으로탐색하면서수행되며, 만약에노드 N에기초한최소비용부트리의비용이노드 N에서직접적으로레코드들을엔코딩 (encoding) 하는비용보다같거나크면, 노드 N의자식들을가지치기한다. 부트리의비용은재귀적으로계산된다. 가지치기단계에서가장비용이많이드는연산은각노드에서레코드들의클래스들을엔코딩 (encoding) 하는비용이며, 각파티션의개별클래스들에속하는레코드들의개수에대한정보가필요하다. 분류후기술되는것은새로운데이터에대해유도된마이닝모델을적용하는예측 (prediction) 이며, 이런적용을 prediction join 연산이라한다. 새로운소스데이터 (source data) 의속성값들은유도된마이닝모델로부터제시된사례 (cases) 들과매칭 (matching) 이된다. 잎노드에대한클래스라벨배정은훈련데이터로부터얻어진통계적기대값에기초한다. 그러므로주어진사례들에대한예측된클래스는훈련데이터로부터유도된확률과같은추가적인통계치에의해서표현되어진다. 대부분의경우예측은단일값이아니고클래스들과확률을포함한다. Prediction join의구현은모델표현에크게의존한다. 예를들면, 판단트리는연관된조건-클래스와노드-간선으로표현되거나예측된클래스라벨과더불어노드에있는분류점또는속성값들의개별조합을구체화함으로써표현될
858 정보처리학회논문지 / 소프트웨어및데이터공학제 2 권제 12 호 (2013. 12) 수있다. 특정한모델표현이주어진다면 prediction join 연산자는중요한분류기초기능이될수있다. 판단트리분류를위한기초기능에는다음과같은것들이있다. (1) 데이터마이닝의전처리단계의데이터준비를하는기초기능 [10] : 만약관련이없거나중복되거나또는잡음성의데이터이거나신뢰할수없는데이터가있다면데이터마이닝은어렵게된다. 데이터전처리에는데이터필터링, 데이터정규화, 변환, 추출과선택등이포함된다. (2) AVC group and CC table generation primitives( 노드통계표작성기초기능 ) : 분류기에공통되는 CC table 등을작성한다. 판단트리알고리즘에서각노드는그노드의데이터에관련된개수통계를얻어서, 모든가능한분할들을평가해서가장좋은분할을선택한다. 각속성에대해서그속성값과클래스값의각조합에대해서발생하는튜플들의개수가필요하다. 분할판단기준은개수통계테이블로부터계산할수있으며, 4 개의칼럼 ( 속성이름, 속성값, 클래스, 개수 ) 을갖는테이블이다. 이테이블을 CC 테이블 [8] 이라하고, 한번만들어지면더이상데이터자체를참조할필요가없다. (3) partial-match query의구현에의한노드의 partition을얻기위한 filtering operation primitives. (4) gini index, information entropy 같은분류척도를계산하는기초기능 : 노드통계테이블에기초해서구현될수있다. (5) prediction join operator 기초기능. 3. 판단트리기초기능의 PL/SQL 구현 본절에서는판단트리분류기초기능에대해서서술하고, partial-match 질의어를지원하는필터링기초기능에대해서서술한다. 판단트리 T에서노드를 N i (0 i n) 라면, N 0 는근노드이다. 각노드 N i 에대해서 A i θ v 또는 A i V 이고, 프레디키트 P Ni 에연관되는분류조건과각노드에따른클래스라벨 C Ni 를배정한다. 클래스라벨은해당노드의파티션에있는가장빈번한클래스를선택함으로써결정되며, 시퀀스 N 0 N 1 N k (k n) 을 decision path라지정한다. 판단트리 T에서, i 1에대해서 N i 는 N i-1 의직접적인자식노드이다. 노드 N r 에대한 decision path는 and 연결조건으로선택되어지며, cond Nr =P N1 and P N2 and and P Nr 을의미한다. 각속성은프레디키트에서최대한번만나타난다. 따라서필터기초기능의목적을다음과같이기술한다. select 연산자 : 필터기초기능 입력 : 데이터세트 S, 노드 Nr에대한 decision path 의분류조건 cond Nr 출력 : 파티션 Sr S, Sr = б cond Nr (S) 기본적으로필터기초기능을구현하는여러가지접근방법으로 KDB 트리와같은다차원해싱 (MDH, Multi Dimensional Hashing), 그리드파일, 비트맵인덱스등이있으며, 그중본논문에서는기본인덱스또는비트맵인덱스로구현한다. Table 2의예시테이블에서속성 mrg( 결혼상태 ) 평가에따른 hh( 주택소유여부 ), inclev( 연수입 ) 에대한노드통계를산출하기위한판단트리 (Fig. 2) 와 N 2 에대한파티션 (Table 3) 및노드통계 (Table 4) 를살펴보면다음과같다. attribute name Fig. 2. Decision Tree for Node statistics Table 3. Partition for Node N2 hh inclev defaults(class) y m n n l n n l y n m y Table 4. Node statistics for Node N2 attribute value class label count hh y n 1 hh n n 1 hh n y 2 inclev m n 1 inclev l n 1 inclev l y 1 inclev m y 1 판단트리의노드와연관된파티션을필터링하는것은분류속성과분류조건을결정하는첫단계이다. 속성값과클래스라벨의각조합에대한튜플들의개수를요약하는테이블로부터 information entropy와 gini index를계산할수있다. 분류속성에의해이미사용하지않은데이터세트의모든속성들이조사된다. Fig. 2와같이부분적으로성장한트리와노드 N 2 에서스키마 R(A 1, A 2,, A n, 클래스 ) 에대해서속성 A 2,, A n 고려된다. Table 3과같이노드 N 2 에서데이터세트의나머지파티션이주어졌다고한다면, 결과테이블은 Table 4와같은정보를갖는다. Sp S에서 S p 는데이터세트 S의한파티션이라하고, 클래스 Sp를 S p 에나타나는클래스라벨의집합이라한다. A={A 1, A 2,, A m } 을속성들의집합, V=U i dom(a i ) 를값들의집합이라하고, 하나
판단트리분류를위한 SQL 기초기능의구현에관한연구 859 의레코드 r S p 에대해서 r(a i ) 를레코드 r의속성 A i 의값이라한다면, 노드통계계산기초기능은다음과같다. 개의개체를갖는다면, 데이터세트 S에대한 information entropy(i) 는다음과같다. 입력 : 파티션 S p 속성들의집합 A = {A 1, A 2,, A m } 클래스라벨을나타내는속성 ' 클래스Sp 출력 : 릴레이션 S통계 A ⅹ V ⅹ 클래스Sp ⅹ N( 횟수 ) ( 속성이름, 속성값, 클래스라벨, 횟수 ) S통계는다음사항과 equivalent( 동등 ) 하다. 속성이름 A and 속성값 V and 클래스 클 래스 Sp and 횟수 = { r r S p and ( 클래스라벨 ) = 클래스 } r(a i )= 속성값 and r 앞의테이블을만드는방법으로 SQL 질의어를사용하며, 예시로근노드에서노드통계테이블을만드는 SQL 질의어는다음과같은것이다. insert into ndsttab / * ndsttab : 근노드노드통계테이블, trtab : 훈련레코드테이블 * / (select hh, hh, defaults, count(*) from trtab group by hh, defaults) / * hh : 주택소유여부속성 * / (select mrg, mrg, defaults, count( * ) from trtab group by mrg, defaults) / * mrg : 결혼상태속성 * / (select inclev inclev, defaults, count( * ) from trtab group by inclev, defaults); / * inclev : 소득수준, default : 채무불이행클래스라벨 * / 다음은해당노드의통계를계산하는알고리즘이다. procedure nodestatscomp(query q, attribute set A, class label attribute cl) array count = initialize execute query q foreach tuple t = (a 1, a 2,, a m, cl) foreach attribute A 1,, A n A count[a i ][a i ][cl] += 1 foreach attribute A i foreach value v dom(ai) foreach class label c dom(cl) if count[a i ][v][cl]>0 produce tuple (A i, v, clb, count[a i ][v][cl]) I(p, n) = -((p/(p+n)) * log(2, (p/(p+n)))) (n/(p+n)) * log(2, (n/(p+n)))) A = a i 의조건에의해서근노드의데이터세트 S를 S 1, S 2,, S n 분할세트로나누고, 각분할세트 S i 에서속성 A 는속성값 a i 를갖는다. 분할세트 S i 가클래스 P에속하는 p i 와클래스 N에속하는 n i 를갖는다면, 분할집합 S i 에대한부트리에필요한정보는 I(p i, n i ) 가된다. 근노드에서분류속성으로 A를택했을때기대정보는다음과같은균형평균기대정보 E(A) = ((p i +n i )/(p+n)) * I(p i, n i ) 이며, 근노드에서속성 A를분류속성으로분할했을때얻어지는획득정보 gain(a) = I(p, n) E(A) 와같다. 이와같은계산결과가장큰획득정보를얻을수있는속성으로분류하는것이좋은기준이될수있다. ID3[6] 는모든후보속성에대해서 gain( 속성 ) 을계산을해서최대인것을분류속성으로정한다. 이런과정을각부트리의근노드에서도수행을해서판단트리를만든다. 판단트리가개체를분류하기위해서사용될때예상되는클래스의반환은근노드에서시작하여 y 또는 n 결과클래스개수 3개와 7개를반환하는것으로생각할수있다. Table 1의결과클래스의기대정보는다음과같다. I(y, n) = -(3/(3+7)) * log(2,3/(3+7)) (7/(3+7)) * log(2,7/(3+7)) = 0.88 어떤속성 A에의해서근노드에서분류했을때, 각부트리에서 y 또는 n 메시지를나타내는데필요한기대정보는 I(y i, n i ) 이고, 분류했을때근노드에서의기대정보 E(A) 는가중치평균으로각속성에적용하여계산하면다음과같다. E(mrg) = 0.4 * (-(0/(0+4) * log(2,0)) - 1 * log(2,1)) + 0.4 * (-0.5 * log(2,0.5) - 0.5 * log(2,0.5)) + 0.2 * (-0.5 * log(2,0.5) - 0.5 * log(2,0.5)) = 0.6 E(hh) = 0.3 * (-1 * log(2,1)) + 0.7 * (-(3/7) * log (2,(3/7)) - (4/7) * log(2,(4/7))) = 0.69 E(inclev) = 0.5 * (-(2/5) * log(2,(2/5)) - (3/5) * log (2,(3/5))) + 0.4(-(1/4) * log(2,(1/4)) - (3/4) * log (2,(3/4))) + 0.1 * (-1 * log(2,1)) = 0.8 따라서속성 A에의해서분류했을때얻어지는획득정보 gain(a) 을각속성에적용하여계산하면다음과같다. 다음은분류속성을결정하기위한측도로활용되는기대정보 information entropy 계산식을기술한다. 데이터세트 S가클래스 P에속하는 p개의개체와클래스 N에속하는 n gain(mrg)=i(y,n) E(mrg)=0.88 0.6 = 0.28 gain(hh) = I(y,n) E(hh) = 0.88 0.69 = 0.19 gain(inclev) = I(y,n) E(inclev) = 0.88 0.8= 0.08
860 정보처리학회논문지 / 소프트웨어및데이터공학제 2 권제 12 호 (2013. 12) 위결과, 근노드에서각속성에대한정보획득을계산했을때 mrg 속성이가장정보획득이컸다. 따라서근노드에서분류속성으로 mrg를선택하고분류했을때, 세개의부트리가생성된다. mrg=mrg 인프레디키트에의해서분류된부트리는클래스라벨이전부 n 이기때문에더이상분류가불필요하다. mrg=unm 인프레디키트에의해서분류된부트리에서의각종기대정보는다음과같다. I(y,n)= -0.5 * log(2,0.5)-0.5 * log(2,0.5)=1.0 E(hh)= (1/4) * (-log(2,1))+(3/4) * (-(2/3) * log(2,(2/3))- (1/3) * log(2,(1/3)))=0.69 E(inclev)=0.5 * (-0.5 * log(2,0.5)-0.5 * log(2,0.5))+0.5 * (-0.5 * log(2,0.5)-0.5 * log(2,0.5))=1 미혼 (unm) 노드에서각속성별정보획득을계산하면아래와같은결과를얻을수있다. gain(hh)=0.31, gain(inclev)=0.0 이결과, 미혼노드에서는 hh 속성의값이크기때문에선택하고분류한다. 다음은이혼 (div) 노드에서기대정보를계산한다. I(y,n) = -0.5 * log(2,0.5)-0.5 * log(2,0.5)=1 E(hh) = 0.5 * (-log(2,1))+0.5 * (-log(2,1))=1 E(inclev) = 0.5 * (-log(2,1))+0.5 * (-log(2,1))=1 이혼노드에서속성 hh와 inclev에의한정보획득은동일하며 (hh를분류속성으로임의로정하였음 ), 이렇게만들어진판단트리는 Fig. 3과같이나타낼수있다. 판단트리가만들어진후유도된모델은클래스속성이없는새로운데이터레코드의클래스를예측할수있고이러한연산을 prediction join이라한다. 이연산은각노드의연관된분류조건이평가되는트리의경로를따라서모델이해석되어지며다음과같이정의할수있다. (prediction-join) 입력 : 판단트리 T : 노드 N 0, N n 으로구성 소스릴레이션 R(A 1,, A m ) Fig. 3. Decision Tree Model 출력 : prediction 릴레이션 Rp(A 1,, A m, 클래스속성 ) node path N 0,, N k, t R, t p Rp : k m k maximal i i = 1,, k : t(a i )=t p (A i ) cond Np (t p )=true and t p (cl)=cl Ni prediction join의구현은모델표현에의존하기때문에적당한자료구조가필요하며, 트리를 RDBMS에저장하기위해서 flat table 구조를이용한다. 그런예로 Fig. 3의판단트리를테이블로표현하면 Table 5와같다. Table 5. Decision Tree Table of Fig. 3 parents node attribute attribute value class label probabi lity N 0 - - - n 0.70 N 1 N 0 A 2 mrg n 1.0 N 2 N 0 A 2 unm y 0.5 N 3 N 0 A 2 div y 0.5 N 4 N 2 A 1 y n 1.0 N 5 N 2 A 1 n y 0.67 N 6 N 3 A 1 y n 1.0 N 7 N 3 A 1 n y 1.0 판단트리테이블의각튜플은각노드에해당되며, N 1 노드에해당하는튜플은다음과같은 pl/sql 코드에의해서생성된다. declare v_ncnt number; v_ycnt number; clslb varchar2(5); v_prob number; select count( * ) into v_ncnt 이터테이블 * / / * psmset : 훈련데 from (select * from psmset where mrg='mrg') g where defaults='n'; v_ycnt :=0; if v_ncnt >= v_ycnt then else clslb:='n'; select v_ncnt / (v_ncnt + v_ycnt) into v_prob from dual; clslb:='y'; select v_ycnt / (v_ncnt + v_ycnt) into v_prob from dual; end if; 테이블 * / / * ndttab : 판단트리 insert into ndttab(node, parent, att, atval, cls, prob) values(1, 0, 'mrg', 'mrg', clslb,v_prob); end;
판단트리분류를위한 SQL 기초기능의구현에관한연구 861 판단트리의테이블표현의각튜플은부모노드로부터현재노드까지를경로로하는트리의각간선 (edge) 으로나타낸다. 간선은조건과연관되어있으며, 속성이름은속성필드에저장되고, 분류를위한도메인은속성값필드의값들에의해서표현된다. 클래스라벨필드는그클래스에속할확률과더불어간선의노드에연관된파티션에가장많이나타나는클래스의라벨을갖는다. prediction join의의사코드는다음과같다. 위의질의어의원형은다음과같다. select * from model where (atname = 'A 1 ' and A 1 =a 1 )or (atname = 'A 2 ' and A 2 =a 2 )or (atname = 'A m ' and A m =a m ) procedure predictionjoin(source table S, model table M) foreach tuple t S =(a 1,, a m ) S execute query q(t S ) fetch tuple t M =(n, p, c, prob) node := n classlabel := c finished := false do do fetch tuple t M =(n, p, c, prob) if tuple = not found create result tuple (a1,, a m, c) finished := true while p node node := n classlabel = c while not finished 소스릴레이션의각튜플 t S =(a 1,, a m ) 에대해서튜플의속성값에의해서만족되는조건을갖는노드들이선택된다. 다음은 Table 2의시험데이터집합의 11번튜플에대해서판단트리테이블로대응하여, 그결과를임시판단트리에넣은후임시판단트리테이블을노드번호순으로정렬하는 pl/sql 코드이다. set serveroutput on delete from tdttab; / * tdttab은임시판단트리테이블 * / insert into tdttab select * from ndttab / * ndttab은훈련데이터에대한판단트리테이블 * / where (att='hh' and atval='n') or (att='mrg' and atval='unm') or (att='inclev' and atval='l'); delete from stdttab; / * stdttab은임시판단트리테이블을노드번호순으로정렬 * / insert into stdttab select * from tdttab order by node asc; end; 이후보노드들은노드-id( 노드번호 ) 순으로정렬되며근노드로부터시작해서현재노드-id가부모-id인다음노드를얻는다. 이런경우클래스라벨과확률이활동소스튜플 ( 시험데이터튜플 ) 에배정된다. 이런절차를수행하는시험데이터세트의 11번튜플을처리하는 pl/sql 코드는다음과같다. declare frnode number; / * current node * / nxnode number; / * next node * / tcls varchar2(5); / * class label * / tprob number; / * probability * / procedure calcsetcls(strowid in varchar2) / * calculate and set the class label and probability * / is select node into frnode from stdttab / * sorted temparay decision table * / where parent = 0; loop select node into nxnode from stdttab where parent=frnode; if nxnode!= 0 then frnode := nxnode; end if; end loop; exception when NO_DATA_FOUND then select cls into tcls from stdttab where node = frnode; select prob into tprob from stdttab where node = frnode; update pstset / * update the test set tuple * / set defaults=tcls where id=strowid; update pstset set prob=tprob where id=strowid; end calcsetcls;
862 정보처리학회논문지 / 소프트웨어및데이터공학제 2 권제 12 호 (2013. 12) calcsetcls('11'); / * 11 tuple of the test set table * / end; Table 2의시험집합을판단트리의테이블에적용한결과는 Table 6과같다. Table 6. Decision Tree Table of Table 2. Test set id hh mrg inclev defaults prob 11 n unm l y 0.67 12 y mrg l n 1.0 13 y div m n 1.0 14 n unm m y 0.67 15 n div l y 1.0 4. 성능평가 본논문의기초기능에대한성능을비교평가하기위해서 sun workstation 시스템에 solaris OS를구축하고, 대부분데이터베이스환경에서실험이가능하나본논문에서는이들제품들중에서 Oracle 9i 버전의 pl/sql 프로그래밍언어를사용하여실험을진행하였다. 합성된실험데이터세트는 10개의속성을갖는테이블로구성하고적용된튜플의개수는 10만개, 11만개, 12만개등세가지로분류하였다. 각속성은 1에서 5까지의개별값들을갖는다. 본실험으로첫번째, 노드통계테이블을만드는질의어에대한몇가지인덱스전략에대한성능실험이며, 두번째, partial-match 질의에대한전체테이블스캔, 비트맵인덱스, MDH 기반기본기능등을비교평가하였다. 다음은성능평가실험에이용하기위한훈련집합, 노드통계테이블, 기본인덱스, 비트맵인덱스등을만드는 pl/sql 코드들이다. 훈련집합생성 pl/sql 코드 delete from trset; sttime := systimestamp; for i in 1.. 120000 loop insert into trset(a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,cs) / * this is the training set * / select trunc(dbms_random.value(1,6)), ~ 중략 ~ from dual; end loop; end; trunc(dbms_random.value(0,2)) 노드통계테이블생성 pl/sql 코드 delete from ndsttab; / * ndsttab: node statistics table * / set serveroutput on declare sttime timestamp; entime timestamp; tstring varchar2(200); sttime := systimestamp; insert into ndsttab (select 'a1', a1, cs, count( * ) from trset group by a1, cs) (select 'a2', a2, cs, count( * ) from trset group by a2, cs) ~ 중략 ~ (select 'a10', a10, cs, count( * ) from trset group by a10, cs); entime := systimestamp; dbms_output.put_line(entime - sttime); delete from times; insert into times values(entime, sttime); select extract(hour from (tentime - tsttime)) ':' extract(minute from (tentime - tsttime)) ':' extract(second from (tentime - tsttime)) into tstring from times; dbms_output.put_line(tstring); end; 기본인덱스생성 pl/sql 코드 create table itrset12(a1 varchar2(2), a2 varchar2(2), a3 varchar2(2), a4 varchar2(2), a5 varchar2(2), a6 varchar2(2), a7 varchar2(2), a8 varchar2(2), a9 varchar2(2), a10 varchar2(2), cs varchar2(2)); create index idx0112 on itrset12(a1); create index idx0212 on itrset12(a2); ~ 중략 ~ create index idx1012 on itrset12(a10); 비트맵인덱스생성 pl/sql 코드 create bitmap index idxb0112 on btrset12(a1); create bitmap index idxb0212 on btrset12(a2); ~ 중략 ~ create bitmap index idxb0912 on btrset12(a9); create bitmap index idxb1012 on btrset12(a10); 첫번째, 비교평가로노드통계테이블을만드는질의어에대한각인덱스전략별실험결과는아래 Table 7과같다. Table 7의결과를기반으로성능비교한결과, 인덱스를사용하지않은질의와기본인덱스를사용한질의결과보다비트맵인덱스를사용한질의결과가더우수하다는것을
판단트리분류를위한 SQL 기초기능의구현에관한연구 863 Table 7. Specific performance test results for each index strategy (unit : second) tuple number 100,000 110,000 120,000 count no index primary index bitmap index 1 4.574092 4.155113 4.004418 2 4.296085 4.200096 4.020136 3 4.310769 4.199035 4.003782 1 4.747681 4.531726 4.438142 2 4.752661 4.536967 4.457907 3 4.746554 4.536083 4.427109 1 5.046417 4.892384 4.855071 2 5.008943 4.889755 4.850213 3 5.051371 4.901146 4.857553 알수가. 추가적으로기본인덱스를사용한테이블생성시간보다비트맵인덱스를사용한테이블생성시간이훨씬작았다. 이결과테이블및질의어수행시간면에서기본인덱스를사용하는것보다비트맵인덱스를사용하는것이우수함을학인할수있었다. 두번째실험으로 partial-match 질의어에대한서로다른전략으로전체테이블스캔, 비트맵인덱스, MDH 기반기본기능등올비교를하였으며상기에서제시된다양한수의정의되지않은속성들을가진 10만개튜플의테이블을대상으로하였다. 아래 Fig. 4는전략별 100개의질의를적용한평가결과시간이다. Fig. 4. partial-match query evaluation result partial-match에서모든속성들이쿼리에주어진경우라면완전검색쿼리의상황에서 MDH가 1.2초필요하며, 완전스캔은약 17초, 비트맵의경우 19.5초의시간을필요로한다. 정의되지않는속성들의수가증가할수록경과시간은완전스캔과비트맵인덱스보다많이시간을필요로하지만완전검색쿼리에서 6개의속성개수까지는 MDH 전략이우수하다는점을보였다. 5. 결론 데이터마이닝과데이터베이스시스템의결합은대형데 이터베이스에대한데이터마이닝의효율을향상시킨다. 특히판단트리분류에대한기초기능이 DBMS에의해서제공되는경우에대해서본논문에서서술했고, 기초기능을 pl/sql로구현하는것에대해서기술하였다. 첫째로판단트리분류기능을분석해서공통적인기초기능을확인하였으며, 둘째로기초기능의효율적인구현을위해서데이터베이스시스템의 pl/sql을사용하였다. 기초기능의하나로분류측도를계산하는연산을노드통계테이블에대한 pl/sql 의함수로구현했다. 예시훈련데이터에대한판단트리모델을만들고예시시험데이터에적용해서예상되는클래스와확률을계산하였다. 또한, 성능평가하기위하여첫번째로판단트리에대한노드통계테이블을구현하는질의어를구현해서, 전체테이블탐색, 기본인덱스를이용한탐색, 비트맵인덱스를이용한탐색별로질의어를실행해서평가하였으며, 두번째로 partial-match 질의어에대한서로다른전략으로전체테이블스캔, 비트맵인덱스, MDH 기반기본기능등을비교하였다. 실험결과는이런기초기능의장점을각전략별로제시하였고, 데이터베이스시스템과의통합의필요성을보여주었다. 참고문헌 [1] Surajit Chaudhuri, Data Mining and Database Systems: Where is the Intersection?, Data Engineering Bulletin, 21(1): 4-8, 1998. [2] R. Meo, G. Psaila, and S. Ceri. A New SQL-like Operators for Mining Association Rules. VLDB 96, pp. 122-133, Mumbai, India, Sept., 3-6, 1996. R. [3] A. Netz, S. Chaudhuri, J. Bernhardt, and U. M. Fayyad, Integration of Data Mining with Database Technology, Proceedings of 26the International Conference on Very Large Data Bases, September 10-14, 2000. [4] Vipin Kumar, etc., Introduction to data mining, Addison-Wesley, May 12, 2005. [5] L. Breiman, J. H. Friedman, R. A. Olshen, and C. J. Stone, Classification and Regression Trees, Chapman and Hall, 1984. [6] M. Xu, J. Wang, and T. Chen, Improved decision tree algorithm: ID3+, Intelligent Computing in Signal Processing and Pattern Recognition, Vol.345, pp.141-149, 2006. [7] M. Mehta, I. Rissanen, and R. Agrawal, MDL-based Decision Tree Pruning, Proc. of Intl. Conf. on Knowledge Discovery in Databases and Data Mining, Montreal, Canada, 1995. [8] S. Chaudhuri, U. M. Fayyad, and J. Bernhardt, Scalable Classification over SQL Databases, ICDE-99, pp.470-479, Sydney, Australia, 1999. [9] J. Gerhke, R. Ramakrishnan, and V. Ganti, RainForest - A Framework for Fast Decision Tree Construction of Large Datasets, VLDB 98, pp.416-427, New York City, New York, USA, 1999.
864 정보처리학회논문지 / 소프트웨어및데이터공학제 2 권제 12 호 (2013. 12) [10] S.B. Kotsiantis, D. Kanellopoulos and P.E. Pintelas, Data Preprocessing for supervised learning, International Journal of Computer Science, Vol.1, No.2, 2006. [11] M. BenHajHmida and A. Congiusta, Parallel, distributed, and grid-based data mining : algorithms, systems, and applications, Handbook of Research on Computational Grid, IGI Global, pp.90-119, May, 2009. [12] L. Zhou, Z. Zhang, and M. Xu, Massive data mining based on item sequence set grid space, In Proceedings of the 2nd International Asia Conference on Informatics in Control, Automation and Robotics, pp.208-211, March, 2010. 고재진 e-mail : jjkoh@ulsan.ac.kr 1972년서울대학교응용수학과 ( 공학사 ) 1981년서울대학교계산통계학과 ( 이학석사 ) 1990년서울대학교컴퓨터공학과 ( 공학박사 ) 1975년~1979년한국후지쯔 ( 주 ) 기술개발부사원 1979년~2010년울산대학교컴퓨터정보통신공학부교수 2011년~현재울산대학교전기공학부교수관심분야 : DB시스템, 전문가시스템, DB설계, ERP 안형근 e-mail : hkahn@ulsan.ac.kr 2003년울산대학교정보통신대학원정보통신공학과 ( 공학석사 ) 2008년울산대학교컴퓨터정보통신공학부 ( 공학박사 ) 1997년~2004년현대오토시스템기술지원부 2004년~2006년 ( 주 )CFIC 기업부설연구소연구소장 2008년~2010년울산대학교컴퓨터정보통신공학부객원교수 2012년~현재울산대학교 LINC사업단연구교수관심분야 : 멀티미디어DB, DB설계 / 분석, ERP, BPM, Workflow