بخشی از مقاله
چکیده
خوشهبندی دادهها، روش یافتن ویژگیهای مشابه از میان حجم انبوه دادهها و دستهبندی آنها به گروههایی است که هر یک از این گروهها، خوشه نامیده میشوند. از آنجایی که عوامل مختلفی همچون نویز و تعداد ابعاد دادهها بر روی نتیجه الگوریتمهای مختلف خوشهبندی اثر گذارند، لذا این الگوریتمها نتایج مختلفی تولید میکنند. با توجه به اینکه کیفیت خوشهبندی و صحت خوشههای استخراج شده، بسیار حائز اهمیت است، لذا معیارهایی جهت اعتبارسنجی عملیات خوشه-بندی ابداع شدهاند. شاخصهای اعتبارسنجی خوشهبندی با توجه به اطلاعات مورد استفاده جهت تعیین کیفیت خوشه-بندی، به دو دسته داخلی و خارجی تقسیم میشوند. در این تحقیق سه شاخص ارزیابی استاندارد داخلی کیفیت خوشهبندی Davies-Bouldin، Silhouette و Gap ، مورد بررسی قرار گرفتهاند.
تلاش این پژوهش بر آن بوده است تا شاخص اعتبارسنجی داخلی جدیدی پیشنهاد شود به طوری که با استفاده از الگوریتم خوشهبندی افرازی K-Means و در مقایسه با دیگر شاخصهای معرفی شده، بر روی مجموعه دادههای استاندارد مورد بررسی، بهتر عمل نماید. شاخص معرفی شده در تحقیق حاضر، - Compression And Separation - CAS نام دارد. عملکرد شاخص CAS برای تشخیص تعداد صحیح خوشهها نسبت به شاخص Davies-Bouldin به میزان 27/27%، نسبت به شاخص Silhouette به مقدار 36/36% و نسبت به شاخص Gap به میزان 54/54%بهتر عمل نموده است. نهایتاً میتوان نتیجه گرفت که شاخص CAS با بیشترین تشخیص صحیح تعداد خوشهها، نسبت به سه شاخص استاندارد دیگر مناسبترین عملکرد را بر روی مجموعهدادههای استاندارد دارد.
-1 مقدمه
امروزه افزایش سریع حجم پایگاه دادهها به شکلی است که توانایی انسان برای درک این دادهها بدون ابزارهای قدرتمند میسر نمیباشد. دادهکاوی تکنیکی است که اطلاعات پنهانی از مجموعه دادههای حجیم را استخراج میکند .[1] خوشه مجموعه-ای از اشیاء میباشد که هر شی در یک خوشه نزدیکتر - شبیه تر - به اشیاء همین خوشه میباشد تا به دیگر خوشهها .[2] خوشهبندی عبارت از افراز مجموعهای از اشیاء به داخل گروههای اشیاء مشابه در یک مجموعه داده است .[3] در اکثر روشهای دادهکاوی، مثل درخت تصمیمگیری و شبکههای عصبی، الگوریتمها با یک مجموعهی آموزشی آغاز میشوند و به کمک این مجموعه سعی میشود تا یک مدل برای طبقهبندی دادهها ایجاد شود. در نهایت از مدل ایجاد شده برای پیشبینی دادههای جدید استفاده میشود.
[4] از آنجا که تاکنون الگوریتمهای خوشهبندی زیادی توسعه یافتهاند، مسئله تعیین کیفیت خوشههای تولید شده، موضوعی اساسی در فرآیند خوشهبندی محسوب میشود. اعتبارسنجی خوشهبندی، تکنیکی برای یافتن مجموعهای از خوشهها است به طوری که بهترین تقسیمات طبیعی را در مورد اشیای دادهای انجام دهد بدون اینکه هیچ اطلاعاتی در مورد کلاس دادهها داشته باشد .[5] به منظور ارزیابی نتایج خوشهبندی و تعیین میزان کیفیت آن، معیارها و شاخصهای زیاد و متنوعی مطرح شدهاند که طبیعتاً میزان کارایی آنها در محیطهای مختلف دادهای، متفاوت خواهد بود .[5] روشهای اعتبارسنجی تکنیکهای دادهکاوی، به دو دسته اعتبارسنجی داخلی و اعتبارسنجی خارجی طبقهبندی میشوند.
امروزه از خوشه-بندی افرازی در کاربردهای مختلفی استفاده میگردد. به علاوه، در خوشهبندی افرازی تعیین تعداد خوشهها قبل از آغاز عملیات خوشهبندی ضروری به نظر میرسد. یکی از مهمترین مشکلاتی که پژوهشگران رشتههای مختلف در هنگام استفاده از خوشهبندی افرازی با آن مواجه هستند، تعیین یک مقدار صحیح و بهینه به عنوان تعداد خوشهها میباشد. با وجود اینکه تاکنون روشهای مختلفی جهت ارزیابی عملیات خوشهبندی و متعاقب آن یافتن تعداد بهینه خوشهها ابداع و معرفی شدهاند، هنوز در موارد زیادی برای استفاده از این روشها ابهام وجود دارد.
در این تحقیق، علاوه بر معرفی شاخصهای ارزیابی Davies-Bouldin، Silhouette و Gap، با اعمال آنها بر روی مجموعه دادههای استاندارد و سپس بررسی عملکرد آنها، تلاش بر این است که شاخص اعتبارسنجی داخلی جدیدی پیشنهاد شود که با استفاده از الگوریتمهای خوشهبندی افرازی و در مقایسه با دیگر شاخصهای معرفی شده، بر روی مجموعه دادههای استاندارد بهتر عمل نماید. جهت مقایسه معیار ارائه شده با سایر شاخصها، از الگوریتم خوشهبندی افرازی K-Means استفاده شده است.
-2 مبانی نظری و کارهای انجام شده
-2-1 خوشهبندی
یکی از روشهای بدون نظارت دادهکاوی، تکنیک خوشهبندی است. خوشهبندی شامل افراز دادهها بوده که به استخراج برخی گروهها - یا خوشهها - از نمونه دادهها میانجامد به طوری که نمونههای هر خوشه بسیار شبیه به یکدیگر میباشند و نمونههای هر خوشه با نمونههای دیگر خوشهها بسیار متفاوت هستند .[6] این روش، کاربردهای وسیعی در حوزههای مختلف نظیر پزشکی، روانشناسی، زیستشناسی، اقلیمشناسی، تجارت، طبقهبندی اسناد و بازیابی اطلاعات دارد .[7] کیفیت خوشهبندی به معیار استفاده شده توسط روش خوشهبندی و پیادهسازی آن بستگی دارد.
[8] با استفاده از خوشهبندی به دنبال گروههایی از دادهها هستیم که به هم شباهت دارند و با کشف این شباهتها میتوان رفتارها را بهتر شناسایی نمود و بر مبنای آنها طوری عمل کرد که نتیجهی بهتری حاصل شود. مسئله اساسی خوشهبندی، توزیع دادهها به K گروه مختلف است که دادههای هر گروه با یکدیگر مشابه و دادههای گروههای مختلف با یکدیگر نامتشابه باشند. این تشابه یا عدم تشابه بر اساس معیارهای اندازهگیری فاصله تعریف میشود. تجزیه و تحلیل شباهت یا عدم شباهت، کاهش حجم و ابعاد دادهها و تشخیص دادههای پرت از کاربردهای مهم خوشهبندی هستند.
-2-2 الگوریتم خوشهبندی K-Means
در الگوریتم k-means، مجموعه دادهها به تعدادی خوشههای از پیش تعیین شده، تقسیم میشوند. ورودی الگوریتم خوشه-بندی k-means تعداد k خوشه میباشد. ابتدا k نقطه به صورت تصادفی به عنوان مراکز خوشهها انتخاب میشوند. هر رکورد در مجموعه داده به خوشهای که مرکز آن خوشه کمترین فاصله تا آن رکورد را داد، نسبت داده میشود. معیار محاسبه فاصله در این مرحله هر معیاری میتواند باشد که معمولاً از فاصله اقلیدسی - رابطه - 1 استفاده میگردد.
-2-3 اعتبارسنجی خوشهبندی
از آنجایی که تاکنون الگوریتمهای خوشهبندی زیادی توسعه یافتهاند، لذا مسئله تعیین کیفیت خوشههای تولید شده، موضوعی اساسی در فرآیند خوشهبندی محسوب میشود. اعتبارسنجی خوشهبندی، تکنیکی برای یافتن مجموعهای از خوشهها است به طوری که بهترین تقسیمات طبیعی را در مورد اشیای دادهای انجام دهد، بدون اینکه هیچ اطلاعاتی در مورد کلاس دادهها داشته باشد .[ 5] هدف یک عملیات خوشهبندی خوب و باکیفیت این است که دادههای ورودی به خوشههایی افراز شوند به گونهای که اشیای دادهای موجود در یک خوشه، بیشترین شباهت را به هم و نقاط دادهای موجود در سایر خوشهها، با اشیای دادهای آن خوشه حداکثر تفاوت را داشته باشند.
[10] روشهای اعتبارسنجی تکنیکهای دادهکاوی، به دو دسته اعتبارسنجی داخلی و اعتبارسنجی خارجی طبقهبندی میشوند. شاخصهای اعتبارسنجی داخلی به معیارهایی گفته میشود که تعیین کیفیت عملیات خوشهبندی را با توجه به اطلاعات موجود در مجموعه دادهها به عهده دارند .[11] در مقابل، شاخصهای اعتبارسنجی خارجی، به معیارهایی اطلاق میشود که با استفاده از اطلاعاتی خارج از حیطه مجموعه دادههای مورد بررسی، عملکرد الگوریتمهای خوشهبندی را مورد ارزیابی قرار میدهند .[11] سه شاخص داخلی Davies-Bouldin، Silhouette و Gap در این تحقیق مورد بررسی قرار گرفتهاند.
