یک روش خوشه بندی خودکار با استفاده از رابطه همسایگی متقابل داده ها و ساختار هندسی دایره آپولونیوس

در بسیاری از مسائل یادگیری ماشین و داده کاوی مانند طبقه بندی و خوشه بندی، از الگوریتم های ساخت همسایگی برای مدل سازی روابط محلی بین نمونه های داده استفاده می شود. در یافتن ارتباط بین نقاط داده، تشخیص دقیق همسایگی نقاط به طور انکارناپذیری برای کاوش داده ها مفید است. طی سالیان اخیر، برخی روش های تشخیص همسایگی مبتنی بر ساختارهای هندسی ارائه شده اند که به دلیل دقت بالا در مکان یابی نقاط همسایگی بسیار کارآمد بوده اند. با این حال اغلب این روش ها برای تشکیل گروه های مشابه نیاز به بررسی همه نقاط همسایگی دارند. از این رو، هزینه های محاسباتی بالایی دارند. در این میان، ساختار دایره آپولونیوس در ارزیابی شباهت های محلی در بین مشاهدات، عملکرد بهتری از خود نشان داده است و زمینه جدیدی از علم هندسه را در داده کاوی گشوده است. ساختار آپولونیوس امکان معرفی دانش پنهان را از طریق معرفی معیارهای هندسه فراهم می کند و می تواند یک منطقه همسایگی پویا را برای نقاط داده تعریف کند. در این مقاله، با بهره گیری از مزایای ساختار هندسی دایره آپولونیوس و ایده همسایگان متقابل داده ها، یک روش خوشه بندی خودکار ارائه می شود. از ویژگی همسایگی متقابل نقاط داده برای تشخیص سریع و بهینه همسایگی نقاط داده، شناسایی نواحی متراکم و کشف داده های پرت (نویز) استفاده می شود. از ساختار هندسی دایره آپولونیوس نیز برای تعیین شعاع همسایگی نواحی متراکم (با چگالی داده بالا) استفاده می شود. طوری که برای هریک از نواحی، یک شعاع همسایگی پویا و متناسب با نقاط داده مربوطه استخراج می شود. طی این دو فرایند، هم تعداد خوشه های بهینه و هم اعضا هر خوشه شناسایی می شود. بدین ترتیب یک روش خوشه بندیخودکار حاصل می شود که بدون نیاز به دریافت پارامتر خاصی، حتی تعداد خوشه ها، می تواند عمل خوشه بندی داده ها را انجام دهد. آزمایش های انجام شده بر روی مجموعه داده های استاندارد و مقایسه نتایج با دیگر روش ها، نشان از عملکرد مناسب روش پیشنهادی دارد.

کلیدواژه ها:

داده کاوی ، تشخیص همسایگی ، ساختار هندسی ، دایره آپولونیوس ، همسایگان متقابل ، خوشه بندی