بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
بهبود دقت الگوريتم KNN در داده کاوي با استفاده از قوانين وابستگي
چکيده : الگوريتم KNN يکي از بهترين و پرکاربردترين الگوريتم هاي دسـته بنـدي اسـت کـه از آن اسـتفاده ي گـسترده اي در کاربردهـاي مختلف مي شود. يکي از مشکلات اين الگوريتم ، تـأثير يکـسان همـه ي خصيصه ها در محاسبه ي فاصله ي رکورد جديـد بـا همـسايه هـاي آن رکورد مي باشد، در صورتيکه برخي از اين خصيصه ها براي عمل دسـته بندي کم اهميت ترند. اين امر باعث گمراهي روند دسته بندي و کاهش دقت الگوريتم دسته بند مي شود. در اين تحقيق با استفاده از اقـلام پـر رخـداد يکتـايي در قـوانين وابـستگي بـه خصيـصه هـاي مختلـف وزن اختصاص داده و با اين عمل دقت الگوريتم KNN را افزايش مي دهـيم .
مقايسه ي نتايج ارزيابي اين الگوريتم با ٧ الگوريتم ديگر دسته بندي بر روي پايگاه داده هاي مختلف UCI ، بهبود قابل توجه دقت دسته بندي توسط اين الگوريتم را نشان مي دهد.
١- مقدمه
الگوريتم دسته بندي KNN [١] براي هر تاپل جديد در بين مجموعه تاپل هاي يادگيري به دنبال تاپل هاي مشابه مي گردد. اگر تاپل ها داراي n خصيصه باشند، آنگاه آنها را به صورت يک بردار در يک فضاي n بعدي در نظر مي گيرد و در اين فضا k همسايه ي تاپل جديد را جستجو مي کند و بر اساس برچسب کلاس اين همسايه ها برچسب کلاس تاپل جديد را پيش بيني مي کند. در اين الگوريتم با استفاده از فرمول زيـر فاصـله ي اقليدسـي [٢] بـين تاپل جديـد و همـه ي تاپـل هـاي موجـود در مجموعـه ي تاپـل هـاي يادگيري محاسبه مي شود.
سپس k تا از تاپل هاي يادگيري که کمترين فاصـله را بـا تاپـل جديـد دارند، به عنوان همسايه هاي آن تاپل انتخاب مـي کنـيم . در بـين ايـن همسايه ها برچسب کلاسي که در اکثريت باشـد را بـه عنـوان برچـسب دسته ي اين رکورد جديد پيش بيني مي کنيم .
يکي از مشکلات اين الگوريتم تأثير يکسان همه ي ويژگي ها در محاسبه ي فاصله ي بين دو رکورد است ، در صورتيکه برخي از خصيصه ها براي دسته بندي رکوردها تأثير بيشتري دارند. به منظور رفع اين مشکل به هر يک از خصيصه ها يک وزن اختصاص داده و براي محاسبه ي فاصله ي بين دو تاپل به جاي استفاده از فاصله ي اقليدسي از فاصله ي مانهتن استفاده مي کنند.در اين تحقيق هدف ، ارائه ي يک روش وزن دهي به خصيصه ها به منظور افزايش دقت دسته بندي الگوريتم KNN است .به اين منظور از اقلام پر رخداد يکتايي در قوانين وابستگي استفاده کرده و الگوريتم جديد KNNBA را ارائه مي کنيم .
ادامه ي اين مقاله از اين قسمت ها تشکيل شده است :در قسمت ٢ به برخي از بهبودهاي الگوريتم KNN مي پردازيم . در قسمت ٣ به بيان الگوريتم پيشنهادي مي پردازيم .در قسمت ٤ به ارزيابي الگوريتم پيشنهادي و مقايسه ي آن با الگوريتم هاي دسته بندي موجود پرداخته شده است . نهايتاً در قسمت ٥ نتيجه گيري شده است .
٢- کارهاي مرتبط
در الگوريتم KNN براي دسته بندي از همه ي ويژگي هاي رکورد به يک اندازه استفاده مي شود [٣]. در صورتيکه همه ي ويژگي ها ي رکوردها ممکن است در دسته بندي نقش يکسان نداشته باشند و اين ويژگي هاي غير مرتبط باعث شوند که دو رکورد با فاصله ي نزديک به هم ، دور از هم تشخيص داده شوند و دسته بندي به درستي انجام نگيرد.اين مشکل را اصطلاحاً بلاي ابعاد ١ مي گويند [٣].
به منظور رفع اين مشکل ، براي محاسبه ي فاصله ي دو رکورد، ويژگي هايي که داراي اهميت بيشتري هستند را نسبت به ويژگي هايي که اهميت کمتري دارند، بيشتر تأثير مي دهيم . به اين منظور بايد براي هر ويژگي i يک وزن Wi تعريف شود. هر چه قدر وزن يک ويژگي بزرگتر باشد، ميزان تأثير آن در محاسبه ي فاصله بيشتر است .
اگر براي n ويژگي موجود در پايگاه داده ها يک بردار n بعدي از وزن ها به صورت تعريف کنيم . آنگاه فرمول محاسبه ي فاصله ي بين دو رکورد x١ و x٢ به صورت زير خواهد بود[٢,٣,٤].
اين نوع محاسبه ي فاصله در واقع فقط به کميت مقدار ويژگي ها نمي پردازد بلکه به کيفيت ويژگي ها نيز اهميت مي دهد و باعث مي شود که دقت دسته بندي بيشتر شود. واضح است هر چه قدر اين وزن ها دقيق تر باشد ، دقت دسته بندي بيشتر مي شود ولي اگر وزن ها بد انتخاب شوند، حتي دقت دسته بندي نسبت به قبل کاهش هم مي يابد.
محققان ، روش هاي مختلفي براي توليد برداروزن خصيصه هـا پيـشنهاد کرده اند. در الگوريتم نزديک ترين کا تـايي همـسايگي بـا تنظـيم وزن ها٢ [٥] به وزن دهي ويژگي ها به منظور افزايش دقت دسته بندي متن مي پردازد. در اين روش به کلمات بصير٣ اهميـت و وزن بيـشتري مـي دهد و براي تشخيص کلمات بصير به بررسي ارتباط اطلاعات بـه دسـت آمده از آن کلمه و برچسب دسته ي متن مي پردازد.
در الگوريتم کا نزديک ترين همسايگي پويا بيز ساده با وزن دهي ويژگي ها٤ [٦] براي وزن دهي به خصيصه ها از اطلاعات متقابل بين هر ويژگي و برچسب دسته استفاده کرده و سعي در بهبود دقت دسته بندي دارد.
در واقع مي توان گفت اين الگوريتم از ايده ي روش WAKNN براي دسته بندي متن در دسته بندي داده هاي غير متني استفاده کرده است . در اين الگوريتم پس از انتخاب k همسايه ي رکورد جديد آن ها را به عنوان داده هاي يادگيري به الگوريتم بيز مي دهيم و آن الگوريتم دسته بندي را انجام مي دهد.
الگوريتم نزديک ترين کا تايي همسايگي پويا٥ [٤] ، از يک روش مبتني بر Chi-squared براي وزن دهي به خصيصه ها استفاده مي کند.
فاصله ي Chi-squared مي تواند بيان کننده ي اين موضوع باشد که يک ويژگي خاص چقدر مي تواند در پيشگويي کلاس تأثيرگذار باشدو اين ايده ي اصلي براي يافتن وزن ويژگي ٦ ها است .
٣- الگوريتم KNNBA
در اين قسمت ابتدا به اختصار در مورد قوانين وابستگي و الگوريتم هايي که اقلام پر رخداد را از پايگاه داده ها استخراج مي کنند صحبت مي کنيم . سپس با استفاده از اقلام پر رخداد يک روش جديد به منظور دسته بندي داده ها با تلفيق نوع خاصي از قوانين وابستگي و الگوريتم نزديک ترين K تايي همسايگي ارائه مي کنيم ، که با وزن دهي به ويژگي ها دقت دسته بندي الگوريتم KNN را افزايش مي دهد.
٣-١- استخراج اقلام پررخداد
يکي از روش هاي داده کاوي استخراج الگوهاي تکرار شونده از بين داده ها مي باشد. در اين روش الگوهاي موجود در داده ها به صورت قوانيني از بين داده هااستخراج مي شوند.
قوانين وابستگي در دو مرحله استخراج مي شوند:يافتن الگوهاي تکرار شونده ، استخراج قوانين وابستگي با استفاده از الگوهاي تکرار شوندة کشف شده در مرحله ي قبل .
مرحلۀ اول به دليل حجم زياد داده ها وقت گير تر و مشکل تر است . تا کنون الگوريتم هاي زيادي براي اين کار ارائه شده است که معروف ترين آنها الگوريتم Apriori است . اين الگوريتم اقلام پررخداد٧ را با چندين بار پيمايش ترتيبي پايگاه داده ها به دست مي آورد. در مرحلۀ i ام اين الگوريتم کليه ي اقلام پررخداد i تايي (اقلامي که داراي قلم هستند) استخراج مي شوند. هر مرحله شامل دو قسمت است : توليد اقلام هاي کانديد و سپس تعيين تکرار (پشتيباني) آنها در پايگاه داده ها.
در مرحلۀ اول الگوريتم کليه ي قلم هاي موجود در پايگاه داده به عنوان اقلام کانديد يکتايي استخراج مي شوند و سپس پشتيباني همه ي اين قلم ها محاسبه مي شود. سپس فقط قلم هايي انتخاب مي شوند که پشتيباني آنها از حد آستانه تعريف شده ، بيشتر باشد.در مرحله ي دوم با استفاده از اقلام انتخاب شده در مرحله ي اول اقلام دوتايي ساخته مي شوند و غيره . در مرحله ي دوم الگوريتم هدف ساخت مجموعه اقلام دوتايي است که از ترکيب برخي ازاقلام کانديد يکتايي به دست مي آيند و اين مراحل تا ساختن مجموعه ي اقلام K تايي ادامه پيدا مي کند.
٣-٢- الگوريتم KNNBA
در اين الگوريتم ابتدا مرحله ي اول الگوريتم Apriori را به منظور استخراج اقلام يکتايي و ميزان پشتيباني آنها اجرا مي کنيم . در اين جا حد آستانه حداقل پشتيباني را صفر در نظر مي گيريم تا هيچ يک از اقلام حذف نشوند. در اين تحقيق براي هر قلم يک ضريب اطمينان قلم تعريف مي شود.
براي هر قلم مانند Vi=Atti ضريب اطمينان قلم درصد رکوردهايي است که مقدار ويژگي i ام آنها برابر با Vi باشد و بيشترين کلاس يکسان را پيشگويي کنند.براي محاسبه ي آن بايد بررسي کنيم که اکثريت رکوردهايي که مقدار ويژگي i ام آنها برابر با Atti است ، کدام برچسب کلاس را پيشگويي مي کنند(مثلاً برچسب کلاس l را پيشگويي مي کنند.) ، سپس ضريب اطمينان را براي قانون زير به دست مي آوريم .
در اين روش براي ويژگيهايي که برخي مقاديرشان زياد تکرار مي شوند(يعني پشتيباني حداقل يکي از قلم هاي مربوط به آن ويژگي از حد آستانه ي پشتيباني تعريف شده بيشتر باشد. ) ، بررسي مي کنيم که آيا اين تکرار زياد با برچسب کلاس مرتبط است يا نه . (يعني ضريب اطمينان حداقل يکي از قلم هاي مربوط به آن ويژگي از حد آستانه ی ضريب اطمينان تعريف شده بيشتر باشد.) اين به اين مفهوم است که آن مقدار خاص براي آن ويژگي احتمال وقوع يک برچسب کلاس خاص را افزايش مي دهد. حال ويژگي هايي که داراي خصوصيت بالا نباشند را در محاسبه ي فاصله با وزن ٠ شرکت مي دهيم . از طرف ديگر براي ويژگيهايي که مقاديرشان بيشتر تکرار شده است ، در محاسبه ي فاصله ارزش بيشتري قائل مي شويم . در اين روش فرض بر اين است که ، اقلامي که پشتيباني بالاتري دارند در محاسبه بر چسب کلاس مهم ترند.
البته براي محاسبه ي وزن ويژگي ها به منظور اينکه تأثير منفي بازه ي مقادير ويژگي هاي مختلف را در محاسبه ي فاصله از بين ببريم ، علاوه بر استفاده از ضريب پشتيباني هر قلم ، حداقل و حداکثر مقادير آن ويژگي در
