[논문]연역적 유전자 알고리즘을 이용한 연관 단어 지식베이스의 최적화

고수정; 최준혁; 이정현

연역적 유전자 알고리즘을 이용한 연관 단어 지식베이스의 최적화
Optimization of Associative Word Knowledge Base using Apriori-Genetic Algorithm 원문보기

정보과학회논문지. Journal of KIISE. 소프트웨어 및 응용, v.28 no.8, 2001년, pp.560 - 569

고수정 (유니버셜 소프트 정보통신(주) 연구원) , 최준혁 (김포대학 컴퓨터계열) , 이정현 (인하대학교 전자계산공학과)

초록
AI-Helper

지식 기반 정보검색 시스템에서의 질의 확장은 단어간의 의미 관계를 고려한 지식베이스를 필요로 한다. 기존의 단순 마이닝 기법은 사용자의 선호도를 고려하지 않은 채 연관 단어를 추출하므로 재현율은 향상되나 정확도는 저하된다. 본 논문에서는 단어간의 의미 관게를 고려한 연관 단어 중에서 사용자가 선호하는 연관 단어만을 포함하는 정확도가 향상된 최적화된 연관 단어 지식베이스 구축을 위한 방법을 제안한다. 이를 위해 컴퓨터 분야의 웹문서를 8개의 클래스로 분류하고, 각 클래스별 웹문서에서 명사를 추출한다. 추출된 명사를 대상으로 Apriori 알고리즘을 이용하여 연관 단어를 추출하고, 유전자 알고리즘을 이용하여 사용자가 선호하지 않은 연관 단어를 지식베이스의 구축 대상에서 제외시킨다. 본 논문에서 제안된 Apriori 알고리즘과 유전자 알고리즘의 성능을 평가하기 위하여 Apriori 알고리즘은 상호 정보량과 Rocchio 알고리즘과 비교하며, 유전자 알고리즘은 TF.IDF를 이용한 단어 정제 방법과 비교한다.

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 논문에서는 지식 기반 정보검색 시스템에서의 질의 확장에 이용되는 지식베이스를 구축하기 위하여, 컴퓨터 분야의 웹문서를 수집하여 클래스별로 명사를 추출하고 Apriori 알고리즘을 이용하여 연관 단어를 추출하였다, 이를 대상으로 유전자 알고리즘을 적용하여, 사용자가 선 호하지 않는 연관 단어를 제외시킴으로써 클래스별로 최 적화된 연관 단어 지식베이스를 구축하였다. 본 논문에서 설계한 Apriori 알고리즘을 이용하여 클래스별 웹문서를 대상으로 연관 단어를 추출할 경우, 户膩 측정 방법에 의한 단어 분류의 성능에서 상호정보량에 의한 방법보다는 평균 5.

가설 설정

평가하는 기준은 평균 적합율 이 적합율 임계값과 같거나 크다면 진화를 종료하고 작 다면 재구성 단계부터 다시 진화를 반복한다. 본 논문에서는 적합율 임계값을 1로 하여 계산된 평균 적합율이 1보다 작다면 진화를 계속 진행한다.

제안 방법

추출된 단어를 한 글로 번역하여 300개의 연관 단어를 구성하였다. 마이닝 된 연관 단어가 이들 300개의 연관 단어에 포함되지 않을 경우 오류로 처리하였다. 정확도는 마이닝된 연관 단 어 중에서 오류로 처리된 연관 단어의 비율을 나타낸다.
본 논문에서는 Apriori 알고리즘을 사용하여 연관 단 어 지식베이스를 구축하였으며 유전자 알고리즘을 사용하여 구축된 지식베이스를 최적화하였다. 이를 평가하기 위해 Apriori 알고리즘은 연관 단어를 추출하는 기존의 방법인 상호정보량[14]과 Rocchio 알고리즘[8]과 비교 하였으며 유전자 알고리즘은 TF .
본 논문의 실험을 위해 컴퓨터 분야의 웹문서를 8개의 클래스로 분류한다. 실험 대상의 웹문서를 8개의 클래스 로 :분류한 기준은 야후, 한미르, 알타비스타 등 기존의 정보검색 엔진에서 이용하는 분류 통계를 따른 것이다.
여기서, B 는 F0 측정식에서 정확도에 대한 재현율의 상대적인 가중치를 나타내는 수치로 일 경우 정확도와 재현율 의 가중치가 같다. 본 실험에서는 8의 값을 L0로 설정 하여 클래스별로 분류 결과를 분석하였다.
본 논문의 실험을 위해 컴퓨터 분야의 웹문서를 8개의 클래스로 분류한다. 실험 대상의 웹문서를 8개의 클래스 로 :분류한 기준은 야후, 한미르, 알타비스타 등 기존의 정보검색 엔진에서 이용하는 분류 통계를 따른 것이다. 표 1은 그림 2에 속한 Bio아口의 MOR( )을 실행하였 을 경우에 대한 한 예이다.
마이닝된 결과에 대해 재현율과 정확도를 평가하는 기준은 영어 단어에 대한 시소러스인 WordNet[9] 을 사용하여 평가하였다. 평가를 위해WordNet에서 게임과 관련된 영어 단어의 동의어, 상의어, 하의어를 추출하였다. 추출된 단어를 한 글로 번역하여 300개의 연관 단어를 구성하였다.

대상 데이터

그림 3은 100개의 웹문서를 대상으로 신뢰도를 다양 하게 변화시켰을 때, 추출된 연관 단어에 대한 정확도와 재현율을 나타낸다. 100개의 웹문서는 본 논문이 실험을 위해 컴퓨터 분야의 웹문서를 8개의 클래스로 분류한 클래스 중에서 게임 클래스에 수집된 웹문서이다. 웹문 서 수집은 웹문서 수집기를 이용한다.
평가를 위해WordNet에서 게임과 관련된 영어 단어의 동의어, 상의어, 하의어를 추출하였다. 추출된 단어를 한 글로 번역하여 300개의 연관 단어를 구성하였다. 마이닝 된 연관 단어가 이들 300개의 연관 단어에 포함되지 않을 경우 오류로 처리하였다.
표 3의 연관 단어에서 부적절한, 연관 단어를 제거하기 위해서 사용자가 선정한 10개의 웹문서를 대상으로 Block3의 MOR0를 실행하여 표 4와 같이 명사를 추출한다.

데이터처리

이를 평가하기 위해 Apriori 알고리즘은 연관 단어를 추출하는 기존의 방법인 상호정보량[14]과 Rocchio 알고리즘[8]과 비교 하였으며 유전자 알고리즘은 TF . IDF를 이용한 텍스트 여과 방법U3]을 응용한 TFTDF를 이용한 단어 정제 방법과 비교하였다. TFTDF를 이용한 단어 정제 방법은 먼저 사용자가 선호하는 문서를 형태소 분석한 후 명사를 추출한다, 다음으로 추출된 명사를 대상으로 식 (5)를 사용하여 TFTDF값을 계산한다.
본 논문에서는 Apriori 알고리즘을 사용하여 연관 단 어 지식베이스를 구축하였으며 유전자 알고리즘을 사용하여 구축된 지식베이스를 최적화하였다. 이를 평가하기 위해 Apriori 알고리즘은 연관 단어를 추출하는 기존의 방법인 상호정보량[14]과 Rocchio 알고리즘[8]과 비교 하였으며 유전자 알고리즘은 TF . IDF를 이용한 텍스트 여과 방법U3]을 응용한 TFTDF를 이용한 단어 정제 방법과 비교하였다.

이론/모형

웹문 서 수집은 웹문서 수집기를 이용한다. 마이닝된 결과에 대해 재현율과 정확도를 평가하는 기준은 영어 단어에 대한 시소러스인 WordNet[9] 을 사용하여 평가하였다. 평가를 위해WordNet에서 게임과 관련된 영어 단어의 동의어, 상의어, 하의어를 추출하였다.
본 논문에서는 컴퓨■터 분야의 웹문서를 대상으로 각 문서를 8개의 클래스로 분류하였고 Apriori 알고리즘을 사용하여 연관 단어를 추출한 후 최적화를 목적으로 하는 유전자 알고리즘[12]을 적용한다. 유전자 알고리즘은 마이닝 기법에 의해 추출된 연관 단어 중에서 사용자가 선호하지 않는 연관 단어를 지식베이스 구축대상에서 제외시 킴으로써 지식베 이스를 최적 화한다.

성능/효과

53%로 TF . IDF를 사용한 단어 여과 방법에 의한 방법보다는 7.02% 높은 것으로 나타났다.
TFTDF를 이용한 단어 정제 방법은 먼저 사용자가 선호하는 문서를 형태소 분석한 후 명사를 추출한다, 다음으로 추출된 명사를 대상으로 식 (5)를 사용하여 TFTDF값을 계산한다. 계산 결과, 연 관 단어 지식베이스의 연관 단어에 속한 명사의 TF - IDF값이 1보다 작은 경우의 단어는 연관 단어 지식베이 스에서 제거한다.
그림 11에서 Apriori 알고리즘의 정확률은 91.50%로 Rocchio 알고리즘을 사용한 방법보다는 평균 0.04%, 상 호정보량을 사용한 방법보다는 19.34%의 향상된 정확도 를 나타낸다.
유전자 알고리즘에서는 개체의 성능을 다른 개체와 비교하기 위하여, 혹은 개체가 얼마나 유전자 알고리즘 이 적용되고 있는 가상의 환경에 잘 적응하고 있는지를 나타내는 척도로서 적합율을 모든 개체에 부여한다. 본 논문에서 선택한 적합율의 기준은 선택한 문서간에 유 사도가 높다면 적합율이 높은 것으로 유사도가 낮다면 적합율이 낮은 것으로 판정하였다. 문서간의 유사도[15] 는 유전자 알고리즘에서 사용되는 적합율은 비트간의 일치수를 사용하여 유사도를 구해야 하므로 식(3)의 Jaccard 방법 [5] 을 이용한다.
본 논문에서는 지식 기반 정보검색 시스템에서의 질의 확장에 이용되는 지식베이스를 구축하기 위하여, 컴퓨터 분야의 웹문서를 수집하여 클래스별로 명사를 추출하고 Apriori 알고리즘을 이용하여 연관 단어를 추출하였다, 이를 대상으로 유전자 알고리즘을 적용하여, 사용자가 선 호하지 않는 연관 단어를 제외시킴으로써 클래스별로 최 적화된 연관 단어 지식베이스를 구축하였다. 본 논문에서 설계한 Apriori 알고리즘을 이용하여 클래스별 웹문서를 대상으로 연관 단어를 추출할 경우, 户膩 측정 방법에 의한 단어 분류의 성능에서 상호정보량에 의한 방법보다는 평균 5.46%, Rocchio 알고리즘에 의한 방법보다는 평균 7.26% 높은 측정 결과를 얻을 수 있었다. 또한 Apriori 알고리즘에 의해 구축된 연관 단어 지식베이스를 정제하기 위한 유전자 알고리즘은 TF・IDF를 이용한 단어 여 과 방법보다 7.
IDF를 이용한 단어 여과 방법의 정확도와 재 현율을 식(6어〕대입하여 분석한 결과를 나타낸다. 유전 자 알고리즘을 이용한 방법과 TF TDF를 사용한 단어 여과 방법의 재현율은 각각 87.23%, 87.25%로 거의 홉 사한 결과를 나타내므로 정확도의 관계만을 보인다. 그림 13은 식(6)을 바탕으로 한 정확도의 관계를 나타낸다.
그림 12와 같이 3=1.。일 경우, 外에 의한 단어 분류 성능은 Apriori 알고리즘은 89%로, 상호정보량을 이용한 방법보다는 10.04%, Rocchio 알고리즘에 의한 방법 보다는 11.80% 높은 것으로 나타났다.

후속연구

향후, 복합 명사를 대상으로 Apriori-Genetic 알고리즘을 이용하여 클래스별 연관 단어 지식베이스를 구축 한다면 정보검색 시스템의 성능을 더욱 높일 수 있을 것으로 기대된다.

참고문헌 (15)

R. Agrawal and R. Srikant, 'Fast Algorithms for Mining Association Rules,' Proceedings of the 20th VLDB Conference, Santiago, Chile, 1994
R. Agrawal and T. Imielinski and A. Swami, 'Mining association rules between sets of items in large databases,' Proceedings of the 1993 ACM SIGMOD Conference, Washington DC, USA, May 1993
P. Brown and P. Della and R. Mercer, 'Classbased n-gram models of natural language,' Computational Linguistics, 18(4), pp.467-479, 1992
C. Clifton and R. Steinheiser, 'Data Mining on Text,' Proceedings of the Twenty-Second Annual International Computer Software & Applications Conference, 1998
M. Gondon, 'Probabilistic and genetic algorithms for document retrieval,' Communication of the ACM,31, pp.1208-1218, 1988

상세보기
V. Hatzivassiloglou and K. McKeown, 'Towards the automatic identification of adjectival scales: Clustering adjectives according to meaning.' Proceedings of the 31st Annual Meeting of the ACL, pp.172-182, 1993
K. Hyun-Jin and P. Jay-Duke and J. Myung-Gil and P. Dong-In. 'Clustering Korean Nouns Based On Syntactic Relations and Corpus Data,' Proceedings of the LASTED International Conference Artificial Intelligence and Soft Computing, 1998
T. Joachims, 'A Probabilistic Analysis of the Rocchio Algorithm with TFIDF for Text Categorization,' Proc. 14th International Conference on Machine Learning, 1997
H. IU and R. Setiono and H. Liu, 'Effective Data Mining Using Neural Networks,' Proceeding of the IEEE Trans. Knowledge and data engineering, V.8 N.6, pp.962-969, 1996

상세보기
Miller, George A., Martin Chodorow, Shari Landes, Claudia Leacock, and Robert G. Thomas, WordNet: An on-line Lexical database, International Journal of Lexicography, 3(4), pp. 235-244, 1990

상세보기
K. Miyashita and K. Sycara, 'Improving System Performance in CaseBased Iterative Optimization through Knowledge Filtering,' Proceedings of the International Joint Conference on Artificial Intelligence, 1995
T. Michael, Maching Learning, McGraw-Hill, pp. 249-273, 1997
D. W. Oard and G. Marchionini, 'A Conceptual Framework for Text Filtering,' Tehcnical Report CAR-TR-830, Human Computer Interaction Laboratory, University of Maryland at College Park, 1996
C. Plaunt and B.A.Norgard, 'An association based method for automatic indexing with a controlled vocabulary,' Journal of the American Society for Information Science, 49, pp.888-902. 1998

상세보기
한승희, 이재윤, '문헌 클러스터링을 위한 유사계수간의 연관성 측정', 제6회 한국정보관리학회 논문집, pp. 25-28, 1999

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증