데이터 스트림 환경을 위한 유틸리티 기반 웹 방문 패턴의 마이닝 기법

아메드 파한,최호진,정병수 한국정보과학회 2010 데이타베이스 연구 Vol.26 No.2

Web access sequence mining can discover the frequently accessed web pages pursued by users. Utility‐based web access sequence mining handles non‐binary occurrences of web pages and extracts more useful knowledge from web logs. However, the existing utility‐based web access sequence mining approach considers web access sequences from the very beginning of web logs and therefore it is not suitable for mining data streams where the volume of data is huge and unbounded. At the same time, it cannot find the recent change of knowledge in data streams adaptively. The existing approach has many other limitations such as considering only forward references of web access sequences, suffers in the level‐wise candidate generation‐and‐test methodology, and needs several database scans, etc. In this paper, we propose a new approach for utility‐based web access sequence mining over data streams with a sliding window method. Our approach can not only handle large‐scale data but also efficiently discover the recently generated information from data streams. Moreover, it can solve the other limitations of the existing algorithms over data streams. Extensive performance analysis shows that our approach is very efficient and outperforms the existing algorithms. 유틸리티 기반 웹 방문 패턴의 마이닝은 웹 페이지의 중요도, 사용자가 웹 페이지에 머문 시간을 유틸리티로정의하여 유티릴티 값이 큰 방문 패턴을 탐색하는 마이닝 기법을 말한다. 기존의 유틸리티 기반 웹 방문 패턴의 마이닝 기법들은 여러 번의 데이터베이스 스캔을 필요로 하는 것으로 데이터 스트림과 같은 웹 로그 데이터를 처리하기에는 적절하지 못하였다. 본 논문에서는 슬라이딩 윈도우 모델을 기반으로 한 번의 데이터베이스스캔을 통하여 유틸리티 기반 웹 방문 패턴을 탐색하는 기법을 제안한다. 제안하는 기법은 대용량의 데이터에대하서도 좋은 확장성을 보이고 슬라이딩 윈도우 모델을 통하여 최근의 정보를 탐색할 수 있는 기법임을 여러실험을 통하여 중명한다.

단일 스캔을 통한 웹 방문 패턴의 탐색 기법

김낙민(Nakmin Kim),정병수(Byeong-Soo Jeong),아메드 파한(Chowdhury Farhan Ahmed) 한국정보과학회 2010 정보과학회논문지 : 데이타베이스 Vol.37 No.5

인터넷 사용의 급증과 더불어 보다 편리한 인터넷 서비스를 위한 여러 연구가 활발히 진행되어 왔다. 웹 로그 데이터로부터 빈번하게 발생되는 웹 페이지들의 방문 시퀀스를 탐색하는 기법 역시 효과적인 웹 사이트를 설계하기 위한 목적으로 많이 연구되어 왔다. 그러나 기존의 방법들은 모두 여러 번의 데이터베이스 스캔을 필요로 하는 방법으로 지속적으로 생성되는 웹 로그 데이터로부터 빠르게 실시간적으로 웹 페이지 방문 시퀀스를 탐색하기에는 많은 어려움이 있었다. 또한 점진적(incremental)이고 대화형식(interactive)의 탐색 기법 역시 지속적으로 생성되는 웹 로그 데이터를 처리하기 위하여 필요한 기능들이다. 본 논문에서는 지속적으로 생성되는 웹 로그 데이터로부터 단일 스캔을 통하여 빈번히 발생하는 웹 페이지 방문 시퀀스를 점진적이고 대화 형식적인 방법으로 탐색하는 방법을 제안한다. 제안하는 방법은 WTS(web traversal sequence)-트리 구조를 사용하며 다양한 실험을 통하여 기존의 방법들에 비해 성능적으로 우수하고 효과적인 방법임을 증명한다. Web access sequence mining can discover the frequently accessed web pages pursued by users. Utility-based web access sequence mining handles non-binary occurrences of web pages and extracts more useful knowledge from web logs. However, the existing utility-based web access sequence mining approach considers web access sequences from the very beginning of web logs and therefore it is not suitable for mining data streams where the volume of data is huge and unbounded. At the same time, it cannot find the recent change of knowledge in data streams adaptively. The existing approach has many other limitations such as considering only forward references of web access sequences, suffers in the level-wise candidate generation-and-test methodology, needs several database scans, etc. In this paper, we propose a new approach for high utility web access sequence mining over data streams with a sliding window method. Our approach can not only handle large-scale data but also efficiently discover the recently generated information from data streams. Moreover, it can solve the other limitations of the existing algorithm over data streams. Extensive performance analyses show that our approach is very efficient and outperforms the existing algorithm.

시계열 스트림 데이터 상에서 핸드헬드 디바이스를 위한 효율적인 스트림 시퀀스 매칭 알고리즘

문양세,노웅기,Moon Yang-Sae,Loh Woong-Kee 한국통신학회 2006 韓國通信學會論文誌 Vol.31 No.8B

핸드헬드 디바이스의 경우, 반복 작업에 대한 CPU 연산 최소화가 성능에 중요한 요소이다. 본 논문에서는 주식 데이터, 네트워크 트래픽, 센서 데이터 등의 시계열 스트림 데이터 상에서 유사 시퀀스를 효율적으로 찾아내는 핸드헬드 디바이스용 알고리즘을 제시한다. 이를 위하여, 우선 시계열 스트림 데이터 상에서 유사 시퀀스를 찾아내는 문제를 스트림 시퀀스 매칭(stream sequence matching)으로 정형적으로 정의한다. 다음으로, 기존의 서브시퀀스 매칭에서 사용했던 윈도우 구성법을 적용하여, 스트림 시퀀스 매칭을 효율적으로 처리하는 윈도우 기반 접근법을 제안한다. 그리고 이러한 윈도우 기반 접근법을 가능하게 하는 윈도우 MBR(window MBR) 개념을 제시하고, 이 개념을 사용하면 스트림 시퀀스 매칭을 정확하게 수행할 수 있음을 증명한다. 또한, 윈도우 기반 접근법에 기반한 두 가지 스트림 시퀀스 매칭 알고리즘을 제안한다. 마지막으로, 분석과 실험을 통해 제안한 알고리즘이 단순 접근법에 비해 CPU 연산을 크게 줄이고 성능을 향상시킴을 보인다. 이 같은 결과를 볼 때, 제안한 방법은 CPU 연산 능력이 부족한 핸드헬드 디바이스의 내장형 알고리즘으로 매우 적합하다고 사료된다. For the handhold devices, minimizing repetitive CPU operations such as multiplications is a major factor for their performances. In this paper, we propose efficient algorithms for finding similar sequences from streaming time-series data such as stock prices, network traffic data, and sensor network data. First, we formally define the problem of similar subsequence matching from streaming time-series data, which is called the stream sequence matching in this paper. Second, based on the window construction mechanism adopted by the previous subsequence matching algorithms, we present an efficient window-based approach that minimizes CPU operations required for stream sequence matching. Third, we propose a notion of window MBR and present two stream sequence matching algorithms based on the notion. Fourth, we formally prove correctness of the proposed algorithms. Finally, through a series of analyses and experiments, we show that our algorithms significantly outperform the naive algorithm. We believe that our window-based algorithms are excellent choices for embedded stream sequence matching in handhold devices.

발생 간격 기반 가중치 부여 기법을 활용한 데이터 스트림에서 가중치 순차패턴 탐색

장중혁(Joong Hyuk Chang) 한국지능정보시스템학회 2010 지능정보연구 Vol.16 No.3

Sequential pattern mining aims to discover interesting sequential patterns in a sequence database, and it is one of the essential data mining tasks widely used in various application fields such as Web access pattern analysis, customer purchase pattern analysis, and DNA sequence analysis. In general sequential pattern mining, only the generation order of data element in a sequence is considered, so that it can easily find simple sequential patterns, but has a limit to find more interesting sequential patterns being widely used in real world applications. One of the essential research topics to compensate the limit is a topic of weighted sequential pattern mining. In weighted sequential pattern mining, not only the generation order of data element but also its weight is considered to get more interesting sequential patterns. In recent, data has been increasingly taking the form of continuous data streams rather than finite stored data sets in various application fields, the database research community has begun focusing its attention on processing over data streams. The data stream is a massive unbounded sequence of data elements continuously generated at a rapid rate. In data stream processing, each data element should be examined at most once to analyze the data stream, and the memory usage for data stream analysis should be restricted finitely although new data elements are continuously generated in a data stream. Moreover, newly generated data elements should be processed as fast as possible to produce the up-to-date analysis result of a data stream, so that it can be instantly utilized upon request. To satisfy these requirements, data stream processing sacrifices the correctness of its analysis result by allowing some error. Considering the changes in the form of data generated in real world application fields, many researches have been actively performed to find various kinds of knowledgeembedded in data streams. They mainly focus on efficient mining of frequent itemsets and sequential patterns over data streams, which have been proven to be useful in conventional data mining for a finite data set. In addition, mining algorithms have also been proposed to efficiently reflect the changes of data streams over time into their mining results. However, they have been targeting on finding naively interesting patterns such as frequent patterns and simple sequential patterns, which are found intuitively, taking no interest in mining novel interesting patterns that express the characteristics of target data streams better. Therefore, it can be a valuable research topic in the field of mining data streams to define novel interesting patterns and develop a mining method finding the novel patterns, which will be effectively used to analyze recent data streams. This paper proposes a gap-based weighting approach for a sequential pattern and amining method of weighted sequential patterns over sequence data streams via the weighting approach. A gap-based weight of a sequential pattern can be computed from the gaps of data elements in the sequential pattern without any pre-defined weight information. That is, in the approach, the gaps of data elements in each sequential pattern as well as their generation orders are used to get the weight of the sequential pattern, therefore it can help to get more interesting and useful sequential patterns. Recently most of computer application fields generate data as a form of data streams rather than a finite data set. Considering the change of data, the proposed method is mainly focus on sequence data streams.

세미-스트림 서브시퀀스 매칭을 이용한 온라인 머신러닝

이종학,김홍지,이기훈 한국정보과학회 2020 데이타베이스 연구 Vol.36 No.2

Online machine learning is a machine learning method that continuously updates models using the real-time stream data. Although online machine learning research using the time-series data has been steadily increasing, little attention has been paid to a semi-stream operation. A semi-stream operation combines the real-time data with disk-based stored data, which is required to combine the stored data having a pattern similar to the stream data. In this paper, a semi-stream operation is applied to enhance the prediction performance of the online machine learning, and a subsequence matching operation is used to combine the stream data with the stored data. The experimental results using a real-world time series dataset show that the proposed method reduces the average mean square error (MSE) by 6.61% compared with the method using only the stream data. 온라인 머신러닝(online machine learning)은 실시간 스트림 데이터를 이용하여 지속적으로 모델을 갱신하는 머신러닝 방법이다. 최근 시계열 데이터를 이용한 온라인 머신러닝 연구가 꾸준히 증가하고 있지만, 세미-스트림(semi-stream) 연산을 적용한 연구는 아직 부족하다. 세미-스트림 연산은 스트림 데이터에 디스크에 저장된 데이터를 결합하는 연산으로, 스트림 데이터와 유사한 패턴을 가지는 데이터를 함께 결합하기 위해 필요한 연산이다. 본 논문에서는 시계열 데이터에 대한 온라인 머신러닝의 예측 성능을 높이기 위해 세미-스트림 연산을 적용하고, 두 데이터를 결합하는 조건으로 서브시퀀스 매칭(subsequence matching) 연산을 이용한다. 실제 시계열 데이터를 이용하여 실험한 결과, 스트림 데이터만을 이용하는 방법에 비해 제안한 방법의 평균제곱오차(MSE)가 평균 6.61% 감소함을 확인하였다.

순차 데이터 스트림에서 발생 간격 제한 조건을 활용한 빈발 순차 패턴 탐색

장중혁(Joong-Hyuk Chang) 한국컴퓨터정보학회 2010 韓國컴퓨터情報學會論文誌 Vol.15 No.9

순차 패턴 탐색은 데이터 마이닝의 주요 기법 중의 하나로서 웹기반 시스템, 전자상거래, 생물정보학 및 USN 환경 등과 같은 여러 컴퓨터 응용 분야에서 생성되는 데이터를 효율적으로 분석하기 위하여 널리 활용되고 있다. 한편 이들 응용 분야에서 생성되는 정보들은 근래들어 한정적인 데이터 집합이 아닌 구성요소가 지속적으로 생성되는 데이터 스트림 형태로 생성되고 있다. 이러한 상황을 고려하여 데이터 스트림에서 순차패턴 탐색에 대한 연구들도 활발히 진행되고 있다. 하지만 이전의 연구들은 주로 분석 대상 데이터 스트림에서 단순 순차패턴을 구하는 과정에서 마이닝 수행 시간이나 메모리 사용량 등을 줄이는데 초점을 맞추고 있으며, 따라서 해당 데이터 스트림의 특성을 효율적으로 표현할 수 있는 보다 중요하고 의미있는 패턴들을 탐색하기 위한 연구는 거의 진행되지 못하고 있다. 본 논문에서는 데이터 스트림에서 보다 의미있는 순차패턴을 탐색하기 위한 방법으로 구성요소의 발생 간격 제한 조건을 활용한 빈발 순차패턴 탐색 방법을 제안한다. 먼저 발생 간격 정의 기준 및 발생 간격제한 빈발 순차패턴의 개념을 제시하고, 이어서 데이터 스트림에서 발생 간격 제한 조건을 적용하여 빈발 순차패턴을 효율적으로 탐색할 수 있는 마이닝 방법을 제안한다. Sequential pattern mining is one of the essential data mining tasks, and it is widely used to analyze data generated in various application fields such as web-based applications, E-commerce, bioinformatics, and USN environments. Recently data generated in the application fields has been taking the form of continuous data streams rather than finite stored data sets. Considering the changes in the form of data, many researches have been actively performed to efficiently find sequential patterns over data streams. However, conventional researches focus on reducing processing time and memory usage in mining sequential patterns over a target data stream, so that a research on mining more interesting and useful sequential patterns that efficiently reflect the characteristics of the data stream has been attracting no attention. This paper proposes a mining method of sequential patterns over data streams with a gap constraint, which can help to find more interesting sequential patterns over the data streams. First, meanings of the gap for a sequential pattern and gap-constrained sequential patterns are defined, and subsequently a mining method for finding gap-constrained sequential patterns over a data stream is proposed.

시계열 스트림 시퀀스 매칭을 위한 효율적인 내장형 알고리즘

문양세,김진호 강원대학교 정보통신연구소 2006 정보통신논문지 Vol.10 No.-

For handheld devices, minimization of CPU operations is the most important factor in performance. In this paper, we propose the efficient algorithms that extract sequences similar to the given query sequence from the time-series stream sequence matching as the problem of finding similar to the given query sequence from the time-series stream such as network traffic data, stock prices, and sensor data. First, we formally define th stream sequence matching as the problem of finding similar sequences from the time-series stream. Second, we propose an efficient window-based approach by using the window construction mechanism of traditional subsequence matching methods. Third, we provide the notion of window MBR and propose two different stream sequence matching algorithms based on the notion. Fourth, we formally prove correctness of the proposed algorithms by presenting related theorems. Last, through extensive experiments, we show that our approach improves performance significantly compared with the naive approach. Overall, we believe that our methods would be very suitable for handheld devices as the embedded algorithms.

집합에 기반한 서브시퀀스 매칭 기법

여은지,이주원,임효상 한국정보과학회 2016 데이타베이스 연구 Vol.32 No.3

본 논문에서는 집합에 기반한 데이터스트림에서의 서브시퀀스 매칭 방법인 S-Match(Set-based subsequence Matching)를 제안하였다. 서브시퀀스 매칭은 데이터 시퀀스(data sequence) 중에서 질의 시퀀스(query sequence)와 유사한 서브시퀀스와 해당 서브시퀀스의 위치를 찾는 문제이다. S-Match는 다음의 두 가지 특징을 갖는다. 첫 번째로 사용자의 선호를 집합 개념을 고려하여 “선호 아이템 집합 시퀀스”로 표현하여 시간 개념을 고려하면서도 정확한 순서에 의한 불일치 문제를 해결하였다. 이때 아이템 집합 시퀀스 간의유사도를 측정하기 위해 유클리디안 거리를 집합으로 확장한 유클리디안 집합 거리를 제안하였다. 두 번째로추천 시스템(Recommendation System)의 핵심 요소인 유사 사용자 매칭 문제를 데이터스트림에서의 서브시퀀스 매칭 문제로 변환하여 다른 사용자의 최근 선호뿐만 아니라 과거의 모든 시점의 선호까지도 검색하였다. 그리고 S-Match를 수행할 때에 실제로 유사하지만 유사하지 않다고 판단되는 착오기각이 발생하지 않음을 증명하였다. 성능 평가 결과, 제안하는 S-Match가 실제 영화 평점 데이터에서 서브시퀀스 매칭을 수행하여 착오기각이 없이 정확하게 유사한 사용자를 찾아내는 것을 보였다. In this paper, we propose a method for set-based subsequence matching (S-Match) in data streams. Subsequence matching is a problem to find subsequences and their locations in data sequences which are similar to a query sequence. We first propose the preferred item set sequence which reflects the time concept of user preference. A preferred item set sequence is an ordered list of sets where each set collects preferred items within in a specific time interval. We then propose a similarity measurement between item set sequences, the Euclidean set distance, which extends Euclidian distance. Second, in order to find the similar user not only in current time but also in past time, we transforms the similar user matching problem into the similar subsequence matching problem. We proves that the method does not incur false dismissals which are actually similar but discarded in the results of the similar sequence matching. Through experiments with movie rating real data sets, we show that S-Match accurately finds similar users with a false dismissal.

Similar sequence matching supporting variable-length and variable-tolerance continuous queries on time-series data stream

Lim, H.S.,Whang, K.Y.,Moon, Y.S. North-Holland [etc ; Elsevier Science Ltd 2008 Information sciences Vol.178 No.6

We propose a new similar sequence matching method that efficiently supports variable-length and variable-tolerance continuous query sequences on time-series data stream. Earlier methods do not support variable lengths or variable tolerances adequately for continuous query sequences if there are too many query sequences registered to handle in main memory. To support variable-length query sequences, we use the window construction mechanism that divides long sequences into smaller windows for indexing and searching the sequences. To support variable-tolerance query sequences, we present a new notion of intervaled sequences whose individual entries are an interval of real numbers rather than a real number itself. We also propose a new similar sequence matching method based on these notions, and then, formally prove correctness of the method. In addition, we show that our method has the prematching characteristic, which finds future candidates of similar sequences in advance. Experimental results show that our method outperforms the naive one by 2.6-102.1 times and the existing methods in the literature by 1.4-9.8 times over the entire ranges of parameters tested when the query selectivities are low (<32%), which are practically useful in large database applications.

스트림 데이터 학습을 위한 예측적 컨볼루션 신경망

허민오(Min-Oh Heo),장병탁(Byoung-Tak Zhang) 한국정보과학회 2016 정보과학회 컴퓨팅의 실제 논문지 Vol.22 No.11

인터넷 상 데이터와 스마트 디바이스가 증가함에 따라 순차적으로 유입되는 스트림 형식의 데이터가 늘어나고 있다. 잠재적인 빅데이터인 스트림 데이터를 다루기 위해서는 온라인 학습이 가능해야 한다. 이에 본 고에서는 스트림 데이터 학습을 위한 새로운 모델인 예측적 컨볼루션 신경망과 온라인 학습방법을 제안한다. 이 모델은 탐지와 풀링을 반복하는 컨볼루션 연산을 통해 탐지 패턴을 계층화하여 상위계층이 될수록 긴 길이의 패턴의 정보를 다루도록 한다. 본 모델의 기초적 검증을 위해 스마트폰으로 2달간 수집한 GPS 데이터를 이산화하여 관측데이터로 삼았다. 이를 제안모델을 통해 학습하여 계층을 따라 추상화된 정보로부터 복원한 데이터와 관측데이터를 비교하여, 긴 시간의 패턴을 다루면서도 관측 수준의 데이터를 복원하는 것을 확인하였다. As information on the internet and the data from smart devices are growing, the amount of stream data is also increasing in the real world. The stream data, which is a potentially large data, requires online learnable models and algorithms. In this paper, we propose a novel class of models: predictive convolutional neural networks to be able to perform online learning. These models are designed to deal with longer patterns as the layers become higher due to layering convolutional operations: detection and max-pooling on the time axis. As a preliminary check of the concept, we chose two-month gathered GPS data sequence as an observation sequence. On learning them with the proposed method, we compared the original sequence and the regenerated sequence from the abstract information of the models. The result shows that the models can encode long-range patterns, and can generate a raw observation sequence within a low error.