Journal of the Korea Institute of Information and Communication Engineering 한국정보통신학회논문지 (J. Korea Inst. Inf. Commun. Eng.) Vol. 18, No. 3 : 595~601 Mar. 2014 역순트리를이용한특이데이터국소적접근 임광철 1 설정자 2* Unusual data local access using inverse order tree Kwang-cheol Rim 1 Jung-ja Seol 2* 1 Department of Computer Engineering, Chosun University, Gwangju 230-7381, Korea 2* Department of Mathmatics, Chosun University, Gwangju 230-6610, Korea 요약 스마트정보통신시대에데이터의수는기하급수적으로증가하고있다. 이에데이터발생지역과발생상황을실시간으로파악하고분석하는것이신속한조치를취하는중요한요소로떠오르고있다. 본논문에서는분석자가원하는특성데이터발생지역의국소적판단을하기위하여데이터발생에대한값을최하위모듈에서부터최상위모듈까지이어지는루트를역순으로진행하면데이터발생과동시에분석이가능하다. 먼저군집분석에대해알아보고군집원들의합에의한분석법을트리구조에병합하여최하위모듈부터최상위모듈까지발생특성값에대해수치로치환하고그합을도출하도록설계하였다. 또한특성값에대한가중치를부여하여원하는값의발생상황을실시간으로도출되도록설계하였다. ABSTRACT With the advent of the Smart information-communication era, the number of data has increased exponentially. Accordingly, figuring out and analyzing in which area and circumstance the data has been created becomes one of the factors for prompt actions. In this paper identifies how to analyze the data by implementing a route from the lowest module to highest one in an inverse order for the part judgement for the particular data. The script first identifies cluster analisys, paralizes the analysis using the sum of each factors of the cluster with the tree structure, and finally transpose the answer into number. Also, it is designed to place priority on particular answer, thereafter, draws the wanted answer real-time. 키워드 : 역순트리, 가중트리, 10 진트리, 빅데이터, 실시간분석 Key word : inverse order, weight tree, digit tree, Big data, real time analysis 접수일자 : 2014. 01. 20 심사완료일자 : 2014. 02. 11 게재확정일자 : 2014. 02. 26 * Corresponding Author Jung-ja Seol (E-mail:jzseol@korea.com, Tel:+82-62-230-7381) Department of Mathmatics, Chosun University, Gwangju 230-6610, Korea Open Access http://dx.doi.org/10.6109/jkiice.2014.18.3.595 print ISSN: 2234-4772 online ISSN: 2288-4165 This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License(http://creativecommons.org/li-censes/ by-nc/3.0/) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited. Copyright C The Korea Institute of Information and Communication Engineering.
한국정보통신학회논문지 (J. Korea Inst. Inf. Commun. Eng.) Vol. 18, No. 3 : 595~601 Mar. 2014 Ⅰ. 서론스마트정보통신시대로접어들면서범람하는정보의홍수와이를가공, 변환하여새로운정보로생성하고그로인한여러가지결론을도출시키는일이계속하여일어나고있다. Big data라는신조어가만들어지고 Big data를이해하고이에속한 data 의흐름을분석, 통계, 취합하여보다나은의사결정의수단으로사용되고있다. Big data의생성은새로운경제성장을위한중요한가치창출효과를가져온다고볼수있고작은정보들일지라도모이면거대한흐름과새로운문화, 경제, 사회흐름을형성한다. 또한소셜네트워크데이터로글퍼짐관계와특정주제에대해관심있는그룹, 그리고그룹간의관계와그룹내에영향력있는사람관련분야에대한전반적인내용을분석할수있다 [1]. 방대한정보를추출하여다른정보와연계성을파악하는텍스트마이닝기술과데이터의긍정, 부정, 중립등선호도를구별하는오피니언마이닝등페이스북이나트위터에서사용될수있는관측개체를몇개의그룹으로나눔으로써대상집단에대한효율적인활용과아울러앞으로일어날일을예측할수있게되었다. Big data 의발달은순기능만제공해주는것은아니다. 필요이상으로많은데이터들이범람함으로인하여개인정보유출과이로인한보안취약성이급증할수있다. 최근사이버공격이표적공격으로심화되어사이버테러, 사이버전 (war), 핵티비즘등으로집중공격이매번새로운공격방법으로접근하고있다. 때문에발생 data 의관리는중요한부분을차지하고있다. Big data 관리에서중요한요소로저장된데이터로부터필요한정보를신속히획득할수있어야한다는점이다 [2]. 이에본고에서는 Big data로인하여발생하는 data 들을취합하지않고실시간으로탐색하는구조를설계하고자한다. Data 탐색의기본방식은모든 data를모아서첫째항부터끝항까지검색하고일치하는 data 를골라내는방식이기준으로주어져있다. 역순10진트리구조는방향을반대로돌려서최상위모듈의구성이하위모듈로부터올라오게설계를하였다. 검색시간은기하급수적으로줄어들고하위모듈에서올라오는 data의합으로인하여상위모듈의성분을결정하게되므로상위모듈에서하위모듈로실시간탐지가 가능하게되었다. 먼저그룹을분류하고분석할수있는그룹분석이론에대하여살펴보고역순 10진트리구조와각각의성분에가중치를부여한가중트리구조그리고그룹에가중치를부여한모듈가중진트리에대해정의하였다. 마지막으로역순트리구조를활용하는방안에대해간략히언급하였다. Ⅱ. 군집분석관측대상에대한각각의특징들이표현되는데이터들의분류기준을서로의유사성에의해분류하고분석하는것을군집분석 (cluster analisys) 라한다. 군집분석의종류는크게두가지로볼수있다. 관측대상간의거리 ( 유사성, similarity) 를기초로해서가까운것들끼리군집으로묶는방법이있고데이터간의분산을이용하여그룹간분리정도를결정하는방법이있다. 본고에서는거리개념을도입한분석을살펴보고이를실시간데이터검색으로확장해서알아본다. 군집분석을실시하기위하여관측대상이 n개의속성을갖고 m개의관측대상을갖는다고하면각각의 m개의관측대상마다주관적인척도를줄수있고이러한척도에대해관측값이변이되는데이터들에대한측정값을산정한다. m개의관측대상들중임의의두관측대상을, 라하면 로나타낼수있고이는각관측대상들을 n차원벡터공간의원소로볼수있고이에대한유사성의척도를각각의대응하는변량의차가작으면두대상을유사하다고판단하는유클리드거리와각각변량들마다가중치를적용하는가중유클리드거리로표현할수있다., 유클리드거리 596
역순트리를이용한특이데이터국소적접근, 는가중치 주어진관측대상을벡터공간의원소로보고두벡터의내적으로유사성을정의할수도있다. (1) 이고이를표준화하여 Pearson 적률상관계수를구하면 (2) 만약관측대상의모든성분들이 2진 data인경우를 categorical data라하며동일위치의벡터성분의연관성을 4가지의형태의자료로분류한다., (1,1) 의개수 (1,0) 의개수, Ⅲ. 역순트리수형도는나무모양으로데이터의흐름을표현하는방법으로주로 2진트리구조를사용한다. 본고에서는가지가 10개인 10진트리구조를제안하고이에대한정의와구조를설계한다. 정의 n항수형도모든모듈의차수가 n 이하인루트수형도를 n항수형도라하고 n=10 인경우를 10진수형도 (digitary tree) 라한다. 정의 상태전이 (state transmition) n번째모듈의상태즉 n번째모듈의총성분들의합을상태라하며이상태를상위모듈에전해주는것을상태전이라한다. 정의 상위탐색 n-th 수형도의최상위모듈에서부터반응모듈로내려가는탐색을상위탐색이라한다. 정의 상위탐색시간상위탐색으로반응모듈까지상태를검색하면서거치는모듈의개수를상위탐색시간이라한다. (0,1) 의개수 (0,0) 의개수 정의 차수각각의모듈에서나오는가지의수를차수라하고가지가 10개인경우 10차라한다. 이므로 임을알수있다. 본고에서는이미생성된 data가아닌생성될 data에대한상태파악을기준으로분석을진행한다. 가중치를적용하기전의각각의벡터성분의합을 (3) 라하고이를상위모듈에전송하여상위모듈을생성하는방식으로 data를완성한다. 정의 깊이최상위모듈에서최하위모듈까지이르는최단거리를트리의깊이라한다. 3.1. 역순10진트리그림 1에서보는바와같이각각의모듈별로 10개의가지를가지고있는구조를 10진트리구조라하고최상위모듈에서최하위모듈까지의데이터에접근하는데걸리는시간은어느곳으로접근하더라도탐색시간이 3 으로나타난다. 이는최상위모듈에서최하위모듈까지의거리를계산하는데깊이가깊을수록기하급수적으로단축됨을볼수있다. 깊이가 10인트리구조를살펴 597
한국정보통신학회논문지 (J. Korea Inst. Inf. Commun. Eng.) Vol. 18, No. 3 : 595~601 Mar. 2014 그림 1. 깊이 3 인 10 진트리 Fig. 1 digit tree of deep 3 보면최하위모듈의수는 개인데반해최상위모듈에서최하위모듈까지탐색해들어가는데걸리는탐색시간은 log 으로지수에종속됨을볼수있다. 각각모듈에서의성분의움직임은아래모듈의성분의합으로표현한다. 그림1에서최하위모듈인 x30의 성분의합은 이고이는 x20의첫번째성분으 로상태전이된다. 또한 x20의두번째부터 10번재성분은각각 x31의성분의합과 x39의성분의합으로상태전이된다. x20의성분의합은또다시 x1의첫번째성분으로상태전이된다. 즉최하위모듈인 x30에서최상위모듈인 x1까지거리가 3으로, 상위탐색에의해최하위모듈까지가는데거리 3이됨을볼수있다. 깊이가 3인 10진트리의성분은다음식을따른다. = = = = = = = = (4) 가됨을볼수있다. 이를깊이가 10인 10진트리로확장해보면최상위모듈의성분들은아래모듈들의모든성분의합으로표현할수있다. =, (5) 3.2. 가중치를적용한 10진트리최하위모듈의성분에각각가중치를부여하거나각각의모듈에가중치를부여하는트리구조를살펴보자. 역순10진트리구조에서최하위모듈각각의성분에특정한가중치를부여한구조를가중10진트리라하고성분이아닌모듈에가중치를부여한구조를모듈가중10 진트리라하자. 그림 2에서와같이최하위모듈에속하는 10개의성분에각각가중치 를부여하 598
역순트리를이용한특이데이터국소적접근 그림 2. 깊이가 3 인가중트리 Fig. 2 weight of deep 3 여각각의성분에크기를달리하는것을가중10진트리라하고그림 2에서와같이차상위모듈에군집분석에의해분류하고각각의그룹의중요도에따른가중치 를각모듈의성분합에곱하여상태전이시키는방법을모듈가중10진트리라한다. 3.2.1. 가중10진트리최하위성분의원소를결정지을때각각성분의중요도에따라성분출현에대한가중치를부여하는방법으로그림 2의 의성분각각에다음과같이가중치를부여한다. = 이의합 는 의첫번째성분으로상태 전이된다. 마찬가지로 의두번째부터 10번째성분은각각 와 의성분합으로상태전이된다. 의성분의합은 의첫번째성분으로상태전이된다. 깊이가 3인역순가중10진트리의성분은다음과같이결정된다. = = = = = = = = (6) 가중10진트리는찾고자하는성분에특성을부여하여최하위성분에출현빈도가적더라도강한특성값을갖는다면상위모듈에그특성이반영되게설계하였다. 3.2.2. 모듈가중 10진트리동일한성분의구성이라도각각의모듈을형성하는데서로다른성질의군집을이룰수있다. 군집을구성하는방법은일반적인유클리드군집분석으로접근하기힘든상황들이연출된다. 이에사용자의전문적인지식과생각이부여된전문가시스템에의한군집분석이이루어져야한다. 이후각각의군집들의가중치를달리표현해서분석하는방 599
한국정보통신학회논문지 (J. Korea Inst. Inf. Commun. Eng.) Vol. 18, No. 3 : 595~601 Mar. 2014 법을모듈가중 10진트리라한다. 본고에서는단순유클리드거리를이용하여모듈가중10진트리의구조를살펴보기로하자. 깊이가 3인 10 진트리구조에서두번째단계인 은 까지의성분의합이 각각의성분으로상태전이되었고 의각각의성분은 성분의합이상태전이된것이다. 이는 부터 까지거리 1인유클리드군집분류에의해 으로상태전이됨을볼수있다. 이후 에는가중치 를 에는가중치 을부여하면첫번째모듈인 에서가중치의영향을받은성분이각각생성된다. = = = = (7) Ⅳ. 결론현대사회는과거에비해어마어마한양의 data가발생하고이러한 data 들을분석, 가공후필요한정보를생성하는대는시간과공간의제약이따른다. 최근 big data에대한여러연구성과와실사용예들이속속나오고있는실정이지만대부분이이미발생된 data를취합하여제가공하는방식으로진행된다. 모든 data는취합하는순간이미지나버린정보로취급된다. 다시말해 data를가공하기위하여하는작업자체는실시간대응은이룰수없다고볼수있다. 본논문에서살펴본바는먼저군집분석에대하여정의를하고군집분석상거리 1인유클리드거리를이용하여하위모듈을분류하고진행하였다. 역순10진트리를설계하고수학적인흐름을통해최상위모듈까지의발생빈도합을도출하였고가중10진트리구조는각각의발생data에가중치를부여하는방식과발생모듈에가중 치를부여하는방식으로발생빈도합을수학적으로계산하였다. 이는기존알려진트리구조의설계에비하여지역적접근면에서실시간으로발생을제어할수있다는것을살펴보았다. 역순10진트리와역순가중10진트리는발생하는 data를실시간으로빈도를확인하고어떠한장소, 어떠한그룹에서일어나는이벤트인지를바로확인할수있는장점이있다. 예를들어감기와관련된단어를최하위성분으로구성한다면 감기, 인플루엔자, 열, 기침, 컨디션, 와같이감기와관련어를최하위성분으로배열하고발생하는매순간각성분값이 1 로활성화된다. 이후 감기, 열 이라는단어가최하위성분에도출되면, 과 가 1이되므로 =2 로상태전이된다. 이는 =2 로상태전이되어최하위모듈의결과값이최상위모듈로취합됨을볼수있다. 사용자는최상위모듈의 의상태를보고 으로탐색해들어갈수있다. 최상위모듈에서성분값이정해진값이상이도출되면바로하위탐색하여발생한지역과그룹을선별하고이벤트를해결할수있다. 역순10진트리탐색은깊이가 10인경우 개의검색대상을선정할수있고선정된대상들에대한실시간탐색시간은최하위모듈까지 log 로도출되므로많은대상에대한실시간정보검색과대응이가능하다. 여러연구자들의관심과좀더진전된모습으로발전된다면 Big data 응용분야뿐만아니라의료, 기상, 보안, 바이러스확산, 등등그응용범위는광범위하다할수있다. REFERENCES [1] S. J. Shin, SNS using Big Data utilization research, Journal of the Institute of Internet, Broadcasting and Communication, vol. 12, no. 6, pp. 268-272, Dec. 2012. [2] J. H. Kim, S. H. Lim, I. K. Kim, H. S. Cho, B. k. No Technical trends of cyber security with Big data, Journal of the Electronics and telecommunications trends, vol. 28, no. 3, pp.19-29, Jun. 2013. 600
역순트리를이용한특이데이터국소적접근 임광철 (Kwang-cheol Rim) 2000 년조선대학교대학원이학석사 2006 년조선대학교대학원이학박사현재조선대학교수학과외래교수 관심분야 : 응용수학, 정보보안, 양자암호, 암호학 설정자 (Jung-Za Seol) 2000 년조선대학교교육대학원교육학석사 2007 년조선대학교컴퓨터공학박사수료현재조선대학교컴퓨터공학부외래교수 관심분야 : 통신네트워크및정보보안, 유비쿼터스 601