T2FM: A novel hashtable based type-2 fuzzy frequent itemsets mining

Abstract

Association rule mining (ARM) is an important research issue in the field of data mining that aims to find relations among different items in binary databases. The conventional ARM algorithms consider the frequency of the items in binary databases, which is not sufficient for real time applications. In this paper, a novel hash table based Type-2 fuzzy mining algorithm (T2FM) with an efficient pruning strategy is presented for discovering multiple fuzzy frequent itemsets from quantitative databases. The algorithm employs a hash table based structure for efficient storage and retrieval of item/itemset which reduces the search efficiency to O(1) or constant time. Previously, type-2 based Apriori and FP-growth based fuzzy frequent itemsets mining were proposed, which required large amounts of computation and a greater number of candidate generation and processing. Meanwhile, the proposed approach reduces a huge amount of computation by finding the common keys before the actual intersection operation takes place. An efficient pruning strategy is proposed to avoid unpromising candidates in order to speed up the computations. Several experiments are carried out to verify the efficiency of the approach in terms of runtime and memory for different minimum support threshold and the results show that the designed approach provides better performance compared to the state-of-the-art algorithms.

Keywords

Data mining type-2 fuzzy set quantitative dataset fuzzy frequent itemsets multiple linguistic terms

1 Introduction

Knowledge Discovery in Databases (KDD), also called pattern mining [1 –3] is an important research problem in many tasks since it can discover implicit and hidden information from the dataset. Apriori [1] is the first fundamental algorithm that can be used to find the associations among the item(s) in the dataset. Since the Apriori algorithm is a level wise approach, a higher computational cost is needed to generate the candidates and then evaluate them level-by-level for generating frequent itemsets. FP-growth [4] is an improved algorithm that generates frequent itemsets by compressing the transactions into a tree structure called FP-tree. Most ARM algorithms focus on mining frequent itemsets (FIs) or association rules from binary datasets, in which they consider whether the item(s) appears or not in the transaction. Important factors like weight, interestingness, quantity and importantness are not considered in ARM.

Fuzzy-set theory [5, 6] can be used in many intelligent systems, such as manufacturing, engineering fields, or medical diagnosis, since fuzzy-set based knowledge representation is more interpretable for human reasoning. Fuzzy based system also converts the quantitative value of items into meaningful linguistic terms with the corresponding degrees that can be used for making efficient decisions.

Many algorithms have been proposed to handle quantitative datasets for mining fuzzy frequent itemsets based on fuzzy set theory [7 –9]. However, most of the introduced approaches consider only one linguistic term with the maximum scalar cardinality of an item. So the discovered information may not be complete for decision making. Several other algorithms consider multiple fuzzy terms [10 –13] to generate a complete set of fuzzy frequent itemsets, which provide more complete and sufficient knowledge for better and useful decision making.

The above specified methods mostly use the type-1 fuzzy set theory for discovering the required knowledge such as ARs or FIs. Mendel and John [14] introduced the type-2 fuzzy set theory that involves uncertain factor to discover the required information for effective decision making. Chen et al. [15] uses type-2 fuzzy set model with the level-wise approach for the generation of frequent itemsets from the quantitative datasets. However, this approach does not provide the complete information because it considers single linguistic term of an item. Lin et al. [16], designed a list based method for the mining of type-2 fuzzy frequent itemsets, which speed up the mining process compared with the level-wise approach. However, this approach does not have the effective pruning methods to reduce the search area for the effective mining of frequent itemsets.

In this study, a novel hash table based Type-2 fuzzy mining algorithm (T2FM) is introduced with the purpose of effective mining of fuzzy frequent itemsets from quantitative datasets. T2FM is a simple and fast algorithm for knowledge mining since it uses the hash table data structure for the storage and retrieval of fuzzy itemsets, which reduces the search efficiency to O(1) or constant time. The algorithm finds the common keys before doing the actual intersection operation, which increases the execution speed of the algorithm. It uses two hash tables, each for storing 1-itemsets and fuzzy frequent itemsets. No other data structure is used in the proposed approach.

The remaining of the paper is organized as follows: Section 2 reviews the related works. The preliminaries and the problem statement of the type-2 fuzzy frequent itemsets mining are given in section 3. The proposed T2FM algorithm and the data structure used are described in section 4. The application of T2FM to breast cancer detection is described in section 5. Experimental evaluations and discussions are shown in section 6. Finally, the conclusion is given in section 7.

2 Literature review

Association rule mining [1 –3] is an important research issue in data mining that finds the relationship among the item(s) in the databases. Apriori [2] is the first algorithm that generates frequent itemsets step by step using prior knowledge, while infrequent candidates are removed at each step. This method requires either n or n + 1 searches of the entire transaction database, where n is the maximum length of the frequent itemset. That is, the method uses a lot of memory and takes a long time to search the frequent itemsets due to repetitive searches of the database.

To solve this problem, Han et al., [4] introduce the FP-growth algorithm that finds the complete set of FIs without generating a huge number of candidate itemsets. The FP-Growth transforms the transactional dataset into a FP-Tree structure in which the frequent itemsets are searched through a recursive exploration process. However, the size of the tree and the number of branches become too large in the case of rare frequent item sets. Furthermore, several extensions of association rule mining, such as maintenance algorithm [17] for data stream, sequential pattern mining [18], high-utility itemset mining [19], have been proposed for different applications.

Even though these algorithms find frequent items effectively, they cannot be applied to quantitative datasets. It is not easy to discover the relationships between items in the quantitative database. Fuzzy set theory [6, 20] is a solution for discovering knowledge for human reasoning and is used in many intelligent systems. Fuzzy set theory is used for converting quantitative numbers of items into meaningful linguistic terms with the corresponding degrees. Thus, several fuzzy mining algorithms were then introduced. For example, Au and Chen [21] developed F-APACS for mining fuzzy association rules based on fuzzy linguistic terms to recognize the discovered regularities.

Hong et al. [7] designed an algorithm for mining fuzzy association rules based on the generate-and-test approach that deals with quantitative datasets. Chen et al. [22] designed a model for mining multi-level fuzzy association rules that is based on a cumulative probability distribution. Watanabe and Fujioka [23] have implemented the fuzzy association rule mining algorithm based on redundancy equivalence and theorems. Chang et al. [24] designed an ISPFTI algorithm to mine the complete frequent sequences within the fuzzy time intervals based on fuzzy set theory.

Several other algorithms have been developed for mining the necessary information in different application domains based on fuzzy set theory [25 –30]. Lin et al. [8] proposed the FFP-tree (Fuzzy Frequent Pattern Tree) algorithm for the mining of fuzzy frequent itemsets that compress the fuzzy 1-itemsets into tree structure for the subsequent mining process. Since this approach has a loose tree structure, a compressed fuzzy frequent pattern (CFFP) tree [31] algorithm is proposed to reduce the number of nodes in the tree structure. Though, this approach needs more memory for storing the attached array, it also has the problem of memory leakage. The UBFFP-tree (Upper Bound Fuzzy Frequent Pattern-Tree) algorithm [9] is then designed to solve this problem, which reduces the memory leakage problem by keeping a more condensed tree structure to handle big datasets.

These algorithms [5 , 32] use a single linguistic term as the representative for the processing of the item, so the information derived may not be sufficient for better decision making. Thus, several multiple fuzzy frequent itemsets mining algorithms [12 , 33] are developed for making better strategies or decisions with sufficient information. These algorithms consider multiple linguistic terms as the representative terms of an item for deriving complete information, which helps make better decisions.

The above specified approaches follow type-1 fuzzy-set theory [6], in which the uncertainty factor is not taken into account. Since the type-1 fuzzy-set membership functions are crisp, they are not enough to handle the uncertainty model in real time applications. To solve this problem, type-2 fuzzy set theory [34, 35] is then developed, which takes the uncertainty factor into account. Chen et al. [15] designed the first Apriori-based approach for type-2 fuzzy set based FFIs mining. The algorithm uses a level-wise generate-and-test strategy based on type-2 fuzzy membership functions. Since this is a time consuming process, the transformed fuzzy values of the linguistic terms are converted into type-1 fuzzy values based on the centroid mechanism. However, this approach consumes more time for the generation of candidates. Also, a single linguistic term of an item is considered by the model, which may not produce sufficient information for better decision making.

Hence, there is a need to derive complete information that must be sufficient for efficient decision making. In this paper, an efficient system is designed that consists of: i) an efficient structure for storing and retrieving information; ii) reducing the multiple scans of the datasets; iii) an efficient pruning strategy to speed up the mining process; and iv) generating complete information for efficient decision making (i.e., MFFIs–Multiple Fuzzy Frequent Itemsets).

3 Preliminaries and problem statement

The background preliminaries of the problem and the problem statement of hash table based type-2 fuzzy frequent itemsets mining are stated below.

3.1 Preliminaries

Suppose that I = {i₁, i₂, i₃, . . . . . . , i_m} is a finite set with ‘m’ distinct items. A quantitative database ‘D’ is considered a set of transactions ‘n’ such that D = {T₁, T₂, T₃, T₄, . . . .T_n}. Each transaction in the dataset has its own unique identifier, referred to as a TID in the dataset. Moreover, each item i_j in a transaction T_q comprises its purchase quantity, denoted as q(i_j, T_q). An itemset with ‘k’ distinct elements is called a k-itemset. A minimum support threshold denoted as δ, which can be adjusted by users’ preference. Table 1 is a set of quantitative transactions that is considered as a running example in this paper. The example dataset from Table 1 has 10 transactions with distinct items from (A) to (F). The minimum support threshold δ is assumed to be (δ= 20%). To illustrate the steps of the proposed algorithm, the membership function shown in Fig. 1 is used. Figure 1 shows the membership functions (μ) with linguistic 3-terms in type-2 fuzzy set theory. It is seen that there are three linguistic terms Low(L), Middle(M), and High(H) in the given membership function. The user can specify the number of linguistic terms based on the application and requirements.

Fig. 1

Membership functions (μ) with linguistic 3-terms in type-2 fuzzy set theory.

Table 1

An example quantitative dataset

TID	Items
T1	A:5, C:4, E:1
T2	A:3, E:1
T3	A:1, E:2, F:2
T4	B:2, C:1, E:3
T5	A:4, B:5, C:5, D:3, E:3
T6	B:4, D:1, E:4
T7	C:4, E:2
T8	B:4, E:4, F:3
T9	B:3, C:4, E:2, F:1
T10	E:5, F:5

Definition 1: The linguistic variable i, also called an attribute or item of a quantitative database, i ⊆ I. The value of i is represented by several linguistic terms, R_i1, R_i2, . . . , R_ih, which can be converted by μ, a type-2 fuzzy membership function.

For example, from the sample dataset in Table 1, there are six linguistic variables from (A) to (F) and each linguistic variable has three linguistic terms: low, middle and high.

Definition 2: The value of i, denoted as v_iq, is the quantitative value for the linguistic variable i of the transaction T_q.

For example, the values for the items (A), (C), and (E) in T₁ are v_A1 (= 5), v_C1 (= 4), and v_E1 (= 1) respectively.

Definition 3: A hash table is defined as a data structure that stores data in an associative manner. Each data in the Hash table is in the format of (Key, Value) pairs, where Value may be a direct value or refer to some other object.

For example, HTC1 stores data in the form of an item as the key, and the values are in the form of another hash table in which values are stored in the form of objects.

Definition 4: The keyset for the itemset ‘xy’ is the intersection of the itemset ‘x’ and the itemset ‘y’ i.e., xy.keySet = x.keySet ∩ y.keySet

Let us assume that the itemset B@H.keySet = {5, 6, 8, 9} and E@M.keySet = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10,} then the itemset B@H:E@M.keySet = {5, 6, 8, 9.}

Definition 5: The value for the itemset ‘xy’ on the transaction t_id is the minimum of the values for the items ‘x’ and ‘y’, that can be denoted as E_xy.t_id.V_xy = min(V_x, V_y).

For example, the value for the itemset ‘B@H:E@M’ at t_id ‘9’ is the minimum value of the itemsets B@H (0.1) and E@M (0.55), i.e., min(0.1, 0.55) is ‘0.1’.

Definition 6: The maximum remaining fuzzy value (MRF) of the item ‘x’ in t_id, denoted as MRF(X, T), is the maximum membership value of all the items in T/X calculated as: $MRF (X, T) = \max {fv (i, T / - X)}$

Each entry in the hash table of fuzzy frequent itemsets consists of three ordered fields as: t_id, fv and MRF.

t_id indicates the fuzzy term X exists in transaction T.

fv indicates the fuzzy membership value of the term X in T.

MRF indicates the maximum remaining fuzzy value after X in T.

3.2 Research Problem

The aim of this paper is to propose an efficient method for mining multiple fuzzy frequent itemsets (MFFIs) by using a type-2 fuzzy membership function with an efficient pruning strategy. The problem can be defined formally as, $MFFIs \leftarrow {X | S (X) ⩾ δ \times | D |}$ where X is the fuzzy item(set); S(X) is the support count of the item(set) X; δ is the user specified minimum support count threshold; |D| is the number of transactions in the dataset or the size of the transaction dataset.

Since the traditional methods of fuzzy frequent itemsets [8 , 31] consider only itemsets with maximum scalar cardinality for processing, the information derived may not be complete and not enough to make better and more accurate decisions.

In this paper, multiple fuzzy frequent itemsets are considered to represent the discovered fuzzy frequent itemsets. Thus, all the linguistic terms that satisfy the minimum support count threshold are considered, i.e., more than one term of an item may form the association rules. Also, a hash table data structure is used for maintaining and generating the itemsets, which significantly reduces the execution time since its searching time is O(1) or constant time. An efficient pruning strategy is proposed to avoid unpromising candidates in order to speed up the computations. The detailed description of the proposed T2FM (Type-2 based fuzzy frequent itemsets mining) algorithm is given in the following section.

4 Proposed T2FM Algorithm

The T2FM algorithm is a hash table based type-2 fuzzy mining algorithm with an efficient pruning strategy to speed up the process. It consists of two major parts, namely i) fuzzy C1-itemset formation and ii) generation of fuzzy frequent itemsets. During the first part, called data pre-processing, the quantitative value of each item in the transactions is converted into a form appropriate for fuzzy mining. During the second part, the algorithm discovers the complete set of fuzzy frequent itemsets. Figure 2 shows the overall architecture of the proposed fuzzy mining system. Notations used in the algorithm are given below.

Fig. 2

Architecture of proposed fuzzy mining system.

Notation

D - a quantitative dataset

N - number of transactions in D

μ - a set of type-2 fuzzy membership functions

h - number of fuzzy regions

T_i -- i^th transaction in the dataset (1≤i≤N)

i_j.R_jl - l-th fuzzy region of item i_j

$f_{ijl}^{lower}$ - v_ij’s lower fuzzy membership value for region R_jl

f_ijl^upper -v_ij’s upper fuzzy membership value for region R_jl

HTC1 – Hash table stores candidate 1-itemsets

HTC1S - Sub table of Hash table HTC1

HTFZ – Hash table stores fuzzy frequent itemsets

HTFZS - Sub table of Hash table HTFZ

δ - minimum support threshold

keySize() - total number of keys in the Hash Table

keyset() - set of keys in the Hash Table

fv - fuzzy membership value

MRF - Maximum remaining fuzzy value

4.1 Fuzzy C₁-itemsets formation

Fuzzy Candidate 1-itemsets (C₁) are the item(s) based on which all the fuzzy frequent itemsets are generated. In this phase, the quantitative value of each item in the transactions is converted into a type-2 fuzzy value by using the given type-2 fuzzy membership function μ. Then, the calculated type-2 fuzzy values are reduced into type-1 fuzzy values with the centroid type reduction method. To maintain the C₁-itemsets, the algorithm uses a hash table called HTC1 (Hash table for Candidate 1-itemsets), which has the form of item as the key and another hash table called HTC1S (Sub of HTC1) as the value. Each entry in HTC1S has the form of (key, value) pairs, with TID as the key and fuzzy values for all the linguistic terms of the corresponding variable as the values. For each entry in HTC1S, the corresponding “Total” is updated when the item is an existing member of HTC1. Otherwise, “Total” is assigned with the calculated value “cval” and added as the new entry for HTC1S. In both cases, HTC1S is added as the value for the key of the item. Figure 3 shows the structure of the HTC1 hash table. The algorithm for the generation of fuzzy c₁-itemsets is shown in Fig. 4.

Fig. 3

Structure of HTC1 Table.

Fig. 4

Algorithm for Fuzzy c1-itemsets generation.

4.2 Multiple fuzzy frequent itemsets generation

In this phase, the actual fuzzy frequent itemsets mining takes place with the help of the minimum support threshold δ. The output of the first phase (set of C₁-itemsets) and δ are the inputs to this phase. It consists of two parts: i) L₁-itemset generation and ii) L_k-itemset (k > 1) generation. L₁-itemsets are formed by filtering all the elements that satisfy δ from HTC1. In this phase, a hash table HTFZ (Hash table for Fuzzy Frequent Itemsets) is used to store all fuzzy frequent itemsets, which also has the form of Item@Region as the key and HTFZS (Sub of HTFZ) as the value of HTFZ. HTFZS stores a set of TIDs with the fuzzy membership value and the maximum remaining fuzzy value for the respective region of the corresponding item. The algorithm initializes the maximum remaining fuzzy value for each item by comparing every item’s MRF with successive items’ fuzzy values and considering whether it is greater.

In the second part, the algorithm generates L_K (K > 1) from the set of L₁-itemsets. Every item ‘x’ in HTFZ is intersected with every other item ‘y’ in HTFZ if x and y not belong to the same item i. The algorithm first determines the intersection of TIDs of x and y referred to as xy.keySet. Then, for each element in xy.keySet, find the intersection by considering the minimum fuzzy values of x and y. Meanwhile, the maximum remaining fuzzy value is the MRF of the item y in the respective t_id. For every intersection operation, the “Total” value of the respective key “xy” is updated. After completion of the intersection operation on two items, the resultant itemset is added to HTFZ only when its support count value is greater than or equal to δ. A separate list called “item To Process” is maintained to store every new itemset that has a MRF greater than δ. This list will be used later for generating the next level of frequent itemsets. Repeat the steps 24 to 45 until the list “item To Process” becomes less than or equal to “1”. Figure 5 shows the structure of the fuzzy frequent itemsets table. The T2FM algorithm for mining multiple fuzzy frequent item sets is given in Fig. 6.

Fig. 5

Structure of fuzzy frequent itemsets table.

Fig. 6

T2FM Algorithm for mining multiple fuzzy frequent itemsets.

4.3 An Example

In this section, a running example is given to illustrate how the MFFIs are discovered from the set of quantitative transactions by the proposed approach. The quantitative dataset shown in Table 1 is considered as an example. The dataset consists of 10 transactions and 6 distinct items, denoted A to F.

The minimum support threshold δ is assumed to be 20% and the type-2 fuzzy membership function shown in Fig. 1 is used for fuzzification. In this example, the fuzzy membership function has three linguistic terms: low, middle and high; and their range of values is assumed to be low[∞ and (3, 3.5)], middle[(0.5, 1) and (5, 5.5)] and high[(2.5, 3) and ∞]. The fuzzy C₁-itemset generation for the example is described below.

First, the quantitative values of the items are transformed into type-2 fuzzy values. Consider the first item “A:5” in transaction 1 as an example. The value

of “5” is converted into (0, 0.2)/A.M + (1.0,1.0)/A.H; by using μ in Fig. 1. The same step is repeated for all the other items in all transactions. The transformed results are shown in Table 2. Then, the calculated type-2 fuzzy values are reduced into type-1 values by the centroid type-reduction method. In this example, for the item “A:5”, the transformed fuzzy value (0, 0.2)/A.M + (1.0,1.0)/A.H; is reduced into (0.1)/A.M + (1.0)/A.H and the resultant representation for all the items is shown in Table 3. For each item’s presence on successive transactions, the corresponding “Total” is added. In this example, the item “A” exists on TIDs T₁, T₂, T₃ and T₅, and the “Total” calculated is [A.Low: 1.1; A.Middle: 1.75; A.High: 1.65]. At the end of the first phase, the hash table HTC1 contains all the fuzzy C₁-itemsets of the example dataset.

Table 2
Fuzzified data with Type-2 membership function from Table 1

TID Transformed Type-2 fuzzy representation

LT1 (0,0.2)/A.M + (1.0,1.0)/A.H; (0.5, 0.6)/C.M + (0.5, 0.6)/C.H; (1,1)/E.L + (0,0.2)/E.M

T2 (0,0.2)/A.L + (1,1)/A.M + (0,0.2)/A.H; (1,1)/E.L + (0,0.2)/E.M

T3 (1,1)/A.L + (0,0.2)/A.M; (0.5, 0.6)/E.L + (0.5,0.6)/E.M; (0.5, 0.6)/F.L + (0.6,0.6)/F.M

T4 (0.5,0.6)/B.L + (0.5,0.6)/B.M; (1,1)/C.L + (0,0.2)/C.M; (0,0.2)/E.L + (1,1)/E.M + (0,0.2)/E.H

T5 (0.5,0.6)/A.M + (0.5,0.6)/A.H; (0,0.2)/B.M + (1,1)/B.H; (0,0.2)/C.M + (1,1)/C.H; (0,0.2)/D.L + (1,1)/D.M + (0,0.2)D.H; (0,0.2)/E.L + (1,1)/E.M + (0,0.2)E.H

T6 (0.5,0.6)/B.M + (0.5,0.6)/B.H; (1,1)/D.L + (0,0.2)/D.M; (0.5,0.6)/E.L + (0.5,0.6)/E.H

T7 (0.5.0.6)/C.M + (0.5.0.6)/C.H; (0.5,0.6)/E.L + (0.5,0.6)/E.M

T8 (0.5,0/6)/B.M + (0.5,0/6)/B.H; (0.5,0/6)/E.M + (0.5,0/6)/E.H; (0,0.2)/F.L + (1,1)/F.M + (0,0.2)/F.H

T9 (0,0.2)/B.L + (1,1)/B.M + (0,0.2)/B.H); (0.5,0.6)/C.M + (0.5,0.6)/C.H; (0.5,0.6)/E.L + (0.5,0.6)/E.M; (1,1)/F.L + (0,0.2)/F.M

T10 (0,0.2)/E.M + (1,1)/E.H; (0,0.2)/E.M + (1,1)/E.H

TID	Transformed Type-2 fuzzy representation
LT1	(0,0.2)/A.M + (1.0,1.0)/A.H; (0.5, 0.6)/C.M + (0.5, 0.6)/C.H; (1,1)/E.L + (0,0.2)/E.M
T2	(0,0.2)/A.L + (1,1)/A.M + (0,0.2)/A.H; (1,1)/E.L + (0,0.2)/E.M
T3	(1,1)/A.L + (0,0.2)/A.M; (0.5, 0.6)/E.L + (0.5,0.6)/E.M; (0.5, 0.6)/F.L + (0.6,0.6)/F.M
T4	(0.5,0.6)/B.L + (0.5,0.6)/B.M; (1,1)/C.L + (0,0.2)/C.M; (0,0.2)/E.L + (1,1)/E.M + (0,0.2)/E.H
T5	(0.5,0.6)/A.M + (0.5,0.6)/A.H; (0,0.2)/B.M + (1,1)/B.H; (0,0.2)/C.M + (1,1)/C.H; (0,0.2)/D.L + (1,1)/D.M + (0,0.2)D.H; (0,0.2)/E.L + (1,1)/E.M + (0,0.2)E.H
T6	(0.5,0.6)/B.M + (0.5,0.6)/B.H; (1,1)/D.L + (0,0.2)/D.M; (0.5,0.6)/E.L + (0.5,0.6)/E.H
T7	(0.5.0.6)/C.M + (0.5.0.6)/C.H; (0.5,0.6)/E.L + (0.5,0.6)/E.M
T8	(0.5,0/6)/B.M + (0.5,0/6)/B.H; (0.5,0/6)/E.M + (0.5,0/6)/E.H; (0,0.2)/F.L + (1,1)/F.M + (0,0.2)/F.H
T9	(0,0.2)/B.L + (1,1)/B.M + (0,0.2)/B.H); (0.5,0.6)/C.M + (0.5,0.6)/C.H; (0.5,0.6)/E.L + (0.5,0.6)/E.M; (1,1)/F.L + (0,0.2)/F.M
T10	(0,0.2)/E.M + (1,1)/E.H; (0,0.2)/E.M + (1,1)/E.H

Table 3

Reduced dataset with centroid type-reduction method

HTC1- fuzzy (C₁) Candidate 1-itemsets
Item	HTC1S
A	1	2	3	5	Total
	–	0.1	1	–	1.1
	0.1	1	0.1	0.55	1.75
	1	0.1	–	0.55	1.65
B	4	5	6	8	9	Total
	0.55	–	–	–	0.1	0.65
	0.55	0.1	0.55	0.55	1	2.75
	–	1	0.55	0.55	0.1	2.2
C	1	4	5	7	9	Total
	–	1	–	–	–	1
	0.55	0.1	0.1	0.55	0.55	1.85
	0.55	–	1	0.55	0.55	2.65
D	5	6	Total
	0.1	1	1.1
	1	0.1	1.1
	0.1	–	0.1
E	1	2	3	4	5	6	7	8	9	10	Total
	1	1	0.55	0.1	0.1	–	0.55	–	0.55	–	3.85
	0.1	0.1	0.55	1	1	0.55	0.55	0.55	0.55	0.1	5.05
	–	–	–	0.1	0.1	0.55	0	0.55	–	1	2.3
F	3	8	9	10	Total
	0.55	0.1	1	–	1.65
	0.55	1	0.1	0.1	1.75
	–	0.1	–	1	1.1

During the second phase of the algorithm, L₁ and L_k(k > 1) itemsets generation steps take place. In this phase, L₁-itemsets are formed by filtering all the elements that satisfy δ as 20%. Since the example dataset has 10 transactions, δ is calculated as 2 (10*20/100 = 2). From Table 3, it is seen that B@M (2.75), B@H (2.2), C@H (2.65), E@L (3.85), E@M (5.05) and E@H (2.3) are satisfied and therefore these elements are only filtered out and stored in the hash table HTFZ. For every level of updation into HTFZ, the keys are copied into the list “item To Process” for the generation of next level frequent itemsets. In this example, initially the list “item To Process” has the elements [B@M, B@H, C@H, E@L, E@M, E@H] once the L₁-itemsets are copied to HTFZ. Then, successive levels of L_K-itemsets are generated.

In this example, since B@M and B@H belong to the same item, they do not intersect themselves. Similarly, E@L, E@M and E@H do not intersect themselves. But they can intersect with other itemsets. Consider the items B@H and E@M; initially, the TIDs that are common to both itemsets are determined by choosing the common keys from the keySets for these two itemsets. Since, T₅, T₆, T₈ and T₉ are common to both B@H and E@M, intersection is calculated by taking the minimum value of these TIDs for these basic items. Here, min(B@H, E@M) for the TIDs (T₅, T₆, T₈ and T₉) are [1, 0.55, 0.55, 0.1 = 2.2 (sum)] which satisfies the minimum support count threshold, combination of B@H:E@M is inserted into HTFZ as the key and [T₅:1, T₆:0.55, T₈:0.55, T₉:0.1, Total:2.2] is stored as the value in the form of hash table HTFZS. Similarly, the same process is repeated until “item To Process” becomes null. In order to speed up the computation process, the algorithm identifies and removes the unpromising nodes based on the maximum remaining fuzzy values of the itemsets. For every intersection operation, T2FM takes the MRF of the second base itemset as the resultant MRF. Even though the resultant itemset is a fuzzy frequent itemset, it is considered for further processing only when its MRF is greater than δ. After the completion of this phase, the hash table HTFZ contains the complete set of multiple fuzzy frequent itemsets of the example dataset, as shown in Table 4.

Table 4

Set of Fuzzy frequent itemsets derived from the example dataset

HTFZ- fuzzy frequent itemsets
Item	HTFZS
B@H	5	6	8	9	Total
	1	0.55	0.55	0.1	2.2
	1	0.55	0.55	0.55	2.65
B@M	4	5	6	8	9	Total
	0.55	0.1	0.55	0.55	1	2.75
	1	1	0.55	0.55	0.55	3.65
E@L	1	2	3	4	5	7	9	Total
	1	1	0.55	0.1	0.1	0.55	0.55	3.85
	0	0	0	0	0	0	0	0
C@H	1	5	7	9	Total
	0.55	1	0.55	0.55	2.65
	1	1	0.55	1	3.55
E@M	1	2	3	4	5	6	7	8	9	10	Total
	0.1	0.1	0.55	1	1	0.55	0.55	0.55	0.55	0.1	5.05
	0	0	0	0	0	0	0	0	0	0	0
E@H	4	5	6	8	10	Total
	0.1	0.1	0.55	0.55	1	2.3
	0.55	1	0.55	0.55	0	2.65
B@H:E@M	5	6	8	9	Total
	1	0.55	0.55	0.1	2.2
	0	0	0	0	0
B@M:E@M	4	5	6	8	9	Total
	0.55	0.1	0.55	0.55	0.55	2.3
	0	0	0	0	0	0
C@H:E@M	1	5	7	9	Total
	0.1	1	0.55	0.55	2.2
	0	0	0	0	0

5 Applications of T2FM in Breast Cancer Detection

According to a study from a cancer research institute, breast cancer is the most serious disease that impacts people worldwide and is the fifth-largest cause of death in women. The two types of breast lesions that can be diagnosed are malignant and benign lesions [39]. In the UK, about 48,000 cases occur every year, and around one in nine women is affected in their lifetime [40]. This disease can be cured easily if diagnosed at an earlier stage. Mammography is one of the methods frequently used to diagnose breast cancer. But the mammography identifies the breast abnormalities with an accuracy level of 85–90%. On the other hand, fine needle aspiration cytology (FNAC) has a correct identification rate of 90%. Hence, there is a need to implement a better identification method for the diagnosis of breast cancer.

In this section, the T2FM is applied to the detection of breast cancer. The core features with the appropriate ranges of values are detected through the algorithm. The algorithm is applied to the Wisconsin Breast Cancer Database (WBCD) [38] and the features are analyzed. The dataset has 699 instances, among which 241 records (34.5%) are malignant, whereas 458 records (65.5%) are benign. In the experiment, the dataset is divided into benign and malignant categories and the features with an appropriate range of values are observed separately. Table 5 shows the set of frequent items generated with an appropriate range of values through T2FM on WBCD datasets.

Table 5
Frequent itemsets formed on WBCD through T2FM

Class Frequent Itemsets Minimum Support Minimum Support Percentage Maximum Remaining fuzzy value Confidence

Benign mitos@L 449.6 0.0 100

> = 95

mitos@L &Normal@L 413.99 0.0 100

> = 90

bare@L 413.95 434.65 100

normal@L 419.7 436.95 100

bare@L &mito@L 409.15 0.0 100

> = 85

adh@L &mito@L 393.65 0.0 100

sizeu@L 403.05 442.2 100

mitos@L &sizeu@L 398.69 0.0 100

bare@L &normal@L 387.85 420.4 100

> = 80

adh@L &mitos@L &normal@L 371.59 0.0 100

mitos@L &normal@L sizeu@L 382.69 0.0 100

bare@L &mitos@L &normal@L 383.5 0.0 100

adh@L &bare@L &mitos@L 367.4 0.0 100

bare@L &mitos@L &sizeu@L 372.89 0.0 100

Malignant thick@H 217.8 > = 90 0.0 100

shapu@H 197.35 > = 80 229.3 100

bare@H 198.55 195.15 100

sizeu@H &thick@H 175.20 > = 70 0.0 100

bland@H 185.2 231.55 100

bare@H &thick@H 178.05 0.0 100

shapu@H &thick@H 179.55 0.0 100

shapu@H &sizeu@H 175.85 221.3 100

bare@H &sizeu@H &thick@H 145.45 > = 60 0.0 100

bland@H &shapu@H &sizeu@H 145.00 214.3 100

epi@H &thick@H 146.2 0.0 100

bare@H &shapu@H &sizeu@H 149.0 182.05 100

adh@H 151.1 188.0 100

shapu@H &sizeu@H &thick@H 161.65 0.0 100

bland@H &thick@H 167.05 0.0 100

bare@H &bland@H 157.7 188.6 100

bare@H &shapu@H &thick@H 150.8 0.0 100

normal@H 157.55 194.0 100

mitos@L 151.95 192.0 100

Class	Frequent Itemsets	Minimum Support	Minimum Support Percentage	Maximum Remaining fuzzy value	Confidence
Benign	mitos@L	449.6		0.0	100
			> = 95
	mitos@L &Normal@L	413.99		0.0	100
			> = 90
	bare@L	413.95		434.65	100
	normal@L	419.7		436.95	100
	bare@L &mito@L	409.15		0.0	100
			> = 85
	adh@L &mito@L	393.65		0.0	100
	sizeu@L	403.05		442.2	100
	mitos@L &sizeu@L	398.69		0.0	100
	bare@L &normal@L	387.85	420.4	100
			> = 80
	adh@L &mitos@L &normal@L	371.59		0.0	100
	mitos@L &normal@L sizeu@L	382.69		0.0	100
	bare@L &mitos@L &normal@L	383.5		0.0	100
	adh@L &bare@L &mitos@L	367.4		0.0	100
	bare@L &mitos@L &sizeu@L	372.89		0.0	100
Malignant	thick@H	217.8	> = 90	0.0	100
	shapu@H	197.35	> = 80	229.3	100
	bare@H	198.55		195.15	100
	sizeu@H &thick@H	175.20	> = 70	0.0	100
	bland@H	185.2		231.55	100
	bare@H &thick@H	178.05		0.0	100
	shapu@H &thick@H	179.55		0.0	100
	shapu@H &sizeu@H	175.85		221.3	100
	bare@H &sizeu@H &thick@H	145.45	> = 60	0.0	100
	bland@H &shapu@H &sizeu@H	145.00		214.3	100
	epi@H &thick@H	146.2		0.0	100
	bare@H &shapu@H &sizeu@H	149.0		182.05	100
	adh@H	151.1		188.0	100
	shapu@H &sizeu@H &thick@H	161.65		0.0	100
	bland@H &thick@H	167.05		0.0	100
	bare@H &bland@H	157.7		188.6	100
	bare@H &shapu@H &thick@H	150.8		0.0	100
	normal@H	157.55		194.0	100
	mitos@L	151.95		192.0	100

The output shows that the feature ‘mitoses’ with a low range of values has the highest support percentage on benign (98.03%). But it also supports 63.04% in the malignant category. Thus, it shows that the feature ‘mitoses’ does not contribute to the diagnosis of breast cancer. The output also shows that the higher range of clump thickness (above 90%), shape uniformity (71.74%) and Bare Nuclei (82.38%) indicate that the person has a higher possibility of breast cancer. It is also seen that the low range of Bare Nuclei (bare), Normal Nucleoli (normal), Marginal Adhesion (adh), and Uniformity of Cell Size (sizeu) confirm the non-existence of breast cancer. Table 5 shows the complete set of fuzzy frequent itemsets generated through T2FM on the WBCD dataset. For clear readability, maximally frequent items are only shown in the table.

6 Experimental results

In this section, the performance of the proposed algorithm “T2FM” is compared with the recently proposed LFFT2 [36] and Apriori based approach [15] in terms of execution time and memory usage. Three algorithms have been implemented with Java in NetBeans IDE 6.0.1. Experiments have been done on computer with Intel(R) Core(TM)i5-3210M CPU @ 2.50 GHz processor having 6.00 GB main memory. It is to be noted that the Apriori based approach considers only the single linguistic term of an item. On the other hand, LFFT2 considers multiple fuzzy frequent itemsets. Both real and synthetic datasets, like Chess [37], Mushroom [37] and Breast Cancer [38] were used in the experimental evaluations. Parameters and characteristics of the datasets used for the implemented algorithms are shown in Tables 6 and 7, respectively.

Table 6
Parameters of the dataset used

#|D| Number of transactions in a dataset

#|I| Number of distinct items in a dataset

AvgLen Average transaction length of a dataset

MaxLen Maximum length of the transactions in a dataset

6.1 Execution time

In this section, the time taken by the proposed algorithm is compared with other state-of- the art algorithms Apriori and LFFT2. Runtime is measured by executing three algorithms for the datasets given in Table 7 with varying values of the minimum support threshold. Figure 7 shows the time taken by the proposed T2FM, Apriori, and LFFT2 for different datasets. It is observed that the proposed T2FM takes less time compared with the other two algorithms since it uses a hash table data structure, whose search efficiency for insertion or retrieval of items is O(1). Also, the algorithm does not consider the itemset as frequent if the “Total” of the fuzzy term is less than the minimum support count threshold, and thus it will be removed directly. Except candidate 1-itemsets and fuzzy frequent itemsets, none of the others are maintained in T2FM, which also increases the speed of the algorithm. On the other hand, the apriori-based approach takes more time due to the generation of level-wise candidate generation and multiple scans of the database, which considerably reduces the execution speed of the algorithm. Even though LFFT2 avoids multiple scanning of the dataset, it takes comparatively more time with T2FM because of the use of the list-based structure and an explicit pruning strategy, while in T2FM, non-frequent itemsets are automatically removed from the structure.

Fig. 7

Runtime comparisons of Apriori, LFFT2 and T2FM on (a) Breast cancer (b) Chess and (c) Mushroom datasets.

Table 7

Characteristics of the dataset used

Database	#\|D\|	#\|I\|	AvgLen	MaxLen	Type
BreastCancer	699	10	10	10	dense
Chess	3196	75	37	37	dense
Mushroom	8124	119	23	23	dense

6.2 Memory usage

In this section, the memory usage of the proposed algorithm is compared with other state-of-the-art algorithms Apriori and LFFT2. Memory usage is measured by executing three algorithms on the datasets: Breast cancer, Chess and Mushroom for varying values of the minimum support threshold. Figure 8 shows the memory usage comparison of three algorithms. It shows that T2FM consumes little memory compared with other algorithms due to the compact representation of itemsets in the hash table structure. Also, T2FM maintains only the needed data, like the candidate 1-itemsets and frequent itemsets. Other unneeded data is not maintained in T2FM, which considerably reduces the memory usage of the algorithm. On the other hand, Apriori maintains candidate itemsets in addition to frequent itemsets. Even though LFFT2 does not maintain candidate itemsets, it stores the maximum remaining fuzzy membership value for each TID of the fuzzy itemsets, which in turn consumes a little more memory than T2FM.

Fig. 8

Memory usage comparisons of Apriori, LFFT2 and T2FM on (a) Breast cancer (b) Chess and (c) Mushroom datasets.

7 Conclusion

This paper proposes a novel type-2 based fuzzy mining algorithm for the generation of multiple fuzzy frequent itemsets. The algorithm uses a hash table structure for efficient storage and retrieval of frequent itemsets, which reduces the search efficiency to O(1) or constant time. An efficient pruning strategy was designed to avoid the unpromising candidates in advance so that execution speed is increased. Based on the proposed model, complete and sufficient information is produced, which helps to make efficient strategies for better decision making. The algorithm was applied to the Wisconsin Breast Cancer Dataset to find the features with appropriate ranges of values for the diagnosis of breast cancer. Experimental evaluation performed on real and synthetic datasets shows that the developed T2FM achieves better performance compared to other recent state-of-the-art algorithms, Apriori and LFFT2, in terms of execution time and memory usage.

The dataset used in the algorithm is assumed to be static. But in the real world, application data is dynamically added to the database. Thus, in the future, T2FM will be extended to handle dynamic datasets. Further improvements will also be performed in the T2FM.

Author contributions statement

M. Jeya sutha: Conceptualization, Methodology, Software, Writing. F. Ramesh Dhanaseelan: Validation, Supervision. M. Felix Nes Mabel: Formal analysis, Writing, Visualization. V. T. Vijumon: Validation, Writing and Visualization.

Funding

“Not Applicable”

References

Agrawal

, Imielinski

, Swami

Mining association rules between sets of items in large databases, ACM SIGMOD Record (1993), pp. 207–216.

Agrawal

, Srikant

Fast algorithms for mining association rules in large databases, The International Conference on Very Large Databases (1994), pp. 487–499.

Chen

M.S.

, Han

and Yu

P.S.

, Data mining: An overview from a database perspective,pp, IEEE Transactions on Knowledge and Data Engineering 6 (1996), 866–883.

Han

, Pei

, Yin

and Mao

, Mining frequent Patterns without candidate generation: a frequent-pattern tree approach, Data Mining & Knowledge Discovery 8 (2004), 53–87.

Lin

C.W.

and Hong

T.P.

, A survey of fuzzy web mining,pp, Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery 3 (2013), 190–199.

Zadeh

L.A.

, Fuzzy sets, Information and Control 8 (1965), 338–353.

Hong

T.P.

, Kuo

C.S.

and Chi

S.C.

, Mining association rules from quantitative data,pp, Intelligent Data Analysis 3 (1999), 363–376.

Lin

C.W.

, Hong

T.P.

and Lu

W.H.

, Linguistic data mining with fuzzy FP-trees,pp, Expert Systems with Applications 37 (2010), 4560–4567.

Lin

C.W.

and Hong

T.P.

, Mining fuzzy frequent itemsets based on UBFFP trees,pp, Journal of Intelligent and Fuzzy Systems 27 (2014), 535–548.

10.

Hong

T.P.

, Lan

G.C.

, Lin

Y.H.

and Pan

S.T.

, An effective gradual data-reduction strategy for fuzzy itemset mining,pp, International Journal of Fuzzy Systems 15(2) (2013), 170–181.

11.

Hong

T.P.

, Lin

C.W.

and Lin

T.C.

, The MFFP-tree fuzzy mining algorithm to discover complete linguistic frequent itemsets, Computational Intelligence 30 (2014), pp. 145–166.

12.

Lin

J.C.W.

, Hong

T.P.

and Lin

T.C.

, A CMFFP-tree algorithm to mine complete multiple fuzzy frequent itemsets, Applied Soft Computing 28 (2015), pp. 431–439.

13.

Lin

J.C.W.

, Hong

T.P.

, Lin

T.C.

and Pan

S.T.

, An UBMFFP tree for mining multiple fuzzy frequent itemsets, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems 23 (2015), pp. 861–879.

14.

Mendel

J.M.

and John

R.I.B.

, Type-2 fuzzy sets made simple,pp, IEEE Transactions on Fuzzy Systems 10 (2002), 117–127.

15.

Chen

C.H.

, Hong

T.P.

, Li

Fuzzy association rule mining with type-2 membership functions, Lecture Notes in Computer Science, (2015), pp. 128–134.

16.

Lin

J.C.W.

, Lv

, Fournier-Viger

, Wu

T.Y.

, Hong

T.P.

Efficient mining of fuzzy frequent itemsets with type-2 membership functions, The Asian Conference on Intelligent Information and Database Systems, (2016), pp. 191–200.

17.

Lin

C.W.

, Hong

T.P.

and Lu

W.H.

, The Pre-FUFP algorithm for incremental mining, Expert Systems with Applications 36 (2009), 9498–9505.

18.

Gan

, Lin

J.C.W.

, Fournier-Viger

, Chao

H.C.

and Yu

P.S.

, A survey of parallel sequential pattern mining, ACM Transactions on Knowledge Discovery from Data 13(3) (2019), 1–34.

19.

Gan

, Lin

J.C.W.

, Fournier-Viger

, Chao

H.C.

, Tseng

V.S.

and Yu

P.S.

, A survey of utility-oriented pattern mining, IEEE Transactions on Knowledge and Data Engineering 33(4) (2019), 1306–1327.

20.

Holland

Adaptation in natural and artificial systems, Cambridge, MA: MIT Press, 1975.

21.

W.H.

, Chan

K.C.C.

An effective algorithm for discovering fuzzy rules in relational databases, IEEE International Conference on Fuzzy Systems (1998), 1314–1319.

22.

Chen

J.S.

, Chen

F.G.

, Wang

J.Y.

Enhance the multi-level fuzzy association rules based on cumulative probability distribution approach, The ACIS International Conference on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing, (2012), pp. 89–94.

23.

Watanabe

, Fujioka

Fuzzy association rules mining algorithm based on equivalence redundancy of items, IEEE International Conference on Systems, Man, and Cybernetics (2012), pp. 1960–1965.

24.

Chang

C.I.

, Chueh

H.E.

, Luo

Y.C.

An integrated sequential patterns mining with fuzzy time-intervals, The International Conference on Systems and Informatics (2012), pp. 2294–2298.

25.

, Yan

, Tang

, Yi

and Zhang

, Data driven hybrid fuzzy model for short-term traffic flow prediction,pp, Journal of Intelligent & Fuzzy Systems 35 (2018), 6525–6536.

26.

Han

, Fu

Discovery of multiple-level association rules from large databases, The International Conference on Very Large Data Bases, (1995), pp. 420–431.

27.

Kar

, Kabir

M.M.J.

Comparative analysis of mining fuzzy association rule using genetic algorithm, The International Conference on Electrical, Computer and Communication Engineering, (2019), pp. 1–5.

28.

Lin

J.C.W.

, Li

, Fournier-Viger

and Hong

T.P.

, A fast algorithm for mining fuzzy frequent itemsets, Journal of Intelligent & Fuzzy Systems 29 (2015), pp. 2373–2379.

29.

Srivastava

D.K.

, Roychoudhury

and Samalia

H.V.

, Fuzzy association rule mining for economic development indicators, International Journal of Intelligent Enterprise 6(1) (2019), pp. 3–18.

30.

Wang

, Ma

and Meng

, Incremental fuzzy association rule mining for classification and regression, IEEE Access 7 (2019), 121095–121110.

31.

Lin

C.W.

, Hong

T.P.

and Lu

W.H.

, An efficient tree-based fuzzy data mining approach, International Journal of Fuzzy Systems 12 (2010), pp. 150–157.

32.

Ling

, Zengrui

and Metawa

, Data mining-based competency model of innovation and entrepreneurship, Journal of Intelligent & Fuzzy Systems 37 (2019), pp. 35–43.

33.

Hong

T.P.

, Lin

C.W.

and Lin

T.C.

, The MFFP-tree fuzzy mining algorithm to discover complete linguistic frequent itemsets, Computational Intelligence 30 (2014), 145–166.

34.

Hagras

Type-2 fuzzy logic controllers: A way forward for fuzzy systems in realworld environments, Lecture Notes in Computer Science (2008), 181–200.

35.

Karnik

N.N.

, Mendel

J.M.

Introduction to type-2 fuzzy logic systems, International Conference on Fuzzy Systems (1998), 915–920.

36.

T-Y.

, Chun-Wei Lin

, Yun

, Chen

C-H

, Srivastava

and Lv

, An efficient algorithm for fuzzy frequent itemset mining, Journal of Intelligent & Fuzzy Systems 38 (2020), 5787–5797.

37.

http://fimi.ua.ac.be/data/

38.

William

Dr.

, Wolberg

(1992), Breast CancerWisconsin (Original), https://archive.ics.uci.edu/ml/datasets.php,Accessed on 30.07.2022

39.

Asadi

and Memon

, Efficient breast cancer detection via cascade deep learning network, International Journal of Intelligent Networks 4 (2023), 46–52.

40.

Dhanaseelan

and Sutha

, Detection of Breast Cancer Based on Fuzzy Frequent Itemsets Mining, IRBM 42 (2021), pp. 198–206.

#\|D\|	Number of transactions in a dataset
#\|I\|	Number of distinct items in a dataset
AvgLen	Average transaction length of a dataset
MaxLen	Maximum length of the transactions in a dataset

T2FM: A novel hashtable based type-2 fuzzy frequent itemsets mining

Abstract

Keywords

1 Introduction

2 Literature review

3 Preliminaries and problem statement

3.1 Preliminaries

4 Proposed T2FM Algorithm

Table 6 Parameters of the dataset used #|D| Number of transactions in a dataset #|I| Number of distinct items in a dataset AvgLen Average transaction length of a dataset MaxLen Maximum length of the transactions in a dataset

Author contributions statement

Funding

References

Table 6
Parameters of the dataset used

#|D| Number of transactions in a dataset

#|I| Number of distinct items in a dataset

AvgLen Average transaction length of a dataset

MaxLen Maximum length of the transactions in a dataset