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

장중혁(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.

WIS: Weighted Interesting Sequential Pattern Mining with a Similar Level of Support and/or Weight

윤은일 한국전자통신연구원 2007 ETRI Journal Vol.29 No.3

Sequential pattern mining has become an essential task with broad applications. Most sequential pattern mining algorithms use a minimum support threshold to prune the combinatorial search space. This strategy provides basic pruning; however, it cannot mine correlated sequential patterns with similar support and/or weight levels. If the minimum support is low, many spurious patterns having items with different support levels are found; if the minimum support is high, meaningful sequential patterns with low support levels may be missed. We present a new algorithm, weighted interesting sequential (WIS) pattern mining based on a pattern growth method in which new measures, sequential s-confidence and w-confidence, are suggested. Using these measures, weighted interesting sequential patterns with similar levels of support and/or weight are mined. The WIS algorithm gives a balance between the measures of support and weight, and considers correlation between items within sequential patterns. A performance analysis shows that WIS is efficient and scalable in weighted sequential pattern mining.

시간간격 유틸리티에 기반한 효과적인 순차 패턴 마이닝 알고리즘

이경훈,최우식,이민재,이석룡 한국정보과학회 2015 데이타베이스 연구 Vol.31 No.1

Sequential pattern mining methods using the frequency and quantity of items have been studied, and recently, utility sequential pattern mining methods based on a utility index are actively investigated, which also consider the profit of items to find effective sequential patterns. However, the existing utility-based methods are not able to handle various types of sequential patterns in reality as they do not consider the time interval between occurrences of items. Noticing these problems, we present a new index that considers the time interval in addition to current indices. The proposed algorithm is designed to recognize the effective sequential patterns that reflect the time value by filtering the patterns with little or weak relevance, due to long-time interval between the items. Experimental results demonstrate that the proposed method identifies the relevant sequential patterns more effectively than the traditional sequential pattern mining and utility-based methods, by eliminating the patterns that have weak relevance in terms of time intervals. 아이템의 출현빈도와 수량에 기초한 순차패턴 마이닝에 대한 연구가 활발히 이루어져 왔으며, 최근 들어 아이템의 고유한 가치(profit)를 고려한 유틸리티(utility) 지표를 척도로 사용하는 유틸리티한 순차패턴 기법이 활발히 연구되고 있다. 그러나 유틸리티 지표는 아이템들이 발생하는 시간간격에 대해서는 고려하지 않기 때문에 서로 다른 시간간격을 두고 발생하는 다양한 현실 상황을 반영하기 어렵다. 본 논문에서는 이러한 문제점에 착안하여 시간간격을 반영한 새로운 지표를 제시한다. 제안한 알고리즘에서는 기존의 유틸리티 순차패턴 마이닝 기법에서 유효한 결과로 간주되었던 순차패턴이라 하더라도 아이템 간 시간간격이 큰 중요하지 않은 패턴들을 제외함으로써 유효한 순차패턴을 찾아낸다. 실험 결과, 제안한 알고리즘은 기존의 기법에 비해 시간적 측면에서 유효하지 않은 순차패턴들을 적절히 검출하여 제외함으로써 현실적으로 효용성 있는 순차패턴들을 도출하였다.

A Novel Approach for Mining High-Utility Sequential Patterns in Sequence Databases Chowdhury Farhan Ahmed, Syed Khairuzzaman Tanbeer, and Byeong-Soo Jeong, ETRI Journal, vol.32, no.5, Oct. 2010, pp.676-686.

아메드파한,Syed Khairuzzaman Tanbeer,Byeong-Soo Jeong 한국전자통신연구원 2010 ETRI Journal Vol.32 No.5

Mining sequential patterns is an important research issue in data mining and knowledge discovery with broad applications. However, the existing sequential pattern mining approaches consider only binary frequency values of items in sequences and equal importance/significance values of distinct items. Therefore, they are not applicable to actually represent many real-world scenarios. In this paper, we propose a novel framework for mining high- utility sequential patterns for more real-life applicable information extraction from sequence databases with non-binary frequency values of items in sequences and different importance/significance values for distinct items. Moreover, for mining high-utility sequential patterns, we propose two new algorithms: UtilityLevel is a high-utility sequential pattern mining with a level-wise candidate generation approach, and UtilitySpan is a high-utility sequential pattern mining with a pattern growth approach. Extensive performance analyses show that our algorithms are very efficient and scalable for mining high-utility sequential patterns.

근사 알고리즘을 이용한 순차패턴 탐색

산사볼트가람라흐차(Garawagchaa Sarlsarbold),황영섭(Young-Sup Hwang) 한국컴퓨터정보학회 2009 韓國컴퓨터情報學會論文誌 Vol.14 No.5

서열데이터베이스에 있는 자주 발현하는 부분 서열을 패턴으로 찾아내는 순차패턴 탐색은 넓은 응용 분야를 가지는 중요한 데이터 마이닝 문제이다. DNA 서열에서 순차패턴이 모티프가 될 수 있으므로 DNA 서열에서 순차패턴을 찾는 것을 연구하였다. 대부분의 기존 마이닝 방법은 순차패턴의 정의에 따라 정확한 정합에 주력하여 노이즈가 있는 환경이나 실제 문제에서 발생하는 부정확한 데이터에 대하여 제대로 작동하지 않을 수 있다. 이러한 문제가 생물 데이터인 DNA 서열에서 자주 나타난다. 이러한 문제를 다루기 위한 근사 정합 방법을 연구하였다. 본 연구의 아이디어는 자주 발생하는 패턴을 근사 패턴이라 부르는 그룹으로 분류할 수 있다는 관찰에서 기반을 둔다. 기존의 Prefixspan 알고리즘은 주어진 긴 서열에서 순차패턴을 잘 찾을 수 있다. 본 연구는 Prefixspan 알고리즘을 개선하여 유사한 순차패턴을 찾을 수 있게 하였다. 실험 결과는 PreFixSpan보다 제안한 방법이 패턴 길이가 4일 때, 근사 순차패턴의 빈도가 5배 높아짐을 보였다. Sequential pattern mining, which discovers frequent subsequences as patterns in a sequence database, is an important data mining problem with broad applications. Since a sequential pattern in DNA sequences can be a motif, we studied to find sequential patterns in DNA sequences. Most previously proposed mining algorithms follow the exact matching with a sequential pattern definition. They are not able to work in noisy environments and inaccurate data in practice. Theses problems occurs frequently in DNA sequences which is a biological data. We investigated approximate matching method to deal with those cases. Our idea is based on the observation that all occurrences of a frequent pattern can be classified into groups, which we call approximated pattern. The existing PrefixSpan algorithm can successfully find sequential patterns in a long sequence. We improved the PrefixSpan algorithm to find approximate sequential patterns. The experimental results showed that the number of repeats from the proposed method was 5 times more than that of PrefixSpan when the pattern length is 4.

Anomalous Event Detection in Traffic Video Based on Sequential Temporal Patterns of Spatial Interval Events

( Ashok Kumar P. M ),( Vaidehi. V ) 한국인터넷정보학회 2015 KSII Transactions on Internet and Information Syst Vol.9 No.1

Detection of anomalous events from video streams is a challenging problem in many video surveillance applications. One such application that has received significant attention from the computer vision community is traffic video surveillance. In this paper, a Lossy Count based Sequential Temporal Pattern mining approach (LC-STP) is proposed for detecting spatio-temporal abnormal events (such as a traffic violation at junction) from sequences of video streams. The proposed approach relies mainly on spatial abstractions of each object, mining frequent temporal patterns in a sequence of video frames to form a regular temporal pattern. In order to detect each object in every frame, the input video is first pre-processed by applying Gaussian Mixture Models. After the detection of foreground objects, the tracking is carried out using block motion estimation by the three-step search method. The primitive events of the object are represented by assigning spatial and temporal symbols corresponding to their location and time information. These primitive events are analyzed to form a temporal pattern in a sequence of video frames, representing temporal relation between various object`s primitive events. This is repeated for each window of sequences, and the support for temporal sequence is obtained based on LC-STP to discover regular patterns of normal events. Events deviating from these patterns are identified as anomalies. Unlike the traditional frequent item set mining methods, the proposed method generates maximal frequent patterns without candidate generation. Furthermore, experimental results show that the proposed method performs well and can detect video anomalies in real traffic video data.

정량 정보를 포함한 순차 패턴 마이닝 알고리즘

김철연(Chulyun Kim),임종화(Jong-Hwa Lim),Raymond T. Ng,심규석(Kyuseok Shim) 한국정보과학회 2006 정보과학회논문지 : 데이타베이스 Vol.33 No.5

순차 패턴을 찾는 것은 데이타마이닝 응용분야에서 중요한 문제이다. 기존의 순차 패턴 마이닝 알고리즘들은 아이템으로만 이루어진 순차 패턴만을 취급하였으나 경제나 과학분야와 같은 많은 분야에서는 정량 정보가 아이템과 같이 기록되어 있으며, 기존의 알고리즘이 처리하지 못하는 이러한 정량 정보는 사용자에게 보다 유용한 정보를 전달하여 줄 수 있다 본 논문에서는 정량 정보를 포함한 순차패턴 마이닝 문제를 제안하였다. 기존의 순차패턴 알고리즘에 대한 단순한 확장으로는 모든 정량에 대한 후보 패턴들을 모두 생성하기 때문에 확대된 탐색 공간을 효율적으로 탐색할 수 없음을 보이고, 이러한 단순한 확장 알고리즘의 성능을 대폭 향상시키기 위하여 정량정보에 대해 해쉬 필터링과 정량 샘플링 기법을 제안하였다. 다양한 실험 결과들은 제안된 기법들이 단순히 확장된 알고리즘과 비교하여 수행시간을 매우 단축시켜 줄 뿐만 아니라, 데이타베이스 크기에 대한 확장성 또한 향상시켜줌을 보여 준다. Discovering sequential patterns is an important problem for many applications. Existing algorithms find sequential patterns in the sense that only items are included in the patterns. However, for many applications, such as business and scientific applications, quantitative attributes are often recorded in the data, which are ignored by existing algorithms but can provide useful insight to the users. In this paper, we consider the problem of mining sequential patterns with quantities. We demonstrate that naive extensions to existing algorithms for sequential patterns are inefficient, as they mayenumerate the search space blindly. Thus, we propose hash filtering and quantity sampling techniques that significantly improve the performance of the naive extensions. Experimental results confirm that compared with the naive extensions, these schemes not only improve the execution time substantially but also show better scalability for sequential patterns with quantities.

Application of Gap-Constraints Given Sequential Frequent Pattern Mining for Protein Function Prediction

박현아,김태욱,Meijing Li,손호선,박정석,류근호 질병관리본부 2015 Osong Public Health and Research Persptectives Vol.6 No.2

Objectives: Predicting protein function from the proteineprotein interaction network is challenging due to its complexity and huge scale of protein interaction process along with inconsistent pattern. Previously proposed methods such as neighbor counting, network analysis, and graph pattern mining has predicted functions by calculating the rules and probability of patterns inside network. Although these methods have shown good prediction, difficulty still exists in searching several functions that are exceptional from simple rules and patterns as a result of not considering the inconsistent aspect of the interaction network. Methods: In this article, we propose a novel approach using the sequential pattern mining method with gap-constraints. To overcome the inconsistency problem, we suggest frequent functional patterns to include every possible functional sequence-including patterns for which search is limited by the structure of connection or level of neighborhood layer. We also constructed a tree-graph with the most crucial interaction information of the target protein, and generated candidate sets to assign by sequential pattern mining allowing gaps. Results: The parameters of pattern length, maximum gaps, and minimum support were given to find the best setting for the most accurate prediction. The highest accuracy rate was 0.972, which showed better results than the simple neighbor counting approach and link-based approach. Conclusion: The results comparison with other approaches has confirmed that the proposed approach could reach more function candidates that previous methods could not obtain.

Classification and Sequential Pattern Analysis for Improving Managerial Efficiency and Providing Better Medical Service in Public Healthcare Centers

최근호,정석훈,이현실,서용무 대한의료정보학회 2010 Healthcare Informatics Research Vol.16 No.2

Objectives: This study sought to find answers to the following questions: 1) Can we predict whether a patient will revisit a healthcare center? 2) Can we anticipate diseases of patients who revisit the center? Methods: For the first question, we applied 5 classification algorithms (decision tree, artificial neural network, logistic regression, Bayesian networks, and Naïve Bayes) and the stacking-bagging method for building classification models. To solve the second question, we performed sequential pattern analysis. Results: We determined: 1) In general, the most influential variables which impact whether a patient of a public healthcare center will revisit it or not are personal burden, insurance bill, period of prescription, age, systolic pressure, name of disease, and postal code. 2) The best plain classification model is dependent on the dataset. 3) Based on average of classification accuracy, the proposed stacking-bagging method outperformed all traditional classification models and our sequential pattern analysis revealed 16 sequential patterns. Conclusions: Classification models and sequential patterns can help public healthcare centers plan and implement healthcare service programs and businesses that are more appropriate to local residents, encouraging them to revisit public health centers.

규칙성기반 놀이가 발달지체유아의 순차처리정도에 미치는 영향

구효진,정미영,조영득 한국유아특수교육학회 2015 유아특수교육연구 Vol.15 No.2

The aim of this study was to investigate the sequential processing of young children with developmental delays, and figure out positive effect of the pattern-based play for on the ability of sequential processing of young children with developmental delays. 38 participants were involved from 7 nurseries in Gyeonggi-do, Chungcheongbuk-do and Chungcheongnam-do. The participants were divided into two groups as experimental group(N=19) and control group(N=19). A pretest-posttest control group design was used. The results of this study were as follows; First of all, there is a significant difference between the mean of sequential processing of young children with developmental delays and the norm group. Secondly, the mean of sequential processing of experimental group was significantly improved. Lastly, according to the results of post-test, the mean of sequential processing of experimental group was significantly higher than that of control group. The importance of developing teaching methods and contents relates to sequential processing has suggested. 본 연구는 발달지체유아의 인지처리과정 중 순차처리와 관련 된 특성을 알아보고 규칙성기반 놀이가 해당 유아의 순차처리 및 하위영역(손동작, 수 회생, 단어배열)에 미치는 영향을 파악하기 위해 실시되었다. 이를 위해 경기도와 충청남북도 내 7개 장애전담어린이집에서 38명(실험집단 N=19, 통제집단 N=19)의 발달지체유아들이 연구대상으로 참여하였으며 실험집단에 포함 된 발달지체 유아에게는 주2회 40분씩 총 12회기의 규칙성기반 놀이 관련 프로그램이 적용 되었다. 이에 대한 연구결과는 다음과 같다. 첫째, 발달지체유아의 순차처리와 전반적인 하위영역(손동작, 수 회생, 단어배열)의 점수는 또래 규준집단과 비교했을 때 유의미하게 낮은 것으로 보고되었다. 둘째, 사후검사 결과, 규칙성기반 놀이가 적용 된 실험집단 내 발달지체유아들의 순차처리 정도가 사전에 비해 유의미하게 향상되었다. 셋째, 실험집단 내 발달지체유아들의 사후검사 점수는 통제집단 유아들에 비해 유의하게 높은 것으로 나타났다. 이러한 결과를 통해 규칙성기반 놀이가 발달지체유아들의 전반적인 순차처리 및 해당 하위영역 처리능력 향상에 효과적인 교수방법으로 사용될 수 있음이 시사되었다.