초록 ▼

그래프 분류는 화합물, 소셜 네트워크, XML 문서 등과 같이 그래프로 모델링 된 데이터를 분류하는 기술이다. 그래프 분류를 위해 그래프의 구조적 정보를 반영하는 부분그래프들이 특징으로 널리 사용되고 있다. 그러나 그래프의 복잡한 구조와 알고리즘들의 높은 복잡성, 그리고 그래프 데이터베이스의 대용량화로 인하여 기존의 특징추출 기법이 좋은 성능을 보이지 못하고 있다. 또한, 대용량의 데이터가 축적되고 있음에도 불구하고, 데이터에 레이블을 붙이는 과정이 고비용이기 때문에 레이블 데이터가 적어 기존의 특징 추출 기법이 좋은 성능을 보이지

그래프 분류는 화합물, 소셜 네트워크, XML 문서 등과 같이 그래프로 모델링 된 데이터를 분류하는 기술이다. 그래프 분류를 위해 그래프의 구조적 정보를 반영하는 부분그래프들이 특징으로 널리 사용되고 있다. 그러나 그래프의 복잡한 구조와 알고리즘들의 높은 복잡성, 그리고 그래프 데이터베이스의 대용량화로 인하여 기존의 특징추출 기법이 좋은 성능을 보이지 못하고 있다. 또한, 대용량의 데이터가 축적되고 있음에도 불구하고, 데이터에 레이블을 붙이는 과정이 고비용이기 때문에 레이블 데이터가 적어 기존의 특징 추출 기법이 좋은 성능을 보이지 못하고 있다.
본 연구는 이와 같은 문제를 해결하기 위하여 대용량의 레이블되지 않은 인스턴스를 사용하여 충분한 훈련용 인스턴스를 생성함으로써 변별력이 있는 유용한 특징을 선택하는 부분감독기반 특징선택 알고리즘 및 프레임워크를 개발하였다. 제안하는 부분감독 특징선택 프레임워크는 분류력이 높은 동시발생 특징을 사용하며, 레이블 되지 않은 그래프들과 레이블 그래프들을 모두 활용하여 특징 집합을 선택한다. 또한 분류력이 높은 특징 집합을 선택하기 위하여 특징을 군집화하여 분류력이 유사한 특징들을 효과적으로 제거하였다. 그리고 대용량의 그래프 환경에서 부분감독 특징 선택 프레임워크가 활용될 수 있도록 수행시간을 개선하는 연구를 수행하였다.
[그래프 데이터 분류를 위한 부분감독기반 특징선택 기법 연구]
그래프 데이터베이스는 일반적으로 많은 수의 특징이 존재하며, 레이블 인스턴스를 생성하기 위하여 매우 고비용의 연산이 요구된다. 기존의 연구는 대부분 레이블 데이터로부터 빈발 부분그래프를 특징으로 사용하여 그래프 데이터를 분류하기 때문에 높은 성능을 갖지 못하였다. 본 연구에서는 소량의 레이블 데이터와 대량의 레이블 되지 않은 데이터를 활용하여 그래프 분류를 위한 특징선택 기법을 개발하였다. 이를 위하여 빈발 부분그래프보다 높은 분류 성능을 갖는 동시발생 빈발 부분그래프를 특징으로 사용하는 기법과 레이블 되지 않은 데이터도 동시에 활용하기 위한 분류력 측정 척도를 개발하였다. 또한 분류력이 유사한 특징들을 선택하는 것을 방지하기 위해 군집화 기반의 특징선택 기법을 개발하였다.
[대용량의 언레이블 데이터 환경에서 부분감독 기반 특징선택의 수행속도 개선 연구]
대용량의 레이블되지 않은 데이터베이스로부터 분류에 유용한 특징을 마이닝하기 위해서는 오랜 수행 시간이 요구된다. 더욱이 그래프데이터는 복잡한 구조적 특성 때문에 기존의 방법들로는 빠른 시간 내에 특징을 선택하기 어렵다. 본 연구에서는 특징선택 과정의 수행속도 개선을 위하여 가장 오랜 수행시간을 갖는 빈발 부분그래프 특징 추출 단계와 동시발생 빈발 부분그래프 특징 추출 단계의 수행속도를 개선하였다. 반복적으로 수행되는 빈발 부분그래프 마이닝 연산에서 같은 빈발 부분그래프들에 대한 중복 연산을 제거하여 수행속도를 크게 향상시켰다. 또한 동시발생 빈발 부분그래프를 마이닝하는 과정에서 분류력이 낮은 동시발생 빈발 부분그래프들에 대한 탐색공간을 제거하여 수행속도를 크게 향상시켰다.

목차 Contents

• 일반연구자지원사업 최종(결과)보고서 ... 1
• 목 차 ... 3
• Ⅰ. 연구결과 요약문 ... 4
• Ⅱ. 연구내용 및 결과 ... 5
• 1. 연구과제의 개요 ... 5
• 2. 국내외 기술개발 현황 ... 5
• 3. 연구수행 내용 및 결과 ... 6
• 4. 목표 달성도 및 관련 분야에의 기여도 ... 9
• 5. 연구결과의 활용계획 ... 9
• 6. 연구과정에서 수집한 해외과학기술정보 ... 9
• Ⅲ. 연구 성과 ... 10