صفحه 1:
irmgn.ir و
Data Mining
Techniques
صفحه 2:
irmgn.ir و
تصميم كيرى
* درخت تصميم يكى از ابزارهاى قوى و متداول براى دسته بندى
بيش بينى مى باشد.
cll ilps neck gate LL درخت تسنمیم کیری یگ ©
* در اين ساختار هر کره داخلی آزمونی را بر روی یک ویژگی
مقتخض تن ند
گره های بر کلاسها يا توزيع كلاسها را ارائه مى نمايند.
* بالاترين كره در
رخت گره ريشه است.
صفحه 3:
irmgn.ir و
خصوصیات درخت تصمیم گیری
* درخت تصمیم پیش بینی خود را در قالب يكسرى قوانين
Gale ge gh Se pa دهد در eee
بينى بيان مى شود و جكونكى أن در خود شبكه بنهان باقى
مق مان
همچنین در درخت تصمیم گیری بر خلاف شبکه های عصبی
لزومی ندارد که داده ها لزوما بصورت عددی باشند.
صفحه 4:
irmgn.ir ۱
درخت تصمیم گیری چگونه کار می کند؟
* در درخت تصمیم گیری نیز یکسری سوال وجود دارد و
یا مشخص شدن پاسخ هر سوال یک سوال دیگر پرسیده
می شود. اگر سوالها درست وخوب پرسیده شوند یکسری
کوتاه از سوالات برای پیش بینی دسته رکورد جدید
کافی می باشد.
مثال
ses Say Cs
ود ee 2
ده میا منیا
وق هیا
lass 6: (ge
0 Balam <=a0)
امه و > 58)
Satay >-90(۵۶ (ge >
Salam >S0)08 (Rge> a8
صفحه 5:
التلنت
irmgn.ir
اثر بخشی یک درخت تصمیم گیری
* درسد ذاده یی که درست: ده بندی.می. شون و همه
ین پیب شنه با دنه واقمی نها یکنان نت
* همچنین کیفیت شاه های ایجادشده تیز مهم است. هرراه
یجانشده از ريه يه يك يرك معادل یک قانون ات که بفشی,
قانوتها بهتر از ساير قانوتها مى باشند. در بعضى اوقات بريدن
برخی شاخه های ضعیف
درخت باعث بهبود قدرت پیش
بینی درخت می شود.
Training Database
مهمترین هدف از دسته بندی (مععععوه۲ ۵ «طممجععتا 6 بدست آوردن
مدلی برای پیش بینی می باشد.بدین متظور از مجموعه ای به تام داده های
آموزشی (معمخعاه« ودعسم) که مجموعه ای از متفیرها و رکوردها است
ran كلدم ae
Fan متال:
۳
صفحه 6:
التلنت
irmgn.ir
انواع متغیر های درخت تصمیم گیری
عددی 38621( ماد سن قد
eg wl Categorical gl, gla pice * جنس
از اين متغير ها براى يبش بينى متفير هدف يا متغير وابسته استفاده م
اكليم
Age) J Jl js 21s cif ole pies 4 Predictor Attributes
متیر های مستقل می گوین. و با که ها نشان مي دهند )011 007 06
sins ge Sy lg ef متغير هاى وابسته مى Class Label
Risk J Joe
E lassipnadon &Regeessinn
* اگر متفیروابسته از نوع عددی باشد سأله به یک سأله
«سعهسود 1 تبدیل خواهد شد.
* واگر رده ای باشد مسأله #مةمتهيعدها #است.
صفحه 7:
irmgn.ir srearene
Jot yo ایجاد درخت تصمیم گیری
Eazy yes
* مرحله هرس درخت (که هدف این مرحله کاهش خطا ها می باشد.
الگوریتمهای متفاوتی بای ایجاد درخت وجود
الگوریتم کلی ابجاد درخت
۹
pif n split
best split to partition D to D1 and D2 عمج
[1-Build tree(n!.DIss)
[5-Build tree(n2.D2.s5)
lécend if
صفحه 8:
irmgn.ir و
متدهای انتخاب نقطه شکست شاخه
SglitSelendon
(gini(T) = 1 - Epj2): Gini Index ۰
(entopy(T) =- Epj x loe2(pi)): Enwopy
cat +
زرد ۰
Min(pi) +
كي ٠
ens
Ginilndex
* در روش Index :818 همه متغير ها را در گره امتحان کرده
و آن متغیری که از همه کوچکتر باشد را انتخاب می کنیم.
* بهترین انتخاب برای تقسیم مجموعه 5 به دو مجموعه 81 و
8 از معیار زیر تبعیت می کنده یعنی ماکزیمم کردن ثابع زر
105(- 61/6 ۴۲)61(+۱۹2۷۱6۳۲)62(
صفحه 9:
التلنت
مثال ۱218 :10 كا
Spore
Family
3
Family
Ginilndex مثال
Age Car Bype Rae
2 3 3
17 سر iat
baad چدول را بر آساین متفیز 488 بها سورت سودي عردب مق
Carpe
irmgn.ir
صفحه 10:
irmgn.ir ۱
* حال از مت ۱۵8 مق برای انتخاب اتشعاب استفاده می
كنيم. هر دو متفیر 98 او 108 48 ل] را بررسی می کنیم.
اما قبل از اختصارات را معرفى مى نماييم:
و ۱ : ۱
سا :با
RoR ghee hid
۳ قلت
Gini(2)=I -Yay?
Age<=l2 +
=
US1)—aiy ~n7 = L-0
US2): 1/97 ~@!5) = 1-9125-41250.48
§/)6/*0.48= 0+ Si6%0.48-0.4
صفحه 11:
التلنت
Age<=20 +
Lio
14/16 416
= 11S): 2/60 |4)6"#0.S= 416405
24 هکل
مسمال- ترويم- |
119-044 د ترد
182): 1- avs"
6و۱ 5 36۹۵+ 3)(6/*0-444= 34640.444=0222
۱۳ 53
irmgn.ir
صفحه 12:
التلنت
۱
1
US) دمو
sie. is
سوه 5-0 4166
tft
51خ
151-۵ 1-16/25-1/25-032
KS2):1- pin? avy’ = 1041-0,
[S21 Js}-6=> 16): [560.32 + |1\j6}0= S16*0.32 ~0-0.266
irmgn.ir
صفحه 13:
التلنت
Age<=a0 +
HOoL
fee
|
US1)1-i6} ~ 216) = 1-166-436-0444
1-0-0621 نوم تيمر جرعي
sl
[52-0 |s}-6= US: ۵۵۸۹
* برای بررسی متفیر های رده ای 3892081 و به منظور
سهولت در انجام کره جدول فروانی های هر کلاس را از روی
همان تجدول اولیة بای متیر های ردة ای:تشکبل ذفتم و
سپس محاسبات را مشابه همان روش قبل انجام می دهیم
Car Type
sports
Fanily 1
Truck, 9 1
irmgn.ir
صفحه 14:
التلنت
Car type={sports}
Car type= amily}
/6"0444 + 3)(6%0444 = 0.444
ASG 1S): 2V6*0 + HIl6)*0 = 416*0.5 ~0-0.333
yay = 79
4
1S2):1-@/3)'-A13) = 1419-19-04
۳
irmgn.ir
وی
carte sports
usa.
1/52: ۱-6
carpe tay
carpe fly
1
صفحه 15:
التلنت
Cae rype=rek
0=0.266- دوه
* پس از بررسی کلیه حالتهاء مینیمم ( 1)5را بدست می آوریم:
irmgn.ir
5] شاوی
]| وت
04 = - ارم - نا
۱ 0/9) = 1-16/25-1725-0.32
(۱/6۵ + ۱۹۹۵۵1
ادك وكاتوا
۲0 6.۵ ۰3310288 0 ۰۵۱ 38,0 .881 ,۵ ۰886, 303,
۱.211 ۲ 282 8
يس معيار 8 28> 88 8 را به عنوان نقطه انشعاب انتخاب می کنیم:
(11,80,۸3) 2 قتعكمور
صفحه 16:
التلنت
irmgn.ir
| سس | ب [a
ee LD)
5 Blass cus چون
7 881ل نا اين مجموعه
باشد: go High همه
* حال جدول 98<88 8 را تشکیل می دهیم تا معیار انشعاب
بعدی با استفاده از همان روش فوق مجدداً برای اين بخش از
داده ها انتخاب شود:
‘Ae Cae Type Risk
32 3 Low
3 Sporis High
Family Low
صفحه 17:
التلنت
Cartype={sports}
= KS): [1 3)*0 + 12/13)*0 = 0
Car type = fuck)
دمر
114-1405
151(:۱- ۵/۱ -(
رد )1-412 :)182
۵ ۱۱/3۳۵۰ کل 3اه ۵1
irmgn.ir
cartype= spots
carte spots
182): 1-1
ist/=1.|s2)
carpe = ok
موی
«- خرم- لا
صفحه 18:
irmgn.ir و
cartype=finity ]
1 1 ]تاه
۱
4 - تردن - رد-۱ :(2ک1
|
تکمیل درخت
* پس از بررسی تمام حالات مینیمم (1)5 بین آنها صفر می باشد.
پس درخت به شکل زیر تکمیل می کردد. این درخت نهایی است
زیرا تمام برگهای آن به 4881لا 8ظ ها لا ختم شده اند.
Age <8
a Re 5056
4
High
صفحه 19:
التلنت
ارزیابی درخت ایجاد شده
* برای محاسبه رخ خطا در درخت ادا بید نرخ خطا در هر
شاخه را بدست آوریم. نرخ خطا در هر برگ عبارتست از نسبت
تعداد رکورد هایی که کلاس یا دسته آنها درست انتخاب یا
نرخ خطاهای
آگرمثلا هدف دسته بندی بر اساس قدآفردباشد: و مجبوعه
آی ۱۱ نفری داشته پاشیم که:هبه بجز یک مخند رای قد
کوتاه هستند.اگر این گره را به دو شاخه تیم کنیمه ممكن
است قاونی ه شکل زیر حاصل شود
* "فراد کمتر از ۲۸ سال كه نام آنها محمد است, بلند قد هستند.
irmgn.ir
صفحه 20:
irmgn.ir و
هرس کردن Pruning
* برای جلوگیری از چنین قانون هایی در بعضی از شاخه ها که
شرایط خاصی در آنها وجود دارد عملیات هرس با برش
pF gt Spo (Bruning)
اين كار با آنكه نرخ خطا را اقزايش مى دهد ولى از إيجاد بعضى
قانون هاى ناكارآمد جلوكيرى مى كند.
* البته نرخ خطای بدست آمده در درخت جدید تبايد تفاوث
چندانی با قبلی داشته باشد.
صفحه 21:
irmgn.ir و
نقاط ضعف درخت تصمیم گیری
irmgn.ir
5/20/2012
زازُ کاٍي
زستِ تٌسي
زرذت تصوين
سويِ ػليسازُ
1
irmgn.ir
5/20/2012
درخت تصميم گيري
سمیه علیزاده هیات علمی دانشکده صنایع
دانشگاه خواجه نصیر طوسی
تعريف
• زرذت تصوين يكي از اتسارّاي قَي ٍ هتساٍل تراي زستِ تٌسي
ٍ پيص تيٌي هي تاضس.
• زرذت تصوين گيري يک ساذتار زرذتي ضثيِ فلَچارت است.
• زر ايي ساذتار ّر گرُ زاذلي آزهًَي را تر رٍي يک ٍيژگي
هطرص هي کٌس.
گرُ ّاي ترگ ،کالسْا يا تَزيغ کالسْا را ارائِ هي ًوايٌس.
• تاالتريي گرُ زر زرذت گرُ ريطِ است.
سمیه علیزاده هیات علمی دانشکده صنایع
دانشگاه خواجه نصیر طوسی
2
irmgn.ir
5/20/2012
ساختار درخت تصميم گيري
سمیه علیزاده هیات علمی دانشکده صنایع
دانشگاه خواجه نصیر طوسی
خصوصيات درخت تصميم گيري
• زرذت تصوين پيص تيٌي ذَز را زر قالة يكسري قَاًيي
تَضيح هي زّس زر حاليكِ زر ضثكِ ّاي ػصثي تٌْا پيص
تيٌي تياى هي ضَز ٍ چگًَگي آى زر ذَز ضثكِ پٌْاى تاقي
هي هاًس.
• ّوچٌيي زر زرذت تصوين گيري تر ذالف ضثكِ ّاي ػصثي
لسٍهي ًسارز کِ زازُ ّا لسٍها تصَرت ػسزي تاضٌس.
سمیه علیزاده هیات علمی دانشکده صنایع
دانشگاه خواجه نصیر طوسی
3
irmgn.ir
5/20/2012
درخت تصميم گيري چگونه كار مي كند؟
• زر زرذت تصوين گيري ًيس يكسري سَال ٍجَز زارز ٍ
تا هطرص ضسى پاسد ّر سَال يک سَال زيگر پرسيسُ
هي ضَز .اگر سَالْا زرست ٍذَب پرسيسُ ضًَس يكسري
کَتاُ از سَاالت تراي پيص تيٌي زستِ رکَرز جسيس
کافي هي تاضس.
سمیه علیزاده هیات علمی دانشکده صنایع
دانشگاه خواجه نصیر طوسی
مثال
Classification rules:
)Class B: (Age <= 35 AND Salary <= 40) OR (Age > 35 AND Salary <= 50
)Class G: (Age <= 35 AND Salary > 40) OR (Age > 35 AND Salary > 50
سمیه علیزاده هیات علمی دانشکده صنایع
دانشگاه خواجه نصیر طوسی
4
Test data: Age = 25 AND Salary = 50
= Class
irmgn.ir
5/20/2012
اثر بخشي يک درخت تصميم گيري
• زرصس زازُ ّايي کِ زرست زستِ تٌسي هي ضًَس ٍ زستِ
پيص تيٌي ضسُ تا زستِ ٍاقؼي آًْا يكساى است.
• ّوچٌيي کيفيت ضاذِ ّاي ايجازضسُ ًيس هْن استّ .رراُ
ايجازضسُ از ريطِ تِ يک ترگ هؼازل يک قاًَى است کِ تؼضي
قاًًَْا تْتر از ساير قاًًَْا هي تاضٌس .زر تؼضي اٍقات تريسى
ترذي ضاذِ ّاي ضؼيف تر زرذت تاػث تْثَز قسرت پيص
تيٌي زرذت هي ضَز.
سمیه علیزاده هیات علمی دانشکده صنایع
دانشگاه خواجه نصیر طوسی
Training Database
• هْوتريي ّسف از زستِ تٌسي ) (Classification & Regressionتسست آٍرزى
هسلي تراي پيص تيٌي هي تاضس .تسيي هٌظَر از هجوَػِ اي تِ ًام زازُ ّاي
آهَزضي ) (Training Databaseکِ هجوَػِ اي از هتغيرّا ٍ رکَرزّا است
استفازُ هي کٌين.
هثال:
سمیه علیزاده هیات علمی دانشکده صنایع
دانشگاه خواجه نصیر طوسی
5
irmgn.ir
5/20/2012
انواع متغير هاي درخت تصميم گيري
• هتغير ّاي ػسزي Numericalهاًٌس سي ،قس
• هتغير ّاي رزُ اي Categoricalهاًٌس ًَع ،جٌس
• از ايي هتغير ّا تراي پيص تيٌي هتغير ّسف يا هتغير ٍاتستِ استفازُ هي
کٌين.
• :Predictor Attributesتِ هتغير ّاي گفتِ ضسُ زر هثال قثل ( Age
)and Car typeهتغير ّاي هستقل هي گَيٌس ٍ .تا گرُ ّا ًطاى هي زٌّس.
• :Class Labelتِ هتغير ّاي ٍاتستِ هي گَيٌس ٍ تا ترگ ًطاى هي زٌّس .زر
هثال قثل .Risk
سمیه علیزاده هیات علمی دانشکده صنایع
دانشگاه خواجه نصیر طوسی
Classification & Regression
• اگر هتغير ٍاتستِ از ًَع ػسزي تاضس هسألِ تِ يک هسألِ
Regressionتثسيل ذَاّس ضس.
• ٍ اگر رزُ اي تاضس هسألِ Classificationاست.
سمیه علیزاده هیات علمی دانشکده صنایع
دانشگاه خواجه نصیر طوسی
6
irmgn.ir
5/20/2012
مراحل ايجاد درخت تصميم گيري
• هرحلِ رضس ٍ ايجاز زرذت
• هرحلِ ّرس زرذت (کِ ّسف ايي هرحلِ کاّص ذطا ّا هي تاضس.
الگَريتوْاي هتفاٍتي تراي ايجاز زرذت ٍجَز زارز
سمیه علیزاده هیات علمی دانشکده صنایع
دانشگاه خواجه نصیر طوسی
الگوريتم کلي ايجاد درخت
سمیه علیزاده هیات علمی دانشکده صنایع
دانشگاه خواجه نصیر طوسی
7
irmgn.ir
5/20/2012
متذهاي انتخاب نقطه شکست شاخه
Split Selection
سمیه علیزاده هیات علمی دانشکده صنایع
دانشگاه خواجه نصیر طوسی
Gini Index
• زر رٍش ّ Gini Indexوِ هتغير ّا را زر گرُ اهتحاى کرزُ
ٍ آى هتغيري کِ از ّوِ کَچكتر تاضس را اًتراب هي کٌين.
• تْتريي اًتراب تراي تقسين هجوَػِ Sتِ زٍ هجوَػِ ٍ S1
S2از هؼيار زير تثؼيت هي کٌس ،يؼٌي هاکسيون کرزى تاتغ زير:
)I(S)-|S1|/|S|*I(S1)+|S2|/|S|*I(S2
سمیه علیزاده هیات علمی دانشکده صنایع
دانشگاه خواجه نصیر طوسی
8
irmgn.ir
5/20/2012
مثال Gini Index
سمیه علیزاده هیات علمی دانشکده صنایع
دانشگاه خواجه نصیر طوسی
مثال Gini Index
اتتسا جسٍل را تر اساس هتغير ageتِ صَرت صؼَزي هرتة هي
کٌين.
سمیه علیزاده هیات علمی دانشکده صنایع
دانشگاه خواجه نصیر طوسی
9
irmgn.ir
5/20/2012
• حال از هتس Gini Indexتراي اًتراب اًطؼاب استفازُ هي
کٌينّ .ر زٍ هتغير Car Type ٍ Ageرا تررسي هي کٌين.
اها قثل از اذتصارات را هؼرفي هي ًوايين:
H: High
L: Low
R: Right Child
L: Left Child
Gini(T)=1-∑pj²
سمیه علیزاده هیات علمی دانشکده صنایع
دانشگاه خواجه نصیر طوسی
• Age<=17
سمیه علیزاده هیات علمی دانشکده صنایع
دانشگاه خواجه نصیر طوسی
10
irmgn.ir
5/20/2012
• Age<=20
سمیه علیزاده هیات علمی دانشکده صنایع
دانشگاه خواجه نصیر طوسی
• Age<=23
سمیه علیزاده هیات علمی دانشکده صنایع
دانشگاه خواجه نصیر طوسی
11
irmgn.ir
5/20/2012
• Age<=32
سمیه علیزاده هیات علمی دانشکده صنایع
دانشگاه خواجه نصیر طوسی
• Age<=43
سمیه علیزاده هیات علمی دانشکده صنایع
دانشگاه خواجه نصیر طوسی
12
irmgn.ir
5/20/2012
• Age<=68
سمیه علیزاده هیات علمی دانشکده صنایع
دانشگاه خواجه نصیر طوسی
• تراي تررسي هتغير ّاي رزُ اي ٍ categoricalتِ هٌظَر
سَْلت زر اًجام کار ،جسٍل فراٍاًي ّاي ّر کالس را از رٍي
ّواى جسٍل اٍليِ تراي هتغير ّاي رزُ اي تطكيل زازُ ٍ
سپس هحاسثات را هطاتِ ّواى رٍش قثل اًجام هي زّين.
سمیه علیزاده هیات علمی دانشکده صنایع
دانشگاه خواجه نصیر طوسی
13
irmgn.ir
5/20/2012
سمیه علیزاده هیات علمی دانشکده صنایع
دانشگاه خواجه نصیر طوسی
سمیه علیزاده هیات علمی دانشکده صنایع
دانشگاه خواجه نصیر طوسی
14
irmgn.ir
5/20/2012
سمیه علیزاده هیات علمی دانشکده صنایع
دانشگاه خواجه نصیر طوسی
• پس از تررسي کليِ حالتْا ،هيٌيون ) I(Sرا تسست هي آٍرين:
Min{0.4,0.33,0.222,0.4166,0.266,0.444,0.303,
0.266,0.444}=0.222
پس هؼيار Age<=23را تِ ػٌَاى ًقطِ اًطؼاب اًتراب هي کٌين:
}Age<=23 = {17,20,23
سمیه علیزاده هیات علمی دانشکده صنایع
دانشگاه خواجه نصیر طوسی
15
irmgn.ir
5/20/2012
چَى زستِ Class
Labelايي هجوَػِ
ّوِ Highهي تاضس:
سمیه علیزاده هیات علمی دانشکده صنایع
دانشگاه خواجه نصیر طوسی
• حال جسٍل Age>23را تطكيل هي زّين تا هؼيار اًطؼاب
تؼسي تا استفازُ از ّواى رٍش فَق هجسزاً تراي ايي ترص از
زازُ ّا اًتراب ضَز:
سمیه علیزاده هیات علمی دانشکده صنایع
دانشگاه خواجه نصیر طوسی
16
irmgn.ir
5/20/2012
سمیه علیزاده هیات علمی دانشکده صنایع
دانشگاه خواجه نصیر طوسی
سمیه علیزاده هیات علمی دانشکده صنایع
دانشگاه خواجه نصیر طوسی
17
irmgn.ir
5/20/2012
سمیه علیزاده هیات علمی دانشکده صنایع
دانشگاه خواجه نصیر طوسی
تکميل درخت
• پس از تررسي توام حاالت هيٌيون ) I(Sتيي آًْا صفر هي تاضس.
پس زرذت تِ ضكل زير تكويل هي گرزز .ايي زرذت ًْايي است
زيرا توام ترگْاي آى تِ Class Labelذتن ضسُ اًس.
23
سمیه علیزاده هیات علمی دانشکده صنایع
دانشگاه خواجه نصیر طوسی
18
irmgn.ir
5/20/2012
ارزيابي درخت ايجاد شذه
• تراي هحاسثِ ًرخ ذطا زر زرذت اتتسا تايس ًرخ ذطا زر ّر
ضاذِ را تسست آٍرينً .رخ ذطا زر ّر ترگ ػثارتست از ًسثت
تؼساز رکَرز ّايي کِ کالس يا زستِ آًْا زرست اًتراب يا
پيص تيٌي ًطسُ است.
• تراي هحاسثِ ذطاي کل زرذت ،هجوَع ٍزًي ًرخ ذطاّاي
ترگ ّا را تسست هي آٍرين.
سمیه علیزاده هیات علمی دانشکده صنایع
دانشگاه خواجه نصیر طوسی
کيفيت درخت
• اگر هثالً ّسف زستِ تٌسي تر اساس قس افراز تاضس ٍ ،هجوَػِ
اي ً 11فري زاضتِ تاضين کِ ّوِ تجس يک هحوس زاراي قس
کَتاُ ّستٌس ،اگر ايي گرُ را تِ زٍ ضاذِ تقسين کٌين ،هوكي
است قاًًَي تِ ضكل زير حاصل ضَز:
• ”افراز کوتر از 28سال کِ ًام آًْا هحوس است ،تلٌس قس ّستٌس.
سمیه علیزاده هیات علمی دانشکده صنایع
دانشگاه خواجه نصیر طوسی
19
irmgn.ir
5/20/2012
هرس کردن Pruning
• تراي جلَگيري از چٌيي قاًَى ّايي زر تؼضي از ضاذِ ّا کِ
ضرايط ذاصي زر آًْا ٍجَز زارز ،ػوليات ّرس تا ترش
( )Pruningصَرت هي گيرز.
• ايي کار تا آًكِ ًرخ ذطا را افسايص هي زّس ٍلي از ايجاز تؼضي
قاًَى ّاي ًاکارآهس جلَگيري هي کٌس.
• الثتِ ًرخ ذطاي تسست آهسُ زر زرذت جسيس ًثايس تفاٍت
چٌساًي تا قثلي زاضتِ تاضس.
سمیه علیزاده هیات علمی دانشکده صنایع
دانشگاه خواجه نصیر طوسی
نقاط قوت درخت تصميم گيري
سمیه علیزاده هیات علمی دانشکده صنایع
دانشگاه خواجه نصیر طوسی
20
irmgn.ir
5/20/2012
نقاط ضعف درخت تصميم گيري
سمیه علیزاده هیات علمی دانشکده صنایع
دانشگاه خواجه نصیر طوسی
21