CN108446375A - A kind of multi-scale coupling rule and method based on Spark platforms - Google Patents

Abstract

The present invention provides a kind of multi-scale association rule method based on Spark platform, and this method comprises: build HDFS file system and Spark platform with virtual machine on physical server, and upload data set in HDFS file system; Spark platform from Read data in the HDFS file system and convert it into an elastic distributed data set RDD, and store it in memory; select multiple benchmark scales to divide the data set and perform parallel operations on the Spark platform to obtain frequent itemsets of the benchmark scale data set; Then, the association rules of the target data set are mined through the scale conversion mechanism, and the accuracy of the algorithm is obtained. The present invention combines the traditional association rule algorithm with the scale conversion mechanism, and only needs to mine the reference scale data set once to obtain the relevant knowledge under the target scale data set, which greatly improves the accuracy and efficiency of operations on the scale data set, and at the same time Implementation on the Spark platform further improves the data processing speed.

Description

A method of multi-scale association rules based on Spark platform

technical field

The invention relates to the technical fields of data mining and data processing, in particular to a method for multi-scale association rules based on a Spark platform.

Background technique

The era of big data has arrived. Data has penetrated into individuals and organizations in various fields in the world. Recording the entire process of its life cycle is an indispensable factor of production. Faced with the massive data brought by the information explosion, data mining technology is regarded as an indispensable analysis tool in both the scientific research field, commercial field and government agencies, and data mining research has also received unprecedented attention and attention. Data mining aims to discover the similarity of the nature of the research object and the consistency of behavior from a large amount of data with different forms and heterogeneous content, so as to condense certain rules and knowledge for decision-making.

Association rule mining is a widely used and highly practical research direction in the field of data mining, which aims to discover frequent and interesting associations and correlations between data items. Since association rule mining has a wide range of commercial applications, the research on it has been unabated. At present, the research on association rule mining is becoming more and more specific. Researchers often focus on emerging new problems and specific application fields, and conduct research on association rule mining, trying to solve problems on a more practical level. Today, simple "beer, diaper" rule mining can no longer meet the information needs of decision makers, and multi-level and multi-angle correlation pattern analysis is the key to solving practical problems.

Multi-scale science is a newly emerging discipline. Because it describes the structural and hierarchical nature of the research object, it has set off an upsurge of interdisciplinary research in the fields of mathematics, physics, biology, chemistry, and geosciences. At present, interdisciplinary research combined with multi-scale science is the general trend, and the field of data mining also conforms to this trend. In terms of theory and methods, multi-scale science and data mining technology are combined to analyze the multi-level and multi-scale connotations of mining results. Elevating ordinary mining results to multi-scale knowledge will facilitate the formation of multi-scale decision-making in practice; in addition, the idea of hierarchical and sub-scale processing and analysis of research objects in multi-scale science coincides with the idea of parallel computing , the study of multi-scale data mining methods is beneficial to efficiently deal with practical problems in the big data environment.

In 2009, Spark was originally born as a research project in the AMPLab of Berkeley University. The development language it adopted was scala, a language that combines object-oriented and functional programming. The core code part was originally composed of 63 scala files. In June 2013, the project was open sourced and became an Apache Foundation project, and in February 2014, it became a top open source project of the Apache Software Foundation. So far, developers from more than 200 companies have contributed to Spark, and more than 800 developers have participated in it. It is one of the most active open source projects in the current big data technology field. In the actual production environment, it has been deeply applied by many famous enterprises at home and abroad, and the number of nodes in the Spark cluster has exceeded 1,000. In this short period of more than 2 years, Spark has released nearly 15 versions with the strong support of many enterprises and developers.

As one of the most popular distributed computing frameworks today, Apache Spark is based on memory computing and parallel computing, and is very suitable for big data mining and machine learning. In terms of speed, it is based on memory calculation, and Hadoop writes the intermediate calculation results to the HDFS file system, and each read and write operation must read and write to the HDFS file system, so the running efficiency of Spark is 100 times faster than Hadoop. The disk is also 10 times faster than Hadoop. Therefore, Spark is more suitable for running more complex algorithms, such as iterative calculations and graph calculations. Not only that, Spark supports multiple operations on data sets, such as map, filter, flatmap, etc. In contrast, MapReduce only supports two operations of map and reduce.

In short, combining data mining algorithms with multi-scale disciplines on the Spark platform can not only improve efficiency, but also effectively utilize resources.

Contents of the invention

The purpose of the present invention is to provide a multi-scale association rule method based on the Spark platform, which combines multi-scale domain knowledge and association rule algorithms and realizes it on the Spark platform. Compared with the algorithm, the execution efficiency and accuracy of the present invention have been greatly improved.

The present invention is realized through the following steps.

A method for multi-scale association rules based on the Spark platform, including:

Step 1: Construct the HDFS file system and Spark platform with virtual machines on the physical server, and upload the dataset to the HDFS file system;

Step 2: Submit the job to the Spark platform through the client, and the Spark platform reads the data from the HDFS file system and converts it into an elastic distributed dataset RDD, and stores it in memory;

Step 3: Select multiple benchmark scales BS, and determine the data set ds _BS of each benchmark scale. Since each RDD corresponds to multiple partitions, a benchmark scale dataset is run in each partition, and each partition is operated in parallel;

Step 4: Mining each benchmark scale data set with the minimum support min_sup in each partition to obtain the set FI _i of frequent itemsets of each benchmark scale data set, and obtain the union of the above frequent itemset sets FI _C as the target scale data Set ds _SO frequent itemsets set of candidate itemsets;

Step 5. Determine the weight matrix λ of the benchmark-scale dataset to the target-scale dataset by kriging, which is used to estimate the support of frequent itemsets in the target-scale dataset;

Step 6: Screen the final frequent itemsets of the target scale data set, generate association rules, and calculate the algorithm accuracy of each partition, and then calculate the mean value of the accuracy as the overall experimental result.

Wherein, in the step 3, the number of partitions in the RDD is set according to the number of reference scales selected by the user, and a certain number of concurrent threads are started to read data.

Wherein, in the step 4, for the multi-scale association rule algorithm, only correlation mining is performed on the benchmark scale data set, and the set of frequent itemsets of the benchmark scale data set is obtained, and then the frequent itemsets of the target scale data set are derived, and frequent Multiscale Transformation of Itemsets.

Wherein, in the step 5, the linear estimator is first defined by the kriging method, and then the kriging coefficient λ in the linear estimator is calculated, and the support degree estimation value in the target scale data set and the support degree in the reference scale data set Corresponding to the estimated value and sample point data of the defined linear equation respectively.

Wherein, in the step 6, the estimated support of all candidate itemsets is compared with the minimum support min_sup, and the frequent itemsets whose estimated support is not less than min_sup are selected to form the final frequent itemset set FI of the target scale data set, and Generate association rules according to the minimum confidence min_conf.

Compared with the prior art, the present invention has the following advantages:

The present invention combines the scale conversion mechanism in the multi-scale field with the association rule algorithm in data mining, and realizes the multi-scale conversion of knowledge with the multi-scale data mining algorithm framework and specific multi-scale association rule mining. From the perspective of the algorithm, the algorithm is Implemented on a data set with multi-scale characteristics, the accuracy and running speed will be greatly improved, which has considerable practical significance.

Benming also runs the multi-scale association rule algorithm on the Spark platform. Under the background of massive data generated all the time, the parallelization mode based on the Spark platform will further improve the data processing efficiency.

Description of drawings

Fig. 1 is method flowchart of the present invention;

Figure 2 is the implementation flow chart on the Spark platform.

Detailed ways

In order to make the object, technical solution and advantages of the present invention clearer, the present invention will be further described in detail below in conjunction with the accompanying drawings and embodiments. It should be understood that the specific embodiments described here are only used to explain the present invention, not to limit the present invention.

Combining Figure 1 and Figure 2, a multi-scale association rule method based on the Spark platform includes the following steps:

Step 1: Construct the HDFS file system and Spark platform with virtual machines on the physical server, and upload the dataset to the HDFS file system;

Step 2: Submit the job to the Spark platform through the client, and the Spark platform reads the data from the HDFS file system and converts it into an elastic distributed dataset RDD, and stores it in memory;

Step 3: Select multiple benchmark scales BS, determine the data set ds _BS of each benchmark scale, call the parallelize method of SparkContext, parallelize the data set, and convert it into a distributed RDD. Each RDD is composed of many partitions, so Run a benchmark dataset in each partition, and each partition operates in parallel.

This process sets the number of partitions in the RDD according to the number of benchmark scales selected by the user and starts a certain number of concurrent threads to read data.

Step 4: Mining each benchmark scale data set with the minimum support min_sup in each partition to obtain the set FI _i of frequent itemsets of each benchmark scale data set, and obtain the union FI _C of the above frequent itemsets as the target scale data Set ds _SO frequent item set candidate item set, this candidate item set set can reflect the hidden frequent item set in the target scale data set to the greatest extent.

To put it simply, this process only performs correlation mining on the benchmark scale dataset, obtains the set of frequent itemsets of the benchmark scale dataset, and then derives the frequent itemsets of the target scale dataset, and performs multi-scale conversion of frequent itemsets.

Step 5: Determine the weight matrix λ of the benchmark-scale dataset to the target-scale dataset by kriging, which is used to estimate the support of frequent itemsets in the target-scale dataset;

In step S500, the Kriging method defines a linear estimator:

in, is the value to be estimated, Z( _xi ) is the sample data, λ is the Kriging coefficient, expressed as:

λ=K ^- 1D

Step S501, determine the similarity matrix K between benchmark scale datasets, we calculate the matrix elements M _ij through the Jaccard similarity coefficient:

Among them, FI _i and FI _j represent the collection of frequent itemsets of data sets of different benchmark scales.

Step S502, determine the matrix D, when the scale is pushed up (base scale BS ∈ target scale SO), the element of D is the ratio of the base scale dataset to the upper scale dataset; the scale is pushed down (target scale SO ∈ reference scale BS), the element of D is the Jaccard similarity coefficient of the two;

Step S503, applying the linear estimator defined by the kriging method to find the estimated support value of the target scale data set:

Process all candidate item sets of the target scale dataset in step 4 in the manner described above.

Step 6: Screen the final frequent itemsets of the target scale dataset, generate association rules, and calculate the algorithm accuracy and execution time of each partition, and then calculate the average of the accuracy and running time as the overall experimental result.

Compare the estimated support of all candidate item sets with the minimum support min_sup, select frequent itemsets whose estimated support is not less than min_sup to form the final frequent itemset set FI of the target scale data set, and set the minimum confidence min_conf Generate association rules; use the Action operator under the spark platform to obtain the accuracy of the algorithm under each partitioned data set, and then calculate its mean value as the final result.

Step S600, calculating confidence for each generated association rule, the calculation formula is:

Given the parameter minimum confidence threshold min_conf, compare the confidence calculated by each of the above association rules with min_conf, and only leave the association rules with confidence greater than min_conf;

Step S601, calculating the final accuracy of the algorithm, the calculation formula is:

Among them, FI _m is the frequent itemset mined by the algorithm, FI _o is the real frequent itemset contained in the target scale data set, fp and fn are the frequent itemsets misjudged, and n is the number of partitions in the RDD (that is, the Set the number of benchmark scales).

Claims (5)

1. A Spark platform-based multi-scale association rule method is characterized by comprising the following steps:

step 1: constructing an HDFS file system with a virtual machine and a Spark platform on a physical server, and uploading a data set to the HDFS file system;

step 2: submitting a job to a Spark platform through a client, reading data from an HDFS file system by the Spark platform, converting the data into an elastic distributed data set RDD, and storing the RDD in a memory;

and step 3: selecting a plurality of reference scales BSData set ds for each reference scale_BSEach RDD corresponds to a plurality of partition partitions, so that a reference scale data set is operated in each partition, and each partition is operated in parallel;

and 4, step 4: mining each reference scale data set with the minimum support degree min _ sup in each partition to obtain a set FI of frequent item sets of each reference scale data set_iAnd finding out a union FI of the frequent item sets_CAs a target scale dataset ds_SOA candidate item set of the frequent item set;

and 5: determining a weight matrix lambda of the reference scale data set to the target scale data set by a kriging method, and estimating the support degree of frequent item sets in the target scale data set;

step 6: and screening the final frequent item set of the target scale data set of each partition, generating an association rule, calculating the algorithm accuracy of each partition, and further obtaining the average value of the accuracy as a final result.

2. The Spark platform based multi-scale association rule method as claimed in claim 1, wherein in step 3, the partition number in the RDD is set according to the reference scale number selected by the user and a certain number of concurrent threads are started to read data.

3. The Spark platform based multi-scale association rule method as claimed in claim 1, wherein in step 4, for the multi-scale association rule algorithm, only the reference scale dataset is subjected to correlation mining, a set of frequent item sets of the reference scale dataset is obtained, then the frequent item sets of the target scale dataset are deduced, and multi-scale conversion of the frequent item sets is performed.

4. The Spark platform based multi-scale association rule method according to claim 1, wherein the specific process of step 5 is as follows:

step S500, kriging defines a linear estimator:

wherein,to be evaluated, Z (x)_i) For the sample data, λ is the kriging coefficient, expressed as:

λ＝K^-1D

step S501, a similarity matrix K between the reference scale data sets is determined, and matrix elements M are calculated through Jaccard similarity coefficients_ij：

Step S502, determining a matrix D, wherein when the scale is pushed up, the element of D is the ratio of the number of the reference scale data set to the number of the upper scale data set; when the scale is pushed down, the element of D is the Jaccard similarity coefficient of the two;

step S503, solving the support degree estimated value of the target scale data set by applying the linear estimator defined by the kriging method:

all candidate sets of the target scale data set in step 4 are processed in the manner described above.

5. The Spark platform based multi-scale association rule method as claimed in claim 1, wherein in step 6, the algorithm accuracy under each partition data set is obtained through an Action operator under the Spark platform, and then the average value is obtained as the final result,

step S600, calculating a confidence for each generated association rule, where the calculation formula is:

giving a parameter minimum confidence threshold value min _ conf, comparing the confidence calculated by each association rule with min _ conf, and only leaving the association rules with the confidence greater than min _ conf;

step S601, the final accuracy of the algorithm is obtained, and the calculation formula is as follows:

wherein, FI_mFor frequent item sets mined by the algorithm, FI_oFor the real frequent item set contained in the target scale data set, fp and fn are wrong judged frequent item sets, and n is the number of partition in the RDD (i.e. the number of set reference scales).