خوشه بندی مقید Constrained Clustering
2
فهرست مطالب
مقدمه ای بر خوشه بندی
ارزیابی خوشه بندی
خوشه بندی مقید
چالشها و راهکارها
پژوهش های انجام شده
3
خوشه بندی
خوشه بندی
گروه بندی داده ها به گونه ای که خصوصیات مشترک بین داده های هر گروه زیاد و خصوصیات مشترک بین گروه های متفاوت کم باشد.
سوال 1: خصوصیات مشترک؟ چگونگی تشخیص خصوصیات؟
طیف وسیع کاربرد
یادگیری ماشین، هوش مصنوعی، الگوشناسی، وب کاوی، تحلیل پایگاه داده، پردازش متون و تصاویر، علوم پزشکی، علوم اجتماعی، اقتصاد و تجارت، علوم کامپیوتر، پزشکی
خوشه بندی به عنوان یک مساله مشکل
مهم ترین دلایل مشکل بودن مساله:
ذات بدون ناظر بودن الگوریتم های خوشه بندی
ابهام در تعریف خوشه مناسب
مشکل بودن تعریف معیار فاصله مناسب
تعریف تابع هدف مناسب به منظور خوشه بندی
عدم وجود الگوریتم جامع برای حل همه مسائل خوشه بندی
4
روشهای خوشه بندی (دسته بندی)
ارزیابی کلاسترینگ
چند مساله
تمایل به خوشه بندی شدن داده؟
آیا یک ساختار غیر تصادفی در داده وجود دارد؟
استفاده از تستهای آماری
تعداد خوشه ها؟
برخی الگوریتم ها نیاز به دانستن تعداد خوشه ها قبل از خوشه بندی دارند.
راهکارهای تقسیم و ادغام با معیارهایی از قبیل واریانس درون و برون خوشه ای
کیفیت خوشه بندی انجام شده؟
خوشه بندی انجام شده چقدر خوب است؟
ارائه معیارهای ارزیابی مناسب
5
ویژگیهای یک معیار ارزیابی مناسب (4 شرط)
Cluster homogeneity
هر چه خلوص در خوشه بندی (با دانستن کلاس اصلی داده ها، داده های هم کلاس در یک خوشه قرار بگیرند) بیشتر باشد این معیار بیشتر است.
داده های دسته های متفاوت در خوشه های متفاوت قرار داده شوند.
6
ارزیابی کلاسترینگ (کیفیت خوشه بندی انجام شده؟)
Cluster completeness
نقطه مقابل Cluster homogeneity
داده ها ی دسته های یکسان در خوشه های یکسان قرار داده شوند.
7
ارزیابی کلاسترینگ (کیفیت خوشه بندی انجام شده؟)
Rag bag
در برخی مسایل دسته ای به نام «متفرقه» داریم که شامل داده هایی است که نمی توانند با داده های دیگر کلاسها هم خوشه شوند.
جریمه انتساب این نوع داده ها به یک خوشه خالص بیشتر از انتساب آنها به خوشه متفرقه است .
8
ارزیابی کلاسترینگ (کیفیت خوشه بندی انجام شده؟)
Small cluster preservation
هدف: ممانعت از شکسته شدن دسته های کوچک اشیا
تقسیم یک دسته کوچک از اشیا به دسته های ریز بسیار خطرناکتر از تقسیم دسته بزرگ به دسته های کوچکتر است.
داده ها ممکن است با فرض نویز یا outlier حذف شوند.
9
ارزیابی کلاسترینگ (کیفیت خوشه بندی انجام شده؟)
معیار Bcubed
10
11
مسائل مطرح خوشه بندی
ذات بدون ناظر مساله
پیش فرضهای اولیه
ساختار داده ها
معیارهای فاصله و شباهت
تابع هدف
عدم انطباق پیش فرضها و مدل واقعی (Model mismatch)
راه حل؟
استفاده از اطلاعات جانبی
برای کمک به الگوریتم های خوشه بندی جهت تولید فرض های صحیح
اطلاعات جانبی
ساختار داده ها
هدف خوشه بندی
شکل خوشه ها
بیشینه اندازه خوشه ها
حداکثر اعضای هر خوشه
قیدهای در سطح نمونه
قیدهای باید-پیوند Must-link(ML)
قیدهای نفی-پیوند Cannot-link(CL)
قابلیت این قیدها در تعریف قیدهای پیچیده تر
قید وجود حداقل یک همسایه در فاصله ε: با ایجاد قید باید-پیوند میان هر داده و حداقل یکی از نقاط موجود در همسایگی ε
12
استفاده از اطلاعات جانبی در خوشه بندی
خوشه بندی مقید
Constrained Clustering
(Wagstaff 2000)
ML
CL
13
خوشه بندی مقید (دسته بندی)
14
خوشه بندی مقید (دسته بندی )
مبتنی بر ارضاء قید:
ارضاء سخت:
ارضاء تمامی قیدها به طور کامل
رویکرد جستجوی حریصانه، عدم یافتن یک جواب ممکن برای مساله حتی در صورت وجود جواب
COP-KMEANS [Wagstaff01]
ارضاء نرم: تا حد ممکن سعی در ارضاء قیدها دارند.
15
خوشه بندی مقید (دسته بندی)
سلسله مراتبی:
با تغییر الگوریتم های خوشه بندی سلسله مراتبی قابلیت برآورده کردن قیدها را نیز در آنها تعبیه می نمایند.
خوشه بندی با ساختن دندروگرامی از داده ها
روش پایه:
ابتدا هر داده به عنوان یک خوشه درنظر گرفته می شود.
عمل ادغام خوشه ها تا هنگامی که ادغام آنها هیچ قیدی را نقض نکند
روش Davidson [Davidson05]
ابتدا بستارهای تراگذری مربوط به قیدهای باید-پیوند (ML) محاسبه می شود
خوشه بندی را با X1+r خوشه آغاز می نماید کهX1 تعداد نمونه هایی است که هیچ قید باید-پیوندی بر روی آنها اعمال نشده و r تعداد اجزاء همبند حاصل از قیدهای باید-پیوند است..
انتخاب دو نزدیکترین خوشه و ادغام آنها تا زمانی که دو خوشه برای ادغام وجود دارند.
16
خوشه بندی مقید (دسته بندی)
تغییر ماتریس فاصله
استفاده از اطلاعات قیدها قبل از خوشه بندی برای تغییر ماتریس فاصله و استفاده از آن در خوشه بندی نهایی
روش Klein [Klein02]
17
خوشه بندی مقید (دسته بندی)
یادگیری معیار فاصله به عنوان محبوب ترین روش خوشه بندی مقید
معیار فاصله اقلیدسی به عنوان معیار فاصله متداول در فرایند خوشه بندی
ناکارامدی معیار فاصله اقلیدسی در توصیف صحیح فاصله در یک مجموعه داده نوعی
معیار فاصله ماهالانوبیس بسیار مورد توجه قرار گرفته است
18
مزایا و مشکلات استفاده از قیدها در خوشه بندی
مزایا
افزایش میانگین دقت خوشه بندی [Wagstaff00]
تولید خوشه هایی به شکل دلخواه [Wagstaff01b]
مشکلات
شدنی بودن (Feasibility)
مفید نبودن هر مجموعه ای از قیدها [Wagstaff06]
19
چالش های موجود در خوشه بندی مقید
با وجود الگویتم های بسیار در خوشه بندی مقید چالشهایی در این حوزه وجود دارد که نیازمند تحقیق گسترده می باشد.
20
چالش های موجود در خوشه بندی مقید
مجموعه قیدهای متفاوت سودمندی متفاوتی برای الگوریتم های خوشه بندی دارند
قیدهایی که الگوریتم خوشه بندی به خودی خود قادر به استخراج آن از داده ها باشد، تاثیر چندانی بر بهبود دقت خوشه بندی نخواهد داشت
تعیین سودمندی یک مجموعه قید قبل از خوشه بندی
به الگوریتم خوشه بندی این قابلیت را می دهد که تصمیم بگیرد که آیا از یک مجموعه قید در راستای خوشه بندی استفاده نماید یا خیر.
انتخاب بهترین مجموعه قید ممکن.
از 1000 بار انتخاب تصادفی مجموعه قیدهای 25 تایی، درصد مواردی که سبب کاهش دقت خوشه بندی در چند الگوریتم شده است. (جدول از [Davidson06])
21
چالش های موجود در خوشه بندی مقید
در یک مجموعه داده با n نمونه، n(n-1)/2 قید کاندید برای انتخاب وجود دارد.
انتخاب λ بهترین قید چگونه است؟
به گونه ای چالش اول را در خود دارد.
رفع این چالش با معرفی معیارهای کارامد برای تعیین سودمندی یک مجموعه قید، سبب کاهش هزینه گردآوری قیدها میگردد.
روشها
انتخاب قیدها از میان L داده (L<n) است که در آن هزینه گردآوری قیدها، فقط شامل برچسب گذاری L داده می باشد.
پیمایش دورترین-اولین [Basu04]
انتخاب فعال قیدها به کمک تشخیص نقاط مرزی [Xu05]
22
چالش های موجود در خوشه بندی مقید
تمامی روش های خوشه بندی مقید بر این فرض استوارند که انتشار محلی اطلاعات قیدها به همسایه ها ایمن بوده و می تواند سبب بهبود نتیجه خوشه بندی گردد.
مسائل مهم:
تشخیص ایمن بودن انتشار قید بر روی یک مجموعه داده خاص
درجه انتشار قید به همسایه ها (تعیین شعاع همسایگی بهینه و …
23
خوشه بندی مقید با رویکرد انتخاب فعال قیدها
مساله: خوشه بندی مقید با رویکرد انتخاب فعال قیدها
نگاه تکرارشونده به حل مساله
تعیین میزان سودمندی یک قید مشخص
تاثیر انتخاب یک قید بر انتخاب قیدهای بعدی
تعیین میزان سودمندی یک مجموعه قید
تعریف تابع هدف مناسب برای انتخاب یک مجموعه قید
24
خوشه بندی مقید
ارائه یک روش خوشه بندی مقید
مبتنی بر یادگیری معیار فاصله
حفظ ساختار را در حین تبدیل در نظر می گیرد.
درجه اهمیت قیدها را هم در نظر می گیرد
25
مدل خطی رویکرد دوم
در مدل خطی
یادگیری ماتریس تبدیل d*D
WM و WC ماتریس درجه اهمیت قیدهای باید-پیوند و نفی-پیوند
DM و DC ماتریس های قطری حاصل از جمع ستونی WM و WC
به صورت مستقیم با رویکردهای تجزیه طیفی قابل حل نمی باشد.
از روش ارائه شده در [Xiang08] برای یافتن ماتریس بهینه A استفاده می شود..
26
مدل غیرخطی رویکرد دوم
در مدل غیرخطی
استفاده از توابع هسته برای حالت غیرخطی
یادگیری ماتریس تبدیل به صورت
تبدیل یافته داده ها در فضای هسته
نوشتن هر بردار Ai به صورت ترکیب خطی از نقاط
در نتیجه یک ماتریس وجود دارد که
با جایگذاری در مدل اصلی داریم:
تبدیل بهینه نقاط به فضای مقصد
27
انتخاب فعال قیدها (مستقل از الگوریتم خوشه بندی مقید)
مسائل مطرح:
تعیین میزان سودمندی یک قید مشخص
با استفاده از فاصله نقاط مرزی
تاثیر انتخاب یک قید بر انتخاب قیدهای بعدی
با تعریف فاصله قید کاندید با قیدهای قبلی
تعیین میزان سودمندی یک مجموعه قید
حاصل جمع سودمندی قید با درنظرگرفتن ترتیب
تعریف تابع هدف مناسب برای انتخاب یک مجموعه قید
ایده: استفاده از اطلاعات مرز داده ها
28
انتخاب فعال قیدها
توزیع قیدها در فضای داده
29
نگاه تکرارشونده به حل مساله در ادامه راه
– سودمندی قید بسیار به الگوریتمی که از آن استفاده می کند وابسته است.
– ارائه راهکاری برای انتخاب قید در حین خوشه بندی
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
منابع (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
منابع (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
منابع (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
با تشکر