디지털 라이브러리[ 검색결과 ]
다변량 시계열 이상 탐지에서의 센서 간 관계 유형을 반영하는 그래프 구조 학습
http://doi.org/10.5626/JOK.2024.51.3.236
수처리 시스템이나 스마트 팩토리 등 다양한 분야에서 시스템을 모니터링하기 위해 센서를 사용하여 데이터를 수집하고 있으며, 센서의 측정 데이터로 구성된 다변량 시계열을 분석하여 시스템의 이상 상황을 탐지할 수 있다. 이상 상황을 효율적으로 탐지하기 위해서는 센서 간 형성되는 관계에 대한 정보가 필요하지만, 일반적으로 이러한 정보를 알기 어렵다는 문제가 있다. 선행 연구에서는 이를 해결하기 위해 센서 데이터 간 관계로부터 센서 간 관계 구조를 학습하고 그래프 구조로 나타낸다. 그러나 이 과정에서 그래프 구조에 센서 간 관계 유무만을 반영하며 센서 간 관계의 유형까지는 고려하지 않는다. 본 논문에서는 센서 간의 관계 유형을 반영하여 그래프 구조를 학습하고, 이를 기반으로 다변량 시계열을 분석해 시스템의 이상 상황을 탐지한다. 또한 실험을 통해 다변량 시계열 이상 탐지의 그래프 구조 학습에 있어 센서간 관계 유형을 고려하는 것이 이상 탐지 성능을 향상함을 보인다.
k-배율 순위패턴매칭문제를 해결하는 알고리즘
http://doi.org/10.5626/JOK.2022.49.8.585
두 문자열의 길이가 같고 문자열 내에서 같은 위치의 문자들의 상대적 순위가 모두 동일하면 두 문자열은 순위동형이다. 순위패턴매칭문제는 길이가 n인 문자열 T와 길이가 m인 문자열 P가 주어졌을 때, P와 순위동형인 T의 모든 부분문자열을 찾는 문제이다. 순위패턴매칭은 주가지수 분석, 멜로디 분석과 같은 시계열데이터 분석에 활용될 수 있다. 본 논문에서는 순위패턴매칭을 확장한 k-배율 순위패턴매칭문제를 정의하고, 이 문제를 O(n+mlogm) 시간에 해결하는 알고리즘을 제시한다. 또한, O(n+m) 개의 스레드를 사용하여 O(m+k) 시간에 k-배율 순위패턴매칭문제를 해결하는 병렬알고리즘을 제시한다.
노드와 링크간의 상호작용을 동시에 반영한 그래프 어텐션 네트워크 기반 지식 그래프 임베딩
http://doi.org/10.5626/JOK.2022.49.7.555
지식 그래프는 실제 세계의 다양한 지식들을 노드와 링크 기반의 트리플 형태로 표현하는 지식구조로서 검색, 질의 응답 등의 여러 분야에서 유용하게 활용된다. 이런 지식 그래프는 불완전하며, 누락된 다른 관계들을 찾기 위해 노드와 링크를 저차원 벡터공간에 효과적으로 표현하는 임베딩 기법들이 많이 연구되었다. 최근 뉴럴 네트워크 기반의 지식 그래프 링크 예측 방법이 많이 연구되었지만, 기존 모델들은 노드에 대한 트리플의 중요도를 구할 때 노드와 링크를 독립적으로 고려하므로 트리플 내의 노드와 링크의 상호작용이 잘 반영하기 어렵다. 본 논문에서는 합성연산자를 이용하여 노드와 링크를 동시에 고려하여 트리플 단위의 중요도를 구하는 임베딩 방법을 제안하며 해당 모델이 지식 그래프 링크 예측에 우수한 성능을 보임을 증명한다.
Karp-Rabin 알고리즘을 이용한 순위다중패턴매칭 알고리즘의 병렬 구현
http://doi.org/10.5626/JOK.2021.48.3.249
길이가 같은 두 문자열은 각 문자의 상대적 순위가 모두 일치할 때 순위동형이라 한다. 순위다중패턴매칭문제는 텍스트 T(｜T｜=n)와 패턴들의 집합 P̃={P₁,P₂,...,Pk}가 주어졌을 때, P̃의 패턴들과 순위동형인 T의 모든 부분문자열을 찾는 문제이다. 패턴들 중 가장 짧은 패턴의 길이를 m, 가장 긴 패턴의 길이를 m̅, 모든 패턴들의 길이의 합을 M이라 하자. M∈mO(1)인 경우 Karp-Rabin 알고리즘을 이용하여 탐색단계를 평균적으로 O(n)시간에 수행하는 순위다중패턴매칭 알고리즘이 제시되었다. 본 논문에서는 Karp-Rabin 알고리즘을 이용하여 순위다중패턴매칭문제를 병렬적으로 해결하는 구현 방법을 제시한다. 제시하는 병렬 구현은 전처리단계를 O(M)개의 스레드를 사용하여 평균적으로 O(m̅)시간에 수행하며, 탐색단계를 O(n)개의 스레드를 사용하여 평균적으로 O(m)시간에 각각 수행한다. 무작위로 생성된 문자열에 대해 실험한 결과, n=1,000,000, k=1,000, m=5 일 때 본 논문에서 제시하는 병렬 구현이 기존의 순차알고리즘보다 약 201.5배 빠르게 수행되었다.
문자열 집합의 순위주기와 순위경계 병렬 계산
http://doi.org/10.5626/JOK.2019.46.12.1232
정수알파벳으로 구성된 같은 길이의 두 문자열이 주어졌을 때, 두 문자열의 상대적인 순위가 같으면 두 문자열은 순위동형이라 한다. 문자열 T(∣T∣=n)의 접두사 T[1..p](1≤p≤n)와 순위동형인 문자열이 T 에서 주기적으로 반복되어 나타나면, T[1..p]의 순위관계표현을 T의 순위주기라 한다. 만약 T의 접두사 T[1..p](1 ≤q ≤ n)와 접미사 T[n-q+1..n]이 서로 순위동형이면, T[1..p]의 순위관계표현을 T의 순위경계라 한다. T의 모든 순위주기, 순위경계의 길이는 Z-함수를 이용하여 각각 O(n log) 시간에 계산할 수 있다. 본 논문에서는 정수알파벳으로 구성된 길이가 n인 문자열들의 집합 Ŝ=｛S₁, S₂,..., Sr｝이 주어졌을 때, S의 모든 순위주기, 순위경계의 길이를 각각 O(rn)개의 스레드를 이용하여 O(n) 시간에 계산하는 Z-함수 기반 병렬알고리즘을 제시한다. 실험결과, r=1,000, n=10,000일 때, 다우존스지수 데이터에 대해 Ŝ의 모든 순위주기, 순위경계의 길이를 계산하는 병렬알고리즘은 각각 기존의 순차알고리즘보다 약 3.47배, 약 3.41배 빠르게 수행되었다.
재설정 가능한 모션 캡쳐를 위한 부분 동작 저작
http://doi.org/10.5626/JOK.2019.46.10.989
인간의 동작 인식과 관련된 연구는 기술의 발전과 함께 여러 분야에서 진행되고 있으며, 동작인식에 관한 수요는 날로 증가하는 추세에 있다. 모션 캡쳐에서는 실제 동작과 같은 자연스러운 움직임을 구현하기 위해서는 센서 또는 카메라를 이용하여 각 신체부위의 데이터를 취득 한다. 하지만 동작 데이터를 얻기 위해 매번 센서를 사용하거나, 약간의 동작 차이로 인해 다시 측정하는 과정은 비효율적이다. 또한, 보유하고 있는 데이터를 다른 사람에게 전달하거나, 수정하여 다른 동작으로 활용하기 위해서는 여러 문제점들이 해결되어야 한다.
본 연구에서는 동작인식 관련 연구의 추세를 살펴보며, 키 프레임 애니메이션을 이용한 기존의 동작 재현 방식과 라바노테이션을 이용한 동작 기록 방식의 특징을 분석하였다. 또한, 기존 방식의 단점을 보완하는 동작 저작 방식을 제안한다. 이미지 단위로 부분 동작의 패턴을 시각화하여 기록함으로써, 동작의 의미를 포함한 채로 다른 동작으로의 재구성이 가능하다.
사각망 순열패턴매칭 문제에 대한 병렬알고리즘
http://doi.org/10.5626/JOK.2019.46.4.299
사각망 순열패턴매칭은 텍스트 T(|T|= n)와 패턴 P(|P|= m)가 주어졌을 때, P와 순위동형인 T의 모든 사각망 부분서열을 찾는 문제이다. 본 논문에서는 사각망 순열패턴매칭문제를 해결하는 두 가지 병렬알고리즘을 제시한다. 먼저 O(n)개의 스레드를 사용하여 O(nm) 시간에 해결하는 병렬알고리즘을 제시한 후, O(nm)개의 스레드를 사용하여 O(n) 시간에 해결하는 병렬알고리즘을 제시한다. 다우존스 지수 데이터에 대한 실험결과, n = 36, 364 m = 30일 때, 순위통계트리를 사용한 순차알고리즘에 비해 첫번째 병렬알고리즘은 약 7.2배 빠른 수행시간을 보였고, 두 번째 병렬알고리즘은 약 20.6배 빠른 수행시간을 보였다.
2개의 q-그램에 대한 핑거프린트를 이용한 순위패턴매칭알고리즘
http://doi.org/10.5626/JOK.2018.45.11.1111
순위패턴매칭문제는 길이가 각각 n, m인 텍스트 T와 패턴 P가 주어졌을 때, P와 순위가 같은 T의 모든 부분문자열을 찾는 문제이다. 최근 q-그램의 핑거프린트를 이용한 O(nm + nqlogq +q!) 시간 순위패턴매칭 알고리즘이 제시되었다. 본 논문에서는 2개의 q-그램에 대한 핑거프린트를 이용하여 수행시간을 개선한 순위패턴매칭 알고리즘을 제시한다. 실험 결과, 본 논문에서 제시하는 알고리즘은 기존의 알고리즘보다 무작위로 생성된 T(n = 5,000,000)와 P(m = 5,10,15)에 대해 최대 약 12% 빠르게 수행된다. 또한 다우존스지수 데이터를 이용한 T(n = 34,658)와 T에서 무작위로 추출한 P(m = 5,10,15)에 대해 최대 약 10% 빠르게 수행된다.
Z-함수를 이용한 순위패턴매칭과 순위다중패턴매칭 병렬계산
http://doi.org/10.5626/JOK.2018.45.8.778
순위패턴매칭문제는 길이가 각각 n, m 인 텍스트 T와 패턴 P가 주어졌을 때, P와 순위동형인 T의 모든 부분문자열의 위치를 찾는 문제이다. 순위다중패턴매칭문제는 길이가 n인 텍스트 T와 패턴 집합 W={P₁, P₂,…, Pb}가 주어졌을 때 W의 패턴들과 순위동형인 T의 모든 부분문자열의 위치를 찾는 문제이다. 본 논문에서는 Z-함수를 기반으로, 순위패턴매칭문제를 O(n+hm)개의 스레드를 사용하여 O(m) 시간에 해결하는 병렬알고리즘과 순위다중패턴매칭문제를 O(b(n+M))개의 스레드를 사용하여 O(n+M) 시간에 해결하는 병렬알고리즘을 제시한다. 이때, h는 블록의 개수이며, M은 W에서 가장 긴 패턴의 길이를 나타낸다. 실험 결과, 순위패턴매칭문제에 대한 병렬알고리즘은 순차알고리즘보다 m=10, n=1,000,000일 때 약 71.2배 빠르게 수행되었다. 또한 순위다중패턴매칭문제에 대한 병렬알고리즘은 b=1,000, m=10, n=1,000일 때 순차알고리즘보다 약 12.2배 빠르게 수행되었다.
정수문자열의 δ-근사주기와 γ-근사주기를 찾는 병렬알고리즘
http://doi.org/10.5626/JOK.2017.44.8.760
반복적인 문자열은 데이터압축, 생물정보학 등 여러 분야에서 연구되어 왔다. 본 논문에서는 음악서열이나 주가지수와 같이 정수로 표현될 수 있는 문자열에 대한 반복에 대해 연구한다. 최근 정수문자열의 최소 δ-근사주기와 최소 γ-근사주기를 찾는 문제들이 소개되었고, 문자열의 길이가 n일 때, 두 문제를 각각 O(n²)시간에 해결하는 알고리즘들이 제시되었다. 본 논문에서는 위의 두 문제에 대해 각각 O(n²)개의 스레드를 이용하여 O(n) 시간에 해결하는 병렬알고리즘을 제시한다. 실험결과, n = 10,000일 때, 본 논문에서 제시하는 병렬알고리즘은 순차알고리즘보다 최소 δ-근사주기를 계산하는데 약 19.7배, 최소 γ-근사주기를 계산하는데 약 40.08배 빠른 수행시간을 보였다.
