A Data Cleansing Method for Clustering Large-Scale Transaction Databases

LOH, Woong-Kee,MOON, Yang-Sae,KANG, Jun-Gyu The Institute of Electronics, Information and Comm 2010 IEICE transactions on information and systems Vol.93 No.11

<P>In this paper, we emphasize the need for data cleansing when clustering large-scale transaction databases and propose a new data cleansing method that improves clustering quality and performance. We evaluate our data cleansing method through a series of experiments. As a result, the clustering quality and performance were significantly improved by up to 165% and 330%, respectively.</P>

ROCKET: A Robust Parallel Algorithm for Clustering Large-Scale Transaction Databases

LOH, Woong-Kee,MOON, Yang-Sae,AHN, Heejune The Institute of Electronics, Information and Comm 2011 IEICE transactions on information and systems Vol.94 No.10

<P>We propose a robust and efficient algorithm called ROCKET for clustering large-scale transaction databases. ROCKET is a divisive hierarchical algorithm that makes the most of recent hardware architecture. ROCKET handles the cases with the small and the large number of similar transaction pairs separately and efficiently. Through experiments, we show that ROCKET achieves high-quality clustering with a dramatic performance improvement.</P>

A parallel algorithm for robust fault detection in semiconductor manufacturing processes

Loh, Woong-Kee,Yun, Ju-Young Springer-Verlag 2014 CLUSTER COMPUTING Vol.17 No.3

반도체공정 이상탐지 및 클러스터링을 위한 심볼릭 표현법의 적용

노웅기(Woong-Kee Loh),홍상진(Sang Jeen Hong) 한국정보과학회 2009 정보과학회 컴퓨팅의 실제 논문지 Vol.15 No.11

반도체(semiconductor) 기술은 1950년대에 집적 회로(integrated circuit, IC)가 발명된 이후 오늘날까지 급속한 발전을 거듭하고 있다. 하나의 완전한 반도체를 제조하기 위해서는 매우 다양하고 긴공정을 거쳐야 한다. 반도체 제조 생산성을 높이기 위하여 공정들이 종료되기 전에 미리 이상(fault)을 발견하기 위한 이상탐지 및 분류(fault detection and classification, FOC)에 대한 많은 연구가 진행되고 있다. 이를 위하여 다양한 반도체 장비에 갖가지 종류의 센서를 부착하여 일정한 시간 간격으로 원하는 값을 측정한다. 이러한 측정 값은 실수 값들의 연속이므로 시계열(time- seIies) 데이터의 일종이다. 본 논문에서는 반도체 공정에서의 이상탐지 및 클러스터링을 수행하는 알고리즘을 제안한다. 제안된 알고리즘은 시계열 데이터를 심불릭 표현법(symbolic representation) 으로 변환하여 이상을 탐지하는 기존의 알고리즘을 수정한 것이다. 본 논문의 공헌은 일반적인 시계열 데이터에 대한 기존의 이상탐지 알고리즘을 수정하여 반도체 공정 데이터에 대해서도 활용할 수 있음을 보일 뿐만 아니라, 이상탐지 및 클러스터링의 정확성을 높이는 실험 결과를 제시하는 것이다. 실험 결과, 본 논문에서 제안한 알고리즘은 긍정 오류(false positive) 및 부정 오류(false negative)를 모두 발생하지 않았다. Since the invention of the integrated circuit (IC) in 1950s, semiconductor technology has undergone dramatic development up to these days. A complete semiconductor is manufactured through a diversity of processes. For better semiconductor productivity, fault detection and classification (FDC) has been rigorously studied for finding faults even before the processes are completed. For FDC, various kinds of sensors are attached in many semiconductor manufacturing devices, and sensor values are collected in a periodic manner. The collection of scnsor values consists of sequences of real numbers, and hence is regarded as a kind of time-series data. In this paper, we propose an algorithm for dctecting and clustering faults in semiconductor processes. The proposed algorithm is a modification of the existing anomaly detection algorithm dealing with symbolically-represented time-series. The contributions of this paper are: (1) showing that a modification of the existing anomaly detection algorithm dealing with general time-series could be used for semiconductor process data and (2) presenting experimental results for improving correctness of fault detection and clustering. As a result of our expeliment, the proposed algorithm caused neither false positive nor false negative.

MHEG 객체 클래스를 기반으로 하는 멀티미디어 전자 우편 시스템의 설계 및 구현

노웅기(Woong-Kee Loh),황규영(Kyu-Young Whang) 한국정보과학회 1993 한국정보과학회 학술발표논문집 Vol.20 No.2

본 논문에서는 표준화된 멀티미디어 정보 객체를 인코드/디코드하는 멤버 함수를 갖는 MHEG 객체 클래스를 정의하고, 그를 이용하여 인터네트 상에 연결된 시스템들 간의 멀티미디어 메일 시스템을 설계, 구현한다. MHEG 객체 클래스는 멀티미디어 응용 시스템에 서브시스템으로 포함되고, 멀티미디어 전자 우편 시스템은 기존의 텍스트 메일 시스템과의 호환성을 유지하며, 텍스트, 정지 영상, 오디오 등의 복합 객체로 이루어진 멀티미디어 메일을 가능하게 한다.

시계열 데이타베이스에서 인덱스 보간법을 기반으로 정규화 변환을 지원하는 서브시퀀스 매칭 알고리즘 (pp.152-154)

노웅기(Woong-Kee Loh),김상욱(Sang-Wook Kim),황규영(Kyu-Young Whang) 한국정보과학회 2000 한국정보과학회 학술발표논문집 Vol.27 No.1B

본 논문에서는 시계열 데이터베이스에서 정규화 변환을 지원하는 서브시퀀스 매칭 알고리즘을 제안한다. 정규화 변환은 시계열 데이터 간의 절대적인 유클리드 거리에 관계 없이, 구성하는 값들의 상대적인 변화 추이가 유사한 패턴을 갖는 시계열 데이터를 검색하는 데에 유용하다. 제안된 알고리즘은 몇 개의 질의 시퀀스 길이에 대해서만 각각 인덱스를 생성한 후, 이를 이용하여 모든 가능한 길이의 질의 시퀀스 길이에 대해서만 각각 인덱스를 생성한 후, 이를 이용하여 모든 가능한 길이의 질의 시퀀스에 대해서 탐색을 수행한다. 이때, 착오 기각이 발생하지 않음을 증명한다. 본 논문에서는 이와 같이 인덱스가 요구되는 모든 경우 중에서 적당한 간격의 일부에 대해서만 생성된 인덱스를 이용한 탐색 기법을 인덱스 보간법이라 부른다. 질의 시퀀스의 길이 256 ~ 512 중 다섯 개의 길이에 대해 인덱스를 생성하여 실험한 결과, 탐색 결과 선택률이 10^(-5)일 때 제안된 알고리즘의 탐색 알고리즘의 탐색 성능이 순차 검색에 비하여 평균 14.6배 개선되었다.

시계열 데이타베이스에서 임의 계수의 이동평균 변환을 지원하는 서브시퀀스 매칭 알고리즘 (pp.469-485)

노웅기(Woong-Kee Loh),김상욱(Sang-Wook Kim),황규영(Kyu-Young Whang),심규석(Kyuseok Shim) 한국정보과학회 2000 정보과학회논문지 : 데이타베이스 Vol.27 No.3

본 논문에서는 시계열 데이타베이스에서 임의 계수의 이동평균 변환을 지원하는 서브시퀀스 매칭 알고리즘을 제안한다. 이동평균 변환은 시계열 데이타 내의 잡음의 영향을 감소시킴으로써 시계열 데이타 전체의 경향을 파악하는 데에 유용하여 통계경제학 등의 분야에서 널리 사용되어 왔다. 응용 분야와 분석하려고 하는 시계열 데이타의 특성에 따라 잡음의 영향을 줄이는 정도와 경향을 파악하는 주기가 달라지므로 이동평균 계수의 선택도 달라진다. 제안된 매칭 알고리즘은 기존의 서브시퀀스 매칭 알고리즘을 확장하여 임의 계수의 이동평균 변환을 지원한다. 기존의 서브시퀀스 매칭 알고리즘을 확장 없이 그대로 응용할 경우 하나의 이동평균 계수에 대하여 하나씩의 인덱스를 생성하여야 한다. 따라서, 임의의 이동평균 계수를 지원하려면 저장 공간 및 데이타 시퀀스의 삽입/삭제 부담이 매우 심각하다. 본 논문에서는 하나의 이동평균 계수 k에 대해서 생성한 인덱스만을 이용하여 인덱스가 생성되어 있지 않은 계수 m(≤k) 에 대해서도 탐색을 수행하는 방법을 제안한다. 이때, 제안된 탐색 기법이 질의 결과로 반환되어야 할 서브시퀀스를 모두 찾아내지 못하는 착오 기각이 발생하지 않음을 증명한다. 제안된 알고리즘은 하나 이상의 이동평균 계수에 대하여 생성된 인덱스를 이용할 수도 있으며, 이때 탐색 성능의 향상을 얻을 수 있다. 실험을 통하여 제안된 알고리즘의 평균 탐색 성능을 구한 결과, 제안된 알고리즘이 순차 검색에 비하여 최대 약 2.7 배까지 우수하였다. 제안된 알고리즘의 탐색 성능은 탐색 결과 선택률이 작아질수록 향상되어, 일반적인 데이타베이스 응용에서의 효용성이 높다고 판단된다. 본 논문에서 제안된 탐색 기법은 유사한 경향을 갖는 주가 데이타의 검색, 특정 상품의 판매 예측, 기온 데이타 분석을 통한 일기 예보 등 이동평균 변환을 필요로 하는 다양한 응용 분야에 적용될 수 있다. In this paper, we propose a subsequence matching algorithm that supports moving average transform of arbitrary order in time-series databases. Moving average transform reduces the effect of noise and has been used in many areas such as econometrics since it is useful in finding the overall trends in the time-series data. The moving average order to be used varies, since the users want to control the degree of noise reduction and the frequency of analysis depending on the applications and the characteristics of data sequences. The proposed matching algorithm supports moving average transform of arbitrary order by extending the existing subsequence matching algorithm. If we applied the existing subsequence matching algorithm without any extension, we would have to generate an index per each moving average order. Thus, supporting an arbitrary moving average order would cause serious overhead on storage space and insertion/deletion of data sequences. The proposed algorithm can use only one index for a preselected moving average order k and performs subsequence matching for an arbitrary order m(≤k). We prove that the proposed algorithm causes no false dismissal, i.e., it does not miss part of the final search result. The proposed algorithm can also use more than one index for improving search performance. We have evaluated the performance of the proposed algorithm through experiments. The results show that the proposed algorithm improves the performance by up to 2.7 times on the average compared with the sequential scan algorithm. Since the proposed subsequence matching algorithm works better with smaller selectivities, it is suitable for practical applications. The proposed algorithm can be applied in a variety of areas that use the moving average transform. They include finding stock items with similar trends in prices, estimation of sales for a product, and weather forecast through temperature data analysis.

시계열 데이타베이스에서 인덱스 보간법을 기반으로 정규화 변환을 지원하는 서브시퀀스 매칭 알고리즘 (pp.217-232)

노웅기(Woong-Kee Loh),김상욱(Sang-Wook Kim),황규영(Kyu-Young Whang) 한국정보과학회 2001 정보과학회논문지 : 데이타베이스 Vol.28 No.2

본 논문에서는 시계열 데이타베이스에서 정규화 변환을 지원하는 서브시퀀스 매칭 알고리즘을제안한다. 정규화 변환은 시계열 데이타 간의 절대적인 유클리드 거리에 관계 없이, 구성하는 값들의 상대적인 변화 추이가 유사한 패턴을 갖는 시계열 데이타를 검색하는 데에 유용하다. 기존의 서브시퀀스 매칭 알고리즘을 확장 없이 정규화 변환 서브시퀀스 매칭에 단순히 응용할 경우, 질의 결과로 반환되어야 할 서브시퀀스를 모두 찾아내지 못하는 착오 기각이 발생한다. 또한, 정규화 변환을 지원하는 기존의 전체 매칭 알고리즘의 경우, 모든 가능한 질의 시퀀스 길이 각각에 대하여 하나씩의 인덱스를 생성하여야 하므로, 저장 공간 및 데이타 시퀀스 삽입/삭제의 부담이 매우 심각하다. 본 논문에서는 인덱스 보간법을 이용하여 문제를 해결한다. 인덱스 보간법은 인덱스가 요구되는 모든 경우 중에서 적당한 간격의 일부에 대해서만 생성된 인덱스를 이용하며, 인덱스가 필요한 모든 경우에 대한 탐색을 수행하는 기법이다. 제안된 알고리즘은 몇 개의 질의 시퀀스 길이에 대해서만 각각 인덱스를 생성한 후, 이를 이용하여 모든 가능한 길이의 질의 시퀀스에 대해서 탐색을 수행한다. 이때, 착오 기각이 발생하지 않음을 증명한다. 제안된 알고리즘은 질의 시에 주어진 질의 시퀀스의 길이에 따라 생성되어 있는 인덱스 중에서 가장 적절한 것을 선택하여 탐색을 수행한다. 이때, 생성되어 있는 인덱스의 개수가 많을수록 탐색 성능이 향상된다. 필요에 따라 인덱스의 개수를 변화함으로써 탐색 성능과 저장 공간 간의 비율을 유연하게 조정할 수 있다. 질의 시퀀스의 길이 256 ~ 512 중 다섯 개의 길이에 대해 인덱스를 생성하여 실험한 결과, 탐색 결과 선택률이 10^(-2)일 때 제안된 알고리즘의 탐색 성능이 순차 검색에 비하여 평균 2.40 배, 선택률이 10^(-5)일 때 평균 14.6 배 개선되었다. 제안된 알고리즘의 탐색 성능은 탐색 결과 선택률이 작아질수록 더욱 향상되므로, 실제 데이타베이스 응용에서의 효용성이 높다고 판단된다. In this paper, we propose a subsequence matching algorithm that supports normalization transform in time-series databases. Normalization transform enables finding sequences with similar patterns even though they are not close to each other in terms of the Euclidean distance. Simple application of the existing subsequence matching algorithms fails to support normalization transform since the algorithms cause false dismissal; i.e., miss part of the final search result. Moreover, the application of the existing whole matching algorithm supporting normalization transform to the subsequence matching requires an index for every possible length of the query sequence, which causes serious overhead on both storage space and time when inserting and deleting data sequences. We tackle the problem using the notion of index interpolation. Index interpolation is a searching method that uses one or more indexes generated for a few selected cases and performs searching for all cases. The proposed algorithm generates indexes only for a small number of different lengths of query sequences. For subsequence matching it selects the most appropriate index among them. We can obtain the better search performance by using more indexes. We formally prove that the proposed algorithm does not cause false dismissal. We can trade-off the search performance with storage space by adjusting the number of indexes. For performance evaluation, we conducted a series of experiments using the indexes for only five different lengths out of lengths 256 ~ 512 of the query sequence. The results show that the proposed algorithm outperforms the sequential scan up to 2.4 times on average when the selectivity of the query is 10^(-2) and up to 14.6 times when it is 10^(-5). Since the proposed algorithm performs better with smaller selectivities, it is suitable for practical situations, where the queries with smaller selectivities are much more frequent.

정규화 변환을 지원하는 스트리밍 시계열 매칭 알고리즘

노웅기(Woong-Kee Loh),문양세(Yang-Sae Moon),김영국(Young-Kuk Kim) 한국정보과학회 2006 정보과학회논문지 : 데이타베이스 Vol.33 No.6

최근에 센서 및 모바일 장비들의 발전으로 인하여 이러한 장비들로부터 생성된 대량의 데이타 스트림(data stream)의 처리가 중요한 연구 과제가 되고 있다. 데이타 스트림 중에서 연속되는 시점에 얻어진 실수 값들의 스트림을 스트리밍 시계열(streaming time-series)이라 한다. 스트리밍 시계열에 대한 유사성 매칭은 여러 가지 고유 특성에 의하여 기존의 시계열 데이타와는 다르게 처리되어야 한다. 본 논문에서는 정규화 변환(normalization transform)을 지원하는 스트리밍 시계열 매칭 문제를 해결하기 위한 효율적인 알고리즘을 제안한다. 기존에는 스트리밍 시계열을 아무런 변환 없이 비교하였으나, 본 논문에서는 정규화 변환된 스트리밍 시계열을 비교한다. 정규화 변환은 절대적인 값은 달라도 유사한 변동 경향을 가지는 시계열 데이타를 찾기 위하여 유용하다. 본 논문의 공헌은 다음과 같다. (1) 기존의 정규화 변환을 지원하는 서브시퀀스 매칭 알고리즘[4]에서 제시된 정리(theorem)를 이용하여 정규화 변환을 지원하는 스트리밍 시계열 매칭 문제를 풀기 위한 간단한 알고리즘을 제안한다. (2) 검색 성능을 향상시키기 위하여 간단한 알고리즘을 k (≥ 1) 개의 인덱스를 이용하는 알고리즘으로 확장한다. (3) 주어진 k에 대하여, 확장된 알고리즘의 검색 성능을 최대화하기 위해 k 개의 인덱스를 생성할 최적의 윈도우 길이를 선택하기 위한 근사 방법(approximation)을 제시한다. (4) 스트리밍 시계열의 연속성(continuity) 개념[8]에 기반하여, 현재 시점 t?에서의 스트리밍 서브시퀀스에 대한 검색과 동시에 미래 시점 (t? + m - 1) (m ≥ 1)까지의 검색 결과를 한번의 인덱스 검색으로 구할 수 있도록 재차 확장한 알고리즘을 제안한다. (5) 일련의 실험을 통하여 본 논문에서 제안된 알고리즘들 간의 성능을 비교하고, k 및 m 값의 변화에 따라 제안된 알고리즘들의 검색 성능 변화를 보인다. 본 논문에서 제시한 정규화 변환 스트리밍 시계열 매칭 문제에 대한 연구는 이전에 수행된 적이 없으므로 순차 검색(sequential scan) 알고리즘과 성능을 비교한다. 실험결과, 제안된 알고리즘은 순차 검색에 비하여 최대 13.2배까지 성능이 향상되었으며, 인덱스의 개수 k가 증가함에 따라 검색 성능도 함께 증가하였다. According to recent technical advances on sensors and mobile devices, processing of data streams generated by the devices is becoming an important research issue. The data stream of real values obtained at continuous time points is called streaming time-series. Due to the unique features of streaming time-series that are different from those of traditional time-series, similarity matching problem on the streaming time-series should be solved in a new way. In this paper, we propose an efficient algorithm for streaming time-series matching problem that supports normalization transform. While the existing algorithms compare streaming time-series without any transform, the algorithm proposed in the paper compares them after they are normalization-transformed. The normalization transform is useful for finding time-series that have similar fluctuation trends even though they consist of distant element values. The major contributions of this paper are as follows. (1) By using a theorem presented in the context of subsequence matching that supports normalization transform[4], we propose a simple algorithm for solving the problem. (2) For improving search performance, we extend the simple algorithm to use k ( ≥ 1) indexes. (3) For a given k, for achieving optimal search performance of the extended algorithm, we present an approximation method for choosing k window sizes to construct k indexes. (4) Based on the notion of continuity[8] on streaming time-series, we further extend our algorithm so that it can simultaneously obtain the search results for m ( ≥ 1) time points from present t? to a time point (t? + m - 1) in the near future by retrieving the index only once. (5) Through a series of experiments, we compare search performances of the algorithms proposed in this paper, and show their performance trends according to k and m values. To the best of our knowledge, since there has been no algorithm that solves the same problem presented in this paper, we compare search performances of our algorithms with the sequential scan algorithm. The experiment result showed that our algorithms outperformed the sequential scan algorithm by up to 13.2 times. The performances of our algorithms should be more improved, as k is increased.

멀티미디어 내용기반 검색을 위한 빠른 k - 최근접 객체 탐색 알고리즘

노웅기(Woong-Kee Loh),황규영(Kyu-Young Whang) 한국정보과학회 1997 한국정보과학회 학술발표논문집 Vol.24 No.2Ⅰ

k-최근접 객체 질의는 주어진 질의 점에서 가장 가까운 k개의 객체를 찾는 질의로서 멀티미디어 내용기반 검색 분야에서 가장 중요한 질의 중의 하나이다. 본 논문에서는 기존 알고리즘들의 문제점을 해결하기 위하여 새로운 k-최근접 객체 탐색 알고리즘을 제안한다. 제안된 알고리즘은 최소 비용 분기와 한정(least cost branch and bound) 기법을 이용하여 동적인 데이타베이스 환경에서 인덱스 구조에 저장된 데이타를 검색한다. 그리고 약간의 에러를 허용함으로써 고차원 데이타에 대한 탐색 성능을 크게 향상시킬 수 있는 근사 탐색(approximate search) 기법과 이를 위한 가지치기 전략을 제시한다. 임의 생성 데이타를 이용한 실험 결과 제안된 알고리즘의 성능은 기존의 알고리즘에 비하여 최고 34.5% 향상되었다. 그리고, 제안된 근사 탐색의 성능은 절대 탐색에 비하여 최고 92.0%까지 향상되었다.