大数据数据挖掘培训讲义：偏差检测

1、,Summarization and Deviation Detection - What is new?,2,Outline,Summarization KEFIR Key Findings Reporter WSARE What is Strange About Recent Events,3,What is New?,Old data,new data,4,Summarization,Concisely summarize what is new and different, unexpected with respect to previous values with respect

2、to expected values Focus on what is actionable!,5,Problem: Healthcare Costs,Healthcare costs in US: 1 out of 7 GDP $ and rising potential problems: fraud, misuse, understanding where the problems are is first step to fixing them GTE self insured for medical costs GTE healthcare costs $X00,000,000 Ta

3、sk: Analyze employee health care data and generate a report that describes the major problems,6,GTE Key Findings Reporter: KEFIR,KEFIR Approach: Analyze all possible deviations Select interesting findings Augment key findings with: Explanations of plausible causes Recommendations of appropriate acti

4、ons Convert findings to a user-friendly report with text and graphics,KEFIR Search Space,8,Drill-Down Example,9,What Change Is Important?,10,Deviation Detection,Drill Down through the search space Generate a finding for each measure deviation from previous period deviation from norm deviation projec

5、ted for next period, if no action,Interestingness of Deviations,Impact: how much the deviation affects the bottom line,Savings Percentage: how much of the deviation from the norm can be expected to be saved by the action,Recommendations,Hierarchical recommendation rules define appropriate interventi

6、on strategies for important measures and study areas.,Example:,measure = admission rate per 1000 & study_area = Inpatient admissions & percent_change 0.10,If,Then,Utilization review is needed in the area of admission certification.,Expected Savings: 20%,13,Explanation,A measure is explained by findi

7、ng the path of related measures with the highest impact,The large increase in m1 in group s1 was caused by an increase in m3, which was caused by a rise in m5 , primarily in sector s13.,14,Report Generation,Automatic generation of business-user-oriented reports Natural language generation with templ

8、ate matching Graphics delivered via browser,16,Sample KEFIR pages,Overview,Inpatient admissions,Status,Prototype implemented in GTE in 1995 KEFIR received GTEs highest award for technical achievement in 1995 Key business user left GTE in 1996 and system was no longer used Publication: Selecting and

9、Reporting What is Interesting: The KEFIR Application to Healthcare Data, C. Matheus, G. Piatetsky-Shapiro, and D. McNeill, in Advances in Knowledge Discovery and Data Mining, AAAI/MIT Press, 1996,Whats Strange About Recent Events (WSARE),Weng-Keen Wong (Carnegie Mellon University) Andrew Moore (Carn

10、egie Mellon University) Gregory Cooper (University of Pittsburgh) Michael Wagner (University of Pittsburgh) /wsare,Designed to be easily applicable to any date/time-indexed biosurveillance-relevant data stream,19,Motivation,Suppose we have access to Emergency Department data fr

11、om hospitals around a city (with patient confidentiality preserved),20,Traditional Approaches,We need to build a univariate detector to monitor each interesting combination of attributes:,Diarrhea cases among children,Respiratory syndrome cases among females,Viral syndrome cases involving senior cit

12、izens from eastern part of city,Number of children from downtown hospital,Number of cases involving people working in southern part of the city,Number of cases involving teenage girls living in the western part of the city,Botulinic syndrome cases,And so on,Youll need hundreds of univariate detector

13、s! We would like to identify the groups with the strangest behavior in recent events.,21,WSARE Approach,Rule-Based Anomaly Pattern Detection Association rules used to characterize anomalous patterns. For example, a two-component rule would be: Gender = Male AND 40 Age 50,22,WSARE v2.0 Overview,2. Se

14、arch for rule with best score,3. Determine p-value of best scoring rule through randomization test,All Data,4. If p-value is less than threshold, signal alert,Recent Data,Baseline,Obtain Recent and Baseline datasets,23,Step 1: Obtain Recent and Baseline Data,Recent Data,Baseline,Data from last 24 ho

15、urs,Baseline data is assumed to capture non-outbreak behavior. We use data from 35, 42, 49 and 56 days prior to the current day,24,Example,Sat 12-23-2001 35.8% (48/134) of todays cases have 30 = age 40 17.0% (45/265) of other (baseline) cases have 30 = age 40,25,Step 2. Search for Best Rule,For each

16、 rule, form a 2x2 contingency table eg. Perform Fishers Exact Test to get a p-value (score) for each rule (for this data 0.00005) Find rule R-best with the lowest score. Caution: This score is not the true p-value of RBEST because of multiple tests,26,Step 3: Randomization Test,Take the recent cases

17、 and the baseline cases. Shuffle the date field to produce a randomized dataset called DBRand Find the rule with the best score on DBRand.,27,Step 3: Randomization Test,Repeat the procedure on the previous slide for 1000 iterations. Determine how many scores from the 1000 iterations are better than

18、the original score.,If the original score were here, it would place in the top 1% of the 1000 scores from the randomization test. We would be impressed and an alert should be raised.,Estimated p-value of the rule is: # better scores / # iterations,28,Results on Actual ED Data from 2001,1. Sat 2001-0

19、2-13: SCORE = -0.00000004 PVALUE = 0.00000000 14.80% ( 74/500) of todays cases have Viral Syndrome = True and Encephalitic Prodome = False 7.42% (742/10000) of baseline have Viral Syndrome = True and Encephalitic Syndrome = False 2. Sat 2001-03-13: SCORE = -0.00000464 PVALUE = 0.00000000 12.42% ( 58

20、/467) of todays cases have Respiratory Syndrome = True 6.53% (653/10000) of baseline have Respiratory Syndrome = True 3. Wed 2001-06-30: SCORE = -0.00000013 PVALUE = 0.00000000 1.44% ( 9/625) of todays cases have 100 = Age 110 0.08% ( 8/10000) of baseline have 100 = Age 110 4. Sun 2001-08-08: SCORE

21、= -0.00000007 PVALUE = 0.00000000 83.80% (481/574) of todays cases have Unknown Syndrome = False 74.29% (7430/10001) of baseline have Unknown Syndrome = False 5. Thu 2001-12-02: SCORE = -0.00000087 PVALUE = 0.00000000 14.71% ( 70/476) of todays cases have Viral Syndrome = True and Encephalitic Syndr

22、ome = False 7.89% (789/9999) of baseline have Viral Syndrome = True and Encephalitic Syndrome = False,29,WSARE 3:0 Improving the Baseline,Recall that the baseline was assumed to be captured by data that was from 35, 42, 49, and 56 days prior to the current day.,Baseline,We would like to determine th

23、e baseline automatically!,What if this assumption isnt true? What if data from 7, 14, 21 and 28 days prior is better?,30,Temporal Trends,From: Goldenberg, A., Shmueli, G., Caruana, R. A., and Fienberg, S. E. (2002). Early statistical detection of anthrax outbreaks by tracking over-the-counter medica

24、tion sales. Proceedings of the National Academy of Sciences (pp. 5237-5249),31,WSARE v3.0,Generate the baseline “Taking into account recent flu levels” “Taking into account that today is a public holiday” “Taking into account that this is Spring” “Taking into account recent heatwave” “Taking into ac

25、count that theres a known natural Food-borne outbreak in progress”,Bonus: More efficient use of historical data,32,Idea: Bayesian Networks,“On Cold Tuesday Mornings the folks coming in from the North part of the city are more likely to have respiratory problems”,“Patients from West Park Hospital are

26、 less likely to be young”,“On the day after a major holiday, expect a boost in the morning followed by a lull in the afternoon”,Bayesian Network: A graphical model representing the joint probability distribution of a set of random variables,“The Viral prodrome is more likely to co-occur with a Rash

27、prodrome than Botulinic”,33,Obtaining Baseline Data,Baseline,All Historical Data,Todays Environment,Learn Bayesian Network,2. Generate baseline given todays environment,What should be happening today given todays environment,34,Simulation,DATE,DAY OF WEEK,SEASON,FLU LEVEL,WEATHER,REGION,AGE,GENDER,Region Grassiness,Region Anthrax Concentration,Region Food Condition,Immune System,Outside Activity,Has Anthrax,Has Flu,Has Allergy,Has Heart Attack,Has Sunburn,Has Cold,Heart Health,Has Food Po