Выпуск №6 (Май)
XLII Международная научно-практическая конференция «Актуальные проблемы современной науки», 27.06.2019 (Совместная конференция с Международным научным центром развития науки и технологий)

XLI Международная научно-практическая конференция «Актуальные проблемы современной науки», 30.05.2019 (Совместная конференция с Международным научным центром развития науки и технологий)

XL Международная научно-практическая конференция «Актуальные проблемы современной науки», 28.03.2019 (Совместная конференция с Международным научным центром развития науки и технологий)

МНПК "Цифровая трансформация и инновации в экономике, праве, государственном управлении, науке и образовательных процессах", 18-21.03.2019

XXXIX Международная научно-практическая конференция «Актуальные проблемы современной науки», 27.02.2019 (Совместная конференция с Международным научным центром развития науки и технологий)

XIII Международная научно-практическая конференция «Научный диспут: вопросы экономики и финансов», 31.01.2019 (Совместная конференция с Финансово-экономическим научным советом)

XXXVIII Международная научно-практическая конференция «Актуальные проблемы современной науки», 30.01.2019 (Совместная конференция с Международным научным центром развития науки и технологий)

XXXVІI Международная научно-практическая конференция: "Актуальные проблемы современной науки", 28.12.2018 (Совместная конференция с Международным научным центром)

XXXVI Международная научно-практическая конференция: "Актуальные проблемы современной науки", 29.11.2018 (Совместная конференция с Международным научным центром)

XIII Международная научно-практическая конференция «Актуальные проблемы экономики и финансов», 31.10.2018 (Совместная конференция с Финансово-экономическим научным советом)

XXXV Международная научно-практическая конференция: "Актуальные проблемы современной науки", 30.10.2018 (Совместная конференция с Международным научным центром)

XXXIV Международная научно-практическая конференция: "Актуальные проблемы современной науки", 28.09.2018 (Совместная конференция с Международным научным центром)

ХXXIII Международная научно-практическая конференция: "Актуальные проблемы современной науки", 30.08.2018 (Совместная конференция с Международным научным центром)

ХXXII Международная научно-практическая конференция: "Актуальные проблемы современной науки", 31.07.2018 (Совместная конференция с Международным научным центром)

XII Международная научно-практическая конференция «Актуальные проблемы экономики и финансов», 31.07.2018 (Совместная конференция с Финансово-экономическим научным советом)

ХXXI Международная научно-практическая конференция: "Актуальные проблемы современной науки", 29.06.2018 (Совместная конференция с Международным научным центром)

ХІ Международная научно-практическая конференция «Глобальные проблемы экономики и финансов», 31.05.2018 (Совместная конференция с Финансово-экономическим научным советом)

XXХ Международная научно-практическая конференция: "Актуальные проблемы современной науки", 30.05.2018 (Совместная конференция с Международным научным центром)

XXIХ Международная научно-практическая конференция: "Актуальные проблемы современной науки", 30.04.2018 (Совместная конференция с Международным научным центром)

ХХVIІІ Международная научно-практическая конференция: "Актуальные проблемы современной науки", 29.03.2018 (Совместная конференция с Международным научным центром)

ІІІ МНПК "Экономика, финансы и управление в XXI веке: анализ тенденций и перспективы развития", 19-22.03.2018 (Совместная конференция с Финансово-экономическим научным советом)

X Международная научно-практическая конференция «Глобальные проблемы экономики и финансов», 28.02.2018 (Совместная конференция с Финансово-экономическим научным советом)

ХХVІІ Международная научно-практическая конференция: "Актуальные проблемы современной науки", 27.02.2018 (Совместная конференция с Международным научным центром)

ХХVІ Международная научно-практическая конференция: "Актуальные проблемы современной науки", 30.01.2018 (Совместная конференция с Международным научным центром)

XІІ Международная научно-практическая конференция «Научный диспут: вопросы экономики и финансов», 29.12.2017 (Совместная конференция с Финансово-экономическим научным советом)

ХХV Международная научно-практическая конференция: "Актуальные проблемы современной науки", 28.12.2017 (Совместная конференция с Международным научным центром)

ХХІV Международная научно-практическая конференция: "Актуальные проблемы современной науки", 29.11.2017 (Совместная конференция с Международным научным центром)

XI Международная научно-практическая конференция «Актуальные проблемы экономики и финансов», 31.10.2017 (Совместная конференция с Финансово-экономическим научным советом)

XІ Международная научно-практическая конференция «Научный диспут: вопросы экономики и финансов», 29.09.2017 (Совместная конференция с Финансово-экономическим научным советом)

ХХIІІ Международная научно-практическая конференция: "Актуальные проблемы современной науки", 28.09.2017 (Совместная конференция с Международным научным центром)

X Международная научно-практическая конференция «Актуальные проблемы экономики и финансов», 31.07.2017 (Совместная конференция с Финансово-экономическим научным советом)

ХXII Международная научно-практическая конференция: "Актуальные проблемы современной науки", 28.07.2017 (Совместная конференция с Международным научным центром)

ХXI Международная научно-практическая конференция: "Актуальные проблемы современной науки", 29.06.2017 (Совместная конференция с Международным научным центром)

IX Международная научно-практическая конференция «Глобальные проблемы экономики и финансов», 31.05.2017 (Совместная конференция с Финансово-экономическим научным советом)

ХX Международная научно-практическая конференция: "Актуальные проблемы современной науки", 30.05.2017 (Совместная конференция с Международным научным центром)

"Тенденции развития национальных экономик: экономическое и правовое измерение" 18-19.05.2017 (Совместная конференция с Финансово-экономическим научным советом и ККИБиП)

ХIX Международная научно-практическая конференция: "Актуальные проблемы современной науки", 27.04.2017 (Совместная конференция с Международным научным центром)

IX Международная научно-практическая конференция "Научный диспут: вопросы экономики и финансов", 31.03.2017 (Совместная конференция с Финансово-экономическим научным советом)

ХVIII Международная научно-практическая конференция: "Актуальные проблемы современной науки", 30.03.2017 (Совместная конференция с Международным научным центром)

МНПК "Экономика, финансы и управление в XXI веке: анализ тенденций и перспективы развития", 20–23.03.2017 (Совместная конференция с Финансово-экономическим научным советом)

VIII Международная научно-практическая конференция "Глобальные проблемы экономики и финансов", 28.02.2017 (Совместная конференция с Финансово-экономическим научным советом)

ХVII Международная научно-практическая конференция: "Актуальные проблемы современной науки", 27.02.2017 (Совместная конференция с Международным научным центром)

VIII Международная научно-практическая конференция "Актуальные проблемы экономики и финансов", 31.01.2017 (Совместная конференция с Финансово-экономическим научным советом)

ХVI Международная научно-практическая конференция: "Актуальные проблемы современной науки", 30.01.2017 (Совместная конференция с Международным научным центром)

ХV Международная научно-практическая конференция: "Актуальные проблемы современной науки", 28.12.2016 (Совместная конференция с Международным научным центром)

VIII Международная научно-практическая конференция "Научный диспут: вопросы экономики и финансов", 28.12.2016 (Совместная конференция с Финансово-экономическим научным советом)

VII Международная научно-практическая конференция "Глобальные проблемы экономики и финансов", 30.11.2016 (Совместная конференция с Финансово-экономическим научным советом)

ХІV Международная научно-практическая конференция: "Актуальные проблемы современной науки", 29.11.2016 (Совместная конференция с Международным научным центром)

VII Международная научно-практическая конференция "Актуальные проблемы экономики и финансов", 31.10.2016 (Совместная конференция с Финансово-экономическим научным советом)

ХІІІ Международная научно-практическая конференция: "Актуальные проблемы современной науки", 28.10.2016 (Совместная конференция с Международным научным центром)

VII Международная научно-практическая конф. «Научный диспут: вопросы экономики и финансов», 30.09.2016 (Совместная конференция с Финансово-экономическим научным советом)

ХІІ Международная научно-практическая конференция: "Актуальные проблемы современной науки", 29.09.2016 (Совместная конференция с Международным научным центром)

XI Международная научно-практическая конференция «Актуальные проблемы современной науки», 30.08.2016 (Совместная конференция с Международным научным центром)

ІV Международная научно-практическая конф. "Экономика и управление в XXI веке: анализ тенденций и перспектив развития", 29.07.2016 (Совместная конференция с Финансово-экономическим научным советом)

X Международная научно-практическая конференция "Актуальные проблемы современной науки", 28.07.2016 (Совместная конференция с Международным научным центром)

VІ Международная научно-практическая конференция "Актуальные проблемы экономики и финансов", 30.06.2016 (Совместная конференция с Финансово-экономическим научным советом)

ІX Международная научно-практическая конференция "Актуальные проблемы современной науки", 29.06.2016 (Совместная конференция с Международным научным центром)

VI Международная научно-практическая конференция "Научный диспут: вопросы экономики и финансов", 31.05.2016 (Совместная конференция с Финансово-экономическим научным советом)

VIIІ Международная научно-практическая конференция "Актуальные проблемы современной науки", 30.05.2016 (Совместная конференция с Международным научным центром)

V Международная научно-практическая конференция "Глобальные проблемы экономики и финансов", 29.04.2016 (Совместная конференция с Финансово-экономическим научным советом)

VIІ Международная научно-практическая конференция "Актуальные проблемы современной науки", 28.04.2016 (Совместная конференция с Международным научным центром)

VІ Международная научно-практическая конференция "Актуальные проблемы современной науки", 31.03.2016 (Совместная конференция с Международным научным центром)

ІI Международная научно-практическая конф. "Экономика и управление в XXI веке: анализ тенденций и перспектив развития", 30.03.2016 (Совместная конференция с Финансово-экономическим научным советом)

V Международная научно-практическая конференция "Актуальные проблемы экономики и финансов", 21-24.03.2016 (Совместная конференция с Финансово-экономическим научным советом)

V Международная научно-практическая конференция "Научный диспут: вопросы экономики и финансов", 26.02.2016 (Совместная конференция с Финансово-экономическим научным советом)

II Международная научно-практическая конференция: "Научный диспут: актуальные вопросы медицины" 20.02.2016 (Совместная конференция с Международным научным центром)

ІV Международная научно-практическая конференция "Актуальные проблемы современной науки", 29.12.2015 (Совместная конференция с Международным научным центром)

IV Международная научно-практическая конференция "Глобальные проблемы экономики и финансов", 28.12.2015 (Совместная конференция с Финансово-экономическим научным советом)

IV Международная научно-практическая конференция "Актуальные проблемы экономики и финансов", 30.11.2015 (Совместная конференция с Финансово-экономическим научным советом)

IV Международная научно-практическая конференция "Научный диспут: вопросы экономики и финансов", 29.10.2015 (Совместная конференция с Финансово-экономическим научным советом)

Международная научно-практическая конференция: "Научный диспут: актуальные вопросы медицины" 28.10.2015 (Совместная конференция с Международным научным центром)

III Международная научно-практическая конференция "Глобальные проблемы экономики и финансов", 30.09.2015 (Совместная конференция с Финансово-экономическим научным советом)

III Международная научно-практическая конференция "Актуальные проблемы экономики и финансов", 31.08.2015 (Совместная конференция с Финансово-экономическим научным советом)

ІІІ Международная научно-практическая конференция "Научный диспут: вопросы экономики и финансов", 30.06.2015 (Совместная конференция с Финансово-экономическим научным советом)

ІІ Международная научно-практическая конференция "Актуальные проблемы современной науки", 29.06.2015 (Совместная конференция с Международным научным центром)

II Международная научно-практическая конференция "Глобальные проблемы экономики и финансов", 28.05.2015 (Совместная конференция с Финансово-экономическим научным советом)

Актуальные проблемы экономики и финансов, 29.04.2015 (Совместная конференция с Финансово-экономическим научным советом)

Научный диспут: вопросы экономики и финансов, 31.03.2015 (Совместная конференция с Финансово-экономическим научным советом)

Актуальные проблемы современной науки, 27.03.2015 (Совместная конференция с Международным научным центром)

Глобальные проблемы экономики и финансов, 27.02.2015 (Совместная конференция с финансово-экономическим научным советом)



Аннотация: В данной статье описано модификацию алгоритма кластеризации CURE для работы в распределенной системе, а также результаты работы этого алгоритма, полученные с использованием средств Hadoop MapReduce.

Ключевые слова: Интеллектуальный анализ данных, Распределенная кластеризация, CURE, Hadoop, MapReduce.


Отрасль науки: Технические науки
Скачать статью (pdf)

Технічні науки

УДК 004.75

Yaremenko V.

student

National technical university of  Ukraine

«Igor Sikorsky Kyiv Polytechnic Institute»

Яременко Вадим Сергійович

студент

Національний технічний університет України

«Київський політехнічний інститут ім. Ігоря Сікорського»

Яременко Вадим Сергеевич

студент

Национальный технический университет Украины

«Киевский политехнический институт им. Игоря Сикорского»

DISTRIBUTED DATA CLUSTERING CURE ALGORITHM APPROBATION USING HADOOP MAPREDUCE

АПРОБАЦІЯ РОЗПОДІЛЕНОГО АЛГОРИТМУ КЛАСТЕРИЗАЦІЇ CURE З ВИКОРИСТАННЯМ HADOOP MAPREDUCE

АППРОБАЦИЯ РАСПРЕДЕЛЕННОГО АЛГОРИТМА КЛАСТЕРИЗАЦИИ CURE С ИСПОЛЬЗОВАНИЕМ HADOOP MAPREDUCE

Summary: In this article the modification of clustering CURE algorithm for distributed calculations and results of its work in the Hadoop MapReduce system are described.

Keywords: Data mining, Distributed clustering, CURE, Hadoop, MapReduce.

Анотація: У даній статті описано модифікацію алгоритму кластеризації CURE для роботи у розподіленій системі, а також результати роботи цього алгоритму, отримані з використанням засобів Hadoop MapReduce.

Ключові слова: Інтелектуальний аналіз даних, Розподілена кластеризація, CURE, Hadoop, MapReduce.

Аннотация: В данной статье описано модификацию алгоритма кластеризации CURE для работы в распределенной системе, а также результаты работы этого алгоритма, полученные с использованием средств Hadoop MapReduce.

Ключевые слова: Интеллектуальный анализ данных, Распределенная кластеризация, CURE, Hadoop, MapReduce.

1. Introduction

With the increase in the amount of information, it is necessary to develop algorithms for its fast and efficient processing. Parallel clustering algorithms and implementation techniques are the key to meeting the scalability and performance requirements entailed in such scientific data analyses. So far, there are some parallel clustering algorithms, but all of them have following drawbacks: a) They assume that all objects can reside in main memory at the same time; b) Their parallel systems have provided restricted programming models and used the restrictions to parallelize the computation  utomatically. Both assumptions areprohibitive for very large datasets with millions of objects. Therefore, dataset oriented parallel clustering algorithms should be developed [1, p.675]. One of such approaches is described in this article.

2. Parallel CURE algorithm based on MapReduce

In this section described the information about general CURE algorithm design and parallel MapReduce CURE algorithm design. First part is needed to present parallel parts of CURE algorithm, that could be implemented as map and reduce operations.

2.1. CURE algorithm

CURE (Clustering Using REpresentatives) algorithm begins from taking a small sample of the data and cluster it in main memory. In principle, any clustering method could be used, but as CURE is designed to handle oddly shaped clusters, it is often advisable to use a hierarchical method in which clusters are merged when they have a close pair of points.

During the second step it is necessary to Select a small set of points from each cluster to be representative points. These points should be chosen to be as far from one another as possible.

Then each of the representative points should be moved a fixed fraction of the distance between its location and the centroid of its cluster. Perhaps 20% is a good fraction to choose. Note that this step requires a Euclidean space, since otherwise, there might not be any notion of a line between two points [2, p.263].

The next phase of CURE is to merge two clusters if they have a pair of representative points, one from each cluster, that are sufficiently close. The user may pick the distance that defines “close.” This merging step can repeat, until there are no more sufficiently close clusters [2, p.264].

So, after the analysis of above steps I understood that such operations could be performed separately in the distributed system, no need to have the whole dataset on one PC. Even more at the one moment of time it is enough to have only the description of already known clusters (representative points and centroid) and new point from the dataset. In the next part the details of such approach are described.

2.2. CURE algorithm based on MapReduce

The general model consists of N nodes that run Map program and 1 node that runs a Reduce program. Chunks from datasets are input to the map program. One chunk is a description of one point (e.g. in Cartesian coordinate system it is an array with coordinates). Map program finishes its work after the full dataset on this node has being processed.

The output of map program is a set of key-value pairs, where the key is equals to 1 and the value is a set of representative points from cluster(i,j). In this case i – it is a number of the node and j – a cluster number from the ith node. For example, if on the node 2 there are 3 clusters of data, the output should be following: key 1 value cluster(2,1); key 1 value cluster(2,2); key 1 value cluster(2,3).

The reduce program gets the output of the map program. The main task of reduce program is to merge clusters produced from all datasets. After merging is done, the reduce program produces the resulting dataset which contains a description of each cluster: centroid and representative points [3, p.204].

3. Experimental results

For the experiment two programs were developed using the Java language. The first program has one thread and could be launched on each PC with pre-installed Java virtual machine and the second program is written for Hadoop MapReduce distributed system. Algorithms of both programs are described in the part 2 of this article.

As I don’t have the direct access to a real distributed system, I launched above programs on my local PC with such characteristics: Intel® CoreTM i7-2630QM 2GHz, 4 GB DDR3 RAM, Ubuntu OS. Hadoop MapReduce system was configured as a single-node cluster according to the official tutorial [4].

For the dataset generating one more program was developed. Input of this program is size of future dataset, dimensions, number of clusters, size of field (x-axis, y-axis borders). Output of this program is a file with floating-points values – Cartesian coordinates of each point. For this experiment such parameters were used: 2-dimensional coordinates, 100 MB, 250 MB, 500 MB, 1000 MB, 2000 MB, 4000 MB, 6000 MB and various number of clusters for each dataset.

Plot with received results could be found on the figure 1 below. With increasing of dataset size the efficiency of distributed CURE algorithm implementation is clearly visible. But in the future it is necessary to get results from the real environment, not from the local PC. Other parameters are following: field borders are [0; 500] for x-axis and [0; 500] for y-axis, number of clusters is 80, number of representatives points in cluster is 20, critical distance (to merge clusters) is 20, move fraction is 20%.

Fig. 1. Running time in comparison with dataset size [author work]

Also, it is necessary to mention that such results differ for different datasets. For example, in case of just one cluster programs run faster, because of small amount of points to process, otherwise a big amount of comparison operations will be performed between representative points of clusters. That’s why a lot of experiment’s details are described above.

4. Conclusion

In this article was described an approach of the distributed CURE algorithm implementation. The advantage of the described approach is in distributed calculations on each node separately. Also, it is not necessary to load a full dataset into the RAM because map task processes a chunk of data in a correct way.

After the description of distributed CURE algorithm’s there are presented details of efficiency of the proposed approach. As seen on the figure 1, the efficiency of the algorithm is especially noticeable with a growth of dataset size. The efficiency of the distributed implementation is seen on the dataset larger than 400 MB. Unfortunately, there is one disadvantage of received results: there were no ability to test Hadoop MapReduce program in the real distributed environment, so presented values have been got from the personal computer.

Reference:

  1. W. Zhao, H. Ma, Q. He (2009). Parallel K-Means Clustering Based on MapReduce. CloudCom 2009, LNCS 5931, pp. 674-679.
  2. J. Leskovec, A. Rajaraman, J. D. Ullman (2014). Mining Of Massive Datasets, Second Edition. Cambridge University Press. ISBN-13: 978-1107077232. Print.
  3. V. Yaremenko (2017). An approach for data clustering CURE algorithm implementation using the MapReduce technology. System Analysis and Information Technologies. 19-th International Conference SAIT 2017 Kyiv, Ukraine. ISBN 978-966-2748-94-2. Print.
  4. Hadoop: Setting up a Single Node Cluster. Access date: 06 May 2017. Access link: https://hadoop.apache.org/docs/stable/hadoop-project-dist/hadoop-common/SingleCluster.html.