کنفرانس بین المللی محاسبات نرم

صفحه اصلی / چهارمین کنفرانس بین المللی محاسبات نرم

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

نویسندگان :

مژگان سادات مشیریان¹ مهدی هاشم زاده² شهین پوربهرامی³

1- دانشگاه شهیدمدنی آذربایجان 2- دانشگاه شهید مدنی آذربایجان 3- دانشکده مهندسی کامپیوتر دانشگاه فنی و حرفه ای تهران

کلمات کلیدی :

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

چکیده :

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