Research on an Improved Decision Tree Classification Algorithm

Wenyi Xu 보안공학연구지원센터 2016 International Journal of Database Theory and Appli Vol.9 No.12

In the paper, with the introduction of data mining algorithm of the classification in detail, and then combining the classification algorithm and incremental learning technology, an incremental decision tree algorithm is proposed to solve the problem of incremental learning and analysis the experimental data for this algorithm. The paper used ID3 and C4.5 algorithm for detailed research. According to two algorithms, combining Bayesian classification algorithm’s incremental learning characteristic, the paper proposed an incremental decision tree algorithm , and by the analysis of experimental data. This algorithm can solve the incremental learning problem of the decision tree algorithm very well.

RFID 시스템에서 충돌 트리 기반 충돌방지 알고리즘

서현곤(Hyun-Gon Seo) 한국정보과학회 2007 정보과학회논문지 : 정보통신 Vol.34 No.5

RFID는 RF신호를 이용하여 물체를 식별하는 가장 유망한 미래의 비접촉 기술이다. RFID 리더의 식별영역에 여러 개의 태그가 있는 경우, 리더의 질의에 대하여 모든 태그들이 동시에 응답을 하기 때문에 충돌이 발생되어 태그를 식별할 수 없게 된다. RFID에서 다중 태그 식별문제는 아주 중요한 핵심기술로 이것을 해결하기 위해 슬롯기반 알로하 알고리즘, 트리 기반 알고리즘 등과 같은 충돌 방지 알고리즘이 제안되었다. 본 논문에서는 RFID 시스템에서 충돌 트리를 이용한 충돌트리 기반 충돌 방지알고리즘을 제안한다. 제안하는 방법은 효과적인 충돌 방지 메커니즘을 제공하며 메모리래스 알고리즘이다. 제안하는 충돌트리는 다중 태그 식별문제를 해결하기 위한 메커니즘으로 리더와 태그사이 질의와 응답과정에서 만들어 진다. 리더가 k 비트로 구성된 프리픽스를 질의하면, 태그는 자신의 식별자와 프리픽스를 비교하여 일치할 경우 식별자의 K+1 비트에서 마지막 비트까지 리더에게 전송한다. 시뮬레이션 결과에 따라 제안하는 충돌 트리 기반 충돌 방지 알고리즘이 기존의 트리 워킹 알고리즘이나 쿼리 트리 알고리즘보다 좋은 성능을 보임을 알 수 있다. RFID (Radio Frequency Identification) is one of the most promising air interface technologies in the future for object identification using radio wave. If there are multiple tags within the range of the RFID tag reader, all tags send their tag identifications to the reader at the same time in response to the reader's query. This causes collisions on the reader and no tag is identified. A multi-tag identification problem is a core issue in the RFID. It can be solved by anti-collision algorithm such as slot based ALHOA algorithms and tree based algorithms. This paper, proposes a collision tree based anti-collision algorithm using collision tree in RFID system. It is a memory-less algorithm and is an efficient RFID anti-collision mechanism. The collision tree is a mechanism that can solve multi-tag identification problem. It is created in the process of querying and responding between the reader and tags. If the reader broadcasts K bits of prefix to multiple tags, all tags with the identifications matching the prefix transmit the reader the identifications consisted of k+1 bit to last. According to the simulation result, a proposed collision tree based anti-collision algorithm shows a better performance compared to tree working algorithm and query tree algorithm.

GENETIC ALGORITHM-BASED COMBINATION METHOD OF MULTIPLE DECISION TREES FOR CUSTOMER RELATIONSHIP MANAGEMENT

Zhe Zhang 글로벌지식마케팅경영학회 2018 Global Marketing Conference Vol.2018 No.07

This study applies optimization-based algorithm to develop combination classification methods. We propose a genetic algorithm-based combination classification method of multiple decision trees to improve predictive accuracy, optimize classification rules, and interpret classification results. The basic algorithm for decision tree has been constructed in a top-down recursive divide-and-conquer manner. Based on different split measures (attribute selection measures), different decision tree algorithms can be produced, and then multiple decision trees can be formed. We proposed the parallel combination model of multiple decision trees. On top of the combination model, multiple decision trees are parallel combined. Each decision tree produces its own classification rules according to training samples from which one can present the classification result using probability distribution of target class label. At the bottom, the classification result of each decision tree serves as the input for combination algorithm in producing classification result and rules for the combination model. Combination algorithm adopts weighted summation of the outputs of probability measurement levels from individual decision trees, while genetic algorithm optimizes connection weight matrix. Finally the target class label with the largest probability output value is selected as the decision result for combination classification methods. The proposed method is applied to the issues of customer credit rating assessment and customer response behaviour pattern recognition in CRM. From the simulation results it is concluded that the proposed method has higher predictive accuracy than single decision tree. Moreover, it retains good interpretability and optimizes classification rules.

순차감축 알고리즘과 지연감축 알고리즘을 이용한 효과적인 지배자 트리의 구현

이대식 ( Dae Sik Lee ) 한국인터넷정보학회 2005 인터넷정보학회논문지 Vol.6 No.6

지배자 트리란 유향그래프에서 지배관계를 트리로 표현한 것이다. 임의의 유향그래프로부터 지배자 트리를 구성하기 위한 효과적인 알고리즘을 제시한다. 감축 가능한 흐름그래프는 지배자 계산을 한 후 지배자 트리로 감축된다. 감축 불가능한 흐름그래프는 정보 테이블의 연결가지 정보를 이용하여 지배자 연결그래프로 구성된다. 지배자 연결그래프에서 지배자 트리로 감축하기 위하여 효과적인 순차감축 알고리즘과 지연감축 알고리즘을 구현한다. 구현한 결과 순차감축 알고리즘 보다 지연감축 알고리즘의 실행시간이 빠르다. 따라서 흐름그래프에서 효과적인 지배자 트리로 감축된다. The dominator tree presents the dominance frontier from directed graph to the tree. we present the effective algorithm for constructing the dominator tree from arbitrary directed graph. The reducible flow graph was reduced to dominator tree after dominator calculation. And the irreducible flow graph was constructed to dominator-join graph using join-edge information of information table. For reducing the dominator tree from dominator-join graph, we implement the effective sequency reducible algorithm and delay reducible algorithm. As a result of implementation, we can see that the delay reducible algorithm takes less execution time than the sequency reducible algorithm. Therefore, we can reduce the flow graph to dominator tree effectively.

GPU상에서 동작하는 Ray Tracing을 위한 효과적인 k-D tree 탐색 알고리즘

강윤식,박우찬,서충원,양성봉 한국정보과학회 2008 정보과학회논문지 : 시스템 및 이론 Vol. No.

This paper proposes an effective k-D tree traversal algorithm for ray tracing on a GPU. The previous k-D tree traverse algorithm based on GPU uses bottom-up searching from a leaf to the root after failing to find the ray intersected primitive in the leaf node. During the bottom-up search the algorithm decides the current node is visited or not from the parent node. In such a way, we need to visit the parent node which was already visited and the duplicated bounding box intersection tests. The new k-D tree traverse algorithm reduces the brother and parent duplicated visit by using an efficient method which decides whether the brother node is already visited or not during the bottom-up search. Also the algorithm take place bounding box intersection tests only for the nodes which is not yet done. As a result our experiment shows the new algorithm is about 30% faster than the previous. 본 논문은 GPU상에서 작동되는 ray tracing을 위한 효과적인 k-D tree 탐색 알고리즘을 제안한다. 기존의 k-D tree를 위한 GPU 기반 탐색 알고리즘은 임의의 단말노드에서 교차되는 primitive를 찾지 못한 경우, root 노드 방향으로 bottom-up 탐색하여 부모 노드에서 bounding box 교차검사를 이용해 형제 노드의 기 방문 여부를 판단한다. 이러한 방법은 이미 방문한 부모 노드의 방문과 bounding box 교차검사를 중복적으로 수행한다. 본 논문에서 제안하는 알고리즘은 bottom-up 탐색을 수행 할 때 형제 노드가 이전에 방문했는지를 확인할 수 있는 효율적인 방법을 제시함으로써 형제노드 및 부모노드의 방문을 생략하도록 하고, 또한 아직 방문하지 않은 노드에 대해서만 bounding box 교차검사를 수행함으로써 중복된 연산을 피한다. 결과적으로 본 논문의 실험은 기존 알고리즘 대비 제안하는 알고리즘이 약 30%의 성능 향상이 있음을 보여 준다.

GPU상에서 동작하는 Ray Tracing을 위한 효과적인 k-D tree 탐색 알고리즘

강윤식(Yoon-Sig Kang),박우찬(Woo-Chan Park),서충원(Choong-Won Seo),양성봉(Sung-Bong Yang) 한국정보과학회 2008 정보과학회논문지 : 시스템 및 이론 Vol.35 No.3·4

본 논문은 GPU상에서 작동되는 ray tracing을 위한 효과적인 k-D tree 탐색 알고리즘을 제안한다. 기존의 k-D tree를 위한 GPU 기반 탐색 알고리즘은 임의의 단말노드에서 교차되는 primitive를 찾지 못한 경우, root 노드 방향으로 bottom-up 탐색하여 부모 노드에서 bounding box 교차검사를 이용해 형제 노드의 기 방문 여부를 판단한다. 이러한 방법은 이미 방문한 부모 노드의 방문과 bounding box 교차검사를 중복적으로 수행한다. 본 논문에서 제안하는 알고리즘은 bottom-up 탐색을 수행 할 때 형제노드가 이전에 방문했는지를 확인할 수 있는 효율적인 방법을 제시함으로써 형제노드 및 부모노드의 방문을 생략하도록 하고, 또한 아직 방문하지 않은 노드에 대해서만 bounding box 교차검사를 수행함으로써 중복된 연산을 피한다. 결과적으로 본 논문의 실험은 기존 알고리즘 대비 제안하는 알고리즘이 약 30%의 성능 향상이 있음을 보여 준다. This paper proposes an effective k-D tree traversal algorithm for ray tracing on a GPU. The previous k-D tree traverse algorithm based on GPU uses bottom-up searching from a leaf to the root after failing to find the ray intersected primitive in the leaf node. During the bottom-up search the algorithm decides the current node is visited or not from the parent node. In such a way, we need to visit the parent node which was already visited and the duplicated bounding box intersection tests. The new k-D tree traverse algorithm reduces the brother and parent duplicated visit by using an efficient method which decides whether the brother node is already visited or not during the bottom-up search. Also the algorithm take place bounding box intersection tests only for the nodes which is not yet done. As a result our experiment shows the new algorithm is about 30% faster than the previous.

유전 알고리즘과 게임 트리를 병합한 오목인공지능 설계 및 GPU 기반 병렬 처리 기법

안일준(Il Jun Ahn),박인규(In Kyu Park) 한국정보과학회 2010 정보과학회논문지 : 시스템 및 이론 Vol.37 No.2

본 논문에서는 GPU(graphics processing unit)를 이용하여 오목의 인공지능 알고리즘 연산을 고속으로 수행하기 위한 효율적인 알고리즘 설계와 구현 방법을 제안한다. 본 논문에서 제안하는 게임 인공지능은 최소-최대 게임 트리(min-max game tree)와 유전 알고리즘(genetic algorithm)의 협업적 구조로 설계된다. 게임 트리와 유전 알고리즘의 평가함수(evaluation function) 부분은 많은 계산 량을 소모하지만 해 공간(solution space)의 수많은 후보 벡터에 대해 독립적으로 수행되기 때문에 본 논문에서는 이를 GPU 상에서의 대량 병렬처리를 통해 수행한다. NVIDIA CUDA(compute unified device architecture) 환경에서의 실제 구현을 통해 CPU에서의 처리에 비해 게임 트리는 400배 이상의 수행 속도의 향상을, 유전 알고리즘은 300배 이상의 수행 속도의 향상을 각각 보였다. 본 논문에서는 스레드(thread)의 넘침(overflow)을 피하고 보다 효과적인 해 공간 탐색을 위해, 게임 트리를 이용하여 근방의 몇 단계까지 전역 탐색(full search)을 수행한 후 이후 단계는 유전 알고리즘을 이용하여 선별 탐색을 수행하는 협업적인공지능을 제안한다. 다양한 실험 결과를 통해 제안하는 알고리즘은 게임의 인공지능을 향상시키고 게임의 규칙으로부터 주어진 시간 내에 문제를 해결할 수 있음을 보인다. This paper proposes an efficient method for design and implementation of the artificial intelligence (AI) of ‘omok’ game on the GPU. The proposed AI is designed on a cooperative structure using min-max game tree and genetic algorithm. Since the evaluation function needs intensive computation but is independently performed on a lot of candidates in the solution space, it is computed on the GPU in a massive parallel way. The implementation on NVIDIA CUDA and the experimental results show that it outperforms significantly over the CPU, in which parallel game tree and genetic algorithm on the GPU runs more than 400 times and 300 times faster than on the CPU. In the proposed cooperative AI, selective search using genetic algorithm is performed subsequently after the full search using game tree to search the solution space more efficiently as well as to avoid the thread overflow. Experimental results show that the proposed algorithm enhances the AI significantly and makes it run within the time limit given by the game's rule.

글로벌 라우팅 유전자 알고리즘의 설계와 구현

송호정,송기용 한국융합신호처리학회 2002 융합신호처리학회 논문지 (JISPS) Vol.3 No.2

글로벌 라우팅(global routing)은 VLSI 설계 과정중의 하나로, 네트리스트의 모든 네트들을 연결하기 위하여 각 네트들을 라우팅 영역(routing area)에 할당시키는 문제이며, 글로벌 라우팅에서 최적의 해를 얻기 위해 maze routing 알고리즘, line-probe 알고리즘, shortest path 기반 알고리즘, Steiner tree 기반 알고리즘등이 이용된다. 본 논문에서는 라우팅 그래프에서 최단 경로 Steiner tree 탐색방법인 weighted network heuristic(WNH)과 이를 기반으로 하는 글로벌 라우팅 유전자 알고리즘(genetic algorithm; GA)을 제안하였으며, 제안한 방식을 시뮬레이티드 어닐링(SA) 방식과 비교, 분석하였다. Global routing is to assign each net to routing regions to accomplish the required interconnections. The most popular algorithms for global routing inlcude maze routing algorithm, line-probe algorithm, shortest path based algorithm, and Steiner tree based algorithm. In this paper we propose weighted network heuristic(WNH) as a minimal Steiner tree search method in a routing graph and a genetic algorithm based on WNH for the global routing. We compare the genetic algorithm(GA) with simulated annealing(SA) by analyzing the results of each implementation.

수목 도복의 3D 충격량 산출 기법 개발

김채원,김충식 한국조경학회 2023 韓國造景學會誌 Vol.51 No.2

This study intended to develop a technique for quantitatively and 3-dimensionally predicting the potential failure zone and impulse that may occur when trees are fall down. The main outcomes of this study are as follows. First, this study established the potential failure zone and impulse calculation formula in order to quantitatively calculate the risks generated when trees are fallen down. When estimating the potential failure zone, the calculation was performed by magnifying the height of trees by 1.5 times, reflecting the likelihood of trees falling down and slipping. With regard to the slope of a tree, the range of 360° centered on the root collar was set in the case of trees that grow upright and the range of 180° from the inclined direction was set in the case of trees that grow inclined. The angular momentum was calculated by reflecting the rotational motion from the root collar when the trees fell down, and the impulse was calculated by converting it into the linear momentum. Second, the program to calculate a potential failure zone and impulse was developed using Rhino3D and Grasshopper. This study created the 3-dimensional models of the shapes for topography, buildings, and trees using the Rhino3D, thereby connecting them to Grasshopper to construct the spatial information. The algorithm was programmed using the calculation formula in the stage of risk calculation. This calculation considered the information on the trees’ growth such as the height, inclination, and weight of trees and the surrounding environment including adjacent trees, damage targets, and analysis ranges. In the stage of risk inquiry, the calculation results were visualized into a three-dimensional model by summarizing them. For instance, the risk degrees were classified into various colors to efficiently determine the dangerous trees and dangerous areas.

이븐 연결망 Ed의 에지 중복 없는 스패닝 트리를 구성하는 알고리즘

김성원,김종석 한국정보처리학회 2010 정보처리학회논문지. 컴퓨터 및 통신시스템 Vol.17 No.3

Even networks were introduced as a class of fault-tolerant multiprocessor networks and analyzed so many useful properties and algorithms such as simple routing algorithms, maximal fault tolerance, node disjoint path. Introduced routing algorithms and node disjoint path algorithms are proven to be optimal. However, it has not been introduced to constructing scheme for edge-disjoint spanning trees in even networks. The design of edge-disjoint spanning trees is a useful scheme to analyze for measuring the efficiency of fault tolerant of interconnection network and effective broadcasting. Introduced routing algorithm or node disjoint path algorithm are for the purpose of routing or node disjoint path hence they are not applicable to constitute edge disjoint spanning tree. In this paper, we show a construction algorithm of edge-disjoint spanning trees in even network Ed. 이븐 연결망은 고장허용 다중컴퓨터에 대한 하나의 모형으로 제안된 연결망으로, 간단한 라우팅 알고리즘, 최대고장허용도, 노드 중복 없는 경로와 같은 여러 가지 유용한 성질과 알고리즘들이 분석되었다. 기존에 발표된 라우팅 알고리즘과 노드 중복 없는 경로를 구성하는 알고리즘은 최적임이 증명되었다. 하지만 아직까지 이븐 연결망에서 에지 중복 없는 스패닝 트리를 구성하는 기법은 소개되지 않았다. 에지 중복 없는 스패닝 트리는 상호연결망의 고장허용도의 성능 향상과 효율적인 방송 기법을 분석하기 위해서 사용되는 매우 유용한 기법이다. 기존에 발표된 라우팅 알고리즘 또는 노드 중복 없는 경로를 구성하는 알고리즘은 라우팅 또는 노드 중복 없는 경로를 위한 알고리즘으로 에지 중복 없는 스패닝 트리를 구성하기 위해 적용될 수 없는 알고리즘이다. 본 논문에서는 이븐 연결망 Ed에서 에지 중복 없는 스패닝 트리를 구성하는 알고리즘을 제안한다.