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