3.1 Apriori algorithm and association rules
Perform strong association rule analysis:
In the first part, the confidence level of each item set is obtained from the frequent item set found in the experiment, and the rule that meets the confidence level is not less than the minimum confidence level. The first step is a large I/O operation. Second, based on the frequent itemsets filtered in the previous step, create robust rules with high reliability, and then make judgments. In the whole association analysis process, the first part is the most important, so as to obtain the main calculation formula of Apriori:
$$\text{C}\text{o}\text{n}(\text{Y}\Rightarrow \text{Z})=\text{C}\text{%}=\frac{\sum _{\text{i}=1}^{\text{m}} \left\{(\text{Y}\Rightarrow \text{Z})\subseteq {\text{T}}_{\text{i}}\right\}}{\sum _{\text{i}=1}^{\text{m}} \left\{\text{Y}\subseteq {\text{T}}_{\text{i}}\right\}}\text{*}100\text{\%}$$
1
3.2 Apriori algorithm improvement method
Common methods to improve Apriori algorithm:
Reduce the frequency of database scanning. One is to convert the data into a Boolean array to reduce the number of database scans. The second is to scan the database once, extract key data values, and create a numerical array for further calculation. These two methods map the database data into an array, temporarily store it in the system cache, use the cached data for operations, and release the cache after each operation to improve efficiency.
Optimize the method of connecting intermediate itemsets. The traditional Apriori algorithm uses release, rebuild, or add and delete arrays when performing join operations on intermediate objects. In the calculation process, this connection method takes time, and constantly changing the matrix will consume a lot of resources. Therefore, some scientists have optimized the linking method through adjacency linked list, binary tree, multi tree and other methods to improve the computing efficiency.
Priority rule optimization algorithm. From the perspective of the basic rules of the optimization algorithm, some researchers put forward the idea of algorithm optimization, and introduced probability theory, weighting, analytic hierarchy process and other methods to strengthen inter layer filtering, so as to reduce the number of meaningless intermediate elements to a certain range to improve the efficiency of the algorithm.
The key of this algorithm is to improve the filtering of original meaningless data through multidimensional filtering. In the above algorithm steps, for the implementation strategy of initial meaningless data rule filtering, the basic matrix vector selection strategy of R3 filtering rules, the selection and implementation of parameters in data blocks, the decision strategy of middle set filtering strategy of low order and maximum item sets and other key strategies still need further analysis and research.
Assuming that the order of the original matrix I is mxn, the filtering rule R1 can only filter N columns of data, and the filtering rule R3 can filter M rows of data. Now we design two execution schemes for comparison. Scheme A executes filtering rule R1 first, and then R3. Scheme B executes filtering rule R3 first, and then R1. Then, the number of calculations required for each of the two schemes A and B is as follows.
Scheme A:
$$\text{C}\text{o}\text{u}\text{n}\text{t}\left(\text{A}\right)=\text{m}\text{*}\text{n}+\text{m}\text{*}(\text{n}-\text{N})+(\text{n}-\text{N})\text{*}(\text{m}\text{i}\text{n}\text{S}\text{u}\text{p}-1)$$
2
Scheme B:
$$\text{C}\text{o}\text{u}\text{n}\text{t}\left(\text{B}\right)=\text{m}\text{*}\text{n}+(\text{m}-\text{M})\text{*}\text{n}+\text{n}\text{*}(\text{m}\text{i}\text{n}\text{S}\text{u}\text{p}-1)$$
3
Therefore, the difference between the two schemes is:
$$\text{C}\text{o}\text{u}\text{n}\text{t}\left(\text{B}\right)-\text{C}\text{o}\text{u}\text{n}\text{t}\left(\text{A}\right)=\text{m}\text{*}\text{N}-\text{M}\text{*}\text{n}+\text{N}\text{*}(\text{ minSup }-1)\text{ }$$
4
Assuming that each element is scanned, the calculated value is represented by 1, and the total calculated value is represented by Ca, the truncation is not considered. The calculated value of x column vectors is:
$$\text{C}\text{a}\left(\text{x}\right)=\text{m}\text{*}\left({\text{C}}_{\text{x}}^{1}+{\text{C}}_{\text{x}}^{2}+\dots +{\text{C}}_{\text{x}}^{\text{x}}\right)=\text{m}\text{*}\left({2}^{\text{x}}-1\right)$$
5
Where, k represents the maximum number of constant elements in the element set, and Mk represents the number of column vectors after the matrix is compressed.
$$\text{O}(\text{n}\text{l}\text{o}\text{g}\text{n})=\text{O}\left({\text{M}}_{\text{k}}\text{l}\text{o}\text{g}{\text{M}}_{\text{k}}\right)+\text{O}\left({\text{N}}_{\text{k}}\text{l}\text{o}\text{g}{\text{N}}_{\text{k}}\right)$$
6
3.3 Data simulation analysis
Enter databases of different sizes. The number of data records ranges from 30 to 300. Run the same set of transaction data through two algorithm scripts. The running time (milliseconds) is shown in Fig. 1:
It can be seen that the improved algorithm is actually better and more efficient than the original algorithm in running time. With the increasing number of records in the dataset, the improvement effect is more obvious.
By viewing the Matlab simulation, create a Boolean random matrix I, with the order of m = n = 130, and set N to 2, 3, 4, 5... scanning times. The simulation results are shown in Fig. 2.
For Fig. 2, since there are many calculation results, the logarithm of the results is mapped to the figure. It can be seen that the higher the number of blocks, the less the number of element scans. It shows that data segmentation can effectively reduce the number of element scans and improve the overall efficiency of the algorithm.
In order to verify the correctness and effectiveness of the results of CBEF Apriori algorithm, the number of final constant elements generated by the three algorithms under different support constraints is compared in the experiment, as shown in Table 1. It can be seen that CBEF algorithm has different incremental scales and different minimum support thresholds. Under the constraint of minimum support threshold, the correct results can be obtained.
Table 1
Number of Frequent Option Sets in Different Increments and Supports
Incremental scale
|
Minimum Support
|
Apriori
|
CBE-Apriori
|
CBEF-Apriori
|
1125
|
0.6
|
155
|
155
|
155
|
1125
|
0.5
|
571
|
571
|
571
|
1125
|
0.4
|
2762
|
2762
|
2762
|
1125
|
0.3
|
5600
|
5600
|
5600
|
2125
|
0.6
|
155
|
155
|
155
|
2125
|
0.5
|
571
|
571
|
571
|
2125
|
0.4
|
2762
|
2762
|
2762
|
2125
|
0.3
|
5600
|
5600
|
5600
|