[논문]토너먼트 기반의 빅데이터 분석 알고리즘

이현진

doi:10.9728/dcs.2015.16.4.545

토너먼트 기반의 빅데이터 분석 알고리즘
An Algorithms for Tournament-based Big Data Analysis 원문보기

디지털콘텐츠학회 논문지 = Journal of Digital Contents Society, v.16 no.4, 2015년, pp.545 - 553

이현진 (Dept. of Computer Science & Software, Korea Soongsil Cyber University)

초록
AI-Helper

모든 데이터는 그 자체로 가치를 가지고 있지만, 실세계에서 수집되는 데이터들은 무작위적이며 비구조화되어 있다. 따라서 이러한 데이터를 효율적으로 활용하기 위해서 데이터에서 유용한 정보를 추출하기 위한 데이터 변환과 분석 알고리즘들을 사용하게 된다. 이러한 목적으로 사용되는 것이 데이터 마이닝이다. 오늘날에는 데이터를 분석하기 위한 다양한 데이터 마이닝 기법뿐만 아니라, 대용량 데이터를 효율적으로 처리하기 위한 연산 요건과 빠른 분석 시간을 필요로 하고 있다. 대용량 데이터를 저장하기 위하여 하둡이 많이 사용되며, 이 하둡의 데이터를 분석하기 위하여 맵리듀스 프레임워크를 사용한다. 본 논문에서는 단일 머신에서 동작하는 알고리즘을 맵리듀스 프레임워크로 개발할 때 적용의 효율성을 높이기 위한 토너먼트 기반 적용 방안을 제안하였다. 본 방법은 다양한 알고리즘에 적용할 수 있으며, 널리 사용되는 데이터 마이닝 알고리즘인 k-means, k-근접 이웃 분류에 적용하여 그 유용성을 보였다.

Abstract ▼ AI-Helper

While all of the data has a value in itself, most of the data that is collected in the real world is a random and unstructured. In order to extract useful information from the data, it is need to use the data transform and analysis algorithms. Data mining is used for this purpose. Today, there is not only need for a variety of data mining techniques to analyze the data but also need for a computational requirements and rapid analysis time for huge volume of data. The method commonly used to store huge volume of data is to use the hadoop. A method for analyzing data in hadoop is to use the MapReduce framework. In this paper, we developed a tournament-based MapReduce method for high efficiency in developing an algorithm on a single machine to the MapReduce framework. This proposed method can apply many analysis algorithms and we showed the usefulness of proposed tournament based method to apply frequently used data mining algorithms k-means and k-nearest neighbor classification.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 논문에서는 단일 머신 알고리즘을 맵리듀스를 사용하여 빅데이터를 분석하도록 변환하였을 때 분석 속도를 향상시킬 수 있는 방법을 제안한다. 토너먼트 방식으로 단계별로 전달되는데이터의 양을 축소하여 데이터 저장을 위한 디스크 I/O와 데이터 전송을 위한 네트워크 부하를 감소시켜 수행 시간의 효율을 높이고자 한다.
본 논문은 맵리듀스를 사용한 분석 알고리즘을 개발하는 데 있어서 토너먼트 방식을 적용하여 매퍼에서 리듀서 사이에 전달되는 데이터의 양을 줄임으로써 성능을 개선하는 목적을 가지고 있다. 성능을 측정하는 여러 척도 중 수행 시간 관점에서 접근을 하였고, 군집화 기법 중 k-means와 분류 기법 중 k-NN에 제안하는 방법을 적용한 알고리즘을 개발하여, 제안하는 방법의 범용성을 보였다.
토너먼트 방식으로 단계별로 전달되는데이터의 양을 축소하여 데이터 저장을 위한 디스크 I/O와 데이터 전송을 위한 네트워크 부하를 감소시켜 수행 시간의 효율을 높이고자 한다. 본 방법은 맵리듀스로 수행되는 알고리즘의 수행 시간의 효율성을 높이는 방법으로 다양한 분석 알고리즘에 할 수 있는 방법이다. 본 논문의 구성은 다음과 같다.
본 논문에서는 단일 머신 알고리즘을 맵리듀스를 사용하여 빅데이터를 분석하도록 변환하였을 때 분석 속도를 향상시킬 수 있는 방법을 제안한다. 토너먼트 방식으로 단계별로 전달되는데이터의 양을 축소하여 데이터 저장을 위한 디스크 I/O와 데이터 전송을 위한 네트워크 부하를 감소시켜 수행 시간의 효율을 높이고자 한다. 본 방법은 맵리듀스로 수행되는 알고리즘의 수행 시간의 효율성을 높이는 방법으로 다양한 분석 알고리즘에 할 수 있는 방법이다.

제안 방법

단일 머신에서 k-means를 수행한 결과(Single k-means)와 Zhou 등이 제안한 맵리듀스를 사용한 빅 데이터 분석 k-means(Big k-means)[6], 제안하는 토너먼트 방식의 빅 데이터 분석 k-means(Tournament Big k-means)의 분석 속도를 비교하였다. 데이터 수마다 iteration 수가 달라질 수 있기 때문에 1회의 iteration에 대한 시간만 비교하였다. 데이터가 작은 경우 (약 10MB 내외)에는 단일 머신에서 동작하는 k-means가 빅 데이터 분석 k-means 보다 더 빠른 속도를 보였다.
실험을 위한 데이터는 빅 데이터에 맞는 합성 데이터를 만들어 사용하였다. 데이터들은 10차원 데이터로 6개의 클래스를 가지며, 각 데이터들은 클래스의 중심을 기준으로 가우시안 분포를 따르게 만들었다. 1억개의 포인트를 가지는 약 700MB의 데이터를 생성 한 후 1억개씩 증가시켜가면서 6억개의 포인트, 약 4.
하지만 맵 단계에서 평균을 직접 계산하면 리듀스 단계에서 각 군집의 평균을 계산할 수 없다. 따라서 맵 단계에서는 평균 계산식인 #에 착안하여, 군집에 속한 데이터 좌표의 합과 군집에 속한 데이터의 수를 계산한 후 리듀스 단계에서 평균을 계산하였다. 이 방법으로 각 매퍼 단계에서 저장하는 데이터의 개수는 2*n_c 개가 된다.
k-means 알고리즘은 첫 군집의 중심을 임의로 선정하기 때문에 수행할 때 마다 결과가 달라진다. 비교를 위하여 첫 군집의 중심을 결정한 상태에서 동일한 조건으로 실험을 하였다. 3억개의 데이터를 이용한 실험 결과에서 세 알고리즘 모두 k-means의 반복 횟수는 17회로 동일하였고, 분할된 데이터의 수도 각각 17.
제안하는 토너먼트 기반의 k-means 생성 알고리즘은 맵 단계에서 키는 군집을 의미하고, 값은 개별 데이터의 좌표를 각각 할당하는 것이 아니라, 의 중간 결합자 작업에서 수행하는 데이터들의 평균을 할당한다.

대상 데이터

데이터들은 10차원 데이터로 6개의 클래스를 가지며, 각 데이터들은 클래스의 중심을 기준으로 가우시안 분포를 따르게 만들었다. 1억개의 포인트를 가지는 약 700MB의 데이터를 생성 한 후 1억개씩 증가시켜가면서 6억개의 포인트, 약 4.5GB의 데이터까지 6개의 데이터 집합을 생성 하였다.
본 실험은 한 개의 Namenode와 3개의 Datanode를 가지는 하둡 환경에서 이루어졌다. 실험을 위한 데이터는 빅 데이터에 맞는 합성 데이터를 만들어 사용하였다.
본 실험은 한 개의 Namenode와 3개의 Datanode를 가지는 하둡 환경에서 이루어졌다. 실험을 위한 데이터는 빅 데이터에 맞는 합성 데이터를 만들어 사용하였다. 데이터들은 10차원 데이터로 6개의 클래스를 가지며, 각 데이터들은 클래스의 중심을 기준으로 가우시안 분포를 따르게 만들었다.
단일 머신에서 k-NN을 수행한 결과(Single k-NN)와 Prajesh 등이 제안한 맵리듀스를 사용한 빅 데이터 분석 k-NN(Big k-NN)[11], 제안하는 토너먼트 방식의 빅 데이터 분석 k-NN(Tournament Big k-NN)의 분석 속도를 비교하였다. 한 번에 찾을 이웃의 개수인 k는 5로 하였고, 전체 데이터 중 70%는 학습 데이터, 30%는 테스트 데이터로 사용하였다. 데이터가 작은 경우 (약 10MB 내외)에는 단일 머신에서 동작하는 k-NN이 빅 데이터 분석 k-NN보다 더 빠른 속도를 보였다.

데이터처리

(그림 5)는 k-NN에 대한 실험 결과를 비교한 그래프이다. 단일 머신에서 k-NN을 수행한 결과(Single k-NN)와 Prajesh 등이 제안한 맵리듀스를 사용한 빅 데이터 분석 k-NN(Big k-NN)[11], 제안하는 토너먼트 방식의 빅 데이터 분석 k-NN(Tournament Big k-NN)의 분석 속도를 비교하였다. 한 번에 찾을 이웃의 개수인 k는 5로 하였고, 전체 데이터 중 70%는 학습 데이터, 30%는 테스트 데이터로 사용하였다.
(그림 4)는 k-means에 대한 실험 결과를 비교한 그래프이다. 단일 머신에서 k-means를 수행한 결과(Single k-means)와 Zhou 등이 제안한 맵리듀스를 사용한 빅 데이터 분석 k-means(Big k-means)[6], 제안하는 토너먼트 방식의 빅 데이터 분석 k-means(Tournament Big k-means)의 분석 속도를 비교하였다. 데이터 수마다 iteration 수가 달라질 수 있기 때문에 1회의 iteration에 대한 시간만 비교하였다.

성능/효과

비교를 위하여 첫 군집의 중심을 결정한 상태에서 동일한 조건으로 실험을 하였다. 3억개의 데이터를 이용한 실험 결과에서 세 알고리즘 모두 k-means의 반복 횟수는 17회로 동일하였고, 분할된 데이터의 수도 각각 17.7%, 18.3%, 18.1%, 12.4%, 18.2%, 15.3%로 동일한 결과를 보였다. Big k-means와 Tournament Big k-means 모두 Single k-means 알고리즘을 분산 환경에서 동일하게 수행되도록 구성된 알고리즘이기 때문에 동일한 데이터와 동일한 초기 중심값을 사용한 경우에 결과는 동일하였다.
6%의 인식률을 보였다. Big k-NN, Tournamet Big k-NN 모두 Sigle k-NN 알고리즘에 기반을 두어 만든 알고리즘이고, 학습 데이터와 테스트 데이터를 미리 구분하고 실험하였기 때문에 동일한 결과를 보인 것을 확인할 수 있었다.
또한, k-means와 마찬가지로 제안하는 토너먼트 방식의 빅 데이터 분석 k-NN이 30% 정도 더 빠른 속도를 보이는 것을 확인 할 수 있다. k-means와 동일하게 5개의 실험 데이터 중 3억개의 데이터에 대한 실험결과를 보면 세 알고리즘 모두 테스트 데이터에 대해 94.6%의 인식률을 보였다. Big k-NN, Tournamet Big k-NN 모두 Sigle k-NN 알고리즘에 기반을 두어 만든 알고리즘이고, 학습 데이터와 테스트 데이터를 미리 구분하고 실험하였기 때문에 동일한 결과를 보인 것을 확인할 수 있었다.
성능을 측정하는 여러 척도 중 수행 시간 관점에서 접근을 하였고, 군집화 기법 중 k-means와 분류 기법 중 k-NN에 제안하는 방법을 적용한 알고리즘을 개발하여, 제안하는 방법의 범용성을 보였다. 단일 머신에서의 알고리즘들, 일반적인 빅 데이터 분석 알고리즘들과 제안하는 토너먼트 방식의 빅 데이터 분석 알고리즘들의 성능을 비교한 실험 결과 제안하는 방법에 의하여 k-means와 k-NN 모두 수행효율이 높아진 것을 확인할 수 있었다.
데이터 수마다 iteration 수가 달라질 수 있기 때문에 1회의 iteration에 대한 시간만 비교하였다. 데이터가 작은 경우 (약 10MB 내외)에는 단일 머신에서 동작하는 k-means가 빅 데이터 분석 k-means 보다 더 빠른 속도를 보였다. 하지만, 데이터양이 많아지면, (그림 4)와 같이 빅 데이터 분석 k-means가 더 빠른 속도를 보이는 것을 알 수 있다.
첫째, 하둡은 분산 디스크 기반 환경이기 때문에 디스크 읽기(read)가 많이 발생하면, 속도 저하가 발생한다. 둘째, 하둡 노드들 사이에 데이터가 이동할 필요가 있을 때는 네트워크를 사용하기 때문에 매퍼와 리듀서 사이에 이동하는 데이터가 많으면, 속도 저하가 발생한다.
데이터양이 많은 경우 (그림 5)에서와 같이 빅 데이터 분석 k-NN이 더 빠른 속도를 보이는 것을 확인 할 수 있다. 또한, k-means와 마찬가지로 제안하는 토너먼트 방식의 빅 데이터 분석 k-NN이 30% 정도 더 빠른 속도를 보이는 것을 확인 할 수 있다. k-means와 동일하게 5개의 실험 데이터 중 3억개의 데이터에 대한 실험결과를 보면 세 알고리즘 모두 테스트 데이터에 대해 94.
하지만, 빅 데이터 시대로 오면서 가용 데이터의 양이 극적으로 늘어났기 때문에 빅 데이터에 대한 분석 알고리즘의 수행 시간은 증가하게 되었다. 본 논문에서 제시한 토너먼트 방식의 맵리듀스 기반의 분산 분석 알고리즘은 빅 데이터에 대한 분석 속도를 향상시킬 수 있으며, 이 기법을 다른 알고리즘들에도 확대 적용할 수 있다.
본 논문은 맵리듀스를 사용한 분석 알고리즘을 개발하는 데 있어서 토너먼트 방식을 적용하여 매퍼에서 리듀서 사이에 전달되는 데이터의 양을 줄임으로써 성능을 개선하는 목적을 가지고 있다. 성능을 측정하는 여러 척도 중 수행 시간 관점에서 접근을 하였고, 군집화 기법 중 k-means와 분류 기법 중 k-NN에 제안하는 방법을 적용한 알고리즘을 개발하여, 제안하는 방법의 범용성을 보였다. 단일 머신에서의 알고리즘들, 일반적인 빅 데이터 분석 알고리즘들과 제안하는 토너먼트 방식의 빅 데이터 분석 알고리즘들의 성능을 비교한 실험 결과 제안하는 방법에 의하여 k-means와 k-NN 모두 수행효율이 높아진 것을 확인할 수 있었다.
이 방식은 리듀서로 입력 데이터 n을 모두 전달한다. 제안하는 토너먼트 방식의 k-NN은 매퍼에서 k개의 근접 이웃을 선택하고, 리듀서에서 다시 한 번 k개의 근접 이웃을 결정하는 방식으로 리듀서로 n이 아닌 k개의 데이터를 전달하기 때문에, 저장 공간과 분석 시간을 절약할 수 있다. 이 알고리즘은 토너먼트 방식으로 데이터의 개수를 단계별로 줄여가는 방법으로 제안하는 토너먼트 방식의 k-NN은 <표 5>와 같다.
하지만, 데이터양이 많아지면, (그림 4)와 같이 빅 데이터 분석 k-means가 더 빠른 속도를 보이는 것을 알 수 있다. 제안하는 토너먼트 방식의 빅 데이터 분석 k-means는 일반적인 빅 데이터 분석 k-means 보다 20% 정도의 속도향상을 보이는 것을 확인할 수 있었다. 단일 머신에서의 k-means는 모든 데이터를 메모리에 올려놓고 수행하는 구조이기 때문에 4억개 데이터(2.
빅데이터 분석 알고리즘을 개발할 때 고려해야 할 사항은 다음과 같다. 첫째, 하둡은 분산 디스크 기반 환경이기 때문에 디스크 읽기(read)가 많이 발생하면, 속도 저하가 발생한다. 둘째, 하둡 노드들 사이에 데이터가 이동할 필요가 있을 때는 네트워크를 사용하기 때문에 매퍼와 리듀서 사이에 이동하는 데이터가 많으면, 속도 저하가 발생한다.

질의응답

핵심어	질문	논문에서 추출한 답변
	맵리듀스 프레임워크는 무슨 기술인가?	대용량 데이터는 기존 데이터베이스에 저장하는 것이 아니라 분산 환경에 저장되며, 하둡(Hadoop) 프로젝트는 분산 파일 시스템인 HDFS (Hadoop Distributed File System)를 사용하여 데이터를 분산하여 저장한다[2]. 맵리듀스(MapReduce) 프레임워크(Framework)는 구글이 분산 컴퓨팅 환경인 하둡에서 대용량 데이터 처리를 위해 제안한 분산 컴퓨팅 기술이다[3,4]. 하둡과 맵리듀스는 대용량 데이터 저장소, 데이터 분석과 제어를 관리하는 기술로 잘 알려져 있다[5].
	HDFS는 어떤 기능들을 제공하고 있는가?	저성능이지만 대량의 서버를 통하여 하둡 클러스터의 컴퓨팅 파워, 저장 용량 등을 쉽게 증대 시킬 수 있다. 또한 HDFS는 데이터 복제의 신뢰성, 빠른 장애 감지 및 자동 복구 등 분산 환경에서의 파일 관리를 위한 다양한 기능들을 제공하고 있다[6].
	빅데이터 분석 알고리즘을 개발할 때 고려해야 할 사항은 무엇인가?	빅데이터 분석 알고리즘을 개발할 때 고려해야 할 사항은 다음과 같다. 첫째, 하둡은 분산 디스크 기반 환경이기 때문에 디스크 읽기(read)가 많이 발생하면, 속도 저하가 발생한다. 둘째, 하둡 노드들 사이에 데이터가 이동할 필요가 있을 때는 네트워크를 사용하기 때문에 매퍼와 리듀서 사이에 이동하는 데이터가 많으면, 속도 저하가 발생한다.

참고문헌 (13)

Sungmin Kang, Seokjoo Lee, Jun-ki Min, "An Efficie nt Clustering Method based on Multi Centroid Set using MapReduce," KIISE Transactions on Computing Practices, Vol.21, No.7, pp.494-499, 2015.

상세보기
Hadoop, "http://hadoop.apache.org/"
J. Dean and S. Ghemawat, "MapReduce: Simplified data processing on large clusters," Communications of the ACM, Vol. 51, No. 1, pp. 107-113, 2008.

상세보기
Seung-jun Choi, Jea-Won Park, Jong-Bae Kim, Jae- Hyun Choi, "A Quality Evaluation Model for Distributed Processing Systems of Big Data," Journal of Digital Contents Society, Vol. 15, No. 4, pp. 533-545, 2014.

원문보기 상세보기
S. Ghemowat, H. Gobioff, and S. T. Leung, "The Goo gle file system," 19th Symposium on Operating Systems Principles, pp. 29-43, 2003.
P. Zhou, J. Lei, and W. Ye, "Large-Scale Data Sets Clustering Based on MapReduce and Hadoop," Journal of Computational Information systems, vol. 7, No. 16, pp. 5956-5963, 2011.
Lin G., Zhonghua S., Zhiqiang M., Xiang G., Charles Z., and Yoohui J., "K-Means of Cloud Computing: MapReduce, DVM, and Windows Azure," in CLOUD COMPUTING 2013, pp. 13-18, 2013.
Hyunjin Lee, "Decombined Distributed Parallel VQ Codebook Generation Based on MapReduce," Journal of Digital Contents Society, Vol. 15, No. 3, pp. 365- 371, 2014.

원문보기 상세보기
Prajesh P. Anchalia, and Kaushik Roy, "The k-Nearest Neighbor Algorithm Using MapReduce Paradigm," 2014 Fifth International Conference on Intelligent System, Modeling and Simulation, pp. 512-518. 2014.
H. Maulik, and S. Bandyopadhyay. "Genetic Algorithm-Based Clustering Technique," Pattern Recognition, Vol.33, pp. 1455-1465, 2000.

상세보기
D. Arthur and S. Vassilvitskii. "K-Means++: The Advantage of Careful Seeding," Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2007.
Young Joon Kim, Keon Myung Lee, "Big Numeric Data Classification Using Grid-based Bayesian Inference in the MapReduce Framework," International Journal of Fuzzy Logic and Intelligent Systems, Vol. 14, No.4, 2014.

원문보기 상세보기
Chi Zhang, Feifei Li, and Jeffrey Jestes, "Efficient parallel kNN joins for large data in MapReduce," Proceedings of the 15th International Conference on Extending Database Technology, pp. 38-49, 2012.

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증