위키피디아카테고리구조를이용한상하위관계추출 최동현 O 최기선 KAIST 전산학과시멘틱웹연구센터 cdh4696@world.kaist.ac.kr, kschoi@cs.kaist.ac.kr ISA Relation Extraction from Wikipedia Category Structure DongHyun Choi O Key-Sun Choi Semantic Web Research center, Computer Science Department, KAIST 요약 상하위관계자동추출은분류체계를자동구축하는데있어서핵심적인내용이며, 이렇게자동으로구축된분류체계는정보추출과같은여러가지분야에있어서중요하게사용된다. 본논문에서는위키피디아카테고리구조로부터상하위관계를추출하는방식에대하여제안한다. 본논문에서는판별하고자하는위키피디아카테고리구조뿐만이아닌, 그와관련된다른위키피디아카테고리구조까지고려하여카테고리이름에나타난토큰들간의수식그래프를구축한후, 그래프분석알고리즘을통하여각카테고리구조가상하위관계일가능성에대한점수를매긴다. 실험결과, 본알고리즘은기존의연구로상하위관계임을판별할수없었던일부카테고리구조에대하여성공적으로상하위관계인지를판별하였다. 주제어 : 상하위관계, 위키피디아카테고리, 분류체계 1. 서론 1.1 문제정의 분류체계는문서클러스터링 [1], 데이터베이스검색 [2] 및정보추출 [3] 과같은작업들에있어서중요하게사용된다. 따라서, 분류체계를자동으로구축하기위해서수많은연구들이이루어져왔다. 일부연구는비구조화된일반문서로부터분류체계를구축하고자하였고 [4, 5], 일부연구는위키피디아카테고리와같이구조화된정보로부터분류체계를얻어내고자시도하였다 [6, 7, 8]. 다수의연구들이비구조화된문서로부터상하위관계를얻어내어분류체계를구축하고자시도하였으나, 다수의연구들이낮은정확률과재현율을보였다. 반면에, 구조화된데이터로부터상하위관계를얻어내고자하는시도는상대적으로높은성능을보였으나, 대규모의분류체계를얻어내기위해서는그보다훨씬더큰크기의구조화된데이터를요구하는문제가있다. 최근들어위키피디아 [9] 나 DBPedia[10] 와같은구조화된대용량의데이터가사용가능해짐으로써이문제는어느정도해결되었다. 본연구에서는위키피디아의카테고리구조로부터상하위관계를추출하는방식에대하여제안한다. 위키피디아의카테고리구조는카테고리와페이지, 그리고그것들간의포함관계로이루어져있다. 페이지는위키피디아의문서하나를의미하며, 카테고리는이러한페이지들과다른카테고리들을무기명다수의일반인들이임의로분류한후이름을붙인것이다. 위키피디아카테고리구조는전문가가아닌사람들에의하여구축되었지만, 다수의사람들에의하여정제됨으로써어느정도의신뢰성을확보할수있고, 또한위키피디아카테고리구조는 764,581 개의카테고리와 6,801,594 개의페이지간의 35,904,116 개의포함관계를보유 1) 하고있어대량의상하위관계를추츨하기위한좋은자료가된다. 본논문에서는위키피디아카테고리구조로부터상하위관계를추출하는방식에대하여제안한다. 1.2 제안하는모델의구제적인예 본논문에서위키피디아카테고리구조는 <A, B, n> 의형태로써표현되며, A 는 B 를포함하는카테고리의이름, B 는 A 에의해포함되는카테고리또는페이지의이름, n 은 A 와 B 사이에존재하는카테고리의개수이다. 예를들어, Wikipedia 의 ipod 페이지는 2001 introduction", "portable media player", "industrial design examples", "IPod" 라는 4 개의카테고리에속해있는데, 이를위의표현방식으로나타내면, <2001 introduction, ipod, 0>, <Portable media players, ipod, 0>, <Industrial design examples, ipod, 0>, <IPod, ipod, 0> 이된다. 위의 ipod 의예시에서볼수있듯이, 모든카테고리구조가상하위관계로전환될수있지는않다. 카테고리구조 <Portable media players, ipod, 0>, <Industrial design examples, ipod, 0> 는상하위관계로볼수있지만, <2001 introduction, ipod, 0> 는상하위관계가아니고, 단지두개의단어가서로관계가있을뿐이다. 본논문에서는어떤카테고리또는페이지이름 B 가주어졌을때, B 를하위카테고리 / 페이지로가지는모든카테고리구조 <A, B, n> 에대하여, 각카테고리구조가상하위관계가될수있는가능성을점수로계산하여정렬한다. 이때, 하나의카테고리구조에대한점수를매기기위하여, 페이지이름 B 가포함된다른카테고리구조에서 1) 2009 년 8 월 27 일현재
추출된정보를이용한다. 표 1 은페이지 ipod 에대하여, 본논문에서제시된방법을이용하여카테고리구조에점수를매겨순위화한것이다. n 2 로설정하였다. 표 1 페이지 ipod을포함하는카테고리구조의순위화결과 입력 입력을 하위로 가지는 카테고 리 구조 (n 2) 정렬된 카테고 리구조 2. 관련연구 ipod <2001_introductions, ipod,0> <2001, ipod, 1> <2000s, ipod, 2> <21st_century_introductions, ipod, 1> <21st_century, ipod, 2> <Introductions_by_year, ipod, 2> <Portable_media_players, ipod, 0> <MPEG, ipod, 1> <ISO_standards, ipod, 2> <IEC_standards, ipod, 2> <Broadcast_engineering, ipod, 2> <Television_technology, ipod, 2> <Digital_audio_players, ipod, 1> <Digital_audio, ipod, 2> <MP3, ipod, 2> <Audio_players, ipod, 2> <Industrial_design_examples, ipod, 0> <Industrial_design, ipod, 1> <Design, ipod, 2> <Industry, ipod, 2> <Applied_sciences, ipod, 2> <ipod, ipod, 0> 카테고리구조점수 <Digital_audio_players, ipod, 1> 1.47 <Portable_media_players, ipod, 0> 1.24 <Audio_players, ipod, 2> 1.24 <Digital_audio, ipod, 2> 0.36 <MPEG, ipod, 1> 0 이하, 모두점수 0으로동일 위키피디아카테고리로부터분류체계확장을위한상하위관계를추출하는연구중대표적인것으로는두가지가있다. [7] 에서는주어진카테고리구조에포함된두카테고리이름이같은중심어를가지는지, 한카테고리이름에서의수식어가다른카테고리이름에서중심어로쓰이는지, 상위카테고리이름이복수형인지등을검사하여주어진카테고리구조가상하위관계인지아닌지를판별하였다. [8] 에서는카테고리이름에서나타나는특정패턴 5개 (members of X, X [VBN IN] Y, X [IN] Y, X Y, X by Y) 를정의하고, 정의된패턴이카테고리이름에서 발견되었을시정해진규칙을기반으로하여상하위관계및기타다른관계들을추출하였다. 지금까지이루어진위키피디아카테고리를기반으로한상하위관계추출연구들은카테고리이름에서어떤특정한패턴이나타나야만주어진카테고리구조가상하위관계인지를판별할수있었다. [7] 의논문에서보고된바에의하면, [7] 의방법으로는 349,263개의카테고리-카테고리링크중 81,564 개에대하여, 그것이상하위관계인지를판별할수없었고, 또한카테고리 - 페이지링크에관해서는연구가진행되지않았다. 본연구에서는기존연구의이러한한계를극복하기위하여, 카테고리구조가주어졌을때관련된다른카테고리구조들을이용하여주어진카테고리구조가상하위관계인지를판별하는방법을제안한다. 3. 제안모델본단원에서는주어진카테고리구조가상하위관계인지를판별하는점수를매기기위해서사용된두가지의알고리즘에대하여설명한다. 본단원에서는알고리즘의용이한설명을위하여다음과같은용어를사용한다. <A, B, n>: 상하위관계인지판별하고싶은카테고리구조. 상위카테고리 : 카테고리구조에서첫번째항을지칭. 하위카테고리 : 카테고리구조에서두번째항을지칭. S(a, b): a를하위카테고리로가지고, n b인카테고리구조의집합 U(a, b): S(a, b) 에속한카테고리구조의모든상위카테고리이름의집합 T(a, b): U(a, b) 에서나타나는모든토큰의집합 Freq(t, u): 토큰 t가단어 u 안에서등장한횟수 S Tok (u): 단어 u에서등장한토큰의집합 Head(u): 단어 u의중심어 Mod(u): 단어 u의수식어의집합아래에서제시된두방법에서는, 공통적으로 T(a, b) 의각각의원소에대하여점수를매긴다음, 그점수를이용하여각각의카테고리구조에점수를매기게된다. 3.1. 토큰의개수에대한방법본방법에서는판별하고자하는카테고리구조 <A, B, n> 에대하여, A를이루고있는토큰들이 B의다른상위카테고리에서도많이등장하고있을경우, <A, B> 가상
하위관계일가능성이높다고가정한다. 본가정을토대로각카테고리구조 <A, B, n> 가상하 위관계인지를나타내는척도로서의점수를매기기위하여, 먼저 T(a, b) 의각각의원소 t에대한점수를매긴다. 이를위해, t가 U(a, b) 의각각의원소 u 안에서나타난횟수를측정한후, 그값을모두더한다. 즉, 모든 t T(a, b) 에대하여, Score(t, a, b) = 로정의한다. 카테고리구조 <A, B, n> 에대한점수는다음의공식을이용하여구한다 : Score(<A, B, n>) = b는임의로지정해줄수있으며, 본논문에서는 b=2 의값을사용하였다. 어떤토큰에대한점수가정의되어있지않을경우, Score(<A, B, n>) 은무조건 0이된다. 표 2는표 1의입력을본방법을사용하여각토큰에점수를매긴예시이다. 표 3은표 2의점수를이용하여표 1의각카테고리구조에점수를매긴방식이다. 표 2 T("iPod", 2) 의각원소에개수세기방식으로점수 를매긴예시 t T("iPod", 2) Score(t, "ipod", 2) introduction, player, audio, design 3 2001, 21st, century, standards, digital, industrial 2 2000s, by, year, portable, media, MPEG, ISO, IEC, broadcast, engineering, television, technology, MP3, example, industry, applied, science, ipod 표 3 표 1 의카테고리구조들각각에표 2 의결과를이 용하여점수를매긴예시 카테고리구조 점수 <Digital_audio_players, ipod, 1> 8 <21st_century_introductions, ipod, 1> 7 <Audio_players, ipod, 2> 6 <Industrial_design_examples, ipod, 0> 6 <2001_introductions, ipod,0> 5 <Introductions_by_year, ipod, 2> 5 <Portable_media_players, ipod, 0> 5 <Digital_audio, ipod, 2> 5 1 <Industrial_design, ipod, 1> 5 <21st_century, ipod, 2> 4 <ISO_standards, ipod, 2> 3 <IEC_standards, ipod, 2> 3 <Design, ipod, 2> 3 <2001, ipod, 1> 2 <Broadcast_engineering, ipod, 2> 2 <Television_technology, ipod, 2> 2 <Applied_sciences, ipod, 2> 2 <2000s, ipod, 2> 1 <MPEG, ipod, 1> 1 <MP3, ipod, 2> 1 <Industry, ipod, 2> 1 <ipod, ipod, 0> 1 3.2. 수식관계를나타내는그래프에기반한모델 위 3.1장에서제시된것은가장직관적인방법이나, 많은오류가존재한다. 위표 3에서두번째순위로랭크된카테고리구조 <21st_century_introductions, ipod, 1> 의경우, 상하위관계를나타내고있다고는보기힘들다. 이카테고리구조가개수세기방법에서상위에올라선이유는, introduction" 이라는토큰이 ipod의상위카테고리이름들과의관련성에비하여나타나는빈도수가높기때문이다. 이문제를해결하기위하여, 먼저다음의두가지가설을세운다 : 가정 1. 어떤중심어가여러가지중요한수식어에의해수식받는다면, 그중심어는중요하다. 가정 2. 어떤수식어가여러가지중요한중심어들을수식한다면, 그수식어는중요하다. 여기서, 중요하다 는것의의미는그것이하위카테고리 / 페이지의주요한특징을나타내고있음을의미한다. 위의가정을통해문제를해결하기위하여, 본방법에서는먼저수식어그래프를구축한다. 어떤카테고리구조 <A, B, n> 에대한수식어그래프는다음과같이정의된다 : G := (V, E) V := {v 각정점 v는토큰 t T(B, b) 에대응 } E := {(v1, v2) v1의토큰 t1은 v2의토큰 t2를 U(B, b) 의원소내부에서수식 } 이때, 변의가중치는 U(B, b) 에서해당수식관계가나타난개수로정의된다. 중심어는 [11] 의방법을이용하여추출되었다.
표 1 의예시를수식관계그래프로나타내면그림 2 와 같이표현된다. 표 1의결과는본단원에서제시된그래프기반분석방법을토대로계산된것이다. 4 실험 그림 1 표 1 의예시에서추출된수식그래프 수식그래프에서위가정 1과 2에서서술된것과같은중심어와수식어의중요도를얻어내기위하여, HITS 링크분석알고리즘 [12] 을사용한다. HITS 알고리즘을사용하는이유는, 하나의중요도점수만반환하는다른링크분석알고리즘과는달리본논문의가정에적합한두가지종류의중요도점수 - 얼마나다른중요한페이지에의해링크당했는지를나타내는 Authority 점수와얼마나얼마나다른중요한페이지를링크하는지를나타내는 Hub 점수 -를반환하기때문이다. 본논문에서는 HITS 알고리즘의 Authority 점수를중심어의중요도로, HITS 알고리즘의 Hub 점수를수식어의중요도로가정하였다. 또한, 변의가중치를계산식에넣기위하여 [13] 에서사용된변형을이용하였다. 변형된 HITS 알고리즘의수식은다음과같다 : 위수식에서, In(V i) 는정점 V i 로들어오는변을가진정점의집합을의미하고, Out(V i ) 는정점 V i 에서나오는변을가진정점의집합을의미하며, e ij 는 V i 에서 V j 로가는변의가중치를의미한다. HITS 알고리즘은먼저각정점의 Authority 및 Hub 점수들을 1로초기화한후, 먼저 Authority 점수를갱신하고이후 Hub 점수를갱신한다. 점수갱신은각점수가어느일정수준으로수렴할때까지계속된다. 카테고리구조 <A, B, n> 의점수는다음과같이계산된다 : Score(<A, B, n>) = 본논문에서제시된그래프기반방식의정확도를알아내기위하여, 위키피디아카테고리구조중그래프기반방식으로 0.5점이상을얻은 100개의카테고리구조를랜덤하게추출하였다. 이 100개의카테고리구조에대하여, 2명의어노테이터가수작업으로상하위관계인지아닌지를판별하였다. 표 4는두명의어노테이터의판별결과가얼마나일치하는지보여준다. 표 4 어노테이터평가 - 컨퓨젼매트릭스 Annotator 2 Annotator 1 O X O 57 14 X 3 26 표에서보는바와같이, 두어노테이터의평가는 83 % 일치하였다. 두어노테이터의평가가일치된 83개의카테고리구조에관하여, 68.7 % 인 57개의카테고리구조에대하여두어노테이터모두상하위관계라고판단하였고, 31,3 % 인나머지 26개의카테고리구조는모두상하위관계가아니라고판단하였다. 그래프기반방식의성능을기존연구와비교하기위하여 [7] 의방법을적용하여두어노테이터의평가가일치한 83개의카테고리구조의상하위관계를판별하였다. 표 5는 [7] 의어휘적인규칙을사용하는방법의결과를나타낸다. 표 5 [7] 의방법평가 Ponzetto[7] Annotator O Unknown O 32 25 X 17 9 표 5에서볼수있는것과같이, [7] 의방법으로상하위관계인지를판별하는것이불가능한카테고리구조들을상하위관계가아니라고결정하면, 동일한카테고리구조에대하여 [7] 의방법은단지 41개만이어노테이터의평가와일치하였다. 즉, [7] 의방법은 47.1 % 의정확도를보였다.
5 결론본논문에서는그래프분석을통하여위키피디아카테고리구조에서상하위관계를얻어내는새로운방법에대하여서술하였다. 다른알고리즘과의비교결과, 본논문에서제시된방법은기존에제시된방법 [7][8] 을이용하여알아낼수없었던상하위관계들을얻어낼수있었다. 현재는단순히카테고리의이름과동일한하위카테고리구조를가진다른카테고리구조들을사용하여주어진카테고리구조가상하위관계인지아닌지를알아낼수있지만, 주어진카테고리구조에포함된페이지의내용등을추가적인자질로이용할수있을것이다. 이부분은추후연구가필요하다. 감사의글본논문은지식경제부및정보통신연구진흥원의정보통신선도기반기술개발사업의연구결과로수행되었습니다. Taxonomy from Wikipedia. Proceedings of the national conference on artificial intelligence (2007) [8] Nastase, V., Strube, M.: Decoding Wikipedia category names for knowledge acquisition.proceedings of the 23rd Conference on the Advancement of Artificial Intelligence, pp. 1219-1224. (2008) [9] http://www.wikipedia.org/ [10] http://dbpedia.org/about [11] Collins, M.: Head-driven statistical models for natural language parsing. Ph.D. thesis, University of Pennsylvania, Philadelphia (1999) [12] Kleinberg, J. M.: Authoritative sources in a hyper-linked environment. Journal of the ACM, 46(5):604-632 (1999) [13] Mihalcea, R., Tarau, P.: A Language Independent Algorithm for Single and Multiple Document Summarization. Proceedings of IJCNLP 2005 (2005) 6 참고문헌 [1] Hotho, A., Staab, S., Stumme, G.: Ontologies improve text document clustering. Proceedings of the IEEE International Conference on Data Mining (2003) [2] Chakrabarti, S., Dom, B., Agrawal, R., Raghavan, P.: Using taxonomy, discriminants, and signatures for navigating in text databases. Proceedings of the international conference on very large data bases (1997) [3] Sanderson, M., Croft. B.: Deriving concept hierarchies from text. Proceedings of the International Conference on New Methods in Language Processing (1994) [4] Cimiano, P., Hotho, A., Staab, S.: Learning Concept Hierarchies from Text Corpora using Formal Concept Analysis. Journal of Artificial Intelligence Research (2005) [5] Cimiano, P., Pivk, A., Schmidt-Thieme, L., Staab, S.: Learning Taxonomic Relations from Heterogeneous Sources of Evidence. Ontology Learning from Text: Methods, Evaluation and Applications (2005) [6] Huang, J.X., Shin, J.A., Choi, K.S.: Enriching Core Ontology with Domain Thesaurus through Concept and Relation Classification. OntoLex07 (2007) [7] Ponzetto, S.P., Strube, M.: Deriving a Large Scale