최근 네트워크 기술 발전과 함께 IoT 및 소셜 네트워크 서비스의 활성화로 인해 많은 그래프 스트림 데이터가 생성되고 있다. 이와 같은 그래프 스트림에서 객체들 사이의 관계가 동적으로 변화함에 따라 그래프의 변화를 탐지하거나 분석하기 위한 연구들이 진행되고 있다. 본 논문에서는 그래프 스트림에서 이전 슬라이딩 윈도우에서 검출한 빈발 패턴에 대한 정보를 이용해 빈발 패턴을 점진적으로 검출하는 기법을 제안한다. 제안하는 기법은 이전 슬라이딩 윈도우에서 검출된 패턴이 앞으로 몇 슬라이딩 윈도우동안 빈발할지 또는 빈발하지 않을지를 계산하여 빈발 패턴 관리 테이블에 저장한다. 그리고 이 값을 통해 다음 슬라이딩 윈도우에서는 필요한 계산만 수행함으로써 전체 연산량을 감소시킨다. 또한 패턴 간에 간선을 통해 연결되어있는 것만 하나의 패턴으로 인식함으로써 더 유의미한 패턴만을 검출한다. 본 논문에서는 제안하는 기법의 우수함을 보이기 위해 여러 성능 평가를 진행하였다. 그래프 데이터의 크기가 커지고 슬라이딩 윈도우의 크기가 커질수록 중복되는 데이터가 증가되기 때문에 기존 기법보다 빠른 처리 속도를 나타낸다.
최근 네트워크 기술 발전과 함께 IoT 및 소셜 네트워크 서비스의 활성화로 인해 많은 그래프 스트림 데이터가 생성되고 있다. 이와 같은 그래프 스트림에서 객체들 사이의 관계가 동적으로 변화함에 따라 그래프의 변화를 탐지하거나 분석하기 위한 연구들이 진행되고 있다. 본 논문에서는 그래프 스트림에서 이전 슬라이딩 윈도우에서 검출한 빈발 패턴에 대한 정보를 이용해 빈발 패턴을 점진적으로 검출하는 기법을 제안한다. 제안하는 기법은 이전 슬라이딩 윈도우에서 검출된 패턴이 앞으로 몇 슬라이딩 윈도우동안 빈발할지 또는 빈발하지 않을지를 계산하여 빈발 패턴 관리 테이블에 저장한다. 그리고 이 값을 통해 다음 슬라이딩 윈도우에서는 필요한 계산만 수행함으로써 전체 연산량을 감소시킨다. 또한 패턴 간에 간선을 통해 연결되어있는 것만 하나의 패턴으로 인식함으로써 더 유의미한 패턴만을 검출한다. 본 논문에서는 제안하는 기법의 우수함을 보이기 위해 여러 성능 평가를 진행하였다. 그래프 데이터의 크기가 커지고 슬라이딩 윈도우의 크기가 커질수록 중복되는 데이터가 증가되기 때문에 기존 기법보다 빠른 처리 속도를 나타낸다.
Recently, with the advancement of network technologies, and the activation of IoT and social network services, many graph stream data have been generated. As the relationship between objects in the graph streams changes dynamically, studies have been conducting to detect or analyze the change of the...
Recently, with the advancement of network technologies, and the activation of IoT and social network services, many graph stream data have been generated. As the relationship between objects in the graph streams changes dynamically, studies have been conducting to detect or analyze the change of the graph. In this paper, we propose a scheme to incrementally detect frequent patterns by using frequent patterns information detected in previous sliding windows. The proposed scheme calculates values that represent whether the frequent patterns detected in previous sliding windows will be frequent in how many future silding windows. By using the values, the proposed scheme reduces the overall amount of computation by performing only necessary calculations in the next sliding window. In addition, only the patterns that are connected between the patterns are recognized as one pattern, so that only the more significant patterns are detected. We conduct various performance evaluations in order to show the superiority of the proposed scheme. The proposed scheme is faster than existing similar scheme when the number of duplicated data is large.
Recently, with the advancement of network technologies, and the activation of IoT and social network services, many graph stream data have been generated. As the relationship between objects in the graph streams changes dynamically, studies have been conducting to detect or analyze the change of the graph. In this paper, we propose a scheme to incrementally detect frequent patterns by using frequent patterns information detected in previous sliding windows. The proposed scheme calculates values that represent whether the frequent patterns detected in previous sliding windows will be frequent in how many future silding windows. By using the values, the proposed scheme reduces the overall amount of computation by performing only necessary calculations in the next sliding window. In addition, only the patterns that are connected between the patterns are recognized as one pattern, so that only the more significant patterns are detected. We conduct various performance evaluations in order to show the superiority of the proposed scheme. The proposed scheme is faster than existing similar scheme when the number of duplicated data is large.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
본 논문에서는 그래프 스트림에서 빈발 패턴 검출을 위한 점진적인 처리 기법을 제안하였다. 이렇게 함으로써 기존의 기법보다 빠르게 빈발 패턴 검출이 가능하기 때문에 더 많은 양의 데이터에 대해 분석이 가능하다.
본 논문에서는 실시간으로 입력되는 그래프 스트림 데이터에서 점진적으로 빈발 패턴을 검출하는 기법을 제안한다. 제안하는 기법은 윈도우가 이동할 때 이전 윈도우에서 분석한 결과를 재사용하여 연산량을 감소시킨다.
정확성 알고리즘은 모든 빈발 패턴을 정확하게 검출해 내는 것을 목적으로 한다. 따라서 유사 알고리즘에 비해 느리게 검출하지만 정확한 빈발 패턴만을 검출한 다.
가설 설정
따라서 어느 정도 데이터가 입력되었을 때, 분석한 후 삭제하여 메모리를 확보해야 다음에 입력될 데이터에서 분석이 가능하다. 두 번째는 시간에 따라 입력되는 데이터가 다르다는 점이다. 즉, 현재의 빈발 패턴이 나중엔 빈발 패턴이 아닐 수 있고, 그 반대의 경우도 발생한다.
slideNum은 FiS가 threshold 보다 클 때와 작을 때의 경우로 나누어 계산한다. 먼저 클 때에는 BatchCount 에 현재 슬라이딩 윈도우에서 가장 처음 배치를 삭제했을 때 남은 수를 계산하고 그 다음 새로 입력되는 배치가 모두 0이라고 가정하여 threshold를 넘는지 확인한다. 이 과정을 반복하여 몇 회 반복했을 때 BatchCount 가 threshold보다 작아지는지 계산하여 결과를 반환한다.
제안 방법
그리고 빈발 패턴을 검출할 때, 간단한 AND 연산을 이용하므로 빠르게 빈발 패턴 검출이 가능하다. 그리고 제안하는 기법은 시간에 따라 입력되는 데이터가 다른 특성을 고려하기 위해 슬라이딩 윈도우를 사용한다. 이 방법을 이용함으로써 여러 시간 동안의 그래프의 변화를 고려한 빈발 패턴 검출이 가능하다.
만약 두 개의 패턴이 떨어져있다면 이 두 패턴이 동시에 발생해도 하나의 패턴으로 보기 어렵다. 따라서 제안하는 기법에서는 연결성을 고려하여 더 의미 있는 빈발 패턴을 검출한다.
이 방법을 이용함으로써 여러 시간 동안의 그래프의 변화를 고려한 빈발 패턴 검출이 가능하다. 또한 간단한 연산을 통해 연결성을 고려하여 더 의미 있는 패턴을 검출한다.
[12]에서는 빈발 패턴 검출을 할 때 FPTree를 구축하지 않고 간단한 AND연산을 통해 빈발 패턴을 찾아내는 기법을 제안한다. 또한 간선간의 연결성을 고려하여 더 의미 있는 빈발 패턴을 검출하는 기법을 제안하였다. 여기서는 두가지 빈발 패턴 검출 기법을 제안한다.
제안하는 기법은 이전 슬라이딩 윈도우에서 발견한 빈발 패턴들을 빈발 패턴 관리 테이블에 관리하여 다음 빈발 패턴 검출할 때 활용함으로써 처리속도를 감소시킨다. 또한 연결성을 고려하여 유의미한 빈발 패턴을 검출하였다. 성능평가 결과 제안하는 기법은 그래프의 크기가 커지고, 슬라이딩 윈도우의 크기가 커질수록 슬라이딩 윈도우에서 중복된 부분이 많아지기 때문에 이런 중복 연산을 감소시킴으로써 기존 기법들보다 평균 55%정도 처리 시간이 감소하는 것을 확인하였다.
본 논문에서는 제안하는 기법의 우수성을 보이기 기존 기법[11][12]과의 성능평가를 수행하였다. [표 4]는 성능평가 환경을 보여준다.
이를 위해 빠르게 빈발 패턴을 검출하는 방법이 요구된다. 본 논문에서는 패턴의 발생 횟수를 합하여 빈발 여부를 확인하고 발생된 두 패턴을 AND 연산을 하여 다시 발생 횟수를 합하여 연속적으로 여러 간선으로 이루어진 빈발 패턴 검출한다. 여기서 AND연산과 발생횟수를 합하는 연산은 간단한 연산이기 때문에 빠른 패턴 검출이 가능하다.
임의의 그래프 스트림 데이터를 생성하고 배치의 크기, 윈도우 슬라이드의 크기, threshold 값 등 여러 가지 경우에 대해 평가하였다. 성능평가 환경은 Intel(R) Core(TM) i5-4440 3.10GHz 프로세서, 8G 메모리, 1TB디스크 환경으로 구성되고 Java로 구현하여 성능평가를 수행하였다.
또한 간선간의 연결성을 고려하여 더 의미 있는 빈발 패턴을 검출하는 기법을 제안하였다. 여기서는 두가지 빈발 패턴 검출 기법을 제안한다. 첫 번째 기법은 모든 빈발 패턴을 AND연산을 통해 검출한 후, 연결되지 않은 패턴을 제외시키는 방법이다.
하지만 슬라이딩 윈도우는 데이터가 중복되기 때문에 [11][12]과 같이 성능저하가 발생한다. 이 문제를 해결하기 위해 이전에 검출하였던 빈발패턴정보를 빈발 패턴 관리테이블에 저장하고, 이를 활용하여 새로운 빈발패턴을 검출하는 방법을 제안한다. 빈발 패턴 관리 테이블에는 기존에 검출된 패턴이 앞으로 몇 슬라이딩 윈도우동안 빈발할지 또는 빈발하지 않을지를 계산하여 저장하고, 이 값을 통해 다음 슬라이딩 윈도우에서는 필요한 계산만 수행함으로써 전체 연산량을 감소시킨다.
유사 알고리즘은 정확성 보다 빠르게 검출하는 것을 목적으로 하는 기법으로 대표적으로 FP-streaming 알고리즘[9]이 있다. 이 알고리즘에서는 그래프 스트림 데이터가 매시간마다 입력데이터의 양이 달라지는 것을 해결하기 위해 입력 시간 별로 빈발 패턴을 검출한다.
[표 4]는 성능평가 환경을 보여준다. 임의의 그래프 스트림 데이터를 생성하고 배치의 크기, 윈도우 슬라이드의 크기, threshold 값 등 여러 가지 경우에 대해 평가하였다. 성능평가 환경은 Intel(R) Core(TM) i5-4440 3.
제안하는 기법에서 빈발 패턴을 검출하기 위해서는 먼저 단일 간선에 대해 빈발 여부를 확인한다. 전처리 단계에서 만들어진 DSMatrix에서 각 간선 별로 하나의 배치에서의 발생 횟수를 계산하여 [표 1]의 빈발 패턴 관리 테이블의 FiB (Frequency in Batch)에 입력한다.
본 논문에서는 실시간으로 입력되는 그래프 스트림 데이터에서 점진적으로 빈발 패턴을 검출하는 기법을 제안한다. 제안하는 기법은 윈도우가 이동할 때 이전 윈도우에서 분석한 결과를 재사용하여 연산량을 감소시킨다. 제안하는 기법은 입력되는 그래프 스트림을 DSMatrix에 저장한 후, 간단한 AND 연산을 통해 빈발 패턴을 검출할 수 있다.
이런 빈발 패턴 검출은 센서 네트워크에서 이상감지, 소셜 네트워크에서 사용자간의 관계 및 정보를 이용한 인적 네트워크 분석 및 실시간 트랜드를 분석 등 다양한 분야에서 활용할 수 있다. 제안하는 기법은 이전 슬라이딩 윈도우에서 발견한 빈발 패턴들을 빈발 패턴 관리 테이블에 관리하여 다음 빈발 패턴 검출할 때 활용함으로써 처리속도를 감소시킨다. 또한 연결성을 고려하여 유의미한 빈발 패턴을 검출하였다.
제안하는 기법은 윈도우가 이동할 때 이전 윈도우에서 분석한 결과를 재사용하여 연산량을 감소시킨다. 제안하는 기법은 입력되는 그래프 스트림을 DSMatrix에 저장한 후, 간단한 AND 연산을 통해 빈발 패턴을 검출할 수 있다. 이 때, 검출된 패턴은 앞으로 몇 슬라이딩 윈도우동안 빈발할지 또는 빈발하지 않을지를 계산하여 따로 테이블에 관리한다.
[11]에서는 두 가지 정확성 빈발 패턴 검출 기법을 제안한다. 첫 번째는 그래프 스트림을 DSMatrix에 저장한 후, 모든 간선에 대해 FPTree를 구축한다. 이렇게 구축된 FPTree에서 재귀적으로 FPTree를 구축함으로써, 모든 빈발 패턴 검출이 가능하다.
대상 데이터
[그림 9]는 threshold값에 따른 처리 시간을 보여준다. 이 성능평가에서 그래프는 30만개로 이루어져 있고 1개 배치는 100개 그래프, 1개 슬라이딩 윈도우는 5개의 배치로 구성되어있다. 그림에서 보다시피 threshold 가 작아지면 처리속도가 급격하게 감소한다.
[그림 7]은 데이터 크기, 즉 간선의 수가 증가함에 따라 데이터의 처리 속도를 기존 기법과 비교한 실험 결과이다. 이 실험에서는 그래프의 간선의 개수를 변화시키며 성능평가를 하였고, 배치는 100개의 그래프로 구성되며, 윈도우 슬라이드는 5개의 배치로 이루어져있다. 또한 Threshold는 80%로 윈도우 슬라이드에서 400회 이상 등장한 패턴을 검출한다.
이론/모형
본 논문에서 빈발 패턴을 검출할 때 슬라이딩 윈도우 방식을 사용한다. 하지만 슬라이딩 윈도우는 데이터가 중복되기 때문에 [11][12]과 같이 성능저하가 발생한다.
본 논문에서는 한정적인 저장 공간을 효율적으로 사용하기 위해 DSMatrix를 사용한다. DSMatrix는 boolean 형식의 2차원 배열로 작은 크기로 많은 그래프를 저장할 수 있다.
따라서 어느 정도 데이터가 입력되었을 때, 분석한 후 삭제하여 메모리를 확보해야 다음에 입력될 데이터에서 분석이 가능하다. 이러한 특성을 고려하여, 제안하는 기법의 전처리 단계는 DSMatrix이라는 2차원 배열구조를 이용한다. DSMatrix 는 boolean 형식의 배열이기 때문에 기존 기법[10]에서 사용한 DSTree보다 적은 공간에 많은 데이터를 저장할 수 있다.
성능/효과
또한 연결성을 고려하여 유의미한 빈발 패턴을 검출하였다. 성능평가 결과 제안하는 기법은 그래프의 크기가 커지고, 슬라이딩 윈도우의 크기가 커질수록 슬라이딩 윈도우에서 중복된 부분이 많아지기 때문에 이런 중복 연산을 감소시킴으로써 기존 기법들보다 평균 55%정도 처리 시간이 감소하는 것을 확인하였다. 하지만 threshold 값이 작아지면서 빈발 패턴의 수가 지수 형태로 증가하게 되고, 그 결과로 성능이 저하되는 것이 발견되었다.
그림에서 하나의 슬라이딩 윈도우에 배치가 20개가 있을 때, [11]의 처리시간의 63%, [12]의 처리시간의 50%가 감소하는 것을 볼 수 있다. 이 결과를 통해 슬라이딩 윈도우의 개수가 증가할수록 제안하는 기법의 성능이 좋아진다는 것을 확인할 수 있다. 그 이유는 점진적 빈발 패턴 검출 기법을 사용할 때, slideNum의 값에 따라 앞으로 몇 번의 입력동안 계산하지 않아도 되는지가 결정되기 때문이다.
또한 Threshold는 80%로 윈도우 슬라이드에서 400회 이상 등장한 패턴을 검출한다. 이 실험에서 간선의 수가 적을 때에는 처리 시간이 크게 차이 나지 않지만, 간선의 수가 증가할수록 제안하는 기법의 처리 시간이 최대 60%까지 줄어드는 것을 볼 수 있다. 이러한 이유는 간선의 수가 증가함에 따라 중복되는 처리결과도 같이 증가하는데 기존 기법은 이런 중복되는 처리를 계속 수행하기 때문이다.
첫째, 스트림 데이터는 연속적으로 입력되기 때문에 어느 정도 데이터가 입력되었을 때, 분석한 후 삭제하여 메모리를 확보해야 다음에 입력될 데이터에서 분석이 가능하다.
후속연구
본 논문에서는 빈발 패턴을 테이블에 관리하기 때문에 빈발 패턴의 수가 많아질 때, 이를 관리하기 위하여 많은 메모리 공간이 필요하고, 스캔하는데 많은 시간이 소요된다는 한계가 있다. 따라서 향후 연구로 관리해야하는 패턴의 수가 증가되었을 때 인덱스를 이용하여 스캔하는 비용을 줄이고, 필요한 패턴에 직접 접근하기 위한 인덱스를 사용하는 기법에 대해 연구할 예정이다. 또한 임의로 생성한 데이터를 사용하여 실험평가를 진행하였기 때문에, 데이터의 신뢰도를 향상시키기 위하여 실제 데이터를 이용하여 더 다양한 실험 평가를 진행할 예정이다.
따라서 향후 연구로 관리해야하는 패턴의 수가 증가되었을 때 인덱스를 이용하여 스캔하는 비용을 줄이고, 필요한 패턴에 직접 접근하기 위한 인덱스를 사용하는 기법에 대해 연구할 예정이다. 또한 임의로 생성한 데이터를 사용하여 실험평가를 진행하였기 때문에, 데이터의 신뢰도를 향상시키기 위하여 실제 데이터를 이용하여 더 다양한 실험 평가를 진행할 예정이다.
하지만 threshold 값이 작아지면서 빈발 패턴의 수가 지수 형태로 증가하게 되고, 그 결과로 성능이 저하되는 것이 발견되었다. 본 논문에서는 빈발 패턴을 테이블에 관리하기 때문에 빈발 패턴의 수가 많아질 때, 이를 관리하기 위하여 많은 메모리 공간이 필요하고, 스캔하는데 많은 시간이 소요된다는 한계가 있다. 따라서 향후 연구로 관리해야하는 패턴의 수가 증가되었을 때 인덱스를 이용하여 스캔하는 비용을 줄이고, 필요한 패턴에 직접 접근하기 위한 인덱스를 사용하는 기법에 대해 연구할 예정이다.
질의응답
핵심어
질문
논문에서 추출한 답변
빈발 패턴 검출의 활용의 예로는 무엇이 있는가?
빈발 패턴 검출은 그래프 스트 림에서 자주 사용되는 분석 기법 중 하나로 특정 기간 동안 자주 발생한 서브그래프를 검출하는 방법이다 [9-12]. 예를 들어, 스마트 팩토리에서는 고장 예측을 위해 전조 현상들에 대한 패턴을 감지한다. 소셜 네트 워크에서는 사용자간에 친밀 관계를 분석하기 위해서 사용자들 사이에 정보 교류 패턴을 판별한다[13].
FP-Streaming (Frequent Pattern-Streaming)기법이 제안된 이유는 무엇인가?
최근 그래프 스트림에서 빈발 패턴 검출에 대한 활용이 증감됨에 따라 다양한 연구가 활발히 진행되고 있다 [9-17]. [9]에서는 시간에 따라 입력되는 데이터의 양이 달라지는 것을 해결하기 위해 FP-Streaming (Frequent Pattern-Streaming)기법을 제안하였다. [10] 에서는 그래프 스트림을 DSTree (Data Stream Tree) 라는 구조를 제안함으로써, 빈발 패턴 검출을 할 때 효율적으로 데이터를 메모리에 저장한다.
빈발 패턴 검출이란 무엇인가?
그래프에서 객체들 사이의 관계가 동적으로 변화함에 따라 그래프의 변화를 탐지하거나 분석하기 위한 연구들이 진행되고 있다. 빈발 패턴 검출은 그래프 스트 림에서 자주 사용되는 분석 기법 중 하나로 특정 기간 동안 자주 발생한 서브그래프를 검출하는 방법이다 [9-12]. 예를 들어, 스마트 팩토리에서는 고장 예측을 위해 전조 현상들에 대한 패턴을 감지한다.
참고문헌 (17)
임종태, 복경수, 유재수, "대용량 그래프 환경에서 스카이라인을 이용한 서브 그래프 유사도 측정 기법," 한국콘텐츠학회 종합학술대회, pp.47-48, 2017.
유병국, 김순홍, "소셜네트워크 분석을 통한 마케팅 전략," 한국콘텐츠학회논문지, 제13권, 제5호, pp.396-407, 2013.
A. Cuzzocrea, F. Furfaro, G. M. Mazzeo, and D. Sacca, "A grid framework for approximate aggregate query answering on summarized sensor network readings," Proc. OTM Workshops, pp.144-153, 2004.
A. Fariha, C. F. Ahmed, C. K. Leung, S. M. Abdullah, and L. Cao, "Mining frequent patterns from human interactions in meetings using directed acyclic graphs," Proc. Pacific-Asia Conference on Knowledge Discovery and Data Mining, Springer, pp.38-49, 2013.
F. Jiang and C. K. Leung, "Mining interesting "following" patterns from social networks," Proc. International Conference on Data Warehousing and Knowledge Discovery, Springer, pp.308-319, 2014.
S. K. Tanbeer, F. Jiang, C. K. Leung, R. K. MacKinnon, and I. J. M. Medina, "Finding groups of friends who are significant across multiple domains in social networks," Proc. International Conference on Computational Aspects of Social Networks, pp.21-26, 2013.
한진수, 조중권, 최도진, 임종태, 복경수, 유재수, "부하 분산을 위한 정점 절단 기반의 그래프 스트림 분할 기법," 한국정보과학회 학술발표논문, pp.206-208, 2017.
강필성, "사물인터넷과 빅데이터 분석 기반의 스마트공장 구현 사례 및 시사점," 한국정보화진흥원, Near & Future, Vol.20, pp.25-35, 2016.
C. Giannella, J. Han, J. Pei, X. Yan, and P. S. Yu, "Mining frequent patterns in data streams at multiple time granularities," Next generation data mining, pp.191-212, 2003.
C. K. Leung and Q. I. Khan, "DSTree: A Tree Structure for the Mining of Frequent Sets from Data Streams," Proc. International Conference on Data Mining, pp.928-932, 2006.
P. Braun, J. J. Cameron, A. Cuzzocrea, F. Jiang, and C. K. Leung, "Effectively and Efficiently Mining Frequent Patterns from Dense Graph Streams on Disk," Proc. International Conference in Knowledge Based and Intelligent Information and Engineering Systems, pp.338-347, 2014.
A. Cuzzocrea, Z. Han, F. Jiang, C. K. Leung, and H. Zhang, "Edge-based Mining of Frequent Subgraphs from Graph Streams," International Conference in Knowledge Based and Intelligent Information and Engineering Systems, pp.573-582, 2015.
S. K. Tanbeer, C. K. Leung, and J. J. Cameron, "Interactive Mining of Strong Friends from Social Networks and its Applications in E-Commerce," Journal of Organizational Computing and Electronic Commerce, Vol.24, No.2-3, pp.157-173, 2014.
C. C. Aggarwal, Y. Li, P. S. Yu, and R. Jin, "On dense pattern mining in graph streams," Proceedings of the VLDB Endowment, Vol.3, No.1-2, pp.975-984, 2010.
A. Bifet, G. Holmes, B. Pfahringer, and R. Gavalda, "Mining frequent closed graphs on evolving data streams," Proc. ACM SIGKDD international conference on Knowledge discovery and data mining, pp.591-599, 2011.
E. Valari, M. Kontaki, and A. N. Papadopoulos, "Discovery of top-k dense subgraphs in dynamic graph collections," Proc. International Conference on Scientific and Statistical Database Management, Springer, pp.213-230, 2012.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.