다중 최소 임계치 기반 빈발 패턴 마이닝의 성능분석

양흥모 ( Heungmo Ryang ),윤은일 ( Unil Yun ) 한국인터넷정보학회 2013 인터넷정보학회논문지 Vol.14 No.6

거대한 데이터베이스로부터 중요하고 의미 있는 정보를 찾아내기 위해 데이터 마이닝 기법들이 사용되며, 패턴 마이닝은 이러한 데이터 마이닝을 위한 중요한 기법 중에 하나이다. 패턴 마이닝은 거대 데이터베이스로부터 유용한 패턴을 찾아내는 기법이며, 패턴 마이닝 분야 중에 하나인 빈발 패턴 마이닝은 데이터베이스에서 최소 임계치 이상의 빈도수를 가지는 빈발 패턴을 마이닝 한다. 전통적인 빈발 패턴 마이닝은 전체 데이터베이스에 대한 단일 최소 임계치를 기반으로 중요 빈발 패턴을 마이닝 한다. 단일 최소 임계치 모델은 데이터베이스 내 모든 아이템이 동일한 특성을 가진다고 암묵적으로 가정한다. 그러나 실제 응용에서는 각 아이템들이 개별적인 특성을 가지고 있을 수 있으며, 따라서 이를 반영한 패턴 마이닝 기법이 요구된다. 데이터베이스 내 아이템들의 이러한 특성이 반영되지 않은 빈발 패턴 마이닝 모델에서, 중요한 희귀 아이템이 포함된 패턴을 마이닝 하기 위해서는 낮은 최소 임계치를 설정해야 한다. 그러나 너무 낮은 최소 임계치는 의미 없는 아이템들을 포함하는 수많은 패턴을 야기한다. 반대로 높은 최소 임계치는 희귀 아이템이 포함된 패턴을 마이닝 하지 못하는 희귀 아이템 문제라 불리는 딜레마가 발생한다. 이러한 문제의 해결을 위한 초기 연구들은 아이템 빈도수에 따라 데이터를 몇 개의 블록으로 분할하거나 관련 희귀 아이템들을 하나의 그룹으로 만드는 방법을 사용한 근사적 접근법을 제안하였다. 그러나 이러한 기법들은 근사적 방법의 적용에 의해 모든 희귀 패턴을 포함한 빈발 패턴을 마이닝 하지 못한다. 다중 최소 임계치를 고려한 패턴 마이닝 모델은 아이템들의 개별적인 특성을 반영하여 희귀 아이템 문제를 해결하기 위해 제안되었다. 다중 최소 임계치 기반의 빈발 패턴 마이닝 모델에서 각 아이템은 MIS (Minimum Item Support)라고 불리는 개별 최소 임계치를 가지며, 아이템들의 데이터베이스 내 빈도수를 기반으로 계산된다. 다중 최소 임계치 모델은 MIS를 통해 수많은 의미 없는 패턴을 생성하지 않고도 손실 없이 모든 희귀 빈발 패턴을 찾아낸다. 한편, 빈발 패턴을 마이닝 하는 과정에서 후보 패턴들이 생성되며, 단일 최소 임계치 모델에서는 각 후보 패턴의 빈도수가 유일한 최소 임계치와 비교된다. 따라서, 희귀 아이템 문제가 발생할 뿐만 아니라 후보 패턴을 구성하는 아이템들의 특성이 고려되지 않는다. 다중 최소 임계치 모델에서는 이 문제를 다루기 위해 후보 패턴을 구성하는 아이템들의 MIS 값 중에서 가장 작은 MIS 값을 해당 후보 패턴의 최소 임계치로 설정하여 패턴 내 아이템들의 특성을 반영한다. 이를 적용하여 효율적으로 희귀 빈발 패턴을 마이닝 하기 위해 트리 구조 기반의 알고리즘은 빈도수 내림차순으로 트리 내 아이템들을 정렬하는 단일 최소 임계치 모델과는 달리 MIS 내림차순으로 아이템들을 정렬하여 마이닝을 수행한다. 본 논문에서는 다중 최소 임계치 기반의 빈발 패턴 마이닝 알고리즘에 대한 특성을 살펴보고, 일반 단일 임계치 기반 알고리즘과의 성능평가를 수행한다. 성능평가는 실행 속도, 메모리 사용량, 그리고 확장성의 관점에서 수행된다. 성능평가 결과, 다중 최소 임계치 기반의 빈발패턴 마이닝 알고리즘은 희귀 빈발 패턴을 포함한 모든 빈발 패턴을 단일 임계치 기반의 빈발 패턴 마이닝 알고리즘보다 더 빠른 속도로 마이닝 하였으며, 각 아이템의 최소 임계치 정보를 위한 추가적인 메모리를 필요로 하였다. 또한, 비교 알고리즘들은 좋은 확장성 결과를 보였다. Data mining techniques are used to find important and meaningful information from huge databases, and pattern mining is one of the significant data mining techniques. Pattern mining is a method of discovering useful patterns from the huge databases. Frequent pattern mining which is one of the pattern mining extracts patterns having higher frequencies than a minimum support threshold from databases, and the patterns are called frequent patterns. Traditional frequent pattern mining is based on a single minimum support threshold for the whole database to perform mining frequent patterns. This single support model implicitly supposes that all of the items in the database have the same nature. In real world applications, however, each item in databases can have relative characteristics, and thus an appropriate pattern mining technique which reflects the characteristics is required. In the framework of frequent pattern mining, where the natures of items are not considered, it needs to set the single minimum support threshold to a too low value for mining patterns containing rare items. It leads to too many patterns including meaningless items though. In contrast, we cannot mine any pattern if a too high threshold is used. This dilemma is called the rare item problem. To solve this problem, the initial researches proposed approximate approaches which split data into several groups according to item frequencies or group related rare items. However, these methods cannot find all of the frequent patterns including rare frequent patterns due to being based on approximate techniques. Hence, pattern mining model with multiple minimum supports is proposed in order to solve the rare item problem. In the model, each item has a corresponding minimum support threshold, called MIS (Minimum Item Support), and it is calculated based on item frequencies in databases. The multiple minimum supports model finds all of the rare frequent patterns without generating meaningless patterns and losing significant patterns by applying the MIS. Meanwhile, candidate patterns are extracted during a process of mining frequent patterns, and the only single minimum support is compared with frequencies of the candidate patterns in the single minimum support model. Therefore, the characteristics of items consist of the candidate patterns are not reflected. In addition, the rare item problem occurs in the model. In order to address this issue in the multiple minimum supports model, the minimum MIS value among all of the values of items in a candidate pattern is used as a minimum support threshold with respect to the candidate pattern for considering its characteristics. For efficiently mining frequent patterns including rare frequent patterns by adopting the above concept, tree based algorithms of the multiple minimum supports model sort items in a tree according to MIS descending order in contrast to those of the single minimum support model, where the items are ordered in frequency descending order. In this paper, we study the characteristics of the frequent pattern mining based on multiple minimum supports and conduct performance evaluation with a general frequent pattern mining algorithm in terms of runtime, memory usage, and scalability. Experimental results show that the multiple minimum supports based algorithm outperforms the single minimum support based one and demands more memory usage for MIS information. Moreover, the compared algorithms have a good scalability in the results.

상위 K 하이 유틸리티 패턴 마이닝 기법 성능분석

양흥모 ( Heungmo Ryang ),윤은일 ( Unil Yun ),김철홍 ( Chulhong Kim ) 한국인터넷정보학회 2015 인터넷정보학회논문지 Vol.16 No.6

전통적인 빈발 패턴 마이닝은 데이터베이스로부터 사용자 정의 최소 임계치 이상의 빈도수를 가지는 유효 패턴들을 식별한다. 적절한 임계치 설정은 해당 도메인에 대한 사전 지식을 요구하므로 쉬운 작업이 아니다. 따라서 임계치 설정을 통한 마이닝 결과의 정밀한 제어 불가능으로 인해 도메인 지식을 기반으로 하지 않는 패턴 마이닝 방법이 필요하게 되었다. 상위 K 빈발 패턴 마이닝은 이러한 문제를 해결하기 위해 제안되었으며, 임계치 설정 없이 상위 K개의 중요 패턴들을 마이닝 한다. 사용자는 이를 적용함으로써 데이터베이스에 상관없이 가장 높은 빈도수의 패턴부터 K번째로 높은 빈도수의 패턴까지 찾아낼 수 있다. 비록 상위 K 빈발 패턴 마이닝이 임계치 설정 없이 상위 K개의 중요 패턴들을 마이닝 하지만, 트랜잭션 내 아이템 수량과 데이터베이스 내 서로 다른 아이템 중요도를 고려하지 못하여 많은 실세계 응용의 요구에 부합하지 못한다. 하이 유틸리티 패턴 마이닝은 아이템 중요도가 포함된 비 바이너리 데이터베이스의 특성을 고려하기 위해 제안되었으나 최소 임계치를 필요로 한다. 최근 임계치 설정 없는 하이 유틸리티 패턴 마이닝을 위한 상위 K 하이 유틸리티 패턴 마이닝이 개발되었으며, 이를 통해 사용자는 사전 지식 없이 원하는 수의 패턴을 마이닝 할 수 있다. 본 논문은 상위 K 하이 유틸리티 패턴 마이닝을 위한 알고리즘을 분석한다. 최신 알고리즘에 대한 성능분석을 통해 개선사항 및 발전 방향에 대해 고찰한다. Traditional frequent pattern mining discovers valid patterns with no smaller frequency than a user-defined minimum threshold from databases. In this framework, an enormous number of patterns may be extracted by a too low threshold, which makes result analysis difficult, and a too high one may generate no valid pattern. Setting an appropriate threshold is not an easy task since it requires the prior knowledge for its domain. Therefore, a pattern mining approach that is not based on the domain knowledge became needed due to inability of the framework to predict and control mining results precisely according to the given threshold. Top-k frequent pattern mining was proposed to solve the problem, and it mines top-k important patterns without any threshold setting. Through this method, users can find patterns from ones with the highest frequency to ones with the k-th highest frequency regardless of databases. In this paper, we provide knowledge both on frequent and top-k pattern mining. Although top-k frequent pattern mining extracts top-k significant patterns without the setting, it cannot consider both item quantities in transactions and relative importance of items in databases, and this is why the method cannot meet requirements of many real-world applications. That is, patterns with low frequency can be meaningful, and vice versa, in the applications. High utility pattern mining was proposed to reflect the characteristics of non-binary databases and requires a minimum threshold. Recently, top-k high utility pattern mining has been developed, through which users can mine the desired number of high utility patterns without the prior knowledge. In this paper, we analyze two algorithms related to top-k high utility pattern mining in detail. We also conduct various experiments for the algorithms on real datasets and study improvement point and development direction of top-k high utility pattern mining through performance analysis with respect to the experimental results.

슬라이딩 윈도우 기반의 스트림 하이 유틸리티 패턴 마이닝 기법 성능분석

양흥모 ( Heungmo Ryang ),윤은일 ( Unil Yun ) 한국인터넷정보학회 2016 인터넷정보학회논문지 Vol.17 No.6

최근 무선 센서 네트워크, 사물 인터넷, 소셜 네트워크 서비스와 같은 다양한 응용 분야에서 대용량 스트림 데이터가 실시간으로 생성되고 있으며, 효율적인 기법을 통해 처리 및 분석하여 유용한 정보를 찾아내고, 이를 의사 결정을 위해 사용할 수 있도록 하는 것은 중요한 이슈 중에 하나이다. 스트림 데이터는 끊임없이 빠른 속도로 생성되므로 최소한의 접근을 통해 처리해야 하며, 신속한 저전력 처리를 필요로 하는 자원이 제한된 환경에서 분석될 수 있도록 적합한 기법이 요구된다. 이러한 문제를 해결하기 위해, 슬라이딩 윈도우 개념이 제안되어 연구되고 있다. 한편, 대용량 데이터로부터 의미 있는 정보를 찾아내기 위한 데이터 마이닝 기법 중에 하나인 패턴 마이닝은 중요 정보를 패턴 형태로 추출한다. 전통적인 빈발 패턴 마이닝은 이진 데이터베이스를 대상으로 하고 모든 아이템을 동일한 중요도로 고려함으로써 데이터 마이닝 분야에서 중요한 역할을 수행해 왔지만, 실제 데이터 특성을 반영하지 못하는 단점을 지닌다. 하이 유틸리티 패턴 마이닝은 비 이진 데이터베이스로부터 상대적인 아이템 중요도를 반영하여 더욱 의미 있는 정보를 찾아내기 위해 제안되었다. 정적 데이터를 대상으로 하는 하이 유틸리티 패턴 마이닝 기법은 그러나 스트림 데이터 처리에 적합하지 못하다. 제한된 환경에서 스트림 데이터의 특성을 반영하고 효율적으로 처리하여 중요한 정보를 찾아내기 위해 슬라이딩 윈도우 기반의 접근법이 제안되었다. 본 논문은 슬라이딩 윈도우 기반 하이 유틸리티 패턴 마이닝 기법들의 성능을 평가하고 분석하여 해당 기법들의 특성 및 발전 방향을 고찰한다. Recently, huge stream data have been generated in real time from various applications such as wireless sensor networks, Internet of Things services, and social network services. For this reason, to develop an efficient method have become one of significant issues in order to discover useful information from such data by processing and analyzing them and employing the information for better decision making. Since stream data are generated continuously and rapidly, there is a need to deal with them through the minimum access. In addition, an appropriate method is required to analyze stream data in resource limited environments where fast processing with low power consumption is necessary. To address this issue, the sliding window model has been proposed and researched. Meanwhile, one of data mining techniques for finding meaningful information from huge data, pattern mining extracts such information in pattern forms. Frequency-based traditional pattern mining can process only binary databases and treats items in the databases with the same importance. As a result, frequent pattern mining has a disadvantage that cannot reflect characteristics of real databases although it has played an essential role in the data mining field. From this aspect, high utility pattern mining has suggested for discovering more meaningful information from non-binary databases with the consideration of the characteristics and relative importance of items. General high utility pattern mining methods for static databases, however, are not suitable for handling stream data. To address this issue, sliding window based high utility pattern mining has been proposed for finding significant information from stream data in resource limited environments by considering their characteristics and processing them efficiently. In this paper, we conduct various experiments with datasets for performance evaluation of sliding window based high utility pattern mining algorithms and analyze experimental results, through which we study their characteristics and direction of improvement.