بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
رگرسیون درختی و طبقهبندی
چکیده – داده کاوی یک علم میان رشتهای با هدف استخراج دانش پنهان از میان بانک اطلاعاتی انبوه میباشد. رگرسیون درختی و طبقهبندی از روشهای مهم دادهکاوی است و مدلی ناپارمتریک و بدون پیش فرض خاص محسوب میشود. در این روش شاخههای دوتایی بر اساس یک متغیر مستقل ایجاد میشوند. معیار ارزیابی شاخهها، گوناگونی نام دارد. برای جداسازی گره به دو زیر گره میتوان از شاخص جینی یا شاخص دوتایی استفاده نمود. مهمترین و اصلیترین معیار ارزیابی درخت ایجاد شده، معیار نرخ خطا در درخت است. به منظور محاسبهی نرخ خطای کل درخت، مجموع وزنی نرخ خطاهای برگها بدست آورده میشود. به منظور جلوگیری از تولید قانونهای بیکیفیت در برخی از شاخهها، هرس صورت می-گیرد. هرچند این عمل باعث افزایش نرخخطا میشود، اما مانع از ایجاد برخی قانونهای ناکارا میشود. توجه به این نکته نیز ضروری است که هرس به نحوی صورت گیرد تا خطا از مقدار معینی بیشتر نشود. در نهایت باید توجه داشت که درختی بهینه است که کمترین هزینهی دستهبندی اشتباه را برای دادههای آزمایشی داشته باشد.
کلید واژه- دادهکاوی، رگرسیون درختی و طبقهبندی، نرخ خطا، شاخص جینی، هرس.
-1 مقدمه
دادهکاوی یک علم میان رشتهای است که روشهای مختلف از جمله آمار، تشخیص الگو، یادگیری ماشین و پایگاه داده را بکار میگیرد تا دانش نهفته در انبوه دادههای بانک اطلاعاتی را استخراج کند. در دسترس بودن حجم وسیعی از دادهها و نیاز شدید به اینکه از این دادهها اطلاعات و دانش سودمندی استخراج کنیم، باعث شد دادهکاوی کانون توجهات در صنعت اطلاعات قرار بگیرد. اطلاعات و دانش بدست آمده در کاربردهای وسیعی از مدیریت کسب و کار، کنترل تولید و تحلیل بازار تا طراحی مهندسی و تحقیقات علمی استفاده میشود .[1]
مدلهای درختی که در ردهبندی و رگرسیون درختی استفاده میشوند توسط مورگان و سونی کوئیست در سال 1963 میلادی برای بررسی اثرات متقابل متغیرها در دادههای علوم اجتماعی پیشنهاد شدهاند و جنبههای نظری و کاربردی آن توسط بریمن و همکارانش در سال 1984 میلادی در رسالهای که در این مورد منتشر گردید، بسط و توسعه داده شد .[2]
مدل کارت که یک مدل ناپارامتری و بدون هرگونه پیش فرض در خصوص رابطه بین متغیرهای مستقل و متغیر هدف است و از روشهای مهم دادهکاوی میباشد، به طور گسترده در تجارت، صنعت، مهندسی و سایر علوم استفاده شده است. مدل کارت، ابزاری قدرتمند در تعیین مهمترین متغیرهای مستقل و حل مسائل دستهبندی و پیشبینی است .[3]
به طور کلّی روشهای مبتنی بر مدلهای خطی، فضای متغیرهای کمکی را به ناحیههای مجزا تقسیم میکند و دادهها را به گروههای متناظر تخصیص میدهد. این روشها دادهها را به طور بازگشتی برای تعیین یا معرفی اثرات متقابل متغیرها و معرفی زیر گروههایی از افراد با مشخصات دموگرافی و علائم مشخص جهت تشخیصهای بعدی تقسیم میکند. با توجه به نوع مسئله، هدف اساسی در یک مطالعهی مدلهای ردهبندی و رگرسیون درختی میتواند ایجاد یک ردهبندی کنندهی دقیق و یا کشف یک ساختار پیشبینی کننده برای مسئله مورد نظر باشد. اگر هدف تعیین یک ساختار پیشبینی کننده باشد، آنگاه درک صحیح متغیرها و اثرات متقابل آنها ضروری است. معمولاً
1
در مسائل مختلف این دو هدف به موازات هم بررسی میشوند .[2]
-2 درخت تصمیم
طبقهبندی و رگرسیون دو مسأله مهم در علم آمار میباشند. الگوریتم طبقهبندی و درخت رگرسیون در برگیرنده سه وظیفه مهم است. اولین وظیفه این است که چگونه در هر مرحله دادهها را بخشبندی نماید. دومین وظیفه آن است که چه زمانی بخش-بندی را متوقف نماید. آخرین وظیفه، چگونگی پیشبینی مقدار y برای هر x در یک بخشبندی (قسمت)، است .[4] همچنین این روش به سه دلیل عمده، نوع جذاب و مخصوص مدلها می-باشد. اول آنکه نشاندهنده نتایج مدل به صورت آسان برای درک و تلفیق (شبیه سازی) توسط انسان میباشد. دومین دلیل این است که درخت تصمیم مدلی ناپارامتریک میباشد، مداخله توسط کاربر نیاز ندارد، و بسیار مناسب برای جستجوی دانش اکتشافی میباشد. سوم این که الگوریتم قابل درجهبندی است، به مفهوم دیگر؛ کارایی درجهبندی مطلوب ارتباط با افزایش اندازه نمونه آموزشی دارد، این حالت برای درخت تصمیم مدلهای ساخته شده وجود دارد و نیز صحت درخت تصمیم، همسنگ یا برتر از دیگر مدلها میباشد .[5]
-3 درخت طبقهبندی
درخت طبقهبندی زمانی برای مشاهده نمونه آموزشی به کار برده میشود که بدانند طبقه در حال پیشرفت (حالت پیشرفته) است. طبقات در نمونه آموزشی شاید توسط کاربر فراهم شده باشد یا در مطابقت با برخی قوانین برونزا محاسبه گردد. در شکل 1، tp به عنوان یک گره والدین (مادر) و tr و tl به ترتیب گرههای فرزند راست و چپ گره والدین میباشد. ملاحظه می-شود که نمونه آموزشی با ماتریس متغیر X با M تعداد متغیرهای xj و N مشاهدات میباشد. در اینجا بردار طبقه Y شامل N مشاهدات با مجموع مقدار K طبقه میباشد. درخت طبقهبندی در تطابق با قانون جداسازی ساخته میشود. قانونی که ایفاگر جداسازی نمونه آموزشی به بخشهای کوچکتر است.
شکل :(1) الگوریتم جداسازی CART
که در اینجا؛ tp، tr و tl گرههای والدین، راست و چپ میباشند؛ xj متغیر j؛ بهترین مقدار جدا شده متغیر .xj بیشترین (حداکثر) همجنسی گرههای فرزند با نام تابع ناپاکی i(t) تعریف شده است. از این جهت ناپاکی گره والدین tp برای هر جداسازی ممکن ثابت است. حداکثر یکنواختی گرههای فرزند چپ و راست برابر بیشینه تغییر تابع ناپاکی خواهد بود:
(1 ) که در اینجا tc گرههای فرزند چپ و راست گره والدین tp هستند. فرض بر آن است که Pl و Pr احتمال گرههای چپ و
راست است. بنابراین بدست میآید:
(2) در نتیجه، در هر گره CART، مشکل بیشینه ذیل حل می-
گردد:
(3)
رابطه (3 ) این مفهوم را میرساند که CART به طور کامل تمام مقادیر ممکن کل متغیرها در ماتریس X برای بهترین جداسازی پرسش که بیشینه تغییر سنجش ناپاکی خواهد بود را مورد تجسس قرار میدهد.
سئوال مهم بعدی در مورد چگونگی تعریف تابع ناپاکی i(t) خواهد بود. در این تئوری توابع ناپاکی متعدد بودهاند. دو گونه بسیار مهم و کاربردی عبارتند از؛ قاعده جداسازی جینی و قاعده جداسازی توئینگ (دوتایی).
-1-3 قاعده جداسازی جینی
قاعده جداسازی جینی (یا شاخص جینی) قانونی میباشد که به نسبت وسیعی مورد استفاده قرار میگیرد. این کاربرد تابع ناپاکی i(t) طبق رابطه 4 میباشد:
(4)
2
در اینجا k و l، 1و.... وK شاخص طبقه، p(k|t) احتمال شرطی طبقه k که از گره t بدست میآید.
بکار گرفتن تابع ناپاکی جینی بنابر بیشینه، فرمول (4)، این
امکان را فراهم میآورد تا تغییر سنجش ناپاکی بدست
آید:
بنابراین، الگوریتم جینی به صورت فرمول (5) محاسبه می-گردد:
(5)
الگوریتم جینی در نمونه آموزشی برای بزرگترین طبقه و مجزا نمودن از سایر دادهها (باقیماندهها) جستجو مینماید. جینی برای دادههای با اغتشاش مناسب است.
-2-3 قاعده جداسازی دوتایی
این قاعده؛ غیر مشابه با قاعده جینی بوده و برای دو طبقه که با یکدیگر بیش از %50 دادهها را تشکیل میدهند، مورد تفحص قرار میدهد. قاعده جداسازی دوگانه، تغییر سنجش ناپاکی ذیل را بیشینه میسازد:
(6) که دلالت بر بیشینه مقدار فرمول (7) دارد:
(7)
همچنین قاعده جداسازی دوگانه جهت ایجاد نمودن درختهای متوازن بیشتر، اجازه خواهد داد. عملکرد این الگوریتم نسبت به قاعده جینی کُندتر میباشد. برای مثال، اگر تعداد کل طبقات برابر K باشد، بنابراین 2k-1 جداکننده خواهد داشت. در
تحقیق کنونی از قاعده جداسازی جینی استفاده شده است.
-4 رگرسیون درختی
رگرسیون درختی قابلیت طبقهبندی را ندارد. در عوض این بردار پاسخ Y میباشد که نشان دهنده مقادیر پاسخ برای هر مشاهده در ماتریس متغیر X است. از آنجاییکه درخت رگرسیون پیش اختصاص طبقهبندی انجام نمیدهد، قواعد جداسازی طبقهبندی مشابه جینی یا دوتایی کاربردی نخواهند
بود. جداسازی در رگرسیون درختی مطابق با الگوریتم حداقل مربع باقیمانده با دلالت بر آنکه مجموع واریانسهای مورد انتظار برای دو نتیجهگیری گرهها باید حداقل شده باشد، ساخته می-شود.
(8)
که در اینجا Var(Yl) و Var(Yr)، بردارهای پاسخ برای متناظر بودن گرههای فرزند چپ و راست میباشد.
بهینه پرسشهای جداسازی که هر کدام رضایتمندی شرایط فرمول (8) میباشد.
الگوریتم حداقل مربع باقیمانده برابر با قاعده جداسازی جینی است. تابع ناپاکی جینی (4) در توصیف کامل نکته واریانسها ساده است. اگر به مقادیر طبقه K مقدار 1 و به مقادیر سایر طبقات عدد صفر را اختصاص دهند، بدینگونه واریانس نمونه این مقادیر برابر خواهد بود. در مجموع توسط شماره ( تعداد ) طبقات K، میتوان معیار سنجش ناپاکی i(t) ذیل را بدست آورد:
(9) در بالا این نکته به نام درخت حداکثر ساخته شده بود و به
این معنا میباشد که جداسازی برای مشاهدات گذشته در نمونه آموزشی ساخته شده است. درخت حداکثر شاید حاصل بسیار بزرگی باشد، بویژه در نمونه رگرسیون درختی، زمانیکه احتمال هر مقدار پاسخ نتیجهای در یک گره مجزا باشد .[6]
-1-4 عمل شاخه بندی در رگرسیون درختی (تقسیم)
عمل شاخهبندی پایه ساخت درخت است. یک گره از درخت و یک خصوصیت Xj را در نظر میگیرند. فرض کنید بازه تعریف این خصوصیت به تعداد Lj زیر مجموعه تقسیم شود (در زیر روشهای انتخاب چنین زیر مجموعههایی خواهد آمد). در مورد خصوصیتهای کمی، این زیر مجموعهها گروهی از زیر بازههای مجزا هستند، در مورد خصوصیتهای کیفی، زیر مجموعهای از مقادیر و در مورد دادههای خصوصیات ترتیبی زیر مجموعههایی شامل مقادیر همسایه میباشند.
فرض بر آن است به هر یک از زیر مجموعهها یک شاخه نسبت داده شود که از گره فعلی (مادر) به سمت یک گره جدید که (فرزند) نامیده میشود امتداد یابد. بنابراین، گره به تعداد Lj گره جدید "منشعب" شده (تقسیم شده) است (شکل .(2
3
شکل :(2) تقسیم در رگرسیون درختی
توجه شود برای درختهای باینری Lj همیشه برابر با 2 است. اگر Lj برای یک درخت همیشه برابر با 3 باشد آن درخت را "سهگانه" مینامند. اگر Lj همیشه برابر با 4 باشد یک درخت "چهارگانه" خواهد بود.
برای خصوصیتهای کیفی یا ترتیبی مواردی میتواند وجود داشته باشد (هنگامیکه اندازه نمونه مشاهدات کوچک است) که مجموعه مقادیر مشاهدات خصوصیت انجام شده برای یک گره تنها قسمتی از کل بازه تعریف مقادیر خصوصیت را در بَر بگیرد.
در چنین مواردی لازم است که بقیه مقادیر را به یک شاخه جدید نسبت دهند، تا در پیشبینی نمونه کنترل که دارای چنین مقداری باشد بتوان تعیین نمود که این مقدار به کدام شاخه تعلق دارد. برای مثال، ممکن است مقادیر معلوم را با توجه به بیشترین تعداد مشاهدات به شاخهها نسبت داد.
-2-4 عمل تعریف درجه توافق برای شاخه بندی گره (قانون توقف)
یک گره آزاد (گرهای که شاخهای از آن منشعب نشده) را در درخت در نظر بگیرید، که مشخص نیست آیا این گره یک برگ است یا اینکه باید شاخهبندی شود. زیر مجموعه مشاهدات مربوط به این گره را در نظر میگیرند. گرهها را به دو دسته تقسیم میکنند؛ اول آنکه این مقادیر همگن باشند، یعنی اساساً متعلق به یک کلاس باشند (مسئله تشخیص الگو .(RP یا اینکه واریانس Y آنها به اندازه کافی کوچک باشد (مسئله آنالیز رگرسیون .(RA موردی که در آن مقدار خصوصیت برای تمام مشاهدات یکسان باشد نیز به این حالت مربوط میشود. دوم آنکه تعداد مشاهدات کافی نباشد. گرهای که دارای شرایط شاخهبندی نباشد یک برگ نامیده میشود. برای تعریف درجه توافق میتوان پارامترهای زیر را تعریف نمود:
خطای مجاز برای گره (مسئله (PR، واریانس مجاز (مسئله (RA و آستانه برای مشاهدات کیفی .[7]
4
