CN107609105B - Construction method of big data acceleration structure - Google Patents

Abstract

The invention relates to a construction method of a big data acceleration structure, which comprises the following steps: A. preprocessing data to form a data set conforming to an operation process; B. clustering, calculating the similarity between records in the category, and enabling the most similar records in the group to have the minimum spatial distance according to the grouping result of a clustering algorithm; C. establishing a mapping relation among the transaction attributes, the transaction attribute weights and the transaction records according to the three-level index, and circularly performing the process until all data are mapped; D. initializing a compression index structure, a transaction attribute weight index and a transaction attribute, determining the range of the shared attribute weight of the continuous records, traversing the inverted index mapping structure, and compressing the continuous records under the shared transaction attribute weight through a stroke compression algorithm. The method can quickly establish an acceleration structure of big data association analysis, and remarkably accelerates the processing speed and the data loading speed of the model.

Description

Construction method of big data acceleration structure

technical field

The invention relates to a method for data acceleration processing, in particular to a construction method of a big data acceleration structure.

Background technique

Big data technology has become the most effective and common technology for processing massive data. As one of the most representative scenarios in big data processing scenarios, police big data has attracted more and more attention. In the process of massive data analysis, the processing speed and processing performance of the general big data platform is one of the urgent problems to be solved. In the big data analysis scenario, especially in the police big data, the most common analysis method is the correlation analysis. The comprehensive correlation analysis of the relevant factors involved in the analysis object can effectively improve the accuracy of the police analysis. The commonly used big data correlation analysis The algorithm model is the association analysis algorithm model, and the association analysis algorithm is further divided into the traditional association analysis algorithm and the association analysis algorithm based on evolution theory. The difficulty of interaction lies in the generation of candidate sets, while evolutionary association analysis algorithm uses evolutionary algorithm to generate rules, and there is no generation process of frequent itemsets. At this stage, the big data processing system uses different algorithm models for different correlation analysis services. The main way to solve the processing speed of this type of model is the algorithm parallelization method for the business platform, but this method can only be used for a single algorithm and The specified platform works, and the algorithm is limited and the effect is not ideal. At present, the more commonly used parallelization method is the algorithm parallel method for Hadoop platform and Spark platform. The main idea of this kind of method is to divide the overall data set according to the specific parallelization framework of the platform, so that the divided data set is evenly distributed in the In the cluster, the association rule algorithm model is used to process the local data set, and the results of each node are collected through the collection function, so as to complete the parallel operation of the algorithm under this framework. The defect of this method is very obvious, that is, its improvement for a specific platform cannot have better performance on other platforms, and especially in the complex platform of police affairs, its correlation analysis algorithm model is diverse, and some algorithms are not very good. Being suitable for such parallelized operations increases the limitations of this approach.

SUMMARY OF THE INVENTION

The invention provides a construction method of a big data acceleration structure, so as to improve the speed and accuracy of data processing when analyzing the associated big data.

The construction method of the big data acceleration structure of the present invention includes:

A. Data preprocessing: perform data cleaning, data integration and data conversion on the original data to form a data set that conforms to the operation process;

B. Clustering processing: Clustering the preprocessed data, calculating the similarity between the records within the category through Hamming distance after the clustering is completed, and reordering the records, according to the grouping results of the clustering algorithm, Calculate the similarity of records in each group, so that the most similar records in the group have the smallest spatial distance;

C. Inverted index mapping structure: initialize the index file, attribute weight index item and attribute index item, extract the attributes of the sorted data and the attribute weight list, and then construct an inverted index structure, which combines transaction attributes, transaction attribute weights and The transaction record establishes the mapping relationship according to the three-level index, and this process is repeated until all data mapping is completed; the "transaction" refers to an atomic operation in data processing, and its nature is similar to the transaction in the database;

The normal process of index building is to build the index according to the number or row number of the data record. The index access sequence is index->record number->attribute->weight. This method is called forward indexing. The inverted index means that the index is not established according to the row number of the data record, but is established according to the attribute and weight of the record. The record number is the weight, and its access order is index->attribute->weight->record The index structure whose access order is opposite to that of the forward index is called an inverted index.

D. Stroke compression: Initialize the compression index structure, transaction attribute weight index and transaction attribute, determine the range of shared attribute weights of continuous records, traverse the inverted index mapping structure, and pass the continuous records under the shared transaction attribute weights through the stroke compression algorithm to compress. Stroke compression algorithm, namely RLE algorithm, its principle is to replace the adjacent elements with the same value in the data record line with a starting position and two adjacent weight values, for example: aaabccccccddeee, can use 3a1b6c2d3e instead, use RLE Compression methods can compress data very efficiently. There are many specific stroke compression methods derived from the RLE principle.

Further, the data cleaning described in step A includes deleting original data, filling in missing values and smoothing/filtering noise data.

Specifically, deletion of missing data or filling in missing values is determined by the attribute weight coverage p of the original data, where the attribute weight coverage p is:

where A is the data attribute, ε is the attribute weight, indicating the importance of the attribute, and ε ₁ +ε ₂ +...+ε _k =1, α indicates whether the attribute value is missing, α∈{0,1}, set the threshold ω, the value range of the threshold ω is (0,1), if p≥ω, fill in the missing value for the missing data, otherwise, delete the original data;

The mean filtering method is used to smooth/filter the noise data. This method selects a template for the current data to be processed, which is a number of adjacent records, and uses the template mean value to replace the original record value, which is expressed as:

Where k represents the number of attributes, g() represents the mean, M represents the number of adjacent data with the current data, s represents the neighbor set of the current data, and f represents a piece of data in s.

Specifically, the method for filling in the missing values is as follows: measure the data in the known complete original data by Euclidean distance, query the complete data that is most similar to the missing value, and perform the missing value according to the relevant field weight of the complete data. Replenish.

Further, in the data integration described in step A, the data in the multiple data sets are combined into a unified database, and redundant attributes are filtered through data cross-matching of each data set and multi-data set fusion.

Further, the data conversion described in step A includes constructing the attributes of the data set after data integration, reducing the attribute dimension of the data set, and performing integrity checking and supplementation on the data set after the reduction of the dimension. Reducing the attribute dimension of the data set can reduce the occupation of memory or hard disk. If there is insufficient memory or memory overflow during calculation, it is necessary to use PCA (Principal Component Analysis) to obtain data of low-dimensional attributes; secondly, data dimensionality reduction can To speed up machine learning, in many cases, it may be necessary to view data attributes, but high-dimensional (multiple) attributes cannot be observed. At this time, the attributes of the data can be reduced to 2D or 3D, that is, the attribute dimension of the data can be reduced. Count down to 2 or 3 so that you can visualize the data.

Specifically, the reducing the attribute dimension of the dataset includes:

Transform the data set into a matrix form and normalize the attributes. The normalization operation includes: making all attributes have similar scales, avoiding the large difference in attribute scales affecting the effect of dimensionality reduction, and then performing zero mean normalization operation;

Calculate the covariance matrix of the attributes of the data set, and then calculate the eigenvalues and eigenvectors of the covariance matrix through the algorithm of singular value decomposition;

The dimensionality reduction matrix is obtained through the dimensionality reduction calculation, and the dataset is mapped to the low-dimensional space through the dimensionality reduction matrix.

Specifically, the clustering process described in step B includes:

B1. Set the value range of the number of clusters K [K1, K2], K1 and K2 are the number of classifications, and assign the number of clusters K as the lower limit K1 of the value range;

B2. Randomly select K cluster centers;

B3. For a class, assign it to the nearest cluster center by distance calculation;

B4. Recalculate the new cluster center;

B5. Divide each obtained class into two subclasses by the binary division method, and compare the BIC scores of each pair of parent classes and subclasses; BIC is the Bayesian Information Criterion (BIC), which is carried out by BIC. Automatically determine the number of categories of clusters, assuming that there is a dataset D and some models M _j for selection, and different models M _j correspond to different K values. The BIC calculation formula is:

where R is the total number of data points in the data set D, l _j (D) represents the log-likelihood function of the data for the jth model, and takes the maximum likelihood function value, and p _j is the parameter in the model M _j quantity. The principle is to use the posterior decision probability to judge the effect of clustering results.

B6. Calculate the pair of parent class and child class with the largest difference in BIC score;

B7. Save the parent class subclass of step B6, and other remaining parent classes remain unchanged, so that the number of clusters K=K+1;

B8. Go to step B2, calculate the category situation under the new situation;

B9. If the K value reaches the upper limit value K2 or the results of two consecutive cycles are the same, it means that there is no cluster center that needs a split operation (ie step B5), and the cycle ends;

B10. Simultaneously calculate the Hamming distance between records for multiple cluster categories, and reorder the data within the group.

The construction method of the big data acceleration structure of the present invention can quickly establish the acceleration structure of the big data association analysis, and overcome the limitations of the existing methods and platform limitations, whether it is a traditional association analysis algorithm or an association analysis algorithm based on evolution theory , the acceleration structure can significantly speed up the processing speed and data loading speed of the model, and the construction process of the acceleration structure is simple, which is suitable for various large-scale data scenarios including police data.

The above content of the present invention will be further described in detail below with reference to the specific implementation of the embodiments. However, this should not be construed as limiting the scope of the above-mentioned subject matter of the present invention to the following examples. Without departing from the above-mentioned technical idea of the present invention, various substitutions or changes made according to common technical knowledge in the art and conventional means should all be included in the scope of the present invention.

Description of drawings

FIG. 1 is a flowchart of a method for constructing a big data acceleration structure according to the present invention.

Detailed ways

As shown in Figure 1, the construction method of the big data acceleration structure of the present invention includes:

A. Data preprocessing: Data cleaning, data integration and data conversion are performed on the original data to form a data set that conforms to the operation process.

The data cleaning described therein includes deleting raw data, filling in missing values, and smoothing/filtering noisy data.

In the process of deleting the original data and filling in the missing values, the missing data is judged by the attribute weight coverage p of the original data, and the attribute weight coverage p is:

where A is the data attribute, ε is the attribute weight, indicating the importance of the attribute, and ε ₁ +ε ₂ +...+ε _k =1, α indicates whether the attribute value is missing, α∈{0,1}, set the threshold ω, the value range of the threshold ω is (0,1), if p≥ω, fill in the missing value for the missing data, otherwise, delete the original data;

The mean filtering method is used to smooth/filter the noise data. This method selects a template for the current data to be processed, which is a number of adjacent records, and uses the template mean value to replace the original record value, which is expressed as:

Where k represents the number of attributes, g() represents the mean, M represents the number of adjacent data with the current data, s represents the neighbor set of the current data, and f represents a piece of data in s.

The method for filling in missing values is: measure the data in the known complete original data by Euclidean distance, query the complete data that is most similar to the missing value, and supplement the missing value according to the relevant field weights of the complete data.

In the data integration, data in multiple data sets are combined into a unified database, and redundant attributes are filtered through data cross-matching of each data set and multi-data set fusion.

The data transformation includes constructing the attributes of the data set after data integration, reducing the attribute dimension of the data set, and performing integrity checking and supplementation on the data set after the reduction of the dimension. The reducing the attribute dimension of the dataset includes:

Transform the data set into a matrix form and normalize the attributes. The normalization operation includes: making all attributes have similar scales, avoiding the large difference in attribute scales affecting the effect of dimensionality reduction, and then performing zero mean normalization operation;

Calculate the covariance matrix of the attributes of the data set, and then calculate the eigenvalues and eigenvectors of the covariance matrix through the algorithm of singular value decomposition;

The dimensionality reduction matrix is obtained through the dimensionality reduction calculation, and the dataset is mapped to the low-dimensional space through the dimensionality reduction matrix.

B. Clustering processing: Clustering the preprocessed data, calculating the similarity between the records within the category through Hamming distance after the clustering is completed, and reordering the records, according to the grouping results of the clustering algorithm, The similarity of records is calculated in each group, so that the most similar records in the group have the smallest spatial distance. Specifically include:

B1. Set the value range [K1, K2] of the number of clusters K, where K1 and K2 are the number of classifications, and assign the number of clusters K as the lower limit K1 of the value range. The values of K1 and K2 are determined by attributes of specific business data.

B2. Randomly select K cluster centers.

B3. For a class, assign it to the nearest cluster center by distance calculation.

B4. Recalculate new cluster centers.

B5. Divide each obtained class into two subclasses by the binary division method, and compare the BIC scores of each pair of parent class and subclass. BIC is the Bayesian Information Criterion (BIC), and the number of categories of clusters is automatically determined by BIC. Assuming that there is a dataset D and some models M _j for selection, different models M _j correspond to different K value. The BIC calculation formula is:

where R is the total number of data points in the data set D, l _j (D) represents the log-likelihood function of the data for the jth model, and takes the maximum likelihood function value, and p _j is the parameter in the model M _j quantity. The principle is to use the posterior decision probability to judge the effect of clustering results.

B6. Calculate the pair of parent and child classes with the largest difference in BIC scores.

B7. Save the parent class subclass in step B6, and other remaining parent classes remain unchanged, so that the number of clusters K=K+1.

B8. Go to step B2 to calculate the class case for the new case.

B9. If the K value reaches the upper limit value K2 or the results of two consecutive cycles are the same, it means that there is no cluster center that needs a split operation (ie, step B5), and the cycle ends.

B10. Simultaneously calculate the Hamming distance between records for multiple cluster categories, and reorder the data within the group.

C. Inverted index mapping structure: initialize the index file, attribute weight index item and attribute index item, extract the attributes of the sorted data and the attribute weight list. Then construct an inverted index structure, and establish a mapping relationship between transaction attributes, transaction attribute weights, and transaction records according to the three-level index. This process is repeated until all data mapping is completed, and a three-level inverted index structure is constructed.

D. Stroke compression: Initialize the compression index structure, transaction attribute weight index and transaction attribute, determine the range of shared attribute weights of continuous records, traverse the inverted index mapping structure, and pass the continuous records under the shared transaction attribute weights through the stroke compression algorithm to compress. Stroke compression algorithm, namely RLE algorithm, its principle is to replace the adjacent elements with the same value in the data record line with a starting position and two adjacent weight values, for example: aaabccccccddeee, can use 3a1b6c2d3e instead, use RLE Compression methods can compress data very efficiently. There are many specific stroke compression methods derived from the RLE principle. In this embodiment, the PCX run-length compression method is adopted: this method is a conversion method from a bitmap format to a compressed format. In this method, for the byte Ch that appears once in a row, if Ch>0xc0, add 0xc1 before the byte when compressing, otherwise, output Ch directly. For the byte Ch that appears N times in a row, it is compressed to 0xc0+N. Because Ch is two bytes, the maximum N can only be ff-c0=3fh (63 in decimal). When N is greater than 63, it needs to be compressed several times.

Claims (8)

1. The method for constructing the big data acceleration structure is characterized by comprising the following steps:

A. Data preprocessing: performing data cleaning, data integration and data conversion on the original data to form a data set conforming to the operation process;

B. Clustering treatment: clustering the preprocessed data, calculating the similarity among the records in the category through the Hamming distance after the clustering is finished, reordering the records, and calculating the record similarity in each group according to the grouping result of the clustering algorithm so as to minimize the spatial distance of the most similar record in the group;

C. The mapping structure of the inverted index: initializing an index file, an attribute weight index item and an attribute index item, extracting attributes of the sorted data and an attribute weight list, then constructing an inverted index structure, establishing a mapping relation among the transaction attributes, the transaction attribute weights and the transaction records according to a three-level index, and circularly performing the process until all data are mapped;

D. Stroke compression: initializing a compression index structure, a transaction attribute weight index and a transaction attribute, determining the range of the shared attribute weight of the continuous records, traversing the inverted index mapping structure, and compressing the continuous records under the shared transaction attribute weight through a stroke compression algorithm.

2. The big data acceleration structure construction method according to claim 1, characterized by: the data cleaning described in step a includes deleting the original data, filling in missing values, and smoothing/filtering the noise data.

3. The big data acceleration structure construction method according to claim 2, characterized in that: deleting missing data or filling missing values in the missing data is judged according to the attribute weight coverage rate p of the original data, wherein the attribute weight coverage rate p is as follows:

Wherein A is data attribute, is attribute weight, represents importance degree of attribute, and ₁+₂+...+_kif p is larger than or equal to omega, filling missing values in the missing data, otherwise, deleting the original data;

Smoothing/filtering the noise data employs mean filtering, represented as:

Where k represents the number of attributes, g () represents the mean, M is the number of data neighbors to the current data, s represents the neighbor set of the current data, and f represents one of the data in s.

4. The big data acceleration structure construction method according to claim 2, characterized in that: the method for filling in the missing value comprises the following steps: and measuring the data in the known complete original data through Euclidean distance, inquiring the complete data most similar to the missing value, and supplementing the missing value according to the weight of the relevant field of the complete data.

5. The big data acceleration structure construction method according to claim 1, characterized by: and B, combining the data in the data sets into a unified database in the data integration in the step A, and filtering redundant attributes through data cross matching and multi-data-set fusion of each data set.

6. The big data acceleration structure construction method according to claim 1, characterized by: the data conversion in the step A comprises the steps of carrying out attribute construction on the data set after data integration, reducing attribute dimensionality of the data set and carrying out integrity check and supplement on the data set after dimensionality reduction.

7. The big data acceleration structure construction method according to claim 6, characterized in that: the reducing the dataset attribute dimension comprises:

Transforming the data set into a matrix form and normalizing the attributes;

Calculating a covariance matrix of the data set attribute, and calculating an eigenvalue and an eigenvector of the covariance matrix through a singular value decomposition algorithm;

And obtaining a dimension reduction matrix through dimension reduction calculation, and mapping the data set to a low-dimensional space through the dimension reduction matrix.

8. The big data acceleration structure construction method according to claim 1, characterized by: the clustering process in the step B comprises the following steps:

B1. Setting the value range [ K1, K2], K1 and K2 of the cluster number K as the classification number, and assigning the cluster number K as the lower limit K1 of the value range;

B2. Randomly selecting K clustering centers;

B3. For a class, assigning it to the nearest cluster center by distance calculation;

B4. Recalculating a new cluster center;

B5. Dividing each obtained class into two subclasses by a dichotomy method, and comparing the BIC scores of each pair of the father class and the subclasses;

B6. Calculating to obtain a pair of parent class and subclass with the largest difference of BIC scores;

B7. Saving the parent subclass in the step B6, and keeping other remaining parent subclasses unchanged, so that the clustering number K is K + 1;

B8. Turning to step B2, calculating the category condition in the new case;

B9. If the K value reaches the upper limit value K2 or the results of two continuous circulation are the same, indicating that no clustering center needs to be split, and ending the circulation;

B10. And simultaneously calculating Hamming distances among the records for a plurality of cluster categories, and reordering the data in the group.

Images