Progress in various hardware and sensor technology has made new kind of management for data emerge. These data, being generated and growing over time continuously and rapidly, are referred to stream data. Stream data became a challenge for Knowledge Discovery and Data mining (KDD) due to their large size and dynamics in generation and processing. Even high-dimensional attributes and multi-valued categorical values found in recent stream data issues a new challenge in management and processing of them.
When processing stream data, three aspects should be considered. First, the size of stream data is very large to fit a limited system memory. Second, stream data is seriously affected by time because it emerges in time line and the characteristics of it are subject to be changed. Furthermore, recent applications of stream data require more sophisticated processes on complicated data format like summarizing or finding hidden knowledge in it, not only simple data management or filtering process. Based on factors of processing of stream data, we suggested a sampling for limited memory, a clustering method for multi-valued categorical data in high-dimension space, and a method to detect evolution of characteristics of data and learn from it.
We suggest a sampling method reflecting time feature of stream data based on Quantile system. The importance of data is apt to be dependent on data arrival rate. Our method samples more data in the data interval with high arrival rate. Our sampling method can be applied to sophisticated knowledge applications such as clustering from multi-sources and help them to reflect the characteristics of stream data effectively.
We propose an effective method to quantify the level of dissimilarity of categorical values and developed a framework of unsupervised learning for high dimensional categorical data. Clustering is the most representative unsupervised learning in KDD to group similar data and to find out hidden information about the characteristics of dataset for the further analysis. Any method of grouping requires having an understanding for how similar objects are to each other. The concept of similarity and dissimilarity of objects is decisive factor to measure of the quality of clustering results as well. When attributes of data are categorical and especially high dimensional, it is not simple to determine the level of dissimilarity of data objects, which have synonymous values or unimportant attributes. The new similarity measure CATCH is to quantify the level of dissimilarity of categorical values and to weigh the implicit influence of each attribute on grouping a particular cluster. We exploit distributional information of data correlated to each categorical value to discover intrinsic relationship of values and distributional information of values in a cluster to measure significance of attributes to contribute to construct each cluster dynamically.
In processing stream data, time is one of the most significant facts to consider not only because the size of data is dramatically increased but because the characteristics of data are varying over time. Especially, learning tasks should be adapted to that change in order to reflect the recent information of data. For this time sensitive characteristics of stream data, we propose a window adaptation function on domain value (WAV) to determine the size of windowed batch and the method to detect the change of data characteristics with the criterion function on a multi-stream data model.
Experiments on both synthetic and real datasets show propriety and effectiveness of our methods for high dimensional categorical data. When our method is applied only to traditional clustering algorithm, the results are considerably improved. Our approach does not couple with a clustering algorithm tightly and can be applied to various algorithms flexibly as well. When applying on a clustering task, our method for evolving data determines the effective size of windowed batches. Our criterion function with correlation information of data value distribution over time showed the reasonable threshold to detect the change between windowed batches.
하드웨어와 센서 기술 그리고 다양한 응용 분야의 발전은 시간의 흐름에 따라 지속적이고 빠르게데이터를 생산하게 되었으며, 이러한 형태의 데이터를 스트림 데이터라고 한다. 스트림 형태로 생산되는 데이터의 매우 큰 용량과 시간에 따른 동적인 속성은 이들 데이터에 대한 데이터 마이닝 분야에 도전이 되고 있다. 요즘의 스트림 데이터에서는 고차원의 다중 범주 값과 같은 복잡한 형태의 속성도 발견되고 있어 이들을 효과적으로 처리하기 위한 방법에 대한 연구가 필요하다. 최근의 스트림 데이터를 처리함에 있어 고려해야 할 중요한 속성은 시스템 메모리에 비해 대용량이라는 점, 시간 속성에 동적으로 영향을 받는 점, 그리고 고차원의 다중 범주와 같은 일반적이지 않는 값을 가지는 점이다. 본 논문에서는 이러한 스트림 데이터의 속성을 고려한 효과적인 학습 프로세스를 위해 세가지 부분에 대한 접근 방법을 제안한다.
먼저, 스트림 데이터의 시간 속성을 반영한 퀀타일 시스템 기반의 실시간 샘플링 방법을 제안한다. 윈도우 모델의 스트림 데이터에서 도착하는 각 데이터들의 속도 속성을 기반으로 스트림 내 중요한 장소 (Hot spot)에서 더 많은 데이터를 추출하도록 퀀타일의 크기를 조정한다. 본 연구에서 제안하는 방법은 윈도우의 크기를 기반으로 각 데이터가 도착할 때 마다 실시간으로 해당 데이터를 선택할 수 있으므로 실시간 샘플링을 가능하게 한다. 또한, 다차원 다중 범주값에 대해 대표적인 마이닝 기법인 클러스터링 방법을 제안한다. 본 연구에서는 우선 다중 범주값들 사이의 유사도를 각 값들과 관련된 주변 데이터들의 분포 정보를 기반으로 효과적으로 정량화함으로 범주값들 사이에 내제된 유사도의 정도를 측정하기 위한 방법을 제안한다. 각 속성의 값들이 다른 속성의 값들과 전체 데이터 상에서 함께 등장하는 정보를 추출하고 해당 정보의 차이를 기반으로 각 송성 값들의 차이를 발견한다. 그리고 다차원 속성으로 인해 생겨나는 고차원 문제에 대해 각 클러스터 구성에 참여하는 속성의 중요도를 차별화 함으로 효과적인 해결점을 제안한다. 클러스터내 데이터들의 속성 중 다른 클러스터 내의 데이터의 값들과 가장 다른 값을 가지는 속성은 해당 클러스터를 구성함에 있어 가장 중요할 수 있다. 따라서 클러스터를 구성하면서 각 클러스터에 구성된 데이터들의 속성 값 정보와 전체 그룹의 속성 값 정보를 비교하여 각 클러스터마다 속성의 중요도를 다르게 부과한다. 끝으로, 스트림 데이터에 대해 효율적인 학습 프로세스의 적용을 위해 윈도우의 크기를 정하는 기준을 제안한다. 생산되는 각 데이터마다 학습 프로세스를 반복 적용시킴에 의해 발생되는 비효율성을 데이터 윈도우의 요약 정보에 대한 학습으로 개선할 수 있으며 이를 위해 효과적인 요약을 보장하는 윈도우 크기의 지정이 요구된다. 본 연구에서는 데이터의 도메인 정보를 기반으로 타당한 크기 측정 방법을 제안한다. 그리고 이러한 방법으로 지정된 윈도우들 사이에 발생되는 데이터의 변화를 탐지하기 위한 척도를 제안한다. 데이터의 변화는 윈도우들 내 데이터들의 값들의 상관정보로 탐지 되며, 이러한 상관 정보를 기반으로 효과적인 변화 탐지가 가능하다. 다양한 데이터 실험을 통해 본 연구에서 제안한 다차원 다중 범주 데이터에 대한 방법과 윈도우 크기 측정 방법, 그리고 데이터의 변화 탐지 척도가 효과적임을 보였다. 본 연구에서 제안한 방법들은 종합적으로 스트림 데이터에 대한 학습 시스템의 모델을 효과적으로 구축함에 활용될 수 있다.