CN103258049A - Association rule mining method based on mass data - Google Patents

Abstract

The invention discloses an association rule mining method based on massive data, and relates to the technical field of information processing. Specifically, the input data is divided according to the records, the frequent 1-itemset table is constructed, and then the data is projected on the frequent 1-itemset, the projected data is stored in the established grouping table, and the local frequent pattern tree is constructed, and then Mining data association rules for frequent pattern trees. In the process of mining frequent pattern trees, the pruning strategy is adopted to reduce the number of iterations of frequent pattern tree mining, and each computing node only processes a part of data records, which solves the problem of Massive data cannot be read into memory by a single machine for processing; in addition, multiple nodes participate in parallel processing, effectively improving processing efficiency.

Description

A Method of Mining Association Rules Based on Massive Data

technical field

The invention relates to the field of data mining, in particular to a method for realizing data association rule mining.

Background technique

With the rapid development of information technology, it has become a very difficult task to discover valuable information and knowledge from increasingly large and complex data to serve the purpose of decision-making. Data mining technology came into being in this context. Association rule mining is an important branch of data mining, and it is also the most widely used type of data mining.

The purpose of mining data association rules is to discover the noteworthy associations or correlations among a large number of data items, and the typical application is shopping basket analysis in the retail industry. The so-called shopping basket analysis refers to the study of the association rules of the data, and discovers the connection between different commodities in the transaction database, which helps to find out the pattern of customer purchasing behavior. For example, if bread and milk are often purchased by customers at the same time, placing them together can help increase sales of both items. In order to measure the importance of rules, association rules usually use support and credibility as metrics. The degree of support can indicate the importance of commodities in supermarket sales, and the degree of credibility reflects the degree of correlation between commodities. If 60% of the transactions that buy bread buy both bread and milk, then the association rule "bread and milk" (meaning that if you buy bread, you buy milk) has 60% confidence.

The support of association rules (meaning that A and B exist simultaneously) in transaction database D can be represented by probability, and the credibility of association rules in transaction database D is in those transactions containing A in transaction database D, The probability that B also occurs at the same time is the conditional probability.

The support degree of an itemset X in the transaction database D is the percentage of transactions containing X in the transaction database D to the total number of transactions, that is, the probability P(X). For an itemset X, if its support is greater than or equal to the pre-specified support threshold min_s, X is called a frequent itemset.

The basic idea of the FP-growth (Frequent Pattern Growth Algorithm) algorithm is to use the tree structure to compress transactions while retaining the relationship between attributes in the transaction. The important step of the algorithm is the establishment and mining of frequent pattern trees, which need to scan transaction sets twice: the first scan transaction set D, find frequent 1-itemset sets, and arrange the sets in descending order of support count; the second The transaction set D is scanned twice, and the frequent pattern tree is constructed with "Null" as the root node. In order to quickly traverse the frequent pattern tree, an item header table T is created, each row in the table represents a frequent item and its frequency of occurrence, and the pointer is set to point to its corresponding node in the frequent pattern tree, and finally the frequent pattern tree is recursed Mining to find all frequent itemsets. The specific algorithm flow is as follows:

(1) Create the original frequent pattern tree

1) Scan the transaction set T, find out the items whose support count meets the condition, and combine these items into a frequent 1-item set L, and sort L in descending order based on the support count to get the 1-item set list.

2) Create an original frequent pattern tree with "Null" as the root node.

3) Create an item header table. For the convenience of traversing the original frequent pattern tree, each row in the item header table represents a frequent item, and has a corresponding pointer pointing to its node in the frequent pattern tree.

4) Traverse the transaction set T once, adjust the item order of all transactions in T according to the 1-itemset list, and create a transaction branch for each transaction with the adjusted item order. Branches share paths if they can, and record the number of shared transactions on each node.

(2) Recursively find all frequent itemsets on the original frequent pattern tree

1) The initial value of the suffix pattern a is the root node Null, that is, a=Null. A recursive method is used to search for frequent itemsets on the frequent pattern tree. If the frequent pattern tree has only one branch, then a combination of nodes on the branch path is a prefix pattern b. Eliminate the nodes on the branch path that do not meet the minimum support, and merge any set b composed of the remaining node values with the suffix pattern a to obtain all corresponding frequent itemsets. Where b _i is a prefix pattern, otherwise increase a, a=a∪{E _i } (where E _i is the last item in the 1-itemset table, which is the minimum item of support count). Then construct the conditional pattern base and conditional frequent pattern tree of the suffix pattern. (The conditional pattern base of a refers to all branches with E _i as the leaf node in the frequent pattern tree. The conditional frequent pattern tree of A refers to the conditional pattern base of a as the transaction according to the method in step 1. The new frequent pattern tree created)

2) Use the same method to recursively search for frequent itemsets on the conditional frequent pattern tree (the suffix pattern a is {E _i } at this time).

3) For each maximum frequent itemset, take all its subsets, and each subset is a frequent itemset.

The above-mentioned FP-growth (Frequent Pattern Growth Algorithm) data mining method can be conveniently implemented on a single computer for a small amount of data records. However, when mining data association rules for massive data records, on the one hand, due to the limited memory capacity of a single machine, it is impossible to read massive data; Long, in the actual data business application, the efficiency is very low.

Therefore, for association rule mining of massive data in practical applications, how to effectively improve processing efficiency is a major problem that needs to be solved in data association rule mining.

Cloud computing has massive storage capacity and elastically variable computing power. Therefore, massive data mining and association rule acquisition based on cloud computing has become an efficient and reliable solution to the inadaptability of traditional centralized data mining to the dynamic growth of massive data. letter path.

Contents of the invention

Aiming at the problem of mining association rules of massive data existing in the prior art, the present invention conducts in-depth analysis and research on the structure and mining process of the frequent pattern tree of the classic FP-growth algorithm, and analyzes the single-path and multi-path mining methods of the frequent pattern tree , a pruning method is proposed, and a pruning frequent pattern tree algorithm is proposed; the number of iterations of some branches can be reduced. Then, using the MapReduce programming technology of cloud computing, the steps of the pruning frequent pattern tree algorithm are parallelized, which improves the data processing ability and efficiency of the pruning frequent pattern tree algorithm.

The technical solution of the present invention to solve the above-mentioned technical problems is: to propose a data association rule mining implementation method for massive data, including the following steps:

1) Divide the input data according to the records, and distribute the divided data to multiple computing nodes, each computing node counts the frequency of 1-itemsets in parallel, sorts the results according to the frequency of 1-itemsets, and constructs frequent 1-itemsets Itemset table, delete itemsets smaller than a given threshold, and generate the final frequent 1-itemset table;

2) Group frequent 1-itemsets according to the frequent 1-itemset table, then perform data projection on frequent 1-itemsets, and store the projected data in the established grouping table;

，那么前缀路径集合中长路径集合B中的项集i就可以剪枝和短路径集合A合并。3) Each node counts the data in the grouping table, builds a local frequent pattern tree, and then mines the data association rules of the frequent pattern tree. When traversing the frequent pattern tree, if the item set i is in the frequent pattern tree There exists a set of prefix paths A, B in and satisfies

, then the item set i in the long path set B in the prefix path set can be pruned and merged with the short path set A.

Suppose the frequency of i in set A is m, the frequency of i in set B is n, the minimum support is q, and m≥q, n<q. The conditional pattern base of i obtained from the unpruned frequent pattern tree is {{A:m},{B:n}}, and the resulting frequent pattern is {Ai:m+n}. After pruning the frequent pattern tree, the conditional pattern base of i is {A:m+n}, and the resulting frequent pattern is {Ai:m+n}. The frequent pattern containing i after pruning is equal to the frequent pattern containing i without pruning. Therefore, i in set B can be pruned and merged with short path set A.

4) Mining the frequent patterns of each subtree, and then merging the frequent patterns mined from each subtree to obtain the final frequent pattern.

Further, the step 1) specifically includes the following steps:

11) Divide data objects evenly by records, so that each group of data contains balanced data objects;

12) In each set of data, count the number of occurrences of each item set;

13) Sort according to the frequency of item sets, and then compare with a given threshold (absolute support count), delete itemsets smaller than the given threshold, and finally create a Hash table to store frequent 1-itemsets, the The table is named frequent 1-itemset table.

Further, the step 2) specifically includes the following steps:

21) According to the frequent 1-itemset table, group the frequent 1-itemset data, project the source data on the grouped data, create a Hash table to store the projected data, and name the stored table as the grouping table;

22) Set the size of the grouping table according to the number of nodes in the cluster, and the size of the grouping table is equal to the number of Maps set in MapReduce.

Further, the step 4) specifically includes the following steps:

41) Mining frequent patterns on the frequent pattern tree after pruning;

42) Merge all frequent patterns.

Further, in step 13), frequent 1-itemsets are generated, where the data structure of frequent 1-itemsets is in the form of Hash, and each Hash data is obtained by one-way Hash calculation of q data objects, and each data object participates in t +1 Hash calculation, get q(t+1) Hash data.

Further, in the step 21), the data structure of the grouping table is in Hash form, and the grouping table stores the grouped item sets and the row number of the data where the item sets are located; record the records where the data is located, project the source data, and divide the data into in the corresponding group.

In the data association rule mining method provided by the present invention, multiple computing nodes are used to participate in the data item statistical process in parallel and then merge the statistical results, which speeds up the generation of frequent 1-item sets; and through data grouping, and then data distribution , and finally mine the association rules through the distributed data sets on the computing nodes, in which each node adopts the pruning strategy in the process of frequent pattern tree mining, which reduces the number of iterations of data mining and improves the processing efficiency. At the same time, each computing node only processes a part of data records, which solves the problem that massive data cannot be read into memory by a single machine for processing. The invention can be used in the extraction of association rules of data mining; it is suitable for data processing in the fields of commerce, enterprises, government departments and scientific research; it is also applicable to various occasions that need to extract the association of data.

Other advantages, objects, and features of the present invention will be set forth in the ensuing description to some extent, and to some extent, will be obvious to those skilled in the art based on the investigation and research below, or can be Learn from the practice of the invention.

Description of drawings

In order to make the purpose, technical solutions and advantages of the present invention clearer, the present invention will be further described in detail below in conjunction with the accompanying drawings:

Figure 1 is a schematic diagram of the frequent pattern tree structure established by the data set in Table 1;

Fig. 2 is a flowchart of the present invention;

Fig. 3 is the frame diagram of parallel pruning frequent pattern tree algorithm;

Fig. 4 is a schematic structural diagram of a cloud computing platform.

Detailed ways

The method for implementing data association rule mining provided by the embodiment of the present invention will be described in detail below in conjunction with the accompanying drawings.

Fig. 1 is a schematic structural diagram of frequent pattern tree pruning provided by an embodiment of the present invention, including:

Perform frequent 1-itemset statistics on the source data to obtain the conditional pattern base, construct the frequent pattern tree, and adopt an optimization method in the process of mining the frequent pattern tree. See Figure 2 for specific steps, including the following steps:

Divide the input data and distribute it to multiple computing nodes. Each computing node counts the frequency of 1-itemsets in parallel, sorts them according to the frequency of 1-itemsets, and deletes 1-itemsets smaller than a given threshold to construct frequent 1-itemsets. -itemset table; according to the frequent 1-itemset table to group frequent 1-itemsets to establish a grouping table, then perform data projection on frequent 1-itemsets, and store the projected data in the grouping table; calculated by each The node counts the data in the grouping table, builds a local frequent pattern tree, and then mines data association rules for each subtree of the frequent pattern tree. If item set i has prefix path sets A and B in the frequent pattern tree, and satisfies , then item set i in set B can be pruned and merged with set A; carry out data association rule mining on each frequent pattern subtree, and merge frequent patterns mined from each frequent pattern subtree.

Divide the data objects evenly according to the records, so that each group of data contains balanced data objects; in each group of data, count the number of occurrences of each item set; sort according to the frequency of occurrence of the item set, and the given threshold is absolute support Counting, frequent 1-itemset table is a Hash table that stores frequent 1-itemsets. Wherein, each Hash data in the Hash table is obtained by performing one-way Hash calculation on q data objects, and each data object participates in t+1 Hash calculations to obtain q(t+1) Hash data.

Project the grouped data to the source data, create a Hash table to store the projected data, and name the table as a grouping table; set the size of the grouping table according to the number of computing nodes, and the size of the grouping table is equal to the function set by the parallel programming mode MapReduce Number of maps. The data structure of the grouping table is in Hash form, which stores the grouped itemset and the row number of the data where the itemset is located; records the row number where the data is located, projects the source data, and divides the data into corresponding groups.

，那么前缀路径集合中长路径集合B中的项集i就可以剪枝和短路径集合A合并，For the constructed frequent pattern tree, traverse each item set in it, if the item set i is infrequent on a certain path, assuming that the item set i has prefix path sets A and B in the frequent pattern tree, and satisfies

, then the item set i in the long path set B in the prefix path set can be pruned and merged with the short path set A,

Specifically: Assume that the frequency of i in set A is m, the frequency of i in set B is n, the minimum support is q, and m≥q, n<q. The conditional pattern base of i obtained from the unpruned frequent pattern tree is {{A:m},{B:n}}, and the resulting frequent pattern is {Ai:m+n}. After pruning the frequent pattern tree, the conditional pattern base of i is {A:m+n}, and the resulting frequent pattern is {Ai:m+n}. The frequent pattern containing i after pruning is equal to the frequent pattern containing i without pruning. Therefore, i in set B can be pruned and merged with short path set A.

For multi-path itemsets, some itemsets have a support degree on a certain path that is less than a given threshold, so the above method can be used to prune. After pruning, if it is a single path, it can be considered as a single path. This can reduce the recursion times of itemset mining and improve mining efficiency.

Take the transaction data set D in Table 1 as an example to illustrate the process of the pruning method. If the minimum support is 2, after the frequent pattern tree in Figure 1 is established, the HeaderTable (item header table) information corresponding to the frequent pattern tree can be obtained, and the prefix path of each node of each item can be found by using the information of the node chain in the HeaderTable .

Table 1 Dataset D

It can be seen from Figure 1 that one prefix path of I5 item is A={I2, I1}, another prefix path of I5 item is B={I2, I1, I3}, and A is a proper subset of B, satisfying the above mentioned Therefore, after pruning the frequent pattern tree of I5, I5 changes from the original multi-path to single-path, and directly mines frequent items, reducing the number of recursive mining.

Fig. 3 is the flow chart of parallel pruning frequent pattern tree algorithm steps provided by the embodiment of the present invention, including the following steps:

Pruning frequent pattern tree algorithm shows certain advantages in serial algorithm. Find frequent patterns by constructing frequent pattern trees. However, when the data set reaches a certain scale, it is unrealistic to construct memory-based frequent pattern trees. Therefore, a parallel pruning frequent pattern tree algorithm based on MapReduce is proposed to solve the above problems. Based on the pruning frequent pattern tree algorithm, the algorithm uses the MapReduce programming model to parallelize each step of the pruning frequent pattern tree algorithm. Overall divided into four steps:

Frequency statistics of frequent 1-itemsets; use the frequency statistics of frequent 1-itemsets to create a frequent 1-itemset table, and group the data according to the frequent 1-itemset table, thus dividing the data into n parts; The decomposed data is used to mine association rules; the final frequent patterns are summarized, namely M1, M2, M3, M4.

The M1 stage uses a MapReduce task to perform frequency statistics of all itemsets. When a fragment is input, the Map function is first called to divide the item set into pair<key=num, String> line by line according to the records of the item set; then the String is divided according to the interval of the item set to form a pair<key, value= Ti>, where the key is a single item, and the value is the transaction where the item is located; then the Reduce (a function of the MapReduce mode) operation is performed on the result after the Map is decomposed, and the number of transactions where the key is located is found out, and the frequency Statistics; finally, the results of frequency statistics are screened according to the set minimum support, and the screened results are stored in the frequent 1-itemset table in order of the frequency of itemsets from high to low.

The M2 stage is to achieve the effect of load balancing and to ensure that each group is relatively independent, so that the subsequent processing is more convenient and the integrity of the mining results is ensured. The data should be balanced and grouped. In this step, first, group the transaction projection data in the F-list table, then create a group table, and finally store the grouped data in the table.

In the M3 stage, the data is divided into n groups according to the strategy of balanced grouping, so that when the data is input, one Map function corresponds to one group, and each group is mined separately. In this way, the effect of data decomposition can be achieved, and finally the Reduce function is used to summarize the results of Map processing. The operation of each map task is based on the grouping table generated during the process of balancing grouping. The established grouping table is a Hash structure, and each item is mapped to the transaction number of the item. Each Reduce task reduces the frequent patterns generated by the Map task.

The M4 stage is to summarize the final frequent patterns, that is, Reduce collects all the results for subsequent processing.

Referring to Fig. 4, it is a schematic structural diagram of a cloud computing platform provided by an embodiment of the present invention, including:

The system platform consists of three parts: Distributed file system service, in which the main control server (Namenode) is used to maintain and manage the entire file system, and the data server (Datanode) is used to store data blocks; MapReduce computing service, in which the task server (TaskTracker) is used to complete Map and Reduce tasks, while the job server (JobTracker) is mainly used to schedule task execution, handle machine failure (fault tolerance), TaskTracker communication, and monitor the execution of Job and Task; in addition, there are The submitter of a job (Job), that is, the client.

In the data association rule mining implementation method provided by the present invention, a pruning method is proposed, and a pruning frequent pattern tree algorithm is proposed to reduce the number of iterations of some branches. Then the present invention utilizes the MapReduce programming technology of cloud computing to parallelize each step of the pruning frequent pattern tree algorithm, which improves the data processing capability and efficiency of the pruning frequent pattern tree algorithm, and simultaneously enables the pruning frequent pattern tree algorithm to adapt to cloud computing environment. The data records to be processed are divided into blocks and distributed to different computing nodes for processing. Each computing node only processes a part of the data records, which solves the problem that the massive data cannot be read into the memory by a single machine for mining and processing; the data association provided by the present invention In the implementation method of rule mining, multiple computing nodes are used to participate in the statistical process of data items in parallel and then merge the statistical results, which effectively solves the problem that the existing technology cannot realize the mining of association rules for massive data and the problem of low processing efficiency. The invention not only optimizes the traditional FP-growth algorithm to improve the mining efficiency, but also proposes an improved parallel mining algorithm to solve the massive data mining problem. The invention can be used in the extraction of association rules of data mining; it is suitable for data processing in the fields of commerce, enterprises, government departments and scientific research; it is also applicable to various occasions that need to extract the association of data.

The above is only a preferred embodiment of the present invention, and is not intended to limit the present invention. Obviously, those skilled in the art can use the pruning frequent pattern tree algorithm in the present invention to optimize and perform parallel processing to apply the present invention , without departing from the spirit and scope of the present invention.

Claims (5)

1. data association rule mining implementation method, it is characterized in that, may further comprise the steps: (1) will be imported data and cut apart, and be distributed to a plurality of computing nodes, frequency by the parallel statistics of each computing node 1-item collection, according to the ordering of 1-item collection frequency, and deletion makes up frequent 1-item collection table less than the 1-item collection of given threshold value; (2) grouping sheet that frequent 1-item collection is divided into groups to set up according to frequent 1-item collection table so carries out data projection to frequent 1-item collection, and the data after the projection are stored in the grouping sheet; (3) by each computing node the data in the grouping sheet are added up, make up local frequent pattern tree (fp tree), then each subtree of frequent pattern tree (fp tree) is carried out the data association rule mining, if there is the prefix path set A in a collection i in frequent pattern tree (fp tree), B, and satisfy

, then the item collection i in the set B just can beta pruning, and and the set A merging; (4) each frequent mode subtree is carried out the data association rule mining, merge by each frequent mode subtree and excavate the frequent mode that obtains.

2. data association rule mining implementation method as claimed in claim 1 is characterized in that, described step (1) further comprises: data object is evenly divided by record, made every group of data comprise the data object of balance; In every group of data, add up the number of times that each collection occurs; The frequency that occurs according to the item collection sorts, and given threshold value is the counting of absolute support, and frequent 1-item collection table is the Hash table of a frequent 1-item collection of storage.

3. data association rule mining implementation method as claimed in claim 1, it is characterized in that, described step (2) further comprises: the data after the grouping are carried out the projection of source data, set up the Hash table data after the projection are stored, this table called after grouping sheet; According to the computing node number grouping sheet size is set, the grouping sheet size equals the function Map number that Parallel Programming Models MapReduce arranges.

4. data association rule mining implementation method as claimed in claim 2, it is characterized in that, each Hash data is carried out unidirectional Hash calculating acquisition by q data object in the Hash table, and each data object participates in t+1 Hash and calculates, and obtains the individual Hash data of q (t+1).

5. data association rule mining implementation method as claimed in claim 3 is characterized in that the data structure of grouping sheet is the Hash form, the item collection after the stores packets, and the row of a collection place data number; The row at record data place number goes the projection source data, and data are assigned in the corresponding group.

Images