New Approach to Mining Fuzzy Association Rule with Linguistic Threshold Based on Hedge Algebras LeAnhPhuong Department of Computer Science Hue University of Education Hue University TranDinhKhang SoICT Hanoi University of Science and Technology NguyenVinhTrung Information Technology Center Hue University of Education Hue University New Approach to Mining Fuzzy Association Rule with Linguistic Threshold Based on Hedge Algebras E80B6D4256253B3AA0CE020DB94BB468 GROBID - A machine learning software for extracting information from scholarly documents fuzzy association rules linguistic threshold hedge algebra

The authors [2][3][4][5] have studied and presented the quantitative method of linguistic variables and linguistic threshold by fuzzy set. Chien-Hua Wang, Chin-Pang Tzong proposed an algorithms for mining fuzzy association rule [2]. In this paper, we extend the algorithms proposed in [2] for number data and linguistic variables by using hedge algebras.
Introduction

Data mining with the approach of association rules is one of important aspects in the field of data mining.

Many authors have presented various methods, algorithms of data mining by association rules with numerical support and confidence value. However, in reality, these values are natural linguistic ones. Besides, importance value of each item is evaluated not only by quantity, frequency of occurrence in each transaction but also by the qualitative evaluation of administrators (for those items) by natural language. And hedge algebra have met the requirements for directly processing calculation on linguistic value (without fuzzification, but with direct calculation based on qualitative semantic function and flexible calculation). Thus, it is necessary to establish a method of data mining by association rules with hedge algebra, in which the input is qualitative transactional database and qualitative evaluation table of those database items and the support, confidence values are also natural language ones.

Knowledge Base
Association rules

Let I = I 1 , I 2 , . . . , I m be a set of items. Let D, the task-relevant data, be a set of database transactions where each transaction T is a set of items, such is T ✓ I. Each transaction is associated with an identi er, called TID. confidence

(X ! Y ) = support(X [ Y ) support(X) = |X \ Y | |X|

Where: |X| is the number of transactions, including X; |X \ Y | is the number of transactions, including X and Y ; N is the total of transaction database.

Mining the association rules of the database is finding all of the rules that have the degree of support and confidence greater than degree of support minsup and confidence minconf determined by the available user.

Hedge algebras (HA)

Let X be a linguistic variable and X be a set of its terms, called a term-domain of X. E.g. if X is the rotation speed of an electrical motor and linguistic hedges used to describe its speed are V ery, More, P ossibly, Little, denoted correspondingly for short by V, M, P and L, then X = {fast, V fast, Mfast, LP fast, Lfast, P fast, Lslow, slow, P slow, V slow, ...} U 0, W, 1 is a term-domain of X.

It can be considered as an abstract algebra AX = (X, C, H, ), where H is a set of linguistic hedges, which can be regarded as one-argument operations,  is called a semantics-based ordering relation on X and W, 0, 1 is a set of constants in X with fast and slow being primary terms of X and W, 0, 1 being additional elements in X interpreted as the neutral, the least and the greatest ones, respectively. Denote by hx the result of applying an h 2 H to x 2 X and by H(x) the set of all u 2 X generated algebraically from x by using hedges in

H, i.e. H(x) = u: u = h n ...h 1 x, h 1 , ..., h n 2 H.

It is natural that there is a demand to transform fuzzy sets defined on a real interval [a, b], which represents the meaning of terms in a term-domain X, into [a, b] or, for normalization, into [0, 1]. This defines a mapping of the termdomain X into [0, 1], called in the algebraic approach a semantically quantifying mapping. Now, we take these mappings in mind to define a notion of fuzziness measure. Let us consider a mapping f from X into [0, 1], which preserves the ordering relation on X. Then, the "size" of the set H(x), for x 2 X, can be measured by the diameter of f (H(x)) ✓ [0, 1]. That is that this diameter will be considered as a fuzzy measure of the term x. Taking this model of fuzziness measure in mind, we may adopt the following definition:

Let AX = (X, C, H, ) be a linear HA. An fm: X ! [0, 1] is said to be a fuzzy measure of terms in X if: Definition 4. For each x 2 X, the length of x is denoted by |x|, and defined as follows:

1) if x = c + or x = c then |x| = 1. 2) if x = hx 0 then |x| = 1 + |x 0 |, for all h 2 H.

Proposition 1. The fuzziness measure (fm) and the fuzziness measure of hedge h, denoted by µ (h), 8h 2 H, with the following properties:

1) fm(hx) = µ(h) ⇥ fm(x) with 8x 2 X; 2) fm(c + ) + fm(c ) = 1; 3) P qip,i6 =0 fm(h i c) = fm(c), c 2 {c + , c }; 4) P qip,i6 =0 fm(h i x) = fm(x); 5) P qi 1 µ(h i ) = ↵, P 1jp µ(h j ) = , ↵ + = 1, (↵, > 0)

3 Algorithm Input:

-D: The data set includes n quantitative transactions; -Table qualitative: A set of m items with their importance evaluated by d managers; -A pre-defined linguistic minimum support valuemin s and linguistic minimum confidence valuemin c.

Output: A set of fuzzy association rules. Method: Includes 9 following general steps:

Step 1: Identify minsup, minconf from the pre-definedthreshold linguistic.

Transform min sas X variables in HA. Including:

+ Calculate the fuzzy of variable X: fm(X); + Identify fuzzy approximately of X:

I(X) = [a, b];

+ The fuzzy average value of the variable X:

gt(X) = a + b 2 ;

+ Similarly, the linguistic confidence min c; + Select linguistic thresholds (X, Y ), respectively to the fuzzy value of (X, Y ) as minsup, minconf: minsup(X) = gt(X); minconf (X) = gt(Y).

Step 2: Handling qualitative table : A set of m items with their importance evaluated by d managers + Calculate the fuzzy of linguistic variables; + Calculate the average o↵uzzy approximatelyqualitativeterms for all items.

kdt ⇠ tb (j) = 1 d ⇥ d X i=1 (a(j) i , b(j) i ) ; (has the form: [a j , b j ])

+ Calculate the average of fuzzy value for each item:

gtdt ⇠ tb (j) = a j + b j 2 ;

where: a j and b j are the values of kdt ⇠ tb (j), which kdt ⇠ tb (j) = [a j , b j ] Step 3: Handling n quantitative transactions.

+ Transform the quantitative valueas A j (j = (1, m)) as X variables in HA (X 2 X), determined as follows:

X sl = (X sl , G sl , H sl , ), with: G sl = {High,max count j = max(count ji ), with i = (1, K);

Step 4: Calculate the fuzzy support of each item (j = 1, m), as:

sup(j) = gtdt ⇠ tb (j) ⇥ max count j N ;

where gtdt ⇠ tb (j) is the qualitative value (calculated by formula (3), in step 2); max count j is the quantitative vaule (calculated by formula (4), in step 3); and N is the total number of transaction data, N = |D|.

Step 5: Filter out all items in D ⇠ , such that: satisfied frequent item of minimum support: sup(item) minsup.

Step 6: Establish Fuzzy FP-tree: establish Header table; establish FP-tree

Step 7: Calculate the fuzzy qualitative of n-itemset (K n 2). + Find out of all frequent itemsets (denote by n-itemset) from FP-tree; + Calculate the qualitative of n-itemset.

Step 8: Calculate the fuzzy support of each n-itemset.

+ Using the formula (5) -in step 4:

sup(n itemset) = gtdt ⇠ tb (j) ⇥ max count j N ;

+ Filter out all n-itemset, such that: satisfied frequent items of minimum support: sup(n itemset) minsup. (n 2)

Step 9: Export rules, calculate the confidence and check with minconf.

Using the following substeps:

+ Check the association rules from result of step 8, each n-itemset with items

(A 1 , A 2 , ..., A n ), (n = 2, M): A 1 ... ^A î 1 A i+1 ...A n ! A i ; (i = 1, M) + Calculate

the fuzzy confidence value of each possible fuzzy association rule as:

conf (A ! B) = sup(A [ B) sup(A) ;

+ Select the satisfied fuzzy association rule of minimum confidence. During use of HA for fuzzy transaction database and quantify of linguitics, we view each element of HA is a fuzzy region. So, the process of creating fuzzy region based on the structure of HA will simple, intuitive, and more cient. Output: A set of fuzzy association rules. Method: Includes 9 following general steps:

Step Table 3 is converted into Table 4, where kdt ⇠ tb is the average of fuzzy approximately qualitative; gtdt ⇠ tb is the average of fuzzy value. Step 3: Handling n quantitative transactions.

Transform the quantitative valueas A j (j = 1, m) as X variables in HA (X 2 X), determined as follows: Using formula (4), find out the largest fuzzy partition (result from table 6) as representative of each item: Step 6: Establish fuzzy FP-tree: see figure 1 Step 7: Calculate the fuzzy qualitative of n-itemset Substep 7.1: Find out of all frequent itemsets (denote by n-itemset) from FP-tree (see Table 11)

X sl = (X sl , G sl ,
Conclusion

The paper is an extension of the evaluation of fuzzy association rules was researched by Chien-Hua Wang and Chin-Pang Tzong [2], using algebras instead of fuzzy sets. The optimization of the parameters of quantitative semantic content in order to fit various problems will be discussed in our next papers.

Definition 1 .Definition 2 .Definition 3 .An association rule has the form of X ! Y , where X ✓ I, Y ✓ I, and X \ Y = ✓. The support of association rule X ! Y the probability that X [Y exists in a transaction in the database D. support(X ! Y ) = |X \ Y | |N | The confidence of the association rule X ! Y is the probability that X [ Y exists given that a transaction contains X, i.e.
Low}, (High = H, Low = L); c + = {H}; c = {L}; H + sl = {V ery, More}; H sl = {Less, P ossibly}; (with V ery > More; Less > P ossibly) -Selection: Dom(sl); fm(H); fm(L); fm(V); fm(M); fm(L); fm(P); -Identify fuzzy approximately of X is I(X), with X 2 X -Transform the quantitative value of item into [0, 1] respectively; With each A j 2 [0, 1] that into fuzzy approximately I(X), respectively; + Statistics of fuzzy partitions in D ⇠ + Find the largest fuzzy partition as representative of each item j th :
1 :Step 2 :Identify minsup, minconf from the pre-defined threshold linguistic Identify parameters in HA: X = (X, G, H, ), with: G = {Low, High}; c + = High (denoted by H); c = Low (denoted by L); H + = {V ery, More}, H = {Less, P ossibly}; (with: V ery > More; Less > P ossibly) with: fm(L) = 0.3; fm(H) = 0.7; fm(V ) = fm(M ) = fm(L) = fm(P ) = 0.25;Identify fuzzy degree and fuzzy approximately of X:With the variable X contains c = "Low":+ fm(V L) = 0.25 ⇥ 0.3 = 0.075 ) I(V L) = [0, 0.075] ) I(V L) T B = 3.75% + fm(ML) = 0.25 ⇥ 0.3 = 0.075 ) I(ML) = [0.075, 0.15] ) I(ML) T B = 11.25% + fm(P L) = 0.25 ⇥ 0.3 = 0.075 ) I(P L) = [0.15, 0.225] ) I(P L) T B = 18.75% + fm(LL) = 0.25 ⇥ 0.3 = 0.075 ) I(LL) = [0.225, 0.3] ) I(LL) T B = 26.25% Similar, with the variable X contains c + = "High": + fm(LH) = 0.25⇥0.7 = 0.175 ) I(LH) = [0.3, 0.475] ) I(LH) T B = 38.75% + fm(P H) = 0.25 ⇥ 0.7 = 0.175 ) I(P H) = [0.475, 0.65] ) I(P H) T B = 56.25% + fm(MH) = 0.25 ⇥ 0.7 = 0.175 ) I(MH) = [0.65, 0.825] ) I(MH) T B = 73.75% + fm(V H) = 0.25 ⇥ 0.7 = 0.175 ) I(V H) = [0.825, 0.1] ) I(V H) T B = 91.25% -Select minsupport with linguistic thresholds as "Less Low" (denoted by LL) minsup = minsup(LL) = 26.25% -Select minconf with linguistic thresholds as "More High" (denoted by MH) minconf = minconf (MH) = 73.75% Handling qualitative table: A set of m items with their importance evaluated by 03 managers. Identify parameters in HA: Denote: I: Important; uI: UnImportant; O: Ordinary; VI: Very Important; VuI: Very UnImportant; X qt = (X qt , G qt , H qt , ), with: G qt = {Important, U nImportant}; c + = Important; c = U nImportant; H + qt = {V ery, More}; H qt = {Less, P ossibly}; (with: V ery > More; Less > P ossibly). Let: W qt = 0.5; fm(I) = 0.4; fm(uI) = 0.6; fm(V ) = 0.3; fm(M ) = 0.2; fm(L) = 0.3; fm(P ) = 0.2; Should have: fm(V I) = 0.3 ⇥ 0.4 = 0.12 ) I(V I) = [0.88, 1]; fm(V uI) = 0.3 ⇥ 0.6 = 0.18 ) I(V uI) = [0, 0.18]; fm(O) = 0.5 ) I(O) = [0.25, 0.75];
H sl , ), with: G sl = {c , c + }, with: c + = High (denoted by H); c = Low (denoted by L); H + sl = {V ery, More}; H sl = {Less, P ossibly}; (with: V ery > More; Less > P ossibly) (V ery, More, Less, P ossibly denoted by: V , M , L, P respectively) Let: Dom(sl) = [0, 13]; fm(H) = 0.4; fm(L) = 0.6; fm(V ) = 0.15; fm(M ) = 0.25; fm(L) = 0.35; fm(P ) = 0.25; Should have: fm(V L) = 0.15 ⇥ 0.6 = 0.09; fm(ML) = 0.25 ⇥ 0.6 = 0.15; fm(P L) = 0.25 ⇥ 0.6 = 0.15; fm(LL) = 0.35 ⇥ 0.6 = 0.21; Because: V L < ML < Low < P L < LL, should: I(V L) = [0, 0.09]; I(ML) = [0.09, 0.24]; I(P L) = [0.24, 0.39]; I(LL) = [0.39, 0.6]; Similar: fm(V H) = 0.15 ⇥ 0.4 = 0.06; fm(MH) = 0.25 ⇥ 0.4 = 0.1; fm(P H) = 0.25 ⇥ 0.4 = 0.1; fm(LH) = 0.35 ⇥ 0.4 = 0.14; Because: V H > MH > High > P L > LH, should: I(LH) = [0.6, 0.74]; I(P H) = [0.74, 0.84]; I(MH) = [0.84, 0.94]; I(V H) = [0.94, 1.0]. From: Dom(sl) = 2, 3, 4, 5, 7, 8, 9, 10 convert into [0, 1] Converted into: Dom(sl) = {0.15, 0.23, 0.
Table 1 .The symbols used in the algorithmSymbol The meaningSymbol The meaningDtransaction databaseD ⇠fuzzy transaction databaseminsupminimum supportminconf minimum confidencemin sthreshold language of minsupmin cthreshold language of minconfNthe total number of transac-Mthe total number of itemstion datadthe total number of managersVhedge "Very"Xlinguistics variableMhedge "More"Phedge "Possibly"Lhedge "Less"KThe number of fuzzy parti-tions in each items
Table 3 .The item importance evaluated by three managersItemManager 1Manger 2Manager 3AImportantOrdinaryOrdinaryBVery ImportantImportantImportantCOrdinaryImportantImportantDUnImportantUnImportantVery UnImportantEImportantImportantImportantFImportantImportantOrdinary
Table 4 .The item importance evaluated by three managersItemManager 1 Manger 2Manager 3 kdt ⇠ tbgtdt ⇠ tbA[0.6, 1][0.25, 0.75][0.25, 0.75][0.367, 0.833] 0.6B[0.88, 1][0.6, 1][0.6, 1][0.693, 1]0.85C[0.25, 0.75][0.6, 1][0.6, 1][0.483, 0.92]0.7D[0, 0.6][0, 0.6][0, 0.18][0, 0.46]0.23E[0.6, 1][0.6, 1][0.6, 1][0.6, 1]0.8F[0.6, 1][0.6, 1][0.25, 0.75][0.483, 0.92]0.7
Table 5 .Database transaction was fuzzy (denoted by D ⇠ )TID Fuzzy items1(0.23/A.ML) (0.3/B.PL) (0.15/C.ML) (0.23/D.ML) (0.53/E.LL) (0.15/F.ML)2(0.23/A.ML) (0.53/B.LL) (0.23/D.ML) (0.76/E.PH) (0.53/F.LL)3(0.15/A.ML) (0.76/B.PH) (0.38/C.PL) (0.15/D.ML) (0.76/E.PH) (0.53/F.LL)4(0.76/B.PH) (0.76/C.PH) (0.76/E.PH) (0.76/F.PH)5(0.53/A.LL) (0.53/D.LL) (0.53/E.LL) (0.76/F.PH)6(0.15A.ML) (0.76/B.PH) (0.15/D.ML) (0.76/E.PH)(0.76/F.PH)
Table 6 .Statistics of fuzzy partitionsFuzzy item CountFuzzy item CountA.ML0.76D.ML0.76A.LL0.53D.LL0.53B.PL0.30E.LL1.06B.LL0.53E.PH3.04B.PH2.28E.LL0.53C.ML0.15F.ML0.15C.ML0.38F.LL1.06C.PH0.76F.PH2.28
Table 7 .Fuzzy itemFuzzy item CountFuzzy item CountE.PH3.04A.ML0.76F.PH2.28D.ML0.76B.PH2.28C.PH0.76Step 4: Calculate the fuzzy support of each item (1-itemset).Using formula (5): For example with item E.P H:+ fuzzy approximately of support: ([0.6, 1] ⇥ 3.04)/6 = [0.304, 0.51]; + fuzzy value of support: (0.304 + 0.51)/2 = 0.41 = 41%.Step 5: Filter out all items in D ⇠ . Such that: satisfied frequent item ofminimum support: sup(item) minsup.If: sup(item) < minsup (with: minsup = 26.25%, result at Step 1)Then: remove item in table 8.
Table 8 .Fuzzy supportItem fuzzy Fuzzy approximately Fuzzy supportE.PH(0.304, 0.51)41%F.PH B.PH A.ML27% 32% (0.367, 0.833) ⇥ 0.76/6 7.6% (0.483, 0.92) ⇥ 2.28/6 (0.693, 1) ⇥ 2.28/6Establish Header table
Table 9 .HeaderItem fuzzy SupportE.PH41%B.PH32%F.PH27%
Table 10 .Filter D ⇠TID Transaction1 (0.76/E.PH)2 (0.76/B.PH) (0.76/E.PH)3 (0.76/B.PH) (0.76/E.PH) (0.76/F.PH)4 (0.76/F.PH)5 (0.76/B.PH) (0.76/E.PH) (0.76/F.PH)
Fig. 1. Tree FP-tree Fig. 2. Fuzzy approximately of 2 items on the qualitative attributes Substep 7.2: Calculate the fuzzyqualitative of n-itemset. For example with itemset BF: Fuzzyqualitative of B, F as [0.483, 0.92], [0.693,1], respectiely in figure 2. Fuzzyqualitative of itemset BF as [0.693, 0.92]. Similar for other itemset. Step 8: Calculate the fuzzy support of each n-itemset (n 2)Using the formula (5), example for itemset FE:
Table 11 .Itemset should check the frequently 2-item 3-item F.PH, B.PH: 1.52; F.PH, E.PH: 1.52; B.PH, E.PH: 2.28 F.PH, B.PH, E.PH: 1.52
Table 12 .Fuzzy approximately of 2 items on the qualitative attributes Result, we have 2 rules: + If E.PH then B.PH with a LL support and a MH confidence. If a Possibly High number of item E is bought, then a Possibly High number of item B is bought with a Less Low support and a MoreHigh confidence. + If B.PH then E.PH with a LL support and a VH confidence. If a Possibly High number of item B is bought, then a Possibly High number of item E is bought with a Less Low support and a Very High confidence.
Table 13. Supportof itemsetitemsetkdt ⇠ tbgtdt ⇠ tbItemsetSupport Minsup = 26.25%F.PH, B.PH (0.693, 0.92) 81%F.PH, E.PH 19%unselectedF.PH, E.PH (0.6, 0.92)76%F.PH, B.PH 21%unselectedB.PH, E.PH(0.693, 1)85%E.PH, B.PH 32%selectedF.PH, B.PH, (0.693, 0.92) 81%F.PH, B.PH, 21%unselectedE.PHE.PH
An example

In this section, an example is given to illustrate the proposed algorithm. Input: includes three data follows:

1. The data set includes six quantitative transactions, as show in Table 2.

2. The importance of the items is evaluated by three managers as shown in Table 3.

3. A pre-defined linguistic minimum support value min s and linguistic minimum confidence value min c.

Improve e ciency of fuzzy association rule using hedge algebra approach TranThai SonNguyen AnhTuan Journal of Computer Science and Cybernetics 30 4 2014 Finding Fuzzy Association Rules Using FWFP-Growth with linguistic Supports and Confidences Chien-HuaWang Chin-TzongPang World Academy of Science, Engineering and Technology 29 2009 Mining association rules uses fuzzy weighted FP-growth, Soft Computing and Intelligent Systems Chien-HuaWang Chin-TzongPang Sheng-HsingLiu SCIS) and 13th International Symposium on Advanced Intelligent Systems (ISIS) 2012. 2012 13498461 Joint 6th International Conference on Lingguitic data mining with fuzzy FP-trees Tzung-PeiHong Chun-WeiLin Wen-HsiangLu Expert Systems with Applications 37 2010 Data Mining with Linguistic Thresholds Tzung-PeiHong Minh-JerChiang Shyue-LiangWang Int.Jcontemp. Math. Sciences 7 35 2012