مقاله استفاده از خوشه بندی بهینه در طبقه بندی k نزدیکترین همسایه

بخشی از مقاله

*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***

استفاده از خوشه بندي بهینه در طبقه بندي k نزدیکترین همسایه

چکیده: در این مقاله با استفاده از الگوریتم هاي تکاملی، روش طبقه بندي k -نزدیک ترین همسایه در شناسایی الگو بهبود یافته و سرعت عملکرد آن ارتقاء داده شده است. روال اصلی الگوریتم پیشنهاد شده بر این ترتیب بوده است که داده هایی را که پیش تر با روش هاي طولانی و زمان بر خوشه بندي و طبقه بندي می شدند، اینک با روشی سریع تر و با درصد صحت بالاتر، خوشه بندي نموده و در نهایت توسط الگوریتم -kنزدیک ترین همسایه طبقه بندي شوند. در این مقاله با استفاده از روشی بهینه و جدید هم مجموع فواصل درون خوشه اي حداقل شده اند و هم با وزن دهی مناسب به روابط، فواصل مراکز خوشه ها، این فواصل به حداکثر مقدار خود رسیده اند. در نتیجه ي این تغییرات، خطاي متداول در طبقه بندي نمونه هاي آزمایشی با توجه به نمونه هاي آموزشی حداقل شده و دقت عملکرد الگوریتم به میزان زیادي بهبود یافته است.
کلمات کلیدي: طبقه بندي، خوشه بندي، K-means، KNN، PSO، الگوریتم ژنتیک .

-1 مقدمه

با پیشرفت تکنولوژي و تئوري اطلاعات، نیاز بشر به دسته بندي و مدیریت اطلاعات روز به روز افزایش میابد. در هنگام مواجهه با حجم داده هاي بزرگ1، براي جلوگیري از پراکندگی، در هم ریختگی و همچنین مدیریت بهینه و پردازش مناسب آن ها، طبقه بندي و شناسایی الگوها می تواند نقش موثر و مهمی در تجزیه تحلیل داده ها داشته باشد. تاکنون روش هاي متعددي براي طبقه بندي و خوشه بندي در زمینه هاي مختلف پیشنهاد شده است، که در اینجا به اختصار تعدادي از آن ها را بررسی می کنیم. روش هایی همچون ماشین بردار پشتیبان (SVM2)، -k تعداد نزدیک ترین همسایه (KNN3)، درخت تصمیم گیري4، شبکه ي عصبی 5، الگوریتم رده بندي بیزین6، براي طبقه بندي داده هاي خطی توصیه شده اند .[1] یکی از ساده ترین و متداول ترین روش ها درمیان روش هاي خوشه بندي با الگوریتم تکراري، روشی به نام K-means است که در آن داده ها به k گروه متمایز تقسیم می شوند. در این روش، فاصله ي هر نمونه ي آزمایشی جدید ابتدا با تمام مراکز خوشه ها اندازه گیري می شود و سپس نمونه ي جدید نزدیک ترین خوشه نسبت به خود را انتخاب کرده و با آن خوشه بندي می گردد KNN .[2] روش دیگري است که اولین بار توسط E.Fix و [3] J.Hodges ارائه گردید و الگوریتم آن شامل محاسبه ي فاصله اقلیدسی درمیان نقاط نمونه هاي آزمایشی و تشکیل ماتریس فواصل بین تمام جفت نقاط موجود (x,y) است. هریک از نقاط داده در این مجموعه به کلاسی تعلق دارند که با برچسب هايc  {c1 , ,c N } تعیین می گردند. سپس به تعداد K نمونه آموزشی داراي کمترین فاصله از نمونه آزمایشی انتخاب شده و با توجه به برچسب کلاس آنها، در مورد برچسب کلاس داده آزمایشی موردنظر تصمیم گیري میشود (طبقه بندي صورت می گیرد). تصمیم گیري در مورد برچسب داده جدید از روي برچسبهاي Kنزدیکترین همسایه انتخاب شده به روشهاي مختلفی مانند محاسبه مد، میانه و یا میانگین آنها ممکن است صورت پذیرد که بسته به نوع مسئله و داده ها متغیر است.

تحقیقات و پیشرفت هاي زیادي در روش KNN تاکنون صورت گرفته است. Z.Zhang و همکارانش [4] تنظیمات بهینه اي را براي روش KNN پیشنهاد کردند تا در زمان مواجهه با حجم داده هاي بزرگ عملکرد پایین این روش را بهبود دهند. [5] M.Kerwin توانست با استفاده از منطق فازي روشی را ابداع کند تا KNN بتواند نوع نمونه هاي آزمایشی خود را شناسایی کند و بر اساس این روش طبقه بندي نماید. [6] R.L.Brown، توانست با ترکیب قالب قوانین فشردگی7 و قالب هاي شناختی8، الگوریتم جدیدي را پیشنهاد دهد که الگوریتم درخت تراکم9 نام دارد. درحالی که بسیاري از روش هاي شناسایی الگو در این حوزه بر اساس ویژگی هاي اصلی اندازه گیري هاي متریک نا متجانس می باشند [8,7]، روش هاي دیگري هم براي انواع غیر متریک کاربرد دارند که البته تنها در فضاهایی با ابعاد محدود کاربردي می باشند .[10, 9]

در این مقاله سعی شده است تا با بهره گیري از روش هاي تکاملی، یکی از مشکلات الگوریتم KNN ، بهبود داده شود. یکی از مشکلات رایج در روش KNN امکان بروز خطا در تشخیص کلاس، به هنگام مواجهه با کلاس هاي متراکم و پر ازدحام است .[1] با توجه به شکل (1)، همان طور که مشاهده می گردد، یک سري داده با دو کلاس مشخص توسط روش KNN طبقه بندي نا متوازن شده اند. منظور از نامتوازن در این طبقه بندي آن است که یک کلاس از کلاس دیگر چگال تر و فشرده تر بوده و حتی اگر تعداد نمونه هاي آزمایشی در هر دو کلاس برابر باشند، فضایی که این نمونه ها اشغال کرده اند یکسان نمی باشد و در نتیجه کلاس ها نامتوازن می شوند. حال اگر به این مجموعه نمونه آزمایشی جدیدي اضافه شود و محل آن در ناحیه ي مرزي واقع شده باشد، مطابق با این روش در طبقه بندي آن خطا رخ خواهد داد. علاوه بر این در رویارویی با حجم داده هاي بزرگ، از سرگیري محاسبات و اندازه گیري فواصل نمونه جدید با تک تک مراکز خوشه ها بار محاسباتی بالایی دارد و زمان بسیاري را به خود اختصاص می دهد.

شکل.1 تأثیر توزیع چگال نمونه هاي آزمایشی بر روي نتایج طبقه بندي

R.Lu Li و همکارانش [11]، راهکاري را بر اساس فشردگی و ازدحام کلاس ها ارائه داده اند، تا مشکل خطاي احتمالی در طبقه بندي نامتوازن را براي نمونه هاي آزمایشی برطرف سازند. اگرچه این روش سریع تر و کارامدتر بوده و نرخ دقت طبقه بندي KNN را بالا برده است ولی در مجموع این روش براي نمونه هاي پراکنده و تنک میسر نمی باشد و موجب طبقه بندي نا متوازن آن ها می گردد.

از طرفی دیگرهمان طور که قبلاً مطرح گردید، یکی دیگر از معضلات بزرگ روش KNN میزان عملکرد پایین آن در هنگام مواجهه با حجم زیاد داده و بار محاسباتی سنگین می باشد. براي هر نمونه آزمایشی جدیدي که به مجموعه ي قبلی اضافه می شود، محاسبات باید از سر گرفته شود و دوباره طبقه بندي با توجه به تمام نمونه هاي آموزشی انجام گیرد که علاوه بر حجم

محاسباتی، زمان زیادي را به خود اختصاص می دهد. تاکنون تلاش هاي بسیاري براي کاهش بار محاسباتی در روش هاي مختلف طبقه بندي صورت گرفته است. بعضی از روش ها همچون برنامه هاي عددي10، برنامه ریزي پویا11و شاخه و کران12 براي کاهش محاسبات ارائه شده اند. با این که این تکنیک ها نسبت به روش محاسباتی متداول بهتر و کارامدتر می باشند، ولی در مقایسه هنوز بار محاسبات بالایی داشته و ایده آل نمی باشند. در این میان روش هاي الگوریتم تکاملی و محاسبات نرم پیشرفت بسزایی در این زمینه داشته اند و بسیاري از مسائل بهینه سازي را حل نموده اند.

ما در اینجا روشی را پیشنهاد داده ایم که در آن با استفاده از روش هاي تکاملی، نمونه ها بتوانند با حداقل مجموع فواصل درون خوشه اي، خوشه بندي شوند و به منظور کاهش خطا در طبقه بندي، خوشه ها در دورترین مکان نسبت به هم واقع شوند.

-2 الگوریتم تعمیم یافته KNN تکاملی

در این مقاله براي مسائل مربوط به طبقه بندي KNN ابتدا داده هاي آموزشی را خوشه بنـدي کـرده و در نتیجـه توزیـع نسبتاً متوازنی از نمونه هاي آموزشی را فراهم می آوریم. سپس بر اساس الگوهاي آموزشی، نمونه هـاي آزمایشـی جدیـد توسط الگوریتم توسعه یافته طبقه بندي KNN کلاس بندي می گردند. الگوریتم ساده طبقه بندي KNN و خوشه بنـدي K-MEANS به صوریت زیر تعریف می شوند.

1-2 الگوریتم KNN
الگوریتم KNN در حالت کلی شامل مراحل زیر می باشد:
• فرض کنید k تعداد نزدیک ترین همسایه ها و D مجموعه هاي آموزشی داده شده مسأله باشند.
• براي هر نمونه ي آزمایشی جدید('z  (x',y ، که در آن x' بردار ویژگی هاي داده آزمایشـی و y' برچسـب
کلاس آن هاست، مراحل زیر به ترتیب اجرا می شوند.
• ابتدا فاصله d(x',x) بین D و هر نمونه ي (x,y)Dمحاسبه می شود.

• سپس k تعداد از نزدیکترین نمونه ها ي آموزشی به z را انتخاب می کنیم.

• بدین ترتیب نمونه هاي آزمایشی با استفاده از برچسب هاي نزدیک ترین همسایه هایشان طبقه بندي می گردند

.[3]

2-2 روش K-MEANS

روش K-MEANS اولین بار توسط MacQueen در سال [2] 1967، مطرح گردید و از سـاده تـرین روش هـایی اسـت کـه مسائل مربوط به خوشه بندي را حل می کند. روند این الگوریتم راه ساده اي براي طبقه بندي داده ها به خوشه هایی با تعداد مشخصمثلاً( (K می باشد. ایده اصلی این الگوریتم، تعریف K مرکز براي هر خوشه است. این مراکـز بایـد بـه نحـو مناسـبی انتخاب شوند تا محل هر انتخاب به نتیجه اي مجزا منتهی گردد. بنابراین بهترین انتخاب، انتخابی اسـت کـه خوشـه هـا را در دورترین مکان ممکن از هم جاي دهد. گام بعدي خوشه بندي هر نقطه از مجموعه داده ها، بـه مرکـز خوشـه ي مناسـب آن نقطه است. وقتی تمام نقاط براي اولین بار خوشه بندي شدند، مرحله اول تکمیل شده است و خوشـه بنـدي اولیـه بـه انجـام

رسیده است. در این مرحله مراکز جدید براي خوشه هاي حاصل از مرحله قبلیباید مجدداً محاسبه گردند . پس از بـه دسـت آوردن این K مرکز جدید، رابطه ي بین نقاط داده ي مشابه مجموعه ي قبلی و نزدیک ترین مراکز جدید، باید مشخص گردد. بنابراین در این روش یک حلقه ایجاد می شود که در نتیجه ي این حلقه محل مراکز خوشه ها در هر مرحله تغییر می کننـد، تا جایی که ثابت بمانند و دیگر تغییر نکنند یا به عبارتی دیگر حرکت نکنند.

در نهایت، هدف این الگوریتم به حداقل رساندن میزان خطا است که در این مورد خاص یک تابع مربع خطا به قـرار زیـر مـی باشد:

به طور خلاصه الگوریتم K-MEANS از مراحل زیر تشکیل شده است:

• K نقطه را در فضا به عنوان نقاطی که قرار است خوشه بندي شوند، انتخاب کنید. این نقاط به عنوان مراکز اولیه خوشه ها اختیار می شوند.

• هر داده اي را به خوشه اي مرتبط سازید که کم ترین فاصله را با مرکز آن خوشه داشته باشد.

• وقتی تمام نقاط، خوشه بندي شدند مراکز خوشه هارا مجدداً محاسبه کنید (با محاسبه ي مرکز ثقل خوشه ها).

• دو مرحله ي قبل را تا جایی تکرار کنید که مراکز دیگر حرکت نکنند.

• بدین ترتیب نمونه هاي آزمایشی با نزدیک ترین نمونه ها در همسایگی شان خوشه بندي می گردند.

-3 روش پیشنهادي

در این مقاله در ابتدا با استفاده از روش هاي متداول، داده ها توسط روش K-means خوشه بندي شـده و در گـام بعـدي بـا بهره گیري از روش KNN طبقه بندي شده اند. در ادامه روشی جدید پیشنهاد شده است که در آن با بهره گیري از الگوریتم تکاملی، داده ها خوشه بندي شده اند. معیار هایی که در این خوشه بندي مد نظر قرار گرفته شده اند، حداقل رسـانی فواصـل درون خوشه اي نمونه ها و حداکثر رسانی فواصل برون خوشه اي نسب به یکدیگر بوده است . درواقع در الگوریتم اصلی، وزنی براي رابطه در نظر گرفته شده است که با انتخاب مناسب آن وزن، رابطه فاصله ي خوشه ها نسبت به یکدیگر تنظـیم شـوند. این وزن دهی با توجه به نوع داده می تواند تغییر کند. کار عمده اي که توسط الگـوریتم تکـاملی انجـام گرفتـه اسـت، ایجـاد حداقل مقدار مجموع فواصل درون خوشه اي بوده است. در نهایت این دو نوع روند کاري (روش متداول و روش تعمـیم یافتـه توسط الگوریتم تکاملی) با یکدیگر مقایسه شده اند و کیفیت عملکرد آن ها بر روي یک دسته داده ي مشابه آزمایش شده اند.

-4 نتایج شبیه سازي روش متداول خوشه بندي

در این شبیه سازي که با استفاده از روش هاي متدوال در شناسایی الگو صورت گرفته است، از داده هایی اسـتفاده شـده کـه مناسب و سازگار با روش هاي طبقه بندي و خوشه بندي بوده اند و صحت کلاس ها و ویژگی هاي آن ها از قبـل تأییـد شـده است. به همین منظور از مجموعه ي داده هاي مربوط به دستگاه الکتروانسفالوگرافی (١٣(EEG استفاده شده اسـت. تمـام ایـن مجموعه داده ها از اندازه گیري پیوسته حالات چشم توسط حسگرهاي دقیق تهیه شده است. طول زمان اندازه گیري براي هر مجموعه داده 117 ثانیه بوده است. در این آزمایش، حالت چشم توسط دوربین حسگر در حین اندازه گیـري EEG تشـخیص داده شده و سپس به صورت دستی به مجموعه اطلاعات اندازه گیري شده افزوده شده است. با تجزیه و تحلیل هر قاب تصـویر تهیه شده، کلاس (1) مربوط به حالت چشم بسته و کلاس (0) مربوط به حالت چشم باز است.

هدف در این جا بر این بوده است که ابتدا بخشی از این داده ها را به عنوان نمونه هاي آموزشی فرض کرده و الگوریتم خوشه بندي را بر روي آن ها پیاده کنیم. سپس داده هاي آزمایشی را وارد کرده و با توجه به نمونه هاي آموزشی طبقه بندي گردند.

در همین راستا، 70 درصد داده هاي ورودي با ویژگی هاي مشخص به عنوان داده ي آموزشی در نظـر گرفتـه شـده انـد و بـا استفاده از برنامه ي مناسب ترتیب گزینش این داده ها بر هم زده تا فرآیندي انتخاب کاملاً اتفاقی و تصادفی در نظـر گرفتـه شود. سپس ویژگی ها و برچسب مربوط به هر داده ي آموزشی را مشخص کرده تا خوشه بنـدي توسـط الگـوریتم K-means انجام گیرد. پس از خوشه بندي داده هاي آموزشی، داده هاي آزمایشی هریک به نوبت وارد حلقه ي طبقه بندي می شوند. در این روش با استفاده از الگوریتم KNN برچسب مناسب هر داده ي آزمایشی تعیین می گردد. در گام آخر با توجـه بـه دانـش قبلی نسبت به ویژگی ها و کلاس صحیح تمام نمونه هاي آزمایشی و آموزشی، صحت طبقه بنـدي و خوشـه بنـدي الگـوریتم مشخص شده است.

در شکل (2) نتایج شبیه سازي را براي خوشه بندي K-means می توان مشاهده کرد. درصد صحت طبقه بندي، براي مقادیر مختلف خوشه (براي تعداد 1،20،15،10،5،4،3،(2 و براي تعداد مختلف K نزدیک ترین همسایه 3)،2،1،(4 محاسبه و ترسیم شده است. همان طور که مشاهده می شود براي خوشه هاي کم تعداد 4)،3،2،(1 درصد صحت مقدار ثابتی می باشد و نسـبت به حالتی که خوشه بندي انجام نشده است 1)خوشه) تغییر چندانی نمی کند. با این حال در شکل (3) که زمان محاسبات این متغیرها را نشان می دهد، تغییرات محسوس تر بوده و می توان آن را به خوبی مشاهده کرد. این در حالی است کـه وابسـتگی صحت طبقه بندي به تعداد خوشه ها در آزمایش هایی با خوشه هاي بالاتر بهتر مشاهده می شود.

-5 نتایج شبیه سازي روش تعمیم یافته تکاملی خوشه بندي

در این جا با بهره گیري از الگوریتم تکاملی، روشی براي طبقه بندي داده هاي قبلی پیشنهاد شده که در آن داده ها بـه جـاي محاسبات سربار k-means ، با دقت بیش تر خوشه بندي شوند و در نهایت با استفاده از KNN طبقه بنـدي گردنـد. در ایـن الگوریتم، داده هاي آموزشی به جاي محاسبات k-means توسط الگوریتم تکاملی خوشه بندي شده و در مرحله ي بعد همانند قبل توسط KNN طبقه بندي می گردند. سپس داده ها آزمایشی جدید به مجموعه ي قبلـی اضـافه مـی شـوند و فرآینـد ي طبقه بندي تکمیل می گردد.

در این بخش از دونوع الگوریتم تکاملی براي انجام محاسبات بهره گرفته شده است. روش اول، روش الگوریتم ژنتیک است که از روش هاي قدیمی و مشهور در زمینه ي الگوریتم هاي تکاملی می باشد. همان طور کـه در شـکل (4) مشـاهده مـی گـردد، درصد صحت پیشرفت زیادي نسبت به روش k-means داشته است. زمان محاسبات نیز به نوبه ي خود کوتاه تر از روش قبلی بوده است که تفاوت آن را در شکل (5) می توان مشاهده نمود.

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

از آنجا که با خوشه بندي داده هاي آموزشی ممکن است صحت نتایج نسبت به نتایج الگوریتم KNN عادي (معادل با 1 خوشه) کمتر شود (به علت امکان دیده نشدن برخی از نزدیکترین همسایه ها توسط داده آزمایشی)، لازم است خوشه بندي به بهترین صورت ممکن خود انجام پذیرد. با توجه به نتایج بدست آمده از شبیه سازي ها می توان دید که استفاده از الگوریتم PSO براي خوشه بندي اولیه داده هاي آموزشی به طور کلی منجر به کسب نتایج سریعتر با حفظ میزان صحت مطلوب نسبت به نتایج ناشی از خوشه بندي با الگوریتم هاي ژنتیک و k-means شده است. با توجه به شکل هاي 6 و 7 می توان مشاهده کرد که با خوشه بندي 5 خوشهاي توسط PSO و سپس طبقه بندي با -4 نزدیکترین همسایه، میزان صحت طبقه بندي آزمایشی 97.5 درصد در زمان حدود 13 ثانیه فراهم شده است. در حالی که همین میزان صحت با خوشه بندي توسط الگوریتم ژنتیک در حدود 17 ثانیه و براي الگوریتم k-means در حدود 45 ثانیه بدست می آید. همچنین با توجه به شکل

7 سریعترین نتایج ناشی از PSO در حدود 3 ثانیه بوده است، در حالی که سریعترین نتایج بدست آمده از GA و k-means به ترتیب 8 و 10 ثانیه بوده است.

شکل-2میزان درصد صحت روش طبقه بندي KNN با خوشه بندي K-means

شکل-3 زمان انجام محاسبات روش طبقه بندي KNN با خوشه بندي K-means