تحصيلات تکميلي

نام و نام خانوادگي : مهدي مراديان

دانشکده : فني و مهندسي

استاد راهنما : دکتر احمد براآني

تاريخ دفاع : 25/3/88

رشته و گرايش : کامپيوتر- نرم افزار

استاد مشاور : -

بهبود روش هاي دسته بندي در داده کاوي با استفاده از دانش گذشته

چکيده

الگوريتم KNN يکي از بهترين و پرکاربردترين الگوريتم هاي دسته بندي است که از آن استفاده ي گسترده اي در کاربردهاي مختلف مي شود. يکي از مشکلات اين الگوريتم، تأثير يکسان همه ي خصيصه ها در محاسبه ي فاصله ي رکورد جديد با رکوردهاي موجود در پايگاه داده هاي آموزشي مي باشد، در صورتي که برخي از اين خصيصه ها براي عمل دسته بندي کم اهميت ترند. اين امر باعث گمراهي روند دسته بندي و کاهش دقت الگوريتم دسته بندي مي شود.

در اين تحقيق به استخراج نوع خاصي از قوانين وابستگي مي پردازيم که سمت چپ آن ها فقط يک قلم وجود دارد و سمت راست آن ها برچسب دسته وجود دارد. سپس با بررسي و آناليز اين قوانين وابستگي و ترکيب آن ها با الگوريتم KNN دو الگوريتم دسته بندي جديد پيشنهاد مي کنيم. در الگوريتم اول يعني الگوريتم نزديک ترين k تايي همسايگي مبتني بر وابستگي پويا 1 بر اساس مقادير ويژگي هاي رکورد جديد به صورت پويا به ويژگي هاي مختلف وزن اختصاص مي دهيم، يعني هر بار که يک رکورد جديد وارد مي شود، وزن ويژگي ها براي محاسبه ي فاصله تغيير مي کند. اما در الگوريتم دوم يعني الگوريتم نزديک ترين k تايي همسايگي مبتني بر وابستگي ايستا2 بدون توجه به مقادير ويژگي هاي رکورد جديد و به صورت ايستا به ويژگي هاي مختلف وزن اختصاص مي دهيم. در الگوريتم دوم وزن همه ي ويژگي ها براي همه ي رکوردهاي جديدي که وارد سيستم مي شوند، ثابت است. بعد با توجه به وزن خصيصه هاي مختلف و با استفاده از فرمول محاسبه ي فاصله ي مانهتن بين رکوردها به دسته بندي بر اساس الگوريتم KNN مي پردازيم و با اين عمل دقت دسته بندي الگوريتم KNN را افزايش مي دهيم. مقايسه ي نتايج ارزيابي اين الگوريتم با هفت الگوريتم ديگر دسته بندي بر روي پايگاه داده ي مختلف، بهبود قابل توجه دقت دسته بندي توسط اين الگوريتم را نشان مي دهد.

واژه هاي کليدي: داده کاوي، دسته بندي، الگوريتم نزديک ترين k تايي همسايگي، قوانين وابستگي، وزن دهي به خصيصه ها

1- D_KNNBA (Dynamic-K-Nearest-Neighbor)

2- S_KNNBA (Static-K-Nearest-Neighbor)