بخشی از مقاله
چکیده
خوشهبندی با محدودیت باعث دقیقتر شدن برنامه خوشهبندی از طریق تلفیق محدودیتهای کاربر میشود که میتواند محدودیتهای سطح خوشهای یا سطح نمونه باشد. بعضی فعالیتها تلفیق انواع متفاوتی از محدودیتها را مدنظر قرار میدهند که معمولا بر اساس چارچوبهای خبری بوده و اغلب روشهای واقعیاند که تمام راهحلهای برطرفکننده محدودیتهای کاربر را برمی-شمرند و یا یک حد مطلوب جهانی را هنگام تعیین معیار بهینهسازی پیدا میکنند. در این مقاله ما مدل جدیدی را برای خوشهبندی با محدودیت بررسی می کنیم که بر اساس یک چارچوب برنامهریزی محدودیت است. مقایسه رویکرد ارائهشده با رویکردهای واقعی بر اساس یک رویکرد پرش و کرانی یا رنگی سازی نگارهها روی دوازده مجموعه دادهها ارائه میشود. در پایان، هدف بررسی این موضوع، ارائهشده است.
کلمات کلیدی: خوشهبندی، خوشهبندی با محدودیت، برنامهریزی با محدودیت، داده کاوی
.1 مقدمه
خوشهبندی با محدودیت باعث دقیقتر شدن برنامه خوشهبندی از طریق تلفیق محدودیتهای کاربر میشود. محدودیتها میتوانند شامل محدود کردن اندازه یا قطر خوشهها و محدودیتهای لینک باید باشند. اکثر فعالیتها، متمرکز بر محدودیتهای مبتنی بر نمونه بوده و روشهای خوشهبندی کلاسیک را برای کنترل محدودیتهای لینک باید تائید کردهاند. در این مقاله ما یک الگو جدید را برای خوشهبندی بر اساس برنامهریزی محدودیت مطرح میکنیم که شامل یک متغیر برای هر نقطه است که ارائهدهنده شاخص خوشه این نقطه متعلق به آن است. همچنین ما الگوی خود را از تلفیق دو معیاری خوشهبندی در یک فرایند پیچیدهتر، یعنی یافتن »الحاق« حداقل رساندن قطر و حداکثر رساندن حداقل شکاف توضیح میدهیم.
این مقاله بهصورت زیر ترتیب دادهشده است. بخش 2 اختصاص به مقدمات خوشهبندی محدود و برنامهریزی محدودیت دارد. فعالیت های مرحله در بخش [3] ارائه میشوند. بخش - 4 - اختصاص به معرفی الگوهای CP دارد، اولی و الگو جدید در [3] معرفی میشود. الگوریتمهای فیلترینگ برای معیارهای بهینهسازی در بخش - 5 - معرفی میشوند. ما در بخش - 6 - نشان میدهیم که چطور چارچوب کاری ما میتواند بهراحتی برای حل یک برنامه خوشهبندی محدود دو معیاری تلفیق شود. آزمایشها در بخش 7 معرفی میشوند که عملکرد انعطافپذیری رویکرد ما را نشان میدهد.
.2 مقدمات
-2-1 خوشهبندی با محدودیت
تحلیلهای خوشه، یک برنامه کاوش داده است که هدف آن بخشبندی یک مجموعهاشی به زیرمجموعههای تفکیکشده به نام خوشه است که اغلب بهصورت جستجوی یک بخش فرمولبندی هست طوری که این خوشه مشابه بوده و متفاوت ازشیهای دیگر خوشهها است. این نیازمندیهامعمولاً با یک معیار مطلوب بیان میشوند و برنامه خوشهبندی معمولا با یافتن یک بخش از شی ها که معیار ارائهشده را بهینه میسازند تعیین میشود. یک برنامه خوشهبندی که این معیار را به حداقل میرساند خوشهبندی لینک کامل غیر سلسله مراتبی نامیده میشود. در خوشهبندی تک پیوندی شکاف حداقل بین خوشهها به حداکثر میرسد. بیشتر الگوریتمهای خوشهبندی متکی بر معیار بهینهسازی هستند. اکثر این معیارها NP-Hard هستند، درنتیجه اکثر الگوریتمها به دنبال یک حد مطلوب داخلی هستند.
بهعنوان نمونه، الگوریتم K-means یک حد مطلوب داخلی را برای معیار WCSS و نیز FPF - دورترین نقطه اول - برای معیار قطر پیدا میکند.بهمنظور مدلسازی بهتر برنامه و کاهش پیچیدگی محدودیت های مشخصشده، کاربر افزودهشده و باعث خوشهبندی محدودی میشود که هدف آن یافتن خوشههایی است که محدودیتهای کاربرد را کاهش میدهد. محدودیتهای کاربر میتواند به محدودیتهای سطح خوشهای، نیازمندیهای تعیین گر بر اساس خوشهها، محدودیتهای سطح نمونه و نیازمندیهای تعیینشده بر اساس جفت شیها طبقهبندی شوداخیراً. فعالیتهای زیادی رویکردهای خبری خوشهبندی محدودیت را بررسی کرده است که هدف آن بسط الگوریتم مرسوم برای انواع متفاوتی از محدودیت های کاربر است. معرفی این فعالیتها در بخش - 3 - ارائهشده است.
-2-2 خوشهبندی محدود دو معیاری
هدف خوشهبندی با معیار، کاهش حداکثر قطر یافتن خوشههای همگون هست، اما اغلب از اثر کالبدشکافی [6] رنج میبرد. از طرف دیگر، خوشهبندی با معیار حداکثر رساندن و مینیمم سازی حداقل که هدف آن یافتن خوشههای تفکیکشده مناسب است اغلب دچار تاثیر زنجیرهای [7] است همچنین معیار عمومی WCSS که مجموع مجذور فاصلههای بین نقاط و مرکز خوشه آنها را به حداقل میرساند از تأثیرات نامطلوب رنج میبرد. یک بخشبندی خوب با خوشههای همگون و تفکیکشده مطلوب باید یک حداقل قطر و حداکثر دونیم سازی را داشته باشند که چنین بخشپذیری بهطورکلی وجود ندارد، زیرا دو معیار اغلب در تضاد هستند. در نظر گرفتن این دو معیار باهم طبیعی است و باعث تسخیر نیازهای همگن و تفکیکی برای یک خوشهبندی خوب میشود. یک رویکرد کلی برای کنترل دو معیار بهینهسازی، پیداکرده راهحل های مطلوب »الحاق« هست که امکان توسعه مقدار یک معیار را بدون کاستن مقدار دیگری ندارد.
.3فعالیت مربوطه
به علت سختی مساله خوشهبندی، چند الگوریتم واقعی در این مقاله بررسی میشوند که اغلب اکتشافی، فرا اکتشافی یا تقریبی هستند. یک الگوریتم واقعی بر اساس رنگسازی نگارهها برای بررسی اینکه آیا فاصله بین دو شی میتواند حداکثر قطر باشد یا خیر در [7] پیشنهاد میشود. برای معیار کاهش مجموع درون شاخهای مغایرتها، الگوریتم تکراری انشعابزنی و محدودسازی در [2] ارائه میشود. در مرجع [3] برای بهینهسازی دو معیاری دونیم سازی قطر بدون محدودیتهای کاربرد، یک الگوریتم که یابنده مجموعه کامل و حداقل از راهحلهای مطلوب الحاق است که بخشبندیهایی در اکثر خوشه های Kmax دارد، معرفی میشود.
در مرجع L.De Radt.[ 8] و همکارانش یک چارچوب کاری را در مورد برنامهریزی محدودیت برای کاوش مجموعه الگو- K ارائه میدهند و نشان میدهند که چطور میتواند برای خوشهبندی ادراکی بکار برده شوند. در خوشهبندی ادراکی، یک تعریف دانسته ارائهشده توسط یک الگو همراه هر خوشه هست. J-P.Me tivier و همکارانش در [9] یکزبان مبتنی بر محدودیت را معرفی میکنند که بیانگر پرسشهایی برای کشف الگوها درباز کاوی داده ه است.دیوید سون وهمکارانس یک قالب کاری [1]SAT را برای خوشهبندی محدود - اما تنها برای مسائل با -K=2 مطرح میکنند. انواع مختلفی از محدودیتها مدنظر قرار میگیرند: لینک باید، لینک نتوانستن، قطر و محدودیتهای دونیم سازی، این الگوریتم باعث رسیدن به یک حد مطلوب کلی با معیار قطر یا دو نیم سازی میشود.
مولرو همکارانش در [5] رویکردی را برای خوشهبندی محدود بر اساس برنامهسازی خطی عدد صحیح پیشنهاد میکنند. این رویکرد مجموعه خوشههای کاندید مثل دادهها را در بردارد و یک خوشهبندی را با انتخاب یک زیرمجموعه مناسب میسازد. این موجب انواع متفاوتی از محدودیتها بر خوشهها با بر مجموعهای از خوشهها میشود، اما هیچ محدودیتی بر اشیایی اختصاصی ندارد. در این مقاله، ما استفاده از برنامهریزی محدودیت را برای خوشهبندی محدود بررسی میکنیم. برنامهریزی محدودیت یک رویکرد نویدبخش برای بازکاوی دادهها از طریق برنامههای مختلف مثل بازکاوی مجموعه فقره [10,11]، بازکاوی الگو آسمانی [12] یا ساخت درخت تصمیمگیری نشان دادهشده است.
.4 الگو جدید CP برای خوشهبندی محدود
در این مقاله مجموعهای از n نقطه نیک معیار ناهمگونی بین جفتهای نقاط j,i که D - I,j - تلقی میشود ارائهشده است. هدف این مدل یافتن این موضوع است که بخشبندی به شاخههای K، مجموعهای از محدودیتهای کابل را برطرف کرده و یک معیار ارائهشده را بهینهسازی میکند. در این مقاله، ما یک مدل جدید CP را معرفی میکنیم که تنها بر اساس مجموعهای از متغیرها برای تخصیص تعدادی خوشه به هر نقطه است. درنتیجه، تعدادی از خوشههای k تنها توسط Kmax,Kmin توسط کاربر ارائه میشوند. در ادامه ما دو مدل برای تسهیل مقایسه معرفی میکنیم. در هر دو مدل محدودیتهای CP بیان میکند که محدودیتهای کاربر مشابه هستند اما آنها بیان میکنند که نیازهای بخشبندی و معیار بهینهسازی متفاوتاند. تمام معیارهای بهینهسازی در مدل جدید توسط محدودیت های جدید کلی با یک الگوریتم فیلترینگ بیان میشود. تفاوتهایی بین دو مدل مهم هستند، زیرا مدل خرید متغیرها و محدودیتهای کمی دارد، درحالیکه نتیجهبخشتر از مدل قبلی است. جدول 1 تفاوتهای بین این دو مدل را مطالعه میکند.
-4-1 متغیرها
در اولین مدل، برای هر خوشه c {1, k }، نقطه با کوچکترین شاخص بهعنوان نقطه نماینده خوشه محسوب میشود.یک متغیر عدد صحیح Ic معرفی میشود، مقدار آن، شاخص نقطه نماینده خوشه c هست، دامنه IC بنابراین مجموعه اعداد صحیح [1,n] است. Z این آرایه هست .>,1'…',.@ تخصیص یک نقطه به یک خوشه این نقطه را به نماینده خوشه تخصیص میدهد؛ بنابراین برای هر نقطه i {1, n } ، یک متغیر عدد صحیح Gi {1, n} معرفی میشود: Gi نقطه نماینده خوشه است که شامل نقطه i هست. برای معرفی هر معیار بهینهسازی، در هر دو مدل، یک متغیر مقدار شناور معرفی میشود؛ که برای معیار قطر D نامیده میشود، S برای معیار دونیم سازی و v برای معیار .WCSD
-4-2 محدودیتهای بخشبندی
-4-2-1 اولین مدل
برای بیان اینکه نتیجه باید یک بخشبندی باشد، ما محدودیت های زیرا وضعشده است:
هر نماینده متعلق به خوشه خود است: برای هر C [1, K ] و ما GLC IC قرار میدهیم. این محدودیت توسط مؤلفه محدودسازی - g.IC,IC - CP ارائه میشود و مؤلفه محدودسازی - A,B,C - با A آرایهای از متغیرها ومتغیرهای B,C رابطه A[B]=C را تنظیم میکند.هر نقطه به یک نماینده تخصیص داده میشود: برای هر i [1, n ] ، ما نیاز به - C[1, K ] - Gi I Cداریم.این رابطه میتواند توسط IC Gi } 1 {C بیان شود که توسط یک محدودسازی CP درواقع - 1,I,Gi - معرفی میشود. این محدودسازی رابطهای را تنظیم میکند که مقدار Gi باید بهطور حقیقی یکبار در آرایه I باشد.
