일반적인 순차패턴 마이닝에서는 분석 대상데이터 집합에 포함되는 구성요소의 발생 순서만을 고려하며, 따라서 단순 순차패턴은 쉽게 찾을 수 있는 반면 실제 응용 분야에서 널리 활용될 수 있는 관심도가 큰 순차패턴을 탐색하는데 한계가 있다. 이러한 단점을 보완하기 위한 대표적인 연구 주제들 중의 하나가 가중치 순차패턴 탐색이다. 가중치 순차패턴 탐색에서는 관심도가 큰 순차패턴을 얻기 위해서 구성요소의 단순 발생 순서 뿐만 아니라 구성요소의 가중치를 추가로 고려한다. 본 논문에서는 발생 간격에 기반 한 순차패턴 가중치 부여 기법 및 이를 활용한 순차 데이터 스트림에 대한 가중치 순차패턴 탐색 방법을 제안한다. 발생 간격 기반 가중치는 사전에 정의된 별도의 가중치 정보를 필요로 하지 않으며 순차정보를 구성하는 구성요소들의 발생 간격으로부터 구해진다. 즉, 순차패턴의 가중치를 구하는데 있어서 구성요소의 발생순서와 더불어 이들의 발생 간격을 고려하며, 따라서 보다 관심도가 크고 유용한 순차패턴을 얻는데 도움이 된다. 한편, 근래 대부분의 컴퓨터 응용 분야에서는 한정적인 데이터 집합 형태가 아닌 데이터 스트림 형태로 정보를 발생시키고 있다. 이와 같은 데이터 생성 환경의 변화를 고려하여 본 논문에서는 순차 데이터 스트림을 마이닝 대상으로 고려하였다.
일반적인 순차패턴 마이닝에서는 분석 대상 데이터 집합에 포함되는 구성요소의 발생 순서만을 고려하며, 따라서 단순 순차패턴은 쉽게 찾을 수 있는 반면 실제 응용 분야에서 널리 활용될 수 있는 관심도가 큰 순차패턴을 탐색하는데 한계가 있다. 이러한 단점을 보완하기 위한 대표적인 연구 주제들 중의 하나가 가중치 순차패턴 탐색이다. 가중치 순차패턴 탐색에서는 관심도가 큰 순차패턴을 얻기 위해서 구성요소의 단순 발생 순서 뿐만 아니라 구성요소의 가중치를 추가로 고려한다. 본 논문에서는 발생 간격에 기반 한 순차패턴 가중치 부여 기법 및 이를 활용한 순차 데이터 스트림에 대한 가중치 순차패턴 탐색 방법을 제안한다. 발생 간격 기반 가중치는 사전에 정의된 별도의 가중치 정보를 필요로 하지 않으며 순차정보를 구성하는 구성요소들의 발생 간격으로부터 구해진다. 즉, 순차패턴의 가중치를 구하는데 있어서 구성요소의 발생순서와 더불어 이들의 발생 간격을 고려하며, 따라서 보다 관심도가 크고 유용한 순차패턴을 얻는데 도움이 된다. 한편, 근래 대부분의 컴퓨터 응용 분야에서는 한정적인 데이터 집합 형태가 아닌 데이터 스트림 형태로 정보를 발생시키고 있다. 이와 같은 데이터 생성 환경의 변화를 고려하여 본 논문에서는 순차 데이터 스트림을 마이닝 대상으로 고려하였다.
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 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 knowledge embedded 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.
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 knowledge embedded 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.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
가중치 순차패턴 마이닝의 필요성을 살펴보기 위하여 인터넷 쇼핑몰에서 이용자의 웹 페이지 접근 로그로부터 생성된 순차 데이터 집합을 예로 들어 보자. 이때 하나의 웹 페이지는 하나의 개별 상품에 대한 정보를 담고 있다고 가정한다.
데이터 스트림에서 발생 간격 기반 가중치 순차패턴 마이닝은 분석 대상이 되는 순차 데이터 스트림에 대해서 해당 데이터 스트림에서 발생한 모든 빈발 발생 간격 기반 가중치 순차패턴들을 찾는 작업으로 정의할 수 있다. 본 절에서는 데이터 스트림 처리를 위한 기본적인 요구사항(Garofalakis, 2002)을 만족하면서 발생 간격 기반 가중치 순차패턴을 효율적으로 탐색하는 데이터 스트림 마이닝 기법을 제안한다. 먼저 제 5.
본 절에서는 발생 간격 기반 가중치 부여 기법 및 WSGap 방법의 유용성 및 효율성을 검증하기 위한 일련의 실험 결과를 제시하고 이에 대한 분석 결과를 기술한다. 실험에 사용된 데이터 집합은 두 가지이며, 하나는 SD_IBM 데이터 집합으로서 순차패턴 마이닝 방법의 효율성 검증을 위한 실험용 데이터 집합 생성에 널리 활용되는 IBM 데이터 생성기(IBM data generator)(Agrawal, 1995)를 이용하여 생성되었으며, 다른 하나는 SD_Web 데이터 집합으로서 실제 응용 분야에서 WSGap 방법의 효율성을 검증하기 위한 것으로 웹 사이트의 사용자 접근 로그로부터 생성되었다.
본 논문에서 제안하는 발생 간격 기반 가중치 순차패턴 탐색 방법은 데이터 스트림에서 순차패턴 탐색을 위한 기본적인 방법으로 선행 연구된 eISeq(Chang, 2005) 방법을 기반으로 발생 간격 기반 가중치 부여 기법을 적용하여 마이닝 결과 집합을 구한다. 본 절에서는 해당 방법에 대한 간략히 기술함으로써 본 논문에서 제안하는 WSGap 방법의 기본적인 틀에 대한 이해를 높이고자 한다.
여기서 두 개의 순차패턴 s1 = 와 s2 = 에 대해서 발생 간격 기반 가중치 적용에 따른 지지도 변화를 살펴보자.
이상에서 기술한 가중치 순차패턴 마이닝의 효용성 및 순차패턴 탐색에서 구성요소의 발생 간격의 중요성 등을 바탕으로 본 논문에서는 발생 간격 기반 가중치 부여 기법을 활용한 가중치 순차패턴 마이닝 방법을 제안하고자 한다. 특히 한정적인 데이터 집합이 아니라 지속적으로 확장되는 데이터 스트림 형태로 정보를 발생시키는 근래 컴퓨터 응용 분야의 특성을 고려하여 순차 데이터 스트림을 대상으로 발생 간격 기반 가중치 순차패턴을 탐색한다.
WSGap 방법 수행을 위한 설정값 중에서 중요 지지도 Ssig값은 발생간격 기반 가중치 순차패턴 탐색에는 직접적인 영향을 미치지 않는 것으로서 각 실험에서 동일하게 Smin의 30%로 설정하였다. 한편, WSGap 방법 수행에 있어서 데이터 스트림 처리를 위한 기본적인 요구조건인 메모리 사용량 및 마이닝 수행 시간 단축 등과 관련된 성능 분석 결과는 이전의 선행연구에서 충분히 검증되었으며 본 논문에서는 이를 생략한다.
가설 설정
가중치 순차패턴 마이닝의 필요성을 살펴보기 위하여 인터넷 쇼핑몰에서 이용자의 웹 페이지 접근 로그로부터 생성된 순차 데이터 집합을 예로 들어 보자. 이때 하나의 웹 페이지는 하나의 개별 상품에 대한 정보를 담고 있다고 가정한다. 해당 데이터 집합에서 각 순차정보는 개별 이용자의 순차적인 웹 페이지 접근 기록을 담고 있으며, 이는 해당 이용자가 관심을 갖고 정보를 검색한 물품들의 리스트로 간주할 수 있다.
제안 방법
이어서 해당 기법을 데이터 스트림에 대한 순차패턴 마이닝에 적용하여 데이터 스트림에 대한가중치 순차패턴 마이닝 기법을 완성한다. 논문에서 제안되는 방법은 데이터 스트림 처리의 기본적인 요구 조건들(Garofalakis, 2002)을 만족하면서 발생 간격에 기반 한 단위 항목의 가중치를 고려하여 관심도나 흥미도가 큰 순차패턴을 얻을 수 있다. 즉, 마이닝 수행 과정에서 메모리 사용량 및 수행 시간 최소화 등과 같은 데이터 스트림 처리를 위한 기본적인 요구 조건을 만족하면서 발생 간격 기반 가중치 순차패턴을 얻을 수 있다.
본 논문에서 제안한 발생 간격 기반 가중치 부여 기법에서는 하나의 순차패턴을 구성하는 여러 단위 항목들에 대해서 인접한 두 단위항목의 순차정보에서의 발생순서 차이를 발생 간격으로 정의하고, 이를 활용하여 발생 간격 기반 가중치를 부여한다. 먼저 가중치 함수를 이용하여 하나의 순차패턴에 존재하는 각 발생 간격에 대한 가중치를 구하고 이로부터 해당 순차패턴의 가중치를 구한다. 이어서 분석 대상이 되는 하나의 데이터 스트림에서 각 순차패턴의 가중치를 총합하여 해당 순차패턴의 지지도를 구하고, 이로부터 해당 순차패턴이 빈발 순차패턴이지를 판단한다.
먼저 발생 간격 기반 가중치 부여 기법의 효용성을 검증하기 위해서 SD_IBM 데이터 집합에 대해서 발생 간격 기반 가중치 적용시 마이닝 결과로 얻어지는 빈발 순차패턴 집합을 분석하였다. 해당 데이터 집합에 대한 다음의 실험들에서 Smin 값은 0.
특히 한정적인 데이터 집합이 아니라 지속적으로 확장되는 데이터 스트림 형태로 정보를 발생시키는 근래 컴퓨터 응용 분야의 특성을 고려하여 순차 데이터 스트림을 대상으로 발생 간격 기반 가중치 순차패턴을 탐색한다. 먼저 하나의 순차패턴을 구성하는 구성요소에 대해서 발생 간격을 정의하고, 이로부터 발생 간격에 기반 한 가중치 부여 기법을 제시한 다. 이어서 해당 기법을 데이터 스트림에 대한 순차패턴 마이닝에 적용하여 데이터 스트림에 대한가중치 순차패턴 마이닝 기법을 완성한다.
발생 간격 기반 가중치 부여 기법 및 WSGap 방법의 실제 응용 분야에서 발생한 데이터에 대한 유용성을 검증하기 위해서 SD_Web 데이터 집합에 대한 실험을 수행하였다. 해당 데이터 집합에 대한 다음의 실험들에서 Smin 값은 0.
발생 간격 기반 가중치 적용에 따른 순차패턴의 지지도 변화를 보다 명확히 파악하기 위하여 에서와 같이 동일한 순차패턴에 대해서 단순 지지도와 발생 간격 기반 가중치 지지도를 비교하였다.
SD_IBM 데이터 집합은 1,000개의 단위 항목으로부터 생성된 100,000개의 순차정보로 구성되며, SD_IBM 데이터 집합은 545개의 단위항목(즉, 개별 웹 페이지)으로부터 생성된 1,000,000개의 순차정보로 구성된다. 본 논문에서 제시되는 모든 실험에서는 구성 요소가 지속적으로 발생되고 이를 순차적으로 처리해야 하는 데이터 스트림 환경을 구현하기 위해서 각 데이터 집합을 구성하는 순차정보를 하나씩 차례로 탐색하여 처리하였다. WSGap 방법 수행을 위한 설정값 중에서 중요 지지도 Ssig값은 발생간격 기반 가중치 순차패턴 탐색에는 직접적인 영향을 미치지 않는 것으로서 각 실험에서 동일하게 Smin의 30%로 설정하였다.
본 논문에서 제안하는 발생 간격 기반 가중치 순차패턴 탐색 방법은 데이터 스트림에서 순차패턴 탐색을 위한 기본적인 방법으로 선행 연구된 eISeq(Chang, 2005) 방법을 기반으로 발생 간격 기반 가중치 부여 기법을 적용하여 마이닝 결과 집합을 구한다. 본 절에서는 해당 방법에 대한 간략히 기술함으로써 본 논문에서 제안하는 WSGap 방법의 기본적인 틀에 대한 이해를 높이고자 한다.
하나의 순차패턴에 있어서 발생 간격은 분석 대상이 되는 데이터 스트림의 특성이나 사용자의 관심도에 따라 다양한 기준으로 정의될 수 있다. 본 논문에서 제안한 발생 간격 기반 가중치 부여 기법에서는 하나의 순차패턴을 구성하는 여러 단위 항목들에 대해서 인접한 두 단위항목의 순차정보에서의 발생순서 차이를 발생 간격으로 정의하고, 이를 활용하여 발생 간격 기반 가중치를 부여한다. 먼저 가중치 함수를 이용하여 하나의 순차패턴에 존재하는 각 발생 간격에 대한 가중치를 구하고 이로부터 해당 순차패턴의 가중치를 구한다.
<표 1>은 발생 간격 기반 가중치 적용에 따른 가중치 순차패턴 마이닝 결과 집합에서 길이별 순차패턴의 개수 변화를 제시하고 있으며, SD_IBM 데이터 집합을 구성하는 100,000개의 순차정보가 모두 처리된 후의 결과를 분석하였다. 본 실험에서 감쇠기본값 b 및 허용 발생 간격 Ga는 각각 0.9 및 5로 설정되었으며, 단위 발생 간격 u의 변화에 따른 순차패턴 수의 변화를 분석하였다. 표에서 Lk(k = 1, 2, …)는 k개의 단위 항목으로 구성된 빈발 순차 패턴을 의미한다.
<그림 4>는 WSGap 방법을 이용한 발생 간격 기반 가중치 순차패턴 탐색의 효율성을 검증하기 위한 실험 결과로서 마이닝 수행시간을 제시하고 있다. 본 실험에서는 분석 대상이 되는 데이터 스트림을 2만 개의 순차정보로 구성되는 다섯 개의 동일 크기 구간으로 구분하여 각 구간에 포함되는 순차정보를 처리하는데 소요된 평균 시간을 보여주고 있다. <그림 4(a)>는 분석 대상 데이터 스트림을 구성하는 각 순차정보를 처리하는데 필요한 시간을 나타내고 있으며, 그림에서 보듯이 30 msec 이하의 시간에 하나의 순차정보를 처리하고 있다.
본 절에서는 발생 간격 기반 가중치 순차패턴 마이닝을 위한 기본적인 내용으로서 분석 대상이 되는 순차 데이터 스트림을 정의하고 가중치 순차패턴 마이닝의 기본 개념을 정리한다.
<그림 5>는 단위 발생 간격 u의 변화에 따른 빈발 순차패턴 수의 변화를 보여준다. 실험 데이터 집합에 속하는 순차정보가 지속적으로 발생되는 상황에서 순차정보가 매번 100,000개씩 처리된 시점에서의 마이닝 결과를 구하여 비교하였다. 동일한 발생 간격을 갖는 순차패턴이라 하더라도 단위 발생 간격이 작을수록 해당 순차패턴의 가중치가 감소되어 일정 시점에서 해당 순차패턴의 출현빈도 수 및 지지도가 작아지므로 SD_IBM 데이터 집합에 대한 실험 결과와 마찬가지로 단위 발생 간격이 작을수록 마이닝 결과로 얻어지는 순차패턴의 수가 감소된다.
이러한 연구 흐름을 고려하여 본 논문에서는 발생 간격 기반 가중치 부여 기법 및 이를 활용한 데이터 스트림에서의 가중치 순차패턴 탐색 방법인 WSGap 방법을 제안하였다. 하나의 순차패턴에 있어서 발생 간격은 분석 대상이 되는 데이터 스트림의 특성이나 사용자의 관심도에 따라 다양한 기준으로 정의될 수 있다.
먼저 가중치 함수를 이용하여 하나의 순차패턴에 존재하는 각 발생 간격에 대한 가중치를 구하고 이로부터 해당 순차패턴의 가중치를 구한다. 이어서 분석 대상이 되는 하나의 데이터 스트림에서 각 순차패턴의 가중치를 총합하여 해당 순차패턴의 지지도를 구하고, 이로부터 해당 순차패턴이 빈발 순차패턴이지를 판단한다. 한편, 일련의 실험 결과로부터 논문에서 제안한 방법이 데이터 스트림에 대한 가중치 순차패턴 탐색에 효과적으로 적용될 수 있으며 발생 간격을 고려하여 보다 정제된 형태의 순차패턴들을 마이닝 결과로 구해줌을 확인하였다.
먼저 하나의 순차패턴을 구성하는 구성요소에 대해서 발생 간격을 정의하고, 이로부터 발생 간격에 기반 한 가중치 부여 기법을 제시한 다. 이어서 해당 기법을 데이터 스트림에 대한 순차패턴 마이닝에 적용하여 데이터 스트림에 대한가중치 순차패턴 마이닝 기법을 완성한다. 논문에서 제안되는 방법은 데이터 스트림 처리의 기본적인 요구 조건들(Garofalakis, 2002)을 만족하면서 발생 간격에 기반 한 단위 항목의 가중치를 고려하여 관심도나 흥미도가 큰 순차패턴을 얻을 수 있다.
이상에서 기술한 가중치 순차패턴 마이닝의 효용성 및 순차패턴 탐색에서 구성요소의 발생 간격의 중요성 등을 바탕으로 본 논문에서는 발생 간격 기반 가중치 부여 기법을 활용한 가중치 순차패턴 마이닝 방법을 제안하고자 한다. 특히 한정적인 데이터 집합이 아니라 지속적으로 확장되는 데이터 스트림 형태로 정보를 발생시키는 근래 컴퓨터 응용 분야의 특성을 고려하여 순차 데이터 스트림을 대상으로 발생 간격 기반 가중치 순차패턴을 탐색한다. 먼저 하나의 순차패턴을 구성하는 구성요소에 대해서 발생 간격을 정의하고, 이로부터 발생 간격에 기반 한 가중치 부여 기법을 제시한 다.
이와 달리 본 논문에서 제안하는 방법과 같이 발생 간격을 기반으로 순차정보의 가중치를 구하고 이를 활용하여 순차패턴을 탐색하는 경우 발생 간격의 차이에 유연하게 변화되는 마이닝 결과 집합을 얻을 수 있다. 한편, 가중치 순차패턴 탐색을 위한 이전의 방법들은 일반적으로 순차정보 또는 순차패턴의 가중치를 구하기 위해서 사전에 부여된 가중치 정보를 필요로 하는 반면 본 논문에서는 해당 가중치 정보를 순차정보를 구성하는 단위 항목들의 발생 간격으로부터 구한다. 즉, 본 논문에서 제안하는 발생 간격 기반 가중치 순차패턴 탐색 방법은 사전에 부여된 가중치 정보가 없이 순차정보 및 순차패턴에서 중요한 의미를 갖는 단위 항목들의 발생 간격으로부터 가중치 순차패턴을 구할 수 있으며, 이를 통해 발생 간격 변화에 유연하게 적응되는 순차패턴 집합을 마이닝 결과를 얻을 수 있다.
대상 데이터
실험에 사용된 데이터 집합은 두 가지이며, 하나는 SD_IBM 데이터 집합으로서 순차패턴 마이닝 방법의 효율성 검증을 위한 실험용 데이터 집합 생성에 널리 활용되는 IBM 데이터 생성기(IBM data generator)(Agrawal, 1995)를 이용하여 생성되었으며, 다른 하나는 SD_Web 데이터 집합으로서 실제 응용 분야에서 WSGap 방법의 효율성을 검증하기 위한 것으로 웹 사이트의 사용자 접근 로그로부터 생성되었다. SD_IBM 데이터 집합은 1,000개의 단위 항목으로부터 생성된 100,000개의 순차정보로 구성되며, SD_IBM 데이터 집합은 545개의 단위항목(즉, 개별 웹 페이지)으로부터 생성된 1,000,000개의 순차정보로 구성된다. 본 논문에서 제시되는 모든 실험에서는 구성 요소가 지속적으로 발생되고 이를 순차적으로 처리해야 하는 데이터 스트림 환경을 구현하기 위해서 각 데이터 집합을 구성하는 순차정보를 하나씩 차례로 탐색하여 처리하였다.
반면 L2의 경우는 발생 간격 기반 가중치에 크게 영향을 받음을 알 수 있다. 실험에 사용된 SD_IBM 데이터 집합은 실제 응용 분야 데이터 집합이 아니라 인위적으로 생성된 데이터 집합으로서 각 순차패턴의 지지도 및 발생 간격 등이 적절히 분포되도록 생성된다. 또한 일반적으로 큰 발생 간격을 갖는 순차패턴이 자주 발생되어 빈발 순차패턴이 되는 경우는 거의 존재하지 않는다.
본 절에서는 발생 간격 기반 가중치 부여 기법 및 WSGap 방법의 유용성 및 효율성을 검증하기 위한 일련의 실험 결과를 제시하고 이에 대한 분석 결과를 기술한다. 실험에 사용된 데이터 집합은 두 가지이며, 하나는 SD_IBM 데이터 집합으로서 순차패턴 마이닝 방법의 효율성 검증을 위한 실험용 데이터 집합 생성에 널리 활용되는 IBM 데이터 생성기(IBM data generator)(Agrawal, 1995)를 이용하여 생성되었으며, 다른 하나는 SD_Web 데이터 집합으로서 실제 응용 분야에서 WSGap 방법의 효율성을 검증하기 위한 것으로 웹 사이트의 사용자 접근 로그로부터 생성되었다. SD_IBM 데이터 집합은 1,000개의 단위 항목으로부터 생성된 100,000개의 순차정보로 구성되며, SD_IBM 데이터 집합은 545개의 단위항목(즉, 개별 웹 페이지)으로부터 생성된 1,000,000개의 순차정보로 구성된다.
데이터처리
값 변화에 따른 빈발 순차패턴 수 변화를 보여준다. 각각의 결과는 SD_IBM에 속하는 순차정보가 지속적으로 발생되는 상황에서 순차정보가 매번 10,000개씩 처리된 시점에서의 마이닝 결과를 구하여 비교하였다. <그림 3(a)>는 단위 발생 간격 u의 변화에 따른 빈발 순차패턴 수의 변화를 보여준다.
따라서 발생 간격 기반 가중치를 적용하여 이들을 마이닝 결과집합에서 제외하는 가중치 순차패턴 마이닝을 통해 보다 효율적인 순차패턴 마이닝을 수행할 수 있다. <표 4>는 SD_Web 데이터 집합에 대한 실험에서 동일한 순차패턴에 대한 단순 지지도와 발생 간격 기반 가중치 지지도를 비교하였다. 표에서 순차패턴을 구성하는 숫자들은 개별 단위항목을 나타낸다.
<표 1>은 발생 간격 기반 가중치 적용에 따른 가중치 순차패턴 마이닝 결과 집합에서 길이별 순차패턴의 개수 변화를 제시하고 있으며, SD_IBM 데이터 집합을 구성하는 100,000개의 순차정보가 모두 처리된 후의 결과를 분석하였다. 본 실험에서 감쇠기본값 b 및 허용 발생 간격 Ga는 각각 0.
이론/모형
즉, 출현빈도 수 갱신 과정에서 하나의 순차정보에 출현한 각 순차패턴에 대해서 출현빈도 수를 갱신하는데 있어서 단순 지지도를 기반으로 하는 기존의 방법에서는 1만큼 출현빈도 수를 증가시켰으나 WSGap 방법에서는 해당 순차패턴을 구성하는 단위항목들의 발생 간격으로부터 가중치를 구한 후 해당 가중치만큼 출현빈도 수를 증가시킨다. 순차패턴 추가 과정에서도 새로 발생된 순차패턴의 출현빈도 수를(Chang, 2005)에서 제시된 방법으로 계산하는데 있어서 해당 순차패턴의 발생 간격 기반 가중치를 활용한다. WSGap 방법의 수행 과정은 <그림 2>에서와 같다.
성능/효과
이때 발생 시간이 동일한 단위 항목들은 단위항목을 나타내는 기호의 알파벳 순서로 정렬된다. 유사한 방법으로 본 논문에서 사용한 방식으로 표현된 순차정보도 기존의 표현 방식으로 변경할 수 있다. 즉, 동시에 발생한 단위 항목들을 항목집합으로 결합하고 이들을 발생 시간 순서에 따라 정렬함으로써 기존의 표현 방식으로 변경할 수 있다(Garofalakis, 2002).
이로 인해 마이닝 수행 결과로 얻어지는 순차패턴 집합이 발생 간격의 작은 차이에도 지나치게 변화된다. 이와 달리 본 논문에서 제안하는 방법과 같이 발생 간격을 기반으로 순차정보의 가중치를 구하고 이를 활용하여 순차패턴을 탐색하는 경우 발생 간격의 차이에 유연하게 변화되는 마이닝 결과 집합을 얻을 수 있다. 한편, 가중치 순차패턴 탐색을 위한 이전의 방법들은 일반적으로 순차정보 또는 순차패턴의 가중치를 구하기 위해서 사전에 부여된 가중치 정보를 필요로 하는 반면 본 논문에서는 해당 가중치 정보를 순차정보를 구성하는 단위 항목들의 발생 간격으로부터 구한다.
논문에서 제안되는 방법은 데이터 스트림 처리의 기본적인 요구 조건들(Garofalakis, 2002)을 만족하면서 발생 간격에 기반 한 단위 항목의 가중치를 고려하여 관심도나 흥미도가 큰 순차패턴을 얻을 수 있다. 즉, 마이닝 수행 과정에서 메모리 사용량 및 수행 시간 최소화 등과 같은 데이터 스트림 처리를 위한 기본적인 요구 조건을 만족하면서 발생 간격 기반 가중치 순차패턴을 얻을 수 있다.
포함 관계에 있는 두 순차패턴의 발생 간격 기반 가중치 지지도에 대한 이러한 관계를 발생 간격 기반 가중치 지지도의 anti-monotone 속성이라 하며, 이를 활용하여 발생 간격 기반 가중치 순차패턴 탐색 과정에서 데이터 집합에 대한 탐색 횟수나 탐색 범위를 크게 감소시킬 수 있다. 즉, 만약 하나의 순차패턴 s의 발생 간격 기반 가중치 지지도 gwSk(s)가 최소 지지도 Smin보다 작아서 빈발 순차패턴이 되지 못한다면 발생 간격 기반 가중치 지지도의 anti-monotone 속성에 의해 s의 확대-순차패턴들도 빈발 순차패턴이 될 수 없음을 판단할 수 있다.
한편, 가중치 순차패턴 탐색을 위한 이전의 방법들은 일반적으로 순차정보 또는 순차패턴의 가중치를 구하기 위해서 사전에 부여된 가중치 정보를 필요로 하는 반면 본 논문에서는 해당 가중치 정보를 순차정보를 구성하는 단위 항목들의 발생 간격으로부터 구한다. 즉, 본 논문에서 제안하는 발생 간격 기반 가중치 순차패턴 탐색 방법은 사전에 부여된 가중치 정보가 없이 순차정보 및 순차패턴에서 중요한 의미를 갖는 단위 항목들의 발생 간격으로부터 가중치 순차패턴을 구할 수 있으며, 이를 통해 발생 간격 변화에 유연하게 적응되는 순차패턴 집합을 마이닝 결과를 얻을 수 있다.
반면 WSGap 방법은 분석 대상이 되는 데이터 스트림이 지속적으로 갱신되는 경우에도 새로 추가된 하나의 순차정보에 대한 처리를 통해 최신의 마이닝 결과를 얻을 수 있다. 즉, 분석 대상 데이터 스트림을 구성하는 전체 순차정보에 대한 재탐색이나 반복적인 탐색 없이 추가된 순차정보에 대한 처리만으로 최신의 마이닝 결과를 얻을 수 있다. 따라서 매우 짧은 시간에 해당 마이닝 결과를 얻을 수 있다.
한편, 일련의 실험 결과로부터 논문에서 제안한 방법이 데이터 스트림에 대한 가중치 순차패턴 탐색에 효과적으로 적용될 수 있으며 발생 간격을 고려하여 보다 정제된 형태의 순차패턴들을 마이닝 결과로 구해줌을 확인하였다. 특히, 실제 응용 분야에서 발생된 데이터 집합에 대해서도 효과적으로 적용될 수 있음을 확인하였다.
<표 2>에서 제시된 순차패턴은 상대적으로 발생 간격이 큰 순차패턴으로서 발생 간격 기반 가중치 적용 시 지지도가 감쇠되는 것들이다. 표에서 제시된 것보다 많은 수의 순차패턴들이 발생 간격 기반 가중치 지지도가 감소되었으며, 표에서는 지지도 감소폭이 큰 10개를 제시하였다. 표에서 알 수 있듯이 각 순차패턴들은 단순 지지도 기반으로 순차패턴 마이닝을 수행하는 경우 Smin = 0.
일반적으로 순차정보는 항목집합(itemset)들의 정렬된 집합으로 표현되는 반면 본 논문에서는 순차정보를 단위 항목들의 정렬된 리스트로 정의하였다. 하지만, 본 논문의 정의 방식으로도 기존의 순차정보인 항목집합들의 정렬된 집합을 효과적으로 표현할 수 있다. 즉, 항목집합들의 정렬된 집합인 기존의 순차정보에서 각 단위 항목들을 발생시간 순서에 따라 정렬하여 단위 항목들의 정렬된 집합으로 변경하는 경우 본 논문의 표현방식과 동일한 형태로 변경할 수 있다.
동일한 발생 간격을 갖는 순차패턴이라 하더라도 단위 발생 간격이 작을수록 해당 순차패턴의 가중치가 감소되어 일정 시점에서 해당 순차패턴의 출현빈도 수 및 지지도가 작아지므로 SD_IBM 데이터 집합에 대한 실험 결과와 마찬가지로 단위 발생 간격이 작을수록 마이닝 결과로 얻어지는 순차패턴의 수가 감소된다. 한편, SD_Web 데이터 집합에 대한 감쇠기본값 b 및 허용 발생 간격 Ga에 변화에 따른 순차패턴 수 변화 실험에서도 SD_IBM 데이터 집합에 대한 실험 결과와 유사한 결과를 확인할 수 있었다.
이어서 분석 대상이 되는 하나의 데이터 스트림에서 각 순차패턴의 가중치를 총합하여 해당 순차패턴의 지지도를 구하고, 이로부터 해당 순차패턴이 빈발 순차패턴이지를 판단한다. 한편, 일련의 실험 결과로부터 논문에서 제안한 방법이 데이터 스트림에 대한 가중치 순차패턴 탐색에 효과적으로 적용될 수 있으며 발생 간격을 고려하여 보다 정제된 형태의 순차패턴들을 마이닝 결과로 구해줌을 확인하였다. 특히, 실제 응용 분야에서 발생된 데이터 집합에 대해서도 효과적으로 적용될 수 있음을 확인하였다.
후속연구
웹 기반 시스템, 전자상거래, 생물정보학 및 USN 환경 등 근래의 다양한 컴퓨터 응용 환경에서는 순차 데이터 스트림 형태로 정보를 발생시키고 있다. 따라서 본 논문에서 제안한 발생 간격 기반 가중치 부여 기법 및 이를 활용한 데이터 스트림에 대한 가중치 순차패턴 탐색 방법은 이들 응용 분야에서 유용하게 활용될 수 있으며, 특히 관심도 큰 순차패턴을 얻는데 도움이 될 것이다.
단순 지지도에 기반한 일반 순차패턴 마이닝에서는 해당 데이터 집합에서 물품의 단순 검색 순서만 고려하여 순차패턴을 구한다. 하지만 해당 데이터 집합에 대한 마이닝에서 단순히 이용자들이 관심을 갖는 물품에 대한 분석 결과뿐만 아니라 물품의 가격 정보가 고려된 분석 결과를 얻을 수 있다면 해당 인터넷 쇼핑몰의 이익을 증가시킬 수 있을 것이다. 이를 고려하여 물품에 대한 검색 순서뿐만 아니라 각 물품의 가격 정보를 고려하여 순차패턴 마이닝을 수행하는 가중치 순차패턴 마이닝을 적용하는 경우 해당 인터넷 쇼핑몰의 필요에 보다 적합한 분석 결과를 얻을 수 있다.
즉, 동시에 발생한 단위 항목들을 항목집합으로 결합하고 이들을 발생 시간 순서에 따라 정렬함으로써 기존의 표현 방식으로 변경할 수 있다(Garofalakis, 2002). 한편, 본 논문의 정의 방식 그 자체로도 웹 사용 정보 분석이나 생물정보학 분야의 DNA 순서 분석 등 여러 분야에서 유용하게 활용될 수 있다(Ji, 2007).
질의응답
핵심어
질문
논문에서 추출한 답변
순차패턴 탐색이란 무엇인가?
순차패턴 마이닝(sequential pattern mining)은 순차 데이터 집합으로부터 흥미로운 순차패턴(sequential pattern)을 탐색하는데 목적을 두고 있으며, 이는 주요한 데이터마이닝 분야 중의 하나로서 다양한 컴퓨터 응용 분야에서 널리 활용되고 있다. 순차패턴 탐색은 분석 대상 데이터 집합 및 출현빈도 수 임계값이 주어졌을 때 해당 임계값 이상의 출현빈도 수를 갖는 모든 순차패턴을 찾는 작업이다. 일반적으로 마이닝 수행 결과로 얻어지는 순차패턴의 수가 매우 많으며, 따라서 이를 바로 응용 분야의 특성을 이해하기 위해서 활용하는데 어려움이 있다.
가중치 순차패턴 마이닝을 위한 대부분의 이전 연구들은 일반적으로 사전에 정의된(혹은 부가적으로 명시된) 별도의 가중치 정보를 필요로 하는데, 이러한 접근 방법은 어떤 한계가 있는가?
예를 들어 도소매 업체의 물품 판매 데이터 집합에서는 판매 물품의 단가나각 판매에 따른 판매량 등의 정보를 가중치 정보로 활용한다. 하지만 사전에 정의된 가중치를 활용하는 이러한 접근 방법은 부가적인 정보를 발생시키지 않고 단순히 구성요소의 순차적인 발생 여부만을 판단할 수 있는 응용 분야에서는 효율적으로 활용되는데 한계가 있다. 한편, 상대적으로 관심도가 큰 순차패턴을 탐색하기 위한 다른 연구들도 활발히 진행되어 왔다.
순차패턴 마이닝의 목적은 무엇인가?
순차패턴 마이닝(sequential pattern mining)은 순차 데이터 집합으로부터 흥미로운 순차패턴(sequential pattern)을 탐색하는데 목적을 두고 있으며, 이는 주요한 데이터마이닝 분야 중의 하나로서 다양한 컴퓨터 응용 분야에서 널리 활용되고 있다. 순차패턴 탐색은 분석 대상 데이터 집합 및 출현빈도 수 임계값이 주어졌을 때 해당 임계값 이상의 출현빈도 수를 갖는 모든 순차패턴을 찾는 작업이다.
참고문헌 (16)
Agrawal, R. and R. Srikant., "Mining Sequential Patterns", Proc. of the 1995 Int'l Conf. on Data Engineering, (1995), 3-14.
Chang, J. H. and W. S. Lee., "Efficient Mining Method for Retrieving Sequential Patterns over Online Data Streams", Journal of Information Science, Vol.31, No.5(2005), 420-432.
Chen, Y. L. and T. C.-H. Huang., "Discovering Time-Interval Sequential Patterns in Sequence Databases", Expert Systems with Applications, Vol.25, No.1(2003), 343-354.
Chen, Y. L., M. C. Chiang. and M. T. Ko., "Discovering Fuzzy Time-Interval Sequential Patterns in Sequence Databases", IEEE Transactions on Systems, Man, and Cybernetics-Part B : Cybernetics, Vol.35, No.5(2005), 959-972.
Garofalakis, M., J. Gehrke. and R. Rastogi., "Querying and Mining Data Streams : You Only Get One Look", in The tutorial notes of the 28th Int'l Conf. onVery Large Data Bases, (2002).
Huang, Q. and W. Ouyang., "Mining Sequential Patterns in Data Streams", Proc. of the 6th Int'l Symposium on Neural Networks, (2009), 865-874.
Ji, X., J. Bailey. and G. Dong., "Mining Minimal Distinguishing Subsequence Patterns with Gap Constraints", Knowledge and Information Systems, Vol.11, No.3(2007), 259-296.
Kum, H. C., J. Pei., W. Wang. and D. Duncan., "ApproxMAP : Approximate Mining of Consensus Sequential Patterns", Proc. of the 2003 SIAM Int'l Conf. on Data Mining(SDM'03), 311-315, (2003).
Kum, H. C., J. H. Chang. and W. Wang., "Sequential Pattern Mining in Multi- Databases via Multiple Alignment", Data Mining and Knowledge Discovery, Vol.12, No.2(2006), 151-180.
Lin, M. Y., S. C. Hsueh. and C. W. Chang., "Fast Discovery of Sequential Patterns in Large Databases using Effective Time-Indexing", Information Sciences, Vol.178, No.22(2008), 4228-4245.
Lo, S., "Binary Prediction based on Weighted Sequential mining method", Proc. of the (2005) Int'l Conf. on Web Intelligence, pp. 755-761, 2005.
Luo, C. and S. M. Chung., "Efficient Mining of Maximal Sequential Patterns Using Multiple Samples", Proc. of the 2005 SIAM Int'l Conf. on Data Mining(SDM '05), 64-72, (2005).
Pei, J., J. Han. and W. Wang., "Mining Sequential Patterns with Constraints in Large Databases", Proc. of the 2002 ACM Int'l Conf. on Information and Knowledge Management (CIKM '02), (2002), 18-25.
Pei, J., J. Han., B. Mortazavi-Asl., J. Wang., H. Pinto., Q. Chen., U. Dayal. and M. C. Hsu., "Mining Sequential Patterns by Pattern- Growth: The PrefixSpan Approach", IEEE Transactions on Knowledge and Data Engineering, Vol.16, No.11(2004), 1424-1440.
Wang, J., J. Han. and C. Li., "Frequent Closed Sequence Mining without Candidate Maintenance", IEEE Transactions on Knowledge and Data Engineering, Vol.19, No. 8(2007), 1042-1056.
Yun, U., "A New Framework for Detecting Weighted Sequential Patterns in Large Sequence Databases", Knowledge-Based Systems, Vol.21, No.2(2008), 110-122.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.