HLTHINFO730HealthcareDecisionSupportSystemsLecture

1、HLTHINFO 730 lecture 6 Slide #1HLTHINFO 730Healthcare Decision Support Systems Lecture 6: Decision TreesLecturer: Prof Jim WarrenHLTHINFO 730 lecture 6 Slide #2Decision Trees Essentially flowcharts A natural order of micro decisions (Boolean yes/no decisions) to reach a conclusion In simplest form a

2、ll you need is A start (marked with an oval) A cascade of Boolean decisions (each with exactly outbound branches) A set of decision nodes (marked with ovals) and representing all the leaves of the decision tree (no outbound branches)HLTHINFO 730 lecture 6 Slide #3ExampleConsider this fragment of the

3、 Prostate Cancer Workup (Evaluation) decision tree from The page also shows supporting text: “Additional testing is recommended for men expected to live 5 or more years or who have symptoms from the cancer. For example, if the tumor is T1 or T2, a bone scan is recommended if the PSA level is greater

4、 than 20 or if the Gleason score is greater than 8. A bone scan is also recommended if the man has any symptoms, or the cancer is growing outside the prostate (T3 or T4). A CT or MRI of the pelvis is recommended when the tumor is T1 or T2 and there is a 7% or greater chance of lymph node spread base

5、d on the Partin tables, or the tumor is growing outside the prostate (T3 or T4).”HLTHINFO 730 lecture 6 Slide #4KE problems for flowchart The natural language may pack a lot in E.g., “any one of the following” Even harder if they say “two or more of the following” which implies they mean to compute

6、some score and then ask if its =2 Incompleteness There are logically possible (and, worse, physically possible) cases that arent handled The for example in the text is a worry Inconsistency Are we trying to reach one decision (which test) or a set of decisions 1) whether to do a bone scan 2) whether

7、 to do a CT or MRIHLTHINFO 730 lecture 6 Slide #5Lets try it anyway Whats said for staging workup looks like thisT1 or T2T3 or T4PSA20SymptomsT3 or T4LNSS3S2BSBSBSS2S3NYLegendS2 = step 2: CT or MRI of pelvisBS = Bone scanS3 = step 3: All others: no additional testingLNS = 7% or greater chance of lym

8、ph node spread based on the Partin tablesPlease dont decide your fathers Prostate follow-up from this!Its unverified, and I dont think a tumour can be T1 or T2 and ALSO T3 or T4 (but thats what it says!)HLTHINFO 730 lecture 6 Slide #6Decision Tables As you can see from the Prostate example, a flowch

9、art can get huge We can pack more into a smaller space if we relinquish some control on indicating the order of microdecisions A decision table has One row per rule One column per decision variable An additional column for the decision to take when that rule evaluates to trueHLTHINFO 730 lecture 6 S

10、lide #7Decision Table exampleFrom van Bemmel & Musen, Ch 15d= doesnt matter (True or False)HLTHINFO 730 lecture 6 Slide #8Flowcharts v. Tables Decision table is not as natural as a flowchart But weve seen, a real (complete and consistent) flowchart ends up very large (or representing a very smal

11、l decision) Decision table gets us close to production rule representation Good as design specification to take to an expert system shell Completeness is more evident with a flowchart Decision table could allow for multiple rules to simultaneously evaluate to true Messy on a flowchart (need multiple

12、 charts, or terminals that include every possible combination of decision outcomes) Applying either in practice requires KE in a broad sense E.g., may need to reformulate the goals of the guidelineHLTHINFO 730 lecture 6 Slide #9On to production rule systems In a production rule system we have decisi

13、on-table-like rule, but also the decision outcomes can feed back to the decision variables Evaluating some special decision rule (or rules) is then the goal for the decision process The other rules are intermediary, and might be part of the explanation of how externally-derived decision variables we

14、re used to reach a goal decision The inference engine of the expert system shell chooses how to reach the goal i.e., with backward chaining, or forward chaining Possibly with some direction from a User Interface (UI) manager component (e.g., we might group sets of variables for input into forms as a

15、 web page)HLTHINFO 730 lecture 6 Slide #10Boolean Algebra To formulate flow chart decisions and (especially) decision table rows, can help to have mastered Boolean Algebra Basic operators NOT if A was true, NOT A is false AND A AND B is only true if both A and B are true OR A OR B is true if either

16、A, or B, or both are true (aka inclusive or) This is not the place for a course on Boolean algebra, but a few ideas will helpHLTHINFO 730 lecture 6 Slide #11Notation Alas there are a lot of ways the operators are written NOT A might appear as A, A, A or A A AND B might appear as A.B, AB, AB or simpl

17、y AB A OR B might appear as A+B or AvB We can use parentheses like in normal algebra C(A+B) means the expression is True if and only if C is true AND either B is true OR C is true (or both) Its equivalent to CA + CB (C-AND-A or C-AND-B, evaluate AND before OR) So AND is a bit like multiplication, wh

18、ereas OR is a bit like addition 1 + 1 1 1 + 0 1 (inclusive OR) 1 x 1 1 1 x 0 1 (logical AND)HLTHINFO 730 lecture 6 Slide #12Think! If you just keep your head and focus on the meaning in the clinical domain, you can usually find the Boolean expression you need Be sure to be precise “NOT (x43)” is “x

19、is NOT GREATER than 43” is “x=43” (get your equals in the right place!)(with this advice, I wont teach you De Morgans Law, truth tables, or Karnaugh maps, but feel free to look them up they all Google well)HLTHINFO 730 lecture 6 Slide #13Venn diagrams Visual representations of membership in sets Can

20、 be very useful to decide what Boolean expression you need Say A is the set of everything with two legs and B the set of everythingthat flies AB would be true for a parrot A would be true for a human,B would be false B would be true for a mosquito,A would be falseHumanParrotMossieA: 2 legsB: can fly

21、HLTHINFO 730 lecture 6 Slide #14Decision Tree Induction An alternative to knowledge engineering a decision tree is to turn the task over to a machine learning algorithm The decision tree can be induced (or inducted) from a sufficiently large set of example The ID3 algorithm is the classic for induci

22、ng a decision tree using Information Theory If I have 50 examples where the patients survived and 50 where they didnt I have total (1.0) entropy and zero information Given a set of potential decision attributes I can try to create more order (less entropy, more information) in the dataHLTHINFO 730 l

23、ecture 6 Slide #15Example: Induced Decision TreeFrom Chen et al, Complete Blood Count as a Surrogate CD4 Marker for HIV Monitoring in Resource-limited Settings, 10th Conf on Retroviruses and Opportunistic Infection, 2003.Of course they go and use ovals for listing the decision variables, put the tes

24、t criteria on the arcs and put leaf decisions in rectangles notations vary; get used to it!HLTHINFO 730 lecture 6 Slide #16Using Entropy measures in ID3 For a decision node S with pp positive example (e.g., surviving patients) and pn negataive example Entropy(S) = - pplog2 pp pnlog2 pn So with 15 su

25、rvivors out of 25 patients Entropy(S) = - (15/25) log2 (15/25) - (10/25) log2 (10/25) = 0.970 I want to select a Boolean attribute A that splits S such that the two subsets are as ordered as possible, usually writtenHLTHINFO 730 lecture 6 Slide #17ID3 continued So if I have 20 available Boolean deci

26、sion variables I try splitting my cases, S, according to each, until I find the variable that gives the most Gain I repeat this on each sub-tree until either every node if perfect (all survivors, or all deaths) or I run out of attributes If my variables arent Boolean, then I have more work to do Act

27、ually, the Gain equation works fine if the attribute is multi-valued (Day of Week would be OK, I just have a 7-way split in my tree) For continuous values I have to discretize make one or more split points e.g., SBP140? now Ive made continuous-valued blood pressure into a Boolean Can be done based o

28、n knowledge (e.g., clinical significance), or handed to an algorithm to search for the max GainSee HLTHINFO 730 lecture 6 Slide #18Tools You dont find pure ID3 too much Other algorithms in a similar spirit to search for are C4.5 and Adaboost Tools Matlab implements decision tree induction Weka toolkit (from Waikato Uni) has a variety of Java tools