传统电脑决策.ppt

1、The Application of Fuzzy Sets on Data Mining,Prof. Tzung-Pei Hong Department of Electrical Engineering National University of Kaohsiung,Outline,Introduction Review Data Mining Fuzzy Sets Fuzzy Data Mining Fuzzy Association Rules (I) Fuzzy Association Rules (II) Fuzzy Generalized Association Rules Fu

2、zzy Web Mining,Outline,Review of GA Fuzzy data mining for membership functions and rules Two approaches Conclusion,Reasons for data mining,Reasons for data mining,Mining association rules,Bread,Milk,IF bread is bought then milk is bought,The role of data mining,Useful patterns,Transaction data,Prepr

3、ocess data,Data Mining,Knowledge and strategy,Different kinds of knowledge,Association rules Generalized association rules Sequential patterns Quantitative association rules Classification rules Clustering rules etc,Focus,Mining association rules,Bread,Milk,IF bread is bought then milk is bought,Apr

4、iori Algorithm,Proposed by Agrawal et al. Step1:Define minsup and minconf ex: minsup=50% minconf=50% Step2:Find large itemsets Step3:Generate association rules,Example,Large itemsets,Scan Database,Scan Database,Scan Database,Itemset,Sup.,A,2,B,3,C,3,E,3,L,1,Example,Fuzzy Sets,傳統電腦決策 不是對(1)就是錯(0) 例如：

5、25歲以上是青年，那26歲就是中年? 60分以上是及格，那60分以下就是不及格 何謂模糊 在對(1)與錯(0)之間，再多加幾個等級 幾乎對(0.8) 可能對(0.6) 可能錯(0.4) 幾乎錯(0.2),Fuzzy Sets,Question:168公分到底算不算高?,身高(Cm),中,矮,高,170,180,160,隸屬度,再多分成幾級 連續,Example:“Close to 0”,e.g. A(3) = 0.01 A(1) = 0.09 A(0.25) = 0.62 A(0) = 1 Define a Membership Function: A(x) =,Example:“Close

6、to 0”,Very Close to 0: A(x) =,Fuzzy Set (Cont.),Membership function 0, 1 e.g. sunny : x 0, 1,Fuzzy Set,Simple Intuitively pleasing A generalization of crisp set Vague member non-member,0 or 1,Non-member member,gradual,Fuzzy Operations,交集(AND) 取較小的可能性 EX:學生聰明(0.8) 而且 用功(0.6) 則是模範生(0.6) 聯集(OR) 取較大的可能性

7、 EX:學生聰明(0.8) 或者 用功(0.6) 則是模範生(0.8) 反面(NOT) 取與1的差 EX:學生聰明是0.8, 則學生不聰明0.2,Fuzzy Inference Example,洪老師找小老婆的條件 (大眼睛而且小嘴巴)或者是身材好 Question : 誰是最佳女主角,大眼睛小嘴巴身材好 陶晶瑩00.80.3 張惠妹10.60.8 李玟00.30.9 李心潔 蔡依林,Answer,對陶晶瑩= (0 AND 0.8) OR 0.3 = 0 OR 0.3 = 0.3 對張惠妹= (1 AND 0.6) OR 0.8 = 0.8 對李玟= (0

8、AND 0.3) OR 0.9 = 0.9 對李心潔= (0.7 AND 0.1) OR 0.5 = 0.5 對蔡依林= (0.8 AND 0.5) OR 0.3 = 0.5 李玟 為最佳選擇!,謝謝!,Fuzzy Decision,A = A1, A2, A3, A4, A5 A set of alternatives C = C1, C2, C3 A set of criteria,Example (Cont.),Assume : C1 and C2 or C3 E (Ai) : evaluation function E (A1) = (0 0.8) 0.3 = 0 0.3 = 0.3

9、E (A2) = (1 0.6) 0.8 = 0.6 0.8 = 0.8 E (A3) = (0 0.3) 0.9 = 0 0.9 = 0.9 the best choice E (A4) = (0.7 0.1) 0.5 = 0.1 0.5 = 0.5 E (A5) = (0.8 0.5) 0.3 = 0.5 0.3 = 0.5,Motivation for Fuzzy Mining,In real-world applications Transactions with quantitative values Using fuzzy sets to process it,Fuzzy Data

10、 Mining,Solving quantitative values e.g. John buys 10 bread, 2 butter and 3 Milk. Fuzzy Data Mining Much Bread and Little Butter Middle Amount of Milk,Fuzzy data mining,Quantitative data,Linguistic term,Membership function,0 1 6 11,Low,Middle,High,1 0,Membership value,Number of item,Main Idea,Numeri

11、c Database,Fuzzy Data Mining,Knowledge,If milk.Middle Then cookies.Low,Related research,Lee and Hyung, 1997 -cut Converting the membership tuples to binary tuples Pedrycz, 1996, 1998 Running the FCM (Fuzzy C-Means) method Solving cluster problem,Related research,Chan and his co-workers, 1997 Maddour

12、i et al., 1998 Rubin, 1998 Han et al. , 1998 Using Machine learning method Combining data mining,Fuzzy Mining Algorithm,Input n quantitative transaction data m attributes A set of membership functions Two thresholds Minimum support = Minimum confidence = Output A set of fuzzy association rules,Fuzzy

13、 Mining Algorithm,Step 1 Transform the quantitative value of each transaction datum into a fuzzy set using the given membership functions. Step 2 Calculate the scalar cardinality of each attribute region in the transaction data,Fuzzy Mining Algorithm,Step 3 For each fuzzy region, check whether it is

14、 in the set of large 1-itemsets (L1 ) Step 4 Set r = 1, where r is used to represent the number of items kept in the current large itemsets,Fuzzy Mining Algorithm,Step 5 Generate the candidate set Cr+1 from Lr in a way similar to that in the apriori algorithm except that two regions belonging to the

15、 same attribute cannot simultaneously exist in an itemset in Cr+1.,Fuzzy Mining Algorithm,Step 6 Do the following substeps for each newly formed candidate (r+1)-itemset s with items in Cr+1 : Step 6.1 : Calculate the fuzzy value of each transaction data in s ; Step 6.2: Calculate the scalar cardinal

16、ity of s on the transactions; Step 6.3: If counts is larger than or equal to the predefined minimum support value, put s in Lr+1,Fuzzy Mining Algorithm,Step 7 IF Lr+1 is null, then do the next step; otherwise, set r=r+1 and repeat STEPs 5 to 7. Step 8 Construct the association rules for all large q-

17、itemset s with items, using the following substeps: Step 8.1: Form all possible association rule: Step 8.2: Calculate the confidence values of all association rules: Step 9 Output the rules with confidence values larger than or equal to the predefined confidence threshold ,An Example,Generating asso

18、ciation rules for course grades According to historical data concerning students course scores. The data set 10 transactions. Each case consists of five course scores Object-Oriented Programming (denoted OOP), Database (denoted DB), Statistics (denoted ST), Data Structure (denoted DS), Management In

19、formation System (denoted MIS).,Transactions,The set of students course scores in the example Minsup=1.5, Minconf=0.7,Membership Functions,STEP 1,Transform the quantitative values of each transaction datum into fuzzy sets. e.g. Score=86,STEP 2,Calculate the scalar cardinality of each attribute regio

20、n in the transactions as the count value,STEP 3,Checking count minimum support value (1.5) The contents of L1 for this example,An Example,STEP 4 Set r=1 STEP 5 Generate the candidate set Cr+1 from Lr e.g. (OOP.Middle, DB.Middle), (OOP.Middle, DB.High) (OOP.Middle, ST.Middle), (OOP.Middle, ST.High) (

21、OOP.Middle, DS.Middle), (OOP.Middle, DS.High) (OOP.Middle, MIS.Middle), (OOP.Middle,MIS.High) , (DS.High, MIS.Middle), and (DS.High, MIS.High),STEP 6,Do the following substeps for each newly formed candidate itemset Step 6.1 Calculate the fuzzy membership value of each transaction datum e.g.,STEP 6,

22、Step 6.2 Calculate the scalar cardinality (count) of each candidate 2-itemset in the transaction data,STEP 6,Step 6.3 Check whether these counts are larger than or equal to the predefined minimum support value 1.5 Result (OOP.Middle, DB.High), (OOP.Middle, ST.Middle) (OOP.Middle, ST.High), (OOP.Midd

23、le, DS.Middle) (OOP.Middle, DS.High), (OOP.High, DB.Middle) (OOP.High, MIS.High), (DB.Middle, MIS.High) (DB.High, ST.High), (DB.High, DS.Middle) (ST.High, DS.Middle), (ST.High, MIS.Middle) (ST.High, MIS.High), and (DS.Middle, MIS.Middle),STEP 7,IF Lr+1 is null, then do the next step; otherwise, set

24、r = r+1 and repeat STEPs 5 to 7 e.g: The itemsets and their support values in L3,STEP 8,Construct the association rules for each large itemset using the following substeps Step 8.1 Form all possible association rules e.g: (OOP.Middle , DB.High, DS.Middle) If OOP.Middle and DB.High then DS.Middle. If

25、 OOP.Middle and DS.Middle then DB.High. If DB.High and DS.Middle then OOP.Middle.,STEP 8,Step 8.2 Calculate the confidence factors for the above association rules e.g. Rule If OOP.Middle and DB.High then DS.Middle The counts of OOP.Middle DB.High OOP.Middle DB.High DS.Middle,Confidence,= = 0.73,STEP

26、 9,Check whether the confidence factors of the above association rules are larger than or equal to the predefined confidence threshold,Fuzzy association rules,12 rules If OOP.Middle and DS.Middle then DB.High “, conf=0.94 If ST.Middle then OOP.Middle “, conf=0.94 If DB.High and ST.High then DS.Middl

27、e,conf=0.86 If MIS.Middle then ST.High , conf=0.83 If DS.Middle then MIS.Middle “, conf=0.78 If OOP.High then DB.Middle “, conf=0.74 If OOP.Middle and DB.High then DS.Middle“, conf=0.73 If DS.Middle then ST.High “, conf=0.72 If DB.Middle then OOP.High , conf=0.71 If DB.High then DS.Middle “, conf=0.

28、71 If DB.High and DS.Middle then ST.High “, conf=0.70 If OOP.High then MIS.High “, conf=0.70,Another Variant,Use only the region with the maximum fuzzy cardinality for each item,Results,L1,L2,Results,Less number of large itemsets Not complete Less computation time,L3,Taxonomy,Only the terminal items

29、 can appear in transaction data,Mining under taxonomy,Many Approaches Here, by Agrawal and Srikants approach Step 1: Define minsup and minconf ex: minsup=50% minconf=50% Step 2: Generate expanded transaction data Step 3: Find large itemsets Step 4: Generate association rules Step 5: Check interest o

30、f association rules,Step 2,Generate expanded transaction ancestors are added.,Step 5,Rule Interest Criteria: 1. A rule with no ancestor rules mined out, 2.The support value of a rule being R-time larger than the expected support values of its ancestor rules 3.The confidence value of a rule being R-t

31、ime larger than the expected confidence values of its ancestor rules.,Algorithm,Input Quantitative transaction dataset Membership functions Taxonomy Three Thresholds Min-support Min-confidence R-interest Output Fuzzy interesting generalized association rules,Example,Quantitative transaction dataset

32、Transaction ID Some purchased items with quantities Taxonomy Only the terminal items can appear in transaction data,T2 T1 C A B,T3 D E,Taxonomy,Step 1,Generate expanded transaction Ancestors are appended Quantities are added,Step 2,Transform the quantitative data into fuzzy data Using the given memb

33、ership functions Take the first item in transaction 4 as an example,0 1 6 9 11,Low,Middle,High,1 0,Membership value,Number of item,Result after step 2,The fuzzy sets transformed from the quantitative data,Step 3,Calculate the scalar cardinality of each fuzzy region,Step 4,Generate large itemsets L1

34、Assume the minimum support value is 1.5,Step 5,Generate candidates and calculate fuzzy cardinality By minimum operators e.g. (B.Low, C. Middle),1.4,Step 6,Generate large itemsets L2 Assume the minimum support value is 1.5 No L3,L2,Step 7,Calculate confidence and generate rules By conditional probabi

35、lity confidence value = min-conf threshold Assume min-conf = 0.75 There are three rules in this example If C = Middle, then T1 = Low (2.0, 0.77) If T1 = Middle, then T3 = Middle (1.6, 0.8) If T3 = Middle, then T2 = High (2.4, 0.86) If T3 = High, then T2 = High (1.8, 0.82),Step 8,Check whether the ru

36、les are interesting All the rules has no ancestor rules Final Results: If C = Middle, then T1 = Low (2.0, 0.77) If T1 = Middle, then T3 = Middle (1.6, 0.8) If T3 = Middle, then T2 = High (2.4, 0.86) If T3 = High, then T2 = High (1.8, 0.82),Another Variant,Use only the region with the maximum fuzzy c

37、ardinality for each item,Result after step3,Less number of large itemsets Not complete Less computation time,L1,L2,Experiments,In C on a Pentium-III Three levels, four branches Numbers of purchased items are first randomly generated Purchased items and quantities are then randomly generated.,Experim

38、ents,For 10000 transactions The relationships between numbers of rules and minimum support values and confidence values,Support - Rules Confidence - Rules ,Experiments,Different average numbers of items in transactions Average number of items - Rules ,Experiments,Average number of items - time ,Expe

39、riments,For different numbers of transactions Numbers of transactions - Rules ,Experiments,Numbers of transactions - Time ,Experiment,A comparison of the proposed approaches Rules are more complete by the first approach,Experiment,A comparison of the proposed approaches More Time is spent by the fir

40、st approach,Experiment,A comparison of fuzzy effects By prediction accuracy,Fuzzy partition is better than crisp partition,Web Mining,Log data,Web Mining,Knowledge and strategy,Browsing patterns,Web mining,web-content mining focuses on information discovery from sources across the World Wide Web e.g

41、. Mining page-keyword relations from web pages web-usage mining emphasizes on the automatic discovery of user access patterns from web servers e.g. Mining page browsing patterns from log files,Goal,Proposing a web-usage mining algorithm Finding linguistic browsing behaviors from data logs on web ser

42、vers e.g. If browsing page A a long time Then next browsing page B a short time Adopting fuzzy concepts in analyzing the browsing time,Related work,Web content mining Web usage mining,Related work,Mining sequential pattern Fuzzy set theory and fuzzy data mining,AprioriAll Algorithm,Proposed by Agraw

43、al and Srikant For finding sequential patterns Five phases Form customer sequences Find large itemsets Map itemsets into integers Find large sequences Find maximally large sequences,AprioriAll Algorithm,Proposed by Agrawal and Srikant For finding sequential patterns e.g. Customer 1 10:00 BCD Custome

44、r 2 11:00 BC Customer 1 15:00 BCDE Customer 2 17:00 EF Customer 1: BCD - BCDE Customer 2: BC - EF = BC - E,Example,Support = 60%,Example,Fuzzy web-mining algorithm,Input Log data Membership functions For converting browsing durations into linguistic terms Threshold Min-sup Output Fuzzy browsing patt

45、erns,Log data,Our algorithm,Step 1 The following file names are selected .asp, .htm, .html, .jva, .cgi and closing connection The following four fields are kept date, time, cilent-ip and file-name,Our algorithm,Step 2 The values of field client-ip are transformed into contiguous integers for convene

46、nce Step 3 The log data sorted first by encoded client ID and then by date and time,Our algorithm,Step 4 The time durations of the web pages browsed by each encoded client ID are calculated e.g. 2001/03/01, 05:39:56 2001/03/01, 05:40:26 30 seconds,Our algorithm,Step 5 The web pages browsed by each c

47、lient are listed to form browsing sequence,Our algorithm,Step 6 The time durations are represented as fuzzy sets Using the given membership functions e.g. the second item (C, 101) in Client 4,0 20 70 80 101 130,Short,Middle,Long,1 0,Browsing duration,Results after step 6,The fuzzy sets transformed f

48、rom the quantitative data,Our algorithm,Step 7: The maximum membership value for each region in each sequence is found e.g. Client 2: D.Middle: max(0.8, 0.0, 0.6)=0.8,Our algorithm,Step 8: The support value of each region is calculated e.g. D.Middle:,D.Middle: 0.6 + 0.8 + 1.0 + 0.0 = 2.4,Our algorit

49、hm,Steps 9-11: Large 1-sequences are generated e.g. Assume Min-sup: 1.8 B.Short, C.Middle, D.Middle Steps 12-15: Large k-sequences are generated Candidate 2-itemsets B.Short, C.Middle C.Middle, B.Short B.Short, D.Middle D.Middle, B.Short :,Support value of composite regions,The support value of each

50、 composite region is calculated For example : client 4 (B.Short, C.Middle) maxmin(1.0, 0.6), min(1.0, 0.4), min(1.0, 0.4) = 0.6,Support = 0.8+0.0+ 0.8+0.6 = 2.2,Our algorithm,Large 2-sequences (B.Short, C.Middle) (D.Middle, B.Short) (D.Middle, C.Middle) In this example, no large 3-sequences exist,Ou

51、r algorithm,Step 16: Maximally large sequences are output For example ABC, AB, BC, AC Output: ABC In this example (B.Short, C.Middle) (D.Middle, B.Short) (D.Middle, C.Middle),Mining Membership Functions,Fuzzy Association Rules,Transaction data,Fuzzy Mining,Good Enough ? GAs Interesting rules Bad kin

52、ds of membership MFs ,Quantitative Data,Fuzzy Association Rules,Related Study,Wang, Hong and Tseng: Knowledge Integration,Expert System,4. Reduce the effort on developing an expert system or decision support system,1. Knowledge is distributed among sources,RB1,RBi,RBn,GRB,User Interface,Integration,

53、3. Knowledge can be reused,2. It Increases reliability of knowledge-based systems,Genetic Knowledge-Integration Framework,Why Using GAs ?,Integration,RB1,RBi,RBn,Integration must satisfy,1.Completeness 2.Correctness 3.Consistency 4.Conciseness,Multi-objective optimization problem,GAs finding optimal

54、 or nearly optimal solutions,Related studies,Wang et al. (2000) Tuning membership functions for intrusion detection systems by GAs Based on similarity of association rules,Review of Related Studies (Cont.),Kaya et al (2003) Derive a predefined number of membership functions by GAs Getting a maximum

55、profit within an interval of user specified minimum support values,History of GAs,GA: Genetic Algorithm History,John Holland,1975,K. A. De Jong,D. E. Goldberg,Idea of GA,Survival of the fittest Iterative Procedure Genetic operators Reproduction Crossover Mutation Near optimal solution,Simple Genetic

56、 Algorithms,An Example,A Function Find the max,Step1,Define a suitable representation Each Chromosome 12 bits e.g. t = 0 000000000000 t = 1 111111111111 t = 0.680 101011100001,Step2,Create an initial population of N N Population size Assume N = 40,Step3,Define a suitable fitness function f to evalua

57、te the individuals Fitness function f(t) e.g. The first six individuals,Step 4,Perform the crossover and the mutation operations to generate the possible offsprings,Crossover,Offsprings: Inheriting some characteristics of their parents e.g.,Parent 1 : 00011 0000001 Parent 2 : 01001 1001101,Child 1 :

58、 000111001101 Child 2 : 010010000001,Mutation,Offsprings possessing different characteristics from their ascendents Preserving a reasonable level of population diversity e.g. Bit change e.g. Inversion,1 1 1 1 0 0 0 0 0 1 0 0,0 1 1 1 0 0 0 0 0 1 0 0,1 1 1 1 0 1 0 0 0 1 0 0,1 1 1 0 1 1 0 0 0 1 0 0,New Offsprings,The new offsprings produced by the operators,Step 5,Replace the individual e.g. The first six individuals,NEW,Step 6,If the termination criteria are not sat