본문 바로가기
HOME> 논문 > 논문 검색상세

학위논문 상세정보

Efficient approaches of constraint-based graph pattern mining : 제약사항 기반의 그래프 패턴 마이닝에 대한 효율적인 접근방법들 원문보기

  • 저자

    이강인

  • 학위수여기관

    세종대학교 일반대학원

  • 학위구분

    국내석사

  • 학과

    컴퓨터공학과

  • 지도교수

    윤은일

  • 발행년도

    2014

  • 총페이지

  • 키워드

    연관성 데이터 마이닝 빈발 패턴 마이닝 다중 최소 지지도 가중화 빈발 패턴 마이닝;

  • 언어

    eng

  • 원문 URL

    http://www.riss.kr/link?id=T13541031&outLink=K  

  • 초록

    빈발 그래프 패턴 마이닝은 대규모의 복잡한 그래프 데이터베이스로부터 의미 있는 패턴 정보를 마이닝 할 수 있다는 점에서 빈발 패턴 마이닝 분야 중 가장 흥미롭게 연구되고 있는 주제들 중 하나이다. 기존의 전통적인 데이터의 형태와 달리, 최근의 데이터는 항목 기반의 트렌젝션 데이터베이스나 순차 데이터베이스와 같은 기본적인 데이터 구조로는 제대로 표현할 수 없을 만큼 대규모화 되고 복잡해졌다. 이러한 문제를 극복하기 위해, 현실상의 거의 모든 데이터 형태를 표현할 수 있는 그래프 데이터 구조가 기존의 구조 대신 적용되기 시작했다. 따라서 기존의 빈발 패턴 마이닝 방법들은 이러한 그래프 데이터베이스를 처리하지 못하는 문제에 직면하게 되었고, 이런 이유로, 다양한 빈발 그래프 패턴 마이닝 방법들이 제안되었다. 반면에, 빈발 그래프 패턴 마이닝은 다음과 같은 문제를 가진다. 먼저 그래프 데이터베이스로부터의 빈발 그래프 패턴 추출은 생성되는 패턴 수의 차이로 인해 전통적인 데이터베이스로부터의 빈발 패턴 마이닝과 비교해 더욱 막대한 연산 오버헤드를 야기한다. 이러한 오버헤드는 사용자로부터 주어진 최소 지지도 임계값이 더욱 작아짐에 따라 기하급수적으로 증가한다. 더욱이, 추출되는 그래프 패턴들이 빈발할지라도, 모든 패턴이 실제적으로 유용한 것은 아니다. 다시 말해서, 어떤 그래프 패턴이 빈발할지라도, 그 패턴을 구성하는 요소들은 이들의 지지도 혹은 가중치 특성 면에서 확연히 다를 수 있다. 이 경우 이러한 그래프 패턴은 의미 없는 결과가 될 가능성이 더욱 높다. 기존의 빈발 패턴 마이닝 접근방법이 가지는 또 다른 문제는 오직 하나의 최소 지지도 임계값을 기준으로 마이닝 과정을 진행한다는 것이다. 현실상의 다수의 어플리케이션에서, 상대적으로 낮은 지지도를 갖는 그래프 패턴이 실제적으로 유용한 경우가 있을 수 있다. 그러나 전통적인 방법들은 “rare item problem”으로 불리는 이러한 문제를 다루지 못하는 문제점이 있다. 위에서 언급된 문제들을 해결하기 위해, 본 논문에서는 이러한 문제점들을 고려하며 빈발 그래프 패턴들을 마이닝하기 위한 효율적인 다양한 알고리즘들을 제안한다. 또한 본 논문의 총체적이고 실증적인 성능 실험 결과들을 통해, 제안되는 알고리즘들이 패턴 생성, 수행시간, 메모리 사용량 측면에서 뛰어난 성능을 발휘할 수 있음을 나타낸다.


    Frequent graph pattern mining is one of the most interesting fields in the frequent pattern mining area in that this approach can mine meaningful pattern information from large, complex graph databases. Unlike previous traditional data, recent data have become so large-scale and complicated that basic data structures such as item-based transactional database and sequential database forms cannot appropriately express them. To overcome such problem, graph data structures have been applied instead of the previous ones since they can express almost all data forms in the real world. Therefore, existing frequent pattern mining methods faced the problem that did not process such graph databases; for this reason, various frequent graph pattern mining methods have been proposed. Meanwhile, frequent graph pattern mining has the following problems. First, extracting frequent graph patterns from graph databases causes more enormous computational overheads compared to finding frequent patterns from traditional databases due to the difference of the number of generated patterns. Such overheads are exponentially increased as a user-given minimum support threshold becomes lower. Moreover, even though the extracted graph patterns are frequent, parts of them may become actually useless ones. In other words, although a certain graph pattern is frequent, elements composing the pattern can be sharply different in terms of their support or weight characteristics, where such graph pattern is more likely to be a meaningless one. Another problem of the previous frequent graph pattern mining approaches is that they mine graph patterns only based on a single minimum support threshold. In many of the real world applications, graph patterns with relatively low supports can be used as meaningful information, but these traditional methods do not deal with such issue, called a “rare item problem”. To solve the aforementioned problems, we propose a variety of efficient algorithms for mining frequent graph patterns considering the above issues. The results of comprehensive, empirical experiments in this thesis report that the proposed algorithms have outstanding performance in terms of pattern generation, runtime, and memory usage.


 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역