A Heuristic Data Sampling Approach for Data Mining Preparation under Big Data Environment

海量資料近年來無論在業界或學界中都是非常熱門的話題，其資料的特性不僅數量龐大、來源紛雜，同時資料會不停地新增成長，基於這些特性而使得這些資料比起過往的資料內容更加難以分析，原有的資料探勘方式應用在海量資料時有非常大的可能遭遇到無法適用的狀況，特別是在執行時間上極有可能因為海量資料的特性而不能夠即時有效的產生分析結果，甚至可能因為資料的物件或屬性的數量過大造成完全無法取得結果。 在本篇研究中，我們使用基於關聯性規則的分類法作為資料探勘的分類方式，在不改動原有資料探勘方法的前提下，透過資料的選擇、前處理以及產生分類器結果後的評估、整合來解決所遭遇到的海量資料問題。 我們提出的方法分為兩個部分，首先是在初始狀態下對資料進行有目的的啟發式抽樣方法，使得抽樣出來的資料能夠足以代表整個海量資料的母體，再針對屬性的部分計算各個屬性分別的鑑別力與重要性，從中選擇出重要的屬性來做為後續資料探勘所用。針對資料分布型態的不同，我們可以視需求使用適當的方法調整抽樣的比率，使得某些特定的稀有分類資料能夠有相對應的分類規則能夠使用。第二部分則是特別處理資料成長增加的問題，首先使用初始狀態的方式分別對舊有資料以及新進資料進行抽樣並建立分類器，再透過新進資料與舊有資料的整合，將舊有與新進的分類器合併，重新驗證分類器中的規則，刪除不必要的規則並將其餘規則重新排序，成為最終調整過後的分類器並得以得以應用在資料上。 本研究所提出的方法應用在海量資料下的資料探勘時，透過實驗的結果能夠得知產生的結果與使用所有資料時能夠有相似的準確率，但能夠有效的減少所需要的執行時間，使得分析結果能夠迅速的產生，並將其結果應用在其他資料上。Big data has been a greatly popular topic among industries and academics. It contains several characteristics which are extreme scale, various data sources and incremental. These characteristics make big data harder to be analyzed while classic data mining techniques are highly possible to be infeasible. Especially, the processing time may not be efficient enough to generate analytic results in time due to the characteristics of big data. Furthermore, it could fail to generate any result since the number of objects and attributes are too large. In this study, we use classification based on association rules as our data mining technique. Under the premise of not changing existing data mining method, we try to solve the problem of big data by data preparation, integration and evaluation. The algorithm we proposed separates to two parts. The first part is a heuristic sampling method at the initial phase. Samples the data that is representative to the population of big data and then selects attributes which are important and discriminative. The sampling result can be further applied to following data mining techniques. For the purpose of handling different class distributions, we can apply undersampling method for some specific rare class to generate corresponding rules. The second part is dealing with incremental problem. Using the sampled data of initial phase from both the preliminary data and the incremental data and their classifiers, we merge the data and apply these data to verify the combined classifier. After pruning invalid rules and ranking all rules, we can obtain the final modified classifier as the result and apply the modified classifier on other data in the population. Applying the algorithm we proposed in data mining under big data environment, we can generate the result that is comparable to the one using the whole dataset. Moreover, the processing time is significantly reduced and thus the analytic result can be obtained in time to make further applications.Contents iv List of Figures vii List of Tables viii Chapter 1 Introduction 1 1.1 Motivation 1 1.2 Objective 6 1.3 Scope 7 Chapter 2 Literature Review 9 2.1 Big Data 9 2.2 Data Mining 11 2.3 Sampling 13 2.4 Conclusion 16 Chapter 3 Problem Description 18 3.1 Data Preparation Step for Data Mining Methods 19 3.2 Data Preparation under Big Data Environment 21 3.2.1 Big Data 21 3.2.2 Sampling 23 3.2.3 Attribute Selection 24 3.3 Problem Statement 25 3.3.1 Invasion Detection of Internet Packets 27 3.3.2 Conditions of Records under Big Data 29 3.3.3 Conditions of Attributes under Big Data 30 3.4 Summary 31 Chapter 4 The Heuristic Big-Data Sampling Algorithm (HBDSA) 33 4.1 Data and Attribute Sampling Algorithm (DASA) 35 4.1.1 Step 1: Data Sampling 36 4.1.2 Step 2: Attribute Selection 42 4.1.3 Step 3: Undersampling to Generate Rules of Rare Classes 45 4.2 Incremental Classifier Modifying Algorithm (ICMA) 47 4.2.1 Attributes Change between Original and Incremental Data 49 4.2.2 Classes Change between Original and Incremental Data 50 4.2.3 Combining Original and Incremental Classifiers and Data 50 4.2.4 Scenario 1: Without class and attributes change 51 4.2.5 Scenario 2: Removing an attribute 55 4.2.6 Scenario 3: Adding an attribute 57 4.2.7 Scenario 4: Removing a class 60 4.2.8 Scenario 5: Adding a class 63 4.3 Time Complexity of DASA and ICMA 66 Chapter 5 Computation Analysis 68 5.1 Data Description and Experiment Environment 68 5.2 Experiments for the DASA 70 5.2.1 Comparison between Sample and Population 70 5.2.2 Data with Uniform Class Distribution 74 5.2.3 Data with Long Tail Class Distribution 76 5.3 Experiments for the ICMA 79 5.3.1 Scenario 1: No changes in Classes 80 5.3.2 Scenario 2: Removing a Class 83 5.3.3 Scenario 3: Adding a Class 86 5.3.4 Scenario 4: Removing and Adding a Class 89 5.3.5 Effect over Certain Periods 92 5.4 Summary 94 Chapter 6 Conclusion and Future Work 96 6.1 Conclusion 96 6.2 Future Work 98 Reference 99 Appendix A Accuracy of Classifiers in Incremental Population 10