# A New Fast Algorithm for Library Circulation Data Mining Based on FUP

Authors: Cunge Han; Wensen Yu; Xiaofei Li; Hai Lin; Huanyun Zhao
Journal: Scientific Programming
 (2022)

---

## Abstract

As the first incremental association mining algorithm, FUP can well solve the problem, but the algorithm also has the deficiencies to produce a large set of candidates and multiple iterating the database, leading to the algorithm’s low execution efficiency when dealing with some large transactions with fast updates, such as book circulation data. This study proposes an improved FUP algorithm that takes transaction identifier (TID) in the database to scan the database only once, making the computation significantly less than the FUP algorithm. Through detecting the circulation data of a university library, the experimental results show that compared with the standard FUP algorithm and SFUA algorithm, with the increase of borrowing and record transactions, the improved FUP algorithm has significantly improved the operation efficiency, which can help the library to do a good job in book recommendation scientifically.


---

## Body

## 1. Introduction

Association mining is a main study direction of data mining. In the research of association mining algorithm, AIS [1], SETM [2], Apriori [3], DHP [4], and other algorithms have appeared successively. The above association mining algorithms that can only mine association rules from static databases [5] belong to static data mining algorithms. However, the actual situation is that it is often necessary to add a batch of new transactions to the original database transaction, or readjust the support degree and confidence threshold. In this case, a method needed to realize the updating problem of association mining. Rule of incremental association algorithm mainly deals with two kinds of problems: dynamic adjustment of threshold and updating of database. Concerning problem of dynamic threshold adjustment, the main representative algorithm is IUA [6] algorithm proposed by Feng Yucai et al, and related algorithms have also been proposed later. Reference [7] adopts the Can-tree sorted by the amount of data to improve the efficiency of frequent itemset mining in space and time. Reference [8] improves alarm prediction accuracy and model training efficiency through the alarm weight and communication prediction plan digging by weighted incremental association rule mining based on Can-tree. Reference [9] proposed a parallel incremental association rule mining algorithm based on information entropy and genetic algorithm to solve the problem of dynamically setting the support degree threshold. There are mainly FUP [10], FUP2 [11], and SFUA [12] algorithms for database updating problems. FUP is the first incremental association mining algorithm, which solves the problem of data update mining well, but it also has some shortcomings, such as generating a large number of candidate itemsets, traversing the database many times and so on. In view of the above shortcomings, scholars have improved this algorithm. Reference [13] uses the combination of strong frequent itemset connection and prepruning to improve the execution efficiency of the algorithm. Reference [14] proposed a method to update association rules efficiently based on attribute change. Reference [15] transforms the dataset into Boolean matrix to reduce the number of scans and storage of the database. Reference [16] combines inverted index technology with tree structure to solve the problems of low efficiency and high computational cost of incremental update mining algorithm.In this study, an improved FUP algorithm is proposed. The algorithm uses the transaction identifier TID in the database to obtain frequent itemsets. It only needs to scan the database once, and then the candidate itemsets are obtained by connectingLK−1 and L1, so that the amount of calculation of the algorithm is significantly less than FUP. Through the detection of the circulation data of a university library, the experimental results show that compared with the standard FUP algorithm and SFUA algorithm, with the increase of borrowing record transactions, the improved FUP algorithm has significantly improved its operation efficiency, and can scientifically help the library do a good job in book recommendation.


## 2. Incremental Association Mining Algorithm

### 2.1. FUP Algorithm

#### 2.1.1. The Core Idea of FUP Algorithm

Assume the original dataset dB, the new dataset dB and the updated dataset (DB∪db). Frequent itemset LDB in Dataset DB and support degree supdb. The support degree supdb in new dataset db, minsup is the minimum support degree, and the core idea of FUP algorithm is [17] as follows:(1)
Frequent itemsetLdb of the dataset db generated by Apriori algorithm, for any frequent itemset t, if t∈LDB and t∈Ldb, then t will be the frequent itemset of the dataset (DB∪db).(2)
For any frequent itemsett, if t∈LDB and t∉Ldb , count the support degree supdb of t in db by scanning the new dataset db, then according to the support degree supDB of the original dataset calculate support degree sup (DB∪db) of itemset t by the formula in the updated dataset. If sup(DB∪db)>minsup, then itemset t is the frequent itemset of database set(DB∪db), otherwise is the infrequent itemset. The formula is: supDB∪db=supDBDB+supdbdb/DB+db(3)
For any frequent itemsett, if t∈Ldb and t∉LDB, count the support degree supDB of t in DB by scanning the new dataset DB, then calculate itemset t according to the support degree supdb in dataset (DB∪db), if sup(DB∪db) > minsup, t is the frequent itemset of database set(DB ∪ db), otherwise is the infrequent itemset.


#### 2.1.2. Analysis of FUP Algorithm

FUP algorithm uses the frequent itemsets and support of the original dataset to generate a much smaller candidate itemset. When updating, it reduces the scanning of the original dataset as much as possible, so as to improve the efficiency of the algorithm. However, the algorithm also has obvious shortcomings [18]:(1)
The consumption of computing support is too large, and the database needs to be scanned many times, which is inefficient.(2)
Candidate itemsets are obtained by Apriori connection. With the increase of the number of items in the database, a large number of candidate itemsets will be generated, and the time complexity of the algorithm will rise sharply.


### 2.2. FUP2 Algorithm

FUP2 algorithm divides the updated database into ① datasets that remain unchanged after updating; ② additional datasets; and ③ deleted datasets. The algorithm adopts apriori_gen function and theLK−11 in frequent k-1 itemset of the updated dataset (DB ∪ db) generates a candidate k-itemset Ck, and Ck is a superset of LK−11. Then, using the LK in frequent k-itemset of the original dataset DB, the candidate itemset Ck is divided into the infrequent itemset and frequent itemset of the original dataset DB. What’s more, the two itemsets are processed to finally obtain the frequent k-itemset of (DB∪db). Compared with FUP algorithm, FUP2 algorithm improves the operation efficiency, but it still uses Apriori algorithm when generating candidate itemsets, which likes FUP algorithm, it will produce too many candidate itemsets.


### 2.3. SFUA Algorithm

SFUA algorithm is an incremental association mining algorithm proposed by Chen Jinsong and others. The algorithm is mainly based on apriori_gen function in Apriori algorithm generating a collection of frequent itemsets db. Using the property “for itemsetX, if X ∈ LDB, and X ∈ Ldb, there must be X ∈ L (DB∪db).” The frequent itemset is divided into three disjoint parts:①a certain itemset is a frequent itemset in both dataset DB and db; ② an itemset is a frequent itemset in DB, while a infrequent itemset in db; ③ a certain itemset is a frequent itemset in db, but it is infrequent in DBSFUA algorithm scans the dataset as follows: scanning the original transaction dataset DB only once; for the newly added dataset, db scanningk + 1 times; the aggregate number of scanning is |DB| + (k + 1)|db|. When the dataset is relative small, the efficiency of SFUA algorithm is truly high. However, when the newly added dataset is large, SFUA algorithm also has the problem of too many frequent itemsets.


## 2.1. FUP Algorithm

### 2.1.1. The Core Idea of FUP Algorithm

Assume the original dataset dB, the new dataset dB and the updated dataset (DB∪db). Frequent itemset LDB in Dataset DB and support degree supdb. The support degree supdb in new dataset db, minsup is the minimum support degree, and the core idea of FUP algorithm is [17] as follows:(1)
Frequent itemsetLdb of the dataset db generated by Apriori algorithm, for any frequent itemset t, if t∈LDB and t∈Ldb, then t will be the frequent itemset of the dataset (DB∪db).(2)
For any frequent itemsett, if t∈LDB and t∉Ldb , count the support degree supdb of t in db by scanning the new dataset db, then according to the support degree supDB of the original dataset calculate support degree sup (DB∪db) of itemset t by the formula in the updated dataset. If sup(DB∪db)>minsup, then itemset t is the frequent itemset of database set(DB∪db), otherwise is the infrequent itemset. The formula is: supDB∪db=supDBDB+supdbdb/DB+db(3)
For any frequent itemsett, if t∈Ldb and t∉LDB, count the support degree supDB of t in DB by scanning the new dataset DB, then calculate itemset t according to the support degree supdb in dataset (DB∪db), if sup(DB∪db) > minsup, t is the frequent itemset of database set(DB ∪ db), otherwise is the infrequent itemset.


### 2.1.2. Analysis of FUP Algorithm

FUP algorithm uses the frequent itemsets and support of the original dataset to generate a much smaller candidate itemset. When updating, it reduces the scanning of the original dataset as much as possible, so as to improve the efficiency of the algorithm. However, the algorithm also has obvious shortcomings [18]:(1)
The consumption of computing support is too large, and the database needs to be scanned many times, which is inefficient.(2)
Candidate itemsets are obtained by Apriori connection. With the increase of the number of items in the database, a large number of candidate itemsets will be generated, and the time complexity of the algorithm will rise sharply.


## 2.1.1. The Core Idea of FUP Algorithm

Assume the original dataset dB, the new dataset dB and the updated dataset (DB∪db). Frequent itemset LDB in Dataset DB and support degree supdb. The support degree supdb in new dataset db, minsup is the minimum support degree, and the core idea of FUP algorithm is [17] as follows:(1)
Frequent itemsetLdb of the dataset db generated by Apriori algorithm, for any frequent itemset t, if t∈LDB and t∈Ldb, then t will be the frequent itemset of the dataset (DB∪db).(2)
For any frequent itemsett, if t∈LDB and t∉Ldb , count the support degree supdb of t in db by scanning the new dataset db, then according to the support degree supDB of the original dataset calculate support degree sup (DB∪db) of itemset t by the formula in the updated dataset. If sup(DB∪db)>minsup, then itemset t is the frequent itemset of database set(DB∪db), otherwise is the infrequent itemset. The formula is: supDB∪db=supDBDB+supdbdb/DB+db(3)
For any frequent itemsett, if t∈Ldb and t∉LDB, count the support degree supDB of t in DB by scanning the new dataset DB, then calculate itemset t according to the support degree supdb in dataset (DB∪db), if sup(DB∪db) > minsup, t is the frequent itemset of database set(DB ∪ db), otherwise is the infrequent itemset.


## 2.1.2. Analysis of FUP Algorithm

FUP algorithm uses the frequent itemsets and support of the original dataset to generate a much smaller candidate itemset. When updating, it reduces the scanning of the original dataset as much as possible, so as to improve the efficiency of the algorithm. However, the algorithm also has obvious shortcomings [18]:(1)
The consumption of computing support is too large, and the database needs to be scanned many times, which is inefficient.(2)
Candidate itemsets are obtained by Apriori connection. With the increase of the number of items in the database, a large number of candidate itemsets will be generated, and the time complexity of the algorithm will rise sharply.


## 2.2. FUP2 Algorithm

FUP2 algorithm divides the updated database into ① datasets that remain unchanged after updating; ② additional datasets; and ③ deleted datasets. The algorithm adopts apriori_gen function and theLK−11 in frequent k-1 itemset of the updated dataset (DB ∪ db) generates a candidate k-itemset Ck, and Ck is a superset of LK−11. Then, using the LK in frequent k-itemset of the original dataset DB, the candidate itemset Ck is divided into the infrequent itemset and frequent itemset of the original dataset DB. What’s more, the two itemsets are processed to finally obtain the frequent k-itemset of (DB∪db). Compared with FUP algorithm, FUP2 algorithm improves the operation efficiency, but it still uses Apriori algorithm when generating candidate itemsets, which likes FUP algorithm, it will produce too many candidate itemsets.


## 2.3. SFUA Algorithm

SFUA algorithm is an incremental association mining algorithm proposed by Chen Jinsong and others. The algorithm is mainly based on apriori_gen function in Apriori algorithm generating a collection of frequent itemsets db. Using the property “for itemsetX, if X ∈ LDB, and X ∈ Ldb, there must be X ∈ L (DB∪db).” The frequent itemset is divided into three disjoint parts:①a certain itemset is a frequent itemset in both dataset DB and db; ② an itemset is a frequent itemset in DB, while a infrequent itemset in db; ③ a certain itemset is a frequent itemset in db, but it is infrequent in DBSFUA algorithm scans the dataset as follows: scanning the original transaction dataset DB only once; for the newly added dataset, db scanningk + 1 times; the aggregate number of scanning is |DB| + (k + 1)|db|. When the dataset is relative small, the efficiency of SFUA algorithm is truly high. However, when the newly added dataset is large, SFUA algorithm also has the problem of too many frequent itemsets.


## 3. Improved NFUP Algorithm Based on FUP Algorithm

### 3.1. Incremental Update Problem Analysis

The improved algorithm is based on the following theorems and properties [19], where S(X) is a set consisting of identifiers, the number of elements in S(X) is the support count of X, Ck is the candidate k-itemset, and Lk is the frequent k-itemset.Theorem 1.
the necessary and sufficient condition for itemsetX to becoming a frequent itemset is: SUP (DB∪db) (X)≥(|DB| + |db|)∗minsupTheorem 2.
if the itemsetX does not belong to the original frequent itemset, the necessary condition for X to become a frequent itemset is: SUPdb(X)≥|db|∗ minsup.Theorem 3.
∀C∈Ck, S(C) can be obtained from two elements S(X) and S(Y) in Sk−1, and SC=SX∩SY.Property 1.
If itemsetX is a frequent itemset in (DB∪db), then X is at least frequent in DB or db.Property 2.
If all candidate itemsets Ck can be generated by Lk−1∞Lk−1 and there is t∈ Lk-1, the candidate itemset can also be generated by Lk−1∞L1.
From Theorem1, Theorem 2, and Property 1, combined with the support calculation formula, we can deduce SUPDB(t)+SUPdb(t)≥ (|DB| + |db|)∗minsup, that is, to determine whether an itemset is a frequent itemset in the updated dataset, we need to compare whetherSUPDB(t) + SUPdb(t) ≥ (|DB| + |db|)∗minsup is true.
According to the above derivation formula and FUP algorithm, when adding a dataset db to an original dataset DB, the itemset has the following situations:(1)
If an itemset is a frequent itemset in both dataset DB and db, the itemset is also a frequent itemset in dataset(DB ∪ db).(2)
For any frequent itemsett, if there are one of the following two cases: ① t∈LDB and t∉Ldb② t∈Ldb and t∉LDB, if judging whether t is a frequent itemset in the dataset(DB∪db), it is necessary to compare the relationship between SUPDB(t)+SUPdb(t) and (|DB|+|db|)∗minsup. If the former is bigger than the latter, it is a frequent itemset, otherwise it is a infrequent itemset.(3)
Moreover,t must also be a infrequent itemset in the updated dataset (DB∪db) if t∉LDB and t∉Ldb. For cases (1) and (3), it is easy to determine whether they are frequent itemsets, so the improved algorithm focuses on case (2), and the problem is how to quickly find frequent itemsets. From Property 2, it is obtained by connecting Lk−1 and L1 when generating the candidate candidate set. The improved algorithm replaces the Apriori algorithm used in the original FUP algorithm to obtain the candidate item set for L K-1 self connection.
FUP algorithm mainly deals with the frequent itemsets of the database. In view of the shortcomings of this algorithm, this study proposes a method NFUP to obtain candidate itemsets by connectingLk−1 and L1. When generating frequent itemsets, it uses the transaction identifier TID in the database to obtain them. For the generated frequent itemsets, only the transaction identifier TID list and support degree need to be retained. The improved algorithm NFUP only needs to scan the original dataset and the new dataset once.


### 3.2. Execution Process of NFUP Minimum Support

(1)
Scan the original dataset DB and the new dataset db respectively. The candidate item set of DB and db isCDB1, Cdb1, record the transaction identifier TID list corresponding to each item, and get the frequent 1-itemset of DB and db according to the minimum support, and mark them as LDB1 and Ldb1.(2)
According to Theorem3, calculate the support degree of db in DB. The support degreeof Ldb1 in LDB1 is the support degree of db in DB. According to the formula: SUPDB(t) + SUPdb(t), calculate the support degree of Ldb1 in (DB∪db). If SUPDB(t) + SUPdb(t)≥ (|DB| + |db|)∗minsup is true, it is the frequent itemset of (DB∪db), otherwise it is the infrequent itemset. In order to avoid repeating operations, LDB11 obtained from the same items in LDB1 and Ldb1 that deleted from LDB1, and calculate the support degree of LDB11 in db. If the support degree of LDB11 in db is empty, it means that an item in DB has never appeared in db. Then continue to calculate the support degree of LDB11 in (DB ∪ db). If it is bigger than (|DB| + |db|)∗minsup, this item can be retained as a frequent itemset.(3)
Merge the frequent itemset ofLdb1 in (DB ∪ db) and the frequent itemset of LDB11 in (DB ∪ db) to obtain the frequent 1-itemset of LDB∪db1 in (DB∪db).(4)
k > 1, Calculate and itemsets of LDBk and Ldbk, obtain LDB∪db1 and respectively prune according to step (3), then obtain LDB12 and Ldb12. Adopt improved Apriori_gen algorithm in LDB12 and Ldb12 to generate candidate itemset of LDB12 and Ldb12. The idea of improvement followed by Property 2 shows that the candidate itemset Ck can also be generated by Lk−1∞L1. The choice of Lk−1 is related to k. when k = 2, it is actually L1 connecting L1, and L1 is the frequent one item set after pruning.Continue to perform steps (1), (2) and (3) in the above process to obtain the frequent itemsetk of (DB ∪ db) until the candidate itemset k + 1 of (DB ∪ db) is empty till the execution process ends.


### 3.3. NFUP Main Function Execution Function

(1)
Build identifier Get_TID( ) function of 1 item collectionGet_ TID (database) function:(1)
C1 = {database collection)}(2)
for all itemC ∈ C1 do S(C) = c//S contains a set of identifiers, c is each item of C1(3)
end for(4)
for allt ∈ Database do//an item in S(5)
Ct = subset(t, C1)(6)
for allC ∈ Ct do S(C) = S(C) ∪ t.TID( )//build the identifier of 1-itemset to form 1 collection(2)
The process of generating candidate itemsets Apriori_gen( ) functionApriori_CI( ) function:(1)
for alllk−1∈Lk−1 do//lk−1 is one item of Lk−1(2)
for alllk−1 ∈L1 do(3)
lk−1 = lk−1∞l1(4)
S(lk) = S(lk−1) ∩ ∪S(l1)//generate k-itemsets(5)
Ct = subset(t, C1)//gets a list of identifiers for the k-itemset


### 3.4. Case Analysis of NFUP

In order to better understand the process of finding frequent itemsets using NFUP algorithm, examples are listed for analysis. The original dataset DB is known, and the minimum support is 4. The specific information is shown in Table1. Add a new dataset db with a minimum support of 2. The specific transaction data are shown in Table 2. The minimum support value of the updated dataset (DB ∪ db) is 6.Table 1
Dataset DB.
TIDItemsetT1I1,I2,I4,I5T2I1,I2,I3,I4T3I1,I2,I4,I5,I6T4I3,I4T5I1,I3,I4,I6T6I1,I2,I4,I5T7I2,I3,I4T8I1,I2,I3,I4,I5,I6Table 2
New dataset db.
TIDItemsetT1I2,I3T2I1,I2,I3,I5T3I1,I2,I5T4I1,I3,I5,I6T5I1,I2The process of mining frequent sets using the improved NFUP algorithm is shown in Figure1.Figure 1
The process of digging frequent itemsets by using NFUP mining algorithm.Scan the original dataset DB and the new dataset db respectively to obtain the candidate item set. In Figure1. ①, CDB1, Cdb1 are the candidate item sets of the original dataset and the new dataset respectively. Then the frequent itemsets LDB1, Ldb1 of DB and db are obtained according to the minimum support. Here, corresponding identifier and each item obtained from the improved algorithm Get_TID( ) function.In Figure1. ②, according to Theorem 3, the support degree of Ldb1 in DB is counted, and the support degree of db in (DB ∪ db) is calculated. The support degree of {I1} in DB is 3, and that in db is 4. According to the formula SUPDB(I1) + SUPdb(I1), 3 + 4>6 is calculated, so { I1} is the frequent 1-itemset in (DB∪db). Similarly, {I2} is also the frequent item set in (DB∪db). {I3} and {I5} are infrequent itemsets via validating. To avoid repeating operations, delete the same items in Ldb1 and LDB1 from LDB1, and the remaining itemset is {I4}. Count the support degree of { I4} in the dataset (DB∪db). First calculate the support degree of {I4} in db. If {I4} does not appear in, the support count is 0, that is, the support degree of {I4} in Ldb1 is 0, the support degree of {I4} in LDB1 is 8, and 0 + 8 is bigger than the minimum support degree of 6, so it is determined that {I4} is the frequent itemset of (DB∪db). Merge and obtain the frequent 1-itemset {I1,I2,I4} of (DB∪db).In Figure1. (2), prune LDB1 and Ldb1 respectively according to the frequent 1-itemset of (DB∪db). Adopt the improved Apriori_gen algorithm to generate candidate itemsets, and then obtains two frequent itemsets CDB2 and Cdb2 . The same as the above calculation process, counte the Ldb2 in frequent 2- itemset of (DB∪db) and LDB2 in the frequent 2-itemset of (DB ∪ db). The obtained frequent 2-itemsets are: {{I1, I4},{I2,I4}}. Because Ldb2 in the frequent 2-itemset of (DB ∪ db) is empty, the frequent 3-itemset in (DB∪db) is empty, and all frequent itemsets in (DB ∪ db) are {I1,I2,I4, {I1, I4},{I2,I4}}. It is consistent with the mining results of FUP algorithm.


## 3.1. Incremental Update Problem Analysis

The improved algorithm is based on the following theorems and properties [19], where S(X) is a set consisting of identifiers, the number of elements in S(X) is the support count of X, Ck is the candidate k-itemset, and Lk is the frequent k-itemset.Theorem 1.
the necessary and sufficient condition for itemsetX to becoming a frequent itemset is: SUP (DB∪db) (X)≥(|DB| + |db|)∗minsupTheorem 2.
if the itemsetX does not belong to the original frequent itemset, the necessary condition for X to become a frequent itemset is: SUPdb(X)≥|db|∗ minsup.Theorem 3.
∀C∈Ck, S(C) can be obtained from two elements S(X) and S(Y) in Sk−1, and SC=SX∩SY.Property 1.
If itemsetX is a frequent itemset in (DB∪db), then X is at least frequent in DB or db.Property 2.
If all candidate itemsets Ck can be generated by Lk−1∞Lk−1 and there is t∈ Lk-1, the candidate itemset can also be generated by Lk−1∞L1.
From Theorem1, Theorem 2, and Property 1, combined with the support calculation formula, we can deduce SUPDB(t)+SUPdb(t)≥ (|DB| + |db|)∗minsup, that is, to determine whether an itemset is a frequent itemset in the updated dataset, we need to compare whetherSUPDB(t) + SUPdb(t) ≥ (|DB| + |db|)∗minsup is true.
According to the above derivation formula and FUP algorithm, when adding a dataset db to an original dataset DB, the itemset has the following situations:(1)
If an itemset is a frequent itemset in both dataset DB and db, the itemset is also a frequent itemset in dataset(DB ∪ db).(2)
For any frequent itemsett, if there are one of the following two cases: ① t∈LDB and t∉Ldb② t∈Ldb and t∉LDB, if judging whether t is a frequent itemset in the dataset(DB∪db), it is necessary to compare the relationship between SUPDB(t)+SUPdb(t) and (|DB|+|db|)∗minsup. If the former is bigger than the latter, it is a frequent itemset, otherwise it is a infrequent itemset.(3)
Moreover,t must also be a infrequent itemset in the updated dataset (DB∪db) if t∉LDB and t∉Ldb. For cases (1) and (3), it is easy to determine whether they are frequent itemsets, so the improved algorithm focuses on case (2), and the problem is how to quickly find frequent itemsets. From Property 2, it is obtained by connecting Lk−1 and L1 when generating the candidate candidate set. The improved algorithm replaces the Apriori algorithm used in the original FUP algorithm to obtain the candidate item set for L K-1 self connection.
FUP algorithm mainly deals with the frequent itemsets of the database. In view of the shortcomings of this algorithm, this study proposes a method NFUP to obtain candidate itemsets by connectingLk−1 and L1. When generating frequent itemsets, it uses the transaction identifier TID in the database to obtain them. For the generated frequent itemsets, only the transaction identifier TID list and support degree need to be retained. The improved algorithm NFUP only needs to scan the original dataset and the new dataset once.


## 3.2. Execution Process of NFUP Minimum Support

(1)
Scan the original dataset DB and the new dataset db respectively. The candidate item set of DB and db isCDB1, Cdb1, record the transaction identifier TID list corresponding to each item, and get the frequent 1-itemset of DB and db according to the minimum support, and mark them as LDB1 and Ldb1.(2)
According to Theorem3, calculate the support degree of db in DB. The support degreeof Ldb1 in LDB1 is the support degree of db in DB. According to the formula: SUPDB(t) + SUPdb(t), calculate the support degree of Ldb1 in (DB∪db). If SUPDB(t) + SUPdb(t)≥ (|DB| + |db|)∗minsup is true, it is the frequent itemset of (DB∪db), otherwise it is the infrequent itemset. In order to avoid repeating operations, LDB11 obtained from the same items in LDB1 and Ldb1 that deleted from LDB1, and calculate the support degree of LDB11 in db. If the support degree of LDB11 in db is empty, it means that an item in DB has never appeared in db. Then continue to calculate the support degree of LDB11 in (DB ∪ db). If it is bigger than (|DB| + |db|)∗minsup, this item can be retained as a frequent itemset.(3)
Merge the frequent itemset ofLdb1 in (DB ∪ db) and the frequent itemset of LDB11 in (DB ∪ db) to obtain the frequent 1-itemset of LDB∪db1 in (DB∪db).(4)
k > 1, Calculate and itemsets of LDBk and Ldbk, obtain LDB∪db1 and respectively prune according to step (3), then obtain LDB12 and Ldb12. Adopt improved Apriori_gen algorithm in LDB12 and Ldb12 to generate candidate itemset of LDB12 and Ldb12. The idea of improvement followed by Property 2 shows that the candidate itemset Ck can also be generated by Lk−1∞L1. The choice of Lk−1 is related to k. when k = 2, it is actually L1 connecting L1, and L1 is the frequent one item set after pruning.Continue to perform steps (1), (2) and (3) in the above process to obtain the frequent itemsetk of (DB ∪ db) until the candidate itemset k + 1 of (DB ∪ db) is empty till the execution process ends.


## 3.3. NFUP Main Function Execution Function

(1)
Build identifier Get_TID( ) function of 1 item collectionGet_ TID (database) function:(1)
C1 = {database collection)}(2)
for all itemC ∈ C1 do S(C) = c//S contains a set of identifiers, c is each item of C1(3)
end for(4)
for allt ∈ Database do//an item in S(5)
Ct = subset(t, C1)(6)
for allC ∈ Ct do S(C) = S(C) ∪ t.TID( )//build the identifier of 1-itemset to form 1 collection(2)
The process of generating candidate itemsets Apriori_gen( ) functionApriori_CI( ) function:(1)
for alllk−1∈Lk−1 do//lk−1 is one item of Lk−1(2)
for alllk−1 ∈L1 do(3)
lk−1 = lk−1∞l1(4)
S(lk) = S(lk−1) ∩ ∪S(l1)//generate k-itemsets(5)
Ct = subset(t, C1)//gets a list of identifiers for the k-itemset


## 3.4. Case Analysis of NFUP

In order to better understand the process of finding frequent itemsets using NFUP algorithm, examples are listed for analysis. The original dataset DB is known, and the minimum support is 4. The specific information is shown in Table1. Add a new dataset db with a minimum support of 2. The specific transaction data are shown in Table 2. The minimum support value of the updated dataset (DB ∪ db) is 6.Table 1
Dataset DB.
TIDItemsetT1I1,I2,I4,I5T2I1,I2,I3,I4T3I1,I2,I4,I5,I6T4I3,I4T5I1,I3,I4,I6T6I1,I2,I4,I5T7I2,I3,I4T8I1,I2,I3,I4,I5,I6Table 2
New dataset db.
TIDItemsetT1I2,I3T2I1,I2,I3,I5T3I1,I2,I5T4I1,I3,I5,I6T5I1,I2The process of mining frequent sets using the improved NFUP algorithm is shown in Figure1.Figure 1
The process of digging frequent itemsets by using NFUP mining algorithm.Scan the original dataset DB and the new dataset db respectively to obtain the candidate item set. In Figure1. ①, CDB1, Cdb1 are the candidate item sets of the original dataset and the new dataset respectively. Then the frequent itemsets LDB1, Ldb1 of DB and db are obtained according to the minimum support. Here, corresponding identifier and each item obtained from the improved algorithm Get_TID( ) function.In Figure1. ②, according to Theorem 3, the support degree of Ldb1 in DB is counted, and the support degree of db in (DB ∪ db) is calculated. The support degree of {I1} in DB is 3, and that in db is 4. According to the formula SUPDB(I1) + SUPdb(I1), 3 + 4>6 is calculated, so { I1} is the frequent 1-itemset in (DB∪db). Similarly, {I2} is also the frequent item set in (DB∪db). {I3} and {I5} are infrequent itemsets via validating. To avoid repeating operations, delete the same items in Ldb1 and LDB1 from LDB1, and the remaining itemset is {I4}. Count the support degree of { I4} in the dataset (DB∪db). First calculate the support degree of {I4} in db. If {I4} does not appear in, the support count is 0, that is, the support degree of {I4} in Ldb1 is 0, the support degree of {I4} in LDB1 is 8, and 0 + 8 is bigger than the minimum support degree of 6, so it is determined that {I4} is the frequent itemset of (DB∪db). Merge and obtain the frequent 1-itemset {I1,I2,I4} of (DB∪db).In Figure1. (2), prune LDB1 and Ldb1 respectively according to the frequent 1-itemset of (DB∪db). Adopt the improved Apriori_gen algorithm to generate candidate itemsets, and then obtains two frequent itemsets CDB2 and Cdb2 . The same as the above calculation process, counte the Ldb2 in frequent 2- itemset of (DB∪db) and LDB2 in the frequent 2-itemset of (DB ∪ db). The obtained frequent 2-itemsets are: {{I1, I4},{I2,I4}}. Because Ldb2 in the frequent 2-itemset of (DB ∪ db) is empty, the frequent 3-itemset in (DB∪db) is empty, and all frequent itemsets in (DB ∪ db) are {I1,I2,I4, {I1, I4},{I2,I4}}. It is consistent with the mining results of FUP algorithm.


## 4. Application of NFUP in Library Circulation Data

In order to test the feasibility and effectiveness of the improved incremental data association rule mining algorithm, library circulation data is used for detection. Test environment: 4G memory, CPU 2.50 ghz, window7 operating system, test software: WEKA.


### 4.1. Data Preprocessing

The mining data comes from the borrowing information of students from August 2017 to July 2019 exported from the management system of a university library. There are 110,326 records of the exported borrowing information. The core data in the borrowing information is shown in Table3. Data cleaning, integration, selection and other processing work are carried out for borrowing information, and the processed data is 35,232 records. For the processed data, the book is classified by the retrievable number, and the classification number is A—Z, in which the classification number A—Z corresponds to 22 major categories in the Chinese library. The borrowing records are generalized to obtain the borrowing record transactions. The information in the transaction table is shown in Table 4.Table 3
Book borrowing records (part).
Borrowing numberAccession numberBorrowing numberAccession number2015405031I247.572016302021D925.2012015405032F237.2/472016302022F279.2432015405033F713.32016302023B821-492015405034F2532016302024I247.572015405035TP311.52016302025TP294.42015405036TP3912016302026TP316…………Table 4
Lending record transactions (part).
Borrowing numberCategoryBorrowing numberCategory2015405031I, H2016302021D, H, O, T2015405032F, T2016302022F, I2015405033F, O2016302023B, C, D2015405034F,T, O2016302024I, D2015405035T, K, J2016302025T, I, F2015405036T, I, H, B2016302026T, R, I…………


### 4.2. Analysis of Association Rule Mining Results

Given the minimum support degree is 15%, the confidence is 40%, and 3,000 new data are added, the mining results are shown in Table5.Table 5
Mining results (part).
ConsequentAntecedentSupport degree (%)Confidence (%)FT18.57170.732FO16.870.35HT19.569.7IH34.41368.731IJ18.22168.6OH27.7245.767…………From the mining results, 70.732% of the students who borrowed T-books borrowed F-books at the same time. 68.731% of the students who borrowed H-books and I-books simultaneously. The probability of H and I-books being borrowed at the same time is 34.413%, and the other rules are similar. According to the mining results, it can help university libraries establish a more reasonable collection layout, improve the utilization rate of library collection resources, and scientifically help libraries do a better job in book recommendation.In order to verify the operation efficiency of the improved algorithm, a comparative experiment is carried out on FUP algorithm, SFUA algorithm and NFUP algorithm. Because FUP2 algorithm is equivalent to FUP algorithm when the database is added, so it is not used for comparison. When the original dataset DB used in the experiment is 7,000, the new dataset db is 3,000, and the dataset of (DB∪db) increases from 10,000 to 30,000, the running time of the three algorithms is shown in Table6, the comparison of running time is shown in Figure 2. The execution time is the execution time of the updated dataset (DB∪db) when all frequent itemsets in the original database are known. From Figure 2, with the increase of transaction data, the execution time of FUP algorithm, SFUA algorithm and NFUP algorithm gradually increases, but the execution time of NFUP algorithm is shorter than that of SFUA algorithm and FUP algorithm, which has main reasons as follows:(1)
The FUP algorithm needs to scan the original dataset and the newly added one for many times. The Hash table is used to store the candidate optionset. During mining, the Hash table needs to be searched, while the SFUA algorithm scans the original transaction dataset DB once; for the newly added dataset db scansk + 1 times. NFUP algorithm only needs to traverse the database once to obtain the transaction identifier TID of each item, and get the frequent itemset according to the transaction identifier.(2)
NFUP algorithm obtains frequent itemsets by connectingLK−1 and L1, and prunes the frequent k-itemsets before generating candidate itemsets. The amount of computation and the number of candidate itemsets of the algorithm are significantly reduced. Compared with FUP algorithm and SFUA algorithm, this algorithm is more efficient.Table 6
Running schedule for the three algorithms.
Transaction volume (10000)FUP (s)NFUP (s)SFUA (s)164.75.11.585.66.329.778.12.515810.53181114Figure 2
Comparison diagram of the experimental results.


## 4.1. Data Preprocessing

The mining data comes from the borrowing information of students from August 2017 to July 2019 exported from the management system of a university library. There are 110,326 records of the exported borrowing information. The core data in the borrowing information is shown in Table3. Data cleaning, integration, selection and other processing work are carried out for borrowing information, and the processed data is 35,232 records. For the processed data, the book is classified by the retrievable number, and the classification number is A—Z, in which the classification number A—Z corresponds to 22 major categories in the Chinese library. The borrowing records are generalized to obtain the borrowing record transactions. The information in the transaction table is shown in Table 4.Table 3
Book borrowing records (part).
Borrowing numberAccession numberBorrowing numberAccession number2015405031I247.572016302021D925.2012015405032F237.2/472016302022F279.2432015405033F713.32016302023B821-492015405034F2532016302024I247.572015405035TP311.52016302025TP294.42015405036TP3912016302026TP316…………Table 4
Lending record transactions (part).
Borrowing numberCategoryBorrowing numberCategory2015405031I, H2016302021D, H, O, T2015405032F, T2016302022F, I2015405033F, O2016302023B, C, D2015405034F,T, O2016302024I, D2015405035T, K, J2016302025T, I, F2015405036T, I, H, B2016302026T, R, I…………


## 4.2. Analysis of Association Rule Mining Results

Given the minimum support degree is 15%, the confidence is 40%, and 3,000 new data are added, the mining results are shown in Table5.Table 5
Mining results (part).
ConsequentAntecedentSupport degree (%)Confidence (%)FT18.57170.732FO16.870.35HT19.569.7IH34.41368.731IJ18.22168.6OH27.7245.767…………From the mining results, 70.732% of the students who borrowed T-books borrowed F-books at the same time. 68.731% of the students who borrowed H-books and I-books simultaneously. The probability of H and I-books being borrowed at the same time is 34.413%, and the other rules are similar. According to the mining results, it can help university libraries establish a more reasonable collection layout, improve the utilization rate of library collection resources, and scientifically help libraries do a better job in book recommendation.In order to verify the operation efficiency of the improved algorithm, a comparative experiment is carried out on FUP algorithm, SFUA algorithm and NFUP algorithm. Because FUP2 algorithm is equivalent to FUP algorithm when the database is added, so it is not used for comparison. When the original dataset DB used in the experiment is 7,000, the new dataset db is 3,000, and the dataset of (DB∪db) increases from 10,000 to 30,000, the running time of the three algorithms is shown in Table6, the comparison of running time is shown in Figure 2. The execution time is the execution time of the updated dataset (DB∪db) when all frequent itemsets in the original database are known. From Figure 2, with the increase of transaction data, the execution time of FUP algorithm, SFUA algorithm and NFUP algorithm gradually increases, but the execution time of NFUP algorithm is shorter than that of SFUA algorithm and FUP algorithm, which has main reasons as follows:(1)
The FUP algorithm needs to scan the original dataset and the newly added one for many times. The Hash table is used to store the candidate optionset. During mining, the Hash table needs to be searched, while the SFUA algorithm scans the original transaction dataset DB once; for the newly added dataset db scansk + 1 times. NFUP algorithm only needs to traverse the database once to obtain the transaction identifier TID of each item, and get the frequent itemset according to the transaction identifier.(2)
NFUP algorithm obtains frequent itemsets by connectingLK−1 and L1, and prunes the frequent k-itemsets before generating candidate itemsets. The amount of computation and the number of candidate itemsets of the algorithm are significantly reduced. Compared with FUP algorithm and SFUA algorithm, this algorithm is more efficient.Table 6
Running schedule for the three algorithms.
Transaction volume (10000)FUP (s)NFUP (s)SFUA (s)164.75.11.585.66.329.778.12.515810.53181114Figure 2
Comparison diagram of the experimental results.


## 5. Summary and Prospect

Incremental association mining algorithm FUP solves the problem of data updating, but the algorithm needs to traverse the database many times and spend a lot of efforts dealing with the candidate itemset with geometric growth. In this study, FUP is improved. The improved algorithm NFUP uses the transaction identifier TID in the database to obtain the frequent itemsets. It only needs to traverse the database once. The candidate itemsets are obtained by connectingL K-1 and L1, so that the amount of calculation of the algorithm is significantly less than FUP. The experimental results of borrowing data in the library management system show that compared with FUP algorithm and SFUA algorithm, with the increase of the amount of transaction data, the improved NFUP algorithm improves the operation efficiency and can efficaciously help the library do a good job in book recommendation. In the next research, we can focus on the borrowing relationship of a specific subcategory (such as category TP), dig out popular books, try to dig out the relationship between majors and book categories, find out the borrowing interests of students of different majors, and recommend books according to students’ borrowing habits.



---

*Source: 1683099-2022-04-14.xml*