CN118643444A - Big data anomaly detection method, device, equipment, storage medium and product - Google Patents

Abstract

The invention discloses a big data anomaly detection, a device, equipment, a storage medium and a computer program product, wherein the method is characterized in that an original isolated forest algorithm is improved, and a plurality of isolated trees are created according to business data to be processed; then, calculating the fitness value of each isolated tree in the plurality of isolated trees; and then, selecting a target isolated tree form among a plurality of isolated trees to form an isolated forest based on a tabu search algorithm by taking the fitness value of the isolated tree as a screening index, and finally, carrying out anomaly detection on service data to be processed according to the isolated forest to obtain an anomaly detection result. The adaptation value of the isolated tree is used as a screening index, the isolated tree with lower adaptation value and redundancy in the plurality of isolated trees is removed based on a tabu search algorithm, and a better target isolated tree is screened, so that the occupied space of the isolated forest is reduced, the calculation cost of anomaly detection is reduced, and the anomaly detection efficiency is improved.

Description

Big data anomaly detection method, device, equipment, storage medium and product

Technical Field

The present invention relates to the field of big data processing technology, and in particular to a big data anomaly detection method, device, equipment, storage medium and computer program product.

Background Art

In the production process of traditional enterprise business, data is mostly generated by manual reporting by staff. The correctness of the data in the source database cannot be guaranteed. There are often some abnormal data such as garbled characters, mismatched data units, and missing data. If the abnormal data is not eliminated during the data conversion process, it will not only increase the burden on the system, but also cause the collapse of the data conversion task for complex data conversion operations. There are currently two main existing technical solutions: distance-based methods such as the K-Means algorithm; density-based methods such as the local outlier factor LOF algorithm. Although the distance-based method K-Means algorithm has the characteristics of simplicity and efficiency, it also has the problem of being sensitive to noise and outliers. The density-based method local outlier factor LOF algorithm determines the abnormal data by calculating the outlier factor of each sample in the data set. Although it works well for medium and high-dimensional data sets, it needs to calculate the distance between each sample, and the calculation overhead is too high, so it is very ineffective for large data sets.

To address this problem, an isolation forest algorithm has been proposed. The original isolation forest algorithm works well in anomaly detection, but the detection accuracy is related to the number of isolated trees. For anomaly detection of large amounts of data, it is often necessary to build more isolated trees, which consumes a lot of memory space, has high computational overhead, and has low anomaly detection efficiency.

Summary of the invention

The main purpose of the present invention is to provide a big data anomaly detection method, device, equipment, storage medium and computer program product, aiming to solve the technical problems in the prior art that constructing a large number of isolated trees consumes a large amount of memory space, has a large computational overhead and has low anomaly detection efficiency.

To achieve the above object, the present invention provides a big data anomaly detection method, the method comprising:

Create multiple isolated trees based on the business data to be processed;

Calculating the fitness value of each of the plurality of isolated trees;

Using the fitness value of the isolated tree as a screening index, a target isolated tree is selected from the plurality of isolated trees based on a taboo search algorithm to form an isolated forest;

Anomaly detection is performed on the business data to be processed according to the isolation forest to obtain anomaly detection results.

Optionally, calculating the fitness value of each of the plurality of isolated trees includes:

Calculate the accuracy value of samples correctly classified by each of the multiple isolated trees, and calculate the difference between samples correctly detected by any two isolated trees among the multiple isolated trees;

The fitness value of each of the isolated trees is calculated according to the precision value and the difference.

Optionally, the calculating the fitness value of each of the isolated trees according to the precision value and the difference includes:

Calculating a sum of a product of the precision value and a first weight and a product of the difference and a second weight;

The reciprocal of the sum of the products is used as the fitness value of each of the isolated trees.

Optionally, calculating the accuracy value of correctly classified samples of each of the plurality of isolated trees includes:

The accuracy value of the correctly classified samples of each of the multiple isolated trees is calculated according to a statistical method.

Optionally, the calculating the difference between samples correctly detected by any two isolated trees among the plurality of isolated trees includes:

The difference between samples correctly detected by any two isolated trees among the plurality of isolated trees is calculated according to the cross-validation method.

Optionally, the step of using the fitness value of the isolated tree as a screening index and selecting a target isolated tree from the plurality of isolated trees based on a taboo search algorithm to form an isolated forest includes:

Selecting any isolated tree from the fitness values of the plurality of isolated trees as an initial solution;

Selecting a candidate set that meets a preset taboo requirement in the neighborhood of the initial solution, wherein the preset taboo requirement is that the fitness value of the isolated tree in the candidate set is greater than the fitness value of the isolated tree corresponding to the initial solution;

Update the taboo table according to the isolated tree with the largest fitness value selected from the candidate set;

Using the isolated tree with the largest fitness value as a solution, re-searching the candidate set and re-updating the taboo table based on the candidate set until a preset termination condition is met;

When the preset termination condition is reached, the isolated tree in the taboo table is used as the target isolated tree to form the isolated forest.

Optionally, performing anomaly detection on the to-be-processed business data according to the isolation forest to obtain anomaly detection results includes:

Calculate the expected value of the path length of each business data of the business data to be processed in the target isolated tree of the isolated forest, and calculate the average value of the path length of each business data of the business data to be processed in each of the target isolated trees;

Calculate the abnormal score of each of the business data in the target isolation tree according to the expected value and the average value;

An anomaly detection result is determined according to an anomaly score of each of the business data in the to-be-processed business data in the target isolated tree.

In addition, to achieve the above-mentioned purpose, the present invention also proposes a big data anomaly detection device, the big data anomaly detection device comprising:

An isolated tree construction module is used to create multiple isolated trees based on the business data to be processed;

A processing module, used for calculating the fitness value of each of the plurality of isolated trees;

A taboo search module, configured to use the fitness value of the isolated tree as a screening index and select a target isolated tree from the plurality of isolated trees based on a taboo search algorithm to form an isolated forest;

The anomaly detection module is also used to perform anomaly detection on the to-be-processed business data according to the isolation forest to obtain anomaly detection results.

In addition, to achieve the above-mentioned purpose, the present invention also proposes an electronic device, which includes: a memory, a processor, and a big data anomaly detection program stored in the memory and run on the processor, and the big data anomaly detection program is configured to implement the steps of the big data anomaly detection method described above.

In addition, to achieve the above-mentioned purpose, the present invention also proposes a storage medium, on which a big data anomaly detection program is stored, and when the big data anomaly detection program is executed by a processor, the steps of the big data anomaly detection method described above are implemented.

In addition, to achieve the above-mentioned purpose, the present invention also provides a computer program product, which includes a big data anomaly detection program, and when the big data anomaly detection program is executed by a processor, it implements the steps of the big data anomaly detection method described above.

The present invention provides a big data anomaly detection method, which improves the original isolation forest algorithm. First, multiple isolated trees are created according to the business data to be processed; then, the fitness value of each isolated tree in the multiple isolated trees is calculated; then, the fitness value of the isolated tree is used as a screening index, and a target isolated tree is selected from the multiple isolated trees based on a taboo search algorithm to form an isolated forest. Finally, anomaly detection is performed on the business data to be processed based on the isolated forest to obtain anomaly detection results. In this embodiment, the multiple isolated trees created by the business data to be processed are not directly used for anomaly detection, but the fitness value of the isolated tree is used as a screening index, and the isolated trees with lower fitness values and more redundant are removed from the multiple isolated trees based on the taboo search algorithm, and the more excellent target isolated trees are screened out, which not only reduces the space occupied by the isolated forest, but also reduces the calculation overhead of anomaly detection, and improves the efficiency of anomaly detection.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG1 is a schematic diagram of the structure of an electronic device in a hardware operating environment according to an embodiment of the present invention;

FIG2 is a schematic diagram of the relationship between anomaly scores and expected path lengths of samples in an isolated tree according to an embodiment of the present invention;

FIG3 is a schematic diagram of the structure of an isolated tree composed of samples ABCD involved in an embodiment of the present invention;

FIG4 is a schematic diagram of a process flow of a taboo search algorithm according to an embodiment of the present invention;

FIG5 is a schematic diagram of a process flow of a first embodiment of big data anomaly detection according to an embodiment of the present invention;

FIG6 is a flow chart of a first embodiment of big data anomaly detection according to an embodiment of the present invention;

FIG7 is a flow chart of a first embodiment of big data anomaly detection according to an embodiment of the present invention;

FIG8 is a flow chart of a third embodiment of big data anomaly detection according to an embodiment of the present invention;

FIG9 is a schematic diagram of the test time of the improved isolation forest anomaly detection algorithm and the original isolation forest anomaly detection algorithm involved in the embodiment of the present invention;

FIG. 10 is a structural block diagram of a first embodiment of a big data anomaly detection device according to an embodiment of the present invention.

The realization of the purpose, functional features and advantages of the present invention will be further explained in conjunction with embodiments and with reference to the accompanying drawings.

DETAILED DESCRIPTION

It should be understood that the specific embodiments described herein are only used to explain the present invention, and are not used to limit the present invention.

In the production process of traditional enterprise business, data is mostly generated by manual reporting by staff, and the correctness of the data in the source database cannot be guaranteed. There are often some abnormal data such as garbled characters, mismatched data units, missing data, etc. If the abnormal data is not eliminated during the data conversion process, it will not only increase the system burden, but also cause the data conversion task to crash for complex data conversion operations. There are currently two main existing technical solutions:

One is a distance-based method, which is based on the assumption that normal samples are always clustered, while abnormal samples are always isolated. That is, by calculating the distance between each sample and the surrounding samples, it is determined whether a point is abnormal.

A more representative algorithm is the K-Means algorithm. K-Means divides the data set into multiple clusters by calculating the Euclidean distance of samples, and samples far away from the cluster are identified as abnormal data.

The other is a density-based method, which is similar to the distance-based method. It calculates the anomaly score by calculating the density around the sample and the density around its neighboring points to achieve the purpose of detecting abnormal data. The DBSCAN algorithm (Density-Based Spatial Clustering of Applications with Noise) is a classic density-based anomaly detection algorithm. It groups data sets based on data density, and samples in low-density areas are outliers.

The distance-based method K-Means algorithm has the characteristics of simplicity and efficiency, and has been widely used, but it is also sensitive to noise and outliers. The density-based method Local Outlier Factor (LOF) algorithm determines abnormal data by calculating the outlier factor of each sample in the data set. The LOF algorithm works well for medium and high-dimensional data sets, but because it needs to calculate the distance between each sample, the computational overhead is too high, and it has poor effect on large data sets.

To solve this problem, an isolation forest algorithm was proposed. The original isolation forest algorithm works well in anomaly detection, but the detection accuracy is related to the number of isolated trees. For anomaly detection of large amounts of data, it is often necessary to build more isolated trees, which consumes a lot of memory space, has high computational overhead, and has low anomaly detection efficiency.

The present invention provides a big data anomaly detection method, which improves the original isolation forest algorithm. First, multiple isolated trees are created according to the business data to be processed; then, the fitness value of each isolated tree in the multiple isolated trees is calculated; then, the fitness value of the isolated tree is used as a screening index, and a target isolated tree is selected from the multiple isolated trees based on a taboo search algorithm to form an isolated forest. Finally, anomaly detection is performed on the business data to be processed based on the isolated forest to obtain anomaly detection results. In this embodiment, the multiple isolated trees created by the business data to be processed are not directly used for anomaly detection, but the fitness value of the isolated tree is used as a screening index, and the isolated trees with lower fitness values and more redundant are removed from the multiple isolated trees based on the taboo search algorithm, and the more excellent target isolated trees are screened out, which not only reduces the space occupied by the isolated forest, but also reduces the calculation overhead of anomaly detection, and improves the efficiency of anomaly detection.

Refer to FIG. 1 , which is a schematic diagram of the structure of an electronic device in a hardware operating environment according to an embodiment of the present invention.

As shown in FIG1 , the electronic device may include: a processor 1001, such as a central processing unit (CPU), a communication bus 1002, a user interface 1003, a network interface 1004, and a memory 1005. Among them, the communication bus 1002 is used to realize the connection and communication between these components. The user interface 1003 may include a display screen (Display), an input unit such as a keyboard (Keyboard), and the optional user interface 1003 may also include a standard wired interface and a wireless interface. The network interface 1004 may optionally include a standard wired interface and a wireless interface (such as a wireless fidelity (Wireless-Fidelity, WI-FI) interface). The memory 1005 may be a high-speed random access memory (Random Access Memory, RAM), or a stable non-volatile memory (Non-Volatile Memory, NVM), such as a disk storage. The memory 1005 may also be a storage device independent of the aforementioned processor 1001.

Those skilled in the art will appreciate that the structure shown in FIG. 1 does not limit the electronic device and may include more or fewer components than shown in the figure, or combine certain components, or arrange the components differently.

As shown in FIG. 1 , the memory 1005 as a storage medium may include an operating system, a network communication module, a user interface module, and a big data anomaly detection program.

In the electronic device shown in FIG1 , the network interface 1004 is mainly used for data communication with a network server; the user interface 1003 is mainly used for data interaction with a user; the processor 1001 and the memory 1005 in the electronic device of the present invention can be set in the electronic device, and the electronic device calls the big data anomaly detection program stored in the memory 1005 through the processor 1001, and executes the big data anomaly detection method provided in an embodiment of the present invention.

The present invention first describes a method for abnormality detection based on the original isolation forest.

In large data sets, abnormal data generally have two characteristics: 1) there is always a large deviation between the characteristic values of abnormal data and normal data; 2) the probability of abnormal data appearing in the data set is very low.

Using these two characteristics, the Isolation Forest Algorithm defines a binary search tree called an Isolation Tree, which recursively partitions the data set until all samples are isolated. Under this recursive partitioning strategy, abnormal data is closer to the root node of the tree, which means that fewer recursions are required to isolate abnormal data. The Isolation Forest Algorithm introduces the definitions of isolation trees, path lengths, and anomaly scores.

First, a brief introduction to the definition.

Definition 1 (Isolation Tree): Let N be a node in an isolation tree T. N can only exist in two states: no child node or two child nodes. If N has no child nodes, then N is called an external node of the isolation tree T; if N has two child nodes (Nl, Nr), then N is called an internal node of the isolation tree T. For a given data set X = {x1,...,xn} with n samples, randomly select feature q and split value p from the data set. For node N (N is a sample xi in the data set X), if N's feature value Nq<q, then N is placed in the left subtree, otherwise it is placed in the right subtree. Recursively split the data set X in this way until any of the following conditions are met: 1) the isolation tree reaches the limit height; 2) only the same samples remain on the node; 3) only one sample remains on the node.

Definition 2 (Path Length): The path length is the number of edges from the root node of the isolated tree T to the external node, denoted as h(x). For a given data set X = {x1,...,xn} with n samples, the average path length of the constructed isolated tree T is equivalent to the path length of failed queries in the binary search, and formula (1) is as follows:

C(n)＝2H(n-1)-2(n-1)/n (1)

Where H(i) is the harmonic function, H(i) = Ln(i) + γ, γ is the Euler constant, Ln(i) is Log2i; n is the number of samples in the data set; C(n) is the average value of the path length h(x) for a given n, which is used to standardize the path length h(x) of sample x.

Definition 3 (Anomaly Score): The anomaly score is used to determine whether a sample x is abnormal. By traversing each isolated tree in the isolation forest, calculating the path length of x in each tree, and then obtaining the anomaly score S(x,n) of x based on its path length, as shown in formula (2):

S( x , n ) = 2^-E(h(x))/C(n) (2)

Among them, E(h(x)) is the expected path length of sample x in the isolated tree T. The relationship between S(x,n) and E(h(x)) is shown in Figure 2. It can be seen from Figure 2 that: when E(h(x))→n-1, s approaches 0, and the sample is regarded as normal data; when E(h(x))→0, s approaches 1, that is, the abnormal score of the sample approaches 1, and it is regarded as abnormal data; when E(h(x))→C(n), s approaches 0.5, that is, the average path length of the sample is the same as the average path length of the isolated tree, and it is impossible to distinguish whether the sample is abnormal data.

It should be noted that the construction process of the isolation tree is essentially random. At each node, the algorithm randomly selects a feature and a split value to divide the data. Due to this randomness, the distribution of data points in the tree becomes relatively uniform. In addition, since the isolation tree is a binary tree, each node has at most two children, which also leads to a certain relationship between the expectation of the path length and the number of samples. The maximum depth of the isolation tree is usually defined as log2(n), where n is the number of samples. This means that as the number of samples increases, the height (or depth) of the tree will also increase. The path length of the sample point is directly related to the height of the tree, so the expectation of the path length will also increase with the increase in the number of samples.

The purpose of the isolation forest algorithm is to identify outliers by calculating the path length of sample points. Normal samples usually have longer path lengths in the isolation tree because they follow the overall distribution of the data, because they need to go through more segmentation to be isolated to the leaf nodes. Outliers, due to their differences from the overall distribution, are often isolated at a shallower level, so their path lengths are shorter.

In probability theory and statistics, the expected value is the probability-weighted average of all possible outcomes of a random variable. For a sample point in an isolated tree, the expected value of its path length is the weighted average of all possible path lengths, while the expected value of the path length of a normal sample is close to n-1 due to its distribution characteristics in the tree.

It should be noted that "close to n-1" here is an approximate description, and the actual expected value may be affected by many factors, such as the distribution characteristics of the data, the height of the tree, feature selection, etc. Therefore, in practical applications, the performance and accuracy of the isolation forest algorithm are usually evaluated through a large number of experiments and verifications.

Secondly, the process of anomaly detection using the isolation forest algorithm is explained.

The use of the isolation forest algorithm for anomaly detection mainly includes two stages: training and testing. The following briefly introduces the process of using the isolation forest algorithm for anomaly detection.

Training phase: build isolated trees based on subsamples of the dataset.

(1) For a data set X = {x1, ..., xn}, select ψ samples from X to form a subset M.

(2) Randomly select a feature q and a split point p from the d feature points, and use this split point to divide the samples into the left and right subtrees respectively.

(3) Iterate step (2) until the termination condition of the isolated tree in Definition 1 is met.

It should be noted that step (1) of selecting ψ samples from X to form a subset M can be repeated multiple times to generate a target number of isolated trees. For example, if the number of isolated trees to be generated is F, then it is necessary to select F samples from X to form F subsets. Each of the F subsets forms an isolated tree through the above steps (2) and (3). In this way, F isolated trees are obtained.

Testing phase: Anomaly scores are calculated for each sample using an isolation tree.

For each sample point xi in the data set, let it traverse each isolated tree, calculate the anomaly score of the sample point xi according to the anomaly score formula, and finally determine whether the sample point is an abnormal data according to the anomaly score of the sample point. As shown in Figure 3, it is a schematic diagram of the sample set (A, B, C, D) traversing an isolated tree. It can be seen that the sample point D is most likely to be an anomaly because it reaches the isolated state the earliest.

Specifically, for each sample point, the algorithm calculates the path length in each isolated tree. The path length refers to the number of edges from the root node to the leaf node containing the sample point. This length can be regarded as the number of splits, or the depth from the root node to the sample point.

Based on the path length of the sample point in each tree, the algorithm calculates its anomaly score. The anomaly score is usually calculated based on the average path length and some normalization factor. Specifically, for each sample x, its anomaly score s(x) may be calculated based on the average path length c(n) from the root node to x and the expected value E(h(x)) of the average path length for a given number of samples, see formula (2) above. The lower the anomaly score, the more likely the sample point is an outlier.

The anomalies are screened out based on the anomaly score and a predetermined threshold, which is usually determined based on the statistical characteristics of the training data. If the anomaly score of a sample point exceeds this threshold, it will be marked as an anomaly.

Since there are multiple isolated trees, each isolated tree may produce its own anomaly detection results. The final anomaly detection decision can be made by integrating the results of all isolated trees. For example, the anomaly scores of each tree can be averaged or voted to decide whether a sample point is an outlier.

Finally, the algorithm outputs the anomaly detection results for each sample point, including which sample points are considered outliers.

It should be noted that the parameters in the Isolation Forest algorithm (such as the number of isolated trees, the maximum depth of the tree, the sample sampling ratio, etc.) can be adjusted according to the specific application scenario and data to optimize the performance of anomaly detection. In addition, the Isolation Forest algorithm has a linear time complexity, so it is more efficient when processing large data sets.

In this application, the original isolation forest anomaly detection algorithm is improved, and a taboo search algorithm is introduced to remove low-precision and redundant isolated trees, so as to enhance the efficiency of anomaly detection.

Among them, the taboo search algorithm is a classic heuristic algorithm with powerful global search performance. The process of the taboo search algorithm is shown in Figure 4. The taboo search algorithm records some operations that have been experienced by setting a taboo table, and repeatedly executes the process of "moving the neighborhood → selecting candidate solutions → calculating fitness → judging whether it meets the contempt rule → updating the current solution", constantly iterating the current solution, and finally selecting the optimal solution.

In this case, the taboo search algorithm will be used to screen the original forest, obtain the better target isolated trees to form an isolation forest, reduce the algorithm calculation overhead, and improve the accuracy of anomaly detection of the isolation forest algorithm.

Referring to FIG. 5 , an embodiment of the present invention provides a method for detecting anomalies in big data. FIG. 5 is a flow chart of a first embodiment of the method for detecting anomalies in big data according to the present invention.

In this embodiment, the big data anomaly detection includes the following steps:

Step S101: Create multiple isolated trees according to the business data to be processed.

It should be noted that the execution subject of this embodiment can be a computing service device with data processing, network communication and program running functions, such as a desktop, tablet computer, personal computer, mobile phone, etc., or an electronic device capable of realizing the above functions, a cloud server, etc. The following takes an electronic device as an example to illustrate this embodiment and the following embodiments.

In this embodiment, the original isolation forest algorithm can be used to create multiple isolated trees for the service data to be processed. The process of constructing an isolated tree based on the original isolation forest algorithm is as follows:

(1) For the business data set to be processed X = {x1, ..., xn}, select ψ samples from X to form a subset M.

(2) Randomly select a feature q and a split point p from the d feature points, and use this split point to divide the samples into the left and right subtrees respectively.

(3) Iterate step (2) until the termination condition of the isolation tree is met. The termination conditions include: 1. The isolation tree reaches the limit height; 2. Only the same samples remain on the node; 3. Only one sample remains on the node.

Assume that there are N samples of business data to be processed, and the sample features are age or income, etc. If age or income is a feature, the specific value is the feature value. Randomly select and consider age>70 (split value q) as abnormal, and age<=70 (split value q) as normal. This is equivalent to drawing a hyperplane in the sample space. Next, select another sample feature as income, and consider income>1w as abnormal, and income<=1W as normal. At this time, another hyperplane is drawn in the sample space. It can be seen that points in sparsely distributed positions can be isolated through fewer hyperplane divisions, while points in densely distributed positions require more hyperplane divisions to be isolated.

It should be noted that the step (1) of selecting ψ samples from X to form a subset M can be repeated multiple times to generate the target number of isolated trees. For example, if the number of isolated trees to be generated is F, then it is necessary to select F samples from X to form F subsets. Each of the F subsets forms an isolated tree using the above (2) and (3). In this way, F isolated trees are obtained.

In this embodiment, the business data to be processed is divided into k parts (for example, k-fold cross validation), and for each fold, k-1 parts are used as training data to build multiple isolated trees, and then the remaining part is used as test data for anomaly detection.

Step S102: Calculate the fitness value of each of the plurality of isolated trees.

In this embodiment, the higher the fitness value, the greater the difference value and the better the accuracy of the isolated tree. By calculating the fitness value of each isolated tree, the isolated tree with a higher fitness value can be selected according to the size of the fitness value.

Step S103: using the fitness value of the isolated tree as a screening index, selecting a target isolated tree from the plurality of isolated trees based on a taboo search algorithm to form an isolated forest.

In this embodiment, the fitness value is not directly used to screen the isolated tree, but the fitness value of the isolated tree is used as a screening index to screen the target isolated tree based on the taboo search algorithm. This is because directly using the fitness value to screen the target isolated tree may cause the algorithm to fall into the local optimum. Using the fitness value of the isolated tree as a screening index to screen the isolated tree by the taboo search algorithm is a meta-heuristic method. It introduces a certain randomness and "jump out" mechanism in the search process by setting a taboo table and a contempt criterion, so that the algorithm can jump out of the local optimum and explore the solution space more comprehensively, thereby increasing the possibility of finding the global optimal solution or a solution close to the global optimal solution.

Step S104: performing anomaly detection on the to-be-processed business data according to the isolation forest to obtain anomaly detection results.

In this embodiment, multiple isolated trees created by the business data to be processed are not directly used for anomaly detection, nor is the fitness value used directly to screen the target isolated tree. Instead, the fitness value of the isolated tree is used as a screening indicator, and the taboo search algorithm is used to remove the isolated trees with lower fitness values and more redundant ones among the multiple isolated trees, and the better target isolated trees are screened out. This not only reduces the space occupied by the isolated forest, but also reduces the computational overhead of anomaly detection, thereby improving the efficiency of anomaly detection.

In some embodiments, the above step S102 includes step S1021 and step S1022.

Step S1021: Calculate the accuracy value of each of the multiple isolated trees for correctly classifying samples, and calculate the difference between any two of the multiple isolated trees for correctly detecting samples.

In this embodiment, a statistical method may be used to calculate the accuracy value of the correctly classified samples of each of the plurality of isolated trees.

Specifically, for each tree, the number of correctly classified samples (i.e., true positive examples TP and true negative examples TN) is calculated, and then the accuracy value is calculated using the following formula (3):

Accuracy＝(TP+TN)/(FP+FN+TP+TN) (3)

Among them, TP is a true positive example (anomaly samples correctly labeled as normal), TN is a true negative example (anomaly samples correctly labeled as abnormal), FP is a false positive example (normal samples incorrectly labeled as abnormal), and FN is a false negative example (anomaly samples incorrectly labeled as normal).

In this embodiment, a cross-validation method may be used to calculate the difference between samples correctly detected by any two isolated trees among the plurality of isolated trees.

Specifically, the difference between isolated trees Ti and Tj can be calculated using formula (4):

Qi,j = (Ki+Kj-2Kij)/(Ki+Kj ) (4)

Among them, Qi,j represents the difference between isolated trees Ti and Tj, Ki and Kj represent the number of correctly detected samples of isolated trees Ti and Tj respectively, and kij represents the number of overlapped correctly detected samples of isolated trees Ti and Tj.

It should be noted that the meaning of correctly detecting samples here can be understood as follows: for example, if the sample time is 9:30, then the result obtained after entering the sample into the isolation tree is before 10 o'clock, which means the detection result is correct, and if it is after 12 o'clock, the detection result is wrong. The large number of correctly detected duplicate samples indicates that the two isolation trees Ti and Tj are consistent in detecting certain specific abnormal samples.

Step S1022: Calculate the fitness value of each of the isolated trees according to the precision value and the difference.

Optionally, the fitness value of each isolated tree is calculated according to the precision value and the difference, including: calculating the sum of the product of the precision value and the first weight and the product of the difference and the second weight; and taking the inverse of the sum of the products as the fitness value of each isolated tree.

The calculation formula for calculating the fitness value of each isolated tree based on the difference and precision value of the isolated tree is shown in formula (5):

F(Ti) = 1/(uXi+rQij) (5)

Among them, F(Ti) represents the fitness value of the isolated tree Ti, Xi represents the precision value of the isolated tree Ti, Qi,j represents the difference between the isolated tree Ti and Tj, u represents the first weight of the precision value, and r represents the second weight of the difference.

The above embodiment provides a specific implementation method for calculating the fitness value.

In some embodiments, as shown in FIG. 6 , the above step S103 includes steps S1031 to S1035 .

Step S1031: Select any isolated tree from the fitness values of the plurality of isolated trees as an initial solution.

Step S1032: Select a candidate set that meets a preset taboo requirement in the neighborhood of the initial solution, where the preset taboo requirement is that the fitness value of the isolated tree in the candidate set is greater than the fitness value of the isolated tree corresponding to the initial solution.

In this embodiment, the neighborhood of the initial solution can be understood as isolated trees adjacent to the isolated tree.

Step S1033: Update the taboo table according to the isolated tree with the largest fitness value selected from the candidate set.

In this embodiment, the taboo table is initially empty, and is gradually updated according to the execution of step S1033, and isolated trees in the taboo table are no longer taken out for screening.

Step S1034: using the isolated tree with the largest fitness value as the solution to re-search the candidate set and re-update the taboo table based on the candidate set until a preset termination condition is met.

In this embodiment, the preset termination condition may be:

(1) Reaching the maximum number of iterations: The algorithm will preset a maximum number of iterations. When the number of iterations reaches this preset value, the algorithm will stop iterating. This is the most common termination condition, which ensures that the algorithm will not run indefinitely.

(2) Stagnation of solution quality improvement: If the quality of the solution does not improve significantly (i.e., the fitness value does not increase significantly) in a certain number of consecutive iterations, the algorithm may terminate. This means that the algorithm may have fallen into a local optimal solution and cannot find a better solution.

(3) Achieving the preset solution quality: If the algorithm finds a solution that meets the preset conditions (for example, reaching or exceeding a certain fitness value) during the iteration process, the algorithm may terminate early. This is usually applicable to problems with clear optimization goals.

(4) Computational resource limitations: Sometimes, the algorithm may need to terminate early due to computational resource limitations (such as memory, time, etc.). In this case, the algorithm may not be able to complete all the preset iterations, but will output a relatively good solution based on the current calculation results.

It should be noted that these termination conditions are not independent of each other, and one or more of them can be selected according to the needs of the specific problem. At the same time, the setting of the termination condition also needs to consider the performance and efficiency of the algorithm to avoid terminating the iteration too early or too late.

Step S1035: When the preset termination condition is reached, the isolated tree in the taboo table is used as the target isolated tree to form the isolated forest.

In this embodiment, the fitness value is not directly used to screen the isolated tree, but the fitness value of the isolated tree is used as a screening index to screen the target isolated tree based on the taboo search algorithm. This is because directly using the fitness value to screen the target isolated tree may cause the algorithm to fall into the local optimum. Using the fitness value of the isolated tree as a screening index to screen the isolated tree by the taboo search algorithm is a meta-heuristic method. It introduces a certain randomness and "jump out" mechanism in the search process by setting a taboo table and a contempt criterion, so that the algorithm can jump out of the local optimum and explore the solution space more comprehensively, thereby increasing the possibility of finding the global optimal solution or a solution close to the global optimal solution.

In some embodiments, as shown in FIG. 7 , the above step S104 includes steps S1041 to S1043 .

Step S1041: Calculate the expected value of the path length of each business data of the business data to be processed in the target isolated tree of the isolated forest, and calculate the average value of the path length of each business data of the business data to be processed in each of the target isolated trees.

Step S1042: Calculate the abnormal score of each business data in the target isolated tree according to the expected value and the average value.

Step S1043: determining an anomaly detection result according to an anomaly score of each of the business data in the to-be-processed business data in the target isolated tree.

In this embodiment, the expected value of the path length of each business data of the business data to be processed in the target isolated tree is calculated, and the average value of the path length of each business data of the business data to be processed in the target isolated tree is calculated; the anomaly score of each business data is calculated according to the expected value and the average value; the anomaly detection result is determined according to the anomaly score of each business data in the business data to be processed. For details, please refer to formula (2) and the above-mentioned method for obtaining anomaly detection results based on the original isolated forest. The method for obtaining anomaly detection results based on the new isolated forest in this embodiment is roughly the same as the method for obtaining anomaly detection results based on the original isolated forest, and will not be repeated in this embodiment.

The following takes the historical log data of the collection business system as an example of the business data to be processed to specifically illustrate the steps of the isolation forest anomaly detection algorithm based on the taboo search algorithm in this embodiment, as shown in FIG8 .

Step S201: Collect business system historical log data.

Step S202: Initialize and construct an original isolation forest based on the log data collected by the business system.

Step S203: extract a subset of a certain size from the log data set, and create an isolated tree until the conditions are met.

Step S204: Calculate the precision value of each isolated tree according to the cross-validation method and calculate the difference of each isolated tree according to the statistical method.

Step S205: Select any isolated tree from the fitness values of the plurality of isolated trees as an initial solution.

Step S206: Select a candidate set that meets a preset taboo requirement in the neighborhood of the initial solution, where the preset taboo requirement is that the fitness value of the isolated tree in the candidate set is greater than the fitness value of the isolated tree corresponding to the initial solution.

Step S207: Update the taboo table according to the isolated tree with the largest fitness value selected from the candidate set.

Step S208: using the isolated tree with the largest fitness value as the solution to re-search the candidate set and re-update the taboo table based on the candidate set until a preset termination condition is met.

Step S209: When the preset termination condition is reached, the isolated tree in the taboo table is used as the target isolated tree to form the isolated forest.

Step S210: Detect the data set according to the isolation forest, traverse and calculate the anomaly score, so as to obtain the abnormal log data set.

Among them, in the isolated forest algorithm, the detection ability of each isolated tree will change according to the training set data and parameters. Therefore, this case uses the cross-validation method to calculate the accuracy value of each isolated tree.

By analyzing and comparing the anomaly detection accuracy and execution time of the improved isolation forest algorithm and the original isolation forest algorithm, it can be proved that the improved isolation forest algorithm is more effective than the original isolation forest algorithm.

This proposal introduces the area under the ROC curve (AUC), a common indicator of anomaly detection, to measure the accuracy of abnormal data classification. The value of AUC is between 0.5 and 1. The closer the AUC is to 1, the higher the accuracy of the algorithm. The number of samples in the test data set is 256, and 100 isolated trees are constructed. The results are shown in Table 1 below.

Table 1:

It can be seen that the improved isolation forest algorithm has better anomaly detection accuracy than the original isolation forest. In terms of execution efficiency, the improved isolation forest algorithm and the original forest algorithm were used to execute 10 times on the 6 data sets in the above table. The results are shown in Figure 9 below. It can be seen that the improved isolation forest algorithm is significantly better than the original isolation forest algorithm in terms of execution time.

This case is based on the improved isolation forest anomaly detection algorithm, which not only effectively reduces the computational cost overhead, has linear complexity, good anti-noise effect, but also has a wide range of applications and high detection accuracy.

This proposal can be applied in the unified data management platform of the centralized construction management system. The specific scenario is that in the process of synchronizing data from various business systems to the planned construction system, the data platform needs to uniformly clean, verify, and audit the synchronized business data. In the process of processing, there are usually inaccurate business field data, garbled characters, or even missing data, which may lead to abnormal processing or even crash of the data management platform. By introducing the algorithm of this proposal, the accuracy and stability of abnormal data detection in the data management system are greatly improved. Therefore, this proposal has a high application value in the field of big data anomaly detection.

This proposal mainly solves the problem of dirty data faced by the system during implementation. Improve basic quality through detection, aggregation and cleaning of abnormal business data; standardize various types of data, unify internal and external calibers to provide full-link, cross-service, cross-system data exchange and analysis capabilities; establish and optimize data governance organizations and processes, gradually achieve data security and controllability, and enable data applications. The data anomaly detection method of this proposal greatly improves data quality.

In addition, an embodiment of the present invention further proposes a storage medium, on which a big data anomaly detection program is stored. When the big data anomaly detection program is executed by a processor, the steps of the big data anomaly detection method described above are implemented.

In addition, an embodiment of the present invention also proposes a computer program product, including a big data anomaly detection program, which implements the steps of the big data anomaly detection method as described above when executed by a processor.

The specific implementation methods of the computer program product of the present invention are basically the same as the embodiments of the above-mentioned big data anomaly detection method, and will not be repeated here.

Refer to Figure 10, which is a structural block diagram of the first embodiment of the big data anomaly detection device of the present invention.

As shown in FIG10 , the big data anomaly detection device proposed in the embodiment of the present invention includes: an isolated tree construction module 301, which is used to create multiple isolated trees according to the business data to be processed; a processing module 302, which is used to calculate the fitness value of each of the multiple isolated trees; a taboo search module 303, which is used to use the fitness value of the isolated tree as a screening index, and select the target isolated tree from the multiple isolated trees based on the taboo search algorithm to form an isolated forest; an anomaly detection module 304, which is also used to perform anomaly detection on the business data to be processed according to the isolated forest to obtain anomaly detection results.

The embodiments or specific implementation methods of the big data anomaly detection device of the present invention can refer to the above-mentioned method embodiments, which will not be repeated here.

It should be noted that, in this article, the terms "include", "comprises" or any other variations thereof are intended to cover non-exclusive inclusion, so that a process, method, article or system including a series of elements includes not only those elements, but also other elements not explicitly listed, or also includes elements inherent to such process, method, article or system. In the absence of further restrictions, an element defined by the sentence "comprises a ..." does not exclude the existence of other identical elements in the process, method, article or system including the element.

The serial numbers of the above embodiments of the present invention are only for description and do not represent the advantages or disadvantages of the embodiments.

Through the description of the above implementation methods, those skilled in the art can clearly understand that the above-mentioned embodiment methods can be implemented by means of software plus a necessary general hardware platform, and of course by hardware, but in many cases the former is a better implementation method. Based on such an understanding, the technical solution of the present invention, or the part that contributes to the prior art, can be embodied in the form of a software product, which is stored in a storage medium (such as a read-only memory/random access memory, a magnetic disk, or an optical disk), and includes a number of instructions for enabling a terminal device (which can be a mobile phone, a computer, a server, an air conditioner, or a network device, etc.) to execute the methods described in each embodiment of the present invention.

The above are only preferred embodiments of the present invention, and are not intended to limit the patent scope of the present invention. Any equivalent structure or equivalent process transformation made using the contents of the present invention specification and drawings, or directly or indirectly applied in other related technical fields, are also included in the patent protection scope of the present invention.

Claims (11)

1. A big data anomaly detection method, the method comprising:

Creating a plurality of isolated trees according to the service data to be processed;

Calculating the fitness value of each isolated tree in the plurality of isolated trees;

Selecting a target isolated tree form from the plurality of isolated trees to form an isolated forest based on a tabu search algorithm by taking the fitness value of the isolated tree as a screening index;

and carrying out anomaly detection on the business data to be processed according to the isolated forest to obtain an anomaly detection result.

2. The big data anomaly detection method of claim 1, wherein the calculating the fitness value of each of the plurality of orphan trees comprises:

calculating the precision value of a correct classification sample of each isolated tree in the plurality of isolated trees, and calculating the difference degree of a correct detection sample of any two isolated trees in the plurality of isolated trees;

and calculating the fitness value of each isolated tree according to the precision value and the difference.

3. The big data anomaly detection method according to claim 2, wherein the calculating the fitness value of each of the isolated trees from the precision value and the degree of difference comprises:

calculating the sum of the product of the precision value and the first weight and the product of the difference degree and the second weight;

and taking the inverse of the sum of the products as the fitness value of each isolated tree.

4. The big data anomaly detection method of claim 2, wherein said calculating an accuracy value of a correctly classified sample for each of said plurality of orphans comprises:

and calculating the precision value of the correct classification sample of each isolated tree in the plurality of isolated trees according to a statistical method.

5. The big data anomaly detection method according to claim 2, wherein the calculating the degree of difference of the correctly detected samples of any two of the plurality of isolated trees includes:

And calculating the difference degree of the correct detection samples of any two isolated trees in the plurality of isolated trees according to a cross validation method.

6. The big data anomaly detection method according to claim 1, wherein selecting a target isolated tree form among the plurality of isolated trees based on a tabu search algorithm to form an isolated forest by using the fitness value of the isolated tree as a screening index comprises:

selecting any isolated tree from the fitness values of the plurality of isolated trees as an initial solution;

Selecting a candidate set meeting preset tabu requirements from the neighborhood of the initial solution, wherein the preset tabu requirements are that the adaptability value of the isolated tree in the candidate set is larger than that of the isolated tree corresponding to the initial solution;

Selecting an isolated tree with the maximum fitness value according to the candidate set to update a tabu table;

Utilizing the isolated tree with the maximum fitness value as a solution to search for a candidate set again and updating a tabu table again based on the candidate set until a preset termination condition is met;

and under the condition that the preset termination condition is reached, forming the isolated forest by taking the isolated tree in the tabu table as the target isolated tree.

7. The big data anomaly detection method according to claim 1, wherein the anomaly detection of the service data to be processed according to the isolated forest, obtaining an anomaly detection result, includes:

Calculating expected values of path lengths of each service data of the service data to be processed in the target isolated tree of the isolated forest, and calculating average values of path lengths of each service data of the service data to be processed in each target isolated tree;

calculating the abnormal score of each business data in the target isolated tree according to the expected value and the average value;

And determining an abnormality detection result according to the abnormality score of each business data in the to-be-processed business data in the target isolated tree.

8. A big data abnormality detection device, characterized by comprising:

the isolated tree construction module is used for creating a plurality of isolated trees according to the business data to be processed;

the processing module is used for calculating the fitness value of each isolated tree in the plurality of isolated trees;

The tabu search module is used for selecting a target isolated tree form among the plurality of isolated trees to form an isolated forest based on a tabu search algorithm by taking the fitness value of the isolated tree as a screening index;

And the abnormality detection module is also used for carrying out abnormality detection on the business data to be processed according to the isolated forest to obtain an abnormality detection result.

9. An electronic device, the device comprising: a memory, a processor, and a big data abnormality detection program stored on the memory and executable on the processor, the big data abnormality detection program configured to implement the steps of the big data abnormality detection method according to any one of claims 1 to 7.

10. A storage medium having stored thereon a big data abnormality detection program which, when executed by a processor, implements the steps of the big data abnormality detection method according to any one of claims 1to 7.

11. A computer program product, characterized in that the computer program product comprises a big data anomaly detection program which, when executed by a processor, implements the steps of the big data anomaly detection method of any one of claims 1 to 7.