Incremental association rules update algorithm based on the sort compression matrix

Abstract

Association rule algorithm has always been a research hotspot in the field of data mining, in the context of today’s big data era, in order to efficiently obtain association rules and effectively update them, based on the original fast update pruning (FUP) algorithm, an association rule incremental update algorithm (FBSCM) based on sorting compression matrix is proposed to solve the shortcomings of frequent scanning of transaction datasets. Firstly, The algorithm maps the transaction dataset as a Boolean matrix, and changes the storage mode of the matrix(that is, adding two columns and a row vector); Secondly, the matrix is compressed many times during the generation of frequent k-itemset; After that, the items in the matrix are sorted incrementally according to the support degree of the itemset; Finally, the original string comparison operation is replaced by the vector product of each column of the matrix. Experimental results and analysis show that the FBSCM algorithm has higher temporal performance than the traditional FUP algorithm in different incremental dataset sizes, different minimum support thresholds and different feature datasets, especially when the incremental transaction volume is large or the minimum support degree is small.

Keywords

FUP algorithm boolean matrix matrix compression incremental association rule mining

1 Introduction

Data mining has significant applications in many fields [1 –5]. Among them, association rule mining, as one of widely used technologies of data mining [6], can find the relationship of interest from massive data [7] and mine meaningful association relationship [8]. However, with the passage of time, the existing association rule information will be invalid due to the change of influencing factors, so in the new state, it is necessary to use the existing mining results to perform corresponding addition and deletion operations, so as to quickly update the association rule base, and the association rule incremental update algorithm came into being. At present, the research methods of this algorithm are mainly divided into two categories. One is mining based on tree structure [9, 10], and the other is iterative-based mining algorithms [11, 12]. Among them, the FUP [Fast Update Pruning] algorithm proposed by Cheung et al. is one of the most classic and practical algorithms, but there are still shortcomings in multiple scans of transactional data sets and inability to process massive data.

To solve the shortcomings of multiple scan transactional datasets in the FUP algorithm, the researchers proposed corresponding improved algorithms. The simple and efficient incremental update algorithm proposed by Chen et al. SFUA can quickly update the association rules when the newly added database is relatively small [13]. Based on the distributed environment, the CMFUP algorithm proposed by Geng et al. [14] and the MRFUP algorithm proposed by Zhu et al. [15] have higher correlation rule mining efficiency in processing large data sets. In addition, some researchers have proposed improved methods based on Boolean matrices for mining frequent itemset. The key idea of such methods is to convert the transaction dataset into a 0-1 matrix, and replace the inefficient string comparison operation with the “AND operation”, which greatly shortens the calculation time of the support of frequent itemset, thereby improving the efficiency of algorithm operations. Liu et al. [16] proposed a new association rule algorithm, ABBM, which uses the Boolean vector “relational calculus” method to discover frequent itemset because all transaction data is stored in bits, so less memory space is required. Yu et al. [17] proposed an improved Apriori algorithm, which replaces the original transaction database with a Boolean matrix. This approach makes it easier to delete infrequent itemset by using the “AND operation” and random access characteristics of arrays. The algorithm can also be mined on the Hadoop platform, which exponentially improves the efficiency of the algorithm. From the aspects of matrix storage mode, matrix compression, and efficient calculation of support, a variety of improvement schemes [18, 19] are proposed, which effectively improves the efficiency of the algorithm. However, these algorithms are all proposed in the context of static databases, and there are not many ways to start from the matrix improvement for dynamic databases.

Zhou et al. [20] proposed a new association rule incremental algorithm (FBCM), based on the improvement idea of Boolean matrix. The algorithm operates on two compressed Boolean matrices to achieve efficient update of association rules. Related experiments show that the algorithm can greatly reduce the computational overhead and computation amount, effectively improve the update efficiency of association rules. However, the approach still requires multiple scans of the matrix and does not reduce the number of candidate sets.

Due to the classic incremental association rule mining algorithm in data mining technology, the FUP algorithm has the following two disadvantages, for example, although the use of the original association rule mining information can reduce the calculation of the transaction itemset part, it still needs to scan the transaction database frequently, which increases the amount of calculation; It takes a long time to use the string comparison function to complete the statistical itemset support. This paper aims to solve the above shortcomings by proposing an incremental association rule mining algorithm (FBSCM) based on sorted compression matrix. FBSCM further improves the mining efficiency of the algorithm by converting the Boolean matrix of the transactional data set, effectively compressing the rows and columns of the matrix, bitwise and arithmetic, and matrix sorting. Finally, the design experiment is used for comparative analysis, and the performance of the algorithm before and after the improvement in processing different incremental dataset sizes, different support thresholds and different data sets is compared.

2 Improved algorithm

2.1 Definitions and related properties

2.1.1 Definitions

Definition 1. The transaction dataset B contains n transactions B = (B₁, B₂, … , B_n) and m items I = (I₁, I₂, … , I_m), where the items contained in each transaction B_i are a subset of I. The transaction dataset B is mapped to the corresponding Boolean matrix M as follows:

Table 1
Transaction matrix transformation mode

TID Itemsets a b c d e

T1 a,c,e f:D ->M T1 1 0 1 0 1

T2 b → T2 0 1 0 0 0

T3 b,c T3 0 1 1 0 0

T4 a,c,d,e T4 1 0 1 1 1

TID	Itemsets		a	b	c	d	e
T1	a,c,e	f:D ->M	T1	1	0	1	0	1
T2	b	→	T2	0	1	0	0	0
T3	b,c		T3	0	1	1	0	0
T4	a,c,d,e		T4	1	0	1	1	1

where the row represents a transaction T_i = (d_i1d_i2d_i3 …… d_in), the column represents the item I_j = (d_1jd_2jd_3j …… d_mj), and we have

$d_{ij} = {\begin{matrix} 0, I_{j} \notin T_{i} \\ 1, I_{j} \in T_{i} \end{matrix} (i = 1, 2, \dots n, j = 1, 2, \dots, m)$ (1)

Definition 2. The number of support for the project I_i

$sup (i) = \sum_{k = 1}^{m} d_{ki} * ω_{k}$ (2)

Definition 3. In Boolean matrix M, if there is a frequent itemset {I_i, I_j}, the ith and jth column vectors in the Boolean matrix M are summed, and the number of 1 is the support degree of the frequent itemset.

$sup (i, j) = \sum_{k = 1}^{m} (d_{ki} \land d_{kj}) * ω_{k}$ (3)

2.1.2 Related properties

In the association rule mining algorithm based on matrix improvements, the compression strategy of the matrix depends on the following properties:

Property 1. Supersets of infrequent itemset are also infrequent and can be removed during iterations that generate frequent itemset later [21].

Property 2. In the kth iteration process of obtaining frequent itemset, if there is a row vector transaction number (that is, the number of 1) in the 0-1 matrix that is less than k, the row can be deleted.

Property 3. For a set of frequent k-itemset L_k, if the |L_k| < k + 1, then the frequent k-itemset is the maximum frequent itemset.

2.2 FBSCM algorithm

As brought up earlier, FUP as an iterative mining algorithm has a couple of disadvantages, such as multiple scanning of database and generation of a large number of invalid candidate sets. Our proposed FBSCM addresses these issues from three aspects:

(1) Storage of the matrix

FBSCM adds three vectors at the end of the generated Boolean matrix to reduce multiple scans of the matrix. Among them, the vector ω is used as the weight, representing the frequency of each transaction in the transaction dataset, and effectively compressing the non-unique transactions in the transaction dataset to ensure that each transaction information in the matrix is not repeated. The vector n is considered to count the number of candidates contained in each transaction. The vector m is used to count the size of the number of supports corresponding to each term.

(2) Matrix compression

Column compression is performed on the matrix. The sum of the rows in the matrix is recalculated, and the rows of the matrix are compressed. According to the properties 1 and 2, the frequency of infrequent itemset is reduced by continuous compression, so that the matrix can achieve maximum simplification, which can maximize the utilization of storage space and improve the operation efficiency of the algorithm.

(3) The orderliness of the itemset

In the Apriori algorithm, the more supportive the frequent 1-itemset and the self-connection to generate the more frequent 2-itemset has the higher probability of success. Drawing on the idea of itemset ordering in the Apriori algorithm, in the mining of incremental association rules, the columns of the merged matrix are arranged in increments according to the frequent 1-itemset support count m. And the subsequent connection operation will produce fewer candidate combinations (the number of candidate 2-itemset generated $C_{n}^{2}$ will not be affected by the sorting operation, but at this time, the order of occurrence of the children in each set has been different, and the impact of the sorting operation will appear in the candidate 3-itemset and after). Under the premise that the frequent itemset has integrity, it not only reduces the computational overhead, but also improves the efficiency of the algorithm.

Corollary 1. Statistically frequent 1-itemset in the itemset {I₁} , { I₂ } , …, { I_n } supports the number and arranges them in ascending order, which can produce a smaller candidate k-itemset (k> =3).

Proof. Set the minimum number of support thresholds to s, if count (item|item ∈ L_k ∝ L_k) ⩾ s, it means that item is a frequent k-itemset L_k one of the frequent (k + 1)-items generated by the connection, that is, item ∈ L_k+1. When L₁ ={{ I₁ } , { I₂ } , …, { I_n }} is incremented by the number of supports, {{ i₁ } , { i₂ } , …, { i_n }}, since the $\sup_count (I_{1}) ⩾ \sup_count (i_{1})$ , the number of transactions to which the itemset {i₁} belongs≤the number of transactions to which the itemset {I₁} belongs. Therefore, in the subsequent process of connecting the frequent k-itemset with itself to obtain the frequent (k + 1)-itemset, that is, P (| { i₁ } ∝ { i_j } | ⩾ s|j ∈ (1, n]) ⩽ P (| { I₁ } ∝ { I_j } | ⩾ s|j ∈ (1, n]), and so on for the remaining frequent 1-itemset. Therefore, the smaller the number of supports, the fewer frequent k-itemset connections result in fewer candidate k + 1 combinations. For the other 1-itemset in the L₁, because the number of supports is larger than the previous 1-itemset, and the itemset has already performed a connection operation with the previous 1-itemset, it will not produce too many candidate sets. Therefore, the overall resulting candidate k-itemset after sorting is small, and the proof is completed.

FBSCM consists of the following key steps. We assume that the original dataset is DB, and the new dataset is db. DB+db is the updated transaction dataset.

Step1 Generate frequent 1-itemset L₁ (DB + db) .

Scans dataset db for supported updates to all 1-itemset X belonging to L₁ (DB) in db support (X_DB∪db). X is checked once the scan is complete. If support (X_DB∪db) ⩾ minsup × (|DB + db|), it is added to the L₁ (DB + db). Count the number of supports support (X_db) for 1-itemset X in db that is not part of the L₁ (DB + db) and if support (X_db) ⩾ minsup × (|DB + db|) which is added to the L₁ (DB + db). At this point, L₁ (DB + db) is generated.

Where,

$support (X_{db}) = X . {count}_{db} / | db |$ (4)

$support (X_{DB \cup db}) = X . {count}_{DB \cup db} / | DB + db |$ (5)

Step2 Generate a sorted compression matrix

Column compression is performed on matrix matrix_DB and matrix_db according to L₁ (DB + db) and the property 1, respectively. The Boolean matrix of DB and db is then combined to generate a new matrix matrix_DB+db. The matrix is compressed accordingly according to the property 2. Each column m is updated, after which the columns of the matrix are sorted in ascending order supporting the number m.

Fig. 1

FBSCM algorithm flowchart.

Step3 Mine frequent itemset based on sorted compression matrix

Candidate 2-itemset is generated by frequently connecting 1-itemset to itself, where efficient calculation of the support of each candidate combination is performed by “AND operation” of each vector of the matrix. Items that do not meet the minimum support threshold set are removed from the candidate 2-itemset, resulting in a frequent 2-items set. Repeat this process until the frequent (k + 1)-itemset can no longer be obtained, at which point the algorithm finally wants to get the frequent k-itemset.

2.3 FBSCM case analysis

This section explains the flow of FBSCM by analyzing an example. Set the minimum support threshold s = 0.33. The number of transactions in the original transaction dataset DB is |DB|=6, as shown in Table 2. The number of entries is 5, and the minimum number of db supports is 2. The increased number of transactions in the transaction dataset db is |db|=3, as shown in Table 3, the number of entries is 4, and the minimum number of supported db is 1. The minimum number of supports for DB+db is 3. Set sup as the count for the supported numbers.

Table 2
The original transaction dataset DB

TID itemset

T1 A, B, C, E

T2 B, D

T3 B, C

T4 A, B, C, D

T5 A, C

T6 B, E

TID	itemset
T1	A, B, C, E
T2	B, D
T3	B, C
T4	A, B, C, D
T5	A, C
T6	B, E

Table 3

Add transaction dataset

TID	itemset
T1	A, C
T2	A, B, E
T3	A, B, C

Frequent itemsets on DB are:

$\begin{matrix} L 1 (DB) = {A : 3, B : 5, C : 4, D : 2, E : 2}, \\ L 2 (DB) = {AB : 2, AC : 3, BC : 3, BD : 2, BE : 2}, \\ L 3 (DB) = {ABC : 2} \end{matrix}$

2.3.1 Generate frequent 1-itemset

The first step of the algorithm is to map DB and db as corresponding Boolean matrices, as shown in Table 4 and Table 5.

Table 4
DB’s Boolean matrix

TID A B C D E ω n

T1 1 1 1 0 1 1 4

T2 0 1 0 1 0 1 2

T3 0 1 1 0 0 1 2

T4 1 1 1 1 0 1 4

T5 1 0 1 0 0 1 2

T6 0 1 0 0 1 1 2

m 3 5 4 2 2

TID	A	B	C	D	E	ω	n
T1	1	1	1	0	1	1	4
T2	0	1	0	1	0	1	2
T3	0	1	1	0	0	1	2
T4	1	1	1	1	0	1	4
T5	1	0	1	0	0	1	2
T6	0	1	0	0	1	1	2
m	3	5	4	2	2

Table 5

db ‘s Boolean matrix

TID	A	B	C	E	ω	n
T1	1	0	1	0	1	2
T2	1	1	0	1	1	3
T3	1	1	1	0	1	3
m	3	2	2	1

First, scan db to update the number of supports for all 1-itemset belonging to L₁ (DB), A . sup (DB + db) = 6, B . sup (DB + db) = 7, C . sup (DB + db) = 6, E . sup (DB + db) = 3, D . sup (DB + db) = 2 <3, so D is an infrequent 1-itemset, so L₁ (DB+ db) = { A, B, C, E }.

2.3.2 Generate a sorted compression matrix

According to L₁ (DB + db) and the property 1, the 1-itemset {D} in the DB Boolean matrix does not need to participate in subsequent iterations. It can be deleted by column compression of db’s Boolean matrix, recalculated the number of occurrences of “1” in each row of the matrix, and updated the values of the array n, w, m, while the Boolean matrix of db does not need to change. The compressed DB matrix is shown in Table 6.

Table 6
Boolean matrix after the first compression of DB

TID A B C E ω n

T1 1 1 1 1 1 4

T2 0 1 0 0 1 1

T3 0 1 1 0 1 2

T4 1 1 1 0 1 3

T5 1 0 1 0 1 2

T6 0 1 0 1 1 2

m 3 5 4 2

TID	A	B	C	E	ω	n
T1	1	1	1	1	1	4
T2	0	1	0	0	1	1
T3	0	1	1	0	1	2
T4	1	1	1	0	1	3
T5	1	0	1	0	1	2
T6	0	1	0	1	1	2
m	3	5	4	2

The Boolean matrix of DB and db is then combined to generate a new matrix. The merged matrix is row compressed according to the property 3, the item support number m of each column of the matrix is recalculated, and the columns of the matrix are sorted in ascending order according to the number of supports. The combined and sorted matrix is shown in Table 7.

Table 7

DB + db combined and sorted Boolean matrix

TID	E	A	B	C	ω	n
T1	1	1	1	1	1	4
T3	0	0	1	1	1	2
T4	0	1	1	1	2	3
T5	0	1	0	1	2	2
T6	1	0	1	0	1	2
T8	1	1	1	0	1	3
m	3	6	6	6

2.3.3 Frequent itemset mining based on sorted compression matrix

Before mining the frequent 2-itemset, it is necessary to compress the corresponding rows and columns of the matrix according to the properties 1 and 2. Similarly, in the iterative generation process of the frequent k-itemset afterwards, the matrix also needs to be compressed according to the compression strategy. Then use the sorted compression matrix to get the frequent 2-itemset, the frequent 1-itemset mined earlier is L₁ (DB+ db) = { E, A, B, C }, the candidate 2-itemset of DB+db is generated by the L₁ (DB + db) self-join, so the candidates are EA, EB, EC, AB, AC, BC.

Take E ∧ A = 100001, $support_count (E, A) = 1 \times 1 + 0 \times 1 + 0 \times 2 + 0 \times 2 + 0 \times 1 + 1 \times 1 = 2$ . The number of supports for itemset {E, A } = 2 is less than the minimum number of support (= 3), so it cannot be added to the collection of frequent 2-itemset. The other candidate 2-itemset are calculated, and the final frequent 2-itemset are: L₂ (DB+ db) = {{ EB } , { AB } , { AC } , { BC }}. Before mining the frequent 3-itemset, perform the corresponding row compression operation on the matrix according to nature 2. The compressed matrix is shown in Table 8.

Table 8
Compressed DB+db Boolean matrix

TID E A B C ω n

T1 1 1 1 1 1 4

T4 0 1 1 1 2 3

T8 1 1 1 0 1 3

m 3 6 6 6

TID	E	A	B	C	ω	n
T1	1	1	1	1	1	4
T4	0	1	1	1	2	3
T8	1	1	1	0	1	3
m	3	6	6	6

The Candidate 3-itemset for DB+db is generated by L₂ (DB + db) self-join, with only ABC candidates. Take A ∧ B ∧ C = 110, $support_count (A, B, C) = 1 \times 1 + 1 \times 2 + 0 \times 1 = 3$ . The number of supports for itemsets {A, B, C} equals to the minimum number of supports 3, so it is added to the collection of frequent 3-itemset. At this point, the frequent 3-itemset ends up being: L₃ (DB+ db) = {{ ABC }}. There is only one frequent 3-itemset, and according to the property 3, it is impossible to produce a frequent 4-itemset, so the algorithm ends.

Eventually, the frequent itemset is obtained as L (DB+ db) = {{ E } , { A } , { B } , { C } , { E } , { EB } , { AB } , { AC } , { BC } , { ABC }}.

3 Performance analysis and experimental results

3.1 Performance analysis

The parameters used for the time complexity analysis of the FBSCM algorithm and the FUP algorithm are shown in the following Table 9:

Table 9
Parameter list

Parameters Parameter description Parameters Parameter description

T Average transaction length R Total transactions for DB and db

K Maximum number of frequent items I Total number of items for DB and db

T_FBSCM Total time complexity of the FBSCM algorithm I_k D_k number of columns after compression

T_FUP Total time complexity of the FUP algorithm R_k D_k number of rows after compression

L _k frequent k-itemset

Parameters	Parameter description	Parameters	Parameter description
T	Average transaction length	R	Total transactions for DB and db
K	Maximum number of frequent items	I	Total number of items for DB and db
T_FBSCM	Total time complexity of the FBSCM algorithm	I_k	D_k number of columns after compression
T_FUP	Total time complexity of the FUP algorithm	R_k	D_k number of rows after compression
L _k	frequent k-itemset

The complexity of the time required to scan the original transactional database DB and the incremental transactional database db into a Boolean matrix is O (T × R); By adding two columns and a row array to the Boolean matrix to change the storage mode of the matrix, the space complexity consumed is O ((R + 1) × (I + 2)): For the compressed and merged matrix column vectors to support ascending order by itemset, a fast sort algorithm is adopted, and the time complexity consumed is O (I_k log I_k); In the subsequent mining of frequent 1-itemset, only affected by the compressed matrix, a Boolean matrix D₁ will be generated, and the time complexity consumed is O (R₁ × I₁); When k ⩾ 2, the time complexity required to generate candidate k-itemset C_k is O (|L_k-1|²), the final acquired frequent k-itemset depends on the Boolean matrix size and C_k, so the required complexity is O (|C_k| × I_k) + O (|L_k-1| × I_k-1). Therefore, the total time complexity of the FBSCM algorithm is:

$\begin{matrix} T_{FBSCM} = O (T \times R) + O (R_{1} \times I_{1}) \\ + \sum_{k = 2}^{K} [O ({| L_{k - 1} |}^{2}) + O (| C_{k} | \times I_{k}) \\ + O (| L_{k - 1} | \times I_{k - 1}) + O (I_{k} log I_{k})] \end{matrix}$ (6)

The time complexity analysis of the traditional FUP algorithm is as follows: firstly, the time complexity consumed to obtain frequent 1-itemset is O (T × R); when 2 ⩽ k ⩽ K, the time complexity required to generate candidate k-itemset C_k is O (|L_k-1|²); The process of generating frequent k-itemset has operations such as calculating the number of itemset support and pruning, and the time complexity needs O (|C_k| × R) and O (|C_k| × k × (k - 2)), respectively. Therefore, the total time complexity required by the traditional FUP algorithm is:

$\begin{matrix} T_{FUP} = O (T \times R) + \sum_{k = 2}^{K} \\ [O ({| L_{k - 1} |}^{2}) + O (| C_{k} | \times R) + O (| C_{k} | \times k \times (k - 2))] \end{matrix}$ (7)

Poor results for these two algorithms: $\begin{matrix} \begin{matrix} T_{FUP} - T_{FBSCM} = O (T \times R) + \sum_{k = 2}^{K} [O ({| L_{k - 1} |}^{2}) \\ + O (| C_{k} | \times R) + O (| C_{k} | \times k \times (k - 2))] - \end{matrix} \end{matrix}$

Fig. 2

Partial Groceries dataset presentation.

$\begin{matrix} {O (T \times R) + O (R_{1} \times I_{1}) + \sum_{k = 2}^{K} [O ({| L_{k - 1} |}^{2}) + \\ O (| C_{k} | \times I_{k}) + O (| L_{k - 1} | \times I_{k - 1}) + O (I_{k} log I_{k})]} \\ = \sum_{k = 2}^{K} [O (| C_{k} | \times R) + O (| C_{k} | \times k \times (k - 2)) \\ - O (| C_{k} | \times I_{k}) - O (| L_{k - 1} | \times I_{k - 1}) \\ - O (I_{k} log I_{k})] - O (R_{1} \times I_{1}) \end{matrix}$ (8)

From the above analysis, it can be seen that the values of both I_k and R_k are less than R, therefore,

$O (| C_{k} | \times R) - O (| C_{k} | \times I_{k}) - O (I_{k} log I_{k}) > 0$ (9)

|C_k| is the number of candidate k-itemset, generated by frequent (k-1)-itemset L_k-1, therefore, |L_k-1| is less than |C_k|, available:

$O (| C_{k} | \times k \times (k - 2)) - O (| L_{k - 1} | \times I_{k - 1}) > 0$ (10)

In summary, T_FUP - T_FBSCM > 0. The time complexity of the FBSCM algorithm is theoretically superior to that of the FUP algorithm.

3.2 Environment and Dataset

The experimental environment of this paper is carried out on a PC with Win10 64-bit system, 8 G memory, 4 G graphics card, and i5-8250U CPU @ 1.60 GHz.

In this experiment, four datasets are selected according to the density of data samples and the size of transaction volume, and the experimental data sets are shown in Table 10:

Table 10
Experimental dataset table

Dataset Transaction data volume (bar) Dataset characteristics

Groceries 9836 Small and sparse

mushroom 8124 Small and dense

T40I10D100K 100000 Quantity and dense

T10I4D100K 100000 Quantity and sparse

Dataset	Transaction data volume (bar)	Dataset characteristics
Groceries	9836	Small and sparse
mushroom	8124	Small and dense
T40I10D100K	100000	Quantity and dense
T10I4D100K	100000	Quantity and sparse

Among them, the Groceries dataset (shown in Fig. 2) is composed of the transaction list of department stores, the Mushroom dataset (shown in Fig. 3) comes from the UCI machine learning library, and the T40I10D100K dataset (shown in Fig. 4) and the T10I4D100K dataset (shown in Fig. 5) are the datasets used by Cheung et al. when proposing the FUP algorithm.

Fig. 3

Partial Mushroom dataset presentation.

Fig. 4

Partial T40I10D100K dataset presentation.

Fig. 5

Partial T10I4D100K dataset presentation.

3.3 Experimental design

For the association rule mining algorithm, experimental comparison is normally carried out from the three aspects of setting transaction datasets of different sizes, setting different minimum support thresholds, and setting transaction datasets with different characteristics. Therefore, in this paper, the single-variable method will be selected for experimental comparison:

First, take the incremental data amount as a single variable, and compare the changes of each algorithm under the same dataset.

Second, the support threshold is used as a single variable to compare the changes of each algorithm under the same dataset. Finally, the effect of the support threshold on the efficiency of the algorithm is obtained.

Third, the data characteristics of the dataset are used as a single variable, and the changes of each algorithm under the same transaction data volume size and minimum support threshold are compared.

In this experiment, we can finally obtain the influence of incremental transaction data size, minimum support threshold, and data characteristics of the dataset on the efficiency of the algorithm.

3.4 Experimental results and analysis

3.4.1 Algorithm comparison under different incremental datasets

The original transaction dataset DB will randomly select 4500 records from the data-intensive much-related Mushroom dataset, while the incremental dataset db will randomly select 500–3500 records (step size is 500) from the remaining data. Given the minimum support min_sup = 0.4, the running time of FUP, FBCM and FBSCM under different incremental dataset sizes is compared, as shown in Fig. 6:

Fig. 6

Comparison under different volumes of dataset.

The charts in Fig. 6 are a simulated implementation of the matrix-based incremental algorithm proposed in Refs. 20, under different incremental dataset data volumes. The abscissa represents the incremental transaction data volume, taking 500 as the step size, changing to 3500. As can be seen from the Fig. 6, while keeping the min_sup = 0.4 unchanged, as the amount of data in the new transaction dataset continues to increase, the workload of scanning the transaction dataset increases greatly, and the running time also increases. In terms of the speed of mining frequent itemset, FUP is the slowest, and FBSCM has the highest execution efficiency and the slowest time increase. Obviously, FBSCM has the highest execution efficiency due to the use of sorted compression matrix to mine frequent patterns. Moreover, FBSCM effectively narrows the search scope of understanding and avoids the generation of invalid candidate sets on the basis of making frequent itemset complete, which not only reduces the computational overhead, but also accelerates the mining speed of frequent itemset. After the frequent 1-itemset is obtained, the compressed matrix is sorted in ascending order according to the order of the itemset, which avoids the generation of invalid candidate sets. And in the process of mining k-itemset, the support of the itemset is efficiently counted through “AND operation”, which further increases the efficiency of the algorithm.

3.4.2 Experimental comparison at different minimum support

We use the data-intensive Mushroom dataset for this experiment. The original transaction dataset DB will randomly extract 6000 records from the Mushroom, the incremental dataset db will randomly extract 2000 data from the remaining data. The experiment takes different minimum support thresholds as the abscissa, and compares the running time of the algorithm in different minimum support min_sup cases. The results are shown in Fig. 7.

Fig. 7

Comparison with different minimum support.

The abscissa in Fig. 7 represents the minimum degree of support, taking 0.02 as the step size, increasing from 0.25 to 0.41, and the ordinate represents the change in the running time of each algorithm, which is in milliseconds. As can be seen from the Fig. 7, when the support threshold changes to 0.41, the running time of FBSCM is 32.4 ms, which is 1.6 times faster than the run time of FUP 51.9 ms. The running time of FBCM based on matrix-based improvements is 43.3 ms. When the support threshold is 0.41, because the transaction dataset is updated after the frequent itemset will not be much, FUP can reduce the number of scans of the original transaction dataset, and the running time is not be very high. For FBCM based on matrix improvement and FBSCM, at this point, even if there is not a lot of frequent itemset generation, it is still necessary to map the transaction dataset to a Boolean matrix, the time consumed by this step is not reduced. As a result, FBSCM improvement does not open a significant gap with FUP. When the support threshold is at 0.25, the running time of FBSCM is 77 ms, which is nearly 10 times faster than the running time of FUP (765.5 ms). Given the same amount of data in the dataset, the time taken by FBSCM is always at the lowest level of the three algorithms, and the processing time of the three algorithms is gradually decreasing with the increase of support. This experiment shows that FBSCM has a significant advantage in the case of frequent itemset mining with small threshold (that is, large computational volume).

3.4.3 Experimental comparison under different datasets

Given the incremental transaction dataset size |db|=1000, and the minimum support threshold min_sup, the operating efficiency of FUP, FBCM and FBSCM under the dataset Mushroom and Groceries is compared, and the experimental results are shown in Fig. 8.

Fig. 8

Comparison between algorithm under different feature dataset.

Figure 8 shows the operation efficiency comparison chart of FUP, FBCM and FBSCM algorithms under the small and dense Mushroom dataset, the small and sparse Groceries dataset, the large and dense T40I10D100K dataset and the large and sparse T10I4D100K dataset, respectively, and the incremental data sets were obtained by sampling 1000 pieces in the original dataset. The detailed experimental data corresponding to the experimental results are shown in Table 11.

Table 11

Detailed experimental data

Datasets		Mushroom	Groceries	T10I4D100K	T40I10D100K
Transaction data volume		8124	9836	100000	100000
min_support		0.33	0.02	0.05	0.3
FUP runtime(s)		14.5	4.74	27.48	40.58
FBCM runtime(s)		5.31	1.23	11.64	30.88
FBSCM runtime(s)		4.18	1.01	10.3	28.32
Efficiency ratio	(FUP/FBSCM)	3.47	2.67	1.43	4.69
	(FBCM/FBSCM)	1.27	1.13	1.09	1.22

From the efficiency ratio of Table 11 (FUP/FBSCM) and (FBCM/FBSCM), it can be seen that the data relationship, whether dense or sparse or transaction volume, regardless of size, does not have much impact on the operation efficiency of FBSCM, because the mining rate of FBSCM under the above four datasets is about 3 to 5 times higher than that of FUP. Compared with FBCM with the same matrix improvement idea, the improvement by FBSCM is about 1-2 times, and the optimization situation is more ideal, thanks to the use of sorted compression matrix. The large amount of overhead generated by FUP scanning the entire transaction dataset multiple times during the mining process has become the performance bottleneck of the algorithm, which makes the efficiency of the algorithm not well improved.

4 Conclusion

In this paper, an improved algorithm based on the sorted compression matrix, FBSCM is proposed. Compared with FUP that needs multiple scans for transaction dataset and generates invalid candidate sets, FBSCM scans the transaction data only once by mapping the transaction dataset to a Boolean matrix and effectively avoids the generation of invalid candidate sets by sorting the Boolean matrix. Through performance analysis and experimental results, the results show that FBSCM gives better performance in terms of runtime performance, especially if the minimum support threshold is low or the incremental transaction volume is large. In the future we will investigate new approaches to improve the memory consumption performance.

References

Usman

and Usman

, Multi-Level Mining and Visualization of Informative Association Rules [J], Information Science & Engineering 32(4) (2016).

Gladju

, Kamalam

B.S.

and Kanagaraj

, Applications of data mining and machine learning framework in aquaculture and fisheries: A review [J], Smart Agricultural Technology 2022 (2022), 100061.

Chen

, Wang

, Li

, et al., Principal association mining: an efficient classification approach [J], Knowledge-Based Systems 67 (2014), 16–25.

Kumara

B.T.

, Paik

, Siriweera

, et al., Cluster-based web service recommendation; proceedings of the 2016 IEEE international conference on services computing (SCC), F, 2016 [C], IEEE.

Rashid

M.M.

, Gondal

and Kamruzzaman

, Dependable large scale behavioral patterns mining from sensor data using Hadoop platform [J], Information Sciences 379 (2017), 128–145.

and Luo

, Risk prediction and early warning for air traffic controllers’ unsafe acts using association rule mining and random forest [J], Safety Science 135 (2021), 105125.

Ratner

, Statistical and machine-learning data mining:: Techniques for better predictive modeling and analysis of big data [M], CRC Press, 2017.

Chen

, Zhao

, Duan

, et al., Verifiable privacy-preserving association rule mining using distributed decryption mechanism on the cloud [J], Expert Systems with Applications 201 (2022), 117086.

Cheung

and Zaiane

O.R.

, Incremental mining of frequent patterns without candidate generation or support constraint; proceedings of the Seventh International Database Engineering and Applications Symposium, 2003 Proceedings, F, 2003 [C], IEEE.

10.

Leung

C.-S.

, Khan

Q.I.

and Hoque

, CanTree: a tree structure for efficient incremental mining of frequent patterns; proceedings of the Fifth IEEE International Conference on Data Mining (ICDM’05), F, 2005 [C], IEEE.

11.

Cheung

D.W.

, Han

, Ng

V.T.

, et al., Maintenance of discovered association rules in large databases: An incremental updating technique; proceedings of the Proceedings of the twelfth international conference on data engineering, F, 1996 [C], IEEE.

12.

Cheung

D.W.

, Lee

S.D.

and Kao

, A general incremental technique for maintaining discovered association rules [M], Database Systems For Advanced Applications’ 97, World Scientific 1997:185–194.

13.

CHEN Jin-Song and SHI Xiao-Ying , An incremental updating algorithm for mining association rules [J], Computer Engineering (07) (2002), 106–107.

14.

GENG Zhi-qiang , ZHANG Yang and HAN Yong-Ming , Matrix-based association rule incremental updating and its improved algorithm [J], Journal of Beijing University of Chemical Technology (Natural Science Edition) 43(05) (2016), 89–94.

15.

ZHU Xiao-feng , LI Ling-juan , XU Xiao-long , et al., MapReduce based association rule incremental updating algorithm [J], Computer Technology and Development 22(04) (2012), 115–118+122.

16.

Liu

and Wang

, An association rule mining algorithm based on a Boolean matrix [J], Data Science Journal 6 (2007), S559–S565.

17.

, Wen

, Wang

, et al., An improved Apriori algorithm based on the Boolean matrix and Hadoop [J], Procedia Engineering 15 (2011), 1827–1831.

18.

CAO Song-yang , LIU Lei , Wang Ya-gang , Apriori Improved Algorithm Based on Transaction Weights and Boolean Matrix, Software Guide 17(12) (2018), 65–68.

19.

ZHOU Kai , GU Hong-bo , LI Ai-guo , An Improved Algorithm for Mining Apriori Algorithm Based on Association Rules, Journal of Shaanxi University of Technology (Natural Science Edition) 34(05) (2018), 40–44.

20.

Zhou

, Ouyang

, Kuang

, et al., Incremental association rule mining based on matrix compression for edge computing [J], IEEE Access 7 (2019), 173044–173053.

21.

CHENG Chang-pin , WU Yi-lin , JIANG Yong-sheng , Association Rule Mining of Apriori Improved Algorithm Based on Matrix, Journal of Guangdong Second Normal University 39(05) (2019), 89–97.

22.

Rene

V.-O.J.

, M-F

C.A.

, Esteban V-B

, et al., Monitoring of local deformations and reservoir water level for a gravity type dam based on GPS observations [J], Advances in Space Research 69(1) (2022).

TID	A	B	C	D	E	ω	n
T1	1	1	1	0	1	1	4
T2	0	1	0	1	0	1	2
T3	0	1	1	0	0	1	2
T4	1	1	1	1	0	1	4
T5	1	0	1	0	0	1	2
T6	0	1	0	0	1	1	2
m	3	5	4	2	2

TID	A	B	C	E	ω	n
T1	1	1	1	1	1	4
T2	0	1	0	0	1	1
T3	0	1	1	0	1	2
T4	1	1	1	0	1	3
T5	1	0	1	0	1	2
T6	0	1	0	1	1	2
m	3	5	4	2

TID	E	A	B	C	ω	n
T1	1	1	1	1	1	4
T3	0	0	1	1	1	2
T4	0	1	1	1	2	3
T5	0	1	0	1	2	2
T6	1	0	1	0	1	2
T8	1	1	1	0	1	3
m	3	6	6	6

TID	A	B	C	D	E	ω	n
T1	1	1	1	0	1	1	4
T2	0	1	0	1	0	1	2
T3	0	1	1	0	0	1	2
T4	1	1	1	1	0	1	4
T5	1	0	1	0	0	1	2
T6	0	1	0	0	1	1	2
m	3	5	4	2	2

TID	A	B	C	E	ω	n
T1	1	1	1	1	1	4
T2	0	1	0	0	1	1
T3	0	1	1	0	1	2
T4	1	1	1	0	1	3
T5	1	0	1	0	1	2
T6	0	1	0	1	1	2
m	3	5	4	2

TID	E	A	B	C	ω	n
T1	1	1	1	1	1	4
T3	0	0	1	1	1	2
T4	0	1	1	1	2	3
T5	0	1	0	1	2	2
T6	1	0	1	0	1	2
T8	1	1	1	0	1	3
m	3	6	6	6

Incremental association rules update algorithm based on the sort compression matrix

Abstract

Keywords

1 Introduction

2 Improved algorithm

2.1 Definitions and related properties

2.1.1 Definitions

Table 1 Transaction matrix transformation mode TID Itemsets a b c d e T1 a,c,e f:D ->M T1 1 0 1 0 1 T2 b → T2 0 1 0 0 0 T3 b,c T3 0 1 1 0 0 T4 a,c,d,e T4 1 0 1 1 1

2.2 FBSCM algorithm

Table 2 The original transaction dataset DB TID itemset T1 A, B, C, E T2 B, D T3 B, C T4 A, B, C, D T5 A, C T6 B, E

Table 4 DB’s Boolean matrix TID A B C D E ω n T1 1 1 1 0 1 1 4 T2 0 1 0 1 0 1 2 T3 0 1 1 0 0 1 2 T4 1 1 1 1 0 1 4 T5 1 0 1 0 0 1 2 T6 0 1 0 0 1 1 2 m 3 5 4 2 2

Table 6 Boolean matrix after the first compression of DB TID A B C E ω n T1 1 1 1 1 1 4 T2 0 1 0 0 1 1 T3 0 1 1 0 1 2 T4 1 1 1 0 1 3 T5 1 0 1 0 1 2 T6 0 1 0 1 1 2 m 3 5 4 2

Table 8 Compressed DB+db Boolean matrix TID E A B C ω n T1 1 1 1 1 1 4 T4 0 1 1 1 2 3 T8 1 1 1 0 1 3 m 3 6 6 6

3.1 Performance analysis

Table 10 Experimental dataset table Dataset Transaction data volume (bar) Dataset characteristics Groceries 9836 Small and sparse mushroom 8124 Small and dense T40I10D100K 100000 Quantity and dense T10I4D100K 100000 Quantity and sparse

3.4 Experimental results and analysis

3.4.1 Algorithm comparison under different incremental datasets

References

Table 1
Transaction matrix transformation mode

TID Itemsets a b c d e

T1 a,c,e f:D ->M T1 1 0 1 0 1

T2 b → T2 0 1 0 0 0

T3 b,c T3 0 1 1 0 0

T4 a,c,d,e T4 1 0 1 1 1

Table 2
The original transaction dataset DB

TID itemset

T1 A, B, C, E

T2 B, D

T3 B, C

T4 A, B, C, D

T5 A, C

T6 B, E

Table 4
DB’s Boolean matrix

TID A B C D E ω n

T1 1 1 1 0 1 1 4

T2 0 1 0 1 0 1 2

T3 0 1 1 0 0 1 2

T4 1 1 1 1 0 1 4

T5 1 0 1 0 0 1 2

T6 0 1 0 0 1 1 2

m 3 5 4 2 2

Table 6
Boolean matrix after the first compression of DB

TID A B C E ω n

T1 1 1 1 1 1 4

T2 0 1 0 0 1 1

T3 0 1 1 0 1 2

T4 1 1 1 0 1 3

T5 1 0 1 0 1 2

T6 0 1 0 1 1 2

m 3 5 4 2

Table 8
Compressed DB+db Boolean matrix

TID E A B C ω n

T1 1 1 1 1 1 4

T4 0 1 1 1 2 3

T8 1 1 1 0 1 3

m 3 6 6 6

Table 10
Experimental dataset table

Dataset Transaction data volume (bar) Dataset characteristics

Groceries 9836 Small and sparse

mushroom 8124 Small and dense

T40I10D100K 100000 Quantity and dense

T10I4D100K 100000 Quantity and sparse

TID	A	B	C	D	E	ω	n
T1	1	1	1	0	1	1	4
T2	0	1	0	1	0	1	2
T3	0	1	1	0	0	1	2
T4	1	1	1	1	0	1	4
T5	1	0	1	0	0	1	2
T6	0	1	0	0	1	1	2
m	3	5	4	2	2

TID	A	B	C	E	ω	n
T1	1	1	1	1	1	4
T2	0	1	0	0	1	1
T3	0	1	1	0	1	2
T4	1	1	1	0	1	3
T5	1	0	1	0	1	2
T6	0	1	0	1	1	2
m	3	5	4	2

TID	E	A	B	C	ω	n
T1	1	1	1	1	1	4
T3	0	0	1	1	1	2
T4	0	1	1	1	2	3
T5	0	1	0	1	2	2
T6	1	0	1	0	1	2
T8	1	1	1	0	1	3
m	3	6	6	6