Coronary Artery Disease
Carotid wall thickness

Progression

NormalvesselMinimal
CAD

Moderate
CAD

SevereCAD

Coronary Arterial Wall

Angina Pectoris Myocardial infraction

Sudden death of coronary artery disease
The death rates that of from diseases in the arecent medical report are much higher than that offrom accidents and disasters

Statistical reports show that 130(cancer),
77(cerebrovascular), and 37(cardiovascular) per 100,000
people in the Korean population have been dying as theresult of the diseases every year
Increased carotid intima-media thickness (IMT) is
associated with atherosclerosis risk factors and adverse
cardiovascular outcomesOur objective The first aim is to implement Korean reference standard
database
Normal and abnormal reference and standard data such as multiparametric features, clinical information
 For different heart diseases, we develop diagnostic indexes andalgorithms
 The second aim is to develop biosignal data mining
methodology for predicting and diagnosing the
cardiovascular disease

A multi-parametric measure of HRV, ST-segments and IMT
measurements andA suitable prediction method to enhance the reliability of medical
treatment
We apply and analyze existing classification and statistical methods

Development of intelligent automatic
diagnosis system prototype (KOSEF project)
Clinical/hospital
information
systemInternet
Internet
Bluetooth TM or
WLAN

Emergency
service

ECG signal
Processing Server
Raw Data
StreamData
Cleaning Process
Synopsis
StreamBiosignal

Internet
Internet

Hospital

Data
Process
Data
Process

Data Mining
ServerGatewayServerServerPhysicianintelligent automatic diagnosis system architecture

- iDB 2008 -A Data Mining Approach andFramework of Intelligent
Diagnosis System for Coronary
Artery Disease Prediction

Keun Ho Ryu1, Heon Gyu Lee1, Wuon-Shick Kim2
1(khryu, hglee@dblab.chungbuk.ac.kr), 2wskim@kriss.re.kr
1Database/Bioinformatics Laboratory,
Chungbuk National University, Korea
2Korea Research Institute of Standards and Science, Korea

Outline IntroductionApplication of data mining
to medical data
Motivation and objective

 Background

ECG Analysis
ST-segments
Heart Rate Variability
Carotid arterial wall thickness

 Automated detection of Ischemic
ECG beats30-Sep-08

 Heart Rate VariabilityECG processing, Linear/ Nonlinear
featuresClassification methods for diagnosing CAD
CASE study2 : AP and ACS diseases
classification

 Dyslipidemia diagnosis methodologyMeasuring Intima-Media thickness
Feature extraction from IMT image
CASE study3: dyslipidemia classification

 Discussion
 On going workCompressed Patricia FP-Tree for Frequent
Itemsets Mining

ST-segments feature extraction  Conclusion
CASE study1: Ischemia beatclassification
6 /57

http://dblab.chungbuk.ac.kr

Introduction ...
: Why data mining?
 Modern medicine generates, almost daily, huge amounts ofheterogeneous dataMedical data may contain signals like ECG, clinical information like
temperature, cholesterol levels, etc., as well as the physician's
interpretation
Those who deal with such data understand that there is a widening
gap between data collection and data comprehension
As more and more medical procedures employ signal and imaging
as preferred diagnostic tools

 There is a need to develop methods for efficientmining in databases of signals

30-Sep-08

7 /57

http://dblab.chungbuk.ac.kr

Introduction ...
: Application of data mining to medical data Cardiovascular disease

Myocardial ischemia : ST-segments from ECG signal

Coronary artery disease: Multi-parametric features of Heart ratevariability from ECG signal
Myocardial ischemia
R-R intervals

Angina Pectoris

Carotid wall thickness (intima-media thickness)Atherosclerosis

30-Sep-08

8 /57

http://dblab.chungbuk.ac.kr

A Data Mining Framework of Intelligent Heart
Disease Diagnosis System
ECG/IMT Dataset

Multi-parametric FeatureHeart Disease Diagnosis

QRS wave,
R-R interval detection
ST-segment

T-wave amplitude

ST-seg.

HRV Analysis

ECG Signals
Lead II Channel
Learning and Prediction
using multi-parametricfeatures
Measuring IMTDiagnosis CAD
Carotid Arterial Wall Thickness

ClinicalInfo.

ECG/IMTECG/IMT Dataset

 Step 1: Data Preparationz Measure ECG Signals
ECG Signals
Lead II Channelz Scan Carotid arterial wall thickness: intima-media thicknessz Collect clinical information

Carotid Arterial Wall Thickness

ClinicalInfo.

ECG/IMTMulti-parametric Feature
QRS wave,
R-R interval detection
ST-segment

T-wave amplitude

ST-seg. HRV Analysis

 Step 2: Diagnosis Feature
extractionz Detect RR intervals from ECG signals
z Extracting ST-segments featuresz HRV analysis

Measuring IMT: Linear/nonlinear feature extractionz Measure intima-media thickness

separately

Heart Disease Diagnosis

In our experiments
 Ischemia beat classification
 Angina Pectoris and Acute Coronary Syndromeclassification
dyslipidemia detection
Î gave about 91%, 89%, 93% goodness of accuracy Step 3: Coronary Artery
Disease Diagnosis
Learning and Prediction
using multi-parametricfeatures

Diagnosis CAD

z build classifiers using multi-parametricfeatures.

z classify the patients with coronary

artery disease.

z evaluate the results of classification

Motivation: Why need multi-parametric features
 Coronary heart disease is in danger of becoming the mostfatal disease among Koreans because of smoking and theadoption of westernized eating habits It is very important social issue to detect early heart
problems and predict accurate heart disease The various diagnosis indexes have different physiologicalmeanings
There is not a master feature that explains the whole characteristics
of diagnosis indexes at one timeResearchers must select to use among various features

Need multi-parametric feature with accuracy

30-Sep-08

It will be helpful to predict the heart disease
13 /57

http://dblab.chungbuk.ac.kr

Objective
 A helpful diagnostic supplementary tool, using various
features, that takes into consideration all possible
diagnostic features

30-Sep-08

Linear and Nonlinear features of HRV, ST-segments, IMT

14 /57

http://dblab.chungbuk.ac.kr

Outline IntroductionApplication of data mining to
medical data
Motivation and objective

 Background

ECG Analysis
ST-segments
Heart Rate Variability
Carotid arterial wall thickness

 Automated detection of Ischemic
ECG beats30-Sep-08

 Heart Rate Variability

ST-segments feature extraction
CASE study1: Ischemia beatclassification

ECG processing, Linear/ Nonlinear
featuresClassification methods for diagnosing CAD
CASE study2 : AP and ACS diseases
classification

 Dyslipidemia diagnosis methodologyMeasuring Intima-Media thickness
Feature extraction from IMT image
CASE study3: dyslipidemia classification

 Discussion
 On going work

Development of Contrast data mining andfrequent pattern mining methods

 Conclusion

15 /57

http://dblab.chungbuk.ac.kr

Background: BioSignals (ECG:Electrocardiogram) The most used signal in clinical practice is theElectrocardiogram (ECG)

ECG is test that measures a heart’s electrical activity

ECG provides clinical information about the heart’s status

9

Richard E. Klabunde
30-Sep-08

16 /57

http://dblab.chungbuk.ac.kr

Background ...
: A basic approach to ECG analysis
 Simply a guide to understanding how clinicians identify
abnormalities in the ECG(4)

1. Identify the QRS complexes
2. Identify the P waves
3. Examine ST-T segments: arethere abnormalities (such as
elevation or depression)?
4. Examine the T wave

(2)

(3)

(1)
(5)
Is the abnormality suggestive ofIschemia or infarction?

5. Examine the QT interval

 ECG analysis is a routine part of any complete medical evaluation, due
to the heart’s essential role in human health and disease

30-Sep-08

17 /57

http://dblab.chungbuk.ac.kr

Background ...
: ST-segments and T amplitude
 Several techniques the evaluate the ST-segment changes and the Twave alterations by different methodologies have been used to ischemic
beat detectionParametric modeling, wavelet theory, set of rules, neural nets, decision
analysis, genetic algorithms

 It is clinically important if elevated or depressed as it can be a sign ofischemia or infarction
ST-segment

T-wave amplitude

30-Sep-08

18 /57

http://dblab.chungbuk.ac.kr

Background ...
: Heart Rate Variability
 HRV (Heart Rate Variability) has been used to assessautonomic control of the heart under physiological andpathological conditions
 Control of Heart Rate is known to be affected by the
sympathetic and parasympathetic system

 HRV is used as a clinical tool predicting heart function inboth health and disease HRV is based on analysis of RR intervals in ECG signals
RRIs (RR intervals) are the series of time intervals between
heartbeats

30-Sep-08

19 /57

http://dblab.chungbuk.ac.kr

Background ...
: Heart Rate Variability
 HRV is one of the most promising indications of autonomic
activity (sympathetic / parasympathetic activity)

Reduced parasympathetic activity has been reported in patients withCAD (Coronary Artery Disease)
This reduction in parasympathetic activity evaluated by HRV analysis

 Two properties of HRV analysis
Linear analysis : time- and frequency-domain

Nonlinear analysis : complexity and irregularity

30-Sep-08

20 /57

http://dblab.chungbuk.ac.kr

Background ...
: Heart Rate Variability
 Linear property : Time- / Frequency- domainLinear time domain have been employed in quantification of theoverall variability of HR
Linear frequency domain variables provide markers of the heart
regulation

 Nonlinear property30-Sep-08

The heart rate has complexity which reflect the healthy condition ina living body
The complexity of the human physiological system is reduced in badhealth, but increased in good healthThis complexity can be analyzed by various nonlinear methods

21 /57

http://dblab.chungbuk.ac.kr

Background ...

: Effect of 3 recumbent positions on

nervous system using HRV

 There is a relationship between recumbent position andHRV
In linear analysis, parasympathetic activity is increased andsympathetic activity is decreased in the right position
 In nonlinear analysis, complexity are increased in right position
 Among 3 recumbent positions (supine, right, left), the right position
can enhance the parasympathetic activity
 Right recumbent position is recommended in patient torecover the depressed parasympathetic activity
 Because of the effect of the recumbent position on HRV, we
considered that it is worthwhile to include Linear/Nonlinear
properties of HRV for three positions
30-Sep-08

22 /57

http://dblab.chungbuk.ac.kr

Background ...
: Carotid arterial wall thickness
 The appearance of atherosclerosis has been highly associated withincidence of coronary heart disease
 the severity of carotid IMT is an independent predictor of coronary
events such as myocardial infarction [American Heart Association]

30-Sep-08

Carotid IMT consists of intima thickness and media thickness

23 /57

http://dblab.chungbuk.ac.kr

Background: Classification for Diagnosing Disease (SVM) SVM (Support Vector Machine)30-Sep-08

A new classification method for both linear and nonlinear data
It uses a nonlinear mapping to transform the original training data
into a higher dimension

24 /57

http://dblab.chungbuk.ac.kr

Background ...
: Classification for Diagnosing Disease (SVM) With the new dimension, it searches for the linear optimal separating
hyperplane (i.e., “decision boundary”)
 SVM finds this hyperplane using support vectors (“essential” training
tuples) and margins (defined by the support vectors)

30-Sep-08

25 /57

http://dblab.chungbuk.ac.kr

Background: Classification for Diagnosing Disease (MDA) Multiple Discriminant Analysis is an analysis of dependence method thatis a special case of canonical correlation
 With more than two groups, there will potentially be more than one
discriminant function that can be used to explain the differences amonggroupsFor example, if we want to discriminate among three groups, two canonicaldiscriminant functions will be derived
The first discriminant function separates group 1 from groups 2 and 3, andthe second discriminant function separates group 2 from group 3.

 We can obtain classification function for prediction through thediscriminant analysis
 Classification function is generated for each group30-Sep-08

If new case we have to classify comes into existence, this subject will
belong to a group that has the highest value of classification function
26 /57

http://dblab.chungbuk.ac.kr

Background ...
: Classification for Diagnosing Disease (CMAR)
 Associative classification (CMAR: Classification based on
multiple association rules)Association rules are generated and analyzed for use in classification
Search for strong associations between frequent patterns(conjunctions of attribute-value pairs) and class labels
Classification: Based on evaluating a set of rules in the form of p1 ^p2 … ^ pl Æ “Aclass = C” (conf, sup) It may overcome some constraints introduced by decisiontree induction, which considers only one attribute at a time
 CMAR classification: Statistical analysis on multiple rules

30-Sep-08

27 /57

http://dblab.chungbuk.ac.kr

Background ...
: Classification for Diagnosing Disease (Bayes.) Let D be a training set of tuples and their associated class labels, andeach tuple is represented by an n-D attribute vector X = (x1, x2, …, xn)
 Suppose there are m classes C1, C2, …, Cm.
 Classification is to derive the maximum posteriori, i.e., the maximal

P(Ci|X) This can be derived from Bayes’ theorem

P(X | C ) P(C )ii
P(C | X) =i
P(X) A simplified assumption: attributes are conditionally independent ->Naïve Bayesiann
P(X | C i) = ∏ P( x | C i) = P( x | C i) × P( x | C i) × ...× P( x | C i)
k
1
2
n
k =1

30-Sep-08

28 /57

http://dblab.chungbuk.ac.kr

Background ...
: Classification for Diagnosing Disease (Bayes.) Bayesian belief network allows a subset of the variables
conditionally independentA graphical model of causal relationships



Represents dependency among the variables

Gives a specification of joint probability distribution

Nodes: random variables

Links: dependency

Network search algorithm30-Sep-08

Tree Augmented Naïve Bayes(TAN)
29 /57

http://dblab.chungbuk.ac.kr

Classifiers Evaluation Methodology
Selecting HRVclassified by
Cardiologists
Pattern-based
Methods
Data Discretizntion& Transformation

30-Sep-08

Bayesian,
Function- &Treebased
Methods

Selecting
ST-segements
From ST-T
database

30 /57

 Flowchart of theoverall ischemic beatand patients with
CAD classification
methodology

http://dblab.chungbuk.ac.kr

Outline IntroductionApplication of data mining to
medical data
Motivation and objective

 Background

ECG Analysis
ST-segments
Heart Rate Variability
Carotid arterial wall thickness

 Automated detection of
Ischemic ECG beats30-Sep-08

 Heart Rate VariabilityECG processing, Linear/ Nonlinear
featuresClassification methods for diagnosing CAD
CASE study2 : AP and ACS diseases
classification

 Dyslipidemia diagnosis methodologyMeasuring Intima-Media thickness
Feature extraction from IMT image
CASE study3: dyslipidemia classification

 Discussion
 On going work

Development of Contrast data mining andfrequent pattern mining methods

ST-segments feature extraction
 Conclusion
CASE study1: Ischemia beatclassification
31 /57

http://dblab.chungbuk.ac.kr

Automated detection of Ischemic beats Flowchart of the overall ischemic beat classification methodology
ECG recordings
ECG feature extraction••••• ST J, J80• ST deviation• ST slope• ST area• T amplitude

QRS detection
Isoelectric line identification
ST detection
T peak detection

Build detection
modelsECG Beat
Classification

Training set
Test set

30-Sep-08

32 /57

http://dblab.chungbuk.ac.kr

ST-segments feature extraction
 Location of the J point was detected

If (heart rate ≤ 120 beats/min) then J80
If (heart rate > 120 beats/min) then J60

 ST-segment deviation: refer to the amplitude deviation of the STsegment from the isoelectric line (the line defining the level of zeroamplitude) ST-segment slope: the slope of the line connecting the J and J80 (orJ60) points
 ST-segment area: the area between the ECG trace, the isoelectric line
and the points J and J80
 T-wave amplitude: the amplitude deviation of the T-wave peak from theisoelectric line

30-Sep-08

33 /57

http://dblab.chungbuk.ac.kr

ST-segments feature extraction ...

30-Sep-08

34 /57

http://dblab.chungbuk.ac.kr

CASE study – I: Ischemia beat classification
 Data generation


Download ST-segments data from PhysioNet database(http://physionet.org)
Total # of data : Ischemia(204), Normal(198)
Selected features for our experimentST-deviation, Slope, Area, T amplitude, Class(Ischemia/Normal)

 Experimental results

30-Sep-08

35 /57

http://dblab.chungbuk.ac.kr

Outline Introduction Heart Rate Variability

Application of data mining to
medical data
Motivation and objective Background

ECG Analysis
ST-segments
Heart Rate Variability
Carotid arterial wall thickness

 Automated detection of Ischemic
ECG beats30-Sep-08

ST-segments feature extraction
CASE study1: Ischemia beatclassification

ECG processing, Linear/ Nonlinear
featuresClassification methods for diagnosing CAD
CASE study2 : AP and ACS diseases
classification

 Dyslipidemia diagnosis methodologyMeasuring Intima-Media thickness
Feature extraction from IMT image
CASE study3: dyslipidemia classification

 Discussion
 On going work

Development of Contrast data mining andfrequent pattern mining methods

 Conclusion
36 /57

http://dblab.chungbuk.ac.kr

HRV analysis: ECG processing Measuring ECG for each 3 position


The ECG signals are recorded during 5min. for each 3 recumbent
position (Supine, Right, Left)
No

Start
Start

30-Sep-08

One
One ofof threethreerecumbent
recumbent
positions
positions

55 min.
min.
rest
rest

55 min.
min.
ECG:
ECG: Lead
Lead IIII

37 /57

S=1
S=1 &
&
R=1
R=1 &
&
L=1
L=1

Yes
FinishFinishhttp://dblab.chungbuk.ac.kr

HRV analysis: ECG processing …
 Time series of RR intervals30-Sep-08

RR intervals are the series of timeintervals between heartbeat
The ECG are retrieved to measure
the RR intervals by using S/W for
the detection of R waves : Extract
the R-peaks from the ECG
recordings
RR intervals time series were resampled at rate of 4Hz to obtain
power spectral density (frequency
domain analysis)

38 /57Rv

RR Interval

T

P
ECG

RRI0

RRI1

R

S

RRI2

RRI3

RRI4

t

RRI0 RRI1 RRI2 RRI3 RRI4

RRI0

RRI1

RRI2

RRI3
RRI4

http://dblab.chungbuk.ac.kr

HRV analysis: Linear Feature Extraction
 Time domain of Linear FeaturesSimple time domain features include :① RRm: the mean RR intervals② SDRR: the standard deviation of all RR intervals③ SDSD: the standard deviation of differences between RR intervals

 Frequency domain of Linear Features

30-Sep-08

After Calculating the heart rate, performed the power spectrum analysis
Define areas of spectral peaks as follows:① Total Power (TP): 0~0.4Hz② Very Low Frequency (VLF) power: 0~0.04Hz③ Low Frequency (LF) power: 0.04~0.15Hz④ High Frequency (HF) power: 0.15~0.4Hz.
⑤ Ratio LF/HF : LF to HF ratio⑥ Normalized LF (nLF):(TP − VLF )
nLF =
× 100
LF
(TP − VLF )⑦ Normalized HF (nHF):
nHF =
× 100
HF
39 /57

http://dblab.chungbuk.ac.kr

HRV analysis: Nonlinear Feature Extraction
 Poincare Plots







The Poincare Plots is constructed by plotting each RR interval
against the previous one
SD1: the standard deviation of the distances of points from y=x axis
SD2: the standard deviation of the distances of points from y= -x +RRavg
SD2/SD1: the ratio SD2/SD1 is the measure of heart activity

 Approximate Entropy

30-Sep-08

The ApEn describes the complexity and irregularity of the signal
The value of ApEn is low in regular time series (bad health) / high incomplex irregular ones (good health)40 /57

http://dblab.chungbuk.ac.kr

HRV analysis: Nonlinear Feature Extraction …
 Hurst Exponent, H
H is the measure of the smoothness of a time series based on
asymptotical behavior of the rescaled range of the process

H = 1 : regular behavior (bad health)

0.5 < H < 1.0 : normal (good health : 0.7)



H = 0.5 : random behavior

30-Sep-08

41 /57

http://dblab.chungbuk.ac.kr

CASE study – II
: AP and ACS classification
 Real ECG datasets : Patients in five university hospitals

Patients with stenosis by using angiography Luminal narrowing >= 50% : CAD Group The others: Normal GroupCAD group was divided into two group by cardiologists, AP (Angina
Pectoris) and ACS (Acute Coronary Syndrome)

90% stenosis

 Collect 193 ECG data from our ECG DB


30-Sep-08

99 patients with CAD group and 94 normal group were studied
42 /57

http://dblab.chungbuk.ac.kr

CASE study – II ...
: Classifiers Evaluation Results
 Analysis : Use of multiparametric features of HRV

Classifiers’ Accuracy
Bayes

85.7143

C4.5

84.0476

MDA

71.1905

CMAR

86.1905

SVM

88.3333
0

20

40

60

80

100

Confusion matrix
30-Sep-08

43 /57

http://dblab.chungbuk.ac.kr

Outline IntroductionApplication of data mining to
medical data
Motivation and objective

 Background Heart Rate VariabilityECG processing, Linear/ Nonlinear features
Classification methods for diagnosing CAD
CASE study2 : AP and ACS diseases
classification

 Dyslipidemia diagnosis method

ECG Analysis
ST-segments
Heart Rate Variability
Carotid arterial wall thicknessMeasuring Intima-Media thickness
Feature extraction from IMT image
CASE study3: dyslipidemia
classification

 Discussion

 Automated detection of Ischemic
 On going work
ECG beats30-Sep-08

Development of Contrast data mining and

ST-segments feature extraction
frequent pattern mining methods
CASE study1: Ischemia beatclassification
 Conclusion
44 /57

http://dblab.chungbuk.ac.kr

Measuring Intima-Media thickness: KRISS IMT can be measured byanalyzing the ultrasound imagesof Common Carotid Arterymeasure the IMT at the far wallof a designated 1cm length of
the right common carotid
calculate the average values
over 200 points

IT
1cm

30-Sep-08

45 /57MT

IMT

IntimaMedia
Adventitia

1cm <http://dblab.chungbuk.ac.kr

Measuring Intima-Media thickness ...
: KRISS CCA (Common Carotid Arterial) scanning with a highresolution ultrasound system is doneExam a cross-section of carotid artery

Detect four points (a, b, c, d)

a : the start point of intima
b : the start point of adventitia
c : maximal point between a and b
d : minimal point between a a and b

Cross-sectional view of carotid artery wall
30-Sep-08

46 /57

http://dblab.chungbuk.ac.kr

Feature extraction from IMT image: KRISS In order to classify patients with dyslipidemia from normalgroup, total 15 features are extracted from ultrasoundimage
1. Fv01 : Distance between a and b
2. Fv02 : Area of Fv01[sum(a:b)]
3. Fv03 : Value of c
4. Fv04 : Distance between a and c
5. Fv05 : Area of Fv04 [sum(a:c)]
6. Fv06 : Value of d
7. Fv07 : Distance between a and d
8. Fv08 : Area of Fv07[sum(a:d)]
9. Fv09 : Gradient of straight line from value point of a to value point of c
10. Fv10 : Gradient of straight line from value point of c to value point of d
11. Fv11 : Gradient of straight line from value point of a to value point of b
12. Fv12 : Angle acd
13. Fv13 : Angle cdb
14. Fv14 : Value of c-value of a
15. Fv15 : Value of c-value of d
30-Sep-08

47 /57

http://dblab.chungbuk.ac.kr

CASE study – III: dyslipidemia classification using IMT features
 Collect 600 real IMT dataset
Classifiers' accuracy

328 patients withdyslipidemia and 272
patients with normal groupwere studied

100
90

92.6667
84.0526
78.166780

70.1667

70
60
50
40
30
20



10

Performance evaluation:

0
KNN

Accuracy and confusion
matrix

30-Sep-08

Neural Net

SVM

C4.5

Result: suitable method forpredicting patients withdyslipidemia : Neural Net

48 /57

http://dblab.chungbuk.ac.kr

Discussion
 In this work, in order to predict and diagnose
cardiovascular disease such as ischemia, coronary arterydisease (AP, ACS)Used ST-segments features of ECG
Suggested a possibility that multi-parametric feature of HRV may be
helpful to make a diagnosis the heart disease
Extract useful features from carotid artery wall image

 Also, we applied data mining techniques (classification
methods and association rules) to enhance the reliability ofthe diagnosis and detect early symptoms of heart problems

30-Sep-08

49 /57

http://dblab.chungbuk.ac.kr

On going work
 Development of Contrast data mining and frequent patternmining methods

30-Sep-08

Contrast data mining : Emerging Pattern Mining-Based
Methodology for Automated Diagnosis of Cardiovascular
DiseasesFrequent pattern mining : Compressed Patricia FP-Treefor Frequent Itemsets Mining

50 /57

http://dblab.chungbuk.ac.kr

Emerging Pattern Mining-Based
Methodology
 Propose a special type of Emerging Patterns (IEPs) andshow that they are high quality patterns for building
accurate classifiers Generalize the interestingness measure for EPs, including
the min. support, min growth rate, the subset relationshipbetween EPs and correlation based on common statisticalmeasure (chi-square value) Develop tree-based pattern growth algorithms for mining
only those interesting EPs

30-Sep-08

51 /57

http://dblab.chungbuk.ac.kr

Emerging Pattern Mining-Based
Methodology ... : T-tree & P-tree structure Emerging Patterns (EPs) are contrast patterns between two classes ofdata whose support changes significantly between the two classes
 In this study, we extend EPs mining algorithm using TFP algorithm
0

a

b

c

d

e

nl
4

4

4

4

0

0

0

0

3

0

0

0

0

3/2

nl

nl

nl

nl

5

A

nl

nl
0

0

a

0

a

b

c

nl

0

a

nl

nl

b

c

d

2

2

2

2

3

2

3

3

2

1

1

1

1

2

2

2

2

in

0

0

0

0

2

in

2

2

B

nl

nl

nl

nl

A

A

A

A

nl

nl

nl

nl

nl

nl

nl

0

a

nl

nl

52 /57b2b2

30-Sep-08

a

nl

nl

0

a

b

nl

nl

nl

c

2

0

2

0

in

nl

A

nl

nl

http://dblab.chungbuk.ac.kr

Compressed Patricia FP-Tree forFrequent Itemsets Mining Compressed Patricia FP-Tree (CPFP-Tree)

New data structureCan find fast frequent itemsets

Sparse frequent itemsets



Dense frequent itemsets

 CPFP-Tree applications
Finding frequent itemsets



Association rules mining & other mining

System with limited memorySparse & dense frequent itemsets

30-Sep-08

53 /57

http://dblab.chungbuk.ac.kr

CPFP-Tree: example

30-Sep-08

54 /57

http://dblab.chungbuk.ac.kr

CPFP-Tree: performance evaluation

30-Sep-08

55 /57

http://dblab.chungbuk.ac.kr

Conclusion
 In this study,

We proposed data mining framework for coronary heart disease perdition
Automated diagnosis methodology using ST-segments, HRV features and
IMT features
Our experiments showed that Function -, Pattern-based classifiers were themost accurate in comparison with all other classifiers for diagnosing heartdiseases On going work, We proposed emerging pattern mining-based Methodology for
Automated Diagnosis of Cardiovascular Diseases
Extend emerging pattern based classifier – tree-based Introduce the interestingness measure, Chi-square Directly generate EPs and remove uninformative patterns
We developed a novel fast algorithm for discovering frequent itemsets
 CPFP-Tree is efficient and scalable Dense and Sparse frequent itemsets mining tasks
 CPFP-Tree is faster than the Apriori and FP Growth algorithm30-Sep-08

56 /57

http://dblab.chungbuk.ac.kr

Thank You

Any Question?

 This work was supported by

The Korea Science and Engineering Foundation (KOSEF) grant funded by the Korea
government(MOST) (R01-2007-000-10926-0)
The Korea Research Foundation Grant funded by the Korean Government(MOEHRD)" (The Regional
Research Universities Program/Chungbuk BIT Research-Oriented University Consortium)
a grant from the Personalized Tumor Engineering Research Center(PTERC) and the Korea Scienceand Engineering Foundation(KOSEF).