بخشی از مقاله
چکیده
تحقیقات اخیر نشان داده است که تکنیکهای خوشهبندی که یک هدف واحد یعنی یک معیار اعتبارسنجی را بهینه می-کنند ممکن است نتیجه رضایت بخشی را فراهم نکند چرا که هیچ معیار اعتبارسنجی به تنهایی برای انواع مختلف مجموعه دادهها به خوبی کار نمیکند.فرایند اصلی داده کاوی استفاده از فناوری اکتشاف داده ها برای استخراج داده ها، ایجاد مدل های پیش بینی با استفاده از درخت های تصمیم گیری و تست و بررسی ثبات و کارآمدی مدل ها است.مشتریان بخش بندی روش فازی c-means به خوشه ها بر اساس صدور صورت حساب، وفاداری و پرداخت رفتارها برای ایجاد مدل های مبتنی بر درخت تصمیم گیری می باشند.تعیین تعداد k خوشه در یک مجموعه داده با دانش قبلی محدود از ارزش مناسب، یک مسئله شایع است که متمایز از حل مسائل خوشه بندی داده است.
برای تصمیم گیری مقدار k چند دسته روش وجود دارد، اما انتخاب بهینه حداکثر فشرده سازی داده ها در داخل یک خوشه و به دقت اختصاص هر مشاهده در خود خوشه دارد.در این مقاله از الگوریتم فازی c-means که یکی از الگوریتمهای پرکاربرد برای خوشهبندی فازی است استفاده کردهایم. برای ارزیابی الگوریتمها از معیار Jm که یکی از معیارهای اعتبارسنجی خوشهبندی فازی است، استفاده نمودهایم. همچنین یک روش موازی برای افزایش سرعت تعیین k در n مشاهده ارائه شده است.ما دو روش برای انتخاب مرکز اولیه جهت صرفه جویی در تکرار محاسبات در خوشه بندی فازی c-means معرفی می کنیم: - 1 انتقال مرکز به جلو؛ - 2 حداقل تاثیر.هر دو روش برای تسریع محاسبات فازی c-means و شناسایی K طراحی شده اند.
-1 مقدمه
دادهکاوی مرحلهای از کشف دانش در پایگاههای داده، زیر رشتهای از علوم کامپیوتر است که پایگاهها و مجموعههای حجیم دادهها را در پی کشف و استخراج دانش، مورد تحلیل و کندوکاوهای ماشینی و نیمه ماشینی قرار میدهد. برای درک بهترخوشهبندی فازی و الگوریتمهای مختلف آن لازم است تا ابتدا با مفهوم مجموعههای فازی و تفاوت آنها با مجموعههای کلاسیک آشنا شویم. در مجموعههای کلاسیک یک عضو از مجموعه مرجع یا عضوی از مجموعه A است یا عضو مجموعه A نیست. مثلا مجموعه مرجع اعداد حقیقی را در نظر بگیرید. عدد 2/5 عضو مجموعه اعداد صحیح نمیباشد حال آنکه عدد 2 عضو این مجموعه است. به زبان دیگر تعلق عدد 2/5 به مجموعه اعداد صحیح 0 است و تعلق عدد 2 به این مجموعه 1 است. در واقع می توان برای هر مجموعه یک تابع تعلق تعریف کرد که مقدار این تابع تعلق برای اعضای مجموعه 1 می باشد و برای بقیه .0 در مجموعههای کلاسیک مقدار این تابع تعلق یا 0 است یا .1 آثار مرتبط مطالعات انجام شده در خوشه بندی فازی c-means گزارش شده و کاربردهای آنمعمولاً هیچ توضیح یا توجیهی برای انتخاب مقادیر خاص برای k نیست.
روش های موجود در زیر توضیح داده شده است.
روش های معیار اطلاعات معرفی شده برای تعیین تعدادی از روش ها مانند معیار آکائیک اطلاعات - AIC - ، و معیار اطلاعات بیزی . - BIC -
روش تئوری اطلاعات در [5] برای انتخاب k به نام روش "jump" اعمال شده است، که حداکثر بهره وری تعداد خوشه تعیین می کند در حالی که خطا با اطلاعات استانداردهای تئوری به حداقل رسانده است.
برای دستیابی و سرعت محاسبات قابل قبول در مجموعه داده ها، بسیاری از محققان از طرح موازی استفاده کرده اند.
Li و [7] Fang یک الگوریتم موازی برای معماری دستورالعمل های منفرد با اطلاعات چندگانه - SIMD - ارائه داده اند.
Dhillon و [8] Modha، K-means توزیع شده که در یک محیط چند پردازنده اجرا می شود، ارائه شده است. Kantabutra و [9] Couch روش برنامه واحد master-slave برای داده های متعدد - SPMD - بر روی یک شبکه ایستگاه های کاری الگوریتم k-means موازی ارائه شده است. تفاوت عمده بین محتوا معرفی شده در این مقاله و پیشنهادات فوق این است که ما یک طراحی ترکیبی از الگوریتم فازی c-means موازی با تعیین مقدار k، محاسبات خوشه بندی، و یک روش بهینه سازی جدید در انتخاب مرکز اولیه ارائه شده است.
این فرایند یعنی تعیین مراکز خوشه و محاسبه درجه عضویت هر داده به k خوشه با استفاده از فرمولهای - 2 - و - 3 - تکرار میشود. زمانی که هیچ تغییری در مراکز خوشه بوجود نیاید و یا پس از تعداد تکرار معینی، الگوریتم متوقف میشود. در پایان، هر نقطه داده به خوشهای که بیشترین درجه عضویت به آن را دارد، اختصاص مییابد. نقطه قوت الگوریتم خوشهبندی فازی c-means این است که الگوریتم از نوع بدون نظارت است. نقاط ضعف این الگوریتم حساس بودن به نویز و حدسهای اولیه است بهطوریکه ممکن است در مینممهای محلی متوقف شود.
.B تعیین مقدار k
تجزیه و تحلیل مشتری در شبکه های مخابراتی را قادر می سازد محدوه K بر اساس اطلاعات ارائه شده توسط اپراتورهای تعیین می شود؛ برای مثال، مقدار در محدوده 1 تا .Kmax مقدار واقعی K در این محدوده باید نسبتا بزرگ تا منعکس کننده ویژگی های مجموعه داده خاص باشد. با این وجود، مقدار نباید بیش از حد نزدیک به تعداد اشیاء باشد زیرا عملیات خوشه بندی کمتر معنی دار است. برای پیدا کردن یک مقدار مناسب برای k، ما روش در [3] برای تولید یک منحنی اعوجاج برای داده های ورودی با اجرای یک عملیات فازی c-means استاندارد در تمام مقادیر K بین 1 و Kmax استفاده می شود.
