Data Mining Using Association Rules for Intuitionistic Fuzzy Data

Abstract

This paper considers approaches to the computation of association rules for intuitionistic fuzzy data. Association rules can provide guidance for assessing the significant relationships that can be determined while analyzing data. The approach uses the cardinality of intuitionistic fuzzy sets that provide a minimum and maximum range for the support and confidence metrics. A new notation is used to enable the representation of the fuzzy metrics. A running example of queries about the desirable features of vacation locations is used to illustrate.

1. Introduction

Knowledge discovery and data mining involve a number of approaches from the areas of database processing, pattern recognition, and machine learning. These techniques are used in order to find data patterns or associations of value for decision-making. To deal with the uncertainty often found in real-world data, there have been significant considerations about data mining involving uncertain and fuzzy data mining [1,2,3,4]. The use of fuzzy sets is well established in managing real-world applications in which uncertainty is commonly involved. More specifically for our interest here in association rules, a number of approaches have been considered for fuzzy data [5,6,7].While fuzzy sets present some capabilities, a simple membership function has limitations [8]. This motivates our use of intuitionistic fuzzy sets, as they provide more flexibility for human interactions under uncertainty in association rule data mining. Some concepts are more easily approached by separately envisaging positive and negative instances. In preference modeling involving various interrelated factors, it can be very difficult to simply specify a single simple membership function. [9] For example, in formulating preferences for a family vacation location, there are usually multiple criteria such as distance, costs, and location desirability which influence the evaluation. It can then be very difficult to formulate a simple degree of suitability, but by specifying membership and non-membership corresponding to preferences, the choices can be more easily modeled.

This paper considers the modifications required for association rule computations if fuzzy intuitionistic valued information is involved. The goal is to determine useful associations and patterns from large data sources. Association rules are used to develop valuable insights in determining significant correlations that can be found in the current environment of large data sets, such as those found in various databases or the cloud [10]. The extension using intuitionistic sets is very significant as it captures both positive and negative evaluations. This can then provide contrasting association rules to better inform decision-making. Additionally this provides a complementary capability to the approaches in which positive and negative association rules are generated [11,12].

There have been a large number of specific data mining and knowledge discovery algorithms that have been designed and implemented [13]. Patterns and relationships that can be discovered must be assessed based on interestingness measures in order to provide pruning of the combinatorial complexity of such relationships. Since this sort of information often integrates with decision-making systems, effective user interfaces must be developed with visualizations or other representations for presenting the knowledge discovered.

For this paper, association rule development is our main focus [14]. Associations correspond to correlations among data items which are represented in the form of rules composed of attribute–value conditions that occur with some significant correlations in a set of data [15]. Association rules are of the form antecedents A, and consequents C, A → C, where data entries satisfying the antecedent A commonly occur in conjunction with data values for C. The term “common occurrence” has a probabilistic implication and is not a functional dependency as used in databases.

Finally, we provide an outline of the paper:

Section 2: Fuzzy set representations to be used are defined. A review of previous research on fuzzy data mining, especially research on association rule data mining using fuzzy sets, is presented.

Section 3: The metrics used in association data mining are defined. Specifics of basic association rule data mining are given and a running example illustrates this. A case analysis of the bounds of the basic measures, support and confidence, and the interestingness metrics, lift and conviction, are provided.

Section 4: Next, the basics of the Apriori algorithm are illustrated using the running example.

Section 5: The extensions of association mining needed for intuitionistic fuzzy sets are described, in particular the required set cardinality used for association rule generation. The running example extended to fuzzy intuitionistic data is then used to illustrate the approach using the various metrics.

2. Background

In this section we provide an overview of the fuzzy set representations that are relevant to this paper. Then we discuss data mining in general and specifically fuzzy data mining. In particular, we review other research for fuzzy association rules.

2.1. Uncertainty Representations

In this section we briefly overview common uncertainty representations [16], including fuzzy sets and intuitionistic fuzzy sets for approaches to data mining.

2.1.1. Fuzzy Set Theory

Fuzzy set representations [17,18] provide the membership degrees of data values in a set, as opposed to crisp sets. For domain D, a fuzzy set, FS, is

FS(D) = {<a_i, m(a_i)>|0 ≤ m(a_i) ≤ 1}, a_i ∈ D, I = 1…n

where a_i is a data value and m(a_i) is the membership of the data value.

2.1.2. Intuitionistic Fuzzy Sets

Intuitionistic fuzzy set theory extends ordinary fuzzy set theory by allowing both positive and negative memberships to be specified. Recall that an ordinary fuzzy set FS (D) = {<a_i,m(a_i)>} has only one membership value for a data element a_i. An intuitionistic fuzzy set IFS(D), [19] allows both positive, m_S(a_i), and negative membership values, m_S*(a_i).

IFS(D) = {<a_i, m_S(a_i), m_S*(a_i)>|a_i ∈ D} where m_S(a_i), m*_S(a_i), ∈ [0, 1].

Specifically, the sum of the membership, m_S(a_i), and non-membership, m_S*(a_i), is not necessarily one, then: 0 ≤ m_S(a_i) + m*_S(a_i) ≤ 1. Additionally the hesitation h_S (a_i)

h_S (a_i) = 1 − (m_S(a_i) + m*_S(a_i))

is the degree of indeterminacy (hesitation).

2.1.3. Interval-Valued Fuzzy Sets

Interval values are used in many areas to capture the imprecision and uncertainty of data. We first provide the formalisms for interval arithmetic [20,21] as needed for interval valued fuzzy sets. We let D be the domain and intervals will be represented by the values of the lower bound, z_† = lb(a_i), and an upper bound, z^† = ub(a_i), of an interval I (a_i), for the data value a_i ∈ D

I (a_i) = [z_†, z^†] = {z ∈ D|z_† ≤ z ≤ z^†}

Now, in an interval-based fuzzy set, IVF(D), representation is based on using upper, mu(a_i), and lower bounds, ml(a_i), on fuzzy memberships

IVF(D) = {<a_i, I (a_i) >|I (a_i) = [ ml(a_i), mu(a_i)]}

For an interval I (a_i), the size or length of the interval, IW, is just the difference of the lower and upper bounds,

IW (I (a_i)) = |ml(a_i) − mu(a_i)|.

IW is often used as a representation of the uncertainty of a data value a_i in an IVF as an information measure [22].

We note that IVF and IFS sets are equivalent as generalizations of fuzzy sets [23]. In particular, we have

m_S(a_i) = ml(a_i) and m_S*(a_i) = 1 − mu(a_i)

So,

IVF(D) = {<a_i, I (a_i)>|I (a_i) = [m_s(a_i), 1 − m_S*(a_i)]}

This can be used for the set cardinality of IVF(D), as related to the set cardinality of IFS(D) developed for the calculation of support and confidence of fuzzy association rules.

2.2. Data Mining Approaches

We are primarily concerned with some of the particular algorithms used for knowledge discovery, but we will overview the complete processes involved in data mining. To begin, the initial basic steps involve data preparation [24]. First is a data cleaning stage, which includes resolution of missing data [25] or data errors. Additionally, the integration of data from multiple sources which may be heterogeneous is performed [26,27,28]. Next are the steps needed to prepare for actual data mining, which include the selection of the specific data relevant to the task and the transformation of this data into a format required by the data mining approach. Often, these steps are seen to be those involved in developing data warehouses. This provides an organization for the formatting of data to facilitate data mining approaches.

Knowledge discovery or data mining algorithms can generally be classified into two categories: predictive and descriptive data mining. The descriptive category includes association rules, classification, and class characterization. Typically, data generalizations or characterizations are provided for class descriptions, such as data summarizations [29]. Additionally, data class comparisons allow discrimination of classes to be developed.

Lastly, a classification approach uses data with known class memberships and then builds class models from the features extracted from the training data. Often, this is output as classification rules or a type of decision tree to support predictive classification of new data. Another well-developed knowledge discovery technique is predictive analysis with clustering approaches. Discovery of collections of data items that are similar is achieved by cluster analysis. A distance function is often developed by experts to provide effective similarity metrics. The characteristics of an appropriate clustering algorithm are that it results in high similarity for intra-cluster measures and low similarity for inter-clusters. To determine potential values that may be missing or the distribution of attribute values, various prediction techniques may be used. Some such techniques include machine learning, genetic algorithms, and regression and correlation analysis.

2.3. Fuzzy Data Mining

Many early efforts in knowledge discovery appear in pattern recognition, especially in the form of fuzzy clustering [30]. There have been significant considerations of data mining involving uncertain and fuzzy data mining using neural networks and genetic algorithm approaches [2,3]. More specifically for our interest here in association rules, a number of approaches have been considered for fuzzy data [7,31,32].

2.3.1. Fuzzy Association Rules

In one approach, fuzzy association rule data mining has been developed which can use both fuzzy transactional and relational data [5]. Relational data enable extraction of multidimensional association rules and transactional data make the discovery of patterns more reliable. In another approach based on crisp sets of fuzzy transactions, a general model was developed to discover association rules [33]. The model was capable of being specialized to specific patterns or application data. Additionally, associative rules can be formed by using generalized implicit knowledge based on quantitative transaction data [34]. This technique uses a taxonomy, and items in the rules can be based on any level of the taxonomy. Another paper [35] proposed an automated method for autonomous mining of fuzzy association rules. They first find fuzzy sets by using an efficient clustering algorithm, and then determine their membership functions. Using these they find interesting fuzzy association rules. Two papers have proposed using type-2 fuzzy sets. In one, the quantitative values in transactions are dealt with as type-2 values. These can then be reduced to ordinary fuzzy data using split points and association data mining is carried out on this data [36]. Another approach [37] proposes a fuzzy frequent pattern-mining algorithm based on the type-2 fuzzy set theory of the data stream. The stream is partitioned based on a sliding window. This is then used to extract fuzzy association rules.

2.3.2. Fuzzy Spatial Association Rules

Some interesting approaches have focused on spatial data. Spatial association rules can be implemented by permitting spatial application features represented by fuzzy spatial objects and topological relationships [6]. They extract association rules using application-related spatial objects of interest and the fuzzy spatial features. Another approach to extracting association rules on spatially related data includes uncertain geographic and geologic information [38]. This makes use of fuzzy set cardinality to compute support and confidence metrics for rule evaluation.

None of these approaches have considered alternative uncertainty representations. In this paper we have extended the association rule approaches to consider the more flexible representation of uncertainty using intuitionistic fuzzy sets.

3. Association Rules

This section will describe the basis for the computation of association rules and provide examples demonstrating this. The extensions to the use of intuitionistic fuzzy sets will then be developed and the examples used to provide illustrations of the approach. A common example motivating association rules is the “market basket” of grocery items often purchased in the same transaction [14]. This sort of relationship can provide guidance on the marketing and placement of such items.

3.1. Association Rules Metrics

There are two main metrics, support and confidence, used for association rule data mining. Others are called interestingness metrics, used to evaluate discovered rules.

Let E = { e₁, …, e_n} be a set of data items of interest. We will later consider the possibility that some of these items can involve uncertainty and be represented by intuitionistic fuzzy values. For the data in E we examine a set of items, R, that result from interactions such as a transaction consisting of items related to a purchase order or a query finding vacation locations for which desirable features appear. The interactions are specified by the resulting subsets of E, R = {R₁, R₂, …, R_i, …} where R_i = { e_j, …, e_k} ⊆ E.

Specifically, we are concerned with the possible relationships among the data items that occur in R. Let S_j, S _k ⊆ E, then we are interested in rules of the form F_jk

F_jk: S_j ⇒ S_k

where S_j is the antecedent and S_k the consequent term of the rule. Such a rule means items in S_j co-occur with items in S_k. We must make an assessment of the value of such rules by using two common metrics, support and confidence, to be evaluated to quantify the relationships. We first define two counts, N_sp and N_ant, used in the computation of the support and confidence metrics.

N_sp = |{R_i ∈ R|S_j ∪ S_k ⊆ R_i}|

N_ant = |{R_i ∈ R|S_j ⊆ R_i}|

So N_sp is a count of the number of rules of the form F_jk and N_ant is the number of occurrences of the rule antecedent S_j.

3.1.1. Support Metric: M_sp

The support of a rule is a measure of how frequently the antecedent, S_j, and consequent, S_k, of a rule appear in the same entry R_i of the result set R. Using the count N_sp, we have

Support: M_sp = N_sp/|R|

3.1.2. Confidence Metric: M_cf

The confidence factor indicates how strongly a relationship is represented in the set of results R. That is if S_j ⊆ R_i then it is also the case that S_k ⊆ R_i. So we use the count N_ant here.

Confidence: M_cf = N_sp/N_ant

The percentage of results R_i in R satisfying M_cf will determine if the rule is of value for decision-making.

The support and confidence can be interpreted as probabilities where we have

M_sp: Prob (S_j ∪ S_k); M_cf: Prob (S_k|S_j)

Support and confidence metrics are distinct. Confidence measures a rule’s strength while support is a measurement of statistical significance. In other words, we want a rule with enough support above a threshold, or else it is not representative enough of the data. Rules with support above a threshold are termed as being frequent.

3.2. Examples of Rule Support and Confidence

We can examine a simple example of responses in a query to illustrate the formation of association rules F_jk. So we consider a website that can be queried to locate desirable eco-tourism vacation locations. In

Table 1. Vacation Features Items.

Query Responses	Location Features
R1	{S1, S2, S5}: camp, fish, ski
R2	{S1, S2, S4}: camp, fish, raft
R3	{S1, S2, S4}: camp, fish, raft
R4	{S1, S3}: camp, hike
R5	{S1, S3, S4}: camp, hike, raft
R6	{S2, S3, S5}: fish, hike, ski
R7	{S1, S2, S3}: camp, fish, hike

are responses to queries on vacation preferences related to various available activities which constitute the items of interest, such as camping, fishing, etc.:

E = {S₁: camp; S₂: fish; S₃: hike; S₄: raft; S₅: ski}.

Analyzing these query results, we can obtain association rules and the corresponding support and confidence values.

Table 2. Rules for Results of Table 1.

Rules: Fjk	Msp—Support	Mcf—Confidence
1. F12: camp → fish	4/7 = 0.57	4/6 = 0.66
2. F21: fish → camp	4/7 = 0.57	4/5 = 0.8
3. F31: hike → camp	3/7 = 0.43	3/4 = 0.75
4. F25: fish → ski	2/7 = 0.28	2/5 = 0.4
5. F52: ski → fish	2/7 = 0.28	2/2 = 1
6. F54: ski → raft	0/7 = 0	0/2 = 0
7. F{12}4: camp, fish → raft	2/7 = 0.28	2/4 = 0.5
8. F5{12}: ski → camp, fish	1/7 = 0.14	1/2 = 0.5

shows an example of some representative potential rules relating activities to be evaluated. Note that, in general, all possible combinations of the items in E must be considered, which is then a potentially large space. We discuss the Apriori algorithm in the next section to help prune computation of these combinations.

Consider the first line in Table 2 for the rule F₁₂: “camp → fish”, where camp is the rule antecedent and fish the consequent. This rule shows that available locations with camping often occurred in conjunction with a location in which fishing was allowed. Then, for this rule, the support is 57% since camp and fish co-occur in four entries in Table 1, (R₁, R₂, R₃, R₆), out of the seven query responses. Furthermore, the confidence is 0.66% since the feature camp occurs in a total of six entries of Table 1. Additionally, the second rule, F₂₁, has 80% confidence since the feature S₂—fish appears in five of the responses. Note that not all potential rules have support such as F₅₄, since the items ski and raft do not co-occur in any of the responses.

In considering the rules in Table 2, we can see a range of support values. Most often we are interested in rules with support above a minimum threshold Th_sp. If the support were not high enough, then the rule would not be significant enough to be considered, or even simply not as preferred. So if a threshold were Th_sp = 40%, then the first three rules would be considered to be of interest. These three also have good confidence values, and so are strong rules worth consideration. We see that rules that have high confidence are not necessarily of interest as their support may be low (for example F₂₅ or F_5{12}).

3.3. Interestingness Metrics

Support and confidence are the most common metrics for association rules; however we will examine others that can provide alternative analyses for rules. The commonly used lift measure relates the rule confidence and the expected confidence [39]. Strong rules with high support and confidence can be uninteresting depending on how much the rule antecedent and consequent are related. Lift is used to determine the statistical relationship between the antecedent and consequent, which relates to the interestingness or usefulness of the rule. Another metric is conviction, which relies on the expected support that the antecedent of the rule appears without the consequent. For these metrics, we obtain evaluations as to the prediction significance of the rule.

Although interestingness metrics are useful in evaluation of rules after they are determined, the rules were dependent on the thresholds for confidence and support. Similarly to decisions on fuzzy set memberships, this can be somewhat arbitrary and user-dependent, making consistency of the rule discovery process a problem. One interesting approach addressing this that has been proposed [40] can be applied if rule antecedents follow a determined distribution. Then the minimum confidence and support thresholds can be set based on using a one-sided statistical confidence interval with hypothesis testing.

3.3.1. Lift Metric

First we consider lift given as:

Lift = confidence/expected confidence

We must first specify the support of the consequent of F_jk by defining

N_con = |{R_i ∈ R|S_k ⊆ R_i}|;

and so the support of the consequent is

Consequent Support: M_con = N_con/|R|

Now the expected confidence for a rule is the product of the rule support and consequent support divided by the rule support:

(M_sp ∗ M_con)/M_sp = M_con.

Then finally we obtain:

Lift = M_cf/M_con = (N_sp/N_ant) ∗ (|R|/N_con)

For the rule S_j ⇒ S_k, lift is interpreted as the correlation of the S_j and S_k.

(a)

Lift > 1, positive correlation.

(b)

Lift < 1, negative correlation.

(c)

Lift = 1, correlation is independent.

So lift determines how much more frequently S_j and S_k appear concurrently than would be expected if they were independent statistically.

In our example rules in

Table 3. Lift Values.

Lift < 1	Lift > 1
F12: 0.93	F25: 1.4
F21: 0.93	F52: 1.4
F31: 0.87	F{12}4: 1.12
F5{12}: 0.88

, four rules have a lift less than 1. For example in rules F₁₂ and F₂₁ there is not a significant correlation between the items S₂: fish and S₁: camp, as camp occurs without fish twice and fish occurs without camp once. Now consider rules F₂₅ and F₅₂ for which the lift is 1.4. There is a positive correlation as there is a strong prediction of S₂: fish when S₅: ski occurs since in the only two occurrences of ski, fish also appears in the response.

3.3.2. Conviction Metric

Next we examine the conviction metric

Conviction = (1 − M_con)/(1 − M_cf)

Conviction is sensitive to the direction of rules, S_j ⇒ S_k versus S_k ⇒ S_j. So, we see rule 1 (F₁₂) and rule 2 (F₂₁) differ in their direction, and conviction for rule 1 is 1.26 but for rule 2 it is 2.15. This can be attributed to the lower confidence (0.66) of rule 1, and so rule 2 has greater interest by this measure, leading to the stronger conviction. For logical implications where confidence is 1, the value is unbounded (+∞), as is true for rule 5 (F₅₂). That is, S₅ (ski) uniquely appears with S₂ (fish) and not vice-versa.

3.4. Case Analysis of Metrics

We can examine the range of values of the metrics discussed by an analysis of the possible extreme values. Let |R| = Z and consider a supported rule of interest F_jk. Then for F_jk, {S_j ∪ S_k} must appear at least once, but can in the extreme, however unlikely, appear as many as the maximum of Z times or occurrences. The range of counts for such rules is then

1 ≤ N_sp ≤ Z

3.4.1. Support and Confidence Analysis

So, the range for support, M_sp = N_sp/Z, is

1/Z ≤ M_sp ≤ Z/Z = 1

Since, for each occurrence of a rule F_jk the antecedent S_j must appear, its ranges are similarly

1 ≤ N_ant ≤ Z

Recall that confidence is M_cf = N_sp/N_ant. We analyze the possible cases in

Table 4. Confidence Ranges.

	Nsp = 1	Nsp = Z
Nant = 1	Mcf = 1	⌀ (not possible)
Nant = Z	Mcf = 1/Z	Mcf = Z/Z = 1

.

Hence, the range of M_cf is:

1/Z ≤ M_cf ≤ 1/1 = 1

3.4.2. Lift Analysis

Now, we can perform a similar extreme case analysis for lift. Consider the relationship of N_ant and N_con. For N_sp = 1, the antecedent, S_j,, and consequent, S_k, must both appear at least once, and independently can each appear up to the extreme of Z times. For N_sp = Z, they must both appear Z times. The analysis of the cases for the range of lift is in

Table 5. Range of values for Lift: (N_sp/N_ant) * (|R|/N_con).

		Lift	Lift
Nant	Ncon	Nsp = 1	Nsp = z
1	1	1*Z/1*1 = Z	⌀ (not possible)
1	Z	1*Z/1*Z = 1	⌀ (not possible)
Z	1	1*Z/Z*1 = 1	⌀ (not possible)
Z	Z	1*Z/Z*Z = 1/Z	Z*Z/Z*Z = 1

.

From Table 5, the range for lift is:

1/Z ≤ Lift ≤ Z

3.4.3. Conviction Analysis

Finally, we examine conviction

Conviction = (1 − M_con)/(1 − M_cf)

As for the antecedent, 1 ≤ N_con ≤ Z. Then, since M_con = N_con/Z

1/Z ≤ M_con ≤ 1

Since 1/Z ≤ M_cf ≤ 1 and 1/Z ≤ M_con ≤ 1, the ranges for both the numerator and denominator are: [1 − 1/Z, 1 − 1] = [(Z − 1)/Z, 0)]. However M_con and M_cf cannot both be 1, so there is not a 0/0 case. Then, for conviction the range is:

0 ≤ Conviction ≤ +∞

4. Apriori Procedure

As discussed, a major issue for finding association rules is the combinatorial complexity of computing all potential appropriate combinations of data items. This issue has been addressed by developing algorithms using the Apriori property [41]. Examples of the approach are described in this section.

An overview of the overall approach for discovering strong association rules can be formulated in three stages:

A.

Computing the frequent item sets: This is performed using the support metric for evaluation and utilizing the Apriori property to simplify the search.

B.

Determining strong association rules: From the frequent item sets in the first stage, the confidence metric is used in the evaluation to determine strong rules.

C.

Evaluating effectiveness of the resulting strong rules: Interestingness metrics, such as lift and conviction, are used in the selection of the most useful strong rules.

We will illustrate some possible frequent item sets using an example from the recreation locations application. A major issue is that there is a combinatorially large number of possible frequent item sets. The Apriori algorithm is commonly used to reduce computational complexity. It makes use of the prior knowledge of the support frequency to help reduce the generation of frequent sets. This property means that all subsets of a frequent set are frequent and if a set is not frequent all of its supersets are not frequent. The basic characteristic of the Apriori property is that it treats the support measure as being anti-monotonic.

Apriori Example of Frequent Set Generation

Finding frequent item sets is an iterative process that determines the next candidate frequent set from previous ones. The search generates the next candidate k + 1 level item set from the co-join of the previous k level item set. The Apriori property is then used to prune the search by eliminating possible sets from the generated set. The process follows as all item supersets of any item set that is not frequent are not frequent and can be eliminated. This terminates when no new frequent sets are generated.

We illustrate this with data similar to the previous discussion, with the same item set,

E = {S₁: camp; S₂: fish; S₃: hike; S₄: raft; S₅: ski},

but suitable to illustrate the approach for computing frequent sets,

Table 6. Example results for Apriori process.

Query Responses	Location Features
R1	{S1, S2, S4}: camp, fish, raft
R2	{S2, S5}: fish, ski
R3	{S2, S3}: fish, hike
R4	{S1, S3}: camp, hike
R5	{S1, S, S4, S5}: camp, fish, raft, ski
R6	{S2, S3}: fish, hike,
R7	{S1, S3}: camp, hike
R8	{S1, S2, S3, S4}: camp, fish, hike, raft
R9	{S1, S2, S3}: camp, fish, hike

.

To start the algorithm, we determine the support for each of the five features, as their support values determine the frequent feature sets.

For simplicity, we will use the first letter of the features for the rest of this example.

The iterative process starts using

Table 7. Example features.

Feature	Support
S1: Camp	6/9–0.66
S2: Fish	7/9–0.77
S3: Hike	6/9–0.66
S4: Raft	3/9–0.33
S5: Ski	2/9–0.22

as the candidate set C₁ and generates the next possible set C₂ by a join, (C₁ ⊕ C₁), of the items for the next set of candidates:

{CF, CH, CS, CR, FH FS, FR, HS, HR, SR}

Then we apply the Apriori condition using Table 7, where a set is pruned if any of its subsets are not above the support count threshold. For example, the set CH has C and H as subsets both with 0.66 support above the threshold and so CH is not pruned. However, if our support threshold Th_sp is 0.3 then any set with S as a subset will be pruned.

Again, any sets with S as a subset, {CS, HS, FS, RS}, are pruned, since S is not frequent, and we obtain as the next candidate set, C₂,

Table 8. Candidate set C_2.

Item-Set	Support
S1 ⊕ S2: CF	4/9–0.44
S1⊕ S3: CH	4/9–0.44
S1 ⊕ S4: CR	3/9–0.33
S2 ⊕ S3: FH	4/9–0.44
S2 ⊕ S4: FR	3/9–0.33
S3 ⊕ S4: HR	1/9–0.11

.

From this candidate set we generate the next stage by joining C₂ and C₂ giving:

{CFH, CFR, CHR, FHR}

Now, these must be checked to see if all subsets are frequent. For example, the subsets of {CFH} are {CF, CH, FH}, all of which are frequent. For {FHR} the subsets are {FH, FR, HR}, and HR is not frequent, and it is pruned. Similarly, CHR is pruned. So, C₃ = {CFH, CFR} and the join of these is {CFHR}. Since FHR is a non-frequent subset we go no further and the final result is C₃.

5. Uncertainty Querying

In this section extensions to the use of intuitionistic fuzzy sets for association rules are developed based on extensions of the metrics. The examples used to provide illustrations of the approach are based on the running example of the querying of vacation locations.

We first examine more closely our example of querying of vacation locations described in Table 1. As well as the specific features for each site, there are usually criteria such as distance, costs, and location desirability influencing the user evaluation. With these subjective criteria specified by linguistic values such as lower cost, nearness, or pleasantness of location, we would then obtain a degree of the suitability of each location retrieved on this basis. We can use the term “desirable” for the combination of the factors and capture this using a fuzzy set representation for membership in the set of desirable locations. Basic fuzzy sets were used in previous research [38], and here we want to extend this to more flexible representations, including intuitionistic-based fuzzy memberships.

5.1. Fuzzy Intuitionistic Measures for Support and Confidence

Next we must consider how to deal with the uncertainty using intuitionistic fuzzy set representations of subjective results of an operation such as a query. In the cases here for a query response, R_i, we consider an intuitionistic fuzzy membership in R for the query.

{<R_i = {e_j, …e_k}, m_R(R_i), m*_R (R_i)>}

To determine frequent feature sets it is necessary to calculate the number of responses R_i that support the rule F_jk. For crisp operations, the support count N_sp is simply the size or cardinality of the set R_i. However, since we have a fuzzy membership, we must adapt the support count. For the case of a query with simple fuzzy membership, this was modeled using the set cardinality for fuzzy sets [42] as the sigma count, which is simply the sum of its membership values.

$$\mathrm{Card}\left(\mathrm{FS}\right(\mathrm{D}\left)\right)={\sum }_{\mathrm{i}=1}^{\mathrm{n}}\mathrm{m}\left({\mathrm{a}}_{\mathrm{i}}\right), {\mathrm{a}}_{\mathrm{i}}\in \mathrm{D}$$

5.1.1. Cardinality of Intuitionistic Fuzzy Sets

The cardinality of intuitionistic-valued fuzzy sets (IFS) is needed in the procedure of determining association rules [43,44]. The development of the cardinality of an IFS set follows a geometrical framework [45]. Specifically, they define two bounds, the least cardinality:

$$\mathrm{Min} \mathrm{Card} \left(\mathrm{IFS}\right(\mathrm{D}\left)\right)={\sum }_{\mathrm{i}=1}^{\mathrm{n}}{\mathrm{m}}_{\mathrm{S}}\left({\mathrm{a}}_{\mathrm{i}}\right)$$

and the maximum cardinality:

$$\begin{gathered} \mathrm{Max} \mathrm{Card} \left(\mathrm{IFS}\right(\mathrm{D}\left)\right)={\sum }_{\mathrm{i}=1}^{\mathrm{n}}{(\mathrm{m}}_{\mathrm{S}}\left({\mathrm{a}}_{\mathrm{i}}\right)+{\mathrm{h}}_{\mathrm{S}}\left({\mathrm{a}}_{\mathrm{i}}\right))={\sum }_{\mathrm{i}=1}^{\mathrm{n}}{(\mathrm{m}}_{\mathrm{S}}\left({\mathrm{a}}_{\mathrm{i}}\right)+1-{(\mathrm{m}}_{\mathrm{S}}\left({\mathrm{a}}_{\mathrm{i}}\right)+{\mathrm{m}*}_{\mathrm{S}}\left({\mathrm{a}}_{\mathrm{i}}\right)\left)\right) \\ ={\sum }_{\mathrm{i}=1}^{\mathrm{n}}(1-{\mathrm{m}*}_{\mathrm{S}}\left({\mathrm{a}}_{\mathrm{i}}\right)) \end{gathered}$$

Then, the overall cardinality is the interval of the least and maximum values:

Card(IFS(D)) = [Min Card (IFS(D)), Max Card (IFS(D))]

An interval may not be as convenient to use in calculations, so the average possibility cardinality AVCard can also be used:

$$\begin{gathered} \mathrm{AVcard}\left(\mathrm{IFS}\right(\mathrm{D}\left)\right)=½ ({\sum }_{\mathrm{i}=1}^{\mathrm{n}}({\mathrm{m}}_{\mathrm{S}}\left({\mathrm{a}}_{\mathrm{i}}\right)+1-\mathrm{m}{*}_{\mathrm{S}}\left({\mathrm{a}}_{\mathrm{i}}\right))=½ ({\sum }_{\mathrm{i}=1}^{\mathrm{n}}({\mathrm{m}}_{\mathrm{S}}\left({\mathrm{a}}_{\mathrm{i}}\right)+{\mathrm{m}}_{\mathrm{S}}\left({\mathrm{a}}_{\mathrm{i}}\right)+{\mathrm{h}}_{\mathrm{S}}\left({\mathrm{a}}_{\mathrm{i}}\right)) \\ ={\sum }_{\mathrm{i}=1}^{\mathrm{n}}\left({\mathrm{m}}_{\mathrm{S}}\right({\mathrm{a}}_{\mathrm{i}})+{\mathrm{h}}_{\mathrm{S}}({\mathrm{a}}_{\mathrm{i}})/2) \end{gathered}$$

It is noted that this is the midpoint of the interval of the Min–Max cardinalities for the IFS.

5.1.2. Intuitionistic Metrics

Now, we can develop the support and confidence measures for fuzzy intuitionistic memberships using these cardinality approaches. First adapting the counts, FN_sp, FN_ant, FN_con, for a rule F_jk we must define for each count, an index set.

I(sp) = {i|S_j ∪ S_k ⊆ R_i}; I(ant) = {i|S_j ⊆ R_i}; I(con) = {i|S_k ⊆ R_i};

Since the cardinality we use here is an interval, there are two measures for the Min and Max cardinality, respectively, in the counts:

FN_sp = |{<R_i, m_R(R_i), m*_R (R_i)>|S_j ∪ S_k ⊆ R_i}|

$${\mathrm{MinFN}}_{\mathrm{sp}}=\mathrm{Min}|\{<{\mathrm{R}}_{\mathrm{i}}, {\mathrm{m}}_{\mathbf{R}} \left({\mathrm{R}}_{\mathrm{i}}\right), \mathrm{m}{*}_{\mathbf{R}} \left({\mathrm{R}}_{\mathrm{i}}\right)>\}|={\sum }_{\mathrm{i}\in \mathrm{I}\left(\mathrm{s}\mathrm{p}\right)}{\mathrm{m}}_{\mathbf{R}} \left({\mathrm{R}}_{\mathrm{i}}\right)$$

$$\mathrm{MaxFN}{\mathrm{sp}}_{ }=\mathrm{Max}|\{<{\mathrm{R}}_{\mathrm{i}}, {\mathrm{m}}_{\mathbf{R}}\left({\mathrm{R}}_{\mathrm{i}}\right), \mathrm{m}{*}_{\mathbf{R}}\left({\mathrm{R}}_{\mathrm{i}}\right)>\}|={\sum }_{\mathrm{i}\in \mathrm{I}\left(\mathrm{s}\mathrm{p}\right)}({\mathrm{m}}_{\mathbf{R}}\left({\mathrm{R}}_{\mathrm{i}}\right)+{\mathrm{h}}_{\mathbf{R}}\left({\mathrm{R}}_{\mathrm{i}}\right))={\sum }_{\mathrm{i}\in \mathrm{I}\left(\mathrm{s}\mathrm{p}\right)}(1-\mathrm{m}{*}_{\mathbf{R}}({\mathrm{R}}_{\mathrm{i}}\left)\right)$$

Similarly, for antecedent and consequent counts:

$$\begin{gathered} \mathrm{Min} {\mathrm{FN}}_{\mathrm{ant}}={\sum }_{\mathrm{i}\in \mathrm{I}\left(\mathrm{a}\mathrm{n}\mathrm{t}\right)}{\mathrm{m}}_{\mathbf{R}} \left({\mathrm{R}}_{\mathrm{i}}\right); \mathrm{Max} {\mathrm{FN}}_{\mathrm{ant}}={\sum }_{\mathrm{i}\in \mathrm{I}\left(\mathrm{a}\mathrm{n}\mathrm{t}\right)}(1-\mathrm{m}{*}_{\mathbf{R}}({\mathrm{R}}_{\mathrm{i}}\left)\right) \\ \mathrm{Min} {\mathrm{FN}}_{\mathrm{con}}={\sum }_{\mathrm{i}\in \mathrm{I}\left(\mathrm{c}\mathrm{o}\mathrm{n}\right)}{\mathrm{m}}_{\mathbf{R}} \left({\mathrm{R}}_{\mathrm{i}}\right); \mathrm{Max} \mathrm{FN}{\mathrm{con}}_{ }={\sum }_{\mathrm{i}\in \mathrm{I}\left(\mathrm{c}\mathrm{o}\mathrm{n}\right)}(1-\mathrm{m}{*}_{\mathbf{R}}({\mathrm{R}}_{\mathrm{i}}\left)\right) \end{gathered}$$

Now the measures become two values for support and confidence each. First for fuzzy supports:

MinFM_sp = MinFN_sp/|R|

MaxFM_sp = MaxFN_sp/|R|

Following a similar approach for the counts for the antecedent, we have a min and a max count. Then, to determine fuzzy confidence, we use::

MinFM_cf = MinFN_p/Min FN_ant

MaxFM_cf = MaxFN_sp/Max FN_ant

However, to proceed, we must consider that there are two possible interpretations of |R|. It is an issue of whether or not the size or cardinality of R should be based on the membership values. So we will use two interpretations of |R|:

$$1.\mathrm{Min}|\mathbf{R}|={\sum }_{\mathrm{i}=1}^{\mathrm{n}}{\mathrm{m}}_{\mathbf{R}}\left({\mathrm{R}}_{\mathrm{i}}\right) 2. \mathrm{Max} |\mathbf{R}|={\sum }_{\mathrm{i}=1}^{\mathrm{n}}(1-\mathrm{m}{*}_{\mathbf{R}}({\mathrm{R}}_{\mathrm{i}}\left)\right)$$

5.2. Fuzzy Query Example

We will first show the results of the query using the example of Table 1 with the example fuzzy memberships. Then we compute support and confidence using the extended measures we have developed.

Next, using the data in

Table 9. Query responses with intuitionistic uncertainty.

Query Responses	Location Features	Intuitionistic Membership (m, m*)
R1	{S1, S2, S5}: camp, fish, ski	<0.6, 0.3>
R2	{S1, S2, S4}: camp, fish, raft	<0.5, 0.3>
R3	{S1, S2, S4}: camp, fish, raft	<0.8, 0.2>
R4	{S1, S3}: camp, hike	<0.6, 0.4>
R5	{S1, S3, S4}: camp, hike, raft	<0.9, 0.1>
R6	{S2, S3, S5}: fish, hike, ski	<0.8, 0.1>
R7	{S1, S2, S3}: camp, fish, hike	<0.7, 0.2>

, we evaluate support and confidence for the same example rules as shown in Table 2.

5.3. Discussion of Results

It is clear that the most consistent use of |R| is to use the min value for the min support and the max value for the max support. These results for Min/Min and Max/Max produce values bracketing the support values for the crisp cases in Table 2. Averaging these produces values about 1% different from the crisp support values. Additionally, the confidence values are compatible with previous values. This shows that we can use the intuitionistic fuzzy sets to provide flexibility in capturing uncertainty in analyzing data and obtain useful results,

Table 10. Support and Confidence.

Rules: Fjk	MinFMsp Min|R|	MinFMsp Max |R|	MaxFMsp Min |R|	MaxFMsp Max |R|	MinFMcf	MaxFMcf
1. F12: camp → fish	0.529	0.479	0.615	0.557	0.63	0.67
2. F21: fish → camp	0.529	0.479	0.600	0.557	0.76	0.77
3. F31: hike → camp	0.449	0.402	0.472	0.428	0.76	0.74
4. F25: fish → ski	0.286	0.259	0.329	0.298	0.41	0.41
5. F52: ski → fish	0.286	0.259	0.329	0.298	1.0	1.0
6. F54: ski → raft	0.0	0.0	0.0	0.0	0.0	0.0
7. F{12}4:camp, fish → raft	0.271	0.246	0.30	0.272	1.0	1.0
8. F5{12}: ski → camp, fish	0.129	0.117	0.143	0.129	0.43	0.44

.

5.3.1. Effect of Negative Memberships

In our example of intuitionistic data in Table 9 we chose to focus only on stronger positive memberships to allow a consistent analysis of rules. Now we examine the effect if a few data values have higher negative memberships. Specifically, we will use a membership of <0.3, 0.6> for R₆ and then R₁ to compare the effects on rule support. For the case of R₆, we consider rules F₂₅ and F₅₂ as there is only one other entry, R₁, involved. We expect less significant changes for rules in which more data is involved, and the effect of the one change would not be expected to be as strong.

For rules F₂₅ and F₅₂, the change affects |R| and FN_sp:

Min|R| = 4.4; Max |R| = 4.9; Min FN_sp = 0.9; Max FN_sp = 1.1

So,

Min FM_sp = 0.9/4.4 = 0.205; Max FM_sp = 1.1/4.9 = 0.224

Then, the support for both rules has decreased, to a support of 28% for MinFM_sp and 25% for Max FM_sp.

Next, we replace the membership of R₁ with <0.3, 0.6> and compare the effect on F₁₂. Here,

Min|R| = 4.6; Max |R| = 5.1; Min FN_sp = 2.3; Max FN_sp = 2.7

Then,

Min FM_sp = 2.3/4.6 = 0.5; Max FM_sp = 2.7/5.1 = 0.529

As expected, the changes in the support are now much less—roughly 9.5% for both supports.

5.3.2. Lift Metric

Now, we examine the lift metric with the data of Table 9. Again, the results are consistent with the lift results of Table 3, as the same three rules, F₂₅, F₅₂, F_{12}4, have lift >1,

Table 11. Lift values for Intuitionistic Memberships.

Rules: Fjk	Lift Min	Lift Max
1. F12: camp → fish	0.91	0.92
2. F21: fish → camp	0.9	0.92
3. F31: hike → camp	0.9	0.89
4. F25: fish → ski	1.43	1.39
5. F52: ski → fish	1.44	1.38
6. F54: ski → raft	0	0
7. F{12}4:camp, fish → raft	1.1	1.2
8. F5{12}: ski → camp, fish	0.81	0.79

.

Finally, to be complete, we examine the same change in negative membership for R₆ and R₁ above. For F₂₅ and F₅₂, we see:

Lift Min: 1.52–6% increase; Lift Max: 1.44–3.5% increase.

For F₁₂, the lift value changes are marginal:

Lift Min: 0.90–1% decrease; Lift Max: 0.91–1% decrease.

These results are still consistent with previous values, since F₂₅ and F₅₂ have lift >1, and F₁₂ has lift <1. The increases for F₂₅ and F₅₂ reflect the change in the co-occurrence of the antecedents and consequents due to the increased negative membership as shown in Section 5.3.1 above. Additionally, for F₁₂ the change is negligible, again consistent with the smaller changes in its support for similar reasons.

6. Conclusions

We have shown that it is quite feasible to discover association rules appropriate for applications in which the data involves intuitionistic fuzzy set descriptions.

The extensions required were applications of the set cardinality for intuitionistic fuzzy sets for determining the counts used in the metrics. This produced consistent results for the support and confidence of rules. We also examined the effects of data with higher negative memberships in some cases. The results implied that the approaches were still valid, depending on the percentage of data with such memberships. Additionally, to provide insight into the metrics used in the approach, the ranges of support and confidence as well as lift and conviction were determined.

Since interval valued fuzzy sets have similar formulations, the use of such uncertainty measures can be considered next for association rules. Entropy measures can be used [22] to evaluate the IFS and IVFS in the association rule computations.