خوشه بندی مقيد

صفحه 1:
به نام خدا خوشه‌بندي مقید Coxstroced Chsterter PS enc 

صفحه 2:
© مقدمه ای بر خوشه بندی * ارزیابی خوشه بندی © خوشه ‎Gay‏ مقيد © جالشها و راهكارها ‎٩‏ پژوهش های انجام شده ‎ ‎harif ‎۱ < 

صفحه 3:
9 خوشه‌بندي گروه‌بندي داده‌ها به كونماي كه خصوصیات مشترک بین داده‌هاي هر گروه زياد و خصوصيات مشترك بين كرودهاي متفاوت كم باشد. سول ا: خصوصیات مشترک؟ چگونگي تشخیس خصوصیات؟ طیف وسیع کاربرد ادگيري ماشین. هوش مصنوعي. الگوشنا علوم اجتماعي. اقتصاد و تجارت. علوم كام ‎٠‏ وب كاويء تحليل بايكاه داده. بردازش متون و تصاوير. علوم بزشكي. ‎oe ‎ ‎ ‏خوشه‌بندي به عنوان يك مساله مشکل #مهمترين دلايل مشكليودن مساله: بدون ناظر بودن الكوريتموهاي خوشهبندي © ابهام در تعريف خوشه مناسب 9 ‎Sew ea ye ©‏ ' ‎ ‎ ‎ ‏یف تابع هدف مناسب به منظور خوشه‌بندي عدم وجود الگوریتم جامع براي حل همه مسائل خوشه‌بندي ‎ ‎ ‏مله ادع ع0 ۱0 

صفحه 4:
. روشهاي خوشه‌بندي (دسته بندی) یبای * خوشهبندی در یک ساختار سلسله‌مرانبی (دندروگرام) Agglomerative ‏يا‎ =.» Divisive + (BRICH) * تقسیم مجموعه داده یه ۴ فراز که هر افرازنماینده یک خوشه می‌باشد * افرازبندی بر حسب یک تابع هدفه تايع هدف؟ * استفاده از اطلاعات ویژه ماتریس شبامت اده‌ها جهت خوشه‌بندی ماتریس شیاهت داده‌ها؟ حجم بالای محاسیات, (Spectral) مبتنی بر شبکه * تشکیل ساختار شبکه‌ای در فضای داده‌ها ‎(STING)‏ * زمان پردازش پایین و عدم وابستگی به تعداد داده‌ها, ساخت شبکه؟ مبتنی بر چگالی * استفاده از چگالی توزیع داده‌ها جهت تشخیص و بسط خوشه‌ها (DBSCAN) مدیریت نویز در داده‌ها 

صفحه 5:
ارزیابی کلاسترینگ ‎٩‏ چند مساله ‎٩‏ تمایل به خوشه بندی شدن داده؟ ‎٩‏ آیا یک ساختار غیر تصادفی در داده وجود دارد؟ ۶ استفاده از تستهای آماری 9 تعداد خوشه ها؟ ‎٩‏ برخی الگوریتم ها نیاز به دانستن تعداد خوشه ها قبل از خوشه بندی دارند. © راهکارهای تقسیم و ادغام با معیارهایی از قبیل واریانس درون و برون خوشه ای © کیفیت خوشه بندی انجام شده؟ ‎ ‎٩‏ خوشه بندی انجام شده چقدر خوب است؟ * ارائه معیارهای ارزیابی مناسب ‎ ‎ ‏مله ادع ع0 ۱0 

صفحه 6:
ویژگیهای یک معیار ارزیابی مناسب (4 شرط) ۶ رصان © هر چه خلوص در خوشه بندی (با دانستن کلاس اصلی داده هاء داده های هم كلاس در یک خوشه قرار بگیرند) بیشتر باشد این معیار بیشتر است. © داده های دسته های متفاوت در خوشه های متفاوت قرار داده شوند. 2-08 

صفحه 7:
ارزیابی کلاسترینگ (کیفیت خوشه بندی انجام شده؟) © سم 9/۲] * نقطه مقابل ربمم ‎Ohster‏ ‏* داده ها ی دسته های یکسان در خوشه های یکسان قرار داده شوند. ‎ag‏ وف ‎ 

صفحه 8:
ینگ (کیفیت خوشه بندی انجام شده؟) بی کلاستر ۶ پم بو در برخی مسایل دسته ای به نام «متفرقه» داریم که شامل داده هایی است که نمی توانند با داده های دیگر کلاسها هم خوشه شوند. * جریمه التساب اين نوع داده ها به یک خوشه خالص بیشتر از انتساب آنها به خوشه متفرقه است 9 

صفحه 9:
یابی کلاستربنگ (کیفیت خوشه بندی انجام شده؟) ۶ یووم صصاه ‎Good‏ ‏* هدف: ممانعت از شکسته شدن دسته های کوچک اشیا © تقسيم یک دسته کوچک از اشیا به دسته های ریز بسیار خطرناکتر از تقسیم دسته بزرگ به دسته های کوچکتر است. * داده ها ممکن است با فرض نویزیا «طامی حذف شوند. كاك 

صفحه 10:
ارزیابی کلاسترینگ (کیفیت خوشه بندی انجام شده؟) * معیار اس 1 ‏را > رما گز‎ & Clo;) = C(oj) Ce tr :0( ‏ح‎ ‎orrectnes(0no)= J) cea, Correctness(oi.0j) Secrecy oli ‏(«مان زگ‎ 7 0۱| Precision BCabed Correctness(o7,09) op Mojli Fj, Lo 7 Lei Recall BCubed = Sharif UuWERsITY oF TEcHNOLOSY, ao 

صفحه 11:
مسائل مطرح خوشه‌بندي ‎٩‏ ذات بدون ناظر مساله ۶ پیش فرضهاي اولیه ساختار داده ها ‎٩‏ معيارهاي فاصله و شباهت © تابع هدف © عدم انطباق پیش فرضها و مدل واقعي «اسسحب بل« راه حل؟ استفاده از اطلاعات جانبی براي کمك به الگوريتم‌هاي خوشه‌بندي جهت تولید فرض‌هاي صحیح 

صفحه 12:
استفاده از اطلاعات جانبي در خوشه‌بندي ۶ اطلاعات جانبي ‎٩‏ ساختار داده‌ها هدف خوشه‌بندي شکل خوشه‌ها بيشیته اندازه خوشه‌ها حداکثر اعضاي هر خوشه قيدهاي در سطح نمونه *_قيدهاي باید-پیوند (0)ب < ‎٠‏ قيدهاي تفي ايبوف (ز0) لط سين سلسم ‎ ‎ ‎ ‏© قابليت اين قيدها در تعريف قيدهاي بيجيده تر ‏© قيد وجود حداقل يك همسايه در فاصله 6: با ايجاد قيد بايد-بيوند ميان هر داده و حداقل يكي از نقاط موجود در همسايكي 8 ‎ ‎ ‎ 

صفحه 13:
خوشه‌بندي مقید (دسته‌بندي) Sharif 

صفحه 14:
خوشه‌بندي مقید (دسته‌بندي ) 6 ارضاء تمامي قیدها به طور کامل * رویکرد جستجوي حریسانه. عدم یافتن يك جواب ممکن براي مساله حتي در صورت وجود جواب ‎COP-MKOCOOG [DarptshPOd] ©‏ ارضاء فرم: تا حد ممکن سعي در ارضاء قيدها دارند. ‎77۲ ‏عبارت جریمه برای نقض قیدها در تیم هدف ‎POKoraw [Dirks]‏ ‎ ‎ ‏عبارت جریمه براي ‏قیدها در تابع هدف و يادكيري متريك [0] سسی0۳00 ‎ 

صفحه 15:
خوشه‌بندي مقید (دسته‌بندي) © سلسله مراتبي: © با تغيير الكوريتمهاي خوشهبندي سلسلهمراتبي برآورده کردن قیدها را نیز در آنها تعبیه مي‌نمایند. ‎٩‏ خوشه‌بندي با ساختن دندروگرامي از داده‌ها * روش ‎ab‏ © ابندا هر داه بهعتون یك خوشه درنظر گرفته مي شود © عمل ادغام خوشهها تا هنگامي که ادغام أنها هيج قيدي را نقض نکند روش [09ه0] مطلنه) © ابتدا يستارهاي تراكذري مربوط به فيدهايباید-یوند )) محاسبه مي‌شود © خوشه‌بتدي را با 2609۳ خوشه آغاز مي‌نماید که266 تعداد نموتدهابي اسث که هيج قيد بايد-بيوندي بر روي أنها اعمال نشده و تعداد اجزاء همبتد حاصل از قيدهاي بايد-بيوند است. © انتخاب دو نزديكترين خوشه و ادغام أنها تا زماتي كه دو خوشه براي ادغام وجود. ‎aio‏ Sharif دسا 

صفحه 16:
خوشه‌بندي مقید (دسته‌بندي) تغییر ماتریس فاصله ‎ve‏ ‏6 استفاده از اطلاعات قیدها قبل از خو براي تغییر ماتریس فاصله و استفاده از 0 میج ۴۹۷۶ wo ar re tg Se], Bes As fenDO] 3) “canes D@ise harif (ل سا 

صفحه 17:
خوشه‌بندي مقید (دسته‌بندي) © يادكيري معيار فاصله به عنوان محبوبترين روش ۰ ۰ خوشه‌بندي مقید 0 هم ۰ © معیار فاصله اقليدسي به عنوان معیار فاصله متداول در 5 فرایند خوشه‌بندي ۰ ۲ ‎٩‏ _ ناكارامدي معیار فاصله اقليدسي در توصیف صحیح فاصله گم ور 9 در يك مجموعه داده نوعي . 6 _ معیار فاصله ماهالانوبیس بسیار مورد توجه قرار گرفته ۰ ۰ ‎cel‏ 422 » harif NVERSTY 0 1 eT (| 

صفحه 18:
مزایا و مشکلات استفاده از قیدها در خوشه‌بندي * مزایا © افزایش میانگین دقت خوشه‌بندي [00:0)06] © تولید خوشه‌هايي به شکل ‎(DerpraPPOAb] aads‏ © مشكلات © شدني بودن (مهاطاصج 0 © مفید نبودن هر مجموعه اي از قیدها [)۳۳»()] 

صفحه 19:
چالش‌هاي موجود در خوشه‌بندي مقید © با وجود الگوبتم هاي بسیار در خوشه بندي مقید چالشهايي در این حوزه وجود دارد که نیازمند تحقیق گسترده مي باشد. 5 جكونه مىتوان ميزان سودمندی بيك مجموعه قيد را اندازه كرفت؟ چگونه می‌توان هزینه فراهم کردن| قیدها را کمینه نمود؟ چگونه می‌تون اطلاعات قيدها را به نواحی مجاور انتشار داد؟ Sharif دسا 

صفحه 20:
چالش‌هاي موجود در خوشه‌بندي مقید © مجموعه قيدهاي متفاوت سودمندي منفاوتي براي الگوريتم‌هاي خوشه‌يندي دارند © قيدهايي که الگوریتم خوشه‌بندي به خودي خود قادر به استخراج آن از دلده‌ها باشد, تاثیر چنداني بر بهبود دقت خوشه‌بندي نخواهد © به الگوریتم خوشه‌بندي این قابليت را مي‌دهد که مجموعه قید در راستاي خوشه‌بندي استفاده نماید یا خیر © انتخاب بهترین مجموعه قید ممکن. * از 1000 بار انتخاب تصادفي مجموعه قيدهاي 25 تابي. درصد مواردي که سیب کاهش دقت خوشه‌بندي در چند الگوريتم شده است. (جدول از 660161 harif سل سس لا 

صفحه 21:
چالش‌هاي موجود در خوشه‌بندي مقید © در يك مجموعه داده با © نمونه. ©/(5401)» قيد کاندید براي | انتخاب ۸ بهترین قید چگونه ا به گونه اي چالش اول را در خود دارد. _رفع این چالش با معرفي معيارهاي کارامد براي تعيين سودمندي يك مجموعه قید. سبب کاهش هزینه گردآوري قیدها میگردد. اب وجود دارد. * روشها © انتخاب قيدها ازميان باداذه (4/>8 است كه حر آن هزيته گرداري قیده فقط شامل برچسبگذاري ب ده مي‌باش © بیمایش دورترین-لین 10۳406 ۱ © انتخلب فعال فيدها به كمك تشخيص نقاط مرزي [©0640] eq 

صفحه 22:
چالش‌هاي موجود در خوشه‌بندي مقید _ تمامي روش‌هاي خوشه بندي مقید بر این فرض استوارند که انتشار محلي اطلاعات قیدها به همسایه‌ها ايمن بوده و مي تواند سیب بهبود نتیجه خوشه‌بندي گردد. © مسائل مهم: _ تشخیص ایمن بودن انتشار قيد بر روي يك مجموعه داده خاص © درجه انتشار قید به همسای‌ها (تعیین شعاع همسايگي بهینه و .. وه 

صفحه 23:
خوشه‌بندي مقید با رویکرد انتخاب فعال قيدها © مساله: خوشه‌بندي مقید با رويكرد انتخاب فعال قيدها © نكاه تكرارشوتده به حل مساله و تعس ديا 0تعيين ميزان سودمندي بك قيد مشخص 9تاثير انتخا افيد بر نخاب قبدهاي بسي 0تعيين ميزان سودمندي بك مجموعه قبد 0تعریف تابع هدف مناسب براي انتخاب يك مجموعه قید. Sharif NVERSTY 0F 11 TC) 

صفحه 24:
* ارائه یک روش خوشه بندی مقید ۶ مبتنی بر یادگیری معیار فاصله © حفظ ساختار را در حین تبدیل در نظر می گیرد.., _درجه اهمیت قیدها را هم در نظر می گیرد 

صفحه 25:
مدل خطي رویکرد دوم © _ در مدل خطي © يادگيري ماتریس تبدیل 1۳0 ;3 ‎AT‏ tr(AT X(2a.L°)X7 A) tran AT REV XTALBATXU—W")TU-W*)XT A) 8 tr(ATX(2acL°)X7A arg MAX 44T =F ATX QamL¥+3—-W*)? U-Ws))XTA))* AY = argmaxgyr_y 12 ‘nl Le = Do -we [yt Wass Un] IM = (31-4 ‎rg tle D? 4D?‏ لهميتق يدهايه اين سود و نفی‌پسوند )و 007 ماتريسرهاوق طريحاصراز جمع ستوني ۳( و 000 به صورت مستقيم ب رويكردهاي تجزيه طيفي قابل حل نميباشد. #شده در [26۸000//069]براي یافتن ماتریس بهینه 60 استفاده مي شود. ‎ ‏از روش ارا ‎ ‎harif ‎UNIVERSITY ‏بن ماوع دعو‎ 011111111101011 © 

صفحه 26:
مدل غيرخطي روبکرد دوم © _ در مدل غيرخطي (o(z),0(u)) = ‏رها‎ @ RP RF 1 Vi. Vas يك ماتريس ‎RR!‏ باجايكذاري در مدل اصلي داريم: ‎fhe tr(ATO(2a.L°)7 A)‏ ee era (AT@Qa,L™ + Ad —Wa)h — Wea) © استفاده از توابع هسته براي حالت غيرخطي اشرق ارس د مو 2 ‎Ad] :BF 4 Re‏ 4 © تبديليافته دادهها در فضاي هسته ‎O(¢n)]‏ ....,)0(22 (رم)ما عق 6 توشتن هر بردار 00 به صورت تركيب خطي از نقاط (2) .... ,(و)ة ,لضاة ۰ ۰ 5 8 11:7 57 ‏را ع2‎ ۱ TET Po, ] (7 1-172۳۳۳0۲ tr(V7 K(2aeL°)KV) ATE MAXV YT =T HVT K Qa LER ۲۳۳(۳ ۱-۳۰ © تبدیل بهینه نقاط به فضاي مقصد 

صفحه 27:
انتخاب فعال قیدها (مستقل از الگوریتم خوشه بندی مقید) 0ايده: استفاده از اطلاعات مرزداده ها مسائل مطرح: 0تعيين ميزان سودمندي يك فيد مشخص با استفاده از فاصله نقاط مرزى تاثير انتخاب بك قيد ير التخاب فيدهاي بعدي 0ب تعريف فاصله فید کاندید با قيدهاى قبلى #تعبين ميزان سودمندي بك مجموعه فيد 0حاصل جمع سودمندی قید با درنظرگرفتن ترتیب 0تعريف تابع هدف مناسب براي انتخاب بك مجموعه قيد جو وه و رود رین 

صفحه 28:
66 UuWERsITY oF TEcHNOLOSY, 

صفحه 29:
نگاه تکرارشونده به حل مساله در ادامه راه - سودمندی قید بسیار به الگوریتمی که از آن استفاده می کند وابسته است. - ارائه راهکاری برای انتخاب قید در حین خوشه بندی Sharif UNVERSTY 0 110 5:١ ‏ات ا‎ 

صفحه 30:
0 6 (,100) روما مانب( ‎Oowerenee ou‏ عمط ۰ رها تسود 0 Oar, O. Corde, ©. Rongre, ead ©. Ochevd, "Onsstraand kewrene chester ia ‏تسسا‎ oven howe,” “ha Proceeding oP “keer oarad OP ereare oa Darke Lewrann (100L), AOL ‘OM, ~.SPP-GOF, COOA. ] ‏هت‎ © [ . 1. Deurbooa ced ©. ©. (Revs, "Ohotrtog wal cosets! Peasbity eaves ced he keene ‏,ساسا‎ a Proceeding oF ODD ‘haerretooal OoPereure on (Dera Drees, ADDS. [bDO}. . em, .0. Cerover, cael O. . Daxets, “Proc Rexncetevel owen w epane uel over! chica he coos! oP pr hooulexk dara hiss,” “a Proveedheee oP be nereends “apres OrxPereace ox Dunkioe Learvns, JOOL ‘D2, pp 20/P-OUP, DOO. [Co~LetDO] ©. Bartel, ۳۰ Lerts, . Ohevtd, rl (D. Derek, "Lrarciy cece ‏ای مهس‎ ‏ها م فقوت‎ Ia Procerchace of “iter actzcal OoxP erecre on Darke Leursiss; (OL), ppki— 08, 8009. | laren apphcatr © chester nt Lud ‏وق وهی امس‎ oP (Deurd ‘lores Procesin Oper (DRO), pp: SOG. 602, E008. Sharif UNVERSTY OF 11 <2) 

صفحه 31:
0 De, ore ©. “Lhomy, “Leary 9 evakoknnbe detoare wer Por dara chert ood ‏"ماه‎ Patera Rerexnira, Onl P, Oo, pp. 9XDD-VAE, BODO. [Dem fd). &. Dor, "Sewerrerveed cre karte by wxnteie commas carps," TBEE Prencastice oa Oysews, Dos, oad Opberews, Pat 8, AE, Oo, pp BH-B9O, OOM وا رو یه روا هوجو مه موه مه نت رنهاب را ‎[DO].‏ ‏را ‎oa Dakine‏ یی سوه 2 با ‎chesP care," ha Proceetkng oP‏ مود ‎OOOO.‏ ,مه کم ‎ODL),‏ وا سا( مه لو تسس 0 ©. ©. Gow, “Doorkearmene lara vein pants ‏لمك بحاصت‎ ‏سا لو بو اوق‎ «power sivenre oP ches,” Patera ‏موس‎ ۱۱۵, 0, 72908-8092, BOW, [DaerFPOO |. 0. Oapni onl ©. Candy, ‘Cheterini uth netnare-kuel comers,” Provera oP be ‏و‎ ‘harrrarad Oowereure os Durkice Leurven (ODL ODDO), pr AKKDOKMID, ODDO. [WeprPADO]. (. DexentP, O. Corte, ©. Roxers, wee ©. ‏وا سا لو ماوت‎ was barker ‏وله‎ Ja ‏من لین جع او وولو‎ Duckie Learacny (ADL), ODL 04, ~EPP-GOF, 8001. Sharif NVERSTY 0F 1 ‏ال‎ 

صفحه 32:
(opr PPOO]. (C. DexpxhP, “Oche, vont, ‏و را اه و هه ما باه لو‎ oP ©! Tetercterrd (Dorkokop on (Korwleke Decry ۰ ‏,هت مها‎ ۵ 0006, do, 8009. ] om RU. Dovey, “Bowe sewe super vera Por parse ‏سسجت‎ ‎cheater” 0 ‏م۳‎ of the Pow KB ‘irsntomd OP errace oa Dats Drie, pp. 39O— 5۵, 600 حصي سوه ‎exexriieg‏ را رده وه موه ‎Days‏ با :1 لت تططلصط 0۰ ‎P69]. Q. Xu,‏ ,00 ,هه روم مه وه تسم ‎vectors," In Proceeding of te Of‏ ‎BOOS‏ ۵۵-۵0 مر ] 6 06[ 1۰ Devedoon, ۱: ‏موه‎ oad ©. ‏ده ام یفوص" بح‎ ‏موی‎ la Proceeding ‏موی( رتم۳ له‎ om (Keene Decovery ord Destress ] wr.MS189, B00. [DekpragedXDO]. P_(C. Dokpragads, (Rl, ood @. CC. dota, “Beare query ‏ام مج چا ماه‎ cheater” bo Proceed oP haierntead OnPereue oa Patera Recon, pr, 600006. [OME]. 0.0. Oy, ©. Labracke, ond B. Orch ‏رجا لوصو‎ uit ste ‏",ساد رسو‎ Pamra Revoir, OPS, Do, pp. PPO-APHO, OOO. Sharif NVERSTY 0 11 ‏3ؤؤآؤآؤآؤآ‎ 

صفحه 33:
‎specird cheney” a Procede of ‘hieratood OrPerrare‏ و :0 ,960696 (1000) ما مت مد ‎[LoD]. 6.0.41. hea, Raho, od O. R. Lia, “Lraraces socparcnoeny kere waroee Brow parse | oocPereuce om (Darke fearay, promod Ont ere 7a Darke Leorciny (ODL), pp 9-990, BOOP. ‎VAM). ©. Lau, X. Pra, D. Par, ord I. Lei, "Coveircied cree: arcana det ‏"مف همه وی‎ 1 CProverdage of (BBO OncP rear oa (Brifiad Inehgrrrr, BBO1 6۵0, ۰ ‎[@rrOO]. 0.Crre, 0. Orexm, ‏موه‎ “Boive sectswperveed Keay cherie,” Patera ‏همست‎ OPA, Ov.O, ppMOOFAOPP, OOOO, ‎Sharif ‎NVERSTY OF 11 TC) ‎ 

صفحه 34: