Using Multi-Conditional Minimum Thresholds in Temporal Fuzzy Utility Mining

Wei-Ming Huang; Tzung-Pei Hong; Ming-Chao Chiang; Jerry Chun-Wei Lin

doi:10.2991/ijcis.d.190426.001

<Previous Article In Issue

Download article (PDF)

Next Article In Issue>

Volume 12, Issue 2, 2019, Pages 613 - 626

Using Multi-Conditional Minimum Thresholds in Temporal Fuzzy Utility Mining

Authors

Wei-Ming Huang¹, Tzung-Pei Hong¹^{, 2}^{, *}, Ming-Chao Chiang¹, Jerry Chun-Wei Lin³

¹Department of Computer Science and Engineering, National Sun Yat-sen University, 70, Lienhai Road, 80424 Kaohsiung, Taiwan, R.O.C.

²Department of Computer Science and Information Engineering, National University of Kaohsiung, 700, Kaohsiung University Road, Nanzih District, 81148 Kaohsiung, Taiwan, R.O.C.

³Department of Computing, Mathematics, and Physics, Western Norway University of Applied Science, Inndalsveien 28, 5063 Bergen, Norway

^*Corresponding author. Email: tphong@nuk.edu.tw

Corresponding Author

Tzung-Pei Hong

Received 21 December 2018, Accepted 12 April 2019, Available Online 11 May 2019.

DOI: 10.2991/ijcis.d.190426.001 How to use a DOI?
Keywords: Fuzzy data mining; fuzzy set; Temporal fuzzy utility mining; Multiple thresholds; Extended two-phase model
Abstract: In the field of fuzzy utility mining, the characteristics of transaction time have been a widely studied topic in data mining. However, using a single-conditional threshold for all items does not suffice to reflect the true properties of items. This paper, therefore, proposes a multi-conditional minimum threshold approach which considers the temporal behavior, the importance in items, and the usage of linguistic terms to mine high temporal fuzzy utility itemsets. The multi-conditional minimum thresholds are utilized to assist users in deciding appropriate standards for itemsets in mining when its contained items have different importance. An extended two-phase model and a corresponding mining approach are designed to handle the temporal fuzzy utility mining problem with the multi-conditional minimum thresholds. Finally, the results from the experimental evaluation show the effectiveness of the proposed approach under different settings.
Copyright: © 2019 The Authors. Published by Atlantis Press SARL.
Open Access: This is an open access article distributed under the CC BY-NC 4.0 license (http://creativecommons.org/licenses/by-nc/4.0/).

1. INTRODUCTION

Discovering knowledge discovery in data mining have been widely studied due to its wide applications. Frequent patterns found by association-rule mining is one of the fundamental research issues, as it can be used to identify implicit relationships among items in a database [1–3]. One drawback of association-rule mining, however, is that we cannot take for granted that the quantity of an item is binary. Besides, it cannot consider the profit of an item as an essential factor, either. As such, mining frequent itemsets are easy, in contrast to finding high-utility itemsets with the quantitative information and unit profit. Thus the utility mining strategy [4] was proposed, which considers both the sold quantities of items and their corresponding unit profits in transactions for recognizing the actual utility values of itemsets and thus discovering high-utility itemsets from a transaction database. Most of the related approaches were designed to improve the execution efficiency [5–9], to find the items with negative profits [10], to consider the on-shelf periods of the items [11–13], or to process the dynamic update of the datasets [14,15]. However, quantitative values are still not easily understood by decision-makers.

To resolve the problem, fuzzy sets provided a good solution, and thus fuzzy utility mining strategy [16,17] was proposed. Transforming quantitative information in each transaction to implied fuzzy terms by using the membership functions of each item, with the fuzzy intersection operator of fuzzy sets, users can easily comprehend the implication of quantity.

However, fuzzy utility mining has difficulty in maintaining the downward-closure property which is the main principle for association-rule mining to prune candidate itemsets efficiently. Lan et al. presented a fuzzy utility function and adopted the minimum operator for the intersection [17]. Besides, they propose an effective model with fuzzy utility upper bounds to prune unpromising candidates early in fuzzy utility mining. Going on the above concept, the late-on-shelf items in a supermarket may be obscured in fuzzy utility mining. Therefore, temporal fuzzy utility mining [18] was proposed to consider the first on-shelf time of an item to find more relevant patterns. Most works in fuzzy utility mining have been proposed to handle various applications but use only a single-conditional measurement for determining high fuzzy utility itemsets [16–18].

Nevertheless, a single-conditional measurement [9–11,16] may not accurately reflect the properties of items and itemsets in real applications, such as the difference in significance between emerging items and aged ones. In the past, several algorithms considering multiple-conditional measurements for association-rule mining [19–23], fuzzy association-rule mining [24,25], utility mining [26], and sequential pattern mining [27] have been studied. In these approaches, each item can be assigned an individual threshold.

According to the above reasons, in this paper, we consider the temporal fuzzy utility mining problem with multi-conditional minimum thresholds (TFUMP_mmt). In the problem, the given minimum thresholds depend on the items. A mechanism is then designed to decide the minimum thresholds of itemsets based on the fuzzy operators. To avoid information loss, an extended two-phase model is provided to keep the downward-closure property for TFUMP_mmt, and a TPM (Two-Phase Multi-conditional algorithm for temporal fuzzy utility mining) algorithm is proposed to solve it. At last, experimental results are given to compare the efficiency and effectiveness of the proposed approach and that for the temporal fuzzy utility mining problem with single-conditional minimum threshold (TFUMP_smt).

2. RELATED WORKS

The association-rule mining, such as the Apriori approach proposed by Agrawal et al. [1,2] and the FP-growth presented by Han et al. [28], focuses on binary mining to reveal the co-occurrence relationship of items but cannot discover itemsets with high profit. Products with high profit but low frequency may not be found in mining. The utility model, proposed by Yao et al. [4], then keeps the quantitative value of items and their profits to solve the disadvantage. Besides, Chan et al. [29] proposed the topic of utility mining, which considered not only quantities of items in a transaction but also profits of items in a database, to find itemsets with high utility values. However, the high-utility itemsets discovered contain just items without quantitative information and are difficult for users to comprehend the quantitative relationship of the items.

Fuzzy quantifiers can represent fuzzy approximation to the implicit meaning of facts [30,31]. For example, “two oranges” in a quantitative sentence can be treated as a “low” amount label for the semantic meaning needed by decision-makers. Thus, the methods of fuzzy utility mining were designed to capture the explicit meaning of the quantity sold. For example, Lan et al. [17] presented a framework to discover high fuzzy utility itemsets by adopting the fuzzy concepts to convert the quantity information in a quantitative transactional dataset into fuzzy regions. Wang et al. [16] also defined fuzzy utility mining as the problem of identifying linguistic itemsets taking into account both whole (i.e., three apples) and fractional (i.e., 2.1 pounds) quantities.

The methods mentioned above did not consider the temporal factor of the items while discussing high-utility or fuzzy utility itemsets. Because of this, short-sale or time-limited items in a supermarket may be obscured in mining. For example, during summer or winter vacations, supermarkets use different sale strategies to promote unfixed products. However, if all the products on shelves are viewed as being of the same time, it is difficult to explore the various combinations of products effectively, especially in short-sale or time-limited situations. To overcome the limitation, Huang et al. [18] in 2017 introduced fuzzy utility mining with consideration of transactional time (TFUM). But they only use a single minimum threshold to get high temporal fuzzy utility itemsets (HTFUIs).

The use of a single-conditional threshold in mining has largely been applied in utility mining [4,7,12,13], incremental utility mining [15], and fuzzy utility mining [17,18]. Existing approaches employ the threshold for all items as a measuring standard to mine desired itemsets. However, considering all items of the same importance does not reflect real-world practice. Thus, the threshold requirement should depend on the items to get better effects. For example, people will consider the utility of emerging items and aged ones under different criteria. An emerging item may not currently get much profit, but it may have a high potential to earn much money in the future. Hence, using a minimum fuzzy utility threshold for all items in fuzzy utility mining is not a fair measurement. Although taking into account multiple item thresholds better reflects real-world needs, it is also more challenging.

3. MINING TEMPORAL FUZZY UTILITY ITEMSETS WITH MULTI-CONDITIONAL MINIMUM THRESHOLDS

3.1. The Concept of the Proposed TPM Method

The proposed method mines HTFUIs under multi-conditional minimum thresholds. Figure 1 shows the execution process of the proposed TPM method.

In Figure 1, the <Preprocessing> dotted box contains the parameters of the proposed approach and the fuzzified process of the transaction data. First, a quantitative database is transformed into a corresponding temporal quantitative database by time periods, which is then converted into the temporal fuzzy database by fuzzy transformation. The <Input parameters> dotted box includes a utility table storing the profit of each item and a set of multiple minimum thresholds with items. After the preprocessing steps are conducted, the proposed mining method has two main phases. In the first phase, the algorithm determines the high upper-bound itemsets which satisfy the upper-bound ratio. Then in the second phase, the upper-bound itemsets derived in the first phase are further checked to find their actual fuzzy utility values. The fuzzy itemsets with their actual fuzzy utility values larger than or equal to the corresponding thresholds are output as the results. In this way, the proposed method can find the complete set of HTFUIs satisfying the multi-conditional minimum constraints.

3.2. Formal Problem Definition

Let P = {P₁, P₂, …, P_m}, where m represents the number of time periods and P_i represents the i-th time period, be a set of adjacent disjoint time periods with a d ∈ esignated time granularity. Given a set I of n distinct items {i₁, i₂, …, i_n}, a quantitative transaction database is a set of transactions represented as QTD = {Qtrans₁, Qtrans₂, …, Qtrans_y, …, Qtrans_z}, in which each transaction Qtrans_yQTD 1≤y≤z is a subset of I and has a Unique Identifier (TID). In addition, each item i_g in Qtrans_y possesses a quantitative value as its sale amount (denoted as v_yg). Based on the membership functions of the quantitative values of the item i_g, the value v_yg of i_g in the quantitative transaction Qtrans_y is transformed into a fuzzy set f_yg represented as

fyg=fyg1Rg1+fyg2Rg2+…+fyglRgl+…+fyghRgh,

where h is the number of membership functions for i_g, R_gl is the l-th linguistic term of i_g, and f_ygl is the fuzzy membership value of v_yg in R_gl. Besides, a profit table = {S₁, S₂, …, S_n} needs to be given, with an element S_g denoting the profit value of a corresponding item i_g. An itemset X with k distinct items {i₁, i₂, …, i_k} satisfying X⊆I is called a k-itemset, where k is the length of the itemset. Itemset X is said to be contained in a transaction Qtrans_y if X⊆Qtransy. An example of a temporal quantitative dataset is shown in Table 1.

Period	TID	A	B	C	D	E	F	G
P₁	Qtrans₁	2	0	2	3	5	1	0
	Qtrans₂	0	1	25	0	0	0	0
	Qtrans₃	0	0	0	0	10	1	0
	Qtrans₄	0	1	12	0	0	0	0
P₂	Qtrans₅	4	0	8	0	10	0	0
	Qtrans₆	0	0	4	3	0	1	0
	Qtrans₇	0	0	2	3	0	0	0
P₃	Qtrans₈	6	2	0	0	10	3	0
	Qtrans₉	4	0	0	4	0	0	3
	Qtrans₁₀	0	0	4	0	10	0	0

Table 1

An example of a temporal quantitative dataset.

It is used throughout this work to help explain the definitions. In the dataset, there are 10 transactions which consist of 7 items in total, denoted from A to G. There are three time periods, P₁ to P₃, in this example. Table 2 represents the profit table and Table 3 shows the minimum fuzzy utility thresholds of all the items. The membership functions of each item are shown in Figure 2.

Item	Profit
A	3
B	10
C	1
D	6
E	5
F	2
G	20

Table 2

The profit table.

Item	Minimum Threshold
A	0.25
B	0.4
C	0.3
D	0.5
E	0.25
F	0.25
G	0.3

Table 3

The minimum thresholds of all the items.

To explain the proposed TPM algorithm clearly, we offer the formal definitions for TFUMP_mmt as follows: Let a fuzzy region of an item is called a fuzzy item, and a fuzzy itemset is composed of one or more fuzzy items with the condition that no two fuzzy items are formed from an identical item. For example, A.Low, A.Middle, and A.High are three fuzzy items derived from the item A, and {A.Low, B.High} is a fuzzy itemset. Note that {A.Low, A.High} cannot be a fuzzy itemset since both of the fuzzy items come from the same item A.

1^st Definition: (The utility of a fuzzy item) The utility value u_ygl is defined as

uygl=fygl*vyg*Sg,

where the value f_ygl represents the l-th fuzzy region for an item, i_g in Qtrans_y, v_yg represents the quantity sold for i_g in Qtrans_y, and S_g is the unit profit for i_g.

In Table 1, for example, we can see that the item D in Qtrans₉ has a quantity of 4. Its unit profit is 6 from Table 2. From Figure 2, its quantity membership for R_D.Low is 0.66, for R_D.Middle is 0.33, and for R_D.High is 0. Thus, u_9,D.Low = 0.66 * 4 * 6 = 15.84, u_9,D.Middle = 0.33 * 4 * 6 = 7.92, and u_9,D.High = 0 * 4 * 6 = 0. As such, the utility values of all the fuzzy items for the example are shown in Table 4.

	A			B			C			D			E			F			G
TID	Low	Middle	High	Low	Middle	High	Low	Middle	High	Low	Middle	High	Low	Middle	High	Low	Middle	High	Low	Middle	High
	The Utility Value of Each Fuzzy Item
Qtrans₁	6	0	0	0	0	0	1	0	0	18	0	0	25	0	0	1	0	0	0	0	0
Qtrans₂	0	0	0	5	0	0	0	0	25	0	0	0	0	0	0	0	0	0	0	0	0
Qtrans₃	0	0	0	0	0	0	0	0	0	0	0	0	0	50	0	1	0	0	0	0	0
Qtrans₄	0	0	0	5	0	0	0	0	12	0	0	0	0	0	0	0	0	0	0	0	0
Qtrans₅	0	12	0	0	0	0	0	8	0	0	0	0	0	50	0	0	0	0	0	0	0
Qtrans₆	0	0	0	0	0	0	4	0	0	18	0	0	0	0	0	1	0	0	0	0	0
Qtrans₇	0	0	0	0	0	0	1	0	0	18	0	0	0	0	0	0	0	0	0	0	0
Qtrans₈	0	0	12	20	0	0	0	0	0	0	0	0	0	50	0	3	3	0	0	0	0
Qtrans₉	0	12	0	0	0	0	0	0	0	15.84	7.92	0	0	0	0	0	0	0	30	30	0
Qtrans₁₀	0	0	0	0	0	0	4	0	0	0	0	0	0	50	0	0	0	0	0	0	0

Table 4

The utility values of all the fuzzy items in the example.

2^nd Definition: (Total utility in a transaction) The total utility tu_y of a transaction Qtrans_y is the sum of the utility values of all the fuzzy items in Qtrans_y. That is,

tuy=∑ig∈Qtransy∑l=1hguygl,

where h_g is the number of membership functions for i_g and u_ygl is the utility value of the fuzzy item R_gl derived from i_g.

Take, for example, Qtrans₈ in Table 4. We can get tu₈ = u_8,{A.High} + u_8,{B.Low} + u_8,{E.Middle} + u_8,{F.Low} + u_8,{F.Middle} = 12 + 20 + 50 + 3 + 3 = 88. The same process is done for the other transactions in Table 4. The resulting tu values of the 10 transactions are 51, 30, 51, 17, 70, 23, 19, 88, 95.76, and 54, respectively.

3^rd Definition: (The utility of a fuzzy itemset) The utility value of a fuzzy itemset X in Qtrans_y, represented as u_yX, is defined below:

uyX=fyX*∑Rgl∈Xvyg*Sg,

where f_yX is the integrated membership value of X in Qtrans_y and can be calculated as

MinRgl∈Xfygl,

where v_yg is the quantity sold for i_g in Qtrans_y and S_g is the profit value of i_g.

Applying the membership functions given in Figure 2, for instance, the membership values of the two fuzzy items A.Middle and D.Low in Qtrans₉ are 1 and 0.66, respectively. Therefore, the integrated membership value f_{9,{A.Middle, D.Low}} of the fuzzy itemset {A.Middle, D.Low} in Qtrans₉ is Min(1, 0.66), which is 0.66. The utility u_{9,{A.Middle, D.Low}} is then calculated as 0.66 * ((4 * 3) + (4 * 6)), which is 23.76.

4^th Definition: (The starting transactional period of an item) The starting transactional period of an item i_g in a database, denoted as stp(i_g), is the time period in which i_g first occurs in a database. For instance, the stp values of the two items D and G in Table 1 are P₁ and P₃, respectively.

5^th Definition: (The starting transactional period of an itemset) The starting transactional period of an itemset X in a database, denoted as stp(X), is defined as the latest starting transactional period of the items included in X. That is,

stpX=minTPstpig|ig∈X,X∈QTD,

where stp(i_g) is the starting time period of i_g and min_TP is the operator to get the lastest starting transactional period of the parameters attached.

Continuing the above example, the stp value of the itemset {D, G} in Table 1 is P₃.

6^th Definition: (The interval of transactional periods of an itemset) The interval of transactional periods of an itemset X, denoted ITP(X), includes the periods from stp(X) to the end of the database.

For example, ITP({D}) in Table 1 is from P₁ to the end. It thus includes {P₁, P₂, P₃}. As another example, ITP({D, G}) is {P₃}.

7^th Definition: (The starting transactional period of all items) The starting transactional period of all items I in a database, denoted stp(I), is defined as the latest starting transactional period of all items in I. That is,

stpI=minTPstpig|ig∈I,I∈QTD,

where stp(i_g) is the starting time period of i_g and min_TP is the operator to get the lastest starting transactional period of the parameters attached.

For instance, in Table 1, the starting transactional period of item G is P₃, and that of all the other items in I is P₁. Therefore, stp(I) is P₃.

8^th Definition: (The interval of transactional periods of all items) The interval of transactional periods of all items I, denoted ITP(I), includes intervals from stp(I) to the end of the database.

Continuing the above example, ITP(I) in Table 1 is {P₃}.

9^th Definition: (Maximal utility of an item) The maximal utility of an item i_g in Qtrans_y, denoted as mu_yg, is defined as the maximum utility value among all the fuzzy regions of i_g.

For instance, the three utility values of D.Low, D.Middle, and D.High derived from item D in Trans₉ from Table 4 are 15.84, 7.92, and 0, respectively. According to the above definition, the mu_9,{D} value of item {D} in Qtrans₉ is 15.84.

10^th Definition: (Maximal utility in a transaction) The maximal utility of a transaction Qtrans_y, denoted as mut_y, is computed as follows:

muty=∑ig⊆Qtransymuyg,

where mu_yg is the maximal utility value of item i_g in Qtrans_y.

For instance in Qtrans₉ from Table 4, mut₉ = mu_9,{A}+ mu_9,{D} + mu_9,{G} = 12 + 15.84 + 30 = 57.84. The same process is done for the other transactions in Table 4. The mut values of the 10 transactions are 51, 30, 51, 17, 70, 23, 19, 85, 57.84, and 54, respectively.

11^th Definition: (Temporal fuzzy utility upper-bound ratio for a fuzzy itemset) The temporal fuzzy utility upper-bound ratio of a fuzzy itemset X, denoted tfuubr_X, is computed as the following formula:

tfuubrX=∑X∈Qtransy∩Qtransy∈ITPXmutyX/∑Qtransy∈ITPItuy,

where mut_yX is the maximal utility value of a fuzzy itemset X in Qtrans_y and tu_y represents the total utility of a transaction Qtrans_y.

For instance, the tfuubr value of the itemset {B.Low} in Table 4 is calculated as tfuubr_{B.Low} = (mut₂ + mut₄ + mut₈) / (tu₁ + tu₂ + tu₃ + tu₄ + tu₅ + tu₆ + tu₇ + tu₈ + tu₉ + tu₁₀) = (30 + 17 + 91) / (51 + 30 + 51 + 17 + 70 + 23 + 19 + 88 + 95.76 + 54) = 138 / 498.76, which is 0.2766.

12^th Definition: (High temporal fuzzy utility upper-bound itemset under a single-conditional threshold) Given a single minimum threshold λ, a fuzzy itemset X is a high temporal fuzzy utility upper-bound itemset under the single condition if tfuubr_X ≥ λ.

Continuing the above example, if the minimum threshold λ is set at 0.26, {B.Low} is a high temporal fuzzy utility upper-bound 1-itemset.

As mentioned above, in real-world applications, a single-conditional measurement may not suffice to reflect the different importance of items. To solve this problem, different minimum thresholds should be used for different items. The extended upper-bound model is thus proposed as follows:

13^th Definition: (Minimum threshold for an itemset) Let λ_g be the minimum threshold of an item i_g. The minimum threshold of an itemset X, denoted as λ_X, is defined as min{λ₁, λ₂, …, λ_|X|}, where |X| is the number of items in X.

14^th Definition: (High temporal fuzzy utility upper-bound itemset under multi-conditional minimum thresholds) Given a set of minimum thresholds {λ₁, λ₂, …, λ_|X|} for different items in a fuzzy itemset X, X is a high temporal fuzzy utility upper-bound itemset under multi-conditional minimum thresholds (abbreviated as HTFUUBI) if tfuubr_X ≥ λ_X.

15^th Definition: (Temporal fuzzy utility ratio under multi-conditional minimum thresholds) The temporal fuzzy utility ratio for a fuzzy itemset X under multi-conditional minimum thresholds in QTD, denoted as tfur_X, is computed as the following formula:

tfurX=∑X∈Qtransy∩Qtransy∈ITPXuyx/∑Qtransy∈ITPXtuy,

where u_yX is the utility value of a fuzzy itemset X in Qtrans_y and tu_y represents the total utility of a Qtrans_y.

For example, the {C.Low, D.Low} is an HTFUUBI in Table 4. Its temporal fuzzy utility ratio, tfur_{{C.Low, D.Low}} can be calculated as follows: Its ITP_{{C.Low, D.Low}} is from P₁ to P₃, which includes all the 10 transactions. The total tu value in the 10 transactions is calculated as 498.76 (= 51 + 30 + 51 + 17 + 70 + 23 + 19 + 88 + 95.76 + 54). In addition, since the itemset {C.Low, D.Low} appears in Trans₁, Trans₆, and Trans₇, according to the third definition, the utility value of {C.Low, D.Low} is calculated as 42 (= 0.5 * (2 * 1 + 3 * 6) + 1*(4 * 1 + 3 * 6) + 1 * (2 * 1 + 3 * 6)). The tfur value of {C.Low, D.Low} is thus 0.0842 (= 42 / 498.76).

16^th Definition: (HTFUI under multi-conditional minimum thresholds) A fuzzy itemset X is a HTFUI (abbreviated as HTFUI) under multi-conditional minimum thresholds if tfur_X≥ λ_X.

Problem Statement: The problem to be solved is based on the above mentioned concept: to find all HTFUIs from a given QTD under multi-conditional minimum thresholds.

3.3. The TPM Algorithm for Temporal Fuzzy Utility Mining

The TPM algorithm is proposed to mine HTFUIs under multi-conditional minimum thresholds. It is applied with the two main phases shown in Figure 1 in Section 3.1. The first phase mainly finds out all high upper-bound itemsets (HTFUUBI) by checking whether their tfuubr values are not smaller than the corresponding minimum thresholds. If an itemset is smaller than its derived minimum threshold, it is pruned and not used to generate larger candidate itemsets. Then in the second phase, the tfur values of the HTFUUBIs found in the first phase are calculated and the ones satisfying tfur_X≥ λ_X are put in the set of HTFUIs. The pseudocode of the proposed TPM algorithm is briefly shown in Algorithm 1. The PRE-PROCESS is a procedure to handle the fuzzy transformation of the database for use in later mining process (Line 1). The variable HTFUUBI_all which put all derived high upper-bound itemsets, initially set to (Line 2). Then, the FIND-ONE-ITEM-HTFUUBI procedure is called to find out the HTFUUBI₁ itemsets, each of which contains only one item, and are then added to the set of HTFUUBI_all (Lines 3–4). A variable r is initially set to 1 (Line 5), which is used to keep the number of items to be processed currently. Then, a while-loop is performed to generate all HTFUUBI itemsets in a level-wise manner starting from those of length 2 (Lines 6–12). In the beginning, the algorithm checks whether any itemsets in HTFUUBI 1-itemsets exist. If yes, the FIND-NEXT-HTFUUBI procedure is called with HTFUUBI_r as its input parameter to find the high upper-bound (r + 1)-itemsets HTFUUBI_r+1 (Line 7), which is then added into HTFUUBI_all. The variable r is then increased with 1, and the loop is executed again to find the HTFUUBI itemsets of length r + 1 until no new HTFUUBI itemsets are found (Lines 8–12). At last, the FIND-HTFUI procedure is invoked to check the actual tfur values of the itemsets in HTFUUBI_all for determining all the HTFUI itemsets (Line 13).

First, a preprocessing procedure is built to transform the occurrence time of each transaction to a time period and to covert the quantitative information of the database to fuzzy regions. The procedure is shown in Algorithm 2, in which the procedure of ConvertToFuzzyRegion will transfer each transaction into fuzzy representation according to the given membership functions.

Next, in Line 3 of the main program, all the upper-bound 1-itemsets (HTFUUBI₁) are generated by the procedure of FIND-ONE-ITEM-HTFUUBI, which is shown in Algorithm 3 below. And then, in Line 7 of the main program, all the upper-bound (r + 1)-itemsets (HTFUUBI_r+1) are generated by the procedure of FIND-NEXT-HTFUUBI, which is shown in Algorithm 4 below.

Algorithm 1: The TPM method.

Input: QTD, a quantitative transaction dataset with items I = {i₁, i₂, …, i_n}, an item profit set S = {S₁, S₂, …, S_n}, multiple minimum thresholds λ = {λ₁, λ₂, …, λ_n}, time periods P = {P₁, P₂, …, P_m}, and membership functions MF.

Output: Finding out all the HTFUIs.

1. PRE-PROCESS( );

2. HTFUUBI_all = ø

3. HTFUUBI₁ = FIND-ONE-ITEM-HTFUUBI( );

4. HTFUUBI_all = HTFUUBI_all + HTFUUBI₁;

5. Set r = 1;

6. WHILE HTFUUBI_r <> ø DO:

7. HTFUUBI_r+1 = FIND-NEXT-HTFUUBI(HTFUUBI_r);

8. IF HTFUUBI_r+1 <> ø THEN

9. HTFUUBI_all = HTFUUBI_all + HTFUUBI_r+1;

10. END IF

11. r + = 1;

12. END WHILE

13. HTFUI = FIND-HTFUI(HTFUUBI_all);

Algorithm 2: Preprocessing data.

**Preprocessing data for time periods and fuzzy regions**

PROCEDURE PRE-PROCESS( )

14. FOR each transaction Qtrans_y in QTD Do:

15. Obtain the time period of Qtrans_y;

16. END FOR

17. FOR each item i_g Do:

18. Find the starting transactional time period stp(i_g);

// Using the 4th definition and will be used in Algorithm 3

19. END FOR

20. Sort items in QTD in descending order of their minimum thresholds as SQTD;

21. FOR each sorted transaction Qtrans_y in SQTD Do:

22. Qtrans_y = ConvertToFuzzyRegion(Qtrans_y, MF);

// Qtrans_y thus includes the fuzzy terms after this step

23. END FOR

24. FOR each transaction Qtrans_y in SQTD Do:

25. FOR each fuzzy region R_ygl in Qtrans_y Do:

26. Find u_ygl value for each fuzzy region; // Using the 1st definition

27. END FOR

28. END FOR

END PROCEDURE

Finally, the second phase of the proposed approach checks all the upper-bound itemsets derived from Algorithms 3 and 4 for whether they satisfy the corresponding thresholds. If so, they are put in HTFUIs, which are to be found. The procedure is given in Algorithm 5 below.

4. AN ILLUSTRATIVE EXAMPLE

An example is given to find HTFUIs in QTD under multiple minimum constraints by applying the proposed TPM algorithm. The algorithm proceeds as follows:

Algorithm 3: Finding HTFUUBI₁ itemsets.

** Finding out all the high temporal fuzzy utility upper-bound 1-itemsets under multi-conditional minimum thresholds**

PROCEDURE FIND-ONE-ITEM-HTFUUBI( )

29. FOR each item i_g of a transaction Qtrans_y in SQTD Do:

30. Calculate the mu_yg value of i_g; // Using the 9th definition

31. END FOR

32. FOR each transaction Qtrans_y in SQTD Do:

33. Get the mut_y of Qtrans_y; // Using the 10th definition

34. Get the tu_y value of Qtrans_y; // Using the 2nd definition

35. END FOR

36. stp(I) = min_TP{st(i_g)| i_g ∈ I}; Find ITP(I), includes intervals from stp(I) to the end of QTD; //Using the 7th and 8th definitions

37. λ_min,1 = min{λ(i_g)| i_g ∈ I};

// find out the minimum threshold among minimum thresholds of the items λ in the set of all items I

38. FOR each transaction Qtrans_y in ITP(I) Do:

39. numTransTotalUtility = numTransTotalUtility + tu_y;

40. END FOR

41. HTFUUBI₁ = ø

42. FOR each fuzzy region R_ygl Do:

43. mut_ygl = 0;

44. FOR each transaction Qtrans_y in SQTD Do:

45. IF R_ygl has existed in Qtrans_y THEN

46. mut_ygl = mut_ygl + mut_y;

47. END IF

48. END FOR

49. tfuubr = mut_ygl / numTransTotalUtility; // Using the 11th definition

50. IF tfuubr >= _min,1 Then // Using the 14th definition

51. HTFUUBI₁ = HTFUUBI₁ ∪ R_ygl;

52. END IF

53. END FOR

END PROCEDURE

Phase 1: Finding all high upper-bound itemsets (HTFUUBIs)

Line 1: The function of PRE-PROCESS is executed. The following steps are shown in Algorithm 2.

Lines 14–16: According to the user's need, the time duration of the quantitative transaction database QTD is partitioned into specific-length time periods. Assume the transaction time has been converted beforehand in Table 1.

Lines 17–19: The starting transactional period of each item is found in Table 1, and the results are shown in Table 5.

Item	stp
A	P₁
B	P₁
C	P₁
D	P₁
E	P₁
F	P₁
G	P₃

Table 5

The stp values of all items.

Line 20: Assume there is a QTD including seven items (denoted as A to G), and the minimum threshold values of the seven items are 0.25, 0.4, 0.3, 0.5, 0.25, 0.25, and 0.3, respectively. In this step, each item in the quantitative transaction database QTD needs to be sorted. Assume the results for the Sorted Quantitative Transactions (SQTD) are shown in Table 6.

Period	TID	D	B	C	G	A	E	F
P₁	Qtrans₁	3	0	2	0	2	5	1
	Qtrans₂	0	1	25	0	0	0	0
	Qtrans₃	0	0	0	0	0	10	1
	Qtrans₄	0	1	12	0	0	0	0
P₂	Qtrans₅	0	0	8	0	4	10	0
	Qtrans₆	3	0	4	0	0	0	1
	Qtrans₇	3	0	2	0	0	0	0
P₃	Qtrans₈	0	2	0	0	6	10	3
	Qtrans₉	4	0	0	3	4	0	0
	Qtrans₁₀	0	0	4	0	0	10	0

Table 6

The SQTD in this example.

Algorithm 4: Finding HTFUUBI_r+1 itemsets.

**Finding out all the high temporal fuzzy utility upper-bound (r + 1)-itemsets under multi-conditional minimum thresholds**

PROCEDURE FIND-NEXT-HTFUUBI (HTFUUBI_r)

54. HTFUUBI_r+1 = ø

55. C_r+1 = generateCandidate(HTFUUBI_r);

56. FOR each itemset x in C_r+1 Do:

57. IF all the r-sub-itemsets of x exist in HTFUUBI_r Then

58. HTFUUBI_r+1 = HTFUUIB_r+1 ∪ x;

59. END IF

60. END FOR

61. λ_min,r+1 = min{λ(i_g)| i_g ∈ C_r+1};

// find out the minimum threshold among minimum thresholds of the items λ in the set of the items C_r+1;

62. FOR each transaction Qtrans_y in ITP(I) Do:

63. numTransTotalUtility = numTransTotalUtility + tu_y;

64. END FOR

65. FOR each itemset x in HTFUUBI_r+1 Do:

66. mut_x = 0;

67. FOR each transaction Qtrans_y in SQTD Do:

68. IF all the r-sub-itemsets of x exist in Qtrans_y THEN

69. mut_x = mut_x + mut_y;

70. END IF

71. END FOR

72. tfuubr = mut_x / numTransTotalUtility; // Using the 11th definition

73. IF tfuubr < λ_min,r+1 Then // Using the 14th definition

74. Remove x in HTFUUB_r+1;

75. END IF

76. END FOR

END PROCEDURE

Algorithm 5: Finding HTFUIs itemsets.

**Finding out all the HTFUIs under multi-conditional minimum thresholds**

PROCEDURE FIND-HTFUI(HTFUUBI_all)

77. FOR each itemset x in HTFUUBI_all Do:

78. Find ITP(x), which includes the intervals from stp(x) to the end of QTD

// Using the 5th and 6th definitions

79. FOR each transaction Qtrans_y in ITP(x) Do:

80. numTransTotalUtility_x = numTransTotalUtility_x + tu_y;

81. END FOR

82. Calculate the utility u_x value of each itemset in SQTD; // Using the 3rd definition

83. λ_min,x = min{λ(i_g)| i_g ∈ x}; // find out the minimum threshold among minimum thresholds of the items λ in the set of the items x

84. tfur_x = u_x / numTransTotalUtility_x; // Using the 15th definition

85. IF tfur_x >= λ_min,x Then // Using the 16th definition

86. HTFUIs = HTFUI_S ∪ x;

87. END IF

88. END FOR

END PROCEDURE

Lines 21–23: By applying the membership functions of the items, the quantity value for each item in SQTD is converted into a specific fuzzy set. Take the ninth quantitative transaction, Qtrans₉, in Table 6 as an instance. It includes three items (quantity values), D(4), G(3), and A(4), respectively. By applying the membership functions, which is given in Figure 1, their quantity values are transformed into the three fuzzy sets (0.66/D.Low + 0.33/D.Middle + 0/D.High), (0.5/G.Low + 0.5/G.Middle + 0/G.High), and (0/A.Low + 1/A.Middle + 0/A.High), respectively. The results for all the quantitative transactions in Table 6 are shown in Table 7.

TID	Linguistic Representation
Qtrans₁	1D.Low,0D.Middle,0D.High0.5C.Low,0C.Middle,0C.High1A.Low,0A.Middle,0A.High 1E.Low,0E.Middle,0E.High0.5F.Low,0F.Middle,0F.High
Qtrans₂	0.5B.Low,0B.Middle,0B.High0C.Low,0C.Middle,1C.High
Qtrans₃	0E.Low,1E.Middle,0E.High0.5F.Low,0F.Middle,0F.High
Qtrans₄	0.5B.Low,0B.Middle,0B.High0C.Low,0C.Middle,1C.High
Qtrans₅	0C.Low,1C.Middle,0C.High0A.Low,1A.Middle,0A.High0E.Low,1E.Middle,0E.High
Qtrans₆	1D.Low,0D.Middle,0D.High1C.Low,0C.Middle,0C.High0.5F.Low,0F.Middle,0F.High
Qtrans₇	1D.Low,0D.Middle,0D.High0.5C.Low,0C.Middle,0C.High
Qtrans₈	1B.Low,0B.Middle,0B.High0A.Low,0A.Middle,1A.High 0E.Low,1E.Middle,0E.High0.5F.Low,0.5F.Middle,0F.High
Qtrans₉	0.66D.Low,0.33D.Middle,0D.High0.5G.Low,0.5G.Middle,0G.High0A.Low,1A.Middle,0A.High
Qtrans₁₀	1C.Low,0C.Middle,0C.High0E.Low,1E.Middle,0E.High

Table 7

The converted linguistic representation of the transactions in Table 6.

Lines 24–28: For each transaction in Table 6, find out the utility values of the fuzzy regions for each item. Take the item G in the ninth transaction (Qtrans₉) in Table 6 as an example. The quantity and the profit for the item G in Qtrans₉ are 3 and 20. Moreover, the membership values of the three fuzzy regions (G.Low, G.Middle, G.High) for the item G are 0.5, 0.5, and 0. The utility values can be calculated as 0.5 * 3 * 20 (= 30), 0.5 * 3 * 20 (= 30), and 0 * 3 * 20 (= 0), respectively. The same process can be executed for the remaining items. The results for the utility of the 10 transactions in this example are shown in Table 8. Note that “Low,” “Middle,” and “High” in Table 8 are simplified as “L,” “M,” and “H.” Next, the following steps are in Algorithm 1.

TID	D			B			C			G			A			E			F			mut
TID		L	M	H	L	M	H	L	M	H	L	M	H	L	M	H	L	M	H	L	M	mut	H
Qtrans₁	18	0	0	0	0	0	1	0	0	0	0	0	6	0	0	25	0	0	1	0	0	51
Qtrans₂	0	0	0	5	0	0	0	0	25	0	0	0	0	0	0	0	0	0	0	0	0	30
Qtrans₃	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	50	0	1	0	0	51
Qtrans₄	0	0	0	5	0	0	0	0	12	0	0	0	0	0	0	0	0	0	0	0	0	17
Qtrans₅	0	0	0	0	0	0	0	8	0	0	0	0	0	12	0	0	50	0	0	0	0	70
Qtrans₆	18	0	0	0	0	0	4	0	0	0	0	0	0	0	0	0	0	0	1	0	0	23
Qtrans₇	18	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	19
Qtrans₈	0	0	0	20	0	0	0	0	0	0	0	0	0	0	18	0	50	0	3	3	0	91
Qtrans₉	15.84	7.92	0	0	0	0	0	0	0	30	30	0	0	12	0	0	0	0	0	0	0	57.84
Qtrans₁₀	0	0	0	0	0	0	4	0	0	0	0	0	0	0	0	0	50	0	0	0	0	54

Table 8

The utility of each fuzzy region in Table 6.

Lines 2–4: The function of FIND-ONE-ITEM-HTFUUBI is executed. The following steps are in Algorithm 3.

Lines 29–35: The mu value of each item in a transaction is found and then the mut value of each transaction in Table 8 is calculated. Using the ninth transaction Qtrans₉ as an example, the mu value of the item D is 15.8 from D.L. Similarly, the mu values of the two items G and A are 30 and 12, respectively, from G.L and A.M. The mut value of Qtrans₉ is then calculated as 15.84 + 30 + 12, which is 57.84. All the other transactions can be handled in the same way and the mut values of the remaining transactions are shown in the last column of Table 8.

The tu value of a transaction is calculated. Using the example of the ninth transaction Qtrans₉ in Table 8, the fuzzy regions with nonzero utility values are D.L, D.M, G.L, G.M, and A.M. The tu value of Qtrans₉ is thus calculated as 15.84 + 7.92 + 30 + 30 + 12, which is 95.76. The rest can be processed in the same way.

Line 36: According to the 7th definition, the starting transactional period stp(I) = min{st(i_A), st(i_B), st(i_C), st(i_D), st(i_E), st(i_F), st(i_G)} = min{P₁, P₁, P₁, P₁, P₁, P₁, P₃} = P₃. Then, ITP(I) represents a duration of time periods from P₃ to the end, which is still P₃ in the example.

Line 37: Table 8 includes seven items and Table 3 has the corresponding minimum thresholds for all the items, which are 0.25 (A), 0.4 (B), 0.3 (C), 0.5 (D), 0.25 (E), 0.25 (F), and 0.3 (G), respectively. Thus, the minimum value λ_min,1 among the seven minimum thresholds is 0.25.

Lines 38–40: In Line 37, ITP(I) is {P₃}. The third period, P₃, includes three transactions, Qtrans₈, Qtrans₉, and Qtrans₁₀, which have the tu values of 94, 95.76, and 54, respectively. The variable numTransTotalUtility is calculated as 94 + 95.76 + 54, which is 243.76.

Line 41: The variable HTFUUBI₁ is assigned as ø.

Lines 42–53: After this step, all the upper-bound 1-itemsets are found. Take the 1-itemset {D.Low} in Table 8 as an example. It appears in Qtrans₁, Qtrans₆, Qtrans₇, and Qtrans₉, and its mut values in the four transactions are 51, 23, 19, and 57.84, respectively. Its upper-bound value is calculated as 51 + 23 + 19 + 57.84 (= 150.84). The results are shown in Table 9.

Fuzzy Itemset	UB	Fuzzy Itemset	UB
D.Low	150.84	G.High	0
D.Middle	57.84	A.Low	51
D.High	0	A.Middle	127.84
B.Low	138	A.High	91
B.Middle	0	E.Low	51
B.High	0	E.Middle	266
C.Low	147	E.High	0
C.Middle	70	F.Low	216
C.High	47	F.Middle	91
G.Low	57.84	F.High	0
G.Middle	57.84

Table 9

The 1-itemsets with upper-bound values.

Therefore, the tfuubr value of {D.Low} is 150.84/243.76, which is 0.6188. Since it is larger than the minimum value λ_min,1 (0.25), the fuzzy item, {D.Low}, is put into the set of HTFUUBI₁. The results after the check are shown in Table 10. The following steps are in Algorithm 1.

1-Itemset	1-Itemset
D.Low	A.High
B.Low	E.Middle
C.Low	F.Low
C.Middle	F.Middle
A.Middle

Table 10

The HTFUUBI₁ Table.

Line 5: The variable r is assigned as 1.

Line 6: All the upper-bound 1-itemsets in Table 10 are found.

Line 7: The function of FIND-NEXT-HTFUUBI is executed. The following steps are in Algorithm 4.

Line 54: The variable HTFUUBI_r+1 is assigned as ø.

Line 55: The Apriori-like algorithm is used to generate the candidate itemsets. For example, thirty-three candidate 2-itemsets are produced from the set of HTFUUBI₁. The results are shown in Table 11. Note that a valid utility itemset cannot contain two fuzzy regions from the same item. For example, {C.Low, C.Middle} is invalid.

2-Itemset	2-Itemset	2-Itemset	2-Itemset
D.Low, B.Low	B.Low, C.Middle	C.Low, F.Low	A.Middle, F.Middle
D.Low, C.Low	B.Low, A.Middle	C.Low, F.Middle	A.High, E.Middle
D.Low, C.Middle	B.Low, A.High	C.Middle, A.Middle	A.High, F.Low
D.Low, A.Middle	B.Low, E.Middle	C.Middle, A.High	A.High, F.Middle
D.Low, A.High	B.Low, F.Low	C.Middle, E.Middle	E.Middle, F.Low
D.Low, E.Middle	B.Low, F.Middle	C.Middle, F.Low	E.Middle, F.Middle
D.Low, F.Low	C.Low, A.Middle	C.Middle, F.Middle
D.Low, F.Middle	C.Low, A.High	A.Middle, E.Middle
B.Low, C.Low	C.Low, E.Middle	A.Middle, F.Low

Table 11

All the candidate 2-itemsets in this example.

Lines 56–60: Check each candidate 2-itemset in Table 11. All of its 1-sub-itemsets are checked for whether each 1-sub-itemset exists in the set of HTFUUBI₁ or not. For example, {D.Low, B.Low}, includes the two 1-sub-itemsets, D.Low and B.Low, both of which appear in HTFUUBI₁. Hence, {D.Low, B.Low} can be put into the set of HTFUUBI₂.

Line 61: The minimum threshold λ_min in the second pass is found. There are six distinct items in Table 11 includes D, B, C, A, E, and F. According to theirs minimum thresholds, the λ_min,2 is 0.25 and is used for finding the set of HTFUUBI₂.

Lines 62–64: Like in Lines 38–40, the variable numTransTotalUtility is calculated as 94 + 95.76 + 54, which is 243.76.

Lines 65–76: The required upper-bound value of each candidate 2-itemset in Table 11 is found by scan. Use the 2-itemset {D.Low, C.Low} as an instance. D.Low and C.Low simultaneously appear in the three transactions: Trans₁, Trans₆, and Trans₇ in Table 8. Its upper-bound value is mut₁ + mut₆ + mut₇, which is 51 + 23 + 19 (= 93). The results of all the candidate 2-itemsets are shown in Table 12.

2-Itemset	UB	2-Itemset	UB	2-Itemset	UB	2-Itemset	UB
D.Low, B.Low	0	B.Low, C.Middle	0	C.Low, F.Low	74	A.Middle, F.Middle	0
D.Low, C.Low	93	B.Low, A.Middle	0	C.Low, F.Middle	0	A.High, E.Middle	91
D.Low, C.Middle	0	B.Low, A.High	91	C.Middle, A.Middle	70	A.High, F.Low	91
D.Low, A.Middle	57.84	B.Low, E.Middle	91	C.Middle, A.High	0	A.High, F.Middle	91
D.Low, A.High	0	B.Low, F.Low	91	C.Middle, E.Middle	70	E.Middle, F.Low	142
D.Low, E.Middle	0	B.Low, F.Middle	91	C.Middle, F.Low	0	E.Middle, F.Middle	91
D.Low, F.Low	74	C.Low, A.Middle	0	C.Middle, F.Middle	0
D.Low, F.Middle	0	C.Low, A.High	0	A.Middle, E.Middle	70
B.Low, C.Low	0	C.Low, E.Middle	54	A.Middle, F.Low	0

Table 12

The candidate 2-itemsets with upper-bound values.

Fuzzy Itemset	Fuzzy Itemset	Fuzzy Itemset
{D.Low, C.Low}	{B.Low, F.Middle}	{A.High, E.Middle}
{D.Low, F.Low}	{C.Low, F.Low}	{A.High, F.Low}
{B.Low, A.High}	{C.Middle, A.Middle}	{A.High, F.Middle}
{B.Low, E.Middle}	{C.Middle, E.Middle}	{E.Middle, F.Low}
{B.Low, F.Low}	{A.Middle, E.Middle}	{E.Middle, F.Middle}

Table 13

The HTFUUBI₂ Table.

Fuzzy Itemset	Fuzzy Itemset	Fuzzy Itemset	Fuzzy Itemset
D.Low	{D.Low, C.Low}	{A.Middle, E.Middle}	{B.Low, A.High, F.Middle}
B.Low	{D.Low, F.Low}	{A.High, E.Middle}	{B.Low, E.Middle, F.Low}
C.Low	{B.Low, A.High}	{A.High, F.Low}	{B.Low, E.Middle, F.Middle}
C.Middle	{B.Low, E.Middle}	{A.High, F.Middle}	{C.Middle, A.Middle, E.Middle}
A.Middle	{B.Low, F.Low}	{E.Middle, F.Low}	{A.High, E.Middle, F.Low}
A.High	{B.Low, F.Middle}	{E.Middle, F.Middle}	{A.High, E.Middle, F.Middle}
E.Middle	{C.Low, F.Low}	{D.Low, C.Low, F.Low}
F.Low	{C.Middle, A.Middle}	{B.Low, A.High, E.Middle}
F.Middle	{C.Middle, E.Middle}	{B.Low, A.High, F.Low}

Table 14

The HTFUUBI_all Table.

Use the fuzzy 2-itemset {D.Low, C.Low} in Table 12 as an instance. The tfuubr value of {D.Low, C.Low} is 93/243.76, which is 0.3815. Since it is larger than the minimum value λ_min,2 (0.25), the fuzzy 2-itemset, {D.Low, C.Low}, is still kept in the set HTFUUBI₂. The results are shown in Table 13. The following steps are in Algorithm 1.

Lines 8–11: Since the set HTFUUBI₂ is not empty, the HTFUUBI₂ itemsets are added to the set of HTFUUBI_all. The variable r is then increased to 2 and the process in Lines 6 to 12 is executed again for the set of HTFUUBI₃ and HTFUUBI₄. Since HTFUUBI₄ is empty, Line 13 will be executed.

Phase 2: Finding all HTFUIs

Line 13: The function of FIND-HTFUI is executed. The following steps are in Algorithm 5.

Lines 77–88: The required tfur value of each item in HTFUUBIs is found by scan in this step. The HTFUUBI_all table, which puts the high temporal fuzzy utility upper-bound itemsets under multi-conditional minimum thresholds, includes thirty-three upper-bound itemsets listed in Table 14.

For {D.Low, C.Low} in the HTFUUBI_all table, its stp value is P₁. The interval ITP_{{D.Low, C.Low}} of the transactional periods of {D.Low, C.Low}, thus includes {P₁, P₂, P₃}. Therefore, numTransTotalUtility_{{D.Low, C.Low}} is calculated as tu₁ + tu₂ + … + tu₁₀ = 51 + 30 + 51 + 17 + 70 + 23 + 19 + 94 + 95.76 + 54 = 504.76.

From Table 7, the membership values of the two fuzzy terms, D.Low and C.Low, in the fuzzy 2-itemset {D.Low, C.Low} in Qtrans₁, Qtrans₆, and Qtrans₇ are {1, 0.5}, {1, 1}, and {1, 0.5}, respectively. By applying the minimum operator, the membership values for the 2-itemset {D.Low, C.Low} in Qtrans₁, Qtrans₆, and Qtrans₇ are thus 0.5, 1 and 0.5, respectively. The u_{{D.Low, C.Low}} value can thus be calculated as 0.5 * [(3 * 6) + (2 * 1)] + 1 * [(3 * 6) + (4 * 1)] + 0.5 * [(3 * 6) + (2 * 1)] (= 42).

For Table 3, the minimum thresholds of D and C are 0.5 and 0.3, respectively. So the minimum value λ_{{D.Low, C.Low}} = min(0.5, 0.3), which is 0.3.

From the above results, tfur_{{D.Low, C.Low}} = 42/504.76 = 0.083. Since it is smaller than the minimum value λ_{{D.Low, C.Low}}, {D.Low, C.Low} is not put into HTFUIs. The final results are shown in Table 15 after the remaining itemsets are checked. In this example, only one fuzzy itemset {E.Middle} satisfies the conditions.

Fuzzy Itemset	Utility
E.Middle	200

Table 15

The final set of HTFUIs in the example.

5. EXPERIMENTAL RESULTS

The three synthetic datasets (T10N1KD200K, T10N3KD200K, and T10N5KD200K) produced from the IBM data generator [32] were conducted to make a comparison of the proposed TPM, which is for multi-conditional minimum thresholds, and the traditional TFUM [18], which is for a single conditional minimum threshold. The OS was Windows 7, and all the programs were implemented in Java, run in J2SDK 1.8.0 and executed on a PC with 3.2 GHz CPU and 8GB memory.

Since our purpose is to find HTFUIs from quantitative databases, a simulation model, which is similar to that used in [18], is used to generate the quantities varying from 1 to 10. The relevant parameters, D, N, and T stand for the number of transactions, the total number of different items, and the average length of items per transaction, respectively. Besides, for the three synthetic datasets produced, the relevant profits are produced ranging from 0.01 to 10.00. A profit value is randomly assigned to an item, and also a minimum threshold table is produced in which a threshold value is randomly assigned to each item.

A user-specified threshold λ_DIFF is set to produce the minimum threshold of each item in the range from λ_DIFF to 1.0 in the multi-conditional temporal fuzzy utility mining problem. Besides, λ_DIFF is also considered as the single minimum threshold λ_min for temporal fuzzy utility mining.

5.1. Evaluation of the Effectiveness of Phase 1 in the Two Methods

Experiments were first done for comparing the execution time and the numbers of upper-bound itemsets under a single minimum threshold and under multiple minimum thresholds. We compare various N values for the three T4NxKD200K datasets. Figures 3–5 show the execution time along with various λ_DIFF values for the three datasets. Here the symbol λ_DIFF represents the lower bound of the minimum thresholds of all the items in databases and can be regarded as the minimum threshold, λ_min, in TFUM, which uses only a single minimum utility threshold.

Note that in Figures 3 and 4, the y-axis use log-scale. Figures 6–8 show the numbers of upper-bound itemsets along with various λ_DIFF values for the three datasets. Similarly in Figures 6–8, the y-axis use log-scale.

It could be observed from these figures that the execution time and the numbers of high upper-bound itemsets derived by our proposed TPM algorithm were less than those of TFUM using only a single minimum standard. The main reason for this is that all the items in the traditional TFUM were treated uniformly. That is, it did not consider the different property of items, and thus the minimum threshold was the same for all items in a database. Compared to the traditional TFUM, the new algorithm considers different minimum standards for items. In other words, in the experiments, since the minimum standards of all the items were not smaller than the user-specified lower-bound, which was used as the single minimum fuzzy utility threshold in the traditional TFUM, the number of high utility itemsets derived by our proposed TPM algorithm must be less than or equal to that by the TFUM method. In addition, as mentioned in Line 37 of Algorithm 3 and Line 61 of Algorithm 4, the integrated minimum threshold would gradually increase when a larger number of items were included in an itemset at later passes during the process of finding high upper-bound itemsets (HTFUUBI).

5.2. Evaluation of Execution Efficiency for Phase 2 in the Two Methods

The same as before, the three synthetic datasets were conducted to assess the mining efficiency of the proposed TPM and the traditional TFUM for phase 2. Figures 9–11 show the execution efficiency of the two approaches (TPM and TFUM) for phase 2 under various λ_DIFF values. Figures 12–14 show the numbers of HTFUI itemsets of the two methods under various λ_DIFF values. Note that in Figures 9 and 10, the y-axis use log-scale.

It could be observed from these figures that the execution time of phase 2 and the numbers of HTFUI itemsets derived by our proposed TPM algorithm was less than those of TFUM using only a single minimum standard. Again, this is because all the items in the traditional TFUM were treated uniformly when compared to the TPM algorithm. That is, TFUM did not consider the different properties of items, and thus the minimum threshold was the same for all items in a database. However, the TPM algorithm considers different minimum standards for items. Thus, the traditional temporal fuzzy utility mining algorithm mined more HTFUIs than the proposed one. Hence, the proposed framework using multiple minimum constraints might be a proper framework where items had different minimum constraints. Besides, both the algorithms would get more high upper-bound itemsets when the minimum threshold was smaller.

5.3. Evaluation of Execution Efficiency for the Two Methods

The three datasets were conducted to assess the total mining efficiency of the two phases for the proposed TPM and the traditional TFUM. Figures 15–17 show the execution efficiency of the two approaches (TPM and TFUM) for the databases under various λ_DIFF values.

We could observe that the TPM approach was better than the traditional TFUM approach with a single threshold regarding execution efficiency when λ_DIFF increased. The main reason is that with the help of the minimum constraints, only the itemsets which satisfied their own minimum thresholds and not the lowest minimum threshold value for all items could be generated in the databases. Accordingly, the proposed TPM approach did not need to derive more itemsets than the traditional TFUM approach using only a single minimum threshold. Overall, the proposed TPM outperformed the traditional TFUM approach in execution efficiency under a variety of parameter settings.

The proposed TPM method can be thought of as a general algorithm for temporal fuzzy utility problem. When the multi-conditional thresholds for the proposed TPM method are identical for all items, TPM can be considered as the TFUM method. In this case, the TPM method with identical values may require a few more execution time than the TFUM method because the former needs to find itemset constraints.

6. CONCLUSION AND FUTURE WORK

This study proposes a new mining problem named temporal fuzzy utility mining with multi-conditional minimum thresholds, which goes further to consider the fuzzy viewpoint of applying the multiple minimum constraints of itemsets in a database when items have different standards. Different from the traditional temporal fuzzy utility mining with considering only a single minimum standard, the nature of items in our study can be reflected under different minimum thresholds. The experimental results also showed that our proposed TPM approach derived fewer itemsets than the TFUM approach and had good performance from both the effectiveness of multi-conditional viewpoint and the execution efficiency. Besides, the proposed TPM approach can be thought of as a generalized version of the previous TFUM approach and can execute the work that TFUM performs.

In the future, we will attempt to handle the maintenance problems of temporal fuzzy utility mining when new transactions are inserted, old transactions are modified even if overdue transactions are deleted.

REFERENCES

1.R. Agrawal, T. Imieliński, and A. Swami, Mining association rules between sets of items in large databases, in ACM SIGMOD International Conference on Management of Data (Washington), 1993, pp. 207-216.

2.R. Agrawal and R. Srikant, Fast algorithms for mining association rules in large databases, in The International Conference on Very Large Data Bases (San Francisco), 1994, pp. 487-499. https://dl.acm.org/citation.cfm?id=672836

3.F. Berzal, J.C. Cubero, N. Marín, and J.M. Serrano, TBAR: an efficient method for association rule mining in relational databases, Data Knowledge Eng., Vol. 37, 2001, pp. 47-64.

4.H. Yao, H.J. Hamilton, and C.J. Butz, A foundational approach to mining itemset utilities from databases, in The 4th SIAM International Conference on Data Mining (Lake Buena Vista, Florida, USA), 2004, pp. 482-486.

5.C.F. Ahmed, S.K. Tanbeer, B.S. Jeong, and Y.K. Lee, Efficient tree structures for high utility pattern mining in incremental databases, IEEE Trans. Knowledge Data Eng., Vol. 21, 2009, pp. 1708-1721.

6.C.F. Ahmed, S.K. Tanbeer, B.S. Jeong, and Y.K. Lee, HUC-Prune: an efficient candidate pruning technique to mine high utility patterns, Appl. Intell., Vol. 34, 2011, pp. 181-198.

7.A. Erwin, R.P. Gopalan, and N.R. Achthan, Achuthan, CTU-Mine: an efficient high utility itemset mining algorithm using the pattern growth approach, in The 7th IEEE International Conferences on Computer and Information Technology (Fukushima), 2007, pp. 71-76.

8.Y.C. Li, J.S. Yeh, and C.C. Chang, Isolated items discarding strategy for discovering high utility itemsets, Data Knowledge Eng., Vol. 64, 2008, pp. 198-217.

9.V.S. Tseng, C.W. Wu, P.F. Viger, and P.S. Yu, Efficient algorithms for mining the concise and lossless representation of high utility itemsets, IEEE Trans. Knowledge Data Eng., Vol. 27, 2015, pp. 726-739.

10.C.J. Chu, V.S. Tseng, and T. Liang, An efficient algorithm for mining high utility itemsets with negative item values in large databases, Appl. Math. Comput., Vol. 215, 2008, pp. 767-778.

11.G.C. Lan, T.P. Hong, and V.S. Tseng, Discovery of high utility itemsets from on-shelf time periods of products, Expert Syst. Appl., Vol. 38, 2011, pp. 5851-5857.

12.G.C. Lan, T.P. Hong, and V.S. Tseng, Reducing database scans for on-shelf utility mining, IETE Tech. Rev. Spec. Issue Adv. Soft Comput. Theory Appl., Vol. 28, 2011, pp. 103-112. https://www.tandfonline.com/doi/abs/10.4103/0256-4602.78090

13.G.C. Lan, T.P. Hong, J.P. Huang, and V.S. Tseng, On-shelf utility mining with negative item values, Expert Syst. Appl., Vol. 41, 2014, pp. 3450-3459.

14.C.W. Lin, G.C. Lan, and T.P. Hong, Mining high utility itemsets for transaction deletion in a dynamic database, Appl. Intell., Vol. 19, 2015, pp. 43-55.

15.C.W. Lin, G.C. Lan, and T.P. Hong, An incremental mining algorithm for high utility itemsets, Expert Syst. Appl., Vol. 39, No. 2012, pp. 7173-7180.

16.C.M. Wang, S.H. Chen, and Y.F. Huang, A fuzzy approach for mining high utility quantitative itemsets, in IEEE International Conference on Fuzzy Systems (Jeju Island), 2009.

17.G.C. Lan, T.P. Hong, Y.H. Lin, and S.L. Wang, Fuzzy utility mining with upper-bound measure, Appl. Soft Comput., Vol. 30, No. 2015, pp. 767-777.

18.W.M. Huang, T.P. Hong, G.C. Lan, M.C. Chiang, and J.C.W. Lin, Temporal-based fuzzy utility mining, IEEE Access, Vol. 5, 2017, pp. 26639–-26652.

19.T. Fukuda, Y. Morimoto, S. Morishita, and T. Tokuyama, Mining optimized association rules for numeric attributes, in ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (Quebec), 1996, pp. 182-191.

20.Y.H. Hu and Y.L. Chen, Mining association rules with multiple minimum supports: a new mining algorithm and a support tuning mechanism, Decis. Support Syst., Vol. 42, 2006, pp. 1-24.

21.H. Jiang, Y. Zhao, C. Yang, and X. Dong, Mining both positive and negative weighted association rules with multiple minimum supports, in The International Conference of Computer Science and Software Engineering (Hubei), 2008, pp. 407-410.

22.R. Uday Kiran and P. Krishna Reddy, Novel techniques to reduce search space in multiple minimum supports-based frequent pattern mining algorithms, in The 14th International Conference on Extending Database Technology (Uppsala), 2011, pp. 11-20.

23.B. Liu, W. Hsu, and Y. Ma, Mining association rules with multiple minimum supports, in The International Conference on Knowledge Discovery and Data Mining (San Diego), 1999, pp. 337-341.

24.C.H. Chen, T.P. Hong, V.S. Tseng, and C.S. Lee, A genetic-fuzzy mining approach for items with multiple minimum supports, Soft Comput., Vol. 13, 2008, pp. 521-533.

25.W. Ouyang and Q. Huang, Mining direct and indirect fuzzy association rules with multiple minimum supports in large transaction databases, in The 8th International Conference on Fuzzy Systems and Knowledge Discovery (Shanghai), Vol. 4, 2011, pp. 947-951.

26.J.C.W. Lin, W. Gan, P. Fournier-Viger, T.P. Hong, and J. Zhan, Efficient mining of high utility itemsets with multiple minimum utility thresholds, Knowledge Based Syst., Vol. 113, 2016, pp. 100-115.

27.Y.H. Hu and I.C. Chiang, Mining cyclic patterns with multiple minimum repetition supports, in The Eighth International Conference on Fuzzy Systems and Knowledge Discovery (Shanghai), 2011, pp. 1545-1549.

28.J. Han, J. Pei, and Y. Yin, Mining frequent patterns without candidate generation: a frequent-pattern tree approach, Data Mining Knowledge Discov., Vol. 8, 2004, pp. 53-87.

29.R. Chan, Q. Yang, and Y.D. Shen, Mining high utility itemsets, in The 3rd IEEE International Conference on Data Mining (Melbourne), 2003, pp. 19-26.

30.Q. Li, A novel Likert scale based on fuzzy sets theory, Expert Syst. Appl., Vol. 40, 2013, pp. 1609-1618.

31.I. Glöckner and A. Knoll, Fuzzy quantifiers: a natural language technique for data fusion, in The 4th International Conference on Information Fusion (Montreal QC, Canada), 2001.

32.IBM Quest Data Mining Project, Quest Synthetic Data Generation Code, 1996. http://www.almaden.ibm.com/cs/quest/syndata.html

<Previous Article In Issue

Download article (PDF)

Next Article In Issue>

Journal: International Journal of Computational Intelligence Systems
Volume-Issue: 12 - 2
Pages: 613 - 626
Publication Date: 2019/05/11
ISSN (Online): 1875-6883
ISSN (Print): 1875-6891
DOI: 10.2991/ijcis.d.190426.001 How to use a DOI?
Open Access: This is an open access article distributed under the CC BY-NC 4.0 license (http://creativecommons.org/licenses/by-nc/4.0/).

Cite this article

ris enw bib

TY  - JOUR
AU  - Wei-Ming Huang
AU  - Tzung-Pei Hong
AU  - Ming-Chao Chiang
AU  - Jerry Chun-Wei Lin
PY  - 2019
DA  - 2019/05/11
TI  - Using Multi-Conditional Minimum Thresholds in Temporal Fuzzy Utility Mining
JO  - International Journal of Computational Intelligence Systems
SP  - 613
EP  - 626
VL  - 12
IS  - 2
SN  - 1875-6883
UR  - https://doi.org/10.2991/ijcis.d.190426.001
DO  - 10.2991/ijcis.d.190426.001
ID  - Huang2019
ER  -

download .riscopy to clipboard

International Journal of Computational Intelligence Systems

Using Multi-Conditional Minimum Thresholds in Temporal Fuzzy Utility Mining

1. INTRODUCTION

2. RELATED WORKS

3. MINING TEMPORAL FUZZY UTILITY ITEMSETS WITH MULTI-CONDITIONAL MINIMUM THRESHOLDS

3.1. The Concept of the Proposed TPM Method

3.2. Formal Problem Definition

3.3. The TPM Algorithm for Temporal Fuzzy Utility Mining

Algorithm 1: The TPM method.

Algorithm 2: Preprocessing data.

4. AN ILLUSTRATIVE EXAMPLE

Algorithm 3: Finding HTFUUBI1 itemsets.

Algorithm 4: Finding HTFUUBIr+1 itemsets.

Algorithm 5: Finding HTFUIs itemsets.

5. EXPERIMENTAL RESULTS

5.1. Evaluation of the Effectiveness of Phase 1 in the Two Methods

5.2. Evaluation of Execution Efficiency for Phase 2 in the Two Methods

5.3. Evaluation of Execution Efficiency for the Two Methods

6. CONCLUSION AND FUTURE WORK

REFERENCES

Cite this article

Algorithm 3: Finding HTFUUBI₁ itemsets.

Algorithm 4: Finding HTFUUBI_r+1 itemsets.