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

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

اسلاید 1: خوشه‌بندي مقيد Constrained Clustering

اسلاید 2: 2فهرست مطالبمقدمه ای بر خوشه بندیارزیابی خوشه بندیخوشه بندی مقیدچالشها و راهکارهاپژوهش های انجام شده

اسلاید 3: 3خوشه‌بنديخوشه‌بنديگروه‌بندي داده‌ها به گونه‌اي که خصوصيات مشترک بين داده‌هاي هر گروه زياد و خصوصيات مشترک بين گروه‌هاي متفاوت کم باشد.سوال 1: خصوصيات مشترک؟ چگونگي تشخيص خصوصيات؟طيف وسيع كاربرديادگيري ماشين، هوش مصنوعي، الگوشناسي، وب كاوي، تحليل پايگاه داده، پردازش متون و تصاوير، علوم پزشكي، علوم اجتماعي، اقتصاد و تجارت، علوم كامپيوتر، پزشكيخوشه‌بندي به عنوان يك مساله مشكل مهم‌ترين دلايل مشكل‌بودن مساله:ذات بدون ناظر بودن الگوريتم‌هاي خوشه‌بنديابهام در تعريف خوشه مناسبمشكل بودن تعريف معيار فاصله مناسبتعريف تابع هدف مناسب به منظور خوشه‌بنديعدم وجود الگوريتم جامع براي حل همه مسائل خوشه‌بندي

اسلاید 4: 4روشهاي خوشه‌بندي (دسته بندی)

اسلاید 5: ارزیابی کلاسترینگچند مسالهتمایل به خوشه بندی شدن داده؟آیا یک ساختار غیر تصادفی در داده وجود دارد؟استفاده از تستهای آماریتعداد خوشه ها؟برخی الگوریتم ها نیاز به دانستن تعداد خوشه ها قبل از خوشه بندی دارند.راهکارهای تقسیم و ادغام با معیارهایی از قبیل واریانس درون و برون خوشه ایکیفیت خوشه بندی انجام شده؟خوشه بندی انجام شده چقدر خوب است؟ارائه معیارهای ارزیابی مناسب5

اسلاید 6: ویژگیهای یک معیار ارزیابی مناسب (4 شرط)Cluster homogeneityهر چه خلوص در خوشه بندی (با دانستن کلاس اصلی داده ها، داده های هم کلاس در یک خوشه قرار بگیرند) بیشتر باشد این معیار بیشتر است.داده های دسته های متفاوت در خوشه های متفاوت قرار داده شوند.6

اسلاید 7: ارزیابی کلاسترینگ (کیفیت خوشه بندی انجام شده؟)Cluster completenessنقطه مقابل Cluster homogeneityداده ها ی دسته های یکسان در خوشه های یکسان قرار داده شوند.7

اسلاید 8: ارزیابی کلاسترینگ (کیفیت خوشه بندی انجام شده؟)Rag bagدر برخی مسایل دسته ای به نام «متفرقه» داریم که شامل داده هایی است که نمی توانند با داده های دیگر کلاسها هم خوشه شوند.جریمه انتساب این نوع داده ها به یک خوشه خالص بیشتر از انتساب آنها به خوشه متفرقه است .8

اسلاید 9: ارزیابی کلاسترینگ (کیفیت خوشه بندی انجام شده؟)Small cluster preservationهدف: ممانعت از شکسته شدن دسته های کوچک اشیاتقسیم یک دسته کوچک از اشیا به دسته های ریز بسیار خطرناکتر از تقسیم دسته بزرگ به دسته های کوچکتر است.داده ها ممکن است با فرض نویز یا outlier حذف شوند.9

اسلاید 10: ارزیابی کلاسترینگ (کیفیت خوشه بندی انجام شده؟)معیار Bcubed10

اسلاید 11: 11مسائل مطرح خوشه‌بنديذات بدون ناظر مسالهپيش فرضهاي اوليهساختار داده هامعيارهاي فاصله و شباهتتابع هدفعدم انطباق پيش فرضها و مدل واقعي (Model mismatch)راه حل؟استفاده از اطلاعات جانبيبراي كمك به الگوريتم‌هاي خوشه‌بندي جهت توليد فرض‌هاي صحيح

اسلاید 12: اطلاعات جانبيساختار داده‌هاهدف خوشه‌بنديشكل خوشه‌هابيشينه اندازه خوشه‌هاحداكثر اعضاي هر خوشهقيدهاي در سطح نمونهقيدهاي بايد-پيوند Must-link(ML)قيدهاي نفي-پيوند Cannot-link(CL)قابليت اين قيدها در تعريف قيدهاي پيچيده ترقيد وجود حداقل يك همسايه در فاصله ε: با ايجاد قيد بايد-پيوند ميان هر داده و حداقل يكي از نقاط موجود در همسايگي ε12استفاده از اطلاعات جانبي در خوشه‌بنديخوشه بندي مقيدConstrained Clustering(Wagstaff 2000)MLCL

اسلاید 13: 13خوشه‌بندي مقيد (دسته‌بندي)

اسلاید 14: 14خوشه‌بندي مقيد (دسته‌بندي )مبتني بر ارضاء قيد:ارضاء سخت: ارضاء تمامي قيدها به طور كاملرويكرد جستجوي حريصانه، عدم يافتن يك جواب ممكن براي مساله حتي در صورت وجود جوابCOP-KMEANS [Wagstaff01]ارضاء نرم: تا حد ممكن سعي در ارضاء قيدها دارند. روشايدهPCKmeans [Bilenko04]عبارت جريمه براي نقض قيدها در تابع هدف MPCKmeans [Bilenko04] عبارت جريمه براي نقض قيدها در تابع هدف و يادگيري متريك

اسلاید 15: 15خوشه‌بندي مقيد (دسته‌بندي)سلسله مراتبي:با تغيير الگوريتم‌هاي خوشه‌بندي سلسله‌مراتبي قابليت برآورده كردن قيدها را نيز در آنها تعبيه مي‌نمايند.خوشه‌بندي با ساختن دندروگرامي از داده‌هاروش پايه:ابتدا هر داده به عنوان يك خوشه درنظر گرفته مي شود.عمل ادغام خوشه‌ها تا هنگامي كه ادغام آنها هيچ قيدي را نقض نكندروش Davidson [Davidson05]ابتدا بستارهاي تراگذري مربوط به قيدهاي بايد-پيوند (ML) محاسبه مي‌شودخوشه‌بندي را با X1+r خوشه آغاز مي‌نمايد كهX1 تعداد نمونه‌هايي است كه هيچ قيد بايد-پيوندي بر روي آنها اعمال نشده و r تعداد اجزاء همبند حاصل از قيدهاي بايد-پيوند است..انتخاب دو نزديكترين خوشه و ادغام آنها تا زماني كه دو خوشه براي ادغام وجود دارند.

اسلاید 16: 16خوشه‌بندي مقيد (دسته‌بندي)تغيير ماتريس فاصلهاستفاده از اطلاعات قيدها قبل از خوشه‌بندي براي تغيير ماتريس فاصله و استفاده از آن در خوشه‌بندي نهاييروش Klein [Klein02]

اسلاید 17: 17خوشه‌بندي مقيد (دسته‌بندي)يادگيري معيار فاصله به عنوان محبوب‌ترين روش خوشه‌بندي مقيدمعيار فاصله اقليدسي به عنوان معيار فاصله متداول در فرايند خوشه‌بنديناكارامدي معيار فاصله اقليدسي در توصيف صحيح فاصله در يك مجموعه داده نوعيمعيار فاصله ماهالانوبيس بسيار مورد توجه قرار گرفته است

اسلاید 18: 18مزايا و مشكلات استفاده از قيدها در خوشه‌بنديمزاياافزايش ميانگين دقت خوشه‌بندي [Wagstaff00]توليد خوشه‌هايي به شكل دلخواه [Wagstaff01b]مشكلاتشدني بودن (Feasibility)مفيد نبودن هر مجموعه اي از قيدها [Wagstaff06]

اسلاید 19: 19چالش‌هاي موجود در خوشه‌بندي مقيدبا وجود الگويتم هاي بسيار در خوشه بندي مقيد چالشهايي در اين حوزه وجود دارد كه نيازمند تحقيق گسترده مي باشد.

اسلاید 20: 20چالش‌هاي موجود در خوشه‌بندي مقيدمجموعه قيدهاي متفاوت سودمندي متفاوتي براي الگوريتم‌هاي خوشه‌بندي دارندقيدهايي كه الگوريتم خوشه‌بندي به خودي خود قادر به استخراج آن از داده‌ها باشد، تاثير چنداني بر بهبود دقت خوشه‌بندي نخواهد داشتتعيين سودمندي يك مجموعه قيد قبل از خوشه‌بنديبه الگوريتم خوشه‌بندي اين قابليت را مي‌دهد كه تصميم بگيرد كه آيا از يك مجموعه قيد در راستاي خوشه‌بندي استفاده نمايد يا خير.انتخاب بهترين مجموعه قيد ممكن.از 1000 بار انتخاب تصادفي مجموعه قيدهاي 25 تايي، درصد مواردي كه سبب كاهش دقت خوشه‌بندي در چند الگوريتم شده است. (جدول از [Davidson06])

اسلاید 21: 21چالش‌هاي موجود در خوشه‌بندي مقيددر يك مجموعه داده با n نمونه، n(n-1)/2 قيد کانديد براي انتخاب وجود دارد.انتخاب λ بهترين قيد چگونه است؟به گونه اي چالش اول را در خود دارد.رفع اين چالش با معرفي معيارهاي كارامد براي تعيين سودمندي يك مجموعه قيد، سبب كاهش هزينه گردآوري قيدها ميگردد.روشهاانتخاب قيدها از ميان L داده (L<n) است كه در آن هزينه گردآوري قيدها، فقط شامل برچسب‌گذاري L داده مي‌باشد.پيمايش دورترين-اولين [Basu04]انتخاب فعال قيدها به كمك تشخيص نقاط مرزي [Xu05]

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

اسلاید 23: 23خوشه‌بندي مقيد با رويكرد انتخاب فعال قيدهامساله: خوشه‌بندي مقيد با رويكرد انتخاب فعال قيدهانگاه تكرارشونده به حل مسالهتعيين ميزان سودمندي يك قيد مشخصتاثير انتخاب يك قيد بر انتخاب قيدهاي بعديتعيين ميزان سودمندي يك مجموعه قيدتعريف تابع هدف مناسب براي انتخاب يك مجموعه قيدفضاي قيدهاانتخاب قيدها و انتساب درجه اهميت به آنهاخوشه‌بندي مقيدقيدها

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

اسلاید 25: 25مدل خطي رويكرد دومدر مدل خطييادگيري ماتريس تبديل d*DWM و WC ماتريس درجه اهميت قيدهاي بايد-پيوند و نفي-پيوندDM و DC ماتريس هاي قطري حاصل از جمع ستوني WM و WC به صورت مستقيم با رويكردهاي تجزيه طيفي قابل حل نمي‌باشد.از روش ارائه‌شده در [Xiang08] براي يافتن ماتريس بهينه A استفاده مي شود..

اسلاید 26: 26مدل غيرخطي رويكرد دومدر مدل غيرخطياستفاده از توابع هسته براي حالت غيرخطييادگيري ماتريس تبديل به صورتتبديل‌يافته داده‌ها در فضاي هستهنوشتن هر بردار Ai به صورت تركيب خطي از نقاط در نتيجه يك ماتريس وجود دارد كه با جايگذاري در مدل اصلي داريم:تبديل بهينه نقاط به فضاي مقصد

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

اسلاید 28: 28انتخاب فعال قیدهاتوزیع قیدها در فضای داده

اسلاید 29: 29نگاه تكرارشونده به حل مساله در ادامه راه- سودمندی قید بسیار به الگوریتمی که از آن استفاده می کند وابسته است.- ارائه راهکاری برای انتخاب قید در حین خوشه بندیفضاي قيدهاانتخاب فعال قيدهاخوشه‌بندي مقيدقيدها

اسلاید 30: 30منابع (1)[Bilenko04]. M. Bilenko, S. Basu, and R. J. Mooney, “Integrating constraints and metric learning in semi-supervised clustering,” In Proceedings of International Conference on Machine Learning (ICML), 2004.[Wagstaff01]. K. Wagstaff, C. Cardie, S. Rogers, and S. Schrodl, “Constrained k-means clustering with background knowledge,” In Proceedings of International Conference on Machine Learning (ICML), ICML ’01, pp.577–584, 2001.[Davidson05]. I. Davidson and S. S. Ravi, “Clustering with constraints: Feasibility issues and the k-means algorithm,” In Proceedings of SIAM International Conference on Data Mining, 2005.[Klein02]. D. Klein, S. D. Kamvar, and C. D. Manning, “From instance-level constraints to space-level constraints: Making the most of prior knowledge in data clustering,” In Proceedings of the Nineteenth International Conference on Machine Learning, ICML ’02, pp.307–314, 2002.[Bar-Hillel03] A. Bar-Hillel, T. Hertz, N. Shental, and D. Weinshall, “Learning distance functions using equivalence relations,” In Proceedings of International Conference on Machine Learning (ICML), pp.11–18, 2003.[Xing02]. E. P.Xing, A.Y.Ng,M. I. Jordan, and S. J. Russell, “Distancemetric learningwith application to clustering with side-information,” In Proceedings of Neural Information Processing Systems (NIPS), pp.505–512, 2002.

اسلاید 31: 31منابع (2)[Xiang08]. S. Xiang, F. Nie, and C. Zhang, “Learning a mahalanobis distance metric for data clustering and classification,” Pattern Recognition, Vol.41, No.12, pp.3600–3612, 2008.[Wang11]. F. Wang, “Semisupervised metric learning by maximizing constraint margin,” IEEE Transactions on Systems, Man, and Cybernetics, Part B, Vol.41, No.4, pp.931–939, 2011.[Li08]. Z. Li, J. Liu, and X. Tang, “Pairwise constraint propagation by semidefinite programming for semi-supervised classification,” In Proceedings of the 25th international conference on Machine learning, International Conference on Machine Learning (ICML), pp.576–583, 2008.[Soleymani10]. M. S. Baghshah and S. B. Shouraki, “Non-linearmetric learning using pairwise similarity and dissimilarity constraints and the geometrical structure of data,” Pattern Recognition, Vol.43, No.8, pp.2982–2992, 2010.[Wagstaff00 ]. K.Wagstaff and C. Cardie, “Clustering with instance-level constraints,” In Proceedings of the Seventeenth International Conference on Machine Learning (ICML 2000), pp.1103–1110, 2000.[Wagstaff01b]. K. Wagstaff, C. Cardie, S. Rogers, and S. Schrodl, “Constrained k-means clustering with background knowledge,” In Proceedings of International Conference on Machine Learning (ICML), ICML ’01, pp.577–584, 2001.

اسلاید 32: 32منابع (3)[Wagstaff06]. K. Wagstaff, “Value, cost, and sharing: Open issues in constrained clustering,” In Proceedings of 5th International Workshop on Knowledge Discovery in Inductive Databases, KDID 2006, pp.1–10, 2006. [Basu04]. S. Basu, A. Banerjee, and R. J. Mooney, “Active semi-supervision for pairwise constrained clustering,” In Proceedings of the Fourth SIAM International Conference on Data Mining, pp.333–344, 2004.[Xu05]. Q. Xu, M. desJardins, and K. L. Wagstaff, “Active constrained clustering by examining spectral eigen-vectors,” In Proceedings of the 8th international conference on Discovery Science, DS’05, pp.294–307, 2005.[Davidson06]. I. Davidson, K. Wagstaff, and S. Basu, “Measuring constraint-set utility for partitional clustering algorithms,” In Proceedings of Pacific-Asia Conference on Knowledge Discovery and DataMining (PAKDD), pp.115–126, 2006.[Mallapragada08]. P. K. Mallapragada, R. Jin, and A. K. Jain, “Active query selection for semi-supervised clustering,” In Proceedings of International Conference on Pattern Recognition, pp.1–4, 2008.[Vu12]. V.-V. Vu, N. Labroche, and B. Bouchon-Meunier, “Improving constrained clustering with active query selection,” Pattern Recognition, Vol.45, No.4, pp.1749–1758, 2012.

اسلاید 33: 33منابع (4)[Wang10]. X. Wang and I. Davidson, “Active spectral clustering,” In Proceedings of International Conference on Data Mining (ICDM), pp.561–568, 2010.[Hoi07]. S. C. H. Hoi, R. Jin, and M. R. Lyu, “Learning nonparametric kernel matrices from pairwise constraints,” In Proceedings of the 24th international conference on Machine learning, International Conference on Machine Learning (ICML), pp.361–368, 2007.[Liu10]. W. Liu, X. Tian, D. Tao, and J. Liu, “Constrained metric learning via distance gap maximization,” In Proceedings of AAAI Conference on Artificial Intelligence, AAAI 2010, 2010.[Grira08]. N.Grira, M. Crucianu, andN. Boujemaa, “Active semi-supervised fuzzy clustering,” Pattern Recognition, Vol.41, No.5, pp.1834–1844, 2008.

اسلاید 34: 34با تشکر