Earticle

확장된 데이터 표현의 주요 목표는 유비쿼터스 환경에서 일반적인 문제에 적합한 데이터 구조를 개발하는 것이다. 이 방법의 가장 큰 특징은 속성 값을 확률로 표현할 수 있다는 것이다. 다음 특성은 훈련 데이터의 각 이벤트가 중요도를 나타내는 가중치 값을 갖도록 한다는 것이다. 데이터 구조가 개발된 후에 이를 학습할 수 있는 알고리즘이 고안된다. 그 동안 이 알고리즘은 여러 분야에서 여러 문제에 적용하여 좋은 결과를 산출해 왔다. 본 논문은 먼저 데이터 표현 기법인 UChoo를 소개하고 이론적인 배경이 되는 규칙 개선 문제를 소개한다. 그리고 규칙 개선, 손실 데이터 처리, BEWS 문제, 앙상블 시스템과 같은 응용 분야의 예를 소개한다.

The main goal of extended data expression is to develop a data structure suitable for common problems in ubiquitous environments. The greatest feature of this method is that the attribute values can be represented with probability. The next feature is that each event in the training data has a weight value that represents its importance. After this data structure has been developed, an algorithm has been devised that can learn it. In the meantime, this algorithm has been applied to various problems in various fields to obtain good results. This paper first introduces the extended data expression technique, UChoo, and rule refinement method, which are the theoretical basis. Next, this paper introduces some examples of application areas such as rule refinement, missing data processing, BEWS problem, and ensemble system.

본 논문은 불완전한 데이터를 처리하기 위해 본래 규칙개선 문제를 위해 고안되었던 데이터 확장 기법을 사용한다. 이 기법은 사건마다 중요도를 의미하는 가중치를 가질 수 있으며 각 변수를 확률값으로 나타낼 수 있는 특징이 있다. 본 논문에서의 핵심 문제가 손실값과 가장 근사한 확률을 구하여 손실값을 확률로 대치하는 것이므로, 3가지 다른 알고리즘으로 손실값에 대한 확률을 구한 후 이 데이터 구조의 형식으로 저장한다. 그리고 각각의 확률 구조에 대한 평가를 위해 SVM 분류 알고리즘으로 각각의 정보 영역을 분류하는 학습을 한 후, 본래의 정보와 비교하여 얼마나 서로 일치하느냐를 측정한다. 손실값의 대치 확률을 위한 3가지 알고리즘들은 같은 데이터 구조를 사용하고 있으나 접근 방법에서는 서로 다른 특징을 가지고 있어 적용 분야에 따라 다양한 용도로 이용될 수 있기를 기대한다.

This paper uses a data extension technique originally designed for the rule refinement problem to handling incomplete data. This technique is characterized in that each event can have a weight indicating importance, and each variable can be expressed as a probability value. Since the key problem in this paper is to find the probability that is closest to the missing value and replace the missing value with the probability, three different algorithms are used to find the probability for the missing value and then store it in this data structure format. And, after learning to classify each information area with the SVM classification algorithm for evaluation of each probability structure, it compares with the original information and measures how much they match each other. The three algorithms for the imputation probability of the missing value use the same data structure, but have different characteristics in the approach method, so it is expected that it can be used for various purposes depending on the application field.

본 논문은 불완전한 데이터를 처리하기 위해 2가지의 서로 다른 기법과 이를 학습하는 알고리즘을 소개한다. 첫째방법은 손실변수가 가질 수 있는 균등한 확률로 손실값을 할당하여 불완전한 데이터를 처리하고, SVM 알고리즘으 로 이 데이터를 학습하는 것이다. 이 기법은 임의의 변수에 손실 값의 빈도가 높을수록 엔트로피가 높도록 하여 이 변수 가 결정트리에서 선택되지 않도록 하는 것이다. 이 방법은 손실 변수에 남아있는 정보를 모두 무시하고 새로운 값을 할당한다는 특징이 있다. 이에 반해 새로운 방법은 손실 값을 제외하고 남아있는 정보로 엔트로피 확률을 구하고 이를 손실 변수의 추정 값으로 사용하는 것이다. 즉, 불완전한 학습데이터로부터 소실되지 않은 많은 정보들을 이용해 소실된 일부 정보를 복구하고 딥러닝을 이용해 학습한다. 이 2가지 방법은 학습데이터에서 차례로 변수 하나를 선택하고, 이 변수에 손실된 데이터의 비율을 달리하면서 서로 다른 측정값들의 결과들과 반복적으로 비교함으로써 성능을 측정한다.

This paper introduces two different techniques for dealing with incomplete data and algorithms for learning this data. The first method is to process the incomplete data by assigning the missing value with equal probability that the missing variable can have, and learn this data with the SVM. This technique ensures that the higher the frequency of missing for any variable, the higher the entropy so that it is not selected in the decision tree. This method is characterized by ignoring all remaining information in the missing variable and assigning a new value. On the other hand, the new method is to calculate the entropy probability from the remaining information except the missing value and use it as an estimate of the missing variable. In other words, using a lot of information that is not lost from incomplete learning data to recover some missing information and learn using deep learning. These two methods measure performance by selecting one variable in turn from the training data and iteratively comparing the results of different measurements with varying proportions of data lost in the variable.

제안 모델은 소실 데이터를 포함하는 불완전한 데이터에서 정보의 손실을 최소화할 수 있도록 개발되었다. 이를 위한 과정은 우선 데이터 확장기법을 이용하여 손실 정보를 보상하도록 학습 데이터를 변환한다. 이 변환 과정에서 데이터 의 속성값은 원-핫 인코딩으로 이진 또는 확률값으로 채워진다. 다음 이 변환 데이터는 딥러닝 모델에 입력되는데, 이때 각 속성의 카디너리티에 따라 엔트리 수가 일정하지 않게 된다. 그리고 각 속성의 엔트리 값들을 각각의 입력 노드에 할당하 고 학습을 진행한다. 이점이 기존 학습 모델과의 차이점으로, 임의의 속성값이 입력층에서 여러 개의 노드로 분산되는 특이 한 구조를 가진다. 제안 모델의 학습 성능을 평가하기 위해, 소실 데이터를 대상으로 다양한 실험을 수행하여 성능 면에서 우수함을 보인다. 제안 모델은 유비쿼터스 환경에서 손실을 최소화하기 위한 알고리즘으로 유용하게 사용될 것으로 본다.

The proposed model is developed to minimize the loss of information in incomplete data including missing data. The first step is to transform the learning data to compensate for the loss information using the data extension technique. In this conversion process, the attribute values of the data are filled with binary or probability values in one-hot encoding. Next, this conversion data is input to the deep learning model, where the number of entries is not constant depending on the cardinality of each attribute. Then, the entry values of each attribute are assigned to the respective input nodes, and learning proceeds. This is different from existing learning models, and has an unusual structure in which arbitrary attribute values are distributedly input to multiple nodes in the input layer. In order to evaluate the learning performance of the proposed model, various experiments are performed on the missing data and it shows that it is superior in terms of performance. The proposed model will be useful as an algorithm to minimize the loss in the ubiquitous environment.

New incremental learning algorithm using extended data expression, based on probabilistic compounding, is presented in this paper. Incremental learning algorithm generates an ensemble of weak classifiers and compounds these classifiers to a strong classifier, using a weighted majority voting, to improve classification performance. We introduce new probabilistic weighted majority voting founded on extended data expression. In this case class distribution of the output is used to compound classifiers. UChoo, a decision tree classifier for extended data expression, is used as a base classifier, as it allows obtaining extended output expression that defines class distribution of the output. Extended data expression and UChoo classifier are powerful techniques in classification and rule refinement problem. In this paper extended data expression is applied to obtain probabilistic results with probabilistic majority voting. To show performance advantages, new algorithm is compared with Learn++, an incremental ensemble-based algorithm.

유비쿼터스 환경에서 데이터는 빠르게 변하고 새로운 데이터는 시간이 경과함에 따라서 출현한다. 그리고 때로, 메모리 공간이 충분하지 않다면, 모든 과거의 데이터를 잃을 수 있다. 그러므로, 과거의 모든 데이터를 잃지 않도록 또는 데이터를 처리하기 위해서 룰을 만들고 새로운 데이터와 결합하는 문제를 해결할 필요가 있다. 이진트리를 만들고 룰을 추출할 때, 각 룰의 중요도는 일반적으로 리프의 클래스의 총 개수로 정해진다. 주어진 데이터에 맞는 최소한의 유한한 상태 억셉터를 찾기 위한 계산 문제는 NP 하드 문제이다. 추출된 룰은 정확하지 않고 정보의 유실이 있다고 가정된다. 이러한 전제조건 때문에, 본 논문은 룰을 개선하기 위한 새로운 접근을 제시한다. 이것은 이전 지식 또는 데이터로 된 룰의 중요도를 제어하는 것이다. 룰 개선을 할 때, 본 논문은 다수와 소수 특성을 이용하는 푸루닝 방법을 사용하여 다양한 룰을 만들고 룰의 각각의 중요도를 제어하고 성능의 변화를 관찰한다. 본 본문에서 고정된 중요도를 갖는 확장된 데이터 표현을 갖는 이진트리 분류기가 사용되었다. 시험 결과는 룰 개선을 위한 새로운 정책을 이용해서 수행한 성능이 더 좋을 수 있음을 보여준다.

In ubiquitous environment, data are changing rapidly and new data is coming as times passes. And sometimes all of the past data will be lost if there is not sufficient space in memory. Therefore, there is a need to make rules and combine it with new data not to lose all the past data or to deal with large amounts of data. In making decision trees and extracting rules, the weight of each of rules is generally determined by the total number of the class at leaf. The computational problem of finding a minimum finite state acceptor compatible with given data is NP-hard. We assume that rules extracted are not correct and may have the loss of some information. Because of this precondition. this paper presents a new approach for refining rules. It controls their weight of rules of previous knowledge or data. In solving rule refinement, this paper tries to make a variety of rules with pruning method with majority and minority properties, control weight of each of rules and observe the change of performances. In this paper, the decision tree classifier with extended data expression having static weight is used for this proposed study. Experiments show that performances conducted with a new policy of refining rules may get better.