Search
Search

연구성과물 검색 타이틀 이미지

HOME ICON HOME > Search by Achievements Type > Reports View

Reports Detailed Information

https://www.krm.or.kr/krmts/link.html?dbGubun=SD&m201_id=10007016&local_id=10010627
온라인 트랜잭션 데이터 스트림에서 빈발 패턴 탐색 (Mining Frequent Patterns over Online Transactional Data Streams)
Reports NRF is supported by Research Projects( 온라인 트랜잭션 데이터 스트림에서 빈발 패턴 탐색 (Mining Frequent Patterns over Online Transactional Data Streams) | 2004 Year 신청요강 다운로드 PDF다운로드 | 장중혁(연세대학교) ) data is submitted to the NRF Project Results
Researcher who has been awarded a research grant by Humanities and Social Studies Support Program of NRF has to submit an end product within 6 months(* depend on the form of business)
사업별 신청요강보기
  • Researchers have entered the information directly to the NRF of Korea research support system
Project Number D00053
Year(selected) 2004 Year
the present condition of Project 종료
State of proposition 재단승인
Completion Date 2005년 11월 02일
Year type 결과보고
Year(final report) 2005년
Research Summary
  • Korean
  • 한정적인 데이터 집합 형태로 정보를 발생시키는 이전의 응용 분야와는 달리 최근 들어 유비쿼터스 환경을 포함하는 다양한 센서 네트워크, 인터넷 및 네트웍 분석, 정보 보안, 상업적 데이터 분석, 생물정보학, 다양한 로그 정보 분석 등과 같은 다양한 실제 응용 분야에서 지속적으로 발생되는 데이터 스트림 형태로 정보를 발생 시키고 있다. 데이터 스트림은 구성 요소들이 매우 빠른 속도로 지속적으로 발생되는 방대한 양의 무한 집합으로 정의된다. 또한, 해당 데이터 스트림에 내재된 지식이나 정보들은 시간 변화에 따른 가변성이 매우 높다. 따라서, 데이터 스트림에 대한 효율적인 마이닝 수행을 위해서는 한정적인 데이터 집합을 대상으로 하는 기존의 마이닝 방법들과는 다른 새로운 마이닝 방법을 필요로 한다. 한편, 온라인 데이터 스트림의 시간변화에 따른 가변성을 고려할 때, 해당 데이터 스트림에서 최신의 변화를 효율적으로 감지하는 것은 해당 데이터 스트림에 대한 분석에서 보다 가치있는 정보를 제공할 수 있다. 이러한 이유들로 인해서 마이닝 결과를 구하기 위해서 상당히 긴 수행 시간을 필요로 하는 기존의 마이닝 방법들을 온라인 데이터 스트림에 대한 마이닝 작업에 적용하는 것은 거의 불가능하다.</br>
    본 연구에서는 온라인 트랜잭션 데이터 스트림에서 빈발항목 탐색을 위한 마이닝 방법을 제안한다. 더불어 해당 방법에서는 분석 대상 데이터 스트림에 지속적으로 확장되더라도 마이닝 수행과정에서의 메모리 사용량이 한정적으로 유지되도록 지원하기 위한 몇 가지 최적화 방법도 제안한다. 즉 마이닝 수행과정에서 메모리 상에서 관리되는 패턴의 수가 두 가지 핵심 작업인 지연추가 및 전지 작업에 의해 최소화 된다. 지연 추가 작업은 트랜잭션에서 발생된 패턴들이 충분히 큰 지지도를 가질 때까지 해당 패턴의 지지도 관리를 지연하는 방법이며, 전지 작업은 현재 메모리 상에서 관리되는 패턴들 중에서 지지도가 감소되어 비중요 패턴으로 간주될 수 있는 패턴을 더 이상 관리하지 않고 전지하는 방법이다. 메모리 상에서 관리되는 패턴의 수는 이러한 두 가지 작업의 매개변수에 따라 조절된다. 이러한 두 가지 작업을 통해서 하나의 트랜잭션 처리를 위한 수행 시간 및 임의 시점에서의 마이닝 탐색 시간도 최소화 할 수 있다.</br>
    일반적으로, 데이터 스트림을 대상으로 하는 이전의 마이닝 방법들은 과거의 오래된 정보로부터 최근에 발생된 새로운 정보를 구분하는 정보차별화 기법을 포함하지 않는다. 따라서, 이전의 마이닝 방법들에서는 시간 변화에 따라 지속적으로 변화되는 데이터 스트림에서 나타나는 최근의 변화를 효율적 반영한 마이닝 결과를 얻지 못한다. 본 연구에서는 데이터 스트림에서 나타나는 최근의 변화를 효율적으로 분석하기 위해서 감쇠율 방법 및 슬라이딩 윈도우 기법과 같은 정보 차별화 기법을 제안한다. 감쇠율 기법을 적용한 데이터 스트림 마이닝 기법에서는 마이닝 결과를 구하는데 있어서 과거 정보의 중요성을 시간 변화에 따라 일정 비율로 감쇠시킴으로써 현재의 마이닝 결과에 포함된 해당 과거 정보들의 영향력을 감소시킨다. 이를 통해, 데이터 스트림에서 과거 정보들로 인해 현재 마이닝 결과가 왜곡되는 현상을 방지하고 최근의 변화를 효율적으로 반영하는 마이닝 결과를 얻을 수 있다. 한편, 슬라이딩 윈도우 기법을 적용한 데이터 스트림 마이닝 기법에서는 새로 발생된 정보들의 유효 주기가 슬라이딩 윈도의 크기에 의해 결정된다. 즉, 현재의 윈도우 범위에 해당되는 정보들만 유효 정보로 간주되며, 해당 범위에 포함되는 정보들에 대한 마이닝 결과를 얻을 수 있다.
  • English
  • Recently, in various application fields such as sensor networks, network monitoring, anomaly intrusion detections, financial tickers, bio-informatics, telecommunications data management, web personalization, and others, data takes the form of continuous data streams rather than finite stored data sets. A data stream is a massive unbounded sequence of data elements continuously generated at a rapid rate, and the knowledge embedded in the data stream is more likely to be changed over time. Therefore, to find an embedded knowledge in a data stream efficiently, a novel mining method that differs from the conventional mining method of a fixed data set is required. Especially, considering the changeability of an online data stream over time, identifying the recent change of the data stream can provide valuable information for the data stream analysis. Due to these requirements, it is almost impossible to apply conventional data mining methods to mining task in an online data stream.</br>
    In this research, a mining method of frequent patterns over an online transactional data stream is proposed. Moreover, several optimization techniques are also proposed, which make its memory usage be small. In other words, the current set of monitored itemsets in an online data stream is minimized by two major operations: delayed-insertion and pruning. The former is delaying the insertion of a new itemset in new transactions until the itemset becomes significant enough to be monitored. The latter is pruning a monitored itemset when the itemset turns out to be insignificant. The number of monitored itemsets can be flexibly controlled by the thresholds of these two operations. By these operations, the processing time per transaction and that for finding its mining result at any moment of the proposed method can also be minimized.</br>
    Generally, most of mining algorithms over a data stream do not differentiate the information of recently generated data elements from the obsolete information of old data elements which may be no longer useful or possibly invalid at present. Therefore, they are not able to extract the recent change of information in a data stream adaptively. In this research, to identify the recent change of a data steam, information differentiation techniques over a data stream such as a decay mechanism and a sliding window technique are also proposed. In a mining method over a data stream based on a decay mechanism, the effect of old transactions on the current mining result of the data steam is diminished by decaying the old occurrences of each itemset over time. While, in a mining method over a data stream based on a sliding window technique, the desired life-time of information in a newly generated transaction is defined by the size of a sliding window. Consequently, only recently generated transactions in the range of the window are considered to find the recently frequent itemsets of a data stream.
Research result report
  • Abstract
  • 한정적인 데이터 집합 형태로 정보를 발생시키는 이전의 응용 분야와는 달리 최근 들어 유비쿼터스 환경을 포함하는 다양한 센서 네트워크, 인터넷 및 네트웍 분석, 정보 보안, 상업적 데이터 분석, 생물정보학, 다양한 로그 정보 분석 등과 같은 다양한 실제 응용 분야에서 지속적으로 발생되는 데이터 스트림 형태로 정보를 발생 시키고 있다. 데이터 스트림은 구성 요소들이 매우 빠른 속도로 지속적으로 발생되는 방대한 양의 무한 집합으로 정의된다. 또한, 해당 데이터 스트림에 내재된 지식이나 정보들은 시간 변화에 따른 가변성이 매우 높다. 따라서, 데이터 스트림에 대한 효율적인 마이닝 수행을 위해서는 한정적인 데이터 집합을 대상으로 하는 기존의 마이닝 방법들과는 다른 새로운 마이닝 방법을 필요로 한다. 한편, 온라인 데이터 스트림의 시간변화에 따른 가변성을 고려할 때, 해당 데이터 스트림에서 최신의 변화를 효율적으로 감지하는 것은 해당 데이터 스트림에 대한 분석에서 보다 가치있는 정보를 제공할 수 있다. 이러한 이유들로 인해서 마이닝 결과를 구하기 위해서 상당히 긴 수행 시간을 필요로 하는 기존의 마이닝 방법들을 온라인 데이터 스트림에 대한 마이닝 작업에 적용하는 것은 거의 불가능하다.</br>
    본 연구에서는 온라인 트랜잭션 데이터 스트림에서 빈발항목 탐색을 위한 마이닝 방법을 제안한다. 더불어 해당 방법에서는 분석 대상 데이터 스트림에 지속적으로 확장되더라도 마이닝 수행과정에서의 메모리 사용량이 한정적으로 유지되도록 지원하기 위한 몇 가지 최적화 방법도 제안한다. 즉 마이닝 수행과정에서 메모리 상에서 관리되는 패턴의 수가 두 가지 핵심 작업인 지연추가 및 전지 작업에 의해 최소화 된다. 지연 추가 작업은 트랜잭션에서 발생된 패턴들이 충분히 큰 지지도를 가질 때까지 해당 패턴의 지지도 관리를 지연하는 방법이며, 전지 작업은 현재 메모리 상에서 관리되는 패턴들 중에서 지지도가 감소되어 비중요 패턴으로 간주될 수 있는 패턴을 더 이상 관리하지 않고 전지하는 방법이다. 메모리 상에서 관리되는 패턴의 수는 이러한 두 가지 작업의 매개변수에 따라 조절된다. 이러한 두 가지 작업을 통해서 하나의 트랜잭션 처리를 위한 수행 시간 및 임의 시점에서의 마이닝 탐색 시간도 최소화 할 수 있다.</br>
    일반적으로, 데이터 스트림을 대상으로 하는 이전의 마이닝 방법들은 과거의 오래된 정보로부터 최근에 발생된 새로운 정보를 구분하는 정보차별화 기법을 포함하지 않는다. 따라서, 이전의 마이닝 방법들에서는 시간 변화에 따라 지속적으로 변화되는 데이터 스트림에서 나타나는 최근의 변화를 효율적 반영한 마이닝 결과를 얻지 못한다. 본 연구에서는 데이터 스트림에서 나타나는 최근의 변화를 효율적으로 분석하기 위해서 감쇠율 방법 및 슬라이딩 윈도우 기법과 같은 정보 차별화 기법을 제안한다. 감쇠율 기법을 적용한 데이터 스트림 마이닝 기법에서는 마이닝 결과를 구하는데 있어서 과거 정보의 중요성을 시간 변화에 따라 일정 비율로 감쇠시킴으로써 현재의 마이닝 결과에 포함된 해당 과거 정보들의 영향력을 감소시킨다. 이를 통해, 데이터 스트림에서 과거 정보들로 인해 현재 마이닝 결과가 왜곡되는 현상을 방지하고 최근의 변화를 효율적으로 반영하는 마이닝 결과를 얻을 수 있다. 한편, 슬라이딩 윈도우 기법을 적용한 데이터 스트림 마이닝 기법에서는 새로 발생된 정보들의 유효 주기가 슬라이딩 윈도의 크기에 의해 결정된다. 즉, 현재의 윈도우 범위에 해당되는 정보들만 유효 정보로 간주되며, 해당 범위에 포함되는 정보들에 대한 마이닝 결과를 얻을 수 있다.
  • Research result and Utilization method
  • 이전에 한정적인 데이터 집합을 대상으로 제안된 다양한 마이닝 기법들 중에서 본 연구에서는 빈발항목 탐색 및 이를 바탕으로 하는 연관규칙 탐색 기법과 순차패턴 탐색 기법에 대해서 연구하였다. 즉, 데이터 스트림을 대상으로 하는 효율적인 빈발항목 탐색 기법 및 순차패턴 탐색 기법을 설계/구현하였다. 더불어, 시간 변화에 따른 변화를 효율적으로 마이닝 결과 집합에 포함하기 위한 정보차별화 기법을 설계하였으며 이를 빈발항목 탐색 및 연관규칙 탐색 기법에 포함하여 데이터 스트림에서 정보의 중요성이 시간 변화에 따라 차별화되는 빈발항목 탐색 기법 및 순차패턴 탐색 기법을 연구연구하였다. 주요 연구 결과는 다음과 같다.</br>
    - 수행중 컴퓨팅 자원 사용을 최소화하는 데이터 스트림에 대한 빈발항목 탐색 기법</br>
    - 데이터 스트림에 나타나는 변화를 마이닝 결과에 반영할 수 있는 데이터 스트림 변화 감지 기법</br>
    - 시간 변화에 따른 데이터 스트림의 변화 및 가용 컴퓨팅 자원 변화를 고려한 동적 마이닝 기법</br>
    - 다양한 응용 분야에서의 적용 가능성 평가를 위한 응용분야 데이터에 의한 성능 검증</br>

    한편, 이러한 연구 결과들은 스트림 형태로 정보를 발생시키는 야러 응용 분야에서 효율적으로 활용될 수 있다. 주요 활용 분야는 다음과 같다.</br>
    - 센서네트워크 환경(유비쿼터스 컴퓨팅 환경)에서의 정보 분석 : 유비쿼터스 컴퓨팅 및 센서네트워크 환경에서는 다양한 센서들로부터 방대한 양의 정보들이 지속적으로 발생된다. 이들 정보들을 실시간으로 분석하여 분석 결과에 따른 적절한 대응을 필요로 한다. 본 연구에서 개발하고자 하는 데이터 스트림에 대한 마이닝 기술은 유비쿼터스 컴퓨팅 및 센서네트워크 환경에서 발생되는 정보에 대한 실시간 분석 및 시의 적절한 대응을 위한 핵심 기술로 활용될 수 있다.</br>
    - 정보 보안 : 정보를 저장하는 각 매체에 대한 사용자의 접근 형태는 시스템 접근 로그나 시스템 사용 로그 등의 형태로 기록된다. 이러한 로그 정보는 양적 측면이나 지속적인 발생이라는 측면에서 데이터 스트림 형태를 가진다. 본 연구에서 개발하고자 하는 데이터 스트림에 대한 마이닝 기술을 활용하여 정보 저장 매체에 대한 이러한 로그 정보를 실시간으로 분석함으로써 해당 매체에서 관리하는 정보에 대한 비정상적인 접근 및 활용을 차단할 수 있다.</br>
    - 인터넷 활용도 분석, 금용 정보 분석 : 다양한 인터넷 활용 정보는 웹로그 형태로 각 시스템에 기록되며 이를 분석함으로써 해당 시스템에 접근하는 사용자들의 다영한 패턴을 분석할 수 있다. 이때, 데이터 스트림에 대한 마이닝 기술은 해당 웹로그에 대한 실시간 분석 기술을 제공함으로써 분석된 결과의 활용도를 높일 수 있다. 한편, 주식 정보와 같이 실시간으로 변화되는 다양한 금융 정보를 데이터 스트림에 대한 마이닝 기술을 적용하여 분석함으로써 분석 대상이 되는 정보의 변화 추세 및 특성을 실시간으로 분석할 수 있을 수 있으며 경제적인 이익 창출 정도를 높일 수 있다.</br>
    - 디지털 텔레비전에서의 활용 : 디지털 TV에서 실시간으로 수신되는 다채널의 방송 정보들은 방대한 정보의 양과 지속적으로 발생되는 특성 등을 고려할 때 데이터 스트림으로 간주할 수 있다. 따라서, 하나의 디지털 텔레비전을 공유하는 가정내 다수의 시청자에 대해서 다채널의 방송 스트림 중에서 개별 시청자에 의해 시청되는 방송 정보를 실시간으로 마이닝함으로써 각 시청자별 방송 컨텐츠 선호도를 분석한다. 이를 통해서 개인별 방송 선호도 특성 정보를 구축하고 다 채널에서 제공되는 방대한 양의 방송 컨텐츠 중에서 각 개인이 선호하는 컨텐츠를 선별적으로 제공하는 맞춤형 방송 서비스를 제공할 수 있다.</br>
    - LBS(위치기반시스템)에서 발생 정보 분석
  • Index terms
  • 최근 빈발 패턴, 빈발 패펀, 데이터 스트림, 정보 차별화, 감쇠율 방법, 슬라이딩 윈도우 기법, 데이터 스트림의 변화
  • List of digital content of this reports
데이터를 로딩중 입니다.
  • This document, it is necessary to display the original author and you do not have permission
    to use copyrighted material for-profit
  • In addition , it does not allow the change or secondary writings of work
데이터 이용 만족도
자료이용후 의견
입력
트위터 페이스북
NRF Daejeon
(34113) 201, Gajeong-ro, Yuseong-gu, Daejeon, Korea
Tel: 82-42-869-6114 / Fax: 82-42-869-6777
NRF Seoul
(06792) 25, Heonreung-ro, Seocho-gu, Seoul, Korea
Tel: 82-2-3460-5500 / Fax: 82-2-3460-5759
KRM Help Center
Tel : 042-710-4360
E-mail : krmcenter@nrf.re.kr / Fax : 042-861-4380