디지털 라이브러리[ 검색결과 ]
맵리듀스 기반 상향식 최대 밀도 부분그래프 탐색 알고리즘
최대 밀도 부분 그래프는 소셜 네트워크에서 사용자들이 속한 특정 커뮤니티나 사용자들의 공통 관심사를 나타내기에, 최대 밀도 부분 그래프를 찾는 연구가 다수 있었다. 그러나 기존의 연구들은 단일한 최고 밀도 부분 그래프를 찾는다는 문제점이 있었다. 이 연구에서는 주어진 노드에서 시작하여, 인접하는 노드 중에 연결수(degree)가 가장 높은 노드를 추가하는 방식을 사용한 최고 밀도 부분 그래프를 찾는 상향식 휴리스틱 알고리즘을 제안한다. 이에 따라, 병렬 처리에 용이하게 하였고, 이를 맵리듀스 프레임워크 상에서 병렬 알고리즘으로 구현하였다. 다양한 그래프 데이터로 실험결과 이전 연구와 비교하여 조기에 최고 밀도 부분 그래프를 찾아냄을 보였다. 또한 다양한 다수의 노드가 주어졌을 때에도 효과적으로 동작함을 보였다.
대용량 그래프 압축과 마이닝을 위한 그래프 정점 재배치 분산 알고리즘
수십억 개 간선들로 구성된 대용량 그래프를 어떻게 효과적으로 압축할 수 있을까? 정점 재배치를 통해 인접 행렬의 0이 아닌 값들을 집중시키면 그래프를 효율적으로 압축할 수 있을 뿐 아니라 페이지랭크 등 여러 그래프 마이닝 알고리즘의 수행 속도를 개선할 수 있다. 최신 정점 재배치 기법인 SlashBurn 은 실세계 네트워크의 멱법칙 특성을 활용하는 실세계 그래프에 효과적인 방법이다. 하지만 단일 머신 기반으로 설계되어 대용량 그래프에 대해 처리 속도가 현저히 느려지거나 적용이 불가능한 한계가 있다. 본 논문에서는 이러한 한계를 극복하기 위한 분산 SlashBurn을 제안한다. 분산 SlashBurn은 대규모의 정점재배치 프로세스를 분산 처리하여 대용량 그래프를 기존 방법보다 훨씬 빠르고 확장성 있게 처리한다. 대용량 실세계 그래프들에 대한 실험 결과, 분산 SlashBurn은 단일 머신 SlashBurn보다 45배 이상 빠르게 동작하였고, 16배 이상 큰 그래프를 처리할 수 있었다.
사물인터넷 환경에서 지리적 응집도를 고려한 동적 서비스 검색방법
사물인터넷 환경에서 사용자가 자신의 태스크를 수행하기 위해서는, 태스크 수행에 사용되는 서비스들을 제공하는 사물인터넷 기기를 검색하는 과정이 필요하다. 사용자가 필요로 하는 태스크는 기술이 발전함에 따라 더 많은 서비스들이 복합적으로 결합된 형태로 변하는 중이다. 이 때 태스크를 구성하는 많은 수의 서비스들이 사용자 태스크를 효과적으로 수행하기 위해서는 검색된 사물인터넷 기기들이 지리적으로 서로 인접하여 위치해야 한다. 또한 동적으로 변화하는 사물인터넷 환경의 특징을 고려하여 안정적으로 서비스 검색이 이루어져야 한다. 이러한 문제를 해결하기 위해 본 논문에서는 동적 모바일 애드혹 네트워크 환경에서 지리적 응집력을 갖는 두 가지의 서비스 검색 방법을 제안하고, 지리적 응집도를 바탕으로 기존의 서비스 검색 방법과 비교, 평가하였다.
Min-Hash를 이용한 효율적인 대용량 그래프 클러스터링 기법
그래프 클러스터링은 서로 유사한 특성을 갖는 정점들을 동일한 클러스터로 묶는 기법으로 그래프 데이터를 분석하고 그 특성을 파악하는데 폭넓게 사용된다. 최근 소셜 네트워크 서비스와 월드 와이드 웹, 텔레폰 네트워크 등의 다양한 응용분야에서 크기가 큰 대용량 그래프 데이터가 생성되고 있다. 이에 따라서 대용량 그래프 데이터를 효율적으로 처리하는 클러스터링 기법의 중요성이 증가하고 있다. 본 논문에서는 대용량 그래프 데이터의 클러스터들을 효율적으로 생성하는 클러스터링 알고리즘을 제안한다. 우리의 제안 기법은 그래프 내의 클러스터들 간의 유사도를 Min-Hash를 이용하여 효과적으로 추정하고 계산된 유사도에 따라서 클러스터들을 생성한다. 실세계 데이터를 이용한 실험에서 우리는 본 논문에서 제안하는 기법과 기존 그래프 클러스터링 기법들과 비교하여 제안기법의 효율성을 보였다.
컴퓨터 게임의 NPC를 위한 적응적 경로 이동의 구현
컴퓨터 게임에서 NPC(NonPlayer Character)의 획일적인 경로 이동은 게임 플레이어의 흥미를 떨어뜨리는 요인이 된다. 웨이포인트 그래프를 이용한 길찾기의 경우, NPC가 지정된 위치만을 이용하여 이동하게 되므로 이 문제점은 더욱 두드러져 보인다. 본 논문에서는 이 문제의 해결을 위해 플레이어의 이동을 관찰하여 NPC가 적응적으로 경로를 계획할 수 있도록 하는 방법을 제안한다. 제안하는 방법은 우선, 플레이어 이동의 포인트 지정을 관찰하여 웨이포인트를 동적으로 수정하고, 수정된 웨이포인트들을 NPC의 경로 탐색에 이용하는 것이다. 또한 플레이어의 지형 선호도를 학습하여 NPC별로 특성에 맞는 경로를 계획하기 위한 알고리즘을 제안한다. 유니티 4.0으로 제작된 RPG(Role Playing Game) 게임으로 구현된 알고리즘을 시뮬레이션하여 NPC 이동이 다양해지고 플레이어의 이동과 유사한 방향으로 개선됨을 확인한다.
한국어 어휘의미망(UWordMap)을 이용한 동형이의어 분별 개선
한국어처리 분야에서 동형이의어 분별은 의미처리를 위해서는 매우 중요하고 오랫동안 연구되어온 주제이다. 최근에 말뭉치를 학습하는 기계학습 방법이 정확률과 속도면에서 좋은 결과를 보이고 있으며, 미학습 어절을 처리하기 위해 어휘의미망을 이용한 지식기반 방법도 연구되고 있다. 본 논문은 말뭉치를 학습한 기계학습 방법에 어휘의미망과 함께 사용하는 방법을 제시한다. 이 방법의 기본 전략은 하위범주화 정보를 말뭉치화하여서 기존 말뭉치와 함께 학습시키고, 동형이의어 태깅 시점에서 분석 대상 명사의 상위어를 찾아서 학습정보와 같이 사용하는 것이다. 이 방법의 효과를 확인하기 위해 세종말뭉치와 UWordMap으로 실험을 하였으며, 정확률이 96.51%에서 96.52%로 미미하지만 상승하는 것을 확인하였다.
준지도 학습에서 꼭지점 중요도를 고려한 레이블 추론
준지도 학습은 기계 학습의 한 분야로서, 레이블된 데이터와 레이블되지 않은 데이터 모두를 사용하여 모델을 학습함으로써 지도 학습에 비해 예측 정확도를 높일 수 있다. 최근 각광받고 있는 그래프 기반 준지도 학습은 입력 데이터를 그래프의 형태로 변환하는 그래프 구축 단계와 이를 사용하여 레이블되지 않은 데이터의 레이블을 예측하는 레이블 추론 단계로 나뉜다. 이 추론은 준지도 학습에서의 평활도 가정을 기본으로 한다. 본 연구에서는 추가로 각 꼭지점 중요도를 결합함으로써 개선된 레이블 추론알고리즘을 제안한다. 이와 함께 알고리즘의 수렴성을 증명하고, 또한 실험을 통해 알고리즘의 우수성을 검증하였다.
효과적인 모델 기반 안드로이드 GUI 테스팅을 위한 GUI 상태 비교 기법
안드로이드(Android) 어플리케이션(앱)의 신뢰성과 사용성 검증을 위해, 앱의 기능 검사와 크래쉬(Crash) 탐지 등을 위한 다양한 GUI 테스팅(Graphical User Interface Testing) 기법이 널리 사용되고 있다. 그 중 모델 기반(Model-based) GUI 테스팅 기법은 GUI 모델을 이용해 테스트 케이스를 생성하기 때문에, 기법의 유효성(Effectiveness)은 기반 모델의 정확도에 의존적이다. 따라서 모델 기반 기법의 유효성 향상을 위해서는 테스트 대상 앱의 행위를 충분히 반영할 수 있는 모델 생성 기법이 필요하며, 이를 위해 본 연구에서는 GUI 상태를 정밀하게 구분하는 계층적 화면 비교 기법을 통해 테스팅의 유효성과 효율성을 향상시키고자 한다. 또한, 기존 연구 기법과의 비교 실험을 통해 제안 기법이 유효한 모델의 효율적 생성을 가능하게 함을 확인함으로써, 모델 기반 안드로이드 GUI 테스팅의 성능 향상 가능성을 제시한다.
구면 파노라마 영상에서의 평면 패턴의 기하 변환 추정
핀홀 카메라 모델을 가정하는 기존 영상처리 기술의 평면 대 평면 간 기하 변환은 구면 파노라마 영상에서의 픽셀 좌표에는 적용될 수 없다. 본 논문에서는 구면 파노라마 영상과 평면 영상의 특징점정합 쌍이 주어졌을 때 두 영상에 포함된 평면 기하 변환 관계를 추정하는 방법을 제안한다. 정합된 특징점들로부터 평면 패턴의 위도 변화, 경도 변화, 회전 변화, 크기 변화 인자를 모두 구하여 기하 변환을 추정하는 것이 본 논문에서 제안하는 방법의 목적이다. 평면 영상을 구면 파노라마 영상에 투영하게 될 경우 두 번의 비선형 좌표계 변환이 포함되어 기하 변환식이 복잡하다. 제안하는 방법은 좌표 변환뿐만 아니라 변환에 내재된 각 인자들을 모두 알아낼 수 있는 것이 장점이다. 실험 결과 제안하는 방법은 약 1%의 오차 수준에서 기하 변환을 추정하였고 위도 및 회전 등 주요 변형 요인에 영향을 거의 받지 않았다.
인메모리 기반 병렬 컴퓨팅 그래프 구조를 이용한 대용량 RDFS 추론
전명중, 소치승, 바트셀렘, 김강필, 김진, 홍진영, 박영택
근래에 들어 풍부한 지식베이스를 구축하기 위한 대용량 RDFS 추론에 대한 관심이 높아지면서 기존의 단일 머신으로는 대용량 데이터의 추론 성능을 향상시키기에 한계가 있다. 그래서 분산 환경에서 의 RDFS 추론 엔진 개발이 활발히 연구되고 있다. 하지만 기존의 분산 환경 엔진은 실시간 처리가 불가능 하며 구현이 어렵고 반복 작업에 취약하다. 본 논문에서는 이러한 문제를 극복하기 위해 병렬 그래프 구조 를 사용한 인-메모리 분산 추론 엔진 구축 방법을 제안한다. 트리플 형태의 온톨로지는 기본적으로 그래프 구조를 가지고 있으므로 그래프 구조 기반의 추론 엔진을 설계하는 것이 직관적이다. 또한 그래프 구조를 활용하는 오퍼레이터를 활용하여 RDFS 추론 규칙을 구현함으로써 기존의 데이터 관점과 달리 그래프 구조의 관점에서 설계할 수 있다. 본 논문에서 제안한 추론 엔진을 평가하기 위해 LUBM1000(1억 3천 3백만 트리플, 17.9GB), LUBM3000(4억 1천 3백만 트리플, 54.3GB)에 대해 추론 속도를 실험을 하였으며 실 험결과, 비-인메모리 분산 추론 엔진보다 약 10배 정도 빠른 추론 성능을 보였다.
