Chương 1 và chương 2 giới thiệu các khái niệm về tập coreset và các kiến thức liên quan trong. Trong các chương này, chúng tôi cũng tóm tắt ngắn gọn về Apache Spark và các định lý được sử dụng trong luận văn. • Trong chương 3, chúng tôi đề xuất và chứng minh phương pháp đầu tiên để xây dựng tập coreset dựa trên giải thuật Farthest-First-Traversal và giải thuật ProTraS [58] cho bài toán gôm cụm k-median và k-means. Chúng tôi cũng tiến hành đánh giá giải thuật này trong cuối chương.
• Trong chương 4, dựa trên các công trình về lightweight coreset [12], chúng tôi đề xuất và chứng minh tính đúng đắn của phương pháp xây dựng coreset thứ hai, α - lightweight coreset, cho bài toán gôm cụm k- means, đây được xem là một dạng tổng quát và có thể điều chỉnh hệ số của lightweight coreset. • Trong chương 5, chúng tôi sử dụng phương pháp α - lightweight coreset cùng với phương pháp tổng quát hoá dữ liệu để giải quyết tổng thể bài toán – gôm cụm trên tập dữ liệu có kích thước lớn. Chúng tôi cũng sử dụng nền tảng Apache Spark để bài toán được giải quyết nhanh hơn. Để đánh giá độ chính xác, chúng tôi tiến hành thử nghiệm và so sánh kết quả trên các tập mẫu benchmark có kích thước lớn.
viii Declaration of Authorship I, NGUYEN LE HOANG, declare that this thesis - Clustering Large Datasets based on Data Sampling and Spark, and the work presented in this thesis are my own. I confirm that: • This work was done wholly or mainly while in candidature for a Master of Science at University of Technology, VNU-HCMC. • No part of this thesis has previously been submitted for any degree or any other qualification at this University or any other institution. • Where I have quoted from the work of others, the source is always given.
With the exception of such quotations, this thesis is entirely my own work. • I have acknowledged all main sources of help. • Where the thesis is based on work done by myself jointly with others, I have made clear exactly what was done by others and what I have contributed my- self. Signed: Date: ix Contents Acknowledgements v Abstract vi List of Figures xii List of Tables xiii List of Algorithms xiv 1 Introduction 1 1.2 The Scope of Research .4 Organization of Thesis .5 Publications relevant to this Thesis.
6 2 Background and Related Works 7 2.1 k-Means and k-Means++ Clustering .2 Some Coreset Constructions .1 What is Apache Spark? .2 Why Apache Spark? .4 Bounds on Sample Complexity of Learning. 14 3 FFT-based Coresets 15 3.1 Farthest-First-Traversal Algorithm .2 FFT-based Coresets for k-Median and k-Means Clustering .3 ProTraS algorithm and limitations .2 Drawbacks in ProTraS .4 Proposed FFT-based Coreset Construction .3 Decrease the Computational Complexity .2 Results and Discussion. 29 4 General Lightweight Coresets 33 4.2 The α-Lightweight Coreset .2 Theorem about the Optimal Solutions. 39 5 Clustering Large Datasets via Coresets and Spark 45 5.2 Built-in k-Means clustering in Spark .2 Experimental Data Sets.
59 xii List of Figures 1.1 Big Data properties .2 Machine Learning: Supervised vs Unsupervised .1 Spark Logo - https://spark.2 The Components of Spark .1 Original-R15 (small cluster) and scaling-R15 .2 Some data sets for experiments .3 ARI in relation to subsample size for datasets D1 - D8 .4 ARI in relation to subsample size for datasets D9 - D16 .1 ARI and Runtime of Birch1 in relation to full data .2 ARI and Runtime of Birch2 in relation to full data .3 ARI and Runtime of Birch3 in relation to full data .4 ARI and Runtime of ConfLongDemo in relation to full data .5 ARI and Runtime of KDDCupBio in relation to full data. 51 xiii List of Tables 3.1 Data sets for Experiments .2 Experimental Results - Adjusted Rand Index Comparison .3 Experimental Results - Time Comparison .1 Data sets for Experiments .2 Experimental Results for dataset Birch1 .3 Experimental Results for dataset Birch2 .4 Experimental Results for dataset Birch3 .5 Experimental Results for dataset ConfLongDemo .6 Experimental Results for dataset KDDCup Bio. 56 xiv List of Algorithms 1 k-Means Clustering - Lloyd’s Algorithm [42]. 8 2 D2 Sampling for k-Means++ [6].
9 3 Farthest-First-Traversal algorithm. 22 5 Proposed FFT-based Coreset Construction. 35 7 Proposed α - Lightweight Coreset Construction .1 Overview Over the past few years, the development of technology has lead to the rapid increas- ing in the amount of data. Twenty years ago, almost data were just from sciences, but the explosion of Internet takes human to new era of data.
They are now exist- ing everywhere around us. For instance, the growth of smart city and Internet of Things (IoT) devices such as aerial (remote sensing), cameras, microphones, radio- frequency identification (RFID) readers, wireless sensor networks, etc. create a lot of data every second. Besides, the increasing in mobile and personal devices such as smart phones or tablets also make the data bigger every day, especially through photo and video sharing in popular social networks like Facebook, Twitter, YouTube, etc.
Many researches have shown that the amount of data created each year is growing faster than ever before and they estimate that by 2020, every human on the planet will be creating 1.7 megabytes of information each second; and in only a year, the accu- mulated world data will grow to 44 zettabytes 1 [46]. Another research from IDC predict that the amount of global data captured in 2025 will reach 163 zettabytes, a tenfold increase compared to 2016 [55] Consequently, researchers now have to face new hard situation: solving prob- lems for data that have big amount in volume, variety, velocity, veracity and value. For the demand of understanding and explaining these data in order to solve reality problems, it is very hard for human if there is no help from machine. That’s why machine learning plays an important role in this decade as well as in the future.
By applying machine learning combined with artificial intelligence (AI), sci- entists can create systems having the ability to automatically learn and improve from experience without being explicitly programmed. For each specific purpose, machine learning is divided into two categories: su- pervised and unsupervised. Supervised learning is a kind of training model where the training sets go along with provided target labels, the system will learn from these 1 One zettabyte is equivalent to one billion gigabytes. 2 Image source: https://www.co/blog/what-is-big-data/ Chapter 1.1: Big Data properties training sets and then is used to predict or classify future instances.
In contrast, unsu- pervised machine learning approaches extract information from data sets where such explicit labels are not available. The importance of this field is expected to grow as it is estimated that 85% of global data in 2025 will be unlabeled [55]. In particular, data clustering - the tasks of grouping together similar objects into clusters — seems to be a fruitful approach for analyzing that data. Applications are broad and include fields such as computer vision [61], information retrieval [35], computational ge- ometry [36] and recommendation systems [41].
Furthermore, clustering techniques can also be used to learn data representations that are used in downstream prediction tasks such as classification and regression [16]. Machine learning categories can be described briefly in Figure 1. In general, clustering is one of the most popular techniques in machine learning and is used widely in large-scale data analysis. The target of clustering is partition- ing a set of objects into groups such that objects in same group are similar to each other and objects in different groups are dissimilar to each other.
This technique, due to its importance and application in reality, has a lot of investigations and various algorithms. For example, we can use BIRCH [68], CURE [27] which are belonging to hierarchical clustering, also known as connectivity-based clustering, for solving problems based on the idea of objects being more related to nearby objects than to objects farther away. If the problems are closely related to statistics, we can use distribution-based clustering such as Gaussian Mixture Model (GMM) [66] or DB- CLASD [53]. For matter based on density clustering in which the data that is in the 3 Image source: https://towardsdatascience.com/supervised-vs-unsupervised-learning Chapter 1.2: Machine Learning: Supervised vs Unsupervised region with high density of the data space is considered to belong to the same clus- ter [38], we can use Mean-shift [17], DBSCAN [20] - the most well-known density- based clustering algorithm, or OPTICS [4] - an improvement of DBSCAN.
And one of the most common approaches for clustering is based on partition in which the basic idea is to assign the centers of data points to some random objects, the actual cen- ters will be reveal through several iterations until a stop condition is satisfied. Some common algorithms of this kind are k-means [45], k-medoids [49], CLARA [37], CLARANS [48]. For a more detail, we refer readers to the survey of clustering algorithms by R.Xu (2005) [65] and by D. Xu (2015) [64] In fact, there are a lot of clustering algorithms and improvements that can be used in applications.
Each one has its own benefits and drawbacks as well. The question of choosing a suitable clustering algorithm is an important and difficult problem that users must deal with when they have to solve situations with specific configurations and settings. There are some research about this such as in [14], [39], [67] where explain about the quality of clusters in some circumstances. However, in the scope of this thesis, we do not cover this issue and various clustering algorithms, instead of this, we fix and select one of the most popular clustering algorithm - the k- means clustering.
We will use this algorithm throughout of this report and investigate methods that can deal with k-means clustering for large-scale data set. Moreover, to design a complete solution that can cluster and analyze large-scale data is still a challenge for data scientists. Many methods have been proposed for several years to deal with machine learning for big data. One of the simplest way is depending on infrastructure and hardware: the more powerful and modern machine we have, the more complicated and larger amount of data we can solve.
This solution is quite easy but costs a lot of money and few people can afford this. Another option is finding suitable algorithms to reduce the computational complexity from the input size that may contain millions or billions of data points. There are some approach methods such as data compression in [69], [1], data deduplication [19], dimension Chapter 1. Introduction 4 reduction [25], [60], [51], etc.
For a survey about this, readers can find more useful information in [54]. Among big data reduction methods, data sampling is one of the popular options that are closely related to machine learning and data mining for researchers. The key idea of data sampling is that instead of solving problems on the full data with large-scale size, we can find the answer for the subset of this data; this result is then used as the baseline for finding the actual solution for original data set. This leads us to a new difficulty: finding a subset that must be small enough for effectively reducing computational complexity but must keep all representative characteristics of original data.
And, this difficulty is the motivation for us to do this research and this thesis as well.2 The Scope of Research In this thesis, we will propose a solution for a problem of clustering large datasets. We use the word "large" to indicate the data that has "big" in volume, not the whole characteristics of big data described in previous section with 5 V’s (Volume, Variety, Value, Velocity and Veracity) (Figure 1.