خوشه بندی خودکار

الگوریتم های خوشه بندی خودکار الگوریتم هایی هستند که بدون داشتن پیش اطلاعات از مجموعه داده ها کار میکنند. بر خلاف سایر الگوریتم های خوشه بندی، الگوریتم خوشه بندی خودکار در حضور نویز و داده های پرت نیز میتواند تعداد بهینه خوشه هارا محاسبه کند.

مبتنی بر مرکز[ویرایش]

در مجموعه‌ای از n شی، الگوریتم های مبتنی بر مرکز، k دسته براساس تابعی از عدم شباهت ایجاد میکنند به طوری که k≤n برقرار می باشد. مشکل اصلی در بکارگیری این نوع الگوریتم، تعیین تعداد مناسب خوشه‌ها برای داده های بدون برچسب است.بنابراین قسمت عمده ای از تحقیقات در تجزیه و تحلیل خوشه بندی بر روی خودکارسازی فرآیند متمرکز شده است.

انتخاب خودکار k در الگوریتم خوشه‌بندی K- means، یکی از پرکاربردترین الگوریتم های خوشه بندی مبتنی بر مرکز، همچنان یک مشکل اساسی در یادگیری ماشین می باشد. پذیرفته شده ترین راه حل برای این مشکل روش البو (elbow method) می باشد.این روش شامل اجرای الگوریتم خوشه بندی K-means روی مجموعه ای از داده ها با طیف گسترده ای از مقادیر، محاسبه مجموع مربعات خطاها برای هر کدام از خوشه ها و رسم آنها در نمودار خطی می باشد.اگر نمودار به شکل یک بازو پدیدار شود بهترین مقدار برای k, روی elbow می باشد.^[۱]

روش دیگری که الگوریتم K-means برای مدیریت انتخاب خودکار تعداد بهینه خوشه ها استفاده میکند الگوریتم G-means می‌ باشد. این الگوریتم براساس نظریه پیروی توزیع داده های یک مجموعه از توزیع گاوسی توسعه داده شده است. بنابراین k تا زمانی افزایش پیدا میکند که داده های مراکز هر کدام از دسته های K-means گاوسی شود. این الگوریتم فقط به سطح معناداری از آمار های استاندارد به عنوان پارامتر نیاز دارد و محدودیتی برای کوواریانس داده ها تعیین نمیکند.^[۲]

مبتنی بر اتصال (خوشه بندی سلسله مراتبی)[ویرایش]

خوشه‌بندی مبتنی بر اتصال یا خوشه‌بندی سلسله مراتبی بر این ایده استوار است که اشیاء شباهت‌های بیشتری به دیگر اشیاء نزدیک دارند تا با اشیای دورتر. بنابراین، خوشه های تولید شده از این نوع الگوریتم، حاصل فاصله بین اشیاء مورد تجزیه و تحلیل خواهند بود.

مدل‌های سلسله مراتبی می‌توانند تقسیم‌کننده باشند، به طوریکه در آن پارتیشن‌ها از کل مجموعه داده‌های موجود ساخته می‌شوند، یا انباشته شوند، که در آن هر پارتیشن با یک شی شروع می‌شود و اشیاء اضافی به مجموعه اضافه می‌شوند.^[۳] اگرچه خوشه بندی سلسله مراتبی این مزیت را دارد که اجازه می دهد هر متریک معتبری به عنوان فاصله تعریف شده استفاده شود، ولی به نویز و نوسانات در مجموعه داده حساس است و خودکار کردن آن دشوارتر است.

روش‌هایی برای بهبود و خودکارسازی الگوریتم‌های خوشه‌بندی سلسله مراتبی موجود^[۴] مانند نسخه خودکار تجزیه و تحلیل خوشه‌ای سلسله مراتبی پیوندی (HCA) ایجاد شده‌اند. این روش کامپیوتری موفقیت خود را بر روی یک رویکرد کاهش پرت خودسازگار و به دنبال ایجاد یک تابع توصیفی استوار می‌کند که امکان تعریف خوشه‌های طبیعی را فراهم می‌کند. اشیاء دور ریخته شده را نیز می توان به این خوشه ها اختصاص داد. اساساً برای شناسایی خوشه های طبیعی نیازی به متوسل شدن به پارامترهای خارجی نیست. اطلاعات جمع‌آوری‌شده از HCA، خودکار و قابل اعتماد، می‌تواند در یک دندروگرام با تعداد خوشه‌های طبیعی و جداسازی مربوطه از سر گرفته شود، گزینه‌ای که در HCA کلاسیک یافت نمی‌شود. این روش شامل دو مرحله زیر می‌شود: حذف نقاط پرت (این در بسیاری از برنامه‌های فیلترینگ اعمال می‌شود) و یک طبقه‌بندی اختیاری که امکان گسترش خوشه‌ها را با کل مجموعه اشیاء فراهم می‌کند.^[۵]

BIRCH (کاهش و خوشه بندی متوازن تکرار شونده با استفاده از سلسله مراتب) الگوریتمی است که برای انجام خوشه بندی مبتنی بر اتصال برای مجموعه داده های بزرگ استفاده می شود.^[۶] این الگوریتم به عنوان یکی از سریعترین الگوریتم های خوشه بندی در نظر گرفته می شود، اما محدود است زیرا به تعداد خوشه ها به عنوان ورودی نیاز دارد. بنابراین الگوریتم های جدیدی بر اساس BIRCH ایجاد شده است که در آنها نیازی به ارائه شمارش خوشه از ابتدا نیست، اما کیفیت و سرعت خوشه ها را حفظ می کند. اصلاح اصلی حذف مرحله نهایی BIRCH است، جایی که کاربر باید تعداد خوشه را وارد می‌کرد، و با بهینه‌سازی یک پارامتر آستانه از داده‌ها، بقیه الگوریتم را که درخت-BIRCH نامیده می‌شود، بهبود بخشید. در این الگوریتم به دست آمده، پارامتر آستانه از حداکثر شعاع خوشه و حداقل فاصله بین خوشه ها که اغلب شناخته شده هستند، محاسبه می شود. این روش ثابت کرد که برای مجموعه داده های با تعداد ده ها هزار خوشه کارآمد است. اگر فراتر از این مقدار برویم، مشکل تقسیم ابرخوشه ای معرفی می شود. برای این کار، الگوریتم‌های دیگری مانند MDB-BIRCH توسعه یافته‌اند که تقسیم‌بندی فوق‌خوشه‌ای را با سرعت نسبتاً بالایی کاهش می‌دهد.

مبتنی بر تراکم[ویرایش]

بر خلاف روش‌های پارتیشن‌بندی و سلسله مراتبی، الگوریتم‌های خوشه‌بندی مبتنی بر چگالی قادرند خوشه‌هایی با هر شکل دلخواه و نه تنها کره‌ها را پیدا کنند.

الگوریتم خوشه‌بندی مبتنی بر چگالی از یادگیری ماشینی مستقل استفاده می‌کند که الگوهای مربوط به موقعیت جغرافیایی و فاصله تا تعداد خاصی از همسایگان را شناسایی می‌کند. این الگوریتم مستقل در نظر گرفته می شود زیرا دانش پیشینی در مورد آنچه که یک خوشه است مورد نیاز نیست.^[۷]این نوع الگوریتم روش های مختلفی را برای یافتن خوشه ها در داده ها ارائه می دهد. سریعترین روش DBSCAN است که از فاصله مشخصی برای تمایز بین گروههای متراکم اطلاعات و نویز پراکنده استفاده می کند. علاوه بر این، HDBSCAN می تواند با استفاده از طیف وسیعی از فواصل به جای یک فاصله مشخص، خود تنظیم شود. در نهایت، روش OPTICS یک نمودار دسترسی را بر اساس فاصله از ویژگی های همسایه ایجاد می کند تا نویز را از خوشه هایی با چگالی متفاوت جدا کند.

این روش ها همچنان نیاز به ارائه مرکز خوشه توسط کاربر دارند و نمی توان آنها را خودکار در نظر گرفت. الگوریتم خوشه بندی چگالی محلی خودکار (ALDC) نمونه ای از تحقیقات جدید است که بر توسعه خوشه بندی خودکار مبتنی بر چگالی متمرکز شده است. ALDC چگالی محلی و انحراف فاصله هر نقطه را محاسبه می کند، بنابراین تفاوت بین مرکز خوشه بالقوه و سایر نقاط را گسترش می دهد. این گسترش به دستگاه اجازه می دهد تا به طور خودکار کار کند. ماشین مراکز خوشه را شناسایی می کند و نقاطی را که توسط نزدیکترین همسایه با چگالی بالاتر باقی می ماند، اختصاص می دهد.^[۸]

در اتوماسیون چگالی داده ها برای شناسایی خوشه ها، تحقیقات نیز بر روی تولید مصنوعی الگوریتم ها متمرکز شده است. به عنوان مثال، تخمین الگوریتم‌های توزیع، تولید الگوریتم‌های معتبر را توسط نمودار غیر چرخه‌ای جهت‌دار (DAG) تضمین می‌کند، که در آن گره‌ها رویه‌ها (بلوک ساختمانی) را نشان می‌دهند و یال‌ها دنباله‌های اجرای ممکن بین دو گره را نشان می‌دهند. Building Blocks الفبای EDA یا به عبارت دیگر هر الگوریتم تولید شده را تعیین می کند. الگوریتم‌های خوشه‌بندی که به‌طور مصنوعی تولید می‌شوند با DBSCAN، یک الگوریتم دستی، در نتایج تجربی مقایسه می‌شوند.

منابع[ویرایش]

↑ «Figure S1: Elbow tests of phenotypic microarray array data to determine the number of clusters appropriate for k-means clustering». dx.doi.org. دریافت‌شده در ۲۰۲۳-۰۱-۳۱.
↑ Hamerly, Greg; Elkan, Charles (2002-11-04). "Alternatives to the k-means algorithm that find better clusterings". Proceedings of the eleventh international conference on Information and knowledge management. New York, NY, USA: ACM. doi:10.1145/584792.584890.
↑ "Introducing Clustering II: Clustering Algorithms - GameAnalytics". GameAnalytics (به انگلیسی). 2014-05-20. Retrieved 2018-11-06.
↑ Almeida, J.A.S.; Barbosa, L.M.S.; Pais, A.A.C.C.; Formosinho, S.J. (June 2007). "Improving hierarchical cluster analysis: A new method with outlier detection and automatic clustering" (PDF). Chemometrics and Intelligent Laboratory Systems (به انگلیسی). Elsevier. 87 (2): 208–217. doi:10.1016/j.chemolab.2007.01.005. Archived from the original (PDF) on 15 November 2018. Retrieved 3 November 2022.
↑ Almeida, J.A.S.; Barbosa, L.M.S.; Pais, A.A.C.C.; Formosinho, S.J. (2007-06-15). "Improving hierarchical cluster analysis: A new method with outlier detection and automatic clustering" (PDF). Chemometrics and Intelligent Laboratory Systems (به انگلیسی). 87 (2): 208–217. doi:10.1016/j.chemolab.2007.01.005. hdl:10316/5042. ISSN 0169-7439.
↑ Zhang, Tian; Ramakrishnan, Raghu; Livny, Miron; Zhang, Tian; Ramakrishnan, Raghu; Livny, Miron (1996-06-01). "BIRCH: an efficient data clustering method for very large databases, BIRCH: an efficient data clustering method for very large databases". ACM SIGMOD Record. 25 (2): 103, 103–114, 114. doi:10.1145/235968.233324. ISSN 0163-5808.
↑ Saltus, Christina; Reif, Molly; Johansen, Richard (2021-10-19). "waterquality for ArcGIS Pro Toolbox". {{cite journal}}: Cite journal requires |journal= (help)
↑ "An algorithm for automatic recognition of cluster centers based on local density clustering - IEEE Conference Publication" (به انگلیسی). doi:10.1109/CCDC.2017.7978726. {{cite journal}}: Cite journal requires |journal= (help)

[1] «Figure S1: Elbow tests of phenotypic microarray array data to determine the number of clusters appropriate for k-means clustering». dx.doi.org. دریافت‌شده در ۲۰۲۳-۰۱-۳۱.

[2] Hamerly, Greg; Elkan, Charles (2002-11-04). "Alternatives to the k-means algorithm that find better clusterings". Proceedings of the eleventh international conference on Information and knowledge management. New York, NY, USA: ACM. doi:10.1145/584792.584890.

[3] "Introducing Clustering II: Clustering Algorithms - GameAnalytics". GameAnalytics (به انگلیسی). 2014-05-20. Retrieved 2018-11-06.

[4] Almeida, J.A.S.; Barbosa, L.M.S.; Pais, A.A.C.C.; Formosinho, S.J. (June 2007). "Improving hierarchical cluster analysis: A new method with outlier detection and automatic clustering" (PDF). Chemometrics and Intelligent Laboratory Systems (به انگلیسی). Elsevier. 87 (2): 208–217. doi:10.1016/j.chemolab.2007.01.005. Archived from the original (PDF) on 15 November 2018. Retrieved 3 November 2022.

[5] Almeida, J.A.S.; Barbosa, L.M.S.; Pais, A.A.C.C.; Formosinho, S.J. (2007-06-15). "Improving hierarchical cluster analysis: A new method with outlier detection and automatic clustering" (PDF). Chemometrics and Intelligent Laboratory Systems (به انگلیسی). 87 (2): 208–217. doi:10.1016/j.chemolab.2007.01.005. hdl:10316/5042. ISSN 0169-7439.

[6] Zhang, Tian; Ramakrishnan, Raghu; Livny, Miron; Zhang, Tian; Ramakrishnan, Raghu; Livny, Miron (1996-06-01). "BIRCH: an efficient data clustering method for very large databases, BIRCH: an efficient data clustering method for very large databases". ACM SIGMOD Record. 25 (2): 103, 103–114, 114. doi:10.1145/235968.233324. ISSN 0163-5808.

[7] Saltus, Christina; Reif, Molly; Johansen, Richard (2021-10-19). "waterquality for ArcGIS Pro Toolbox". {{cite journal}}: Cite journal requires |journal= (help)

[8] "An algorithm for automatic recognition of cluster centers based on local density clustering - IEEE Conference Publication" (به انگلیسی). doi:10.1109/CCDC.2017.7978726. {{cite journal}}: Cite journal requires |journal= (help)

[۱]

[۲]

[۳]

[۴]

[۵]

[۶]

[۷]

[۸]